第3章栈和队列栈

1、带头结点的单链表为空的判定条件是（哈尔滨工业大学）A.H=NULLB.H->next=NULLC.H->next=HD.H!=NULL2、将图中S结点加到P所指结点之后，其语句是：(浙江大学)A.s->next=p+1p->next=sB.(*p).next=s(*s).next=(*p).nextC.s->next=p->nextp->next=s->nextD.s->next=p->nextp->next=sAPCBS3.下面关于线性表的叙述中，错误的是哪一个？（北方交通大学）线性表采用顺序储存，必须占用一片连续的存储单元线性表采用顺序储存，便于进行插入和删除操作线性表采用链式储存，不必占用一片连续的储存单元线性表采用链式储存，便于插入和删除操作4.某线性表中最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，这样采用（）储存方式最节省时间。（哈尔滨工业大学）A顺序表B双向链表C单链表5.线性表的逻辑顺序和物理顺序总是一致的这种说法A正确B不正确6.线性表若是采用链式存储，要求内存中可用存储单元的地址A必须连续B部分地址必须连续C一定是不连续的D连续不连续都可以7.非空循环单链表L的尾结点P满足A.p->next=NULLB.p=NULLC.p->next=LD.p=L本章小结线性表的顺序表示与链式表示:从空间方面看：顺序存储空间是静态分配的，程序运行之前必须明确规定存储元素得多少，过大造成空间的浪费，过小会溢出。链式存储的空间是动态分配的，利用率高，但是链表中每个结点都要由指针域，因此从存储密度来说是不经济的从时间方面看：顺序表是一种随机存储的结构，在数据的查找时时间复杂度为O(1)但是插入和删除时为O(n)链式存储在数据的查找时时间复杂度为O(n)但是插入和删除时为O(1)3.1栈3.1.1栈的定义3.1.2栈的顺序存储结构及其基本运算的实现3.1.3栈的链式存储结构及其基本运算的实现3.1.4栈的应用例子

栈是一种操作受限的线性表。栈是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。

3.1.1栈的定义

栈顶栈底出栈进栈栈示意图栈顶的当前位置是动态的,栈顶的当前位置由一个称为栈顶指针的位置指示器指示。表的另一端称为栈底。当栈中没有数据元素时,称为空栈。数据的插入操作通常称为进栈或入栈,数据的删除操作通常称为退栈或出栈。栈顶top栈底botton出栈进栈栈示意图A1A2A3A4A5A6A7栈是一种限制存取点的线性结构，即只允许在栈顶进行出栈和入栈的操作。所以，栈还叫做“后进先出”表

例3.1设一个栈的输入序列为A,B,C,D,则借助一个栈所得到的输出序列不可能是

。（北京航天航空大学） (A)A,B,C,D (B)D,C,B,A (C)A,C,D,B (D)D,A,B,C答:可以简单地推算,得容易得出D,A,B,C是不可能的,因为D先出来,说明A,B,C,D均在栈中,按照入栈顺序,在栈中顺序应为D,C,B,A,出栈的顺序只能是D,C,B,A。所以本题答案为D。

例3.2一个栈的输入序列12345，则下列序列中不可能是栈的输出序列的是(南开大学，山东大学，北京理工大学)A23415B54132C23145D15432答案：B

例3.3设n个元素进栈序列是1,2,3,…,n,其输出序列是p1,p2,…,pn,若p1=3,则p2的值

。 (A)一定是2 (B)一定是1 (C)不可能是1 (D)以上都不对答:当p1=3时,说明1,2,3先进栈,立即出栈3,然后可能出栈,即为2,也可能4或后面的元素进栈,再出栈。因此,p2可能是2,也可能是4,…,n,但一定不能是1。所以本题答案为C。顺序栈进栈和出栈示意图TOP栈指针—代表的是物理位序data[MaxSize]栈空TOP=-1栈满TOP=MaxSize-1思考：如何表示栈顶元素?栈的几种基本运算如下:初始化栈InitStack():构造一个空栈s。进栈Push(s,e):将元素e插入到栈s中作为栈顶元素(3)求栈的长度StackLength(s):返回栈s中的元素个数。(4)判断栈是否为空StackEmpty(s):若栈s为空,则返回1；否则返回0。

(5)出栈Pop(s,&e):从栈s中退出栈顶元素,并将其值赋给e。(6)取栈顶元素GetTop(s,&e):返回当前的栈顶元素,并将其值赋给e。(7)显示栈中元素DispStack(s):从栈顶到栈底顺序显示栈中所有元素。(8)销毁栈ClearStack(s):释放栈s占用的存储空间。3.1.2栈的顺序存储结构及其基本运算实现

假设栈的元素个数最大不超过正整数MaxSize,所有的元素都具有同一数据类型ElemType,则可用下列方式来定义栈类型SqStack:

typedefstruct{ ElemTypedata[MaxSize]； inttop； /*栈指针*/}SqStack；在顺序栈中实现栈的基本运算算法:(1)初始化栈initStack()建立一个新的空栈s,实际上是将栈顶指针指向-1即可。对应算法如下:

SqStack*InitStack(void){ s=(SqStack*)malloc(sizeof(SqStack));s->top=-1; returns;

}

43210(a)初始化空栈Top=-1(2)进栈Push(s,e)算法思想：若栈满返回0；在栈不满的条件下,先将栈指针增1,然后在该位置上插入元素e，返回1。

intPush(SqStack*s,ElemTypee){ if(s->top==MaxSize-1)return0; /*栈满的情况,即栈上溢出*/ s->top++; s->data[s->top]=e; return1;

}a(b)元素a入栈dcba(c)元素b、c、d入栈4321043210Top=3Abcde(3)显示栈中元素DispStack(s)从栈顶到栈底顺序显示栈中所有元素。对应算法如下:

voidDispStack(SqStack*s){ inti; for(i=s->top;i>=0;i--) printf("%c",s->data[i]); printf("\n");}(4)求栈的长度StackLength(s)返回栈s中的元素个数,即栈指针加1的结果。对应算法如下:

intStackLength(SqStack*s){ return(s->top+1);}(5)判断栈是否为空StackEmpty(s)栈S为空的条件是s->top==-1。对应算法如下:

intStackEmpty(SqStack*s){ return(s->top==-1);}(6)出栈Pop(s,&e)在栈不为空的条件下,先将栈顶元素赋给e,然后将栈指针减1。对应算法如下:

intPop(SqStack*s,ElemType*e){ if(s->top==-1)return0; /*栈为空的情况,即栈下溢出*/ *e=s->data[s->top]; s->top--; return1;}(7)取栈顶元素GetTop(s,&e)在栈不为空的条件下,将栈顶元素赋给e。对应算法如下:

intGetTop(SqStack*s,ElemType&e){ if(s->top==-1)return0; /*栈为空的情况,即栈下溢出*/ e=s->data[s->top]; return1;}(8)销毁栈ClearStack(&s)释放栈s占用的存储空间。对应算法如下:

voidClearStack(SqStack*&s){ free(s);}编写一个程序exam3-1，实现顺序栈的各种基本运算，并在此基础上设计一个主程序完成如下功能初始化栈s;判断栈s是否非空;依次进栈元素a,b,c,d,e;判断栈s是否非空;输出栈的长度;输出从栈顶到栈底元素;输出出栈序列;判断栈s是否为空;释放栈.3.1.3栈的链式存储结构及其基本运算的实现

采用链式存储的栈称为链栈,这里采用单链表实现。链栈的优点是不存在栈满上溢的情况。我们规定栈的所有操作都是在单链表的表头进行的,下图是头结点为*lhead的链栈,第一个数据结点是栈顶结点,最后一个结点是栈底结点。栈中元素自栈顶到栈底依次是a1、a2、…、an。链栈示意图

链栈中数据结点的类型LiStack定义如下:

typedefstructlinknode{ ElemTypedata; /*数据域*/structlinknode*next; /*指针域*/}LiStack;在链栈中,栈的基本运算算法如下:(1)初始化栈initStack(&s)建立一个空栈s。实际上是创建链栈的头结点,并将其next域置为NULL。对应算法如下:

LiStack*InitStack(){

LiStack*

s; s=(LiStack*)malloc(sizeof(LiStack)); s->next=NULL; returns;}^s(2)进栈Push(&s,e)将新数据结点插入到头结点之后。对应算法如下:

voidPush(LiStack*s,ElemTypee){ LiStack*p; p=(LiStack*)malloc(sizeof(LiStack)); p->data=e; p->next=s->next;/*插入*p结点作为第一个数据结点*/ s->next=p;}(3)求栈的长度StackLength(s)从第一个数据结点开始扫描单链表,用i记录访问的数据结点个数,最后返回i值。对应算法如下:

intStackLength(LiStack*s){ inti=0; LiStack*p; p=s->next; while(p!=NULL) {i++;p=p->next;} return(i);}(4)判断栈是否为空StackEmpty(s)栈S为空的条件是s->next==NULL,即单链表中没有数据结点。对应算法如下:

intStackEmpty(LiStack*s){ return(s->next==NULL);}^s(5)显示栈中元素DispStack(s)从第一个数据结点开始扫描单链表,并输出当前访问结点的数据域值。对应算法如下:

voidDispStack(LiStack*s){ LiStack*p=s->next; while(p!=NULL) { printf("%c",p->data); p=p->next; } printf("\n");}(6)出栈Pop(&s,&e)在栈不为空的条件下,将头结点后继数据结点的数据域赋给e,然后将其删除。对应算法如下:

intPop(LiStack*s,ElemType&e){ LiStack*p; if(s->next==NULL)return0;/*栈空的情况*/ p=s->next; /*p指向第一个数据结点*/ e=p->data; s->next=p->next; free(p); return1;}(7)取栈顶元素GetTop(s)在栈不为空的条件下,将头结点后继数据结点的数据域赋给e。对应算法如下:

intGetTop(LiStack*s,ElemType&e){

LiStack*p; if(s->next==NULL)return0;/*栈空的情况*/ p=s->next; e=p->data; return1;}(8)销毁栈ClearStack(&s)释放栈s占用的全部存储空间。对应算法如下:

voidClearStack(LiStack*&s){ LiStack*p=s->next; while(p!=NULL) { free(s); s=p; p=p->next; }}编写一个程序exam3-2，实现顺序栈的各种基本运算，并在此基础上设计一个主程序完成如下功能初始化链栈s;判断链栈s是否非空;依次进链栈元素a,b,c,d,e;判断链栈s是否非空;输出链栈的长度;输出从栈顶到栈底元素;输出出链栈序列;判断链栈s是否为空;释放链栈.

exam3-3假设表达式中允许包含三种括号:圆括号、方括号和大括号。编写一个算法判断表达式中的括号是否正确配对。解:设置一个括号栈,扫描表达式：遇到左括号(包括(、[和{)时进栈,遇到右括号时,若栈是相匹配的左括号,则出栈,否则,返回0。若表达式扫描结束,栈为空,返回1表示括号正确匹配,否则返回0。

intcorrect(LiStack*&Head,charexp[],intlength){ inti,flag=1; chare;

for(i=0;i<length&&flag==1;i++) if(exp[i]=='{'||exp[i]=='['||exp[i]=='(') Push(Head,exp[i]); elseswitch(exp[i]) { case'}':GetTop(Head,e);if(e=='{')Pop(Head,e); else flag=0; break; case']':GetTop(Head,e);if(e=='[')Pop(Head,e); else flag=0; break; case')':GetTop(Head,e);if(e=='(')Pop(Head,e); else flag=0; break; } returnflag;}3.1.4栈的应用例子1.exam3-4表达式求值这里限定的表达式求值问题是:用户输入一个包含“+”、“-”、“*”、“/”、正整数和圆括号的合法数学表达式,计算该表达式的运算结果。在程序语言中,运算符位于两个操作数中间的表达式称为中缀表达式。例如：1+2*3就是一个中缀表达式,中缀表达式是最常用的一种表达式方式。对中缀表达式的运算一般遵循“先乘除,后加减,从左到右计算,先括号内,后括号外”的规则。因此,中缀表达式不仅要依赖运算符优先级,而且还要处理括号。所谓后缀表达式,就是运算符在操作数的后面,如1+2*3的后缀表达式为123*+。在后缀表达式中已考虑了运算符的优先级,没有括号,只有操作数和运算符。

对后缀表达式求值过程是:从左到右读入后缀表达式,若读入的是一个操作数,就将它入数值栈,若读入的是一个运算符op,就从数值栈中连续出栈两个元素(两个操作数),假设为x和y,计算xopy之值,并将计算结果入数值栈；对整个后缀表达式读入结束时,栈顶元素就是计算结果。

算术表达式求值过程是:先将算术表达式转换成后缀表达式,然后对该后缀表达式求值。假设算术表达式中的符号以字符形式由键盘输入,并存放在字符型数组str中,其后缀表达式存放在字符型数组exp中,在将算术表达式转换成后缀表达式的过程中用一个字符型数组op作为栈。将算术表达式转换成后缀表示的方法如下:while(从exp读取字符ch,ch!='\0'){若ch为数字,将后续的所有数字均依次存放到postexp中,并以字符“#”标志数值串结束。若ch为左括号“(”,则将此括号进栈到运算符栈op中。若ch为右括号“)”,则将运算符栈op中左括号“(”以前的运算符依次出栈并存放到postexp中,然后将左括号“(”删除。若ch运算符优先级小于或等于op栈顶运算符的优先级(除栈顶运算符为“(”外)的优先级,则依次出栈并存入到postexp中,然后将ch进栈。}若字符串exp扫描完毕,则将运算栈op中的所有运算符依次出栈并存放到postexp中。最后得到后缀表达式postexp。中缀表达式后缀表达式对于表达式“(56-20)/(4+2)”,其转换成后缀表达式的过程如下：exp操作过程oppostexp(56-20)/(4+2)遇到ch为“(”,将此括号进栈op。(

56-20)/(4+2)遇到ch为数字,将56存入postexp中,并插入一个字符“#”。(56#-20)/(4+2)遇到ch为“-”,由于op中“(”以前没有字符,则直接将ch进栈op中。(-56#20)/(4+2)遇到ch为数字,将20#存入数组exp中。(-56#20#exp操作过程oppostexp)/(4+2)遇到ch为“)”,则将栈op中“(”以前的字符依次出栈并存入postexp中,然后将“(”删除。

56#20#-/(4+2)遇到ch为“/”,将将ch进栈op中。/56#20#-(4+2)遇到ch为“(”,将此括号进栈op中。/(56#20#-4+2)遇到ch为数字,将4#存入数组postexp中。/(56#20#-4#exp操作过程oppostexp+2)遇到ch为“+”,由于op栈顶运算符为“(”,则直接将ch进栈op中。/(+56#20#-4#2)遇到ch为数字,将2#存入postexp中。/(+56#20#-4#2#)遇到ch为“)”,则将栈op中“(”以前的字符依次出栈并存放到postexp中,然后将“(”出栈。/56#20#-4#2#+

str扫描完毕,则将栈op中的所有运算符依次弹出并存放到postexp中,得到后缀表达式。

56#20#-4#2#+/将算术表达式str转换成后缀表达式expvoidtrans(charstr[],charexp[]){ struct { chardata[MaxSize]; /*存放运算符*/ inttop; /*栈指针*/ }op; /*定义运算符栈*/ charch; inti=0,t=0; /*t作为exp的下标,i作为str的下标*/ op.top=-1; ch=str[i];i++;while(ch!='\0') /*str表达式未扫描完时循环*/{switch(ch) {case'(': /*判定为左括号*/ op.top++;op.data[op.top]=ch;break; case')': /*判定为右括号*/ while(op.data[op.top]!='(') {exp[t]=op.data[op.top];op.top--;t++;} op.top--;break; case'+':case'-': /*判定为加或减号*/ while(op.top!=-1&&op.data[op.top]!='(') {exp[t]=op.data[op.top];op.top--;t++;} op.top++;op.data[op.top]=ch;break; case'*':case'/':/*判定为'*'或'/'号*/ while(op.data[op.top]=='*'||op.data[op.top]=='/') {exp[t]=op.data[op.top];op.top--;t++;} op.top++;op.data[op.top]=ch;break; case'':break; /*过滤掉空格*/ default: while(ch>='0'&&ch<='9')/*判定为数字*/ {exp[t]=ch;t++; ch=str[i];i++; } i--; exp[t]='#';t++;/*用#标识一个数值串结束*/}ch=str[i];i++;}while(op.top!=-1)/*此时str扫描完毕,栈不空时循环*/{exp[t]=op.data[op.top];t++;op.top--;}exp[t]='\0';/*给exp表达式添加结束标识*/}下面对后缀表达式求值。在后缀表达式求值算法中要用到一个数值栈st,该算法实现过程如下:后缀表达式存放在字符型数组exp中,从头开始依次扫描这个后缀表达式,当遇到运算数时,就把它插入到数值栈st中；当遇到运算符时,就执行两次退栈,并根据该运算符对退栈的数值进行相应的运算,再把结果入栈st。重复上述过程,直至后缀表达式exp扫描完毕,此时数值栈st中栈顶的数值即为表达式的值。while(从postexp读取字符ch,ch!='\0'){若ch为数字,将后续的所有数字构成一个整数存放到数值栈st中。若ch为“+”,则从数值栈st中退栈两个运算数,相加后进栈st中。若ch为“－”,则从数值栈st中退栈两个运算数,相减后进栈st中。若ch为“*”,则从数值栈st中退栈两个运算数,相乘后进栈st中。若ch为“/”,则从数值栈st中退栈两个运算数,相除后进栈st中(若除数为零,则提示相应的错误信息)。}若字符串postexp扫描完毕,则数值栈op中的栈顶元素就是表达式的值。对后缀表达式求值对于后缀表达式“56#20#-4#2#+/”的求值过程如下：postexp操作过程st56#20#-4#2#+/遇到56#,将56进栈。5620#-4#2#+/遇到20#,将20进栈。56,20-4#2#+/遇到“-”,出栈两次,将56-20=36进栈。364#2#+/遇到4#,将4进栈。36,42#+/遇到2#,将2进栈。36,4,2+/遇到“+”,出栈两次,将4+2=6进栈。36,6/遇到“/”,出栈两次,将36/6=6进栈。6

postexp扫描完毕,算法结束,栈顶的元素6即为所求。

floatcompvalue(charexp[]) /*计算后缀表达式的值*/{ struct {floatdata[MaxSize]; /*存放数值*/ inttop; /*栈指针*/ }st; /*定义数值栈*/ floatd;charch;intt=0; /*t作为exp的下标*/ st.top=-1;ch=exp[t];t++; while(ch!='\0') /*exp字符串未扫描完时循环*/ {switch(ch) { case'+':st.data[st.top-1]=st.data[st.top-1]+st.data[st.top]; st.top--;break; case'-':st.data[st.top-1]=st.data[st.top-1]-st.data[st.top]; st.top--;break; case'*':st.data[st.top-1]=st.data[st.top-1]*st.data[st.top]; st.top--;break; case'/':if(st.data[st.top]!=0) st.data[st.top-1]=st.data[st.top-1]/st.data[st.top]; else {printf("\n\t除零错误!\n"); exit(0); /*异常退出*/ } st.top--;break; default:d=0;/*将数字字符转换成数值存放到d中*/ while(ch>='0'&&ch<='9')/*为数字字符*/ {d=10*d+ch-'0'; ch=exp[t];t++; } st.top++;st.data[st.top]=d; } ch=exp[t];t++; } returnst.data[st.top];}2.求解迷宫问题求迷宫问题就是求出从入口到出口的路径。在求解时,通常用的是“穷举求解”的方法,即从入口出发,顺某一方向向前试探,若能走通,则继续往前走；否则沿原路退回,换一个方向再继续试探,直至所有可能的通路都试探完为止。为了保证在任何位置上都能沿原路退回(称为回溯),需要用一个后进先出的栈来保存从入口到当前位置的路径。首先用如图3.3所示的方块图表示迷宫。对于图中的每个方块,用空白表示通道,用阴影表示墙。所求路径必须是简单路径,即在求得的路径上不能重复出现同一通道块。为了表示迷宫,设置一个数组mg,其中每个元素表示一个方块的状态,为0时表示对应方块是通道,为1时表示对应方块为墙,如图3.3所示的迷宫,对应的迷宫数组mg如下:intmg[M+1][N+1]={ /*M=10,N=10*/ {1,1,1,1,1,1,1,1,1,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,0,0,1,1,0,0,1}, {1,0,1,1,1,0,0,0,0,1}, {1,0,0,0,1,0,0,0,0,1}, {1,0,1,0,0,0,1,0,0,1}, {1,0,1,1,1,0,1,1,0,1}, {1,1,0,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1}};对于迷宫中的每个方块,有上下左右四个方块相邻,如图3.4所示,第i行第j列的当前方块的位置为(i,j),规定上方方块为方位0,顺时针方向递增编号。在试探过程中,假设从方位0到方位3的方向查找下一个可走的方块。为了便于回溯,对于可走的方块都要进栈,并试探它的下一可走的方位,将这个可走的方位保存到栈中,为此,将栈定义为:

struct