《数据结构——C语言描述 教学课件 ppt 作者 王国钧 主编 唐国民 苏晓萍 马瑜 副主编 电子教案DS03-栈和队列》由会员分享，可在线阅读，更多相关《数据结构——C语言描述 教学课件 ppt 作者 王国钧 主编 唐国民 苏晓萍 马瑜 副主编 电子教案DS03-栈和队列（51页珍藏版）》请在金锄头文库上搜索。
1、栈（Stack） 栈的应用 队列（Queue） 队列的应用,第三章 栈和队列,定义,3.1 栈,与线性表相同，仍为一对一( 1:1)关系。,用顺序栈或链栈存储均可，但以顺序栈更常见,只能在栈顶运算，且访问结点时依照后进先出（LIFO）或先进后出（FILO）的原则。,关键是编写入栈和出栈函数，具体实现依顺序栈或链栈的存储结构有别而不同。,限定只能在表的一端进行插入和删除运算的线性表。,基本操作 建栈、判断栈满或栈空、入栈、出栈、读栈顶元素值，等等。,栈 是仅在表尾进行插入、删除操作的线性表。 表尾(即 an 端)称为栈顶 /top ; 表头(即 a1 端)称为栈底/base,例如： 栈 S= (
2、a1 , a2 , a3 , .,an-1 , an ),插入元素到栈顶的操作，称为入栈。 从栈顶删除最后一个元素的操作，称为出栈。,an称为栈顶元素,a1称为栈底元素,强调：插入和删除都只能在表的一端（栈顶）进行！,栈的基本操作,ClearStack(S)： 清除栈S中的所有元素 InitStack(S)： 构造一个空栈S StackEmpty(S)：判断栈S是否为空，若为空，则返回 true；否则返回false GetTop(S) ： 返回S的栈顶元素，但不移动栈顶指针 Push(S, x) ：插入元素x为新的栈顶元素（入栈操作) Pop(S) ： 删除S的栈顶元素并返回其值（出栈操作）,
3、顺序栈的存储结构和操作的实现,顺序栈:是利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素。,在C语言中，预设一个数组的最大空间,栈底设置在0下标端，栈顶随着插入和删除元素而变化，用一个整型变量top来指示栈顶的位置。,0,n,压入(PUSH): Stop+=an+1 弹出( POP) : e=S-top,顺序栈存储结构的描述： #define Maxsize 100 /*设顺序栈的最大长度为100，可依实现情况而修改*/ typedef int datatype; typedef struct datatype stackMaxsize; int top； /*栈顶指针*/ SeqSt
4、ack； /*顺序栈类型定义*/ SeqStack *s； /*s为顺序栈类型变量的指针*/,顺序栈的几种状态以及在这些状态下栈顶指针top和栈中结点的关系,栈为空的条件 ： top=0; 栈满的条件 ： top-base=Maxsize,若入栈动作使地址向高端增长，称为“向上生成”的栈； 若入栈动作使地址向低端增长，称为“向下生成”的栈； 对于向上生成的堆栈: 入栈：栈指针top “先压后加” : Stop+=an+1 出栈：栈指针top “先减后弹” : e=S-top,顺序栈的基本操作,构造一个空顺序栈,SeqStack *InitStack() SeqStack *S ; S=(Seq
5、Stack *)malloc(sizeof(SeqStack); if(!S) printf(“空间不足”)； return NULL; else S-top=0; return S; ,取顺序栈栈顶元素,datatype GetTop(SeqStack *S) if (S-top=0) printf(“n栈是空的!“); return FALSE; else return S-stackS-top-1; ,判别空栈,int StackEmpty(SeqStack *S) if(S-top=0) return TRUE; else return FALSE; ,顺序栈的入栈操作例如用堆栈存放（
6、A，B，C，D）,A,A,C B A,B A,核心语句：,顺序栈入栈函数PUSH（） SeqStack*Push(SeqStack*S，datatype x) if(S-top=Maxsize) return NULL; else S-stackS-top=x; S-top+; return s; ,Push (B);,Push (C);,Push (D);,低地址L,Push (A);,高地址M,B,C,D,顺序栈出栈操作例如从栈中取出B,核心语句： Pop ( );,顺序栈出栈函数POP() datatype Pop( SeqStack *S) if(S-top=0) printf(“nT
7、he sequence stack is empty!“); return FALSE; S-top-; return S-stackS-top; ,Pop ( );,Printf( Pop () );,链栈的入栈操作和出栈操作,链栈的构造方式以头指针为栈顶，在头指针处插入或删除.,栈顶,栈底,栈也可以用链式结构来表示，用链式结构来表示的栈就是链栈,链栈中每个结点由两个域构成： data域和next域，其定义为：,Typedef struct node datatype data; struct node * next; LinkStack; LinkStack *top;,将x入栈，修改栈顶
8、指针:top=p,an出栈，修改栈顶指针:top=top-next,LinkStack *Push(LinkStack *top，datatype x) LinkStack *p; p=( Linkstack *)malloc(sizeof(LinkStack); p-data=x; p-next=top; top=p; return top; ,链栈入栈操作,LinkStack *Pop( LinkStack *top) LinkStack *q; if(!top) printf(“n链栈是空的!“);return NULL; q=top; top=top-next; free(q); re
9、turn top; ,链栈出栈操作,1、数制转换（十转N） 设计思路：用栈暂存低位值 2、括号匹配问题 设计思路：用栈暂存左括号 3、子程序的调用 设计思路：用栈暂存指令地址 4、逆置一个单链表 设计思路：用栈暂存每一结点,3.2 栈的应用举例,例3.2 将十进制整数转换成二至九之间的任一进制数输出,将一个十进制数4327转换成八进制数(10347)8：,1、当N0，将N%r压入栈s中； 2、用N/r代替N； 3、若N0，则重复（1）、（2）；若N=0，则将栈s的内容依次出栈。,解题思路如下：,void conversion(int N, int r) int x=N,y=r; SeqStac
10、k *s; s=InitStack(); while(N!=0) Push(s, N %r ); N=N/r ; printf(“n十进制数%d所对应的%d进制数是:”，x,y); while(!StackEmpty(s) printf(“%d”,Pop(s); printf(“n”); ,例3.5 利用一个顺序栈将利用一个顺序栈将单链表（a1,a2,an）（其中n=0）逆置为（an,an-1,，a1）,1、建立一个带头结点的单链表head； 2、输出该单链表； 3、建立一个空栈s（顺序栈）； 4、依次将单链表的数据入栈； 5、依次将单链表的数据出栈，并逐个将出栈的数据存入单链表的数据域（自前
11、向后）; 6、再输出单链表。,解题思路如下：,linklist*backlinklist(linklist *head) linklist *p; p=head-next; initstack(); while(p) push( ,；,3.3 队列,与线性表相同，仍为一对一关系。,顺序队或链队，以循环顺序队更常见。,只能在队首和队尾运算，且访问结点时依照先进先出（FIFO）的原则。,关键是掌握入队和出队操作，具体实现依顺序队或链队的不同而不同。,只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。,基本操作：入队或出队，建空队列，判队空或队满等操作。,尾部插入,首部删除,队列定义,队
12、列 （Queue）是仅在表尾进行插入操作，在表头进行删除操作的线性表。它是一种先进先出（）的线性表。,例如：队列 Q= (a1 , a2 , a3 , .,an-1 , an ),在队尾插入元素称为入队；在队首删除元素称为出队。,队首,队尾,问：为什么要设计队列？它有什么独特用途？,答： 1.离散事件的模拟（模拟事件发生的先后顺序,例如 CPU芯片中的指令译码队列）； 2.操作系统中的作业调度（一个CPU执行多个作业）； 3.简化程序设计。,队的实现方式是本节重点，关键是掌握入队和出队操作。 具体实现依存储结构（链队或顺序队）的不同而不同。,1. 链队列 2. 顺序队,（1）InitQueue
13、 (Q)： 构造一个空队列Q （2）QueueEmpty (Q)： 判断队列是否为空 （3）QueueLength (Q)： 求队列的长度 （4）GetHead (Q)： 返回Q的队头元素，不改变队列状态 （5）EnQueue(Q， x )： 插入元素x为Q的新的队尾元素 （6）DeQueue(Q)： 删除Q的队头元素 （7）ClearQueue(Q)：清除队列Q中的所有元素,链队列类型定义： typedef struct Qnode *front ; /*队头指针*/ Qnode *rear ; /*队尾指针*/ LinkQueue;,结点类型定义： typedef Struct Qnode
14、 datatype data; /*数据域*/ Struct Qnode *next; /*指针域*/ Qnode;,链队列,链队的几种状态示意图：,此时，front=rear,修改rear指针,修改头结点的指针域,空链队的特征？front=rear, 链队会满吗？,一般不会，因为删除时有free动作。除非内存不足！,入队（尾部插入）：rear-next=S; rear=S; 出队（头部删除）：front-next=p-next;, 怎样实现链队的入队和出队操作？ 若设S所指结点为入队结点,LinkQueue *InitQueue() LinkQueue *q; Qnode *p; Q=(Li
15、nkQueue*)malloc(sizeof(LinkQueue); p=(Qnode*)malloc(sizeof(Qnode); p-next=NULL; q-front =q-rear=p; return q; ,构造一个空链队操作,datatype GetHead(LinkQueue *Q) if(Q-.front-next =Q-rear) printf(“n链队列为空!”); return FALSE; return Q-front-next-data； ,取链队队头元素操作,void EnQueue(LinkQueue *Q，datatype x) Qnode *p; p = (Qnode*)malloc(sizeof(Qnode)； p-data = x； p-next = NULL； Q-rear-next = p； Q-rear=p； ,链队入队操作,datatype DeQueue(LinkQueue *Q) Qnode *p; datatype x; if (Q-front = Q-rear) printf(“队列为空，无法删除！“); return FALSE; p = Q-front-next； x = p-data； Q-front-next = p-next； if(Q-rear = p) Q-rear=Q-front； free(p)
