数据结构-图的邻接表

r囧r小猫 2022-04-03 15:54 232阅读 0赞

typedef struct Path         //定义边表节点
    {
        int placeNum;          //存储顶点下标
        int distance;          //权重值
        struct Path* next;     //边指针
    } Path;
    
    typedef struct Place   /*顶点表节点*/
    {
        string data; //顶点存的数据
        Path* head; //指向一个邻接点链表（即边表）
    } Place,PlaceList[MAXVEX];
    
    typedef struct
    {
        PlaceList PlaceList;
        int numVertexes,numEdges;
    } Graph;

## 例如下面的图 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE0NjM3OTQ_size_16_color_FFFFFF_t_70]

## 利用邻接表表示（以0这个点为例） ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE0NjM3OTQ_size_16_color_FFFFFF_t_70 1]

## 图的PlaceList数组存了图中五个节点 ##

## 0的节点跟1,2,3节点是相连的，所以他的邻接点链表（也就是边链表）有三个有值节点，分别表示1,2,3这三个点以及他们与0点的距离 ##

# 可以根据下面这个例子理解一下 #

## 这个例子是输入各地点以及相连的距离，可以把图存入文件 ##

#include<iostream>
    #include<stdio.h>
    #include<stdlib.h>
    #define MAXVEX 100
    #define true 1
    
    using namespace std;
    
    
    typedef struct Path         //定义边表节点
    {
        int placeNum;           //存储顶点下标
        int distance;           //权重值
        struct Path* next;      //边指针
    } Path;
    
    typedef struct Place   /*顶点表节点*/
    {
        string introduce;
        string data;
        Path* head;
    } Place,PlaceList[MAXVEX];
    
    typedef struct
    {
        PlaceList PlaceList;
        int numVertexes,numEdges;
    } Graph;
    
    
    void CreatGraph(Graph *g)
    {
        int i,j,k;
        int distance;
        Path *e,*e2;
        cout<<"输入图的顶点数与边数："<<endl;
        cin>> g->numVertexes>> g->numEdges;
        string name;
        //gettchar();
        for(i=0; i<g->numVertexes; i++)
        {
            cout<<"第"<<i+1<<"个地点名称"<<endl;
            cin>>g->PlaceList[i].data;            //获取顶点值，
            g->PlaceList[i].head = NULL;    //将边表置为空
        }
        cout<<"回车进入边的输入"<<endl;
        getchar();
        getchar();
        system("cls");
    
        for(i=0; i<g->numVertexes; i++)
        {
            cout<<"编号："<<i<<" 地点："<<g->PlaceList[i].data<<endl;
        }
    
        for(k=0; k<g->numEdges; k++)
        {
            cout<<"输入边(两个顶点)及权值"<<endl;
            cin>>i>>j>>distance;           //输入i,j 在图中有i--j
            e=(Path*)malloc(sizeof(Path));
            e->placeNum = j;
            e->distance = distance;
            e->next = g->PlaceList[i].head;   //头插法建立边表
            g->PlaceList[i].head= e;
    
            e2=(Path*)malloc(sizeof(Path));
            e2->placeNum = i;
            e2->distance = distance;
            e2->next = g->PlaceList[j].head;
            g->PlaceList[j].head= e2;
    
        }
    }
    
    void writeToFile(Graph g)//如果想涉及把图存入文件，可以留着此函数
    {
        FILE *fw = fopen("place.txt","w+");
        int i;
        for(i=0; i<g.numVertexes; i++)
        {
    
            char  num[100];
            itoa(i,num,10);
            char *data =(char*) g.PlaceList[i].data.data();
            fprintf(fw,num);
            fprintf(fw,"\t");
            fprintf(fw,data);
            fprintf(fw,"\t");//结束写点信息
            //开始写边
            Path* current = g.PlaceList[i].head;
            if(current==NULL)
            {
                fprintf(fw,"\n");
            }
            else
            {
                while(current!=NULL)
                {
                    char placeNum[100];
                    itoa(current->placeNum,placeNum,10);
                    char distance[100];
                    itoa(current->distance,distance,10);
                    fprintf(fw,placeNum);
                    fprintf(fw,"\t");
                    fprintf(fw,distance);
                    fprintf(fw,"\t");
                    current = current->next;
                }
                fprintf(fw,"\n");
    
            }
        }
        fclose(fw);
        cout<<"写出成功！"<<endl;
    }
    
    void showPath(Graph g)
    {
        Path* current;
    
        for(int j=0; j<g.numVertexes; j++)
        {
            if(g.PlaceList[j].head==NULL)
            {
                break;
            }
            else
            {
                current = g.PlaceList[j].head;
                while(current!=NULL)
                {
                    cout<<g.PlaceList[j].data<<"----"<<g.PlaceList[current->placeNum].data<<": "<<current->distance<<endl;
                    current = current->next;
                }
            }
        }
    }
    
    void showPlace(Graph g)
    {
        for(int i=0; i<g.numVertexes; i++)
        {
            cout<<"第"<<i+1<<"个地点名称:"<<g.PlaceList[i].data<<endl;
        }
    }
    
    int main()
    {
        Graph g;
        int num = 0;
        do
        {
            cout<<"*************************************\n";
            cout<<"*              菜单                 *\n";
            cout<<"*          1.显示地点               *\n";
            cout<<"*          2.显示路径               *\n";
            cout<<"*          3.写入文件               *\n";
            cout<<"*          4.初始化图               *\n";
            cout<<"*          5.退出                   *\n";
            cout<<"*************************************\n";
            cin>>num;
            {
                switch(num)
                {
                case 1:
                {
                    showPlace(g);
                    break;
                }
                case 2:
                {
                    showPath(g);
                    break;
    
                }
                case 3:
                {
                    writeToFile(g);
                    break;
                }
                case 4:
                {
                    CreatGraph(&g);
                    break;
                }
                default:
                    break;
                }
            }
            cout<<"按回车继续....";
            getchar();
            getchar();
            system("cls");
        }
        while(1 == num|| 2 == num || 3 == num ||4 == num);
    
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE0NjM3OTQ_size_16_color_FFFFFF_t_70]: /images/20220403/76a04a79172b4e6a9312ffadb998fd00.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTE0NjM3OTQ_size_16_color_FFFFFF_t_70 1]: /images/20220403/ff21fa64bd78411889e48cae841f4aca.png