Вставка узлов отсортированным способом в связанный список

Question

Я пытаюсь создать отсортированный список в порядке возрастания.Я должен прочитать файл, который содержит год в каждой строке (поэтому я хочу сделать заказ от самой ранней даты до самой последней).

Что я пытаюсь выполнить с помощью своего кода:

1. Элемент списка
2. Получить данные (год) из строки файла .csv;
3. Перебирать список, пока не будет найдено место для узла, содержащего данные;
4. Повторяйте до тех пор, пока файл не закончится;
5. Печать;

Всякий раз, когда я пытаюсь запустить его, виртуальная коробка начинает отставать и ничего не делает.(даже когда я удаляю функцию печати).

Я пытался решить эту проблему уже 3 дня, поэтому я совершенно отчаялся.

Вот мой код:

#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

Так что, я думаю, ваша самая большая проблема - составить этот список ...

Так я бы сделал эти функции.

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


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


node *new_node(int key, int data)
{
    node * n =malloc(sizeof(node));
    if(!n)
    {
        fprintf(stderr,"malloc failed");
        exit(EXIT_FAILURE);
    }
    n->data = data;
    n->key = key;
    n->next = NULL;
}

node *insert_middle(node *next, int key, int data)
{
    node *new = new_node(key,data);
    new->next = next;
    return new;
}


node * insert_node(node *n, int key, int data)
{
    if(!n)
    {
        return new_node(key, data);
    }
    else if(n->data < data)
    {
        n->next = insert_node(n->next, key, data);
    }
    else
    {
        return insert_middle(n, key, data);
    }

}

int main()
{
    node *head=NULL;
    node *tmp = NULL;
    int i,j;
    for(i=0;i<10;i++)
    {
        scanf("%d",&j);
        tmp = insert_node(head, 0, j);
         //keep track of the head
        if(tmp!=head)
            head = tmp;
    }
    printf("====================");
    while(head)
    {
        printf("%d\n",head->data);
        head=head->next;
    }
    return 0;
}

Некоторые ошибки в вашем коде, которые я нашел:

for (key = 0; key <  20 ; key++)
{
    //you never change the value of data
    data = test[0];

if ( head_countries == NULL || key == 2 )
{
     //you should place curr = insertFirst(key, data);
     //the way you have written the code nothing happens
    //inserFirst function just return the vale and you don't store it anywhere so you can not use it
    insertFirst( key, data );
}

else
{
    curr = head_countries;
    //after this line of code curr=NULL in first iteration 

     //curr->next will cause SIGSEGV since curr=NULL, so NULL->next is not possible
    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;
    }

Слишком много ошибок ... Я думаю, вам следует начать заново.Если вы не понимаете мой пример, просто прокомментируйте, и я сделаю все возможное, чтобы объяснить

Answer 2

У вас есть несколько проблем, но наиболее значительная, похоже, связана с тем, как вы вставляете данные в список:

    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.
• Вы вставляете новый узел N после P.
• Вы продолжаете перебирать список .Следующий узел, который вы рассматриваете, является преемником P, , который теперь N .
• N также соответствует условиям для предшественника ваших данных (data == N.data), поэтому вы вставляете другой новый узел.И другой.И еще ...

Это будет продолжаться бесконечно, и компьютер действительно может начать замедляться слишком скоро, поскольку его физическая и виртуальная память будут загружены всеми узлами, выделяемыми программой.