Rivalry2

HTML Diff

0 added 0 removed

Original 2026-01-01

Modified 2026-03-10

1 <ul><li><a>Основополагающие сведения о структурах данных</a><ul><li><a>Базовые термины</a></li>

2 <li><a>Характеристики</a></li>

3 <li><a>Какие проблемы можно решить с помощью структуры данных</a></li>

4 <li><a>Случаи выполнения</a></li>

5 </ul></li>

6 <li><a>Основные виды структур</a><ul><li><a>Массивы</a></li>

7 <li><a>Списки</a><ul><li><a>Связные (связанные) списки</a></li>

8 <li><a>Стеки</a></li>

9 <li><a>Очереди</a></li>

10 <li><a>Дек или двухсторонняя очередь</a></li>

11 </ul></li>

12 <li><a>Графы</a></li>

13 <li><a>Множества</a></li>

14 <li><a>Map</a></li>

15 <li><a>Хэш-таблицы</a></li>

16 <li><a>Деревья</a><ul><li><a>Дерево двоичного (бинарного) поиска</a></li>

17 <li><a>Префиксные деревья (Trie), боры, лучи</a></li>

18 <li><a>Двоичная куча</a></li>

19 </ul></li>

20 </ul></li>

21 </ul><p>Предлагаем укрепить (или получить) знания о базовых структурах данных. Эти понятия являются основой всего, что связано с программами. Вспомните азы, а если не знаете - получите их. Они пригодятся в работе, а если есть цель найти ее, то и при прохождении интервью. Укажите, что вы знаете составляющие структуры данных, их применение, и это поможет в поиске работы. Потратив немного времени, вы приятно удивите интервьюера, начальника или коллег по работе.</p>

22 <h2>Основополагающие сведения о структурах данных</h2>

23 <p>Классическая структура данных представляет собой определенный способ организации этих самых данных для дальнейшего эффективного использования. Это если кратко. В более развернутом виде - она представляет собой некую упаковку, в которой данные сохраняются в определенной "моделе".</p>

24 <p>Структуры данных делятся на:</p>

25 <ul><li>линейные (стеки, очереди, массивы) - элементы выстраиваются в последовательность либо линейный список. Также линейны и обходы узлов;</li>

26 <li>нелинейные (графы, деревья) - данные выстраиваются без какой-либо последовательности. Также не линейны и обходы узлов.</li>

27 </ul><p>Коснемся основных действий. Данные можно получить, найти, добавить, удалить. Для реализации этих целей существует много разнообразных структур данных. Каждая отдельно взятая более эффективна в одних вопросах и менее эффективна в других. Потому разработчик должен понимать функциональные составляющие каждой структуры. Грамотное применение функциональных свойств структуры данных ускорит решение любой поставленной задачи.</p>

28 <p>Приходится часто искать информацию - укажите одну разновидность. Если нужно постоянно что-либо вставлять - укажите другую. А если частенько приходится выполнять действия по перестановке и удалению - укажите третье решение.</p>

29 <h3>Базовые термины</h3>

30 <p>Перед изучением структуры данных кратко коснемся их основы - терминов, а затем перейдем к применению. К ним относятся:</p>

31 <ul><li>Интерфейс - определенный набор операций, поддерживающих структуру данных. Он присущ каждой структуре. Интерфейс может предоставлять только перечень поддерживаемых операций, тип принимаемых параметров и возвращает тип этих операций.</li>

32 <li>Реализация - обеспечивает внутреннее представление структуры данных, помогает в определении алгоритмов, которые используются в операциях.</li>

33 </ul><h3>Характеристики</h3>

34 <p>Важными характеристиками структур данных являются:</p>

35 <ul><li>Корректность - она должна грамотно реализовывать свой интерфейс.</li>

36 <li>Сложность времени - должно использоваться минимальное количество времени на выполнение операций.</li>

37 <li>Сложность пространства - при проведении операций память должна использоваться минимально.</li>

38 </ul><h3>Какие проблемы можно решить с помощью структуры данных</h3>

39 <p>В связи с тем, что приложения становятся все более сложными, а количество составляющей информации в них постоянно растет, то возникают три проблемы:</p>

40 <ul><li>замедление процесса поиска в связи с ростом данных;</li>

41 <li>ограниченная скорость процессоров. Несмотря на то, что она достаточно высокая, с ростом объема информации и она ограничивается;</li>

42 <li>многократные запросы через поиск на веб-серверах вызывают сбои в их работе.</li>

43 </ul><p>Структуры данных помогают в решение вышеперечисленных проблем. Данные можно организовать в структуры таким образом, что поиск будет осуществляться практически мгновенно.</p>

44 <h3>Случаи выполнения</h3>

45 <p>Чтобы провести сравнение временных промежутков, необходимых для выполнения различной структуры, используются следующие случаи:</p>

46 <ul><li>худший - сценарий, при котором для выполнения конкретной операции потребуется максимальное время, которое только возможно;</li>

47 <li>средний - сценарий, при котором на выполнение операции отводится среднее время;</li>

48 <li>наилучший - сценарий, который отображает кратчайший промежуток времени, необходимый для выполнения операции.</li>

49 </ul><h2>Основные виды структур</h2>

50 <p>К основным видам структуры данных относятся:</p>

51 <h3>Массивы</h3>

52 <p>Это наипростейшие и широко используемые структуры данных, в которых элементы следуют один за другим. Представляет собой контейнер, в котором может храниться фиксированное количество однотипных компонентов.</p>

53 <p>Важнейшие термины:</p>

54 <ul><li>элементами называют все компоненты, хранящиеся в массиве;</li>

55 <li>индексы - местонахождение каждого элемента в массиве выражается целым числовым индексом, используемом для его идентификации.</li>

56 </ul><p>Размерность массива определяет количество индексов в нем. Они бывают одномерными (называют векторами) и многомерными (массив в середине массива). Массивы могут объявляться разными способами на различных языках программирования.</p>

57 <p>Некоторые структуры являются производными массивов (стеки, очереди). В массиве каждый элемент имеет индекс (положительное целое числовое значение), соответствующий тому, какую позицию в массиве он занимает.</p>

58 <p>Язык программирования определяет, с какого значения в массиве начинается нумерация. Во многих языках начальным индексом массива определен 0.</p>

59 <p>Массивы бывают:</p>

60 <ul><li>статическими - характеризуются однородностью данных;</li>

61 <li>динамическими - характеризуются непостоянством размера, который может меняться в ходе выполнения программы. Это усложняет процесс, ухудшает быстроту действий, но работа с информацией становится более гибкой;</li>

62 <li>гетерогенными - характеризуется неоднородностью данных.</li>

63 </ul><p>Основные операции, которые поддерживаются массивами:</p>

64 <ul><li>Traverse - выставляет один за одним все компоненты массива;</li>

65 <li>Insert - добавляет один или несколько элементов по указанному индексу;</li>

66 <li>Get - производит возврат элемента по указанному индексу;</li>

67 <li>Delete - выполняет удаление элемента по указанному индексу;</li>

68 <li>Size - позволяет узнать общую численность элементов, содержащихся в массиве.</li>

69 </ul><h3>Списки</h3>

70 <p>Список является абстрактным типом данных. Существует несколько их разновидностей. Рассмотрим наиболее популярные:</p>

71 <h4>Связные (связанные) списки</h4>

72 <p>Связной список представляет собой массив с конечным множеством элементов (отдельных объектов) и указателями на них.</p>

73 <p>Каждый объект содержит:</p>

74 <ul><li>поле информации (тип данных может быть любым);</li>

75 <li>ссылки (указатели) на последующий узел.</li>

76 </ul><p>Таким образом упорядоченные элементы связного списка связаны друг с другом указателями. Вместе эти группы образуют последовательность.</p>

77 <p>Как и массив, список лежит в основе понятия классической структуры данных. Их функциональные особенности часто сравнивают, т.к. большинство других структур могут быть реализованы с помощью массивов или связных списков. Последний отличается от массива структурной гибкостью. Доступ к спискам осуществляется последовательно, а к массивам - произвольно.</p>

78 <p>Связанные списки бывают следующих видов:</p>

79 <ul><li>Однонаправленные (односвязные) - каждый узел сохраняет адрес либо ссылку на тот узел, который числится следующим. А узел, являющийся последним, содержит последующий адрес либо ссылку как NULL. Линейные однонаправленные списки встречаются чаще всего.</li>

80 <li>Двунаправленные (двусвязные) - имеют две ссылки, которые связаны с каждым отдельным узлом (первая указывает на последующий, вторая - на предыдущий).</li>

81 <li>Круговые (кольцевые) - все узлы списка соединены в круг при отсутствии в последнем NULL. Является подвидом двух предыдущих видов связных списков. Они могут быть одно- или двусвязными.</li>

82 </ul><p>Чтобы односвязный список стал круговым, необходимо в его последний узел вставить указатель на первый элемент. Чтобы двунаправленный список преобразовать в кольцевой, следует добавить две ссылки на узлы: первый и последний.</p>

83 <p>Операции, являющиеся основными:</p>

84 <ul><li>InsertAtEnd - вставка заданного элемента в конце списка;</li>

85 <li>InsertAtHead - вставка заданного элемента в начало списка;</li>

86 <li>Delete - удаление заданного элемента из списка;</li>

87 <li>DeleteAtHead - удаление первого элемента в списке;</li>

88 <li>Search - возвращение заданного элемента из списка</li>

89 <li>isEmpty - в тем случае, когда список пустой, производится возврат True.</li>

90 </ul><h4>Стеки</h4>

91 <p>Являются базовой структурой, в которой реализовано лишь добавление и удаление объектов в начало стека (через его вершину). Представляет собой список элементов, которые организованы по принципу LIFO (на английском языке Last In - First Out, что в переводе означает "последним зашел - первым ушел"). По тому же принципу работает в приложениях функционал "Отменить".</p>

92 <p>Отличное сравнение - стопка тарелок. Чтобы из стопки взять тарелку, необходимо вначале снять верхние тарелки. А положить тарелку можно только на верх стопки.</p>

93 <p>Основные операции:</p>

94 <ul><li>Push - вставка в стек элемента наверху;</li>

95 <li>Pop - удаление верхнего элемента из стека;</li>

96 <li>Pip - отображается содержимое;</li>

97 <li>isEmpty - происходит возврат True в случае, когда стек пустой;</li>

98 <li>Top - возвращает элемент сверху, не удаляя его из стека.</li>

99 </ul><p>Чаще всего в программировании применяется:</p>

100 <ul><li>стек изменений в редакторе кода, позволяющий быстро делать отмену изменений и возвращаться к предыдущему состоянию;</li>

101 <li>стек передвижения по страницам в браузере - позволяет быстро переходить по страницам.</li>

102 </ul><h4>Очереди</h4>

103 <p>Является яркой аналогией с очередью в магазин. Порядок входа в него определяет то, в каком порядке была занята очередь. Первый занявший очередь зайдет первым, за ним - второй и т.д. В очереди используется принцип доступа к данным FIFO (на английском языке - First In First Out, в переводе означает "Первый вошел, первый ушел").</p>

104 <p>Если кратко, то очередью является список, в котором добавление новых элементов допустимо строго в его конец, а извлечение - происходит строго с другого конца, который называют началом списка.</p>

105 <p>Элементы сохраняются последовательно. Но для очереди используется принцип FIFO, а не LIFO.</p>

106 <p>Выполняются операции:</p>

107 <ul><li>Enqueue - вставка элемента в конец очереди;</li>

108 <li>Dequeue - удаление элемента из начала очереди;</li>

109 <li>isEmpty - будет возвращено значение True, если очередь пуста;</li>

110 <li>Top - возвращает первый элемент из очереди.</li>

111 </ul><h4>Дек или двухсторонняя очередь</h4>

112 <p>Дек (двухсторонняя очередь) - это вид списка (стека) с двумя концами. Он позволяет добавлять и извлекать элементы с двух сторон (как в начале, так и в конце).</p>

113 <p>Дек работает одновременно по FIFO и LIFO. Потому он и относится к отдельной программной единице, которая была получена в результате суммирования стека и очереди.</p>

114 <h3>Графы</h3>

115 <p>Графом называют набор узлов (вершин), соединенных между собой связями (называют ребра, дуги).</p>

116 <p>Графы бывают:</p>

117 <ul><li>ориентированными - имеют ребра с единственно возможным направлением между парой связанных вершин;</li>

118 <li>неориентированными - для каждой дуги переход между вершинами может происходить в любом направлении, а также из каждой вершины можно перейти в другую;</li>

119 <li>смешанные - отличаются присутствием дуг, перечисленных выше.</li>

120 </ul><p>Графы могут иметь различную форму:</p>

121 <ul><li>матрицы смежности - таблицы целых чисел, в которой каждая строка либо столбец являются другим узлом на графе. В месте пересечения столбца и строки находится число, указывающее на отношение. Нули указывают, что ребер нет, а единицы - что связи есть;</li>

122 <li>матрицы инцидентности;</li>

123 <li>списка смежности - представлен списком, в котором левая сторона выступает вершиной, а правая - перечнем всех иных узлов, соединенных с ней;</li>

124 <li>списка ребер.</li>

125 </ul><p>В графах используются алгоритмы обхода:</p>

126 <ul><li>в глубину (depth-first search) - обход осуществляется по узлам.</li>

127 <li>в ширину (breadth-first search) - поиск осуществляется по уровням;</li>

128 </ul><p>Стиль дуг граф может быть не только в виде прямой линии, а вершин - выражен в цифрах. Существуют графы, именуемые взвешенными, где ребрам соответствует определенное значение (именуемое его весом). При совпадении концов ребра его называют петлей.</p>

129 <p>Графы довольно часто используются в транспортных и компьютерных сетях, веб-технологиях. По принципу граф построены социальные сети, где люди являются узлами, а дуги - их связями.</p>

130 <h3>Множества</h3>

131 <p>Хранение данных во множество организовано беспорядочно и без повторяющихся значений. В них можно добавлять и удалять объекты, а также есть еще ряд важнейших функций, позволяющих работать одновременно с двумя наборами функций.</p>

132 <p>Так, при двух заданных множествах функции выполнят:</p>

133 <ul><li>Union (объединение множеств) - объединятся все элементы, принадлежащие им обеим. Результат будет возвращен в качестве нового (не имеющего дубликатов);</li>

134 <li>Intersection (пересечение множеств) - будет возвращено новое множество, которому будут принадлежать объекты, имевшиеся в обеих заданных множествах;</li>

135 <li>Difference (разница множеств) - будет возвращено множество с элементами, содержавшимися в одном и не повторявшиеся в другом;</li>

136 <li>Subset (подмножество) - возвращает булево значение, демонстрирующее содержатся ли в множестве все объекты иного.</li>

137 </ul><h3>Map</h3>

138 <p>Map также именуют ассоциативный массив или словарь. Это структура данных, которая сохраняет данные в связке уникальный ключ/ значение. Чаще всего он используется, когда необходим быстрый поиск информации</p>

139 <p>С помощью Map можно:</p>

140 <ul><li>добавить пару;</li>

141 <li>удалить пару;</li>

142 <li>изменить пару;</li>

143 <li>найти значения, которые связаны с определенными ключами.</li>

144 </ul><h3>Хэш-таблицы</h3>

145 <p>Это структуры, реализующие интерфейс Map, позволяющий сохранять пару (ключ/ значение). Хеширование применяется для нахождения в массиве значения индекса, по которому будет найдено нужное значение.</p>

146 <p>При детальном рассмотрении можно увидеть, что хэш-таблица является массивом. В нем хэш-функция является индексом.</p>

147 <p>Коллизией называют хеширование двух вводов, имеющих одинаковый цифровой выход. Цель - уменьшение числа коллизий.</p>

148 <p>Когда в хэш-таблицу вводится пара ключ/ значение, с уникальным ключом проводится хеширование, после чего он становится числом. Оно в последствии используется в качестве фактического ключа, в котором это значение хранится. При повторной попытке получить доступ к этому же ключу, хеш-функция проведет его обработку и вернет то же числовое значение, которое в дальнейшем будет использовано для нахождения связанного значения. Это способствует быстрому поиску.</p>

149 <p>Производительность хеширования зависит от:</p>

150 <ul><li>функций хеширования;</li>

151 <li>параметров хэш-таблиц;</li>

152 <li>методов устранения коллизий.</li>

153 </ul><h3>Деревья</h3>

154 <p>Деревом является иерархическая структура данных. Она составлена из узлов (вершин) и дуг (ребер). При близком рассмотрении можно понять, что деревьями являются связанные графы, не имеющие цикличности.</p>

155 <p>От деревьев, встречающихся в природе, классическое математическое дерево отличается тем, что корень последнего расположен вверху. А его ветви "растут" сверху вниз.</p>

156 <p>Дереву присущи характеристики:</p>

157 <ol><li>Каждое имеет единственную вершину (корневой узел), расположенную сверху и не имеющую предков. Никакая вершина не ссылается на корень, а из него можно достичь любой имеющейся вершины дерева (это следствие свойства связанности древовидной структуры).</li>

158 <li>Вершины, которые не имеют потомков (не ссылаются на иные) называются терминальными узлами (листьями).</li>

159 <li>Объекты, которые располагаются между вершиной и листьями, называются промежуточными узлами.</li>

160 <li>Каждая вершина древовидной структуры имеет лишь единого предка, а если он является корневым - не имеет ни одного предка.</li>

161 <li>У корневого узла может быть от нуля или более потомков.</li>

162 <li>У каждого дочернего узла может быть от нуля или более дочерних вершин.</li>

163 </ol><p>Поддеревом называется часть древовидной структуры, которая имеет вершину и имеющиеся потомки.</p>

164 <p>Существует несколько типов деревьев. Чаще других встречается бинарное дерево. Оно представляет собой структуру данных с иерархией, в которой каждый узел имеет определенное значение (которое является ключом) вместе со ссылками на потомков (слева и справа).</p>

165 <p>Для деревьев используются следующие методы обхода:</p>

166 <ul><li>прямой - осуществляется сверху вниз (начинается с посещения предков и постепенно переходит к потомкам);</li>

167 <li>обратный - обход осуществляется снизу вверх (прежде посещаются потомки, потом - предки);</li>

168 <li>симметричный - обход осуществляется слева направо (по очереди осуществляется обход поддеревьев главного дерева).</li>

169 </ul><p>Выражение информации в виде древовидных структур оправдано в том случае, если у нее есть явная иерархия. Иерархически выраженная структура потребуется при работе с данными о географических объектах, служебных должностях и т.д. В таких случаях информацию лучше представлять в виде классических математических деревьев.</p>

170 <h4>Дерево двоичного (бинарного) поиска</h4>

171 <p>Кроме вышеуказанных характеристик деревьев, дереву двоичного поиска характерны еще ряд характеристик:</p>

172 <ol><li>Узел может иметь не больше двух детей (потомков).</li>

173 <li>Левые потомки меньше текущего узла, что меньше, чем у правых детей.</li>

174 </ol><p>Бинарные деревья помогают существенно ускорить работу объектами (находить, удалять, добавлять их).</p>

175 <h4>Префиксные деревья (Trie), боры, лучи</h4>

176 <p>Префиксные деревья, именуемые иногда борами и лучами, являются разновидностью древовидных структур. Они особенно эффективны для работы со строками, т.к. обеспечивают быстрый поиск информации. По сути бор является деревом поиска.</p>

177 <p>Чаще всего боры используют для:</p>

178 <ul><li>поиска слов в словарях;</li>

179 <li>автозавершений в поисковиках;</li>

180 <li>IP-маршрутизации.</li>

181 </ul><p>Бор хранит данные в узлах. Такие деревья часто используются для хранения слов. Они хранятся в борах сверху вниз - в каждом узле по букве.</p>

182 <p>Для записи слова необходимо проследовать по ветвям дерева, вписывая за раз по одной букве. Если порядок букв не похож на другие слова в дереве либо слово заканчивается, шаги начинают расходиться. В каждой вершине находится буква (данные) вместе с логическим значением, которое указывает на то, является ли данный узел в слове последним или нет.</p>

183 <h4>Двоичная куча</h4>

184 <p>Так называют полное дерево, у которого в каждом узле до двух детей. У двоичной кучи все уровни до последнего заполнены полностью. В последнем уровне заполнение ведется слева направо.</p>

185 <p>Она может быть:</p>

186 <ul><li>максимальной - у родительских узлов ключи всегда больше либо равны тем ключам, которые у детей;</li>

187 <li>минимальной - у родительских узлов ключи меньше либо равны ключам у дочерних элементов.</li>

188 </ul><p>В двоичной куче прослеживается важность порядка между уровнями, но не между узлами одного уровня.</p>

189 <p>Это вся важная информация о структурах данных программы. Изучайте материал, находите новое и применяйте на практике. Если возникли вопросы - задавайте. Обязательно ответим на них.</p>

190 <a></a>