文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 工学 > 数据结构课程设计指导书
侵权投诉

数据结构课程设计指导书

信息,也可以提高查找信息的速度。

5. 二叉排序树与平衡二叉排序树基本操作的实现

设计要求:用二叉链表作存储结构,编写程序实现二叉排序树上的基本操作。

基本功能:

用二叉链表作存储结构,编写程序实现二叉排序树上的基本操作:以回车('\n')为输入结束标志,输入数列L,生成二叉排序树T;对二叉排序树T作中序遍历;计算二叉排序树T的平均查找长度,输出结果;输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历;否则输出信息“无结点x”; 判断二叉排序树T是否为平衡二叉树;再用数列L,生成平衡二叉排序树BT:当插入新元素之后,发现当前的二叉排序树BT不是平衡二叉排序树,则立即将它转换成新的平衡二叉排序树BT;计算平衡的二叉排序树BT的平均查找长度,输出结果。

实现提示:

建立二插排序树采用边查找边插入的方式。查找函数采用递归的方式进行查找。如果查找成功则不应再插入原树,否则返回当前结点的上一个结点。然后利用插入函数将该元素插入原树。对二叉树进行中序遍历采用递归函数的方式。在根结点不为空的情况下,先访问左子树,再访问根结点,最后访问右子树。计算二插排序树的平均查找长度时,可采用类似中序遍历的递归方式,用s记录总查找长度,j记录每个结点的查找长度,s置初值为0,采用累加的方式最终得到总查找长度s。平均查找长度就等于s/i(i为树中结点的总个数)。

删除结点函数,采用边查找边删除的方式。如果没有查找到,则不对树做任何的修改;如果查找到结点,则分四种情况分别进行讨论:1、该结点左右子树均为空;2、该结点仅左子树为空;3、该结点仅右子树为空;4、该结点左右子树均不为空。

判断二插排序树是否为平衡二叉树的函数,也是采用递归函数的方式,分别判定以树中每个结点为根结点的子树是否为平衡二叉树。只要有一个子树不为平衡二叉树,则该树便不是平衡二叉树。

6.哈夫曼树的应用

设计要求:从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式(比如树)显示在终端上;利用已经建好的哈夫曼树(如不在内存,则从文件htmTree中读入),对文件ToBeTran中的正文进行编码,然后将结果存入文件CodeFile中,并输出结果,将文件CodeFile以紧凑格式先是在终端上,每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码,结果存入文件TextFile中,并输出结果。

实现提示:

在构造哈夫曼树时,可以设置一个大小为2n-1的数组ht保存哈夫曼树中各结点的信息.其中,weight域保存结点的权值,lchild和rchild域分别保存该结点的左、右孩子结点在数组ht中的序号,叶子结点的这两个指针值为空(即-1)。为了判定一个结点是否已加入到要建立的s哈夫曼树中,可通过parent域的值来确定。初始时parent的值为-1,当结点加入到树中时,该结点parent的值为其双亲结点在数组ht中的序号。

哈夫曼树的存储结构定义述如下:

#define MaxSize 10000 /*定义最大权值*/

typedef struct {

int weight;

int parent;

int lchild;

上一页第5页

你可能喜欢

  • 二叉树的中序遍历
  • c语言数据结构课程设计
  • c++数据结构课程设计
  • 哈希表设计数据结构课程设计
  • 数据结构课程设计说明书
  • 数据结构课程设计停车场
  • 数据结构课程设计题目
  • 数据结构课程设计排序

热门文档

相关文档

  • 数据结构课程设计指导书

    数据结构课程设计指导书主编 荣祺 适用专业: 计算机科学与技术 上海应用技术学院 2006 年 08 月 目录 第一章 第二章 第三章 课程设计教学大纲 ... 2 课程设计...

  • 2011下数据结构课程设计指导书

    2011下数据结构课程设计指导书_工学_高等教育_教育专区。本书介绍,怎样书写你的课程设计报告。课程设计指导书 课程设计指导书一、课程设计的地位、目的和作用 课程...

  • 数据结构课程设计指导书

    《数据结构 A》课程设计指导书计算机与控制学院 一.目的通过本课程设计,使学生更加系统地理解和掌握数据结构的基本概念;使学生能自如地根 据实际要求,设计相应的...

  • 数据结构课程设计指导书1

    《数据结构》课程设计指导书 数据结构》计算机与通信学院 肖小克 一.目的通过本课程设计,使学生更加系统地理解和掌握数据结构的基本概念;使学生能自如地根 据实际...

  • 2013《数据结构课程设计》指导书

    数据结构课程设计指导书李娅 编 电子与信息工程学院计算机系 2013-3 1 一、课程设计的目的和意义本课程设计是学生在学完了《数据结构》课程后,培养学生程序设计...

  • 数据结构课程设计指导书

    《数据结构与算法》课程设计 指导书 计算机学院 一.设计要求: 本课程设计是为了配合《数据结构与算法》课程的开设,通过设计一个完整的程序, 使学生掌握数据结构的...

  • 数据结构课程设计指导书

    数据结构课程设计指导书 1 课程管理系统功能:假定有 n 门课程,每门课程有课程编号,课程名称,总学时,学分,开课学期等信息。试设计一课程管理系统, 使之能提供以下...

  • 《数据结构课程设计》指导书

    《数据结构》课程设计指导书 沈阳理工大学.信息学院 2013.11.1 一.目的与意义 软件设计能力对计算机专业的学生是很重要。 通过数据结构的学习, 使学 生对软件...

  • 数据结构课程设计指导书

    数据结构课程设计 指导书 2014.9 一、实验目的通过训练,实现以下三方面目标: 1.使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email