Программирование на языках высокого уровня. Методические указания - 17 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

17
òîðîãî êîëè÷åñòâà èíôîðìàöèîííûõ ïîëåé, ïðèñóòñòâóåò â êàæäîì ýëå-
ìåíòå ñïèñêà è êîòîðîå ñîäåðæèò óêàçàòåëü, èëè àäðåñ, ñëåäóþùåãî
ýëåìåíòà ëèíåéíîé ñòðóêòóðû. Â C-ïðîãðàììå îïèñàíèå òàêîé ñòðóêòó-
ðû âûïîëíÿåòñÿ ïî ñõåìå:
struct listrec{
<òèï1> info1; //èíôîðìàöèîííûå
. . .
<òèïn>infon; //ïîëÿ
struct listrec *link; //ïîëå óêàçàòåëÿ
};
Äèíàìè÷åñêèé ëèíåéíûé ñïèñîê ÿâëÿåòñÿ ïðèìåðîì ñòðóêòóðû ñ
ïîñëåäîâàòåëüíûì äîñòóïîì. Îí çàäàåòñÿ óêàçàòåëåì (ò. å. ñ èñïîëüçî-
âàíèåì âûøåïðèâåäåííûõ îáîçíà÷åíèé ïåðåìåííîé-óêàçàòåëåì íà äàí-
íûå òèïà struct listrec) íà ïåðâûé ýëåìåíò ñïèñêà. Äëÿ òîãî ÷òîáû ïîëó-
÷èòü äîñòóï ê i-ìó ýëåìåíòó, íåîáõîäèìî ïîñëåäîâàòåëüíî ïðîñìîòðåòü
i1 ýëåìåíòîâ ñïèñêà, íà÷èíàÿ ñ ïåðâîãî:
base = first;
for(j = 1; j<= i1; j++)
base = base>link;
Ïðèâåäåííûé ôðàãìåíò ïðîãðàììû ïîäðàçóìåâàåò, ÷òî ïåðåìåííûå
base è first èìåþò òèï: struct listrec *first, *base ; â ïåðåìåííîé first ñîäåð-
æèòñÿ àäðåñ ïåðâîãî ýëåìåíòà ñïèñêà. Ðåçóëüòàòîì âûïîëíåíèÿ ôðàã-
ìåíòà ÿâëÿåòñÿ çíà÷åíèå ïåðåìåííîé base àäðåñ i-ãî ýëåìåíòà ñïèñêà.
Ôîðìèðîâàíèå ýëåìåíòîâ äèíàìè÷åñêîé ñòðóêòóðû âûïîëíÿåòñÿ â
äâà äåéñòâèÿ: îòâåäåíèå ïàìÿòè äëÿ ýëåìåíòà è çàïîëíåíèå îòâåäåííîé
ïàìÿòè íåêîòîðûìè çíà÷åíèÿìè. Ïåðâîå äåéñòâèå âûïîëíÿåòñÿ îïåðà-
òîðîì: <óêàçàòåëü> = new <òèï>. Ðåçóëüòàòîì ÿâëÿåòñÿ âûäåëåíèå èç
äèíàìè÷åñêîé îáëàñòè ôðàãìåíòà ïàìÿòè, îáúåì êîòîðîãî îïðåäåëÿåòñÿ
òèïîì, óêàçàííûì ïîñëå new, à àäðåñ âûäåëåííîãî ôðàãìåíòà áóäåò ïî-
ìåùåí â ïåðåìåííóþ-óêàçàòåëü. Òàêèì îáðàçîì, ïîëó÷åííîå çíà÷åíèå
ñëåäóåò ïîìåñòèòü â ïîëå link ïðåäûäóùåãî ïî îòíîøåíèþ ê ôîðìèðóå-
ìîìó ýëåìåíòó ñïèñêà. Â ïîëå link ïîñëåäíåãî ýëåìåíòà ñïèñêà ñëåäóåò
ïîìåñòèòü «ïóñòîé» àäðåñ, êîòîðûé îáîçíà÷àåòñÿ çàðåçåðâèðîâàííûì
ñëîâîì NULL. Çàïîëíåíèå îñòàëüíûõ (èíôîðìàöèîííûõ) ïîëåé ýëåìåíòà
ñïèñêà îñóùåñòâëÿåòñÿ â ñîîòâåòñòâèè ñ íàçíà÷åíèåì ñïèñêà â êîíêðåòíîé
çàäà÷å è àëãîðèòìîì åå ðåøåíèÿ. Ïðè ýòîì äîñòóï ê ïîëþ îðãàíèçóåòñÿ
÷åðåç óêàçàòåëü íà ýëåìåíò ñïèñêà, íàïðèìåð:
base>info1=<çíà÷åíèå òèïà <òèï 1>>,

Страницы