Вход

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

Рекомендуемая категория для самостоятельной подготовки:
Курсовая работа*
Код 91097
Дата создания 2015
Страниц 30
Источников 21
Покупка готовых работ временно недоступна.
1 810руб.

Содержание

Введение 3
1. Алгоритмы сортировки и поиска 6
1.1. Сортировка массива методом «всплывающего пузырька» 6
1.2. Сортировка массива методом поиска локального минимума 8
1. 3. Сортировка Шелла 9
1.4. Прямой поиск в неупорядоченном массиве 13
1.5. Бинарный поиск в упорядоченном массиве 13
1.6. Интерполяционный поиск элемента в массиве 15
2. Алгоритм оценки эффективности методов сортировки и поиска 17
3. Разработка программного продукта 21
3.1. Интерфейс программного продукта 21
3.2. Программные тексты с комментариями 23
3.2.1. Листинг программного модуля ukurs_p.cpp 23
Заключение 29
Список литературы 30

Фрагмент работы для ознакомления

cpp
//---------------------------------------------------------------------------
#include <vcl.h>
#pragma hdrstop
#include "uKurs_p.h"
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
int m[100], kol;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
}
//---------------------------------------------------------------------------
// процедура передачи чисел из Мemo2 глобальный массив m
void IsMemo2()
{int i;
kol=Form1->Memo2->Lines->Count;
Form1->Lbkol->Caption=IntToStr(kol);
for (i=0;i<=kol-1;i++)
{m[i]=StrToInt(Form1->Memo2->Lines->Strings[i]);}
}
//--------------------------------------------------------
// процедура передачи чисел из глоб.массива m в ListBox2
void VListBox2 ()
{int i;
Form1->ListBox2->Items->Clear();
for (i=0;i<=kol-1;i++)
{Form1->ListBox2->Items->Strings[i]=IntToStr(m[i]);}
}
//--------------------------------------------------------
void __fastcall TForm1::btnEXITClick(TObject *Sender)
{
Close();
}
//---------------------------------------------------------------------------
void __fastcall TForm1::FormActivate(TObject *Sender)
{
IsMemo2();
}
//---------------------------------------------------------------------------
void __fastcall TForm1::btbSort1Click(TObject *Sender)
{
// вызов сортировки методом пузырька
int Sr, Per, i, j, x, Ef;
Sr=0; Per=0; Ef=0; // Начальные значения параметров эффективности сортировки
IsMemo2(); // из Memo2 в массив m
for(j=0; j<kol-1; j++)
for(i=0; i<kol-1; i++)
{ Sr++;
if(m[i+1]<m[i])
{ x=m[i];
m[i]=m[i+1];
m[i+1]=x;
Per=Per+3; }
}
Ef = Sr + 10*Per; // расчет эффективности
Edit1->Text=IntToStr(Sr); // Выводим параметры сортировки
Edit2->Text=IntToStr(Per);
Edit3->Text=IntToStr(Ef);
VListBox2(); // передача чисел из массива m в ListBox2
}
//---------------------------------------------------------------------------
void __fastcall TForm1::btbSort2Click(TObject *Sender)
{
// вызов сортировки локальным минимумом
int Sr, Per, x, Ef;
Sr=0; Per=0; Ef=0; // обнуляем характеристики алгоритма
IsMemo2(); // из Memo2 в массив m
int i, j;
int min, imin;
// Главный цикл до n-1, а не n, т.к. последний остающийся элемент - максимальный
for (i=0; i<kol-1; i++)
{
min=m[i]; imin=i;
for (j=i+1; j<kol; j++)
{
Sr++;
if(m[j]<min)
{ min=m[j];
imin=j;
Per++; }
}
x=m[i];
m[i]=min;
m[imin]=x;
Per=Per+3;
}
Ef = Sr + 10*Per; // расчитываем эффективность
Edit4->Text=IntToStr(Sr);
Edit5->Text=IntToStr(Per);
Edit6->Text=IntToStr(Ef);
VListBox2(); // передача чисел из массива m в ListBox2
}
//---------------------------------------------------------------------------
void __fastcall TForm1::btbSort3Click(TObject *Sender)
{
// вызов сортировки Шелла
int Sr, Per, x, Ef;
Sr=0; Per=0; Ef=0;
IsMemo2(); // из Memo2 в массив m
int d = kol, i, j;
while (d > 0)
{
d /= 2;
/* Цикл представляет собой один "пузырьковый" проход по всем группам элементов
на данном шаге. Кроме того, здесь, он выполняется и в конце, когда d=1,
позволяя избежать результирующей сортировки */
for (i=d; i<kol; i++)
{
int tmp = m[i];
for (j=i-d;(j>=0)&&(m[j]>tmp); j-=d)
{
m[j+d] = m[j]; Sr++;
}
m[j+d] = tmp; Per++;
}
}
Ef = Sr + 10*Per;
Edit7->Text=IntToStr(Sr);
Edit8->Text=IntToStr(Per);
Edit9->Text=IntToStr(Ef);
VListBox2(); // передача чисел из массива m в ListBox2
}
//---------------------------------------------------------------------------
void __fastcall TForm1::btbPoisk0Click(TObject *Sender)
{
// прямой поиск в исходном массиве
int i, x, Sr;
IsMemo2(); // из Memo2 в массив m
Sr=0;
x=StrToInt(Edit10->Text);
for (i=0;i<=kol-1;i++)
{ Sr++;
if (x==m[i])
{ Edit15->Text="Искомое число "+Edit10->Text+ " найдено в позиции "+IntToStr(i+1);
goto Vyxod;
}
}
Edit15->Text="Искомое число "+Edit10->Text+ " отсутствует";
Vyxod:
Edit11->Text=IntToStr(Sr);
}
//---------------------------------------------------------------------------
void __fastcall TForm1::btbPoisk1Click(TObject *Sender)
{
// прямой поиск в отсортированном массиве
int i, x, Sr; // число сравнений
IsMemo2(); // из Memo2 в массив m
Sr=0;
btbSort3Click(Sender); // сортировка массива m по методу Шелла
x=StrToInt(Edit10->Text);
for (i=0;i<kol-1;i++)
{ Sr++;
if (x==m[i])
{ Edit15->Text="Искомое число "+Edit10->Text+ " найдено в позиции "+IntToStr(i+1);
goto Vyxod;
}
}
Edit15->Text="Искомое число "+Edit10->Text+ " отсутствует";
Vyxod:
Edit12->Text=IntToStr(Sr);
}
//---------------------------------------------------------------------------
void __fastcall TForm1::btbPoisk2Click(TObject *Sender)
{
//Бинарный поиск в отсортированном массиве
int i, Sr, x,
l, // индекс верхней границы часитичного массива
u, // индекс нижней границы часитичного массива
s;// индекс середины
IsMemo2(); // из Memo2 в массив m
Sr=0;
btbSort3Click(Sender); // сортировка массива m по методу Шелла
x=StrToInt(Edit10->Text);// Запрос на поиск
l=0;
u=kol-1;
while (true) // "бесконечный" цикл
{s=(l+u)/2; // определяем середину отрезка
if (m[s]<x) // определяем в какой части искать дальше
{l = s + 1;
Sr++;}
else
{Sr++;
if (m[s] == x) // если найден
{Edit15->Text="Искомое число "+Edit10->Text+ " найдено в позиции "+IntToStr(s+1);
goto Vyxod;}
else
{Sr++;
if (m[s]>x)
u=s-1;}
}
}
Edit15->Text="Искомое число "+Edit10->Text+ " отсутствует";
Vyxod:
Edit13->Text=IntToStr(Sr);
}
//---------------------------------------------------------------------------
void __fastcall TForm1::btbPoisk3Click(TObject *Sender)
{
// вызов Интерполяционного поиска
int i, Sr, x,
iA, // индекс верхней границы часитичного массива
iB, // индекс нижней границы часитичного массива
iSred;// индекс середины
IsMemo2(); // из Memo2 в массив m
Sr=0;
btbSort3Click(Sender); // сортировка массива m по методу Шелла
x=StrToInt(Edit10->Text);// Запрос на поиск
iA = 0;
iB = kol-1;
while(iB >= iA) // пока не просмотрим весь
{
i = iA+(iB-iA)*(x-m[iA])/(m[iB]-m[iA]); // точка просмотра
Sr++;
if(x < m[i]) iB = i-1; // определяем направление поиска
else
{ Sr++;
if(x > m[i]) iA = i+1;
else
{Edit15->Text="Искомое число "+Edit10->Text+ " найдено в позиции "+IntToStr(i+1); // найден элемент
goto Vyxod;}
}
}
Edit15->Text="Искомое число "+Edit10->Text+ " отсутствует";
Vyxod:
Edit14->Text=IntToStr(Sr);
}
//---------------------------------------------------------------------------
Заключение
В результате выполнения курсовой работы были реализованы три метода сортировки и три метода поиска. Для каждого метода выводятся параметры эффективности работы алгоритма.
Результаты выполнения курсовой работы показывают значимость знания различных методов сортировки и поиска и умение применять их в зависимости от ситуации.
Список литературы
1.Ахо А. Структуры данных и алгоритмы: учеб. пособ. / А. Ахо, Д.Э. Хопкрофт, Д. Ульман; пер. с англ. - М.: Издательский дом "Вильяме", 2000. 2.Ахтамова С.С. Алгоритмы поиска данных // Современные наукоемкие технологии. - 2007. - № 3 - С. 11-14. 3.Бакнелл Джулиан М. Фундаментальные алгоритмы и структуры данных в Delphi. Пер. с англ./Джулиан М. Бакнелл. - СПб: ООО «ДиаСофтЮП», 2003.- 560 с. 4.Вирт Н. Алгоритмы и структуры данных: Пер. с англ. М.: Мир, 2001. 5.Гагарина Л.Г. Алгоритмы и структуры данных: учеб. пособие/ Л.Г. Гагарина, В.Д. Колдаев. - М.: Финансы и статистика; ИНФРА-М, 2009. -304 с. 6.Гасфилд Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология / Пер с англ. И.В. Романовского. - СПб.: Невский диалект; БХВ-Петербург, 2003 г. - 654 с. 7.Голицына ОЛ., Попов И.И. Основы алгоритмизации и программирования: учеб. пособие. - 3-е изд., испр. и доп. - М: ФОРУМ, 2008. - 432 с 8.ГОСТ «Единая система программной документации» (ЕСПД): ГОСТ 19.701-90. 9.Информатика : учебник для вузов / под ред. Н.В. Макаровой. - М. : Финансы и статистика, 2007. - 768 с. 10.Кнут, Д. Искусство программирования. Т. 3. Сортировка и поиск. - М.: Издательский дом «Вильямс», 2003. 11. Колдаев В. Д. Основы алгоритмизации и программирования: Учебное пособие / Под ред. проф. Л. Г. Гагариной. - М.: ИД «ФОРУМ»: ИНФРА-М, 2006. - 416c. 12. Кормен, Томас X., Лейзерсон, Чарльз И., Ривсст, Рональд Л., Штайн, Клиффорд. Алгоритмы: построение и анализ, 2-е издание. : Пер. с англ. - М. : Издательский дом "Вильяме", 2005. - 1296 с. 13. Королев, Л. Н. Информатика. Введение в компьютерные науки / Л. Н. Королев, А. И. Миков. - М.: Высш. шк., 2003. 14. Макконнелл Дж. Основы современных алгоритмов. Москва: Техносфера, 2004. - 368с.  15. Мейн М. Структуры данных и другие объекты в С++ / М. МеЙн, У Савитч; пер. с англ. - М.: Издательский дом "Вильяме", 2002. 16. Николаев В. И., Иванова И. В. Теория алгоритмов: Текст лекций. - СПб.: СЗТУ, 1995. 17. Николаев В. И., Чалов Д. В., Сиоирев В. Н. Информатика. Теоретические основы: Учеб. пособие. - СПб.: СЗТУ, 2002. 18.Островейковский В. А. Информатика: Учебник для вузов. - М.: Высш. шк.. 2000. 19. Сотанин С. В. Численный анализ методов сортировки. [Электронный ресурс.- метод доступа: http://conf.sfu-kras.ru/sites/mn2011/thesis/s31/s31_01.pdf] 20. Хусаинов Б.С. Структуры и алгоритмы обработки данных: примеры на языке Си: учеб. пособ. / Б.С. Хусаинов. - М.: Финансы и статистика, 2004. 21. Шень А. Программирование: Теоремы и задачи / А. Шень. - М.: МЦНМО, 2004.
30

Список литературы [ всего 21]

1.Ахо А. Структуры данных и алгоритмы: учеб. пособ. / А. Ахо, Д.Э. Хопкрофт, Д. Ульман; пер. с англ. - М.: Издательский дом "Вильяме", 2000.
2.Ахтамова С.С. Алгоритмы поиска данных // Современные наукоемкие технологии. - 2007. - № 3 - С. 11-14.
3.Бакнелл Джулиан М. Фундаментальные алгоритмы и структуры данных в Delphi. Пер. с англ./Джулиан М. Бакнелл. - СПб: ООО «ДиаСофтЮП», 2003.- 560 с.
4.Вирт Н. Алгоритмы и структуры данных: Пер. с англ. М.: Мир, 2001.
5.Гагарина Л.Г. Алгоритмы и структуры данных: учеб. пособие/ Л.Г. Гагарина, В.Д. Колдаев. - М.: Финансы и статистика; ИНФРА-М, 2009. -304 с.
6.Гасфилд Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология / Пер с англ. И.В. Романовского. - СПб.: Невский диалект; БХВ-Петербург, 2003 г. - 654 с.
7.Голицына ОЛ., Попов И.И. Основы алгоритмизации и программирования: учеб. пособие. - 3-е изд., испр. и доп. - М: ФОРУМ, 2008. - 432 с
8.ГОСТ «Единая система программной документации» (ЕСПД): ГОСТ 19.701-90.
9.Информатика : учебник для вузов / под ред. Н.В. Макаровой. - М. : Финансы и статистика, 2007. - 768 с.
10.Кнут, Д. Искусство программирования. Т. 3. Сортировка и поиск. - М.: Издательский дом «Вильямс», 2003.
11. Колдаев В. Д. Основы алгоритмизации и программирования: Учебное по¬собие / Под ред. проф. Л. Г. Гагариной. - М.: ИД «ФОРУМ»: ИНФРА-М, 2006. - 416c.
12. Кормен, Томас X., Лейзерсон, Чарльз И., Ривсст, Рональд Л., Штайн, Клиффорд. Алгоритмы: построение и анализ, 2-е издание. : Пер. с англ. - М. : Издательский дом "Вильяме", 2005. - 1296 с.
13. Королев, Л. Н. Информатика. Введение в компьютерные науки / Л. Н. Королев, А. И. Миков. - М.: Высш. шк., 2003.
14. Макконнелл Дж. Основы современных алгоритмов. Москва: Техносфера, 2004. - 368с.
15. Мейн М. Структуры данных и другие объекты в С++ / М. МеЙн, У Савитч; пер. с англ. - М.: Издательский дом "Вильяме", 2002.
16. Николаев В. И., Иванова И. В. Теория алгоритмов: Текст лекций. - СПб.: СЗТУ, 1995.
17. Николаев В. И., Чалов Д. В., Сиоирев В. Н. Информатика. Теоретические основы: Учеб. пособие. - СПб.: СЗТУ, 2002.
18.Островейковский В. А. Информатика: Учебник для вузов. - М.: Высш. шк.. 2000.
19. Сотанин С. В. Численный анализ методов сортировки. [Электронный ресурс.- метод доступа: http://conf.sfu-kras.ru/sites/mn2011/thesis/s31/s31_01.pdf]
20. Хусаинов Б.С. Структуры и алгоритмы обработки данных: при¬меры на языке Си: учеб. пособ. / Б.С. Хусаинов. - М.: Финансы и статистика, 2004.
21. Шень А. Программирование: Теоремы и задачи / А. Шень. - М.: МЦНМО, 2004.
Пожалуйста, внимательно изучайте содержание и фрагменты работы. Деньги за приобретённые готовые работы по причине несоответствия данной работы вашим требованиям или её уникальности не возвращаются.
* Категория работы носит оценочный характер в соответствии с качественными и количественными параметрами предоставляемого материала. Данный материал ни целиком, ни любая из его частей не является готовым научным трудом, выпускной квалификационной работой, научным докладом или иной работой, предусмотренной государственной системой научной аттестации или необходимой для прохождения промежуточной или итоговой аттестации. Данный материал представляет собой субъективный результат обработки, структурирования и форматирования собранной его автором информации и предназначен, прежде всего, для использования в качестве источника для самостоятельной подготовки работы указанной тематики.
© Рефератбанк, 2002 - 2022