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