当前位置：文档之家 › 数据结构第三次实验

数据结构第三次实验

  • 格式：doc
  • 大小：55.50 KB
  • 文档页数：8

实验四树的操作与应用【实验目的】1．熟练掌握二叉树的二叉链表存储结构2．掌握二叉树的非线性和递归性特点3．熟练掌握二叉树的递归遍历操作的实现方法，掌握二叉树的非递归遍历操作的实现4．加深对二叉树结构和性质的理解，逐步培养解决实际问题的编程能力【实验内容】1．定义二叉树的链式存储结构；2．实现二叉树的基本操作：建空树、销毁二叉树、生成二叉树(先序,中序或后序)、判二叉树是否为空、3．求二叉树的深度、求二叉树的根等基本算法；4．实现二叉树的递归(先序、中序或后序)遍历算法；【实验指导】1．首先将二叉树的链式存储结构定义放在一个头文件：如取名为BinTreeDef.h。

2．将二叉树的基本操作算法也集中放在一个文件之中，如取名为BinTreeAlgo.h。

包含关于二叉树的链式结构操作的一些基本算法，如：InitBiTree、DestroyBiTree、CreateBiTree、BiTreeEmpty、BiTreeDepth、Root、PreOrderTraverse、InOrderTraverse 等。

3．将函数的测试和主函数组合成一个文件，如取名为BinTreeUse.cpp。

利用二叉树的链式存储结构，设计一组输入数据（假定为一组整数或一组字符），能够对二叉树进行如下操作：1．创建一棵空二叉树；2．对一棵存在的二叉树进行销毁；3．根据输入某种遍历次序输入二叉树中结点的值，依序建立二叉树；4．判断某棵二叉树是否为空；5．求二叉树的深度；6．求二叉树的根结点，若为空二叉树，则返回一特殊值；7．二叉树的遍历，即按某种方式访问二叉树中的所有结点，并使每个结点恰好被访问一次；8．编写主程序，实现对各不同的算法调用；实现要求如下：“构造空二叉树算法”操作结果：构造一个空二叉树T；“销毁二叉树算法”初始条件: 二叉树T 存在；操作结果: 销毁二叉树T ；“创建二叉树算法”初始条件:可以根据先序、中序和后序输入二叉树中结点的值（可为字符型或整型）；操作结果: 以选择的某种次序建立二叉树T ；“判二叉树是否为空算法”初始条件: 二叉树T 存在；操作结果: 若T 为空二叉树,则返回TRUE,否则FALSE ；“求二叉树的深度算法”初始条件: 二叉树T 存在；操作结果: 返回T 的深度；“求二叉树的根算法”初始条件: 二叉树T 存在；操作结果: 返回T 的根；“先序递归遍历算法”初始条件: 二叉树T 存在,Visit 是对结点操作的应用函数；操作结果: 先序递归遍历T,对每个结点调用函数Visit 一次且仅一次；“中序递归遍历算法”初始条件: 二叉树T 存在,Visit 是对结点操作的应用函数；操作结果: 中序递归遍历T,对每个结点调用函数Visit 一次且仅一次；“后序递归遍历算法”初始条件: 二叉树T 存在,Visit 是对结点操作的应用函数；操作结果: 后序递归遍历T,对每个结点调用函数Visit 一次且仅一次；长春大学计算机科学技术学院实验报告日期_______________ 地点______________ 指导教师_____________ 成绩实验四树的操作与应用利用二叉树的链式存储结构，设计一组输入数据（假定为一组整数或一组字符），能够对二叉树进行如下操作：1．创建一棵空二叉树；2．对一棵存在的二叉树进行销毁；3．根据输入某种遍历次序输入二叉树中结点的值，依序建立二叉树；4．判断某棵二叉树是否为空；5．求二叉树的深度；6．求二叉树的根结点，若为空二叉树，则返回一特殊值；7．二叉树的遍历，即按某种方式访问二叉树中的所有结点，并使每个结点恰好被访问一次；实现过程：1、文件pubuse.h，与实验一相同；2．文件BinTreeDef.h 中实现了二叉树的链式存储结构定义typedef struct BiTNode{TElemType data；struct BiTNode *lchild,*rchild；/* 左右孩子指针*/}BiTNode,*BiTree；3．文件BinTreeAlgo.h 中实现二叉树的基本操作（存储结构由BinTreeDef.h 定义）Status InitBiTree(BiTree &T){ /* 操作结果: 构造空二叉树T */T=NULL；return OK；}void DestroyBiTree(BiTree &T){ /* 初始条件: 二叉树T 存在。

操作结果: 销毁二叉树T */if(T) /* 非空树*/{if(T->lchild) /* 有左孩子*/DestroyBiTree(T->lchild)；/* 销毁左孩子子树*/if(T->rchild) /* 有右孩子*/DestroyBiTree(T->rchild)；/* 销毁右孩子子树*/free(T)；/* 释放根结点*/T=NULL；/* 空指针赋0 */}}#define ClearBiTree DestroyBiTreevoid CreateBiTree(BiTree &T){ /* 按先序次序输入二叉树中结点的值，构造二叉链表表示的二叉树T。

变量Nil 表示空（子）树。

*/TElemType ch；scanf("%d",&ch)；if(ch==Nil) /* 空*/T=NULL；else{T=(BiTree)malloc(sizeof(BiTNode))；if(!T)exit(OVERFLOW)；T->data=ch；/* 生成根结点*/CreateBiTree(T->lchild)；/* 构造左子树*/CreateBiTree(T->rchild)；/* 构造右子树*/}Status BiTreeEmpty(BiTree T){ /* 初始条件: 二叉树T 存在*//* 操作结果: 若T 为空二叉树,则返回TRUE,否则FALSE */if(T)return FALSE；elsereturn TRUE；}int BiTreeDepth(BiTree T){ /* 初始条件: 二叉树T 存在。

操作结果: 返回T 的深度*/int i,j；if(!T)return 0；if(T->lchild)i=BiTreeDepth(T->lchild)；elsei=0；if(T->rchild)j=BiTreeDepth(T->rchild)；elsej=0；return i>j?i+1:j+1；}TElemType Root(BiTree T){ /* 初始条件: 二叉树T 存在。

操作结果: 返回T 的根*/if(BiTreeEmpty(T))return Nil；elsereturn T->data；}void PreOrderTraverse(BiTree T,Status(*Visit)(TElemType)){ /* 初始条件: 二叉树T 存在,Visit 是对结点操作的应用函数。

*//* 操作结果: 先序递归遍历T,对每个结点调用函数Visit 一次且仅一次*/ if(T) /* T 不空*/{Visit(T->data)；/* 先访问根结点*/PreOrderTraverse(T->lchild,Visit)；/* 再先序遍历左子树*/ PreOrderTraverse(T->rchild,Visit)；/* 最后先序遍历右子树*/}}void InOrderTraverse(BiTree T,Status(*Visit)(TElemType)){ /* 初始条件: 二叉树T 存在,Visit 是对结点操作的应用函数*//* 操作结果: 中序递归遍历T,对每个结点调用函数Visit 一次且仅一次*/ if(T){}}void PostOrderTraverse(BiTree T,Status(*Visit)(TElemType)){ /* 初始条件: 二叉树T 存在,Visit 是对结点操作的应用函数*//* 操作结果: 后序递归遍历T,对每个结点调用函数Visit 一次且仅一次*/if(T) /* T 不空*/{}}4．在文件BinTreeUse.cpp 中，测试二叉树基本算法的调用/* BinTreeUse.cpp 检验BinTreeAlgo.h 的主程序*/#include"pubuse.h" /* 与实验一的意义相同*/TElemType Nil=0；#include"BinTreeDef.h" /* 二叉树链式存储结构定义*/#include"BinTreeAlgo.h" /* 二叉树基本算法和扩展算法定义*/Status visitT(TElemType e){printf("%d ",e)；return OK；}void main(){ int i；BiTree T,p,c；TElemType e1,e2；/* 1---基本实验算法的验证*/InitBiTree(T)；printf("构造空二叉树后,树空否？%d(1:是0:否) 树的深度=%d\n", BiTreeEmpty(T), BiTreeDepth(T))；e1=Root(T)；if(e1!=Nil)printf("二叉树的根为: %d\n",e1)；elseprintf("树空，无根\n")；printf("请先序输入二叉树(如:1 2 0 0 0 表示1 为根结点,2 为左子树的二叉树)\n")；CreateBiTree(T)；printf("建立二叉树后,树空否？%d(1:是0:否) 树的深度=%d\n",BiTreeEmpty(T),BiTreeDepth(T))；e1=Root(T)；printf("二叉树的根为: %d\n",e1)；elseprintf("树空，无根\n")；printf("中序递归遍历二叉树:\n")；InOrderTraverse(T,visitT)；printf("后序递归遍历二叉树:\n")；PostOrderTraverse(T,visitT)；}。

合集下载

哈尔滨理工大学数据结构第3次实践课内容

哈尔滨理工大学数据结构第3次实践课内容

必做●SubString (&Sub, S, pos, len)求子串●Index (S, T, pos)字符串查找#include <stdio.h>#include <stdlib.h>#define INTERLENGTH 100#define INCREASE 10#define OK 1#define ERROR -1#define overflow -2typedef struct{char *data;int length;int size;}Sqlist;int cj(Sqlist &L){L.data=(char *)malloc(INTERLENGTH*sizeof(char));if(L.data==NULL)exit(overflow);L.length=0;L.size=INTERLENGTH;return OK;}int AgainMalloc(Sqlist &L){char *newbase;newbase=(char *)realloc(L.data,(INCREASE+L.size)*sizeof(char)); if(newbase==NULL)exit(overflow);L.data=newbase;L.size+=INCREASE;return OK;}int insert(Sqlist &L,char a){if(L.length==L.size){AgainMalloc(L);}L.data[L.length]=a;L.length++;return OK;int travel(Sqlist &L){for(int i=0;i<L.length;i++)printf("%c",L.data[i]);printf("\n");return OK;}int clear(Sqlist &L){L.length=0;return OK;}int SubString(Sqlist &L,int pos,int len,Sqlist &sub) {if(pos<1||pos>L.length||len<0||len>L.length-pos+1) {printf("²»ºÏ·¨ ");exit(overflow);}cj(sub);clear(sub);int i;for(i=pos-1;i<pos+len-1;i++){insert(sub,L.data[i]);}return OK;}int index(Sqlist &L,Sqlist &sub){int i=0;int j=0;while(i<L.length&&j<sub.length){if(L.data[i]==sub.data[j]){i++;j++;}else{i=i-j+1;j=0;}}if(j>=sub.length)return i-sub.length+1;elsereturn ERROR;}int main(){Sqlist L,sub;cj(L);char c;printf("请输入字符串：\n");while((c=getchar())!='\n'){insert(L,c);}printf("求得从2位置开始4位自串如下：\n"); SubString(L,2,4,sub);travel(sub);clear(sub);printf("请输入待查找字符串；\n");while((c=getchar())!='\n'){insert(sub,c);}int a= index(L,sub);printf("%d",a);}。

数据结构实验报告三

数据结构实验报告三

数据结构实验报告三数据结构实验报告三引言：数据结构是计算机科学中的重要内容之一，它研究的是如何组织和存储数据以便高效地访问和操作。

本实验报告将介绍我在数据结构实验三中的实验过程和结果。

实验目的：本次实验的主要目的是熟悉并掌握树这种数据结构的基本概念和操作方法，包括二叉树、二叉搜索树和平衡二叉树等。

实验内容：1. 实现二叉树的创建和遍历在本次实验中，我首先实现了二叉树的创建和遍历。

通过递归的方式，我能够方便地创建一个二叉树，并且可以使用前序、中序和后序遍历方法对二叉树进行遍历。

这些遍历方法的实现过程相对简单，但能够帮助我们更好地理解树这种数据结构的特点。

2. 实现二叉搜索树的插入和查找接下来，我实现了二叉搜索树的插入和查找操作。

二叉搜索树是一种特殊的二叉树，它的左子树上的节点的值都小于根节点的值，右子树上的节点的值都大于根节点的值。

通过这种特性，我们可以很方便地进行插入和查找操作。

在实现过程中，我使用了递归的方法，通过比较节点的值来确定插入的位置或者进行查找操作。

3. 实现平衡二叉树的插入和查找平衡二叉树是为了解决二叉搜索树在某些情况下可能会退化成链表的问题而提出的。

它通过在插入节点的过程中对树进行旋转操作来保持树的平衡。

在本次实验中，我实现了平衡二叉树的插入和查找操作。

通过对树进行左旋、右旋等操作，我能够保持树的平衡，并且能够在O(log n)的时间复杂度内进行插入和查找操作。

实验结果：通过本次实验，我成功地实现了二叉树、二叉搜索树和平衡二叉树的相关操作。

我编写了测试代码，并对代码进行了测试，结果表明我的实现是正确的。

我能够正确地创建二叉树，并且能够使用前序、中序和后序遍历方法进行遍历。

对于二叉搜索树和平衡二叉树，我能够正确地进行插入和查找操作，并且能够保持树的平衡。

实验总结：通过本次实验，我深入了解了树这种数据结构的特点和操作方法。

二叉树、二叉搜索树和平衡二叉树是树的重要应用，它们在实际开发中有着广泛的应用。

数据结构实验-第3次试验-图的应用

数据结构实验-第3次试验-图的应用

第三次实验 图的应用
[问题描述] 给定一个图，设计一个程序，找出一条从某一顶点A到另一顶点B边数最少的一条路径。 [输入] 图的顶点个数N，图中顶点之间的边的关系及要找的路径的起点A和终点B。 [输出] 若A到B无路径，则输出“There is no path”，否则输出A到B路径上各顶点。 [存储结构] 图采用邻接矩阵或邻接表的方式存储。
实现时采用队列记录被访问过的顶点。每次访问与队头顶点
相邻接的顶点，然后将队头顶点从队列中删去。若队空，则说明到
不存在通路。在访问顶点过程中，每次把当前顶点的序号作为与其 邻接的未访问的顶点的前驱顶点记录下来，以便输出时回溯。
Байду номын сангаас
[算法的基本思想] 采用广度优先搜索的方法，从顶点A开始，依次访问与A邻接的顶 点VA1,VA2,...,VAK, 访问遍之后,若没有访问B，则继续访问与VA1邻 接的顶点VA11,VA12,...,VA1M，再访问与VA2邻接顶点...，如此下去 ，直至找到B，最先到达B点的路径，一定是边数最少的路径。
数据结构实验三实验报告

数据结构实验三实验报告

数据结构实验三实验报告数据结构实验三实验报告一、实验目的本次实验的目的是通过实践掌握树的基本操作和应用。

具体来说，我们需要实现一个树的数据结构，并对其进行插入、删除、查找等操作，同时还需要实现树的遍历算法，包括先序、中序和后序遍历。

二、实验原理树是一种非线性的数据结构，由结点和边组成。

树的每个结点都可以有多个子结点，但是每个结点只有一个父结点，除了根结点外。

树的基本操作包括插入、删除和查找。

在本次实验中，我们采用二叉树作为实现树的数据结构。

二叉树是一种特殊的树，每个结点最多只有两个子结点。

根据二叉树的特点，我们可以使用递归的方式实现树的插入、删除和查找操作。

三、实验过程1. 实现树的数据结构首先，我们需要定义树的结点类，包括结点值、左子结点和右子结点。

然后，我们可以定义树的类，包括根结点和相应的操作方法，如插入、删除和查找。

2. 实现插入操作插入操作是将一个新的结点添加到树中的过程。

我们可以通过递归的方式实现插入操作。

具体来说，如果要插入的值小于当前结点的值，则将其插入到左子树中；如果要插入的值大于当前结点的值，则将其插入到右子树中。

如果当前结点为空，则将新的结点作为当前结点。

3. 实现删除操作删除操作是将指定的结点从树中移除的过程。

我们同样可以通过递归的方式实现删除操作。

具体来说，如果要删除的值小于当前结点的值，则在左子树中继续查找；如果要删除的值大于当前结点的值，则在右子树中继续查找。

如果要删除的值等于当前结点的值，则有三种情况：- 当前结点没有子结点：直接将当前结点置为空。

- 当前结点只有一个子结点：将当前结点的子结点替代当前结点。

- 当前结点有两个子结点：找到当前结点右子树中的最小值，将其替代当前结点，并在右子树中删除该最小值。

4. 实现查找操作查找操作是在树中寻找指定值的过程。

同样可以通过递归的方式实现查找操作。

具体来说，如果要查找的值小于当前结点的值，则在左子树中继续查找；如果要查找的值大于当前结点的值，则在右子树中继续查找。