WWW.BOOK.LIB-I.RU
БЕСПЛАТНАЯ  ИНТЕРНЕТ  БИБЛИОТЕКА - Электронные ресурсы
 

«1 Связные списки Ранее мы уже познакомились с массивами средством объединения нескольких однотипных переменных, доступных по номеру, который ...»

1 Связные списки

Ранее мы уже познакомились с массивами средством объединения нескольких однотипных переменных, доступных

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

однотипных переменных имеет ряд недостатков трудно вставить новый элемент в середину массива и даже просто

расширить массив, добавив один или несколько элементов в конец. Расширить обычный (не динамический) массив в

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

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

Чтобы использовать так устроенную структуру данных, нам нужно завести новый структурный тип данных (тип узла), содержащий два поля данные (те элементы последовательности, которые нам надо хранить) и указатель на этот же тип узла. К счастью, C++ позволяет в структурном типе данных иметь указатель на тот же тип, который мы определяем (это происходит потому, что размер памяти, отводимый под указатель, не зависит от размера памяти, отводимого под значение того типа, на который он указывает).

Если нам нужен список из элементов конкретного типа, например, целых чисел, тип узла может выглядеть так:

struct Node { int d; // элемент данных Node *n; // указатель на следующий узел Node(int dd, Node *nn = nullptr): d(dd), n(nn) {} };

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

templateclass T struct Node { T d;

NodeT *n; // указатель на следующий узел // из того же типа элементов Node(int dd, NodeT *nn = nullptr): d(dd), n(nn) {} };

Сам список теперь представляется в программе как указатель на первый его узел (список, вообще говоря, может быть и вовсе пустым, т. е. не содержащим ни одного узла; такой список представляется указателем nullptr).

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

Теоретически, наличия типа узла достаточно для написания программы, использующей связные списки. Для примера рассмотрим функцию, вычисляющую длину списка, на первый узел которого указывает ее параметр:

–  –  –

Задачи.

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





2. Написать функцию, возвращающую указатель на второй элемент списка.

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

4. Написать функцию, возвращающую указатель на элемент, находящийся в заданной позиции списка (добавляется один целый параметр номер необходимой позиции; 0 первый элемент списка, 1 второй элемент,..., длина списка1 последний элемент): а) для списка целых чисел; б) для списка из любого типа элементов.

5. Написать функцию, печатающую все элементы списка на экран.

6. Написать функцию, подсчитывающую элементы списка, удовлетворяющие определенному условию (добавляется один параметр указатель на функцию, принимающую элемент данных и возвращающую логическое значение;

считать надо те элементы, на которых эта функция возвращает true).

7. Написать функцию, возвращающую указатель на: а) первый; б) последний элемент списка с указанными данными (второй параметр функции).

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

–  –  –

Эта операция меняет указатель на первый элемент списка, поэтому его надо передавать по ссылке.

Используя конструктор структуры узла, текст этой функции можно сократить до одной строки:

void add_first(Node *&f, int d) { f = new Node(d, f);

} Задачи.

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

2. Написать функцию, вставляющую последний элемент в список для любого типа его элементов (для шаблонного варианта типа узлов списка).

3. Написать функцию, вставляющую элемент в заданную позицию списка (добавляется один целый параметр номер необходимой позиции; 0 вставка в начало списка, 1 после первого элемента,..., длина списка вставка в конец): а) для списка целых чисел; б) для списка из любого типа элементов.

4. Написать функцию без параметров, считывающую элементы списка с клавиатуры до тех пор, пока элементы не кончатся (конец потока) и возвращающую указатель на первый элемент созданного списка: а) при помощи операции вставки элемента в конец списка (порядка n2 действий, где n длина списка); б) более быстрый вариант порядка n действий (используя вспомогательный указатель на текущий узел).

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

6. Написать функцию, строящую копию списка (другой список (т. е. при его построении узлы заводятся при помощи new, а не заимствования из того списка, который копируется), содержащий ту же самую последовательность данных в узлах): а) рекурсивно с использованием конструктора узла; б) с разбором случаев (см. предыдущую задачу) в) используя указатели на указатели.

7. Построить копию списка, но в обратном порядке.

8. Поменять порядок узлов в списке на обратный (только путем изменения указателей на первый элемент и в узлах).

9*. Дан список, каждый узел которого в качестве данных имеет другой указатель на узел, причем известно, что он указывает на какой-то элемент того же списка. Требуется построить копию данного списка, в которой дополнительный указатель на узел ( данные ) указывает на узел копии с тем же номером в копии, с каким указатель в оригинале для данного узла указывал на элемент исходного списка (за линейное время, на константной памяти, кроме заведения копий узлов). Пример:

Следующий пример функция, удаляющая первый элемент списка:

–  –  –

Эта операция тоже меняет указатель на первый элемент списка, поэтому его и здесь надо передавать по ссылке.

Также, нам нужно перед выполнением этой операции проверить, что список не пуст.

Задачи.

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

2. Написать функцию, удаляющую последний элемент из списка для любого типа его элементов (для шаблонного варианта типа узлов списка).

3. Написать функцию, удаляющую элемент из заданной позиции списка (добавляется один целый параметр номер необходимой позиции; 0 удаление первого элемента списка, 1 второго элемента,..., длина списка1 удаление последнего элемента): а) для списка целых чисел; б) для списка из любого типа элементов.

4. Написать функцию, удаляющую все элементы списка.

5. Написать функцию, удаляющую элементы списка, удовлетворяющие определенному условию (добавляется один параметр указатель на функцию, принимающую элемент данных и возвращающую логическое значение; удалять из списка надо те элементы, на которых эта функция возвращает true): а) с разбором случаев; б) через указатель на указатель.

6. Найти все простые числа от 2 до 1000, используя решето Эратосфена: сначала строится список, содержащий все числа из указанного диапазона; затем берется первый элемент, и из списка выкидываются все узлы, содержащие числа, кратные ему; затем аналогичная процедура применяется для второго элемента списка, затем для третьего, и т. д. до предпоследнего.

7. Построить кольцевой список (в котором последний элемент указывает на первый), узлы которого хранят последовательные числа от 1 до 40. Затем, начиная с узла, содержащего 1, выкидывать каждый пятый узел по порядку, печатая числа, содержащиеся в удаляемых узлах (в конце, когда число узлов станет меньше пяти, при определении пятого узла некоторые узлы придется считать несколько раз), до тех пор, пока не останется один узел. Каков будет его номер?

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

9. Используя функцию предыдущей задачи, написать процедуру, сортирующую список за время порядка n ln n, где n длина исходного списка.

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

Задача.

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

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

Для исправления этой ситуации было изобретено понятие двусвязного списка. Узел такого списка отличается от узла обычного списка тем, что у него есть дополнительное поле, указывающее на предыдущий узел списка (у первого узла списка этот указатель, очевидно, равен nullptr).

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

struct DNode { int d; // элемент данных DNode *p, *n; // указатели на предыдущий и следующий узлы };

Кроме того, хотя для доступа к любому узлу такого списка достаточно иметь указатель на любой из его узлов (в том числе на первый узел, как у обычных списков), часто для двусвязного списка хранят как указатель на первый узел, так и указатель на последний.

С учетом этих замечаний класс двусвязного списка мог бы выглядеть так:

struct DList { DNode *h, *t; // указатели на первый и последний элементы DList(); // пустой список DList(const DList &); // конструктор копирования DList &operator = (const DList &); // операция присваивания ~DList(); // удалить все элементы void add_first(int d); // добавить в начало void del_first(); // удалить из начала void add_last(int d); // добавить в конец void del_last(); // удалить последний void add_i(int i, int d); // добавить в указанную позицию void del_i(int i); // удалить i-й void del_ptr(DNode *p); // удалить тот узел, на который указывает p void splice(DNode *p, DList &L); // вклеить элементы списка L // сразу после элемента, на который указывает p. После этого // список L остается пустым DNode *find(int d); // указатель на узел с данными d void swap(); // меняет местами первые два элемента.

void reverse(); // изменить порядок элементов // на обратный; можно менять только указатели };

В качестве примера разберем реализацию метода swap из класса DList, для написания которого применим технологию опорных указателей. Эта технология состоит в следующем: сначала нужно завести несколько переменныхуказателей на узлы, указывающих на все те узлы, указатели на которые нам понадобятся в процессе работы. В данном случае, для перемены мест первых двух узлов списка нам понадобятся указатели на первые три узла нашего списка (если в списке меньше двух узлов, то менять местами нечего, а если ровно два третий указатель будет nullptr).

Затем, пользуясь только что заведенными указателями, мы проставляем заново значения всех тех указателей в узлах, которые должны измениться в результате нашей операции.

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

–  –  –

1. Реализовать еще не реализованные методы класса DList (двусвязный список).




Похожие работы:

«ОБЪЯВЛЕНИЕ ОБ ЭЛЕКТРОННЫХ ЗАКУПКАХ СПОСОБОМ ЗАПРОС ЦЕНОВЫХ ПРЕДЛОЖЕНИЙ N:165411 1. в лице "Восточные МЭС" (наименование заказчика) объявляет о проведении электронных закупок способом запроса ценовых предложений Лебедка тягова...»

«15 мая 2014 г. город Сургут Вставьте картинку DIRECTED EVOLUTION: целенаправленное развитие информационных систем Применение метода Directed Evolution для анализа и прогнозирования развития инф...»

«Приложение № 4 к Условиям открытия и обслуживания расчетного счета Перечень тарифов и услуг, оказываемых клиентам подразделений Западно-Уральского банка ПАО Сбербанк на территории Удмуртской республики (действуют с 25.03.2016) Наименование услуги Стоимость услуги РАСЧЕТНО-КАССОВОЕ ОБСЛУЖИВАНИЕ...»

«ч ХІ-ІІІ годъ изданія. ХИГІІІ годъ изданія. Воскресенье 25 августа 1913 года. 1 ) В Х Д Т Е Е Е ІЬ Ь О !Ы О Я Ъ ЖН Д Л О. А Р : дресъ е д а к ц іи / \ \ 5 р. № 34 Ц н а г о д о в о м у и д ь н ію В. Д о ро н еж ъ уховная 2 р. 5 0 и. З а полгода С. е м и н а р ія / Ч ф ч У у Опредленія...»

«ИТЭ №3, 2015 ЕНЕРГЕТИКА ТЕПЛОТЕХНОЛОГІЇ ТА ЕНЕРГОЗБЕРЕЖЕННЯ Товажнянский Л. Л., Капустенко П. А., Перевертайленко А. Ю., Дуич Н., Краячич Г., Селяков А. М., Илюнин О. О. К вопросу энергосберегающей реконструкции систем теплоснабжения с паровыми котельными 3 Ульев Л. М., Маатук А., Васильев М. А. Пинч-интеграция теплового насоса в процесс разде...»

«Автоматизированная копия 586_374943 ВЫСШИЙ АРБИТРАЖНЫЙ СУД РОССИЙСКОЙ ФЕДЕРАЦИИ ПОСТАНОВЛЕНИЕ Президиума Высшего Арбитражного Суда Российской Федерации № 2820/12 Москва 17 июля 2012 г. Президиум Высшего Арб...»

«Автоматизированная информационная система мониторинга ДОМОВОЙ на базе программного обеспечения MICROSOFT DYNAMICS AX ИНСТРУКЦИЯ Web-интерфейс для обработки заявок АИСМ Домовой Составитель: Селезнева Т...»

«ISSAI 11 Международные стандарты высших органов аудита (ISSAI) выпускаются Международной организацией высших органов аудита (ИНТОСАИ). Для получения дополнительной информации см. веб-сайт www.issai.org Рекоменда...»








 
2017 www.book.lib-i.ru - «Бесплатная электронная библиотека - электронные ресурсы»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.