实验
2
栈与队列
|
成绩 |
实验类型：●验证性实验 ○综合性实验 ○设计性实验
一、实验目的或任务
通过指导学生上机实践，对常用数据结构的基本概念及其不同的实现方法的理论得到进一步的掌握，并对在不同存储结构上实现不同的运算方式和技巧有所体会。
二、实验教学基本要求
1.了解实验目的及实验原理；
2.编写程序，并附上程序代码和结果图；
3.总结在编程过程中遇到的问题、解决办法和收获。
三、实验教学的内容或要求
1.编写函数,采用链式存储实现栈的初始化、入栈、出栈操作
2.编写函数,采用顺序存储实现栈的初始化、入栈、出栈操作
3.编写函数,采用链式存储实现队列的初始化、入队、出队操作
4.编写函数,采用顺序存储实现队列的初始化、入队、出队操作
5.编写一个主函数,在主函数中设计一个简单的菜单,分别调试上述算法
四、实验内容
实验代码：
1.栈的进出
#include
using namespace std;
const int StackSize=20;
templatelass DataType>
class SeqStack
{
public:
SeqStack();
~SeqStack(){};
void Push(DataType x);
DataType Pop();
DataType GetTop();
int Empty();
private:
DataType data[StackSize];
int top;
};
template
SeqStack::SeqStack()
{
top=-1;
}
template
void SeqStack::Push(DataType x)
{
if(top==StackSize-1)throw”上溢”;
top++;
data[top]=x;
}
template
DataType SeqStack::Pop()
{
DataType x;
if(top==-1)throw”下溢”;
x=data[top–];
return x;
}
template
DataType SeqStack::GetTop()
{
if
(top!=-1)
return data[top];
}
template
int SeqStack::Empty()
{
if(top==-1)return 1;
else return 0;
}
int main()
{
SeqStackS;
if (S.Empty())
{cout<
}
else
{cout<
}
cout<行入栈操作”<
S.Push(12);
S.Push(11);
cout<
cout<
cout<
S.Pop();
cout<
cout
<
}
2.队列的进出
#include “stdlib.h”
#include “stdio.h”
typedef struct Queue
{
int data;
struc
t 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 OutQueue(LinkQueue Q)
{
if(Q.rear==Q.front)
printf(“队列为空\n”);
Queue*head=Q.front->next;
while(head!=NULL)
{
printf(“%d”,head->data);
prin
tf(“?”);
head=head->next;
}
}
void InitQueue(LinkQueue &Q);
int EnQueue(LinkQueue &Q,int &e);
void DeQueue(LinkQueue &Q,int &e);
void OutQueue(LinkQueue Q);
int main()
{
char ch;
int e;
LinkQueue Q;
do{
ch=getchar();
switch(ch)
{
case ‘1’:
In
itQueue(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();
bre
ak;
case’5′:
printf(“链对元素有:?\n”);
OutQueue(Q);
getchar();
break;
default :
getchar();
printf(“输入错误，请重新输入\
n”);
}
} while(ch!=’y’)
;
}
实验总结：
通过本次实验我巩固了链式存储结构栈的初始化、入栈、出栈操作；链式存储结构队列的初始化、入队、出队操作；顺序存储结果栈的初始化、入栈、出栈操作；顺序存储结构队列的初始化、入队、出队操作；在本次实验中我发现了自己在链式存储结构和顺序存储结构的栈和队列任然存在不足，顺序存储结构既是难点也是重点，在接下来的学习中我也要着重复习一下栈与队列的基本操作。
实验结果：
