Двоичное дерево
struct btree
{
int val;
btree *left,*right;
};
Указанное свойство позволяет применить в двоичном дереве алгоритм двоичного поиска. Действительно, каждое сравнение искомого значения и значения в вершине двоичного дерева позволяют выбрать для следующего шага правое или левое поддерево. Алгоритмы включения и исключения вершин дерева не должны нарушать указанное свойство: при включении вершины дерева поиск места ее размещения производится путем аналогичных сравнений:
//------------------------------------------------------bk55-06.cpp
//----- Рекурсивный поиск в двоичном дереве---------------
// Возвращается указатель на найденную вершину
btree *Search(btree *p, int v)
{
if (p==NULL) return(NULL); // Ветка пустая
if (p->val == v) return(p); // Вершина найдена
if (p->val > v) // Сравнение с текущим
return(Search(p->left,v)); // Левое поддерево
else
return(Search(p->right,v)); // Правое поддерево
}
//----- Включение значения в двоичное дерево--------------
// функция возвращает указатель на созданную вершину,
// либо на существующее поддерево
btree *Insert(btree *pp, int v)
{
if (pp == NULL) // Найдена свободная ветка
{ // Создать вершину дерева
btree *q = new btree; // и вернуть указатель
q->val = v;
q->left = q->right = NULL;
return q;
}
if (pp->val == v) return pp;
if (pp->val > v) // Перейти в левое или
pp->left=Insert(pp->left,v); // правое поддерево
else
pp->right=Insert(pp->right,v);
return pp;
}
void main()
{
btree *ss=Search(ph,5); // пример вызова
ph=Insert(ph,6);
}
Двоичное дерево имеет также естественное представление и в обычном массиве.
Так, если вершина дерева имеет индекс n в массиве, то вершины левого и правого поддерева - 2*n и 2*n+1 соответственно. Головная вершина дерева имеет индекс, равный 1 . Кроме того, в таком массиве необходимо как-то обозначать пустые вершины (аналог указателя NULL).
Поиск в двоичном дереве требует количества сравнений, не превышающего максимальной длины ветви дерева, или максимальной длины цепочки его вершин. Следовательно, условием эффективности поиска в дереве является равенство длин его ветвей (сбалансированность). В самом крайнем случае дерево имеет одну ветвь и вырождается в односвязный список, в котором имеет место последовательный поиск. В идеальном случае, когда длины ветвей дерева отличаются не более, чем на 1 (сбалансированное дерево) и равны n или n-1 , при общем количестве вершин в дереве порядка " 2 в степени n " требуется не более n сравнений для нахождения требуемой вершины. Это соответствует характеристикам алгоритма двоичного поиска в упорядоченном массиве.
Таким образом, необходимым условием эффективного использования двоичного дерева для быстрого поиска является его сбалансированность. Поддержание сбалансированности при операциях включения и исключения является довольно трудной задачей.
Двоичное дерево может использоваться также для сортировки последовательности данных. Если производить включение в двоичное дерево последовательности элементов в порядке их поступления, то затем обычный рекурсивный обход этого дерева даст их упорядоченную последовательность:
//------------------------------------------------------bk55-07.cpp
// Рекурсивный обход двоичного дерева с выводом
// значений вершин в порядке возрастания
void Scan(btree *p)
{
if (p==NULL) return;
Scan(p->left);
cout << p->val << endl;
Scan(p->right);
}
void operator()(void* pnew,int (*cmp)(void*,void*))
{
if (data==NULL) { data=pnew; return; }
int n=(*cmp)(key,data);
if (n==0) return;
if (n < 0)
{
if (l==NULL) l=new btree;
(*l)(pnew,cmp);
}
else
{
if (r==NULL) r=new btree;
(*r)(pnew,cmp);
}
}
Простейшим случаем введения иерархии в систему классов является использование объектов ранее определенных классов в качестве элементов данных нового класса. Взаимодействие классов в этом случае ограничивается тем, что новый класс использует стандартный интерфейс объекта: функции-элементы и переопределенные операции, то есть работает с ним как с любым другим базовым типом данных. С абстрактной точки зрения элемент данных -объект класса представляет собой некоторое частное свойство более сложного класса, в котором он определен. Рассмотрим в качестве примера класс man -информация о человеке, включающая в себя даты рождения и поступления на работу:
class man
{
char name[20]; // Другие элементы класса
char *address;
dat dat1; // Дата рождения
dat dat2; // Дата поступления на работу
public: ...
man(char*); // Конструктор
};
Единственной проблемой здесь является конструирование объектов -элементов данных. Здравый смысл подсказывает, что если в конструкторе нового класса не содержится информации о конструировании объектов -элементов данных, то по умолчанию для них возможен только вызов их собственных конструкторов без параметров, причем перед вызовом конструктора нового класса. Действительно, последний может воспользоваться некоторыми свойствами уже инициализированных внутренних объектов.
Если все-таки требуется использовать конструкторы внутренних объектов с параметрами, то в заголовке конструктора нового класса их необходимо явно перечислить. Их параметры могут быть любыми выражениями, включающими формальные параметры конструктора нового класса:
class man
{
char name[20]; // Другие элементы класса
dat dat1; // Дата рождения
dat dat2; // Дата поступления на работу
public:
man(char *,char *,char *); // Конструкторы
man(char *);
};
//----- Конструктор класса man с неявным вызовом ----------
// конструкторов для dat1 и dat2 без параметров
man::man(char *p) { ... }
//----- Конструктор класса man с явным вызовом ------------
// конструкторов для dat1 и dat2 с параметрами
man::man(char *p,char *p1, char *p2) : dat1(p1), dat2(p2)
{ ... }
// Вызов конструктора для объекта dat1
// В качестве параметра передается строка -
// второй параметр вызова
// конструктора для класса man Вызов конструктора для объекта dat2
void main()
{
man JOHN("John","8-9-1958","15-1-1987");
// 1. Строка конструктора man
// 2. Строка передается конструктору объекта dat1 в объекте man
// 3. Строка передается конструктору объекта dat2 в объекте man
}
Другой способ создания иерархии классов заключается в том, что новый класс автоматически включает в себя все свойства старого класса, а затем развивает их. С абстрактной точки зрения старый класс определяет только общие свойства, а новый -конкретизирует более частные свойства.
Сохранение с новом классе свойств старого называется НАСЛЕДОВАНИЕМ . Принцип наследования состоит в том, что элементы данных старого класса автоматически становятся элементами данных нового класса, а все функции-элементы старого класса применимы к объекту нового класса, точнее к его старой составляющей.
Старый класс при этом называется БАЗОВЫМ КЛАССОМ (БК), новый - ПРОИЗВОДНЫМ КЛАССОМ (ПК).
Синтаксис определения производного класса имеет вид:
class производный : базовый_1, базовый_2,...базовый_n
{ определение личной и общей частей производного класса
}
Перечислим основные свойства базового и производного классов:
-объект базового класса определяется в производном классе как неименованный. Это значит, что он не может быть использован в явном виде как обычный элемент данных;
-элементы данных базового класса включаются в объект производного класса (как правило, транслятор размещает их в начале объекта производного класса). Однако личная часть базового класса закрыта для прямого использования в производном классе;
-функции-элементы базового класса наследуются в производном классе, то есть вызов функции, определенной в базовом классе возможен для объекта производного класса и понимается как вызов ее для входящего в него объекта базового класса;
-в производном классе можно переопределить (перегрузить) наследуемую функцию, которая будет вызываться вместо нее. При этом для выполнения соответствующих действий над объектом базового класса она может включать явный вызов переопределенной функции по полному имени.
Сказанное проиллюстрируем весьма условным примером определения производного класса:
class a
{
public:
void f() {}
void g() {}
};
// производный класс : базовый класс
class b : a
{
public:
void f() // "f" переопределяется
{ ...
a::f(); // явный вызов "f" для БК
} // "g" наследуется из БК
void h() {} // собственная функция в ПК
};
void main()
{
a A1;
b B1;
B1.f(); // вызов переопределенной b::f()
B1.g(); // вызов наследуемой a::f()
}
Предполагается, что при вызове в производном классе функций, наследуемых из базового, транслятор производит преобразование указателя this объекта производного класса в указатель на входящий в него объект базового класса, учитывая размещение второго в первом.
Взаимоотношение конструкторов и деструкторов базового и производного классов аналогичны описанным выше:
-если конструктор производного класса определен обычным образом, то сначала вызывается конструктор базового класса без параметров, а затем конструктор производного класса. Деструкторы вызываются в обратном порядке -сначала для производного, затем для базового;
-в заголовке конструктора производного класса может быть явно указан вызов конструктора базового класса с параметрами. Он может быть без имени, а может быть с именем базового класса. Если базовых классов несколько, то в вызовы конструкторов базовых классов должны быть перечислены через запятую и должны быть с поименованы.
Принцип наследования следует воспринимать прежде всего в рамках программирования " от класса к классу" .
При проектировании производного класса определяется потенциальное множество объектов с новыми свойствами, отличными от свойств объектов базового класса. Внешне наблюдаемые свойства объекта - это его методы. Поэтому перечисленные ниже варианты наследования методов базового класса в производном нужно воспринимать с более широкой точки зрения - как способы изменения свойств объекта.
1. l " Новое свойство" . Имя определяемого в производном классе метода не совпадает ни с одним из известных в базовом классе. В этом случае это - " новое свойство" объекта, которое объект приобретает в производном классе.
class a {
public: void f() {}
};
class b : public a
{
public: void newb() {} // newb() - новое свойство (метод)
};
2.l " Полное неявное наследование" . Если в производном классе метод не переопределяется, то по умолчанию он наследуется из базового класса. Это значит, что он может быть применен к объекту производного класса, при этом будет вызван метод для базового класса, причем именно для объекта базового класса, включенного в производный. Определенное в базовом классе свойство не меняется.
class a {
public: void f() {}
};
class b : public a
{
public: // f() - унаследованное свойство (метод)
}; // эквивалентно void f() { a::f(); }
3. l " Полное перекрытие" . Если в производном классе определяется метод, совпадающий с именем с методом базового класса, причем в теле метода отсутствует вызов одноименного метода в базовом классе, то мы имеем дело с полностью переопределенным свойством. В этом случае свойство объекта базового класса в производном классе отрицается, а метод производного класса " перекрывает" метод базового.
class a {
public: void f() {}
};
class b : public a
{
public:
void f() {...} // переопределенное свойство (метод)
};
4. l " Условное наследование" . Наиболее точно отражает сущность наследования последний вариант, в котором в производном классе переопределяется метод, перекрывающий одноименный метод базового класса.
Но в методе базового класса обязательно имеется вызов перекрытого метода базового класса - условный или безусловный. Этот прием наиболее полно соответствует принципу развития свойств объекта, поскольку свойство в производном классе является усложненным вариантом аналогичного свойства объекта базового класса.
class a {
public: void f() {}
};
class b : public a
{
public:
void f()
{... a::f(); .... }
// Переопределенное свойство развивает соответствующее свойство объекта
// базового класса. Переопределенный метод в явном виде вызывает метод
// в базовом классе по его полному имени.
};
Производный класс включает в себя как личную, так и общую части базового класса. При этом важно, в какую часть производного класса, личную или общую, они попадут. От этого зависит доступность элементов базового класса, как из функций-элементов производного класса, так и извне - через объекты производного класса. Здесь возможны следующие варианты:
-личная часть базового класса A всегда включается в личную часть производного класса B, но при этом непосредственно недоступна в классе B. Это соответствует общему принципу защиты данных класса от вмешательства извне.
-по умолчанию, то есть при использовании заголовка class B : A { } общая часть класса A попадает в личную часть класса B. Это значит, что функции-элементы класса A доступны из функций -элементов класса B, но не могут быть вызваны извне при обращении к объектам класса B. То есть для внешнего пользователя класса B интерфейс класса A закрывается;
-при использовании заголовка class B : public A { } общая часть класса A попадает в общую часть класса B, и внешнему пользователю при работе с объектами класса B доступны интерфейсы обоих классов;
-и наконец, в определении общей части класса B можно явно указать функции-элементы (а также данные) общей части базового класса A, которые попадают в общую часть класса B
class B : A
{
public:
public A::fun;
} ;
Из рассмотренных вариантов видно, что личная часть базового класса недоступна в любом производном классе -это естественно следует из свойств закрытости определения класса.
Однако по аналогии с дружественностью базовый класс может разрешить доступ к своим элементам личной части в производных классах. Это делается при помощи объявления защищенных (protected) элементов.
Элемент с меткой protected в базовом классе входит в личную часть базового класса. Кроме того, он доступен и в личной части производного класса. Если же базовый класс включается в производный как public, то защищенный элемент становится защищенным и в производном классе, то есть может использоваться в последующих производных классах.
Сказанное поясним примером:
class A
{
int a1; // Обычный личный элемент
protected:
int a2; // Защищенный личный элемент
public:
};
//----- Вариант 1: наследование без public ---------------
class B : A // a1,a2 в личной части B
{
void x();
};
void B::x()
{
a1 = 5; // Ошибка: a1 недоступен в B
a2 = 3; // a2 доступен в личной части B
}
//----- Вариант 2: наследование с public ------------------
class B : public A // a2 доступен и защищен в личной
{ // части B, неявно имеет место protected: int a2;
};
Применительно к базовому и производному классу можно сказать, что, преобразуя указатель на объект производного класса к указателю на объект базового класса, мы получаем доступ к вложенному объекту базового класса. Но при такой трактовке преобразования типа указателя транслятору необходимо учитывать размещение объекта базового класса в производном, что он и делает. В результате значение указателя (адрес памяти) на объект базового класса может оказаться не равным исходному значению указателя на объект производного. Ввиду " особости" такого преобразования оно может быть выполнено в Си++ неявно (остальные преобразования типов указателей должны быть явными).
Побочный эффект такого преобразования состоит в том, что транслятор "забывает" об объекте производного класса и вместо переопределенных в нем функций вызывает функции базового:
class A
{
public: void f1();
};
class B : A
{
public: void f1(); // Переопределена в классe B
void f2();
};
A *pa;
B *pb;
B x;
pa = &x;
// Неявное преобразование указателя на объект
// класса B в указатель на объект класса A
pa->f1();
// Вызов функции из вложенного объекта базового
// класса A::f1(), хотя она переопределена
Обратное преобразование от указателя на базовый класс к указателю на производный может быть сделано только явно. Преобразование будет корректно, если данный объект базового класса действительно входит в объект того производного класса, к типу указателя которого оно выполняется:
pb = (B*) pa; // Обратное преобразование - явное
pb ->f2(); // Корректно, если под "pa" был объект класса "B"
С понятием производных классов тесно связан ПОЛИМОРФИЗМ. Прежде всего, полиморфизм -это свойство функции определенной в множестве производных классов, построенных на основе общего базового. В каждом из классов функция может быть переопределена, а может быть унаследована из базового. Свойство полиморфности заключается в том, что при отсутствии полной информации о том, к какому из классов относится объект, функция в состоянии идентифицировать его класс и корректно выполниться в этом классе. Важнейшее следствие полиморфности -возможность организовать регулярный процесс обработки объектов группы производных классов.
Сформулируем теперь свойство полиморфности уже с использованием терминов Си++. Пусть имеется базовый класс A и производные классы B,C. В классе А определена функция -элемент f(), в классах B,C -унаследована и переопределена. Пусть теперь имеется массив указателей на объекты базового класса -p. Он инициализирован как указателями на объекты класса A, так и на объекты производных классов B,C (точнее, на вложенные в них объекты базового класса A):
class a
{ ... void f(); };
class b : public a
{ ... void f(); };
class c : public a
{ ... void f(); };
a A1;
b B1;
c C1;
a *p[3] = { &B1, &C1, &A1 };
Как будет происходить вызов обычной неполиморфной функции при использовании указателей из этого массива ? Очевидно, что транслятор, располагая исключительно информацией о том, что указуемыми переменными являются объекты базового класса A (что следует из определения массива), вызовет во всех случаях функцию a::f().
То же самое произойдет, если обрабатывать массив указателей в цикле:
p[0]->f(); // Вызов a::f()
p[1]->f(); // во всех трех случаях
p[2]->f(); // по указателю на объект базового класса
for (i=0; i<=2; i++)
p[i]->f();
Наличие указателя на объект базового класса A свидетельствует о том, что в данной точке программы транслятор не располагает информацией о том, объект какого из производных классов расположен под указателем. Тем не менее, если функция является полиморфной, то при вызове ее по указателю на объект базового класса она должна идентифицировать его производный класс и вызвать переопределенную функцию именно для этого класса:
p[0]->f(); // вызов b::f() для B1
p[1]->f(); // вызов c::f() для C1
p[2]->f(); // вызов a::f() для A1
for (i=0; i<=2; i++) // вызов b::f(),c::f(),a::f()
p[i]->f(); // в зависимости от типа объекта
В Си++ полиморфная функция называется ВИРТУАЛЬНОЙ ФУНКЦИЕЙ.
Наиболее содержательным синонимом к термину полиморфная (виртуальная) функция является термин l " многоликая" . Действительно создается этот механизм виртуальной функции создает иллюзию функции " единой во многих лицах" - в каждом из производных классов. В то же время базовый класс позволяет объединить эти все разнородные функции под одним общим началом - объектом базового класса, включенным во все производные. Объект базового класса должен быть доступен через указатель только по той причине, что это единственный в Си механизм, позволяющий ссылаться на объекты неопределенного вида (объект одного из производных классов).
Таким образом, если при преобразовании типа " указатель на производный класс" к типу " указатель на базовый класс" происходит потеря информации о типе объекта производного класса, то при вызове виртуальной функции происходит обратный процесс неявного восстановления типа объекта.
Принцип реализации механизма виртуальных функций заключается в том, что объект базового класса должен содержать в себе информацию о преобразовании указателя на базовый класс в указатель на производный (смещение) и о функциях-элементах объекта производного класса (указатели на функции).
В простейшем случае это реализуется через массив указателей на функции. Для каждой пары производный класс -базовый класс транслятором генерируется свой массив указателей, каждой виртуальной функции соответствует в нем свое значение индекса. Указатель на массив (начальный адрес) записывается в объект базового класса в момент конструирования объекта производного класса. Проиллюстрируем сказанное средствами "классического" Си:
// Компоненты, создаваемые транслятором, обозначены " * **"
class A
{
void (**ftable)(); //* ** Указатель на массив
public: // указателей виртуальных функций
virtual void x();
virtual void y();
virtual void z();
A();
~A();
};
#define vx 0 //* ** Индексы в массиве
#define vy 1 //* ** указателей на
#define vz 2 //* ** виртуальные функции
// Массив адресов функций класса А
void (*TableA[])() = { A::x, A::y, A::z }; //***
A::A()
{ ftable = TableA; //* ** Установка массива для класса А
}
class B : public A
{
public:
void x();
void z();
B();
~B();
};
// Массив адресов функций класса A в B
// A::y - наследуется из А, B::x - переопределяется в B
void (*TableB[])() = { B::x, A::y, B::z }; //***
B::B()
{ A::ftable = TableB; // *** Установка таблицы для класса B
}
void main()
{
A* p; // Указатель p базового класса A
B nnn; // ссылается на объект производного класса B
p = &nnn;
p->z(); // *** реализация - (*(p->ftable[vz]))();
}
Виртуальной может быть не только обычная функция-элемент, но и переопределяемая операция.
Если базовый класс используется только для порождения производных классов, то виртуальные функции в базовом классе могут быть "пустыми", поскольку никогда не будут вызваны для объекта базового класса. Базовый класс в котором есть хотя бы одна такая функция, называется АБСТРАКТНЫМ. Виртуальные функции в определении класса обозначаются следующим образом:
class base
{
public:
virtual print()=0;
virtual get() =0;
};
Определять тела этих функций не требуется.
Множественным наследованием называется процесс создания производного класса из двух и более базовых. В этом случае производный класс наследует данные и функции всех своих базовых предшественников. Существенным для реализации множественного наследования является то, что адреса объектов второго и последующих базовых классов не совпадают с адресом объекта производного класса. Этот факт должен учитываться транслятором при преобразовании указателя на производный класс в указатель на базовый и наоборот:
class d : public a,public b, public c { };
d D1;
pd = &D1; // #define db sizeof(a)
pa = pd; // #define dc sizeof(a)+sizeof(b)
pb = pd; // pb = (char*)pd + db
pc = pd; // pc = (char*)pd + dc
pc
Такое действие выполняется компилятором как явно при преобразовании в программе типов указателей, так и неявно, когда в объекте производного класса наследуется функция из второго и последующих базовых классов. Для вышеуказанного примера при определении в классе bb функции f() и ее наследовании в классе "d" вызов D1.f() будет реализован следующим образом:
this = &D1; // Указатель на объект производного класса
this = (char*)this + db // Смещение к объекту базового класса
b::f(this); // Вызов функции в базовом классе
Механизм виртуальных функций при множественном наследовании имеет свои особенности. Во-первых, на каждый базовый класс в производном классе создается свой массив виртуальных функций (в нашем случае -для aa в d, для bb в d и для cc в d ). Во-вторых, если функция базового класса переопределена в производном, то при ее вызове требуется преобразовать указатель на объект базового класса в указатель на объект производного. Для этого транслятор включает соответствующий код, корректирующий значение this в виде "заплаты", передающей управление командой перехода к переопределяемой функции, либо создает отдельные таблицы смещений.
В процессе иерархического определения производных классов может получиться, что в объект производного класса войдут несколько экземпляров объектов базового класса, например:
class base {}
class aa : public base {}
class bb : public base {}
class cc : aa, bb {}
В классе cc присутствуют два объекта класса base. Для исключения такого дублирования объект базового класса должен быть объявлен виртуальным:
class a : virtual public base {}
class b : virtual public base {}
class c : public a, public b {}
a A1;
b B1;
c C1;
Объект обычного базового класса располагается, как правило, в начале объекта производного класса и имеет фиксированное смещение. Если же базовый класс является виртуальным, то требуется его динамическое размещение. Тогда в объекте производного класса на соответствующем месте размещается не сам объект базового класса, а указатель на него, который устанавливается конструктором. Для вышеприведенного примера получим такую картину:
Один из наиболее распространенных приемов использования виртуальных функции - создание базовых классов, объединяющих в единую группу различные классы на основе некоторого общего свойства. Базовый класс при этом заключает в себе общие свойства группы, а весь набор действий, которые одинаково применимы к объектам из любого класса, реализуется через виртуальные функции.
В качестве примера рассмотрим группу классов - типов данных. Допустим, проектируется база данных, предназначенная для хранения произвольных объектов (типов данных). Прежде всего, определяется ряд общих действий, которые обязательно должны быть выполнимы к объекте любого класса, чтобы он мог включаться в базу данных.
class ADT
{
public:
virtual int Get(char *)=0; // Загрузка объекта из строки
virtual char *Put()=0; // Выгрузка объекта в строку
virtual long Append(BinFile&)=0; // Добавить объект в двоичный файл
virtual int Load(BinFile&)=0; //
virtual int Type()=0; // Возвращает идентификатор
// типа объекта
virtual char *Name()=0; // Возвращает имя типа объекта
virtual int Cmp(ADT *)=0; // Сравнивает значения объектов
virtual ADT *Copy()=0; // Создает динамический объект -
// копию с себя
virtual ~ADT(){}; // Виртуальный деструктор
};
Как видим, базовый класс получился абстрактным, то есть его объект не содержит данных, а функции являются " пустыми" . Это значит, что объекты базового класса не могут создаваться в программе, а сам класс создан исключительно как " объединяющая идея" некоторого типа данных. В принципе, базовый класс может содержать данные и непустые функции, если в самой группе классов можно выделить некоторую общую часть.
Естественно, что при проектировании любого производного класса должен соблюдаться приведенный шаблон, то есть в первую очередь в нем должны быть реализованы виртуальные функции, которые поддерживают в нем перечисленные действия. Остальная часть класса может быть какой угодно, естественно, что она уже не может быть использована в общих функциях работы с базой данных.
Базовый класс и набор виртуальных функций используются как общий интерфейс доступа к объектам - типам данных при проектировании базы данных. Любое множество объектов, для которых осуществляются основные алгоритмы базы данных (хранение, включение, исключение, сортировка, поиск и т.д.) будут представлены как множество указателей на объекты базового класса ADT , за которыми могут " скрываться" объекты любых производных классов. Естественно, что все действия, выполняемые над объектами будут осуществляться через перечисленные виртуальные функции. В качестве примера рассмотрим фрагмент класса - массив указателей, который здесь выступает аналога базы данных.
#include "ADT.h"
// Динамический массив указателей ADT*
class MU
{
int sz;
ADT **p;
public:...
ADT *min(); // Поиск минимального
void sort(); // Сортировка
int test(); // Проверка на идентичность типов
};
// Вызов виртуальных функций отмечен " ***"
int MU::test()
{
for (i=1; p[i]!=NULL; i++)
if (p[i]->Type()!=p[i-1]->Type()) return 0; //***
return 1;
}
ADT *MU::min()
{ ADT *pmin; int i;
if (p[0]==NULL || !test()) return NULL;
for (i=0, pmin=p[0]; p[i]!=NULL; i++)
if (pmin->Cmp(p[i]) > 0) pmin=p[i]; //***
return pmin;
}
void MU:sort()
{ int d,i; void *q;
if (p[0]==NULL || !test()) return;
do {
for (d=0, i=1; p[i]!=NULL; i++)
if (p[i-1]->Cmp(p[i]) > 0) //***
{d++; q=p[i-1]; p[i-1]=p[i]; p[i]=q; }
}
while (d!=0);}
