冒泡在链表C中排序

any idea why does my program crash after showing the right result? (i.e. i insert 6 2 4 3 he returns 2 3 4 6 but the console crashes right after!)

任何想法为什么我的程序在显示正确的结果后崩溃？ （即我插入6 2 4 3他返回2 3 4 6但控制台在之后崩溃！）

The main idea is to sort a linked list after the user giving the integers. I tried to solve it like if it was a bubble sort but for some reason it's not 100% operational. sorry for the portuguese comments!

主要思想是在用户给出整数后对链表进行排序。我试图解决它，就好像它是一个泡泡排序，但由于某种原因，它不是100％可操作的。对不起葡萄牙语评论！

#define ITEM_TYPE int
typedef struct lnode* List;

typedef struct lnode{
    ITEM_TYPE info;
    List next;
}List_node;

void ordenalista(List lista){

    int contador = 0, i;
    /* lista é uma lista recebida */

    List head = lista; /* termos sempre disponível o início da lista*/
    List actual = NULL; /*lista vazia, ou nó */
    List temp = NULL;

    if(head == NULL || head->next == NULL){ /* caso de lista vazia ou so com 1 elemento*/
        printf("A lista esta vazia ou tem apenas um elemento");
        return 0;
    }

    while(head != NULL){ /* contar quantos elementos tem a lista*/
        contador++;
        head = head->next;
        printf("%d \n", contador);
    }

    for(i=0; i<contador; i++){ /* percorrer todos os elementos da lista*/
        while(head->next != NULL){ /* enquanto não chegarmos ao final da lista*/
            if(head->info > head->next->info){ /* se o valor do atual for maior que o valor do seguinte*/
                temp = head->next;
                head->next = head->next->next; /* não precisamos de usar actual->data, apenas precisamos de mudar os ponteiros*/
                temp->next = head;
            }
        }
    }
}

void ex213(){
    int numero;
    List lista;
    lista = create_list();

    while((scanf("%d",&numero)) == 1){ /* lê da esquerda para a direita. SCANF DÁ 1 SE INSERIR INTEIRO, 0 CASO CONTRÁRIO */
        insertwithoutorder(lista, numero);
    }

    ordenalista(lista);
    printlist(lista);
}

void insertwithoutorder(List lista, ITEM_TYPE it){
    List no;
    List ant, inutil;
    no = (List)malloc(sizeof(List_node));
    if (no != NULL) {
        no->info = it;
        searchwithoutorder(lista, it, &ant, &inutil);
        /*while(ant->next != NULL){
          ant = ant->next;
          }*/
        no->next = NULL;
        ant->next = no;
    }
}

void searchwithoutorder(List lista, ITEM_TYPE chave, List *ant, List*actual){
    *ant = lista; *actual = lista->next;
    while ((*actual) != NULL){
        *ant = *actual;
        *actual = (*actual)->next;
    }
    if ((*actual) != NULL && (*actual)->info != chave)
        *actual = NULL; /* Se elemento não encontrado*/
}

void printlist(List lista){
    List l = lista->next; /* Salta o header */
    while (l){
        printf("%d ", l->info);
        l=l->next;
    }
}

int main(){
    ex213();

    return 0;
}

3 个解决方案

#1

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

#define ITEM_TYPE int
typedef struct lnode* List;

typedef struct lnode{
    ITEM_TYPE info;
    List next;
} List_node;

List create_list(void){
    //top node unused
    return calloc(1, sizeof(List_node));//note : might NULL != 0
}

List lastNode(List lista){
    while (lista->next != NULL){
        lista = lista->next;
    }
    return lista;
}

void insertwithoutorder(List lista, ITEM_TYPE it){
    List no, ant;
    no = create_list();
    if (no != NULL) {
        no->info = it;
        no->next = NULL;
        ant = lastNode(lista);
        ant->next = no;
    } else {
        printf("failed to create a new node.\n");
    }
}

void ordenalista(List lista){
    List head = lista;
    List actual, neighbor, sentinel = NULL;

    if(head->next == NULL){
        printf("A lista esta vazia\n");
        return ;
    }

    while(head->next != sentinel){
        actual  = head->next;
        neighbor= actual->next;
        while(neighbor != sentinel){
            if(actual->info > neighbor->info){
                ITEM_TYPE temp = actual->info;
                actual->info   = neighbor->info;
                neighbor->info = temp;
            }
            actual  = neighbor;
            neighbor= neighbor->next;
        }
        sentinel = actual;
    }
}

void printlist(List lista){
    List l = lista->next;
    while (l){
        printf("%d ", l->info);
        l=l->next;
    }
    puts("");
}

void ex213(void){
    int numero;
    List lista = create_list();

    while((scanf("%d", &numero)) == 1){
        insertwithoutorder(lista, numero);
    }

    //printlist(lista);
    ordenalista(lista);
    printlist(lista);
    //deallocate ?
}

int main(void){
    ex213();

    return 0;
}

#2

The crash must be occurring in the function (now) named printlist(), as your program does nothing else after that function returns.

崩溃必须发生在名为printlist（）的函数（现在）中，因为在该函数返回后，程序不会执行任何其他操作。

I don't see anything inherently wrong with printlist(), but it does depend on the list being in a valid state. In particular, my best guess at why the program fails where it does would be that the next pointer of the last list element contains a junk value instead of the expected NULL. You could verify that by running the program in a debugger.

我没有看到printlist（）本身存在任何错误，但它确实依赖于列表处于有效状态。特别是，我最好猜测程序失败的原因是最后一个列表元素的下一个指针包含一个垃圾值而不是预期的NULL。您可以通过在调试器中运行程序来验证。

How, then, might the list be corrupted?

那么，列表可能如何被破坏？

Well, your insertion function looks ok. The searchwithoutorder() function on which it relies doesn't actually do what its name says, but it does do what insertwithoutorder() needs it to do.

好吧，你的插入功能看起来不错。它所依赖的searchwithoutorder（）函数实际上并不像它的名字所说的那样，但它确实执行了insertwithoutorder（）需要它做的事情。

That leaves the sort function, ordenalista(), and here I'm a bit flumoxed. I don't see how the version you posted could do any sorting at all. You have a while loop like so: while(head != NULL){...}, whithout any break or goto inside, so when control passes beyond this loop it must be that head == NULL. Then, without modifying the value of head, you go into a loop nest like this:

这留下了sort函数，ordenalista（），在这里我有点笨拙。我不知道你发布的版本如何进行任何排序。你有一个像这样的while循环：while（head！= NULL）{...}，没有任何break或goto里面，所以当控制超出这个循环时，它必须是head == NULL。然后，在不修改head的值的情况下，进入如下的循环嵌套：

for(i=0; i<contador; i++) { /* percorrer todos os elementos da lista*/
    while(head->next != NULL) { /* enquanto não chegarmos ao final da lista*/
        ...
    }
}

But head is NULL at that point, so dereferecing it produces undefined behavior. If that behavior were not itself a crash, then correctly guessing and dereferencing the pointer you meant is an extremely unlikely alternative. Moreover, you do not modify head in the body of the loop, so it remains NULL. There are other problems with this loop, too.

但是那时head是NULL，所以取消它会产生未定义的行为。如果这种行为本身并不是崩溃，那么正确猜测和解除引用你指的是一个极不可能的替代方案。此外，您不修改循环体中的头部，因此它保持为NULL。这个循环也有其他问题。

As if all that weren't enough, there is also no good way for your sort function to change which element is at the head of the list -- at least none that would be effective for the caller.

好像所有这些还不够，你的排序函数也没有好的方法来改变哪个元素位于列表的头部 - 至少没有一个对调用者有效。

So basically, I don't believe you have accurately described the problem. It must be either that the failure behavior you observed is different from what you described, or that the code you presented does not correspond to the program whose misbehavior you described.

所以基本上，我不相信你已经准确地描述了这个问题。它必须是您观察到的失败行为与您描述的失败行为不同，或者您提供的代码与您描述的行为不当的程序不对应。

#3

When asking the user for data, it is useful to let the user know what you are asking for and how to handle/terminate any requests for input. A blinking cursor on a blank line tells the user nothing. (even when it is testing for you, it can help prevent an inadvertent keystroke of the wrong type). For example your ex213 function leaves a blinking cursor on a blank line leaving the user wondering "Is the program hung?" "Did it encounter a race condition?" etc.. When asking the user for linked-list data, a simple additional line or two of guidance can really help. Example:

在询问用户数据时，让用户知道您要求的内容以及如何处理/终止任何输入请求是很有用的。空白行上闪烁的光标告诉用户什么都没有。 （即使它正在测试你，它可以帮助防止错误类型的无意按键）。例如，你的ex213函数在空行上留下一个闪烁的光标，让用户想知道“程序是否挂起？” “它遇到了竞争条件吗？”当询问用户链接列表数据时，一个或两个简单的额外线条可以真正起到帮助作用。例：

void ex213 (void)
{
    int numero;
    List lista = create_list ();

    printf ("\nEnter a number to add to the list [CTRL+D] when done:\n\n");
    while (printf (" data: ") && (scanf ("%d", &numero)) == 1) {
        insertwithoutorder (lista, numero);
    }

    ordenalista (lista);

    printf ("\n\nThe ordered linked-list is:\n\n");
    printlist (lista);
    printf ("\n");

    //deallocate ?
}

Output

产量

$ ./bin/ll_single_sort

Enter a number to add to the list [CTRL+D] when done:

 data: 2
 data: 8
 data: 20
 data: 6
 data: 9
 data: 1
 data:

The ordered linked-list is:

1 2 6 8 9 20

Adding that to the answer provided by BLUEPIXY provides the results you were looking for.

将其添加到BLUEPIXY提供的答案中可提供您正在寻找的结果。