数据结构实验报告最小生成树

第1页 《算法与数据结构》实验报告

实验一 约瑟夫环问题（2学时）

将编号为1，2，…，n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数上限值m，从第一个开始按顺时针方向自1开始报数，报到m时停止报数。报m的人出列，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。

实验二 链表的操作（4学时）

编一程序：① 建立一个数据域为1至10的带头结点的链表；

② 将此链表就地逆转。

链表的类型说明如下：

#include

#include

class Node{

public:

int data;

Node *next;

Node( ){next=0;}

friend class LinkList;

};//Node

class LinkList {

Node *head;

public:

LinkList( ) { head=new Node(); }

void Create(); //创建长度为n的单链表

int GetElem(int i); //返回第i个元素值

Node* Locate(int e); //返回第一个与e匹配的元素结点指针

bool IsEmpty( ) {return (head->next==0);} //判断是否为空链表 第2页 void Insert(int x, int i ); //在第i个结点之前插入元素值为x的结点

int Delete ( int i ); //删除第i个结点，并返回其元素值

的最小生成树算法Prim与Kruskal算法的比较

Prim算法和Kruskal算法都是常用的最小生成树算法，它们可以在给定的加权连通图中找到连接所有节点的最小权重边集合。然而，这两种算法在实现细节和时间复杂度上有所不同。本文将对Prim算法和Kruskal算法进行比较，并讨论它们的优缺点以及适用场景。

一、Prim算法

Prim算法是一种贪心算法，它从一个起始节点开始，逐步扩展最小生成树的边集合，直到包含所有节点为止。具体步骤如下：

1. 选取一个起始节点作为最小生成树的根节点。

2. 在最小生成树的边集合中寻找与当前树集合相连的最小权重边，并将这条边添加到最小生成树中。

3. 将新添加的节点加入到树集合中。

4. 重复步骤2和3，直到最小生成树包含所有节点为止。

Prim算法的时间复杂度为O(V^2)，其中V是节点的个数。这是因为在每轮迭代中，需要从树集合以外的节点中找到与树集合相连的最小权重边，而在最坏情况下，可能需要检查所有的边。

二、Kruskal算法

Kruskal算法是一种基于边的贪心算法，它按照边的权重从小到大的顺序依次选择边，并判断是否加入最小生成树中。具体步骤如下： 1. 初始化一个空的最小生成树。

2. 将所有边按照权重从小到大进行排序。

3. 依次检查每条边，如果这条边连接了两个不同的树（即不会形成环），则将这条边加入到最小生成树中。

4. 重复步骤3，直到最小生成树包含所有节点为止。

Kruskal算法使用并查集数据结构来快速判断连通性，时间复杂度为O(ElogE)，其中E是边的个数。排序边的时间复杂度为O(ElogE)，而对每条边进行判断和合并操作的时间复杂度为O(E)。

三、比较与总结

1. 时间复杂度：Prim算法的时间复杂度为O(V^2)，而Kruskal算法的时间复杂度为O(ElogE)。因此，在边的数量较大的情况下，Kruskal算法的效率优于Prim算法。

《数据结构和算法》

实验指导书

实验及学时数分配

序号 实验名称 学时数（小时）

1 实验一 线性表 4

2 实验二 树和二叉树 2

3 实验三 图 2

4 实验四 查找 2

5 实验五 内部排序 2

合计 12

几点要求：

一、 上机前：认真预习相关实验内容，提前编写算法程序，上机时检查（未提前编写程序者，扣除平时成绩中实验相关分数）。

二、 上机中：在Turbo C或VC6.0环境中，认真调试程序，记录调试过程中的问题、解决方法以及运行结果。上机时签到；下机时验收签字。

三、 下机后：按要求完成实验报告，并及时提交（实验后1周内）。

实验一 线性表

【实验目的】

1、 掌握用Turbo c上机调试线性表的基本方法；

2、 掌握线性表的基本操作，插入、删除、查找以及线性表合并等运算在顺序存储结构和链式存储结构上的运算；

3、 运用线性表解决线性结构问题。

【实验学时】

4 学时

【实验类型】

设计型

【实验内容】

1、 顺序表的插入、删除操作的实现；

2、 单链表的插入、删除操作的实现；

3、 两个线性表合并算法的实现。(选做)

【实验原理】

1、 当我们在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表中第i个元素之后的所有元素依次后移一个位置，以便腾出一个位置，再把新元素插入到该位置。若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置；

2、 当我们在线性表的链式存储结构上的第i个位置上插入一个元素时，只需先确定第i个元素前一个元素位置，然后修改相应指针将新元素插入即可。若是欲删除第i个元素时，也必须先确定第i个元素前一个元素位置，然后修改相应指针将该元素删除即可；

3、 详细原理请参考教材。

【实验步骤】

一、用C语言编程实现建立一个顺序表，并在此表中插入一个元素和删除一个元素。

1、 通过键盘读取元素建立线性表；（从键盘接受元素个数n以及n个整形数；按一定格式显示所建立的线性表）

数据结构普里姆算法

普里姆算法（Prim'salgorithm）是一种贪心算法，用于在加权无向图中找到最小生成树。该算法在每一步选择当前生成树到最远未连接点的最小边，直到所有的点都被连接起来。以下是普里姆算法的基本步骤：1.随机选择图中的一点作为起始点，将其加入生成树集合中。2.在所有连接已选择点和未选择点的边中，选择权重最小

的边。将这条边以及其对应的未选择点加入到生成树集合中。3.重复步骤2，直到所有的点都被加入到生成树集合中。下面是使用Python实现的普里姆算法示例：```python

importheapq

defprim(graph,start):

mst={}#最小生成树的键值对，键为节点，值为

该节点所在的最小权重边visited=set([start])#已访问的节点集合

edges=[#用于存储最小权重边的优先队列，键为

权重，值为边的信息(weight,start,to)

forto,weightingraph[start].items()]

heapq.heapify(edges)

whileedges:

weight,frm,to=heapq.heappop(edges)

iftonotinvisited:visited.add(to)

mst[to]=(frm,weight)#将边加入最小

生成树中forto_next,weight2in

graph[to].items():ifto_nextnotinvisited:heapq.heappush(edges,

(weight2,to,to_next))#将相邻未访问节点加入优先队列中returnmst

```

其中，`graph`是一个字典，表示无向图的邻接表形式。字典的键表示节点，值是另一个字典，表示与该节点相邻的节

点及其对应的权重。`start`是算法的起始点。函数返回一个字典，表示最小生成树，其中键是节点，值是该节点所在的

最小权重边。边的信息由起始节点、权重和目标节点组成。