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

size было простым числом (см. Вирт Н., Алгоритмы + структуры данных = программы: Пер. с англ. М.: Мир, 1985. С. 305).

Разрешение конфликтов. Если строка в таблице рТаЫе, соот­ ветствующая заданному ключу Key Word, не содержит нужный эле­ мент, то имеет место конфликт. Это означает, что два или более элементов таблицы имеют ключи, отображающиеся в один и тот же хэш-индекс строки таблицы. Для разрешения конфликтов такого ро­ да существуют различные методы получения вторичных индексов.

Один из методов разрешения конфликтов состоит в просмотре одного за другим различных элементов таблицы, начиная со строки с индексом Hash( Key Word ), пока не будет найден нужный элемент или не встретится свободное, не заполненное место таблицы. По­ следнее означает отсутствие в таблице строки с заданным ключом. Этот метод называется открытой адресацией. Разумеется, что шаг просмотра элементов таблицы при вторичных пробах должен быть

постоянным. Одним из таких методов является метод линейного	ап­
робирования с открытой адресацией. Реализация этого метода	со­
держится в определении функции HashSearch.

Отметка в таблице свободных мест. Для этой цели можно, например, в первый символ ключа (байт) свободной строки таблицы записать символ пробела:

/ /	Отметка	строк		таблицы		как	свободных
fox:(	1 = О/	i	<	size/	i-h+	)
(	рТаЫе[	i	] . key [		О ]	= '	';

I

Начальная подготовка хэш-таблицы. При начальном запол­ нении хэш-таблицы также может иметь место конфликт. В связи с этим сделаем валсное замечание. При хэш-поиске и при начальной подготовке таблицы для разрешения конфликта следует использо­ вать один и тот эюе метод. В нашем примере таким методом явля­ ется метод линейного апробирования с открытой адресацией. Про­ тотип функции BeginTable, используемой для начального заполне­ ния хэш-таблицы, и ее определение имеются в примере, приведен­ ном в подразд. 17.2. Функция BeginTable является интерфейсной функцией.

Функция для поиска в хэш-таблице. Прототип функции

HashSearch и ее определение имеются в примере, приведенном вы­ ше в подразд. 17.2. Функция HashSearch также является интерфейс­ ной функцией. Обратите внимание на то, что функции BeginTable и

310

HashSearch очень похожи друг на друга.

Пример тестирования хэш-поиска в таблице имеется в подразд. 17.2 (см. функцию main).

Эффективность хэш-поиска. Проведенный для линейного апробирования анализ показал, что среднее значение числа проб при поиске (длина поиска)

WP ~	\-al2
	\-а '

где a = TabLen/size есть		коэффициент	заполненности		таблицы (табл.
30).
	Табл. 30. Эффективность хэш-поиска
а	0.1	0.2	0.3	0.5	0.9
L,,,	1.056	1.125	1.214	1.5	5.5

Из таблицы следует, что хэш-поиск имеет весьма высокую эф­ фективность. Но при этом важно понимать и недостатки данного метода.

1. Существенное повышение эффективности поиска достига­ ется только при большой избыточности таблицы.

2.Сложность удаления элемента из таблицы.

Взаключение отметим, что из перечисленных выше классиче­ ских задач прикладного программирования^ составляющих золотой багаж любого программиста - сортировка массивов, транспортная задача (задача коммивояжера), поиск в таблице, обработка списков, работа с очередями; сортировка файлов ) — мы рассмотрели решение первых трех классов задач прикладного программирования. Осталь­ ные задачи будут рассмотрены в следующем учебном пособии "Тех­ нология программирования" в связи с изучением и освоейием дру­ гих технологий программирования, таких как объектноориентированное программирование, программирование с исполь­ зованием библиотеки стандартных классов языка C++ и др. Учебное пособие "Технология программирования" предназначено для обес­ печения одноименной дисциплины, изучаемой в следующем, треть­ ем семестре в рамках подготовки бакалавров (направление 5502) и специалистов (направление 6519).

ЗП

18ОТВЕТЫ И РЕШЕНИЯ К УПРАЖНЕНИЯМ ДЛЯ САМОПРОВЕРКИ

18.1. Для подраздела 2.4.4

Ответ к упражнению	1.
retcode^l 1=17 j=123 с1=4 с2=5 сЗ=6 а=2400,000000
Ъ=172,000000
Ответ к упражнению	2.

Файл 2_4_4_2.СРР

2.Имеется следующий фрагмент Си-программы:

float		a;
±nt		i^	jr
cbSLr		cl,	c2r	c3;
±nt		retcode;
ch^jc		c4,	c5r	s[20]
Написать фрагмент программыг обеспечивающий чтение из
файлаf.dat		на магнитном диске			следующих	значений:
а = 1,5		1 = 21			j = -12	с1 =	'в'
с2 = 'е '		сЗ = 'с '			с4 ^ 'а'	с5 =	'н'
S = "Прочитанная-строка"
Как при этом будут выглядеть строки исходных данных в
файле	f.dat?
Предусмотреть контроль корректности значений^ возвращае­
мых функциями библиотеки Си.
В. Давыдов^ консольное приложение (Microsoft							Visual
Studio	C++	6.О)
*/
#include	<stdio.h>			// STanDart Input		Output -	для

//стандартных функций ввода-

//вывода

±nt main ( void )			// Возвращает О при успехе
{
float	а;
Int	i г j /
chctr	cl,	c2,	c3;
char	c4,	c5^	s[20];

312

FILE				*f_in;		// Указатель на файл для					ввода
±пЬ			ret code;			//	Возвращаемое значение для функции
							//			fscanf
//	Открываем файл f.dat							для		чтения
f_±n		= fopen(			"f.dat",		"г"		);
±f(	f__in == NULL )
{	printf(				"\n Файл f.dat				для чтения не открыт. " );
	jzebvucn 1;
}
//	Чтение данных					из файла				f.dat
retcode			= fscanf(			f_±n,		" a = %f 1 = %d j = %d "
		"cl	= \'%c\' c2 = \'%c\'							c3 = \'%c\' "
	"c4		^	\'%c\'		c5 = \*%c\^				S = \"%s\" ",
	&a, &i, &j, &cl, &c2, &c3, &c4, &c5, s );
if(	retcode			!= 9 )
{	printf(			"\n Данные прочитаны с ошибками."							);
	retvim 2;
}
//	Закрываем				файл ввода
fclose		( f_in			) ;

z-etiLm О;

Ответ к упражнению 3.

Файл 2_4_4_З.СРР 3. В программе имеются следующие переменные:

±nt d = 254/

float f = 1234.56;

cha.r *str = "Строка символов"/

Используя, по возможности, только эти данные написать программу, выводящую в файл результатов file.out следующие строки (в них символ ^ обозначает местоположение пробела) :

1+254^''^^^''^]^'^[^^''''^254] (^^^^^1234.5600) ^^ (1234.5600^^'^^^) /Стр/^^/м/

В.	Давыдов, консольное			приложение	(Microsoft	Visual
Studio	C++ 6. 0)
^Include	<stdlo.h>	//	STanDart Input		Output	- для
			//	стандартных функций ввода-

313

//

вывода

±nt main

( void

)

//

Возвращает О при

успехе

{

d

=

254;

int

float

f

=

1234.56f;

символов"/

cha,r

*str

=

"Строка

файл

для

взвода

FILE

*f_out;

//

Указатель

на

//

Открываем

файл

file,out

для

записи

f_out

= fopen(

"file.out"г

"w"

)

;

±f(

f_out

== NULL

)

{

printf

(

"\n

Файл file,

out

для

записи

не

открыт.

" ) .

return

1;

}

//

Вывод

данных

в

файл

file.out

fprintf(

f_out,

"[%+-lld],%2c[%8d]

",

\n

(%14.

4f)

%2c("

f,

"%-14.4f)\n/%.3s/%2c/%c/\n

6

]r

d,

str[

)

6

],

d,

str[

6 ; ,

f,

str,

strf

str[

9 ]

;

//Закрываем файл взвода

fclose

( f_out

) ;

return 0;

18.2. Для подраздела 3.8

	Ответ				к упражнению	1.
	Будет напечатано:
i=l	j=3
next	(		)=11
last	(	)=0
nw(i+j)			=9
	Ответ				к упражнению	2.
	Будет напечатано:
i ==		3	j	=	1
next	(	i	)	=	3
last	(	i	)		=10
i =	3	j	^	2	4
next	(	i	)	=
last	(	i	)	=	9

314

18.3. Для подраздела 3.9.3

Ответ купрамснению 1,

Фаил		3_ 9_3_1.		срр
Написать			прототип^		определение			функции и		пример	вызова
функции	для		вычисления		суммы		элементов		одномерного		массива
х[ N ]	(N	=	50)	целого	типа ^		имеющих		нечетные	индексы
В.	Давыдов,			Консольное		приложение			(Microsoft		Visual
Studio	C++		6.О)
V
^include		<stdio.h>				//	Для	ввода-вывода
^define	N50					//	Размер	массива

//Прототип

±nt	SumUneven(				±nt	ar[	] ) ;
±nt	main		(	void	)		//	Возвращает 0 при	успехе
{	Int				a[	N ] ;
	//	Инициализация				i<N;	массива
	toj:	(	±zib		i=0/		i + +	)
			a[	i	] ^	1;

//Вызов функции

±nt

s = SumUneven(

a ) ;

//Печать найденной суммы

printf(	" Сумма	значений		элементов	массива	с	нечетными "
	"индексами		= %d	\л", s ) ;
x-etujm	0;
}
// Вычисление	суммы	значений		элементов	вектора	с	нечетными

//индексами

Int SumUneven (				//	Возвращает	сумму		значений
				//	элементов	с	нечетными
±пЬ	аг[	]	)	//	индексами			массив
				//	Обрабатываемый
{
int	Sum	=	0;	//	Искомая сумма

//Поиск суммы

£ог( Int i=l; i<N; i+=2 )

315

Sum

+=

ar[

i

]/

return

Sum/

}

Ответ

к упражнению

2.

Файл 3_9_3_2.

срр

Написать

прототип,

определение

функции

и

пример

вызова

функции

для

получения

одномерного

массива

],

z[

N ]

(N

= 40) из

двух заданных массивов

целого

типа

х[

N

у[

N

]

по

правилу:

z[

i ]

:=

тах{ х[ ±

],

у[

±

]

}

В.

Давыдов.

Консольное

приложение

(Microsoft

Visual

Studio

C+-h 6, О)

*/

^include

<stdio.h>

//

Для

ввода-вывода

^define

N40

//

Размер

массивов

//Прототип

void.	CreateArr		( Int	x[	], int	y[ 7, Int	z[ ]	) ;
int	main ( void		)		//	Возвращает	0 при	успехе
{	±nt				x[N],y[N],z[N];
	//	Инициализация		исходных		массивов
	£or(	int	i=--0;	i<N;	i + + )

{

x[ i ] = 1; y[ i ] = 0;

}

//Вызов функции

CreateArr(			x, y,		z	) ;
retujm		0;
}
// Формирование				массива
void	CreateArr(		X [	7,			//	Исходные
int
int			y[	],			//	массивы	массив
int			z[	] )			//	Формируемый
{	Формирование				массива
//
for(	int	i=0;		i<N;		i+=2		)
{	if(	x[	i	]>y[	i	7	;
		z[	i	] =	x[	i	];

316

else

z[ i ] = y[ ± ];

}

18.4. Для

подраздела 3.9.6

Ответ

к упражнению

1,

/*

Файл

3_9_3_2, срр

из

1.

В

текстовом

файле

"ctrl4,

dat"

имеется

15

строк,

каждая

которых

имеет

следующий

формат:

Здесь

"число_1"

число_

1

число_ 2

фигуры

(1 -

2

определяет

вид

геометрической

квадрат,

-

круг)

, а "число_2"

-

параметр

фигуры

(при

"чис-

ло_1"

=

1

~

длина

стороны,

а при "число_2"

= 2

-

радиус) .

1.1.

Написать

определение

массива

структур

для

хранения

указанных

сведений

о

геометрических

фигурах.

Каждый

элемент

массива

должен

иметь

следующие

поля:

*

имя

фигуры;

или

радиус;

* длина

стороны

*

площадь

фигуры.

1.2.Написать фрагмент программы для чтения из файла на

магнитном диске "ctг14.dat"	информации о геометрических	фигу­
рах.

1.3.Написать фрагмент программы, вычисляющий площади

геометрических фигур.

1.4.Написать фрагмент программы, печатающий в файл

"ctrl4.out"

параметры

геометрических

фигур.

Сведения

об

от­

дельных

фигурах

располагаются

в

отдельной

строке и

имеют

вид:

круг:

радиус=

. . . ,

площадь= . . .

квадрат:

длина

или

. . . , площадь= . . .

стороны=

Предусмотреть

контроль

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

значений,

возвращае­

мых функциями

библиотеки

Си,

указать

какие

включаемые

файлы

требует

представленный

фрагмент.

В.

Давыдов.

Консольное

приложение

(Microsoft

Visual

Studio

C++ 6.0)

V

^include

<stdlo.h>

//

Для

ввода-вывода

^include

<string.h>

//

Для

строковых

функций

#define

N15

//

Размер массива

структур

int main

( void

)

//

Возвращает

О при

успехе

(

317

// Определение		массива		фигур
sbiract	GeomFigure
{	name [ 8		];//	Название	фигуры
cbai:						стороны
double	pa ram;		//	Параметр фигуры: длина
double	square/		//	или	радиус
			//	Площадь	фигуры

)

агг[

N

];

//

Массив

геометрических

фигур

//

Заполнение

массива

структур

со

сведениями

о

//

геометрических

фигурах

и вычисление

их

площадей

FILE

*f__ln;

//

Указатель

на

файл

для

ввода

//

Открываем

файл

ctrl4,dat

для

чтения

f__in

= fopen(

"ctrl4,dat",

"г" ) ;

±£(

f_±n

== NULL )

{

Файл

ctrl4.

dat

для

чтения

не

открыт.

" ) ;

print

f

(

"\n

jretuxn

1;

}

±zib

Tag;

//

1 -

квадрат^

2

-

круг

double

pa ram;

//

Параметр

фигуры

for(

±nt

1=0;

KN;

1 ++)

{

±f(

fscanf(

f_ln,

" %d %lf",

&Tag,

&param

) != 2

)

{

printf(

"\n

Ошибка

чтения

"

) ;

return

2;

}

switch

(

Tag

)

{

1 :

ca.se

(

arr[

i

J.name,

"Квадрат"

) ;

strcpy

arr[

1

] .pa ram

= pa

ram;

arr[

1

]. square

= pa ram "&param;

case

break;

2:

arr[

1

J.name^

"Круг"

)

;

strcpy(

1

arr[

].pa

ram

= pa

ram;

arr[

1

].square

=

3.141592*param*param;

break;

default:

3;

}

return

}

//Закрываем файл чтения

fclose		( f_in		) ;
//	Печать		сведений		о геометрических		фигурах
FILE			*f_out;		//	Указатель	на файл для	вывода
//	Открываем			файл	ctrl4.out	для	записи
f_out		= fopen(		"ctrl4.out",		"w" )	;
lf(		f out	== NULL		)

318

prlntf

( "\n

Файл

ctrl4.

out

для

записи

не открыт. " )

;

jretujrn

4;

}

fo3z( 1=0/

KN/

1++)

{

"Квадрат"

)

)

±£( !strcmp

( arrf

1 ] . name,

{

f_out,

"\n

Квадрат:

длина

стороны=%1д,

"

fprlntf(

"площадь

= %1д

",

arr[

1

]

,param,

}

arrf

1 ]. square

)

;

else

{

f_out,

"\n

круг:

радиус=%1д,

"

fprlntf(

1

"площадь=%1д

",

arr[

]

.param,

arr[

1 ]. square

)

;

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

fclose

( f_out

) ;

retuim 0;

18.5. Для подраздела 4.12

Ответ к упражнению 1 (рис. 100).

Нет

Нет

Рис. 100. Ответ к упражнению 1

Ответ к упралснению 2.

±f( a<=b )

к=п;

319