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

Цусшииг 12.13. Связанные cnncoi

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, klsSame) ; 24;

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

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

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

28; class Data

29; {

30; public;

31; Data(int val);myValue(val){ }

32; -Data(){ }

33; int Compare(const Data &);

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

35: private;

36; int myValue;

ЗУГ } ;

3,8;

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 kIsSaitie;

49: }

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 NodeOi }

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

65: virtual void Show() = 0;

66: private:

67: } ;

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

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

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

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

73: class InternalNode: public Node

74: {

75: public:

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

77: InternalNode(){ delete itiyNext; delete itiyData; }

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

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

81: private:

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

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

84: } ;

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

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

88: myData(theData),myNext(next)

89: {

90: }

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

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

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

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

Node * InternalNode:;Insert(Data * theOata) {

Этот новенький больше или меньше чем я? int result = myData->Compare(*theData):

switch(result) {

По соглашению, если он такой же как я, то он идет первым case kIsSame; условие выполняется case klsLarger: новые данные вводятся перед моими {

InternalNode dataNode = new InternalNode(theData, this); return dataNode;

Oh больше чем я, поэтому передается в

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

myNext = myNext->Insert(theData); return this;

return this; появляется MSG

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

class TailNode : public Node {

public: TailNodeOi } TailNode(){ }

virtual Node Insert(Data * theData); virtual void Showi) { }

private:

Если данные подходят для меня, то они должны быть вставлены передо мной, так как я хвост и НИЧЕГО не может быть после меня Node * TailNode::Insert(Data * theData) {

InternalNode dataNode = ew InternalNode(theData, this); return dataNode;

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