§ 21. Структуры данных

21.2. Список

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

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

Список представляет собой последовательность связанных структур. Каждая структура содержит ссылку, связывающую ее с другой структурой, входящей в список. Обычно структура состоит из двух смысловых частей — информационной и дополнительной. Информационная часть содержит данные, в дополнительной находятся указатели на последующую или предыдущую структуру списка. Порядок элементов определяется ссылкой на первый элемент. Такая организация структуры данных позволяет последовательно перемещаться по ссылкам от одного элемента списка к другому.

Основные операции, производимые над списком, перечислены в примере 21.5.

Добавление в список элемента, следующего за заданным, включает в себя следующие этапы:

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

(Рассмотрите пример 21.6.)

Удаление из списка элемента, следующего за заданным, включает в себя следующие этапы:

  • установка указателя предыдущего элемента на элемент, следующий за удаляемым;
  • освобождение памяти удаляемого элемента.

(Рассмотрите пример 21.7.)

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

Если воспользоваться структурой данных list, входящей в STL, то все моменты, связанные с хранением элементов списка, а также с выделением и освобождением памяти, будут решаться самой структурой данных. Для пользователя операции доступны в виде функций, присущих данному классу.

Для работы со списком необходимо подключить библиотеку <list>. Описание списка:

list <тип данных> имя переменной;

В библиотеке list реализован двунаправленный список, который является более общим, чем однонаправленный, и поддерживает большее количество операций. Если необходима работа с однонаправленным списком, можно использовать тип данных forward_list с подключением одноименной библиотеки.

В примере 21.8 перечислены некоторые операции, доступные для работы со списком. С другими можно ознакомиться в Приложение к главе 1.1. Многие функции аналогичны функциям, определенным для типа данных vector.

Пример 21.9. В файле хранится список фамилий. Написать программу, которая отсортирует фамилии в списке, найдет номер человека по фамилии Королев, вставит перед ним фамилию Иванов и удалит фамилию после Королева (Королев не последний в списке). Преобразованный список вывести в файл.

Этапы выполнения задания

I. Исходные данные: переменные n — количество фамилий в списке, spis — список.

II. Результат: номер Королева и преобразованный список.

III. Алгоритм решения задачи.

1. Ввод исходных данных. Будем считывать строку из файла и добавлять ее в конец списка, используя функцию push_back.
2. Для решения задачи будем использовать структуру данных list.

2.1. Для сортировки списка используем функцию sort. Поскольку список нужно сортировать по возрастанию, компаратор не потребуется. 
2.2. Для поиска n1 — номера Королева воспользуемся линейным поиском. Просмотр элементов списка осуществляется с помощью итератора. 
2.3. Для вставки фамилии будем использовать функцию insert. 
2.4. Для удаления фамилии будем использовать функцию erase.

3. Вывод результата.

IV. Описание переменных: n, n1, – int, spis –  list<string>.

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

Пример 21.3. Однонаправленный линейный список:

Пример 21.4. Двунаправленный линейный список:

Элементы связанного списка (в отличие от элементов массива) не обязаны располагаться в памяти друг за другом.

Связные списки иногда называют самоссылочными (self-referent) структурами. Хотя ссылка элемента обычно указывает на другой элемент, возможны и ссылки на себя (прямо или косвенно, через другие элементы), поэтому связные списки могут представлять собой циклические (cyclic) структуры.

Пример 21.5. Основные операции над списком:

1. Инициализация списка. 
2. Добавление элемента в список. 
3. Удаление элемента из списка. 
4. Поиск заданного элемента x. 
5. Просмотр элементов списка.

Пример 21.6. Добавление элемента в однонаправленный список:

Пример 21.7. Удаление элемента из однонаправленного списка:

Пример 21.8. Некоторые операции для типа данных list.

Функция

Действие

front

Доступ к первому элементу 

>back

Доступ к последнему элементу 

push_front

Вставляет элемент в начало

pop_front

Удаляет первый элемент 

push_back

Вставляет элемент в конец

pop_back

Удаляет последний элемент 

empty

Проверяет отсутствие элементов

size

Возвращает количество элементов

clear

Очищает список 

erase

Удаляет элементы 

insert

Вставляет элементы  

reverse

Изменяет порядок элементов на обратный

sort

Сортирует элементы

Списки оптимизированы для выполнения операций по добавлению и удалению элементов. Если мы знаем месторасположение элемента, то для вставки или удаления элемента достаточно изменить значения указателей. Сами элементы при этом не перемещаются (в отличие от вставки и удаления элементов в массиве). Для поиска элемента x в списке понадобится (в худшем случае) порядка n операций сравнения.

Пример 21.9.

V. Программа:

#include <iostream>

#include <fstream>

#include <list>

#include <windows.h>

 

using namespace std;

 

int main()

{

  SetConsoleCP(1251);

  SetConsoleOutputCP(1251);

  ifstream fin("input.txt");

  ofstream fout("output.txt");

  int n;

  fin >> n;

  fin.ignore();

  list <string> spis;

  for (int i = 0; i < n; i++){

    string t;

    fin >> t;

    spis.push_back(t);

  }

  spis.sort();

  list <string>::iterator fm = spis.end();

  int n1 = 0;

  for (list <string>::iterator

       i = spis.begin();

       i != spis.end(); i++){

     n1++;

     if (*i == "Королев"){

        fm = i;

        break;

     }

  }

  if (fm != spis.end()){

    spis.insert(fm, "Иванов");

    fm++;

    fm++;

    spis.erase(fm);

    cout << n1 << endl;

    for (list <string>::iterator

         i = spis.begin();

         i != spis.end(); i++)

      fout << *i << endl;

  }

  else

    cout << "нет Королева" << endl;

  return 0;

}

 VI. Тестирование.

     

VII. Анализ результатов. В итоговом списке Королев имеет номер 40, поскольку перед ним вставили Иванова. До вставки номер был 39.