Студопедия Главная Случайная страница Задать вопрос

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Титульный лист. Задание кафедры, соответствующее варианту. Задание кафедры, соответствующее варианту





Задание кафедры, соответствующее варианту.

12. Цель работы.

Краткие теоретические сведения.

Формализованный алгоритм.

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

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

17. Выводы по работе.

Задание

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

Таблица 5

Варианты заданий

№ п/п Ключ Запись   Метод внутренней сортировки
int ключ, char[], float Метод обмена
int[] только ключ Сортировка с помощью дерева
float ключ, float[], char[] Сортировка включением
float[] только ключ Сортировка разделением
char ключ, int[], char Сортировка разделением
char[] только ключ Метод обмена
int ключ, char, float Сортировка с помощью дерева
int[] только ключ Метод выбора
float ключ, int[], char Метод выбора
float[] только ключ Сортировка включением
char только ключ Сортировка включением
char[] только ключ Метод выбора
int ключ, char[] Сортировка включением
int[] только ключ Метод обмена
float ключ, char[], int Сортировка разделением
float[] только ключ Метод обмена
char ключ, char[], int Сортировка с помощью дерева
char[] только ключ Сортировка включением

 

Пример выполнения работы

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

Ключ – int

Запись – только ключ

Метод внутренней сортировки – Метод Шелла

 

Блок – схема программы представлена на рис. 9.

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

#include<stdio.h>

#include<windows.h>

#include<conio.h>

#include<math.h>

#include<string.h>

 

void shell(int *items, int count)

{

register int i, j, x, gap;

gap=(int)(count/2);

while(gap>0)

 

Рис. 9. Блок-схема программы

 

{

for(i=gap;i<count;i++)

{

x=items[i];

for(j=i-gap; (x < items[j]) && (j >= 0); j=j-gap)

{

items[j+gap] = items[j];

}

items[j+gap] = x;

}

gap=(int)(gap/2);

}

}

 

void main()

{

SYSTEMTIME tim;

GetSystemTime(&tim);

srand(tim.wMilliseconds);

int count,k=0,*source,**a,*b,*stek;

printf("Puts count elements:\t");

scanf("%d",&count);

 

int N=(int)ceil(sqrt((float)count));

source=(int*)malloc(sizeof(int)*count);

a=(int**)malloc(sizeof(int*)*N);

b=(int*)malloc(sizeof(int)*N);

stek=(int*)malloc(sizeof(int)*N);

for(int i=0;i<N;i++)

{

a[i]=(int*)malloc(sizeof(int));

b[i]=0;

}

for(int i=0;i<count;i++)

{

k=i%N;

source[i]=rand();

a[k]=(int*)realloc(a[k],sizeof(int)*(++b[k]));

a[k][b[k]-1]=source[i];

printf("%d ",source[i]);

}

printf("\n\n");

for(int i=0;i<N;i++)

{

shell(a[i],b[i]);

for(int j=0;j<b[i];j++)printf("%d\t",a[i][j]);

printf("\n");

}

printf("\n");

for(int i=count-1;i>-1;i--)

{

k=0;

if(b[0]>0)stek[0]=a[0][b[0]-1];

else

{

int j=0;

while((b[j]<=0)&&(j<N))j++;

j--;

stek[0]=a[j][b[j]-1];

b[0]=b[j];

b[j]=0;

}

for(int j=1;j<N;j++)

{

if(b[j]<=0)continue;

stek[j]=a[j][b[j]-1];

if(stek[j]>stek[0])

{

stek[0]=stek[j];

k=j;

}

}

source[i]=stek[0];

b[k]--;

}

for(int i=0;i<count;i++)printf("%d ",source[i]);

free(source);

getch();

}

 






Дата добавления: 2014-11-10; просмотров: 396. Нарушение авторских прав

Studopedia.info - Студопедия - 2014-2017 год . (0.017 сек.) русская версия | украинская версия