2

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

ЛИПЕЦКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

КАФЕДРА АВТОМАТИЗИРОВАННЫХ СИСТЕМ УПРАВЛЕНИЯ

Лабораторная работа №1

по дисциплине

«Технология программирования»

на тему:

«Программирование алгоритмов сортировки»

Студент

подпись, дата

фамилия, инициалы

Группа

Принял

Домашнев П.А.

ученая степень, звание

подпись, дата

фамилия, инициалы

Липецк 2010

1. Задание

Осуществить программную реализацию сортировки информации заданного вида сбалансированным N-ленточным слиянием (в оперативной памяти), используя выбранные, в соответствии с вариантом, из табл. 1 алгоритм внутренней сортировки и формат исходных данных.

Вариант	ключ	Запись 0 – только ключ, 1 – ключ и другие данные различных типов	Метод внутренней сортировки
18	char[]	0	4

Метод подсчета (4)

Метод основан на том, что k+1-ый элемент упорядоченной последовательности превышает ровно k элементов, и следовательно занимает k+1-ую позицию. В процессе сортировки на каждом i-ом проходе i-ый элемент исходной последовательности попарно сравнивается со всеми остальными элементами. Инициализированный нулем перед началом прохода счетчик k увеличивается, если i-ый элемент оказался больше текущего. Таким образом, порядковый номер i-го элемента, по окончанию i-го прохода, равен k+1. Для сортировки последовательности из N элементов требуется N проходов, на каждом из которых выполняется N сравнений. Число сравнений равно N². Приведенный метод подсчета можно использовать, если достоверно известно, что в исходно последовательности нет записей с одинаковыми ключами.

2. Листинг программы

#include <stdio.h>

#include <conio.h>

#include <locale.h>

#include <stdlib.h>

#include <math.h>

void main()

{

setlocale(LC_ALL, "Russian");

int i,j,k,r,kolvo_strok=0, kolvo_sym=0,q,*Vsp,d,p, s[4];

char **Mass, ch, **Mass_new;

printf("Введите количество строк, такое, что kоличество/4=целому числу: ");

scanf("%d", &kolvo_strok);

printf("Введите количество символов в строке:");

scanf("%d", &kolvo_sym);

Mass=(char **)malloc(kolvo_strok*sizeof(char));

for(i=0;i<kolvo_strok;i++)

Mass[i]=(char *)malloc(kolvo_sym*sizeof(char));

Mass_new=(char **)malloc(kolvo_strok*sizeof(char));

for(i=0;i<kolvo_strok;i++)

Mass_new[i]=(char *)malloc(kolvo_sym*sizeof(char));

if(!Mass_new)

{

printf("Ошибка 0: память не выделена!");

getch();

exit(1);

}

if(!Mass)

{

printf("Ошибка 1: память не выделена!");

getch();

exit(1);

}

Vsp=(int *)malloc(kolvo_strok*sizeof(int));

if(!Vsp)

{

printf("Ошибка 2: память не выделена!");

getch();

exit(1);

}

for(i=0;i<kolvo_strok;i++)

{

re: printf("\nВведите %d символов английского алфавита %d-й строки: ",kolvo_sym,i+1);//ввод массива

for(j=0;j<kolvo_sym;j++)

{

ch=getch();

printf("%c",ch);

if((ch>=65)&&(ch<=122))

Mass[i][j]=ch;

else

{

printf("\nНеправильный ввод, повторите:");

goto re;

}

}

}

for(r=1;r<=4;r++)//сортировка четырех частей массива по отдельности

{

for(i=((r-1)*kolvo_strok/4);i<(r*kolvo_strok/4);i++)/*определение упорядоченных позиций в файлах*/

{

k=0;

for(j=((r-1)*kolvo_strok/4);j<(r*kolvo_strok/4);j++)

if(Mass[i][0]>Mass[j][0])

k++;

Vsp[i]=k;

}

p=0;

k=0;

for(i=((r-1)*kolvo_strok/4);i<(r*kolvo_strok/4);i++)//перестановка

{

for(j=((r-1)*kolvo_strok/4);j<(r*kolvo_strok/4);j++)

if(Vsp[j]==p)

d=j;

p++;

for(q=0;q<kolvo_sym;q++)

{

ch=Mass[d][q];

Mass[d][q]=Mass[i][q];

Mass[i][q]=ch;

}

k=Vsp[i];

Vsp[i]=Vsp[d];

Vsp[d]=k;

}

}

/*теперь мы получили массив, каждая из четырех частей которого упорядочена методом подсчета, теперь надо упорядочить весь массив, для этого используется способ слияния лент*/

for(i=0;i<4;i++)//инициализация счетчиков

s[i]=i*kolvo_strok/4;

k=0;

for(i=0;i<kolvo_strok;i++)//сортировка слинием лент

{

ch='z';

for(j=0;j<4;j++)//поиск наименьшего элемента

if((s[j]!=-1)&&(ch>=Mass[s[j]][0]))

{

ch=Mass[s[j]][0];

d=j;

}

for(j=0;j<kolvo_sym;j++)

Mass_new[k][j]=Mass[s[d]][j];//присвоение строки новому массиву

k++;

s[d]=s[d]+1;//увеличивание счетчика

if(s[d]==(d*kolvo_strok/4)+kolvo_strok/4)//если счетчик достиг предела

s[d]=-1;

}

for(i=0;i<kolvo_strok;i++)//вывод

{

printf("\n");

for(j=0;j<kolvo_sym;j++)

printf("%c",Mass_new[i][j]);

}

getch();

}

3. Контрольный пример

4. Блок-схема

5. Вывод

При выполнении данной лабораторной работы я получил навыки программирования методов сортировки.

6. Список использованной литературы

1. Шилдт Г. Искусство программирования на C++. БХВ.2005

2. Шилдт Г. C++ Руководство для начинающих. Вильямс.2005

3. Страуструп Б. Язык программирования С++. Специальное издание, 3-изд. Бином.2004