级数据结构专业课程设计任务计划书.doc

一课程设计任务此次设计是为加强学生软件编程能力而进行专门训练。选题考虑到学生在数据结构中学过多种算法、数据组织方法进行选题，考虑数据结构算法所包含操作系统、网络、编译方法等中实例，进行设计。下面是课程设计待选题目共43题。按学号对应选题，如：学号为01，则选择第1题。分析题目，完成对应题目标程序设计。1、商品管理问题描述：以链表结构有序表表示某商场家电部库存模型，当有提货或进货时需要对该链表立即进行维护，每个工作日结束以后，将该链表中数据以文件形式保留，每日开始营业之前，须将文件形式保留数据恢复成链表结构有序表。实现要求：链表结构数据域 包含家电名称、品牌、单价和数量，以单价升序表现链表有序性。程序功效包含：初始化、创建表、插入、删除、更新数据、查询及链表数据和文件之间转换等。2、编程整理表示式键盘输入一个含有括号四则运算表示式，可能含有多出括号，编程整理该表示式，去掉全部多出括号，原表示式中全部变量和运算符相对位置保持不变，并保持和原表示式等价。3、个人帐簿管理问题描述：个人帐簿管理系统统计某人每个月全部收入及各项开支情况，包含食品消费，房租，儿女教育费用，水电费，医疗费，储蓄等。进入系统后能够输入和修改某月收支情况，能够对每个月开支从小到大进行排序，能够依据输入月份查询每个月收支情况。实现要求：1 初步完成总体设计，搭好框架，确定人机对话界面，确定函数个数；2 完成最低要求：建立一个文件，包含某人5个月收支情况，能对文件中信息进行扩充（追加），修改和删除；3 深入要求：完成对每个月开支排序，和完成系统查询功效。有爱好同学能够自己扩充系统功效。4、实现：连通无向图非递归遍历。5、招聘模拟。 问题描述：某集团企业为发展生产向社会公开招聘m个工种工作人员，每个工种各有不一样编号(o，1，3，m一1)和计划招聘人数，参与应聘人数有n个(编号为o，1，2，n一1)。每位应聘者能够申报两个工种，并参与企业组织考试。企业将按应聘者成绩，从高到低次序排队录用。企业录用标准是：从高分到低分依次对每位应聘者先按其第一志愿录用；当不能按第一志愿录用时，便将她成绩扣去5分后，重新排队并按其第二志愿考虑录用。 实现要求：要求程序输出每个工种录用者信息(编号、成绩，和落选者信息(编号、成绩)。 程序设计思绪：程序中按应聘者成绩从高到低次序排队录用。假如在第一志愿队列中落选，便将她成绩扣去5分后重新排队，并按其第二志愿考虑录用。程序为每个工种保留一个录用者有序队列。录用处理循环直至招聘额满或已对全部应聘者全部做了录用处理。6、求矩阵全部马鞍点。矩阵A中元素若满足：Ai,j是第i行中值最小元素，且又是第j列中值最大元素，则称元素Ai,j为该矩阵一个马鞍点。求出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。8、实现： 拓扑排序9、图算法实现问题描述：图存放结构建立、Prim、Kruskal、Dijkstra和拓扑排序算法。实现要求：（1）将图信息建立文件；（2）从文件读入图信息，建立邻接矩阵和邻接表；（3）实现Prim、Kruskal、Dijkstra和拓扑排序算法。10、实现二叉树叶子结点按从左到右次序连成一个单链表请设计一个算法，把二叉树叶子结点按从左到右次序连成一个单链表。二叉树用二叉链存放，链接时用叶子结点rchild 域存放指针。11、模拟实现五子棋在围棋比赛中，某一方（假设为黑方）在棋盘某个位置（i，j）下子后，有可能提取对方（白方一串子）。以W1919表示一个棋盘，若Wij=0表示在位置(i,j)上没有子，Wij=1表示该位置上是黑子，Wij=-1表示该位置上是白子。模拟实现五子棋 过程。12、实现：判别给定二叉树是否为二叉排序树。13、文章编辑问题描述：输入一页文字，程序能够统计出文字、数字、空格个数。静态存放一页文章，每行最多不超出80个字符，共N行；实现要求：（1）分别统计出其中英文字母数和空格数及整篇文章总字数；（2）统计某一字符串在文章中出现次数，并输出该次数；（3）删除某一子串，并将后面字符前移。存放结构使用线性表，分别用多个子函数实现对应功效；输入数据形式和范围：能够输入大写、小写英文字母、任何数字及标点符号。输出形式：（1）分行输出用户输入各行字符；（2）分4行输出全部字母数、数字个数、空格个数、文章总字数（3）输出删除某一字符串后文章14、实现：对一个存放为邻接表图，给出求其全部连通分量。15、管道铺设设计问题描述：N(N10)个居民区之间需要铺设煤气管道。假设任意两个居民区之间全部能够 铺设煤气管道，但代价不一样。实现要求：事先任意两居民区之间铺设煤气管道代价存入磁盘文件中。设计一个最好方案使得这N个居民区之间铺设煤气管道所需代价最小，并将结果以图形方法在屏幕上输出。16、排序算法实现和比较问题描述：编程实现希尔、快速排序算法，并利用程序统计每种算法实施时间。实现要求：随机产生10000、50000、 100000、 00个待排数据存入磁盘文件，从磁盘文件读入待排数据进行排序，并将排序结果写入另一个文件中。17、实现排序：设一单向链表头指针为head,链表统计中包含着整数类型key域,试设计算法,将此链表统计根据key递增次序进行就地排序.（不许可使用数组做辅助存放）18、统计C程序单词个数问题描述：扫描c源程序，利用hash技术和二分查找技术统计该源程序中关键字出现频度，并比较各自查找次数。实现要求：（1）、先用Hash表存放c语言中32个关键字，再扫描c源程序取出每个单词，利用Hash查找技术统计该程序中关键字出现频度。发生Hash冲突用线性探测法处理。设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,j)表示村庄i到j之间道路长度， 在无向图中n个顶点之间，最多可能设置n(n-1)/2条线路，怎样在这些线路中选择n-1条线路，以使总线路最短？对于n个顶点连通网能够建立很多不一样无向图，每一个无向图全部能够表示一个道路网，其中要选择一个最优图，使图上各边之小。21、求二叉树根结点到指定结点路径。22、保龄球记分系统 问题描述：保龄球一局分10轮，每轮可按球一次或数次，以击倒球数为依据得分。一局得分为10轮得分之和，而每轮得分不仅和本轮滚球情况相关，还可能和后续一两轮滚球情况相关。即某轮某次滚球击例球数不仅要记入本轮得分，还可能记入前一两轮得分。具体滚球规则和记分规则以下。 (1)若一轮第一次该球就击倒10个球，则本轮不再滚球(若是第10轮则还需另加两次滚球)，该轮得分为此次击倒球数10和以后两次滚球所击倒球数之和。 (2)若某一轮第一次滚球未击倒10个球，则可对剩下球再击一次。假如两次击倒10个球，则本轮不再滚球(若是第10轮则还需另加一次滚球)，该轮得分为此次击倒球数10和下一次滚球所击倒球数之和。 (3)若某一轮两次滚球未击倒10个球，则本轮不再滚球。该轮得分为本轮击倒球数。 实现要求：程序要求输出10轮中各轮第一次得分和第二次得分，和各轮得分和总分。 程序设计思想 程序交互地逐轮输入一次滚球击倒球数ball1和ball2，计算该轮得分score和累计得分total。为统计因一轮击倒10个球，还临时不能计算该轮得分和累计总分情况，程序引入变量frame，用来统计目前已完成完整计算轮次，程序每输入一次滚球击倒球数，就检验还未完成完整计算轮次，并计算之。23、修改起泡排序试修改起泡排序，以交替正、反两个方向进行扫描。即第一趟把排序码最大统计放到最末尾，第二趟把排序码最小统计放到最头上。如此反复进行。24、运动会分数统计：问题描述：参与运动会有n个学校，学校编号为1n。比赛分成m个男子项目，和w个女子项目。项目编号为男子1m，女子m+1m+w。不一样项目取前五名或前三名积分；取前五名积分分别为：7、5、3、2、1，前三名积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m=20,n=20）实现要求：1). 能够输入各个项目标前三名或前五名成绩；2)能统计各学校总分，3)能够按学校编号、学校总分、男女团体总分排序输出；4).能够按学校编号查询学校某个项目标情况；能够按项目编号查询取得前三或前五名学校。要求：输入数据形式和范围：20以内整数（假如做得愈加好能够输入学校名称，运动项目标名称）25、堆排序实现：在次序结构上完成,先建堆然后重建堆,最终实现全部排序26、公园导游图问题描述：给出一张某公园导游图，游客经过终端问询可知：从某一景点到另一景点最短路径。游客从公园大门进入，选一条最好路线，使游客能够不反复地游览各景点，最终回到出口（出口就在入口旁边）。实现要求：1 初步完成总体设计，搭好框架，确定人机对话界面，确定函数个数；2 完成最低要求：建立一个文件，包含5个景点情况，能完成遍历功效；3 深入要求：深入扩充景点数目，画出景点图，有爱好同学能够自己扩充系统功效。27、万年历：经过给定年，求该年日历，闰年算法：Y%4 &!Y%100|Y%4000 28、归并排序算法：用两路归并算法，实现N个无素排序29、学籍管理 对学生、课程、成绩分别建立三个数据文件（学生、课程、成绩属性自定）。查询某个学生选课情况成绩不及格学生情况对课程名按不及格学生人数进行排序建立模拟索引。30、最短路径：求图中任意两点间最短路径 31、旅游交通查询系统：实现功效：火车信息查询、最短路径查询、火车信息编辑、读入修改信息、查看火车信息、查看城市信息。每个功效中又有部分小功效，如火车信息查询中有：按车次查询、按出发地和目标地查询（其中又有最快、最省钱、全部选择）中转站查询、查看火车信息，火车信息编辑又包含：添加火车信息、删除火车信息、查看火车信息、保留火车信息功效。32、房产信息管理 自己建立数据文件方法对房产信息进行以下管理：查询修改排序33、供货信息管理自己建立数据文件方法对供货信息进行以下管理：查询修改排序。商店货架以栈形式摆放商品，生产日期越近越靠近栈底,出栈是从栈顶取货，一天营业结束，假如货架不满,则需上货，假如直接将商品摆放到货架上，则会使生产日期越近越靠近栈顶.这就需要倒货架，仍使生产日期越近越靠近栈底。写出货物进栈、出栈算法。34、银行业务模拟问题描述： 用户业务分为两种。第一个是申请从银行得到一笔资金，即取款或借款。第二种是向银行投入一笔资金，即存款或还款。银行有两个服务窗口，对应有两个队列。用户抵达银行后先排第一个队。处理每个用户业务时，假如属于第一个，且申请额超出银行现存资金总额而得不到满足，则立即排入第二队等候，直至满足时才离开银行，不然业务处理完后立即离开银行。每接待完一个第二种业务用户，则次序检验和处理（假如可能）第二个队列用户，对能满足申请者给予满足，不能满足者重新排到第二个队列队尾。注意，在此检验过程中，一旦银行资金总额少于或等于刚才第一个队列中最终一个用户（第二种业务）被接待之前数额，或此次已将第二个队列检验或处理了一遍，就停止检验（因为此时已不可能还有能满足者）转而继续接待第一个队列用户。任何时刻全部只开一个窗口。假设检验不需要时间。营业时间结束时全部用户立即离开银行。写一个上述银行业务事件驱动模拟系统，经过模拟方法求出用户在银行内逗留平均时间。 35、航空订票系统：经过此系统能够实现以下功效： 1、录入航线信息每条航线信息包含航班号、飞机号、目标地、订票数、余票数共5项。假设现在有3条航线, 目标地分别是北京, 上海, 广州, 飞机上可乘坐100人( 即初始订票数为0, 余票数为100) , 将这3条航线信息存入文件中。 2、订票业务用户信息包含姓名, 航班号, 座位号(初始为0), 假设已经有3个用户信息存入文件中。3、退票业务依据用户提出航班号, 办理退票, 并删除该用户信息, 并修改对应航线订票数和余票数。4、修改航班信息：当航班信息改变能够修改航班数据文件。5、输出全部航线信息和全部用户信息。6、退出系统。 36、24点游戏：基础要求及步骤： 1、 随机产生四个1-13数，分别代表13张牌。 2、 提醒玩家输入算式。 3、 判定玩家输入表示式是否正当，其中算式中四个数字只能是程序所给四个数字，非法则回到1）。 4、 假如玩家认为这四张牌算不出24点（如：1，1，1，1），可只输入？，程序将判定这四张牌是否能得出24点，假如能，则程序将给出算式，假如不能，说明不能，并回到1）。 5、 当用户正确输入算式后，用“堆栈来求表示式值”原理 求出结果并判定是否为24，得出用户是输是赢结果。 6、 问询用户是否继续，是则回到1），不然结束程序。37、工资管理 自己建立数据文件（提醒可建立：职员、工资等级、职职员资）完成：查询职员平均工资查询某一级她人员平均工资普调工资将职员姓名按工资额度进行排序38、 一元多项式计算任务：能够根据指数降序排列建立并输出多项式；能够完成两个多项式相加、相减，并将结果输入；39、 猴子选大王任务：一堆猴子全部有编号，编号是1，2，3 .m ,这群猴子（m个）根据1-m次序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这么依次下来，直到圈中只剩下最终一只猴子，则该猴子为大王。要求：输入数据：输入m,n m,n 为整数，nm输出形式：汉字提醒根据m个猴子，数n 个数方法，输出为大王猴子是几号 ，建立一个函数来实现此功效40、 joseph环 任务：编号是1，2，,nn个人根据顺时针方向围坐一圈，每个人只有一个密码（正整数）。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始次序报数，报到m时停止报数。报m人出列，将她密码作为新m值，从她在顺时针方向下一个人开始重新从1报数，如此下去，直到全部些人全部出列为止。设计一个程序来求出出列次序。要求：利用单向循环链表存放结构模拟此过程，根据出列次序输出各个人编号。41、 纸牌游戏任务：编号为1-52张牌，正面向上，从第2张开始，以2为基数，是2倍数牌翻一次，直到最终一张牌；然后，从第3张开始，以3为基数，是3倍数牌翻一次，直到最终一张牌；然后从第4张开始，以4为基数，是4倍数牌翻一次， 直到最终一张牌；.再依次5倍数牌翻一次，6，7 直到 以52为基数 翻过，输出：这时正面向上牌有哪些？42、迷宫求解在迷宫中求一条路径算法，基础思想：若目前、位置可经过，则压入栈中，不然探索下一位置，若走不通，则回溯，迷宫大小：M*N。迷宫设置自定义。43、内存分配算法：利用静态链表，模拟实现内存分配 二. 要求：1、 对对应题目进行算法设计2、 编写源代码3、 上机调试4、 显示调试结果5、写出试验总结三课程设计进度安排设计总课时为2周课程设计大致分五个阶段:1、选题和搜集资料:每人选择对应题目,进行课程设计课题资料搜集.2、分析和概要设计:依据搜集资料,进行程序功效和数据结构分析,并选择适宜数据结构,并在此基础上进行实现程序功效算法设计.3、程序设计:利用掌握C语言编写程序,实现所程序各个模块功效.4、调试和测试:自行调试程序,组员交叉测试程序,并统计测试情况.5、实习汇报:编写实习汇报6、验收和评分:指导老师对每个小组开发系统,及每个组员开发模块进行综合验收.结合设计汇报,依据课程设计成绩评定方法,评出成绩.四.课程设计考评标准考评时关键有以下几项参考：1、 初步设计内容考评：是否有查阅资料能力？是否有设计思想？2、 程序编码能力调试能力考评：程序是否清楚、易读？在技算计上是否可独立完成程序调试，是否熟练？3、 说明书质量考评：设计结构是否合理？叙述是否正确？方案是否可行？4、 答辩：设计结果调试能力，对自己设计是否熟练？5、 出勤率极平时表现考评：出勤超出2次不到者成绩为不及格。五课程设计汇报内容设计结束后要写出课程设计汇报,以作为整个课程设计评分书面依据和存档材料.设计汇报以要求格式电子文档书写,打印并装订,排版及图,表要清楚,工整.装订次序以下:封面、目录、正文.正文包含以下7个内容:1.需求分析 陈说说明程序设计任务,强调是程序要做什么 ，需要什么结果、所能达成功效.2.概要设计 说明本程序中用到全部抽象数据类型定义,主程序步骤和各程序模块之间层次(调用)关系.3.具体设计 实现概要设计中定义全部数据类型,对每个操作只需要写出伪码算法;对主程序和其它模块也全部需要写出伪码算法(伪码算法达成具体程度提议为:根据伪码算法能够在计算机键盘直接输入高级程序设计语言程序);可采取步骤图、N S 图进行描述,画出函数和过程调用关系图.4.调试分析内容包含:a.调试过程中碰到问题是怎样处理和对设计和实现回顾讨论和分析;b.算法时空分析(包含基础操作和其它算法时间复杂度和空间复杂度分析)和 改善设想;c.经验和体会等.5.测试结果列出你测试结果,包含输入和输出.这里测试数据应该完整和严格,最好多于需求分析中所列.6.参考文件列出参考相关资料和书籍.附录：程序运行窗口展示以下： 1. 主窗口2. 分层菜单