天猫网站设计特点,网络策划需要哪些技能,郑州市城乡建设局网站,蓝色经典通用网站模板简介#xff1a;主要为图的顺序存储和链式存储。其中顺序存储即邻接矩阵的画法以及代码#xff0c;邻接矩阵又分为有权图和无权图#xff0c;区别就是有数据的地方填权值#xff0c;无数据的地方可以填0或者∞#xff0c;而有权图和无权图#xff0c;又细分为有向图和无向…简介主要为图的顺序存储和链式存储。其中顺序存储即邻接矩阵的画法以及代码邻接矩阵又分为有权图和无权图区别就是有数据的地方填权值无数据的地方可以填0或者∞而有权图和无权图又细分为有向图和无向图。无向图为对称矩阵因为没有方向可言出度入度一样。而有向图则有区分对了邻接矩阵横着看是出度竖着看是入度。链式存储中则包含邻接表、十字链表和邻接多重表其中邻接表有向图和无向图都可以而十字链表是其邻接表有向图的优化可以同时计算入度和出度而邻接多重表是邻接表无向图的优化可以节约一半的边数空间由原来的顶点数2*总边数变为了顶点数总边数。 目录
一、顺序存储-邻接矩阵
1.1-简介
1.2-代码
1.3-运行结果
二、链式存储-邻接表
2.1邻接表
2.1.1.代码
2.2十字链表
2.2.1代码
2.3邻接多重表
2.3.1代码 一、顺序存储-邻接矩阵
1.1-简介
图嘛自然是包括了顶点和边。而邻接矩阵则是通过数组的形式表示图。
其中需要一个一维数组用来存储顶点的信息——顶点即一个单位像学生1学生2之类的。
还需要一个二维数组就是邻接矩阵来存储顶点之间的关系其次则是记录图中顶点数和边的总数。
我代码的思路是自己想的从创建到可以运行如果遇到简单的我后期再来改。
思路
先初始化图给图输入想要的顶点数和边数。其次初始化一维数组和二维数组。创建以及输入数据先给顶点的信息输入顶点数组中。随后是进行判断看是有向图还是无向图。这里面默认是无权图有权图只不过又多了一组需要手动输入的数字。无向图是对称矩阵输入想要的边的关系即1与2则邻接矩阵对应的直接改为1表示两个点之间相连同时更新对称位置也为1.有向图。则是更新一个就行另一个不更新。
1.2-代码
#include stdio.h
#define Max 10
#include string.h
//图的顺序存储_邻接矩阵
typedef struct
{char vertex[Max]; //存放顶点的一维数组 int edge[Max][Max]; //表示顶点之间关系的二维数组 int vertex_num; //顶点数 int edge_num; //边数 }MGragh;
//初始化邻接矩阵
void InitMGragh(MGragh *a)
{printf(添加几个顶点\n);int x;scanf(%d,x); //赋值 a-vertex_numx;printf(有多少条边\n); int c; scanf(%d,c);//赋值 a-edge_numc;//初始化邻接矩阵存储边信息的二维数组 a-edge[Max][Max];int p,q;for(p0;pa-vertex_num;p){for(q0;qa-vertex_num;q){a-edge[p][q]0;}} //初始化顶点数组 a-vertex[a-vertex_num]0;
}
//打印邻接矩阵
void PrintMGragh(MGragh *a)
{int p,q;for(p0;pa-vertex_num;p){for(q0;qa-vertex_num;q){printf(%d ,a-edge[p][q]);}printf(\n);}
}
void Creat_MGragh(MGragh *a)
{printf(图的顶点数%d\n,a-vertex_num);int i0;printf(请加顶点到顶点数组\n); for(i0;ia-vertex_num;i){ printf(i%d\n,i);char x;xgetchar();char k;//由于单个字符输入回车也在输入序列中因此还需要一个变量来吃掉回车 kgetchar();a-vertex[i]x;}printf(您想弄成无向图还是有向图,1为无向图2为有向图\n);int text;scanf(%d,text);if(text 1){printf(请添加顶点间关系\n); int w0;while(w!2){printf(哪个顶点和哪个顶点之间有联系\n);int d1,d2;scanf(%d %d,d1,d2);a-edge[d1-1][d2-1]1;a-edge[d2-1][d1-1]1;printf(是否还需要继续添加是填1否填2\n);scanf(%d,w); } }else{printf(请添加顶点间关系\n); int w0;while(w!2){int d1,d2;printf(从哪个顶点到哪个顶点\n);scanf(%d %d,d1,d2);a-edge[d1-1][d2-1]1;printf(是否还需要继续添加是填1否填2\n);scanf(%d,w); }}
}int main()
{MGragh a;//初始化图 InitMGragh(a);//创建邻接矩阵图 Creat_MGragh(a); //打印邻接矩阵 PrintMGragh(a);return 0;}
1.3-运行结果 二、链式存储-邻接表
2.1邻接表 简介邻接表实际上主要为一个顶点表后面串着相应的边表。在记录总的边数和顶点数。
为链式存储。它适用于稀疏图方便计算出度只需要找到相应的顶点然后通过该顶点的单链表往后遍历串就行。但入度则需要遍历每个顶点单链表。
无向图有向图都可以。有向图每个顶点传一个方向的要么都弄出度要么都弄入度。所以它所需要的空间为O(顶点数总边数)而无向图则是与该顶点相连的都穿起来因此所需要的存储空间为O(顶点数2*总边数)。
2.1.1.代码 边表ArcNode包括该点下标和下一个指针域。
//边表
typedef struct ArcNode
{int NodeName;struct ArcNode *next;}ArcNode; 顶点表存储图的各个顶点每个顶点后面实际上是对应的从他出发的出度的单链表。
//顶点表
typedef struct
{int data;//顶点内容 ArcNode* first; //顶点标的链的头指针 }VNode; 邻接表最后才是邻接表即只需要通过顶点表就可访问其各个顶点的出度。
//创建邻接表包含顶点表和边表以及边数和顶点数的记录
typedef struct
{VNode vertice[vertice_num];//顶点表每个顶点标中的数据串成一个对应的链 int vexnum;//顶点数 int edgenum;//边数
}ALGragh; 由于实现的话以我目前的水平感觉有点麻烦需要遍历每个顶点每个顶点还需要创建边表结点还需要给每个顶点单链表形成目前没思路写到中间卡壳了以后熟练了再来补实现
2.2十字链表 简介十字链表仅适用于有向图为了弥补邻接表中有向图只能计算单向的度。
多了一些入度的信息。先给邻接表的形式出度画出来。随后再找顶点表中各个顶点的入度入0的入度从0出发看边表中哪个终点为0则连起来没有则置为空。 十字链表仍然是通过顶点表即可遍历相应顶点的出度链和入度链即可直到相应顶点的出度和入度。 2.2.1代码
//边表
typedef struct ArcNode
{int tailvex,headvex;//弧尾tail弧头head 弧尾起点-弧头终点 struct ArcNode *hlink,*tlink;//指针域即出度指针域为弧头入读指针域为弧尾先连接弧头指针域出度、再连接弧尾指针域 char info;//存储信息的指针
}ArcNode;
//顶点表
typedef struct VNode
{AreNode *firstin,*firstout;//出度入读头指针 int data;//顶点信息 }VNode;
//十字链表
typedef struct GLGraph
{VNode xlist[vertice_num];//顶点表 int vexnum,edgenum;//顶点数和边数 }GLGraph;
2.3邻接多重表
简介邻接多重表仅适用于无向图是邻接表中无向图的优化邻接表中无向图会重复多连2*总边数而邻接多重表节约为E。
画法先画出顶点表和边表边表中为与最左边顶点表中顶点相关的顶点即边为边的起点和边的终点并有两个相关的指针域。第一步先标记好相应的数值自上而下画下方顶点若有重复的边则不画。
//强连通机构的例题——不想自己画了偷个懒 第二步串链由左边顶点表中的顶点出发找右边边表中与该顶点相同的指针域连接上即可如b的下标是2从b出发找右边边表中2的指针域。2的指针域第一行有一个第二行有两个给这三个串上即可。 2.3.1代码
//邻接多重表-无向图
//边表
typedef struct AreNode
{int mark; //标记是否串过int ivex,jvex;//表示弧的两个顶点struct AreNode *ilink,*jlink;char info;//其他信息
}AreNode;
//顶点表
typedef struct VNode
{int data;//顶点信息 AreNode *first;//指向边表中第一个挨着该顶点的结点 }VNode;
//邻接多重表
typedef struct AMLGraph
{VNode xlist[vertice_num];//顶点表 int vexnum,edgenum;//总边数和总结点数
}AMLGraph;
