1北京邮电大学自动化学院
数据结构
北京邮电大学自动化学院
杨福兴
电话,13331090202
E-mail,yangfx@sina.com
2004年 9月 13日
2北京邮电大学自动化学院
? 使用教材：
?严蔚敏 吴伟民 编著,数据结构（ C语言
版），清华大学出版社
? 参考书：
?1、曹桂琴 编著，数据结构基础，大连理工大
学出版社。
?2、晋良颖 编，数据结构，人民邮电出版社
?3,Bruno R.Preiss，数据结构与算法，电子
工业出版社
使用教材及参考书
3北京邮电大学自动化学院
? 许晓燕 负责班级,1～ 2班
?电 话,13121868069
? E-mail,ingo@tom.com
? 吴 魏 负责班级,3～ 4班
?电 话,13810354850
? E-mail,wilson_nuaa@163.com
? 徐 刚 负责班级,5~6班
?电 话,13311321087
? E-mail,werhh@163.com1
,数据结构, 辅导老师名单
4北京邮电大学自动化学院
课程教学目的
? 在计算机及其应用的各个领域中，都会用到各种
各样的数据结构，通过本课程使学生学会分析和
研究计算机加工对象的特性，选择合适的数据结
构和存储表示，以及编制相应的实现算法．
? 课程教学基本要求,本课程介绍各种最常用的数据
结构，阐述各种数据结构内涵的逻辑关系，讨论
它们在计算机中的存储表示，以及在这些数据结
构上的运算和实际的执行算法，并对算法的效率
进行简要的分析和讨论。
5北京邮电大学自动化学院
? 数据结构的研究不仅涉及到
? 计算机硬件 （特别是编码理论、存储装置和存取
方法）的研究范围，
? 而且和 计算机软件 的研究有着密切的关系，无论
是编译程序还是操作系统，都涉及到数据元素在
存储器中的分配问题。
? 在研究 信息检索时 也必须考虑如何组织数据，以
便查找和存取数据元素更为方便。
课程介绍
6北京邮电大学自动化学院
? 因此，可以认为 数据结构 是介于 数学、计算机硬件
和计算机软件 三者之间的一门核心课程。
? 程序＝算法＋数据结构
? 目前在我国,,数据结构, 已经不仅仅是计算机专
业的教学计划中的核心课程之一，而且是其它非计
算机专业的主要选修课程之一。
? 通过对这门课程的学习可增强选择合适的数据结构
与编写高效的程序的能力。
课程介绍
7北京邮电大学自动化学院
教学安排及考试
? 讲课学时,34学时
? 上机时间,5次（每次 2学时）
? 考试成绩计算：
?平时成绩（考勤,作业及上机） 30分
?考试（ 70分）
? 考查课和考试课分别考试，考查课在第 17周考
试，考试课按学校安排时间考试。
8北京邮电大学自动化学院
目录
? 第 1章 绪论
? 第 2章 线性表
? 第 3章 栈和队列 第 4章 串
? 第 5章 数组和广义表
? 第 6章 树和二叉树
? 第 7章 图
? 第 8章 查找
? 第 9章 内部排序
? 第 10章 文件
9北京邮电大学自动化学院
? 计算机的应用已不再局限于科学计算，而更多地
用于控制、管理及数据处理等 非数值计算的处理
工作 。
? 与此对应，计算机加工处理的对象由纯粹的数值
发展到 字符、表格和图像 等各种具有一定结构的
数据。
? 为了编写出一个“好”的程序，必须分析 待处理
的对象的特征以及各对象之间存在的关系,这就
是“数据结构”这门学科形成和发展的背景。
第一章 绪 论
第一章 绪 论
10北京邮电大学自动化学院
?1.1 什么是数据结构
?1.2 基本概念和术语
?1.3 抽象数据类型的表示与实现
?1.4 算法和算法分析
第一章 绪 论
11北京邮电大学自动化学院
? 一般来说，用计算机解决一个具体问题时，大致需要经多下
列几个步骤：
?首先要从具体问题抽象出一个适当的数学模型
?然后设计一个解此数学模型的算法，
?最后编出程序、进行测试、调整直至得到最终解答。
? 寻求数学模型的实质是分析问题，从中提取操作的对象，并
找出这些操作对象之间含有的关系，然后用数学的语言加以
描述。
? 然而，更多的非数值问题无法用数学方程描述。什么是数据
结构呢？先看以下几个例子。
1.1 什么是数据结构
12北京邮电大学自动化学院
0 0 1 高等数学 樊映川 S 0 1
0 0 2 理论力学 罗远祥 L 0 1
0 0 3 高等数学 华罗庚 S 0 1
0 0 4 线性代数 栾汝书 S 0 2
…… …… …… ……
书目文件
按书名 按作者名 按分类号
高等数学 001, 003 ……
理论力学 002, ……,.
线性代数 004, ……
…… ……,.
樊映川 001,…
华罗庚 002,…,
栾汝书,…,
……, ……,
L 002,…
S 0 0 1,0 0 3,
…… ……
索引表
线性表
例 1 书目自动检索系统
登录号：
书名：作者名：
分类号：出版单位：
出版时间：价格：
书目卡片
13北京邮电大学自动化学院
树
……..……..
…..,…..,…..,…...
例 2 人机对奕问题
14北京邮电大学自动化学院
? 对于一个多叉路口，设计一
个交通信号灯的管理系统。
? 首先需要分析一下所有车辆
的行驶路线的冲突问题。
? 这个问题可以归结为对车辆
的可能行驶方向作某种分
组，对分组的要求是使任一
个组中各个方向行驶的车辆
可以同时安全行驶而不发生
碰撞。
C
E
D
A
B
例 3 多叉路口交通灯管理问题
15北京邮电大学自动化学院
可通行方向
?A?B A?C A ?D
?B ?A B?C B?D
?D?A D?B D ?C
?E ?A E?B E?C E?D
C
E
D
A
B
例 3多叉路口交通灯管理问题
16北京邮电大学自动化学院
有些通行方向显然不能同时进行，相应的结点间画一条连线。
AB AC AD
BA BC BD
DA D B DC
EA EB EC ED
图 1.2 交叉路口的图示模型
C
E
D
A
B
图
17北京邮电大学自动化学院
? 把图 1.2中的结点进行分组，使得有结点相连的结点不
在同一个组里。
? 地图着色问题
? 如果把上图中的一个结点理解为一个国家,结点之间
的连线看作两国有共同边界，上述问题 就变成著名的
“着色问题”,即求出最少要几种颜色可将图中所有
国家着色，使得任意两个相邻的国家颜色都不相同。
? 通过上面的分析，我们就获得了该交通管系统的数学
模型。下面就可以着手进行算法的设计。
例 3多叉路口交通灯管理问题
18北京邮电大学自动化学院
算法设计
? 2,―贪心法”
? while 有结点未着色；
? { 选择一种新颜色；
? 在未着色的结点中,给尽可能多的彼此结点之间没有边
点着色；
? }
? 1,对 n个结点，逐个测试其所有组合；
例 3多叉路口交通灯管理问题
19北京邮电大学自动化学院
AB AC AD
BA BC BD
DA D B DC
EA EB EC ED
图 1.2 交叉路口的图示模型
图
AB AC AD
BA BC BD
DA DB DC
EA EB EC ED
C
E
D
A
B
着色结果
20北京邮电大学自动化学院
? 把上面方法应用于图 1.2，得到下面的分组：
? 绿色,AB,AC,AD,BA,DC,ED
? 蓝色,BC,BD,EA
? 红色,DA,DB
? 白色,EB,EC
例 3多叉路口交通灯管理问题
21北京邮电大学自动化学院
? 综上三个例子，描述这类非数值计算问题的数学模型
不再是数学方程，而是诸如 表、树和图 之类的数据结
构。
? 因此，简单说来，数据结构是一门 研究非数值计算的
程序设计问题中 计算机的操作对象以及它们之间的关
系和操作等等的学科 。
? 数据结构就是研究数据的逻辑结构和物理结构它们之
间相互关系，并对这种结构定义相应的运算，而且确
保经过这些运算后所得到的新结构仍然是原来的结构
类型。
第一章 绪 论
22北京邮电大学自动化学院
? 数据 (Data):是对客观事物的符号表示，在计算机科
学中是指 所有能输入到计算机中并被计算机程序处
理的符号的总称。
? 对计算机科学而言，数据的含义极为广泛，如图
像、声音等都可以通过编码而归之于数据的范畴。
? 数据元素 (Data Element):是数据的基本单位，在计
算机程序中通常作为一个整体进行考虑和处理。
? 例如，例 1－ 2中的“树”中的一个棋盘格局，例 1
－ 3中的“图”中的一个园圈都被称为一个数据元
素。
1.2 基本概念和术语
23北京邮电大学自动化学院
? 一个数据元素可由若干个数据项组成。例如，例 1－ 1中一
本书的书目信息为一个数据元素，而书目信息中的每一项
（如书名、作者名等）为一个数据项。
? 数据项是数据的不可分割的最小单位 。
? 数据对象 (Data Object),是性质相同的数据元素的集合，
是数据的一个子集。例如，整数数据对象是集合 N＝ {0，
± 1,± 2,… }，字母字符数据对象是集合 C＝ {A,B，
C,…} 。
? 数据结构 (Data Structure),是相互之间存在一种或多种
特定关系的数据元素的集合。
1.2 基本概念和术语
24北京邮电大学自动化学院
? 数据结构主要指逻辑结构和物理结构。 数据之间的相互关系称
为逻辑结构 。通常分为四类基本结构：
? 一、集合 结构中的数据元素除了同属于一种类型外，别无其
它关系。
? 二、线性结构 结构中的数据元素之间存在一对一的关系。
? 三、树型结构 结构中的数据元素之间存在一对多的关系。
? 四、图状结构或网状结构 结构中的数据元素之间存在多对多
的关系。
1.2 基本概念和术语
25北京邮电大学自动化学院
? 数据结构的形式定义为：数据结构是一个二元组：
? Data-Structure=(D,S)
? 其中,D是数据元素的有限集,S是 D上关系的有限
集。
? 例 复数的数据结构定义如下,Complex=(C,R)
? 其中,C是含两个实数的集合 ﹛ C1,C2﹜,分别表
示复数的实部和虚部。 R={P},P是定义在集合上的
一种关系 {〈 C1,C2〉 }。
1.2 基本概念和术语
26北京邮电大学自动化学院
? 数据结构在计算机中的表示称为数据的物理结构，又称为
存储结构。
? 数据结构在计算机中有两种不同的表示方法：
? 顺序表示和非顺序表示
? 由此得出两种不同的存储结构,顺序存储结构和链式存储
结构
? 顺序存储结构,用数据元素在存储器中的相对位置来表示
数据元素之间的逻辑关系。
? 链式存储结构,在每一个数据元素中增加一个存放地址的
指针,用此指针来表示数据元素之间的逻辑关系。
1.2 基本概念和术语
27北京邮电大学自动化学院
元素 n
……..
元素 i
……..
元素 2
元素 1L
o
Lo+m
Lo+(i-1)*m
Lo+（ n-1)*m
存储地址 存储内容
Loc(元素 i)=Lo+（ i-1)*m
顺序存储
28北京邮电大学自动化学院
1536元素 21400元素 1 1346元素 3 ∧元素 4
1345h
存储地址 存储内容 指针
1345 元素 1 1400
1346 元素 4 ∧
……, ……,,……,
1400 元素 2 1536
……, ……,,……,
1536 元素 3 1346
链式存储
h
29北京邮电大学自动化学院
数据的逻辑结构
数据的存储结构
数据的运算：检索、排序、插入、删除、修改等
线性结构
非线性结构
顺序存储
链式存储
线性表
栈
队
树形结构
图形结构
数据结构的三个方面：
1.2 基本概念和术语
30北京邮电大学自动化学院
? 数据类型,数据类型是一个值的集合和定义在这个值集范围
上的一组操作的总称。例如,C语言中的整型变量，其值集
为某个区间上的整数，定义在其上的操作为：加、减、乘、
除和取模等算术运算。
? 按“值”的不同特性，高级程序语言中的数据类型可分为：
? 一类是非结构的原子类型 。原子类型的值是不可分解的。
如,C语言中的基本类型（整型、实型、字符型和枚举类
型）、指针类型和空类型。
? 另一类是结构类型 。结构类型的值是由若干成分按某种结构
组成的。例如数组的值由若干分量组成。每个分量可以是整
数，也可以是数组等。
1.2 基本概念和术语
31北京邮电大学自动化学院
? 抽象数据类型：一个数学模型以及定义在该模型上的一组操
作。 抽象数据类型的定义仅取决于它的一组逻辑特性，而与
其在计算机内部如何表示和实现无关，即不论其内部结构如
何变化，只要它的数学特性不变，都不影响其外部的使用。
? 抽象数据类型实际上就是对该数据结构的定义。因为它定义
了一个数据的逻辑结构以及在此结构上的一组算法。
? 和数据结构的形式定义相对应，抽象数据类型可用三元组描
述如下,（Ｄ，Ｓ，Ｐ）
? D是数据对象,S是 D上的关系集,P是对 D的基本操作集。
1.2 基本概念和术语
32北京邮电大学自动化学院
? 本书采用以下格式定义抽象数据类型
? 抽象数据类型的定义：
ADT抽象数据类型名 {
数据对象,<数据对象的定义 >
数据关系,<数据逻辑关系的定义 >
基本操作,<基本操作的定义 >
? }ADT抽象数据类型名
? 基本操作的定义格式为：
基本操作名（参数表）
初始条件,<初始条件描述 >
? 操作结果,<操作结果描述 >
1.2 基本概念和术语
33北京邮电大学自动化学院
? 抽象数据类型三元组的定义：
? ADT Triplet{
? 数据对象,D={e1,e2,e3|e1,e2,e3?ElemSet}
? 数据关系,R1={<e1,e2>,<e2,e3>}
? 基本操作：
? InitTriplet(&T,v1,v2,v3)
? 操作结果,构造了三元组 T，元素 e1,e2和 e3分别赋以参数
v1,v2和 v3的值。
? } ADT Triplet
1.2 基本概念和术语
34北京邮电大学自动化学院
? ADT Triplet{
? 数据对象, D={e1,e2,e3|e1,e2,e3?ElemSet}
? 数据关系, R1={<e1,e2>,<e2,e3>}
? 基本操作,
? Get(T,i,&e)
? 初始条件,三元组 T已存在,1?i?3
? 操作结果,用 e返回 T的第 i元的值。
? } ADT Triplet
1.2 基本概念和术语
35北京邮电大学自动化学院
? 抽象数据类型 可通过固有数据类型来表示和实现，即利
用处理器中已存在的数据类型来说明新的结构，用已经
实现的操作来组合新的操作。
? 由于本书在高级程序设计语言的虚拟层次上讨论抽象数
据类型的表示和实现，并且讨论的数据结构及其算法主
要是面向读者，故采用 介于伪码和 C语言之间的类 C语
言作为描述工具,有时也用伪码描述一些只含抽象操作
的抽象算法。
? 这使得数据结构和算法的描述和讨论简明清晰，不拘泥
于 C语言的细节，又能容易转换成 C或者 C＋＋程序。
1.3 抽象数据类型的表示和实现
36北京邮电大学自动化学院
? 本书采用的类 C语言精选了 C语言的一个核心子集，同时作了
若干扩充，增强了语言的描述功能。以下对其作简要说明。
? （ 1）预定义常量和类型
? //函数结果状态代码
? #define TRUE 1 #define FLASE 0
? #define OK 1 #define ERROR 0
? #define INFEASIBLE -1 #define OVERFLOW -2
? // Status是函数的类型，其值是函数结果状态代码
? Typedef int Status;
1.3 抽象数据类型的表示和实现
37北京邮电大学自动化学院
? （ 2）数据结构的表示用类型定义（ typedef）描述。
数据元素类型约定为 Elemtype，由用户在使用该数据
类型时定义。
? （ 3）基本操作的算法都用以下形式的函数描述：
?函数类型 函数名 （函数参数表） {
?//算法说明
?语句序列
?}//函数名
1.3 抽象数据类型的表示和实现
38北京邮电大学自动化学院
? （ 4）赋值语句有
?简单赋值 变量名 =表达式；
?串值赋值 变量名 1=变量名 2=……= 表达式
?成组赋值 （变量名 1，。。。，） =（表达式
1，）
?交换赋值 变量名 ? 变量名
?条件赋值 变量名 =条件表达式？表达式 T：表
达式 F
1.3 抽象数据类型的表示和实现
39北京邮电大学自动化学院
? （ 5）选择语句有
? 条件语句 1 if（表达式）语句；
? 条件语句 2 if（表达式）语句； Else 语句
? 开关语句 1 switch(表达式 ) {
? case 值 1：语句序列 1； break;
? Default,语句序列 n+1;}
? 开关语句 2 switch{
? case 条件 1：语句序列 1； break;
? Default,语句序列 n+1;}
1.3 抽象数据类型的表示和实现
40北京邮电大学自动化学院
? （ 6）循环语句有
? For语句
? for（赋初值表达式；条件；修改表达式序列）语句；
? While 语句 while（条件）语句；
? do-while语句
? do {
? 语句序列 }while（条件）；
1.3 抽象数据类型的表示和实现
41北京邮电大学自动化学院
? （ 7）结束语句
?函数结束语句 return 表达式； return；
?Case结束语句 break;
?异常结束语句 exit(异常代码 )
? 8）输入和输出语句
? 输入语句 scanf([格式串 ]，变量 1，变量 n)；
? 输出语句 printf([格式串 ]，表达式 1，表达式 2)；
1.3 抽象数据类型的表示和实现
42北京邮电大学自动化学院
? （ 9）注释
? 单行注释 //文字序列
? （ 10）基本函数有
? 求最大值 max(表达式 1，表达式 n）
? 求最小值 min(表达式 1，表达式 n）
? 求绝对值 abs(表达式 )
? 求不足整数值 floor（表达式）
? 判定行结束 eoln（文件变量）或 eoln
1.3 抽象数据类型的表示和实现
43北京邮电大学自动化学院
? （ 11）逻辑运算约定
? 与运算 &&,对于 A &&B,当 A的值为 0时,不再对 B
求值。
? 或运算 ||,对于 A||B,当 A的值为非 0时,不再对 B
求值。
1.3 抽象数据类型的表示和实现
44北京邮电大学自动化学院
? 例题：抽象数据类型 Triplet的表示和实现
? //--------采用动态分配的顺序存储结构 ----------------
? Typedef ElemType *Triplet://initTriplet分配三个元素存
储空间
? //--------基本操作的函数原形说明 ----------------
? Status InitTriplet (Triplet &T,ElemType v1,ElemType
v2,ElemType v3）；
? //操作结果：构造了三元组 T，元素 e1,e2和 e3分别赋以参
数 v1,v2和 v3的值。
1.3 抽象数据类型的表示和实现
45北京邮电大学自动化学院
? Status DestroyTriplet (Triplet &T）；
?//操作结果：三元组 T被消除。
? Status Get (Triplet &T,int i,ElemType &e）；
?//初始条件：三元组 T已存在,1?i?3 。
? //操作结果：用 e返回 T的第 i元的值。
1.3 抽象数据类型的表示和实现
46北京邮电大学自动化学院
? //--------基本操作的实现 ----------------
? Status Get (Triplet &T,int i,ElemType &e） {
? // 1?i?3,用 e返回 T的第 i元的值。
? If (i<1||i>3) return ERROR;
? e=T [i-1] ；
? return OK;
? }//Get
? } ADT Triplet
1.3 抽象数据类型的表示和实现
47北京邮电大学自动化学院
? 算法是对特定问题求解步骤的一种描述，它是指令的有限序
列，每一条指令表示一个或多个操作。 1、算法有五个特性：
? （ 1）有穷性 一个算法必须总是在执行有穷步之后结束，且
每一步都在有穷时间内完成。
? （ 2）确定性 算法中每一条指令必须有确切的含义。不存在二
义性。且算法只有一个入口和一个出口。
? （ 3）可行性 一个算法是可行的。即算法描述的操作都是可以
通过已经实现的基本运算执行有限次来实现的。
? （ 4）输入 一个算法有零个或多个输入。
? （ 5）输出 一个算法有一个或多个输出。
1.4 算法和算法分析
48北京邮电大学自动化学院
? 评价一个好的算法有以下几个标准,
? （ 1） 正确性
? （ 2）可读性 算法应该好读。
? （ 3）健状性 算法应具有容错处理。当输入非法数据
时，算法应对其作出反应，而不是产生莫名其妙的输
出结果。
? （ 4）效率与存储量需求 效率是指算法执行的时
间；存储量需求指算法执行过程中所需要的最大存储
空间。
2,算法设计的要求
49北京邮电大学自动化学院
? 程序不含语法错误。
? 程序对于几组输入数据能够得出满足规格说
明的结果。
? 程序对于精心选择的典型、苛刻而带有刁难
性的几组输入数据能够得出满足规格说明的
结果。
? 程序对于一切合法的输入数据都能产生满足
规格说明的结果。
正确性（算法应满足具体问题的需求）
50北京邮电大学自动化学院
? 算法执行时间需要通过依据该算法编制的程序在计算机上运行时
所消耗的时间度量。度量一个程序的执行时间通常有两种方法。
? 事后统计的方法
?一是必须先运行依据算法编制的程序
?二是所得时间的统计量依赖于计算机的硬件、软件等环境
因素求出该算法的一个时间界限函数
? 事前分析估算的方法
?依据的算法选用何种策、问题的规模、书写的语言、编译
程序所产生的机器代码的质量、机器执行指令的速度。
? 所以，人们常常采用事前分析估算的方法。
3,算法效率的度量
51北京邮电大学自动化学院
? 使用绝对的时间单位衡量算法的效率是不合适的。 撇开这些
与计算机硬件软件有关的因素，可以认为一个特定算法的
“运行工作量”的大小，只依赖于 问题的规模 （通常用整数
量表示），或者说,它是问题规模的函数。
? 一个算法是由控制结构（顺序分支和循环三种）和原操作
（指固有数据类型的操作）构成的，则算法时间取决于两者
的综合效果。
? 为了便于比较同一问题的不同算法,通常的做法是，从算法
中选取一种对于研究问题（或算法类型）来说是基本操作的
原操作，以该基本操作重复执行的次数作为算法的时间量
度。
3,算法效率的度量
52北京邮电大学自动化学院
? 整个算法的执行时间与该基本操作（乘法）重复执行的次数
n3成正比，记为 T(n)=O(n3)
? for(i=1;i<=n;++i)
? for(j=1;j<=n;++j){ c[i][j]=0;
? for(k=1;k<=n;++k) c[i][j]+=a[i][k]*b[k][j];}
? 一般情况下，算法中基本操作重复执行的次数是问题规模 n
的某个函数 f(n),算法的时间度量记作 T(n)=O(f(n))
? 它表示随着问题规模 n的增加，算法执行时间的增长率和
f(n)的增长率相同,称作算法的渐进时间复杂度，简称时间
复杂度。
? 例 1，在如下所示的两个矩阵相乘的算法中，“乘法”运算是
“矩阵相乘问题”的基本操作。
53北京邮电大学自动化学院
? 显然，被称作问题的基本操作的原操作应是其重复执行次数
和算法的执行时间成正比的原操作，多数情况下它是最深层
循环内的语句中的原操作,它的执行次数和包含它的语句的
频度相同。
? 语句的频度是指的是该语句重复执行的次数。
? 例２ {++x;s=0;}
? 将 x自增看成是基本操作，则语句频度为 １,即 时间复杂度
为Ｏ (1)。
? 如果将 s=0也看成是基本操作，则语句频度为 ２,其 时间复
杂度仍为Ｏ (1)，即常量阶。
3,算法效率的度量
54北京邮电大学自动化学院
? 例３,for(i=1;i<=n;++i) {++x;s+=x;}
?语句频度为,2n
?其时间复杂度为,O(n)
?即时间复杂度为线性阶。
? 例４,for(i=1;i<=n;++i)
? for(j=1;j<=n;++j) {++x;s+=x;}
?语句频度为,2n2
?时间复杂度为,O(n2)
?即时间复杂度为平方阶。
3,算法效率的度量
55北京邮电大学自动化学院
? 定理：若 A(n)=amnm +am-1nm-1 +…+a 1n+a0是一个 m次多项
式，则 A(n)=O(nm)。证略。
? 例５ for(i=2;i<=n;++I)
? for(j=2;j<=i-1;++j) {++x;a[i,j]=x;}
? 语句频度为,1+2+3+…+n -2=(1+n-2) × (n-2)/2
? =(n-1)(n-2)/2 =n2-3n+2
?时间复杂度为 O(n2),
? 即此算法的时间复杂度为平方阶。
3,算法效率的度量
56北京邮电大学自动化学院
? 以下六种计算算法时间的多项式是最常用的。其关系为：
? O(1)<O(logn)<O(n)<O(nlogn) <O(n2)<O(n3)
? 指数时间的关系为：
? O(2n)<O(n!)<O(nn)
? 当 n取得很大时，指数时间算法
和多项式时间算法在所需时间上
非常悬殊。 因此，只要有人能将
现有指数时间算法中的任何一个
算法化简为多项式时间算法，那
就取得了一个伟大的成就。
3,算法效率的度量
57北京邮电大学自动化学院
? 有的情况下，算法中基本操作重复执行的次数还随问题
的输入数据集不同而不同。例如：
? Void bubble-sort(int a[],int n)
? for(I=n-1;change=TURE;I>1 && change;--I) {
? change=false; for(j=0;j<I;++j)
? if (a[j]>a[j+1]) { a[j] ←→a[j+1];change=TURE} }
? 最好情况,0次 最坏情况,1+2+3+…+n -1=n(n-1)/2
? 平均时间复杂度为,O(n2)
? 在本书以后各章节中讨论的时间复杂度，除特别指明
外，均指最坏情况下的时间复杂度。
3,算法效率的度量
58北京邮电大学自动化学院
? 类似于算法的时间复杂度，本书中以空间复杂
度作为算法所需存储空间的量度，记作,
? S(n)=O(f(n))
? 其中 n为问题的规模 (或大小 )。
? 一个上机执行的程序除了需要存储空间来寄存
本身所用指令、常数、变量和输入数据外，也
需要一些对数据进行操作的工作单元和存储一
些为实现计算所需信息的辅助空间。
4、算法的存储空间需求
59北京邮电大学自动化学院
? 线性结构的特点,在数据元素中的非空有限集中
? （ 1）存在 唯一 的一个被称作,第一”的数据元素；
? （ 2）存在 唯一 的一个被称作,最后一个”的数据元
素；
? （ 3） 除第一个外,集合中的每一个数据元素均 只有
一个前驱；
? （ 4） 除最后一个外,集合中的每一个数据元素均 只
有一个后继。
第二章 线性表
60北京邮电大学自动化学院
?2.1 线性表的类型定义
?2.2 线性表的顺序表示和实现
?2.3 线性表的链式表示和实现
?2.4 一元多项式的表示及相加
第二章 线性表
61北京邮电大学自动化学院
? 1、线性表
? 线性表 (Linear List), 一个线性表是 n个数据元素的
有限序列。例如：
? 例 1,26个英文字母组成的字母表
?（ A,B,C,…, Z）
? 例 2、某校从 1999年到 2003年各种型号的计算机拥
有量的变化情况。
?（ 6,17,28,50,92,188）
2.1 线性表的类型定义
62北京邮电大学自动化学院
? 在稍复杂的线性表中，一个数据元素可以由若干个数据项组
成。在这种情况下，常把 数据元素称为记录, 含有大量记录的
线性表又称为文件。
? 例 3、学生健康情况登记表如下：
姓 名 学 号 性 别 年龄 健康情况
王小林 790631 男 18 健康
陈 红 790632 女 20 一般
刘建平 790633 男 21 健康
张立立 790634 男 17 神经衰弱
…….,…….,……,……,…….
1、线性表
63北京邮电大学自动化学院
? 综合上述三个例子可见，线性表中的数据元素可以是各种各样
的，但同一线性表中的元素必定具有相同特征，即属同一数据
对象，相邻数据元素之间存在着序偶关系。若将线性表记为：
? (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、线性表
64北京邮电大学自动化学院
? 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。
? DestroyList(&L)
? 初始条件,线性表 L已经存在。
? 操作结果,销毁线性表 L。
2、抽象数据类型线性表
65北京邮电大学自动化学院
? ClearList(&L)
? 初始条件,线性表 L已经存在。
? 操作结果,将 L置为空表。
? ListEmpty(L)
? 初始条件,线性表 L已经存在。
? 操作结果,若 L为空表，则返回 TRUE，否则返回
FALSE。
2、抽象数据类型线性表
66北京邮电大学自动化学院
? ListLength(L)
? 初始条件,线性表 L已经存在。
? 操作结果,返回 L中数据元素个数。
? GetElem(L,i,&e)
? 初始条件,线性表 L已经存在，
1?i?Listlength(L)。
? 操作结果,用 e返回 L中第 i数据各元素的值。
? … …
2、抽象数据类型线性表
67北京邮电大学自动化学院
? LocateElem(L,e,compare())
? 初始条件,线性表 L已经存在,compare是数据元素判定函数。
? 操作结果,返回 L中第一个与 e满足关系 compare()的数据元素的
位序。若这样的元素不存在，则返回值为零为。
? ListInsert(&L,i,e)
? 初始条件,线性表 L已经存在，且 1?i ? Listlength(L)＋ 1。
? 操作结果,在 L中第 i个位置之前插入新的数据元素 e,L的长度加 1
? … …
? } ADT List
2、抽象数据类型线性表
68北京邮电大学自动化学院
? 例 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、例题
69北京邮电大学自动化学院
? 例 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）
? 从上面的问题要求可知,LC中的数据元素或是 LA中的数据元
素，或是 LB中的数据元素，则只要先设 LC为空表，然后将 LA或
LB中的元素逐个插入到 LC中即可。设两个指针 i和 j分别指向 LA
和 LB中某个元素，
??
?
?
??
时，当
时当
bab
baac,
3、例题
70北京邮电大学自动化学院
? 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
71北京邮电大学自动化学院
? 上述两个算法的时间复杂度取决于抽象数据类型 list定义中基本
操作的执行时间。假如 GetElem和 ListInsert这两个操作的执行
时间和表长无关,LocateElem的执行时间和表长成正比。
? 则算法 2.1的时间复杂度为
?O（ ListLength(LA)?ListLength(LB),
? 算法 2.2的时间复杂度则为
?O（ List Length(LA)+ListLength(LB)。
? 虽然算法 2.2中含有三个（ While）循环语句，但只有当 i和 j均指
向表中实际存在的数据元素时，才能取得数据元素的值并进行相
互比较；并且当其中一个线性表的数据元素均已插入到线性表
LC中后，只要将另外一个线性表中的剩余元素依次插入即可。
4、算法的存储空间需求
72北京邮电大学自动化学院
? 一,线性表的顺序表示
? 线性表的顺序表示指的是用一组地址连续的存储单元依次存
储线性表的数据元素。
? 假设线性表的每个元素需占用 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
2.2 线性表的顺序存储结构
73北京邮电大学自动化学院
? 线性表的这种机内表示称作线性表的顺序存储结构，称
这种存储结构的线性表为顺序表。
? 顺序存储的结构特点：以数据元素在计算机“物理位置
相邻”来表示表中数据元素间的逻辑关系。对于这种存
储方式，要访问第 i个数据元素，就可以直接计算出 ai的
存储位置 Loc(ai)。因而能随机存取表中任一数据元素，
换言之，数据元素在顺序表中的存储位置取决于该数据
元素在线性表中的顺序号。
? 例如：一个班学生，集体出游，按学号分配房
间。。。。。
74北京邮电大学自动化学院
? 由于 C语言中的一维数组也是采用顺序存储表示，故可以
用数组类型来描述顺序表。又因为除了用数组来存储线
性表的元素之外，顺序表还应该用一个变量来表示线性
表的长度属性，所以我们用结构类型来定义顺序表类
型。
? # define LIST-INIT-SIZE 100 //初始分配量
? # define LISTINCREMENT 10 //分配增量
? typedef struc{
? Elemtype *elem //存储空间基址
? int length ;//当前长度
? int ListSize; } Sqlist;
75北京邮电大学自动化学院
? 在顺序表存储结构中，很容易实现线性表的一些操作，如
线性表的构造、第 i个元素的访问。
? 注意,C语言中的数组下标从,0‖开始，因此，若 L是
Sqlist类型的顺序表，则表中第 i个元素是 L.data[i-1]。
? 顺序表上基本运算
? 1,顺序表的初始化
? 2,插入运算
? 3,删除运算
? 4,按值查找
二、顺序表上实现的基本操作
76北京邮电大学自动化学院
? 线性表的插入是指在表的第 i个位置上插入一个值为 x 的
新元素，插入后使原表长为 n的表,
? (a1,a2,..., ai-1,ai,ai+1,..., an)
? 成为表长为 n+1 表,
? (a1,a2,...,ai-1,x,ai,ai+1,...,an ) 。
? i 的取值范围为 1<=i<=n+1 。
? 顺序表上完成这一运算需要通过以下步骤进行：
? (1) 将 ai～ an 顺序向下移动，为新元素让出位置；
? (2) 将 x 置入空出的第 i个位置；
? (3) 修改 last 指针 (相当于修改表长 )，使之仍指向最后
一个元素。
1、插入
77北京邮电大学自动化学院
内存
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
78北京邮电大学自动化学院
算法 2.3
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;} // 增加存储容量
}
79北京邮电大学自动化学院
算法 2.3
? 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;} //IistInsert_Sq
80北京邮电大学自动化学院
? 算法的复杂度
? 这里的问题规模是表的长度，设它的值为 n。该算法的时间主
要花费在循环的结点后移语句上，由此可看出，所需移动结点
的次数不仅依赖于表的长度，而且还与插入位置有关。
? 当 =n时，由于循环变量的终值大于初值，结点后移语句将不进
行；这是最好情况，其时间复杂度 O（ 1）；
? 当 =1时，结点后移语句将循环执行 n次，需移动表中所有结
点，这是最坏情况，其时间复杂度为 O（ n）。
? 由于插入可能在表中任何位置上进行，因此需分析算法的平均
复杂度。
81北京邮电大学自动化学院
? 在长度为 n的线性表中第 i个位置上插入一个结点，令 Eis(n)表
示移动结点的期望值（即移动的平均次数），则在第 i个位置
上插入一个结点的移动次数为 n-i+1。故
?
? 不失一般性，假设在表中任何位置 (1≦ i≦ n+1)上插入结点的
机会是均等的，则 p1=p2=p3=…=pn+1=1/(n+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)。
82北京邮电大学自动化学院
? 线性表的删除运算是指将表的第 i(1≦ i≦ n)结点删除，使
长度为 n的线性表：
? (a1,…a i -1,ai,a i+1…, an)
? 变成长度为 n-1的线性表
? (a1,…a i -1,a i+1,…, an)
? 顺序表上完成这一运算的步骤如下：
? (1) 将 ai+1～ an 顺序向前移动。
? (2) 修改 last指针 (相当于修改表长 )使之仍指向最后
一个元素。
2、删除
83北京邮电大学自动化学院
内存
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
84北京邮电大学自动化学院
算法 2.4
? 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; //表尾元素位置
? For (++p; p<=q; ++p)*(p-1)=*p;
? //被删除元素之后的元素左移
? --L.length; //表长减 1
? return OK; } //IistDelete_Sq
85北京邮电大学自动化学院
?
?
??
n
i
idl inqE
1
)(
?
?
???? n
i
dl
nin
nE 1 2
1)(1
86北京邮电大学自动化学院
该算法的时间分析与插入算法相似，结点的移动
次数也是由表长 n和位置 i决定。
假设 qi是删除第 i个元素的概率，则在长度为 n的
线性表中删除一个元素时所需移动元素次数的
期望值（平均次数）为：
不失一般性，假设在表中任何位置上删除结点
的机 会是均等的，则 qi=1/n
因此，在等概率插入的情况下，
也就是说，在顺序表上做删除运算，平均要移
4、算法的存储空间需求
87北京邮电大学自动化学院
? 线性表的顺序表示的特点是用物理位置上的邻接关系来表示结点
间的逻辑关系，这一特点使我们可以随机存取表中的任一结点，
但它也使得插入和删除操作会移动大量的数据元素。
? 由于顺序表需要一组地址连续的存储单元，对于长度可变的线性
表就需要预分配足够的空间，有可能使一部分存储空间长期闲置
不能充分利用。
? 也可能由于估计不足，当表长超过预分配的空间而造成溢出，在
这种情况下，又难于扩充连续的存储空间。
? 为了克服上述缺点，我们将谈论线性表的另一种存储方式链式存
储结构，简称为链表 (Linked List)。
2.3 线性表的链式表示和实现
88北京邮电大学自动化学院
? 线性表的链式存储的特点是指用一组任意的存储单元来依次
存放线性表的结点，这组存储单元既可以是连续的，也可以
是不连续的，甚至是零散分布在内存中的任意位置上的。因
此，链表中结点的逻辑次序和物理次序不一定相同。
? 为了能正确表示结点间的逻辑关系，在存储每个结点值的同
时，还必须存储指示其后继结点的地址（或位置）信息，这
个信息称为指针 (pointer)或链 (link)。这两部分信息组成了元
素 ai的存储映象，称为结点，它包括两个域：
?
? 其中,data域是数据域，用来存放结点的值。 next是指针
域（亦称链域），用来存放结点的直接后继的地址（或位
置）。
data next
2.3.1 线性链表
89北京邮电大学自动化学院
? 链表正是通过每个结点的链域将线性表的 n个结点按其逻辑次序
链接在一起的。
? n个结点（ ai( 1<=i<=n）的存储映象）连接成一个链表，即为
线性表 (a1,a2,…,an) 的链式存储结构。由于上述链表的每一个
结点只有一个链域，故将这种链表称为单链表（ Single
Linked)。
? 链表中每个结点的存储地址是存放在其前驱结点 next域中，而
开始结点无前驱，故应设头指针 head指向开始结点。同时，由
于终端结点无后继，故终端结点的指针域为空，即 NULL（图示
中也可用 ^表示 )。
? 通常我们把线性链表画成用箭头相连接的节点序列，其中箭头
表示链域中的指针。
2.3.1 线性链表
h a1 a2
头结点
an ^…...
90北京邮电大学自动化学院
设 h是指向链表的头指针,p是指向链表中的某一结点的指针，可以说明如下,JD *h,*p;
p及其指向的节点关系如图所示。图中
（ *p）表示由指针所指向的节点。
(*p).data?p->data表示 p指向结点的数据域
(*p).link?p->link表示 p指向结点的指针域
data link
p 结点（ *p）
? 由上述可见，单链表可由头指针唯一确定，在 C语言中可用
“结构指针”来描述：
? typedef struct LNode {
? Elemtype data;
? struct LNode *next;
? } LNode,*Linklist,JD;
91北京邮电大学自动化学院
若 L为“空”（ L=NULL），则所表示的线性表为“空”表，其长度 n为“零”。
h 空表^
h 1145 1248
头结点
2158 ^…...
例如在上图中,h->data=1012
(h->link)->data=1145
(*h).data=1012
p为动态变量，它是通过标准函数生成的，即
p=(listnode*)malloc(sizeof(listnode));
函数 malloc分配了一个类型为 listnode的结点变量的空间，并将其首地址放入指针变量 p中。
一旦 p所指的结点变量不再需要了，又可通过标准函数 free(p) 释放所指的结点变量空间。
data link
p 结点（ *p）
1012
92北京邮电大学自动化学院
? 指针变量 p（其值为结点地址）和结点变量 *p之间的关系。
? p结点是指指针 p所指向的结点（即其存储位置存放在 p中的
结点）。
? 假设 p是指向线性表中第 i个数据元素（结点 ai）的指针，则
p->next是指向第 i+1个数据元素（结点 ai+1）的指针。
? 换句话说，若 p->data=ai，则 p->next->data=ai+1。由此，
在单链表中，取得第 i个数据元素必须从指针出发寻找，因
此，单链表是非随机存取的存储结构。
data link
p 结点（ *p）
h a1 a2
头结点
an ^…...
93北京邮电大学自动化学院
赵 钱 孙 李
周 吴 郑 王 ^
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
头指针
94北京邮电大学自动化学院
?假设线性表中结点的数据类型是字符，我们逐个输
入这些字符型的结点，并以换行符‘ \n’为输入结束
标记。动态地建立单链表的常用方法有如下两种：
?1、头插法建表
? 该方法从一个空表开始，重复读入数据，生成新
结点，将读入数据存放到新结点的数据域中，然
后将新结点插入到当前链表的表头上，直到读入
结束标志为止。
一、建立单链表
95北京邮电大学自动化学院
linklist createlistf(void)
{ char ch; linklist head; listnode *p;
head=null;
ch=getchar( );
while (ch!=‵ \n′{
p=(listnode*)malloc(sizeof(listnode));
p–>data=ch;
p–>next=head; head=p;
ch=getchar( );
}
return (head);
}
96北京邮电大学自动化学院
listlink createlist(int n)
{ int data;
linklist head;
listnode *p
head=null;
for(i=n;i>0;--i){
p=(listnode*)malloc(sizeof(listnode));
scanf((〝 %d〞, &p–>data);
p–>next=head;
head=p;
} return(head);
}
97北京邮电大学自动化学院
?2、尾插法建表
? 头插法建立链表虽然算法简单，但生成的链表中结
点的次序和输入的顺序相反。
?若希望二者次序一致，可采用尾插法建表。该方法
是将新结点插入到当前链表的表尾上，为此必须增
加一个尾指针 r，使其始终指向当前链表的尾结点。
例：
98北京邮电大学自动化学院
linklist creater( ) {
char ch; linklist head;
listnode *p,*r; //(,*head;)
head=NULL;r=NULL;
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); }
99北京邮电大学自动化学院
? 说明：第一个生成的结点是开始结点，将开始结点插入到空
表中，是在当前链表的第一个位置上插入，该位置上的插入
操作和链表中其它位置上的插入操作处理是不一样的，原因
是开始结点的位置是存放在头指针（指针变量）中，而其余
结点的位置是在其前驱结点的指针域中。算法中的第一个 if
语句就是用来对第一个位置上的插入操作做特殊处理。算法
中的第二个 if语句的作用是为了分别处理空表和非空表两种
不同的情况，若读入的第一个字符就是结束标志符，则链表
head是空表，尾指针 r亦为空，结点 *r不存在；否则链表
head非空，最后一个尾结点 *r是终端结点，应将其指针域置
空。
100北京邮电大学自动化学院
?如果我们在链表的开始结点之前附加一个结点，并
称它为头结点，那么会带来以下两个优点：
? a、由于开始结点的位置被存放在头结点的指针域
中，所以在链表的第一个位置上的操作就和在表的
其它位置上的操作一致，无需进行特殊处理；
? b、无论链表是否为空，其头指针是指向头结点
的非空指针（空表中头结点的指针域为空），因此
空表和非空表的处理也就统一了。
101北京邮电大学自动化学院
其算法如下：
linklist createlistr1( ){
char ch; linklist head=(linklist)malloc(sizeof(listnode));
listnode *p,*r;
r=head;
while((ch=getchar( ))!=‵ \n′{
p=(listnode*)malloc(sizeof(listnode));
p–>data=ch;
p–>next=p;
r=p; }
r–>next=NULL;
return(head); }
102北京邮电大学自动化学院
上述算法里动态申请新结点空间时未加错误处理，可作下列处理：
p=(listnode*)malloc(sizeof(listnode))
if(p==NULL)
error(〝 No space for node can be obtained〞 );
return ERROR;
以上算法的时间复杂度均为 O(n)。
103北京邮电大学自动化学院
?1、按序号查找
? 在链表中，即使知道被访问结点的序号 i，也不能象顺
序表中那样直接按序号 i访问结点，而只能从链表的头指
针出发，顺链域 next逐个结点往下搜索，直到搜索到第 i
个结点为止。因此，链表不是随机存取结构。
?设单链表的长度为 n，要查找表中第 i个结点，仅当
1≦ i≦ n时,i的值是合法的。但有时需要找头结点的位
置，故我们将头结点看做是第 0 个结点，其算法如下：
二、查找运算
104北京邮电大学自动化学院
Listnode * getnode(linklist head, int i)
{ int j;
listnode * p;
p=head; j=0;
while(p–>next && j<i) {
p=p–>next;
j++;
}
if (i==j)
return p; else
return NULL;
}
105北京邮电大学自动化学院
? 2、按值查找
? 按值查找是在链表中，查找是否有结点值等于给定值 key的
结点，若有的话，则返回首次找到的其值为 key的结点的存
储位置；否则返回 NULL。查找过程从开始结点出发，顺着
链表逐个将结点的值和给定值 key作比较。其算法如下：
? Listnode * locatenode(linklist head,int key) {
? listnode *p=head–>next;
? while( p && p–>data!=key)
? p=p–>next;
? return p; }
? 该算法的执行时间亦与输入实例中的的取值 key有关，其平
均时间复杂度的分析类似于按序号查找，也为 O(n)。
106北京邮电大学自动化学院
?插入运算是将值为 x的新结点插入到表的第 i个结点
的位置上，即插入到 ai-1与 ai之间。因此，我们必须
首先找到 ai-1的存储位置 p，然后生成一个数据域为
x的新结点 *s，并令结点 *s的指针域指向新结点，新
结点的指针域指向结点 ai,p结点的指针域指向新结
点 s，从而实现三个结点 ai-1,x和 ai之间的逻辑关系
的变化，插入过程如：
p ai-1 ai
xs
s->link=p->link;p->link=s;
三、插入运算
107北京邮电大学自动化学院
具体算法如下,
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));
s–>data=x;
s–>next=p–next;
p–>next=s;
}
p ai-1 ai
xs
s->link=p->link;
p->link=s;
108北京邮电大学自动化学院
?设链表的长度为 n，合法的插入位置是
1≦ i≦ n+1。
?注意当 i=1时,getnode找到的是头结点，
?当 i=n+1时,getnode找到的是结点 an。
?因此，用 i-1做实参调用 getnode时可完成插入位置
的合法性检查。算法的时间主要耗费在查找操作
getnode上，故时间复杂度亦为 O(n)。
109北京邮电大学自动化学院
? 删除运算是将表的第 i个结点删去。因为在单链表中
结点 ai的存储地址是在其直接前驱结点 a i-1的指针域
next中，所以我们必须首先找到 a i-1的存储位置 p。
然后令 p–>next指向 ai的直接后继结点，即把 ai从链
上摘下。最后释放结点 ai的空间，将其归还给“存储
池”。
p ai-1 ai ai+1
p->link=p->link->link;
四、删除运算
110北京邮电大学自动化学院
具体算法如下,
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 ) ;
}
111北京邮电大学自动化学院
? 设单链表的长度为 n，则删去第 i个结点仅当 1≦ i≦ n时是合法
的。注意，当 i=n+1时，虽然被删结点不存在，但其前驱结
点却存在，它是终端结点。因此被删结点的直接前趋 *p存在
并不意味着被删结点就一定存在，仅当 *p存在（即
p!=NULL）且 *p不是终端结点
? （即 p–>next!=NULL）时，才能确定被删结点存在。
? 显然此算法的时间复杂度也是 O(n)。
? 从上面的讨论可以看出，链表上实现插入和删除运算，无
须移动结点，仅需修改指针。
112北京邮电大学自动化学院
? 1、在头指针为 h的带表头结点的单链表中，把结点 b插入
到 a结点之前，若不存在结点 a就把结点 b插入到表尾。
? 插入过程：
?找到结点 a时,p指向结点,q指向结点 a的直接前驱结
点。
?首先生成一个 s结点，将 s结点的数据域置为 b，然后修
改相应的指针，把结点 a作为 s结点的直接后继，把 s结
点作为 q结点的直接后继。
五、链表的其他运算示例
113北京邮电大学自动化学院
? Void dlbqcr(JD *h,int a,int b)
? {//在头指针为 h的带表头结点的单链表中结点 a之前插入结点 b，若表中无结点 a，则插到
表尾
? JD*p,*q,*s;
? 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;)
? {q->link=s;s->link=p;}//找到结点时，把结点插到结点 a之前
? Else{p->link=s;s->link=NULL;}//表中无结点 a，则插到表尾 }
114北京邮电大学自动化学院
? 2、设线性表的 n个数据元素依次存放在一维数组 a[n]中，请建立
一个带表头结点的单链表,h为新建单链表的指针。
? 要建立一个带表头结点的单链表，首先生成一个 h结点作为表结
点，其链域置为“空”。
? 在生成一个 s结点，将其数据域置为第 n个数据元素，链域置为
“空”。 s结点作为表中第一个结点。
? 顺次生成新的 s结点，置其数据域为第 i个数据元素 (i=n-1,n-
2,…,2,1),修改有关指针：把表中第一个结点作为 s结点的直接后
继,s结点作为表中第一个结点。即把含第 i个数据元素的结点插
入到表中第一个结点之前。
115北京邮电大学自动化学院
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);}
116北京邮电大学自动化学院
? 3、设 h是带表头结点的单链表的头指针，请设计一个逆置这
个单链表的算法。
? 建立逆表的方法是：顺序扫描原表，依次将原表中的结点逐
个插入到第一个结点之前，可得到逆置链表。
? 设 s指向当前逆转结点,p指向 s结点的直接后继结点。
? Void dlbnz(JD*h){ JD*s,*p;
? p=h->link;// *p先指向原表中第一个结点
? h->link=NULL;//逆表的初态为空表
? While(p!=NULL)
? {s=p;// *s指向当前逆转的结点
? p=p->link;
? s->link=h->link;
117北京邮电大学自动化学院
? 4、设 pa,pb分别为两个按升序排列的单链表的头指
针，请设计一个算法把这两个单链表合并为一个按升序
排列的单链表。
? 合并的方法是：从两表的第一个结点开始顺链逐个将对
应数据元素进行比较，复制小者并插入 c表尾。当两表
中之一已到表尾，则复制另一链表的剩余部分，插入到
c表尾。
? /JD*dlnhb(JD *pa,JD*pb)
? {//把 pa,pb为头指针的按升序排列的单链表合并成一
个按升序排列的单链表。
? JD *p,*q;*pc;
? pc=(JD)malloc(sizeof(JD)); p=pc;
118北京邮电大学自动化学院
While(pa!=NULL && pb!=NULL)
{
q=(JD* )malloc (sizeof(JD));
If (pb->data<pa->data)
{q->data=pb->data; pb=pb->link;}
Else { q->data=pa->data; pa=pa->link;
If (pa->data==pb->data) pb=pb->link； }
p->link=q;
p=q;
}
119北京邮电大学自动化学院
While(pa!=NULL)
{ q=(JD*)malloc(sizeof(JD));
q->data=pa->data;
pa=pa->link; p->link=q; p=q;
}
While(pb!=NULL)
{ q=(JD*)malloc(sizeof(JD));
q->data=pb->data;
pb=pb->link; p->link=q; p=q;
}
p->link=NULL
p=pc;
pc=p->link;
free(p)
return(pc);}
120北京邮电大学自动化学院
? 循环链表是一种头尾相接的链表。其特点是无须增加存储
量，仅对表的链接方式稍作改变，即可使得表处理更加方便
灵活。
? 单循环链表：在单链表中，将终端结点的指针域 NULL改为
指向表头结点或开始结点，就得到了单链形式的循环链表，
并简单称为单循环链表。
? 为了使空表和非空表的处理一致，循环链表中也可设置一个
头结点。这样，空循环链表仅有一个自成循环的头结点表
示。如下图所示：
2.3.2 循环链表
121北京邮电大学自动化学院
h
⑴ 非空表
h
⑵ 空表
? 在用头指针表示的单链表中，找开始结点 a1的时间是
O(1)，然而要找到终端结点 an，则需从头指针开始遍历整
个链表，其时间是 O(n)。
122北京邮电大学自动化学院
? 在很多实际问题中，表的操作常常是在表的首尾位置上进
行，此时头指针表示的单循环链表就显得不够方便,如果改用
尾指针 rear来表示单循环链表，则查找开始结点 a1和终端结
点 an都很方便，它们的存储位置分别是 (rear–>next) —
>next和 rear，显然，查找时间都是 O(1)。因此，实际中多
采用尾指针表示单循环链表。
? 由于循环链表中没有 NULL指针，故涉及遍历操作时，其终
止条件就不再像非循环链表那样判断 p或 p—>next是否为
空，而是判断它们是否等于某一指定指针，如头指针或尾指
针等。
123北京邮电大学自动化学院
例、在链表上实现将两个线性表 (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;
ha—>next=p—>next; //a,b两个线性表尾首相连
hb—>next=q;// a,b两个线性表首尾相连
ha=hb;
free(p);//释放 hb表头结点
}
124北京邮电大学自动化学院
?单链表有一个很大的缺点：它只能顺着直接后继指针向
后查找其他结点，如若找某结点的直接前驱结点，只能
从表头指针开始查找。换句话说，在单链表中，
NextElem的执行时间为 O(1)，而 PriorElem的执行时间
为 O（ n）。
?为了克服单链表这种单向性的缺点，双向链表可有效解
决这个问题。
?双向链表 (Double linked list):在单链表的每个结点里再
增加一个指向其直接前驱的指针域 prior。这样形成的链
表中就有两个方向不同的链，故称为双向链表。
2.3.3双链表
125北京邮电大学自动化学院
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）
结点定义
126北京邮电大学自动化学院
? 和单链表类似，双链表一般也是由头指针唯一确定的，增加
头指针也能使双链表上的某些运算变得方便，将头结点和尾
结点链接起来也能构成循环链表，并称之为双向链表。
? 设指针 p指向某一结点，则双向链表结构的对称性可用下式
描述,(p—>prior)—>next=p=(p—>next)—>prior
? 即结点 *p的存储位置既存放在其前趋结点 *(p—>prior)的直
接后继指针域中，也存放 在它的后继结点 *(p—>next)的直
接前趋指针域中。
? 在双链表中，有些操作如,ListLength,GetElem和
LocateElem等仅需要涉及一个方向的指针，则它们的算法
描述和线性链表的操作相同，但在插入和删除操作时有很大
的不同，在双链表中插入和删除必须同时修改两个方向上的
指针。上述两个算法的时间复杂度均为 O(n)。
127北京邮电大学自动化学院
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步
}
128北京邮电大学自动化学院
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);
}
129北京邮电大学自动化学院
130北京邮电大学自动化学院
从本节的讨论中可见：由于链表在空间的合理利
用上和插入、删除时不需要移动等优点，因此
在很多场合下，它是线性表的首选存储结构。
然而它也存在着实现某些基本操作如求线性表长
度时不如顺序存储结构的缺点；另一方面，由
于在链表中，节点之间的关系用指针来表示，
则数据元素在线性表中的“位序”的概念已淡
化，而被数据元素在线性表链表中的“位置”
所代替。
为此，从实际应用角度出发重新定义线性链表及
其基本操作（见 P37~38）。
4、算法的存储空间需求
131北京邮电大学自动化学院
nnn xPxPxPPxP ????? ??2210)(
? 多项式的运算问题，已经成为表处理的一个经典问题。通
常一个多项式 Pn(x)可按升密写成：
2.4一元多项式相加
),,,210 nqqqqQ ??（?
),,,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 ?? ???????（
132北京邮电大学自动化学院
20 00 010 00 231)( xxxS ???
mee emn xPxPxPxP ???? ??21 21)(
为非零系数）（ im Peee ??? ??210
? 至此，一元多项式的表示及相加问题似乎已经解决。然而，在
通常的应用中，多项式的次数可能很高且变化很大，使得顺序
存储结构的最大长度很难确定。特别是在处理式的次数可能很
高且变化很大，使得顺序存储结构的最大长度很难确定。特别
是在处理形如：
2.4一元多项式相加
? 的多项式时，就要用一长度为 20001的线性表来表示，表中仅
有 3个非零元素，这种对内存空间浪费应当避免。
? 但是如果只存储非零系数项，显然必须同时存储相应的指数。
? 一般情况下的一元 n次多项式可写成：
? 其中,pi是指数为 ei的项的非零系数，且满足：
133北京邮电大学自动化学院
emmn xPxPxPxP ee ???? ??21 21)(
? ? ? ? ? ?? ?emPePeP m,，，，,??21 21
? 若用一个长度为 m且为每个数据元素有两个数据项（系数项和
指数项）的线性表
2.4一元多项式相加
? 便可唯一确定多项式 Pn(x)。在最坏情况下,n+1(=m)个系数都
不为零，则比只存储每项系数的方案要多一倍的数据。但是，
对于 S(x)类的多项式，这种表示将大大节省空间。
? 对应于线性表的两种存储结构，由上式定义的一元多项式也可
以有两种存储表示方法。在实际的应用程序中取用哪一种，则
要视多项式作何种运算而定。
? 若只对多项式进行“求值”等不改变多项式的系数和指数的运
算，则采用类似于顺序表的顺序存储结构即可，否则应采用链
式存储结构。本节中将主要讨论如何利用线性链表的基本操作
来实现一元多项式的运算。
134北京邮电大学自动化学院
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、单链表的结点定义
135北京邮电大学自动化学院
设 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）运算规则
136北京邮电大学自动化学院
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）算法描述
137北京邮电大学自动化学院
1、单链表操作
（ 1）建立带表头结点的单链表 h；
（ 2）打印单链表 h中所有结点的数据域值；
（ 3）输入 x,y。在第 1结点 x后插入 y，若无结
点 x，则在表尾插入结点 y；
（ 4）输入 k，删除单链表中所有的结点 k，并输
出被删除结点个数。
作业：以手写文档形式
4、算法的存储空间需求
138北京邮电大学自动化学院
第二章 习题
?1、单链表操作
?（ 1）建立带表头结点的单链表 h；
?（ 2）打印单链表 h中所有结点的数据域值；
?（ 3）输入 x,y。在第 1结点 x后插入 y，若无结点
x，则在表尾插入结点 y；
?（ 4）输入 k，删除单链表中所有的结点 k，并输出
被删除结点个数。
?作业：以手写文档形式
139北京邮电大学自动化学院
3.1 栈
3.2 栈的应用举例
3.3 队列
第三章 栈和队列
140北京邮电大学自动化学院
?1 栈的定义
?栈 (Stack)是限制在表的一端进行插入和删除运算的
线性表，通常称插入、删除的这一端为栈顶 (Top)，
另一端为栈底 (Bottom)。当表中没有元素时称为空
栈。
? 假设栈 S=(a1,a2,a3,…an),则 a1称为栈底元
素,an为栈顶元素。栈中元素按 a1,a2,a3,…an
的次序进栈，退栈的第一个元素应为栈顶元素。换句
话说，栈的修改是按后进先出的原则进行的。因此，
栈称为后进先出表（ LIFO）。
3.1.1抽象数据类型栈的定义
141北京邮电大学自动化学院
图 3.1栈的示意图
? 只允许在一端插入和删除
的顺序表
? 允许插入和删除的一端称
为栈顶 (top)，另一端称
为栈底 (bottom)
? 特点,
? 后进先出 (LIFO)
142北京邮电大学自动化学院
? （ 1）初始化
? （ 2）进栈
? （ 3）退栈
? （ 4）取栈顶元素
? （ 5）判栈是否非空
? （ 6）置栈空
2、栈的基本操作
143北京邮电大学自动化学院
? ADT stack{
? 数据对象,D={ai|ai?ElemSet,i=1,2,…,n,n>=0)}
? 数据关系,R1={<ai-1,ai>|ai-1,ai ?D} 约定 an为栈顶,a1端为
栈底
? 基本操作：
? Initstack(&s)
? 操作结果：构造一个空栈 s
? Destroystack(&s)
? 初始条件：栈已经存在
? 操作结果：栈 s被销毁
? Clearstack(&S)
3、栈的抽象数据类型的定义
144北京邮电大学自动化学院
? StackEmpty(&s)
? 初始条件：栈已经存在
? 操作结果：若栈 S为空,
则返回 TRUE,否则 FALSE.
? StackLength(&s)
? 初始条件：栈 S已经存
在
? 操作结果：返回栈 S的
元
? 素个数,即栈的长度,
? GetTop(S,&e)
3、栈的抽象数据类型的定义
? Push (&s,e)
? 初始条件, 栈 S已经存在
? 操作结果：插入元素 e
为
? 新的栈顶元素,
? Pop(&s,&e)
? 初始条件：栈已经存在
且
? 非空
? 操作结果：删除 S的栈
顶
145北京邮电大学自动化学院
和线性表类似，栈也有两种存储表示方法。顺序栈、链栈。
3.1.2 栈的表示和实现
顺序表,即栈的顺序存储结构是利用一组地址连续的存储单
元依次存放自栈底到栈顶的数据元素．同时附设指针 top指
示栈顶元素在顺序表中的位置,
通常的习惯做法是以 top=0表示空栈,鉴于 C语言中数组的下
标约定从 0开始,则当以 C语言作描述语言时,如此设定会带来
很大不方便 ;
另一方面,由于栈在使用过程中所需要最大空间的大小很难
估计,因此,一般来说,在初始化设计空栈时不应限定栈的最大
容量,
一个合理的做法是,先为栈分配一个基本容量,然后在应用过
程中,当栈的空间不够使用时再逐段扩大,
146北京邮电大学自动化学院
为此设定两个常量,STACK_INIT_SIZE(存储空间初始分配量 )
和 STACKINCREMENT(存储空间分配增量 ),并以下述类型说明
作为顺序栈的定义,
其中,stacksize指示栈的当前可使用的最大容量,栈的初始化操作
为, 按设定的初始分配量进行第一次存储分配,base可称为栈底
指针,在顺序标中,它始终指向栈底的位置,若 base的值为 NULL,
则表明栈结构不存在,
typedef Struct{
SElemType *base;
SElemType *top;
int stacksize; }SqStack;
1,顺序栈
147北京邮电大学自动化学院
例、一叠书或一叠盘子。
a n
a n-1
a2
a1
……
top
base
1,顺序栈
? 称 top为栈顶指针,其初始值指
向栈底,即 top=base可作为栈
空的标记,每当插入新的栈顶
元素时,指针 top增 1;删除栈顶
元素时,指针 top减 1,因此,非空
栈中的栈顶指针始终在栈顶元
素的下一位置上,右图展示了
顺序栈中数据元素和栈顶指针
之间的对应关系,
148北京邮电大学自动化学院
进栈示例
退栈示例
149北京邮电大学自动化学院
基本操作的算法描述
（ 1）置空栈
void initstack(seqstack *s)
{
s–>top=-1;
}
（ 2）判断栈空
int stackempty(seqstack *s)
{
return(s–>top==-1);
}
150北京邮电大学自动化学院
（ 3）判断栈满
int stackfull(seqstack *s)
{
return(s–>top==stacksize-1);
}
（ 4）进栈
void push(seqstack *s,datatype x)
{
if (stackfull(s))
error(―stack overflow‖);
s–>data[++s–>top]=x;
}
151北京邮电大学自动化学院
（ 5）退栈
datatype pop(seqstack *s)
{
if(stackempty(s))
error(―stack underflow‖);
x=s–>data[top];
s–>top--;
return(x)
//return(s–>data[s–>top--]);
}
152北京邮电大学自动化学院
（ 6）取栈顶元素
Datatype stacktop(seqstack *s)
{
if(stackempty(s)
error(―stack is enpty‖);
return s–>data[s–>top];
}
153北京邮电大学自动化学院
? 栈的链式存储结构称为链栈，它是运算受限的单链表，插
入和删除操作仅限制在表头位置上进行。由于只能在链表
头部进行操作，故链表没有必要像单链表那样附加头结
点。栈顶指针就是链表的头指针。
? 链栈的类型说明如下：
? typedef struct stacknode {
? datatype data
? struct stacknode *next
? }stacknode;
2,链栈
154北京邮电大学自动化学院
链式栈无栈满问题
空间可扩充
插入与删除仅在栈顶处执行
链式栈的栈顶在链头
适合于多栈操作
? 链式栈的特点：
栈的链接表示 — 链式栈
155北京邮电大学自动化学院
计
算
顺
序
输
出
顺
序
? 例 1,数制转换
? 十进制数 N和其他 d进制数的转换是计算机实现计算的基本
问题,其中一个简单算法基于下列原理,
? N=(N div d)?d+N mod d
? 例如,（ 1348)10 = (2504)8,其运算过程如下：
?N N div 8 N mod
?1348 168 4
?168 21 0
?21 2 5
?2 0 2
3.2 栈的应用举例
156北京邮电大学自动化学院
void conversion () {
//对于输入的任意一个非负十进制整数,打印输出与
其等值的八进制数
InitStack(S); //构造空栈
scanf ("%d",N);
while (N) {
Push(S,N % 8);
N = N/8;
}
while (!StackEmpty(S)) {
Pop(S,e);
printf ( "%d",e );}
} // conversion
例 1、数制转换
157北京邮电大学自动化学院
? 假设在表达式中允许包含两种括号,园括号和方括号,其嵌套
是随意,并假定 （［］（））或［（［ ］［ ］）］等为正确
的格式,
? ［（ ］）或（［（ ））或 (( )])均为不正确的格式。
? 检验括号是否匹配的方法,可用“期待的急迫程度”这个概
念来描述,
分析可能出现的不匹配的情况,
到来的右括弧非是所“期待”的 ;
到来的是“不速之客” ;直到结束，也没有到来所
“期待”的括弧 ;。
例 2,括号匹配的检验
例如：考虑下列括号序列：
[ ( [ ] [ ] ) ]
1 2 3 4 5 6 7 8
158北京邮电大学自动化学院
[ ( [ ] [ ] ) ]
1 2 3 4 5 6 7 8
? 当计算机接受了第 1个括号后，它期待着与其匹配的第 8个括
号的出现，然而等来的却是第 2个括号，此时第 1个括号,[‖
只能暂时靠边，“期待的急迫程度”最高是第 2个括号
“（” 。
? 而迫切等待与第 2个括号“（”相匹配的第 7个扩号“）”的
出现，类似地，因等来的是第 3个括号,[‖,其期待匹配的程
度较第 2个括号更急迫,则第 2个括号也只能靠边，让位于第 3
个括号,[‖,显然第 2个括号,(‖的期待急迫性高于第 1个括号
,[‖;
? 在接受了第四个括号,]‖之后,第 3个括号的期待得到满足,消
解之后，第 2个括号的期待匹配就成为当前最急迫的任务
了,……,依次类推,
可见这个处理过程恰好与栈的特点相吻合,
159北京邮电大学自动化学院
算法的设计思想
? 1）凡出现左括弧，则进栈； 自然使原有的在栈中的所有
未消解的期待的急迫性都降了一级。
? 2）凡出现右括弧，首先检查栈是否空
?若栈空，则表明该“右括弧”多余
3）表达式检验结束时，
若栈空，则表明表达式中匹配正确
否则表明“左括弧”有余
否 则和栈顶元素比较
否则表明不匹配
若相匹配，
则“左括弧出栈”
160北京邮电大学自动化学院
Status matching(string& exp) {
int state = 1;
while (i<=Length(exp) && state) {
switch of exp[i] {
case ―(‖:{Push(S,exp[i]); i++; break;}
case ―)‖,{
if(NOT StackEmpty(S) && GetTop(S)=― (‖)
{Pop(S,e); i++;}
else {state = 0;}
break; } … … }
if (StackEmpty(S) && state) return OK; …...
161北京邮电大学自动化学院
如何实现？
―每接受一个字符即存入存储器”?
并不恰当！
例 3、行编辑程序问题
? 合理的作法是：设立一个输入缓冲区，用以接受用户输入
的一行字符，然后逐行存入用户数据区 ; 并假设,#‖为退格
符，,@‖为退行符。
? 在用户输入一行的过程中，允许用户输入出差错，并在发
现有误时可以及时更正。
? 一个简单的行编辑程序的功能是,接受用户从终端输入
的程序或数据,并存入用户的数据区,
162北京邮电大学自动化学院
? 例如,当用户发现刚刚输入的一个字符是错的时候,可以补进
一个,#‖,以表示前一个字符无效 ;
? 如果发现当前输入的行内差错太多或难以补救,则可以键入
一个退行符,@‖,以表示当前行中的字符均无效,
? 假设从终端接受了这样两行字符：
? whli##ilr#e（ s#*s)
? outcha@putchar(*s=#++);
? 则实际有效的是下列两行：
? while (*s)
? putchar(*s++);
163北京邮电大学自动化学院
while (ch != EOF && ch != '\n') {
switch (ch) {
?case ?#‘, Pop(S,c); break;//仅当栈非空时退栈
?case '@',ClearStack (S); break;// 重置 S为空栈
? default, Push(S,ch); break; //有效字符进栈 }
? ch = getchar(); // 从终端接收下一个字符 }
ClearStack (S); // 重置 S为空栈
if (ch != EOF) ch = getchar();}
while (ch != EOF) { //EOF为全文结束符
将从栈底到栈顶的字符传送至调用过程的数据区；
164北京邮电大学自动化学院
求迷宫中从入口到出口的所有路径是一个经典的程序设计问
题,计算机解迷宫问题，通常用的是“穷举求解”的方法。
# # # # # # # # # #
# ? ? # $ $ $ # #
# ? # $ $ $ # #
# ? ? $ $ # # #
# ? # # # # #
# ? ? ? # # #
# # ? ? ? # #
# # # # # ? # # #
# ? ? ? ? #
# # # # # # # # # #
例 4,迷宫求解
165北京邮电大学自动化学院
? 即从入口出发，顺某一方向向前探索，若能走通，则继续往
前走；否则沿原路退回，换一个方向再继续探索，直到所有
可能的通路都探索到为止。
? 为了保证在任何位置上都能沿原路退回，显然需要用一个后
进先出的结构来保存从入口到当前位置的路径。因此，在求
迷宫通路的算法中应用“栈”也就是自然而然的事了。
? 首先，在计算机可以用图所示的方块表示迷宫。途中的每个
方块或为通道（以白方块表示），或为墙（以带阴影的方块
表示）。所求路径必须是简单路径，即在求得的路径上不能
重复出现同一通道块。
166北京邮电大学自动化学院
? 假设“当前位置”指的是“在搜索过程中某一时刻所在图中某
个方块的位置”，则求迷宫中一条路径的算法的基本思想是：
? 若当前位置“可通”，则纳入路径，并继续朝“下一个位置”
探索，即切换“下一位置”为“当前位置”,如此重复直至到达
出口；
? 若当前位置“不可通”，则应顺着“来向”退回到“前一通道
块”，然后朝着除“来向”之外的其它方向继续探索；
?若该通道块的四周 4个方块均“不可通”，则应从“当前路
径”上删除该通道块。所谓“下一位置”指的是“当前位
置”四周四个方向（东、南、西、北）上相邻的方块。? 假设以栈 S记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。由此，“纳入路径”的操作即为“当前
位置入栈”；,从当前路径上删除前一通道块”的操作即为
“出栈”。
167北京邮电大学自动化学院
? 假设以栈 S记录“当前路径”，则栈顶中存放的是“当前路径
上最后一个通道块”。由此，“纳入路径”的操作即为“当前
位置入栈”；,从当前路径上删除前一通道块”的操作即为
“出栈”。? 求迷宫中一条从入口到出口的路径的算法：
? 设定当前位置的初值为入口位置；
? do｛
? 若当前位置可通，
? 则｛ 将当前位置插入栈顶； //纳入路径
? 若该位置是出口位置，则算法结束； //求得路径
? 否则切换当前位置的东邻方块为新的当前位置；｝
? 否则 { 见下一页 }
? ｝ while (栈不空） ；
168北京邮电大学自动化学院
do｛
若当前位置可通，则｛ 见上一页｝ ;
否则
若栈不空且栈顶位置尚有其他方向未被探索，
则设定新的当前位置为, 沿顺时针方向旋转找到的栈顶
位置的下一相邻块；
若栈不空但栈顶位置的四周均不可通，
则｛
删去栈顶位置； // 从路径中删去该通道块
若栈不空，则重新测试新的栈顶位置,直至找
到一个可通的相邻块或出栈至栈空； }
｝｝ while (栈不空）；
若栈空，则表明迷宫没有通路。
169北京邮电大学自动化学院
? 在此，尚需要说明一点的是，所谓当前位置可通，指的是未
曾走到过的通道块，即要求该方块的位置不仅是通道块，而
且既不在当前路径上（否则所求路径就不是简单路径），也
不是曾经纳入过路径的通道块（否则只能在死胡同内转
圈）。
? Typedef struct{
? Int ord; // 通道块在路径上的“序号”
? PosType seat; // 通道块在迷宫中的“坐标位置”
? Int di; // 从此通道块走向下一通道块的“方向”
? }SElemType; / / 栈的元素类型
170北京邮电大学自动化学院
Status Mazepath(MazeType maze,PosType start,PosType end){
//若迷宫中存在从入口到出口的通道,则求得一条存放在栈中 (从
//栈底到栈顶 ),并返回 TRUE;否则返回 FLASE;
InitStack(S);curpos=start;//设定“当前位置”为“入口位置”
Curstep=1;//探索第一步
Do {If ( pass(curpos )) { //当前位置可以通过，即是未曾走过的通道块
FootPrint ( curpos ); //留下足迹
e=(curstep,curpos,1);
Push(S,e);//加入路径
If( curpos==end) return (TRUE); //到达终点（出口）
curpos=NextPos(curpos,1);//下一位置是当前位置的东邻
Curstep++;} //探索下一步
}// if
171北京邮电大学自动化学院
Else{//当前位置不通
If (!StackEmpty(S)){
Pop(S,e);
While(e.di==4&&!StackEmpty(S)){
MarkPrint(e.seat)； Pop(S,e);//留下不能通过的标记，
并退回一步 }//while
If(e.di<4){
e.di++; Push(S,e);//换下一个方向探索
Curpos=NextPos(e.seat,e.di);//设定当前位置是该新方向上的
相邻块 }//if }// if }//else
} while (!StackEmpty(S ));
Return(FALSE);
}//MazePath
172北京邮电大学自动化学院
# # # # # # # # # #
# # # #
# # # #
# # # #
# # # # # #
# # # #
# # # #
# # # # # # # #
# ? #
# # # # # # # # # #
?
? ?
??
?
?
?
?
???
?
1 1 1
1 2 2
2 2 2
3 2 1
3 3 1
3 4 4
2 4 1
2 5 1
2 6 4
1 6 3
1 5 3
1 4 4
3
$ $ $
$$$
$$
173北京邮电大学自动化学院
? 例如 要对下面的表达式求值,4+2*3-10/5
?首先要了解算术四则运算的规则。即是：
? 先乘除，后加减
? 从左到右
? 先括号内，后括号外
?由此，这个算术表达式的计算顺序应为：
? 4+2*3-10/5
? =4+6-10/5
? =10-10/5
? =10-2=2
?任何一个表达式都是有操作数、运算符和界限符组成的，我们把运算符
和界限符统称为算符，它们构成的集合命名为 OP。
例 5,表达式求值
174北京邮电大学自动化学院
根据上述三条运算规则，在运算的每一步中，任意两个相继出现
的算符 Q1和 Q2之间的优先关系至多是下面的三种关系之一：
Q1<Q2 Q1的优先权低于 Q2
Q1=Q2 Q1的优先权等于 Q2
Q1>Q2 Q1的优先权高于 Q2
为了实现算符优先算法，可以使用两个工作栈。 一个称做 OPTR，
用以寄存运算符；另一个称做 OPND，用以积存操作数或运算结
果。 算法的基本思想是：
首先置操作数栈为空栈，表达式起始符,#‖为运算符栈的栈底元
素；
依次读入表达式中每个字符，若是操作数则进 OPND栈，若是运
算符，则和 OPTR栈的栈顶运算符比较优先权后作相应操作，直
至整个表达式求值完毕（即 OPTR栈顶元素和当前读入的字符均
为,#‖）。
175北京邮电大学自动化学院
OperandType EvaluateExpression(){
//设 OPTR和 OPND分别为运算符栈和运算数栈
InitStack(OPTR);Push(OPTR,‘#‘);
InitStack(OPND);c=getchar();
While(c!=‘#‘||GetTop(OPTR)!=―#‘){
If(!In(c,OP)） {Push((OPND,c);c=getchar();}//不是运算
符则进栈
Else
Switch Precede(GetTop(OPTR),c)){
Case ―<?,//栈顶元素优先权低
Push(OPTR,c);c=getchar();break;
Case ―=?,//脱括号接收下一字符
Pop(OPTR,x);c=getchar();break;
176北京邮电大学自动化学院
While(c!=‘#‘||GetTop(OPTR)!=―#‘){
If(!In(c,OP)） {Push((OPND,c);c=getchar();}//
Else
Switch Precede(GetTop(OPTR),c)){
Case ―<?:Push(OPTR,c);c=getchar();break;
Case ―=?:Pop(OPTR,x);c=getchar();break
Case ―>?,//退栈并将运算结果入栈
Pop(OPTR,theta);
Pop(OPND,b); Pop(OPND,a);
Push(OPND,Operate(a,theta,b));break; }
}//while
Return GetTop(OPND);
}//EvaluateExpression
177北京邮电大学自动化学院
步骤 OPTR栈 OPND栈 输入字符 主要操作
RETURN(GETTOP(OPND))
1 # 3*(7-2)# PUSH(OPND,‘3‘)
2 # 3 *(7-2)# PUSH(OPTR,‘*‘)
3 #* 3 (7-2)# PUSH(OPTR,‘(‘)
4 #*( 3 7-2)# PUSH(OPND,‘7‘)
5 #*( 37 -2)# PUSH(OPTR,‘-‘)
6 #*(- 37 2)# PUSH(OPND,‘2‘)
7 #*(- 372 )# operate(?7‘,‘-‘,‘2‘)
8 #*( 35 )# Pop(OPTR)
9 #* 35 # operate(?3‘,‘*‘,‘5‘)
10 # 15 #
178北京邮电大学自动化学院
例 6 栈与递归的实现
当在一个函数的运行期间调用另一个函数时，在运行
该被调用函数之前，需先完成三项任务：
将所有的实在参数、返回地址等信息传递给被调用函数保
存 ;
为被调用函数的局部变量分配存储区 ;
将控制转移到被调用函数的入口保存被调函数的计算结果 ;
从被调用函数返回调用函数之前，应该完成下列三项
任务：
保存被调函数的计算结果 ;
释放被调函数的数据区 ;
依照被调函数保存的返回地址将控制转移到调用函数。
179北京邮电大学自动化学院
多个函数嵌套调用的规则是,
此时的内存管理实行,栈式管理
”
后调用先返回 ！
例如：
void main( ){ void a( ){ void b( ){
… … …
a( ); b( );
… …
}//main }// a }// b
Main的数据区
函数 a的数据区
函数 b的数据区
180北京邮电大学自动化学院
栈的应用
过程的嵌套调用
r
主
程
序
s
rr
r
s
子
过
程
1 r
s
t
子
过
程
2 rs
t 子过
程
3
181北京邮电大学自动化学院
例 递归的执行情况分析
递归过程及其实现
递归：函数直接或间接的调用自身叫 ~
实现：建立递归工作栈
void print(int w)
{ int i;
if ( w!=0)
{ print(w-1);
for(i=1;i<=w;++i)
printf(―%3d,‖,w);
printf(―/n‖);
}
}
运行结果：
1，
2,2，
3,3,3，
182北京邮电大学自动化学院
递归调用执行情况如下：
主程序
(1)
print(w)
w=3;
3
print(2);
（ 1） w=3
top
(2) 输出,3,3,3
w
2
print(1);
（ 2） w=2
（ 1） w=3
top
(3) 输出,2,2
w 1
print(0);
（ 3） w=1
（ 2） w=2
（ 1） w=3
top
(4)输出,1
w
0
（ 4） w=0
（ 3） w=1
（ 2） w=2
（ 1） w=3
top
w
(2) 2
(1) 3
输出：
(3) 1
(2) 2
(1) 3
top
(1 ) 3
返回
(3)
(2)
(1) 3
top (4)
结束
183北京邮电大学自动化学院
解决方法：
n=1时，直接把圆盘从 A移到 C
n>1时，先把上面 n-1个圆盘从 A移到 B,然后将 n号盘从 A移到 C,再将 n-1个盘从 B移到 C
。 即把求解 n个圆盘的 Hanoi问题转化为求解 n-1个圆盘的 Hanoi问题，依次类推，直
至转化成只有一个圆盘的 Hanoi问题
执行情况,递归工作栈保存内容：形参 n,x,y,z和返回地址,返回地址用行编号表示
n x y z 返回地址
Tower of Hanoi问题
问题描述：有 A,B,C三个塔座,A上套有 n个直径不同的圆盘，按直径从小到
大叠放，形如宝塔,编号 1,2,3…… n。 要求将 n个圆盘从 A移到 C,叠放顺序不
变，移动过程中遵循下列原则：
每次只能移一个圆盘
圆盘可在三个塔座上任意移动
任何时刻，每个塔座上不能将大盘压到小盘上 A B C
12
3
184北京邮电大学自动化学院
void hanoi (int n,char x,char y,char z) {
// 将塔座 x上按直径由小到大且至上而下编号为 1至 n
// 的 n个圆盘按规则搬到塔座 z上,y可用作辅助塔座。
1 if (n==1)
2 move(x,1,z); // 将编号为１的圆盘从 x移到 z
3 else {
4 hanoi(n-1,x,z,y); // 将 x上编号为１至 n-1的
//圆盘移到 y,z作辅助塔
5 move(x,n,z); // 将编号为 n的圆盘从 x移到 z
6 hanoi(n-1,y,x,z); // 将 y上编号为１至 n-1的
//圆盘移到 z,x作辅助塔
7 }
8 }
185北京邮电大学自动化学院
main()
{ int m;
printf("Input number of disks”);
scanf("%d",&m);
printf(”Steps, %3d disks”,m);
hanoi(m,'A','B','C');
(0) }
void hanoi(int n,char x,char y,char z)
(1) {
(2) if(n==1)
(3) move(1,x,z);
(4) else{
(5) hanoi(n-1,x,z,y);
(6) move(n,x,z);
(7) hanoi(n-1,y,x,z);
(8) }
(9) }
A B C
12
3
3 A B C 0
3 A B C 0
2 A C B 6
3 A B C 0
2 A C B 6
1 A B C 6
A B C
3 A B C 0
2 A C B 6
186北京邮电大学自动化学院
main()
{ int m;
printf("Input the number of disks
scanf("%d",&m);
printf("The steps to moving %3d
hanoi(m,'A','B','C');
(0) }
void hanoi(int n,char x,char y,char z)
(1) {
(2) if(n==1)
(3) move(1,x,z);
(4) else{
(5) hanoi(n-1,x,z,y);
(6) move(n,x,z);
(7) hanoi(n-1,y,x,z);
(8) }
(9) }
A B C
3 A B C 0
2 A C B 6
1 C A B 8
A B C
3 A B C 0
2 A C B 6
3 A B C 0
3 A B C 0
2 A C B 6
187北京邮电大学自动化学院
main()
{ int m;
printf("Input the number of disks
scanf("%d",&m);
printf("The steps to moving %3d
hanoi(m,'A','B','C');
(0) }
void hanoi(int n,char x,char y,char z)
(1) {
(2) if(n==1)
(3) move(1,x,z);
(4) else{
(5) hanoi(n-1,x,z,y);
(6) move(n,x,z);
(7) hanoi(n-1,y,x,z);
(8) }
(9) }
A B C
3 A B C 0
2 B A C 8
3 A B C 0
2 B A C 8
1 B C A 6
A B C
3 A B C 0
2 B A C 8
3 A B C 0
188北京邮电大学自动化学院
main()
{ int m;
printf("Input the number of disks
scanf("%d",&m);
printf("The steps to moving %3d
hanoi(m,'A','B','C');
(0) }
void hanoi(int n,char x,char y,char z)
(1) {
(2) if(n==1)
(3) move(1,x,z);
(4) else{
(5) hanoi(n-1,x,z,y);
(6) move(n,x,z);
(7) hanoi(n-1,y,x,z);
(8) }
(9) }
A B C
3 A B C 0
2 B A C 8
1 A B C 8
A B C
3 A B C 0
2 B A C 8
3 A B C 0
栈空
3 A B C 0
2 B A C 8
189北京邮电大学自动化学院
链式栈无栈满问题
空间可扩充
插入与删除仅在栈顶处执行
链式栈的栈顶在链头
适合于多栈操作
? 链式栈的特点：
栈的链接表示 — 链式栈
190北京邮电大学自动化学院
3.3队列
? 3.3.1 抽象数据类型队列的定义
? 队列 (Queue)也是一种运算受限的线性表。它只允许在表的
一端进行插入，而在另一端进行删除。允许删除的一端称为
队头 (front)，允许插入的一端称为队尾 (rear)。
? 例如：排队购物。操作系统中的作业排队。先进入队列的成
员总是先离开队列。因此队列亦称作先进先出 (First In First
Out)的线性表，简称 FIFO表。
? 当队列中没有元素时称为空队列。在空队列中依次加入元素
a1,a2,…an 之后,a1是队头元素,an是队尾元素。显然退出
队列的次序也只能是 a1,a2,…an,也就是说队列的修改是依
先进先出的原则进行的。
191北京邮电大学自动化学院
出队 入队
队头 队尾
下图是队列的示意图：
a1 a2 a3 an
队列的抽象数据定义见书Ｐ 59
双端队列,就是限定插入和删除操作在表的两端进
行的线性表。
尽管双端队列看起来似乎比栈和队列更灵活，但实
际上在应用程序中远不及栈和队列有用，故在此不
作详细讨论。
192北京邮电大学自动化学院
设队首、队尾指针 front和 rear,
front指向头结点,rear指向队尾
? 队列的链式存储结构简称为链队列，它是限制仅在表头删
除和表尾插入的单链表。显然仅有单链表的头指针不便于
在表尾做插入操作，为此再增加一个尾指针，指向链表的
最后一个结点。
3.3.2 链队列
头结点
…...front
队头 队尾
rear
193北京邮电大学自动化学院
front rear
x入 队 ^x
front rear
y入 队 x ^y
front rear
x出 队 x ^y
front rear
空队 ^
front rear
y出 队 ^
194北京邮电大学自动化学院
我们也是将这两个指针封装在一起，将链队列的类型
LinkQueue定义为一个结构类型：
链队列结点定义
typedef struct Qnode
{ QElemType data;
struct QNode *next;
} QNode,*QueuPtr;
?Typedef struct{
QueuPtr front;//对头指针
QueuPtr rear;//对尾指针
} LinkQueue
195北京邮电大学自动化学院
下面给出链队列上实现的基本运算：
void initqueue(linkqueue *q)//构造一个空队列
{
q–>front=q–>rear=null;
}
int queueempty(linkqueue *q)//若队列 Q为空队列，
则返回 TRUE，否则返回 FALSE
{
return q–>front==null &&q–>rear==null;
}
196北京邮电大学自动化学院
Status EnQueue( LinkQueue *Q,QElemType e)
//插入元素 e为 Q的新的队尾元素； {
p=(QueuePtr * )malloc ( sizeof(QNode));
if (!p) exit (OVERFLOW);//存储分配失败
p–>data=e;
p–>next=NULL;
Q.rear->next=p;
Q.rear=p;
return OK;}
197北京邮电大学自动化学院
Status DeQueue(LinkQueue &Q,QElemType &e)
//若队列不空，则删除 Q的队头元素，用 e返回其值，并返回
OK；否则返回 ERROR {
if( Q.front==Q.rear) return ERROR;
p=Q.front->next;
e=p–>data;
Q–>front->next=p–>next;
if(Q.rear==p) Q.rear=Q.front;
free(p);
return OK;}
注意,在出队算法中，一般只需修改队头指针。但当原队
中只有一个结点时，该结点既是队头也是队尾，故删去此
结点时亦需修改尾指针，且删去此结点后队列变空。
198北京邮电大学自动化学院
3.3.2 循环队列－队列的顺序表示和实现
?队列的顺序存储结构称为顺序队列，在队列的顺序存储
结构中，除了用一组地址连续的储存单元依次存放从对
头到对尾的元素之外，尚需要附设两个指针 front和 rear
分别指示队列头元素和队列尾元素的位置。
?为了在 C语言中描述方便起见，在此我们约定：初始化
建空队列时，令 front＝ rear＝ 0。每当插入新的队列尾
元素时“尾指针增 1‖；每当删除队列头元素时“头指针
增 1‖。
?因此，在非空队列中，头指针始终指向队头元素，而尾
指针始终指向队尾元素的下一位置。
199北京邮电大学自动化学院
J1
J2
J3
rear
设两个指针 front,rear,约定,在非
空队列中,front始终 指 向对头元
素； Rear始终 指 向队列 尾元素 的
下一位置 ；初值 front=rear=0
空队列条件,front==rear
入队列,sq[++rear]=x;
出队列,x=sq[++front];
rear
rear
front
front
front
front
队列的顺序存储结构
实现：用一维数组实现 sq[M]
1
2
3
4
5
0front
J1,J1,J3入队
rear
1
2
3
4
5
0
J1,J2,J3出队
J1
J2
J3
rear
1
2
3
4
5
0
J4,J5,J6入队
J4
J5
J6
front
front=0
rear=0
1
2
3
4
5
0
队空
200北京邮电大学自动化学院
存在问题
设数组维数为 M,则：
当 front=0,rear=M-1时，再有元素入队发生溢出 ——真溢出
当 front?0,rear=M-1时，再有元素入队发生溢出 ——假溢出
解决方案
队首固定，每次出队剩余元素向下移动 ——浪费时间
循环队列
基本思想：把队列设想成环形，让 sq[0]接在 sq[M-1]之后，
若 rear+1==M,则令 rear=0;
rear
1
2
3
4
5
0
J4,J5,J6入队
J4
J5
J6
front
0
M-1
1
front
rear 实现：利用“模”运算
入队, rear=(rear+1)%M;
sq[rear]=x;
出队, front=(front+1)%M
x=sq[front];
队满、队空判定条件
201北京邮电大学自动化学院
J4
J5
J6
0
123
4 5
rear
front
J9
J8
J7
队满,front==rear
解决方案：
1.另 外设一个标志 以区别队空、队满
2.少用一个元素空间，约定以“队列头
指针在队列尾指针的下一位置上”，
作为队列呈“满”状态的标志。
队空,front==rear
队满,(rear+1)%M==front
J4
J5
J6
0
123
4 5
rear
front
初始状态
1
234
5 0
rear
front
202北京邮电大学自动化学院
第 3章 习题
?1、设将整数以 1,2,3,4依次进栈，但只要出栈
时栈非空，则可将出栈操作按任何次序夹入其中，
请回答下有问题：
?（ 1）若入栈次序为 push(1),pop(),push(2，
push(3),pop(),pop( ),push(4),pop( )，则
出栈的数字序列为什么？
?（ 2）能否得到出栈序列车员 423和平共处五项原
则 432？并说明为什么不能得到或如何得到。
203北京邮电大学自动化学院
谢 谢 !
数据结构
北京邮电大学自动化学院
杨福兴
电话,13331090202
E-mail,yangfx@sina.com
2004年 9月 13日
2北京邮电大学自动化学院
? 使用教材：
?严蔚敏 吴伟民 编著,数据结构（ C语言
版），清华大学出版社
? 参考书：
?1、曹桂琴 编著，数据结构基础，大连理工大
学出版社。
?2、晋良颖 编，数据结构，人民邮电出版社
?3,Bruno R.Preiss，数据结构与算法，电子
工业出版社
使用教材及参考书
3北京邮电大学自动化学院
? 许晓燕 负责班级,1～ 2班
?电 话,13121868069
? E-mail,ingo@tom.com
? 吴 魏 负责班级,3～ 4班
?电 话,13810354850
? E-mail,wilson_nuaa@163.com
? 徐 刚 负责班级,5~6班
?电 话,13311321087
? E-mail,werhh@163.com1
,数据结构, 辅导老师名单
4北京邮电大学自动化学院
课程教学目的
? 在计算机及其应用的各个领域中，都会用到各种
各样的数据结构，通过本课程使学生学会分析和
研究计算机加工对象的特性，选择合适的数据结
构和存储表示，以及编制相应的实现算法．
? 课程教学基本要求,本课程介绍各种最常用的数据
结构，阐述各种数据结构内涵的逻辑关系，讨论
它们在计算机中的存储表示，以及在这些数据结
构上的运算和实际的执行算法，并对算法的效率
进行简要的分析和讨论。
5北京邮电大学自动化学院
? 数据结构的研究不仅涉及到
? 计算机硬件 （特别是编码理论、存储装置和存取
方法）的研究范围，
? 而且和 计算机软件 的研究有着密切的关系，无论
是编译程序还是操作系统，都涉及到数据元素在
存储器中的分配问题。
? 在研究 信息检索时 也必须考虑如何组织数据，以
便查找和存取数据元素更为方便。
课程介绍
6北京邮电大学自动化学院
? 因此，可以认为 数据结构 是介于 数学、计算机硬件
和计算机软件 三者之间的一门核心课程。
? 程序＝算法＋数据结构
? 目前在我国,,数据结构, 已经不仅仅是计算机专
业的教学计划中的核心课程之一，而且是其它非计
算机专业的主要选修课程之一。
? 通过对这门课程的学习可增强选择合适的数据结构
与编写高效的程序的能力。
课程介绍
7北京邮电大学自动化学院
教学安排及考试
? 讲课学时,34学时
? 上机时间,5次（每次 2学时）
? 考试成绩计算：
?平时成绩（考勤,作业及上机） 30分
?考试（ 70分）
? 考查课和考试课分别考试，考查课在第 17周考
试，考试课按学校安排时间考试。
8北京邮电大学自动化学院
目录
? 第 1章 绪论
? 第 2章 线性表
? 第 3章 栈和队列 第 4章 串
? 第 5章 数组和广义表
? 第 6章 树和二叉树
? 第 7章 图
? 第 8章 查找
? 第 9章 内部排序
? 第 10章 文件
9北京邮电大学自动化学院
? 计算机的应用已不再局限于科学计算，而更多地
用于控制、管理及数据处理等 非数值计算的处理
工作 。
? 与此对应，计算机加工处理的对象由纯粹的数值
发展到 字符、表格和图像 等各种具有一定结构的
数据。
? 为了编写出一个“好”的程序，必须分析 待处理
的对象的特征以及各对象之间存在的关系,这就
是“数据结构”这门学科形成和发展的背景。
第一章 绪 论
第一章 绪 论
10北京邮电大学自动化学院
?1.1 什么是数据结构
?1.2 基本概念和术语
?1.3 抽象数据类型的表示与实现
?1.4 算法和算法分析
第一章 绪 论
11北京邮电大学自动化学院
? 一般来说，用计算机解决一个具体问题时，大致需要经多下
列几个步骤：
?首先要从具体问题抽象出一个适当的数学模型
?然后设计一个解此数学模型的算法，
?最后编出程序、进行测试、调整直至得到最终解答。
? 寻求数学模型的实质是分析问题，从中提取操作的对象，并
找出这些操作对象之间含有的关系，然后用数学的语言加以
描述。
? 然而，更多的非数值问题无法用数学方程描述。什么是数据
结构呢？先看以下几个例子。
1.1 什么是数据结构
12北京邮电大学自动化学院
0 0 1 高等数学 樊映川 S 0 1
0 0 2 理论力学 罗远祥 L 0 1
0 0 3 高等数学 华罗庚 S 0 1
0 0 4 线性代数 栾汝书 S 0 2
…… …… …… ……
书目文件
按书名 按作者名 按分类号
高等数学 001, 003 ……
理论力学 002, ……,.
线性代数 004, ……
…… ……,.
樊映川 001,…
华罗庚 002,…,
栾汝书,…,
……, ……,
L 002,…
S 0 0 1,0 0 3,
…… ……
索引表
线性表
例 1 书目自动检索系统
登录号：
书名：作者名：
分类号：出版单位：
出版时间：价格：
书目卡片
13北京邮电大学自动化学院
树
……..……..
…..,…..,…..,…...
例 2 人机对奕问题
14北京邮电大学自动化学院
? 对于一个多叉路口，设计一
个交通信号灯的管理系统。
? 首先需要分析一下所有车辆
的行驶路线的冲突问题。
? 这个问题可以归结为对车辆
的可能行驶方向作某种分
组，对分组的要求是使任一
个组中各个方向行驶的车辆
可以同时安全行驶而不发生
碰撞。
C
E
D
A
B
例 3 多叉路口交通灯管理问题
15北京邮电大学自动化学院
可通行方向
?A?B A?C A ?D
?B ?A B?C B?D
?D?A D?B D ?C
?E ?A E?B E?C E?D
C
E
D
A
B
例 3多叉路口交通灯管理问题
16北京邮电大学自动化学院
有些通行方向显然不能同时进行，相应的结点间画一条连线。
AB AC AD
BA BC BD
DA D B DC
EA EB EC ED
图 1.2 交叉路口的图示模型
C
E
D
A
B
图
17北京邮电大学自动化学院
? 把图 1.2中的结点进行分组，使得有结点相连的结点不
在同一个组里。
? 地图着色问题
? 如果把上图中的一个结点理解为一个国家,结点之间
的连线看作两国有共同边界，上述问题 就变成著名的
“着色问题”,即求出最少要几种颜色可将图中所有
国家着色，使得任意两个相邻的国家颜色都不相同。
? 通过上面的分析，我们就获得了该交通管系统的数学
模型。下面就可以着手进行算法的设计。
例 3多叉路口交通灯管理问题
18北京邮电大学自动化学院
算法设计
? 2,―贪心法”
? while 有结点未着色；
? { 选择一种新颜色；
? 在未着色的结点中,给尽可能多的彼此结点之间没有边
点着色；
? }
? 1,对 n个结点，逐个测试其所有组合；
例 3多叉路口交通灯管理问题
19北京邮电大学自动化学院
AB AC AD
BA BC BD
DA D B DC
EA EB EC ED
图 1.2 交叉路口的图示模型
图
AB AC AD
BA BC BD
DA DB DC
EA EB EC ED
C
E
D
A
B
着色结果
20北京邮电大学自动化学院
? 把上面方法应用于图 1.2，得到下面的分组：
? 绿色,AB,AC,AD,BA,DC,ED
? 蓝色,BC,BD,EA
? 红色,DA,DB
? 白色,EB,EC
例 3多叉路口交通灯管理问题
21北京邮电大学自动化学院
? 综上三个例子，描述这类非数值计算问题的数学模型
不再是数学方程，而是诸如 表、树和图 之类的数据结
构。
? 因此，简单说来，数据结构是一门 研究非数值计算的
程序设计问题中 计算机的操作对象以及它们之间的关
系和操作等等的学科 。
? 数据结构就是研究数据的逻辑结构和物理结构它们之
间相互关系，并对这种结构定义相应的运算，而且确
保经过这些运算后所得到的新结构仍然是原来的结构
类型。
第一章 绪 论
22北京邮电大学自动化学院
? 数据 (Data):是对客观事物的符号表示，在计算机科
学中是指 所有能输入到计算机中并被计算机程序处
理的符号的总称。
? 对计算机科学而言，数据的含义极为广泛，如图
像、声音等都可以通过编码而归之于数据的范畴。
? 数据元素 (Data Element):是数据的基本单位，在计
算机程序中通常作为一个整体进行考虑和处理。
? 例如，例 1－ 2中的“树”中的一个棋盘格局，例 1
－ 3中的“图”中的一个园圈都被称为一个数据元
素。
1.2 基本概念和术语
23北京邮电大学自动化学院
? 一个数据元素可由若干个数据项组成。例如，例 1－ 1中一
本书的书目信息为一个数据元素，而书目信息中的每一项
（如书名、作者名等）为一个数据项。
? 数据项是数据的不可分割的最小单位 。
? 数据对象 (Data Object),是性质相同的数据元素的集合，
是数据的一个子集。例如，整数数据对象是集合 N＝ {0，
± 1,± 2,… }，字母字符数据对象是集合 C＝ {A,B，
C,…} 。
? 数据结构 (Data Structure),是相互之间存在一种或多种
特定关系的数据元素的集合。
1.2 基本概念和术语
24北京邮电大学自动化学院
? 数据结构主要指逻辑结构和物理结构。 数据之间的相互关系称
为逻辑结构 。通常分为四类基本结构：
? 一、集合 结构中的数据元素除了同属于一种类型外，别无其
它关系。
? 二、线性结构 结构中的数据元素之间存在一对一的关系。
? 三、树型结构 结构中的数据元素之间存在一对多的关系。
? 四、图状结构或网状结构 结构中的数据元素之间存在多对多
的关系。
1.2 基本概念和术语
25北京邮电大学自动化学院
? 数据结构的形式定义为：数据结构是一个二元组：
? Data-Structure=(D,S)
? 其中,D是数据元素的有限集,S是 D上关系的有限
集。
? 例 复数的数据结构定义如下,Complex=(C,R)
? 其中,C是含两个实数的集合 ﹛ C1,C2﹜,分别表
示复数的实部和虚部。 R={P},P是定义在集合上的
一种关系 {〈 C1,C2〉 }。
1.2 基本概念和术语
26北京邮电大学自动化学院
? 数据结构在计算机中的表示称为数据的物理结构，又称为
存储结构。
? 数据结构在计算机中有两种不同的表示方法：
? 顺序表示和非顺序表示
? 由此得出两种不同的存储结构,顺序存储结构和链式存储
结构
? 顺序存储结构,用数据元素在存储器中的相对位置来表示
数据元素之间的逻辑关系。
? 链式存储结构,在每一个数据元素中增加一个存放地址的
指针,用此指针来表示数据元素之间的逻辑关系。
1.2 基本概念和术语
27北京邮电大学自动化学院
元素 n
……..
元素 i
……..
元素 2
元素 1L
o
Lo+m
Lo+(i-1)*m
Lo+（ n-1)*m
存储地址 存储内容
Loc(元素 i)=Lo+（ i-1)*m
顺序存储
28北京邮电大学自动化学院
1536元素 21400元素 1 1346元素 3 ∧元素 4
1345h
存储地址 存储内容 指针
1345 元素 1 1400
1346 元素 4 ∧
……, ……,,……,
1400 元素 2 1536
……, ……,,……,
1536 元素 3 1346
链式存储
h
29北京邮电大学自动化学院
数据的逻辑结构
数据的存储结构
数据的运算：检索、排序、插入、删除、修改等
线性结构
非线性结构
顺序存储
链式存储
线性表
栈
队
树形结构
图形结构
数据结构的三个方面：
1.2 基本概念和术语
30北京邮电大学自动化学院
? 数据类型,数据类型是一个值的集合和定义在这个值集范围
上的一组操作的总称。例如,C语言中的整型变量，其值集
为某个区间上的整数，定义在其上的操作为：加、减、乘、
除和取模等算术运算。
? 按“值”的不同特性，高级程序语言中的数据类型可分为：
? 一类是非结构的原子类型 。原子类型的值是不可分解的。
如,C语言中的基本类型（整型、实型、字符型和枚举类
型）、指针类型和空类型。
? 另一类是结构类型 。结构类型的值是由若干成分按某种结构
组成的。例如数组的值由若干分量组成。每个分量可以是整
数，也可以是数组等。
1.2 基本概念和术语
31北京邮电大学自动化学院
? 抽象数据类型：一个数学模型以及定义在该模型上的一组操
作。 抽象数据类型的定义仅取决于它的一组逻辑特性，而与
其在计算机内部如何表示和实现无关，即不论其内部结构如
何变化，只要它的数学特性不变，都不影响其外部的使用。
? 抽象数据类型实际上就是对该数据结构的定义。因为它定义
了一个数据的逻辑结构以及在此结构上的一组算法。
? 和数据结构的形式定义相对应，抽象数据类型可用三元组描
述如下,（Ｄ，Ｓ，Ｐ）
? D是数据对象,S是 D上的关系集,P是对 D的基本操作集。
1.2 基本概念和术语
32北京邮电大学自动化学院
? 本书采用以下格式定义抽象数据类型
? 抽象数据类型的定义：
ADT抽象数据类型名 {
数据对象,<数据对象的定义 >
数据关系,<数据逻辑关系的定义 >
基本操作,<基本操作的定义 >
? }ADT抽象数据类型名
? 基本操作的定义格式为：
基本操作名（参数表）
初始条件,<初始条件描述 >
? 操作结果,<操作结果描述 >
1.2 基本概念和术语
33北京邮电大学自动化学院
? 抽象数据类型三元组的定义：
? ADT Triplet{
? 数据对象,D={e1,e2,e3|e1,e2,e3?ElemSet}
? 数据关系,R1={<e1,e2>,<e2,e3>}
? 基本操作：
? InitTriplet(&T,v1,v2,v3)
? 操作结果,构造了三元组 T，元素 e1,e2和 e3分别赋以参数
v1,v2和 v3的值。
? } ADT Triplet
1.2 基本概念和术语
34北京邮电大学自动化学院
? ADT Triplet{
? 数据对象, D={e1,e2,e3|e1,e2,e3?ElemSet}
? 数据关系, R1={<e1,e2>,<e2,e3>}
? 基本操作,
? Get(T,i,&e)
? 初始条件,三元组 T已存在,1?i?3
? 操作结果,用 e返回 T的第 i元的值。
? } ADT Triplet
1.2 基本概念和术语
35北京邮电大学自动化学院
? 抽象数据类型 可通过固有数据类型来表示和实现，即利
用处理器中已存在的数据类型来说明新的结构，用已经
实现的操作来组合新的操作。
? 由于本书在高级程序设计语言的虚拟层次上讨论抽象数
据类型的表示和实现，并且讨论的数据结构及其算法主
要是面向读者，故采用 介于伪码和 C语言之间的类 C语
言作为描述工具,有时也用伪码描述一些只含抽象操作
的抽象算法。
? 这使得数据结构和算法的描述和讨论简明清晰，不拘泥
于 C语言的细节，又能容易转换成 C或者 C＋＋程序。
1.3 抽象数据类型的表示和实现
36北京邮电大学自动化学院
? 本书采用的类 C语言精选了 C语言的一个核心子集，同时作了
若干扩充，增强了语言的描述功能。以下对其作简要说明。
? （ 1）预定义常量和类型
? //函数结果状态代码
? #define TRUE 1 #define FLASE 0
? #define OK 1 #define ERROR 0
? #define INFEASIBLE -1 #define OVERFLOW -2
? // Status是函数的类型，其值是函数结果状态代码
? Typedef int Status;
1.3 抽象数据类型的表示和实现
37北京邮电大学自动化学院
? （ 2）数据结构的表示用类型定义（ typedef）描述。
数据元素类型约定为 Elemtype，由用户在使用该数据
类型时定义。
? （ 3）基本操作的算法都用以下形式的函数描述：
?函数类型 函数名 （函数参数表） {
?//算法说明
?语句序列
?}//函数名
1.3 抽象数据类型的表示和实现
38北京邮电大学自动化学院
? （ 4）赋值语句有
?简单赋值 变量名 =表达式；
?串值赋值 变量名 1=变量名 2=……= 表达式
?成组赋值 （变量名 1，。。。，） =（表达式
1，）
?交换赋值 变量名 ? 变量名
?条件赋值 变量名 =条件表达式？表达式 T：表
达式 F
1.3 抽象数据类型的表示和实现
39北京邮电大学自动化学院
? （ 5）选择语句有
? 条件语句 1 if（表达式）语句；
? 条件语句 2 if（表达式）语句； Else 语句
? 开关语句 1 switch(表达式 ) {
? case 值 1：语句序列 1； break;
? Default,语句序列 n+1;}
? 开关语句 2 switch{
? case 条件 1：语句序列 1； break;
? Default,语句序列 n+1;}
1.3 抽象数据类型的表示和实现
40北京邮电大学自动化学院
? （ 6）循环语句有
? For语句
? for（赋初值表达式；条件；修改表达式序列）语句；
? While 语句 while（条件）语句；
? do-while语句
? do {
? 语句序列 }while（条件）；
1.3 抽象数据类型的表示和实现
41北京邮电大学自动化学院
? （ 7）结束语句
?函数结束语句 return 表达式； return；
?Case结束语句 break;
?异常结束语句 exit(异常代码 )
? 8）输入和输出语句
? 输入语句 scanf([格式串 ]，变量 1，变量 n)；
? 输出语句 printf([格式串 ]，表达式 1，表达式 2)；
1.3 抽象数据类型的表示和实现
42北京邮电大学自动化学院
? （ 9）注释
? 单行注释 //文字序列
? （ 10）基本函数有
? 求最大值 max(表达式 1，表达式 n）
? 求最小值 min(表达式 1，表达式 n）
? 求绝对值 abs(表达式 )
? 求不足整数值 floor（表达式）
? 判定行结束 eoln（文件变量）或 eoln
1.3 抽象数据类型的表示和实现
43北京邮电大学自动化学院
? （ 11）逻辑运算约定
? 与运算 &&,对于 A &&B,当 A的值为 0时,不再对 B
求值。
? 或运算 ||,对于 A||B,当 A的值为非 0时,不再对 B
求值。
1.3 抽象数据类型的表示和实现
44北京邮电大学自动化学院
? 例题：抽象数据类型 Triplet的表示和实现
? //--------采用动态分配的顺序存储结构 ----------------
? Typedef ElemType *Triplet://initTriplet分配三个元素存
储空间
? //--------基本操作的函数原形说明 ----------------
? Status InitTriplet (Triplet &T,ElemType v1,ElemType
v2,ElemType v3）；
? //操作结果：构造了三元组 T，元素 e1,e2和 e3分别赋以参
数 v1,v2和 v3的值。
1.3 抽象数据类型的表示和实现
45北京邮电大学自动化学院
? Status DestroyTriplet (Triplet &T）；
?//操作结果：三元组 T被消除。
? Status Get (Triplet &T,int i,ElemType &e）；
?//初始条件：三元组 T已存在,1?i?3 。
? //操作结果：用 e返回 T的第 i元的值。
1.3 抽象数据类型的表示和实现
46北京邮电大学自动化学院
? //--------基本操作的实现 ----------------
? Status Get (Triplet &T,int i,ElemType &e） {
? // 1?i?3,用 e返回 T的第 i元的值。
? If (i<1||i>3) return ERROR;
? e=T [i-1] ；
? return OK;
? }//Get
? } ADT Triplet
1.3 抽象数据类型的表示和实现
47北京邮电大学自动化学院
? 算法是对特定问题求解步骤的一种描述，它是指令的有限序
列，每一条指令表示一个或多个操作。 1、算法有五个特性：
? （ 1）有穷性 一个算法必须总是在执行有穷步之后结束，且
每一步都在有穷时间内完成。
? （ 2）确定性 算法中每一条指令必须有确切的含义。不存在二
义性。且算法只有一个入口和一个出口。
? （ 3）可行性 一个算法是可行的。即算法描述的操作都是可以
通过已经实现的基本运算执行有限次来实现的。
? （ 4）输入 一个算法有零个或多个输入。
? （ 5）输出 一个算法有一个或多个输出。
1.4 算法和算法分析
48北京邮电大学自动化学院
? 评价一个好的算法有以下几个标准,
? （ 1） 正确性
? （ 2）可读性 算法应该好读。
? （ 3）健状性 算法应具有容错处理。当输入非法数据
时，算法应对其作出反应，而不是产生莫名其妙的输
出结果。
? （ 4）效率与存储量需求 效率是指算法执行的时
间；存储量需求指算法执行过程中所需要的最大存储
空间。
2,算法设计的要求
49北京邮电大学自动化学院
? 程序不含语法错误。
? 程序对于几组输入数据能够得出满足规格说
明的结果。
? 程序对于精心选择的典型、苛刻而带有刁难
性的几组输入数据能够得出满足规格说明的
结果。
? 程序对于一切合法的输入数据都能产生满足
规格说明的结果。
正确性（算法应满足具体问题的需求）
50北京邮电大学自动化学院
? 算法执行时间需要通过依据该算法编制的程序在计算机上运行时
所消耗的时间度量。度量一个程序的执行时间通常有两种方法。
? 事后统计的方法
?一是必须先运行依据算法编制的程序
?二是所得时间的统计量依赖于计算机的硬件、软件等环境
因素求出该算法的一个时间界限函数
? 事前分析估算的方法
?依据的算法选用何种策、问题的规模、书写的语言、编译
程序所产生的机器代码的质量、机器执行指令的速度。
? 所以，人们常常采用事前分析估算的方法。
3,算法效率的度量
51北京邮电大学自动化学院
? 使用绝对的时间单位衡量算法的效率是不合适的。 撇开这些
与计算机硬件软件有关的因素，可以认为一个特定算法的
“运行工作量”的大小，只依赖于 问题的规模 （通常用整数
量表示），或者说,它是问题规模的函数。
? 一个算法是由控制结构（顺序分支和循环三种）和原操作
（指固有数据类型的操作）构成的，则算法时间取决于两者
的综合效果。
? 为了便于比较同一问题的不同算法,通常的做法是，从算法
中选取一种对于研究问题（或算法类型）来说是基本操作的
原操作，以该基本操作重复执行的次数作为算法的时间量
度。
3,算法效率的度量
52北京邮电大学自动化学院
? 整个算法的执行时间与该基本操作（乘法）重复执行的次数
n3成正比，记为 T(n)=O(n3)
? for(i=1;i<=n;++i)
? for(j=1;j<=n;++j){ c[i][j]=0;
? for(k=1;k<=n;++k) c[i][j]+=a[i][k]*b[k][j];}
? 一般情况下，算法中基本操作重复执行的次数是问题规模 n
的某个函数 f(n),算法的时间度量记作 T(n)=O(f(n))
? 它表示随着问题规模 n的增加，算法执行时间的增长率和
f(n)的增长率相同,称作算法的渐进时间复杂度，简称时间
复杂度。
? 例 1，在如下所示的两个矩阵相乘的算法中，“乘法”运算是
“矩阵相乘问题”的基本操作。
53北京邮电大学自动化学院
? 显然，被称作问题的基本操作的原操作应是其重复执行次数
和算法的执行时间成正比的原操作，多数情况下它是最深层
循环内的语句中的原操作,它的执行次数和包含它的语句的
频度相同。
? 语句的频度是指的是该语句重复执行的次数。
? 例２ {++x;s=0;}
? 将 x自增看成是基本操作，则语句频度为 １,即 时间复杂度
为Ｏ (1)。
? 如果将 s=0也看成是基本操作，则语句频度为 ２,其 时间复
杂度仍为Ｏ (1)，即常量阶。
3,算法效率的度量
54北京邮电大学自动化学院
? 例３,for(i=1;i<=n;++i) {++x;s+=x;}
?语句频度为,2n
?其时间复杂度为,O(n)
?即时间复杂度为线性阶。
? 例４,for(i=1;i<=n;++i)
? for(j=1;j<=n;++j) {++x;s+=x;}
?语句频度为,2n2
?时间复杂度为,O(n2)
?即时间复杂度为平方阶。
3,算法效率的度量
55北京邮电大学自动化学院
? 定理：若 A(n)=amnm +am-1nm-1 +…+a 1n+a0是一个 m次多项
式，则 A(n)=O(nm)。证略。
? 例５ for(i=2;i<=n;++I)
? for(j=2;j<=i-1;++j) {++x;a[i,j]=x;}
? 语句频度为,1+2+3+…+n -2=(1+n-2) × (n-2)/2
? =(n-1)(n-2)/2 =n2-3n+2
?时间复杂度为 O(n2),
? 即此算法的时间复杂度为平方阶。
3,算法效率的度量
56北京邮电大学自动化学院
? 以下六种计算算法时间的多项式是最常用的。其关系为：
? O(1)<O(logn)<O(n)<O(nlogn) <O(n2)<O(n3)
? 指数时间的关系为：
? O(2n)<O(n!)<O(nn)
? 当 n取得很大时，指数时间算法
和多项式时间算法在所需时间上
非常悬殊。 因此，只要有人能将
现有指数时间算法中的任何一个
算法化简为多项式时间算法，那
就取得了一个伟大的成就。
3,算法效率的度量
57北京邮电大学自动化学院
? 有的情况下，算法中基本操作重复执行的次数还随问题
的输入数据集不同而不同。例如：
? Void bubble-sort(int a[],int n)
? for(I=n-1;change=TURE;I>1 && change;--I) {
? change=false; for(j=0;j<I;++j)
? if (a[j]>a[j+1]) { a[j] ←→a[j+1];change=TURE} }
? 最好情况,0次 最坏情况,1+2+3+…+n -1=n(n-1)/2
? 平均时间复杂度为,O(n2)
? 在本书以后各章节中讨论的时间复杂度，除特别指明
外，均指最坏情况下的时间复杂度。
3,算法效率的度量
58北京邮电大学自动化学院
? 类似于算法的时间复杂度，本书中以空间复杂
度作为算法所需存储空间的量度，记作,
? S(n)=O(f(n))
? 其中 n为问题的规模 (或大小 )。
? 一个上机执行的程序除了需要存储空间来寄存
本身所用指令、常数、变量和输入数据外，也
需要一些对数据进行操作的工作单元和存储一
些为实现计算所需信息的辅助空间。
4、算法的存储空间需求
59北京邮电大学自动化学院
? 线性结构的特点,在数据元素中的非空有限集中
? （ 1）存在 唯一 的一个被称作,第一”的数据元素；
? （ 2）存在 唯一 的一个被称作,最后一个”的数据元
素；
? （ 3） 除第一个外,集合中的每一个数据元素均 只有
一个前驱；
? （ 4） 除最后一个外,集合中的每一个数据元素均 只
有一个后继。
第二章 线性表
60北京邮电大学自动化学院
?2.1 线性表的类型定义
?2.2 线性表的顺序表示和实现
?2.3 线性表的链式表示和实现
?2.4 一元多项式的表示及相加
第二章 线性表
61北京邮电大学自动化学院
? 1、线性表
? 线性表 (Linear List), 一个线性表是 n个数据元素的
有限序列。例如：
? 例 1,26个英文字母组成的字母表
?（ A,B,C,…, Z）
? 例 2、某校从 1999年到 2003年各种型号的计算机拥
有量的变化情况。
?（ 6,17,28,50,92,188）
2.1 线性表的类型定义
62北京邮电大学自动化学院
? 在稍复杂的线性表中，一个数据元素可以由若干个数据项组
成。在这种情况下，常把 数据元素称为记录, 含有大量记录的
线性表又称为文件。
? 例 3、学生健康情况登记表如下：
姓 名 学 号 性 别 年龄 健康情况
王小林 790631 男 18 健康
陈 红 790632 女 20 一般
刘建平 790633 男 21 健康
张立立 790634 男 17 神经衰弱
…….,…….,……,……,…….
1、线性表
63北京邮电大学自动化学院
? 综合上述三个例子可见，线性表中的数据元素可以是各种各样
的，但同一线性表中的元素必定具有相同特征，即属同一数据
对象，相邻数据元素之间存在着序偶关系。若将线性表记为：
? (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、线性表
64北京邮电大学自动化学院
? 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。
? DestroyList(&L)
? 初始条件,线性表 L已经存在。
? 操作结果,销毁线性表 L。
2、抽象数据类型线性表
65北京邮电大学自动化学院
? ClearList(&L)
? 初始条件,线性表 L已经存在。
? 操作结果,将 L置为空表。
? ListEmpty(L)
? 初始条件,线性表 L已经存在。
? 操作结果,若 L为空表，则返回 TRUE，否则返回
FALSE。
2、抽象数据类型线性表
66北京邮电大学自动化学院
? ListLength(L)
? 初始条件,线性表 L已经存在。
? 操作结果,返回 L中数据元素个数。
? GetElem(L,i,&e)
? 初始条件,线性表 L已经存在，
1?i?Listlength(L)。
? 操作结果,用 e返回 L中第 i数据各元素的值。
? … …
2、抽象数据类型线性表
67北京邮电大学自动化学院
? LocateElem(L,e,compare())
? 初始条件,线性表 L已经存在,compare是数据元素判定函数。
? 操作结果,返回 L中第一个与 e满足关系 compare()的数据元素的
位序。若这样的元素不存在，则返回值为零为。
? ListInsert(&L,i,e)
? 初始条件,线性表 L已经存在，且 1?i ? Listlength(L)＋ 1。
? 操作结果,在 L中第 i个位置之前插入新的数据元素 e,L的长度加 1
? … …
? } ADT List
2、抽象数据类型线性表
68北京邮电大学自动化学院
? 例 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、例题
69北京邮电大学自动化学院
? 例 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）
? 从上面的问题要求可知,LC中的数据元素或是 LA中的数据元
素，或是 LB中的数据元素，则只要先设 LC为空表，然后将 LA或
LB中的元素逐个插入到 LC中即可。设两个指针 i和 j分别指向 LA
和 LB中某个元素，
??
?
?
??
时，当
时当
bab
baac,
3、例题
70北京邮电大学自动化学院
? 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
71北京邮电大学自动化学院
? 上述两个算法的时间复杂度取决于抽象数据类型 list定义中基本
操作的执行时间。假如 GetElem和 ListInsert这两个操作的执行
时间和表长无关,LocateElem的执行时间和表长成正比。
? 则算法 2.1的时间复杂度为
?O（ ListLength(LA)?ListLength(LB),
? 算法 2.2的时间复杂度则为
?O（ List Length(LA)+ListLength(LB)。
? 虽然算法 2.2中含有三个（ While）循环语句，但只有当 i和 j均指
向表中实际存在的数据元素时，才能取得数据元素的值并进行相
互比较；并且当其中一个线性表的数据元素均已插入到线性表
LC中后，只要将另外一个线性表中的剩余元素依次插入即可。
4、算法的存储空间需求
72北京邮电大学自动化学院
? 一,线性表的顺序表示
? 线性表的顺序表示指的是用一组地址连续的存储单元依次存
储线性表的数据元素。
? 假设线性表的每个元素需占用 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
2.2 线性表的顺序存储结构
73北京邮电大学自动化学院
? 线性表的这种机内表示称作线性表的顺序存储结构，称
这种存储结构的线性表为顺序表。
? 顺序存储的结构特点：以数据元素在计算机“物理位置
相邻”来表示表中数据元素间的逻辑关系。对于这种存
储方式，要访问第 i个数据元素，就可以直接计算出 ai的
存储位置 Loc(ai)。因而能随机存取表中任一数据元素，
换言之，数据元素在顺序表中的存储位置取决于该数据
元素在线性表中的顺序号。
? 例如：一个班学生，集体出游，按学号分配房
间。。。。。
74北京邮电大学自动化学院
? 由于 C语言中的一维数组也是采用顺序存储表示，故可以
用数组类型来描述顺序表。又因为除了用数组来存储线
性表的元素之外，顺序表还应该用一个变量来表示线性
表的长度属性，所以我们用结构类型来定义顺序表类
型。
? # define LIST-INIT-SIZE 100 //初始分配量
? # define LISTINCREMENT 10 //分配增量
? typedef struc{
? Elemtype *elem //存储空间基址
? int length ;//当前长度
? int ListSize; } Sqlist;
75北京邮电大学自动化学院
? 在顺序表存储结构中，很容易实现线性表的一些操作，如
线性表的构造、第 i个元素的访问。
? 注意,C语言中的数组下标从,0‖开始，因此，若 L是
Sqlist类型的顺序表，则表中第 i个元素是 L.data[i-1]。
? 顺序表上基本运算
? 1,顺序表的初始化
? 2,插入运算
? 3,删除运算
? 4,按值查找
二、顺序表上实现的基本操作
76北京邮电大学自动化学院
? 线性表的插入是指在表的第 i个位置上插入一个值为 x 的
新元素，插入后使原表长为 n的表,
? (a1,a2,..., ai-1,ai,ai+1,..., an)
? 成为表长为 n+1 表,
? (a1,a2,...,ai-1,x,ai,ai+1,...,an ) 。
? i 的取值范围为 1<=i<=n+1 。
? 顺序表上完成这一运算需要通过以下步骤进行：
? (1) 将 ai～ an 顺序向下移动，为新元素让出位置；
? (2) 将 x 置入空出的第 i个位置；
? (3) 修改 last 指针 (相当于修改表长 )，使之仍指向最后
一个元素。
1、插入
77北京邮电大学自动化学院
内存
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
78北京邮电大学自动化学院
算法 2.3
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;} // 增加存储容量
}
79北京邮电大学自动化学院
算法 2.3
? 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;} //IistInsert_Sq
80北京邮电大学自动化学院
? 算法的复杂度
? 这里的问题规模是表的长度，设它的值为 n。该算法的时间主
要花费在循环的结点后移语句上，由此可看出，所需移动结点
的次数不仅依赖于表的长度，而且还与插入位置有关。
? 当 =n时，由于循环变量的终值大于初值，结点后移语句将不进
行；这是最好情况，其时间复杂度 O（ 1）；
? 当 =1时，结点后移语句将循环执行 n次，需移动表中所有结
点，这是最坏情况，其时间复杂度为 O（ n）。
? 由于插入可能在表中任何位置上进行，因此需分析算法的平均
复杂度。
81北京邮电大学自动化学院
? 在长度为 n的线性表中第 i个位置上插入一个结点，令 Eis(n)表
示移动结点的期望值（即移动的平均次数），则在第 i个位置
上插入一个结点的移动次数为 n-i+1。故
?
? 不失一般性，假设在表中任何位置 (1≦ i≦ n+1)上插入结点的
机会是均等的，则 p1=p2=p3=…=pn+1=1/(n+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)。
82北京邮电大学自动化学院
? 线性表的删除运算是指将表的第 i(1≦ i≦ n)结点删除，使
长度为 n的线性表：
? (a1,…a i -1,ai,a i+1…, an)
? 变成长度为 n-1的线性表
? (a1,…a i -1,a i+1,…, an)
? 顺序表上完成这一运算的步骤如下：
? (1) 将 ai+1～ an 顺序向前移动。
? (2) 修改 last指针 (相当于修改表长 )使之仍指向最后
一个元素。
2、删除
83北京邮电大学自动化学院
内存
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
84北京邮电大学自动化学院
算法 2.4
? 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; //表尾元素位置
? For (++p; p<=q; ++p)*(p-1)=*p;
? //被删除元素之后的元素左移
? --L.length; //表长减 1
? return OK; } //IistDelete_Sq
85北京邮电大学自动化学院
?
?
??
n
i
idl inqE
1
)(
?
?
???? n
i
dl
nin
nE 1 2
1)(1
86北京邮电大学自动化学院
该算法的时间分析与插入算法相似，结点的移动
次数也是由表长 n和位置 i决定。
假设 qi是删除第 i个元素的概率，则在长度为 n的
线性表中删除一个元素时所需移动元素次数的
期望值（平均次数）为：
不失一般性，假设在表中任何位置上删除结点
的机 会是均等的，则 qi=1/n
因此，在等概率插入的情况下，
也就是说，在顺序表上做删除运算，平均要移
4、算法的存储空间需求
87北京邮电大学自动化学院
? 线性表的顺序表示的特点是用物理位置上的邻接关系来表示结点
间的逻辑关系，这一特点使我们可以随机存取表中的任一结点，
但它也使得插入和删除操作会移动大量的数据元素。
? 由于顺序表需要一组地址连续的存储单元，对于长度可变的线性
表就需要预分配足够的空间，有可能使一部分存储空间长期闲置
不能充分利用。
? 也可能由于估计不足，当表长超过预分配的空间而造成溢出，在
这种情况下，又难于扩充连续的存储空间。
? 为了克服上述缺点，我们将谈论线性表的另一种存储方式链式存
储结构，简称为链表 (Linked List)。
2.3 线性表的链式表示和实现
88北京邮电大学自动化学院
? 线性表的链式存储的特点是指用一组任意的存储单元来依次
存放线性表的结点，这组存储单元既可以是连续的，也可以
是不连续的，甚至是零散分布在内存中的任意位置上的。因
此，链表中结点的逻辑次序和物理次序不一定相同。
? 为了能正确表示结点间的逻辑关系，在存储每个结点值的同
时，还必须存储指示其后继结点的地址（或位置）信息，这
个信息称为指针 (pointer)或链 (link)。这两部分信息组成了元
素 ai的存储映象，称为结点，它包括两个域：
?
? 其中,data域是数据域，用来存放结点的值。 next是指针
域（亦称链域），用来存放结点的直接后继的地址（或位
置）。
data next
2.3.1 线性链表
89北京邮电大学自动化学院
? 链表正是通过每个结点的链域将线性表的 n个结点按其逻辑次序
链接在一起的。
? n个结点（ ai( 1<=i<=n）的存储映象）连接成一个链表，即为
线性表 (a1,a2,…,an) 的链式存储结构。由于上述链表的每一个
结点只有一个链域，故将这种链表称为单链表（ Single
Linked)。
? 链表中每个结点的存储地址是存放在其前驱结点 next域中，而
开始结点无前驱，故应设头指针 head指向开始结点。同时，由
于终端结点无后继，故终端结点的指针域为空，即 NULL（图示
中也可用 ^表示 )。
? 通常我们把线性链表画成用箭头相连接的节点序列，其中箭头
表示链域中的指针。
2.3.1 线性链表
h a1 a2
头结点
an ^…...
90北京邮电大学自动化学院
设 h是指向链表的头指针,p是指向链表中的某一结点的指针，可以说明如下,JD *h,*p;
p及其指向的节点关系如图所示。图中
（ *p）表示由指针所指向的节点。
(*p).data?p->data表示 p指向结点的数据域
(*p).link?p->link表示 p指向结点的指针域
data link
p 结点（ *p）
? 由上述可见，单链表可由头指针唯一确定，在 C语言中可用
“结构指针”来描述：
? typedef struct LNode {
? Elemtype data;
? struct LNode *next;
? } LNode,*Linklist,JD;
91北京邮电大学自动化学院
若 L为“空”（ L=NULL），则所表示的线性表为“空”表，其长度 n为“零”。
h 空表^
h 1145 1248
头结点
2158 ^…...
例如在上图中,h->data=1012
(h->link)->data=1145
(*h).data=1012
p为动态变量，它是通过标准函数生成的，即
p=(listnode*)malloc(sizeof(listnode));
函数 malloc分配了一个类型为 listnode的结点变量的空间，并将其首地址放入指针变量 p中。
一旦 p所指的结点变量不再需要了，又可通过标准函数 free(p) 释放所指的结点变量空间。
data link
p 结点（ *p）
1012
92北京邮电大学自动化学院
? 指针变量 p（其值为结点地址）和结点变量 *p之间的关系。
? p结点是指指针 p所指向的结点（即其存储位置存放在 p中的
结点）。
? 假设 p是指向线性表中第 i个数据元素（结点 ai）的指针，则
p->next是指向第 i+1个数据元素（结点 ai+1）的指针。
? 换句话说，若 p->data=ai，则 p->next->data=ai+1。由此，
在单链表中，取得第 i个数据元素必须从指针出发寻找，因
此，单链表是非随机存取的存储结构。
data link
p 结点（ *p）
h a1 a2
头结点
an ^…...
93北京邮电大学自动化学院
赵 钱 孙 李
周 吴 郑 王 ^
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
头指针
94北京邮电大学自动化学院
?假设线性表中结点的数据类型是字符，我们逐个输
入这些字符型的结点，并以换行符‘ \n’为输入结束
标记。动态地建立单链表的常用方法有如下两种：
?1、头插法建表
? 该方法从一个空表开始，重复读入数据，生成新
结点，将读入数据存放到新结点的数据域中，然
后将新结点插入到当前链表的表头上，直到读入
结束标志为止。
一、建立单链表
95北京邮电大学自动化学院
linklist createlistf(void)
{ char ch; linklist head; listnode *p;
head=null;
ch=getchar( );
while (ch!=‵ \n′{
p=(listnode*)malloc(sizeof(listnode));
p–>data=ch;
p–>next=head; head=p;
ch=getchar( );
}
return (head);
}
96北京邮电大学自动化学院
listlink createlist(int n)
{ int data;
linklist head;
listnode *p
head=null;
for(i=n;i>0;--i){
p=(listnode*)malloc(sizeof(listnode));
scanf((〝 %d〞, &p–>data);
p–>next=head;
head=p;
} return(head);
}
97北京邮电大学自动化学院
?2、尾插法建表
? 头插法建立链表虽然算法简单，但生成的链表中结
点的次序和输入的顺序相反。
?若希望二者次序一致，可采用尾插法建表。该方法
是将新结点插入到当前链表的表尾上，为此必须增
加一个尾指针 r，使其始终指向当前链表的尾结点。
例：
98北京邮电大学自动化学院
linklist creater( ) {
char ch; linklist head;
listnode *p,*r; //(,*head;)
head=NULL;r=NULL;
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); }
99北京邮电大学自动化学院
? 说明：第一个生成的结点是开始结点，将开始结点插入到空
表中，是在当前链表的第一个位置上插入，该位置上的插入
操作和链表中其它位置上的插入操作处理是不一样的，原因
是开始结点的位置是存放在头指针（指针变量）中，而其余
结点的位置是在其前驱结点的指针域中。算法中的第一个 if
语句就是用来对第一个位置上的插入操作做特殊处理。算法
中的第二个 if语句的作用是为了分别处理空表和非空表两种
不同的情况，若读入的第一个字符就是结束标志符，则链表
head是空表，尾指针 r亦为空，结点 *r不存在；否则链表
head非空，最后一个尾结点 *r是终端结点，应将其指针域置
空。
100北京邮电大学自动化学院
?如果我们在链表的开始结点之前附加一个结点，并
称它为头结点，那么会带来以下两个优点：
? a、由于开始结点的位置被存放在头结点的指针域
中，所以在链表的第一个位置上的操作就和在表的
其它位置上的操作一致，无需进行特殊处理；
? b、无论链表是否为空，其头指针是指向头结点
的非空指针（空表中头结点的指针域为空），因此
空表和非空表的处理也就统一了。
101北京邮电大学自动化学院
其算法如下：
linklist createlistr1( ){
char ch; linklist head=(linklist)malloc(sizeof(listnode));
listnode *p,*r;
r=head;
while((ch=getchar( ))!=‵ \n′{
p=(listnode*)malloc(sizeof(listnode));
p–>data=ch;
p–>next=p;
r=p; }
r–>next=NULL;
return(head); }
102北京邮电大学自动化学院
上述算法里动态申请新结点空间时未加错误处理，可作下列处理：
p=(listnode*)malloc(sizeof(listnode))
if(p==NULL)
error(〝 No space for node can be obtained〞 );
return ERROR;
以上算法的时间复杂度均为 O(n)。
103北京邮电大学自动化学院
?1、按序号查找
? 在链表中，即使知道被访问结点的序号 i，也不能象顺
序表中那样直接按序号 i访问结点，而只能从链表的头指
针出发，顺链域 next逐个结点往下搜索，直到搜索到第 i
个结点为止。因此，链表不是随机存取结构。
?设单链表的长度为 n，要查找表中第 i个结点，仅当
1≦ i≦ n时,i的值是合法的。但有时需要找头结点的位
置，故我们将头结点看做是第 0 个结点，其算法如下：
二、查找运算
104北京邮电大学自动化学院
Listnode * getnode(linklist head, int i)
{ int j;
listnode * p;
p=head; j=0;
while(p–>next && j<i) {
p=p–>next;
j++;
}
if (i==j)
return p; else
return NULL;
}
105北京邮电大学自动化学院
? 2、按值查找
? 按值查找是在链表中，查找是否有结点值等于给定值 key的
结点，若有的话，则返回首次找到的其值为 key的结点的存
储位置；否则返回 NULL。查找过程从开始结点出发，顺着
链表逐个将结点的值和给定值 key作比较。其算法如下：
? Listnode * locatenode(linklist head,int key) {
? listnode *p=head–>next;
? while( p && p–>data!=key)
? p=p–>next;
? return p; }
? 该算法的执行时间亦与输入实例中的的取值 key有关，其平
均时间复杂度的分析类似于按序号查找，也为 O(n)。
106北京邮电大学自动化学院
?插入运算是将值为 x的新结点插入到表的第 i个结点
的位置上，即插入到 ai-1与 ai之间。因此，我们必须
首先找到 ai-1的存储位置 p，然后生成一个数据域为
x的新结点 *s，并令结点 *s的指针域指向新结点，新
结点的指针域指向结点 ai,p结点的指针域指向新结
点 s，从而实现三个结点 ai-1,x和 ai之间的逻辑关系
的变化，插入过程如：
p ai-1 ai
xs
s->link=p->link;p->link=s;
三、插入运算
107北京邮电大学自动化学院
具体算法如下,
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));
s–>data=x;
s–>next=p–next;
p–>next=s;
}
p ai-1 ai
xs
s->link=p->link;
p->link=s;
108北京邮电大学自动化学院
?设链表的长度为 n，合法的插入位置是
1≦ i≦ n+1。
?注意当 i=1时,getnode找到的是头结点，
?当 i=n+1时,getnode找到的是结点 an。
?因此，用 i-1做实参调用 getnode时可完成插入位置
的合法性检查。算法的时间主要耗费在查找操作
getnode上，故时间复杂度亦为 O(n)。
109北京邮电大学自动化学院
? 删除运算是将表的第 i个结点删去。因为在单链表中
结点 ai的存储地址是在其直接前驱结点 a i-1的指针域
next中，所以我们必须首先找到 a i-1的存储位置 p。
然后令 p–>next指向 ai的直接后继结点，即把 ai从链
上摘下。最后释放结点 ai的空间，将其归还给“存储
池”。
p ai-1 ai ai+1
p->link=p->link->link;
四、删除运算
110北京邮电大学自动化学院
具体算法如下,
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 ) ;
}
111北京邮电大学自动化学院
? 设单链表的长度为 n，则删去第 i个结点仅当 1≦ i≦ n时是合法
的。注意，当 i=n+1时，虽然被删结点不存在，但其前驱结
点却存在，它是终端结点。因此被删结点的直接前趋 *p存在
并不意味着被删结点就一定存在，仅当 *p存在（即
p!=NULL）且 *p不是终端结点
? （即 p–>next!=NULL）时，才能确定被删结点存在。
? 显然此算法的时间复杂度也是 O(n)。
? 从上面的讨论可以看出，链表上实现插入和删除运算，无
须移动结点，仅需修改指针。
112北京邮电大学自动化学院
? 1、在头指针为 h的带表头结点的单链表中，把结点 b插入
到 a结点之前，若不存在结点 a就把结点 b插入到表尾。
? 插入过程：
?找到结点 a时,p指向结点,q指向结点 a的直接前驱结
点。
?首先生成一个 s结点，将 s结点的数据域置为 b，然后修
改相应的指针，把结点 a作为 s结点的直接后继，把 s结
点作为 q结点的直接后继。
五、链表的其他运算示例
113北京邮电大学自动化学院
? Void dlbqcr(JD *h,int a,int b)
? {//在头指针为 h的带表头结点的单链表中结点 a之前插入结点 b，若表中无结点 a，则插到
表尾
? JD*p,*q,*s;
? 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;)
? {q->link=s;s->link=p;}//找到结点时，把结点插到结点 a之前
? Else{p->link=s;s->link=NULL;}//表中无结点 a，则插到表尾 }
114北京邮电大学自动化学院
? 2、设线性表的 n个数据元素依次存放在一维数组 a[n]中，请建立
一个带表头结点的单链表,h为新建单链表的指针。
? 要建立一个带表头结点的单链表，首先生成一个 h结点作为表结
点，其链域置为“空”。
? 在生成一个 s结点，将其数据域置为第 n个数据元素，链域置为
“空”。 s结点作为表中第一个结点。
? 顺次生成新的 s结点，置其数据域为第 i个数据元素 (i=n-1,n-
2,…,2,1),修改有关指针：把表中第一个结点作为 s结点的直接后
继,s结点作为表中第一个结点。即把含第 i个数据元素的结点插
入到表中第一个结点之前。
115北京邮电大学自动化学院
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);}
116北京邮电大学自动化学院
? 3、设 h是带表头结点的单链表的头指针，请设计一个逆置这
个单链表的算法。
? 建立逆表的方法是：顺序扫描原表，依次将原表中的结点逐
个插入到第一个结点之前，可得到逆置链表。
? 设 s指向当前逆转结点,p指向 s结点的直接后继结点。
? Void dlbnz(JD*h){ JD*s,*p;
? p=h->link;// *p先指向原表中第一个结点
? h->link=NULL;//逆表的初态为空表
? While(p!=NULL)
? {s=p;// *s指向当前逆转的结点
? p=p->link;
? s->link=h->link;
117北京邮电大学自动化学院
? 4、设 pa,pb分别为两个按升序排列的单链表的头指
针，请设计一个算法把这两个单链表合并为一个按升序
排列的单链表。
? 合并的方法是：从两表的第一个结点开始顺链逐个将对
应数据元素进行比较，复制小者并插入 c表尾。当两表
中之一已到表尾，则复制另一链表的剩余部分，插入到
c表尾。
? /JD*dlnhb(JD *pa,JD*pb)
? {//把 pa,pb为头指针的按升序排列的单链表合并成一
个按升序排列的单链表。
? JD *p,*q;*pc;
? pc=(JD)malloc(sizeof(JD)); p=pc;
118北京邮电大学自动化学院
While(pa!=NULL && pb!=NULL)
{
q=(JD* )malloc (sizeof(JD));
If (pb->data<pa->data)
{q->data=pb->data; pb=pb->link;}
Else { q->data=pa->data; pa=pa->link;
If (pa->data==pb->data) pb=pb->link； }
p->link=q;
p=q;
}
119北京邮电大学自动化学院
While(pa!=NULL)
{ q=(JD*)malloc(sizeof(JD));
q->data=pa->data;
pa=pa->link; p->link=q; p=q;
}
While(pb!=NULL)
{ q=(JD*)malloc(sizeof(JD));
q->data=pb->data;
pb=pb->link; p->link=q; p=q;
}
p->link=NULL
p=pc;
pc=p->link;
free(p)
return(pc);}
120北京邮电大学自动化学院
? 循环链表是一种头尾相接的链表。其特点是无须增加存储
量，仅对表的链接方式稍作改变，即可使得表处理更加方便
灵活。
? 单循环链表：在单链表中，将终端结点的指针域 NULL改为
指向表头结点或开始结点，就得到了单链形式的循环链表，
并简单称为单循环链表。
? 为了使空表和非空表的处理一致，循环链表中也可设置一个
头结点。这样，空循环链表仅有一个自成循环的头结点表
示。如下图所示：
2.3.2 循环链表
121北京邮电大学自动化学院
h
⑴ 非空表
h
⑵ 空表
? 在用头指针表示的单链表中，找开始结点 a1的时间是
O(1)，然而要找到终端结点 an，则需从头指针开始遍历整
个链表，其时间是 O(n)。
122北京邮电大学自动化学院
? 在很多实际问题中，表的操作常常是在表的首尾位置上进
行，此时头指针表示的单循环链表就显得不够方便,如果改用
尾指针 rear来表示单循环链表，则查找开始结点 a1和终端结
点 an都很方便，它们的存储位置分别是 (rear–>next) —
>next和 rear，显然，查找时间都是 O(1)。因此，实际中多
采用尾指针表示单循环链表。
? 由于循环链表中没有 NULL指针，故涉及遍历操作时，其终
止条件就不再像非循环链表那样判断 p或 p—>next是否为
空，而是判断它们是否等于某一指定指针，如头指针或尾指
针等。
123北京邮电大学自动化学院
例、在链表上实现将两个线性表 (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;
ha—>next=p—>next; //a,b两个线性表尾首相连
hb—>next=q;// a,b两个线性表首尾相连
ha=hb;
free(p);//释放 hb表头结点
}
124北京邮电大学自动化学院
?单链表有一个很大的缺点：它只能顺着直接后继指针向
后查找其他结点，如若找某结点的直接前驱结点，只能
从表头指针开始查找。换句话说，在单链表中，
NextElem的执行时间为 O(1)，而 PriorElem的执行时间
为 O（ n）。
?为了克服单链表这种单向性的缺点，双向链表可有效解
决这个问题。
?双向链表 (Double linked list):在单链表的每个结点里再
增加一个指向其直接前驱的指针域 prior。这样形成的链
表中就有两个方向不同的链，故称为双向链表。
2.3.3双链表
125北京邮电大学自动化学院
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）
结点定义
126北京邮电大学自动化学院
? 和单链表类似，双链表一般也是由头指针唯一确定的，增加
头指针也能使双链表上的某些运算变得方便，将头结点和尾
结点链接起来也能构成循环链表，并称之为双向链表。
? 设指针 p指向某一结点，则双向链表结构的对称性可用下式
描述,(p—>prior)—>next=p=(p—>next)—>prior
? 即结点 *p的存储位置既存放在其前趋结点 *(p—>prior)的直
接后继指针域中，也存放 在它的后继结点 *(p—>next)的直
接前趋指针域中。
? 在双链表中，有些操作如,ListLength,GetElem和
LocateElem等仅需要涉及一个方向的指针，则它们的算法
描述和线性链表的操作相同，但在插入和删除操作时有很大
的不同，在双链表中插入和删除必须同时修改两个方向上的
指针。上述两个算法的时间复杂度均为 O(n)。
127北京邮电大学自动化学院
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步
}
128北京邮电大学自动化学院
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);
}
129北京邮电大学自动化学院
130北京邮电大学自动化学院
从本节的讨论中可见：由于链表在空间的合理利
用上和插入、删除时不需要移动等优点，因此
在很多场合下，它是线性表的首选存储结构。
然而它也存在着实现某些基本操作如求线性表长
度时不如顺序存储结构的缺点；另一方面，由
于在链表中，节点之间的关系用指针来表示，
则数据元素在线性表中的“位序”的概念已淡
化，而被数据元素在线性表链表中的“位置”
所代替。
为此，从实际应用角度出发重新定义线性链表及
其基本操作（见 P37~38）。
4、算法的存储空间需求
131北京邮电大学自动化学院
nnn xPxPxPPxP ????? ??2210)(
? 多项式的运算问题，已经成为表处理的一个经典问题。通
常一个多项式 Pn(x)可按升密写成：
2.4一元多项式相加
),,,210 nqqqqQ ??（?
),,,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 ?? ???????（
132北京邮电大学自动化学院
20 00 010 00 231)( xxxS ???
mee emn xPxPxPxP ???? ??21 21)(
为非零系数）（ im Peee ??? ??210
? 至此，一元多项式的表示及相加问题似乎已经解决。然而，在
通常的应用中，多项式的次数可能很高且变化很大，使得顺序
存储结构的最大长度很难确定。特别是在处理式的次数可能很
高且变化很大，使得顺序存储结构的最大长度很难确定。特别
是在处理形如：
2.4一元多项式相加
? 的多项式时，就要用一长度为 20001的线性表来表示，表中仅
有 3个非零元素，这种对内存空间浪费应当避免。
? 但是如果只存储非零系数项，显然必须同时存储相应的指数。
? 一般情况下的一元 n次多项式可写成：
? 其中,pi是指数为 ei的项的非零系数，且满足：
133北京邮电大学自动化学院
emmn xPxPxPxP ee ???? ??21 21)(
? ? ? ? ? ?? ?emPePeP m,，，，,??21 21
? 若用一个长度为 m且为每个数据元素有两个数据项（系数项和
指数项）的线性表
2.4一元多项式相加
? 便可唯一确定多项式 Pn(x)。在最坏情况下,n+1(=m)个系数都
不为零，则比只存储每项系数的方案要多一倍的数据。但是，
对于 S(x)类的多项式，这种表示将大大节省空间。
? 对应于线性表的两种存储结构，由上式定义的一元多项式也可
以有两种存储表示方法。在实际的应用程序中取用哪一种，则
要视多项式作何种运算而定。
? 若只对多项式进行“求值”等不改变多项式的系数和指数的运
算，则采用类似于顺序表的顺序存储结构即可，否则应采用链
式存储结构。本节中将主要讨论如何利用线性链表的基本操作
来实现一元多项式的运算。
134北京邮电大学自动化学院
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、单链表的结点定义
135北京邮电大学自动化学院
设 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）运算规则
136北京邮电大学自动化学院
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）算法描述
137北京邮电大学自动化学院
1、单链表操作
（ 1）建立带表头结点的单链表 h；
（ 2）打印单链表 h中所有结点的数据域值；
（ 3）输入 x,y。在第 1结点 x后插入 y，若无结
点 x，则在表尾插入结点 y；
（ 4）输入 k，删除单链表中所有的结点 k，并输
出被删除结点个数。
作业：以手写文档形式
4、算法的存储空间需求
138北京邮电大学自动化学院
第二章 习题
?1、单链表操作
?（ 1）建立带表头结点的单链表 h；
?（ 2）打印单链表 h中所有结点的数据域值；
?（ 3）输入 x,y。在第 1结点 x后插入 y，若无结点
x，则在表尾插入结点 y；
?（ 4）输入 k，删除单链表中所有的结点 k，并输出
被删除结点个数。
?作业：以手写文档形式
139北京邮电大学自动化学院
3.1 栈
3.2 栈的应用举例
3.3 队列
第三章 栈和队列
140北京邮电大学自动化学院
?1 栈的定义
?栈 (Stack)是限制在表的一端进行插入和删除运算的
线性表，通常称插入、删除的这一端为栈顶 (Top)，
另一端为栈底 (Bottom)。当表中没有元素时称为空
栈。
? 假设栈 S=(a1,a2,a3,…an),则 a1称为栈底元
素,an为栈顶元素。栈中元素按 a1,a2,a3,…an
的次序进栈，退栈的第一个元素应为栈顶元素。换句
话说，栈的修改是按后进先出的原则进行的。因此，
栈称为后进先出表（ LIFO）。
3.1.1抽象数据类型栈的定义
141北京邮电大学自动化学院
图 3.1栈的示意图
? 只允许在一端插入和删除
的顺序表
? 允许插入和删除的一端称
为栈顶 (top)，另一端称
为栈底 (bottom)
? 特点,
? 后进先出 (LIFO)
142北京邮电大学自动化学院
? （ 1）初始化
? （ 2）进栈
? （ 3）退栈
? （ 4）取栈顶元素
? （ 5）判栈是否非空
? （ 6）置栈空
2、栈的基本操作
143北京邮电大学自动化学院
? ADT stack{
? 数据对象,D={ai|ai?ElemSet,i=1,2,…,n,n>=0)}
? 数据关系,R1={<ai-1,ai>|ai-1,ai ?D} 约定 an为栈顶,a1端为
栈底
? 基本操作：
? Initstack(&s)
? 操作结果：构造一个空栈 s
? Destroystack(&s)
? 初始条件：栈已经存在
? 操作结果：栈 s被销毁
? Clearstack(&S)
3、栈的抽象数据类型的定义
144北京邮电大学自动化学院
? StackEmpty(&s)
? 初始条件：栈已经存在
? 操作结果：若栈 S为空,
则返回 TRUE,否则 FALSE.
? StackLength(&s)
? 初始条件：栈 S已经存
在
? 操作结果：返回栈 S的
元
? 素个数,即栈的长度,
? GetTop(S,&e)
3、栈的抽象数据类型的定义
? Push (&s,e)
? 初始条件, 栈 S已经存在
? 操作结果：插入元素 e
为
? 新的栈顶元素,
? Pop(&s,&e)
? 初始条件：栈已经存在
且
? 非空
? 操作结果：删除 S的栈
顶
145北京邮电大学自动化学院
和线性表类似，栈也有两种存储表示方法。顺序栈、链栈。
3.1.2 栈的表示和实现
顺序表,即栈的顺序存储结构是利用一组地址连续的存储单
元依次存放自栈底到栈顶的数据元素．同时附设指针 top指
示栈顶元素在顺序表中的位置,
通常的习惯做法是以 top=0表示空栈,鉴于 C语言中数组的下
标约定从 0开始,则当以 C语言作描述语言时,如此设定会带来
很大不方便 ;
另一方面,由于栈在使用过程中所需要最大空间的大小很难
估计,因此,一般来说,在初始化设计空栈时不应限定栈的最大
容量,
一个合理的做法是,先为栈分配一个基本容量,然后在应用过
程中,当栈的空间不够使用时再逐段扩大,
146北京邮电大学自动化学院
为此设定两个常量,STACK_INIT_SIZE(存储空间初始分配量 )
和 STACKINCREMENT(存储空间分配增量 ),并以下述类型说明
作为顺序栈的定义,
其中,stacksize指示栈的当前可使用的最大容量,栈的初始化操作
为, 按设定的初始分配量进行第一次存储分配,base可称为栈底
指针,在顺序标中,它始终指向栈底的位置,若 base的值为 NULL,
则表明栈结构不存在,
typedef Struct{
SElemType *base;
SElemType *top;
int stacksize; }SqStack;
1,顺序栈
147北京邮电大学自动化学院
例、一叠书或一叠盘子。
a n
a n-1
a2
a1
……
top
base
1,顺序栈
? 称 top为栈顶指针,其初始值指
向栈底,即 top=base可作为栈
空的标记,每当插入新的栈顶
元素时,指针 top增 1;删除栈顶
元素时,指针 top减 1,因此,非空
栈中的栈顶指针始终在栈顶元
素的下一位置上,右图展示了
顺序栈中数据元素和栈顶指针
之间的对应关系,
148北京邮电大学自动化学院
进栈示例
退栈示例
149北京邮电大学自动化学院
基本操作的算法描述
（ 1）置空栈
void initstack(seqstack *s)
{
s–>top=-1;
}
（ 2）判断栈空
int stackempty(seqstack *s)
{
return(s–>top==-1);
}
150北京邮电大学自动化学院
（ 3）判断栈满
int stackfull(seqstack *s)
{
return(s–>top==stacksize-1);
}
（ 4）进栈
void push(seqstack *s,datatype x)
{
if (stackfull(s))
error(―stack overflow‖);
s–>data[++s–>top]=x;
}
151北京邮电大学自动化学院
（ 5）退栈
datatype pop(seqstack *s)
{
if(stackempty(s))
error(―stack underflow‖);
x=s–>data[top];
s–>top--;
return(x)
//return(s–>data[s–>top--]);
}
152北京邮电大学自动化学院
（ 6）取栈顶元素
Datatype stacktop(seqstack *s)
{
if(stackempty(s)
error(―stack is enpty‖);
return s–>data[s–>top];
}
153北京邮电大学自动化学院
? 栈的链式存储结构称为链栈，它是运算受限的单链表，插
入和删除操作仅限制在表头位置上进行。由于只能在链表
头部进行操作，故链表没有必要像单链表那样附加头结
点。栈顶指针就是链表的头指针。
? 链栈的类型说明如下：
? typedef struct stacknode {
? datatype data
? struct stacknode *next
? }stacknode;
2,链栈
154北京邮电大学自动化学院
链式栈无栈满问题
空间可扩充
插入与删除仅在栈顶处执行
链式栈的栈顶在链头
适合于多栈操作
? 链式栈的特点：
栈的链接表示 — 链式栈
155北京邮电大学自动化学院
计
算
顺
序
输
出
顺
序
? 例 1,数制转换
? 十进制数 N和其他 d进制数的转换是计算机实现计算的基本
问题,其中一个简单算法基于下列原理,
? N=(N div d)?d+N mod d
? 例如,（ 1348)10 = (2504)8,其运算过程如下：
?N N div 8 N mod
?1348 168 4
?168 21 0
?21 2 5
?2 0 2
3.2 栈的应用举例
156北京邮电大学自动化学院
void conversion () {
//对于输入的任意一个非负十进制整数,打印输出与
其等值的八进制数
InitStack(S); //构造空栈
scanf ("%d",N);
while (N) {
Push(S,N % 8);
N = N/8;
}
while (!StackEmpty(S)) {
Pop(S,e);
printf ( "%d",e );}
} // conversion
例 1、数制转换
157北京邮电大学自动化学院
? 假设在表达式中允许包含两种括号,园括号和方括号,其嵌套
是随意,并假定 （［］（））或［（［ ］［ ］）］等为正确
的格式,
? ［（ ］）或（［（ ））或 (( )])均为不正确的格式。
? 检验括号是否匹配的方法,可用“期待的急迫程度”这个概
念来描述,
分析可能出现的不匹配的情况,
到来的右括弧非是所“期待”的 ;
到来的是“不速之客” ;直到结束，也没有到来所
“期待”的括弧 ;。
例 2,括号匹配的检验
例如：考虑下列括号序列：
[ ( [ ] [ ] ) ]
1 2 3 4 5 6 7 8
158北京邮电大学自动化学院
[ ( [ ] [ ] ) ]
1 2 3 4 5 6 7 8
? 当计算机接受了第 1个括号后，它期待着与其匹配的第 8个括
号的出现，然而等来的却是第 2个括号，此时第 1个括号,[‖
只能暂时靠边，“期待的急迫程度”最高是第 2个括号
“（” 。
? 而迫切等待与第 2个括号“（”相匹配的第 7个扩号“）”的
出现，类似地，因等来的是第 3个括号,[‖,其期待匹配的程
度较第 2个括号更急迫,则第 2个括号也只能靠边，让位于第 3
个括号,[‖,显然第 2个括号,(‖的期待急迫性高于第 1个括号
,[‖;
? 在接受了第四个括号,]‖之后,第 3个括号的期待得到满足,消
解之后，第 2个括号的期待匹配就成为当前最急迫的任务
了,……,依次类推,
可见这个处理过程恰好与栈的特点相吻合,
159北京邮电大学自动化学院
算法的设计思想
? 1）凡出现左括弧，则进栈； 自然使原有的在栈中的所有
未消解的期待的急迫性都降了一级。
? 2）凡出现右括弧，首先检查栈是否空
?若栈空，则表明该“右括弧”多余
3）表达式检验结束时，
若栈空，则表明表达式中匹配正确
否则表明“左括弧”有余
否 则和栈顶元素比较
否则表明不匹配
若相匹配，
则“左括弧出栈”
160北京邮电大学自动化学院
Status matching(string& exp) {
int state = 1;
while (i<=Length(exp) && state) {
switch of exp[i] {
case ―(‖:{Push(S,exp[i]); i++; break;}
case ―)‖,{
if(NOT StackEmpty(S) && GetTop(S)=― (‖)
{Pop(S,e); i++;}
else {state = 0;}
break; } … … }
if (StackEmpty(S) && state) return OK; …...
161北京邮电大学自动化学院
如何实现？
―每接受一个字符即存入存储器”?
并不恰当！
例 3、行编辑程序问题
? 合理的作法是：设立一个输入缓冲区，用以接受用户输入
的一行字符，然后逐行存入用户数据区 ; 并假设,#‖为退格
符，,@‖为退行符。
? 在用户输入一行的过程中，允许用户输入出差错，并在发
现有误时可以及时更正。
? 一个简单的行编辑程序的功能是,接受用户从终端输入
的程序或数据,并存入用户的数据区,
162北京邮电大学自动化学院
? 例如,当用户发现刚刚输入的一个字符是错的时候,可以补进
一个,#‖,以表示前一个字符无效 ;
? 如果发现当前输入的行内差错太多或难以补救,则可以键入
一个退行符,@‖,以表示当前行中的字符均无效,
? 假设从终端接受了这样两行字符：
? whli##ilr#e（ s#*s)
? outcha@putchar(*s=#++);
? 则实际有效的是下列两行：
? while (*s)
? putchar(*s++);
163北京邮电大学自动化学院
while (ch != EOF && ch != '\n') {
switch (ch) {
?case ?#‘, Pop(S,c); break;//仅当栈非空时退栈
?case '@',ClearStack (S); break;// 重置 S为空栈
? default, Push(S,ch); break; //有效字符进栈 }
? ch = getchar(); // 从终端接收下一个字符 }
ClearStack (S); // 重置 S为空栈
if (ch != EOF) ch = getchar();}
while (ch != EOF) { //EOF为全文结束符
将从栈底到栈顶的字符传送至调用过程的数据区；
164北京邮电大学自动化学院
求迷宫中从入口到出口的所有路径是一个经典的程序设计问
题,计算机解迷宫问题，通常用的是“穷举求解”的方法。
# # # # # # # # # #
# ? ? # $ $ $ # #
# ? # $ $ $ # #
# ? ? $ $ # # #
# ? # # # # #
# ? ? ? # # #
# # ? ? ? # #
# # # # # ? # # #
# ? ? ? ? #
# # # # # # # # # #
例 4,迷宫求解
165北京邮电大学自动化学院
? 即从入口出发，顺某一方向向前探索，若能走通，则继续往
前走；否则沿原路退回，换一个方向再继续探索，直到所有
可能的通路都探索到为止。
? 为了保证在任何位置上都能沿原路退回，显然需要用一个后
进先出的结构来保存从入口到当前位置的路径。因此，在求
迷宫通路的算法中应用“栈”也就是自然而然的事了。
? 首先，在计算机可以用图所示的方块表示迷宫。途中的每个
方块或为通道（以白方块表示），或为墙（以带阴影的方块
表示）。所求路径必须是简单路径，即在求得的路径上不能
重复出现同一通道块。
166北京邮电大学自动化学院
? 假设“当前位置”指的是“在搜索过程中某一时刻所在图中某
个方块的位置”，则求迷宫中一条路径的算法的基本思想是：
? 若当前位置“可通”，则纳入路径，并继续朝“下一个位置”
探索，即切换“下一位置”为“当前位置”,如此重复直至到达
出口；
? 若当前位置“不可通”，则应顺着“来向”退回到“前一通道
块”，然后朝着除“来向”之外的其它方向继续探索；
?若该通道块的四周 4个方块均“不可通”，则应从“当前路
径”上删除该通道块。所谓“下一位置”指的是“当前位
置”四周四个方向（东、南、西、北）上相邻的方块。? 假设以栈 S记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。由此，“纳入路径”的操作即为“当前
位置入栈”；,从当前路径上删除前一通道块”的操作即为
“出栈”。
167北京邮电大学自动化学院
? 假设以栈 S记录“当前路径”，则栈顶中存放的是“当前路径
上最后一个通道块”。由此，“纳入路径”的操作即为“当前
位置入栈”；,从当前路径上删除前一通道块”的操作即为
“出栈”。? 求迷宫中一条从入口到出口的路径的算法：
? 设定当前位置的初值为入口位置；
? do｛
? 若当前位置可通，
? 则｛ 将当前位置插入栈顶； //纳入路径
? 若该位置是出口位置，则算法结束； //求得路径
? 否则切换当前位置的东邻方块为新的当前位置；｝
? 否则 { 见下一页 }
? ｝ while (栈不空） ；
168北京邮电大学自动化学院
do｛
若当前位置可通，则｛ 见上一页｝ ;
否则
若栈不空且栈顶位置尚有其他方向未被探索，
则设定新的当前位置为, 沿顺时针方向旋转找到的栈顶
位置的下一相邻块；
若栈不空但栈顶位置的四周均不可通，
则｛
删去栈顶位置； // 从路径中删去该通道块
若栈不空，则重新测试新的栈顶位置,直至找
到一个可通的相邻块或出栈至栈空； }
｝｝ while (栈不空）；
若栈空，则表明迷宫没有通路。
169北京邮电大学自动化学院
? 在此，尚需要说明一点的是，所谓当前位置可通，指的是未
曾走到过的通道块，即要求该方块的位置不仅是通道块，而
且既不在当前路径上（否则所求路径就不是简单路径），也
不是曾经纳入过路径的通道块（否则只能在死胡同内转
圈）。
? Typedef struct{
? Int ord; // 通道块在路径上的“序号”
? PosType seat; // 通道块在迷宫中的“坐标位置”
? Int di; // 从此通道块走向下一通道块的“方向”
? }SElemType; / / 栈的元素类型
170北京邮电大学自动化学院
Status Mazepath(MazeType maze,PosType start,PosType end){
//若迷宫中存在从入口到出口的通道,则求得一条存放在栈中 (从
//栈底到栈顶 ),并返回 TRUE;否则返回 FLASE;
InitStack(S);curpos=start;//设定“当前位置”为“入口位置”
Curstep=1;//探索第一步
Do {If ( pass(curpos )) { //当前位置可以通过，即是未曾走过的通道块
FootPrint ( curpos ); //留下足迹
e=(curstep,curpos,1);
Push(S,e);//加入路径
If( curpos==end) return (TRUE); //到达终点（出口）
curpos=NextPos(curpos,1);//下一位置是当前位置的东邻
Curstep++;} //探索下一步
}// if
171北京邮电大学自动化学院
Else{//当前位置不通
If (!StackEmpty(S)){
Pop(S,e);
While(e.di==4&&!StackEmpty(S)){
MarkPrint(e.seat)； Pop(S,e);//留下不能通过的标记，
并退回一步 }//while
If(e.di<4){
e.di++; Push(S,e);//换下一个方向探索
Curpos=NextPos(e.seat,e.di);//设定当前位置是该新方向上的
相邻块 }//if }// if }//else
} while (!StackEmpty(S ));
Return(FALSE);
}//MazePath
172北京邮电大学自动化学院
# # # # # # # # # #
# # # #
# # # #
# # # #
# # # # # #
# # # #
# # # #
# # # # # # # #
# ? #
# # # # # # # # # #
?
? ?
??
?
?
?
?
???
?
1 1 1
1 2 2
2 2 2
3 2 1
3 3 1
3 4 4
2 4 1
2 5 1
2 6 4
1 6 3
1 5 3
1 4 4
3
$ $ $
$$$
$$
173北京邮电大学自动化学院
? 例如 要对下面的表达式求值,4+2*3-10/5
?首先要了解算术四则运算的规则。即是：
? 先乘除，后加减
? 从左到右
? 先括号内，后括号外
?由此，这个算术表达式的计算顺序应为：
? 4+2*3-10/5
? =4+6-10/5
? =10-10/5
? =10-2=2
?任何一个表达式都是有操作数、运算符和界限符组成的，我们把运算符
和界限符统称为算符，它们构成的集合命名为 OP。
例 5,表达式求值
174北京邮电大学自动化学院
根据上述三条运算规则，在运算的每一步中，任意两个相继出现
的算符 Q1和 Q2之间的优先关系至多是下面的三种关系之一：
Q1<Q2 Q1的优先权低于 Q2
Q1=Q2 Q1的优先权等于 Q2
Q1>Q2 Q1的优先权高于 Q2
为了实现算符优先算法，可以使用两个工作栈。 一个称做 OPTR，
用以寄存运算符；另一个称做 OPND，用以积存操作数或运算结
果。 算法的基本思想是：
首先置操作数栈为空栈，表达式起始符,#‖为运算符栈的栈底元
素；
依次读入表达式中每个字符，若是操作数则进 OPND栈，若是运
算符，则和 OPTR栈的栈顶运算符比较优先权后作相应操作，直
至整个表达式求值完毕（即 OPTR栈顶元素和当前读入的字符均
为,#‖）。
175北京邮电大学自动化学院
OperandType EvaluateExpression(){
//设 OPTR和 OPND分别为运算符栈和运算数栈
InitStack(OPTR);Push(OPTR,‘#‘);
InitStack(OPND);c=getchar();
While(c!=‘#‘||GetTop(OPTR)!=―#‘){
If(!In(c,OP)） {Push((OPND,c);c=getchar();}//不是运算
符则进栈
Else
Switch Precede(GetTop(OPTR),c)){
Case ―<?,//栈顶元素优先权低
Push(OPTR,c);c=getchar();break;
Case ―=?,//脱括号接收下一字符
Pop(OPTR,x);c=getchar();break;
176北京邮电大学自动化学院
While(c!=‘#‘||GetTop(OPTR)!=―#‘){
If(!In(c,OP)） {Push((OPND,c);c=getchar();}//
Else
Switch Precede(GetTop(OPTR),c)){
Case ―<?:Push(OPTR,c);c=getchar();break;
Case ―=?:Pop(OPTR,x);c=getchar();break
Case ―>?,//退栈并将运算结果入栈
Pop(OPTR,theta);
Pop(OPND,b); Pop(OPND,a);
Push(OPND,Operate(a,theta,b));break; }
}//while
Return GetTop(OPND);
}//EvaluateExpression
177北京邮电大学自动化学院
步骤 OPTR栈 OPND栈 输入字符 主要操作
RETURN(GETTOP(OPND))
1 # 3*(7-2)# PUSH(OPND,‘3‘)
2 # 3 *(7-2)# PUSH(OPTR,‘*‘)
3 #* 3 (7-2)# PUSH(OPTR,‘(‘)
4 #*( 3 7-2)# PUSH(OPND,‘7‘)
5 #*( 37 -2)# PUSH(OPTR,‘-‘)
6 #*(- 37 2)# PUSH(OPND,‘2‘)
7 #*(- 372 )# operate(?7‘,‘-‘,‘2‘)
8 #*( 35 )# Pop(OPTR)
9 #* 35 # operate(?3‘,‘*‘,‘5‘)
10 # 15 #
178北京邮电大学自动化学院
例 6 栈与递归的实现
当在一个函数的运行期间调用另一个函数时，在运行
该被调用函数之前，需先完成三项任务：
将所有的实在参数、返回地址等信息传递给被调用函数保
存 ;
为被调用函数的局部变量分配存储区 ;
将控制转移到被调用函数的入口保存被调函数的计算结果 ;
从被调用函数返回调用函数之前，应该完成下列三项
任务：
保存被调函数的计算结果 ;
释放被调函数的数据区 ;
依照被调函数保存的返回地址将控制转移到调用函数。
179北京邮电大学自动化学院
多个函数嵌套调用的规则是,
此时的内存管理实行,栈式管理
”
后调用先返回 ！
例如：
void main( ){ void a( ){ void b( ){
… … …
a( ); b( );
… …
}//main }// a }// b
Main的数据区
函数 a的数据区
函数 b的数据区
180北京邮电大学自动化学院
栈的应用
过程的嵌套调用
r
主
程
序
s
rr
r
s
子
过
程
1 r
s
t
子
过
程
2 rs
t 子过
程
3
181北京邮电大学自动化学院
例 递归的执行情况分析
递归过程及其实现
递归：函数直接或间接的调用自身叫 ~
实现：建立递归工作栈
void print(int w)
{ int i;
if ( w!=0)
{ print(w-1);
for(i=1;i<=w;++i)
printf(―%3d,‖,w);
printf(―/n‖);
}
}
运行结果：
1，
2,2，
3,3,3，
182北京邮电大学自动化学院
递归调用执行情况如下：
主程序
(1)
print(w)
w=3;
3
print(2);
（ 1） w=3
top
(2) 输出,3,3,3
w
2
print(1);
（ 2） w=2
（ 1） w=3
top
(3) 输出,2,2
w 1
print(0);
（ 3） w=1
（ 2） w=2
（ 1） w=3
top
(4)输出,1
w
0
（ 4） w=0
（ 3） w=1
（ 2） w=2
（ 1） w=3
top
w
(2) 2
(1) 3
输出：
(3) 1
(2) 2
(1) 3
top
(1 ) 3
返回
(3)
(2)
(1) 3
top (4)
结束
183北京邮电大学自动化学院
解决方法：
n=1时，直接把圆盘从 A移到 C
n>1时，先把上面 n-1个圆盘从 A移到 B,然后将 n号盘从 A移到 C,再将 n-1个盘从 B移到 C
。 即把求解 n个圆盘的 Hanoi问题转化为求解 n-1个圆盘的 Hanoi问题，依次类推，直
至转化成只有一个圆盘的 Hanoi问题
执行情况,递归工作栈保存内容：形参 n,x,y,z和返回地址,返回地址用行编号表示
n x y z 返回地址
Tower of Hanoi问题
问题描述：有 A,B,C三个塔座,A上套有 n个直径不同的圆盘，按直径从小到
大叠放，形如宝塔,编号 1,2,3…… n。 要求将 n个圆盘从 A移到 C,叠放顺序不
变，移动过程中遵循下列原则：
每次只能移一个圆盘
圆盘可在三个塔座上任意移动
任何时刻，每个塔座上不能将大盘压到小盘上 A B C
12
3
184北京邮电大学自动化学院
void hanoi (int n,char x,char y,char z) {
// 将塔座 x上按直径由小到大且至上而下编号为 1至 n
// 的 n个圆盘按规则搬到塔座 z上,y可用作辅助塔座。
1 if (n==1)
2 move(x,1,z); // 将编号为１的圆盘从 x移到 z
3 else {
4 hanoi(n-1,x,z,y); // 将 x上编号为１至 n-1的
//圆盘移到 y,z作辅助塔
5 move(x,n,z); // 将编号为 n的圆盘从 x移到 z
6 hanoi(n-1,y,x,z); // 将 y上编号为１至 n-1的
//圆盘移到 z,x作辅助塔
7 }
8 }
185北京邮电大学自动化学院
main()
{ int m;
printf("Input number of disks”);
scanf("%d",&m);
printf(”Steps, %3d disks”,m);
hanoi(m,'A','B','C');
(0) }
void hanoi(int n,char x,char y,char z)
(1) {
(2) if(n==1)
(3) move(1,x,z);
(4) else{
(5) hanoi(n-1,x,z,y);
(6) move(n,x,z);
(7) hanoi(n-1,y,x,z);
(8) }
(9) }
A B C
12
3
3 A B C 0
3 A B C 0
2 A C B 6
3 A B C 0
2 A C B 6
1 A B C 6
A B C
3 A B C 0
2 A C B 6
186北京邮电大学自动化学院
main()
{ int m;
printf("Input the number of disks
scanf("%d",&m);
printf("The steps to moving %3d
hanoi(m,'A','B','C');
(0) }
void hanoi(int n,char x,char y,char z)
(1) {
(2) if(n==1)
(3) move(1,x,z);
(4) else{
(5) hanoi(n-1,x,z,y);
(6) move(n,x,z);
(7) hanoi(n-1,y,x,z);
(8) }
(9) }
A B C
3 A B C 0
2 A C B 6
1 C A B 8
A B C
3 A B C 0
2 A C B 6
3 A B C 0
3 A B C 0
2 A C B 6
187北京邮电大学自动化学院
main()
{ int m;
printf("Input the number of disks
scanf("%d",&m);
printf("The steps to moving %3d
hanoi(m,'A','B','C');
(0) }
void hanoi(int n,char x,char y,char z)
(1) {
(2) if(n==1)
(3) move(1,x,z);
(4) else{
(5) hanoi(n-1,x,z,y);
(6) move(n,x,z);
(7) hanoi(n-1,y,x,z);
(8) }
(9) }
A B C
3 A B C 0
2 B A C 8
3 A B C 0
2 B A C 8
1 B C A 6
A B C
3 A B C 0
2 B A C 8
3 A B C 0
188北京邮电大学自动化学院
main()
{ int m;
printf("Input the number of disks
scanf("%d",&m);
printf("The steps to moving %3d
hanoi(m,'A','B','C');
(0) }
void hanoi(int n,char x,char y,char z)
(1) {
(2) if(n==1)
(3) move(1,x,z);
(4) else{
(5) hanoi(n-1,x,z,y);
(6) move(n,x,z);
(7) hanoi(n-1,y,x,z);
(8) }
(9) }
A B C
3 A B C 0
2 B A C 8
1 A B C 8
A B C
3 A B C 0
2 B A C 8
3 A B C 0
栈空
3 A B C 0
2 B A C 8
189北京邮电大学自动化学院
链式栈无栈满问题
空间可扩充
插入与删除仅在栈顶处执行
链式栈的栈顶在链头
适合于多栈操作
? 链式栈的特点：
栈的链接表示 — 链式栈
190北京邮电大学自动化学院
3.3队列
? 3.3.1 抽象数据类型队列的定义
? 队列 (Queue)也是一种运算受限的线性表。它只允许在表的
一端进行插入，而在另一端进行删除。允许删除的一端称为
队头 (front)，允许插入的一端称为队尾 (rear)。
? 例如：排队购物。操作系统中的作业排队。先进入队列的成
员总是先离开队列。因此队列亦称作先进先出 (First In First
Out)的线性表，简称 FIFO表。
? 当队列中没有元素时称为空队列。在空队列中依次加入元素
a1,a2,…an 之后,a1是队头元素,an是队尾元素。显然退出
队列的次序也只能是 a1,a2,…an,也就是说队列的修改是依
先进先出的原则进行的。
191北京邮电大学自动化学院
出队 入队
队头 队尾
下图是队列的示意图：
a1 a2 a3 an
队列的抽象数据定义见书Ｐ 59
双端队列,就是限定插入和删除操作在表的两端进
行的线性表。
尽管双端队列看起来似乎比栈和队列更灵活，但实
际上在应用程序中远不及栈和队列有用，故在此不
作详细讨论。
192北京邮电大学自动化学院
设队首、队尾指针 front和 rear,
front指向头结点,rear指向队尾
? 队列的链式存储结构简称为链队列，它是限制仅在表头删
除和表尾插入的单链表。显然仅有单链表的头指针不便于
在表尾做插入操作，为此再增加一个尾指针，指向链表的
最后一个结点。
3.3.2 链队列
头结点
…...front
队头 队尾
rear
193北京邮电大学自动化学院
front rear
x入 队 ^x
front rear
y入 队 x ^y
front rear
x出 队 x ^y
front rear
空队 ^
front rear
y出 队 ^
194北京邮电大学自动化学院
我们也是将这两个指针封装在一起，将链队列的类型
LinkQueue定义为一个结构类型：
链队列结点定义
typedef struct Qnode
{ QElemType data;
struct QNode *next;
} QNode,*QueuPtr;
?Typedef struct{
QueuPtr front;//对头指针
QueuPtr rear;//对尾指针
} LinkQueue
195北京邮电大学自动化学院
下面给出链队列上实现的基本运算：
void initqueue(linkqueue *q)//构造一个空队列
{
q–>front=q–>rear=null;
}
int queueempty(linkqueue *q)//若队列 Q为空队列，
则返回 TRUE，否则返回 FALSE
{
return q–>front==null &&q–>rear==null;
}
196北京邮电大学自动化学院
Status EnQueue( LinkQueue *Q,QElemType e)
//插入元素 e为 Q的新的队尾元素； {
p=(QueuePtr * )malloc ( sizeof(QNode));
if (!p) exit (OVERFLOW);//存储分配失败
p–>data=e;
p–>next=NULL;
Q.rear->next=p;
Q.rear=p;
return OK;}
197北京邮电大学自动化学院
Status DeQueue(LinkQueue &Q,QElemType &e)
//若队列不空，则删除 Q的队头元素，用 e返回其值，并返回
OK；否则返回 ERROR {
if( Q.front==Q.rear) return ERROR;
p=Q.front->next;
e=p–>data;
Q–>front->next=p–>next;
if(Q.rear==p) Q.rear=Q.front;
free(p);
return OK;}
注意,在出队算法中，一般只需修改队头指针。但当原队
中只有一个结点时，该结点既是队头也是队尾，故删去此
结点时亦需修改尾指针，且删去此结点后队列变空。
198北京邮电大学自动化学院
3.3.2 循环队列－队列的顺序表示和实现
?队列的顺序存储结构称为顺序队列，在队列的顺序存储
结构中，除了用一组地址连续的储存单元依次存放从对
头到对尾的元素之外，尚需要附设两个指针 front和 rear
分别指示队列头元素和队列尾元素的位置。
?为了在 C语言中描述方便起见，在此我们约定：初始化
建空队列时，令 front＝ rear＝ 0。每当插入新的队列尾
元素时“尾指针增 1‖；每当删除队列头元素时“头指针
增 1‖。
?因此，在非空队列中，头指针始终指向队头元素，而尾
指针始终指向队尾元素的下一位置。
199北京邮电大学自动化学院
J1
J2
J3
rear
设两个指针 front,rear,约定,在非
空队列中,front始终 指 向对头元
素； Rear始终 指 向队列 尾元素 的
下一位置 ；初值 front=rear=0
空队列条件,front==rear
入队列,sq[++rear]=x;
出队列,x=sq[++front];
rear
rear
front
front
front
front
队列的顺序存储结构
实现：用一维数组实现 sq[M]
1
2
3
4
5
0front
J1,J1,J3入队
rear
1
2
3
4
5
0
J1,J2,J3出队
J1
J2
J3
rear
1
2
3
4
5
0
J4,J5,J6入队
J4
J5
J6
front
front=0
rear=0
1
2
3
4
5
0
队空
200北京邮电大学自动化学院
存在问题
设数组维数为 M,则：
当 front=0,rear=M-1时，再有元素入队发生溢出 ——真溢出
当 front?0,rear=M-1时，再有元素入队发生溢出 ——假溢出
解决方案
队首固定，每次出队剩余元素向下移动 ——浪费时间
循环队列
基本思想：把队列设想成环形，让 sq[0]接在 sq[M-1]之后，
若 rear+1==M,则令 rear=0;
rear
1
2
3
4
5
0
J4,J5,J6入队
J4
J5
J6
front
0
M-1
1
front
rear 实现：利用“模”运算
入队, rear=(rear+1)%M;
sq[rear]=x;
出队, front=(front+1)%M
x=sq[front];
队满、队空判定条件
201北京邮电大学自动化学院
J4
J5
J6
0
123
4 5
rear
front
J9
J8
J7
队满,front==rear
解决方案：
1.另 外设一个标志 以区别队空、队满
2.少用一个元素空间，约定以“队列头
指针在队列尾指针的下一位置上”，
作为队列呈“满”状态的标志。
队空,front==rear
队满,(rear+1)%M==front
J4
J5
J6
0
123
4 5
rear
front
初始状态
1
234
5 0
rear
front
202北京邮电大学自动化学院
第 3章 习题
?1、设将整数以 1,2,3,4依次进栈，但只要出栈
时栈非空，则可将出栈操作按任何次序夹入其中，
请回答下有问题：
?（ 1）若入栈次序为 push(1),pop(),push(2，
push(3),pop(),pop( ),push(4),pop( )，则
出栈的数字序列为什么？
?（ 2）能否得到出栈序列车员 423和平共处五项原
则 432？并说明为什么不能得到或如何得到。
203北京邮电大学自动化学院
谢 谢 !
