《数据结构c语言描述(耿国华)第3章剖析》由会员分享，可在线阅读，更多相关《数据结构c语言描述(耿国华)第3章剖析（94页珍藏版）》请在金锄头文库上搜索。
1、第3章 限定性线性表栈和队列,3.1 栈 3.2 队列,3.1 栈,3.1.1 栈的定义 栈作为一种限定性线性表，是将线性表的插入和删除运算限制为仅在表的一端进行，通常将表中允许进行插入、删除操作的一端称为栈顶(Top)，因此栈顶的当前位置是动态变化的，它由一个称为栈顶指针的位置指示器指示。同时表的另一端被称为栈底(Bottom)。当栈中没有元素时称为空栈。栈的插入操作被形象地称为进栈或入栈，删除操作称为出栈或退栈。,图3.1 栈,ADT Stack 数据元素： 可以是任意类型的数据，但必须属于同一个数据对象。 关系： 栈中数据元素之间是线性关系。 基本操作： （1） InitStack(S)
2、 操作前提： S为未初始化的栈。 操作结果： 将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，表示操作失败，否则
3、返回TRUE。 （6） Pop(S, x) 操作前提：栈S已经存在。 操作结果：删除(亦称弹出)栈S的顶部元素，并用x带回该值；若栈为空，返回值为FALSE，表示操作失败，否则返回TRUE。 （7） GetTop(S, x) 操作前提： 栈S已经存在。 操作结果：取栈S的顶部元素。与Pop(S, x)不同之处在于GetTop(S,x)不改变栈顶的位置。 ,3.1.2 栈的表示和实现,1. 顺序栈 顺序栈是用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时由于栈的操作的特殊性， 还必须附设一个位置指针top（栈顶指针）来动态地指示栈顶元素在顺序栈中的位置。通
4、常以top=-1表示空栈。顺序栈的存储结构可以用C语言中的一维数组来表示。 栈的顺序存储结构定义如下：,define TRUE 1 define FALSE 0 define Stack-Size 50 typedef struct StackElementType elemStack-Size; /*用来存放栈中元素的一维数组*/ int top; /*用来存放栈顶元素的下标*/ SeqStack;,图3.2 顺序栈中的进栈和出栈,顺序栈基本操作的实现如下: (1) 初始化。,void InitStack(SeqStack *S) /*构造一个空栈S*/ S-top= -1; (2) 判栈空
5、。 int IsEmpty(SeqStack *S) /*判栈S为空栈时返回值为真， 反之为假*/ return(S-top=-1?TRUE:FALSE); ,(3) 判栈满。 int IsFull(SeqStack *S) return(S-top = Stack-Size?TRUE:FALSE); (4) 进栈。 int Push(SeqStack *S, StackElementType x) if(S-top= Stack-Size) return(FALSE); /*栈已满*/ S-top+; S-elemS-top=x; return(TRUE); ,(5) 出栈。 int Pop
6、(SeqStack * S, StackElementType *x) /* 将栈S的栈顶元素弹出， 放到x所指的存储空间中 */ if(S-top=-1) /*栈为空*/ return(FALSE); else *x= S-elemS-top; S-top-; /* 修改栈顶指针 */ return(TRUE); ,(6) 取栈顶元素。 int GetTop（SeqStack S, StackElementType *x） /* 将栈S的栈顶元素弹出， 放到x所指的存储空间中， 但栈顶指针保持不变 */ if(S-top=-1) /*栈为空*/ return(FALSE); else *x
7、= S-elemS-top; return(TRUE); ,在栈的共享技术中最常用的是两个栈的共享技术： 它主要利用了栈“栈底位置不变，而栈顶位置动态变化”的特性。首先为两个栈申请一个共享的一维数组空间SM，将两个栈的栈底分别放在一维数组的两端，分别是0， M-1。 由于两个栈顶动态变化，这样可以形成互补，使得每个栈可用的最大空间与实际使用的需求有关。由此可见，两栈共享比两个栈分别申请M/2的空间利用率高。 两栈共享的数据结构定义如下：,define M 100 typedef struct StackElementType StackM; StackElementType top2; /*t
8、op0和top1分别为两个栈顶指示器*/ DqStack;,图3.3 共享栈,初始化操作。 void InitStack(DqStack *S) S-top0=-1; S-top1=M; ,(2) 进栈操作算法。 int Push(DqStack *S, StackElementType x, int i) /*把数据元素x压入i号堆栈*/ if(S-top0+1=S-top1) /*栈已满*/ return(FALSE); switch(i) case 0: S-top0+;,S-StackS-top0=x; break; case 1: S-top1-; S-StackS-top1=x;
9、break; default: /*参数错误*/ return(FALSE) return(TRUE); ,(3) 出栈操作算法。 int Pop(DqStack *S, StackElementType *x, int i) /* 从i 号堆栈中弹出栈顶元素并送到x中 */ switch(i) case 0: if(S-top0=-1) return(FALSE); *x=S-StackS-top0; S-top0-; break; case 1: if(S-top1=M) return(FALSE); *x=S-StackS-top1; S-top1+; break; default: r
10、eturn(FALSE); return(TRUE); ,2. 链栈,图3.4 链栈示意图,链栈的结构可用C语言定义如下：,typedef struct node StackElementType data; struct node *next; LinkStackNode; typedef LinkStackNode *LinkStack;,(1) 进栈操作。,int Push(LinkStack top, StackElementType x) /* 将数据元素x压入栈top中 */ LinkStackNode * temp; temp=(LinkStackNode * )malloc(s
11、izeof(LinkStackNode); if(temp=NULL) return(FALSE); /* 申请空间失败 */ temp-data=x; temp-next=top-next; top-next=temp; /* 修改当前栈顶指针 */ return(TRUE); ,(2) 出栈操作。,int Pop(LinkStack top, StackElementType *x) /* 将栈top的栈顶元素弹出， 放到x所指的存储空间中 */ LinkStackNode * temp; temp=top-next; if(temp=NULL) /*栈为空*/ return(FALSE)
12、; top-next=temp-next; *x=temp-data; free(temp); /* 释放存储空间 */ return(TRUE); ,3.1.3 栈的应用举例,1. 数制转换 假设要将十进制数N转换为d进制数，一个简单的转换算法是重复下述两步， 直到N等于零： X = N mod d (其中mod为求余运算) N = N div d (其中div为整除运算),void Conversion(int N) /*对于任意的一个非负十进制数N， 打印出与其等值的二进制数*/ Stack S; int x; /* S为顺序栈或链栈 */ InitStack( ,2. 括号匹配问题 假
13、设表达式中包含三种括号：圆括号、 方括号和花括号， 它们可互相嵌套， 如( ( ) )或( ( ( ) ) )等均为正确的格式， 而 ) 或 ( ) 或( 均为不正确的格式。 在检验算法中可设置一个栈， 每读入一个括号，若是左括号，则直接入栈， 等待相匹配的同类右括号；若读入的是右括号， 且与当前栈顶的左括号同类型，则二者匹配， 将栈顶的左括号出栈， 否则属于不合法的情况。另外，如果输入序列已读尽，而栈中仍有等待匹配的左括号，或者读入了一个右括号，而栈中已无等待匹配的左括号，均属不合法的情况。当输入序列和栈同时变为空时， 说明所有括号完全匹配。,void BracketMatch(char *
14、str) = /* str中为输入的字符串， 利用堆栈技术来检查该字符串中的括号是否匹配*/ = Stack S; int i; char ch; InitStack( i+) /*对字符串中的字符逐一扫描*/ switch(stri) case (: case : case :,Push( /*已匹配的左括号出栈*/,else printf(n对应的左右括号不同类!); return; /*switch*/ /*for*/ if(IsEmpty(S) printf(n括号匹配!); else printf(n左括号多余!); ,3. 表达式求值,表达式求值是高级语言编译中的一个基本问题， 是
15、栈的典型应用实例。 任何一个表达式都是由操作数(operand)、 运算符(operator)和界限符(delimiter)组成的。操作数既可以是常数， 也可以是被说明为变量或常量的标识符；运算符可以分为算术运算符、 关系运算符和逻辑运算符三类；基本界限符有左右括号和表达式结束符等。,1） 无括号算术表达式求值,表达式计算 程序设计语言中都有计算表达式的问题， 这是语言编译中的典型问题。 (1) 表达式形式： 由运算对象、 运算符及必要的表达式括号组成； (2) 表达式运算： 运算时要有一个正确的运算形式顺序。 由于某些运算符可能具有比别的运算符更高的优先级，因此表达式不可能严格的从左到右， 见图3.5。,图3.5 表达式运算及运算符优先级,
