Библиотека программи�та
Пользователь

Добро пожаловать,

Реги�траци� или входРеги�траци� или вход
Потер�ли пароль?Потер�ли пароль?

�ик:
Пароль:

Меню �айта




Ваше мнение
Какой браузер Вы предпочитаете?

Internet Explorer
Mozilla Firefox
Opera
Netscape
Chrome
Другой


Результаты
Другие опро�ы

В�его голо�ов: 1676
Комментарии: 10


�аши партнеры



Стати�тика




Programming books  Download software  Documentation  Scripts  Content Managment Systems(CMS)  Templates  Icon Sets  Articles  Contacts  Voting  Site Search




Книги-online



Ëàáîðàòîðíàÿ ðàáîòà ¹6

Ëàáîðàòîðíàÿ ðàáîòà ¹6


Ëèíåéíûå ñïèñêè

Öåëü ðàáîòû:
Ïîëó÷èòü ïðàêòè÷åñêèå íàâûêè ðàáîòû ñ äèíàìè÷åñêèìè ïåðåìåííûìè è äèíàìè÷åñêèìè ñòðóêòóðàìè äàííûõ.

Îáùèå ñâåäåíèÿ

Äëÿ ðàáîòû ñ äèíàìè÷åñêèìè ñòðóêòóðàìè äàííûõ èñïîëüçóþòñÿ óêàçàòåëè. Óêàçàòåëè ïðåäñòàâëÿþò ñîáîé ñïåöèàëüíûé òèï äàííûõ. Îíè ïðèíèìàþò çíà÷åíèÿ, ðàâíûå àäðåñàì ðàçìåùåíèÿ â îïåðàòèâíîé ïàìÿòè ñîîòâåòñòâóþùèõ äèíàìè÷åñêèõ ïåðåìåííûõ.
Ñïèñêîì íàçûâàåòñÿ ñòðóêòóðà äàííûõ, êàæäûé ýëåìåíò êîòîðîé ïîñðåäñòâîì óêàçàòåëÿ ñâÿçûâàåòñÿ ñî ñëåäóþùèì ýëåìåíòîì. Íà ñàìûé ïåðâûé ýëåìåíò (ãîëîâó ñïèñêà) èìååòñÿ îòäåëüíûé óêàçàòåëü.
Èç îïðåäåëåíèÿ ñëåäóåò, ÷òî êàæäûé ýëåìåíò ñïèñêà ñîäåðæèò ïîëå äàííûõ (îíî ìîæåò èìåòü ñëîæíóþ ñòðóêòóðó) è ïîëå ññûëêè íà ñëåäóþùèé ýëåìåíò. Ïîñëå ññûëêè ïîñëåäíåãî ýëåìåíòà äîëæíî ñîäåðæàòü ïóñòîé óêàçàòåëü (nil).
×èñëî ýëåìåíòîâ ñâÿçàííîãî ñïèñêà ìîæåò ðàñòè èëè óìåíüøàòüñÿ â çàâèñèìîñòè îò òîãî, ñêîëüêî äàííûõ ìû õîòèì õðàíèòü â íåì. ×òîáû äîáàâèòü íîâûé ýëåìåíò â ñïèñîê, íåîáõîäèìî:
1. Ïîëó÷èòü ïàìÿòü äëÿ íåãî;
2. Ïîìåñòèòü òóäà èíôîðìàöèþ;
3. Äîáàâèòü ýëåìåíò â êîíåö ñïèñêà (èëè íà÷àëî).
Ýëåìåíò ñïèñêà ñîñòîèò èç ðàçíîòèïíûõ ÷àñòåé (õðàíèìàÿ èíôîðìàöèÿ è óêàçàòåëü), è åãî åñòåñòâåííî ïðåäñòàâèòü çàïèñüþ. Ïåðåä îïèñàíèåì ñàìîé çàïèñè îïèñûâàþò óêàçàòåëü íà íåå:
Type { îïèñàíèå ñïèñêà èç öåëûõ ÷èñåë }
  PList = ^TList;
  TList = record
     Inf : Integer;
     Next : PList;
  end;

Ïðèìåðû

Ñîçäàíèå ñïèñêà.
Çàäà÷à. Ñôîðìèðîâàòü ñïèñîê, ñîäåðæàùèé öåëûå ÷èñëà 3, 5, 1, 9.
Îïðåäåëèì çàïèñü òèïà TList ñ ïîëÿìè, ñîäåðæàùèìè õàðàêòåðèñòèêè äàííûõ – çíà÷åíèÿ î÷åðåäíîãî ýëåìåíòà è àäðåñà ñëåäóþùåãî çà íèì ýëåìåíòà
PList = ^TList;
  TList = record
     Data : Integer;
     Next : PList;
  end;
×òîáû ñïèñîê ñóùåñòâîâàë, íàäî îïðåäåëèòü óêàçàòåëü íà åãî íà÷àëî. Îïèøåì ïåðåìåííûå.
Var
  Head, x : PList;
Ñîçäàäèì ïåðâûé ýëåìåíò: New(Head); { âûäåëÿåì ìåñòî â ïàìÿòè äëÿ ïåðåìåííîé Head } Head^.Next := nil; { óêàçàòåëü íà ñëåäóþùèé ýëåìåíò ïóñò (òàêîãî ýëåìåíòà íåò) } Head^.Data := 3; { çàïîëíÿåì èíôîðìàöèîííîå ïîëå ïåðâîãî ýëåìåíòà }
Ïðîäîëæèì ôîðìèðîâàíèå ñïèñêà, äëÿ ýòîãî íóæíî äîáàâèòü ýëåìåíò â êîíåö ñïèñêà.
Ââåäåì âñïîìîãàòåëüíóþ ïåðåìåííóþ óêàçàòåëüíîãî òèïà, êîòîðàÿ áóäåò õðàíèòü àäðåñ ïîñëåäíåãî ýëåìåíòà ñïèñêà: x := Head; {ñåé÷àñ ïîñëåäíèé ýëåìåíò ñïèñêà ñîâïàäàåò ñ åãî íà÷àëîì}
New(x^.Next); { âûäåëèì îáëàñòè ïàìÿòè äëÿ ñëåäóþùåãî (2-ãî) ýëåìåíòà è ïîìåñòèì åãî àäðåñ â àäðåñíóþ ÷àñòü ïðåäûäóùåãî (1-ãî) ýëåìåíòà }
x := x^.Next ; { ïåðåìåííàÿ x ïðèíèìàåò çíà÷åíèå àäðåñà âûäåëåííîé îáëàñòè. Òàêèì îáðàçîì îñóùåñòâëÿåòñÿ ïåðåõîä ê ñëåäóþùåìó (2-îìó) ýëåìåíòó ñïèñêà }
x^.Data := 5; { çíà÷åíèå ýòîãî ýëåìåíòà } x^.Next := nil; {ñëåäóþùåãî çíà÷åíèÿ íåò }
Îñòàëüíûå ÷èñëà çàíîñÿòñÿ àíàëîãè÷íî: New(x^.Next); { âûäåëèì îáëàñòè ïàìÿòè äëÿ ñëåäóþùåãî ýëåìåíòà } x := x^.Next ; { ïåðåõîä ê ñëåäóþùåìó (3-ìó) ýëåìåíòó ñïèñêà } x^.Data := 1; { çíà÷åíèå ýòîãî ýëåìåíòà } x^.Next := nil; {ñëåäóþùåãî çíà÷åíèÿ íåò } New(x^.Next); { âûäåëèì îáëàñòè ïàìÿòè äëÿ ñëåäóþùåãî ýëåìåíòà } x := x^.Next ; { ïåðåõîä ê ñëåäóþùåìó (4-ìó) ýëåìåíòó ñïèñêà } x^.Data := 9; { çíà÷åíèå ýòîãî ýëåìåíòà } x^.Next := nil; {ñëåäóþùåãî çíà÷åíèÿ íåò }
Çàìå÷àíèå. Êàê âèäíî èç ïðèìåðà, îòëè÷íûì ÿâëÿåòñÿ òîëüêî ñîçäàíèå ïåðâîãî (Head) ýëåìåíòà – ãîëîâû ñïèñêà. Âñå îñòàëüíûå äåéñòâèÿ ïîëíîñòüþ àíàëîãè÷íû è èõ åñòåñòâåííî âûïîëíÿòü â öèêëå.
Ïðèñîåäèíåíèå íîâîãî ýëåìåíòà ê ãîëîâå ñïèñêà ïðîèçâîäèòñÿ àíàëîãè÷íî: ……………….. New(x); { ââîä çíà÷åíèÿ ýëåìåíòà x^.Data := … } x^.Next := Head; Head := x; ………………..
 ýòîì ñëó÷àå ïîñëåäíèé ââåäåííûé ýëåìåíò îêàæåòñÿ â ñïèñêå ïåðâûì, à ïåðâûé – ïîñëåäíèì.
Ïðîñìîòð ñïèñêà.
Ïðîñìîòð ýëåìåíòîâ ñïèñêà îñóùåñòâëÿåòñÿ ïîñëåäîâàòåëüíî, íà÷èíàÿ ñ åãî íà÷àëà. Óêàçàòåëü List ïîñëåäîâàòåëüíî ññûëàåòñÿ íà ïåðâûé, âòîðîé è ò. ä. ýëåìåíòû ñïèñêà äî òåõ ïîð, ïîêà âåñü ñïèñîê íå áóäåò ïðîéäåí. Ïðè ýòîì ñ êàæäûì ýëåìåíòîì ñïèñêà âûïîëíÿåòñÿ íåêîòîðàÿ îïåðàöèÿ– íàïðèìåð, ïå÷àòü ýëåìåíòà. Íà÷àëüíîå çíà÷åíèå List – àäðåñ ïåðâîãî ýëåìåíòà ñïèñêà (Head). Digit – çíà÷åíèå óäàëÿåìîãî ýëåìåíòà.
List := Head;
While List^.Next <> nil do
  begin
     WriteLn(List^.Data);
     List := List^.Next; { ïåðåõîä ê ñëåäóþùåìó ýëåìåíòó; àíàëîã äëÿ ìàññèâà i:=i+1 }
  end;
Óäàëåíèå ýëåìåíòà èç ñïèñêà.
Ïðè óäàëåíèè ýëåìåíòà èç ñïèñêà íåîáõîäèìî ðàçëè÷àòü òðè ñëó÷àÿ:1. Óäàëåíèå ýëåìåíòà èç íà÷àëà ñïèñêà.
2. Óäàëåíèå ýëåìåíòà èç ñåðåäèíû ñïèñêà.
3. Óäàëåíèå èç êîíöà ñïèñêà.
Óäàëåíèå ýëåìåíòà èç íà÷àëà ñïèñêà.
List := Head; { çàïîìíèì àäðåñ ïåðâîãî ýëåìåíòà ñïèñêà }
Head := Head^.List; { òåïåðü Head óêàçûâàåò íà âòîðîé ýëåìåíò ñïèñêà }
Dispose(List); { îñâîáîäèì ïàìÿòü, çàíÿòóþ ïåðåìåííîé List^ }
Óäàëåíèå ýëåìåíòà èç ñåðåäèíû ñïèñêà.
Äëÿ ýòîãî íóæíî çíàòü àäðåñà óäàëÿåìîãî ýëåìåíòà è ýëåìåíòà, íàõîäÿùåãîñÿ â ñïèñêå ïåðåä íèì.
List := Head;
While (List<>nil) and (List^.Data<>Digit) do
  begin
     x := List;
     List := List^.Next;
  end;
x^.Next := List^.Next;
Dispose(List);
 Óäàëåíèå èç êîíöà ñïèñêà.
Îíî ïðîèçâîäèòñÿ, êîãäà óêàçàòåëü õ ïîêàçûâàåò íà ïðåäïîñëåäíèé ýëåìåíò ñïèñêà, à List – íà ïîñëåäíèé.
List := Head; x := Head;
While List^.Next<>nil do
  begin
     x := List;
     List := List^.Next;
  end;
x^.Next := nil;
Dispose(List);

Êîíòðîëüíûå âîïðîñû

1. ×òî òàêîå óêàçàòåëè? Êàêèå çíà÷åíèÿ îíè ìîãóò ïðèíèìàòü? Êàêèå îïåðàöèè âîçìîæíû íàä óêàçàòåëÿìè?
2. ×òî ïðåäñòàâëÿþò ñîáîé äèíàìè÷åñêèå ñòðóêòóðû äàííûõ? Äëÿ ÷åãî îíè èñïîëüçóþòñÿ? ×åì îòëè÷àþòñÿ îò äàííûõ ñòàòè÷åñêîãî òèïà?
3. Êàêèå ñòàíäàðòíûå ïðîöåäóðû ñóùåñòâóþò â ÿçûêå Pascal äëÿ ðàáîòû ñ óêàçàòåëÿìè?
4. Çà÷åì ðàçëè÷àòü òèïû óêàçàòåëåé?
5. Êàêèå îïåðàöèè òðåáóåòñÿ âûïîëíèòü äëÿ âñòàâêè è óäàëåíèÿ ýëåìåíòà ñïèñêà?
6. Ñêîëüêî ýëåìåíòîâ ìîæåò ñîäåðæàòü ñïèñîê?
7. Ìîæíî ëè äëÿ ïîñòðîåíèÿ ñïèñêà îáîéòèñü îäíîé ïåðåìåííîé?

Âàðèàíòû çàäàíèé

1. Ñôîðìèðîâàòü ñïèñîê ñòðîê è à) ñîõðàíèòü åãî â òåêñòîâîì ôàéëå; á) ñîõðàíèòü åãî â îáðàòíîì ïîðÿäêå â òåêñòîâîì ôàéëå. Èñïîëüçîâàòü ðåêóðñèþ.
2. Ñôîðìèðîâàòü ñïèñîê ñòðîê èç òåêñòîâîãî ôàéëà.
3. Íàïèñàòü ôóíêöèþ, êîòîðàÿ âû÷èñëÿåò ñðåäíåå àðèôìåòè÷åñêîå ýëåìåíòîâ íåïóñòîãî ñïèñêà.
4. Íàïèñàòü ïðîöåäóðó ïðèñîåäèíåíèÿ ñïèñêà L2 ê ñïèñêó L1.
5. Íàïèñàòü ôóíêöèþ, êîòîðàÿ ñîçäàåò ñïèñîê L2, ÿâëÿþùèéñÿ êîïèåé ñïèñêà L1, íà÷èíàþùåãîñÿ ñ äàííîãî óçëà.
6. Íàïèñàòü ôóíêöèþ, êîòîðàÿ ïîäñ÷èòûâàåò êîëè÷åñòâî âõîæäåíèé êëþ÷à â ñïèñêå.
7. Íàïèñàòü ôóíêöèþ, êîòîðàÿ óäàëÿåò èç ñïèñêà âñå âõîæäåíèÿ êëþ÷à.
8. Ìíîãî÷ëåí çàäàí ñâîèìè êîýôôèöèåíòàìè, êîòîðûå õðàíÿòñÿ â ôîðìå ñïèñêà. Íàïèñàòü ôóíêöèè:
– Equal(p, q), ïðîâåðÿþùóþ íà ðàâåíñòâî ìíîãî÷ëåíû p è q;
– Summa(p, q, r), êîòîðàÿ ñòðîèò ìíîãî÷ëåí r = p + q.
9. Âû÷èñëèòü çíà÷åíèå ìíîãî÷ëåíà â öåëî÷èñëåííîé òî÷êå x. Êîýôôèöèåíòû ââîäÿòñÿ ñ êëàâèàòóðû è äèíàìè÷åñêè ðàçìåùàþòñÿ â ïàìÿòè.
10. Ñôîðìèðîâàòü ñïèñîê öåëûõ ÷èñåë è óïîðÿäî÷èòü èõ ïî íåóáûâàíèþ.
11. Ñôîðìèðîâàòü ñïèñîê öåëûõ ÷èñåë è óäàëèòü èç íåãî âñå ÷åòíûå.
12. Ñôîðìèðîâàòü ñïèñîê âåùåñòâåííûõ ÷èñåë è âû÷èñëèòü ñóììó.
13. Íàïèñàòü ðåêóðñèâíóþ è íåðåêóðñèâíóþ ïðîöåäóðû ïðîâåðêè íàëè÷èÿ â ñïèñêå çàäàííîãî ÷èñëà.
14. Íàïèñàòü ôóíêöèþ, êîòîðàÿ ïðîâåðÿåò, óïîðÿäî÷åíû ëè ýëåìåíòû ñïèñêà ïî àëôàâèòó.
15. Íàïèñàòü ôóíêöèþ, ïîäñ÷èòûâàþùóþ êîëè÷åñòâî ñëîâ â ñïèñêå, êîòîðûå íà÷èíàþòñÿ ñ òîé æå áóêâû, ÷òî è ñëåäóþùåå ñëîâî.
16. Îïðåäåëèòü ñèììåòðè÷íîñòü ïðîèçâîëüíîãî òåêñòà ëþáîé äëèíû. Òåêñò äîëæåí îêàí÷èâàòüñÿ òî÷êîé. Çàäà÷ó ðåøèòü ñ ïîìîùüþ äâóõ ñïèñêîâ.
17. Âû÷èñëèòü çíà÷åíèå âûðàæåíèÿ. Çíà÷åíèÿ ââîäÿòñÿ ñ êëàâèàòóðû è äèíàìè÷åñêè ðàçìåùàþòñÿ â ïàìÿòè.
18. Íàïèñàòü ôóíêöèþ, êîòîðàÿ èñïîëüçóåò èñõîäíûé ñïèñîê L è ñîçäàåò äâà íîâûõ ñïèñêà L1 è L2. L1 ñîäåðæèò íå÷åòíûå óçëû, à L2 – ÷åòíûå.
19. Íàïèñàòü ôóíêöèþ, êîòîðàÿ èñïîëüçóåò èñõîäíûé ñïèñîê L è ñîçäàåò äâà íîâûõ ñïèñêà L1 è L2. L1 ñîäåðæèò íå÷åòíûå ÷èñëà, à L2 – ÷åòíûå.
20. Ñôîðìèðîâàòü äâà ñïèñêà, îòñîðòèðîâàòü èõ îáúåäèíèòü â îäèí, íå íàðóøàÿ ïîðÿäêà.
Íàçàä
Íà ãëàâíóþ
    Ó÷åáíèê ïî ÿçûêó Pascal          Ëàáîðàòîðíûå ðàáîòû ïî ïðîãðàììèðîâàíèþ          Ñïðàâî÷íèê


Внимание! Е�ли у ва� не получило�ь найти нужную информацию, и�пользуйте рубрикатор или во�пользуйте�ь пои�ком


.


книги по программированию и�ходники компоненты шаблоны �айтов C++ PHP Delphi �качать