Материал: 695_Poletajkin_A.N._Uchebno-metodicheskoe_posobie_Realizatsija_zhiznennogo_ch.1_

Предел распределения динамической памяти в системе виртуальной памяти может быть равен объему доступного пространства на диске. Как правило, пределы намного меньше, потому что доступная память компьютера распределяется среди множества пользователей.

Для динамического распределения памяти принципиальное значение имеет оператор new. В качестве операнда оператор new принимает динамически распределяемый объект и возвращает ссылку на вновь созданный объект данного типа. Например, выражение

Node nodeToAdd = new Node(10); // Число 10 — данные объекта Node

распределяет соответствующий объем памяти для сохранения Node и сохраняет ссылку на данный объект в nodeToAdd. Если память недоступна, тогда оператор new выдает исключение OutOfMemoryException.

6.2. Связанные списки

Связанный список (linked list) — это линейная коллекция (то есть последовательность) объектов самоотносимого класса, называемых узлами, соединенная ссылками; отсюда и термин: "связанный" список. Программа осуществляет доступ к связанному списку посредством ссылки на первый узел списка. Доступ к каждому последующему узлу выполняется посредством элемента ссылки, сохраненного в предыдущем узле. Условно говоря, значение ссылки в последнем узле списка установлено на null для отметки конца списка. Данные сохраняются в связанном списке динамически, т. е. каждый узел создается по мере необходимости. Узел может содержать данные любого типа, включая объекты других классов. Стеки и очереди — тоже линейные структуры данных, являющиеся ограниченными версиями связанных списков.

Списки данных могут сохраняться в массивах, однако связанные списки обеспечивают ряд преимуществ. Связанный список уместен, когда нельзя предсказать количество элементов данных для представления их в структуре. В отличие от связанного списка, размер традиционного массива в С# изменить нельзя, потому что он фиксируется в момент создания. Традиционные массивы могут быть полными, а связанные списки заполняются только при недостаточном объеме памяти для удовлетворения запросов на ее динамическое распределение.

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

Узлы связанных списков, как правило, не сохраняются в памяти смежно; они демонстрируют логическую смежность. На рис. 15 показан связанный список с несколькими узлами.

56

Рис. 15. Графическое представление односвязного списка

6.3. Программирование односвязного списка

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

Для создания модели такой структуры требуется добавить в проект модуль класса, в котором объявить пространство имен LinkedListLibrary.

Листинг 4. Пространство имен LinkedListLibrary и структура PData

using System; using System.IO;

namespace LinkedListLibrary

{

public struct PData

{

public long TabNom; public string Surname; public string Firstname; public string Lastname; public byte Age;

public string Pol; public string Adress;

}

} // Конец пространства имен LinkedListLibrary

Для манипулирования данными списка в LinkedListLibrary объявлена статическая структура PData, включающая в себя семь полей списка. В дальнейшем при проведении каких-либо манипуляций с данными списка потребуется ссылаться на тип данных PData.

Каждый узел в списке представляется объектом самоотносимого класса ListNode. (см. листинг 5)

57

Листинг 5. Класс ListNode для представления односвязного списка

// Класс, представляющий один узел списка class ListNode

{

private PData data; private ListNode next;

// Конструктор для создания узла со ссылкой на dataValue – последний // узел в списке

public ListNode(PData dataValue) : this(dataValue, null)

{}

//Конструктор для создания узла со ссылкой на dataValue и на

//следующий узел в списке

public ListNode(PData dataValue, ListNode nextNode)

{

data = dataValue; next = nextNode;

}

//свойство Next public ListNode Next

{

get

{

return next;

}

set

{

next = value;

}

}

//свойство Data public PData Data

{

get

{

return data;

}

set

{

data = value;

}

}

}// Конец класса ListNode

58

Класс ListNode состоит из двух переменных элементов — data и next. Элемент data представляет собой структуру PData. В элементе next сохраняется ссылка на следующий объект класса ListNode в связанном списке.

Организация списка

Для организации собственно списка и манипуляций с ним используется объект класса List (см. листинг В.1 в приложении В). В каждом объекте List инкапсулирован связанный список объектов ListNode. Класс List (см. листинг В.1) осуществляет доступ к переменным элемента ListNode посредством свойств Data и Next соответственно.

Класс List содержит элементы типа private — firstNode (ссылка на первый объект ListNode в классе List) и lastNode (ссылка на последний объект ListNode в классе List). Конструкторы класса инициализируют обе ссылки на null.

Методы insertAtFront, insertAtBack, RemoveFromFront, RemoveFromBack

являются основными методами класса List. В каждом из этих методов присутствует блок lock для обеспечения многопоточной безопасности объектов класса List при использовании в многопоточной программе. Если один поток модифицирует содержимое объекта класса List, тогда ни один другой поток не может одновременно модифицировать этот же объект. Метод isEmpty является предикатным методом, определяющим, пуст список или нет (т. е. ссылка на первый узел списка имеет значение null). Предикатные методы, как правило, проверяют условие, но не модифицируют объект, для которого они вызваны. Если список пуст, тогда метод isEmpty возвращает значение true; в противном случае возвращается значение false. Метод Print отображает содержимое списка. Метод Printf выводит содержимое списка в файл.

Рассмотрим подробно основные методы класса List.

Метод InsertAtFront размещает новый узел в начале списка. Данный метод состоит из трех шагов (показаны на рис. 16):

1.Вызов метода isEmpty для определения, пустой список или нет.

2.Если список пуст, задание элементов f irstNode и lastNode для обращения к новому объекту ListNode, инициализированному с insertltem.

Конструктор ListNode(data) вызывает конструктор ListNode(data, next)

для задания экземпляра переменной data для ссылки на объект, переданный в качестве первого аргумента, и для задания ссылке next значения null.

3.Если список не пустой, тогда новый узел "вплетается" в список заданием элемента firstNode для ссылки на новый объект класса ListNode, инициализированный с элементами insertltem и firstNode. При исполнении конструктора ListNode задается переменная экземпляра data для ссылки на объект PData, переданный в качестве первого аргумента, и выполняется вставка заданием ссылки next объекту ListNode, переданному в качестве второго аргумента.

На рисунке 16, а показан список и новый узел во время операции InsertAtFront до ввода нового узла в список. Пунктирные стрелки на

59

рисунке 16, б иллюстрируют шаг 3 операции InsertAtFront, превращающий узел, содержащий 12, в первый узел нового списка.

Рис. 16. Графическое представление операции InsertAtFront

Метод insertAtBack размещает новый узел в конец списка. Данный метод состоит из трех шагов (показаны на рисунке 17):

1.Вызов метода isEmpty для определения, пустой список или нет.

2.Если список пуст, задание элементов firstNode и lastNode для обращения к новому объекту ListNode, инициализированному insertItem. Конструктор ListNode вызывает ListNode с параметрами для задания экземпляра переменной data для ссылки на объект, переданный в качестве первого аргумента, и для задания ссылке next значения null.

3.Если список не пустой, тогда новый узел "вплетается" в список заданием элементов lastNode и lastNode.next для ссылки на новый объект ListNode, инициализированный с элементом insertItem. При исполнении конструктора ListNode задается переменная экземпляра data для ссылки на объект PData, переданный в качестве первого аргумента, и ссылке next задается значение null.

На рисунке 17, а представлен список и новый узел во время операции InsertAtBack до ввода нового узла в список. Пунктирные стрелки на рисунке 17, б иллюстрируют шаги метода InsertAtBack, обеспечивающего добавление узла в конец не пустого списка.

а) список и новый узел

60