Алгоритмы сортировки и поиска

Лабораторная работа №8

 

Алгоритмы сортировки и поиска

 

 

1. Цель работы: разработать приложение для решения задач сортировки числовых массивов и поиска элементов в них, используя язык программирования С++.

 

2. Пример выполнения лабораторной  работы.

Задание: разработать программный продукт, в котором реализованы следующие функции:

• генерация массива целых чисел, сохранение его в элементе управления ListBox,  размерность массива задает пользователь в элементе управления EditBox (до 100 элементов);
• сортировка массива методом пузырька с заданием пользователем способа упорядочивания с помощью элементов управления Radio Button;
• поиск элементов массива с указанным пользователем значением с помощью алгоритма линейного поиска.

 

1) В среде Microsoft Developer Studio (Visual C++)создаем проект на основе диалога.

2. После генерации всех файлов вам будет показана заготовка будущей программы. Рядом будет отображена панель инструмента для создания интерфейса пользователя с программой. Нужно разместить необходимые элементы управления в окне приложения, при необходимости удалив уже имеющиеся по умолчанию кнопки и текстовый элемент. Вариант размещения необходимых элементов управления представлен на рисунке 1.

На окне приложения в левой части размещены три группы элементов, каждая из которых заключена в элемент управления Group Box, изображаемый рамкой:

• для генерации массива: Edit Box (целочисленная переменная m_n), текстовая подпись (элемент Static Text) и кнопка для вызова соответствующей функции OnButton1();
• для сортировки: два элемента Radio Button и кнопка для вызова функции OnButton2().

Для создания переменной для элементов Radio Button нужно обязательно размещать их в элементе управления Group Box и в первом созданном элементе Radio Buttonв разделе Properties (вызываем нажатием правой клавиши манипулятора мышь) необходимо установить флажок Group, как показано на рисунке 2. Этот флажок обеспечит возможность выбора только одной альтернативы из двух элементов Radio Button, расположенных внутри одного элемента управления Group Box. Все переключатели Radio Button должны быть созданы  в Group Box последовательно (без перемежения с созданием других элементов управления).

Для кнопки «Сортировать» в свойствах «Properties» установлен флаг «Disabled» для невозможности ее нажатия до генерации файла (рисунок 3).

 

Рисунок 1 –  Интерфейс приложения

 

Рисунок 2 –  Свойства элемента управления Radio Button

 

 

Рисунок 3 –  Свойства кнопки

 

• для поиска: Edit Box (целочисленная переменная m_х), текстовая подпись (элемент Static Text) и кнопка для вызова соответствующей функции OnButton3(). Для кнопки «Искать» в свойствах «Properties» установлен флаг «Disabled» для невозможности ее нажатия до генерации файла (рисунок 3).

Активизация кнопок «Сортировать» и «Искать» будет осуществлена программно после генерации массива.

В правой части интерфейсного окна размещен элемент управления List Box для вывода массива чисел на экран (переменная m_list).

3)  Создаем для элементов управления переменные, результат приведен на рисунке 4.

Переменные для кнопок требуются, чтобы делать их активными или пассивными в процессе работы программы.

4) Создадим указатель на целочисленный массив в файле Имя_проектаDlg.h в разделе public класса разрабатываемого приложения (рисунок 5). Добавим инициализацию указателя mas в функцию OnInitDialog() в файле Имя_проектаDlg.cpp:

5) Создадим функцию проверки вводимых пользователем данных в поле m_n. Для этого используем событие EN_KILLFOCUS, возникающее при потере фокуса элементом Edit Box, связанного с переменной m_n (рисунок 6).

Также создадим функции, вызываемые при нажатии на кнопки генерации массива, сортировки, поиска элементов и выхода из программы (бывшая кнопка «ОК»).

 

Рисунок 4 – Результат объявления переменных

 

Рисунок 5 – Объявление указателя на массив

 

Рисунок 6 – Объявление функции для события EN_KILLFOCUS

 

7) В файл Имя_проектаDlg.cpp подключим библиотеки для работы с псевдослучайными числами:

#include "time.h"

#include "stdlib.h"

 

8) Добавим программный код в созданные с помощью мастера Class Wizard функции.

 

void CLara8Dlg::OnKillfocusEdit1() // потеря фокуса для Edit Box1

{ UpdateData(1);

if (m_n<1) // проверка введенных пользователем данных

{AfxMessageBox ("Размерность  массива не корректна!");

m_button2.EnableWindow(FALSE);

//кнопку "Сортировать" делаем неактивной

m_button3.EnableWindow(FALSE);

//кнопку "Искать" делаем неактивной

m_list.ResetContent();

return;

}

}

 

void CLara8Dlg::OnButton1() //генерация массива

{ UpdateData(1);

 

mas = new int [m_n];

m_list.ResetContent();

srand(UINT(time(NULL)));

 

CString s;

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

{mas[i] = rand();

s.Format("%i", mas[i]);

m_list.InsertString(i,s);

}

 

m_button2.EnableWindow(TRUE);

//кнопку "Сортировать" делаем активной

m_button3.EnableWindow(TRUE);

//кнопку "Искать" делаем активной

m_order=TRUE;

//устанавливаем точку в RADIO BUTTON "по убыванию"

UpdateData(0);

}

 

void CLara8Dlg::OnButton2() //пузырьковая сортировка

{int z;

UpdateData(1);

if (m_order==FALSE)// если выбрана сортировка по возрастанию

{

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

for (int j=0; j<m_n-1; j++)

if(mas[j]>mas[j+1])

{z=mas[j];

mas[j]=mas[j+1];

mas[j+1]=z;

}

}

else

{for (int i=0; i<m_n; i++)

for (int j=0; j<m_n-1; j++)

if(mas[j]<mas[j+1])

{z=mas[j];

mas[j]=mas[j+1];

mas[j+1]=z;

}

}

 

m_list.ResetContent();

CString s;

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

{s.Format("%i", mas[i]);

m_list.InsertString(i,s);

}

UpdateData(0);

}

 

void CLara8Dlg::OnButton3() //линейный поиск

{ UpdateData(1);

CString s, message;

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

if (mas[i] == m_x)

{s.Format("mas[%i]. ", i+1);

message+=s;

}

if (message.GetLength()==0) //если строка осталась пустой

message.Format ("Элементов со значением %i в массиве нет", m_x);

 

AfxMessageBox(message);

}

 

void CLara8Dlg::OnOK() // кнопка «Выход»

{

if (mas) delete [] mas;// освобождаем память, занимаемую массивом

CDialog::OnOK();

}

 

9) Результаты работы программного продукта приведены на рисунках 7 и 8.

Рисунок 7 – Результат работы программы при верном вводе данных

Рисунок 8 – Результат работы программы при неверных данных

 

3. Задание на лабораторную работу.

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

 

4. Контрольные вопросы.

1) Какие классы и методы этих  классов использованы в разработанной  программе?

2) Принцип работы выбранного  алгоритма сортировки.

3) Принцип работы алгоритма бинарного  поиска.