实验三 栈和队列
3.1实验目的：
（1） 熟悉栈的特点（先进后出）及栈的基本操作，如入栈、出栈等，掌握栈的基本操作
在栈的顺序存储结构和链式存储结构上的实现；
（2） 熟悉队列的特点（先进先出）及队列的基本操作，如入队、出队等，掌握队列的基
本操作在队列的顺序存储结构和链式存储结构上的实现。
3.2 实验要求：
（1） 复习课本中有关栈和队列的知识；
（2） 用C语言完成算法和程序设计并上机调试通过；
（3） 撰写实验报告，给出算法思路或流程图和具体实现（源程序）、算法分析结果（包括
时间复杂度、空间复杂度以及算法优化设想）、输入数据及程序运行结果（必要时给出多种可能的输入数据和运行结果）。
3.3 基础实验
[实验1] 栈的顺序表示和实现
实验内容与要求:
编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：
（1）初始化顺序栈
（2）插入元素
（3）删除栈顶元素
（4）取栈顶元素
（5）遍历顺序栈
（6）置空顺序栈
分析:
栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。
对于顺序栈，入栈时，首先判断栈是否为满，栈满的条件为：p->top= =MAXNUM-1，栈满时，不能入栈; 否则出现空间溢出，引起错误，这种现象称为上溢。
出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产生错误。通常栈空作为一种控制转移的条件。
注意：
（1）顺序栈中元素用向量存放
（2）栈底位置是固定不变的，可设置在向量两端的任意一个端点
（3）栈顶位置是随着进栈和退栈操作而变化的，用一个整型量top（通常称top为栈顶指针）来指示当前栈顶位置
参考程序:
#include<stdio.h>
#include<stdlib.h>
#define MAXNUM 20
1
#define ElemType int
/*定义顺序栈的存储结构*/
typedef struct
{ ElemType stack[MAXNUM];
int top;
}SqStack;
/*初始化顺序栈*/
void InitStack(SqStack *p)
{ if(!p)
printf("Eorror");
p->top=-1;
}
/*入栈*/
void Push(SqStack *p,ElemType x)
{ if(p->top<MAXNUM-1)
{ p->top=p->top+1;
p->stack[p->top]=x;
}
else
printf("Overflow!\n");
}
/*出栈*/
ElemType Pop(SqStack *p)
{ ElemType x;
if(p->top!=0)
{ x=p->stack[p->top];
printf("以前的栈顶数据元素%d已经被删除！\n",p->stack[p->top]); p->top=p->top-1;
return(x);
}
else
{ printf("Underflow!\n");
return(0);
}
}
/*获取栈顶元素*/
ElemType GetTop(SqStack *p)
{ ElemType x;
if(p->top!=0)
{ x=p->stack[p->top];
return(x);
}
else
{ printf("Underflow!\n");
2
return(0);
}
}
/*遍历顺序栈*/
void OutStack(SqStack *p)
{ int i;
printf("\n");
if(p->top<0)
printf("这是一个空栈！");
printf("\n");
for(i=p->top;i>=0;i--)
printf("第%d个数据元素是：%6d\n",i,p->stack[i]); }
/*置空顺序栈*/
void setEmpty(SqStack *p)
{
p->top= -1;
}
/*主函数*/
main()
{ SqStack *q;
int y,cord;ElemType a;
do{
printf("\n");
printf("第一次使用必须初始化！\n");
printf("\n");
printf("\n 主菜单 \n"); printf("\n 1 初始化顺序栈 \n"); printf("\n 2 插入一个元素 \n"); printf("\n 3 删除栈顶元素 \n"); printf("\n 4 取栈顶元素 \n"); printf("\n 5 置空顺序栈 \n"); printf("\n 6 结束程序运行 \n"); printf("\n--------------------------------\n");
printf("请输入您的选择( 1, 2, 3, 4, 5,6)");
scanf("%d",&cord);
printf("\n");
switch(cord)
{ case 1:
{ q=(SqStack*)malloc(sizeof(SqStack)); InitStack(q);
OutStack(q);
}break;
case 2:
3
{ printf("请输入要插入的数据元素：a=");
scanf("%d",&a);
Push(q,a);
OutStack(q);
}break;
case 3:
{ Pop(q);
OutStack(q);
}break;
case 4:
{ y=GetTop(q);
printf("\n栈顶元素为：%d\n",y);
OutStack(q);
}break;
case 5:
{ setEmpty(q);
printf("\n顺序栈被置空！\n");
OutStack(q);
}break;
case 6:
exit(0);
}
}while (cord<=6);
}
[实验2] 栈的链式表示和实现
实验内容与要求:
编写一个程序实现链栈的各种基本运算，并在此基础上设计一个主程序，完成如下功能：
（1）初始化链栈
（2）链栈置空
（3）入栈
（4）出栈
（5）取栈顶元素
（6）遍历链栈
分析:
链栈是没有附加头结点的运算受限的单链表。栈顶指针就是链表的头指针。
注意：
（1）LinkStack结构类型的定义可以方便地在函数体中修改top指针本身
（2）若要记录栈中元素个数，可将元素个数属性放在LinkStack类型中定义。
（3）链栈中的结点是动态分配的，所以可以不考虑上溢。
4
参考程序:
#include "stdio.h"
#include "malloc.h"
#include "stdlib.h"
typedef int Elemtype;
typedef struct stacknode {
Elemtype data;
stacknode * next;
}StackNode;
typedef struct {
stacknode * top; //栈顶指针
}LinkStack;
/*初始化链栈*/
void InitStack(LinkStack * s)
{ s->top=NULL;
printf("\n已经初始化链栈！\n");
}
/*链栈置空*/
void setEmpty(LinkStack * s)
{ s->top=NULL;
printf("\n链栈被置空！\n");
}
/*入栈*/
void pushLstack(LinkStack * s, Elemtype x)
{ StackNode * p;
p=(StackNode *)malloc(sizeof(StackNode)); //建立一个节点。 p->data=x;
p->next=s->top; //由于是在栈顶pushLstack，所以要指向栈顶。 s->top=p; //插入
}
/*出栈*/
Elemtype popLstack(LinkStack * s)
{ Elemtype x;
StackNode * p;
p=s->top; //指向栈顶
if (s->top ==0)
{ printf("\n栈空，不能出栈！\n");
exit(-1);
}
x=p->data;
s->top=p->next; //当前的栈顶指向原栈的next
free(p); //释放
return x;
}
5
/*取栈顶元素*/
Elemtype StackTop(LinkStack *s)
{ if (s->top ==0)
{ printf("\n链栈空\n");
exit(-1);
}
return s->top->data;
}
/*遍历链栈*/
void Disp(LinkStack * s)
{ printf("\n链栈中的数据为：\n");
printf("=======================================\n"); StackNode * p;
p=s->top;
while (p!=NULL)
{ printf("%d\n",p->data);
p=p->next;
}
printf("=======================================\n"); }
void main()
{ printf("================= 链栈操作=================\n\n"); int i,m,n,a;
LinkStack * s;
s=(LinkStack *)malloc(sizeof(LinkStack));
int cord;
do{ printf("\n");
printf("第一次使用必须初始化！\n");
printf("\n");
printf("\n 主菜单 \n");
printf("\n 1 初始化链栈 \n");
printf("\n 2 入栈 \n");
printf("\n 3 出栈 \n");
printf("\n 4 取栈顶元素 \n");
printf("\n 5 置空链栈 \n");
printf("\n 6 结束程序运行 \n");
printf("\n--------------------------------\n");
printf("请输入您的选择( 1, 2, 3, 4, 5,6)");
scanf("%d",&cord);
printf("\n");
switch(cord)
{ case 1:
{ InitStack(s);
Disp(s);
6
}break;
case 2:
{printf("输入将要压入链栈的数据的个数：n=");
scanf("%d",&n);
printf("依次将%d个数据压入链栈：\n",n);
for(i=1;i<=n;i++)
{scanf("%d",&a);
pushLstack(s,a);
}
Disp(s);
}break;
case 3:
{ printf("\n出栈操作开始!\n");
printf("输入将要出栈的数据个数：m=");
scanf("%d",&m);
for(i=1;i<=m;i++)
{printf("\n第%d次出栈的数据是：%d",i,popLstack(s));}
Disp(s);
}break;
case 4:
{ printf("\n\n链栈的栈顶元素为：%d\n",StackTop(s));
printf("\n");
}break;
case 5:
{ setEmpty(s);
Disp(s);
}break;
case 6:
exit(0);
}
}while (cord<=6);
}
[实验3] 队列的顺序表示和实现
实验内容与要求
编写一个程序实现顺序队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能：
（1）初始化队列
（2）建立顺序队列
（3）入队
（4）出队
（5）判断队列是否为空
（6）取队头元素
7
（7）遍历队列
分析:
队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。
入队时，将新元素插入rear所指的位置，然后将rear加1。出队时，删去front所指的元素，然后将front加1并返回被删元素。
顺序队列中的溢出现象：
（1） "下溢"现象。当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。
（2） "真上溢"现象。当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。
（3） "假上溢"现象。由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为"假上溢"现象。
注意：
（1）当头尾指针相等时，队列为空。
（2）在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。
参考程序:
#include <stdio.h>
#include <malloc.h>
#define MAXNUM 100
#define Elemtype int
#define TRUE 1
#define FALSE 0
typedef struct
{ Elemtype queue[MAXNUM];
int front;
int rear;
}sqqueue;
/*队列初始化*/
int initQueue(sqqueue *q)
{ if(!q) return FALSE;
q->front=-1;
q->rear=-1;
return TRUE;
}
/*入队*/
int append(sqqueue *q, Elemtype x)
{ if(q->rear>=MAXNUM-1) return FALSE;
q->rear++;
q->queue[q->rear]=x;
return TRUE;
}
8
/*出队*/
Elemtype Delete(sqqueue *q)
{ Elemtype x;
if (q->front==q->rear) return 0;
x=q->queue[++q->front];
return x;
}
/*判断队列是否为空*/
int Empty(sqqueue *q)
{ if (q->front==q->rear) return TRUE;
return FALSE;
}
/*取队头元素*/
int gethead(sqqueue *q)
{ if (q->front==q->rear) return 0;
return(q->queue[q->front+1]);
}
/*遍历队列*/
void display(sqqueue *q)
{ int s;
s=q->front;
if (q->front==q->rear)
printf("队列空!\n");
else
{printf("\n顺序队列依次为：");
while(s<q->rear)
{s=s+1;
printf("%d<-", q->queue[s]);
}
printf("\n");
printf("顺序队列的队尾元素所在位置:rear=%d\n",q->rear); printf("顺序队列的队头元素所在位置:front=%d\n",q->front); }
}
/*建立顺序队列*/
void Setsqqueue(sqqueue *q)
{ int n,i,m;
printf("\n请输入将要入顺序队列的长度:");
scanf("%d",&n);
printf("\n请依次输入入顺序队列的元素值:\n");
for (i=0;i<n;i++)
{ scanf("%d",&m);
append(q,m);}
}
9
main()
{ sqqueue *head;
int x,y,z,select;
head=(sqqueue*)malloc(sizeof(sqqueue));
do{printf("\n第一次使用请初始化！\n");
printf("\n请选择操作(1--7):\n");
printf("===================================\n"); printf("1 初始化\n");
printf("2 建立顺序队列\n");
printf("3 入队\n");
printf("4 出队 \n");
printf("5 判断队列是否为空\n");
printf("6 取队头元素 \n");
printf("7 遍历队列\n");
printf("===================================\n"); scanf("%d",&select);
switch(select)
{case 1:
{ initQueue(head);
printf("已经初始化顺序队列！\n");
break;
}
case 2:
{ Setsqqueue(head);
printf("\n已经建立队列！\n");
display(head);
break;
}
case 3:
{ printf("请输入队的值:\n ");
scanf("%d",&x);
append(head,x);
display(head);
break;
}
case 4:
{ z=Delete(head);
printf("\n队头元素%d已经出队！\n",z); display(head);
break;
}
case 5:
{ if(Empty(head))
printf("队列空\n");
10
else
printf("队列非空\n");
break;
}
case 6:
{ y=gethead(head);
printf("队头元素为:%d\n",y);
break;
}
case 7:
{ display(head);
break;
}
}
}while(select<=7);
}
[实验4[ 队列的链式表示和实现
实验内容与要求:
编写一个程序实现链队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能：
（1）初始化并建立链队列
（2）入链队列
（3）出链队列
（4）遍历链队列
分析:
队列的链式存储结构简称为链队列。它是限制仅在表头删除和表尾插入的单链表。 注意：
（1）和链栈类似，无须考虑判队满的运算及上溢。
（2）在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。
（3）和单链表类似，为了简化边界条件的处理，在队头结点前可附加一个头结点。 参考程序:
#include<stdio.h>
#include<stdlib.h>
#define ElemType int
typedef struct Qnode
{ ElemType data;
struct Qnode *next;
}Qnodetype;
typedef struct
{ Qnodetype *front;
11
Qnodetype *rear;
}Lqueue;
/*初始化并建立链队列*/
void creat(Lqueue *q)
{ Qnodetype *h;
int i,n,x;
printf("输入将建立链队列元素的个数：n= "); scanf("%d",&n);
h=(Qnodetype*)malloc(sizeof(Qnodetype)); h->next=NULL;
q->front=h;
q->rear=h;
for(i=1;i<=n;i++)
{ printf("链队列第%d个元素的值为：",i); scanf("%d",&x);
Lappend(q,x);
}
}
/*入链队列*/
void Lappend(Lqueue *q,int x)
{ Qnodetype *s;
s=(Qnodetype*)malloc(sizeof(Qnodetype)); s->data=x;
s->next=NULL;
q->rear->next=s;
q->rear=s;
}
/*出链队列*/
ElemType Ldelete(Lqueue *q)
{ Qnodetype *p;
ElemType x;
if(q->front==q->rear)
{ printf("队列为空!\n");
x=0;
}
else
{ p=q->front->next;
q->front->next=p->next;
if(p->next==NULL)
q->rear=q->front;
x=p->data;
free(p);
}
return(x);
12
}
/*遍历链队列*/
void display(Lqueue *q)
{ Qnodetype *p;
p=q->front->next; /*指向第一个数据元素节点 */
printf("\n链队列元素依次为：");
while(p!=NULL)
{ printf("%d-->",p->data);
p=p->next;
}
printf("\n\n遍历链队列结束！ \n");
}
main()
{ Lqueue *p;
int x,cord;
printf("\n*****第一次操作请选择初始化并建立链队列！*****\n "); do
{ printf("\n 链队列的基本操作\n ");
printf("=========================================\n"); printf(" 主菜单 \n");
printf("=========================================\n"); printf(" 1 初始化并建立链队列 \n");
printf(" 2 入链队列 \n");
printf(" 3 出链队列 \n");
printf(" 4 遍历链队列 \n");
printf(" 5 结束程序运行 \n");
printf("==========================================\n"); scanf("%d",&cord);
switch(cord)
{ case 1:
{ p=(Lqueue *)malloc(sizeof(Lqueue));
creat(p);
display(p);
}break;
case 2:
{ printf("请输入队列元素的值：x=");
scanf("%d",&x);
Lappend(p,x);
display(p);
}break;
case 3:
{ printf("出链队列元素：x=%d\n",Ldelete(p)); display(p);
}break;
13
}
case 4: {display(p);}break; case 5: {exit (0);} } }while (cord<=5);
3.4 提高实验
[实验1] 迷宫的求解
实验内容与要求:
迷宫只有两个门，一个叫做入口，另一个叫做出口。把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍，在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。求解迷宫问题，即找出从入口到出口的路径。
分析:
迷宫问题是栈应用的一个典型例子。求解过程可采用回溯法。回溯法是一种不断试探且及时纠正错误的搜索方法。从入口出发，按某一方向向前探索，若能走通（未走过的），即某处可以到达，则到达新点，否则试探下一方向 ; 若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到所有可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点。
在求解过程中，为了保证在到达某一点后不能向前继续行走（无路）时，能正确返回前一点以便继续从下一个方向向前试探，则需要用一个栈保存所能够到达的每一点的下标及从该点前进的方向，栈中保存的就是一条迷宫的通路。
为了确保程序能够终止，调整时，必须保证曾被放弃过的填数序列不被再次试验，即要求按某种有序模型生成填数序列。给解的候选者设定一个被检验的顺序，按这个顺序逐一生成候选者并检验。
参考程序::
#include<stdio.h>
#include<stdlib.h>
#define n1 10
#define n2 10
typedef struct node
{
int x; //存x坐标
int y; //存Y坐标
int c; //存该点可能的下点所在的方向,1表示向右,2向上,3向左,4向右
}linkstack;
linkstack top[100];
14
//迷宫矩阵
int maze[n1][n2]={1,1,1,1,1,1,1,1,1,1,
0,0,0,1,0,0,0,1,0,1,
1,1,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,0,
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,};
int i,j,k,m=0;
main()
{//初始化top[],置所有方向数为左
for(i=0;i<n1*n2;i++)
{top[i].c=1;}
printf("the maze is:\n");
//打印原始迷宫矩阵
for(i=0;i<n1;i++)
{for(j=0;j<n2;j++)
printf(maze[i][j]?"* ":" ");
printf("\n"); }
i=0;top[i].x=1;top[i].y=0;
maze[1][0]=2;
/*回溯算法*/
do{
if(top[i].c<5) //还可以向前试探
{if(top[i].x==5 && top[i].y==9) //已找到一个组合 { //打印路径
printf("The way %d is:\n",m++);
for(j=0;j<=i;j++)
{printf("(%d,%d)-->",top[j].x,top[j].y);} printf("\n");
//打印选出路径的迷宫
for(j=0;j<n1;j++)
{for(k=0;k<n2;k++)
{if(maze[j][k]==0) printf(" ");
else if(maze[j][k]==2) printf("O ");
else printf("* ");}
printf("\n"); }
maze[top[i].x][top[i].y]=0;
top[i].c = 1;
i--;
top[i].c += 1;
15
continue;}
switch (top[i].c) //向前试探 {
case 1:
{ if(maze[top[i].x][top[i].y+1]==0) {i++;
top[i].x=top[i-1].x;
top[i].y=top[i-1].y+1;
maze[top[i].x][top[i].y]=2;} else
{top[i].c += 1;}
break;}
case 2:
{if(maze[top[i].x-1][top[i].y]==0) {i++;
top[i].x=top[i-1].x-1; top[i].y=top[i-1].y;
maze[top[i].x][top[i].y]=2;} else
{top[i].c += 1;}
break;}
case 3:
{if(maze[top[i].x][top[i].y-1]==0) {i++;
top[i].x=top[i-1].x;
top[i].y=top[i-1].y-1;
maze[top[i].x][top[i].y]=2;} else
{top[i].c += 1;}
break;}
case 4:
{if(maze[top[i].x+1][top[i].y]==0) {i++;
top[i].x=top[i-1].x+1; top[i].y=top[i-1].y;
maze[top[i].x][top[i].y]=2;} else
{ top[i].c += 1;}
break;}
}
}
else //回溯
{if(i==0) return; //已找完所有解 maze[top[i].x][top[i].y]=0;
16
top[i].c = 1;
i--;
top[i].c += 1;}
}while(1);
}
[实验2] 停车场管理
实验内容与要求:
设停车场内只有一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。 试为停车场编制按上述要求进行管理的模拟程序。
分析:
综合利用栈和队列模拟停车场管理，学习利用栈和队列解决实际问题。
以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表实现。
需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。
设n=2,输入数据为：（?A?，1，5），（?A?，2，10），（?D?，1，15），（?A?，3， 20）， （?A?，4，25），（?A?，5，30），（?D?，2，35），（?D?，4，40），（?E?，0，0）。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，其中，?A?表示到达；?D?表示离去，?E?表示输入结束。
参考程序:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 2 /*车库容量*/
#define price 0.05 /*每车每分钟费用*/
typedef struct time{
int hour;
int min;
}Time; /*时间结点*/
typedef struct node{
char num[10];
17
Time reach;
Time leave;
}CarNode; /*车辆信息结点*/
typedef struct NODE{
CarNode *stack[MAX+1];
int top;
}SeqStackCar; /*模拟车站*/
typedef struct car{
CarNode *data;
struct car *next;
}QueueNode;
typedef struct Node{
QueueNode *head;
QueueNode *rear;
}LinkQueueCar; /*模拟通道*/
void InitStack(SeqStackCar *); /*初始化栈*/
int InitQueue(LinkQueueCar *); /*初始化便道*/
int Arrival(SeqStackCar *,LinkQueueCar *); /*车辆到达*/
void Leave(SeqStackCar *,SeqStackCar *,LinkQueueCar *); /*车辆离开*/ void List(SeqStackCar,LinkQueueCar); /*显示存车信息*/
void main()
{SeqStackCar Enter,Temp;
LinkQueueCar Wait;
int ch;
InitStack(&Enter); /*初始化车站*/
InitStack(&Temp); /*初始化让路的临时栈*/
InitQueue(&Wait); /*初始化通道*/
while(1)
{ printf("\n1. 车辆到达");
printf(" 2. 车辆离开");
printf(" 3. 列表显示");
printf(" 4. 退出系统\n");
while(1)
{scanf("%d",&ch);
if(ch>=1&&ch<=4)break;
else printf("\n请选择： 1|2|3|4.");
}
switch(ch)
{ case 1:Arrival(&Enter,&Wait);break; /*车辆到达*/
case 2:Leave(&Enter,&Temp,&Wait);break; /*车辆离开*/
case 3:List(Enter,Wait);break; /*列表打印信息*/
case 4:exit(0); /*退出主程序*/
default: break;
}}}
18
void InitStack(SeqStackCar *s) /*初始化栈*/
{ int i;
s->top=0;
for(i=0;i<=MAX;i++)
s->stack[s->top]=NULL;}
int InitQueue(LinkQueueCar *Q) /*初始化便道*/
{Q->head=(QueueNode *)malloc(sizeof(QueueNode)); if(Q->head!=NULL)
{Q->head->next=NULL;
Q->rear=Q->head;
return(1);}
else return(-1);}
void PRINT(CarNode *p,int room) /*打印出站车的信息*/ {int A1,A2,B1,B2;
printf("\n请输入离开的时间:/**:**/");
scanf("%d:%d",&(p->leave.hour),&(p->leave.min));
printf("\n离开车辆的车牌号为:");
puts(p->num);
printf("\n其到达时间为: %d:%d",p->reach.hour,p->reach.min); printf("离开时间为: %d:%d",p->leave.hour,p->leave.min); A1=p->reach.hour;
A2=p->reach.min;
B1=p->leave.hour;
B2=p->leave.min;
printf("\n应交费用为: %2.1f元",((B1-A1)*60+(B2-A2))*price); free(p);
}
int Arrival(SeqStackCar *Enter,LinkQueueCar *W) /*车辆到达*/ { CarNode *p;
QueueNode *t;
p=(CarNode *)malloc(sizeof(CarNode));
flushall();
printf("\n请输入车牌号(例:陕A1234):");
gets(p->num);
if(Enter->top<MAX) /*车场未满，车进车场*/
{Enter->top++;
printf("\n车辆在车场第%d位置.",Enter->top);
printf("\n请输入到达时间:/**:**/");
scanf("%d:%d",&(p->reach.hour),&(p->reach.min));
Enter->stack[Enter->top]=p;
return(1);}
else /*车场已满，车进便道*/
{ printf("\n该车须在便道等待!");
t=(QueueNode *)malloc(sizeof(QueueNode));
19
t->data=p;
t->next=NULL;
W->rear->next=t;
W->rear=t;
return(1); }}
void Leave(SeqStackCar *Enter,SeqStackCar *Temp,LinkQueueCar *W) { /*车辆离开*/
int i, room;
CarNode *p,*t;
QueueNode *q;
/*判断车场内是否有车*/
if(Enter->top>0) /*有车*/
{ while(1) /*输入离开车辆的信息*/
{printf("\n请输入车在车场的位置/1--%d/：",Enter->top);
scanf("%d",&room);
if(room>=1&&room<=Enter->top) break;}
while(Enter->top>room) /*车辆离开*/
{Temp->top++;
Temp->stack[Temp->top]=Enter->stack[Enter->top];
Enter->stack[Enter->top]=NULL;
Enter->top--;
}
p=Enter->stack[Enter->top];
Enter->stack[Enter->top]=NULL;
Enter->top--;
while(Temp->top>=1)
{Enter->top++;
Enter->stack[Enter->top]=Temp->stack[Temp->top];
Temp->stack[Temp->top]=NULL;
Temp->top--;}
PRINT(p,room);
/*判断通道上是否有车及车站是否已满*/
if((W->head!=W->rear)&&Enter->top<MAX) /*便道的车辆进入车场*/ { q=W->head->next;
t=q->data;
Enter->top++;
printf("\n便道的%s号车进入车场第%d位置.",t->num,Enter->top); printf("\n请输入现在的时间/**:**/:");
scanf("%d:%d",&(t->reach.hour),&(t->reach.min));
W->head->next=q->next;
if(q==W->rear) W->rear=W->head;
Enter->stack[Enter->top]=t;
free(q);}
else printf("\n便道里没有车.\n");}
20
else printf("\n车场里没有车."); /*没车*/ }
void List1(SeqStackCar *S) /*列表显示车场信息*/
{int i;
if(S->top>0) /*判断车站内是否有车*/
{printf("\n车场:");
printf("\n 位置 到达时间 车牌号\n");
for(i=1;i<=S->top;i++)
{printf(" %d ",i);
printf("%d:%d ",S->stack[i]->reach.hour,S->stack[i]->reach.min);
puts(S->stack[i]->num);}}
else printf("\n车场里没有车");}
void List2(LinkQueueCar *W) /*列表显示便道信息*/
{ QueueNode *p;
p=W->head->next;
if(W->head!=W->rear) /*判断通道上是否有车*/
{printf("\n等待车辆的号码为:");
while(p!=NULL)
{puts(p->data->num);
p=p->next;}}
else printf("\n便道里没有车."); }
void List(SeqStackCar S,LinkQueueCar W)
{int flag,tag;
flag=1;
while(flag)
{printf("\n请选择 1|2|3:");
printf("\n1.车场\n2.便道\n3.返回\n");
while(1)
{ scanf("%d",&tag);
if(tag>=1||tag<=3) break;
else printf("\n请选择 1|2|3:");
}switch(tag)
{case 1:List1(&S);break; /*列表显示车场信息*/
case 2:List2(&W);break; /*列表显示便道信息*/
case 3:flag=0;break;
default: break; }}}
3.5思考题：
（1）读栈顶元素的算法与退栈顶元素的算法有何区别？
（2）如果一个程序中要用到两个栈，为了不发生上溢错误，就必须给每个栈预先分配一个足够大的存储空间。若每个栈都预分配过大的存储空间，势必会造成系统空间紧张。如何解决这个问题？
（3）栈的两种存储结构在判别栈空与栈满时，所依据的条件有何不同？
（4）在程序中同时使用两个以上的栈时，使用顺序栈共享邻接空间则很难实现，能否通过链栈来方便地实现？如何实现？
21
（5）简述栈和队列的共同点和不同点。它们为什么属于线性表？
（6）在顺序队列中，当队尾指针已经指向了队列的最后一个位置时，但事实上队列中可能还有空位置。此时若有元素入列，就会发生“假溢出”。如何解决这个问题？
（7）链栈只有一个top指针，对于链队列，为什么要设计一个头指针和一个尾指针？
（8）一个程序中如果要用到两个栈时，可通过两个栈共享一维数组来实现。即双向栈共享邻接空间。如果一个程序中要用到两个队列，能否实现？如何实现？
假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意：不设头指针），试编写相应的队列初始化、入队列和出队列算法。
(9) 设计算法实现括弧配对的检查。
(10) 设计算法求解迷宫的一条最短路径。
(11) 求解“背包问题”。 “背包问题”的基本描述是：有一个背包，能盛放的物品总重量为 S，设有 N 件物品，其重量分别为w1，w2，...，wn，希望从N件物品中选择若干件物品，所选物品的重量之和恰能放入该背包，即所选物品的重量之和等于S 。
22