栈和队列的基本操作
- 格式：doc
- 大小：87.00 KB
- 文档页数：10
-
-
- .可修编- 《数据结构与算法》实验报告
专业 班级 学号
实验项目
实验二 栈和队列的基本操作。
实验目的
1、掌握栈的基本操作：初始化栈、判栈为空、出栈、入栈等运算。
2、掌握队列的基本操作：初始化队列、判队列为空、出队列、入队列等运算。
实验容
题目1：
进制转换。利用栈的基本操作实现将任意一个十进制整数转化为R进制整数
算法提示：
1、定义栈的顺序存取结构
2、分别定义栈的基本操作（初始化栈、判栈为空、出栈、入栈等）
3、定义一个函数用来实现上面问题：
十进制整数X和R作为形参
初始化栈
只要X不为0重复做下列动作
将X%R入栈X=X/R
只要栈不为空重复做下列动作
栈顶出栈输出栈顶元素
题目2：
利用队列的方式实现辉三角的输出。
算法设计分析
（一）数据结构的定义
1、栈的应用
实现十进制到其他进制的转换，该计算过程是从低位到高位顺序产生R进制数的各个位数，而打印输出一般从高位到低位进行，恰好与计算过程相反。因此，运用栈先进后出的性质，即可完成进制转换。
栈抽象数据结构描述
typedef struct SqStack /*定义顺序栈*/
{
int *base; /*栈底指针*/
int *top; /*栈顶指针*/
int stacksize; /*当前已分配存储空间*/
} SqStack; -
-
- .可修编-
2、队列的应用
由于是要打印一个数列，并且由于队列先进先出的性质，肯定要利用已经进队的元素在其出队之前完成辉三角的递归性。即，利用要出队的元素来不断地构造新的进队的元素，即在第N行出队的同时，来构造辉三角的第N+1行，从而实现打印辉三角的目的。
队列抽象数据结构描述
typedef struct SeqQueue
{
int data[MAXSIZE];
int front; /*队头指针*/
int rear; /*队尾指针*/
}SeqQueue;
（二）总体设计
1、栈
（1）主函数：统筹调用各个函数以实现相应功能
int main()
（2）空栈建立函数：对栈进行初始化。
int StackInit(SqStack *s)
（3）判断栈空函数：对栈进行判断，若栈中有元素则返回1，若栈为空，则返回0。
int stackempty(SqStack *s)
（4）入栈函数：将元素逐个输入栈中。
int Push(SqStack *s,int x)
（5）出栈函数：若栈不空，则删除栈顶元素，并用x返回其值。
int Pop(SqStack *s,int x)
（6）进制转换函数：将十进制数转换为R进制数
int conversion(SqStack *s)
2、队列
（1）主函数：统筹调用各个函数以实现相应功能
void main()
（2）空队列建立函数：对队列进行初始化。
SeqQueue *InitQueue()
（3）返回队头函数： 判断队是否为空，若不为空则返回队头元素。
int QueueEmpty(SeqQueue *q)
（4）入队函数：将元素逐个输入队列中。
void EnQueue(SeqQueue *q,int x)
（5）出队函数：若队列不空，则删除队列元素，并用x返回其值。
int DeQueue(SeqQueue *q)
（6）计算队长函数：计算队列的长度。
int QueueEmpty(SeqQueue *q)
（7）输出辉三角函数：按一定格式输出辉三角。
void YangHui(int n)
-
-
- .可修编- （三）各函数的详细设计：
1、栈
（1）int main()主函数
定义s为栈类型
调用函数建立空栈
调用进制转换函数
返回0值
（2）int StackInit(SqStack *s) 空栈建立函数
动态分配存
判断分配成功并返回相应的值
若成功，初始化存储空间
（3）int stackempty(SqStack *s) 判断栈空函数
若栈为空，返回0，否则返回1
（4）int Push(SqStack *s,int x) 入栈函数
比较栈中元素所占空间与已分配存储空间
若栈满，追加存储空间
若存储失败则返回0
存储空间不够，添加增量
逐个输入数据元素
返回x的值
（5）int Pop(SqStack *s,int x) 出栈函数
如果栈为空，则返回0
若栈不空，则删除栈顶元素，用x返回其值
（6）：int conversion(SqStack *s) 进制转换函数
输入要转化的十进制数
输入要转化为几进制
运用求余运算改变进制数
运用选择结构控制十六进制的输出方式
2、队列
（1）void main()主函数
输入辉三角的行数
调用辉三角输出函数
输出辉三角
（2）SeqQueue *InitQueue()空队列建立函数
动态分配存
建立队列并返还该队列
（3）int QueueEmpty(SeqQueue *q) 返回队头函数
判断队列为空，返回0
若不空返回队头元素
（4）void EnQueue(SeqQueue *q,int x) 入队函数
判断队满
若不满，逐个添加元素
（5）int DeQueue(SeqQueue *q) 出队函数
-
-
- .可修编- 若头指针等于尾指针，顺序队列是空的不能做删除操作
否则，删除队列
用x返回出队的值
（6）int QueueEmpty(SeqQueue *q) 计算队长函数
头指针减尾指针，求队列长度
（7）void YangHui(int n) 输出辉三角函数
定义变量
循环输出元素1
插入1为队列队尾元素
使用空格控制输出格式
逐个输出队列元素，并构建下一行需输出的队列
运算结果插入队尾
实验测试结果及结果分析
（一）测试结果
（进制转换）
（辉三角）
- -
- .可修编-
（二）结果分析
调试程序时，出现了许多错误。如： 有时候写的没有出现问题，但运行的结果是Press anu
key to continue 。程序肯定有错，但为什么会出现这种问题呢。分号的忘记那还是很经常的，要加强注意。在做表达式的计算的时候一定要注意何时入栈何时出栈，队列也是同样的。如果如栈与出栈的情况判断不清楚就无法得出答案。在写主函数时，如果是用void main的形式，那么可以不用有返回值，如果是int main的话，要有返回值，既末尾要有return语句。
实验总结
1.进一步巩固了C语言的基础，尤其是指针那部分；
2.通过实验加深了对栈和队列的操作方面知识的认识。更深层次了解了栈和队列的操作特点及不同之处；
3.通过实验达到了理论与实践结合的目的，提高了自己的编程能力；
4.程序可能不够完善需要在学习过程中不断去完善，这需要平时的努力。
附录 实验程序代码
一、进制转换
#include
#include
#include
#define STACK_INIT_SIZE 100 /*存储空间初始分配量*/
#define STACKINCEREMENT 10 /*存储空间分配增量*/
typedef struct SqStack /*定义顺序栈*/
{ int *base; /*栈底指针*/
int *top; /*栈顶指针*/
int stacksize; /*当前已分配存储空间*/
} SqStack;
/*建立空栈函数*/
int StackInit(SqStack *s) /*构造一个空栈*/
{ s->base=(int *)malloc(STACK_INIT_SIZE *sizeof(int));/*动态分配存*/
if(!s->base) /*存储分配失败*/
return 0; -
-
- .可修编- s->top=s->base;
s->stacksize=STACK_INIT_SIZE; /*初始化存储空间*/
return 1;
}
/*判断栈空函数*/
int stackempty(SqStack *s) /*判断栈是否为空*/
{ if(s->top==s->base)
{ return 1; }
else
{ return 0; }
}
/*入栈函数 */
int Push(SqStack *s,int x) /*入栈，插入x为新的栈顶元素*/
{ if(s->top-s->base>=s->stacksize) /*比较栈中元素所占空间与已分配存储空间*/
{
