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

实验二：栈的表示与实现及栈的应用

【实验目的】

（1） 掌握栈的顺序存储结构及其基本操作的实现。

（2） 掌握栈后进先出的特点，并利用其特性在解决实际问题中的应用。 （3） 掌握用递归算法来解决一些问题。 【实验内容】

1. 编写程序，对于输入的任意一个非负十进制整数，输出与其等值的八进

制数。

2. 编写递归程序，实现N！的求解。 3. 编写递归程序，实现以下函数的求解。

n,?Fib(n)???Fib(n?1)?Fib(n?2),n?0,1n?14. 编写程序，实现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 -2 typedef 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; }//InitStack

Status 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;

} //PUSH

Status Pop(SqStack &S, SElemType &e) {

if(S.top==S.base) return ERROR; e=*--S.top; return OK; } //Pop

Status StackEmpty(SqStack S) {

if (S.top==S.base) return OK; else

return ERROR; } //StackEmpty void conversion() { int N; int e; SqStack S; InitStack(S);

printf(\输入要转换的数据：\ scanf(\ while (N) {

Push(S, N % 8); N = N/8;

}

printf(\其对应的八进制数是：\ while (!StackEmpty(S)) {

Pop(S,e); printf ( \ } }

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(\}

3、#include int fib(int n) {