ОБЪЕКТНО-ОРИЕНТИРОВАННОЕ ПРОГРАММИРОВАНИЕ В C++ (4-Е ИЗДАНИЕ) (часть 10) онлайн

Цепочка указателей

Связный список представляет собой более гибкую систему для хранения данных, в которой вовсе не используются массивы. Вместо них мы получаем для каждого элемента память, используя операцию new, а затем соединяем (или связываем) элементы данных между собой, используя указатели. Элементы списка не обяза- ны храниться в смежных участках памяти, как это происходит с массивами; они могут быть разбросаны по всему пространству памяти.

В нашем примере связный список является объектом класса linkList. Элемен- ты списка представлены структурой link. Каждый элемент содержит целое чис- ло, представляющее собой данные, и указатель на следующий элемент списка. Указатель на сам список хранится в начале списка. Структура списка показана на рис. 10.15.

Рис. 10.15. Связный список

Рассмотрим листинг программы LINKLIST:

// linklist.cpp

// список

#include <iostream>

using namespace std;

///////////////////////////////////////////////////////////

 

struct link   // один элемент списка

{

  int data;   // некоторые данные

  link* next; // указатель на следующую структуру

};

///////////////////////////////////////////////////////////

class linklist // список

{

  private:

    link* first;

  public:

    linklist ( )            // конструктор без параметров

      { first = NULL; }     // первого элемента пока нет

    void additem ( int d ); // добавление элемента

    void display ( );       // показ данных

};

///////////////////////////////////////////////////////////

void linklist::additem ( int d ) // добавление элемента

{

  link* newlink = new link;      // выделяем память

  newlink->data = d;             // запоминаем данные

  newlink->next = first;         // запоминаем значение first

  first = newlink;               // first теперь указывает на новый элемент

}

///////////////////////////////////////////////////////////

void linklist::display ( )

{

  link* current = first;           // начинаем с первого элемента

  while( current )                 // пока есть данные

  {

    cout << current->data << endl; // печатаем данные

    current = current->next;       // двигаемся к следующему элементу

  }

}

///////////////////////////////////////////////////////////

int main ( )

{

  linklist li;       // создаем переменную-список

 

  li.additem ( 25 ); // добавляем туда несколько чисел

  li.additem ( 36 );

  li.additem ( 49 );

  li.additem ( 64 );

 

  li.display ( );    // показываем список

 

  return 0;

}

 

 Класс linklist имеет только одно поле: указатель на начало списка. При созда- нии списка конструктор инициализирует этот указатель, именованный как first, значением NULL, которое аналогично значению 0. Это значение является призна- ком того, что указатель указывает на адрес, который точно не может содержать полезной информации. В нашей программе элемент, указатель которого на сле- дующий элемент имеет значение NULL, является конечным элементом списка.

 

35