Печатать книгуПечатать книгу

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

Сайт: Профильное обучение
Курс: Информатика. 10 класс (Повышенный уровень)
Книга: § 21. Структуры данных
Напечатано:: Гость
Дата: Воскресенье, 22 Декабрь 2024, 08:14

Оглавление

21.1. Понятие о структурах данных

В информатике структура данных —  программная единица, позволяющая хранить и обрабатывать данные, а также обеспечивающая их эффективное использование. Данные при этом должны быть однотипными или логически связанными.

Различные виды структур данных подходят для различных задач; некоторые из них имеют узкую специализацию, другие являются универсальными (пример 21.1).

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

Ни одна профессиональная программа сегодня не пишется без использования структур данных, поэтому многие из них содержатся в стандартных библиотеках современных языков программирования (например, STL для С++).

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

Структуры данных классифицируют по разным признакам. В примере 21.2 приведена классификация структур данных по организации взаимосвязей между элементами.

Далее будут рассмотрены некоторые линейные структуры данных.

Пример 21.1. Примеры некоторых структур данных:

1. Массив (вектор в C++) — самая простая и широко используемая структура данных.

2. Запись (структура в С++) — совокупность элементов данных разного типа. Содержит постоянное количество элементов, которые называют полями.

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

4. Граф — совокупность вершин (узлов) и связей между ними (ребер). В реальной жизни по такому принципу устроены социальные сети: узлы — это люди, а ребра — их отношения.

5. Множество — совокупность данных, значения которых не повторяются,  реализация математического объекта множество, за исключением того, что множество в программировании конечно.

Пример 21.2. Классификация структур данных.

•        Линейные:

    • массив;
    • список;
    • связанный список;
    • стек;
    • очередь;
    • хэш-таблица.

•        Иерархические:

    • двоичные деревья;
    • n-арные деревья;
    • иерархический список.

•        Сетевые:

    • неориентированный граф;
    • ориентированный граф.

•        Табличные:

    • таблица реляционной базы данных;
    • двумерный массив.

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.

21.3. Стек

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

Стек организован по принципу LIFO (англ. last in — first out, «последним пришел — первым ушел»).

Для стека определены операции добавления элемента и удаления элемента (пример 21.10). По своей организации стек является линейным списком, добавление и удаление элементов в который допускается только в начало списка.

В STL для работы со стеком определен тип данных stack, для чего подключается одноименная библиотека. Описание стека:

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

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

Пример 21.12. Правильная скобочная последовательность — последовательность, состоящая из символов — «скобок», в которой каждой открывающейся скобке соответствует закрывающаяся скобка такого же типа, что и открывающаяся скобка. Проверить, является ли заданная скобочная последовательность правильной.

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

I. Исходные данные: переменная s — строка, содержащая скобочную последовательность.

II. Результат: ответ «да» или «нет».

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

1. Ввод исходных данных. 
2. Проверку скобочной последовательности, состоящей из скобок различного типа, удобно выполнить при помощи структуры стек. Будем просматривать строку слева направо.

2.1. Если текущий символ — открывающаяся скобка, то этот символ заносится в стек. 
2.2. Если текущий символ — закрывающаяся скобка, то проверяем, что находится в вершине стека. 
2.2.1. Если в вершине стека лежит соответствующая открывающаяся скобка, то очередная скобка не добавляется, а имеющаяся в вершине удаляется. 
2.2.2. Если в вершине скобка другого типа, то работа программы прерывается и выдается ответ «нет». 
2.2.3. Если стек пуст, то работа программы прерывается и выдается ответ «нет». 
2.3. Если в конце работы программы стек оказывается пустым, то скобочная последовательность правильная, иначе — нет.

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

IV. Описание переменных: s – string, st –  stack<char>.

Принцип работы стека часто сравнивают со стопкой тарелок: чтобы взять тарелку из середины стопки, нужно снять верхние. Стек также можно сравнить с железнодорожным путём: вагон, который попал туда последним, заберут первым.

Пример 21.10. Добавление и удаление элемента в вершине стека:

Пример 21.11. Операции для типа данных stack.

Функция

Действие

top

Доступ к вершине стека

empty

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

size

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

push

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

pop

Удаляет верхний элемент

Пример 21.12.

Правильные скобочные последовательности: [([])((([[[]]])))]{()}, ()((()))[[]]. Неправильные скобочные последовательности: [[)) (несоответствие типа закрывающихся скобок типу открывающихся), }{ (закрывающая скобка стоит раньше открывающейся), [[{{}}] (не каждой открывающейся скобке соответствует закрывающаяся).

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

#include <iostream>

#include <string>

#include <stack>

 

using namespace std;

using namespace std::__cxx11;

 

int main()

{

  string s;

  cout << "s = " ;

  cin >> s;

  string otkr = "([{<";

  string zakr = ")]}>";

  int n = s.length();

  stack <char> st;

  bool f = true;

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

    if (otkr.find(s[i]) != -1)

      st.push(s[i]);

    if (zakr.find(s[i]) != -1){

      if (st.empty()){

        f = false;

        break;

      }

      if (zakr.find(s[i]) ==

          otkr.find(st.top()))

        st.pop();

      else{

        f = false;

        break;

      }

    }

  }

  if (st.empty() && f)

    cout << "da";

  else

    cout << "net";

  return 0;

}

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

VII. Анализ результатов. Рассмотрим пример для правильной скобочной последовательности [([])(([]))]. В первой строке — текущий символ, во второй — состояние стека.

[

(

[

]

)

(

(

[

]

)

)

]

[

[(

[([

[(

[

[(

[((

[(([

[((

[(

[

 

21.4. Очередь

Очередь — динамическая линейная структура данных, хранящая последовательность элементов, в которой добавление новых элементов происходит в конец очереди (хвост, tail), а удаление — из начала очереди (головы, head).

Очередь организована по принципу FIFO (англ. first in — first out, «первым пришел — первым ушел»).

Для очереди определены операции добавления элемента и удаления элемента (пример 21.13). По своей организации очередь является линейным списком, добавление в который допускается только в конец списка, а удаление только из начала.

В STL для работы со стеком определен тип данных queue, для работы с которым подключается одноименная библиотека. Описание стека:

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

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

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

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

I. Исходные данные: переменная s — строка, содержащая прописные и строчные буквы.

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

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

1. Ввод исходных данных.
2. Будем просматривать строку слева направо.

2.1. В очередь будем заносить буквы одного регистра. 
2.2. Если появляется символ в другом регистре, то достаем букву из очереди и выводим пару. 
2.2.1. Для проверки того, что две буквы относятся к одному регистру, создадим логическую функцию check. Буква x является прописной, если для нее выполняется условие x >= 'A' && x <= 'Z'. Для строчной буквы должно выполняться условие: x >= 'a' && x <= 'z'. 
2.2.2. Для вывода букв в нужном порядке создадим функцию vyvod.

3. Если в конце очередь не пуста, то в ней остались символы, которым не хватило пары. Для того чтобы вывести все символы из очереди, будем после вывода удалять символ, пока очередь не станет пустой.

IV. Описание переменных: s – string, q –  queue<char>.

Часто используется структура дек — (англ. deque — double ended queue, «двухсторонняя очередь»). Дек можно определять как двухстороннюю очередь, или как стек, имеющий два конца. Это означает, что данный вид списка позволяет добавлять элементы в начало и в конец, и то же самое справедливо для операции извлечения. Эта структура данных одновременно работает по двум способам организации данных: FIFO и LIFO (пример 21.16).

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

Пример 21.13. Добавление и удаление элемента в очереди:

Пример 21.14. Операции для типа данных queue.

Функция

Действие

front

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

back

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

empty

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

size

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

push

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

pop

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

Пример 21.15.

Если на вход подана строка   ZHJKqwertASDyuiopQWERTYUIOPasdf,   то должны получиться следующие пары:   Zq Hw Je Kr At Sy Du Qi Wo Ep Ra Ts Yd Uf.   Буквы I O P останутся без пары.

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

#include <iostream>

#include <string>

#include <queue>

 

using namespace std;

 

bool check(char x, char y)

{

  bool u1 =  x >= 'A' && x <= 'Z';

  bool u2 =  y >= 'A' && y <= 'Z';

  bool u3 =  x >= 'a' && x <= 'z';

  bool u4 =  y >= 'a' && y <= 'z';

  return (u1 && u4 || u2 && u3);

}

 

void vyvod (char x, char y)

{

  if (x < y)

    cout << x << y << " ";

  else

    cout << y << x << " ";

}

 

int main()

{

  string s;

  cout << "s = " ;

  cin >> s;

  int n = s.length();

  queue <char> q;

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

    if (q.empty())

      q.push(s[i]);

     else

       if (check(s[i], q.front())){

          vyvod(s[i], q.front());

          q.pop();

       }

       else

         q.push(s[i]);

  }

  cout << endl;

  if (q.empty())

    cout << "u vseh ect para";

  else{

    cout << "bez pary:" << endl;

    while (!q.empty()){

      cout << q.front();

      q.pop();

    }

  }

  return 0;

}

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

VII. Анализ результатов. Рассмотрим пример для строки wwerTyGJLqTT. В первой строке — текущий символ, во второй — состояние очереди.

w

w

e

r

T

y

G

J

L

q

T

T

w

ww

eww

reww

rew

yrew

yre

yr

y

qy

q

 

Пример 21.16. Добавление и удаление элемента в деке:

В STL для работы с деком определен тип данных deque, для работы с которым подключается одноименная библиотека. Функции для работы с деком можно посмотреть в см. Приложение к главе 1.1.

Вопросы к параграфу

1. Что понимают под структурой данных?

2. Как добавить элемент в список?

3. Как удалить элемент из списка?

4. Как устроен стек?

5. Какие операции определены для очереди?

Упражнения

    

1. В файле хранится список фамилий. Написать программу, которая определит, есть ли в списке одинаковые фамилии, и, если есть, удалит их. Преобразованный список вывести в файл.

2. Дано целое число x и список, состоящий из целых чисел. Удалить из списка все элементы со значением x.

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

4. По заданному текстовому файлу получите новый текстовый файл, в котором слова из первого файла расположены в обратном порядке. Используйте структуру данных стек.

5. В файле хранятся целые числа. Разместить числа в два стека. В первый стек — положительные числа, а во второй — отрицательные. Если количество чисел в стеках одинаково, то в итоговый файл вывести попарные произведения чисел: один множитель из первого стека, другой — из второго, иначе в итоговый файл записать значения вершины каждого стека.

6. В стеке хранятся целые числа. Найдите минимальное число в стеке.

7. В очереди хранятся целые числа. Найдите максимальное число в очереди.

8. Дана величина a строкового типа из четного количества символов. Получить и вывести величину b, состоящую из символов первой половины величины a, записанных в обратном порядке, после которых идут символы второй половины величины a, также записанные в обратном порядке. Например, при а = «привет» b должно быть равно «ирптев».

9. Имеется n черных и белых карточек, сложенных в стопку. Карточки раскладываются на стол в одну линию следующим образом: первая кладется на стол, вторая — под низ стопки, третья — на стол, четвертая — под низ стопки и т. д., пока все карточки не будут выложены на стол. Каким должно быть исходное расположение карточек в стопке, чтобы разложенные на столе карточки чередовались по цвету: белая, черная, белая, черная и т. д.? Подсказка: используйте очередь.