Освой самостоятельно С++ за 21 день.

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

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: