b00tyhunt3r
V2EX  ›  C

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

  •  
  •   b00tyhunt3r · May 14, 2019 · 3726 views
    This topic created in 2567 days ago, the information mentioned may be changed or developed.
    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 replies    2019-05-15 23:03:13 +08:00
    wutiantong
        1
    wutiantong  
       May 14, 2019
    都有注释了还看不懂么?

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

    这不就是了吗。
    across
        4
    across  
       May 14, 2019 via iPhone
    放 ide 里面单步调试一步步看。

    估计你是没理解中间 while 内容,每次都从头遍历一遍,找到最后一个节点
    b00tyhunt3r
        5
    b00tyhunt3r  
    OP
       May 14, 2019
    **
    @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,那么是怎么一步步遍历到最后一个结点上的呢?!?!**
    atx
        6
    atx  
       May 14, 2019
    重点在这句 while(last->next)
    kiddult
        7
    kiddult  
       May 14, 2019
    @b00tyhunt3r

    第一个问题看 maichael 的回答

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

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

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


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

    当自己的理解和实际代码运行不一致的时候 ,一定是你的理解有问题,单步调试看是哪里理解错了 啊
    xiri
        13
    xiri  
       May 14, 2019
    @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  
       May 14, 2019 via Android
    甭管单向链表双向链表还是异或链表都应该是俩指针,一头一尾。
    单指针链表要么当栈使,要么追加元素复杂度是 O(n)的。这个是后者,重新找一段代码学霸吧
    ThomasZ
        15
    ThomasZ  
       May 14, 2019 via Android
    调试一把,看看数据变化就知道咋回事了
    JerryCha
        16
    JerryCha  
       May 14, 2019
    每一次 add 在创建好新节点后,会从头开始遍历到最后一个节点为止,然后把新节点接上。
    这写法还真是简洁,涨姿势了。
    vx2018
        17
    vx2018  
       May 15, 2019
    只有一个节点时直接插 next, 多个节点时用临时指针遍历到最后一个插到 next 嘛
    b00tyhunt3r
        18
    b00tyhunt3r  
    OP
       May 15, 2019 via iPad
    感谢各位大哥!!我真辣鸡啊!
    About   ·   Help   ·   Advertise   ·   Blog   ·   API   ·   FAQ   ·   Solana   ·   941 Online   Highest 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 56ms · UTC 18:53 · PVG 02:53 · LAX 11:53 · JFK 14:53
    ♥ Do have faith in what you're doing.