Динамические информационные структуры и абстракции данных

Оглавление Введение 3 Структуры хранения данных 3 Структуры данных и алгоритмы 3 Разновидности структур хранения данных 3 Одномерный массив 4 Двумерный массив 4 Списочные структуры (списки) 4 Древовидные структуры 9 Графовая структура 11 Уровни представления программы 12 Абстрактные типы данных (ADT) 13 Структура данных и абстракция данных 14 Список 14 Стек 16 Очередь 17 Очередь приоритетов 18 Упорядоченный список 19 Пример реализации абстрактного типа данных (ADT) «список» 20 Контрольные вопросы 34 Источники дополнительных сведений 34 ​ Введение Изучаемые вопросы: Динамические информационные структуры. Список, упорядоченный список, стек, очередь, очередь приоритетов, дерево, граф. Абстракции данных. Спецификация. Множество реализаций. При решении некоторых задач возникает необходимость создания, удаления и модификации структур данных в процессе выполнения приложений. Размер таких структур данных невозможно определить на этапе разработки приложения. Поэтому, как правило, невозможно определить требуемый размер памяти для их хранения. Такого рода структуры данных называют динамическими информационными структурами. Память под них распределяется динамически в процессе работы приложения. К таким структурам относят списковые структуры, деревья и графовые структуры хранения данных. Абстракция данных или абстрактный тип данных – это средство расширения языка программирования новым типом данных для решения задач в заданной предметной области. Абстракция данных характеризуется объектами типа и определёнными на них операциями. Поведение абстракции данных полностью задаётся её спецификацией. ​ Структуры хранения данных ​ Структуры данных и алгоритмы Программу, предназначенную для достижения некоторой цели, можно рассматривать как результат объединения структуры данных и алгоритма. Для достижения одной и той же цели может существовать ряд различных программ. Как правило, могут существовать различные алгоритмы решения одной и той же задачи. Это зависит от постановки задачи и метода её решения. Алгоритмы решения задачи могут различаться в зависимости от способа представления и упорядочения данных. Если задана упорядоченность данных, то алгоритм упрощается и значительно возрастает скорость обработки данных. Достоинства структуры данных оцениваются по простоте их восприятия, а также по эффективности применения алгоритма к такой структуре данных. ​ Разновидности структур хранения данных Необходимо по возможности более точно с учётом организации памяти реализовать структуру данных, обеспечивающую эффективность их обработки большим числом алгоритмов. С этой точки зрения рассмотрим типичные методы хранения данных в ЭВМ. ​ Одномерный массив Этот способ является обычным при вводе данных в последовательность адресов памяти запоминающего устройства. В случае, когда данные представляют собой полностью упорядоченное множество, хранение данных лучше осуществлять в соответствии с их порядком. ​ Двумерный массив Этот способ хранения данных широко применяется на практике. Если длина (m) строки или столбца известна, а индексация начинается от 0, то для выборки элемента необходимо определить место его расположения в памяти по формуле A[i,j] = A + (i*m + j)*size. Здесь size – размер компонента массива, выраженный в числе байт занимаемой памяти; A – адрес массива, который совпадает с адресом первого компонента массива A[0,0]. ​ Списочные структуры (списки) Предположим, что данные, записываются не в последовательные ячейки памяти, как в случае одномерных и двумерных массивов, а в произвольные места памяти. Для того, чтобы задать связь между данными, применяются указатели. Наименьшим структурным элементом в этом случае является узел. Узел – это структурная переменная типа запись или класс, содержащая два поля. Списочная структура (или линейная структура), как показано на рисунке представляет собой структуру данных в виде нескольких линейно связанных узлов. Первый узел содержит элемент данных и адрес (указатель) на последующий узел. Добавление и исключение некоторых данных можно выполнять с помощью простой операции изменения указателя. Рисунок. Списочная структура – односвязный список. В односвязном списке, каждый узел кроме последнего знает адрес одного следующего за ним узла в списке. Пример реализации на C# односвязного списка целых чисел. //Узел односвязного списка. class OL_List { //Поле для хранения данных. public int key; //Поле для хранения указателя на следующий элемент списка. public OL_List next; //Конструктор. public OL_List(int key, OL_List next = null) { this.key = key; this.next = next; } } class Program { static void Main(string[] args) { //Список представлен переменной lst. OL_List lst; //В список добавляем узел со значением 1. lst = new OL_List(1); //В список добавляем узел со значением 2. lst.next = new OL_List(2); //В список добавляем узел со значением 3. lst.next.next = new OL_List(3); } } Рисунок. Двусвязный список. Можно привести различные структуры сходные со списочной структурой. Например, двусвязный список. Он имеет удобную организацию с точки зрения свободного прохождения из некоторого узла в начало или конец списка. Однако в данном случае имеется недостаток, связанный с необходимостью выделения места для хранения обратного указателя. В двусвязном списке, каждый узел кроме первого и последнего знает адрес одного следующего за ним в списке узла и одного узла, который предшествует ему в списке. У первого узла нет предшествующего, у последнего – последующего узла. Пример реализации на C# двусвязного списка целых чисел. //Узел двусвязного списка. class DL_List { //Поле для хранения данных. public int key; //Поле для хранения указателя на предующий узел списка. public DL_List pred; //Поле для хранения указателя на следующий узел списка. public DL_List next; //Конструктор. public DL_List(int key, DL_List pred = null, DL_List next = null) { this.key = key; this.next = next; this.pred = pred; } } class Program { static void Main(string[] args) { //Список представлен переменной lst. DL_List lst; //В список добавляем узел со значением 1. lst = new DL_List(1); //В список добавляем узел со значением 2. lst.next = new DL_List(2,lst); //В список добавляем узел со значением 3. lst.next.next = new DL_List(3,lst.next); } } Рисунок. Кольцевой список. В кольцевом односвязном списке, каждый узел кроме последнего знает адрес одного следующего за ним в списке узла. Последний узел хранит указатель на первый узел списка. Рисунок. Список с дескриптором списка. Список с дескриптором обеспечивает через дескриптор списка доступ, как к первому, так и к последнему элементу односвязного списка. Кроме того, в дескрипторе постоянно хранится текущий размер списка. Однако в некоторых операциях (приводящих в результате своей работы к изменению размера списка), определённых на таком списке необходимо предусмотреть постоянное обновление полей дескриптора списка. Помимо указанной информации дескриптор списка может хранить любую информацию о состоянии списка, полезную для реализации операций над списком. //Односвязный список с дескриптором. class Dsc_List { //Поле для хранения размера списка. public int size; //Поле для хранения указателя на первый узел списка. public Node first; //Поле для хранения указателя на последний узел списка. public Node last; //Конструктор. public Dsc_List() { this.size = 0; this.first = null; this.last = null; } } //Узел односвязного списка. class Node { //Поле для хранения данных. public int key; //Поле для хранения указателя на следующий элемент списка. public Node next; //Конструктор. public Node(int key, Node next = null) { this.key = key; this.next = next; } } class Program { static void Main(string[] args) { //Список представлен переменной lst. Dsc_List lst = new Dsc_List(); //В список добавляем узел со значением 1. lst.first = new Node(1); lst.size = 1; //В список добавляем узел со значением 2. lst.first.next = new Node(2, lst.first); //lst.first.next = new Node(2, lst.first); lst.size = 2; //В список добавляем узел со значением 3. lst.first.next.next = new Node(3, lst.first.next); lst.size = 3; Console.WriteLine("O'key 1"); } } ​ Древовидные структуры Древовидная структура используется во многих структурах данных. Существуют деревья с двумя ветвями (бинарное дерево) и деревья с большим количеством ветвей. В основном применяют деревья с большим количеством ветвей, но для однородности структуры узлов памяти деревья с большим количеством ветвей представляются форме бинарных деревьев. Пример такой структуры представлен на рисунке. Дерево. Бинарное дерево Структура указателей Структура узла Пример реализации бинарного дерева на C# приведён ниже. //Узел бинарного дерева. class BT_Node { //Поле для хранения данных. public int key; //Указатель на левое поддерево. public BT_Node left; //Указатель на правое поддерево. public BT_Node right; //Конструктор. public BT_Node(int key = 0, BT_Node left = null, BT_Node right = null) { this.key = key; this.left = left; this.right = right; } } class Program { static void Main(string[] args) { //Переменная, представляющая корень дерева. BT_Node t; //Созддаём корень дерева. t = new BT_Node(5); //Созддаём корень правого поддерева. t.right = new BT_Node(4); //Созддаём корень левого поддерева. t.left = new BT_Node(6); } } Рассмотренный выше двумерный массив при необходимости можно представить в виде древовидной структуры, показанной на рисунке. В языке программирования Lisp, как программы, так и данные представляются в виде древовидных структур, и в этом смысле между ними нет существенных различий. Древовидную структуру имеют схема иерархии логических модулей, дерево папок на диске компьютера. ​ Графовая структура Графовая структура представляет собой структуру наиболее общего вида. Рассмотренные выше списочные и древовидные структуры можно рассматривать как частный случай графовой структуры. Графовая структура, представленная на рисунке ниже, содержит циклы, поэтому при обработке такой структуры данных, если не быть в достаточной степени внимательным, существует опасность попасть в бесконечный цикл. Рис. 1. Графовая структура. Рис. 2. Граф сети авиалиний (1 Мм = 1000 км). Рис. 3. Структура представления узлов и дуг графа. Рис. 4. Пример представления графа сети авиалиний. Существуют различные способы представления графовой структуры в памяти ЭВМ. Например, в узлах и дугах графа, показанного на рисунке 1, указаны конкретные значения данных. Один из способов представления узлов и дуг этого графа в памяти ЭВМ показан на рис. 2. На рис. 4 приведен пример представления графа сети авиалиний, изображенного на рис. 2. Рассмотренные выше структуры данных могут быть представлены в ЭВМ различными способами. Однако усложнение структур представления данных в памяти вызывает усложнение программ обработки данных. Особенно усложняются программы, реализующие операции дополнения и изменения структуры данных. В этом случае целесообразнее использовать по возможности более простую структуру представления даже в ущерб объему памяти. Именно такой принцип используют реляционные базы данных. ​ Уровни представления программы Любую программу можно рассматривать в трёх аспекта или с трёх точек зрения: 1. Логический (уровень заказчика, пользователя). 2. Языка программирования (уровень программиста). 3. Физический (системного программиста – память, процессор). ​ Абстрактные типы данных (ADT) Абстракция данных является мощным инструментом современного программирования. Этот концептуальный подход позволяет объединить тип данных с множеством операций, которые допустимо выполнять над данными этого типа. Более того, эта философия позволяет использовать такой тип данных, не задумываясь о деталях внутренней организации данных, которые могут быть продиктованы средствами используемого компьютерного оборудования. Абстракция данных позволяет рассматривать необходимые объекты данных и операции, которые должны выполняться над такими объектами, без необходимости вникать в несущественные детали их реализации. Кроме того, абстракция данных является важнейшей составной частью объектно-ориентированного программирования. Абстракция данных - средство описания процессов обработки данных, в котором существенными являются объекты и определённые на них операции. Абстрактный тип данных = «объекты, операции» Абстракции данных обеспечивают возможность расширения языка программирования новыми типами данных. Новые типы данных должны включать в себя абстракции, как через параметризацию, так и через спецификацию. Абстракция через параметризацию может быть осуществлена точно так же, как и для функций, - использованием параметров там, где это имеет смысл. Абстракция через спецификацию достигается за счет того, что мы представляем операции как часть типа. Абстракции данных - наиболее важный метод в проектировании программ они позволяют отложить окончательный выбор структур данных до момента, когда эти структуры станут нам достаточно ясны. После того, как абстракция данных выявлена в процессе анализа предметной области, она должна быть специфицирована, то есть описана. Специфицировать абстракцию данных – это значит описать её свойства и поведение в существенных для пользователя признаках. На основе спецификации программист реализует абстракцию данных так, чтобы её свойства и поведение удовлетворяли спецификации. На основе одной спецификации можно построить множество различных реализаций. Они могут отличаться в несущественных для пользователя признаках, но должны удовлетворять спецификации. Спецификации бывают формальнее и неформальные. При написании формальных спецификаций используют язык исчисления предикатов. Они трудны для написания и понимания. Мы будем пользоваться неформальными спецификациями. ​ Структура данных и абстракция данных Структура данных определяет особенности распределения памяти под объекты данных. В абстракции данных мы отвлекаемся от этих особенностей. Нас интересуют особенности объектов данных с точки зрения пользователя данными и набор определённых на них операций. Так массивы и записи это структуры данных. В языке программирования над ними не определены операции. А вот предопределённые в языке простые типы (например, int) – это скорее абстракции данных. Объекты этих типов и операции на них определены, а вот организация памяти под объекты и особенности реализации операций для программиста, как правило, неважны. ​ Список Список - это последовательность элементов, принадлежащих одному множеству элементов, называемому алфавитом. Вид алфавита определяется особенностями решаемой задачи. Он может состоять из символов, строк, целых чисел, структур данных или подсписков переменной длины. Имя списка будем обозначать строчной латинской буквой, имена элементов списка - прописными латинскими буквами. Например: t = (A B K J U). Здесь t - список, содержащий элементы A, B, K, J, U. Список - это структура непоименованных данных. Он имеет имя, однако отдельные элементы списка имен не имеют. Понятие «список» имеет такое же большое значение в вычислениях, как понятие «множество» в математике. Любой вычислительный процесс может быть представлен и описан с помощью операций над списками. Пустым списком называется последовательность, не содержащая элементов обозначается Ø или (). Последовательность элементов, представляющую список, можно рассматривать как упорядоченную слева направо, так и упорядоченную справа налево. Элемент A в некотором списке отличается от одноэлементного списка (A), содержащего такой же элемент. Операция «+» позволяет добавить элемент A к списку t справа A + t (ДобавитьСправа(t,A)) или слева t + A (ДобавитьСлева(t,A)). Операция Элементов(t) возвращает число элементов в списке t. Первый элемент A некоторого непустого списка t записывается как A = Голова(t), t <> Ø, если последовательность рассматривается как упорядоченная слева направо, и как A = ГоловаСправа( t ), t <> Ø, если последовательность рассматривается как упорядоченная справа налево. Непустой список t с удаленным первым элементом записывается как Хвост(t), если последовательность рассматривается как упорядоченная слева направо, и как ХвостСправа(t), если последовательность рассматривается как упорядоченная справа налево. Операция Опустошить(t) опустошает список t. Операция t||f (Соединить(t,f)) присоединяет содержимое списка f к списку t справа. ​ Стек Стек - это абстрактный тип данных, который обеспечивает доступ к данным по принципу LIFO (поступивший последним обслуживается первым). Элементы данных, помещаемые в стек, принадлежат заданному пользователем алфавиту. При выборке Извлечь(s) определяет и удаляет из стека s последний поступивший в него элемент, а при записи Положить(s,A) добавляет элемент A на вершину стека s. Операция Просмотреть(s) обеспечивает доступ для чтения к значению элемента, находящегося на вершине стека s. Операция Элементов(s) возвращает число элементов в стеке. Операция Пуст(s) возвращает значение True, если стек s пуст, False в противном случае. Операция Опустошить(s) опустошает стек s. Операции Извлечь и Просмотреть в случае пустого стека не могут быть выполнены. Как запись, так и считывание элементов данных в стек осуществляется через его вершину. При реализации стека с помощью списка роль вершины стека выполняет элемент, находящийся в голове списка. Ниже приведён пример реализации объектов данных «стек» в памяти с помощью односвязного списка. Здесь push - операция положить в стек, pop - извлечь из стека. ​ Очередь Очередь - это абстрактный тип данных, который обеспечивает доступ к данным по принципу FIFO (поступивший первым обслуживается первым). Элементы данных, помещаемые в очередь, принадлежат заданному пользователем алфавиту. При выборке Извлечь(q) определяет и удаляет из очереди q элемент, поступивший в неё раньше всех других её элементов, а при записи Положить(q,A) добавляет элемент A в очередь q. Операция Просмотреть(q) обеспечивает доступ для чтения к значению элемента, поступившего в очередь q раньше всех других её элементов. Операция Элементов(q) возвращает число элементов в очереди q. Пуста(q) возвращает значение True, если очередь q пуста, False в противном случае. Операция Опустошить(q) опустошает очередь q. Операции Извлечь и Просмотреть в случае пустой очереди не могут быть выполнены. При реализации очереди с помощью списка в качестве места вставки элемента данных в очередь можно выбрать голову списка, тогда в качестве места удаления элемента данных из списка необходимо выбрать последний элемент (хвост) списка. Но можно сделать и, наоборот: при постановке в очередь помещать элемент в конец списка, при извлечении из очереди извлекать элемент из головы списка. Ниже приведён пример реализации объектов данных «очередь» в памяти с помощью односвязного списка. ​ Очередь приоритетов Очередь приоритетов - это абстрактный тип данных, который обеспечивает доступ к данным по принципу: первым обслуживается элемент очереди с самым высоким приоритетом среди элементов очереди. В качестве значения приоритета может выступать любой атрибут элемента. В случае значений простого типа в качестве значения приоритета выступает значение элемента помещаемого в очередь. Элементы данных, помещаемые в очередь, принадлежат заданному пользователем алфавиту. При выборке Извлечь(q) определяет и удаляет из очереди q элемент, имеющий самый высокий приоритет среди всех других её элементов, а при записи Положить(q,A) добавляет элемент A в очередь q. Операция Просмотреть(q) обеспечивает доступ для чтения к значению элемента, имеющего самый высокий приоритет среди всех других элементов очереди q. Пуста(q) возвращает значение True, если очередь q пуста, False в противном случае. Операция Элементов(q) возвращает число элементов в очереди q. Операция Опустошить(q) опустошает очередь q. Операции Извлечь и Просмотреть в случае пустой очереди не могут быть выполнены. При реализации очереди с помощью списка в качестве места вставки элемента данных в очередь можно выбрать голову списка. В качестве значения приоритета элемента может быть взято само значение элемента. ​ Упорядоченный список Упорядоченный список - это последовательность элементов, упорядоченных в соответствии с заданным порядком, принадлежащих одному множеству элементов, называемому алфавитом. Вид алфавита определяется особенностями решаемой задачи. Он может состоять из символов, строк, целых чисел, структур данных или подсписков переменной длины. В целях упорядочения на элементах списка должна быть определена одна из операций отношения: >,>=,<,<=. Элемент в упорядоченный список добавляется с учётом заданного отношения порядка. Например: (1 2 5 7 9) – это упорядоченный по возрастанию список. Если к нему добавить элемент 6, то список примет следующий вид: (1 2 5 6 7 9). Например: (9 7 5 1) – это упорядоченный по убыванию список. Если к нему добавить элемент 6, то список примет следующий вид: (9 7 6 5 1). ​ Пример реализации абстрактного типа данных (ADT) «список» ​ Задание 1. Реализовать абстрактный тип данных Список целых чисел, в соответствии с приведенной ниже спецификацией. 2. Протестировать каждую операцию, определенную на типе данных одним из методов тестирования. ​ Спецификация абстрактного типа данных «список целых чисел». Для описания ADT на логическом уровне используется формат, который включает заголовок с именем ADT, описание объекта типа данных и список операций. Для каждой операции определяются входные (Вход) значения, предоставляемые клиентом, (Предусловия), требования к исходным данным, в случае истинности которых операция может быть выполнена, и процесс обработки данных (Процесс), который выполняется операцией. После выполнения операции определяются выходные значения (Выход), которые возвращаются клиенту, и постусловия (Постусловия), указывающие на любые изменения данных. ADT List Данные Списки - это изменяемые неограниченные последовательности целых чисел. Они изменяются операциями: «Опустошить», «ДобавитьСлева», «ДобавитьСправа», «Голова», «ГоловаСправа», «Хвост», «ХвостСправа», «Соединить». Таблица 1. Описание операций для ADT List. Наименование Операции Описание СписокВСтроку Вход: L - список. Предусловия: Нет. Процесс: Формирует строку, содержащую строковое представление значений элементов списка L. Если список пуст – формируется пустая строка. Выход: Строка. Постусловия: Нет. Опустошить Вход: L - список. Предусловия: Нет. Процесс: Удаляет все элементы из списка L. Выход: Нет. Постусловия: Список L пуст. СписокПуст Вход: L - список. Предусловия: Нет. Процесс: Возвращает True, если список L пуст, False - в противном случае. Выход: Булевское значение. Постусловия: Нет. ДобавитьСправа Вход: L - список, E - элемент списка - целое число. Предусловия: Нет. Процесс: Добавляет элемент E к элементам списка L справа. Выход: Нет. Постусловия: Количество элементов списка L увеличивается на 1. ДобавитьСлева Вход: L - список, E - элемент списка - целое число. Предусловия: Нет. Процесс: Добавляет элемент E к элементам списка L слева. Выход: Нет. Постусловия: Количество элементов списка L увеличивается на 1. Голова Вход: L - список. Предусловия: Список L не пуст. Процесс: Удаляет из списка L крайний левый элемент E ( элемент, находящийся в голове списка). Выход: E - элемент списка - целое число. Постусловия: Количество элементов списка L уменьшается на 1. ГоловаСправа Вход: L - список. Предусловия: Список L не пуст. Процесс: Удаляет из списка L крайний правый элемент E (элемент, находящийся в голове списка, если рассматривать его справа налево). Выход: E - элемент списка - целое число. Постусловия: Количество элементов списка L уменьшается на 1. Хвост Вход: L - список. Предусловия: Нет. Процесс: Выделяет и возвращает список, являющийся хвостом списка L. Если список L пуст или в нём один элемент, возвращает пустой список. Выход: Список. Постусловия: В списке L остаётся голова (левый крайний элемент). ХвостСправа Вход: L - список. Предусловия: Нет. Процесс: Выделяет и возвращает список, являющийся хвостом списка L, если рассматривать его справа налево. Если список L пуст или в нём один элемент, возвращает пустой список. Выход: Список. Постусловия: В списке L остаётся голова (правый крайний элемент). Соединить Вход: L, N - списки. Предусловия: Нет. Процесс: Добавляет к элементам списка L элементы списка N справа. Выход: Нет. Постусловия: Список L содержит элементы списков L и N. Список N пуст. Элементов Вход: L - список. Предусловия: Нет. Процесс: Подсчитывает и возвращает количество элементов списка L. Выход: Целое число. Постусловия: Нет. end List ​ Реализация 1. На логическом уровне (уровень пользователя) список – это последовательность целых чисел. На уровне языка программирования список будет представлен двумя классами ListOL и Node. Класс ListOL реализует операции для работы со списком. Объекты класса Node обеспечивают хранения элементов списка в памяти и связывание их в список. на рисунке ниже показана реализации списка в памяти. На физическом уровне (оперативная память) - список целых чисел организуем, как динамическую информационную структуру односвязный список (Рисунок 1) с дескриптором. Для этой цели будем использовать объекты классов ListOL и Node. Рисунок 1. Односвязный список из трёх элементов с дескриптором. 2. На уровне языка программирования для описания элементов списка будем использовать следующие типы данных (Пример 1): Node, ListOL. • class Node { int key;//поле для хранения информации node next;//вспомогательное поле для хранения //указателя на следующий узел списка } • класс ListOLобеспечивает хранение дескриптора списка и выполнения операций на списке. Таким образом, список мы реализуем как динамическую информационную структуру – список узлов, в которой узлы и дескриптор списка представляют собой объекты классов, которые являются динамическими переменными и размещаются в куче. 4. Ниже приводится (Пример 1) консольного приложения на языке C#, в котором даны описания классов, реализующих операции над списком целых чисел и тестирование некоторых операций. Пример 1. Реализация односвязного списка целых чисел с дескриптором. using System; namespace List { class Node//---------------------Узел списка------------------------------ { public int key;//поле для хранения информации public Node next;//вспомогательное поле для хранения //указателя на следующий узел списка public Node(int key) { this.key = key; next = null; } } class ListOL// --------------------Список с дескриптором односвязный------------------------ { Node first;//указатель на первый элемент списка Node last;//указатель на последний элемент списка int size;//Число элементов списка public int Size { get { return size; } } // --Операции на списке----------------------------------------- // --------------------Формирует строку из элементов списка, начиная с головы списка public override String ToString() //Формирует строковое представление элементов списка { Node p = first; string result = ""; if (size == 0) return "list is empty"; result = "Size = " + size + "| Elements: "; while (p != null) { result += p.key + "; "; p = p.next; } return result; } //---------------------Конструктор без параметров. public ListOL() { first = null; last = null; size = 0; } // --------------------Список пуст------------------------------ public bool IsEmpty() { return size == 0 ? true : false; } // --------------------Добавить элемент к списку (слева)------------------------ public void AddLeft(int key) { Node p; if (size == 0) { first = new Node(key); last = first; size++; } else { p = new Node(key); p.next = first; first = p; size++; } } // --------------------Добавить элемент к списку (справа)------- public void AddRight(int key) { if (size == 0) { first = new Node(key); last = first; size++; } else { last.next = new Node(key); last = last.next; size++; } } // --------------------Взять голову списка (слева)-------------- public int Head() { int key; if (size != 0) { key = first.key; first = first.next; size--; if (size == 0) { last = null; first = null; } return key; } else { throw new Exception("Список пуст"); } } // --------------------Взять голову списка (справа)-------------- public int Head_() //Выделяет из списка L и удаляет узел, который является его головой (справа), //возвращает элемент списка, который находился в этом узле. { Node p, lst; //Указатели на предпоследний и последний узлы списка. if(size == 0) throw new Exception("Список пуст. Операция не определена."); if (Size == 1) { int key = last.key; last = null; first = null; size = 0; return key; } lst = PredLast(out p); last = p; last.next = null; size = size - 1; return lst.key;//Возвратили элемент списка, находящийся в голове. } // --------------------Опустошить список------------------------ public void EmptyList() { while (size != 0) Head(); } // --------------------Выделить хвост списка (слева)------------ public ListOL Tail() //Создает список, полученный выделением элементов хвоста списка L, //и возвращает указатель на него. В L остается голова исходного списка.} { ListOL r = new ListOL(); if (Size > 1) { r.first = first.next; r.last = last; r.size = size - 1; first.next = null; last = first; size = 1; } return r; } // --------------------Объединить два списка в один------------- public void Merge(ListOL T) { if (T.IsEmpty()||(T.IsEmpty() && this.IsEmpty())) return;//Добавляемый список - пуст или оба. if (this.IsEmpty() && !T.IsEmpty() ) { first = T.first; size = T.size; last = T.last; T.size = 0; T.first = null; T.last = null; return; } last.next = T.first; last = T.last; size = T.size + size; T.size = 0; T.first = null; T.last = null; } public Node PredLast(out Node p)//Работает для двух и более узлов в списке. { Node lst = null; if (size > 1) { p = first; lst = p.next; while (lst.next != null) { p = p.next; lst = lst.next; } return lst; } else throw new Exception("В списке менее двух узлов"); } // --------------------Выделить хвост списка (справа)----------- public ListOL Tail_() //Создает список, полученный выделением элементов хвоста списка L (справа) //и возвращает указатель на него. В L остается голова исходного списка. { Node p,lst; ListOL res = new ListOL(); if (size > 1 ) { lst = PredLast(out p); res.size = size - 1; res.first = first; res.last = p; res.last.next = null; last = lst; first = last; size = 1; } return res; } } } ​ Тестирование «Списка целых чисел». Ниже приведено консольное приложение для тестирования разработанной абстракции данных «список целых чисел». Абстрактный тип данных реализован под именем ListOL. using System; namespace List { class Program { static void Main(string[] args) { ListOL L = new ListOL(); Console.WriteLine(L.ToString()); //------Операция ДобавитьСлева () for (int i = 0; i < 5; i++) { L.AddLeft(i); } Console.WriteLine(L.ToString()); //------Операция ДобавитьСправа () for (int i = 5; i < 10; i++) { L.AddRight(i); } Console.WriteLine(L.ToString()); //------Операция Опустошить () L.EmptyList(); Console.WriteLine(L.ToString()); //------Операция ГоловаСлева () ListOL R = new ListOL(); for (int i = 5; i < 10; i++) { R.AddRight(i); } while (R.Size != 0) Console.WriteLine(R.Head()); } } } ​ Реализация операций на списке. Рассмотрим подробнее реализацию операции добавить элемент данных к списку справа. Текст программы, реализующей операцию приведён ниже. Реализацию операции начнём с анализа зависимости её выполнения от состояния списка. Под состоянием списка будем понимать число элементов в списке. С точки зрения этой операции в списке можно выделить два состояния: список пуст и список не пуст. Если список пуст, то операция выполняет следующие действия: 1. создаётся узел списка, в поле данных которого заносится элемент данных 5 полученный операцией через параметр. 2. Указатель на созданный узел заносится в поля first и last дескриптора списка, поскольку этот элемент в списке единственный и является одновременно и первым и последним. 3. Поле size дескриптора списка увеличивается на 1. Если список не пуст (в не зависимости от числа элементов в нём), то операция выполняет следующие действия: 1. создаётся узел списка, в поле данных которого заносится элемент данных 7 полученный операцией через параметр. 2. В поле next последнего узла заносится указатель на созданный узел. 3. Указатель на созданный узел заносится в поля last дескриптора списка. 4. Поле size дескриптора списка увеличивается на 1. //Добавляет элемент E к списку справа public void AddRight(int key) { if (size == 0) { first = new Node(key); last = first; size++; } else { last.next = new Node(key); last = last.next; size++; } } Рассмотрим подробнее реализацию операции взять голову списка, если рассматривать список справа налево (Head_). Текст программы, реализующей операцию приведён ниже. Реализацию операции начнём с анализа зависимости её выполнения от состояния списка. Под состоянием списка будем понимать число элементов в списке. С точки зрения этой операции в списке можно выделить три состояния: список пуст, в списке один элемент, в списке два и более элементов. Если список пуст, то операция не определена. Поэтому эта операция не применима к пустому списку. Если список не пуст, то необходимо выполнить следующие действия: 1. возвратить значение элемента данных последнего узла списка, 2. отыскать адрес предпоследнего узла, 3. удалить последний узел, 4. поле size дескриптора списка уменьшить на единицу (изменяем размер списка). 5. в поле last дескриптора занести найденный адрес предпоследнего узла, 6. если получившейся список пуст, то в поле first занести nil, в противном случае - в поле next вновь образовавшегося последнего узла занести значение nil. Иллюстрация к выполнению операции взять голову, если рассматривать список справа налево. В списке один элемент. Иллюстрация к выполнению операции взять голову, рассматривая список, справа налево. В списке три элемента. // --------------------Взять голову списка (справа)-------------- public int Head_() //Выделяет из списка L и удаляет узел, который является его головой (справа), //возвращает элемент списка, который находился в этом узле. { Node p, lst; //Указатели на предпоследний и последний узлы списка. if(size == 0) throw new Exception("Список пуст. Операция не определена."); if (Size == 1) { int key = last.key; last = null; first = null; size = 0; return key; } lst = PredLast(out p); last = p; last.next = null; size = size - 1; return lst.key;//Возвратили элемент списка, находящийся в голове. } //-------------------------------------------------------------- Таблица 2. Тестовый набор для тестирования списка целых чисел. Тестовый набор для тестирования операции ГоловаСправа Номер теста Исходные данные Ожидаемый результат Вход Состояние списка Возвращаемое значение Состояние списка 1 Нет () Не определено. () 2 Нет (1) 1 () 3 Нет (5 7 1) 1 (5 7) ​ Контрольные вопросы 1. Что такое абстрактный тип данных ADT? 2. Из каких разделов состоит спецификация ADT? 3. Что описывается в каждом из разделов ADT? 4. Какую дисциплину обслуживает стек? 5. Какую дисциплину обслуживает стек? 6. Какую дисциплину обслуживает очередь приоритетов? 7. В чём особенность добавления элемента в упорядоченный список? ​ Источники дополнительных сведений В печатном виде 1. Павловская Т.А. C#. Программирование на языке высокого уровня :Учебник для вузов.  - СПб. : Питер, 2014. - 432 с. : ил. - (Серия "Учебник для вузов"). 2. Рихтер Дж. CLR via C#. Программирование на платформе Microsoft.NET Framework 4.0 на языке C# . 3-е изд.:  - СПб.:Питер, 2012. - 928 с. : ил. В электронном виде 1. Руководство по программированию на C# [Электронный ресурс]  URL: https://docs.microsoft.com/ru-ru/dotnet/csharp/programming-guide/ (дата обращения 14.02.18) 2. METANIT.COM. Сайт о программировании [Электронный ресурс]  URL: http://metanit.com/sharp/tutorial/ (дата обращения 12.08.16)