c - 链表的无限冒泡排序

Question

我的 C 代码有问题。我正在尝试打开一个包含电影名称、年份、 Actor ...的 txt 文件

我将电影放在链表中。问题是在列表中订购电影时。我尝试通过冒泡排序方法来完成，但由于列表太大，当在 Dev 中运行时，程序会无限地运行该函数，而不会执行主要的其余部分(由于排序效率低下)。

有人会给我提示或帮助我在代码中应用并设法对列表进行排序吗？

代码如下:

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

#define N 10000  

typedef struct Lista {
    char data[N];
    struct Lista *next;
} Filmes;

typedef struct ListaDupla {
    char pessoa[N];
    struct ListaDupla *prox;
    struct ListaDupla *ant;
} DuplaLista;

struct Lista *Insert(struct Lista *head, char data[N]) {
    char aux3[N];
    struct Lista *tmp = ((struct Lista *)malloc(sizeof(struct Lista)));
    int aux5;
    strcpy(tmp->data, data);
    tmp->next = NULL;
    if (head == NULL) {
        head = tmp;
        return head;
    } else {
        struct Lista *aux = head;
        struct Lista *aux2 = head;
        while (aux->next != NULL) {
            aux = aux->next;
        }

        aux->next = tmp;

        while (aux != NULL) {
            aux2 = aux2->next;
            while (aux2 != NULL) {
                aux5 = strcmp(aux->data, aux2->data);
                if (aux5 > 0) {
                    strcpy(aux3, aux->data);
                    strcpy(aux->data, aux2->data);
                    strcpy(aux2->data, aux3);    
                }
            }
            aux = aux->next;
        }
        return head;
    } 

    // Complete this method
}

int main() {
    struct Lista *filmes = ((struct Lista *)malloc(sizeof(struct Lista)));
    int opcao;
    char aux2[N];
    FILE *arq;
    arq = fopen("nomes.txt", "rt");
    int i, a = 0, b, aux;
    char linha[600], nome[100];

    if (arq == NULL) {
        printf("Ocorreu um erro!");
        return 1;
    }
    while (fgets(linha, 700, arq)) {
        char *p = strtok(linha, ",");
        filmes = Insert(filmes, p);
        while (filmes->next != NULL) {
            printf(" \n Nome:%s", filmes->data);
            filmes = filmes->next;
        }
    }
    fclose(arq);
}

Answer 1

你的代码有很多问题:

• 列表项应该有一个指向已分配字符串的指针，而不是一个大尺寸(10000 字节!)的 char 数组。

• 您应该使用插入排序在正确的点插入新节点，而不是在使用冒泡排序尝试失败时修改列表元素。

• 您使用 struct Lista *filmes = ((struct Lista *)malloc(sizeof(struct Lista))); 在 main() 的开头分配了一个初始项目； 没有目的。您应该使用 struct Lista *filmes = NULL;

将列表初始化为空

• 您使用 fgets(linha, 700, arq) 将行读入 linha，但 linha 的大小仅为 600 字节。使用 fgets(linha, sizeof linha, arq) 来避免这样的不一致。

• 您使用 filmes = Insert(filmes, p); 插入一个新条目，这很好，但是您使用相同的指针在下面的循环中迭代列表。因此 filmes 将指向循环末尾的最后一项，下一个元素将不会插入到下一行头部的列表中。您应该使用不同的指针来遍历列表。

修改后的版本:

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

typedef struct Lista {
    char *data;
    struct Lista *next;
} Lista;

struct Lista *Insert(struct Lista *head, const char *data) {
    struct Lista *newp;
    struct Lista *tmp;
    char *new_data;

    /* allocate a new list item */
    newp = malloc(sizeof(struct Lista));
    new_data = strdup(data);
    if (newp == NULL || new_data == NULL) {
        fprintf(stderr, "out of memory");
        return NULL;
    }
    newp->data = new_data;
    newp->next = NULL;

    /* check if element should be inserted at the head */
    if (head == NULL || strcmp(new_data, head->data) < 0) {
        newp->next = head;
        head = newp;
    } else {
        /* otherwise find the point of insertion */
        tmp = head;
        while (tmp->next && strcmp(new_data, tmp->next->data) >= 0) {
            tmp = tmp->next;
        }
        newp->next = tmp->next;
        tmp->next = newp;
    }
    return head;
}

int main() {
    struct Lista *filmes;
    struct Lista *film;
    FILE *arq;
    char linha[600];

    /* open the file */
    arq = fopen("nomes.txt", "r");
    if (arq == NULL) {
        printf("Ocorreu um erro!");
        return 1;
    }

    /* insert the items */
    filmes = NULL;
    while (fgets(linha, sizeof linha, arq)) {
        char *p = strtok(linha, ",");
        filmes = Insert(filmes, p);
    }
    fclose(arq);

    /* print the sorted list */
    for (film = filmes; film != NULL; film = film->next) {
        printf("Nome: %s\n", film->data);
    }

    /* free the list */
    while (filmes != NULL) {
        struct Lista *next = filmes->next;
        free(filmes->data);
        free(filmes);
        filmes = next;
    }
    return 0;
}

请注意，可以修改插入函数以避免在头部插入的特殊套管:

struct Lista *Insert(struct Lista *head, const char *data) {
    struct Lista *newp;
    struct Lista **linkp;
    char *new_data;

    /* allocate a new list item */
    newp = malloc(sizeof(struct Lista));
    new_data = strdup(data);
    if (newp == NULL || new_data == NULL) {
        fprintf(stderr, "out of memory");
        return NULL;
    }
    newp->data = new_data;
    newp->next = NULL;

    /* use a double pointer to locate the point of insertion in a single pass */
    linkp = &head;
    while (*linkp && strcmp(new_data, (*linkp)->data) >= 0) {
        linkp = &(*linkp)->next;
    }
    newp->next = *linkp;
    *linkp = newp;
    return head;
}