C - 链表的无尽气泡排序

Question

我在 C 语言中的代码有问题。我正在尝试打开一个包含电影名称、年份、演员等的 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

您的代码中存在许多问题：

• 列表项应具有指向已分配字符串的指针，char而不是具有较大大小(10000字节！

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

• 您在main()开始时分配初始项目，没有任何目的struct Lista *filmes = ((struct Lista *)malloc(sizeof(struct Lista)));。您应该使用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: %sn", 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;
}

Answer 2

让我们专注于这一切的核心，即您的insert功能。您在此处处理由指针链接的链表。与其一遍又一遍地复制内容，不如弯曲指针：

struct Lista *Insert(struct Lista *head, char data[N]) {
struct Lista *new_el = calloc(1, sizeof(struct Lista)));
strcpy(new_el->data, data);
new_el->next = NULL;
if (0 == head) {
return new_el;
} 
if(0 < strcmp(head->data, new_el->data)) {
new_el->next = head;
return new_el;
}
struct Lista* tmp = head;
while(0 != tmp->next){
If(0 < strcmp(new_el->data, tmp->next->data)) {
new_el->next = tmp->next;
tmp->next = new_el;
return head;             
} 
tmp = tmp->next;
} 
if(0 < strcmp(tmp->data, new_el->data)) {
new_el->next = tmp;
return head;
}
tmp->next = new_el;
return head;  
} 

希望这是有帮助的，不幸的是，我无法检查编译它，因为我现在才拿到手机。但是你明白了基本的想法，不是吗？

正如其他人所说，你应该很好地改变很多其他东西，比如不使用固定大小的数组，而是使用char*......

顺便说一句：你可以避免很多这样的极端情况，只需将标题指向一个空条目，并将实际列表从head->next开始......