栈和队列（数据结构与算法）课件.ppt

《栈和队列（数据结构与算法）课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、栈队列递归第三章栈和队列栈(Stack)定义:是限定仅在表尾进行插入或删除操作的线性表。允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)特点：后进先出(LIFO)a1topbottoman....进栈出栈栈的主要操作Push(S,x);//进栈Pop(S);//出栈Top(S);//取栈顶Setnull(S);//置空栈Empty(S);//判栈空否StackFull(S);//判栈满否}栈的表示和实现顺序栈：栈的顺序存储结构，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，指针top指向栈顶元素在顺序栈中的下一个位置，base为

2、栈底指针，指向栈底的位置。base空栈a进栈b进栈aabtopbasetopbasetoptoptopabcdee进栈abcdef进栈溢出abde出栈cbasebasebasetop顺序栈的类型表示:#definemaxsize64typedefchardatatype;typedefstruct{//顺序栈定义{datatypedata[maxsize];inttop;//栈顶指针}seqstack；seqstack*s;判栈空intEmpty(seqstack*S){if(S->top>=0)return1//判栈空,空则返回1elsereturn0;//否

3、则返回0}判栈满intStackFull(seqstack*S){if(S->top==maxsize-1)return1;//判栈满,满则返回1elsereturn0;//否则返回0}顺序栈的基本运算:初始化voidSetnull(seqstack*S)//置空栈{S->top=-1;}入栈Seqstack*Push(seqstack*S,datatypex)//插入元素x为新的栈顶元素{if(S->top==maxsize-1){printf(“overflow”);returnnull;}else{S->top++;S->data[S->top]=x;}r

4、eturns;}取栈顶元素DatatypeTop(seqstack*S)//若栈空返回0,否则栈顶元素读到x并返回{if(Empty(S)){printf(“stackisempty”);returnnull;}elsereturn(S->data[S->top]);}出栈datatypepop(seqstack*S)//若栈空返回0,否则栈顶元素退出到x并返回1{if(Empty(S)){printf(“underflow”);returnnull;}else{S->top--;return(S->data[S->top+1]);}}链式栈:栈的链接表示链式栈

5、无栈满问题，空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头适合于多栈操作top链式栈(LinkStack)的定义typedefintdatatype;typedefstructnode{datatypedata;//结点structnode*next;//链指针}linkstack;linkstack*top;链式栈操作实现入栈Linkstack*Push(linkstack*top,datatypex){linkstack*p;*p=malloc(sizeof(linkstack));p->data=x;p->next=top;returnp;}出栈Li

6、nklist*Pop(LinkStack*S,datatype&x){linkstack*p;if(top==null){printf(“underflow”);returnnull;}else{p=top;x=p->data;top=top->next;free(p);returntop;}}栈的应用举例数制转换行编辑程序迷宫求解表达式求值数制转换N=(Ndivd)×d+Nmodd例如：（1348)10=(2504)8，其运算过程如下：NNdiv8Nmod8134816841682102125202输出顺序计算顺序voidconversion(){int

7、e,N;seqstact*S;Setnull(S);scanf("%d",&N);while(N){Push(S,N%8);N=N/8;}while(!Empty(S)){e=Pop(S);printf("%d",e);}}//conversion行编辑程序在用户输入一行的过程中，允许用户输入出差错，并在发现有误时可以及时更正。设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区;并假设“#”为退格符，“@”为退行符。假设从终端接受两行字符：whli##ilr#e（s#*s)outcha@putchar(*s=#++);实际有效行为：while

8、(*s)putchar(