2014-02-17
755
Основные структуры данных
Под циклической структурой данных понимается набор однотипных элементов (массив). Существуют два принципиально различных способа размещения циклических структур данных в памяти компьютера: вектор и связанный список.
Вектор соответствует хранению данных в памяти последовательно, друг за другом. Здесь, как правило, данные имеют одинаковый размер. Также вектор может хранить не сами данные, а указатели на них, сами данные при этом могут размещаться в различных частях памяти и иметь различный размер. Доступ к элементу осуществляется по адресу, получаемому сложением базового адреса вектора и смещения. При данных одного размера смещение получается умножением номера элемента на размер элементов. Так как все данные хранятся последовательно, требуется выделять в памяти место сразу на все данных, что ограничивает возможности роста массива.
Связанный список соответствует хранению каждого данного по своему адресу, независящему от адресов других элементов. Каждый элемент хранит служебную информацию — адреса одного или нескольких соседних элементов, благодаря чему осуществляется связь между всеми элементами списка. Также может храниться указатель на управляющую структуру, хранящую обобщённую информацию о списке, например, размер, адрес первого элемента и т.д. В списке нет ограничений на размер каждого элемента и на рост списка.
|
|
|
С помощью списков могут быть представлены не только одномерные и двумерные массивы, но и деревья, сети и другие структуры, имеющие сложные связи между элементами.
Каждый элемент односвязанного список хранит адрес только следующего элемента, поэтому доступ может быть осуществлён только от начала списка к концу. Элемент двусвязанного списка хранит адреса как предыдущего, так и следующего элементов списка. Это увеличивает удобство работы со списком, но увеличивает размер каждого элемента.
Сравнивая два способа размещения циклических структур в памяти можно отметить следующие относительные достоинства каждого из них.
Вектор: более быстрый доступ к элементу; малые расходы памяти на вспомогательные структуры данных. Список: размер ограничен только объёмом доступной виртуальной памяти; более быстрое добавление и удаление элементов (кроме последнего). Эти достоинства и недостатки проявляются сильнее с увеличением числа элементов.
Итератор – указатель на определенный элемент составной структуры данных.
В связанных списках, как правило, обращение к элементу происходит не через индекс, а через итератор. Итераторы содержат методы перехода к следующему и предыдущему (для двусвязанного списка) элементу.
|
|
|
Пример реализации связанного списка
struct Item
{
char data[256];
Item *next;
};
struct LinkedList
{
Item *last;
// эффективнее хранить последний элемент, т.к. из него //можно получить первый за 1 шаг
};
// добавить после
void PushAfter (Item *item, Item* newitem)
{
newitem->next = item->next;
item->next = newitem;
}
// исключить элемент, следующий за текущим
void RemoveAfter(Item *item)
{
Item *t = item->next->next;
item->next->next = NULL;
item->next = t;
}
Графическая интерпретация операций над вектором и списком представлена на рис. 3.1.
Рис. 3.1. Графическая интерпретация вектора и односвязанного списка: а — вектор, б — список, в — вставка в вектор, г — вставка в список
