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

Введение

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

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

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

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

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

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. //+----------------+
11.     public:
12. //+----------------+
13.         stList(void)
14.             :prev(NULL)
15.         {}
16. //+----------------+
17.         void Push(T arg)
18.         {
19.             stList <T> *loc;
20. 
21.             loc = new stList <T>;
22.             (*loc).info = arg;
23.             (*loc).prev = prev;
24.             prev = loc;
25.         }
26. //+----------------+
27.         bool Pop(T &arg)
28.         {
29.             stList <T> *loc;
30. 
31.             if (prev == NULL)
32.                 return false;
33. 
34.             loc = prev;
35.             arg = (*loc).info;
36.             prev = (*loc).prev;
37. 
38.             delete loc;
39. 
40.             return true;
41.         }
42. //+----------------+
43. };
44. //+------------------------------------------------------------------+
45. void OnStart(void)
46. {
47.     stList <char> list;
48. 
49.     list.Push(10);
50.     list.Push(84);
51.     list.Push(-6);
52. 
53.     for (char info; list.Pop(info);)
54.         Print(info);
55. };
56. //+------------------------------------------------------------------+

Код 01

Этот код 01 предназначен для создания эквивалента стека, который представляет собой тип очереди, где значения, добавленные недавно, считываются самыми первыми. Однако, в отличие от реализации очереди, этот код 01 больше не использует никакой внутренний массив. Именно данная небольшая деталь обуславливает другую классификацию этой реализации. Таким образом, код 01 будет классифицирован как СВЯЗНЫЙ СПИСОК. Однако его пока нельзя в полной мере считать связным.

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

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

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

Однако, когда мы хотим добавить элементы в середину существующего массива или в начало того же массива, происходит нечто иное. В этом случае функция ArrayInsert выделит новый блок памяти, а затем скопирует некоторые элементы в этот новый блок. Затем в этот новый блок будут добавлены вставляемые элементы. Лишь после этого функция скопирует в выделенный блок оставшуюся часть исходного массива. Следовательно, при использовании очень большого массива время выполнения может быть довольно длительным. Однако, учитывая особенности современных материнских плат и используемую ими шину данных, блоки, которые необходимо перемещать, должны быть действительно большими, чтобы вы заметили разницу. Или, как минимум, нам нужно выполнить несколько вставок, чтобы время обработки можно было ощутить.

Однако в начале эры компьютеров вычисления тогда были не столь быстрыми. Шина данных работала медленно, и эти перемещения, даже с небольшим количеством элементов, требовали много времени. Таким образом, инженеры и ученые разработали решение данной проблемы. И это решение — именно списки. А теперь вернёмся к вопросу о коде 01. Когда список будет полностью сформирован, в памяти мы получим нечто похожее на показанное ниже:

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

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

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

Теперь предположим, что мы хотим добавить новый элемент в массив изображения 02, как показано на изображении 03:

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

Как это сделать без использования функции ArrayInsert? Хорошо, если вы поняли объяснение, данное чуть выше в этой статье, сначала вам нужно будет выделить новый блок памяти. В результате получится изображение, представленное ниже:

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

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

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

Теперь мы можем вставить новый элемент в массив. Таким образом, мы получим это:

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

Как только новый элемент будет вставлен в конечный массив, мы можем скопировать остальные элементы, которые существовали в исходном массиве. Итак, финальный результат показан на изображении 07:

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

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

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

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

Обратите внимание, что изображение 08 очень похоже на изображение 01. Но здесь необходимо добавить новый элемент. И этот элемент ещё не входит в связный список. Тогда всё, что нам нужно сделать, чтобы добавить этот новый элемент, — это указать, где он должен быть добавлен. А сама реализация преобразует изображение 08 в изображение 09, которое показано ниже:

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

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

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

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

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)
20.         {
21.             stList <T> *loc;
22. 
23.             loc = new stList <T>;
24.             (*loc).info = arg;
25.             (*loc).prev = prev;
26.             prev = loc;
27.         }
28. //+----------------+
29.         bool Restore(T &arg)
30.         {
31.             stList <T> *loc;
32. 
33.             if (prev == NULL)
34.                 return false;
35. 
36.             loc = prev;
37.             arg = (*loc).info;
38.             prev = (*loc).prev;
39. 
40.             delete loc;
41. 
42.             return true;
43.         }
44. //+----------------+
45. };
46. //+------------------------------------------------------------------+
47. void OnStart(void)
48. {
49.     stList <char> list;
50. 
51.     list.Store(10);
52.     list.Store(84);
53.     list.Store(-6);
54. 
55.     for (char info; list.Restore(info);)
56.         Print(info);
57. };
58. //+------------------------------------------------------------------+

Код 02

А теперь обратите внимание, уважаемый читатель. В коде 02 мы начинаем реализовывать то, что фактически является простым связным списком. Здесь можно использовать любое название для принятых функций и процедур. Это не имеет значения. Однако, и это очень важно, необходимо тщательно продумать реализацию кода, чтобы список создавался и поддерживался корректно. В том виде, в каком находится этот код 02, у нас по-прежнему есть то, что можно назвать стеком, реализованным в виде списка. Понимание этого важно для понимания того, что мы увидим дальше.

Теперь мы можем постепенно реализовать эти функции и процедуры. Но прежде чем это сделать, как насчёт того, чтобы посмотреть результат выполнения этого кода 02? Хотя те, кто читал предыдущую статью, это уже знают. В любом случае, результат можно увидеть ниже:

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

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

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.             switch(pos)
25.             {
26.                 case SEEK_SET:
27.                     (*loc).info = arg;
28.                     (*loc).prev = NULL;
29.                     (*start).prev = loc;
30.                     start = loc;
31.                     break;
32.                 case SEEK_END:
33.                     (*loc).info = arg;
34.                     (*loc).prev = prev;
35.                     prev = loc;
36.                     start = (start == NULL ? loc : start);
37.                     break;
38.             }
39.         }
40. //+----------------+
41.         bool Restore(T &arg)
42.         {
43.             stList <T> *loc;
44. 
45.             if (prev == NULL)
46.                 return false;
47. 
48.             loc = prev;
49.             arg = (*loc).info;
50.             prev = (*loc).prev;
51. 
52.             delete loc;
53. 
54.             return true;
55.         }
56. //+----------------+
57. };
58. //+------------------------------------------------------------------+
59. void OnStart(void)
60. {
61.     stList <char> list;
62. 
63.     list.Store(10);
64.     list.Store(84);
65.     list.Store(-6);
66.     list.Store(47, SEEK_SET);
67. 
68.     for (char info; list.Restore(info);)
69.         Print(info);
70. };
71. //+------------------------------------------------------------------+

Код 03

А теперь, уважаемый читатель, внимательно послушайте, что я сейчас объясню. Хотя для меня и для программистов с хорошим опытом то, что делается здесь в коде 03, очень просто для понимания, для многих из вас это крайне сложно. И это только начало реализации самого списка. Чтобы не создавать слишком много всего, я использую здесь в коде перечисление позиционирования файла. Это можно увидеть в строке 19.

Обратите внимание, что существует разница между кодом 02 и 03 именно в этой же процедуре. Этот код 03 продолжает функционировать так, как будто это стек, но такой стек, который можно построить довольно произвольным способом. Теперь перейдём к сути. SEEK_END всегда будет размещать элементы начиная с конца того, что уже находится в списке. А функция SEEK_SET всегда будет размещать элементы, начиная с начала уже имеющихся в списке элементов. Этот же принцип применяется при работе с бинарными файлами.

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

Итак, когда вызов процедуры в строке 19 имеет SEEK_SET в качестве второго аргумента, как это происходит в строке 66, выполняется код между строками 26 и 31. Давайте теперь разберемся, строка за строкой, что здесь происходит. В строке 27 хранится значение элемента, как и в строке 33. В свою очередь, строка 28 гарантирует, что предыдущее значение равно NULL. Это важно, чтобы проверка в строке 45 прошла успешно в случае, если в списке нет ни одного элемента. Итак, строка 29 заставляет текущий указатель на предыдущее значение указывать на то, что будет новым первым элементом в начале списка. И в завершение строка 30 задаёт указатель на первый элемент так, чтобы он был установлен корректно.

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

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

Хорошо, но вы можете подумать: не могли бы мы разместить содержимое этой строки 66 перед тем, что было бы строкой 63? Это позволило бы избежать потенциальной путаницы в коде. На самом деле, проблема здесь не совсем в этом, уважаемый читатель. Дело в том, что нам нужно убедиться, что код может добавлять элементы в то, что будет началом нашего списка. Вот почему строка 66 выглядит так, как показано в коде 03.

Это было довольно интересно, но мы можем и сделаем всё ещё интереснее. Давайте теперь изменим код 03 на код 04, который показан ниже:

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. };
69. //+------------------------------------------------------------------+
70. void OnStart(void)
71. {
72.     stList <char> list;
73. 
74.     list.Store(10);
75.     list.Store(84);
76.     list.Store(-6);
77.     list.Store(47, SEEK_SET);
78. 
79.     for (char info; list.Restore(info, SEEK_SET);)
80.         Print(info);
81. };
82. //+------------------------------------------------------------------+

Код 04

В этом коде 04 мы уже начинаем реализовывать нечто, что на первый взгляд не выглядит тем, чем оно является на самом деле. Итак, давайте немного расслабимся и спокойно посмотрим на этот код 04. Обратите внимание, что теперь у нас есть функция Restore, присутствующая в строке 43, которая также может получать указание о том, как должно выполняться чтение.

Таким образом, именно в этот момент мы сталкиваемся с проблемой, уже описанной в статье От начального до среднего уровня: Очереди, списки и деревья (I) где мы говорили о очередях типа FIFO, а также о круговых очередях. Но здесь, ради простоты самого кода, мы не будем углубляться в вопрос о круговых очередях. Давайте сосредоточимся на самом простом и одновременно интересном вопросе для этой статьи.

Прежде чем перейти к вопросу о функции Restore, давайте посмотрим, что изменилось по сравнению с процедурой Store. Хотя может показаться, что ничего не изменилось, модификации, внесённые в эту процедуру, создают нечто иное, чем то, что показано на изображении 01. Итак, обратите внимание, уважаемый читатель, потому что на изображении 01 мы видели то, что представляло бы собой простой односвязный список. Однако этот код 04, более конкретно в процедуре Store, создаёт то, что известно как ДВУСВЯЗНЫЙ СПИСОК. "Но подождите секунду. Разве мы не создавали данный тип двусвязного списка в коде 03?" Нет, уважаемый читатель. В коде 03 мы всё ещё находились в простом списке. Однако эти небольшие изменения, внесённые в код 04, превратили то, что было простым списком, в двусвязный список. Чтобы понять это, посмотрите на следующее изображение, которое представляет двусвязный список.

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

Обратите внимание, что в этом случае на изображении 12 у нас есть два направления стрелок, а это отличается от того, что видно на изображении 01, где было только одно направление стрелки. Именно это позволяет нам различать двусвязный список и простой список.

"Но подождите, я до сих пор не могу понять, почему код 03 представляет собой простой список, а код 04 — двусвязный. Не могли бы вы объяснить это подробнее?" Давайте тогда сделаем всё более понятным. Обратите внимание, что в строке 30 из кода 04 мы создали ссылку, чтобы обозначить начало списка. Это также делается в строке 35, но способ, которым мы это осуществляем, меняет поведение списка. Не во время записи, а во время процесса чтения, который мы рассмотрим чуть позже. Обратите внимание, что каждый элемент или узел, как обычно называют элемент списка, имеет два направления, по которым можно двигаться. Первое из этих направлений ведет нас к началу, или первому элементу списка, а второе же направление, напротив, заставляет нас двигаться к концу списка. Поскольку мы не замыкаем список, чтобы сделать его циклическим, возможности ограничиваются этим диапазоном навигации.

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

Обратите внимание на то, что в проверке в строке 47 мы проверили два условия, которые делают список пустым. Если он не пуст, переходим к части, отвечающей за чтение. Поскольку реализация SEEKEND, то есть чтение от самого нового элемента к самому старому, уже была достаточно объяснена, давайте перейдём к новому материалу. Другими словами, перейдём к SEEK_SET. При использовании этого метода мы будем читать от самого старого элемента, то есть от первых элементов списка, до самых новых, которыми будут последние элементы, присутствующие в списке. Обратите внимание, что для этого мы читаем текущий элемент в строке 53 и сразу после этого перенастраиваем указатель текущего элемента на следующий элемент списка. Это делается в строке 54. И это всё, что нам нужно сделать. Таким образом, при выполнении кода мы увидим то, что показано на следующем изображении:

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

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

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

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

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. //+------------------------------------------------------------------+

Код 05

Если вы будете спокойно и внимательно использовать данный код 05, который будет в приложении, вы поймёте, как создаётся список на практике. Это связано с тем, что в строке 68 я добавил процедуру, цель которой — отобразить список в памяти. Поскольку здесь, в MetaTrader 5, мы не можем делать некоторые вещи без погружения в ещё более продвинутые детали, эта процедура из строки 68 выведет в терминал структуру списка в относительно простой для понимания форме. При выполнении строки 87 мы вызовем данную процедуру из строки 68. Результат можно увидеть на следующем изображении:

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

Здесь у нас отмечены четыре области. И эти регионы в некоторой степени связаны с тем, что можно было бы отнести к изображению 12. Обратите внимание, что на изображении зелёным цветом выделены значения, присутствующие в этом узле списка. Жёлтым цветом обозначен адрес узла. "А что насчет областей, выделенных красным и фиолетовым цветом?" Хорошо, эти области указывают направление к следующему и предыдущему блоку. Обратите внимание, что стрелки на изображении 14 указывают направление чтения, которому мы будем следовать. Если стрелка указывает влево, мы будем читать от самого старого элемента к самому новому. Это будет эквивалентно чтению по алгоритму FIFO. С другой стороны, при стрелках, направленных вправо, мы будем читать узлы так, как было бы эквивалентно стеку, то есть, от самого нового элемента к самому старому в списке.

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

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

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

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

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

Попробуйте изменить процедуру в строке 68 из кода 05, чтобы определять точки удаления и вставки данных в список. Как только вам удастся это сделать, попробуйте соответствующим образом изменить процедуру в строке 19, чтобы она принимала индекс, указывающий, в какой позиции будет изменён список. Это позволит вам создать или удалить определенный узел из списка, в результате чего получится нечто очень похожее на показанное на изображении 09. Деталь: для двусвязного списка будет проще реализовать код, поскольку код 05 создаёт двусвязный список. Но ничто не мешает вам создать простой связный список.

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

Файл MQ5	Описание
Code 01	Простой список
Code 02	Простой список