На этом шаге мы приведем общие сведения о списках.

    Список - это совокупность объектов, называемых элементами списка, в которой каждый объект содержит информацию о местоположении связанного с ним объекта [1, с. 214].

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

    Каждый элемент списка представим структурой языка C++ с двумя полями:

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

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

    С учетом сказанного, мы можем описать звено списка так:

    struct node
    {
      int elem; //Информационный элемент звена списка 
      node *sled; // Указатель на следующее звено списка 
    };

    Чтобы иметь возможность оперировать со списком как с единым объектом, введем в употребление статическую ссылочную переменную phead, которая указывает на первое звено списка и описывается следующим образом:

    struct node *phead;

    На следующем шаге мы рассмотрим однонаправленные списки без заглавного звена.

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