栈的表示和应用.doc

《栈的表示和应用.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验三栈的表示和应用一、实验目的1.掌握栈这种数据结构特性及其主要存储结构-顺序存储和链式存储结构。2.了解和掌握递归程序设计的基本原理和方法。3.学会在现实生活中灵活运用。4.保存的文件名为：学号后2位姓名Linkstack.c二、知识点栈：属于一种操作受限的线性表，只在表的一端进行插入和删除操作的线性表。又称为后进先出LIFO(LastInFirstOut)或先进后出FILO(FirstInLastOut)线性表。栈顶(Top)：允许进行插入、删除操作的一端，又称为表尾。用栈顶指针(top)来指示栈顶元素。空栈：当表中没有元素时称为空栈。1.栈的顺序存储结构及实现。#incl

2、ude#include#defineMAXSIZE20/*数组最大界限*/typedefintElemType;/*数据元素类型*/typedefstruct{ElemTypea[MAXSIZE];/*一维数组子域*/inttop;/*栈顶指针子域*/}SqStack;/*栈的顺序结构体类型*/2、栈的链式存储结构#include#includetypedefstructnode//定义结点类型{intdata;structnode*next;}Stacknode,*Linkstack;//Linksta

3、ck为指向结构体的指针类型//等价Stacknode*2三、实验内容1、写程序实现栈的初始化，置空，入栈，出栈及输出栈内数据的函数，并调试。注意：函数类型与调用方式一致。提示：编写五个操作的函数，然后在主函数内对其进行调用。LinkstackInit_stack()//初始化栈intEmpty_stack(Linkstacktop)//判断空栈LinkstackPush_stack(Linkstacktop,intx)//元素入栈LinkstackPop_stack(Linkstacktop,int*x)//元素出栈voidPri_stack(Linkstacktop)//输出栈

4、中元素2、栈的应用。在第1题调试正确的基础上，写一个函数实现数据的进制转换。如：十进制数108,转换为八进制数为154，即（108）10=（154）8提示：voidConver(intn,intd)//进制转换（除以基数、取余、倒序）｛//用循环辗转相除，将余数入栈//将栈内的数输出｝3、利用栈的思想，则中缀表达式(A+B)*D+E/(F+A*D)对应的后缀表达式为。（只需写出结果）提示：中缀转变为后缀表达式，操作数输出，操作符进栈。1、进栈的操作符优先级要高于栈顶的操作符，否则先让栈顶的操作符先出栈，直到高于栈顶的优先级，才可入栈。2、扫描表达式前入栈#，表达式扫描完再入栈#。

5、3、（）内操作符优先级>（）优先级>（）外操作符优先级4、优先级相同的操作符，先入栈的高于后入栈的。2