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

题目1. 学生运动会成绩管理任务：学生运动会成绩数据库系统记录某校运动会上所有运动项目，各系获得分数及排名状况，涉及50、100、200，400，1500米，跳高，跳远，标枪，铅球铁饼等。进入系统后可以输入和修改某个项目成果状况，可以按各系院编号输出总分；按总分排序；按男团队总分排序 ；按系编号查询；按项目编号查询；按女团队总分排序。规定：建立一种文献，涉及各种系，各种项目得分状况，能对文献中信息进行扩充（追加），修改和删除；完毕对各种系，各种项目得分排序，以及完毕系统查询功能。键盘输入：系数目，男子项目数女子项目数，（每项目取前三名，分别为10，5，2分）。2. 哈夫曼树应用任务： 1从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树并将它存于文献hfmTree中.将已在内存中哈夫曼树以直观方式（例如树）显示在终端上；2运用已经建好哈夫曼树（如不在内存，则从文献htmTree中读入），对文献ToBeTran中正文进行编码，然后将成果存入文献CodeFile中，并输出成果，将文献CodeFile以紧凑格式先是在终端上，每行50个代码。同步将此字符形式编码文献写入文献CodePrint中。3运用已建好哈夫曼树将文献CodeFile中代码进行译码，成果存入文献TextFile中，并输出成果。规定：完毕功能1、2和3。3.图遍历任务：实现图深度优先，广度优先遍历算法，并输出原图构造及遍历成果。规定：两种必要都要实现，写出画图思路；画出图构造，有兴趣同窗可以进一步改进图效果。4.矩阵乘法任务：设计一种矩阵相乘程序，一方面从键盘输入两个矩阵a，b内容，并输出两个矩阵，完毕矩阵加法，减法，数乘，转置，ab1成果，对于不符合规定运算给与提示。规定：除键盘输入外，可通过文献输入。5. 数组应用功能： 按照行优先顺序将输入数据建成4维数组，再按照列优先顺序输出成果，给出任意处元素值，并给出相应一维数组中序号。规定：完毕规定功能。6.n元多项式运算任务： 完毕两个n元多项式作加法、减法、乘法，给出明确等式形式。规定：建立一种文献，实现两个一元二次多项式运算。规定：完毕规定功能。7.集合运算任务：完毕集合合并、求交集、差、对称差等操作。 规定：（1）使用顺序、单链表、双向循环链表、二叉平衡树、哈希表做存储形式表达集合。（2）比较不同存储构造算法效率。8.公园导游图任务：给出一张某公园导游图，游客通过终端询问可知：从某一景点到另一景点最短途径。游客从公园大门进入，选一条最佳路线，使游客可以不重复地游览各景点，最后回到出口（出口就在入口旁边）。规定：建立一种文献，涉及5个景点状况，能完毕遍历功能；进一步扩充景点数目，画出景点图，9. 商店存货管理系统任务：建立一商店存货管理系统，规定每次出货时取进货时间最早且最接近保质期中断时间货品。规定：建立一种文献，涉及5个种类货品状况，能对商品信息进行扩充（追加），修改和删除以及简朴排序；扩充商品数量，以及完毕系统查询功能。10. 汉诺威塔任务：编程序显示n（n0)个人按顺时针方向围坐一圈，每个人持有一种正整数密码。开始时任选一种正整数做为报数上限m，从第一种人开始顺时针方向自1起顺序报数，报到m是停止报数，报m人出列，将她密码作为新m值，从她下一种人开始重新从1报数。如此下去，直到所有人所有出列为止。令n最大值取30。规定设计一种程序模仿此过程，求出出列编号序列。规定：完毕规定功能，13.一元稀疏多项式计算器任务：一元稀疏多项式简朴计算器基本功能是:(1)输入并建立多项式;(2)输出多项式,输出形式为整数序列:n,c1,e1,c2,e2,cn,en,其中n是多项式项数,ci和ei分别是第i项系数和指数,序列按指数降序排列;(3)多项式a和b相加,建立多项式a+b;(4)多项式a和b相减,建立多项式a-b；(5)多项式a和b相乘,建立多项式a*b. (6)计算多项式在x处值.(7)求多项式a导函数a.(8)多项式输出形式为类数学表达式.例如,多项式-3x8+6x3-18输出形式为-3x8+6x3 -18,x15+(-8)x7-14输出形式为x15-8x7-14.注意,系数值为1 非零次项输出形式中略去系数1,如项1x8输出形式为x8,项-1x3输出形式为-x3.(9)计算器仿真界面.规定：用带表头结点单链表存储多项式.。14.走迷宫游戏任务:程序开始运营时显示一种迷宫地图，迷宫中央有一只老鼠，迷宫右下方有一种粮仓。游戏任务是使用键盘上方向键操纵老鼠在规定期间内走到粮仓处。规定:1)老鼠形象可辨认，可用键盘操纵老鼠上下左右移动；2)迷宫墙足够结实，老鼠不能穿墙而过；3)对的检测成果，若老鼠在规定期间内走到粮仓处，提示成功，否则提示失败；4)添加编辑迷宫功能，可修改当前迷宫，修改内容：墙变路、路变墙；5)找出走出迷宫所有途径，以及最短途径。6)运用序列化功能实现迷宫地图文献存盘和读出等功能15.哈夫曼编/编译器任务：运用哈夫曼编码进行通信可以大大提高信道运用率，缩短信息传播时间，减少传播成本。但是，这是规定在发送端通过一种编码系统对待传数据预先编码，在接受端将传来数据进行译码（复原）。对于双工信道（即可以双向传播信息信道），每端都需要一种完整编/译码系统。试为这样信息收发站写一种哈夫曼编/译码系统。规定：一种完整系统应当具备如下功能：（1）I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文献hfmTree中。 （2）E编码（Encoding）。 运用建好哈夫曼树（如不在内存，则从文献hfmTree中读入），对文献ToBeTran中正文进行编码，然后将成果存入文献CodeFile中。 （3）D：译码（Decoding）。运用已建好哈夫曼树将文献CodeFile中代码进行译码，成果存入文献TextFile中。 （4）P印代码文献（Print）。将文献CodeFile以紧凑格式显示在终端上，每行50个代码。 同步将此字符形式编码文献写入文献CodePrin中。 （5）T打印哈夫曼树（Tree printing）。将已在内存中哈夫曼树以直观方式（树或凹入表形式）显示在终端上，同步将此文字符形式哈夫曼树写入文献TreePrint中。（6）上述文献CodeFile中每个“0”或“1”事实上占用了一种字节空间，只起到示意或模仿作用。为最大限度运用码点存储能力，试改写你系统，将编码成果以二进制形式存储在文献CodeFile中。 （7） 修改你系统，实现对你系统原程序编码和译码（8） 实现各个转换操作源/目文献，均由顾客在选取此操作时指定。测试数据： 用下表给出字符集和频度实际记录数据建立哈夫曼树，并实现如下报文编码和译码：“THIS PROGRAM IS MY FAVORITE ”。字符 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 V W X Y Z频度57 63 15 1 48 51 80 23 8 18 1 16 116. 稀疏矩阵运算器任务：稀疏矩阵是指那些多数元素为零矩阵。运用“稀疏”特点进行存储和计算可以大大节约存储空间，提高计算效率。实现一种能进行稀疏矩阵基本运算运算器。以“带行逻辑链接信息”三元组、以十字链表表达稀疏矩阵。表达稀疏矩阵，实现两矩阵相加、相减和相乘运算。稀疏矩阵输入形式采用三元组表达，而运算成果矩阵则以普通阵列形式列出。实现矩阵求逆运算。规定：一方面应输入矩阵行数和列数，并鉴别两个矩阵行、列数对于所规定做运算与否相匹配。可设矩阵行数和列数均不超过20。程序可以对输入三元组进行限制，例如，按行优先。注意提高计算效率。17. 迷宫问题求解及演示任务：以一种mn长方阵表达迷宫,0和1分别表达迷宫中道路和障碍.设计一种程序,对任意设定迷宫,求出一条从入口到出口通路,或得出没有通路结论。编写递归形式算法，求得迷宫中所有也许通路；以方阵形式输出迷宫及其通路。规定：一方面实现一种以链表做存储构造栈类型,然后编写一种求解迷宫非递归程序。求得通路以三元组(i,j,d)形式输出,其中:(i,j)批示迷宫中一种坐标,d表达走到下一坐标方向.如:对于下列数据迷宫,输出一条通路为(1,1,1),(1,1,2),(2,2,2),(3,2,3),(3,1,2),。测试数据：迷宫测试数据如下:左上角(1,1)为入口,右下角(8,9)为出口 1 2 3 4 5 6 7 8001000100010001000001101011100100001000001000101011110011100010111000000实现提示：计算机解迷宫通惯用是“穷举求解”办法，即从入口出发，顺着某一种方向进行摸索，若能走通，则继续往迈进；否则沿着原路退回，换一种方向继续摸索，直至出口位置，求得一条通路。如果所有也许通路都摸索到而未能到达出口，则所设定迷宫没有通路。可以二维数组存储迷宫数据，普通设定入口下标为（1，10，出口点下标为（n，n）。为解决以便起见，可在迷宫四周加一圈障碍。对于迷宫中任一位置，均可商定有东、南、西、北四个方向可通。18、串基本操作演示任务：实现串类型，并写一种串基本操作演示系统。规定：用堆分派存储表达实现HString串最小操作子集基本上，实现串抽象数据类型别的基本操作，参数合法性检查必要严格。系统既能解决对的命令，也能解决错误命令。阐明：（在格式中，表达0个、1个或各种空格所构成串；串标记表达一种内部名或一种串文字。前者是一种串唯一标记，是一种内部形式（而不是字符形式）标记符。后者是两端由单引号括起来仅可打印字符构成序列。串内每两个持续单引号表达一种单引号符。） 运用上述基本操作函数构造如下系统：它是一种命令解释程序，循环往复地解决顾客键入每一条命令，直至终结程序命令为止。命令定义如下：（1）赋值。格式：A串标记回车 用串标记所示值建立新串，并显示新串内部名和串值。如：A Hi！（2）判相等。 格式：E串标记1串标记2回车若两串相等，则显示“EQUAL”，否则显示“UNEQUAL”。（3）联接。 格式：C串标记1串标记2回车将两串联接产生成果串，它内部名和串值都显示出来。（4） 求长度 格式：L串标记回车 显示串长度。（5） 求子串 格式：S串标记+数1+数2回车如果参数合法，则显示子串内部名和串值。数不带正负号。（6）子串定位。 格式：I串标记1串标记2回车显示第二个串在第一种串中初次浮现时位置。（7）串替代 格式：R串标记1串标记2串标记2回车将第一种串中浮现所有浮现第二个串用第三个串替代，显示成果串内部名和串值，原串不变。 （8）显示格式：P回车 显示所有在系统中被保持串内部名和串值对照表。 （9）删除格式：D内部名回车 删除该内部名相应串，即赋值逆操作。 （10）退出 格式：Q回车 结束程序运营。在上述命令中，如果一种自变量是串，则应一方面建立它。基本操作函数成果（即函数值）如果是一种串，则应在尚未分派区域内新辟空间存储。支持串名。将串名（可设不超过6个字符）存于串表头中。命令（1）（3）（5）要增长命令参数成果串名；命令（7）中串标记1改为串名，并用此名作为成果串名，删除原被替串标记，用串名代替串标记定义和命令解释中内部名。每个命令执行完毕时及时自动删除无名串。测试数据：自定。但要涉及如下几组： （1）E 回车，应显示“EQUAL”。（2）Eabc abcd回车，应显示“UNEQUAL”。 （3）C 回车，应显示。 （4）Ia 回车，应报告：参数非法。 （5）Raaa aa b回车，应显示ba （6） Raaabc a aab回车，应显示aabaabaabbc。 （7）Raaaaaaaa aaaa ab回车，应显示abab。 实现提示： （1）演示系统主构造是一种串表头，可定义为：struct HString StrHead100； int CurNum; StrHeadList；将各串头指针依次存于串头数组StrHead中（设串数目不超过100）。CurNum为系统中既有串数目，CurNum+1是可为下一种新串头指针分派位置。可以取StrHead元素下标作为所相应串内部名。（2）应设立一种命令为分析函数，把命令分析成果通过一下类型一种变量参数返回： typedef struct int CmdNo；/或char类型，为命令号或命令符 int s3； /命令串参数内部名（最多3个） int num2； / 命令数值参数（最多2个）ResultType；此函数还在存储构造中建立命令参数中串。也许再设立一种“取下一种命令参数串”操作是有益。注意不要把这里命令与所有机器操作系统命令相混。为了解决简朴化，可以不对命令格式作严格语法检查。19.内部排序算法比较任务：在教科书中，各种内部排序算法时间复杂度分析成果只给出了算法执行时间阶，或大概执行时间。试通过随机数据比较各算法核心字比较次数和核心字移动次数，以获得直观感受。规定：（1）对如下内部算法进行比较：起泡排序、直接插入排序、简朴选取排序、迅速查找排序、希尔排序、堆排序、折半插入排序、二路插入排序、归并排序、基数排序。（2）待排序表表长不不大于100；其中数据要用伪随机数产生程序产生；至少要用5组不同输入数据作比较；比较指标为有核心字参加比较次数和核心字移动次数（核心字互换计为3次移动）。（3）最后要对成果作出简朴分析，涉及对各数据得出成果波动大小解释。实现提示：重要工作是设法在已知算法中恰当位置插入对核心字比较次数和移动次数计数操作。程序还可以考虑几组数据典型性，如，正序、逆序和不同限度乱序。注意采用分块调试办法。对不同输入表长作实验，观测检查两个指标相对于表长变化关系。还可以对稳定性作验证。20. 算术表达式求值演示任务：表达式计算是实现程序设计语言基本问题之一，也是栈应用一种典型例子。设计一种程序，演示用算符优先法对算术表达式求值过程。规定：以字符序列形式从终端输入语法对的、不含变量整数表达式。运用教科书给出算符优先关系，实现对算术四则混合运算表达式求值，并仿照教科书上例子演示在求值中运算符栈、运算数栈、输入字符和重要操作变化过程。测试数据：8； 1+2+3+4； 88-1*5；1024/4*8； 1024/（4*8）； （20+2）*（6/2）；3-3-3； 8/（9-9）； 2*（6+2*（3+6*（6+6）；（6+6）*6+3）*2+6）*2；实现提示：（1）设立运算符栈和运算数栈辅助分析算符优先关系。（2） 在读入表达式字符序列同步，完毕运算符和运算数（整数）辨认解决，以及相应运算。（3）在辨认出运算数同步，要将其字符序列形式转化成整数形式。 （4）在程序恰当位置输出运算符栈、运算数栈、输入字符和重要操作内容。选做内容 ：（ 1）扩充运算符集，如增长乘方、单目减、赋值等运算。（2）运算量可以是变量。（3）运算量可以是实数类型。（4）计算器功能和仿真界面。21. 校园导游征询任务：设计一种校园导游程序，为来访客人提供各种信息查询服务。规定：（1）设计你所在学校校园平面图，所含景点不少于10个。以图中顶点表达校内各景点，存储景点名称、代号、简介等信息；以边表达途径，存储途径长度有关信息。（2）为来访客人提供图中任意景点有关信息查询。 （3）为来访客人提供图中任意景点问路查询，即查询任意两个景点之间一条最短途径。（4）提供图中任意景点问路查询，即求任意两个景点之间所有途径。 （5）校园导游图景点和道路修改扩充功能。 （6）道路信息，如道路类别（车道、人行道等）、沿途景色级别，以至可按客人所需分别查询人行途径或车行途径或观景途径等。选做内容 ：（1）求校园关节点。（2）提供校园图中各种景点最佳访问路线查询，即求路过这个景点最佳（短）途径。（3）扩充每个景点邻接景点方向等信息，使得途径查询成果能提供详导向信息。（4）实现校园导游图仿真界面。22. 马踏棋盘任务：设计一种国际象棋马踏遍棋盘演示程序。规定：将马随机放在国际象棋88棋盘Board88某个方格中，马按走棋规则进行移动。规定每个方格只进入一次，走遍棋盘上所有64个方格。编制非递归程序，求出马行走路线，并按求出行走路线，将数字1，2，64依次填入一种88方阵，并输出。23.平衡二叉树操作演示任务：运用平衡二叉树实现一种动态查找表。规定：(1) 实现动态查找表三种功能：查找、插入、删除。平衡二叉树显示可采用凹入体现形式，也可以采用图形界面画出树。每次插入或删除一种结点后，应更新平衡二叉树显示。(2) 合并两棵平衡二叉树。（3）把一棵二叉树分裂为两棵平衡二叉树，使得在一棵树中所有核心字都不大于或等于x，另一棵树中任一核心字都不不大于x。24. 最小生成树问题任务：若要在n个都市之间建设通信网络，只需要假设n-1条线路即可。如何以最低经济代价建设这个通信网，是一种网最小生成树问题。规定：（1）运用普里姆、克鲁斯卡尔算法求网最小生成树。（2）实现教材6.5节中定义抽象数据类型MFSet。以此表达构造生成树过程中连通分量。（3）以文本形式输出生成树中各条边以及她们权值。（a c 3）（4）运用堆排序实现选取权值最小边。25 内存分派算法任务：解决器中有一就绪队列，若干个进程依到达时刻依次进入就绪队列，每个进程有进程名和解决器解决此进程所需空间、优先级。规定：（1）仿静态链表形式分派内存所需空间，编程序实现内存分派算法，演示调度过程；（2）实现按照优先级调度算法，并演示调度过程。26.运动会分数记录任务：参加运动会有n个学校，学校编号为1n。比赛提成m个男子项目，和w个女子项目。项目编号为男子1m，女子m+1m+w。不同项目取前五名或前三名积分；取前五名积分分别为：7、5、3、2、1，前三名积分分别为：5、3、2；哪些取前五名或前三名由学生自己设定。（m=20,n=20）规定：1) 可以输入各个项当前三名或前五名成绩；2) 能记录各学校总分，3) 可以按学校编号或名称、学校总分、男女团队总分排序输出；4) 可以按学校编号查询学校某个项目状况；可以按项目编号查询获得前三或前五名学校。5) 数据存入文献并能随时查询 6) 规定：输入数据形式和范畴：可以输入学校名称，运动项目名称输出形式：有中文提示，各学校分数为整形界面规定：有合理提示，每个功能可以设立菜单，依照提示，可以完毕有关功能规定。存储构造：学生自己依照系统功能规定自己设计，但是规定运动会有关数据要存储在数据文献中。请在最后上交报告中指明你用到存储构造；测试数据：规定使用1、所有合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序稳定。测试数据及测试成果请在上交报告中写明；27. 飞机订票系统任务：通过此系统可以实现如下功能：（1）录入：可以录入航班状况（数据可以存储在一种数据文献中，数据构造、详细数据自定）（2）查询：可以查询某个航线状况（如，输入航班号，查询起降时间，起飞到达都市，（3）订票：（订票状况可以存在一种数据文献中，构造自己设定）可以订票，如果该航班已经无票，可以提供有关可选取航班；（4）退票： 可退票，退票后修改有关数据文献；（5）客户资料有姓名，证件号，订票数量及航班状况，订单要有编号。（6）修改航班信息：当航班信息变化可以修改航班数据文献规定：依照以上功能阐明，设计航班信息，订票信息存储构造，设计程序完毕功能；28. 文章编辑功能：输入一页文字，程序可以记录出文字、数字、空格个数。静态存储一页文章，每行最多不超过80个字符，共N行。规定：（1）分别记录出其中英文字母数和空格数及整篇文章总字数；（2）记录某一字符串在文章中浮现次数，并输出该次数；（3）删除某一子串，并将背面字符前移。（4）存储构造使用线性表，分别用几种子函数实现相应功能；（5）输入数据形式和范畴：可以输入大写、小写英文字母、任何数字及标点符号。（6）输出形式：1）分行输出顾客输入各行字符；2）分4行输出所有字母数、数字个数、空格个数、文章总字数；3）输出删除某一字符串后文章；29. 纸牌游戏任务：编号为1-52张牌，正面向上，从第2张开始，以2为基数，是2倍数牌翻一次，直到最后一张牌；然后，从第3张开始，以3为基数，是3倍数牌翻一次，直到最后一张牌；然后从第4张开始，以4为基数，是4倍数牌翻一次， 直到最后一张牌；.再依次5倍数牌翻一次，6，7 直到 以52为基数翻过，输出：这时正面向上牌有哪些？规定：界面和谐美观，给出变化过程。30. 宿舍管理查询软件任务：为宿舍管理人员编写一种宿舍管理查询软件。规定：（1）采用交互工作方式；（2）建立数据文献，数据文献按核心字（姓名、学号、房号）进行排序(排序方式至少4种)；(3) 查询：(用4种以上查找方式实现如下操作)按姓名查询、按学号查询、按房号查询；(4) 打印查询成果。31. 地图着色问题任务：已知中华人民共和国地图，对各省进行着色，规定相邻省所使用颜色不同，并保证使用颜色总数至少。规定：（1）界面和谐（2）给出求解过程32. 员工管理系统任务：每个员工信息涉及：编号、姓名、性别、出生年月、学历、职务、电话、住址等。系统可以完毕员工信息查询、更新、插入、删除、排序等功能。规定：（1） 排序：按不同核心字，对所有员工信息进行排序。（2） 查询：按特定条件查找员工。（3） 更新：按编号对某个员工某项信息进行修改。（4） 插入：加入新员工信息。（5） 删除：按编号删除已离职工工信息。（6）规定分别使用顺序存储、链式存储构造。（7）实现4种以上查询和4种以上排序方式，并计算查找次数/数据互换次数。33. 学校超市选址问题（带权有向图中心点）任务：拟在某一学校开设2个超市，每个超市商品类别不重复。其她各单位到超市距离不同，同步各单位人员购买某一商品类别频度也不同。请为超市选址和出售商品类别分派，规定实现总体最优。规定：（1）商品类别总数设定（2）各单位人数设定、人员-购买商品频度设定（3）输出地图，超市位置用特殊标记显示。