Связанные списки
Это пожалуй самая трудная для понимания тема. Но не стоит сомневаться в себе. Время и ваше упорство доведут вас до атомов понимания. Для того, чтобы полностью понять связанные списки, их нужно не один раз создать. Первые разы наверняка с использованием готовых наработок. Я же в этой статье постараюсь дать вам теоретическую часть как можно доходчиво.
И так связанные списки представляют собой подобие безразмерных(ограничено
только оперативной памятью компьютера)динамических массивов. Во многих случаях
можно обойтись динамическими массивами, но когда размерность массива будет часто
изменяться, то работоспособность вашей программы резко снизится. Связанные
списки в этом случае работают намного быстрее, имеют гибкую структуру
размерности, позволяют использовать нестандартные решения. Основной критерий, по
которому лучше отказаться от массивов в своей программе в пользу связанных
списков, это заранее неизвестное большое кол-во хранимой информации.
Связанные списки не имеют упорядоченную как у массива область памяти. У
массива четкая структура: все его ячейки последовательно идут друг за другом в
памяти. Например для байтового массива aa(0) - 3210000 ,
aa(1) - 3210001 .
Пункты связанного списка могут быть
разбросаны, они не имеют индексов. Все что у них есть это точки отсчета: начало
или конец листа, а также информация: адрес следующего и предыдущего. И для
того чтобы нам перемещаться по ячейкам связанного списка (читать, записывать) ,
нам нужно его как бы "связать", точнее выстроить цепочку. Принцип цепочки как
нельзя кстати подойдет для объяснения. Звенья цепи соединенные между собой,
образуют целое. Каждое звено (кроме первого и последнего) соединено с предыдущим
и следующим. Как вы понимаете у первого нет предыдущего , а у последнего
нет следующего. Однако если мы имеем первое звено, мы легко доберемся до
последнего и наоборот. Этот принцип заложен в связанных списках и является его
основой.
Каждый пункт связанного списка представляет собой объект, который
должен содержать как минимум такую информацию:
- адрес предыдущего пункта
- адрес следующего пункта
- значение, ради которого мы его и создаем
Имея пункт с такой информацией, мы можем создать временный объект класса, и присвоить ему адрес предыдущего или следующего объекта, а далее получать значение его свойства. Давайте перейдем к примеру:
'---------Класс связанного списка------------ '-------------------------------------------- 'подкласс B Type B next_ As B Ptr =0 prev_ As B Ptr =0 value As Byte =0 End Type 'подкласс A (главный) Type A First_ As B Ptr =0 last_ As B Ptr =0 Declare Sub Add_last(As Byte) End Type ' метод добавления пункта в конец Sub A.Add_last(value_ As Byte) Dim temp As B Ptr = New B temp->value=value_ If first_=0 Then first_=temp Else last_->next_=temp temp->prev_=last_ Endif last_ = temp End Sub '----------конец класса------------- '----------------------------------- '------использование класса---------- Dim list As A Ptr = New A list->Add_last(10) list->Add_last(20) list->Add_last(30) ? list->First_->value ? list->First_->next_->value ? list->First_->next_->next_->value Delete list->First_->next_->next_ Delete list->First_->next_ Delete list->First_ Delete list Sleep
В нашем примере реализован класс, имеющий два подкласса (A и B) , а так же
один метод добавления новых пунктов со значением в связанный список. Для чего
сделаны два подкласса? Обратите внимание на содержимое подклассов. Подкласс A
содержит два свойства first_ и last_ , а так же один метод. По сути подкласс A
является главным, именно он создает начальный объект и задает начальную и
конечную точку листа. Ведь без сомнения у связанного списка как и у цепочки не
может быть нескольких начал и концов. У них есть одно начало и один конец. Но
начальный и конечный пункт списка, такие же как и остальные, поэтому им
присваивается тип такой же как всем остальным. Разница лишь в том, что у
начального предыдущий равен 0 , а у конечного следующий равен нулю. И это нам
сослужит нам хорошую службу в будующем. К примеру находясь по середине списка,
мы не знаем сколько пунктов надо отшагать назад или вперед, чтобы дойти до
начала или конца и не вылезти за рамки дозволенной памяти. Как раз нуль
присвоенный для предыдущего или следующего и есть тот бортик. Мы можем программу
при переходе на следующий пункт спрашивать: не равен ли он нулю. Если равен,
значит уперлись в начало или в конец.
Каждый новый созданный пункт объекта
имеет свойства , реализованные в подклассе B. На самом деле мы создаем при
добавлении новых пунктов новые объекты, правда не имеющие методов. А потом
свойствам (Prev_ и Next_) этих объектов, присваиваем адреса предыдущих и
следущих объектов и так мы их связываем. В любой момент времени мы можем
поменять у нужных пунктов адреса предыдущих и следующих объектов, и таким
образом можем перемещать их по списку, удалять ненужные или же сортировать.
Обратите внимание на то, что свойства Next_ , Prev_ имеют тип подкласса B
, таким образом они по сути являются полноценными членами листа: они так же при
надобности могут иметь в свойствах адреса предыдущего пункта, следующего пункта
и значение типа Byte. Вы можете подумать, что получается бесконечность: Next_
имеет тип B , который в свою очередь имеет свойство Next_ которое опять имеет
тип B и так до посинения. На самом деле cвойство Next_ не имеет силы пока мы не
выделим ему память. По сути мы только закладываем такую вероятную возможность,
но реализуем только то, что нам необходимо. Примерно тоже что с мозгом человека,
он не работает на всю катушку, но такая возможность заложена.
При использовании класса, мы сначала должны создать главный объект на базе подкласса A , для реализации точек отсчета и использования метода. Это мы как раз и делаем командой:
Dim list As A Ptr = New A
Команда New - выделение памяти
Команда Delete - удаление объекта и очистка
памяти
Далее с помощью метода Add_Last происходит создание и добавление(связывание) новых пунктов( у нас добавляется три пункта).
В методе Add_last реализуется (построчно):
- выделение памяти для нового созданного объекта на базе подкласса B
- занесение значения типа Byte в одно из свойств объекта
- тест на имеющийся первый пункт списка
- если нет ни одного пункта , то новосозданный становится первым
- если первый пункт уже существует, тогда адресу, который являлся последним в свойство Next_ заносим адрес новосозданного пункта , а так же новосозданному пункту в свойство Prev_ заносим адрес бывшего последнего.
- делаем новосозданный последним
Далее имея под рукой точку отсчета - первый пункт, мы от него пляшем,
доставая значения из свойства value.
Первый объект располагается по адресу
list->First_ , а его свойство value будет располагаться по адресу
list->First_->value . Второй объект у него записан в свойстве Next_ ,
поэтому адрес второго будет: list->First_->next_ и значение в свойстве
value будет находится по адресу list->First_->next_->value и так же
рассматривается третий пункт.
В конце , поскольку нам уже не нужны более созданные объекты, мы их удаляем командой Delete .
Сказать по чести добавление пунктов у нас сделано более или менее нормально, но получение значений реально неудобно, ведь так? Давайте автоматизируем, добавив метод вывода всех значений в окно консоли. Перепишем пример так:
'---------Класс связанного списка------------ '-------------------------------------------- 'подкласс B Type B next_ As B Ptr =0 prev_ As B Ptr =0 value As Byte =0 End Type 'подкласс A (главный) Type A First_ As B Ptr =0 last_ As B Ptr =0 Declare Sub Add_last(As Byte) Declare Sub All() End Type ' метод добавления пункта в конец Sub A.Add_last(value_ As Byte) Dim temp As B Ptr = New B temp->value=value_ If first_=0 Then first_=temp Else last_->next_=temp temp->prev_=last_ Endif last_ = temp End Sub ' метод вывода всех значений Sub A.ALL() Dim temp As B Ptr = first_ Do ? temp->value temp=temp->next_ Loop While temp<>0 End Sub '----------конец класса------------- '----------------------------------- '------использование класса---------- Dim list As A Ptr = New A list->Add_last(10) list->Add_last(20) list->Add_last(30) list->All Delete list->First_->next_->next_ Delete list->First_->next_ Delete list->First_ Delete list Sleep
Что хорошо в нашем классе, так это то, что не надо шибко ничего
переписывать. Достаточно добавить декларацию метода в подкласс A и реализовать
этот метод.
По сути в нем сложного ничего нет. Мы создаем временный объект,
которому присваиваем адрес первого пункта нашего связанного списка. А далее с
помощью свойств Next_ переходим до последнего имеющегося пункта. Вот тут как раз
и видна вся полезность нашего нуля (бортика), о котором мы выше вели речь.
Обязательно рекомендую вам самим переписать пример вывода всех значений с конца
списка, а так же будет неплохо если вы автоматизируете очистку всех объектов,
потому как очищать тем способом, который в нашем примере неудобно. Кстати
неплохо будет если вы для метода очистки сумеете применить деструктор, о котором
мы вели речь в нашей прошлой статье.
Я попробовал объяснить так, как я
понимаю данную тему, но я уверен, что большинству из вас многое будет непонятно.
Именно поэтому я еще раз говорю, пока вы сами не создадите связанный список
несколько раз, все ваши поиски и чтения мануалов, будут только лишний раз
засорять мозги. Берите как платформу пример из этой статьи и начинайте строить
свой список с различными методами:
- добавление в начало списка
- перемещение пунктов по списку
- удаление пунктов из списка, и т. д.
Возникнут какие то недопонимания, загляните в исходник моей библиотеки window9, который идет тандемом со связанным списком Linked_list. В нем реализованы все часто используемые методы.
Данная глава об ООП исчерпала себя, все те вещи, которые известны мне, описаны в этих четырех статьях.
Всего доброго!
содержание | назад | вперед
