1北京邮电大学自动化学院
? 线性结构的特点,在数据元素中的非空有限集中
? （ 1）存在 唯一 的一个被称作,第一”的数据元素；
? （ 2）存在 唯一 的一个被称作,最后一个”的数据元
素；
? （ 3） 除第一个外,集合中的每一个数据元素均 只有
一个前驱；
? （ 4） 除最后一个外,集合中的每一个数据元素均 只
有一个后继。
第二章 线性表
2北京邮电大学自动化学院
? 1、线性表
? 线性表 (Linear List), 一个线性表是 n个数据元素的
有限序列。例如：
? 例 1,26个英文字母组成的字母表
?（ A,B,C,…, Z）
? 例 2、某校从 1999年到 2003年各种型号的计算机拥
有量的变化情况。
?（ 6,17,28,50,92,188）
2.1 线性表的类型定义
3北京邮电大学自动化学院
? 在稍复杂的线性表中，一个数据元素可以由若干个数据项组
成。在这种情况下，常把 数据元素称为记录, 含有大量记录的
线性表又称为文件。
? 例 3、学生健康情况登记表如下：
姓 名 学 号 性 别 年龄 健康情况
王小林 790631 男 18 健康
陈 红 790632 女 20 一般
刘建平 790633 男 21 健康
张立立 790634 男 17 神经衰弱
…….,…….,……,……,…….
1、线性表
4北京邮电大学自动化学院
? 综合上述三个例子可见，线性表中的数据元素可以是各种各样
的，但同一线性表中的元素必定具有相同特征，即属同一数据
对象，相邻数据元素之间存在着序偶关系。若将线性表记为：
? (a1,…,a i-1,ai,a i+1…,a n)
? 则表中 ai-1领先于 ai,ai领先于 a i+1,称 ai-1是 ai的 直接前驱元
素, ai+1是 ai的 直接后继元素 。
? 当 i=1,2,…,n -1时,ai有且仅有一个直接后继，当 i=2,3,…,n
时,ai有且仅有一个直接前驱。
? 线性表中的元素的个数 n(n ? 0)定义为线性表的长度,n=0时
称为空表。
1、线性表
5北京邮电大学自动化学院
? ADT List{
? 数据对象,={ai|ai?ElemSet,i=1,2,…,n,n ?0}
? 数据关系,R1={<ai-1,ai>| ai-1,ai,?D,i=2,…,n}
? 基本操作：
? InitList(&L)
? 操作结果,构造一个空的线性表 L。
2、抽象数据类型线性表
? DestroyList(&L)
? 初始条件,线性表 L已经存在。
? 操作结果,销毁线性表 L。
6北京邮电大学自动化学院
? ClearList(&L)
? 初始条件,线性表 L已经存在。
? 操作结果,将 L置为空表。
2、抽象数据类型线性表
? ListEmpty(L)
? 初始条件,线性表 L已经存在。
? 操作结果,若 L为空表，则返回 TRUE，否则返回
FALSE。
7北京邮电大学自动化学院
? ListLength(L)
? 初始条件,线性表 L已经存在。
? 操作结果,返回 L中数据元素个数。
2、抽象数据类型线性表
? GetElem(L,i,&e)
? 初始条件,线性表 L已经存在,?i?Listlength(L)。
? 操作结果,用 e返回 L中第 i个数据元素的值。
? LocateElem(L,e,compare())
? 初始条件,线性表 L已经存在,compare是数据元素判定函数。
? 操作结果,返回 L中第一个与 e满足关系 compare()的数据元素的
位序。若这样的元素不存在，则返回值为零为。
8北京邮电大学自动化学院
2、抽象数据类型线性表
? ListInsert(&L,i,e)
? 初始条件,线性表 L已经存在，且 1?i ? Listlength(L)＋ 1。
? 操作结果,在 L中第 i个位置之前插入新的数据元素 e,L的长度加 1
? Listdelte(&L,i,&e)
? 初始条件,线性表 L已经存在且非空，且 1?i ? Listlength(L)。
? 操作结果,删除 L中的第 i个数据元素，并用 e返回其值,L的长度
减 1。
? … …
? } ADT List
9北京邮电大学自动化学院
? 例 2-1 利用两个线性表 LA和 LB分别表示两个集合 A和 B，现要
求一个新的集合 A=A∪ B。只要从线性表 LB中依次取得每个数
据元素，并依值在线性表 LA中进行查访，若不存在，则插入。
? 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);//取 Lb 中的第个 i元素赋给 e
? if(!LocateElem(La,e,equal)) Listinsert(La,++La-en,e);
? //La中不存在和 e相同的数据元素，则插入
? } }//union
3、例题
10北京邮电大学自动化学院
? 例 2-2 巳知线性表 LA和线性表 LB中的数据元素按值非递减有序
排列，现要求将 LA和 LB归并为一个新的线性表 LC，且 LC中的
元素仍按值非递减有序排列。
? 例 LA=（ 3,5,8,11）,LB=（ 2,6,8,9,11,15,20）
? 则 LC=（ 2,3,5,6,8,8,9,11,11,15,20）
??
?
?
??
时，当
时当
bab
baac,
3、例题
? 从上面的问题要求可知,LC中的数据元素或是 LA中的数据元
素，或是 LB中的数据元素，则只要先设 LC为空表，然后将 LA或
LB中的元素逐个插入到 LC中即可。设两个指针 i和 j分别指向 LA
和 LB中某个元素，设 i当前所指的元素为 a,j当前所指的元素为
b，则当前应插入到 LC中的元素 c为
11北京邮电大学自动化学院
? 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)) {//La和 Lb均非空
? GetElem(La,i,ai); GetElem(Lb,j,bj);
? if(ai<=bj){ListInsert(Lc,++k,ai);++i;}
? else{ListInsert(Lc,++k,bj);++j;} }
? while(i<=La-len){
? GetElem((La,i++,ai); ListInsert(Lc,++k,ai); }
? while(j<=Lb-len){
? GetElem((Lb,j++,bj);ListInsert(Lc,++k,bj); }}//MergeList
12北京邮电大学自动化学院
? 上述两个算法的时间复杂度取决于抽象数据类型 list定义中基本
操作的执行时间。假如 GetElem和 ListInsert这两个操作的执行
时间和表长无关,LocateElem的执行时间和表长成正比。
4、算法的存储空间需求
? 则算法 2.1的时间复杂度为
?O（ ListLength(LA)?ListLength(LB),
? 算法 2.2的时间复杂度则为
?O（ List Length(LA)+ListLength(LB)。
? 虽然算法 2.2中含有三个（ While）循环语句，但只有当 i和 j均指
向表中实际存在的数据元素时，才能取得数据元素的值并进行相
互比较；并且当其中一个线性表的数据元素均已插入到线性表
LC中后，只要将另外一个线性表中的剩余元素依次插入即可。
13北京邮电大学自动化学院
? 一,线性表的顺序表示 线性表的顺序表示指的是用一组地址
连续的存储单元依次存储线性表的数据元素。
2.2 线性表的顺序存储结构
? 假设线性表的每个元素需占用 l个存储单元，并以所占的第一个
单元的存储地址作为数据元素的存储位置。则线性表中第 i+1个
数据元素的存储位置 LOC( a i+1)和第 i个数据元素的存储位置
LOC(ai )之间满足下列关系：
?LOC(a i+1)=LOC(ai)+l
? 一般来说，线性表的第 i个数据元素 ai的存储位置为：
?LOC(ai)=LOC(a1)+(i-1)*l
? 若每个数据元素占用 m个存储单元，则第 i个数据元素 ai的存储位
置为,LOC(ai)=LOC(a1)+(i-1)*m
14北京邮电大学自动化学院
? 线性表的这种机内表示称作 线性表的顺序存储结构, 称
这种存储结构的线性表为顺序表。
一,线性表的顺序表示
? 顺序存储的结构特点,以数据元素在计算机“物理位置
相邻”来表示表中数据元素间的逻辑关系。 对于这种存
储方式，要访问第 i个数据元素，就可以直接计算出 ai的
存储位置 Loc(ai)。因而能随机存取表中任一数据元素，
换言之,数据元素在顺序表中的存储位置取决于该数据
元素在线性表中的顺序号 。
? 例如：一个班学生，集体出游，按学号分配房
间。。。。。
15北京邮电大学自动化学院
? 由于 C语言中的一维数组也是采用顺序存储表示，故可以用数组
类型来描述顺序表。又因为除了用数组来存储线性表的元素之
外，顺序表还应该用一个变量来表示线性表的长度属性，所以我
们用结构类型来定义顺序表类型。
一,线性表的顺序表示
? # define LIST-INIT-SIZE 100 //线性表初始分配量
? # define LISTINCREMENT 10 //线性表分配增量
? typedef struc{
? Elemtype *elem //存储空间基址
? int length ;//当前长度
? int ListSize; } Sqlist;
16北京邮电大学自动化学院
? 在顺序表存储结构中，很容易实现线性表的一些操作，如线
性表的构造、第 i个元素的访问。
? 注意,C语言中的数组下标从,0”开始，因此，若 L是
Sqlist类型的顺序表，则表中第 i个元素是 L.data[i-1]。
二、顺序表上实现的基本操作
? 顺序表上基本运算
? 1,顺序表的初始化
? 2,插入运算
? 3,删除运算
? 4,按值查找
17北京邮电大学自动化学院
? 线性表的插入 是指在表的第 i个位置上插入一个值为 x 的新元
素，插入后使原表长为 n的表,
? (a1,a2,..., ai-1,ai,ai+1,..., an)
? 成为表长为 n+1 表,
? (a1,a2,...,ai-1,x,ai,ai+1,...,an ) 。 1<=i<=n+1 。
1、插入
? 顺序表上完成这一运算需要通过以下步骤进行：
? 1）将 ai～ an 顺序向下移动，为新元素让出位置；
? 2）将 x 置入空出的第 i个位置；
? 3）修改 last 指针 (相当修改表长 )，使之仍指向最后一个元素。
18北京邮电大学自动化学院
内存
a1
a2
ai
ai+1
an
0
1
i-1
V数组下标
n-1
i
n
1
2
i
元素序号
i+1
n
n+1
内存
a1
a2
ai
ai+1
an
0
1
i-1
V数组下标
n-1
i
n
1
2
i
元素序号
i+1
n
n+1
an-1
x
19北京邮电大学自动化学院
? Status ListInsert_Sq(SqList &L,int i,ElemType e)
? {if(i<1 || i>L.length+1) return ERROR //i值不合法
? 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;} // 增加存储容量 }
算法 2.3
20北京邮电大学自动化学院
?q=&(L.elem[i-1]); //q为插入位置
算法 2.3
? for(p=&(L,elem [L.length-1]);p>=q;--p)
*(p+1)=*p;
? //插入位置及之后的元素后移
? *q=e; //插入 e
? ++L.length; //表长增 1
? return OK;} //IistInsert_Sq
21北京邮电大学自动化学院
? 这里的问题规模是表的长度，设它的值为 n。 该算法的时间
主要花费在循环的结点后移语句上,由此可看出，所需移动
结点的次数不仅依赖于 表的长度，而且还与插入位置有关 。
算法的复杂度
? 当 i=n时，由于循环变量的终值大于初值，结点后移语句将
不进行；这是最好情况，其时间复杂度 O（ 1）；
? 当 i=1时，结点后移语句将循环执行 n次，需移动表中所有
结点，这是最坏情况，其时间复杂度为 O（ n）。
? 由于插入可能在表中任何位置上进行，因此需分析算法的
平均复杂度。
22北京邮电大学自动化学院
? 在长度为 n的线性表中第 i个位置上插入一个结点，令 Eis(n)表
示移动结点的期望值（即移动的平均次数），则在第 i个位置
上插入一个结点的移动次数为 n-i+1。故
1)i-(np ( n )E
1n
1i
iis ?
?
?
??
2)1(1
1 1
1
nin
nE
n
iis
????? ??
?
? 也就是说,在顺序表上做插入运算，平均要移动表上一半结
点。 当表长 n较大时，算法的效率相当低。虽然 Eis(n)中 n的
系数较小，但就数量级而言，它仍然是线性阶的。因此算法
的平均时间复杂度为 O(n)。
? 不失一般性，假设在表中任何位置 (1≦ i≦ n+1)上插入结点的
机会是均等的，则 p1=p2=p3=…=p n+1=1/(n+1)
? 因此，在等概率插入的情况下，
算法的复杂度
23北京邮电大学自动化学院
? 线性表的删除运算是指将表的第 i(1≦ i≦ n)结点删除，使长度
为 n的线性表：
? (a1,…a i-1,ai,a i+1…, an)
2、删除
? 变成长度为 n-1的线性表
? (a1,…a i-1,a i+1,…, an)
? 顺序表上完成这一运算的步骤如下：
?（ 1） 将 ai+1～ an 顺序向前移动。
?（ 2） 修改 last指针 (相当于修改表长 )使之仍指向最后
一个元素。
24北京邮电大学自动化学院
内存
a1
a2
ai
ai+1
an
0
1
i-1
V数组下标
n-1
i
n
1
2
i
元素序号
i+1
n
n+1
内存
a1
a2
ai+1
V数组下标
0
1
i-1
n-2
i
n-1
1
2
i
元素序号
i+1
n-1
n
an
ai+2
25北京邮电大学自动化学院
? Status ListDelete_Sq(SqList &L,int i,ElemType e) {
? if((i<1 || i>L.length) return ERROR; //i值不合法
? p=&(L.elem[i-1]); //p为被删除元素位置
? e = *p; //被删除元素值赋给 e
? q=L.elem+L.length-1; //表尾元素位置
算法 2.4
? For (++p; p<=q; ++p)*(p-1)=*p;
? //被删除元素之后的元素左移
? --L.length; //表长减 1
? return OK; } //IistDelete_Sq
26北京邮电大学自动化学院
? 该算法的时间分析与插入算法相似，结点的移动次数也是由表
长 n和位置 i决定。
4、算法的存储空间需求
? 假设 qi是删除第 i个元素的概率，则在长度为 n的线性表中删除
一个元素时所需移动元素次数的期望值（平均次数）为：
? 不失一般性，假设在表中任何位置上删除结点的机会是均等
的，则 qi=1/n
? 因此，在等概率插入的情况下，
? 也就是说,在顺序表上做删除运算，平均要移动表中约一半的
结点，平均时间复杂度也是 O(n)。
?
?
??
n
i
idl inqE
1
)(
?
?
???? n
i
dl
nin
nE 1 2
1)(1
27北京邮电大学自动化学院
? 线性表的顺序表示的特点是用 物理位置上的邻接关系来表示结点
间的逻辑关系,这一特点使我们可以随机存取表中的任一结点，
但它也使得 插入和删除操作会移动大量的数据元素。
2.3 线性表的链式表示和实现
? 由于顺序表需要一组地址连续的存储单元，对于长度可变的线性
表就需要预分配足够的空间，有可能使一部分存储空间长期闲置
不能充分利用。
? 也可能由于估计不足，当表长超过预分配的空间而造成溢出，在
这种情况下，又难于扩充连续的存储空间。
? 为了克服上述缺点，我们将谈论线性表的另一种存储方式链式存
储结构，简称为 链表 (Linked List)。
28北京邮电大学自动化学院
? 线性表的链式存储的特点 是指用 一组任意的存储单元 来依次
存放线性表的结点，这组存储单元既可以是连续的，也可以
是不连续的，甚至是零散分布在内存中的任意位置上的。因
此,链表中结点的逻辑次序和物理次序不一定相同。
data next
2.3.1 线性链表
? 为了能正确表示结点间的逻辑关系,在存储每个结点值的同
时，还必须存储指示其后继结点的地址（或位置）信息,这
个信息称为 指针 (pointer)或链 (next)。 这两部分信息组成了
元素 ai的存储映象，称为 结点,它包括两个域：
? 其中,data域是 数据域,用来存放结点的值。 next是 指针域
（亦称链域），用来存放结点的直接后继的地址（或位置）。
29北京邮电大学自动化学院
? 链表正是通过每个结点的链域将线性表的 n个结点按其逻辑次
序链接在一起的。
2.3.1 线性链表
? n个结点 ai( 1<=i<=n）连接成一个链表，即为线性表 (a1，
a2,…, an) 的链式存储结构。 由于上述链表的每一个结点只
有一个链域，故将这种链表称为单链表（ Single Linked)。
? 链表中每个结点的存储地址是存放在其前驱结点 next域中，而
开始结点无前驱,故应设头指针 head指向开始结点。同时，由
于终端结点无后继，故终端结点的指针域为空，即 NULL（图
示中也可用 ^表示 )
? 通常把线性链表画成用箭头相连接的节点序列，其中箭头表示
链域中的指针。
h a2 a3 an ^…...a1
30北京邮电大学自动化学院
赵 钱 孙 李
周 吴 郑 王 ^
H
例 线性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)
43
13
1
NULL
37
7
19
25
数据域 指针域
李
钱
孙
王
吴
赵
郑
周
存储地址
1
7
13
19
25
31
37
4331
H
头指针
31北京邮电大学自动化学院
2.3.1 线性链表
? 由上述可见，单链表可由头指针唯一确定，在 C语言中可用
“结构指针”来描述：
? typedef struct Listnode
{
? Elemtype data;
? struct Listnode *next;
? } Listnode,*Linklist,JD;
? Elemtype 为数据域的类型，
可以是任何类型。
? Data为数据域，存放该结点
的数据 ;
? next为指针域，指向该结点
的直接后继结点。
? 线性表的单链表存储结构
32北京邮电大学自动化学院
? 假设 L为 LinkList型的变量，则 L为单链表的头指针，它指向表
中第一个结点。
L 空表^
? 有时，我们在单链表的第一个结点之前附设一个结点，称之为
头结点 。 头结点 的数据可以不存储任何信息，也可以存储如线
性表的长度等类的附加信息，头结点的指针域存储指向第一个
结的指针。
? 若 L为“空”（ L=NULL），则所表示的线性表为“空”表，
其长度 n为“零”。
2.3.1 线性链表
L a1 a2
头结点
an ^…...
33北京邮电大学自动化学院
data next
p 结点（ *p）
2.3.1 线性链表
? （ *p）表示由指针所指向的节点。
? (*p).data?p->data表示 p指向结点的数据域
? (*p).next?p->next表示 p指向结点的指针域
? 指针变量 p（其值为结点地址）和结点变量 *p之间的关系。
h 1145 1248 2158 ^…...1012
? h->data=1012 (h->next)->data=1145
? p结点是指指针 p所指向的结点（即其存储位置存放在 p中的
结点）。,.”是成员（分量）运算符，“－ >”指向运算符。
? (*h).data=1012
34北京邮电大学自动化学院
?假设 p是指向线性表中第 i个数据元素（结点 ai）的
指针，则 p->next是指向第 i+1个数据元素（结点
ai+1）的指针。
? 换句话说，若 p->data=ai，
2.3.1 线性链表
p ai ai+1 ai+2
则 p->next->data=ai+1
? 由此，在单链表中，取得第 i个数据元素必须从头
指针出发寻找，因此,单链表是非随机存取的存储
结构。
35北京邮电大学自动化学院
?假设线性表中结点的数据类型是字符，我们逐个输
入这些字符型的结点，并以换行符‘ \n’为输入结束
标记。
一、建立单链表
? 动态地建立单链表的常用方法有如下两种：
? 1、头插法建表
? 该方法从一个空表开始，重复读入数据，生成新
结点，将读入数据存放到新结点的数据域中，然
后将新结点插入到当前链表的表头上，直到读入
结束标志为止。
36北京邮电大学自动化学院
? linklist createlistf(void)
? { char ch; linklist head; listnode *p;
? head=null; ch=getchar( );
? while (ch!=‵ \n′） {
? p=(Listnode*)malloc(sizeof(Listnode));
1、头插法建表
? p–>data=ch;
? p–>next=head; head=p;
?ch=getchar( ); }
? return (head); }
37北京邮电大学自动化学院
? listlink createlist ( int n)
? { int data; linklist head; listnode *p; head=null;
? for(i=n;i>0;--i){
? p=(listnode*)malloc(sizeof(listnode));
1、头插法建表
?scanf((〝 %d〞, &p–>data);
? p–>next=head;
? head=p;
?} return(head); }
38北京邮电大学自动化学院
? 假设 p是 LinkList型的变量，则执行
? p=(listnode*)malloc(sizeof(listnode));
2.3.1 线性链表
? 因此单链表和顺序存储结构不同，它是一种 动态结构。 整个可用
存储空间可为多个链表共同享受，每个链表占用的空间不需要预
先划定，而是可以由系统应需求即时生成。
? 的作用是由系统生成一个 listnode型的结点，同时将该结点的起
始位置赋给指针变量 p。
? 一旦 p所指的结点变量不再需要了，又可通过标准函数 free(p) 释
放所指的结点变量空间。
39北京邮电大学自动化学院
?头插法建立链表虽然算法简单，但生成的链表中结
点的次序和输入的顺序相反。
2、尾插法建表
?若希望二者次序一致，可采用尾插法建表。该方法
是将 新结点插入到当前链表的表尾上,为此必须增
加一个尾指针 r，使其始终指向当前链表的尾结点。
例：
40北京邮电大学自动化学院
? linklist creater( ) { char ch; linklist head;
? listnode *p,*r; //(,*head;)
? head=NULL; r=NULL;
2、尾插法建表
? while((ch=getchar( )!=‵ \n′) {
? p=(listnode *)malloc(sizeof(listnode));
? p–>data=ch;
? if(head=NULL) head=p; else r–>next=p;
? r=p;
? } if (r!=NULL) r–>next=NULL; return(head); }
41北京邮电大学自动化学院
? 说明,第一个生成的结点是开始结点,将开始结点插入到空表
中，是在当前链表的第一个位置上插入，该位置上的插入操作
和链表中其它位置上的插入操作处理是不一样的，原因是 开始
结点的位置是存放在头指针（指针变量）中，而其余结点的位
置是在其前驱结点的指针域中。
2、尾插法建表
? 算法中的第一个 if语句就是用来对第一个位置上的插入操作做
特殊处理 。
? 算法中的第二个 if语句的作用是为了分别处理 空表和非空表 两
种不同的情况，若读入的第一个字符就是结束标志符，则链表
head是空表，尾指针 r亦为空，结点 *r不存在；否则链表 head
非空，最后一个尾结点 *r是终端结点，应将其指针域置空。
42北京邮电大学自动化学院
?如果我们在链表的开始结点之前附加一个结点，并
称它为头结点，那么会带来以下两个优点：
? a、由于开始结点的位置被存放在头结点的指针域
中，所以在链表的第一个位置上的操作就和在表的
其它位置上的操作一致，无需进行特殊处理；
? b、无论链表是否为空，其头指针是指向头结点
的非空指针（空表中头结点的指针域为空），因此
空表和非空表的处理也就统一了。
2、尾插法建表
43北京邮电大学自动化学院
? linklist createlistr1( ){ char ch;
? linklist head=(linklist)malloc(sizeof(listnode));
? listnode *p,*r; r=head;
2、尾插法建表
? while((ch=getchar( ))!=‵ \n′{
? p=(listnode*)malloc(sizeof(listnode));
? p–>data=ch; r–>next=p; r=p; }
? r–>next=NULL;
? return(head); }
44北京邮电大学自动化学院
?上述算法里动态申请新结点空间时未加错误处理，
可作下列处理：
? p=(listnode*)malloc(sizeof(listnode))
? if(p==NULL)
? error(〝 No space for node can be obtained〞 );
? return ERROR;
? 以上算法的时间复杂度均为 O(n)。
2、尾插法建表
45北京邮电大学自动化学院
?1、按序号查找
二、查找运算
? 在链表中，即使知道被访问结点的序号 i，也不能象顺
序表中那样直接按序号 i访问结点，而只能从链表的头
指针出发，顺链域 next逐个结点往下搜索，直到搜索到
第 i个结点为止。因此,链表不是随机存取结构。
? 设单链表的长度为 n，要查找表中第 i个结点，仅当
1≦ i≦ n时,i的值是合法的。但有时需要找头结点的位
置，故我们将头结点看做是第 0 个结点，其算法如下：
46北京邮电大学自动化学院
? Listnode * getnode(linklist head, int i)
? { int j; listnode * p; p=head; j=0;
1、按序号查找
? while(p–>next && j<i)
? { p=p–>next; j++;
? }
? if (i==j) return p;
? else
? return NULL; }
47北京邮电大学自动化学院
?按值查找是在链表中，查找是否有结点值等于给
定值 key的结点，若有的话，则返回首次找到的
其值为 key的结点的存储位置；否则返回 NULL。
2、按值查找
? 查找过程从开始结点出发，顺着链表逐个将结点
的值和给定值 key作比较。
48北京邮电大学自动化学院
? 其算法如下：
? Listnode * locatenode(linklist head,int key) {
? listnode *p=head–>next;
2、按值查找
? while( p && p–>data!=key)
? p=p–>next;
? return p; }
? 该算法的执行时间亦与输入实例中的的取值 key有关，其平
均时间复杂度的分析类似于按序号查找，也为 O(n)。
49北京邮电大学自动化学院
? 插入运算是将值为 x的新结点插入到表的第 i个结点的位置
上，即插入到 ai-1与 ai之间。
p ai-1 ai
xs
s->next=p->next;p->next=s;
三、插入运算
? 然后，新结点的指针域指向结点 ai，
? 最后,p结点的指针域指向新结点 s，
? 从而实现三个结点 ai-1,x和 ai之间的逻辑关系的变化。
? 必须首先找到 ai-1的存储位置 p，然后生成一个数据域为 x的新
结点 *s，并令结点 *s的指针域指向新结点，
50北京邮电大学自动化学院
? void insertnode(linklist head,datetype x,int i) {
? listnode * p,*q;
? p=getnode(head,i-1);
? if(p==NULL)
? error(〝 position error〞 );
? s=(listnode *)malloc(sizeof(listnode));
p ai-1 ai
xs
s->next=p->next;
p->next=s;
插入运算具体算法
? s–>data=x;
? s–>next=p–next;
? p–>next=s; }
51北京邮电大学自动化学院
?设链表的长度为 n，合法的插入位置是
1≦ i≦ n+1。
?注意当 i=1时,getnode找到的是头结点，
?当 i=n+1时,getnode找到的是结点 an。
?因此，用 i-1做实参调用 getnode时可完成插入位置
的合法性检查。算法的时间主要耗费在查找操作
getnode上，故时间复杂度亦为 O(n)。
插入运算具体算法
52北京邮电大学自动化学院
?删除运算 是将表的第 i个结点删去。因为在单链表中结
点 ai的存储地址是在其直接前驱结点 a i-1的指针域
next中，
p ai-1 ai ai+1
p->next=p->next->next;
四、删除运算
? 所以我们必须首先找到 a i-1的存储位置 p。
? 然后令 p–>next指向 ai的直接后继结点，即把 ai从链上
摘下。最后释放结点 ai的空间，将其归还给“存储
池”。
53北京邮电大学自动化学院
? void deletelist(linklist head,int i) {
? listnode * p,*r;
? p=getnode(head,i-1);
删除运算算法
? if(p= =NULL || p–>next= =NULL)
? return ERROR;
? r=p–>next;
? p–>next=r–>next;
? free( r ) ; }
54北京邮电大学自动化学院
? 设单链表的长度为 n，则删去第 i个结点仅当 1≦ i≦ n时是合法
的。注意，当 i=n+1时，虽然被删结点不存在，但其前驱结
点却存在，它是终端结点。 因此被删结点的直接前驱 *p存在
并不意味着被删结点就一定存在，仅当 *p存在（即
p!=NULL）且 *p不是终端结点。
删除运算算法
? （即 p–>next!=NULL）时，才能确定被删结点存在
? 显然此算法的时间复杂度也是 O(n)。
? 从上面的讨论可以看出，链表上实现插入和删除运算，无须
移动结点，仅需修改指针。
55北京邮电大学自动化学院
?1、在头指针为 h的带表头结点的单链表中，把结
点 b插入到 a结点之前，若不存在结点 a就把结点 b
插入到表尾。
五、链表的其他运算示例
? 插入过程：
? 找到结点 a时,p指向结点,q指向结点 a的直接
前驱结点。
? 首先生成一个 s结点，将 s结点的数据域置为
b，然后修改相应的指针，把结点 a作为 s结点
的直接后继，把 s结点作为 q结点的直接后继。
56北京邮电大学自动化学院
? Void dlbqcr(JD *h,int a,int b) {//在头指针为 h的带表头结点的单链表中结点 a
之前插入结点 b，若表中无结点 a，则插到表尾
? JD*p,*q,*s;
例题 1算法
? s=(JD*)malloc(sizeof(JD));
? s->data=b;
? p=h->link;q=h;
? While(p->data!=a&&p->link!=NULL)
? {q=p;p=p->link;}//查找结点 a
? If(p->data==a;)
? { s->link=p; q->link=s;}//找到结点时，把结点插到结点 a之前
? Else{p->link=s;s->link=NULL;}//表中无结点 a，则插到表尾 }
q ai-1 ai
xs
s->next=p
q->next=s;
57北京邮电大学自动化学院
? 2、设线性表的 n个数据元素依次存放在一维数组 a[n]中，请建立
一个带表头结点的单链表,h为新建单链表的指针。
? 要建立一个带 表头结点的单链表,首先生成一个 h结点作为表结
点，其链域置为“空”。
? 在生成一个 s结点，将其数据域置为第 n个数据元素，链域置
为“空”。 s结点作为表中第一个结点。
? 顺次生成新的 s结点，置其数据域为第 i个数据元素 (i=n-1,n-
2,…,2,1),修改有关指针：把表中第一个结点作为 s结点的直接
后继,s结点作为表中第一个结点。即把含第 i个数据元素的结点
插入到表中第一个结点之前。
2、例题 2
58北京邮电大学自动化学院
? JD*DLBJL(INT A[],INTN)
? {//线性表中的 n个数据元素
存入一维数组 a中，建立一
个带表头结点的单链表，其
头指针为 h
? JD *S,*h; Int i;
? h=(JD*)malloc(sizeof(JD));
? h->data=0;h->link=NULL;
? For(i=n;i>0;i--)
?
{s=(JD*)mallic(sizeof(JD));
? s->data=a[i-1];
? s->link=h->link;
? h->link=s;}
? return(h);}
例题 2算法
59北京邮电大学自动化学院
?3、设 h是带表头结点的单链表的头指针，请设计一
个逆置这个单链表的算法。
3、例题 3
?建立逆表的方法是,顺序扫描原表,依次将原表中
的结点逐个插入到第一个结点之前,可得到逆置链
表。
?设 s指向当前逆转结点,p指向 s结点的直接后继结
点。
60北京邮电大学自动化学院
?Void dlbnz(JD*h){ JD*s,*p;
? p=h->link;// *p先指向原表中第一个结点
? h->link=NULL;//逆表的初态为空表
例题 3算法
? While(p!=NULL)
? {s=p;// *s指向当前逆转的结点
? p=p->link;
? s->link=h->link ;
? h->link=s;//把 s结点插入到逆表 }}
61北京邮电大学自动化学院
? 4、设 pa,pb分别为两个按升序排列的单链表的头指针，请设
计一个算法把这两个单链表合并为一个按升序排列的单链表。
4、例题 4
? 合并的方法是：从两表的第一个结点开始顺链逐个将对应数据
元素进行比较，复制小者并插入 c表尾。当两表中之一已到表
尾，则复制另一链表的剩余部分，插入到 c表尾。
? /JD*dlnhb(JD *pa,JD*pb);
? {//把 pa,pb为头指针的按升序排列的单链表合并成一个按升序
排列的单链表。 P指向 c表的当前表尾。
? JD *p,*q;*pc;
? pc=(JD)malloc(sizeof(JD)); p=pc;
62北京邮电大学自动化学院
? While(pa!=NULL && pb!=NULL){
? q=(JD* )malloc (sizeof(JD));
例题 4算法
? Else { q->data=pa->data; pa=pa->link;
? If (pb->data<pa->data)
? {q->data=pb->data; pb=pb->link;}
? If (pa->data==pb->data) pb=pb->link； }
? p->link=q;
? p=q;}
63北京邮电大学自动化学院
?While(pa!=NULL)
?{ q=(JD*)malloc(sizeof(JD));
? q->data=pa->data;
? pa=pa->link;
例题 4算法
? p->link=q;
? p=q;
? }
64北京邮电大学自动化学院
?While(pb!=NULL)
?{ q=(JD*)malloc(sizeof(JD));
例题 4算法
?q->data=pb->data; pb=pb->link;
?p->link=q; p=q;}
?p->link=NULL
?p=pc; pc=p->link; free(p)
?return(pc);}
65北京邮电大学自动化学院
? 循环链表 是一种头尾相接的链表。其特点是无须增加存储
量，仅对表的链接方式稍作改变，即可使得表处理更加方便
灵活。
2.3.2 循环链表
? 单循环链表,在单链表中，将终端结点的指针域 NULL改为
指向表头结点或开始结点，就得到了单链形式的循环链表，
并简单称为 单循环链表。
? 为了使空表和非空表的处理一致，循环链表中也可设置一个
头结点。这样，空循环链表仅有一个自成循环的头结点表
示。如下图所示：
66北京邮电大学自动化学院
h
⑴ 非空表
h
⑵ 空表
? 在用头指针表示的单链表中，找开始结点 a1的时间是 O(1)，
然而要找到终端结点 an，则需从头指针开始遍历整个链
表，其时间是 O(n)。
2.3.2 循环链表
67北京邮电大学自动化学院
? 在很多实际问题中，表的操作常常是在表的首尾位置上进
行，此时头指针表示的单循环链表就显得不够方便。
? 由于循环链表中没有 NULL指针，故涉及遍历操作时，其终
止条件就不再像非循环链表那样判断 p或 p—>next是否为
空,而是判断它们是否等于某一指定指针，如头指针或尾指
针等。
2.3.2 循环链表
? 如果改用尾指针 rear来表示单循环链表，则查找开始结点 a1
和终端结点 an都很方便，它们的存储位置分别是 (rear–
>next) —>next和 rear,显然，查找时间都是 O(1)。因此，
实际中多采用尾指针表示单循环链表。
68北京邮电大学自动化学院
? 例如、在链表上实现将两个线性表 (a1,a2,a3,…a n)和
(b1,b2,b3,…b n)链接成一个线性表的运算。
? JD * xhblj(JD *ha,JD *hb); {//ha,hb为两个带 头结点 的循
环链表的尾指针，把 hb表连在 ha表之后
? JD *q,*p
? q=ha—>next; p=hb—>next;
2.3.2 循环链表
? ha—>next=p—>next; //a,b两个线性表 尾首相连
? hb—>next=q;// a,b两个线性表 首尾相连
? ha=hb; free(p);//释放 hb表头结点 }
69北京邮电大学自动化学院
?单链表有一个很大的缺点,它只能顺着直接后继指针向
后查找其他结点,如若找某结点的直接前驱结点，只能
从表头指针开始查找。换句话说，在单链表中，
NextElem的执行时间为 O(1)，而 PriorElem的执行时间
为 O（ n）。
2.3.3双链表
? 为了克服单链表这种单向性的缺点，双向链表可有效解
决这个问题。
? 双向链表 (Double linked list):在单链表的每个结点里
再增加一个指向其直接前驱的指针域 prior。这样形成
的链表中就有两个方向不同的链，故称为 双向链表。
70北京邮电大学自动化学院
? typedef struct node {
? datatype element;
? struct node *prior,*next;}JD;
prior element next
L空双向循环链表：
非空双向循环链表,L A B
b ca
p
p->prior->next= p= p->next->proir;
双向链表（ double linked list）结点定义
71北京邮电大学自动化学院
?和单链表类似，双链表一般也是由头指针唯一确定的，
增加头指针也能使双链表上的某些运算变得方便，将头
结点和尾结点链接起来也能构成循环链表，并称之为 双
向链表。
2.3.3双链表
? (p—>prior)—>next=p=(p—>next)—>prior
?即结点 *p的存储位置既存放在其前驱结点 *(p—>prior)
的直接后继指针域中，也存放在它的后继结点 *(p—
>next)的直接前驱指针域中。
? 设指针 p指向某一结点，则双向链表结构的对称性可用
下式描述：
72北京邮电大学自动化学院
?在双链表中，有些操作如,ListLength,GetElem
和 LocateElem等仅需要涉及一个方向的指针，则它
们的算法描述和线性链表的操作相同，但在插入和
删除操作时有很大的不同，在双链表中插入和删除
必须同时修改两个方向上的指针。上述两个算法的
时间复杂度均为 O(n)。
2.3.3双链表
73北京邮电大学自动化学院
xS
ba
P（ 1）插入
?void sxlbcr(JD*p,int x)
?{ JD *s;s=(JD *s) malloc (sizeof(JD)); s—>data=x;
?s—>prior=p->prior;//1步
?p->prior->next=s;//2步
?s—>next=p;//3步
?p—>prior=s; //4步 }
74北京邮电大学自动化学院
b ca
P
（ 2）删除
p->prior->next=p->next;
p->next->prior=p->prior;
?void ddeletenode(dlistnode *p)
? {p–>prior–>next=p–>next;
? p–>next–>prior=p–>prior;
? free(p); }
75北京邮电大学自动化学院
?从本节的讨论中可见：由于链表在空间的合理利用上
和插入、删除时不需要移动等优点，因此 在很多场合
下，它是线性表的首选存储结构。
?然而它也存在着实现某些基本操作如求线性表长度时
不如顺序存储结构的缺点；
?为此，从实际应用角度出发重新定义线性链表及其基
本操作（见 P37~38）。
?另一方面，由于在链表中，节点之间的关系用指针来
表示，则数据元素在线性表中的“位序”的概念已淡
化，而被数据元素在线性表链表中的“位置”所代
替。
76北京邮电大学自动化学院
nnn xPxPxPPxP ????? ??2210)(
? 多项式的运算问题，已经成为表处理的一个经典问题。通
常一个多项式 Pn(x)可按升密写成：
2.4一元多项式相加
),,,210 mqqqqQ ??（?
),,,210 nppppP ??（?
? 它由 n+1个系数唯一确定。在计算机里，它可用一个线性表 P
来表示：
? 每一项的指数 i隐含在其系数 pi的序号里。
? 假设 Qm(x)是一元 m次多项式，同样可用线性表 Q来表示：
? 假设 m<n,则两个多项式相加的结果 Rn(x)=Pn(x)+Qm(x)可用
线性表 R表示,
? 我们可以对 P,Q和 R采用顺序存储结构,使得多项式相加的算
法定义十分简洁。
),,,,,,11221100 nmmm ppqpqpqpqpR ?? ???????（
77北京邮电大学自动化学院
20 00 010 00 231)( xxxS ???
mee emn xPxPxPxP ???? ??21 21)(
为非零系数）（ im Peee ??? ??210
? 至此，一元多项式的表示及相加问题似乎已经解决。然而，在
通常的应用中，多项式的次数可能很高且变化很大，使得顺序
存储结构的最大长度很难确定。特别是在处理式的次数可能很
高且变化很大，使得顺序存储结构的最大长度很难确定。特别
是在处理形如：
2.4一元多项式相加
? 的多项式时，就要用一长度为 20001的线性表来表示，表中仅
有 3个非零元素，这种对内存空间浪费应当避免。
? 其中,pi是指数为 ei的项的非零系数，且满足：
? 但是如果只存储非零系数项，显然必须同时存储相应的指数。
一般情况下的一元 n次多项式可写成：
78北京邮电大学自动化学院
emmn xPxPxPxP ee ???? ??21 21)(
? ? ? ? ? ?? ?emPePeP m,，，，,??21 21
? 若用一个长度为 m且为每个数据元素有两个数据项（系数项和
指数项）的线性表
2.4一元多项式相加
? 便可唯一确定多项式 Pn(x)。在最坏情况下,n+1(=m)个系数都
不为零，则比只存储每项系数的方案要多一倍的数据。但是，
对于 S(x)类的多项式，这种表示将大大节省空间。
? 对应于线性表的两种存储结构，由上式定义的一元多项式也可
以有两种存储表示方法。在实际的应用程序中取用哪一种，则
要视多项式作何种运算而定。
? 若只对多项式进行“求值”等不改变多项式的系数和指数的运
算,则采用类似于顺序表的顺序存储结构即可,否则应采用链
式存储结构。 本节中将主要讨论如何利用线性链表的基本操作
来实现一元多项式的运算。
79北京邮电大学自动化学院
? typedef struct node
? { int coef,exp;
? struct node *next;}JD;
coef exp next
177
87
172
522117)()()(
9228)(
5937)(
xxxxBxAxC
xxxxB
xxxxA
??????
???
????
-1A 7 0 3 1 9 8 5 17 ^
-1B 8 1 22 7 -9 8 ^
-1C 7 0 11 1 22 7 5 17 ^
2、一元多项式相加
1、单链表的结点定义
80北京邮电大学自动化学院
设 p,q分别指向 A,B中某一结点,p,q初值是第一结点
比较
p->exp
与
q->exp
p->exp < q->exp,p结点是和多项式中的一项,
p后移,q不动
p->exp > q->exp,q结点是和多项式中的一项,
将 q插在 p之前, q后移, p不动
p->exp = q->exp:系数相加
0：从 A表中删去 p,释放
p,q,p,q后移
?0：修改 p系数域,
释放 q,p,q后移
直到 p或 q为 NULL
若 q==NULL,结束
若 p==NULL,将 B中剩余部分连到 A上即可
（ 1）运算规则
81北京邮电大学自动化学院
q
-1pa 7 0 3 1 9 8 5 17 ^
-1pb 8 1 22 7 -9 8 ^
ppre
-
- -
ppre
q
-1pa 7 0 11 1 9 8 5 17 ^
-1pb 8 1 22 7 -9 8 ^
p
preq
11 1
ppre
q=NULL
p
-1pa 7 0 11 1 22 7 5 17 ^
（ 2）算法描述
82北京邮电大学自动化学院
第二章学习要点
?1、深入掌握线性表的逻辑结构及相关概念；
?2、深入掌握线性表的两种存储结构。采用顺序存
储方法来表示线性关系，得到顺序表；采用链式存
储方式来表示线性关系，得到线性表。体会这两种
存储方式之间的差异及各自的优缺点。
?3、深入顺序表上各种基本运算的实现过程；
?4、深入掌握链表上各种基本运算的实现过程；
?5、灵活运用顺序表和链表的特点解决复杂的应用
问题。
83北京邮电大学自动化学院
第二章 习题
? 一、填空题
? 1、向一个长度为 n的顺序表中的第 i个元素（ 0≤i≤n-1）之前
插入一个元素时，需向后移动 n-i+1 个元素。
? 2、在单链表中，要删除某一指定的结点，必须找到该结点
的 直接前驱 结点。
? 3、访问单链表中的结点，必须沿着 指针 一次进行。
? 4、在一个单链表中 p所指结点之后插入一个 s所指结点时，
应执行 s->next= p->next 和 p->next= S 的操作。
84北京邮电大学自动化学院
第二章 习题
? 二、选择题
? 1、链表不具备的特点是 (1) 。
? ①可随机访问任一节点 ②插入删除不须要移动元素
? ③不必事先估计存储空间 ④所需空间与其长度成正比
? 2、带头结点的单链表 head为空的判定条件是 (2) 。
? ① head==NULL ② head->next==NULL
? ③ head->next==head ④ head!=NULL
? 3、如果最常用的操作是取第 i个结点及其前驱，则采用 (4)
存储方式最节省时间。
? ①单链表 ②双链表 ③单循环链表 ④顺序表
85北京邮电大学自动化学院
?1、单链表操作
?（ 1）建立带表头结点的单链表 h；
?（ 2）打印单链表 h中所有结点的数据域值；
?（ 3）输入 x,y。在第 1个结点 x后插入 y，若无结
点 x，则在表尾插入结点 y；
?（ 4）输入 k，删除单链表中所有值为 k的结点，并
输出被删除结点个数。
?作业：到院机房检查程序，时间另行通知。
第二章上机作业
86北京邮电大学自动化学院
第 2章 上机时间及地点
班 级 时 间 地 点 老 师
0215301～ 302 10.18日 (周一）
14:00~16:00
4－ 328 张志霞
03501~502 10.19日 (周二）
14:00~16:00
4－ 327
4－ 328
杜伟
03503~504 10.19日 (周二）
14:00~16:00
4－ 327
4－ 328
李维成
03507～ 09 10.20日 (周三）
14:00~17:00
4－ 328 王松月
? 线性结构的特点,在数据元素中的非空有限集中
? （ 1）存在 唯一 的一个被称作,第一”的数据元素；
? （ 2）存在 唯一 的一个被称作,最后一个”的数据元
素；
? （ 3） 除第一个外,集合中的每一个数据元素均 只有
一个前驱；
? （ 4） 除最后一个外,集合中的每一个数据元素均 只
有一个后继。
第二章 线性表
2北京邮电大学自动化学院
? 1、线性表
? 线性表 (Linear List), 一个线性表是 n个数据元素的
有限序列。例如：
? 例 1,26个英文字母组成的字母表
?（ A,B,C,…, Z）
? 例 2、某校从 1999年到 2003年各种型号的计算机拥
有量的变化情况。
?（ 6,17,28,50,92,188）
2.1 线性表的类型定义
3北京邮电大学自动化学院
? 在稍复杂的线性表中，一个数据元素可以由若干个数据项组
成。在这种情况下，常把 数据元素称为记录, 含有大量记录的
线性表又称为文件。
? 例 3、学生健康情况登记表如下：
姓 名 学 号 性 别 年龄 健康情况
王小林 790631 男 18 健康
陈 红 790632 女 20 一般
刘建平 790633 男 21 健康
张立立 790634 男 17 神经衰弱
…….,…….,……,……,…….
1、线性表
4北京邮电大学自动化学院
? 综合上述三个例子可见，线性表中的数据元素可以是各种各样
的，但同一线性表中的元素必定具有相同特征，即属同一数据
对象，相邻数据元素之间存在着序偶关系。若将线性表记为：
? (a1,…,a i-1,ai,a i+1…,a n)
? 则表中 ai-1领先于 ai,ai领先于 a i+1,称 ai-1是 ai的 直接前驱元
素, ai+1是 ai的 直接后继元素 。
? 当 i=1,2,…,n -1时,ai有且仅有一个直接后继，当 i=2,3,…,n
时,ai有且仅有一个直接前驱。
? 线性表中的元素的个数 n(n ? 0)定义为线性表的长度,n=0时
称为空表。
1、线性表
5北京邮电大学自动化学院
? ADT List{
? 数据对象,={ai|ai?ElemSet,i=1,2,…,n,n ?0}
? 数据关系,R1={<ai-1,ai>| ai-1,ai,?D,i=2,…,n}
? 基本操作：
? InitList(&L)
? 操作结果,构造一个空的线性表 L。
2、抽象数据类型线性表
? DestroyList(&L)
? 初始条件,线性表 L已经存在。
? 操作结果,销毁线性表 L。
6北京邮电大学自动化学院
? ClearList(&L)
? 初始条件,线性表 L已经存在。
? 操作结果,将 L置为空表。
2、抽象数据类型线性表
? ListEmpty(L)
? 初始条件,线性表 L已经存在。
? 操作结果,若 L为空表，则返回 TRUE，否则返回
FALSE。
7北京邮电大学自动化学院
? ListLength(L)
? 初始条件,线性表 L已经存在。
? 操作结果,返回 L中数据元素个数。
2、抽象数据类型线性表
? GetElem(L,i,&e)
? 初始条件,线性表 L已经存在,?i?Listlength(L)。
? 操作结果,用 e返回 L中第 i个数据元素的值。
? LocateElem(L,e,compare())
? 初始条件,线性表 L已经存在,compare是数据元素判定函数。
? 操作结果,返回 L中第一个与 e满足关系 compare()的数据元素的
位序。若这样的元素不存在，则返回值为零为。
8北京邮电大学自动化学院
2、抽象数据类型线性表
? ListInsert(&L,i,e)
? 初始条件,线性表 L已经存在，且 1?i ? Listlength(L)＋ 1。
? 操作结果,在 L中第 i个位置之前插入新的数据元素 e,L的长度加 1
? Listdelte(&L,i,&e)
? 初始条件,线性表 L已经存在且非空，且 1?i ? Listlength(L)。
? 操作结果,删除 L中的第 i个数据元素，并用 e返回其值,L的长度
减 1。
? … …
? } ADT List
9北京邮电大学自动化学院
? 例 2-1 利用两个线性表 LA和 LB分别表示两个集合 A和 B，现要
求一个新的集合 A=A∪ B。只要从线性表 LB中依次取得每个数
据元素，并依值在线性表 LA中进行查访，若不存在，则插入。
? 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);//取 Lb 中的第个 i元素赋给 e
? if(!LocateElem(La,e,equal)) Listinsert(La,++La-en,e);
? //La中不存在和 e相同的数据元素，则插入
? } }//union
3、例题
10北京邮电大学自动化学院
? 例 2-2 巳知线性表 LA和线性表 LB中的数据元素按值非递减有序
排列，现要求将 LA和 LB归并为一个新的线性表 LC，且 LC中的
元素仍按值非递减有序排列。
? 例 LA=（ 3,5,8,11）,LB=（ 2,6,8,9,11,15,20）
? 则 LC=（ 2,3,5,6,8,8,9,11,11,15,20）
??
?
?
??
时，当
时当
bab
baac,
3、例题
? 从上面的问题要求可知,LC中的数据元素或是 LA中的数据元
素，或是 LB中的数据元素，则只要先设 LC为空表，然后将 LA或
LB中的元素逐个插入到 LC中即可。设两个指针 i和 j分别指向 LA
和 LB中某个元素，设 i当前所指的元素为 a,j当前所指的元素为
b，则当前应插入到 LC中的元素 c为
11北京邮电大学自动化学院
? 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)) {//La和 Lb均非空
? GetElem(La,i,ai); GetElem(Lb,j,bj);
? if(ai<=bj){ListInsert(Lc,++k,ai);++i;}
? else{ListInsert(Lc,++k,bj);++j;} }
? while(i<=La-len){
? GetElem((La,i++,ai); ListInsert(Lc,++k,ai); }
? while(j<=Lb-len){
? GetElem((Lb,j++,bj);ListInsert(Lc,++k,bj); }}//MergeList
12北京邮电大学自动化学院
? 上述两个算法的时间复杂度取决于抽象数据类型 list定义中基本
操作的执行时间。假如 GetElem和 ListInsert这两个操作的执行
时间和表长无关,LocateElem的执行时间和表长成正比。
4、算法的存储空间需求
? 则算法 2.1的时间复杂度为
?O（ ListLength(LA)?ListLength(LB),
? 算法 2.2的时间复杂度则为
?O（ List Length(LA)+ListLength(LB)。
? 虽然算法 2.2中含有三个（ While）循环语句，但只有当 i和 j均指
向表中实际存在的数据元素时，才能取得数据元素的值并进行相
互比较；并且当其中一个线性表的数据元素均已插入到线性表
LC中后，只要将另外一个线性表中的剩余元素依次插入即可。
13北京邮电大学自动化学院
? 一,线性表的顺序表示 线性表的顺序表示指的是用一组地址
连续的存储单元依次存储线性表的数据元素。
2.2 线性表的顺序存储结构
? 假设线性表的每个元素需占用 l个存储单元，并以所占的第一个
单元的存储地址作为数据元素的存储位置。则线性表中第 i+1个
数据元素的存储位置 LOC( a i+1)和第 i个数据元素的存储位置
LOC(ai )之间满足下列关系：
?LOC(a i+1)=LOC(ai)+l
? 一般来说，线性表的第 i个数据元素 ai的存储位置为：
?LOC(ai)=LOC(a1)+(i-1)*l
? 若每个数据元素占用 m个存储单元，则第 i个数据元素 ai的存储位
置为,LOC(ai)=LOC(a1)+(i-1)*m
14北京邮电大学自动化学院
? 线性表的这种机内表示称作 线性表的顺序存储结构, 称
这种存储结构的线性表为顺序表。
一,线性表的顺序表示
? 顺序存储的结构特点,以数据元素在计算机“物理位置
相邻”来表示表中数据元素间的逻辑关系。 对于这种存
储方式，要访问第 i个数据元素，就可以直接计算出 ai的
存储位置 Loc(ai)。因而能随机存取表中任一数据元素，
换言之,数据元素在顺序表中的存储位置取决于该数据
元素在线性表中的顺序号 。
? 例如：一个班学生，集体出游，按学号分配房
间。。。。。
15北京邮电大学自动化学院
? 由于 C语言中的一维数组也是采用顺序存储表示，故可以用数组
类型来描述顺序表。又因为除了用数组来存储线性表的元素之
外，顺序表还应该用一个变量来表示线性表的长度属性，所以我
们用结构类型来定义顺序表类型。
一,线性表的顺序表示
? # define LIST-INIT-SIZE 100 //线性表初始分配量
? # define LISTINCREMENT 10 //线性表分配增量
? typedef struc{
? Elemtype *elem //存储空间基址
? int length ;//当前长度
? int ListSize; } Sqlist;
16北京邮电大学自动化学院
? 在顺序表存储结构中，很容易实现线性表的一些操作，如线
性表的构造、第 i个元素的访问。
? 注意,C语言中的数组下标从,0”开始，因此，若 L是
Sqlist类型的顺序表，则表中第 i个元素是 L.data[i-1]。
二、顺序表上实现的基本操作
? 顺序表上基本运算
? 1,顺序表的初始化
? 2,插入运算
? 3,删除运算
? 4,按值查找
17北京邮电大学自动化学院
? 线性表的插入 是指在表的第 i个位置上插入一个值为 x 的新元
素，插入后使原表长为 n的表,
? (a1,a2,..., ai-1,ai,ai+1,..., an)
? 成为表长为 n+1 表,
? (a1,a2,...,ai-1,x,ai,ai+1,...,an ) 。 1<=i<=n+1 。
1、插入
? 顺序表上完成这一运算需要通过以下步骤进行：
? 1）将 ai～ an 顺序向下移动，为新元素让出位置；
? 2）将 x 置入空出的第 i个位置；
? 3）修改 last 指针 (相当修改表长 )，使之仍指向最后一个元素。
18北京邮电大学自动化学院
内存
a1
a2
ai
ai+1
an
0
1
i-1
V数组下标
n-1
i
n
1
2
i
元素序号
i+1
n
n+1
内存
a1
a2
ai
ai+1
an
0
1
i-1
V数组下标
n-1
i
n
1
2
i
元素序号
i+1
n
n+1
an-1
x
19北京邮电大学自动化学院
? Status ListInsert_Sq(SqList &L,int i,ElemType e)
? {if(i<1 || i>L.length+1) return ERROR //i值不合法
? 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;} // 增加存储容量 }
算法 2.3
20北京邮电大学自动化学院
?q=&(L.elem[i-1]); //q为插入位置
算法 2.3
? for(p=&(L,elem [L.length-1]);p>=q;--p)
*(p+1)=*p;
? //插入位置及之后的元素后移
? *q=e; //插入 e
? ++L.length; //表长增 1
? return OK;} //IistInsert_Sq
21北京邮电大学自动化学院
? 这里的问题规模是表的长度，设它的值为 n。 该算法的时间
主要花费在循环的结点后移语句上,由此可看出，所需移动
结点的次数不仅依赖于 表的长度，而且还与插入位置有关 。
算法的复杂度
? 当 i=n时，由于循环变量的终值大于初值，结点后移语句将
不进行；这是最好情况，其时间复杂度 O（ 1）；
? 当 i=1时，结点后移语句将循环执行 n次，需移动表中所有
结点，这是最坏情况，其时间复杂度为 O（ n）。
? 由于插入可能在表中任何位置上进行，因此需分析算法的
平均复杂度。
22北京邮电大学自动化学院
? 在长度为 n的线性表中第 i个位置上插入一个结点，令 Eis(n)表
示移动结点的期望值（即移动的平均次数），则在第 i个位置
上插入一个结点的移动次数为 n-i+1。故
1)i-(np ( n )E
1n
1i
iis ?
?
?
??
2)1(1
1 1
1
nin
nE
n
iis
????? ??
?
? 也就是说,在顺序表上做插入运算，平均要移动表上一半结
点。 当表长 n较大时，算法的效率相当低。虽然 Eis(n)中 n的
系数较小，但就数量级而言，它仍然是线性阶的。因此算法
的平均时间复杂度为 O(n)。
? 不失一般性，假设在表中任何位置 (1≦ i≦ n+1)上插入结点的
机会是均等的，则 p1=p2=p3=…=p n+1=1/(n+1)
? 因此，在等概率插入的情况下，
算法的复杂度
23北京邮电大学自动化学院
? 线性表的删除运算是指将表的第 i(1≦ i≦ n)结点删除，使长度
为 n的线性表：
? (a1,…a i-1,ai,a i+1…, an)
2、删除
? 变成长度为 n-1的线性表
? (a1,…a i-1,a i+1,…, an)
? 顺序表上完成这一运算的步骤如下：
?（ 1） 将 ai+1～ an 顺序向前移动。
?（ 2） 修改 last指针 (相当于修改表长 )使之仍指向最后
一个元素。
24北京邮电大学自动化学院
内存
a1
a2
ai
ai+1
an
0
1
i-1
V数组下标
n-1
i
n
1
2
i
元素序号
i+1
n
n+1
内存
a1
a2
ai+1
V数组下标
0
1
i-1
n-2
i
n-1
1
2
i
元素序号
i+1
n-1
n
an
ai+2
25北京邮电大学自动化学院
? Status ListDelete_Sq(SqList &L,int i,ElemType e) {
? if((i<1 || i>L.length) return ERROR; //i值不合法
? p=&(L.elem[i-1]); //p为被删除元素位置
? e = *p; //被删除元素值赋给 e
? q=L.elem+L.length-1; //表尾元素位置
算法 2.4
? For (++p; p<=q; ++p)*(p-1)=*p;
? //被删除元素之后的元素左移
? --L.length; //表长减 1
? return OK; } //IistDelete_Sq
26北京邮电大学自动化学院
? 该算法的时间分析与插入算法相似，结点的移动次数也是由表
长 n和位置 i决定。
4、算法的存储空间需求
? 假设 qi是删除第 i个元素的概率，则在长度为 n的线性表中删除
一个元素时所需移动元素次数的期望值（平均次数）为：
? 不失一般性，假设在表中任何位置上删除结点的机会是均等
的，则 qi=1/n
? 因此，在等概率插入的情况下，
? 也就是说,在顺序表上做删除运算，平均要移动表中约一半的
结点，平均时间复杂度也是 O(n)。
?
?
??
n
i
idl inqE
1
)(
?
?
???? n
i
dl
nin
nE 1 2
1)(1
27北京邮电大学自动化学院
? 线性表的顺序表示的特点是用 物理位置上的邻接关系来表示结点
间的逻辑关系,这一特点使我们可以随机存取表中的任一结点，
但它也使得 插入和删除操作会移动大量的数据元素。
2.3 线性表的链式表示和实现
? 由于顺序表需要一组地址连续的存储单元，对于长度可变的线性
表就需要预分配足够的空间，有可能使一部分存储空间长期闲置
不能充分利用。
? 也可能由于估计不足，当表长超过预分配的空间而造成溢出，在
这种情况下，又难于扩充连续的存储空间。
? 为了克服上述缺点，我们将谈论线性表的另一种存储方式链式存
储结构，简称为 链表 (Linked List)。
28北京邮电大学自动化学院
? 线性表的链式存储的特点 是指用 一组任意的存储单元 来依次
存放线性表的结点，这组存储单元既可以是连续的，也可以
是不连续的，甚至是零散分布在内存中的任意位置上的。因
此,链表中结点的逻辑次序和物理次序不一定相同。
data next
2.3.1 线性链表
? 为了能正确表示结点间的逻辑关系,在存储每个结点值的同
时，还必须存储指示其后继结点的地址（或位置）信息,这
个信息称为 指针 (pointer)或链 (next)。 这两部分信息组成了
元素 ai的存储映象，称为 结点,它包括两个域：
? 其中,data域是 数据域,用来存放结点的值。 next是 指针域
（亦称链域），用来存放结点的直接后继的地址（或位置）。
29北京邮电大学自动化学院
? 链表正是通过每个结点的链域将线性表的 n个结点按其逻辑次
序链接在一起的。
2.3.1 线性链表
? n个结点 ai( 1<=i<=n）连接成一个链表，即为线性表 (a1，
a2,…, an) 的链式存储结构。 由于上述链表的每一个结点只
有一个链域，故将这种链表称为单链表（ Single Linked)。
? 链表中每个结点的存储地址是存放在其前驱结点 next域中，而
开始结点无前驱,故应设头指针 head指向开始结点。同时，由
于终端结点无后继，故终端结点的指针域为空，即 NULL（图
示中也可用 ^表示 )
? 通常把线性链表画成用箭头相连接的节点序列，其中箭头表示
链域中的指针。
h a2 a3 an ^…...a1
30北京邮电大学自动化学院
赵 钱 孙 李
周 吴 郑 王 ^
H
例 线性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)
43
13
1
NULL
37
7
19
25
数据域 指针域
李
钱
孙
王
吴
赵
郑
周
存储地址
1
7
13
19
25
31
37
4331
H
头指针
31北京邮电大学自动化学院
2.3.1 线性链表
? 由上述可见，单链表可由头指针唯一确定，在 C语言中可用
“结构指针”来描述：
? typedef struct Listnode
{
? Elemtype data;
? struct Listnode *next;
? } Listnode,*Linklist,JD;
? Elemtype 为数据域的类型，
可以是任何类型。
? Data为数据域，存放该结点
的数据 ;
? next为指针域，指向该结点
的直接后继结点。
? 线性表的单链表存储结构
32北京邮电大学自动化学院
? 假设 L为 LinkList型的变量，则 L为单链表的头指针，它指向表
中第一个结点。
L 空表^
? 有时，我们在单链表的第一个结点之前附设一个结点，称之为
头结点 。 头结点 的数据可以不存储任何信息，也可以存储如线
性表的长度等类的附加信息，头结点的指针域存储指向第一个
结的指针。
? 若 L为“空”（ L=NULL），则所表示的线性表为“空”表，
其长度 n为“零”。
2.3.1 线性链表
L a1 a2
头结点
an ^…...
33北京邮电大学自动化学院
data next
p 结点（ *p）
2.3.1 线性链表
? （ *p）表示由指针所指向的节点。
? (*p).data?p->data表示 p指向结点的数据域
? (*p).next?p->next表示 p指向结点的指针域
? 指针变量 p（其值为结点地址）和结点变量 *p之间的关系。
h 1145 1248 2158 ^…...1012
? h->data=1012 (h->next)->data=1145
? p结点是指指针 p所指向的结点（即其存储位置存放在 p中的
结点）。,.”是成员（分量）运算符，“－ >”指向运算符。
? (*h).data=1012
34北京邮电大学自动化学院
?假设 p是指向线性表中第 i个数据元素（结点 ai）的
指针，则 p->next是指向第 i+1个数据元素（结点
ai+1）的指针。
? 换句话说，若 p->data=ai，
2.3.1 线性链表
p ai ai+1 ai+2
则 p->next->data=ai+1
? 由此，在单链表中，取得第 i个数据元素必须从头
指针出发寻找，因此,单链表是非随机存取的存储
结构。
35北京邮电大学自动化学院
?假设线性表中结点的数据类型是字符，我们逐个输
入这些字符型的结点，并以换行符‘ \n’为输入结束
标记。
一、建立单链表
? 动态地建立单链表的常用方法有如下两种：
? 1、头插法建表
? 该方法从一个空表开始，重复读入数据，生成新
结点，将读入数据存放到新结点的数据域中，然
后将新结点插入到当前链表的表头上，直到读入
结束标志为止。
36北京邮电大学自动化学院
? linklist createlistf(void)
? { char ch; linklist head; listnode *p;
? head=null; ch=getchar( );
? while (ch!=‵ \n′） {
? p=(Listnode*)malloc(sizeof(Listnode));
1、头插法建表
? p–>data=ch;
? p–>next=head; head=p;
?ch=getchar( ); }
? return (head); }
37北京邮电大学自动化学院
? listlink createlist ( int n)
? { int data; linklist head; listnode *p; head=null;
? for(i=n;i>0;--i){
? p=(listnode*)malloc(sizeof(listnode));
1、头插法建表
?scanf((〝 %d〞, &p–>data);
? p–>next=head;
? head=p;
?} return(head); }
38北京邮电大学自动化学院
? 假设 p是 LinkList型的变量，则执行
? p=(listnode*)malloc(sizeof(listnode));
2.3.1 线性链表
? 因此单链表和顺序存储结构不同，它是一种 动态结构。 整个可用
存储空间可为多个链表共同享受，每个链表占用的空间不需要预
先划定，而是可以由系统应需求即时生成。
? 的作用是由系统生成一个 listnode型的结点，同时将该结点的起
始位置赋给指针变量 p。
? 一旦 p所指的结点变量不再需要了，又可通过标准函数 free(p) 释
放所指的结点变量空间。
39北京邮电大学自动化学院
?头插法建立链表虽然算法简单，但生成的链表中结
点的次序和输入的顺序相反。
2、尾插法建表
?若希望二者次序一致，可采用尾插法建表。该方法
是将 新结点插入到当前链表的表尾上,为此必须增
加一个尾指针 r，使其始终指向当前链表的尾结点。
例：
40北京邮电大学自动化学院
? linklist creater( ) { char ch; linklist head;
? listnode *p,*r; //(,*head;)
? head=NULL; r=NULL;
2、尾插法建表
? while((ch=getchar( )!=‵ \n′) {
? p=(listnode *)malloc(sizeof(listnode));
? p–>data=ch;
? if(head=NULL) head=p; else r–>next=p;
? r=p;
? } if (r!=NULL) r–>next=NULL; return(head); }
41北京邮电大学自动化学院
? 说明,第一个生成的结点是开始结点,将开始结点插入到空表
中，是在当前链表的第一个位置上插入，该位置上的插入操作
和链表中其它位置上的插入操作处理是不一样的，原因是 开始
结点的位置是存放在头指针（指针变量）中，而其余结点的位
置是在其前驱结点的指针域中。
2、尾插法建表
? 算法中的第一个 if语句就是用来对第一个位置上的插入操作做
特殊处理 。
? 算法中的第二个 if语句的作用是为了分别处理 空表和非空表 两
种不同的情况，若读入的第一个字符就是结束标志符，则链表
head是空表，尾指针 r亦为空，结点 *r不存在；否则链表 head
非空，最后一个尾结点 *r是终端结点，应将其指针域置空。
42北京邮电大学自动化学院
?如果我们在链表的开始结点之前附加一个结点，并
称它为头结点，那么会带来以下两个优点：
? a、由于开始结点的位置被存放在头结点的指针域
中，所以在链表的第一个位置上的操作就和在表的
其它位置上的操作一致，无需进行特殊处理；
? b、无论链表是否为空，其头指针是指向头结点
的非空指针（空表中头结点的指针域为空），因此
空表和非空表的处理也就统一了。
2、尾插法建表
43北京邮电大学自动化学院
? linklist createlistr1( ){ char ch;
? linklist head=(linklist)malloc(sizeof(listnode));
? listnode *p,*r; r=head;
2、尾插法建表
? while((ch=getchar( ))!=‵ \n′{
? p=(listnode*)malloc(sizeof(listnode));
? p–>data=ch; r–>next=p; r=p; }
? r–>next=NULL;
? return(head); }
44北京邮电大学自动化学院
?上述算法里动态申请新结点空间时未加错误处理，
可作下列处理：
? p=(listnode*)malloc(sizeof(listnode))
? if(p==NULL)
? error(〝 No space for node can be obtained〞 );
? return ERROR;
? 以上算法的时间复杂度均为 O(n)。
2、尾插法建表
45北京邮电大学自动化学院
?1、按序号查找
二、查找运算
? 在链表中，即使知道被访问结点的序号 i，也不能象顺
序表中那样直接按序号 i访问结点，而只能从链表的头
指针出发，顺链域 next逐个结点往下搜索，直到搜索到
第 i个结点为止。因此,链表不是随机存取结构。
? 设单链表的长度为 n，要查找表中第 i个结点，仅当
1≦ i≦ n时,i的值是合法的。但有时需要找头结点的位
置，故我们将头结点看做是第 0 个结点，其算法如下：
46北京邮电大学自动化学院
? Listnode * getnode(linklist head, int i)
? { int j; listnode * p; p=head; j=0;
1、按序号查找
? while(p–>next && j<i)
? { p=p–>next; j++;
? }
? if (i==j) return p;
? else
? return NULL; }
47北京邮电大学自动化学院
?按值查找是在链表中，查找是否有结点值等于给
定值 key的结点，若有的话，则返回首次找到的
其值为 key的结点的存储位置；否则返回 NULL。
2、按值查找
? 查找过程从开始结点出发，顺着链表逐个将结点
的值和给定值 key作比较。
48北京邮电大学自动化学院
? 其算法如下：
? Listnode * locatenode(linklist head,int key) {
? listnode *p=head–>next;
2、按值查找
? while( p && p–>data!=key)
? p=p–>next;
? return p; }
? 该算法的执行时间亦与输入实例中的的取值 key有关，其平
均时间复杂度的分析类似于按序号查找，也为 O(n)。
49北京邮电大学自动化学院
? 插入运算是将值为 x的新结点插入到表的第 i个结点的位置
上，即插入到 ai-1与 ai之间。
p ai-1 ai
xs
s->next=p->next;p->next=s;
三、插入运算
? 然后，新结点的指针域指向结点 ai，
? 最后,p结点的指针域指向新结点 s，
? 从而实现三个结点 ai-1,x和 ai之间的逻辑关系的变化。
? 必须首先找到 ai-1的存储位置 p，然后生成一个数据域为 x的新
结点 *s，并令结点 *s的指针域指向新结点，
50北京邮电大学自动化学院
? void insertnode(linklist head,datetype x,int i) {
? listnode * p,*q;
? p=getnode(head,i-1);
? if(p==NULL)
? error(〝 position error〞 );
? s=(listnode *)malloc(sizeof(listnode));
p ai-1 ai
xs
s->next=p->next;
p->next=s;
插入运算具体算法
? s–>data=x;
? s–>next=p–next;
? p–>next=s; }
51北京邮电大学自动化学院
?设链表的长度为 n，合法的插入位置是
1≦ i≦ n+1。
?注意当 i=1时,getnode找到的是头结点，
?当 i=n+1时,getnode找到的是结点 an。
?因此，用 i-1做实参调用 getnode时可完成插入位置
的合法性检查。算法的时间主要耗费在查找操作
getnode上，故时间复杂度亦为 O(n)。
插入运算具体算法
52北京邮电大学自动化学院
?删除运算 是将表的第 i个结点删去。因为在单链表中结
点 ai的存储地址是在其直接前驱结点 a i-1的指针域
next中，
p ai-1 ai ai+1
p->next=p->next->next;
四、删除运算
? 所以我们必须首先找到 a i-1的存储位置 p。
? 然后令 p–>next指向 ai的直接后继结点，即把 ai从链上
摘下。最后释放结点 ai的空间，将其归还给“存储
池”。
53北京邮电大学自动化学院
? void deletelist(linklist head,int i) {
? listnode * p,*r;
? p=getnode(head,i-1);
删除运算算法
? if(p= =NULL || p–>next= =NULL)
? return ERROR;
? r=p–>next;
? p–>next=r–>next;
? free( r ) ; }
54北京邮电大学自动化学院
? 设单链表的长度为 n，则删去第 i个结点仅当 1≦ i≦ n时是合法
的。注意，当 i=n+1时，虽然被删结点不存在，但其前驱结
点却存在，它是终端结点。 因此被删结点的直接前驱 *p存在
并不意味着被删结点就一定存在，仅当 *p存在（即
p!=NULL）且 *p不是终端结点。
删除运算算法
? （即 p–>next!=NULL）时，才能确定被删结点存在
? 显然此算法的时间复杂度也是 O(n)。
? 从上面的讨论可以看出，链表上实现插入和删除运算，无须
移动结点，仅需修改指针。
55北京邮电大学自动化学院
?1、在头指针为 h的带表头结点的单链表中，把结
点 b插入到 a结点之前，若不存在结点 a就把结点 b
插入到表尾。
五、链表的其他运算示例
? 插入过程：
? 找到结点 a时,p指向结点,q指向结点 a的直接
前驱结点。
? 首先生成一个 s结点，将 s结点的数据域置为
b，然后修改相应的指针，把结点 a作为 s结点
的直接后继，把 s结点作为 q结点的直接后继。
56北京邮电大学自动化学院
? Void dlbqcr(JD *h,int a,int b) {//在头指针为 h的带表头结点的单链表中结点 a
之前插入结点 b，若表中无结点 a，则插到表尾
? JD*p,*q,*s;
例题 1算法
? s=(JD*)malloc(sizeof(JD));
? s->data=b;
? p=h->link;q=h;
? While(p->data!=a&&p->link!=NULL)
? {q=p;p=p->link;}//查找结点 a
? If(p->data==a;)
? { s->link=p; q->link=s;}//找到结点时，把结点插到结点 a之前
? Else{p->link=s;s->link=NULL;}//表中无结点 a，则插到表尾 }
q ai-1 ai
xs
s->next=p
q->next=s;
57北京邮电大学自动化学院
? 2、设线性表的 n个数据元素依次存放在一维数组 a[n]中，请建立
一个带表头结点的单链表,h为新建单链表的指针。
? 要建立一个带 表头结点的单链表,首先生成一个 h结点作为表结
点，其链域置为“空”。
? 在生成一个 s结点，将其数据域置为第 n个数据元素，链域置
为“空”。 s结点作为表中第一个结点。
? 顺次生成新的 s结点，置其数据域为第 i个数据元素 (i=n-1,n-
2,…,2,1),修改有关指针：把表中第一个结点作为 s结点的直接
后继,s结点作为表中第一个结点。即把含第 i个数据元素的结点
插入到表中第一个结点之前。
2、例题 2
58北京邮电大学自动化学院
? JD*DLBJL(INT A[],INTN)
? {//线性表中的 n个数据元素
存入一维数组 a中，建立一
个带表头结点的单链表，其
头指针为 h
? JD *S,*h; Int i;
? h=(JD*)malloc(sizeof(JD));
? h->data=0;h->link=NULL;
? For(i=n;i>0;i--)
?
{s=(JD*)mallic(sizeof(JD));
? s->data=a[i-1];
? s->link=h->link;
? h->link=s;}
? return(h);}
例题 2算法
59北京邮电大学自动化学院
?3、设 h是带表头结点的单链表的头指针，请设计一
个逆置这个单链表的算法。
3、例题 3
?建立逆表的方法是,顺序扫描原表,依次将原表中
的结点逐个插入到第一个结点之前,可得到逆置链
表。
?设 s指向当前逆转结点,p指向 s结点的直接后继结
点。
60北京邮电大学自动化学院
?Void dlbnz(JD*h){ JD*s,*p;
? p=h->link;// *p先指向原表中第一个结点
? h->link=NULL;//逆表的初态为空表
例题 3算法
? While(p!=NULL)
? {s=p;// *s指向当前逆转的结点
? p=p->link;
? s->link=h->link ;
? h->link=s;//把 s结点插入到逆表 }}
61北京邮电大学自动化学院
? 4、设 pa,pb分别为两个按升序排列的单链表的头指针，请设
计一个算法把这两个单链表合并为一个按升序排列的单链表。
4、例题 4
? 合并的方法是：从两表的第一个结点开始顺链逐个将对应数据
元素进行比较，复制小者并插入 c表尾。当两表中之一已到表
尾，则复制另一链表的剩余部分，插入到 c表尾。
? /JD*dlnhb(JD *pa,JD*pb);
? {//把 pa,pb为头指针的按升序排列的单链表合并成一个按升序
排列的单链表。 P指向 c表的当前表尾。
? JD *p,*q;*pc;
? pc=(JD)malloc(sizeof(JD)); p=pc;
62北京邮电大学自动化学院
? While(pa!=NULL && pb!=NULL){
? q=(JD* )malloc (sizeof(JD));
例题 4算法
? Else { q->data=pa->data; pa=pa->link;
? If (pb->data<pa->data)
? {q->data=pb->data; pb=pb->link;}
? If (pa->data==pb->data) pb=pb->link； }
? p->link=q;
? p=q;}
63北京邮电大学自动化学院
?While(pa!=NULL)
?{ q=(JD*)malloc(sizeof(JD));
? q->data=pa->data;
? pa=pa->link;
例题 4算法
? p->link=q;
? p=q;
? }
64北京邮电大学自动化学院
?While(pb!=NULL)
?{ q=(JD*)malloc(sizeof(JD));
例题 4算法
?q->data=pb->data; pb=pb->link;
?p->link=q; p=q;}
?p->link=NULL
?p=pc; pc=p->link; free(p)
?return(pc);}
65北京邮电大学自动化学院
? 循环链表 是一种头尾相接的链表。其特点是无须增加存储
量，仅对表的链接方式稍作改变，即可使得表处理更加方便
灵活。
2.3.2 循环链表
? 单循环链表,在单链表中，将终端结点的指针域 NULL改为
指向表头结点或开始结点，就得到了单链形式的循环链表，
并简单称为 单循环链表。
? 为了使空表和非空表的处理一致，循环链表中也可设置一个
头结点。这样，空循环链表仅有一个自成循环的头结点表
示。如下图所示：
66北京邮电大学自动化学院
h
⑴ 非空表
h
⑵ 空表
? 在用头指针表示的单链表中，找开始结点 a1的时间是 O(1)，
然而要找到终端结点 an，则需从头指针开始遍历整个链
表，其时间是 O(n)。
2.3.2 循环链表
67北京邮电大学自动化学院
? 在很多实际问题中，表的操作常常是在表的首尾位置上进
行，此时头指针表示的单循环链表就显得不够方便。
? 由于循环链表中没有 NULL指针，故涉及遍历操作时，其终
止条件就不再像非循环链表那样判断 p或 p—>next是否为
空,而是判断它们是否等于某一指定指针，如头指针或尾指
针等。
2.3.2 循环链表
? 如果改用尾指针 rear来表示单循环链表，则查找开始结点 a1
和终端结点 an都很方便，它们的存储位置分别是 (rear–
>next) —>next和 rear,显然，查找时间都是 O(1)。因此，
实际中多采用尾指针表示单循环链表。
68北京邮电大学自动化学院
? 例如、在链表上实现将两个线性表 (a1,a2,a3,…a n)和
(b1,b2,b3,…b n)链接成一个线性表的运算。
? JD * xhblj(JD *ha,JD *hb); {//ha,hb为两个带 头结点 的循
环链表的尾指针，把 hb表连在 ha表之后
? JD *q,*p
? q=ha—>next; p=hb—>next;
2.3.2 循环链表
? ha—>next=p—>next; //a,b两个线性表 尾首相连
? hb—>next=q;// a,b两个线性表 首尾相连
? ha=hb; free(p);//释放 hb表头结点 }
69北京邮电大学自动化学院
?单链表有一个很大的缺点,它只能顺着直接后继指针向
后查找其他结点,如若找某结点的直接前驱结点，只能
从表头指针开始查找。换句话说，在单链表中，
NextElem的执行时间为 O(1)，而 PriorElem的执行时间
为 O（ n）。
2.3.3双链表
? 为了克服单链表这种单向性的缺点，双向链表可有效解
决这个问题。
? 双向链表 (Double linked list):在单链表的每个结点里
再增加一个指向其直接前驱的指针域 prior。这样形成
的链表中就有两个方向不同的链，故称为 双向链表。
70北京邮电大学自动化学院
? typedef struct node {
? datatype element;
? struct node *prior,*next;}JD;
prior element next
L空双向循环链表：
非空双向循环链表,L A B
b ca
p
p->prior->next= p= p->next->proir;
双向链表（ double linked list）结点定义
71北京邮电大学自动化学院
?和单链表类似，双链表一般也是由头指针唯一确定的，
增加头指针也能使双链表上的某些运算变得方便，将头
结点和尾结点链接起来也能构成循环链表，并称之为 双
向链表。
2.3.3双链表
? (p—>prior)—>next=p=(p—>next)—>prior
?即结点 *p的存储位置既存放在其前驱结点 *(p—>prior)
的直接后继指针域中，也存放在它的后继结点 *(p—
>next)的直接前驱指针域中。
? 设指针 p指向某一结点，则双向链表结构的对称性可用
下式描述：
72北京邮电大学自动化学院
?在双链表中，有些操作如,ListLength,GetElem
和 LocateElem等仅需要涉及一个方向的指针，则它
们的算法描述和线性链表的操作相同，但在插入和
删除操作时有很大的不同，在双链表中插入和删除
必须同时修改两个方向上的指针。上述两个算法的
时间复杂度均为 O(n)。
2.3.3双链表
73北京邮电大学自动化学院
xS
ba
P（ 1）插入
?void sxlbcr(JD*p,int x)
?{ JD *s;s=(JD *s) malloc (sizeof(JD)); s—>data=x;
?s—>prior=p->prior;//1步
?p->prior->next=s;//2步
?s—>next=p;//3步
?p—>prior=s; //4步 }
74北京邮电大学自动化学院
b ca
P
（ 2）删除
p->prior->next=p->next;
p->next->prior=p->prior;
?void ddeletenode(dlistnode *p)
? {p–>prior–>next=p–>next;
? p–>next–>prior=p–>prior;
? free(p); }
75北京邮电大学自动化学院
?从本节的讨论中可见：由于链表在空间的合理利用上
和插入、删除时不需要移动等优点，因此 在很多场合
下，它是线性表的首选存储结构。
?然而它也存在着实现某些基本操作如求线性表长度时
不如顺序存储结构的缺点；
?为此，从实际应用角度出发重新定义线性链表及其基
本操作（见 P37~38）。
?另一方面，由于在链表中，节点之间的关系用指针来
表示，则数据元素在线性表中的“位序”的概念已淡
化，而被数据元素在线性表链表中的“位置”所代
替。
76北京邮电大学自动化学院
nnn xPxPxPPxP ????? ??2210)(
? 多项式的运算问题，已经成为表处理的一个经典问题。通
常一个多项式 Pn(x)可按升密写成：
2.4一元多项式相加
),,,210 mqqqqQ ??（?
),,,210 nppppP ??（?
? 它由 n+1个系数唯一确定。在计算机里，它可用一个线性表 P
来表示：
? 每一项的指数 i隐含在其系数 pi的序号里。
? 假设 Qm(x)是一元 m次多项式，同样可用线性表 Q来表示：
? 假设 m<n,则两个多项式相加的结果 Rn(x)=Pn(x)+Qm(x)可用
线性表 R表示,
? 我们可以对 P,Q和 R采用顺序存储结构,使得多项式相加的算
法定义十分简洁。
),,,,,,11221100 nmmm ppqpqpqpqpR ?? ???????（
77北京邮电大学自动化学院
20 00 010 00 231)( xxxS ???
mee emn xPxPxPxP ???? ??21 21)(
为非零系数）（ im Peee ??? ??210
? 至此，一元多项式的表示及相加问题似乎已经解决。然而，在
通常的应用中，多项式的次数可能很高且变化很大，使得顺序
存储结构的最大长度很难确定。特别是在处理式的次数可能很
高且变化很大，使得顺序存储结构的最大长度很难确定。特别
是在处理形如：
2.4一元多项式相加
? 的多项式时，就要用一长度为 20001的线性表来表示，表中仅
有 3个非零元素，这种对内存空间浪费应当避免。
? 其中,pi是指数为 ei的项的非零系数，且满足：
? 但是如果只存储非零系数项，显然必须同时存储相应的指数。
一般情况下的一元 n次多项式可写成：
78北京邮电大学自动化学院
emmn xPxPxPxP ee ???? ??21 21)(
? ? ? ? ? ?? ?emPePeP m,，，，,??21 21
? 若用一个长度为 m且为每个数据元素有两个数据项（系数项和
指数项）的线性表
2.4一元多项式相加
? 便可唯一确定多项式 Pn(x)。在最坏情况下,n+1(=m)个系数都
不为零，则比只存储每项系数的方案要多一倍的数据。但是，
对于 S(x)类的多项式，这种表示将大大节省空间。
? 对应于线性表的两种存储结构，由上式定义的一元多项式也可
以有两种存储表示方法。在实际的应用程序中取用哪一种，则
要视多项式作何种运算而定。
? 若只对多项式进行“求值”等不改变多项式的系数和指数的运
算,则采用类似于顺序表的顺序存储结构即可,否则应采用链
式存储结构。 本节中将主要讨论如何利用线性链表的基本操作
来实现一元多项式的运算。
79北京邮电大学自动化学院
? typedef struct node
? { int coef,exp;
? struct node *next;}JD;
coef exp next
177
87
172
522117)()()(
9228)(
5937)(
xxxxBxAxC
xxxxB
xxxxA
??????
???
????
-1A 7 0 3 1 9 8 5 17 ^
-1B 8 1 22 7 -9 8 ^
-1C 7 0 11 1 22 7 5 17 ^
2、一元多项式相加
1、单链表的结点定义
80北京邮电大学自动化学院
设 p,q分别指向 A,B中某一结点,p,q初值是第一结点
比较
p->exp
与
q->exp
p->exp < q->exp,p结点是和多项式中的一项,
p后移,q不动
p->exp > q->exp,q结点是和多项式中的一项,
将 q插在 p之前, q后移, p不动
p->exp = q->exp:系数相加
0：从 A表中删去 p,释放
p,q,p,q后移
?0：修改 p系数域,
释放 q,p,q后移
直到 p或 q为 NULL
若 q==NULL,结束
若 p==NULL,将 B中剩余部分连到 A上即可
（ 1）运算规则
81北京邮电大学自动化学院
q
-1pa 7 0 3 1 9 8 5 17 ^
-1pb 8 1 22 7 -9 8 ^
ppre
-
- -
ppre
q
-1pa 7 0 11 1 9 8 5 17 ^
-1pb 8 1 22 7 -9 8 ^
p
preq
11 1
ppre
q=NULL
p
-1pa 7 0 11 1 22 7 5 17 ^
（ 2）算法描述
82北京邮电大学自动化学院
第二章学习要点
?1、深入掌握线性表的逻辑结构及相关概念；
?2、深入掌握线性表的两种存储结构。采用顺序存
储方法来表示线性关系，得到顺序表；采用链式存
储方式来表示线性关系，得到线性表。体会这两种
存储方式之间的差异及各自的优缺点。
?3、深入顺序表上各种基本运算的实现过程；
?4、深入掌握链表上各种基本运算的实现过程；
?5、灵活运用顺序表和链表的特点解决复杂的应用
问题。
83北京邮电大学自动化学院
第二章 习题
? 一、填空题
? 1、向一个长度为 n的顺序表中的第 i个元素（ 0≤i≤n-1）之前
插入一个元素时，需向后移动 n-i+1 个元素。
? 2、在单链表中，要删除某一指定的结点，必须找到该结点
的 直接前驱 结点。
? 3、访问单链表中的结点，必须沿着 指针 一次进行。
? 4、在一个单链表中 p所指结点之后插入一个 s所指结点时，
应执行 s->next= p->next 和 p->next= S 的操作。
84北京邮电大学自动化学院
第二章 习题
? 二、选择题
? 1、链表不具备的特点是 (1) 。
? ①可随机访问任一节点 ②插入删除不须要移动元素
? ③不必事先估计存储空间 ④所需空间与其长度成正比
? 2、带头结点的单链表 head为空的判定条件是 (2) 。
? ① head==NULL ② head->next==NULL
? ③ head->next==head ④ head!=NULL
? 3、如果最常用的操作是取第 i个结点及其前驱，则采用 (4)
存储方式最节省时间。
? ①单链表 ②双链表 ③单循环链表 ④顺序表
85北京邮电大学自动化学院
?1、单链表操作
?（ 1）建立带表头结点的单链表 h；
?（ 2）打印单链表 h中所有结点的数据域值；
?（ 3）输入 x,y。在第 1个结点 x后插入 y，若无结
点 x，则在表尾插入结点 y；
?（ 4）输入 k，删除单链表中所有值为 k的结点，并
输出被删除结点个数。
?作业：到院机房检查程序，时间另行通知。
第二章上机作业
86北京邮电大学自动化学院
第 2章 上机时间及地点
班 级 时 间 地 点 老 师
0215301～ 302 10.18日 (周一）
14:00~16:00
4－ 328 张志霞
03501~502 10.19日 (周二）
14:00~16:00
4－ 327
4－ 328
杜伟
03503~504 10.19日 (周二）
14:00~16:00
4－ 327
4－ 328
李维成
03507～ 09 10.20日 (周三）
14:00~17:00
4－ 328 王松月
