数据结构课件--第三章.ppt

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

1、第3章限定性线性表——栈和队列3.1栈3.2队列返回主目录3.1栈3.1.1栈的定义3.1.2栈的表示和实现3.1.3栈的应用举例3.1.4栈与递归的实现返回主目录栈的定义：栈作为一种限定性线性表，是将线性表的插入和删除运算限制为仅在表的一端进行。通常将表中允许进行插入、删除操作的一端称为栈顶(Top)，表的另一端被称为栈底(Bottom)。当栈中没有元素时称为空栈。栈的插入操作被形象地称为进栈或入栈，删除操作称为出栈或退栈。返回主目录根据栈定义，每次进栈的元素都被放在原栈顶元素之上而成为新的栈顶，而每次出栈的总是当前栈中“最新”的元素

2、，即最后进栈的元素。因此，栈又称为后进先出的线性表。简称为LIFO表。如下图所示：进栈、出栈图例进栈出栈进栈出栈栈顶栈底ana2a1返回主目录栈的抽象数据类型定义关系：栈中数据元素之间是线性关系数据元素：可以是任意类型的数据，但必须属于同一个数据对象。基本操作：InitStack（S）2.ClearStack（S）3.IsEmpty（S）4.IsFull（S）5.Push（S，x）6.Pop（S，x）7.GetTop（S，x）返回主目录3.1.2栈的表示和实现栈在计算机中主要有两种基本的存储结构：顺序存储结构和链式存储结构。顺序存储的栈

3、为顺序栈；链式存储的栈为链栈。返回主目录1.顺序栈顺序栈是用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时由于栈的操作的特殊性，还必须附设一个位置指针top（栈顶指针）来动态地指示栈顶元素在顺序栈中的位置。通常以top=-1表示空栈。返回主目录用C语言定义栈的顺序存储结构#defineTRUE1#defineFALSE0#defineStack_Size50typedefstruct{StackElementTypeelem[Stack_Size];/*用来存放栈中元素的一维数组*/inttop;

4、/*用来存放栈顶元素的下标*/}SeqStack;返回主目录顺序栈中的进栈和出栈图例AEDCBABAtoptoptoptop返回主目录顺序栈基本操作的实现1）初始化voidInitStack(SeqStack*S){/*构造一个空栈S*/S->top=-1;}返回主目录2）判栈空intIsEmpty(SeqStack*S)/*判栈S为空栈时返回值为真，反之为假*/{return(S->top==-1?TRUE:FALSE);}返回主目录3）判栈满intIsFull(SeqStack*S)/*判栈S为满时返回真，否则返回假*/{retur

5、n(S->top==Stack_Size?TRUE:FALSE);}返回主目录4）进栈intPush(SeqStack*S,StackElementTypex){if(S->top==Stack_Size)return(FALSE);/*栈已满*/S->top++;S->elem[S->top]=x;return(TRUE);}返回主目录5）出栈intPop(SeqStack*S,StackElementType*x){if(S->top==-1)/*栈为空*/return(FALSE);else{*x=S->elem[S->top];

6、S->top--;/*修改栈顶指针*/return(TRUE);}}返回主目录6）取栈顶元素intGetTop（SeqStackS,StackElementType*x）{/*将栈S的栈顶元素弹出，放到x所指的存储空间中，但栈顶指针保持不变*/if(S->top==-1)/*栈为空*/return(FALSE);else{*x=S->elem[S->top];return(TRUE);}}返回主目录两栈共享技术：主要利用了栈“栈底位置不变，而栈顶位置动态变化”的特性。首先为两个栈申请一个共享的一维数组空间S[M]，将两个栈的栈底分别放在

7、一维数组的两端，分别是0，M-1。共享栈的空间示意为：top[0]和top[1]分别为两个栈顶指示器。top[0]top[1]Stack：0M-1返回主目录两栈共享的数据结构定义#defineM100typedefstruct{StackElementTypeStack[M];StackElementTypetop[2];/*top[0]和top[1]分别为两个栈顶指示器*/}DqStack;返回主目录1）两栈共享的初始化操作算法voidInitStack(DqStack*S){S->top[0]=-1;S->top[1]=M;}返回主

8、目录2）两栈共享的进栈操作算法intPush(DqStack*S,StackElementTypex,inti){if(S->top[0]+1==S->top[1])/*栈已满*/return(FALSE)