3. Линейные таблицы
 

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

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

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