数据结构课程设计题目2017

《数据结构课程设计题目2017》由会员分享，可在线阅读，更多相关《数据结构课程设计题目2017（10页珍藏版）》请在装配图网上搜索。

1、1. 通讯录的制作【问题描述】 设计一个通讯录管理程序。【基本要求】1）每条信息至包含 ：姓名（ NAME ）、性别 （GENDER） 、电话（ TEL） 、城市（ CITY ） 邮编（EIP）几项。2）作为一个完整的系统，应具有友好的界面和较强的容错能力 要求： 显示提示选单。根据选单的选项调用各函数，并完成相应的功能。 能对通讯录的末尾，写入新的信息，并返回选单。能查询某人的信息， 如果找到了，则显示该人的信息，如果未找到，则提示通讯录中没有此 人的信息，并返回选单。 （能按姓名、电话、城市 3 种方式查询） 能修改某人的信息， 如果未找到要修改的人， 则提示通讯录中没有此人的信息， 并返

2、回选单。（按姓名、电话）能删除某人的信息， 如果未找到要删除的人， 则提示通讯录中没有此人的信息， 并返回选单。（按姓名、电话） 能显示通讯录中的所有记录。 通讯录信息以文件形式存盘。2. 图书管理系统【问题描述】 设计一个计算机管理系统完成图书管理基本业务。【基本要求】1）每种书的登记内容包括书号、书名、著作者、现存量和库存量；2）对书号建立索引表（线性表）以提高查找效率；3）系统主要功能如下： 采编入库：新购一种书，确定书号后，登记到图书帐目表中，如果表中已有，则只将库存量 增加；借阅：如果一种书的现存量大于 0，则借出一本，登记借阅者的书证号和归还期限，改变现 存量；归还：注销对借阅者的

3、登记，改变该书的现存量。【进一步完成内容】 （选做）1）系统功能的进一步完善；2）索引表采用树表。3. 简单的职工管理系统【问题描述】 设计简单的职工信息管理程序。对单位的职工进行管理，包括插入、删除、查找、排序 等功能。 职工对象包括姓名、 性别、 出生年月、 工作年月、学历、职务、住址、 电话等信息。【基本要求】（ 1 ）新增一名职工：将新增职工对象按姓名以字典方式职工管理文件中。（2）删除一名职工：从职工管理文件中删除一名职工对象。（3）查询：从职工管理文件中查询符合某些条件的职工。（4）修改：检索某个职工对象，对其某些属性进行修改。（5）排序：按某种需要对职工对象文件进行排序。 【实现

4、提示】职工对象数不必很多，便于一次读入内存，所有操作不经过内外存交换。（1）由键盘输入职工对象，以文件方式保存。程序执行时先将文件读入内存。（2）对职工对象中的 姓名 按字典顺序进行排序。（3）对排序后的职工对象进行增、删、查询、修改、排序等操作。【选做内容】 将职工对象按散列法存储，并设计解决冲突的方法。在此基础上实现增、删、查询、修 改、排序等操作。4. 仓库管理系统（线性表应用）【问题描述】建立一个仓库管理程序， 可以按顺序和货物名称查询仓库存储情况， 也可以增加或删除货物 信息、实现货物的入库出库，要求能用文件保存仓库货品信息。【实现提示】可以采用双向链表的存储结构，如可定义如下的存储

5、结构：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；哪些取前

6、 五名或前三名由学生自己设定。 （ m=20,n=20 ）【基本要求】1）可以输入各个项目的前三名或前五名的成绩；2）能统计各学校总分，3）可以按学校编号或名称、学校总分、男女团体总分排序输出；4）可以按学校编号查询学校某个项目的情况；可以按项目编号查询取得前三或前五名的学 校。5）数据存入文件并能随时查询6）规定：输入数据形式和范围：可以输入学校的名称，运动项目的名称 输出形式：有中文提示，各学校分数为整形界面要求： 有合理的提示， 每个功能可以设立菜单， 根据提示，可以完成相关的功能要 求。存储结构： 学生自己根据系统功能要求自己设计， 但是要求运动会的相关数据要存储在 数据文件中。（数据

7、文件的数据读写方法等相关内容在 c 语言程序设计的书上， 请自学解决） 请在最后的上交资料中指明你用到的存储结构；测试数据：要求使用 1、全部合法数据； 2、整体非法数据； 3、局部非法数据。进行程序测 试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明；6. 飞机订票系统【问题描述】 设计一个飞机订票系统。客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。 设计航班信息，订票信息的存储结构，设计程序完成功能。【基本要求】 录入：可以录入航班情况 （数据可以存储在一个数据文件中， 数据结构、 具体数据自定） 查询：可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达

8、城市，航 班票价，票价折扣，确定航班是否满仓） ；可以输入起飞抵达城市，查询飞机航班情况； 订票：可以订票，如果该航班已经无票，可以提供相关可选择航班； （订票情况可以存 在一个数据文件中，结构自己设定）退票： 可退票，退票后修改相关数据文件； 修改航班信息：当航班信息改变可以修改航班数据文件7. 校园导游问题【问题描述】设计你的学校的平面图，至少包括10 个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径） 。 【基本要求】1）设计校园平面图， 在校园景点选 10 个左右景点。 以图中顶点表示校园内各景点， 存放景 点名称、代号、简介等

9、信息；以边表示路径，存放路径长度等有关信息。2）为来访客人提供图中任意景点相关信息的查询。3）为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径。4）增加、删除、更新有关景点和道路的信息 【实现提示】一般情况下，校园的道路是双向通行的，可设计校园平面图是一个无向网。顶 点和边均含有相关信息。8. 敢死队问题【问题描述】有M个敢死队员要炸掉敌人的一碉堡，谁都不想去，排长决定用轮回数数的办法来决定 哪个战士去执行任务。 如果前一个战士没完成任务， 则要再派一个战士上去。 现给每个战士 编一个号， 大家围坐成一圈，随便从某一个战士开始计数，当数到5 时，对应的战士就去执行任务，

10、且此战士不再参加下一轮计数。 如果此战士没完成任务， 再从下一个战士开始数数， 被数到第 5 时，此战士接着去执行任务。以此类推，直到任务完成为止。排长是不愿意去的， 假设排长为 1号， 请你设计一程序， 求出从第几号战士开始计数才能 让排长最后一个留下来而不去执行任务。【基本要求】至少采用两种不同的数据结构的方法实现。9. 学生搭配问题【问题描述】一班有m个女生，有n个男生（m不等于n）,现要开一个舞会.男女生分别编号坐在舞池的两 边的椅子上每曲开始时，依次从男生和女生中各出一人配对跳舞 ，本曲没成功配对者坐着等 待下一曲找舞伴【基本要求】请设计一系统模拟动态地显示出上述过程，要求如下：1）

11、输出每曲配对情况2）计算出任何一个男生（编号为X）和任意女生（编号为Y）,在第K曲配对跳舞的情况至少求 出K的两个值3）尽量设计出多种算法及程序，可视情况适当加分提示:用队列来解决比较方便10. 教学计划编制问题【问题描述】大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等，每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门， 也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。【基本要求】（1）输入参数包括：学期总数，一学期的学分上限，每

12、门课的课程号（固定占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计算机

13、原理C11C7编译原理C5，C3C8操作系统C3，C6C9高等数学无C10线性代数C9C11普通物理C9C12数值分析C9, C10, C1【实现提示】可设学期总数不超过 12,课程总数不超过100。如果输入的先修课程号不在该专业开设的课 程序列中，则作为错误处理。应建立内部课程序号与课程号之间的对应关系。11双层停车场管理【问题描述】有一个两层的停车场，每层有6个车位，当第一层车停满后才允许使用第二层。（停车 场可用一个二维数组实现，每个数组元素存放一个车牌号）每辆车的信息包括车牌号，层号，车位号，停车时间共 4项。其中停车时间按分钟计算。【基本要求】（1） 假设停车场初始状态为第一层已经停

14、有4辆车，其车位号依次为1 4，停车时间依次 为20, 15, 10, 5。即先将这四辆车的信息存入文件“cadat 中（数组的对应元素也要 进行赋值）（2） 停车操作：当一辆车进入停车场时， 先输入其车牌号，再为它分配一个层号和一个车 位 号（分配前先查询车位的使用情况， 如果第一层有空则必须停在第一层），停车时间设为 5, 最后将新停入的汽车的信息添加文件 “ cadat ”中，并将在此之前的所有车的停车时间加 5。（2）收费管理（取车）:当有车离开时，输入其车牌号，先按其停车时间计算费用，每5分钟0.2元。（停车费用可设置一个变量进行保存 ），同时从文件“cadat ”中删除该车的信 息

15、， 并将该车对应的车位设置为可使用状态 （即二维数组对应元素清零）。按用户的选择来判断 是否要输出停车收费的总计。（4）输出停车场中全部车辆的信息。（5）退出系统。12. 迷宫问题【问题描述】迷宫实验是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口， 在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验， 一直到老鼠从入口到出口，而不走错一步。老鼠经多次实验终于得到它学习走迷宫的路线。 设计一个计算机程序对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。

16、【实现提示】可以利用一个二维数组 mazeij表示迷宫，其中1=i=m,1=j=n,m 和n分别代表迷 宫的行数和列数。数组元素值为1表示该位置是墙壁，不能通行；元素值为0表示该位置是通路。假定从 maze11出发，出口位于 mazemn，移动方向可以是 8个方向（东、东 南、南、西南、西、西北、北和东北）。计算机解迷宫时，通常用的是穷举求解的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个 方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，需要用一个后进先出的栈结构来保存从入口到当前位置的路径。13. 哈夫曼编码/译码器

17、【问题描述】利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼编/译码系统。【基本要求】一个完整的系统应具有以下功能：（1） I :初始化（Initialization ）。从终端读入字符集大小n,以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。（2） E：编码（Encoding ）。利用已建好的哈夫曼树（如不在内存，则从文件htmTree中

18、读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。（3） D ：译码（Decoding ）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结 果存入文件TextFile中。（4） P:印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码写入文件CodePrint中。（5）T：印哈夫曼树（Tree Printing ）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。【测试数据】（1）数据一：已知某系统在通信联络中只

19、可能出现8种字符，其概率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,以此设计哈夫曼编码。利用此数据对程序进行调试。（2 ）用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE 。字符A 二BC 1DEFGHIJKLM频度1866413223210321154757153220字符NOPQ |RSTUVWXYZ频度5763151 485180238181161【实现提示】（1）文件CodeFile的基类型可以设为子界型 bit = 0.1。（2） 用户界面可以设计为 菜单

20、”方式：显示上述功能符号，再加上“Q；表示运行Quit。请用户键入一个先功能符，把些功能执行完毕后再经菜单，直至某次用户先把了“ E为止。（3） 在程序的一次执行过程中，第一次执行I、D或C命令之后，哈夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。14. 模拟旅馆管理系统的一个功能 床位的分配与回收【问题描述】某旅馆有n个等级的房间，第I等级有ai个房间，每个等级有bi个床位（10。起始行下面的每一行是鳄鱼的坐标（x, y）,其中x, y都是整数，而且没有任何两只鳄鱼出现在同一个位置。 input.txt 文件以一个负数结尾。【输出要求】程序输

21、出结果输出到 output.txt 文件中。对于每组输入数据，如果 007 可以逃脱，则输出到 output.txt 文件的内容格式如下：第一行是 007 必须跳的最小的步数，然后下面按照跳出顺序记录跳出路径上的鳄鱼坐标(x, y),每行一个坐标。如果007不可能跳出去，则将-1写入文件。如果这里有很多个最短的路径，只需输出其中的任意一种【输入例子】4 1017027 037 045 01 1020 30-1【输出例子】517027 037 045 0-1提示：将每个鳄鱼看作图中的一个顶点。如果007可以从A点跳到B点，则A和B之间就有一条边。19. 最小生成树 :室内布线【问题描述】 装修新

22、房子是一项颇为复杂的工程, 现在需要写个程序帮助房主设计室内电线 的布局。首先, 墙壁上插座的位置是固定的。 插座间需要有电线相连, 而且要布置的整齐美 观,即要求每条线都与至少一条墙边平行,且嵌入四壁或者地板(不能走屋顶)。房主要求知道,要将所有插座连通,自己需要买的电线的最短长度。另外,别忘了每个房间都有门, 电线不可以穿门而过。上图给出了一个有 4 插座的房间的电线布局。【输入要求】 输入由若干组测试数据组成。每组数据的第1行包含房间的长、宽、高和插座的个数 N (N为一个不超过20的正整数)。 接下去的 N 行中,第 i 行给出第 i 个插座的位置坐标( xi,yi,zi )；最后一行

23、包含 4个 3元组(x1,y1,z1 )( x4, y4, z4),分别是长方形门框的 4个角三维坐标。4个数字全部为0表 示全部测试结束，不要对该数据任何处理。注意：这里假设长方体形状的房间完全位于三维直角坐标系的第一象限内，并且有一个角落在原点上。地板位于 x-y 平面。题目数据保证，每个插座仅属于四面墙中的一面，门上没有 插座。要求每段电线的两端必须仅与插座连接，电线之间不能互相交叉焊接。【输出要求】 对每一组测试，在一行里输出要将所有插座连通需要买的电线的最短整数长度。【输入例子】101010 40 1 3.32.5 0 2500.85101000 0 0 31.5 001.50 30

24、00 0【输出例子】2120. 神秘国度的爱情故事【问题描述】 某个太空神秘国度中有很多美丽的小村， 从太空中可以望见， 小村间有路相连， 更精确点说，任意两村之间有且仅有一条路径。小村 A 中有位年轻人爱上了自己村里美丽姑娘。每天早晨，姑娘都要去小村 B 里的面包房 工作，傍晚 6 点回家。年轻人终于决定要向姑娘表白，他打算在小村 C 等着姑娘路过的时 候把爱慕说出来。问题是，他不能确定小村C是否在小村B到小村A之间的路径上。你可帮助他解决这个问题吗？【输入要求】输入由若干组测试数据组成。每组数据的第1行包含一正整数 N (1 N 50000),代表神秘国度中小村的个数，每个小 村即从 0 到 N-1 编号。接下来有 N-1 行输入，每行熬好一条双向道路的两个端点小村的编 号,中间用空格分开。之后一行包含一正整数M (1 M 500000),代表着该组测试问题的个数。接下来M行，每行给出A、B、C三个小村的编号，中间用空格分开。当N为0时，表示全部测试结束，不要对该数据做任何处理。【输出要求】对每一组测试给定的 A、B、C,在一行里输出答案，即：如果C在A和B之间的路径上，输出Yes，否则输出 No。【输入例子】3011230211201210【输出例子】YesNoYes