Как сделать связанный список в использовании структур? - PullRequest
Новая
       27

Как сделать связанный список в использовании структур?

1 голос
/ 11 октября 2011

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

Допустим, у меня есть: 

struct element 
{
    int       val;
    element   *next;
};

Элемент * next является указателем на элемент, который будет использоваться для соединения элементов вместе, чтобы сформировать связанный список.

Я также понял, что вам нужно что-то связать, чтобы вы не потеряли свой список.Мой профессор описывает это как след из воздушных шаров, и если у вас нет «привязки», ваш список может потеряться.

Поэтому я начну с создания указателя «привязки»: 

element first;
first -> *next = 0; // or null

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

Как-то так? 

element addMe;
addMe -> val = 100;

first -> next = *addMe;

Это верно??

Что бы я сделал, чтобы добавить что-то в непустой список?

Спасибо за потраченное время!

Редактировать: Это не домашняя работа.Мы просмотрели связанные списки и сделали с ними задание.Я не получил очень хорошую оценку по заданию, поэтому я стараюсь укрепить свое понимание перед следующим заданием.Мы будем снова использовать связанные списки.

Edit2: Спасибо!

Я не знаю, будет ли это рассматриваться как "домашняя работа" или нет.Лично я так не думаю, учитывая, что я не буду использовать код, который я разместил здесь.

Ответы [ 4 ]

4 голосов
/ 11 октября 2011

При использовании односвязных списков эффективный способ добавления новых элементов - это поместить их в начало списка.Для вашего дизайна это будет: 

element newHead;
newHead.next = &list;

Вы заметите, что newHead теперь является первым элементом, а list больше не представляет весь список.Это приводит к более функциональному стилю программирования, в котором вы постоянно создаете новые списки (см .: cons функция в Лиспе).

Процедурные языки, такие как C ++, обычно используют некоторую структуру-обертку, такую ​​как:* 

struct list
{
    element * first;
    void prepend(element * elt)
    {
        elt->next = first;
        first = elt;
    }
}

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

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

0 голосов
/ 23 февраля 2012

у вас должен быть первый указатель или указатель головы, или как вы там его называете.это указатель, который равен NULL, когда ваш связанный список пуст.Но когда вы добавляете первый элемент в связанный список, добавьте адрес узла этих элементов и в указатель «прослушать / первый».и начиная со 2-го узла, добавьте адрес новых узлов в конец списка (узел, чей следующий указатель равен NULL) или в звезду, изменив head / first и затем добавив текущую head к следующей head.Я не знаю, помогла ли такая теория.Просто следуйте примерам или напишите свой собственный код.и если вы столкнетесь с ошибками, напишите об этом на SO.Я думаю, связанный список, очередь, стек и т. д. доступны во всех книгах на c или c ++.

или поиск связанного списка в SO.

для начала: Простой C ++ связанный список

0 голосов
/ 11 октября 2011

Обычно вы храните указатель на первый узел: 

element* first = &first_node; // this "ties" it off

first->val = 5; // set first node value to 5
first->next;    // pointer to next node

Если ваш список пуст, то сначала должно быть установлено NULL.

Кроме того, последний узел в вашем списке должен иметь next со значением NULL.

0 голосов
/ 11 октября 2011

Если вы хотите добавить в начало списка 

struct element *el = (element *) malloc(sizeof(struct element));
el->val = 100;
el->next = first;

Теперь el - это первый элемент, а first - второй.

В вашем примере вы перезаписалипервый элемент следующий элемент с новым.Вы разрезаете список и вставляете новый элемент в качестве второго.Все после первого теперь не в списке (который также является списком, но вы не можете получить к нему доступ, поскольку вы перезаписали указатель на этот третий элемент).

Чтобы добавить в конец списка, выполните итерацию

struct element *e;

e = first;
while (e->next !=0)
  e = e->next;

// here e is the last element. Allocate a new one and point e->next to it. And set this new one next to 0.
...