栈的表示与实现及栈的应用实验报告.doc

实验二：栈的表示与实现及栈的应用【实验目的】（1） 掌握栈的顺序存储结构及其基本操作的实现。（2） 掌握栈后进先出的特点，并利用其特性在解决实际问题中的应用。（3） 掌握用递归算法来解决一些问题。【实验内容】1. 编写程序，对于输入的任意一个非负十进制整数，输出与其等值的八进制数。2. 编写递归程序，实现N！的求解。3. 编写递归程序，实现以下函数的求解。4. 编写程序，实现Hanoi塔问题。【实验步骤】1.打开VC+。2.建立工程：点File-New，选Project标签，在列表中选Win32 Console Application，再在右边的框里为工程起好名字，选好路径，点OK-finish。至此工程建立完毕。 3.创建源文件或头文件：点File-New，选File标签，在列表里选C+ Source File。给文件起好名字，选好路径，点OK。至此一个源文件就被添加到了你刚创建的工程之中。 4写好代码 5编译链接调试 1、#include #include #include #define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;typedef int SElemType;#define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct SElemType *base; SElemType *top; int stacksize; SqStack; Status InitStack(SqStack &S) S.base=(SElemType *)malloc (STACK_INIT_SIZE*sizeof(SElemType); if (!S.base) return OVERFLOW; S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK;/InitStackStatus Push(SqStack &S, SElemType e) if (S.top-S.base=S.stacksize) S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT) *sizeof(SElemType); if (!S.base) exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; return OK; /PUSHStatus Pop(SqStack &S, SElemType &e) if(S.top=S.base) return ERROR; e=*-S.top; return OK; /PopStatus StackEmpty(SqStack S) if (S.top=S.base) return OK; else return ERROR; /StackEmptyvoid conversion()int N;int e;SqStack S; InitStack(S); printf(输入要转换的数据：); scanf(%d,&N);while (N) Push(S, N % 8);N = N/8; printf(n其对应的八进制数是：); while (!StackEmpty(S) Pop(S,e); printf ( %d, e );void main()conversion();2、#include Int fact(int n)If(n=1)return 1;else return n*fact(n-1);void main()Int n;printf(“输入一个数n:”);scanf(“%d”,&n);printf(fact(%d)=%dn,n,fact(n);3、#include int fib(int n)if(n1)return fib(n-1)+fib(n-2);elsereturn n;void main()int n;printf(n输入一个数n:);scanf(%d,&n);printf(fib(%d)=%dn,n,fib(n);4、#include void move(char x,int n,char z)printf(将%d号盘从%c柱移到%c柱n,n,x,z);void hanoi (int n, char x, char y, char z) if (n=1) move(x,1,z); else hanoi(n-1, x, z, y); move(x, n, z); hanoi(n-1, y, x, z); void main()int n;scanf(%d,&n);hanoi(n,x,y,z);【实验心得】这节课的实验内容是栈的表示与实现及栈的应用。与上节课不同的是,在上机之前，老师先给我们讲解了上机思路，演示了上机步骤。在老师的引导下，同学们很快的进入状态，编写代码，调试程序，遇到解决不了的问题时，大家都积极主动的请教老师，都很快的完成了任务。通过这次上机实验，首先我更加认识到了自己动手的重要性，因为有些问题我们看起来很简单，但是等到亲自去实践时，你会发现出现很多问题。正是通过不断的发现问题、解决问题，我们才能更加深刻的领悟到问题的核心，进而更好