数据结构自用

guhusf

#include<stdlib.h>
#include<stdio.h>
#define MAX 20

typedef struct
{
        int vexs[MAX];
        int arcs[MAX][MAX];
        int len,ArcNum,VexNum;
}NetGraph;

void buigra(NetGraph *G)
{
        int i,j,k,s;
        printf("请输入结点数和边数:");
        scanf("%d %d",&G->VexNum,&G->ArcNum);
        printf("请输入结点:\n");
        for(i=0;i<G->VexNum;i++)
        {
                scanf("%d",&G->vexs[i]);
        }
        printf("请输入边两端和权值:\n");
        for(i=0;i<G->VexNum;i++)
        {
                for(j=0;j<G->VexNum;j++)
                {
                        G->arcs[i][j] = 0;
                }
        }
        for(k=0;k<G->ArcNum;k++)
        {
                scanf("%d %d %d",&i,&j,&s);
                G->arcs[i-1][j-1] = s;
                G->arcs[j-1][i-1] = s;
        }
}

void disng(NetGraph G)
{
        int i,j;
        printf("%*s",2," ");
        for(i=0;i<G.VexNum;i++)
        {
                printf("%d ",G.vexs[i]);
        }
        printf("\n");
        for(i=0;i<G.VexNum;i++)
        {
                printf("%d ",G.vexs[i]);
                for(j=0;j<G.VexNum;j++)
                {
                        printf("%d ",G.arcs[i][j]);
                }
                printf("\n");
        }
}

void sholen(NetGraph G)
{
        int i, j, k=0, si, sj;
        for(i=0;i<G.VexNum;i++)
                for(j=0;j<G.VexNum;j++)
                {
                        if(G.arcs[i][j]!=0 && k==0)
                        {
                                k = G.arcs[i][j];
                                si = G.vexs[i];
                                sj = G.vexs[j];
                        }
                        else if(G.arcs[i][j]!=0 && G.arcs[i][j]<k)
                        {
                                k = G.arcs[i][j];
                                si = G.vexs[i];
                                sj = G.vexs[j];
                        }
                }
                printf("最短的边是%d---%d",si,sj);
}

void insertarc(NetGraph *G)
{
        int i, j, s;
        printf("请输入插入的边两端和权值:\n");
        scanf("%d %d %d",&i,&j,&s);
        G->arcs[i-1][j-1] = s;
        G->arcs[j-1][i-1] = s;
        printf("Finished!");
}

void delarc(NetGraph *G)
{
        int i, j;
        printf("请输入要删除的边:\n");
        scanf("%d %d",&i,&j);
        G->arcs[i-1][j-1] = 0;
        G->arcs[j-1][i-1] = 0;
        printf("Finished!");
}

void getdu(NetGraph G)
{
        int i,j,n;
        for(i=0;i<G.VexNum;i++)
        {
                n = 0;
                for(j=0;j<G.VexNum;j++)
                {
                        if(G.arcs[i][j]!=0)
                                n++;
                }
                printf("第%d个结点的度是%d\n",i+1,n);
        }
}

void arrive(NetGraph G,int v,int key,int *flag,int visited[])
{
        int i;
        if(G.vexs[v]==key)
        {
                printf("Yes!");
                *flag = 1;
                return;
        }
        visited[v] = 1;
        for(i=0;i<G.VexNum;i++)
        {
                if(G.arcs[v][i]!=0 && visited[i]==0)
                        arrive(G,i,key,flag,visited);
        }
}

int menu()
{
        int n;
        while(1)
        {
                system("cls");
                printf("1.创建\t\t2.输出\t\t3.最短边\n");
                printf("4.插入边\t5.删除边\t6.求度\n");
                printf("7.可达性\t8.退出\n");
                printf("请选择功能:");
                scanf("%d",&n);
                return n;
        }
}

void main()
{
        NetGraph G;
        int n;
        while(1)
        {
                n = menu();
                switch(n)
                {
                case 1:{
                        buigra(&G);
                        system("pause");
                        getchar();
                        break;
                           }
                case 2:{
                        disng(G);
                        system("pause");
                        getchar();
                        break;
                           }
                case 3:{
                        sholen(G);
                        system("pause");
                        getchar();
                        break;
                           }
                case 4:{
                        insertarc(&G);
                        system("pause");
                        getchar();
                        break;
                           }
                case 5:{
                        delarc(&G);
                        system("pause");
                        getchar();
                        break;
                           }
                case 6:{
                        getdu(G);
                        system("pause");
                        getchar();
                        break;
                           }
                case 7:{
                        int key,v,flag=0,visited[MAX]={0};
                        printf("请输入两个点:");
                        scanf("%d %d",&v,&key);
                        arrive(G,v,key,&flag,visited);
                        if(flag == 0) printf("NO!");
                        system("pause");
                        getchar();
                        break;
                           }
                case 8:{
                        exit(0);
                           }
                }
        }
}