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

±f( ре != NULL )

{

free ре; ре == NULL;

I

/*

Пример освобождения динамической памяти. занятой элементом

линейного списка. Среда языка С++

*/

±f( ре != NULL )

{

del&te ре; ре = NULL;

}

Рассмотрим еще один практически значимый пример разме­ щения в динамической памяти двумерного массива (матрицы) и ос­ вобождения занятой памяти.

/*

Файл DynMem,срр

Демонстра ция работы с ма трицеи в динамической памяти

*/

^include		<stdio.h>		//	Для	ввода-вывода
^include		<stdlib.h>		//	Для	exit ( )
//	Ввод размеров матрицы, размещение матрицы в динамической
//	памяти и заполнение			ее		*
srold ReadMatrix (
	chetr		*pFileInp,//		Указатель на файл данных
	unsigned		&RowSize, //		Строчный размер
	unsigned		&ColSize,	//	Столбцовый размер
	int		**&рМх )	//	Указатель на матрицу

{

//Указатель на структуру со сведениями о файле данных

FILE *pStructInp;

//Открытие файла данных для чтения

if(	( pStructlnp		= fopeni pFilelnp,		"г"	) ) == NULL )
{	printf(	"\n	Ошибка 10,	Файл %s для		чтения не "
	jretuarn/	"открыт \п",		pFilelnp	);
// Чтение размеров матрицы
int	retcode		= fscanf(	pStructlnp,		"%u %u",
if(	retcode	!= 2 )		ScRowSize, &ColSize ) ;
{	printf(	"\n	Ошибка 20.	Ошибка чтения размеров"

150

return;

" матрицы

\п"

) /

}

//

Размещение

в

ДП массива

указателей

на

строки

матрицы

рМх

= new

±nt

*

[

RowSize

];

±£(

!рМх

)

{

printf

(

"\п

Ошибка

30.

Ошибка

размещения

в ДП

"

return;

"массива

указателей

на строки

матрицы

\п" ) /

}

//

Размещение

в

ДП

строк

матрицы

£ог(

unsigned

int

1=0;

l<RowSize;

1++

)

{

рМх [

1

]

= new

int

[

Col Size

];

i£(

!pMx[

1

]

)

{

Ошибка

40.

Ошибка

размещения

в

ДП"

printf(

"\n

return;

"

строки

матрицы

\п"

)

;

}

}

//

Заполнение

матрицы

£ог(

1=0;

KRowSlze;

1 + + )

{

£ог

(

unsigned

int j = 0;

j<ColSlze;

j++

)

{

retcode

=

fscanf(

pStructlnp^

] [

j ]

) ;

i£(

retcode

!=

1

)

" %1" r

&pMx[l

{

printf(

"\n

Ошибка

50.

Ошибка

чтения

"

return;

"элемента

ма трицы

\п"

) ;

)

}

}

fclose

(

pStructlnp

)

;

/ /

Закрытие

файла

данных

return;

;

int maln(

void

)

//

Возвращает

О при

успехе

{

"^^рМх;

//

Указатель

на

матрицу

int

unsigned

г,

//

Число

строк

с;

//

Число

столбцов

//Ввод матрицы

ReadMatrlx ( "DynMem. Inp", г, с, рМх ) ;

151

/ / Здесь проверяем	г, с , рМх
/ / . . .

// Освобождение динамической памяти, занятой матрицей

// Освобождение ДП, занятой строками матрицы for( unsigned ±nt i=0; Кг; i++ )

{	[ ]	pMx[	i ];
delete
}		ДП,	занятой массивом указателей	на строки
// Освобождение

//матрицы

delete

[ ] рМх;

ret-arn 0;

}

Для работы с ЛС используются следующие основные опера­

ции:

•инициализация;

•добавление элемента в начало ЛС;

•добавление элемента в конец ЛС;

•создание ЛС таким образом, чтобы первый занесенный элемент оказался в начале списка;

•создание ЛС таким образом, чтобы последний занесенный эле­ мент оказался в начале списка;

•удаление элемента из начала ЛС;

•удаление элемента из конца JIC\

•разрушение ЛС с освобождением занятой им динамической памя­ ти;

•печать содержимого ЛС;

•добавление или удаление элемента после каждого элемента ЛС, содержащего заданное значение;

•добавление или удаление элемента перед каждым элементом ЛС, содержащим заданное значение.

Реализация перечисленных операций неоднозначна. Рассмот­

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

8.2. Инициализация линейного списка

Эта операция является тривиальной и заключается в присваи­ вании указателю на начало линейного списка значения NULL^ озна­ чающего, что ЛС пуст. Инициализация списка выполняется самой

152

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

функции Initls,

Остальной материал будет рассмотрен далее.

Файл

LS.CPP

Работа

с

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

памятью.

Однонаправленный

линейный

список

и

операции

с

ним

^include

<stdio.h>

//

Для

функций

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

^include

<stdlib.h>

//

Для

функции

exit

struct

EL

//

Структура

для

элемента

списка

{

char

ch;

//

Данные

(символ)

EL

*next;

//

Указатель

на

следующий

элемент

} ;

//

Указатель

на

начало

списка:

класс

хранения

внешний

//

(область

действия

и время

жизни

-

вся

программа),

//

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

во

всех

функциях

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

проекта

и

//

через

список

параметров

функций

не

передается

EL

*

start;

//

Прототипы

функций

void

Init_ls

(

void.

)

;

void

Dest^^ls

(

void

)

;

void

Add_end

(

cha.r

с

)

;

void

Add__beg

(

cbstr

с

)

;

void

Del_end

(

void

)

;

void

Del_beg

(

void

)

;

void

Create_end

(

void

)

;

void

Create__beg(

void

)

;

void

Print_ls

(

void

) ;

void

After_Add(

char

find,,

сЪа.г

add

) ;

void

Before__Add

(

char

find,

char

add

)

;

void

After_Del

(

char

find

) ;

void

Before_Del

(

char

find

)

;

int

main(

void

)

//

Возвращает

0

при

успехе

{

Init_ls

(

)

;

//

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

списка

//

Заполнение

линейного

списка

символами

из

файла

LS.DAT:

//

первый

прочитанный

символ

-

в

начале

списка

Сгеаte_beg(

)

;

//

Print__ls

(

)

;

Вывод

содержимого

списка

на

экран

Dest__ls

(

)

;

//

Разрушение

списка

After_Del

(

'3');

//

Удаление

после

'3'

Print

Is(

)

;

153

Add

end(

' С

) ,

//

Добавление

в

конец

списка

//

элемента

'С'

After_Del

(

'3');

//

Удаление

после

'3'

Pr±nt_ls

(

)

;

Dest_ls

(

)

;

//

Разрушение

списка

//

Заполнение

линейного

списка

символами

из

файла

LS.DAT:

//

последний

прочитанный

символ

- в

конце

списка

Create_end(

)

;

Print

Is(

)

;

//

Dest_ls

(

)

;

) ;

Разрушение

списка

списка

Add__end

(

'C

//

Добавление

в

конец

'D'

) ;

//

элемента

'С'

Add_end

(

//

Добавление

в

конец

списка

)

;

//

элемента

'D'

Add

beg(

^B^

//

Добавление

в

начало

элемента

'В

Add_beg

(

//

Добавление

в

начало

элемента

'А

Print

Is ( 'A' ) ;

Del_end(

r)

;

)

;

//

Удаление

последнего

элемента

) ;

//

списка

Del_beg(

;

//

Удаление

первого

элемента

спиСК(

Print_ls

(

)

//

Разрушение

списка

Dest_ls

(

) /

//

Заполнение

списка

пятью

двойками

for(

Int

i

=

1;

i

<=

5;

i-^+ )

Add__end(

;

'2' )

;

Print_ls

(

)

'1 '

перед

//

Добавление

Before_Add(

' 2 ' ,

Ч'

) ;

Print_ls

(

)

;

//

Добавление

'3 '

после

After_Add(

'2',

'3'

)

;

Print_ls

(

)

;

//

Добавление

'1 '

перед

Before_Add(

(

)

' 1

' ,

Ч'

) /

Print_ls

;

'2 '

//

Добавление

после

After_Add(

' 2 ' ,

'2' )

;

Print_ls(

)

;

//Добавление '2 ' после

After_Add(		)	' 2 ' ,	'2' )		;
Print_ls(			/
// Добавление			'3 '		после
After__Add(	(	)	'3',	'3'	)	/
Print_ls			;			//
After_Del	(	)	'3');				Удаление	после
Print_ls	(		;			//
Before_Del(		)	'1')				Удаление	перед	' 1
Print_ls(			;			//
Dest_ls	( )	;					Разрушение		списка
return	0;
// Инициализация			списка

154

void

Init_ls

(

void

)

{

start

=

NULL;

//

Вначале

список

пуст

rebvLrn;

}

//

Paзрушение

списка

void

Dest_ls

(

void

)

{

if(

start

== NULL

)

{

printf(

"\n

Список

пуст.

Удалять

нечего"

) ;

retuxm/

}

while

(

start

/- NULL

)

Del__beg ( ) ;

//

Удаление

первого

элемента

списка

}

return/

//

Добавление

(

элемента

в

конец

списка

void

Add_end

с

)

//

Данные

добавляемого

элемента

char

{

//

Указатель

на

новый

(добавляемый)

элемент

списка

EL

*temp,

//

Указатель

на

текущий

элемент

*сиг;

temp

= new

EL;

//

1:

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

размещение

if(

temp

== NULL )

//

элемента

{

printf(

"\n

Элемент

списка

не

размещен" )

;

exit

(

1

)

;

}

=

с;

//

2:

занесение

данного

temp->ch

temp->next

= NULL;

//

3:

новый

элемент

является

if(

start

== NULL

)

//

Новый

последним

(пустой)

//

список

списка

else

start

= temp;

//

4а:

указатель

на

начало

{

//

46:

проходим

весь

список

от начала,

пока

текущий

//

=

элемент

не

станет

последним

сиг

start;

!=

NULL

)

while(

cur->next

//

Продвижение

по

списку

//

сиг

=

cur->next;

элемента

на

новый,

4в:

ссылка

последнего

//

добавляемый

в конец

списка

155

cur~>next = temp;

}

return/

}

//

Добавление

элемента

в начало

списка

void

Add_beg(

с

)

//

Данные добавляемого

элемента

char

{

//

Указатель

на

новый

(добавляемый)

элемент

списка

EL

*temp;

temp

= new

EL;

//

1:

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

размещение

±f(

temp

== NULL )

//

элемента

(

printf(

"\n

Элемент

списка

не

размещен"

)

;

exit

( 2

)

;

}

= с/

// 2:

занесение

данного

temp->ch

//

3:

новый

элемент

ссылается

на

начало

списка

temp->next

=

start;

4:

новый

элемент

становится

start

=

temp;

//

/ /

первым

return;

}

//

Заполнение

линейного

списка

символами

из

файла

LS.DAT:

//

первый

прочитанный

символ

- в начале

списка

void

Create^beg(

void

)

{

//

Данное

для

элемента,

добавляемого

в

конец

списка

сЪаг

с;

на

структуру

со

сведениями

о

файле для

//

Указатель

//чтения

FILE		*f__in;
//	Открываем		файл для	чтения		"г" ) )	==	NULL )
±£(	( f_in	=	fopeni	"Is.dat",
{	printf(	"\n Файл		Is.dat	для	чтения	не	открыт " ) ;
	exit (	3 )	;

}

//Создаем список

while		( ( с =	(	сНаг	)fgetc(	f_in ) ) != EOF )
{	Add_end(		с	) ;
}
	Закрываем		файл
//
i£(	(	fclose(	f	in	) ) == EOF )

156

*f_in;

{

printf

(

"\n

Файл

Is.dat

не

закрыт

"

)

;

e x i t

( 4

)

;

}

return;

}

// Заполнение

линейного

списка

символами

из

файла

LS.DAT:

//

последний

прочитанный

символ

-

в начале

списка

void

Create_end

(

void, )

{

Данное

для

элемента^

добавляемого

в

конец

списка

//

сЬа.г

с;

на

структуру

со

сведениями

о

файле

для

//

Указатель

//чтения

FILE

//	Открываем		файл для	чтения		"г" ; ; == NULL )
±£(	( f__in	=	fopen(	"Is.dat",
{	print f	(	"\n Файл	Is.dat	для	чтения не открыт " ) ;
	exit(5);

}

//Создаем список

while

( (

с

=

(

char

)fgetc(

f_in

)

)

!=

EOF

)

{

Add_beg

(

с

) ;

}

//

Закрываем

файл

±f(

(

fclose(

f_in

)

)

==

EOF )

{

printf(

"\n

Файл

Is.dat

не

закрыт

"

) ;

exit(6);

}

rebum;

}

/ / Удаление

последнего

элемента

списка

void Del_end

(

void

)

{

*prev,

//

Указатель

на

предпоследний

EL

*end/

//

элемент

на

последний

элемент

//

Указатель

i£(

start

- =

NULL

)

{

Список

пуст. Удалять

нечего"

) ;

retjim;

printf

(

"\n

}

1:

поиск

последнего

(и

предпоследнего)

элементов

//

157

prev

= NULL;

end

=

start;

while(

end->next

/=

NULL

)

{

prev

=

end;

}

end

=

end->next;

//

Продвижение

no

списку

d&lete

end;

//

2: удаление

последнего

элемента

±f(

prev

!=

NULL

)

{

//

3:

бывший

предпоследний

элемент

становится

//последним

prev~>next

=

NULL;

}

else

(

start

= NULL;

// 3:

в списке

был один

элемент

}

return;

}

//

Удаление

первого

элемента

списка

void

Del_beg

( void.

)

{

EL

*del;

//

Указатель

на

удаляемый

элемент

if(

start

== NULL

)

{

printf(

"\n

Список

пуст.

Удалять

нечего"

)

;

return;

}

1:

подготовка

первого

элемента

для

удаления

//

del

=

=

start;

//

2:

start

сдвигается

на

второй

start

del->next;

delete

del;

//

1:

элемент

элемента

//

удаление

первого

}

return;

//

Печать

содержимого

списка

на

экран

void

Print_ls(

void

)

{

EL

*prn;

//

Указатель

на

печатаемый

элемент

i£(

start

== NULL

)

{

Список

пуст.

Распечатывать

нечего"

) ;

printf(

"\n

return;

}

prn

=

start;

//

Указатель

на

начало

списка

print

f

(

"\п" ) ;

158

while

(

prn

!=

NULL

) //

До

конца

списка

{

//

Печать

данных

(символа)

элемента

printf(

"%с", prn->ch

)

;

prn

= prn~>next;

//

Продвижение

по

списку

}

return/

}

// Добавление

элемента

add

после

элемента

find

void

After_Add

(

char

find,

char

add

)

{

EL

*temp,

//

Указатель

на

добавляемый

элемент

*cur;

//

Указатель

на

текущий

элемент

if(

start

== NULL )

{

printf(

"\n

Список

пуст.

Нельзя

найти

нужный

"

return/

"элемент

"

) /

}

//

Поиск элементов,

содержащих символ

find,

с

добавлением

//

после

них

элемента

с

символом add

сиг

=

start/

NULL

)

while

(

cur

!=

{

if(

cur->ch

== find

)

{

//

Нужный элемент

найден

(он

является

текущим)

//

1:

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

размещение

элемента

temp

= new

EL/

)

if(

temp

== NULL

{

printf(

"\n

Элемент

списка

не

размещен"

) /

( 7

exit

) /

}

2:

занесение

данного

//

temp->ch

=

add/

//3: ссылка на элемент, который стоял за текущим

temp->next = cur->next/

//4: текущий элемент указывает на новый

cur->next		=	temp/	текущим
//	5: новый		элемент становится
сиг =		temp/
)
сиг =	cur->next/		// Продвижение по	списку
}
return/
/ у	i^:h*iir-^-k-^irTlf*^Th-^-^9r-^ir*i^-k*-*c***Thilc-^*-ki^-k-k*-!h***T^

159