第3章栈和队列







3.1验证性实验
实验题1： 实现顺序栈的各种基本运算的算法
目的： 领会顺序栈的存储结构和掌握顺序栈中各种基本运算算法的设计。
内容： 编写一个程序sqstack.cpp，实现顺序栈(假设栈中的元素类型ElemType为char)的各种基本运算，并在此基础上设计一个程序exp31.cpp完成以下功能。
(1) 初始化栈s。
(2) 判断栈s是否非空。
(3) 依次进栈元素a、b、c、d、e。
(4) 判断栈s是否非空。
(5) 输出出栈序列。
(6) 判断栈s是否非空。
(7) 释放栈。
 
 根据《教程》中3.1.2节的算法得到sqstack.cpp程序，其中包含如下函数。
 InitStack(SqStack *&s)： 初始化顺序栈s。
 DestroyStack(SqStack *&s)： 销毁顺序栈s。
 StackEmpty(SqStack *s)： 判断顺序栈s是否为空栈。
 Push(SqStack *&s，ElemType e)： 元素e进顺序栈。
 Pop(SqStack *&s，ElemType &e)： 元素e出顺序栈。
 GetTop(SqStack *s，ElemType &e)： 取顺序栈的栈顶元素e。
对应的程序代码如下(设计思路详见代码中的注释)： 



#include <stdio.h>

#include <malloc.h>

#define MaxSize 100

typedef char ElemType;

typedef struct

{ElemType data［MaxSize］;

int top;//栈顶指针

} SqStack;//声明顺序栈类型

void InitStack(SqStack *&s)//初始化顺序栈

{s=(SqStack *)malloc(sizeof(SqStack));

s->top=-1;

}

void DestroyStack(SqStack *&s)//销毁顺序栈

{

free(s);

}

bool StackEmpty(SqStack *s)//判断栈是否为空栈

{

return(s->top==-1);






}

bool Push(SqStack *&s，ElemType e)//进栈

{if (s->top==MaxSize-1)//栈满的情况，即栈上溢出

return false;

s->top++;

s->data［s->top］=e;

return true;

}

bool Pop(SqStack *&s，ElemType &e)//出栈

{if (s->top==-1)//栈为空的情况，即栈下溢出

return false;

e=s->data［s->top］;

s->top--;

return true;

}

bool GetTop(SqStack *s，ElemType &e)//取栈顶元素

{if (s->top==-1) //栈为空的情况，即栈下溢出

return false;

e=s->data［s->top］;

return true;

}





实验程序exp31.cpp的结构如图3.1所示，图中方框表示函数，方框中指出函数名； 箭头方向表示函数间的调用关系； 虚线方框表示文件的组成，即指出该虚线方框中的函数存放在哪个文件中。



图3.1exp31.cpp程序的结构


 
 实验程序exp31.cpp的代码如下： 



#include "sqstack.cpp"//包含顺序栈的基本运算算法

int main()

{ElemType e;

SqStack *s;

printf("顺序栈s的基本运算如下:＼n");

printf("(1)初始化栈s＼n");

InitStack(s);

printf("(2)栈为%s＼n"，(StackEmpty(s)?"空":"非空"));

printf("(3)依次进栈元素a，b，c，d，e＼n");






Push(s，'a');

Push(s，'b');

Push(s，'c');

Push(s，'d');

Push(s，'e');

printf("(4)栈为%s＼n"，(StackEmpty(s)?"空":"非空"));

printf("(5)出栈序列:");

while (!StackEmpty(s))

{Pop(s，e);

printf("%c "，e);

}

printf("＼n");

printf("(6)栈为%s＼n"，(StackEmpty(s)?"空":"非空"));

printf("(7)释放栈＼n");

DestroyStack(s);

return 1;

}





 
 exp31.cpp程序的执行结果如图3.2所示。



图3.2exp31.cpp程序的执行结果


实验题2： 实现链栈的各种基本运算的算法
目的： 领会链栈的存储结构和掌握链栈中各种基本运算算法的设计。
内容： 编写一个程序listack.cpp，实现链栈(假设栈中的元素类型ElemType为char)的各种基本运算，并在此基础上设计一个程序exp32.cpp完成以下功能。
(1) 初始化栈s。
(2) 判断栈s是否非空。
(3) 依次进栈元素a、b、c、d、e。
(4) 判断栈s是否非空。
(5) 输出出栈序列。
(6) 判断栈s是否非空。
(7) 释放栈。
 
 根据《教程》中3.1.3节的算法得到listack.cpp程序，其中包含如下函数。
 InitStack(LinkStNode *&s)： 初始化链栈s。
 DestroyStack(LinkStNode *&s)： 销毁链栈s。
 StackEmpty(LinkStNode *s)： 判断链栈s是否为空栈。
 Push(LinkStNode *&s，ElemType e)： 元素e进链栈。
 Pop(LinkStNode *&s，ElemType &e)： 元素e出链栈。
 GetTop(LinkStNode *s，ElemType &e)： 取链栈的栈顶元素e。
对应的程序代码如下(设计思路详见代码中的注释)： 



#include <stdio.h>

#include <malloc.h>

typedef char ElemType;

typedef struct linknode

{ElemType data;//数据域

struct linknode *next;//指针域

} LinkStNode;//链栈类型定义

void InitStack(LinkStNode *&s)//初始化链栈

{s=(LinkStNode *)malloc(sizeof(LinkStNode));

s->next=NULL;

}

void DestroyStack(LinkStNode *&s)//销毁链栈

{LinkStNode *p=s->next;

while (p!=NULL)

{free(s);

s=p;

p=p->next;

}

free(s);//s指向尾结点,释放其空间

}

bool StackEmpty(LinkStNode *s)//判断栈是否为空栈

{

return(s->next==NULL);

}

void Push(LinkStNode *&s,ElemType e)//进栈

{LinkStNode *p;

p=(LinkStNode *)malloc(sizeof(LinkStNode));

p->data=e;//新建元素e对应的结点p

p->next=s->next;//插入p结点作为开始结点

s->next=p;

}

bool Pop(LinkStNode *&s,ElemType &e)//出栈

{LinkStNode *p;

if (s->next==NULL)//栈空的情况

return false;

p=s->next;//p指向开始结点

e=p->data;

s->next=p->next;//删除p结点






free(p);//释放p结点

return true;

}

bool GetTop(LinkStNode *s,ElemType &e)//取栈顶元素

{if (s->next==NULL)//栈空的情况

return false;

e=s->next->data;

return true;

}







实验程序exp32.cpp的结构如图3.3所示，图中方框表示函数，方框中指出函数名； 箭头方向表示函数间的调用关系； 虚线方框表示文件的组成，即指出该虚线方框中的函数存放在哪个文件中。



图3.3exp32.cpp程序的结构


 
 实验程序exp32.cpp的代码如下： 




#include "listack.cpp"//包含链栈的基本运算算法

int main()

{ElemType e;

LinkStNode *s;

printf("链栈s的基本运算如下:＼n");

printf("(1)初始化栈s＼n");

InitStack(s);

printf("(2)栈为%s＼n",(StackEmpty(s)?"空":"非空"));

printf("(3)依次进栈元素a,b,c,d,e＼n");

Push(s,'a');

Push(s,'b');

Push(s,'c');

Push(s,'d');

Push(s,'e');

printf("(4)栈为%s＼n",(StackEmpty(s)?"空":"非空"));

printf("(5)出栈序列:");

while (!StackEmpty(s))

{Pop(s,e);

printf("%c ",e);

}

printf("＼n");






printf("(6)栈为%s＼n",(StackEmpty(s)?"空":"非空"));

printf("(7)释放栈＼n");

DestroyStack(s);

return 1;

}





 
 exp32.cpp程序的执行结果如图3.4所示。



图3.4exp32.cpp程序的执行结果


实验题3： 实现环形队列的各种基本运算的算法
目的： 领会环形队列的存储结构和掌握环形队列中各种基本运算算法的设计。
内容： 编写一个程序sqqueue.cpp，实现环形队列(假设栈中的元素类型ElemType为char)的各种基本运算，并在此基础上设计一个程序exp33.cpp完成以下功能。
(1) 初始化队列q。
(2) 判断队列q是否非空。
(3) 依次进队元素a、b、c。
(4) 出队一个元素，输出该元素。
(5) 依次进队元素d、e、f。
(6) 输出出队序列。
(7) 释放队列。
 
 根据《教程》中3.2.2节的算法得到sqqueue.cpp程序，其中包含如下函数。
 InitQueue(SqQueue *&q)： 初始化环形队列q。
 DestroyQueue(SqQueue *&q)： 销毁环形队列q。
 QueueEmpty(SqQueue *q)： 判断环形队列q是否为空。
 enQueue(SqQueue *&q，ElemType e)： 环形队列进队一个元素e。
 deQueue(SqQueue *&q，ElemType &e)： 环形队列出队一个元素e。
对应的程序代码如下(设计思路详见代码中的注释)： 



#include <stdio.h>

#include <malloc.h>

#define MaxSize 100






typedef char ElemType;

typedef struct

{ElemType data［MaxSize］;

int front,rear;//队首和队尾指针

} SqQueue;//声明环形队列类型

void InitQueue(SqQueue *&q)//初始化队列q

{q=(SqQueue *)malloc (sizeof(SqQueue));

q->front=q->rear=0;

}

void DestroyQueue(SqQueue *&q)//销毁队列q

{

free(q);

}

bool QueueEmpty(SqQueue *q)//判断队列q是否为空

{

return(q->front==q->rear);

}

bool enQueue(SqQueue *&q,ElemType e)//进队

{if ((q->rear+1)%MaxSize==q->front)

return false;//队满，上溢出，返回false

q->rear=(q->rear+1)%MaxSize;

q->data［q->rear］=e;

return true;

}

bool deQueue(SqQueue *&q,ElemType &e)//出队

{if (q->front==q->rear) 

return false;//队空，下溢出，返回false

q->front=(q->front+1)%MaxSize;

e=q->data［q->front］;

return true;

}





实验程序exp33.cpp的结构如图3.5所示,图中方框表示函数,方框中指出函数名； 箭头方向表示函数间的调用关系； 虚线方框表示文件的组成，即指出该虚线方框中的函数存放在哪个文件中。



图3.5exp33.cpp程序的结构


 
 实验程序exp33.cpp的代码如下： 



#include "sqqueue.cpp"//包含环形队列的基本运算算法

int main()

{ElemType e;

SqQueue *q;

printf("环形队列基本运算如下:＼n");

printf("(1)初始化队列q＼n");

InitQueue(q);

printf("(2)依次进队列元素a,b,c＼n");

if (!enQueue(q,'a')) printf("＼t提示:队满,不能进队＼n");

if (!enQueue(q,'b')) printf("＼t提示:队满,不能进队＼n");

if (!enQueue(q,'c')) printf("＼t提示:队满,不能进队＼n");

printf("(3)队列为%s＼n",(QueueEmpty(q)?"空":"非空"));

if (deQueue(q,e)==0) 

printf("队空,不能出队＼n");

else

printf("(4)出队一个元素%c＼n",e);

printf("(5)依次进队列元素d,e,f＼n");

if (!enQueue(q,'d')) printf("＼t提示:队满,不能进队＼n");

if (!enQueue(q,'e')) printf("＼t提示:队满,不能进队＼n");

if (!enQueue(q,'f')) printf("＼t提示:队满,不能进队＼n");

printf("(6)出队列序列:");

while (!QueueEmpty(q))

{deQueue(q,e);

printf("%c ",e);

}

printf("＼n");

printf("(7)释放队列＼n");

DestroyQueue(q);

return 1;

}





 
 exp33.cpp程序的执行结果如图3.6所示。执行结果表明环形队列q中最多只能存放MaxSize-1(=4)个元素。



图3.6exp33.cpp程序的执行结果


实验题4： 实现链队的各种基本运算的算法
目的： 领会链队的存储结构和掌握链队中各种基本运算算法的设计。
内容： 编写一个程序liqueue.cpp，实现链队(假设栈中的元素类型ElemType为char)的各种基本运算，并在此基础上设计一个程序exp34.cpp完成以下功能。
(1) 初始化链队q。
(2) 判断链队q是否非空。
(3) 依次进队元素a、b、c。
(4) 出队一个元素，输出该元素。
(5) 依次进队元素d、e、f。
(6) 输出出队序列。
(7) 释放链队。
 
 根据《教程》中3.2.3节的算法得到liqueue.cpp程序，其中包含如下函数。
 InitQueue(LinkQuNode *&q)： 初始化链队q。
 DestroyQueue(LinkQuNode *&q)： 销毁链队q。
 QueueEmpty(LinkQuNode *q)： 判断链队q是否为空。
 enQueue(LinkQuNode *&q，ElemType e)： 链队进队一个元素e。
 deQueue(LinkQuNode *&q，ElemType &e)： 链队出队一个元素e。

对应的程序代码如下(设计思路详见代码中的注释)： 



#include <stdio.h>

#include <malloc.h>

typedef char ElemType;

typedef struct DataNode

{ElemType data;

struct DataNode *next;

} DataNode;//声明链队数据结点类型

typedef struct

{DataNode *front;

DataNode *rear;

} LinkQuNode;//声明链队类型

void InitQueue(LinkQuNode *&q)//初始化队列q

{q=(LinkQuNode *)malloc(sizeof(LinkQuNode));

q->front=q->rear=NULL;

}

void DestroyQueue(LinkQuNode *&q)//销毁队列q

{DataNode *p=q->front,*r;//p指向队头数据结点

if (p!=NULL)//释放数据结点占用的空间

{r=p->next;

while (r!=NULL)

{free(p);

p=r;r=p->next;

}

}

free(p);






free(q);//释放链队结点占用的空间

}

bool QueueEmpty(LinkQuNode *q)//判断队列q是否为空

{

return(q->rear==NULL);

}

void enQueue(LinkQuNode *&q,ElemType e)//进队

{DataNode *p;

p=(DataNode *)malloc(sizeof(DataNode));

p->data=e;

p->next=NULL;

if (q->rear==NULL)//若链队为空,则新结点既是队首结点又是队尾结点

q->front=q->rear=p;

else

{q->rear->next=p;//将p结点链到队尾,并将rear指向它

q->rear=p;

}

}

bool deQueue(LinkQuNode *&q,ElemType &e)//出队

{DataNode *t;

if (q->rear==NULL)//队列为空

return false;

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 true;

}






实验程序exp34.cpp的结构如图3.7所示，图中方框表示函数，方框中指出函数名； 箭头方向表示函数间的调用关系； 虚线方框表示文件的组成，即指出该虚线方框中的函数存放在哪个文件中。



图3.7exp34.cpp程序的结构


 
 实验程序exp34.cpp的代码如下： 



#include "liqueue.cpp"//包含链队的基本运算算法

int main()

{ElemType e;

LinkQuNode *q;

printf("链队的基本运算如下:＼n");

printf("(1)初始化链队q＼n");

InitQueue(q);

printf("(2)依次进链队元素a,b,c＼n");

enQueue(q,'a');

enQueue(q,'b');

enQueue(q,'c');

printf("(3)链队为%s＼n",(QueueEmpty(q)?"空":"非空"));

if (deQueue(q,e)==0) 

printf("＼t提示:队空,不能出队＼n");

else

printf("(4)出队一个元素%c＼n",e);

printf("(5)依次进链队元素d,e,f＼n");

enQueue(q,'d');

enQueue(q,'e');

enQueue(q,'f');

printf("(6)出链队序列:");

while (!QueueEmpty(q))

{deQueue(q,e);

printf("%c ",e);

}

printf("＼n");

printf("(7)释放链队＼n");

DestroyQueue(q);

return 1;

}





 
 exp34.cpp程序的执行结果如图3.8所示。



图3.8exp34.cpp程序的执行结果



3.2设计性实验
实验题5： 用栈求解迷宫问题的所有路径及最短路径
目的： 掌握栈在求解迷宫问题中的应用。
内容： 编写一个程序exp35.cpp，改进《教程》3.1.4节中的求解迷宫问题程序，要求输出如图3.9所示的迷宫的所有路径，并求第一条最短路径及其长度。

 
 在本实验中用mg作为迷宫数组，用St数组作为顺序栈，Path数组保存一条迷宫路径，将它们都设置为全局变量。设计的功能算法如下。
 mgpath(int xi，int yi，int xe，int ye)： 求解迷宫问题，即输出从入口(xi，yi)到出口(xe，ye)的全部路径和最短路径(包含最短路径长度)。与《教程》3.1.4节中的求解迷宫问题程序相比，其改进的方法是当找到一条路径时不使用return语句退出，而是出栈一次，重新回溯走另一条路径并输出，并用minlen记录最短路径长度，用Path数组记录最短路径。
 dispapath()： 输出一条路径并求最短路径。
 dispminpath()： 输出第一条最短路径及其长度。
实验程序exp35.cpp的结构如图3.10所示，图中方框表示函数，方框中指出函数名； 箭头方向表示函数间的调用关系； 虚线方框表示文件的组成，即指出该虚线方框中的函数存放在哪个文件中。



图3.9迷宫示意图




图3.10exp35.cpp程序的结构



 
 实验程序exp35.cpp的代码如下(设计思路详见代码中的注释)： 



#include <stdio.h>

#define M 4//行数

#define N 4//列数

#define MaxSize 100//栈中最多元素个数

int mg［M+2］［N+2］={//一个迷宫,其四周加上均为1的外框

{1,1,1,1,1,1},{1,0,0,0,1,1},{1,0,1,0,0,1},

{1,0,0,0,1,1},{1,1,0,0,0,1},{1,1,1,1,1,1}};

struct

{int i,j;

int di;






} St［MaxSize］,Path［MaxSize］;//定义栈和存放最短路径的数组

int top=-1;//栈顶指针

int count=1;//路径数计数

int minlen=MaxSize;//最短路径长度

void dispapath()//输出一条路径并求最短路径

{int k;

printf("%5d: ",count++);//输出第count条路径

for (k=0;k<=top;k++)

printf("(%d,%d) ",St［k］.i,St［k］.j);

printf("＼n");

if (top+1<minlen)//比较找最短路径

{for (k=0;k<=top;k++)//将最短路径存放在Path中

Path［k］=St［k］;

minlen=top+1;//将最短路径长度存放在minlen中

}

}

void dispminpath()//输出第一条最短路径

{printf("最短路径如下:＼n");

printf("长度: %d＼n",minlen);

printf("路径: ");

for (int k=0;k<minlen;k++)

printf("(%d,%d) ",Path［k］.i,Path［k］.j);

printf("＼n");

}

void mgpath(int xi,int yi,int xe,int ye) //求迷宫路径

{int i,j,i1,j1,di;

bool find;

top++;//进栈

St［top］.i=xi;

St［top］.j=yi;

St［top］.di=-1;mg［xi］［yi］=-1;//初始方块进栈

while (top>-1)//栈不空时循环

{i=St［top］.i;j=St［top］.j;//取栈顶方块(i,j)

di=St［top］.di;

if (i==xe && j==ye)//找到了出口

{dispapath();//输出一条路径

mg［i］［j］=0;//让出口变为其他路径可走方块

top--;//出口退栈,即回退一个方块

i=St［top］.i;j=St［top］.j;

di=St［top］.di;//让栈顶方块变为当前方块

}

find=false;//找下一个可走方块(i1,j1)

while (di<4 && !find)

{di++;

switch(di)

{

case 0:i1=i-1; j1=j;break;

case 1:i1=i;j1=j+1; break;

case 2:i1=i+1;j1=j;break;

case 3:i1=i,j1=j-1; break;






}

if (mg［i1］［j1］==0) find=true;

}

if (find)//找到了下一个可走方块(i1,j1)

{St［top］.di=di;//修改原栈顶元素的di值

top++;St［top］.i=i1;St［top］.j=j1;

St［top］.di=-1;//下一个可走方块(i1,j1)进栈

mg［i1］［j1］=-1;//避免重复走到该方块

}

else//没有路径可走,则(i,j)方块退栈

{mg［i］［j］=0;//让该位置变为其他路径可走方块

top--;

}

}

dispminpath();//输出最短路径

}

int main()

{printf("迷宫所有路径如下:＼n");

mgpath(1,1,M,N);

return 1;

}







 
 exp35.cpp程序的执行结果如图3.11所示，该迷宫从入口(1，1)到出口(4，4)共有4条路径，第一条最短路径的长度为7。



图3.11exp35.cpp程序的执行结果


实验题6： 编写病人看病模拟程序
目的： 掌握队列应用的算法设计。
内容： 编写一个程序exp36.cpp，反映病人到医院排队看病的情况。在病人排队过程中主要重复下面两件事。
(1) 病人到达诊室，将病历本交给护士，排到等待队列中候诊。
(2) 护士从等待队列中取出下一位病人的病历，该病人进入诊室就诊。
要求模拟病人等待就诊这一过程。程序采用菜单方式，其选项及功能说明如下。
1： 排队——输入排队病人的病历号，加入病人排队队列中。
2： 就诊——病人排队队列中最前面的病人就诊，并将其从队列中删除。
3： 查看排队——从队首到队尾列出所有排队病人的病历号。
4： 不再排队，余下依次就诊——从队首到队尾列出所有排队病人的病历号，并退出运行。
5： 下班——退出运行。
 
 本实验中采用一个链队qu存放病人排队的情况，链队头结点类型为QuType，链队结点类型为QNode。设计的功能算法如下。
 SeeDoctor()： 模拟病人看病的过程。病人排队看病要用到一个队列，这里设计了一个不带头结点的单链表作为队列。


图3.12exp36.cpp程序的结构

 Destroyqueue(QuType *&qu)： 释放病人排队所建立的就医链队。
 exist(QuType *qu，int no)： 队列中是否有病历号no的病人在排队。
实验程序exp36.cpp的结构如图3.12所示，图中方框表示函数，方框中指出函数名； 箭头方向表示函数间的调用关系； 虚线方框表示文件的组成，即指出该虚线方框中的函数存放在哪个文件中。
 
 实验程序exp36.cpp的代码如下(设计思路详见代码中的注释)： 



#include <stdio.h>

#include <malloc.h>

typedef struct qnode

{int data;//病历号

struct qnode *next;//下一个结点指针

} QNode;//链队结点类型

typedef struct

{

QNode *front,*rear;

} QuType;//声明链队类型

void Destroyqueue(QuType *&qu)//释放链队

{QNode *pre,*p;

pre=qu->front; 

if (pre!=NULL)//若链队不为空

{p=pre->next;

while (p!=NULL)//释放队列中的所有数据结点

{free(pre);

pre=p;p=p->next;

}

free(pre);

}

free(qu);//释放链队结点

}

bool exist(QuType *qu,int no)//队列中是否有病历号no的病人






{bool find=false;

QNode *p=qu->front;

while (p!=NULL && !find)

{if (p->data==no)find=true;

elsep=p->next;

}

return find;

}

void SeeDoctor()//模拟病人看病的过程

{int sel,no;

bool flag=true;

QuType *qu;

QNode *p;

qu=(QuType *)malloc(sizeof(QuType));//创建空队

qu->front=qu->rear=NULL;

while (flag) //循环执行

{printf(">1:排队 2:就诊 3:查看排队 4.不再排队,余下依次就诊 5:下班请选择:");

scanf("%d",&sel); 

switch(sel) 

{

case 1://排队

printf("输入病历号:");

while (true)

{scanf("%d",&no);

if (exist(qu,no))

printf("输入的病历号重复,重新输入:");

else

break;

};

p=(QNode *)malloc(sizeof(QNode));   //创建结点

p->data=no;p->next=NULL;

if (qu->rear==NULL)//第一个病人排队

qu->front=qu->rear=p;

else

{qu->rear->next=p; 

qu->rear=p;//将p结点进队

}

break;

case 2://就诊

if (qu->front==NULL)//队为空

printf("没有排队的病人!＼n");

else//队不为空

{p=qu->front;

printf(">>病人%d就诊＼n",p->data);

if (qu->rear==p)//只有一个病人排队的情况

qu->front=qu->rear=NULL;

else

qu->front=p->next;

free(p);

}






break;

case 3://查看排队

if (qu->front==NULL)//队为空

printf("没有排队的病人!＼n");

else //队不为空

{p=qu->front;

printf(">>排队病人:");

while (p!=NULL) 

{printf("%d ",p->data);

p=p->next;

}

printf("＼n");

}

break;

case 4://不再排队,余下依次就诊

if (qu->front==NULL)//队为空

printf(">>没有排队的病人!＼n");

else//队不为空

{p=qu->front;

printf(">>病人按以下顺序就诊:");

while (p!=NULL) 

{printf("%d ",p->data);

p=p->next;

}

printf("＼n");

}

Destroyqueue(qu);//释放链队

flag=false;//退出

break;

case 5://下班

if (qu->front!=NULL)//队不为空

printf("请排队的病人明天就医!＼n");

flag=false;//退出

Destroyqueue(qu);//释放链队

break;

}

}

}

int main()

{SeeDoctor();

return 1;

}






 
 exp36.cpp程序的一次执行过程如图3.13所示。首先病人1、2排队，病人1就诊，接着病人3、4参加排队，通过查看队列发现排队病人是2、3、4，然后病人2就诊，最后病人3、4依次就诊。



图3.13exp36.cpp程序的一次执行过程


实验题7： 求解栈元素排序问题
目的： 掌握栈应用的算法设计。
内容： 编写一个程序exp37.cpp，按升序对一个字符栈进行排序，即最小元素位于栈顶,注意最多只能使用一个额外的栈存放临时数据，并输出栈排序的过程。
 
 本实验中采用一个额外的栈tmpst存放临时数据。设计的功能算法为StackSort(SqStack *&st)，即对栈st中的元素排序。其思路是处理栈st的某个栈顶元素e，出栈元素e，将其存放在tmpst中。若临时栈tmpst为空，直接将e进入栈tmpst； 若栈tmpst不为空，将它的元素退栈(放入栈st中)直到tmpst栈顶元素小于e，再将tmp进入栈tmpst中，如图3.14所示为处理栈st的栈顶元素3的过程。进行这样的过程直到st为空，而tmpst中的元素从栈底到栈顶是递增的。再将tmpst中的所有元素退栈并进到栈st中。



图3.14处理st的栈顶元素3的过程



实验程序exp37.cpp的结构如图3.15所示，图中方框表示函数，方框中指出函数名； 箭头方向表示函数间的调用关系； 虚线方框表示文件的组成，即指出该虚线方框中的函数存放在哪个文件中。


图3.15exp37.cpp程序的结构


 
 实验程序exp37.cpp的代码如下(设计思路详见代码中的注释)： 



#include "sqstack.cpp"//包含顺序栈的基本运算算法

void StackSort(SqStack *&st)//对栈st中的元素排序

{SqStack *tmpst;

InitStack(tmpst);

ElemType e,e1;

while (!StackEmpty(st))//栈st不为空时循环

{Pop(st,e);//出栈元素e

printf("st:出栈%c=> ",e);

while(!StackEmpty(tmpst))

{GetTop(tmpst,e1);

printf("tmpst:取栈顶元素%c ",e1);

if (e1>e)

{printf("因%c>%c ",e1,e);

printf("tmpst:退栈%c ",e1);

Pop(tmpst,e1);

printf("s:进栈%c ",e1);

Push(st,e1);

}

else

{printf("因%c<%c,退出循环 ",e1,e);

break;

}

}

Push(tmpst,e);

printf("tmpst:进栈%c＼n",e);

}

while (!StackEmpty(tmpst))

{Pop(tmpst,e);

Push(st,e);

}

DestroyStack(tmpst);






}

int main()

{ElemType e;

SqStack *s;

InitStack(s);

printf("(1)依次进栈元素1,3,4,2＼n");

Push(s,'1');

Push(s,'3');

Push(s,'4');

Push(s,'2');

printf("(2)栈s排序过程:＼n");

StackSort(s);

printf("(3)栈s排序完毕＼n");

printf("(4)s的出栈序列:");

while (!StackEmpty(s))

{Pop(s,e);

printf("%c ",e);

}

printf("＼n");

DestroyStack(s);

return 1;

}






 
 exp37.cpp程序的执行过程如图3.16所示。



图3.16exp37.cpp程序的执行过程



3.3综合性实验
实验题8： 用栈求解n皇后问题
目的： 深入掌握栈应用的算法设计。
内容： 编写一个程序exp38.cpp求解n皇后问题，即在n×n的方格棋盘上放置n个皇后，要求每个皇后不同行、不同列、不同左右对角线。如图3.17所示为八皇后问题的一个解。在本实验中，皇后个数n由用户输入，其值不能超过20，输出所有的解； 采用类似于用栈求解迷宫问题的方法。



图3.17八皇后问题


 
 用col［1..n］数组存放n个皇后的位置，其中col［i］表示第i(1≤i≤n)个皇后的列号，即第i个皇后的位置是(i，col［i］)。例如图3.17所示的八皇后问题的解表示为col［1..8］={4，7，3，8，2，5，1，6}。本实验中使用一个顺序栈St，其类型如下： 



typedef struct

{int col［MaxSize］;//col［i］存放第i个皇后的列号

int top;//栈顶指针

} StackType;//声明顺序栈类型





如同用栈求解迷宫问题，找到出口后栈中所有方块构成一条迷宫路径一样，这里栈St中保存当前已经放好的皇后的位置，若其中的皇后个数为n，表示得到一个解。设计的功能算法如下。
 dispasolution(StackType St)： 输出一个皇后问题解，即n个皇后的位置是(1，St.col［1］)，(2，St.col［2］)，…，(n，St.col［n］)。
 place(StackType St，int k，int j)： 对于第k个皇后，测试(k，j)(j从第1列开始)是否与栈中已放置好的第1~k-1个皇后有冲突，St.col［k］用于存放第k个皇后的列号，即该皇后的位置为(k，St.col［k］)。对于位置(i，j)(1≤i≤k-1)上的皇后，是否与位置(k，St.col［k］)有冲突呢？不同行是显然的，若同列则有St.col［k］==j。再考虑两条对角线冲突，如图3.18所示，若它们在任意一条对角线上，则构成一个等边直角三角形，即|j-St.col［k］|==|k-i|。所以，只要满足以下条件就表示存在冲突，否则表示不存在冲突： 
(St.col［k］==j) ‖ (abs(j-St.col［k］)==abs(k-i))

 queen(int n)： 用于求解n皇后问题，并输出所有解。
实验程序exp38.cpp的结构如图3.19所示，图中方框表示函数，方框中指出函数名； 箭头方向表示函数间的调用关系； 虚线方框表示文件的组成，即指出该虚线方框中的函数存放在哪个文件中。



图3.18两个皇后构成对角线的情况




图3.19exp38.cpp程序的结构



 
 实验程序exp38.cpp的代码如下(设计思路详见代码中的注释)： 




#include <stdio.h>

#include <stdlib.h>

#define MaxSize 100

typedef struct

{int col［MaxSize］;//col［i］存放第i个皇后的列号

int top;//栈顶指针

} StackType;//声明顺序栈类型

void dispasolution(StackType St)//输出一个解

{static int count=0;//静态变量用于统计解的个数

printf("第%d个解:",++count);

for (int i=1;i<=St.top;i++)

printf("(%d,%d) ",i,St.col［i］);

printf("＼n");

}

bool place(StackType St,int k,int j)//测试(k,j)是否与第1~k-1个皇后有冲突

{int i=1;

if (k==1) return true;//放第一个皇后时没有冲突

while (i<=k-1)//测试与前面已放置的皇后是否有冲突

{if ((St.col［i］==j) ‖ (abs(j-St.col［i］)==abs(i-k)))

return false;//有冲突时返回false

i++;

}

return true;//没有冲突时返回true

}

void queen(int n)//求解n皇后问题

{int k;

bool find;

StackType St;//定义栈st

St.top=0;//初始化栈顶指针

St.top++; St.col［St.top］=0;//col［1］=0,表示从第1个皇后开始,初始列号为0

while (St.top!=0)//栈不空时循环

{k=St.top;//试探栈顶的第k个皇后

find=false;//尚未找到第k个皇后的位置,find设置为false

for (int j=St.col［k］+1;j<=n;j++)//为第k个皇后找一个合适的列号

if (place(St,k,j))//在第k行找到一个放皇后的位置(k,j)

{St.col［St.top］=j;//修改第k个皇后的位置(新列号)

find=true;//找到第k个皇后的位置,find设置为true

break;//找到后退出for循环






}

if (find)//在第k行找到一个放皇后的位置(k,j)

{if (k==n)//若所有皇后均放好,输出一个解

dispasolution(St);

else//还有皇后未放时将第k+1个皇后进栈

{St.top++;

St.col［St.top］=0;//新进栈的皇后从第0列开始试探

}

}

else//若第k个皇后没有合适位置,回溯

St.top--;//即将第k个皇后退栈

}

}

int main()

{int n;//n存放实际的皇后个数

printf("皇后问题(n<20) n=");

scanf("%d",&n);

if (n>20)

printf("n值太大＼n");

else

{printf(" %d皇后问题求解如下： ＼n",n);

queen(n);

}

return 1;

}






 
 exp38.cpp程序的一次执行结果如图3.20所示，表示六皇后问题有4种放置方式，如图3.21所示。



图3.20exp38.cpp程序的一次执行结果




图3.21六皇后问题的4种放置方式


实验题9： 编写停车场管理程序
目的： 深入掌握栈和队列应用的算法设计。
内容： 编写满足以下要求的停车场管理程序exp39.cpp。设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。
汽车在停车场内按车辆到达时间的先后顺序依次由南向北排列(大门在最北端，最先到达的第一辆车停放在停车场的最南端)，若停车场内已停满n辆车，则后来的汽车只能在门外的便道(即候车场)上等候，一旦有车开走，


图3.22停车场示意图

则排在便道上的第一辆车即可开入； 当停车场内的某辆车要离开时，在它之后进入的车辆必须先退出停车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入停车场，每辆停放在停车场的车在它离开停车场时必须按停留的时间长短交纳费用。整个停车场的示意图如图3.22所示。
 
 用栈模拟停车场，用队列模拟停车场外的便道，按照从键盘获取的数据序列进行模拟管理。每一组输入数据包括3个数据项： 汽车到达或者离开、汽车牌照号码以及到达或离开的时刻。对每一组输入数据进行操作后的输出信息为： 若是汽车到达，则输出汽车在停车场内或便道上的停车位置； 若是汽车离开，则输出汽车在停车场内停留的时间和应交纳的费用(在便道上停留的时间不收费)。这里栈采用顺序存储结构，队列采用环形队列。
另外还需设一个临时栈，用于临时停放为要给离开的汽车让路而从停车场退出来的汽车，也用顺序结构实现。
用户输入的命令有以下5种： 
(1) 汽车到达。
(2) 汽车离开。
(3) 输出停车场中的所有汽车牌号。
(4) 输出候车场中的所有汽车牌号。
(5) 退出系统运行。

其中，栈s和队列q分别采用顺序栈和环形队列。设计的功能算法如下。
 InitStack(SqStack *&s)： 初始化栈s。
 StackEmpty(SqStack *s)： 判断栈s是否为空栈。
 StackFull(SqStack *s)： 判断栈s是否为满栈。
 Push(SqStack *&s，ElemType e)： 元素e进栈。
 Pop(SqStack *&s，ElemType &e)： 元素e出栈。
 DispStack(SqStack *s)： 从栈顶到栈底输出元素。
 InitQueue(SqQueue *&q)： 初始化队列q。
 QueueEmpty(SqQueue *q)： 判断队列q是否为空。
 QueueFull(SqQueue *q)： 判断队列q是否为满。
 enQueue(SqQueue *&q，ElemType e)： 元素e进队。
 deQueue(SqQueue *&q，ElemType &e)： 元素e出队。
实验程序exp39.cpp的结构如图3.23所示，图中方框表示函数，方框中指出函数名； 箭头方向表示函数间的调用关系； 虚线方框表示文件的组成，即指出该虚线方框中的函数存放在哪个文件中。



图3.23exp39.cpp程序的结构


 
 实验程序exp39.cpp的代码如下(设计思路详见代码中的注释)： 



#include <stdio.h>

#include <malloc.h>

#define N 3//停车场内最多的停车数

#define M 4//候车场内最多的候车数

#define Price 2//每单位停车费用

typedef struct

{int CarNo［N］;//车牌号

int CarTime［N］;//进场时间

int top;//栈指针

} SqStack;//声明顺序栈类型

typedef struct

{int CarNo［M］;//车牌号

int front,rear;//队首和队尾指针

} SqQueue;//声明环形队列类型

//以下为栈的运算算法

void InitStack(SqStack *&s)//初始化栈

{s=(SqStack *)malloc(sizeof(SqStack));

s->top=-1;

}

bool StackEmpty(SqStack *s)//判断栈是否为空

{

return(s->top==-1);

}

bool StackFull(SqStack *s)//判断栈是否为满

{

return(s->top==N-1);

}

bool Push(SqStack *&s,int e1,int e2)//进栈

{if (s->top==N-1)

return false;

s->top++;

s->CarNo［s->top］=e1;

s->CarTime［s->top］=e2;

return true;

}

bool Pop(SqStack *&s,int &e1,int &e2)//出栈






{if (s->top==-1)

return false;

e1=s->CarNo［s->top］;

e2=s->CarTime［s->top］;

s->top--;

return true;

}

void DispStack(SqStack *s)//显示栈中元素

{for (int i=s->top;i>=0;i--)

printf("%d ",s->CarNo［i］);

printf("＼n");

}

//以下为队列的运算算法

void InitQueue(SqQueue *&q)//初始化队

{q=(SqQueue *)malloc (sizeof(SqQueue));

q->front=q->rear=0;

}

bool QueueEmpty(SqQueue *q)//判断队是否为空

{

return(q->front==q->rear);

}

bool QueueFull(SqQueue *q)//判断队是否为满

{

return ((q->rear+1)%M==q->front);

}

bool enQueue(SqQueue *&q,int e)//进队

{if ((q->rear+1)%M==q->front)//队为满的情况

return false;

q->rear=(q->rear+1)%M;

q->CarNo［q->rear］=e;

return true;

}

bool deQueue(SqQueue *&q,int &e)//出队

{if (q->front==q->rear)//队为空的情况

return false;

q->front=(q->front+1)%M;

e=q->CarNo［q->front］;

return true;

}

void DispQueue(SqQueue *q)//显示队中元素

{int i=(q->front+1)%M;

printf("%d ",q->CarNo［i］);

while ((q->rear-i+M)%M>0) 

{i=(i+1)%M;

printf("%d ",q->CarNo［i］);

} 

printf("＼n");

}

int main()

{int comm,i,j;

int no,e1,time,e2;

SqStack *St,*St1;

SqQueue *Qu;






InitStack(St);

InitStack(St1);

InitQueue(Qu);

do

{printf(">输入指令(1:到达 2:离开 3:停车场 4:候车场 0:退出):");

scanf("%d",&comm);

switch(comm)

{

case 1://汽车到达

printf("车号 到达时间:");

scanf("%d%d",&no,&time);

if (!StackFull(St))//停车场不满

{Push(St,no,time);

printf("停车场位置:%d＼n",St->top+1);

}

else//停车场已满

{if (!QueueFull(Qu))//候车场不满

{enQueue(Qu,no);

printf("候车场位置:%d＼n",Qu->rear);

}

else printf("候车场已满,不能停车＼n");

}

break;

case 2://汽车离开

printf("车号 离开时间:");

scanf("%d%d",&no,&time);

for (i=0;i<=St->top && St->CarNo［i］!=no;i++);

if (i>St->top)

printf("未找到该编号的汽车＼n");

else

{for (j=i;j<=St->top;j++)

{Pop(St,e1,e2);

Push(St1,e1,e2);//倒车到临时栈St1中

}

Pop(St,e1,e2);//该汽车离开

printf("%d汽车停车费用:%d＼n",no,(time-e2)*Price);

while (!StackEmpty(St1))//将临时栈St1中的汽车重新回到St中

{Pop(St1,e1,e2);

Push(St,e1,e2);

}

if (!QueueEmpty(Qu))//队不为空时将队头进栈St

{deQueue(Qu,e1);

Push(St,e1,time);//以当前时间开始计费

}

}

break;

case 3://显示停车场情况

if (!StackEmpty(St))

{printf("停车场中的车辆:");   //输出停车场中的车辆

DispStack(St);

}

else printf("停车场中无车辆＼n");

break;






case 4://显示候车场情况

if (!QueueEmpty(Qu))

{printf("候车场中的车辆:");   //输出候车场中的车辆

DispQueue(Qu);

}

else printf("候车场中无车辆＼n");

break;

case 0://结束

if (!StackEmpty(St))

{printf("停车场中的车辆:");   //输出停车场中的车辆

DispStack(St);

}

if (!QueueEmpty(Qu))

{printf("候车场中的车辆:");   //输出候车场中的车辆

DispQueue(Qu);

}

break;

default://其他情况

printf("输入的命令错误＼n");

break;

} 

} while(comm!=0);

return 1;

}







 
 exp39.cpp程序的一次执行结果如图3.24所示。首先有4辆车依次进入，由于停车场内最多只能停放3辆车，所以有一辆车停放在候车场中。然后101车离开，共停车5小时，收费10元，候车场中的车辆进入停车场，此时看到停车场中有3辆车。


图3.24exp39.cpp程序的一次执行结果