数据结构实用教程讲课教案.pdf

《数据结构实用教程讲课教案.pdf》由会员分享，可在线阅读，更多相关《数据结构实用教程讲课教案.pdf（84页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、这次由本人主讲的数据结构（本科）IP课程共分为10讲，每讲大致为50分钟。第一讲数据结构概述第二讲集合与线性表第三讲栈和队列第四讲二叉树第五讲二叉搜索树和堆第六讲平衡二叉树第七讲图的概念和存储结构第八讲二分查找和散列查找第九讲选择排序第十讲 快速排序和归并排序第一讲数据结构概述一、数据结构的分类二、数据结构的定义三、数据结构的图形表示四、数据结构的二元组表示五、数据结构的应用实例六、算法的时间复杂度一、数据结构的分类数据结构又分为数据的逻辑结构和数据的存储结构这两个方面，我们时常把数据的逻辑结构简称为数据结构，而在讨论数据的存储结构时则必须指明是数据的存储结构。数据结构的分类：这里是指数据的逻

2、辑结构的分类。总体来说数据的逻辑结构被分为集合结构、线性结构、树结构和图结构等四种基本类型。对于一些复杂的数据结构可以由这四种基本的数据结构，根据实际需要进行组合或嵌套所构成。数据的存储结构分类：被分为顺序、链接、索引和散列四种，由它们的组合和嵌套可以构成更复杂的存储结构。广义的数据结构的概念还包含对数据进行的各种运算，通常有插入、删除、查找、更新、排序、遍历等运算.二、数据结构的定义1、集合结构集合结构是指数据中各元素之间没有任何次序。如一个容器中的所有乒乓球，一个俱乐部里的所有成员，可以认为它们之间没有任何次序，它们均为集合结构。2、线性结构线性结构是指数据中各元素之间具有1对 1 的先后

3、次序关系。如在一个列车时刻表中，各车次记录之间是按照发车时间的先后次序排列的；在一个人事职工表中，各职工记录之间是按照职工编号的先后次序排列的。所以，它们的表结构都是线性结构。3、树结构树结构是指数据中各元素之间具有1对多的先后次序关系，并且只有一个元素称为树根结点，其余均为树枝结点和树叶结点。如在一个企业的组织机构中，总经理只有一个，相当于是树根；它下属多个部门，每个部门又各有一个部门经理，相当于是树枝；每个部门又有多名员工，属于部门经理领导，相当于是树叶。所以，企业的组织结构是一个树结构。4、图结构图结构是指数据中各元素之间具有多对多的关系。这是数据结构中最复杂的结构。如在一个城市交通图中

4、，所有道路连接成一个复杂的图结构，交叉路口就是图中的顶点，每条道路就是图中的边，从一个交叉路口可以到达与其连接的其他交叉路口。三、数据结构的图形表示各种数据结构类型的图形表示如下:(b)线性结构(d)图结构从图形表示中可以清醒地看出：集合结构中的元素是各自独立的，元素之间没有联系.线性结构中的元素是一个接一个串联起来的，它有一个头元素A和一个尾元素G,其余为中间元素；每个中间元素既有前驱元素，又有后继元素，如B的前驱元素为A,后继元素为C;C的前驱元素为B,后继元素为D,，头元素A没有前驱元素，只有后继元素B;尾元素G只有前驱元素F,没有后继元素。树结构的图形表示象倒着画的一棵树，树中有一个树

5、根元素A,它 有3个后继元素，又称为A的孩子结点B、C和D,C结点有两个孩子E和F,D结点有一个孩子G,由于B、E、F、G没有孩子，所以称它们为叶子结点，而A、C、D被称为树枝结点或分支结点，同时A又是唯一的一个树根结点。在树结构中，树根结点只有后继结点，而没有前驱结点；如A为树根结点，它没有前驱结点，或者说其前驱结点为空，它有后继结点为B、C和D;除树根结点外，每个结点都有唯一一个前驱结点，又称为是父结点或双亲结点；如C的前驱结点为A,G的前驱结点为D,每个结点的前驱结点即双亲结点，从图形中都能够很容易得到。在图结构中，每个结点或称顶点都可以有任意多个前驱结点和任意多个后继结点.如(d)图所

6、示的图中，顶 点A没有前驱结点，或者说它有0个前驱结点，A有3个后继结点B、C和G;G有2个前驱结点A和D,有一个后继结点F;E有一个前驱结点C和0个后继结点，或者说，E没有后继，对于图形中的其他结点都能够很容易得到其前驱和后继结点。从数据结构的图形表示中还可以清楚地看出：树结构是图结构的特例，若在图结构中，每个结点的前驱不能有任意多个，而只能有一个，并且只能有一个结点没有前驱，则就成为了树结构；线性结构是树结构的特例，若在树结构中，每个结点不能有任意多个后继，而只能有一个后继，则就成为了线性结构。为了区别于线性结构，时常把树结构和图结构称为非线性结构。四、数据结构的二元组表示数据结构的二元组

7、表示采用B=(K,R)的形式，其中第一元K给出数据结构中所有元素的集合，第二元R给出数据结构中所有元素具有的二元关系的集合，通常对每个二元关系分别进行讨论，所以直接用R表示这一种二元关系，该二元关系是有序对的集合，又称是序偶的集合，每个有序对(即序偶)是用一对尖括号括起来的、具有前驱和后继关系的两个元素.对于前面图形中给出的四种数据结构，下面分别讨论它们的二元组表示。集合结构中的元素集合K和二元关系R分别为：K=A,B,C,D,E,F,G)R=)因为集合中的元素为孤立顶点，它们之间没有前驱和后继的关系，所以对应的二元关系为空。线性结构中的元素集合K和二元关系R分别为：K=A,B,C,D,E,F

8、,G R=,因为A和B构成一对前驱和后继关系，对应图形中的一条有向边，它的起点为A,终点为B,它就构成了 R中的一个有序对，同理，B和C、C和D等都是R中的有序对。由于该线性结构包含有7个元素，所以二元关系R中共含有6个有序对。树结构中的元素集合K和二元关系R分别为：K=A,B,C,D,E,F,G R=,因为A和B构成一对前驱和后继关系，所以它是R中的一个有序对，同理，A和C、A和D等都是R中的有序对。由于该树结构包含有7个元素，所以二元关系R中共含有6个有序对，即每个元素对应唯一一个有序对，并且是有序对中的后继元素，而树根结点没有对应的、作为后继元素的有序对。所以当一棵树具有n个结点时，它必

9、然具有n-1个有序对，对应图形中为n-1条有向边。图结构中的元素集合K和二元关系R分别为：K=A,B,C,D,E,F,G R=,)在线性结构和树结构中，若元素个数为n,则有序对个数必然为n-1;而在图结构中不存在这种对应的关系，也就是说，其有序对的个数又称有向边数可能大于、等于或小于n-1。在这个图结构的例子中，元素个数为7个，边数为8个。五、数据结构应用实例下面为某个公司的职工简表职工号姓名性别出生日期职务部门01万明华男1962-03-20经理02赵 宁男1968-06-14主管销售部03张 利女1964-12-07主管财务部04赵书芳女1972-08-05主任办公室05刘永年男1959-

10、08-15科员销售部06王明理女1975-04-01科员销售部07王 敏女1972-06-28科员财务部0 8张 才男1 9 6 7-0 3-1 7科员财务部0 9马立仁男1 9 7 5-1 0-1 2科员财务部1 0邢怀常男1 9 7 6-0 7-0 5科员办公室该表中包含有10条职工记录，每条记录都由六个数据项所组成，由于每条记录的职工号各不相同，所以可把每条记录的职工号作为该记录的关键字，并在下面的讨论中，用记录的关键字来代表整个记录。对于上面所述的一张表，假定不考虑该表中记录之间的任何次序，则该表中的数据就是一个集合结构，对应的记录集合以及二元关系为：K=01,02,03,04,05,

11、06,07,08,09,10R=)若考虑到该表中的职工记录是按照职工号从小到大有序排列的这个特点，则这个职工表又是一个线性结构，其中表头元素为01号职工，接着为02号职工，依次类推，表尾元素为10号职工。该线性结构包含的记录集合和二元关系为：K=01,02,03,04,05,06,07,08,09,10R=,有时需要按职工的出生日期进行数据结构的定义和处理，则可以把表中的所有职工看作是按照出生日期，从小到大有序的，由此对应的数据结构也是一种线性结构，其 中05号职工的出生日期最早，即年龄最大，为表头元素，01号职工年龄次之，为这种线性结构中的第二个元素，依次类推，10号职工的出生日期最晚，为表

12、尾元素。该线性结构包含的记录集合和二元关系为：K=01,02,03,04,05,06,07,08,09,10R=,)对应的图形表示为：:碱 一 1 03 08 1同 从图形表示中能够清楚地看出每个职工出生日期的先后排列次序。在上面职工表中，还存在职工人员之间领导与被领导的关系，其 中01号职工为经理,直接领导0 2、0 3和0 4号职工，他们分别是相应部门的主管，0 2号职工直接领导0 5和0 6号职工，0 3号职工直接领导07、0 8和0 9号职工，0 4号职工直接领导1 0号职工。由此可知，该职工表是一种树结构，包含的职工集合和二元关系分别为：K=0 1,0 2,0 3,0 4,0 5,0

13、 6,0 7,0 8,0 9,1 0)R=,对应的图形表示为：若要反映职工之间的好友关系，假 定0 1和0 2号职工是好友，0 1和0 4号是好友，0 2和0 3、0 2和0 6、0 2和0 7、0 3和0 7、0 4和0 6、0 5和0 7之间是好友，则反映这种好友关系的数据结构是图结构，二元组中的元素集合和有序对集合分别为：K=0 1,0 2,0 3,0 4,0 5,0 6,0 7,0 8,0 9,1 0 R=,对应的图形表示如下面左图所示，其 中0 8、0 9和1 0号职工无好友，在图形中为孤立顶点，省略未画；图形中每对顶点之间的两条相反的有向边，表示这两个顶点职工是一对好朋友，为了简化

14、起见，两条相反的有向边可以用一条无向边来代替，隐含着该无向边是双向的，即连接的两个顶点互为前驱和后继，则对应的无向图表示如下面右图所示。从上面左图可以看出，R是K上的对称关系，即若存在这个序偶，则必然存在这个序偶与之对应。为了简化起见，我们在二元组表示中把和这两个对称序偶用一个无序对(x,y)或(y,x)来代替，这样R关系可改写为：R=(0 1,0 2),(0 1,0 4),(0 2,0 3),(0 2,0 6),(0 2,0 7),(0 3,0 7),(0 4,0 6),(0 5,0 7)可见R成为了一个无序对的集合，其中的每个元素为用圆括号括起来的一个无序对，对应图形中的一条无向边，由无向

15、边构成的图形称为无向图，反之为有向图。六、算法的时间复杂度算法的时间复杂度是一个算法运行时间的相对量度。一个算法的运行时间是指在计算机上从开始到结束运行所花费的时间长短，它大致等于计算机执行一种简单操作(如赋值、比较、计算、转向、返回、输入、输出等)所需的时间与算法中进行简单操作次数的乘积.因为执行一种简单操作所需的时间随机器而异，它是由机器本身硬软件环境决定的，与算法无关，所以我们只讨论影响运行时间的另一个因素一一算法中进行简单操作次数的多少。不管一个算法是简单还是复杂，最终都是被编译后分解成简单操作再通过C P U 来具体执行的。因此，每个算法都对应着一定的简单操作的次数。显然，在一个算法

16、中，进行简单操作的次数越少，其运行时间也就相对地越短；次数越多，其运行时间也就相对地越长。所以，通常把算法中包含简单操作次数的多少叫做该算法的时间复杂度，或者叫做时间复杂性，用它来衡量一个算法的运行时间性能或称计算性能。若解决一个问题的规模为n,即表示待处理的数据中包含有n 个元素，则算法的时间复杂度通常是n 的一个函数，假定记为f(n)。算法的时间复杂度通常采用数量级的形式表示，所以求一个算法的时间复杂度只要分析清楚算法中主要的循环体内简单操作的执行次数，或递归函数的调用次数即可。例如，对于一个含有n 土 C次循环的算法，其 中 n 表示待处理问题的规模，C是一个常量，n C,则该算法的时间

17、复杂度为0(n);对于一个含有双重循环的算法，循环次数的主体呈现在/数量级上，所以则该算法的时间复杂度为0(/)。算法的时间复杂度通常具有 0(1)、0(V n)、0(n).0(l o g2n),0(n*l o g2n),0(/)、0 35、0(2 )和 0(n!)等形式。其 中 0(1)表示算法的时间复杂度为常量，它不随数据量n 的改变而改变，如访问一个数据表中第一个元素时，无论该表的大小如何，其时间复杂度均为0(1)。0 (新)表示算法的时间复杂度与数据量大小n 的平方根成正比,如计算满足不等式 k nk=l中的最大i 值时，其算法的时间复杂度就是0 ()。具有0(n)数量级的算法被称为具

18、有线性数量级的算法，其运行时间与n 成正比，如对一个表进行顺序查找时，其时间复杂度就是0(n)。有一些算法的时间复杂度为0(l o g m),即与n 的对数成正比，如在有序表上进行二分查找的算法就是如此。对数组进行简单插入或选择排序的算法的时间复杂度为0(/),当 n加倍时，其运行时间将增长4 倍。一个算法的时间复杂度还可以具体分为最好、最差和平均三种情况来讨论。下面结合从一维数组a n 中顺序查找其值等于给定值i t e m 的元素的算法进行说明。i nt Se qu e nc e Se a rc h (i nt a ,i nt n,i nt i t e m)若查找成功则返回元素的下标，否则

19、返回-1。(f o r(i nt i=0;i n;i+)i f (a i =i t e m)re t u rn i;re t u rn-1;)此算法的时间复杂度主要取决于f o r循环体被反复执行的次数。最好情况是第一个元素a 0 的值就等于i t e m,此时只需要进行元素的一次比较就查找成功，相应的时间复杂度为0(1);最差情况是最后一个元素a nT 的值等于i t e m,此时需要进行同全部n 个元素的比较才能查找成功，相应的时间复杂度为0(n);平均情况是：每一个元素都有相同的概率(即均 为,)等 于 给 定 值 i t e m,则 查 找 成 功 需 要 同 元 素 进 行 比 较

20、的 平 均 次 数 为nn:Z i =；5 +D，相应的时间复杂度为0(n),它同最坏情况具有相同的数量级，因为它z =l们之间的比较次数只在n 的系数项和常数项上有差别，而在n 的指数上没有差别。当在数组a 上顺序比较所有n 个元素后仍找不到等于给定值item 的元素，则表明查找失败，这种情况所对应的时间复杂度也为0(n)o对于许多算法来说，平均和最差这两种情况下的时间复杂度的数量级形式往往是相同的，它们主要是差别在最高次赛的系数上。另外有一些算法，其最好、最差和平均情况下的时间复杂度或相应的数量级都是相同的，如求出n 个元素平均值的算法就是如此，其时间复杂度的最好、最差和平均情况均为0(n

21、).上面从数据结构的分类、数据结构的定义、数据结构的二元组表示、数据结构的图形表示、数据结构的应用举例等多个方面，对数据结构的含义进行了详细地阐述，以便使同学们能够更好地利用数据结构组织数据和处理问题。这一讲也同时简要地介绍了算法的时间复杂度，与时间复杂度相类似的还有算法的空间复杂度，它是算法在运行过程中临时占用内存空间大小的相对量度，它也有常量级0(1)、平方根级0(五)、线性级0(n)、平方级0(/)、对数级O(logji)等不同级别。例如，对于下面的算法：int f(int n)if(n 0。当n=0 时则为空集。若集合为空，则表示为 ,若非空则表示为：(3 1,a.2,a i,Hi+i

22、,a j其中每个元素的下标为对该元素的编号，它是为了区别而任意标注的，不代表任何次序。因为集合中的元素可以按任何次序排列，假定就按元素前后位置编号的次序排列，那 么 a 1就是集合中的第一个元素,a?就是集合中的第二个元素,a i 就是第i 个元素,a。就是第口个(即最后一个)元素。集合中不含有任何关系，或者说含有的关系为空。集合中的元素类型可以为任何一种类型，假定用标识符E l e m T y p e 表示。若实际的元素类型为某一具体类型，如 整 型 i n t,则可以通过如下语句把E l e m T y p e 类型等价定义为i n t类型。T y p e d e f i n t E l

23、e m T y p e;二、集合的抽象数据类型集合的抽象数据类型包括数据和操作两个部分.数据部分为一个集合，假定用标识符S表示。操作部分包含对集合进行的各种常用运算，如初始化一个集合，向集合中插入一个元素，从集合中删除一个元素，从集合中查找一个元素等。集合结构的抽象数据类型可定义如下：ADT SET i s /其中SET表示集合的抽象数据类型名Dat a:表明为数据部分一个集合SO p e r at i o n:/表明为操作部分v o i d I n i t Se t (&S)/初始化集合为空bo o l I n s e r t Se t (&S,i t e m);/向集合中插入一个元素bo

24、o l De l e t e Se t (&S,i t e m);/从集合中删除一个元素bo o l Fi n d Se t (&S,&i t e m);从集合中查找一个元素.还有其他对集合的运算e n d SET初始化集合、向集合中插入元素和从集合中删除元素等，都需要改变集合的状态，所以函数中的集合参数S 必须定义为引用参数，这样才能够把运算后的结果反映到实参变量上，当从集合中查找元素时，它不会改变集合的状态，所以其集合参数可以使用引用参数，也可以使用值参数，若使用值参数，将会花费时间用来实现实参向值参变量的内容复制上，所以对集合的查找也最好采用引用参数为宜。另外，为了保护引用参数的值在查找

25、过程中不被改变，可以使用常量引用，即在引用参数前加上const保留字。三、集合的顺序存储结构和操作实现集合的顺序存储结构就是把集合中的所有元素，按照一定的次序顺序存储到内存中一块连续的存储空间中。我们知道，一个数组空间是内存的一块连续的存储空间，该空间中的存储位置是按照数组下标的次序顺序排列的，所以只要按照集合元素的编号次序把每个元素存储到数组中相应下标的存储位置，就实现了集合的顺序存储结构。假定用标识符set指向动态分配的数组空间，用标识符len表示集合当前长度的变量，用标识符MaxSize表示数组空间的大小，即数组中下标位置的个数，则集合的顺序存储结构类型，定义如下：struct SetS

26、q 这里假定用标识符SetSq表示这种结构类型ElemType*set;set用来指向动态分配的数组空间int len;存集合当前长度，即当前集合中所含元素的个数int MaxSize;/存 set数组长度，亦即所能存储集合的最大长度)；集合的顺序存储结构的示意图如下所示：lenset 0 12 n-1 n I n+1 I MaxSize-1a】a2汽3an在这里，加元素被存储到数组中下标为。的数组单元中，a2元素被存储到下标为1 的单元中，依次类推，最后一个元素an被存储到下标为n-1的单元中，存储集合长度len变量的值等于n,存储数组长度MaxSize变量的值等于数组空间的最大下标值加1。

27、下面给出对顺序存储的集合S 进行初始化以及插入、删除和查找元素的算法。1.初始化集合初始化集合需要为集合动态分配数组存储空间，并使set指向这个数组空间，该空间的大小由参数ms决定，当然ms 的值要大于等于1。void InitSet(SetSq&S,int ms)(if(ms item值插入到最后一个集合元素的后面空位置上；(4)集合长度增1;(5)返回真表示插入成功。对应的算法描述如下：bool InsertSet(SetSq&S,ElemType i tem)(if(S.len=S.MaxSize)cout 集合空间满！endl;exit(1);for(int i=0;iS.len;i+

28、)if(S.set i=i tem)cout 元素已存在！endl;return false;S.set S.len=i tem;S.len+;return true;)3.从集合中删除一个元素此算法首先从集合中顺序查找值等于待删值item 的元素，若存在则删除它，删除过程是把最后一个元素直接移动到该元素空出的位置，接着使集合长度减1,返回真表示删除成功；若不存在，则无法删除，返回假表示删除失败。bool DeleteSet(SetSqfc S,ElemType i tem)(for(int i=0;iS.len;i+)if(S.set i=item)break;if(iS.len)S.set

29、 i=S.set S.len-1;S.len一;return true;/删除成功返回真)elsereturn false;删除失败返回假4.从集合中查找一个元素此算法首先从集合中顺序查找值等于待查值ite m 的元素，若存在则把该元素值赋给item 引用参数带回，并返回真表示查找成功；若不存在，则返回假表示查找失败。通常传递给item 的待查值是一个元素的关键字，不是完整的记录，如对于学生记录，待查值是学号，对于产品记录，待查值是产品号；若查询到对应值的元素，则需要把该元素的完整值赋给item 带回，以便彳吏用。如可以通过item 得到某个学生的成绩，某个产品的价格等。bool FindSe

30、t(SetSq&S,ElemType&item)for(int i=0;iS.len;i+)if(S.set i=item)break;if(idata=item)break;else p=p-next;)if(p!=NULL)return false;/插入失败返回假建立值为item 的新结点sNode*tp=new sNode;tp-data=item;/新结点tp 插入到单链表的表头tp-next=head;head=tp;返回真表示插入成功return true;)3.从集合中删除一个元素(1)顺序查找集合单链表中是否存在值为待删除值为item 的元素，若不存在则返回假,表示删除失败；

31、(2)从单链表中删除结点，即把被删除结点的指针域的值赋给其前驱结点的指针域，若删除的是单链表中的表头结点，则把该结点的指针域的值赋给表头指针即可；(3)返回真表示删除成功。bool DeleteSet(sNode*&head,ElemType item)(从单链表中顺序查找是否存在值为item 的结点sNode*p=head,*q=NULL;/q 指 向 p 的前驱结点，开始时p 指表头，q 为空while(p!=NULL)if(p-data=item)break;else q=p;p=p-next;)if(p=NULL)return false;删除失败，返回假从单链表中删除已找到的p 结点

32、，它的前驱结点为q 结点if(q=NULL)head=p-next;删除表头结点，从单链表中摘除else q-next=p-next;/删除非表头结点回收p 结点后返回真delete p;return true;)4.从集合中查找一个元素bool FindSet(sNode*head,ElemType&item)(从单链表中顺序查找是否存在值为item 的结点sNode*p=head;while(p!=NULL)if(p-data=item)break;else p=p-next;)若存在由item 带回已查找到的元素并返回真，否则返回假if(p!=NULL)item=p-data;retur

33、n true;else return false;五、集合运算的时间复杂度分析插入运算：若已知插入的元素是集合中没有的，则可以省略从集合中查找该元素的步骤，把该元素直接写入到集合顺序表的表尾后的位置，使之成为新的表尾，或者把该元素直接链接到集合单链表的表头，成为新的表头结点，这种情况的时间复杂度为0(1);若在插入时不省略查找步骤，则向集合插入元素的时间复杂度为0 3)。删除运算：需要从集合中先顺序查找出待删除的元素，然后再从集合中删除该元素，所以其时间复杂度为0(n)。查找运算：需要顺序查找出给定元素，所以其时间复杂度为0(n)。六、线性表的存储和运算简介线性表是线性结构的一种表现形式。线性

34、表的定义、抽象数据类型、存储结构和运算等都同集合类似。线性表就是一种线性结构，即是具有相同属性的一个有限序列，序列中的元素是一个接一个有序的，序列中元素的个数就是该线性表的长度，若用n 表示，则 n 大于等于0,当n等 于 0 时其线性表为空。线性表中的所有元素通常用一对圆括号括起来，元素之间的位置排列次序就是它们的先后逻辑顺序。线性表中的元素个数也随着插入和删除元素的变化而变化。当向线性表中插入一个元素时，其长度就增加1,相反，当从线性表中删除一个元素后，其长度就减少1。线性表的抽象数据类型也同样包括数据和操作两个部分，数据部分是一个用顺序或链接存储的线性表，操作部分包括线性表的初始化，插入

35、、删除、查找元素等操作。线性表的存储结构也通常采用顺序和链接两种方式，顺序存储方式也是依靠数组实现的，链接存储方式也是依靠存储结点链接实现的。这都和集合的存储结构类似。线性表的插入运算与集合结构有所不同。向集合中插入一个元素是插入到顺序存储的集合的表尾，或者链接存储的集合的表头，它不涉及到其他任何元素或结点的改变；而向线性表中插入一个元素时，是按照逻辑次序进行插入，若要插入到顺序存储的线性表的第i个元素之后，则 第i+1至第n个的所有位置上的元素都要后移一个位置，腾出第i+1个位置，以便存储待插入的元素；若要插入到链接存储线性表的第i个元素之后，则要把新插入元素结点链接到对应的第i个元素结点之

36、后，第i+1个元素结点之前，为此需把第i个结点的指针域的值赋给新插入结点的指针域，使其指向后继的第i+1个结点，接着把新插入结点的地址赋给第i个结点的指针域，使其指向新插入的结点。下面来看一下向线性表插入元素的例子。假定一个包含6个元素的线性表为(23,15,48,34,79,60)假定被顺序存储在一维数组A 的前6个下标位置，如下所示：下标 012345678g23 15 48 34 79 60假定需要在下标为3的位置插入一个元素5 6,则首先需要把位置3至表尾位置5的所有元素依次后移一个位置，注意，应该按下标从大到小的次序，后移对应的元素，使下标为3的位置空出来，如下所示：下标 01234

37、5678g23 15 48 34 79 60接着把新元素56写入到已经空出的下标为3的位置，如下所示：下标 012345678g23 15 48 56 34 79 60再修改线性表中保存的当前长度的值，使之增加1,即由6变为，这样，对顺序存储的线性表的插入过程就结束了。若用链接的方式存储上述所给的线性表，则如下所示：head 23 M15 用 48 3 4若要在值为48的结点之后插入一个值为56的新结点，则得到的链接存储结构如下:head 23 15 48 56 f 34 *79 *60 A此时，48结点的后继结点不是34结点，而是56结点，即首先需要把原48结点的next域的值赋给新结点56

38、的指针域使之指向34结点，接着把新结点56的地址赋给48结点的指针域，使之指向新插入的56结点，这样就完成了在链接存储的线性表上插入元素的运算。若在顺序存储的线性表上删除一个元素，则需要把该元素位置之后的所有元素依次前移一个位置，然后再使线性表的长度减1即可。例如，一个线性表的顺序存储结构为：下标 012345678g23 15 48 34 79 60若要删除下标为1位置上的元素1 5,则使其后的每个元素前移，如下所示：下标 012345678g23 48 34 79 60然后，使线性表的长度由6减1后变为5,则删除操作就此完成。若要在链接存储的线性表上删除一个结点，则同在链接存储的集合上的删

39、除完全相同，就是把被删除结点的指针域的值赋给其前驱结点的指针域即可。例如，一个线性表的链接存储结构如下：head-2 3 用话一川48 修34 用79 用60加若要从中删除值为34的结点，则把结点34的指针域的值赋给其前驱结点48的指针域即可，得到的结果如下：head-23 修 西 闺 48 川 79 f 60|/|特殊地，若删除的是表头结点，即 head指针所指向的值为23的结点，则需要把需要把23结点的指针域的值赋给表头指针变量h e a d,使 head指向了值为15的结点，即原单链表中的第二个结点，运算结果如下：head 15 )48 34 79 60 H这一讲就讲到这里，同学们再见!

40、同学们好:第三讲栈和队列第一部分栈一、栈的定义二、栈的抽象数据类型三、栈的顺序存储结构和操作实现四、栈的链接存储结构和操作实现五、栈的简单应用举例一、栈的定义栈（S t a c k）是一种运算受限的线性表，其限制是仅允许在表的一端进行插入和删除运算。人们把对栈进行运算的一端称为栈顶，栈顶的第一个元素被称为栈顶元素，相对地，把另一端称为栈底，向一个栈插入新元素又称为进栈或入栈，它是把该元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称为出栈或退栈，它是才“戋顶元素删除掉，使其下面的相邻元素成为新的栈顶元素。在日常生活中，有许多类似栈的例子，如刷洗盘子时，依次把每个洗净的盘子放到洗

41、好的一摞盘子的上面，此操作相当于进栈；取用盘子时，从一摞盘子上一个接一个地向下拿，相当于出栈。又如向枪支弹夹里装子弹时，子弹被一个接一个地压入，则称为进栈；射击时子弹总是从顶部一个接一个地被射出，此称为子弹出栈。由于栈的插入和删除运算仅在栈顶一端进行，后进栈的元素必定先出栈，所以又把栈称为后进先出表（La st In Fi rst Out,简称LIFO）。假定一个栈S为（a,b,c）,其中表尾的一端为栈顶，字 符c为栈顶元素。若 向S压入一个 元 素d,则S变为（a,b,c,d）,此时字符d为栈顶元素；若接着从栈S中依次删除两个元素，则首先删除的是元素d,接着删除的是元素c,栈S变为（a,b）

42、,栈顶元素为b.二、栈的抽象数据类型栈的抽象数据类型中的数据部分为具有El e m Ty pe元素类型的一个栈，它可以采用任一种存储结构实现；操作部分应包括元素进栈、元素出栈、读取栈顶元素、检查栈是否为空等。下面给出栈的抽象数据类型的具体定义.ADT STACK is STACK是栈的抽象数据类型名一个栈S,存储栈中的所有元素O peration:void Ini tStack(&S);void Push(&S,item)ElemType Pop(&S)ElemType Peek(&S)bool EmptyStack(&S);void C learStack(&S);初始化栈S,即把它置为空/

43、元素进栈，即把元素ile m插入到栈顶/删除栈顶元素并返回之/返回栈顶元素的值，但不改变栈的状态/判断S是否为空清除栈中所有元素，使之成为空栈end STACK对于判断栈是否为空和返回栈顶元素这两种操作，由于它们不改变栈的状态，所以可在引用参数前使用常量定义符c o n s t,使得函数操作不能有意或无意地改变栈的状态。假定栈a 的元素类型为i n t,下面给出调用上述栈操作的一些例子。(1)In i tSta ck(a);(2)P ush (a,1 8);(3)i n t x=4 6;P ush (a,x);(4)P ush(a,x/3);(5)x=P op(a);(6)cout P e e

44、 k (a);P op(a);(8)Em pty Sta ck (a);(9)cout P op(a)e n d l;(1 0)x=Em pty Sta ck (a);表示把栈a置空表示元素1 8进栈表示x的值4 6进栈表示x除 以3的整数值1 5进栈表示栈顶元素1 5退栈并赋给x表示读取当前栈顶元素4 6并输出栈顶元素4 6出栈，返回值4 6自动丢失因此时栈a非空，所以返回的值f a l se栈顶元素1 8退栈并输出，此时栈已空因栈为空，返 回true,接着把对应的整数值1赋 给x三、栈的顺序存储结构和操作实现栈的顺序存储结构同集合的顺序存储结构类似，定义的结构类型如下：struct Sta

45、 ck /Sta ck 为结构类型名El e m Ty pe *sta ck;指向动态分配的数组存储空间的首地址的指针i n t top;栈顶指针，存储栈顶元素所在的下标位置i n t Ma x Si z e;/保 存sta ck所指向的栈空间的大小）；在顺序存储的栈中，to p 的值为T表示栈空，每次向栈中压入一个元素时，首先使top增 1,用以指示新的栈顶位置，然后再把元素赋值到这个空位置上，每次从栈中弹出一个元素时，首先取出栈顶元素，然后使top减 1,指示出前一个元素成为新的栈顶元素。由此可知，对顺序栈的插入和删除运算相当于是在顺序表的表尾进行的，其时间复杂度为0（1）。在一个顺序栈中

46、，若 to p 已经指向了 MaxSize-1的位置，则表示栈满，若再向其插入新元素时就需要进行栈满处理，如分配更大的存储空间满足插入要求，或输出栈满信息告之用户等；相反，若 to p 的值已经等于T,则表示栈空，通常利用栈空作为循环结束的条件，表明栈中的数据已经处理完毕。设一个栈S 为（a,b,c,d,e）,对应的顺序存储结构如下图（a）所示。若向S 中插入一个元素 3则对应如下图（b）所示。若接着执行两次出栈操作后，贝 U 栈 S 对应如下图（c）所示。若依次使栈S 中的所有元素出栈，则 s 变为空，如下图（d）所示。(a)top=4MaxSize-1.MaxSize-1.MaxSize-

47、1.MaxSize-1.5f top4etop 4e443d3d3d4top 32c2c2c21b1b1b10a0a0a0(b)top=5(c)top=3(d)top二 T下面给出栈在顺序存储结构下的操作实现。1.初始化栈S 为空初始化顺序栈需要为其动态分配数组存储空间，并使stack指向这个数组空间，该空间的大小由参数ms决定，当然ms的值要大于等于Lvoid Ini tStack(Stack&S,int ms)(if(ms=0)coutnms 值非法!endl;exit(1);初始设置栈空间大小为ms的值S.MaxSize=ms;/动态存储空间分配S.stack=new ElemTypeS

48、.MaxSize;/初始置栈为空S.top=-l;)2.元 素 item 进栈，即插入到栈顶void Push(Stack&S,ElemType item)(若栈空间用完则自动扩大2 倍空间，原有栈内容不变if(S.top=S.MaxSize-1)int k=s izeof(ElemType);计算每个元素存储空间的长度S.stack=(ElemType*)realloc(S.stack,2*S.MaxSize*k);S.MaxSize=2*S.MaxSize;把栈空间大小修改为新的长度)栈顶指针后移一个位置S.top+;将新元素插入到栈顶S.stackS.top=item;)3.删除栈顶元素

49、并返回ElemType Pop(Stack&S)(若栈空则退出运行if(S.top=-l)cerr 栈空，退出运行！d a t a=it er n;向栈顶插入新结点new p t r-nex t=HS;HS=new p t r;)3.从链栈中删除一个元素并返回El em Ty p e P o p (s N o d e*&HS)(if(HS=N U L L)不能从空栈中删除c er r L ink ed s t a c k is em p t y!ne x t;/使栈顶指针指向下一结点El em Ty p e t em p=p-d a t a;/暂存原栈顶元素d el et e p;回收原栈顶结

50、点r et u r n t em p;返回原栈顶元素)4.读取栈顶元素El em Ty p e P eek (s N o d e*HS)HS 为值参或引用形参均可(if(HS=N U L L)无法从空栈中读取c er r L ink ed s t a c k is em p t y!*d a t a;/返回栈顶结点的值)5.检查链栈是否为空b o o l Em p t y S t a c k (s N o d e*I I S)HS 为值参或引用形参均可(r et u r n HS=N U L L;)6 清除链栈为空v o id Cl ea r S t a c k (s N o d e*&I I