1) Определение элементов связанного списка

struct Listp{int elem; int*beg;};

2) Удаление элемента х из списка

void Delete(int x, Listp **beg)

{ Listp *p, *q = *beg;

while(q->elem != x) {

if(q->next==NULL)return1; // элемент не найден

p=q; // сохранение текущего адреса

q=q->next; // фиксация адреса следующего элемента

}

/* если элемент найден */

if(q== *beg) // найденный элемент – первый в списке

*beg = *beg -> next;

elseif(q->next==NULL) // найденный элемент = последний в списке

p -> next = NULL;

elsep->next=q->next; // найденный элемент не первый и не последний

delete p;

}

3. Добавление элемента х в конец списка

void Insert(int x1, Listp *beg)

{ Listp *p, *q = beg;

p=newListp; // создание нового элемента списка в динамической памяти

p->elem=x1; // инициализация элемента списка

p -> next = NULL;

while (q -> next != NULL)q=q->next; // движение по списку

q->next=p; // связывание нового элемента с последним элементом

}

4. Добавление элемента х в позицию к списка

void Insert(int x1, int k, Listp *beg)

{ Listp *p = new Listp;

p -> elem = x;

for(i = 1; i < k-1; i++) q = q -> next;

p -> next = q -> next;

q -> next = p; }

5. Определение номера позиции элемента х в списке

int Locate(int x1, Listp *beg)

{ Listp *q = beg; k = 1;

while(q -> next != NULL)

{ if(q->elem==x1)returnk+1; // элемент найден; возврат номера позиции

else { q = q -> next; k++; }

} returnk++;

}

12. Основные положения технологии классов

Описание класса

Синтаксис описания класса имеет следующий вид:

classимя_класса{

private:

закрытые элементы (функции и данные)

protected:

защищенные элементы

public:

открытые элементы

};

Закрытые элементы имеют наибольшую защиту от модификации. Доступ к ним и модификация разрешена только функциям-элементам данного класса и дружественным функциям. Доступ к ним из внешних функций и функций производных классов запрещен.

Защищенныеэлементы доступны функциям-элементам данного класса, производного от него класса и дружественным функциям.

Закрытые и защищенные элементы класса образуют реализациюкласса.

Открытые элементы доступны в пределах всей программы и образуютинтерфейскласса.

Пример:

classmyclass

{ private: int a; //закрытый элемент

public: void set_a(int num){a = num;} //объявление открытых

intget_a(); //функций-элементов

};

Определение функций-элементов может осуществляться вне класса, но обязательно с указанием принадлежности к классу с помощью знака расширения области видимости «::».

Например:

int myclass::get_a() { return a; }

Ключевое слово voidозначает, что функцияset_aне возвращает результат в точку вызова.

Доступ к элементам класса (объекта)

Доступ к элементам класса может быть осуществлен из функций-элементов непосредственно, а из внешних функций – к открытым элементам через представителя класса (объект) с помощью операции «.» (точка). Если при создании объекта объявлен указатель на него, то доступ к открытым элементам из внешних функций осуществляется через имя указателя и операцию «→» (стрелка). Если разрешен доступ непосредственно к элементу класса, минуя объект (открытые статические элементы), то доступ осуществляется указанием имени класса и операции «::» (для статических данных).

Доступ из внешних функций зависит от статуса элементов:

а) к открытым элементам – через объект класса, например, ob1.a= 6 (как в структурах);

б) к закрытым и защищенным элементам – с помощью специальных интерфейсных (открытых) функций (модификатор или селектор), например,

ob1.seta(6); // модификация компонентной переменной а

или

cout<<ob1.geta(); // чтение и отображение на экране значения

// компонентной переменной а.

Пример:

classTime

{ public: static int a;

int hour;

int min;

};

int Time::a=0;

intmain() // функцияmainявляется внешней по отношению к классу

{ Тimestart; // создание локального объектаstart

Тime*pTime= &start; // объявление указателя на объектstart

start.hour= 17; // доступ к элементу через объект класса

pТime→min= 30; // доступ к элементу через указатель на объект

Time::a=5; // доступ к элементу непосредственно

return0;

}

Встраиваемые функции-элементы

Если определение функции помещено в описание класса, то такая функция-элемент является встраиваемой.

Для встраиваемой функции компилятор генерирует ее код в точке вызова. Это сокращает время выполнения программы, но увеличивает объем программы.

Если определение функции помещено вне описания класса, то Функция-элемент не является встроенной . Машинный код такой функции транслятором генерируется однократно, а привязка кода к точке вызова (вызывающему объекту) осуществляется с помощью указателя this (передачей адреса) во время выполнения программы (позднее связывание).

Если определение функции-элемента расположено вне класса, то ей можно установить статус встроенной с помощью ключевого слова inline в ее описании в классе,например:

classA

{ public: inline void func();

};

void A::func() {тело функции}

Создание экземпляров класса. Конструктор

Экземпляры класса создаются с помощью специальной компонентной функции класса – конструктора.

Конструктор представляет собой специальную функцию-элемент, которая имеет имя, идентичное имени класса, объявляется без типа возвращаемого значения (ничего не возвращает в точку вызова и поэтому не имеет оператора return) и этим формально отличается от обычных функций. Если конструктор не определен в классе, то компилятор генерирует конструктор по умолчанию без параметров. Конструктор вызывается всегда, когда создается новый объект.

В теле конструктора могут быть любые операторы, в том числе и вызовы функций. Конструктор не наследуется, не может быть объявлен с атрибутами const,volatileилиstaticи не может быть объявлен как виртуальный.

Конструктор с параметрами позволяет инициализировать объект путем присваивания элементам-данным начальных значений.

Явно определенный в классе конструктор может быть с параметрами и без параметров. Определение конструктора имеет вид:

имя_класса( список_параметров ) { тело }

имя_класса() { тело }.

В первом случае значениями параметров в теле конструктора инициализируются элементы-данные класса. Во втором случае инициализация осуществляется значениями, заданными в теле конструктора. Если конструктор генерируется по умолчанию, то инициализация осуществляется нулевыми значениями.

При явном определении конструктора элементы-данные могут инициализироваться двумя способами:

- индивидуальным присвоением значений компонентным данным в теле конструктора;

- использованием списка инициализации данных в заголовке конструктора

Пример:

а) class Time

{ int hr, min;

public: Time (int h) {hr = h; min = 0;} // 1 - й способ

Time (int h, int m): hr(h), min(m){} // 2 – й способ

};

void main(){

Time start1(17);

Time start(17,45);

}

б) class Time { // комбинация двух способов

int min; const int hr;

public:

Time (int h, int m): hr(h) {min = m;}

};

Список инициализации является единственным средством присвоения значений элементам-данным класса, объявленным как constили как ссылки.

Для вызова конструктораиспользуется следующие синтаксические формы:

имя_класса имя_объекта;

имя_класса имя_объекта(аргументы);

имя_класса(аргументы);

Первая форма используется для вызова стандартного конструктора (по умолчанию). Вторая форма используется для конструктора с параметрами. Третья форма используется для создания и инициализации объекта без имени, когда необходимо инициализировать вновь создаваемый объект значениями другого объекта (без имени) с помощью операции присваивания или когда имя объекта не используется в последующем контексте программы. Именно такая форма используется при создании объекта в динамической памяти.

Пример:

myclass ob1;

myclassob1(4);

myclassob1 =myclass(4); //автоматически вызывается конструктор копии.

Создание объекта в динамической памяти

Обращение к динамической памяти осуществляется в ходе выполнения программы с помощью операции new. Операцияnewвыделяет в динамической памяти фрагмент, размер которого определяется типом, заданным в операцииnew. Синтаксис операцииnew:

newтип;

В точку вызова она возвращает адрес выделенного фрагмента. Если тип это имя класса, то операция newвозвращает адрес объекта.

Пример:

Timeob=newTime(17,45); // вызов конструктора в третьей форме

Уничтожение объектов класса. Деструктор

При создании объекта ему выделяется память в стеке. Деструктор вызывается автоматически для удаления объекта и возвращения системе занимаемой им фрагмента памяти. Локальные объекты удаляются тогда, когда выходят из области видимости (при выходе из блока). Глобальные объекты удаляются при завершении программы.

Имя деструктора совпадает с именем класса, но с символом ~ (тильда) в начале.

Свойства деструктора:

- не имеет параметров;

- не возвращает значений;

- не наследуется;

- не может быть объявлен с атрибутами static,constилиvolatile.

Пример:

class B{

inta; // закрытый элемент

public:B(); // конструктор

~B(); // деструктор

void show();

};

B::B() {cout<< ”содержимое конструктора\n”);a= 10;}

B::~B() {cout<< ”удаление объекта\n”;}

void B::show() {cout << a << ”\n”;}

int main()

{ Bob; // вызов конструктора

ob.show();

return0;

}

Простое наследование

При простом наследовании производный класс наследует один предшествующий ему по иерархии базовый или промежуточный базовый класс.

Синтаксис описания производного класса при простом наследовании:

class имя_производного_класса: ключ_доступа имя_базового_класса { };

Пример:

class A { private: int a;

public: A (int b) {a = b;} // Конструктор

};

class B: public A

{ private: int c, d;

public:B(inti,intj):A(j) {с =i;d=j; } // Конструктору предшествующего базового

// класса передается параметр j

// (используется список инициализации )

}; Bob(10,15);

В результате инициализации глобального объекта obего элементы-данные будут иметь значения:

а = 15; c= 10;d= 15.

Если при создании объектов осуществляется инициализация компонентных данных (конструкторы с параметрами), то при создании производного класса должна быть предусмотрена последовательная передача всех аргументов всем инициализирующим конструкторам. При этом в конструкторе производного класса обеспечивается передача все параметров конструктору наследуемого класса, который в свою очередь передает параметры далее вверх по схеме наследования.

Множественное наследование

При множественном наследовании производный класс наследует несколько базовых классов.

Пример:

class A { int a; public: A(int i){ a=i; } };

classB {int b; public: B(int j){ b=j; }};

class C: public A, public B {int c; public: C(int i, int j, int k): A(i),B(j) {c=k;} };

В данном примере конструктор производного класса передает параметры конструкторам всех наследуемых классов.

Передача параметров:

CAB;

Вызов конструкторов:

A( )B( )C( )

Вызов деструкторов:

~C( )~B( )~A( )

12. Реализация АТД «Стек» на основе связанного списка и технологии классов

сlass stack{ int elem; stack * next;

public: static stack * beg; static int n;

static void push_back(int x) {

stack *ob=new stack; ob->elem=x;

if(beg==NULL) ob->next=NULL;

else ob->next=beg;

beg=ob;n++;}

int Top(){return beg->elem;}

static void Pop(){ stack *p=beg; beg=beg->next;

delete p;}

int getElem();

stack * getNext();

};

stack *stack::beg=NULL;

int stack::n=0;

int stack::getElem(){return this->elem;}

stack * stack::getNext(){return this->next;

//--------------------------------------------------------------------------

// вставить

//---------------------------------------------------------------------------

void __fastcall TForm1::Button1Click(TObject *Sender)

{ int x=StrToInt(Edit1->Text);

stack::push_back(x);

Edit3->Text=IntToStr(stack::n);

}

//--------------------------------------------------------------------------

// отобразить

//---------------------------------------------------------------------------

void __fastcall TForm1::Button2Click(TObject *Sender)

{ stack *q= stack::beg; AnsiString st="";

while(q!=NULL){

st+=AnsiString(q->elem)+" ";

q=q->next;}

Edit2->Text=st;

}