数据结构--线性表实验报告+二叉树实验报告

线性表实验报告+二叉树实验报告

实验报告

班级： 学号： 姓名： 日期：

1. 实验题目

编辑一个程序，用来演示线性表的建立、插入、删除等操作。

2. 需求分析

本演示程序在Microsoft Visual C++ 6.0环境下编写调试，完成线性表的生成、任意位置的插入、删除等。

（1）输入的形式和输入的范围：执行插入操作时，需要输入插入位置和元素的值；执行删除操作时，需要输入待删除元素的位置。在所有输入中，元素的值都是由整数、字符数组和字符数组组成的。

（2）输出的形式：在所有操作中都要求显示相关操作是否正确以及操作后线性表的内容。其中删除操作完成后，要显示删除后所剩的元素的值。

（3）程序所能达到的功能：完成线性表的生成、插入、删除操作。

3. 概要设计

（1）为了实现上述程序功能，需要定义线性表的数据结构。线性表单个元素的结构如图1.1所示。

图1.1 线性表元素的数据结构

（2）本程序包含6个函数： ①主函数main()。

②初始化线性表函数creat()。 ③插入元素函数insert()。 ④删除元素函数del()。

线性表实验报告+二叉树实验报告

各函数间的关系如图1.2所示。

图1.2 程序所包含各函数之间的关系

4. 详细设计

实现概要设计中定义的所有的数据类型，对每个操作给出具体的算法；对主程序和其他模块也都需要写出具体算法。

（一）数据类型。用C语言描述如下：

typedef struct {

int num; float score; }student;

（二）线性表的基本操作函数的具体算法：

1. 主函数main()的具体算法：

void main() {

student L[4]; creat(L); insert(L); del(L); }

2. 初始化线性表函数creat()的具体算法：

void creat(student s[4]) {

printf("输入学生数据：\n"); for(i=0;i<3;i++)

scanf("%d%f",&s[i].num,&s[i].score);

线性表实验报告+二叉树实验报告

printf("目前数据数：%d组\n",i); for(i=0;i<3;i++)

printf("%d\t%5.1f\t\n",s[i].num,s[i].score); }

3. 插入元素函数insert()的具体算法：

void insert(student s[4]) {

printf("输入插入数据位置：\n"); scanf("%d",&j); if(j>4)

printf("输入有误，请输入在0~4之间\n"); scanf("%d",&j); // if(j=4)

// printf("输入插入数据：\n");

// scanf("%d%f",&s[j-1].num,&s[j-1].score); if(j<=4)

for(i=3;i>=j-1;i--) s[i]=s[i-1];

printf("输入插入数据：\n");

scanf("%d%f",&s[j-1].num,&s[j-1].score); n=n+1;

printf("目前数据数：%d组\n",n); for(i=0;i<4;i++)

printf("%d\t%5.1f\t\n",s[i].num,s[i].score); }

4. 删除元素函数del()的具体算法：

void del(student s[4]) {

printf("输入删除数据位置：\n"); scanf("%d",&j); if(j>4)

printf("输入有误，请输入在0~4之间\n"); scanf("%d",&j); for(i=j-1;i<4;i++) s[i]=s[i+1]; n=n-1;

printf("目前数据数：%d组\n",n); for(i=0;i<3;i++)

线性表实验报告+二叉树实验报告

printf("%d\t%5.1f\t\n",s[i].num,s[i].score); }

5. 测试结果

（1）初始化线性表函数creat()：

根据提示信息“输入学生数据”，依次输入三个学生数据，运行结果将显示

“目前数据数：3组”，则会依次显示3组数据，如图1.3所示。

图1.3 初始化线性表函数creat()

（2）插入元素函数insert()：

根据提示信息“输入插入数据位置”，输入一个正整数，此时整数会根据

初始化创建函数给定的数据个数条件，输入大于等于1或小于等于X（X表示初始化数据个数）的数值，会正确执行插入程序；否则程序执行ERROR。根据提示信息，输入插入数据。输入结束时，会显示目前数据数，清晰明了，如图1.4所示。

图1.4 插入元素函数insert()

（3）删除元素函数del()：

根据提示信息“输入删除数据位置”，输入一个正整数，此时整数由于在初始化设定的数据个数基础上插入了新数据，所以，输入删除数据的位置时要大于等于1或小于等于初始化数据个数加上插入的数据个数之和，否则程序将是

线性表实验报告+二叉树实验报告

ERROR。执行结束，显示信息“目前数据数”，如图1.5所示。

图1.5 删除元素函数del()

线性表实验报告+二叉树实验报告

实验报告

班级： 学号： 姓名： 日期：

1. 实验题目

编辑一个程序，用来演示二叉树的初始化，二叉树的递归先序、中序，非递归先序、中序等操作。

2. 需求分析

本演示程序在Microsoft Visual C++ 6.0环境下编写调试，完成二叉树的各种操作。为了实现对二叉树的有关操作，首先要在计算机中建立所需的二叉树，建立二叉树有各种不同的方法。

一种方法是利用二叉树的性质5来建立二叉树，输入数据时需要将结点的序号（按满二叉树编号）和数据同时给出：（序号，数据元素）。例如二叉树输入数据顺序为：（1,A），（2,B），（3,C），（4,D），（6,E），（7,F），（9,G），（13,H）。如下图1.1所示：

图1.1二叉树

另一种算法是教材中介绍的方法，这是一个递归方法，与二叉树的先序遍历有点相似。数据的组织是先序的顺序，上例二叉树的输入数据顺序应该是：ABD G CE H F。递归调用建立函数，建立当前结点的左右子树。

3. 概要设计

（1）为了实现上述程序功能，需要定义二叉树的数据结构，结构如图1.2所示。

线性表实验报告+二叉树实验报告

图1.2 二叉树的数据结构

（2）本程序包含6个函数，如下所示：

①主函数main()；

②初始化二叉树函数CreatBiTree(Tree)； ③递归先序函数PreOrderTrave(Tree)； ④递归中序函数InOrderTrave(Tree)； ⑤非递归先序函数Preorder(Tree)； ⑥非递归中序函数Inorder(Tree)。

图1.3程序各函数之间的关系

4.详细设计

实现概要设计中定义的所有的数据类型，对每个操作给出具体的算法；对主程序和其他模块也都需要写出具体算法。 一．数据类型用C语言描述如下： typedef struct BiTNode {

char data;

struct BiTNode *lchild,*rchild,*par; int n;

}BiTNode,*BiTree;

struct BiTNode *stack[20];

二．二叉树的基本操作函数的具体算法： 1. 主函数main()的具体算法：

void main() {

线性表实验报告+二叉树实验报告

BiTNode *Tree;

printf("输入结点：\n"); CreatBiTree(Tree);

printf("\n递归先序：\n"); PreOrderTrave(Tree);

printf("\n递归中序：\n"); InOrderTrave(Tree);

printf("\n非递归先序：\n"); Preorder(Tree);

printf("\n非递归中序：\n"); Inorder(Tree);

}

2. 初始化二叉树函数creat()的具体算法：

int CreatBiTree(BiTree &T)

{

char ch;

scanf("%c",&ch); if(ch==' ') T=NULL; else

{

T=(BiTNode *)malloc(sizeof(BiTNode)); T->data=ch; T->n=0;

CreatBiTree(T->lchild); CreatBiTree(T->rchild); }

return (OK); }

3. 递归先序函数PreOrderTrave(Tree)：

void PreOrderTrave(BiTree T) { if(T) {

printf("%c ",T->data); PreOrderTrave(T->lchild); PreOrderTrave(T->rchild);

线性表实验报告+二叉树实验报告

}

}

4. 递归中序函数InOrderTrave(Tree)：

void InOrderTrave(BiTree T) { if(T)

{InOrderTrave(T->lchild); printf("%c ",T->data); InOrderTrave(T->rchild);} }

5. 非递归先序函数Preorder(Tree)：

void Preorder(BiTree T) {

int top=0;

while(T || top!=0) {

while (T)

{printf("%c ",T->data ); stack[top++]=T; T=T->lchild ; }

T=stack[--top]; T=T->rchild ; } }

6. 非递归中序函数Inorder(Tree)：

void Inorder(BiTree T) {

int top=0;

while(T || top!=0) {

while (T) {

stack[top++]=T; T=T->lchild ; }

T=stack[--top];

线性表实验报告+二叉树实验报告

printf("%c ",T->data ); T=T->rchild ; } } 4. 测试结果

输入数据的组织是先序的顺序，输入需求分析中例二叉树数据顺序应该是：ABD G CE H F，如图1.4所示，演示二叉树的递归先序、中序和非递归先序、中序结果：

本文来源：https://www.bwwdw.com/article/xxae.html