Компоненты связанных списков

 

Связанный список состоит из узлов. Узлы представляют собой абстрактные классы. В нашем примере для построения связанного списка используются три подтипа данных. Один узел будет представлять голову связанного списка и отвечать за его инициализацию. Попробуйте догадаться сами, за что отвечает хвостовой узел. Между ними могут быть представлены (либо могут отсутствовать) один или несколько промежуточных узлов, которые отвечают за обработку данных, переданных в список.

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

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

В листинге 12.13 рассматривается пример программы со связанным списком, а затем детально анализируется ее работа.

Листинг 12.13. Связанный список

0: // **********************************************

1: // Листинг 12.13.

2: //

3: // ЦЕЛЬ: Показать использование связанного списка

4: // ПРИМЕЧАНИЯ:

5: //

6: // Авторское право: Copyright (С) 1998 Liberty Associates, Inc.

7: // Все права защищены

8: //

9: // Показан один из подходов обьектно-ориентированного

10: // программирования по созданию связанных списков.

11: // Список распределяет задачи между узлами,

12: // представляющими собой абстрактные типы данных.

13: // Список состоит из трех узлов: головного,

14: // хвостового и промежуточного. Данные содержит

15: // только промежуточный узел.

16: // Все объекты, используемые в списке, относятся

17: // к классу Data.

18: // **********************************************

19:

20:

21: #include <iostream.h>

22:

23: enum { kIsSmaller, kIsLarger, kIsSame};

24:

25: // Связанный список основывается на обьектах класса Data

26: // Любой класс в связанном списке должен поддерживать два метода:

27: // Show (отображение значения) и Compare (возвращение относительной позиции узла)

28: class Data

29: {

30: public:

31: Data(intval):myValue(val){ }

32: ~Data(){ }

33: int Compare(const Data &);

34: void Show() { cout << myValue << endl; }

35: private:

36: int myValue;

37: };

38:

39: // Сравнение используется для определения

40: // позиции в списке для нового узла.

41: int Data::Compare(const Data & theOtherData)

42: {

43: if (myValue < theOtherData.myValue)

44: return kIsSmaller;

45: if (myValue > theOtherData.myValue)

46: return kIsLarger;

47: else

48: return kIsSame;

49: }

50:

51: // Объявления

52: class Node;

53: class HeadNode;

54: class TailNode;

55: class InternalNode;

56:

57: // ADT-представление узловых объектов списка.

58: // В каждом производном классе должны быть замещены функции Insert и Show

59: class Node

60: {

61: public:

62: Node(){ }

63: virtual ~Node(){ }

64: virtual Node * Insert(Data * theData)=0;

65: virtual void Show() = 0;

66: private:

67: };

68:

69: // Этот узел поддерживает реальные объекты.

70: // В данном случае объект имеет тип Data

71: // 0 другом, более общем методе решения этой

72: // задачи мы узнаем при рассмотрении шаблонов.

73: class InternalNode: public Node

74: {

75: public:

76: InternalNode(Data * theData, Node * next);

77: ~InternalNode() { delete myNext; delete myData; }

78: virtual Node * Insert(Data * theData);

79: virtual void Show() { myData->Show(); myNext->Show(); } // Делегирование!

80:

81: private:

82: Data * myData; // данные списка

83: Node * myNext; // указатель на следующий узел в связанном списке

84: };

85:

86: // Инициализация, выполняемая каждым конструктором

87: InternalNode::InternalNode(Data * theData, Node * next):

88: myData(theData), myNext(next)

89: {

90: }

91:

92: // Сущность списка.

93: // Когда в список передается новый объект,

94: // программа определяет позицию в списке

95: // для нового узла

96: Node * InternalNode::Insert(Data * theData)

97: {

98:

99: // Этот новенький больше или меньше чем я?

100: int result = myData->Compare(*theData);

101:

102:

103: switch(result)

104: {

105: // По соглашению, если он такой же как я, то он идет первым

106: case kIsSame: // условие выполняется

107: case kIsLarger: // новые данные вводятся перед моими

108: {

109: InternalNode * dataNode = new InternalNode(theData, this);

110: return dataNode;

111: }

112:

113: // Он больше чем я, поэтому передается в

114: // следующий узел, и пусть тот делает с этими данными все, что захочет.

115: case kIsSmaller:

116: myNext = myNext->Insert(theData);

117: return this;

118: }

119: return this; // появляется MSC

120: }

121:

122:

123: // Хвостовой узел выполняет роль часового

124:

125: class TailNode: public Node

126: {

127: public:

128: TailNode(){ }

129: ~TailNode(){ }

130: virtual Node * Insert(Data * theData);

131: virtual void Show() { }

132:

133: private:

134:

135: };

136:

137: // Если данные подходят для меня, то они должны быть вставлены передо мной,

138: // так как я хвост и НИЧЕГО не может быть после меня

139: Node * TailNode::Insert(Data * theData)

140: {

141: InternalNode * dataNode = ew InternalNode(theData, this);

142: return dataNode;

143: }

144:

145: // Головной узел не содержит данных, он только

146: // указывает на начало списка

147: class HeadNode: public Node

148: {

149: public:

150: HeadNode();

151: ~HeadNode() { delete myNext; }

152: virtual Node * Insert(Data * theData);

153: virtual void Show() { myNext->Show(); }

154: private:

155: Node * myNext;

156: };

157:

158: // Как только создается головной узел,

159: // он создает хвост

160: HeadNode::HeadNode()

161: {

162: myNext = new TailNode;

163: }

164:

165: // Ничего не может быть перед головой, поэтому

166: // любые данные передаются в следующий узел

167: Node * HeadNode::Insert(Data * theData)

168: {

169: myNext = myNext->Insert(theData);

170: return this;

171: }

172:

173: // Я только распределяю задачи между узлами

174: class LinkedList

175: {

176: public:

177: LinkedList();

178: ~LinkedList() { delete myHead; }

179: void Insert(Data * theData);

180: void ShowAll() { myHead->Show(); }

181: private:

182: HeadNode * myHead;

183: };

184:

185: // Список появляется с созданием головного узла,

186: // который сразу создает хвостовой узел.

187: // Таким образом, пустой список содержит указатель на головной узел,

188: // указывающий, в свою очередь, на хвостовой узел, между которыми пока ничего нет.

189: LinkedList::LinkedList()

190: {

191: myHead = new HeadNode;

192: }

193:

194: // Делегирование, делегирование, делегирование

195: void LinkedList::Insert(Data * pData)

196: {

197: myHead->Insert(pData);

198: }

199:

200: // выполняемая тестовая программа

201: int main()

202: {

203: Data * pData;

204: int val;

205: LinkedList 11;

206:

207: // Предлагает пользователю ввести значение,

208: // которое передается в список

209: for (;;)

210: {

211: cout << "What value? (0 to stop): ";

212: cin >> val;

213: if (!val)

214: break;

215: pData = new Data(val);

216: ll.Insert(pData);

217: }

218:

219: // теперь пройдемся по списку и посмотрим значения

220: ll.ShowAll();

221: return 0; // 11 выходит за установленные рамки и поэтому удалено!

222: }

 

Результат:

What value? (0 to stop) 5

What value? (0 to stop) 8

What value? (0 to stop) 3

What value? (0 to stop) 9

What value? (0 to stop) 2

What value? (0 to stop) 10

What value? (0 to stop) 0

 

Анализ: Первое, на что следует обратить внимание, — это константное перечисление, в котором представлены константы kIsSmaller, kIsLarger и kIsSame. Любой объект, представленный в списке, должен поддерживать метод Compare('). Константы, показанные выше, возвращаются в результате выполнения этого метода.

В строках 28—37 объявляется класс Data, а в строках 39—49 выполняется метод Compare(). Объекты класса Data содержат данные и могут использоваться для сравнения с другими объектами класса Data. Они также поддерживают метод Show(), отображающий значение объекта класса Data.

Чтобы лучше разобраться в работе связанного списка, проанализируем шаг за шагом выполнение программы, показанной выше. В строке 201 объявляется выполняемый блок программы, в строке 203 — указатель на класс Data, а в строке 205 определяется связанный список.

Для создания связанного списка в строке 189 вызывается конструктор. Единственное, что он делает, — выделяет области памяти для объекта HeadNode и присваивает адрес объекта указателю, поддерживаемому связанным списком и объявленному в строке 182.

При создании объекта HeadNode вызывается еще один конструктор, объявленный в строках 160—163, который, в свою очередь, создает объект TailNode и присваивает его адрес указателю myNext, содержащемуся в объекте HeadNode. При создании объекта TailNode вызывается конструктор TailNode, объявленный в строке 128. Тело конструктора содержится в той же строке программы, и он не создает никаких новых объектов.

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

В строке 209 начинается бесконечный цикл. Появляется предложение пользователю ввести значение, которое будет добавлено в связанный список. Ввод новых значений можно продолжать до бесконечности. Ввод значения 0 завершает цикл. Введенное значение проверяется в строке 213.

Если введенное значение отличается от 0, то в строке 215 создается новый объект типа Data, а в строке 216 он вводится в связанный список. Предположим, что пользователь ввел число 15, после чего в строке 195 будет вызван метод Insert.

 

 

Рис. 12.6. Связанный список сразу после создания

 

Связанный лист немедленно передаст ответственность за ввод объекта головному узлу, вызвав в строке 167 метод Insert. Головной узел немедленно делегирует ответственность любому другому узлу (вызывает в строке 139 метод Insert), адрес которого хранится в указателе myNext. Сначала в этом указателе представлен адрес хвостового узла (вспомните, что при создании головного узла автоматически создается хвостовой узел и ссылка на него добавляется в головной узел).

Хвостовому узлу TailNode известно, что любой объект, переданный обращением TailNode::Insert, нужно добавить в список непосредственно перед собой. Так, в строке 141 создается объект InternalNode, который добавляется в список перед хвостовым узлом и принимает введенные данные и указатель на хвостовой узел. Эта процедура выполняется с помощью объявленного в строке 87 конструктора объекта InternalNode.

Конструктор объекта InternalNode просто инициализирует указатель класса Data адресом переданного объекта этого класса, а также присваивает указателю myNext этого

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

Теперь, после того как был создан узел InternalNode, адрес этого узла присваивается указателю dataNode в строке 141, и именно этот адрес возвращается теперь методом TailNode::Insert(). Так мы возвращаемся к методу HeadNode::Insert(), где адрес узла InternalNode присваивается указателю myNext узла HeadNode (строка 169). И наконец, адрес узла HeadNode возвращается в связанный список — туда, где в строке 197 он был сброшен (ничего страшного при этом не произошло, так как связанному списку уже был известен адрес головного узла).

Зачем было беспокоиться о возвращении адреса, если он не используется? Метод Insert был объявлен в базовом классе Node. Для выполнения метода необходимо задать значение возврата. Если изменить значение возврата функции HeadNode::Insert(), то компилятор покажет сообщение об ошибке. Это все равно что возвратить узел HeadNode и позволить связанному списку выбросить его адрес.

Так что же все-таки произошло? Данные были введены в список. Список передал эти данные головному узлу. Головной узел передал их дальше по тому адресу, что хранится в его указателе. В первом цикле в этом указателе хранился адрес хвостового узла. Хвостовой узел немедленно создает новый промежуточный узел, указателю которого присваивается адрес хвостового узла. Затем хвостовой узел возвращает адрес промежуточного узла в головной узел, где он присваивается указателю myNext головного узла. Итак, свершилось то, что требовалось: данные расположились в списке правильным образом (рис. 12.7).

После ввода первого промежуточного узла программа переходит к строке 211 и выводит предложение пользователю ввести новое значение. Предположим, что в этот раз было введено значение 3. В результате в строке 215 создается новый объект класса Data и вводится в список в строке 216.

 

Рис. 12.7. Вид связанного списка после того, как был добавлен первый промежуточный узел

 

И вновь в строке 197 список передает новое значение в головной узел HeadNode. Метод HeadNode::Insert(), в свою очередь, передает эти данные по адресу, хранящемуся в указателе myNext. Как вы помните, теперь он указывает на узел, содержащий объект типа Data со значением 15. В результате в строке 96 вызывается метод InternalNode::Insert(). В строке

100 указатель myData узла InternalNode сообщает объекту этого узла (значение которого сейчас равно 15) о необходимости вызвать метод Compare(), принимающий в качестве аргумеи'- та новый объект Data со значением 3. Метод Compare() объявлен в строке 41.

Происходит сравнение значений двух объектов, и, поскольку значение myValue соответствует 15, а theOtherData.myValue равно 3, метод возвращает константу kIsLarget. B соответствии со значением возвращенной константы программа переходит к выполнению строки 109.

Создается новый узел InternalNode для нового объекта данных. Новый узел будет указывать на текущий объект узла InternalNode, и адрес нового узла InternalNode возвращается методом InternalNode:;Insert() в головной узел HeadNode. Таким образом, новый узел, значение которого меньше значения текущего объекта, добавляется в связанный список, после чего связанный список выглядит так, как показано на рис, 12.8.

Натретьем цикле пользователь ввел значение 8. Оно больше чем 3, но меньше чем 15, поэтому программа должна ввести новый объект данных между двумя существующими промежуточными узлами. Последует та же серия операций, что и в предыдущем цикле, за тем исключением, что при вызове метода Compare() для объекта типа Data, значение кото- рогоравно 3, будет вОзвращена константа kIsSmaller, а не kIsLarger, как в предыдущем случае (поскольку значение текущего объекта 3 меньше значения нового объекта 8).

В результате метод InternalNode::Insert() переведет выполнение программы на строку 116. Вместо создания и ввода в список нового узла, новые данные будут переданы в метод Insert того объекта, на который ссылается указатель myNext текущего объекта. В данном случае будет вызван метод InsertNode для промежуточного узла, значение объекта которого равняется 15.

Вновь будет проведено сравнение данных, которое в этот раз завершится созданием нового промежуточного узла. Этот новый узел будет ссылаться на тот промежуточный узел, значение которого 15, а адрес нового узла будет присвоен указателю узла со значением 3, как показано в строке 116.

 

Рис. 12.8. Вид связанного списка после того, как был добавлен второй промежуточный узел

 

В результате новый узел вновь будет вставлен в правильную позицию.

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

 

Что мы узнали в этой главе

 

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

Хвостовой узел создает новые узлы и добавляет их в список, если они содержат данные. Хвостовому узлу известно, что если новые объекты содержат какие-то данные, то они должны располагаться в списке до него.

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

Обратите внимание, что промежуточные узлы сами по себе не имеют никакого представления о данных объектов и о том, как их сравнивать. Сравнение выполняется методами, вызываемыми объектами. Все, за что отвечает промежуточный узел, — это обращение к своему объекту с требованием вызвать метод сравнения текущего значения с новым переданным значением. В зависимости от того, какую константу возвратит метод сравнения, узел либо добавляет объекты перед собой, либо передает их другому узлу, не беспокоясь о том, что будет с этим объектом дальше.

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

 

Классы массивов

 

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

Можно разработать механизм сортировки или какого-либо другого упорядочения элементов массива либо использовать множество других эффективных вариантов массивов, наиболее популярны среди которых следующие:

• отсортированные коллекции: каждый член массива автоматически занимает свое определенное место;

• наборы: ни один из членов не повторяется в массиве дважды;

• словари: связанные пары элементов массива, где один член выполняет роль ключа для возвращения второго члена;

• разреженные массивы: допускается использование произвольных значений индексов, но в массив будут добавляться только реально существующие элементы. Так, можно ввести и использовать элемент с индексом SprseArray[5] или SpcseArray[2Q0], HO 3TO не значит, что в массиве реально существуют все элементы с меньшими индексами;

• мультимножества: неупорядоченные коллекции, члены которых добавляются и возвращаются в произвольном порядке.

Перегрузив оператор индексирования ([]), можно превратить связанный список в отсортированную коллекцию. Если добавить функцию отслеживания одинаковых членов, то отсортированная коллекция превратится в набор. Если все объекты списка связать попарно, то связанный список превратится в словарь или в разреженный массив.

 

Резюме

 

Сегодня вы узнали, как создавать массивы в C++. Массив представляет собой коллекцию объектов одинакового типа с фиксированным числом элементов.

Массивы никак не контролируют свой размер. Поэтому вполне возможно в программе заносить данные за пределы массива, что часто является причиной ошибок. Отсчет индексов массива начинается с 0. Часто допускаемой ошибкой является указание индекса n для массива с размером n.

Массивы могут быть одномерными или многомерными. Независимо от размерности, все массивы базовых типов (например, int) или массивы объектов классов с конструкторами, заданными по умолчанию, могут быть инициализированы при объявлении.

Объекты массивов или все массивы целиком можно сохранять как в стековой области памяти, так и в области динамического обмена. Если удаляется объект из области динамической памяти, не забудьте установить квадратные скобки после ключевого слова delete[].

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

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

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

 

Вопросы и ответы

 

Что произойдет, если в массив из 24-х членов вписать значение для 25-го элемента?

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

Что представляют собой элементы неинициализированного массива?

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

Можно ли создавать комбинации массивов?

Да. Массив может содержать указатель на другой, более крупный массив. В случае работы со строками можно использовать некоторые стандартные функции, такие как strcat, чтобы создавать комбинации массивов символов.

Чем связанные списки лучше массивов?

Массивы всегда имеют фиксированный размер, тогда как размер связанного списка может изменяться динамически во время выполнения программы.

Всегда ли нужно в классе строк использовать указатель char * для сохранения содержимого строки?

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

 

Коллоквиум

 

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

Контрольные вопросы

 

1. Как обратиться к первому и последнему элементам массива SomeArray[25]?

2. Как объявить многомерный массив?

3. Выполните инициализацию элементов многомерного массива, созданного при ответе на вопрос 2.

4. Сколько элементов содержит массив SomeArray[10][5][20]?

5. Каково максимальное число элементов, которые можно добавить в связанный список?

6. Можно ли в связанном списке использовать индексы?

7. Каким является последний символ в строке "Сергей — хороший парень"?

 

Упражнения

 

1. Объявите двухмерный массив, который представляет поле для игры в крестики и нолики.

2. Запишите программный код, инициализирующий значением 0 все элементы созданного перед этим массива.

3. Объявите класс узла Node, поддерживающего целые числа.

4. Жучки: что неправильно в следующей программе?

unsigned short SomeArray[5][4];

for (int i = 0; i<4; i++)

for (int j = 0; j<5; ]++)

SomeArray[i][j] = i+j;

5. Жучки: что неправильно в следующей программе?

unsigned short SomeArray[5][4];

for (int i = 0; i<=5; i++)

for (int j = 0; j<=4; j++)

SomeArray[i][j] = 0;

 

День 13-й. Полиморфизм

 

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

• Что такое множественное наследование и как его использовать

• Что представляет собой виртуальное наследование

• Что такое абстрактные типы данных

• Что такое чистые виртуальные функции