- •2. Разработка программ с графическим интерфейсом пользователя с помощью mfc, но без AppWizard.
- •4. Класс двунаправленного списка.
- •5. Алгоритм поиска. Хеширование. Класс хеш-таблицы.
- •Хеширование
- •7. Параметризированная функция бинарного поиска в массиве.
- •8. Кодування символів, алгоритм Хаффмана.
- •6. Построение класса параметризованного ограниченного массива.
- •3. Построение параметризованного класса очереди.
- •9. Збалансовані дерева. Включення в збалансоване дерево. Два випадки балансування.
1.Основные принципы объектно–ориентированного программирования и их воплощение в языке С++.
Объектно-ориентированное программирование (ООП) — парадигма программирования, основанная на представлении предметной области в виде системы взаимосвязанных абстрактных объектов и их реализаций. Каждый объект в ООП имеет свой тип (класс). Класс представляет собой тип данных, имеющий в составе свойства (параметры объекта), методы (действия, которые можно выполнять над объектом такого типа, или которые сам объект может выполнять) и события (сообщения, рассылаемые объектом подписчикам, т.е. различным элементам программ, при определённом изменении состояния объекта).
Важнейшие принципы ООП – абстракция данных, наследование, полиморфизм, инкапсуляция.
Абстракция данных предполагает, что объекты представляют собою не полную информацию о реальных сущностях предметной области, а их модели, адекватные решаемой задаче, работать с которыми намного удобнее, чем с полным описанием всех возможных свойств и реакций объекта. Объекты имеют очень простое внешнее поведение: единственное что доступно для пользователя объекта — это возможность послать ему сообщение и получить ответ на него.
Наследованием называется возможность порождать один класс от другого с сохранением всех свойств и методов класса-предка (иногда его называют суперклассом). Наследование призвано отобразить такое свойство реального мира, как иерархичность.
Полиморфизмом называется способность класса-потомка изменять своё поведение, т. е. существующие у класса-предка методы.
Инкапсуляция — это принцип, согласно которому поведение любого класса должно рассматриваться как чёрный ящик — пользователь класса должен видеть и использовать только его интерфейс (от английского interface — внешнее лицо, т. е. список декларируемых свойств и методов) класса и не вникать в его внутреннюю реализацию. Этот принцип (теоретически) позволяет минимизировать число связей между классами и соответственно упростить реализацию. В простейшем случае объявление класса имеет следующий формат:
class имя { тип1 переменная1 тип2 переменная2 public: функция1; функция2; } ;
Основное отличие класса от структур состоит в том, что все члены класса по умолчанию считаются закрытыми и доступ к ним могут получить только функции — члены этого же класса. Однако режим доступа к элементам класса может быть изменен путем его явного указания. Для этого перед элементами класса записывается соответствующий спецификатор доступа. Существуют три таких спецификатора:
private (частный);
public (общедоступный);
protected (защищенный).
//В программе объявлен класс простых дробей, описана переменная этого класса, выполнена обработка переменной
#include <iostream.h>
#include <math.h>
struct Frac{int P; int Q;};
Frac F;
//Объявление класса
class Drob{
Frac A;
public:
void Vvod(void);
int NOD(void);
void Sokr(void);
void Stepen(int N);
void Print(void);};
//Описания функций — членов класса
2. Разработка программ с графическим интерфейсом пользователя с помощью mfc, но без AppWizard.
Поскольку Windows является ОС, в значительной степени ориентированной на работу с мышью, все программы для Windows должны определенным образом реагировать на действия мыши. Учитывая возможность этого момента, в Windows имеется несколько типов сообщений мыши. В ниже описанном примере рассматривается 2 наиболее общих из них – OnLButtonDown, OnRButtonDown. Их прототипы afx_msg void OnLButtonDown(UINT flags,CPoint loc); afx_msg void OnRButtonDown(UINT flags,CPoint loc);
Значение flags указывает на то, использовались ли клавиши CTRL,SHIFT или другая кнопка мыши. Параметр loc содержит координаты в момент нажатия кнопки.
Шаг 1 – file/new – проект типа Win32 Application .. выбираем имя проекта
Шаг 2 – добавляем файл CMainWin.cpp и Message.h
//Message.h // это класс для создания главного окна
class CmainWin : public CFrameWnd
{ CMainWin();
afx_msg void OnChar(UINT ch,UINT count,UINT flags);
afx_msg void OnPaint();
afx_msg void OnLButtonDown(UINT flags,CPoint loc);
afx_msg void OnRButtonDown(UINT flags,CPoint loc);
DECLARE_MESSAGE_MAP() };
// это класс для создания приложения
class Capp : public CwinApp {
public:BOOL InitInstance(); };
#include <afxwin.h>
#include <string.h>
#include “message.h”
char str[80] = “Simple output”; // строка для вывода
CMainWin::CMainWin()
{ Create(NULL,”Processing Mouse Messages”);}
//инициализация приложения
BOOL CApp::InitInstance()
{ m_pMainWnd = new CMainWin;
m_pMainWnd->ShowWindow(m_nCmdShow);
m_pMainWnd->UpdateWindow();
return TRUE; }
//это очередь сообщений приложения
BEGIN_MESSAGE_MAP(CMainWin,CframeWnd)
ON_WM_CHAR()
ON_WM_PAINT()
ON_WM_LBUTTONDOWN()
ON_WM_RBUTTONDOWN()
END_MESSAGE_MAP()
// обработка сообщения приложения WM_CHAR
afx_msg void CMainWin::OnChar(UINT ch, UINT count, UINT flags)
{ CclientDC dc(this);
dc.TextOut(1,1,” ”,3); // стирает предыдущий символ
wsprintf(str,”%c”,ch);
dc.TextOut(1,1,str,strlen(str)); }
//обработка сообщения WM_PAINT
afx_msg void CMainWin::OnPaint()
{ CpaintDC dc(this); // для отображения последнего введенного символа
dc.TextOut(1,1,str,strlen(str)); }
//обработка нажатия левой кнопки мыши
afx_msg void CMainWin::OnLButtonDown(UINT flags,CPoint loc)
{ CClientDC dc(this);
wsprintf(str,”Left button is down.”);
dc.TextOut(loc.x,loc.y,str,strlen(str)); }
// обработка нажатия правой кнопки мыши
afx_msg void CMainWin::OnRButtonDown(UINT flags,CPoint loc)
{ CClientDC dc(this);
wsprintf(str,”Right button is down.”);
dc.TextOut(loc.x,loc.y,str,strlen(str)); }
CApp App; // Создание экземпляра приложения
4. Класс двунаправленного списка.
Имеется набор связанных между собой узлов. Помимо ссылки на след. узел, есть ссылка на предыдущий.
Двунаправленные списки позволяют осуществить движение в обоих направлениях по цепи. Деревья представляют собой более сложные структуры, в которых один узел может содержать ссылки на два или три следующих узла.
#include "iostream.h" class list
{ private: int data;
list * prev; list * next;
public: static list * first;
static list * current;
static void ins(int a);
static int del();
static void clear();};
list * list::first=NULL;
list * list::current=NULL;
//вставка после текущего элемента
void list::ins(int a)
{ list * newnode;
newnode=new list;
newnode->data=a;
if(current!=NULL)
{ newnode->next=current->next;
current->next=newnode; }
Else newnode->next=NULL;
newnode->prev=current;
if(newnode->next!=NULL) newnode->next-> prev=newnode;
current=newnode;
if(first==NULL)first=current;}
int list::del()
{ list * prevnode;
int result;
if(current==NULL)return -1;
result=current->data;
prevnode=current->prev;
if(prevnode!=NULL) prevnode->next=current->next;
if(current->next!=NULL) current->next-> prev=prevnode;
if(current==first)first=current->next;
delete current;
current=prevnode;
if((current==NULL)&&(first!=NULL))current=first;
return result;}
void list::clear()
{ while(first!=NULL)del(); }
void main()
{ list l;
l.ins(1);
l.ins(2);
l.ins(3);
cout<<l.del()<<endl;
l.current=l.first;
cout<<l.del()<<endl;
cout<<l.del()<<endl;
cout<<l.del()<<endl; }