InsertOrder Упорядоченный список
template <class T>
void InsertOrder(Node<T>* & head, T item)
{
// currPtr пробегает по списку
Node<T> *currPtr, *prevPtr, *newNode;
// prevPtr == 0 указывает на совпадение в начале списка
prevPtr = 0;
currPtr = head;
// цикл по списку и поиск точки вставки
while (currPtr != 0)
{
// точка вставки найдена, если item < текущего data
if (item < currPtr->data)
break;
prevPtr = currPtr;
currPtr = currPtr->NextNode();
}
// вставка
if (prevPtr == 0)
// если prevPtr == 0, вставлять в начало
InsertFront(head,item) ;
else
{
// вставить новый узел после предыдущего
newNode = GetNode(item);
prevPtr->InsertAfter (newNode) ;
}
}
// удаление свех узлов в связанном списке
template <class T>
void ClearList(Node<T> * &head)
{
Node<T> *currPtr, *nextPtr;
currPtr = head;
while(currPtr != 0)
{
// записать адрес следующего узла, удалить текущий узел
nextPtr = currPtr->NextNode();
delete currPtr;
currPtr = nextPtr;
}
// пометить как пустой
head = 0;
}
LinkSort
template <class T>
void LinkSort(T a[], int n)
{
Node<T> *ordlist = 0, *currPtr;
int i;
// вставлять элементы из массива в список с упорядочением
for (i=0;i < n;i++)
InsertOrder(ordlist, a[i]);
// сканировать список и копировать данные в массив
currPtr = ordlist;
i = 0;
while(currPtr != 0)
{
a[i++] = currPtr->data;
currPtr = currPtr->NextNode();
}
// удалить все узлы, созданные в упорядоченном списке
ClearList(ordlist);
}
Сортировка вставками
#include <iostream>
#include "node.h"
#include "nodelib.h"
using namespace std;
// сканировать массив и печатать его элементы
void PrintArray(int a[], int n)
{
for(int i=0;i < n;i++)
cout << a[i] << " ";
}
int main()
{
system("chcp 650
01");
// инициализировать массив с 10 целыми значениями
int A[10] = {82,65,74,95,60,28,5,3,33,55};
LinkSort(A,10); // сортировать массив
cout << " Отсортированный массив: ";
PrintArray(A,10); // печать массива
cout << endl;
}
Результат:
Отсортированный массив: 3 5 28 33 55 60 65 74 82 95
Двусвязный циклический список
В случаях, когда нам необходимо обращаться к узлам в любом направлении, полезным является двусвязный список (doubly linked list). Узел в двусвязном списке содержит два указателя для создания мощной и гибкой структуры обработки списков.
Для двусвязного списка операции вставки и удаления имеются в каждом направлении. Следующий рисунок иллюстрирует проблему вставки узла р справа от текущего. При этом необходимо установить четыре новых связи.
В двусвязном списке узел может удалить сам себя из списка, изменяя два указателя.
Листинг 12: Двусвязный список
#pragma once
template <class T>
class DNode
{
private:
// циклические связи влево и вправо
DNode<T> *left;
DNode<T> *right;
public:
// данные — открытые
T data;
// конструкторы
DNode(){}
DNode (const T& item);
// методы модификации списка
void InsertRight(DNode<T> *p);
void InsertLeft(DNode<T> *p);
DNode<T> *DeleteNode(void);
// получение адреса следующего (вправо и влево) узла
DNode<T> *NextNodeRight(void) const { return right; }
DNode<T> *NextNodeLeft(void) const { return left; }
};
template<class T>
DNode<T>::DNode(const T& item)
{
// установить узел для указания на самого себя и
// инициализировать данные
left = right = this;
data = item;
}
// вставить узел р справа от текущего
template <class T>
void DNode<T>::InsertRight(DNode<T> *p)
{
// связать р с его предшественником справа
p->right = right;
right->left = p;
// связать р с текущим узлом
p->left = this;
right = p;
}
// вставить узел р слева от текущего
template <class T>
void DNode<T>::InsertLeft(DNode<T> *p)
{
// связать р с его предшественником слева
p->left = left;
left->right = p;
// связать р с текущим узлом
p->right = this;
left = p;
}
// отсоединить текущий элемент от списка и возвратить его адрес
template <class T>
DNode<T> *DNode<T>::DeleteNode(void)
{
left->right = right;
right->left = left;
return this;
}
Проверка:
#include <iostream>
#include "dnode.h"
using namespace std;
int main()
{
DNode<int> node(3);
DNode<int> *p = new DNode<int>(1), *f;
node.InsertLeft(p);
p = new DNode<int>(2);
node.InsertLeft(p);
p = new DNode<int>(5);
node.InsertRight(p);
p = new DNode<int>(4);
node.InsertRight(p);
f = node.NextNodeLeft()->NextNodeLeft();
p = f;
do{
cout << p->data << endl;
p = p->NextNodeRight();
}while(p!=f);
}
Очередь
Очередь (queue) — это структура данных, которая сохраняет элементы в списке и обеспечивает доступ к данным только в двух концах списка (рис. 5.4). Элемент вставляется в конец списка и удаляется из начала списка. Приложения используют очередь для хранения элементов в порядке их поступления.
Элементы удаляются из очереди в том же порядке, в котором они сохраняются и, следовательно, очередь обеспечивает FIFO (first-in/first-out) или FCFS- упорядочение (first-come/first-served). Обслуживание клиентов в очереди и буферизация задач принтера в системе входных и выходных потоков принтера — это классические примеры очередей.
Очередь включает список и определенные ссылки на начальную и конечную позиции. Эти позиции используются для вставки и удаления элементов очереди. Подобно стеку, очередь сохраняет элементы параметризованного типа DataType. Подобно стеку, абстрактная очередь не ограничивает количество элементов ввода. Однако, если для реализации списка используется массив, может возникнуть условие полной очереди.
ADT формат
ADT Queue
Данные
Список элементов
front: позиция первого элемента в очереди
rear: позиция последнего элемента в очереди
count: число элементов в очереди в любое данное время
Операции
Конструктор
Начальные значения: Нет
Процесс: Инициализация начала и конца очереди.
QLength
Вход: Нет
Предусловия: Нет
Процесс: Определение количества элементов в очереди
Выход: Возвращать количество элементов в очереди.
Постусловия: Нет
QEmpty
Вход: Нет
Предусловия: Нет
Процесс: Проверка: пуста ли очередь.
Выход: Возвращать 1 (True), если очередь пуста и 0 (False)
иначе. Заметьте, что это условие эквивалентно
проверке, равна ли QLength 0.
Постусловия: Нет
QDelete
Вход: Нет
Предусловия: Очередь не пуста.
Процесс: Удаление элемента из начала очереди.
Выход: Взвращать элемент, удаляемый из очереди.
Постусловия: Элемент удаляется из очереди.
Qlnsert
Вход: Элемент для сохранения в очереди.
Предусловия: Нет
Процесс: Запись элемента в конец очереди.
Выход: Нет
Постусловия: Новый элемент добавляется в очередь
QFront
Вход: Нет
Предусловия: Очередь не пуста.
Процесс: Выборка значения элемента в начале очереди.
Выход: Возвращать значение элемента в начале очереди.
Постусловия: Нет
ClearQueue
Вход: Нет
Предусловия: Нет
Процесс: Удаление всех элементов из очереди и восстановление
начальных условий.
Выход: Нет
Постусловия: Очередь пуста.
Конец ADT Queue
Класс Queue
Класс Queue реализует ADT, используя массив для сохранения списка элементов и определяя переменные, которые поддерживают позиции front и rear. Так как для реализации списка используется массив, класс содержит метод Qfull для проверки, заполнен ли массив.