§ 21. Структуры даных
21.2. Спіс
Спіс — дынамічная лінейная структура даных. Яна захоўвае канечную паслядоўнасць элементаў, парадак якіх вызначаецца з дапамогай спасылак. Спіс з’яўляецца дынамічнай лінейнай структурай даных, у якой кожны элемент спасылаецца або толькі на наступны – аднанакіраваны лінейны спіс (прыклад 21.3), або на папярэдні і наступны за ім — двунакіраваны лінейны спіс (прыклад 21.4). Спіс уяўляе сабой паслядоўнасць звязаных структур. Кожная структура змяшчае спасылку, якая звязвае яе з іншай структурай, што ўваходзіць у спіс. Звычайна структура складаецца з дзвюх сэнсавых частак — інфармацыйнай і дадатковай. Інфармацыйная частка змяшчае даныя, у дадатковай знаходзяцца паказальнікі на наступную ці папярэднюю структуру спіса. Парадак элементаў вызначаецца спасылкай на першы элемент. Такая арганізацыя структуры даных дазваляе паслядоўна перамяшчацца па спасылках ад аднаго элемента спіса да іншага. Асноўныя аперацыі, якія выконваюцца над спісам, пералічаны ў прыкладзе 21.5. Дабаўленне ў спіс элемента, наступнага за зададзеным, складаецца з наступных этапаў:
Выдаленне са спіса элемента, наступнага за зададзеным, уключае у сябе наступныя этапы:
Пошук элемента x у лінейным спісе ажыццяўляецца паслядоўным праглядам элементаў. Ён заканчваецца або пры выяўленні шуканага элемента, або пры дасягненні канца спіса. Пошук у спісе аналагічны пошуку ў лінейным масіве, толькі зварот да элементаў ажыццяўляецца не па індэксе, а па паказальніку. Калі выкарыстаць структуру даных list, што ўваходзіць у STL, то ўсе моманты, звязаныя з захоўваннем элементаў спіса, а таксама з вылучэннем і вызваленнем памяці, будуць рашацца самой структурай даных. Для карыстальніка аперацыі даступныя ў выглядзе функцый, уласцівых дадзенаму класу. Для работы са спісам неабходна падключыць бібліятэку <list>. Апісанне спіса: list <тып даных> імя пераменнай; У бібліятэцы list рэалізаваны двунакіраваны спіс, які з’яўляецца больш агульным, чым аднанакіраваны, і падтрымлівае большую колькасць аперацый. Калі неабходна работа з аднанакіраваным спісам, можна выкарыстоўваць тып даных forward_list з падключэннем аднайменнай бібліятэкі. У прыкладзе 21.8 пералічаны некаторыя аперацыі, даступныя для работы са спісам. З іншымі можна азнаёміцца ў Дадатку да главы 1.1. Шмат якія функцыі аналагічныя функцыям, вызначаным для тыпу даных vector. Прыклад 21.9. У файле захоўваецца спіс прозвішчаў. Напісаць праграму, якая адсартуе прозвішчы ў спісе, знойдзе нумар чалавека па прозвішчы Каралёў, уставіць перад ім прозвішча Іваноў і выдаліць прозвішча пасля Каралёва (Каралёў не апошні ў спісе). Ператвораны спіс вывесці ў файл. Этапы выканання задання I. Зыходныя даныя: пераменныя n — колькасць прозвішчаў у спісе, spis — спіс. II. Вынік: нумар Каралёва і пераўтвораны спіс. III.Алгарытм рашэння задачы. 1. Увод зыходных даных. Будзем счытваць радок з файла і дабаўляць яго ў канец спіса, выкарыстоўваючы функцыю push_back. 2.1. Для сартавання спіса выкарыстоўваем функцыю sort. Паколькі спіс трэба сартаваць па ўзрастанні, кампаратар не спатрэбіцца. 3. Вывад выніку. IV. Апісанне пераменных: n, n1, – int, spis – list<string>. |
Спісы адрозніваюцца ад масіваў тым, што доступ да іх элементаў ажыццяўляецца паслядоўна, у той час як масівы — структура даных свабоднага доступу (дае магчымасць у любы момант часу звярнуцца да любога элемента па яго індэксе). Элементы звязанага спіса (у адрозненне ад элементаў масіву) не абавязаны размяшчацца ў памяці адзін за адным. Складныя спісы часам называюць самаспасылачнымі (self-referent) структурамі. Хоць спасылка элемента звычайна паказвае на іншы элемент, магчымы і спасылкі на сябе (прама ці ўскосна, праз іншыя элементы), таму складныя спісы могуць уяўляць сабой цыклічныя (cyclic) структуры. Прыклад 21.5. Асноўныя аперацыі над спісам:
Прыклад 21.6. Дабаўленне элемента ў аднанакіраваны спіс: Прыклад 21.7. Выдаленне элемента з аднанакіраванага спіса: Прыклад 21.8. Некаторыя аперацыі для тыпу даных list.
Спісы аптымізаваны для выканання аперацый па дабаўленні і выдаленні элементаў. Калі мы ведаем месцазнаходжанне элемента, то для ўстаўкі ці выдалення элемента дастаткова змяніць значэнні паказальнікаў. Самі элементы пры гэтым не перамяшчаюцца (у адрозненне ад устаўкі і выдалення элементаў у масіве). Для пошуку элемента x у спісе спатрэбіцца (у горшым выпадку) каля n аперацый параўнання. V. Праграма:
VI. Тэсціраванне. VII. Аналіз вынікаў. У выніковым спісе Каралёў мае нумар 40, паколькі перад ім уставілі Іванова. Да ўстаўкі нумар быў 39. |