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

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

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

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

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

IElem *pbeg;
public:
IStack() { pbeg = NULL; }
~IStack();
void push(int val);
int pop();
};

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;
}

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

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;
}

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

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

int value;
ListElem *next;
};
где значение value будет также служить ключом при поиске в списке.

новые методы:
class List
{
ListElem *pbeg, *pend;
public:
List() { pend = pbeg = NULL; }
~List() { clear(); }
void push_front(int val);
int pop_front();
void clear();
…
};

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;
}

метод используется и в деструкторе.
void List::clear()
{
ListElem *ptr;
while (pbeg != NULL)
{
ptr = pbeg; pbeg = pbeg->next;
delete ptr;
}
}

не используется.
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;
}
}

списка 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; }
}

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;
}

count = 0;
for (; pcur; pcur = pcur->next)
count++;
return count;
}

(!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);

списка по ключу) и 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;
}

ListElem *pcur = pbeg;
prev = NULL;
while (pcur && pcur->value != keyval)
{
prev = pcur; pcur = pcur->next;
}
return pcur;
}

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;
}

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

модифицируемый метод поиска элемента:
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();
};

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

для пустого списка):
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);
}

если текущий не установлен):
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);
}

List::insert(int val)
{
if (!pcurpos) return false;
ListElem *pnew = new ListElem;
pnew->value = val;
pnew->next = pcurpos->next;
pcurpos->next = pnew;
return true;
}

*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;
}

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(); }
}

*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);
};

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;
}
}

pbeg;
while (pcur && pcur->value < keyval)
pcur = pcur->next;
if (pcur && pcur->value == keyval)
return pcur;
return NULL;
}

find_elem(keyval);
if (!ptr) return -1;
return ptr->value;
}

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

{
if (!pbeg) return NULL;
ListElem *ptr = pbeg;
pbeg = pbeg->next;
if (!pbeg) pend = NULL;
return ptr;
}

списка:
void SortedList::push_back(ListElem *ptr)
{
ptr->next = NULL;
if (!pbeg) pbeg = pend = ptr;
else
{ pend->next = ptr; pend = ptr; }
}

(!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;
}
}

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;
}