第一篇：2数据结构-实验报告二(栈和队列及其应用)
实验二 栈和队列及其应用
一、实验目的
1.掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。
2.熟练掌握栈类型的两种实现方法。
3.熟练掌握循环队列和链队列的基本操作实现算法。
二、实验内容
用队列求解迷宫问题 [问题描述] 以一个M*N的长方阵表示迷宫，0和1分别表示迷宫中的通路和墙壁。设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。[基本要求] 实现一个以顺序存储结构的队列类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i，j，pre）的形式输出，其中：（i，j）指示迷宫中的一个坐标，pre表示本路径中上一个方块在队列中的下标。
[测试数据] 由学生任意指定。
三、源代码
# include
//行数 //列数
//队最多元素个数
//一个迷宫,其四周要加上均为1的外框{1,1, #define MaxSize 100 int mg[M+2][N+2]={ {1,1,1,1,1,1,1}, {1,0,0,0,0,0,1}, {1,0,1,0,0,1,1}, {1,0,1,0,0,1,1}, {1,0,1,0,1,0,1}, {1,0,0,0,0,0,1}, {1,1,1,1,1,1,1} };
typedef struct {int i,j;int pre;} Box;typedef struct { Box data[MaxSize];int front, rear;}QuType;void mgpath1(int xi,int yi,int xe,int ye)//搜索路径为：（xi，yi）{ void print(QuType qu, int front);->(xe,ye)
int i,j,find=0,di;QuType qu;//定义顺序队 qu.front=qu.rear=-1;qu.rear++;qu.data[qu.rear].i=xi;//(xi,yi)进队 qu.data[qu.rear].j=yi;qu.data[qu.rear].pre=-1;mg[xi][yi]=-1;while(qu.front!=qu.rear&&!find){qu.front++;i=qu.data[qu.front].i;j=qu.data[qu.front].j;if(i==xe&&j==ye){find=1;print(qu,qu.front);
}
for
(di=0;di<4;di++)
{
switch(di)
{
case 0 :i=qu.data[qu.front].i-1;j=qu.data[qu.front].j;break;case 1 :i=qu.data[qu.front].i;j=qu.data[qu.front].j+1;break;case 2 :i=qu.data[qu.front].i+1;j=qu.data[qu.front].j+1;break;case 3 :i=qu.data[qu.front].i;j=qu.data[qu.front].j-1;break;
}
if(mg[i][j]==0)
{find=1;
qu.rear++;
qu.data[qu.rear].i=i;qu.data[qu.rear].j=j;
qu.data[qu.rear].pre=qu.front;
mg[i][j]=-1;
}
} } }
void print(QuType qu, int front){
int k=front,j,ns=0;
printf(“n”);do
{j=k;
k=qu.data[k].pre;
qu.data[j].pre=-1;
} while(k!=0);printf(“迷宫路径如下：n”);k=0;while(k ns++; printf(“t(%d,%d)”,qu.data[k].i,qu.data[k].j); if(ns%5==0)printf(“n”);} k++;} printf(“n”);} void main() { mgpath1(1,1,M,N);printf(“迷宫所有路径如下:n”); } 四、测试结果： 五、心得体会 做实验首先要掌握大量的理论知识，然后认真去完成实验。做实验过程会碰见较大的困难，这就要需要我们的毅力。小小的迷宫隐藏大大的奥秘。 实验5 栈和队列的应用 目的和要求： （1）熟练栈和队列的基本操作；（2）能够利用栈与队列进行简单的应用。 一、题目 题目1.利用顺序栈和队列，实现一个栈和一个队列，并利用其判断一个字符串是否是回文。所谓回文，是指从前向后顺读和从后向前倒读都一样的字符串。例如，a+b&b+a等等。 题目2.假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一算法模拟上述舞伴配对问题，并实现。 题目3.打印机提供的网络共享打印功能采用了缓冲池技术，队列就是实现这个缓冲技术的数据结构支持。每台打印机具有一个队列（缓冲池），用户提交打印请求被写入到队列尾，当打印机空闲时，系统读取队列中第一个请求，打印并删除之。请利用队列的先进先出特性，完成打印机网络共享的先来先服务功能。 题目4.假设以数组Q[m]存放循环队列中的元素, 同时设置一个标志tag，以tag == 0和tag == 1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。试编写与此结构相应的插入(enqueue)和删除(dlqueue)算法。 题目5.利用循环链队列求解约瑟夫环问题。 请大家从本组未讨论过的五道题中选择一道，参照清华邓俊辉老师MOOC视频及课本相关知识，编写相应程序。 选择题目3： 打印机提供的网络共享打印功能采用了缓冲池技术，队列就是实现这个缓冲技术的数据结构支持。 二、程序清单 //Ch3.cpp #include { p=front; front=front->link; delete p;} };template if(front==NULL){//判断是否为空 front=rear=new LinkNode front->data=rear->data=x; if(front==NULL)//分配结点失败 return false;} else{ rear->link=new LinkNode rear->link->data=x; if(rear->link==NULL) return false; rear=rear->link;} return true;};template { return false;} cout< LinkNode delete p;//释放原结点 return true;};void main() //主函数 { LinkedQueue char flag='Y'; //标志是否输入了命令 const int max=30;//一次获取输入命令的最大个数 while(flag=='Y')//循环 { int i=0;char str[max];//定义存储屏幕输入的命令的数组 gets(str);//获取屏幕输入的命令 while(str[i]!=' '){ q.put_in(str[i]);//调用提交命令函数，将每个命令存入队列中 i++; } for(int j=0;j<=i;j++){ if(q.IsEmpty()==true)//判断是否为空，为空则说明没有可执行的命令 { cout<<“已经没有可执行的命令！是否继续输入命令(Y|N)?”< cin>>flag;continue;//为空跳出for循环为下次输入命令做好准备 } q.carry_out();//调用执行命令的函数，将命令打印并删除 } 三、程序调试过程中所出现的错误 无。 四、运行结果： 五、心得体会 打印机采用的缓冲池技术，本质上就是利用了队列的先进先出的特点，体现了先来后到原则。虽然意思很简单，但是实际编程过程中，出现bug的概率还是蛮高的，因为在编写程序中一点疏忽就容易产生错误。 本来我对模板类的使用还是很模糊的，通过这个例子，至少让我清楚了模板类的使用和特点。觉得模板类的恰当使用，对于自己今后的编程好处还是很大的。 队列实验报告 小组成员：xxxxxxxx日期：xxxxxxxx 一、需求分析（xxx） 1.链队列 1）在本演示程序中，首先要链队列添加一个头结点，并判断队列是否为空，它只允许在表的一端进行插入，而在另一端删除元素，允许插入的一段叫队尾，允许删除的一端则为对头，接着访问队列中所有元素，并输出，输出是每个元素之间用空格来完成。最后销毁队列，释放空间。2）演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“欢迎来到链队列”“元素入队”“元素出队”“销毁队列”“清空队列”之后。由用户在键盘上输入演示程序中规定的运算命令，相应的运算数据和显示结果显示在其后。3）程序执行的命令包括： 欢迎来到链队列 1输出队列长度 2元素入队 3元素出队 4销毁队列 5清空队列 6对头元素 7退出链队列 4）测试数据 入队 1 2 3 4 5 分别执行“元素入队”“元素出队”“销毁队列”“清空队列”等操作。2.顺序队列 1）在本演示程序中，首先要顺序队列添加一个头结点，并判断队列是否为空，它只允许在表的一端进行插入，而在另一端删除元素，允许插入的一段叫队尾，允许删除的一端则为对头，接着访问队列中所有元素，并输出，输出是每个元素之间用空格来完成。2）演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“欢迎来到链队列”“元素入队”“元素出队”“取得头结点”“输出显示”之后。由用户在键盘上输入演示程序中规定的运算命令，相应的运算数据和显示结果显示在其后。3）程序执行的命令包括： 欢迎来到顺序队列 1入队 2出队 3判断是否为空 4取得头结点 5输出显示 6退出顺序队列 4）测试数据 入队 1 2 3 4 5 分别执行“元素入队”“元素出队”等操作。3循环队列 1）在本演示程序中，首先要顺序队列添加一个头结点，并判断队列是否为空，初始化建空队列时，令front=rear=0,每当插入新的队列尾元素时，“尾指针增1”；每当删除队列头元素时，“头指针增1”。接着访问队列中所有元素，并输出，输出是每个元素之间用空格来完成。2）演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“欢迎来到链队列”“元素入队”“元素出队”“取得头结点”“输出显示”之后。由用户在键盘上输入演示程序中规定的运算命令，相应的运算数据和显示结果显示在其后。3）程序执行的命令包括： 欢迎来到循环队列 1入队 2出队 3判断是否为空 4取得头结点 5输出显示 6退出顺序队列 4）测试数据 入队 1 2 3 4 5 分别执行“元素入队”“元素出队”等操作。 二．概要设计(xxxx) ⒈ 为实现上述算法，需要顺序表的抽象数据类型，抽象数据类型定义如下： ADT Queue { 数据对象：D={ ai|ai∈ElemSet, i=1,2,3...,n, n>=0 } 数据关系: R={ 操作结果：队列Q已被销毁。ClearQueue(&Q)初始条件：队列Q已存在。 操作结果：将Q清为空队列。QueueEmpty(Q)初始条件：队列Q已存在。 操作结果：若Q为空队列，则返回TRUE,否则FALSE。QueueLength(Q)初始条件：队列Q已存在。 操作结果：返回Q元素的个数，即队列的长度。GetHead(Q,&e)初始条件:Q为非空队列。 操作结果：用e返回Q的队头元素。EnQueue(&Q,e)初始条件：队列Q已存在。 操作结果：插入e返回Q的新的队尾元素。DeQueue(&Q，&e)初始条件：Q为非空队列。 操作结果：删除Q的队头元素，并用e返回其值。}ADT Queue 2.单链队列 typedefstructQNode { QElemType;structQNode *next;//指针域 }QNode,*QueuePtr;Typedefstruct{ QueuePtr front;QueuePtr rear;}LinkQueue;Status InitQueue(LinkQueue&Q)//构造一个空队列。 Status DestroyQueue(LinkQueue&Q)//销毁队列Q，Q不存在。 Status ClearQueue(LinkQueue&Q)//将Q清为空队列。 Status QueueEmpty(LinkQueueQ)//若Q为空队列，则返回TRUE,否则FALSE。intQueueLength(LinkQueueQ)//返回Q元素的个数，即队列的长度。 Status GetHead(LinkQueueQ,QElemType&e)//若队列不为空，则用e返回Q的队头元素，并返回OK;否则返回ERROR。 Status EnQueue(LinkQueue&Q,QElemType e)//插入e返回Q的新的队尾元素。 Status DeQueue(LinkQueue&Q,QElemType&e)//若队列不空，则删除Q的队头元素，并用e返回其值，并返回OK;否则返回ERROR。 三．详细设计（xxx） 1.顺序队列的实现和运算 1）元素的类型 typedefstruct { Datatypedata[MAXSIZE];intfront,rear;}Squeue;2）空的队列的构造 void InitSqueue(Squeue *p)/*初始化队列*/ { p->front=0;p->rear=0;} 3）元素的入队 int Ensqueue1(Squeue1 *q, Datatype e)/*入队*/ { if((q->rear+1)% MAXSIZE == q->front){ printf(“n队列已满n”);return 0;} 4）元素的出队 int DeSqueue1(Squeue1 *q,Datatype *e)/*出队*/ { if(q->front==q->rear){ printf(“队列已空,无法出队!”);return 0;} *e=q->data[q->front];q->front=(q->front+1)%MAXSIZE;return 1;} 5）判断队列是否为空 int QueueEmpty1(Squeue1 q)// 判断是否为空 { if(q.front==q.rear)return 1;else return 0;} 6）队头元素的取值的算法 int Gethead1(Squeue1 *q,Datatype *e)// 取对头元素 { if(q->front==q->rear){ printf(“队列已空，无法出队!”);return 0;} else *e=q->data[q->front];return 1;} 7）遍历顺序队列的算法 void display1(Squeue1 q)//遍历顺序对列 { printf(“此队列数据为:n”);if(q.front==q.rear)printf(“此队列为空!”);else { while(q.front void InitQueue2(LinkQueue *q){ // 构造一个空队列Q q->front=q->rear=malloc(sizeof(QNode));if(!q->front)exit(1);q->front->next=NULL;} 2）元素的入队算法 void EnQueue2(LinkQueue *q, QElemType e)//将元素e进队 { QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode));//创建新节点 if(!p)//如果内存分配成功 exit(1); p->data=e;//初始化新节点数据为e p->next=NULL; q->rear->next=p; q->rear=p;} 3）元素的出队的算法 int DeQueue2(LinkQueue *q,QElemType e)//队头结点出队,将出队的元素存入e { QueuePtr p;if(q->front==q->rear)//队列为空 return 0;p=q->front->next;//初始化temp为要出队的结点指针 if(q->front->next==q->rear)//要出队的结点为最后一个结点 q->rear=q->front;e=p->data;//要出队的数据元素为e q->front->next=p->next;//使下一个结点变为对头 free(p);//删除要出队的结点 return e;} 4）队列的长度算法 void QueueLength2(LinkQueue *q)//返回队列长度 { QueuePtr p;int i=0;p=q->front->next;while(p){ ++i; p=p->next;} printf(“链队列长度为:%dn”,i);} 5）队列的销毁 void DestroyQueue2(LinkQueue *q){ while(q->front){ q->rear=q->front->next; free(q->front); q->front=q->rear; if(!q->rear) free(q->rear);} free(q->front);} 6）队列的输出算法 void output2(LinkQueue *q)//输出队列 { QueuePtr p;p=q->front->next;printf(“链队列元素依次为:”);while(p){ printf(“%d->”,p->data); p=p->next;} printf(“n”);} 7）队列的清空的算法 void Clear2(LinkQueue *q)//清空队列 { QueuePtr temp=q->front->next;while(temp){ QueuePtrtp=temp; temp=temp->next; free(tp);} temp=q->front; q->front=q->rear=NULL;free(temp);} 8）返回对头元素的算法 int GetHead2(LinkQueue *q, int *e)//返回对头结点元素，存入e { if(q->front==q->rear) return 0;*e=q->front->next->data;return 1;} 3.循环队列的实现和运算 1）队列的初始化算法 void InitSqueue3(Squeue3 *p)/*初始化队列*/ { p->base=(Datatype *)malloc(sizeof(Datatype)* MAXSIZE);p->front=0;p->rear=0;} 2）入队的算法 int Ensqueue3(Squeue3 *q, Datatype e)/*入队*/ { if((q->rear+1)% MAXSIZE == q->front){ printf(“n队列已满n”);return 0;} else q->base[q->rear]=e;/*将接收到得值付给队尾所指的节点*/ q->rear=(q->rear+1)% MAXSIZE;/*队尾向后移一位完成入队*/ return 1;} 3）出队的算法 int DeSqueue3(Squeue3 *q,Datatype *e)/*出队*/ { if(q->front==q->rear){ printf(“队列已空,无法出队!”);return 0;} *e=q->base[q->front];q->front=(q->front+1)%MAXSIZE;return 1;} 4判断队列是否为空的算法 int QueueEmpty3(Squeue3 q)// 判断是否为空 { if(q.front==q.rear)return 1;else return 0;} 5）对头元素的返还的算法 int Gethead3(Squeue3 *q,Datatype *e)// 取对头元素 { if(q->front==q->rear){ printf(“队列已空，无法出队!”);return 0;} else *e=q->base[q->front];return 1;} 6）遍历循环队列的算法 void display3(Squeue3 *q)//遍历循环对列 { int tail;tail=q->front;printf(“此队列数据为:n”);if(q->front==q->rear)printf(“此队列为空!”);else { while(tail!=q->rear){ printf(“%dt”, q->base[tail]);tail=(tail+1)%MAXSIZE;} printf(“n”);} } 4.主函数的算法 void main(){ int choice;Datatype e1;int i1,a1,x1,s1,j1;//顺序队列定义的量 int e2,i2,n2,s2,a2;//链队列定义的量 int i3,a3,x3,s3,j3;//循环队列定义的量 Datatype e3; Squeue1 Q1; //******************************* LinkQueue q; //******************************** Squeue3 Q; //**************************** choice=-1;Begin();while(choice!=0){ scanf(“%d”,&choice);switch(choice){ case 1://顺序队列 { system(“cls”);InitSqueue1(&Q1);printf(“创建队列完成!n”);printf(“请输入数据个数j1=”);scanf(“%d”,&j1);for(i1=1;i1<=j1;i1++)//输入的数据个数不要超过MAXSIZE,多了的部分没有插入队列 { printf(“请输入第%d个数据:”,i1);scanf(“%d”,&a1);Ensqueue1(&Q1,a1); } printf(“对头为:%dn”,Q1.data[Q1.front]);printf(“队尾为:%dn”,Q1.data[Q1.front+j1-1]);display1(Q1);s1=-1;start1();while(s1!=0) { scanf(“%d”,&s1);switch(s1) { case 0: system(“cls”); choice=-1; Begin(); break;case 1: { system(“cls”);printf(“请输入入队元素:n ”);scanf(“%d”,&x1);Ensqueue1(&Q1,x1);display1(Q1); s1=-1; start1();break; } case 2: { system(“cls”);DeSqueue1(&Q1,&e1);display1(Q1);s1=-1; start1();break; } case 3: { system(“cls”);if(QueueEmpty1(Q1))printf(“此队列为空!n”);else printf(“此队列不为空!n”); } s1=-1; start1();break;case 4: { system(“cls”); Gethead1(&Q1,&e1);printf(“对头元素为:%dn”,e1); s1=-1; start1();break; } case 5: { system(“cls”);display1(Q1);s1=-1; start1();break; } }//switch } //while }//case1 break;//************************************************* case 2: { system(“cls”); InitQueue2(&q);printf(“创建队列完成!n”);printf(“输入将建立链队列元素的个数:n2=”);scanf(“%d”,&n2);printf(“请输入队列的元素：n”);for(i2=1;i2<=n2;i2++) { printf(“请输入第%d个元素:”,i2); scanf(“%d”,&e2); EnQueue2(&q,e2); } a2=-1;start2();while(a2!=0) { scanf(“%d”,&a2); switch(a2) { case 1:system(“cls”); QueueLength2(&q); a2=-1;start2(); break; case 2:{ system(“cls”); printf(“请输入入队元素:”); scanf(“%d”,&e2);EnQueue2(&q,e2); output2(&q);a2=-1;start2(); }break; case 3: system(“cls”); e2=DeQueue2(&q,e2); output2(&q); printf(“出队元素为:%dn”,e2);a2=-1;start2(); break; case 4:DestroyQueue2(&q);printf(“队列已销毁!n”); a2=0;system(“cls”); choice=-1; Begin(); break; case 5: Clear2(&q);printf(“队列已清空n”); a2=0;system(“cls”); choice=-1; Begin(); break; case 6: system(“cls”);GetHead2(&q,&e2); printf(“队头元素为:%dn”,e2);s2=-1; start2(); break; case 0: system(“cls”); choice=-1; Begin(); break; }//switch }//while }//case2 break;//************************************************** case 3: { system(“cls”); InitSqueue3(&Q);printf(“创建队列完成!n”);printf(“请输入数据个数j3=”);scanf(“%d”,&j3);for(i3=1;i3<=j3;i3++)//输入的数据个数不要超过MAXSIZE,多了的部分没有插入队列 { printf(“请输入第%d个数据:”,i3);scanf(“%d”,&a3);Ensqueue3(&Q,a3); } printf(“对头为:%dn”,Q.base[Q.front]);printf(“队尾为:%dn”,Q.base[Q.front+j3-1]);display3(&Q);s3=-1;start3();while(s3!=0) { scanf(“%d”,&s3);switch(s3) { case 0: system(“cls”); choice=-1; Begin(); break;case 1: { system(“cls”);printf(“请输入入队元素:n ”);scanf(“%d”,&x3);Ensqueue3(&Q,x3);display3(&Q); s3=-1; start3();break; } case 2: { system(“cls”);DeSqueue3(&Q,&e3);display3(&Q);s3=-1; start3();break; } case 3: { system(“cls”);if(QueueEmpty3(Q))printf(“此队列为空!n”);else printf(“此队列不为空!n”); } s3=-1; start3();break;case 4: { system(“cls”); Gethead3(&Q,&e3);printf(“对头元素为:%dn”,e3); s3=-1; start3();break; } case 5: { system(“cls”);display3(&Q);s3=-1; start3();break; } }//switch } //while }//case 3 break; case 0: printf(“ 谢谢使用！！n”); break; //*************************** }//switch }//while }//main 四．调试分析（xxx） 顺序队列 1.编译并调试，运行程序。 2.设计测试用例，分析测试结果，以验证所完成的系统是否达到预期效果。3.判断队列是否为空。队列是否为空的标志就是队头指针和队尾指针是否同时指向队列中的同一个位置，即队头指针和队尾指针是否相等。 4.队列满时候不能入队列，否则会出现溢出现象。即先要判断队列是否已经已满，因为队尾指针的最大值是MAXQSIZE，所以通过检查队尾指针rear是否等于MAXQSIZE来判断队列是否已满。在删除队首元素时，应首先通过队头指针和队尾指针是否相等判断队列是否已空。 5.在元素出队操作，先通过队头指针和队尾指针是否相等判断队列是否已空，空时不能操作，这是要注意的。 6.程序满足了本次试验的目的和任务要求，可以进行人机交互，在后来的程序中将会做些改进，以增强人机交互性。 7.本程序存在较多不足，如有问题，参考用户手册。 8.在程序语句中，原本使用了大量的生僻的函数名，经过改进，目前使用都是通俗易懂的函数名称，方便用户理解。 链队列 1.编译并调试，运行程序。2.设计测试用例，分析测试结果，以验证所完成的系统是否达到预期效果。 3.要注意设定一个在链队列添加一个头结点并令指针指向头结点。同时，删除不可以在最后面进行删除，但是插入可以最后一个进行插入，这点需要注意 4.需要分别指向队头和队尾的指针。 5.程序满足了本次试验的目的和任务要求，可以进行人机交互，在后来的程序中将会做些改进，以增强人机交互性。 6.本程序存在较多不足，如有问题，参考用户手册。 7.在程序语句中，原本使用了大量的生僻的函数名，经过改进，目前使用都是通俗易懂的函数名称，方便用户理解。 循环队列 1.编译并调试，运行程序。 2.设计测试用例，分析测试结果，以验证所完成的系统是否达到预期效果。 3.为了避免顺序队列造成的“假溢出”现象，我们通常采用顺序循环队列实现队列的顺序存储。4.队头指针和对尾指针与队列元素之间关系和顺序队列一样，不变。5.先判断队列是否为空。就是看队头指针和队尾指针是否同时指向队列中的同一个位置，即队头指针和队尾指针是否相等，空时不能操作，这是要注意的。 6.在将元素插入到队列之前首先要判断队列是否已经已满，根据顺序循环队列队满条件front==(rear+1)%MAXQSIZE来判断队列是否已满。在删除队首元素时，应首先通过队头指针和队尾指针是否相等判断队列是否已空。 6.程序满足了本次试验的目的和任务要求，可以进行人机交互，在后来的程序中将会做些改进，以增强人机交互性。 7.本程序存在较多不足，如有问题，参考用户手册。 8.在程序语句中，原本使用了大量的生僻的函数名，经过改进，目前使用都是通俗易懂的函数名称，方便用户理解。 五、用户手册(xx)1.链队列 (1)本程序的运行环境为DOS操作系统，执行文件名为：j.exe.(2)进入演示程序后即显示文本方式的用户界面，输入元素1,2,3,4,5创建队列。 （3）根据提示，选择操作2执行元素入队操作。回车，输入入队元素0，回车，将0插入到队列中。 （4）选择操作3执行元素出队操作，回车，队首元素1出队。 （5）选择操作1执行输出队列长度操作，回车，输出队列长度为5.（6）选择操作5执行清空队列操作，回车，清空。 （7）选择操作6执行输出队头元素操作，回车，输出元素2。 2.顺序队列 （1）创建队列，输入数据 1,2,3,4,5.（2）选择操作1，执行入队操作.输入入队元素0 （3）选择操作2，执行出队操作。 队首元素1出队.（4）选择操作3，判断对是否为空 （5）选择操作4，输出对头元素2.（6）选择操作5，显示队列元素 3、循环队列 （1）创建队列，输入数据 1,2,3,4,5.（2）选择操作1，执行入队操作.输入入队元素0 （3）选择操作2，执行出队操作。队首元素1出队.（3）选择操作3，判断对是否为空 （5）选择操作4，输出对头元素2.（6）选择操作5，显示队列元素为,2,3,4,5,0 六．测试结果（xxx）1.顺序队列的实现和运算 1）输入1即可进行进入到顺序队列 2）顺序队列的建立，输入元素的个数为5，输入的数据分别为1，2，3，4，5，对头为1，队尾为5，此时队列的数据为1 2 3 3）输入2即可进行入队运算，输入的入队元素为0，此时的队列的数据为1 2 3 4 5 0 4）输入3即可进行判断队列的是否为空，如下图： 5）输入4即可进行去的对头元素的算法，如下图所示： 6）此时的队列的数 据 为 0，如 下 图 ： 7）输入0即可退出顺序队列，如下图： 8）输入3即可进行顺序队列的算法，如下图所示： 9）输入1即可进 行 相 应的入 队 运 算，如 下 10）输入2即可进行队列的出队运算，如下图所示： 所 示 图 ：11）输入3 即可判断顺序队列是否为空的算法，如下图所示： 12）输入4即可进行去的头结点的运算，如下图所示： 13）输入5即可进行队列的输出显示的运算，如 14）输入0即可进行退出顺序队列的算法，如下图所示： 下图所示：2.链式队列的实现和运算 1）队列的建立以及队列的个数输入为5，输入的数据分别为1，2，3，4，5.如下图： 2）输入2即可进入到元素的入队运算，输入入队的元素的为0，输入3即可进行相应的元素的出队运算，出队元素为1.如下图： 3）则此时的队列的长度为5，输入4即可进行队列的销毁以及输入5即可进行队列的清空运算，如下图： 4）输入6即可进行输出队列的对头元素，输入0即可进行退出链队列的运算 3．循环队列的实现和运算 1）输入3即可进行循环队列的操作，输入5个数据，它们分别为1 2 3 4 5，输入1，即可进行入队操作，输入入队的元素为0，则此时的数据为1 2 3 4 5 0，如下图所示： 2）输入2即可进行出队运算，如下图所示： 3）输入3即可进行判断队列的是否为空，如下图所示： 4）输入4即可进行取得对头元素，如 下 5)输入5即可进行输出所有的数据显示，如下图所示： 所示图： 七．心得体会（xx） 队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。 在队列这种数据结构中，最先插入的元素将是最先被删除的元素；反之最后插入的元素将是最后被删除的元素，因此队列又称为“先进先出” 的线性表。注意的是为了避免顺序队列造成的“假溢出”现象，我们通常采用顺序循环队列实现队列的顺序存储。还有要注意的是在C语言中不能用动态分配的一维数组来实现循环队列，如果用户的应用程序中设有循环队列，则必须为它设定一个最大队列长度；若用户无法估计所用队列的最大长度，则宜采用链式队列。 栈和队列上机实习 1、实验目的： （1）熟练掌握栈的逻辑结构和操作规则，能在相应的实际问题中正确选用该结构。（2）熟练掌握栈的2种存储结构实现方法（顺序栈和链栈），两种存储结构和基本运算的实 现算法，注意栈空盒满的判断条件及它们的描述方法。 （3）熟练掌握队列的逻辑结构和操作规范，能在相应的实际问题中正确选用该结构。（4）掌握循环队列与链队列两种存储结构的实现，熟练掌握各种队列基本运算的实现。 2、实验要求： （1）顺序栈的插入、删除，栈顶数据元素的读取。（2）链栈的插入、删除，栈顶数据元素的读取。（3）循环队列的插入、删除。（4）链队列的插入、删除。 3、实验内容: ① 栈 （1）抽象数据类型定义 typedef struct { ElemType data[MaxSize]; //栈的空间大小为MaxSize int top; //设置栈顶指针 }SqStack; //栈的结构定义 在本次实验中，首先建立一个空栈，进入主程序后首先初始化栈为其分配空间，然后进入菜单选择界面，通过不同的数字输入，实现入栈，出栈，读取栈顶元素，显示栈的所有元素，栈的长度，释放栈等操作。 （2）存储结构定义及算法思想 在栈结构体的定义中，typedef int Typeelem 为整型，存储结构（入栈）如下： cin>>a; s->top++; //在入栈是首先将栈顶指针向上加1 s->data[s->top]=a; //与数组赋值一样，直接赋值 //其他存储与此类似，都是直接赋值与数组的某一位 退栈函数模块： void Pop(SqStack * &s){ //对指针的引用 if(s->top ==-1){ cout<<“栈是空栈，不能退栈”< //首先判断是否为空栈，若为空，则退出 return;} cout<<“退栈的元素为：”< //显示退栈元素 s->top--; //栈顶元素减1，指向实际栈的最上面 } 显示栈所有元素函数模块： void DispStack(SqStack *s){ //从栈顶到栈底顺序显示所有元素 int i;cout<<“栈的元素分别为：”< //同过循环实现实现从栈顶元素到栈底元素的遍历以输出 } cout< 栈结构的入栈和退栈是两个相反的过程，先进后出，入栈是先让栈顶指针加1,指向未被赋值位置，然后进行赋值，退栈是先取出退栈元素，然后栈顶元素减1，指向推展后的实际栈顶。诸如读取栈顶元素，显示栈的元素，读取栈的长度，都是用过对栈顶指针实现相关操作。 （3）实验结果与分析 ② 循环队列 （1）抽象数据类型定义 typedef struct { ElemType elem[Maxqsize]; //循环队列的长度为MaxSize int front,rear; //设置队列的头指针和尾指针 }SqQueue; //循环队列的结构体定义 在本次实验中，首先建立一个空队列，进入主程序后首先初始化队列为其分配空间，然后进入菜单选择界面，通过不同的数字输入，实现入队，出队，显示队列的所有元素，队列的长度，释放队列等操作。 （2）存储结构定义及算法思想 在队列结构体的定义中，typedef int Typeelem 为整型，存储（入队）结构如下： q->rear=(q->rear+1)%Maxqsize; //尾指针加1 q->elem[q->rear]=a; //将入队元素装到新的空尾部 在此队列的存储结构的实现：先让队尾指针进1，再将新的元素加入到队尾指针所指示的位置，因此，队尾指针指示实际的队尾位置，队头指针指示实际队头的前一位置，要想退出队头元素，必须先让队头指针进1，才能取出队头元素。 退队函数模块如下： void deQueue(SqQueue *&q){ //对指针的引用 if(QueueEmpty(q)) { //调用带返回值的判断空队函数 cout<<“队列为空”< //判断队列是否为空 } q->front=(q->front+1)%Maxqsize; //队头指针进1 cout<<“退队的元素为：”< //取出队头元素 } 遍历队表函数： void displayqueue(SqQueue *q){ int m;m=q->front+1; //队头元素进1，指向实际队头 if(QueueEmpty(q)) { cout<<“队列为空”< //判断是够为空队 } cout<<“所有队列元素为：”< while(q->rear+1>m){ cout< //通过循环遍历所有元素 m++; } cout< 循环队列的入队和退队分别是在队尾与队头跟别进行操作的，通过队头队尾指针的操作便可实现对队列的相关操作。 （3）实验结果与分析 ③ 心得体会 本次上机是做栈与队列的操作，这次实验，我有意的用到了对指针的引用与指针实现子函数功能的调用，刚开始编译的时候也有错误，但是在慢慢的摸索中，也逐渐掌握了它们的用法，这次实验也让我熟练了对队列与栈存储结构的应用。 附录： 顺序表源代码: 栈： #include void InitStack(SqStack * &s) //建立一个空栈，即将栈顶指针指向-1即可 的引用 { s=(SqStack *)malloc(sizeof(SqStack));s->top=-1;} void ClearStack(SqStack * &s) //释放栈s占用的存储空间 { free(s);} void StackLength(SqStack *s) { cout<<“栈的长度为：” <<(s->top +1)< int StackEmpty(SqStack *s){ return(s->top==-1);} void Push(SqStack *&s){ if(s->top==MaxSize-1) { cout<<“栈满”< // s=(SqStack *)realloc(s,sizeof(SqStack));} int a; 指针 cout<<“请输入入栈元素”< void Pop(SqStack * &s){ if(s->top ==-1){ cout<<“栈是空栈，不能退栈”< return;} cout<<“退栈的元素为：”< void GetTop(SqStack * &s,ElemType &e){ if(s->top==-1){cout<<“空栈”< void DispStack(SqStack *s) //从栈顶到栈底顺序显示所有元素 { int i;cout<<“栈的元素分别为：”< cout<<“请选择功能”< cout<<“ 入栈 1”< cout<<“ 出栈 2”< cout<<“ 读取栈顶元素 3”< cout<<“ 显示栈所有元素 4”< cout<<“ 栈的长度 5”< cout<<“ 释放栈 6”< cin>>k; switch(k) { case 1: Push(s);break; case 2: Pop(s);break; case 3: GetTop(s,e);cout<<“栈顶元素为： ”< case 4: DispStack(s);break; case 5: StackLength(s);break; case 6: ClearStack(s);break; default :break; } } } 队列： #include TypeElem elem[Maxqsize]; int front,rear;}SqQueue;void InitQueue(SqQueue *&q){ q=(SqQueue *)malloc(sizeof(SqQueue)); q->front=q->rear=0;} void ClearQueue(SqQueue *&q){ free(q);exit(0);} void QueueLength(SqQueue *q){ cout<<“队列长度为：”<<(q->rear-q->front+Maxqsize)%Maxqsize< return(q->front==q->rear); } void enQueue(SqQueue *&q){ int a; if((q->rear+1)%Maxqsize==q->front) { cout<<“队列已满，无法插入”< } cout<<“请输入插入元素”< cin>>a; q->rear=(q->rear+1)%Maxqsize; q->elem[q->rear]=a;} void deQueue(SqQueue *&q){ if(QueueEmpty(q)) { cout<<“队列为空”< } q->front=(q->front+1)%Maxqsize; cout<<“退队的元素为：”< } void displayqueue(SqQueue *q){ int m;m=q->front+1; if(QueueEmpty(q)) { cout<<“队列为空”< } cout<<“所有队列元素为：”< while(q->rear+1>m) { cout< m++; } cout< int k=0; SqQueue *q; InitQueue(q); if(QueueEmpty(q))cout<<“队列为空”< while(1){ cout<<“请选择功能”< cout<<“ 入队 cout<<” 出队 cout<<“ 队列长度 cout<<” 显示队列元素 cout<<“ 释放栈 cin>>k; switch(k) { case 1: enQueue(q);break; case 2: deQueue(q);break; case 3: QueueLength(q);break; case 4: displayqueue(q);break; case 5: ClearQueue(q);break; default :break; } } } 1”< 2“< 4“< 一、实验目的 掌握栈的数据类型描述及栈的特点； 掌握栈的顺序存储结构的特点及算法描述； 掌握队列的数据类型描述及链式存储结构的特点和算法描述。 二、实验内容 停车场管理。设有一个可以停放n辆汽车的狭长停车场（先进后出），它只有一个大门可以供车辆进出。车辆按到达停车场时间的先后依次从停车场最里面向大95E8口处停放（最先到达的第一辆车停放在停车场的最里面）。如果停车场已放满n辆车，则后来的车辆只能在停车场大门外的便道上等待，一旦停车场内有车离开，则排在便道上的第一辆车就可以进入停车场。停车场内如有某辆车要离开，在它之后进入停车场的车都必须先退出停车场为它让路，待其开出停车场后，这些车再按原来的次序进停车场。每辆车在离开停车场时，都应根据它在停车场内停留的时间长短交费。如果停留在便道上的车没进停车场就要离开，允许其离开，不收停车费，并且仍然保持在便道上的车辆次序。试编程模拟停车场管理。 三、算法描述 提示：可以将停车场定义成一个顺序栈s1，便道定义成一个链队列q，而停车场中的某辆车要离开，则在它后面进停车场的车必须让道，让其离开，故还必须有一个临时的顺序栈s2，存放让道的车辆。 当有车辆进停车场时，直接进入s1栈，若s1栈满，则进入便道（链队列q）。若有s1中车辆x离开时，先让在x后面进栈的车从s1退栈并进栈到s2中，让x离开并收取停车费，然后，再把s2中的所有车辆退栈并重新进入s1栈，最后，将链队列q的队头车辆进栈到s1中并删除队头车辆。若有链队列q（便道）中的车辆y离开时，从链队列中删除该车辆即可，不收停车费。 车辆的数据可以表示为（车辆编号，到达/离开时间）。 四.程序清单: #include SeqStack(){top=-1;} ~SeqStack(){};void Push(int x);void Push2(int x);int *Return();int Pop(int y);int Count();void PrintStack();private: int data[StackSize];int top;};//入栈 void SeqStack::Push(int x){ if(top>=StackSize-1)throw“上溢”;for(int i=0;i<=top+1;i++){ if(data[i]==x) { cout<<“该车牌已经存在!请重新输入: ”; i=-1; cin>>x; } } top++;data[top]=x;} //返回数组地址 int *SeqStack::Return(){ return data;} //临时栈 void SeqStack::Push2(int x){ top++;data[top]=x; } //输出函数 void SeqStack::PrintStack(){ for(int i=0;i<=top;i++) cout<<“位置为”< int SeqStack::Pop(int y){ if(top==-1)throw“下溢”;int x;x=data[top--];if(y==top+2)data[top+1]=123456789;if(top==-1)data[top+1]=123456789;return x;} //数数 int SeqStack::Count(){ return top;} //队列 struct Node { int data;Node *next;};class LinkQueue { public: LinkQueue();void EnQueue(int x,int *q);void xzDeQueue(int x);int Count();int DeQueue(); private: Node *front,*rear;};//构造函数 LinkQueue::LinkQueue(){ Node *s=new Node;s->next=NULL;front=rear=s;} //入队 void LinkQueue::EnQueue(int x,int *q){ Node *s=new Node;Node *p=new Node;p=front;while(p){ if(p->data ==x) { cout<<“便道已有该车牌号,请重新输入: ”; cin>>x; for(int i=0;i<5;i++) { if(x==q[i]) { cout<<“停车场已有该车牌号,请重新输入: ”; cin>>x; i=-1; } } p=front;} p=p->next;} s->data =x;s->next =NULL; rear->next =s;rear=s;} //出队 int LinkQueue::DeQueue(){ if(front==rear)throw“便道无车辆”;Node *p=new Node;int x;p=front->next;x=p->data;front->next =p->next;if(p->next ==NULL)rear=front;delete p;return x;} //计算结点数 int LinkQueue::Count(){ Node *p=new Node;p=front;int i=0;while(p&&p->next!=NULL){ p=p->next; i++;} return i;} //选择性出队 void LinkQueue::xzDeQueue(int x){ if(rear==front)throw“便道无车辆”;Node *p=new Node;p=front;int y;int i=0;for(;p->next!=NULL;p=p->next) { if(p->next->data ==x) if(p->next->next!=NULL) { Node *q=new Node; q=p->next; y=q->data; p->next =q->next; i=1; delete q; cout<<“车牌号为:”< break; } else { Node *q=new Node; q=p->next; y=q->data; p->next =NULL; i=1; delete q; if(front->next==NULL)rear=front; cout<<“车牌号为:”< break; } } if(i==0)cout<<“无车牌号为:”< SeqStack b;//b是作为临时存放车辆的栈 LinkQueue c;//c是作为便道的队列 cout<<“tttt1.车辆进入”< cout<<“tttt4.便道车辆离开”< int xh1=1;//xh1为菜单最外层的循环控制变量 int time[100];//记录各车辆进入停车场的时间 int t1=0;//作为车辆对应的时间编号 int money=1;while(xh1==1){ cout<<“请选择指令: ”; cin>>zl; switch(zl) { case 1: try{ int n1=a.Count(); int n; cout<<“请输入车牌号: ”; cin>>n; if(n1==4) { int *Num=a.Return(); for(int i=0;i<=4;i++) if(Num[i]==n) { cout<<“停车场已有该车牌号,请重新输入!”; cin>>n; i=-1; } int *CarNum=a.Return(); c.EnQueue(n,CarNum); cout<<“停车场已满,请在便道等候!”< break; } a.Push(n); cout<<“请输入进入时间: ”; cin>>time[t1]; while(time[t1]<0||time[t1]>=24) { cout<<“请输入正确的时间(0~23时):”; cin>>time[t1]; } t1++; } catch(char*s){cout< break; case 2: try{int n2;//离开车辆的编号 cout<<“请输入要离开的车的位置: ”; cin>>n2; if(a.Count()+1==0) { cout<<“该停车场没有车辆,请选择其他操作!”; break; } else while(n2<1||n2>a.Count()+1) { cout<<“请输入1~”< cin>>n2; } int j=a.Count(); for(int i=0;i<(j+1-n2);i++) b.Push2(a.Pop(n2)); a.Pop(n2); int j2=b.Count(); for(int i1=0;i1<=j2;i1++) a.Push(b.Pop(n2)); int j3=c.Count(); int time1; cout<<“请输入离开时间: ”; cin>>time1; while(time1<0||time1>23) { cout<<“请输入正确的时间(0~23时): ”; cin>>time1; } int day=0; if(time1 { cout<<“离开时间已小于进入时间!请加上停留天数(天):”; cin>>day; while(day<=0) { cout<<“输入的天数必须大于0：”; cin>>day; } } cout<<“您的费用是(元): ”<<(time1-time[n2-1]+24*day)*money< for(int i2=0;i2<(j+1-n2);i2++) time[n2-1+i2]=time[n2+i2]; t1--; if(j3!=0) { a.Push(c.DeQueue()); cout<<“ttt通知: 便道车辆请进入停车场!”< cout<<“请输入进入时间: ”; cin>>time[t1]; while(time[t1]<0||time[t1]>=24) { cout<<“请输入正确的时间(0~23时):”; cin>>time[t1]; } t1++; } }catch(char *s){cout< break; case 3: a.PrintStack();break; case 4: int n3; cout<<“请输入离开车辆的车牌号: ”; cin>>n3;try{ c.xzDeQueue(n3);}catch(char*s){cout< break; case 5: cout<<“请输入单价: ”; cin>>money; cout<<“修改成功!”< cout<<“当前停车场的费用是:”< break; case 6: xh1=0; break; } } system(“pause”);} 心得体会: 完成时间:2010-10-30第二篇：实验报告——栈和队列的应用
第三篇：数据结构 队列实验报告
第四篇：数据结构栈与队列报告
第五篇：实验三 栈和队列的应用
点击咨询 