第3章 链栈及栈的应用VIP免费

第3章链栈及栈的应用栈的链接存储结构及实现链栈：栈的链接存储结构特殊线性表——栈特殊线性表——栈firsta1a2an∧ai链栈需要加头结点吗？如何改造链表实现栈的链接存储？将哪一端作为栈顶？将链头作为栈顶，方便操作。链栈不需要附设头结点。栈的链接存储结构及实现栈顶栈底链栈：栈的链接存储结构特殊线性表——栈特殊线性表——栈topanan-1a1∧firsta1a2an∧ai两种示意图在内存中对应同一种状态topa1an-1an∧栈顶栈底3链栈栈的链式存储结构称为链栈，它是运算受限的单链表，其插入和删除操作仅限制在表头位置上进行.由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。其类型说明为：typedefstructStackNode{DataTypedatastructStackNode*next};StackNode*top;(1)初始化栈voidInitStack(StackNode*top){top=NULL;}(2)判断空栈intStackEmpty(StackNode*top){returntop==NULL;}(3)取栈顶DataTypeGetTop(StackNode*top){if(StackEmpty(p))error(“stackisempty.”);returntop–>data;}算法描述：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->next;deletep;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=(2504)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行编辑程序接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入错误，并在发现有误时可以及时更正。例如:用户发现输入错误时,输入”#”(退格符),以表示前一个字符无效;输入”@”(退行符),表示当前输入的一行无效;设一个栈接受输入,每输入一个字符,做如下判断:是无效符,删除前一个入栈的符号是退行符,删除前一行入栈的符号其它,入栈行编辑程序算法如下:voidLineEdit(){//利用字符栈S,从终端接收一行并传送至数据区InitStack(S);//构造空栈ch=getcher();//从终端接收第一个字符while(ch!=EOF){//EOF为全文结束符while(ch!=EOF&&ch!=‘\n’){switch(ch){case‘#’:Pop(S,c);//无效符,出栈case‘@’:ClearStack(S);//退行符,清空栈default:Push(S,ch);//其它,入栈}ch=getchar();//从终端接收下一个字符}//while//将从栈底到栈顶的栈内字符传送至调用过程的数据区ClearStack(S);if(ch!=EOF)ch=getchar();}DestroyStack(S);}//LindeEdit表达式的计算在计算机中进行算术表达式的计算是通过栈来实现的。(1)算术表达式的三种表示：中缀：——双目运算符出现在两个操作数中间,例：a+b前缀：——双目运算符出现在两个操作数前面,例：+ab后缀：——双目运算符出现在两个操作数后面,例：ab+(2)三种表达式之间的转换：按运算的优先次序全部加上括号，逐个括号写成另一种表示式（括号——*，/——+，-）注意：操作数出现的顺序不变3表达式求值三种表达式之间的转换：例将中缀表达式：——转换成后缀表达式（A+B）*D–E/（F+A*D）+CAB+FAD*+AB+D*EFAD*+/AB+D*EFAD*+/-AB+D*EFAD*+/-C+例：A+B*D–E/F+A*D+CABD*+EF/-AD*+C+把表达式翻译成正确的机器执行指令,要正确地解释表达式.算符优先法是根据算术四则运算的规定来编译或解释表达式的.表达式由操作数,运算符,界限符组成.操作数可以是变量或常量;此处考虑的运算符仅...