武汉理工大学华夏学院 -信息工程系第二章 线性表
2.1 线性表的类型定义定义：线性表是一个有 n（ n>=0） 个元素的有限序列，各元素具有相同的数据类型
（同一数据对象）。例如 (a,b,c,d,e) 与
（ 23,45,67,89,90,…,100 ） 都称为线性表。
(a,b,c,d,e)也称为串。
术语,表长：表中元素的个数，称为表的长度 。
空表：表中元素个数为零的表武汉理工大学华夏学院 -信息工程系
线性表的特点：表中元素存在着“序偶”关系，
即除首结点无前件，尾结点无后件以外的其余结点都有且仅有一个前件也有且仅有一个后件。
存储线性表的方法：顺序存储和链式存储；
线性表的基本操作
1,初始化（置空表）
2,求表长
3,取表中元素
4,定位
5,在表中插入新元素
6,删除表中某一个元素武汉理工大学华夏学院 -信息工程系
2.2 线性表的顺序表示和实现
2.2.1 定义 用顺序存储方法存储的表称为顺序表实现方法 用一维数组作为顺序表的存储区域。设线性表中的所有结点按前驱后继关系排成一个线性序列,(K1,K2,K3…… KN) 其中结点个数 N称为表的长度，当 N=0时的线性表称为空表。又设数组 V[N0]
(N<N0)用来依次存储线性表中的 N个元素,V[N+1]到
V[N0]是为插入新元素准备的空单元，如图 2-1所示：
下标 …
数组 V … …
1 2 3 4 N … N0
K1 K2 K3 K4 KN
图 2－ 1顺序表的存储结构示意 MAXSIZE
武汉理工大学华夏学院 -信息工程系
1） 节省存储空间；
2） 逻辑上相邻结点在物理次序上也相邻，其存储地址可以用计算公式表示为：
LOC(I)=LOC(1)+(I-1)*L
其中 I的是结点的逻辑序号即为第 I个结点 ；
LOC(1)为首结点的地址；
L为每一个结点占用的存储单元数
3）可以实现对结点的随机访问。
顺序存储的优点是,
不便于动态修改，即在对结点进行插入或删除操作时，要移动较多的结点。
顺序存储的缺点是：
武汉理工大学华夏学院 -信息工程系
2.2.2 顺序表的基本操作顺序表的类型定义,
#defile N0 100 /*用宏定义表的容量 */
Typedef struct
｛ char V[N0]； /*V为字符数组，元素值是字符 */
int len； /*表的当前长度 */
｝ SQLIST;
1.建表,定义一个数组 V及表长变量 N,输入数据。注意：每输入一个值，其表长要加 1。
武汉理工大学华夏学院 -信息工程系
2,定位操作 顺序表的定位操作非常简单，由于顺序表的逻辑顺序与存储顺序一致，则当 1<=I<=N时,V[I]就是顺序表中的第 I个元素。其算法流程是：
输入 K （ 被查值）
I=1
V[I]=K?
I=I+1
I<=N?
图 2－ 2 顺序表的定位操作查找到，输出 V[I],结束
K不是顺序表中的元素
2.2.2 顺序表的基本操作
＋
－
－
＋
思考：
查找第 I个结点的前驱和后继应如何实现？
分析：第 I个结点的位置，
若 I=1,表明是首结点；
若 I=N,表明是尾结点；
武汉理工大学华夏学院 -信息工程系在顺序表中插入一个元素时，由于顺序表中的元素是连续存放的，所以在插入前需要考虑以下几个问题：
3,插入操作其一，事先定义的存储区域（数组）是否还有空闲的单元，若有，则可以插入，否则，表明表已经满了；
其二，要确定插入位置 I,即在第 I个元素后面插入，
确定插入位置 I的方法有直接给出位置 I或者给出元素值，
去确定位置 I；
其三，插入方法是，若 I >= N 则直接将被插入的值送往 V[N+1]单元就可以了,若 I<N则表明数组元素 V[I+1]不是空单元，因此在插入新元素之前，要将顺序表中的
V[I+1]～ V[N]中的所有元素依次向后移动一个位置，空出数组元素 V[I+1],再将被插入的值送往 V[I+1]单元。
其四，插入一个元素后，应改变将顺序表的长度 N，
即将原来的 N加 1取代 N，其算法流程是：
武汉理工大学华夏学院 -信息工程系输入被插入值 K
和插入位置 I
I<=N
J=I+1
J=N
V[J+1]=V[J]
J=J-1
V[I+1]=K
N=N+1
返回
V[N+1]=K
表满返回图 2－ 3 顺序表的插入操作否否追加插入
N=N0
移动数据空出位置 改变表长插入武汉理工大学华夏学院 -信息工程系在顺序表中删除一个元素时，删除前需要考虑以下几个问题,
4,删除操作其一 已建成的顺序表是否为空，若是则表明该线性表中无结点，因此无元素删除，否则表明表中有结点；
其二，要确定被删结点的位置 I,即要删除第 I个元素，确定被删位置 I的方法有直接给出位置 I或者给出元素值，去确定位置 I；
其三，删除方法是，若 I=N则表明将要删除的是终端结点，因此直用 N=N-1就可以了，若 I<N则表明将要删除的是非终端结点，因此要将顺序表中的 V[I+1]～
V[N]中的所有元素依次向前移动一个位置就可以了。
其四，删除后，应修改顺序表的长度 N（ 即 N=N-1)。
其算法流程是：
武汉理工大学华夏学院 -信息工程系输入被删除值 K
的位置 I
J=I+1
V[J-1]=V[J]
J=J+1
表空返回
N=N-1
N=N-1
返回图 2－ 4 顺序表的删除操作删除最后一个结点
＋
－
改变表长
I=n
N＝ 0
N＝ j
武汉理工大学华夏学院 -信息工程系顺序表的插入和删除算法的执行时间主要用在元素的前后移动上,
（ 4）效率评价以插入为例：当 I=0时，（即在排首插入）则需要移动 N个元素，当 I=1时，则需要移动 N－ 1个元素，当 I=N-1
时，则需要移动 1个元素，设插入新元素在表中的各位置概率相等，则插入时，平均移动元素的次数是
M(I)=[(n-1)+(n-2)+…,.+(n-i)]/(n+1)=n/2
删除时，平均移动元素的次数是
M(D)= )=[(n-1)+(n-2)+…,.+(n-i)]/n=(n-1)/2
这说明，在顺序表上进行一次插入或删除平均需要移动一半的元素，这两个算法的执行时间的时间复杂度为 O(N)。
（ 5）应用举例：两个有序表合并武汉理工大学华夏学院 -信息工程系
（ 1） 链表的定义 用链接方法存储的线性表称为线性链表,简称链表。
（ 2） 表示方法 每一个结点的存储内容分成两个部分：
一部分用来存储结点的值，称为数值字段（又称数值域），一部分用来存储结点之间关系的，称为指针字段
（又称指针域）。
（ 3）链表的类型 按每个结点所含指针字段的个数，
分为,单链表和双链表两种。
2.3 线性表的链接存储结构及运算
2.3.1 链表和指针指针：存储其他结点位置信息的域称为指针域，指针域中存储的信息称为指针或链。
武汉理工大学华夏学院 -信息工程系
(1) 每个结点除数字字段外还包含一个指向后继结点的指针字段，用来存放后继结点的地址的链表。
(3) 单链表的结构：
通常，把链表画成用箭头相连接的结点序列，结点之间的箭头表示指针字段的值。用一个称为头指针的变量 HEAD存储开始结点（首结点）的地址，对于一个空的单链表则 HEAD的值为空。
2.3.2 单链表（单向链表）
定义结点形式,(2) 由两个字段组成，如下图所示。
数值字段 指针字段 data next
武汉理工大学华夏学院 -信息工程系
(5) 循环单链表 它是单链表的另外的一种形式，即在单链表的的尾结点的指针字段中存放着首结点的地址。见下图
(4)单链表的画法 见下图,
H
A B C Q…
H
A B C Q…
武汉理工大学华夏学院 -信息工程系
2.3.3 单链表的操作高级语言中对单链表的描述有两种方法,一种为利用数组类型构成 静态链表 ； 另一种是利用指针类型构成 动态链表 。这里重点介绍动态链表。对于动态链表，先做如下说明：
1.高级语言中对单链表的描述
§使用 C语言 时，类型说明为：
＃ define elemtype char
struct node{
elemtype data; /*数字字段 */
struct node *next; /*指针字段 */
}NODE,*NODEPTR;
# dedile LEN sizeof(NODE) /*定义结点长度 */
NODE *p,*q; /*定义指针变量 */
NODEPTR H; /*定义头指针变量 */
武汉理工大学华夏学院 -信息工程系功能,在链表中查找第 I个结点，若存在则返回结点的地址，否则给出不存在的信息。
2,定位操作方法,首先看表空否？
不空则从表头结点的地址开始查找，找到结束；
找不到再取下一个结点的地址，看其空否？
若空则给出不存在地信息，否则继续查找。
算法框图：见下图武汉理工大学华夏学院 -信息工程系输入被查值 X
返回
P=H
p=p.next
查找成功，输出 P
查找不成功，返回图 2－ 5 单链表定位操作算法框图表空否？
P.data=x
p= NULL
+
+
+
武汉理工大学华夏学院 -信息工程系
3,插入操作功能,在地址为 P的结点后面插入一个新结点，该新结点的值由 X给出。
操作步骤,首先检查给定地址 P是否正确；
若正确则可以插入插入结点的过程为：
（ 1）为新结点分配存储单元 Q
（ 2） 形成结点（把 X送入 Q的数值字段中）
（ 3）将 Q结点链接到链表中（把 P 结点的后件地址送入 Q的指针字段；再将 Q送入 P的后件的指针字段中）
武汉理工大学华夏学院 -信息工程系实现过程描述,见下图
P p.next
新结点 q
P q.next
q
x
武汉理工大学华夏学院 -信息工程系图 2-8 单链表插入操作 算法框图,
输入被插入的新结点的值 X
形成新结点地址 q
显示无法插入
q=(NODEPTR)malloc(LEN)
q.data=x
q.next=p.next
p.next=q
插入结束返回
P结点存在否？ 无
q=(NODE*)malloc(sizeof(NODE))
武汉理工大学华夏学院 -信息工程系
4,删除操作功能,删除地址为 P的结点后件。
操作步骤,首先检查给定地址 P是否正确；
若正确则可以删除。
删除结点的过程为：
（ 1）设置一个辅助单元 q
（ 2） q的值存放在 P结点的后件指针域中，即
q=p.next
（ 3） 将被删结点 q的后件地址（ q.next)送入 p结点的指针字段中，即 p.next=q.next
（ 4） 释放 q结点占用的存储武汉理工大学华夏学院 -信息工程系实现过程描述：图 2－ 8
P q
武汉理工大学华夏学院 -信息工程系图 2-9 单链表删除给定结点后件 算法框图给出被删结点信息无此结点显示不能删开始进行删除
q=p.next
p.next=q.next
显示已删除，返回有否该结点？ 无有武汉理工大学华夏学院 -信息工程系请思考,?在单链表中
1.若在地址为 P的结点前面插入一个结点如何实现？
2.若要删除地址为 P的结点或者删除地址为 P的结点的前件如何实现？
武汉理工大学华夏学院 -信息工程系
2.3.4 循环链表
(1)定义：将单链表中的尾结点的指针场中存放首结点的地址，形成的链表称为循环链表。
(2)循环链表的形式：
设头指针的循环链表和设尾指针的循环链表
H
A B C Q…
A B C Q…
H
武汉理工大学华夏学院 -信息工程系
（ 3）循环链表的特点：
只要知道某一个结点的地址，就可以把表中所有结点访问一遍。
设起始结点为 p,被访问结点为 q，
其判断结点是否访问完的判断条件为：
q.next＝＝ p？
（ 4) 带尾指针的循环链表使用的场合：在末尾添加结点或删除首结点。
其优点是：不需要查找删除或插入的地址
（尾指针指出了）。
武汉理工大学华夏学院 -信息工程系
(1) 每个结点除数字字段外还包含一个指向后继结点的地址指针字段及一个指向前驱结点地址的指针字段，用来存放后继结点的地址的链表。
2.3.5 双链表（双向链表）
定义结点形式,(2) 由两个字段组成，如下图所示。
数值字段 指针字段
data next
指针字段
prior
武汉理工大学华夏学院 -信息工程系
(3) 双链表的结构：
通常，把链表画成用箭头相连接的结点序列，结点之间的箭头表示指针字段的值。用一个称为头指针的变量 HEAD存储开始结点（首结点）的地址，对于一个空的单链表则 HEAD的值为空。
a b c
后件地址前驱地址武汉理工大学华夏学院 -信息工程系
(4)双链表的操作
1.高级语言中对双链表的描述对于动态链表，先做如下说明：
§使用 C语言 时，类型说明为：
＃ define datatype int
struct dbnode{
datatype data; /*数字字段 */
struct dbnode *next;
struct dbnode *prior ； /*指针字段 */
} DBNODE,*DBNODEPTR
武汉理工大学华夏学院 -信息工程系
2.双链表的特点
设某结点的地址为 p,则有一个恒等式为：
P结点的前驱结点的后件指针场值 与 P结点的后继结点的前件指针场值相等 且 等于 p。
用符号表示为：
设 p的前驱结点地址为 q； p的后继地址为 r，
则：
q＝ p－ >prior ；
r＝ p－ >next；
q->next＝ r->prior＝ p
武汉理工大学华夏学院 -信息工程系
3.双链表的插入操作（在 q结点后插入）
92 3
q
q 6
新结点 p
q的后件 q－ >next
3
q
9
q的后件 q－ >next
1.形成 p P＝（ DBNODEPTR)malloc(sizeof(DBNODEPTR))
武汉理工大学华夏学院 -信息工程系
2.挂链
q 6
新结点 p
3
q
9
q的原后件 q－ >next
第一个链,p送入 q－ >next
将 p送入其前件的后件指针域第二个链,p送入（ p－ >next）－ >prior
将 p送入其后件的前件指针域武汉理工大学华夏学院 -信息工程系
4.双链表的删除操作（删除 q结点 ）
92 3
q
3
被删除结点 q
q的后件 q－ >next
2
q
9
q的后件 q－ >next
1.删除 p 办移交前件指针域送往后件的前件指针域中后件指针域送往前件的后件指针域中 2.释放 p
武汉理工大学华夏学院 -信息工程系本章小结：
1.线性表有顺序存储和链式存储两种存储结构；
2.顺序存储是一种随机存取的结构、链式存储是一种顺序存取的结构；
3.顺序存储适用于静态操作、链式存储适用于动态操作；
4.选择使用何种存储时，主要考虑：
表长能否事先确定？常常使用的操作是什么？
5.若使用链式存储，还要考虑是单链、双链还是循环链；
6.链表有静态链表和动态链表的区别
作业,P53 2.1,2.3,2.5,2.6,2.9
武汉理工大学华夏学院 -信息工程系习题解答
P53 2.3 要求用最快速度存取元素选用表－顺序表好
2.5 （ 1) 4,1 （ 2) 12,8,9,6 （ 3) 5,13
（ 4) 12,10,7,1
2.6 p＝ l； num＝ 0;
P＝＝ ^ 输出 num＋
num＝ num+1； p＝ p－ >next 结束武汉理工大学华夏学院 -信息工程系
2.9
#define m 10
#define n 8
main（）
{
int a[m],b[n],c[m+n];
int I,j,k;
for(i=0;i<m;i++) scanf(“%d”,&a[i]);
for(j=0;j<n;j++) scanf(“%d”,&b[j]);
i=0;j=0;k=0
while(i<m&&j<n)
if(a[i]<b[j]) c[k++]=a[i++];
else c[k++]=b[j++];
while(i<m && k<m+n ) c[k++]=a[i++];
while(j<n && k<m+n ) c[k++]=b[j++];
for(k=0; k<m+n ;k++)
printf(“%5d\n”,c[k]);
}
2.1 线性表的类型定义定义：线性表是一个有 n（ n>=0） 个元素的有限序列，各元素具有相同的数据类型
（同一数据对象）。例如 (a,b,c,d,e) 与
（ 23,45,67,89,90,…,100 ） 都称为线性表。
(a,b,c,d,e)也称为串。
术语,表长：表中元素的个数，称为表的长度 。
空表：表中元素个数为零的表武汉理工大学华夏学院 -信息工程系
线性表的特点：表中元素存在着“序偶”关系，
即除首结点无前件，尾结点无后件以外的其余结点都有且仅有一个前件也有且仅有一个后件。
存储线性表的方法：顺序存储和链式存储；
线性表的基本操作
1,初始化（置空表）
2,求表长
3,取表中元素
4,定位
5,在表中插入新元素
6,删除表中某一个元素武汉理工大学华夏学院 -信息工程系
2.2 线性表的顺序表示和实现
2.2.1 定义 用顺序存储方法存储的表称为顺序表实现方法 用一维数组作为顺序表的存储区域。设线性表中的所有结点按前驱后继关系排成一个线性序列,(K1,K2,K3…… KN) 其中结点个数 N称为表的长度，当 N=0时的线性表称为空表。又设数组 V[N0]
(N<N0)用来依次存储线性表中的 N个元素,V[N+1]到
V[N0]是为插入新元素准备的空单元，如图 2-1所示：
下标 …
数组 V … …
1 2 3 4 N … N0
K1 K2 K3 K4 KN
图 2－ 1顺序表的存储结构示意 MAXSIZE
武汉理工大学华夏学院 -信息工程系
1） 节省存储空间；
2） 逻辑上相邻结点在物理次序上也相邻，其存储地址可以用计算公式表示为：
LOC(I)=LOC(1)+(I-1)*L
其中 I的是结点的逻辑序号即为第 I个结点 ；
LOC(1)为首结点的地址；
L为每一个结点占用的存储单元数
3）可以实现对结点的随机访问。
顺序存储的优点是,
不便于动态修改，即在对结点进行插入或删除操作时，要移动较多的结点。
顺序存储的缺点是：
武汉理工大学华夏学院 -信息工程系
2.2.2 顺序表的基本操作顺序表的类型定义,
#defile N0 100 /*用宏定义表的容量 */
Typedef struct
｛ char V[N0]； /*V为字符数组，元素值是字符 */
int len； /*表的当前长度 */
｝ SQLIST;
1.建表,定义一个数组 V及表长变量 N,输入数据。注意：每输入一个值，其表长要加 1。
武汉理工大学华夏学院 -信息工程系
2,定位操作 顺序表的定位操作非常简单，由于顺序表的逻辑顺序与存储顺序一致，则当 1<=I<=N时,V[I]就是顺序表中的第 I个元素。其算法流程是：
输入 K （ 被查值）
I=1
V[I]=K?
I=I+1
I<=N?
图 2－ 2 顺序表的定位操作查找到，输出 V[I],结束
K不是顺序表中的元素
2.2.2 顺序表的基本操作
＋
－
－
＋
思考：
查找第 I个结点的前驱和后继应如何实现？
分析：第 I个结点的位置，
若 I=1,表明是首结点；
若 I=N,表明是尾结点；
武汉理工大学华夏学院 -信息工程系在顺序表中插入一个元素时，由于顺序表中的元素是连续存放的，所以在插入前需要考虑以下几个问题：
3,插入操作其一，事先定义的存储区域（数组）是否还有空闲的单元，若有，则可以插入，否则，表明表已经满了；
其二，要确定插入位置 I,即在第 I个元素后面插入，
确定插入位置 I的方法有直接给出位置 I或者给出元素值，
去确定位置 I；
其三，插入方法是，若 I >= N 则直接将被插入的值送往 V[N+1]单元就可以了,若 I<N则表明数组元素 V[I+1]不是空单元，因此在插入新元素之前，要将顺序表中的
V[I+1]～ V[N]中的所有元素依次向后移动一个位置，空出数组元素 V[I+1],再将被插入的值送往 V[I+1]单元。
其四，插入一个元素后，应改变将顺序表的长度 N，
即将原来的 N加 1取代 N，其算法流程是：
武汉理工大学华夏学院 -信息工程系输入被插入值 K
和插入位置 I
I<=N
J=I+1
J=N
V[J+1]=V[J]
J=J-1
V[I+1]=K
N=N+1
返回
V[N+1]=K
表满返回图 2－ 3 顺序表的插入操作否否追加插入
N=N0
移动数据空出位置 改变表长插入武汉理工大学华夏学院 -信息工程系在顺序表中删除一个元素时，删除前需要考虑以下几个问题,
4,删除操作其一 已建成的顺序表是否为空，若是则表明该线性表中无结点，因此无元素删除，否则表明表中有结点；
其二，要确定被删结点的位置 I,即要删除第 I个元素，确定被删位置 I的方法有直接给出位置 I或者给出元素值，去确定位置 I；
其三，删除方法是，若 I=N则表明将要删除的是终端结点，因此直用 N=N-1就可以了，若 I<N则表明将要删除的是非终端结点，因此要将顺序表中的 V[I+1]～
V[N]中的所有元素依次向前移动一个位置就可以了。
其四，删除后，应修改顺序表的长度 N（ 即 N=N-1)。
其算法流程是：
武汉理工大学华夏学院 -信息工程系输入被删除值 K
的位置 I
J=I+1
V[J-1]=V[J]
J=J+1
表空返回
N=N-1
N=N-1
返回图 2－ 4 顺序表的删除操作删除最后一个结点
＋
－
改变表长
I=n
N＝ 0
N＝ j
武汉理工大学华夏学院 -信息工程系顺序表的插入和删除算法的执行时间主要用在元素的前后移动上,
（ 4）效率评价以插入为例：当 I=0时，（即在排首插入）则需要移动 N个元素，当 I=1时，则需要移动 N－ 1个元素，当 I=N-1
时，则需要移动 1个元素，设插入新元素在表中的各位置概率相等，则插入时，平均移动元素的次数是
M(I)=[(n-1)+(n-2)+…,.+(n-i)]/(n+1)=n/2
删除时，平均移动元素的次数是
M(D)= )=[(n-1)+(n-2)+…,.+(n-i)]/n=(n-1)/2
这说明，在顺序表上进行一次插入或删除平均需要移动一半的元素，这两个算法的执行时间的时间复杂度为 O(N)。
（ 5）应用举例：两个有序表合并武汉理工大学华夏学院 -信息工程系
（ 1） 链表的定义 用链接方法存储的线性表称为线性链表,简称链表。
（ 2） 表示方法 每一个结点的存储内容分成两个部分：
一部分用来存储结点的值，称为数值字段（又称数值域），一部分用来存储结点之间关系的，称为指针字段
（又称指针域）。
（ 3）链表的类型 按每个结点所含指针字段的个数，
分为,单链表和双链表两种。
2.3 线性表的链接存储结构及运算
2.3.1 链表和指针指针：存储其他结点位置信息的域称为指针域，指针域中存储的信息称为指针或链。
武汉理工大学华夏学院 -信息工程系
(1) 每个结点除数字字段外还包含一个指向后继结点的指针字段，用来存放后继结点的地址的链表。
(3) 单链表的结构：
通常，把链表画成用箭头相连接的结点序列，结点之间的箭头表示指针字段的值。用一个称为头指针的变量 HEAD存储开始结点（首结点）的地址，对于一个空的单链表则 HEAD的值为空。
2.3.2 单链表（单向链表）
定义结点形式,(2) 由两个字段组成，如下图所示。
数值字段 指针字段 data next
武汉理工大学华夏学院 -信息工程系
(5) 循环单链表 它是单链表的另外的一种形式，即在单链表的的尾结点的指针字段中存放着首结点的地址。见下图
(4)单链表的画法 见下图,
H
A B C Q…
H
A B C Q…
武汉理工大学华夏学院 -信息工程系
2.3.3 单链表的操作高级语言中对单链表的描述有两种方法,一种为利用数组类型构成 静态链表 ； 另一种是利用指针类型构成 动态链表 。这里重点介绍动态链表。对于动态链表，先做如下说明：
1.高级语言中对单链表的描述
§使用 C语言 时，类型说明为：
＃ define elemtype char
struct node{
elemtype data; /*数字字段 */
struct node *next; /*指针字段 */
}NODE,*NODEPTR;
# dedile LEN sizeof(NODE) /*定义结点长度 */
NODE *p,*q; /*定义指针变量 */
NODEPTR H; /*定义头指针变量 */
武汉理工大学华夏学院 -信息工程系功能,在链表中查找第 I个结点，若存在则返回结点的地址，否则给出不存在的信息。
2,定位操作方法,首先看表空否？
不空则从表头结点的地址开始查找，找到结束；
找不到再取下一个结点的地址，看其空否？
若空则给出不存在地信息，否则继续查找。
算法框图：见下图武汉理工大学华夏学院 -信息工程系输入被查值 X
返回
P=H
p=p.next
查找成功，输出 P
查找不成功，返回图 2－ 5 单链表定位操作算法框图表空否？
P.data=x
p= NULL
+
+
+
武汉理工大学华夏学院 -信息工程系
3,插入操作功能,在地址为 P的结点后面插入一个新结点，该新结点的值由 X给出。
操作步骤,首先检查给定地址 P是否正确；
若正确则可以插入插入结点的过程为：
（ 1）为新结点分配存储单元 Q
（ 2） 形成结点（把 X送入 Q的数值字段中）
（ 3）将 Q结点链接到链表中（把 P 结点的后件地址送入 Q的指针字段；再将 Q送入 P的后件的指针字段中）
武汉理工大学华夏学院 -信息工程系实现过程描述,见下图
P p.next
新结点 q
P q.next
q
x
武汉理工大学华夏学院 -信息工程系图 2-8 单链表插入操作 算法框图,
输入被插入的新结点的值 X
形成新结点地址 q
显示无法插入
q=(NODEPTR)malloc(LEN)
q.data=x
q.next=p.next
p.next=q
插入结束返回
P结点存在否？ 无
q=(NODE*)malloc(sizeof(NODE))
武汉理工大学华夏学院 -信息工程系
4,删除操作功能,删除地址为 P的结点后件。
操作步骤,首先检查给定地址 P是否正确；
若正确则可以删除。
删除结点的过程为：
（ 1）设置一个辅助单元 q
（ 2） q的值存放在 P结点的后件指针域中，即
q=p.next
（ 3） 将被删结点 q的后件地址（ q.next)送入 p结点的指针字段中，即 p.next=q.next
（ 4） 释放 q结点占用的存储武汉理工大学华夏学院 -信息工程系实现过程描述：图 2－ 8
P q
武汉理工大学华夏学院 -信息工程系图 2-9 单链表删除给定结点后件 算法框图给出被删结点信息无此结点显示不能删开始进行删除
q=p.next
p.next=q.next
显示已删除，返回有否该结点？ 无有武汉理工大学华夏学院 -信息工程系请思考,?在单链表中
1.若在地址为 P的结点前面插入一个结点如何实现？
2.若要删除地址为 P的结点或者删除地址为 P的结点的前件如何实现？
武汉理工大学华夏学院 -信息工程系
2.3.4 循环链表
(1)定义：将单链表中的尾结点的指针场中存放首结点的地址，形成的链表称为循环链表。
(2)循环链表的形式：
设头指针的循环链表和设尾指针的循环链表
H
A B C Q…
A B C Q…
H
武汉理工大学华夏学院 -信息工程系
（ 3）循环链表的特点：
只要知道某一个结点的地址，就可以把表中所有结点访问一遍。
设起始结点为 p,被访问结点为 q，
其判断结点是否访问完的判断条件为：
q.next＝＝ p？
（ 4) 带尾指针的循环链表使用的场合：在末尾添加结点或删除首结点。
其优点是：不需要查找删除或插入的地址
（尾指针指出了）。
武汉理工大学华夏学院 -信息工程系
(1) 每个结点除数字字段外还包含一个指向后继结点的地址指针字段及一个指向前驱结点地址的指针字段，用来存放后继结点的地址的链表。
2.3.5 双链表（双向链表）
定义结点形式,(2) 由两个字段组成，如下图所示。
数值字段 指针字段
data next
指针字段
prior
武汉理工大学华夏学院 -信息工程系
(3) 双链表的结构：
通常，把链表画成用箭头相连接的结点序列，结点之间的箭头表示指针字段的值。用一个称为头指针的变量 HEAD存储开始结点（首结点）的地址，对于一个空的单链表则 HEAD的值为空。
a b c
后件地址前驱地址武汉理工大学华夏学院 -信息工程系
(4)双链表的操作
1.高级语言中对双链表的描述对于动态链表，先做如下说明：
§使用 C语言 时，类型说明为：
＃ define datatype int
struct dbnode{
datatype data; /*数字字段 */
struct dbnode *next;
struct dbnode *prior ； /*指针字段 */
} DBNODE,*DBNODEPTR
武汉理工大学华夏学院 -信息工程系
2.双链表的特点
设某结点的地址为 p,则有一个恒等式为：
P结点的前驱结点的后件指针场值 与 P结点的后继结点的前件指针场值相等 且 等于 p。
用符号表示为：
设 p的前驱结点地址为 q； p的后继地址为 r，
则：
q＝ p－ >prior ；
r＝ p－ >next；
q->next＝ r->prior＝ p
武汉理工大学华夏学院 -信息工程系
3.双链表的插入操作（在 q结点后插入）
92 3
q
q 6
新结点 p
q的后件 q－ >next
3
q
9
q的后件 q－ >next
1.形成 p P＝（ DBNODEPTR)malloc(sizeof(DBNODEPTR))
武汉理工大学华夏学院 -信息工程系
2.挂链
q 6
新结点 p
3
q
9
q的原后件 q－ >next
第一个链,p送入 q－ >next
将 p送入其前件的后件指针域第二个链,p送入（ p－ >next）－ >prior
将 p送入其后件的前件指针域武汉理工大学华夏学院 -信息工程系
4.双链表的删除操作（删除 q结点 ）
92 3
q
3
被删除结点 q
q的后件 q－ >next
2
q
9
q的后件 q－ >next
1.删除 p 办移交前件指针域送往后件的前件指针域中后件指针域送往前件的后件指针域中 2.释放 p
武汉理工大学华夏学院 -信息工程系本章小结：
1.线性表有顺序存储和链式存储两种存储结构；
2.顺序存储是一种随机存取的结构、链式存储是一种顺序存取的结构；
3.顺序存储适用于静态操作、链式存储适用于动态操作；
4.选择使用何种存储时，主要考虑：
表长能否事先确定？常常使用的操作是什么？
5.若使用链式存储，还要考虑是单链、双链还是循环链；
6.链表有静态链表和动态链表的区别
作业,P53 2.1,2.3,2.5,2.6,2.9
武汉理工大学华夏学院 -信息工程系习题解答
P53 2.3 要求用最快速度存取元素选用表－顺序表好
2.5 （ 1) 4,1 （ 2) 12,8,9,6 （ 3) 5,13
（ 4) 12,10,7,1
2.6 p＝ l； num＝ 0;
P＝＝ ^ 输出 num＋
num＝ num+1； p＝ p－ >next 结束武汉理工大学华夏学院 -信息工程系
2.9
#define m 10
#define n 8
main（）
{
int a[m],b[n],c[m+n];
int I,j,k;
for(i=0;i<m;i++) scanf(“%d”,&a[i]);
for(j=0;j<n;j++) scanf(“%d”,&b[j]);
i=0;j=0;k=0
while(i<m&&j<n)
if(a[i]<b[j]) c[k++]=a[i++];
else c[k++]=b[j++];
while(i<m && k<m+n ) c[k++]=a[i++];
while(j<n && k<m+n ) c[k++]=b[j++];
for(k=0; k<m+n ;k++)
printf(“%5d\n”,c[k]);
}
