论坛 › C\C++交流 › 链表冒泡排序我感觉我这么更改应该没有问题但是为什么执行不了哪位能给指点一下谢谢

奥普瓯江 发表于 2019-10-4 20:42:10

链表冒泡排序我感觉我这么更改应该没有问题但是为什么执行不了哪位能给指点一下谢谢

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

struct Node
{
                int a;
                struct Node *next;
};

void addlibrary(struct Node **);
void getInput(struct Node *);
void sort(struct Node *);
void printflibrary(struct Node *);

void getInput(struct Node *number)
{
                scanf("%d", &number->a);

}
void addlibrary(struct Node **library)
{
                struct Node *number;
                static struct Node *tail;

                number = (struct Node *)malloc(sizeof(struct Node));
                if(number == NULL)
                {
                                printf("对不起内存分配失败！");
                                exit(1);
                }

                getInput(number);
               
                if(*library != NULL)
                {
                                tail->next = number;
                                number->next = NULL;
                }
                else
                {
                                *library = number;
                                number->next = NULL;
                }
                tail = number;

}
//为什么这个链表一排序就出错呢？我这个排序程序哪里写的有问题呢？

void sort(struct Node *library)
{
                struct Node *temp;
                struct Node *one;
               

                while(library != NULL)
                {
                                temp = library->next;
                                if(library->a > temp->a)
                                {
                                                one = library;
                                                library = temp;
                                                one->next = temp->next;
                                                library = one;
                                }
                }


}

void printflibrary(struct Node *library)
{
                struct Node *temp;

                temp = library;

                while(temp != NULL)
                {
                                printf("%d", temp->a);
                                temp = temp->next;
                }
}

int main()
{
                struct Node *library = NULL;
                int ch = 10;

                while(ch)
                {
                                addlibrary(&library);
                                ch--;
                }

                sort(library);
                printflibrary(library);
                return 0;
}

人造人 发表于 2019-10-4 22:51:19

有2个问题

1.你用错算法了，你的这个算法没办法完成排序
参考这个，你应该能明白你的算法无法完成排序
#include <stdio.h>
#include <stdlib.h>

struct Node
{
        int a;
        struct Node *next;
};

void getInput(struct Node *number)
{
        scanf("%d", &number->a);

}
void addlibrary(struct Node **library)
{
        struct Node *number;
        static struct Node *tail;

        number = malloc(sizeof(struct Node));
        if(!number)
        {
                printf("对不起内存分配失败！\n");
                exit(1);
        }

        getInput(number);

        if(*library != NULL)
        {
                tail->next = number;
                number->next = NULL;
        }
        else
        {
                *library = number;
                number->next = NULL;
        }
        tail = number;

}

void sort(struct Node *library)
{
        struct Node *current = library;
        while(current)
        {
                struct Node *min = current;
                struct Node *p = current->next;
                while(p)
                {
                        if(min->a > p->a)
                                min = p;
                        p = p->next;
                }

                int temp = current->a;
                current->a = min->a;
                min->a = temp;

                current = current->next;
        }
}

void printflibrary(struct Node *library)
{
        struct Node *temp = library;
        while(temp)
        {
                printf("%d ", temp->a);
                temp = temp->next;
        }
        printf("\n");
}

int main()
{
        struct Node *library = NULL;
        int ch = 10;
        while(ch--)
                addlibrary(&library);
        sort(library);
        printflibrary(library);
        return 0;
}

/*
9 1 0 2 8 3 7 4 6 5
0 1 2 3 4 5 6 7 8 9
请按任意键继续. . .
*/



第2个问题
要修改一级指针，你需要二级指针
参考这个代码
#include <stdio.h>
#include <stdlib.h>

struct Node
{
        int a;
        struct Node *next;
};

void getInput(struct Node *number)
{
        scanf("%d", &number->a);

}
void addlibrary(struct Node **library)
{
        struct Node *number;
        static struct Node *tail;

        number = malloc(sizeof(struct Node));
        if(!number)
        {
                printf("对不起内存分配失败！\n");
                exit(1);
        }

        getInput(number);

        if(*library != NULL)
        {
                tail->next = number;
                number->next = NULL;
        }
        else
        {
                *library = number;
                number->next = NULL;
        }
        tail = number;

}

void sort(struct Node **library)
{
        struct Node *current = *library;
        while(current->next)
        {
                struct Node *min = current;
                struct Node *p = current->next;
                while(p->next)
                {
                        if(min->next->a > p->next->a)
                                min = p;
                        p = p->next;
                }

                struct Node *temp = current->next;
                current->next = min->next;
                min->next = temp;
                temp = min->next->next;
                min->next->next = current->next->next;
                current->next->next = temp;

                current = current->next;
        }

        current = *library;
        struct Node *p = current;
        while(p->next)
        {
                if(current->a > p->next->a)
                        p = p->next;
                else
                        break;
        }
        if(p == current && current->a < current->next->a)
                return;
        *library = current->next;

        current->next = p->next;
        p->next = current;
}

void printflibrary(struct Node *library)
{
        struct Node *temp = library;
        while(temp)
        {
                printf("%d ", temp->a);
                temp = temp->next;
        }
        printf("\n");
}

int main()
{
        struct Node *library = NULL;
        int ch = 10;
        while(ch--)
                addlibrary(&library);
        sort(&library);
        printflibrary(library);
        return 0;
}

/*
8 1 9 0 2 7 3 6 4 5
0 1 2 3 4 5 6 7 8 9
请按任意键继续. . .
*/


void sort(struct Node **library)
sort的参数改成了二级指针，因为要修改main函数中的library变量，library是一级指针，所以这里的参数要二级指针，这样才能修改main函数中的那个library

sort(&library);
在main函数中这样使用sort函数

如果链表的第0个元素不存储数据，那么通过交换指针的方式排序是可行的
但是如果链表的第0个元素也存储数据，那么就不适合通过交换指针的方式排序

我不知道这个代码你能不能看懂
因为链表的第0个元素也存储数据，这个数据结构不适合通过交换指针的方式排序，非要这样做也不是不可以，就是像我这样，通过算法来适应数据结构，就导致了我把代码写成这样，很不好理解，说真的，我理解这个代码都够呛，但是我还是勉强能理解，毕竟这个代码是我写的
^_^

奥普瓯江 发表于 2019-10-4 23:02:19

人造人 发表于 2019-10-4 22:51
有2个问题

1.你用错算法了，你的这个算法没办法完成排序


恩恩就是想理解指针的用法，刚学算法小甲鱼讲的算法，总感觉链表这做一张要是不把单链表这个吃透了学起来总是有些困难，这不正在一点一点的实验呢，总感觉不做题看那些东西理解又不理解所以就找些题来做做，看看能不能记点东西，这个是我把带你学C带你飞那张的链表那个题改了一下。我仔细看看你给的这些例题争取能看懂了，怎么也得能从你这里学点东西不是，加油

奥普瓯江 发表于 2019-10-21 17:15:01

人造人 发表于 2019-10-4 22:51
有2个问题

1.你用错算法了，你的这个算法没办法完成排序


第一种方式我理解了我按照自己的理解的方式写了一遍如果可以的话给指点一下谢谢了
#include<stdio.h>
#include<stdlib.h>

struct Node
{
                int a;
                struct Node *next;
};

void addlibrary(struct Node **);
void getinput(struct Node *);
void printflibrary(struct Node *);
void srot(struct Node *);

void getinput(struct Node *number)
{
                scanf("%d", &number->a);
}

void addlibrary(struct Node **library)
{
                struct Node *number;
                static struct Node *tail;

                number = (struct Node *)malloc(sizeof(struct Node));
                if(number == NULL)
                {
                                printf("内存分配失败！");
                                exit(1);
                }

                getinput(number);

                if(*library != NULL)
                {
                                tail->next = number;
                                number->next = NULL;
                }
                else
                {
                                *library = number;
                                number->next = NULL;
                }
                tail = number;
}
void srot(struct Node *library)
{
                struct Node *temp;
                temp = library;
                while(temp != NULL)
                {
                                struct Node *first;
                                int old;
                                first = library;
                                while(first != NULL)
                                {
                                                if(temp->a < first->a)
                                                {
                                                                old =temp->a;
                                                                temp->a = first->a;
                                                                first->a = old;
                                                }
                                                first = first->next;
                                }
                                temp = temp->next;
                }


}
void printflibrary(struct Node *library)
{
                struct Node *temp;

                temp = library;

                while(temp != NULL)
                {
                                printf("%d", temp->a);
                                temp = temp->next;
                }
}



int main()
{
                struct Node *library = NULL;
                int ch = 10;
                while(ch)
                {
                                addlibrary(&library);
                                ch--;
                }
                srot(library);
                printflibrary(library);

                return 0;
}

人造人 发表于 2019-10-21 21:31:43

addlibrary改成这样怎么样？

void addlibrary(struct Node **library)
{
        struct Node *number;
        static struct Node *tail;

        number = (struct Node *)malloc(sizeof(struct Node));
        if(!number)
        {
                printf("内存分配失败！");
                exit(1);
        }

        getinput(number);
        number->next = NULL;

        if(*library)
                tail->next = number;
        else
                *library = number;
        tail = number;
}

人造人 发表于 2019-10-21 21:36:10

void srot(struct Node *library)
{
        struct Node *temp = library;
        while(temp != NULL)
        {
                struct Node *first = library;
                int old;
                while(first != NULL)
                {
                        if(temp->a < first->a)
                        {
                                old =temp->a;
                                temp->a = first->a;
                                first->a = old;
                        }
                        first = first->next;
                }
                temp = temp->next;
        }
}

奥普瓯江 发表于 2019-10-22 14:49:14

人造人 发表于 2019-10-21 21:31
addlibrary改成这样怎么样？

嗯嗯这样改比我那个要效率高减少了寄存器的调用，不管*library是不是为空number->next = NULL谢谢指教

奥普瓯江 发表于 2019-10-22 14:50:28

人造人 发表于 2019-10-21 21:36


struct Node *temp = library;
我这里啰嗦了谢谢

查看完整版本: 链表冒泡排序我感觉我这么更改应该没有问题但是为什么执行不了哪位能给指点一下谢谢