计算机软件基础基本数据结构修改课件.ppt

《计算机软件基础基本数据结构修改课件.ppt》由会员分享，可在线阅读，更多相关《计算机软件基础基本数据结构修改课件.ppt（171页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算机算机软件基件基础基本数据基本数据结构修改构修改第1页，此课件共171页哦2.1 数据结构的基本概念数据结构的基本概念2.1.1 两个例子两个例子2.1.2 什么是数据结构什么是数据结构2.1.3 数据结构的图形表示数据结构的图形表示2.1.4 线性数据结构与非线性数据结构线性数据结构与非线性数据结构2第2页，此课件共171页哦数据结构三个方面的问题：数据结构三个方面的问题：(1)(1)数据的逻辑结构数据的逻辑结构(2)(2)数据的存储结构数据的存储结构(3)(3)对各种数据结构进行的运算对各种数据结构进行的运算目的：提高数据处理的效率目的：提高数据处理的效率提高数据处理的速度提高数据处理

2、的速度尽量节省计算机存储空间尽量节省计算机存储空间 3第3页，此课件共171页哦2.1.1 两个例子两个例子 计计算算机机已已广广泛泛应应用用于于数数据据处处理理。实实际际问问题中的各数据元素之间总是相互关联的。题中的各数据元素之间总是相互关联的。所所谓谓数数据据处处理理，是是指指对对数数据据集集合合中中的的各各元元素素以以各各种种方方式式进进行行运运算算，包包括括插插入入、删删除除、查查找找、更更改改等等运运算算，以以包包括括对对数数据据元元素素进进行行分析。分析。4第4页，此课件共171页哦 重要的是知道数据集合中各数据元素之间存重要的是知道数据集合中各数据元素之间存在什么关系，为了提高处

3、理效率，应如何组在什么关系，为了提高处理效率，应如何组织它们，即如何表示所需要处理的数据元素。织它们，即如何表示所需要处理的数据元素。5第5页，此课件共171页哦例例2.1 2.1 无序表的顺序查找无序表的顺序查找35 16 78 85 43 29 33 21 54 4635 16 78 85 43 29 33 21 54 46 有序表的对分查找有序表的对分查找16 21 29 33 35 43 46 54 78 8516 21 29 33 35 43 46 54 78 85数数据据元元素素在在表表中中的的排排列列顺顺序序对对查查找找效效率率是是有有很很大影响大影响6第6页，此课件共171页哦

4、无序表的顺序查找无序表的顺序查找从第一个元素开始，逐个将表中的元素与被查数从第一个元素开始，逐个将表中的元素与被查数进行比较，直到表中的某个元素与被查数相等进行比较，直到表中的某个元素与被查数相等（即查找成功）或者表中所有元素都与被查数（即查找成功）或者表中所有元素都与被查数进行了比较且都不相等（即查找失败）为止。进行了比较且都不相等（即查找失败）为止。最少次数最少次数：被查元素刚好是表中第一个元素时。：被查元素刚好是表中第一个元素时。只需比较一次。只需比较一次。最多次数最多次数：被查元素刚好是表中最后一个元素时：被查元素刚好是表中最后一个元素时或表中不存在被查元素。在这种情况下顺序查或表中不

5、存在被查元素。在这种情况下顺序查找是很费时间的。找是很费时间的。7第7页，此课件共171页哦有序表中的二分查找有序表中的二分查找 将被查数与表中的中间这个元素进行比较：将被查数与表中的中间这个元素进行比较：若相等，则表示查找成功，查找过程结束；若若相等，则表示查找成功，查找过程结束；若被查数大于表中的中间这个元素，则表示如果被查数大于表中的中间这个元素，则表示如果被查数在表中，只能在表的后半部，此时可以被查数在表中，只能在表的后半部，此时可以舍弃表中的前半部保留后半部；若被查数小于舍弃表中的前半部保留后半部；若被查数小于表中的中间元素，则表示如果被查数在表中，表中的中间元素，则表示如果被查数在

6、表中，只能在表的前半部此时可以舍弃后半部而保留只能在表的前半部此时可以舍弃后半部而保留前半部。然后对剩下部分再按照上述方法进行前半部。然后对剩下部分再按照上述方法进行查找，这个过程一直做到在某次的比较中相等查找，这个过程一直做到在某次的比较中相等（查找成功）或剩下的部分已空（查找失败）（查找成功）或剩下的部分已空（查找失败）为止。为止。8第8页，此课件共171页哦 在有序表的对分查找中，不论查找的是什在有序表的对分查找中，不论查找的是什么数，也不论要查找的数在表中有没有，都不么数，也不论要查找的数在表中有没有，都不需要与表中所有元素进行比较，并且只需要与需要与表中所有元素进行比较，并且只需要与

7、表中很少的元素进行比较。但需要指出的是，表中很少的元素进行比较。但需要指出的是，对分查找只适用于有序表，而对于无序表是无对分查找只适用于有序表，而对于无序表是无法进行对分查找的。法进行对分查找的。9第9页，此课件共171页哦例例2.2 2.2 学生情况登记表以学号为顺序排列学生情况登记表以学号为顺序排列10第10页，此课件共171页哦11第11页，此课件共171页哦12第12页，此课件共171页哦结论：结论：在对数据进行处理时，在对数据进行处理时，可以根据所做的运算不同，可以根据所做的运算不同，将数据组织成不同的形式，将数据组织成不同的形式，以便于做该种运算，以便于做该种运算，从而提高数据处理

8、的效率。从而提高数据处理的效率。13第13页，此课件共171页哦2.1.2 什么是数据结构什么是数据结构 数据结构数据结构(data structure)(data structure)是指相互有关联的是指相互有关联的数据元素集合。数据元素集合。数据元素（数据元素（data elementdata element）是数据集合中的一是数据集合中的一个个体，是数据的基本单位。个个体，是数据的基本单位。14第14页，此课件共171页哦例例1 1：描述一年四季的季节名描述一年四季的季节名 春，夏，秋，冬春，夏，秋，冬 可以作为季节的数据元素；可以作为季节的数据元素；例例2 2：数值集合数值集合N=1,

9、2,3,4,5N=1,2,3,4,5中整数中整数1 1至至5 5均为数均为数据元素。据元素。例例3 3：表示家庭成员的各成员名表示家庭成员的各成员名 父亲，儿子，女儿父亲，儿子，女儿 可以作为家庭成员的数据元素。可以作为家庭成员的数据元素。现实世界中客观存在的一切个体都可以是数据元素。现实世界中客观存在的一切个体都可以是数据元素。15第15页，此课件共171页哦 前后件关系前后件关系是数据元素之间的一个基本关系，是数据元素之间的一个基本关系，但前后件关系所表示的实际意义是随具体对但前后件关系所表示的实际意义是随具体对象的不同而不同。象的不同而不同。一般来说，数据元素之间的任何关系都可以一般来说

10、，数据元素之间的任何关系都可以用前后件关系来描述。用前后件关系来描述。例如：例如：“春春”是是“夏夏”的的前件前件，“夏夏”是是“春春”的的后件后件。“父亲父亲”是是“儿子儿子”，“女儿女儿”的的前件前件，“儿子儿子”，“女儿女儿”是是“父亲父亲”的的后续后续。16第16页，此课件共171页哦1.数据的逻辑结构数据的逻辑结构 是指反映数据元素之间逻辑关系的数据结构。是指反映数据元素之间逻辑关系的数据结构。研究数据元素及其关系的数学特性；研究数据元素及其关系的数学特性；（1 1）表示数据元素的信息；）表示数据元素的信息；（2 2）表示各数据元素之间的前后件关系。）表示各数据元素之间的前后件关系。

11、17第17页，此课件共171页哦 数据的逻辑结构有两个要素：数据的逻辑结构有两个要素：数据元素的集合数据元素的集合D D；反映反映D D中各数据元素之间的前后件关系中各数据元素之间的前后件关系R R。数据结构可以表示成数据结构可以表示成 S S（D D，R R）其中其中B B表示数据结构。表示数据结构。18第18页，此课件共171页哦为了反映为了反映D D中各数据元素之间的前后件关系，一中各数据元素之间的前后件关系，一般用二元组来表示。般用二元组来表示。设设a a与与b b是是D D中的两个数据，则二元组中的两个数据，则二元组 （a a，b b）表示表示a a是是b b的前件，的前件，b b是

12、是a a的后件。的后件。例如例如 S S（D D，R R）D D 春，夏，秋，冬春，夏，秋，冬 R R(春，夏春，夏)，(夏，秋夏，秋)，(秋，冬秋，冬)19第19页，此课件共171页哦家庭成员数据结构家庭成员数据结构 S S（D D，R R）D D 父亲，儿子，女儿父亲，儿子，女儿 R R(父亲，儿子），父亲，儿子），(父亲，女儿）父亲，女儿）n n维向量维向量 X X（x x1 1，x x2 2，x xn n）也是一种数据结构。即也是一种数据结构。即 S S（D D，R R）D Dxx1 1，x x2 2，x xn n R R(x(x1 1，x x2 2)，(x(x2 2，x x3 3)，

13、(x(xn n1 1，x xn n)20第20页，此课件共171页哦mnmn的矩阵是一个数据结构。即的矩阵是一个数据结构。即 S S（D D，R R）D DAA1 1，A A2 2，A Am m R R(A(A1 1，A A2 2)，(A(A2 2，A A3 3)，(A(Ai i，A Ai i1 1)，(A(Am m1 1，A Am m)其中其中A Ai i=（a ai1i1，a ai2i2，a ainin），），i i1 1，2 2，m m A Ai i（D Di i，R Ri i）D Di iaai1i1，a ai2i2，a ainin R Ri i(a(ai1i1，a ai2i2)，(a

14、(ai2i2，a ai3i3)，(a(aijij，a ai i，j j1 1)，(a(ai i，n n1 1，a ainin)21第21页，此课件共171页哦2.数据的存储结构（数据的物理结构）数据的存储结构（数据的物理结构）数据的逻辑结构在计算机存储空间中的存放形数据的逻辑结构在计算机存储空间中的存放形式。也就是具体实现，通常用高级语言中各种式。也就是具体实现，通常用高级语言中各种数据类型来描述这种实现。数据类型来描述这种实现。常用的存储结构有：常用的存储结构有：顺序、链接、索引等存储结构。顺序、链接、索引等存储结构。采用不同的存储结构，其数据处理的效率是不采用不同的存储结构，其数据处理的效

15、率是不同的。同的。22第22页，此课件共171页哦2.1.3 数据结构的图形表示数据结构的图形表示数据集合数据集合D D中的每一个数据元素用中间标有元素中的每一个数据元素用中间标有元素值的方框表示（数据结点，结点）值的方框表示（数据结点，结点）用一条有向线段从前件结点指向后件结点。用一条有向线段从前件结点指向后件结点。23第23页，此课件共171页哦 一年四季数据结构的图形表示一年四季数据结构的图形表示24第24页，此课件共171页哦家庭成员间辈份关系数据结的图形表示家庭成员间辈份关系数据结的图形表示25第25页，此课件共171页哦S=(D1,R1)D1=a,b,c,d,eR1=(a,b),(

16、b,c),(c,d),(d,e),(e,a),(a,c),(a,d),(b,e),(c,e)daebcDS1是个无向图是个无向图26第26页，此课件共171页哦S=(D2,R2)D2=a,b,c,d,eR2=a,b,b,c,c,d,d,e,e,a,a,c,a,d,b,e,c,edaebcDS2是一个有向图是一个有向图27第27页，此课件共171页哦S=(D,R)D=a1,a2,a3,akR=|这说明这个关系这说明这个关系R任何两递增下标的数据元素都任何两递增下标的数据元素都有相邻关系，如图所示有相邻关系，如图所示a1a2a3ak数组的数据结构数组的数据结构28第28页，此课件共171页哦 用图

17、形表示数据结构用图形表示数据结构S S（D D，R R）D Dddi i|1i7|1i7dd1 1，d d2 2，d d3 3，d d4 4，d d5 5，d d6 6，d d7 7 R R(d(d1 1，d d3 3)，(d(d1 1，d d7 7)，(d(d2 2，d d4 4)，(d(d3 3，d d6 6)，(d(d4 4，d d5 5)29第29页，此课件共171页哦数据结构的相关概念数据结构的相关概念在数据结构中，没有前件的结点称为根结点；没在数据结构中，没有前件的结点称为根结点；没有后件的结点成为终端结点（也成为叶子结点）有后件的结点成为终端结点（也成为叶子结点）；除了根结点与终

18、端结点外的其他结点一般称；除了根结点与终端结点外的其他结点一般称为内部结点。为内部结点。数据结构中的相关运算：数据结构中的相关运算：插入运算、删除运算。这两个运算是对数据结构插入运算、删除运算。这两个运算是对数据结构的两种基本运算。除此之外，对数据结构的运的两种基本运算。除此之外，对数据结构的运算还有查找、分类、合并、分解、复制和修改算还有查找、分类、合并、分解、复制和修改等。等。在一个数据结构中元素结点和数据元素之间的关在一个数据结构中元素结点和数据元素之间的关系都可能是动态变化的。系都可能是动态变化的。30第30页，此课件共171页哦2.1.4 线性数据结构与非线性数据结构线性数据结构与非

19、线性数据结构线性表的逻辑结构是线性表的逻辑结构是n n个数据元素的有限序列个数据元素的有限序列(a1,a2,a3,(a1,a2,a3,an),an)其中其中n n表示了线性表的长度（表示了线性表的长度（n=0n=0）.n=0.n=0的表的表称为空表。称为空表。线性结构：数据元素呈线性关系。隐含有序。线性结构：数据元素呈线性关系。隐含有序。（1 1）有且只有一个根结点；）有且只有一个根结点；（2 2）每一个结点最多有一个前件，）每一个结点最多有一个前件，也最多有一个后件。也最多有一个后件。线性结构又称线性表。线性结构又称线性表。31第31页，此课件共171页哦特别说明特别说明 在一个线性结构中插

20、入或删除任何一个结在一个线性结构中插入或删除任何一个结点后还应该是线性结构。如果一个数据结构满点后还应该是线性结构。如果一个数据结构满足上述两个条件，但当在此数据结构中插入或足上述两个条件，但当在此数据结构中插入或删除任何一个结点后就不满足这两个条件了，删除任何一个结点后就不满足这两个条件了，则该数据结构不能称为线性结构。则该数据结构不能称为线性结构。32第32页，此课件共171页哦不是线性结构的数据结构特例不是线性结构的数据结构特例33第33页，此课件共171页哦 如果一个数据结构不是线性结构，如果一个数据结构不是线性结构，则称之为则称之为非线性非线性结构结构34第34页，此课件共171页哦

21、2.2 线性表及其顺序存储结构线性表及其顺序存储结构2.2.1 2.2.1 线性表及其运算线性表及其运算2.2.2 2.2.2 栈及其应用栈及其应用2.2.3 2.2.3 队列及其应用队列及其应用35第35页，此课件共171页哦2.2.1 线性表及其运算线性表及其运算1.什么是线性表什么是线性表(Linear List)线性表是最简单最常用的一种数据结构。线性表是最简单最常用的一种数据结构。线性表是由一组数据元素构成。线性表是由一组数据元素构成。例如：例如：n维向量维向量(x1，x2，xn)是一个长度为是一个长度为n的线性表，其中的每一个分量就是一个数据的线性表，其中的每一个分量就是一个数据元

22、素。元素。英英文文小小写写字字母母表表(a(a，b b，c c，z)z)是是一一个个长长度度为为2626的线性表的线性表一一年年中中的的四四个个季季节节(春春，夏夏，秋秋，冬冬)是是一一个个长长度度为为4 4的线性表的线性表矩阵是一个比较复杂的线性表矩阵是一个比较复杂的线性表36第36页，此课件共171页哦学生情况登记表是一个复杂的线性表学生情况登记表是一个复杂的线性表,由若干数据由若干数据项组成的数据元素称为记录项组成的数据元素称为记录(record)(record)由多个记录构成的线性表又称为文件由多个记录构成的线性表又称为文件(file)(file)37第37页，此课件共171页哦 线线

23、性性表表是是由由n(n0)n(n0)个个数数据据元元素素a a1 1，a a2 2，a an n组组成成的的一一个个有有限限序序列列，表表中中的的每每一一个个数数据据元元素素，除除了了第第一一个个外外，有有且且只只有有一一个个前前件件，除除了了最最后后一一个个外外，有有且且只只有有一一个个后后件件。即即线线性性表表或或是是一一个个空空表表，或或可可以表示为以表示为 (a(a1 1，a a2 2，a ai i，a an n)其其中中a ai i(i(i1 1，2 2，n)n)是是属属于于数数据据对对象象的的元元素素，通通常常也也称称其其为为线线性性表表中中的的一一个结点。个结点。线性表的逻辑结构

24、线性表的逻辑结构38第38页，此课件共171页哦 非空线性表结构特征：非空线性表结构特征：(1)(1)有且只有一个根结点有且只有一个根结点a a1 1，它无前件；，它无前件；(2)(2)有且只有一个终端结点有且只有一个终端结点a an n，它无后件；，它无后件；(3)(3)除根结点与终端结点外，其它所有结除根结点与终端结点外，其它所有结点有且只有一个前件，也有且只有一个点有且只有一个前件，也有且只有一个后件。后件。线性表中结点的个数线性表中结点的个数n n称为线性表的长度。称为线性表的长度。当当n n0 0时，称为空表。时，称为空表。39第39页，此课件共171页哦2.线性表的顺序存储结构线性

25、表的顺序存储结构线性表的顺序存储结构基本特点：线性表的顺序存储结构基本特点：(1)(1)线线性性表表中中所所有有元元素素所所占占的的存存储储空空间间是是连连续的；续的；(2)(2)线线性性表表中中各各数数据据元元素素在在存存储储空空间间中中是是按按逻辑顺序依次存放的。逻辑顺序依次存放的。线性表中第线性表中第i i个元素个元素a ai i在计算机存储空间中在计算机存储空间中的存储地址为的存储地址为 ADR(aADR(ai i)ADR(aADR(a1 1)(i(i1)k1)k40第40页，此课件共171页哦长度为长度为n n的线性表的线性表(a(a1 1，a a2 2，a ai i，a an n)

26、顺序存储结构顺序存储结构41第41页，此课件共171页哦整型一维数组存放整型一维数组存放长度为长度为8 8的线性表的线性表(29,18,56,63,35,24,31,47)(29,18,56,63,35,24,31,47)42第42页，此课件共171页哦建立空线性表的顺序存储空间建立空线性表的顺序存储空间（即初始化线性表的顺序存储空间）（即初始化线性表的顺序存储空间）#include stdlib.h#include stdlib.h void initsl(v void initsl(v，m m，n)n)ET *v ET *v；int mint m，*n n；v vmalloc(m*size

27、of(ET)malloc(m*sizeof(ET)；*n n0 0；returnreturn；释放线性表的顺序存储空间释放线性表的顺序存储空间 free(v)free(v)；43第43页，此课件共171页哦 线性表顺序存储结构下的主要运算：线性表顺序存储结构下的主要运算：(1)(1)在在线线性性表表的的指指定定位位置置处处加加入入一一个个新新的的元元素素（即即线性表的插入）；线性表的插入）；(2)(2)在线性表中删除指定的元素（即线性表的删除）；在线性表中删除指定的元素（即线性表的删除）；(3)(3)在在线线性性表表中中查查找找某某个个（或或某某些些）特特定定的的元元素素（即线性表的查找）；（

28、即线性表的查找）；(4)(4)对线性表中的元素进行整序（即线性表的排序）；对线性表中的元素进行整序（即线性表的排序）；(5)(5)按按要要求求将将一一个个线线性性表表分分解解成成多多个个线线性性表表（即即线线性表的分解）；性表的分解）；(6)(6)按按要要求求将将多多个个线线性性表表合合并并成成一一个个线线性性表表（即即线线性表的合并）；性表的合并）；(7)(7)复制一个线性表（即线性表的复制）；复制一个线性表（即线性表的复制）；(8)(8)逆转一个线性表（即线性表的逆转）等。逆转一个线性表（即线性表的逆转）等。44第44页，此课件共171页哦3.线性表在顺序存储下的插入运算线性表在顺序存储下

29、的插入运算45第45页，此课件共171页哦46第46页，此课件共171页哦线性表在顺序存储下的插入算法线性表在顺序存储下的插入算法输输入入：线线性性表表的的存存储储空空间间V(1V(1：m)m)；线线性性表表的的长长度度n n（nmnm）；插插入入的的位位置置i i（i i表表示示在在第第i i个个元元素之前插入）；插入的新元素素之前插入）；插入的新元素b b。输输出出：插插入入后后的的线线性性表表存存储储空空间间V(1V(1：m)m)及及线线性性表的长度表的长度n n。47第47页，此课件共171页哦PROCEDURE INSL(VPROCEDURE INSL(V，m m，n n，i i，b

30、)b)1.1.IF IF (n(nm)m)THEN THEN OVERFLOWOVERFLOW；RETURNRETURN 2.IF (i 2.IF (in)THEN in)THEN in n1 1 3.IF (i 3.IF (i1)THEN i1)THEN i1 1 4.4.FOR FOR j jn n TO TO i i BY BY 1 1 DO DO V V(j(j1)1)V(j)V(j)5.V(i)5.V(i)b b 6.n 6.nn n1 1 7.RETURN 7.RETURN48第48页，此课件共171页哦 void insl(v void insl(v，m m，n n，i i，b)

31、b)ET v ET v，b b；int mint m，*n n，i i；if (*n if (*nm)m)printf(overflow n)printf(overflow n)；returnreturn；if (i if (i*n n1)i1)i*n n1 1；if (iif (i1)i1)i1 1；for for(j(j*n n；j ji i；j)j)vjvjvjvj11；vivi11b b；*n n*n n1 1；returnreturn；49第49页，此课件共171页哦4.线性表在顺序存储下的删除运算线性表在顺序存储下的删除运算50第50页，此课件共171页哦51第51页，此课件共17

32、1页哦线性表在顺序存储下的删除算法线性表在顺序存储下的删除算法输输入入：线线性性表表的的存存储储空空间间V(1V(1：m)m)；线线性表的长度性表的长度n n（nmnm）；）；删删除除的的位位置置i i（表表示示删删除除第第i i个个元元素）。素）。输输出出：删删除除后后的的线线性性表表存存储储空空间间V(1V(1：m)m)及线性表的长度及线性表的长度n n。52第52页，此课件共171页哦PROCEDURE DESL(VPROCEDURE DESL(V，m m，n n，i)i)1.1.IF IF (n(n0)0)THEN THEN UNDERFLOWUNDERFLOW；RETURNRETUR

33、N 2.IF(i 2.IF(i1)or(i1)or(in)THEN n)THEN “Not Not this this element element in in the the listlist”；RETURNRETURN 3.3.FOR FOR j ji i TO TO n n1 1 DO DO V(j)V(j)V(jV(j1)1)4.n 4.nn n1 1 5.RETURN 5.RETURN53第53页，此课件共171页哦 void desl(v void desl(v，m m，n n，i)i)ET v ET v；int mint m，*n n，i i；if(*n if(*n0)0)pr

34、intf(underflow n)printf(underflow n)；returnreturn；if (i if (i1)|(i1)|(i*n)n)printf(Not this element in the list n)printf(Not this element in the list n)；returnreturn；for (j for (ji i；j j*n n1 1；j j)vj)vj11vjvj；*n n*n n1 1；returnreturn；54第54页，此课件共171页哦1.什么是栈什么是栈栈（栈（stack）是一种特殊的线性表。对它的）是一种特殊的线性表。对它的操作

35、只能是操作只能是“后进先出后进先出”（LIFO），也是），也是使用最为广泛的数据结构之一。因为它的运算使用最为广泛的数据结构之一。因为它的运算次序受到严格的规定，故又称为限定性数据结次序受到严格的规定，故又称为限定性数据结构。构。为了认识栈这种数据结构，首先介绍一个例为了认识栈这种数据结构，首先介绍一个例子。子。2.2.2 栈及其应用栈及其应用55第55页，此课件共171页哦主程序与子程序之间的调用关系主程序与子程序之间的调用关系 MAIN SUB1 SUB2 SUB3 SUB4MAIN SUB1 SUB2 SUB3 SUB4 CALLSUB1 CALLSUB2 CALLSUB3 CALLSU

36、B4 CALLSUB1 CALLSUB2 CALLSUB3 CALLSUB4 A A：B B：C C：D D：END RETURN RETURN RETURN RETURN END RETURN RETURN RETURN RETURN56第56页，此课件共171页哦 由这个例子可以看出，在这种特殊的由这个例子可以看出，在这种特殊的线性表中，其插入与删除运算都只能在线性表中，其插入与删除运算都只能在线性表的一段进行。即在这种线性表的线性表的一段进行。即在这种线性表的结构中，一端是封闭的，不允许插入和结构中，一端是封闭的，不允许插入和删除元素；另一端是开口的，允许插入删除元素；另一端是开口的，允

37、许插入与删除元素。在顺序存储结构下，对这与删除元素。在顺序存储结构下，对这种类型线性表的插入与删除运算是不需种类型线性表的插入与删除运算是不需要移动表中其它数据元素的。这种线性要移动表中其它数据元素的。这种线性表成为栈。表成为栈。57第57页，此课件共171页哦栈栈(stack)(stack)是限定在一端进行插入与删除的线性表。是限定在一端进行插入与删除的线性表。栈顶栈顶:允许插入与删除的一端允许插入与删除的一端.栈底栈底:不允许插入与删除的另一端。不允许插入与删除的另一端。栈是按照栈是按照“先进后出先进后出”(FILO(FILOFirst In Last Out)First In Last

38、Out)或或“后进先出后进先出”(LIFO(LIFOLast In First Out)Last In First Out)的原则的原则组织数据的，因此，栈也被称为组织数据的，因此，栈也被称为“先进后出先进后出”表或表或“后进先出后进先出”表。表。栈具有栈具有记忆记忆作用。用指针作用。用指针toptop来指示栈顶的位置，用指来指示栈顶的位置，用指针针bottombottom指向栈底。指向栈底。往栈中插入一个元素称为往栈中插入一个元素称为入栈入栈运算，从栈中删除一个运算，从栈中删除一个元素元素(即删除栈顶元素即删除栈顶元素)称为称为退栈退栈运算。运算。关于栈的几个基本概念关于栈的几个基本概念58

39、第58页，此课件共171页哦59第59页，此课件共171页哦2.栈的顺序存储及其运算栈的顺序存储及其运算60第60页，此课件共171页哦toptop0 0表示栈空；表示栈空；toptopm m表示栈满。表示栈满。建立空栈的顺序存储空间建立空栈的顺序存储空间（即初始化栈的顺序存储空间）（即初始化栈的顺序存储空间）#include stdlib.h#include stdlib.h void init_stack(s void init_stack(s，m m，top)top)ET *s ET *s；int mint m，*toptop；s smalloc(m*sizeof(ET)malloc(m

40、*sizeof(ET)；*toptop0 0；returnreturn；释放栈的顺序存储空间时释放栈的顺序存储空间时 free(s)free(s)；61第61页，此课件共171页哦(1)(1)入栈运算入栈运算 PROCEDURE PUSH(SPROCEDURE PUSH(S，m m，toptop，x)x)1.1.IF IF (top(topm)m)THEN THEN StackStackOVERFLOWOVERFLOW；RETURN RETURN 2.top 2.toptoptop1 1 3.S(top)3.S(top)x x 4.RETURN 4.RETURN void push(s，m，t

41、op，x)ET s，x；int m，*top；if(*topm)printf(Stackoverflown)；return；*top*top1；s*top1x；return；62第62页，此课件共171页哦(2)(2)退栈运算退栈运算PROCEDURE POP(S，m，top，y)1.IF (top0)THEN StackUNDERFLOW；RETURN 2.yS(top)3.toptop14.RETURNvoid pop(s，m，top，y)ET s，*y；int m，*top；if(*top0)printf(Stackunderflown)；return；*ys*top1；*top*top

42、1；return；63第63页，此课件共171页哦PROCEDURE TOP(S，m，top，y)1.IF (top0)THEN “Stack empty”；RETURN 2.yS(top)3.RETURN(3)(3)读栈顶元素读栈顶元素void top(s，m，top，y)ET s，*y；int m，*top；if(*top0)printf(Stack empty n)；return；*ys*top1；return；64第64页，此课件共171页哦3.表达式的计算表达式的计算运运算算符符栈栈，用用于于在在表表达达式式处处理理过过程程中中存存放放运算符。运算符。在在开开始始时时，运运算算符符栈

43、栈中中先先压压入入一一个个表表达达式式结结束符束符“；”。操操作作数数栈栈，用用于于在在表表达达式式处处理理过过程程中中存存放放操作数。操作数。65第65页，此课件共171页哦从左到右依次读出表达式中的各个符号：从左到右依次读出表达式中的各个符号：若若是是操操作作数数，则则压压入入操操作作数数栈栈，依依次次读读下一个符号。下一个符号。若是运算符，则作进一步判断：若是运算符，则作进一步判断：66第66页，此课件共171页哦若若读读出出运运算算符符的的优优先先级级大大于于运运算算符符栈栈栈栈顶顶运运算算符符的的优优先先级级，则则将将读读出出的的运运算算符符压压入入运运算算符符栈栈，并并依依次读下一

44、个符号。次读下一个符号。若若读读出出的的是是表表达达式式结结束束符符“；”，且且运运算算符符栈栈栈栈顶顶的的运运算算符符也也是是表表达达式式结结束束符符“；”，则则表表达达式式处处理结束，最后的计算结果在操作数栈的栈顶位置。理结束，最后的计算结果在操作数栈的栈顶位置。若若读读出出运运算算符符的的优优先先级级不不大大于于运运算算符符栈栈栈栈顶顶运运算算符符的的优优先先级级，则则从从操操作作数数栈栈连连续续退退出出两两个个操操作作数数，并并从从运运算算符符栈栈退退出出一一个个运运算算符符，然然后后作作相相应应的的运运算算（运运算算符符为为刚刚从从运运算算符符栈栈退退出出的的运运算算符符，运运算算对

45、对象象为为刚刚从从操操作作数数栈栈退退出出的的两两个个操操作作数数），并并将将运运算算结结果压入操作数栈。果压入操作数栈。67第67页，此课件共171页哦A AB*CB*CD/ED/E；68第68页，此课件共171页哦A AB*CB*CD/ED/E；69第69页，此课件共171页哦A AB*CB*CD/ED/E；70第70页，此课件共171页哦A AB*CB*CD/ED/E；71第71页，此课件共171页哦4.递归递归依次打印输出自然数依次打印输出自然数1 1到到n n的非递归算法的非递归算法 PROCEDURE WRT(n)PROCEDURE WRT(n)FOR k FOR k1 TO n

46、DO OUTPUT k1 TO n DO OUTPUT k RETURN RETURN依次打印输出自然数依次打印输出自然数1 1到到n n的递归算法的递归算法 PROCEDURE WRT(n)PROCEDURE WRT(n)IF IF (n0)(n0)THEN THEN WRT(n)WRT(n)；OUTPUT OUTPUT n n RETURN RETURN72第72页，此课件共171页哦#include stdio.h#include stdio.h wrt(int n)wrt(int n)if(n!if(n!0)0)wrt(n wrt(n1)1)；printf(%dnprintf(%dn，

47、n)n)；return return；73第73页，此课件共171页哦2.2.3 队列及其应用队列及其应用1.什么是队列什么是队列队队列列(equeue)(equeue)是是指指允允许许在在一一端端进进行行插插入入、而而在在另另一一端端进行删除的线性表。进行删除的线性表。数数据据结结构构中中的的队队列列与与生生活活中中的的“排排队队”极极为为相相似似，也也是是按按“先先来来先先解解决决”的的原原则则行行事事的的，并并且且既既不不允允许许“加塞加塞”，也不允许，也不允许“中途离队中途离队”。74第74页，此课件共171页哦关于队列的几个基本概念关于队列的几个基本概念允允许许插插入入的的一一端端称

48、称为为队队尾尾，用用尾尾指指针针(rearrear)指指向向队尾元素。队尾元素。允允许许删删除除的的一一端端称称为为排排头头(也也称称队队头头)，用用排排头头指指针针(frontfront)指向排头元素的前一个位置。指向排头元素的前一个位置。队队 列列 又又 称称 为为“先先 进进 先先 出出”(FIFOFIFOFirst First In In FirstFirst OutOut)或或“后后进进后后出出”(LILOLILOLast Last In In Last Last OutOut)的的线线性性表表，体体现现了了“先先来来先先服服务务”的的原则。原则。往往队队列列的的队队尾尾插插入入一一

49、个个元元素素称称为为入入队队运运算算，从从队队列的排头删除一个元素称为列的排头删除一个元素称为退队运算退队运算。75第75页，此课件共171页哦76第76页，此课件共171页哦2.循环队列及其运算循环队列及其运算77第77页，此课件共171页哦78第78页，此课件共171页哦队列空的条件为队列空的条件为 s s0 0队列满的条件为队列满的条件为 (s(s1)1)且且frontfrontrearrear79第79页，此课件共171页哦建立循环队列顺序存储空间建立循环队列顺序存储空间（即初始化循环队列顺序存储空间）（即初始化循环队列顺序存储空间）#include stdlib.h#include

50、stdlib.hvoid init_queue(qvoid init_queue(q，m m，frontfront，rearrear，s)s)ET *qET *q；int mint m，*frontfront，*rearrear，*s s；q qmalloc(m*sizeof(ET)malloc(m*sizeof(ET)；*frontfrontm m；*rearrearm m；*s s0 0；returnreturn；释放循环队列的顺序存储空间释放循环队列的顺序存储空间 free(q)free(q)；80第80页，此课件共171页哦(1)(1)入队运算入队运算PROCEDURE ADDCQ(Q