Сьпіс
Зьвесткі зь Вікіпэдыі — вольнай энцыкляпэдыі.
Сьпіс – (у праграмаваньні) структура дадзеных, якая зьмяшчае лінейна ўпарадкаванае мноства элемэнтаў. Кожны элемэнт мае спасылку на дадзеныя і адну ці дзьве спасылкі на наступны і папярэдні элемэнты. У сьпіс можна дадаваць/выдаляць элемэнты ў любым месцы за пастаянны час, але немагчымы адвольны доступ, толькі пасьлядоўны.
Зьмест |
[рэдагаваць] Варыянты
[рэдагаваць] Просты адназьвязаны сьпіс
Адназьвязаны сьпіс - найпрасьцейшы варыянт. У мове Lisp, дзе сьпісы - асноўная структура дадзеных, такі сьпіс ўяўляе сабой пару: галава (спасылка на дадзеныя: head) і хвост (працяг сьпісу: tail, або іншымі словамі, спасылка на наступны элемэнт: next), які можа быць пустым (роўны null). Гэта выглядае ў кропачнай натацыі:
( галава . хвост )
Адназьвязны сьпіс з трыма элемэнтамі A, null, 21 можа быць запісаны: (A . (null . (21 . null))) ці ў скарочаным выглядзе: (A null 21). Графічна гэта паказана на наступным малюнку (перакрэсьлены квадрат азначае пустую спасылку - null):
Каб указаць адназьвязны сьпіс, напрыклад, перадаць у якасьці парамэтра ў працэдуру, дастаткова пазначыць адрас яго першага элемэнта. Усе іншыя элемэнты можна атрымаць паступова, калі рухацца па спасылках, пачынаючы ад першага.
[рэдагаваць] Двузьвязаны сьпіс
Двузьвязаны сьпіс - больш складаны варыянт адназьвязанага сьпісу. Кожны элемэнт мае дзьве спасылкі - ня толькі на наступны элемэнт (next), але і на папярэдні (prev). Той жа самы сьпіс (A null 21):
У такім сьпісе магчымы рух у абодвух напрамках: ад першага да апошняга элемэнта і наадварот.
[рэдагаваць] Цыклічны сьпіс
У цыклічным сьпісе апошні элемэнт мае спасылку не на null, а на першы, ствараючы цыкль, колца. Цыклічным можа быць і двузьвязаны сьпіс, у такім разе дадаткова і prev-спасылка першага элемэнта ўказвае на апошні элемэнт. Каб указаць адназьвязны цыклічны сьпіс пазначаюць адрас апошняга элемэнта, таму што празь яго можна лёгка атрымаць першы, пры гэтым застаецца магчымасьць хутка дадаваць новыя элемэнты пасьля апошняга ці перад першым.
[рэдагаваць] Элемэнты-вартавыя
Часам сьпісы маюць спэцыяльныя дапаможныя элемэнты-вартавыя перад першым і/ці пасьля апошняга. Яны не зьмяшчаюць дадзеных, але прызначаны для спрашчэньня ці паскарэньня апрацоўкі сьпісу. Наяўнасьць такіх элемэнтаў гарантуе, што кожны элемэнт мае наступніка/папярэдніка, і што ў кожным сьпісе, нават пустым, ёсьць першы і апошні элемэнт.
[рэдагаваць] Параўнаньні
Сьпіс адрозьніваецца ад масіваў тым, што дазваляе дадаваць і выдаляць элемэнты (масівы, акрамя дынамічных - звычайна статычныя, колькасьць элемэнтаў у іх нязьменна), устаўляць новыя элемэнты паміж ужо існуючых бяз руханьня іншых элемэнтаў, але доступ да элемэнтаў сьпісу - толькі пасьлядоўны, а не па індэксу, як у масіве.
TODO
