实验二 栈和队列的操作与应用

实验二 栈和队列的操作与应用

【实验目的】

1．熟练掌握栈和队列的特点

2．掌握栈的定义和基本操作，熟练掌握顺序栈的操作及应用

3．掌握对列的定义和基本操作，熟练掌握链式队列的操作及应用, 掌握环形队列的入队和出队等基本操作

4． 加深对栈结构和队列结构的理解，逐步培养解决实际问题的编程能力1．掌握线性表的两类存储结构（顺序存储结构和链式存储结构）的描述方法。

【实验内容】

1．定义顺序栈，完成栈的基本操作：空栈、入栈、出栈、取栈顶元素;

2．实现十进制数与八进制数的转换，十进制数与十六进制数的转换和任意进制之间的转换;

3．定义链式队列，完成队列的基本操作：入队和出队;·

··1 亲亲1··················11112

【实验指导】

1.利用栈的顺序存储结构,设计一组输入数据（假定为一组整数），能够对顺序栈进行如下操作：

（1） 初始化一个空栈，分配一段连续的存储空间，且设定好栈顶和栈底; （2）完成一个元素的入栈操作，修改栈顶指针; （3）完成一个元素的出栈操作，修改栈顶指针; （4）读取栈顶指针所指向的元素的值;

（5） 将十进制数N 和其它d 进制数的转换是计算机实现计算的基本问题，其解决方案很多，其中最简单方法基于下列原理：即除d 取余法。例如：（1348）10=（2504）8

N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2

从中我们可以看出，最先产生的余数4 是转换结果的最低位，这正好符合栈的特性即后进先出的特性。所以可以用顺序栈来模拟这个过程。以此来实现十进制数与八进制数的转换，十进制数与十六进制数的转换;

（6）编写主程序，实现对各不同的算法调用。 2.程序组织

（1）首先将顺序栈存储结构定义放在一个头文件：如取名为SqStackDef.h。

（2）将顺序栈的基本操作算法也集中放在一个文件之中，如取名为SqStackAlgo.h 。如：InitStack、DestroyStack、ClearStack、StackEmpty、StackLength、GetTop、Push、Pop等。

（3）将函数的测试和主函数组合成一个文件，如取名为SqStackUse.cpp。

3.利用队列的链式存储结构,设计一组输入数据（假定为一组整数），能够对链式队列进行如下操作：

（1）初始化一个空队列，形成一个带表头结点的空队; （2）完成一个元素的入队操作，修改队尾指针; （3） 完成一个元素的出队操作，修改队头指针; （4）修改主程序，实现对各不同的算法调用。 4.程序组织

（1）首先将链式队列的存储结构定义放在一个头文件：如取名为LinkQueueDef.h。 （2）将链式队列的基本操作算法也集中放在一个文件之中，如取名为LinkQueueAlgo.h。如：InitQueue、DestroyQueue、ClearQueue、QueueEmpty、QueueLength、GetHead_Q、EnQueue、DeQueue、QueueTraverse等。

（3）将函数的测试和主函数组合成一个文件，如取名为LinkQueueUse.cpp。

长春大学计算机科学技术学院实验报告

日期_______________ 地点______________ 指导教师_____________ 成绩

实验二 栈和队列的操作与应用

要求：

1.完成算法填空，并上机运行调试。 2.将运行结果粘贴在指定处。

3.将完成的实验报告单独建立一个新文件，命名为：班级+学号+姓名+（实验二），（如：1340538张三（实验二）），发邮件到：ccujsjzl@163.com。

一、顺序栈，对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数 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 的元素个数，即栈的长度*/

int a;

a=(S.top-S.base)+1;

编写此函数 return a ; }

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(\;

scanf(\; /* 输入非负十进制整数n */ while(n) /* 当n 不等于0 */ {

n= n%8 ; /* 入栈n 除以8 的余数(8 进制的低位) */ S.base =n ; }

while(!StackEmpty(s)) /* 当栈不空*/ {

e*=S.top ; /* 弹出栈顶元素且赋值给e */ printf(\; /* 输出e */ }

printf(\; }

3．在SqStackUse.cpp 文件中，测试算法的调用，其中间接调用了顺序栈的其他基本算法。

typedef int SElemType; /* 定义栈元素类型为整型*/

#include \常量定义与系统函数原型声明，与实验一中的相同*/ #include \采用顺序栈的类型定义*/ #include \利用顺序栈的基本操作*/ void main()

{ conversion10_8(); /* 十进制数到八进制转换的验证*/ }

运行结果：

请将运行结果粘贴在此处

本文来源：https://www.bwwdw.com/article/vg93.html