qingtian

用户名：ying907

访问量：337

签　名：

等　　级
排　　名	69212
经　　验	153
参赛次数	1
文章发表	1
年　　龄	0
在职情况	学生
学　　校	周口师范学院
专　　业

　　自我简介：

TA的其他文章

图邻接表创建
浏览：269

你可能喜欢

图邻接表创建

　　作者: qingtian　　　　发表时间：2022-05-08 15:20:52 浏览：269　|　评论：0　

/*----------邻接表------------*/
    
    #include<stdio.h>
    #include<malloc.h>
    
    #define MAX_VERTEX_NUM 20
    #define InfoType int
    #define VertexType int
    #define Boolean int
    
    #define FALSE 0
    #define TRUE 1
    
    /*点与点之间的关系,换句话说，就是顶点与下一个顶点之间的关系*/
    typedef struct ArcNode{
       int adjvex;   //该弧所指向的顶点的位置
       struct ArcNode *nextarc;   //指向下一条弧的指针
       InfoType *info;    //该弧的相关信息的指针（例如，权值）
    }ArcNode;
    
    /*顶点的信息，也就是说这条弧的第一个点*/
    typedef struct{
       VertexType data;    //顶点信息
       ArcNode *firstarc;   //指向第一条依附该顶点的弧的指针
    }VNode, AdjList[MAX_VERTEX_NUM];
    
    
    /*该图的总的信息*/
    typedef struct
    {
       AdjList vertices;   //存顶点值的数组
       int vexnum,arcnum;   //图的当前顶点数和弧数
       int kind;    //图的种类标志
    }ALGraph;
    
    /*老朋友了，查找并定位*/
     int LocateVex(ALGraph G, VertexType u)
     {
       for(int i = 0; i < G.vexnum; ++ i)
       {
           if(G.vertices[i].data == u)
              return i;   //返回下标
       }
       return -1;
     }
    
     /*有向图*/
     void CreateDG(ALGraph &G)
     {
         int i, j, k;
         VertexType va, vb; //弧头弧尾
    
         printf("请输入图的顶点和弧的个数：");
         scanf("%d%d",&G.vexnum, &G.arcnum);
    
         printf("请输入顶点的值：");
         for(i = 0; i < G.vexnum; i ++)
         {
             scanf("%d", &G.vertices[i].data);
    
             G.vertices[i].firstarc = NULL;
         }
    
         /*头插法*/
         ArcNode *p;//顶点指针
         for(k = 0; k < G.arcnum; k ++)
         {
             printf("请输入弧尾和弧头：");
             scanf("%d%d", &va, &vb);
    
             i = LocateVex(G, va);  //弧尾在顶点数组中的下标
             j = LocateVex(G, vb);  //弧头在顶点数组中的下标
    
             p = (ArcNode *)malloc(sizeof(ArcNode));  //动态分配内存（来一个我开一个）
             p->adjvex = j;  //顶点下标为j
             p->info = NULL;  //图是没有权值的，所以设为空
    
             p->nextarc = G.vertices[i].firstarc;  //这个顶点的下一个指向的地址是他的第一个邻接点
             G.vertices[i].firstarc = p;  //开始创建这个点的第一个邻接点
         }
    
     }
    
    void CreateDN(ALGraph &G)
    {
         int i, j, k;
         VertexType va, vb, weight;
    
         ArcNode *p;
    
         printf("请输入图的顶点和弧的个数：");
         scanf("%d%d",&G.vexnum, &G.arcnum);
    
         printf("请输入顶点的值：");
         for(i = 0; i < G.vexnum; i ++)
         {
             scanf("%d", &G.vertices[i].data);
    
             G.vertices[i].firstarc = NULL;
         }
    
         for(k = 0; k < G.arcnum; k ++)
         {
             printf("请输入弧尾、弧头和权值：");
             scanf("%d%d%d", &va, &vb, &weight);
    
             i = LocateVex(G, va);
             j = LocateVex(G, vb);
    
             p = (ArcNode *)malloc(sizeof(ArcNode));
             p->adjvex = j;
    
             p->info = (InfoType *)malloc(sizeof(InfoType));
             *(p->info) = weight;
    
             p->nextarc = G.vertices[i].firstarc;
             G.vertices[i].firstarc = p;
         }
    }
    
    void CreateUDG(ALGraph &G)
    {
         int i, j, k;
         VertexType va, vb;
    
         ArcNode *p;
    
         printf("请输入图的顶点和弧的个数：");
         scanf("%d%d",&G.vexnum, &G.arcnum);
    
         printf("请输入顶点的值：");
         for(i = 0; i < G.vexnum; i ++)
         {
             scanf("%d", &G.vertices[i].data);
    
             G.vertices[i].firstarc = NULL;
         }
    
         for(k = 0; k < G.arcnum; k ++)
         {
             printf("请输入弧尾和弧头：");
             scanf("%d%d", &va, &vb);
    
             i = LocateVex(G, va);
             j = LocateVex(G, vb);
    
             p = (ArcNode *)malloc(sizeof(ArcNode));
             p->adjvex = j;
             p->info = NULL;
    
             p->nextarc = G.vertices[i].firstarc;
             G.vertices[i].firstarc = p;
    
             /*对称*/
             p = (ArcNode *)malloc(sizeof(ArcNode));
             p->adjvex = i;
             p->info = NULL;
    
             p->nextarc = G.vertices[j].firstarc;
             G.vertices[j].firstarc = p;
         }
    
    }
    
    void CreateUDN(ALGraph &G)
    {
         int i, j, k;
         VertexType va, vb, weight;
    
         ArcNode *p;
    
         printf("请输入图的顶点和弧的个数：");
         scanf("%d%d",&G.vexnum, &G.arcnum);
    
         printf("请输入顶点的值：");
         for(i = 0; i < G.vexnum; i ++)
         {
             scanf("%d", &G.vertices[i].data);
    
             G.vertices[i].firstarc = NULL;
         }
    
         for(k = 0; k < G.arcnum; k ++)
         {
             printf("请输入弧尾、弧头和权值：");
             scanf("%d%d%d", &va, &vb, &weight);
    
             i = LocateVex(G, va);
             j = LocateVex(G, vb);
    
             p = (ArcNode *)malloc(sizeof(ArcNode));
             p->adjvex = j;
    
             p->info = (InfoType *)malloc(sizeof(InfoType));
             *(p->info) = weight;
    
             p->nextarc = G.vertices[i].firstarc;
             G.vertices[i].firstarc = p;
    
             /*对称*/
             p = (ArcNode *)malloc(sizeof(ArcNode));
             p->adjvex = i;
    
             p->info = (InfoType *)malloc(sizeof(InfoType));
             *(p->info) = weight;
    
             p->nextarc = G.vertices[j].firstarc;
             G.vertices[j].firstarc = p;
         }
    }
    
     int CreateGraph(ALGraph &G)
    {
        printf("请输入您要创造的图的类型：");
        scanf("%d",&G.kind);
    
        switch(G.kind)
        {
            case 1: CreateDG(G);  break;
    
            case 2: CreateDN(G);  break;
    
            case 3: CreateUDG(G);  break;
    
            case 4: CreateUDN(G);  break;
    
            default : printf("ERROR");
        }
    
        return 0;
    }
    
    int FirstAdjVex(ALGraph G, VertexType v)
    {
       ArcNode *p;
    
       p = G.vertices[v].firstarc;  //p是该点的第一个邻接点
    
       //如果p存在，返回p点的下标
       if(p)
       {
           return p->adjvex;
       }
       else
       {
            return -1;
       }
     }
    
     int NextAdjVex(ALGraph G, VertexType v, VertexType w)
     {
       ArcNode *p;
    
       p = G.vertices[v].firstarc;
    
       //当p存在且没有被访问过，访问下一个顶点
       while(p && p->adjvex != w)
       {
           p = p->nextarc;
       }
    
       if(!p || !p->nextarc)
       {
            return -1;
       }
       else
       {
           return p->nextarc->adjvex;
       }
     }
    
     Boolean visited[MAX_VERTEX_NUM];
    
     void visit(ALGraph G, int v)
     {
         printf("%d ", G.vertices[v].data);
     }
    
    void DFS(ALGraph G, int v)
    {
       visited[v] = TRUE;
       visit(G, v);
    
       for(int w = FirstAdjVex(G,v); w >= 0; w = NextAdjVex(G, v, w))
       {
           if(!visited[w])
              DFS(G,w);
       }
    }
    
    void DFSTraverse(ALGraph G)
    {
       int v;
    
       for(v = 0; v < G.vexnum; v ++)
       {
           visited[v] = FALSE;
       }
    
       for(v = 0; v < G.vexnum; v ++)
       {
           if(!visited[v])
           DFS(G,v);
       }
    }
    
    int main()
    {
        ALGraph G;
        CreateGraph(G);
    
        DFSTraverse(G);
        return 0;
    }
    ```c
/*----------邻接表------------*/

#include<stdio.h>
#include<malloc.h>

#define MAX_VERTEX_NUM 20
#define InfoType int
#define VertexType int
#define Boolean int

#define FALSE 0
#define TRUE 1

/*点与点之间的关系,换句话说，就是顶点与下一个顶点之间的关系*/
typedef struct ArcNode{
   int adjvex;   //该弧所指向的顶点的位置
   struct ArcNode *nextarc;   //指向下一条弧的指针
   InfoType *info;    //该弧的相关信息的指针（例如，权值）
}ArcNode;

/*顶点的信息，也就是说这条弧的第一个点*/
typedef struct{
   VertexType data;    //顶点信息
   ArcNode *firstarc;   //指向第一条依附该顶点的弧的指针
}VNode, AdjList[MAX_VERTEX_NUM];

/*该图的总的信息*/
typedef struct
{
   AdjList vertices;   //存顶点值的数组
   int vexnum,arcnum;   //图的当前顶点数和弧数
   int kind;    //图的种类标志
}ALGraph;

/*老朋友了，查找并定位*/
 int LocateVex(ALGraph G, VertexType u)
 {
   for(int i = 0; i < G.vexnum; ++ i)
   {
       if(G.vertices[i].data == u)
          return i;   //返回下标
   }
   return -1;
 }

/*有向图*/
 void CreateDG(ALGraph &G)
 {
     int i, j, k;
     VertexType va, vb; //弧头弧尾

printf("请输入图的顶点和弧的个数：");
     scanf("%d%d",&G.vexnum, &G.arcnum);

printf("请输入顶点的值：");
     for(i = 0; i < G.vexnum; i ++)
     {
         scanf("%d", &G.vertices[i].data);

G.vertices[i].firstarc = NULL;
     }

/*头插法*/
     ArcNode *p;//顶点指针
     for(k = 0; k < G.arcnum; k ++)
     {
         printf("请输入弧尾和弧头：");
         scanf("%d%d", &va, &vb);

i = LocateVex(G, va);  //弧尾在顶点数组中的下标
         j = LocateVex(G, vb);  //弧头在顶点数组中的下标

p = (ArcNode *)malloc(sizeof(ArcNode));  //动态分配内存（来一个我开一个）
         p->adjvex = j;  //顶点下标为j
         p->info = NULL;  //图是没有权值的，所以设为空

p->nextarc = G.vertices[i].firstarc;  //这个顶点的下一个指向的地址是他的第一个邻接点
         G.vertices[i].firstarc = p;  //开始创建这个点的第一个邻接点
     }

}

void CreateDN(ALGraph &G)
{
     int i, j, k;
     VertexType va, vb, weight;

ArcNode *p;

printf("请输入图的顶点和弧的个数：");
     scanf("%d%d",&G.vexnum, &G.arcnum);

printf("请输入顶点的值：");
     for(i = 0; i < G.vexnum; i ++)
     {
         scanf("%d", &G.vertices[i].data);

G.vertices[i].firstarc = NULL;
     }

for(k = 0; k < G.arcnum; k ++)
     {
         printf("请输入弧尾、弧头和权值：");
         scanf("%d%d%d", &va, &vb, &weight);

i = LocateVex(G, va);
         j = LocateVex(G, vb);

p = (ArcNode *)malloc(sizeof(ArcNode));
         p->adjvex = j;

p->info = (InfoType *)malloc(sizeof(InfoType));
         *(p->info) = weight;

p->nextarc = G.vertices[i].firstarc;
         G.vertices[i].firstarc = p;
     }
}

void CreateUDG(ALGraph &G)
{
     int i, j, k;
     VertexType va, vb;

ArcNode *p;

printf("请输入图的顶点和弧的个数：");
     scanf("%d%d",&G.vexnum, &G.arcnum);

printf("请输入顶点的值：");
     for(i = 0; i < G.vexnum; i ++)
     {
         scanf("%d", &G.vertices[i].data);

G.vertices[i].firstarc = NULL;
     }

for(k = 0; k < G.arcnum; k ++)
     {
         printf("请输入弧尾和弧头：");
         scanf("%d%d", &va, &vb);

i = LocateVex(G, va);
         j = LocateVex(G, vb);

p = (ArcNode *)malloc(sizeof(ArcNode));
         p->adjvex = j;
         p->info = NULL;

p->nextarc = G.vertices[i].firstarc;
         G.vertices[i].firstarc = p;

/*对称*/
         p = (ArcNode *)malloc(sizeof(ArcNode));
         p->adjvex = i;
         p->info = NULL;

p->nextarc = G.vertices[j].firstarc;
         G.vertices[j].firstarc = p;
     }

}

void CreateUDN(ALGraph &G)
{
     int i, j, k;
     VertexType va, vb, weight;

ArcNode *p;

printf("请输入图的顶点和弧的个数：");
     scanf("%d%d",&G.vexnum, &G.arcnum);

printf("请输入顶点的值：");
     for(i = 0; i < G.vexnum; i ++)
     {
         scanf("%d", &G.vertices[i].data);

G.vertices[i].firstarc = NULL;
     }

for(k = 0; k < G.arcnum; k ++)
     {
         printf("请输入弧尾、弧头和权值：");
         scanf("%d%d%d", &va, &vb, &weight);

i = LocateVex(G, va);
         j = LocateVex(G, vb);

p = (ArcNode *)malloc(sizeof(ArcNode));
         p->adjvex = j;

p->info = (InfoType *)malloc(sizeof(InfoType));
         *(p->info) = weight;

p->nextarc = G.vertices[i].firstarc;
         G.vertices[i].firstarc = p;

/*对称*/
         p = (ArcNode *)malloc(sizeof(ArcNode));
         p->adjvex = i;

p->info = (InfoType *)malloc(sizeof(InfoType));
         *(p->info) = weight;

p->nextarc = G.vertices[j].firstarc;
         G.vertices[j].firstarc = p;
     }
}

int CreateGraph(ALGraph &G)
{
    printf("请输入您要创造的图的类型：");
    scanf("%d",&G.kind);

switch(G.kind)
    {
        case 1: CreateDG(G);  break;

case 2: CreateDN(G);  break;

case 3: CreateUDG(G);  break;

case 4: CreateUDN(G);  break;

default : printf("ERROR");
    }

return 0;
}

int FirstAdjVex(ALGraph G, VertexType v)
{
   ArcNode *p;

p = G.vertices[v].firstarc;  //p是该点的第一个邻接点

//如果p存在，返回p点的下标
   if(p)
   {
       return p->adjvex;
   }
   else
   {
        return -1;
   }
 }

int NextAdjVex(ALGraph G, VertexType v, VertexType w)
 {
   ArcNode *p;

p = G.vertices[v].firstarc;

//当p存在且没有被访问过，访问下一个顶点
   while(p && p->adjvex != w)
   {
       p = p->nextarc;
   }

if(!p || !p->nextarc)
   {
        return -1;
   }
   else
   {
       return p->nextarc->adjvex;
   }
 }

Boolean visited[MAX_VERTEX_NUM];

void visit(ALGraph G, int v)
 {
     printf("%d ", G.vertices[v].data);
 }

void DFS(ALGraph G, int v)
{
   visited[v] = TRUE;
   visit(G, v);

for(int w = FirstAdjVex(G,v); w >= 0; w = NextAdjVex(G, v, w))
   {
       if(!visited[w])
          DFS(G,w);
   }
}

void DFSTraverse(ALGraph G)
{
   int v;

for(v = 0; v < G.vexnum; v ++)
   {
       visited[v] = FALSE;
   }

for(v = 0; v < G.vexnum; v ++)
   {
       if(!visited[v])
       DFS(G,v);
   }
}

int main()
{
    ALGraph G;
    CreateGraph(G);

DFSTraverse(G);
    return 0;
}

````

**请不要在编辑框中直接粘贴代码，请使用代码块。**
- #### 代码块
![](/image_editor_upload/20190606022155_81717.png)
![](/image_editor_upload/20190606024121_61585.png)

**点击图标“代码块（多语言风格）”，即可在其中输入想要插入的代码。**

*输入与预览图例：*
	![](/image_editor_upload/20190606022918_54401.png)

**如上图代码块的开头与结尾都有三个间隔号（键盘左上角Esc下方按键），开头三个间隔号后的“c”即为代码语言。下面是一个例子：**

```c
	#include<stdio.h>
	int main()
	{
		int a,b;
		while(~scanf("%d%d", &a, &b))printf("%d\n",a+b);
		return 0;
	}
	```

- #### 行内代码
![](/image_editor_upload/20190606040412_74577.png)

**请点击“行内代码”按钮，再输入代码。**

*输入与预览图例：*
	![](/image_editor_upload/20190606040626_28452.png)

**如上图，与代码块不同，行内代码开头和结尾只有一个间隔号。下面是一个例子：**

`#include<stdio.h>`的作用是引入头文件！

## 标题样式

**标题支持6种样式，可点击H1~H6按钮变更标题样式；**

![](/image_editor_upload/20190606013846_99194.png)

**也可以直接输入“#”来编辑，“#”对应H1,“##”对应H2……**

*输入与预览图例：*
![](/image_editor_upload/20190606014119_69661.png)

## 文字样式

![](/image_editor_upload/20190606014703_35680.png)

**可点击按钮变更样式，或直接输入标记语法。**

*输入与预览图例：*
![](/image_editor_upload/20190606021227_16757.png)

**如上图中直接输入标记语法符号也可以达到想要的效果。下面是几个例子：**

*强调文本* _强调文本_
**加粗文本** __加粗文本__
　　==标记文本==
~~删除文本~~
> 引用文本

## 插入图片

![](/image_editor_upload/20190606023726_46319.png)

**点击“添加图片”按钮即可插入想要的图片，但上传有大小限制，图片如果过大请修改本地图片属性后再上传。**

## 插入表格

![](/image_editor_upload/20190606024844_48835.png)

**点击“添加表格”，填写一些基本属性，点击确定得到下图结果：**

![](/image_editor_upload/20190606025647_67742.png)

**在左边输入框中填入一些信息，即可完成表格：**

*输入与预览图例：*
![](/image_editor_upload/20190606025824_42776.png)

**你可以在左边输入框中任意增减图例中的竖线符号来调整表格格式。下面是一个例子：**

| 内容板块 | 大纲内容 | 学习目标 | …… |
| ------------ | ------------ |
| 标准语法 | 标准C语言全语法 | 熟练掌握C语言标准语法 |
| 实验与探究 | C语言特性  | 理解C语言底层原理 | 其他内容 |

## 列表

![](/image_editor_upload/20190606032543_63651.png)

**编辑一个列表，点击图标“无须列表”或“有序列表”，即可编辑内容，编辑好后按回车键，再次点击列表按钮开始编辑下一条。**

*输入与预览图例：*
![](/image_editor_upload/20190606033831_52890.png)

**你可以如上图中根据需求灵活使用其他标记语法与Tab键，改变文字样式与格式。下面是一个例子：**

- #### C语言快速入门

1. C语言第一个简单实例
	1. 实例说明

- **C语言的数据类型**

- 变量与常量数据
	- 数据类型和关键字
	- 本章总结与作业

## 科学公式 TeX(KaTeX)

**请在编辑器的预编辑内容中查看公式语法示例**

$$E=mc^2$$

行内的公式$$E=mc^2$$行内的公式。

$$x > y$$

$$$\sqrt{3x-1}+(1+x)^2$$$

$$\sin(\alpha)^{\theta}=\sum_{i=0}^{n}(x^i + \cos(f))$$

多行公式：

```math
\displaystyle
\left( \sum\_{k=1}^n a\_k b\_k \right)^2
\leq
\left( \sum\_{k=1}^n a\_k^2 \right)
\left( \sum\_{k=1}^n b\_k^2 \right)
```

```katex
\displaystyle
    \frac{1}{
        \Bigl(\sqrt{\phi \sqrt{5}}-\phi\Bigr) e^{
        \frac25 \pi}} = 1+\frac{e^{-2\pi}} {1+\frac{e^{-4\pi}} {
        1+\frac{e^{-6\pi}}
        {1+\frac{e^{-8\pi}}
         {1+\cdots} }
        }
    }
```

```latex
f(x) = \int_{-\infty}^\infty
    \hat f(\xi)\,e^{2 \pi i \xi x}
    \,d\xi
```

## 关于空格

**想要给一段文字添加多个　*空格符*　？**

**　　如果一定要输入多个连续空格符，可以切换输入法至全角输入（默认半角），然后再输入空格；**

------------

### 来试试编辑一篇文章吧，祝您使用愉快！

0.0分

1 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

qingtian

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

【数组的距离】（C语言代码）

母牛的故事（C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

上车人数（C语言代码）

图邻接表创建

评论区

精彩推荐

【偶数求和】（C语言代码）

兰顿蚂蚁（C++代码）

【简单计算】（C语言代码）

printf基础练习2 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

【矩阵】（C++代码）

C语言考试练习题_保留字母（C语言代码）

Hello, world! （C语言代码）

字符串输入输出函数（C语言代码）

qingtian

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

【数组的距离】 （C语言代码）

母牛的故事 （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

上车人数 （C语言代码）

图邻接表创建

评论区

精彩推荐

【偶数求和】 （C语言代码）

兰顿蚂蚁 （C++代码）

【简单计算】 （C语言代码）

printf基础练习2 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

【矩阵】 （C++代码）

C语言考试练习题_保留字母 （C语言代码）

Hello, world! （C语言代码）

字符串输入输出函数 （C语言代码）

【数组的距离】（C语言代码）

母牛的故事（C语言代码）

上车人数（C语言代码）

　　评论区

【偶数求和】（C语言代码）

兰顿蚂蚁（C++代码）

【简单计算】（C语言代码）

【矩阵】（C++代码）

C语言考试练习题_保留字母（C语言代码）

字符串输入输出函数（C语言代码）