Реферат по предмету "Программирование"


Сортировка массива методом Шелла

Сортировка массива методом Шелла

Отчёт по практике

Выполнили: 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

 }

 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

 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

 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

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/


Не сдавайте скачаную работу преподавателю!
Данный реферат Вы можете использовать для подготовки курсовых проектов.

Поделись с друзьями, за репост + 100 мильонов к студенческой карме :

Пишем реферат самостоятельно:
! Как писать рефераты
Практические рекомендации по написанию студенческих рефератов.
! План реферата Краткий список разделов, отражающий структура и порядок работы над будующим рефератом.
! Введение реферата Вводная часть работы, в которой отражается цель и обозначается список задач.
! Заключение реферата В заключении подводятся итоги, описывается была ли достигнута поставленная цель, каковы результаты.
! Оформление рефератов Методические рекомендации по грамотному оформлению работы по ГОСТ.

Читайте также:
Виды рефератов Какими бывают рефераты по своему назначению и структуре.

Сейчас смотрят :

Реферат «динамика функционального состояния почек у больных ишемической болезнью сердца и хронической сердечной недостаточностью различных функциональных классов» 14. 00. 06- кардиология 14. 00. 15- патологическая анатомия
Реферат Гражданско-процессуальный порядок защиты прав граждан и организаций
Реферат Комплексна терапія мікроциркуляторних порушень у яснах хворих на хронічний генералізований пародонтит
Реферат Международная валютная система 3
Реферат Обзор нормативных документов по охране окружающей среды
Реферат 13 февраля 2011 года в 70 городах России будет дан старт XXIX открытой Всероссийской массовой лыжной гонки «Лыжня России 2011»
Реферат Администрация муромского района владимирской области постановление главы района
Реферат Чистые активы как индикатор финансовой устойчивости акционерного общества (на материалах ОАО "РусГидро")
Реферат Андрей Курейчик пьемонтский зверь
Реферат Анализ учения Адвентистов седьмого дня в свете исторического христианства
Реферат Анализ банковских рисков
Реферат Совершенствование производственно-хозяйственной деятельности (на примере УП "Рамок")
Реферат Маркетинговые стратегии на разных этапах жизненного цикла товара
Реферат Место и роль небанковских финансово-кредитных организаций в экономике РБ
Реферат Вознесением дарованные служения: дары благодати, пятигранное служение, виды пятигранного служения