08092数据结构课程设计任务书网络07级

1、数据结构课程设计任务书使用班级：网络 0701，0702，0703， 0704使用学期： 2008-2009 学年第二学期指导老师：林芳、蒋建辉、肖琳2009 年 6 月 1 日数据结构课程设计任务书一、 设计目的算法与数据结构是计算机专业的核心课程，是一门实践性很强的课程。为了学好这门课程，必须 在掌握理论知识的同时，加强上机实践。课程设计是加强学生实践能力的一个强有力手段，要求学生掌握 数据结构的应用、算法的编写、将算法转换成程序并上机调试的基本方法，还要求学生在完成程序设计的 同时能够写出比较规范的设计报告。本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够 根据数据对象的特性

2、，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养 学生的基本程序设计素养和软件工作者工作作风。二、 设计内容题目1:基本线性表的就地逆置在基本线性表原有空间的基础上，将线性表中的数据元素逆置，使新的顺序序列与原来的顺序序列 刚好相反。如原来顺序序列abcdef”，逆置之后的新顺序序列为 fedcba”。要求：数据结构可以选择顺序结构或链式结构；操作过程必须在线性表的原有空间，不能借助临时变量所申请的临时空间，也不能借助其他形式的临时空间。题目2 :火车票销售编制一个简单的火车票销售系统，可完成售票、退票、车票剩余情况查询等功能。每张车票包含车次、 座位信息。要求：在售

3、票、退票、车票剩余情况查询等环节中，都必须显示出车票的具体信息（车次、座位信息） 退票时，必须是车站售出的票才能退。题目3 :简单编译器的实现将中缀表达式转换为后缀表达式。假设输入的算法表达式的运算符只有“ +、X、/、（、）”这几种。要求：用栈完成；首先要判断输入的表达式括号是否配对，在正确表达式的基础上转换为后缀表达式。题目4:商品货架管理商店货架以栈的方式摆放商品。商品货架可以看成一个栈，栈顶商品的生产日期最早，栈底商品的 生产日期最近。生产日期越接近的越靠栈底，出货时从栈顶取货。一天营业结束，如果货架不满，则需上 货。入货直接将商品摆放到货架上，则会使生产日期越近的商品越靠近栈顶。这样

4、就需要倒货架，使生产 日期越近的越靠近栈底。请编写程序模拟商品销售，上架操作。（设有5种商品，每种商品至少有商品名和生产日期两个属性）题目5 :模拟停车场管理的问题设停车场只有一个可停放几辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场按车 辆到来的先后顺序依次排列，若车场内已停满几辆汽车，则后来的汽车只能在门外的便道上等候，一旦停 车场内有车开走，则排在便道上的第一辆车即可进入；当停车场内某辆车要离开时，由于停车场是狭长的 通道，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门后，为它让路的车辆在按原次序 进入车场。每辆停放在车场的车在它离开停车场时必须按它停留的时间长短

5、交纳费用。试为停车场编制按 上述要求进行管理的模拟程序。在这里假设汽车不能从便道上开走。试设计一个停车场管理程序。实现提示：以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，例如：（A,1,5）表示一号牌照车爱 5这个时刻到达，而（D,5,20）表示5号牌照车在20这个时刻离去，整个程序 可以在输入信息为（E,0,0）时结束。对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽 车在停车场内或便道上的停车位置；若是车离去；则输出汽车在停车场内停留的时间和应交纳的费

6、用（在 便道上停留的时间不收费）。栈以顺序结构实现，队列以链表实现。需另设一个栈，临时停放为给要离去 的汽车让路而从停车场退出来的汽车，题目6 :哈夫曼编码和译码利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编 /译码系统。试为这样的信息收发站写一个哈夫曼编/译码系统。基本要求：一个完整的系统应具有以下功能：（1）初始化（Initialization ）。从终端读入字符集大小 n ,以及n个字符和n个权值

7、，建立哈夫曼树，（选 做：并将它存于文件 hfmTree 中）。并显示出每个字符的编码。（2） 编码（Encoding）。利用已建好的哈夫曼树（选做：如不在内存，则从文件htmTree中读入），对 输入的字符串文本（选做：对文件 ToBeTran 中的正文）进行编码， （选做：然后将结果存入文件 CodeFile 中。）并显示在屏幕上。（3）译码（Decoding）。利用已建好的哈夫曼树将输入的代码进行译码（选做：将文件CodeFile中的代码进行译码，结果存入文件TextFile中。），并显示在屏幕上。（4）打印哈夫曼树（Tree Printing）。将已在内存中的哈夫曼树以直观的方式显示在

8、屏幕上。题目 7：校园导游程序 设计一个校园导游程序为来访的客人提供各种信息查询服务。基本要求：（1） ）设计学校的旗山校区北区校园平面图，所含场所不少于10 个。以图中顶点表示校内各场所，存放场所名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。（ 2）为来访客人提供图中任意场所相关信息的查询。（ 3）为来访客人提供图中任意场所的问路查询，即查询任意两个景点之间的一条最短的简单路径。题目 8：内部排序算法比较 各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。试通过随 机的数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。基本要求：（1）

9、从以下常用的内部排序算法至少选取 5 种进行比较：直接插入排序；折半折入排序；希尔排序； 起泡排序；快速排序；简单选择排序；堆排序；归并排序。（2） 待排序表的表长为 20000；其中的数据要用伪随机数产生程序产生；至少要用5 组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字移动次数（关键字交换计为3次移动）。题目 9：哈希表设计针对同班同学信息设计一个通讯录，学生信息有姓名，学号，电话号码等。以学生姓名为关键字设计 哈希表，并完成相应的建表和查表程序。基本要求：姓名以汉语拼音形式，待填入哈希表的人名约30 个，自行设计哈希函数，用线性探测再散列法或链地址法处理冲突；在查找的

10、过程中给出比较的次数。完成按姓名查询的操作。题目 10：平衡二叉树 二叉排序树的查找效率取决于二叉树的形态，而二叉排序树的形态与生成树时结点的插入次序有关， 而结点的插入次序往往不能预先确定，这就需要在生成二叉排序树的过程中进行动态调整，以构造形态匀 称的平衡二叉树。设计实现按输入的序列构造平衡二叉树。要求：对构造好的平衡二叉树进行先序和中序遍历；或者图示平衡二叉树的形态。三、设计要求1、 每人至少选择一题完成，每道题每个班选择人数不能超过5 人。2、独立思考，独立完成：课程设计中各任务的设计和调试要求独立完成，遇到问题可以讨论，但不可以 拷贝，不允许雷同。3、在处理每个题目时，要求从分析题目

11、的需求入手，按设计抽象数据类型、构思算法、通过类的设计实 现抽象数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。前期准备工 作完备与否直接影响到后序上机调试工作的效率。在程序设计阶段应尽量利用已有的标准函数，加大代码 的重用率。4、设计出的系统要有一个易于使用人机界面。5、源程序中应对重要程序写出注释语句四、 应提交的作品1.设计报告（电子稿） ，文档书写格式可参看附录。2.源程序。五、 提交方式及要求 每个人以自己的“学号姓名”形式建立文件夹，每个人的文档及源程序存放在自己的文件夹内。 答辩时拷贝给指导教师检查、答辩。答辩结束后拷给学习委员，学习委员将全班的设计报

12、告和程序收集齐后交给指导教师。六、 时间安排第20周的星期一至星期五。时间内容星期一选定题目：明确题目要求、确定数据结构、算法描述， 准备测试数据等星期二至星期四上午完成要求问题并测试、归档星期四下午、星期五演示回答教师提问文档及程序的整理并提交作品课程设计期间不迟到， 不早退，有特殊情况要事先请假，并经有关老师批准方能有效，无故缺席者作旷 课处理。进入机房，应遵守机房规定的各项制度。附录课程设计课程：_题目_专业：_班级：_座 号：_姓名：_(x+1,y)00111r 121031-140r -15-1-16-107-11实验题目：求迷宫的最短路径一、要解决的问题这是实验心理学中的一个经典问

13、题，心理学家把一只老鼠从一个无顶盖的大盒子的入口 处赶进迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫的唯一出 口处放置了一块奶酪，吸引老鼠在迷宫中寻找通路以达到出口。我们要解决的是如何找到了 一条迷宫的最短路径。二、算法基本思想描述：要用到回溯的思想。从迷宫入口点出发，向四周搜索，记下所有一步能到达的坐标点； 然后依次从这些点出发，再记下所有一步能到达的坐标点，.依此类推，直到到达迷宫的出口点为止，然后从迷宫出口点沿搜索路径回溯。这样就找到了一条迷宫的最短路径，否则 迷宫无路径。由于先到达的点先搜索，故用先进先出的数据结构一一队列来保存已到达的坐标点。三、设计1.数据结构

14、的设计（1）迷宫的表示设迷宫为m行n列，利用mazemn来表示迷宫，mazemn=0或1，其中0表示通路，1 表示不通。入口坐标（1， 1），出口坐标（m,n）.迷宫定义如下：#defi ne m 6#defi ne n 8int mazem+2n+2；2）试探方向的表示在迷宫中有8个方向可以试探，规定：从当前位置向前试探的方向为从正东开始沿顺时针 方向进行。为了简化问题，将这 8个方向的坐标增量放在一个结构数组 move8中。在move 数组中，每个元素有两个域组成，X：横坐标增量；Y:纵坐标增量。Move数组定义如下：typedef structint x,y;item;item move

15、8= 0,1,1,1, 1,0, 1,-1,0,-1, -1,-1,-1,0,-1,1 ;（3）队列的表示在找到出口点之后，需要沿搜索路径回溯，所以到达某点时，不仅要记下该点的坐标，还要记下该点的前驱。用一个结构数组sqnum作为队列的存储空间。Sq的每一个结构有三个域：x,y,pre,其中x，y分别为所到达的点的坐标，pre为前驱点的坐标。还设队头front 和队尾rear指针。(x+1,y+1)序号 X Y12345 678111111121沢1恪1031吊、11114111k;1151A160*111 0：111k03)（3，1 )、1（2， 丄4 )（4，11 )（1，5 )（5，2

16、)（2，6 )( 5，3 )1（&6，4 )#defi ne num 50 typedef structint x,y; int pre;SqType;SqType sqnum； int front, rear；2.算法的设计（1）求最短路径的算法设计初始状态，队列中只有一个元素 sq1,记录的是入口点的坐标（1, 1）,因为该点是出发 点，因此没有直接前驱点，pre域为-1,队头指针front的队尾指针rear均指向它，此后搜索 时都是以front所指点为搜索的出发点，即将该点的坐标及front所指点的位置入队，这样不但记下了到达点的坐标，还记下了它的前驱点。Front所指向点的8个方向搜索

17、完毕后，则出队，继续对下一点搜索。搜索过程中遇到出口点则成功，搜索结束，打印出迷宫的最短路径， 算法结束；或者当前队空，既没有搜索点了，表明没有路径，算法也结束。（2）防止重复到达某点的考虑为避免发生死循环，当到达某点（i, j）后，使mazeij置-1，以便区分未到达过的顶点 算法结束前可恢复原迷宫。（3）队列头、尾指针的指向队头指针指向搜索的出发点，当找到一个可到达点，就入队；当8个方位都搜索完毕,队头指针往后移一个（出队，但原位置值依然存在，方便最后回溯）。（4）模块结构及功能：(3 ,4 )(4 ,5 )6 ) ( 5 ,6 )7 ) ( 6 ,5 )(11)4 ,(2 , 2 )/

18、迷宫的初始化/ 队列的初始化/ 求迷宫的最短路径/ 打印路径b) viod init_maze(int)c) void init_queue(SqType)d) int path(int,int)e) void print_path(SqType,rear)f) void in_queue(SqType ,datatype) / 入队操作g) void out_queue(SqType)/ 出队操作h) int empty_queue(SqType)/ 判队空5)主要模块算法描述求迷宫最短路径的算法描述：path(int maze,int move) 队列头、尾指针初始化(=-1); 将入口点的前驱设置为 -1，入队； 将入口点设置为已走过；将是否找到出口点信息 found 赋值为 0(未找到)； while (未找到 &队列非空) 队头指针后移指向当前搜索点，并将它赋值给x；for i=1 to 8搜索x点的8个方向if (找到一个可走点)就将该点坐标及前驱值(front)入队; 将该点设置为已走过；if (该点是出口点)found=1;if(找到)回溯打印最短路径；else 打印 “该迷宫没有路径 ”;四、源程序清单：(略)五、测试数据及测试结果：例如：测试数据： mazem+2n+2=1,1,1,1,1,