数据结构-第三章-栈和队列

第三章栈和队列3.1栈3.1.1抽象数据类型栈的定义3.1.2栈的表示和实现3.2栈的应用举例3.2.1数制转换3.2.2括号匹配的检验3.2.4行编辑程序3.2.5迷宫求解3.2.5表达式求值3.1.1栈3.1.1栈的定义及基本运算栈(Stack)是限制在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。当表中没有元素时称为空栈。假设栈S=(a1，a2，a3，…an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，…an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。栈是限定仅能在表尾一端进行插入、删除操作的线性表（a1,a2,...,ai-1,ai,ai+1,…,an）插入删除什么是栈一、栈的定义进行插入和删除的一端是浮动端，通常被称为栈顶，并用一个“栈顶指针”指示；而另一端是固定端，通常被称为栈底。通常将栈用下图的形式描述：1）限定在线性表的一端进行插入。2）限定在线性表的一端进行删除。3）后进先出（LastInFirstOut），简称为LIFO线性表。第一个进栈的元素在栈底，最后一个进栈的元素在栈顶，第一个出栈的元素为栈顶元素，最后一个出栈的元素为栈底元素。不含元素的栈称为空栈。出栈Pop进栈Push栈顶栈底topbottom空栈topbottoman...a2a1bottomtopbottomtopAABCDEAB栈操作图示A进栈BCDE进栈EDC出栈CDEtoptoptop栈的特点后进先出LIFO入栈与出栈topbottomtopbottomtoptoptop栈的表示和实现顺序栈：栈的顺序存储结构，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，指针top指向栈顶元素在顺序栈中的下一个位置，base为栈底指针，指向栈底的位置。base空栈a进栈b进栈aabtopbasetopbasetoptoptopabcdee进栈abcdef进栈溢出abde出栈cbasebasebasetop思考：假设有A,B,C三个元素进S栈的顺序是A,B,C，写出所有可能的出栈序列。CBAACBABCCABBACBCA如果是4个元素，那么它不可能的出栈序列有哪些？可能的出栈序列：12341243132413421432213421432314234124313241321434214321不可能出现的出栈序列：1423241331243142341241234132423142134312栈的数学性质若已知栈的输入序列为1,2,3…n,则输出序列有1/(n+1)*种.如：若输入序列为1,2,3,4,则输出序列有14种。以1为头：12341243132413421432以2为头：21342143231423412431以3为头：321432413421以4为头：4321nnc2四．写出下列程序段的输出结果（栈的元素类型SElemType为char）（8分）Voidmain(){StackS;charx,y;InitStack(S);x=’c’;y=’k’;Push(S,x);Push(S,’a’);Push(S,y);Pop(S,x);Push(S,’t’);Push(S,x);Pop(S,x);Push(S,’s’);while(!StackEmpty(S)){Pop(S,y);printf(y);};printf(x);}简述以下算法的功能Algo1(StackS){inti,n=0,A[255];While(!StackEmpty(S)){n++;pop(S,A[n]);}For(i=1;i=n;i++)push(S,A[i]);}Algo2(StackS,inte){StackT;intd;Initstack(T);While(!stackEmpty(S)){pop(s,d);if(d!=e)push(T,d);}While(!stackEmpty(T)){pop(T,d);push(S,d);}}3.1.2顺序栈由于栈是运算受限的线性表，因此线性表的存储结构对栈也适应。栈的顺序存储结构简称为顺序栈，它是运算受限的线性表。因此，可用数组来实现顺序栈。因为栈底位置是固定不变的，所以可以将栈底位置设置在数组的两端的任何一个端点；栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量top。例、一叠书或一叠盘子。栈的抽象数据类型的定义如下：anan-1a2a1……栈顶栈底顺序栈的类型表示:#defineSTACK_INIT_SIZE100；#defineSTACKINCREMENT10；typedefcharSElemtype;typedefstruct{//顺序栈定义SElemtype*base;//栈底指针SElemtype*top;//栈顶指针intstacksize；//当前已分配的全部存储空间}SeqStack；判栈空intStackEmpty(SeqStack*S){if(S-top==S-base)return1//判栈空,空则返回1elsereturn0;//否则返回0}判栈满intStackFull(SeqStack*S){if(S-top-S-base=S-StackSize)return1//判栈满,满则返回1elsereturn0;//否则返回0}顺序栈的基本运算:初始化InitStack(SeqStack*S){//置空栈S-base=(SElemtype*)malloc(STACK_INIT_SIZE*sizeof(SElemtype));if(!S-base)exit(OVERFLOW);S-top=S-base;S-stacksize=STACK_INIT_SIZE;Returnok;}入栈intPush(SeqStack*S,SElemtypex){//插入元素x为新的栈顶元素if(StackFull(S)){S-base=(SElemtype*)realloc(S-base,(S-stacksize+STACKINCREMENT)*sizeof(StackData));if(!S-base)exit(overflow);S-top=S-base+S-stacksize;S-stacksize+=STACKINCREMENT;//追加存储空间}*(S-top)=x;（S-top）++;Returnok}取栈顶元素intGetTop(SeqStack*S,SElemtype&x){//若栈空返回0,否则栈顶元素读到x并返回1if(StackEmpty(S))return0;x=*(S-top-1);return1;}出栈intPop(SeqStack*S,SElemtype&x){//若栈空返回0,否则栈顶元素退出到x并返回1if(StackEmpty(S))return0;--(S-top);x=*(S-top);return1;}求栈长intStacklength(SeqStack*S){returnS-top-S-base;}栈遍历voidStackTraverse(SeqStack*S){SElemtype*p;p=S-base;while(p!=S-top){printf(““,*p);p++;}}IntDestroyStack(SeqStack*S){if(S-base)free(S-base);returnOK;}置栈空IntClearStack(SeqStack*S){S-top=S-base;returnOK;}链式栈:栈的链接表示链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头适合于多栈操作top链式栈(LinkStack)的定义typedefintStackData;typedefstructnode{StackDatadata;//结点structnode*next;//链指针}StackNode;typedefstruct{StackNode*top;//栈顶指针}LinkStack;链式栈操作实现初始化voidInitStack(LinkStack*S){S-top=NULL;}入栈intPush(LinkStack*S,StackDatax){StackNode*p=(StackNode*)malloc(sizeof(StackNode));p-data=x;p-next=S-top;S-top=p;return1;}判栈空intStackEmpty(LinkStack*S){returnS-top==NULL;}出栈intPop(LinkStack*S,StackData&x){if(StackEmpty(S))return0;StackNode*p=S-top;S-top=p-next;x=p-data;free(p);return1;}取栈顶intGetTop(LinkStack*S,StackData&x){if(StackEmpty(S))return0;x=S-top-data;return1;}销毁栈intMakeEmpty(LinkStack*S){StackNode*p;While(S-top!=NULL){p=S-top;S-top=S-top-next;free(p);}}求栈长intStacklength(LinkStack*S){StackNode*p=S-top;intn=0;While(p!=NULL){n++;p=p-next;}returnn;}栈遍历voidStackTraverse(LinkStack*S){StackNode*p=S-top;;While(p!=NULL){printf(p-data);p=p-next;}}栈的应用举例数制转换行编辑程序迷宫求解表达式求值数制转换十进制数转换为八进制数。采用对十进制数除8取余的方法，可得到八进制数的倒序。N=(Ndivd)×d+Nmodd例如：（1348)10=(2504)8，其运算过程如下：NNdiv8Nmod8134816841682102125202计算顺序输出顺序voidconversion(){InitStack(S);scanf(%d,&N);while(N){Push(S,N%8);N=N/8;}while(!StackEmpty(S)){Pop(S,e);printf(%d,e);}}//conversion行编辑程序在用户输入一行的过程中，允许用户输入出差错，并在发现有误时可以及时更正。设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区;并假设“#”为退格符，“@”为退行符。假设从终端接受两行字符：whli##ilr#e（s#*s)outcha@putchar(*s=#++);实际有效行为：while(*s)putchar(*s++);VoidLineEdit(){InitStack(s);ch=getchar();while(ch!=EOF){//EOF为全文结束符while(ch!=EOF&&ch!='\n'){switch(ch){case'#':Pop(S,ch);break;case'@':ClearStack(S);break;//重置S为空栈default:Push(S,ch);break;}ch=getchar();//从终端接收下一个字符}//while将从栈底到栈顶的字符传送至调用过程的数据区；ClearS