数据结构(C语言)_3.doc

第三章 栈和队列第三章 栈和队列 本章介绍的是栈和队列的逻辑结构定义及在两种存储结构(顺序存储结构和链式存储结构)上如何实现栈和队列的基本运算。栈和队列： 从数据结构角度：操作受限的线性表限定性的数据结构，其基本操作是线性表操作的子集； 从数据类型角度：与线性表不同的抽象数据类型（多型）。两者的逻辑结构相同，但操作的种类和数目不同，用途大为不同。本章的重点：掌握栈和队列在两种存储结构上实现的基本运算；难点：循环队列中对边界条件的处理。3.1 栈一、抽象数据类型栈的定义栈（Stack）:限定仅在表尾进行插入或删除操作的线性表。栈的表尾称为栈顶，表头称为栈底，不含元素的空表称为空栈。假设栈S=(a1，a2，a3，an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出的线性表（Last In First Out ，LIFO）。栈的抽象数据类型定义：ADT Stack数据对象:D=ai|ai(- ElemSet,i=1,2,.,n,n=0)数据关:R1=|ai-1,ai(- D,i=2,.,n)基本操作:InitStack(&S) 构造一个空栈SDestroyStack(&S) 栈S存在则栈S被销毁ClearStack(&S) 栈S存在则清为空栈StackEmpty(S) 栈S存在则返回TRUE,否则FALSEStackLength(S) 栈S存在则返回S的元素个数,即栈的长度GetTop(S,&e) 栈S存在且非空则返回S的栈顶元素Push(&S,e) 栈S存在则插入元素e为新的栈顶元素入栈Pop(&S,&e) 栈S存在且非空，则删除S的栈顶元素并用e返回其值出栈StackTraverse(S,visit()栈S存在且非空，则从栈底到栈顶依次对S的每个数据元素调用函数visit()，一旦visit()失败，则操作失败ADT Stack二、栈的表示和实现 顺序栈由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针top指示栈顶元素在顺序栈中的位置。 栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量top例 一叠书或一叠盘子。要了解的是，在顺序栈中有上溢和下溢的概念。顺序栈好比一个盒子，在里头放了一叠书，当要用书的话只能从第一本开始拿(把盒子翻过来吗?)，那么当把书本放到这个栈中超过盒子的顶部时就放不下了(叠上去的不算)，这时就是上溢,上溢也就是栈顶指针指出栈的外面，显然是出错了。反之，当栈中已没有书时，再去拿，看看没书，把盒子拎起来看看盒底，还是没有，这就是下溢。下溢本身可以表示栈为空栈,因此可以用它来作为控制转移的条件。顺序栈的类C语言定义:typedef structSElemType *base;SElemType *top; /设栈顶栈底两指针的目的是便于判断栈是否为空int StackSize; /栈的当前可使用的最大容量.SqStack;一般说来，在初始化设空栈时，不应限定栈的最大容量，而是：先为栈分配一个基本容量，然后在应用过程中，当栈的空间不够使用时，再逐段扩大。顺序栈的的模块说明:struct STACK SElemType *base; SElemType *top; int stacksize; ; typedef struct STACK Sqstack; Status InitStack(SqStack &S); Status DestroyStack(SqStack &S); Status ClearStack(SqStack &S); Status StackEmpty(SqStack S); int StackLength(SqStack S); Status GetTop(SqStack S,SElemType &e); Status Push(SqStack &S,SElemType e); Status Pop(SqStack &S,SElemType &e);Status StackTraverse(SqStack S,Status (*visit)(); Status InitStack(SqStack &S) S.base=(SelemType *)malloc(STACK_INIT_SIZE *sizeof(ElemType);if(!S.base)exit(OVERFLOW); S.top=S.base; S.stacksize=STACK_INI_SIZE; return OK; /InitStack Status DestroyStack(SqStack &S) /DestroyStack Status ClearStack(SqStack &S) S.top=S.base; /ClearStackStatus StackEmpty(SqStack S) if(S.top=S.base) return TRUE; else return FALSE; /StackEmptyint StackLength(SqStack S); int i; SElemType *p; i=0; p=S.top;while(p!=S.base) p+; i+; /stackLengthStatus GetTop(SqStack S,SElemType &e); if(S.top=S.base) return ERROR; e=*(S.top-1); return OK; /GetTopStatus Push(SqStack &S,SElemType e); if(S.top - s.base=S.stacksize) S.base=(ElemType *) realloc(S.base, (S.stacksize + STACKINCREMENT) * sizeof(ElemType); if(!S.base) exit(OVERFLOW);S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; return OK; /PushStatus Pop(SqStack &S,SElemType &e); if(S.top=S.base) return ERROR; e=*-S.top; return OK; /Pop Status StackTraverse(SqStack S,Status (*visit)(); /StackTraverse以上伪代码的C语言源码#include#include#include#define ERROR 0#define TRUE 1#define FALSE 0#define OK 1#define EQUAL 1#define OVERFLOW -1#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef int Status ;struct STU char name20; char stuno10; int age; int score;typedef struct STU SElemType;struct STACK SElemType *base; SElemType *top; int stacksize;typedef struct STACK SqStack;typedef struct STACK *pSqstack;Status InitStack(SqStack *S);Status DestroyStack(SqStack *S);Status ClearStack(SqStack *S);Status StackEmpty(SqStack S);int StackLength(SqStack S);Status GetTop(SqStack S,SElemType *e);Status Push(SqStack *S,SElemType e);Status Pop(SqStack *S,SElemType *e);Status StackTraverse(SqStack S,Status (*visit)();Status InitStack(SqStack *S)(*S)=(SqStack *)malloc(sizeof(SqStack); (*S)-base=(SElemType *)malloc(STACK_INIT_SIZE *sizeof(SElemType); if(!(*S)-base)exit(OVERFLOW); (*S)-top=(*S)-base; (*S)-stacksize=STACK_INIT_SIZE; return OK;Status DestroyStack(SqStack *S)free(S-base); free(S);Status ClearStack(SqStack *S) S-top=S-base;Status StackEmpty(SqStack S)if(S.top=S.base) return TRUE; else return FALSE;int StackLength(SqStack S)int i;SElemType *p;i=0;p=S.top;while(p!=S.base) p+; i+; Status GetTop(SqStack S,SElemType *e)if(S.top=S.base) return ERROR; *e=*(S.top-1); return OK;Status Push(SqStack *S,SElemType e)if(S-top - S-base=S-stacksize) S-base=(SElemType *) realloc(S-base,(S-stacksize + STACKINCREMENT) * sizeof(SElemType);if(!S-base)exit(OVERFLOW); S-top=S-base+S-stacksize; S-stacksize += STACKINCREMENT;*(S-top+)=e; return OK;Status Pop(SqStack *S,SElemType *e)if(S-top=S-base) return ERROR; *e=*-S-top;return OK;Status StackPrintElem(SElemType * e)printf(%s %s %d %dn,e-name,e-stuno,e-age,e-score);Status StackTraverse(SqStack S,Status (*visit)()while(S.top!=S.base) visit(-S.top);main()SElemType e;SqStack *Sa;clrscr();printf(nn-SqStack Demo is running.-nn); printf(First is Push function.n);InitStack(&Sa);strcpy(,stu1); strcpy(e.stuno,100001);e.age=80; e.score=1000;printf( Now Stack is Empty.n); StackTraverse(*Sa,StackPrintElem); Push(Sa,e); printf( Now Stack has one element.n); StackTraverse(*Sa,StackPrintElem); strcpy(,stu3); strcpy(e.stuno,100002); e.age=80; e.score=1000; Push(Sa,e); printf( Now Stack has another element.n); StackTraverse(*Sa,StackPrintElem); printf( Now Pop Stack,the top elem put into variable e.n); Pop(Sa,&e); printf(%sn%sn%dn%dn,,e.stuno,e.age,e.score); printf( Lets see the left of Stacks elem:n); StackTraverse(*Sa,StackPrintElem); getch(); printf(nnnWelcom to visit nn); 链栈栈的链式存储结构称为链栈，它是运算是受限的单链表，插入和删除操作仅限制在表头位置上进行。链栈没有上溢的限制，它就象是一条一头固定的链子，可以在活动的一头自由地增加链环(结点)而不会溢出，链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要在头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。栈顶指针就是链表的头指针。链栈的类型说明如下：typedef struct stacknodedatatype data； struct stacknode *next；stacknode;Void initstack(seqstack *p) ptop=null;int stackempty(linkstack *p) return ptop=null;Void push(linkstack *p,datatype x) stacknode *q q=(stacknode*)malloc(sizeof(stacknode); qdata=x; qnext=ptop; ptop=p;Datatype pop(linkstack *p) datatype x; stacknode *q=ptop; if(stackempty(p) error(“stack underflow.”); x=qdata; ptop=qnext; free(q); return x;datatype stack_top(linkstack *p) if(stackempty(p) error(“stack is empty.”); return ptopdata;3.2 栈的应用举例由于其LIFO的固有特性，成为程序设计中的有用工具。一、栈应用之一：数制转换将十进制数转换成其它进制的数有一种简单的方法：例：十进制转换成八进制：(66)10=(102)866/8=8 余 28/8=1 余 01/8=0 余 1结果为余数的逆序:102 。先求得的余数在写出结果时最后写出，最后求出的余数最先写出，符合栈的先入后出性质，故可用栈来实现数制转换：void conversion() pSqStack S; SElemType e; int n; InitStack(&S); printf(Input a number to convert to OCT:n);scanf(%d,&n); if(n0) printf(nThe number must be over 0.); return;if(!n) Push(S,0); while(n) Push(S,n%8); n=n/8; printf(the result is: ); while(!StackEmpty(*S) Pop(S,&e); printf(%d,e);数制转换的C源程序：#include#include#include#define ERROR 0#define TRUE 1#define FALSE 0#define OK 1#define EQUAL 1#define OVERFLOW -1#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef int Status ;struct STU char name20; char stuno10; int age; int score;typedef struct STU SElemType;struct STACK SElemType *base; SElemType *top; int stacksize;typedef struct STACK SqStack;typedef struct STACK *pSqstack;Status InitStack(SqStack *S);Status DestroyStack(SqStack *S);Status ClearStack(SqStack *S);Status StackEmpty(SqStack S);int StackLength(SqStack S);Status GetTop(SqStack S,SElemType *e);Status Push(SqStack *S,SElemType e);Status Pop(SqStack *S,SElemType *e);Status StackTraverse(SqStack S,Status (*visit)();Status InitStack(SqStack *S) (*S)=(SqStack *)malloc(sizeof(SqStack); (*S)-base=(SElemType *)malloc(STACK_INIT_SIZE *sizeof(SElemType); if(!(*S)-base)exit(OVERFLOW);(*S)-top=(*S)-base;(*S)-stacksize=STACK_INIT_SIZE;return OK;Status DestroyStack(SqStack *S)free(S-base); free(S);Status ClearStack(SqStack *S)S-top=S-base;Status StackEmpty(SqStack S)if(S.top=S.base) return TRUE; else return FALSE;int StackLength(SqStack S)int i;SElemType *p;i=0;p=S.top;while(p!=S.base) p+; i+; Status GetTop(SqStack S,SElemType *e)if(S.top=S.base) return ERROR; *e=*(S.top-1); return OK;Status Push(SqStack *S,SElemType e)if(S-top - S-base=S-stacksize) S-base=(SElemType *) realloc(S-base,S-stacksize + STACKINCREMENT) * sizeof(SElemType);if(!S-base) exit(OVERFLOW);S-top=S-base+S-stacksize;S-stacksize += STACKINCREMENT;*(S-top+)=e; return OK;Status Pop(SqStack *S,SElemType *e) if(S-top=S-base) return ERROR; *e=*-S-top; return OK;Status StackPrintElem(SElemType * e)printf(%s %s %d %dn,e-name,e-stuno,e-age,e-score);Status StackTraverse(SqStack S,Status (*visit)()while(S.top!=S.base) visit(-S.top);main()SElemType e;SqStack *Sa;clrscr();printf(nn-SqStack Demo is running.-nn);printf(First is Push function.n);InitStack(&Sa);strcpy(,stu1);strcpy(e.stuno,100001);e.age=80;e.score=1000;printf( Now Stack is Empty.n);StackTraverse(*Sa,StackPrintElem);Push(Sa,e);printf( Now Stack has one element.n);StackTraverse(*Sa,StackPrintElem);strcpy(,stu3);strcpy(e.stuno,100002);e.age=80;e.score=1000;Push(Sa,e);printf( Now Stack has another element.n);StackTraverse(*Sa,StackPrintElem);printf( Now Pop Stack,the top elem put into variable e.n);Pop(Sa,&e);printf(%sn%sn%dn%dn,,e.stuno,e.age,e.score);printf( Lets see the left of Stacks elem:n);StackTraverse(*Sa,StackPrintElem);getch();printf(nnnWelcom to visit nn);二、栈应用之二：括号匹配的检验假设表达式中充许括号嵌套,则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例：（）（） （）三、栈应用之三：行编辑一个简单的行编辑程序的功能是：接受用户从终端输入的程序或数据，并存入用户的数据区。允许用户输入出错时可以及时更正。可以约定为退格符，以表示前一个字符无效，为退行符，表示当前行所有字符均无效。例：在终端上用户输入为whli#ilr#e(s#*s) 应为 while(*s)void LineEdit() pSqStack S,T; char str1000; int strlen=0; char e; char ch; InitStack(&S); InitStack(&T); ch=getchar();while(ch!=EOFILE) while(ch!=EOFILE&ch!=n) switch(ch) case #: Pop(S,&ch); break; case : ClearStack(S); break; default: Push(S,ch); break; ch=getchar(); if(ch=n) Push(S,ch);while(!StackEmpty(*S) Pop(S,&e); Push(T,e); while(!StackEmpty(*T) Pop(T,&e); strstrlen+=e; if(ch!=EOFILE) ch=getchar(); strstrlen=0; printf(n%s,str); DestroyStack(S); DestroyStack(T); #include#include#include#define EOFILE typedef char SElemType;#include stack.hStatus visit(SElemType * e)printf(%c, *e);void LineEdit() pSqStack S,T; char str1000; int strlen=0; char e; char ch; InitStack(&S); InitStack(&T); ch=getchar(); while(ch!=EOFILE) while(ch!=EOFILE&ch!=n) switch(ch) case #: Pop(S,&ch); break;case : ClearStack(S); break;default: Push(S,ch); break; ch=getchar(); if(ch=n) Push(S,ch);while(!StackEmpty(*S) Pop(S,&e);Push(T,e);while(!StackEmpty(*T) Pop(T,&e);strstrlen+=e;if(ch!=EOFILE) ch=getchar(); strstrlen=0; printf(n%s,str); DestroyStack(S); DestroyStack(T);main() printf(nnnn); LineEdit();四、栈应用之四：表达式求值(P52)表达式求值是程序设计语言编译中的一个最基本问题，它的实现是栈应用的一个典型例子。一个程序设计语言应该允许设计者根据需要用表达式描述计算过程，编译器则应该能分析表达式并计算出结果。表达式的要素是运算符、操作数、界定符、算符优先级关系。例：1+2*3有+,*两个运算符，*的优先级高,1,2,3是操作数。 界定符有括号和表达式结束符等。要把一个表达式翻译成正确求值的一个机器指令序列,或直接对表达式求值,首先要能够正确解释表达式.要对表达式求值,首先要了解算术四则运算的规则.即: 先乘除,后加减；从左算到右；先括号内，后括号外。算符优先法就是根据这个运算优先关系的规定来实现对表达式的编译或解释执行的。任何一个表达式都是由数,运算符和界限符组成的,称它们为单词。仅讨论简单算术表达式的求值问题.这种表达式只含加,减,乘,除等四种运算符，可将它推广到一般的表达式上。把运算符和界限符统称为算符,它们构成的集合命名为OP。根据上述三条运算规则，在运算的每一步中,任意两个相继出现的算符1和2之间的优先关系至多是下面三种关系之一：12，1的优先权高。为实现算符优先算法,可以使用两个工作栈.一个称作OPTR,用以寄存运算符；另一个称作POND ,用以寄存操作数或运算结果。算法基本思想： 置操作数栈为空栈，表达式起始符为运算符栈的栈底元素； 依次读表达式中每个字符，若是操作数则进OPND栈，若是运算符，则和OPTR栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕。(即OPTR栈的栈顶元素和当前读入的字符均为#)优先关系的函数；orerate为进行二元运算ab的函数，如果是编译表达式，则产生这个运算的一组相应指令并返回存放结果的中间变量名；如果解释执行表达式，则直接进行该运算，并返回运算结果。例 利用算法对算术表达式3*（7-2）求值，操作过程如下所示。char EvaluateExpression() SqStack *OPND,*OPTR; char c,x,theta; char a,b; InitStack(&OPTR); Push(OPTR,#); InitStack(&OPND); c=getchar(); while(c!=#|GetTop(*OPTR)!=#) if(!In(c,OP) Push(OPND,c);c=getchar(); else switch(Precede(GetTop(*OPTR),c) case : Pop(OPTR,&theta); Pop(OPND,&b); Pop(OPND,&a); Push(OPND,Operate(a,theta,b);break; c=GetTop(*OPND); DestroyStack(OPTR); DestroyStack(OPND); return c; 五、栈应用之五：迷宫求解（P51，算法3.3）3.3 栈与递归的实现一、递归的定义及分类递归：若在一个函数、过程或者数据结构定义的内部，直接或间接出现定义本身的应用（一个直接调用自己或通过一系列的过程调用语句间接地调用自己的过程）。二、递归的应用 有很多数学函数是递归定义的，如：阶乘函数： | 1 n=0 Fact(n)= | n*Fact(n-1) n0 Fibonacci数列： | 0 n=0 Fib(n)= 1 n=1 | Fib(n-1)+Fib(n-2) 其它 有的数据结构，如二叉树，广义表，由于结构本身固有的递归特性，也可以用递归描述； 还有一类问题，虽然问题本身没有明显的递归结构，但用递归求解比迭代求解更简单，如：八皇后问题，Hanoi塔问题等。例 Hanoi塔问题：假设有三个分别命名为X,Y,Z的塔座，在塔座X上插有N个直径大小个不相同，以小到大编号为1，2，.的圆盘.现在要求将X轴上的N个圆盘移至塔座Z上并且仍按同样的顺序叠排，圆盘移动是必须遵循下列规则： 每次只能移动一个圆盘。 圆盘可以插在X,Y,Z中的任意一个塔座上。 任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。分析： 当N=1时，问题比较简单，只要将编号为1的圆盘从塔座X上直接移至塔座Z上即可；当N1时，需利用塔座Y作辅助塔座，若能设法将压在编号为N的圆盘之上的N-1个圆盘从塔座X移至塔座Y上，则可先将编号为N的圆盘从塔座X移至塔座Z上，然后再将塔座Y上的N-1个圆盘移至塔座Z上。而如何将N-1个圆盘从一个塔座移至另一个塔座的问题是一个和原问题具有相同特征属性的问题，只是问题的规模小1，因此可以用同样的方法求解。算法描述： （P55 算法3.5）三、递归的模型递归模型反映一个递归问题的递归结构，例如： f(1)=1 f(n)=n*f(n-1) n=0) 数据关系: R1= | ai-1,ai(- D,i=2,.,n) 基本操作： InitQueue(&Q) 构造一个空队列QDestroyqueue(&Q) 队列Q存在则销毁QClearQueue(&Q) 队列Q存在，则将Q清为空队列QueueEmpty(Q) 队列Q存在，若Q为空队列则返回TRUE，否则返回FALSEQueueLenght(Q) 队列Q存在,返回Q的元素个数（队列的长度）GetHead(Q,&e) Q为非空队列,用e返回Q的队头元素EnQueue(&Q,e) 队列Q存在,插入元素e为Q的队尾元素DeQueue(&Q,&e) Q为非空队列,删除Q的队头元素,并用e返回其值QueueTraverse(Q,vivsit() Q存在且非空,从队头到队尾，依次对Q的每个数据元素调用函数visit()。一旦visit()失败，则操作失败ADT Queue二、顺序队列队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。顺序队列的表示： 和顺序表一样，顺序队列用一个向量空间来存放当前队列中的元素。 由于队列的队头和队尾的位置是变化的，设置两个指针front和rear分别指示队头元素和队尾元素在向量空间中的位置，它们的初值在队列初始化时均应置为0。 顺序队列的基本操作入队时：将新元素插入rear所指的位置，然后将rear加1。出队时：删去front所指的元素，然后将front加1并返回被删元素。注意：当头尾指针相等时，队列为空；在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。 顺序队列中的溢出现象 “下溢”现象当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。 “真上溢”现象当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。 “假上溢”现象由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为假上溢现象。【例】假设下述操作序列作用在初始为空的顺序队列上： EnQueue，DeQueue，EnQueue，DeQueue， 尽管在任何时刻，队列元素的个数均不超过1，但是只要该序列足够长，事先定义的向量空间无论多大均会产生指针越界错误。二、循环队列为充分利用向量空间，克服假上溢现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。循环队列中进行出队、入队操作时，头尾指针仍要加1，朝前移动。只不过当头尾指针指向向量上界（QueueSize-1）时，其加1操作的结果是指向向量的下界0。这种循环意义下的加1操作可以描述为： 方法一：if(i+1=QueueSize) /i表示front或rear i=0; else i+; 方法二利用模运算i=(i+1)%QueueSize；循环队列边界条件处理：循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件front=rear来判别队列是