堆栈堆栈的应用队列队列的应用ppt课件

1、退栈退栈进栈进栈进栈例如进栈例如 退栈例如退栈例如栈的根本操作栈的根本操作1、初始化、初始化2、进栈、进栈3、退栈、退栈4、取栈顶元素、取栈顶元素5、判栈能否非空、判栈能否非空6、置栈空、置栈空栈的顺序存储构造栈的顺序存储构造顺序栈的定义顺序栈的定义typedef int datatype;#define maxsize 64typedef struct datatype datamaxsize; int top;seqstack; 栈的根本运算栈的根本运算置空栈置空栈SETNULL(seqstack *s) s-top-1; 判栈空判栈空int EMPTY(seqstack *s) if (

2、s-top=0) return FALSE; else return TRUE;进栈进栈seqstack *PUSH(seqstack *s,datatype x) if (s-top=maxsize-1) printf(“overflown);return NULL; else s-top+; s-datas-topx; return s;退栈退栈datatype POP(seqstack *s) if (EMPTY(s) printf(“underflown);return NULL; else s-top-; return(s-datas-top+1); 取栈顶取栈顶datatype T

3、OP(seqstack *s) if (EMPTY(s) printf(“underflown);return NULL; else return(s-datas-top);两个堆栈共享空两个堆栈共享空间间0maxsize-1lefttoprighttop栈的链接存储构造栈的链接存储构造链栈的结点定义链栈的结点定义typedef int datatype;typedef struct node datatype data; struct node *next; linkstack; 链栈的进栈算法链栈的进栈算法linkstack *PUSHLSTACK(linkstack *top, data

4、type x) linkstack *p; pmalloc(sizeof(linkstack); p-datax; p-nexttop; return p;链栈的出栈算法链栈的出栈算法linkstack *POPLSTACK(linkstack *top, datatype *datap) linkstack *p; if (top=NULL) printf(“under flown); return NULL; else *dataptop-data; ptop; toptop-next; free(p); return top; 例：例：对于一个栈，给出输入项对于一个栈，给出输入项A、B、

5、C，假设输入项序列，假设输入项序列由由ABC组成，试给出一切能够的输出序列。组成，试给出一切能够的输出序列。A进进 A出出 B进进 B出出 C进进 C出出 ABCA进进 A出出 B进进 C进进 C出出 B出出 ACBA进进 B进进 B出出 A出出 C进进 C出出 BACA进进 B进进 B出出 C进进 C出出 A出出 BCAA进进 B进进 C进进 C出出 B出出 A出出 CBA不能够产生输出序列不能够产生输出序列CAB栈的运用举例文字编辑器栈的运用举例文字编辑器seqstack s;EDIT() char c; SETNULL(&s); cgetchar(); while (c!=*)

6、if (c=#) POP(&s); else if (c=) SETNULL(&s); else PUSH(&s,c); cgetchar(); 栈的运用递归函数栈的运用递归函数int FACT(int n) if (n=1) return(1); else return(n*FACT(n-1); 栈的运用表达式计算栈的运用表达式计算中缀表达式：中缀表达式：A + ( B C / D) A + ( B C / D) E E后缀表达式：后缀表达式：ABCD/ABCD/E E+ + 逆波兰表达式逆波兰表达式后缀表达式特点后缀表达式特点1 1、与相应的中缀表达式中的操作数次序

7、一样、与相应的中缀表达式中的操作数次序一样2 2、没有括号、没有括号后缀表达式的处置过程后缀表达式的处置过程操作顺序后缀表达式ABCD/E+T1 C/DABT1E+T2 B T1AT2E+T3 T2 EAT3+T4 A + T3T4ABCDEABCT1ABT2AT3中缀表达式转换为后缀表达式中缀表达式转换为后缀表达式()#(#frontmaxsize-1; sq-rearmaxsize-1;顺序队列判队空顺序队列判队空int EMPTY(sequeue *sq) if (sq-rear=sq-front) return(TRUE); else return(FALSE); 顺序队列取队头元素顺

8、序队列取队头元素datatype FRONT(sequeue *sq) if (EMPTY(sq) printf(“queue is emptyn); return NULL; else return (sq-front+1)%maxsize);顺序队列入队顺序队列入队int ENQUEUE(sequeue *sq,datatype x) if (sq-front=(sq-rear+1)%maxsize) printf(“sequeue is fulln;return NULL); else sq-rear(sq-rear+1)%maxsize; sq-datasq-rearx; return

9、(TRUE); 顺序队列出队顺序队列出队datetype DEQUEUE(sequeue *sq) if (EMPTY(sq) printf(“queue is emptyn);return NULL; else sq-front(sq-front+1)%maxsize; return(sq-datasq-front); front 链队列结点类型定义链队列结点类型定义typedef struct node datatype data; struct node *next; linklist; typedef struct linklist *front,*rear; linkqueue;链队

10、列置队空链队列置队空SETNULL(linkqueue *q) q-frontmalloc(sizeof(linklist); q-front-nextNULL; q-rearq-front; 链队列判队空链队列判队空int EMPTY(linkqueue *q) if q-front=q-rear) return(TRUE); else return(FALSE); 链队列取队头结点链队列取队头结点datatype FRONT(linkqueue *q) if (EMPTY(q) printf(“queue is emptyn); return NULL; else return(q-fro

11、nt-next-data); 链队列入队链队列入队ENQUEUE(linkqueue *q,datatype x) q-rear-next(linklist *)malloc(sizeof(linklist); q-rearq-rear-next; q-rear-datax; q-rear-nextNULL; 链队列出队链队列出队datatype DEQUEUE(linkqueue *q) linklist *s; if (EMPTY(q) printf(“queue is emptyn);return NULL; else sq-front; q-frontq-front-next; fre

12、e(s); return(q-front-data); 0111011110101010010011110111001110011000011001101 2 3 4 5 6 7 8123456队列的运用举例求迷宫的最短途径队列的运用举例求迷宫的最短途径zxzy1-102-1+130+14+1+15+106+1-170-18-1-1需求处理的问题1：如何从某一坐标点出发搜索其周围的邻点需求处理的问题2：如何存储搜索途径需求处理的问题3：如何防止反复到达某坐标点步xypre1110222133324343需求处理的问题4：如何输出搜索途径1121314151617181920 x15256566

13、56y1663175488pre08910101112141616队列队列#define m 10#define n 15 typedef struct int x,y; int pre; sqtype;sqtype sq400; int mgm+1n+1;int zx8, zy8;void mglj( ) int i, j, v, front, rear, find x, y; sq1.x1; sq1.y1; sq1.pre0; front1; rear1; find=0; maze11-1; while(front=rear & !find) xsqfront.x; ysqfront.y; for (v=1;v=8;v+) ix+zxv; jy+zyv; if (mgij= =0) rear+; sqrear.xi; sqrear.yj; s