Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364139
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62791)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21319)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21692)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8692)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3462)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20644)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

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

Название: Сортировка массива методом Шелла
Раздел: Рефераты по информатике
Тип: реферат Добавлен 18:24:36 08 апреля 2011 Похожие работы
Просмотров: 125 Комментариев: 19 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

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

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

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

#include <stdlib.h>

#include <conio.h>

#include <string.h>

// Данные одного элемента массива

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<num;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')<num)) {

// Установка указателя в зависимости от нажатой цифры

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<num;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<num;n++)

printf("%5d %s\n",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<num) {

// Поиск минимального элемента

p=fs;

mn=fs;

while (p<num) {

if (mas[p].n<mas[mn].n) mn=p;

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

Блок–схема алгоритма программы

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Хватит париться. На сайте FAST-REFERAT.RU вам сделают любой реферат, курсовую или дипломную. Сам пользуюсь, и вам советую!
Никита15:55:58 05 ноября 2021
.
.15:55:57 05 ноября 2021
.
.15:55:55 05 ноября 2021
.
.15:55:52 05 ноября 2021
.
.15:55:49 05 ноября 2021

Смотреть все комментарии (19)
Работы, похожие на Реферат: Сортировка массива методом Шелла

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

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



Результаты(294152)
Комментарии (4230)
Copyright © 2005-2022 BestReferat.ru support@bestreferat.ru реклама на сайте

Рейтинг@Mail.ru