Коллекции

Понятие коллекции. Классификация

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

Коллекции с индексным доступом

К данному виду относят словари и хеш-таблицы.

Хеш-таблица – коллекция, в которой имеется набор ключей и связанных с каждым ключом данных. Поиск и выборка данных осуществляется по ключу, который трансформируется в целый индекс, используемый для нахождения данных.

Словарь – разновидность хеш-таблицы, в которой ключом выступает слово, а значением – строка, указывающая его определение. К значению осуществляется прямой доступ с использованием ключа в качестве индекса. В результате словарь подобен массиву, за исключением того, что индексы не должны быть целыми числами. Словари также часто называют ассоциативными массивами.

Коллекции с прямым доступом

Массив – совокупность однотипных элементов, расположенных в смежных ячейках памяти. Для доступа к элементам используют числовой индекс – порядковый номер в наборе.

Запись – это базовая структура коллекций для сохранения данных, которые могут состоять из разных типов. Для многих программ различные элементы данных ассоциированы с одним объектом. Например авиабилет включает такие данные, как номер рейса, номер места, имя пассажира, стоимость. Запись связывает поля структуры данных при обеспечении прямого доступа к данным в отдельных полях.

Коллекции с последовательным доступом

Более общей коллекцией является список, сохраняющий элементы в определенном порядке. Структура, называемая линейным списком содержит произвольное число элементов. Размер списка изменяется, после удаления и добавления к нему новых элементов. Первый элемент находится в начале или голове списка, а последний – в хвосте списка. Каждый элемент списка имеет связь с последующим, таким образом можно передвигаться от одного элемента к другому. Для доступа к элементам списка необходимо выполнять прохождение от головы до нужной позиции. Если движение по списку можно осуществлять только в одном направлении, то список называется однонаправленным, если в двух направлениях – двунаправленный. Если элемент списка хранит информацию об одном “соседе”, то список называется односвязным, если о двух – двусвязным.

Стеки и очереди – особые версии линейного списка с ограниченным доступам к элементам данных. В стеке элементы добавляются и удаляются через один конец списка, называемым вершиной. Операция удаления элемента называется извлечением из стека, операция добавления называется помещением элемента в стек. При помещении элемента в стек все остальные элементы опускаются вниз, уступая место на вершине новому элементу. Когда элемент удаляется, остальные перемещаются в обратном порядке. Последний элемент, помещенный в стек, является первым извлекаемым.

Очередь – это список с доступом в начало и конец. Элементы вставляются в конец, а извлекаются из начала списка. Иногда используются очереди приоритетов. В них добавление новых элементов происходит в конец, а удаление – из произвольного места согласно приоритету.

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

Нелинейные коллекции

Иерархическая коллекция – набор элементов, разделенных на уровни. Элементны на текущем уровне могут иметь несколько связанных элементов на нижнем уровне. Особой иерархической коллекцией является дерево, в которой на верхнем уровне имеется один эелемент – корень. Элементы в дереве называют узлами, каждый из которых указывает на нисходящие узлы, называемыми потомками. Каждый элемент, за исключением корня имеет одного потомка. Дерево является идеальной структурой для описания файловой системы с каталогами и подкаталогами.

Группа – представляет те коллекции, которые содержат элементы без упорядочивания. Набор переменных в программе – яркий пример группы. Сюда можно отнести граф – структуру, задающую набор вершин и набор связей, соединяющих вершины. Графы широко используются в планировании, транспортных задачах и в задачах проектирования. Сеть – особая форма графа, которая приписывает вес каждой связи. Вес указывает стоимость использования связи при прохождения графа. Так в задаче коммивояжера используется сеть для представления городов и стоимостей проезда из города в город.

Программная реализация списков

Рассмотрев классификацию коллекций приступим к практической их реализации. Начнем с общих вопросов. Список может храниться в памяти двумя способами. Во-первых, это традиционное последовательное расположение элементов с смежных областях памяти, а во-вторых, в произвольных областях с динамическими связями между собой. Основным преимуществом динамически связанных списков является простота изменения порядка следования элементов. В массиве для изменения порядка мы вынуждены делать перестановку элементов, что отнимает время и приводит к массе ненужных операций. С ростом размера элемента и их числа эти факторы сильно влияют на выполнение программы. В динамическом списке нет необходимости перемещать элементы, важно только изменить адресные связи. Для организации списка нам необходимы динамические объекты, расположенные в любых областях памяти и связанных между собой через адреса. Элемент списка должен содержать информационные поля для хранения данных и служебные поля для хранения адресов связанных с ним элементов. В языках программирования используются составные типы, которые могут включать несколько полей с данными. Для хранения адресов используются специальные переменные указатели. Таким образом, для реализации элемента списка нам потребуются составной тип и указатели.

struct Item
{
		char *text;     // информационные поля
		Item *next;    // служебные поля
};

Рассмотрим программные реализации общих для односвязного списка операций:
СОЗДАНИЕ ПЕРВОГО ЭЛЕМЕНТА

Item *unit(char *str)
{
	Item *head=new Item;
	head->text=new char[strlen(str)+1];
	strcpy(head->text,str);
	head->next=NULL;
	return head;
}

ДОБАВЛЕНИЕ ЭЛЕМЕНТА (в голову n = 0)

Item *addItemNOM(Item *head,char *buf,int n)
{
	Item *temp=head;
	Item *item=new Item;
	item->text=new char[strlen(buf)+1];
	strcpy(item->text,buf);
	if(n==0)
	{
		item->next=head;
		return item;
	}
	else
	{
		for(int i=1;i<(n-1) && head->next;i++)
			head=head->next;
		item->next=head->next;
		head->next=item;
		return temp;
	};
}

УДАЛЕНИЕ ЭЛЕМЕНТА

Item *removeItemNOM(Item *head,int n)
{
	Item *temp=head,*item=0;
	if(n==0)
	{
		head=head->next;
		delete temp;
		return head;
	}
	else
	{
		for(int i=1;inext->next;i++)
			head=head->next;
		item=head->next;
		head->next=head->next->next;
		delete item;
		return temp;
	};
}

УДАЛЕНИЕ СПИСКА

bool removeALL(Item *head)
{
	if(!head) return false;
	Item *temp;
	while (head)
	{
		temp=head->next;
		delete head;
		head=temp;
	}
	return true;
}

СОХРАНЕНИЕ СПИСКА

void saveall(Item *head,FILE *fp)
{
while(1)
{
fwrite(head,sizeof(Item),1,fp);
if(head->next)
head=head->next;
else
return;
}
}

ЗАГРУЗКА СПИСКА ИЗ ФАЙЛА

Item  * loadall(Item *head,FILE *fp)
{
fseek(fp,0L,0);
head=new Item; int a;
BOOK *old_head=head,*temp;
while((a=fread(head,sizeof(Item),1,fp)))
{
head->next=new Item;
temp=head;
head=head->next;
}
head=temp;
head->next=NULL;
return old_head;
}

КОПИРОВАНИЕ СПИСКА

Item  * copy(Item  * head1, Item  * head2)
{
head2=new Item;
Item  * old_head2=head2;
while(1)
{
memcpy(head2,head1,sizeof(Item));
if(head1->next)
{
head2->next=new Item;
head1=head1->next;
head2=head2->next;
}
else
break;
}
head2->next=NULL;
return old_head2;
}
ПОИСК ПО ПОЛЮ
Item *search_title(Item  * head,char  * text)
{
while(head->next)
{
if(!strcmp(head-> text, text)) return head;
head=head->next;
}
if(!strcmp(head-> text, text))
return head;
else
return NULL;
}