Банк Рефератов - Методы сортировки. Их сравнительный анализ

Рефераты. Методы сортировки. Их сравнительный анализ

Библиотека MFC прямо поддерживает около 140 функций, обрабатывающих Windows-сообщения. Кроме того, можно определять свои собственные сообщения, связанные с обработчиками команд меню, элементов управления и т.д. В программе “Sort” используется более 40 функций, методов и сообщений Windows. Ниже они перечислены в порядке их появления в программе с кратким описанием:

Format – преобразует типы переменных;

InvalidateRect и Invalidate – обновляют рабочую область и генерируют сообщение WM_PAINT;

DestroyWindow – разрушает окно;

PostQuitMessage – посылает окну сообщение WM_DESTROY;

ShowWindow – отображает или скрывает окно;

UpdateWindow – заставляет окно перерисовать своё содержимое;

TextOut – вывод текста на экран;

После вызова функции UpdateWindow, окно окончательно выведено на экран. Теперь программа должна подготовить себя для получения информации от пользователя через клавиатуру и мышь. Windows поддерживает “очередь сообщений” (message queue) для каждой программы, работающей в данный момент в системе Windows. Когда происходит ввод информации, Windows преобразует её в “сообщение”, которое помещается в очередь сообщений программы. Каждое получаемое окном сообщение идентифицируется номером, который содержится в параметре message оконной процедуры. В заголовочных файлах Windows определены идентификаторы, начинающиеся с префикса WM (“window message”) для каждого типа сообщений. Ниже приведены все сообщения используемые в курсовом проекте:

Сообщение WM_CREATE – это первое сообщение, которое Windows посылает объекту View. Оно передаётся, когда каркас приложения вызывает оконную функцию Create, т.е. в тот момент, когда создание окна ещё не закончено и его не видно на экране. Следовательно, обработчик OnCreate пока не может обращаться к Windows-функциям, доступным только после отображения окна. Такие функции можно вызвать из замещённой функции OnInitialUpdate.

Функция-член OnDraw(). Это виртуальная функция-член класса CView; каркас приложений вызывает её всякий раз, когда приходит сообщение о том, что нужно перерисовать окно отображения. А такая необходимость возникает при масштабировании окна или при появлении ранее скрытой его части, или при изменении программой данных, связанных с этим окном. В первых двух случаях каркас приложения вызывает OnDraw, но если какая-то функция в программе изменяет данные, она должна уведомить об этом Windows, вызвав наследуемую функцию-член Invalidate (или InvalidateRect) для данной области отображения. Вызов Invalidate приводит впоследствии к автоматическому вызову OnDraw.

Windows не разрешает прямой доступ к видеооборудованию, обращение к нему проходит через так называемый контекст устройства (device context), сопоставленный с конкретным окном. В библиотеке MFC контекст устройства – это С++-объект класса CDC, передаваемый функции OnDraw (по указателю) как параметр. Получив указатель на контекст устройства, можно вызывать множество функций-членов CDC, которые и выполняют всю работу по рисованию.

В данном курсовом проекте при вызове функции OnDraw происходит вывод исходного и отсортированного массива на экран, а также информации о количестве перестановок произведённых во время сортировки.

Когда пользователь выбирает пункт меню, Windows посылает программе сообщение WM_COMMAND, содержащее идентификатор этого пункта меню в младшем слове параметра сообщения. Ниже рассмотрены идентификаторы, соответствующее пунктам меню программы:

ID_QUIK – это идентификатор пункта “ Обменная сортировка с разделением (quicksort)” в меню. Выбор этого пункта приводит к сортировке массива данным методом.

ID_SHELL – это идентификатор пункта “Метод Шелла” в меню. Выбор этого пункта приводит к сортировке массива методом Шелла.

ID_PUZIROK – этому идентификатору в меню соответствует пункт “Метод прямого обмена (Пузырька)”. Выбор этого пункта приводит к сортировке массива методом “Пузырька”.

Выбор пункта меню “О программе…”, которому соответствует идентификатор ID_APP_ABOUT, выведет модальное окно диалога, в котором содержится краткая информация о разработчике и программе.

ID_APP_EXIT – этому идентификатору в меню соответствует пункт “Выход”. При выборе этого пункта происходит вызов функции OnDestroy, что приводит к разрушению окна и завершению работы с программой.

3 ИНСТРУКЦИЯ ПОЛЬЗОВАТЕЛЯ

Запуск программы осуществляется при открытии файла Sort.exe, который находится на дискете. При этом на экране появиться окно, в левой верхней части которого будет видна надпись “Методы сортировки” – это имя программы. Ниже располагается меню, с помощью которого можно выполнить различные действия с данным приложением. При нажатии на пункте меню “Файл”, выпадет, так называемое, всплывающее меню, в котором находится пункт “Выход”. При выборе этого пункта программа закрывается.

Следующий пункт главного меню – это “Сортировка”, подменю которого содержит пункты “Обменная сортировка с разделением (quicksort)”, “Метод Шелла” и “Метод прямого обмена (Пузырька)”. Выбор первого пункта позволяет произвести сортировку массива методом “Обменной сортировки с разделением”. Нажатие на пункте меню “Метод Шелла” приводит к сортировке массива методом Шелла. И выбор последнего подпункта меню сортирует массив методом “Пузырька”.

Последним пунктом меню является “Помощь”. Если выбрать этот пункт, то в подменю можно увидеть пункт: “О программе”, который содержит информацию о разработчике и о самой программе.

Под меню располагается панель инструментов, которая дублирует все пункты основного меню. Ещё ниже расположена клиентская область, в которой происходит весь вывод информации.

Системные требования: Pentium 133, 16 MB RAM, Windows 95/98/2000 NT/XP.

ЗАКЛЮЧЕНИЕ

В ходе выполнения данного курсового проекта были разработана программа на языке высокого уровня Visual C++. А также изучены возможности данного языка.

Систематизированы и закреплены практические навыки использования ЭВМ, программного обеспечения, существующих средств обслуживания системных программистов, а также теоретические знания по основным разделам курса "Объектно-ориентированного программирования". Основное внимание уделено изучению современных методов защиты информации, способов проектирования приложений, объектно-ориентированному и системному программированию.

При выполнении курсового проекта произведено знакомство с реферативными журналами и другими информационными источниками по объектно-ориентированному и системному программированию с целью анализа состояния решаемой задачи.

Получены практические навыки работы в среде Visual C++.

ПРИЛОЖЕНИЕ

#include "stdafx.h"

#include "Sort.h"

#include "SortDoc.h"

#include "SortView.h"

#ifdef _DEBUG

#define new DEBUG_NEW

#undef THIS_FILE

static char THIS_FILE[] = __FILE__;

#endif

//объявление глобальных переменных

int mas[20]={30,5,17,8,1,14,12,3,77,2,45,89,33,21,6}, mas2[20], kol=15, count=0;

CString str;

bool sort=false;

int metod=0;

//1- quicksort

//2- shell

//3- пузырька

/////////////////////////////////////////////////////////////////////////////

// CSortView

IMPLEMENT_DYNCREATE(CSortView, CView)

BEGIN_MESSAGE_MAP(CSortView, CView)

//{{AFX_MSG_MAP(CSortView)

ON_COMMAND(ID_QUICK, OnQuick)

ON_COMMAND(ID_PUZIROK, OnPuzirok)

ON_COMMAND(ID_SHELL, OnShell)

//}}AFX_MSG_MAP

END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////

// CSortView construction/destruction

CSortView::CSortView()

{

// TODO: add construction code here

}

CSortView::~CSortView()

{

}

BOOL CSortView::PreCreateWindow(CREATESTRUCT& cs)

{

// TODO: Modify the Window class or styles here by modifying

// the CREATESTRUCT cs

return CView::PreCreateWindow(cs);

}

/////////////////////////////////////////////////////////////////////////////

// CSortView drawing

//функция вывода данных на экран

void CSortView::OnDraw(CDC* pDC)

{

CSortDoc* pDoc = GetDocument();

ASSERT_VALID(pDoc);

// TODO: add draw code for native data here

int i;

//выводим исходный массив на экран

for(i=0;i<kol;i++)

{

str.Format("%d,",mas[i]);//формирование строки

pDC->TextOut(10+i*20,10,str);//вывод на экран

}

//если был выбран какой-нибудь метод сортировки

if(sort)

{

if(metod==1)//если выбран Quicksort

pDC->TextOut(10,40,"Обменная сортировка с разделением (quicksort)");//вывод строки на экран

if(metod==2)//если выбран Shell

pDC->TextOut(10,40,"Метод Шелла");//вывод строки на экран

if(metod==3)//если выбран Bubble

pDC->TextOut(10,40,"Метод прямого обмена (Пузырька)");//вывод строки на экран

//выводим отсортированный массив

for(i=0;i<kol;i++)

{

str.Format("%d,",mas2[i]);//формирование строки

pDC->TextOut(10+i*20,80,str);//вывод строки на экран

}

str.Format("Количество перестановок в нашем случае: %d",count);//формирование строки

pDC->TextOut(10,110,str);//вывод строки на экран

if(metod==3)//если был выбран метод "Пузырька"

{

str.Format("Максимальное количество перестановок для массива из %d элементов методом 'Пузырька': %d",kol, kol*(kol-1)/2);//формирование строки

pDC->TextOut(10,140,str);//вывод строки на экран

}

/////////////////////////////////////////////////////////////////////////////

// CSortView diagnostics

#ifdef _DEBUG

void CSortView::AssertValid() const

{

CView::AssertValid();

}

void CSortView::Dump(CDumpContext& dc) const

{

CView::Dump(dc);

}

CSortDoc* CSortView::GetDocument() // non-debug version is inline

{

ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CSortDoc)));

return (CSortDoc*)m_pDocument;

}

#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////

// CSortView message handlers

//при выборе сортировки Quicksort

void CSortView::OnQuick()

{

//объявление локальных переменных

sort=true;

metod=1;

int i;

count=0;

for(i=0;i<kol;i++)

{

mas2[i]=mas[i];

}

quicksort(0, kol-1);//вызов функции quicksort

Invalidate(true);//перерисовка содержимого окна

}

//при выборе сортировки Shell

void CSortView::OnShell()

{

//объявление локальных переменных

sort=true;

metod=2;

int ii,t=5,i,j, k, s, m, h[6], x;

count=0;

for(ii=0;ii<kol;ii++)

{

mas2[ii]=mas[ii];

}

h[1]=9; h[2]=5; h[3]=3; h[4]=2; h[5]=1;

////////////////////////////////////////////

//АЛГОРИТМ

for(m=1;m<=t;m++)

{

k=h[m];

s=-k;

for(i=k+1; i<=kol;i++)

{

x=mas2[i];

j=i-k;

while (x<mas2[j] && j<kol)

{

mas2[j+k]=mas2[j];

j=j-k;

}

mas2[j+k]=x;

count++;

}

x=mas2[0];

mas2[0]=mas2[1];

mas2[1]=x;

////////////////////////////////////////////

Invalidate(true);//перерисовка содержимого окна

}

//при выборе сортировки Bubble

void CSortView::OnPuzirok()

{

//объявление локальных переменных

int dop;

bool end;

count=0;

sort=true;

metod=3;

int i, j;

for(i=0;i<kol;i++)

{

mas2[i]=mas[i];

}

////////////////////////////////////////////

//АЛГОРИТМ

for(i=0;i<kol;i++)

{

end=true;

for(j=i+1;j<kol;j++)

{

if(mas2[i]>mas2[j])

{

dop=mas2[i];

mas2[i]=mas2[j];

mas2[j]=dop;

end=false;

count++;

}

if(end==true) break;

}

/////////////////////////////////////////////

Invalidate(true);//перерисовка содержимого окна

}

//функция быстрого поиска

void CSortView::quicksort(int l, int r)

{

int i, j;

i=l;j=r;

{

part(l, r, i, j);

if(i<r)quicksort(i, r);// переход к сортировке левой части

if(j>l)quicksort(l, j);// переход к сортировке правой части

}

//функция поиска по частям

void CSortView::part(int l, int r, int &i, int &j)

{

int x, dop;

i=l;

j=r;

x=(l+r)/2;

{

while(mas2[i]<mas2[x])

i++;

while(mas2[j]>mas2[x])

j--;

if(i<=j)

{

dop=mas2[i];

mas2[i]=mas2[j];

mas2[j]=dop;

i++;j--;count++;

}

while(i<j);

}

Литература

1. Петзольд Ч. Программирование под Windows 95. В двух книгах: BHV – Санкт - Петербург, 1997, silt.

2. Ричард С.Линкер, Том Арчер. Программирование для Windows 98. Библия разработчика. “Диалектика ” – Москва, 1999.-864 с.: ил.- Парал. тит. англ. Уч.пос.

3. Джесс Либерти. С++ за 21 день. ”Вильямс” - Москва, 2000.-816 с.: ил. - Парал.тит. англ.

4. Дэвид Дж. Круглински. Основы С++. “Русская редакция” – Москва, 1997.- 696 с.: ил.

5. Кэйт Грегори. Использование Visual C++. “Вильямс” – Москва, 1999.-864 с.: ил.. - Парал.тит. англ., уч. пос.

7. Конспект лекций.

Страницы: 1, 2, 3