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

*1 * 栈和队列 栈 抽象数据类型栈的定义 栈的表示和实现 栈的应用举例 数制转换 表达式求解 队列 *2 * 是限制仅在线性表的一端进行插入和删除运算的线性表。 an . . . a2 a1 栈顶 TOP 栈底 Bottom 栈顶（TOP） 允许插入和删除的一端。 栈底（bottom) 不允许插入和删除的一端 。 空栈 表中没有元素。 栈(Stack) *3 * an . . . a2 a1 进栈 退栈 栈顶 栈底 进栈 最先插入的元素放在栈的底 部。 退栈 最后插入的元素最先退栈。 栈的基本概念 栈:又称为后进先出的线性表（LIFO表，Last In First Out ）一叠书或一叠盘子。 *4 * 栈与子程序调用 调用子程序时，计算机将子程序要用到的参数及返回地 址等信息存放在栈里 子程序返回时，从栈顶取回返回地址，转回主调程序继 续运行。 处理递归调用 *5 * 顺序栈 用数组定义（类似于顺序表），将栈底位置设置在向量两端 的任意一个端点；用top（整型量，栈顶指针）来指示栈当前 栈顶位置。 定义： typedef (type) Element;/*栈元素的数据类型*/ #define maxsize 100 /*栈初始的容量*/ typedef struct stack Element datamaxsize; int top; Stack;/*顺序栈类型定义*/ Stack *s;/*s是顺序栈类型指针*/ *6 * 3 2 1 0 Top=-1空栈 A 3 2 1 0 TOP A进栈 3 2 1 0 D C B A B、C、D依次进栈 TOP 3 2 1 0 B A TOP D、C依次退栈 3 2 1 0 Top=-1，B、A退栈 顺序栈：栈顶指针与栈中元素间的关系 *7 * 顺序栈 栈底位置固定在数组的低端，即： S-data0-表示栈底元素； 进栈：S-TOP加1（正向增长）。 退栈：S-TOP减1。 空栈： S-TOP TOP=maxsize-1 上溢：栈满时再做进栈运算（一种出错状态，应设法避 免）。 *8 * 顺序栈的几种基本运算 置空栈 判栈空 进栈 退栈 取栈顶元素 *9 * 顺序栈的几种基本运算 置空栈：Create(Stack else return True; /* Empty */ *11 * void Push(Stack else S.top+; S.dataS.top=e; /* Push */ 顺序栈的几种基本运算 进栈： *12 * /*若栈S非空，取出栈顶元素删除*/ void Pop(Element else e=S.dataS.top; S.top-; 退栈： Pop(S) 顺序栈的几种基本运算 *13 * /*取顺序栈S的栈顶*/ Element Top(Stack return NULL; else return(S.dataS.top); 取栈顶： Top(S) 顺序栈的几种基本运算 *14 * 链栈 栈的链式存储结构（当顺序栈的最大容量事先无法估 计时，可采用链栈结构）。 TOP e1 next 栈顶 . . 链栈的定义： typedef struct cell* Position; typedef struct cell Element e1; Position next; Cell; typedef struct stack Position *top; Stack; *15 * 链栈的特点 插入和删除（进栈/退栈）仅能在表头位置上（栈顶） 进行。 链栈中的结点是动态产生的，可不考虑上溢问题。 不需附加头结点，栈顶指针就是链表（即链栈）的头指 针。 *16 * void Push(Element e,Stack p=new(Cell); p-e1=e; p-next=S.top; S.top=p; . 栈底 x s.top 链栈进栈运算 *17 * 链栈退栈运算 void Pop(Element if(S.top=NULL) SErr=StackUnderflow; else e=S.top-e1; p=S.top; S.top=S.top-next; free(p); top . 栈底 top q *18 * 栈小结 顺序栈有发生上溢 的可能，而链栈通常不会发生栈满（ 除非整个空间均被占满） 只要满足LIFO原则，均可采用栈结构。 栈的应用实例：递归调用。 *19 * 栈的应用举例一数制转换 十进制N和其它进制数的转换是计算机实现计算的基本问 题,其解决方法很多,其中一个简单算法基于下列原理: N=(n div d)*d + (n mod d) （185）10 =（ ？ ）8 （1 8 5）10 = （2 7 1）8 8 2 78 0 2 1 8 5 8 2 3 1 余数 *20 * 例 把十进制数159转换成八进制数。 (159)10=(237)8 1598 198 28 0 2 3 7 余 7 余 3 余 2 top top 7 top 7 3 top 7 3 2 栈的应用举例一数制转换 *21 * void conversion( ) /conversion Initstack(S); scanf(“%d”, while(N) Push(S,N % 8) ; N=N/8 ; while (! Stackempty(s) Pop(S,e); Printf(“%d”,e); 栈的应用举例一数制转换 *22 * 栈的应用举例一算术表达式 建立2个栈：操作数栈及运算符栈，初始为空 从左到右读取表达式，如果读到操作数则置入操作数栈中， 若读到运算符时则置入运算符栈。 当读到的运算符优先级比栈中的运算符高，则存入栈 当读到的运算符优先级比堆栈中的运算符低或相等，则取出 该运算符并从操作数栈取出相应的操作数运算，并将结果存 回操作数栈；同时新运算符入栈； 堆栈非空 从运算符栈中取出一个运算符 从操作数栈中取出所需操作数 计算其值后将结果存回操作数栈 例 计算 2+4-3*6 *23 * 例 计算 2+4-3*6 操作数运算符 2 4 + 操作数运算符 6- 操作数运算符 6- 3 6 * 操作数运算符 6- 18 操作数运算符 12 栈的应用举例一算术表达式 *24 * 队列 只允许在表的一端进行插入，而在表的另一端进行删除 ，是一种先入先出的线性表（FIFO）。 *25 * 队列的基本概念 队头（head):允许删除（出队）的一端 队尾（tail):允许插入的一端 空队列：队列中没有元素 进队：队的插入运算，即插入新的队尾元素 出队：队的删除运算，删除队首元素 *26 * 队列的基本运算 入队 出队 取队头元素 置空队列 判队列是否为空 *27 * 顺序队列 队列的顺序存储结构，用一组连续的存储单元依次存放 队列中的元素 顺序队列的类型说明： typedef struct datatype datam; int head, tail; /*队首、队尾*/ queue; queue *sq; *28 * B A D C 3 2 1 0 sq-head sq-tail sq-head sq-tail sq-head sq-tail sq-tail sq-head 空队列A、B相继入队 A、B相继出队C、D相继入队 顺序队列运算时的头、尾指针变化 *29 * 顺序队列的约定和主要运算 队头指针:head总是指向当前队头元素 队尾指针:tail指向当前队尾元素的下一个位置。 初始状态：head=tail=0 入队运算：sq-tail+; /*尾指针加1 */ sq-datasq-tail=x; /* x入队 */ 出队运算：sq-head+; /* 头指针加1 */ *30 * 顺序队列的约定和主要运算 队列长度：(sq-tail)-(sq-head) 队空：(sq-tail)=(sq-head) 下溢：队空时再作出队操作。 队满：(sq-tail)-(sq-head)=m 上溢：队满时再作入队操作。 *31 * 顺序队列的上溢 队上溢： 真上溢（r-f=m)：队列真正满时再入队。 假上溢：r已指向数组尾端，但队列前端仍有空位置。 解决假上溢的方法： 方法一：每次删除队头一个元素后，把整个队列往前 移一个位置（造成时间浪费）。 方法二：循环队列 *32 * Setnull(queue *sq) sq-head0; sq-tail0; 顺序队列置队空 *33 * Bool Empty(queue *sq) if (sq-tail = sq-head) return (True); else return (False); 顺序队列判队空 *34 * datatype Front(queue *sq) datatype temp; if (Empty(sq) printf(“queue is emptyn”); return NULL; else temp= sq-data sq-head; return temp ; 顺序队列取队头元素 *35 * 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); 顺序队列入队 *36 * datetype Dequeue(queue *sq) if (Empty(sq) printf(“queue is emptyn”);return NULL; else sq-head(sq-head+1); return(sq-datasq-head); 顺序队列出队 *37 * 循环队列 (Circular Queue) 当队尾指针tail等于MaxSize时，无论有否空间，都无法 再将数据存于队列中 将所用的数组sq-datam设想为首尾相接的循环数组（ 即：data0连在datam-1之后)。 tail head *38 * 循环队列的进队和出队 0 1 0 76 5 4 3 2 1 head tail 空队列 A 1 0 76 5 4 3 2 1 head tail A入队 A 1 0 76 5 4 3 C B head tail BC入队 0 1 0 76 5 4 3 C B head tail A出队 *39 * 循环队列 (Circular Queue) 队列入队： 若尾指针 r 等于向量的上界，再入队，令尾指针等于 向量的下界，即：在循环意义下的尾指针的加1操作 可描述为： if(sq-tail+1=m) sq-tail=0; else sq-tail+; *40 * 循环队列 (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 *41 * Q-head data next 队头 . . Q-tail 队尾 队列的链接表示 链式队列 队头在链头，队尾在链尾。 链式队列在进队时无队满问题，但有队空问题。 队空条件为 head = NULL *42 * Q-head Q-tail 空队列 Q-head Q-tail 元素 x 入队列 x 元素 y 入队列 Q-head Q-tail xy Q-head Q-tail xy 元素x 出队列 队列的链接表示 链式队列 *43 * typedef struct linklist *head,*tail; linkqueue; 链队列结点类型定义 *44 * Setnull (linkqueue *q) q-headmalloc(sizeof(linklist); q-head-nextNULL; q-tailq-head; 链队列置队空 *45 * int Empty(linkqueue *q) if ( q-head = q-tail ) return(True); else return(False); 链队列判队空 *46 * datatype Front(linkqueue *q) if (Empty(q) printf(“queue is emptyn”); return NULL; else return(q-head-next-data); 链队列取队头结点 *47 * Enqueue(linkqueue *q, datatype x) pmalloc(sizeof(linklist); p -data=x; p -next=null; q-tail-nextp; q-tailp; 链队列入队 *48 * datatype Dequeue(linkqueue *q, datatype e) linklist *p; if (Empty(q) printf(“queue is emptyn”); return NULL; else pq-head-next; ep-data; q-head-