课程设计题目-数据结构.doc

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

1、注意：课设封面：课程名称填写：基础软件设计封皮日期填写：2013-12-23姓名，学号等信息填写自己的信息。一、要想得到优秀：只做（必做）题目：数据结构各章算法的演示系统 二、其他选题：第一部分：基本知识题（每人必选1题）1、线性表及其应用 （1）：顺序表基本操作验证 (创建，清空，判空，销毁，插入，删除，查找，排序，输出) （2）：单链表基本操作验证(创建，清空，判空，销毁，插入，删除，查找，排序，输出) （3）：单链表的归并合并算法和双链表的插入删除操作。 （4）：链表应用：已知非空线性链表第一个链结点的指针为list，写出下列各项操作的算法程序。（1）逆转该线性链表；（2）删除线性链表中

2、从左往右第一个数据为data的链结点；（3）删除从第i个链结点开始的连续k个结点。 要求：（1）设计一组输入数据并编写完整的程序。调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果。程序具有可扩展性。（2）要求设计的界面美观、合理、便于操作等，功能与实际应用系统紧密联系，系统结构合理构思巧妙、模块化程度高等。2、栈和队列其应用目的在于使读者深入了解栈和队列的特性，以便在实际问题背景下灵活运用他们；同时还将巩固对这两种结构的构造方法的掌握，接触较复杂问题的递归算法设计。（1）：算术表达式转波兰表达式和逆波兰表达式 （2）：栈列操作的验证（建栈、入栈、出栈、销毁栈） （3）：判

3、断表达式中括弧是否正确配对 （4）：队列元素倒置 （5）：判断字符串是否回文 （6）：字符串的基本操作（5个基本函数实现）3、树和二叉树及其应用 （1）：哈夫曼树的构造和哈夫曼编码 （2）：二叉树操作 1. 已知二叉树的前序、中序序列，恢复此二叉树； 2. 求二叉树高度、分支结点数和叶子结点数； 3. 插入结点到指定位置、删除指定结点； 4. 将二叉树中所有结点的左右子树交换； 5. 对二叉树进行层序、非递归中序遍历。4、各种排序算法的演示排序器（排序算法验证及评价）要 求：实现以下六种排序算法，将给定的不同规模大小的数据进行排序，并将排序结果分别存储到不同的空间中。1）、Shell排序；2）

4、、Quick排序 3）、插入排序； 4）、堆排序5）、归并排序； 6）、基数排序在实现排序算法1）4）时，统计数据元素比较的次数和交换的次数，进而对这四种算法在特定数据条件下的效率进行分析和评判。并统计每一种排序上机所花费的时间5、各种查找算法的演示第二部分：综合应用题（每人最少一个）1、宿舍管理查询软件 1、设计内容和要求任务：为宿舍管理人员编写一个宿舍管理查询软件, 程序设计要求： A. 采用交互工作方式 B. 建立数据文件 ，数据文件按关键字（姓名、学号、房号）进行排序(冒泡、选择、插入排序等任选一种) 查询菜单: (用二分查找实现以下操作) C. 按姓名查询D. 按学号查询E. 按房号

5、查询 打印任一查询结果（可以连续操作）2、迷宫求解任务：可以输入一个任意大小的迷宫数据，用非递归的方法求出一条走出迷宫的路径，并将路径输出；3、学生成绩管理系统 设计内容： 利用线性链表实现学生成绩管理系统，具体功能：输入、输出、插入、删除、查找、追加、读入、显示、保存、拷贝、排序、索引、分类合计、退出，并能在屏幕上输出操作前后的结果。设计要求：编程实现,界面友好。输出操作前后的结果。4. 敢死队问题 有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个

6、战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。 排长是不愿意去的，假设排长为1号，请你设计一程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。 要求：至少采用两种不同的数据结构的方法实现。如果采用三种以上的方法者，可加分。5、校园导游咨询任务：设计一个校园导游程序，为来访的客人提供各种信息查询服务。基本要求：设计学校的校园平面图，所含景点不小于10个。以图中个顶点表示校园各个景点，存放景点名称，带好，简介等信息；边表示路径，存放路径长

7、度等相关信息。为来访客人提供图中任意景点相关信息的查询。为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。实现提示：一般情况下，校园的道路是双向通行的，可设校园平面是一个无向网。顶点和边均含有相关信息。6、文章编辑功能：输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符，共N行；要求（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小

8、写的英文字母、任何数字及标点符号。输出形式：（1）分行输出用户输入的各行字符；（2）分4行输出全部字母数、数字个数、空格个数、文章总字数（3）输出删除某一字符串后的文章； 7、运动会分数统计问题描述：参加运动会有n个学校，学校编号为1n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1m，女子m+1m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m=20,n=20）功能要求：1).可以输入各个项目的前三名或前五名的成绩；2)能统计各学校总分，3)可以按学校编号、学校总分、男女团体总分排

9、序输出；4).可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。规定：输入数据形式和范围：20以内的整数（如果做得更好可以输入学校的名称，运动项目的名称）输出形式：有中文提示，各学校分数为整形界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构；测试数据：要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的

10、稳定。测试数据及测试结果请在上交的资料中写明；8. 通讯录的制作模块要求：第一个模块主函数main()的功能是：根据选单的选项调用各函数，并完成相应的功能。 第二个模块Menu()的功能是：显示英文提示选单。第三个模块Quit()的功能是：退出选单。 第四个模块Create()的功能是：创建新的通讯录。 第五个模块Add()的功能是：在通讯录的末尾，写入新的信息，并返回选单。第六个模块Find()的功能是：查询某人的信息，如果找到了，则显示该人的信息，如果未找到，则提示通讯录中没有此人的信息，并返回选单。 第七个模块Alter()的功能是：修改某人的信息，如果未找到要修改的人，则提示通讯录中没有此人的信息，并返回选单。 第八个模块Delete()的功能是：删除某人的信息，如果未找到要删除的人，则提示通讯录中没有此人的信息，并返回选单。 第九个模块List()的功能是：显示通讯录中的所有记录。;设计要求：1) 每条信息至包含 ：姓名（NAME ）、性别(GENDER)、电话（TEL） 、城市（CITY）邮编（EIP）几项。2) 作为一个完整的系统，应具有友好的界面和较强的容错能力9、题目自选