8.3 Понятие контейнера

Под контейнером понимается такая организация хранения данных, при которой возможно хранить разнотипные данные. В контейнер можно складывать строки символов, массивы, различные структуры и прочее. Простейший пример контейнера можно сделать из линейного односвязанного списка, заменив в описании элемента списка описание данных:

typedef struct LinkTag
{
      struct LinkTag *next;
      void *data; //это указатель на любые типы данных
};

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

Основные функции для контейнера следующие:

1. создать контейнер;
2. вставить новый элемент данных;
3. удалить элемент списка;
4. механизм просмотра ForEach(beg,end,Func) и ForEachParam(beg,end,FuncParam,Param);
5. механизм поиска Find(beg, end,Comp) и Find(beg, end,CompParam,Param);
6. механизм сортировки Sort(beg,end, Comp2).
7. удалить контейнер Delete(DeleteElement).

Здесь beg и end - указатели на начало и конец поиска. Comp - функции сравнения для поиска и сортировки. DeleteElement - функция удаления элемента данных. Контейнер, организованный на основе двухсвязного списка, можно найти в файлах KruList.h и KruList.cpp Переход на идеи объектно-ориентированного программирования дает новые возможности использования контейнеров, которые будут описаны далее.

Специальные списки : cтек, очередь, дек.

Стек - это линейный список, у которого операции вставки и удаления производятся с одного конца. Обычно стек имеет один указатель, называемый вершиной стека, и две функции: Push (вставка на вершину стека) и Pull (удаление элемента на вершине стека). Иногда вводят функцию Top - посмотреть данные на вершине стека.

Очередь - это линейный список, у которого операции вставки и удаления производится с разных концов. Для очереди необходимо хранить два указателя: head - указатель на голову, tail - указатель на хвост. Как известно, очередь растет с хвоста, а уменьшается с головы. Поэтому операция Insert - вставка в очередь - производится с хвоста. А операция Delete (Service - обслужить) - с головы.

Дек - это линейный список, у которого операции вставки и удаления производятся с обоих концов. Для этого пишется две функции вставки (InsertHead, InsertTail) и две функции удаления, DeleteTail и DeleteHead.

Описанный выше односвязный список реализован как стек. А двухсвязный список - это очередь. Для того, чтобы построить свой стек, очередь или дек, можно воспользоваться контейнером.