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

1. 通讯录的制作【问题描述】设计一个通讯录管理程序。【基本要求】1) 每条信息至包含 ：姓名（NAME ）、性别(GENDER)、电话（TEL） 、城市（CITY）邮编（EIP）几项。2) 作为一个完整的系统，应具有友好的界面和较强的容错能力要求：显示提示选单。根据选单的选项调用各函数，并完成相应的功能。能对通讯录的末尾，写入新的信息，并返回选单。能查询某人的信息，如果找到了，则显示该人的信息，如果未找到，则提示通讯录中没有此人的信息，并返回选单。 （能按姓名、电话、城市3种方式查询）能修改某人的信息，如果未找到要修改的人，则提示通讯录中没有此人的信息，并返回选单。（按姓名、电话） 能删除某人的信息，如果未找到要删除的人，则提示通讯录中没有此人的信息，并返回选单。（按姓名、电话） 能显示通讯录中的所有记录。通讯录信息以文件形式存盘。2. 图书管理系统【问题描述】设计一个计算机管理系统完成图书管理基本业务。【基本要求】1) 每种书的登记内容包括书号、书名、著作者、现存量和库存量；2) 对书号建立索引表（线性表）以提高查找效率；3) 系统主要功能如下：采编入库：新购一种书，确定书号后，登记到图书帐目表中，如果表中已有，则只将库存量增加；借阅：如果一种书的现存量大于0，则借出一本，登记借阅者的书证号和归还期限，改变现存量；归还：注销对借阅者的登记，改变该书的现存量。【进一步完成内容】（选做）1) 系统功能的进一步完善；2) 索引表采用树表。3.简单的职工管理系统【问题描述】设计简单的职工信息管理程序。对单位的职工进行管理，包括插入、删除、查找、排序等功能。职工对象包括姓名、性别、出生年月、工作年月、学历、职务、住址、电话等信息。【基本要求】（1）新增一名职工：将新增职工对象按姓名以字典方式职工管理文件中。（2）删除一名职工：从职工管理文件中删除一名职工对象。（3）查询：从职工管理文件中查询符合某些条件的职工。（4）修改：检索某个职工对象，对其某些属性进行修改。（5）排序：按某种需要对职工对象文件进行排序。【实现提示】职工对象数不必很多，便于一次读入内存，所有操作不经过内外存交换。（1）由键盘输入职工对象，以文件方式保存。程序执行时先将文件读入内存。（2）对职工对象中的姓名按字典顺序进行排序。（3）对排序后的职工对象进行增、删、查询、修改、排序等操作。【选做内容】将职工对象按散列法存储，并设计解决冲突的方法。在此基础上实现增、删、查询、修改、排序等操作。4.仓库管理系统（线性表应用）【问题描述】建立一个仓库管理程序，可以按顺序和货物名称查询仓库存储情况，也可以增加或删除货物信息、实现货物的入库出库，要求能用文件保存仓库货品信息。【实现提示】可以采用双向链表的存储结构，如可定义如下的存储结构：typedef struct dnode /*定义双向链表结构体*/ int number; /*货物编号*/ char namemax; /*货物名称*/ int counter; /*货物数量*/ struct dnode *prior,*next; /*定义两指针，分别指向其前驱和后继*/ dlnode;5. 运动会分数统计【问题描述】参加运动会有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) 规定：输入数据形式和范围：可以输入学校的名称，运动项目的名称输出形式：有中文提示，各学校分数为整形界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构；测试数据：要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；6. 飞机订票系统【问题描述】设计一个飞机订票系统。客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。设计航班信息，订票信息的存储结构，设计程序完成功能。【基本要求】录入：可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定）查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）；可以输入起飞抵达城市，查询飞机航班情况；订票：可以订票，如果该航班已经无票，可以提供相关可选择航班；（订票情况可以存在一个数据文件中，结构自己设定）退票： 可退票，退票后修改相关数据文件；修改航班信息：当航班信息改变可以修改航班数据文件7. 校园导游问题【问题描述】设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。【基本要求】1）设计校园平面图，在校园景点选10个左右景点。以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。2）为来访客人提供图中任意景点相关信息的查询。3）为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径。4) 增加、删除、更新有关景点和道路的信息【实现提示】一般情况下，校园的道路是双向通行的，可设计校园平面图是一个无向网。顶点和边均含有相关信息。8. 敢死队问题【问题描述】 有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。 排长是不愿意去的，假设排长为1号，请你设计一程序，求出从第几号战士开始计数才能让排长最后一个留下来而不去执行任务。【基本要求】至少采用两种不同的数据结构的方法实现。9. 学生搭配问题【问题描述】一班有m个女生,有n个男生(m不等于n),现要开一个舞会. 男女生分别编号坐在舞池的两边的椅子上.每曲开始时,依次从男生和女生中各出一人配对跳舞, 本曲没成功配对者坐着等待下一曲找舞伴.【基本要求】 请设计一系统模拟动态地显示出上述过程,要求如下:1) 输出每曲配对情况2) 计算出任何一个男生(编号为X)和任意女生(编号为Y),在第K曲配对跳舞的情况.至少求出K的两个值.3) 尽量设计出多种算法及程序,可视情况适当加分提示:用队列来解决比较方便.10. 教学计划编制问题【问题描述】 大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等，每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。【基本要求】（1）输入参数包括：学期总数，一学期的学分上限，每门课的课程号(固定占3位的字母数字串)、学分和直接先修课的课程号。（2）允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。（3）若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。计划的表格格式自行设计。【测试数据】学期总数：6；学分上限：10；该专业共开设12门课，课程号从C01到C12，学分顺序为2,3,4,3,2,3,4,4,7,5,2,3。先修关系如下： 课程编号课程名称先决条件C1程序设计基础无C2离散数学C1C3数据结构C1，C2C4汇编语言C1C5语言的设计和分析C3，C4C6计算机原理C11C7编译原理C5，C3C8操作系统C3，C6C9高等数学无C10线性代数C9C11普通物理C9C12数值分析C9，C10，C1【实现提示】可设学期总数不超过12，课程总数不超过100。如果输入的先修课程号不在该专业开设的课程序列中，则作为错误处理。应建立内部课程序号与课程号之间的对应关系。11双层停车场管理 【问题描述】有一个两层的停车场，每层有 6 个车位，当第一层车停满后才允许使用第二层。(停车 场可用一个二维数组实现， 每个数组元素存放一个车牌号)每辆车的信息包括车牌号， 层号， 车位号，停车时间共 4 项。其中停车时间按分钟计算。 【基本要求】（1）假设停车场初始状态为第一层已经停有 4 辆车，其车位号依次为 14，停车时间依次 为 20，15，10，5。即先将这四辆车的信息存入文件“car.dat”中( 数组的对应元素也要 进行赋值 ) （2）停车操作：当一辆车进入停车场时，先输入其车牌号，再为它分配一个层号和一个车 位号(分配前先查询车位的使用情况， 如果第一层有空则必须停在第一层)， 停车时间设为 5， 最后将新停入的汽车的信息添加文件“car.dat”中，并将在此之前的所有车的停车时间加 5。 （2）收费管理(取车)：当有车离开时，输入其车牌号，先按其停车时间计算费用，每 5 分 钟 0.2 元。(停车费用可设置一个变量进行保存)，同时从文件“car.dat”中删除该车的信 息， 并将该车对应的车位设置为可使用状态(即二维数组对应元素清零)。 按用户的选择来判 断是否要输出停车收费的总计。 （4）输出停车场中全部车辆的信息。 （5）退出系统。12. 迷宫问题【问题描述】迷宫实验是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口到出口，而不走错一步。老鼠经多次实验终于得到它学习走迷宫的路线。设计一个计算机程序对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。【实现提示】可以利用一个二维数组mazeij表示迷宫，其中1=i=m,1=j0。起始行下面的每一行是鳄鱼的坐标（x，y），其中x, y都是整数，而且没有任何两只鳄鱼出现在同一个位置。input.txt文件以一个负数结尾。【输出要求】程序输出结果输出到output.txt文件中。对于每组输入数据，如果007可以逃脱，则输出到output.txt文件的内容格式如下：第一行是007必须跳的最小的步数，然后下面按照跳出顺序记录跳出路径上的鳄鱼坐标（x，y），每行一个坐标。如果007不可能跳出去，则将-1写入文件。如果这里有很多个最短的路径，只需输出其中的任意一种 【输入例子】4101702703704501102030-1【输出例子】5170270370450-1提示：将每个鳄鱼看作图中的一个顶点。如果007可以从A点跳到B点，则A和B之间就有一条边。19.最小生成树:室内布线【问题描述】装修新房子是一项颇为复杂的工程，现在需要写个程序帮助房主设计室内电线的布局。首先，墙壁上插座的位置是固定的。插座间需要有电线相连，而且要布置的整齐美观，即要求每条线都与至少一条墙边平行，且嵌入四壁或者地板（不能走屋顶）。房主要求知道，要将所有插座连通，自己需要买的电线的最短长度。另外，别忘了每个房间都有门，电线不可以穿门而过。上图给出了一个有4插座的房间的电线布局。【输入要求】输入由若干组测试数据组成。每组数据的第1行包含房间的长、宽、高和插座的个数N（N为一个不超过20的正整数）。接下去的N行中，第i行给出第i个插座的位置坐标（xi,yi,zi）；最后一行包含4个3元组（x1,y1,z1）（x4，y4，z4），分别是长方形门框的4个角三维坐标。4个数字全部为0表示全部测试结束，不要对该数据任何处理。注意：这里假设长方体形状的房间完全位于三维直角坐标系的第一象限内，并且有一个角落在原点上。地板位于x-y平面。题目数据保证，每个插座仅属于四面墙中的一面，门上没有插座。要求每段电线的两端必须仅与插座连接，电线之间不能互相交叉焊接。【输出要求】对每一组测试，在一行里输出要将所有插座连通需要买的电线的最短整数长度。【输入例子】10 10 10 40 1 3.32.5 0 25 0 0.85 10 10 0 0 0 0 3 1.50 0 1.5 0 30 0 0 0【输出例子】2120.神秘国度的爱情故事【问题描述】某个太空神秘国度中有很多美丽的小村，从太空中可以望见，小村间有路相连，更精确点说，任意两村之间有且仅有一条路径。 小村A中有位年轻人爱上了自己村里美丽姑娘。每天早晨，姑娘都要去小村B里的面包房工作，傍晚6点回家。年轻人终于决定要向姑娘表白，他打算在小村C等着姑娘路过的时候把爱慕说出来。问题是，他不能确定小村C是否在小村B到小村A之间的路径上。你可帮助他解决这个问题吗？【输入要求】输入由若干组测试数据组成。每组数据的第1行包含一正整数N（1N50000），代表神秘国度中小村的个数，每个小村即从0到N-1编号。接下来有N-1行输入，每行熬好一条双向道路的两个端点小村的编号，中间用空格分开。之后一行包含一正整数M（1M500000），代表着该组测试问题的个数。接下来M行，每行给出A、B、C三个小村的编号，中间用空格分开。当N为0时，表示全部测试结束，不要对该数据做任何处理。【输出要求】对每一组测试给定的A、B、C，在一行里输出答案，即：如果C在A和B之间的路径上，输出Yes，否则输出No。【输入例子】30 11 230211201210【输出例子】YesNoYes