数据结构课程设计大纲.doc

《数据结构课程设计大纲.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计大纲.doc（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构课程设计教学大纲（Data Structure Curriculum Design）制定单位：信息科学学院计算机系制 定 人：王瑜审 核 人：江效尧编写时间：2011年10月18日第一部分 课程概述一、基本信息（一）课程代码（二）课程属性、学分、学时本课程属于计算机科学与技术专业的学科基础课，2学分，共30学时（三）适用对象本课程面向对象为计算机科学与技术专业的本科生（四）先修课程与知识准备先修课程：程序设计基础，数据结构二、课程简介数据结构课程设计是计算机科学与技术专业集中性的实践教学环节之一，是学习完数据结构课程后进行的一次全面的综合练习。三、教学目标数据结构课程设计是计算机科学与

2、技术专业专业本科生的一门必修课程。通过本课程学习，其目的就是要达到理论与实际应用相结合，使学生能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养良好的程序设计技能，并强化学生的团队分工与合作能力。四、师资团队王 瑜陈一飞五、教学资源教材：1. 数据结构（C语言版）严蔚敏，吴伟民等 编著 清华大学出版社，2007 2. 数据结构课程设计苏仕华 编著 机械工业出版社，2005参考文献：1. 数据结构（C语言版）唐国民等 编著 清华大学出版社，2009.9 2. C语言数据结构程序设计王开铸等 编著 哈尔滨工业大学出版社，2003.33. 数据结构课程设

3、计滕国文 编著 清华大学出版社出版，2010.9专题网站：1. http:/www.cs.berkeley.edu/jrs/61b/2. http:/172.17.14.75实践性教学资源：竞慧东楼实验室六、教学要求1.要求教师具有计算机相关的专业背景，熟悉程序设计、编译原理、操作系统等相关课程的内容。2.要求教师开设过数据结构课程，在开课之前对课程设计内容有深入的理解。3.课程组定期进行教学研讨活动，各团队成员应该按时参加，研究教学规律，交流教学经验，探讨教学内容，反映在教学中出现的问题，群策群力，共同提高教学质量。4.在教学过程中，应发给学生包括教学大纲和课程设计报告模板等在内的教学文档。

4、七、学习要求1.要求同学独立完成（若有两位或以上的同学采用完全相同的课程设计报告或源代码相同，则这些同学全部不合格；若有两位或以上的同学的课程设计报告或源代码雷同，则这些同学最终成绩等级均下降一个等级）。2.按时到机房上机，遵守机房纪律，不得在课上处理与本门课程无关的事情。3.每位学生提交打印装订好的课程设计报告和电子版的课程设计报告和源代码（例如张三同学的学号是，则要提交“张三.doc”和“张三.cpp”两个文件。注意：所有源代码拼成一个.cpp文件 ），课程设计报告的格式见附录，内容包括自己所选择的课程设计题目、课程设计内容、解决的思路、算法思想、实现的功能的描述、数据结构的说明、主程序的

5、流程图和主要功能模块流程图及说明、用户操作说明、部分运行结果等等。八、考核方案1个人考核和小组考核都为优秀的同学最终成绩评定为优秀；2. 个人考核和小组考核有一个为优秀，另一个为良好的同学最终成绩评定为良好；3个人考核和小组考核都为良好的同学最终成绩评定为良好；4. 个人考核和小组考核有一个为不及格的同学最终成绩评定为不及格；5. 个人考核和小组考核的成绩等级情况不在上述四者中的，最终成绩均评定为合格；九、参考进度1第一周，完成个人任务，并出具个人任务的课程设计报告；2第二周，完成小组任务； 3第三周，测试系统，完成小组课程设计报告，准备.ppt文件和最后的答辩。第二部分 课程内容一、个人任务

6、 每位同学必须完成(1) 直接插入排序 (2) 折半插入排序 (3) 冒泡排序 (4) 简单选择排序 (5) 快速排序 (6) 堆排序 (7) 归并排序以上这些算法，并完成这些算法的性能分析（从时间复杂度和空间复杂度两个方面进行比较分析）报告。 二、小组任务1运动会分数统计（限3人完成）【系统任务】参加运动会有n个学校，学校编号为1n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1m，女子m+1m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m=20,n=20）【功能要求】1)可以输

7、入各个项目的前三名或前五名的成绩；2)能统计各学校总分，3)可以按学校编号或名称、学校总分、男女团体总分排序输出；4)可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。5)数据存入文件并能随时查询 6)规定：输入数据形式和范围：可以输入学校的名称，运动项目的名称【输出形式】有合理的提示，各学校分数为整形【界面要求】有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。【存储结构】学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指明

8、你用到的存储结构；【测试数据】要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；2飞机订票系统（限3人完成）【系统任务】通过此系统可以实现如下功能：录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；订票：（订票情况可以存在一个数据文件中，结构自己设定）可以订票，如果该航班已经无票，可以提供相关可选择航班；退票： 可退票，退票后修改相

9、关数据文件；客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。修改航班信息：当航班信息改变可以修改航班数据文件【功能要求】根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能；3文章编辑（限3人完成）【系统任务】输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符，共N行；【功能要求】1）分别统计出其中英文字母数和空格数及整篇文章总字数；2）统计某一字符串在文章中出现的次数，并输出该次数；3）删除某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、

10、任何数字及标点符号。【输出形式】1）分行输出用户输入的各行字符；2）分4行输出全部字母数、数字个数、空格个数、文章总字数；3）输出删除某一字符串后的文章。4宿舍管理查询软件（限3人完成）【系统任务】为宿舍管理人员编写一个宿舍管理查询软件；【功能要求】1）采用交互工作方式；2）建立数据文件，数据文件按关键字（姓名、学号、房号）进行排序(冒泡、选择、插入排序等任选一种)；3）查询菜单: (用二分查找实现以下操作)A.按姓名查询 B.按学号查询 C.按房号查询4）打印查询结果（可以连续操作）5校园导航问题（限3人完成）【系统任务】设计审计学院校园平面图，有两个校区，在这些校区内选10个以上的建筑物、

11、办公室、宿舍等地名。以图中顶点表示校园内各地名，存放地名名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。【功能要求】1）为来访客人提供图中任意地名相关信息的查询。2）为来访客人提供任意地名的问路查询，即查询任意两个地名之间的一条最短路径。 【实现提示】一般情况下，校园的道路是双向通行的，可设计校园平面图是一个无向网。顶点和边均含有相关信息。6图书借阅管理系统（限3人完成）【系统任务】设计一个计算机管理系统完成图书管理；【功能要求】1）每种书的登记内容包括书号、书名、著作者、现存量和库存量；2）对书号建立索引表（线性表）以提高查找效率；3）采编入库：新购一种书，确定书号后，登记到图

12、书帐目中，如果此书已有，则只将库存量增加；4）借阅：如果一种书的现存量大于0，则借出一本，登记借阅者的书证号和归还期限，改变现存量；5）归还：注销对借阅者的登记，改变该书的现存量。 7简单的职工管理系统（限3人完成）【系统任务】对单位的职工进行管理，包括插入、删除、查找、排序等功能。【功能要求】职工对象包括姓名、性别、出生年月、工作年月、学历、职务、住址、电话等信息。1）新增一名职工：将新增职工对象按姓名以字典方式职工管理文件中；2）删除一名职工：从职工管理文件中删除一名职工对象；3）查询：从职工管理文件中查询符合某些条件的职工；4）修改：检索某个职工对象，对其某些属性进行修改；5）排序：按某

13、种需要对职工对象文件进行排序；【实现提示】1）职工对象数不必很多，便于一次读入内存，所有操作不经过内外存交换；2）由键盘输入职工对象，以文件方式保存。程序执行时先将文件读入内存；3）对职工对象中的姓名按字典顺序进行排序；4）对排序后的职工对象进行增、删、查询、修改、排序等操作。8通讯录的制作（限3人完成）【系统任务】用双向链表作数据结构，编写一个通讯录管理系统；【功能要求】本系统应完成一下几方面的功能：1）输入信息，每条信息至少包含：姓名、街道、城市、邮编、国家和电话；2）显示信息；3）查找以姓名作为关键字；4）删除信息；5）保存信息；6）作为一个完整的系统，应具有友好的界面和较强的容错能力9

14、哈夫曼编码/译码器（限3 人完成）【系统任务】设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。【功能要求】1）将权值数据存放在数据文件中，文件名为data.txt，位于执行程序的当前目录中；2）初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；3）编码：利用建好的哈夫曼树生成哈夫曼编码；4）输出编码；5）设字符集及频度如下表（同学也可以自己设置字符和频度）：字符 空格 A B C D E F G H I J K L M 频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20字符 N O P Q R S T U

15、V W X Y Z频度 57 63 15 1 48 51 80 23 8 18 1 16 16）译码功能；7）显示哈夫曼树；8）界面设计的优化。10散列表的设计与实现（限3人完成）【系统任务】设计散列表实现电话号码查找系统。【功能要求】1）设每个记录有下列数据项：电话号码、用户名、地址；2）从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；3）采用一定的方法解决冲突；4）查找并显示给定电话号码的记录；5）查找并显示给定用户名的记录；6）设计不同的散列函数，比较冲突率；7）在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。 11利用栈求表达式的值，本系统可

16、供小学生作业，并能给出分数。（限2人完成）【系统任务】建立试题库文件，随机产生n个题目；题目涉及加减乘除，带括弧的混合运算；随时可以退出；保留历史分数，能回顾历史，给出与历史分数比较后的评价。12数制转换问题（限2人完成） 【系统任务】任意给定一个M进制的数x ，请实现如下要求1）求出此数x的10进制值（用MD表示）2）实现对x向任意的一个非M进制的数的转换。3）至少用两种或两种以上的方法实现上述要求（用栈解决，用数组解决，或其它方法）。13图的遍历的实现（限2人完成）【系统任务】建立图结构，利用多种算法对实现遍历；【功能要求】1）先任意创建一个图；2）图的DFS,BFS的递归和非递归算法的实

17、现；3）要求用有向图和无向图分别实现；4）要求用邻接矩阵、邻接表多种结构存储实现。14稀疏矩阵应用（限2人完成）【系统任务】实现三元组，十字链表下的稀疏矩阵的加、转、乘的实现；【功能要求】1）稀疏矩阵的存储2）稀疏矩阵加法3）矩阵乘法4）矩阵转置15树的应用（限2人完成）【系统任务】实现树与二叉树的转换的实现。以及树的前序、后序的递归、非递归算法，层次序的非递归算法的实现，应包含建树的实现；16串的查找和替换（限2人完成）【系统任务】打开一篇英文文章，在该文章中找出所有给定的单词，然后对所有给定的单词替换为另外一个单词，再存盘；【功能要求】1） 要用三种不同的匹配算法完成上述系统任务；2） 完

18、成上述三种算法的匹配时间的比较。17约瑟夫环 （限2人完成）【系统任务】编号为1，2 n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个开始重新从1报数，如此下去，直至所有人全部出列为止，设计一个程序求出出列顺序；【功能要求】1）利用单循环链表作为存储结构模拟此过程；2）键盘输入总人数、初始报数上限值m及各人密码；3）按照出列顺序输出各人的编号。 18构造可以使n个城市连接的最小生成树 （限3人完成）【系统任务】给定一个

19、地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价；【功能要求】1）城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价；2）表示城市间距离网的邻接矩阵（要求至少6个城市，10条边）；3）最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。 19客户消费积分管理系统（限3人完成）【系统任务】针对客户的消费情况，进行客户管理，根据客户的消费积分对客户实行不同程度的打折优惠；【功能要求】1）采用一定的存储结构进行客户信息的存储；2）对客户的信息可以进行修改、删除、添加；3）能够根据消费情况进行客户积分的计算；4）根据积分情况实行不同程度的打折优惠；20产品进销存管理系统（限3人完成）【系统任务】针对某一种行业的库房的产品进销存情况进行管理；【功能要求】1）采用一定的存储结构对库房的货品及其数量进行分类管理；2）可以进行产品类的添加、产品的添加、产品数量的添加；3）能够查询库房每种产品的总量、进货日期、销出数量、销售时间等。