数据结构C语言版实验三报告

一、实验目的

1、掌握栈的储存结构的表示和实现方法。

2、掌握栈的入栈和出栈等基本操作算法实现。

3、了解栈在解决实际问题中的简单应用。

二、实验内容

1、建立顺序栈，并在顺序栈上实现入栈和出栈操作（验证性内容）。

2、建立链栈，并在链栈上实现入栈和出栈操作（设计性内容）。

3、实现汉诺塔求解问题（应用性设计内容）。

三、验证性实验

1、实验要求

编程实现如下功能：

（1）根据输入的栈中元素个数n和各元素值建立一个顺序栈，并输出栈中各元素值。

（2）将数据元素e入栈，并输出入栈后的顺序栈中各元素值。

（3）将顺序栈中的占顶元素出栈，并输出出栈元素的值和出栈后顺序栈中各元素值。

四、设计性实验

编程实现链栈的入栈和出栈操作。

1、实验要求

(1)根据输入的占中元素个数和各元素值建立一个链栈，并输出链栈中各元素值，观察输入的内容与输出的内容是否一致，特别注意栈顶元素的位置。

(2)将数据元素_入栈，并输出入栈后的链栈中各元素值。

(3)将链栈中的栈顶元素出栈，并输出栈元素的值和出栈后链栈中各元素值。

五、应用性设计实验

编程实现汉诺塔求解问题

1、实验要求

假设有三个命名为_、Y和Z的塔座，在塔座_上插有n个直径大小个不相同且从小到大编号为1、2、……,n的圆盘。现要求将塔座_上的n个圆盘借助于塔座Y移至塔座Z上，并仍按同样顺序叠排。圆盘移动时必须遵循下列规则：

（1）每次只能移动一个圆盘；

（2）圆盘可以插在_、Y和Z中的任何一个塔座上；

附上编译成功代码：

验证性实验：

include

include

defineERROR0

defineOK1

definestack_init_size100

definestackincrement10

typedefstruct{

intbase;

inttop;

intstacksize;

}SqStack;

intInitStack(SqStacks)

XXX(int)malloc(stack_init_sizesizeof(int));

if(!XXX)

returnERROR;

s.top=XXX;

XXX;

returnOK;

intPush(SqStacks,inte)

if(s.top-XXX>=XXX)

XXX(int)realloc(XXX,(XXX+stackincrement)sizeof(int));if(!XXX)

returnERROR;

XXX=XXX+XXX;

XXX+=stackincrement;

XXX;

returnOK;

intPop(SqStacks,inte)

if(XXX==XXX)

returnERROR;

e=XXX;

returnOK;

voiddisplay(SqStacks)

for(XXX;XXX!=XXX;XXX)

printf("%d",XXX);

printf("%d ",XXX);

voidmain()

SqStacks;

inti=-1;

InitStack(s);

printf("endof0: ");

for(;;)

scanf("%d",i);

if(i==0)

break;

Push(s,i);

printf("newstack: ");

display(s);

getchar();

getchar();

Pop(s,i);

printf("%d ",i);

display(s);

设计性试验：

include

include

defineERROR0

defineOK1

typedefstructSNode{

intdata;

structSNodene_t;

}SNode,LinkStack;

intPush(LinkStacktop,inte){

LinkStackp;

p=(LinkStack)malloc(sizeof(SNode));p->data=e;

p->ne_t=top->ne_t;

top->ne_t=p;

returnOK;

intPop(LinkStacktop,inte){

LinkStackp;

p=top->ne_t;

if(!p->ne_t)

returnERROR;

e=p->data;

top->ne_t=p->ne_t;

free(p);

returnOK;

voiddisplay(LinkStacktop)

for(top=top->ne_t;top->ne_t;top=top->ne_t)printf("%d",top->data);printf("%d ",top->data);

voidmain()

LinkStacktop;

top=(LinkStack)malloc(sizeof(SNode));top->ne_t=NULL;

inti=-1,j;

printf("endof0: ");

for(;;)

scanf("%d",i);

if(i==0)

break;

Push(top,i);

display(top);

Pop(top,j);

printf("%d ",j);

display(top);

应用性设计实验:

include

voidmove(char_,intn,charz)

printf("%c->%c ",_,z);

voidhanoi(intn,char_,chary,charz){

if(n==1)

move(_,1,z);

else

hanoi(n-1,_,z,y);

move(_,n,z);

hanoi(n-1,y,_,z);

voidmain(void)

{}intn=3;char_,y,z;_='a';y='b';z='c';hanoi(n,_,y,z);