список двонаправлений. Сортування по полях і умов

У цій статті я опишу методику роботи з двонаправленим списком в класичному його варіанті. введення списку, висновок і сортування по природному розмаїттю та полях елементів списку. Не буду вдаватися в теорію списків – перейду до опису того, що необхідно зробити для вирішення даного завдання, і по ходу справи опишу чому саме так я організував роботу.

Адміністратор сайту

На початку 2016 року ми плануємо опублікувати цілий розділ по темі списки в С ++. До нього входитимуть теми: Динамічні структури даних, одинзв'язні списки, двусвязного списки, циклічні списки…

Для побудови списку нам знадобляться дві структури: одна – поля елемента списку. друга – сам елемент списку з якорями, які будуть зв'язувати елементи між собою.

Перша структура може виглядати так:

struct TRecord {
	//В котором есть некоторые поля
	int x;
	string s;
};

struct TRecord {

//В котором есть некоторые поля

int x;

string s;

};

Це структура даних списку. У ній повинні міститися поля, які безпосередньо до самого списку (вірніше до його структурі ) відношення не мають, зате зберігають інформацію. ця запис – контейнер (назвемо її так).

Другий запис:

struct TList {
	TRecord Rec;
	TList *Next, *Prev;
}

struct TList {

TRecord Rec;

TList *Next, *Prev;

}

Вона вже покликана зберігати в собі елемент контейнера, в який ми спакуємо дані, і поля для зв'язку з елементами-сусідами в списку.

Для чого знадобився такий розворот на дві структури? Так буде зручніше проводити сортування. У звичайних умовах список сортується шляхом перенаправлення його полів-якорів на інші елементи (наступного і перед в даному прикладі). Тобто,. самі дані, як були в пам'яті так в тій же комірці (осередках) і залишаються, а змінюються лише покажчики на сусідів. І це звичайно добре і правильно, але складно. Чим вище складність, тим більше ймовірність нарватися на баг в програмі. Тому варто спростити програму, щоб можна було не якоря міняти, а дані місцями (як зазвичай це робиться в сортуванні масивів наприклад). Тому доцільніше дані виділити в окремий блок-структуру, щоб перетягувати їх одним оператором, а не тягати кожне поле окремо. Нижче ви побачите що мається на увазі.

Для роботи зі списком потрібні змінні голови списку і, по необходимости, хвоста:

TList *Head=0, *Last=0;

1	TList Head=0, Last=0;

І ось так вже буде виглядати процедура наповнення списку:

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

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;

}

Така велика вона через “marafeta”. Гарний висновок на екран – досить важлива опціонально програми. Тому ширину для елементів і табличний вигляд варто дотримати.

Тепер переходимо до найцікавішого – сортування списку. Процедуру сортування я розбив на дві частини, прибравши з неї умови перевірки, які аналізують потрібно сортовані елементи просувати за списком в залежності від умови. Сама ж процедура сортування виглядає так:

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

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;

}

У неї домовимося передавати опції сортування: ім'я поля, яке підлягає сортуванню, і напрямок сортування (по зростанню – по зростанню або по спадаючій – за зменшенням).

У процедурі застосована сортування бульбашкою, як найбільш ходова. У подвійному циклі відбувається виклик функції-аналізатора, яка повинна відповісти сортування, чи потрібно міняти місцями сортовані елементи чи ні. вид, прибравши умови сортування, я спростив код самої процедури сортування. Навіть якщо потрібно буде додавати якісь ще умови або поля, саму сортування вже не доведеться чіпати.

Функція аналізатор виглядає так:

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)
		;
}

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)

;

}

вона виконує 4 умови:

Если по зростанню – за зростанням, і сортируемое поле – х:
Если по спадаючій – за зменшенням, і поле той же
Если по зростанню – за зростанням, але сортується друге поле, строковое
Если по спадаючій – по спадаючій з строковим полем

У кожному з умов відповідно проводиться порівняння “больше” или “меньше” в залежності від заданих параметрів сортування. Таким чином ця функція відповідає процедурі сортування, як їй чинити з елементами. В цілому це і є весь алгоритм сортування двонаправленого списку.

Збираємо описане вище в одну програму і дописуємо функцію main():

#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;
}

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;

}

Зверніть увагу: Я словами вказую, як сортувати список, по якому полю і в якому порядку.

Результат:

Про другому методі сортування списку шляхом перезацепленія якорів можете почитати на programmersforum

На прохання колег по сайту (які звичайно ж правильно помітили) варто хоча б коротко згадати про принади C ++ і STL. Маю на увазі клас list, який власне уособлює списки (двонаправлені). посил простий: Все, що потрібно для роботи зі списком вже зробили. По хорошому, програмісту, працюючому зі списками, звичайно ж варто в побутових випадках обирати для роботи STL.

Опишу невеликий код із застосуванням цього контейнера, як альтернатива тому, що описано вище:

#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;
}

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

}

Якщо завдання дозволяє використовувати STL – используйте. Рішення виявиться надійніше і не буде трати часу на винаходи свого механізму зберігання списків.

Вибір з цих двох методів варто робити в залежності від кількості корисних даних, що вводяться в елемент списку. Якщо це пара десятка полів з числами або невеликими рядками, то найпростіший спосіб, як раз – переміщення контейнера з корисними даними (як тут). Якщо ж елементи списку мають величезний розмір, то швидше буде виконуватися методика перестановки якорів (зміни останній і наступного для перезацепленія елемента до іншого елементу). У будь-якому випадку вибір за програмістом.

3 думки про "список двонаправлений. Сортування по полях і умов”

Василь Аюпов говорить:
08.12.2015 at 20:20
Це круто, але це ваш алгоритм замінено тільки поле даних в вузлах. Якщо вам потрібно зробити велику роботу, вам потрібно замінити покажчики:
Сортування недійсними(вузол *&топ, вузол *&кінець) {
if (топ && топ->наступного) {
Вузол * ток = Вгору;
Вузол * перед = nullptr;
Вузол * TMP = nullptr;
BOOL прапор = брехня;
for (int i = 0; я поруч) {
TMP = current->наступного;
if (current->дані > tmp->дані) {
прапор = істина;
current->наступна = tmp->наступного;
tmp->Наступного = ток;
if (попередня)
prev->наступна = TMP;
tmp->перед = перед;
перед = TMP;
if (струму == Вгору)
Top = TMP;
if (!current->наступного)
End = ток;
}// якщо кінець
else {
перед = ток;
ток = current->наступного;
}
}// Кінець в той час як
if (!прапор)
break;
else {
ток = Вгору;
перед = nullptr;
прапор = брехня;
}
}// для кінця
}
else
cout << "\nNo entries for sorting\n";
}
відповісти
1. Stilet говорить:
  09.12.2015 at 13:31
  Azizjan, почитай уважніше статтю. Посилання на метод, де дані залишаються на своєму місці я давав в реченні
  “Про другому методі сортування списку шляхом перезацепленія якорів можете почитати на programmersforum”
  Упевнений що новачкам корисно знати і такий і такий метод.
  відповісти
Piter говорить:
20.03.2019 at 20:50
Є код готовий?
відповісти

список двонаправлений. Сортування по полях і умов

3 думки про "список двонаправлений. Сортування по полях і умов”

залишити коментар Скасувати відповідь

Останні повідомлення

недавні коментарі

Статистика