双链表排序,该怎么处理

2013-08-13

双链表排序#includestdio.h#includestring.h#includestdlib.hstruct node_t{int datastruct node_t

双链表排序

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

struct node_t{
int data;
struct node_t *next;
struct node_t *prev;
};

int main(void)
{
int num;
struct node_t *head = NULL;
struct node_t *tail = NULL, *next = NULL, *prev = NULL, *new = NULL;
while(1)
{
printf("please input numbers:");
scanf("%d",&num);

if(num == -1)
  break;

new = (struct node_t *)malloc(sizeof(struct node_t));
if(NULL == new)
return -1;

new->data = num;

if(head == NULL)
{
new->next = new;
new->prev = new;
head = new;
}
else
{
//for(tail = head;tail->next != head && new->data > tail->next->data;tail = tail->next)
for(tail = head;tail->next != head && new->data > tail->data;tail = tail->next)
;
/*new->next = tail->next; 
new->prev = tail;
tail->next->prev = new;
tail->next = new;*/

new->next = tail;
new->prev = tail->prev->next;
tail->prev->next = new;
tail->prev = new;
}

}
for(tail = head; tail->next != head; tail = tail->next)
{
printf("%d\t",tail->data);
}
printf("\n");
}
/*hr@hr-laptop:~/妗岄潰/sqsz1309/3rd$ cc link_list.c 
hr@hr-laptop:~/妗岄潰/sqsz1309/3rd$ ./a.out
please input numbers:3
please input numbers:2
please input numbers:1
please input numbers:3
please input numbers:4
please input numbers:2
please input numbers:-1
32312(用注释的代码的结果)
===================================================================
hr@hr-laptop:~/妗岄潰/sqsz1309/3rd$ cc link_list.c 
hr@hr-laptop:~/妗岄潰/sqsz1309/3rd$ ./a.out
please input numbers:3
please input numbers:2
please input numbers:1
please input numbers:3
please input numbers:4
please input numbers:2
please input numbers:-1
343（用非注释代码的结果）*/

求解为何会出现这样的情况？头结点永远不参与排序尾节点无法输出。。。

双链表排序
[解决办法]
bug-插入结点不对


 for(tail = head;tail->next != head && new->data > tail->data;tail = tail->next)                        ;                        /*new->next = tail->next;                     new->prev = tail;                    tail->next->prev = new;                    tail->next = new;*/                         new->next = tail;                new->prev = tail->prev->next;                tail->prev->next = new;                tail->prev = new;

bug分析


 for(tail = head;tail->next != head && new->data > tail->data;tail = tail->next);
  //for循环执行完毕后，那么不成立两种情况，1表尾，2tail结点值>=当前new，不可统一操作，因为
到达尾结点时，要插入位置在末尾，即tail之后，而第2中条件下，要插入到tail之前，否则就不是排序了。

很显然，你注释掉那一段是在tail之后添加新结点。
未注释那段是在tail之前插入，但是可惜又错了

修改意见：
1.我看你另外发有帖子，我觉得循环条件new->data>tail->next->data还是可以使用的
2.针对末尾插入时，特别处理，使用条件判断一下即可.比如if(tail->next == head)
3.tail之前插入


new->next = tail;
new->prev = tail->prev;
tail->prev->next = new;
tail->prev = new;

热点排行

C语言

双链表排序,该怎么处理