单链表排序解决方案

单链表排序

C/C++ code

#include<stdio.h>#include<malloc.h>#define num 5typedef int datatype;typedef struct link_node{    datatype info;    struct link_node *next;}node;/*初始化*/node *init(){    return NULL;}/*前插法建立一个单链表*/node *create(node *head){    node *p;    datatype x,i;    for(i = 0;i<num;i++)    {       p = (node*)malloc(sizeof(node));       scanf("%d",&x);       p->info = x;       p->next = head;       head = p;     }    return head;}/*遍历单链表*/void display(node *head){    node *p;    p = head;    if(!p)        printf("\n单链表是空的！\n");    else    {        printf("\n单链表各节点值为：\n");        while(p)        {            printf("%d ",p->info);            p = p->next;        }    }}//单链表排序                            node *order(node *head){    int i = 0;    node *small,*q,*p,*p2,*head1,*head2;    q = small = head1 = head;    p = head->next;    while(head1)    {        small =head1;        p = head1->next;        while(p)        {            if(small->info >= p->info)            {                small = p;                p = p->next;            }            else                p = p->next;        }        i++;        p = head;    //查找small的前驱        while(p != small)        {            q = p;            p = p->next;        }        q->next = small->next;        if(small == head1)   //第一个节点就是small            head1 = head1->next;        if(i == 1)     //第一个找到的，也就是单链表中值最小的节点            head2 = small;        else            p2->next = small;        p2 = small;        small->next = NULL;    }    printf("\n-------------------------按学号排序成功！");    return head2;}/*主函数*/void main(){    node *head;    head = init();    head = create(head);    head = order(head);    display(head);}

这个排序有什么问题？

[解决办法]
问题很严重呀，看了一下你的代码是将HEAD1的表折腾折腾，找好排序的值放到HEAD2
中，这样指针很容易将原来的前后关系破坏，一般做法是在HEAD2
新建一个空间，或每次拷贝一个新节点放到HEAD2中。
[解决办法]
如果一个结点所拥有的值不多的话，紧把数据交换好了。

查看更多 下一篇