Страница 337 из 371
Чтобы не затемнять ситуацию сложностью списка, рассмотрим достаточно простой односвязный список с курсором. Элементы этого списка будут принадлежать классу Node, два поля которого будут хранить ключ и сам элемент, а третье поле будет задавать указатель на следующий элемент списка. Очевидно, что этот класс должен быть универсальным классом. Вот как выглядит текст этого класса:
class Node<K, Т> where К: IComparable<K>
{
public Node()
{
next = null; key = default(K); item = default(T);
}
public К key;
public T item;
public Node<K, T> next;
}
Класс Node имеет два родовых параметра, задающих тип ключей и тип элементов. Ограничение на тип ключей позволяет выполнять их сравнение. В конструкторе класса поля инициализируются значениями по умолчанию соответствующего типа.
Рассмотрим теперь организацию односвязного списка. Начнем с того, как устроены его данные:
public class OneLinkList<K, Т> where К: IComparable<K>
{
Node<K, T> first, cursor;
}
Являясь клиентом универсального класса Node, наш класс сохраняет родовые параметры клиента и ограничения, накладываемые на них. Два поля класса — first и cursor — задают указатели на первый и текущий элементы списка. Операции над списком связываются с курсором, позволяя перемещать курсор по списку. Рассмотрим вначале набор операций, перемещающих курсор:
public void start ()
{ cursor = first; } public void finish ()
{
while (cursor.next!= null)
cursor = cursor.next;
}
public void forth()
{ if (cursor.next!= null) cursor = cursor.next; }
Операция start передвигает курсор к началу списка, finish — к концу, a forth — к следующему элементу справа от курсора. Операции finish и forth определены только для непустых списков. Конец списка является барьером, и курсор не переходит через барьер. Нарушая принципы ради краткости текста, я не привожу формальных спецификаций методов, записанных в тегах <summary>.
Основной операцией является операция добавления элемента с ключом в список. Возможны различные ее вариации, из которых рассмотрим только одну — новый элемент добавляется за текущим, отмеченным курсором. Вот текст этого метода:
public void add(К key, Т item)
{
Node<K, T> newnode = new Node<K, T>();
if (first == null)
{
first = newnode; cursor = newnode;
newnode.key = key; newnode.item = item;
}
else
{
newnode.next = cursor.next; cursor.next = newnode;
newnode.key = key; newnode.item = item;
}
}
Заметьте, аргументы метода имеют соответствующие родовые параметры, чем и обеспечивается универсальный характер списка. При добавлении элемента в список различаются два случая — добавление первого элемента и всех остальных.
Рассмотрим теперь операцию поиска элемента по ключу, реализация которой потребовала ограничения универсальности типа ключа к;
public bool findstart(К key)
{
Node<K, T> temp = first;
while (temp!= null)
{
if (temp.key.CompareTo(key) == 0) {cursor=temp;
return(true);}
temp= temp.next;
}
return (false);
}
Искомые элементы разыскиваются во всем списке. Если элемент найден, то курсор устанавливается на найденном элементе и метод возвращает значение true. Если элемента с заданным ключом нет в списке, то позиция курсора не меняется, а метод возвращает значение false, в процессе поиска для каждого очередного элемента списка вызывается допускаемый ограничением метод CompareTo интерфейса IComparable. При отсутствии ограничений универсальности вызов этого метода или операции эквивалентности приводил бы к ошибке, обнаруживаемой на этапе компиляции.
Два метода класса являются запросами, позволяющими извлечь ключ и элемент списка, который отмечен курсором:
public К Key ()
{
return (cursor.key);
}
public T Item()
{
return(cursor.item);
}
Давайте рассмотрим теперь тестирующую процедуру — клиента нашего списка, демонстрирующую работу со списками, в которых элементы и ключи имеют разные типы:
public void TestConstraint ()
{
OneLinkList<int, string> list1 = new OneLinkList
<int, string>();
list1.add(33, "thirty three"); list1.add (22, "twenty two");
if (list1.findstart(33)) Console.WriteLine ("33 — найдено!");
else Console.WriteLine("33 — не найдено!");
if (list1.findstart(22)) Console.WriteLine ("22 — найдено!");
else Console.WriteLine("22 — не найдено!");
if (list1.findstart(44)) Console.WriteLine ("44 — найдено!");
else Console.WriteLine("44 — не найдено!");
Person pers1 = new Person("Савлов", 25, 1500);
Person pers2 = new Person("Павлов", 35, 2100);
OneLinkList<string, Person> list2 = new OneLinkList
< string, Person>();
list2.add("Савл", pers1); list2.add("Павел", pers2);
if (list2.findstart("Павел")) Console.WriteLine ("Павел — найдено!");
else Console.WriteLine("Павел — не найдено!");
if (list2.findstart("Савл")) Console.WriteLine ("Савл — найдено!");
else Console.WriteLine("Савл — не найдено!");
if (list2.findstart("Иоанн")) Console.WriteLine ("Иоанн — найдено!");
else Console.WriteLine("Иоанн — не найдено!");
Person pers3 = new Person("Иванов", 33, 3000);
list2.add("Иоанн", pers3); list2.start ();
Person pers = list2.Item(); pers.PrintPerson();
list2.findstart("Иоанн"); pers = list2.Item();
pers.PrintPerson();
}
Рис. 22.5. Поиск в списке с ограниченной универсальностью
Обратите внимание на строки, где создаются два списка:
OneLinkList<int, string> list1 = new OneLinkList<int, string>();
OneLinkList<string, Person> list2 = new OneLinkList< string, Person>();
У списка list1 ключи имеют тип int, у списка list2 — string. Заметьте, оба фактических типа, согласно обязательствам, реализуют интерфейс IComparable, у первого списка тип элементов — string, у второго — Person. Все работает прекрасно. Вот результаты вычислений по этой процедуре:
Как справиться с арифметикой
Представьте себе, что мы хотим иметь специализированный вариант нашего списка, элементы которого допускали бы операцию сложения и одно из полей которого сохраняло бы сумму всех элементов, добавленных в список. Как задать соответствующее ограничение на класс?
Как уже говорилось, наличие ограничения операции, где можно было бы указать, что над элементами определена операция +, решало бы проблему. Но такого типа ограничений нет. Хуже того, нет и интерфейса INumeric, аналогичного IComparable, определяющего метод сложения Add. Так что нам не может помочь и ограничение наследования.
Вот один из возможных выходов, предлагаемых в такой ситуации. Стратегия следующая: определим абстрактный универсальный класс Calc с методами, выполняющими вычисления. Затем создадим конкретизированных потомков этого класса. В классе, задающем список с суммированием, введем поле класса Calc. При создании экземпляров класса будем передавать фактические типы ключа и элементов, а также соответствующий калькулятор, но уже не как тип, а как аргумент конструктора класса. Этот калькулятор, согласованный с типом элементов, и будет выполнять нужные вычисления. Давайте приступим к реализации этой стратегии. Начнем с определения класса Calc;