c - 在链表中按排序方式插入节点

Question

我正在尝试按升序创建一个排序列表。我必须读取一个文件，其中每一行都包含一年(所以我想从最早的日期到最近的日期排序)。

我试图用我的代码完成的是:

1. 列出项目
2. 从 .csv 文件的一行中检索数据(年份)；
3. 迭代列表，直到找到包含数据的节点的位置；
4. 重复直到文件结束；
5. 打印；

每当我尝试运行它时，虚拟框就会开始滞后并且不执行任何操作。 (即使我删除了打印功能)。

我已经尝试解决这个问题三天了，所以我非常绝望。

这是我的代码:

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

struct node {
int data;
int key;
struct node *next;
} node;


struct node *head_countries = NULL;
struct node *current = NULL;

//display the list
void printList() {
   struct node *ptr = head_countries;
   printf("\n[ ");


    //start from the beginning
    while(ptr != NULL) {
    printf("(%d,%d)",ptr->key,ptr->data);
    ptr = ptr->next;
}

printf(" ]");
}

//insert link at the first location
struct node* insertFirst(int key, int data) {
    //create a link
    struct node *link = (struct node*) malloc(sizeof(struct node));

    link->key = key;
    link->data = data;

    //point it to old first node
    link->next = head_countries;

    //point first to new first node
    head_countries = link;

    return link;
    }

void insertAfter(struct node* PrevNode, int key, int data)
{
    struct node *NewNode = (struct node*) malloc(sizeof(struct node));

    if ( PrevNode == NULL )
    {
        printf("Erro 1");
        return;
    }

    NewNode->key = key;
    NewNode->data = data;

    NewNode->next = PrevNode->next;
    PrevNode->next = NewNode;

}


void CreateCountriesList()
{
    char linha[150];
    char cabecalho[100];
    int key = 0, data = 0;
    int test[15] = {0};

    test[0] = 10;
    test[1] = 25;
    test[2] = 7;
    test[3] = 5;
    test[4] = 30;
    test[5] = 40;
    test[6] = 3;
    test[7] = 4;
    test[8] = 98;
    test[10] = 4;
    test[11] = 14;
    test[12] = 23;
    test[13] = 16;
    test[14] = 35;
    test[15] = 6;

    //dados_temp New_Entry;

    struct node* curr_head = NULL;
    struct node* curr = NULL;

    FILE *inputf;
    inputf = fopen("tempcountries_all.csv", "r");


    if (inputf == NULL)
    {
        printf("Nao da pa abrir o ficheiro");
        exit(EXIT_FAILURE);
    }

    fgets(cabecalho, 100, inputf);

    for (key = 0; key <  20 ; key++)
    {
        data = test[key]

    if ( head_countries == NULL || key == 2 )
    {
        insertFirst( key, data );
    }

    else
    {
        curr = head_countries;
        //insertAfter(curr, key, data);
        //printf("%d\n", curr->data);
        //curr = curr->next;

        while ( curr->next != NULL )
        {
            //printf("%d", key);
            if ( curr->data < data && curr->next->data > data )
            {
                insertAfter(curr, key, data);
            }

            if ( data == curr->data )
            {
                //insertAfter(curr, key, data);
            }

            curr = curr->next;
        }
    }


}

printList();

fclose(inputf);
}

int main() {
CreateCountriesList();
return EXIT_SUCCESS;
}

是不是因为列表太大了？如果是这样，您建议我如何处理这么大的列表？

提前谢谢您!

编辑:从代码和未使用的函数中删除警告。

编辑:添加测试。

Answer 1

您遇到了几个问题，但最重要的一个似乎与如何将数据插入列表有关:

    while ( curr->next != NULL )
    {
        //printf("%d", key);
        if ( curr->data < data && curr->next->data > data )
        {
            insertAfter(curr, key, data);
        }

        if ( data == curr->data )
        {
            //insertAfter(curr, key, data);
        }

        curr = curr->next;
    }

执行插入后不会中断循环，因此请观察会发生什么:

• 您为要插入的数据找到合适的前驱 P。 curr 此时将指向 P。
• 您在 P 之后插入一个新节点 N。
• 您继续迭代列表。您考虑的下一个节点是 P 的后继节点，现在是 N。
• N 还满足数据前驱的条件 (data == N.data)，因此您插入另一个新节点。还有另一个。还有另一个...

这种情况将无限期地持续下去，并且计算机确实可能会在不久之后开始变慢，因为它的物理和虚拟内存会因程序分配的所有节点而负载过重。