数据结构课程设计题目(1).docx

数据结构课程设计题目(1) 数据结构课程设计题目 1.表达式求值 问题描述： 一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的。假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值。 基本要求： （1）从键盘读入一个合法的算术表达式，输出正确的结果。 （2）显示输入序列和栈的变化过程。 选作内容： （1）扩充运算符集合。 （2）引入变量操作数。 （3）操作数类型扩充到实数。 2. 简单的员工管理系统 问题描述： 每个员工的信息包括编号、姓名、性别、出生年月、学历、职务、电话、住址等。系统的功能如下。 实习要求： （1）查询：按特定条件查找员工。 （2）修改：按编号对某个员工的某项信息进行修改。 （3）插入：加入新员工的信息。 （4）删除：按编号删除已离职的员工的信息。 （5）排序：按特定条件对所有员工的信息进行排序。 3. 迷宫问题 问题描述： 迷宫实验是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口到出口，而不走错一步。老鼠经多次实验终于得到它学习走迷宫的路线。设计一个计算机程序对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。 实现提示： 可以利用一个二维数组mazeij表示迷宫，其中1<=i<=m,1<=j<=n,m和n分别代表迷宫的行数和列数。数组元素值为1表示该位置是墙壁，不能通行；元素值为0表示该位置是通路。假定从maze11出发，出口位于mazemn，移动方向可以是8个方向（东、东南、南、西南、西、西北、北和东北）。计算机解迷宫时，通常用的是“穷举求解”的方法，即从入口出发，顺某一方向向前探索，若能走通，则继续往前走；否则沿原路退回，换一个方向再继续探索，直至所有可能的通路都探索到为止。为了保证在任何位置上都能沿原路退回，需要用一个后进先出的栈结构来保存从入口到当前位置的路径。 4.最小生成树的两种算法 要求：任意创建一个图，分别用Prime算法和kruskal算法，求出该图的最 小生成树。 5.二叉树的竖向显示 问题描述：建立二叉树按照二叉链表方式存储，编写算法，要求实现二叉树的竖向显示（竖向显示就是二叉树的按层显示）。如下图所示： 测试数据：输入ABDCEF （其中符号“”表示空格（space）字符） 6.停车场管理 问题描述： 设停车场是一个可停放n辆车的狭长通道，且只有一个大门可供汽车进出。在停车场内，汽车按到达的先后次序，由北向南依次排列（假设大门在最南端）。若车场内已停满n辆车，则后来的汽车需在门外的便道上等候，当有车开走时，便道上的第一辆车即可开入。当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门后，其他车辆再按原次序返回车场。每辆车离开停车场时，应按其停留时间的长短交费（在便道上停留的时间不收费）。 基本要求： （1）要求以顺序栈模拟停车场，以链队列模拟便道。 （2）从终端读入汽车到达或离去的数据，每组数据包括三项：是“到达”还是“离去”；汽车牌照号码；“到达”或“离去”的时刻。与每组输入信息相应的输出信息为：如果是到达的车辆，则输出其在停车场中或便道上的位置；如果是离去的车辆，则输出其在停车场中停留的时间和应交的费用。 7.约瑟夫环 问题描述：约瑟夫问题的一种描述是：编号为1，2，n 的n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个整数作为报数上限值m,从第一个人开始顺时针自1开始顺序报数，报到m 时停止报数。报 m 的人出列，将他的密码作为新的m 值，从他在顺时针方向上的下一个人开始 重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序，求出出列顺序。 利用单向循环链表作为存储结构模拟此过程，按照出列顺序打印出各人的编号。 测试数据： m 的初值为20；n =7，7个人的密码依次是：3，1，7，2，4，8，4，出列的顺序为6，1，4，7，2，3，5。 8.交通咨询系统 设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到另一个城市顶点之间的最短里程、最低花费或最少时间等问题。对于不同的咨询要求，可输入城市间的路程、所需时间或所需费用。 9.学生管理系统 已知有20个学生记录（包括学号、姓名、班级、性别、出生年月、成绩，所有学生以学号从小到大排序。 要求：编程序实现查询、排序、插入、删除等功能。具体要求如下： （1）要求显示如下界面 * 1-查询 2-排序 3-插入 4-删除 5-退出 * 通过选择1-4来确定要做哪一个操作。 （2）若选1，则出现如下界面 * 1.1-按学号查询 1.2-按姓名查询 1.3-按成绩查询 * 通过选择1.1-1.3来确定要做哪一个操作，找到该生将学生记录输出到屏幕，若查无此人，输出相关信息。 （3）若选2，则按成绩从大到小排序，姓名，学号顺序也随之调整。 （4）若选3，将一个新学生记录按学号顺序插入。 （5）若选4，删除指定学生的记录。 （6）若选5，则退出程序。 （7）以上各个功能均编写成子函数，由主函数调用实现。 10利用链表实现工资报表管理系统 已知N个职工的姓名、职工编号、基本工资、附加工资和扣除工资。 要求： 编写函数：计算每个职工的实发工资；按职工编号由小到大顺序排列，相应数据也要随之调整；要求输入一个职工编号，找出该职工的数据，从主函数输入要查找的职工号，输出该职工的数据； 以上各个功能均编写成子函数，由主函数调用实现。 根据题意此题用4个函数完成： main 函数：总控函数 compute函数：计算函数（求每个职工的实发工资） sort函数：排序函数（按职工编号从小到大排列） search函数：查找函数（按给定的职工编号进行查找） 11哈夫曼编码、译码器 12订票系统 通过此系统可以实现如下功能： （1）录入： 可以录入航班情况（数据可以存储在一个数据文件中，数据结构、具体数据自定） （2）查询： 可以查询某个航线的情况（如，输入航班号，查询起降时间，起飞抵达城市，航班票价，票价折扣，确定航班是否满仓）； 可以输入起飞抵达城市，查询飞机航班情况； （3）订票：（订票情况可以存在一个数据文件中，结构自己设定） 可以订票，如果该航班已经无票，可以提供相关可选择航班； （4）退票：可退票，退票后修改相关数据文件； 客户资料有姓名，证件号，订票数量及航班情况，订单要有编号。 （5）修改航班信息：当航班信息改变可以修改航班数据文件 要求：根据以上功能说明，设计航班信息，订票信息的存储结构，设计程序完成功能； 13运动会分数统计 问题描述：参加运动会有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以内的整数（如果做得更好可以输入学校的名称，运动项目的名称） 输出形式：有中文提示，各学校分数为整形 界面要求：有合理的提示，每个功能可以设立菜单，根据提示，可以完成相关的功能要求。 存储结构：学生自己根据系统功能要求自己设计，但是要求运动会的相关数据要存储在数据文件中。（数据文件的数据读写方法等相关内容在c语言程序设计的书上，请自学解决）请在最后的上交资料中指明你用到的存储结构； 测试数据：要求使用1、全部合法数据；2、整体非法数据；3、局部非法数据。进行程序测试，以保证程序的稳定。测试数据及测试结果请在上交的资料中写明； 14.二叉树操作 创建二叉树，求二叉树的叶子数、总结点数、深度，并输出二叉树的先序、中序、后序遍历的序列（此处为了说明非递归算法，中序遍历采用递归和非递归两种算法，其余采用递归算法）。 15.各种排序 问题描述：利用随机函数产生N个随机整数（2000以上），对这些数利用 插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序等排序方法进行排序，并统计每一种排序上机所花费的时间。 输入的数据形式为任何一个正整数，大小不限。 输出的形式：数字大小逐个递增的序列。 16. 八皇后问题 八皇后问题，是一个古老而著名的问题，在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法？ 17.文本文件中单词的检索与计数 要求编程建立一个文本文件，每个单词不包括空格且不跨行，单词由字符序列构成且区分大小写，统计给定单词在文本文件中出现的总次数，检索输出的某个单词出现在文本中的行号、在该行中出现的次数以及位置。 18.通讯录管理系统 要求：利用链表编程序实现插入、查询、删除、更新以及通讯录信息的输出等信息。要求显示如下界面： * 1通讯录链表的建立 2通讯者信息的插入 3通讯者信息的查询 4通讯者信息的修改 5通讯者信息的删除 6通讯者信息的输出 0退出管理系统 * 通过选择0-6来确定要做哪一个操作。 19. 哈希表设计 假设人名为中国人的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突。 20.拓扑排序 问题描述：建立图的存储结构，能够输入图的顶点和边的信息，并存储到相应的存储结构中，再编写函数实现图的拓扑排序。 基本要求：选择邻接表作为有向图的存储结构模拟整个过程，并输出拓扑排序的顶点序列。 测试数据：利用下图中的数据调试程序 21.宿舍管理查询 为宿舍管理人员编写一个宿舍管理查询软件，程序设计要求： （1）建立数据文件，数据文件按关键字（姓名、学号、宿舍号）进行排序。 （2）实现如下查询功能： 按姓名查询 按学号查询 按宿舍查询 （3）打印任意查询结果 22.背包问题 假设有一个能装入总体积为T的背包和n件体积分别为w1，w2,w n的物品，能否从n件物品中挑选若干件恰好装满背包，即使w1+w2+w n=T,要求找出所有满足上述条件的解。例如：当T=10，各件物品的体积为1，8，4，3，5，2时，可以找到下列4组解：（1，4，3，2）、（1，4，5）、（8，2）、（3，5，2）