Двусвязный список #5

Доброй ночи всем.

В столь поздний час, как ни странно, я хочу рассказать о двусвязных списках (они уже были упомянуты в этой статье).

Двусвязный список — это динамическая структура данных, а именно, он является разновидностью связных списков. Его «двусвязность» заключается в наличии двух ячеек для хранения адресов. В одной хранится адрес следующего элемента, а в другой — предыдущего (привет Кэп 🙂 ). В этом и все отличие от односвязного списка.

Крайний слева элемент так же называется головой, а крайний справа — хвостом.

Вот небольшая иллюстрация двусвязного списка:

 

twolist

Здесь А3 — голова, А1 — хвост. Еще бывают случаи, когда А1 и А3 связаны — такой список называется кольцевым.

circular

Преимущества двусвязного списка перед односвязным заключается в более удобной навигации (перемещении) по списку, при этом элемент двусвязного списка занимает больше памяти, что является минусом (в наши времена этот минус незначителен — вон недавно вышла планка оперативки на 128 ГБ). Наиболее серьезным минусом сабжа является сложная реализация вставки и удаления элементов — это обусловлено тем, что приходится изменять постоянно две ячейки адреса у элементов списка.

Но не так страшен черт, как его малюют. Его реализация на С++ вполне понятна и не должна вызывать недоумения (я надеюсь). Вот, собственно, и она:

// Реализация двусвязного списка (С)Swamp_Dok 09.04.2014
#include<iostream>

using namespace std;

class two_list // Объявляем класс двусвязного списка
{
private:

	struct list // Создаем структуру для хранения элемента списка
				//Теперь ячеек адреса две
	{
		int value; // Тут значение элемента стека
		list *back; // Указатель на элемет справа в сторону хвоста)
		list *next; //На элемент слева
	};

	list *head; // Указатель на голову списка
	int size; // Кол-во элементов стека

public:
	two_list(int value) //Конструктор класса
	{
		head=new(list); // Выделяем память под первый элемент
		head->value=value; // Записываем значение                                
		head->next=0; //Нули, так как они никуда не ссылаются.
		head->back=0; 
		size=1; // Элемент появился, значит ++ :)
	}

	int list_size() // Возвращает количество элементов списка
	{
		return size;
	}

	void list_add(int value, int k) //Добавляет value на k-е место
									//Элементы списка считаются с нуля
									// При k=0 вставится новая голова
									//При k=size вставится новый хвост
	{
		if( k>size || k<0) //Проверка на позицию
			{
				cout<<"Такого элемента нет!";
				return;//Завершаем ф-ю
			}

		size++;// Увеличиваем количество

		list *temp=head; //Записываем адрес головы

		if(k == 0) // Добавляется новая голова
		{

			head=new(list); // Память для новой головы
			temp->next=head; // Записываем в next старой головы
			head->back=temp; // Записываем в back новой головы  адрес старой
			head->next=0; // Ноль, так как слева от головы ничего нету
			head->value=value; // Записываем значение в новую голову
			return; //Завершаем функцию и ничего не возвращаем
		}

		for(int i=1;  i<k ; i++) temp=temp->back; // Находим и записываем в temp адрес элемента с номером (k-1) 

				//temp->back -- элемент, стоящий справа от вставляемого
				//temp->next -- элемент, стоящий слева от вставляемого
				list *buff=new(list); // Выделяем память  и записываем адрес выделенной памяти в buf
				buff->next=temp; // Записываем в next нового элемента адрес элемента, стоящего слева.
				buff->back=temp->back; // Записываем в back нового элемента адрес элемента, стоящего справа.

				if(temp->back!= 0 ) // Проверяем на хвостатость temp
				{
					temp->back->next=buff;//Записывает в next элемента, стоящего справа от нового, адрес нового
				}
				temp->back=buff; // Записываем в элемент, стоящий слева от нового, адрес добавленного элемента
				buff->value=value; // записываем значение в новый элемент
	}

	void list_delete(int k, int *ret) //Вытокнуть k-й элемент в ret
							//Если k=0, то выталкивается голова
	{
		if( k>=size || k<0) // Проверка
			{
				cout<<"Такого элемента нет!";
				return; //Завершаем ф-ю
			}
		size--; // Уменьшаем кол-во элементов
		list *temp=head; //Записываем адрес головы
		if(k == 0) //Удаляется голова
		{
			*ret= head->value; // Записываем значение головы
			head=head->back; //Изменяем адрес головы
			delete temp; // Удаляем старую голову
			head->next=0; // Ноль, так слева от головы ничего нету
			return;
		}

		for(int i=1;  i<=k ; i++) temp=temp->back; // Находим и записываем в temp адрес элемента с номером k 
		//temp->back -- элемент, стоящий справа от удаляемого
		//temp->next -- элемент, стоящий слева от удаляемого
		*ret=temp->value;
		if(temp->back!=0) temp->back->next=temp->next; // Проверяем, является ли удаляемый элемент хвостом
		temp->next->back=temp->back;
		delete temp;
	}

	void list_read_elem(int k,int *ret) // Cчитываем k-й и записываем в ret
	{
		if( k>=size || k<0)
			{
				cout<<"Такого элемента нет!";
				return;//Завершаем ф-ю
			}
		list *temp=head;
		for(int i=0;  i<k ; i++) temp=temp->back; // Находим и записываем в temp адрес элемента с номером k 
		*ret=temp->value;//Записываем значение элемента под номером  k
	}

};// Конец класса

В классе реализованы методы вставки/удаления/чтения любого элемента списка, что является достаточным для большинства целей — остальные предполагаемые методы является производными от базовых и реализуются за 5 минут.

Вот такие вот пирожки с котятами…

Пример использования класса:

int main()
{
	system("chcp 1251");
	int b;

	two_list a(0); // Вводим 7 элементов в список
	a.list_add(1,1);
	a.list_add(2,2);
	a.list_add(5,1);
	a.list_add(6,3);
	a.list_add(7,2);
	a.list_add(8,0);
	cout<<"Содержимое списка: ";
	for(int i=0; i<a.list_size(); i++)//Выводим весь список
	{
		a.list_read_elem(i,&b);
		cout<<b<<" ";
	}

	a.list_delete(3,&b); // Удаляем 3-й элемент
	a.list_delete(5,&b); // Удаляем 5-й элемент
	a.list_delete(4,&b); // Удаляем 4-й элемент

	cout<<endl<<"Список после обработки: ";
		for(int i=0; i<a.list_size(); i++)
		{
		a.list_read_elem(i,&b);
		cout<<b<<" ";
		}

		cout<<endl;
	system("pause");

	return 0;
}

После запуска программы получаем следующее:

 

output

К вышесказанному  добавить особо нечего. Примером использования двусвязного списка является файловая система NTFS, а вот FAT основана на односвязном списке.

На этой ноте мы завершаем увлекательное погружение в динамические структуры.

В следующей статье я расскажу о бинарных деревьях — не пропустите!

До скрой встречи.

Поддержать сайт и автора: Z208212694629
R429062753687
Яндекс деньги - https://money.yandex.ru/to/410013974912682

Подпишись:
На мой канал youtube
На рассылку свежих статей
На группу ВК

Понравилась статья? Поделись с друзьями)

Опубликовать в Google Buzz
Опубликовать в Google Plus
Опубликовать в LiveJournal
Опубликовать в Мой Мир
Опубликовать в Одноклассники

Двусвязный список #5: 2 комментария

  1. Уведомление: Указатели? Это просто! С++ #1 | Всего наилучшего — 73!

Добавить комментарий