c语言数据结构--图的邻接矩阵和邻接表操作的基本操作

#include

#include

#include

#define MAX 100

typedef char DataType;

typedef int VectorRelationType;

typedef char VectorType;

typedef struct arcell

{

VectorRelationType adj;

//DataType * data;

}arcell, adjmatrix[MAX][MAX];

//邻接矩阵定义

typedef struct

{

VectorType vexs[MAX];//顶点向量

adjmatrixarcs;      //邻接矩阵

int vexnum,arcnum;   //图的当前顶点数和边数

// GraphType kind;

}MGraph;

typedef struct ArcNode

{

intadjvex;          //邻接点在头结点数组中的位置(下标)

struct ArcNode * nextarc;//指向下一个表结点

DataType * date;

}ArcNode;

//顶点结点

typedef struct VNode

{

VectorType vexdata;

ArcNode * firstarc;

}VNode, Adjlist[MAX];

//邻接表类型定义

typedef struct

{

Adjlist vexs;

int vexnum, arcnum;

//GraphType gtype;

}ALGraph;

//打印邻接表

void TraverseG(ALGraph G)

{

ArcNode * p;

int i;

printf("图的邻接表如下:\n");

for(i = 0; i

{

printf("%c ->", G.vexs[i].vexdata);

p = G.vexs[i].firstarc;

while(p)

{

printf("%d ->", p->adjvex);

p = p->nextarc;

}

printf("NULL\n");

}

}

//确定v在邻接矩阵中位置

int Locatevex(ALGraph * G, VectorType v)

{

int i;

for(i = 0; ivexnum; i++)

if(G->vexs[i].vexdata == v)

return (i);

return -1;

}

int locatevexM(MGraph * G, VectorType v)

{

int i;

for(i = 0; ivexnum; i++)

if(G->vexs[i] == v)

return (i);

return -1;

}

//建立邻接矩阵

void CreateMGraph(MGraph * G)

{

int i, j, k, w;

VectorType u, v;

printf("创建有向图的邻接矩阵\n");

printf("请输入当前的顶点数和弧数(vexarc): \n");

fflush(stdin);       //清空输入缓冲区，确保不影响后面的数据读取

scanf("%d %d",&G->vexnum,&G->arcnum);

for(i = 0; ivexnum; i++)

{

printf("请输入第%d个顶点(vertex): \n", i+1);

fflush(stdin);

scanf("%c", &G->vexs[i]);

}

for(i = 0; ivexnum; i++)

{

for(j = 0; j vexnum; j++)

{

G->arcs[i][j].adj = 0;

}

}

for(k = 0; karcnum; k++)

{

printf("请输入顶点和权值

fflush(stdin);

scanf("%c %c %d", &u, &v,&w);

i = locatevexM(G, u);

j = locatevexM(G, v);

G->arcs[i][j].adj = w;

}

}

void CreateALGraph(ALGraph * G)

{

int i, j, k;

ArcNode * s;

char u, v;

printf("请输入当前顶点数和弧数(vexarc):\n");

fflush(stdin);

scanf("%d %d",&G->vexnum,&G->arcnum);

printf("首先输入顶点:\n");

for(i = 0; ivexnum; i++)

{

printf("请输入顶点%d,回车输入下一个顶点\n", i);

fflush(stdin);

scanf("%c",&(G->vexs[i].vexdata));

G->vexs[i].firstarc = NULL;

}

printf("接下来输入弧:\n");

for(k = 0; karcnum; k++)

{

printf("请输入弧%d, 回车输入下一条弧\n", k);

fflush(stdin);

scanf("%c %c", &u, &v);

i = Locatevex(G, u);

j = Locatevex(G, v);

s = (ArcNode *)malloc(sizeof(ArcNode));

s->adjvex = j;

s->nextarc = G->vexs[i].firstarc;

G->vexs[i].firstarc = s;

}

}

void Print_MGraph(MGraph * G)

{

int i, j;

printf("\n");

printf("邻接矩阵输入如下: \n");

printf("[]");

for(i = 0; ivexnum; i++)

printf("%c ", G->vexs[i]);

printf("\n");

for(i = 0; ivexnum; i++)

{

printf("%c ", G->vexs[i]);

for(j = 0; j vexnum; j++)

printf("%d ", G->arcs[i][j].adj);

printf("\n");

}

}

//邻接表转换为邻接矩阵

void list_to_mat(ALGraph * AG, MGraph * MG)

{

int i, j;

ArcNode * p;

MG->vexnum =AG->vexnum;

for(i = 0; ivexnum; i++)

{

for(j = 0; j vexnum; j++)

{

MG->arcs[i][j].adj = 0;

}

}

for(i = 0; ivexnum; i++)

{

MG->vexs[i] =AG->vexs[i].vexdata;

}

printf("图的顶点向量如下:\n");

for(i = 0; ivexnum; i++)

{

printf("%d %c\n", i, MG->vexs[i]);

}

for(i = 0; ivexnum; i++)

{

p = AG->vexs[i].firstarc;

while(p != NULL)

{

MG->arcs[i][p->adjvex].adj = 1;

p = p->nextarc;

}

}

}

void main()

{

MGraph MG;

ALGraph AG;

CreateALGraph(&AG);

TraverseG(AG);

list_to_mat(&AG, &MG);

Print_MGraph(&MG);

CreateMGraph(&MG);

Print_MGraph(&MG);

}

#include

#include

#include

#define MAX 100

typedef char DataType;

typedef int VectorRelationType;

typedef char VectorType;

typedef struct arcell

{

VectorRelationType adj;

//DataType * data;

}arcell, adjmatrix[MAX][MAX];

//邻接矩阵定义

typedef struct

{

VectorType vexs[MAX];//顶点向量

adjmatrixarcs;      //邻接矩阵

int vexnum,arcnum;   //图的当前顶点数和边数

// GraphType kind;

}MGraph;

typedef struct ArcNode

{

intadjvex;          //邻接点在头结点数组中的位置(下标)

struct ArcNode * nextarc;//指向下一个表结点

DataType * date;

}ArcNode;

//顶点结点

typedef struct VNode

{

VectorType vexdata;

ArcNode * firstarc;

}VNode, Adjlist[MAX];

//邻接表类型定义

typedef struct

{

Adjlist vexs;

int vexnum, arcnum;

//GraphType gtype;

}ALGraph;

//打印邻接表

void TraverseG(ALGraph G)

{

ArcNode * p;

int i;

printf("图的邻接表如下:\n");

for(i = 0; i

{

printf("%c ->", G.vexs[i].vexdata);

p = G.vexs[i].firstarc;

while(p)

{

printf("%d ->", p->adjvex);

p = p->nextarc;

}

printf("NULL\n");

}

}

//确定v在邻接矩阵中位置

int Locatevex(ALGraph * G, VectorType v)

{

int i;

for(i = 0; ivexnum; i++)

if(G->vexs[i].vexdata == v)

return (i);

return -1;

}

int locatevexM(MGraph * G, VectorType v)

{

int i;

for(i = 0; ivexnum; i++)

if(G->vexs[i] == v)

return (i);

return -1;

}

//建立邻接矩阵

void CreateMGraph(MGraph * G)

{

int i, j, k, w;

VectorType u, v;

printf("创建有向图的邻接矩阵\n");

printf("请输入当前的顶点数和弧数(vexarc): \n");

fflush(stdin);       //清空输入缓冲区，确保不影响后面的数据读取

scanf("%d %d",&G->vexnum,&G->arcnum);

for(i = 0; ivexnum; i++)

{

printf("请输入第%d个顶点(vertex): \n", i+1);

fflush(stdin);

scanf("%c", &G->vexs[i]);

}

for(i = 0; ivexnum; i++)

{

for(j = 0; j vexnum; j++)

{

G->arcs[i][j].adj = 0;

}

}

for(k = 0; karcnum; k++)

{

printf("请输入顶点和权值

fflush(stdin);

scanf("%c %c %d", &u, &v,&w);

i = locatevexM(G, u);

j = locatevexM(G, v);

G->arcs[i][j].adj = w;

}

}

void CreateALGraph(ALGraph * G)

{

int i, j, k;

ArcNode * s;

char u, v;

printf("请输入当前顶点数和弧数(vexarc):\n");

fflush(stdin);

scanf("%d %d",&G->vexnum,&G->arcnum);

printf("首先输入顶点:\n");

for(i = 0; ivexnum; i++)

{

printf("请输入顶点%d,回车输入下一个顶点\n", i);

fflush(stdin);

scanf("%c",&(G->vexs[i].vexdata));

G->vexs[i].firstarc = NULL;

}

printf("接下来输入弧:\n");

for(k = 0; karcnum; k++)

{

printf("请输入弧%d, 回车输入下一条弧\n", k);

fflush(stdin);

scanf("%c %c", &u, &v);

i = Locatevex(G, u);

j = Locatevex(G, v);

s = (ArcNode *)malloc(sizeof(ArcNode));

s->adjvex = j;

s->nextarc = G->vexs[i].firstarc;

G->vexs[i].firstarc = s;

}

}

void Print_MGraph(MGraph * G)

{

int i, j;

printf("\n");

printf("邻接矩阵输入如下: \n");

printf("[]");

for(i = 0; ivexnum; i++)

printf("%c ", G->vexs[i]);

printf("\n");

for(i = 0; ivexnum; i++)

{

printf("%c ", G->vexs[i]);

for(j = 0; j vexnum; j++)

printf("%d ", G->arcs[i][j].adj);

printf("\n");

}

}

//邻接表转换为邻接矩阵

void list_to_mat(ALGraph * AG, MGraph * MG)

{

int i, j;

ArcNode * p;

MG->vexnum =AG->vexnum;

for(i = 0; ivexnum; i++)

{

for(j = 0; j vexnum; j++)

{

MG->arcs[i][j].adj = 0;

}

}

for(i = 0; ivexnum; i++)

{

MG->vexs[i] =AG->vexs[i].vexdata;

}

printf("图的顶点向量如下:\n");

for(i = 0; ivexnum; i++)

{

printf("%d %c\n", i, MG->vexs[i]);

}

for(i = 0; ivexnum; i++)

{

p = AG->vexs[i].firstarc;

while(p != NULL)

{

MG->arcs[i][p->adjvex].adj = 1;

p = p->nextarc;

}

}

}

void main()

{

MGraph MG;

ALGraph AG;

CreateALGraph(&AG);

TraverseG(AG);

list_to_mat(&AG, &MG);

Print_MGraph(&MG);

CreateMGraph(&MG);

Print_MGraph(&MG);

}


相关内容

  • 最小生成树数据结构实验报告

    • 摘 要 最小生成树是数据结构中图的一种重要应用,在图中对于n个顶点的连通网 可以建立许多不同的生成树,最小生成树就是在所有生成树中总的权值最小的生成树. 本课程设计是以邻接矩阵作为图的存储结构,分别采用Prim和Kruskal算法 求最小生成树.Kruskal算法和Prim算法是求最小生成树的常用算 ...

  • 医院选址问题

    • <算法与数据结构>课程设计报告 题目: 医院选址问题 完成日期:2013 年12月27日 一.课程设计目的 本课程设计的目标就是要达到理论与实际应用相结合,提高学生组织数据及编写大型程序的能力,并培养基本的.良好的程序设计技能以及合作能力. 设计中要求综合运用所学知识,上机解决一些与实际 ...

  • [数据结构]教学大纲

    • <数据结构>教学大纲 Data Structure 课程编号:J6110G0003 课程性质:学科基础课程 适用专业:计算机科学与技术.网络工程.数字媒体技术 先行课:计算机科学导论.离散数学.高级语言程序设计: 后续课:无 . 学分数:5 主讲教师:任燕.王命延.冯豫华.周石林.王玮立 ...

  • 太原理工大学数据结构试题库及答案

    • 数据结构试题库及答案 第一章 概论 一.选择题 1.研究数据结构就是研究( D). A.数据的逻辑结构 B.数据的存储结构 C.数据的逻辑结构和存储结构 D.数据的逻辑结构.存储结构及其基本操作 2.算法分析的两个主要方面是(A). A. 空间复杂度和时间复杂度 B. 正确性和简单性 C. 可读性和 ...

  • 校园导航系统课程设计

    • 校园导航 课 程设 计报 专 业:计算机科学与技术 课程设计名称:<数据结构课程设计> 题 目:校园导航问题 班 级: 学 号: 姓 名: 同 组 人 员: 指 导 老 师: 完 成 时 间:2012年2月17日 告书 摘要 校园导航问题是基于校园中的不同的景点,从陌生人的角度,为来往的 ...

  • 贪心算法 最小生成树

    • 摘 要 网络的最小生成树在实际中有广泛的应用,例如,网络G表示n各城市之间的通信线路网线路(其中顶点表示城市,边表示两个城市之间的通信线路,边上的权值表示线路的长度或造价).可通过求该网络的最小生成树达到求解通信线路或总代价最小的最佳方案.本课程设计采用贪心算法中Prim算法解决最小生成树问题,贪心 ...

  • 数据结构填空总题目

    • 1. 一个算法应该具有以下几个五个特征:(有穷性)(确定性)(输入)(输出)(可行性) 2. 算法的复杂度有(时间)和(空间)之分 3. 数据结构指的是数据之间的相互关系,,既数据的组织形式,一般包括三个方面的内容(逻辑结构)(存储结构)(数据的运算) 4. (数据元素)是数据的基本单位 5. (算 ...

  • 数据结构题库

    • 第一章绪论 一,选择题 1．组成数据的基本单位是(C ) A ．数据项B ．数据类型C ．数据元素D ．数据变量 2．数据结构是研究数据的(C )以及它们之间的相互关系. A ．理想结构,物理结构B ．理想结构,抽象结构 C ．物理结构,逻辑结构D ．抽象结构,逻辑结构 3．算法分析的两个主要方面是 ...

  • 李春葆数据结构习题与解析(修订版)

    • 李春葆编著:数据结构(C 语言篇)――习题与解析(修订版) 清华大学出版社 一.绪论 选择题 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间的 和运算等的学科. 1 A. 数据元素 B. 计算方法 C. 逻辑存储 D. 数据映像 2 A. 结构 B. 关系 C. 运算 D. ...

热门内容

标签

品牌授权   房屋遗嘱范文   预备党员心得体会范文   英语面试介绍范文   高中入团申请书范文   创业计划书格式范文   公司处罚决定书范文   毕业顶岗实习报告范文   校庆邀请函范文   初中生申请书范文   考核材料范文   投资意向书范文   关于奖励公文通报范文   无违法违纪政审情况