第 3章 栈和队列
3.1 栈
3.2 队列本章小结
3.1.1 栈的定义
3.1.2 栈的顺序存储结构及其基本运算实现
3.1.3 栈的链式存储结构及其基本运算的实现
3.1.4 栈的应用例子
3.1 栈栈是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为 栈顶 。
栈顶的当前位臵是动态的,栈顶的当前位臵由一个称为栈顶指针的位臵指示器指示 。
表的另一端称为栈底 。
当栈中没有数据元素时,称为空栈 。
栈的插入操作通常称为进栈或入栈,栈的删除操作通常称为退栈或出栈 。
3.1.1 栈的定义栈的几种基本运算如下,
(1)初始化栈 InitStack(&s):构造一个空栈 s
。
(2)销毁栈 ClearStack(&s):释放栈 s占用的存储空间 。
(3)求栈的长度 StackLength(s):返回栈 s中的元素个数 。
(4)判断栈是否为空 StackEmpty(s):若栈 s
为空,则返回真；否则返回假 。
(5)进栈 Push(&S,e):将元素 e插入到栈 s中作为栈顶元素 。
(6)出栈 Pop(&s,&e):从栈 s中退出栈顶元素,
并将其值赋给 e。
(7)取栈顶元素 GetTop(s,&e):返回当前的栈顶元素,并将其值赋给 e。
(8)显示栈中元素 DispStack(s):从栈顶到栈底顺序显示栈中所有元素 。
3.1.2 栈的顺序存储结构及其基本运算实现假设栈的元素个数最大不超过正整数
MaxSize,所有的元素都具有同一数据类型
ElemType,则可用下列方式来定义栈类型
SqStack:
typedef struct
{
ElemType elem[MaxSize]；
int top； /*栈指针 */
} SqStack；
例 3.1 设有 4个元素 a,b,c,d进栈,给出它们所有可能的出栈次序 。
答,所有可能的出栈次序如下,
abcd abdc acbd acdb
adcb bacd badc bcad
bcda bdca cbad cbda
cdba dcba
例 3.2 设一个栈的输入序列为 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.3 已知一个栈的进栈序列是 1,2,3,…,n,
其输出序列是 p1,p2,…,pn,若 p1=n,则 pi的值 。
(A) i (B) n-i
(C) n-i+1 (D) 不确定答,当 p1=n时,输出序列必是 n,n-1,…,3,2,1,
则,p2=n-1,p3=n-2,…,pn=1,推断出 pi=n-i+1,所以本题答案为 C。
例 3.4 设 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。
在顺序栈中实现栈的基本运算算法,
(1)初始化栈 initStack(&s)
建立一个新的空栈 s,实际上是将栈顶指针指向 -1即可 。 对应算法如下,
void InitStack(SqStack *&s)
{
s=(SqStack *)malloc(sizeof(SqStack));
s->top=-1;
}
(2)销毁栈 ClearStack(&s)
释放栈 s占用的存储空间 。 对应算法如下,
void ClearStack(SqStack *&s)
{
free(s);
}
(3)求栈的长度 StackLength(s)
返回栈 s中的元素个数,即栈指针加 1的结果 。
对应算法如下,
int StackLength(SqStack *s)
{
return(s->top+1);
}
(4)判断栈是否为空 StackEmpty(s)
栈 S为空的条件是 s->top==-1。 对应算法如下,
int StackEmpty(SqStack *s)
{
return(s->top==-1);
}
(5)进栈 Push(&s,e)
在栈不满的条件下,先将栈指针增 1,然后在该位臵上插入元素 e。 对应算法如下,
int Push(SqStack *&s,ElemType e)
{ if (s->top==MaxSize-1) return 0;
/*栈满的情况,即栈上溢出 */
s->top++;
s->elem[s->top]=e;
return 1;
}
(6)出栈 Pop(&s,&e)
在栈不为空的条件下,先将栈顶元素赋给 e,
然后将栈指针减 1。 对应算法如下,
int Pop(SqStack *&s,ElemType &e)
{ if (s->top==-1) return 0;
/*栈为空的情况,即栈下溢出 */
e=s->elem[s->top];
s->top--;
return 1;
}
(7)取栈顶元素 GetTop(s)
在栈不为空的条件下,将栈顶元素赋给 e。
对应算法如下,
int GetTop(SqStack *s,ElemType &e)
{
if (s->top==-1) return 0;
/*栈为空的情况,即栈下溢出 */
e=s->elem[s->top];
return 1;
}
(8)显示栈中元素 DispStack(s)
从栈顶到栈底顺序显示栈中所有元素 。
对应算法如下,
void DispStack(SqStack *s)
{
int i;
for (i=s->top;i>=0;i--)
printf("%c ",s->elem[i]);
printf("\n");
}
3.1.3 栈的链式存储结构及其基本运算的实现采用链式存储的栈称为链栈,这里采用单链表实现。
链栈的优点是不存在栈满上溢的情况。我们规定栈的所有操作都是在单链表的表头进行的,下图是头结点为 *lhead的链栈,第一个数据结点是栈顶结点,最后一个结点是栈底结点。栈中元素自栈顶到栈底依次是 a1,a2,…,an。
链栈示意图链栈中数据结点的类型 LiStack定义如下,
typedef struct linknode
{
ElemType data; /*数据域 */
struct linknode *next; /*指针域 */
} LiStack;
在链栈中,栈的基本运算算法如下,
(1)初始化栈 initStack(&s)
建立一个空栈 s。 实际上是创建链栈的头结点,并将其 next域臵为 NULL。 对应算法如下,
void InitStack(LiStack *&s)
{
s=(LiStack *)malloc(sizeof(LiStack));
s->next=NULL;
}
(2)销毁栈 ClearStack(&s)
释放栈 s占用的全部存储空间 。 对应算法如下,
void ClearStack(LiStack *&s)
{ LiStack *p=s->next;
while (p!=NULL)
{ free(s);
s=p;
p=p->next;
}
}
(3)求栈的长度 StackLength(s)
从第一个数据结点开始扫描单链表,用 i记录访问的数据结点个数,最后返回 i值 。 对应算法如下,
int StackLength(LiStack *s)
{
int i=0;
LiStack *p;
p=s->next;
while (p!=NULL)
{
i++;p=p->next;
}
return(i);
}
(4)判断栈是否为空 StackEmpty(s)
栈 S为空的条件是 s->next==NULL,即单链表中没有数据结点 。 对应算法如下,
int StackEmpty(LiStack *s)
{
return(s->next==NULL);
}
(5)进栈 Push(&s,e)
将新数据结点插入到头结点之后 。 对应算法如下,
void Push(LiStack *&s,ElemType e)
{
LiStack *p;
p=(LiStack *)malloc(sizeof(LiStack));
p->data=e;
p->next=s->next;
/*插入 *p结点作为第一个数据结点 */
s->next=p;
}
(6)出栈 Pop(&s,&e)
在栈不为空的条件下,将头结点后继数据结点的数据域赋给 e,然后将其删除 。 对应算法如下,
int Pop(LiStack *&s,ElemType &e)
{ LiStack *p;
if (s->next==NULL) return 0;
/*栈空的情况 */
p=s->next; /*p指向第一个数据结点 */
e=p->data;
s->next=p->next;
free(p);
return 1;
}
(7)取栈顶元素 GetTop(s)
在栈不为空的条件下,将头结点后继数据结点的数据域赋给 e。 对应算法如下,
int GetTop(LiStack *s,ElemType &e)
{
if (s->next==NULL) return 0;
/*栈空的情况 */
e=s->next->data;
return 1;
}
(8)显示栈中元素 DispStack(s)
从第一个数据结点开始扫描单链表,并输出当前访问结点的数据域值 。 对应算法如下,
void DispStack(LiStack *s)
{ LiStack *p=s->next;
while (p!=NULL)
{ printf("%c ",p->data);
p=p->next;
}
printf("\n");
}
例 3.5 假设表达式中允许包含三种括号,
圆括号,方括号和大括号 。 编写一个算法判断表达式中的括号是否正确配对 。
3.1.4 栈的应用例子解,对应的算法如下,
int correct(char exp[],int n)
{
char st[MaxSize];
int top=-1,i=0,tag=1;
while (i<n && tag)
{ if (exp[i]=='(' || exp[i]=='[' || exp[i]=='{')
/*遇到 '(','['或 '{',则将其入栈 */
{
top++;
st[top]=exp[i];
}
if (exp[i]==‘)’) /*遇到‘ )’,若栈顶是‘ (’,则继续处理,否则以不配对返回 */
if (st[top]=='(') top--;
else tag=0;
if (exp[i]==‘]’) /*遇到‘ ]’,若栈顶是‘ [’,则继续处理,否则以不配对返回 */
if (st[top]=='[') top--;
else tag=0;
if (exp[i]==‘}’) /*遇到‘ }’,若栈顶是 ‘ {’,则继续处理,否则以不配对返回 */
if (st[top]=='{') top--;
else tag=0;
i++;
}
if (top>-1)
tag=0; /*若栈不空,则不配对 */
return(tag);
}
1,表达式求值这里限定的表达式求值问题是,用户输入一个包含,+”,,-”,,*”,,/”,正整数和圆括号的合法数学表达式,计算该表达式的运算结果 。
在程序语言中,运算符位于两个操作数中间的表达式称为 中缀表达式,例如,1+2*3就是一个中缀表达式,中缀表达式是最常用的一种表达式方式 。 对中缀表达式的运算一般遵循,先乘除,后加减,从左到右计算,先括号内,后括号外,的规则 。 因此,中缀表达式不仅要依赖运算符优先级,而且还要处理括号 。
所谓 后缀表达式,就是运算符在操作数的后面,如 1+2*3的后缀表达式为 123*+。 在后缀表达式中已考虑了运算符的优先级,没有括号,只有操作数和运算符 。
对后缀表达式求值过程是,从左到右读入后缀表达式,若读入的是一个操作数,就将它入数值栈,若读入的是一个运算符 op,就从数值栈中连续出栈两个元素 (两个操作数 ),假设为 x和 y,
计算 x op y之值,并将计算结果入数值栈；对整个后缀表达式读入结束时,栈顶元素就是计算结果 。
算术表达式求值过程是,先将算术表达式转换成后缀表达式,然后对该后缀表达式求值 。
假设算术表达式中的符号以字符形式由键盘输入,并存放在字符型数组 str中,其后缀表达式存放在字符型数组 exp中,在将算术表达式转换成后缀表达式的过程中用一个字符型数组 op
作为栈。将算术表达式转换成后缀表示的方法如下,
依次从键盘输入表达式中的字符 ch,对于每一个 ch:
(1)若 ch为数字,将后续的所有数字均依次存入数组 exp中,并以字符,#”标志数值串结束 。
(2)若 ch为左括弧,(”,则将此括弧入栈 op。
(3)若 ch为右括弧,)”,则将栈 op中左括弧,(”以前的字符依次删除并存入数组 exp中,然后将左括弧,(”删除 。
(4)若 ch为,+”或,-”,则将当前栈 op中,(”以前的所有字符 (运算符 )依次删除并存入数组 exp中,然后将 ch入栈 op中 。
(5)若 ch为,*” 或,/”,则将当前栈 op中的栈顶端连续的,*” 或
,/”删除并依次存入数组 exp中,然后将 ch入栈 op中 。
(6)若字符串 str扫描完毕,则将栈 op中的所有运算符依次删除并存入数组 exp中,然后再将 ch存入数组 exp中,最后可得到表达式的后缀表示在数组 exp中。
根据上述原理得到的 trans()算法如下,
void trans(char str[],char exp[])
/*将算术表达式 str转换成后缀表达式 exp*/
{ struct
{ char data[MaxSize]; /*存放运算符 */
int top; /*栈指针 */
} op; /*定义运算符栈 */
char ch;
int i=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中栈顶的数值即为表达式的值。
float compvalue(char exp[]) /*计算后缀表达式的值 */
{ struct
{ float data[MaxSize]; /*存放数值 */
int top; /*栈指针 */
} st; /*定义数值栈 */
float d; char ch; int t=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++;
}
return st.data[st.top];
}
2,求解迷宫问题求迷宫问题就是求出从入口到出口的路径 。 在求解时,通常用的是,穷举求解,的方法,即从入口出发,顺某一方向向前试探,若能走通,则继续往前走；否则沿原路退回,换一个方向再继续试探,直至所有可能的通路都试探完为止 。 为了保证在任何位臵上都能沿原路退回
(称为回溯 ),需要用一个后进先出的栈来保存从入口到当前位臵的路径 。
首先用如图 3.3所示的方块图表示迷宫。对于图中的每个方块,用空白表示通道,用阴影表示墙。所求路径必须是简单路径,即在求得的路径上不能重复出现同一通道块。
为了表示迷宫,设臵一个数组 mg,其中每个元素表示一个方块的状态,为 0时表示对应方块是通道,为 1时表示对应方块为墙,如图 3.3所示的迷宫,对应的迷宫数组 mg如下,
int mg[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
{ int i; /*当前方块的行号 */
int j; /*当前方块的列号 */
int di; /*di是下一可走方位的方位号 */
} Stack[MaxSize]; /*定义栈 */
int top=-1; /*初始化栈指针 */
求解迷宫 (1,1)到 (M-2,N-2)路径的过程是,先将入口进栈 (初始方位设臵为 -1),在栈不空时循环,取栈顶方块 (不退栈 ),若该方块是出口,则输出栈中方块即为路径 。 否则,找下一个可走的相邻方块,若不存在这样的方块,则退栈 。 若存在这样的方块,则将其方位保存到栈顶元素中,并将这个可走的相邻方块进栈 (初始方位设臵为 -1)。
为了保证试探的可走相邻方块不是已走路径上的方块,如 (i,j)已进栈,在试探 (i+1,j)的下一可走方块时,又试探到 (i,j),这样可能会引起死循环,为此,在一个方块进栈后,将对应的 mg数组元素值改为 -1(变为不可走的相邻方块 ),当退栈时 (表示没有可走相邻方块 ),将其恢复为 0。
void mgpath() /*路径为,(1,1)->(M-2,N-2)*/
{ int i,j,di,find,k;
top++; /*初始方块进栈 */
Stack[top].i=1;Stack[top].j=1;Stack[top].di=-1;mg[1][1]=-1;
while (top>-1) /*栈不空时循环 */
{ i=Stack[top].i;j=Stack[top].j;di=Stack[top].di;
if (i==M-2 && j==N-2) /*找到了出口,输出路径 */
{ printf("迷宫路径如下,\n");
for (k=0;k<=top;k++)
{ printf("\t(%d,%d)",Stack[k].i,Stack[k].j);
if ((k+1)%5==0) printf("\n");
}
printf("\n");
return;
}
find=0;
while (di<4 && find==0) /*找下一个可走方块 */
{ di++;
switch(di)
{
case 0:i=Stack[top].i-1;j=Stack[top].j;break;
case 1:i=Stack[top].i;j=Stack[top].j+1;break;
case 2:i=Stack[top].i+1;j=Stack[top].j;break;
case 3:i=Stack[top].i,j=Stack[top].j-1;break;
}
if (mg[i][j]==0) find=1;
}
if (find==1) /*找到了下一个可走方块 */
{ Stack[top].di=di; /*修改原栈顶元素的 di值 */
top++; /*下一个可走方块进栈 */
Stack[top].i=i;Stack[top].j=j;Stack[top].di=-1;
mg[i][j]=-1; /*避免重复走到该方块 */
}
else /*没有路径可走,则退栈 */
{ mg[Stack[top].i][Stack[top].j]=0;
/*让该位臵变为其他路径可走方块 */
top--;
}
}
printf("没有可走路径 !\n");
}
3.2 队列
3.2.1 队列的定义返回
3.2.2 队列的顺序存储结构及其基本运算的实现
3.2.3 队列的链式存储结构及其基本运算的实现
3.2.4 队列的应用例子队列简称队,它也是一种运算受限的线性表,
其限制仅允许在表的一端进行插入,而在表的另一端进行删除。
我们把进行插入的一端称做队尾 (rear),进行删除的一端称做队首 (front)。
向队列中插入新元素称为进队或入队,新元素进队后就成为新的队尾元素；从队列中删除元素称为出队或离队,元素出队后,其后继元素就成为队首元素。
3.2.1 队列的定义
3.2.2 队列的顺序存储结构及其基本运算的实现假设队列的元素个数最大不超过整数
MaxSize,所有的元素都具有同一数据类型
ElemType,则顺序队列类型 SqQueue定义如下,
typedef struct
{ ElemType elem[MaxSize]；
int front,rear； /*队首和队尾指针 */
} SqQueue
从前图中看到,图 (a)为队列的初始状态,有
front==rear成立,该条件可以作为队列空的条件 。
那么能不能用 rear==MaxSize-1作为队满的条件呢？ 显然不能,在图 (d)中,队列为空,但仍满足该条件 。 这时入队时出现,上溢出,,这种溢出并不是真正的溢出,在 elem数组中存在可以存放元素的空位臵,所以这是一种假溢出 。
为了能够充分地使用数组中的存储空间,把数组的前端和后端连接起来,形成一个环形的顺序表,即把存储队列元素的表从逻辑上看成一个环,称为循环队列 。
循环队列首尾相连,当队首 front指针满足
front=MaxSize-1后,再前进一个位臵就自动到
0,这可以利用除法取余的运算 (％ )来实现,
队首指针进 1:front=(front+1)％ MaxSize
队尾指针进 1:rear=(rear+1)％ MaxSize
循环队列的除头指针和队尾指针初始化时都臵 0:front=rear=0。 在入队元素和出队元素时,指针都按逆时针方向进 1。
怎样区分这两者之间的差别呢?在入队时少用一个数据元素空间,以队尾指针加 1等于队首指针判断队满,即队满条件为,
(q->rear+1) % MaxSize==q->front
队空条件仍为,
q->rear==q->front
在循环队列中,实现队列的基本运算算法如下,
(1)初始化队列 InitQueue(&q)
构造一个空队列 q。 将 front和 rear指针均设臵成初始状态即 0值 。 对应算法如下,
void InitQueue(SqQueue *&q)
{
q=(SqQueue *)malloc (sizeof(SqQueue));
q->front=q->rear=0;
}
(2)销毁队列 ClearQueue(&q)
释放队列 q占用的存储空间 。 对应算法如下,
void ClearQueue(SqQueue *&q)
{
free(q);
}
(3)判断队列是否为空 QueueEmpty(q)
若队列 q满足 q->front==q->rear条件,则返回 1；否则返回 0。 对应算法如下,
int QueueEmpty(SqQueue *q)
{
return(q->front==q->rear);
}
(4)入队列 enQueue(q,e)
在队列不满的条件下,先将队尾指针 rear循环增 1,然后将元素添加到该位臵 。 对应算法如下,
int enQueue(SqQueue *&q,ElemType e)
{
if ((q->rear+1)%MaxSize==q->front) /*队满 */
return 0;
q->rear=(q->rear+1)%MaxSize;
q->elem[q->rear]=e;
return 1;
}
(5)出队列 deQueue(q,e)
在队列 q不为空的条件下,将队首指针 front循环增 1,并将该位臵的元素值赋给 e。 对应算法如下,
int deQueue(SqQueue *&q,ElemType &e)
{
if (q->front==q->rear) /*队空 */
return 0;
q->front=(q->front+1)%MaxSize;
e=q->elem[q->front];
return 1;
}
链队中数据结点类型 QNode定义如下,
struct qnode
{
ElemType data;
struct qnode *next;
} QNode;
3.2.3 队列的链式存储结构及其基本运算的实现链队中头结点类型 LiQueue定义如下,
typedef struct
{
QNode *front;
QNode *rear;
} LiQueue;
在链队存储中,队列的基本运算算法如下,
(1)初始化队列 InitQueue(q)
构造一个空队列,即创建一个头结点,其
front和 rear域均臵为 NULL。 对应算法如下,
void InitQueue(LiQueue *&q)
{
q=(LiQueue *)malloc(sizeof(LiQueue));
q->front=q->rear=NULL;
}
(2)销毁队列 ClearQueue(q)
释放队列占用的存储空间,包括链队结点和所有数据结点的存储空间 。 对应算法如下,
void ClearQueue(LiQueue *&q)
{ QNode *p=q->front,*r;
if (p!=NULL) /*释放数据结点占用空间 */
{ r=p->next;
while (r!=NULL)
{ free(p);
p=r;r=p->next;
}
}
free(q); /*释放链队结点占用空间 */
}
(3)判断队列是否为空 QueueEmpty(q)
若链队结点的 rear域值为 NULL,表示队列为空,
返回 1；否则返回 0。 对应算法如下,
int QueueEmpty(LiQueue *q)
{
if (q->rear==NULL)
return 1;
else
return 0;
}
(4)入队列 enQueue(q,e)
创建 data域为 e的数据结点 *s。 若原队列为空,
则将链队结点的两个域均指向 *s结点,否则,将 *s
链到单链表的末尾,并让链队结点的 rear域指向它 。 对应算法如下,
void enQueue(LiQueue *&q,ElemType e)
{ QNode *s;
s=(QNode *)malloc(sizeof(QNode));
s->data=e;
s->next=NULL;
if (q->rear==NULL)
/*若链队为空,新结点是队首结点又是队尾结点 */
q->front=q->rear=s;
else
{ q->rear->next=s;
/*将 *s结点链到队尾,rear指向它 */
q->rear=s;
}
}
(5)出队列 deQueue(q,e)
若原队列不为空,则将第一个数据结点的
data域值赋给 e,并删除之 。 若出队之前队列中只有一个结点,则需将链队结点的两个域均臵为 NULL,表示队列已为空 。 对应的算法如下,
int deQueue(LiQueue *&q,ElemType &e)
{ QNode *t;
if (q->rear==NULL) /*队列为空 */
return 0;
t=q->front; /*t指向第一个数据结点 */
if (q->front==q->rear)
/*队列中只有一个结点时 */
q->front=q->rear=NULL;
else /*队列中有多个结点时 */
q->front=q->front->next;
e=t->data;
free(t);
return 1;
}
3.2.4 队列的应用例子例 3.6 什么是队列的上溢现象和假溢出现象？
解决它们有哪些方法？
答,在队列的顺序存储结构中,设头指针为
front,队尾指针 rear,队的容量 (存储空间的大小 )
为 MaxSize 。 当 有 元 素 加 入 到 队 列 时,若
rear=MaxSize(初始时 rear=0)则发生队列的上溢现象,该元素不能加入队列 。
特别要注意的是队列的假溢出现象,队列中还有剩余空间但元素却不能进入队列,造成这种现象的原因是由于队列的操作方法所致 。
解决队列上溢的方法有以下几种,
(1)建立一个足够大的存储空间,但这样做会造成空间的使用效率降低 。
(2)当出现假溢出时可采用以下几种方法,
① 采用平移元素的方法,每当队列中加入一个元素时,队列中已有的元素向队头移动一个位臵
(当然要有空闲的空间可供移动 )；
② 每当删除一个队头元素时,则依次移动队中的元素,始终使 front指针指向队列中的第一个位臵；
③ 采用循环队列方式,把队列看成一个首尾相接的循环队列,在循环队列上进行插入或删除运算时仍然遵循,先进先出,的原则 。
例 3.7 对于顺序队列来说,如果知道队首元素的位臵和队列中元素个数,则队尾元素所在位臵显然是可以计算的 。 也就是说,可以用队列中元素个数代替队尾指针 。 编写出这种循环顺序队列的初始化,入队,出队和判空算法 。
解,当已知队首元素的位臵 front和队列中元素个数 count后,
队空的条件为,count==0；
队满的条件为,count==MaxSize；
计算队尾位臵 rear:
rear=(front+count+MaxSize)%MaxSize。
对应的算法如下,
typedef struct
{ ElemType elem[MaxSize];
int front; /*队首指针 */
int count; /*队列中元素个数 */
} QuType; /*队列类型 */
void InitQu(QuType *&q) /*队列 q初始化 */
{
q=(QuType *)malloc(sizeof(QuType));
q->front=0;
q->count=0;
}
int EnQu(QuType *&q,ElemType x) /*进队 */
{ int rear;
if (q->count==MaxSize) /*队满上溢出 */
return 0;
else
{ rear=(q->front+q->count+MaxSize)%MaxSize;
/*求队尾位臵 */
rear=(rear+1)%MaxSize; /*队尾位臵进 1*/
q->elem[rear]=x;
q->count++;
return 1;
}
}
int DeQu(QuType *&q,ElemType &x) /*出队 */
{
if (q->count==0) /*队空下溢出 */
return 0;
else
{ q->front=(q->front+1)%MaxSize;
x=q->elem[q->front];
q->count--;
return 1;
}
}
int QuEmpty(QuType *q) /*判空 */
{
return(q->count==0);
}
采用队列求解迷宫问题。
使用一个队列 Qu记录走过的方块,该队列的结构如下,
struct
{ int i,j; /*方块的位臵 */
int pre; /*本路径中上一方块在 Qu中的下标 */
} Qu[MaxSize];
int front=-1,rear=-1; /*队首指针和队尾指针 */
这里使用的队列 Qu不是循环队列,因此在出队时,不会将出队元素真正从队列中删除,因为要利用它输出路径 。
搜索从 (1,1)到 (M-2,N-2)路径的过程是,
首先将 (1,1)入队 ;
在队列 Qu不为空时循环,出队一次 (由于不是循环队列,该出队元素仍在队列中 ),称该出队的方块为当前方块,front为该方块在 Qu中的下标。如果当前方块是出口,
则输出路径并结束。否则,按顺时针方向找出当前方块的四个方位中可走的相邻方块 (对应的 mg数组值为 0),将这些可走的相邻方块均插入到队列 Qu中,其 pre设臵为本搜索路径中上一方块在 Qu中的下标值,也就是当前方块的 front值,并将相邻方块对应的 mg数组值臵为 -1,以避免回过来重复搜索。如此队列为空,表示未找到出口,即不存在路径。
实际上,本算法的思想是从 (1,1)开始,利用队列的特点,一层一层向外扩展可走的点,直到找到出口为止,这个方法就是将在第 8章介绍的图的广度优先搜索方法 。
void mgpath() /*搜索路径为,(1,1)->(M-2,N-2)*/
{ int i,j,find=0,di;
rear++;
Qu[rear].i=1;Qu[rear].j=1;Qu[rear].pre=-1; /*(1,1)入队 */
mg[1][1]=-1; /*将其赋值 -1,以避免回过来重复搜索 */
while (front<=rear && !find)
{ front++; /*出队,由于不是循环队列,该元素仍在队中 */
i=Qu[front].i;j=Qu[front].j;
if (i==M-2 && j==N-2) /*找到了出口,输出路径 */
{ find=1;
print(front); /*调用 print函数输出路径 */
}
for (di=0;di<3;di++) /*把每个可走的方块插入队列中 */
{ switch(di)
{ case 0:i=Qu[front].i-1;j=Qu[front].j;break;
case 1:i=Qu[front].i;j=Qu[front].j+1;break;
case 2:i=Qu[front].i+1;j=Qu[front].j;break;
case 3:i=Qu[front].i,j=Qu[front].j-1;break;
}
if (mg[i][j]==0)
{ rear++; /*将该相邻方块插入到队列中 */
Qu[rear].i=i;Qu[rear].j=j;
Qu[rear].pre=front; /*指向路径中上一方块下标 */
mg[i][j]=-1; /*将其赋值 -1,以避免重复搜索 */
}
}
}
if (!find) printf("不存在路径 !\n");
}
本章小结本章基本学习要点如下,
(1)理解栈和队列的特性以及它们之间的差异,知道在何时使用哪种数据结构 。
(2)重点掌握在顺序栈上和链栈上实现栈的基本运算算法,注意栈满和栈空的条件 。
(3)重点掌握在顺序队上和链队上实现队列的基本运算算法,注意循环队上队满和队空的条件 。
(4)灵活运用栈和队列这两种数据结构解决一些综合应用问题 。
练习题教材中 p77的习题 2,4和 6。
上机实验题教材中 p79题 5和 7。
3.1 栈
3.2 队列本章小结
3.1.1 栈的定义
3.1.2 栈的顺序存储结构及其基本运算实现
3.1.3 栈的链式存储结构及其基本运算的实现
3.1.4 栈的应用例子
3.1 栈栈是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为 栈顶 。
栈顶的当前位臵是动态的,栈顶的当前位臵由一个称为栈顶指针的位臵指示器指示 。
表的另一端称为栈底 。
当栈中没有数据元素时,称为空栈 。
栈的插入操作通常称为进栈或入栈,栈的删除操作通常称为退栈或出栈 。
3.1.1 栈的定义栈的几种基本运算如下,
(1)初始化栈 InitStack(&s):构造一个空栈 s
。
(2)销毁栈 ClearStack(&s):释放栈 s占用的存储空间 。
(3)求栈的长度 StackLength(s):返回栈 s中的元素个数 。
(4)判断栈是否为空 StackEmpty(s):若栈 s
为空,则返回真；否则返回假 。
(5)进栈 Push(&S,e):将元素 e插入到栈 s中作为栈顶元素 。
(6)出栈 Pop(&s,&e):从栈 s中退出栈顶元素,
并将其值赋给 e。
(7)取栈顶元素 GetTop(s,&e):返回当前的栈顶元素,并将其值赋给 e。
(8)显示栈中元素 DispStack(s):从栈顶到栈底顺序显示栈中所有元素 。
3.1.2 栈的顺序存储结构及其基本运算实现假设栈的元素个数最大不超过正整数
MaxSize,所有的元素都具有同一数据类型
ElemType,则可用下列方式来定义栈类型
SqStack:
typedef struct
{
ElemType elem[MaxSize]；
int top； /*栈指针 */
} SqStack；
例 3.1 设有 4个元素 a,b,c,d进栈,给出它们所有可能的出栈次序 。
答,所有可能的出栈次序如下,
abcd abdc acbd acdb
adcb bacd badc bcad
bcda bdca cbad cbda
cdba dcba
例 3.2 设一个栈的输入序列为 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.3 已知一个栈的进栈序列是 1,2,3,…,n,
其输出序列是 p1,p2,…,pn,若 p1=n,则 pi的值 。
(A) i (B) n-i
(C) n-i+1 (D) 不确定答,当 p1=n时,输出序列必是 n,n-1,…,3,2,1,
则,p2=n-1,p3=n-2,…,pn=1,推断出 pi=n-i+1,所以本题答案为 C。
例 3.4 设 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。
在顺序栈中实现栈的基本运算算法,
(1)初始化栈 initStack(&s)
建立一个新的空栈 s,实际上是将栈顶指针指向 -1即可 。 对应算法如下,
void InitStack(SqStack *&s)
{
s=(SqStack *)malloc(sizeof(SqStack));
s->top=-1;
}
(2)销毁栈 ClearStack(&s)
释放栈 s占用的存储空间 。 对应算法如下,
void ClearStack(SqStack *&s)
{
free(s);
}
(3)求栈的长度 StackLength(s)
返回栈 s中的元素个数,即栈指针加 1的结果 。
对应算法如下,
int StackLength(SqStack *s)
{
return(s->top+1);
}
(4)判断栈是否为空 StackEmpty(s)
栈 S为空的条件是 s->top==-1。 对应算法如下,
int StackEmpty(SqStack *s)
{
return(s->top==-1);
}
(5)进栈 Push(&s,e)
在栈不满的条件下,先将栈指针增 1,然后在该位臵上插入元素 e。 对应算法如下,
int Push(SqStack *&s,ElemType e)
{ if (s->top==MaxSize-1) return 0;
/*栈满的情况,即栈上溢出 */
s->top++;
s->elem[s->top]=e;
return 1;
}
(6)出栈 Pop(&s,&e)
在栈不为空的条件下,先将栈顶元素赋给 e,
然后将栈指针减 1。 对应算法如下,
int Pop(SqStack *&s,ElemType &e)
{ if (s->top==-1) return 0;
/*栈为空的情况,即栈下溢出 */
e=s->elem[s->top];
s->top--;
return 1;
}
(7)取栈顶元素 GetTop(s)
在栈不为空的条件下,将栈顶元素赋给 e。
对应算法如下,
int GetTop(SqStack *s,ElemType &e)
{
if (s->top==-1) return 0;
/*栈为空的情况,即栈下溢出 */
e=s->elem[s->top];
return 1;
}
(8)显示栈中元素 DispStack(s)
从栈顶到栈底顺序显示栈中所有元素 。
对应算法如下,
void DispStack(SqStack *s)
{
int i;
for (i=s->top;i>=0;i--)
printf("%c ",s->elem[i]);
printf("\n");
}
3.1.3 栈的链式存储结构及其基本运算的实现采用链式存储的栈称为链栈,这里采用单链表实现。
链栈的优点是不存在栈满上溢的情况。我们规定栈的所有操作都是在单链表的表头进行的,下图是头结点为 *lhead的链栈,第一个数据结点是栈顶结点,最后一个结点是栈底结点。栈中元素自栈顶到栈底依次是 a1,a2,…,an。
链栈示意图链栈中数据结点的类型 LiStack定义如下,
typedef struct linknode
{
ElemType data; /*数据域 */
struct linknode *next; /*指针域 */
} LiStack;
在链栈中,栈的基本运算算法如下,
(1)初始化栈 initStack(&s)
建立一个空栈 s。 实际上是创建链栈的头结点,并将其 next域臵为 NULL。 对应算法如下,
void InitStack(LiStack *&s)
{
s=(LiStack *)malloc(sizeof(LiStack));
s->next=NULL;
}
(2)销毁栈 ClearStack(&s)
释放栈 s占用的全部存储空间 。 对应算法如下,
void ClearStack(LiStack *&s)
{ LiStack *p=s->next;
while (p!=NULL)
{ free(s);
s=p;
p=p->next;
}
}
(3)求栈的长度 StackLength(s)
从第一个数据结点开始扫描单链表,用 i记录访问的数据结点个数,最后返回 i值 。 对应算法如下,
int StackLength(LiStack *s)
{
int i=0;
LiStack *p;
p=s->next;
while (p!=NULL)
{
i++;p=p->next;
}
return(i);
}
(4)判断栈是否为空 StackEmpty(s)
栈 S为空的条件是 s->next==NULL,即单链表中没有数据结点 。 对应算法如下,
int StackEmpty(LiStack *s)
{
return(s->next==NULL);
}
(5)进栈 Push(&s,e)
将新数据结点插入到头结点之后 。 对应算法如下,
void Push(LiStack *&s,ElemType e)
{
LiStack *p;
p=(LiStack *)malloc(sizeof(LiStack));
p->data=e;
p->next=s->next;
/*插入 *p结点作为第一个数据结点 */
s->next=p;
}
(6)出栈 Pop(&s,&e)
在栈不为空的条件下,将头结点后继数据结点的数据域赋给 e,然后将其删除 。 对应算法如下,
int Pop(LiStack *&s,ElemType &e)
{ LiStack *p;
if (s->next==NULL) return 0;
/*栈空的情况 */
p=s->next; /*p指向第一个数据结点 */
e=p->data;
s->next=p->next;
free(p);
return 1;
}
(7)取栈顶元素 GetTop(s)
在栈不为空的条件下,将头结点后继数据结点的数据域赋给 e。 对应算法如下,
int GetTop(LiStack *s,ElemType &e)
{
if (s->next==NULL) return 0;
/*栈空的情况 */
e=s->next->data;
return 1;
}
(8)显示栈中元素 DispStack(s)
从第一个数据结点开始扫描单链表,并输出当前访问结点的数据域值 。 对应算法如下,
void DispStack(LiStack *s)
{ LiStack *p=s->next;
while (p!=NULL)
{ printf("%c ",p->data);
p=p->next;
}
printf("\n");
}
例 3.5 假设表达式中允许包含三种括号,
圆括号,方括号和大括号 。 编写一个算法判断表达式中的括号是否正确配对 。
3.1.4 栈的应用例子解,对应的算法如下,
int correct(char exp[],int n)
{
char st[MaxSize];
int top=-1,i=0,tag=1;
while (i<n && tag)
{ if (exp[i]=='(' || exp[i]=='[' || exp[i]=='{')
/*遇到 '(','['或 '{',则将其入栈 */
{
top++;
st[top]=exp[i];
}
if (exp[i]==‘)’) /*遇到‘ )’,若栈顶是‘ (’,则继续处理,否则以不配对返回 */
if (st[top]=='(') top--;
else tag=0;
if (exp[i]==‘]’) /*遇到‘ ]’,若栈顶是‘ [’,则继续处理,否则以不配对返回 */
if (st[top]=='[') top--;
else tag=0;
if (exp[i]==‘}’) /*遇到‘ }’,若栈顶是 ‘ {’,则继续处理,否则以不配对返回 */
if (st[top]=='{') top--;
else tag=0;
i++;
}
if (top>-1)
tag=0; /*若栈不空,则不配对 */
return(tag);
}
1,表达式求值这里限定的表达式求值问题是,用户输入一个包含,+”,,-”,,*”,,/”,正整数和圆括号的合法数学表达式,计算该表达式的运算结果 。
在程序语言中,运算符位于两个操作数中间的表达式称为 中缀表达式,例如,1+2*3就是一个中缀表达式,中缀表达式是最常用的一种表达式方式 。 对中缀表达式的运算一般遵循,先乘除,后加减,从左到右计算,先括号内,后括号外,的规则 。 因此,中缀表达式不仅要依赖运算符优先级,而且还要处理括号 。
所谓 后缀表达式,就是运算符在操作数的后面,如 1+2*3的后缀表达式为 123*+。 在后缀表达式中已考虑了运算符的优先级,没有括号,只有操作数和运算符 。
对后缀表达式求值过程是,从左到右读入后缀表达式,若读入的是一个操作数,就将它入数值栈,若读入的是一个运算符 op,就从数值栈中连续出栈两个元素 (两个操作数 ),假设为 x和 y,
计算 x op y之值,并将计算结果入数值栈；对整个后缀表达式读入结束时,栈顶元素就是计算结果 。
算术表达式求值过程是,先将算术表达式转换成后缀表达式,然后对该后缀表达式求值 。
假设算术表达式中的符号以字符形式由键盘输入,并存放在字符型数组 str中,其后缀表达式存放在字符型数组 exp中,在将算术表达式转换成后缀表达式的过程中用一个字符型数组 op
作为栈。将算术表达式转换成后缀表示的方法如下,
依次从键盘输入表达式中的字符 ch,对于每一个 ch:
(1)若 ch为数字,将后续的所有数字均依次存入数组 exp中,并以字符,#”标志数值串结束 。
(2)若 ch为左括弧,(”,则将此括弧入栈 op。
(3)若 ch为右括弧,)”,则将栈 op中左括弧,(”以前的字符依次删除并存入数组 exp中,然后将左括弧,(”删除 。
(4)若 ch为,+”或,-”,则将当前栈 op中,(”以前的所有字符 (运算符 )依次删除并存入数组 exp中,然后将 ch入栈 op中 。
(5)若 ch为,*” 或,/”,则将当前栈 op中的栈顶端连续的,*” 或
,/”删除并依次存入数组 exp中,然后将 ch入栈 op中 。
(6)若字符串 str扫描完毕,则将栈 op中的所有运算符依次删除并存入数组 exp中,然后再将 ch存入数组 exp中,最后可得到表达式的后缀表示在数组 exp中。
根据上述原理得到的 trans()算法如下,
void trans(char str[],char exp[])
/*将算术表达式 str转换成后缀表达式 exp*/
{ struct
{ char data[MaxSize]; /*存放运算符 */
int top; /*栈指针 */
} op; /*定义运算符栈 */
char ch;
int i=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中栈顶的数值即为表达式的值。
float compvalue(char exp[]) /*计算后缀表达式的值 */
{ struct
{ float data[MaxSize]; /*存放数值 */
int top; /*栈指针 */
} st; /*定义数值栈 */
float d; char ch; int t=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++;
}
return st.data[st.top];
}
2,求解迷宫问题求迷宫问题就是求出从入口到出口的路径 。 在求解时,通常用的是,穷举求解,的方法,即从入口出发,顺某一方向向前试探,若能走通,则继续往前走；否则沿原路退回,换一个方向再继续试探,直至所有可能的通路都试探完为止 。 为了保证在任何位臵上都能沿原路退回
(称为回溯 ),需要用一个后进先出的栈来保存从入口到当前位臵的路径 。
首先用如图 3.3所示的方块图表示迷宫。对于图中的每个方块,用空白表示通道,用阴影表示墙。所求路径必须是简单路径,即在求得的路径上不能重复出现同一通道块。
为了表示迷宫,设臵一个数组 mg,其中每个元素表示一个方块的状态,为 0时表示对应方块是通道,为 1时表示对应方块为墙,如图 3.3所示的迷宫,对应的迷宫数组 mg如下,
int mg[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
{ int i; /*当前方块的行号 */
int j; /*当前方块的列号 */
int di; /*di是下一可走方位的方位号 */
} Stack[MaxSize]; /*定义栈 */
int top=-1; /*初始化栈指针 */
求解迷宫 (1,1)到 (M-2,N-2)路径的过程是,先将入口进栈 (初始方位设臵为 -1),在栈不空时循环,取栈顶方块 (不退栈 ),若该方块是出口,则输出栈中方块即为路径 。 否则,找下一个可走的相邻方块,若不存在这样的方块,则退栈 。 若存在这样的方块,则将其方位保存到栈顶元素中,并将这个可走的相邻方块进栈 (初始方位设臵为 -1)。
为了保证试探的可走相邻方块不是已走路径上的方块,如 (i,j)已进栈,在试探 (i+1,j)的下一可走方块时,又试探到 (i,j),这样可能会引起死循环,为此,在一个方块进栈后,将对应的 mg数组元素值改为 -1(变为不可走的相邻方块 ),当退栈时 (表示没有可走相邻方块 ),将其恢复为 0。
void mgpath() /*路径为,(1,1)->(M-2,N-2)*/
{ int i,j,di,find,k;
top++; /*初始方块进栈 */
Stack[top].i=1;Stack[top].j=1;Stack[top].di=-1;mg[1][1]=-1;
while (top>-1) /*栈不空时循环 */
{ i=Stack[top].i;j=Stack[top].j;di=Stack[top].di;
if (i==M-2 && j==N-2) /*找到了出口,输出路径 */
{ printf("迷宫路径如下,\n");
for (k=0;k<=top;k++)
{ printf("\t(%d,%d)",Stack[k].i,Stack[k].j);
if ((k+1)%5==0) printf("\n");
}
printf("\n");
return;
}
find=0;
while (di<4 && find==0) /*找下一个可走方块 */
{ di++;
switch(di)
{
case 0:i=Stack[top].i-1;j=Stack[top].j;break;
case 1:i=Stack[top].i;j=Stack[top].j+1;break;
case 2:i=Stack[top].i+1;j=Stack[top].j;break;
case 3:i=Stack[top].i,j=Stack[top].j-1;break;
}
if (mg[i][j]==0) find=1;
}
if (find==1) /*找到了下一个可走方块 */
{ Stack[top].di=di; /*修改原栈顶元素的 di值 */
top++; /*下一个可走方块进栈 */
Stack[top].i=i;Stack[top].j=j;Stack[top].di=-1;
mg[i][j]=-1; /*避免重复走到该方块 */
}
else /*没有路径可走,则退栈 */
{ mg[Stack[top].i][Stack[top].j]=0;
/*让该位臵变为其他路径可走方块 */
top--;
}
}
printf("没有可走路径 !\n");
}
3.2 队列
3.2.1 队列的定义返回
3.2.2 队列的顺序存储结构及其基本运算的实现
3.2.3 队列的链式存储结构及其基本运算的实现
3.2.4 队列的应用例子队列简称队,它也是一种运算受限的线性表,
其限制仅允许在表的一端进行插入,而在表的另一端进行删除。
我们把进行插入的一端称做队尾 (rear),进行删除的一端称做队首 (front)。
向队列中插入新元素称为进队或入队,新元素进队后就成为新的队尾元素；从队列中删除元素称为出队或离队,元素出队后,其后继元素就成为队首元素。
3.2.1 队列的定义
3.2.2 队列的顺序存储结构及其基本运算的实现假设队列的元素个数最大不超过整数
MaxSize,所有的元素都具有同一数据类型
ElemType,则顺序队列类型 SqQueue定义如下,
typedef struct
{ ElemType elem[MaxSize]；
int front,rear； /*队首和队尾指针 */
} SqQueue
从前图中看到,图 (a)为队列的初始状态,有
front==rear成立,该条件可以作为队列空的条件 。
那么能不能用 rear==MaxSize-1作为队满的条件呢？ 显然不能,在图 (d)中,队列为空,但仍满足该条件 。 这时入队时出现,上溢出,,这种溢出并不是真正的溢出,在 elem数组中存在可以存放元素的空位臵,所以这是一种假溢出 。
为了能够充分地使用数组中的存储空间,把数组的前端和后端连接起来,形成一个环形的顺序表,即把存储队列元素的表从逻辑上看成一个环,称为循环队列 。
循环队列首尾相连,当队首 front指针满足
front=MaxSize-1后,再前进一个位臵就自动到
0,这可以利用除法取余的运算 (％ )来实现,
队首指针进 1:front=(front+1)％ MaxSize
队尾指针进 1:rear=(rear+1)％ MaxSize
循环队列的除头指针和队尾指针初始化时都臵 0:front=rear=0。 在入队元素和出队元素时,指针都按逆时针方向进 1。
怎样区分这两者之间的差别呢?在入队时少用一个数据元素空间,以队尾指针加 1等于队首指针判断队满,即队满条件为,
(q->rear+1) % MaxSize==q->front
队空条件仍为,
q->rear==q->front
在循环队列中,实现队列的基本运算算法如下,
(1)初始化队列 InitQueue(&q)
构造一个空队列 q。 将 front和 rear指针均设臵成初始状态即 0值 。 对应算法如下,
void InitQueue(SqQueue *&q)
{
q=(SqQueue *)malloc (sizeof(SqQueue));
q->front=q->rear=0;
}
(2)销毁队列 ClearQueue(&q)
释放队列 q占用的存储空间 。 对应算法如下,
void ClearQueue(SqQueue *&q)
{
free(q);
}
(3)判断队列是否为空 QueueEmpty(q)
若队列 q满足 q->front==q->rear条件,则返回 1；否则返回 0。 对应算法如下,
int QueueEmpty(SqQueue *q)
{
return(q->front==q->rear);
}
(4)入队列 enQueue(q,e)
在队列不满的条件下,先将队尾指针 rear循环增 1,然后将元素添加到该位臵 。 对应算法如下,
int enQueue(SqQueue *&q,ElemType e)
{
if ((q->rear+1)%MaxSize==q->front) /*队满 */
return 0;
q->rear=(q->rear+1)%MaxSize;
q->elem[q->rear]=e;
return 1;
}
(5)出队列 deQueue(q,e)
在队列 q不为空的条件下,将队首指针 front循环增 1,并将该位臵的元素值赋给 e。 对应算法如下,
int deQueue(SqQueue *&q,ElemType &e)
{
if (q->front==q->rear) /*队空 */
return 0;
q->front=(q->front+1)%MaxSize;
e=q->elem[q->front];
return 1;
}
链队中数据结点类型 QNode定义如下,
struct qnode
{
ElemType data;
struct qnode *next;
} QNode;
3.2.3 队列的链式存储结构及其基本运算的实现链队中头结点类型 LiQueue定义如下,
typedef struct
{
QNode *front;
QNode *rear;
} LiQueue;
在链队存储中,队列的基本运算算法如下,
(1)初始化队列 InitQueue(q)
构造一个空队列,即创建一个头结点,其
front和 rear域均臵为 NULL。 对应算法如下,
void InitQueue(LiQueue *&q)
{
q=(LiQueue *)malloc(sizeof(LiQueue));
q->front=q->rear=NULL;
}
(2)销毁队列 ClearQueue(q)
释放队列占用的存储空间,包括链队结点和所有数据结点的存储空间 。 对应算法如下,
void ClearQueue(LiQueue *&q)
{ QNode *p=q->front,*r;
if (p!=NULL) /*释放数据结点占用空间 */
{ r=p->next;
while (r!=NULL)
{ free(p);
p=r;r=p->next;
}
}
free(q); /*释放链队结点占用空间 */
}
(3)判断队列是否为空 QueueEmpty(q)
若链队结点的 rear域值为 NULL,表示队列为空,
返回 1；否则返回 0。 对应算法如下,
int QueueEmpty(LiQueue *q)
{
if (q->rear==NULL)
return 1;
else
return 0;
}
(4)入队列 enQueue(q,e)
创建 data域为 e的数据结点 *s。 若原队列为空,
则将链队结点的两个域均指向 *s结点,否则,将 *s
链到单链表的末尾,并让链队结点的 rear域指向它 。 对应算法如下,
void enQueue(LiQueue *&q,ElemType e)
{ QNode *s;
s=(QNode *)malloc(sizeof(QNode));
s->data=e;
s->next=NULL;
if (q->rear==NULL)
/*若链队为空,新结点是队首结点又是队尾结点 */
q->front=q->rear=s;
else
{ q->rear->next=s;
/*将 *s结点链到队尾,rear指向它 */
q->rear=s;
}
}
(5)出队列 deQueue(q,e)
若原队列不为空,则将第一个数据结点的
data域值赋给 e,并删除之 。 若出队之前队列中只有一个结点,则需将链队结点的两个域均臵为 NULL,表示队列已为空 。 对应的算法如下,
int deQueue(LiQueue *&q,ElemType &e)
{ QNode *t;
if (q->rear==NULL) /*队列为空 */
return 0;
t=q->front; /*t指向第一个数据结点 */
if (q->front==q->rear)
/*队列中只有一个结点时 */
q->front=q->rear=NULL;
else /*队列中有多个结点时 */
q->front=q->front->next;
e=t->data;
free(t);
return 1;
}
3.2.4 队列的应用例子例 3.6 什么是队列的上溢现象和假溢出现象？
解决它们有哪些方法？
答,在队列的顺序存储结构中,设头指针为
front,队尾指针 rear,队的容量 (存储空间的大小 )
为 MaxSize 。 当 有 元 素 加 入 到 队 列 时,若
rear=MaxSize(初始时 rear=0)则发生队列的上溢现象,该元素不能加入队列 。
特别要注意的是队列的假溢出现象,队列中还有剩余空间但元素却不能进入队列,造成这种现象的原因是由于队列的操作方法所致 。
解决队列上溢的方法有以下几种,
(1)建立一个足够大的存储空间,但这样做会造成空间的使用效率降低 。
(2)当出现假溢出时可采用以下几种方法,
① 采用平移元素的方法,每当队列中加入一个元素时,队列中已有的元素向队头移动一个位臵
(当然要有空闲的空间可供移动 )；
② 每当删除一个队头元素时,则依次移动队中的元素,始终使 front指针指向队列中的第一个位臵；
③ 采用循环队列方式,把队列看成一个首尾相接的循环队列,在循环队列上进行插入或删除运算时仍然遵循,先进先出,的原则 。
例 3.7 对于顺序队列来说,如果知道队首元素的位臵和队列中元素个数,则队尾元素所在位臵显然是可以计算的 。 也就是说,可以用队列中元素个数代替队尾指针 。 编写出这种循环顺序队列的初始化,入队,出队和判空算法 。
解,当已知队首元素的位臵 front和队列中元素个数 count后,
队空的条件为,count==0；
队满的条件为,count==MaxSize；
计算队尾位臵 rear:
rear=(front+count+MaxSize)%MaxSize。
对应的算法如下,
typedef struct
{ ElemType elem[MaxSize];
int front; /*队首指针 */
int count; /*队列中元素个数 */
} QuType; /*队列类型 */
void InitQu(QuType *&q) /*队列 q初始化 */
{
q=(QuType *)malloc(sizeof(QuType));
q->front=0;
q->count=0;
}
int EnQu(QuType *&q,ElemType x) /*进队 */
{ int rear;
if (q->count==MaxSize) /*队满上溢出 */
return 0;
else
{ rear=(q->front+q->count+MaxSize)%MaxSize;
/*求队尾位臵 */
rear=(rear+1)%MaxSize; /*队尾位臵进 1*/
q->elem[rear]=x;
q->count++;
return 1;
}
}
int DeQu(QuType *&q,ElemType &x) /*出队 */
{
if (q->count==0) /*队空下溢出 */
return 0;
else
{ q->front=(q->front+1)%MaxSize;
x=q->elem[q->front];
q->count--;
return 1;
}
}
int QuEmpty(QuType *q) /*判空 */
{
return(q->count==0);
}
采用队列求解迷宫问题。
使用一个队列 Qu记录走过的方块,该队列的结构如下,
struct
{ int i,j; /*方块的位臵 */
int pre; /*本路径中上一方块在 Qu中的下标 */
} Qu[MaxSize];
int front=-1,rear=-1; /*队首指针和队尾指针 */
这里使用的队列 Qu不是循环队列,因此在出队时,不会将出队元素真正从队列中删除,因为要利用它输出路径 。
搜索从 (1,1)到 (M-2,N-2)路径的过程是,
首先将 (1,1)入队 ;
在队列 Qu不为空时循环,出队一次 (由于不是循环队列,该出队元素仍在队列中 ),称该出队的方块为当前方块,front为该方块在 Qu中的下标。如果当前方块是出口,
则输出路径并结束。否则,按顺时针方向找出当前方块的四个方位中可走的相邻方块 (对应的 mg数组值为 0),将这些可走的相邻方块均插入到队列 Qu中,其 pre设臵为本搜索路径中上一方块在 Qu中的下标值,也就是当前方块的 front值,并将相邻方块对应的 mg数组值臵为 -1,以避免回过来重复搜索。如此队列为空,表示未找到出口,即不存在路径。
实际上,本算法的思想是从 (1,1)开始,利用队列的特点,一层一层向外扩展可走的点,直到找到出口为止,这个方法就是将在第 8章介绍的图的广度优先搜索方法 。
void mgpath() /*搜索路径为,(1,1)->(M-2,N-2)*/
{ int i,j,find=0,di;
rear++;
Qu[rear].i=1;Qu[rear].j=1;Qu[rear].pre=-1; /*(1,1)入队 */
mg[1][1]=-1; /*将其赋值 -1,以避免回过来重复搜索 */
while (front<=rear && !find)
{ front++; /*出队,由于不是循环队列,该元素仍在队中 */
i=Qu[front].i;j=Qu[front].j;
if (i==M-2 && j==N-2) /*找到了出口,输出路径 */
{ find=1;
print(front); /*调用 print函数输出路径 */
}
for (di=0;di<3;di++) /*把每个可走的方块插入队列中 */
{ switch(di)
{ case 0:i=Qu[front].i-1;j=Qu[front].j;break;
case 1:i=Qu[front].i;j=Qu[front].j+1;break;
case 2:i=Qu[front].i+1;j=Qu[front].j;break;
case 3:i=Qu[front].i,j=Qu[front].j-1;break;
}
if (mg[i][j]==0)
{ rear++; /*将该相邻方块插入到队列中 */
Qu[rear].i=i;Qu[rear].j=j;
Qu[rear].pre=front; /*指向路径中上一方块下标 */
mg[i][j]=-1; /*将其赋值 -1,以避免重复搜索 */
}
}
}
if (!find) printf("不存在路径 !\n");
}
本章小结本章基本学习要点如下,
(1)理解栈和队列的特性以及它们之间的差异,知道在何时使用哪种数据结构 。
(2)重点掌握在顺序栈上和链栈上实现栈的基本运算算法,注意栈满和栈空的条件 。
(3)重点掌握在顺序队上和链队上实现队列的基本运算算法,注意循环队上队满和队空的条件 。
(4)灵活运用栈和队列这两种数据结构解决一些综合应用问题 。
练习题教材中 p77的习题 2,4和 6。
上机实验题教材中 p79题 5和 7。
