Основы алгоритмизации и программирования

ОСНОВЫ 

АЛГОРИТМИЗАЦИИ 

И ПРОГРАММИРОВАНИЯ

В.Д. Колдаев

Под редакцией профессора Л.Г. Гагариной

Допущено Министерством образования и науки Российской Федерации

в качестве учебного пособия для студентов учреждений среднего

профессионального образования, обучающихся по группе

специальностей 09.00.00 «Информатика и вычислительная техника»

УЧЕБНОЕ ПОСОБИЕ

Москва 

ИД «ФОРУМ» — ИНФРА-М

201УДК  004(075.32) 
ББК 32.973-018я723 
 
К60

Колдаев В.Д.

К60  
Основы алгоритмизации и программирования : учеб. пособие / 

В.Д. Колдаев ; под ред. проф. Л.Г. Гагариной. — М. : ИД «ФОРУМ» : 
ИНФРА-М, 2019. — 414 с. — (Среднее профессиональное образование).

ISBN 978-5-8199-0733-7 (ИД «ФОРУМ») 
ISBN 978-5-16-013541-0 (ИНФРА-М, print) 
ISBN 978-5-16-103967-0 (ИНФРА-М, online)

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

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

УДК 004(075.32) 

ББК 32.973-018я723 

Р е ц е н з е н т ы:

В.В. Уздовский, доктор физико-математических наук, профессор 

Московского государственного института электронной техники (технического университета), кафедра общей физики; 

О.И. Лисов, доктор технических наук, профессор Московского госу
дарственного института электронной техники (технического университета), кафедра информатики и программного обеспечения вычислительных систем

ISBN 978-5-8199-0733-7 (ИД «ФОРУМ») 
ISBN 978-5-16-013541-0 (ИНФРА-М, print) 
ISBN 978-5-16-103967-0 (ИНФРА-М, online)

© Колдаев В.Д., 2015
© ИД «ФОРУМ», 2015

Ââåäåíèå

 ïîñëåäíèå ãîäû ïðîãðàììèðîâàíèå äëÿ ïåðñîíàëüíûõ êîì
ïüþòåðîâ âûëèëîñü â íåêîòîðóþ äèñöèïëèíó, âëàäåíèå êîòîðîé
ñòàëî îñíîâíûì è êëþ÷åâûì ìîìåíòîì, îïðåäåëÿþùèì óñïåõ
ìíîãèõ èíæåíåðíûõ ïðîåêòîâ, à ñàìà îíà ïðåâðàòèëàñü â îáúåêò
íàó÷íîãî èññëåäîâàíèÿ. Èç ðåìåñëà ïðîãðàììèðîâàíèå ïåðåøëî
â ðàçðÿä àêàäåìè÷åñêèõ íàóê. Êðóïíûå ñïåöèàëèñòû â îáëàñòè
ïðîãðàììèðîâàíèÿ ïîêàçàëè, ÷òî ïðîãðàììû ïîääàþòñÿ òî÷íîìó
àíàëèçó, îñíîâàííîìó íà ñòðîãèõ ìàòåìàòè÷åñêèõ ðàññóæäåíèÿõ.
Óáåäèòåëüíî ïðîäåìîíñòðèðîâàíî, ÷òî ìîæíî èçáåæàòü ìíîãèõ
îøèáîê, òðàäèöèîííûõ äëÿ ïðîãðàììèñòîâ, åñëè ïîñëåäíèå áóäóò îñìûñëåííî ïîëüçîâàòüñÿ ìåòîäàìè è ïðèåìàìè, êîòîðûå
ðàíüøå îíè ïðèìåíÿëè èíòóèòèâíî, ÷àñòî íå îñîçíàâàÿ èõ êàê
òàêîâûå. Ïðè ýòîì îñíîâíîå âíèìàíèå èìè îáû÷íî óäåëÿåòñÿ
ïîñòðîåíèþ è àíàëèçó ïðîãðàììû, à àíàëèçó è âûáîðó ïðåäñòàâëåíèÿ äàííûõ, êàê ïðàâèëî, óäåëÿåòñÿ ìåíüøåå, ÿâíî âòîðîñòåïåííîå, âíèìàíèå. Íà ñàìîì äåëå ñîâðåìåííàÿ ìåòîäîëîãèÿ
ïðîãðàììèðîâàíèÿ ïðåäïîëàãàåò, ÷òî îáà àñïåêòà ïðîãðàììèðîâàíèÿ — çàïèñü àëãîðèòìà íà ÿçûêå ïðîãðàììèðîâàíèÿ è âûáîð
ñòðóêòóð ïðåäñòàâëåíèÿ äàííûõ — çàñëóæèâàþò àáñîëþòíî îäèíàêîâîãî âíèìàíèÿ. Òåïåðü âñåì, êòî çàíÿò âîïðîñàìè ïðîãðàììèðîâàíèÿ äëÿ âû÷èñëèòåëüíîé òåõíèêè, ñòàëî ÿñíî, ÷òî ðåøåíèå î òîì, êàê ïðåäñòàâëÿòü äàííûå, íåâîçìîæíî ïðèíèìàòü áåç
ïîíèìàíèÿ òîãî, êàêèå àëãîðèòìû áóäóò ê íèì ïðèìåíÿòüñÿ, è
íàîáîðîò, âûáîð àëãîðèòìà ÷àñòî î÷åíü ñèëüíî çàâèñèò îò ñòðîåíèÿ äàííûõ, ê êîòîðûì îí ïðèìåíÿåòñÿ.

Áåç çíàíèÿ ñòðóêòóð äàííûõ è àëãîðèòìîâ íåâîçìîæíî ñîç
äàòü ñêîëüêî-íèáóäü ñåðüåçíûé ïðîãðàììíûé ïðîäóêò. Íè îäíà
èíôîðìàöèîííàÿ ñèñòåìà íå îáõîäèòñÿ áåç ïðîãðàììíîãî îáåñïå÷åíèÿ, áîëåå òîãî, îíà ïðîñòî íå ìîæåò ñóùåñòâîâàòü áåç ýòîé
êîìïîíåíòû. Ïîýòîìó îñíîâíàÿ çàäà÷à äàííîé êíèãè ñîñòîèò â
ñëåäóþùåì:

ïîçíàêîìèòü ñî âñåì ðàçíîîáðàçèåì èìåþùèõñÿ ñòðóêòóð

äàííûõ, ïîêàçàòü, êàê ýòè ñòðóêòóðû ðåàëèçîâàíû â ÿçûêàõ
ïðîãðàììèðîâàíèÿ;

ïîçíàêîìèòü ñ îïåðàöèÿìè,
êîòîðûå âûïîëíÿþòñÿ íàä

ñòðóêòóðàìè äàííûõ;

ïîêàçàòü îñîáåííîñòè ñòðóêòóðíîãî ïîäõîäà ê ðàçðàáîòêå

àëãîðèòìîâ, ïðîäåìîíñòðèðîâàòü ïîðÿäîê ðàçðàáîòêè àëãîðèòìîâ.

Òùàòåëüíî ïîäîáðàííûé ìàòåðèàë, âîøåäøèé â ïîñîáèå,

âêëþ÷àåò â ñåáÿ îñíîâíûå, ôóíäàìåíòàëüíûå êëàññû àëãîðèòìîâ, êîòîðûå â òîì èëè èíîì âèäå íàèáîëåå ÷àñòî âñòðå÷àþòñÿ â
ïðàêòèêå ïðîãðàììèðîâàíèÿ.

Öåííîñòü åãî â òîì, ÷òî îíî ïðåäíàçíà÷åíî íå ñòîëüêî äëÿ

îáó÷åíèÿ òåõíèêå ïðîãðàììèðîâàíèÿ, ñêîëüêî äëÿ îáó÷åíèÿ,
åñëè ýòî âîçìîæíî, «èñêóññòâó» ïðîãðàììèðîâàíèÿ. Íàñòîÿùåå
ïîñîáèå ïðåäëàãàåò ìàññó ðåöåïòîâ óñîâåðøåíñòâîâàíèÿ ïðîãðàìì è, ÷òî ñàìîå ãëàâíîå, ó÷èò ñàìîñòîÿòåëüíî íàõîäèòü ýòè
ðåöåïòû.

Ðàññìîòðåíû ñòðóêòóðû äàííûõ, èõ ïðåäñòàâëåíèå è àëãîðèò
ìû îáðàáîòêè, áåç çíàíèÿ êîòîðûõ íåâîçìîæíî ñîâðåìåííîå
êîìïüþòåðíîå ïðîãðàììèðîâàíèå. Ïðèâåäåíû ðàçëè÷íûå àëãîðèòìû äëÿ ðàáîòû ñ î÷åðåäÿìè, ñòåêàìè, ñïèñêàìè, äåðåâüÿìè,
òàáëèöàìè è ãðàôàìè. Àëãîðèòìû áîëüøèíñòâà îïåðàöèé íàä
ñòðóêòóðàìè äàííûõ äîâåäåíû äî ïðîãðàììíîé ðåàëèçàöèè â
âèäå ôóíêöèé íà ÿçûêàõ Ñè è Turbo Pascal.

 êîíöå êàæäîé ãëàâû ñîäåðæèòñÿ áîëüøîå êîëè÷åñòâî êîí
òðîëüíûõ âîïðîñîâ è çàäà÷ äëÿ ñàìîñòîÿòåëüíîãî ðåøåíèÿ.

Ïîñîáèå ïðåäíàçíà÷åíî äëÿ ñòóäåíòîâ, îáó÷àþùèõñÿ ïî íà
ïðàâëåíèþ è ñïåöèàëüíîñòÿì «Âû÷èñëèòåëüíûå ìàøèíû, ñèñòåìû, êîìïëåêñû è ñåòè», «Àâòîìàòèçèðîâàííûå ñèñòåìû îáðàáîòêè èíôîðìàöèè è óïðàâëåíèÿ», «Ïðîãðàììíîå îáåñïå÷åíèå âû÷èñëèòåëüíîé òåõíèêè è àâòîìàòèçèðîâàííûõ ñèñòåì».

Âûðàæàþ áëàãîäàðíîñòü Ëþäìèëå Ìèõàéëîâíå Ïîääóáíîé

è Áîðèñó Ìàòâååâè÷ó Ïîëîñóõèíó çà ïîìîùü â ïîäãîòîâêå äàííîãî ó÷åáíîãî ïîñîáèÿ.

4
Ââåäåíèå

Ãëàâà 1
ÎÑÍÎÂÛ ÀËÃÎÐÈÒÌÈÇÀÖÈÈ

1.1. Ñòðóêòóðíàÿ îðãàíèçàöèÿ äàííûõ

Îáðàáîòêà íà ïåðñîíàëüíûõ ýëåêòðîííûõ âû÷èñëèòåëüíûõ

ìàøèíàõ (ÏÝÂÌ) äàííûõ ðåàëüíîãî ìèðà òðåáóåò, ÷òîáû èõ
ñòðóêòóðà áûëà îïðåäåëåíà è òî÷íî ïðåäñòàâëåíà â ÏÝÂÌ.
Ñòðóêòóðà äàííûõ îïðåäåëÿåò ñåìàíòèêó äàííûõ, à òàêæå ñïîñîáû îðãàíèçàöèè è óïðàâëåíèÿ äàííûìè. Èíôîðìàöèÿ, ïðåäñòàâëåííàÿ â âèäå ïîñëåäîâàòåëüíîñòè ñèìâîëîâ è ïðåäíàçíà÷åííàÿ
äëÿ îáðàáîòêè íà ÏÝÂÌ, íàçûâàåòñÿ äàííûìè. Ïðè èñïîëüçîâàíèè êîìïüþòåðà äëÿ õðàíåíèÿ è îáðàáîòêè äàííûõ íåîáõîäèìî
õîðîøî çíàòü òèï è ñòðóêòóðó äàííûõ, à òàêæå íàéòè ñïîñîá
íàèáîëåå åñòåñòâåííîãî èõ ïðåäñòàâëåíèÿ. Ñòðóêòóðû äàííûõ è
àëãîðèòìû ñëóæàò òåìè ìàòåðèàëàìè, èç êîòîðûõ ñòðîÿòñÿ ïðîãðàììû.

Áåç ïîíèìàíèÿ ñòðóêòóð äàííûõ è àëãîðèòìîâ íåâîçìîæíî

ñîçäàòü ñåðüåçíûé ïðîãðàììíûé ïðîäóêò — «îíè ñëóæàò áàçîâûìè ýëåìåíòàìè ëþáîé ìàøèííîé ïðîãðàììû. Â îðãàíèçàöèè
ñòðóêòóð äàííûõ è ïðîöåäóð èõ îáðàáîòêè çàëîæåíà âîçìîæíîñòü ïðîâåðêè ïðàâèëüíîñòè ðàáîòû ïðîãðàììû» [4].

1.1.1. Îñíîâíûå ïîíÿòèÿ ñòðóêòóð äàííûõ

 îñíîâå ðàáîòû êîìïüþòåðà ëåæèò óìåíèå îïåðèðîâàòü

òîëüêî ñ îäíèì âèäîì äàííûõ — ñ îòäåëüíûìè áèòàìè, èëè äâîè÷íûìè öèôðàìè. Ðàáîòàåò æå ñ ýòèìè äàííûìè êîìïüþòåð
òîëüêî â ñîîòâåòñòâèè ñ íåèçìåííûì íàáîðîì àëãîðèòìîâ, êîòîðûå îïðåäåëÿþòñÿ ñèñòåìîé êîìàíä ïðîöåññîðà. Çàäà÷è, êîòîðûå ðåøàþòñÿ ñ ïîìîùüþ êîìïüþòåðà, ðåäêî âûðàæàþòñÿ íà
ÿçûêå áèòîâ. Êàê ïðàâèëî, äàííûå èìåþò ôîðìó ÷èñåë, ëèòåð,

òåêñòîâ, ñèìâîëîâ è áîëåå ñëîæíûõ ñòðóêòóð òèïà ïîñëåäîâàòåëüíîñòåé, ñïèñêîâ è äåðåâüåâ. Åùå ðàçíîîáðàçíåå àëãîðèòìû,
ïðèìåíÿåìûå äëÿ ðåøåíèÿ ðàçëè÷íûõ çàäà÷; ôàêòè÷åñêè àëãîðèòìîâ íå ìåíüøå, ÷åì âû÷èñëèòåëüíûõ çàäà÷.

Ñòðóêòóðà äàííûõ îòíîñèòñÿ ïî ñóùåñòâó ê ïðîñòðàíñòâåí
íûì ïîíÿòèÿì: åå ìîæíî ñâåñòè ê ñõåìå îðãàíèçàöèè èíôîðìàöèè â ïàìÿòè êîìïüþòåðà. Àëãîðèòì æå ÿâëÿåòñÿ ñîîòâåòñòâóþùèì ïðîöåäóðíûì ýëåìåíòîì â ñòðóêòóðå ïðîãðàììû — îí ñëóæèò ðåöåïòîì ðàñ÷åòà. Ïåðâûå àëãîðèòìû áûëè ïðèäóìàíû äëÿ
ðåøåíèÿ ÷èñëåííûõ çàäà÷ òèïà óìíîæåíèÿ ÷èñåë, íàõîæäåíèÿ
íàèáîëüøåãî îáùåãî äåëèòåëÿ, âû÷èñëåíèÿ òðèãîíîìåòðè÷åñêèõ
ôóíêöèé è äð. Ñåãîäíÿ â ðàâíîé ñòåïåíè âàæíû è íå÷èñëåííûå
àëãîðèòìû; îíè ðàçðàáîòàíû äëÿ òàêèõ çàäà÷, êàê, íàïðèìåð,
ïîèñê â òåêñòå çàäàííîãî ñëîâà, ïëàíèðîâàíèå ñîáûòèé, ñîðòèðîâêà äàííûõ â óêàçàííîì ïîðÿäêå è ò. ï. Íå÷èñëåííûå àëãîðèòìû îïåðèðóþò ñ äàííûìè, êîòîðûå íå îáÿçàòåëüíî ÿâëÿþòñÿ
÷èñëàìè.

Ñòðóêòóðû äàííûõ, ïðèìåíÿåìûå â àëãîðèòìàõ, ìîãóò áûòü

÷ðåçâû÷àéíî ñëîæíûìè.  ðåçóëüòàòå âûáîð ïðàâèëüíîãî ïðåäñòàâëåíèÿ äàííûõ ÷àñòî ñëóæèò êëþ÷îì ê óäà÷íîìó ïðîãðàììèðîâàíèþ è ìîæåò â áîëüøåé ñòåïåíè ñêàçûâàòüñÿ íà ïðîèçâîäèòåëüíîñòè ïðîãðàììû, ÷åì äåòàëè èñïîëüçóåìîãî àëãîðèòìà.
Âðÿä ëè êîãäà-íèáóäü ïîÿâèòñÿ îáùàÿ òåîðèÿ âûáîðà ñòðóêòóð
äàííûõ. Ñàìîå ëó÷øåå, ÷òî ìîæíî ñäåëàòü, — ðàçîáðàòüñÿ âî
âñåõ áàçîâûõ «êèðïè÷èêàõ» è ñîáðàííûõ èç íèõ ñòðóêòóðàõ.
Ñïîñîáíîñòü ïðèëîæèòü ýòè çíàíèÿ ê êîíñòðóèðîâàíèþ áîëüøèõ ñèñòåì — ýòî ïðåæäå âñåãî äåëî èíæåíåðíîãî ìàñòåðñòâà è
ïðàêòèêè.

Íåçàâèñèìî îò ñîäåðæàíèÿ è ñëîæíîñòè ëþáûå äàííûå â ïà
ìÿòè ÝÂÌ ïðåäñòàâëÿþòñÿ ïîñëåäîâàòåëüíîñòüþ äâîè÷íûõ ðàçðÿäîâ, èëè áèòîâ, à èõ çíà÷åíèÿìè ÿâëÿþòñÿ ñîîòâåòñòâóþùèå
äâîè÷íûå ÷èñëà. Äàííûå, ðàññìàòðèâàåìûå â âèäå ïîñëåäîâàòåëüíîñòè áèòîâ, èìåþò î÷åíü ïðîñòóþ îðãàíèçàöèþ èëè, äðóãèìè ñëîâàìè, ñëàáî ñòðóêòóðèðîâàíû. Äëÿ ÷åëîâåêà îïèñûâàòü è
èññëåäîâàòü ñëîæíûå äàííûå â òåðìèíàõ ïîñëåäîâàòåëüíîñòåé
áèòîâ âåñüìà íåóäîáíî. Áîëåå êðóïíûå è ñîäåðæàòåëüíûå, íåæåëè áèò, «ñòðîèòåëüíûå áëîêè» äëÿ îðãàíèçàöèè ïðîèçâîëüíûõ
äàííûõ ïîëó÷àþòñÿ íà îñíîâå ïîíÿòèÿ «ñòðóêòóðû äàííûõ».

Ïîä ñòðóêòóðîé äàííûõ â îáùåì ñëó÷àå ïîíèìàþò ìíîæåñòâî

ýëåìåíòîâ äàííûõ è ìíîæåñòâî ñâÿçåé ìåæäó íèìè. Òàêîå îïðåäåëåíèå îõâàòûâàåò âñå âîçìîæíûå ïîäõîäû ê ñòðóêòóðèçàöèè

6
Ãëàâà 1. Îñíîâû àëãîðèòìèçàöèè

äàííûõ, íî â êàæäîé êîíêðåòíîé çàäà÷å èñïîëüçóþòñÿ òå èëè
èíûå åãî àñïåêòû. Ïîýòîìó ââîäèòñÿ äîïîëíèòåëüíàÿ êëàññèôèêàöèÿ ñòðóêòóð äàííûõ, íàïðàâëåíèÿ êîòîðîé ñîîòâåòñòâóþò ðàçëè÷íûì àñïåêòàì èõ ðàññìîòðåíèÿ. Ïðåæäå ÷åì ïðèñòóïàòü ê
èçó÷åíèþ êîíêðåòíûõ ñòðóêòóð äàííûõ, äàäèì èõ îáùóþ êëàññèôèêàöèþ ïî íåñêîëüêèì ïðèçíàêàì. Ïîíÿòèå ôèçè÷åñêàÿ
ñòðóêòóðà äàííûõ îòðàæàåò ñïîñîá ôèçè÷åñêîãî ïðåäñòàâëåíèÿ
äàííûõ â ïàìÿòè ìàøèíû è íàçûâàåòñÿ åùå ñòðóêòóðîé õðàíåíèÿ, âíóòðåííåé ñòðóêòóðîé èëè ñòðóêòóðîé ïàìÿòè. Ðàññìîòðåíèå ñòðóêòóðû äàííûõ áåç ó÷åòà åå ïðåäñòàâëåíèÿ â ìàøèííîé
ïàìÿòè
íàçûâàåòñÿ
àáñòðàêòíîé
èëè
ëîãè÷åñêîé
ñòðóêòóðîé.

 îáùåì ñëó÷àå ìåæäó ëîãè÷åñêîé è ñîîòâåòñòâóþùåé åé ôèçè÷åñêîé ñòðóêòóðàìè ñóùåñòâóåò ðàçëè÷èå, êîòîðîå çàâèñèò îò ñàìîé ñòðóêòóðû è îñîáåííîñòåé òîé ñðåäû, â êîòîðîé îíà äîëæíà
áûòü îòðàæåíà. Âñëåäñòâèå ýòîãî ðàçëè÷èÿ ñóùåñòâóþò ïðîöåäóðû, îñóùåñòâëÿþùèå îòîáðàæåíèå ëîãè÷åñêîé ñòðóêòóðû â ôèçè÷åñêóþ è, íàîáîðîò, ôèçè÷åñêîé ñòðóêòóðû â ëîãè÷åñêóþ. Ýòè
ïðîöåäóðû îáåñïå÷èâàþò, êðîìå òîãî, äîñòóï ê ôèçè÷åñêèì
ñòðóêòóðàì è âûïîëíåíèå íàä íèìè ðàçëè÷íûõ îïåðàöèé, ïðè÷åì êàæäàÿ îïåðàöèÿ ðàññìàòðèâàåòñÿ ïðèìåíèòåëüíî ê ëîãè÷åñêîé èëè ôèçè÷åñêîé ñòðóêòóðå äàííûõ.

Ðàçëè÷àþò
ïðîñòûå
(áàçîâûå,
ïðèìèòèâíûå)
ñòðóêòóðû

(òèïû) äàííûõ è èíòåãðèðîâàííûå (ñòðóêòóðèðîâàííûå, êîìïîçèòíûå, ñëîæíûå). Ïðîñòûìè íàçûâàþòñÿ òàêèå ñòðóêòóðû äàííûõ, êîòîðûå íå ìîãóò áûòü ðàñ÷ëåíåíû íà ñîñòàâíûå ÷àñòè,
áîëüøèå, ÷åì áèòû. Ñ òî÷êè çðåíèÿ ôèçè÷åñêîé ñòðóêòóðû âàæíûì ÿâëÿåòñÿ òî îáñòîÿòåëüñòâî, ÷òî â äàííîé ìàøèííîé àðõèòåêòóðå, â äàííîé ñèñòåìå ïðîãðàììèðîâàíèÿ âñåãäà ìîæíî çàðàíåå ñêàçàòü, êàêîâ áóäåò ðàçìåð âûáðàííîãî ïðîñòîãî òèïà è
êàêîâà ñòðóêòóðà åãî ðàçìåùåíèÿ â ïàìÿòè. Ñ ëîãè÷åñêîé òî÷êè
çðåíèÿ ïðîñòûå äàííûå ÿâëÿþòñÿ íåäåëèìûìè åäèíèöàìè.

Èíòåãðèðîâàííûìè íàçûâàþòñÿ òàêèå ñòðóêòóðû äàííûõ, ñî
ñòàâíûìè ÷àñòÿìè êîòîðûõ ÿâëÿþòñÿ äðóãèå ñòðóêòóðû äàííûõ — ïðîñòûå èëè â ñâîþ î÷åðåäü èíòåãðèðîâàííûå. Èíòåãðèðîâàííûå ñòðóêòóðû äàííûõ êîíñòðóèðóþòñÿ ïðîãðàììèñòîì ñ
èñïîëüçîâàíèåì ñðåäñòâ èíòåãðàöèè äàííûõ, ïðåäîñòàâëÿåìûõ
ÿçûêàìè ïðîãðàììèðîâàíèÿ.

 çàâèñèìîñòè îò îòñóòñòâèÿ èëè íàëè÷èÿ ÿâíî çàäàííûõ

ñâÿçåé ìåæäó ýëåìåíòàìè äàííûõ ñëåäóåò ðàçëè÷àòü íåñâÿçíûå
ñòðóêòóðû (âåêòîðû, ìàññèâû, ñòðîêè, ñòåêè, î÷åðåäè) è ñâÿçíûå
ñòðóêòóðû (ñâÿçíûå ñïèñêè).

1.1. Ñòðóêòóðíàÿ îðãàíèçàöèÿ äàííûõ
7

1.1.2. Êëàññèôèêàöèÿ ñòðóêòóð äàííûõ ïî ïðèçíàêó
èçìåí÷èâîñòè

Âåñüìà âàæíûé ïðèçíàê ñòðóêòóðû äàííûõ — åå èçìåí÷è
âîñòü, ò. å. èçìåíåíèå ÷èñëà ýëåìåíòîâ è (èëè) ñâÿçåé ìåæäó ýëåìåíòàìè ñòðóêòóðû.  îïðåäåëåíèè èçìåí÷èâîñòè ñòðóêòóðû íå
îòðàæåí ôàêò èçìåíåíèÿ çíà÷åíèé ýëåìåíòîâ äàííûõ, ïîñêîëüêó
â ýòîì ñëó÷àå âñå ñòðóêòóðû äàííûõ èìåëè áû ñâîéñòâî èçìåí÷èâîñòè. Ïî ïðèçíàêó èçìåí÷èâîñòè ðàçëè÷àþò ñòàòè÷åñêèå, ïîëóñòàòè÷åñêèå, äèíàìè÷åñêèå ñòðóêòóðû. Êëàññèôèêàöèÿ ñòðóêòóð
äàííûõ (ÑÄ) ïî ïðèçíàêó èçìåí÷èâîñòè ïðèâåäåíà íà ðèñ. 1.1.
Áàçîâûå ñòðóêòóðû äàííûõ, ñòàòè÷åñêèå, ïîëóñòàòè÷åñêèå è äèíàìè÷åñêèå õàðàêòåðíû äëÿ îïåðàòèâíîé ïàìÿòè è ÷àñòî íàçûâàþòñÿ îïåðàòèâíûìè ñòðóêòóðàìè. Ôàéëîâûå ñòðóêòóðû ñîîòâåòñòâóþò ñòðóêòóðàì äàííûõ äëÿ âíåøíåé ïàìÿòè.

Âåêòîð (îäíîìåðíûé ìàññèâ) — ñòðóêòóðà äàííûõ ñ ôèêñè
ðîâàííûì ÷èñëîì ýëåìåíòîâ îäíîãî è òîãî æå òèïà.

Ìàññèâ — ïîñëåäîâàòåëüíîñòü ýëåìåíòîâ îäíîãî òèïà, íàçû
âàåìîãî áàçîâûì.

Ìíîæåñòâî — òàêàÿ ñòðóêòóðà, êîòîðàÿ ïðåäñòàâëÿåò ñîáîé

íàáîð íåïîâòîðÿþùèõñÿ äàííûõ îäíîãî è òîãî æå òèïà.

Çàïèñü — êîíå÷íîå óïîðÿäî÷åííîå ìíîæåñòâî ïîëåé, õàðàê
òåðèçóþùèõñÿ ðàçëè÷íûì òèïîì äàííûõ.

8
Ãëàâà 1. Îñíîâû àëãîðèòìèçàöèè

Ðèñ. 1.1. Êëàññèôèêàöèÿ ñòðóêòóð äàííûõ

Òàáëèöà — ïîñëåäîâàòåëüíîñòü çàïèñåé, êîòîðûå èìåþò îäíó

è òó æå îðãàíèçàöèþ.

Ñïèñêîì íàçûâàåòñÿ óïîðÿäî÷åííîå ìíîæåñòâî, ñîñòîÿùåå èç

ïåðåìåííîãî ÷èñëà ýëåìåíòîâ, ê êîòîðûì ïðèìåíèìû îïåðàöèè
âêëþ÷åíèÿ, èñêëþ÷åíèÿ. Ñïèñîê, îòðàæàþùèé îòíîøåíèÿ ñîñåäñòâà ìåæäó ýëåìåíòàìè, íàçûâàåòñÿ ëèíåéíûì.

1.1.2.1. Ñâÿçíûå ñïèñêè

Ñâÿçíûé ñïèñîê — ñòðóêòóðà äàííûõ, ýëåìåíòàìè êîòîðîé

ÿâëÿþòñÿ çàïèñè, ñâÿçàííûå äðóã ñ äðóãîì ñ ïîìîùüþ óêàçàòåëåé, õðàíÿùèõñÿ â ñàìèõ ýëåìåíòàõ (ðèñ. 1.2).

 çàâèñèìîñòè îò õàðàêòåðà âçàèìíîãî ðàñïîëîæåíèÿ ýëå
ìåíòîâ â ïàìÿòè ñòðóêòóðû äàííûõ ìîæíî ðàçäåëèòü íà ñòðóêòóðû ñ ïîñëåäîâàòåëüíûì ðàñïðåäåëåíèåì ýëåìåíòîâ â ïàìÿòè (âåêòîðû, ñòðîêè, ìàññèâû, ñòåêè, î÷åðåäè) è ñòðóêòóðû ñ ïðîèçâîëüíûì ñâÿçíûì ðàñïðåäåëåíèåì ýëåìåíòîâ â ïàìÿòè (îäíîñâÿçíûå,
äâóõñâÿçíûå ñïèñêè) (ðèñ. 1.3).

 ÿçûêàõ ïðîãðàììèðîâàíèÿ ïîíÿòèå «ñòðóêòóðû äàííûõ»

òåñíî ñâÿçàíî ñ ïîíÿòèåì «òèïû äàííûõ». Ëþáûå äàííûå, ò. å.
êîíñòàíòû, ïåðåìåííûå, çíà÷åíèÿ ôóíêöèé èëè âûðàæåíèÿ, õàðàêòåðèçóþòñÿ ñâîèìè òèïàìè. Èíôîðìàöèÿ ïî êàæäîìó òèïó
îäíîçíà÷íî îïðåäåëÿåò:

1) ñòðóêòóðó õðàíåíèÿ äàííûõ óêàçàííîãî òèïà, ò. å. âûäåëå
íèå ïàìÿòè è ïðåäñòàâëåíèå äàííûõ â íåé, ñ îäíîé ñòîðîíû, è
èíòåðïðåòèðîâàíèå äâîè÷íîãî ïðåäñòàâëåíèÿ, ñ äðóãîé;

2) ìíîæåñòâî äîïóñòèìûõ çíà÷åíèé, êîòîðûå ìîæåò èìåòü

òîò èëè èíîé îáúåêò îïèñûâàåìîãî òèïà;

1.1. Ñòðóêòóðíàÿ îðãàíèçàöèÿ äàííûõ
9

Ðèñ. 1.2. Êëàññèôèêàöèÿ ñâÿçíûõ ñïèñêîâ

3) ìíîæåñòâî äîïóñòèìûõ îïåðàöèé, êîòîðûå ïðèìåíèìû ê

îáúåêòó îïèñûâàåìîãî òèïà.

Íàä âñåìè ñòðóêòóðàìè äàííûõ ìîãóò âûïîëíÿòüñÿ ÷åòûðå

îïåðàöèè: ñîçäàíèå; óíè÷òîæåíèå; âûáîð (äîñòóï); îáíîâëåíèå.

Îïåðàöèÿ ñîçäàíèÿ çàêëþ÷àåòñÿ â âûäåëåíèè ïàìÿòè äëÿ

ñòðóêòóðû äàííûõ. Ïàìÿòü ìîæåò âûäåëÿòüñÿ â ïðîöåññå âûïîëíåíèÿ ïðîãðàììû ïðè ïåðâîì ïîÿâëåíèè èìåíè ïåðåìåííîé â
èñõîäíîé ïðîãðàììå èëè íà ýòàïå êîìïèëÿöèè. Â ðÿäå ÿçûêîâ
äëÿ ñòðóêòóðèðîâàííûõ äàííûõ, êîíñòðóèðóåìûõ ïðîãðàììèñòîì, îïåðàöèÿ ñîçäàíèÿ âêëþ÷àåò â ñåáÿ òàêæå óñòàíîâêó íà÷àëüíûõ
çíà÷åíèé
ïàðàìåòðîâ
ñîçäàâàåìîé
ñòðóêòóðû.
Äëÿ

ñòðóêòóð äàííûõ, îáúÿâëåííûõ â ïðîãðàììå, ïàìÿòü âûäåëÿåòñÿ
àâòîìàòè÷åñêè ñðåäñòâàìè ñèñòåìû ïðîãðàììèðîâàíèÿ ëèáî íà
ýòàïå êîìïèëÿöèè, ëèáî ïðè àêòèâèçàöèè ïðîöåäóðíîãî áëîêà, â
êîòîðîì îáúÿâëÿþòñÿ ïåðåìåííûå. Ïðîãðàììèñò ìîæåò è ñàì
âûäåëÿòü ïàìÿòü äëÿ ñòðóêòóð äàííûõ, èñïîëüçóÿ èìåþùèåñÿ â
ñèñòåìå ïðîãðàììèðîâàíèÿ ñîîòâåòñòâóþùèå ñðåäñòâà äëÿ âûäåëåíèÿ è îñâîáîæäåíèÿ ïàìÿòè. Â îáúåêòíî-îðèåíòèðîâàííûõ
ÿçûêàõ ïðîãðàììèðîâàíèÿ ïðè ðàçðàáîòêå íîâîãî îáúåêòà äëÿ

10
Ãëàâà 1. Îñíîâû àëãîðèòìèçàöèè

Ðèñ. 1.3. Ïðåäñòàâëåíèå ñòðóêòóð äàííûõ â îïåðàòèâíîé (à)

è âî âíåøíåé (á) ïàìÿòè

íåãî äîëæíû áûòü îïðåäåëåíû ïðîöåäóðû åãî ñîçäàíèÿ è óíè÷òîæåíèÿ.

Îïåðàöèÿ óíè÷òîæåíèÿ ñòðóêòóð äàííûõ ïðîòèâîïîëîæíà ïî

ñâîåìó äåéñòâèþ îïåðàöèè ñîçäàíèÿ. Îïåðàöèÿ óíè÷òîæåíèÿ
ïîìîãàåò ýôôåêòèâíî èñïîëüçîâàòü ïàìÿòü.

Îïåðàöèÿ âûáîðà èñïîëüçóåòñÿ ïðîãðàììèñòàìè äëÿ äîñòóïà ê

äàííûì âíóòðè ñàìîé ñòðóêòóðû. Ôîðìà îïåðàöèè äîñòóïà çàâèñèò îò òèïà ñòðóêòóðû äàííûõ, ê êîòîðîé îñóùåñòâëÿåòñÿ îáðàùåíèå. Ìåòîä äîñòóïà — îäíî èç íàèáîëåå âàæíûõ ñâîéñòâ ñòðóêòóð,
îñîáåííî â ñâÿçè ñ òåì, ÷òî ýòî ñâîéñòâî èìååò íåïîñðåäñòâåííîå
îòíîøåíèå ê âûáîðó êîíêðåòíîé ñòðóêòóðû äàííûõ.

Îïåðàöèÿ îáíîâëåíèÿ ïîçâîëÿåò èçìåíèòü çíà÷åíèÿ äàííûõ â

ñòðóêòóðå äàííûõ. Ïðèìåðîì îïåðàöèè îáíîâëåíèÿ ÿâëÿåòñÿ
îïåðàöèÿ ïðèñâàèâàíèÿ, èëè, áîëåå ñëîæíàÿ ôîðìà — ïåðåäà÷à
ïàðàìåòðîâ.

Âûøåóêàçàííûå
÷åòûðå
îïåðàöèè
îáÿçàòåëüíû
äëÿ
âñåõ

ñòðóêòóð è òèïîâ äàííûõ. Ïîìèìî ýòèõ îáùèõ îïåðàöèé äëÿ êàæäîé ñòðóêòóðû äàííûõ ìîãóò áûòü îïðåäåëåíû ñïåöèôè÷åñêèå
îïåðàöèè, ðàáîòàþùèå òîëüêî ñ äàííûìè óêàçàííîãî òèïà (äàííîé ñòðóêòóðû). Ñïåöèôè÷åñêèå îïåðàöèè àíàëèçèðóþòñÿ ïðè
ðàññìîòðåíèè êàæäîé êîíêðåòíîé ñòðóêòóðû äàííûõ.

1.1.3. Ëèíåéíûå è íåëèíåéíûå ñòðóêòóðû äàííûõ

Âàæíûé ïðèçíàê ñòðóêòóðû äàííûõ — õàðàêòåð óïîðÿäî÷åí
íîñòè åå ýëåìåíòîâ. Ïî ýòîìó ïðèçíàêó ñòðóêòóðû ìîæíî ðàçäåëèòü íà ëèíåéíûå è íåëèíåéíûå ñòðóêòóðû (ðèñ. 1.4).

1.1. Ñòðóêòóðíàÿ îðãàíèçàöèÿ äàííûõ
11

Ðèñ. 1.4. Ëèíåéíûå è íåëèíåéíûå ñòðóêòóðû äàííûõ