开课实验室:计算机科学与工程实验(电子楼) 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:仅作为实验参考,有些地方可能不够完善,见谅一下。转载请注明出处!
文章浏览阅读645次。这个肯定是末尾的IDAT了,因为IDAT必须要满了才会开始一下个IDAT,这个明显就是末尾的IDAT了。,对应下面的create_head()代码。,对应下面的create_tail()代码。不要考虑爆破,我已经试了一下,太多情况了。题目来源:UNCTF。_攻防世界困难模式攻略图文
文章浏览阅读2.9k次,点赞3次,收藏10次。偶尔会用到,记录、分享。1. 数据库导出1.1 切换到dmdba用户su - dmdba1.2 进入达梦数据库安装路径的bin目录,执行导库操作 导出语句:./dexp cwy_init/[email protected]:5236 file=cwy_init.dmp log=cwy_init_exp.log 注释: cwy_init/init_123..._达梦数据库导入导出
文章浏览阅读1.9k次。1. 在官网上下载KindEditor文件,可以删掉不需要要到的jsp,asp,asp.net和php文件夹。接着把文件夹放到项目文件目录下。2. 修改html文件,在页面引入js文件:<script type="text/javascript" src="./kindeditor/kindeditor-all.js"></script><script type="text/javascript" src="./kindeditor/lang/zh-CN.js"_kindeditor.js
文章浏览阅读2.3k次,点赞6次,收藏14次。SPI的详情简介不必赘述。假设我们通过SPI发送0xAA,我们的数据线就会变为10101010,通过修改不同的内容,即可修改SPI中0和1的持续时间。比如0xF0即为前半周期为高电平,后半周期为低电平的状态。在SPI的通信模式中,CPHA配置会影响该实验,下图展示了不同采样位置的SPI时序图[1]。CPOL = 0,CPHA = 1:CLK空闲状态 = 低电平,数据在下降沿采样,并在上升沿移出CPOL = 0,CPHA = 0:CLK空闲状态 = 低电平,数据在上升沿采样,并在下降沿移出。_stm32g431cbu6
文章浏览阅读1.2k次,点赞2次,收藏8次。数据链路层习题自测问题1.数据链路(即逻辑链路)与链路(即物理链路)有何区别?“电路接通了”与”数据链路接通了”的区别何在?2.数据链路层中的链路控制包括哪些功能?试讨论数据链路层做成可靠的链路层有哪些优点和缺点。3.网络适配器的作用是什么?网络适配器工作在哪一层?4.数据链路层的三个基本问题(帧定界、透明传输和差错检测)为什么都必须加以解决?5.如果在数据链路层不进行帧定界,会发生什么问题?6.PPP协议的主要特点是什么?为什么PPP不使用帧的编号?PPP适用于什么情况?为什么PPP协议不_接收方收到链路层数据后,使用crc检验后,余数为0,说明链路层的传输时可靠传输
文章浏览阅读587次。软件测试工程师移民加拿大 无证移民,未受过软件工程师的教育(第1部分) (Undocumented Immigrant With No Education to Software Engineer(Part 1))Before I start, I want you to please bear with me on the way I write, I have very little gen...
文章浏览阅读304次。Thinkpad X250笔记本电脑,装的是FreeBSD,进入BIOS修改虚拟化配置(其后可能是误设置了安全开机),保存退出后系统无法启动,显示:secure boot failed ,把自己惊出一身冷汗,因为这台笔记本刚好还没开始做备份.....根据错误提示,到bios里面去找相关配置,在Security里面找到了Secure Boot选项,发现果然被设置为Enabled,将其修改为Disabled ,再开机,终于正常启动了。_安装完系统提示secureboot failure
文章浏览阅读10w+次,点赞93次,收藏352次。1、用strtok函数进行字符串分割原型: char *strtok(char *str, const char *delim);功能:分解字符串为一组字符串。参数说明:str为要分解的字符串,delim为分隔符字符串。返回值:从str开头开始的一个个被分割的串。当没有被分割的串时则返回NULL。其它:strtok函数线程不安全,可以使用strtok_r替代。示例://借助strtok实现split#include <string.h>#include <stdio.h&_c++ 字符串分割
文章浏览阅读2.3k次。1 .高斯日记 大数学家高斯有个好习惯:无论如何都要记日记。他的日记有个与众不同的地方,他从不注明年月日,而是用一个整数代替,比如:4210后来人们知道,那个整数就是日期,它表示那一天是高斯出生后的第几天。这或许也是个好习惯,它时时刻刻提醒着主人:日子又过去一天,还有多少时光可以用于浪费呢?高斯出生于:1777年4月30日。在高斯发现的一个重要定理的日记_2013年第四届c a组蓝桥杯省赛真题解答
文章浏览阅读851次,点赞17次,收藏22次。摘要:本文利用供需算法对核极限学习机(KELM)进行优化,并用于分类。
文章浏览阅读1.1k次。一、系统弱密码登录1、在kali上执行命令行telnet 192.168.26.1292、Login和password都输入msfadmin3、登录成功,进入系统4、测试如下:二、MySQL弱密码登录:1、在kali上执行mysql –h 192.168.26.129 –u root2、登录成功,进入MySQL系统3、测试效果:三、PostgreSQL弱密码登录1、在Kali上执行psql -h 192.168.26.129 –U post..._metasploitable2怎么进入
文章浏览阅读257次。本文将为初学者提供Python学习的详细指南,从Python的历史、基础语法和数据类型到面向对象编程、模块和库的使用。通过本文,您将能够掌握Python编程的核心概念,为今后的编程学习和实践打下坚实基础。_python人工智能开发从入门到精通pdf