【C语言】图的邻接矩阵表示法实现 - 推酷
【C语言】图的邻接矩阵表示法实现
介绍图的邻接矩阵表示法C语言实现
图是一种复杂的数据结构。图的常见表示法有邻接矩阵、邻接表和十字链表。
1、假设现在已经对图有了一定的认识，现在来看图的邻接矩阵表示法所用到的数据结构：
// C语言定义图的邻接矩阵表示法
#define MAXV 20
//顶点最大个数
typedef char InfoT
//定义顶点
typedef struct{
//顶点编号
//顶点其他信息
}VertexType
typedef struct{
int edges[MAXV][MAXV]; //邻接矩阵
int vexnum,
//顶点数目，边的数目
VertexType vexs[MAXV]; //存放顶点的信息
只是定义了相关的存储结构，并未实现。
2、现在来看图的邻接表表示法用到的结构：
// C语言定义图的邻接表表示法
#include &mgraph.c&
//邻接矩阵
#define MAX_VERTEX_NUM 20
//最大结点数目
typedef enum {DG,DN,UDG,UDN}GraphK
//图的种类标记
//定义边或者弧的结构
typedef struct ArcNode{
//边或者弧所指定点的位置
InfoType * //边或者弧相关的信息，例如权值weight
struct ArcNode *nextA
//指向下一个边或者弧的结点
//定义顶点数组
typedef struct VNode {
//顶点携带的信息
//指向第一条依附于该顶点的边或者弧的指针
}VNode,AdjList[MAX_VERTEX_NUM];
//图的结构
typedef struct graphs{
AdjL //顶点数组
int vexnum, //顶点数目，边的数目
//图的种类标记
类似的，只定义了存储结构。
3、现在用完整的代码实现图的邻接矩阵表示法。
首先这是实现邻接矩阵的完整代码
// C语言定义图的邻接矩阵实现
//此文件为用到的相关函数
#define VERTEX_MAX 26
//最大顶点数目
#define MAXVALUE 32767
//顶点最大权值
typedef struct{
char Vertex[VERTEX_MAX];
//保存顶点信息
int Edges[VERTEX_MAX][VERTEX_MAX]; //保存边的权值
int isTrav[VERTEX_MAX]; //是否遍历
int VertexN
//顶点数目
//边的数目
int GraphT
//图的类型，0是无向图，1是有向图
//创建图的邻接矩阵
void Createlin(MatrixGraph *G){
int i,j,k,
//i,j,k分别为迭代数，weight是权值
char start, //边或者弧的起始顶点
printf(&please input the node's info:\n&); //输入各个顶点的信息
for(i=0;i&G-&VertexNi++){
getchar();
printf(&this is the %d num:&,i+1);
scanf(&%c&,&(G-&Vertex[i]));//保存到数组中
//输入每个边的起始顶点和权值
printf(&please input the num and the weight of each edge:\n&);
for(k=0;k&G-&EdgeNk++){
getchar();
printf(&this is %d edge:&,k+1);
scanf(&%c,%c,%d&,&start,&end,&weight);//起点，终点，权值
for(i=0;start!=G-&Vertex[i];i++);//查找起点
for(j=0;end!=G-&Vertex[j];j++); //查找终点
G-&Edges[i][j]=//保存权值
if(G-&GraphType==0){
//若是无向图，就在对角位置保存权值
G-&Edges[j][i]= }
//输出邻接矩阵的内容
void Outlin(MatrixGraph *G){
int i,j;//迭代数
for(j=0;j&G-&VertexNj++){
printf(&\t%c&,G-&Vertex[j]);}
//第一行输出顶点信息
printf(&\n&);
for(i=0;i&G-&VertexNi++){
printf(&%c&,G-&Vertex[i]);
for(j=0;j&G-&VertexNj++){
if(G-&Edges[i][j]==MAXVALUE)
//如果权是最大值就输出MAX
printf(&\tMAX&);
printf(&\t%d&,G-&Edges[i][j]);//否则就输出权值
printf(&\n&);
这是用到的测试代码：
//测试图的邻接矩阵
#include &stdio.h&
#include &tu.c& //包含进来C语言实现图的邻接矩阵的文件
int main(){
MatrixGraph G; //定义一个图
int i,j;//迭代数
//输入图的类型，0是无向图，1是有向图
printf(&please choose the type of graph(0 or 1)&);
scanf(&%d&,&G.GraphType);//保存图的类型
//输入顶点数目和边的数目
printf(&please input the VertexNum and the EdgesNum of the Graph:&);
scanf(&%d,%d&,&G.VertexNum,&G.EdgeNum);//保存顶点和边的数目
for(i=0;i&G.VertexNi++)//清空矩阵
for(j=0;j&G.VertexNj++)
G.Edges[i][j]=MAXVALUE;//设置各元素的值为最大值
Createlin(&G);//创建邻接矩阵
printf(&the graph's data is :\n&);
Outlin(&G);//输出邻接矩阵
getchar();
第三部分代码在CentOS环境下用Linux-C 编写，用gcc 编译通过，代码无错，同时注释详细，可直接参考学习。
图的邻接矩阵实现就到这里。后期会继续总结，加油！
参考资料：张子言.《常用算法深入学习实录》.电子工业出版社
已发表评论数()
请填写推刊名
描述不能大于100个字符!
权限设置： 公开
仅自己可见
正文不准确
标题不准确
排版有问题
主题不准确
没有分页内容
图片无法显示
视频无法显示
与原文不一致1、定义排序所谓排序，就是要整理文件中的记录，使之按关键字递增（或递减）次序排列起来。其确切定义如下：输入：n个记录R1，R2，…，Rn，其相应的关键字分别为K1，K2，…，Kn。输出：Ril，Ri2，…，Rin，使得Ki1≤Ki2≤…≤Kin，或Ki1≥Ki2≥…≥Kin。记录被排序的对象--文件由一组记录组成。记录则由若干个数据项（或域）组成。其中有一项可用来标识一个记录，称为关键字项。该数据项的值称为关键字（Key）。注意：在不易产生混淆时，将关键字项简称为关键字。关键字用来作排序运算依据的关键字，可以是数字类型，也可以是字符类型。关键字的选取应根据问题的要求而定。【例】在高考成绩统计中将每个考生作为一个记录。每条记录包含准考证号、姓名、各科的分数和总分数等项内容。若要惟一地标识一个考生的记录，则必须用"准考证号"作为关键字。若要按照考生的总分数排名次，则需用"总分数"作为关键字。2、排序的稳定性当待排序记录的关键字均不相同时，排序结果是惟一的，否则排序结果不唯一。在待排序的文件中，若存在多个关键字相同的记录，经过排序后这些具有相同关键字的记录之间的相对次序保持不变，该排序方法是稳定的；若具有相同关键字的记录之间的相对次序发生变化，则称这种排序方法是不稳定的。注意：排序算法的稳定性是针对所有输入实例而言的。即在所有可能的输入实例中，只要有一个实例使得算法不满足稳定性要求，则该排序算法就是不稳定的。3、分类（1）按是否涉及数据的内、外存交换分在排序过程中，若整个文件都是放在内存中处理，排序时不涉及数据的内、外存交换，则称之为内部排序（简称内排序）；反之，若排序过程中要进行数据的内、外存交换，则称之为外部排序。注意：① 内排序适用于记录个数不很多的小文件；② 外排序则适用于记录个数太多，不能一次将其全部记录放人内存的大文件。（2）按策略划分内部排序方法可以分为五类：插入排序（直接插入排序、希尔排序）、选择排序（直接选择排序、堆排序）、交换排序（冒泡排序、快速排序）、归并排序和分配排序（箱排序、基数排序）。4、顺序存储结构#defineMAXSIZE10/*用于要排序数组个数最大值，可根据需要修改*/typedefstruct{intdata[MAXSIZE+1];/*用于存储要排序的数组，data[0]用作哨兵或临时变量*//*用于记录顺序表的长度*/}SqList；或者如下定义存储结构：#definenl00//假设的文件长度，即待排序的记录数目typedefintKeyType；//假设的关键字类型typedefstruct//记录类型{KeyTypekey；//关键字项InfoTypeotherinfo；//其它数据项，类型InfoType依赖于具体应用而定义，这里可以是数据长度length}RecType；typedefRecTypeSeqList[n+1]；//SeqList为顺序表类型，表中第0个单元一般用作哨兵注意：若关键字类型没有比较算符，则可事先定义宏或函数来表示比较运算。【例】关键字为字符串时，可定义宏"#define LT(a，b)(Stromp((a)，(b))<0)"。那么算法中"a<b"可用"LT(a，b)"取代。若使用C++，则定义重载的算符"<"更为方便。5、算法分析（1）排序算法的基本操作
　大多数排序算法都有两个基本的操作：　　a、比较两个关键字的大小；　　b、改变指向记录的指针或移动记录本身。 注意：　
第b种基本操作的实现依赖于待排序记录的存储方式。（2）待排文件的常用存储方式a、以顺序表（或直接用向量）作为存储结构
排序过程：对记录本身进行物理重排（即通过关键字之间的比较判定，将记录移到合适的位置）b、以链表作为存储结构　　排序过程：无须移动记录，仅需修改指针。通常将这类排序称为链表（或链式）排序；c、用顺序的方式存储待排序的记录，但同时建立一个辅助表(如包括关键字和指向记录位置的指针组成的索引表)排序过程：只需对辅助表的表目进行物理重排（即只移动辅助表的表目，而不移动记录本身）。适用于难于在链表上实现，仍需避免排序过程中移动记录的排序方法。（3）排序算法性能评价a、评价排序算法好坏的标准评价排序算法好坏的标准主要有两条：① 执行时间和所需的辅助空间；② 算法本身的复杂程度。b、排序算法的空间复杂度若排序算法所需的辅助空间并不依赖于问题的规模n，即辅助空间是O(1)，则称之为就地排序(In-PlaceSou)。非就地排序一般要求的辅助空间为O(n)。c、排序算法的时间开销大多数排序算法的时间开销主要是关键字之间的比较和记录的移动。有的排序算法其执行时间不仅依赖于问题的规模，还取决于输入实例中数据的状态。
最新教程周点击榜
微信扫一扫The page is temporarily unavailable
nginx error!
The page you are looking for is temporarily unavailable.
Please try again later.
Website Administrator
Something has triggered an error on your
This is the default error page for
nginx that is distributed with
It is located
/usr/share/nginx/html/50x.html
You should customize this error page for your own
site or edit the error_page directive in
the nginx configuration file
/etc/nginx/nginx.conf.