Стефан Дэвис - С++ для чайников .

14Это сделано некорректно; как минимум член valFriend не может быть определён в классе того же типа, не считая массы других ошибок. Поэтому к данному примеру следует относиться как к не более чем поясняющей сугубо теоретической модели, которая никогда не будет даже скомпилирована. — Прим. ред.

_________________

176 стр. Часть 3. Введение в классы

К связанному списку легко добавить ещё один элемент — путём изменения указателя в последнем объекте списка. В этом заключается основное преимущество связанного списка — отсутствие необходимости задавать фиксированный размер на этапе компиляции: связанный список может уменьшаться и увеличиваться в зависимости от потребностей программы. Цена этой гибкости — скорость работы со списком, поскольку обратиться к какому-то из элементов списка можно, только пройдя по всем предыдущим.

Не всякий класс может быть использован для создания связанного списка. Связываемый класс объявляется так, как показано в приведённом ниже фрагменте.

class LinkableClass

{

public :

LinkableClass* pNext ;

/* Прочие члены класса */

} ;

Ключевым в этом классе является указатель на объект класса LinkableClass . На первый взгляд несколько необычно выглядит то, что класс содержит указатель сам на себя. В действительности в этом объявлении подразумевается, что каждый объект класса содержит указатель на другой объект этого же класса.

Указатель pNext и есть тот элемент, с помощью которого дети объединяются в цепочки. Фигурально выражаясь, можно сказать, что список детей состоит из некоторого количества объектов, каждый из которых имеет тип "ребёнок". Каждый ребёнок указывает на следующего ребенка.

Головной указатель является указателем типа LinkableClass* , и если использовать аналогию с цепочкой детей, держащихся за руки, то можно сказать, что учитель указывает на объект класса "ребёнок" ( любопытно отметить, что сам учитель не является ребёнком — головной указатель не обязательно должен иметь тип LinkableClass ).

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

[ Атас! ]

«Преобразование целочисленного нуля в типLinkableClass* не обязательно. С++ воспринимает 0 как значение любого типа ( в частности, как "универсальный указатель" ).»

[ Советы ]

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

void addHead( LinkableClass* pLC )

{

pLC -> pNext = pHead

pHead = pLC ;

}

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

Добавление объекта в начало списка — самая простая операция со связанным списком. Хорошее представление о работе связанного списка даёт процедура прохода по нему до конца списка.

_________________

177 стр. Глава 14. Указатели на объекты

/* Проход по связанному списку */

LinkableClass* pL = pHead ;

while ( pL )

{

/* Выполнение некоторых операций */

/* Переход к следующему элементу */

pL = pL -> pNext ;

}

Сначала указатель pL инициализируется адресом первого объекта в списке ( который хранится в переменной pHead ). Затем программа входит в цикл while . Если указатель pL не нулевой, он указывает на некоторый объект LinkableClass . В этом цикле программа может выполнить те или иные действия над объектом, после чего присвоение pL = pL -> pNext "перемещает" указатель к следующему объекту списка. Если указатель становится нулевым, список исчерпан.

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

/* LinkedListData — хранение данных в связанном списке */

#include

#include

#include

#include

using namespace std ;

/* NameDataSet — хранит имя человека ( этот объект можно легко расширить для хранения другой информации ). */

class NameDataSet

{

public :

char szName[ 128 ] ;

/* Указатель на следующую запись в списке */

NameDataSet* pNext ;

} ;

/* Указатель на первую запись списка */

NameDataSet* pHead = 0 ;

/* Добавление нового члена в список */

void add( NameDataSet* pNDS )

{

pNDS -> pNext = pHead ;

/* Заголовок указывает на новую запись */

pHead = pNDS ;

}

/* getData — чтение имени */

NameDataSet* getData( )

{

_________________

178 стр. Часть 3. Введение в классы

// Читаем имя

char nameBuffer [ 128 ] ;

cout << "\nВведите имя:" ;

cin >> nameBuffer ;

/* Если это имя — 'exit'... */

if ( ( stricmp( nameBuffer , "exit" ) == 0 ) )

{

/* ...вернуть нулевое значение */

return 0 ;

}

/* Новая запись для заполнения */

NameDataSet* pNDS = new NameDataSet ;

/* Заполнение поля имени и обнуление указателя */

strncpy( pNDS -> szName , nameBuffer , 128 ) ;

pNDS -> szName[ 127 ] = '\0' ;

pNDS -> pNext = 0 ;

/* Возврат адреса созданного объекта */

return pNDS ;

}

int main( int nNumberofArgs , char* pszArgs[ ] )

{

setlocale ( LC_ALL , ".1251" ) ; /* печать кириллицы */

cout << "Читаем имена студентов\n"

<< "Введите 'exit' для выхода\n" ;

/* Создание объекта NameDataSet */

NameDataSet* pNDS ;

while ( pNDS = getData( ) )

{

/* Добавление в конец списка */

add( pNDS ) ;

}

/* Итерация списка для вывода записей */

cout << "Записи:\n" ;

pNDS = pHead ;

while ( pNDS )

{

/* Вывод текущей записи */

cout << pNDS -> szName << "\n" ;

/* Получение следующей записи */

pNDS = pNDS -> pNext ;

}

/* Пауза для того, чтобы посмотреть на результат работы программы */

system( "PAUSE" ) ; return 0 ;

}

Несмотря на внушительную длину, программа LinkedListData относительно проста. Функция main( ) начинается с вызова функции getData( ) , которая считывает элемент NameDataSet с клавиатуры. Если пользователь вводит строку " exit ", getData( ) возвращает нуль. Функция main( ) вызывает функцию add( ) , чтобы добавить элемент, который вернула getData( ) , в конец связанного списка.