数据结构课程设计报告

合肥学院。

计算机科学与技术系。

课程设计报告。

20 13 ～20 14 学年第二学期。

2023年 6月。

1、问题分析和任务定义。

从题目可知，需要输入多个序列，而且序列中没有重复数字。用第一个序列与剩下的几个序列分别比较，判断两个序列能不能组成同一个序列。

在编程中需要建立二叉树，如何判断两个二叉树能不能组成同一棵二叉搜索树是一个关键问题。由于所有二叉搜索树的先序编列都是递增的，而且中序遍历可以用来区分二叉树，所以用中序遍历来判断两个序列能否组成同一棵二叉树，同时用数组来存储中序遍历后的序列。

因此解决问题的方案是：先序遍历二叉树，用数组存储先序遍历后的序列，用数组来判断两个序列能否组成同一棵二叉搜索树。

2、数据结构的选择和概要设计。

由于二叉树无法直接比较，所以先先序遍历二叉搜索树，同时用数组存储。

我的设计思路是：先建立一个二叉树，然后先序遍历它，由于数组可以比较，所以用数组存储。数组中的数分别对应先序遍历二叉树后的序列中的数所以把数组中对应的数分别比较，同时定义一个整型常量f，如果数组中对应的数相同，f++，否则退出。

用f值与数组长度比较，如果相等，则两个系列能组成同一棵二叉搜索树，否则，不能。

3、详细设计和编码。

程序的核心流程为：

程序的核心即为先序遍历二叉树和数组存储如下：

preorder(bstnode *t先序遍历二叉树。

if(t)f=1利用数组存储并比较。

for(e=b;eif(a[f]==a[e])

f++;else

break;

if(f==d-b+1)

printf("yes");

elseprintf("no");

4、上机调试过程。

问题：序列是无法比较的，故无法直接判断两个序列能否组成同一棵二叉树；在循环时无法直接退出必须人工退出。

解决方法：用数组存储，用数组知识来判断两个序列能否组成同一棵二叉搜索树。先序遍历二叉树得到一个新的序列，同时定义一个全局变量数组用来存储先序遍历二叉树后得到的序列，这样可以直接通过数组的比较来间接判断两个序列能否组成同一个二叉搜索树。

至于第二个问题，只要定义一个整型常量n，利用while循环，以n！=0为循环条件来直接退出运行过后的界面。

部分程序：while(scanf("%d",&n)!=eof&&n!=0)

5、测试结果及其分析。

测试数据1：

测试数据2：

6、用户使用说明。

输入一个数字n（1<=n<=20）表示需要与被比较的序列的序列个数，先输入被比较序列，先序遍历它同时以数组形式存储。然后输入需要与被比较序列比较的序列，也是先遍历序列在以数组形式存储。在比较过程中如果两个序列能组成同一棵二叉搜索树，则输出yes，否则输出no。

7参考文献。

1]王昆仑，李红。数据结构与算法。北京：铁道工业出版社，2023年5月第一版。

2]徐孝凯。数据结构实用教程。北京：清华大学出版社。2023年12月第一版。

8、附录：源程序。

#include ""

#define null 0

#define flag -1

int a[10];

int i=0;

typedef struct node

s=(bstnode *)malloc(sizeof(bstnode));

s->key=x;s->lchild=null;s->rchild=null;

if(t==null)

return s;

if(xkey)

f->lchild=s;

elsef->rchild=s;

return t;

bstnode *createbst()

return t;

preorder(bstnode *t)

void main()

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告

数据结构课程设计报告

其他用户还读了