Связные списки


На главную

Краткое описание

Связный список - это разновидность линейных структур данных, представляющая собой последовательность элементов, обычно отсортированную в соответствии с заданным правилом. Последовательность может содержать любое количество элементов, поскольку при создании списка используется динамическое распределение памяти.

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

Схема, изображающая связный и двусвязный списки из трех элементов:
Связный список

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


Создание простого связного списка

В качестве примера рассмотрим связный список, хранящий целые числа. Элементы списка сортируются по возрастанию в зависимости от величины числа, которое хранится в данном элементе.
Каждый элемент списка является экземпляром структуры, которая описывается следующим образом:
struct TNode {
int value;
TNode* pnext;
TNode(int val): pnext(0), value(val) {}
};
Здесь pnext - указатель на следующий элемент списка, а value - поле для хранения информации.

Для добавления нового элемента к списку используется функция add2list():
void add2list(TNode **pphead, int val) {
TNode **pp = pphead, *pnew;
while(*pp) {
if(val < (*pp)->value)
break;
else
pp = &((*pp)->pnext);
}
pnew = new TNode(val);
pnew->pnext = *pp;
*pp = pnew;
}
Здесь pphead - это указатель на указатель на голову списка (т.е. на его первый элемент), val - значение, которое необходимо добавить в список. При добавлении нового элемента списка учитывается величина числа, которое будет помещено в информационное поле создаваемого элемента. Таким образом, упорядоченность элементов списка, которые расположены по возрастанию, не нарушается, и список остается отсортированным.

Вывести спискок на экран можно с помощью функции print():
void print(TNode *phead) {
TNode* p = phead;
while(p) {
cout << p->value << ' ';
p = p->pnext;
}
cout << endl;
}
Поскольку память для элементов списка выделяется динамически, после окончания работы со списком необходимо явно удалить все его элементы. Функция удаления элементов списка может быть реализована так:
void deleteList(TNode *phead) {
if(phead) {
deleteList(phead->pnext);
if(phead)
delete phead;
}
}
Протестировать функции для работы со связным списком можно следующим образом:
int main() {
TNode *phead = 0;
srand(time(0));
for(int i = 0; i < 10; ++i)
add2list(&phead, rand() % 100);

cout << "Elements of the list:" << endl;
print(phead);
deleteList(phead);
}

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

Теперь приведем пример реализации стека с использованием двусвязного списка.
Определим структуру, описывающую элемент списка:
template<class T>
struct TNode {
T value;
TNode* pnext;
TNode* pprev;
TNode(T val): pnext(0), pprev(0), value(val) {}
};
Это определение отличается от определения элемента простого односвязного списка только наличием указателя на предыдущий элемент списка (pprev).

Определение класса стека будет выглядеть следующим образом:
template<class T>
class Stack {
TNode<T>* plast;
long count;
public:
Stack(): plast(0), count(0) {}
~Stack();
void push(T val);
T pop();
T top()const;
long getCount()const {return count;}
};
plast указывает на последний элемент, помещенный в стек. count - количество элементов в стеке.
Функция push() помещает новый элемент в стек, функция pop() извлекает элемент из стека, а функция top() возвращает значение верхнего элемента, не извлекая его.

Реализация функций для работы со стеком:
template<class T>
Stack<T>::~Stack() {
while(--count > 1) {
plast = plast->pprev;
delete plast->pnext;
}
if(count == 1)
delete plast;
}
template<class T>
void Stack<T>::push(T val) {
TNode<T>* p = 0;
if(count > 0) {
p = plast;
plast = plast->pnext;
}
plast = new TNode<T>(val);
plast->pprev = p;
++count;
}
template<class T>
T Stack<T>::pop() {
if(count > 0) {
T val = plast->value;
if(count > 1) {
plast = plast->pprev;
delete plast->pnext;
}
else {
delete plast;
}
--count;
return val;
}
return -1;
}
template<class T>
T Stack<T>::top()const {
if(count > 0)
return plast->val;
return -1;
}
Протестируем функции push() и pop():
int main() {
Stack<int> stack;
for(int i = 0; i < 10; ++i)
stack.push(i);

cout << "Elements of the stack:" << endl;
for(int i = 0; stack.getCount() > 0; ++i) {
cout << stack.pop() << endl;
}
}


На главную

Rambler's Top100
Хостинг от uCoz