数据结构课件.ppt

1、课时安排,总学时数：80，其中上机实验16学时，讲授64学时。具体如下：,第一章 绪论,数据结构的形成背景： 二十世纪四十年代，电子数字计算机问世。起初，电子计算机仅仅应用于数值计算问题；近三十年来，电子计算机的发展异常迅猛，其应用范围也扩展到了非数值计算领域。为了编写一个“好”的程序，必须分析待处理的对象的特征及处理对象之间存在的关系。,本章内容,基本概念和术语,算法和算法分析,4,抽象数据类型的表示和实现,3,什么是数据结构,第一节 什么是数据结构,计算机解决一个具体问题时，大致需要经过下列几个步骤： 1 要从具体问题中抽象出一个适当的数学模型； 2 设计一个解此数学模型的算法（Algor

2、ithm）； 3 编出程序、进行测试、调整直至得到最终解答。 寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。 计算机算法与数据的结构密切相关，算法无不依附于具体的数据结构，数据结构直接关系到算法的选择和效率。,一 数据结构示例,数据结构示例A 线性表,数据结构示例B树,数据结构示例C图,求从v0（指定城市）到其余各顶点（其他各城市）的最短路径。,某地区有6个城市，一销售人员从指定城市到其他城市进行销售，如何以最短的路程到达其他某个城市？,直观定义：数据结构是研究程序设计中计算机操作的对象以及它们之间的关系和运算的一门学科。 “数据

3、结构”作为一门独立的课程在国外是从1968年才开始设立的。1968年美国唐欧克努特教授开创了数据结构的最初体系，他所著的计算机程序设计技巧第一卷基本算法是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。 “数据结构”在计算机科学中是一门综合性的专业基础课。是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。,二 数据结构定义及其发展历史与地位,三 数据结构要解决的问题,1 数值问题 例 已知：游泳池的长len和宽wide，求面积area 建模型： 问题涉及的对象： 游泳池的长len 宽wide，面积area； 对象之间的关系： area=lenwide,设计求解问题的方法 编程

4、 main ( ) int len, wide ,area ;scanf (“%d %d%n”, ,2 非数值问题 例 已知班级学生情况，如下表1_1，要求分班按入学成绩排列顺序。 表1_1： 学号 姓名 性别 出生日期 籍贯 入学成绩 所在班级 082001 杨润生 男 82/06/01 广州 561 00计算机1 082031 石磊 男 83/12/21 汕头 512 00计算机1 082053 李梅 女 83/02/23 阳江 532 00计算机2 082064 马耀先 男 82/07/12 广州 509 00计算机2,第二节 ：基本概念和术语,数据（data） 人们利用文字符号、数字符

5、号以及其他规定的符号对现实世界的事物及其活动所做的描述。在计算机科学中，数据的含义非常广泛，把一切能够输入到计算机中并被计算机程序处理的信息。 数据元素(data element) 是组成数据的基本单位，在程序中通常把它作为一个整体进行考虑和处理。 一般情况下，一个数据元素中含有若干个数据项（data item）。数据项是构成数据的最小单位。,数据对象（data object） 性质相同的数据元素的集合.例如: 所有的整数集合 数据结构（data structure） 相互之间存在一种或多种特定关系的数据元素的集合 数据元素相互之间的关系称为结构，而这种关系描述的是数据元素之间的逻辑关系，称为

6、数据的“逻辑结构”。图1.1表示的是数据逻辑结构的四种基本结构：,集合 线性结构 树型结构 图结构,图1-3,数据结构表示为： Data_Structure=( D, S ),例：编制一个事务管理的程序，管理学校科学研究课题小组的各项事务，首先要为程序的操作对象课题小组设计一个数据结构。假设每个小组由1个教师(T)、3个研究生(G)及16个本科生(S)组成，小组成员间的关系是：教师指导研究生，而由每个研究生指导一到两名本科生。,定义数据结构： Group=(P,R) 其中：P=T,G1,G2,G3,S11,S32 R=R1,R2 R1=|1|1=i=3, 1=j=2,注意：对每种数据结构，主要

7、讨论如下两方面的问题 1）数据的逻辑结构：数据结构的基本操作 2）数据的存储结构（物理结构）：数据结构基本操作的实现 数据的逻辑结构：从操作对象抽象出来的数学模型，描述数据元素之间的逻辑关系。 数据的物理结构：数据结构在计算机中的表示，又称为存储结构。,数据元素的存储方法 用二进制位（bit）的位串表示数据元素 如：(321)10 = (501)8 = (101000001)2 关系的存储方法:表示 的方法 两种存储结构：顺序存储结构与链式存储结构 注意：顺序存储结构中，逻辑上相邻的数据元素在物理上必然相邻；链式存储结构中，逻辑上相邻的数据元素在物理上不一定相邻.,假设有一组数据元素为（a1,

8、a2,.,an）, 设第一个元素a1的内存地址为LOC(a1)，而每个元素在计算机内占d个存贮单元,则第i个元素ai的地址为 LOC(ai)=LOC(a1)+(i-1)d (其中1in),顺序存储示例,数据类型 一个值的集合和定义在这个值集合上的一组操作的总称，是程序设计语言中各变量可取的数据种类。 一方面，在程序设计语言中，每一个数据都属于某种数据类型。 另一方面，在程序设计过程中，当需要引入某种新的数据结构时，总是借助编程语言所提供的数据类型来描述数据的存储结构。,抽象数据类型（abstract data type,ADT） 一个数学模型及定义在该模型上的一组操作。 不局限于系统已定义并实

9、现的类型，还包括用户在此基础上定义的新类型 用三元组表示：（D, S, P） D：数据对象； S：D上的关系集； P：对D的基本操作集,抽象数据类型三元组表示法格式： ADT 抽象数据类型名 数据对象： 数据关系： 基本操作： ADT抽象数据类型名 基本操作： 基本操作名（参数表） 初始条件： 操作结果：,1.3 抽象数据类型的表示与实现,预定义常量和类型 数据结构的表示用类型定义描述 基本操作的算法描述 赋值语句 选择语句 循环语句 结束语句 注释 逻辑运算约定,抽象数据类型Triplet的表示和实现 函数原型说明及实现 Status InitTriplet(Triplet /InitTri

10、plet,/销毁三元组 Status DestroyTriplet(Triplet /DestroyTriplet,Status Get(Triplet T,int i,Elemtype Get,Status Put(Triplet /Put,/若T的3个元素按升序排列，返回1，否则返回0 Status IsAsceding(Triplet T) return (T0=T1 ,/用e返回指向T的最大元素的值 Status Max(Triplet T,Elemtype /Max,/用e返回指向T的最小元素的值 Status Min(Triplet T,Elemtype /Min,1.4 算法和算

11、法分析,一 算法（algorithm） 1 什么是算法：是解决特定问题的方法，即对特定问题求解步骤的一种描述。 求两个正整数m，n中的最大数MAX的算法 （1）若 m n 则 max=m （2）若 m = n 则 max=n,例,2 算法的基本特征： 1）有穷性 对于任意一组合法输入值，在执行有穷步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成。 2）确定性 对于每种情况下所应执行的操作，在算法中有确切的规定，使算法的执行者或阅读者都能明确其含义及如何执行，并且在任何条件下，算法都只有一条执行路径（即：对于相同的输入只能得出相同的输出）,3）可行性 算法中的所有操作都必须足够基本，

12、并且都可以通过已经实现的基本操作运算有限次实现之。（如：a，b两数互换是基本操作，x变量自增不是） 4）有输入 有的算法表面上可以没有输入，实际上已被嵌入算法之中。（求100内的素数，只要给出一个参数100，而中间的值就已隐含在算法中） 5）有输出 一组与“输入”有确定关系的量值，是算法进行信息加工后得到的结果。,二 算法设计的要求,1)正确性 首先，算法应当满足以特定的“规格说明”方式给出的需求； 其次，对算法是否“正确”的理解可以有以下四个层次： (1)程序中不含语法错误 (2)程序对于几组输入数据能够得到满足要求的结果 (3)程序对于精心选择的、典型的、苛刻且带有刁难性的几组输入数据能够

13、得出满足要求的结果。（如：两数相除，就要考虑除数不等于的情况） (4)对于一切合法的输入数据都能得出满足要求的结果,2)可读性 3)健壮性 当输入的数据非法时，算法应恰当作出反映或进行响应处理; 处理出错的方法不应是中断程序的执行，而是返回一个表示错误或错误性质的值。 4)高效率与低存储量需求 效率指的是算法执行时间，存储量指的是算法执行过程中所需的最大存储空间，两者都与问题的规模有关。,三 算法效率的度量,1算法效率的衡量方法和准则 算法的时间效率是通过依据该算法编制的程序在计算机上运行所消耗的时间来度量的。度量一个程序的执行时间通常有两种方法： (1)事后统计的方法 缺陷：一是必须先运行依

14、据算法编制的程序；二是所得时间的统计量依赖于计算机的硬件、软件等环境因素，有时容易掩盖算法本身的优略。,(2)事前分析估算方法 程序在计算机上运行所消耗的时间与下列因素有关： 依据的算法选用何种策略； 问题的规模，即算法的时间效率与算法处理的数据个数n的关系。 书写算法的程序设计语言； 编译程序所产生的机器代码的质量； 机器执行指令的速度； 后三条和硬件软件相关，和算法无关,2. 时间复杂度 一个特定算法的“运行工作量”的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。 假如，随着问题规模n的增长，算法执行时间的增长率和f（n）的增长率相同，则可记作： T(n)=O

15、(f(n) 称T(n)为算法的时间复杂度。 f(n) : 基本操作重复执行的次数,如何估算时间的时间复杂度? 算法控制结构原操作（固有数据类型的操作） 每一个算法里都有很多原操作，只考虑随n 增长而增长的速度最快的，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量标准。 多数情况下它是最深层循环内的语句中的原操作，它的执行次数等于包含它的语句的频度。,语句的频度(frequency count)指的是该语句重复执行的次数。 例如： for (i=2;i=n;+i) for(j=2;j=i-1;+j) +x; aij=x; /基本操作 语句+x的执行次数关于n的增长率为n2 它是语句频度

16、表达式(n-1)(n-2)/2中增长最快的项。,例：设数组a和b在前边部分已赋值，求如下两个n阶矩阵相乘运算程序段的时间复杂度。 for(i=0;in;i+) for(j=0;jn;j+) cij=0; /基本语句1 for(k=0;kn;k+) cij=cij+aik*bkj; /基本语句2 解：设基本语句的执行次数为f(n)，有 f(n)= n2 + n3 因程序段的时间复杂度 T(n)=f(n)= n2 + n3 c* n3 =O(n3 )。,时间复杂度的等级 O（1） O（log n） O（n） O（nlog n) O (n2) O (nk） O（Xn ）,常见函数的增长率,3. 算法

17、的存储空间需求 空间复杂度（space complexity）作为算法所需存 储空间的量度，记作 S(n)=O(f(n) 其中n作为问题的规模（或大小）。若额外空间相对 输入数据量来说是常数，则称此算法为原地工作。,第二章：线性表,线性表的顺序表示和实现,线性表的类型定义,线性表的链式表示和实现,第一节,第二节,第三节,本章主要讲解内容,线性结构,是一个数据元素的有序（次序）集合。 具有四个基本特征： 1集合中必存在唯一的一个第一元素； 2集合中必存在唯一的一个最后元素； 3除最后元素之外，其它数据元素均有唯一的后继； 4除第一元素之外，其它数据元素均有唯一的前驱。,第一节 线性表的类型定义,

18、一：什么是线性表 1 概念：线性表是由n（n0）个类型相同的数据元素组成的有限序列。 2 表示： L=( a1, a2,.,ai-1,ai,ai+1,.,an) 其中：L为线性表名称，习惯用大写书写； ai 为组成该线性表的数据元素，习惯用小写书写，称i为ai 在线性表中的位序。 3 长度：序列中数据元素的个数 n 定义为线性表的表长 4 空表：n=0 时的线性表被称为空表。,5 线性表的例子： L1=(1,2,3,4,5); L2=(“a”,”b”,”c”,”d”); L3=(“张晓芳”，“李晓”，“陈琳”)； L4=(“student1”,”student2”, ”student3”) 这

19、里student1,student2,student3是P18学生健康情况表格中个三行信息。,二：线性表的抽象数据类型的定义,ADT List 数据对象：Dai | ai ElemSet, i=1,2,.,n, n0 数据关系：R1 | ai-1,aiD, i=2,.,n 基本操作： InitList( +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); ListI

20、nsert(Lc, +k, bj); / merge_list,练习,已知一个非纯集合B，试构造一个纯集合A，使A中只包含B中所有值各不相同的数据元素。,B,A,a,e,f,h,k,n,步骤： 假设集合存储为表Lb，集合存储为La 从Lb中依次取出元素，并赋值给e 判断e是否在La表中存在，如果存在继续从Lb表中取数 若不存在，则将e的值插入到La表中,什么是线性表的顺序存储结构？ 是指用一组连续的存储单元依次存储线性表中的每个数据元素。 线性表的顺序存储过程： 先在内存中为线性表申请一片连续的存储空间，该空间不能小于线性表的长度；然后让线性表的第一个元素存放在这个连续存储空间的开始位置以此类

21、推，所有的元素按逻辑顺序依次往下存放。,第二节：线性表的顺序存储结构,依据顺序表的存储结构特性，可以很容易确定顺序表中各个元素存储位置之间的关系。 d为该线性表的基址，l为每个数据元素所占据的存储单元数目。 位置的计算公式为： LOC(ai+1)=LOC(a1)+(i-1)*L,线性表（a1,a2,a3,ai,an）的顺序存储结构,顺序存储结构的特点,（1）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构（物理结构）一致。 （2）在访问线性表时，可以利用上述给出的数学公式，快速地计算出任何一个数据元素的存储地址，可以随机存储线性表中各个元素。,线性表的

22、顺序存储结构的描述,C语言中线性表的动态分配顺序存储结构表示 #define LIST_INIT_SIZE 100 /线性表存储空间的初始分配长度 #define LISTINCREMENT 10 /线性表存储空间的分配增量 typedef struct EntryType *item; /存储空间基地 int length; /线性表的当前长度 int listsize; /当前分配的存储容量（以sizeof(ElemType)为单位） SQ_LIST；,典型操作的算法实现,1. 初始化线性表L Status InitList(SQ_LIST ,2. 插入操作 在线性表的第i-1个数据元素和

23、第i个数据元素之间插入一个新的数据元素，使长度为n的线性表 (a1,a2,ai-1,ai,an) 变成长度为n+1的线性表 (a1,a2,ai-1,b,ai,an) 数据元素ai-1和ai之间的逻辑关系发生了变化。 注意：顺序存储结构的特性是逻辑关系用物理关系表示，即物理相邻反应逻辑相邻，因而需要移动数据元素。,插入操作的示例,插入25,插入操作之前,插入操作之后,插入算法,Status ListInsert_Sq(SqList ,3. 删除操作 删除线性表中第i个数据元素，使长度为n的线性表 (a1,a2,ai-1,ai, ai+1,an) 变成长度为n-1的线性表 (a1,a2,ai-1,

24、ai+1,an) 数据元素ai-1,ai,和 ai+1之间的逻辑关系发生了变化，同样也需要移动数据元素来反应这种变化。,删除数据元素示例,删除24,删除操作之前,删除操作之后,Status ListDelete_Sq(SqList ,删除算法,插入操作与删除操作的时间复杂度分析,顺序存储结构的插入与删除操作，其时间主要耗费在移动元素，移动元素个数与取决于插入或删除元素的位置。,插入操作所需移动元素的次数期望（平均值）：,删除操作所需移动元素的次数期望（平均值）：,两个概率值分别为：,代入以上两个期望得：,因而，插入和删除操作的时间复杂度都为,关于例2-1,例2-2（顺序存储结构的线性表）,顺序

25、表中的“求表长”和“取第i个数据元素”的时间复杂度均为O(1)，又这两个例子中进行的“插入”操作，均在表尾进行，则不需要移动元素。例2-1的算法执行时间主要取决于查找函数LocateElem的执行时间。 基本操作是“进行两个元素之间的比较”，若L中存在和e相同的元素ai，则比较次数为i（大于等于1小于等于L.length）,否则为L.length，即算法的时间复杂度为O(L.length)，因此，对于顺序表La和Lb而言，合并的时间复杂度为O(La.length*Lb.length)。,int LocateElem_Sq(SqList L,ElemType e, Status(*compare

26、)(ElemType,ElemType) /在顺序线性表L中查找第一个与e满足compare()的元素的位序 i=1; /i的初始值为第一个位序 p=L.elem; /第一个元素的存储位置 while(i=L.length ,查找函数,合并操作,void MergeList_sq(SqList La,SqList Lb,SqList ,While(papa_last /插入Lb的剩余元素 /MergeList_sq,第三节：线性表的链式表示和实现,线性表顺序存储结构的特点: 一种简单、方便的存储方式。要求线性表的数据元素依次存放在连续的存储单元中，从而利用数据元素的存储顺序表示相应的逻辑顺序，

27、即静态存储形式。 优点：随机存取数据元素； 缺点：插入或删除等操作需要移动大量数据元素，同时要求存储空间是连续的。 线性表的链式存储： 逻辑上相邻的数据元素在物理位置上不要求相邻。可以克服顺序存储结构的缺点，同时也是去了顺序存储的优点。,2.3.1 线性链表,链式存储：用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。 为了反映数据元素之间的逻辑关系，对于每个数据元素不仅要表示它的具体内容，还要附加一个表示它的直接后继元素存储位置的信息。 例如数据元素ai除了存储本身的信息外，还要存储一个指示其直接后续的信息。这两部分信息组成数据元素ai的存储映像，称为结点。 存储数据元素

28、信息的域称为数据域；存储直接后续的位置的域称为指针域。,1 什么是链式存储,2 单链表图形描述形式,线性表（ZHAN,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG）的链式表示,头指针H,31,链表的逻辑状态？,head是头指针，它指向单链表中的第一个结点，这是单链表操作的入口点。 最后一个结点没有直接后继结点，所以，它的指针域放入一个特殊的值NULL。NULL值在图示中常用（）符号表示。,3 链式存储结构的特点,线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致。 在对线性表操作时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，这样就会造成寻找第一个

29、结点和寻找最后一个结点所花费的时间不等，具有这种特点的存取方式被称为顺序存取方式。,4 单链表的存储结构,typedef struct LNode ElemType data; struct LNode *next; LNode, *LinkList;,在单链表的第一个节点之前附设一个结点，称为头结点，其指针域存储指向第一个结点的指针，数据域可以不存储任何信息，也可以存储链表长度等附加信息。,L,非空表,空表,线性表的顺序存储结构中，相邻的两个结点的存储位置也具有相邻性； 在单链表中任何两个元素的存储位置没有固定的联系，但每个元素的存储位置都包含在其直接前驱结点的信息中，因而要取得第个数据元素

30、必须从头指针出发寻找，可见单链表不是随机存取的。,（1）取单链表中的一个元素,Status GetElem_L(LinkList L,int i,ElemType ,（2）插入操作与删除操作,插入操作：首先生成一个数据域为x的结点；然后插入在单链表。只需要修改指针，不需要移动数据元素。,具体算法描述,Status ListInsert_L(LinkList ,Status ListDelete_L(LINKLIST ,void CreateList_L(LinkList ,（3）从表尾逆向建立单链表,（4）合并两个有序链表,void MergeList_L(LinkList ,2.3.2 循环

31、链表,循环链表（circular linked list）就是带循环的链表，表中最后一个结点的指针域指向头结点。显然，从表中任一结点出发，均可找到其他结点。,如何判断一个循环链表是空表呢？,如何判断循环链表到了最后一个结点（尾结点）呢？,H-next=H;,p-next=H;,尾指针,尾指针，即指向链表的最后一个结点的指针。 循环链表中，有时不设立头指针，而设立尾指针，这样可使线性表的某些操作简化，如合并两个线性表，仅需改变两个指针（哪两个？）即可。,2.3.3 双向链表,单链表中，NextElem的执行时间为O(1)，而PriorElem的执行时间为O(n)，为了克服后者执行时间上的缺陷，采

32、用双向链表。 双向链表有两个指针域，一个指向直接后继，另一个指向直接前驱。 其在C语言中的描述如下： typedef struct DuLNode ElemType data; struct DuLNode *prior; struct DuLNode *next; DuLNode,*DuLinkList;,双向链表的插入与删除,可见，双向链表中插入和删除操作需要修改两个方向上的指针，但是类似与ListLength、GetElem等只需涉及一个方向上的操作，与单链表的操作一样。,Status ListInsert_Dul(DuLinkList ,Status ListDelete_DuL(Du

33、LinkList ,第三章 栈和队列,本章主要讲解内容,栈和队列的总体认识,数据结构角度：二者也是线性表，只是它们的操作收到限制； 数据类型角度：二者的数据类型与线性表的数据类型相差甚远。,3.1 栈,什么是栈以及栈的相关术语 栈：是限定在表尾插入和删除的线性表。 栈顶：表尾端称为栈顶（允许插入和删除操作）。 栈底：表头端称为栈底（不允许插入和删除操作）。 空栈：不含元素的空表称为空栈。 栈的表示： S=(a1,a2,an),栈的图形表示,通常称往栈顶插入元素的操作为“入栈” 称删除栈顶元素的操作为“出栈”。 a1为栈底元素，an为栈顶元素； 栈遵循后进先出（LIFO）的原则,说明,栈S=(a

34、1,a2,an),栈S=(a1,a2,an),栈的抽象数据类型定义,数据关系：R1 | ai-1, ai D, i=2,.,n 约定an端为栈顶， a1端为栈底。,数据对象：D ai| ai ElemSet, i=1,2,.,n, n0 ,基本操作：InitStack( / 存储空间基址 SElemType *top; / 栈顶指针 int stacksize; / 当前允许的最大存储空间以元素为单位 Stack; 若base的值为NULL，则表示栈不存在。,base=top时，为空栈； base一直指向栈底元素，而top则指向非空栈的栈顶元素的下一个位置。,注意,顺序栈的模块说明,#defi

35、ne STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct SElemType *base; / 基址 SElemType *top; / 栈顶指针 int stacksize; / 当前允许的最大存储空间以元素为单位 Stack;,Status InitStack (SqStack SLink S; / 栈顶指针 Slink next; Stack;,3.2 栈的应用举例,3.2.1 数制转换,数制转换 ：(1348)10 = (2504)8 原理 ：N=(N/d)*d+N%d 过程：,具体算法描述,void convers

36、ion () / 输入的任意一个非负十进制整数，打印输出其八进制数InitStack(S); / 构造空栈scanf(“%d”,N); / 输入一个十进制数 while(N)Push(S,N % 8);/ “余数”入栈N = N/8;/ 非零“商”继续运算 while (!StackEmpty(S)/ 和求余所得相逆的顺序输出八进制的各位数Pop(S,e);printf(“%d”,e); ,将十进制数转换成二进制数呢？ 将是进制数转换成十六进制数呢？ 将十进制数转换成d(非十的自然数)进制数呢？,思考,3.2.2 括号匹配问题,考虑下列括号序列 ( ) 1 2 3 4 5 6 7 8 是合法的

37、吗？ ( ) 1 2 3 4 5 7 6 8 合法吗？,每读入一个括号，若是右括号，则要么与栈顶括号匹配，要么是非法的；若是左括号，则作为新的括号入栈，作为新的最需要满足的。,如何判断是否匹配呢？,具体描述,bool BracketsLegitimate() R=True; initStack(s); scanf(“%c”,ch); switch(ch) case(,:push(S,ch);break; case),: pop(S,e); if(!matchB(ch,e) ) R=False; break; return R; ,栈空条件：s. top =s. base 此时不能出栈 栈满条件

38、：s.top-s.base=s.stacksize 进栈操作：*s.top+=e; 或*s.top=e; s.top+; 退栈操作：e=*-s.top； 或s.top-； e=*s.top； 当栈满时再做进栈运算必定产生空间溢出， 简称“上溢”; 当栈空时再做退栈运算也将产生溢出，简 称“下溢”。,几点说明,3.2.3 行编辑程序,编辑时，若输入错误如何更改？ 紧跟着输入“#”，可以使上一个字符无效，即等价于没有输入上一个字符； 紧跟着输入“”，可以当前行无效。 考虑下面的字符行： Whli#ilr#e(s#*s) adelixnhkabg#cdefgh# 实际有效的是？,具体算法描述,voi

39、d LineEdit() InitStack(S); ch=getchar(); while(ch!=EOF) while(ch!=EOF ,出口,入口,3.2.4 迷宫,通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止 如果所有可能的通路都试探过，还是不能走到终点，那就说明该迷宫不存在从起点到终点的通道,所谓“下一位置”指的是“当前位置”四周四个方向（东、南、西、北）上相邻的方块。 假设以栈S记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。 “纳入路径”的操作即为“当前

40、位置入栈”； “从当前路径上删除前一通道块”的操作即为“出栈”。,do若当前位置可通， 则将当前位置插入栈顶； / 纳入路径 若该位置是出口位置，则算法结束； / 此时栈中存放的是一条从入口位置到出口位置的路径否则切换当前位置的东邻方块为新的当前位置； 否则 若栈不空且栈顶位置尚有其他方向未被探索， 则设定新的当前位置为: 沿顺时针方向旋转找到的栈顶位置的下一相邻块；若栈不空但栈顶位置的四周均不可通， 则 删去栈顶位置； / 从路径中删去该通道块若栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈空； while (栈不空)；,算法描述,typedef struct int

41、ord; /通道块在路径上的“序号” PosType seat; /通道块在迷宫中的“坐标位置” int di; /下一通道块的方向 SElemType;,Status MazePath(MazeType maze,PosType start,PosType end) initStack(s); curpos=start; /设定“当前位置”为“入口位置” curstep=1; /探索第一步 do if(Pass(rurpos) FootPrint(curpos);/留下轨迹 e=(curstep,curpos,1); Push(S,e); /加入路径 if(curpos=end) retur

42、n True;/终点，结束 curpos=NextPos(curpos,1); /下一个位置是当前位置的东 curstep+; /探索下一步 ,else if(!StackEmpty(S) Pop(S,e); while(e,di=4/if /if /else,while(!StackEmpty(S); return False; ,3.2.5 表达式求值问题,任何一个表达式都由操作数、操作符及界限符组成 Exp = S1 + OP + S2 称 OP + S1 + S2 为表达式的前缀表示法（简称前缀式） 称 S1 + OP + S2 为表达式的中缀表示法（简称中缀式） 称 S1 + S2

43、+ OP 为表达式的后缀表示法（简称后缀式）,OP包括运算符和界限符。 定义两个栈，分别存储操作数与OP 四则运算法则 定义结束符“#”，在表达式前虚设一个“#”，显然当“#”与“#”相遇，表示表达式结束； “（”与“）”相遇时，表示括号内操作完成。,分析,首先置操作数栈为空栈，表达式起始符为虚设的“#”，设其为运算符的栈底元素； 依次读入表达式中每个字符，若为操作数，则操作数入栈；若为运算符，则与运算符栈的栈顶元素进行优先级比较做相应操作，直至遇到“#”,基本思想,算法描述,OperandType EvaluateExpression() initStack(OPTR); Push(OPTR

44、,#); initStack(OPND); c=getchar(); while(c！=#|GetTop(OPTR)!=#) if(!In(c,OP) Push(OPND,c); c=getchar(); else switch(Precede(GetTop(OPTR),c) case:Pop(OPTR,theta);Pop(OPND,b); Pop(OPND,a); Operate(a, theta,b);break;/switch /while return GetTop(OPND);,过程的嵌套调用,若让元素1，2，3依次进栈，则出栈次序不可能出现（ ）种情况。 A3，2，1 B2，1，

45、3 C3，1，2 D1，3，2 对于给定的结点序列abcdef，规定进栈只能从序列的左端开始。通过栈的操作，能得到的序列为（ ）。 Aabcfed Bcabfed Cabcfde Dcbafde,思考,设一个栈的输入序列为A、B、C、D，则借助一个栈所能得到的输出序列不可能是（ ）。 AABCD BDCBA CACDB DDABC 栈的插入与删除操作在（ ）进行。 A栈顶B栈底 C任意位置D指定位置,栈结构通常采用的两种存储结构是_和_。 中缀算术表达式5+6/(23-(6+15)*8所对应的后缀算术表达式为_,循环链表练习,1 设单链表中结点的结构为 typedef struct node

46、ElemType data; struct node *link; ListNode; (1)已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行下列哪个操作？ A. s-link=p;p-link=s; B. s-link=p-link;p-link=s; C. s-link=p-link;p=s; D. p-link=s;s-link=p;,(2)非空的循环单链表first的尾结点（由p所指向）满足哪个？ A. p-link=NULL; B. p=NULL; C. p-link=first; D. p=first;,3.4 队列,一 队列的抽象数据类型定义 1 什么是队列 （1

47、）队列，也是一种特殊的线形表，只允许在一端进行插入操作，另一端进行删除操作。 （2）允许插入的一端为队尾（rear/tail），允许删除的一端为对头（front） （3）操作遵循的原则是“先进先出”（FIFO）。,2 队列例子,出队列,入队列,对头,对尾,说明：队列中的对头与队尾分别为a1和an； 操作过程中遵循FIFO规则；,打印机队列管理： 在一台打印机共享使时，任何时刻它只能处理一个用户的打印请求。打印任务的组织就用一个队列来组织（先请求的，先处理）。 当用户发出打印请求时，把打印任务入队； 当打印机空闲时，从打印队列中出队一个任务。 与此类似，打电话电话，网上在线等等。,3 队列的抽象

48、数据类型定义,ADT Queue 数据对象：Dai | ai ElemSet, i=1,2,.,n, n0数据关系：R1 | ai-1, ai D, i=2,.,n 约定其中a1端为队列头，an端为队列尾。基本操作： InitQueue( struct QNode *next; QNode,*QueuePtr; typedef SLink QueuePtr; typedef structQueuePtr front; / 队列的头指针QueuePtr rear; / 队列的尾指针 LinkQueue; / 链队列,（1）构建空队,Status InitQueue (LinkQueue ,思考：

49、Q.rear指针指向何处？,（2）注销队列,Status DestroyQueue(LinkQueue ,(3) 插入元素（入队）,Status EnQueue(LinkQueue ,(4)删除元素（出队）,Status DeQueue(LinkQueue ,（5）队列应用,要求：编写一个打印二项式系数表（即杨辉三角）的算法 假设队列中已存有第 k 行的计算结果，并为了计算方便，在两行之间添加一个0作为行界值，则在计算第 k+1 行之前，头指针正指向第 k 行的0，而尾元素为第 k+1 行的0,队列的主要算法思路,while (e!=0) do DeQueue(Q, s); / s 为二项式系

50、数表第 k 行中左上方的值GetHead(Q, e); / e 为二项式系数表第 k 行中右上方的值printf(e)；/ 输出 e 的值 EnQueue(Q, s+e); / 计算所得第 k+1 行的值入队列,1 栈和队列都是（）。 A链式存储的线性结构 B顺序存储的线性结构 C限制存取位置的线性结构 D限制存取位置的非线性结构 2 一个队列的入队序列是a、b、c、d，则队列的输出序列为_。,3 队列通常采用两种存储结构是( )。 A顺序存储结构和链表存储结构 B散列方式和索引方式C链表存储结构和数组 D线性存储结构和非线性存储结构,三 队列的顺序存储,用一片连续的地址空间存放队列的元素，与

51、顺序表，顺序栈一样。,0,1,2,3,4,栈的顺序存储图,队列中，初始化时，front=rear=0; 入队一个元素，rear增1； 出队一个元素，front增1。 注意，这里1的单位是元素类型。,注销队列,Status DestroyQueue(LinkQueue ,存在问题： 设数组维数为M，则 当front=-1,rear=M-1时，再有元素入队发生溢出真溢出； 当front！-1,rear=M-1时，再有元素入队发生溢出假溢出。 解决方案： 队头固定，每次出队剩余元素向下移动浪费时间。 引入循环队列，把队列设想成环形。,1 不能用动态分配的一维数组来实现循环队列，初始化时必须设定一个最

52、大队列长度。 2 解决 Q.front=Q.rear不能判别队列“空”还是“满”的其他办法： （1）使用一个计数器记录队列中元素的总数（即队列长度）。 （2）设一个标志变量以区别队列是空或满。,说明,1 存储队列的数组被当作首尾相接的表处理。 2 队头、队尾指针加1时从maxSize -1直接进到0，可用语言的取模(余数)运算实现。 队头指针进1: Q.front = (Q.front + 1)% MAXSIZE； 队尾指针进1: Q.rear = (Q.rear + 1)% MAXSIZE; 4 队列初始化：Q.front = Q.rear = 0; 5 队空条件：Q.front = Q.r

53、ear; 6 队满条件：(Q.rear + 1) % MAXSIZE = Q.front 7 队列长度：(Q.rear-Q.front+MAXSIZE)%MAXSIZE,（二）循环队列模块说明,#define MAXQSIZE 100 typedef struct QElemType *base; int front; int rear; SqQueue;,1 初始化,Status InitQueue (SqQueue ,2 循环队列长度,int QueueLength(SqQueue Q) len=Q.rear- Q.front+MAXQSIZE)%MAXQSIZE; return len;

54、 思考：为什么要+MAXQSIZE？ Q.rear-Q.front不可以吗？,3 入循环队列,Status EnQueue (SqQueue ,4 出循环队列,Status DeQueue(SqQueue ,第三章小结,一：栈 1：性质 2：两个重要位置 3：顺序、链式结构图 4：判断栈空、栈满的条件 5：三个重要操作（取栈顶元素、入栈、出栈），注意每种操作的特殊情况。,1 性质 后进先出 相关题目 （1）一个入栈顺序为a,b,c,d,e，则栈的输出不可能是哪个序列_. A a,b,c,d,e B d,e,c,b,a C d,c,e,a,b D e,d,c,b,a,（2）若一个栈的输入序列为1

55、，2，3，.，n，输出序列第一个为n，则第k个输出元素为_ A k B n-k-1 C n-k+1 D 不确定 （3）栈是限定在_一端进行插入或者删除的线性表。,2 栈的两个主要位置： 栈底和栈顶 只能在栈顶位置进行插入和删除，不能在栈底进行任何操作（若栈不是空栈或仅含有一个元素的栈。）,3 栈的顺序、链式表示 栈是操作受限的线性表，因而也有两种存储结构顺序结构和链式结构，分别是循序栈和链式栈。 其图形如下：,4 判断栈空的条件是： base=top； 判断栈满的条件是： top-base=stacksize; 5 取栈顶元素与出栈要考虑栈是否为空栈；入栈时要考虑栈是否已满。 取栈顶元素操作，

56、栈本身不发生任何变化；入栈操作栈顶上移，栈元素个数增一；出栈操作栈顶下移，栈元素个数减一。,二 队列 1：性质 2：两个重要位置 3：顺序、链式结构图 4：判断队空的条件 5：两个重要操作（入队、出队），注意每种操作的特殊情况。 6：循环队列 三：两端队列不同于队列与栈的线性表。,1 性质 先进先出FIFO 2 两个重要位置 队头队尾 队头只能进行出队操作，队尾只能进行出队操作。 3 队的结构图如下：,出队列,入队列,对头,对尾,空队列,4 判断队空的条件 队头=队尾=0； front=rear; 5 出队操作中，需要注意队是否为空队。 6 循环队列中性质、结构图、何时为空、满，以及其插入和删

57、除操作。 三 双端队列可以在队列的队头、队尾进行插入和删除操作。,第三章相关练习,1 判断一个队列Q（最多有n个元素）为空的条件是_ A Q-rear-Q-front=n B Q-rear-Q-front+1=n C Q-front=Q-rear D Q-front=A-rear+1,2 在一个链队列中，假定front和rear分别为头指针和为指针，则删除一个结点的操作是_ A front=front-next B rear=rea-next C rear-next=front D front-next=rear,3 在一个链队列中，假定front和rear分别为头指针和为指针，则插入结点*S的操作是_ A front=front-next B S-next=rear;rear=S C rear-next=S;rear=S D S-next=front;front=S,若一个栈的输入序列为1,2,3,n，输出序列的第一