Связанный список C++
https://stackoverflow.com/questions/1812706
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я пытаюсь сделать связанный список похожим на тот, что здесь:
То есть иметь «голову», как я ее назвал первым, внутри другой структуры.Однако я обнаружил, что делаю это изменение.Усложняет добавление значений в структуру list_item.Я попробовал несколько вещей, чтобы проверить, работает ли это.Он компилируется, однако, когда я запускаю код, происходит сбой.Любая помощь здесь будет полезна.Я знаю, что причина сбоя в том, что я хочу указать new_node на linked_list.
#include <iostream>
using namespace std;
struct list_item
{
int key;
int value;
list_item *next;
};
struct list
{
struct list_item *first;
};
int main()
{
list *head;
list *new_node;
head = NULL;
head->first = NULL;
for(int i = 0; i < 10; i++)
{
//allocate memory for new_node
new_node = (list*)malloc(sizeof(list));
new_node->first = (list_item*)malloc(sizeof(list_item));
//adding the values
new_node->first->key = i;
new_node->first->value = 10 + i;
//point new_node to first;
new_node->first->next = head->first;
//point first to new_node;
head->first = new_node->first;
}
//print
list *travel;
travel->first = head->first;
int i = 0;
while(travel != NULL)
{
cout << travel->first->value << endl;
travel->first = travel->first->next;
}
return 0;
}
Решение
Вы создаете 10 списков, я думаю, вы можете попробовать сделать что-то вроде этого:
#include <iostream>
using namespace std;
struct list_item
{
int key;
int value;
list_item *next;
};
struct list
{
struct list_item *first;
};
int main()
{
//Just one head is needed, you can also create this
// on the stack just write:
//list head;
//head.first = NULL;
list *head = (list*)malloc(sizeof(list));
list_item *new_node = NULL;
head->first = NULL;
for(int i = 0; i < 10; i++)
{
//allocate memory for new_node
new_node = (list_item*)malloc(sizeof(list_item));
//adding the values
new_node->key = i;
new_node->value = 10 + i;
//if the list is empty, the element you are inserting
//doesn't have a next element
new_node->next = head->first;
//point first to new_node. This will result in a LIFO
//(Last in First out) behaviour. You can see that when you
//compile
head->first = new_node;
}
//print the list
list_item *travel;
travel = head->first;
while(travel != NULL)
{
cout << travel->value << endl;
travel = travel->next;
}
//here it doesn't matter, but in general you should also make
//sure to free the elements
return 0;
}
Вот что происходит.Сначала у вас есть только одна голова и никаких элементов.
head
|
|
V
NULL
Затем вы добавляете свой первый элемент.Убедитесь, что «new_node->next==NULL»:
head
|
|
V
node: ------------------> NULL
key = 0
value = 10
Затем вы добавляете еще один узел впереди, но добавляете свой первый узел к следующему узлу.вы перемещаете указатель с головы на новый узел
head:
first
|
|
V
node: ---------> node: -------------> NULL
key: 1 key: 0
value: 11 value: 10
и т. д.
Поскольку вы используете C++, вы можете рассмотреть возможность использования «нового» и «удалить».Просто замените
new_node = (list_item*)malloc(sizeof(list_item));
с
list *head = new list
Другие советы
Я думаю, вы хотите что-то более похожее на это:
#include <iostream>
#include <cstdlib>
using namespace std;
typedef struct tag_list_item
{
int key;
int value;
struct tag_list_item *next;
} list_item;
typedef struct
{
list_item *head;
} list;
int main()
{
list my_list;
list_item *new_node;
list_item *previous_node = NULL;
my_list.head = NULL;
for(int i = 0; i < 10; i++)
{
//allocate memory for new_node
new_node = (list_item*)malloc(sizeof(list_item));
//adding the values
new_node->key = i;
new_node->value = 10 + i;
if(previous_node == NULL)
{
my_list.head = new_node;
}
else
{
previous_node->next = new_node;
}
previous_node = new_node;
}
//print
list_item *iter = my_list.head;
while(iter != NULL)
{
cout << iter->value << endl;
iter = iter->next;
}
return 0;
}
Изменения заметки:
Для malloc я добавил:
#include <cstdlib>
Я изменил ваши структуры списков на typedefs, должен был объявить " next " использование тега, так как typedef на этом этапе не завершен
typedef struct tag_list_item
{
int key;
int value;
struct tag_list_item *next;
} list_item;
Я изменил название вашего списка на "my_list" и объявил это напрямую (без указателя). В этом случае вы можете просто назначить компилятору его автоматически в стеке.
list my_list;
Я сохраняю указатель на " предыдущий_узел " так что вы можете назначить " далее " указатель гораздо проще. Обратите внимание, что на первый выделенный узел указывает " head " указатель в структуре списка. Я считаю, что это традиционное имя для указателя на первый элемент в списке.
if(previous_node == NULL)
{
my_list.head = new_node;
}
else
{
previous_node->next = new_node;
}
previous_node = new_node;
Следующая строка выделяет память только для вашей структуры list . Список содержит только указатель, вы также должны выделить память для new_node-> gt; first перед назначением любому из его членов.
//allocate memory for new_node
new_node = (list*)malloc(sizeof(list));
head = NULL;
head->first = NULL;
Есть проблема. Вы не можете следовать за указателем и установить его в NULL, если сам указатель установлен в NULL.
Это должно быть
head = malloc(sizeof(list));
head->first = NULL;
Это должно исправить ваш код.
Надеюсь, это поможет, Billy3
РЕДАКТИРОВАТЬ: есть также проблема с вашим циклом FOR. Когда вы распределяете список, вы должны распределять сам список только один раз. Когда вы вставляете элемент, вы выделяете только list_item. Вы назначаете указатель списка члену, который принимает только указатель list_item;)
См. сообщение Гейба для демонстрации правильного поведения:)
Посмотрите на объявление структуры
struct list_item
{
int key;
int value;
list_item *next;
};
Это должно быть
struct list_item
{
int key;
int value;
struct list_item *next;
};
Надеюсь, это поможет, С наилучшими пожеланиями, Том
