数据结构课程设计二叉连链表.doc

1、课程设计指导书姓 名学 号班 级课程名称数据结构课程性质专业必修课设计时间2010 年 12 月 1日 2010 年 12月 20日设计名称设计二叉链表结构的相关函数库设计目的使用Microsoft Visual C+ 设计二叉链表结构的相关函数库，并能够在程序设计中调用设计要求设计二叉链表结构的相关函数库，以便在程序设计中调用，实现二叉树的各种基本函数以及常用函数；并给出1-2个例子，通过调用自己的库函数来实现问题的求解。设计思路与设计过程1. 程序需求分析完成：根据需求分析，确定各个程序功能的需求；2. 程序总统设计完成：根据程序需求，进行程序大概框架的设计；3. 主函数设计完成：主函数程

2、序中设计一个菜单，并调试所用算法；4. 其他函数设计完成：建立二叉链表以及递归序列遍历算法5. 系统程序完善完成：完善整个程序细节代码的要求，进行调试。计划与进度12.1-12.2 复习对vc+6.0使用，了解关于二叉链表的相关特征等。12.3-12.4 查找有关二叉链表基本操作的算法等。12.5-12.7 根据需求分析，确立各个函数程序功能。12.8-12.10 根据程序需求，进行相关子函数程序的编写。12.11-12.13 进行主函数程序功能的设计编写。12.14-12.16 进行对整个程序的完善。12.17-12.18 进行程序的调试运行。12.19-12.20 资料归档，填写相关文档。

3、任课教师意 见备 注课程设计报告课程：学号：姓名：班级：教师时间：计算机科学与技术系设计名称： 设计二叉链表的相关函数库日期：2010年 12 月 20 日 设计内容：使用Microsoft Visual C+ 设计二叉链表结构的相关函数库，以便在程序设计中调用设计目的与要求：设计二叉链表结构的相关函数库，在程序设计中调用，并实现二叉树的各种基本函数以及常用函数。设计环境或器材、原理与说明：器材：计算机一台硬件环境：处理器：Intel core i3内存： 1GB硬盘空间：320GB显卡：ATI Mobility Radeon软件环境：Windows XP,Microsoft Visual C

4、+6.0使用数据结构设计的一般方法步骤进行设计。设计过程（步骤）和部分程序代码(可以加页)：一 题目要求 设计二叉链表结构的相关函数库，在程序设计中调用，并实现二叉树的各种基本函数以及常用函数。二 需求分析 建立一棵二叉树： （1）二叉树的链表结构；（2）进行先序遍历，输出结果；（3）进行中序遍历，输出结果；（4）进行后序遍历，输出结果；（5）进行层次遍历，输出结果。三 运行环境Windows XP 四 开发工具和编程语言 1.开发工具：Microsoft Visual C+6.02.编程语言：C语言五 概要设计1. 数据结构typedef char datatype; typedef str

5、uct node /定义二叉树结点类型datatype data;struct node *lchild;struct node *rchild;Btnode,* Btree;2.模块划分1根据先序递归建立二叉树 Btree pre_creat() 2递归遍历输出函数 void preorder_btree(Btree root) /由先根序列遍历输出二叉树void inorder_btree(Btree root) /由中根序列遍历输出二叉树 void postorder_btree(Btree root) /由后根序列遍历输出二叉树3层次遍历输出算法 void level_btree(Bt

6、ree root) /层次遍历输出二叉树六 详细设计1创建二叉树的实现Btree pre_creat() /使用先根序列建立二叉树，返回指针Btree t;char ch;fflush(stdin);scanf(%c,&ch); /输入一个结点数据if(ch=)return NULL; /空结点elset=(Btnode *)malloc(sizeof(Btnode); /申请结点空间，根节点t-data=ch;t-lchild=pre_creat(); /生成左子树t-rchild=pre_creat(); /生成右子树return t;2先序、中序、后序递归遍历输出算法void preor

7、der_btree(Btree root) /由先根序列输出二叉树Btree p=root;if(p!=NULL) printf(%3c,p-data); /输出结点值preorder_btree(p-lchild); /输出左子树preorder_btree(p-rchild); /输出右子树 void inorder_btree(Btree root) /由中根序列输出二叉树Btree p=root;if(p!=NULL) inorder_btree(p-lchild); /输出左子树 printf(%3c,p-data); /输出结点值inorder_btree(p-rchild); /

8、输出右子树 void postorder_btree(Btree root) /由后根序序列输出二叉树Btree p=root;if(p!=NULL) postorder_btree(p-lchild); /输出左子树postorder_btree(p-rchild); /输出右子树 printf(%3c,p-data); /输出结点值 3.层次遍历输出算法 void level_btree(Btree root) /层次遍历输出二叉树 Btree p;p=(Btnode *)malloc(sizeof(Btnode); /申请一个新结点p-data=;p-lchild=p-rchild=NU

9、LL; /为新结点赋初值int front, rear;front=rear=0; /置空队列p=root; /工作结点指向根节点if(p!=NULL)rear +;Qrear=p; /结点不为空就入队if(rear=1)front=1;Qfront=p; /根节点入队作为队列头结点rear +;while(front!=rear)p=Qfront; /队头结点出队front +;printf(%3c,p-data);if(p-lchild!=NULL)Qrear=p-lchild;rear +;if(p-rchild!=NULL)Qrear=p-rchild;rear +; 这三个函数实现了

10、二叉树的递归遍历方法。先序思想是先根、后左孩子、再右孩子，中序遍历思想是先左孩子、后根、再右孩子，后序是先左孩子、后右孩子、再根。4.主函数int main()Btree boot;boot=(Btnode *)malloc(sizeof(Btnode);boot=NULL;int x;doprintf(_n); printf(-欢迎使用！-n);printf(_n); printf(n*主菜单*n); printf( x=1. 先序遍历建立二叉树!n); printf( x=2. 先序遍历输出二叉树!n); printf( x=3. 中序遍历输出二叉树!n); printf( x=4. 后序

11、遍历输出二叉树!n); printf( x=5. 层次遍历输出二叉树!n); printf( x=0. 退出n); printf(*n);dofflush(stdin);printf(请输入x的值:);scanf(%d,&x);if(x!=1)&(x!=2)&(x!=3)&(x!=4)&(x!=0)&(x!=5)printf(请输入正确的x的值n);while(x!=1)&(x!=2)&(x!=3)&(x!=4)&(x!=0)&(x!=5);switch(x)case 1:printf(t先序遍历建立二叉树:n); printf(t请输入二叉树结点的值!:n); printf(可以输n个值均为

12、字母或(n100)字符间以回车符换行,想结束时输多个):n); boot=pre_creat(); /顺序表的逆置printf(nn);break;case 2: printf(t先序遍历输出二叉树！:n); printf(建立的二叉树是: ); preorder_btree(boot);printf(nn);break;case 3:printf(t中序遍历输出二叉树！:n); printf(建立的二叉树是: ); inorder_btree(boot);printf(nn);break; case 4: printf(t后序遍历输出二叉树！:n); printf(建立的二叉树是: ); p

13、ostorder_btree(boot);printf(nn);break;case 5: printf(t层次遍历输出二叉树！:n); printf(建立的二叉树是: ); level_btree(boot);printf(nn);break;while(x!=0);printf(ByeBye!);return x;7. 运行结果： 图 一 图 二 图 三 图 四 图 五 图 六 图 七设计结果与分析(可以加页)：本次课程设计实现了二叉链表的相关函数库的调用。为了实现以链表为存储结构的二叉树的有关操作，要熟练掌握二叉链表的特性，但对于一些算法较为复杂，代码量多些，容易出现一些变量的定义、函数

14、声明、函数调用等细节上的问题出错。在本程序的设计过程中，为了克服以上困难，采取了一些措施：建立清晰的程序设计的步骤方法，分步各个模块程序设计，进行仔细的总体结构设计，反复调试、细心观察达到完善整个系统等。设计体会与建议：数据结构是计算机程序设计的重要理论技术基础，在理论学习和基础实验的基础上，通过实践设计一定量的程序，掌握应用计算机解决实际问题的基本方法，是理解和运用数据结构及算法，提高编程能力的有效途径，并为学习软件专业课程积累理论基础和实践基础。程序的设计和开发过程，不仅要求我们牢固地掌握各种基础知识，更考查了对基础知识的综合运用能力。这次我的实验课题是二叉树的基本算法综合分析。算法是数据

15、结构的核心，是我们学习软件开发必须掌握的基本知识。简单课程设计最重要的是基础知识的运用，以及综合分析问题的能力。二叉树的递归算法主要是将二叉树存储到链表结构中。遍历是二叉树各种操作的基础，先序、中序、后序是二叉树遍历的三种基本遍历方法。而这些都是数据结构的基础内容，是我们必须理解和牢记的基础知识。将这些基础算法综合起来，更能清晰地认识和理解各种算法的作用。当然，要学会编程不会仅局限于课本知识，而是根据课本知识进行有效的拓展，并且不得不学会在众多的参考资料中搜索有用的自己所需的知识，并迫使自己去学习掌握它们，从中不断提高自己。例如，课本上只给出了二叉树的递归中序遍历方法，由此可容易推出递归的前序和中序遍历方法。二叉树的基本操作是多种多样的，由于时间的短促和作者水平有限，因不能做太大规模的设计。虽然程序规模不大，我依然为此付出了努力，仍免不了各种错误的出现。编程过程需要很大的毅