Объектная модель односвязного списка

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

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

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 Sex;

public string Adress;

}

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

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

Каждый узел в списке приставляется объектом самоотносимого класса 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

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

Для организации собственно списка и манипуляций с ним используется объект класса List. В каждом объекте List инкапсулирован связанный список объектов ListNode. Класс List (см. листинг ниже) осуществляет доступ к переменным элемента 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 размещает новый узел в начале списка. Данный метод состоит из трех шагов (показаны на рис. 6):

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

2. Если список пуст, задание элементов f irstNode и lastNode для обращения к новому объекту ListNode, инициализированному с insertltem. Конструктор ListNode(data) вызывает в строках 23—27 конструктор ListNode(data, next) для задания экземпляра переменной data для ссылки на объект, переданный в качестве первого аргумента, и для задания ссылке next значения null.

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

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

а). список и новый узел б). вставка нового узла в начало списка

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

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

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

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

б). вставка нового узла в конецсписка

а). список и новый узел     Рисунок 7. Графическое представление операции InsertAtBack

Метод RemoveFromFront удаляет первый узел из списка и возвращает ссылку на удаленные данные. Метод выдает исключение EmptyListException, если программист пытается удалить узел из пустого списка. В противном случае метод возвращает ссылку на удаленные данные. Данный метод состоит из четырех шагов (показаны на рисунке 1.5):

1. Присвоение firstNode.Data (удаляемые из списка данные) ссылке removeItem.
2. Если объекты, на которые ссылаются элементы firstNode и lastNode, являются одним объектом, тогда список имеет только один элемент перед попыткой удаления. В этом случае метод задает значение null элементам firstNode и lastNode для вывода из потока (удаления) узла из списка (список остается пустым).
3. При наличии в списке более одного узла до операции удаления метод оставляет ссылку lastNode как есть и просто присваивает элемент firstNode.Next ссылке firstNode. Таким образом, firstNode делает ссылку на узел, который был вторым до вызова метода RemoveFromFront.
4. Возвращение ссылки removeItem.

На рисунке 8, а показан список до операции удаления, а на рисунке 8, б— фактические манипуляции ссылкой.

а). список до удаления первого узла

б). изменение ссылки

Рисунок 8. Графическое представление операции RemoveFromFront.

Метод RemoveFromBack удаляет последний узел списка и возвращает ссылку на удаленные данные. Данный метод выбрасывает исключение EmptyListException, если программа делает попытку удаления узла из пустого списка. Метод состоит из нескольких шагов (рисунок 9):

1. Присвоить lastNode.Data (удаляемые из списка данные) ссылку removeItem.
2. Если объекты, на которые ссылаются firstNode и lastNode, являются одним объектом, тогда список имеет только один элемент перед попыткой удаления. В этом случае метод задает элементам firstNode и lastNode значение null для удаления узла из списка (список остается пустым).
3. Если перед операцией удаления список содержит более одного узла, создать ссылку current класса ListNode и присвоить ей элемент firstNode.
4. "Проход списка" ссылкой current до ссылки на предпоследний узел списка: цикл while присваивает current.Next ссылке current, пока current.Next не равно lastNode.
5. После определения местоположения предпоследнего узла присвоить current элементу lastNode для удаления из списка последнего узла.
6. Задать значение null свойству current.Next в новом последнем узле списка для обеспечения надлежащего завершения списка.
7. Возвратить ссылку removeItem.

На рисунке 9, а представлен список до операции удаления, на рисунке 9, б — фактические манипуляции ссылкой.

а). список до удаления последнего элемента

б). изменение ссылки

Рисунок 9. Графическое представление операции RemoveFromBack

Работа с указанными записями.

Выбор записи в списке осуществляется при помощи экранного меню. Как это реализовать, рассмотрим в разделе Организация пользовательского интерфейса, который посвящен программированию изменения указанной записи списка.

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

Метод RemoveFrom(int n)

Метод RemoveFrom удаляет указанную запись из списка. Данный метод также выбрасывает исключение EmptyListException, если программа делает попытку удаления узла из пустого списка.

1. Присвоить RemuveItem данные первой записи.
2. Если первый узел является последним, то очистить список и выйти.
3. Если «выбран» первый элемент, то следующий элемент сделать первым, то есть удалить первый элемент.
4. Во всех остальных случаях перейти к элементу, предшествующему «выбранному».
5. Сохранить данные следующего за текущим («выбранного») элемента.
6. Если «выбранный» элемент является последним, то последним узлом сделать текущий и «заглушить» список (удалить последний элемент).
7. Если «выбранный» элемент не последний, то ссылку next предыдущего элемента установить на элемент, следующий за «выбранным».
8. Возвратить удаленные данные.

Метод EditRow(PData newItem, int posItem)

Метод RemoveFrom заменяет данные на статическую запись PData в указанной записи списка. Здесь метод выполняет поиск указанной записи списка, сохраняет ее данные, задает их как аргумент newItem и возвращает сохраненную запись.

Виртуальный вывод на консоль. Метод Print(string s, bool pak)

Метод Print сначала определяет степень заполнения списка. Если список пуст, тогда метод Print отображает строку, содержащую слово "Пустой" и название списка (name), после чего возвращает 0 и передает управление в вызывающий метод. В противном случае метод Print выдает данные в списке.

Вывод. Метод распечатывает строку s и название name. Затем создается ссылка current класса ListNode, которая инициализируется элементом firstNode. Пока ссылка current не равна null, в списке имеется несколько элементов. Следовательно, метод распечатывает элемент current.Data, после чего присваивает current.Next ссылке current для перехода к следующему узлу списка. После выполнения цикла, если pak истинно, то программа приостанавливается до нажатия любой клавиши. Метод возвращает число узлов в списке.

Виртуальный вывод в файл. Метод Printf(string s)

Метод Printf также проверяет список на пустоту. Если список пуст, тогда метод отображает строку, что "Список с именем (name) пуст" и название списка, после чего возвращает false и передает управление в вызывающий метод. В противном случае метод Printf выводит данные в файл data(s).txt, где s – аргумент метода, представляющий собой следующий номер по порядку файлов формата «data*.txt» в исследуемой директории «D:\».

Для вывода в данный файл создается ссылка на пишущий поток. При помощи стандартного его метода WriteLine производится вывод названия списка и его элементов, подобно выводу в методе Print.

После цикла файл закрывается и возвращается true, означая успех произведенной операции вывода.

Некоторые специализированные типы исключений-наследников класс Exception, которые могут быть использованы при работе с файлами, представлены в разделе Обработка исключений при работе с файлами лабораторной работы №6.

Обратите внимание, что если ссылка в последнем узле списка не имеет значения null, тогда рассмотренные алгоритмы будут предпринимать ошибочную попытку вывода после окончания списка. Алгоритм вывода одинаков для связанных списков, стеков и очередей.

Пространство имен LinkedListLibrary и класс List для представления односвязного списка:

using System;

using System.IO;

namespace LinkedListLibrary

{

// Определение класса List

public class List

{

private ListNode firstNode;

private ListNode lastNode;

private string name; // Имя списка

// Построение пустого списка с заданным именем

public List(string ListName)

{

name = ListName;

firstNode = lastNode = null;

}

// Конструктор без параметров

public List() : this("list") { }

// Вставка узла в начало списка с проверкой списка на пустоту

public void InsertAtFront(PData insertItem)

{

lock (this)

{

if (IsEmpty())

firstNode = lastNode = new ListNode(insertItem);

else

firstNode = new ListNode(insertItem, firstNode);

}

}

// Вставка узла в конец списка с проверкой списка на пустоту

public void InsertAtBack(PData insertItem)

{

lock (this)

{

if (IsEmpty())

firstNode = lastNode = new ListNode(insertItem);

else

lastNode = lastNode.Next = new ListNode(insertItem);

}

}

// Удаление первого узла из списка

public PData RemuveFromFront()

{

lock (this)

{

if (IsEmpty())

throw new EmptyListException(name);

PData RemuveItem = firstNode.Data;

if (firstNode == lastNode)

firstNode = lastNode = null;

else

firstNode = firstNode.Next;

return RemuveItem;

}

}

// Удаление последнего узла из списка

public PData RemuveFromBack()

{

lock (this)

{

if (IsEmpty())

throw new EmptyListException(name);

PData RemuveItem = lastNode.Data;

if (firstNode == lastNode)

firstNode = lastNode = null;

else

{

ListNode current = firstNode;

while (current.Next != lastNode)

current = current.Next;

lastNode = current;

current.Next = null;

}

return RemuveItem;

}

}

// Удаление указанного узла из списка

public PData RemuveFrom(int n)

{

lock (this)

{

if (IsEmpty())

throw new EmptyListException(name);

PData RemuveItem = firstNode.Data;

if (firstNode == lastNode)

{

firstNode = lastNode = null;

return RemuveItem;

}

if (n == 1)

{

firstNode = firstNode.Next;

}

else

{

ListNode current = firstNode;

for (int i = 1; i < n - 1; i++)

{

if (current.Next == lastNode) break;

current = current.Next;

}

RemuveItem = current.Next.Data;

if (current.Next == lastNode)

{

lastNode = current;

current.Next = null;

}

else current.Next = current.Next.Next;

}

return RemuveItem;

}

}

// Специальные операции с записями

// Заменяет указанную запсиь последней, остальные отбрасывает.

public PData ChangeCurrentToLastAndCut(int n)

{

lock (this)

{

ListNode currFirst = firstNode;

ListNode currLast = lastNode;

for (int i = 1; i < n; i++)

currFirst = currFirst.Next;

PData RemuveItem = currFirst.Data;

if (firstNode != lastNode)

do

{

currLast = currFirst;

while (currLast.Next != lastNode)

currLast = currLast.Next;

currLast.Data = lastNode.Data; ;

currLast.Next = null;

lastNode = currLast;

} while (currLast != currFirst);

return RemuveItem;

}

}

// Специальные операции с записями

// Заменяет указанную запись следующей по списку и вовзращает

// удаленные данные.

public PData Left1(int n)

{

ListNode current = firstNode;

for (int i = 1; i < n; i++)

current = current.Next;

if (current.Next == null)

{

PData d = RemuveFromBack();

return d;

}

else

{

PData d = current.Data;

current.Data = current.Next.Data;

if (current.Next.Next == null)

{

current.Next = null;

lastNode = current;

}

return d;

}

}

// Проверка спаска на пустоту

public bool IsEmpty()

{

lock (this)

{

return firstNode == null;

}

}

// Модификация записи списка

public PData EditRow(PData newItem, int posItem)

{

ListNode current = firstNode;

for (int i = 1; i < posItem; i++)

current = current.Next;

PData d = current.Data;

current.Data = newItem;

return d;

}

public void ClearList()

{

firstNode = lastNode = null;

}

// Вывод ФИО пенсионеров

virtual public int PrintPension()

{

ListNode current = firstNode;

Console.WriteLine("\nСписок сотрудников пенсионного возраста:");

int n = 0;

do

{

// Для мужчин

if ((current.Data.Sex.ToUpper() == "М") && (current.Data.Age >= 60))

{

Console.WriteLine("{0} {1} {2}", current.Data.Surname, current.Data.Firstname, current.Data.Lastname);

n++;

}

// Для женщин

if ((current.Data.Sex.ToUpper() == "Ж") && (current.Data.Age >= 55))

{

Console.WriteLine("{0} {1} {2}", current.Data.Surname, current.Data.Firstname, current.Data.Lastname);

n++;

}

current = current.Next;

} while (current != lastNode);

return n;

}

// Вывод содержимого списка на консоль

virtual public int Print(string s, bool pak)

{

lock (this)

{

if (IsEmpty())

{

Console.WriteLine("Пустой " + name);

return 0;

}

Console.WriteLine(s + " " + name + ": ");

ListNode current = firstNode;

int n = 0;

while (current != null)

{

Console.Write(" {0} {1} {2} {3} {4} {5} {6}\n", current.Data.TabNom, current.Data.Surname, current.Data.Firstname, current.Data.Lastname, current.Data.Age, current.Data.Sex, current.Data.Adress);

current = current.Next;

n++;

}

if (pak)

{

Console.WriteLine("\n");

Console.ReadKey();

}

return n;

}

}

// Вывод содержимого списка в файл

virtual public bool Printf(string s)

{

if (IsEmpty())

{

Console.Write(" Список " + name + " пустой, действие отменяется.");

return false;

}

// FileInfo f = new FileInfo(@"D:\data" + s + ".txt");

StreamWriter fs = new StreamWriter(@"D:\data" + s + ".txt");

fs.WriteLine(name);

ListNode current = firstNode;

while (current != null)

{

fs.Write("{0} {1} {2} {3} {4} {5} {6}" + Convert.ToChar(13), current.Data.TabNom, current.Data.Surname, current.Data.Firstname, current.Data.Lastname, current.Data.Age, current.Data.Sex, current.Data.Adress);

current = current.Next;

}

fs.WriteLine();

fs.Close();

return true;

}

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

//Определение класса EmptyListException

public class EmptyListException : ApplicationException

{

public EmptyListException(string name)

: base("Список" + name + "пуст!")

{ }

}

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