неожиданный вывод при попытке создать упорядоченный связанный список

Question

Я пытаюсь написать программу, которая генерирует упорядоченный случайный связанный список.Проблема в том, что на выходе иногда только 4 числа, а иногда бесконечная последовательность чисел.Я думаю, что проблема в функции gen, как я могу это исправить?

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 5

struct node{
    int v;
    struct node *nextPtr;
};

typedef struct node Node;
typedef Node *NodePtr;

void gen(NodePtr *startPtr);
void print(NodePtr start);

int main()
{
    NodePtr startPtr;
    startPtr = NULL;
    gen(&startPtr);
    print(startPtr);
    return 0;
}

void gen(NodePtr *startPtr)
{
    NodePtr currPtr, lastPtr, newPtr;
    int r;
    lastPtr = NULL;
    srand(time(NULL));


    for(int i = 0; i < N; i++){
        currPtr = *startPtr;
        r = rand()%101;
        while(currPtr != NULL && r > currPtr->v){
            lastPtr = currPtr;
            currPtr = currPtr->nextPtr;
        }
        newPtr = malloc(sizeof(Node));
        newPtr->v = r;
        newPtr->nextPtr = NULL;
        if(lastPtr == NULL){
            *startPtr = newPtr;
        }
        else{
            lastPtr->nextPtr = newPtr;
            newPtr->nextPtr = currPtr;
        }
    }
}

void print(NodePtr start)
{
    while(start != NULL){
        printf("%d ", start->v);
        start = start->nextPtr;
    }
}

Answer 1

lastPtr должно быть инициализировано нулем в for -loop.

Рассмотрим && r > currPtr->v как ложное на 2-й (3-й ...) итерации цикла for. Учтите, что на предыдущей итерации цикл while был выполнен один или несколько раз, поэтому lastPtr имеет значение.

Затем на этой итерации, где && r > currPtr->v равно false, старое значение lastPtr используется в части else, где оно должно было быть нулевым.

Итак:

    for(int i = 0; i < N; i++){
        lastPtr = NULL;
        currPtr = *startPtr;

... а потом я запустил его в отладчике и обнаружил также:

    newPtr = malloc(sizeof(Node));
    newPtr->v = r;
    newPtr->nextPtr = currPtr;     // set it here
    if(lastPtr == NULL){
        *startPtr = newPtr;        // because here it is needed too
    }
    else{
        lastPtr->nextPtr = newPtr; // and no lomger needed here
    }

Я обнаружил случай, когда rand() вернул ноль и новый узел должен был быть вставлен впереди.

Answer 2

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

int comp( const void* a, const void* b)
{
     int a_int = * ( (int*) a );
     int b_int = * ( (int*) b );   
     if ( a_int == b_int ) return 0;
     else if ( a_int < b_int ) return -1;
     else return 1;
}

void gen(NodePtr *startPtr)
{
    NodePtr head, tail;
    int a[N] ;
    for(int i = 1; i < N; i++)
      a[i]=rand()%101;
    qsort(a,N,sizeof(N),comp);

    int i=0;
    // first node
    head = malloc(sizeof(Node));
    head->nextPtr=NULL;
    head->v=a[i];
    tail=head;        
    for(i = 1; i < N; i++){
      tail->nextPtr= malloc(sizeof(Node));
      tail=tail->nextPtr;
      tail->v=a[i];
      tail->nextPtr=NULL;
    }
    *startPtr=head;
}

Answer 3

Есть две проблемы.

1. Когда lastPtr == NULL, вы забыли установить newPtr->nextPtr на currPtr.Вам необходимо безоговорочно установить newPtr->nextPtr = currPtr.

2. Переменную lastPtr необходимо повторно инициализировать в NULL каждый раз вокруг цикла.

Оригинальный код:

    for(int i = 0; i < N; i++){
        currPtr = *startPtr;
        r = rand()%101;
        while(currPtr != NULL && r > currPtr->v){
            lastPtr = currPtr;
            currPtr = currPtr->nextPtr;
        }
        newPtr = malloc(sizeof(Node));
        newPtr->v = r;
        newPtr->nextPtr = NULL;
        if(lastPtr == NULL){
            *startPtr = newPtr;
        }
        else{
            lastPtr->nextPtr = newPtr;
            newPtr->nextPtr = currPtr;
        }
    }

Новый код:

    for(int i = 0; i < N; i++){
        currPtr = *startPtr;
        lastPtr = NULL; // <-- (re-)initialize lastPtr
        r = rand()%101;
        while(currPtr != NULL && r > currPtr->v){
            lastPtr = currPtr;
            currPtr = currPtr->nextPtr;
        }
        newPtr = malloc(sizeof(Node));
        newPtr->v = r;
        if(lastPtr == NULL){
            *startPtr = newPtr;
        }
        else{
            lastPtr->nextPtr = newPtr;
        }
        newPtr->nextPtr = currPtr; // <<-- set newPtr->nextPtr unconditionally
    }

Более надежное решение должно также проверять результат malloc.