创新申请(陈成)

项目类别项目批准号 华南农业大学大学生科技创新活动项目申请书项目名称： 数据结构与算法设计入门助手 申 请 人： 陈 成 所在院部： 信息学院 专业年级： 2003级计算机科学与技术班 联系电话：指导教师: 职称 申报日期： 二 五 年 四 月 二十 日 一、简表项目简况项目名称数据结构与算法设计入门助手 项目类别A、文科类； B、理科类；申请经费1500元起止年月2005年七月项目组成员姓 名性别出生年月年级专业班级所在学院上学年综合测评分项目中的分工本人签字陈成男84年6月03级计算机2班信息组长何子右男84年10月03级计算机2班信息组员黄泽彬男84年7月03级计算机2班信息组员指导教师情况姓名性别学位职称研究方向授课名称项目简介本项目(“数据结构与算法设计入门助手”)实则是一个软件，确切来说是一个应用程序。它的内容比较多，大体分为两个部分。一是演示部分，包括基本数据结构的演示和教学（线性表、栈、队列、串、二维数组、广义表、树与二叉树、图、查找和排序）这个部分是一般老师教学软件和课件所具有的，所以还不能体现创新，本程序之所以有这个部分是为了丰富内容，并且我们采用比较不同于一般教学软件的表现手法在演示过程中我们要求用户一步一步自己操作（插入、删除等），并添加声音等使之更为生动（而且我们的用户界面也力求生动）。二是比较部分，主要是一些经典算法题目的设计和比较还有教学。以下容我略为介绍：首先有“七种排序算法”的时间复杂度的比较（这里我们使用TC和VC实现两个演示版本，TC版本的设置一个计时器，七种排序由用户逐个选择然后计时器记录其时间；VC版的我们使用多线程，即七种算法同步执行，以观察七种排序先后完成次序。）。第二有“汉诺塔问题”的递归算法与非递归算法的时间复杂度与空间复杂度的比较。然后有“0-1背包”问题的动态规划解法、回溯解法及分支限界解法的比较。接下来还有“旅行售货员问题”（回溯法、分支限界法），“批作业处理调度问题”（回溯法、分支限界法），“N后问题”（回溯法、Las Vegas算法），“装载问题”（贪心算法、回溯法、分支限界法），“迷宫问题”（四个方向迷宫与八个方向迷宫的单条路径及所有路径），“大整数的加减法乘除”（TC版、VC版），“学籍管理系统”（TC版、VC版），“图书馆管理系统”（TC版、VC版）。对于所有的算法我们都会给出思路和流程图并附以C和C+两个版本的源代码，并可能附以一些稀奇新鲜的算法作欣赏（如“迷宫问题”就有一个很新鲜的“DNA算法”）。由于内容比较多，所以我们会设计良好的用户使用界面，就像普通的windows应用程序一样，用鼠标和按钮给用户提供操作，并提供适当的键盘快捷键。程序的开头和结尾我们打算添加一段动画，吸引用户眼球；用户每学习或浏览完一个算法我们也打算添加一些音乐、或者动画（搞笑的），甚至是小游戏等（如“贪食蛇”和“二十四点”等）以供消遣。程序设计语言我们选择C+，图片的设计和处理我们使用Photoshop，而动画的设计和添加我们则打算用OpenGL(而不是Flash，因为使用OpenGL的过程本身就是一个程序设计的过程，而我们这里的主题是程序设计)。至于我们添加的动画、声音、图片、还有小游戏等我们都会在程序的附录里给出一个详细的制作说明，也就是说我们是“开放源码”的（也许有点言重了）。因为我们的主题是程序设计，教授初学者基本的算法于是有兴趣的同学自然就可以通过我们“附录”里的内容学习简单的图形用户界面的小游戏的制作了（相信这也是对刚学完语言又对Windows深深向往的同学有帮助）。还有一点要提及的就是，我们刚才所谓的“附录”也是本程序的一部分，即可看作“第三部分”的主题（而不是仅仅在一个word或txt文档里的简单介绍）。二、立项依据（项目的意义、现状分析）有冲动要立这个项目并决心要做这个项目是因为：在大一对C语言的学习和大二对数据结构的学习中，在参加学院程序设计比赛的经验中，在对Windows的早期深深向往于是自学又走了很多弯路的教训中我们深深感觉到如果有个人来引导一下，那会多么的事半功倍！（当然不是说我们的老师没有引导我们，相反我们的老师都做得很好并给了我们很多学习的建议和帮助，在此先深深感谢！但老师并不是总是有时间的，而且对一些害羞的同学他就未必喜欢问老师。）所以这个软件只适合大一、大二的初学者，并就是为程序设计的初学者而设计的，如果高年级的学生想看它，或者会不禁一呻，然则也无不可，温故而知新嘛。低年级的学生有很多都想参加程序设计比赛而又因心有余而力不足于是望而却步的，信息学院暑假开设的程序设计免费培训班给这些同学提供了很好的学习机会但是我们以为可以做得更好，所以心血来潮要做这个软件，希望对程序设计感兴趣的同学有所帮助。（当然首先声明一点，我们的程序设计水平本身也不好，所以在写这个软件的过程中我们也是在学习和补充自己。）三、项目研究的基本内容与实施方案项目研究的基本内容和实施方案是：数据结构算法的演示和一些经典算法设计问题的设计与其不同实现方法间的比较，并且注重的是教学，即如何运用通俗易懂的语言去教会初学者一些基本的算法设计方法和技巧（其实我们也是初学者，以初学者去教初学者，我们认为是可行的，就像同学间针对某一问题进行讨论一样。）它的内容详细地讲有两个部分，并一个附加部分。具体如下所述：一是演示部分，包括基本数据结构的演示和教学（线性表、栈、队列、串、二维数组、广义表、树与二叉树、图、查找和排序）这个部分是一般老师教学软件和课件所具有的，所以还不能体现创新，本程序之所以有这个部分是为了丰富内容，并且我们采用比较不同于一般教学软件的表现手法在演示过程中我们要求用户一步一步自己操作（插入、删除等），并添加声音等使之更为生动（而且我们的用户界面也力求生动）。二是比较部分，主要是一些经典算法题目的设计和比较还有教学。以下容我略为介绍：首先有“七种排序算法”的时间复杂度的比较（这里我们使用TC和VC实现两个演示版本，TC版本的设置一个计时器，七种排序由用户逐个选择然后计时器记录其时间：VC版的我们使用多线程，即七种算法同步执行，以观察七种排序先后完成次序。）。第二有“汉诺塔问题”的递归算法与非递归算法的时间复杂度与空间复杂度的比较。然后有“0-1背包”问题的动态规划解法、回溯解法及分支限界解法的比较。接下来还有“旅行售货员问题”（回溯法、分支限界法），“批作业处理调度问题”（回溯法、分支限界法），“N后问题”（回溯法、Las Vegas算法），“装载问题”（贪心算法、回溯法、分支限界法），“迷宫问题”（四个方向迷宫与八个方向迷宫的单条路径及所有路径），“大整数的加减法乘除”（TC版、VC版），“学籍管理系统”（TC版、VC版），“图书馆管理系统”（TC版、VC版）。对于所有的算法我们都会给出思路和流程图并附以C和C+两个版本的源代码，并可能附以一些稀奇新鲜的算法作欣赏（如“迷宫问题”就有一个很新鲜的“DNA算法”）。由于内容比较多，所以我们会设计良好的用户使用界面，就像普通的windows应用程序一样，用鼠标和按钮给用户提供操作，并提供适当的键盘快捷键。程序的开头和结尾我们打算添加一段动画，吸引用户眼球；用户每学习或浏览一个算法我们也打算添加一些音乐、或者动画（搞笑的），甚至是小游戏等（如“贪食蛇”和“二十四点”等）以供消遣。程序设计语言我们选择C+，图片的设计和处理我们使用Photoshop，而动画的设计和添加我们则打算用OpenGL(而不是Flash，因为使用OpenGL的过程本身就是一个程序设计的过程，而我们这里的主题是程序设计)。至于我们添加的动画、声音、图片、还有小游戏等我们都会在程序的附录里给出一个详细的制作说明，也就是说我们是“开放源代码”的（也许有点言重了）。因为我们的主题是程序设计，教授初学者基本的算法于是有兴趣的同学自然就可以通过我们“附录”里的内容学习简单的图形用户界面的小游戏的制作了（相信这也是对刚学完语言又对Windows深深向往的同学有帮助）。还有一点要提及的就是，我们刚才所谓的“附录”也是本程序的一部分，即可看作“第三部分”的主题（而不是仅仅在一个word或txt文档里的简单介绍）。具体的时间安排是：我们预计主要利用暑假的时间去做（因为暑假之前我们要忙于准备英语四级考试和期末考试，另还有数据结构课程设计和操作系统的几实验报告作业要做），并争取在今年（05年）国庆节之前完工。因为很多的内容我们都已学习过或者自学过，所以关键问题就是如何将他们组合一起并如何建立美观的图形用户界面，还有就是声音、图画、动画和小游戏的设计和添加。最后的效果是我们将它压缩成一个安装的可执行文件（Setup.exe）的形式。四、预期成果预期成果就是完成如前所述的方便用户使用的一个应用软件。我们的每一个设计都力从方便用户的角度去考虑。以下是Powerpoint教学课件上的一个交互界面（我们会用作参考，设计出更易用美观的GUI）：以下是陈成同学以前做的一个简陋的界面，用来比较七种排序算法的时间复杂度（我们预想中的软件自然要比它精美得多，功能强大得多）：五、本项目的特色与创新之处特色与创新之处是：它把数据结构与经典算法设计（回溯、动态规划、分支限界、贪心算法等）的教学综合在了一起，并且为有兴趣用VC或C+Builder做indows应用程序的同学提供了一些方法与技巧。还有就是它寓学于乐，提供了一些简单的小游戏和一些搞笑的动画。（如果可能我们还想把它做成中文版和英文版两个版本，在用户安装本软件时弹出一个对话框，由用户选择他是需要安装中文版或者英文版，毕竟学校配的数据结构教材就是纯英文的，不过翻译成英文版我们实在是没有信心，因为英语水平实在有限，还有就是时间问题。不过国庆之前如果我们交得出它的中文版的话，那么国庆之后我们就会尝试翻译它的英文版本，并对之做一些优化和改进然后将中文、英文版本集成到一个安装文件，并取一个好听的名字“数据结构与算法设计入门助手.0”）。六、经费预算 主要是购买参考书的费用,其中有两部特别需要:Windows 程序设计：第5版（上下册）,