开课实验室:计算机科学与工程实验(电子楼) 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:仅作为实验参考,有些地方可能不够完善,见谅一下。转载请注明出处!
文章浏览阅读1.6k次。安装配置gi、安装数据库软件、dbca建库见下:http://blog.csdn.net/kadwf123/article/details/784299611、检查集群节点及状态:[root@rac2 ~]# olsnodes -srac1 Activerac2 Activerac3 Activerac4 Active[root@rac2 ~]_12c查看crs状态
文章浏览阅读1.3w次,点赞45次,收藏99次。我个人用的是anaconda3的一个python集成环境,自带jupyter notebook,但在我打开jupyter notebook界面后,却找不到对应的虚拟环境,原来是jupyter notebook只是通用于下载anaconda时自带的环境,其他环境要想使用必须手动下载一些库:1.首先进入到自己创建的虚拟环境(pytorch是虚拟环境的名字)activate pytorch2.在该环境下下载这个库conda install ipykernelconda install nb__jupyter没有pytorch环境
文章浏览阅读5.2k次,点赞19次,收藏28次。选择scoop纯属意外,也是无奈,因为电脑用户被锁了管理员权限,所有exe安装程序都无法安装,只可以用绿色软件,最后被我发现scoop,省去了到处下载XXX绿色版的烦恼,当然scoop里需要管理员权限的软件也跟我无缘了(譬如everything)。推荐添加dorado这个bucket镜像,里面很多中文软件,但是部分国外的软件下载地址在github,可能无法下载。以上两个是官方bucket的国内镜像,所有软件建议优先从这里下载。上面可以看到很多bucket以及软件数。如果官网登陆不了可以试一下以下方式。_scoop-cn
文章浏览阅读4.5k次,点赞2次,收藏3次。首先要有一个color-picker组件 <el-color-picker v-model="headcolor"></el-color-picker>在data里面data() { return {headcolor: ’ #278add ’ //这里可以选择一个默认的颜色} }然后在你想要改变颜色的地方用v-bind绑定就好了,例如:这里的:sty..._vue el-color-picker
文章浏览阅读640次。基于芯片日益增长的问题,所以内核开发者们引入了新的方法,就是在内核中只保留函数,而数据则不包含,由用户(应用程序员)自己把数据按照规定的格式编写,并放在约定的地方,为了不占用过多的内存,还要求数据以根精简的方式编写。boot启动时,传参给内核,告诉内核设备树文件和kernel的位置,内核启动时根据地址去找到设备树文件,再利用专用的编译器去反编译dtb文件,将dtb还原成数据结构,以供驱动的函数去调用。firmware是三星的一个固件的设备信息,因为找不到固件,所以内核启动不成功。_exynos 4412 刷机
文章浏览阅读2w次,点赞24次,收藏42次。Linux系统配置jdkLinux学习教程,Linux入门教程(超详细)_linux配置jdk
文章浏览阅读3.3k次,点赞5次,收藏19次。xlabel('\delta');ylabel('AUC');具体符号的对照表参照下图:_matlab微米怎么输入
文章浏览阅读119次。顺序读写指的是按照文件中数据的顺序进行读取或写入。对于文本文件,可以使用fgets、fputs、fscanf、fprintf等函数进行顺序读写。在C语言中,对文件的操作通常涉及文件的打开、读写以及关闭。文件的打开使用fopen函数,而关闭则使用fclose函数。在C语言中,可以使用fread和fwrite函数进行二进制读写。 Biaoge 于2024-03-09 23:51发布 阅读量:7 ️文章类型:【 C语言程序设计 】在C语言中,用于打开文件的函数是____,用于关闭文件的函数是____。
文章浏览阅读3.4k次,点赞2次,收藏13次。跟随鼠标移动的粒子以grid(SOP)为partical(SOP)的资源模板,调整后连接【Geo组合+point spirit(MAT)】,在连接【feedback组合】适当调整。影响粒子动态的节点【metaball(SOP)+force(SOP)】添加mouse in(CHOP)鼠标位置到metaball的坐标,实现鼠标影响。..._touchdesigner怎么让一个模型跟着鼠标移动
文章浏览阅读178次。项目运行环境配置:Jdk1.8 + Tomcat7.0 + Mysql + HBuilderX(Webstorm也行)+ Eclispe(IntelliJ IDEA,Eclispe,MyEclispe,Sts都支持)。项目技术:Springboot + mybatis + Maven +mysql5.7或8.0+html+css+js等等组成,B/S模式 + Maven管理等等。环境需要1.运行环境:最好是java jdk 1.8,我们在这个平台上运行的。其他版本理论上也可以。_基于java技术的停车场管理系统实现与设计
文章浏览阅读3.5k次。前言对于MediaPlayer播放器的源码分析内容相对来说比较多,会从Java-&amp;gt;Jni-&amp;gt;C/C++慢慢分析,后面会慢慢更新。另外,博客只作为自己学习记录的一种方式,对于其他的不过多的评论。MediaPlayerDemopublic class MainActivity extends AppCompatActivity implements SurfaceHolder.Cal..._android多媒体播放源码分析 时序图
文章浏览阅读2.4k次,点赞41次,收藏13次。java 数据结构与算法 ——快速排序法_快速排序法