线性表是由 n个相同类型的元素组成的有序集合。线性表中元素个数 n 称为线性表的长度，当时为空表。是第一个数据元素，是最后一个数据元素，是的直接前驱，是的直接后驱。以下为我在学习和实战练习过程中所做的笔记，可供参考。
一、线性表的特点
- 表中元素的个数是有限的。
- 表中元素的数据类型都相同，意味着每一个元素占用相同大小的空间。
- 表中元素具有逻辑上的顺序性，在序列中各元素排序有其先后顺序。
二、线性表的顺序表示
逻辑上相邻的两个元素在物理位置上也相邻。
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
| #define MaxSize 50;
typedef int ElemType;
typedef struct {
ElemType data[MaxSize];
int length;
}SqList;
int main()
{
SqList L;
bool ret;
ElemType del;
L.data[0] = 1; L.data[1] = 2; L.data[2] = 3;
L.len = 3;
ret = ListInsert(L, 2, 60);
if(ret)
PrintList(L);
else
printf("插入失败\n");
ret = ListDelete(L, 1, del);
if(ret)
PrintList(L);
else
printf("删除失败\n");
int pos;
pos = LocateElem(L, 60);
printf("%4d\n", pos);
}
void PrintList(SqList &L)
{
for(int i = 0; i < L.length; i ++)
printf("%4d", L.data[i]);
printf("\n");
}
|
优点
- 可以随机存取（根据表头元素地址和元素序号）表中任意一个元素。
- 存储密度高，每个结点只存储数据元素。
缺点
- 插入和删除操作需要移动大量元素。
- 线性表变化较大时，难以确定存储空间的容量。
- 存储分配需要一整段连续的存储空间，不够灵活。
三、插入操作
- 最好情况：在表尾插入元素，不需要移动元素，时间复杂度为。
- 最坏情况：在表头插入元素，所有元素依次后移，时间复杂度为。
- 平均情况：在插入位置概率均等的情况下，平均移动元素的次数为，复杂度为。
1
2
3
4
5
6
7
8
9
10
11
12
| bool ListInsert(SqList &L, int i, ElemType 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;
}
|
四、删除操作
- 最好情况：删除表尾元素，不需要移动元素，时间复杂度为。
- 最坏情况：删除表头元素，之后的所有元素依次前移，时间复杂度为。
- 平均情况：在删除位置概率均等的情况下，平均移动元素的次数为，时间复杂度为。
1
2
3
4
5
6
7
8
9
10
| bool ListDelete(SqList &L, int i, ElemType e)
{
if(i<=1 || i> L.length || L.length == 0)
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;
}
|
五、查找元素
查找成功，返回位置。位置从 1 开始，查找失败，返回 0：
1
2
3
4
5
6
7
| int LocateElem(SqList L, ElemType e)
{
for(int i = 0; i < L.length; i ++)
if(L.data[i] == e)
return i + 1;
return 0;
}
|
六、动态分配
C 语言的初始动态分配语句：
1
| L.data = (ElemType *)malloc(sizeof(ElemType) * InitSize);
|
C++ 的初始动态分配语句：
1
| L.data = new ElemType[InitSize];
|
动态分配数组的类型定义：
1
2
3
4
5
| #define MaxSize 100;
typedef struct {
ElemType *data;
int MaxSize, length;
}SeqList;
|