Давыдов В.Г. - Программирование и основы алгоритмизации - 2003

//

задается;

ArgV[ 1 ] - файл ввода; ArgVf 2 ] - файл

//вывода)

сЪаг

*ArgV[

]

)

{

Проверка

числа

аргументов

командной

строки

//

±f(

ArдС

/= 3 ;

{

printf(

В

командной

строке

должно

быть

три аргумента:

"

"\п Ошибка

5.

"\л Имя_проекта.

ехе

имя_файла_ввода

имя_файла__вывода

\п" )

;

}

ех11

(

5

)

;

//

Размещение

массивов

в

динамической

памяти:

динамической

//

а, al

-

указатели

на

начало массивов

в

//

памяти;

S,

9

-

размеры

массивов

AllocArrDMf

аггг

8

)

;

//Для сортировки простыми включениями

AllocArrDMl(

arrl,

9 ) ;

//Сортировка массива простым выбором

ReadArr	(	arr,	ArgV[	1 ]	) ;	массива простым			"
WriteArr	(	arrг	"\n	до	Сортировка
"выбором.			Массив		сортировки	\п	'\ ArgV[	2 ],
"w"	) ;
SelectSort	(	( arr ) ;					Массив	после	"
WriteArr		arr,	"\n	", ArgVf 2 ], "a" )
"сортировки			\n				;

//Сортировка массива простыми включениями

ReadArrl

(

arrl,

ArgV[

1 ]

)

;

массива

простыми

"

WriteArrl

( arrl,

"\n\n

до

Сортировка

"включениями.

Массив

сортировки

\п

",

ArgV[

2

],

"а "

)

;

arrl

)

;

InsertSort

(

Массив

после

"

WriteArrl

( arrl,

"\n

2

],

"а"

)

;

"сортировки

\п

", ArgV[

// Сортировка

массива

методом

"пузырька"

ReadArr (

(

arr,

ArgV

[ 1

] )

;

массива

методом

"

WriteArr

arr,

"\n\n

Сортировка

],

"\"пузырька\".

Массив

до

сортировки

\п

",

ArgV[

2

"а "

)

;

arr

) ;

BubbleSort(

Массив после

"

WriteArr(

arr,

"\п

",

ArgV[

2

],

"а"

)

"сортировки

\п

;

//Сортировка массива сложным выбором

ReadArr	( arr,	ArgV [	1 ] ) ;
WriteArr(	arr,	"\n\n	Сортировка массива сложным "

230

"выбором.		Массив	до сортировки	\п	", ArgVf	2 ],
"а "	) ;	) ;
TreeSort(	arr				Массив	после "
WriteArr(	arr,	"\n	ArgV[ 2 ],	"а"
"сортировки		\п ",			) ;

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

ReadArr(	arr,		ArgV[	1	] ) ;				массива	методом	"
WriteArr	(	arr,	"\n\n	до	Сортировка
"Шелла.		Массив			сортировки		\п	",	ArgV[ 2	], "а"	) ;
ShellSort	(	arr	) ;						Массив	после	"
WriteArr	(	arr,	"\n	",	ArgV[ 2	],	"а"	) ;
"сортировки			\п
// Сортировка			массива		методом	Хоора		(не	рекурсивный

//вариант)

ReadArr

( arr,

ArgV[

1

] )

;

Сортировка

массива

методом

"

WriteArr

(

arr,

"\n\n

до

"Хоора.

Массив

сортировки

\п

",

ArgV[

2

],

"а"

)

;

Quicksort(

(

arr

) ;

Массив

после

"

WriteArr

arr,

"\n

",

ArgVl

2

],

"а"

)

;

"сортировки

\п

// Сортировка

массива

методом

Хоора

(рекурсивный

вариант)

ReadArr

( arr,

ArgV[

1

] )

;

Рекурсивная

сортировка

"

WriteArr

(

arr,

"\n\n

до

;

"Хоора.

Массив

сортировки

\п

",

ArgV[

2

],

"а"

)

QuickSortl

( ) ;

"\п

Массив

после

"

WriteArr

(

arr,

",

ArgV[

2

],

"а"

)

;

"сортировки

\п

//ккккккккккккккккккккккккккккккккккккккккккккккккккккккк

//

Освобождение

динамической

памяти,

занятой

массивами

FreeArrDM(

arr

) ;

FreeArrDM(

arrI ; ;

;

xetujrn

0;

/*

SortArr.h.

Подключение

стандартных

заголовочных

фай­

Файл

лов,

объявление

объектов

с описателями

класса

хранения

"внеш­

ний",

типов

элементов

сортируемого

массива,

стека

и

прототи­

пов

функций.

Используется

как

заголовочный

файл

в

программном

проекте

для

сортировки

массивов.

Visual

C++ 6

Давыдов

В.Г.

Консольное

приложение.

V

// Предотвращение

возможности

многократного

подключения

#ifndef

SORTARR__H

^define

SORTARR Н

231

^include			<stdio.h>	// Для ввода-вывода
^include			<stdlib.h>	//		Для exit ( )
const		±nt M = 16;		//		Размер стека отложенных
					//	сегментов: >=	(1од2(size)+1)
//	Структурный тип для элемента массива
struct ELEMENT
{	±nt		key;	// Ключ сортировки
	//	Описание других				компонент элемента
}	;
//	Объявления внешних объектов
extern ELEMENT
			*arr;	//	Указатель на сортируемый массив
extern ±nt size;				//	Размер сортируемого		массива
//	Указатель на сортируемый массив для сортировки
//	простыми вставками
extern ELEMENT
			*arrl;
extern ±nt sizel;				//	Увеличенный на единицу размер

//сортируемого массива

//Структурный тип для элемента стека

struct STACK

{		±nt	1;		//	Левая граница	сегмента
		±nt	г;		//	Правая граница сегмента
}	;
//	Прототипы функций (имена параметров в прототипе не
//		используются			и,	поэтому, мы их не записываем
void		AllocArrDM(			ELEMENT *&, int		);
void. AllocArrDMl ( ELEMENT *&, int							);
void		ReadArr(		ELEMENT [ ], char * );
void		ReadArrl ( ELEMENT [ ] , char * ) ;
void		SelectSort(			ELEMENT [ ] ) Г
void		WriteArr ( ELEMENT [ ], char *, char *, char * );
void		WriteArrl(		ELEMENT [ ], char			*, char *, char * );
void		InsertSort		( ELEMENT [ ] ) ;
void		BubbleSort(			ELEMENT [ ] );
void		TreeSort ( ELEMENT [ ] );
void		Sift(	int,	int, ELEMENT [ ] );
void		ShellSort		( ELEMENT [ ] );
void		Quicksort		( ELEMENT [ J );
void		Push ( int, int,				STACK [ ], int	& );
void		Pop ( int		Sc, int		&, STACK [ ],	int & );
void QuickSortl ( void ) ;
void Split ( int , int );
void		FreeArrDM( ELEMENT *& );

232

iendlf

_

Файл

AlocFreeDM.

и

cpp.

Размещение

одномерного

массива

в

ди­

намической

памяти

освобождение

динамической

памяти,

занятой

массивом.

в

программном

проекте

для

сортировки

масси­

Используется

вов.

В.Г.

Консольное

приложение.

Visual

C-h-h

6

V

Давыдов

// Включаемый

файл

программного

проекта

Unciude

"SortArr.h"

//

Размещение

сортируемого

массива

в

динамической

памяти

void

AllocArrDMi

//

Указатель

на

начало

массива

в

ELEMENT

*&arr,

//

динамической

памяти

(передаем

±пЬ

S

)

//

по

ссылке

- это

ответ)

//

Число

элементов

массива

{

//

Контроль

корректности

размера

массива

±f(

S < 2

)

{

printf

(

"\п

Предупреждение

10.

Массив

должен

"

''

"содержать

более

двух

элементов

\п

(задан

размер,

"

равный

%d) . Принимается

размер

массива,

",

равный'^

S =

"

2.

\п

Выполнение

программы

продолжается

s

) /

}

2/

//

Размещение

массива

в

динамической

памяти

агг

= new

ELEMENT[

s

] ;

±£(

arr

-= NULL

)

{

printf(

"\n

Ошибка

20.

Размещение

массива в

"

"динамической

памяти не

выполнено

");

exit

(

20

)

;

}

//

Инициализация

массива

нулевыми

значениями

£ог

(

int

[

1 = 0;

i<s;

i4-+

)

arr

1 ] . key

=

0;

//

Инициализация

размера

массива

size

=

s;

}

2retuz*n/

//

Размещение

массива

в

динамической

памяти

для

сортировки

//

простым

выбором

233

void

AllocArrDMl

(

ELEMENT

*&arrl,

//

Указатель

на

начало

массива

в

//

динамической

памяти

(передаем

±nt

//

по

ссылке

-

это

ответ)

S

)

//

Число

элементов

массива

{

//

Контроль

корректности

размера

массива

±£(

S

<

3

)

{

print

f

(

"\п

Предупреждение

10.

Массив

должен

"

"содержать

более

трех

элементов

\п (задан

"

"размер,

равный

%d) .

Принимается

размер

"

"массива

г равный

3,\п

Выполнение

программы

S

=

3;

"продолжается

" ) ;

}

//

Размещение

массива

в

динамической

памяти

arrl

=

new

ELEMENT[

s

];

±f(

arrl

==

NULL

)

(

printf(

"\n

Ошибка

20.

Размещение

массива

в

"

"динамической

памяти

не

выполнено

"

) ;

exit

(

20

)

;

}

//

Инициализация

массива

нулевыми

значениями

for(

int

i = 0;

i<s;

i-h-h

)

arrl[

i

] . key

=

0;

//

Инициализация

размера

массива

sizel

=

s;

}

return;

//

Освобождение

динамической

памяти,

занятой

массивом

void

FreeArrDM

(

ELEMENT

*&arr

)

//

Указатель

на

начало

массива

в

//

динамической

памяти

(передаем

//

по

ссылке

-

это

и

ответ)

{

±f(

arr

!=

NULL

)

{

delete

[

]

arr;

arr

NULL;

retvLrn;

Файл

SortlnOut.срр.

Функции

чтения

значений

элементов

мас­

сива

из

файла

данных

и печати

их

значений

в файл

результатов.

234

Используется

в

программном

проекте

для

сортировки

масси­

вов.

Давыдов

В.Г.

Консольное

приложение^

Visual

C++ 6

V

// Включаемый

файл

программного

проекта

§include

"SortArr.h"

// Чтение

значений

элементов

массива

из

файла

данных

void

ReadArr

(

arr[

] ,

//

Сортируемый

массив

ELEMENT

//

Указатель

на

имя

файла

с исходными

данными

cha.r

*pInpFile

)

{

*pStrInp;

//

Указатель

на структуру

со

FILE

±nt

i,

//

сведениями

о

файле

ввода

// Индекс

элемента

массива

)

RetCode,

//

Возвращаемые

значения

fscanf(

RetCodel;//

//

или

их

сумма

fclose(

)

Возвращаемое

значение

//Открытие файла ввода данных

pStrlnp

=

fopen(

pInpFiler

"г"

) ;

±£(

pStrlnp

-= NULL )

{

Ошибка

30.

Файл

%s для

чтения

не

открыт"

printf(

"\n

"

\п",

pInpFile

)

;

exit

(

30

)

;

}

//

Ввод

значений

элементов

массива

Ret

Code

--= О;

<

size;

i++

)

for(

i =

0;

1

{

RetCode

+= fscanf(

pStrlnp,

"

arr[ i

].key

)

)

;

}

%d", &(

RetCode

<

size )

±f(

{

printf(

"\n

Ошибка

40.

Ошибка

чтения

данных

из

файла"

"

%s

\п",

pInpFile

) ;

exit

(

40

)

;

}

//Закрытие файла ввода

RetCodel	= fclose(			pStrlnp	) ;
±f( RetCodel		== EOF )
{		"\n	Ошибка 50.		Файл %s не закрыт \n ",
printf(
exit	( 50	pInpFile		) ;
		)	;

}

235

return/

}

// Чтение значений

элементов

массива

из

файла данных

для

//

сортировки

простыми

включениями

void.

ReadArrl (

arrl

[ ],

//

Сортируемый

массив

ELEMENT

//

Указатель

на

имя

файла с исходными

данными

char

*pInpFile

)

{

*pStrInp;

//

Указатель

на

структуру

со

FILE

int

i,

//

сведениями

о

файле

ввода

// Индекс

элемента

массива

)

RetCode^

//

Возвращаемые

значения

fscanf(

RetCodel;

//

или

их

сумма

f close (

)

\

//

Возвраш.аемое

значение

//Открытие файла ввода данных

pStrlnp

=

fopen(

pInpFile,

"г" )

;

±f(

pStrlnp

-= NULL

)

{

printf(

"\n

Ошибка

30.

Файл

%s для

чтения

не "

exit

(

30

"открыт

\л", pInpFile

) ;

)

;

}

//

Ввод

значений

элементов

массива

~

обратите

внимание на

//

то,

что

первый

элемент

массива

(служебный

-

//

"барьер")

не

заполняется

Ret Code

=

О;

1 < size;

i++

)

fori

i = 0;

{

RetCode

+= fscanf(

pStrlnp,

"

%d",

&(

arrl[

i+1

J.key

) ) /

}

±f(

RetCode

< size

)

{

prmtf

(

"\n

Ошибка

40.

Ошибка

чтения

данных

из "

"файла

%s

\п",

pInpFile

)

;

exit

(

4 0

)

;

}

//Закрытие файла ввода

RetCodel	= fclose			( pStrlnp	) ;
±f( RetCodel		=- EOF )
{		"\n	Ошибка 50.		Файл %s не закрыт \n ",
prmtf(
		pInpFile		) ;
exit	( 50	)	;

}

return/

236

// Печать значений		элементов		массива	в файл		результатов
void. Wri teArr	(	]^	//	Сортируемый		массив
ELEMENT	arr[								о
char	'^'pMSG^		//	Указатель	на	строку-сообщение
			//	печатаемом		массиве
char	*pOutFile^//		//	Указатель	на		имя.расширение
				файла	результатов
char	*Mode )		//	Указатель	на	режим открытия			файла
{	*pStrOut;		//	Указатель	на	структуру		со
FILE
	2,		//	сведениями		о	файле	результатов
int			// Индекс элемента				массива		)
	RetCodel;		//	Возвращаемое		значение		fclose(

//Открытие файла вывода

pStrOut

=

fopen

(

pOutFlle,

Mode

) ;

±£(

pStrOut

= - NULL

)

{

Ошибка

60.

Файл

%s для

вывода

не '

printf(

"\n

"открыт

\л", pOutFile

) /

exit(

60

) ;

}

//

Печать

значений

элементов

массива

с

заголовком

fprintf(

pStrOut,

pMSG

) ;

)

tor(

1

= 0;

i <

size/

i++

{

//

Элементы

выводятся

по

6

в

каждой

строке

из

//

расчета

по

10

позиций

на

каждый

элемент

fprintf(

pStrOut,

"%10d",

arr[

i

].key

) ;

xf(

(

(

i-hl

)

%

6

) == 0

)

{

fprintf(

pStrOut,

"\n

"

)

;

}

}

//Закрытие файла вывода

	RetCodel	=	fclose(		pStrOut			) ;
	±f( RetCodel		== EOF			)
	{		"\n		Ошибка		70.	Файл	%s	не закрыт \n
	printf(
	exit	(	pOutFile			) ;
			70 ) /
}	return;
//	Печать значений			элементов			массива		в	файл результатов	для
//	сортировки		простыми				включениями
void	WriteArrl(			[	] г	//	Сортируемый			массив
	ELEMENT		arrl

237

char	*pMSG,	// Указатель на строку-сообщение о
		//	печатаемом массиве

cha.2: *pOutFile, // Указатель на имя .расширение файла

//результатов

cbajT	*Mode )	//	Указатель	на режим открытия файла
FILE	*pStrOut;	//	Указатель	на	структуру		со
±пЬ	i,	//	сведениями		о	файле	результатов
		// Индекс элемента				массива
	RetCodel;	//	Возвращаемое		значение		fclose( )

//Открытие файла вывода

pStrOut	= fopen		( pOutFile,	Mode	) ;
±f( pStrOut		== NULL )
{
printf(		"\n	Ошибка 60.	Файл	%s для вывода не "
		"открыт \л", pOutFlle ) /
exit	(	60 ) ;

}

//Печать значений элементов массива с заголовком

fprintf(		pStrOut,	pMSG ) ;
for(	i	= 1; i <	sizel; i-h-h )
{	//	Элементы выводятся по 6 в каждой строке из расчета

//по 10 позиций на каждый элемент

fprintf(	pStrOut, "%10d",		arrlf i ].key ) ;
±f( ( 1	% 6 ) == 0 )
{		"\л	" ) /
fprintf ( pStrOut,

}

}

//Закрытие файла вывода

	RetCodel		= fclose(		pStrOut		) ;
	±f( RetCodel			== EOF )
	{
	printf(			"\n Ошибка 10.			Файл %s не	закрыт \n ",
				pOutFile		) ;
	exit		( 70	) ;
	}
	return/
}
	Файл	SortArr.cpp.
	Функции	сортировки			динамически размещенного массива по не­
убыванию:
*	простая	сортировка			массива		выбором;
*	простая	сортировка			массива		обменом;
*	простая	сортировка			массива		вставками;
*	сортировка		массива		с	помощью двоичного		дерева;
*	сортировка		Шелла;
*	не рекурсивная			сортировка Хоора;

238

'*'

рекурсивная

сортировка

Хоора.

вов.

Используется

в

программном

проекте

для

сортировки

масси­

Давыдов

В.Г.

Консольное

приложение,

Visual

C++ 6

V

//

Включаемый

файл

программного

проекта

^include

"SortArr.h"

//

Определения

объектов

с

описателем

класса

хранения

внешний.

//

Их объявление

имеется

в

заголовочном

файле проекта

и эти

//

объекты

доступны

в

других

файлах

проекта

ELEMENT	*arr/	//	Указатель	на	сортируемый	массив
±nt	size;	//	Размер	сортируемого		массива
ELEMENT	*arrl;	//	Указатель	на	сортируемый	массив
		//	для простой		сортировки

//вставками

int		sizel;	//	Увеличенный		на	единицу	размер
			//	сортируемого			массива	для
			//	простой		сортировки		вставками
//	Эти объекты	определяем	в	в данном	месте,		чтобы	при
//	рекурсивных	вызовах		сортировке		Хоора	они	не

//создавались заново

ELEMENT

сору,

//

Копия

элемента

массива

median/

//

Медиана

разделяемого

сегмента

в

//

сортировке

Хоора

int

1

,

//

Индекс

кандидата

на

обмен

слева

J/

//

Индекс

кандидата

на

обмен

справа

//

в

сортировке

Хоора

//

Сортировка

массива

простым

выбором

-

по

неубыванию

void

SelectSort

(

{

ELEMENT

arrf

]

)

//

Сортируемый

массив

//

Индекс

последнего

элемента

из

JLXm

•LJr

indmax.

//

пока

неупорядоченных

//

Индекс

наибольшего

элемента

среди

//

1..L

к;

//

Индекс

анализируемого

элемента

ELEMENT

max;

//

Для

наибольшего

элемента

среди

//

1.

.L

//

Просмотр

неотсортированных

начальных

сегментов

массива

//

(вначале

-

весь

массив,

затем

-

сегмент

из

первых

//

size-1

элементов

и

т.д.)

£ог(

L

^

size-1;

L

>= 1;

L--

)

{

//

Присвоить

indmax

индекс

элемента

массива

//

наибольшим

значением

ключа

из

агг[

О ]. .агг[

L ]

indmax

=

О;

max

=

arr[

О

];

for(

к =

1;

к

<=

L;

к++

)

239