Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
|
Список с курсором. Динамические структуры данных
Добавим в проект классы, задающие динамические структуры данных. Конечно, можно было бы воспользоваться стандартными... Но для обучения крайне полезно уметь создавать собственные классы, задающие такие структуры данных. Список с курсором - один из важнейших образцов подобных классов%:
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 }}Заметьте, класс подробно документирован. Для методов класса указываются предусловия и постусловия. Обратите внимание, в соответствии с принципами контрактного программирования клиент класса, прежде чем вызвать метод, должен проверить выполнимость предусловия, что повышает корректность работы системы в целом. Именно так и будет реализован вызов этих методов в классе формы, где осуществляется работа со списком.
Данная страница нарушает авторские права?