927.00K

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

1.

Двусвязный список
nullptr
Head
m_Data
1
m_pNext
m_pPrev
nullptr
Tail
m_Data
m_pNext
2
m_size=0;
Head.m_pNext=&Tail;
Tail.m_pPrev=&Head;
m_pPrev
m_Data
m_Data
m_Data
m_pNext
m_pNext
m_pNext
m_pPrev
m_pPrev
m_pPrev

2.

Добавление узла после prev
prev
m_Data
1
Node *pn;
pn= prev->m_pNext;
this->m_pPrev= prev;
this->m_pNext= pn;
m_Data
m_pNext
m_pNext
m_pPrev
m_pPrev
prev->m_pNext= this;
pn->m_pPrev= this;
m_Data
m_pNext
prev
m_pPrev
1
pn=prev->m_pNext
m_Data
m_Data
m_pNext
m_pNext
m_pPrev
m_pPrev

3.

Исключение узла
if (m_pPrev)
m_pPrev->m_pNext=this->m_pNext;
if (m_pNext)
m_pNext->m_pPrev=this->m_pPrev;
m_Data
m_pNext
prev
m_Data
m_pPrev
m_Data
1
2
m_pNext
m_pPrev
m_Data
m_pPrev
1
m_pNext
m_pPrev
m_pNext
m_Data
m_pNext
2
m_pPrev

4.

Конструктор копирования
0
0 0
Head
Tail
0
Head
1
2
3
4
Tail
size=0
0
0
copy1
Head
Tail
0
copy2
Head
copy1
0
Tail
List::List (const List& other) //конструктор копирования
{
//1) связываем свои Head и Tail;
//2) инициализируем поля класса
//3) считываем данные из другого списка, начиная с головы, а копируем в конец своего
}

5.

Конструктор копирования (move)
0
0
0
Head
Tail
1
0
Head
2
3
1
2
3
4
Tail
4
0
0
Head
Tail
0
0
Head
//конструктор move- копирования
List::List (List&& other)
{
//1) забираем у "стражей" временного объекта весь список //отобрали
//2) замыкаем стражей временного объекта друг на друга // «обнулили»
}
Tail

6.

Оператор присваивания
0
Head
11
0
12
Head
Tail
21
0
Head
11
12
0
Head
Tail
0
Tail
22
23
24
Tail
0
0
0
0
Head
copy21
copy22
copy23
copy24
Tail
//оператор присваивания
List& List::operator=(const List& other)
{
//проверяем, что не себя копируем
//1) удаляем весь свой список (чистим)
//2) считываем данные из другого списка, начиная с головы, а копируем в конец своего
}
0

7.

Оператор присваивания (эффективный_1случай)
0
Head
0
Head
11
21
12
22
Tail
23
0
24
23
0
Head
21
22
Tail
0
Tail
24
0
Head
21
22
0
23
0
Tail
List& List::operator=(const List& other) {
//проверяем, что не себя копируем
//1) определяем рабочие переменные для узлов, следующих после Head ( для каждого списка)
//2) определяем какой из списков имеет меньший размер: min_size
//3) копируем из other в «свой» список min_size элементов (в цикле)
//4) если свой список меньше другого, то добавляем недостающие данные в ХВОСТ своего
// иначе удаляем ненужные узлы из своего списка
}

8.

Оператор присваивания (эффективный_2случай)
0
Head
11
12
13
0
Head
0
Head
21
21
22
22
Tail
21
22
Tail
Tail
0
13
0
Head
14
0
14
Tail
0
0
List& List::operator=(const List& other) {
//проверяем, что не себя копируем
//1) определяем рабочие переменные для узлов, следующих после Head ( для каждого списка)
//2) определяем какой из списков имеет меньший размер: min_size
//3) копируем из other в «свой» список min_size элементов (в цикле)
//4) если свой список меньше другого, то добавляем недостающие данные в ХВОСТ своего
// иначе удаляем ненужные узлы из своего списка
}

9.

Оператор присваивания (move)
0
Head
11
12
0
0
Tail
Head
21
0
Head
11
21
12
22
24
Tail
0
Tail
23
23
22
0
24
0
0
Head
Tail
//оператор move-присваивания
0
List& List::operator=(List&& other)
{
//проверяем, что не себя копируем
//1) удаляем весь свой список (чистим) // удалили
//2) забираем у "стражей" временного объекта весь список //отобрали
//3) замыкаем стражей временного объекта друг на друга // «обнулили»
}
0
Head
Tail
English     Русский Правила