课程设计任务.doc

附件3：课 程 设 计 任 务 书题 目 还原二叉树 院 (部) 交通与物流工程学院 专 业 物联网工程 班 级 物联141-2 学生姓名 学 号 月 日至 月 日 共 1 周指导教师(签字) 陈颖 负责人(签字) 张良智 年 月 日一、设计内容及要求目的：熟练掌握二叉树存储结构；熟练掌握二叉树的遍历及应用。要求：给定一颗二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。(1) 输入说明：输入第1行给出正整数N(N=50)，为树中结点总数。随后2行先后给出先序和中序遍历序列，均是长度为N的不包含重复英文字母（区别大小写）的字符串。(2) 输出说明：输出为一个整数，即该二叉树的高度。(3) 测试用例序列输入输出说明19ABDFGHIECFDHGIBEAC5一般情况测试215cdefghijklmnxyzcdefghijklmnxyz15完全右斜37AbcdefggfedcbA7完全左斜41aa1边界测试55050个随机数略二、设计原始资料本题需要解决两个子问题：(1) 通过输入给定的先序遍历和中序遍历两个序列构建对应二叉树。由于我们知道先序遍历的第1个结点必然是根节点，可以在终须遍历序列中找到这个根结点的位置，于是就知道在中序遍历中，根节点左边的所有结点一定属于左子树，右边的所有结点一定属于右子树。根据这个判断，可以从中序遍历序列中知道左、右子树分别有L,R个结点，它们必然对应存储在先序遍历序列遍历中第2-（L-1）个结点以及最后的R个结点。于是可以对左右子树递归地解决这个问题，直到生成整个二叉树。(2) 求二叉树的高度。如果已经知道左右子树的高度，那么树的高度就是左右子树中比较高的那个 加1.这是一个可以用二叉树后序遍历解决的问题，在遍历过程中，我们将“访问节点”定义为“求左右子树高度的较大值加1。实现要点：树形结构用一般教材中介绍的链表结构存储，结点结构体存储该节点的字符以及左右子树的指针。在构建二叉树和求二叉树高度的过程中，需注意递归终止的条件。typedef struct TreeNode *BinTree;struct TreeNode char Data; BinTree Left; BinTree Right;三、设计完成后提交的文件和图表1算法设计部分 可以选择队列进行算法设计。必须包含实验分析，需求分析，程序流程设计，函数名称及实现功能说明。2程序部分：针对自己的数据结构算法设计，按照流程图进行C语言源程序设计。设计要求：（1）运行无错误(2) 运行在有限时间内，不能是无限循环(3) 运行测例进行测试无错误。四、进程安排课程设计前完成资料收集课程设计第3天完成五、主要参考资料 数据结构 严蔚敏 清华大学出版社其它网络开源资料附件3：课 程 设 计 任 务 书题 目 六度空间 院 (部) 交通与物流工程学院 专 业 物联网工程 班 级 物联141-2 学生姓名 学 号 月 日至 月 日 共 1 周指导教师(签字) 陈颖 负责人(签字) 张良智 年 月 日一、设计内容及要求“六度空间”理论又称作“六度分隔理论”。这个理论可以通俗地阐述为：“你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过五个人你就能认识任何一个陌生人”六度空间理论虽然得到广泛的认同，并且正在得到越来越多的应用。但是数十年来，试图验证这个力量始终是许多社会学家努力追求的目标。然而由于历史的原因，这样的研究具有太大的局限性和困难。随着当代人依赖于电话、短信、微信以及因特网上即时通信等工具，能够体现社交网络关系的一手数据已经逐渐使得六度空间理论的验证成为可能。假如给你一个社交网络图，请你对每个节点计算符合六度空间理论的结点总数的百分比。(1) 输入：输入第1行给出两个正整数，分别表示社交网络图的结点数N(1N104,表示人数)、边数M(=33*N，表示社交关系数)。随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个结点的编号（节点从1到N编号）。(2) 输出格式：对每个结点输出与该节点距离不超过6的结点数占结点总数的百分比，精确到小数点后2位。每个结节点输出一行，格式为“结点编号：（空格）百分比%”二、设计原始资料（1）问题分析：把验证六度空间理论改成计算“到某个结点的距离不超过6的结点总数占所有节点数的百分比”是一个比较现实的做法。“每个社会人”的这个百分比如果都能够达到98%（或者99%），是不是也可以认为六度空间理论基本成立？(2)实现要点：图的存储有邻接矩阵和邻接表两种。由于本题给出边数的上届不超过结点数的33倍，且结点数最多可达1000，即相对于人数而言，庞大的社交网络的关系远远达不到稠密图，所以选择邻接表来做图的存储比较合理。（这个地方参考教材邻接表的类型，还要考虑题目要求，增加记录最后得到百分比的变量，浮点型）。这里对邻接表中每个节点对应的所有邻接点编号顺序没有要求。所以在建立邻接表时，每条边只需简单依次插入到邻接表的头部。三、设计完成后提交的文件和图表1算法设计部分 可以选择队列进行算法设计。必须包含实验分析，需求分析，程序流程设计，函数名称及实现功能说明。2程序部分：针对自己的数据结构算法设计，按照流程图进行C语言源程序设计。设计要求：（1）运行无错误(2) 运行在有限时间内，不能是无限循环(3) 运行测例进行测试无错误。四、进程安排课程设计前完成资料收集课程设计第4天完成五、主要参考资料 数据结构 严蔚敏 清华大学出版社其它网络开源资料