（精选）数据结构讲义.ppt

数据结构 计算机系 1 第一章绪论 1 1什么是数据结构1 2基本概念和术语1 3抽象数据类型的表示与实现1 4算法和算法分1 4 1算法1 4 2算法设计的要求1 4 3算法效率的度量1 4 4算法的存储空间的需求 2 第一章绪论 计算机是一门研究用计算机进行信息表示和处理的科学 这里面涉及到两个问题 信息的表示信息的处理而信息的表示和组又直接关系到处理信息的程序的效率 随着计算机的普及 信息量的增加 信息范围的拓宽 使许多系统程序和应用程序的规模很大 结构又相当复杂 因此 为了编写出一个 好 的程序 必须分析待处理的对象的特征及各对象之间存在的关系 这就是数据结构这门课所要研究的问题 3 1 1什么是数据结构众所周知 计算机的程序是对信息进行加工处理 在大多数情况下 这些信息并不是没有组织 信息 数据 之间往往具有重要的结构关系 这就是数据结构的内容 那么 什么是数据结构呢 先看以下几个例子 例1 电话号码查询系统设有一个电话号码薄 它记录了N个人的名字和其相应的电话号码 假定按如下形式安排 a1 b1 a2 b2 an bn 其中ai bi i 1 2 n 分别表示某人的名字和对应的电话号码要求设计一个算法 当给定任何一个人的名字时 该算法能够打印出此人的电话号码 如果该电话簿中根本就没有这个人 则该算法也能够报告没有这个人的标志 4 算法的设计 依赖于计算机如何存储人的名字和对应的电话号码 或者说依赖于名字和其电话号码的结构 数据的结构 直接影响算法的选择和效率 上述的问题是一种数据结构问题 可将名字和对应的电话号码设计成 二维数组 表结构 向量 假定名字和其电话号码逻辑上已安排成N元向量的形式 它的每个元素是一个数对 ai bi 1 i n数据结构还要提供每种结构类型所定义的各种运算的算法 5 例2 图书馆的书目检索系统自动化问题例3 教师资料档案管理系统例4 多叉路口交通灯的管理问题P3通过以上几例可以直接地认为 数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系 并对这种结构定义相应的运算 而且确保经过这些运算后所得到的新结构仍然是原来的结构类型 6 1 2基本概念和术语数据 Data 是对信息的一种符号表示 在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称 数据元素 DataElement 是数据的基本单位 在计算机程序中通常作为一个整体进行考虑和处理 一个数据元素可由若干个数据项组成 数据项是数据的不可分割的最小单位 数据对象 DataObject 是性质相同的数据元素的集合 是数据的一个子集 数据结构 DataStructure 是相互之间存在一种或多种特定关系的数据元素的集合 7 数据结构主要指逻辑结构和物理结构数据之间的相互关系称为逻辑结构 通常分为四类基本结构 一 集合结构中的数据元素除了同属于一种类型外 别无其它关系 二 线性结构结构中的数据元素之间存在一对一的关系 三 树型结构结构中的数据元素之间存在一对多的关系 四 图状结构或网状结构结构中的数据元素之间存在多对多的关系 8 数据结构的形式定义为 数据结构是一个二元组 Data Structure D S 其中 D是数据元素的有限集 S是D上关系的有限集 例复数的数据结构定义如下 Complex C R 其中 C是含两个实数的集合 C1 C2 分别表示复数的实部和虚部 R P P是定义在集合上的一种关系 C1 C2 数据结构在计算机中的表示称为数据的物理结构 又称为存储结构 9 数据对象可以是有限的 也可以是无限的 数据结构不同于数据类型 也不同于数据对象 它不仅要描述数据类型的数据对象 而且要描述数据对象各元素之间的相互关系 抽象数据类型 一个数学模型以及定义在该模型上的一组操作 抽象数据类型实际上就是对该数据结构的定义 因为它定义了一个数据的逻辑结构以及在此结构上的一组算法 用三元组描述如下 10 数据结构在计算机中有两种不同的表示方法 顺序表示和非顺序表示由此得出两种不同的存储结构 顺序存储结构和链式存储结构顺序存储结构 用数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系 链式存储结构 在每一个数据元素中增加一个存放地址的指针 用此指针来表示数据元素之间的逻辑关系 11 数据类型 在一种程序设计语言中 变量所具有的数据种类 例1 在FORTRAN语言中 变量的数据类型有整型 实型 和复数型例2 在C语言中数据类型 基本类型和构造类型基本类型 整型 浮点型 字符型构造类型 数组 结构 联合 指针 枚举型 自定义数据对象 某种数据类型元素的集合 例3 整数的数据对象是 3 2 1 0 1 2 3 英文字符类型的数据对象是 A B C D E F 12 1 3抽象数据类型的表示和实现P11 13 1 4算法和算法分析算法 是对特定问题求解步骤的一种描述算法是指令的有限序列 其中每一条指令表示一个或多个操作 算法具有以下五个特性 1 有穷性一个算法必须总是在执行有穷步之后结束 且每一步都在有穷时间内完成 2 确定性算法中每一条指令必须有确切的含义 不存在二义性 且算法只有一个入口和一个出口 3 可行性一个算法是可行的 即算法描述的操作都是可以通过已经实现的基本运算执行有限次来实现的 14 4 输入一个算法有零个或多个输入 这些输入取自于某个特定的对象集合 5 输出一个算法有一个或多个输出 这些输出是同输入有着某些特定关系的量 1 4 2算法设计的要求评价一个好的算法有以下几个标准 1 正确性 Correctness 算法应满足具体问题的需求 2 可读性 Readability 算法应该好读 以有利于阅读者对程序的理解 3 健状性 Robustness 算法应具有容错处理 当输入非法数据时 算法应对其作出反应 而不是产年莫名其妙的输出结果 15 4 效率与存储量需求效率指的是算法执行的时间 存储量需求指算法执行过程中所需要的最大存储空间 一般 这两者与问题的规模有关 1 4 3算法效率的度量对一个算法要作出全面的分析可分成两用人才个阶段进行 即事先分析和事后测试事先分析求出该算法的一个时间界限函数事后测试收集此算法的执行时间和实际占用空间的统计资料 定义 如果存在两个正常数c和n0 对于所有的n n0 有 f n c g n 则记作f n O g n 16 一般情况下 算法中基本操作重复执行的次数是问题规模n的某个函数 算法的时间量度记作T n O f n 称作算法的渐近时间复杂度 例 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 17 由于是一个三重循环 每个循环从1到n 则总次数为 n n n n3时间复杂度为T n O n3 频度 是指该语句重复执行的次数例 x s 0 将x自增看成是基本操作 则语句频度为 即时间复杂度为 1 如果将s 0也看成是基本操作 则语句频度为 其时间复杂度仍为 1 即常量阶 例 for I 1 I n I x s x 语句频度为 2n其时间复杂度为 O n 即时间复杂度为线性阶 18 例 for I 1 I n I for j 1 j n j x s x 语句频度为 2n2其时间复杂度为 O n2 即时间复杂度为平方阶 定理 若A n amnm am 1nm 1 a1n a0是一个m次多项式 则A n O nm 证略 例 for i 2 i n I for j 2 j i 1 j x a i j x 19 语句频度为 1 2 3 n 2 1 n 2 n 2 2 n 1 n 2 2 n2 3n 2 时间复杂度为O n2 即此算法的时间复杂度为平方阶 一个算法时间为O 1 的算法 它的基本运算执行的次数是固定的 因此 总的时间由一个常数 即零次多项式 来限界 而一个时间为O n2 的算法则由一个二次多项式来限界 20 以下六种计算算法时间的多项式是最常用的 其关系为 O 1 O logn O n O nlogn O n2 O n3 指数时间的关系为 O 2n O n O nn 当n取得很大时 指数时间算法和多项式时间算法在所需时间上非常悬殊 因此 只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法 那就取得了一个伟大的成就 21 有的情况下 算法中基本操作重复执行的次数还随问题的输入数据集不同而不同 例如 Voidbubble sort inta intn for I n 1 change TURE I 1change TURE 最好情况 0次 22 最坏情况 1 2 3 n 1 n n 1 2平均时间复杂度为 O n2 1 4 4算法的存储空间需求空间复杂度 算法所需存储空间的度量 记作 S n O f n 其中n为问题的规模 或大小 23 第二章线性表 2 1线性表的类型定义2 2线性表的顺序表示和实现2 3线性表的链式表示和实现2 3 1线性链表2 3 2循环链表2 3 3双向链表2 4一元多项式的表示及相加 24 2 1线性表的逻辑结构线性表 LinearList 由n n 个数据元素 结点 a1 a2 an组成的有限序列 其中数据元素的个数n定义为表的长度 当n 0时称为空表 常常将非空的线性表 n 0 记作 a1 a2 an 这里的数据元素ai 1 i n 只是一个抽象的符号 其具体含义在不同的情况下可以不同 例1 26个英文字母组成的字母表 A B C Z 例2 某校从1978年到1983年各种型号的计算机拥有量的变化情况 6 17 28 50 92 188 25 例3 学生健康情况登记表如下 26 例4 一副扑克的点数 2 3 4 J Q K A 从以上例子可看出线性表的逻辑特征是 在非空的线性表 有且仅有一个开始结点a1 它没有直接前趋 而仅有一个直接后继a2 有且仅有一个终端结点an 它没有直接后继 而仅有一个直接前趋an 1 其余的内部结点ai 2 i n 1 都有且仅有一个直接前趋ai 1和一个直接后继ai 1 线性表是一种典型的线性结构 数据的运算是定义在逻辑结构上的 而运算的具体实现则是在存储结构上进行的 抽象数据类型的定义为 P19 27 算法2 1例2 1利用两个线性表LA和LB分别表示两个集合A和B 现要求一个新的集合A A B voidunion Listif locateelem la e equal listinsert la la en e 28 算法2 2例2 2巳知线性表LA和线性表LB中的数据元素按值非递减有序排列 现要求将LA和LB归并为一个新的线性表LC 且LC中的元素仍按值非递减有序排列 此问题的算法如下 29 voidmergelist listla listlb listwhile I la len j lb len 30 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 bi 31 2 2线性表的顺序存储结构2 2 1线性表把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里 用这种方法存储的线性表简称顺序表 假设线性表的每个元素需占用l个存储单元 并以所占的第一个单元的存储地址作为数据元素的存储位置 则线性表中第I 1个数据元素的存储位置LOC ai 1 和第i个数据元素的存储位置LOC aI 之间满足下列关系 LOC ai 1 LOC ai l线性表的第i个数据元素ai的存储位置为 LOC ai LOC a1 I 1 l 32 由于C语言中的一维数组也是采用顺序存储表示 故可以用数组类型来描述顺序表 又因为除了用数组来存储线性表的元素之外 顺序表还应该用一个变量来表示线性表的长度属性 所以我们用结构类型来定义顺序表类型 defineListSize100typedefintDataType typedefstruc DataTypedata ListSize intlength Sqlist 33 2 2 2顺序表上实现的基本操作在顺序表存储结构中 很容易实现线性表的一些操作 如线性表的构造 第i个元素的访问 注意 C语言中的数组下标从 0 开始 因此 若L是Sqlist类型的顺序表 则表中第i个元素是l data I 1 以下主要讨论线性表的插入和删除两种运算 1 插入线性表的插入运算是指在表的第I 1 i n 1个位置上 插入一个新结点x 34 使长度为n的线性表 a1 ai 1 ai an 变成长度为n 1的线性表 a1 ai 1 x ai an 算法2 3VoidInsertList Sqlist L DataTypex intI intj if Il length 1 printf Positionerror returnERROR 35 if l length ListSize printf overflow exit overflow for j l length 1 j I 1 j l data j 1 l data j l data I 1 x l length 36 现在分析算法的复杂度 这里的问题规模是表的长度 设它的值为 该算法的时间主要化费在循环的结点后移语句上 该语句的执行次数 即移动结点的次数 是 由此可看出 所需移动结点的次数不仅依赖于表的长度 而且还与插入位置有关 当时 由于循环变量的终值大于初值 结点后移语句将不进行 这是最好情况 其时间复杂度O 1 当 1时 结点后移语句将循环执行n次 需移动表中所有结点 这是最坏情况 37 其时间复杂度为O n 由于插入可能在表中任何位置上进行 因此需分析算法的平均复杂度在长度为n的线性表中第i个位置上插入一个结点 令Eis n 表示移动结点的期望值 即移动的平均次数 则在第i个位置上插入一个结点的移动次数为n I 1 故Eis n pi n I 1 不失一般性 假设在表中任何位置 1 i n 1 上插入结点的机会是均等的 则p1 p2 p3 pn 1 1 n 1 因此 在等概率插入的情况下 Eis n n I 1 n 1 n 2 38 也就是说 在顺序表上做插入运算 平均要移动表上一半结点 当表长n较大时 算法的效率相当低 虽然Eis n 中n的的系数较小 但就数量级而言 它仍然是线性阶的 因此算法的平均时间复杂度为O n 2 删除线性表的删除运算是指将表的第i 1 i n 结点删除 使长度为n的线性表 a1 ai 1 ai ai 1 an 变成长度为n 1的线性表 a1 ai 1 ai 1 an 39 VoiddeleteList Sqlist L intI intj if Il length printf Positionerror returnERRORfor j i j l length 1 j l data j 1 l data j l length 40 该算法的时间分析与插入算法相似 结点的移动次数也是由表长n和位置i决定 若I n 则由于循环变量的初值大于终值 前移语句将不执行 无需移动结点 若I 1 则前移语句将循环执行n 1次 需移动表中除开始结点外的所有结点 这两种情况下算法的时间复杂度分别为O 1 和O n 删除算法的平均性能分析与插入算法相似 在长度为n的线性表中删除一个结点 令Ede n 表示所需移动结点的平均次数 删除表中第i个结点的移动次数为n i 故Ede n pi n I 式中 pi表示删除表中第i个结点的概率 在等 41 概率的假设下 p1 p2 p3 pn 1 n由此可得 Ede n n I n n 1 2即在顺序表上做删除运算 平均要移动表中约一半的结点 平均时间复杂度也是O n 2 3线性表的链式表示和实现线性表的顺序表示的特点是用物理位置上的邻接关系来表示结点间的逻辑关系 这一特点使我们可以随机存取表中的任一结点 但它也使得 42 插入和删除操作会移动大量的结点 为避免大量结点的移动 我们介绍线性表的另一种存储方式 链式存储结构 简称为链表 LinkedList 2 3 1线性链表链表是指用一组任意的存储单元来依次存放线性表的结点 这组存储单元即可以是连续的 也可以是不连续的 甚至是零散分布在内存中的任意位置上的 因此 链表中结点的逻辑次序和物理次序不一定相同 为了能正确表示结点间的逻辑关系 在存储每个结点值的同时 还必须存储指示其后继结点的地址 或位置 信息 这个信息称为指针 pointer 或链 link 这两部分组成了链表中的结点结构 43 其中 data域是数据域 用来存放结点的值 next是指针域 亦称链域 用来存放结点的直接后继的地址 或位置 链表正是通过每个结点的链域将线性表的n个结点按其逻辑次序链接在一起的 由于上述链表的每一个结只有一个链域 故将这种链表称为单链表 SingleLinked 显然 单链表中每个结点的存储地址是存放在其前趋结点next域中 而开始结点无前趋 故应设头指针head指向开始结点 同时 由于终端结点无后继 故终端结点的指针域为空 即null 图示中也可用 表示 例1 线性表 bat cat eat fat hat jat lat mat 44 的单链表示意图如下 110 130135 160头指针head165170 200205 45 head bat cat eat mat 单链表是由表头唯一确定 因此单链表可以用头 指针的名字来命名 例如 若头指针名是head 则把链表称为表head 用C语言描述的单链表如下 Typedefchardatatype Typedefstructnode datatypedata structnode next listnode 46 typedeflistnode linklist listnode p linklisthead 注意区分指针变量和结点变量这两个不同的概念 P为动态变量 它是通过标准函数生成的 即p listnode malloc sizeof listnode 函数malloc分配了一个类型为listnode的结点变量的空间 并将其首地址放入指针变量p中 一旦p所指的结点变量不再需要了 又可通过标准函数free p 释放所指的结点变量空间 47 指针变量P和 其值为结点地址 和结点变量 P之间的关系 48 一 建立单链表假设线性表中结点的数据类型是字符 我们逐个输入这些字符型的结点 并以换行符 n 为输入结束标记 动态地建立单链表的常用方法有如下两种 1 头插法建表该方法从一个空表开始 重复读入数据 生成新结点 将读入数据存放到新结点的数据域中 然后将新结点插入到当前链表的表头上 直到读入结束标志为止 49 linklistcreatelistf void charch linklisthead listnode p head null ch getchar while ch n p listnode malloc sizeof listnode p data ch p next head 50 head p ch getchar return head 51 listlinkcreatelist intn intdata linklisthead listnode phead null for i n i 0 i p listnode malloc sizeof listnode scanf d 52 return head 2 尾插法建表头插法建立链表虽然算法简单 但生成的链表中结点的次序和输入的顺序相反 若希望二者次序一致 可采用尾插法建表 该方法是将新结点插入到当前链表的表尾上 为此必须增加一个尾指针r 使其始终指向当前链表的尾结点 例 53 linklistcreater charch linklisthead 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 54 r next p r p if r NULL r next NULL return head 说明 第一个生成的结点是开始结点 将开始结点插入到空表中 是在当前链表的第一个位置上插入 该位置上的插入操作和链表中其它位置上的插入操作处理是不一样的 原因是开始结点的位置是存放在头指针 指针变量 中 55 而其余结点的位置是在其前趋结点的指针域中 算法中的第一个if语句就是用来对第一个位置上的插入操作做特殊处理 算法中的第二个if语句的作用是为了分别处理空表和非空表两种不同的情况 若读入的第一个字符就是结束标志符 则链表head是空表 尾指针r亦为空 结点 r不存在 否则链表head非空 最后一个尾结点 r是终端结点 应将其指针域置空 如果我们在链表的开始结点之前附加一个结点 并称它为头结点 那么会带来以下两个优点 a 由于开始结点的位置被存放在头结点的指针域中 所以在链表的第一个位置上的操作就 56 和在表的其它位置上的操作一致 无需进行特殊处理 b 无论链表是否为空 其头指针是指向头结点在的非空指针 空表中头结点的指针域为空 因此空表和非空表的处理也就统一了 其算法如下 linklistcreatelistr1 charch linklisthead linklist malloc sizeof listnode listnode p r 57 r head while ch getchar n p listnode malloc sizeof listnode p data ch p next p r p r next NULL return head 58 上述算法里动态申请新结点空间时未加错误处理 可作下列处理 p listnode malloc sizeof listnode if p NULL error Nospacefornodecanbeobtained returnERROR 以上算法的时间复杂度均为O n 59 二 查找运算1 按序号查找在链表中 即使知道被访问结点的序号i 也不能象顺序表中那样直接按序号i访问结点 而只能从链表的头指针出发 顺链域next逐个结点往下搜索 直到搜索到第i个结点为止 因此 链表不是随机存取结构 设单链表的长度为n 要查找表中第i个结点 仅当1 i n时 i的值是合法的 但有时需要找头结点的位置 故我们将头结点看做是第0个结点 其算法如下 60 Listnode getnode linklisthead inti intj listnode p p head j 0 while p next 61 elsereturnNULL 2 按值查找按值查找是在链表中 查找是否有结点值等于给定值key的结点 若有的话 则返回首次找到的其值为key的结点的存储位置 否则返回NULL 查找过程从开始结点出发 顺着链表逐个将结点的值和给定值key作比较 其算法如下 62 Listnode locatenode linklisthead intkey listnode p head next while p 该算法的执行时间亦与输入实例中的的取值key有关 其平均时间复杂度的分析类似于按序号查找 也为O n 63 三 插入运算插入运算是将值为x的新结点插入到表的第i个结点的位置上 即插入到ai 1与ai之间 因此 我们必须首先找到ai 1的存储位置p 然后生成一个数据域为x的新结点 p 并令结点 p的指针域指向新结点 新结点的指针域指向结点ai 从而实现三个结点ai 1 x和ai之间的逻辑关系的变化 插入过程如 64 具体算法如下 voidinsertnode linklisthead datetypex inti listnode p q p getnode head i 1 if p NULL error positionerror q listnode malloc sizeof listnode q data x q next p next p next q 65 设链表的长度为n 合法的插入位置是1 i n 1 注意当i 1时 getnode找到的是头结点 当i n 1时 getnode找到的是结点an 因此 用i 1做实参调用getnode时可完成插入位置的合法性检查 算法的时间主要耗费在查找操作getnode上 故时间复杂度亦为O n 四 删除运算删除运算是将表的第i个结点删去 因为在单链表中结点ai的存储地址是在其直接前趋结点aai 1的指针域next中 所以我们必须首先找到 66 ai 1的存储位置p 然后令p next指向ai的直接后继结点 即把ai从链上摘下 最后释放结点ai的空间 将其归还给 存储池 此过程为 67 具体算法如下 voiddeletelist linklisthead inti listnode p r p getnode head i 1 if p NULL p next NULL returnERROR r p next p next r next free r 68 设单链表的长度为n 则删去第i个结点仅当1 i n时是合法的 注意 当i n 1时 虽然被删结点不存在 但其前趋结点却存在 它是终端结点 因此被删结点的直接前趋 p存在并不意味着被删结点就一定存在 仅当 p存在 即p NULL 且 p不是终端结点 即p next NULL 时 才能确定被删结点存在 显然此算法的时间复杂度也是O n 从上面的讨论可以看出 链表上实现插入和删除运算 无须移动结点 仅需修改指针 69 2 3 2循环链表循环链表时一种头尾相接的链表 其特点是无须增加存储量 仅对表的链接方式稍作改变 即可使得表处理更加方便灵活 单循环链表 在单链表中 将终端结点的指针域NULL改为指向表头结点的或开始结点 就得到了单链形式的循环链表 并简单称为单循环链表 为了使空表和非空表的处理一致 循环链表中也可设置一个头结点 这样 空循环链表仅有一个自成循环的头结点表示 如下图所示 70 a1 an head 非空表 空表 在用头指针表示的单链表中 找开始结点a1的时间是O 1 然而要找到终端结点an 则需从头指针开始遍历整个链表 其时间是O n 71 在很多实际问题中 表的操作常常是在表的首尾位置上进行 此时头指针表示的单循环链表就显得不够方便 如果改用尾指针rear来表示单循环链表 则查找开始结点a1和终端结点an都很方便 它们的存储位置分别是 rear next next和rear 显然 查找时间都是O 1 因此 实际中多采用尾指针表示单循环链表 由于循环链表中没有NULL指针 故涉及遍历操作时 其终止条件就不再像非循环链表那样判断p或p next是否为空 而是判断它们是否等于某一指定指针 如头指什或尾指针等 72 例 在链表上实现将两个线性表 a1 a2 a3 an 和 b1 b2 b3 bn 链接成一个线性表的运算 linklistconnect linklistheada linklistheadb linklistp heada next heada next headb next nextfree headb next headb next p return headb 73 2 3 3双链表双向链表 Doublelinkedlist 在单链表的每个结点里再增加一个指向其直接前趋的指针域prior 这样就形成的链表中有两个方向不同的链 故称为双向链表 形式描述为 typedefstructdlistnode datatypedata strucdlistnode prior next dlistnode typedefdlistnode dlinklist dlinklisthead 74 和单链表类似 双链表一般也是由头指针唯一确定的 增加头指针也能使双链表上的某些运算变得方便 将头结点和尾结点链接起来也能构成循环链表 并称之为双向链表 设指针p指向某一结点 则双向链表结构的对称性可用下式描述 p prior next p p next prior即结点 p的存储位置既存放在其前趋结点 p prior 的直接后继指针域中 也存放在它的后继结点 p next 的直接前趋指针域中 75 双向链表的前插操作算法如下 voiddinsertbefor dlistnode p datatypex dlistnode q malloc sizeof dlistnode q data x q prior p prior q next p p prior next q p prior q 76 voidddeletenode dlistnode p p prior next p next p next prior p prior free p 注意 与单链表的插入和删除操作不同的是 在双链表中插入和删除必须同时修改两个方向上的指针 上述两个算是法的时间复杂度均为O 1 77 第三章栈和队列 3 1栈3 1 1抽象数据类型栈的定义3 1 2栈的表示和实现3 2栈的应用举例3 2 1数制转换3 2 2括号匹配的检验3 2 4行编辑程序3 2 5迷宫求解3 2 5表达式求值 78 3 1 1栈3 1 1栈的定义及基本运算栈 Stack 是限制在表的一端进行插入和删除运算的线性表 通常称插入 删除的这一端为栈顶 Top 另一端为栈底 Bottom 当表中没有元素时称为空栈 假设栈S a1 a2 a3 an 则a1称为栈底元素 an为栈顶元素 栈中元素按a1 a2 a3 an的次序进栈 退栈的第一个元素应为栈顶元素 换句话说 栈的修改是按后进先出的原则进行的 因此 栈称为后进先出表 LIFO 79 3 1 2顺序栈由于栈是运算受限的线性表 因此线性表的存储结构对栈也适应 栈的顺序存储结构简称为顺序栈 它是运算受限的线性表 因此 可用数组来实现顺序栈 因为栈底位置是固定不变的 所以可以将栈底位置设置在数组的两端的任何一个端点 栈顶位置是随着进栈和退栈操作而变化的 故需用一个整型变量top 80 例 一叠书或一叠盘子 栈的抽象数据类型的定义如下 P44 栈顶 栈底 81 top 7654321 1 82 来指示当前栈顶的位置 通常称top为栈顶指针 因此 顺序栈的类型定义只需将顺序表的类型定义中的长度属性改为top即可 顺序栈的类型定义如下 defineStackSize100typedefchardatatype typedefstruct datatypedata stacksize inttop seqstack 83 设S是SeqStack类型的指针变量 若栈底位置在向量的低端 即s data 0 是栈底元素 那么栈顶指针s top是正向增加的 即进栈时需将s top加1 退栈时需将s top减1 因此 s toptop stacksize 1表示栈满 当栈满时再做进栈运算必定产生空间溢出 简称 上溢 当栈空时再做退栈运算也将产生溢出 简称 下溢 上溢是一种出错状态 应该设法避免之 下溢则可能是正常现象 因为栈在程序中使用时 其初态或终态都是空栈 所以下溢常常用来作为程序控制转移的条件 84 3 判断栈满intstackfull seqstack s return s top stacksize 1 4 进栈voidpush seqstack s datatypex if stackfull s error stackoverflow s data s top x 85 1 置空栈voidinitstack seqstack s s top 1 2 判断栈空intstackempty seqstack s return s top 1 86 5 退栈datatypepop seqstack s if stackempty s error stackunderflow x s data top s top return x return s data s top 87 6 取栈顶元素Datatypestacktop seqstack s if stackempty s error stackisenpty returns data s top 88 3 1 3链栈栈的链式存储结构称为链栈 它是运算是受限的单链表 克插入和删除操作仅限制在表头位置上进行 由于只能在链表头部进行操作 故链表没有必要像单链表那样附加头结点 栈顶指针就是链表的头指针 链栈的类型说明如下 typedefstructstacknode datatypedatastructstacknode next stacknode 89 Voidinitstack seqstack p p top null intstackempty linkstack p returnp top null 90 Voidpush linkstack p datatypex stacknode qq stacknode malloc sizeof stacknode q data x q next p top p top p 91 Datatypepop linkstack p datatypex stacknode q p top if stackempty p error stackunderflow x q data p top q next free q returnx 92 datatypestacktop linkstack p if stackempty p error stackisempty returnp top data 93 3 2栈的应用举例由于栈结构具有的后进先出的固有特性 致使栈成为程序设计中常用的工具 以下是几个栈应用的例子 3 2 1数制转换十进制N和其它进制数的转换是计算机实现计算的基本问题 其解决方法很多 其中一个简单算法基于下列原理 N ndivd d nmodd 其中 div为整除运算 mod为求余运算 例如 1348 10 2504 8 其运算过程如下 94 nndiv8nmod8134816841682102125202 95 voidconversion initstack s scanf n while n push s n 8 n n 8 while Stackempty s pop s e printf d e 96 3 2 2括号匹配的检验假设表达式中充许括号嵌套 则检验括号是否匹配的方法可用 期待的急迫程度 这个概念来描述 例 3 2 3行编辑程序在编辑程序中 设立一个输入缓冲区 用于接受用户输入的一行字符 然后逐行存入用户数据区 允许用户输入错误 并在发现有误时可以及时更正 97 行编辑程序算法如下 voidlineedit initstack s ch gether while ch eof while ch eof 98 ch getchar clearstack s if ch eof ch gethar destroystack s 99 3 2 4迷宫求解入口 出口 100 3 4队列3 4 1抽象数据类型队列的定义队列 Queue 也是一种运算受限的线性表 它只允许在表的一端进行插入 而在另一端进行删除 允许删除的一端称为队头 front 允许插入的一端称为队尾 rear 例如 排队购物 操作系统中的作业排队 先进入队列的成员总是先离开队列 因此队列亦称作先进先出 FirstInFirstOut 的线性表 简称FIFO表 当队列中没有元素时称为空队列 在空队列中依次加入元素a1 a2 an之后 a1是队头元素 an是队尾元素 显然退出队列的次序也只能是a1 a2 an 也就是说队列的修改是依先进先出的原则进行的 101 下图是队列的示意图 a1a2 an 出队 入队 队头 队尾 队列的抽象数据定义见书 59 3 4 2循环队列 队列的顺序表示和实现队列的顺序存储结构称为顺序队列 顺序队列实际上是运算受限的顺序表 和顺序表一样 顺序队列也是必须用一个向量空间来存放当前队 102 列中的元素 由于队列的队头和队尾的位置是变化的 因而要设两个指针和分别指示队头和队尾元素在队列中的位置 它们的初始值地队列初始化时均应置为 入队时将新元素插入所指的位置 然后将加 出队时 删去所指的元素 然后将加 并返回被删元素 由此可见 当头尾指针相等时队列为空 在非空队列里 头指针始终指向队头元素 而尾指针始终指向队尾元素的下一位置 0123 Frontrear Frontrear a 队列初始为空 b A B C入队 103 frontrearfrontrear c a出队 d b c出队 队为空和栈类似 队列中亦有上溢和下溢现象 此外 顺序队列中还存在 假上溢 现象 因为在入队和出队的操作中 头尾指针只增加不减小 致使被删除元素的空间永远无法重新利用 因此 尽管队列中实际的元素个数远远小于向量空间的规模 但也可能由于尾指针巳超出向量空间的上界而不能做入队操作 该现象称为假上溢 104 为充分利用向量空间 克服上述假上溢现象的方法是将向量空间想象为一个首尾相接的圆环 并称这种向量为循环向量 存储在其中的队列称为循环队列 CircularQueue 在循环队列中进行出队 入队操作时 头尾指针仍要加1 朝前移动 只不过当头尾指针指向向量上界 QueueSize 1 时 其加1操作的结果是指向向量的下界0 这种循环意义下的加1操作可以描述为 if I 1 QueueSize i 0 elsei 利用模运算可简化为 i i 1 QueueSize 105 显然 因为循环队列元素的空间可以被利用 除非向量空间真的被队列元素全部占用 否则不会上溢 因此 除一些简单的应用外 真正实用的顺序队列是循环队列 如图所示 由于入队时尾指针向前追赶头指针 出队时头指针向前追赶尾指针 故队空和队满时头尾指针均相等 因此 我们无法通过front rear来判断队列 空 还是 满 解决此问题的方法至少有三种 其一是另设一个布尔变量以匹别队列的空和满 其二是少用一个元素的空间 约定入队前 测试尾指针在循环意义下加1后是否等于头指针 若相等则认为队满 注意 rear所指的单元始终为空 106 其三是使用一个计数器记录队列中元素的总数 实际上是队列长度 下面我们用第三种方法实现循环队列上的六种基本操作 为此先给出循环队列的类型定义 defineQueueSize100typedefcharDataType typedefStruct intfront intrear intcount datatypedata queuesize cirqueue 107 1 置空队voidinitqueue cirqueue q q front q rear 0 q count 0 2 判断队空intqueueempty cirqueue q returnq count 0 3 判断队满intqueuefull cirqueue q returnq count queuesize 108 4 入队voidenqueue cirqueue q datatypex if queuefull q error queueoverflow q count q data q rear x q rear q rear 1 queuesize 109 5 出队datatypedequeue cirqueue q datatypetemp if queueempty q error queueunderflow temp q data q front q count q front q front 1 queuesize returntemp 110 6 取头指针datatypequeuefront cirqueue q if queueempty q error queueisempty returnq data q front 111 3 4 3链队列队列的链式存储结构简称为链队列 它是限制仅在表头删除和表尾插入的单链表 显然仅有单链表的头指针不便于在表尾做插入操作 为此再增加一个尾指针 指向链表的最后一个结点 于是 一个链队列由一个头指针唯一确定 和顺序队列类似 我们也是将这两个指针封装在一起 将链队列的类型LinkQueue定义为一个结构类型 typedefstructqueuenode datatypedata structqueuenode next queuenode 112 typedefstruct queuenode front queuenode rear linkqueue 下面给出链队列上实现的基本运算 voidinitqueue linkqueue q q front q rear null 113 intqueueempty linkqueue q returnq front null 114 else q rear next p q rear p Datatypedequeue linkqueue q datatypex queuenode p 115 if queueempty q error queueunderflow p q front x p data q front p next if q rear p q rear null free p returnx 116 datatypequeuefront linkqueue q if queueempty q error queueisempty returnq front data 注意 在出队算法中 一般只需修改队头指针 但当原队中只有一个结点时 该结点既是队头也是队尾 故删去此结点时亦需修改尾指针 且删去此结点后队列变空 117 习题1 设将整数以万计 2 3 4依次进栈 但只要出栈时栈非空 则可将出栈操作按任何次序夹入其中 请回答下有问题 1 若入栈次序为push 1 pop push 2 push 3 pop pop push 4 pop 则出栈的数字序列为什么 2 能否得到出栈序列车员423和平共处五项原则432 并说明为什么不能得到或如何得到 3 请分析1 2 3 4的24种排列中 哪些序列可以通过相应的入出栈得到 2 链栈中为何不设头指针 3 循环队列的优点是什么 如何判断它的空和满 118 4 设长度为n的链队列用单循环链表表示 若只设头指针 则怎样进行入队和出队操作 若只设尾指针呢 5 利用栈的基本操作 写一个返回栈s中结点个数的算法intstacksize seqstacks 并说明s为何不用作为指针参数 6 利用栈的基本操作 写一个将栈中所有结点均删除算法 并说明S为何要作为指针参数 7 用第二种方法 即少用一个元素空间的方法来区别循环队列的队空和队满 试设计置空队 判队空 判队满 出队 入队及取队头元素等六个基本操作 119