数据结构实验题目与要求.ppt

数据结构与算法实验数据结构与算法实验计算机软件所计算机软件所2015.092015.09数据结构与算法实验数据结构与算法实验实验一实验一 背包问题的求解背包问题的求解实验二实验二 农夫过河问题的求解农夫过河问题的求解实验三实验三 简易电子表格的设计简易电子表格的设计实验四实验四 八皇后问题八皇后问题实验五实验五 约瑟夫环问题仿真约瑟夫环问题仿真实验六实验六 教学计划编制问题（教学计划编制问题（*）实验七实验七 二叉排序树与平衡二叉树的实现（二叉排序树与平衡二叉树的实现（*）实验八实验八 停车场模拟管理程序的设计与实现停车场模拟管理程序的设计与实现实验九实验九 学生成绩分析学生成绩分析实验十实验十 一元稀疏多项式计算器一元稀疏多项式计算器实验十一、哈夫曼压缩实验十一、哈夫曼压缩/解压缩算法（编译码器）（解压缩算法（编译码器）（*）实验十二、全国交通咨询模拟系统（实验十二、全国交通咨询模拟系统（*）实验十三、迷宫问题实验十三、迷宫问题（*）2西安交通大学计算机系数据结构与算法实验数据结构与算法实验注注：从从上上述述题题目目中中任任选选3 3题题目目，打打星星号号至至少选少选1 1题，共题，共3 3个实验！个实验！3西安交通大学计算机系成绩评定成绩评定题目完成情况的验收题目完成情况的验收基本题目基本题目验收时间：上机时间完成当场验收验收时间：上机时间完成当场验收验收方式：本人简要介绍完成的情况，并检查程序运行结果验收方式：本人简要介绍完成的情况，并检查程序运行结果成绩评定：按照预先给定的各题分值进行成绩评定成绩评定：按照预先给定的各题分值进行成绩评定选做题目选做题目验收时间：上机时间完成当场验收，并给所指定的分数验收时间：上机时间完成当场验收，并给所指定的分数验收方式：填写成绩评定考核表，本人简要介绍完成的情况，检查程序运验收方式：填写成绩评定考核表，本人简要介绍完成的情况，检查程序运行结果，提交专题实验报告行结果，提交专题实验报告成绩评定：实验题目完成情况和报告完成情况，最后核定成绩成绩评定：实验题目完成情况和报告完成情况，最后核定成绩结果正确程序没有结果正确程序没有BUGBUG并有独到之处成绩为所给题目分数的并有独到之处成绩为所给题目分数的9090100100结果正确程序没有结果正确程序没有BUGBUG成绩为所给题目分数的成绩为所给题目分数的75-9075-90结果不完全正确成绩为所给题目分数的结果不完全正确成绩为所给题目分数的60-75%60-75%结果不正确成绩为所给题目分数的结果不正确成绩为所给题目分数的60%0)个人按顺时针方向围坐一圈，每人持有一个正整数密码。开始时任意给出一个报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人起重新自1报数；如此下去直到所有人全部出列为止。2.2.基本要求基本要求 设计一个程序模拟此过程，给出出列人的编号序列。3、实现提示：可考虑不带头结点的单链表结构。4、测试数据：N=7，七个人的密码依次为3，1，7，2，4，8，4.初始报数上限值m=20。9西安交通大学计算机系实验六实验六 教学计划编制问题教学计划编制问题1.1.问题描述问题描述 大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年 限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业 开设的课程都是固定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门 课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。2.2.基本要求基本要求 (1)输入参数包括：学期总数，一学期的学分上限，每门课的课程号(固定占3位的字母数字串)、学分和直接先修课的课程号。(2)允许用户指定下列两种编排策略之一：一是使学生在各学期中的 学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。(3)若根据给定的条件问题无解，则报告适当的信息；否则，将教学 计划输出到用户指定的文件中。计划的表格格式自行设计。3 3、实现提示：、实现提示：可设学期总数不超过12，课程总数小于100。如果输入的先修课程号不在该专业开设的课程序列中，则作为错误处理。10西安交通大学计算机系实验六实验六 教学计划编制问题教学计划编制问题(续续)3.3.测试数据测试数据 学期总数：6；学分上限：10；该专业共开设12门课，课程号从C01 到C12，学分顺序为2，3，4，3，2，3，4，4，7，5，2，3。先修关系见 下图。45271381210911611西安交通大学计算机系实验七实验七 二叉排序树与平衡二叉树的实现二叉排序树与平衡二叉树的实现1.1.问题描述问题描述 分别采用二叉链表和顺序表作存储结构，实现对二叉排序树与平衡 二叉树的操作。2.2.基本要求基本要求 (1)用二叉链表作存储结构实现二叉排序树。1)以回车符(n)为输入结束标志，输入数列L，生成一棵二叉排序 树T；2)对二叉排序树T作中序遍历，输出结果；3)计算二叉排序树T查找成功的平均查找长度，输出结果；4)输入元素x，查找二叉排序树T，若存在含x的结点，则删除该结 点，并作中序遍历(执行操作2)；否则，输出信息“无x”；12西安交通大学计算机系实验七实验七 二叉排序树与平衡二叉树的实现二叉排序树与平衡二叉树的实现(续续)(2)用顺序表(一维数组)作存储结构-静态链表 1)以回车符(n)为输入结束标志，输入数列L，生成一棵二叉排序 树T；2)对二叉排序树T作中序遍历，输出结果；3)计算二叉排序树T查找成功的平均查找长度，输出结果；4)输入元素x，查找二叉排序树T，若存在含x的结点，则删除该结 点，并作中序遍历(执行操作2)；否则，输出信息“无x”；(3)用二叉链表作存储结构实平衡的二叉排序树。1)用数列L，生成平衡的二叉排序树BT：当插入新元素之后，发现 当前的二叉排序树BT不是平衡的二叉排序树，则立即将它转换成新的平 衡的二叉排序树BT；2)计算平衡的二叉排序树BT的平均查找长度，输出结果。13西安交通大学计算机系实验八实验八 停车场模拟管理程序的设计与实现停车场模拟管理程序的设计与实现1.1.问题描述问题描述 设停车场只有一个可停放几辆汽车的狭长通道，且只有一个大门可供汽车进 出。汽车在停车场内按车辆到达的先后顺序依次排列，若车场内已停满几辆汽车，则后来的汽车只能在门外的便道上等候，一旦停车场内有车开走，则排在便道 上的第一辆车即可进入；当停车场内某辆车要离开时，由于停车场是狭长的通道，在它之后开入的车辆必须先退出车场为它让路，待该车辆开出大门，为它让路 的车辆再按原次序进入车场。在这里假设汽车不能从便道上开走，试设计这样一 个停车场模拟管理程序。2.2.数据结构设计数据结构设计 (1)为了便于区分每辆汽车并了解每辆汽车当前所处的位置，需要记录汽车的 牌照号码和汽车的当前状态，所以为汽车定义一个新的类型CAR，具体定义如下：typedef struct char*license_plate;/汽车牌照号码，定义为一个字符指针类型 char state;/汽车的当前状态，字符s表示停放在停车位上，/字符p表示停放在便道上，每辆车的初始状态用 /字符I表示。CAR14西安交通大学计算机系实验八实验八实验八实验八 停车场模拟管理程序的设计与实现停车场模拟管理程序的设计与实现停车场模拟管理程序的设计与实现停车场模拟管理程序的设计与实现(续续续续)(2)由于车位是一个狭长的通道，所以不允许两辆车同时进入停车位，当有车到来要 进入停车位的时候车要顺次停放，当某辆车要离开时，比它后到的车要先暂时离开 停车位，而且越后到的车就越先离开停车位，显然这和栈的“后进先出”特点相吻合，所以可以使用一个栈来描述停车位。由于停车位只能停放有限的几辆车，而且为了便于停车场的管理，要为每个车 位分配一个固定的编号，不妨设为1、2、3、4、5(可利用数组的下标)，分别表示停 车位的1车位、2车位、3车位、4车位、5车位，针对这种情况使用一个顺序栈比较方 便，具体定义如下：#define MAX_STOP 5 typedef stuct CAR STOPMAX_STOP;/各汽车信息的存储空间 into top;/用来指示栈顶位置的静态指针 STOPPING;(3)当停车场的停车位上都已经停满了汽车，又有新的汽车到来时要把它调度到便道 上，便道上的车辆要按照进入便道的先后顺序顺次存放在便道上，为便道上的每个 位置也分配一个固定的编号，当有车从停车位上离开后，便道上的第一辆汽车就立 即进入停车位上的某个车位，由于问题描述中限制了便道上的汽车只能从便道上开15西安交通大学计算机系实验八实验八实验八实验八 停车场模拟管理程序的设计与实现停车场模拟管理程序的设计与实现停车场模拟管理程序的设计与实现停车场模拟管理程序的设计与实现(续续续续)走，既便道上的汽车只能在停车位上停放过之后才能离开停车位，这样越早进入便道的汽车就越早进入停车位，而且每次进入停车位的汽车都是处于便道“最前面”的汽车，显然，这和队列的“先进先出”特点相吻合。所以，这里使用一个顺序队列来描述便道，可以利用数组的下标表示便道的位置，具体定义如下：#define MAX_PAVE 100 /便道不限制停放车辆的数目，设为足够大 typedef struct CAR PAVEMAX_PAVE;/各汽车信息的存放空间 int front,rear;/用来指示队头和队尾位置的静态指针 PAVEMENT;(4)当某辆车要离开停车场的时候，比它后进停车位的车要为它让路，而且当它开走之后，让路的车还要按照原来的停放次序再次进入停车位的某个车位上，为了完成这项功能，再定义一个辅助栈，停车位中让路的车依次“压入”辅助栈，待提出请求的车开走后再从辅助栈的栈顶依次“弹出”到停车位中，对辅助栈也采用顺序栈，具体定义与停车位栈类似，如下：typedef struct CAR BUFFERMAX_STOP;/各汽车信息的存储空间 int top;/用来指示栈顶位置的静态指针 BUFFER;16西安交通大学计算机系实验八实验八实验八实验八 停车场模拟管理程序的设计与实现停车场模拟管理程序的设计与实现停车场模拟管理程序的设计与实现停车场模拟管理程序的设计与实现(续续续续)3.3.功能功能(函数函数)设计设计 (1)本程序从总体上分为四个大的功能模块，分别为：程序功能介绍和操作提示模块、汽车进入停车位的管理模块、汽车离开停车位的管理模块、查看停车场停车状态的查询模块。具体功能描述如下：1)程序功能介绍与操作提示模块：此模块给出程序的欢迎信息，介绍本程序的功能，并给出程序功能所对应的键盘操作的提示。函数原形为 void welcome();2)汽车进入停车位的管理模块：此模块用来登记停车场的汽车的车牌号和对该车的调度过程并修改该车的状态，其中调度过程要以屏幕信息的形式反馈给用户来指导用户对车辆的调度。例如，当前停车位上1,2,3车位分别放着牌照为JF001、JF002、JF003的汽车，便道上无汽车，当牌照为JF004的汽车到来后屏幕应给出如下提示信息：牌照为JF004的汽车进入停车位的4号车位！按回车键继续程序的运行。函数原形为 void come();3)汽车离开停车位的管理模块：此模块用来为提出离开停车场的车辆作调度处理，并修改相关车辆的状态。其中调度过程要以屏幕信息的形式反馈给用户来指导用户对车辆的调度。当有车离开停车场后应该立刻检查便道上是否有车，如果有的话立17西安交通大学计算机系实验八实验八实验八实验八 停车场模拟管理程序的设计与实现停车场模拟管理程序的设计与实现停车场模拟管理程序的设计与实现停车场模拟管理程序的设计与实现(续续续续)即让便道上的第一辆汽车进入停车位。例如，当前停车位上1、2、3、4、5车位分别停放着牌照为JF001、JF002、JF003、JF004、JF005的汽车，便道上的1、2位置分别停放着牌照为JF006、JF007的汽车，当接收到JF003要离开的信息时，屏幕应给出如下提示信息：牌照为JF005的汽车暂时退出停车位；牌照为JF004的汽车暂时退出停车位；牌照为JF003的汽车从停车场开走；牌照为JF004的汽车停回停车位的3号车位；牌照为JF005的汽车停回停车位的4号车位；牌照为JF006的汽车从便道上进入停车位的5号车位；按回车键继续程序的运行。函数原形为 void leave();此函数还要调用其他对于栈和队列的基本操作。4)查看停车场停车停车状态的查询模块：此模块用来在屏幕上显示停车位和便道上各位置的状态。例如，当前停车位上1、2、3、4、5车位分别停放着JF001、JF002、JF003、JF004、JF005的汽车，便道上的1、2位置分别停放着牌照为JF006、JF007的汽车，当接收到查看指令后，提示信息如下：18西安交通大学计算机系实验八实验八实验八实验八 停车场模拟管理程序的设计与实现停车场模拟管理程序的设计与实现停车场模拟管理程序的设计与实现停车场模拟管理程序的设计与实现(续续续续)屏幕上应显示：停车位的情况：1车位JF001 2车位JF002 3车位JF003 4车位JF004 5车位JF005 便道上的情况：1位置JF006 2位置JF007 按回车键继续程序的运行。函数原形为 void display();此函数还要调用其他对于栈和队列的基本操作。19西安交通大学计算机系实验八实验八实验八实验八 停车场模拟管理程序的设计与实现停车场模拟管理程序的设计与实现停车场模拟管理程序的设计与实现停车场模拟管理程序的设计与实现(续续续续)(2)以上4个总体功能模块要用到的栈和队列的基本操作所对应的主要函数如下：STOPPING*init_stopping()初始化“停车位栈”BUFFER*init_buff()初始化“辅助栈”PAVEMENT*init_pavement()初始化“便道队列”Int car_come(int pos)将pos指定的汽车信息输入“停车位栈”，并修改该车状态 Int car_leave(int pos)将pos指定的汽车信息从“停车位栈”删除，并修改该车状态 Int stop_to_buff(int pos)将pos指定的汽车信息从“停车位栈”移动到“辅助栈”Int buff_to_stop(int pos)将pos指定的汽车信息从“辅助栈”移动到“停车位栈”Int pave_to_stop(int pos)将pos指定的汽车信息从“便道队列”移动到“停车位栈”Int car_disp(int pos)将pos指定的汽车信息显示在屏幕上3.3.界面设计界面设计 本程序的界面力求简洁、友好，每一步需要对用户的操作进行提示，并且将操作产生的调度结果以中文的形式显示在屏幕上。文字表述精练、准确。函数原形函数功能20西安交通大学计算机系实验九实验九 学生成绩分析学生成绩分析1.1.问题描述问题描述 录入、保存一个班级学生多门课程的成绩，并对成绩进行分析。2.2.基本要求基本要求 (1)通过键盘输入各学生的多门课程的成绩，建立相应的文件input.dat。(2)对文件 input.dat 中的数据进行处理，要求具有如下功能：1)按各门课程成绩排序，并生成相应的文件输出。2)计算每人的平均成绩，按平均成绩排序，并生成文件。3)求出各门课程的平均成绩、最高分、最低分、不及格人数、60-69分人数、70-79分人数、80-89分人数、90分以上人数。4)根据姓名或学号查询某人的各门成绩，重名情况也能处理。21西安交通大学计算机系实验九实验九 学生成绩分析学生成绩分析(续续)测试数据举例：测试数据举例：学号学号姓名姓名数学数学英语英语计算机计算机001王放787790002张强896788003李浩566678004黄鹏兵898685005李浩678876006陈利风455467007尚晓78767022西安交通大学计算机系实验十实验十 一元稀疏多项式计算器一元稀疏多项式计算器1.1.问题描述问题描述 设计一个一元稀疏多项式简单计算器。2.2.基本要求基本要求 一元稀疏多项式简单计算器的基本功能是：(1)输入并建立多项式；(2)输出多项式，输出形式为整数序列：n,c1,e1,c2,e2,cn,en,其中n是多项式的项数，ci,ei分别是第i项的系数和指数，序列按指数降序排列；(3)多项式a和b相加，建立多项式a+b；(4)多项式a和b相减，建立多项式a-b；(5)计算多项式在x处的值；即给定x值，计算多项式值。3.3.实现提示实现提示 用带表头结点的单链表存储多项式，多项式的项数存放在头结点中。23西安交通大学计算机系实验十一、哈夫曼压缩实验十一、哈夫曼压缩实验十一、哈夫曼压缩实验十一、哈夫曼压缩/解压缩算法（编译码器）解压缩算法（编译码器）解压缩算法（编译码器）解压缩算法（编译码器）1 1、问题描述：、问题描述：利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，要求在发送端通过一个编码系统对传输数据预先编码（压缩）；在接收端将传来的数据进行译码（解压缩复原）。试为这样的通信站编写一个哈夫曼编译码系统-哈夫曼压缩/解压缩算法。2 2、基本要求：、基本要求：1）通信内容可以是任意的多媒体文件；2）自己设定字符大小，统计该文件中不同字符的种类（字符集、个数）、出现频率（在该文件中）；3）构建相应的哈夫曼树，并给出个字符的哈夫曼编码；4）对源文件进行哈夫曼压缩编码形成新的压缩后文件（包括哈夫曼树）；5）编写解压缩文件对压缩后文件进行解码还原成源文件。3 3、实现提示：、实现提示：不同源文件形成的压缩文件中应该包含相应的哈夫曼树结构，以便解压缩系统直接译码还原之。参考哈夫曼树一节内容，但要求编写的软件能完整的对任意文件完成压缩/解压缩。24西安交通大学计算机系实验十二、全国交通咨询模拟系统实验十二、全国交通咨询模拟系统实验十二、全国交通咨询模拟系统实验十二、全国交通咨询模拟系统1 1、问题描述：、问题描述：处于不同目的的旅客对交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的时间尽可能地短，出门旅游的游客则期望旅费尽可能省，而老年旅客则要求中转次数最少。编制一个全国城市间的交通咨询程序，为旅客提供两种或三种最优决策的交通咨询。2 2、设计要求设计要求 (1)提供对城市信息进行编辑（如添加或删除）的功能。(2)城市之间有两种交通工具：火车和飞机。提供对列车时刻表和飞机航班进行编辑（增设或删除）的功能。(3)提供两种最优决策：最快到达和最省钱到达。全程只考虑一种交通工具。(4)旅途中耗费的总时间应该包括中转站的等候时间。(5)咨询以用户和计算机的对话方式进行。由用户输入起始站、终点站、最优决策原则和交通工具。输出信息：最快需要多长时间才能到达或者最少需要多少旅费才能到达，并详细说明依次于何时乘坐哪一趟列车或哪一次班机到何地。25西安交通大学计算机系实验十二、全国交通咨询模拟系统实验十二、全国交通咨询模拟系统实验十二、全国交通咨询模拟系统实验十二、全国交通咨询模拟系统3 3、实现提示、实现提示 (1)对全国城市交通图和列车时刻表及飞机航班表进行编辑，应该提供文件形式输入和键盘输入两种方式。飞机航班表的信息应包括：起始站的出发时间、终点站的到达时间和票价；列车时刻表则需根据交通图给出各个路段的详细信息，例如：对从北京到上海的火车，需给出北京至天津、天津至徐州及徐州至上海各段的出发时间、到达时间及票价等信息。(2)以邻接表作交通图的存储结构，表示边的结构内除含有邻接点的信息外，还应包括交通工具、路程中耗费的时间和花费以及出发和到达的时间等多种属性。(3)*可考虑增加旅途中转次数最少的最优决策。26西安交通大学计算机系实验十三、迷宫问题实验十三、迷宫问题实验十三、迷宫问题实验十三、迷宫问题 1 1、问题描述：迷宫实验是取自心理学的一个古典实验。在该实验中，把一只老鼠从一个无顶大盒子的门放入，在盒中设置了许多墙，对行进方向形成了多处阻挡。盒子仅有一个出口，在出口处放置一块奶酪，吸引老鼠在迷宫中寻找道路以到达出口。对同一只老鼠重复进行上述实验，一直到老鼠从入口到出口，而不走错一步。老鼠经多次试验终于得到它学习走迷宫的路线。2、设计功能要求：迷宫由m行n列的二维数组设置，0表示无障碍，1表示有障碍。设入口为（1，1），出口为（m，n），每次只能从一个无障碍单元移到周围四个方向上任一无障碍单元。编程实现对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。算法输入：代表迷宫入口的坐标 算法输出：穿过迷宫的结果。算法要点：创建迷宫，试探法查找路。27西安交通大学计算机系