网站后台发文章图片链接怎么做,皖icp备 网站建设,网站做引流,语文建设编辑部官方网站目录:代码#xff1a;分析#xff1a;汇编#xff1a;MGrapth图表示有邻接矩阵的方式构成的图结构。邻接矩阵用两个数组保存数据#xff0c;一个一维数组存储图中的顶点信息#xff0c;一个二维数组存储图中边或弧的信息。无向图中的二维数组是个对称矩阵 1.0表示无边分析汇编MGrapth图表示有邻接矩阵的方式构成的图结构。邻接矩阵用两个数组保存数据一个一维数组存储图中的顶点信息一个二维数组存储图中边或弧的信息。无向图中的二维数组是个对称矩阵 1.0表示无边1表示有边 2.顶点的度是行内数组之和 3.求取顶点邻接占将行内元素遍历下
有向图的邻接矩阵二维数组 有分入度和出度行内之和是出度列内之和是入度
代码
LinkQueue.h
#ifndef _LINKQUEUE_H_
#define _LINKQUEUE_H_typedef void LinkQueue;LinkQueue* LinkQueue_Create();void LinkQueue_Destroy(LinkQueue* queue);void LinkQueue_Clear(LinkQueue* queue);int LinkQueue_Append(LinkQueue* queue, void* item);void* LinkQueue_Retrieve(LinkQueue* queue);void* LinkQueue_Header(LinkQueue* queue);int LinkQueue_Length(LinkQueue* queue);#endif
LinkQueue.c
#include malloc.h
#include stdio.h
#include LinkQueue.htypedef struct _tag_LinkQueueNode TLinkQueueNode;//定义队列节点类型
struct _tag_LinkQueueNode
{TLinkQueueNode* next;void* item;
};typedef struct _tag_LinkQueue//定义队列类型
{TLinkQueueNode* front;TLinkQueueNode* rear;int length;
} TLinkQueue;LinkQueue* LinkQueue_Create() //定义创建队列函数
{TLinkQueue* ret (TLinkQueue*)malloc(sizeof(TLinkQueue));if( ret ! NULL ){ret-front NULL;ret-rear NULL;ret-length 0;}return ret;
}void LinkQueue_Destroy(LinkQueue* queue) // 定义销毁队列函数
{LinkQueue_Clear(queue);free(queue);
}void LinkQueue_Clear(LinkQueue* queue) // 定义清空队列函数
{while( LinkQueue_Length(queue) 0 ){LinkQueue_Retrieve(queue);}
}int LinkQueue_Append(LinkQueue* queue, void* item) // 定义进队列函数
{TLinkQueue* sQueue (TLinkQueue*)queue;//取得队列TLinkQueueNode* node (TLinkQueueNode*)malloc(sizeof(TLinkQueueNode));//新建节点int ret (sQueue ! NULL ) (item ! NULL) (node ! NULL);if( ret ){node-item item;//给新建节点保存的数据赋值if( sQueue-length 0 )//如果长度大于0{sQueue-rear-next node;//将队列最后一个节点的next指向新建节点sQueue-rear node;//设新建节点为最后节点 node-next NULL;}else//否则 表示是第一个节点{sQueue-front node;//设第一个节点为新建节点sQueue-rear node;//设最后一个节点为新建节点node-next NULL;}sQueue-length;}if( !ret )//条件不成功{free(node);//释放新建节点}return ret;
}void* LinkQueue_Retrieve(LinkQueue* queue) // 定义出队列函数
{TLinkQueue* sQueue (TLinkQueue*)queue;//取得队列TLinkQueueNode* node NULL;void* ret NULL;if( (sQueue ! NULL) (sQueue-length 0) ){node sQueue-front;//取得出队列节点sQueue-front node-next;//将队列第一个节点设为取出节点的下一个ret node-item;//取得节点保存的数据free(node);//释放出队列节点sQueue-length--;if( sQueue-length 0 )//如果是最后一个节点{sQueue-front NULL;//将第一个节点指针清空sQueue-rear NULL;//将最后一个节点指针清空}}return ret;
}void* LinkQueue_Header(LinkQueue* queue) // 定义获取第一个节点数据函数
{TLinkQueue* sQueue (TLinkQueue*)queue;void* ret NULL;if( (sQueue ! NULL) (sQueue-length 0) ){ret sQueue-front-item;}return ret;
}int LinkQueue_Length(LinkQueue* queue) // 定义获取队列长度函数
{TLinkQueue* sQueue (TLinkQueue*)queue;int ret -1;if( sQueue ! NULL ){ret sQueue-length;}return ret;
}
MGraph.h #ifndef _MGRAPH_H_
#define _MGRAPH_H_typedef void MGraph;//定义图类型
typedef void MVertex;//定义顶点类型
typedef void (MGraph_Printf)(MVertex*);//定义有一个顶点类型指针参数并且无返回值的函数类型MGraph* MGraph_Create(MVertex** v, int n);//声明创建图函数void MGraph_Destroy(MGraph* graph);//声明销毁图函数void MGraph_Clear(MGraph* graph);//声明清空图函数int MGraph_AddEdge(MGraph* graph, int v1, int v2, int w);//声明添加边函数int MGraph_RemoveEdge(MGraph* graph, int v1, int v2);//声明移除边函数int MGraph_GetEdge(MGraph* graph, int v1, int v2);//声明获取边函数int MGraph_TD(MGraph* graph, int v);//声明以一个数作为行与列检测不等于0的值的数量函数int MGraph_VertexCount(MGraph* graph);//声明获取顶点数量函数int MGraph_EdgeCount(MGraph* graph);//声明获取边数量函数void MGraph_DFS(MGraph* graph, int v, MGraph_Printf* pFunc);//声明void MGraph_BFS(MGraph* graph, int v, MGraph_Printf* pFunc);//声明void MGraph_Display(MGraph* graph, MGraph_Printf* pFunc);//声明#endif
MGraph.c
#include malloc.h
#include stdio.h
#include MGraph.h
#include LinkQueue.htypedef struct _tag_MGraph//定义实际使用图类型
{int count;//数量MVertex** v;//指向顶点指针的指针变量int** matrix;//指向整型指针的指针变量
} TMGraph;//递归遍历矩阵函数
static void recursive_dfs(TMGraph* graph, int v, int visited[], MGraph_Printf* pFunc)
{int i 0;pFunc(graph-v[v]);visited[v] 1;printf(, );for(i0; igraph-count; i){if( (graph-matrix[v][i] ! 0) !visited[i] ){recursive_dfs(graph, i, visited, pFunc);}}
}
//用队列遍历矩阵
static void bfs(TMGraph* graph, int v, int visited[], MGraph_Printf* pFunc)
{LinkQueue* queue LinkQueue_Create();//创建队列if( queue ! NULL )//创建成功{LinkQueue_Append(queue, graph-v v);//将顶点信息存进队列visited[v] 1;//将对应行记录为已查看while( LinkQueue_Length(queue) 0 ){int i 0;v (MVertex**)LinkQueue_Retrieve(queue) - graph-v;pFunc(graph-v[v]);printf(, );for(i0; igraph-count; i){if( (graph-matrix[v][i] ! 0) !visited[i] ){LinkQueue_Append(queue, graph-v i);visited[i] 1;}}}}LinkQueue_Destroy(queue);
}MGraph* MGraph_Create(MVertex** v, int n) // 定义创建图函数
{TMGraph* ret NULL;if( (v ! NULL ) (n 0) ){ret (TMGraph*)malloc(sizeof(TMGraph));//新建图if( ret ! NULL )//新建成功{int* p NULL;ret-count n;//设置数量ret-v (MVertex**)malloc(sizeof(MVertex*) * n);//创建n个顶点指针类型的空间v指向第一个ret-matrix (int**)malloc(sizeof(int*) * n);//创建n个整型指针类型的空间matrix指向第一个p (int*)calloc(n * n, sizeof(int));//创建n*n个int 类型空间p指向第一个if( (ret-v ! NULL) (ret-matrix ! NULL) (p ! NULL) )//全部创建成功{int i 0;for(i0; in; i){ret-v[i] v[i];//将传来的顶点信息给新建的图中的顶点赋值ret-matrix[i] p i * n;//将新建图中的矩阵指向p创建的地址(0,6,12,18,24,30)}}else//如果创建失败将申请的空间全部释放{free(p);free(ret-matrix);free(ret-v);free(ret);ret NULL;//返回空}}}return ret;
}void MGraph_Destroy(MGraph* graph) //定义销毁图函数
{TMGraph* tGraph (TMGraph*)graph;//取得图if( tGraph ! NULL )//图不为空将空间全部释放{free(tGraph-v);free(tGraph-matrix[0]);free(tGraph-matrix);free(tGraph);}
}void MGraph_Clear(MGraph* graph) // 定义清空图函数
{TMGraph* tGraph (TMGraph*)graph;//取得图if( tGraph ! NULL )//图不为空{int i 0;int j 0;for(i0; itGraph-count; i){for(j0; jtGraph-count; j){tGraph-matrix[i][j] 0;//将矩阵数值全设0}}}
}int MGraph_AddEdge(MGraph* graph, int v1, int v2, int w) // 定义添加边函数
{TMGraph* tGraph (TMGraph*)graph;//取得图int ret (tGraph ! NULL);//判断是否为空ret ret (0 v1) (v1 tGraph-count);//判断行数是否正常ret ret (0 v2) (v2 tGraph-count);//判断列数是否正常ret ret (0 w);//判断添加的值是否大于等于0if( ret )//条件成功{tGraph-matrix[v1][v2] w;//将对应行列值修改}return ret;//返回是否成功
}int MGraph_RemoveEdge(MGraph* graph, int v1, int v2) // 定义移除边函数
{int ret MGraph_GetEdge(graph, v1, v2);//获取移除的值if( ret ! 0 )//图不为空{((TMGraph*)graph)-matrix[v1][v2] 0;//将对应行列值重置0}return ret;//返回移除值
}int MGraph_GetEdge(MGraph* graph, int v1, int v2) // 定义获取边函数
{TMGraph* tGraph (TMGraph*)graph;//获取图int condition (tGraph ! NULL);//判断图不为空int ret 0;condition condition (0 v1) (v1 tGraph-count);//判断行是否正常condition condition (0 v2) (v2 tGraph-count);//判断列是否正常if( condition ){ret tGraph-matrix[v1][v2];//获取对应行列的值}return ret;//返回对应值
}int MGraph_TD(MGraph* graph, int v) // 定义以一个数作为行与列检测不等于0的值的数量函数
{TMGraph* tGraph (TMGraph*)graph;//取得图int condition (tGraph ! NULL);//判断图不为空int ret 0;condition condition (0 v) (v tGraph-count);//判断v是否在范围内if( condition ){int i 0;for(i0; itGraph-count; i)//如果一个位置的数值有效在行列交叉处会增加两次{if( tGraph-matrix[v][i] ! 0 )//如果以v作为行数将对应行列的值不等于0{ret;//数量增加}if( tGraph-matrix[i][v] ! 0 )//如果以v作为列数将对应行列的值不等于0{ret;//数量增加}}}return ret;//返回总数
}int MGraph_VertexCount(MGraph* graph) //定义获取顶点数量
{TMGraph* tGraph (TMGraph*)graph;int ret 0;if( tGraph ! NULL ){ret tGraph-count;//取得数量}return ret;
}int MGraph_EdgeCount(MGraph* graph) //定义获取边数函数
{TMGraph* tGraph (TMGraph*)graph;int ret 0;if( tGraph ! NULL ){int i 0;int j 0;for(i0; itGraph-count; i){for(j0; jtGraph-count; j){if( tGraph-matrix[i][j] ! 0 )//如果不等于0{ret;//数量增加}}}}return ret;//返回总数
}//从v行开始遍历矩阵visited记录查看过的行。输出v行顶点信息从v行i列开始只要i列不等于0并且用i值作为行检测
//i值行没有看过。就跳到i行查看此时i作为新v行又从v行i列开始检测。循环检测完矩阵每个元素
void MGraph_DFS(MGraph* graph, int v, MGraph_Printf* pFunc)
{TMGraph* tGraph (TMGraph*)graph;//取得图int* visited NULL;int condition (tGraph ! NULL);//图不为空condition condition (0 v) (v tGraph-count);//v是否在范围内condition condition (pFunc ! NULL);//函数指针不为空//判断新申请的count个int类型是否成功condition condition ((visited (int*)calloc(tGraph-count, sizeof(int))) ! NULL);if( condition ){int i 0;recursive_dfs(tGraph, v, visited, pFunc);//调用递归检测for(i0; itGraph-count; i)//如果还有行没遍历的再从该行开始遍历{if( !visited[i] ){recursive_dfs(tGraph, i, visited, pFunc);}}printf(\n);}free(visited);//释放用于记录查看行状态的空间
}
//从v行开始遍历visited记录查看过的行
//将v行对应顶点信息存进队列表示从该行开始遍历将v行记录为已查看输出v行顶点信息
//然后从出队列的行开始遍历如果v行i列不等于0并且将i作为行检测是否查看过
//如果没有将i作为要遍历的行进队列,当前v行检测完再从队列取元素循环同样操作
void MGraph_BFS(MGraph* graph, int v, MGraph_Printf* pFunc)
{TMGraph* tGraph (TMGraph*)graph;//取得图int* visited NULL;int condition (tGraph ! NULL);condition condition (0 v) (v tGraph-count);condition condition (pFunc ! NULL);condition condition ((visited (int*)calloc(tGraph-count, sizeof(int))) ! NULL);if( condition ){int i 0;bfs(tGraph, v, visited, pFunc);for(i0; itGraph-count; i)//如果还有行没遍历的再从该行开始遍历{if( !visited[i] ){bfs(tGraph, i, visited, pFunc);}}printf(\n);}free(visited);//释放用于记录查看行状态的空间
}
//将矩阵中不为0的数值将其坐标与数值输出
void MGraph_Display(MGraph* graph, MGraph_Printf* pFunc) // O(n*n)
{TMGraph* tGraph (TMGraph*)graph;//取得图if( (tGraph ! NULL) (pFunc ! NULL) )//图与函数指针不为空{int i 0;int j 0;for(i0; itGraph-count; i)//输出所有顶点信息{printf(%d:, i);pFunc(tGraph-v[i]);printf( );}printf(\n);for(i0; itGraph-count; i){for(j0; jtGraph-count; j){if( tGraph-matrix[i][j] ! 0 )//将矩阵中不等于0的坐标与数据输出{printf();pFunc(tGraph-v[i]);//输出行printf(, );pFunc(tGraph-v[j]);//输出列printf(, %d, tGraph-matrix[i][j]);//输出对应数据printf();printf( );}}}printf(\n);}
}
main.c
#include stdio.h
#include stdlib.h
#include MGraph.hvoid print_data(MVertex* v)
{printf(%s, (char*)v);
}int main(int argc, char *argv[])
{MVertex* v[] {A, B, C, D, E, F};MGraph* graph MGraph_Create(v, 6);MGraph_AddEdge(graph, 0, 1, 1);MGraph_AddEdge(graph, 0, 2, 1);MGraph_AddEdge(graph, 0, 3, 1);MGraph_AddEdge(graph, 1, 5, 1);MGraph_AddEdge(graph, 1, 4, 1);MGraph_AddEdge(graph, 2, 1, 1);MGraph_AddEdge(graph, 3, 4, 1);MGraph_AddEdge(graph, 4, 2, 1);MGraph_Display(graph, print_data);MGraph_DFS(graph, 0, print_data);//输出A,B,E,C,F,DMGraph_BFS(graph, 0, print_data);//输出A,B,C,D,E,FMGraph_Destroy(graph);getchar();return 0;
}
分析 汇编
