线性表
目录
2.1 线性表的基本概念
2.2 顺序表
2.3 单链表和循环单链表
2.4 双链表****和循环双链表
2.5 线性表的应用
2.1 线性表基本概念
1.认识线性表
线性表（Linear List）是计算机科学中的一种数据结构，用于存储有限数量的元素，并且这些元素具有线性关系，即每个元素除了第一个和最后一个之外，都有一个前驱和一个后继。线性表的元素之间具有明确的顺序关系，可以通过其位置进行访问和操作。
有序性：线性表中的元素按照一定的顺序排列，每个元素都有确定的位置。
唯一性：线性表中每个元素都有唯一的前驱和后继（除了第一个元素没有前驱，最后一个元素没有后继）。
长度有限：线性表中的元素个数是有限的，可以为空表（长度为零）。
双向链表规则
顺序存储结构：用一组地址连续的存储单元依次存储线性表中的元素，例如数组。顺序存储结构的优点是支持随机访问（通过下标访问），缺点是在插入和删除元素时需要大量的移动操作。
链式存储结构：用一组任意的存储单元存储线性表的元素，并通过指针链接这些存储单元，例如链表。链式存储结构的优点是插入和删除操作较为高效，但访问速度较慢（需要从头遍历）。
2.线性表定义
1,线性表由n(n>=0)个相同类型的数据元素组成的有限序列
有序性
2.当n=0时为空表 记为() Φ
3.线性表的表示
有序性
4.线性表特殊
n>1 只有唯一的开始元素和终端元素
唯一性：
5.标号序
线性表每个元素都有序号( 1 2 3 4 5)逻辑上 程序上从0开始-同时允许存储多个元素
3.线性表实现和运算
思路构造为:单链表
链表基础代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
class ListNode {
int value;
ListNode next;
ListNode(int value) {
this.value = value;
this.next = null;
}
}
class LinkedList {
private ListNode head;
public LinkedList() {
this.head = null;
}
public void insert(int value) {
}
public void delete(int value) {
}
public ListNode find(int value) {
return null;
}
public void printList() {
}
}
|
线性表基本运算方法
初始化 InitList(L)
- 逻辑：创建一个空的线性表
L，将其长度设为 0，或者创建一个数据结构（例如数组或链表）来表示空表。
销毁线性表 DestroyList(L)
- 逻辑：释放线性表
L 所占的内存空间，将表设置为空，防止内存泄漏。
- 迭代器销毁吗?一个个mc
求线性表的长度 GetLength(L)**
- 逻辑：返回线性表
L 的当前长度（即线性表中元素的数量）。
- 还是迭代-只有next有指向就++-直到没指向
求线性表中第 i 个元素 GetElem(L, i, e)**
- 逻辑：检查位置
i 是否有效（在范围内），如果有效，返回位置 i 处的元素 e；否则，返回一个错误或特殊值。
- 从头next尾 -找到i就返回
按值查找 Locate(L, x)
- 逻辑：从线性表
L 的头开始，依次遍历每个元素，判断其值是否等于 x。如果找到，返回元素的位置索引；如果没有找到，返回一个表示未找到的特殊值（例如 -1）。
- 从头next尾
插入元素 InsElem(L, x, i)**
- 逻辑：首先检查插入位置
i 是否有效（例如是否在当前表的长度范围内）。然后从最后一个元素开始向后移动元素，腾出位置 i，最后在位置 i 插入新元素 x，并将线性表的长度加 1。
- 头插 尾插 中间插(上面代码思路-未考虑长度)
删除元素 DelElem(L, i)
- 逻辑：检查要删除的位置
i 是否有效。如果有效，从位置 i+1 开始的每个元素向前移动一位，覆盖位置 i 的元素。最后，减少线性表的长度。
- next遍历索引
输出元素值 DispList(L)
List->线性表
利用线性表List的基本运算，设计一个由线性表A和B中的公共元素产生线性表C的算法
2.2 顺序表
ps:纳闷了一下-以为ai归纳错了-把顺序结构也包含在线性表中了
顺序表的定义
顺序表是在计算机内存中以数组的形式保存的线性表，是指用一组地址连续的存储单元依次存储数据元素的线性结构，使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。
1
2
3
4
5
6
7
| #define MaxSize 100
typedef int ElemType;
typedef struct
{ ElemType data[MaxSize];
int length;
} SqList;
|
定义了数组长度为100的 int类型的数据
1
2
3
4
5
| SqList list;
list.length = 0;
list.data[0] = 10;
list.length++;
|
**ArrayList**：适合大部分顺序表场景，动态数组实现，随机访问高效。
**Vector**：线程安全的动态数组，适合多线程环境，但性能略差。
**LinkedList**：双向链表，适合频繁插入和删除操作，但随机访问效率较低。
**CopyOnWriteArrayList**：线程安全，适合读多写少的场景。
**Arrays.asList()**：固定大小的顺序表，不能动态调整大小。
顺序表的基本运算
1.初始化线性表运算算法
设置初始长度-存储个数
1
2
3
4
5
6
| void InitList(SqList &L)
{
L.length=0;
}
|
2.销毁线性表运算算法
L若在栈则return销毁 –也就是变量的生命周期
3.线性表长度运算算法
1
2
3
4
5
| int GetLength(SqList L)
{
return L.length;
}
|
4.求线性表中第i个元素运算算法
1
2
3
4
5
6
7
8
9
10
11
| 在逻辑序号i无效时返回特殊值0（假），有效时返回1（真），并用引用型形参e返回第i个元素的值。
int GetElem(SqList L,int i,ElemType &e)
{ if (i<1 || i>L.length)
return 0;
else
{ e=L.data[i-1];
return 1;
}
}
|
ElemType &e-取引用类型0类型是T泛型-这里没指定而且
5.按值查找运算算法
1
2
3
4
5
6
7
8
9
10
| 在顺序表L找第一个值为x的元素，找到后返回其逻辑序号，否则返回0（由于线性表的逻辑序号从1开始，这里用0表示没有找到值为x的元素）。
int Locate(SqList L,ElemType x)
{ int i=0;
while (i<L.length && L.data[i]!=x)
i++;
if (i>=L.length) return(0);
else return(i+1);
}
|
逻辑序号就是下标+1
6.插入元素运算法
1
2
3
4
| 将新元素x插入到顺序表L中逻辑序号为i的位置（如果插入成功，元素x成为线性表的第i个元素）。
当i无效时返回0（表示插入失败）。
有效时将L.data[i-1..L.length-1]后移一个位置，在L.data[i-1]处插入x，顺序表长度增1，并返回1（表示插入成功。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| int InsElem(SqList &L,ElemType x,int i)
{ int j;
if (i<1 || i>L.length+1)
return 0;
for (j=L.length;j>i;j--)
{
L.data[j]=L.data[j-1];
}
L.data[i-1]=x;
L.length++;
return 1;
}
|
j-i 是逻辑位置-下标+1所想
1
2
3
| 当i=n+1时（插入尾元素），移动次数为0，呈现最好的情况。
当i=1时（插入第一个元素），移动次数为n，呈现最坏的情况。
|
n是最大下标
平均情况分析
回头看看这个公式的计算方法
1
| 插入算法的主要时间花费在元素移动上，所以算法InsElem()的平均时间复杂度为O(n)。
|
7.删除元素运算算法
1
2
3
4
5
| 删除顺序表L中逻辑序号为i的元素。
在i无效时返回0（表示删除失败）。
有效时将L.data[i..length-1]前移一个位置，顺序表长度减1，并返回1（表示删除成功。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| int DelElem(SqList &L,int i)
{ int j;
if(i<1 || i>L.length)
return 0;
for(j=i,j<L.length;j++)
{
L.data[j-1]=L.data[j];
}
L.length--;
return 1;
}
|
1
2
3
4
5
| 当i=n时（删除尾元素），移动次数为0，呈现最好的情况。
当i=1时（删除第一个元素），移动次数为n-1，呈现最坏的情况。
删除算法的主要时间花费在元素移动上，所以算法DelElem()的平均时间复杂度为O(n)。
|
8.输出元素值运算算法
迭代器写法
1
2
3
4
5
6
7
| void DispList(SqList L)
{ int i;
for (i=0;i<L.length;i++)
printf("%d ",L.data[i]);
printf("\n");
}
|
9.顺序表测试
将顺序表类型声明及其基本运算函数存放在*SqList.cpp文件中
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
void main()
{ int i; ElemType e;
SqList L; //定义一个顺序表L
InitList(L); //初始化顺序表L
InsElem(L,1,1); //插入元素1
InsElem(L,3,2); //插入元素3
InsElem(L,1,3); //插入元素1
InsElem(L,5,4); //插入元素5
InsElem(L,4,5); //插入元素4
InsElem(L,2,6); //插入元素2
printf("线性表:");DispList(L);
printf("长度:%d\n",GetLength(L));
i=3; GetElem(L,i,e);
printf("第%d个元素:%d\n",i,e);
e=1;
printf("元素%d是第%d个元素\n",e,Locate(L,e));
i=4; printf("删除第%d个元素\n",i);
DelElem(L,i);
printf("线性表:");DispList(L);
DestroyList(L);
}
|
1
2
3
4
5
6
7
| #define MaxSize 100
typedef int ElemType;
typedef struct
{ ElemType data[MaxSize];
int length;
} SqList;
|
10.数组值创建顺序表
1
2
3
4
5
6
7
8
9
10
11
| 假设给定一个含有n个元素的数组a，由它来创建顺序表。
void CreateList(SqList &L,ElemType a[],int n)
{ int i,k=0;
for (i=0;i<n;i++)
{ L.data[k]=a[i];
k++;
}
L.length=k;
}
|
2.2.3 顺序表的算法设计示例
ps:上数据结构课的时候观看案例
1.基于顺序表基本操作的算法设计
这类算法设计中包括顺序表元素的查找、插入和删除等
2.3
2.4
2.5
2.基于整体建表的算法设计
1
2
| 这类算法设计中需要根据条件产生新的结果顺序表。
|
2.6
2.7
3.有序顺序表的二路归并算法
1
2
3
4
5
| 有序表是指按元素值递增或者递减排列的线性表。
有序顺序表是有序表的顺序存储结构。也可以采用链式存储结构。
对于有序表可以利用其元素的有序性提高相关算法的效率。
二路归并就是有序表的一种经典算法。
|
2.8
2.9
2.10