[数据结构]【笔记】学习第二天--线性表~顺序表
本帖最后由 小熊孩 于 2020-9-23 08:38 编辑~~~ properties
当回首往事的时候，不因虚度年华而悔恨.
2020.9.22
~~~
我是真的不太会调格式,而且我是用md写的笔记,调格式调的很烦躁,我把笔记附加到后边了,请下载后病毒查杀!确定安全后打开!!
## 线性表
1. 线性表的定义
* 线性表是具有相同特性的数据元素的一个有限序列
D = { $a_i$ | 1 $\leq$i $\leq$ n, n $\geq$ 0}
R = {r}
r = {<$a_i$,$a_i$$_+$$_1$> | 1 $\leq$i $\leq$ n-1}
* 当一个线性表的元素有序排列时,成为有序线性表
2. 线性表的逻辑特征
对于含有一个元素的线性表,除其实元素没有钱去元素外,其他元素有且只有一个直接前驱元素;除终端元素没有后继元素之外,其他元素有且仅有一个直接后继元素.
3. 线性表的储存结构
* 顺序储存结构(顺序表)
~~~xml
特点:储存位置为一块连续的储存空间
优点:无需额外开辟空间来储存元素之间的关系
~~~
* 链式储存结构(链表)
~~~xml
特点:每个节点带有指针域,比顺序表消费空间大,储存地址可以使不连续(单个节点的地址必须连续)
~~~
* 单链表(注:这里的`->`不是c语言中的指正,只代表指向下一个元素)
* **`pre_e.next`->`cur_e,cur_e.next`->`next_e`**
- pre_e:是当前元素的前驱元素
- cur_e:当前元素
- next_e:是当前元素的后继元素
* 双链表
* 双链表
**`pre_e.next`<->`cur_e.pre,cur_e,cur_e.next`<->`next_e.pre`**
* 循环链表
~~~mermaid
graph LR
A[头结点] -->B(开始节点)
B --> c[....]
c --> d[尾节点]
d --> A
~~~
* 静态链表()
-----
一知半解
(加入此段落,主要是一切对本段知识点的一个总结和回顾,以及一些知识点的比较和认识,自我感觉有助于从整体上了解.)
1. 顺序表和链表储存方式的特点
顺序表的优点是可以随机存取元素,存储密度高;缺点是不便于插入和删除元素(需要移动大量的元素).
链表的优点是便于节点的插入和删除(只需要修改指针域,不需要移动节点);缺点是不能进行随机访问,只能顺序访问,另外,每个节点上增加指针域,导致储存密度低.
2. 在什么情况下使用顺序表比较好?
当现行表很少进行插入和删除操作,或者插入和删除操作总在尾部进行时.
3. 若频繁地对一个线性表进行插入和删除操作,该线性表采用何种储存结构,为什么?
链式储存结构.因为采用链式储存结构储存线性表,在插入和删除操作时只修改相关节点的指针域,不需要移动节点;而采用顺序结构储存线性表是,插入和删除需要平均移动表中的一半元素.修改指针域操作比移动元素华为的时间少很多.
---
## 顺序表的算法
1. 顺序表的定义
2. 顺序表的基本算法
1. 初始化顺序表算法
~~~ java
#define MaxSize 50
typedet struct
{
ElemType data; //存放顺序表的中的元素
int length; //存放顺序表中的长度
} SqList; //声明顺序表的类型
//初始化
void InitList(SqList &L)
{
L.length = 0;
} //时间复杂度 O(1)
~~~
2. 求顺序表中制定元素位置元素值的算法
~~~ java
void GetElem(SqList L, int i, ElemeType &e)
{
if(i<1 || i>L.length)
return 0;
e = L.data; //实际下标从零开始,第一个元素为L.data
return 1;
}//时间复杂度 O(1)
~~~
3. 按元素值查找算法
~~~ java
int LocateElem(SqList L, ElemType e)
{
int i = 0;
while(i<L.length && L.data !=e) i++;
if(L>=L.length)
return 0; //未找到返回0
else
return i+1; //下标+1为所及序号
}//时间复杂度 O(n)
~~~
4. 插入数据元素算法
~~~ java
int LisInsert(SqList &L, ElemType e, int i)
{
int j;
if(i<1 || i>L.length+1)
return 0; //插入失败
i--;
for(j=L.length; j>i; j--) //循环后移
L.data=L.data;
L.data = e;
L.length++; //元素个数+1
return 1; //成功插入
}//时间复杂度 O(n)
~~~
5. 删除数据元素算法
~~~ java
int ListDelete(SqList &L, int i, ElemeType &e)
{
int j;
if(i<1 || i>L.length)
return 0;
i--;
e = L.data;
for(j=i; j<L.length-1; j++)
L.data= L.data;
L.lengh--;
return 1;
}//时间复杂度 O(n)
~~~
3. 有序顺序表的归并算法
~~~ java
/**
* 当一个有顺序表采用顺序表储存时(默认从小到大排序),称为有序顺序表.
* 当两个有序顺序表归并为一个有序顺序表的过程,称为有序顺序表的归并.
**/
void Merge(SqList L1, SqList L2, SqList &L3)
{
int i = 0, j = 0, k = 0;
while(i<L1.Length && j<L2.Length)
{
if(L1.data < L2.data)
{
L3.data = L1.data;
i++; k++;
}
else
{
L3.data = L2.data;
j++; k++;
}
}
while(i<L1.Length)
{
L3.data = L1.data;
i++; k++;
}
while(i<L2.Length)
{
L3.data = L2.data;
j++; k++;
}
return L3.Length = k;
}
~~~
------
## 以下为Java版本
```java
public class SqList<T> {
/**
* 顺序表中一维数组的初始长度
*/
privateint maxSize = 10;
/**
* 存储元素的数组对象
*/
private T[] arr;
private int length;
/**
* 初始顺序表为空
*/
public SqList() {
length = 0;
arr = (T[]) new Object;
}
/**
* 初始顺序表为空
* @param length
*/
public SqList(int length) {
if (length > 0) {
this.length = 0;
maxSize = length;
arr = (T[]) new Object;
} else {
throw new RuntimeException("请输入长度大于0的正整数!");
}
}
/**
* 在指定位置插入新的元素
* @param t
* @param index
* @return
*/
public boolean add(T t, int index) {
if (index < 1 || index > length + 1) {
System.out.println("请输入正确的插入位置!");
return false;
}
//判断当前顺序表是否已满
if (isFull()) {
System.out.println("顺序表已满,插入失败!");
return false;
}
index--;
if (length - index >= 0) {
System.arraycopy(arr, index, arr, index + 1, length - index);
}
arr = t;
length++;
return true;
}
/**
* 删除指定位置的元素,并返回被删除的元素
* @param index
* @return
*/
public T delete(int index) {
if (isEmpty()) {
System.out.println("顺序表为空!");
return null;
}
if (index < 1 || index > length) {
System.out.println("请输入正确的删除位置");
return null;
}
index--;
T t = arr;
if (length - index >= 0) {
System.arraycopy(arr, index + 1, arr, index, length - index);
}
length--;
return t;
}
/**
* 返回第一个相同元素的位置
* @param t
* @return
*/
public int findIndex(T t) {
if (isEmpty()) {
System.out.println("顺序表为空!");
return -1;
}
for (int i = 0; i < length; i++) {
if (arr.equals(t)) {
return i + 1;
}
}
return -1;
}
/**
* 返回指定位置的元素
* @param index
* @return
*/
public T findT(int index) {
if (isEmpty()) {
System.out.println("顺序表为空!");
return null;
}
if (index < 1 || index > length) {
System.out.println("请输入正确的查询位置");
return null;
}
return arr;
}
/**
* 判断顺序表是否已满
* @return
*/
public boolean isFull() {
return maxSize == length;
}
/**
* 判断顺序表是否为空
* @return
*/
public boolean isEmpty() {
return length == 0;
}
/**
* 返回当前顺序表的长度
* @return
*/
public int getLength() {
return length;
}
/**
* 清空顺序表
* @Description 当初始化长度为0时候已经把顺序表清空了,原有的数值会在下次添加时候覆盖掉
*/
public void clearList() {
length = 0;
arr = null;
}
public static void main(String[] args) {
SqList<Integer> list = new SqList<>(10);
System.out.println(list.isEmpty());
System.out.println(list.add(1, 1));
System.out.println(list.isFull());
System.out.println(list.findIndex(1));
System.out.println(list.findT(1));
System.out.println(list.getLength());
System.out.println(list.delete(1));
list.clearList();
System.out.println(list.isEmpty());
}
}
---
链接: https://pan.baidu.com/s/1IK_KW1m1W9-3ITOg7ubVgw 提取码: vscu 复制这段内容后打开百度网盘手机App，操作更方便哦
文件:
很喜欢你这句话 当回首往事的时候，不因虚度年华而悔恨 谢谢楼主的分享。{:1_893:} 留下足迹 考完四级再来
页:
[1]