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

综合实验1 程序源代码的相似性.7综合实验2 马踏棋盘.8综合实验3 迷宫问题.9综合实验4 病人就医管理系统.10综合实验5 离散事件模拟.11综合实验6 宿舍管理查询系统.13综合实验7 集合的并、交和差运算.14综合实验8 一元稀疏多项式计算器.15综合实验9 简单的职工管理系统.17综合实验10 供货信息管理系统.18综合实验11 通讯录管理系统.19综合实验12 停车场管理.20综合实验13 学生成绩管理系统.22综合实验14 运动会分数统计.23综合实验15 基于BST（二叉排序树）的城市信息管理.24综合实验16 社会网络分析系统的设计和实现.25综合实验17 航空客运订票系统.26综合实验18 文学研究助手.27综合实验19 校园导游咨询.28综合实验20 最小生成树问题.29综合实验21 教学计划编制问题.30综合实验22 全国交通咨询模拟.31综合实验1 程序源代码的相似性一、实验目的（1）熟练掌握哈希查找表的建立及查找方式。（2）利用哈希查找表实现程序源代码的相似性判定程序。二、实验内容：【问题描述】：对于两个Java 语言的源程序代码，用哈希表的方法分别统计两个程序中使用Java 语言关键字的情况，并最终按定量的计算结果，得出两份程序的相似性。【基本要求】建立 Java 语言关键字的哈希表，统计在每个源程序中Java 关键字出现的频度, 得到两个向量X1和X2，通过计算向量X1和X2 的相对距离来判断两个源程序的相似性。例如:关键字 Void Int For Char if else while do break class程序 1 关键字频度4 3 0 4 3 0 7 0 0 2程序 2 关键字频度4 2 0 5 4 0 5 2 0 1X1=4,3,0,4,3,0,7,0,0,2X2=4,2,0,5,4,0,5,2,0,1设 s是向量X1和X2 的相对距离，s=sqrt( (xi1-xi2) 2 )，当X1=X2 时，s=0, 反映出可能是同一个程序；s值越大，则两个程序的差别可能也越大。【测试数据】选择若干组编译和运行都无误的Java 程序，程序之间有相近的和差别大的，用上述方法求s, 对比两个程序的相似性。【选作内容】建立源代码用户标识符表，比较两个源代码用户标识符出现的频度，综合关键字频度和用户标识符频度判断两个程序的相似性。综合实验2 马踏棋盘一、实验目的：（1） 熟练掌握栈的基本操作及应用。（2） 利用栈的基本操作，编制实现一个国际象棋的马踏遍棋盘的非递归演示程序。二、实验内容：【问题描述】设计一个国际象棋的马踏遍棋盘的演示程序。【基本要求】将马随机放在国际象棋的88 棋盘Board88 的某个方格中，马按走棋规则进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格。编制非递归程序，求出马的行走路线，并按求出的行走路线，将数字1，2，64 依次填入一个88 的阵，输出之。【测试数据】由读者指定。可自行指定一个马的初始位置【实现提示】下页图显示了马位于方格（2，3）时，8 个可能的移动位置。一般来说，当马位于位置（i，j）时，可以走到下列8 个位置之一(I2， j1)，(I1，j2)，(I1，j2)，(I2，j1)，(I2，j1)，(I1，j2)，(I1，j2)，(I2j1)但是，如果（i，j）靠近棋盘的边缘，上述有些位置可能超出棋盘范围，成为不允许的位置。8 个可能位置可以用两个一维数组Htry10.7和Htry20.7来表示。位于（I，j）的马可以走到的新位置是在棋盘范围内的（IHtry1h，jHtry2h），其中h0，1，7。每次在多个可走位置中选择其中一个进行试控，其余未曾试过的可走位置必须用适当结构妥善管理，以备试探失败时的“回溯”（悔棋）使用。【选作内容】（1） 求出从某一起点出发的多条以至全部行走路线。（2） 探讨每次选择位置的“最佳策略”，以减少回溯的次数。（3） 演示寻找行走路线的回溯过程。综合实验3 迷宫问题一、实验目的：（1） 熟练掌握链栈的基本操作及应用。（2） 利用链表作为栈的存储结构，设计实现一个求解迷宫的非递归程序。二、实验内容：【问题描述】以一个mn 的长方阵表示迷宫，0 和1 分别表示迷宫中的通路和障碍。设计一个程序，对信任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。【基本要求】首先实现一个链表作存储结构的栈类型，然后编写一个求解迷宫的非递归程序。求得的通路以三元组（i,j,d）的形式输出，其中：（i,j）指示迷宫中的一个坐标，d表示走到下一坐标的方向。如：对于下列数据的迷宫，输出的一条通路为：（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3，1，2），。【测试数据】迷宫的测试数据如下：左上角（1，1）为入口，右下角（8，9）为出口。1 2 3 4 5 6 7 80 0 1 0 0 0 1 00 0 1 0 0 0 1 00 0 0 0 1 1 0 10 1 1 1 0 0 1 00 0 0 1 0 0 0 00 1 0 0 0 1 0 10 1 1 1 1 0 0 11 1 0 0 0 1 0 11 1 0 0 0 0 0 0【实现提示】计算机解迷宫通常用的是“穷举求解”方法，即从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。假如所有可能的通路都探索到则未能到达出口，则所设定的迷宫没有通睡。可以二维数组存储迷宫数据，通常设定入口点的下标为（1，1），出口点的下标为（n,n）。为处理方便起见，可以迷宫的四周加一圈障碍。对于迷宫任一位置，均可约定有东、南、西、北四个方向可通。【选作内容】（） 编写递归形式的算法，求得迷宫中所有可能的通路；（） 以方阵形式输出迷宫及其通路。综合实验 4 病人就医管理系统一、实验目的（1） 熟练掌握队列的两种存储方式。（2） 掌握队列的基本操作及应用。（3） 利用队列实现病人就医管理模拟程序。二、实验内容：【问题描述】设计一个病人就医管理系统【基本要求】编写一个程序定义行医类，反映病人到医院看病，排队看医生的情况，在病人排队过程中，主要发生两件事：（1） 病人到达诊室，将病历本交给护士，排到等待队列中候诊。（2） 护士从等待队列中取出一位病人的病历，该病人进入诊室就诊。要求程序采用菜单方式，其选项及功能说明如下：（1） 排队-输入病人的病历号，加入到病人排队队列中（2） 就诊-病人排队队列中最前面的病人就诊，并将其从队列中删除。（3） 查看排队-从队首到队尾列出所有的排队病人的病历号。（4） 下班-退出运行。【实现提示】病人到达诊室，输入病人的病历号，加入到病人排队队列中。-病人排队队列中最前面的病人就诊，并将其从队列中删除。【测试数据】自己指定。综合实验5 离散事件模拟一、实验目的：（1） 熟练掌握队列的两种存储方式。（2） 掌握队列的基本操作及应用。（3） 利用链式存储线性表和队列实现银行业务模拟程序。二、实验内容：【问题描述】客户业务分为两种。第一种是申请从银行得到一笔资金，即取款或借款。第二种是向银行投入一笔资金，即存款或还款。银行有两个服务窗口，相应地有两个队列。客户到达银行后先排第一个队。处理每个客户业务时，如果属于第一种，且申请额超出银行现存资金总额而得不到满足，则立刻排入第二个队等候，直至满足时才离开银行；否则业务处理完后立刻离开银行。每接待完一个第二种业务的客户，则顺序检查和处理（如果可能）第二个队列中的客户，对能满足的申请者予以满足，不能满足者重新排到第二个队列的队尾。注意，在此检查过程中，一旦银行资金总额少于或等于刚才第一个队列中最后一个客户（第二种业务）被接待之前的数额，或者本次已将第二个队列检查或处理了一遍，就停止检查（因为此时已不可能还有能满足者）转而继续接待第一个队列的客户。任何时刻都只开一个窗口。假设检查不需要时间。营业时间结束时所有客户立即离开银行。写一个上述银行业务的事件驱动模拟系统，通过模拟方法求出客户在银行内逗留的平均时间。【基本要求】利用动态存储结构实现模拟。【测试数据】一天营业开始时银行拥有的款额为10000（元），营业时间为600（分钟）。其他模拟参量自定，注意测定两种极端的情况：一是两个到达事件之间的间隔时间很短，而客户的交易时间很长，另一个恰好相反，设置两个到达事件的间隔时间很长，而客户的交易时间很短。【实现提示】事件有两类：到达银行和离开银行。初始时银行现存资金总额为total。开始营业后的第一个事件是客户到达，营业时间从0 到closetime。到达事件发生时随机地设置此客户的交易时间和距下一到达事件之间的时间间隔。每个客户要办理的款额也是随机确定的，用负值和正值分别表示第一类和第二类业务。变量total, closetime以及上述两个随机量的上下界均交互地从终端读入，作为模拟参数。两个队列和一个事件表均要用动态存储结构实现。注意弄清应该在什么条件下设置离开事件，以及第二个队列用怎样的存储结构实现时可以获得较高的效率。注意：事件表是按时间顺序有序的。【选作内容】自己实现动态数据类型。例如对于客户结点，定义pool 为CustNode poolMAX；/结构类型CustNode含四个域：arrtime, durtime, amount, next或者定义四个同样长的，以上述域名为名字的数组。初始时，将所有分量的next 域链接起来，形成一个静态链栈，设置一个栈顶元素下标指示量top,tip=0 表示栈空。动态存储分配函数可以取名为myMalloc，其作用是出栈，将栈顶元素的下标返回。若返回的值为0，则表示无空间可分配。归还函数可取名为myFree，其作用是把该分量入栈。用FORTRAN 和BASIC等语言实现时只能如此地自行组织。综合实验6 宿舍管理查询系统一、实验目的（1）熟练掌握排序算法。（2）熟练掌握二分查找算法。（3）利用二分查找实现宿舍管理查询系统。二、实验内容：【问题描述】设计一个宿舍管理查询系统【基本要求】程序设计要求：A. 采用交互工作方式B. 建立数据文件，数据文件按关键字（姓名、学号、房号）进行排序(冒泡、选择、插入排序等任选一种)2) 查询菜单: (用二分查找实现以下操作)A. 按姓名查询B. 按学号查询C. 按房号查询3) 打印任一查询结果（可以连续操作）【测试数据】自己指定。综合实验7 集合的并、交和差运算一、实验目的：（1） 熟练掌握线性表顺序或链式存储（2） 掌握有序链表的操作。（3） 以有序链表表示集合，编制一个能演示执行集合的并、交和差运算的程序。二、 实验内容：【问题描述】编制一个能演示执行集合的并、交和差运算的程序。允许采用顺序存储或链式存储来实现。【基本要求】（1） 集合的元素限定为小写字符a. .z。（2） 演示程序以用户和计算机的对话方式执行。【测试数据】(1) Set1magazine ，Set2paper，Set1Set2aeginmprz，Set1Set2ae，Set1Set2gimnz。(2) Set10120per4a6tion89，Set2error data，Set1Set2adeinoprt，Set1Set2aeort，Set1Set2inp。【实现提示】以有序链表表示集合。【选作内容】（1） 集合的元素判定和子集判定运算。（2） 求集合的补集。（3） 集合的混合运算表达式求值。（4） 集合的元素类型推广到其他类型，甚至任意类型。综合实验8 一元稀疏多项式计算器一、实验目的：（1） 熟练掌握线性表链式存储（2） 掌握有序链表的操作及应用。（3） 利用带表头结点的单链表存储多项式，设计一个一元稀疏多项式简单计算器实现多项式的加减运算。二、实验内容：【问题描述】设计一个一元稀疏多项式简单计算器。【基本要求】一元稀疏多项式简单计算器的基本功能是：（1） 输入并建立多项式；（2） 输出多项式，输出形式为整数序列：n,c1,e1,c2,e2,cn,en,其中n 是多项式的项数，ci和ei分别是第I项的系数的指数，序列按指数降序排列；（3） 多项式a和b 相加，建立多项式ab；（4） 多项式a和b 相减，建立多项式ab。【测试数据】(1）(2x5x83.1x11)+(75x811x9)=(3.1x11+11x92x7)(2) (6x3x+4.4x21.2x9)(6x35.4x2x27.8x15)(7.8x151.2x912x3x)(3) 1xx2x3+x4x5)(x3x4)(1xx2x5)(4) (x+x3)(xx3)0(5 ( x x100)(x100x200)(x2x100x200)(6) (xx2x3)0xx2x3(7) 互换上述测试数据中的前后两个多项式【实现提示】用带表头结点的单链表存储多项式。【选作内容】（1） 计算多项式在x 处的值。（2） 求多项式a 的导函数a1。（3） 多项式a和b 相乘，建立乘积多项式ab。（4） 多项式的输出形式为类数学表达式。例如，多项式3x86x318 的输出形式为3x86x318，x15(8)x714 的输出形式为x158x714。注意，系数值为1的非零次项的输出形式中略去系数1，如项1x8 的输出形式为x8，项x3 的输出形式为x3。（5） 计算器的仿真界面。综合实验9 简单的职工管理系统一、实验目的（1）熟练掌握线性表基本操作及应用。（2）利用线性表实现简单的职工管理系统。二、实验内容：【问题描述】对单位的职工进行管理，包括插入、删除、查找、排序等功能。【基本要求】职工对象包括姓名、性别、出生年月、工作年月、学历、职务、住址、电话等信息。（1）新增一名职工：将新增职工对象按姓名以字典方式职工管理文件中。（2）删除一名职工：从职工管理文件中删除一名职工对象。（3）查询：从职工管理文件中查询符合某些条件的职工。（4）修改：检索某个职工对象，对其某些属性进行修改。（5）排序：按某种需要对职工对象文件进行排序。【测试数据】自己指定。注意尽量覆盖算法的各种情况。【实现提示】职工对象数不必很多，便于一次读入内存，所有操作不经过内外存交换。（1）由键盘输入职工对象，以文件方式保存。程序执行时先将文件读入内存。（2）对职工对象中的姓名按字典顺序进行排序。（3）对排序后的职工对象进行增、删、查询、修改、排序等操作。【选作内容】将职工对象按散列法存储，并设计解决冲突的方法。在此基础上实现增、删、查询、修改、排序等操作。综合实验10 供货信息管理系统一、实验目的：（1）熟练掌握栈的基本操作及应用。（2）利用栈的基本操作，设计实现一个供货信息管理系统。二、实验内容：【问题描述】：实现一个供货信息管理系统。【基本要求】系统功能包括取货、上货、倒货架以及对商品进行查询。取货是从货架拿商品，上货是把商品放到货架上。一天营业结束，如果货架不满，则需上货。如果直接将商品摆放到货架上，则会使生产日期越近的越靠上.这就需要倒货架。【测试数据】自己指定。【实现提示】商店货架以栈的形式摆放商品，生产日期越近的越靠近栈底，出栈是从栈顶取货，一天营业结束，如果货架不满，则需上货。如果直接将商品摆放到货架上，则会使生产日期越近的越靠近栈顶.这就需要倒货架，仍使生产日期越近的越靠近栈底。写出货物进栈、出栈算法。【选作内容】用栈的两种存储结构实现。综合实验11 通讯录管理系统一、实验目的（1）熟练掌握线性表基本操作及应用。（2）利用线性表实现简单的通讯录管理系统。二、实验内容：【问题描述】实现一个简单通讯录管理系统。【基本要求】通讯录内容包括每个人的姓名及电话、QQ、E_mail四项内容；通讯录中的内容按姓名顺序（升序）存放；插入一项新的信息或修改一项信息后通讯录任然有序；查询某人的信息时，如果找到了，则显示该人的信息，如果未找到，则提示通讯录中没有此人的信息；修改某人的信息，如果未找到要修改的人，则提示通讯录中没有此人的信息；删除某人的信息，如果未找到要删除的人，则提示通讯录中没有此人的信息；能显示通讯录中的所有记录；采用菜单操作。【测试数据】自己指定。【选作内容】通讯录的内容保存到数据文件中。综合实验12 停车场管理一、实验目的：（1） 熟练掌握栈顺存和链存两种存储方式。（2） 掌握栈的基本操作及应用。（3） 以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。二、实验内容：【问题描述】设停车场是一个可停放n 辆汽车的长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车信放在车场的最北端），若车场内已停满n 辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；当停车场内某辆车要离开时，在它之后进入的车辆必须先退出车场为它让路，待该辆车开出大门外，其他车辆再按原次序进入车场院，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。【基本要求】以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；若是车辆离去，则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表结构实现。【测试数据】设 n=2，输入数据为：(A，1，5)，（A，1，15），（A，3，20），（A，4，25），（A，5，30），（D ，2 ，35），（D ，4 ，40），（E ，0 ，0 ）。其中：A表示到达（Arrival）；D 表示离去（Departure）；E 表示输入结束（End）。【实现提示】需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。【选作内容】（1） 两个栈共享空间，思考应开辟数组的空间是多少？（2） 汽车可有不同种类，则他们的占地面积不同收费标准也不同，如1 辆客车和1。5辆小汽车的占地面积相同，1辆十轮卡车占地面积相当于3 辆小汽车的占地面积。（3） 汽车可以直接从便道开走，此时排在它前面的汽车要先开走让路，然后再依次排到队尾。（4） 停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修改结构以满足这种要求。综合实验13 学生成绩管理系统一、实验目的（1）掌握线性链表的建立。(2) 掌握线性链表的基本操作。(3) 掌握查找的基本算法。二、实验内容：【问题描述】利用线性链表实现学生成绩管理系统，学生信息包含学号、姓名、成绩1、成绩2、总分五项。【基本要求】能实现学生成绩的输入、输出、插入、删除、查找、排序、分类统计等功能；学生成绩的原始状态按学号排序；可以按成绩的高低排序；计算每个同学的总分；计算每门课程的平均分。【测试数据】自己指定。【选作内容】成绩的内容保存到数据文件中。综合实验14 运动会分数统计一、实验目的：（1） 熟练掌握线性表的两种存储方式（2） 掌握链表的操作和应用。（3） 掌握指针、结构体的应用（4）按照不同的学校，不同项目和不同的名次要求，产生各学校的成绩单、团体总分报表。二、 实验内容：【问题描述】参加运动会的n 个学校编号为1n。比赛分成m 个男子项目和w 个女子项目，项目编号分别为1m和m1mw。由于各项目参加人数差别较大，有些项目取前五名，得分顺序为7，5，3，2，1；还有些项目只取前三名，得分顺序为5，3，2。写一个统计程序产生各种成绩单和得分报表。【基本要求】产生各学校的成绩单，内容包括各校所取得的每项成绩的项目号、名次（成绩）、姓名和得分；产生团体总分报表，内容包括校号、男子团体总分、女子团体总分和团体总分。【测试数据】对于n4，m3，w2，编号为奇数的项目取前五名，编号为偶数的项目取前三名，设计一组实例数据。【实现提示】可以假设m20，m30，w20，姓名长度不超过20个字符。每个项目结束时，将其编号、类型符（区分取前五名还是前三名）输入，并按名次顺序输入运动员姓名、校名（和成绩）。【选作内容】允许用户指定某些项目可采取其他名次取法。综合实验15 基于 BST（二叉排序树）的城市信息管理一、实验目的掌握二叉排序树的基本操作。二、实验内容：【问题描述】利用二叉排序树实现城市信息管理，城市信息包括城市名、城市坐标（X,Y）。【基本要求】将若干城市信息按城市名的顺序建立二叉排序树；可以插入一个城市信息；按城市名查找一个城市信息；输入一个城市名，查找和该城市名的距离在指定范围内的所有城市。【测试数据】自己指定。【选作内容】删除一个城市信息。综合实验16 社会网络分析系统的设计和实现一、实验目的（1）熟练掌握图的基本操作及应用。（2）利用图实现简单的社会网络分析系统。二、实验内容：【问题描述】：实现一个社会网络分析系统。【基本要求】系统功能主要包括：（1） 对email数据进行预处理,利用数据结构课程中图中的理论，建立社会网络的邻接矩阵。（2） 利用度的概念,找出社会网络中核心人物、活跃人物和边缘人物。.（3）. 利用子图概念分析社会网络的结构，找出小团体和联系小团体的桥接人物。.（4） 能查找任何人的交往圈子.【测试数据】自己指定。综合实验17 航空客运订票系统一、实验目的：（1） 熟练掌握线性表基本操作及应用。（2） 熟练掌握队列基本操作及应用。（3） 利用线性表和队列实现航空客运订票系统。二、实验内容：【问题描述】航空客运订票的业务活动包括；查询航线、客票预订和办理退票等。试设计一个航空客运订票系统，以使上述业务可以借助计算机来完成。【基本要求】（1）每条航线所涉及的信息有：终点站名、航班名、飞机号、飞行周日（星期几）、乘员定额、余票量、已订票的客户名单（包括姓名、订票量、舱位等级1，2 或3）以及等候替补的客户名单（包括姓名、所需票量）；（2）作为示意系统，全部数据可以只放在内存中；（3）系统能实现的操作和功能如下：查询航线：根据旅客提出的终点站名输出下列信息：航班号、飞机号、星期几飞行，最近一天航班的日期和余票额；承办订票业务：根据客户提出的要求（航班号、订票数额）查询该航班票额情况，若尚有余票，则为客户办理订票手续，输出座位号；若已满员或余票额少于订票额，则需重新询问客户要求。若需要，可登记排队候补；承办退票业务：根据客户提供的情况（日期、航班），为客户办理退票手续，然后查询该航班是否有人排队候补，首先询问排在第一的客户，若所退票额能满足客户的要求，则为客户办理订票手续，否则依次询问其他排队候补的客户。【测试数据】由读者自行指定。【实现提示】两个客户名单可分别由线性表和队列实现。为查找方便，已订票客户的线性表应按客户姓名有序，并且为了插入和删除方便，应以链表作为存储结构。由于预约人数无法预计，队列也应以链表作存储结构。整个系统需汇总各条航线的情况登录在一张线性表上，由于航线基本不变，可采用顺序存储结构，并按航班有序或按终点站名有序。每条航线是这张表上的一个记录，包含上述8 个域、其中乘员名单域为指向乘员名单链表的头指针，等候替补的客户名单域为分别指向队头和队尾的指针。【选作内容】当客户订票要求不能满足时，系统可向客户提供到达同一目的地的其他航线情况。读者还可充分发挥自己的想象力，增加你的系统的功能和其他服务项目。综合实验18 文学研究助手一、 实验目的（1） 熟练掌握串的基本操作及应用。（2） 熟练掌握串的匹配操作算法。（3） 基于串的存储和操作，实现对英文文章文字统计系统。二、 实验内容【问题描述】文学研究人员需要统计某段英文小说中某些形容词的出现次数和位置。试写一个实现这一目标的文字统计系统，称为“文学研究助手”。【基本要求】输入一段英文，再输入一个单词，查找该单词在该段英文中出现的次数及位置，位置信息保存在一个数组中。【测试数据】自己指定。【实现提示】约定小说中的词汇一律不跨行。这样。每读入一行，就统计每个词在这行中的出现次数。【选作内容】（1）英文小说存于一个文本文件中。(2) 自动统计英文段中所有单词出现的