От начального до среднего уровня: Очереди, списки и деревья (IV)

Введение

В предыдущей статье От начального до среднего уровня: очереди, списки и деревья (III) мы рассказали всё основное о том, что на самом деле представляет собой связный список. И мы увидели, что с помощью простого изменения в коде мы могли бы построить двусвязный список или односвязный список. Это то, что многие считают сложным делом. Однако материал, рассмотренный в предыдущей статье, не демонстрирует всех возможностей, которые предоставляет связный список. Также он не объясняет, почему во многих случаях это лучший вариант, когда нужно реализовать систему для анализа больших объёмов данных.

Следует помнить, что изначально эти данные размещались в массивах. Однако использование массивов может сделать наш код довольно затратным с точки зрения производительности во время его выполнения. Чтобы решить именно этот вопрос, учёные и исследователи в области data science разработали механизм, который объясняется в этих статьях. Помните, что здесь я стараюсь объяснять вещи максимально просто и доступно.

Итак, представленный до настоящего момента механизм позволяет нам только вставлять и удалять значения, находящиеся на концах связного списка. Однако нам часто приходится добавлять и удалять значения в промежуточных позициях. Именно данный механизм и остается без объяснения, поскольку он ещё не реализован. Хорошо, давайте теперь продолжим наш ритуал, который заключается в устранении любых отвлекающих факторов, которые могут помешать вам сосредоточиться на том, что мы рассмотрим в статье. Давайте начнём реализацию последней части, чтобы связный список стал полностью функциональным. Как обычно, мы перейдем к новой теме, чтобы начать наше путешествие по увлекательному миру программирования.

Очереди, списки и деревья (IV)

В предыдущей статье мы завершили обзор кодом, который приведен ниже:

01. //+------------------------------------------------------------------+
02. #property copyright "Daniel Jose"
03. //+------------------------------------------------------------------+
04. template <typename T> class stList
05. {
06.     private:
07. //+----------------+
08.         T info;
09.         stList <T>  *prev,
10.                     *start;
11. //+----------------+
12.     public:
13. //+----------------+
14.         stList(void)
15.             :prev(NULL),
16.             start(NULL)
17.         {}
18. //+----------------+
19.         void Store(T arg, const ENUM_FILE_POSITION pos = SEEK_END)
20.         {
21.             stList <T> *loc;
22. 
23.             loc = new stList <T>;
24. 
25.             (*loc).info = arg;
26.             (*loc).prev = NULL;
27.             switch(pos)
28.             {
29.                 case SEEK_SET:
30.                     (*loc).start = start;
31.                     (*start).prev = loc;
32.                     start = loc;
33.                     break;
34.                 case SEEK_END:
35.                     if (prev != NULL) (*prev).start = loc;
36.                     (*loc).prev = prev;
37.                     prev = loc;
38.                     start = (start == NULL ? loc : start);
39.                     break;
40.             }
41.         }
42. //+----------------+
43.         bool Restore(T &arg, const ENUM_FILE_POSITION pos = SEEK_END)
44.         {
45.             stList <T> *loc = NULL;
46. 
47.             if ((prev == NULL) || (start == NULL))
48.                 return false;
49. 
50.             switch (pos)
51.             {
52.                 case SEEK_SET:
53.                     loc = start;
54.                     start = (*loc).start;
55.                     break;
56.                 case SEEK_END:
57.                     loc = prev;
58.                     prev = (*loc).prev;
59.                     break;
60.             }
61.             arg = (*loc).info;
62. 
63.             delete loc;
64. 
65.             return true;
66.         }
67. //+----------------+
68.         void Debug(void)
69.         {
70.             Print("===== DEBUG =====");
71.             for (stList <T> *loc = prev; loc != NULL; loc = (*loc).prev)
72.                 PrintFormat("0x%06X ->> 0x%06X <<- 0x%06X = [%d]",(*loc).start, loc, (*loc).prev, (*loc).info);
73.             Print("=================");
74.         }
75. //+----------------+
76. };
77. //+------------------------------------------------------------------+
78. void OnStart(void)
79. {
80.     stList <char> list;
81. 
82.     list.Store(10);
83.     list.Store(84);
84.     list.Store(-6);
85.     list.Store(47, SEEK_SET);
86. 
87.     list.Debug();
88. 
89.     for (char info; list.Restore(info, SEEK_SET);)
90.         Print(info);
91. };
92. //+------------------------------------------------------------------+

Код 01

Данный код позволяет нам создать список, который ведет себя как стек, или список, работающий по принципу FIFO (первым вошел — первым вышел). Всё в очень простой форме. Для получения более подробной информации обратитесь к предыдущей статье. Однако, хотя эта возможность уже делает код 01 довольно полезным для решения различных задач, в нём отсутствует механизм для вставки или удаления элементов списка, которые не находятся на концах. Иными словами: код 01 позволяет нам удалять или добавлять только первый или последний элемент списка, но никогда — промежуточный.

Тем не менее, в предыдущей статье я предложил вам решить данную задачу. Идея заключалась в том, чтобы вы могли проверить, насколько хорошо вы поняли объяснения и примеры, представленные в статье. Если вы справились с этим, можете себя поздравить. Хотя я и дал несколько подсказок, для начинающих это всё равно не так просто. Это связано с тем, что необходимо продумать, как решить определённые детали реализуемого кода.

В любом случае, удалось ли вам решить задачу, предложенную в предыдущей статье, или нет, здесь мы рассмотрим моё предложение по решению. Помните, что цель носит образовательный характер. Итак, приступим к работе.

Для начала давайте рассмотрим результат выполнения кода 01. Результат показан ниже.

Изображение 01

Идея в том, чтобы сначала удалить одно из этих значений. В данном случае значение 84 или значение 10 без значительного изменения кода 01 и без копирования списка, показанного на изображении 01, в другое место памяти. Простейший способ сделать это — изменить значения prev и start самого списка, чтобы удалить нужный элемент. Это основная идея. Но как это сделать? Если вы посмотрите на изображение 01, вы заметите, что в разделе, где мы отлаживаем список, показано, как связываются адреса. Предположим, мы хотим удалить элемент, значение которого равно 84.

Если вы посмотрите на изображение 01, вы увидите, что адрес, по которому находится этот элемент, — 0x300000; обратите внимание на среднюю колонку. Предыдущий адрес — 0x200000, а последующий — 0x400000. На основе данной информации мы можем определить способ удаления элемента со значением 84: для этого нам нужно, чтобы предыдущий элемент 10 указывал на следующий элемент -6, а элемент со значением -6 указывал на 10. Таким образом, элемент со значением 84 можно без проблем удалить из списка.

Думаю, теперь вы знаете, что нам нужно сделать. Чтобы вы увидели, как это делается на практике, давайте рассмотрим код, который удаляет именно этот элемент 84, показанный ниже:

001. //+------------------------------------------------------------------+
002. #property copyright "Daniel Jose"
003. //+------------------------------------------------------------------+
004. template <typename T> class stList
005. {
006.     private:
007. //+----------------+
008.         T info;
009.         stList <T>  *prev,
010.                     *start;
011. //+----------------+
012.     public:
013. //+----------------+
014.         stList(void)
015.             :prev(NULL),
016.             start(NULL)
017.         {}
018. //+----------------+
019.         void Store(T arg, const ENUM_FILE_POSITION pos = SEEK_END)
020.         {
021.             stList <T> *loc;
022. 
023.             loc = new stList <T>;
024. 
025.             (*loc).info = arg;
026.             (*loc).prev = NULL;
027.             switch(pos)
028.             {
029.                 case SEEK_SET:
030.                     (*loc).start = start;
031.                     (*start).prev = loc;
032.                     start = loc;
033.                     break;
034.                 case SEEK_END:
035.                     if (prev != NULL) (*prev).start = loc;
036.                     (*loc).prev = prev;
037.                     prev = loc;
038.                     start = (start == NULL ? loc : start);
039.                     break;
040.             }
041.         }
042. //+----------------+
043.         bool Restore(T &arg, const ENUM_FILE_POSITION pos = SEEK_END)
044.         {
045.             stList <T> *loc = NULL;
046. 
047.             if ((prev == NULL) || (start == NULL))
048.                 return false;
049. 
050.             switch (pos)
051.             {
052.                 case SEEK_SET:
053.                     loc = start;
054.                     start = (*loc).start;
055.                     break;
056.                 case SEEK_END:
057.                     loc = prev;
058.                     prev = (*loc).prev;
059.                     break;
060.             }
061.             arg = (*loc).info;
062. 
063.             delete loc;
064. 
065.             return true;
066.         }
067. //+----------------+
068.         bool Exclude(const T arg)
069.         {
070.             stList <T>  *loc = start,
071.                         *ptr = NULL;
072. 
073.             for (; loc != NULL; ptr = loc, loc = (*loc).start)
074.                 if ((*loc).info == arg) break;
075. 
076.             if (loc == NULL) return false;
077. 
078.             (*ptr).start = (*loc).start;
079.             (*loc).start.prev = ptr;
080.             
081.             delete loc;
082. 
083.             return true;
084.         }
085. //+----------------+
086.         void Debug(void)
087.         {
088.             Print("===== DEBUG =====");
089.             for (stList <T> *loc = prev; loc != NULL; loc = (*loc).prev)
090.                 PrintFormat("0x%06X ->> 0x%06X <<- 0x%06X = [%d]",(*loc).start, loc, (*loc).prev, (*loc).info);
091.             Print("=================");
092.         }
093. //+----------------+
094. };
095. //+------------------------------------------------------------------+
096. void OnStart(void)
097. {
098.     stList <char> list;
099. 
100.     list.Store(10);
101.     list.Store(84);
102.     list.Store(-6);
103.     list.Store(47, SEEK_SET);
104. 
105.     list.Debug();
106.     list.Exclude(84);
107.     list.Debug();
108. 
109.     for (char info; list.Restore(info, SEEK_SET);)
110.         Print(info);
111. };
112. //+------------------------------------------------------------------+

Код 02

А теперь внимание. Данный код 02 реализует именно то, что объяснялось совсем недавно. Иными словами, при выполнении строки 106 вызывается функция, которая удаляет элемент со значением 84. Прежде чем подробно рассматривать работу функции в строке 68, давайте посмотрим на выполнение кода 02. Результат показан ниже.

Изображение 02

На изображении 02 довольно ясно видно то, что происходит. Если вы посмотрите на значения, которые были выведены из-за строки 105, вы заметите, что при выполнении строки 107 адреса элементов -6 и 10 изменяются. Таким образом, элемент со значением 84 больше не входит в список. Но подождите, куда делся элемент со значением 84? Что ж, уважаемый читатель, этот элемент был удален. Давайте теперь рассмотрим код, который выполняет именно эту задачу, так вы всё поймете.

Чтобы максимально упростить объяснение и избежать путаницы между связным списком и чем-либо ещё, мы на начальном этапе будем работать только со значениями элементов. Таким образом, функция в строке 68 получит значение элемента, который мы хотим удалить из связного списка. Поскольку мы не знаем, где в списке находится этот элемент, так как он может быть где угодно, мы инициализируем некоторые вспомогательные переменные в строках 70 и 71. Теперь начнём поиск элемента в списке. Поиск выполняется в цикле на строке 73. Когда элемент будет найден, строка 74 завершит цикл.

Также может случиться, что элемент не будет найден. В этом случае цикл завершится, когда в списке не останется других элементов. По этой причине нам нужна строка 76, чтобы проверить, дошли ли мы до конца списка или нашли нужный элемент, который необходимо удалить. Если мы находим элемент, который собираемся удалить, мы выполняем следующие строки. Иначе функция удаления завершится.

Итак, теперь переходим к той части, которая многих сбивает с толку. Поскольку у элемента есть предыдущий и следующий узлы, мы должны напрямую связать предыдущий узел со следующим. Только таким образом мы сможем удалить найденный элемент. Для создания данной связи нам нужны строки 78 и 79. После установления связи элемент можно удалить. Удаление происходит в строке 81. В результате, связный список продолжает работать безупречно, как будто ничего не изменилось.

Впрочем, это была самая лёгкая часть. Постарайтесь очень хорошо понять то, что объяснялось до настоящего момента, потому что дальше начинается та часть, из-за которой многие люди желают отправить в ад тех, кто создал или реализовал концепцию связного списка. Настолько велика путаница, которую многие создают в том, что мы увидим дальше.

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

В предыдущей статье я объяснил, что связный список можно рассматривать как массив, и также объяснил, почему появились связные списки. Поскольку связный список можно понимать как массив, наиболее практично указывать индекс значения, которое мы хотим удалить. Представьте следующую ситуацию: вы можете работать с любым набором значений и, хотя вы не знаете, какое значение нужно удалить, вы, скорее всего, знаете, где оно находится. Разве не было бы гораздо практичнее указывать индекс нужного значения? На самом деле, уважаемый читатель, так оно и есть. Однако есть небольшая проблема. И она видна уже в представленном коде.

Для пояснения воспользуемся кодом 02 в качестве примера. Обратите внимание на следующее: в строке 100 мы начинаем наш список со значения 10; затем вставляем значение 84, за которым следует значение -6. Однако значение 47 было помещено перед элементом со значением 10. Как мы увидим позже, в любое место списка можно было бы вставить множество других значений. Но пока давайте сосредоточимся на этих значениях и этой проблеме. Вопрос: на какой позиции находится значение 84? Если присмотритесь, то увидите, что оно находится во втором индексе. Помните, что нумерация начинается с нуля. Однако если вы посмотрите на код, не понимая его, вы подумаете, что значение 84 находится по индексу один. Это связано с тем, что он добавляется после элемента со значением 10, но это было бы верно, если бы не строка 103, где мы добавляем элемент со значением 47 ПЕРЕД элементом со значением 10. Именно подобные вещи вызывают большую путаницу среди многих новичков.

Есть и вторая проблема, менее сложная. В зависимости от того, как вы обходите связный список, вы можете в итоге удалить не тот элемент. Это происходит, когда список проходится от конца к началу. По этой причине при определении первого и последнего элемента необходимо проявлять особую осторожность. Это может показаться глупостью, но если вы когда-либо создадите круговой связный список, такого рода ситуация может сделать реализацию действительно очень запутанной. Хотя круговые связные списки не слишком распространены именно из-за путаницы с определением первого элемента, возможно, вам понадобится создать именно такой. И если это произойдёт, будьте осторожны при реализации кода.

Теперь мы знаем о некоторых опасностях, с которыми нам предстоит столкнуться. А ещё мы уже знаем, как визуализировать связный список, чтобы понять, насколько он похож на массив. Итак, мы можем перейти к самой интересной части, а именно к реализации кода, который будет использовать индексы вместо значений. Соответствующий код показан ниже:

001. //+------------------------------------------------------------------+
002. #property copyright "Daniel Jose"
003. //+------------------------------------------------------------------+
004. template <typename T> class stList
005. {
006.     private:
007. //+----------------+
008.         T info;
009.         stList <T>  *prev,
010.                     *start;
011.         uint        counter;
012. //+----------------+
013.         bool RemoveNode(stList <T> *arg)
014.         {
015.             delete arg;
016.             counter--;
017. 
018.             return true;
019.         }
020. //+----------------+
021.     public:
022. //+----------------+
023.         stList(void)
024.             :prev(NULL),
025.             start(NULL),
026.             counter(0)
027.         {}
028. //+----------------+
029.         void Store(T arg, const ENUM_FILE_POSITION pos = SEEK_END, const uint index = 0)
030.         {
031.             stList <T> *loc;
032. 
033.             loc = new stList <T>;
034. 
035.             (*loc).info = arg;
036.             (*loc).prev = NULL;
037.             switch(pos)
038.             {
039.                 case SEEK_SET:
040.                     (*loc).start = start;
041.                     (*start).prev = loc;
042.                     start = loc;
043.                     break;
044.                 case SEEK_CUR:
045.                     break;
046.                 case SEEK_END:
047.                     if (prev != NULL) (*prev).start = loc;
048.                     (*loc).prev = prev;
049.                     prev = loc;
050.                     start = (start == NULL ? loc : start);
051.                     break;
052.             }
053.             counter++;
054.         }
055. //+----------------+
056.         bool Restore(T &arg, const ENUM_FILE_POSITION pos = SEEK_END)
057.         {
058.             stList <T> *loc = NULL;
059. 
060.             if ((prev == NULL) || (start == NULL))
061.                 return false;
062. 
063.             switch (pos)
064.             {
065.                 case SEEK_SET:
066.                     loc = start;
067.                     start = (*loc).start;
068.                     if (start != NULL)
069.                         (*start).prev = NULL;
070.                     break;
071.                 case SEEK_END:
072.                     loc = prev;
073.                     prev = (*loc).prev;
074.                     if (prev != NULL)
075.                         (*prev).start = NULL;
076.                     break;
077.             }
078.             arg = (*loc).info;
079. 
080.             return RemoveNode(loc);
081.         }
082. //+----------------+
083.         bool Exclude(const uint index)
084.         {
085.             T arg;
086.             ENUM_FILE_POSITION pos = (index == 0 ? SEEK_SET : (index >= counter ? SEEK_END : SEEK_CUR));
087. 
088.             if (pos == SEEK_CUR)
089.             {
090.                 stList <T>  *loc = start,
091.                             *ptr = NULL;
092. 
093.                 for (uint c = 0; (loc != NULL) && (c < index); ptr = loc, loc = (*loc).start, c++);
094.                 if (loc == NULL) return false;
095. 
096.                 (*ptr).start = (*loc).start;
097.                 (*loc).start.prev = ptr;
098. 
099.                 return RemoveNode(loc);
100.             }
101. 
102.             return Restore(arg, pos);
103.         }
104. //+----------------+
105.         void Debug(void)
106.         {
107.             Print("===== DEBUG =====");
108.             for (stList <T> *loc = start; loc != NULL; loc = (*loc).start)
109.                 PrintFormat("0x%06X ->> 0x%06X <<- 0x%06X = [%d]", (*loc).start, loc, (*loc).prev, (*loc).info);
110.             Print("=================");
111.         }
112. //+----------------+
113. };
114. //+------------------------------------------------------------------+
115. void OnStart(void)
116. {
117.     stList <char> list;
118. 
119.     list.Store(10);
120.     list.Store(84);
121.     list.Store(-6);
122.     list.Store(47, SEEK_SET);
123. 
124.     list.Debug();
125. 
126.     list.Exclude(2);
127. 
128.     list.Debug();
129. 
130.     for (char info; list.Restore(info, SEEK_SET);)
131.         Print(info);
132. };
133. //+------------------------------------------------------------------+

Код 03

"Вы шутите? Что это за безумный код?" Возможно, я немного преувеличил, представив это таким образом. (СМЕХ). Этот код не такой уж и безумный. Честно говоря, его очень легко понять, хотя он и не самый красивый. Давайте посмотрим, что делает данный код. Сначала я добавил новую переменную в строке 11. Данная переменная показывает количество элементов в списке. Это похоже на использование функции ArraySize для определения количества элементов в динамическом массиве.

Поскольку это число может изменяться при добавлении или удалении элементов, за его корректировку отвечают строки 16 и 53. Обратите внимание, что в строке 44 из кода 03 я уже резервирую новую опцию, которая будет реализована в ближайшее время. Но давайте сосредоточимся на части, отвечающей за удаление элементов. Обратите внимание, что функция Exclude в строке 83 теперь получает значение, указывающее, какой элемент следует удалить из списка. Это определяется в зависимости от позиции, которую занимает элемент в списке.

А теперь обратите внимание, уважаемый читатель, потому что эта часть довольно интересна: чтение элементов списка — это разрушительная операция. Иными словами, при чтении списка в любом порядке, мы будем удалять данный элемент. Мы можем этим воспользоваться. Когда полученный индекс равен нулю, мы можем использовать саму функцию Restore из строки 56, чтобы удалить первый элемент списка. То же самое относится и к удалению последнего элемента из списка. Для этого мы используем строку 86, которая указывает, является ли удаляемый элемент первым, последним или каким-либо промежуточным.

Если удаляемый элемент находится в промежуточной позиции списка, проверка в строке 88 выполнится, и мы сможем сделать что-то похожее на то, что было сделано в коде 02. В отличие от сделанного в коде 02, проверка в коде 03, которую мы используем для поиска удаляемого элемента, отличается. В этом случае достаточно посмотреть на цикл в строке 93 и сравнить его с циклом в коде 02. Вы увидите, что здесь мы используем счётчик для поиска элемента, который будет удалён. Мы точно не знаем, где он находится. Мы знаем лишь то, какой индекс нам следует использовать. Остальная часть кода практически идентична коду 02.

Таким образом, при выполнении строки 126 код 03 выдаст тот же результат, который мы видели при выполнении кода 02. То есть, изображение 02. Код 03 очень интересен, но мы можем сделать кое-что немного по-другому. Прежде чем показать, как будет выглядеть код для вставки элементов в список, давайте проведём эксперимент с кодом 03. Эксперимент показан ниже:

001. //+------------------------------------------------------------------+
002. #property copyright "Daniel Jose"
003. //+------------------------------------------------------------------+
004. template <typename T> class stList
005. {
006.     private:
007. //+----------------+
008.         T info;
009.         stList <T>  *prev,
010.                     *start;
011.         uint        counter;
012. //+----------------+
013.         bool RemoveNode(stList <T> *arg)
014.         {
015.             delete arg;
016.             counter--;
017. 
018.             return true;
019.         }
020. //+----------------+
021.     public:
022. //+----------------+
023.         stList(void)
024.             :prev(NULL),
025.             start(NULL),
026.             counter(0)
027.         {}
028. //+----------------+
029.         void Store(T arg, const ENUM_FILE_POSITION pos = SEEK_END, const uint index = 0)
030.         {
031.             stList <T> *loc;
032. 
033.             loc = new stList <T>;
034. 
035.             (*loc).info = arg;
036.             (*loc).prev = NULL;
037.             switch(pos)
038.             {
039.                 case SEEK_SET:
040.                     (*loc).start = start;
041.                     (*start).prev = loc;
042.                     start = loc;
043.                     break;
044.                 case SEEK_CUR:
045.                     break;
046.                 case SEEK_END:
047.                     if (prev != NULL) (*prev).start = loc;
048.                     (*loc).prev = prev;
049.                     prev = loc;
050.                     start = (start == NULL ? loc : start);
051.                     break;
052.             }
053.             counter++;
054.         }
055. //+----------------+
056.         bool Restore(T &arg, const ENUM_FILE_POSITION pos = SEEK_END)
057.         {
058.             stList <T> *loc = NULL;
059. 
060.             if ((prev == NULL) || (start == NULL))
061.                 return false;
062. 
063.             switch (pos)
064.             {
065.                 case SEEK_SET:
066.                     loc = start;
067.                     start = (*loc).start;
068.                     if (start != NULL)
069.                         (*start).prev = NULL;
070.                     break;
071.                 case SEEK_END:
072.                     loc = prev;
073.                     prev = (*loc).prev;
074.                     if (prev != NULL)
075.                         (*prev).start = NULL;
076.                     break;
077.             }
078.             arg = (*loc).info;
079. 
080.             return RemoveNode(loc);
081.         }
082. //+----------------+
083.         bool Exclude(const int arg)
084.         {
085.             T tmp;
086.             uint index = MathAbs(arg);
087.             ENUM_FILE_POSITION pos = (index == 0 ? SEEK_SET : (index >= counter ? SEEK_END : SEEK_CUR));
088. 
089.             if (pos == SEEK_CUR)
090.             {
091.                 stList <T>  *loc = (arg < 0 ? prev : start),
092.                             *ptr = NULL;
093. 
094.                 for (uint c = 0; (loc != NULL) && (c < index); ptr = loc, loc = (arg < 0 ? (*loc).prev : (*loc).start), c++);
095.                 if (loc == NULL) return false;
096. 
097.                 if (arg < 0)
098.                 {
099.                     (*ptr).prev = (*loc).prev;
100.                     (*loc).prev.start = ptr;
101.                 }else{
102.                     (*ptr).start = (*loc).start;
103.                     (*loc).start.prev = ptr;
104.                 }
105. 
106.                 return RemoveNode(loc);
107.             }
108. 
109.             return Restore(tmp, pos);
110.         }
111. //+----------------+
112.         void Debug(void)
113.         {
114.             Print("===== DEBUG =====");
115.             for (stList <T> *loc = start; loc != NULL; loc = (*loc).start)
116.                 PrintFormat("0x%06X ->> 0x%06X <<- 0x%06X = [%d]", (*loc).start, loc, (*loc).prev, (*loc).info);
117.             Print("=================");
118.         }
119. //+----------------+
120. };
121. //+------------------------------------------------------------------+
122. void OnStart(void)
123. {
124.     stList <char> list;
125. 
126.     list.Store(10);
127.     list.Store(84);
128.     list.Store(-6);
129.     list.Store(47, SEEK_SET);
130. 
131.     list.Debug();
132. 
133.     list.Exclude(-2);
134. 
135.     list.Debug();
136. 
137.     for (char info; list.Restore(info, SEEK_SET);)
138.         Print(info);
139. };
140. //+------------------------------------------------------------------+

Код 04

Эксперимент заключался в изменении типа аргумента, который может принимать функция Exclude. Обратите внимание, что в отличие от кода 03, в коде 04 мы можем передавать в функцию Exclude как положительные, так и отрицательные значения. Но что это означает на практике? Это означает, что мы можем удалять элементы как из начала, так и из конца списка. "Да уж, вы нам совсем не даёте покоя. Я едва начал понимать код, а тут появляетесь вы и ещё больше его усложняете. Вы никогда не устаете?" Нисколько, уважаемый читатель. Мне кажется очень забавным то, что мы можем сделать. И чем запутаннее становится этот механизм, тем больше удовольствия я получаю от написания кода.

Несмотря на эту кажущуюся путаницу, вы легко поймёте, что происходит. Обратите внимание, что единственное, что пришлось изменить в коде 04, — это то, как будет работать цикл поиска. Также потребовалась небольшая корректировка, потому что мы можем обходить список как с начала, так и с конца.

Как можно контролировать это? Уважаемый читатель, данная часть самая простая. Если значение аргумента функции Exclude положительное, мы будем работать так же, как в коде 03. Если значение отрицательное, обход будет восприниматься иначе. Для начала нам всегда нужно преобразовывать значение в положительное, что поможет избежать проблем. Для этого мы используем строку 86, чтобы получить правильное значение, независимо от того, является ли оно положительным или отрицательным. Если выполняется цикл в строке 94, мы меняем направление обхода. То есть, если значение отрицательное, оно всегда будет указывать на предыдущий элемент. Если значение положительное, мы будем переходить к следующему элементу. В любом случае здесь будет указание на какой-либо элемент. А теперь настала очередь правильной корректировки указателей.

Поскольку мы можем обходить список от конца к началу, указатели могут стать перевёрнутыми. По этой причине в строке 97 мы проверяем, в каком направлении проходится список. Если мы проходим его в обратном направлении, то есть от конца к началу, нам нужно использовать строки 99 и 100, чтобы правильно скорректировать указатели. В итоге результат всегда будет правильным, если проявить необходимую внимательность.

Чтобы продемонстрировать это, обратите внимание, что в строке 133 мы передаём отрицательное значение в качестве аргумента функции Exclude. Следовательно, будет удалён элемент с индексом два, считая с конца списка. Если вы поняли всё, что мы делали с самого начала, вы будете знать, что этот элемент имеет значение 10, поэтому при выполнении кода 04 результат будет таким, как показано на следующем изображении.

Изображение 03

Ладно, хватит шутить. Настало время реализовать часть, отвечающую за вставку значений в произвольные позиции списка. Что-то похожее на то, что мы только что сделали с методом удаления. Как вы уже можете себе представить, мы не будем реализовывать это как попало, а будем экспериментировать с кодом по мере его создания. Так вы лучше поймёте, как работает механизм и почему он реализован именно таким образом.

Итак, давайте сосредоточимся на коде 04, который отвечает за сохранение значений в списке. Если вы посмотрите на инструкцию switch в строке 37, вы увидите, что для вставки нового элемента в конец или в начало списка выполняется ряд шагов. Эти шаги служат именно для настройки адреса памяти предыдущего и следующего элементов относительно нового элемента, который мы добавляем. Очень важно, чтобы вы обратили внимание на то, как это делается. Фактически, разница между размещением нового элемента в начале или в конце списка заключается в том, какой указатель получит ссылку на новый элемент. Но почему это происходит? Итак, если вы посмотрите на ветку case в строке 39, вы увидите, что мы добавляем новый элемент в начало очереди. Причина указана в строке 42.

Если вы посмотрите на строку 46, то увидите, что мы добавляем элемент в конец очереди. Это решается с помощью строки 49. Теперь возникает вопрос. Когда мы указываем индекс, логика меняется, так как в этом случае мы переходим к указанию того, куда будет вставлен элемент. Но на данном этапе нам необходимо спокойно обдумать данный механизм. И причина, в некотором смысле, связана именно с тем, что мы наблюдали при удалении элементов из списка.

Чтобы не усложнять механизм ввода, давайте сделаем следующее: вставим новый элемент, взяв за точку отсчёта начало списка. Следующий код показывает, что нам нужно сделать:

001. //+------------------------------------------------------------------+
002. #property copyright "Daniel Jose"
003. //+------------------------------------------------------------------+
004. template <typename T> class stList
005. {
006.     private:
007. //+----------------+
008.         T info;
009.         stList <T>  *prev,
010.                     *start;
011.         uint        counter;
012. //+----------------+
013.         bool RemoveNode(stList <T> *arg)
014.         {
015.             delete arg;
016.             counter--;
017. 
018.             return true;
019.         }
020. //+----------------+
021.     public:
022. //+----------------+
023.         stList(void)
024.             :prev(NULL),
025.             start(NULL),
026.             counter(0)
027.         {}
028. //+----------------+
029.         void Store(T arg, const ENUM_FILE_POSITION pos = SEEK_END, const uint index = 0)
030.         {
031.             stList <T> *loc;
032. 
033.             loc = new stList <T>;
034. 
035.             (*loc).info = arg;
036.             (*loc).prev = NULL;
037.             switch(pos)
038.             {
039.                 case SEEK_SET:
040.                     (*loc).start = start;
041.                     (*start).prev = loc;
042.                     start = loc;
043.                     break;
044.                 case SEEK_CUR:
045.                     {
046.                         stList <T>  *ptr1 = start,
047.                                     *ptr2 = NULL;
048. 
049.                         for (uint c = 0; (ptr1 != NULL) && (c < index); ptr2 = ptr1, ptr1 = (*ptr1).start, c++);
050. 
051.                         (*loc).start = (ptr2 != NULL ? (*ptr2).start : ptr1);
052.                         (*loc).prev = (ptr1 != NULL ? (*ptr1).prev : ptr2);
053.                         if (ptr2 != NULL) (*ptr2).start = loc; else start = loc;
054.                         if (ptr1 != NULL) (*ptr1).prev = loc; else prev = loc;
055.                     }
056.                     break;
057.                 case SEEK_END:
058.                     if (prev != NULL) (*prev).start = loc;
059.                     (*loc).prev = prev;
060.                     prev = loc;
061.                     start = (start == NULL ? loc : start);
062.                     break;
063.             }
064.             counter++;
065.         }
066. //+----------------+
067.         bool Restore(T &arg, const ENUM_FILE_POSITION pos = SEEK_END)
068.         {
069.             stList <T> *loc = NULL;
070. 
071.             if ((prev == NULL) || (start == NULL))
072.                 return false;
073. 
074.             switch (pos)
075.             {
076.                 case SEEK_SET:
077.                     loc = start;
078.                     start = (*loc).start;
079.                     if (start != NULL)
080.                         (*start).prev = NULL;
081.                     break;
082.                 case SEEK_END:
083.                     loc = prev;
084.                     prev = (*loc).prev;
085.                     if (prev != NULL)
086.                         (*prev).start = NULL;
087.                     break;
088.             }
089.             arg = (*loc).info;
090. 
091.             return RemoveNode(loc);
092.         }
093. //+----------------+
094.         bool Exclude(const uint index)
095.         {
096.             T tmp;
097.             ENUM_FILE_POSITION pos = (index == 0 ? SEEK_SET : (index >= counter ? SEEK_END : SEEK_CUR));
098. 
099.             if (pos == SEEK_CUR)
100.             {
101.                 stList <T>  *loc = start,
102.                             *ptr = NULL;
103. 
104.                 for (uint c = 0; (loc != NULL) && (c < index); ptr = loc, loc = (*loc).start, c++);
105.                 if (loc == NULL) return false;
106. 
107.                 (*ptr).start = (*loc).start;
108.                 (*loc).start.prev = ptr;
109. 
110.                 return RemoveNode(loc);
111.             }
112. 
113.             return Restore(tmp, pos);
114.         }
115. //+----------------+
116.         void Debug(void)
117.         {
118.             Print("===== DEBUG =====");
119.             for (stList <T> *loc = start; loc != NULL; loc = (*loc).start)
120.                 PrintFormat("0x%06X ->> 0x%06X <<- 0x%06X = [%d]", (*loc).start, loc, (*loc).prev, (*loc).info);
121.             Print("=================");
122.         }
123. //+----------------+
124. };
125. //+------------------------------------------------------------------+
126. void OnStart(void)
127. {
128.     stList <char> list;
129. 
130.     list.Store(10);
131.     list.Store(84);
132.     list.Store(-6);
133.     list.Store(47, SEEK_SET);
134. 
135.     list.Debug();
136. 
137.     list.Store(35, SEEK_CUR, 2);
138. 
139.     list.Debug();
140. 
141.     for (char info; list.Restore(info, SEEK_SET);)
142.         Print(info);
143. };
144. //+------------------------------------------------------------------+

Код 05

Прежде чем объяснять, как работает код 05, давайте посмотрим на результат его выполнения. Это показано на следующем изображении:

Изображение 04

Итак, на этом изображении 04 я показываю результат вставки значения в определённую позицию списка. Глядя на код 05, вы можете задаться вопросом: "Как вы это сделали?" Поскольку цель здесь — максимально наглядное объяснение, я упростил код 04. Это можно увидеть в коде 05, в части, касающейся удаления значений. Однако в этом коде нас на самом деле интересует вставка значений. По этой причине я хочу, чтобы вы попытались провести параллель между кодом удаления, который находится в строке 94, и кодом вставки, который находится между строками 44 и 56.

Ещё раз подчеркну: цель — сделать объяснение максимально наглядным. Если вы сравните код удаления с кодом включения, вы увидите, что большая его часть схожа. Многие теряются в этом месте: код вставки требует три указателя, тогда как код удаления — только два. В чём же причина этой разницы? Причина проста.

При добавлении значения в список мы не перемещаем никакие значения, как это происходило бы при работе с массивами. В случае связного списка достаточно просто настроить указатели так, чтобы они указывали на предыдущий или следующий элемент списка. Таким образом, код, который фактически вставляет новый элемент в список, соответствует строкам 53 и 54. То есть мы используем две инструкции if для правильной настройки списка. Чтобы структура списка осталась нетронутой, мы используем строки 51 и 52, чтобы вставляемый элемент указывал на уже существующие элементы.

А теперь внимание: Эти строки, которые я только что упомянул, позволяют создать двусвязный список без необходимости использования кода для случаев SEEK_SET и SEEK_END. То есть данный код внутри случая SEEK_CUR может вставлять элементы в начало, в конец или в произвольную позицию списка. Просто укажите индекс, который будет использоваться.

"Хм... Позвольте мне уточнить, правильно ли я всё понял. Вы хотите сказать, что код 05 можно изменить, чтобы уменьшить его объем? Тем не менее, это сработает и даст тот же результат, что и на изображении 04, верно?" Да, уважаемый читатель. Код 05 был создан таким образом, чтобы вы могли понять, как можно реализовать данный механизм. Этот же код 05 можно изменить для получения результата, показанного ниже:

001. //+------------------------------------------------------------------+
002. #property copyright "Daniel Jose"
003. //+------------------------------------------------------------------+
004. template <typename T> class stList
005. {
006.     private:
007. //+----------------+
008.         T info;
009.         stList <T>  *prev,
010.                     *start;
011.         uint        counter;
012. //+----------------+
013.         bool RemoveNode(stList <T> *arg)
014.         {
015.             delete arg;
016.             counter--;
017. 
018.             return true;
019.         }
020. //+----------------+
021.     public:
022. //+----------------+
023.         stList(void)
024.             :prev(NULL),
025.             start(NULL),
026.             counter(0)
027.         {}
028. //+----------------+
029.         void Store(T arg, const uint index = 0xFFFFFFFF)
030.         {
031.             stList <T> *loc,
032.                         *ptr1 = start,
033.                         *ptr2 = NULL;
034. 
035.             for (uint c = 0; (ptr1 != NULL) && (c < index); ptr2 = ptr1, ptr1 = (*ptr1).start, c++);
036. 
037.             loc = new stList <T>;
038.             (*loc).info = arg;
039.             (*loc).start = (ptr2 != NULL ? (*ptr2).start : ptr1);
040.             (*loc).prev = (ptr1 != NULL ? (*ptr1).prev : ptr2);
041.             if (ptr2 != NULL) (*ptr2).start = loc; else start = loc;
042.             if (ptr1 != NULL) (*ptr1).prev = loc; else prev = loc;
043. 
044.             counter++;
045.         }
046. //+----------------+
047.         bool Restore(T &arg, const ENUM_FILE_POSITION pos = SEEK_END)
048.         {
049.             stList <T> *loc = NULL;
050. 
051.             if ((prev == NULL) || (start == NULL))
052.                 return false;
053. 
054.             switch (pos)
055.             {
056.                 case SEEK_SET:
057.                     loc = start;
058.                     start = (*loc).start;
059.                     if (start != NULL)
060.                         (*start).prev = NULL;
061.                     break;
062.                 case SEEK_END:
063.                     loc = prev;
064.                     prev = (*loc).prev;
065.                     if (prev != NULL)
066.                         (*prev).start = NULL;
067.                     break;
068.             }
069.             arg = (*loc).info;
070. 
071.             return RemoveNode(loc);
072.         }
073. //+----------------+
074.         bool Exclude(const uint index)
075.         {
076.             T tmp;
077.             ENUM_FILE_POSITION pos = (index == 0 ? SEEK_SET : (index >= counter ? SEEK_END : SEEK_CUR));
078. 
079.             if (pos == SEEK_CUR)
080.             {
081.                 stList <T>  *loc = start,
082.                             *ptr = NULL;
083. 
084.                 for (uint c = 0; (loc != NULL) && (c < index); ptr = loc, loc = (*loc).start, c++);
085.                 if (loc == NULL) return false;
086. 
087.                 (*ptr).start = (*loc).start;
088.                 (*loc).start.prev = ptr;
089. 
090.                 return RemoveNode(loc);
091.             }
092. 
093.             return Restore(tmp, pos);
094.         }
095. //+----------------+
096.         void Debug(void)
097.         {
098.             Print("===== DEBUG =====");
099.             for (stList <T> *loc = start; loc != NULL; loc = (*loc).start)
100.                 PrintFormat("0x%06X ->> 0x%06X <<- 0x%06X = [%d]", (*loc).start, loc, (*loc).prev, (*loc).info);
101.             Print("=================");
102.         }
103. //+----------------+
104. };
105. //+------------------------------------------------------------------+
106. void OnStart(void)
107. {
108.     stList <char> list;
109. 
110.     list.Store(10);
111.     list.Store(84);
112.     list.Store(-6);
113.     list.Store(47, 0);
114. 
115.     list.Debug();
116. 
117.     list.Store(35, 2);
118. 
119.     list.Debug();
120. 
121.     for (char info; list.Restore(info, SEEK_SET);)
122.         Print(info);
123. };
124. //+------------------------------------------------------------------+

Код 06

А теперь обратите пристальное внимание на то, что я собираюсь объяснить. Иначе вы потеряете нить и не поймёте, что мы будем делать дальше. Если вы посмотрите на процедуру в строке 29 этого кода 06, вы увидите, что она изменилась, но совсем незначительно. Теперь данная процедура будет получать только элемент, который необходимо сохранить вместе с индексом. Чтобы код 06 продолжал работать так же, как код 05 в части содержимого процедуры OnStart, индекс по умолчанию соответствует концу списка. То есть, если не указано никакое значение в качестве индекса позиции элемента, мы ВСЕГДА будем размещать новый элемент на вершине или в конце списка, как вам удобнее.

Очень важно, чтобы вы это поняли, уважаемый читатель. В противном случае вы можете попытаться реализовать механизм одним способом, в то время как код будет выполнять его по-другому. Чтобы это стало более понятным, сравните процедуру OnStart этого кода 06 с такой же процедурой из кода 05. Вы увидите, что они очень похожи.

В заключение внесем небольшую корректировку в этот же код 06. Это позволит считывать элемент из любой позиции в списке. Помните, что при выполнении этого чтения мы удалим из списка считанное значение. Но поскольку цель здесь образовательная, я не вижу проблемы в том, чтобы так сделать. Итак, после применения изменения мы получим код, показанный ниже.

001. //+------------------------------------------------------------------+
002. #property copyright "Daniel Jose"
003. //+------------------------------------------------------------------+
004. template <typename T> class stList
005. {
006.     private:
007. //+----------------+
008.         T info;
009.         stList <T>  *prev,
010.                     *start;
011.         uint        counter;
012. //+----------------+
013.     public:
014. //+----------------+
015.         stList(void)
016.             :prev(NULL),
017.             start(NULL),
018.             counter(0)
019.         {}
020. //+----------------+
021.         void Store(T arg, const uint index = 0xFFFFFFFF)
022.         {
023.             stList <T> *loc,
024.                         *ptr1 = start,
025.                         *ptr2 = NULL;
026. 
027.             for (uint c = 0; (ptr1 != NULL) && (c < index); ptr2 = ptr1, ptr1 = (*ptr1).start, c++);
028. 
029.             loc = new stList <T>;
030.             (*loc).info = arg;
031.             (*loc).start = (ptr2 != NULL ? (*ptr2).start : ptr1);
032.             (*loc).prev = (ptr1 != NULL ? (*ptr1).prev : ptr2);
033.             if (ptr2 != NULL) (*ptr2).start = loc; else start = loc;
034.             if (ptr1 != NULL) (*ptr1).prev = loc; else prev = loc;
035. 
036.             counter++;
037.         }
038. //+----------------+
039.         bool Restore(T &arg, const uint index = 0xFFFFFFFF)
040.         {
041.             if ((prev == NULL) || (start == NULL))
042.                 return false;
043. 
044.             stList <T>  *loc = (index < counter ? start : prev),
045.                         *ptr = NULL;
046. 
047.             for (uint c = 0; (loc != NULL) && (c < index) && (index < counter); ptr = loc, loc = (*loc).start, c++);
048.             if (loc == NULL) return false;
049. 
050.             if (index == 0)
051.             {
052.                 start = (*loc).start;
053.                 if (start != NULL) (*start).prev = NULL;
054.             } else if (index >= (counter - 1))
055.             {
056.                 prev = (*loc).prev;
057.                 if (prev != NULL) (*prev).start = NULL;
058.             }
059.             else
060.             {
061.                 (*ptr).start = (*loc).start;
062.                 (*loc).start.prev = ptr;
063.             }
064.             arg = (*loc).info;
065.             delete loc;
066.             counter--;
067. 
068.             return true;
069.         }
070. //+----------------+
071.         bool Exclude(const uint index)
072.         {
073.             T tmp;
074. 
075.             return Restore(tmp, index);
076.         }
077. //+----------------+
078.         void Debug(void)
079.         {
080.             Print("===== DEBUG =====");
081.             for (stList <T> *loc = start; loc != NULL; loc = (*loc).start)
082.                 PrintFormat("0x%06X ->> 0x%06X <<- 0x%06X = [%d]", (*loc).start, loc, (*loc).prev, (*loc).info);
083.             Print("=================");
084.         }
085. //+----------------+
086. };
087. //+------------------------------------------------------------------+
088. void OnStart(void)
089. {
090.     stList <char> list;
091. 
092.     list.Store(10);
093.     list.Store(84);
094.     list.Store(-6);
095.     list.Store(47, 0);
096. 
097.     list.Debug();
098. 
099.     list.Exclude(3);
100.     list.Store(35, 2);
101. 
102.     list.Debug();
103. 
104.     for (char info; list.Restore(info, 0);)
105.         Print(info);
106. };
107. //+------------------------------------------------------------------+

Код 07

Код 07 — почти финальная версия реализации двусвязного списка. Но нас по-настоящему интересует результат, который он может дать. При выполнении будет получен результат, показанный ниже:

Изображение 05

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

Заключительные идеи

В сегодняшней статье мы рассмотрели, как реализовать полнофункциональный связный список. Остается объяснить один момент: каждое чтение удаляет считанный элемент из списка. Есть способы этого избежать. Поскольку вопрос о том, как правильно работать с классами, ещё не был рассмотрен, я пока не буду углубляться в эту тему. Поэтому мы оставим вопрос на другой раз. В следующей статье мы рассмотрим, к чему приводит эволюция связного списка. Результатом данной эволюции станет новый тип структур данных.

МQ5	Описание
Code 01	Простой список
Code 02	Простой список
Code 03	Простой список