[工学]数据结构第三章.ppt

《[工学]数据结构第三章.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、福州大学至诚学院3.1栈3.1.1抽象数据类型栈的定义3.1.2栈的表示与实现3.2栈的应用举例3.2.1数制转换3.2.2括号配对问题3.2.4迷宫求解*3.3栈和递归的实现3.4队列3.4.1抽象数据类型队列的定义3.4.2链队列--队列的链式表示与实现3.4.3循环队列--队列的顺序表示与实现第三章栈和队列福州大学至诚学院题目：将十进制数N转换为其他进制数输出基本原理：N=(ndivd)*d+nmodd“div”是整除运算，mod为求余运算。数制转换福州大学至诚学院toptop4top40top405例如：(1348)10=(2504)8，其运算过程如下：NNdiv8Nmod8

2、134816841682102125202计算顺序输出顺序top4052福州大学至诚学院栈栈的定义：操作受限制的线性表，只能在线性表的一端进行插入和删除运算。栈S=(a1，a2，a3，…an)按照按a1…an的次序进栈，如图：栈顶Top：插入、删除的这一端。栈底Bottom:不做任何操作的另一端。空栈：表中没有元素。LIFO：栈的修改是按后进先出的原则进行的。福州大学至诚学院栈的抽象数据类型定义ADTStack{数据对象：D={ai

3、ai属于Elemset,(i=1,2,…,n,n≥0)}数据关系：R1={＜ai-1,ai＞

4、ai-1,ai属于D,(i=2,3,…,n)}约定an为栈

5、顶,a1为栈底。基本操作：InitStack(&S);DestroyStack(&S);ClearStack(&S);StackEmpty(S);StackLength(S);GetTop(S,&e);Push(&S,e);Pop(&S,&e);StackTraverse(S,visit())}ADTStack福州大学至诚学院栈的基本操作InitStack(&S)操作结果:构造一个空的栈S。DestroyStack(&S)初始条件:栈S已经存在。操作结果:销毁栈S。福州大学至诚学院栈的基本操作StackEmpty(S)初始条件:栈S已经存在。操作结果:若栈S为空栈，则返回TURE;否

6、则返回FALSE。StackLength(S)初始条件:栈S已经存在。操作结果:返回栈S中的数据元素个数。GetTop(S,&e)初始条件:栈S已经存在且非空。操作结果:用e返回栈S中栈顶元素的值。福州大学至诚学院StackTraverse(S,visit())初始条件:栈S已经存在且非空。操作结果:从栈底到栈顶依次对S的每个元素调用函数visit()。一旦visit()失败，则操作失败。福州大学至诚学院栈的基本操作Push(&S,e)初始条件:栈S已经存在。操作结果:插入元素e为新的栈顶元素。Pop(&S,&e)初始条件:栈S已经存在且非空。操作结果:删除S的栈顶元素并用e返回其值

7、。ClearStack(&S)初始条件:栈S已经存在。操作结果:将栈S重置为空栈。福州大学至诚学院栈的顺序表示与实现---(顺序栈)#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefstruct{SElemType*base;/*在栈构造之前和销毁之后，base的值为NULL*/SElemType*top;/*栈顶指针*/intstacksize;/*当前已分配的存储空间，以元素为单位*/}SqStack;福州大学至诚学院顺序栈示意图*base*topstacksize初始空栈*top=*base;stacksize=STA

8、CK_INIT_SIZE*base*topstacksize......a1...aian顺序栈空栈的栈顶指针指向栈底非空栈中的栈顶指针始终在栈顶元素的下一个位置福州大学至诚学院top123450进栈A栈满BCDEF设数组维数为Mtop=base,栈空，此时出栈，则下溢（underflow)top=M,栈满，此时入栈则上溢（overflow)toptoptoptoptop123450空栈topbasebasetop出栈toptop栈空base栈底指针base,始终指向栈底位置；栈顶指针top,其初值指向栈底，始终在栈顶元素的下一个位置123450ABtop福州大学至诚学院顺序栈的操作

9、实现-InitStack//构造一个空的栈SStatusInitStack(SqStack*s){s->base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!s->base)return(OVERFLOW);s->top=s->base;s->stacksize=STACK_INIT_SIZE;returnOK;}福州大学至诚学院顺序栈的操作实现-GetTop//返回栈S中栈顶元素St