Опорный конспект

//Файл fstack.cpp******************

#include "fstack.h" #include <stdio.h> #include <string.h> #include <iostream> using namespace std;

struct fstack{ char* str; fstack* next;};

fstack *head;

fstack* push(fstack* phead, char* s){ fstack* p= new fstack;

p->str = new char[strlen(s)+1]; strcpy(p->str, s);

p->next = head; head = p; return head;}

char* pop(fstack** pphead){ fstack* p=*pphead; char *s = p->str;

*pphead = (*pphead)->next; delete p;

return s;}

bool read_file(char* fname){ FILE *rf;

if(!(rf = fopen(fname, "r"))) return 0;

head = 0;

char temp[255]; while(fgets(temp, 255, rf))

head = push(head, temp); return 1;}

bool write_file(char* fname){ FILE *wf;

if(!(wf = fopen(fname, "w"))) return 0;

char *temp; while(head) {

temp = pop(&head); fputs(temp, wf); delete[] temp; }

return 1;}

//******************************

Рис. 10.19. Описание функций стека

103

//Файл test.cpp***********

#include <iostream> #include "fstack.h" using namespace std;

int main()

{

char rfile[255], wfile[255]; cout<<"Enter read file name"<<endl; cin.getline(rfile, 255); cout<<"Enter write file name"<<endl; cin.getline(wfile, 255); if(!read_file(rfile))

{

cout<<"Can't open file to read"<<endl; return -1;

}

if(!write_file(wfile))

{

cout<<"Can't open file to write"<<endl; return -1;

}

return 0;

}

//***************************

Рис. 10.20. Работа со стеком

Вся основная работа скрыта внутри модуля. Пользователь вызывает только две функции – чтение файла и запись в файл. Организация данных полностью скрыта от пользователя. В модуле создана структура, позволяющая реализовать стек. Для работы со стеком традиционно используются две функции – push и pop. Стек можно представить в виде колодца. Функция push добавляет элементы в стек, при этом верхний элемент «опускается», так как на него сверху «давит» новый элемент стека. Функция pop удаляет элемент из стека, при этом все оставшиеся элементы «всплывают» на один уровень вверх. При чтении файла используется функция заполнения стека, а при записи нового файла – удаления элемента из стека.

При чтении строк из файла в стек первая прочитанная строка будет помещена в начало стека. После добавления второй строки, первая «опустится» на дно стека, и т.д. Последняя прочитанная строка файла окажется на вершине стека. Во время записи в файл верхушка стека окажется в начале файла, а «дно» стека – в конце, таким образом новый файл будет содержать все строки исходного файла, но записанные в обратном порядке.

104

Очереди

Другой стандартной структурой данных является очередь [1]. Очередь аналогична очереди людей в магазине: первый клиент в ней обслуживается первым, а другие клиенты ожидают своей очереди. Узлы очереди удаляются только из головы очереди, а помещаются в очередь только в ее хвосте. Это структура данных типа FIFO (first in first out – первым вошел - первым вышел).

У очередей имеется множество применений в вычислительных системах. У большинства компьютеров имеется только один процессор, в один и тот же момент времени может быть обслужен только один процесс. Запросы других процессов помещаются в очередь. Каждый запрос постепенно продвигается по очереди вперед по мере того, как происходит обслуживание пользователей. Запрос в начале очереди является очередным кандидатом на обслуживание.

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

Задача. Получить от пользователя строку и распечатать каждое слово на отдельной строке

//Файл queue.h*************************

#ifndef _QUEUE_H_

#define _QUEUE_H_

struct Queue

{

char* str; Queue* next;

};

Queue* Add(char*, Queue*); //добавляем в хвост void Print(Queue*); //печатаем

Queue* Delete(Queue*); //удаляем из головы

#endif

//************************************

Рис. 10.21. Заголовочный файл очереди

105

//Файл queue.cpp*************************

#include "queue.h" #include <iostream> #include <string.h> using namespace std;

Queue* Add(char* s, Queue* phead)

{

Queue* pnew= new Queue; Queue *p = phead; while(p)

{

if(p->next) p=p->next;

else

break;

}

pnew->str = new char [strlen(s)+1]; pnew->next = NULL; strcpy(pnew->str, s);

if(p)

p->next = pnew; if(phead)

return phead; return pnew;

}

void Print(Queue* phead)

{

while(phead)

{

cout<<phead->str<<endl;

phead = phead->next;

}

}

Queue* Delete(Queue *phead)

{

Queue *p; if(phead)

p=phead->next; delete []phead->str; delete phead;

return p;

}

//***********************************

Рис. 10.22. Описание функций создаваемой очереди

106

//Файл test.cpp**********************

#include "queue.h" #include <string.h> #include <iostream> using namespace std;

int main()

{

Queue * head = 0; char stroka[255];

cout<<"Enter a string:\n"; cin.getline(stroke,255); while(strlen(stroka))

{

char raz[] = {' ', '\t', '\0'};

char *s=strtok(stroka, raz); //разбиение строки на слова while(s)

{

head = Add(s, head);

s = strtok(NULL, raz); // продолжение разбиения

}

cout<<"Enter a string:\n"; cin.getline(stroke,255);

}

Print(head);

while(head)

head = Delete(head); return 0;

}

//*******************************************

Рис. 10.23. Основная функция программы

Деревья

Связные списки, стеки и очереди являются линейными структурами данных [1]. Дерево является нелинейной двумерной структурой данных с особыми свойствами. Узлы дерева могут содержать два и более указателей связи. Бинарные деревья содержат по два указателя. Или один из них, или оба могут быть нулевыми. Корневой узел является первым узлом дерева. Каждый указатель связи в корневом узле ссылается на дочерний узел или узел-потомок. Левый узелпотомок является первым узлом в левом поддереве, а правый узел-потомок является первым узлом в правом поддереве. Узлы-потомки, порожденные одним каким-либо узлом, называются родственными узлами (или узлами-братьями). Узел без узлов-потомков называется листом дерева или концевым узлом. Деревья обычно рисуют сверху вниз, начиная с корневого узла, то есть противоположно тому, как растут деревья в природе.

107

Задача. Написать программу, реализующую бинарное дерево поиска для целых чисел [5].

//Файл btree.h**********************

#ifndef _BTREE_H_ #define _BTREE_H_

struct Node

{

int num; Node* Left; Node* Right;

};

struct List

{

Node* elem; List* next;

};

Node* add(Node* root, int a); void print(Node* root, int l); Node* del(Node* root, int a); void post(Node *root);

void in(Node* root); void pre(Node* root);

Node* isonechild(Node* root);

#endif

//*******************************************

Рис. 10.24. Заголовочный файл задачи построения бинарного дерева поиска

//Файл btree.cpp**********************

#include <iostream> #include "btree.h" using namespace std;

Node* add(Node* root, int a){ if(!root) {

Node *pnew = new Node; pnew->num = a; pnew->Left = NULL; pnew->Right = NULL; root = pnew; }

else if(root->num < a)

root->Right = add(root->Right, a);

else

root->Left = add(root->Left, a); return root;}

Рис. 10.25. Добавление элемента в бинарное дерево поиска

108

void print(Node* root, int level){ if(root)

print(root->Right, level+1); for(int i=0; i<level; i++)

cout<<" "; if(root)

cout<<root->num<<" ("<<level<<")\n";

else

cout<<"#\n";

if(root)

print(root->Left, level+1);

}

void replace(Node** elem, int* a){ if((*elem)->Left)

replace(&((*elem)->Left), a); else {

*a = (*elem)->num; Node *p = *elem;

*elem = (*elem)->Right; p->Right = NULL;

delete p;

}

}

Node* delNode(Node* elem){ if(!elem->Left&&!elem->Right)

{

delete elem; return NULL;

}

else if((elem->Left&&!elem->Right)|| (!elem->Left&&elem->Right)) {

Node *p = elem; if(elem->Left) {

elem = elem->Left; p->Left = NULL;

}

else {

elem = elem->Right; p->Right = NULL;

}

delete p; return elem;

}

else {

int a; replace(&(elem->Right), &a); elem->num = a; }

}

Рис. 10.26. Функции работы с бинарным деревом поиска - продолжение

109

Node* del(Node* root, int a){ if(!root) {

cout<<"No such element!"<<endl; return NULL;

}

else if(root->num == a) { root = delNode(root); return root;

}

else if(root->num< a) {

root->Right = del(root->Right, a); return root;

}

else {

root->Left = del(root->Left, a); return root;

}

void pre(Node *root){ if(root) {

cout<<root->num<<" "; pre(root->Left); pre(root->Right); }

}

Node* isonechild(Node* elem){ if(!elem) return 0;

if(elem->Left && elem->Right) return 0; if(elem->Left)

return elem->Left; if(elem->Right)

return elem->Right;}

//*******************************************

Рис. 10.27. Функции работы с бинарным деревом поиска - окончание

110

//Файл test.cpp**********************

#include <stdlib.h> #include <time.h> #include <iostream> #include "btree.h" using namespace std;

int main()

{

Node* root = NULL; srand(time(0));

for(int i = 0; i<10; i++)

{

int a = rand()%101-50; root = add(root, a);

}

print(root,0);

cout<<"\npost\n\n";

post(root);

cout<<"\nin\n\n";

in(root);

cout<<"\npre\n\n";

pre(root); return 0;

}

//*******************************************

Рис. 10.28. Работа с бинарным деревом поиска

111

Тема 11

КЛАССЫ И АБСТРАГИРОВАНИЕ ДАННЫХ

11.1. Определения классов

Классы – это определяемые пользователем типы данных [1]. Каждый класс содержит данные и функции, манипулирующие с этими данными. После определения они могут использоваться наравне со встроенными типами.

Классы предоставляют программисту возможность моделировать объекты, которые имеют атрибуты (данные-элементы) и варианты поведения или операции (функции-элементы). Типы, содержащие данные-элементы и функцииэлементы, обычно определяются в С++ с помощью ключевого слова class.

Функции-элементы иногда в других объектно-ориентированных языках называют методами, они вызываются в ответ на сообщения, посылаемые объекту. Сообщение соответствует вызову функции-элемента.

Когда класс определен, имя класса может быть использовано для объявления объекта этого класса (см. рис. 11.1).

Определение класса Time начинается с ключевого слова class. Тело определения класса заключается в фигурные скобки ({ }). Определение класса заканчивается точкой с запятой. Определение класса Time содержит три целых эле-

мента hour, minute и second.

Метки public: (открытая) и private: (закрытая) называются спецификаторами доступа к элементам. Любые данные-элементы и функции-элементы, объявленные после спецификатора доступа к элементам public: (и до следующего спецификатора доступа к элементам), доступны при любом обращении программы к объекту класса Time. Любые данные-элементы и функцииэлементы, объявленные после спецификатора доступа к элементам private: (и до следующего спецификатора доступа к элементам), доступны только функциям-элементам этого класса. Спецификаторы доступа к элементам всегда заканчиваются двоеточием (:) и могут появляться в определении класса много раз и в любом порядке.

class Time { public:

Time () ;

void setTime (int, int, int); void print24Hours();

void print12Hours(); private:

int hour; // 0-23 int minute; // 0 -59 int second; }; // 0-59

Рис. 11.1. Определение класса Time

Определение класса в программе содержит после спецификатора доступа к элементам public: прототипы следующих четырех функций-элементов:

112