数据结构课程设计

摘要。数据结构”是有关计算技术及信息管理技术专业的一门必修的核心课程。数据结构课程的任务实在讨论在应用问题求解时数据的逻辑组织、在计算机中的存储实现以及相关操作的算法设计。数据结构课程目的是使学生掌握在实际问题解决过程中组织数据、存储数据和处理数据的基本方法，为以后从事软件开发和应用，为进一步学习后续课程打下坚实的基础。

本文第一个问题是针对随着现代网络的高速发展，从成本角度出发，要求所假设的光缆长度最短，故而采用最小生成树来建模此问题。本文给出了一个城市间光缆假设的场景，采用prim算法、kruskal算法两种算法解决该城市间光缆假设问题，并通过实验**分别实现这两种算法，得到了城市联络网建设的最佳解决方案。

本文第二个问题是根据本学期对数据结构中线性表的学习，编写了一个程序，完成线性表的插入，删除，和查找功能。

关键词：最小生成树；prim算法；kruskal算法；线性表。

目录。1.最小生成树解决城市联络网建设问题 1

1.1问题描述 1

1.2问题分析 1

1.3算法分析 2

1.4算法实现及结果分析 5

2.线性表的插入删除查找程序 7

2.1问题描述 7

2.2问题分析 7

2.3算法分析 8

2.4运行结果 9

总结 10参考文献 11

附录源程序** 12

假设要在个城市之间建立通信联络网，其中顶点表示城市，边表示城市之间是否有通路，边上的权值表示在两者间建立通信链路的花费，要求使得任意两市之间都有通信链路，并且使得总的建设费用最少。

显然，我们会想到连通个城市只需要条线路，在每两个城市之间都可以设置一条线路，相应地都要付出一定的经济代价。个城市之间，最多可以设置条线路，那么，如何在这些可能的线路中选择条，使得总的耗费最少呢？

根据所学的知识，我们知道可以通过寻找最小生成树来解决这个问题。下面我们以图1为例，运用普利姆算法以及克鲁斯卡尔算法来解决城市间通信网建立问题。

图1在一个具有几个顶点的连通图中，如果存在子图包含中所有顶点和一部分边，且不形成回路，则称为图的生成树，代价最小生成树则称为最小生成树。

最小生成树有个重要的性质mst性质（最小生成树性质）：设是一个连通网络，是顶点集的一个真子集。若是中一条“一个端点在中(例如：

)，另一个端点不在中的边，且具有最小权值，则一定存在的一棵最小生成树包括此边。多数算法利用这个性质来求解最小生成树，本文用到的普里姆算法和克鲁斯卡尔算法均利用了这个性质，同时它们也属于贪心算法。

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。

本文中的城市通信网建设问题要求使得任意两市之间都有通信链路，并且使得总的建设费用最少，故而适合用贪心算法求解。

1）prim 算法

假设是图中顶点的集合，为最小生成树中的边的集合，则算法通过以下步骤可以得到最小生成树：

1:初始化： ,此步骤设立一个只有结点的结点集和一个空的边集作为最小生成树的初始形态，在随后的算法执行中，这个形态会不断的发生变化，直到得到最小生成树为止。

2:在所有边中，找一条权最小的边，将此边加进集合中，并将此边的非中顶点加入中。此步骤的功能是在边集中找一条边，要求这条边满足以下条件：

首先边的两个顶点要分别在顶点集合和中，其次边的权要最小。找到这条边以后，把这条边放到边集中，并把这条边上不在中的那个顶点加入到中。这一步骤在算法中应执行多次，每执行一次，集合和都将发生变化，分别增加一条边和一个顶点，因此，和是两个动态的集合，这一点在理解算法时要密切注意。

3:如果，则算法结束；否则重复步骤2。可以把本步骤看成循环终止条件。

我们可以算出当时，步骤2共执行了次(设为图中顶点的数目),中也增加了条边，这条边就是需要求出的最小生成树的边。

prim算法伪**如下：

void minispantree_prim(mgraph g,vertextype u)

closedge[k].loecost=0初始，u=

for(i-0;i< /选择其余个顶点。

k=minimum(closedge); 求出t的下一个结点：第k顶点。

closedge[k].loecost=

min, }

printf(closedge[k].adjvex, /输出生成树的边。

closedge[k].lowcost=0第k顶点并入u集。

for(j=0;j<

if(closedge[j]=

//minispantree

由上述伪**可知，prim算法的时间复杂度为。

算法构造最小生成树如下图所示：

图2图3图4

图5图6图7

2）kruskal算法。

假设是一个含有个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有棵树的一个森林。之后，从网的边集中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。

依次类推，直至森林中只有一棵树，也即子图中含有条边为止。

kruskal算法的伪**如下：

void dfsarticul(algraph g,int v0){

/从第v0个顶点出发深度优先遍历图g，查找并输出关节点。

visited[v0]=min=++count; /v0是第count个访问的顶点。

for(p=>nextarc){/对v0的每个邻接顶点检查。

w=p->adjvex; /w为v0的邻接顶点。

if(visited[w]==0){ w未曾访问，是v0的孩子。

dfsarticul(g,w); 返回前求得low[w]

if(low[w] if(low[w]>=visited[v0]) printf(v0, /关节点。

else if(visited[w]w已访问，w是v0在生成树上的祖先。

//forlow[v0]=min

//dfsarticul。

kruskal算法的时间复杂度为（其中e为网中边得数目）。

kruskal算法构造最小生成树如下图所示：

图8图9图10

图11图12图13

输入（表1）：表1

数据结构课程设计

数据结构课程设计

数据结构课程设计

数据结构课程设计

其他用户还读了