xxxx 大学实验报告
课程名称 数据结构 实验项目 实验一 线性结构(二) ——栈和队列的操作
院 系 信息学院计类系 专业班级 计类1501 姓 名 学 号
指导老师 日 期
批改日期 成 绩
一 实验目的 1. 熟练掌握栈的存储结构及相关典型操作。
2. 熟练掌握队列的存储结构及相关典型操作。
二 实验内容及要求
实验内容：
1. 建立链式栈，实现栈的初始化、进栈、出栈等典型操作。
2. 建立循环队列，实现队列的初始化、进队、出队等典型操作。
实验要求： 1. 键盘输入数据；
2. 屏幕输出运行结果。
3. 要求记录实验源代码及运行结果。
4. 运行环境：VC++6.0
三 实验过程及运行结果
1、 循环队列
#include
#include
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAXQSIZE 100 //最大队列长度
typedef struct
{
int *base; //初始化的动态分配存储空间
int front;
int rear;
}SqQueue;
//初始化队列
int InitQueue(SqQueue Q)
{
}
//入队操作
int EnQueue(SqQueue Q)
{
}
//出队操作 int e; if ((Q.rear+1)%MAXQSIZE==Q.front) //判断队满 { } printf("请输入入队元素:"); scanf("%d",&e); Q.base[Q.rear]=e; //入队 Q.rear =(Q.rear+1)%MAXQSIZE; //队尾指针后移 return OK; printf("队列已满, 不能入队\n"); return ERROR; Q.base=(int*)malloc(MAXQSIZE*sizeof(int)); if (!Q.base)exit(OVERFLOW); //存储分配失败 Q.front=Q.rear=0; return OK;
int DeQueue(SqQueue Q)
{
}
//队列长度
int QueueLength(SqQueue Q)
{
}
//队列遍历
int QueueTraverse(SqQueue Q)
{
printf("遍历结果为:"); while (Q.front!=Q.rear) { } printf ("\n"); printf("%d ",Q.base[Q.front]); Q.front=(Q.front+1)%MAXQSIZE; return((Q.rear-Q.front+MAXQSIZE)%MAXQSIZE); int e; if(Q.front==Q.rear) //判断队空 { } e=Q.base[Q.front]; //队头出队 printf("输出的出队元素为:"); printf("%d\n",e); Q.front=(Q.front+1)%MAXQSIZE; //队头下表后移 return OK; printf("队列已为空\n"); return ERROR;
} return OK;
int main()
{
}
2、 链式栈 #include
#include
#define OK 1
#define ERROR 0
#define OVERFLOW -2 int n; SqQueue Q; InitQueue(Q); printf("*输入1为入队*\n"); printf("*输入2为出队*\n"); printf("*输入3为队列长度*\n"); printf("*输入4为遍历*\n"); printf("*输入0为退出*\n"); printf("*****************\n"); while(scanf("%d",&n),n) { } return 0; switch(n) { case 1:EnQueue(Q);break; case 2:DeQueue(Q);break; case 3:printf("队列长度为%d\n",QueueLength(Q));break; case 4:QueueTraverse(Q);break; }
typedef int Status;
typedef int SElemType;
typedef struct node
{
SElemType data;
struct node *next;}SLnode,*SLinkList;
typedef struct
{
SLinkList top,base;
int len;
}S_LinkList;
//栈的初始化
Status Creat_S(S_LinkList &S)
{ int n;
SLinkList p,q;
printf("栈的初始化，请输入数据，以-1结束:\n");
S.top=(SLinkList )malloc(sizeof(SLnode));
S.base=(SLinkList )malloc(sizeof(SLnode));
S.top->next=S.base;
q=S.base;
S.len=0;
while(scanf("%d",&n),n!=-1)
{
p=(SLinkList )malloc(sizeof(SLnode));
p->data=n;
S.top->next=p; p->next=q;
q=p;
S.len++;
}
q=S.top->next;
while(q!=S.base)
{
printf("%d\n",q->data);
q=q->next;
}
printf("*****\n");
return OK;
}
//进栈
Status Push_S(S_LinkList &S)
{
int e;
printf("请输入进栈元素:");
scanf("%d",&e);
SLinkList p,q;
q=S.top->next;
p=(SLinkList )malloc(sizeof(SLnode));
p->data=e;
S.top->next=p;
p->next=q;
q=p;
S.len++;
return OK;
}
//出栈
Status Pop_S(S_LinkList &S)
{
SLinkList p;
p=S.top->next;
if(p!=S.base)
printf("出栈元素为%d\n",p->data);
return OK;
}
int main()
{
S_LinkList s;
int a;
printf("*输入1为栈的初始化*\n");
printf("*输入2为入栈*\n");
printf("*输入3为出栈*\n");
printf("*输入0为退出*\n");
printf("************************\n");
while(scanf("%d",&a),a)
{
switch(a)
{
case 1:Creat_S(s);break;
case 2:Push_S(s);break;
case 3:Pop_S(s);break;
}
}
return 0;
}
四 调试情况、设计技巧及体会
为了避免顺序栈的存储结构所带来的在操作中需要移动大量数据的缺点，采用链栈，具有动态特性，不用设置头结点。队列是一种先进后出带的线性表，一个链队列由头指针和尾指针唯一确定，所以建立链表的时候，需要在对头加一个头结点，头指针指向头结点。