软件工程数据结构课程设计指导Word文档格式.docx
- 文档编号:8665614
- 上传时间:2023-05-12
- 格式:DOCX
- 页数:29
- 大小:116.49KB
软件工程数据结构课程设计指导Word文档格式.docx
《软件工程数据结构课程设计指导Word文档格式.docx》由会员分享,可在线阅读,更多相关《软件工程数据结构课程设计指导Word文档格式.docx(29页珍藏版)》请在冰点文库上搜索。
3.测试数据。
2、概要设计
Forpersonaluseonlyinstudyandresearch;
notforcommercialuse
包括程序设计组成框图,程序中使用的存储结构设计说明(如果指定存储结构请写出该存储结构的定义)。
3、详细设计
包括模块功能说明(如函数功能、入口及出口参数说明,函数调用关系描述等),每个模块的算法设计说明(可以是描述算法的流程图)。
源程序要按照写程序的规则来编写。
要结构清晰,重点函数的重点变量,重点功能部分要加上清晰的程序注释。
4、调试分析
测试数据,测试输出的结果,时间复杂度分析,和每个模块设计和调试时存在问题的思考(问题是哪些?
问题如何解决?
),算法的改进设想。
5、核心源程序清单和执行结果
附录1数据结构课程设计的具体内容
本次课程设计完成如下模块之一(一组一题)。
1、一元多项式乘法
1)问题描述
已知A(x)=a0+a1x+a2x2+……+anxn和B(x)=b0+b1x+b2x2+……+bmxm,并且在A(x)和B(x)中指数相差很多,求A(x)=A(x)*B(x)。
2)基本要求
(1)设计存储结构表示一元多项式;
(2)设计算法实现一元多项式乘法;
(3)分析算法的时间复杂度和空间复杂度。
2、迷宫问题
1)问题描述
迷宫求解是实验心理学中的一个经典问题,心理学家把一只老鼠从一个无顶盖的大盒子的入口处赶进迷宫,迷宫中设置很多隔壁,对前进方向形成了多处障碍,心理学家在迷宫的唯一出口处放置了一块奶酪,吸引老鼠在迷宫中寻找通路以到达出口。
例如,图2所示为一个迷宫示意图,其中双边矩形表示迷宫,1代表有障碍,0代表无障碍。
1
2
3
4
5
6
7
8
9
(1)设计数据结构存储迷宫;
(2)设计存储结构保存从入口到出口的通路;
(3)设计算法完成迷宫问题的求解;
(4)分析算法的时间复杂度。
3)设计思想
可以采用回溯法实现该问题的求解。
回溯法是一种不断试探及时纠正错误的搜索方法。
从入口出发,按某一方向向前探索,若能走通(未走过的),即某处可以到达,则到达新点,否则试探下一方向;
若所有的方向均没有通路,则沿原路返回前一点,换下一个方向再继续试探,直到所有可能的通路都搜索到,或找到一条通路,或无路可走又返回到入口点。
在求解过程中,为了保证在任何位置上都能沿原路退回,需要一个后进先出的栈来保存从入口到当前位置的路径。
可以将迷宫定义成一个二维数组,则每个点有8个试探方向,如当前点的坐标是(x,y),与其相邻的8个点的坐标都可根据与该点的相邻方位而得到,规定试探顺序为顺时针方向,将这8个方向的坐标增量放在一个结构数组move[8]中,在move数组中,每个元素由两个域组成:
x表示横坐标增量,y表示纵坐标增量。
这样会很方便地求出从某点(x,y)按某一方向v(0≤v≤7)到达新点(i,j)的坐标:
i=x+move[v].x;
j=y+move[v].y。
算法用伪代码描述如下:
1.栈初始化;
2.将入口点坐标(x,y)及该点的方向d(设为-1)入栈;
3.当栈不空时循环执行下述操作:
3.1(x,y,d)<
==栈顶元素出栈;
3.2求出下一个要试探的方向d++;
3.3沿顺时针试探每一个方向,执行下述操作:
3.3.1如果方向d可走,则
将(x,y,d)入栈;
求新点坐标(i,j);
将新点(i,j)切换为当前点(x,y);
若(x,y)是终点,则算法结束;
否则,重置d=0;
3.3.2否则,试探下一个方向d++;
3、抽签游戏
抽签是我们日常生活中经常遇到的一件事,并且其形式有很多种。
这里介绍一种抽签游戏,如图3所示,最上面一排是游戏的参加者——称为抽签者,最下面一排是签号(奖品、公差等)。
每个人依次顺着竖线往下走,当碰到横线时,即转横向前进,碰到竖线再往下,以此类推,则游戏结束后,抽签者会一一对应到最下面一排的签号。
2)基本要求
(1)设计存储结构存储抽签者、签号、游戏用横线、竖线等;
(2)设计算法实现抽签;
(3)存储游戏的最终结果。
3)设计思想
分析上面的抽签游戏的示例,遇到一条横线,代表这两个竖线的数据就要交换顺序,例如,原来的顺序为{A0,A1,A2,A3,A4},经过第0层横线后,顺序为{A1,A0,A3,A2,A4},再经过第1层横线后,顺序为{A1,A3,A0,A2,A4},以此类推,最后顺序为{A4,A1,A0,A2,A3},对应到{p0,p1,p2,p3,p4}。
在该游戏中,需解决以下问题:
(1)抽签游戏可以多人参与,只要加上竖线和横线即可。
那么,如何表示这些参与者呢?
解决:
假设有n个人参加,可以用一个一维数组A[n]来记录n个抽签者。
(2)签号如何存储?
签号的存储也可设计成一个一维数组p[n]来记录n个签号。
(3)如何存储游戏的最终结果?
设计一维数组B[n]存储最终的对应结果,同时在执行过程中记载中间结果。
(4)当碰到某一横线跨在第i条和第i+1条竖线上时,如何交换数据?
用一维数组B[n]来存放游戏过程中的中间结果和最终结果,通过交换B[i]和B[i+1]的值解决交换数据问题。
(5)如何表示抽签游戏的竖线和横线布局?
设计一个二维数组M[m][n],M[i][j]表示第i层上第j条和第j+1条竖线之间是否有横线,其值为0或1,1代表有横线,0代表没有横线。
图3所述示例对应的数组M如图4所示。
算法设计要点如下:
(1)按从上到下、由左到右的方式遍历数组M,若某元素值为1,则进行数据交换。
(2)在数据交换的过程中,用一维数组B来存放游戏过程中的顺序和最终的顺序,即:
如果M[i][j]=1,则B[j]←→B[j+1];
(3)最后B[n]即为所求;
4、信号放大器
天然气经过管道网络从其生产基地输送到消耗地,在传输过程中,其性能的某一个或几个方面可能会有所衰减(例如气压)。
为了保证信号衰减不超过容忍值,应在网络中的合适位置放置放大器以增加信号(例如电压)使其与源端相同。
设计算法确定把信号放大器放在何处,能使所用的放大器数目最少并且保证信号衰减不超过给定的容忍值。
(1)建立模型,设计数据结构;
(2)设计算法完成放大器的放置;
(3)分析算法的时间复杂度。
为了简化问题,假设分布网络是二叉树结构,源端是树的根结点,信号从一个结点流向其孩子结点,树中的每一结点(除了根)表示一个可以用来放置放大器的位置。
图5是一个网络示意图,边上标出的是从父结点到子结点的信号衰减量。
对于网络中任一结点i,设d(i)表示结点i与其父结点间的衰减量,D(i)为从结点i到结点i的子树中任一叶子结点的衰减量的最大值,并有如下递推公式:
在此公式中,要计算某结点的D值,必须先计算其孩子结点的D值,因而必须后序遍历二叉树,当访问一个结点时,计算其D值。
例如,D(B)=max{D(D)+d(D),D(E)}=4,若容忍值为3,则在B点或其祖先的任意一点放置放大器,并不能减少B与其后代的衰减量,必须在D点放置一个放大器或在其孩子结点放置一个或多个放大器。
若在结点D处放置一个放大器,则D(B)=2。
根据上述分析,设计如下存储结构:
structelement
{
intD;
//该结点的衰减量
intd;
//父结点的衰减量
boolboost;
//当且仅当本处设置放大器,则boost为true
};
structBiNode
elementdata;
BiNode*lchild,*rchild;
计算并放置放大器的伪代码为:
1.D(i)=0;
2.for(i的每个孩子j)
2.1如果D(j)+d(j)>
容忍值,则在j处放置放大器;
2.2否则D(i)=max{D(i),D(j)+d(j)};
【思考题】本题假设分布网络是一棵二叉树结构,如果是树结构应如何设计算法?
5、哈夫曼编码
设某编码系统共有n个字符,使用频率分别为{w1,w2,…,wn},设计一个不等长的编码方案,使得该编码系统的空间效率最好。
(1)设计数据结构;
(2)设计编码算法;
(3)分析时间复杂度和空间复杂度。
利用Huffman编码树求得最佳的编码方案。
根据哈夫曼算法,建立哈夫曼树时,可以将哈夫曼树定义为一个结构型的一维数组HuffTree,保存哈夫曼树中各结点的信息,每个结点包括:
权值、左孩子、右孩子、双亲,如图6所示。
由于哈夫曼树中共有2n-1个结点,并且进行n-1次合并操作,所以该数组的长度为2n-1。
构造哈夫曼树的伪代码如下:
1.数组huffTree初始化,所有元素结点的双亲、左右孩子都置为-1;
2.数组huffTree的前n个元素的权值置给定权值w[n];
3.进行n-1次合并
3.1在二叉树集合中选取两个权值最小的根结点,其下标分别为i1,i2;
3.2将二叉树i1、i2合并为一棵新的二叉树k;
在哈夫曼树中,设左分支为0,右分支为1,从根结点出发,遍历整棵哈夫曼树,求得各个叶子结点所表示字符的哈夫曼编码。
【思考题】对于采用哈夫曼编码树进行的编码,如何设计解码算法?
6、TSP问题
所谓TSP问题是指旅行家要旅行n个城市,要求各个城市经历且仅经历一次,并要求所走的路程最短。
该问题又称为货郎担问题、邮递员问题、售货员问题,是图问题中最广为人知的问题。
(1)上网查找TSP问题的应用实例;
(2)分析求TSP问题的全局最优解的时间复杂度;
(3)设计一个求近似解的算法;
对于TSP问题,一种最容易想到的也肯定能得到最佳解的算法是穷举法,即考虑所有可能的旅行路线,从中选择最佳的一条。
但是用穷举法求解TSP问题的时间复杂度为Ο(n!
),当n大到一定程度后是不可解的。
本实验只要求近似解,可以采用贪心法求解:
任意选择某个城市作为出发点,然后前往最近的未访问的城市,直到所有的城市都被访问并且仅被访问一次,最后返回到出发点。
为便于查找离某顶点最近的邻接点,可以采用邻接矩阵存储该图。
1.任意选择某个顶点v作为出发点;
2.执行下述过程,直到所有顶点都被访问:
2.1v=最后一个被访问的顶点;
2.2在顶点v的邻接点中查找距离顶点v最近的未被访问的邻接点j;
2.2访问顶点j;
3.从最后一个访问的顶点直接回到出发点v;
【思考题】上网查找TSP问题的应用实例,写一篇综述报告。
7、医院选址问题
n个村庄之间的交通图可以用有向网图来表示,图中边<
vi,vj>
上的权值表示从村庄i到村庄j的道路长度。
现在要从这n个村庄中选择一个村庄新建一所医院,问这所医院应建在哪个村庄,才能使所有的村庄离医院都比较近?
(1)建立模型,设计存储结构;
(2)设计算法完成问题求解;
医院选址问题实际是求有向图中心点的问题。
首先定义顶点的偏心度。
设图G=(V,E),对任一顶点k,称E(k)=max{d(i,k)}(i∈V)为顶点k的偏心度。
显然,偏心度最小的顶点即为图G的中心点。
如图7(a)所示是一个带权有向图,其各顶点的偏心度如图(b)所示。
医院选址问题的算法用伪代码描述如下:
1.对加权有向图,调用Floyd算法,求每对顶点间最短路径长度的矩阵;
2.对最短路径长度矩阵的每列求大值,即得到各顶点的偏心度;
3.具有最小偏心度的顶点即为所求。
【思考题】图的存储结构和算法的设计需要一定的灵活性和技巧。
从医院选址问题的求解过程,你有什么感想?
8、简单个人电话号码查询系统
人们在日常生活中经常需要查找某个人或某个单位的电话号码,本实验将实现一个简单的个人电话号码查询系统,根据用户输入的信息(例如姓名等)进行快速查询。
(1)在外存上,用文件保存电话号码信息;
(2)在内存中,设计数据结构存储电话号码信息;
(3)提供查询功能:
根据姓名实现快速查询;
(4)提供其他维护功能:
例如插入、删除、修改等;
(5)按电话号码进行排序。
由于需要管理的电话号码信息较多,而且要在程序运行结束后仍然保存电话号码信息,所以电话号码信息采用文件的形式存放到外存中。
在系统运行时,需要将电话号码信息从文件调入内存来进行查找等操作,为了接收文件中的内容,要有一个数据结构与之对应,可以设计如下结构类型的数组来接收数据:
constintmax=10;
structTeleNumber
stringname;
//姓名
stringphoneNumber;
//固定电话号码
stringmobileNumber;
//移动电话号码
stringemail;
//电子邮箱
}Tele[max];
为了实现对电话号码的快速查询,可以将上述结构数组排序,以便应用折半查找,但是,在数组中实现插入和删除操作的代价较高。
如果记录需频繁进行插入或删除操作,可以考虑采用二叉排序树组织电话号码信息,则查找和维护都能获得较高的时间性能。
更复杂地,需要考虑该二叉排序树是否平衡,如何使之达到平衡。
9、各种排序算法时间性能的比较
对各种排序方法(直接插入排序、希尔排序、起泡排序、快速排序、直接选择排序、堆排序和归并排序)的时间性能进行比较。
(1)设计并实现上述各种排序算法;
(2)产生正序和逆序的初始排列分别调用上述排序算法,并比较时间性能;
(3)产生随机的初始排列分别调用上述排序算法,并比较时间性能。
上述各种排序方法都是基于比较的内排序,其时间主要消耗在排序过程中进行的记录的比较次数和移动次数,因此,统计在相同数据状态下不同排序算法的比较次数和移动次数,即可实现比较各种排序算法的目的。
直接插入排序、起泡排序、直接选择排序在教材中已经实现,请仿照教材中的方法在其他排序算法中的适当位置插入计数器统计元素的比较次数和移动次数。
【思考题】如果测算每种排序算法所用实际的时间,应如何修改排序算法?
10、机器调度问题
机器调度是指有m台机器需要处理n个作业,设作业i的处理时间为ti,则对n个作业进行机器分配,使得:
(1)一台机器在同一时间内只能处理一个作业;
(2)一个作业不能同时在两台机器上处理;
(3)作业i一旦运行,则需要ti个连续时间单位。
设计算法进行合理调度,使得在m台机器上处理n个作业所需要的处理时间最短。
(1)建立问题模型,设计数据结构;
(2)设计调度算法,为每个作业分配一台可用机器;
(3)给出分配方案。
假设有七个作业,所需时间分别为{2,14,4,16,6,5,3},有三台机器,编号分别为m1、m2和m3。
这七个作业在三台机器上进行调度的情形如图9所示,阴影区代表作业的运行区间。
作业4在0到16时间被调度到机器1上运行,在这16个时间单位中,机器1完成了对作业4的处理;
作业2在0到14时间被调度到机器2上处理,之后机器2在14到17时间处理作业7;
在机器3上,作业5在0~6时间完成,作业6在6~11时间完成,作业3在11~15时间完成,作业1在15~17时间完成。
注意到作业i只能在一台机器上从si时刻到si+ti时间完成且任何机器在同一时刻仅能处理一个作业,因此最短调度长度为17。
在上述处理中,采用了最长时间优先(LPT)的简单调度策略。
在LPT算法中,作业按其所需时间的递减顺序排列,在分配一个作业时,将其分配给最先变为空闲的机器。
下面设计完成LPT算法的存储结构。
·
为每个机器设计数据类型:
structMachineNode
intID;
//机器号
intavail;
//机器可用时刻
·
为每个作业设计数据类型:
structJobNode
//作业号
inttime;
//处理时间
LPT算法用伪代码描述如下:
1.如果作业数n≤机器数m,则
1.1将作业i分配到机器i上;
1.2最短调度长度等于n个作业中处理时间最大值;
2.否则,重复执行以下操作,直到n个作业都被分配:
2.1将n个作业按处理时间建成一个大根堆H1;
2.2将m个机器按可用时刻建立一个小根堆H2;
2.3将堆H1的堆顶作业分配给堆H2的堆顶机器;
2.4将H2的堆顶机器加上H1的堆顶作业的处理时间重新插入h2中;
2.5将堆H1的堆顶元素删除;
3.堆H2的堆顶元素就是最短调度时间;
11、运动会分数统计
参加运动会有n个学校,学校编号为1……n。
比赛分成m个男子项目,和w个女子项目。
项目编号为男子1……m,女子m+1……m+w。
不同的项目取前五名或前三名积分;
取前五名的积分分别为:
7、5、3、2、1,前三名的积分分别为:
5、3、2;
哪些取前五名或前三名由学生自己设定。
(m<
=20,n<
=20)
(1)可以输入各个项目的前三名或前五名的成绩;
(2)能统计各学校总分,
(3)可以按学校编号、学校总分、男女团体总分排序输出;
(4)可以按学校编号查询学校某个项目的情况;
可以按项目编号查询取得前三或前五名的学校。
规定:
输入数据形式和范围:
20以内的整数(如果做得更好可以输入学校的名称,运动项目的名称)
输出形式:
有中文提示,各学校分数为整型
界面要求:
有合理的提示,每个功能可以设立菜单,根据提示,可以完成相关的功能要求。
存储结构:
学生自己根据系统功能要求自己设计,但是要求运动会的相关数据要存储在数据文件中。
(数据文件的数据读写方法等相关内容在c语言程序设计的书上,请自学解决)请在最后的上交资料中指明你用到的存储结构;
测试数据:
要求使用1、全部合法数据;
2、整体非法数据;
3、局部非法数据。
进行程序测试,以保证程序的稳定。
测试数据及测试结果请在上交的资料中写明;
12、订票系统
通过此系统可以实现如下功能:
(1)录入:
可以录入航班情况(数据可以存储在一个数据文件中,数据结构、具体数据自定)
(2)查询:
可以查询某个航线的情况(如,输入航班号,查询起降时间,起飞抵达城市,航班票价,票价折扣,确定航班是否满仓);
可以输入起飞抵达城市,查询飞机航班情况;
(3)订票:
(订票情况可以存在一个数据文件中,结构自己设定)
可以订票,如果该航班已经无票,可以提供相关可选择航班;
(4)退票:
可退票,退票后修改相关数据文件;
客户资料有姓名,证件号,订票数量及航班情况,订单要有编号。
(5)修改航班信息:
当航班信息改变可以修改航班数据文件
根据以上功能说明,设计航班信息,订票信息的存储结构,设计程序完成功能。
13、文章编辑
输入一页文字,程序可以统计出文字、数字、空格的个数。
静态存储一页文章,每行最多不超过80个字符,共N行;
要求
(1)分别统计出其中英文字母数和空格数及整篇文章总字数;
(2)统计某一字符串在文章中出现的次数,并输出该次数;
(3)删除某一子串,并将后面的字符前移。
存储结构使用线性表,分别用几个子函数实现相应的功能;
输入数据的形式和范围:
可以输入大写、小写的英文字母、任何数字及标点符号。
输出形式:
(1)分行输出用户输入的各行字符;
(2)分4行输出"
全部字母数"
、"
数字个数"
空格个数"
文章总字数"
(3)输出删除某一字符串后的文章;
14、停车场管理
设停车场内只有一个可停放n辆汽车的狭长通道,且只有一个大门可供汽车进出。
汽车在停车场内按车辆到达时间的先后顺序,依次由北向南排列(大门在最南端,最先到达的第一辆车停放在车场的最北端),若
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 软件工程 数据结构 课程设计 指导