资源描述：
《第3章 链栈及栈的应用.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第3章链栈 及栈的应用栈的链接存储结构及实现链栈：栈的链接存储结构特殊线性表——栈firsta1a2an∧ai链栈需要加头结点吗？如何改造链表实现栈的链接存储？将哪一端作为栈顶？将链头作为栈顶，方便操作。链栈不需要附设头结点。栈的链接存储结构及实现栈顶栈底链栈：栈的链接存储结构特殊线性表——栈topanan-1a1∧firsta1a2an∧ai两种示意图在内存中对应同一种状态topa1an-1an∧栈顶栈底3链栈栈的链式存储结构称为链栈，它是运算受限的单链表，其插入和删除操作仅限制在表头位置上进行.由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。
2、栈顶指针就是链表的头指针。其类型说明为：typedefstructStackNode{DataTypedatastructStackNode*next};StackNode*top;(1)初始化栈voidInitStack(StackNode*top){top=NULL;}(2)判断空栈intStackEmpty(StackNode*top){return(top==NULL);}(3)取栈顶DataTypeGetTop(StackNode*top){if(StackEmpty(top))error(“stackisempty.”);returntop–>data
3、;}算法描述：voidPush(StackNode*top,DataTypex){s=(StackNode*)malloc(sizeof(StackNode));s->data=x;s->next=top;top=s;}topanan-1a1∧(4)入栈xstop操作接口：voidPush(StackNode*top,DataTypex){为什么没有判断栈满？算法描述：DataTypePop(StackNode*top){if(StackEmpty(top)error(“stackunderflow.”);x=top->data;p=top;top=top->ne
4、xt;free(p);returnx;}(5)出栈操作接口：DataTypePop(StackNode*top)topanan-1a1∧topptop++可以吗？3.2栈的应用举例1数制转换十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理:N=(ndivd)*d+nmodd(其中:div为整除运算,mod为求余运算)例如(1348)10=(2504)8，其运算过程如下：NNdiv8Nmod8134816841682102125202先入栈,再出栈入栈顺序:4,0,5,2.出栈顺序:2,5,0,4所以1348=(25
5、04)ovoidconversion(){//输入任意一个非负十进制整数,打印输出与其等值的八进制数InitStack(S);//初始化栈scanf(“%d”,N);//输入一个非负十进制数while(N){//非零时,循环push(S,N%8);//余数入栈N=N/8;}while(!StackEmpty(S)){Pop(S,e);//余数出栈printf(“%d”,e);}}//conversion2行编辑程序接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入错误，并在发现有误时可以及时更正。例如:用户发现输入错误时,输入”#”(退格符),以表示前一
6、个字符无效;输入”@”(退行符),表示当前输入的一行无效;设一个栈接受输入,每输入一个字符,做如下判断:是无效符,删除前一个入栈的符号是退行符,删除前一行入栈的符号其它,入栈行编辑程序算法如下:voidLineEdit(){//利用字符栈S,从终端接收一行并传送至数据区InitStack(S);//构造空栈ch=getcher();//从终端接收第一个字符while(ch!=EOF){//EOF为全文结束符while(ch!=EOF&&ch!=‘’){switch(ch){case‘#’:Pop(S,c);//无效符,出栈case‘@’:ClearStack(
7、S);//退行符,清空栈default:Push(S,ch);//其它,入栈}ch=getchar();//从终端接收下一个字符}//while//将从栈底到栈顶的栈内字符传送至调用过程的数据区ClearStack(S);if(ch!=EOF)ch=getchar();}DestroyStack(S);}//LindeEdit表达式的计算在计算机中进行算术表达式的计算是通过栈来实现的。(1)算术表达式的三种表示：中缀：——双目运算符出现在两个操作数中间,例：a+b前缀：——双目运算符出现在两个操作数前面,例：+ab后缀：——双目运算符出现在两个操作数后面,例：ab
8、+(2)三
