C: Создание упорядоченного списка путем проверки 2 значений

Question

Я новичок в C, так что будьте терпеливы со мной, если увидите в моем коде действительно новичок!

Как часть домашней работы, мне нужно создать упорядоченный список для хранения некоторых данных. На данный момент я создал структуру, которая будет представлять каждый узел списка (firstNode - это глобальная переменная, которая указывает на первый узел списка):

typedef struct Node {
    struct Node *next;
    int id;
    int value;
}Node;

Node *firstNode = NULL;

После этого я создал функцию, которая вставляет новый узел в список, проверяя значения узлов. Узлы с меньшими значениями должны быть раньше других. Так что я сделал это:

void addNewNode(int nodeId, int nodeValue) {
    Node *newNode = (Node*) malloc(sizeof(Node));
    Node *temp, *tempPrev;
    newNode->id = nodeId;
    newNode->value = nodeValue;

    if(firstNode == NULL) {
        newNode->next = firstNode;
        firstNode = newNode;
    }
    temp = firstNode;
    tempPrev = NULL;
    while(temp->value < newNode->value) {
        tempPrev = temp;
        temp = temp->next;
    }
    if(tempPrev == NULL) {
        newNode->next = firstNode;
        firstNode = newNode;
    } 
    else {
        tempPrev->next = newNode;
        newNode->next = temp;
    }
}

Проблема с кодом выше заключается в том, что иногда происходит сбой программы, но я не могу найти ошибку!

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

Answer 1

Программа аварийно завершает работу, поскольку в состоянии цикла while вы не проверяете, равно ли значение temp нулю. Другими словами, если вы попытаетесь вставить новый узел с большим значением, чем все остальные, уже находящиеся в списке, temp достигнет конца списка (так что temp равен NULL), и вы попытаетесь получить значение этого узла ! Таким образом, исправление будет:

while(temp!=NULL && temp->value>newNode->value)
{
    ....
}

Что касается идентификатора узлов, вы можете расширить условие цикла while следующим образом:

while(temp!=NULL && (temp->value<newNode->value || (temp->value==newNode->value && temp->id<newNode->id))
{
    ....
}

Кроме того, первый оператор if, где вы проверяете, имеет ли firstNode значение NULL, в вашем случае не требуется. Если он равен NULL, программа не попадет в цикл while и сразу перейдет к первому оператору if после цикла while.

Кстати, хороший код для нового программиста на C: -)

Answer 2

1.

if(firstNode == NULL) {
        newNode->next = firstNode;
        firstNode = newNode;
        return; // done with inserting the first node...need not continue.
    }

2

// ensure temp is not null only then access its value.
while(temp && (temp->value < nodeId->value)) {
        tempPrev = temp;
        temp = temp->next;
    }

Answer 3

Я бы предложил создать пару тестовых случаев, которые проверяют ваши граничные условия (например, добавить элемент в пустой список; добавить элемент, который должен оказаться в начале существующего списка; добавить элемент, который должен быть в конце конец существующего списка; добавьте элемент, который должен оказаться где-то посередине существующего списка). Создайте функцию «print», которая будет печатать элементы списка в консоли для отладки. Это, по крайней мере, поможет вам сузить контекст вашей аварии. Одна возможность (я не знаю, сколько добавлений вы делаете) состоит в том, что программе не хватает памяти и происходит сбой malloc. Вы можете проверить это, потому что я думаю, что malloc возвращает NULL, если не удается выделить необходимую память.

Node *newNode = (Node*) malloc(sizeof(Node)); 
if(newNode == NULL)
{
  printf("Out of Memory!");
  return;
}

Answer 4

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

Answer 5

с одной стороны, у вас есть nodeID -> значение там. NodeID - это int, поэтому это не сработает.