На этом шаге мы рассмотрим алгоритм удаления списка из памяти.

    Остановимся теперь на удалении однонаправленного линейного списка из динамической памяти.

    Алгоритм удаления можно сформулировать следующим образом:

• заводим два указателя q и q1, один из которых будет "опережать" другой (пусть q1 опережает q);
• начальное значение q - это адрес расположения в памяти заглавного звена, а q1 - адрес расположения первого элемента списка;
• организуем цикл, пока q1!=NULL, то есть пока q1 "не доберется" до указателя последнего элемента списка;
• в теле цикла переместим указатели на следующую пару элементов списка (то есть для первого случая q будет содержать адрес первого звена списка, а q1 - второго), и удалим элемент, который адресуется значением q;
• после выполнения цикла у нас останется только заглавное звено, адресуемое указателем phead. Его также нужно удалить.

    Приведем текст функции, реализующей указанный алгоритм.

void OCHISTKA (node **phead)
//Удаление однонаправленного списка из памяти. 
// *phead - указатель на заглавное звено списка.
{
  struct node *q,*q1; // Рабочие указатели.
  q = *phead;
  q1 = (*q).sled; // Указатель q1 "опережает" указатель q.
  while (q1!=NULL)
  { q = q1; q1 = (*q1).sled; delete q;}
  delete *phead; //Удаление заглавного звена.
}

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

    Соберем рассмотренные функции в объектно-ориентированную программу.

#include<iostream.h>
class Spisok
{
  private:
    struct node
      {
        int elem; 
        node *sled;
      } *phead; //Указатель на начало списка.
  public: 
    Spisok() {phead = new (node); (*phead).sled=NULL;} //Конструктор.
    ~Spisok() { delete phead; } //Деструктор.
    void POSTROENIE (); 
    void VYVOD (); 
    void OCHISTKA ();
}; 

void main ()
{
  Spisok A;

  A.POSTROENIE ();
  A.VYVOD ();
  A.OCHISTKA ();
} 

void Spisok::POSTROENIE ()
//Построение однонаправленного списка с заглавным звеном.
// phead - указатель на заглавное звено списка. 
{
  node *t;
  int el;
  t = phead;
  cout<< "Вводите элементы списка: ";
  cin>>el;
  while (el!=0)
  { 
    (*t).sled = new (node); 
    t = (*t).sled; (*t).elem = el; (*t).sled = NULL; 
    cin>>el;
  }
} 

void Spisok::VYVOD ()
//Вывод содержимого однонаправленного линейного списка
//с заглавным звеном.
// phead - указатель на заглавное звено списка.
{
  node *t;
  t = (*phead).sled; 
  cout<<"Список: ";
  while (t!=NULL)
  { 
    cout<<(*t).elem<<" "; 
    t = (*t).sled;
  }
  cout<<endl;
} 

void Spisok::OCHISTKA ()
//Удаление однонаправленного списка из памяти.
// phead - указатель на заглавное звено списка.
{
  node *q,*q1;// Рабочие указатели.

  q = phead;
  q1 = (*q).sled; // Указатель q1 "опережает" указатель q.
  while (q1!=NULL)
  { q = q1; q1 = (*q1).sled; delete q;}
}

    Со следующего шага мы начнем рассматривать основные операции над списками с заглавным звеном.

Предыдущий шаг Содержание Следующий шаг