2021年秋数据结构。共5课时。
课程主页：http://222.195.93.99:82/ds21/#/homepage
认识线性表
Linear List 是有限序列是 n(≥ 0) 个数据元素的有限序列，记作 (a1,a2,…,an)，ai，1 ≤ i ≤ n 是线性表中的数据元素，n 是表长
i 称为 ai 在线性表中的位序；n = 0 是空表。
特点
·同一线性表中的元素具有相同特性
·复杂的数据元素可由若干个数据项组成
·相邻数据元素之间存在序偶关系
线性表的ADT
&L表示已经改变了函数引用的值L。
基本操作
1
2
3
4
5
6
7
8
9
10
11
| Destroy(&L): 将所有痕迹清除
ClearList(&L): 清空现有节点
ListEmpty(L);
ListLength(L);
GetElem(L,i,&e);
LocateElem(L,e,compare()): 利用函数指针实现
PriorElem(L,cur_e,&pre_e);
NextElem(L,cur_e,&next_e);
ListInsert(&L,i,e);
ListDelete(&L,i,&e);
ListTraverse(L,visit): 将所有的数据遍历一次
|
复杂操作：集合的并
1
2
3
4
5
6
7
8
9
| void union(List &La,List Lb){
La_len = ListLength(La);
Lb_len = ListLength(Lb);
for(i = 1;i<Lb_len;i++){
GetElem(Lb,i,e);
if(!LocateElem(La,e,equal))
ListInser
}
}
|
上述算法的时间复杂度依赖 ADT List 定义中基本操作的执行时间 不同的数据结构影响基本操作的实现方式，导致基本操作的执行时间可能相差很大，从而导致上述算法的时间代价相差很大。
