Эмиссия газов от очистных сооружений канализации: В последние годы внимание мирового сообщества сосредоточено на экологических проблемах...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...
Топ:
Методика измерений сопротивления растеканию тока анодного заземления: Анодный заземлитель (анод) – проводник, погруженный в электролитическую среду (грунт, раствор электролита) и подключенный к положительному...
Характеристика АТП и сварочно-жестяницкого участка: Транспорт в настоящее время является одной из важнейших отраслей народного хозяйства...
Устройство и оснащение процедурного кабинета: Решающая роль в обеспечении правильного лечения пациентов отводится процедурной медсестре...
Интересное:
Аура как энергетическое поле: многослойную ауру человека можно представить себе подобным...
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Инженерная защита территорий, зданий и сооружений от опасных геологических процессов: Изучение оползневых явлений, оценка устойчивости склонов и проектирование противооползневых сооружений — актуальнейшие задачи, стоящие перед отечественными...
Дисциплины:
2017-07-01 | 233 |
5.00
из
|
Заказать работу |
|
|
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 для проверки, заполнен ли массив.
|
|
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!