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

时间：2024.4.29

实验三

一、实验目的

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语言版实验报告姓名学号指导老师实验1实验题目单链表的插入和删除实验目的了解和掌握线性表的逻辑结构和链式存储结构掌握单链表的基本算法及相关的时间性能分析实验要求建立一个数据域定义为字符串的单链表在链表中...
数据结构实验报告(C语言)(强力推荐): 数据结构实验实验内容和目的掌握几种基本的数据结构集合线性结构树形结构等在求解实际问题中的应用以及培养书写规范文档的技巧学习基本的查找和排序技术让我们在实际上机中具有编制相当规模的程序的能力养成一种良好的程序设计...
数据结构C语言版实验报告: 苏州科技学院数据结构C语言版实验报告专业班级测绘0911学号0920xx5130姓名朱辉实习地点指导教师史守正实验四图一程序设计的基本思想原理和算法描述图是一种较线性表和树更加复杂的一种数据结构在图形结构中结点...
数据结构(C语言版)实验报告: 数据结构C语言版实验报告学院计算机科学与技术专业计算机大类强化学号xxx班级xxx姓名xxx指导教师xxx实验1实验题目单链表的插入和删除实验目的了解和掌握线性表的逻辑结构和链式存储结构掌握单链表的基本算法及相...
数据结构(C语言版) 实验报告: 数据结构C语言版实验报告专业计算机科学与技术学号班级姓名指导教师青岛大学信息工程学院20xx年10月实验1实验题目顺序存储结构线性表的插入和删除实验目的了解和掌握线性表的逻辑结构和顺序存储结构掌握线性表的基本算...
数据结构c语言版实验报告: 198初程P71内的最确切的解答把相应编号写在答卷的对应栏内设有4个数据元素a1a2a3和a4对他们分别进行栈操作或队操作在进栈或进队操作时按a1a2a3a4次序每次进入一个元素假设栈或队的初始状态都是空现要进...
数据结构(C语言版) 实验报告: 数据结构C语言版实验报告专业计算机科学与技术软件工程学号20xx40703061班级软件二班姓名朱海霞指导教师刘遵仁青岛大学信息工程学院20xx年10月实验1实验题目顺序存储结构线性表的插入和删除实验目的了解和...

数据结构(C语言版)课程设计报告表达式求值: 安徽理工大学数据结构课程设计说明书题目表达式求值院系计算机科学与工程学院专业班级计算机121班学号20xx303038学生姓名丰继强指导教师刘文娟20xx年12月25日安徽理工大学课程设计论文任务书计算机科学与...
数据结构实验报告(C语言)顺序表查找: 计算机科学与技术系实验报告专业名称计算机科学与技术课程名称数据结构与算法项目名称顺序表查找班级学号姓名实验日期格式要求实验报告注意格式规范要求在word中编写文中不要有空行统一使用A4页面页边距上25cm下2c...
数据结构实验报告(C语言)顺序表排序: 计算机科学与技术系实验报告专业名称计算机科学与技术课程名称数据结构与算法项目名称排序班级计科一班学号姓名实验日期格式要求实验报告注意格式规范要求在word中编写文中不要有空行统一使用A4页面页边距上25cm下2...
数据结构c语言版实验教案: 数据结构实验教案授课教师许四平适用专业信息与计算科学使用班级13信计12授课时间20xx年秋季授课学时14学时使用教材数据结构严蔚敏主编实验指导书数据结构实验指导书数理学院编20xx年版湖北理工学院数理学院实验...
《数据结构》(C语言版)严蔚敏著_数据结构实验指导: 数据结构实验指导及报告书学年第学期姓名学号班级指导教师数学与统计学院20xx1预备实验C语言的函数数组指针结构体知识一实验目的1复习C语言中函数数组指针结构体与共用体等的概念2熟悉利用C语言进行程序设计的一般方...

数据结构c语言版实验报告（30篇）

热门关注

《数据结构》(C语言版)严蔚敏著_数据结构实验指导

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

数据结构实验报告(C语言)(强力推荐)

数据结构实验报告(C语言)单链表的基本操作

数据结构实验报告(C语言)(强力推荐)

《数据结构》(C语言版)严蔚敏著_数据结构实验指导

数据结构实验C语言实现线性表

数据结构实验报告