栈的操作(实验报告).doc

实验三 栈和队列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#include#define MAXNUM 20#define ElemType int/*定义顺序栈的存储结构*/typedef struct ElemType stackMAXNUM;int top;SqStack;/*初始化顺序栈*/void InitStack(SqStack *p)if(!p)printf(Eorror);p-top=-1;/*入栈*/void Push(SqStack *p,ElemType x)if(p-toptop=p-top+1;p-stackp-top=x;elseprintf(Overflow!n);/*出栈*/ElemType Pop(SqStack *p)ElemType x;if(p-top!=0)x=p-stackp-top;printf(以前的栈顶数据元素%d已经被删除！n,p-stackp-top);p-top=p-top-1;return(x);elseprintf(Underflow!n);return(0);/*获取栈顶元素*/ElemType GetTop(SqStack *p)ElemType x;if(p-top!=0)x=p-stackp-top;return(x);elseprintf(Underflow!n);return(0);/*遍历顺序栈*/void OutStack(SqStack *p)int i;printf(n);if(p-toptop;i=0;i-)printf(第%d个数据元素是：%6dn,i,p-stacki);/*置空顺序栈*/void setEmpty(SqStack *p)p-top= -1;/*主函数*/main() SqStack *q;int y,cord;ElemType a;doprintf(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: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栈顶元素为：%dn,y);OutStack(q);break;case 5:setEmpty(q);printf(n顺序栈被置空！n);OutStack(q);break;case 6:exit(0);while (cordtop=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; /当前的栈顶指向原栈的nextfree(p); /释放return x;/*取栈顶元素*/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(%dn,p-data);p=p-next;printf(=n);void main()printf(= 链栈操作=nn);int i,m,n,a;LinkStack * s;s=(LinkStack *)malloc(sizeof(LinkStack);int cord;doprintf(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);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(nn链栈的栈顶元素为：%dn,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）遍历队列分析:队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。入队时，将新元素插入rear所指的位置，然后将rear加1。出队时，删去front所指的元素，然后将front加1并返回被删元素。顺序队列中的溢出现象：（1） 下溢现象。当队列为空时，做出队运算产生的溢出现象。“下溢”是正常现象，常用作程序控制转移的条件。（2） 真上溢现象。当队列满时，做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态，应设法避免。（3） 假上溢现象。由于入队和出队操作中，头尾指针只增加不减小，致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时，也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为假上溢现象。注意：（1）当头尾指针相等时，队列为空。（2）在非空队列里，队头指针始终指向队头元素，尾指针始终指向队尾元素的下一位置。参考程序:#include #include #define MAXNUM 100#define Elemtype int#define TRUE 1#define FALSE 0typedef structElemtype queueMAXNUM; 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-queueq-rear=x; return TRUE;/*出队*/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-queueq-front+1); /*遍历队列*/void display(sqqueue *q)int s; s=q-front; if (q-front=q-rear)printf(队列空!n); else printf(n顺序队列依次为：);while(srear) s=s+1;printf(%dqueues);printf(n); printf(顺序队列的队尾元素所在位置:rear=%dn,q-rear); printf(顺序队列的队头元素所在位置:front=%dn,q-front);/*建立顺序队列*/void Setsqqueue(sqqueue *q)int n,i,m;printf(n请输入将要入顺序队列的长度:); scanf(%d,&n); printf(n请依次输入入顺序队列的元素值:n);for (i=0;in;i+) scanf(%d,&m); append(q,m);main() sqqueue *head; int x,y,z,select; head=(sqqueue*)malloc(sizeof(sqqueue); doprintf(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); else printf(队列非空n); break; case 6: y=gethead(head); printf(队头元素为:%dn,y); break; case 7: display(head); break; while(select=7);实验4 队列的链式表示和实现实验内容与要求:编写一个程序实现链队列的各种基本运算，并在此基础上设计一个主程序，完成如下功能：（1）初始化并建立链队列（2）入链队列（3）出链队列（4）遍历链队列分析:队列的链式存储结构简称为链队列。它是限制仅在表头删除和表尾插入的单链表。注意：（1）和链栈类似，无须考虑判队满的运算及上溢。（2）在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。（3）和单链表类似，为了简化边界条件的处理，在队头结点前可附加一个头结点。参考程序:#include#include#define ElemType inttypedef struct QnodeElemType data;struct Qnode *next;Qnodetype;typedef structQnodetype *front;Qnodetype *rear;Lqueue;/*入链队列*/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;/*初始化并建立链队列*/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;ifront=q-rear)printf(队列为空!n);x=0;elsep=q-front-next;q-front-next=p-next;if(p-next=NULL)q-rear=q-front;x=p-data;free(p);return(x);/*遍历链队列*/void display(Lqueue *q)Qnodetype *p; p=q-front-next; /*指向第一个数据元素节点 */printf(n链队列元素依次为：);while(p!=NULL)printf(%d-,p-data);p=p-next;printf(nn遍历链队列结束！ 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=%dn,Ldelete(p);display(p);break;case 4:display(p);break;case 5:exit (0);while (cord=5);3.4 提高实验实验1 迷宫的求解实验内容与要求:迷宫只有两个门，一个叫做入口，另一个叫做出口。把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍，在迷宫的唯一出口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以到达出口。求解迷宫问题，即找出从入口到出口的路径。分析:迷宫问题是栈应用的一个典型例子。求解过程可采用回溯法。回溯法是一种不断试探且及时纠正错误的搜索方法。从入口出发，按某一方向向前探索，若能走通（未走过的），即某处可以到达，则到达新点，否则试探下一方向 ; 若所有的方向均没有通路，则沿原路返回前一点，换下一个方向再继续试探，直到所有可能的通路都探索到，或找到一条通路，或无路可走又返回到入口点。在求解过程中，为了保证在到达某一点后不能向前继续行走（无路）时，能正确返回前一点以便继续从下一个方向向前试探，则需要用一个栈保存所能够到达的每一点的下标及从该点前进的方向，栈中保存的就是一条迷宫的通路。为了确保程序能够终止，调整时，必须保证曾被放弃过的填数序列不被再次试验，即要求按某种有序模型生成填数序列。给解的候选者设定一个被检验的顺序，按这个顺序逐一生成候选者并检验。参考程序:#include #include #define n1 10 #define n2 10 typedef struct node int x; /存x坐标int y; /存Y坐标int c; /存该点可能的下点所在的方向,1表示向右,2向上,3向左,4向右linkstack; linkstack top100; /迷宫矩阵int mazen1n2=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;in1*n2;i+) topi.c=1;printf(the maze is:n);/打印原始迷宫矩阵 for(i=0;in1;i+) for(j=0;jn2;j+) printf(mazeij?* : ); printf(n); i=0;topi.x=1;topi.y=0;maze10=2;/*回溯算法*/doif(topi.c5) /还可以向前试探if(topi.x=5 & topi.y=9) /已找到一个组合/打印路径printf(The way %d is:n,m+);for(j=0;j,topj.x,topj.y);printf(n);/打印选出路径的迷宫for(j=0;jn1;j+) for(k=0;kn2;k+) if(mazejk=0)printf( );else if(mazejk=2) printf(O );else printf(* );printf(n); mazetopi.xtopi.y=0;topi.c = 1;i-;topi.c += 1;continue;switch (topi.c) /向前试探case 1:if(mazetopi.xtopi.y+1=0)i+;topi.x=topi-1.x;topi.y=topi-1.y+1;mazetopi.xtopi.y=2;elsetopi.c += 1;break;case 2:if(mazetopi.x-1topi.y=0)i+;topi.x=topi-1.x-1;topi.y=topi-1.y;mazetopi.xtopi.y=2;elsetopi.c += 1;break;case 3:if(mazetopi.xtopi.y-1=0)i+;topi.x=topi-1.x;topi.y=topi-1.y-1;mazetopi.xtopi.y=2;elsetopi.c += 1;break;case 4:if(mazetopi.x+1topi.y=0)i+;topi.x=topi-1.x+1;topi.y=topi-1.y;mazetopi.xtopi.y=2;elsetopi.c += 1;break;else /回溯if(i=0) return; /已找完所有解mazetopi.xtopi.y=0;topi.c = 1;i-;topi.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#include#include#define MAX 2 /*车库容量*/#define price 0.05 /*每车每分钟费用*/typedef struct timeint hour;int min;Time; /*时间结点*/typedef struct nodechar num10;Time reach;Time leave;CarNode; /*车辆信息结点*/typedef struct NODECarNode *stackMAX+1;int top;SeqStackCar; /*模拟车站*/typedef struct carCarNode *data;struct car *next;QueueNode;typedef struct NodeQueueNode *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&chtop=0;for(i=0;istacks-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-toptop+;printf(n车辆在车场第%d位置.,Enter-top);printf(n请输入到达时间:/*:*/);scanf(%d:%d,&(p-reach.hour),&(p-reach.min);Enter-stackEnter-top=p;return(1);else /*车场已满，车进便道*/ printf(n该车须在便道等待!);t=(QueueNode *)malloc(sizeof(QueueNode);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-top0) /*有车*/ while(1) /*输入离开车辆的信息*/ printf(n请输入车在车场的位置/1-%d/：,Enter-top);scanf(%d,&room);if(room=1&roomtop) break;while(Enter-toproom) /*车辆离开*/Temp-top+;Temp-stackTemp-top=Enter-stackEnter-top;Enter-stackEnter-top=NULL;Enter-top-; p=Enter-stackEnter-top;Enter-stackEnter-top=NULL;Enter-top-;while(Temp-top=1)Enter-top+;Enter-stackEnter-top=Temp-stackTemp-top;Temp-stackTe