Форум программистов
 
О проблемах, например, с регистрацией пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail, а тут можно восстановить пароль.

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Здесь нужно купить рекламу за 20 тыс руб в месяц! ) пишите сюда - alarforum@yandex.ru
Без учёта ботов - 20000 человек в день, 350000 в месяц.

Ответ
 
Опции темы
Старый 09.02.2020, 17:39   #1
Daninil
Новичок
Джуниор
 
Регистрация: 09.02.2020
Сообщений: 1
По умолчанию Сортировка в двусвязном списке

Никак не могу реализовать сортировку по убыванию, помогите пожалуйста ее сделать

Код:
#include <iostream>
#include <windows.h>
#include <iomanip>
#include <cstring>
#include <algorithm>

using namespace std;

template <typename T>
class List
{
public:

	//Длина списка
	int GetSize() { return Size; }

	//Очистить список
	void clear();

	//Добавить элемент в начало списка
	void push_front(T data);

	//Добавить элемент в конец списка
	void push_back(T data);

	//Удалить элемент из начала списка
	void pop_front();

	//Удалить элемент из конца списка
	void pop_back();

	//Добавить элемент по указанному индексу
	void insert(T data, int index);

	//Удалить элемент по указанному индексу
	void removeAt(int index);

	T& operator [] (const int index);

	//Вывести список на экран
	void ShowData();



	
	List <T>();
	~List <T>();

private:

	template <typename T>
	class Node
	{
	public:
		Node(T data = T(), Node* pNext = nullptr, Node* pPrev = nullptr)
		{
			this->data = data;
			this->pNext = pNext;
			this->pPrev = pPrev;
		}

		T data;
		Node* pNext;
		Node* pPrev;
	};

	Node <T>* head;
	Node <T>* tail;
	int Size;

};


List <int> lst;
template <typename T> List <T>::List()
{
	head = nullptr;
	tail = nullptr;
	Size = 0;
}

template <typename T> List <T>::~List()
{
	clear();
}

template<typename T>
void List<T>::clear()
{
	while (Size)
	{
		pop_front();
	}
}

template <typename T>
void List <T>::push_front(T data)
{
	if (Size > 1)
	{
		Node <T>* temp = head;
		head = new Node <T>(data, head);
		temp->pPrev = head;
	}
	else if (Size == 1)
	{
		head = new Node <T>(data, head);
		tail->pPrev = this->head;
	}
	else
	{
		head = tail = new Node <T>(data, head, tail);
	}
	Size++;
}

template <typename T>
void List <T>::push_back(T data)
{
	if (Size > 1)
	{
		Node <T>* temp = tail;
		tail = new Node <T>(data, nullptr, tail);
		temp->pNext = tail;
	}
	else if (Size == 1)
	{
		tail = new Node <T>(data, nullptr, tail);
		head->pNext = this->tail;
	}
	else
	{
		head = tail = new Node <T>(data, head, tail);
	}
	Size++;
}

template <typename T>
void List <T>::pop_front()
{
	if (Size > 1)
	{
		Node <T>* temp = head;
		head = head->pNext;
		delete temp;
	}
	else if (Size == 1)
	{
		Node <T>* temp = head;
		tail = head = head->pNext;
		delete temp;
	}

	Size--;
}

template <typename T>
void List <T>::pop_back()
{
	if (Size > 1)
	{
		Node <T>* temp = tail;
		tail = tail->pPrev;
		delete temp;
	}
	else if (Size == 1)
	{
		Node <T>* temp = tail;
		tail = head = tail->pPrev;
		delete temp;
	}

	Size--;
}

template <typename T>
void List <T>::insert(T data, int index)
{
	if (index == 0) push_front(data);

	else if (index == Size || index > Size) push_back(data);


	else if (index <= Size / 2)
	{
		Node<T>* previous = this->head;
		for (int i = 0; i < index - 1; i++)
		{
			previous = previous->pNext;
		}

		Node<T>* newNode = new Node<T>(data, previous->pNext, previous);

		previous->pNext = newNode;
		Node<T>* next = newNode->pNext;
		next->pPrev = newNode;

		Size++;
	}

	else if (index > Size / 2)
	{
		Node<T>* next = this->tail;
		for (int i = Size - 1; index < i; i--)
		{
			next = next->pPrev;
		}

		Node<T>* newNode = new Node<T>(data, next, next->pPrev);

		next->pPrev = newNode;
		Node<T>* previous = newNode->pPrev;
		previous->pNext = newNode;

		Size++;
	}
}

template <typename T>
void List <T>::removeAt(int index)
{
	if (index == 0) pop_front();

	else if (index == Size || index > Size) pop_back();


	else if (index <= Size / 2)
	{
		Node<T>* previous = this->head;
		for (int i = 0; i < index - 1; i++)
		{
			previous = previous->pNext;
		}

		Node<T>* toDelete = previous->pNext;
		previous->pNext = toDelete->pNext;
		Node<T>* next = toDelete->pNext;
		delete toDelete;
		next->pPrev = previous;

		Size--;
	}

	else if (index > Size / 2)
	{
		Node<T>* next = this->tail;
		for (int i = Size - 1; index < i; i--)
		{
			next = next->pPrev;
		}

		Node<T>* toDelete = next->pPrev;
		next->pPrev = toDelete->pPrev;
		Node<T>* previous = toDelete->pPrev;
		delete toDelete;
		previous->pNext = next;

		Size--;
	}
}

template <typename T>
T& List <T>::operator[] (const int index)
{
	if (index <= Size / 2)
	{
		int counter = 0;
		Node <T>* current = this->head;

		while (current != nullptr)
		{
			if (counter == index) return current->data;
			current = current->pNext;
			counter++;
		}
	}
	else
	{
		int counter = Size - 1;
		Node <T>* current = this->tail;

		while (current != nullptr)
		{
			if (counter == index) return current->data;
			current = current->pPrev;
			counter--;
		}
	}
}

template <typename T>
void List <T>::ShowData()
{
	std::cout << "Список:" << std::endl;
	std::cout << '\n';
	for (size_t i = 0; i < lst.GetSize(); i++) {

		std::cout <<lst[i]<< '|';

	}
	std::cout << '\n';
	std::cout << '\n';
}



int main()
{
	SetConsoleOutputCP(1251);
	SetConsoleCP(1251);


	int n;

	for (int i = 0; i < 10; i++)
	{
		n = rand() % 99;

		lst.push_back(n);

	}
	while (true) {

		int variant;
		std::cout << "Выберите вариант \n" << std::endl;
		std::cout << "1. Добавить элемент \n"
			<< "2. Изменить элемент \n"
			<< "3. Удалить элемент \n"
			<< "4. Отсортировать элементы по убыванию \n"
			<< "5. Вывести элементы \n"
			<< std::endl;
		std::cout << ">>> ";
		std::cin >> variant;



		switch (variant) {
		case 1:
		{
			int N;
			int M;
			std::cout << "Добавить число: ";
			std::cin >> M;
			std::cout << "\n";
			std::cout << "Куда вставить: ";
			std::cin >> N;
			lst.insert(M, N);
			break;
		}
		case 2:
		{
			int N;
			int M;
			std::cout << "Какое число изменить: ";
			std::cin >> N;
			std::cout << "\n";
			std::cout << "На какое число изменить: ";
			std::cin >> M;
			lst.removeAt(N);
			lst.insert(M, N);
			break;
		}
		case 3:
		{
			int N;
			std::cout << "\n";
			std::cout << "Удалить число: ";
			std::cin >> N;
			lst.removeAt(N);			
			break;
		}
		case 4:
		{
	
			lst.ShowData();
			break;
		}
		case 5:
		{
			lst.ShowData();
			break;
		}
		}
	}
	return 0;
}
Daninil вне форума Ответить с цитированием
Ответ

Здесь нужно купить рекламу за 20 тыс руб в месяц! ) пишите сюда - alarforum@yandex.ru
Без учёта ботов - 20000 человек в день, 350000 в месяц.

Опции темы


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Указатель на следующий элемент в двусвязном списке с++ Вероника99 Помощь студентам 1 07.05.2016 21:04
Segfault в двусвязном списке в си Глеб Давыдов Помощь студентам 4 03.03.2016 23:06
помогите исправить процедуру Del,в двусвязном списке svetik290895 Общие вопросы C/C++ 0 10.05.2015 19:32
Удаление элемента в двусвязном списке (Delphi). tgig Помощь студентам 4 10.10.2013 09:36
Сортировка char в двусвязном списке preanik Помощь студентам 0 12.05.2013 01:18


Проекты отопления, пеллетные котлы, бойлеры, радиаторы
интернет магазин respective.ru
Пеллетный котёл Emtas
котлы EMTAS
Здесь нужно купить рекламу за 7 тыс руб в месяц! )
пишите сюда - alarforum@yandex.ru
ИКС 840