Использование malloc для создания связанного списка

Question

Я использовал malloc, чтобы выделить новые узлы в списке, но я столкнулся с ошибкой с определенной частью моего кода; следующее решение относится только к стиранию и вставив

#include <stdio.h> 
#include <malloc.h> 

struct Node{ 
    int value; 
    struct Node * Next; 
    struct Node * Previous; 


}; 
typedef struct Node Node; 
struct List{ 
    int Count; 
    int Total; 
    Node * First; 
    Node * Last; 
}; 
typedef struct List List; 
List Create(); 
void Add(List a,int value); 
void Remove(List a,Node * b); 
List Create() 
{ 
    List a; 
    a.Count=0; 
    return a; 

} 

void Add(List a,int value) 
{ 
    Node * b = (Node *)malloc(sizeof(Node)); 
    if(b==NULL) 
     printf("Memory allocation error \n"); 
    b->value=value; 
    if(a.Count==0) 
    { 
     b->Next=NULL; 
     b->Previous=NULL; 
     a.First=b; 

    } 
    else 
    { 
     b->Next=NULL; 
     b->Previous=a.Last; 
     a.Last->Next=b; 

    } 
    ++a.Count; 
    a.Total+=value; 
    a.Last=b; 
    } 
void Remove(List a,Node * b) 
{ 
    if(a.Count>1) 
    { 
     if(a.Last==b) 
     { 
      b->Previous->Next=NULL; 
     } 
     else 
     { 
      b->Previous->Next=b->Next; 
      b->Next->Previous=b->Previous; 
     } 

     } 
    free(b); 
    } 

в функции удаления, в последнем еще состоянии, я не уверен, является ли или не использовать b-> Далее-> Предыдущее в порядке, и будет работать; при использовании оператора ->, я обращаюсь к указателю узла или его значению?

Answer 1

Короткий ответ: Да, b->Next->Previous в порядке - это struct Node*, точно так же как правая сторона b->Previous.

Я думаю, что ваша ошибка лежит в обработке Count: Увеличивает на Add(), но Remove() не уменьшает его. Фактически, поскольку самому списку нужно только знать, пуст он или нет, вы можете удалить его, а вместо этого посмотреть, a.First == NULL. (Ваш a.Count == 1 тест также может быть заменен a.First != NULL && a.First->Next == NULL тестами.)

Если вы подтверждаете Count в вас API, вы можете добавить его обратно, когда у вас есть сам список работает. Тот же «remove-then-add-back» может быть полезен с Total. Подумайте об обоих из них как кэш.

Даже лучшим решением было бы реализовать циклический список:

struct List 
{ 
    Node Anchor; 
    //... 
}; 

List Create() 
{ 
    List l; 
    l.Anchor.Next = l.Anchor.Previous = &l; 
    return l; 
} 

bool IsEmpty(List const* l) 
{ 
    // Both or neither point at 'l'. 
    assert((l->Anchor.Next == l) == (l->Anchor.Previous == l)); 
    return l->Anchor.Next == l; 
} 

// Add a node 'n' to some list after 'ln'. 
void AddAfter(Node* n, Node* ln) 
{ 
    n->Previous = ln; 
    n->Next = ln->Next; 
    n->Next->Previous = n->Previous->Next = n; 
} 

Node* Remove(Node* n) 
{ 
    n->Previous->Next = n->Next; 
    n->Next->Previous = n->Previous; 
    n->Next = n->Previous = n; // nice and proper 
    return x; 
} 

Теперь вам больше нужны специальные случаи для пустых списков. Я позволю Remove() вернуть сам узел, чтобы упростить перемещение узлов между списками (AddAfter(Remove(somenode), &otherlist.Anchor)) или удалить и удалить заметки (free(Remove(somenode))).

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