Алгоритмизация и программирование. Динамические структуры данных

содержит две ссылки.
Каждый элемент содержит ссылку на следующий и предыдущий элемент.
Вводятся две переменные-указатели – ссылка на «голову» списка (Head) и на «хвост» - послед-ний элемент (Tail).

указателя на следующий и предыдущий узел.

Схема двухсвязного списка

Узел1

Узел2

Узел3

Голова
списка

Хвост
списка

Node *prev;
};
Node * PNode;

Синтаксис объявления двухсвязного списка в С++:

Двухсвязные списки

В программе надо объявить два новых типа данных – узел списка Node и указатель на него PNode.

*PNode;
PNode Head = NULL;
PNode Tail = NULL;

Пример. Объявление двухсвязного списка словаря:

Двухсвязные списки

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

конец списка
После заданного узла
Перед заданным узлом
Проход по списку
Поиск узла
Удаление узла

его, то есть выделить память под узел и запомнить адрес выделенного блока.
Будем считать, что надо добавить к списку узел, соответствующий новому слову, которое записано в переменной NewWord.
Составим функцию, которая создает новый узел в памяти и возвращает его адрес. При записи данных в узел используется обращение к полям структуры через указатель.

PNode CreateNode ( string NewWord )
{
PNode NewNode = new Node;
NewNode->word = NewWord;
NewNode->next = NULL;
return NewNode;
}

// функция создания узла
// указатель на новый узел
// записать слово
// следующего узла нет
// результат функции – адрес узла

Было!! Создание узла для односвязного списка

А что нужно изменить для двухсвязного списка?

Pnode CreateNode ( string NewWord )
{ PNode NewNode = new Node;
NewNode->word = NewWord;
NewNode->next = NULL;
NewNode->prev = NULL;
return NewNode;
}

// функция создания узла
// указатель на новый узел
// записать слово
// следующего узла нет
// предыдущего узла нет
// результат функции – адрес узла

списка надо:

установить ссылку next узла NewNode на голову существующего списка и его ссылку prev в NULL;

NewNode->next = Head;
NewNode->prev= NULL;

2) установить ссылку prev бывшего первого узла (если он существовал) на NewNode;

if ( Head!=NULL )
Head->prev = NewNode;

3) установить голову списка на новый узел;

4) если в списке не было ни одного элемента, хвост списка также устанавливается на новый узел.

Head = NewNode;

if ( Tail == NULL ) Tail = Head;

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

void AddFirst (PNode &Head, PNode &Tail, PNode NewNode)
{
NewNode->next = Head;
NewNode->prev = NULL;
if ( Head != NULL )
Head->prev = NewNode;
Head = NewNode;
if ( Tail == NULL ) Tail = Head;
}

1) установить ссылку next узла NewNode на голову существующего списка и его ссылку prev в NULL;
2) установить ссылку prev бывшего первого узла (если он существовал) на NewNode;
3) установить голову списка на новый узел;
4) если в списке не было ни одного элемента, хвост списка также устанавливается на новый узел.

// функция добавления нового узла в начало списка

конец списка проходит совершенно аналогично, в процедуре надо везде заменить Head на Tail и наоборот, а также поменять prev и next.

установить ссылку prev узла NewNode на хвост существующего списка и его ссылку next в NULL;

NewNode->prev = Tail;
NewNode->next = NULL;

2) установить ссылку next бывшего конечного узла (если он существовал) на NewNode;

if ( Tail!=NULL )
Tail->next = NewNode;

3) установить хвост списка на новый узел;

4) если в списке не было ни одного элемента, голову списка также устанавливается на новый узел.

Tail = NewNode;

if ( Head == NULL )
Head = Tail;

AddFirst (PNode &Head, PNode &Tail, PNode NewNode)
{
NewNode->next = Head;
NewNode->prev = NULL;
if ( Head != NULL )
Head->prev = NewNode;
Head = NewNode;
if ( Tail == NULL ) Tail = Head;
}

// функция добавления нового узла в конец списка

NewNode->prev = Tail;
NewNode->next = NULL;
if ( Tail != NULL )
Tail->next = NewNode;
Tail = NewNode;
 if (Head == NULL) Head = Tail;

AddLast

одного из существующих узлов в списке. Требуется вставить в список новый узел после узла с адресом p.

Если узел p является последним, то операция сводится к добавлению в конец списка

if ( p->next == NULL)
AddLast (Head, Tail, NewNode);

Если узел p – не последний, то операция вставки выполняется в два этапа:

NewNode->next = p->next;
NewNode->prev = p;

1) установить ссылки нового узла на следующий за данным (next) и предшествующий ему (prev);

2) установить ссылки соседних узлов так, чтобы включить NewNode в список.

p->next->prev = NewNode;

p->next = NewNode;

и

узла после которого, хотим вставить новый узел и адрес самого нового узла.

void AddAfter (PNode &Head, PNode &Tail, PNode p, PNode NewNode)
{ if ( p->next == NULL)
AddLast (Head, Tail, NewNode);
else
{
NewNode->next = p->next;
NewNode->prev = p;
p->next->prev = NewNode;
p->next = NewNode;
}
}

1) Если узел p является последним, то вставить NewNode в конец списка.
2) Иначе:
a) установить ссылки нового узла на следующий за данным (next) и предшествующий
ему (prev);
б) установить ссылки соседних узлов так, чтобы включить NewNode в список.

// функция добавления нового узла после указанного

после заданного, и является симметричной операцией!!

Если узел p является первым, то операция сводится к добавлению в начало списка

if ( p == Head)
AddFirst (Head, Tail, NewNode);

Если узел p – не последний, то операция вставки выполняется в два этапа:

NewNode->next = p;
NewNode->prev = p->prev;

1) установить ссылки нового узла на следующий за данным (next) и предшествующий ему (prev);

2) установить ссылки соседних узлов так, чтобы включить NewNode в список.

p->prev->next = NewNode;

p->prev = NewNode;

и

узла перед которого, хотим вставить новый узел и адрес самого нового узла.

void AddBefore (PNode &Head, PNode &Tail, PNode p, PNode NewNode)
{ if ( p == Head)
AddFirst (Head, Tail, NewNode);
else
{
NewNode->next = p;
NewNode->prev = p->prev;
p->prev->next = NewNode;
p->prev = NewNode;
}
}

1) Если узел p является первым, то вставить NewNode в начало списка.
2) Иначе:
a) установить ссылки нового узла на следующий за данным (next) и предшествующий
ему (prev);
б) установить ссылки соседних узлов так, чтобы включить NewNode в список.

// функция добавления нового узла после указанного

)
{
p = p->next;
}

// переходим к следующему узлу

// Обход списка с головы списка

// начинаем с головы списка

// пока не дошли до конца
// делаем что-нибудь с узлом p

Проход по двусвязному списку может выполняться в двух направлениях :
– от головы к хвосту (как для односвязного) , используя указатель next, продвигаться к следующему узлу.
- от хвоста к голове, используя указатель prev, продвигаться к предыдущему узлу.

PNode p = Tail;
while ( p != NULL )
{
p = p->prev;
}

// Обход списка с хвоста списка

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

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

if (Head == OldNode)
{
Head = OldNode->next;

3) Иначе, это не первый элемент. Изменяем ссылки соседних
узлов

4) Иначе, удалили последний элемент

OldNode->prev->next = OldNode->next;

Tail = NULL;

5) Освобождаем память, которую занимал узел.

delete OldNode;

Удаление узла

if ( OldNode->next !=NULL)
OldNode->next->prev = OldNode->prev;

if ( Head != NULL )
Head->prev = NULL;
else Tail = NULL;
}

OldNode)
{ Head = OldNode->next;
if ( Head !=NULL)
Head->prev = NULL;
else
Tail = NULL;
}
else
{ OldNode->prev->next = OldNode->next;
if ( OldNode->next !=NULL)
OldNode->next->prev = OldNode->prev;
else
Tail = NULL;
}
delete OldNode;
}

// удаляем первый элемент

// изменяем ссылки соседних элементов

// освобождаем память

// удаляем единственный элемент

// удаляем последний элемент

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

1) начать с головы списка;

2) пока текущий элемент существует (указатель – не NULL), проверить нужное условие и перейти к следующему элементу;

3) закончить, когда найден
требуемый элемент или все элементы списка
просмотрены.

Поиск по данным

PNode q = Head;

while (q->word != NewWord && q!=NULL)
q = q->next;

return q;

= Head;
while (q->word != NewWord && q != NULL)
q = q->next;
return q;
}

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

// функция поиска узла в списке

//начать с головы списка

//пока текущий элемент существует
(указатель – не NULL), проверить
нужное условие и перейти к
следующему элементу

Например, следующая функция ищет в списке элемент, соответствующий заданному слову (для которого поле word совпадает с заданной строкой NewWord), и возвращает его адрес или NULL, если такого узла нет.

Для того, чтобы добавить новое слово в нужное место (в алфавитном порядке), требуется найти адрес узла, перед которым надо вставить новое слово.
Это будет первый от начала списка узел, для которого «его»
слово окажется «больше», чем новое слово.
Поэтому достаточно просто изменить условие в цикле while в функции Find, учитывая, что сравнение q->word < NewWord возвращает значение «больше» или «меньше» по естественному лексикографичексому порядку.

Поиск по данным в определённом порядке - алфавитном

текущий элемент существует (указатель – не NULL), проверить условие и перейти к следующему элементу;

3) закончить, когда найден
требуемый элемент или все элементы списка
просмотрены.

PNode q = Head;

while (q->word < NewWord && q!=NULL)
q = q->next;

return q;

Куда его вставить?

Будем искать место – адрес узла,
перед которым нужно вставить
новый узел.
Чтобы его данные NewWord
были меньше, чем данные у
узла перед ним.

PNode q = Head;
while (q->word < NewWord && q != NULL)
q = q->next;
return q;
}

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

// функция поиска узла по порядку в списке

//начать с головы списка

//пока текущий элемент существует
(указатель – не NULL), проверить
нужное условие и перейти к
следующему элементу

Эта функция вернет адрес узла, перед которым надо вставить новое слово , когда сравнение вернет true, или NULL, если слово надо добавить в конец списка.

word;
int count;
Node *next;
Node *prev;
};
typedef Node *PNode;
// Создание элемента списка 
PNode CreateNode ( string NewWord )
{
PNode NewNode = new Node;
NewNode->word= NewWord;
NewNode->count = 1;
NewNode->next = NULL;
NewNode->prev= NULL;
return NewNode; /
}
 // и так далее описание всех функций

Пример. Двухсвязный список словарь

PNode pnew, pfind;
  int t; string newslovo;
do
{
cout<<"введите от 1 до 5 или 0 - выход"< cout<<" 0 - выход "< cout<<" 1 - добавить новый элемент в конец списка "< cout<<" 2 - вывод списка "< cout<<" 3 - добавить новый элемент после выбранного "< cout<<" 4 - добавить новый элемент по алфавиту "< cout<<" 5 - добавить новый элемент перед выбранным "< cout<<" 6 - удалить элемент "< cout<  cin>>t;
  switch (t)
{
}

создаем новый узел
if (Head==NULL)
AddFirst (Head, Tail, pnew) ; //вставляем на первое место
else
AddLast (Head, Tail, pnew) ; //вставляем в конец списка
break;
case 2 :
pnew=Head; // вывод списка на экран
while (pnew!=NULL)
{
cout<word<<"\t"<count< pnew=pnew->next;
}
break;
case 3:
/////
};
}
while (t!=0);
  return 0;

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

друг на друга.