Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Стек. От абстрактного, универсального класса к конкретным версиям
|
|
Возьмем классическую задачу определения стека. Следуя схеме, определим абстрактный универсальный класс, описывающий всевозможные представления стеков:
/// < summary> /// Абстрактный класс GenStack< T> задает контейнер с /// доступом LIFO: /// Функции: /// конструктор new: -> GenStack< T> /// запросы: /// item: GenStack -> T/// empty: GenStack -> Boolean/// процедуры: /// put: GenStack*T -> GenStack/// remove: GenStack -> GenStack/// Аксиомы: /// remove(put(s, x)) = s/// item(put(s, x)) = x/// empty(new)= true/// empty(put(s, x)) = false/// < /summary> abstract public class GenStack< T> { /// < summary> /// require: not empty(); /// < /summary> /// < returns> элемент вершины(последний пришедший)< /returns> abstract public T item(); /// < summary> /// require: not empty(); /// ensure: удален элемент вершины(последний пришедший) /// < /summary> abstract public void remove(); /// < summary> /// require: true; ensure: elem находится в вершине стека /// < /summary> /// < param name=" elem" > < /param> abstract public void put(T t); /// < summary> /// require: true; /// < /summary> /// < returns> true если стек пуст, иначе false < /returns> abstract public bool empty(); }// class GenStackВ приведенном примере программного текста чуть-чуть. Это объявление абстрактного универсального класса:
abstract public class GenStack< T>и четыре строки с объявлением сигнатуры его методов. Основной текст задает описание спецификации класса и его методов. Заметьте, здесь спецификации заданы достаточно формально с использованием аксиом, характеризующих смысл операций, которые выполняются над стеком.
Не хочется вдаваться в математические подробности, отмечу лишь, что, если задать последовательность операций над стеком, то аксиомы позволяют точно определить состояние стека в результате выполнения этих операций. Как неоднократно отмечалось с первых лекций курса, XML-отчет, построенный по этому проекту, будет содержать в читаемой форме все спецификации нашего класса. Отмечу еще, что все потомки класса должны удовлетворять этим спецификациям, хотя могут добавлять и собственные ограничения.
Наш класс является универсальным - стек может хранить элементы любого типа, и конкретизация типа будет производиться в момент создания экземпляра стека.
Наш класс является абстрактным - не задана ни реализация методов, ни то, как стек будет представлен. Эти вопросы будут решать потомки класса.
Перейдем теперь ко второму этапу и построим потомков класса, каждый из которых задает некоторое представление стека и соответствующую этому представлению реализацию методов. Из всех возможных представлений ограничимся двумя. В первом из них стек будет представлен линейной односвязной списковой структурой. Во втором - он строится на массиве фиксированного размера, задавая стек ограниченной емкости. Вот как выглядит первый потомок абстрактного класса:
/// < summary> /// Стек, построенный на односвязных элементах списка GenLinkable< T> /// < /summary> public class OneLinkStack< T>: GenStack< T> { public OneLinkStack() { last = null; } GenLinkable< T> last; //ссылка на стек (вершину стека) public override T item() { return (last.Item); }//item public override bool empty() { return (last == null); }//empty public override void put(T elem) { GenLinkable< T> newitem = new GenLinkable< T> (); newitem.Item = elem; newitem.Next = last; last = newitem; }//put public override void remove() { last = last.Next; }//remove}//class OneLinkStackПосмотрите, что происходит при наследовании от универсального класса. Во-первых, сам потомок также является универсальным классом:
public class OneLinkStack< T>: GenStack< T>Во-вторых, если потомок является клиентом некоторого класса, то и этот класс, возможно, также должен быть универсальным, как в нашем случае происходит с классом GenLinkable< T>:
GenLinkable< T> last; //ссылка на стек (элемент стека)В-третьих, тип T встречается в тексте потомка всюду, где речь идет о типе элементов, добавляемых в стек, как, например:
public override void put(T elem)По ходу дела нам понадобился класс, задающий представление элементов стека в списковом представлении. Объявим его:
public class GenLinkable< T> { public T Item; public GenLinkable< T> Next; public GenLinkable() { Item = default(T); Next = null; }}Класс устроен достаточно просто, у него два поля: одно для хранения элементов, помещаемых в стек и имеющее тип T, другое - указатель на следующий элемент. Обратите внимание на конструктор класса, в котором для инициализации элемента используется новая конструкция default(T), которая возвращает значение, устанавливаемое по умолчанию для типа T.
Второй потомок абстрактного класса реализует стек по-другому, используя представление в виде массива. Потомок задает стек ограниченной емкости. Емкостью стека можно управлять в момент его создания. В ряде ситуаций использование такого стека предпочтительнее по соображениям эффективности, поскольку не требует динамического создания элементов. Приведу текст этого класса уже без дополнительных комментариев:
public class ArrayUpStack< T>: GenStack< T> { int SizeOfStack; T[] stack; int top; /// < summary> /// конструктор /// < /summary> /// < param name=" size" > размер стека< /param> public ArrayUpStack(int size) { SizeOfStack = size; stack = new T[SizeOfStack]; top = 0; } /// < summary> /// require: (top < SizeOfStack) /// < /summary> /// < param name=" x" > элемент, помещаемый в стек< /param> public override void put(T x) { stack[top] = x; top++; } public override void remove() { top--; } public override T item() { return (stack[top-1]); } public override bool empty() { return (top == 0); }}//class ArrayUpStackСозданные в результате наследования классы-потомки перестали быть абстрактными, но все еще остаются универсальными. На третьем этапе порождаются конкретные экземпляры потомков - универсальных классов, в этот момент и происходит конкретизация типов, и два экземпляра одного универсального класса могут работать с данными различных типов. Этот процесс создания экземпляров с подстановкой конкретных типов называют родовым порождением экземпляров. Вот как в тестирующей процедуре создаются экземпляры созданных нами классов:
public void TestStacks(){ OneLinkStack< int> stack1 = new OneLinkStack< int> (); OneLinkStack< string> stack2 = new OneLinkStack< string> (); ArrayUpStack< double> stack3 = new ArrayUpStack < double> (10); stack1.put(11); stack1.put(22); int x1 = stack1.item(), x2 = stack1.item(); if ((x1 == x2) & & (x1 == 22)) Console.WriteLine(" OK! "); stack1.remove(); x2 = stack1.item(); if ((x1! = x2) & & (x2 == 11)) Console.WriteLine(" OK! "); stack1.remove(); x2 = (stack1.empty())? 77: stack1.item(); if ((x1! = x2) & & (x2 == 77)) Console.WriteLine(" OK! "); stack2.put(" first"); stack2.put(" second"); stack2.remove(); string s = stack2.item(); if (! stack2.empty()) Console.WriteLine(s); stack3.put(3.33); stack3.put(Math.Sqrt(Math.PI)); double res = stack3.item(); stack3.remove(); res += stack3.item(); Console.WriteLine(" res= {0}", res); }В трех первых строках этой процедуры порождаются три экземпляра стеков. Все они имеют общего родителя - абстрактный универсальный класс GenStack, но каждый из них работает с данными своего типа и по-разному реализует методы родителя. На рис. 22.3 показаны результаты работы этой процедуры.
Рис. 22.3. Три разных стека, порожденных абстрактным универсальным классом
Дополним наше рассмотрение еще одним примером работы с вариацией стеков, в том числе хранящим объекты класса Person:
public void TestPerson(){ OneLinkStack< int> stack1 = new OneLinkStack< int> (); OneLinkStack< string> stack2 = new OneLinkStack< string> (); ArrayUpStack< double> stack3 = new ArrayUpStack < double> (10); ArrayUpStack< Person> stack4 = new ArrayUpStack< Person> (7); stack2.put(" Петров"); stack2.put(" Васильев"); stack2.put(" Шустов"); stack1.put(27); stack1.put(45); stack1.put(53); stack3.put(21550.5); stack3.put(12345.7); stack3.put(32458.8); stack4.put(new Person(stack2.item(), stack1.item(), stack3.item())); stack1.remove(); stack2.remove(); stack3.remove(); stack4.put(new Person(stack2.item(), stack1.item(), stack3.item())); stack1.remove(); stack2.remove(); stack3.remove(); stack4.put(new Person(stack2.item(), stack1.item(), stack3.item())); Person pers = stack4.item(); pers.PrintPerson(); stack4.remove(); pers = stack4.item(); pers.PrintPerson(); stack4.remove(); pers = stack4.item(); pers.PrintPerson(); stack4.remove(); if (stack4.empty()) Console.WriteLine(" OK! "); }Результаты работы этой процедуры приведены на рис. 22.4.
Рис. 22.4. Работа со стеками