算法导论 练习22.1-5算法的实现

针对邻接矩阵的算法的实现：

GtoG2M.c:

/*
* filename : GtoG2M.c
* author : Jesse
* update : 2011/08/15
*/

#include <stdio.h>

void GtoG2(int G[5][5], int G2[5][5], int V)
{
    int r, c, c1;
    for(r = 0; r < V; r++)
    {
        for(c = 0; c < V; c++)
            if(G[r][c] == 1)
            {
                for(c1 = 0; c1 < V; c1++)
                    if(G[c][c1] == 1)    G2[r][c1] = 1;
            }
    }
}

int main(void)
{
    int G[5][5] = {{0, 1, 0, 0, 0}, {0, 0, 1, 1, 0}, {0, 1, 0, 0, 1}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}};
    int G2[5][5] = {{0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}};
    int r, c;

    for(r = 0; r < 5; r++)
    {
        for(c = 0; c < 5; c++)
            printf("%d ", G[r][c]);
        printf("\n");
    }
    printf("\n");

    GtoG2(G, G2, 5);

    for(r = 0; r < 5; r++)
    {
        for(c = 0; c < 5; c++)
            printf("%d ", G2[r][c]);
        printf("\n");
    }
    return(0);
}

针对邻接表的算法的实现：

GtoG2L.c :

#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
    int data;
    struct node *next;
}VNode;

void GtoG2(VNode G[], VNode G2[], int V)
{
    int i;
    VNode *srcline, *dstline, *dstp, *tmp;
    for(i = 0; i < V; i++)
    {
        srcline = G[i].next;
        while(srcline != NULL)
        {
            dstline = G[srcline->data - 1].next;
            while(dstline != NULL)
            {
                dstp = G2[i].next;
                while(dstp != NULL && dstp->data != dstline->data)
                    dstp = dstp->next;
                if(dstp == NULL)
                {
                    tmp = G2[i].next;
                    G2[i].next = (VNode *)malloc(sizeof(VNode));
                    G2[i].next->data = dstline->data;
                    G2[i].next->next = tmp;
                }
                dstline = dstline->next;
            }
            srcline = srcline->next;
        }
    }
}

void INIT(VNode G[], int V)
{
    int i;
    for(i = 0; i < V; i++)
        G[i].next = NULL;
}

void INPUT(VNode G[], int V)
{
    int i, data;
    VNode *p;

    printf("please input %d lines data(data > 0) and every line end with -1 :\n", V);
    for(i = 0; i < V; i++)
    {
        scanf("%d", &data);
        while(data != -1)
        {
            p = (VNode *)malloc(sizeof(VNode));
            p->data = data;
            p->next = G[i].next;
            G[i].next = p;
            scanf("%d", &data);
        }
    }
}

void PRINT(VNode G[], int V)
{
    int i;
    VNode *p;
    for(i = 0; i < V; i++)
    {
        printf("%d\t", i+1);
        p = G[i].next;
        while(p != NULL)
        {
            printf("%d ", p->data);
            p = p->next;
        }
        printf("\n");
    }
}

int main(void)
{
    int Vn = 4;
    VNode G[Vn], G2[Vn];

    INIT(G, Vn);
    INIT(G2, Vn);

    INPUT(G, Vn);
    printf("before GtoG2: \n");
    PRINT(G, Vn);

    GtoG2(G, G2, Vn);

    printf("after GtoG2: \n");
    PRINT(G2, Vn);

    return(0);
}