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

графической форме,

Особые случаи

8.14. Удаление элемента перед каждым элементом ЛС, содержащим заданное значение

Реализация дана на рис. 53.

1

t start

w

t

start

операции, представленная в

До выполнения операции Общий случай

find					а) Start = NULL,
			^	NULL	б) Start->next =
	w	w			NULL,
	После выполнения операции
find					а) Вывод
					сообщения и
		2:		NULL	возврат из
					функции
		w	w
t	t				б) Вывод
					сообщения и
					возврат из
cur		1 • del = cur->next;
					функции
2: cur->next = del->next;

3. delete del;

4:если после удаления текущий элемент - последний, то выполняется выход из функции

Рис. 52. Удаление элемента после каждого элемента ЛС, содержащего заданное значение

Прототип функции BeforDel, выполняющей удаление элемен­ та перед каждым элементом ЛС, содержащим заданное значение find, ее определение и пример вызова содержатся в программном проекте, приведенном в подразд. 8.1,

При реализации операции удаления производится просмотр элементов линейного списка, начиная со второго элемента до по­ следнего элемента списка.

Отличительной особенностью операции является то, что если удаление элемента выполнено, то продвижение указателя на предпредыдущий элемент не требуется. Указатель же на текущий эле­ мент должен продвигаться всегда.

Другой особенностью операции является то, что реализация шагов 1: и 2: в случае, когда текущий элемент является вторым в ЛС, отличаются (см. рис. 53).

170

а) Вывод сообщения и возврат из функции

б) Вывод сообщения и возврат из функции

8.15. Зачем нужен линейный список

Для хранения и обработки информации наряду с ЛС можно использовать и массивы. Например, вместо ЛС, приведенного на рис. 45, можно использовать символьный массив из пяти элементов, причем это сэкономило бы оперативную память. Значит ли это, что ЛС не следует использовать? Конечно же, нет!

" •

t Start

w

t

start

	До выполнения операции			Особые случаи
	Общий случай
		find		а) Start = NULL,
		,^	NULL	б) Start->next =
	... ^			NULL,
		w
	После выполнения операции
		find
	2:	w	NULL
t	t	t
pprev		cur

1 • del = pprev->next или del = Start, если текущий элемент в ЛС второй

2:pprev->next = del->next или Start = Start->next, если текущий элемент в ЛС второй

3:delete del,

Рис. 53. Удаление элемента перед каждым элементом ЛС, содержащим заданное значение

Например, использование ЛС обеспечивает следующие пре­ имущества:

•вставка или удаление элементов в ЛС происходит проще и быст­ рее (вставка или удаление элемента в начальную часть массива большого размера требует выполнения значительного объема ра­ боты);

•при работе с ЛС не требуется знать его максимальный размер (при размещении же массива надо заранее знать его требуемый размер или размещать массив максимального размера в расчете

171

на наихудший случай).

8.16. Упражнения для самопроверки

Определены следующие данные:

stjract ELEM		//	Структура	для	элемента	списка
{	dat;	//	Данное
±nt
struct	ELEM	//	Указатель	на	следующий	элемент
}	*next;
	*сиг,	//	Указатель	на	текущий	элемент
	*start/	//	списка	на	начало	списка
		//	Указатель
Во входном файле Is.dat			содержится некоторое количество це­

лых чисел, разделенных символами пробельной группы ( ' ', '\^', '\«' ).

1. Написать прототип, определение и пример вызова функции для ввода из входного файла имеющихся там чисел, представив вве­ денную информацию линейным списком, в котором каждый узел (динамически размещенная структура) содержит две компоненты. Первая компонента хранит данное (введенное число), а вторая - указывает адрес следующей структуры. При этом первое прочитан­ ное число Должно находиться в начале линейного списка. Исходные данные и результаты работы функции следует передавать через спи­ сок параметров.

С целью обработки ошибок предусмотреть контроль значений, возвращаемых функциями библиотеки языков Си/С++.

2.Дополнительно написать прототип, определение и пример вызова функции, которая в процессе просмотра списка выводит данные (числа) в файл на магнитном диске is.out. Требования к оформлению функции и обработке ошибок аналогичны указанным в

п.1 требованиям.

3.Дополнительно написать прототип, определение и пример вызова функции, которая разрушает линейный список. Требования к оформлению функции и обработке ошибок аналогичны указанным в пункте 1 требованиям.

9. ПРЕПРОЦЕССОР ЯЗЫКА Си/С++

Перед собственно компиляцией программы к ней применяется процедура предварительной обработки. Она выполняется програм­ мой, называемой препроцессором:

ПРЕдварительный ПРОЦЕССОР

Препроцессор расширяет возможности языка следующим.

1. Подстановкой имен (заменой символических аббревиатур на соответствующие значения), т.е. наличием макроопределений.

2.Включением файлов.

3.Условной компиляцией.

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

Наличие препроцессора сокращает затраты времени на разра­ ботку программ, обеспечивает создание переносимых, более читае­ мых и удобных для сопровождения и отладки программ.

9.1. Директивы препроцессора

Указания препроцессору вставляются в программу в виде ди­ ректив. Директивой служит строка, в первой позиции которой ука­ зан символ диеза "#". Допускается, хотя и не рекомендуется, нали­ чие предшествующих символу диеза пробелов и табуляторов. За символом диеза следует название директивы. Между ними допуска­ ется, хотя и не рекомендуется, произвольное число пробелов и/или табуляторов.

Директивы можно размещать в любом месте программы и их действие остается в силе вплоть до конца того файла, в котором они находятся.

9.2. Подстановка имен

Подстановка имени (макроопределение) представляет собой символическое имя, которое присваивается фрагменту программы (строке элементов языка). Когда впоследствии препроцессор обна-

173

руживает это символическое имя в программе, то он заменяет имя соответствующей строкой.

Для подстановки имен предусмотрены две директивы препро­ цессора:

•создать макроопределение (Ude/ine);

•удалить макроопределение, т.е. сделать его неопределенным

{Uundef).

Пример использования директивы Udefine приведен на рис. 54.

Признак директивы - его рекомендуется размещать в начале строки. Допускаются, но не рекомендуются, предшествующие пробелы и/или табуляторы

Служебное слово препроцессора.

По крайней мере один пробел или табулятор.

#define NULL ЛО'

I — Конец строки - завершает макроопределение (макроопределение должно размещаться в одной строке).

Текст макроопределения - любое число символов в пределах одной строки.

По крайней мере один пробел или табулятор

Имя макроопределения - любой идентификатор Для более легкого «узнавания» макроопределения рекомендуется использовать в нем только прописные буквы.

Между знаком диеза и служебным словом препроцессора допускаются, но не рекомендуются, пробелы и табуляторы.

Рис. 54. Структура директивы на примере директивы Udeflne

Приведем несколько примеров:

#define	SUCCES	1
^define	NULL	'\0'
^define	MAX_SIZE 50		макроопределение
^define	UNIX	// Пустое
^define	printf	myprintf

Приведенные примеры показывают, что, как указывалось вы­ ше, запись имени макроопределения прописными буквами не обяза-

174

тельна. Однако использование в именах макроопределения только прописных букв позволяет легко отличить макроопределения от других элементов программы.

Обратите внимание на то, что директивы включения препро­ цессора не требуют завершающей точки с запятой. При ее наличии точка с запятой войдет в текст макроопределения, замещающий имя макроопределения. Это может стать причиной ошибки.

Следующей, достаточно распространенной, ошибкой является включение пробелов в имя макроопределения, так как идентифика­ тор не может содержать пробелов. Следует помнить, что для пре­ процессора имя макроопределения заканчивается на первом же про­ беле или табуляторе. Все символы, следующие за ним, рассматри­ ваются как замещающая строка.

После определения имени

макроопределения

всякое

его вхоэю-

дение

в текст программы

(за исключением

вхождения

в

символьные

и строковые

константы)

будет

замещаться

связанной

с ним

стро­

кой

символов.

Примеры замещения макроопределений, созданных приведен­

ными выше директивами ^define.,

содержатся в табл. 24.

Табл. 24. Примеры замещения макроопределений

До препроцессора

После препроцессора

if(scanner

0 = =SUCCES)pnntf("Cmon\n

");

if (scanner

0==l)myprintf("Cmon

\n ");

struct

INDEXJNFO

index[MAX_SIZE];

struct INDEX JNFO

index[50];

ifOine[pos]=-^NULL)

if(line[pos]=='\0')

printf("3mo

NULLW):

myprintf("3mo

NULL\n"):

Обратите

внимание,

что

строка NULL

внутри

строковой

кон­

станты не подверглась замене.

Для отмены макроопределения можно воспользоваться

директивой Uundef, действие которой иллюстрирует табл. 25.

Отмена

подстановки

имени

макроопределения

с помощью

ди­

рективы

i^undef

остается

в силе

до конца

файла,

в

котором

оно

встретилось,

если только

это

имя

не будет

заново

определено

но­

вой директивой

i^define.

При использовании директивы Udefine можно указывать пара­ метры при имени макроопределения:

^include <stdio.h>

^define

AREA (г) (3 . 14* (г) * (г) )

175

//	Таблица	площадей			кругов
±nt	main (	void.	)
	float		radius		=	1.Of;
	printf	( "\n		Радиус		Площадь \n"	) ;
	while(	radius		<	10.5f	)
	{
	printf(			"%f		%f \ л " , radius,	AREA( radius	) ) .
	radius		-h= 1 . Of ;

геЬмхпл 0;

Табл. 25. Отмена макроопределения директивой i^undef

До препроцессора					После препроцессора
include	<stdio h>			Текст файла stdio.h после обработки его
Ые/гпе	print/myprintf			препроцессором
int main(	void )			ini main(	void)
\{				{
printf(	"Введите	дату:	");	myprintf( "Введите дату:		"),
^undefprintf				printf(	"Введите время-	");
printf(	"Введите	время:	"),
return	0,			return	0;
J				}

В этом примере второй аргумент AREA( radius ) в вызове функ­ ции ргш^/'заменяется на (Ъ.\4*(radius)*(radius)). Обратите внимание также, что в макроопределении не только параметр г, но и весь текст макроопределения заключены в круглые скобки. Эти скобки позволяют избежать ошибок из-за возможных побочных эффектов, связанных с приоритетами выполнения операций:

^include <stdio.h>

^define	AREA (г)	3.14*r*r
2.Of/AREA(radius)			заменяется	на
2.0f/3.14*radius*radius,			ошибка	на
AREA(start-end)			заменяется
3.14*start-end*start-end,			также ошибка
Директива		Udefine	моэюет содер^юатъ	в круглых	скобках не
только	один, но и любое		число параметров, разделенных		запятыми.

176

9.3. Включение файлов

Иногда один и тот же фрагмент программы встречается в не­ скольких файлах, образующих программу. Включение такого обще­ го фрагмента в несколько исходных файлов программы выполняется с помощью директивы

^include "путь_к_файлу"

			или
^include		<путь_к_файлу>
	Здесь путь_к_файлу		означает корректную запись вида
диск:	\ путь_по__ка талогам\		имя__файла_с_ра сширением
	Для включаемых файлов принято использовать расширение .И
или	.hpp.
	Если указанный в директиве файл будет найден, то строка с
директивой		Uinclude будет заменена содержимым этого файла. По­

иск включаемого файла выполняется в каталоге, указанном в дирек­ тиве ^include. Если

	диск:	\путь_по_каталогам\
отсутствует, то при использовании записи в форме:
• " п у т ь к ф а й л у "	поиск ведется сначала в текущем каталоге, а за­
тем в каталогах	включаемых файлов, определенных в интегриро­

ванной среде программирования;

•<путь к_файлу> поиск ведется сразу в каталогах, определенных в интегрированной среде программирования.

Между названием директивы и путем к файлу может нахо­

диться любое число пробелов и табуляторов, в том числе и не одно­ го, но рекомендуется использовать между ними один пробел.

Во включаемые файлы помещают директивы Uinclude; прото­ типы функций; определения встроенных {inline) функций; объявле­ ния {extern) данных, определенных в другом файле; определения {const) констант; перечисления {епит), директивы условной транс­ ляции {#ifndef, Uendif и др.), макроопределения {^define), имено­ ванные пространства имен {namespace), определения типов {class, struct), объявления и определения шаблонов {template), общие для нескольких исходных файлов, составляющих одну программу.

177

Хотя многие из перечисленных средств нами еще не рассматрива­ лись, было целесообразно привести здесь указанные сведения.

9.4. Условная компиляция

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

В зависимости от конкретного "условия" препроцессор может включать или исключать строки из программы. Для этих целей ис­ пользуется пять директив, указанных в табл. 26.

Табл. 26. Директивы условной компиляции

	Директива		Функция
Ш/<константное		выраэюение>	Компилировать строки, следующие за
			директивой, если <константное выражение>
Mfdef	идентификатор		отлично от нуля ("истина")
			Компилировать строки, следующие за
			директивой, если "идентификатор" определен
Mfndef	идентификатор		с помощью Udefine
			Компилировать строки, следующие за
			директивой, если "идентификатор" не
			определен с помощью директивы define или
			определение отменено с помощью Uundef
Uelse			Используется в сочетании с директивами Ш/,
			Uifdef, Uifndef как отрицание условия
Uendif			Заверщает область действия директив #if,
			m/def, m/ndef, Uelse

Эти директивы подобны традиционной конструкции if-then- else. Иллюстрирующий пример приведен в табл. 27.

Если в этом примере удалить директиву

#define TRACE

ТО после обработки препроцессором будем иметь текст файла в сле­ дующем виде:

void	getline	(	sroid ) /
±nt	main ( void		)
{	get line(	)	;
	return	0;

178

void, get line ( void. )

(

return;

Табл, 27. Использование директив условной компиляции

	До препроцессора			После препроцессора
#include	<stdio.h>			Текст файла stdio.h после обработки его
Mefine	TRACE			препроцессором
void gedine(		void	) ;	void getline(	void);
int main(	void)			int main( void	)
и				{
mfdef TRACE
printf(	"Main		\n");	printfC'Main		\n");
Uendif
getline();				getline();
return	0;			return 0;
}		void)		} -		)
void getlinef				void getline( void
{				{
mfdefTRACE
printf(	"Getline		\n");	printf( "Getline		\n");
^endif
return;				return;
}				}
Очень		часто директивы		условной	трансляции используются

для предотвращения многократного включения заголовочных фай­ лов:

/-"
stdlo	h
Definitions		for	stream	Inpu t/OL itput.
V
#lfndef		STDIO_H
^define		STDIO_H		файла
//	Текст включаемого
#en'dlf
Как указывалось выше, существуют и другие, менее употреби­
тельные директивы			препроцессора. Например, в Visual C++ б име­

ются также следующие директивы:

• #е///'(относится к директивам условной компиляции);

• #Нпе (позволяет включать номера строк исходного кода заим­ ствованных файлов);

179