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 для проверки, заполнен ли массив.