Джесс Либерти - Освой самостоятельно С++ за 21 день.

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

Такие объекты называют узлами. Первый узел в списке образует голову, а последний — хвост.

Существует три основных типа связанных списков. Ниже они перечислены в порядке усложнения.

• Однонаправленные списки.

• Двунаправленные списки.

• Деревья.

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

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

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

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

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

Рис. 12.5. Связанные списки

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

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

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

В листинге 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

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: // условие выполняется