第3章-数据结构C语言描述(耿国华)学习资料.ppt

《第3章-数据结构C语言描述(耿国华)学习资料.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章限定性线性表—栈和队列3.1栈3.2队列3.1栈3.1.1栈的定义栈作为一种限定性线性表，是将线性表的插入和删除运算限制为仅在表的一端进行，通常将表中允许进行插入、删除操作的一端称为栈顶(Top)，因此栈顶的当前位置是动态变化的，它由一个称为栈顶指针的位置指示器指示。同时表的另一端被称为栈底(Bottom)。当栈中没有元素时称为空栈。栈的插入操作被形象地称为进栈或入栈，删除操作称为出栈或退栈。ADTStack数据元素：可以是任意类型的数据，但必须属于同一个数据对象。关系：栈中数据元素之间是线性关系。基本操作：（1）InitStack(S)操作前提：S为未初始

2、化的栈。操作结果：将S初始化为空栈。（2）ClearStack(S)操作前提：栈S已经存在。操作结果：将栈S置成空栈。（3）IsEmpty(S)操作前提：栈S已经存在。操作结果：判栈空函数，若S为空栈，则函数值为TRUE，否则为FALSE。（4）IsFull(S)操作前提：栈S已经存在。操作结果：判栈满函数，若S栈已满，则函数值为TRUE，否则为FALSE。（5）Push(S,x)操作前提：栈S已经存在。操作结果：在S的顶部插入(亦称压入)元素x；若S栈未满，将x插入栈顶位置，若栈已满，则返回FALSE，表示操作失败，否则返回TRUE。（6）Pop(

3、S,x)操作前提：栈S已经存在。操作结果：删除(亦称弹出)栈S的顶部元素，并用x带回该值；若栈为空，返回值为FALSE，表示操作失败，否则返回TRUE。（7）GetTop(S,x)操作前提：栈S已经存在。操作结果：取栈S的顶部元素。与Pop(S,x)不同之处在于GetTop(S,x)不改变栈顶的位置。3.1.2栈的表示和实现1.顺序栈顺序栈是用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时由于栈的操作的特殊性，还必须附设一个位置指针top（栈顶指针）来动态地指示栈顶元素在顺序栈中的位置。通常以top=-1表示空栈。顺序栈的存储

4、结构可以用C语言中的一维数组来表示。栈的顺序存储结构定义如下：＃defineTRUE1＃defineFALSE0＃defineStack-Size50typedefstruct{StackElementTypeelem［Stack-Size］;/*用来存放栈中元素的一维数组*/inttop;/*用来存放栈顶元素的下标*/}SeqStack;图3.2顺序栈中的进栈和出栈顺序栈基本操作的实现如下:(1)初始化。voidInitStack(SeqStack*S){/*构造一个空栈S*/S->top=-1;}(2)判栈空。intIsEmpty(SeqStac

5、k*S)/*判栈S为空栈时返回值为真，反之为假*/{return(S->top==-1?TRUE:FALSE);}(3)判栈满。intIsFull(SeqStack*S){return(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

6、*S,StackElementType*x){/*将栈S的栈顶元素弹出，放到x所指的存储空间中*/if(S->top==-1)/*栈为空*/return(FALSE);else{*x=S->elem［S->top］;S->top--;/*修改栈顶指针*/return(TRUE);}}(6)取栈顶元素。intGetTop（SeqStackS,StackElementType*x）{/*将栈S的栈顶元素弹出，放到x所指的存储空间中，但栈顶指针保持不变*/if(S->top==-1)/*栈为空*/return(FALSE);else{*x=S->e

7、lem［S->top］;return(TRUE);}}在栈的共享技术中最常用的是两个栈的共享技术：它主要利用了栈“栈底位置不变，而栈顶位置动态变化”的特性。首先为两个栈申请一个共享的一维数组空间S［M］，将两个栈的栈底分别放在一维数组的两端，分别是0，M-1。由于两个栈顶动态变化，这样可以形成互补，使得每个栈可用的最大空间与实际使用的需求有关。由此可见，两栈共享比两个栈分别申请M/2的空间利用率高。两栈共享的数据结构定义如下：＃defineM100typedefstruct{StackEle