数据结构专升本复习ppt课件.ppt

《数据结构专升本复习ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据结构专升本复习ppt课件.ppt（287页珍藏版）》请在三一办公上搜索。

1、数据结构,第一章,数据的三个层次：数据、数据元素、数据项数据结构的概念：定义、逻辑结构、物理(存储)结构理解数据类型、抽象数据类型的概念。 算法的概念 (算法特性，算法设计要求)理解时间复杂度、空间复杂度的概念。,数据 是对客观事物的符号表示。,数据结构相关的基本概念,在计算机科学中其含义是指所有能够输入到计算机中并被计算机程序处理的符号集合。,基本概念和术语,数据元素 是数据集合中的一个实体，是计算机程序中加工处理的基本单位。有两类数据元素：一类是不可分割的原子型数据元素，如：整数5，字符 N 等；另一类是由多个款项构成的数据元素，其中每个款项被称为一个数据项。例如描述一个学生的信息的数据元

2、素可由下列个数据项组成。,数据结构 简单地说，就是相互之间存在一种或多种特定关系的数据元素的集合。,数据结构的形式定义为：DataStructures= ( D, S )其中：D是数据元素的有限集，S是D上关系的有限集。,常见的存储结构 顺序存储结构：特点是借助于数据元素的相对存储位置来表示数据元素之间的逻辑结构； 链式存储结构：特点是借助于指示数据元素地址的指针表示数据元素之间的逻辑结构。,数据类型和抽象数据类型,数据类型是一个“值”的集合和定义在此集合上的“一组操作”的总称。 例：C语言中的整型，其内涵为一定范围的自然数集合，及定义在该集合上的加减乘除及取模、比较大小操作。而实型则无取模操

3、作。当然整型也不需四舍五入。,抽象数据类型（Abstract Data Type 简称 ADT）是指一个数学模型以及定义在此数学模型上的一组操作。 例如，矩阵的抽象数据类型定义为，矩阵是一个由 m n 个数排成 m 行 n 列的表，它可以进行初等变换、相加、相乘、求逆、等运算。 抽象数据类型的形式描述为ADT = ( D，S，P )其中：D 是数据对象，S 是 D 上的关系集，P 是 D 的基本操作集。,一、算法定义 算法（Algorithm）：是对特定问题求解步骤的一种描述，是由若干条指令组成的有限序列，其中每一条指令表示一个或多个操作。它应该满足下列五个重要特性： 1、有穷性 一个算法必须

4、总是在执行有穷步之后结束，且每一步都在有穷时间内完成。 2、确定性 算法中每一条指令必须有确切的含义，且执行路径唯一。即对于相同的输入只能得出相同的输出。 3、可行性 算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。 4、输入 一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集合。 5、输出 一个算法有一个或多个的输出，这些输出同输入有着某些特定关系的量。,1.2 算法描述,二、算法设计的要求： 1、正确性 算法应满足具体问题的需求。通常算法的正确性可分为四个层次： a.程序不含语法错误; b.程序对于几组输入数据能够得出满足规格说明要求的结果; c.程序对于精心选

5、择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果; d.程序对于一切合法的输入数据都能产生满足规格说明要求的结果。一般情况下，通常以第c层意义的正确性作为衡量一个程序是否合格的标准。,二、算法设计的要求： 2、可读性 算法主要是为了人的阅读与交流，其次才是机器执行。可读性好有助于人对算法的理解，晦涩难懂的程序易于隐藏较多错误难以调试和修改。 3、健壮性 当输入数据非法时，算法也能适当地作出反应或进行处理，而不会产生莫明其妙的输出结果。 4、效率与低存储需求,举例问题：按从小到大的顺序重新排列x，y，z三个数值的内容。算法：（1）输入x，y，z三个数值；（2）从三个数值中挑

6、选出最小者并换到x中；（3）从y，z中挑选出较小者并换到y中；（4）输出排序后的结果。,三、算法复杂性的概念 确切地说，算法的复杂性是运行算法所需要的计算机资源的量。 需要的时间资源的量称为时间复杂性 需要的空间资源的量称为空间复杂性,*在算法分析中，通常所说的找到了时间复杂性的级别，是指找到了同样级别的最简单的函数。如：307 n2、 n2/2、 n2 都是同一级别的函数，最简单的函数是n2 。所以， 307 n2、 n2/2、 n2 的级别都是O(n2 ) 。 f、g同级别：满足： f=O(g) 且 g=O(f),例、for(i=1;i=n;+i) for(j=1;j=n;+j) cij=

7、0; for(k=1;k=n;+k) cij+=aik*bkj; 由于是一个三重循环，每个循环从1到n，则总次数为: nnn=n3,频度：是指该语句重复执行的次数例、 +x;s=0; 将x自增看成是基本操作，则语句频度为，即时间复杂度为(1); 如果将s=0也看成是基本操作，则语句频度为，其时间复杂度仍为(1)，即常量阶。,例、for(i=1;i=n;+i) +x; s+=x; 。,课堂练习：求该程序的语句频度及时间复杂度1、 for(i=2;i=n;+i) for(j=2;j=i-1;+j) +x; aij=x; ,解答：语句频度为： 1+2+3+n-2 =(1+n-2) (n-2)/2 =

8、(n-1)(n-2)/2 =n2/2-3n/2+1 时间复杂度为O(n2) 即此算法的时间复杂度为平方阶。,第二章,1 、理解 ADT 表的概念及基本运算。 2 、掌握表的顺序存储结构及其运算的实现。 3 、掌握表的链接存储结构及其运算的实现。 4 、理解单链表、循环链表、双向链表的特点。,ADT 表,线性结构：结构中的数据元素之间存在一个对一个的关系。在数据元素的非空有限集中，（1）存在唯一的一个被称做“第一个”的数据元素；（2）存在唯一的一个被称做“最后一个”的数据元素；（3）除第一个之外，集合中的每个数据元素均只有一个前驱；（4）除最后一个之外，集合中每个数据元素均只有一个后继。,举例

9、La=（34，89，765，12，90，-34，22） 数据元素类型为int。 Ls=(Hello,World, China, Welcome) 数据元素类型为string。 Lb=(book1,book2,.,book100) 数据元素类型为下列所示的结构类型： struct bookinfo int No; /图书编号 char *name; /图书名称 char *author; /作者名称 .; ,线性表的基本操作线性表初始化：Init_List(L) 求线性表的长度：Length_List(L) 取表元：Get_List(L,i)按值查找：Locate_List(L,x) 插入操作：

10、Insert_List(L,i,x) 删除操作：Delete_List(L,i),线性表的顺序存储结构,线性表的顺序存储结构 线性表的顺序存储结构是指用一组连续的存储单元依次存储线性表中的每个数据元素。如下图2-1所示：,图2-1 线性表顺序存储结构示意图,其中，L为每个数据元素所占据的存储单元数目。 相邻两个数据元素的存储位置计算公式 LOC(ai+1)=LOC(ai)+L 线性表中任意一个数据元素的存储位置的计算公式为： LOC(ai+1)=LOC(a1)+(i)*L,顺序存储结构的特点 （1）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构（物理

11、结构）一致； （2）在访问线性表时，可以利用上述给出的数学公式，快速地计算出任何一个数据元素的存储地址。因此，我们可以粗略地认为，访问每个数据元素所花费的时间相等。这种存取元素的方法被称为随机存取法，使用这种存取方法的存储结构被称为随机存储结构。,在C语言中，实现线性表的顺序存储结构的类型定义 #define MAXSIZE 100 /线性表的最大长度 typedef struct datatype dataMAXSIZE; int last; SeqList;,2.2.2 典型操作的算法实现初始化线性表LSeqList *init_SeqList( ) SeqList *L; L=mallo

12、c(sizeof(SeqList); L-last=-1; return L; ,2.在线性表L中第i个数据元素之前插入数据元素Xint Insert_SeqList(SeqList *L，int i，datatype x) int j; if (L-last=MAXSIZE1) printf(表满); return(-1); /*表空间已满，不能插入*/ if (iL-last+2)/*检查插入位置的正确性*/ printf(位置错);return(0); for(j=L-last;j=i-1;j-) L-dataj+1=L-dataj; /* 结点移动 */ L-datai-1=x;/*新

13、元素插入*/ L-last+; /*last仍指向最后元素*/ return (1);/*插入成功，返回*/ ,3. 删除操作int Delete_SeqList(SeqList *L;int i) int j; if(iL-last+1) /*检查空表及删除位置的合法性*/ printf (不存在第i个元素); return(0); for(j=i;jlast;j+) L-dataj-1=L-dataj; /*向上移动*/ L-last-; return(1); /*删除成功*/ ,在线性表L中检索值为X的数据元素int Location_SeqList(SeqList *L, dataty

14、pe x) int i=0; while(idatai!= x) i+; if (iL-last) return -1; else return i; /*返回的是存储位置*/ ,插入算法的分析 假设线性表中含有n个数据元素，在进行插入操作时，若假定在n+1个位置上插入元素的可能性均等，则平均移动元素的个数为：,删除算法的分析 在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为： 分析结论 顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑。,线性表的链式存储结构,

15、链表的结点定义 链表的建立 链表的常用的操作模式指 针搜索 链表插入、删除运算 一些特殊的链表,线性表的链式存储结构,线性表链式存储时结点结构,有关结点数据,后继结点位置信息,数据域 指针域,线性表的链式存储结构（单链表）,.,head,head,头结点,首结点,首结点,链表结点的定义,struct node elemtp data; struct node *next; ; typedef struct node *pointer, *lklist;lklist与pointer并无性质上的区别。通常用lklist来说明链表头指针的类型，而用pointer来说明定位指针或搜索指针的类型,链表的

16、基本操作算法,单链表的初始化 lklist initiate(lklist h) malloc(h); h-next=0; return h; 单链表的length函数 length(lklist h) k=0;p=h-next; while (p!=0) k=k+1; p=p-next return k; ,Setup1图解 malloc(head);p=head;,head,p,Setup1图解 malloc(q); p-next=q;p=q,head,q,p,Setup1图解 malloc(q); p-next=q;p=q,head,q,p,链表的建立（带表头结点）,lklist set

17、up1 (lklist head ) malloc(head) ; p=head; scanf(x); while (x!=somevalue) malloc(q) ; q-data=x; p-next=q; p=q; scanf(x); ; p-next=0; return(head); ;,Setup2图解 malloc(head);head-next=0;,head,Setup2图解 malloc(p);p-next=head-nexthead-next=p;,head,p,Setup2图解 malloc(p);p-next=head-nexthead-next=p;,head,p,Se

18、tup2图解 malloc(p);p-next=head-nexthead-next=p;,head,p,链表的建立（带表头结点）,lklist setup2 (lklist head ) head=malloc(head) ); head-next=0; scanf(x); while (x!=somevalue) malloc(p) ; p-data=x; p-next=head-next; head-next=p; scanf(x); ; return(head); ;,链表的建立（不带表头结点）,lklist setup3 (lklist head ) head=0; scanf(x)

19、; while (x!=somevalue) malloc(p) ; p-data=x; if (head=0) head=p;q=head; else q-next=p; q=p; scanf(x); ; q-next=0; return(head); ;,链表的建立（不带表头结点）,lklist setup4 (lklist head ) head=0; scanf(x); while (x!=somevalue) malloc(p) ; p-data=x; p-next=head; head=p; scanf(x); ; return(head); ;,链表常用的操作模式指针搜索（链表的

20、显示）,void display (lklist head) p=head-next; while (p!=0) printf(p-data ); p=p-next; ;,链表常用的操作模式指针搜索（链表结点的定位）,将指针定位在 x结点Pointer locate1 (lklist head，elemtp x) p=head-next; ; while(p!=0 ；,链表的插入、删除运算,插入点的定位 * 在指定点之前：定位在指定点的直接前驱 * 在指定点之后：定位在指定点 删除点的定位：定位在指定点的直接前驱 操作的顺序 规范的删除操作 链表的插入与删除操作中最重要的一点就是确定操作对象节

21、点的直接前驱结点。否则，改变结点的连接工作就难于进行。,在指定点之前插入的图示while (p！=0 ,q,p,S,在指定点之前插入的图示s-next=q-next; q-next=s;,q,p,S,在指定点之前插入算法,void insert1 (lklist la, elemtp x,elemtp y) /*将值为y的结点插在la中值为x的结点之前，若无x结点则将新结点*/ /*作为链表的尾结点*/ q=la; p=la-next; while (p-data!=x ,在指定点之后插入的图示s-next=p-next; p-next=s;,P,S,在指定点之后插入的图示s-next=p-n

22、ext; p-next=s;(两语句不可对调）,P,S,void insert2 (lklist la, elemtp x,elemtp y) /*将值为y的结点插在la中值为x的结点之后，若无x结点则不插入*/ malloc(q); q-data=y; p=la-next； while (p-data!=x ,删除指定的结点的图示while (p-next!=0 ,p,删除指定的结点的图示q=p-next; p-next=q-next;,p q,删除指定的结点的图示free(q),p q,删除指定的结点,void delete (lklist la, elemtp x) /* 把链表中值为

23、x的结点删除，若无该结点，则给出出错信息*/ p=la; while (p-next-data!=x ,单链表就地逆置的图示q=head-next; head-next=0;,head,q,单链表就地逆置的图示p=q; q=q-next;,head,P,q,单链表就地逆置的图示 p-next=head-next; head-next=p;,head,P,q,单链表就地逆置的图示p-next=head-next; head-next=p;,head,P,q,例题 将一单链表就地逆置算法 void inver (lklist la) p=la-next; la-next=0; while (p)

24、q=p; p=p-next; q-next=la-next; la-next=q; ,消除单链表中的重复元素的示意图,p,q,q,S,Head,将单链表中的重复元素删除的算法,void delete3 (lklist la) p=la-next; while (p-next!=0) q=p; while (q-next!=0) if (q-next-data=p-data) s=q-next;q-next=s-next; free(s); else q=q-next; p=p-next; ,链表操作的几个注意点,确定进行什么操作？在何处操作？ 定位（搜索）方法 自编程序 利用现成的子程序 搜索

25、时注意指针移动的条件 是否可能丢失不该丢失的结点？ 表头指针不得随意移动 确保操作完成后，表尾结点的指针域为null 注意了解无头结点链表的各种常见的操作,链表操作的几个注意点,确定进行什么操作？在何处操作？ 定位（搜索）方法 自编程序 利用现成的子程序 搜索时注意指针移动的条件 是否可能丢失不该丢失的结点？ 表头指针不得随意移动 确保操作完成后，表尾结点的指针域为nil 注意了解无头结点链表的各种常见的操作,循环链表和双向链表,单循环链表：尾结点的指针指向头结点，形成一个“环”。从任意一个结点都可以访问到单循环链表中的任何一个结点。双向链表：每个结点设有两个指针域，其一指向该结点的直接前驱结

26、点，另一指针指向其直接后继结点。不光可以从任意一个结点访问到双链表中的任何一个结点，而且结点上的指针既可以向表尾方向移动，也可以向表头方向移动,循环链表和双向链表的图示,head,头结点,首结点,单循环链表,双链表,head,不带头结点的循环表,（单）循环链表的建立的图示,malloc(h); h-next=h; p=h; malloc(s);,h,p,s,（单）循环链表的建立的图示,s-next=p-next; p-next=s; p=s;或 p-next=s; s-next=h; p=p-next;,h,p,s,(单)循环链表建立的算法,lklist setupcirlk ( lklist

27、 h) malloc(h); h-next=h;p=h; scanf(x); while (x!=somevalue) malloc(s); s-data=x; p-next=s; s-next=h; p=s; scanf(x); return h; ,(单)循环链表建立的算法,lklist setupcirlk1 ( lklist h) malloc(h); h-next=h; scanf(x); while (x!=somevalue) malloc(s); s-data=x; s-next=h-next ;h-next=s; scanf(x); return h; ,单循环链表例 有一无

28、表头结点的循环链表，指针 s 指向其中的一个结点，设计算法删除 s 的前趋结点。,s,p,单循环链表例,只有一个结点,S,P,free(p);S=0,单循环链表例,有两个（或两个以上）结点,S,P,q,P-next=q-next,单循环链表例,lklist del ( lklist s) p=s-next; while (p-next-next != s) p=p-next; if (p-next=p) free(s); s=0; else q=p-next; p-next=q-next; free(q); return s; ,双向链表的结点定义,Struct node elemtp dat

29、a; struct node *prior,*next ; ;Typedef struct node *bpointer,*lklist1,prior,data,next,1 、掌握栈的定义和基本运算。 2 、掌握栈的顺序实现及其运算的实现。 3 、掌握栈和队列的链接实现及其运算的实现。 4 、掌握栈的应用。,第3章 栈,3.1 ADT栈,栈的定义 栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。如下所示： 进行插入和删除的一端是浮动端，通常被称为栈顶，并用一个“栈顶指针”指示；而另一端是固定端，通常被称为栈底。,a1, a2, a3, ., an 插入和

30、删除端,栈顶,栈底,栈的示意图,结论：后进先出（Last In First Out），简称为LIFO线性表。举例1：家里吃饭的盘子，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只盘子，而最后拿出最下面的那只盘子。举例2：在建筑工地上，使用的砖块从底往上一层一层地码放，在使用时，将从最上面一层一层地拿取。,常用的栈运算：StackEmpty(S)：测试栈S是否为空StackFull(S)：测试栈S是否已满StackTop(S)：返回栈S的栈顶元素Push(x,S)：在栈S的栈顶插入元素x，简称入栈Pop(S)：删除并返回栈S的栈顶元素，简称出栈或抛栈,举

31、例 程序编译时表达式或字符串的括号匹配问题。 如： (x*(x+y)-z) 求解：对于给定的表达式expr，应用栈这种特殊的抽象数据类型。 算法如下：(在算法中，栈ss是一个整数栈，用于存放未匹配左括号在字符串expr中的位置。),void Parenthsis(char *expr) int i,n; Stack ss=StackInit(); n=strlen(expr); for(i=1;i=n;i+) if(expri-1=() Push(i,ss); else if(expri-1=) if(StackEmpty(ss) printf(“位置%d处的右括号不匹配n”，i); else

32、 printf(“%d %dn”，Pop(ss),i); while(!StackEmpty(ss) printf(“位置%d处的左括号不匹配n“，Pop(ss); ,3.2 用数组实现栈(顺序栈),栈的顺序存储结构是用一组连续的存储单元(数组data)依次存放栈中的每个数据元素，并用起始端作为栈底，即data0为最早入栈的元素，并让栈向数组上方（下标增大方向）扩展。,栈结构Stack定义如下： typedef struct astack *Stack; typedef struct astack int top; /栈顶位置 int maxtop; /栈的最大数据元素数目 StackItem

33、 data; /存放栈中数据元素的数组 Astack; 注：在上述栈结构中，栈顶元素存储在datatop中，栈的 容量为maxtop。,用data数组存储示意图,基本操作算法：1. 初始化栈S Stack StackInit (int size) Stack Smalloc(sizeof *S ); S-data=malloc(size*sizeof(StackItem); S-maxtop=size; S-top=-1; return S; ,2. 测试栈S是否为空 int StackEmpty(Stack S) return S-top0; 注：当 top=-1时当前栈为空栈。,3. 测试

34、栈S是否已满 int StackFull(Stack S) return S-top=S-maxtop-1; 注：当 top=maxtop时当前栈为满栈。,4.返回栈S的栈顶元素 StackItem StackTop(Stack S) if(StackEmpty(S) Error(“Stack is empty”); else return S-dataS-top; ,5.将元素x入栈 void Push(StackItem x,Stack S) if(StackFull(S) Error(“Stack is full”); else S-data+S-top=x; ,6.出栈 StackIt

35、em Pop(Stack S) if(StackEmpty(S) Error(“Stack is empty”); else return S-dataS-top-; ,结论：由于栈的插入和删除操作具有它的特殊性，所以用顺序存储结构表示的栈并不存在插入删除数据元素时需要移动的问题，但栈容量难以扩充的弱点仍就没有摆脱。,3.3 用指针实现栈,若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。人们将用链式存储结构表示的栈称作“链栈”。链栈通常用一个无头结点的单链表表示。如图3.3所示。由于栈的插入删除操作只能在一端进行，而对于单链表来说，在首端插入删除结点要比尾端相对

36、地容易一些，所以，我们将单链表的首端作为栈顶端，即将单链表的头指针作为栈顶指针。,链栈的结点类型定义为： typedef struct snode *slink; typedef struct snode StackItem element; /存储栈元素 slink next; /指向下一个结点的指针 StackNode;,创建一个新结点 slink NewStackNode() slink p; if(p=malloc (sizeof(StackNode)=0) Error(“Exhausted memory.”); else return p; ,用指针实现的链栈Stack定义如下： t

37、ypedef struct lstack *Stack; typedef struct lstack slink top; /栈顶结点指针 Lstack;,基本操作算法：1. 初始化栈S ,将top置为空指针，创建一个空栈 Stack StackInit () Stack Smalloc(sizeof *S ); S-top=0; return S; ,2. 测试栈S是否为空 int StackEmpty(Stack S) return S-top0; ,3. 测试栈S是否已满 int StackFull(Stack S) return StackMemFull(); int StackMem

38、Full() slink p; if(p=malloc(sizeof(StackNode)=0) return 1; else free(p); return 0; ,4.返回栈S的栈顶元素 StackItem StackTop(Stack S) if(StackEmpty(S) Error(“Stack is empty”); else return S-top-element; ,5.将元素x入栈 void Push(StackItem x,Stack S) slink p; if(StackFull(S) Error(“Stack is full”); p=NewStackNode();

39、 P-element=x; p-next=S-top; S-top=p; ,6.出栈 StackItem Pop(Stack S) slink p; if(StackEmpty(S) Error(“Stack is empty”); x=S-top-element; p=S-top; S-top=p-next; free(p); return x; ,3.4 应用,【举例1】将从键盘输入的字符序列逆置输出比如，从键盘上输入：tset a si sihT；算法将输出：This is a test 下面我们给出解决这个问题的完整算法。 typedef char StackEntry; void R

40、everseRead( ) STACK S; /定义一个栈结构S char ch; StackInit (); /初始化栈,while (ch=getchar()!=n) /从键盘输入字符，直到输入换行符为止 Push(ch, S); /将输入的每个字符入栈 while (!StackEmpty(S) /依次退栈并输出退出的字符 ch=Pop(S); putchar(ch); putchar(n);,【举例2】十进制数值转换成二进制 使用辗转相除法将一个十进制数值转换成二进制数值。即用该十进制数值除以2，并保留其余数；重复此操作，直到该十进制数值为0为止。最后将所有的余数反向输出就是所对应的二

41、进制数值。 比如：(692)10 = (1010110100)2，其辗转相除的过程如下图所示：,下面给出解决这个问题的完整算法。void Decimal _ Binary ( ) STACK S; /定义栈结构SStackInit (); /初始化栈Sscanf(“%d”,data); /输入十进制正整数,while (data) Push(data%2,S); /余数入栈 data/=2; /被除数data整除以2，得到新的被除数while (!StackEmpty(S) /依次从栈中弹出每一个余数，并输出之 data=Pop(S); printf(“%d”,data);,【举例3】检验表达

42、式中的括号匹配情况 假设在一个算术表达式中，可以包含三种括号：圆括号“（”和“）”，方括号“”和“”和花括号“”和“”，并且这三种括号可以按任意的次序嵌套使用。比如，.(.).。现在需要设计一个算法，用来检验在输入的算术表达式中所使用括号的合法性。 算术表达式中各种括号的使用规则为：出现左括号，必有相应的右括号与之匹配，并且每对括号之间可以嵌套，但不能出现交叉情况。我们可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配情况。在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论。,（1）当遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号；（

43、2）从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况；（3）算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。 下面是解决这个问题的完整算法。,typedef char StackEntry; int Check( ) STACK S; /定义栈结构S char ch; InitStack(); /初始化栈S while (ch=getchar()!=n) /以字符序列的形式输入表达式 switch (ch) case (ch=(|ch= |ch= ): Push(ch,S); break; /遇左括号入栈,/在遇到右括号时，分别检测匹配情况case (

44、ch= ): if (StackEmpty(S) retrun FALSE; else ch=Pop(S); if (ch!= () return FALSE; break; case (ch= ): if (StackEmpty(S) retrun FALSE; else ch=Pop(S); if (ch!= ) return FALSE; break;,case (ch= ): if (StackEmpty(S) retrun FALSE; else ch=Pop(S); if (ch!= ) return FALSE; break; default: break; if (StackE

45、mpty(S) return TRUE; else return FALSE;,第 4 章 队列,1 、掌握队列的定义和基本运算。 2 、掌握队列的顺序实现（循环队列）及其运算的实现。 3 、掌握队列的链接实现及其运算的实现。 4 、掌握队列的应用。,4.1 ADT队列,队列是另一种特殊的表，队列特殊性在于限定插入在线性表的一端进行，删除在线性表的另外一端进行。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。,当

46、队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,an ，也就是说队列的修改是依先进先出的原则进行的。,常用的队列运算：QueueEmpty(Q)：测试队列Q是否为空QueueFull(Q)：测试队列Q是否已满QueueFirst(Q)：返回队列Q的队首元素QueueLast(Q)：返回队列Q的队尾元素EnterQueue (x,Q)：在队列Q的队尾插入元素xDeleteQueue (Q)：删除并返回队列Q的队首元素,4.2 用指针实现队列,用指针实现队列实际上得到一个单链表。队列结点的类型与单链表结点

47、类型相同。 typedef struct qnode *qlink; typedef struct qnode QItem element; /存储队列元素 qlink next; /指向下一个结点的指针 Qnode;,用指针实现的队列Queue定义如下： typedef struct lque * Queue; typedef struct lque qlink front; /队首结点指针 qlink rear; /队尾结点指针 Lqueue;,1. 将队首指针front和队尾指针rear均置为空指针，创建一个空队列 Queue QueueInit () Queue Qmalloc(siz

48、eof *Q ); Q-front=Q-rear=0; return Q; ,队列的基本运算1. 测试队列Q是否为空 int QueueEmpty(Queue Q) return Q-front0; ,3. 测试队列Q是否已满 int QueueFull(Queue Q) return QMemFull(); int QMemFull() qlink p; if(p=malloc(sizeof(Qnode)= =0) return 1; else free(p); return 0; ,4. 返回队列Q的队首结点中的元素 QItem QueueFirst(Queue Q) if(QueueEm

49、pty(Q) Error(“Queue is empty”); else return Q-front-element; ,5. 返回队列Q的队尾结点中的元素 QItem QueueLast(Queue Q) if(QueueEmpty(Q) Error(“Queue is empty”); else return Q-rear-element; ,6.在队尾插入新结点x void EnterQueue(QItem x, Queue Q) qlink p; p=NewStackNode(); P-element=x; p-next=0; if(Q-front) Q-rear-next=p; e

50、lse Q-front=p; Q-rear=p; ,7.删除队首结点 QItem DeleteQueue(Queue Q) qlink p; QItem x; if(QueueEmpty(Q) Error(“Queue is empty”); x=Q-front-element; p=Q-front; Q-front= Q-front-next; free(p); return x; ,4.3 用循环数组实现队列,队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表，和顺序表一样，顺序队列也是必须用一个向量空间来存放当前队列中的元素。由于队列的队头和队尾的位置是变化的，因而要设两个