V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
b00tyhunt3r
V2EX  ›  C

一段看似简单却百思不得其解的 C 链表代码!

  •  
  •   b00tyhunt3r · 2019-05-14 19:37:09 +08:00 · 3090 次点击
    这是一个创建于 2018 天前的主题,其中的信息可能已经有所发展或是发生改变。
    typedef struct ooo{   //定义链表结构体
      int value;
      struct ooo* next;
    }node;
    
    typedef struct _list{   //代表头结点
      node* head;  
    }list;
    
    //声明结点创建函数 add
    void add(int data,list* list);
    
    
    //主函数
    int main()
    {                                                                      
      list list;
      list.head = NULL;  //定义头结点,并初始化为空
    
      int data;     //录入数据,输入-1 代表结束
      do {
      scanf("%d",&data);
      if (data!=-1) 
        {
          add(data,&list);
        }
      }while(data!=-1);
    
    return 0;
    }
    
    
    
    //定义新结点函数 add
    void add(int data,list* list)
    {
      node* new=(node*)malloc(sizeof(node));  //创建新结点并录入数据
      new->value=data;
      new->next = NULL;
    
    
      //寻找已创建结点中的最后一个结点 
      node* last= list->head;  //让最后一个结点等于此时的头结点
      if(last)                 //遍历所有存在的结点,直到到达最后一个               
        {
          while(last->next)
            {
              last=last->next;
            }
          last->next = new; //链接最后一个结点和新结点 new
        }
      else
        {
          list->head=new;  //最初创建第一个新结点 new 时,让 head 头结点=该结点。
        }
    }
    

    问题:看到最后可得知头结点 head 应该永远等于第一次创建的 new 结点, 即 head->next=new->next=NULL,并且每次进入 add 函数,last 都会等于 head,那么 last->next 也应该是 NULL, 所以头结点 head 的 next 永远是 NULL,那它到底是怎么和后边的结点连上的??? 而进来 add 函数以后,last 每个结点间又是怎么连上的呢?? 想了很久头都大了,仍然不得其解!!只能寄望于 v2 大佬了!!本小白先谢过啦!!!!

    18 条回复    2019-05-15 23:03:13 +08:00
    wutiantong
        1
    wutiantong  
       2019-05-14 19:43:52 +08:00
    都有注释了还看不懂么?

    要不你调试一遍,观察一下变量值的变化。
    wutiantong
        2
    wutiantong  
       2019-05-14 19:45:31 +08:00
    话说你的问题描述真是够迷糊的了。。。
    maichael
        3
    maichael  
       2019-05-14 19:47:24 +08:00
    " last->next = new; //链接最后一个结点和新结点 new"

    这不就是了吗。
    across
        4
    across  
       2019-05-14 19:49:59 +08:00 via iPhone
    放 ide 里面单步调试一步步看。

    估计你是没理解中间 while 内容,每次都从头遍历一遍,找到最后一个节点
    b00tyhunt3r
        5
    b00tyhunt3r  
    OP
       2019-05-14 19:50:13 +08:00
    **
    @wutiantong
    抱歉重新组织了一下语言!

    问题:看到最后可得知头结点 head 应该永远等于第一次创建的 new 结点,
    即 head->next=new->next=NULL,
    并且每次进入 add 函数,都会令 last 等于 head,那么 last->next 此时也应该是 NULL,

    所以头结点 head 的 next 永远是 NULL,那它到底是怎么和后边的结点连上的???

    问题 2: 而进入到 add 函数以后,
    ```
    last->next = new; //找到最后的结点后,链接到新结点 new 上
    ```
    这一段可以看出是用 last 链接了新结点,但是在找 last 的过程中,一上来 last 自身的 next 为 NULL,那么是怎么一步步遍历到最后一个结点上的呢?!?!**
    lc1450
        6
    lc1450  
       2019-05-14 19:52:58 +08:00
    重点在这句 while(last->next)
    kiddult
        7
    kiddult  
       2019-05-14 19:54:49 +08:00
    @b00tyhunt3r

    第一个问题看 maichael 的回答

    第二个问题是 last=last->next; 这句是把 next 节点赋值给 last
    xiri
        8
    xiri  
       2019-05-14 19:56:18 +08:00
    楼主你这是不懂链表还是不懂 C 啊,,,,,,
    “看到最后可得知头结点 head 应该永远等于第一次创建的 new 结点”,你好好看看 add()函数最后一个代码块,连 if{}else{}怎么运行的都不知道了吗?
    第一次运行的时候 last 为 null,所以直接把 head 赋值为这个新建的节点 new,然后 head 就不为空了,再次执行 add()函数的时候 last 就也不为空了,那 list->head=new 还会执行???
    ysc3839
        9
    ysc3839  
       2019-05-14 19:59:45 +08:00 via Android
    @b00tyhunt3r 问题 2,“ last 自身的 next 为 NULL ”,说明这就是最后一个节点。
    chashao
        10
    chashao  
       2019-05-14 20:00:09 +08:00 via Android
    在第一次 add 时,last 是 NULL 所以把 head=new,第二次 add 就会用 while 来遍历了😂
    bp0
        11
    bp0  
       2019-05-14 20:04:38 +08:00
    last 指向 list->head,只有第一次进入的时候是 NULL。后面再进入就不再是 NULL 了。

    你不能理解的原因可能是因为
    “ if(last) //遍历所有存在的结点,直到到达最后一个 ”
    这个注释是错误的,正确的注释应该是:“ 判断链表是否为空”。

    如果链表为空,list->head = new。不是空则循环到链表尾部并把新节点挂入。


    这程序好多问题,建议你看看其他书吧,别被耽误了。
    akira
        12
    akira  
       2019-05-14 20:09:25 +08:00
    "并且每次进入 add 函数,last 都会等于 head" 这句话有问题

    当自己的理解和实际代码运行不一致的时候 ,一定是你的理解有问题,单步调试看是哪里理解错了 啊
    xiri
        13
    xiri  
       2019-05-14 20:11:41 +08:00
    @xiri 算了,直接讲太麻烦了,我直接给你口头模拟一边链表连接的过程。
    1. head 为空,执行 add 函数时新建了一个节点 new,last=head=NULL,所以这时候直接执行 else 后面的代码,head 指向新建的节点 new,不再为空
    2. head 不再为空,但此时只有一个节点,head->next=NULL,此时执行 add 函数,last=head,不为空,执行 if 后面的代码块,此时先遇到 while 循环,由于 last->next=head->next=NULL,所以直接跳过,然后 last->next=new 将新节点加在最后面,这时整个链表有两个节点
    3. head 不再为空,head->next 也不为空,执行 add 函数,last=head,不为空,执行 if 后面代码块。此时 last->next 也不为空,执行 while 循环,直至 last->next=NULL 时结束(也就是说 last 指向链表最后一个节点时结束),再然后 last->next=new 又新节点加在最后面,这时整个链表有三个节点
    ......
    后面就跟第三步时完全一样的,关键点在那个 while 循环,它会让 last 指向最后一个节点,之后再执行 last->next=new,也就是将节点加在链表最后面了
    iceheart
        14
    iceheart  
       2019-05-14 20:40:54 +08:00 via Android
    甭管单向链表双向链表还是异或链表都应该是俩指针,一头一尾。
    单指针链表要么当栈使,要么追加元素复杂度是 O(n)的。这个是后者,重新找一段代码学霸吧
    ThomasZ
        15
    ThomasZ  
       2019-05-14 20:50:36 +08:00 via Android
    调试一把,看看数据变化就知道咋回事了
    JerryCha
        16
    JerryCha  
       2019-05-14 21:08:06 +08:00
    每一次 add 在创建好新节点后,会从头开始遍历到最后一个节点为止,然后把新节点接上。
    这写法还真是简洁,涨姿势了。
    vx2018
        17
    vx2018  
       2019-05-15 11:10:48 +08:00
    只有一个节点时直接插 next, 多个节点时用临时指针遍历到最后一个插到 next 嘛
    b00tyhunt3r
        18
    b00tyhunt3r  
    OP
       2019-05-15 23:03:13 +08:00 via iPad
    感谢各位大哥!!我真辣鸡啊!
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3339 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 04:56 · PVG 12:56 · LAX 20:56 · JFK 23:56
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.