Программирование на языке высокого уровня

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

Каждый элемент должен хранить ссылки на последующий и предыдущий элемент. Для того, чтобы отделить хранимые объекты от способа хранения вводится вспомогательный объект УЗЕЛ (Node).

Простой односвязный список:
Простой двухсвязный список:
Кольцевой двухсвязный список:

Узел

- объекты, который содержит ссылки на последующий и предыдущий элементы, а также значение данного элемента списка.

Списки в стандартной библиотеке C++ являются двусвязными. Поэтому список поддерживает вставку в начало (push_front) и в конец (push_back). Кроме того новые элементы можно вставить в любое место списка (insert). При этом не потребуется переразмещение всей структуры данных. Полный список функций вектора см. Приложение 5.

3.4.2. Итераторы

Для обобщения работы с элементами различных контейнеров вводят понятие, общее для всех контейнеров - итератор. Итераторы являются общей концепцией обработки последовательности элементов, хранимых в любых контейнерах. Реализация итератора отличается для разных типов контейнеров, но работа с итератором, набор функций и операторов унифицирован.

Итератор - это объект, который представляет собой обобщение понятия указатель. Это обобщённый "указатель" на элемент, хранящийся в контейнере. Применение оператора * приведет к разыменованию и получению доступа к значению элемента. А использование операторов ++ и -- позволит получить указатель на следующий и предыдущий элемент, хранимый в контейнере. Все контейнеры должны предоставлять несколько ключевых функций-членов, которые позволяют программисту получить итераторы на первый и последний элемент контейнера, то есть найти "концы" последовательности элемента контейнера.

list<double> ls;
list<double>::iterator it;

it=ls.begin(); // итератор на первый элемент контейнера
it=ls.end();   // итератор на следующий после последнего элемент контейнера
it--;          // операторы «++» и «– –» получение указателя на следующий и предыдущий элемент
it++;          
(*it)=5;       // оператор * – разыменование и получение доступа к значению элемента
 
// последовательный перебор всех элементов списка через цикл for
for(it=x.begin(); it!=x.end(); it++)
{
    sum+=(*it); //доступ к элементам по итератору
}
// последовательный перебор всех элементов списка через цикл while
it=x.begin();
while(it!=x.end())
{
    sum+=*it;
    it++;
}

3.4.3. Пример работы со списком с использованием итераторов (пример 3.4)

Рассмотрим пример работы со списком с использванием итераторов.

/////////////////////////////////////////////////////////////////////////////
// Программирование на языке высокого уровня. Основы языка С++
// Пример 3.4. Пример работы с контейнером list
// 
// http://aco.ifmo.ru/el_books/programming
// Университет ИТМО
/////////////////////////////////////////////////////////////////////////////
#include <iostream>   // подключение библиотеки ввода-вывода
#include <list>       // подключение описания списка
#include <fstream>    // для работы с файлами
using namespace std;  // подключение стандартного пространства имен для использования библиотек

// прототипы функций 
void read_from_file(list<int>& data, const string& filename);
/////////////////////////////////////////////////////////////////////////////
// Функция чтения конейнера list из файла
// data - контейнер для заполнения
// filename - имя файла
void read_from_file(list<int>& data, const string& filename)
{
    ifstream ifile(filename); // создание потока ввода из файла по его имени

    data.clear(); // очистить контейнер 

    int value;
    // цикл будет выполняться до тех пор, пока не встретиться конец файла
    while(!ifile.eof())
    {
        ifile>>value;           // читаем число из файла
        data.push_back(value);  // записываем прочитанное число в конец контейнера
    }
}
///////////////////////////////////////////////////////////////////////////////
void main()
{
    list<int> x; // объявление контейнера
    list<int>::iterator it; // объявление итератора

    // пример работы с контейнером
    x.push_back(0); // вставка в конец
    x.push_back(1); // вставка в конец
    x.push_back(2); // вставка в конец
    // x = 0 1 2
    x.push_front(5); // вставка в начало 
    // x = 5 0 1 2
    it=x.begin(); 
    it++;    
    x.insert(it, 3); // вставка перед итератором it 
    // x = 5 3 0 1 2

    // вывод всех элементов контейнера
    for(it=x.begin(); it!=x.end(); it++)
    {
        cout<<*it<<" "; //доступ к элементам по итератору
    }
    cout<<endl<<endl;

    //  чтение элементов списка из файла
    read_from_file(x, "list_data.txt");
    // вывод всех элементов контейнера
    for(it=x.begin(); it!=x.end(); it++)
    {
        cout<<*it<<" "; //доступ к элементам по итератору
    }
    cout<<endl<<endl;

    // вычисление суммы всех значений контейнера
    int sum=0;
    it=x.begin();
    while(it!=x.end())
    {
        sum+=*it; 
        it++;
    }
    cout<<"sum="<<sum<<endl;
}
///////////////////////////////////////////////////////////////////////////////

4.4. Список list

3.4.1. Списки

3.4.2. Итераторы

3.4.3. Пример работы со списком с использованием итераторов (пример 3.4)