2015-01-30
999
Можно выделить следующие основные классы динамических объектов:
· упорядоченные совокупности характеризуются тем, что для них значим физический порядок встраивания элементов. Пример — массивы;
· неупорядоченные совокупности или коллекции — физический порядок объектов в представлении данных незначим, встраивание объектов в коллекцию произвольно. Примеры — хэши, одно‑ и двусвязные списки, деревья;
· последовательности — физический порядок объектов в представлении данных незначим, но значим порядок вставки/удаления, которые выполняются только в определенных точках последовательности. Примеры — стеки, очереди.
Существуют 2 основных возможности для организации динамических структур:
· библиотеки функций classlib;
· организация динамических наборов структур, связанных указателями на структурные типы.
Реализация динамических структур через предопределенные классы требует подключения библиотеки TCLASSS.LIB (если выбрана модель Small, также есть TCLASSL.LIB для Large) из папки BORLANDC\CLASSLIB\LIB к файлу проекта, а также включения в строку опций Include Directories маршрута \BORLANDC\CLASSLIB\INCLUDE. Если предположить, что среда установлена в папку d:\BORLANDC, настройки путей могут иметь следующий вид:
|
|
|
Include Directories:
d:\BORLANDC\INCLUDE; d:\BORLANDC\CLASSLIB\INCLUDE; d:\BORLANDC\TVISION\DEMOS;.
Library directories:
d:\BORLANDC\LIB;d:\BORLANDC\TVISION\LIB;
d:\BORLANDC\CLASSLIB\LIB;.
Output Directory:.
Source Directories: d:\BORLANDC\BIN;.
Подробное рассмотрение иерархии классов библиотек classlib можно найти в специальной литературе, в данном пособии мы подробнее рассмотрим независимое программирование динамических списков структур.
В простейшем случае элемент списка представляет собой структурную переменную, содержащую один или несколько указателей на следующие или предшествующие элементы и любое число других полей, называемых информационными. Если список располагается в оперативной памяти, то информацией для поиска следующего элемента служит адрес (указатель) в памяти. Если список хранится в файле, информация о следующем элементе может включать смещение от начала файла, относительное положение указателя записи/считывания файла, ключ записи и любую другую информацию, позволяющую однозначно отыскать следующий элемент.
Описанный далее односвязный (однонаправленный) список имеет одно информационное поле и один указатель на следующий элемент:
typedef struct list {
list * next;
int info;
};
Для работы с элементами такого списка достаточно определить статический указатель на начало списка
list * head;
и хотя бы один "буферный" элемент, который будет служить для ввода и временного хранения данных:
list work;
Как минимум, функции работы с элементами списка, принимающие в качестве параметра указатель на некоторый его элемент, должны реализовывать операции вывода по порядку всех или избранного элемента, добавление и удаление элементов с выделением и высвобождением памяти, возможно, также поиск элементов, определение того, содержится ли уже в списке нужный элемент и т.п.
|
|
|
Например, функция вывода всех элементов списка, использующая глобальный указатель root на его вершину, могла бы иметь следующий вид:
struct list *root;
//Указатель на вершину списка
void List (void) {
struct list *iter = root;
int i = 0;
while(iter!= NULL) {
//Пока указатель не пуст
printf ("\n элемент %2d: (%d)",
i++,iter->info);
//Напечатать очередной элемент списка
iter = iter->next;
//и перейти к след. элементу
}
}
Разумеется, информационные поля списочной структуры также могут выделяться динамически, как показано в примере ниже. Здесь для простоты элементы добавляются всегда в конец списка и выводятся в порядке ввода. Ввод нуля с клавиатуры служит признаком конца ввода.
#include <stdio.h>
#include <alloc.h>
#include <string.h>
typedef struct list {
char *s;
list *next;
};
void main () {
list head, *ptr;
int i=0;
char s[80];
ptr=&head;
ptr->next=NULL;
do {
printf (" %d) ",i+1);
fgets (s,80,stdin);
if (!strcmp(s,"0\n")) {
break;
}
else {
ptr->s=(char *)malloc(strlen(s));
strcpy (ptr->s,s);
ptr->next=(list *)malloc(sizeof(list));
ptr=ptr->next;
ptr->next=NULL;
}
i++;
} while (1);
ptr=&head;
i=1;
while (ptr->next!=NULL) {
printf ("%d) %s",i++,ptr->s);
ptr=ptr->next;
}
}
В реальном спиcке может потребоваться множество дополнительных функций, таких как встраивание элементов в определенном порядке, перестановка, удаление, модификация и т. д. Приведем пример функции add(), добавляющий элемент, определяемый указателем new_ptr, в список с вершиной head. Встраивание элемента производится по возрастанию значения поля info, предполагается, что перед этим элемент уже проверен на уникальность функцией hasMember(). Использование указателя list **head в функции add() позволяет избежать прямого сравнения указателей в коде. При описании указателя на начало списка в виде list *head; и указателя на новый элемент list *new_ptr;, функция могла бы быть вызвана оператором вида add(&head, new_ptr);.
int add(list ** head, list * new_ptr) {
list * first, * second;
if ((*head)==NULL) { //список пуст
(* head) = new_ptr;
new_ptr -> next = NULL;
return 0;
}
if ((*head)->next == NULL) {
//в списке один элемент
if ((*head)->info > new_ptr->info) {
// новый элемент - первый в списке
second = (*head);
// сохраним указатель на 2-й элемент
(*head) = new_ptr;
new_ptr -> next = second;
second -> next = NULL;
}
else { // новый элемент в конец списка
(*head) -> next = new_ptr;
new_ptr -> next = NULL;
}
return 1;
}
else { //в списке более 1 элемента
if ((*head)->info > new_ptr->info) {
// новый элемент - первый в списке
second = (*head);
(*head) = new_ptr;
new_ptr -> next = second;
return 4;
}
first = (* head);
second = first -> next;
while (first->next!= NULL) {
//цикл поиска места в списке
if (first->info <= new_ptr->info &&
second->info >= new_ptr->info) {
// вставляем элемент между
// first и second
first -> next = new_ptr;
new_ptr -> next = second;
return 2;
}
first = second;
second = first -> next;
}
// если добрались сюда,
// ставим элемент в конец списка
first -> next = new_ptr;
new_ptr -> next = NULL;
return 3;
}
}
int hasMember (list * head, list * work) {
while(head!= NULL) {
// цикл сканирования списка
if (head->info == work -> info) return 1;
head = head -> next;
}
return(0);
}
Аналогичным образом с использованием структур и указателей могут быть реализованы другие динамические стуктуры данных. Приведем пример на работу с деревом, каждый узел которого может иметь произвольное количество узлов-потомков.
#include <stdio.h>
#include <stdlib.h>
#include <alloc.h>
typedef struct tree {
int info;
tree **childs;
unsigned count;
};
int const size1=sizeof(tree);
void error (int c) {
printf ("\nError: ");
switch (c) {
case 1: printf(" no memory"); break;
default: printf(" unknown"); break;
}
exit (c);
}
tree *init (tree *p,int info) {
p->info=info;
p->count=0;
p->childs=NULL;
return p;
}
void print1 (tree *p) {
printf ("\nnode %6d: %2d child(s)",
p->info,p->count);
}
void printnode (tree *p) {
print1 (p);
for (int i=0; i<p->count; i++)
print1 (p->childs[i]);
}
tree *searchnode (tree *t, int info) {
if (t->info == info) return t;
else if (t->count>0) {
|
|
|
for (int i=0; i<t->count; i++) {
tree *p=searchnode (t->childs[i],info);
if (p!=NULL) return p;
}
return NULL;
}
else return NULL;
}
tree *addnode (tree *ptr, int parentinfo,
int info) {
tree *p=searchnode (ptr,parentinfo);
if (p!=NULL) {
if (p->childs==NULL) {
p->childs = (tree **)malloc
(sizeof(tree *));
if (p->childs==NULL) error (1);
p->childs[0]=(tree *)malloc(size1);
if (p->childs[0]==NULL) error (1);
(p->count)=1;
}
else {
p->childs = (tree **)
realloc(p->childs,sizeof(tree *)
*(p->count+1));
if (p->childs==NULL) error (1);
p->childs[p->count]=(tree *)
malloc(size1);
if (p->childs[p->count]==NULL)
error (1);
(p->count)++;
}
return init (p->childs[p->count-1],info);
}
return NULL;
}
void main () {
tree head,temp,*ptr;
ptr=&head;
init(ptr,1);
addnode (ptr,1,2);
addnode (ptr,1,3);
addnode (ptr,2,4);
tree *s=searchnode (ptr,2);
printf ("\n With node after search:");
if (s!=NULL) printnode (s);
else printf ("\nNULL");
printf ("\n With root:");
printnode (ptr);
}
Классы
Классы появились в языке Си++, служащем расширением классического Си. Формально описание класса выглядит следующим образом:
class ИмяКласса {
private:
Список членов класса;
protected:
Список членов класса;
public:
Список членов класса;
};
Список членов класса включает описание типов и имен как данных, так и функций. Переменные, перечисляемые в классе, по умолчанию имеют область видимости в пределах класса (private), и доступ к ним имеют только функции‑члены данного класса. Обычно функции‑члены имеют тип доступа public, т.е., видимы вне класса, к ним может осуществляться доступ извне. Атрибут protected назначается тем членам класса, которые могут использоваться методами данного и производных от него классов.
Функции‑члены связаны с классом специальным оператором:: и обычно описаны сразу после описания класса, к которому принадлежат. В остальном они выглядят как обычные функции Си.
Рассмотрим работу с классом на подробном примере.
#include <stdio.h>
#include <stdlib.h>
class cList { //Класс для описания списка
unsigned int item;
cList *next;
// Указатель на следующий элемент
public:
void show(); // Просмотр списка
cList();//Конструктор по умолчанию -
//сгенерировать item случайно
cList (FILE *);
//Другой конструктор - прочитать
//элемент из файла
cList (unsigned int);
//Третий конструктор -
//ввести значение с клавиатуры
~cList(); // Деструктор
void Start (); //Прототипы
void End(); //методов класса
};
|
|
|
cList *first=NULL; //начало списка
void cList::show() {
cList *p; int i=1;
for (p=first; p!=NULL; p=p->next) {
printf ("\n Элемент %d) %u",i++,p->item);
}
}
cList::cList() {
randomize();
item=random(32000);
next=this;
}
cList::cList(FILE *f) {
unsigned int n=0;
fscanf (f,"%u",&n);
fclose (f);
item=n;
next=this;
}
cList::cList(unsigned int n) {
item = n;
next = this;
}
void cList::Start () {
this->next = first;
first = this;
}
void cList::End () {
cList *sled,*pred;
for (sled=first,pred=NULL;
sled!=NULL; pred=sled,sled=sled->next);
pred->next = this;
this->next = NULL;
sled = this;
}
void main () {
cList *List1 = new cList(3);
List1->Start();
cList *List2 = new cList ();
List2->End();
List1->show();
//...
}
Оператор. (точка), как и в Delphi, позволяет связать функцию с конкретным экземпляром класса. При использовании указателей, как и со структурами, конструкция (*указатель).поле заменяется на указатель->поле.
Для того, чтобы вызываемая функция точно "знала", с каким из объектов класса она работает, Си++ неявно передает в нестатическую функцию еще один скрытый параметр - указатель на текущий объект, называемый this. Параметр this видим в теле вызываемой функции, устанавливается при вызове в значение адреса начала объекта и может быть использован для доступа к членам объекта.
В Си++ разрешено описание прототипов функций с формальными параметрами, имеющими значение по умолчанию. Такие параметры должны быть последними в списке при объявлении функции:
int f (int i,int k=5) {
//тело функции
}
Вызвать функцию f() можно, например, так:
f(i,j); //формальный параметр
//i=фактическому i, k=j
f(1); //i=1, k=5
Класс на Си++ может иметь любое количество конструкторов, предназначенных для создания экземпляров класса. Конструктор всегда имеет то же имя, что и класс, в котором он определен, с созданием экземпляра всегда связано явное или неявное выполнение конструктора. Если отсутствует явно описанный конструктор, создается конструктор по умолчанию. Конструктор вызывается компилятором явно при создании объекта и неявно при выполнении оператора new, применяемого к объекту, а также при копировании объекта данного класса.
Конструктор копирования для класса X имеет 1 аргумент типа X и, возможно, параметры по умолчанию, например
class X {
public:
X() {... } //конструктор по умолчанию
X(const &X) {... }
//конструктор копирования
X(const &X,int=4) {... }
//конструктор по умолчанию
//с параметром по умолчанию
}
Конструктор копирования вызывается, когда происходит копирование объекта, обычно при объявлении с инициализацией:
X one; //вызван конструктор по умолчанию
X two=one; //вызван конструктор копирования
Функция‑ деструктор разрушает объект данного класса и вызывается явно или неявно. Неявный вызов деструктора связан с прекращением существования объекта из‑за завершения области его определения. Явное уничтожение объекта выполняет оператор delete. Деструктор имеет то же имя, что класс, но предваренное символом ~. Деструкторы не могут получать аргументы и быть перегружены. Класс может объявить только один общедоступный деструктор. Если класс не содержит объявления деструктора, компилятор автоматически создаст его.
Как и для обычных функций, для членов класса поддерживается "перегрузка", то есть, использование одинаковых имен для функций, отличающихся числом и типом параметров. Функции не могут перегружаться, если они отличаются только типом возвращаемого значения, но не списком параметров, а также, если их типы аргументов неявно совпадают (int и int &).
Функции, не являющиеся членами класса, но объявленные его "друзьями" с помощью ключевого слова friend, имеют полный доступ к данным класса.
Многие операторы и встроенные функциональные вызовы Си++ также могут быть перегружены в пределах контекста класса, где сделано соответствующее определение. При этом приоритет и порядок выполнения операций не меняются. Переопределены могут быть следующие лексемы:
+ - * / = < > += -= *= /= << >> <<= >>= ==!= <= >= ++ -- % & ^! | ~ &= ^=!= && || %= [] () new delete
Смысл перегрузки оператора в том, что создается функция, выполняемая каждый раз, когда в контексте класса встречается этот оператор. Синтаксис определения перегрузки оператора таков:
ИмяТипа operator СимволОперации
(СписокПараметров)
Производный (англ. derived) класс — это расширение существующего класса, именуемого в этом случае базовым. Производный класс может модифицировать права доступа к данным класса, добавить новые члены или перегрузить существующие функции. Описание производного класса делается так:
class ИмяПроизводногоКласса: БазовыйСписок {
СписокЧленов;
}
Здесь БазовыйСписок содержит перечень разделенных запятой спецификаторов атрибутов доступа (public или private) и имен базовых классов.
Производный класс наследует все члены перечисленных базовых классов, но может использовать только члены с атрибутом public или protected.
Эти и другие особенности классов на Си++ рассмотрим на примере. Код ниже представляет класс Person и расширение класса Student, а также демонстрирует создание экземпляров этих классов.
#include <stdio.h>
#include <string.h>
#include <alloc.h>
class Person {
private: //Данные объекта; атрибут,
//применяемый по умолчанию
char *Name;
int Age;
friend Person *upcase (Person *p);
//эта функция - не член класса, но его
//друг - она имеет полный доступ
//к его членам
protected: //Данные и методы могут
//использоваться функциями-членами и
//друзьями класса, для которого данный
//класс является базовым
char *putName (char *name);
public:
//Данные и методы, доступные извне
static int Count;
//Статический член класса –
//один для всех его экземпляров!
Person (): Name (NULL), Age (0) {
//Конструктор без аргументов
//аргументы установлены по умолчанию
Name = NULL;
//Тело конструктора встроено
Count++;
}
Person (char *name, int age);
//Прототип конструктора с аргументами
~Person ();
//У класса есть деструктор,
//освобождающий память, занятую объектом
Person operator + (char *);
//Переопределение оператора +
//для сложения строк –
//действует в этом классе
//на входе - параметр-указатель,
//на выходе - новый объект Person
//Методы класса:
void Print (); //Перегружаемая функция,
Person Print (Person *p);
//т.е. у нас нес-ко функций с 1 именем
//и разными аргументами
void Input ();
inline char * getName () {
return Name; //Встроенная функция
}; //ее код каждый раз подставляется
//в точку вызова
inline int getAge () { return Age; };
};
//Описание производного класса:
class Student: public Person {
//: - оператор наследования
//Класс, порожденный от Person,
//наследует его члены и может
//использовать члены с атрибутом public
protected:
int Group;
public:
Student (char *name=NULL, int age=0,
int group=0):
Group(group),Person(name,age) {}
//Конструктор со значениями аргументов
//по умолчанию и вызовом конструктора
//родительского класса Person
void Print ();
// Метод производного класса
};
int Person::Count=0;
//один раз инициализировали статический
//член вне описания класса!
// Оператор Класс:: показывает, что
//объект относится к классу:
Person:: Person (char *name, int age) {
//Тело конструктора с аргументами
this->Age = age;
//this - указатель на текущий объект
//из метода класса
//неявно передается в любую нестатическую
//функцию класса
this->Name=putName (name);
Count++;
}
Person:: ~Person () {
//Деструктор всегда без аргументов,
//не м.б. перегружен
free (Name);
}
//Служебная функция:
char * Person:: putName (char *name) {
Name = (char *) calloc
(strlen(name),sizeof(char));
if (Name!=NULL) strcpy (Name, name);
return Name;
}
inline void Person:: Print () {
//Эта функция - встроенная в класс
printf ("\n%s (%d)",Name,Age);
}
Person Person:: Print (Person *p) {
printf ("\nOther print: %s, %d",
p->Name, p->Age);
return *p;
}
//Перегрузка оператора
Person Person:: operator + (char *s) {
Person temp; char name[80];
strcpy(name,strcat (this->Name,s));
temp.Name = putName(name);
temp.Age=this->Age;
return temp;
}
void Person:: Input () {
//Создаем объект и возвращаем его
char s[80];
printf ("\nName? ");
scanf ("%s",s);
strcpy (Name,s);
printf ("\nAge? ");
scanf ("%d",&Age);
putName (s);
}
Person *upcase (Person *p) {
//функция-друг класса
strupr (p->Name);
return p;
}
void Student:: Print () {
printf ("\n%s (%d,%d)",
getName(),getAge(),Group);
}
void main () {
Person *First = new Person ();
//new вернет указатель на новый объект
//происходит вызов конструктора
First->Print ();
delete First; //удаляем объект, неявно
//вызвав деструктор
Person *Second = new Person ("Ivanov",20);
Second->Print ();
Person Third; Third.Input ();
upcase (&Third); Third.Print (&Third);
Person Next = Third + ".N";
Next.Print ();
printf ("\nAll: %d",Person::Count);
delete &Next;
Student *Test = new Student ("Newer",
Second->getAge(),319);
Test->Print (); }
Рекомендуемая литература
1. Бочков С.О., Субботин Д.М. Язык программирования Си для персонального компьютера. — М.: "Радио и связь", 1990. — 384 с.
2. Жешке Р. Толковый словарь стандарта языка Си. — Спб.: "Питер", 1994. — 224 с.
3. Керниган Б.В,, Ричи Д.М. Язык C. — М.: "Финансы и статистика", 1992. — 232 с.
4. Страуструп Б. Язык программирования C++ — Спб.: "Невский диалект", 2007. — 1099 с.
