数据结构chap3

《数据结构chap3》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第三章栈和队列线性表插入删除Insert(L,i,x)Delete(L,i)(1≤i≤n+1)(1≤i≤n)Insert(L,n+1,x)Delete(L,n)Insert(L,n+1,x)Delete(L,1)栈队列栈和队列可以看成是“插入”和“删除”受限定的线性表。3.1栈的类型定义3.3栈类型的实现3.2栈的应用举例3.4队列的类型定义3.5队列类型的实现3.6队列的应用举例ADTStack{}ADTStack数据对象：D＝{ai

2、ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{

3、-1,ai>

4、ai-1,ai∈D,i=2,...,n}约定an端为栈顶，a1端为栈底基本操作：栈是限定只能在表尾进行插入和删除的线性表。ClearStack(&S)(栈清空)GetTop(S,&e)(求栈顶元素)DestroyStack(&S)(销毁栈结构)StackEmpty(S)(判空)Push(&S,e)(入栈)StackLength(S)(求栈长)Pop(&S,&e)(出栈)InitStack(&S)(构造空栈)StackTraverse(S,visit())(遍历栈)a1a2an……GetTop(S,&e

5、)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。a1a2an……Push(&S,e)初始条件：栈S已存在。操作结果：插入e为栈S中新的栈顶元素。ea1a2an-1……Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素,并将它从栈中删除。an例一、数制转换例二、括号匹配的检验例三、迷宫求解例四、表达式求值例五、实现递归数制转换的原理为：N=(Ndivd)×d+Nmodd例如：（1348)10转换成(2504)8的运算过程如下：NNdiv8Nmod8计算顺序输出顺序134816

6、841682102125202voidconversion(){//显示和输入的十进制数对应的八进制数值InitStack(S);scanf("%d",N);while(N){Push(S,N%8);N=N/8;}while(!StackEmpty(S)){Pop(S,e);printf("%d",e);}}//conversion检验含两种括弧的表达式中括弧匹配的正确性。如表达式中（［］（））或［（［］［］）］等为正确的匹配，［（］）或（［（）]或[()])均为不正确的匹配。检验括弧匹配的方法可用“按期待的急迫程

7、度进行处理”描述之。[例如考虑下列括号序列：([][())]]可见，括弧匹配也遵循“后进先出”的规律。如何表示下列“不匹配”的情况？到来的右括弧非是所“期待”的;来了一个“不速之客”;直到结束，也没有等到“期待”的匹配;算法的设计思想：1）凡出现左括弧，则进栈；2）凡出现右括弧，首先检查栈是否空？若栈空，则表明该“右括弧”多余否则和栈顶元素比较，若相匹配，则“左括弧出栈”否则表明不匹配3）表达式检验结束时，若栈空，则表明表达式中匹配正确否则表明“左括弧”有余。boolmatching(charexp[],intn)

8、{//检测长度为n的字符序列exp中的括弧是否匹配inti=0;mat=true;InitStack(S);while(i

9、往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止,如果所有可能的通路都试探过，还是不能走到终点，那就说明该迷宫不存在从起点到终点的通道。#################Q#########################Q#######结论:1．从入口进入迷宫之后，不管在迷宫的哪一个位置上，都是先往东走，如果走得通就继续往东走，如果在某个位置上往东走不通的话，就依次试探往南、往西和往北的方向，依着某个走得通的方向继续往前直到出口为止；2．如果在某个位置上四个方向都走不通的话，就退回到前

10、一个位置，换一个方向再试，如果这个位置已经没有方向可试了就再退一步，如果所有已经走过的位置的四个方向都试探过了，一直退到起始点都没有走通，那就说明这个迷宫根本不通；求迷宫路径算法的基本思想是：若当前位置“可通”，则纳入路径，继续前进;若当前位置“不可通”，则后退，换方向继续探索;若四周“均无通路”，则将当前位置从路径中删除出去。设定当前位置的初值为入口位置；