邻接矩阵的简易实现 C语言

布满荆棘的人生 2022-12-03 08:48 125阅读 0赞

主函数

#include <stdio.h>
    #include <stdlib.h>
    
    #include "AdjMatrix.h"
    //!
    int main()
    {
        
        /*
        if (freopen("D:\\y.txt","r",stdin)==NULL)
    
    		printf("打开文件失败！\n");
        */
        if(freopen("data.txt","r",stdin)==NULL)
        {
        
            printf("File open error!\n");
        }
        else
        {
        
            printf("File open success!\n");
            /*
            //test stdin
            int n,data,i;
            scanf("%d",&n);
            for(i=0;i<n;i++)
            {
                scanf("%d",&data);
                printf("%d ",data);
            }
            */
    
            AdjMatrix G;
            G.kind=UDN;
            printf("Graph kind: %d\n",G.kind);
            if(CreateUDN(&G)==1)
            {
        
                printf("CreateUDN success!\n");
                show(&G);
            }
    
    
        }
        fclose(stdin);
        printf("Hello world!\n");
        return 0;
    }

头文件

#define MAX_VERTEX_NUM 20
    #define INFINITY 0x7fffffff
    
    typedef enum{
        DG,DN,UDG,UDN} GraphKind;
    typedef int VertexData;
    typedef int AdjType;
    
    typedef struct ArcNode
    {
        
        AdjType adj;
        //OtherInfo info;
    }ArcNode;
    
    typedef struct
    {
        
        VertexData vertex[MAX_VERTEX_NUM];
        ArcNode arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
        int vexnum,arcnum;
        GraphKind kind;
    }AdjMatrix;
    
    int LocateVertex(AdjMatrix *G,VertexData v)
    {
        
        int j=-1,k;
        for(k=0;k<G->vexnum;++k)
        {
        
            if(G->vertex[k]==v)
            {
        
                j=k;
                break;
            }
        }
        return(j);
    }
    
    int CreateUDN(AdjMatrix *G)
    {
        
        int i,j,k,weight;
        VertexData v1,v2;
        scanf("%d %d",&G->vexnum,&G->arcnum);
        for(i=0;i<G->vexnum;++i)
        {
        
            for(j=0;j<G->vexnum;++j)
            {
        
                G->arcs[i][j].adj=INFINITY;
            }
        }
    
        for(i=0;i<G->vexnum;++i)
        {
        
            scanf("%d",&G->vertex[i]);
        }
    
        for(k=0;k<G->arcnum;++k)
        {
        
            scanf("%d %d %d",&v1,&v2,&weight);
            i=LocateVertex(G,v1);
            if(i==-1)
            {
        
                printf("error index!\n");
                break;
            }
            j=LocateVertex(G,v2);
            if(j==-1)
            {
        
                printf("error index!\n");
                break;
            }
            G->arcs[i][j].adj=weight;
            G->arcs[j][i].adj=weight;
        }
    
        return 1;
    }
    
    void show(AdjMatrix *G)
    {
        
        printf("vexnum: %d\n",G->vexnum);
        printf("arcnum: %d\n",G->arcnum);
        printf("vertex: ");
        int i;
        for(i=0;i<G->vexnum;++i)
        {
        
            printf("%d ",G->vertex[i]);
        }
        printf("\n");
        int j;
        for(i=0;i<G->vexnum;++i)
        {
        
            // 无向图，一条边只需输出一次 j=i,避免重复
            for(j=i;j<G->vexnum;++j)
            {
        
                if(G->arcs[i][j].adj!=INFINITY)
                {
        
                    printf("i:%d j:%d cost:%d\n",i+1,j+1,G->arcs[i][j].adj);
                }
            }
        }
    }