Основы программирования. Линейные списки

1. Основы программирования

Линейные списки
1

2. Список

Линейный список – это контейнер, в котором элементы
располагаются в памяти в произвольном порядке, а
связь между ними обеспечивается с помощью
указателей (ссылок).
Элемент однонаправленного списка состоит из двух
частей – информационной (собственно данных) и
указателя (ссылки) на следующий элемент списка.
Как правило, память для каждого элемента
выделяется динамически.
Для доступа к начальному элементу списка
используется отдельный указатель (ссылка).
Последний элемент списка не ссылается ни на что, т.е.
имеет нулевой указатель (пустую ссылку). Во многих
случаях выгодно хранить отдельный указатель на
2
последний элемент.

3. Иллюстрация

pbeg – указатель на начальный элемент,
pend – указатель на конечный элемент
(если он нужен).
Доступ к элементам осуществляется последовательно,
по указателям (ссылкам). Если необходимо
обеспечить переход не только к последующим, но и к
предыдущим элементам, в элементы нужно
включить еще один указатель (ссылку) – на
предыдущий элемент (нуль для начального
элемента списка). Соответствующий список будет
двунаправленным.
3

4. Элемент списка

Для представления элемента списка нужно создать
соответствующий тип, т.е. описать структуру (класс).
Пусть информационная часть элемента – это просто
целое число. Тогда новый тип будет выглядеть
следующим образом:
struct IElem
{
int value;
IElem *next;
}
По умолчанию в структуре все поля являются
открытыми (public), поэтому никаких дополнительных
методов доступа к ним не надо.
4

5. Стек на основе списка

На основе списка можно строить другие структуры
данных. Для примера модифицируем стек из раздела
«Структуры и классы», сохраняя весь открытый
интерфейс.
Учитывая, что добавление и извлечение элементов
стека производится в его вершине, будем считать
вершиной начальный элемент списка (т.е. начальный
указатель списка всегда показывает на вершину стека,
а конечный указатель вообще не нужен).
Элементы списка выделяются динамически, поэтому
для стека не нужен массив, и количество элементов
стека не ограничено.
5

6. Пример класса для стека

Для описания элементов стека используем структуру
IElem.
class IStack
{
IElem *pbeg;
public:
IStack() { pbeg = NULL; }
~IStack();
void push(int val);
int pop();
};
6

7. Реализация методов IStack

void IStack::push(int val)
{
IElem *ptr = new IElem;
ptr->value = val; ptr->next = pbeg;
pbeg = ptr;
}
int IStack::pop()
{
if (!pbeg) return -1;
IElem *ptr = pbeg;
int val = pbeg->value;
pbeg = pbeg->next;
delete ptr;
return val;
}
7

8. Деструктор класса IStack

Деструктор класса IStack должен удалять все
элементы списка. Используем pbeg для указания на
текущий удаляемый элемент списка.
void IStack::~IStack()
{
IElem *ptr;
while (pbeg != NULL)
{
ptr = pbeg; pbeg = pbeg->next;
delete ptr;
}
}
8

9. Использование стеков

void main()
{
int i;
IStack a, *pb;
for (i = 0; i < 10; i++)
a.push(i*2);
pb = new IStack;
for (i = 0; i < 20; i++)
pb->push(i+10);
for (i = 0; i < 22; i++)
cout << pb->pop() << endl;
delete pb;
}
9

10. Информационная часть элементов

Информационная часть элементов списка может быть
представлена любым типом, в том числе, структурой
или классом. Например, для списка линий это может
быть:
class PLine
{
double *x, *y;
int key; int length; …
public:
void setlength(int len);
void free();
void setp(int n,double vx,double vy);
…
};
10

11. Элемент списка линий

Элемент списка может содержать либо саму линию:
struct ListElem
{
PLine line;
ListElem *next;
};
либо указатель на динамически выделяемую линию:
struct ListElem
{
PLine *line;
ListElem *next;
};
11

12. Элемент списка целых

Для простоты будем рассматривать список целых с
элементами
struct ListElem
{
int value;
ListElem *next;
};
где значение value будет также служить ключом при
поиске в списке.
12

13. Класс для списка целых

Начальный вид класса, в который мы будем добавлять
новые методы:
class List
{
ListElem *pbeg, *pend;
public:
List() { pend = pbeg = NULL; }
~List() { clear(); }
void push_front(int val);
int pop_front();
void clear();
…
};
13

14. Операции с начальным элементом

void List::push_front(int val)
{
ListElem *pnew = new ListElem;
pnew->value = val; pnew->next = pbeg;
pbeg = pnew; if (!pend) pend = pnew;
}
int List::pop_front()
{
if (!pbeg) return -1;
ListElem *ptr = pbeg;
int val = pbeg->value;
pbeg = pbeg->next;
if (!pbeg) pend = NULL;
delete ptr; return val;
}
14

15. Очистка списка

Открытый метод clear очищает список, удаляя все его
элементы. Данный метод используется и в
деструкторе.
void List::clear()
{
ListElem *ptr;
while (pbeg != NULL)
{
ptr = pbeg; pbeg = pbeg->next;
delete ptr;
}
}
15

16. Добавление элемента в конец списка

Вариант 1: указатель на последний элемент pend не
используется.
void List::push_back(int val)
{
ListElem *pcur, *pnew = new ListElem;
pnew->value = val; pnew->next = NULL;
if (!pbeg) pbeg = pnew;
else
{
for (pcur = pbeg; pcur->next; )
pcur = pcur->next;
pcur->next = pnew;
}
}
16

17. Добавление элемента в конец списка

Вариант 2: используется указатель на последний
элемент списка pend.
void List::push_back(int val)
{
ListElem *pnew = new ListElem;
pnew->value = val; pnew->next = NULL;
if (!pbeg) pbeg = pend = pnew;
else
{ pend->next = pnew; pend = pnew; }
}
17

18. Извлечение последнего элемента списка

int List::pop_back()
{
if (!pbeg) return -1;
ListElem *pcur = pbeg, *prem = pend;
int val = pend->value;
if (pbeg == pend) pbeg = pend = NULL;
else
{
while (pcur->next != pend)
pcur = pcur->next;
pcur->next = NULL; pend = pcur;
}
delete prem; return val;
}
18

19. Вычисление длины списка

int List::getcount()
{
ListElem *pcur = pbeg;
int count = 0;
for (; pcur; pcur = pcur->next)
count++;
return count;
}
19

20. Сцепление двух списков

void List::join(List& lst)
{
if (!lst.pbeg) return;
if (!pbeg) pbeg = lst.pbeg;
else pend->next = lst.pbeg;
pend = lst.pend;
lst.pbeg = lst.pend = NULL;
}
Вызов:
List a, b; int i;
for (i = 0; i < 10; i++) a.push_back(i*2);
for (i = 0; i < 20; i++) b.push_back(i+1);
a.join(b);
20

21. Поиск в списке по ключу

Для поиска реализуем private-метод find_elem (поиск
элемента списка по ключу) и public-метод find (поиск
значения по ключу):
ListElem* List::find_elem(int keyval)
{
ListElem *pcur = pbeg;
for (; pcur; pcur = pcur->next)
if (pcur->value == keyval) break;
return pcur;
}
int List::find(int keyval)
{
ListElem *ptr = find_elem(keyval);
if (!ptr) return -1;
return ptr->value;
}
21

22. Поиск элемента по ключу (для удаления)

ListElem* List::find_elem(int keyval,
ListElem*& prev)
{
ListElem *pcur = pbeg;
prev = NULL;
while (pcur && pcur->value != keyval)
{
prev = pcur; pcur = pcur->next;
}
return pcur;
}
22

23. Удаление элемента с заданным ключом

Public-метод удаления элемента с заданным
значением ключа:
bool List::remove(int keyval)
{
ListElem *prem, *prev;
prem = find_elem(keyval, prev);
if (!prem) return false;
if (!prev) pbeg = pbeg->next;
else prev->next = prem->next;
if (prem == pend) pend = prev;
delete prem;
return true;
}
23

24. Операции с текущим элементом списка

Во многих задачах пользователю требуется выполнять
операции с конкретным (текущим) элементом
списка, например:
• модифицировать информационную часть текущего
элемента
• вставить новый элемент после текущего
• удалить текущий элемент
• последовательно обработать все элементы от
начала до конца списка.
При этом пользователь должен работать только с
информационной частью элементов, а формат
списка и его элементов должны быть скрытыми.
Чтобы реализовать это, можно добавить в класс еще
одно private-поле (указатель на текущий элемент),
модифицировать старые и включить новые методы.
24

25. Модификация класса List

В данном примере приведены только новые члены класса
и модифицируемый метод поиска элемента:
class List
{
ListElem *pbeg, *pend, *pcurpos;
ListElem *find_elem(int keyval);
public:
List() { pend = pbeg = pcurpos = NULL; }
int *get_first();
int *get_last();
int *get_next();
int *get_current();
bool insert(int val);
bool remove();
};
25

26. Модификация метода find_elem

Private-метод find_elem ищет элемент списка по ключу
и изменяет указатель на текущий элемент:
ListElem* List::find_elem(int keyval)
{
ListElem *pcur = pbeg;
for (; pcur; pcur = pcur->next)
if (pcur->value == keyval) break;
pcurpos = pcur;
return pcur;
}
26

27. Методы доступа к информационной части

Получение адреса информационной части начального
элемента (NULL для пустого списка):
int* List::get_first()
{
pcurpos = pbeg;
if (!pcurpos) return NULL;
return &(pcurpos->value);
}
Получение адреса информационной части последнего
элемента (NULL для пустого списка):
int* List::get_last()
{
pcurpos = pend;
if (!pcurpos) return NULL;
return &(pcurpos->value);
}
27

28. Методы доступа к информационной части

Получение адреса информационной части текущего
элемента (NULL, если текущий не установлен):
int* List::get_current()
{
if (!pcurpos) return NULL;
return &(pcurpos->value);
}
Получение адреса информационной части элемента,
следующего за текущим (или NULL):
int* List::get_next()
{
if (!pcurpos) return NULL;
pcurpos = pcurpos->next;
if (!pcurpos) return NULL;
return &(pcurpos->value);
}
28

29. Включение нового элемента

Включение нового элемента после текущего (текущая
позиция не изменяется):
bool List::insert(int val)
{
if (!pcurpos) return false;
ListElem *pnew = new ListElem;
pnew->value = val;
pnew->next = pcurpos->next;
pcurpos->next = pnew;
return true;
}
29

30. Удаление текущего элемента

bool List::remove()
{
if (!pcurpos) return false;
ListElem *pcur = pbeg, *prev = NULL;
while (pcur != pcurpos)
{ prev = pcur; pcur = pcur->next; }
if (!prev) pbeg = pcur->next;
else prev->next = pcur->next;
pcurpos = pcur->next;
if (!pbeg) pend = pcurpos = NULL;
else if (pend == pcur) pend = prev;
delete pcur;
return true;
}
30

31. Пример работы с текущим элементом

void main()
{ List a; int i, *pval;
for (i = 0; i < 50; i++)
a.push_back(rand()%100);
for (pval = a.get_first(); pval;)
{
if (pval->value%2) (pval->value)--;
pval = a.get_next();
}
a.get_first();
if (!a.get_next()) return;
if (get_current()->value < 50)
{ a.insert(77); a.remove(); }
31
}

32. Класс для упорядоченного списка целых

class SortedList
{ ListElem *pbeg, *pend;
ListElem *find_elem(int keyval,
ListElem*& prev);
ListElem *find_elem(int keyval);
ListElem *pop_front();
void push_back(ListElem *ptr);
public:
SortedList() { pend = pbeg = NULL; }
~SortedList() { clear(); }
void clear();
bool remove(int keyval);
void add(int val);
int find(int keyval);
void merge(SortedList &lst);
};
32

33. Добавление к упорядоченному списку

void SortedList::add(int val)
{
ListElem *pnew = new ListElem;
pnew->value = val; pnew->next = NULL;
if (!pbeg) pbeg = pend = pnew;
else if (pbeg->value >= val)
{ pnew->next = pbeg; pbeg = pnew; }
else if (pend->value < val)
{ pend->next = pnew; pend = pnew; }
else
{
ListElem *prev=pbeg, *pnex=pbeg->next;
while (pnex->value < val)
{ prev = pnex; pnex = pnex->next; }
prev->next = pnew; pnew->next = pnex;
}
}
33

34. Поиск элемента в упорядоченном списке

ListElem* SortedList::find_elem(int keyval)
{
ListElem *pcur = pbeg;
while (pcur && pcur->value < keyval)
pcur = pcur->next;
if (pcur && pcur->value == keyval)
return pcur;
return NULL;
}
34

35. Поиск значения в упорядоченном списке

int SortedList::find(int keyval)
{
ListElem *ptr = find_elem(keyval);
if (!ptr) return -1;
return ptr->value;
}
35

36. Идея слияния двух упорядоченных списков

Слияние двух упорядоченных списков A (текущего) и
B можно проводить, строя дополнительный
упорядоченный список C. При этом не нужно
создавать новых элементов: надо извлекать
начальные элементы либо из A, либо из B, и
переносить их в конец C.
После заполнения C списки A и B будут пустыми. Если
необходимо, чтобы объединенный список хранился
в A, необходимо просто перенести туда значения
pbeg и pend из C, а затем очистить эти поля в C (это
необходимо, чтобы при работе деструктора C не
удалялись элементы списка).
36

37. Извлечение начального элемента

Private-метод извлечения начального элемента и
возврата его адреса:
ListElem *SortedList::pop_front()
{
if (!pbeg) return NULL;
ListElem *ptr = pbeg;
pbeg = pbeg->next;
if (!pbeg) pend = NULL;
return ptr;
}
37

38. Добавление элемента в конец списка

Private-метод добавления элемента, заданного
адресом, в конец списка:
void SortedList::push_back(ListElem *ptr)
{
ptr->next = NULL;
if (!pbeg) pbeg = pend = ptr;
else
{ pend->next = ptr; pend = ptr; }
}
38

39. Слияние двух упорядоченных списков

void SortedList::merge(SortedList& B) {
if (!B.pbeg) return;
if (!pbeg){
pbeg = B.pbeg; pend = B.pend;
B.pbeg = B.pend = NULL;
}
else
{ SortedList C; ListElem *ptr;
while (pbeg || B.pbeg) {
if (!B.pbeg) ptr = pop_front();
else if (!pbeg) ptr = B.pop_front();
else if (pbeg->value <= (B.pbeg)->value)
ptr = pop_front();
else ptr = B.pop_front();
C.push_back(ptr);
}
pbeg = C.pbeg; pend = C.pend;
C.pbeg = C.pend = NULL;
}
}
39

40. Использование упорядоченных списков

void main()
{
SortedList a, b; int i;
for (i = 0; i < 30; i++)
a.add(rand()%100);
for (i = 0; i < 20; i++)
b.add(rand()%100);
if (a.find(99) != -1) a.remove(99);
b.merge(a);
cout << b.getcount() << endl;
}
40