Similar presentations:
Основы программирования. Линейные списки
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