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


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

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

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

Выполнили: 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 мильонов к студенческой карме :

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

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