线性表 是一种最简单的 线性结构线性结构的 基本特征,
1．集合中必存在唯一的一个,第一元素” ；
2．集合中必存在唯一的一个,最后元素”
3．除最后元素在外，均有 唯一的后继 ；
4．除第一元素之外，均有 唯一的前驱 。
线性结构 是一个数据元素的 有序（次序）集
2.1 线性表的类型定义
2.3 线性表类型的实现
链式映象
2.4 一元多项式的表示
2.2 线性表类型的实现
顺序映象抽象数据类型 线性表 的定义如下：
ADT List {
数据对象,
D＝ { ai | ai ∈ ElemSet,i=1,2,...,n,n≥0 }
{称 n 为线性表的 表长 ;
称 n=0 时的线性表为 空表 。 }
数据关系,
R1＝ { <ai-1,ai >|ai-1,ai∈ D,i=2,...,n }
{设线性表为 (a1,a2,.,,,ai,.,,,an),
称 i 为 ai 在线性表中的 位序 。 }
基本操作：
结构初始化操作结构销毁操作引用型操作加工型操作
} ADT List
InitList( &L )
操作结果：
构造一个空的线性表 L。
初始化操作结构销毁操作
DestroyList( &L )
初始条件：
操作结果：
线性表 L 已存在。
销毁线性表 L。
ListEmpty( L )
ListLength( L )
PriorElem( L,cur_e,&pre_e )
NextElem( L,cur_e,&next_e )
GetElem( L,i,&e )
LocateElem( L,e,compare( ) )
ListTraverse(L,visit( ))
引用型操作,
ListEmpty( L )
初始条件：
操作结果：
线性表 L已存在。
若 L为空表，则返回
TRUE，否则 FALSE。
（线性表判空）
ListLength( L )
初始条件：
操作结果：
线性表 L已存在。
返回 L中元素个数。
（求线性表的长度）
PriorElem( L,cur_e,&pre_e )
初始条件：
操作结果：
线性表 L已存在。
若 cur_e是 L的元素，但不是第一个，则用 pre_e 返回它的前驱，否则操作失败,pre_e
无定义。
（求数据元素的前驱）
NextElem( L,cur_e,&next_e )
初始条件：
操作结果：
线性表 L已存在。
若 cur_e是 L的元素，但不是最后一个，则用 next_e返回它的后继，否则操作失败，
next_e无定义。
（求数据元素的后继）
GetElem( L,i,&e )
初始条件：
操作结果：
线性表 L已存在，
且 1≤i≤LengthList(L)
用 e 返回 L中第 i 个元素的值。
（求线性表中某个数据元素）
LocateElem( L,e,compare( ) )
初始条件：
操作结果：
线性表 L已存在,e为给定值，
compare( )是元素判定函数。
返回 L中第 1个 与 e满足 关系
compare( )的元素的位序。
若这样的元素不存在，
则返回值为 0。
（定位函数）
ListTraverse(L,visit( ))
初始条件：
操作结果：
线性表 L已存在。
Visit() 为某个访问函数。
依次 对 L的每个元素调用函数 visit( )。一旦 visit( )失败，
则操作失败。
（遍历线性表）
加工型操作
ClearList( &L )
PutElem( &L,i,&e )
ListInsert( &L,i,e )
ListDelete(&L,i,&e)
ClearList( &L )
初始条件：
操作结果：
线性表 L已存在。
将 L重置为空表。
（线性表置空）
PutElem( &L,i,&e )
初始条件：
操作结果：
线性表 L已存在，
且 1≤i≤LengthList(L)
L中第 i个元素赋值同 e的值。
（改变数据元素的值）
ListInsert( &L,i,e )
初始条件：
操作结果：
线性表 L已存在,
且 1≤i≤LengthList(L)+1
在 L的第 i个元素之前 插入新的元素 e,L的长度增 1。
（插入数据元素）
ListDelete(&L,i,&e)
初始条件：
操作结果：
线性表 L已存在且非空，
1≤i≤LengthList(L)
删除 L的第 i个元素，并用
e返回其值,L的长度减 1。
（删除数据元素）
利用上述定义的 线性表可以实现其它更复杂的操作例 2-2
例 2-3
例 2-1
假设,有两个 集合 A 和 B 分别用两个 线性表 LA 和 LB 表示，即：线性表中的数据元素即为集合中的成员。
现要求一个新的集合 A＝ A∪ B。
例 2-1
要求对线性表作如下操作：
扩大线性表 LA，将 存在于线性表
LB 中 而 不存在于线性表 LA 中 的数据元素 插入到线性表 LA中 去。
上述问题可演绎为：
1,从线性表 LB中依次察看每个数据元素 ;
2,依值在线性表 LA中进行查访 ;
3,若不存在，则插入之。
GetElem(LB,i)→ e
LocateElem(LA,e,equal( ))
ListInsert(LA,n+1,e)
操作步骤：
GetElem(Lb,i,e); // 取 Lb中第 i个数据元素赋给 e
if (!LocateElem(La,e,equal( )) )
ListInsert(La,++La_len,e);
// La中不存在和 e 相同的数据元素，则插入之
void union(List &La,List Lb) {
La_len = ListLength(La); // 求线性表的长度
Lb_len = ListLength(Lb);
for (i = 1; i <= Lb_len; i++) {
}
} // union
已知 一个 非纯集合 B，试 构造 一个纯集合 A,使 A中只包含 B 中所有值各不相 同的数据元素 。
仍选用 线性表 表示集合例 2-2
集合 B 集合 A
从集合 B 取出物件放入集合 A
要求集合 A中 同样物件不能有两件以上因此,算法的策略应该和例 2-1相同
void union(List &La,List Lb) {
La_len=ListLength(La); Lb_len=ListLength(Lb);
} // union
GetElem(Lb,i,e); // 取 Lb中第 i 个数据元素赋给 e
if (!LocateElem(La,e,equal( )) )
ListInsert(La,++La_len,e);
// La中不存在和 e 相同的数据元素，则插入之
for (i = 1; i <= Lb_len; i++) {
}
InitList(La); // 构造 (空的 )线性表 LA
若线性表中的数据元素相互之间可以 比较,
并且数据元素在线性表中 依值非递减或非递增有序 排列，即
ai≥a i-1 或 ai≤a i-1(i = 2,3,…,n)，则称该线性表为 有序表 (Ordered List)。
试改变结构，以 有序表 表示集合。
例如,
（ 2,3,3,5,6,6,6,8,12）
对集合 B 而言，
值相同的数据元素必定相邻对集合 A 而言，
数据元素依值从小至大的顺序插入因此,数据结构改变了，
解决问题的策略也相应要改变。
void purge(List &La,List Lb) {
InitList(LA); La_len = ListLength(La);
Lb_len =ListLength(Lb); // 求线性表的长度
for (i = 1; i <= Lb_len; i++) {
}
} // purge
GetElem(Lb,i,e); // 取 Lb中第 i个数据元素赋给 e
if (ListEmpty(La) || !equal (en,e)) {
ListInsert(La,++La_len,e);
en = e;
} // La中不存在和 e 相同的数据元素，则插入之则归并两个“其数据元素按值非递减有序排列”的有序表 LA 和 LB，求得有序表
LC 也具有同样特性。
设 La = (a1,…,ai,…,a n),Lb = (b1,…,bj,…,b m)
Lc = (c1,…,ck,…,c m+n)
且 已由 (a1,…,a i-1)和 (b1,…,b j-1)归并得 (c1,…,c k-1)
jij
jii
k bab
baa
c
例 2-3
k = 1,2,…,m+n
1．初始化 LC 为空表；
基本操作：
2．分别从 LA和 LB中取得当前元素 ai 和 bj；
3．若 ai≤ bj，则将 ai 插入到 LC 中，否则将
bj 插入到 LC 中；
4．重复 2 和 3 两步，直至 LA 或 LB 中元素被取完为止；
5．将 LA 表或 LB 表中剩余元素复制插入到
LC 表中。
// La 和 Lb 均非空,i = j = 1,k = 0
GetElem(La,i,ai);
GetElem(Lb,j,bj);
if (ai <= bj) { // 将 ai 插入到 Lc 中
ListInsert(Lc,++k,ai); ++i; }
else { // 将 bj 插入到 Lc 中
ListInsert(Lc,++k,bj); ++j; }
void MergeList(List La,List Lb,List &Lc) {
// 本算法将非递减的有序表 La 和 Lb 归并为 Lc
} // merge_list
while ((i <= La_len) && (j <= Lb_len))
{ // La 和 Lb 均不空 }
while (i<=La_len) // 若 La 不空
while (j<=Lb_len) // 若 Lb 不空
InitList(Lc); // 构造空的线性表 Lc
i = j = 1; k = 0;
La_len = ListLength(La);
Lb_len = ListLength(Lb);
while (i <= La_len) { // 当 La不空时
GetElem(La,i++,ai);
ListInsert(Lc,++k,ai);
} // 插入 La 表中剩余元素
while (j <= Lb_len) { // 当 Lb不空时
GetElem(Lb,j++,bj);
ListInsert(Lc,++k,bj);
} // 插入 Lb 表中剩余元素最简单的一种顺序映象方法是：
令 y 的存储位置和 x 的存储位置相邻 。
顺序映象
—— 以 x 的存储位置和 y 的存储位置之间某种关系表示逻辑关系 <x,y>
用一组 地址连续 的存储单元依次存放 线性表中的数据元素
a1 a2 … ai-1 ai … an
线性表的 起始地址,
称作线性表的 基地址以,存储位置相邻,表示有序对 <ai-1,ai>
即,LOC(ai) = LOC(ai-1) + C
一个数据元素所占存储量 ↑
所有数据元素的存储位置均取决于第一个数据元素的存储位置
LOC(ai) = LOC(a1) + (i-1)× C
↑ 基地址顺序映像的 C 语言描述
typedef struct {
} SqList; // 俗称 顺序表
#define LIST_INIT_SIZE 80
// 线性表存储空间的初始分配量
#define LISTINCREMENT 10
// 线性表存储空间的分配增量
ElemType *elem; // 存储空间基址
int length; // 当前长度
int listsize; // 当前分配的存储容量
// (以 sizeof(ElemType)为单位 )
线性表的基本操作在顺序表中的实现
InitList(&L) // 结构初始化
LocateElem(L,e,compare()) // 查找
ListInsert(&L,i,e) // 插入元素
ListDelete(&L,i) // 删除元素
Status InitList_Sq( SqList& L,int maxsize ) {
// 构造一个最大容量为 maxsize 的顺序表
} // InitList_Sq 算法 时间复杂度,O(1)
L.elem = new ElemType[maxsize];
// 为顺序表分配大小为 maxsize 的数组空间
if (!L.elem) exit(OVERFLOW);
L.length = 0;
L.listsize = maxsize;
return OK;
例如：顺序表
23 75 41 38 54 62 17
L.elem
L.length = 7
L.listsize
e = 38
p p p p p
i 12348
50
可见，基本操作是，
将顺序表中的元素逐个和给定值 e
相比较。
int LocateElem_Sq(SqList L,ElemType e,
Status (*compare)(ElemType,ElemType)) {
// 在顺序表中查询第一个满足判定条件的数据元素，
// 若存在，则返回它的位序，否则返回 0
} // LocateElem_Sq O( ListLength(L) )
算法的 时间复杂度 为：
i = 1; // i 的初值为第 1 元素的位序
p = L.elem; // p 的初值为第 1 元素的存储位置
while (i <= L.length &&
!(*compare)(*p++,e)) ++i;
if (i <= L.length) return i;
else return 0;
线性表 操作
ListInsert(&L,i,e)的实现,
首先分析,
插入元素时，
线性表的 逻辑结构 发生什么变化？
(a1,…,ai-1,ai,…,a n) 改变为
a1 a2 … ai-1 ai … an
a1 a2 … ai-1 …aie an
<ai-1,ai> <ai-1,e>,<e,ai>
表的长度增加
(a1,…,ai-1,e,ai,…,a n)
Status ListInsert_Sq(SqList &L,int i,ElemType e) {
// 在顺序表 L的第 i 个元素之前插入新的元素 e,
// i 的合法范围为 1≤i≤L.length+1
} // ListInsert_Sq
算法时间复杂度 为,
O( ListLength(L) )
q = &(L.elem[i-1]); // q 指示插入位置
for (p = &(L.elem[L.length-1]); p >= q; --p)
*(p+1) = *p; // 插入位置及之后的 元素右移
*q = e; // 插入 e
++L.length; // 表长增 1
return OK;
……
元素右移
if (L.length >= L.listsize) {
// 当前存储空间已满，增加分配
newbase = (ElemType *)realloc(L.elem,
(L.listsize+LISTINCREMENT)*sizeof (ElemType));
if (!newbase) exit(OVERFLOW);
// 存储分配失败
L.elem = newbase; // 新基址
L.listsize += LISTINCREMENT; // 增加存储容量
}
if (i < 1 || i > L.length+1) return ERROR;
// 插入位置不合法考虑移动元素的平均情况,
假设在第 i 个元素之前插入的概率为,
则在长度为 n 的线性表中 插入一个元素所需移动元素次数的期望值 为：
ip
1
1
)1(n
i
iis inpE
1
1
)1(11
n
i
is innE 2
n
若 假定 在线性表中任何一个位置上进行 插入的概率 都是 相等 的，则 移动元素的期望值 为,
21 18 30 75 42 56 87
21 18 30 75
例如,ListInsert_Sq(L,5,66)
L.length-10
pppq
87564266
q = &(L.elem[i-1]); // q 指示插入位置
for (p = &(L.elem[L.length-1]); p >= q; --p)
*(p+1) = *p;
p
线性表操作
ListDelete(&L,i,&e)的实现,
首先分析：
删除元素时，
线性表的逻辑结构发生什么变化？
(a1,…,ai-1,ai,ai+1,…,a n) 改变为
ai+1 … an
<ai-1,ai>,<ai,ai+1> <ai-1,ai+1>
表的长度减少
a1 a2 … ai-1 ai ai+1 … an
a1 a2 … ai-1
(a1,…,ai-1,ai+1,…,a n)
Status ListDelete_Sq
(SqList &L,int i,ElemType &e) {
} // ListDelete_Sq
for (++p; p <= q; ++p) *(p-1) = *p;
// 被删除元素之后的元素左移
--L.length; // 表长减 1
return OK; 算法时间复杂度 为,
O( ListLength(L))
p = &(L.elem[i-1]); // p 为被删除元素的位置
e = *p; // 被删除元素的值赋给 e
q = L.elem+L.length-1; // 表尾元素的位置
if ((i < 1) || (i > L.length)) return ERROR;
// 删除位置不合法元素左移考虑移动元素的平均情况,
假设删除第 i 个元素的概率为,
则在长度为 n 的线性表中 删除一个元素 所需移动元素次数的期望值 为：
iq
n
i
idl inqE
1
)(
n
i
dl innE
1
)(12 n
若假定在线性表中任何一个位置上进行删除的 概率 都是 相等 的，则 移动元素的期望值 为,
21 18 30 75 42 56 87
21 18 30 75
L.length-10
ppp q
8756
p = &(L.elem[i-1]);
q = L.elem+L.length-1;
for (++p; p <= q; ++p) *(p-1) = *p;
例如,ListDelete_Sq(L,5,e)
p
顺序表的特点,
用一组 地址连续 的存储单元 依次存放 数据元素
3、所占存储空间在初始化时 一次性 分配，
难以任意扩大线性表的容量；
1、可以进行 随机存取 ；
2、插入或删除元素需要 移动 其它元素；
一、单链表二、结点和单链表的 C 语言描述三、线性表的操作在单链表中的实现四、一个带头结点的单链表类型五、其它形式的链表六、有序表类型用一组 地址任意 的存储单元 存放 线性表中的数据元素。
一、单链表以 元素 (数据元素的映象 )
+ 指针 (指示后继元素存储位置 )
= 结点
(表示数据元素 或 数据元素的映象 )
以,结点的序列,表示线性表
称作 链表以线性表中第一个数据元素 的存储地址 作为线性表的地址，称作线性表的 头指针
1a
头结点
a1 a2 …,.,a n ^
头指针头指针有时为了操作方便，在第一个结点之前虚加一个“头结点”，以 指向头结点的指针 为链表的头指针空指针线性表为空表时，
头结点的指针域为空
Typedef struct LNode {
ElemType data; // 数据域
struct Lnode *next; // 指针域
} LNode,*LinkList;
二、结点和单链表的 C 语言描述
LinkList L； // L 为单链表的头指针三、单链表操作的实现
GetElem(L,i,e) // 取第 i个数据元素
ListInsert(&L,i,e) // 插入 数据元素
ListInsert(&L,i,e) // 删除 数据元素
ClearList(&L) // 重置线性表为空表
CreateList(&L,n)
// 生成含 n 个数据元素的链表
L
线性表的操作
GetElem(L,i,&e)
在单链表中的实现,
21 18 30 75 42 56 ∧
p p p
j 123
假设,i = 3
因此，查找第 i 个数据元素的基本操作为,移动指针，比较 j 和 i
单链表是一种顺序存取的结构，为找第 i 个数据元素，必须先找到第 i-1 个数据元素。
令指针 p 始终 指向 线性表中第 j 个数据元素
Status GetElem_L(LinkList L,int i,ElemType &e) {
// L是带头结点的链表的头指针，以 e 返回第 i 个元素
} // GetElem_L
算法 时间复杂度 为,
O(ListLength(L))
p = L->next; j = 1; // p指向第一个结点,j为计数器
while (p && j<i) { p = p->next; ++j; }
// 顺指针向后查找，直到 p 指向第 i 个元素
// 或 p 为空
if ( !p || j>i )
return ERROR; // 第 i 个元素不存在
e = p->data; // 取得第 i 个元素
return OK;
ai-1
线性表的操作 ListInsert(&L,i,e)
在单链表中的实现,
有序对 <ai-1,ai>
改变为 <ai-1,e> 和 <e,ai>
e
ai
因此，在单链表中第 i 个结点之前进行插入的基本操作为,
找到线性表中第 i-1个结点，然后修改其指向后继的指针。
可见，在链表中插入结点只需要修改指针。但同时，若要在第 i 个结点之前插入元素，修改的是第 i-1 个结点的指针。
Status ListInsert_L(LinkList L,int i,ElemType e) {
// L 为带头结点的单链表的头指针，本算法
// 在链表中第 i 个结点之前插入新的元素 e
} // LinstInsert_L
算法的 时间复杂度 为,O(ListLength(L))
……
p = L; j = 0;
while (p && j < i-1)
{ p = p->next; ++j; } // 寻找第 i-1 个结点
if (!p || j > i-1)
return ERROR; // i 大于表长或者小于 1
s = new LNode;
// 生成新结点
s->data = e;
s->next = p->next; p->next = s; // 插入
return OK;
e
ai-1 ai
s
p
线性表 的操作 ListDelete (&L,i,&e)
在链表中的实现,
有序对 <ai-1,ai> 和 <ai,ai+1>
改变为 <ai-1,ai+1>
ai-1 ai ai+1
在单链表中 删除第 i 个结点 的 基本操作 为,找到线性表中第 i-1个结点，修改其指向后继的指针。
ai-1 ai ai+1
q = p->next; p->next = q->next;
e = q->data; delete(q);
p q
Status ListDelete_L(LinkList L,int i,ElemType &e) {
// 删除以 L 为头指针 (带头结点 )的单链表中第 i 个结点
} // ListDelete_L
算法的 时间复杂度 为,O(ListLength(L))
p = L; j = 0;
while (p->next && j < i-1) { p = p->next; ++j; }
// 寻找第 i 个结点，并令 p 指向其前趋
if (!(p->next) || j > i-1)
return ERROR; // 删除位置不合理
q = p->next; p->next = q->next; // 删除并释放结点
e = q->data; delete(q);
return OK;
操作 ClearList(&L) 在链表中的实现,
void ClearList(&L) {
// 将单链表重新置为一个空表
while (L->next) {
p=L->next; L->next=p->next;
}
} // ClearList
delete(p);
算法 时间复杂度,O(ListLength(L))
如何从线性表得到单链表？
链表是一个动态的结构，它不需要予分配空间，因此 生成链表的过程是一个结点,逐个插入,的过程。
例如：逆位序输入 n 个数据元素的值，
建立带头结点的单链表。
操作步骤：
一、建立一个“空表”；
二、输入数据元素 an，
建立结点并插入；
三、输入数据元素 an-1，
建立结点并插入；
an
an
an-1
四、依次类推，直至输入 a1为止。
void CreateList_L(LinkList &L,int n) {
// 逆序输入 n 个数据元素，建立带头结点的单链表
} // CreateList_L
算法的 时间复杂度 为,O(Listlength(L))
L = new LNode;
L->next = NULL; // 先建立一个带头结点的单链表
for (i = n; i > 0; --i) {
p = new LNode;
scanf(&p->data); // 输入元素值
p->next = L->next; L->next = p; // 插入
}
回顾 2.1 节中三个例子的算法，
看一下当线性表分别以顺序存储结构和链表存储结构实现时，
它们的时间复杂度为多少？
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( ))
ListInsert(La,++La_len,e);
}//for
} // union
控制结构：
基本操作：
for 循环
GetElem,LocateElem 和 ListInsert
当以 顺序映像 实现抽象数据类型线性表时为,
O( ListLength(La)× ListLength(Lb) )当以 链式映像 实现抽象数据类型线性表时为,O( ListLength(La)× ListLength(Lb) )
例 2-1
算法时间复杂度
void purge(List &La,List Lb) {
InitList(LA);
La_len = ListLength(La); Lb_len =ListLength(Lb);
for (i = 1; i <= Lb_len; i++) {
GetElem(Lb,i,e);
if (ListEmpty(La) || !equal (en,e))
{ ListInsert(La,++La_len,e); en = e; }
}//for
} // purge
控制结构：
基本操作：
for 循环
GetElem 和 ListInsert
当以 顺序映像 实现抽象数据类型线性表时为,
O( ListLength(Lb) )
当以 链式映像 实现抽象数据类型线性表时为,
O( ListLength2(Lb) )
例 2-2
算法时间复杂度
void MergeList(List La,List Lb,List &Lc) {
InitList(Lc); i = j = 1; k = 0;
La_len = ListLength(La); Lb_len = ListLength(Lb);
while ((i <= La_len) && (j <= Lb_len)) {
GetElem(La,i,ai); GetElem(Lb,j,bj);
if (ai <= bj) {
ListInsert(Lc,++k,ai); ++i; }
else { ListInsert(Lc,++k,bj); ++j; }
} … …
控制结构：
基本操作：
三个并列的 while循环
GetElem,ListInsert
当以 顺序映像 实现抽象数据类型线性表时为,
O( ListLength(La)+ListLength(Lb) )当以 链式映像 实现抽象数据类型线性表时为,O( ListLength 2(La)+ListLength 2(Lb) )
例 2-3
算法时间复杂度用上述定义的单链表实现线性表的操作时，
存在的 问题,
改进链表的设置：
1．单链表的表长是一个隐含的值；
1．增加“表长”、“表尾指针” 和,当前位置的指针” 三个数据域；
2．在单链表的最后一个元素之后插入元素时，
需遍历整个链表；
3．在链表中，元素的“位序”概念淡化，结点的
“位置”概念加强。
2．将基本操作中的,位序 i,改变为,指针 p,。
四、一个带头结点的线性链表类型
typedef struct LNode { // 结点类型
ElemType data;
struct LNode *next;
} *Link,*Position;
Status MakeNode( Link &p,ElemType e );
// 分配由 p 指向的值为 e的结点，并返回 OK；
// 若分配失败，则返回 ERROR
void FreeNode( Link &p );
// 释放 p 所指结点
typedef struct { // 链表类型
Link head,tail; // 分别指向头结点和
// 最后一个结点的指针
int len; // 指示链表长度
Link current; // 指向当前被访问的结点
//的指针，初始位置指向头结点
} LinkList;
链表的基本操作,
{结构初始化和销毁结构 }
Status InitList( LinkList &L );
// 构造一个空的线性链表 L，其头指针、
// 尾指针和当前指针均指向头结点，
// 表长为零。
Status DestroyList( LinkList &L );
// 销毁线性链表 L,L不再存在。
O(1)
O(n)
{引用型操作 }
Status ListEmpty ( LinkList L ); //判表空
int ListLength( LinkList L ); // 求表长
Status Prior( LinkList L );
// 改变当前指针指向其前驱
Status Next ( LinkList L );
// 改变当前指针指向其后继
ElemType GetCurElem ( LinkList L );
// 返回当前指针所指数据元素
O(1)
O(1)
O(n)
O(1)
O(1)
Status LocatePos( LinkList L,int i );
// 改变当前指针指向第 i个结点
Status LocateElem (LinkList L,ElemType e,
Status (*compare)(ElemType,ElemType));
// 若存在与 e 满足函数 compare( )判定关系的元
// 素，则移动当前指针指向第 1个满足条件的
// 元素的前驱，并返回 OK; 否则返回 ERROR
Status ListTraverse(LinkList L,Status(*visit)() );
// 依次对 L的每个元素调用函数 visit()
O(n)
O(n)
O(n)
{加工型操作 }
Status ClearList ( LinkList &L );
// 重置 L 为空表
Status SetCurElem(LinkList &L,ElemType e );
// 更新当前指针所指数据元素
Status Append ( LinkList &L,Link s );
// 在表尾结点之后链接一串结点
Status InsAfter ( LinkList &L,Elemtype e );
// 将元素 e 插入在当前指针之后
Status DelAfter ( LinkList &L,ElemType& e );
// 删除当前指针之后的结点
O(1)
O(n)
O(s)
O(1)
O(1)
Status InsAfter( LinkList& L,ElemType e ) {
// 若当前指针在链表中,则将数据元素 e插入在线性链
// 表 L中当前指针所指结点之后,并改变当前指针指向新
//插入结点，返回 OK; 否则返 回 ERROR。
} // InsAfter
if ( ! L.current ) return ERROR;
if (! MakeNode( s,e) ) return ERROR;
s->next = L.current->next;
L.current->next = s;
if (L.tail = L.current) L.tail = s;
L.current = s; return OK;
Status DelAfter( LinkList& L,ElemType& e ) {
// 若当前指针及其后继在链表中，则删除线性链表 L中当前
// 指针所指结点之后的结点，并返回 OK; 否则返回 ERROR。
} //DelAfter
if ( !(L.current && L.current->next ) )
return ERROR;
q = L.current->next;
L.current->next = q->next;
if (L.tail = q) L.tail = L.current;
e=q->data; FreeNode(q);
return OK;
Status ListInsert_L(LinkList L,int i,ElemType e) {
// 在带头结点的单链线性表 L 的第 i 个元素之前插入元素 e
} // ListInsert_L
利用上述定义的线性链表如何完成线性表的其它操作？
if (!LocatePos (L,i-1)) return ERROR;
// i 值不合法，第 i-1 个结点不存在
if (InsAfter (L,e)) return OK; // 完成 插入
else return ERROR;
例一
Status MergeList_L(LinkList &Lc,LinkList &La,
LinkList &Lb,int (*compare)
(ElemType,ElemType))) {
// 归并有序表 La 和 Lb,生成新的有序表 Lc,
// 并在归并之后销毁 La 和 Lb,
// compare 为指定的元素大小判定函数
……
} // MergeList_L
例二
if ( !InitList(Lc)) return ERROR; // 存储空间分配失败
while (!( a=MAXC && b=MAXC)) { // La 或 Lb 非空
}
… …
LocatePos (La,0); LocatePos (Lb,0); // 当前指针指向头结点
if ( DelAfter( La,e)) a = e; // 取得 La 表中第一个元素 a
else a = MAXC; // MAXC为常量最大值
if ( DelFirst( Lb,e)) b = e; // 取得 Lb 表中第一个元素 b
else b = MAXC; // a 和 b 为两表中当前比较元素
DestroyList(La); DestroyList(Lb); // 销毁链表 La 和 Lb
return OK;
if ((*compare)(a,b) <=0) { // a≤b
InsAfter(Lc,a);
if ( DelAfter( La,e1) ) a = e1;
else a = MAXC;
}
else { // a＞ b
InsAfter(Lc,b);
if ( DelAfter( Lb,e1) ) b = e1;
else b = MAXC;
}
1,双向链表五、其它形式的链表
typedef struct DuLNode {
ElemType data; // 数据域
struct DuLNode *prior;
// 指向前驱的指针域
struct DuLNode *next;
// 指向后继的指针域
} DuLNode,*DuLinkList;
最后一个结点的指针域的指针又指回第一个结点的链表
a1 a2 …,.,a n
2,循环链表和单链表的差别仅在于,判别 链表中最后一个结点的 条件 不再是“后继是否为空”，而是,后继是否为头结点” 。
双向循环链表空表非空表
a1 a2 …,.,a n
双向链表的操作特点：
,查询” 和单链表相同
,插入” 和“删除”时需要同时修改两个方向上的指针。
ai-1 ai
e
s->next = p->next; p->next = s;
s->next->prior = s; s->prior = p;
p
s
插入
ai-1
删除
ai ai+1
p->next = p->next->next;
p->next->prior = p;
p
六、有序表类型
ADT Ordered_List {
数据对象,S = { xi|xi? OrderedSet,
i=1,2,…,n,n ≥0 }
集合中任意两个元素之间均可以进行比较数据关系,R = {<xi-1,xi> | xi-1,xi? S,
xi-1≤ xi,i=2,3,…,n }
回顾例 2-2的两个算法基本操作：
… …
… …
LocateElem( L,e,&q,
int(*compare)(ElemType,ElemType) )
初始条件,有序表 L已存在。
操作结果,若有序表 L中存在元素 e，则 q
指示 L中 第一个值为 e 的元素 的位置,并返回函数值 TRUE；否则 q 指示 第一个大于 e 的元素的前驱 的位置,并返回函数值
FALSE。
Compare是一个有序判定函数
( 12,23,34,45,56,67,78,89,98,45 )
例如,
若 e = 45,
则 q 指向若 e = 88,
则 q 指向表示值为 88 的元素应插入在该指针所指结点之后。
void union(List &La,List Lb) {// Lb 为线性表
InitList(La); // 构造 (空的 )线性表 LA
La_len=ListLength(La); Lb_len=ListLength(Lb);
for (i = 1; i <= Lb_len; i++) {
GetElem(Lb,i,e); // 取 Lb中第 i 个数据元素赋给 e
if (!LocateElem(La,e,equal( )) )
ListInsert(La,++La_len,e);
// La中不存在和 e 相同的数据元素，则插入之
}
} // union 算法时间复杂度,O(n2)
void purge(List &La,List Lb) { // Lb为有序表
InitList(LA); La_len = ListLength(La);
Lb_len =ListLength(Lb); // 求线性表的长度
for (i = 1; i <= Lb_len; i++) {
}
} // purge
GetElem(Lb,i,e); // 取 Lb中第 i个数据元素赋给 e
if (ListEmpty(La) || !equal (en,e)) {
ListInsert(La,++La_len,e);
en = e;
} // La中不存在和 e 相同的数据元素，则插入之算法时间复杂度,O(n)
n
nn xpxpxppxp,..)(
2
210
在计算机中，可以用一个线性表来表示,
P = (p0,p1,…,pn)
一元多项式但是对于形如
S(x) = 1 + 3x10000 – 2x20000
的多项式，上述表示方法是否合适？
一般情况下的 一元稀疏多项式 可写成
Pn(x) = p1xe1 + p2xe2 + ┄ + pmxem
其中,pi 是指数为 ei 的项的非零系数,
0≤ e1 < e2 < ┄ < em = n
可以下列线性表表示：
（（ p1,e1）,(p2,e2),┄,(pm,em) ）
P999(x) = 7x3 - 2x12 - 8x999
例如,
可用线性表
( (7,3),(-2,12),(-8,999) )
表示
ADT Polynomial {
数据对象,
数据关系,
抽象数据类型一元多项式的定义如下：
D＝ { ai | ai ∈ TermSet,i=1,2,...,m,m≥0
TermSet 中的 每个元素包含一个表示系数的实数和表示指数的整数 }
R1＝ { <ai-1,ai >|ai-1,ai∈ D,i=2,...,n
且 ai-1中的指数值 ＜ ai中的指数值 }
CreatPolyn ( &P,m )
DestroyPolyn ( &P )
PrintPolyn ( &P )
基本操作,
操作结果,输入 m 项的系数和指数，
建立一元多项式 P。
初始条件,一元多项式 P 已存在 。
操作结果,销毁一元多项式 P。
初始条件,一元多项式 P 已存在 。
操作结果,打印输出一元多项式 P。
PolynLength( P )
AddPolyn ( &Pa,&Pb )
SubtractPolyn ( &Pa,&Pb )
… …
} ADT Polynomial
初始条件,一元多项式 P 已存在 。
操作结果,返回一元多项式 P 中的项数 。
初始条件,一元多项式 Pa 和 Pb 已存在 。
操作结果,完成多项式相加运算，即：
Pa = Pa＋ Pb，并销毁一元多项式 Pb。
一元多项式的实现：
typedef struct { // 项 的表示
float coef; // 系数
int expn; // 指数
} term,ElemType;
typedef OrderedLinkList polynomial;
// 用带表头结点的有序链表表示多项式结点的数据元素类型定义为,
Status CreatPolyn ( polynomail &P,int m ) {
// 输入 m项的系数和指数，建立表示一元多项式的有序链表 P
} // CreatPolyn
InitList (P); e.coef = 0.0; e.expn = -1;
SetCurElem (h,e); // 设置头结点的数据元素
for ( i=1; i<=m; ++i ) { // 依次输入 m 个非零项
}
return OK;
scanf (e.coef,e.expn);
if (!LocateElem ( P,e,(*cmp)()) )
if ( !InsAfter ( P,e ) ) return ERROR;
注意,1.输入次序不限 ;
2.指数相同的项只能输入一次
Status AddPolyn ( polynomial &Pc,
polynomial &Pa,polynomial &Pb) {
// 利用两个多项式的结点构成“和多项式” Pc = Pa＋
Pb
… …
if (DelAfter(Pa,e1)) a=e1.expn else a=MAXE;
if (DelAfter(Pb,e2)) b=e2.expn else b=MAXE;
while (!(a=MAXE && b=MAXE)) {
… …
}
… …
} // AddPolyn
switch (*cmp(e1,e2)) {
case -1,{ // 多项式 PA中当前结点的指数值小
… … break ; }
case 0,{ // 两者的指数值相等
e1.coef= a.coef + b.coef ;
if ( a.coef != 0.0 ) InsAfter(Pc,e1);
… … break ;
}
case 1,{ //多项式 PB中当前结点的指数值小
… … break ; }
}
本章小结
1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系,在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构 。 用前者表示的线性表简称为顺序表,
用后者表示的线性表简称为链表 。
2.熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现。
3.能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。
1．集合中必存在唯一的一个,第一元素” ；
2．集合中必存在唯一的一个,最后元素”
3．除最后元素在外，均有 唯一的后继 ；
4．除第一元素之外，均有 唯一的前驱 。
线性结构 是一个数据元素的 有序（次序）集
2.1 线性表的类型定义
2.3 线性表类型的实现
链式映象
2.4 一元多项式的表示
2.2 线性表类型的实现
顺序映象抽象数据类型 线性表 的定义如下：
ADT List {
数据对象,
D＝ { ai | ai ∈ ElemSet,i=1,2,...,n,n≥0 }
{称 n 为线性表的 表长 ;
称 n=0 时的线性表为 空表 。 }
数据关系,
R1＝ { <ai-1,ai >|ai-1,ai∈ D,i=2,...,n }
{设线性表为 (a1,a2,.,,,ai,.,,,an),
称 i 为 ai 在线性表中的 位序 。 }
基本操作：
结构初始化操作结构销毁操作引用型操作加工型操作
} ADT List
InitList( &L )
操作结果：
构造一个空的线性表 L。
初始化操作结构销毁操作
DestroyList( &L )
初始条件：
操作结果：
线性表 L 已存在。
销毁线性表 L。
ListEmpty( L )
ListLength( L )
PriorElem( L,cur_e,&pre_e )
NextElem( L,cur_e,&next_e )
GetElem( L,i,&e )
LocateElem( L,e,compare( ) )
ListTraverse(L,visit( ))
引用型操作,
ListEmpty( L )
初始条件：
操作结果：
线性表 L已存在。
若 L为空表，则返回
TRUE，否则 FALSE。
（线性表判空）
ListLength( L )
初始条件：
操作结果：
线性表 L已存在。
返回 L中元素个数。
（求线性表的长度）
PriorElem( L,cur_e,&pre_e )
初始条件：
操作结果：
线性表 L已存在。
若 cur_e是 L的元素，但不是第一个，则用 pre_e 返回它的前驱，否则操作失败,pre_e
无定义。
（求数据元素的前驱）
NextElem( L,cur_e,&next_e )
初始条件：
操作结果：
线性表 L已存在。
若 cur_e是 L的元素，但不是最后一个，则用 next_e返回它的后继，否则操作失败，
next_e无定义。
（求数据元素的后继）
GetElem( L,i,&e )
初始条件：
操作结果：
线性表 L已存在，
且 1≤i≤LengthList(L)
用 e 返回 L中第 i 个元素的值。
（求线性表中某个数据元素）
LocateElem( L,e,compare( ) )
初始条件：
操作结果：
线性表 L已存在,e为给定值，
compare( )是元素判定函数。
返回 L中第 1个 与 e满足 关系
compare( )的元素的位序。
若这样的元素不存在，
则返回值为 0。
（定位函数）
ListTraverse(L,visit( ))
初始条件：
操作结果：
线性表 L已存在。
Visit() 为某个访问函数。
依次 对 L的每个元素调用函数 visit( )。一旦 visit( )失败，
则操作失败。
（遍历线性表）
加工型操作
ClearList( &L )
PutElem( &L,i,&e )
ListInsert( &L,i,e )
ListDelete(&L,i,&e)
ClearList( &L )
初始条件：
操作结果：
线性表 L已存在。
将 L重置为空表。
（线性表置空）
PutElem( &L,i,&e )
初始条件：
操作结果：
线性表 L已存在，
且 1≤i≤LengthList(L)
L中第 i个元素赋值同 e的值。
（改变数据元素的值）
ListInsert( &L,i,e )
初始条件：
操作结果：
线性表 L已存在,
且 1≤i≤LengthList(L)+1
在 L的第 i个元素之前 插入新的元素 e,L的长度增 1。
（插入数据元素）
ListDelete(&L,i,&e)
初始条件：
操作结果：
线性表 L已存在且非空，
1≤i≤LengthList(L)
删除 L的第 i个元素，并用
e返回其值,L的长度减 1。
（删除数据元素）
利用上述定义的 线性表可以实现其它更复杂的操作例 2-2
例 2-3
例 2-1
假设,有两个 集合 A 和 B 分别用两个 线性表 LA 和 LB 表示，即：线性表中的数据元素即为集合中的成员。
现要求一个新的集合 A＝ A∪ B。
例 2-1
要求对线性表作如下操作：
扩大线性表 LA，将 存在于线性表
LB 中 而 不存在于线性表 LA 中 的数据元素 插入到线性表 LA中 去。
上述问题可演绎为：
1,从线性表 LB中依次察看每个数据元素 ;
2,依值在线性表 LA中进行查访 ;
3,若不存在，则插入之。
GetElem(LB,i)→ e
LocateElem(LA,e,equal( ))
ListInsert(LA,n+1,e)
操作步骤：
GetElem(Lb,i,e); // 取 Lb中第 i个数据元素赋给 e
if (!LocateElem(La,e,equal( )) )
ListInsert(La,++La_len,e);
// La中不存在和 e 相同的数据元素，则插入之
void union(List &La,List Lb) {
La_len = ListLength(La); // 求线性表的长度
Lb_len = ListLength(Lb);
for (i = 1; i <= Lb_len; i++) {
}
} // union
已知 一个 非纯集合 B，试 构造 一个纯集合 A,使 A中只包含 B 中所有值各不相 同的数据元素 。
仍选用 线性表 表示集合例 2-2
集合 B 集合 A
从集合 B 取出物件放入集合 A
要求集合 A中 同样物件不能有两件以上因此,算法的策略应该和例 2-1相同
void union(List &La,List Lb) {
La_len=ListLength(La); Lb_len=ListLength(Lb);
} // union
GetElem(Lb,i,e); // 取 Lb中第 i 个数据元素赋给 e
if (!LocateElem(La,e,equal( )) )
ListInsert(La,++La_len,e);
// La中不存在和 e 相同的数据元素，则插入之
for (i = 1; i <= Lb_len; i++) {
}
InitList(La); // 构造 (空的 )线性表 LA
若线性表中的数据元素相互之间可以 比较,
并且数据元素在线性表中 依值非递减或非递增有序 排列，即
ai≥a i-1 或 ai≤a i-1(i = 2,3,…,n)，则称该线性表为 有序表 (Ordered List)。
试改变结构，以 有序表 表示集合。
例如,
（ 2,3,3,5,6,6,6,8,12）
对集合 B 而言，
值相同的数据元素必定相邻对集合 A 而言，
数据元素依值从小至大的顺序插入因此,数据结构改变了，
解决问题的策略也相应要改变。
void purge(List &La,List Lb) {
InitList(LA); La_len = ListLength(La);
Lb_len =ListLength(Lb); // 求线性表的长度
for (i = 1; i <= Lb_len; i++) {
}
} // purge
GetElem(Lb,i,e); // 取 Lb中第 i个数据元素赋给 e
if (ListEmpty(La) || !equal (en,e)) {
ListInsert(La,++La_len,e);
en = e;
} // La中不存在和 e 相同的数据元素，则插入之则归并两个“其数据元素按值非递减有序排列”的有序表 LA 和 LB，求得有序表
LC 也具有同样特性。
设 La = (a1,…,ai,…,a n),Lb = (b1,…,bj,…,b m)
Lc = (c1,…,ck,…,c m+n)
且 已由 (a1,…,a i-1)和 (b1,…,b j-1)归并得 (c1,…,c k-1)
jij
jii
k bab
baa
c
例 2-3
k = 1,2,…,m+n
1．初始化 LC 为空表；
基本操作：
2．分别从 LA和 LB中取得当前元素 ai 和 bj；
3．若 ai≤ bj，则将 ai 插入到 LC 中，否则将
bj 插入到 LC 中；
4．重复 2 和 3 两步，直至 LA 或 LB 中元素被取完为止；
5．将 LA 表或 LB 表中剩余元素复制插入到
LC 表中。
// La 和 Lb 均非空,i = j = 1,k = 0
GetElem(La,i,ai);
GetElem(Lb,j,bj);
if (ai <= bj) { // 将 ai 插入到 Lc 中
ListInsert(Lc,++k,ai); ++i; }
else { // 将 bj 插入到 Lc 中
ListInsert(Lc,++k,bj); ++j; }
void MergeList(List La,List Lb,List &Lc) {
// 本算法将非递减的有序表 La 和 Lb 归并为 Lc
} // merge_list
while ((i <= La_len) && (j <= Lb_len))
{ // La 和 Lb 均不空 }
while (i<=La_len) // 若 La 不空
while (j<=Lb_len) // 若 Lb 不空
InitList(Lc); // 构造空的线性表 Lc
i = j = 1; k = 0;
La_len = ListLength(La);
Lb_len = ListLength(Lb);
while (i <= La_len) { // 当 La不空时
GetElem(La,i++,ai);
ListInsert(Lc,++k,ai);
} // 插入 La 表中剩余元素
while (j <= Lb_len) { // 当 Lb不空时
GetElem(Lb,j++,bj);
ListInsert(Lc,++k,bj);
} // 插入 Lb 表中剩余元素最简单的一种顺序映象方法是：
令 y 的存储位置和 x 的存储位置相邻 。
顺序映象
—— 以 x 的存储位置和 y 的存储位置之间某种关系表示逻辑关系 <x,y>
用一组 地址连续 的存储单元依次存放 线性表中的数据元素
a1 a2 … ai-1 ai … an
线性表的 起始地址,
称作线性表的 基地址以,存储位置相邻,表示有序对 <ai-1,ai>
即,LOC(ai) = LOC(ai-1) + C
一个数据元素所占存储量 ↑
所有数据元素的存储位置均取决于第一个数据元素的存储位置
LOC(ai) = LOC(a1) + (i-1)× C
↑ 基地址顺序映像的 C 语言描述
typedef struct {
} SqList; // 俗称 顺序表
#define LIST_INIT_SIZE 80
// 线性表存储空间的初始分配量
#define LISTINCREMENT 10
// 线性表存储空间的分配增量
ElemType *elem; // 存储空间基址
int length; // 当前长度
int listsize; // 当前分配的存储容量
// (以 sizeof(ElemType)为单位 )
线性表的基本操作在顺序表中的实现
InitList(&L) // 结构初始化
LocateElem(L,e,compare()) // 查找
ListInsert(&L,i,e) // 插入元素
ListDelete(&L,i) // 删除元素
Status InitList_Sq( SqList& L,int maxsize ) {
// 构造一个最大容量为 maxsize 的顺序表
} // InitList_Sq 算法 时间复杂度,O(1)
L.elem = new ElemType[maxsize];
// 为顺序表分配大小为 maxsize 的数组空间
if (!L.elem) exit(OVERFLOW);
L.length = 0;
L.listsize = maxsize;
return OK;
例如：顺序表
23 75 41 38 54 62 17
L.elem
L.length = 7
L.listsize
e = 38
p p p p p
i 12348
50
可见，基本操作是，
将顺序表中的元素逐个和给定值 e
相比较。
int LocateElem_Sq(SqList L,ElemType e,
Status (*compare)(ElemType,ElemType)) {
// 在顺序表中查询第一个满足判定条件的数据元素，
// 若存在，则返回它的位序，否则返回 0
} // LocateElem_Sq O( ListLength(L) )
算法的 时间复杂度 为：
i = 1; // i 的初值为第 1 元素的位序
p = L.elem; // p 的初值为第 1 元素的存储位置
while (i <= L.length &&
!(*compare)(*p++,e)) ++i;
if (i <= L.length) return i;
else return 0;
线性表 操作
ListInsert(&L,i,e)的实现,
首先分析,
插入元素时，
线性表的 逻辑结构 发生什么变化？
(a1,…,ai-1,ai,…,a n) 改变为
a1 a2 … ai-1 ai … an
a1 a2 … ai-1 …aie an
<ai-1,ai> <ai-1,e>,<e,ai>
表的长度增加
(a1,…,ai-1,e,ai,…,a n)
Status ListInsert_Sq(SqList &L,int i,ElemType e) {
// 在顺序表 L的第 i 个元素之前插入新的元素 e,
// i 的合法范围为 1≤i≤L.length+1
} // ListInsert_Sq
算法时间复杂度 为,
O( ListLength(L) )
q = &(L.elem[i-1]); // q 指示插入位置
for (p = &(L.elem[L.length-1]); p >= q; --p)
*(p+1) = *p; // 插入位置及之后的 元素右移
*q = e; // 插入 e
++L.length; // 表长增 1
return OK;
……
元素右移
if (L.length >= L.listsize) {
// 当前存储空间已满，增加分配
newbase = (ElemType *)realloc(L.elem,
(L.listsize+LISTINCREMENT)*sizeof (ElemType));
if (!newbase) exit(OVERFLOW);
// 存储分配失败
L.elem = newbase; // 新基址
L.listsize += LISTINCREMENT; // 增加存储容量
}
if (i < 1 || i > L.length+1) return ERROR;
// 插入位置不合法考虑移动元素的平均情况,
假设在第 i 个元素之前插入的概率为,
则在长度为 n 的线性表中 插入一个元素所需移动元素次数的期望值 为：
ip
1
1
)1(n
i
iis inpE
1
1
)1(11
n
i
is innE 2
n
若 假定 在线性表中任何一个位置上进行 插入的概率 都是 相等 的，则 移动元素的期望值 为,
21 18 30 75 42 56 87
21 18 30 75
例如,ListInsert_Sq(L,5,66)
L.length-10
pppq
87564266
q = &(L.elem[i-1]); // q 指示插入位置
for (p = &(L.elem[L.length-1]); p >= q; --p)
*(p+1) = *p;
p
线性表操作
ListDelete(&L,i,&e)的实现,
首先分析：
删除元素时，
线性表的逻辑结构发生什么变化？
(a1,…,ai-1,ai,ai+1,…,a n) 改变为
ai+1 … an
<ai-1,ai>,<ai,ai+1> <ai-1,ai+1>
表的长度减少
a1 a2 … ai-1 ai ai+1 … an
a1 a2 … ai-1
(a1,…,ai-1,ai+1,…,a n)
Status ListDelete_Sq
(SqList &L,int i,ElemType &e) {
} // ListDelete_Sq
for (++p; p <= q; ++p) *(p-1) = *p;
// 被删除元素之后的元素左移
--L.length; // 表长减 1
return OK; 算法时间复杂度 为,
O( ListLength(L))
p = &(L.elem[i-1]); // p 为被删除元素的位置
e = *p; // 被删除元素的值赋给 e
q = L.elem+L.length-1; // 表尾元素的位置
if ((i < 1) || (i > L.length)) return ERROR;
// 删除位置不合法元素左移考虑移动元素的平均情况,
假设删除第 i 个元素的概率为,
则在长度为 n 的线性表中 删除一个元素 所需移动元素次数的期望值 为：
iq
n
i
idl inqE
1
)(
n
i
dl innE
1
)(12 n
若假定在线性表中任何一个位置上进行删除的 概率 都是 相等 的，则 移动元素的期望值 为,
21 18 30 75 42 56 87
21 18 30 75
L.length-10
ppp q
8756
p = &(L.elem[i-1]);
q = L.elem+L.length-1;
for (++p; p <= q; ++p) *(p-1) = *p;
例如,ListDelete_Sq(L,5,e)
p
顺序表的特点,
用一组 地址连续 的存储单元 依次存放 数据元素
3、所占存储空间在初始化时 一次性 分配，
难以任意扩大线性表的容量；
1、可以进行 随机存取 ；
2、插入或删除元素需要 移动 其它元素；
一、单链表二、结点和单链表的 C 语言描述三、线性表的操作在单链表中的实现四、一个带头结点的单链表类型五、其它形式的链表六、有序表类型用一组 地址任意 的存储单元 存放 线性表中的数据元素。
一、单链表以 元素 (数据元素的映象 )
+ 指针 (指示后继元素存储位置 )
= 结点
(表示数据元素 或 数据元素的映象 )
以,结点的序列,表示线性表
称作 链表以线性表中第一个数据元素 的存储地址 作为线性表的地址，称作线性表的 头指针
1a
头结点
a1 a2 …,.,a n ^
头指针头指针有时为了操作方便，在第一个结点之前虚加一个“头结点”，以 指向头结点的指针 为链表的头指针空指针线性表为空表时，
头结点的指针域为空
Typedef struct LNode {
ElemType data; // 数据域
struct Lnode *next; // 指针域
} LNode,*LinkList;
二、结点和单链表的 C 语言描述
LinkList L； // L 为单链表的头指针三、单链表操作的实现
GetElem(L,i,e) // 取第 i个数据元素
ListInsert(&L,i,e) // 插入 数据元素
ListInsert(&L,i,e) // 删除 数据元素
ClearList(&L) // 重置线性表为空表
CreateList(&L,n)
// 生成含 n 个数据元素的链表
L
线性表的操作
GetElem(L,i,&e)
在单链表中的实现,
21 18 30 75 42 56 ∧
p p p
j 123
假设,i = 3
因此，查找第 i 个数据元素的基本操作为,移动指针，比较 j 和 i
单链表是一种顺序存取的结构，为找第 i 个数据元素，必须先找到第 i-1 个数据元素。
令指针 p 始终 指向 线性表中第 j 个数据元素
Status GetElem_L(LinkList L,int i,ElemType &e) {
// L是带头结点的链表的头指针，以 e 返回第 i 个元素
} // GetElem_L
算法 时间复杂度 为,
O(ListLength(L))
p = L->next; j = 1; // p指向第一个结点,j为计数器
while (p && j<i) { p = p->next; ++j; }
// 顺指针向后查找，直到 p 指向第 i 个元素
// 或 p 为空
if ( !p || j>i )
return ERROR; // 第 i 个元素不存在
e = p->data; // 取得第 i 个元素
return OK;
ai-1
线性表的操作 ListInsert(&L,i,e)
在单链表中的实现,
有序对 <ai-1,ai>
改变为 <ai-1,e> 和 <e,ai>
e
ai
因此，在单链表中第 i 个结点之前进行插入的基本操作为,
找到线性表中第 i-1个结点，然后修改其指向后继的指针。
可见，在链表中插入结点只需要修改指针。但同时，若要在第 i 个结点之前插入元素，修改的是第 i-1 个结点的指针。
Status ListInsert_L(LinkList L,int i,ElemType e) {
// L 为带头结点的单链表的头指针，本算法
// 在链表中第 i 个结点之前插入新的元素 e
} // LinstInsert_L
算法的 时间复杂度 为,O(ListLength(L))
……
p = L; j = 0;
while (p && j < i-1)
{ p = p->next; ++j; } // 寻找第 i-1 个结点
if (!p || j > i-1)
return ERROR; // i 大于表长或者小于 1
s = new LNode;
// 生成新结点
s->data = e;
s->next = p->next; p->next = s; // 插入
return OK;
e
ai-1 ai
s
p
线性表 的操作 ListDelete (&L,i,&e)
在链表中的实现,
有序对 <ai-1,ai> 和 <ai,ai+1>
改变为 <ai-1,ai+1>
ai-1 ai ai+1
在单链表中 删除第 i 个结点 的 基本操作 为,找到线性表中第 i-1个结点，修改其指向后继的指针。
ai-1 ai ai+1
q = p->next; p->next = q->next;
e = q->data; delete(q);
p q
Status ListDelete_L(LinkList L,int i,ElemType &e) {
// 删除以 L 为头指针 (带头结点 )的单链表中第 i 个结点
} // ListDelete_L
算法的 时间复杂度 为,O(ListLength(L))
p = L; j = 0;
while (p->next && j < i-1) { p = p->next; ++j; }
// 寻找第 i 个结点，并令 p 指向其前趋
if (!(p->next) || j > i-1)
return ERROR; // 删除位置不合理
q = p->next; p->next = q->next; // 删除并释放结点
e = q->data; delete(q);
return OK;
操作 ClearList(&L) 在链表中的实现,
void ClearList(&L) {
// 将单链表重新置为一个空表
while (L->next) {
p=L->next; L->next=p->next;
}
} // ClearList
delete(p);
算法 时间复杂度,O(ListLength(L))
如何从线性表得到单链表？
链表是一个动态的结构，它不需要予分配空间，因此 生成链表的过程是一个结点,逐个插入,的过程。
例如：逆位序输入 n 个数据元素的值，
建立带头结点的单链表。
操作步骤：
一、建立一个“空表”；
二、输入数据元素 an，
建立结点并插入；
三、输入数据元素 an-1，
建立结点并插入；
an
an
an-1
四、依次类推，直至输入 a1为止。
void CreateList_L(LinkList &L,int n) {
// 逆序输入 n 个数据元素，建立带头结点的单链表
} // CreateList_L
算法的 时间复杂度 为,O(Listlength(L))
L = new LNode;
L->next = NULL; // 先建立一个带头结点的单链表
for (i = n; i > 0; --i) {
p = new LNode;
scanf(&p->data); // 输入元素值
p->next = L->next; L->next = p; // 插入
}
回顾 2.1 节中三个例子的算法，
看一下当线性表分别以顺序存储结构和链表存储结构实现时，
它们的时间复杂度为多少？
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( ))
ListInsert(La,++La_len,e);
}//for
} // union
控制结构：
基本操作：
for 循环
GetElem,LocateElem 和 ListInsert
当以 顺序映像 实现抽象数据类型线性表时为,
O( ListLength(La)× ListLength(Lb) )当以 链式映像 实现抽象数据类型线性表时为,O( ListLength(La)× ListLength(Lb) )
例 2-1
算法时间复杂度
void purge(List &La,List Lb) {
InitList(LA);
La_len = ListLength(La); Lb_len =ListLength(Lb);
for (i = 1; i <= Lb_len; i++) {
GetElem(Lb,i,e);
if (ListEmpty(La) || !equal (en,e))
{ ListInsert(La,++La_len,e); en = e; }
}//for
} // purge
控制结构：
基本操作：
for 循环
GetElem 和 ListInsert
当以 顺序映像 实现抽象数据类型线性表时为,
O( ListLength(Lb) )
当以 链式映像 实现抽象数据类型线性表时为,
O( ListLength2(Lb) )
例 2-2
算法时间复杂度
void MergeList(List La,List Lb,List &Lc) {
InitList(Lc); i = j = 1; k = 0;
La_len = ListLength(La); Lb_len = ListLength(Lb);
while ((i <= La_len) && (j <= Lb_len)) {
GetElem(La,i,ai); GetElem(Lb,j,bj);
if (ai <= bj) {
ListInsert(Lc,++k,ai); ++i; }
else { ListInsert(Lc,++k,bj); ++j; }
} … …
控制结构：
基本操作：
三个并列的 while循环
GetElem,ListInsert
当以 顺序映像 实现抽象数据类型线性表时为,
O( ListLength(La)+ListLength(Lb) )当以 链式映像 实现抽象数据类型线性表时为,O( ListLength 2(La)+ListLength 2(Lb) )
例 2-3
算法时间复杂度用上述定义的单链表实现线性表的操作时，
存在的 问题,
改进链表的设置：
1．单链表的表长是一个隐含的值；
1．增加“表长”、“表尾指针” 和,当前位置的指针” 三个数据域；
2．在单链表的最后一个元素之后插入元素时，
需遍历整个链表；
3．在链表中，元素的“位序”概念淡化，结点的
“位置”概念加强。
2．将基本操作中的,位序 i,改变为,指针 p,。
四、一个带头结点的线性链表类型
typedef struct LNode { // 结点类型
ElemType data;
struct LNode *next;
} *Link,*Position;
Status MakeNode( Link &p,ElemType e );
// 分配由 p 指向的值为 e的结点，并返回 OK；
// 若分配失败，则返回 ERROR
void FreeNode( Link &p );
// 释放 p 所指结点
typedef struct { // 链表类型
Link head,tail; // 分别指向头结点和
// 最后一个结点的指针
int len; // 指示链表长度
Link current; // 指向当前被访问的结点
//的指针，初始位置指向头结点
} LinkList;
链表的基本操作,
{结构初始化和销毁结构 }
Status InitList( LinkList &L );
// 构造一个空的线性链表 L，其头指针、
// 尾指针和当前指针均指向头结点，
// 表长为零。
Status DestroyList( LinkList &L );
// 销毁线性链表 L,L不再存在。
O(1)
O(n)
{引用型操作 }
Status ListEmpty ( LinkList L ); //判表空
int ListLength( LinkList L ); // 求表长
Status Prior( LinkList L );
// 改变当前指针指向其前驱
Status Next ( LinkList L );
// 改变当前指针指向其后继
ElemType GetCurElem ( LinkList L );
// 返回当前指针所指数据元素
O(1)
O(1)
O(n)
O(1)
O(1)
Status LocatePos( LinkList L,int i );
// 改变当前指针指向第 i个结点
Status LocateElem (LinkList L,ElemType e,
Status (*compare)(ElemType,ElemType));
// 若存在与 e 满足函数 compare( )判定关系的元
// 素，则移动当前指针指向第 1个满足条件的
// 元素的前驱，并返回 OK; 否则返回 ERROR
Status ListTraverse(LinkList L,Status(*visit)() );
// 依次对 L的每个元素调用函数 visit()
O(n)
O(n)
O(n)
{加工型操作 }
Status ClearList ( LinkList &L );
// 重置 L 为空表
Status SetCurElem(LinkList &L,ElemType e );
// 更新当前指针所指数据元素
Status Append ( LinkList &L,Link s );
// 在表尾结点之后链接一串结点
Status InsAfter ( LinkList &L,Elemtype e );
// 将元素 e 插入在当前指针之后
Status DelAfter ( LinkList &L,ElemType& e );
// 删除当前指针之后的结点
O(1)
O(n)
O(s)
O(1)
O(1)
Status InsAfter( LinkList& L,ElemType e ) {
// 若当前指针在链表中,则将数据元素 e插入在线性链
// 表 L中当前指针所指结点之后,并改变当前指针指向新
//插入结点，返回 OK; 否则返 回 ERROR。
} // InsAfter
if ( ! L.current ) return ERROR;
if (! MakeNode( s,e) ) return ERROR;
s->next = L.current->next;
L.current->next = s;
if (L.tail = L.current) L.tail = s;
L.current = s; return OK;
Status DelAfter( LinkList& L,ElemType& e ) {
// 若当前指针及其后继在链表中，则删除线性链表 L中当前
// 指针所指结点之后的结点，并返回 OK; 否则返回 ERROR。
} //DelAfter
if ( !(L.current && L.current->next ) )
return ERROR;
q = L.current->next;
L.current->next = q->next;
if (L.tail = q) L.tail = L.current;
e=q->data; FreeNode(q);
return OK;
Status ListInsert_L(LinkList L,int i,ElemType e) {
// 在带头结点的单链线性表 L 的第 i 个元素之前插入元素 e
} // ListInsert_L
利用上述定义的线性链表如何完成线性表的其它操作？
if (!LocatePos (L,i-1)) return ERROR;
// i 值不合法，第 i-1 个结点不存在
if (InsAfter (L,e)) return OK; // 完成 插入
else return ERROR;
例一
Status MergeList_L(LinkList &Lc,LinkList &La,
LinkList &Lb,int (*compare)
(ElemType,ElemType))) {
// 归并有序表 La 和 Lb,生成新的有序表 Lc,
// 并在归并之后销毁 La 和 Lb,
// compare 为指定的元素大小判定函数
……
} // MergeList_L
例二
if ( !InitList(Lc)) return ERROR; // 存储空间分配失败
while (!( a=MAXC && b=MAXC)) { // La 或 Lb 非空
}
… …
LocatePos (La,0); LocatePos (Lb,0); // 当前指针指向头结点
if ( DelAfter( La,e)) a = e; // 取得 La 表中第一个元素 a
else a = MAXC; // MAXC为常量最大值
if ( DelFirst( Lb,e)) b = e; // 取得 Lb 表中第一个元素 b
else b = MAXC; // a 和 b 为两表中当前比较元素
DestroyList(La); DestroyList(Lb); // 销毁链表 La 和 Lb
return OK;
if ((*compare)(a,b) <=0) { // a≤b
InsAfter(Lc,a);
if ( DelAfter( La,e1) ) a = e1;
else a = MAXC;
}
else { // a＞ b
InsAfter(Lc,b);
if ( DelAfter( Lb,e1) ) b = e1;
else b = MAXC;
}
1,双向链表五、其它形式的链表
typedef struct DuLNode {
ElemType data; // 数据域
struct DuLNode *prior;
// 指向前驱的指针域
struct DuLNode *next;
// 指向后继的指针域
} DuLNode,*DuLinkList;
最后一个结点的指针域的指针又指回第一个结点的链表
a1 a2 …,.,a n
2,循环链表和单链表的差别仅在于,判别 链表中最后一个结点的 条件 不再是“后继是否为空”，而是,后继是否为头结点” 。
双向循环链表空表非空表
a1 a2 …,.,a n
双向链表的操作特点：
,查询” 和单链表相同
,插入” 和“删除”时需要同时修改两个方向上的指针。
ai-1 ai
e
s->next = p->next; p->next = s;
s->next->prior = s; s->prior = p;
p
s
插入
ai-1
删除
ai ai+1
p->next = p->next->next;
p->next->prior = p;
p
六、有序表类型
ADT Ordered_List {
数据对象,S = { xi|xi? OrderedSet,
i=1,2,…,n,n ≥0 }
集合中任意两个元素之间均可以进行比较数据关系,R = {<xi-1,xi> | xi-1,xi? S,
xi-1≤ xi,i=2,3,…,n }
回顾例 2-2的两个算法基本操作：
… …
… …
LocateElem( L,e,&q,
int(*compare)(ElemType,ElemType) )
初始条件,有序表 L已存在。
操作结果,若有序表 L中存在元素 e，则 q
指示 L中 第一个值为 e 的元素 的位置,并返回函数值 TRUE；否则 q 指示 第一个大于 e 的元素的前驱 的位置,并返回函数值
FALSE。
Compare是一个有序判定函数
( 12,23,34,45,56,67,78,89,98,45 )
例如,
若 e = 45,
则 q 指向若 e = 88,
则 q 指向表示值为 88 的元素应插入在该指针所指结点之后。
void union(List &La,List Lb) {// Lb 为线性表
InitList(La); // 构造 (空的 )线性表 LA
La_len=ListLength(La); Lb_len=ListLength(Lb);
for (i = 1; i <= Lb_len; i++) {
GetElem(Lb,i,e); // 取 Lb中第 i 个数据元素赋给 e
if (!LocateElem(La,e,equal( )) )
ListInsert(La,++La_len,e);
// La中不存在和 e 相同的数据元素，则插入之
}
} // union 算法时间复杂度,O(n2)
void purge(List &La,List Lb) { // Lb为有序表
InitList(LA); La_len = ListLength(La);
Lb_len =ListLength(Lb); // 求线性表的长度
for (i = 1; i <= Lb_len; i++) {
}
} // purge
GetElem(Lb,i,e); // 取 Lb中第 i个数据元素赋给 e
if (ListEmpty(La) || !equal (en,e)) {
ListInsert(La,++La_len,e);
en = e;
} // La中不存在和 e 相同的数据元素，则插入之算法时间复杂度,O(n)
n
nn xpxpxppxp,..)(
2
210
在计算机中，可以用一个线性表来表示,
P = (p0,p1,…,pn)
一元多项式但是对于形如
S(x) = 1 + 3x10000 – 2x20000
的多项式，上述表示方法是否合适？
一般情况下的 一元稀疏多项式 可写成
Pn(x) = p1xe1 + p2xe2 + ┄ + pmxem
其中,pi 是指数为 ei 的项的非零系数,
0≤ e1 < e2 < ┄ < em = n
可以下列线性表表示：
（（ p1,e1）,(p2,e2),┄,(pm,em) ）
P999(x) = 7x3 - 2x12 - 8x999
例如,
可用线性表
( (7,3),(-2,12),(-8,999) )
表示
ADT Polynomial {
数据对象,
数据关系,
抽象数据类型一元多项式的定义如下：
D＝ { ai | ai ∈ TermSet,i=1,2,...,m,m≥0
TermSet 中的 每个元素包含一个表示系数的实数和表示指数的整数 }
R1＝ { <ai-1,ai >|ai-1,ai∈ D,i=2,...,n
且 ai-1中的指数值 ＜ ai中的指数值 }
CreatPolyn ( &P,m )
DestroyPolyn ( &P )
PrintPolyn ( &P )
基本操作,
操作结果,输入 m 项的系数和指数，
建立一元多项式 P。
初始条件,一元多项式 P 已存在 。
操作结果,销毁一元多项式 P。
初始条件,一元多项式 P 已存在 。
操作结果,打印输出一元多项式 P。
PolynLength( P )
AddPolyn ( &Pa,&Pb )
SubtractPolyn ( &Pa,&Pb )
… …
} ADT Polynomial
初始条件,一元多项式 P 已存在 。
操作结果,返回一元多项式 P 中的项数 。
初始条件,一元多项式 Pa 和 Pb 已存在 。
操作结果,完成多项式相加运算，即：
Pa = Pa＋ Pb，并销毁一元多项式 Pb。
一元多项式的实现：
typedef struct { // 项 的表示
float coef; // 系数
int expn; // 指数
} term,ElemType;
typedef OrderedLinkList polynomial;
// 用带表头结点的有序链表表示多项式结点的数据元素类型定义为,
Status CreatPolyn ( polynomail &P,int m ) {
// 输入 m项的系数和指数，建立表示一元多项式的有序链表 P
} // CreatPolyn
InitList (P); e.coef = 0.0; e.expn = -1;
SetCurElem (h,e); // 设置头结点的数据元素
for ( i=1; i<=m; ++i ) { // 依次输入 m 个非零项
}
return OK;
scanf (e.coef,e.expn);
if (!LocateElem ( P,e,(*cmp)()) )
if ( !InsAfter ( P,e ) ) return ERROR;
注意,1.输入次序不限 ;
2.指数相同的项只能输入一次
Status AddPolyn ( polynomial &Pc,
polynomial &Pa,polynomial &Pb) {
// 利用两个多项式的结点构成“和多项式” Pc = Pa＋
Pb
… …
if (DelAfter(Pa,e1)) a=e1.expn else a=MAXE;
if (DelAfter(Pb,e2)) b=e2.expn else b=MAXE;
while (!(a=MAXE && b=MAXE)) {
… …
}
… …
} // AddPolyn
switch (*cmp(e1,e2)) {
case -1,{ // 多项式 PA中当前结点的指数值小
… … break ; }
case 0,{ // 两者的指数值相等
e1.coef= a.coef + b.coef ;
if ( a.coef != 0.0 ) InsAfter(Pc,e1);
… … break ;
}
case 1,{ //多项式 PB中当前结点的指数值小
… … break ; }
}
本章小结
1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系,在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构 。 用前者表示的线性表简称为顺序表,
用后者表示的线性表简称为链表 。
2.熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现。
3.能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。
