数据结构CAI系统项目手册.doc

北京工业大学数据结构课程设计项目书数据结构项目书项目经理：产品经理：测试经理：一、 问题描述：以数据结构教材中树和图的内容为例，设计数据结构的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 #include #include #include #include 结构体：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= ; else ch=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，而且目的就是让别人接收我们的产品，虽然还有很多的不足，但我们努力了，我也很有成就感。总之，在这次课设中我学到了很多，也感觉进步了很大。测试经理-于连明： 这次课设给了我很大的锻炼，使我进一步理解数据结构的重要性。我们小组设计的是CAI(Computer Assisted Instruction),也就是计算机辅助教学。目前我们所学的数据结构计算机专业一门重要的专业技术基础课程，有人概括过这样一个公式：程序算法数据结构，要设计好的程序，除了要设计好的算法之外，还必须采用合适的数据结构。所以数据结构的知识对设计和实现计算机系统软件如操作系统、编译程序和数据库管理系统等是十分重要的；它对于编写应用软件的人来说也是必不可少的。 然而学习这门课程有一些困难:(1)内容丰富，学习量大，给学习带来困难。(2)贯穿的动态链表存储结构和递归技术是学习中的重点也是难点;(3)所用到的技术多，而在此之前的各门课程中所介绍的专业性知识又不多，因而加大了学习难度;在解答问题时出会因此而困难重重。 因此我们小组为了解决数据结构学起来困难的麻烦，设计了CAI系统。这是一种崭新的教学方式，它可以代替教师模拟教学过程，是通过学生与计算机之间的交互活动达到教学的目的。其图文并茂，灵活方便的众多特点，可以激发我们学生的学习兴趣，且发挥学生的学生积极性，提高教学质量。CAI可以将某些非顺序信息呈现出来，可以包括一门课程或与某个对象有关的全部知识。我们即可以浏览所有知识，也可以按自己的需要获取其中任意所感兴趣的一部分，学生可以控制学习内容和进度。 但是我们设计的CAI系统缺乏网络支持。它是运行在单机下环境下的。无法利用网络在知识更新上的方便与快捷的优势。这样的CAI课件一旦生产完成就再也无法对教学的内容进行更新和维护，因而是没有生命力的，将随着时间的发展而逐步被淘汰。这类弊端有待研究解决。这次课设也使我明白团队的合作是非常重要的，团结就是胜利。七、 分工协作：项目经理：肖毅 池璐职责：负责整个项目小组的人员管理、进度管理，主要攻克软件产品技术环节的问题，负责路演环节技术问题的答辩，负责项目手册中的核心算法部分的书写及整个项目手册的整理定稿。负责进行项目中期汇报及与指导教师的沟通。产品经理：黄友鹏职责：负责整个产品的框架设计、外观设计和功能模块的升级设计，主要负责产品的需求分析及性能改良，负责手册中产品外观和框架及需求的书写，负责路演环节PPT的制作。测试经理：于连明职责：负责整个产品的功能模块部分的设计与最终产品测试环节，建立产品所需的数据资源库，负责路演环节产品使用的答辩，负责项目手册中功能模块及算法的书写。八、 附录：源代码/*二叉树的三种遍历算法演示*/#include #include #include #include #include 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;int nodeNUM=0; /*统计当前的结点数字,最多26个*/char way; /*自动建立树和手动建立树的标志,2手动,1自动*/char str3; /*显示结点数据的字符串*/void Init(); /*图形初始化*/void Close(); /*图形关闭*/Tree *CreatTree(); /*文本模式下创建树的过程*/Tree *InitTree(int h,int t,int w); /*创建树,h层次,t横坐标,w树之间的宽度,n树的建立方式*/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 main() Tree *root; randomize(); root=CreatTree(); /*创建树*/ Init(); DrawTree(root); /*每次遍历前显示白色的树*/ sleep(1); s.x=100;s.y=300;s.num=1; /*每次遍历前设置显示遍历顺序显示的x,y坐标*/ Preorder(root); /*前序遍历*/ getch(); ClrScr(); DrawTree(root); sleep(1); s.x=100; s.y=350; s.num=1; Midorder(root); /*中序遍历*/ getch(); ClrScr(); DrawTree(root); sleep(1); s.x=100; s.y=400; s.num=1; Posorder(root); /*后序遍历*/ Close();/*清空树的区域*/void ClrScr() setcolor(BLACK); setfillstyle(SOLID_FILL,BLACK); bar(0,20,640,280);/*树的创建*/Tree *CreatTree() Tree *root; clrscr(); printf(n); printf(n); printf( Binary tree traversal n); printf( -n); printf( *Please input 1 OR 2 to choose* n); printf( * * n); printf( * 1.Computer creat * n); printf( * * n); printf( * 2.People creat * n); printf( * * n); printf( * n); way=getch(); /*输入创建树的方法,1电脑自动建立,2人工手动建立*/ if(way!=2) way=1; /*其他数字默认自动建立*/ if(way=2) /*手动建立提示输入结点，例abc de f g */ printf( Please creat the tree: n); root=InitTree(1,320,150); system(pause); return root;/*生成二叉树，h表示层次，t表示横坐标，w表示结点左右子树的宽度，随机数n确定结点是空或非空，如n为0，则为空，但要限定确保结点数不少于三个*/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= ; else ch=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); /*遍历时显示每个结点的过程*/void DrawNode(Tree *t,int color) setcolor(RED); setfillstyle(SOLID_FILL,RED); fillellipse(t-x,t-y,10,10); setcolor(YEL