Глава 2. Реализация приложения «сортировка выбором связанного списка»
2.1. Постановка задачи
Исходя из цели курсовой работы в приложение « Сортировка выбором связанного списка» должны быть реализованы следующие возможности:
-
Ввод случайных чисел.
-
Отсортировка по возрастанию с помощью программы.
2.2. Описание технологии разработки
Используем структуру:
struct list.
Функция ,выводящая список на экран:
PrintList.
Список формируется с помощью случайных чисел ,с помощью функции:
randomize.
В данной программе использовали следующие переменные и указатели.
int n=0; int min=MAXINT; int i; int buf; list *head; list *p; list *tmp; list *k; list *j;
Определение размера списка осуществляется вручную.
cin»n;
Далее происходит формирование самого списка.
for(i=0; i<n; i++)
p->next=new list;
p=p->next;
p->name=random(100)+1;
p->next=NULL;
На данном этапе программного продукта происходит вывод списка на экран.
PrintList(p,head,n);
Далее сортируем список.
for(k=head; k; k=k->next)
min=MAXINT;
for(j=k; j; j=j->next)
if(j->name < min)
tmp = j;
min=j->name;
Меняем местами самый минимальный ,и текущий элементы списка.
buf=k->name;
k->name=min;
tmp->name=buf;
Функция вывода списка на экран.
void PrintList(list* p, list* head, int n)
p=head;
while(p != 0)
p=p->next;
2.2.Экспериментальный раздел
На рисунке 3 изображен ввод желаемого количества элементов списка. После сформирования списка случайных чисел, осуществляется первый цикл.
Рис.3 Ввод количества элементов.
На рисунке 4 изображены следующие два шага преобразования списка. Где видно что число 21 меняется местами с числом 39.
Рис.4 Пошаговое формирование списка.
На рисунке 5 изображен конечный результат данной программы. Отсортированный список.
Рис.5.Конечный результат.
Заключение
В ходе выполнения данной курсовой работы были рассмотрены
проблемы реализации приложения «Сортировка выбором связанного списка», изучен теоретический аспект и получен практические навыки работы.
Получен практический опыт работы с такими возможностями языка программирования С++ ,как сортировка выбором связанного списка.
В результате выполнения данной курсовой работы были выполнены следующие задачи:
-
Изучены теоретические аспекты для реализации приложения « Сортировка выбором связанного списка».
-
Разработан алгоритм работы приложения « Сортировка выбором связанного списка».
-
Создан программный продукт « Сортировка выбором связанного списка» на языке С++.
-
Проведен анализ работоспособности программного продукта реализующего « Сортировка выбором связанного списка».
Список литературы
1. Ананий В. Левитин Глава 3. Метод грубой силы: Сортировка выбором.
2. Гилберт Стивен, Макартни Билл. Самоучитель Visual C++ 6 в примерах. - К.: ООО "ТИД ДС", 2003. - 496с.
3. Лабораторный практикум. Кузьмина Е.А., Минасов Ш.М., Тархов С.В., варианты индивидуальных заданий: Карчевская М.П., Рамбургер О.Л.
4. Уэйт М., Прата С., Мартин Д. Язык Си. Руководство для начинающих.
5. Шиманович Е.Л. C/C++ в примерах и задачах. - Минск: Новое знание, 2004, - 528с.
6. Шмидский Я. К. Программирование на языке С/С++. Самоучитель. –М.: Вильямс, 2004. -352с.
7. Роберт Седжвик Часть III. Глава 6. Элементарные методы сортировки.
8. Касаткин А.И., Вальвачев А.Н. Профессиональное программирование на языке Си: От Турбо Си к С++. – Минск: Вышэйшая школа, 1992. – 240с.
9. Николенко Д. В. Самоучитель по Visual C++. -СПб : Наука и техника, 2001.
ПРИЛОЖЕНИЕ
#include<conio.h>
#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
#include<values.h>
//__________________________STRUKTURA______________________
struct list
{
int name;
list *next;
};
//_________________________________________________________
void PrintList(list* p, list* head, int n);
int main()
{
randomize();
clrscr();
//________________________INICIALIZACIYA___________________
int n=0; //____________kolichestvo elementov spiska
int min=MAXINT; //____________minimal'nyi
int i; //____________schetchik cikla vivoda
int buf; //____________bufer poiska
list *head; //____________ukazatel' golovi spiska
list *p; //____________sam spisok
list *tmp; //____________bufer spiska
list *k; //____________schetchik cikla sortirovki
list *j; //____________schetchik cikla sortirovki
//___________________OPREDELENIE RAZMERA SPISKA____________
cout<<"Vvedite kolichestvo elementov\n";
cin>>n;
n--;
//___________________SOZDAEM GOLOVU SPISKA_________________
p=new list;
head=p;
//___________________FORMIROVANIE SAMOGO SPISKA_____________
for(i=0; i<n; i++)
{
p->next=new list;
p=p->next;
p->name=random(100)+1;
}
p->next=NULL;
//___________________VIVOD SPISKA NA EKRAN___________________
cout<<"\n\n\nSformirovannii spisok\n\n";
PrintList(p,head,n);
//______________________SORTIRUEM SPISOK_____________________
cout<<"\n\n\nOtsortirovannii spisok\n\n";
for(k=head; k; k=k->next)
{
min=MAXINT; //__________opredeliaem minimal'nyi min=max
for(j=k; j; j=j->next) //__________proxod po spisku
{
if(j->name < min) //_________proverka minimal'nogo elementa
{
tmp = j;
min=j->name;
}
}
//___________meniaem mestami samii minimal'nyi i tekushii elementi spsiska
buf=k->name;
k->name=min;
tmp->name=buf;
getch();
cout<<"\n\n";
PrintList(p,head,n);
}
//_________________VIVOD OTSORTIROVANNOGO SPISKA___________
/*
cout<<"\n\n\nOtsortirovannii spisok\n\n";
PrintList(p,head,n);
getch();*/
return 0;
};
//_____________________FUNKCIA VIVODA SPISKA________________
void PrintList(list* p, list* head, int n)
{
p=head;
while(p != 0)
{
cout<<p->name<<" ";
p=p->next;
}
}