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

На главную

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

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

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

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

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

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

В качестве примера рассмотрим связный список, хранящий целые числа. Элементы списка сортируются по возрастанию в зависимости от величины числа, которое хранится в данном элементе.
Каждый элемент списка является экземпляром структуры, которая описывается следующим образом:

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

На главную

Хостинг от uCoz