[已解决]链表排序

一世轻尘

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>//头文件 
#define LEN sizeof(struct data)//student结构的大小
struct data *creat();//创建链表 
void output(struct data *head);//打印链表
void sort(struct data *head);//排序 
struct data *insert(struct data *,struct data *);//插入结点 
struct data *remove(struct data*head,int n);//删除节点 
int m;
struct data{
        int n;
        struct data *next;
}; //定义结构数组 
int N;//全局变量，用来记录存放了多少数据。 
int main()//主函数 
{
        int remove_n;//定义存放需要删除的数值的变量· 
        struct data *stu,node;//声明结构指针变量 
        stu=creat();//函数返回链表第一个节点的地址 
        output(stu);//打印输出链表 
        printf("\n");//换行 
        system("pause"); 
        sort(stu);//排序 
        printf("The result of ascending sorting:\n");
        output(stu);//升序输出 
        return 0;
}
struct data *creat()//创建链表函数 
{
        struct data *head;
        struct data *p1,*p2;
        p1=p2=(struct data*)malloc(LEN);//开辟一个长度为LEN的内存区
        printf("Please enter a number:"); 
        scanf("%d",&p1->n); 
        head=NULL;//初始化头指针 
        N=0;//初始化结点个数 
        while(p1->n!=-1)//当输入-1时停止 
        {
                N++;
                if(1==N)
                {
                        head=p1;
                }
                else
                {
                        p2->next=p1;//把p1所指的结点连接在p2所指的结点后面 
                }
                p2=p1;
                p1=(struct data*)malloc(LEN);
                printf("Please enter a number:");
                scanf("%d",&p1->n);
        }
        p2->next=NULL;//结束 
        return head;//使函数返回头指针 
}
void output(struct data *head)//定义打印输出链表函数 
{
        struct data *p;//在函数中定义struct data类型的变量p 
        p=head;//使p指向第一个结点 
        if(NULL!=head)//若不是空表 
        {
                do
                {
                        printf("%d ",p->n);//输出一个结点中的数值 
                        p=p->next;//p指向下一个结点 
                }while(p!=NULL);//当p不是空地址 
        }
}
void sort(struct data *head)//定义排序函数 
{
        struct data *p,*q,*r,*t;
        int flag = 1;
        while(flag){
                p = head;
                q = head->next;
                flag = 0;

                while(q != NULL){//循环终止条件 
                        r = q->next;
                        if(r == NULL){//循环终止条件 
                                break;
                        }else if(q->n > r->n){
                                t = r->next;
                                q->next = t; 
                                r->next = q;
                                p->next = r;
                                //重新排序 
                                p = r;
                                q = p->next;
                                r = q->next;
                                //指向整体后移便于接下来排序 
                                flag = 1;
                        }else{
                                p = q;
                                q = p->next;//指向后移 
                        }
                }
        }
}

怎样修改才能使第一个节点也参与排序呢？头结点怎么建立，作用是啥？
求助

最佳答案

月排行榜 / 总排行榜

jackz007

2020-12-13 16:28:41

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

struct data{
        int n;
        struct data *next;
};

#define LEN sizeof(struct data)

int m ;
int N ; //全局变量，用来记录存放了多少数据。

struct data * creat(void)//创建链表函数
{
        struct data * head , * p1 , * p2                                             ;
        int d , k                                                                    ;
        for(N = 0 , k = 0 ;; k ++ , N ++) {
                printf("Please enter a number(-1 for ending input) : ")              ;
                scanf("%d" , & d)                                                    ;
                if(d != -1) {
                        if((p2 = malloc(sizeof(struct data))) != NULL) {
                                p2 -> n = d                                          ;
                                p2 -> next = NULL                                    ;
                                if(! k) head = p2                                    ;
                                else p1 -> next = p2                                 ;
                                p1 = p2                                              ;
                        } else {
                                fprintf(stderr , "\n")                               ;
                                fprintf(stderr , "\tError : can't alloc memory !\n") ;
                                fprintf(stderr , "\n")                               ;
                                exit(1)                                              ;
                        }
                } else {
                        break                                                        ;
                }
                printf("\n")                                                         ;
        }
        return head                                  ;
}

void output(struct data * head)//定义打印输出链表函数
{
        struct data * p                                           ;
        for(p = head ; p ; p = p -> next) printf("%d\n" , p -> n) ;
}

struct data * sort(struct data * head)
{
        struct data * h , * p , * q , * r , * t                   ;
        int f                                                     ;
        for(f = 1 , h = head ; f ;) {
                f = 0                                             ;
                for(r = NULL , q = h , p = q -> next ; q && p ; r = q , q = p , p = q -> next) {
                        if(q -> n > p -> n) {
                                t = p -> next                     ;
                                p -> next = q                     ;
                                q -> next = t                     ;
                                if(r) {
                                        r -> next = p             ;
                                } else {
                                        h = p                     ;
                                }
                                f ++                              ;
                        }
                }
        }
        return h                                                  ;
}

int main()//主函数
{
        int remove_n;//定义存放需要删除的数值的变量·
        struct data * stu , node;//声明结构指针变量
        stu = creat() ;//函数返回链表第一个节点的地址
        output(stu)   ;//打印输出链表
        printf("\n");//换行
        stu = sort(stu);//排序
        printf("The result of ascending sorting:\n");
        output(stu);//升序输出
}

        编译、运行实况

D:\00.Excise\C>cl x.c
用于 x86 的 Microsoft (R) C/C++ 优化编译器 19.28.29334 版
版权所有(C) Microsoft Corporation。保留所有权利。

x.c
Microsoft (R) Incremental Linker Version 14.28.29334.0
Copyright (C) Microsoft Corporation.  All rights reserved.

/out:x.exe
x.obj

D:\00.Excise\C>x
Please enter a number(-1 for ending input) : 9

Please enter a number(-1 for ending input) : 8

Please enter a number(-1 for ending input) : 7

Please enter a number(-1 for ending input) : 6

Please enter a number(-1 for ending input) : 5

Please enter a number(-1 for ending input) : 4

Please enter a number(-1 for ending input) : 3

Please enter a number(-1 for ending input) : 2

Please enter a number(-1 for ending input) : 1

Please enter a number(-1 for ending input) : -1
9
8
7
6
5
4
3
2
1

The result of ascending sorting:
1
2
3
4
5
6
7
8
9

D:\00.Excise\C>

跳转到最佳答案楼层

jackz007

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

struct data{
        int n;
        struct data *next;
};

#define LEN sizeof(struct data)

int m ;
int N ; //全局变量，用来记录存放了多少数据。

struct data * creat(void)//创建链表函数
{
        struct data * head , * p1 , * p2                                             ;
        int d , k                                                                    ;
        for(N = 0 , k = 0 ;; k ++ , N ++) {
                printf("Please enter a number(-1 for ending input) : ")              ;
                scanf("%d" , & d)                                                    ;
                if(d != -1) {
                        if((p2 = malloc(sizeof(struct data))) != NULL) {
                                p2 -> n = d                                          ;
                                p2 -> next = NULL                                    ;
                                if(! k) head = p2                                    ;
                                else p1 -> next = p2                                 ;
                                p1 = p2                                              ;
                        } else {
                                fprintf(stderr , "\n")                               ;
                                fprintf(stderr , "\tError : can't alloc memory !\n") ;
                                fprintf(stderr , "\n")                               ;
                                exit(1)                                              ;
                        }
                } else {
                        break                                                        ;
                }
                printf("\n")                                                         ;
        }
        return head                                  ;
}

void output(struct data * head)//定义打印输出链表函数
{
        struct data * p                                           ;
        for(p = head ; p ; p = p -> next) printf("%d\n" , p -> n) ;
}

struct data * sort(struct data * head)
{
        struct data * h , * p , * q , * r , * t                   ;
        int f                                                     ;
        for(f = 1 , h = head ; f ;) {
                f = 0                                             ;
                for(r = NULL , q = h , p = q -> next ; q && p ; r = q , q = p , p = q -> next) {
                        if(q -> n > p -> n) {
                                t = p -> next                     ;
                                p -> next = q                     ;
                                q -> next = t                     ;
                                if(r) {
                                        r -> next = p             ;
                                } else {
                                        h = p                     ;
                                }
                                f ++                              ;
                        }
                }
        }
        return h                                                  ;
}

int main()//主函数
{
        int remove_n;//定义存放需要删除的数值的变量·
        struct data * stu , node;//声明结构指针变量
        stu = creat() ;//函数返回链表第一个节点的地址
        output(stu)   ;//打印输出链表
        printf("\n");//换行
        stu = sort(stu);//排序
        printf("The result of ascending sorting:\n");
        output(stu);//升序输出
}

        编译、运行实况

D:\00.Excise\C>cl x.c
用于 x86 的 Microsoft (R) C/C++ 优化编译器 19.28.29334 版
版权所有(C) Microsoft Corporation。保留所有权利。

x.c
Microsoft (R) Incremental Linker Version 14.28.29334.0
Copyright (C) Microsoft Corporation.  All rights reserved.

/out:x.exe
x.obj

D:\00.Excise\C>x
Please enter a number(-1 for ending input) : 9

Please enter a number(-1 for ending input) : 8

Please enter a number(-1 for ending input) : 7

Please enter a number(-1 for ending input) : 6

Please enter a number(-1 for ending input) : 5

Please enter a number(-1 for ending input) : 4

Please enter a number(-1 for ending input) : 3

Please enter a number(-1 for ending input) : 2

Please enter a number(-1 for ending input) : 1

Please enter a number(-1 for ending input) : -1
9
8
7
6
5
4
3
2
1

The result of ascending sorting:
1
2
3
4
5
6
7
8
9

D:\00.Excise\C>

一世轻尘

少个类型转化，小问题