山东大学数据结构第二次实验实验报告.doc

实验2 ADT栈与队列的编程与实现

实验目的：加深对抽象数据类型ADT栈和队列的理解；
实验原理：参照课本p.64-66，及Figure3.39-3.44；
课本p.82-83，及Figure3.57-3.60.
实验内容：编写程序实现ADT栈的定义，及常用操作（数组或指针实现）：
1) 生成栈；
2) Push
3) Pop

编写程序实现ADT队列的定义，及常用操作：
1) 生成队列；
2) Enqueues入列；
3) Isempty判断是否队列为空。
实验要求：
1) 实现ADT栈的结构及操作；
2) 实现ADT队列的结构及操作，并给出应用。

1. 栈（链表实现）
实验源程序：
#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"
#include "string.h"
typedef struct node //定义一个栈的结构
{
int data;
struct node *pNext; //pNext为指向栈中下一个空间的指针
}Node,*pNode;
typedef pNode Stack;
Stack InitStack() ; //初始化栈
void CreateStack(Stack Top); //生成栈
bool Empty(Stack Top); //判断栈是否为空
void Push(Stack Top,int n); //进行压栈操作
void Pop(Stack Top); //进行出栈操作
void TraverseStack(Stack Top); //遍历栈的函数
void DeleteStack(Stack Top); //清空栈的函数
int main() //主函数
{
int n;
char str[6]; //定义数组，存储操作指令
Stack Top=NULL; //初始化Top为NULL
Top=InitStack(); //初始化栈
CreateStack(Top); //生成栈
TraverseStack(Top); //遍历栈
printf("请输入下一步操作指令(push,pop or end):");
while(1)
{
scanf("%s",str); //获取操作指令
if(strcmp(str,"push")==0)
{
printf("请输入入栈的元素:");
scanf("%d",&n);
Push(Top,n); //进栈操作
TraverseStack(Top);
printf("请输入下一步操作指令(push,pop or end):");
}
if(strcmp(str,"pop")==0)
{
Pop(Top); //出栈操作
TraverseStack(Top);
printf("请输入下一步操作指令(push,pop or end):");
}
if(strcmp(str,"end")==0)
break; //跳出循环
if(strcmp(str,"push")!=0&&strcmp(str,"pop")!=0&&strcmp(str,"end")!=0)
{
printf("输入指令错误，请重新输入指令:");
}
}
DeleteStack(Top); //释放栈空间
return 0;
}

Stack InitStack() //进行栈的初始化的函数
{
Stack Top = (Stack)malloc(sizeof(Node)); //分配内存空间给栈顶
if(Top==NULL)
{
printf("动态分配内存失败\n");
exit(1);
}
printf("初始化栈成功\n");
Top->pNext = NULL; //栈顶指针的指向置为NULL；
return Top;
}

void CreateStack(Stack Top) //生成栈
{
int LEN,x;
Stack Bottom = Top; //令Top和Bottom指向同一空间
Bottom->pNext = NULL;
printf("请输入想要入栈的元素个数:");
scanf("%d",&LEN);
for(int i = 0; i < LEN; i++)
{
printf("请输入第%d个元素(从栈顶到栈底):",i+1);
scanf("%d",&x);
Stack pNew = (Stack)malloc(sizeof(Node));
pNew->data = x; //将输入的数放在栈data单元中
Bottom->pNext = pNew; //Bottom指向新分配空间的单元
pNew->pNext = NULL; //令pNew指向NULL
Bottom = pNew; //让新分配空间的单元成为栈底
}
printf("生成栈成功\n");
}

bool IsEmpty(Stack Top) // 判断栈是否为空
{
return Top->pNext==NULL;
}

void Push(Stack Top,int n) //进行进栈操作的函数
{
Stack pNew = (Stack)malloc(sizeof(Node)); //定义一个新节点，并分配内存空间
if(pNew==NULL)
{
printf("未能动态分配内存，进栈失败\n");
return ;
}
pNew->data = n;
pNew->pNext = Top->pNext;
Top->pNext = pNew;
}

void Pop(Stack Top) //进行出栈操作函数
{
Stack p=Top->pNext;
if (IsEmpty(Top)==true) //判断栈是否为空，为空就不能进行出栈操作
{
printf("栈为空，Pop失败\n");
return ;
}
else
{
printf("弹出的栈顶元素为:");
printf("%d \n",p->data); //显示出栈元素
Top->pNext=p->pNext;
free(p);
}
}

void TraverseStack(Stack Top) //遍历栈，获取栈中的数值
{
printf("现在栈中的元素从栈顶到栈底依次为:");
Stack p = Top->pNext;
if(p==NULL)printf("栈空");
while(p!=NULL)
{
printf("%d ",p->data);
p = p->pNext;
}
printf("\n");
}

void DeleteStack(Stack Top) //释放栈空间
{
Stack p,q ;
p=Top->pNext;
while (p != NULL)
{
q=p->pNext;
free(p);
p=q;
}
Top->pNext=NULL;
}

实验结果：
1） 生成栈
①初始化栈。

②生成栈成功。

2）Push
输入push，进行入栈操作，得到新的栈序列。

3） Pop
①输入pop，进行出栈操作，弹出栈顶元素9,并且得到新的栈序列。

②如果不断进行pop操作，当栈为空时会出现pop失败。

4)其余操作
①结束进程
输入指令end可以结束进程，不会出现要求输入下一步指令。

②输入错误的指令
若在指令输出端输入错误指令，则要求重新输入指令直到输入正确指令

2. 队列（循环数组实现）
实验源程序：
#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"
#include "string.h"
#define maxsize 11
typedef struct pQueue
{
int queue[maxsize];
int rear; //最后元素的位置
int front; //最前元素的位置的前一个位置
}Aqueue,*Queue;
Queue QueueInit(); //初始化队列
void CreateQueue(Queue Q,int n); //生成队列
int IsFull(Queue Q); //判断队列是否为满
int IsEmpty(Queue Q); //判断队列是否为空
int EnQueue(Queue Q,int x); //入队
int DeQueue(Queue Q); //出队
void TraverseQueue(Queue Q); //遍历队列
int main() //主函数
{
int n,x;
char str[10];
Queue Q=QueueInit(); //初始化队列
printf("请输入想要入队元素个数(小于%d):",maxsize);
while(1)
{
scanf("%d",&n);
if(n<maxsize)break;
printf("请重新输入想要入队元素个数(小于%d):",maxsize);

}
CreateQueue(Q,n); //生成队列
printf("队列中的元素依次为:");
TraverseQueue(Q);
printf("请输入下一步操作指令(Enqueue,Dequeue or end):");
while(1)
{
scanf("%s",str); //获取操作指令
if(strcmp(str,"Enqueue")==0)
{
printf("请输入想要入队的元素:");
scanf("%d",&x);
if(EnQueue(Q,x)) //入队
{
printf("元素%d入队后队列中元素依次为:",x);
TraverseQueue(Q);
}
printf("请输入下一步操作指令(Enqueue,Dequeue or end):");
}
if(strcmp(str,"Dequeue")==0)
{
if(IsEmpty(Q)==0)
{
printf("元素%d出队后队列中元素依次为:",DeQueue(Q));//出队
TraverseQueue(Q);
printf("请输入下一步操作指令(Enqueue,Dequeue or end):");
}
else
{
printf("队列为空,出队失败\n");
printf("请输入下一步操作指令(Enqueue,Dequeue or end):");
}
}
if(strcmp(str,"end")==0)
break; //跳出循环
if(strcmp(str,"Enqueue")!=0&&strcmp(str,"Dequeue")!=0&&strcmp(str,"end")!=0)
{
printf("输入指令错误，请重新输入指令:");
}
}
printf("判断队列是否为空:",x); //判断队列是否为空
if(IsEmpty(Q)==1)
printf("队列为空\n");
else
printf("队列不为空\n");
return 0;
}

Queue QueueInit() //初始化队列
{
Queue Q=(Queue)malloc(sizeof(Aqueue));
if(Q!=NULL)
{
Q->rear=-1;
Q->front=-1;
printf("初始化队列成功\n");
return Q;
}
exit(1);
}

void CreateQueue(Queue Q,int n) //生成队列
{
for(int i=0;i<n;i++)
{
printf("请输入队列中第%d个元素:",i+1);
Q->rear=Q->rear+1;
scanf("%d",&Q->queue[Q->rear]);
}
printf("生成队列成功\n");
}

int IsFull(Queue Q) //判断队列是否为满
{
if(Q->front==-1)
Q->front=maxsize-1;
return (Q->rear+1)%maxsize==Q->front;
}

int IsEmpty(Queue Q) //判断队列是否为空
{
return Q->front==Q->rear;
}

int EnQueue(Queue Q,int x) //入队
{
if(IsFull(Q))
{
printf("队列已满,入队失败\n");
return 0;
}
Q->rear=(Q->rear+1)%maxsize;
Q->queue[Q->rear]=x;
return 1;
}

int DeQueue(Queue Q) //出队
{
Q->front=(Q->front+1)%maxsize;
return Q->queue[Q->front];
}

void TraverseQueue(Queue Q) //遍历队列，获取队列中的数值
{
if(IsEmpty(Q)==1)
{
printf("队列为空\n");
return;
}
int front=Q->front;
int rear=Q->rear;
while (front!=rear)
{
front=(front+1)%maxsize;
printf("%d ",Q->queue[front]);
}
printf("\n");
}

实验结果如下：
实验结果：
1）生成队列；
①初始化队列。

②生成队列成功。

2） Enqueues入列；
操作指令输入Enqueue，将66入列。

3） Isempty判断是否队列为空。
①队列不为空。

②队列为空

4）其他操作
①若输入的元素个数超过数组能接受长度，需重新输入。

②队列为满时，入队失败

③出队操作。

5）ADT队列的应用。
ADT队列的应用实例：
①当多个任务分配给打印机时，为了防止冲突，创建一个队列，把任务入队，按先入先出的原则处理任务。
②当多个用户要访问远程服务端的文件时，也用到队列，满足先来先服务的原则。
③当在公交站排队等待进站时也会用到队列，先到的人先上车，相当于出队，后到的人要先排队，相当于入队。
④CPU的分时系统也用到队列，系统根据请求的时间先后处理它们，而这些请求就相当于在队列中排列等待处理。