数据结构实验
长春大学计算机学院网络工程专业
数据结构实验报告
实验名称：实验二栈和队列的操作与应用
班级：网络14406 姓名：李奎学号：041440624
实验地点：日期：
一、实验目的：
1．熟练掌握栈和队列的特点。
2．掌握栈的定义和基本操作，熟练掌握顺序栈的操作及应用。
3．掌握链队的入队和出队等基本操作。
4．加深对栈结构和队列结构的理解，逐步培养解决实际问题的编程能力。
二、实验内容、要求和环境：
注：将完成的实验报告重命名为：班级+学号+姓名+（实验二），（如：041340538张三（实验二）），发邮件到：ccujsjzl@https://www.wendangku.net/doc/1017656683.html,。提交时限：本次实验后24小时之内。
阅读程序，完成填空，并上机运行调试。
1、顺序栈，对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数
(1)文件SqStackDef. h 中实现了栈的顺序存储表示
#define STACK_INIT_SIZE 10 /* 存储空间初始分配量*/
#define STACKINCREMENT 2 /* 存储空间分配增量*/
typedef struct SqStack
{
SElemType *base; /* 在栈构造之前和销毁之后，base 的值为NULL */
SElemType *top; /* 栈顶指针*/
int stacksize; /* 当前已分配的存储空间，以元素为单位*/
}SqStack; /* 顺序栈*/
(2)文件SqStackAlgo.h 中实现顺序栈的基本操作（存储结构由SqStackDef.h 定义）
Status InitStack(SqStack &S)
{ /* 构造一个空栈S */
S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S.base)
exit(OVERFLOW); /* 存储分配失败*/
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
}
int StackLength(SqStack S)
{ // 返回S 的元素个数，即栈的长度, 编写此函数
return(S.top-S.base);
}
Status Push(SqStack &S,SElemType e)
{ /* 插入元素e 为新的栈顶元素*/
if(S.top-S.base>=S.stacksize) /* 栈满，追加存储空间*/
{
S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)
*sizeof(SElemType));
if(!S.base)
exit(OVERFLOW); /* 存储分配失败*/
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*(S.top)++=e;
return OK;
}
Status Pop(SqStack &S,SElemType &e)
{ /* 若栈不空，则删除S 的栈顶元素，用e 返回其值，并返回OK;否则返回ERROR */ if(S.top==S.base)
return ERROR;
e=*--S.top;
return OK;
}
Status StackEmpty(SqStack S)
{ /* 若栈S 为空栈，则返回TRUE，否则返回FALSE */
if(S.top==S.base)
return TRUE;
else
return FALSE;
}
void conversion10_8( )
{ /* 对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数*/ SqStack s;
unsigned n; /* 非负整数*/
SElemType e;
InitStack(s); /* 初始化栈*/
printf("Enter an number(>=0): ");
scanf("%u",&n); /* 输入非负十进制整数n */
while(n) /* 当n 不等于0 */
{
Push(s,n%8);/* 入栈n 除以8 的余数(8 进制的低位) */
n=n/8;
}
while(!StackEmpty(s)) /* 当栈不空*/
{
Pop(s,e); /* 弹出栈顶元素且赋值给e */
printf("%d",e); /* 输出e */
}
printf("\n");
}
(3)在SqStackUse.cpp 文件中，测试算法的调用，其中间接调用了顺序栈的其他基本算法。
typedef int SElemType; /* 定义栈元素类型为整型*/
#include "pubuse.h" /* 常量定义与系统函数原型声明，与实验一中的相同*/
#include "SqStackDef.h" /* 采用顺序栈的类型定义*/
#include "SqStackAlgo.h" /* 利用顺序栈的基本操作*/
void main()
{ conversion10_8(); /* 十进制数到八进制转换的验证*/
}
2、链式队列，利用队列的链式存储结构,设计一组输入数据（假定为一组整数），能够对链式队列进行如下操作：
. 初始化一个空队列，形成一个带表头结点的空队;
. 完成一个元素的入队操作，修改队尾指针;
. 完成一个元素的出队操作，修改队头指针;
(1)文件LinkQueue.h 中实现单链队列－－队列的链式存储结构的表示。
typedef struct QNode
{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
QueuePtr front,rear; /* 队头、队尾指针*/
}LinkQueue;
(2)文件LinkQueueAlgo.h 中实现的链队列的基本算法，其存储结构由LinkQueueDef.h 定义。
Status InitQueue(LinkQueue &Q)
{ /* 构造一个空队列Q */
Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
if(!Q.front)
exit(OVERFLOW);
Q.front->next=NULL;
return OK;
}
int QueueLength(LinkQueue Q)
{ /* 求队列的长度*/
int i=0;
QueuePtr p;
p=Q.front;
while(Q.rear!=p)
{
i++;
p=p->next;
}
return i;
}
Status EnQueue(LinkQueue &Q,QElemType e)
{ /* 插入元素e 为Q 的新的队尾元素*/
QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
if(!p) /* 存储分配失败*/
exit(OVERFLOW);
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return OK;
}
Status DeQueue(LinkQueue &Q,QElemType &e)
{ /* 若队列不空,删除Q 的队头元素,用e 返回其值,并返回OK,否则返回ERROR */ QueuePtr p;
if(Q.front==Q.rear)
return ERROR;
p=Q.front->next;
e= p->data;
Q.front->next=p->next;
if(Q.rear==p)
Q.rear=Q.front;
free(p);
return OK;
}
(3)文件LinkQueueUse.cpp 中包含检验LinkQueueAlgo.h 中关于链式队列基本操作的声明、测试数据和主函数。
#include "pubuse.h" /* 与实验一的意义相同*/
typedef int QElemType; /* 假设链式队列中的结点是一组整数*/ #include "linkqueue.h"
#include "linkqueuealgo.h"
void main()
{ //编写主函数
LinkQueue Q;
int i,j;
QElemType x;
InitQueue(Q);//构建队列
while(i) //给队列插入元素
{
printf("请输入队列插入元素：");
scanf("%d",&j);
EnQueue(Q,j);
printf("停止插入请按0,输入其他数据继续插入:");
scanf("%d",&i);
}
printf("队列的长度为:%d\n",QueueLength(Q));
printf("输出队列：\n");
while (Q.front!=Q.rear) //输出队列数据
{ DeQueue(Q,x);
printf("%d\t",x);
}
}
三、实验结果与分析：(注：请将运行结果粘贴在下面)
1.
结果分析：此实验的目的是让我们输入一个十进制的数，然后通过栈来将其转化为八进制的数，主要是利用到了栈的先进后出的特点来完成的，因此得到了以上的结果，输
入了一个十进制的数据89，最后得到了八进制的131，实验结果如上图所示：2．
结果分析：本实验的目的是让我们能够掌握队列的初始化，入队和出对的操作，我对本次实验的输出结果进行了一点改动，实验要求只让我们对一个元素进行入队和出队的操作，为
了完善实验，我将程序改成了可以自己控制输入多少数据，并且能够显示出有多少个
数据并将其打印出来，实验结果如上图所示：
四、思考题：
1.用带尾指针的循环单链表表示队列，写出入队、出队的算法。
2.回文判断。（参考教材P110实习题1）
五、教师评语：
实验成绩：教师：（签名）年月日
创新活动