1. /*
    2.     采用邻接表的方式存储图
    3.     分析：
    4.         采用邻接表相对于邻接矩阵来说更节省存储空间，这里我们需要两个数据结构：
    5.         ①顶点表结构：包括顶点信息及指向第一个邻接点的头指针
    6.         ②边表结构：包括该邻接点域（在数组中的下标）、权值及下一个邻接点指针
    7.         ③一个数组，用于存储所有顶点，因为数组的随机存储特性，方便我们查找
    8.         ④图结构：包括顶点数组及顶点数、边数
    9.         具体创建流程：
    10.                 首先我们需要输入图的顶点数和边数，将其存入图结构中，并由输入的顶点数依次输入顶点信息，并将第一个邻接点的头指针
    11.             置位NULL，这是建立顶点表的流程；
    12.                 其次我们需要建立边表，根据输入的边个数，依次输入边（vi，vj）的顶点序号，再采取头插法进行插入，若是无向图则需要
    13.             重复反向依次设置，至此，图的邻接表结构建立完成。
    15. */
    16. #define _CRT_SECURE_NO_WARNINGS
    17. #define MAXSIZE 100
    18. #define TYPE int
    19. typedef struct EdgeNode {//边表结点
    20.     int index;//该边所指向的顶点的位置,在顶点数组里面的位置信息
    21.     int weight;//权值
    22.     EdgeNode *next;//下一个邻接边
    23. }EdgeNode;
    25. typedef struct VertexNode {//顶点表节点
    26.     TYPE info;//顶点信息
    27.     EdgeNode *firstEdge;//指向第一条依附该顶点的边的指针
    28. }VertexNode, Adjlist[MAXSIZE];
    30. typedef struct {
    31.     Adjlist adjlist;//顶点数组
    32.     int numE, numV;//边数、顶点数
    33. }ALGraph;
    34. #include <stdio.h>
    35. #include <stdlib.h>
    37. void createGraph(ALGraph *G) {
    38.     int e, v, vi, vj, w;
    39.     printf("请输入图的边数与结点数（以空格分开）：");
    40.     scanf("\n%d %d", &e, &v);
    41.     G->numE = e;
    42.     G->numV = v;
    43.     printf("请依次输入顶点信息：\n");
    44.     for (int i = 0; i < G->numV; i++) {
    45.         printf("请输入第%d个结点信息：", i + 1);
    46.         scanf("\n%c", &G->adjlist[i].info);
    47.         G->adjlist[i].firstEdge = NULL;
    48.         //G->adjlist[i].firstEdge->index = -1;
    49.     }
    51.     printf("请输入边表信息：\n");
    52.     for (int i = 0; i < G->numE; i++) {
    53.         printf("请输入边（vi，vj）的顶点序号及其权值（以空格分开）：");
    54.         scanf("%d %d %d", &vi, &vj, &w);
    55.         //若是无向图则需要两个顶点进行操作,采用头插法
    56.         EdgeNode *e = (EdgeNode *)malloc(sizeof(EdgeNode *));
    57.         e->index = vj - 1;//数组下标要减一
    58.         e->weight = w;
    59.         e->next = G->adjlist[vi - 1].firstEdge;
    60.         G->adjlist[vi - 1].firstEdge = e;
    62.         /*EdgeNode *ed = (EdgeNode *)malloc(sizeof(EdgeNode *));
    63.         ed->index = vi - 1;
    64.         ed->weight = w;
    65.         ed->next = G->adjlist[vj - 1].firstEdge;
    66.         G->adjlist[vj - 1].firstEdge = ed;*/
    67.     }
    69. }
    70. void createGraphInFile(ALGraph *G) {//从文件中读取我们的图的数据，包括边数，节点数，对应关系
    71.     FILE *fp;//创建文件指针
    72.     char ev[4] = {};
    73.     char numE[3] = { 0 };//顶点，边个数信息
    74.     char numV[3] = { 0 };//顶点，边个数信息
    75.     char arc[6] = { 0 };//边信息
    76.     char *vertex;//顶点信息，名称
    77.     fp = fopen("graph.txt", "r");//打开文件
    78.     if (fp == NULL) {
    79.         printf("该文件无法打开！");
    80.         return;
    81.     }
    82.     fscanf(fp, "%hu %hu", numE, numV);//读取第一行
    83.     G->numE = numE[0];
    84.     G->numV = numV[0];
    85.     vertex = (char *)malloc(sizeof(char*)*G->numV);//这是用来存储顶点信息的数组（顶点的名字）
    86.     for (int i = 0; i <= G->numE; i++) {//开始获取后面的信息
    87.         if (i == 0) {//此时，根据我们文件的结构，第二行是顶点信息
    88.             fgets(ev, 4, fp);//获取回车符，上一次fgets后会停在回车符那儿
    89.             fgets(vertex,G->numV*2,fp);//这里获取顶点信息
    90.             int w = 0;//用一个计数器，保证adjlist依次存储顶点
    91.             for (int j = 0; j < G->numV*2;j++) {//因为有空格，所以让j<G->numV*2
    92.                 if (vertex[j]==32) {//是空格，不进行操作
    93.                     continue;
    94.                 }
    95.                 else {//开始赋值
    96.                     G->adjlist[w].info = vertex[j];
    97.                     G->adjlist[w].firstEdge = NULL;
    98.                     w++;
    99.                 }
    100.             }
    101.         }
    102.         else {//开始依次存储边信息
    103.             fgets(ev, 4, fp);//同样先吃掉换行符
    104.             fgets(arc, 6, fp);//读取该行的边信息
    105.             EdgeNode *e = (EdgeNode *)malloc(sizeof(struct EdgeNode ));
    106.             e->index = atoi(&arc[2]) - 1;//数组下标要减一
    107.             e->weight = atoi(&arc[4]);
    108.             e->next = G->adjlist[atoi(&arc[0])-1].firstEdge;//采用头插法
    109.             G->adjlist[atoi(&arc[0])-1].firstEdge = e;
    111.             //下面与上面相似，目的在于构建无向图
    112.             //EdgeNode *otherE = (EdgeNode *)malloc(sizeof(struct EdgeNode ));
    113.             //otherE->index = atoi(&arc[0]) - 1;//数组下标要减一
    114.             //otherE->weight = atoi(&arc[4]);
    115.             //otherE->next = G->adjlist[atoi(&arc[2]) - 1].firstEdge;
    116.             //G->adjlist[atoi(&arc[2]) - 1].firstEdge = otherE;
    117.         }
    119.     }
    120.     fclose(fp);
    121. }
    122. void dispGraph(ALGraph *G) {//将图用邻接表的形式展示出来
    123.     for (int i = 0; i < G->numV; i++) {
    124.         int j = i;
    125.         printf("%c-->", G->adjlist[j].info);
    126.         EdgeNode *p = G->adjlist[j].firstEdge;
    127.         while (p) {
    128.             printf("(%d)%c-->", p->weight, G->adjlist[p->index].info);
    129.             p = p->next;
    130.         }
    131.         printf("^\n");
    132.     }
    134. }
    135. //int main() {
    136. //    ALGraph G;
    137. //    createGraphInFile(&G);
    138. //    dispGraph(&G);
    139. //    return 0;
    140. //}