Одномерный массив

Таблица на основе одномерного массива может быть представлена

следующими структурами данных на языке Си:

#define tableSize 1000 // размер таблицы имен

int i_table = -1;

// индекс последнего занятого элемента

// для пустой таблицы равен -1

struct element table[tableSize]; // таблица имен

Поиск элемента. Может осуществляться по любому алгоритму. Од-

нако наиболее эффективным для упорядоченных таблиц является двоичный

поиск, при котором на каждом шаге пространство поиска делится пополам до

тех пор, пока не будет найден требуемый элемент или зафиксировано его от-

сутствие.

Включение. Осуществляется после того, как в результате поиска

подтверждено отсутствие элемента с заданным ключом. Завершение поиска

обычно сопровождается нахождением индекса элемента_, ключ которого

предшествует исходному. Поэтому новый элемент можно вставить в таблицу

вслед за ним. Вставка должна сопровождаться сдвигом всех последующих

элементов на одну позицию в сторону возрастания индекса.

Удаление. После нахождения элемента в таблице его можно удалить

путем сдвига всех последующих элементов на одну позицию в сторону

уменьшения индекса. В связи с низкой эффективностью такого подхода

можно вместо сдвига специальным образом маркировать такой элемент (на-

пример, задавать пустое имя), а само сжатие осуществлять после нескольких

удалений или при полном заполнении пространства памяти, отведенного

под таблицу.

Очистка таблицы. Осуществляется сбросом индекса последнего за-

нятого элемента, то есть присваивания ему в данном случае значения, равно-

го -1.

Преимущества. Организация таблицы в виде одномерного массива по-

зволяет распределить его в непрерывной области памяти и обеспечивает не-

посредственный доступ к любому элементу по его индексу. Данному методу

присуща простота организации, быстрота поиска элементов и очистки, на-

глядность структуры таблицы.

Недостатки. Максимальный размер таблицы необходимо фик сировать

до ее заполнения, что не всегда удобно из-за отсутствия информации о коли-

честве заносимых элементов. Это может привести к переполнению таблицы

в процессе работы программы или наоборот к неэффективному использова-

нию выделенного пространства памяти. При добавлении элементов в упоря-

доченную таблицу необходимо затрачивать дополнительное время на пере-

мещение элементов, предшествующих вставляемому. При удалении элемента

приходится тратить время на сжатие таблицы. Использование удаления с ус-

тановкой признака пустого элемента ведет к замедлению поиска и неэффек-

тивному использованию памяти (последнее, однако, не столь существенно,

так как за таблицей фиксируется заранее отведенное пространство памяти).