链表中的冒泡排序 C

Question

知道为什么我的程序在显示正确结果后崩溃了吗？（即我插入 6 2 4 3 he returns 2 3 4 6 但控制台立即崩溃！）

主要思想是在用户给出整数后对链表进行排序。我试图像冒泡排序一样解决它，但由于某种原因它不是 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;
}

Answer 1

崩溃一定发生在名为 printlist() 的函数（现在）中，因为您的程序在该函数 returns 之后没有执行任何其他操作。

我没有发现 printlist() 有什么本质上的错误，但这确实取决于列表是否处于有效状态。特别是，我对程序失败原因的最佳猜测是最后一个列表元素的 next 指针包含垃圾值而不是预期的 NULL。您可以通过运行调试器中的程序来验证这一点。

那么，列表如何损坏？

嗯，你的插入函数看起来没问题。它所依赖的 searchwithoutorder() 函数实际上并没有像它的名字那样做，但它确实做了 insertwithoutorder() 需要它做的事情。

剩下排序函数，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*/
        ...
    }
}

但是 head 在那个时候是 NULL，所以取消引用它会产生未定义的行为。如果该行为本身不是崩溃，那么正确猜测和取消引用您 的意思 的指针是一种极不可能的选择。而且，你没有在循环体内修改head，所以它仍然是 NULL。这个循环还有其他问题。

好像这还不够，您的排序函数也没有好的方法来更改哪个元素位于列表的头部——至少 none 这对来电者。

基本上，我认为您没有准确描述问题。一定是您观察到的失败行为与您描述的不同，或者您提供的代码与您描述的错误行为的程序不对应。

Answer 2

#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;
}

Answer 3

当向用户询问数据时，让用户知道您要询问什么以及如何handle/terminate 任何输入请求是很有用的。空白行上闪烁的光标不会告诉用户任何信息。（即使它正在为您测试，它也可以帮助防止错误类型的无意击键）。例如，您的 ex213 函数在空白行上留下闪烁的光标，让用户想知道 "Is the program hung?" "Did it encounter a race condition?" 等。当向用户询问链表数据时，一两行简单的附加行的指导真的很有帮助。示例：

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 ?
}

输出

$ ./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

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

链表中的冒泡排序 C

Bubble Sort in linked lists C

c

linked-list