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

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

21.1. Паняцце пра структуры даных

У інфарматыцы структура даных — праграмная адзінка, якая дазваляе захоўваць і апрацоўваць даныя, а таксама забяспечвае іх эфектыўнае выкарыстанне. Даныя пры гэтым павінны быць аднатыпнымі або лагічна звязанымі.

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

Пры распрацоўцы праграмнага забеспячэння складанасць рэалізацыі і якасць работы праграм істотна залежаць не толькі ад выбару алгарытму, але і ад правільнага выбару структур даных. Адны і тыя ж даныя можна захаваць у структурах, якія патрабуюць рознага аб’ёму памяці, а алгарытмы работы з рознымі структурамі даных могуць мець розную эфектыўнасць. Структура даных, якая найбольш падыходзіць для рашэння пэўнай задачы, дазваляе выконваць вялікую колькасць розных аперацый, выкарыстоўваючы як мага меншы аб’ём рэсурсаў.

Ніводная прафесійная праграма сёння не пішацца без выкарыстання структур даных, таму шмат якія з іх змяшчаюцца ў стандартных бібліятэках сучасных моў праграміравання (напрыклад, STL для С++).

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

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

Далей будуць разгледжаны некаторыя лінейныя структуры даных.

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

Масіў (вектар у C++) — самая простая і шырока выкарыстоўваемая структура даных.
Запіс (структура ў С++) — сукупнасць элементаў даных рознага тыпу. Змяшчае пастаянную колькасць элементаў, якія называюць палямі.
Звязны спіс (Linked List) уяўляе сабой набор звязаных вузлоў, кожны з якіх захоўвае ўласна даныя і спасылку на наступны вузел. У рэальным жыцці звязны спіс можна ўявіць у выглядзе цягніка, кожны вагон якога можа змяшчаюць некаторы груз ці пасажыраў і пры гэтым можа быць звязаны з іншым вагонам.
Граф — сукупнасць вяршынь (вузлоў) і сувязей паміж імі (кантаў). У рэальным жыцці па такім прынцыпе пабудаваны сацыяльныя сеткі: вузлы — гэта людзі, а канты — іх адносіны.
Мноства — сукупнасць даных, значэнні якіх не паўтараюцца, рэалізацыя матэматычнага аб’екта мноства, за выключэннем таго, што мноства ў праграміраванні канечная.

Прыклад 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. Асноўныя аперацыі над спісам:

Ініцыялізацыя спіса.
Дабаўленне элемента ў спіс.
Выдаленне элемента са спіса.
Пошук зададзенага элемента x.
Прагляд элементаў спіса..

Прыклад 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++;

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. Алгарытм рашэння задачы.

Увод зыходных даных.
Праверку паслядоўнасці дужак, якая складаецца з дужак рознага тыпу, зручна выканаць пры дапамозе структуры стэк.

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 чорных і белых картак, складзеных у стос. Карткі раскладваюцца на стол у адну лінію наступным чынам: першая кладзецца на стол, другая — пад ніз стоса, трэцяя — на стол, чацвёртая — пад ніз стоса і г. д., пакуль усе карткі не будуць выкладзены на стол. Якім павінна быць зыходнае размяшчэнне картак у стосе, каб раскладзеныя на стале карткі чаргаваліся па колеры: белая, чорная, белая, чорная і г. д.? Падказка: выкарыстоўвайце чаргу.

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

Оглавление

21.1. Паняцце пра структуры даных

21.2. Спіс

21.3. Стэк

21.4. Очередь

Пытання да параграфу

Практыкаванні