Функция pop () связанного списка - PullRequest
Новая
       10

Функция pop () связанного списка

0 голосов
/ 24 апреля 2010

Рассмотрим следующий список:

[LinkNode * head - LinkNode * node1 - LinkNode * node2]

Я создаю стек FIFO. Я вызываю pop (), который я хочу открыть pop1. 

LinkNode::LinkNode(int numIn) {
    this->numIn = numIn;
    next = null;
}
.
.
.
int LinkNode::pop() {
    Link * temp = head->next;
    head = temp->next;
    int popped = head->nodeNum;
    delete temp;
    Return numOut;

Вопрос:
1) заголовок должен быть указателем или LinkNode *?
2) Ссылка * temp создается в стеке вызовов, и когда всплывающее окно заканчивается, временное удаление не удаляется автоматически?
3) Моя главная путаница в том, что значение temp-> next? Это указывает на node1.next, который равен node2?

Цените вашу помощь?

Моя ссылка на C ++ для программистов на Java от Weiss.

Ответы [ 3 ]

1 голос
/ 24 апреля 2010

Часто при реализации связанных списков, деревьев или других связанных структур данных часто полезно разделить реализацию на инкапсулирующий объект (LinkedList, Tree и т. Д.) И объект узла (LinkedListNode, TreeNode и т. Д.), Который позволяет один для реализации методов за пределами рассматриваемых узлов. Проблема с выталкиванием из узла состоит в том, что извлеченный узел становится недействительным. Инкапсуляция узлов в какой-либо более крупной структуре данных позволяет этой структуре данных выполнять извлечение извне, удаляя старый узел.

Еще одна вещь, которую следует рассмотреть, - это как будет вести себя поп, если для него не осталось предметов. Должно ли это бросить исключение? Должно ли это просто привести к неопределенному поведению?

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

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

В вашем поп-коде вы фактически удаляете слишком много элементов. Должно быть: 

int result = head->nodeNum; // extract the result
LinkNode* tmp = head; // save this so we can delete it
head = head->next; // move the head forward to the next item
delete tmp; // deallocate previous head
return result;

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

1 голос
/ 24 апреля 2010
  1. LinkNode * - указатель. Поэтому я не уверен, что вы спрашиваете.
  2. Переменная выходит из области видимости, но это не приводит к автоматическому удалению динамически распределенных данных. В C ++, если вы динамически распределяете данные (вызов new), вам нужно освободить их (вызов delete)
0 голосов
/ 26 апреля 2010

Хорошая ссылка с картинками здесь. Очень хорошие визуальные эффекты.

http://richardbowles.tripod.com/cpp/linklist/linklist.htm

...