图-十字链表

奥普瓯江

原理：



备注：
        感谢“人造人”给与的帮助，并细心对代码予以的回复，在代码更改中使我对递归的应用打开了一个新的世界。

        “递归的循环和释放是可以分开使用的”

        十字链表是，一个类与两个链表的合理组合与链接，并使用链表尾插法使其排列，注意链表的头容易在逆邻接表数据载入时被替换，对指针的使用有待提高与练习



代码：

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

typedef struct list
{
    int taildata, headdata;
    struct list *headlink, *taillink;
}list,*lists;

typedef struct like
{
    char data[MAX][MAX];
    list *doin, *doout;
}like;

void loop_list (list **doin);
void prin_list (list *doout);
void print_list (list *doin);
//void free_list(list *l);              //“人造人”借鉴释放语句
void free_list(list *doout);

/*void free_list(list *l)
{
    if(!l) return;
    free_list(l->taillink);
    free(l);
}*/

void free_list(list *doout)
{
    if(doout != NULL)                   //“!doout”当doout不等于0时，doout为真，!doout就为假，递归结束条件
    {
        return;
    }
    free_list(doout->taillink);         //递归循环
    free(doout);                        //释放malloc申请的动态内存，当递归循环释放时执行该语句

}

void print_list (list *doin)
{
    while(doin != NULL)
    {
        printf("%d ", doin->taildata);
        printf("%d ", doin->headdata);
        doin = doin->headlink;
    }
}

void prin_list (list *doout)
{
    while(doout != NULL)
    {
        printf("%d ", doout->taildata);
        printf("%d ", doout->headdata);
        doout = doout->taillink;
    }
}


void loop_list (list **doout)
{
    list *temp, *tail;
    int tail_vex, head_vex;


    while(1)
    {
        scanf("%d", &tail_vex);
        scanf("%d", &head_vex);

        if(tail_vex >= 0 && tail_vex <= 9)          //输入9以上的数字结束本函数
        {
            temp = (lists )malloc(sizeof(list ));
            temp->taildata = tail_vex;
            temp->headdata = head_vex;
            temp->taillink = NULL;
            temp->headlink = NULL;

            if(*doout == NULL)
            {
                *doout = temp;
            }
            else
            {
                tail->taillink = temp;
            }
            tail = temp;
        }
        else
        {
            break;
        }
    }
}
int main()
{
    like diss[MAX];
    list*temp, *nice, *kiss;

    for(int i = 0; i < MAX; i++)
    {
        scanf("%s", &diss[i].data[0][0]);
        diss[i].doin = NULL;
        diss[i].doout = NULL;
        loop_list(&diss[i].doout);
    }

    for(int i = 0; i < MAX; i++)
    {
        temp = diss[i].doout;               //先把diss数组中的邻接表传给临时变量指针temp这样temp就能指向diss数组中的doout邻接表

        while(temp)                        //判断temp是否为空指针如果不是空指针就执行该循环
        {
            if(diss[temp->headdata].doin == NULL)       //判断temp->headdata数组中doin逆邻接表是否为空如果是空执行该判断
            {
                diss[temp->headdata].doin = temp;
            }
            else
            {
                nice = diss[temp->headdata].doin;           //生成一个逆邻接表的指针变量把有数据的temp->headdata数组传给变量

                while(nice)                                 //循环变量nice直至他成为空，因为在生成邻接表的时候逆邻接表和邻接表的结尾我都赋予了NULL变量
                {
                    kiss = nice;                            //把逆邻接表的前一个存在数据的逆邻接表的地址传给kiss指针，以便在循环结束时使用
                    nice = nice->headlink;
                }
                kiss->headlink = temp;                      //循环结束把temp地址插入上一个逆邻接表中

            }
            temp = temp->taillink;             //temp作为临时变量向diss数组储存的邻接表向后搜索
        }

   }

    for(int i = 0; i < MAX; i++)
    {

        printf("%s ", diss[i].data[0]);
        prin_list(diss[i].doout);
        putchar('\n');
    }

    putchar('\n');

    for(int i = 0; i < MAX; i++)
    {
        printf("%s ", diss[i].data[0]);
        print_list(diss[i].doin);
        putchar('\n');
    }

     for(int i = 0; i < MAX; i++)
    {
        free_list(diss[i].doout);
    }

    return 0;
}