资源描述：
《《数据结构》ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构(DATASTRUCTURE)第三章栈和队列栈(Stack)栈的应用递归队列(Queue)23.1栈(Stack)1）栈的定义限定在表尾进行插入和删除操作的线性表允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)特点后进先出(LIFO)3ADTStack{数据对象:D＝{ai
2、ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{
3、ai-1,ai∈D,i=2,...,n}基本操作：InitStack(&S):栈的初始化DestoryStack(&S):销毁栈SPush(&S,e):进栈Po
4、p(&S):出栈GetTop(S):取栈顶元素IsEmpty(S):判栈空否……}2)栈的抽象数据类型41)存储特点：利用一组地址连续的存储单元依次存放栈元素附设指针top指示栈顶元素在顺序栈中的位置2)顺序栈的表示#defineStackInitSize100;//存储空间初始分配量typedefintStackElementType；typedefstruct{StackElementTypedata[StackInitSize]；/*栈存储空间用一个预设的长度的一维数组来实现*/inttop；/*栈顶指针*/}SeqStack；3.1.1栈的顺序
5、存储—顺序栈5①进栈（入栈）分析首先判断栈满？（栈满:s->top==StackInitSize)若栈满，则不能进栈操作栈顶指针加1s->top++;数据元素入栈s->data[s->top]=x;3)基本操作的实现6算法voidPush(SeqStack*s,StackElementTypex){if(s->top==StackInitSize){printf("栈满!栈发生上溢，程序运行终止!");exit(0);}else{s->top++;/*栈顶指针加1，指向新的栈顶*/s->data[s->top]=x;/*将数据元素x压入栈*/}re
6、turn;}7分析首先判断栈空？（栈空:(s->top==-1)数据元素出栈temp=s->data[s->top]栈顶指针减1s->top--算法StackElementTypePop(SeqStack*s){StackElementTypetemp;if(IsEmpty(s)){printf("栈空！栈发生下溢，程序运行终止!");exit(0);}else{temp=s->data[s->top];s->top--;returntemp;}}②出栈（退栈）8顺序栈演示：9多栈处理栈浮动技术n个栈共享一个数组空间V[m]设立栈顶指针数组t[n+
7、1]和栈底指针数组b[n+1]，t[i]和b[i]分别指示第i个栈的栈顶与栈底各栈初始分配空间s=m/n指针初始值t[0]=b[0]=-1b[n]=m-1t[i]=b[i]=b[i-1]+s,i=1,2,…,n-110113.1.2栈的链式存储—链式栈1）存储特点是一种特殊形式的单链表（无表头结点；插入、删除操作限定在表头端进行）链式栈无栈满问题，空间可扩充122）链式栈的表示：同单链表typedefstructnode{SElemtypedata;structnode*next;}linkstack;13①进栈（入栈）分析首先申请一个结点空间(用
8、p指向该结点)若链栈不为空，将*p插入链表的第一个结点之前：p->next=top;top=p;否则：p->next=NULL;top=p;3）基本运算的实现14分析首先判断栈空？（栈空:top=NULL)若不空，判断*top是否为栈中最后一个元素如不是，则将*top从链表中删除：top=top->next否则，令top=NULL释放栈顶元素空间;②出栈（退栈）153.1.3栈的应用举例例1：简单应用：数制转换问题问题：将十进制数N转换为r进制的数，其转换方法利用辗转相除法。分析：所转换的r进制数按低位到高位的顺序产生，而通常的输出是从高位到低位的，恰
9、好与计算过程相反16例2中缀表达式求值问题：根据算符优先法对表达式求值,所讨论的算术运算符包括：+、-、*、/、%、^(乘方)和括号()。运算规则为：运算符的优先级为:()→^→＊、/、%→+、-；有括号时先算括号内的，后算括号外的，多层括号由内向外进行；乘方连续出现时先算最右面的；17分析：表达式作为一个串，如表达式“3+2*4-5”,其求值过程为：自左向右扫描表达式，当扫描到3*2时不能马上计算，因后面可能有更高的运算需要两个栈：对象栈OPND和算符栈OPTR;自左至右扫描表达式,若当前字符是运算对象，入OPND栈;对运算符，若这个运算符比栈顶运算
10、符高则入栈，继续向后处理，若这个运算符比栈顶运算符低则从OPND栈出栈两个数，从OPTR栈出栈
