开课实验室:计算机科学与工程实验(电子楼) 2020年12月17日
学院 |
计算机科学与网络工程学院 |
年级、专业、班 |
网络工程194 |
姓名 |
jwt |
学号 |
||
实验课程 |
数据结构实验 |
成绩 |
||||||
实验项目 |
实验三 图的操作与实现 |
指导老师 |
|
1、线性表的链表实现:遍历、查找、插入、删除、翻转
2、栈的链式存储结构实现:入栈、出栈
3、队列的链式存储结构的实现:入队、出队
4、线性表、栈和队列的应用实现
操作系统:Win10
编程软件:C++
建立下图的邻接表或邻接矩阵,并输出之。
思路: (邻接矩阵)采用二维数组来存储顶点之间的相邻关系,若两个顶点之间有直连边,则在数组对应位置赋予相应的权值(自身到自身的权值设置为0),若两个顶点之间没有直连边,则赋予32267,即int型的最大值,意为无穷大;在输入各边的权值时,写了一个找到顶点对应位置的函数,返回顶点对应的下标,这样输入时就能把权值赋予对应的位置。定义一个结构体,结构体属性包括邻接矩阵、存储顶点信息的数组、边数、顶点数。输出用二重循环即可。
以0结点为起点实现上述图的深度优先和广度优先遍历算法。
思路:(深度优先遍历)用寻找顶点下标的函数返回‘0’的下标,然后开始遍历。采用递归的方式,在邻接矩阵中,找到第一个邻接边,然后又从另一顶点开始,依次递归下去(访问过的顶点用visited[]数组记录),直到所有顶点均已被遍历。
(广度优先遍历)访问起点的所有邻接点,然后从近到远(即下标从小到大)再访问邻接点的所有邻接点,直到遍历完成。
利用普里姆(Prim)算法或克鲁斯卡尔(Kruskal)算法求上图的最小生成树,算法实现代码必须有注释。
思路:(普里姆算法)假设有两个集合,一个U,一个V-U,初始时,U里只有起点u1,V-U则为其余顶点,在V-U中寻找权值最小的(u1,vi),然后把vi加入到U,该边对应也加入到最小生成树中,依次类推最终可以得到n个顶点n-1条边的最小生成树。
利用狄克斯特拉(Dijkstra)算法求上图中0结点到其它结点的最短路径,算法实现代码必须有注释。
思路:设有两个集合,一个U,一个V-U;一维数组dist[]用于存储起点到各顶点的最短路径长度;一维数组path[]用于存储最短路径。初始时,U里只有起点u1,V-U则为其余顶点,dist[]数组置为起点的邻接信息。从V-U中寻找较小的顶点(即从dist的值较小的顶点),将它添加到U中,考查该顶点的邻接信息,若该顶点与其他顶点之间有边,则与原定最短路径长度进行比较,新路径插入了中间点,(如新路径0-1-2与原路径0-2比较)更新最短路径长度(如dist[i])为较小者。重复上述步骤,直到U中包含所有顶点。
#define MaxInt 32767
#define MAX 50
bool visited[MAX]; //访问标志数组,其初值为"false"
typedef struct
{
int vexs[MAX]; //顶点表
int arcs[MAX][MAX]; //邻接矩阵
int vexnum, arcnum; //图的当前点数和边数
}AMGraph;
int findVex(AMGraph G, int c)//查找顶点位置
{
for (int i = 0; i < G.vexnum; i++)
if (G.vexs[i] == c)//找到该元素
return i;
cout << "图中没有该结点" << endl;
return -1;
}
void createAdj(AMGraph& G)//用邻接矩阵存储无向图
{
int i, j, k;
cout << "------------------邻接矩阵的创建-------------------" << endl;
cout << endl;
cout << "请输入顶点数:";
cin >> G.vexnum;
cout << "请输入边数: ";
cin >> G.arcnum;
for (i = 0; i < G.vexnum; i++)//初始化邻接矩阵,对角线权值赋予0,没有直连边则赋予最大值
{
for (j = 0; j < G.vexnum; j++)
{
if (i == j)//对角线置0
G.arcs[i][j] = 0;
else//没有直连边则赋予最大值
G.arcs[i][j] = MaxInt;
}
}
cout << endl;
cout << "------------------顶点信息的录入-------------------" << endl;
cout << endl;
cout << "请输入顶点标号: " << endl;
for (i = 0; i < G.vexnum; i++)//输入各个顶点
cin >> G.vexs[i];
cout << endl;
cout << "------------------邻接矩阵的录入-------------------" << endl;
cout << endl;
cout << "输入边依附的顶点及权值,如 v0 v1 28" << endl;
for (k = 0; k < G.arcnum; ++k)
{ //构造邻接矩阵
int v1, v2;
int w;
cout << "请输入第" << (k + 1) << "条边依附的顶点及权值:";
cin >> v1 >> v2 >> w; //输入一条边依附的顶点及权值
i = findVex(G, v1); j = findVex(G, v2); //确定v1和v2在G中的位置,即顶点数组的下标
G.arcs[i][j] = w; //边<v1, v2>的权值置为w
G.arcs[j][i] = G.arcs[i][j]; //置<v1, v2>的对称边<v2, v1>的权值为w
}
}
void outputGraph(AMGraph G)
{
cout << endl;
cout << "------------------顶点数组的输出-------------------" << endl;
cout << endl;
cout << "无向图的顶点为: ";
for (int i = 0; i < G.vexnum; i++)//输出无向图的顶点信息
cout << G.vexs[i] << " ";
cout << endl;
cout << endl;
cout << "------------------邻接矩阵的输出-------------------" << endl;
cout << endl;
for (int i = 0; i < G.vexnum; i++)//输出邻接矩阵
{
for (int j = 0; j < G.vexnum; j++)
{
cout << G.arcs[i][j] << "\t";
}
cout << endl;
}
cout << endl;
}
void DFSGraph(AMGraph G, int v) //深度优先遍历
{
//图G为邻接矩阵类型
int w;
cout << G.vexs[v] << " ";
visited[v] = true; //访问第v个顶点,并置访问标志数组相应分量值为true
for (w = 0; w < G.vexnum; w++) //依次检查邻接矩阵v所在的行
{
if ((G.arcs[v][w] != 0) && (G.arcs[v][w] != MaxInt) && (!visited[w]))
//G.arcs[v][w] != 0 &&G.arcs[v][w] != MaxInt表示w是v的邻接点,如果w未访问,则递归调用DFS
DFSGraph(G, w);
}
}
void BFSGraph(AMGraph G, int v)//广度优先遍历
{
int i, j, w;
SqQueue Q; //定义队列
InitQueue(Q); //初始化队列
for (i = 0; i < G.vexnum; i++)//标志数组置0
visited[i] = 0;
cout << G.vexs[v];
visited[v] = 1; //已访问结点置访问标志为1
EnQueue(Q, v);//起点进队
while (!QueueEmpty(Q))
{ //队列不空
DeQueue(Q, j); //顶点v出队
for (w = 0; w < G.vexnum; w++)
if ((G.arcs[j][w] != MaxInt) && (!visited[w]))
{ //对j的每个邻接点w进行访问,再对w的每个邻接点进行访问,依此类推,并置相应标志为1,直到遍历完成
cout <<" " << G.vexs[w];
visited[w] = 1;
EnQueue(Q, w);
}
}
}
void Prim(AMGraph G, int v)
{
int clovex[MAX];
int min, i, j, k=0;
int lowest[MAX];//lowest[i]=0表示已存在于集合U中
for (i = 0; i < G.vexnum; i++)//初始化
{
lowest[i] = G.arcs[v][i];//lowest存储起点的邻接信息
clovex[i] = G.vexs[v];//clovex数组全置为起点v
}
for (i = 1; i < G.vexnum; i++)//寻找其余顶点
{
min = MaxInt;
for (j = 0; j < G.vexnum; j++)//在V-U中寻找最短的边
{
if (lowest[j] != 0 && lowest[j] < min)
{
min = lowest[j];
k = j;//k记录最近的顶点下标
}
}
//输出最小生成树的各边
cout << "第" << i << "条边为: " << clovex[k] << " " << G.vexs[k] << " " << min << endl;
lowest[k] = 0;//把最近顶点加入集合U
for (j = 0; j < G.vexnum; j++)//对集合V-U中的顶点进行调整
{
if (lowest[j] != 0 && G.arcs[k][j] < lowest[j])
{
lowest[j] = G.arcs[k][j];
clovex[j] = k; //修改数据,为下一次循环输出最小生成树的边准备
}
}
}
}
void outputPath(AMGraph G,int dist[],int path[],int U[],int v)//输出各条最短路径
{
int i, j, k,l;
int temp[MAX];//逆向存储路径的各个下标
for (i = 0; i < G.vexnum; i++)
{
if (i != v)
{
//先输出路径长度
cout << "从起点" << G.vexs[v] << "到顶点" << G.vexs[i] << "的路径为长度为: " << dist[i] << " ";
l = 0;
temp[l] = i;//终点下标
k = path[i];//k赋予原路径终点的前一顶点下标
if (k == -1)//k=-1表示没有路径
cout << "没有路径,无法到达!" << endl;
else //输出路径
{
while(k!=v)
{
l++;
temp[l] = k;
k = path[k];
}
l++;
temp[l] = v; //逆向路径的最后一个元素赋予原路径的起点
cout << G.vexs[temp[l]];//先输出起点
for (j = l - 1; j >= 0; j--)//输出路径的其他顶点
cout << "-" << G.vexs[temp[j]];
cout << endl;
}
}
}
}
void Dijkstra(AMGraph G, int v)
{
int dist[MAX];//存取各最小路径长度
int path[MAX];//路径数组,存取所经过路径的下标
int U[MAX];//集合U,若U[i]=1,则表示顶点在集合U中;若U[i]=0,则表示顶点在集合V-U中
int min,i, j, k=0;
for (i = 0; i < G.vexnum; i++)//初始化
{
dist[i] = G.arcs[v][i];//距离初始化
U[i] = 0;//初始时集合U中没有顶点
if (G.arcs[v][i] != MaxInt)//当另一顶点与起点存在直连边时,该顶点的前一顶点置为起点v
path[i] = v;
else //没有边时,置为-1
path[i] = -1;
}
U[v] = 1; //起点加入到集合U中
for (i = 0; i < G.vexnum; i++)
{
min = MaxInt;
for (j = 0; j < G.vexnum; j++)//先找到权值最小的边
{
if (U[j] == 0 && dist[j] < min)
{
min = dist[j];
k = j;
}
}
U[k] = 1;//把另一顶点加入集合U中
for (j = 0; j < G.vexnum; j++)
{
if ((U[j] == 0) && (G.arcs[k][j] < MaxInt)&&((dist[k] + G.arcs[k][j]) < dist[j]))
{ //若加入新的中间点后,所得路径比原来小,则更新最小路径
dist[j] = dist[k] + G.arcs[k][j];
path[j] = k;
}
}
}
outputPath(G,dist, path, U, v);
}
测试结果:正确
首先输入无向图的顶点数和边数,根据顶点数创建多少阶邻接矩阵,然后输入顶点,再输入各边的信息(每次输入时先输入边相连的两个顶点,还有一个权值),由于是无向图,所以矩阵是对称的,对角线元素均为0,没有边的赋予整形最大值(意味无穷大)。输入完毕后,输出顶点信息,输出邻接矩阵。
测试结果:正确
先由用户确定起点,输入起点后,调用findVex()函数返回起点对应的下标,从该顶点开始深度优先遍历无向图。
测试结果:正确
如图,根据普利姆算法生成最小生成树,并输出最小生成树的各条边。
测试结果:正确
设置‘0’为起点,计算从‘0’到各个顶点的最小路径长度,并把路径输出。
Pass:仅作为实验参考,有些地方可能不够完善,见谅一下。转载请注明出处!
文章浏览阅读2w次,点赞7次,收藏51次。四个步骤1.创建C++ Win32项目动态库dll 2.在Win32项目动态库中添加 外部依赖项 lib头文件和lib库3.导出C接口4.c#调用c++动态库开始你的表演...①创建一个空白的解决方案,在解决方案中添加 Visual C++ , Win32 项目空白解决方案的创建:添加Visual C++ , Win32 项目这......_c#调用lib
文章浏览阅读4.6k次。苹方字体是苹果系统上的黑体,挺好看的。注重颜值的网站都会使用,例如知乎:font-family: -apple-system, BlinkMacSystemFont, Helvetica Neue, PingFang SC, Microsoft YaHei, Source Han Sans SC, Noto Sans CJK SC, W..._ubuntu pingfang
文章浏览阅读159次。表单表单概述表单标签表单域按钮控件demo表单标签表单标签基本语法结构<form action="处理数据程序的url地址“ method=”get|post“ name="表单名称”></form><!--action,当提交表单时,向何处发送表单中的数据,地址可以是相对地址也可以是绝对地址--><!--method将表单中的数据传送给服务器处理,get方式直接显示在url地址中,数据可以被缓存,且长度有限制;而post方式数据隐藏传输,_html表单的处理程序有那些
文章浏览阅读1.2k次。使用说明:开启Google的登陆二步验证(即Google Authenticator服务)后用户登陆时需要输入额外由手机客户端生成的一次性密码。实现Google Authenticator功能需要服务器端和客户端的支持。服务器端负责密钥的生成、验证一次性密码是否正确。客户端记录密钥后生成一次性密码。下载谷歌验证类库文件放到项目合适位置(我这边放在项目Vender下面)https://github.com/PHPGangsta/GoogleAuthenticatorPHP代码示例://引入谷_php otp 验证器
文章浏览阅读4.3k次,点赞5次,收藏11次。matplotlib.plot画图横坐标混乱及间隔处理_matplotlib更改横轴间距
文章浏览阅读2.2k次。①Storage driver 处理各镜像层及容器层的处理细节,实现了多层数据的堆叠,为用户 提供了多层数据合并后的统一视图②所有 Storage driver 都使用可堆叠图像层和写时复制(CoW)策略③docker info 命令可查看当系统上的 storage driver主要用于测试目的,不建议用于生成环境。_docker 保存容器
文章浏览阅读834次,点赞27次,收藏13次。网络拓扑结构是指计算机网络中各组件(如计算机、服务器、打印机、路由器、交换机等设备)及其连接线路在物理布局或逻辑构型上的排列形式。这种布局不仅描述了设备间的实际物理连接方式,也决定了数据在网络中流动的路径和方式。不同的网络拓扑结构影响着网络的性能、可靠性、可扩展性及管理维护的难易程度。_网络拓扑csdn
文章浏览阅读1.8k次,点赞5次,收藏8次。IOS系统Date的坑要创建一个指定时间的new Date对象时,通常的做法是:new Date("2020-09-21 11:11:00")这行代码在 PC 端和安卓端都是正常的,而在 iOS 端则会提示 Invalid Date 无效日期。在IOS年月日中间的横岗许换成斜杠,也就是new Date("2020/09/21 11:11:00")通常为了兼容IOS的这个坑,需要做一些额外的特殊处理,笔者在开发的时候经常会忘了兼容IOS系统。所以就想试着重写Date函数,一劳永逸,避免每次ne_date.prototype 将所有 ios
文章浏览阅读5.3k次。方法一:用PLSQL Developer工具。 1 在PLSQL Developer的sql window里输入select * from test for update; 2 按F8执行 3 打开锁, 再按一下加号. 鼠标点到第一列的列头,使全列成选中状态,然后粘贴,最后commit提交即可。(前提..._excel导入pl/sql
文章浏览阅读83次。Git常用命令速查手册1、初始化仓库git init2、将文件添加到仓库git add 文件名 # 将工作区的某个文件添加到暂存区 git add -u # 添加所有被tracked文件中被修改或删除的文件信息到暂存区,不处理untracked的文件git add -A # 添加所有被tracked文件中被修改或删除的文件信息到暂存区,包括untracked的文件...
文章浏览阅读202次。分享119个ASP.NET源码总有一个是你想要的_千博二手车源码v2023 build 1120
文章浏览阅读1.8k次。版权声明:转载请注明出处 http://blog.csdn.net/irean_lau。目录(?)[+]1、缺省构造函数。2、缺省拷贝构造函数。3、 缺省析构函数。4、缺省赋值运算符。5、缺省取址运算符。6、 缺省取址运算符 const。[cpp] view plain copy_空类默认产生哪些类成员函数