第3章 数据结构C语言描述(耿国华)

第3章限定性线性表——栈和队列第3章限定性线性表—栈和队列3.1栈3.2队列第3章限定性线性表——栈和队列3.1栈3.1.1栈的定义栈作为一种限定性线性表，是将线性表的插入和删除运算限制为仅在表的一端进行，通常将表中允许进行插入、删除操作的一端称为栈顶(Top)，因此栈顶的当前位置是动态变化的，它由一个称为栈顶指针的位置指示器指示。同时表的另一端被称为栈底(Bottom)。当栈中没有元素时称为空栈。栈的插入操作被形象地称为进栈或入栈，删除操作称为出栈或退栈。第3章限定性线性表——栈和队列图3.1栈an…a2a1进栈出栈栈顶栈底进栈出栈(a)栈的示意图(b)铁路调序栈的表示第3章限定性线性表——栈和队列ADTStack数据元素：可以是任意类型的数据，但必须属于同一个数据对象。关系：栈中数据元素之间是线性关系。基本操作：（1）InitStack(S)操作前提：S为未初始化的栈。操作结果：将S初始化为空栈。（2）ClearStack(S)操作前提：栈S已经存在。操作结果：将栈S置成空栈。第3章限定性线性表——栈和队列（3）IsEmpty(S)操作前提：栈S已经存在。操作结果：判栈空函数，若S为空栈，则函数值为TRUE，否则为FALSE。（4）IsFull(S)操作前提：栈S已经存在。操作结果：判栈满函数，若S栈已满，则函数值为TRUE，否则为FALSE。第3章限定性线性表——栈和队列（5）Push(S,x)操作前提：栈S已经存在。操作结果：在S的顶部插入(亦称压入)元素x；若S栈未满，将x插入栈顶位置，若栈已满，则返回FALSE，表示操作失败，否则返回TRUE。（6）Pop(S,x)操作前提：栈S已经存在。操作结果：删除(亦称弹出)栈S的顶部元素，并用x带回该值；若栈为空，返回值为FALSE，表示操作失败，否则返回TRUE。（7）GetTop(S,x)操作前提：栈S已经存在。操作结果：取栈S的顶部元素。与Pop(S,x)不同之处在于GetTop(S,x)不改变栈顶的位置。第3章限定性线性表——栈和队列3.1.2栈的表示和实现1.顺序栈顺序栈是用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时由于栈的操作的特殊性，还必须附设一个位置指针top（栈顶指针）来动态地指示栈顶元素在顺序栈中的位置。通常以top=-1表示空栈。顺序栈的存储结构可以用C语言中的一维数组来表示。栈的顺序存储结构定义如下：第3章限定性线性表——栈和队列＃defineTRUE1＃defineFALSE0＃defineStack-Size50typedefstruct{StackElementTypeelem［Stack-Size］;/*用来存放栈中元素的一维数组*/inttop;/*用来存放栈顶元素的下标*/}SeqStack;第3章限定性线性表——栈和队列图3.2顺序栈中的进栈和出栈第3章限定性线性表——栈和队列顺序栈基本操作的实现如下:(1)初始化。voidInitStack(SeqStack*S){/*构造一个空栈S*/S-top=-1;}(2)判栈空。intIsEmpty(SeqStack*S)/*判栈S为空栈时返回值为真，反之为假*/{return(S-top==-1?TRUE:FALSE);}第3章限定性线性表——栈和队列(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);}第3章限定性线性表——栈和队列(5)出栈。intPop(SeqStack*S,StackElementType*x){/*将栈S的栈顶元素弹出，放到x所指的存储空间中*/if(S-top==-1)/*栈为空*/return(FALSE);else{*x=S-elem［S-top］;S-top--;/*修改栈顶指针*/return(TRUE);}}第3章限定性线性表——栈和队列(6)取栈顶元素。intGetTop（SeqStackS,StackElementType*x）{/*将栈S的栈顶元素弹出，放到x所指的存储空间中，但栈顶指针保持不变*/if(S-top==-1)/*栈为空*/return(FALSE);else{*x=S-elem［S-top］;return(TRUE);}}第3章限定性线性表——栈和队列在栈的共享技术中最常用的是两个栈的共享技术：它主要利用了栈“栈底位置不变，而栈顶位置动态变化”的特性。首先为两个栈申请一个共享的一维数组空间S［M］，将两个栈的栈底分别放在一维数组的两端，分别是0，M-1。由于两个栈顶动态变化，这样可以形成互补，使得每个栈可用的最大空间与实际使用的需求有关。由此可见，两栈共享比两个栈分别申请M/2的空间利用率高。两栈共享的数据结构定义如下：＃defineM100typedefstruct{StackElementTypeStack［M］;StackElementTypetop［2］;/*top［0］和top［1］分别为两个栈顶指示器*/}DqStack;第3章限定性线性表——栈和队列图3.3共享栈Stack:0M－1top[0]top[1]第3章限定性线性表——栈和队列(1)初始化操作。voidInitStack(DqStack*S){S-top［0］=-1;S-top［1］=M;}第3章限定性线性表——栈和队列(2)进栈操作算法。intPush(DqStack*S,StackElementTypex,inti){/*把数据元素x压入i号堆栈*/if(S-top［0］+1==S-top［1］)/*栈已满*/return(FALSE);switch(i){case0:S-top［0］++;第3章限定性线性表——栈和队列S-Stack［S-top［0］］=x;break;case1:S-top［1］--;S-Stack［S-top［1］］=x;break;default:/*参数错误*/return(FALSE)}return(TRUE);}第3章限定性线性表——栈和队列(3)出栈操作算法。intPop(DqStack*S,StackElementType*x,inti){/*从i号堆栈中弹出栈顶元素并送到x中*/switch(i){case0:if(S-top［0］==-1)return(FALSE);*x=S-Stack［S-top［0］］;S-top［0］--;break;case1:if(S-top［1］==M)return(FALSE);*x=S-Stack［S-top［1］］;S-top［1］++;break;default:return(FALSE);}return(TRUE);}第3章限定性线性表——栈和队列2.链栈图3.4链栈示意图第3章限定性线性表——栈和队列链栈的结构可用C语言定义如下：typedefstructnode{StackElementTypedata;structnode*next;}LinkStackNode;typedefLinkStackNode*LinkStack;第3章限定性线性表——栈和队列(1)进栈操作。intPush(LinkStacktop,StackElementTypex)/*将数据元素x压入栈top中*/{LinkStackNode*temp;temp=(LinkStackNode*)malloc(sizeof(LinkStackNode));if(temp==NULL)return(FALSE);/*申请空间失败*/temp-data=x;temp-next=top-next;top-next=temp;/*修改当前栈顶指针*/return(TRUE);}第3章限定性线性表——栈和队列(2)出栈操作。intPop(LinkStacktop,StackElementType*x){/*将栈top的栈顶元素弹出，放到x所指的存储空间中*/LinkStackNode*temp;temp=top-next;if(temp==NULL)/*栈为空*/return(FALSE);top-next=temp-next;*x=temp-data;free(temp);/*释放存储空间*/return(TRUE);}第3章限定性线性表——栈和队列3.1.3栈的应用举例1.假设要将十进制数N转换为d进制数，一个简单的转换算法是重复下述两步，直到N等于零：X=Nmodd(其中mod为求余运算)N=Ndivd(其中div为整除运算)第3章限定性线性表——栈和队列voidConversion(intN){/*对于任意的一个非负十进制数N，打印出与其等值的二进制数*/StackS;intx;/*S为顺序栈或链栈*/InitStack(&S);while(N0){x=N%2;Push(&S,x);/*将转换后的数字压入栈S*/N=N/2;}while(！IsEmpty(S)){Pop(&S,&x);printf(″%d″,x);}}第3章限定性线性表——栈和队列2.括号匹配问题假设表达式中包含三种括号：圆括号、方括号和花括号，它们可互相嵌套，如(［{}］(［］))或({(［］［()］)})等均为正确的格式，而{［］})}或{［()］或(［］}均为不正确的格式。在检验算法中可设置一个栈，每读入一个括号，若是左括号，则直接入栈，等待相匹配的同类右括号；若读入的是右括号，且与当前栈顶的左括号同类型，则二者匹配，将栈顶的左括号出栈，否则属于不合法的情况。另外，如果输入序列已读尽，而栈中仍有等待匹配的左括号，或者读入了一个右括号，而栈中已无等待匹配的左括号，均属不合法的情况。当输入序列和栈同时变为空时，说明所有括号完全匹配。第3章限定性线性表——栈和队列voidBracketMatch(char*str)/*str［］中为输入的字符串，利用堆栈技术来检查该字符串中的括号是否匹配*/={StackS;inti;charch;InitStack(&S);For(i=0;str［i］![KG-*2]=′\0′;i++)/*对字符串中的字符逐一扫描*/{switch(str［i］){case′(′:case′［′:case′{′:第3章限定性线性表——栈和队列Push(&S,str［i］);break;case′)′:case′］′:case′}′:if(IsEmpty(S)){printf(″\n右括号多余!″);return;}else{GetTop(&S,&ch);if(Match(ch,str［i］))/*用Match判断两个括号是否匹配*/Pop(&S,&ch);/*已匹配的左括号出栈*/第3章限定性线性表——栈和队列else{printf(″\n对应的左右括号不同类!″);return;}}}/*switch*/}/*for*/if(IsEmpty(S))printf(″\n括号匹配!″);elseprintf(″\n左括号多余!″);}第3章限定性线性表——栈和队列3.表达式求值表达式求值是高级语言编译中的一个基本问题，是栈的典型应用实例。任何一个表达式都是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。操作数既可以是常数，也可以是被说明为变量或常量的标识符；运算符可以分为算术运算符、关系运算符和逻辑运算符三类；基本界限符有左右括号和表达式结束符等。第3章限定性线性表——栈和队列1）表达式计算程序设计语言中都有计算表达式的问题，这是语言编译中的典型问题。(1)表达式形式：由运算对象、运算符及必要的表达式括号组成；(2)表达式