-1 / 1 / 1
Регистрация: 14.01.2017
Сообщений: 322
|
|
1
|
Сортировка двусвязного списка шаблонного класса
30.04.2020, 16:41. Показов 586. Ответов 0
C++ | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
| template <class T>
struct DListItem
{
T item;//данные
DListItem *next;
DListItem *prev;
};
template <class T>
struct DList
{
DListItem<T> *head;
DListItem<T> *tail;
DListItem<T> *current;
uint count;
DList();
DList(const DList& l);
DList(FILE*f);
~DList() { Clear(); }
void Clear();
DList& operator=(const DList<T>& l);
uint GetCount() const { return count; }
bool isEmpty() const { return count == 0; }
T& operator[](uint index);
DListItem<T> *Move(int);
void Replace(int item1, int item2);
void Find(bool(*)(const T&, char*), char*);
int FindCount(bool(*)(const T&, char*), char*, int);
void AddHead(const T& item);
void AddMiddle(const T&, uint);
void AddTail(const T& item);
void Remove(uint index);
void print() const;
void writeF(FILE*);
void sort();
};
template <class T>
DList<T>::DList()
{
head = tail = current = 0;
count = 0;
}
//template<class T>
////сортування по зростанню бульбашкою
//void DList<T>::sort()
//{
// DListItem <T> *left = head; //Перший елемент — голова
// DListItem <T> *right = head->next; //Другий елемент — наступний за головою елемент
//
// DListItem <T> *temp ; //Тимчасова ланка для зберігання відсортованих значень
//
// while (left->next) { //Обхід по ланках
// while (right) {
// if ((right->item) < (left->item)) { //Перевіряємо необхідність перестановки
// temp->item = left->item;
// }
// //Перестановка всіх внутрішніх елементів місцями
//// left->x = right->x;
//// right->x = temp->x;
//// }
//// right = right->Next; //Направляємо вказівник на наступний елемент
//// }
//// right = left->Next;
//// left = left->Next;
////}
//
// }
// }
//}
template <class T>
DList<T>::DList(FILE*f)
{
T temp;
head = tail = current = 0;
count = 0;
while (fread(&temp, sizeof(T), 1, f))
AddTail(temp);
}
template <class T>
DList<T>::DList(const DList<T>& l)
{
head = tail = current = 0;
count = 0;
DListItem<T> *temp = l.head;
while (temp != 0)
{
AddTail(temp->item); // вставляем данное item из узла с адресом temp списка l в наш создаваемый список
temp = temp->next;
}
}
template <class T>
void DList<T>::Clear()
{
while (count)Remove(0);
}
template <class T>
DList<T>& DList<T>::operator=(const DList<T> & l)
{
if (this == &l) return *this;
Clear();
DListItem<T> *temp = l.head;
while (temp != 0)
{
AddTail(temp->item);
temp = temp->next;
}
return *this;
}
template <class T>
T& DList<T>::operator[](uint index)
{
if (index >= count)
return head->item;
DListItem<T> *temp = head;
int i = 0;
while (i++ < index)
temp = temp->next;
return temp->item;
}
template <class T>
void DList<T>::AddHead(const T& item)
{
DListItem<T> *temp = new DListItem<T>; //создаем новый узел списка с адресом в temp
temp->prev = 0; // в этом узле в поле prev (адрес предыдущего элемента) пишем 0 - наш temp становится головным
temp->item = item; // в поле item нашего узла сохраняем передаваемое методу значение
temp->next = head; // в нашем новом узле в поле next ( адрес след. узла) пишем адрес узла который был головным до этого
if (head) // мы проверям если адрес головного узла не 0 - у нас в списке есть хотя бы один элемент
head->prev = temp;// тогда в этом элементе в поле prev пишем адрес нашего нового узла
if (!count) // если список пуст
head = tail = current = temp;// тогда адрес нашего нового узла становиться адресом и головы и хвоста списка
else
head = temp; //если в списке есть хотя бы один элемент тогда мы меняем адрес головы списка на адрес нашего нового элемента
count++;
}
template <class T>
void DList<T>::AddTail(const T& item)
{
DListItem<T> *temp = new DListItem<T>;
temp->next = 0;
temp->item = item;
temp->prev = tail;
if (tail)
tail->next = temp;
if (!count)
head = tail = current = temp;
else
tail = temp;
count++;
}
Не получается сделать сортировку подскажите пожалуйста.То что я пыталась сделать закомментировала |
|
0
|