Список с курсором. Динамические структуры данных

Добавим в проект классы, задающие динамические структуры данных. Конечно, можно было бы воспользоваться стандартными… Но для обучения крайне полезно уметь создавать собственные классы, задающие такие структуры данных. Список с курсором – один из важнейших образцов подобных классов%:

using System;

namespace Shapes

{

/// <summary>

/// Класс TwoWayList(G)  описывает двусвязный список с

/// курсором. Элементами списка являются объекты

/// TwoLinkable, хранящие, помимо указателей на двух

/// преемников, объекты типа G.Курсор будет определять        /// текущий (активный) элемент списка. Класс будет

/// определять симметричные операции по отношению к

/// курсору.

/// Конструкторы:

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

/// список

/// Запросы:

/// empty: require: true; возвращает true для

/// непустого списка item: require: not empty();

/// возвращает активный элемент типа G; count:

/// require: true; возвращает число элементов списка;

/// count in[0,n]

/// (count == 0) eqviv empty();

/// index: require: not empty(); возвращает индекс

/// активного элемента.

/// search_res: require: true; возвращает true,

/// если последний поиск был успешным.

/// Команды:

/// put_left(elem): require: true;

/// ensure: добавить новый элемент (elem) слева от курсора;

/// put_right(elem): require: true;

/// ensure: добавить новый элемент (elem) справа от

/// курсора;

/// remove: require: not empty();

/// ensure: удалить активный элемент;

/// особо обрабатывается удаление последнего и

/// единственного элементов

/// операции с курсором:

/// start: require: true;

/// ensure: сделать активным первый элемент;

/// finish: require: true;

/// ensure: сделать активным последний элемент;

/// go_prev: require: not (index = 1);

/// ensure: сделать активным предыдущий элемент;

/// go_next: require: not (index = count);

/// ensure: сделать активным последующий элемент;

/// go_i(i): require:  (i in [1, count]);

/// ensure: сделать активным элемент с индексом i;

/// операции поиска:

/// search_prev(elem): require: not (index = 1);

/// ensure: сделать активным первый элемент elem

/// слева от курсора;

/// Успех или неуспех поиска сохранять в булевской

/// переменной search_res

/// search_next: require: not (index = count);

///        ensure: сделать активным первый элемент elem

/// справа от курсора;

/// успех или неуспех поиска сохранять в булевской

/// переменной search_res

/// </summary>

public class TwoWayList

{

public TwoWayList()

{

first = cursor = last = null;

count = index = 0;

search_res = false;

}//конструктор

/// <summary>

/// first, cursor, last – ссылки на первый,

/// активный и последний элементы списка

/// Запросы count, index search_res также

/// реализуются атрибутами.

/// Запросы empty, item реализуются функциями

/// </summary>

protected TwoLinkable first, cursor, last;

protected int count, index;

protected bool search_res;

//доступ на чтение к закрытым свойствам;

public int Count

{

get

{

return(count);

}

}

public int Index

{

get

{

return(index);

}

}

public bool Search_res

{

get

{

return(search_res);

}

}

/// <summary>

/// require: true; возвращает true для непустого списка

/// </summary>

/// <returns></returns>

public bool empty()

{

return(first == null);

}//empty

/// <summary>

/// require: not empty(); возвращает активный

/// элемент типа G;

/// </summary>

/// <returns></returns>

public Figure item()

{

return(cursor.Item);

}//item

/// <summary>

/// require: true;

/// ensure: добавить новый элемент (elem) слева

/// от курсора;

/// </summary>

/// <param name=”elem”>Тип Figure играет роль

/// родового типа G

/// хранимого элемента elem</param>

public void put_left(Figure elem)

{

TwoLinkable newitem = new TwoLinkable();

newitem.Item = elem;

newitem.Next = cursor;

if (empty())        //список пуст

{

first = cursor = last = newitem;

index =1; count = 1;

}

else

{

if (index == 1)

first =newitem;

else

cursor.Prev.Next = newitem;

newitem.Prev = cursor.Prev; cursor.Prev = newitem;

count++; index++;

}

}//put_right

/// <summary>

/// require: true;

/// ensure: добавить новый элемент (elem) справа

/// от курсора;

/// </summary>

/// <param name=”elem”>Тип Figure играет роль

/// родового типа G

/// хранимого элемента elem</param>

public void put_right(Figure elem)

{

TwoLinkable newitem = new TwoLinkable();

newitem.Item = elem;

newitem.Prev = cursor;

if (empty())        //список пуст

{

first = cursor = last = newitem;

index =1; count = 1;

}

else

{

if (index == count)

last =newitem;

else

cursor.Next.Prev = newitem;

newitem.Next = cursor.Next; cursor.Next = newitem;

count++;

}

}//put_right

public void remove()

{

if(count == 1)

{

first = last = cursor = null;

index=0;

}

else if(index==1)

{

first = cursor.Next;

cursor.Prev = null;

cursor = cursor.Next;

}

else if(index == count)

{

last = cursor.Prev;

cursor.Next = null;

cursor = cursor.Prev;

index–;

}

else

{

cursor.Prev.Next = cursor.Next;

cursor.Next.Prev = cursor.Prev;

cursor = cursor.Next;

}

count–;

}//remove

/// операции с курсором:

/// <summary>

/// start: require: true;

/// ensure: сделать активным первый элемент;

/// </summary>

public void start()

{

cursor = first; index = 1;

}//start

/// <summary>

/// finish: require: true;

/// ensure: сделать активным последний элемент;

/// </summary>

public void finish()

{

cursor = last; index = count;

}//finish

/// <summary>

/// go_prev: require: not (index = 1);

/// ensure: сделать активным предыдущий элемент;

/// </summary>

public void go_prev()

{

cursor = cursor.Prev; index–;

}// go_prev

/// <summary>

/// go_next: require: not (index = count);

/// ensure: сделать активным последующий элемент;

/// </summary>

public void go_next()

{

cursor = cursor.Next; index++;

}// go_next

/// <summary>

/// go_i(i): require:  (i in [1, count]);

/// ensure: сделать активным элемент с индексом i;

/// </summary>

/// <param name=”i”></param>

public void go_i(int i)

{

if(i >index)

while (i>index)

{

cursor = cursor.Next; index++;

}

else if(i<index)

while (i<index)

{

cursor = cursor.Prev; index–;

}

}// go_i

/// операции поиска:

/// <summary>

/// search_prev(elem): require: not (index = 1);

/// ensure: сделать активным первый элемент elem

/// слева от курсора;

/// </summary>

/// <param name=”elem”>искомый элемент</param>

public virtual void search_prev(Figure elem)

{

bool found = false;

while (!found && (index !=1))

{

cursor = cursor.Prev; index–;

found = (elem == item());

}

search_res = found;

}// search_prev

/// <summary>

/// успех или неуспех поиска сохранять в булевской

/// переменной search_res

/// search_next: require: not (index = count);

/// ensure: сделать активным первый элемент elem

/// справа от курсора;

/// успех или неуспех поиска сохранять в булевской

/// переменной search_res

/// </summary>

/// <param name=”elem”></param>

public virtual void search_next(Figure elem)

{

bool found = false;

while (!found && (index !=count))

{

cursor = cursor.Next; index++;

found = (elem == item());

}

search_res = found;

}//search_next

}

}

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

Классы элементов списка

Рассмотрим классы, описывающие элементы списков – элементы с одним и с двумя указателями:

using System;

namespace Shapes

{

/// <summary>

/// Класс Linkable(T)задает элементы списка,включающие:

/// информационное поле типа T – item

/// ссылку на элемент типа Linkable – next

/// Функции:

/// конструктор new: -> Linkable

/// запросы:

/// Get_Item: Linkable -> T

/// Get_Next: Linkable -> Linkable

/// процедуры:

/// Set_Item: Linkable*T -> Linkable

/// Set_Next: Linkable*Linkable -> Linkable

/// Роль типа T играет Figure

/// </summary>

public class Linkable

{

public Linkable()

{

item =null; next = null;

}

/// <summary>

/// закрытые атрибуты класса

/// </summary>

Figure item;

Linkable next;

/// <summary>

/// процедуры свойства для доступа к полям класса

/// </summary>

public Figure Item{

get{

return(item);

}

set{

item = value;

}

}

public Linkable Next{

get{

return(next);

}

set{

next = value;

}

}

}//class Linkable

/// <summary>

/// Класс TwoLinkable задает элементы с двумя ссылками

/// </summary>

public class TwoLinkable

{

public TwoLinkable()

{

prev = next = null;

}

/// <summary>

/// закрытые атрибуты класса

/// </summary>

TwoLinkable prev, next;

Figure item;

/// <summary>

/// процедуры свойства для доступа к полям класса

/// </summary>

public Figure Item

{

get

{

return(item);

}

set

{

item = value;

}

}

public TwoLinkable Next

{

get

{

return(next);

}

set

{

next = value;

}

}

public TwoLinkable Prev

{

get

{

return(prev);

}

set

{

prev = value;

}

}

}//class TwoLinkable

}