求解决一个单链表插入排序的问题 - 编程论坛

#2

azzbcc2015-10-23 10:47

不要发两遍!

#3

抹茶裙边2015-10-23 10:54

回复 2楼 azzbcc

我只是觉得这和c语言有关，也和数据结构有关

#4

林月儿2015-10-23 12:36

按照插入排序法的思路理解就好，排序算法应该是在这里发的。
我在C版说过了L->next=NULL;只是让L的指针域为NULL

程序代码：

  p=L->next;L->next=NULL;//置空表，这样说也可以，但前面p=L->next;保存了L的下一结点！这点要注意
   while(p!=NULL)
  {
      r=L;
      q=L->next;
      while(q!=p&&q->data<=p->data)//按照插入排序的算法，这里在进行前半部分局部整序时为寻找后半部分待元素的待插入位置
      {
          r=q;q=q->next;//q=L，而L已经被置空表了，上面说L->next=NULL;q->next不是为空了吗？？//这里r的功能就是存储待插入位置的前一个结点
      }
        u=p->next;p->next=r->next;r->next=p;p=u;//这里应该就是执行插入，但是整个流程和我之前写的不一样，只能是说说自己分析
    }

#5

抹茶裙边2015-10-23 17:36

回复 4楼林月儿

L->next=NULL，也就是现在L的指针域是空。
而q=L->next，那岂不是q=NULL？

#6

林月儿2015-10-23 17:42

以下是引用抹茶裙边在2015-10-23 17:36:32的发言：

L->next=NULL，也就是现在L的指针域是空。
而q=L->next，那岂不是q=NULL？

并不是，q=L->next;先执行先保存了L的下一结点

#7

抹茶裙边2015-10-23 18:00

回复 6楼林月儿

不明白，我感觉钻了牛角尖了。

p=L->next;L->next=NULL;//这里是用p保存了L的下一个节点，之后L的指针域被赋值为空，也就是L现在不指向任何一个节点

而

q=L->next，是在上述代码之后赋值的，此时L->next已经被赋值为空了，L节点后面没有任何节点，q等于一个空啊我觉得。而且并不是q=p，这样的话还能说q是原链表的首元结点，可是并不是这样啊。

很疑惑，望解答。万分感激！

#8

林月儿2015-10-23 18:16

以下是引用抹茶裙边在2015-10-23 18:00:02的发言：

不明白，我感觉钻了牛角尖了。

p=L->next;L->next=NULL;//这里是用p保存了L的下一个节点，之后L的指针域被赋值为空，也就是L现在不指向任何一个节点

而

q=L->next，是在上述代码之后赋值的，此时L->next已经被赋值为空了，L节点后面没有任何节点，q等于一个空啊我觉得。而且并不是q=p，这样的话还能说q是原链表的首元结点，可是并不是这样啊。

很疑惑，望解答。万分感激！

说错了，还也为是进入循环体的p呢。。。恩，怎么说呢，L应该是由渐渐变长的链表而每增加一个结点都要寻找结点插入位置，判断也就是两种从头开始或者从结尾开始
我觉得你还是结合插入排序的流程来理解代码比较好，毕竟算法就是围绕功能走的
L开始为空，L作为局部链表是有序的，通过将结点插入合适位置，这个局部有序将朝着整体有序的方向走

#9

抹茶裙边2015-10-23 18:20

回复 8楼林月儿

嗯嗯，这个懂。我也看了插入排序的过程了，就实在觉得q->next=NULL啊