LinkedList добавление элемента

Question

У нас есть проблема с нашим LinkedList в C. Когда я подсчитываю, сколько узлов должно быть в списке, я всегда получаю 1

LL count: 1

Это Добавить, посчитать и получить последний элемент кода списка:

void addLL(LL * head)
{
LL *newNode;
LL *tail = getLastNode(head);

newNode = malloc(sizeof(LL));
if(newNode != DEF_NULL)
{
    newNode->ID=-1;
    newNode->TCB=-1;
    newNode->next = DEF_NULL;

    if(!head) head = newNode;
    else tail->next = newNode;      
}   
}

LL * getLastNode(LL * head)
{
    LL *temp = head;
    while(temp->next != DEF_NULL)
    {
        temp = temp->next;
    }
    return temp;
}

CPU_INT32U countLL(LL * head)
{
    CPU_INT32U elements = 0;
    LL * temp = head;
    while(temp->next != DEF_NULL)
    {
        temp = temp->next;
        elements++;
    }
    return elements;
}

Это называется так:

addLL(list);
temp = countLL(list);       
Debug_LOG("LL count: %i", temp);

где LL * список; является глобальной переменной, а temp находится в локальной области видимости. Я надеюсь, что кто-нибудь может увидеть, где я ошибся

Привет, Сяак и Геррит

Answer 1

Я вижу несколько проблем в вашем коде:

• Вы всегда должны защищать операции со связанным списком, проверяя, является ли указатель списка действительным (то есть, не нулевым)
• Вы не можете разместить первый элемент в пустом списке из-за способа размещения первого нового элемента: вы меняете head но модификация не будет распространяться за пределы функции. Вы должны передать "указатель на указатель списка" (т.е. LL**), что эквивалентно "адресу LL*Посмотри, как я звоню addLL() и как я изменил его прототип и head назначение
• если ваш список имеет длину только один блок, он не будет учитываться при подсчете, только если есть преемник, посмотрите, как я изменил порядок выполнения условия do / while

Я предлагаю модифицированный код, который работает для 1, 2 или любой длины списка (я только что изменил CPU_INT32U в int чтобы быстро скомпилировать с MinGW, я мог бы иметь typedef'ined):

#include <stdio.h>

#define DEF_NULL 0

typedef struct tagL {
    int ID;
    int TCB;
    struct tagL *next;
} LL;

void addLL(LL ** head);
LL * getLastNode(LL * head);
int countLL(LL * head);

void addLL(LL ** head)
{
    LL *newNode;
    LL *tail = getLastNode(*head);

    newNode = malloc(sizeof(LL));
    if(newNode != DEF_NULL)
    {
        newNode->ID=-1;
        newNode->TCB=-1;
        newNode->next = DEF_NULL;

        if(!*head) 
            *head = newNode;
        else 
            tail->next = newNode;      
    }   
}

LL * getLastNode(LL * head)
{
    LL *temp = head;
    if (head){
        while(temp->next != DEF_NULL)
        {
            temp = temp->next;
        }
    }
    return temp;
}

int countLL(LL * head)
{
    int elements = 0;
    LL * temp = head;
    if (head){
        do {
            temp = temp->next;
            elements++;
        } while(temp != DEF_NULL);
    }
    return elements;
}

int main(int argc, char *argv[]){
    LL *list = 0;

    printf("LL test\n");
    addLL(&list);
    printf("length = %d\n", countLL(list));
    addLL(&list);
    printf("length = %d\n", countLL(list));
    addLL(&list);
    printf("length = %d\n", countLL(list));
}

Выход:

LL test
length = 1
length = 2
length = 3

Answer 2

CPU_INT32U countLL(LL * head){элементы CPU_INT32U = 0;LL * temp = head;while(temp->next!= DEF_NULL){temp = temp->next;elements++;} возвращать элементы;}

в этой функции вы объявляете элементы переменными как auto, поэтому их память освобождается сразу после выхода из функции, поскольку память теперь свободна для выделения другой переменной, поэтому может быть перезаписана, поэтому предыдущее значение cvalue будет потеряно

поэтому, чтобы избежать этого, используйте static при объявлении переменной..... поскольку память статических переменных освобождается только после выполнения всей программы, попробуйте....

Answer 3

void addLL(LL * head)
{
LL *newNode;
LL *tail = getLastNode(head);

Здесь есть проблема, если (глобальный) заголовок окажется NULL, он будет разыменован функцией getLastNode():

LL * getLastNode(LL * head)
{
    LL *temp = head;
    while(temp->next != DEF_NULL)

Вот temp->next != ... вызовет разыменование temp. Это может привести к разыменованию указателя NULL, если temp окажется NULL. (как в вызове с помощью функции вставки. Вы можете добавить дополнительный тест (или использовать указатели на указатели, которые чище):

while(temp && temp->next != DEF_NULL)

Обновление (чтобы показать, что указатель на версию указателя чище)

#include <stdlib.h>
#include <stdio.h>
#define DEF_NULL NULL
#define CPU_INT32U unsigned

typedef struct link {
        struct link *next;
        } LL;

LL *globhead=NULL;
LL **getTailPP(LL **ppHead);
CPU_INT32U countLL(LL * ptr);
void addLL(LL **ppHead);

void addLL(LL **ppHead)
{
ppHead = getTailPP(ppHead);

*ppHead = malloc(sizeof **ppHead);
    if(*ppHead != DEF_NULL)
    {
        // newNode->ID=-1;
        // newNode->TCB=-1;
        (*ppHead)->next = DEF_NULL;
    }
}

LL **getTailPP(LL **ppHead)
{
    for( ; *ppHead; ppHead = &(*ppHead)->next ) {;}
    return ppHead;
}

CPU_INT32U countLL(LL * ptr)
{
    CPU_INT32U elements = 0;
    for(; ptr != DEF_NULL; ptr=ptr->next) { elements++; }
    return elements;
}

int main()
{
unsigned count;

addLL( &globhead);
count = countLL (globhead);
printf("count = %u\n", count);

addLL( &globhead);
count = countLL (globhead);
printf("count = %u\n", count);

return 0;
}

Answer 4

В Windows нет ничего плохого в этой функции - странно...

Ideone также показывает хороший результат.

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

typedef struct LL{
    struct LL *next;
}LL;

LL * getLastNode(LL * head)
{
    LL *temp = head;
    while(temp->next != NULL)
    {
        temp = temp->next;
    }
    return temp;
}

void addLL(LL * head)
{
LL *newNode;
LL *tail = getLastNode(head);

newNode = malloc(sizeof(LL));
if(newNode != NULL)
{
    newNode->next = NULL;

    if(!head) head = newNode;
    else tail->next = newNode;      
}   
}

int countLL(LL * head)
{
    int elements = 0;
    LL * temp = head;
    while(temp->next != NULL)
    {
        temp = temp->next;
        elements++;
    }
    return elements;
}

int main() {
    LL *h = malloc(sizeof(*h));
    addLL(h);
    addLL(h);
    addLL(h);
    printf("%d\n", countLL(h)); // prints 3 as expected
}