数据结构CAI系统项目手册

数据结构项目书项目经理：产品经理：测试经理：一、问题描述：以数据结构教材中树和图的内容为例，设计数据结构的CAI（计算机辅助教学）系统，用菜单的形式选择各项功能。

用图形化界面的形式显示算法的执行过程。

二、程序分析：二叉树的遍历算法演示中，首先定义一个TREE的结构体，里面存放的数据类型分别是char,两个TREE类型指针*lchild(左孩子)，*rchild（右孩子），两个int 分别是x和y,分别代表了树的x坐标和y坐标。

再建立一个名称为OUTPUT的结构体里面存放了三种遍历的x坐标和y坐标。

通过对Tree *CreatTree();函数的调用生成二叉树再通过void Preorder(Tree *t);void Midorder(Tree *t);void Posorder(Tree *t);这三个函数进行前中后的遍历来判断左右孩子是否存在。

三、程序设计：1、结构化函数设计2、设计工具Win-TC, c文件3、编码头文件：#include <graphics.h>#include <stdio.h>#include <stdlib.h>#include <dos.h>#include <time.h>结构体：typedef struct TREE{char data; /*树的结点数据*/struct TREE *lchild;struct TREE *rchild;int x; /*树的x坐标*/int y; /*树的y坐标*/}Tree;struct OUTPUT{int x; /*三种遍历的x坐标*/int y; /*三种遍历的y坐标*/int num;}s;函数：·函数名称：void DrawTree(Tree *t); ·函数描述：用图形显示创建好的树·函数名称：void Preorder(Tree *t); ·函数描述：前序遍历·函数名称：void Midorder(Tree *t); ·函数描述：中序遍历·函数名称：void Posorder(Tree *t); ·函数描述：后序遍历·函数名称：void DrawNode(Tree *t,int color);·函数描述：遍历时显示每个结点的过程·函数名称：void ClrScr();·函数描述：清空树的区域·函数名称：void Close(void);·函数描述：图形模式结束四、测试与调试：1、调试报告一开始的调试中，我们就碰到了很严重的问题，图形化的界面一直无法正常的显示出来，运行之后，都是一闪即逝，为此，我们上网查阅了很多信息。

加了getch（）；也加了system（“plause”）；，这些基本的解决方法毫无用处；又有说要把Egavga.bgi 这个文件和生成的exe文件放在一起，起初使用TC3.0时也无法正常显示图形界面。

多番尝试无果之后打算试试Win-TC,结果莫名其妙的成功了。

并且发现Egavga.bgi的确要和exe文件放在同一个文件夹，不在一起时无法进入图形界面，这是在一次另存为把文件保存到其他文件夹时发现的。

还有最开始时，对于一些需要用到的函数所需的头文件不是很了解，不过通过网络的搜索之后，都一一得到解答。

但是直到目前为止，依然有个比较大的问题，就是系统自动生成二叉树的时候，经常会出现重复字母的结点，我们想的是能不能一个节点之后就在26个字母之中把这个结点用到的字母抽出去，然后剩下的位置就从剩下的字母中选取，可是二叉树是一下子全部显示出来，好像没有明显的先后顺序，最后还是不会。

2、测试结果A：主界面---选择生成树的方式（自动/手动）B：选择1后C：选择2后D：按任意键后，进入二叉树的演示初始界面---图形化界面的初始化E：按任意键后开始遍历，并输出遍历结果五、主要算法分析：（一）二叉树的生成Tree *InitTree(int h,int t,int w){char ch;int n; /*自动建立时随机赋值判断是否是NULL的标志*/Tree *node;if(way=='2') /*手动建立需要自己输入*/scanf("%c",&ch);else /*自动建立的赋值*/{n=random(5);if(n==0&&nodeNUM>=3) /*随机赋值时候确保自动建立的二叉树有三个结点*/ ch=' ';elsech=65+random(25);}if(ch==' ') /*输入空格代表NULL*/return NULL;else{if(h==6||nodeNUM==26) /*如果树的层次已经到5或者结点树到达26个就自动返回NULL*/return NULL;node=(Tree*)malloc(sizeof(Tree));node->data=ch;node->x=t; /*树的x坐标是传递过来的横坐标*/node->y=h*50; /*树的y坐标与层次大小有关*/nodeNUM++;node->lchild=InitTree(h+1,t-w,w/2);node->rchild=InitTree(h+1,t+w,w/2);}return node;}功能：实现二叉树的生成功能，用于构建二叉树（二）图形化显示二叉树void DrawTree(Tree *t){if(t!=NULL){setcolor(BLACK);setfillstyle(SOLID_FILL,BLACK);fillellipse(t->x,t->y,9,9);setcolor(WHITE);circle(t->x,t->y,10); /*画圆*/sprintf(str,"%c",t->data); /*将内容转换成字符串输出*/outtextxy(t->x-3,t->y-2,str);if(t->lchild!=NULL) /*左子树*/{line(t->x-5,t->y+12,t->lchild->x+5,t->lchild->y-12);DrawTree(t->lchild);}if(t->rchild!=NULL) /*右子树*/{line(t->x+5,t->y+12,t->rchild->x-5,t->rchild->y-12);DrawTree(t->rchild);}}}功能：利用坐标实现图形化输出二叉树的功能，用于图形化演示六、心得体会：项目经理-肖毅：刚开始拿到课设的题目时，浏览一遍之后发现毫无头绪，不知从何下手。

从大一接触C语言开始，到后来学习C++，到现在的数据结构，学到现在，面对大型完整程序的编写，依然感觉很是无力。

最后我们选择了数据结构CAI系统，因为觉得可以直接从所学的一些算法中直接完成，已经学过现成的算法，有了明确的目标，我们要做的就是将这些算法图形化的演示出来，不会毫无思路。

虽然的确有些思路了，但是也并没有我们想象的那么简单，从最开始的计划完成3个算法的演示到最后只完成了一个二叉树的三种遍历的演示。

另外我们觉得选择这个也能够帮助我们复习数据结构的一些知识，对于即将到来的数据结构考试也是有所帮助的，虽然查找和排序并没有完成，但是我们也翻阅数据结构课本仔细研究了书上关于那些部分的算法，这也是一种复习，排序和查找也是数据结构中很重要的一部分。

确定完题目之后，就要开始着手编写了，我们组成员的整体水平虽然不是很高，但我们依然能够凭借自己的努力来完成程序，遇到不会的问题，我们会向其他同学请教，并且自己上网搜索相关信息，不得不再次感叹网络的强大，网络确实是现代生活中不可缺少的一部分。

这次课设中我和池璐主要负责程序的编写，我们也是边写程序边学习，我主要负责程序中二叉树图形化输出和二叉树的生成等部分，图形化输出需要用到坐标，我们要将想要输出的东西放到屏幕上正确的部分，需要经过多次尝试之后才能最后确定坐标。

同时也让其他几位成员参与编写并学习，对于一些我会的地方，也会跟他们讲解，为了让他们更好的理解程序，并完成后期PPT的制作。

团队协作能力也是考校一个计算机专业学生的一个很重要的因素。

通过这次课设，对于数据结构基本功的知识是一种强化，更扎实了数据结构的基本功，并学习到了很多课堂上没有学到过的知识，对于计算机知识的学习之路，光靠课堂所学是远远不够的。

实际程序的编写也是很重要的，每一个完整的程序对于自己都是一次历练，这对于以后的学习和未来的工作都是很有帮助的。

项目经理-池璐：在忙碌了一个星期之后，课设终于结束了。

“实践出真知”，编出一些有用的程序更是对数据结构这门课程学习的最好检验。

正是这次的检验，让我受益良多。

我们设计的是一款教学CAI辅助程序，用直观便于理解的动态图示为学生展现的是二叉树的3种遍历方式。

我主要负责的是界面设计和3种遍历。

界面上我设计的比较简洁，用一些特殊符号构成了框架。

为了方便老师，我设计了2种方式，一种为计算机自动分配二叉树，另一种是认为输入。

3种不同的遍历方式主要看的是根节点的位置。

例如先序遍历的根节点最先被访问。

在算法的设计中我也参与了进去，与项目经理进行了探讨，最终完成了整个程序。

当然，编程之路并非一帆风顺。

其间我们也遇到了许多问题。

比如菜单的编程问题，编程环境的影响一记图形函数的应用。

在查阅资料后，大部分问题得到了解决，我也学到了之前不太了解的问题。

另外，我计划还设计一款二分法的CAI程序，由于知识水平有限，我便看书试图解决这个问题。

但是最后没有能够解决。

课设虽然结束了，但是学习的脚步还没有就此停下。

更多的实践等着我把数据结构这么课在学习生活中运用的更加娴熟，理解的更加透彻。

这才是学好这门课的意义。

产品经理-黄友鹏：通过本次课设，我学到很多。

首先必须承认，我的基础很差，本来对编一大段程序就很头疼，但是这次以小组方式进行，使我能够向他人学习，就算是大家都不会的问题我们也可以分工上网寻找解决的办法，总之，第一次觉得学习也可以变得很轻松。

而且，通过这次课设，我也懂得了好多专业的名词，如路演，CAI系统...这些都是我以前没有接触过的。

本次课设我担任产品经理的职位，这不只是一个小小的虚衔，这是让我们提早感受社会，事实上我也是这么努力的，我自己做了路演PPT，而且目的就是让别人接收我们的产品，虽然还有很多的不足，但我们努力了，我也很有成就感。