In this article, I will describe the technique works with a bidirectional list in its classical form. Entry list, O and sort by various conditions and fields of the list elements. I will not go into the theory of lists – I move on to a description of, what needs to be done to solve this problem, and along the way I will describe why so I arranged a job.
To build a list we need two structures: one – field list item. Second – he list item with anchors, which will bind the elements together.
The first structure may look like this:
1 2 3 4 5 | struct TRecord { //В котором есть некоторые поля int x; string s; }; |
This is a list of the data structure. It must contain the field, directly to the list itself (or rather to its structure ) have no relationship, but store information. This entry – container (let's call it so).
The second entry:
1 2 3 4 | struct TList { TRecord Rec; TList *Next, *Prev; } |
She had intended to store a container element, in which we will pack data, and a field for communication with neighboring elements in the list,.
What is needed such a turn on two structures? It will be easier to sort. Under normal circumstances, the list is sorted by redirecting its field-anchors on other elements (Next and Prev in this example). That is. The data itself, as they were in the memory as in the same cell (cell) and remain, but only change the pointers to the neighbors. And it certainly is good and right, but difficult. The higher complexity, the more likely to run into a bug in the program. Therefore it is necessary to simplify the program, so you can not change the anchors, and places data (as it is usually done in sorting arrays for example). Therefore appropriate data in a separate block structure, to drag them one operator, rather than drag each field separately. Below you will see what is meant.
To work with the list of required variables and the head of the list, of necessity, tail:
1 | TList *Head=0, *Last=0; |
And so it will have to look the list filling procedure:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | void Add(int x, string s){ //Создадим элемент TList *r = new TList; //Наполним его данными r->Rec.x = x; r->Rec.s = s; //Обнулим указатели на соседей чтоб список //не содержал мусора r->Next = 0; r->Prev = 0; //Если этот элемент не первый - сцепим его //и предыдущий элемент if (Last) { Last->Next = r; r->Prev = Last; } //И если это голова - запомним ее if (!Head) Head = r; // После чего дадим понять программе //что созданный элемент теперь будет хвостиком Last = r; } |
It can also be divided into two: The first element would be created, the second would have filled him with a container useful data, but it is to taste.
Do not forget about the release of the list procedure. Leaving garbage in memory – bad taste, Even if intelligent Operating System itself can be cleaned:
1 2 3 4 5 6 7 8 9 10 11 12 | void Clear(){ //Если он вообще существует if (!Head) return; //В цикле пройдем последовательно по элементам for (Last = Head->Next; Last; Last = Last->Next){ //Освобождая их соседей сзади. //т.е. убирая предыдущие delete Last->Prev; Head = Last; } delete Head; } |
O procedure:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | void Write(){ //Так же в цикле for (Last = Head; Last; Last = Last->Next){ //выводим на экран элементы списка cout.width(10); cout << Last->Rec.x; } cout << endl; for (Last = Head; Last; Last = Last->Next){ //выводим на экран элементы списка cout.width(10); cout.setf(ios_base::right); cout << Last->Rec.s; }; cout << endl; cout << endl; } |
So much it is due “orderliness”. Beautiful display – important enough optionality program. Therefore, the width of the elements, and table view should comply.
Now on to the fun – sort Lists. The procedure of the sort I've broken into two parts, removing it from the test conditions, who analyze whether the sortable elements should be promoted by, depending on the conditions of the list. The very same sorting procedure is as follows:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | void Sort(string FieldName, string Direct){ //Сортировкой пузырьком пройдемся по элементам списка for (TList *i = Head; i; i = i->Next){ for (TList *j = Head; j; j = j->Next){ //В зависимости от указанного направления if (Condition(Direct, FieldName, i->Rec, j->Rec)){ //Произведем обмен контейнера списка TRecord r = i->Rec; i->Rec = j->Rec; j->Rec = r; } } } } |
It will agree to transfer the sorting options: field Name, which is to be sorted, and the sort direction (asc – ascending or desc – descending).
In the procedure used bubble sort, as the most chassis. In a double loop is a call-function analyzer, which must respond sorting, do you need to rearrange the elements to be sorted or not. view, removing sort conditions, I simplified the code itself sorting procedures. Even if you need to add some more conditions or fields, sort itself will not have to touch.
Analyzer function looks like this:
1 2 3 4 5 6 7 | bool Condition(string Direct, string FieldName, TRecord a, TRecord b){ return (Direct == "asc" && FieldName == "x" && a.x > b.x) || (Direct == "desc" && FieldName == "x" && a.x < b.x) || (Direct == "asc" && FieldName == "s" && a.s < b.s) || (Direct == "desc" && FieldName == "s" && a.s > b.s) ; } |
It performs 4 conditions:
- If asc – Ascending, and the field being sorted – х:
- If desc – descending, and the field of the same
- If asc – Ascending, but sorted second field, strokovoe
- If desc – Descending from a string field
In each of the conditions, respectively, are compared “more” or “less” depending on the set of collations. Thus, this function is responsible sorting procedure, how she deal with the elements. In general, it is bi-directional full list sorting algorithm.
We are putting it into a single program described above and the function appends main():
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 | #include<iostream> #include<string> using namespace std; struct TRecord { //В котором есть некоторые поля int x; string s; }; struct TList { TRecord Rec; TList *Next, *Prev; }; TList *Head; TList *Last; void Add(int x, string s){ //Создадим элемент TList *r = new TList; //Наполним его данными r->Rec.x = x; r->Rec.s = s; //Обнулим указатели на соседей чтоб список //не содержал мусора r->Next = 0; r->Prev = 0; //Если этот элемент не первый - сцепим его //и предидущий элемент if (Last) { Last->Next = r; r->Prev = Last; } //И если это голова - запомним ее if (!Head) Head = r; // После чего дадим понять программе //что чозданный элемент теперь будет хвостиком Last = r; } void Clear(){ //Если он вообще существует if (!Head) return; //В цикле пройдем последовательно по элементам for (Last = Head->Next; Last; Last = Last->Next){ //Освобождая их соседей сзади. //т.е. убирая предидущие delete Last->Prev; Head = Last; } delete Head; } void Write(){ //Так же в цикле for (Last = Head; Last; Last = Last->Next){ //выводим на экран элементы списка cout.width(10); cout << Last->Rec.x; } cout << endl; for (Last = Head; Last; Last = Last->Next){ //выводим на экран элементы списка cout.width(10); cout.setf(ios_base::right); cout << Last->Rec.s; }; cout << endl; cout << endl; } bool Condition(string Direct, string FieldName, TRecord a, TRecord b){ return (Direct == "asc" && FieldName == "x" && a.x > b.x) || (Direct == "desc" && FieldName == "x" && a.x < b.x) || (Direct == "asc" && FieldName == "s" && a.s < b.s) || (Direct == "desc" && FieldName == "s" && a.s > b.s) ; } void Sort(string FieldName, string Direct){ //Сортировкой пузырьком пройдемся по элементам списка for (TList *i = Head; i; i = i->Next){ for (TList *j = Head; j; j = j->Next){ //В зависимости от указанного направления if (Condition(Direct, FieldName, i->Rec, j->Rec)){ //Произведем обмен контейнера списка TRecord r = i->Rec; i->Rec = j->Rec; j->Rec = r; } } } } int main() { setlocale(LC_ALL, "Russian"); //Наполняем список Add(rand() % 100, "Иванов"); Add(rand() % 100, "Петров"); Add(rand() % 100, "Сидоров"); Add(rand() % 100, "Бородач"); //Крутим список так и сяк cout << "Исходный список:" << endl; Write(); cout << "x (A->Z):" << endl; Sort("x", "asc"); Write(); cout << "x (Z->A):" << endl; Sort("x", "desc"); Write(); cout << "s (A->Z):" << endl; Sort("s", "asc"); Write(); cout << "s (Z->A):" << endl; Sort("s", "desc"); Write(); //Освобождаем список Clear(); cin.get(); return 0; } |
Note: I point out the words, how to sort a list of, for which field and in which order the.
Result:
On the second list, the sorting method by perezatsepleniya anchors can read on programmersforum
At the request of colleagues on site (which of course have noticed correctly) worth at least a brief mention of C ++ and the virtues STL. I mean the class list, which actually represents Lists (bi-directional). The promise of a simple: It is all, you need to work with a list of already done. On good, programmer, working with lists, of course, it is in domestic cases, elect to work STL.
I'll describe a small code using the container, as an alternative to, as described above:
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 | #include <list> #include <string> #include <iostream> using namespace std; //Опишем структуру данных элемента struct TData{ int i; string name; }; //Функцию, которая будет выступать "предикатом" //в сортировке bool Condition(TData &a, TData &b){ return a.i<b.i; } int main() { //"Создадим" переменку списка, тип елементов укажем //в <>. В данном случае это список TData list<TData> l; //Постепенно добавим элементы в конец списка TData d; d.i = 1; d.name = "1"; l.push_back(d); d; d.i = 20; d.name = "2"; l.push_back(d); d; d.i = 36; d.name = "3"; l.push_back(d); d; d.i = 4; d.name = "4"; l.push_back(d); /*И вызовем функцию сортировки, передав ей предикат Предикат - функция, принимающая два параметра, которые в ней будут сравниваться. */ l.sort(Condition); //После сортировки выведем список на экран использовав //специально предназначенный для прохода по его элементам //итератор list<TData>::iterator it; for (it = l.begin(); it != l.end(); it++){ d = *it; cout << d.i << '\t' << d.name << endl; } l.clear(); cin.get(); return 0; } |
If the task can be used STL – use. The solution is reliable and will not be spending time on their lists of the invention the storage mechanism.
The choice of these two methods should do depending on the quantity of useful data, that are entered into a list item. If it's a couple of dozen fields with numbers or strings, the easiest way, just – moving the container with useful data (like here). If the list items have a huge size, the faster technique anchors reshuffle will be carried out (changes Last and Next for perezatsepleniya element to another element). In any case, the choice of the programmer.
It’s cool but this your algorithm replaced only data fields in nodes. If you gotta do great job you need replace pointers:
void Sort(Node *&Top, Node *&End) {
if (Top && Top->next) {
Node *current = Top;
Node *prev = nullptr;
Node *tmp = nullptr;
bool flag = false;
for (int i = 0; i next) {
tmp = current->next;
if (current->data > tmp->data) {
flag = true;
current->next = tmp->next;
tmp->next = current;
if (prev)
prev->next = tmp;
tmp->prev = prev;
prev = tmp;
if (current == Top)
Top = tmp;
if (!current->next)
End = current;
}// The if end
else {
prev = current;
current = current->next;
}
}// The while end
if (!flag)
break;
else {
current = Top;
prev = nullptr;
flag = false;
}
}// The for end
}
else
cout << "\nNo entries for sorting\n";
}
Azizjan, Read carefully the article. The reference to the method, where the data remains in its place, I gave the sentence
“On the second list, the sorting method by perezatsepleniya anchors can read on programmersforum”
I am sure that beginners and useful to know such and such a method.
There is a code ready?