数据结构实验报告实验二栈和队列的应用
实验二 栈和队列的应用
一、实验内容：实现链队列（带头结点）的各种基本运算，完成如下功能：
（1）初始化并建立链队列
（2）入队列
（3）出队列
二、实验目的：掌握栈和队列的定义和实现，学习利用栈和队列解决实际问题。
三、问题的实现
数据结构的抽象数据类型定义和说明：
ADT Queue{
数据对象：D={ai|ai∈Elemset,i=1,2,…n,n>=0}
数据关系：R1={}|ai-1,ai∈D, ,i=1,2,…n}
约定其中a1端为队列头，an端为队列尾
基本操作：InitQueue(LinkQueue &Q) //构造一个空队列
EnQueue(LinkQueue &Q,int e) //插入元素e为Q的新的队尾元素
DeQueue(LinkQueue &Q,int &e) //若队列不空，则删除其队头元素，
用e返回其值
GetHead(LinkQueue &Q,int &e) //逐个取出队头元素，直到全部
} ADT Queue
主要的实现思路：首先定义结点类型，链表类型。根据菜单提示做入队出队的操
作。每次入队出队后都会将队中的所有元素输出一遍。
四、实验要求
1、写出主要源程序代码（包含程序备注）；
#include "stdio. h"
#include "stdlib.h"
typedef struct Queue{ int data;struct Queue *next;
} Queue,*QueuePtr;
typedef struct {QueuePtr front; QueuePtr rear;}LinkQueue; /**************构造队列**************/
void InitQueue(LinkQueue &Q)
{Q.front=Q.rear=(QueuePtr)malloc(sizeof(Queue));
Q.front->next=NULL;printf("构造成功！\n");}
/**************进队函数**************/
int EnQueue(LinkQueue &Q,int &e)
{QueuePtr p;p=(QueuePtr)malloc(sizeof(Queue));
if (!p) return 0;p->data=e;p->next=NULL;
Q.rear->next=p;Q.rear=p;return 1;}
/**************出队函数**************/
void DeQueue(LinkQueue &Q,int &e)
{QueuePtr p; if(Q.front==Q.rear) printf("该队列为空\n"); p=Q.front->next;e=p->data;Q.front->next=p->next;
if(Q.rear==p) Q.rear=Q.front;free(p);printf("出队成功\n");} /**************取对头函数**************/
void GetQueue(LinkQueue &Q,int &e)
{QueuePtr p; if (Q.front==Q.rear) printf("队列为空，无对头\n");
p=Q.front->next;e=p->data;}
/**************输出函数**************/
void OutQueue(LinkQueue Q)
{if(Q.rear==Q.front) printf("队列为空，无元素值。\n");
Queue *head=Q.front->next;
while(head!=NULL){printf("%d",head->data);
printf(" ");head=head->next;}}
/**************主函数**************/
void main()
{char ch;int e;LinkQueue Q;
do{
printf("\t\t\t ---队列操作--- ");
printf("\n\t\t\t**********************");
printf("\n\t\t\t* 0---退出 *");
printf("\n\t\t\t* 1---初始化 *");
printf("\n\t\t\t* 2---创建链队列 *");
printf("\n\t\t\t* 3---进队操作 *");
printf("\n\t\t\t* 4---出对操作 *");
printf("\n\t\t\t* 5---取队头元素 *");
printf("\n\t\t\t* 6---输出链队列元素 *");
printf("\n\t\t\t*********************\n");
printf("请选择菜单号（0-6）
:"); ch=getchar();
switch(ch){
case '0': printf("你确定退出吗（y/n）：");
scanf("%c",&ch); ch=getchar();
if(ch=='y’ ) printf("退出程序\n");
else printf("请继续\n"); getchar(); break;
case '1': InitQueue(Q);getchar();break;
case '2': printf("请输入一个队列以0结束: "); scanf("%d",&e); while(e!=0) { if(EnQueue(Q,e)!=0) scanf("%d",&e); }
printf("链队元素有: \n"); OutQueue(Q); getchar();
break;
case '3': printf("请输入要进队的元素e: "); scanf("%d",&e);
if(e==0) printf("进队失败!\n");
else { EnQueue(Q,e); printf("进队成功!\n"); }
printf("链队元素有: \n");
OutQueue(Q); getchar(); break;
case '4': DeQueue(Q,e); printf("链对元素有: \n");
OutQueue(Q);getchar(); break;
case '5': GetQueue(Q,e);printf("队头元素：%d\n",e);
printf("链对元素有: "); OutQueue(Q); getchar(); break; case '6': printf("链对元素有: \n"); OutQueue(Q); getchar(); break; default : getchar();
printf("输入错误，请重新输入……\n"); } } while(ch!='y');}
2、截取实现程序功能的截图。
如上图。