Шаг 6 - Еще раз о двусвязных списках

Если Вы работали, а я уверен , что Вы и сейчас работаете со списками, то у Вас могла возникнуть следующая проблема.

Какая-нибудь процедура "ходит" по списку вдоль и пеперек, при этом удаляет, что ей заблагорасудится. Как Вы знаете, для того чтобы хранить список надо всегда помнить ссылку на один из его компонентов. Думаю ссылку на центральный элемент хранят только "любители", все же остальные нормальные люди хранят адрес первого элемента. Так вот в чем же проблема ? А в том, что та "ходящая" процедура не в курсе какой элемент она удаляет, и ей все равно будь он первый, средний или последний, да хоть папа с мамой :-) Удаляет и все тут... Так что же будет если она нечаянно удалит первый элемент, адрес которого Вы храните неизвестно в каком количестве переменных. Получается, что весь список пропадет разом.

Так вот как уберечься от удаления первого элемента ? Я придумал как, хотя может это и не лучший вариант, но за 10 мин. ничего лучшего я придумать не смог.

Идея, как всегда крайне проста. Деструктор вашего класса списка надо написать таким образом, чтобы он анализировал положение удаляемого элемента списка, т.е. если удаляемый элемент находится в середине списка, то он бы удалял его обычным образом, а вот если он был первым, то не удалял себя, а удалял своего следующего по списку собрата, при этом полностью скопировав его содержимое. Надеюсь идея ясна ? Все просто, надо чтобы элемент как бы удалялся, но при этом второй строго занимал бы его прежнее место. Таким образом помня адрес первого элемента Вы можете с ним делать, что хотите, так как Вы его никогда не потеряете.

Вот программа:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

class List {
public:
	List *next;
	List *pred;
	char *text;

	List(char *TEXT);
	~List();

	Add(List *New);
	Delete();
};

List::List(char *TEXT)
{
	text=strdup(TEXT);
	next=NULL;
	pred=NULL;
};

List::~List()
{
	if (text!=NULL) free(text);
};

List::Add(List *New)
{
	List *temp;

	temp=this;
	while (temp->next!=NULL)
		temp=temp->next;

	temp->next=New;
	New->pred=temp;
};

List::Delete()
{
	List *temp;

	if (pred!=NULL)
	{
		pred->next=next;
		if (next!=NULL) next->pred=pred;
		delete this;
	} else {
		text=next->text;
		next->text=NULL;
		temp=next;
		next=temp->next;
		if (next!=NULL) next->pred=this;
		temp->pred=NULL;
		temp->next=NULL;
		delete temp;
	};
};


void WriteList(List *temp)
{
	while (temp!=NULL)
	{
		if (temp->next!=NULL) printf(" %s ->",temp->text);
		else printf(" %s",temp->text);
		temp=temp->next;
	};
	printf("\n");
};

int main()
{
	List *A=new List("Elem 1");
	A->Add(new List("Elem 2"));
	A->Add(new List("Elem 3"));
	A->Add(new List("Elem 4"));
	A->Add(new List("Elem 5"));

	WriteList(A);
	A->next->Delete();
	WriteList(A);
	A->Delete();
	WriteList(A);

	printf("\n\n");
};

Думаю все видно из программы. Только есть одно НО... Теперь Вы не сможете удалять элементы списка обычным delete. Для этого Вам придется использовать новый метод класса Delete();, который мы написали. Я кстати в первое время думал, что delete будет работать, но после первого же теста оказалось обратное. Дело в том, что содержимое следующего элемента копируется, а вот дальше delete портит ссылки капитально, и ничем их уже не восстановить. Поэтому тут же пришлось писать замену этому стандартному delete.

А вот собственно то, что выводит программа.

Elem 1 -> Elem 2 -> Elem 3 -> Elem 4 -> Elem 5
Elem 1 -> Elem 3 -> Elem 4 -> Elem 5
Elem 3 -> Elem 4 -> Elem 5

Вобщем-то все. Я только не проконтролировал утечку памяти, но думаю должно все прекрасно работать.


Предыдущий Шаг | Следующий Шаг | Оглавление
Автор Кузин Андрей.