鱼C论坛

 找回密码
 立即注册
查看: 1329|回复: 0

[学习笔记] 图-十字链表

[复制链接]
发表于 2022-8-20 19:27:11 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 奥普瓯江 于 2022-8-20 19:40 编辑

原理:



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

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

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



代码:
#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;
}

chrome_y7SevIyxOO.png

CIGzKwgrsQ.png
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-22 11:23

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表