设计出树结构的相关函数库以便在程序设计中调用.doc

数据结构课程设计报告 学 院 专 业 班 级 学 号 学生姓名 * 指导教师 课程成绩 完成日期 2013年7月12日课程设计成绩评定 学 院 城南学院专 业 计算机科学与技术 班 级 学 号 学生姓名 指导教师 完成日期 2013年7月12日指导教师对学生在课程设计中的评价评分项目优良中及格不及格课程设计中的创造性成果学生掌握课程内容的程度课程设计完成情况课程设计动手能力文字表达学习态度规范要求课程设计论文的质量指导教师对课程设计的评定意见综合成绩指导教师签字 2013年7月12日课程设计任务书 学院专业 课程名称数据结构课程设计时间20122013学年第二学期1920周学生姓名 指导老师 题 目设计出树结构的相关函数库,以便在程序设计中调用主要内容:使用Microsoft Visual C+ 6.0 设计二叉链表结构的相关函数库,以便在程序设计中调用设计二叉链表结构的相关函数库,在程序设计中调用,并实现二叉树的各种基本函数以及常用函数。要求: (1)包括树结构的存储结构及各种基本函数以及常用函数(自己确定函数、函数形式及理由)。(2)最好能借助语言环境实现图形显示功能,以便能将抽象的数据结构以图形方式显示出来,将复杂的运行过程以动态方式显示出来。 (3)给出若干例程,演示通过调用自己的库函数来实现相关问题的求解。应当提交的文件: (1)课程设计学年论文。 (2)课程设计附件(主要是源程序)。 设计出树结构的相关函数库,以便在程序设计中调用学生姓名: 指导老师: 摘 要 作为用户我们极少接触系统调用,但是我们熟悉C语言,对库函数的调用并不陌生。C语言支持一系列库函数的调用,而事实上,库函数的调用是C语言在较高层次上调用的一种方式,函数调用是操作系统内核提供给程序员的程序设计界面,它们是内核提供给用户调用的函数。使用Microsoft Visual C+ 6.0设计二叉链表结构的相关函数库,操作系统通过执行main函数开始运行一个C程序。main函数可以调用C程序中的其他函数来完成程序的任务,其他函数也可以互相调用,但其他函数(非main函数)不能调用main函数(main函数只能由操作系统来调用)。关键词 设计函数库;C程序的执行;C程序的调用;C语言;VC+6.0目录1 引 言11.1 课程设计目的11.2 课程设计要求12问题的描述22.1问题的模型化描述23数据结构33.1定义二叉树结点类型34 模块划分34.1 入队34.2 队列判空34.3 出队44.4根据先序递归建立二叉树44.5递归遍历输出函数44.6层次遍历输出算法54.7 求二叉树深度得算法54.8求二叉树叶子结点数的算法55 运行程序65.1程序运行结果66 结束语8附录:源程序代码91 引 言 Visual C+6.0由许多组件组成,包括编辑器、调试器以及程序向导AppWizard、类向导Class Wizard等开发工具。编译就是把高级语言变成计算机可以识别的2进制语言,计算机只认识1和0,编译程序把人们熟悉的语言换成2进制的。编译程序把一个源程序翻译成目标程序的工作过程分为五个阶段:词法分析;语法分析;语义检查和中间代码生成;代码优化;目标代码生成。主要是进行词法分析和语法分析,又称为源程序分析,分析过程中发现有语法错误,给出提示信息。将编译产生的.obj文件和系统库连接装配成一个可以执行的程序。由于在实际操作中可以直接点击Build从源程序产生可执行程序,将源程序翻译成可执行文件的过程分为编译和链接两个独立的步骤,之所以这样做,主要是因为:在一个较大的复杂项目中,有很多人共同完成一个项目每个人可能承担其中一部分模块,其中有的模块可能是用汇编语言写的,有的模块可能是用VC写的,有的模块可能是用VB写的,有的模块可能是购买不是源程序模块而是目标代码或已有的标准库模块,因此,各类源程序都需要先各自编译成目标程序文件,再通过链接程序将这些目标程序文件连接装配成可执行文件,再调用函数或运行可执行程序文件。1.1 课程设计目的(1)使用Microsoft Visual C+6.0 设计二叉链表结构的相关函数库(2)在程序设计中调用设计二叉链表结构的相关函数库(3)在程序设计中调用并实现二叉树的各种基本函数以及常用函数。1.2 课程设计要求 (1)按要求编写课程设计报告书,能正确阐述设计结果。 (2)通过课程设计培养学生严谨的科学态度,认真的工作作风和团队协作精神。 (3)学会文献检索的基本方法和综合运用文献的能力。 (4)在老师的指导下,要求每个学生独立完成课程设计的全部内容。 2.问题的描述 2.1问题的模型化描述 3 数据结构3.1定义二叉树结点类型typedef char datatype; typedef struct Nodechar data;struct Node * Lchild;struct Node * Rchild;BiTNode,*BiTree;/二叉树节点,二叉链表typedef struct QueueNodeBiTree data;struct QueueNode *next;LinkQueueNode;/队列中的每个节点typedef structLinkQueueNode *front;LinkQueueNode *rear;LinkQueue;/队列4.模块划分4.1入队void InitQueueLinkQueue *QQ-front LinkQueueNode *mallocsizeofLinkQueueNode;ifQ-front ! NULLQ-rear Q-front;Q-front-next NULL;else printf分配空间失败!n;4.2队列判空void EnterQueueLinkQueue *Q,BiTree xLinkQueueNode *NewNode;NewNode LinkQueueNode *mallocsizeofLinkQueueNode;ifNewNode ! NULLNewNode-data x;NewNode-next NULL;Q-rear-next NewNode;Q-rear NewNode;4.3出队int QueueIsEmptyLinkQueue *QifQ-front Q-rearreturn 1;else return 0;4.4根据先序递归建立二叉树void DeleteQueueLinkQueue *Q,BiTree *xLinkQueueNode *p;ifQ-front Q-rearreturn ;p Q-front-next;Q-front-next p-next;ifQ-rear pQ-rear Q-front;*x p-data;freep;4.5递归遍历输出函数 void CreateBiTreeBiTree *btchar ch;ch getchar;ifch . *bt NULL;else*bt BiTreemalloc sizeofBiTNode;*bt-data ch;CreateBiTree&*bt-Lchild;CreateBiTree&*bt-Rchild;/*先序递归遍历二叉树*/void PreOrderBiTree rootifroot ! NULLprintf%c ,root-data;PreOrderroot-Lchild;PreOrderroot-Rchild;/*后序递归遍历二叉树 */4.6层次遍历输出算法void PostOrderBiTree rootifroot ! NULLPostOrderroot - Lchild;PostOrderroot - Rchild;printf%c ,root-data;void InOrderBiTree rootifroot ! NULLInOrderroot-Lchild;printf%c ,root-data;InOrderroot-Rchild; 4.7求二叉树深度得算法void depthBiTree root,int &depint dep1,dep2;if!root dep0;elsedepthroot-Lchild,dep1;depthroot-Rchild,dep2;depdep1dep2?dep1+1:dep2+1; 4.8求二叉树叶子结点数的算法void countleafBiTree root,int&nif rootcountleafroot-Lchild,n;if!root-Lchild & !root-Rchild n+;countleafroot-Rchild,n;5 运行程序5.1 程序运行结果7 结束语 本次课程设计为时二周,我选的课题是设计出树结构的相关函数库,以便在程序设计中的调用。其主要研究内容在于实现了二叉链表的相关函数库的调用。为了实现以链表为存储结构的二叉树的有关操作,要熟练掌握二叉链表的特性,但对于一些算法较为复杂,代码量多些,容易出现一些变量的定义、函数声明、函数调用等细节上的问题出错。在本程序的设计过程中,为了克服以上困难,采取了一些措施:建立清晰的程序设计的步骤方法,分步各个模块程序设计,进行仔细的总体结构设计,反复调试、细心观察达到完善整个系统等。二叉树的递归算法主要是将二叉树存储到链表结构中。遍历是二叉树各种操作的基础,先序、中序、后序是二叉树遍历的三种基本遍历方法。而这些都是数据结构的基础内容,是我们必须理解和牢记的基础知识。将这些基础算法综合起来,更能清晰地认识和理解各种算法的作用。当然,要学会编程不会仅局限于课本知识,而是根据课本知识进行有效的拓展,并且不得不学会在众多的参考资料中搜索有用的自己所需的知识,并迫使自己去学习掌握它们,从中不断提高自己。虽然程序规模不大,我们依然为此付出了努力,仍免不了各种错误的出现。编程过程需要很大的毅力和耐心,而且要有良好的思维和扎实的专业基础知识,所以我们需要不断的学习,发现自身不足之处并改正它,逐步提高自身能力,不断取得进步。对于数据结构的学习,一直感到很吃力,也想过放弃。通过实践,我们接触到了很多关于的Microsoft Visual C+ 6.0编程让我们认识到知识的运用性,并加深对基础知识的理解,从中了解自己需要学习的东西并学会自学。在此我们要感谢我的老师对我们专心致志的辅导,让我们学会了许多分析和解决问题的方法,让我们受益匪浅。通过几个星期的努力,虽然从中也发现了自己很多不足,可能其中还有不少问题,但我觉得最重要的是自己也从中得到很多;不敢说百分百的完成也应该基本上完成了课题任务,成功地实现课题目标。参考文献1 严蔚敏. 数据结构(C语言版)M. 北京:清华大学出版社,1997.2谭浩强. C程序设计(第三版)M. 北京:清华大学出版社,2005.1附录:源程序代码#include#includetypedef struct Nodechar data;struct Node * Lchild;struct Node * Rchild;BiTNode,*BiTree;/二叉树节点,二叉链表typedef struct QueueNodeBiTree data;struct QueueNode *next;LinkQueueNode;/队列中的每个节点typedef structLinkQueueNode *front;LinkQueueNode *rear;LinkQueue;/队列/* 队列的初始化 */void InitQueueLinkQueue *QQ-front LinkQueueNode *mallocsizeofLinkQueueNode;ifQ-front ! NULLQ-rear Q-front;Q-front-next NULL;else printf分配空间失败!n;/* 入队 */void EnterQueueLinkQueue *Q,BiTree xLinkQueueNode *NewNode;NewNode LinkQueueNode *mallocsizeofLinkQueueNode;ifNewNode ! NULLNewNode-data x;NewNode-next NULL;Q-rear-next NewNode;Q-rear NewNode;/* 队列判空*/int QueueIsEmptyLinkQueue *QifQ-front Q-rearreturn 1;else return 0;/* 出队*/void DeleteQueueLinkQueue *Q,BiTree *xLinkQueueNode *p;ifQ-front Q-rearreturn ;p Q-front-next;Q-front-next p-next;ifQ-rear pQ-rear Q-front;*x p-data;freep;/* 利用扩展先序遍历序列 创建二叉链表*/void CreateBiTreeBiTree *btchar ch;ch getchar;ifch . *bt NULL;else*bt BiTreemalloc sizeofBiTNode;*bt-data ch;CreateBiTree&*bt-Lchild;CreateBiTree&*bt-Rchild;/*先序递归遍历二叉树*/void PreOrderBiTree rootifroot ! NULLprintf%c ,root-data;PreOrderroot-Lchild;PreOrderroot-Rchild;/*后序递归遍历二叉树 */void PostOrderBiTree rootifroot ! NULLPostOrderroot - Lchild;PostOrderroot - Rchild;printf%c ,root-data;void InOrderBiTree rootifroot ! NULLInOrderroot-Lchild;printf%c ,root-data;InOrderroot-Rchild;/*层序遍历 对给定的二叉树进行层序遍历 */void LayerOrderBiTree rootBiTree *x; /这里要记得申请空间 x BiTree *mallocsizeofBiTree; ifx NULL printf内存分配失败!n;LinkQueue *Q; Q LinkQueue *mallocsizeofLinkQueue; InitQueueQ; EnterQueueQ,root; while!QueueIs