栈和队列的基本操作技巧.doc
!-数据结构与算法实验报告专业班级姓名学号实验项目 实验二 栈和队列的基本操作。实验目的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 dataMAXSIZE; 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 <stdio.h> #include <stdlib.h> #include <malloc.h> #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) /*比较栈中元素所占空间与已分配存储空间*/ s->base=(int *)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; 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; 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为栈类型*/StackInit(&s); conversion(&s); return 0; 二、输出杨辉三角#include <stdio.h>#include <stdlib.h> #include <malloc.h> #define MAXSIZE 10 typedef struct SeqQueue/*定义队列*/ int dataMAXSIZE; int front; /*队头指针*/ int rear; /*队尾指针*/ SeqQueue; /*建立空队列函数*/SeqQueue *InitQueue() /*构造一个空队列*/ SeqQueue *q; q=(SeqQueue*)malloc(sizeof(SeqQueue);/*动态分配内存*/ 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顺序队列是空的！不能做删除操作！"); 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 YangHui(int n)/*输出杨辉三角*/ SeqQueue *q; int i,j,a,b; for(i=1;i<n;i+) printf(" "); printf("1n"); /*循环输出元素1*/ q=InitQueue(); EnQueue(q,0); EnQueue(q,1); /*插入1为队列队尾元素*/ for(j=1;j<n;j+) for(i=1;i<n-j;i+) printf(" "); EnQueue(q,0); while(t!=0); /*逐个输出队列元素，并构建下一行需输出的队列*/ a=DeQueue(q); b=GetHead(q); if(t) printf("%5d"b); 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分)
