В.А. Антонюк, А.П. Иванов - Программирование и информатика (Краткий конспект лекций) (1109543), страница 9
Текст из файла (страница 9)
Потом следует освободитьпамять массива старого размера. Очевидно,Рис. 8: Вставка элементачто при такой вставке будут скопированывсе элементы массива, и чем массив больше, тем больше элементов придётся скопировать.Аналогично и для удаления одного элемента из произвольного места массива – даже, еслимы не будем уменьшать выделенную память, нам в среднем придётся скопировать примерно половину элементов, а «половина элементов» – это линейная зависимость от размерамассива.Теперь посмотрим, как быстро можно найти элемент в массиве с заданным значением. Еслине предпринимать специальных мер, то мы вынуждены будем просматривать элементымассива один за другим.
В среднем мы найдём наш элемент «где-то в середине», то есть,опять же – на половине длины массива. Поэтому и поиск элемента в массиве – линейнаяпо его размеру операция.Ранее указывалось, что если поддерживать массив в отсортированном по возрастанию значений порядке, то можно будет найти элемент с нужным значением методом деления егодлины пополам (дихотомия), что даст логарифмическую, а не линейную зависимость времени выполнения этой операции от размера массива.
На больших массивах это даёт колоссальный выигрыш в производительности.10.3.Стек, дека, очередьЕсли сузить класс решаемых задач, то с помощью совсем небольшого усложнения структуры данных можно добиться более эффективного выполнения операций вставки и удаленияэлемента в конце массива.А именно, давайте – кроме размера памяти, выделенной под хранение элементов массива, –заведём в структуре данных ещё одно поле, в котором будем хранить количество элементовв нашем массиве (буфере):struct array {double* A;unsigned total; /* всего выделено память под столько элементов */unsigned size; /* столько из них используется реально */};Теперь мы можем в пределах размера total добавлять и удалять элементы в хвосте массива за константное время.43То есть, такая вставка и удаление независят от количества элементов, ранееsizetotalсохраненных в массив, фактически, намРис.
9: Вставка-удаление в конценадо скопировать (один) новый элементи увеличить одну целочисленную переменную (size) с проверкой, что она не превысит полного размера массива total.Если же нам размера total не хватит для очередной операции добавления элемента, тоникуда не денешься, нужно будет выделять увеличенный размер памяти и копировать всеэлементы из старого буфера в новый и это будет линейная по количеству элементов операция. Однако и здесь можно применить некоторую оптимизацию, чтобы такая проблемавозникала как можно реже. Обычно при нехватке буфера просто удваивают его размер,в результате размер буфера растет экспоненциально и он за несколько таких операцийбыстро дорастает до такого размера, когда его хватит для решения всей задачи.Тактика удаления элементов ещё проще: при уменьшении количества элементов буферобычно не уменьшают, при этом, конечно, возникает перерасход памяти, но зато операций,линейных по количеству элементов массива нет вовсе – любая операция удаления любогоколичества элементов в конце массива становится константной, не зависящей от количестваэлементов.Отметим, что операция взятия элемента по индексу никуда не делась – она по-прежнемузанимает константное время.
А вот поиск элемента по значению возможен только линейный– мы ведь добавляем элементы только в конец, поэтому упорядочить их по значению неможем.Задачи, связанные с добавлением-удалением элементов в конец массива возникают достаточно часто, поэтому в программировании выделяют специальный вид контейнера, называемый стек (stack, стопка). Такой контейнер чаще всего реализуется в виде описанногоздесь динамического массива, но поддерживает он всего две операции: «добавить элемент»– push() и «извлечь элемент» – pop(). При этом элементы извлекаются в порядке, обратном поступлению – «последний пришедший уходит первым» (LIFO: LastIn, FirstOut).Наш контейнер можно ещё усложнить для того, чтобы организовать двустороннюю вставкуи удаление элементов за константное время.
Для этого, кроме параметров буфера, хранящего элементы, нам нужно будет запомнить положение начала и конца области буфера,занятой под хранение элементов. Такой контейнер называется декой (deque, double-endedqueue – двусторонняя очередь):struct deque {double* A;unsigned total;/* всего выделено память под столько элементов */unsigned first; /* реальный индекс первого элемента в буфере */unsigned end; /* индекс элемента, следующего за последним в буфере */};Если first равен end – то дека пуста, еслинет, то она содержит end – first элеменfirstlasttotalтов. При этом в самом начале first и endустанавливают на середину буфера – чтобыРис. 10: Хранение элементов в декемаксимизировать свободное пространство,доступное для вставки и удаления элементов в начало или конец деки.44Когда после многих вставок в начало декиэлемент first достигнет начала выделенlastfirsttotalного буфера (либо элемент last достигнетtotal), то можно в простейшем случае сраРис.
11: Хранение элементов в декезу увеличить размер буфера, но можно этудорогую по времени выполнения операциюи отложить, если «обернуть» достигший края буфера конец нашей деки через противоположный край буфера.При этом усложнится алгоритм определения -того элемента, однако, эта операция всеравно останется константной по отношению к количеству элементов в деке (т.е. не будетзависеть от этого количества).Для определения момента, когда уже абсолютно необходимо увеличить размер буфера, применяют следующее правило: если first достигает last из положения «first меньше last»,то это означает, что наша дека опустела, если же наоборот, first достигает last из положения «first больше last», то это означает, что свободное место в буфере закончилось и егоразмер нужно увеличить.Увеличение размера буфера можно производить, пользуясь той же тактикой удвоения егоразмера, что и для динамического массива, только при этом следует аккуратно скопироватьэлементы из старого буфера в новый так, чтобы они заняли середину нового массива (см.схему 3.1).Итак, дека поддерживает операции: push_front(), pop_front(), push_tail(), pop_tail()и выполняет их за константное время.
Также за константное время можно получить адрес-того по порядку элемента деки (операция взятия элемента по индексу), как в массиве,хотя эта операция и будет производиться дольше, чем для массива, – из-за необходимостивычислять реальное положение нужного элемента, – но она всё равно не будет зависетьот количества хранимых элементов.Отметим, что реализация деки в стандартных библиотеках устроена сложнее, чем это было рассказано выше: для того, чтобы чуть быстрее вычислять индекс и более предсказуемовыделять новую память при ее нехватке, – но в целом принцип работы деки остаётся похожим на то, что было здесь рассказано. Описанная здесь реализация минимизирует накладныерасходы памяти.На практике довольно часто встречаются более жестко определенные направленные очереди: когда элемент вставляется в очередь с одного конца, а извлекается всегда с другогоконца очереди – так же, как это происходит в реальных очередях, например, в столовой.Поэтому часто определяют для таких очередей самостоятельный контейнер, который поддерживает две операции: вставки в хвост очереди и удаление из начала очереди.
Так же какдля стека, их можно назвать push() и pop(), но следует помнить, что порядок извлеченияэлементов тут будет другой: LIFO (LastIn, FirstOut).10.4.СписокВ том случае, когда нужно за константное время вставить новый элемент в произвольноеместо контейнера, имеет смысл применить другую структуру данных, которая называетсяодносвязным списком. В списке каждый элемент содержит кроме тех данных, которыенадо сохранить, ещё одно служебное поле – указатель на следующий элемент списка:45struct ListElem {double val;struct ListElem *next;};Головной элемент списка обычно задаётся отдельной структурой, в которой хранится указатель первого элемента списка и количество хранимых элементов:struct ListHead {struct ListElem *start;unsigned size;};startx1p1x2p2x3p3x4NULLРис.
12: Хранение элементов в спискеПоследний элемент списка маркируется нулевым (NULL) указателем в поле next.Рассмотрим процедуру вставки элемента после указанного:startx1p1x2p21x21x3p3x4 NULLp2Рис. 13: Вставка в списокТо есть, мы присвоили двум указателям новые значения – и добились вставки в нужнуюпозицию. Очевидно, что в отличие от динамического массива эта операция будет константной, не зависящей от количества элементов. Именно ради этого мы пошли на существенныенакладные расходы – мы на каждый элемент храним дополнительный указатель, которыйзанимает 4 или 8 байт. Даже если мы храним вещественные числа – это означает практически удвоение размера занимаемой контейнером памяти, что уж говорить про случай,когда хранить надо более мелкие данные (байты).Кроме того, нам пришлось отказаться от такой полезной операции, как нахождение элемента по его индексу – в списках, чтобы добраться до -того элемента нужно отсчитать элементов от начала списка.
То есть, операция нахождения элемента по его индексу будеттакой же, как операция нахождения элемента по его значению – линейно зависящей отколичества сохраненных в список элементов.На практике чаще бывает нужно вставить новый элемент несписка, а перед ним.startp1x1p21x21заp3x3указанным элементомNULLx4p2x2Рис. 14: Вставка в список перед нужным элементом46Для того, чтобы получить нужный результат, обычно вставляют элемент за указаннымэлементом, как в предыдущем случае, но после этого обменивают значения, хранимые вдвух соседних элементах.Удаление элемента, следующего за указанным тоже константная операция:startp2x1p2x2p3NULLx4x3Рис.
15: Удаление из списка элемента, следующего за указаннымАналогично тому, как это делалось при вставке, можно реализовать удаление указанногоэлемента: удаляется элемент, следующий за указанным, но предварительно обмениваютсязначения двух элементов.startp1x1p3x3p3NULLx4x3Рис. 16: Удаление из списка указанного элементаОтметим, что константной является операция добавления в список любого количества элементов, то есть, вставка одного списка в другой выполняется практически с той же скоростью, что и вставка одного элемента (сравнить с массивом).Довольно сильно влияет на производительность работы со списками то, в каком порядкемы храним элементы списка, в какую позицию мы их вставляем новые элементы.
Типичнаяоперация – это «поиск со вставкой», для неё логичнее всего вставлять новый элемент вхвост списка: ведь при поиске элемента мы просмотрели список от начала до конца, т.е.мы уже находимся на последнем элементе, и если нужно добавить новый элемент, то мы егодобавим прямо здесь. Ничуть не сложнее вставка нового элемента в голову списка. Однаков обоих случаях, для того, чтобы убедиться, что нужного элемента ещё нет в списке, мыдолжны просмотреть этот список от начала до конца, перебрать все его элементы.Можно сэкономить вдвое при поиске, если поддерживать наш список отсортированным позначениям элементов – в этом случае нам в среднем придётся просмотреть не весь список, аего половину, прежде, чем мы удостоверимся, что нужного элемента в списке нет. Вставкаэлемента в этом случае производится ровно в том месте, где завершился наш поиск.На практике часто бывает нужно перейти от текущего элемента не только к последующемуза ним элементу, но и к предыдущему.
Если для решения этой задачи не жалко выделитьеще по одному указателю на каждый элемент списка, то можно организовать двусвязныйсписок:start(p0)p1x1p2x2NULLp3x4x3p0Рис. 17: Двусвязный список47NULLp1p210.5.Двоичное (бинарное) дерево поискаПростое дерево поискаВ тех случаях, когда основной операцией является «поиск со вставкой» элемента, реализация контейнера в виде отсортированного массива не будет эффективной по временивставки и удаления.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
