线性表–顺序表
顺序表
定义
用顺序存储的方式实现线性表顺序存储。把逻辑上相邻的元素存储在位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
1
2
3
| a1->a2->a3->a4->a5
在内存中也是
a1-a2-a3-a4-a5
|
每个数据元素都是一样大的，即如果a1存放的位置为LOC(L),a2的位置=LOC(L)+数据元素的大小，a3的位置=LOC(L)+2*数据元素的大小…。
sizeof()
C语言中查看一个数据元素大小，使用sizeof(ElemType)。
例：
1
2
3
4
5
6
7
| sizeof(int)==4B
typedef struct{
int num;
int people
} Customer;
sizeof(Customer)==8B
|
数据表的实现
静态分配
1
2
3
4
5
6
| #define MaxSize 10
typedef struct{
Elemtype data [MaxSize];
int length;
}SqList;
|
这里就相当于一上来就定好了这么一个数据元素，内存为其分配连续的存储空间，大小为10.
初始化
1
2
3
4
5
6
7
8
9
10
11
12
|
void InitList(SqList &L){
for(int i =0;i<MaxSize;i++)
L.data[i]=0;
L.length=0;
}
int main(){
SqList L;
InitList(L);
return 0
}
|
缺点：存储空间不可变！
动态分配
1
2
3
4
5
6
7
| #define InitSize 10
typedef struct{
Elemtype *data;
int MaxSize;
int length;
}SeqList;
|
malloc \free
c语言中用于申请内存空间和释放内存空间的函数
c++中是使用new 和delete
malloc 会返回一个地址
L.data=(ElemType *)malloc(sizeof(ElemType) * InitSize);
比如 如果Elemtype为int，则上行代码为L.data=(int *)malloc(sizeof(int)* InitSize);，然后把返回的这个指针赋值给data。
这里sizeof就是查看这数据元素的长度 然后成上大小，就完成这个内存空间的分配 然后返回地址，然后取出地址的指针赋给data。
具体例子
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
| #include <stdlib.h>
#define InitSize 10
typedef struct{
int *data;
int MaxSize;
int length;
}SeqList;
void InitList(SeqList &L){
L.data=(int *)malloc(sizeof(int)* InitSize);
L.length=0;
L.MaxSize=InitSize;
}
void IncreaseSize(SeqList &L,int len){
int *p=L.data;
L.data=(int *)malloc(sizeof(int)* (L.MaxSize+len));
for(int i=0;i<L.length;i++){
L.data[i]=p[i];
}
L.MaxSize=L.MaxSzie+len;
free(p);
}
int main(){
SeqList L;
InitList(L);
IncreaseSize(L,5);
return 0;
}
|
在增加长度的过程中，会先申请一个新的空间(增加后的大小),然后把之前存放的数据元素放到新空间里，然后释放旧空间。
特点
随机访问，可以在O(1)时间内找到第i个元素。data[i-1]
存储密度搞，每个节点只存储数据元素
拓展容量不方便（即使采用动态存储分配的方式实现，拓展长度的时间复杂度也比较高）
插入、删除操作不方便，需要移动大量元素
顺序表的基本操作
插入
ListInsert(&L ,i,e):插入操作，在表L中的第i个位置上插入指定元素e。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| #define MaxSize 10
typedef struct{
int data[MaxSize];
int length;
}SqList;
bool ListInsert(SqList &L ,int i,int e){
if (i < 1 || i > L.length + 1)
return false;
if (L.length >= MaxSize)
return false;
for(int j=L.length;j>=i;j--)
L.data[j]=L.data[j-1];
L.data[i-1]=e;
L.length++;
return true;
}
int main(){
SqList L;
InitList(L);
ListInsert(L,3,3);
return 0;
}
|
时间复杂度
最好情况：新元素插入到表尾，不需要移动元素
i=n+1，循环0次，最好时间复杂度=O(1)
最坏情况：新元素插入到表头，需要把原有的n个元素向后移动
i=1,循环n次,最坏时间复杂度=O(n)
平均情况：新元素随即插入任何位置，平均概率为p=1/(n+1)
则平均循环次数为n/2,化简后，平均时间复杂度=O(n)
删除
ListDelete(&L ,i,&e):删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #define MaxSize 10
typedef struct{
int data[MaxSize];
int length;
}SqList;
bool ListDelete(SqList &L ,int i,int &e){
if (i < 1 || i > L.length + 1)
return false;
e=L.data[i-1];
for(int j=i;j<L.length;j++)
L.data[j-1]=L.data[j];
L.length--;
return true;
}
int main(){
SqList L;
InitList(L);
int e=-1;
if(ListDelete(L,3,e))
printf("删除成功，删除元素为%d\n",e);
else
printf("删除失败，位序i不合法\n");
return 0;
}
|
时间复杂度
与插入操作的类似且相反
最好情况 删除表尾元素 O(1)
最坏情况 删除表头元素O(n)
平均情况 随机位置删除 O(n/2)即O(n)
注意
位序i与数组小标为i的区别（前者从1开始，后者从0开始）
按位查找
GetElem(L,i):按位查找操作，获取L中第i个位置的元素的值。
静态分配方式
直接选择第i个元素就行了
1
2
3
4
5
6
7
8
| #define MaxSize 10
typedef struct{
Elemtype data [MaxSize];
int length;
}SqList;
ElemType GetElem(SqList L,int i){
return L.data[i-1];
}
|
动态分配方式
也是直接选择第i个位置就行
data是个指针，data[i]返回的即内存中data开始到往后sizeof(ElemType)个字节 的数据。
即如果sizeof(ElemType)=3B，data指向123，data[i]= 123+i*3的内容。
1
2
3
4
5
6
7
8
9
| #define InitSize 10
typedef struct{
Elemtype *data;
int MaxSize;
int length;
}SeqList;
ElemType GetElem(SqList L,int i){
return L.data[i-1];
}
|
时间复杂度
O(1)
按值查找
LocateElem(L,e):按值查找操作，在表中查找给定关键字值的元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
| #define InitSize 10
typedef struct{
Elemtype *data;
int MaxSize;
int length;
}SeqList;
int LocateElem(SqList L,int e){
for(int i=0;i<L.length;i++){
if(L.data[i]==e)
return i+1;
return 0;
}
}
|
时间复杂度
最好情况 要查找的元素在第一个位置 最好时间复杂度=O(1)
最坏情况 要查找的元素在最后一个位置 最坏时间复杂度=O(n)
平均情况 要查找的元素在随机位置 平均时间复杂度=O((n+1)/2)即O(n)
总结
还总结？要啥自行车啊🥡
