Основы программирования на C#


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


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

using System; namespace Shapes { /// <summary> /// Класс TwoWayList(G) описывает двусвязный список с /// курсором. Элементами списка являются объекты /// TwoLinkable, хранящие, помимо указателей на двух /// преемников, объекты типа G.Курсор будет определять /// текущий (активный) элемент списка. Класс будет /// определять симметричные операции по отношению к /// курсору. /// Конструкторы: /// Конструктор без параметров будет создавать пустой /// список /// Запросы: /// empty: require: true; возвращает true для пустого списка /// item: require: not empty(); возвращает активный элемент типа G; /// require: true; возвращает число элементов списка; /// count: 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;




Начало  Назад  Вперед