Разработать программу для реализации алгоритма быстрого последовательного поиска - файл n1.doc

Разработать программу для реализации алгоритма быстрого последовательного поиска
Скачать все файлы (10114.6 kb.)

Доступные файлы (47):
n1.doc2508kb.14.01.2012 15:42скачать
n2.txt105kb.07.11.2011 16:52скачать
n3.hlp
n4.obj
n5.gid
n6.cnt
n7.exe
n8.ilk
n9.obj
n10.pch
n11.pdb
n12.res
n13.obj
n14.idb
n15.pdb
16=0=1326548284=1=n16.txt=txt
n17.bat
n18.txt4kb.11.10.2011 17:00скачать
n19.cpp
n20.h
n21.rtf45kb.11.10.2011 20:37скачать
n22.hlp
n23.log
n24.cnt
n25.hm
n26.hpj
n27.ph
n28.ico
n29.rc2
n30.h
n31.aps
n32.clw
n33.cpp
n34.dsp
n35.dsw
n36.h
n37.ncb
n38.opt
n39.plg
n40.rc
n41.sdf
n42.vcxproj
search.vcxproj.filters
search.vcxproj.user
n45.cpp
n46.h
47=0=1322258244=1=n47.txt=txt

n1.doc





















100.0.000.000.000

лист













5.12.11



Изм.

Лист

докум.

Подп.

Дата






Уфимский государственный авиационный технический университет

Кафедра _________ «Вычислительная техника и зашита информации»_____________


100

1

2

3

4

5

6

7

8

9

10

11

12

90





































80





































70





































60





































50





































40





































30





































20





































10





































0





































Разработка прикладного алгоритма


Подп. и дата




Подп. и дата




Взаим. инв. №




Инв.№ подл.




Инв.№ дубл.



на языке программирования С++___

___________________________________

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовому проекту по ____МП и ПА_____


100.0.000.000.000

(обозначение документа)


Группа

Фамилия И.О.

Подпись

Дата

Оценка

Студент













Консультант













Принял














Уфа – 2010

Уфимский государственный авиационный технический университет

Кафедра ____________________________факультет____ИРТ______________________

Задание

на курсовое проектирование по дисциплине ___Методы программирования и прикладные алгоритмы________________________________________________________________________

на тему Разработка прикладного алгоритма и его реализация на языке С++___________

выдано 8 октября 2011г. студенту второго курса____________________________________

______________________________________________________________________ группы

________________________________________________________________________________

__________________________________________________________________________________

(Фамилия И.О)
Срок выполнения ___5 декабря__ 2011г.

Руководитель проекта ____________________.


1.Технические условия

Использование среды программирования Visual C++ для разработки программ на языке программирования C++___________________________________________________________

_________________________________________________________________________________

_________________________________________________________________________________

2. Содержание проекта

1. Постановка задачи и описание исходных данных;__________________________________

2. Разработка математического обеспечения и алгоритма программы;__________________

3. Краткое описание функций среды программирования;_____________________________

4. Описание работы программы с листингом созданных функций;_____________________

5. Получение результатов и выводы.________________________________________________

3. Оформление проекта

1. Пояснительная записка__________________________________________________________

2. Разработанная программа_______________________________________________________
4. Список используемой литературы:

1. Либерти Д. Освой самостоятельно С++ за 21 день 4-е издание : пер. с англ. – М.: Издательский дом «Вильямс», 2001. – 832 с. : ил. - Парал. тит. англ.

2. Селиванова М.В. Методические указания к курсовой работе по дисциплине «Методы программирования и прикладные алгоритмы»/ Уфимск. гос. авиац. тех. ун-т. Сост. Селиванова М.В. – Уфа, 2008. – 31 с.

3. Кнут Д. Искусство программирования. Т.3 Сортировка и поиск. М.: Вильямс, 2000. – 832 с.

4. Культин Н. «С/С++ в задачах и примерах» - СПб.:БХВ-Петербург, 2002. – 288 с.

5. А. Мешков, Ю. Тихомиров «Visual C++ и MFC» - СПб.:БХВ-Петербург. 2002 – 1017с.

Зав. кафедрой ________________ Руководитель проекта _____________________

Содержание

  1. Постановка задачи и описание исходных данных…………………………5

  2. Математическое обеспечение……………………………………………….6

  3. Функция изменения времени вычисления от объема исходных данных...6

  4. О-сложность алгоритма……………………………………………………...6

  5. Разработка алгоритма программы в виде блок-схемы…………………….7

  6. Описание функций среды программирования Visual Studio 6……………10

  7. Описание работы программы……………………………………………….16

Вывод…………………………………………………………………………18

Список используемой литературы……………………………………….…19

Приложение А……………………………………………………………….21

Приложение Б……………………………………………………………….23

Приложение В……………………………………………………………….25

Приложение Г……………………………………………………………….27


Постановка задачи и описание исходных данных

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

Математическое обеспечение
Суть метода :

Cоздаётся фиктивная запись в конце файла (A [ N+1] ) равная искомому элементу. Последовательно перебираются все элементы массива, если на каком-то шаге цикла обнаруживается, что искомый элемент найден, то происходит выход из цикла, и переход к условию i < N+1. Если условие выполняется , то искомый элемент присутствует в массиве, иначе элемента нет.

Алгоритм Quick Sequential Search реализуется следующим образом:

Q1. [Инициализация] Устанавливаем i ? 1 и KN+1 ? K.

Q2. [Сравнение] Если K=Ki , то переходим к шагу Q4.

Q3. [Продвижение.] Увеличить i на 1и перейти к шагу Q2.

Q4. [Конец файла?] Если i ? N, алгоритм заканчивается успешно; в противном случае алгоритм заканчивается неудачно (i = N+1).

Функция изменения времени вычисления от объема исходных данных

Очевидно, что время выполнения алгоритма Q зависит от двух факторов:

C- количество сравнений ключей;

S=1 при успешном окончании поиска, 0 – при неудачном.

Используя значения C и S , получим, что значение времени работы равно

(4С - 4S + 10)u. Так как при поиске будет всегда успешно найден K=Ki получим С=i , S=1; таким образом, полное время составляет (4i+6)u
О-сложность алгоритма

Так как при поиске используется всего лишь один простой цикл

for (int n=0; pInt[n] != m_search; n++), то О-сложность данного алгоритма линейная О(n)

Разработка алгоритма программы в виде блок-схемы



Рисунок 1 – Блок схема создания массива чисел и запись их в файл


Рисунок 2 – Блок схема считывания из файла данных



Рисунок 3 – Блок схема поиска элемента в массиве

Описание функций среды программирования Microsoft Visual Studio 6

Данная курсовая работа выполнена в среде программирования Microsoft Visual Studio 6, в состав которой включен компилятор и интерпритатор С++

C++ - это попытка решения разработчиками языка С задач объектно-ориентированного программирования (Object Oriented Programming, OOP). Построенный на твердом фундаменте С, С++ помимо ООР поддерживает множество других полезных инструментов, не жертвуя при этом ни мощью, ни элегантностью, ни гибкостью С. С++ уже стал универсальным языком для программистов всего мира.

С++ был разработан сотрудником научно-исследовательского центра AT&T Bell Laboratories (Нью-Джерси, США) Бьярном Страуструпом в 1979 году. Первоначальное название «С с классами» было изменено на С++ в 1983 году. Начиная с 1980 года С++ претерпел две существенные модернизации: в 1985 и 1990 годах. Последняя третья модель связана с процессом стандартизации С++. Несколько лет назад началась работа по созданию единого международного стандарта по С++. Для этой цели был сформирован объединенный комитет по стандартизации ANSI (American National Standards Institute, Американский национальный институт стандартов) и ISO (International Standards Organization, Международная организация по стандартам) для языка С++. Первый рабочий проект указанного стандарта был предложен 25 января1994 года. Комитет ANSI/ISO по С++ фактически сохранил все основные черты языка, заложенные туда еще Страуструпом и добавил несколько новых инструментов.

Microsoft Visual Studio — линейка продуктов компании Майкрософт, включающих интегрированную среду разработки программного обеспечения и ряд других инструментальных средств. Данные продукты позволяют разрабатывать как консольные приложения, так и приложения с графическим интерфейсом, в том числе с поддержкой технологии Windows Forms, а также веб-сайты, веб-приложения, веб-службы как в родном, так и в управляемом кодах для всех платформ, поддерживаемых Microsoft Windows, Windows Mobile, Windows CE, .NET Framework, .NET Compact Framework и Microsoft Silverlight.

Visual Studio 6.0 —версия, работающая на платформе Win9x (выпущена в июне 1998). По-прежнему популярна среди программистов, использующих Visual Basic. Данная версия являлась основной средой разработки приложений под Windows от Microsoft до появления платформы .NET.

Создание проекта

Процесс разработки Windows-программы в Visual C++ начинается с создания нового проекта и подготовки набора исходных файлов. Раньше их приходилось делать вручную, теперь всю работу берет на себя "мастер" AppWizard.

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

Классы графического интерфейса

Весь вывод в системе Windows реализован на принципе унификации работы с такими физически различными устройствами, как экран дисплея, принтеры, плоттеры, и.т.п. Для всех этих устройств приложение использует одни и те же функции и, в общем случае, может «не задумываться» над тем, куда будет выведена строка текста или какой-либо графический объект. Система сама распознает устройство ввода и активизирует соответствующий драйвер. Такой подход, с одной стороны, обеспечивает универсальность процесса графического вывода, а с другой – позволяет, например, создавать платы графических акселераторов, которые самостоятельно, без использования центрального процессора осуществляют преобразования команд рисования, существенно разгружая тем самым всю систему в целом.

Для реализации такого подхода в Windows предусмотрен специальный объект, называемый контекстом устройства. Именно он хранит необходимую информацию как об устройстве вывода, так и о параметрах соответственно рисования. Физически весь вывод происходит, естественно, на конкретное устройство, представленное в системе контекстом, описываемым, в свою очередь, дескриптором. Последний используют (в качестве параметра) все функции графического вывода Win32 API, т.е. при этом задействуется объект «контекст устройства», до чего MFC-приложению нет никакого дела – оно работает с объектами классов библиотеки MFC, что существенно удобнее и надежнее.

CDC – базовый класс для всех классов, инкапсулирующих контексты устройств Windows. Объекты этого класса используются для работы со всем экраном дисплея или с таким устройством, как принтер.

CClientDC – объекты этого класса обеспечивают доступ к клиентской части окна. Используется для графического вывода в любой функции. При создании объекта класса CClientDC в конструкторе вызывается функция Win32 API GetDC, а при разрушении, в деструкторе – ReleaseDC, также из Win32 API, обеспечивая необходимые операции для подготовки и завершения процесса графического вывода именно и только в клиентскую часть окна. За создание объекта класса CClientDC отвечает разработчик приложения.

Классы для работы с файлами

Класс CFile

Класс CFile предназначен для обеспечения работы с файлами. Он позволяет упростить использование файлов, представляя файл как объект, который можно создать, читать, записывать и т.д. Чтобы получить доступ к файлу, сначала надо создать объект класса CFile. Далее этот файл можно открыть, вызвав метод Open, в качестве параметров которого указывают путь к открываемому файлу и режим использования файла. Прототип метода Open() имеет следующий вид:

virtual BOOL Open(LPCTSTR FileName, UINT Flags, CFileException* pError = NULL);

В качестве параметра FileName нужно указать имя открываемого файла. Можно указать только имя файла или полное имя файла, включающее полный путь к нему.

Второй параметр Flags определяет действие, выполняемое с файлом, а также атрибуты файла. Ниже представлены некоторые возможные значения параметра Flags:

СFile::modeCreate - Создается новый файл. Если указанный файл существует, то его содержимое стирается и длина файла устанавливается равной нулю.

CFile::modeRead - Файл открывается только для чтения.

СFile::modeReadWrite - Файл открывается для записи и для чтения.

CFile::modeWrite - Файл открывается только для записи.

Необязательный параметр pError, который является указателем на объект класса CFileException, используется только в том случае, если выполнение операции с файлом вызовет ошибку. При этом в объект, указываемый pError, будет записана дополнительная информация.

Метод Open() возвращает ненулевое значение, если файл открыт и нуль в случае ошибки. Ошибка при открытии файла может случиться, например, если методу Open() указан для чтения несуществующий файл.

После завершения работы с файлом, его надо закрыть. Класс CFile имеет для этого специальный метод Close().

Для чтения из файла предназначен метод Read. Его прототип выглядит следующим образом:

virtual UINT Read( void* Buf, UINT nCount );

Параметры:

Buf – указатель на определенный пользователем буфер (область памяти), где размещаются считанные данные;

nCount – максимальное количество байт, которые будут считаны из файла.

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

Для записи в файл предназначен метод Write. Его прототип выглядит следующим образом:

virtual void Write( const void* Buf, UINT nCount );

Параметры:

Buf – указатель на определенный пользователем буфер (область памяти), где размещены данные, которые необходимо записать в файл;

nCount – количество байт, которые необходимо записать в файл.

Класс CStdioFile

Этот класс позволяет выполнять буферизированный ввод/вывод в текстовом и двоичном режиме. Для объектов класса CStdioFile можно вызывать практически всеметоды класса CFile.

Для чтения и записи в текстовый файл класс CStdioFile включает два метода ReadString и WriteString. Метод ReadString позволяет прочитать из файла строку символов, а метод WriteString - записать.

Класс CString – удобное средство для работы со строками. В отличие от языка C, где работа со строковыми данными сводится к использованию массивов символов, ограниченных конечным нулем, а действия над строками осуществляются через указатели на строки, класс CString позволяет создать строковую переменную, аналогичную переменной типа string в языке Pascal. CString не имеет базового класса.

Класс CString содержит последовательность символов переменной длины и набор функций и операций над ней. Тип символа – TCHAR, т. е. если в программе используется двухбайтный символ (определен макрос _UNICODE), то тип символа устанавливается как WCHAR, в противном случае тип символа определяется как char.

В класс CString включено несколько конструкторов, в том числе конструктор по умолчанию, конструктор с параметрами, копирующий конструктор, при создании строк нет необходимости заботиться о выделении достаточного объема памяти для них, выделение памяти производится автоматически.
GetBuffer

Этот метод возвращает указатель на внутренний символьный буфер объекта CString. Возвращенный LPTSTR - неконстанта и таким образом позволяет прямую модификацию содержания CString.

Atoi

Выполнить преобразование строки в число можно многими способами - выбор конкретного зависит от ваших целей на момент написания кода. Есть штатные способы - ряд библиотечных функций, есть более изощренные, есть совсем уж извращенные годные разве что для экзерсисов в области программирования. Cамый распространенный, но далеко не самый лучший способ- использование штатных библиотечных функций atoi. Эта функции входит в стандартную библиотеку языка и присутствует в любом компиляторе. Его объявление выглядит так:

int atoi(const char* str)

Описание работы программы

В диалоге программы имеется 4 элемента Edit Box, 3 элемента Button и 1 List Box.

прямая со стрелкой 8прямая со стрелкой 9прямая со стрелкой 10прямая со стрелкой 11

Рисунок 4 – Окно программы

В первое поле Edit Box (соответствующая переменная m_FileName) вводится название создаваемого файла. Если пользователь не введет название файла по каким-либо причинам, то программа автоматически задаст название файла по умолчанию (Поиск.txt)

В следующее поле Edit Box (m_NUM) пользователь вводит количество генерируемых элементов. Если пользователь не вводит в это поле данные, то программа выведет Message Box с просьбой к пользователю ввести значение.



Рисунок 5 – Ошибка при создании массива Рисунок 6 – Успешное считывание из файла

В третье поле Edit Box (m_search) пользователь вводит то число, которое он хочет найти в только что сгенерированном массиве. Если он не вводит значение для поиска, то программа сообщит ему, о том, что он не ввел то, что хочет найти.



Рисунок 7 – Ошибка при поиске Рисунок 8 – Успешное завершение поиска

В четвертое поле Edit Box (m_SEARCHTIME) выводится время выполнения поиска.

Кнопка

При нажатии на эту кнопку создается одномерный массив сгенерированных данных, который заносятся в заранее определенный файл *.txt
Кнопка

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

Кнопка

При нажатии на эту кнопку происходит поиск в массиве того значения, которое укажет пользователь в поле Edit Box.

Вывод:

В ходе данной курсовой работы был изучен алгоритм быстрого последовательного поиска, а так же основы программирования в среде Microsoft Visual Studio 6.0. Язык С++ называют средой быстрой разработки приложений, что вполне оправдано – для создания аналогичной программы на ассемблере необходимо было бы написать код на сотню страниц. Visual Studio C++ является средой визуальной разработки приложений. Данный подход к программированию является одним из самых перспективных на сегодняшний день и это вполне оправданно как объемом кода для написания программы, так и следствием из этого – экономией времени. А пошаговая отладка позволяет быстро найти и исправить ошибки. Однако, для написания любой программы необходимо знать и уметь составлять алгоритмы решения задачи, что входит исключительно в задачи программиста. В связи с этим, в ходе выполнения работы, были изучены основы программирования на языке С++ , который является базовым для Visual Studio , без знания основ которого не может быть реализован ни один алгоритм. Так что для работы в среде Visual Studio необходимо знание основ как С++, так и объектно ориентированного программирования в целом.

Список используемой литературы

1. Либерти Д. Освой самостоятельно С++ за 21 день 4-е издание : пер. с англ. – М.: Издательский дом «Вильямс», 2001. – 832 с. : ил. - Парал. тит. англ.

2. Селиванова М.В. Методические указания к курсовой работе по дисциплине «Методы программирования и прикладные алгоритмы»/ Уфимск. гос. авиац. тех. ун-т. Сост. Селиванова М.В. – Уфа, 2008. – 31 с.

3. Кнут Д. Искусство программирования. Т.3 Сортировка и поиск. М.: Вильямс, 2000. – 832 с.

4. Культин Н. «С/С++ в задачах и примерах» - СПб.:БХВ-Петербург, 2002. – 288 с.

5. А. Мешков, Ю. Тихомиров «Visual C++ и MFC» - СПб.:БХВ-Петербург. 2002 – 1017с.
ПРИЛОЖЕНИЯ
Приложение А

Листинг функций кнопки «Создать»

void CSearchDlg::OnDofile()

{ UpdateData(1);

if (m_FileName.IsEmpty()) m_FileName = "Поиск";

CStdioFile m_File;

if ( !m_File.Open(m_FileName+CString(".txt"),

CFile::modeCreate | CFile::modeWrite | CFile::typeText) )

{MessageBox("(!) Ошибка открытия файла", "Информация", MB_ICONEXCLAMATION);

return;

}

if (m_NUM==0)

{ this->RedrawWindow();

CClientDC MyDC(GetDlgItem(IDC_NUM));

CRect Rect;

CWnd *pWnd = MyDC.GetWindow();

pWnd->GetClientRect( &Rect );

MyDC.FillSolidRect( &Rect, RGB(255,0,0) );

{MessageBox("Введите количество генерируемых элементов", "Информация", MB_ICONEXCLAMATION);

return;

}}

m_SEARCHTIME.Empty();

продолжение Приложения А

this->RedrawWindow();

CString str;

clock_t start, finish;

start = clock();

for (int n=0; n < m_NUM; n++)

{ str.Format("%i\n", m_NUM * rand());

m_File.WriteString(str);

}

finish = clock();

m_SEARCHTIME.Format("%1.4f сек",(double)(finish - start)/CLOCKS_PER_SEC);

UpdateData(0);

m_DATABOX.ResetContent();

m_File.Close();

CString f;

f.Format("Успешно сгенерированно %i элемента(ов)",n);

MessageBox(f, "Информация", MB_ICONINFORMATION);

}}

Приложение Б

Листинг функций кнопки «Загрузить»

void CSearchDlg::OnReadfile()

{UpdateData(1);

CStdioFile m_File;

if ( !m_File.Open(m_FileName+CString(".txt"),

CFile::modeRead | CFile::typeText) )

{MessageBox("Ошибка открытия файла", "Информация", MB_ICONEXCLAMATION);

return;

}

pInt = new int[m_NUM];

if (pInt == NULL)

{MessageBox("Ошибка создания массива", "Информация", MB_ICONEXCLAMATION);

return;

}

IntNum = 0;

CString str;

m_DATABOX.ResetContent();

while ( m_File.ReadString(str) != NULL)

{pInt[IntNum++] = atoi(str.GetBuffer(0));

m_DATABOX.AddString(str);

продолжение Приложения Б

}

m_File.Close();

UpdateData(0);

CString fg;

fg.Format("Данные считаны успешно. Всего %i элемента(ов)",IntNum);

MessageBox(fg, "Информация", MB_ICONINFORMATION);

}

Приложение В

Листинг функций кнопки «Поиск»

void CSearchDlg::OnDosearch()

{if ((pInt == NULL)||(IntNum<1))

{CClientDC MyDC(GetDlgItem(IDC_LISTDATA));

CRect Rect;

CWnd *pWnd = MyDC.GetWindow();

pWnd->GetClientRect( &Rect );

MyDC.FillSolidRect( &Rect, RGB(230,0,0) );

{MessageBox("Искать нечего","Информация", MB_ICONINFORMATION);

return;

}}

UpdateData(1);

if (m_search==0)

{ this->RedrawWindow();

CClientDC MyDC(GetDlgItem(IDC_SEARCH));

CRect Rect;

CWnd *pWnd = MyDC.GetWindow();

pWnd->GetClientRect( &Rect );

MyDC.FillSolidRect( &Rect, RGB(255,0,0) );

{MessageBox("Введите значение для поиска", "Информация", MB_ICONEXCLAMATION);

return;

}}

продолжение Приложения В

this->RedrawWindow();

pInt[m_NUM+1]=m_search;

for (int n=0; pInt[n] != m_search; n++) ;

if (n < m_NUM+1)

{CClientDC MyDC(GetDlgItem(IDC_LISTDATA));

CRect Rect;

CWnd *pWnd = MyDC.GetWindow();

pWnd->GetClientRect( &Rect );

MyDC.FillSolidRect( &Rect, RGB(0,255,0) );

{MessageBox(" Файл найден", "Информация", MB_ICONINFORMATION);

return;

}}

else MessageBox(" Файл НЕ найден", "Информация", MB_ICONEXCLAMATION );}

Приложение Г

Описание переменных

m_FileName – имя файла

m_File - объекты класса CStdioFile

m_NUM – количество генерируемых элементов

srt, f, fg – объекты класса CString

m_SEARCHTIME – время выполнения поиска

pInt - динамический массив

IntNum, i, n - счетчики

m_search – элемент который нужно найти

start, finish – переменные clock_t
Учебный текст
© perviydoc.ru
При копировании укажите ссылку.
обратиться к администрации