§ 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.