.
《数据结构与算法》实验报告
专业
班级
学号
实验项目
实验二 栈和队列的基本操作。
实验目的
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
#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) /*存储分配失败*/
.
栈和队列的基本操作
