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

实验三

一、实验目的

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

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

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

二、实验内容

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

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

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

三、验证性实验

1、实验要求

编程实现如下功能：

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

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

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

四、设计性实验

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

1、实验要求

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

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

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

五、应用性设计实验

编程实现汉诺塔求解问题

1、实验要求

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

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

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

附上编译成功代码：

验证性实验：

#include<stdio.h>

#include<malloc.h>

#define ERROR 0

#define OK 1

#define stack_init_size 100

#define stackincrement 10

typedef struct{

int *base;

int *top;

int stacksize;

}SqStack;

int InitStack(SqStack &s)

{

s.base=(int*)malloc(stack_init_size*sizeof(int));

if(!s.base)

return ERROR;

s.top=s.base;

s.stacksize=stack_init_size;

return OK;

}

int Push(SqStack &s,int e)

{

if(s.top-s.base>=s.stacksize)

{

s.base=(int*)realloc(s.base,(s.stacksize+stackincrement)*sizeof(int)); if(!s.base)

return ERROR;

s.top=s.base+s.stacksize;

s.stacksize+=stackincrement;

}

*s.top++=e;

return OK;

}

int Pop(SqStack &s,int &e)

{

if(s.top==s.base)

return ERROR;

e=*--s.top;

return OK;

}

void display(SqStack s)

{

for(s.top--;s.top!=s.base;s.top--)

printf("%d ",*s.top);

printf("%d\n",*s.top);

}

void main()

{

SqStack s;

int i=-1;

InitStack(s);

printf("end of 0:\n");

for(;;)

{

scanf("%d",&i);

if(i==0)

break;

Push(s,i);

}

printf("new stack:\n");

display(s);

getchar();

Pop(s,i);

printf("%d\n",i);

display(s);

}

设计性试验：

#include<stdio.h>

#include<malloc.h>

#define ERROR 0

#define OK 1

typedef struct SNode{

int data;

struct SNode *next;

}SNode,*LinkStack;

int Push(LinkStack &top,int e) {

LinkStack p;

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

p->next=top->next;

top->next=p;

return OK;

}

int Pop(LinkStack &top,int &e) {

LinkStack p;

p=top->next;

if(!p->next)

return ERROR;

e=p->data;

top->next=p->next;

free(p);

return OK;

}

void display(LinkStack top)

{

for(top=top->next;top->next;top=top->next) printf("%d ",top->data); printf("%d\n",top->data);

}

void main()

{

LinkStack top;

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

int i=-1,j;

printf("end of 0:\n");

for(;;)

{

scanf("%d",&i);

if(i==0)

break;

Push(top,i);

}

display(top);

Pop(top,j);

printf("%d\n",j);

display(top);

}

应用性设计实验:

#include<stdio.h>

void move(char x,int n,char z)

{

printf("%c->%c\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(void)

{ } int n=3; char x,y,z; x='a'; y='b'; z='c'; hanoi(n,x,y,z);

第二篇：数据结构C语言版顺序栈上机实验

实验 3-1 链栈

[目的] 掌握链栈的实现和简单的应用。

[源代码]

/**************************************************** @title: 数据结构实验

@name: <实验3-1> 栈的链式存储结构

@object:

[实验目的]

采用链式存储结构实现栈的基本操作

[实验提示]

1. 在stack.h中实现栈的基本操作，

在链式存储结构中可是省去头结点。

2. 在dsp0301.cpp中编写适当的代码，进行测试 @include:

stack.h [*]

栈的链式实现

@usage:

请查看"TO-DO列表",根据要求完成代码

@copyright: BTC 2004, Zhuang Bo

@author: Zhuang Bo

@date: 2004

@description:

*****************************************************/

#include <stdio.h>

#include <stdlib.h> //for system()

#include "stack.h" //链栈

//测试链栈的主程序

int main()

{

LinkStack s;

int x;

//输入若干正整数以0结束，依次入栈，然后依次出栈并打印 InitStack(s);

printf("输入若干正整数以0结束:");

scanf("%d",&x);

while(x!=0) {

Push(s,x);

scanf("%d",&x);

}

printf("\n出栈结果:");

while(!StackEmpty(s)) {

Pop(s,x);

printf("%4d",x);

}

//-------------------------------------

// TODO (#1#): 其它测试程序

//-------------------------------------

DestroyStack(s); //销毁栈

system("PAUSE");

return 0;

}

Name: 栈的链式实现

Author:

Date:

Description:

#ifndef STACK_H_INCLUDED

#define STACK_H_INCLUDED

#include "ds.h" //for Status,OK ...

#ifndef ElemType

#define ElemType int /* 数据元素类型默认为 int */ #define ELEMTYPE_TAG

#endif

///////////////////////////////////////////////////////////

//链栈的存储结构定义

typedef struct LNode {

ElemType data;

struct LNode *next;

} LNode, *LinkList;

typedef LinkList LinkStack; //链栈类型

///////////////////////////////////////////////////////////

//链栈的基本操作声明

//构造一个空栈S

Status InitStack(LinkStack &S);

//销毁栈S

Status DestroyStack(LinkStack &S);

//将栈S清空

Status ClearStack(LinkStack &S);

//若栈S为空返回TRUE，否则FALSE Status StackEmpty(LinkStack S);

//返回栈S中的元素个数

int StackLength(LinkStack S);

//用e返回栈顶元素

// 前提：栈S存在且不空

Status GetTop(LinkStack S, ElemType &e); //元素e入栈S

Status Push(LinkStack &S, ElemType e);

//S出栈用e返回出栈元素

// 前提：栈S存在且不空

Status Pop(LinkStack &S, ElemType &e);

///////////////////////////////////////////////////////////

//链栈的基本操作的实现

//构造一个空栈S

Status InitStack(LinkStack &S)

{

// TODO (#1#): 构造一个空栈S，不带头结点 return ERROR;

//-------------------------------------

}

//销毁栈S

Status DestroyStack(LinkStack &S)

{

// TODO (#1#):销毁栈S，相当于清空栈 return ERROR;

//-------------------------------------

}

//将栈S清空

Status ClearStack(LinkStack &S)

{

// TODO (#1#): 将栈S清空，释放所有结点 return ERROR;

//-------------------------------------

}

//若栈S为空返回TRUE，否则FALSE

Status StackEmpty(LinkStack S)

{

// TODO (#1#): 若栈S为空返回TRUE，否则FALSE return TRUE;

//-------------------------------------

}

//返回栈S中的元素个数

int StackLength(LinkStack S)

{

// TODO (#1#): 返回栈S中的元素个数

return 0;

//-------------------------------------

}

//用e返回栈顶元素

// 前提：栈S存在且不空

Status GetTop(LinkStack S, ElemType &e)

{

// TODO (#1#):若栈S不空，则用e返回栈顶元素 return ERROR;

//-------------------------------------

}

//元素e入栈S

Status Push(LinkStack &S, ElemType e)

{

// TODO (#1#): 插入元素e作为新的栈顶

return ERROR;

//-------------------------------------

}

//S出栈用e返回出栈元素

// 前提：栈S存在且不空

Status Pop(LinkStack &S, ElemType &e)

{

// TODO (#1#):若栈S不空，则删除栈顶元素用e返回 return ERROR;

//-------------------------------------

}

#ifdef ELEMTYPE_TAG

#undef ElemType

#undef ELEMTYPE_TAG

#endif

实验 3-2 顺序栈

[目的] 掌握顺序栈的实现和简单的应用。

[源代码]

/**************************************************** @title: 数据结构实验

@name: <实验3-2> 栈的顺序存储结构

@object:

[实验目的]

采用顺序存储结构实现栈的基本操作

[实验提示]

1. 在stack.h中实现栈的基本操作

2. 在dsp0302.cpp中编写适当的代码，进行测试 @include:

stack.h [*]

栈的顺序实现

@usage:

请查看"TO-DO列表",根据要求完成代码

@copyright: BTC 2004, Zhuang Bo

@author: Zhuang Bo

@date: 2004

@description:

*****************************************************/

#include <stdio.h>

#include <stdlib.h> //for system()

#include "stack.h" //for SqStack

//测试顺序栈的主程序

int main()

{

SqStack s;

int x;

//输入若干正整数以0结束，依次入栈，然后依次出栈并打印 InitStack(s);

printf("输入若干正整数以0结束:");

scanf("%d",&x);

while(x!=0) {

Push(s,x);

scanf("%d",&x);

}

printf("\n出栈结果:");

while(!StackEmpty(s)) {

Pop(s,x);

printf("%4d",x);

}

//-------------------------------------

// TODO (#1#): 其它测试程序

//-------------------------------------

DestroyStack(s); //销毁栈

system("PAUSE");

return 0;

}

Name: 顺序栈的实现

Author:

Date:

Description:

#ifndef STACK_H_INCLUDED

#define STACK_H_INCLUDED

#include "ds.h" //for Status,OK ...

#ifndef ElemType

#define ElemType int /* 数据元素类型默认为 int */

#define ELEMTYPE_TAG

#endif

#define SElemType ElemType

///////////////////////////////////////////////////////////

//顺序栈的存储结构定义

#define STACK_INIT_SIZE 100 /* 存储空间初始分配容量 */ #define STACKINCREMENT 10 /* 存储空间分配的增量 */ typedef struct {

ElemType *base; //在构造栈之前和销毁栈之后，base为NULL ElemType *top; //栈顶指针

int stacksize; //当前已分配的存储空间(元素个数)

} SqStack;

///////////////////////////////////////////////////////////

//顺序栈的基本操作声明

//构造一个空栈S

Status InitStack(SqStack &S);

//销毁栈S

Status DestroyStack(SqStack &S);

//将栈S清空

Status ClearStack(SqStack &S);

//若栈S为空返回TRUE，否则FALSE

Status StackEmpty(SqStack S);

//返回栈S中的元素个数

int StackLength(SqStack S);

//用e返回栈顶元素

// 前提：栈S存在且不空

Status GetTop(SqStack S, ElemType &e);

//元素e入栈S

Status Push(SqStack &S, ElemType e);

//S出栈用e返回出栈元素

// 前提：栈S存在且不空

Status Pop(SqStack &S, ElemType &e);

///////////////////////////////////////////////////////////

//顺序栈的基本操作的实现

//构造一个空栈S

Status InitStack(SqStack &S)

{

// TODO (#1#): 构造一个空栈S

return ERROR;

//-------------------------------------

}

//销毁栈S

Status DestroyStack(SqStack &S)

{

// TODO (#1#):销毁栈S，相当于清空栈

return ERROR;

//-------------------------------------

}

//将栈S清空

Status ClearStack(SqStack &S)

{

// TODO (#1#): 将栈S清空，释放所有结点 return ERROR;

//-------------------------------------

}

//若栈S为空返回TRUE，否则FALSE

Status StackEmpty(SqStack S)

{

// TODO (#1#): 若栈S为空返回TRUE，否则FALSE return TRUE;

//-------------------------------------

}

//返回栈S中的元素个数

int StackLength(SqStack S)

{

// TODO (#1#): 返回栈S中的元素个数

return 0;

//-------------------------------------

}

//用e返回栈顶元素

// 前提：栈S存在且不空

Status GetTop(SqStack S, ElemType &e)

{

// TODO (#1#):若栈S不空，则用e返回栈顶元素 return ERROR;

//-------------------------------------

}

//元素e入栈S

Status Push(SqStack &S, ElemType e)

{

// TODO (#1#): 插入元素e作为新的栈顶

return ERROR;

//-------------------------------------

}

//S出栈用e返回出栈元素

// 前提：栈S存在且不空

Status Pop(SqStack &S, ElemType &e)

{

// TODO (#1#):若栈S不空，则删除栈顶元素用e返回 return ERROR;

//-------------------------------------

}

#ifdef ELEMTYPE_TAG

#undef ElemType

#undef ELEMTYPE_TAG

#endif

/**************************************************** @title: 数据结构实验

@name: <实验3-2> 顺序栈和栈的应用

@object:

[实验目的]

实现顺序栈；实现几个栈的具体应用

[实验提示]

1. 在stack.h中实现顺序栈

2. 在app0302.cpp中编写栈的应用程序，数制转换，括号匹配的检验

@include:

stack.h [*]

顺序栈模块

@usage:

请查看"TO-DO列表",根据要求完成代码

@author: Zhuang Bo

@date: 2004

@description:

*****************************************************/

#include <stdio.h>

#include <stdlib.h> //for system()

#include "stack.h" //for SqStack

//数制转换程序

void Conversion();

//检验括号匹配

void Match();

int main()

{

//数制转换程序

Conversion();

//检验括号匹配

Match();

system("PAUSE");

return 0;

}

//数制转换程序

void Conversion()

{

//-------------------------------------

// TODO (#1#): 这里实现数制转换程序

//-------------------------------------

}

//检验括号匹配

void Match()

{

//-------------------------------------

// TODO (#1#): 这里实现检验括号匹配的程序

//-------------------------------------

}

Name: 顺序栈的实现

Author:

Date:

Description:

#ifndef STACK_H_INCLUDED

#define STACK_H_INCLUDED

#include "ds.h" //for Status,OK ...

#ifndef ElemType

#define ElemType int /* 数据元素类型默认为 int */

#define ELEMTYPE_TAG

#endif

#define SElemType ElemType

///////////////////////////////////////////////////////////

//顺序栈的存储结构定义

#define STACK_INIT_SIZE 100 /* 存储空间初始分配容量 */ #define STACKINCREMENT 10 /* 存储空间分配的增量 */ typedef struct {

ElemType *base; //在构造栈之前和销毁栈之后，base为NULL ElemType *top; //栈顶指针

int stacksize; //当前已分配的存储空间(元素个数)

} SqStack;

///////////////////////////////////////////////////////////

//顺序栈的基本操作声明

//构造一个空栈S

Status InitStack(SqStack &S);

//销毁栈S

Status DestroyStack(SqStack &S);

//将栈S清空

Status ClearStack(SqStack &S);

//若栈S为空返回TRUE，否则FALSE

Status StackEmpty(SqStack S);

//返回栈S中的元素个数

int StackLength(SqStack S);

//用e返回栈顶元素

// 前提：栈S存在且不空

Status GetTop(SqStack S, ElemType &e);

//元素e入栈S

Status Push(SqStack &S, ElemType e);

//S出栈用e返回出栈元素

// 前提：栈S存在且不空

Status Pop(SqStack &S, ElemType &e);

///////////////////////////////////////////////////////////

//顺序栈的基本操作的实现

//构造一个空栈S

Status InitStack(SqStack &S)

{

// TODO (#1#): 构造一个空栈S

return ERROR;

//-------------------------------------

}

//销毁栈S

Status DestroyStack(SqStack &S)

{

// TODO (#1#):销毁栈S，相当于清空栈

return ERROR;

//-------------------------------------

}

//将栈S清空

Status ClearStack(SqStack &S)

{

// TODO (#1#): 将栈S清空，释放所有结点 return ERROR;

//-------------------------------------

}

//若栈S为空返回TRUE，否则FALSE

Status StackEmpty(SqStack S)

{

// TODO (#1#): 若栈S为空返回TRUE，否则FALSE return TRUE;

//-------------------------------------

}

//返回栈S中的元素个数

int StackLength(SqStack S)

{

// TODO (#1#): 返回栈S中的元素个数

return 0;

//-------------------------------------

}

//用e返回栈顶元素

// 前提：栈S存在且不空

Status GetTop(SqStack S, ElemType &e)

{

// TODO (#1#):若栈S不空，则用e返回栈顶元素 return ERROR;

//-------------------------------------

}

//元素e入栈S

Status Push(SqStack &S, ElemType e)

{

// TODO (#1#): 插入元素e作为新的栈顶

return ERROR;

//-------------------------------------

}

//S出栈用e返回出栈元素

// 前提：栈S存在且不空

Status Pop(SqStack &S, ElemType &e)

{

// TODO (#1#):若栈S不空，则删除栈顶元素用e返回 return ERROR;

//-------------------------------------

}

#ifdef ELEMTYPE_TAG

#undef ElemType

#undef ELEMTYPE_TAG

#endif

相关推荐

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

第二篇：数据结构C语言版顺序栈上机实验

专栏推荐