c语言课件：栈和队列.ppt

《c语言课件：栈和队列.ppt》由会员分享，可在线阅读，更多相关《c语言课件：栈和队列.ppt（49页珍藏版）》请在三一办公上搜索。

1、栈和队列,栈抽象数据类型栈的定义栈的表示和实现栈的应用举例数制转换表达式求解队列,是限制仅在线性表的一端进行插入和删除运算的线性表。,栈顶（TOP）允许插入和删除的一端。栈底（bottom)不允许插入和删除的一端。空栈表中没有元素。,栈(Stack),进栈最先插入的元素放在栈的底部。退栈最后插入的元素最先退栈。,栈的基本概念,栈:又称为后进先出的线性表（LIFO表，Last In First Out）一叠书或一叠盘子。,栈与子程序调用,调用子程序时，计算机将子程序要用到的参数及返回地址等信息存放在栈里子程序返回时，从栈顶取回返回地址，转回主调程序继续运行。处理递归调用,顺序栈,用数组定义（类似

2、于顺序表），将栈底位置设置在向量两端的任意一个端点；用top（整型量，栈顶指针）来指示栈当前栈顶位置。定义：typedef(type)Element;/*栈元素的数据类型*/#define maxsize 100/*栈初始的容量*/typedef struct stackElement datamaxsize;int top;Stack;/*顺序栈类型定义*/Stack*s;/*s是顺序栈类型指针*/,3 2 1 0,Top=-1空栈,顺序栈：栈顶指针与栈中元素间的关系,顺序栈,栈底位置固定在数组的低端，即：S-data0-表示栈底元素；进栈：S-TOP加1（正向增长）。退栈：S-TOP减1。

3、空栈：S-TOP TOP=maxsize-1上溢：栈满时再做进栈运算（一种出错状态，应设法避免）。,顺序栈的几种基本运算,置空栈判栈空进栈退栈取栈顶元素,顺序栈的几种基本运算,置空栈：Create(Stack&S),void Create(Stack&S)/*将顺序栈S置为空*/S.top=-1,顺序栈的几种基本运算,判栈空：,Bool Empty(Stack/*Empty*/,void Push(Stack/*Push*/,顺序栈的几种基本运算,进栈：,/*若栈S非空，取出栈顶元素删除*/void Pop(Element,退栈：Pop(S),顺序栈的几种基本运算,/*取顺序栈S的栈顶*/El

4、ement Top(Stack,取栈顶：Top(S),顺序栈的几种基本运算,链栈,栈的链式存储结构（当顺序栈的最大容量事先无法估计时，可采用链栈结构）。,TOP,e1 next,栈顶,.,链栈的定义：typedef struct cell*Position;typedef struct cell Element e1;Position next;Cell;typedef struct stack Position*top;Stack;,链栈的特点,插入和删除（进栈/退栈）仅能在表头位置上（栈顶）进行。链栈中的结点是动态产生的，可不考虑上溢问题。不需附加头结点，栈顶指针就是链表（即链栈）的头指针

5、。,void Push(Element e,Stack,.,栈底,x,s.top,链栈进栈运算,链栈退栈运算,void Pop(Element,栈小结,顺序栈有发生上溢 的可能，而链栈通常不会发生栈满（除非整个空间均被占满）只要满足LIFO原则，均可采用栈结构。栈的应用实例：递归调用。,栈的应用举例一数制转换,十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理:N=(n div d)*d+(n mod d),（185）10=（？）8,（1 8 5）10=（2 7 1）8,栈的应用举例一数制转换,void conversion()/conversi

6、on Initstack(S);scanf(“%d”,栈的应用举例一数制转换,栈的应用举例一算术表达式,建立2个栈：操作数栈及运算符栈，初始为空从左到右读取表达式，如果读到操作数则置入操作数栈中，若读到运算符时则置入运算符栈。当读到的运算符优先级比栈中的运算符高，则存入栈当读到的运算符优先级比堆栈中的运算符低或相等，则取出该运算符并从操作数栈取出相应的操作数运算，并将结果存回操作数栈；同时新运算符入栈；堆栈非空从运算符栈中取出一个运算符从操作数栈中取出所需操作数计算其值后将结果存回操作数栈,例 计算 2+4-3*6,例 计算 2+4-3*6,栈的应用举例一算术表达式,队列,只允许在表的一端进行

7、插入，而在表的另一端进行删除，是一种先入先出的线性表（FIFO）。,队列的基本概念,队头（head):允许删除（出队）的一端队尾（tail):允许插入的一端空队列：队列中没有元素进队：队的插入运算，即插入新的队尾元素出队：队的删除运算，删除队首元素,队列的基本运算,入队出队取队头元素置空队列判队列是否为空,顺序队列,队列的顺序存储结构，用一组连续的存储单元依次存放队列中的元素顺序队列的类型说明：typedef struct datatype datam;int head,tail;/*队首、队尾*/queue;queue*sq;,BA,DC,3 2 1 0,sq-headsq-tail,sq-

8、head,sq-tail,sq-headsq-tail,sq-tail,sq-head,空队列,A、B相继入队,A、B相继出队,C、D相继入队,顺序队列运算时的头、尾指针变化,顺序队列的约定和主要运算,队头指针:head总是指向当前队头元素队尾指针:tail指向当前队尾元素的下一个位置。初始状态：head=tail=0入队运算：sq-tail+;/*尾指针加1*/sq-datasq-tail=x;/*x入队*/出队运算：sq-head+;/*头指针加1*/,顺序队列的约定和主要运算,队列长度：(sq-tail)-(sq-head)队空：(sq-tail)=(sq-head)下溢：队空时再作出队

9、操作。队满：(sq-tail)-(sq-head)=m上溢：队满时再作入队操作。,顺序队列的上溢,队上溢：真上溢（r-f=m)：队列真正满时再入队。假上溢：r已指向数组尾端，但队列前端仍有空位置。解决假上溢的方法：方法一：每次删除队头一个元素后，把整个队列往前移一个位置（造成时间浪费）。方法二：循环队列,Setnull(queue*sq)sq-head0;sq-tail0;,顺序队列置队空,Bool Empty(queue*sq)if(sq-tail=sq-head)return(True);else return(False);,顺序队列判队空,datatype Front(queue*sq

10、)datatype temp;if(Empty(sq)printf(“queue is emptyn”);return NULL;else temp=sq-data sq-head;return temp;,顺序队列取队头元素,Bool Enqueue(queue*sq,datatype x)if(sq-head=(sq-tail+1)%m)printf(“queue is fulln”;return NULL);else sq-tail(sq-tail+1);sq-datasq-tailx;return(True);,顺序队列入队,datetype Dequeue(queue*sq)if(E

11、mpty(sq)printf(“queue is emptyn”);return NULL;else sq-head(sq-head+1);return(sq-datasq-head);,顺序队列出队,循环队列(Circular Queue),当队尾指针tail等于MaxSize时，无论有否空间，都无法再将数据存于队列中将所用的数组sq-datam设想为首尾相接的循环数组（即：data0连在datam-1之后)。,tail,head,循环队列的进队和出队,空队列,循环队列(Circular Queue),队列入队：若尾指针 r 等于向量的上界，再入队，令尾指针等于向量的下界，即：在循环意义下的

12、尾指针的加1操作可描述为：if(sq-tail+1=m)sq-tail=0;else sq-tail+;,循环队列(Circular Queue),存储队列的数组被当作首尾相接的表处理。队头、队尾指针加1时从maxSize-1直接进到0，可用语言的取模(余数)运算实现。队头指针进1:head=(head+1)%maxSize;队尾指针进1:tail=(tail+1)%maxSize;队列初始化：head=tail=0;队空条件：head=tail;队满条件：(tail+1)%maxSize=head,Q-head,data next,队头,.,Q-tail,队尾,队列的链接表示 链式队列,队头

13、在链头，队尾在链尾。链式队列在进队时无队满问题，但有队空问题。队空条件为 head=NULL,队列的链接表示 链式队列,typedef struct linklist*head,*tail;linkqueue;,链队列结点类型定义,Setnull(linkqueue*q)q-headmalloc(sizeof(linklist);q-head-nextNULL;q-tailq-head;,链队列置队空,int Empty(linkqueue*q)if(q-head=q-tail)return(True);else return(False);,链队列判队空,datatype Front(lin

14、kqueue*q)if(Empty(q)printf(“queue is emptyn”);return NULL;else return(q-head-next-data);,链队列取队头结点,Enqueue(linkqueue*q,datatype x)pmalloc(sizeof(linklist);p-data=x;p-next=null;q-tail-nextp;q-tailp;,链队列入队,datatype Dequeue(linkqueue*q,datatype e)linklist*p;if(Empty(q)printf(“queue is emptyn”);return NU

15、LL;else pq-head-next;ep-data;q-head-next=p-next free(p);return(p);,链队列出队,栈和队列作业1、用栈实现以下功能：（1）实现任意十进制数转换为二进制数，并测试；（2）实现表达式计算，并测试；2、用循环队列模拟舞伴配对问题：在舞会上，男、女各自排成一队。舞会开始时。依次从男队和女队的队头各出一人配成舞伴。如果两队初始人数不等，则较长的那一队中未配对者等待下一轮舞曲。假设初始男、女人数及性别已经固定，舞会的轮数从键盘输入。试模拟解决上述舞伴配对问题。要求：从屏幕输出每一轮舞伴配对名单，如果在该轮有未配对的，能够从屏幕显示下一轮第一个出场的未配对者的姓名。,