论坛 › 数据结构与算法 › 十字链表代码实现问题求助

奥普瓯江 发表于 2022-8-4 01:23:17

十字链表代码实现问题求助

介绍：我按照“小甲鱼”的数据结构第五十八讲中所讲解的十字链表，自己按照理解写了一个十字链表实现代码，在实现邻接表过程是顺利的但是逆邻接表的实现却遇到了问题，逆邻接表的实现我用的是迭代在main函数中代码如下：
for(int i = 0; i < MAX; i++)
    {
      temp = diss.doout;

      while(temp != NULL)
      {
            temps = &diss.doin;

            if(*temps == NULL)                //如果
            {
                *temps = temp;
            }
            else
            {

                nice = *temps;                  //这里的逻辑我一直想不明白为什么我在这里会错误呢，我感觉他是因为指针的问题但是我不并不知道问题是怎么发生的请指教
                while(*temps != NULL)
                {
                  *temps = (*temps)->headlink;
                }
                *temps = temp;
                *temps = nice;

            }
            temp = temp->taillink;
      }
   }


输入后DOS输入输出页面：




完整代码：
#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;
    list *doin, *doout;
}like;

void loop_list (list **doin);
void prin_list (list *doout);
void print_list (list *doin);

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;
    list *temp;
    list **temps;
    list *nice;

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

    for(int i = 0; i < MAX; i++)
    {
      temp = diss.doout;

      while(temp != NULL)
      {
            temps = &diss.doin;

            if(*temps == NULL)                //如果
            {
                *temps = temp;
            }
            else
            {

                nice = *temps;                  //这里的逻辑我一直想不明白为什么我在这里会错误呢，我感觉他是因为指针的问题但是我不并不知道问题是怎么发生的请指教
                while(*temps != NULL)
                {
                  *temps = (*temps)->headlink;
                }
                *temps = temp;
                *temps = nice;

            }
            temp = temp->taillink;
      }
   }

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

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

    putchar('\n');

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






    return 0;
}

人造人 发表于 2022-8-4 18:06:06

1. 又不写内存释放的代码？
你不写，你在指望谁帮你写？这一次我又帮你写了

2. 没看明白你的逆邻接表的代码

#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;
    list *doin, *doout;
} like;

void loop_list(list **doin);
void prin_list(list *doout);
void print_list(list *doin);

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;
      }
    }
}

void chain_head(like diss) {
    for(size_t i = 0; i < MAX; ++i) {
      list *current = diss.doout;
      for(size_t j = 0; current; ++j) {
            current->headlink = diss.doin;
            diss.doin = current;
            current = current->taillink;
      }
    }
}

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

int main() {
    like diss;
    /*
    list *temp;
    list **temps;
    list *nice;
    */

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

    chain_head(diss);

    /*
    for(int i = 0; i < MAX; i++) {
      temp = diss.doout;

      while(temp != NULL) {
            temps = &diss.doin;

            if(*temps == NULL) //如果
            {
                *temps = temp;
            } else {

                nice =
                  *temps; //这里的逻辑我一直想不明白为什么我在这里会错误呢，我感觉他是因为指针的问题但是我不并不知道问题是怎么发生的请指教
                while(*temps != NULL) {
                  *temps = (*temps)->headlink;
                }
                *temps = temp;
                *temps = nice;
            }
            temp = temp->taillink;
      }
    }
    */

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

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

    putchar('\n');

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

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

    return 0;
}

人造人 发表于 2022-8-4 18:17:02

知道吗？不写内存释放的代码，我这边是直接报错的，会报内存泄漏的错误
我不补齐内存释放的代码，就不知道这个代码还有没有其他问题
如果我的这个环境还报错，那就是还有问题
如果我的这个环境不报错了，那就问题不大了（对于这一句，大概是这样的）

$ gcc-debug -o main main.c
$ ./main <<EOF
v0
0
3
10
v1
1
0
1
2
10
v2
2
0
2
1
10
v3
10
10
EOF
v0 0 3
v1 1 0 1 2
v2 2 0 2 1
v3

v0 2 0 1 0
v1 2 1
v2 1 2
v3 0 3

=================================================================
==653525==ERROR: LeakSanitizer: detected memory leaks

Direct leak of 48 byte(s) in 2 object(s) allocated from:
    #0 0x7fe01c2bfa89 in __interceptor_malloc /usr/src/debug/gcc/libsanitizer/asan/asan_malloc_linux.cpp:69
    #1 0x55f8dc9ca6fb in loop_list /tmp/main.c:46
    #2 0x55f8dc9cb41a in main /tmp/main.c:93
    #3 0x7fe01b83f2cf(/usr/lib/libc.so.6+0x232cf)

Indirect leak of 48 byte(s) in 2 object(s) allocated from:
    #0 0x7fe01c2bfa89 in __interceptor_malloc /usr/src/debug/gcc/libsanitizer/asan/asan_malloc_linux.cpp:69
    #1 0x55f8dc9ca6fb in loop_list /tmp/main.c:46
    #2 0x55f8dc9cb41a in main /tmp/main.c:93
    #3 0x7fe01b83f2cf(/usr/lib/libc.so.6+0x232cf)

SUMMARY: AddressSanitizer: 96 byte(s) leaked in 4 allocation(s).
$


看到了吗？报错了，所以下一次不要再让我们帮你补全内存释放的代码了，因为这应该是你的工作
还有，要学着调试程序
你是如何调试程序的？
用眼睛盯着代码一行一行的看？
在程序中加满printf ？
这都是最低级的调试程序的方法
最好是把程序载入内存，一行一行的执行，通过调试器查看/修改变量的值

奥普瓯江 发表于 2022-8-4 23:11:02

人造人 发表于 2022-8-4 18:17
知道吗？不写内存释放的代码，我这边是直接报错的，会报内存泄漏的错误
我不补齐内存释放的代码，就不知道 ...

明白明白，一定记住以后写内存释放代码，谢谢谢谢，这是非常宝贵的经验

奥普瓯江 发表于 2022-8-4 23:13:34

人造人 发表于 2022-8-4 18:06
1. 又不写内存释放的代码？
你不写，你在指望谁帮你写？这一次我又帮你写了



我先试着理解你给改的这些代码然后再回复，非常感谢

人造人 发表于 2022-8-4 23:19:04

奥普瓯江 发表于 2022-8-4 23:13
我先试着理解你给改的这些代码然后再回复，非常感谢

void chain_head(like diss) {
    for(size_t i = 0; i < MAX; ++i) {
      list *current = diss.doout;
      //for(size_t j = 0; current; ++j) {
      while(current) {
            current->headlink = diss.doin;
            diss.doin = current;
            current = current->taillink;
      }
    }
}

奥普瓯江 发表于 2022-8-20 19:16:49

人造人 发表于 2022-8-4 23:19


我通过你给调整的代码，进行了个人理解，然后对我自己的代码进行了更改，并从你指出的内存释放语句中学到了用递归的方式释放内存而不是使用循环谢谢。

代码：
#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;
    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;
    list*temp, *nice, *kiss;

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

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

      while(temp)                        //判断temp是否为空指针如果不是空指针就执行该循环
      {
            if(diss.doin == NULL)       //判断temp->headdata数组中doin逆邻接表是否为空如果是空执行该判断
            {
                diss.doin = temp;
            }
            else
            {
                nice = diss.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.data);
      prin_list(diss.doout);
      putchar('\n');
    }

    putchar('\n');

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

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

    return 0;
}

查看完整版本: 十字链表代码实现问题求助