课程设计任务2-3

1、附件3:课程设计任务书题 目还原二叉树院（部）交通与物流工程学院专业物联网工程班级物联141-2学生学号月一日至一月一日共丄周指导教师（签字）颖负责人（签字）良智一、设计容及要求目的：熟练掌握二叉树存储结构；熟练掌握二叉树的遍历及应用。要求：给定一颗二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高 度。输入说明：输入第1行给出正整数N(N<=50),为树中结点总数。随后2行先后给出先序和中序遍历序列，均是长度为 N的不包含重复英文字母 (区别大小写)的字符串。(2) 输出说明：输出为一个整数，即该二叉树的高度(3) 测试用例序列输入输出说明19ABDFGHIECFDHGIBEAC

2、5一般情况测试215cdefghijkl mnxyz cdefghijkl mnxyz15完全右斜37Abcdefg gfedcbA7完全左斜41 a a1边界测试55050个随机数略二、设计原始资料本题需要解决两个子问题：(1) 通过输入给定的先序遍历和中序遍历两个序列构建对应二叉树。由于我们知道先序遍历的第1个结点必然是根节点，可以在终须遍历序列中找 到这个根结点的位置，于是就知道在中序遍历中，根节点左边的所有结 点一定属于左子树，右边的所有结点一定属于右子树。根据这个判断， 可以从中序遍历序列中知道左、右子树分别有L,R个结点，它们必然对应存储在先序遍历序列遍历中第 2-( L-1 )个

3、结点以及最后的R个结点 于是可以对左右子树递归地解决这个问题，直到生成整个二叉树。(2) 求二叉树的高度。如果已经知道左右子树的高度，那么树的高度就是左 右子树中比较高的那个加1.这是一个可以用二叉树后序遍历解决的问 题，在遍历过程中，我们将“访问节点”定义为“求左右子树高度的较 大值加1。实现要点：树形结构用一般教材中介绍的链表结构存储，结点结构体存储该节点的字符以及 左右子树的指针。在构建二叉树和求二叉树高度的过程中，需注意递归终止的条 件。typedef struct TreeNode *Bin Tree;struct TreeNodechar Data;Bin Tree Left;Bi

4、n Tree Right;三、设计完成后提交的文件和图表1 算法设计部分可以选择队列进行算法设计。必须包含实验分析，需求分析，程序流程设计，函 数名称及实现功能说明。2.程序部分：针对自己的数据结构算法设计，按照流程图进行C语言源程序设计。设计要求:(1) 运行无错误(2) 运行在有限时间，不能是无限循环(3) 运行测例进行测试无错误。四、进程安排课程设计前完成资料收集课程设计第3天完成五、主要参考资料数据结构严蔚敏清华大学 其它网络开源资料附件3:课程设计任务书题 目六度空间院（部）交通与物流工程学院专业物联网工程班级物联141-2学生学号月日至月日共丄周指导教师（签字）颖负责人（签字）良智

5、、设计容及要求“六度空间”理论又称作“六度分隔理论”。这个理论可以通俗地阐述为:“你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过五个人你就能认识任何一个陌生人”六度空间理论虽然得到广泛的认同， 并且正在得到越来越多的应用。但是数 十年来，试图验证这个力量始终是许多社会学家努力追求的目标。然而由于历史的原因，这样的研究具有太大的局限性和困难。随着当代人依赖于、短信、微信 以及因特网上即时通信等工具，能够体现社交网络关系的一手数据已经逐渐使得 六度空间理论的验证成为可能。假如给你一个社交网络图，请你对每个节点计算符合六度空间理论的结点总 数的百分比。（1）输入：输入第1行给出两个

6、正整数，分别表示社交网络图的结点数 N（1vN<10,表示人数）、边数M（v=33*N表示社交关系数）。随后的 M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个结点的编号（节点从1到N编号）。（2）输出格式：对每个结点输出与该节点距离不超过 6的结点数占结点总数的百分 比，精确到小数点后2位。每个结节点输出一行，格式为“结点编 号：（空格）百分比%输入输出10 91: 70. 00ft1 22: 8D_ 00ft2 33: 901 00?&3 44i IOC. 00%4 55: 10C.OCK15 £S: IOC. 006 77： 10C.OCK7 88:

7、 SO. 00fta eo.oog io10： 7C.0CKi n s1: 70. 00«1 u o i 92: 60. m1搐9 q3 : 30. DOSe -j2 址4: EOL 00ftj 孕4 百5: EOL 00ft£仝U E A乩 SO. 00ftU UA 7心 EOL 00ftu f7 oa： 70_ 00ft1 U q | n9: 20. 00ft10: 20.0D!t1 1 101: lOC.OtK1 2Z: 90. 91?&1 3?; 9Q.91 曙1 44: 100.014 55: lOC.OChi3$ 5$; IOC.000 77: IOC.

8、 00%S BS: 100.00%9 59; 100.00%R 10io： mo.mID 1111: 81.62%、设计原始资料(1)问题分析：把验证六度空间理论改成计算“到某个结点的距离不超过 6的结点总数占所有节点数的百分比”是一个比较现实的做法。“每个社会 人”的这个百分比如果都能够达到 98% (或者99%，是不是也可以认为六 度空间理论基本成立？实现要点：图的存储有邻接矩阵和邻接表两种。由于本题给出边数的上 届不超过结点数的33倍，且结点数最多可达1000,即相对于人数而言，庞 大的社交网络的关系远远达不到稠密图， 所以选择邻接表来做图的存储比较 合理。(这个地方参考教材邻接表的类型，还要考虑题目要求，增加记录最 后得到百分比的变量，浮点型)。这里对邻接表中每个节点对应的所有邻接点编号顺序没有要求。所以在建立邻接表时，每条边只需简单依次插入到邻接表的头部。三、设计完成后提交的文件和图表1 算法设计部分可以选择队列进行算法设计。必须包含实验分析，需求分析，程序流程设计, 函数名称及实现功能说明。2.程序部