栈和队列的基本操作技巧.doc

《栈和队列的基本操作技巧.doc》由会员分享，可在线阅读，更多相关《栈和队列的基本操作技巧.doc（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、!-数据结构与算法实验报告专业班级姓名学号实验项目 实验二 栈和队列的基本操作。实验目的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(SqS

4、tack *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）入队函数：

5、将元素逐个输入队列中。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) 空栈建立函数 动态分配内存 判断分配成功并返回相

6、应的值 若成功，初始化存储空间（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) 进制转换函数 输入要转化的十进制数 输入要转化为几进制 运用求余运算改变进制

7、数 运用选择结构控制十六进制的输出方式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返回出队的值

8、（6）int QueueEmpty(SeqQueue *q) 计算队长函数 头指针减尾指针，求队列长度（7）void YangHui(int n) 输出杨辉三角函数 定义变量 循环输出元素1 插入1为队列队尾元素 使用空格控制输出格式 逐个输出队列元素，并构建下一行需输出的队列 运算结果插入队尾实验测试结果及结果分析（一）测试结果（进制转换） （杨辉三角）（二）结果分析 调试程序时，出现了许多错误。如： 有时候写的没有出现问题，但运行的结果是Press anu key to continue 。程序肯定有错，但为什么会出现这种问题呢。分号的忘记那还是很经常的，要加强注意。在做表达式的计算的时候

9、一定要注意何时入栈何时出栈，队列也是同样的。如果如栈与出栈的情况判断不清楚就无法得出答案。在写主函数时，如果是用void main的形式，那么可以不用有返回值，如果是int main的话，要有返回值，既末尾要有return语句。实验总结1.进一步巩固了C语言的基础，尤其是指针那部分；2.通过实验加深了对栈和队列的操作方面知识的认识。更深层次了解了栈和队列的操作特点及不同之处；3.通过实验达到了理论与实践结合的目的，提高了自己的编程能力；4.程序可能不够完善需要在学习过程中不断去完善，这需要平时的努力。附录 实验程序代码一、进制转换#include #include #include #defi

10、ne 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-b

11、ase) /*存储分配失败*/ 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) /*比较栈中元素所占空间与已分配存储空间*/ s-base=(int

12、 *)realloc(s-base,(s-stacksize+STACKINCEREMENT)*sizeof(int); /*栈满，追加存储空间*/ 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

13、; x=*-s-top;/*若栈不空，则删除栈顶元素，用x返回其值*/ return x; /*进制转换函数*/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

14、; 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); break; case 15: printf(F); break; default: printf(%d,x); printf(n);return 0; /*主函数*/ int main() SqStack s; /*定义s为

15、栈类型*/StackInit(&s); conversion(&s); return 0; 二、输出杨辉三角#include #include #include #define MAXSIZE 10 typedef struct SeqQueue/*定义队列*/ int dataMAXSIZE; int front; /*队头指针*/ int rear; /*队尾指针*/ SeqQueue; /*建立空队列函数*/SeqQueue *InitQueue() /*构造一个空队列*/ SeqQueue *q; q=(SeqQueue*)malloc(sizeof(SeqQueue);/*动态分配内

16、存*/ q-front=q-rear=0; return q; /*入队函数*/ void EnQueue(SeqQueue *q,int x)/*插入元素x为队列的新的队尾元素*/ if(q-rear+1)%MAXSIZE=q-front) /*判断队满*/ printf(n顺序循环队列是满的！); else q-dataq-rear=x; q-rear=(q-rear+1)%MAXSIZE; /*出队函数*/int DeQueue(SeqQueue *q)/*若队列不空则删除队头元素，并返回其值*/ int x; if(q-front=q-rear) printf(n顺序队列是空的！不能做

17、删除操作！); return 0; x=q-dataq-front; /*用x返回出队的值*/ q-front=(q-front+1)%MAXSIZE; return x; /*求队列长度函数*/ int QueueEmpty(SeqQueue *q) /*求队列的长度*/ return(q-front-q-rear); /*返回队头函数*/int GetHead(SeqQueue *q)/*用e返回队头元素*/ int e; if(q-front=q-rear) /*队列为空*/ e=0; else e=q-dataq-front; return e; /*输出杨辉三角函数*/void Ya

18、ngHui(int n)/*输出杨辉三角*/ SeqQueue *q; int i,j,a,b; for(i=1;in;i+) printf( ); printf(1n); /*循环输出元素1*/ q=InitQueue(); EnQueue(q,0); EnQueue(q,1); /*插入1为队列队尾元素*/ for(j=1;jn;j+) for(i=1;in-j;i+) printf( ); EnQueue(q,0); while(t!=0); /*逐个输出队列元素，并构建下一行需输出的队列*/ a=DeQueue(q); b=GetHead(q); if(t) printf(%5db); else printf(n); EnQueue(q,a+b); DeQueue(q); printf(%5d,DeQueue(q); while(!QueueEmpty(q) b=DeQueue(q); printf(%5d,b); /*主函数*/void main() int n; printf(请输入杨辉三角的行数：n); scanf(%d,&n); YangHui(n); getchar();printf(n); 序号项目得分总分1实验报告排版(3分)2算法思想分析(6分)3源代码(6分)4实验结果及分析(5分)