Как добавить номер в отсортированный список ссылок?

Question

Я пытаюсь создать функцию в C для добавления чисел в упорядоченный связанный список, но у меня есть ощущение, что это можно сделать гораздо меньше строк.Есть ли пример?

Этот пример кода не работает:

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

struct listNode {
    int number;
    struct listNode *nextPtr;
};

typedef struct listNode LISTNODE;
typedef LISTNODE *LISTNODEPTR;
int main ()
{
    LISTNODE a = {16,NULL};
    LISTNODEPTR ptr = &a;
    printList(&a);
    insert(&ptr,23);
    insert(&ptr,10);
    insert(&ptr,12);
    insert(&ptr,15);
    printList(&a);
    return 0;
}

void insert(LISTNODEPTR *list, int number){
    if((**list).number > number){
    printf("lol2 %d",number);
        LISTNODE *newNode =  malloc(sizeof(LISTNODE));
        (*newNode).number  = number;
        (*newNode).nextPtr  =  (*list);
        *list = newNode;
    }else if((**list).nextPtr == NULL){
    printf("lol %d",number);
        LISTNODE *newNode =  malloc(sizeof(LISTNODE));
        (*newNode).number  = number;
        (*newNode).nextPtr  =  NULL;
        (**list).nextPtr = newNode;

    }else{
    printf("other %d\n",number);
        LISTNODE *listPtr = *list;
        LISTNODE *listPtr1 = (*listPtr).nextPtr;
        while((*listPtr1).number < number && (*listPtr).nextPtr != NULL ){
            printf("%d > %d\n",(*listPtr).number , number);
            listPtr = (*listPtr).nextPtr;
            listPtr1 = (*listPtr).nextPtr;
        }
        LISTNODE *newNode =  malloc(sizeof(LISTNODE));
        (*newNode).number  = number;
        if((*listPtr).nextPtr != NULL){
            (*newNode).nextPtr  =  listPtr1;
        }else{
            (*newNode).nextPtr  =  NULL;
        }
        (*listPtr).nextPtr = newNode;
    }
}

Answer 1

Да, это можно сделать намного короче:

void insert(LISTNODEPTR *list, int number)
{
    LISTNODE *newNode = malloc(sizeof *newNode);
    newNode->number = number;

    while (*list && (*list)->number < number)
    {
        list = &(*list)->nextPtr;
    }

    newNode->nextPtr = *list;
    *list = newNode;
}

Обратите внимание, что ваши printList строки в основном должны быть printList(ptr);

Answer 2

Одним из способов начать сокращение этого кода является поиск дублирования: то, что вы делаете в нескольких местах.

Например, независимо от того, где вы в конечном итоге вставляете новый узел, вам всегда придется его выделять и устанавливать его поле number, поэтому этот код:

    LISTNODE *newNode =  malloc(sizeof(LISTNODE));
    (*newNode).number  = number;

должно быть сделано один раз, в верхней части вашей функции.

Answer 3

некоторый псевдокод для вставки:

listNode *curNode = *list,*prevNode = 0, *newNode= 0;
while (curNode->nextPtr && number <= curNode->number)
{
   prevNode = curNode;
   curNode = curNode->nextPtr;
}
newNode = CreateNode(number);
newNode->nextPtr = curNode;

if (prevNode)
   prevNode->nextNode = newNode;
else
   *list = newNode;

Answer 4

Что ж, вам, вероятно, следует написать функцию InsertAfter, которая получает указатель на узел списка и новое значение, а затем

• Выделите новый узел со значением в нем и его nextptr, установленным на nextptr старого узла списка
• Измените nextptr старого узла списка, чтобы он указывал на новый узел

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