《数据结构严蔚敏(完整版)》由会员分享，可在线阅读，更多相关《数据结构严蔚敏(完整版)（814页珍藏版）》请在人人文库网上搜索。
1、算法与数据结构,教材：数据结构(C语言版)。严蔚敏，吴伟民 编 著。清华大学出版社。 参考文献： 1 数据结构 。张选平，雷咏梅 编， 严蔚敏 审。 机械工业出版社。 2 数据结构与算法分析。Clifford A. Shaffer著， 张 铭，刘晓丹 译。电子工业出版社。 3 数据结构习题与解析(C语实言版)。李春葆。 清华大学出版社。 4 数据结构与算法。夏克俭
编著。国防工业出版社。,第1章 绪 论,目前，计算机已深入到社会生活的各个领域，其应用已不再仅仅局限于科学计算，而更多的是用于控制，管理及数据处理等非数值计算领域。计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问
2、题：信息的表示，信息的处理。 信息的表示和组织又直接关系到处理信息的程序的效率。随着应用问题的不断复杂，导致信息量剧增与信息范围的拓宽，使许多系统程序和应用程序的规模很大，结构又相当复杂。因此，必须分析待处理问题中的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。,编写解决实际问题的程序的一般过程： 如何用数据形式描述问题?即由问题抽象出一个适当的数学模型;
问题所涉及的数据量大小及数据之间的关系; 如何在计算机中存储数据及体现数据之间的关系? 处理问题时需要对数据作何种运算? 所编写的程序的性能是否良好? 上面所列举的问题基本上由数据结构这门课程来回答。,计算机求解问题
3、的一般步骤,1.1 数据结构及其概念,算法与数据结构是计算机科学中的一门综合性专业基础课。是介于数学、计算机硬件、计算机软件三者之间的一门核心课程，不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。,1.1.1 数据结构的例子,例1：电话号码查询系统
设有一个电话号码薄，它记录了N个人的名字和其相应的电话号码，假定按如下形式安排：(a1, b1)，(a2, b2)，(an, bn)，其中ai, bi(i=1，2n) 分别表示某人的名字和电话号码。 本问题是一种典型的表格问题。如表1-1，数据与数据成简单的一对一的线性关系。,表1-1
4、 线性表结构,例2：磁盘目录文件系统 磁盘根目录下有很多子目录及文件，每个子目录里又可以包含多个子目录及文件，但每个子目录只有一个父目录，依此类推： 本问题是一种典型的树型结构问题，如图1-1 ，数据与数据成一对多的关系，是一种典型的非线性关系结构树形结构。,图1-1 树形结构,例3：交通网络图
从一个地方到另外一个地方可以有多条路径。本问题是一种典型的网状结构问题，数据与数据成多对多的关系，是一种非线性关系结构。,数据(Data) ：是客观事物的符号表示。在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素(Data Element) ：是数据的基本单位，在程序
5、中通常作为一个整体来进行考虑和处理。 一个数据元素可由若干个数据项(Data Item)组成。数据项是数据的不可分割的最小单位。数据项是对客观事物某一方面特性的数据描述。 数据对象(Data Object)：是性质相同的数据元素的集合，是数据的一个子集。如字符集合C=A,B,C, 。,1.1.2 基本概念和术语,数据结构(Data
Structure)：是指相互之间具有(存在)一定联系(关系)的数据元素的集合。元素之间的相互联系(关系)称为逻辑结构。数据元素之间的逻辑结构有四种基本类型，如图1-3所示。 集合：结构中的数据元素除了“同属于一个集合”外，没有其它关系。 线性结构：结构中的数据元素
6、之间存在一对一的关系。 树型结构：结构中的数据元素之间存在一对多的关系。 图状结构或网状结构：结构中的数据元素之间存在多对多的关系。,数据结构的形式定义是一个二元组： Data-Structure=(D，S) 其中：D是数据元素的有限集，S是D上关系的有限集。 例2：设数据逻辑结构B=（K，R） K=k1, k2, , k9 R= ，
画出这逻辑结构的图示，并确定那些是起点，那些是终点,1.1.3 数据结构的形式定义,图1-3 四类基本结构图,1.1.4 数据结构的存储方式,数据元素之间的关系可以是元素之间代表某种含义的自然关系，也可以是为处理问题方便而人为定义的关系，这种自然或人为定义的 “
7、关系”称为数据元素之间的逻辑关系，相应的结构称为逻辑结构。,数据结构在计算机内存中的存储包括数据元素的存储和元素之间的关系的表示。 元素之间的关系在计算机中有两种不同的表示方法：顺序表示和非顺序表示。由此得出两种不同的存储结构：顺序存储结构和链式存储结构。
顺序存储结构：用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构(关系)。,链式存储结构：在每一个数据元素中增加一个存放另一个元素地址的指针(pointer )，用该指针来表示数据元素之间的逻辑结构(关系)。 例：设有数据集合A=3.0,2.3,5.0,-8.5,11.0 ，两种不同的存储结构。 顺序结构：数据元素存放的地址是连续的
8、； 链式结构：数据元素存放的地址是否连续没有要求。 数据的逻辑结构和物理结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。 在C语言中，用一维数组表示顺序存储结构；用结构体类型表示链式存储结构。,数据结构的三个组成部分： 逻辑结构： 数据元素之间逻辑关系的描述 D_S=（D，S） 存储结构：
数据元素在计算机中的存储及其逻辑关系的表现称为数据的存储结构或物理结构。 数据操作： 对数据要进行的运算。 本课程中将要讨论的三种逻辑结构及其采用的存储结构如图1-4所示。,数据类型(Data Type)：指的是一个值的集合和定义在该值集上的一组操作的总称
9、。 数据类型是和数据结构密切相关的一个概念。 在C语言中数据类型有：基本类型和构造类型。 数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。,1.1.5 数据类型,数据结构的主要运算包括： 建立(Create)一个数据结构； 消除(Destroy)一个数据结构； 从一个数据结构中删除(Delete)一个数据元素；
把一个数据元素插入(Insert)到一个数据结构中； 对一个数据结构进行访问(Access)； 对一个数据结构(中的数据元素)进行修改(Modify)； 对一个数据结构进行排序(Sort)； 对一个数据结构进行查找(Se
10、arch)。,1.1.6 数据结构的运算,抽象数据类型(Abstract Data Type ，简称ADT)：是指一个数学模型以及定义在该模型上的一组操作。 ADT的定义仅是一组逻辑特性描述， 与其在计算机内的表示和实现无关。因此，不论ADT的内部结构如何变化，只要其数学特性不变，都不影响其外部使用。 ADT的形式化定义是三元组：ADT=(D，S，P)
其中：D是数据对象，S是D上的关系集，P是对D的基本操作集。,1.2 抽象数据类型,ADT的一般定义形式是： ADT 数据对象： 数据关系： 基本操作： ADT 其中数据对象和数据关系的定义用伪码描述。 基本操作的定义是： () 初始条件： 操
11、作结果： ,初始条件：描述操作执行之前数据结构和参数应满足的条件;若不满足，则操作失败，返回相应的出错信息。 操作结果：描述操作正常完成之后，数据结构的变化状况和 应返回的结果。,1.3.1 算法 算法(Algorithm)：是对特定问题求解方法(步骤)的一种描述，是指令的有限序列，其中每一条指令表示一个或多个操作。 算法具有以下五个特性 有穷性：
一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 确定性：算法中每一条指令必须有确切的含义。不存在二义性。且算法只有一个入口和一个出口。 可行性： 一个算法是能行的。即算法描述的操作都可以通过已经实现的基本运算执行有限次来实现。,
12、1.3 算法分析初步, 输入： 一个算法有零个或多个输入，这些输入取自于某个特定的对象集合。 输出： 一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。 一个算法可以用多种方法描述，主要有：使用自然语言描述；使用形式语言描述；使用计算机程序设计语言描述。
算法和程序是两个不同的概念。一个计算机程序是对一个算法使用某种程序设计语言的具体实现。算法必须可终止意味着不是所有的计算机程序都是算法。 在本门课程的学习、作业练习、上机实践等环节，算法都用C语言来描述。在上机实践时，为了检查算法是否正确，应编写成完整的C语言程序。,评价一个好的算法有以下几个标准 正确性(Correctness
13、 )： 算法应满足具体问题的需求。 可读性(Readability)： 算法应容易供人阅读和交流。可读性好的算法有助于对算法的理解和修改。 健壮性(Robustness)： 算法应具有容错处理。当输入非法或错误数据时，算法应能适当地作出反应或进行处理，而不会产生莫名其妙的输出结果。 通用性(Generality)： 算法应具有一般性
，即算法的处理结果对于一般的数据集合都成立。,1.3.2 算法设计的要求,算法执行时间需通过依据该算法编制的程序在计算机上运行所消耗的时间来度量。其方法通常有两种： 事后统计：计算机内部进行执行时间和实际占用空间的统计。 问题：必须先运行依据算法编制的程序；依赖软
14、硬件环境，容易掩盖算法本身的优劣；没有实际价值。 事前分析：求出该算法的一个时间界限函数。,1.3.3 算法效率的度量, 效率与存储量需求： 效率指的是算法执行的时间；存储量需求指算法执行过程中所需要的最大存储空间。一般地，这两者与问题的规模有关。,与此相关的因素有： 依据算法选用何种策略； 问题的规模； 程序设计的语言； 编译程序所产生的机器代码的质量； 机器执行指令的速度；
撇开软硬件等有关部门因素，可以认为一个特定算法“运行工作量”的大小，只依赖于问题的规模（通常用n表示），或者说，它是问题规模的函数。,算法分析应用举例,算法中基本操作重复执行的次数是问题规模n的某个函数，其时间量度记作
15、 T(n)=O(f(n)，称作算法的渐近时间复杂度(Asymptotic Time complexity)，简称时间复杂度。 一般地，常用最深层循环内的语句中的原操作的执行频度(重复执行的次数)来表示。 “O”的定义： 若f(n)是正整数n的一个函数，则 O(f(n)表示 M0 ，使得当n n0时，| f(n) | M | f(n0) | 。 表示时间复杂度的阶有： O(1)
时间复杂度为O(n2)，即此算法的时间复杂度为平方阶。 一个算法时间为O(1)的算法，它的基本运算执行的次数是固定的。因此，总的时间由一个常数（即零次多项式）来限界。而一个时间为O(n2)的算法则由一个二次多项式来限界。,以下六种计算算
18、法时间的多项式是最常用的。其关系为： O(1)O(n)O(n)O(nn)O(n2)O(n3) 指数时间的关系为： O(2n)O(n!)O(nn) 当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。因此，只要有人能将现有指数时间算法中的任何一个算法化简为多项式时间算法，那就取得了一个伟大的成就。
指令常数变量所占用的存储空间; 输入数据所占用的存储空间; 辅助(存储)空间。 一般地，算法的空间复杂度指的是辅助空间。 一维数组an： 空间复杂度 O(n) 二维数组anm： 空间复杂度 O(n*m),习 题 一,1
20、简要回答术语：数据，数据元素，数据结构，数据类型。 2 数据的逻辑结构？数据的物理结构？逻辑结构与物理结构的区别和联系是什么？ 3 数据结构的主要运算包括哪些？ 4 算法分析的目的是什么？算法分析的主要方面是什么？ 5 分析以下程序段的时间复杂度，请说明分析的理由或原因。,第2章
线性表,线性结构是最常用、最简单的一种数据结构。而线性表是一种典型的线性结构。其基本特点是线性表中的数据元素是有序且是有限的。在这种结构中： 存在一个唯一的被称为“第一个”的数据元素； 存在一个唯一的被称为“最后一个”的数据元素； 除第一个元素外，每个元素均有唯一一个直接前驱； 除最后一个元素外，每个元素均有唯一一个
21、直接后继。,2.1 线性表的逻辑结构,线性表(Linear List) ：是由n(n0)个数据元素(结点)a1，a2， an组成的有限序列。该序列中的所有结点具有相同的数据类型。其中数据元素的个数n称为线性表的长度。 当n=0时，称为空表。 当n0时，将非空的线性表记作： (a1，a2，an) a1称为线性表的第一个(首)结点，an称为线性表的最后一个(尾)结点。,2.1.1
22、数据元素ai所代表的具体含义随具体应用的不同而不同，在线性表的定义中，只不过是一个抽象的表示符号。 线性表中的结点可以是单值元素(每个元素只有一个数据项) 。 例1: 26个英文字母组成的字母表： (A，B，C、Z）,例2 ： 某校从1978年到1983年各种型号的计算机拥有量的变化情况：(6，17，28，50，92，188） 例3 ： 一副扑克的点数
(2，3，4，J，Q，K，A) 线性表中的结点可以是记录型元素，每个元素含有多个数据项 ，每个项称为结点的一个域 。每个元素有一个可以唯一标识每个结点的数据项组，称为关键字。 例4 ： 某校2001级同学的基本情况：(，张里
数据关系：R = | ai-1, aiD, i=2,3,n 基本操作： InitList( 数据元素之间的关系是以元素在计算机内“物理位置相邻”来体现。 设有非空的线性表：(a1，a2，an) 。顺序存储如图2-1所示。,2
24、.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,在高级语言(如C语言)环境下：数组具有随机存取的特性，因此，借助数组来描述顺序表。除了用数组来存储线性表的元素之外，顺序表还应该有表示线性表的长度属性，所以用结构类型来定义顺序表类型。 #define OK 1
顺序表的基本操作,顺序存储结构中，很容易实现线性表的一些操作：初始化、赋值、查找、修改、插入、删除、求长度等。 以下将对几种主要的操作进行讨论。 1 顺序线性表初始化 Status Init_SqList( SqList *L ) L-elem_array=( ElemTyp
28、入新结点，其时间主要耗费在表中结点的移动操作上，因此，可用结点的移动来估计算法的时间复杂度。 设在线性表L中的第i个元素之前插入结点的概率为Pi，不失一般性，设各个位置插入是等概率，则Pi=1/(n+1)，而插入时移动结点的次数为n-i+1。 总的平均移动次数： Einsert=pi*(n-i+1) (1in) Einsert=n/2 。
即在顺序表上做插入运算，平均要移动表上一半结点。当表长n较大时，算法的效率相当低。因此算法的平均时间复杂度为O(n)。,3 顺序线性表的删除 在线性表 L=(a1，a i-1，ai， ai+1，an) 中删除结点ai(1in)，使其成为线性表： L= (a1
设在线性表L中删除第i个元素的概率为Pi，不失一般性，设删除各个位置是等概率，则Pi=1/n，而删除时移动结点的次数为n-i。 则总的平均移动次数： Edelete=pi*(n-i) (1in) Edelete=(n-1)/2 。 即在顺序表上做删除运算，平均要移动表上一半结点。当表长n较大时，算法的效率相
31、当低。因此算法的平均时间复杂度为O(n)。,4 顺序线性表的查找定位删除 在线性表 L= (a1，a2，an) 中删除值为x的第一个结点。 实现步骤 (1) 在线性表L查找值为x的第一个数据元素。 (2) 将从找到的位置至最后一个结点依次向前移动一个位置。 (3) 线性表长度减1。 算法描述 Status Locate_Delete_SqList(Sqlist
首先，在线性表L中查找值为x的结点是否存在; 其次，若值为x的结点存在，且在线性表L中的位置为i ，则在线性表L中删除第i个元素。 设在线性表L删除数据元素概率为Pi，不失一般性，设各个位置是等概率，则Pi=1/n。 比较的平均次数： Ecompare=
存储链表中结点的一组任意的存储单元可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。 链表中结点的逻辑顺序和物理顺序不一定相同。,为了正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储
34、指示其直接后继结点的地址(或位置)，称为指针(pointer)或链(link)，这两部分组成了链表中的结点结构，如图2-2所示。 链表是通过每个结点的指针域将线性表的n个结点按其逻辑次序链接在一起的。 每一个结只包含一个指针域的链表，称为单链表。
为操作方便，总是在链表的第一个结点之前附设一个头结点(头指针)head指向第一个结点。头结点的数据域可以不存储任何信息(或链表长度等信息)。,单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。 例1、线性表L=(bat，cat，eat，fat，hat) 其带头结点的单链表的逻辑状态和物理存储方式如图2-3所示。,1 结点的描述与实现 C语言
假设线性表中结点的数据类型是整型，以32767作为结束标志。动态地建立单链表的常用方法有如下两种：头插入法，尾插入法。 头插入法建表 从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到
38、); (2) 尾插入法建表 头插入法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾，使其成为当前链表的尾结点。,算法描述 LNode *create_LinkList(void) /* 尾插入法创建单链表,链表的头结点head作为返回值 */ int data ; LNode *head,
39、建的结点总是作为最后一个结点*/ return (head); 无论是哪种插入方法，如果要插入建立的单线性链表的结点是n个，算法的时间复杂度均为O(n)。 对于单链表，无论是哪种操作，只要涉及到钩链(或重新钩链)，如果没有明确给出直接后继，钩链(或重新钩链)的次序必须是“先右后左”。,2 单链表的查找 (1) 按序号查找 取单链表中的第i个元素。
对于单链表，不能象顺序表中那样直接按序号i访问结点，而只能从链表的头结点出发，沿链域next逐个结点往下搜索，直到搜索到第i个结点为止。因此，链表不是随机存取结构。 设单链表的长度为n，要查找表中第i个结点，仅当1in时，i的值是合法的。,算法描述
若有，则返回首次找到的值为key的结点的存储位置；否则返回NULL。查找时从开始结点出发，沿链表逐个将结点的值和给定值key作比较。,算法描述 LNode *Locate_Node(LNode *L，int key) /* 在以L为头结点的单链表中查找值为ke
41、y的第一个结点 */ LNode *p=Lnext; while ( p!=NULL 算法的执行与形参key有关，平均时间复杂度为O(n)。,3 单链表的插入 插入运算是将值为e的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，必须首先找到ai-1所在的结点p，然后生成一个数据域为e的新结点q，q结点作为p的直接后继结点。 算法描述 void
为了删除第i个结点ai，必须找到结点的存储地址。该存储地址是在其直接前趋结点ai-1的next域中，因此，必须首先找到ai-1的存储位置p，然后令pnext指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间，
43、将其归还给“存储池”。 设单链表长度为n，则删去第i个结点仅当1in时是合法的。则当i=n+1时，虽然被删结点不存在，但其前趋结点却存在，是终端结点。故判断条件之一是pnext!=NULL。显然此算法的时间复杂度也是O(n)。,算法描述 void Delete_LinkList(LNode *L， int i) /* 删除以L为头结点的单链表中的第i个结点 */ int j=1;
从上面的讨论可以看出，链表上实现插入和删除运算，无需移动结点，仅需修改指针。解决了顺序表的插入或删除操作需要移动大量元素的问题。 变形之一： 删除单链表中值为key的所有结点。 与按值查找相类似，但比前面的算法更简单。 基本思想：从单链表的第一个结点开始，对每个结点进行检查，若结点的值为k
q=p-next; else p=q; q=qnext; ,变形之二： 删除单链表中所有值重复的结点，使得所有结点的值都不相同。 与按值查找相类似，但比前面的算法更复杂。 基本思想：从单链表的第一个结点开始，对每个结点进行检
47、; else q=ptr; ptr=ptrnext; ,p=p-next ; ,5 单链表的合并 设有两个有序的单链表，它们的头指针分别是La 、 Lb，将它们合并为以Lc为头指针的有序链表。合并前的示意图如图2-4所示。,合并了值为-7，-2的结点后示意图如图2-5所示。,算法说明 算法中pa
49、表的长度分别是m，n，则链表合并的时间复杂度为O(m+n) 。,2.3.3 循环链表,循环链表(Circular Linked List)：是一种头尾相接的链表。其特点是最后一个结点的指针域指向链表的头结点，整个链表的指针域链接成一个环。 从循环链表的任意一个结点出发都可以找到链表中的其它结点，使得表处理更加方便灵活。 图2-6是带头结点的单循环链表的示意图。,空表,循环链表的操作
对于单循环链表，除链表的合并外，其它的操作和单线性链表基本上一致，仅仅需要在单线性链表操作算法基础上作以下简单修改： 判断是否是空链表：head-next=head ; 判断是否是表尾结点：p-next=head
50、;,2.4 双向链表,双向链表(Double Linked List) :指的是构成链表的每个结点中设立两个指针域：一个指向其直接前趋的指针域prior，一个指向其直接后继的指针域next。这样形成的链表中有两个方向不同的链，故称为双向链表。 和单链表类似，双向链表一般增加头指针也能使双链表上的某些运算变得方便。 将头结点和尾结点链接起来也能构成循环链表，并称之为双向循环链表。
双向链表是为了克服单链表的单向性的缺陷而引入的。,1 双向链表的结点及其类型定义 双向链表的结点的类型定义如下。其结点形式如图2-7所示，带头结点的双向链表的形式如图2-8所示。 typedef struct Duln
结点p的存储位置存放在其直接前趋结点p-prior的直接后继指针域中，同时也存放在其直接后继结点p-next的直接前趋指针域中。 2 双向链表的基本操作 (1) 双向链表的插入 将值为e的结点插入双向链表中。插入前后链表的变化如图2-9所示。, 插入时仅仅指出直接前驱结点，钩链时必须注意先后次序是： “先右后左” 。部分语句组
53、，再释放结点。部分语句组如下： p-prior-next=p-next; p-next-prior=p-prior; free(p); 注意： 与单链表的插入和删除操作不同的是，在双向链表中插入和删除必须同时修改两个方向上的指针域的指向。,2.5 一元多项式的表示和相加,1 一元多项式的表示 一元多项式 p(x)=p0+p1x+p2x2+ +pnxn
，由n+1个系数唯一确定。则在计算机中可用线性表(p0 ，p1 ，p2 ， ，pn )表示。既然是线性表，就可以用顺序表和链表来实现。两种不同实现方式的元素类型定义如下：,(1) 顺序存储表示的类型 typedef struct float co
当采用链式存储表示时，根据结点类型定义，凡是系数为0的项不在链表中出现，从而可以大大减少链表的长度。,一元多项式相加的实质是： 指数不同： 是链表的合并。 指数相同： 系数相加，和为0，去掉结点，和不为0，修改结点的系数域。 算法之一： 就在原来两个多项式链表的基础上进行相加，相加后原来两个多项式链表就不在存在。当然再
return (Lc) ; ,算法之二： 对两个多项式链表进行相加，生成一个新的相加后的结果多项式链表，原来两个多项式链表依然存在，不发生任何改变，如果要再对原来两个多项式进行其它操作也不影响。,算法描述 Ploy *ad
简述下列术语：线性表，顺序表，链表。 2 何时选用顺序表，何时选用链表作为线性表的存储结构合适?各自的主要优缺点是什么? 3 在顺序表中插入和删除一个结点平均需要移动多少个结点?具体的移动次数取决于哪两个因素? 4 链表所表示
62、的元素是否有序?如有序，则有序性体现于何处?链表所表示的元素是否一定要在物理上是相邻的?有序表的有序性又如何理解? 5 设顺序表L是递增有序表，试写一算法，将x插入到L中并使L仍是递增有序表。,6 写一求单链表的结点数目ListLength(L)的算法。 7 写一算法将单链表中值重复的结点删除，使所得的结果链表中所有结点的值均不相同。 8
写一算法从一给定的向量A删除值在x到y(xy)之间的所有元素(注意：x和y是给定的参数，可以和表中的元素相同，也可以不同)。 9 设A和B是两个按元素值递增有序的单链表，写一算法将A和B归并为按按元素值递减有序的单链表C，试分析算法的时间复杂度。,第3章 栈
63、和队列,栈和队列是两种应用非常广泛的数据结构，它们都来自线性表数据结构，都是“操作受限”的线性表。 栈在计算机的实现有多种方式： 硬堆栈：利用CPU中的某些寄存器组或类似的硬件或使用内存的特殊区域来实现。这类堆栈容量有限，但速度很快； 软堆栈：这类堆栈主要在内存中实现。堆栈容量可以达到很大。在实现方式上，又有动态方式和静态方式两种。
本章将讨论栈和队列的基本概念、存储结构、基本操作以及这些操作的具体实现。,3.1 栈,3.1.1 栈的基本概念,1 栈的概念 栈(Stack)：是限制在表的一端进行插入和删除操作的线性表。又称为后进先出LIFO (Last In First Out)或先进后出FI
64、LO (First In Last Out)线性表。 栈顶(Top)：允许进行插入、删除操作的一端，又称为表尾。用栈顶指针(top)来指示栈顶元素。 栈底(Bottom)：是固定端，又称为表头。 空栈：当表中没有元素时称为空栈。,设栈S=(a1，a2，an)，则a1称为栈底元素，an为栈顶元素，如图3-1所示。
栈中元素按a1，a2，an的次序进栈，退栈的第一个元素应为栈顶元素。即栈的修改是按后进先出的原则进行的。,2 栈的抽象数据类型定义 ADT Stack 数据对象：D = ai|aiElemSet, i=1,2,n，n0 数据关系：R =|ai-1，aiD, i=2,3,n 基本操作：初
65、始化、进栈、出栈、取栈顶元素等 ADT Stack,栈的顺序存储结构简称为顺序栈，和线性表相类似，用一维数组来存储栈。根据数组是否可以根据需要增大，又可分为静态顺序栈和动态顺序栈。 静态顺序栈实现简单，但不能根据需要增大栈的存储空间； 动态顺序栈可以根据需要增大栈的存储空间，但实现稍为复杂。,3.1.2
栈的顺序存储表示,采用动态一维数组来存储栈。所谓动态，指的是栈的大小可以根据需要增加。 用bottom表示栈底指针，栈底固定不变的；栈顶则随着进栈和退栈操作而变化。用top(称为栈顶指针)指示当前栈顶位置。 用top=bottom作为栈空的标记，每次top指向栈顶数组中的下一个存储位置。 结点进栈：首先将数据元素保存到栈顶(
