Лабораторная работа №1 (Вариант 12)

2

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

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

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

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

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

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

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

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

на тему:

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

Студент

Ключанских А.С

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

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

Группа

АС-10

Принял

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

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

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

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

Липецк 2011

1. Задание

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

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

Метод выбора (1)

В процессе первого прохода в исходном массиве находятся минимальный элемент, который помещается на место первого элемента. Первый элемент помещается на место минимального. На втором и последующих проходах поиск и обмен повторяются для оставшихся после предыдущего прохода элементов (с позициями: на втором проходе – со второй по последнюю, на третьем проходе – с третьей по последнюю и т.д.) до тех пор, пока не будет отсортирована вся последовательность. Общее число сравнений составляет приблизительно 0,5 N², N – здесь и далее число элементов.

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

#include <stdio.h>

#include <conio.h>

#include <locale.h>

#include <stdlib.h>

#include <math.h>

#include <string.h>

void main(void)

{

setlocale(LC_ALL,"Russian");

int strings, kolvo_sym, N, r,Imin, i, j, k=0, *s, d;

char **Mass, **Mass_new, *Min, ch;

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

scanf("%d",&strings);

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

scanf("%d",&kolvo_sym);

N = (int)sqrt((double)strings);

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

if(!s){

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

getch();

exit(1);

}

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

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

Mass[i]=(char *)malloc((kolvo_sym+1)*sizeof(char)); //выделение памяти под исходный массив строк

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

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

Mass_new[i]=(char *)malloc((kolvo_sym+1)*sizeof(char)); //выделение памяти под отсортированный массив строк

if(!Mass)

{

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

getch();

exit(1);

}

if(!Mass_new)

{

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

getch();

exit(1);

}

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

{

error: printf("\nВведите %d строку: ",i+1);

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

{

ch=getche();

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

Mass[i][j]=ch;

else

{

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

goto error;

}

if(j==kolvo_sym-1) Mass[i][kolvo_sym]='\0';

}

}

for(r=1;r<=N;r++) // разбиваем массив на части и сортируем отдельно каждую из них методом выбора

{

for(i=(r-1)*strings/N;i<(r*strings/N)-1;i++)

{

Imin = i;

for(j=i+1;j<r*strings/N;j++)

if(strcmp(Mass[j],Mass[Imin])<0)

Imin = j;

Min = Mass[Imin];

Mass[Imin]=Mass[i];

Mass[i]= Min;

}

}

//теперь каждая часть массива отсортирована методом выбора, осталось реализовать слияние лент

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

s[i]=i*strings/N;

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

{

ch='z';

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

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

{

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

d=j;

}

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

k++;

s[d]+=1;

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

s[d]=-1;

}

printf("\n\nРезультаты сортировки:");

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

{

printf("\n");

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

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

}

free(s);

free(Mass);

free(Mass_new);

getch();

}

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

4. Вывод

В ходе выполнения данной лабораторной работы я приобрел навыки реализации алгоритмов внутренней и внешней сортировки.