四章节数据结构

《四章节数据结构》由会员分享，可在线阅读，更多相关《四章节数据结构（44页珍藏版）》请在金锄头文库上搜索。

1、第四章第四章 数据结构数据结构主要内容主要内容4.1 基本数据结构与算法基本数据结构与算法 4.2 线性表线性表 4.3 栈和队列栈和队列4.4 树和二叉树树和二叉树 4.5 查找查找4.6 内部排序内部排序4.1 基本数据结构与算法基本数据结构与算法 4.1.1 数据结构的基本概念数据结构的基本概念1.1.数据结构的定义数据结构的定义(1)(1)数据：数据：信息载体，能够被计算机识别、存储和加工信息载体，能够被计算机识别、存储和加工处理。可以使数值数据处理。可以使数值数据(整数、实数整数、实数)，也可以是非数值，也可以是非数值数据数据(声音、图像等声音、图像等) 。(2)(2)数据元素：数据

2、元素：数据的基本单位，在计算机程序中通常数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理作为一个整体进行考虑和处理(又称结点、记录又称结点、记录)。 数据项：一个数据元素由若干数据项组成，数据的不可分割的最数据项：一个数据元素由若干数据项组成，数据的不可分割的最 小单位。小单位。 关键码：其值能唯一确定一个数据元素的数据项。关键码：其值能唯一确定一个数据元素的数据项。 举例：图书管理系统举例：图书管理系统 数据元素数据元素 数据项数据项 关键码关键码 (一本书一本书)书目信息书目信息 书目信息每一项书目信息每一项 书号书号(唯一确定一本书唯一确定一本书)(3)(3)数据对象：数据对

3、象：具有相同性质的数据元素的集合。数据具有相同性质的数据元素的集合。数据元素是数据对象类的一个实例。元素是数据对象类的一个实例。 (4)(4)数据结构：数据结构：定义定义: :相互之间存在着一种或多种关系的数据元素的集合。相互之间存在着一种或多种关系的数据元素的集合。研究内容研究内容: :数据的逻辑结构数据的逻辑结构：各数据元素之间的逻辑关系各数据元素之间的逻辑关系数据的存储结构数据的存储结构：各数据元素在计算机中的存储关系各数据元素在计算机中的存储关系对各种数据结构进行的运算对各种数据结构进行的运算：添加，删除，排序等。添加，删除，排序等。2.2.数据的逻辑结构数据的逻辑结构四类基本逻辑结构

4、四类基本逻辑结构(1)集合结构：数据元素间的关系是集合结构：数据元素间的关系是“属于同一个集合属于同一个集合” (2)线性结构：数据元素之间存在一个对一个的关系。线性结构：数据元素之间存在一个对一个的关系。(3)树形结构：数据元素之间存在一个对多个的关系。树形结构：数据元素之间存在一个对多个的关系。 (4)图形结构：数据元素之间存在多个对多个的关系。图形结构：数据元素之间存在多个对多个的关系。 学号学号姓名姓名系别系别住址住址电话电话 .981111李洪李洪机械机械六舍六舍5371111982111王刚王刚电子电子四舍四舍5372111983211王将王将计算机计算机五舍五舍537321198

5、3212张强张强机械机械六舎六舎5372221 线性结构线性结构树型结构树型结构线性结构与非线性结构线性结构与非线性结构概念概念结点结点: :组成数据结构的数据元素称为一个结点。组成数据结构的数据元素称为一个结点。前后件关系前后件关系: :数据元素之间的固有关系可以用前后件关系数据元素之间的固有关系可以用前后件关系( (前驱与后继关系前驱与后继关系) )描述。描述。举例：家庭成员辈分关系举例：家庭成员辈分关系( (父亲、儿子、女儿父亲、儿子、女儿) )，“父亲父亲”是是“儿子儿子”和和“女儿女儿”的前件，的前件， “儿子儿子”和和“女儿女儿”是是 “父亲父亲”后件。后件。线性结构线性结构有且只

6、有一个根结点有且只有一个根结点每个结点最多有一个前件，也最多有一个后件每个结点最多有一个前件，也最多有一个后件非线性结构非线性结构一个数据结构如果不是线性结构，则称之为非线性结构。数一个数据结构如果不是线性结构，则称之为非线性结构。数据元素的前后关系复杂，一个结点既可以有多个前件，也可据元素的前后关系复杂，一个结点既可以有多个前件，也可以有多个后件。树型、图形结构属于非线性结构。以有多个后件。树型、图形结构属于非线性结构。3.3.数据的存储结构数据的存储结构定义：定义：数据的逻辑结构在计算机存储空间中的存放形式。数据的逻辑结构在计算机存储空间中的存放形式。数据存储结构中不仅存放各数据元素信息，

7、还存放前后件数据存储结构中不仅存放各数据元素信息，还存放前后件关系的信息。关系的信息。 实现方式：实现方式： (1)顺序存储方顺序存储方式式：逻辑上相邻的元素存储在物理位置相邻：逻辑上相邻的元素存储在物理位置相邻的存储单元中的存储单元中。主要用于线性结构。主要用于线性结构。通常借助于数组来实通常借助于数组来实现。现。顺序存储结构的线性表顺序存储结构的线性表线性表线性表(a1, a2, a3, a4)(2)链式链式存储方存储方式式：对逻辑上相邻的元素不要求其物理地址对逻辑上相邻的元素不要求其物理地址相邻，元素间逻辑关系通过附加的指针字段来表示。通常相邻，元素间逻辑关系通过附加的指针字段来表示。通

8、常借助于指针类型实现。借助于指针类型实现。 链链式式存存储储结结构构的的线线性性表表线性表线性表(a1, a2, a3, a4)链式存储结构的特点链式存储结构的特点每个每个结点结点由两部分组成：一部分存放数据，另一部分由两部分组成：一部分存放数据，另一部分存储存储指向前件或后件结点的指针域。指向前件或后件结点的指针域。逻辑上相邻的结点物理上不必相连。逻辑上相邻的结点物理上不必相连。数据运算数据运算(插入和删除等插入和删除等)灵活。灵活。 (3)索引索引存储存储方法和散列存储方法方法和散列存储方法(为了查找方便为了查找方便) 4.4.数据结构的表示数据结构的表示(1)(1)二元关系表示二元关系表

9、示B=( D, R ) B：数据结构：数据结构D：数据元素的集合：数据元素的集合R：D上的关系上的关系(反映数据元素前后件关系反映数据元素前后件关系) 家庭成员数据结构家庭成员数据结构B=( D, R )D =父亲父亲,儿子儿子,女儿女儿R =(父亲父亲,儿子儿子),(父亲父亲,女儿女儿)(2)(2)图形表示图形表示D D中每个数据元素用标有元素值的方框表示中每个数据元素用标有元素值的方框表示, ,简称结点。简称结点。R R中每个二元组中每个二元组, ,用一条有向线段从前件结点指向后件结点。用一条有向线段从前件结点指向后件结点。根结点：没有前件的结点根结点：没有前件的结点叶子结点叶子结点( (

10、终端结点终端结点) )：没有后件的结点：没有后件的结点5.5.数据的运算数据的运算定义：定义：在数据的逻辑结构上定义的操作算法在数据的逻辑结构上定义的操作算法 常见运算：常见运算：插入、删除、查找、排序和更新等插入、删除、查找、排序和更新等 分类：分类： 加工型运算：运算改变了数据结构的值加工型运算：运算改变了数据结构的值引用型运算：不改变值，只查询或求得结构的值。引用型运算：不改变值，只查询或求得结构的值。 4.1.2 算法和算法分析算法和算法分析 1.1.算法基本概念算法基本概念定义：定义：为解决某个特定问题而采取的确定且有限的步骤为解决某个特定问题而采取的确定且有限的步骤的一种描述。的一

11、种描述。(解题方案的准确而完整描述解题方案的准确而完整描述) 特点特点( (五个五个) )：有穷性：包含有限个操作步骤，有限时间内完成。有穷性：包含有限个操作步骤，有限时间内完成。确定性：每一条指令无二义性确定性：每一条指令无二义性可行性：指定操作都可以实现可行性：指定操作都可以实现输入性：一个算法有零个或多个的输入输入性：一个算法有零个或多个的输入输出性：一个算法有一个或多个的输出输出性：一个算法有一个或多个的输出2.2.算法基本要素及描述算法基本要素及描述基本要素：基本要素：数据对象的运算和操作数据对象的运算和操作算法的控制结构算法的控制结构算法表示：算法表示：自然语言，伪代码，流程图自然

12、语言，伪代码，流程图3.3.算法设计要求算法设计要求(1)正确性：执行结果应满足预先的功能和性能要求正确性：执行结果应满足预先的功能和性能要求(2)可读性：层次分明、易读易懂。可读性：层次分明、易读易懂。(3)健壮性：输入数据非法时，算法能作适当处理健壮性：输入数据非法时，算法能作适当处理(4) 效率：效率： 有效使用存储空间和较高的时间效率。有效使用存储空间和较高的时间效率。4.4.算法的设计方法算法的设计方法(1)列举法：列举法：列举出所有可能情况，用给定条件检验哪列举出所有可能情况，用给定条件检验哪些是需要的，哪些是不需要的。些是需要的，哪些是不需要的。(2)归纳法：归纳法：列举少量简单

13、而又特殊的情况，分析归纳列举少量简单而又特殊的情况，分析归纳出一般结论。出一般结论。 (3)递推法：递推法：从已知初始条件出发，逐步推出各种中间结果从已知初始条件出发，逐步推出各种中间结果和最后结果。和最后结果。 (4)递归法：递归法：解决复杂问题时，将问题逐层分解，归纳为一解决复杂问题时，将问题逐层分解，归纳为一些简单问题，解决了最后简单问题后，再沿原来的逆过程逐些简单问题，解决了最后简单问题后，再沿原来的逆过程逐步综合步综合 。(5)减半递推技术：减半递推技术：减少：问题规模减半，而性质不变减少：问题规模减半，而性质不变递推：重复减半的过程递推：重复减半的过程(6)回溯法：回溯法：尝试。分

14、析找出解决线索，逐步试尝试。分析找出解决线索，逐步试探探成功：求得解成功：求得解失败：逐步回推，换线索再试探。失败：逐步回推，换线索再试探。5.5.算法复杂度算法复杂度评价算法标准：评价算法标准：算法所占用计算机资源，即时间代价和算法所占用计算机资源，即时间代价和空间代价。空间代价。 相关名词：相关名词：(1)问题规模：不同种类问题，问题规模含义不同。如矩问题规模：不同种类问题，问题规模含义不同。如矩阵运算取决于矩阵阶数，多项式运算取决于项数。阵运算取决于矩阵阶数，多项式运算取决于项数。(2)算法运行时间：大致等于其所有语句执行时间的总和。算法运行时间：大致等于其所有语句执行时间的总和。(3)

15、语句频度：该语句在算法中重复执行的次数。语句频度：该语句在算法中重复执行的次数。算法的时间复杂度：算法的时间复杂度：定义：定义：算法运行从开始到结束所需要的计算工作量。算法运行从开始到结束所需要的计算工作量。 记作：记作：T (n)=O( f (n) ) n：问题规模。：问题规模。 T (n) 是是n的某个函数。的某个函数。O：数量级。当问题规模趋向无穷时，：数量级。当问题规模趋向无穷时， T (n)的数量级的数量级称为时间复杂度。称为时间复杂度。算法的时间复杂度不仅仅依赖于问题的规模，也取决于算法的时间复杂度不仅仅依赖于问题的规模，也取决于输入实例的初始状态。输入实例的初始状态。 最优算法：

16、随最优算法：随n n的增大，的增大， T (n)增长较慢的算法。增长较慢的算法。两种：两种：平均时间复杂度：平均时间复杂度：所有可能的输入实例均以等概率出现所有可能的输入实例均以等概率出现的情况下，算法的期望运行时间。的情况下，算法的期望运行时间。最坏时间复杂度：最坏时间复杂度：最坏情况下算法的时间复杂度。最坏情况下算法的时间复杂度。 算法的空间复杂度：算法的空间复杂度：定义：定义：算法运行从开始到结束所需的存储空间量算法运行从开始到结束所需的存储空间量(耗费的耗费的存储空间存储空间)。所需存储空间包括两部分所需存储空间包括两部分固定部分：固定部分：此部分空间与所处理数据的大小和规模无关。此部

17、分空间与所处理数据的大小和规模无关。可变部分：可变部分：此部分空间与处理的数据的大小和规模有关，此部分空间与处理的数据的大小和规模有关， 即执行算法所需额外空间。即执行算法所需额外空间。 4.2 线性表线性表 4.2.1 线性表的基本概念线性表的基本概念定义：定义：具有相同数据类型的具有相同数据类型的n(n0)个数据元素组成的有限个数据元素组成的有限序列。最简单、最常用的数据结构。序列。最简单、最常用的数据结构。 表示：表示：L=( a1，a2，a3，ai-1，ai ，ai+1，an ) n为线性表长度为线性表长度(n=0称为空表称为空表)，表中相邻元素之间存在着，表中相邻元素之间存在着顺序关

18、系。顺序关系。a1 ：表头元素；：表头元素；an ：表尾元素；：表尾元素；ai-1称为称为ai的的直接前驱；直接前驱；ai+1 称为称为ai的直接后继。的直接后继。 结构特点：结构特点：(1)有且只有一个根结点有且只有一个根结点a1，无前驱，无前驱 。(2)有且只有一个终端结点有且只有一个终端结点an ，无后继，无后继 。(3)其他结点有且只有一个直接前驱和一个直接后继。其他结点有且只有一个直接前驱和一个直接后继。 线性表的分类线性表的分类(1)(1)简单线性表：简单线性表：数据元素是简单项数据元素是简单项(数字、字母、季节名数字、字母、季节名等等)，(12,34,4,67,8)(2)(2)复

19、杂线性表：复杂线性表：数据元素由若干个数据项组成，此时数据数据元素由若干个数据项组成，此时数据元素称为记录。元素称为记录。 复杂线性表举例（学生登记表）复杂线性表举例（学生登记表） 姓名姓名学号学号性别性别年龄年龄班级班级王洪强王洪强张利红张利红王刚王刚崔应强崔应强97061970629706397064男男女女男男男男18202117计计97计计97计计97计计974.2.2 线性表的顺序存储结构线性表的顺序存储结构 顺序表：顺序表：采用顺序存储结构的线性表称为顺序表采用顺序存储结构的线性表称为顺序表(一维数组一维数组) 顺序存储：顺序存储：用一组地址连续的存储空间依次存储放线性表的用一组地

20、址连续的存储空间依次存储放线性表的各元素各元素 特点特点( (顺序存储结构顺序存储结构) )表中的所有元素所占存储空间连续表中的所有元素所占存储空间连续表中各元素在存储空间中按逻辑顺序存放表中各元素在存储空间中按逻辑顺序存放 第第i i个元素地址：个元素地址：m：每个元素占：每个元素占m个存储单元个存储单元Loc(a1)第一个元素地址第一个元素地址(基址基址) 1.1.顺序表基本概念顺序表基本概念顺序表的顺序存储结构顺序表的顺序存储结构 2.2.顺序表基本运算顺序表基本运算基本运算：基本运算：插入：在线性表指定位置插入一个新元素插入：在线性表指定位置插入一个新元素删除：删除线性表中指定的元素删

21、除：删除线性表中指定的元素查找：在线性表中查找特定元素查找：在线性表中查找特定元素排序：线性表中元素按关键字升序或降序排序排序：线性表中元素按关键字升序或降序排序分解：将一个线性表分解为多个分解：将一个线性表分解为多个合并合并 复制复制 逆转逆转 插入运算：插入运算：定义：定义：是指在表的第是指在表的第i个位置上插入一个值为个位置上插入一个值为b的新元素的新元素原表长为原表长为n n：( a1，a2，ai-1，ai ，ai+1， an ) 新表长为新表长为n+1n+1：( a1，a2，ai-1，b，ai ，ai+1， ， an ) 步骤：步骤：(1)将将ai an顺序向后移动顺序向后移动,为新

22、元素让出位置为新元素让出位置(2)将将b置入空出的第置入空出的第i个位置个位置举例：举例：( (在第在第4个和第个和第5个元素之间插入元素个元素之间插入元素91) ) 6741262148916 0 1 2 3 4 5 6 7 86741262148916 0 1 2 3 4 5 6 7 86741262148916 0 1 2 3 4 5 6 7 891时间性能分析：时间性能分析：插入运算，时间主要消耗在数据移动上。在长度为插入运算，时间主要消耗在数据移动上。在长度为n n的的线性表中插入一个元素，则线性表中插入一个元素，则平均移动元素次数平均移动元素次数：PiPi：在第：在第i i个位置上

23、作插入的概率。设个位置上作插入的概率。设Pi=1/(n+1) Pi=1/(n+1) 共需共需移动移动(n-i+1)(n-i+1)个元素。个元素。删除运算：删除运算：定义：定义：指将表中第指将表中第i个元素从线性表中去掉。个元素从线性表中去掉。原表长为原表长为n n：( a1，a2，ai-1，ai ，ai+1， an ) 新表长为新表长为n-1n-1：( a1，a2，ai-1，ai+1， ， an ) 步骤：步骤：(1)删除删除ai(2)将将ai+1 an b顺序向前移动顺序向前移动举例：举例：( (删除第五个元素删除第五个元素21) ) 6741262148916 0 1 2 3 4 5 6

24、7 867412648916 0 1 2 3 4 5 6 7 8时间性能分析：时间性能分析：时间消耗与插入运算相同，时间消耗与插入运算相同，平均移动元素次数平均移动元素次数：q qi i: :在第在第i i个位置上作删除的概率。设个位置上作删除的概率。设q qi i=1/n =1/n 共需移动共需移动( (n-in-i) )个元素。个元素。3.3.顺序表优点和缺点顺序表优点和缺点优点：优点：逻辑上相邻元素存储位置也相邻逻辑上相邻元素存储位置也相邻, ,无需增加额外存储空间无需增加额外存储空间可方便随机存取表中任一元素可方便随机存取表中任一元素缺点：缺点：插入和删除运算不方便插入和删除运算不方便

25、, ,必须移动大量结点必须移动大量结点, ,效率较低效率较低不适合元素经常变动的大的线性表不适合元素经常变动的大的线性表4.2.3 线性表的链式存储结构线性表的链式存储结构 链式存储结构：链式存储结构：存储空间可以不连续。存储空间可以不连续。不要求逻辑上相邻不要求逻辑上相邻的元素在物理位置上也相邻。数据元素间逻辑关系由指针的元素在物理位置上也相邻。数据元素间逻辑关系由指针域确定。域确定。 结点组成：结点组成：数据结构中每个数据结点对应一个存储单元，数据结构中每个数据结点对应一个存储单元，简称结点。简称结点。 两部分：两部分：数据域：存放数据元素值数据域：存放数据元素值指针域：存放指针，指向后继

26、结点指针域：存放指针，指向后继结点线性链表中用专门的线性链表中用专门的HEAD指针指向第一个元素的结指针指向第一个元素的结点，其最后一个元素没有后件，因此最后一个结点指点，其最后一个元素没有后件，因此最后一个结点指针域为空针域为空(用用NULL或或0表示表示) 线性链表线性链表定义：定义：线性表的链式存储结构称为线性链表线性表的链式存储结构称为线性链表 分类：分类：单链表、循环单链表、双向链表单链表、循环单链表、双向链表 1.1.单链表单链表定义：定义：由由n个结点链接，且每个结点中只包含一个指针域个结点链接，且每个结点中只包含一个指针域的链表。的链表。 逻辑状态与物理状态：逻辑状态与物理状态

27、：线性单链表线性单链表( A, B, C, D, E, F )( A, B, C, D, E, F )逻辑状态逻辑状态 A B C D EH F物理状态物理状态 E7FNULLB25A13C31D1头指针头指针 存储地址存储地址 数据域数据域 指针域指针域 19 1713192531单链表存取：单链表存取：必须从必须从头指针开始进行，依头指针开始进行，依次顺着指针向链尾方次顺着指针向链尾方向扫描。找到各个元向扫描。找到各个元素。素。(1)(1)单链表插入：单链表插入：增加新结点增加新结点, ,修改链接指针修改链接指针后插结点后插结点在指针在指针p所指结点之后插入一个指针所指结点之后插入一个指针

28、s所指的结点所指的结点修改修改p和和s所指结点的指针域的指针即可所指结点的指针域的指针即可 步骤步骤P B C XS Asnext=pnext 修改修改s指针域指针域, s结点的后继是结点的后继是p结点的后继结点的后继pnexts 修改修改p指针域指针域, 使其指向新结点使其指向新结点s(2)(2)单链表删除：单链表删除：不需要移动元素不需要移动元素, ,仅修改指针链接仅修改指针链接删除结点删除结点删除删除p指向的结点指向的结点只修改只修改p(被删除结点被删除结点)的前驱结点的指针域即可的前驱结点的指针域即可 步骤步骤先找到先找到p的前驱结点的前驱结点q删除删除p结点，修改结点，修改q结点指针

29、域结点指针域 qnextpnext CP B A删除前删除前P删除后删除后q C B A(3)(3)带头结点的单链表带头结点的单链表设置：设置：在单链表的第一个结点之前设一个结点在单链表的第一个结点之前设一个结点(头结点头结点)，其，其数据域可以不存任何信息，指针域指向第一个结点的指针。数据域可以不存任何信息，指针域指向第一个结点的指针。 作用：作用：头结点始终存在，地址不变。头结点始终存在，地址不变。插入和删除第一个结点插入和删除第一个结点时就不影响表头指针时就不影响表头指针(只改变头结点的指针域即可只改变头结点的指针域即可)，简化了，简化了插入、删除算法。插入、删除算法。带头结点的单链表带

30、头结点的单链表L为空的判定条件为：为空的判定条件为：L.next= =NULL 带头结点的单链表带头结点的单链表 2.2.循环链表循环链表特点：特点：表中最后一个结点的指针域指向头结点，整个链表表中最后一个结点的指针域指向头结点，整个链表首尾相连形成一个环。首尾相连形成一个环。 优点：优点：从表中任一结点出发均可找到表中其它结点。从表中任一结点出发均可找到表中其它结点。(单单链表每次查找必须从头指针开始，不方便。链表每次查找必须从头指针开始，不方便。) 注意：注意：操作和线性链表基本一致，差别是循环条件不是操作和线性链表基本一致，差别是循环条件不是判断判断p或或p-next是否为空是否为空,而

31、是它们是否等于头指针而是它们是否等于头指针 。 带头结点的循环单链表带头结点的循环单链表3.3.双向链表双向链表设置：设置：双向链表，每个结点有两个指针域，双向链表，每个结点有两个指针域，next指向后继结指向后继结点，点，prior指向前趋结点。指向前趋结点。 作用：作用：克服克服单链表的的缺点单链表的的缺点每个结点，只能找到它的后继每个结点，只能找到它的后继结点，不能找到前驱结点。若要找前驱结点，必须从头指针结点，不能找到前驱结点。若要找前驱结点，必须从头指针开始重新查找。使用双向链表可以方便地沿向前或向后两个开始重新查找。使用双向链表可以方便地沿向前或向后两个方向查找。方向查找。 (1)

32、(1)插入结点：插入结点：在在p指针所指的结点后插入一个结点指针所指的结点后插入一个结点q，只需，只需要修改要修改p,q结点的结点的prior和和next域即可。域即可。(图与步骤见教材图与步骤见教材P37) (2)(2)删除删除结点：结点：删除删除P指针所指结点，只需修改指针所指结点，只需修改P指针的前驱指针的前驱和后继结点的和后继结点的next，prior域即可。域即可。 (图与步骤见教材图与步骤见教材P38) 4.3 栈和队列栈和队列 4.3.1 栈栈 1.1.栈的定义栈的定义定义：定义：只允许在线性表的一端进行插入和删除的线性表。只允许在线性表的一端进行插入和删除的线性表。 相关术语：

33、相关术语： (1)栈顶：允许插入与删除的一端称为栈顶。栈顶：允许插入与删除的一端称为栈顶。 指针指针toptop指向栈顶位置。指向栈顶位置。 (2)栈底：不允许插入与删除的一端称为栈顶。栈底：不允许插入与删除的一端称为栈顶。 指针指针basebase指向栈底。指向栈底。 (3)入栈：栈的插入操作入栈：栈的插入操作(往栈中插入一个元素往栈中插入一个元素) (4)出栈：栈的删除操作出栈：栈的删除操作(从栈中删除一个元素从栈中删除一个元素) (5)栈空：栈空： top=basetop=base (6)栈满：栈满： top=top=m(mm(m为栈最大容量为栈最大容量) )栈示意图：栈示意图：原则：原

34、则：先进后出或先进后出或后进先出后进先出 栈顶元素总是最后入栈，而最先出栈的栈顶元素总是最后入栈，而最先出栈的栈底元素总是最先入栈，而最后出栈的栈底元素总是最先入栈，而最后出栈的2.2.顺序栈及其运算顺序栈及其运算栈的两种存储结构栈的两种存储结构顺序存储结构：利用一组地址连续的存储单元依次存放顺序存储结构：利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素自栈底到栈顶的数据元素链式存储结构：也称可利用栈。用于收集计算机存储器链式存储结构：也称可利用栈。用于收集计算机存储器中所有空闲存储空间。中所有空闲存储空间。顺序栈：顺序存储结构的栈称为顺序栈。顺序栈：顺序存储结构的栈称为顺序栈。链栈：

35、链式存储结构栈称为链栈。链栈：链式存储结构栈称为链栈。基本运算：基本运算：入栈、退栈与读栈顶元素入栈、退栈与读栈顶元素(1)(1)入栈入栈步骤：步骤：栈顶指针栈顶指针top加加1新元素插入到栈顶指针指向位置新元素插入到栈顶指针指向位置栈顶指针指向栈顶指针指向存储空间最后存储空间最后一个位置时，一个位置时，栈已满，不能栈已满，不能再入栈。称为再入栈。称为栈栈“上溢上溢”错错误误(2)(2)出栈出栈步骤：步骤：栈顶元素赋给一个指定的变量栈顶元素赋给一个指定的变量栈顶指针栈顶指针top减减1栈顶指针为栈顶指针为0时时,栈空栈空,不能再退栈。称为栈不能再退栈。称为栈“下溢下溢”错错误误(3)(3)读栈

36、顶元素读栈顶元素概念：概念：将栈顶元素赋给一个指定变量将栈顶元素赋给一个指定变量注意：注意：不删除栈顶元素，栈顶指针不会改变不删除栈顶元素，栈顶指针不会改变举例举例topbottomABCDEF 10987654321S(1:10)有有6个元素的栈个元素的栈ABCDEFXYS(1:10)topbottom插入插入X和和Y后的栈后的栈 10987654321bottomABCDEFX 10987654321S(1:10)top退出一个元素后的栈退出一个元素后的栈4.3.2 队列队列 定义：定义：指允许在一端插入指允许在一端插入,而在另一端进行删除的线性表。而在另一端进行删除的线性表。 相关术语相

37、关术语(5(5个个) )： (1)队尾：允许插入的一端称为队尾。队尾：允许插入的一端称为队尾。rear队尾指针，始终队尾指针，始终 指向队尾元素的下一个位置。指向队尾元素的下一个位置。 (2)队头：允许进行删除的一端称为队头。队头：允许进行删除的一端称为队头。front队头指针，队头指针，始终指向队头元素。始终指向队头元素。 (3)入队列：队列插入操作入队列：队列插入操作(进队列进队列) (4)出队列：队列的删除操作出队列：队列的删除操作(退队列退队列) (5)空队列：队列中无数据元素空队列：队列中无数据元素原则：原则：先进先出先进先出队头元素总是最先进队列的队头元素总是最先进队列的,也总是最

38、先出队列也总是最先出队列队尾元素总是最后进队列队尾元素总是最后进队列,也是最后出队列也是最后出队列队列结构示意图：队列结构示意图：队列队列Q=(a1，a2, , an )a1aia2an队头队头队尾队尾退队退队入队入队1.1.链队列链队列定义：定义：用链表表示的队列。用链表表示的队列。P41空队列时，头指针空队列时，头指针front和尾指针和尾指针rear同时指向头结点同时指向头结点 新元素入队时插在头结点之后新元素入队时插在头结点之后,修改修改rear指针指针删除一个元素时删除一个元素时,修改修改front指针。删除唯一元素时指针。删除唯一元素时front与与rear回缩到头结点。回缩到头结

39、点。front rear2.2.顺序队列顺序队列定义：定义：队列的顺序存储结构称为顺序队列，利用一组地队列的顺序存储结构称为顺序队列，利用一组地址连续的存储单元依次存放队列中的数据元素。址连续的存储单元依次存放队列中的数据元素。约定：约定：初始化队列令初始化队列令front=rear=0队尾插入新元素，队尾插入新元素，rear加加1队头元素出队列，队头元素出队列，front加加1举例：举例：顺序队列头尾指针变化情况顺序队列头尾指针变化情况543210空队空队 rearfront a1 a2 a3543210frontrear a3543210frontrear a3 a4 a5 a654321

40、0frontrear缺点：缺点：如上例如上例, , 队列最大存储空间为队列最大存储空间为6，队满时再继续插入元，队满时再继续插入元素就会上溢。队尾指针已达到数组上界，不能在增大。而当素就会上溢。队尾指针已达到数组上界，不能在增大。而当前队列可用空间并未占满，前队列可用空间并未占满，“假满假满”现象。现象。 3.3.循环队列循环队列引入：引入：为解决顺序队列为解决顺序队列“假满假满”而采取的方法。而采取的方法。定义：定义：将队列存储空间的最后一个位置饶到第一个位置，将队列存储空间的最后一个位置饶到第一个位置，相成逻辑上的环形空间。相成逻辑上的环形空间。判定条件：判定条件：队空：队空：rear=front队满：队满：方法方法1:rear=front, ,设一个标志变量设一个标志变量S=S=0 队空队空1 队满队满约定循环数组中元素个数达到约定循环数组中元素个数达到M-1队满队满头指针在尾指针下一位置上头指针在尾指针下一位置上方法方法2:少一个元素空间少一个元素空间循环队列示意图：循环队列示意图：02134567front rear队空队空02134567一般情况一般情况a1a2frontrear02134567队满队满(少一个元素少一个元素)a1a2frontreara3a4a5a6a7