数据结构课程设计基础任务书网络

数据结构课程设计任务书

使用班级：网络0701,0702,0703,0704

使用学期：-第二学期

指导老师：

6月1日

数据结构课程设计任务书

一、设计目

《算法与数据结构》是计算机专业关键课程，是一门实践性很强课程。为了学好这门课程，必需在掌握

理论知识同时，加强上机实践。课程设计是加强学生实践能力一个强有力手段，要求学生掌握数据结构应

用、算法编写、将算法转换成程序并上机调试基础方法，还要求学生在完成程序设计同时能够写出比较

规范设计汇报。本课程设计目就是要达成理论与实际应用相结合，使同学们能够依据数据对象特征，学会

数据组织方法，能把现实世界中实际问题在计算机内部表示出犬，并培养学生基础程序设计素养和软件工

作者工作作风。

二、设计内容

题目1:基础线性表就地逆置

在基础线性表原有空间基础上，将线性表中数据元素逆置，使新次序序列与原来次序序列刚好相反。

如原来次序序列“abcdef”，逆置以后新次序序列为“fedcba”。

要求：数据结构能够选择次序结构或链式结构；操作过程必需在线性表原有空间，不能借助临时变最所

申请临时空间，也不能借助其她形式临时空间。

题目2:火车票销售

编制一个简单火车票销售系统，可完成售票、退票、车票剩下情况查询等功效。每张车票包含车次、

座位信息。

要求：在售票，退票，年票剩下情况杳询等步骤中，都必需显示出年票只体信息.（年次，座位信息）；

退票时，必需是车站售出票才能退。

题目3:简单编译器实现

将中缀表示式转换为后缀表示式。假设输入算法表示式运算符只有“十、一、X、/、（、）”这

多个。

要求：用栈完成；首先要判定输入表示式括号是否配对，在正确表示式基础上转换为后缀表示式。

题目4:商品货架管理

商店货架以栈方法摆放商品。商品货架能够看成一个栈，栈顶商品生产口期最早，栈底商品生产口期

最近。生产日期越靠近越靠枝底，出货时从栈顶取货。・天营业结束，假如货架不满，则需上货。入货直接

将商品摆放到货架匕则会使生产日期越近商品越靠近栈顶。这么就需要倒货架，使生产日期越近越靠近

栈底。请编写程序模拟商品销售，上架操作。（设有5种商品，每种商品最少有商品名和生产日期两个属性）

题目5:模拟停车场管理问题

设停车场只有一个可停放几辆汽车狭长通道，且只有一个大门可供汽车进出。汽车在停车场按车辆到

来前后次序依次排列，若车场内已停满几辆汽车，则以后汽车只能在门外便道上等候，一旦停车场内有车

开走，则排在便道上第一辆车即可进入；当停车场内某辆车要离开时，因为停车场是狭长通道，在它以后

开入车辆必需先退出车场为它让路，待该辆车开出大门后，为它让路车辆在按原次序进入车场。每辆停放

在车场车在它离开停车场时必需按它停留时间长短交纳费用。试为停车场编制按上述要求进行管理模拟程

序,在这里假设汽车不能从便道上开走。试设计一个停车场管理程序。

实现提醒：以栈模拟停车场，以队列模拟车场外便道，根据从终端读入输入数据序列进行模拟管理。每

一组输入数据包含三个数据项：汽车“抵达”或“离去”信息、汽车牌照号码及抵达或离去时刻，比如:

（AJ5）表示一号牌照车爱5这个时刻抵达，而CD520）表示5号牌照车在20这个时刻离去，整个程序能够

在输入信息为（E,0,0）时结束。对每一组输入数据进行操作后输出数据为：若是车辆抵达，则输出汽车在停

车场内或便道上停车位置；若是车离去；则输出汽车在停车场内停留时间和应交纳费用（在便道上停留时

间不收费）。栈以次序结构实现，队列以链表实现。需另设一个栈，临时停放为给要离去汽车让路而从停车

场退出来汽车，

题目6:哈夫曼编码和译码

利用哈夫曼编码进行信息通信能够大大提升信道利用率，缩短信息传输时间，降低传输成本。不过，这

要求在发送端经过一个编码系统对待传数据预先编码，在接收端将传来数据进行译码（复原）。对于双工信

道（即能够双向传输信息信道），每端都需要一个完整编/译码系统。试为这么信息收发站写一个哈夫曼编

/译码系统。

基础要求:一个完整系统应含有以下功效：

（1）初始化（Initialization）。从终端读入字符集大小n,以及n个字符和n个权值，建立哈夫曼树，（选

做：并将它存于文件hfmTree中）。并显示出每个字符编码。

（2）编码（Encoding）o利用已建好哈夫曼树（选做：如不在内存，则从文件htmTree中读入），对输入

字符串文本（选做：对文件ToBeTran中正文）进行编码，（选做：然后将结果存入文件CodeFile中。）并

显示在屏幕上。

（3）译码（Decoding）o利用已建好哈夫曼树将输入代码进行译码（选做：将文件CodeFile中代码进行

译谓，结果存入文件TextFile中。），并显示在屏幕上。

（4）打印哈夫曼树（TreePrinting）。将已在内存中哈夫曼树以直观方法显示在屏幕上。

题目7:校园导游程序

设计一个校园导游程序为来访客人提供多种信息查询服务。

基础要求：

（1））设计学校旗山校区北区校园平面图，所含场所不少于10个。以图中顶点表示校内各场所，存放场

所名称、代号、介绍等信息；以边表示路径，存放路径长度等相关信息。

（2）为来访客人提供图中任意场所相关信息查询。

（3）为来访客人提供图中任意场所问路杳询，即杳询任意两个景点之间一条最短简单路径。

题目8:内部排序算法比较

多种内部排序算法时间复杂度分析结果只给出了算法实施时间阶，或大约实施时间。试经过随机数据

比较各算法关键字比较次数和关键字移动次数，以取得直观感受。

基础要求：

（1）从以下常见内部排序算法最少选择5种进行比较：宜接插入排序；折半折入排序；希尔排序；起

泡排序；快速排序；简单选择排序；堆排序；归并排序。

（2）待排序表表长为0;其中数据要用伪随机数产生程序产生；最少要用5组不一样输入数据作比较;

比较指标为相关键字参与比较次数和关键字移动次数（关键字交换计为3次移动）。

题目9:哈希表设计

针对同班同学信息设计一个通讯录，学生信息有姓名，学号，电话号码等。以学生姓名为关键字设计哈

希表，并完成对应建表和查表程序。

基础要求：姓名以汉语拼音形式，待填入哈希表人名约30个，自行设计哈希函数，用线性探测再散列

法或链地址法处理冲突；在查找过程中给出比较次数。完成按姓名查询操作。

题目10:平衡二叉树

二叉排序树查找效率取决于二叉树形态，而二叉排序树形杰与生成树时结点插入次序相关，而结点插

入次序往往不能预先确定，这就需要在生成二叉排序树过程中进行动态调整，以结构形态匀称平衡二叉

树,设计实现按输入序列结构平衡二叉树。

要求：对结构好平衡二叉树进行先序和中序遍历；或者图示平衡二叉树形态。

三、设计要求

1、每人最少选择一题完成，每道题每个班选择人数不能超出5人。

2、独立思索，独立完成：课程设计中各任务设计和调试要求独立完成，碰到问题能够讨论，但不能够拷贝,

不许可雷同。

3、在处理每个题目时，要求从分析题目需求入手，按设计抽象数据类型、构思算法、经过类设计实现

抽象数据类型、编制上机程序和上机调试等若干步骤完成题目、最终写出完整分析汇报。前期准备工作完

备是否直接影响到后序上机调试工作效率。在程序设计阶段应尽可能利用已经有标准函数，加大代码重用

率，

4、设计出系统要有一个易于使用人机界面。

5、源程序中应对关键程序写出注释语句

四、应提交作品

1.设计汇报（电子稿），文档书写格式可参看附录。

2.源程序。

五、提交方法及要求

每个人以自己“学号姓名”形式建立文件夹，每个人文档及源程序存放在自己文件夹内。

答辩时拷贝给指导老师检验、答辩。

答辩结束后拷给学习委员，学习委员将全班设计汇报和程序搜集齐后交给指导老师。

六、时间安排

第20周星期一至星期五。

时间内容

星期一选定题目：明确题目要求、确定数据结构、算法描

述，准备测试数据等

星期二至星期四早晨完成要求问题并测试、归档

星期四下午、星期五演示回复老师提问文档及程序整理并提交作品

课程设计期间不迟到，不早退，有特殊情况要事先请假，并经相关老师同意方能有效，无故缺席者作旷

课处理。

进入机房，应遵守机房要求各项制度。

〈附录》

课程设计

课程：____________________

题目：____________________

专业：____________________

班级：____________________

座号：____________________

姓名：____________________

年月日

试验题目：求迷宫最短路径

一、要处理问题

这是试验心理学中一个经典问题，心理学家把一只老鼠从一个无顶盖大盒子入口处赶进

迷宫。迷宫中设置很多隔壁，对前进方向形成了多处障碍，心理学家在迷宫唯一出口处放置了

块奶酪，吸引老鼠在迷宫中寻求通路以达成出口。我们耍处理是怎样找到了条迷宫最短

路径。

二、算法基础思想描述：

要用到回溯思想。从迷宫入口点出发，向四面搜索，记下全部一步能抵达坐标点；然后依

次从这些点出发，再记下全部一步能抵达坐标点，依这类推，直到抵达迷宫出口点为止,

然后从迷宫出口点沿搜索路径回溯。这么就找到了一条迷宫最短路径，不然迷宫无路径。因

为先抵达点先搜索，故用优异先出数据结构——队列来保留已抵达坐标点。

三、设计

1.数据结构设计

(1)迷宫表示

设迷宫为m行n列,利用maze[m][n]来表示迷宫，maze[m为n]=0或1,其中0表示通路，1

表示不通。入口坐标(1,1),出口坐标(m,n).

迷宫定义以下：

#definem6

#definen8

intmaze[m+2][n+2];

(2)试探方向表示

在迷宫中有8个方向能够试探，要求：从目前位置向前试探方向为从正东开始沿顺时针方

向进行。为了简化问题，将这8个方向坐标增量放在一个结构数组move[8]中。在move数组

中，每个元素有两个域组成，X:横坐标增量；

Y:纵坐标增量。

序号XY

1

1

Move数组定义以下：

typedefstruct

(intx,y;}item;

itemmove[8]={{0,1},{1,1},{1,0},{1,-1},{0,-1},

{-1,-1},{-1,0},{-1,1});

(3)队列表示

在找到出口点以后，需要沿搜索路径回溯，所以抵达某点时，不仅要记下该点坐标,

还要记下该点前驱。用一个结构数组sq[num]作为队列存放空间。Sq每一个结构有三个域:

x,y,pre,其中x,y分别为所抵达点坐标，pre为前驱点坐标。还设队头front和队尾rear

指针。

#definenum50

typedefstruct

(intx,y;

intpre;

)SqType;

SqTypesq[num];

intfront,rear;

2.算法设计

(1)求最短路径算法设计

(1,1)

12345678

C5,7)(6,5)

(5,8)(6,8)

初始状态，队列中只有一个元素sq[l],统计是入口点坐标（1,1）,因为该点是出发点,

所以没有直接前驱点，pro域为-1,队头指针front队尾指针rear均指向它，以后搜索时都

是以front所指点为搜索出发点，立即该点坐标及front所指点位置入队，这么不仅记下了

抵达点坐标，还记下了它前驱点。Front所指向点8个方向搜索完成后，则出队，继续对下

一点搜索。搜索过程中碰到出口点则成功，搜索结束，打印出迷宫最短路径，算法结束；或

者目前队空，既没有搜索点了，表明没有路径，算法也结束。

（2）预防反复抵达某点考虑

为避免发生死循环，当抵达某点（i,j）后，使置T,方便区分未抵达过顶

点。算法结束前可恢复原迷宫。

（3）队列头、尾指针指向

队头指针指向搜索出发点，当找到一个可抵达点，就入队；当8个方位都搜索完成，队

头指针往后移一个（出队，但原位置值仍然存在，方便最终回溯）。

（4）模块结构及功效：

入队出队判队空

b)viodinit_maze(int)〃迷宫初始化

c)voidinit_queue(SqType)〃队列初始化

d)intpath(int,int)〃求迷宫最短路径

e)voidprint_path(SqType,rear)〃打印路径

f)voidin_queue(SqType,datatype)〃入队操作

g）voidout_queue（SqType）〃出队操作

h）intemptyqueue（SqType）〃判队空

（5）关键模块算法描述

求迷宫最短路径算法描述：

path(intmaze,intmove)

①队列头、尾指针初始化（=-1）;

②将入口点前驱设置为T,入队;

③将入口点设置为己走过；

④将是否找到出口点信息found赋值为0（未找到）；

⑤while（未找