Сортування масиву методом Шелла
Звіт по практиці
Виконали: cт.гр. 97ЕЕ3 Тлумач М., Ерегін П., Синьова
Т.
Пензенський державний університет, Кафедра
"Економічна кібернетика"
Пенза 1998
Завдання
Мета роботи: вивчити метод Шелла для сортування
строкового масиву і застосувати цей метод на практиці.
Завданням на практичну роботу є розробка
програми на мові програмування Borland С + + v.3.1. для сортування масиву
рядків по їх індексному значенням. Значення елементів масиву і їх індекси
задаються користувачем з клавіатури.
Вступ
В даний час індустрія виробництва комп'ютерів і
програмного забезпечення для них є однією з найбільш важливих сфер
економіки розвинених країн. Щорічно у світі продаються десятки мільйонів
комп'ютерів. Тільки в США обсяг продажів комп'ютерів складає десятки мільйонів
доларів і постійно продовжує рости.
У чому ж причини такого стрімкого зростання індустрії
персональних комп'ютерів та їх порівняльна вигідність для багатьох ділових
застосувань?
Простота використання, забезпечена за допомогою діалогового
способи взаємодії з комп'ютером.
Відносно високі можливості з переробки інформації,
наявність програмного забезпечення, а також потужних систем для розробки нового
програмного забезпечення.
Мова С + + - універсальна мова загального призначення,
область додатків якого - програмування систем в самому широкому сенсі.
Крім цього, С + + успішно використовується як у багатьох додатках, так і в потужних
операційних системах.
1 Вхідні дані
Вхідними даними в програмі є число елементів
масиву, значення індексу кожного елемента і рядкові елементи масиву. Всі
ці дані вводяться користувачем з клавіатури за запитом програми. Число елементів
масиву не повинно перевищувати 32767. Індекси елементів масиву повинні бути
цілочисельними значеннями.
2 Вихідні дані
Вихідними даними в програмі є вихідний і
відсортовано за методом Шелла масив, які виводяться на екран за запитом
користувача.
3 Архітектура програми
Дана програма розроблена на мові програмування
С + + і складається з наступних функціональних модулів:
1) menu - обробник меню;
2) input - введення даних;
3) output - виведення даних;
4) sort - сортування Шелла;
5) Основна програма.
1.Функція menu:
Здійснює виведення на екран меню, опитування клавіатури в
нескінченному циклі і пересування кольорового курсору по пунктах меню. При натисканні
клавіші 'Esc' повертає -1, якщо натиснути клавішу з номером пункту меню
повертає цей номер, якщо натиснути клавішу 'Enter' повертає номер поточного
пункту меню.
Параметри для виклику функції menu: x, y - координати
меню на екрані, * capt - вміст меню.
2.Функції input:
Здійснює введення індексів і елементів масиву з
клавіатури, повертає кількість введених елементів.
Параметри для виклику функції mas []-вказівник на
масив, stn - номер перший вводиться елементу.
3.Функції output:
Здійснює висновок вмісту масиву на екран.
Параметри для виклику функції mas []-вказівник на
масив, num - число елементів масиву.
4.Функція sort:
Здійснює сортування масиву за індексами елементів
методом Шелла.
Сортування методом Шелла полягає в наступному:
спочатку окремо групуються і сортуються елементи, віддалені один від одного
на відстані 9. Після першого проходу елементи перегруповуються і знову сортуються
елементи, віддалені один від одного на відстані 5, потім сортуються елементи,.
віддалені один від одного на відстані 3, і нарешті, на четвертому проході йде
звичайна або одинарна сортування.
Параметри для виклику функції mas []-вказівник на
масив, num - число елементів масиву.
5. Основна програма:
Здійснює установку квітів, очищення екрана, виклик,
функції обробки меню і в залежності від повернутого значення виклик одній з
наступних функцій: input, output, sort.
Список літератури
1. Вірт Н. Алгоритми та структури даних: Пер з англ. -М.:
Світ, 1989. - 360 с., Іл.
2.Бьярн Страуструп. Мова програмування С + +. у двох
частинах. Пер. з англ. Київ: "ДіаСофт", 1993.-296 с. іл.
ДОДАТОК 1
Роздруківка програми
# include
# include
# include
# include
// Дані одного елемента масиву
struct one_elem (
int n;// Індекс
char st [100];// Дані
);
// Обробка меню
int menu (int x, int
y, char * capt);
// Введення даних
int input (one_elem
mas [], int stn);
// Вивід даних
void
output (one_elem mas [], int num);
// Сортування Шелла
void sort (one_elem
mas [], int num);
// Обробка меню
int menu (int x, int
y, char * capt) (
int n, m;// Лічильники
int num;// Кількість пунктів
int k;// Вибраний пункт
char * pt;// Тимчасовий покажчик на символ
char c;// Лічені з клавіатури символ
// Обчислюємо кількість пунктів
num = strlen (capt)/20;
// Курсор на нульовий елемент
k = 0;
// Нескінченний цикл обробки
for (;;) (
// Вивід меню
pt = capt;
for (n = 0; n
gotoxy (x, y + n);
// зафарбовування пункту, на який вказує курсор
if (n == k) (
// зафарбовування
textbackground (12);
textcolor (14);
) else (
// Нормальний
textbackground (3);
textcolor (1);
)
cprintf ( "% d)", n +1);
for (m = 0; m <20; m + +)
cprintf ( "% c", * (pt ++));
)
textbackground (3);
textcolor (1);
// Опитування клавіатури
c = getch ();
if (! c)
c = getch ();
// Перевірка, не натиснута Чи клавіша з цифрою
if
(((c-'1 ')> = 0 )&&(( c-'1')
// Установка покажчика в залежності від натиснутою цифри
k = c-'1 ';
// Запис у буфер клавіатури символу ENTER
ungetch (13);
) else (
// Аналіз
switch (c) (
// На початок
case (72):
if (k> 0) k -; else k = num-1;
break;
// Вниз
case (80):
if (k <(num-1)) k + +; else k = 0;
break;
// Вихід з
ESC - повертається -1
case (27):
return -1;
// Вихід з
ENTER - повертається номер пункту
case (13):
return k;
)
)
)
)
// Введення даних
// повертає значення - кількість введених
елементів
// Вхідні параметри - вказівник на масив і номер
перший вводиться елемента
int input (one_elem
mas [], int stn) (
clrscr ();
//Очищення масиву
int x;// Індекс
int num;
//Кількість введених елементів
int n;// Лічильник
char a [100];
//Дані
// Введення кількості елементів
printf ( "Кількість вводяться елементів: ");
scanf ( "% d", & num);
printf ( "Введіть, строчки формату X: Слово
n ");
// Введення елементів
for (n = 0; n
scanf ( "% d:% s", & x, a);
mas [n + stn]. n = x;
strcpy (mas [n + stn]. st, a);
);
return num;
)
// Вивід масиву
// Вхідні параметри - вказівник на масив і
кількість елементів
void
output (one_elem mas [], int num) (
clrscr ();
int n;// Лічильник
printf ( "Вміст масиву: n ");
printf ( "Індекс Вміст n ");
// Вивід елементів
for
(n = 0; n
printf ( "% 5d% sn", mas [n]. n, mas [n]. st);
// Очікування ESC
gotoxy (1,24);
printf ( "Натисніть ESC для продовження ... ");
while
(getch ()! = 27);
)
// Сортування Шелла
void sort (one_elem
mas [], int num) (
int stp [4] = (9,5,3,1);//
Кроки сортування
int fs, mn, p;
//Перший, мінімальний і поточний елементи
int n;
//Лічильник
one_elem prm;
//Тимчасова мінлива
// Цикл сортування
for (n = 0; n <4; n + +) (
fs = 0;// Починати сортувати з початку
// Перебір всього масиву
while
(fs
// Пошук мінімального елементу
p = fs;
mn = fs;
while (p
if (mas [p]. n
p + = stp [n];
)
// Якщо мінімальний елемент відрізняється від початкової,
поміняти їх місцями
if (mn> fs) (
prm.n = mas [mn]. n;
strcpy (prm.st, mas [mn]. st);
mas [mn]. n = mas [fs]. n;
strcpy (mas [mn]. st, mas [fs]. st);
mas [fs]. n = prm.n;
strcpy (mas [fs]. st, prm.st);
)
fs + = stp [n];// Перехід до наступного елемента
)
)
)
// Основна програма
void main () (
one_elem mas [100];
//Масив
int num;//
Кількість елементів
int st;// Вибраний пункт меню
textbackground (0);
textcolor (15);
clrscr ();
do (
// Вивід меню
st = menu (30,5, "
Введення даних "
"Додавання даних"
"Виведення даних"
"Сортування Шелла"
"Вихід з програми"
"x0 ");
textbackground (0);
textcolor (15);
// Виконання дій в залежності від обраного
пункту
switch (st) (
// Введення даних
case (0):
num = input (mas, 0);
break;
// Додавання даних
case (1):
num + = input (mas, num);
break;
// Вивід масиву
case (2):
output (mas, num);
break;
// Сортування
case (3):
sort (mas, num);
break;
)
// Вихід по ESC або останнього пункту
) while
((st <4) & & (st! =- 1 ));
clrscr ();
)
ДОДАТОК 2
Результати роботи програми
Меню:
1) Введення
даних
2) Додавання
даних
3) Висновок
даних
4) Сортування
Шелла
5) Вихід з
програми
1) Введення даних:
Число вводяться елементів: 8
Вводите рядки формату X: Слово
0: sign
1001: else
3000: yes
1535: but
1: past
412: cell
99: alert
2888: object
3) Висновок даних:
Вміст масиву:
Індекс Вміст
0 sign
1001 else
3000 yes
1535 but
1 past
412 cell
99
alert
2888 object
Натисніть ESC для продовження ...
2) Додавання даних:
Число вводяться елементів: 1
Вводите рядки формату X: Слово
10000: hello
4) Сортування Шелла
3) Висновок даних:
Вміст масиву:
Індекс Вміст
0 sign
1 past
99
alert
412 cell
1001 else
1535 but
2888 object
3000 yes
10000 hello
Натисніть ESC для продовження ...
5) Вихід з програми
ДОДАТОК 3
Блок-схема алгоритму програми
Для підготовки даної роботи були використані
матеріали з сайту http://kurslab.chat.ru/
