数据结构综合设计题目列表.ppt

1、数据结构实验时间安排,每周进行检查，汇报进展,1.每个题目每个同学独自完成，同一个宿舍的同学不选相同的题目。 2.完成后才用答辩的形式，对自己所做系统的功能、特色讲解，并能正确对老师指定的代码做出解释。同一个题目的同学，在同一时段答辩，以检查是否有相似性，以及就水平不同进行比较。 3.每个题目的难易不同，对应的成绩会不同；每个题目所做的功能及质量的不同，会打出不同的成绩。 4.每个功能的核心都用C语言实现，如果纯C实现，所有的东西都自己实现，除非必要的基本的函数调用一些，得分更高。,综合设计要求,综合设计题目列表,1.实体的描述:根据提供的数据,能显示该实体,并对实体进行裁剪等功能。（人数不限

2、） 该设计内容主要涉及到面、线、点的表示，主要用线性表链式存储方面的知识，会采用多级链表，因此要比书中相应的知识的复杂很多。 该题目出自教图形图像方面的老师，题目所涉及的内容会在大三、大四或毕业设计时使用。 建议能力强的同学，选择此题目。,2.提供手机号码的管理方案。（人数不限） 由于手机号码的特殊性，将号码组织成何种结构是关键。因此从如何组织逻辑结构、物理结构，实现哪些算法，如何实现，这些都需要设计者分析考虑。 功能主要实现在现实生活中真实的号码中查找指定的号码，能增加和删除号码，能遍历所有的号码，要求高效，用时短。 分析过程需要综合书中全部知识，实现可能只会使用书中部分知识。 因为没有任何

3、可以参考的方案，全部需要自己分析与考虑，建议能力强的同学选择此题目。,3.管理系统的设计与实现。（4人） 实现的管理系统要求功能较全，且能与现实生活接近考虑数据量大，如有上百万条的情况。 主要用线性表的知识（顺序与链式存储都会涉及），涉及查找与排序算法，文件的知识是必须。 这里综合用到数据结构的知识，都不复杂，但有些锁碎，建议想强化基本知识掌握的同学选此题目。,游戏中要考虑的因素:可以实现二维游戏,也可以是三维游戏。 二维游戏要求考虑:碰撞检测加截场景声音加载文件保存与加载鼠标拾取与操作地图之生成。 三维游戏要求考虑:碰撞检测骨骼动画之实现灵活摄像机设置粒子系统之实现地形生成天空生成动态流体之

4、模拟场景之渲染输入之交互处理。,4.飞机游戏的实现（2人） 该游戏的基本要求：飞机能飞，有声音，鼠标与键盘控制灵活、合理，能发射子弹，碰雷爆炸。,5.精灵动画之实现（2人）。,6.游戏中部分主要功能之模拟，如寻路功能、地图之生成之模拟。（2人）,游戏可以设计的简单，也可以复杂，这取决于你个人的能力，但界面一定要美观，操作方便。,7.一元多项式的各种运算（10人） 除了考虑书中已提供的加法功能外，可以实现更多的运算。 该算法主要涉及线性表的链式操作，是数据结构中最基本，也是日后应用最常用的操作，也是后续课程认为学生在这方面编程能力最差的一部分知识。 没有完整控制过链表的同学只能选择此题目，因为这

5、是最基本的知识，必须掌握。,8.迷宫求解。（2人） 主要利用栈实现，要求能动态生成迷宫，显示有几条路径，用图形界面显示最合适的路径。,9.离散事件模拟。（2人） 主要利用队列实现。要求能用图形界面显示状态。,10.计算器的实现。（4人） 主要利用栈实现表达式求值，要求功能与界面模拟WINDOWS计算器，支持鼠标。,11.记事本之文本编辑的实现。（3人） 要求功能与界面模拟WINDOWS记事本，支持鼠标，因为记事本功能较多，可以根据自己的能力模拟出部分功能，文本编辑这部分功能必须实现，主要利用串的知识。,12.建立索引词表。（2人） 主要利用串的知识实现。,13.所有矩阵的压缩存储实现。（2人）

6、 包括特殊矩阵与稀疏矩阵的压缩存储，并在上面实现一定的应用，比如显示与转置等。,14.二叉树遍历算法。 （3人） 要求实现前、中、后序、层序遍历的递归与非递归算法，及存储加索引的算法和在索引上的遍历算法。,15.树的遍历和树的计数（2人）。,16.对一西文文本提供最优的编、解码方案，并给出编码与解码结果。（3人） 建议已掌握并实现线性表操作的同学，但编程能力仍不算高的同学可选择此题目，毕竟书中已提供了主要源码，自己可发挥的余地较小。,17.给定一图，在遍历的基础上确定其是否是连通。（4人） 已掌握并实现线性表操作、编程有一定能力的同学，可选此题目。书中虽然有源码，但离实现有一些距离，加上老师没

7、有讲解，考验分析代码之能力。,18.给定一图，用两种方法求其最小生成树，确定其结果是否一致。（4人） 已掌握并实现线性表操作、编程有一定能力的同学，可选此题目。 书中提到的一个方法有源码，关于算法的讲解也很详细；另一个方法只有思想，完全没有代码，实现它考验有算法的基础上，如何表示与实现算法之能力。,19.给定一图，求其拓朴排序。（3人） 要求存储采用邻接矩阵与邻接链表两种方法，其入度为零的点可以采用进栈和进队列两种方法。尤其是书中未提到的方法必须实现。已掌握并实现线性表操作、编程有一定能力的同学，可选此题目。 要求以图形界面呈现结果。,20.给定一图，在其拓朴排序的基础上，求最关键路径。（4人

8、） 该算法虽然较复杂，涉及到的知识也比较多，但书中毕竟有源码，而且讲解也较为详细。已掌握并实现线性表操作、编程有一定能力的同学，可选此题目。 要求以图形界面呈现结果。,21.给定一图，求任意两点间的最短路径。（4人） 该算法有一定的复杂性，老师的讲解尽管不详细，但书中毕竟有源码。建议已掌握并实现线性表操作、编程有一定能力的同学，选此题目。 要求以图形界面呈现结果。,22.实现所有的静态查找表。（3人） 该部分算法较好理解，不太复杂，已掌握并实现线性表操作的同学，可选此题目。 要求最后关于各种静态查找表的性能比较得出一个结论。,23.实现所有的动态查找表。（4人） 该部分算法有一定的难度，尤其二叉排序树与平衡二叉树，涉及树的插入与删除等复杂操作。实现不易，尽管书中给出的代码较为详细 建议能力强的同学选择此题目。,24.实现所有的哈希函数构造法。（3人） 书中算法只有思想，没有代码，实现不易。 已掌握并实现线性表操作的同学，可选此题目。,25.实现所有哈希表的解决冲突的方法。（3人） 书中算法只有思想，没有代码，实现不易。 已掌握并实现线性表操作的同学，可选此