Очередь: понятие, структура, операции

О́чередь — структура данных с дисциплиной доступа к элементам «первый пришёл — первый вышел» . Добавление элемента возможно лишь в конец очереди, выборка — только из начала очереди , при этом выбранный элемент из очереди удаляется.

Описание очереди выглядит следующим образом:

structимя_типа {

информационное поле;

адресное поле1;

адресное поле2;

};

где информационное поле – это поле любого, ранее объявленного или стандартного, типа;

адресное поле1, адресное поле2 – это указатели на объекты того же типа, что и определяемая структура, в них записываются адреса первого и следующего элементов очереди.

Очередь как динамическую структуру данных легко организовать на основе линейного списка. Поскольку работа идет с обоими концами очереди, то предпочтительно будет использовать линейный двунаправленный список. Хотя для работы с таким списком достаточно иметь один указатель на любой элемент списка, здесь целесообразно хранить два указателя – один на начало списка (откуда извлекаем элементы) и один на конец списка (куда добавляем элементы). Если очередь пуста, то списка не существует, и указатели принимают значение NULL.

Описание элементов очереди аналогично описанию элементов линейного двунаправленного списка. Поэтому объявим очередьчерез объявление линейного двунаправленного списка:

structQueue {

Double_List *Begin;//начало очереди

Double_List *End; //конецочереди

};

. . . . . . . . . .

Queue *My_Queue;//указатель на очередь

Основные операции, производимые с очередью:

· создание очереди;

· печать (просмотр) очереди;

· добавление элемента в конец очереди;

· извлечение элемента из начала очереди;

· проверка пустоты очереди;

· очистка очереди.

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

//созданиеочереди

voidMake_Queue(int n, Queue* End_Queue){

Make_Double_List(n,&(End_Queue->Begin),NULL);

Double_List *ptr; //вспомогательныйуказатель

ptr = End_Queue->Begin;

while (ptr->Next != NULL)

ptr = ptr->Next;

End_Queue->End = ptr;

}

//печатьочереди

voidPrint_Queue(Queue* Begin_Queue){

Print_Double_List(Begin_Queue->Begin);

}

//добавлениеэлементавконецочереди

voidAdd_Item_Queue(intNewElem, Queue* End_Queue){

End_Queue->End = Insert_Item_Double_List(End_Queue->End,

0, NewElem)->Next;

}

//извлечение элемента из начала очереди

intExtract_Item_Queue(Queue* Begin_Queue){

intNewElem = NULL;

if (Begin_Queue->Begin != NULL) {

NewElem = Begin_Queue->Begin->Data;

Begin_Queue->Begin=Delete_Item_Double_List(Begin_Queue->Begin,0);

//удаляем вершину

}

returnNewElem;

}

//проверка пустоты очереди

boolEmpty_Queue(Queue* Begin_Queue){

returnEmpty_Double_List(Begin_Queue->Begin);

}

//очисткаочереди

voidClear_Queue(Queue* Begin_Queue){

returnDelete_Double_List(Begin_Queue->Begin);

}

Деки

Деком (англ. deque – аббревиатура от double-ended queue, двухсторонняя очередь) называется структура данных, в которую можно удалять и добавлять элементы как в начало, так и в конец. Дек хранится в памяти так же, как и очередь. Система команд дека:

Частные случаи дека – это ограниченные деки:

· дек с ограниченным входом – из конца дека можно только извлекать элементы;

· дек с ограниченным выходом – в конец дека можно только добавлять элементы.

Данная структура является наиболее универсальной из рассмотренных выше линейных структур. Накладывая дополнительные ограничения на операции с началом и/или концом дека, можно осуществлять моделирование стека и очереди.

Однако применительно к деку целесообразно говорить не о начале и конце как в очереди, а о левом и правом конце.

Описание элементов дека аналогично описанию элементов линейного двунаправленного списка. Поэтому объявим дек через объявление линейного двунаправленного списка:

· создание дека;

· печать (просмотр) дека;

· добавление элемента в левый конец дека;

· добавление элемента в правый конец дека;

· извлечение элемента из левого конца дека;

· извлечение элемента из правого конца дека;

· проверка пустоты дека;

· очистка дека.

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

//создание дека

void Make_Deque(int n, Deque* End_Deque){

Make_Double_List(n,&(End_Deque->Begin),NULL);

Double_List *ptr; //вспомогательный указатель

ptr = End_Deque->Begin;

while (ptr->Next != NULL){

ptr = ptr->Next;

}

End_Deque->End = ptr;

}

//печать дека

void Print_Deque(Deque* Begin_Deque){

Print_Double_List(Begin_Deque->Begin);

}

//добавление элемента в правый конец дека

void Add_Right_Item_Deque(int NewElem, Deque* End_Deque){

End_Deque->End =Insert_Item_Double_List(End_Deque->End,2,NewElem);

End_Deque->End = End_Deque->End->Next;

}

//добавление элемента в левый конец дека

void Add_Left_Item_Deque(int NewElem, Deque* Begin_Deque){

Begin_Deque->Begin =

Insert_Item_Double_List(Begin_Deque->Begin, 1, NewElem);

}

//извлечение элемента из левого конца дека

int Extract_Left_Item_Deque(Deque* Begin_Deque){

int NewElem = NULL;

if (Begin_Deque->Begin != NULL) {

NewElem = Begin_Deque->Begin->Data;

Begin_Deque->Begin=Delete_Item_Double_List(Begin_Deque->Begin,0);

//удаляем вершину

}

return NewElem;

}

//извлечение элемента из правого конца дека

int Extract_Right_Item_Deque(Deque* End_Deque){

int NewElem = NULL;

if (End_Deque->End != NULL) {

NewElem = End_Deque->End->Data;

Delete_Item_Double_List(End_Deque->End, 1);

//удаляем вершину

}

return NewElem;

}

//проверка пустоты очереди

bool Empty_Deque(Deque* Begin_Deque){

return Empty_Double_List(Begin_Deque->Begin);

}

//очистка очереди

void Clear_Deque(Deque* Begin_Deque){

Delete_Double_List(Begin_Deque->Begin);

}

Стек

Стек характерен тем, что получить доступ к его элементам можно лишь с одного конца, называемого вершиной стека; иначе говоря: стек – структура данных типа «список», функционирующая по принципу LIFO (last in — first out, «последним пришёл — первым вышел»).

Описание элементов стека аналогично описанию элементов линейного однонаправленного списка. Поэтому объявим стек через объявление линейного однонаправленного списка:

struct Stack {

Single_List *Top;//вершинастека

};

. . . . . . . . . .

Stack *Top_Stack;//указатель на вершину стека

Основные операции, производимые со стеком:

· создание стека;

· печать (просмотр) стека;

· добавление элемента в вершину стека;

· извлечение элемента из вершины стека;

· проверка пустоты стека;

· очистка стека.

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

//созданиестека

voidMake_Stack(int n, Stack* Top_Stack){

if (n > 0) {

inttmp;//вспомогательная переменная

cout<< "Введите значение ";

cin>>tmp; //вводим значение информационного поля

Push_Stack(tmp, Top_Stack);

Make_Stack(n-1,Top_Stack);

}

}

//печатьстека

voidPrint_Stack(Stack* Top_Stack){

Print_Single_List(Top_Stack->Top);

}

//добавлениеэлементаввершинустека

voidPush_Stack(intNewElem, Stack* Top_Stack){

Top_Stack->Top =Insert_Item_Single_List(Top_Stack->Top,1,NewElem);

}

//извлечениеэлементаизвершиныстека

intPop_Stack(Stack* Top_Stack){

intNewElem = NULL;

if (Top_Stack->Top != NULL) {

NewElem = Top_Stack->Top->Data;

Top_Stack->Top = Delete_Item_Single_List(Top_Stack->Top,0);

//удаляем вершину

}

returnNewElem;

}

//проверка пустоты стека

boolEmpty_Stack(Stack* Top_Stack){

returnEmpty_Single_List(Top_Stack->Top);

}

//очисткастека

voidClear_Stack(Stack* Top_Stack){

Delete_Single_List(Top_Stack->Top);

}

8.

Хеширование (иногда «хэширование», англ. hashing) — преобразование по определённому алгоритму входного массива данных произвольной длины в выходную битовую строку фиксированной длины. Такие преобразования также называются хеш-функциями или функциями свёртки, а их результаты называют хешем, хеш-кодом или сводкой сообщения (англ. message digest).

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

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

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

9.Рахрешение коллизий

Коллизия хеш-функции — это равенство значений хеш-функции на двух различных блоках данных.
Разрешение коллизий в хеш-таблице, задача, решаемая несколькими способами. Можно использовать списки, а можно открытую адресацию.

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

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

Стратегии поиска

Дата добавления: 2015-07-26; просмотров: 178; Нарушение авторских прав

Мы поможем в написании ваших работ!