09级《数据结构》课程设计任务书.docx

1、09级数据结构课程设计任务书09级数据结构课程设计任务书一课程设计的任务本次设计是为加强学生的软件编程能力而进行的专门训练。选题考虑到学生在数据结构中学过的各种算法、数据组织方式进行选题，考虑数据结构算法所涉及的操作系统、网络、编译方法等中的实例，进行设计。下面是课程设计待选题目共43题。按学号相应选题，如：学号为01，则选择第1题。分析题目，完成相应题目的程序设计。1、商品管理问题描述：以链表结构的有序表表示某商场家电部的库存模型，当有提货或进货时需要对该链表及时进行维护，每个工作日结束以后，将该链表中的数据以文件形式保存，每日开始营业之前，须将文件形式保存的数据恢复成链表结构的有序表。实现

2、要求：链表结构的数据域 包括家电名称、品牌、单价和数量，以单价的升序体现链表的有序性。程序功能包括：初始化、创建表、插入、删除、更新数据、查询及链表数据与文件之间的转换等。2、编程整理表达式键盘输入一个含有括号的四则运算表达式，可能含有多余的括号，编程整理该表达式，去掉所有多余的括号，原表达式中所有变量和运算符相对位置保持不变，并保持与原表达式等价。3、个人帐簿管理问题描述：个人帐簿管理系统记录某人每月的全部收入及各项开支情况，包括食品消费，房租，子女教育费用，水电费，医疗费，储蓄等。进入系统后可以输入和修改某月的收支情况，可以对每月的开支从小到大进行排序，可以根据输入的月份查询每月的收支情况

3、。实现要求：1 初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2 完成最低要求：建立一个文件，包括某人5个月的收支情况，能对文件中的信息进行扩充（追加），修改和删除；3 进一步要求：完成对每月的开支排序，以及完成系统查询功能。有兴趣的同学可以自己扩充系统功能。4、实现：连通无向图的非递归遍历。5、招聘模拟。 问题描述：某集团公司为发展生产向社会公开招聘m个工种的工作人员，每个工种各有不同的编号(o，1，3，m一1)和计划招聘人数，参加应聘的人数有n个(编号为o，1，2，n一1)。每位应聘者可以申报两个工种，并参加公司组织的考试。公司将按应聘者的成绩，从高到低的顺序排队录取。公司

4、的录取原则是：从高分到低分依次对每位应聘者先按其第一志愿录取；当不能按第一志愿录取时，便将他的成绩扣去5分后，重新排队并按其第二志愿考虑录取。 实现要求：要求程序输出每个工种录用者的信息(编号、成绩，以及落选者的信息(编号、成绩)。 程序设计思路：程序中按应聘者的成绩从高到低的顺序排队录取。如果在第一志愿队列中落选，便将他的成绩扣去5分后重新排队，并按其第二志愿考虑录取。程序为每个工种保留一个录取者的有序队列。录取处理循环直至招聘额满或已对全部应聘者都做了录用处理。6、求矩阵的所有马鞍点。矩阵A中的元素若满足：Ai,j是第i行中值最小的元素，且又是第j列中值最大的元素，则称元素Ai,j为该矩阵

5、的一个马鞍点。求出mn矩阵的所有马鞍点。7、最少换车次数问题。问题描述: 设某城市有n个车站，并有m条公交线路连接这些车站。设这些公交车都是单向的，这n个车站被顺序编号为0-n-1。编号程序，输入该城市的公交线路数，车站个数，以及各公交线路上的各站编号。 实现要求：求得从站0出发乘公交车至站n一1的最少换车次数。 程序设计思路：利用输入信息构建一张有向图G(用邻接短阵g表示)，有向图的顶点是车站，若有某条公交线路经i站能到达j站，就在顶点i到顶点j之间设置一条权为1的有向边i,j)。这样，从站x至站y的最少上车次数便对应于图G中从点x至点y的最短路径长度。而程序要求的换车次数就是上车次数减1。

6、8、实现： 拓扑排序9、图的算法实现问题描述：图的存储结构的建立、Prim、Kruskal、Dijkstra和拓扑排序算法。实现要求：（1）将图的信息建立文件；（2）从文件读入图的信息，建立邻接矩阵和邻接表；（3）实现Prim、Kruskal、Dijkstra和拓扑排序算法。10、实现二叉树的叶子结点按从左到右的顺序连成一个单链表请设计一个算法，把二叉树的叶子结点按从左到右的顺序连成一个单链表。二叉树用二叉链存储，链接时用叶子结点的rchild 域存放指针。11、模拟实现五子棋在围棋比赛中，某一方（假设为黑方）在棋盘的某个位置（i，j）下子后，有可能提取对方（白方的一串子）。以W1919表示一

7、个棋盘，若Wij=0表示在位置(i,j)上没有子，Wij=1表示该位置上的是黑子，Wij=-1表示该位置上是白子。模拟实现五子棋 过程。12、实现：判别给定的二叉树是否为二叉排序树。13、文章编辑问题描述：输入一页文字，程序可以统计出文字、数字、空格的个数。静态存储一页文章，每行最多不超过80个字符，共N行；实现要求：（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现的次数，并输出该次数；（3）删除某一子串，并将后面的字符前移。存储结构使用线性表，分别用几个子函数实现相应的功能；输入数据的形式和范围：可以输入大写、小写的英文字母、任何数字及标点符号。输出形

8、式：（1）分行输出用户输入的各行字符；（2）分4行输出全部字母数、数字个数、空格个数、文章总字数（3）输出删除某一字符串后的文章14、实现：对一个存储为邻接表的图，给出求其所有连通分量。15、管道铺设设计问题描述：N(N10)个居民区之间需要铺设煤气管道。假设任意两个居民区之间都可以 铺设煤气管道，但代价不同。实现要求：事先任意两居民区之间铺设煤气管道的代价存入磁盘文件中。设计一个最佳方案使得这N个居民区之间铺设煤气管道所需代价最小，并将结果以图形方式在屏幕上输出。16、排序算法的实现与比较问题描述：编程实现希尔、快速排序算法，并利用程序统计每种算法的执行时间。实现要求：随机产生10000、5

9、0000、 100000、 200000个待排数据存入磁盘文件，从磁盘文件读入待排数据进行排序，并将排序结果写入另一个文件中。17、实现排序：设一单向链表的头指针为head,链表的记录中包含着整数类型的key域,试设计算法,将此链表的记录按照key递增的次序进行就地排序.（不允许使用数组做辅助存储）18、统计C程序单词的个数问题描述：扫描c源程序，利用hash技术和二分查找技术统计该源程序中的关键字出现的频度，并比较各自查找的次数。实现要求：（1）、先用Hash表存储c语言中32个关键字，再扫描c源程序取出每个单词，利用Hash查找技术统计该程序中的关键字出现的频度。发生Hash冲突用线性探测

10、法解决。设Hash函数为：Hash（key）=(key的第一个字母序号)*100+(key的最后一个字母序号) MOD 41。（2）、用顺序表存储c语言中的关键字，把c源程序取出每个单词利用二分查找技术统计该程序中的关键字的出现频度。19、擦数游戏在黑板上从1开始写出一组连续的自然数，然后擦去其中的一个数k，其余的数的平均值为a/b(a,b为整数)。试编写程序求出被擦去的数k。20、医院选址问题描述：有n个村庄，现要从这n个村庄中选择一个村庄新建一所医院，使其余的村庄到这所医院的距离总体来说较短，设计较合理。实现要求：可以将问题抽象为有n个接点，在这n个接点之间建立一个无向图，边上的权值w(i

11、,j)表示村庄i到j之间道路的长度， 在无向图中n个顶点之间，最多可能设置n(n-1)/2条线路，如何在这些线路中选择n-1条线路，以使总的线路最短？对于n个顶点的连通网可以建立许多不同的无向图，每一个无向图都可以表示一个道路网，其中要选择一个最优图，使图上各边之小。21、求二叉树根结点到指定结点的路径。22、保龄球记分系统 问题描述：保龄球一局分10轮，每轮可按球一次或多次，以击倒的球数为依据得分。一局得分为10轮得分之和，而每轮的得分不仅与本轮滚球情况有关，还可能与后续一两轮的滚球情况有关。即某轮某次滚球击例的球数不仅要记入本轮得分，还可能记入前一两轮得分。具体的滚球规则和记分规则如下。

12、(1)若一轮的第一次该球就击倒10个球，则本轮不再滚球(若是第10轮则还需另加两次滚球)，该轮的得分为本次击倒球数10与以后两次滚球所击倒的球数之和。 (2)若某一轮的第一次滚球未击倒10个球，则可对剩下的球再击一次。如果两次击倒10个球，则本轮不再滚球(若是第10轮则还需另加一次滚球)，该轮的得分为本次击倒球数10与下一次滚球所击倒的球数之和。 (3)若某一轮的两次滚球未击倒10个球，则本轮不再滚球。该轮的得分为本轮击倒的球数。 实现要求：程序要求输出10轮中各轮的第一次得分和第二次得分，以及各轮得分和总分。 程序设计思想 程序交互地逐轮输入一次滚球击倒的球数ball1和ball2，计算该轮

13、得分score和累计得分total。为记录因一轮击倒10个球，还暂时不能计算该轮的得分和累计总分的情况，程序引入变量frame，用来记录当前已完成完整计算的轮次，程序每输入一次滚球击倒球数，就检查还未完成完整计算的轮次，并计算之。23、修改起泡排序试修改起泡排序，以交替的正、反两个方向进行扫描。即第一趟把排序码最大的记录放到最末尾，第二趟把排序码最小的记录放到最头上。如此反复进行。24、运动会分数统计：问题描述：参加运动会有n个学校，学校编号为1n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1m，女子m+1m+w。不同的项目取前五名或前三名积分；取前五名的积分分别为：7、5、3、2、

14、1，前三名的积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m=20,n=20）实现要求：1). 可以输入各个项目的前三名或前五名的成绩；2)能统计各学校总分，3)可以按学校编号、学校总分、男女团体总分排序输出；4).可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学校。规定：输入数据形式和范围：20以内的整数（如果做得更好可以输入学校的名称，运动项目的名称）25、堆排序的实现：在顺序结构上完成,先建堆然后重建堆,最后实现全部排序26、公园的导游图问题描述：给出一张某公园的导游图，游客通过终端询问可知：从某一景点到另一景点的最短路径。游客从公园大门进入，

15、选一条最佳路线，使游客可以不重复地游览各景点，最后回到出口（出口就在入口旁边）。实现要求：1 初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2 完成最低要求：建立一个文件，包括5个景点情况，能完成遍历功能；3 进一步要求：进一步扩充景点数目，画出景点图，有兴趣的同学可以自己扩充系统功能。27、万年历：通过给定的年，求该年的日历，闰年算法：Y%4 &!Y%100|Y%4000 28、归并排序算法：用两路归并算法，实现N个无素的排序29、学籍管理 对学生、课程、成绩分别建立三个数据文件（学生、课程、成绩属性自定）。查询某个学生的选课情况成绩不及格的学生情况对课程名按不及格学生人数进

16、行排序建立模拟索引。30、最短路径：求图中任意两点间的最短路径 31、旅游交通查询系统：实现功能：火车信息查询、最短路径查询、火车信息编辑、读入修改信息、查看火车信息、查看城市信息。每个功能中又有一些小功能，如火车信息查询中有：按车次查询、按出发地与目的地查询（其中又有最快、最省钱、全部选择）中转站查询、查看火车信息，火车信息编辑又包括：添加火车信息、删除火车信息、查看火车信息、保存火车信息功能。32、房产信息管理 自己建立数据文件的方式对房产信息进行如下管理：查询修改排序33、供货信息管理自己建立数据文件的方式对供货信息进行如下管理：查询修改排序。商店货架以栈的形式摆放商品，生产日期越近的越

17、靠近栈底,出栈是从栈顶取货，一天营业结束，如果货架不满,则需上货，如果直接将商品摆放到货架上，则会使生产日期越近的越靠近栈顶.这就需要倒货架，仍使生产日期越近的越靠近栈底。写出货物进栈、出栈算法。34、银行业务模拟问题描述： 客户业务分为两种。第一种是申请从银行得到一笔资金，即取款或借款。第二种是向银行投入一笔资金，即存款或还款。银行有两个服务窗口，相应的有两个队列。客户到达银行后先排第一个队。处理每个客户业务时，如果属于第一种，且申请额超出银行现存资金总额而得不到满足，则立即排入第二队等候，直至满足时才离开银行，否则业务处理完后立即离开银行。每接待完一个第二种业务的客户，则顺序检查和处理（如

18、果可能）第二个队列的客户，对能满足的申请者予以满足，不能满足者重新排到第二个队列的队尾。注意，在此检查过程中，一旦银行资金总额少于或等于刚才第一个队列中最后一个客户（第二种业务）被接待之前的数额，或者本次已将第二个队列检查或处理了一遍，就停止检查（因为此时已不可能还有能满足者）转而继续接待第一个队列的客户。任何时刻都只开一个窗口。假设检查不需要时间。营业时间结束时所有客户立即离开银行。写一个上述银行业务的事件驱动模拟系统，通过模拟方法求出客户在银行内逗留的平均时间。 35、航空订票系统：通过此系统可以实现如下功能： 1、录入航线信息每条航线信息包括航班号、飞机号、目的地、订票数、余票数共5项。

19、假设现在有3条航线, 目的地分别是北京, 上海, 广州, 飞机上可乘坐100人( 即初始订票数为0, 余票数为100) , 将这3条航线信息存入文件中。 2、订票业务客户信息包括姓名, 航班号, 座位号(初始为0), 假设已有3个客户信息存入文件中。3、退票业务根据客户提出的航班号, 办理退票, 并删除该客户的信息, 并修改相应航线的订票数和余票数。4、修改航班信息：当航班信息改变可以修改航班数据文件。5、输出全部航线信息和全部客户信息。6、退出系统。 36、24点游戏：基本要求及步骤： 1、 随机产生四个1-13的数，分别代表13张牌。 2、 提示玩家输入算式。 3、 判断玩家输入的表达式是

20、否合法，其中算式中的四个数字只能是程序所给的四个数字，非法则回到1）。 4、 如果玩家认为这四张牌算不出24点（如：1，1，1，1），可只输入？，程序将判断这四张牌是否能得出24点，如果能，则程序将给出算式，如果不能，说明不能，并回到1）。 5、 当用户正确输入算式后，用“堆栈来求表达式的值”的原理 求出结果并判断是否为24，得出用户是输是赢的结果。 6、 询问用户是否继续，是则回到1），否则结束程序。37、工资管理 自己建立数据文件（提示可建立：职工、工资级别、职工工资）完成：查询职工的平均工资查询某一级别人员的平均工资普调工资将职工姓名按工资额度进行排序38、 一元多项式计算任务：能够按照

21、指数降序排列建立并输出多项式；能够完成两个多项式的相加、相减，并将结果输入；39、 猴子选大王任务：一堆猴子都有编号，编号是1，2，3 .m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。要求：输入数据：输入m,n m,n 为整数，nm输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号 ，建立一个函数来实现此功能40、 joseph环 任务：编号是1，2，,n的n个人按照顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开

22、始顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向的下一个人开始重新从1报数，如此下去，直到所有人全部出列为止。设计一个程序来求出出列顺序。要求：利用单向循环链表存储结构模拟此过程，按照出列的顺序输出各个人的编号。41、 纸牌游戏任务：编号为1-52张牌，正面向上，从第2张开始，以2为基数，是2的倍数的牌翻一次，直到最后一张牌；然后，从第3张开始，以3为基数，是3的倍数的牌翻一次，直到最后一张牌；然后从第4张开始，以4为基数，是4的倍数的牌翻一次， 直到最后一张牌；.再依次5的倍数的牌翻一次，6的，7的 直到 以52为基数的 翻过，输出：这时

23、正面向上的牌有哪些？42、迷宫求解在迷宫中求一条路径的算法，基本思想：若当前、位置可通过，则压入栈中，否则探索下一位置，若走不通，则回溯，迷宫大小：M*N。迷宫设置自定义。43、内存分配算法：利用静态链表，模拟实现内存分配 二. 要求：1、 对相应的题目进行算法设计2、 编写源代码3、 上机调试4、 显示调试结果5、写出实验总结三课程设计进度安排设计总学时为2周课程设计大体分五个阶段:1、选题与搜集资料:每人选择相应题目,进行课程设计课题的资料搜集.2、分析与概要设计:根据搜集的资料,进行程序功能与数据结构分析,并选择合适的数据结构,并在此基础上进行实现程序功能的算法设计.3、程序设计:运用掌

24、握C语言编写程序,实现所程序的各个模块功能.4、调试与测试:自行调试程序,成员交叉测试程序,并记录测试情况.5、实习报告:编写实习报告6、验收与评分:指导教师对每个小组的开发的系统,及每个成员开发的模块进行综合验收.结合设计报告,根据课程设计成绩的评定方法,评出成绩.四.课程设计考核标准考核时主要有如下几项参考：1、 初步设计内容的考核：是否有查阅资料能力？是否有设计思想？2、 程序编码能力调试能力的考核：程序是否清晰、易读？在技算计上是否可独立完成程序的调试，是否熟练？3、 说明书质量的考核：设计结构是否合理？叙述是否正确？方案是否可行？4、 答辩：设计结果的调试能力，对自己设计是否熟练？5

25、、 出勤率极平时表现的考核：出勤超过2次不到者成绩为不及格。五课程设计报告的内容设计结束后要写出课程设计报告,以作为整个课程设计评分的书面依据和存档材料.设计报告以规定格式的电子文档书写,打印并装订,排版及图,表要清楚,工整.装订顺序如下:封面、目录、正文.正文包括以下7个内容:1.需求分析 陈述说明程序设计的任务,强调的是程序要做什么 ，需要什么结果、所能达到的功能.2.概要设计 说明本程序中用到的所有抽象数据类型的定义,主程序的流程以及各程序模块之间的层次(调用)关系.3.详细设计 实现概要设计中定义的所有数据类型,对每个操作只需要写出伪码算法;对主程序和其他模块也都需要写出伪码算法(伪码算法达到的详细程度建议为:按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序);可采用流程图、N S 图进行描述,画出函数和过程的调用关系图.4.调试分析内容包括:a.调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析;b.算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和 改进设想;c.经验和体会等.5.测试结果列出你的测试结果,包括输入和输出.这里的测试数据应该完整和严格,最好多于需求分析中所列.6.参考文献列出参考的相关资料和书籍.附录：程序运行窗口展示如下： 1. 主窗口2. 分层菜单