лекции (2008) (by Kravets) (укороченное) (1160827), страница 9
Текст из файла (страница 9)
Ê ññûëêè ÿçûêà Ñ++ ïðèìåíèìà åäèíñòâåííàÿîïåðàöèÿ åå èíèöèàëèçàöèè.T &a;Ìîæåò áûòü îïèñàíà êàê1- ïåðåìåííàÿ ñîîòâåòñòâóþùåãî òèïà, äîëæíà áûòü èíèöèàëèçèðîâàíà ÷åðåç èìÿ ñîîòâåòñòâóþùåãî îáúåêòà.2 -ôîðìàëüíûå ïàðàìåòðû ïðîöåäóð è ôóíêöèé.void swap (T& a, T& b);3 âîçâðàùàåìîå çíà÷åíèå ôóíêöèè.X& f();4 êàê ÷ëåí êëàññà. Èíèöèàëèçèðóåòñÿ â êîíñòðóêòîðå.Ññûëî÷íûé òèï äàííûõ îêàçàëñÿ î÷åíü óäîáíûì.23Èòàê ðàññìîòðåíèå ïðèìèòèâíûõ òèïîâ äàííûõ çàêîí÷åíî.
Åäèíñòâåííûé òèï äàííûõ, äîáàâëåííûé âÑ++ èçíà÷àëüíî ññûëî÷íûé òèï.  ñîâðåìåííûõ áèáëèîòåêàõ Ñ++ ïðèñóòñòâóåò ñïåö òèï äàííûõ smart pointer. Îí ìîæåò íàïðèìåð ïðîâåðÿòü âàëèäíîñòü îáúåêòà äîñòóïà, àâòîìàòè÷åñêîå óäàëåíèå îáúåêòàíà êîòîðûé îí óêàçûâàåò è òàê äàëåå.24Ëåêöèÿ11.Ãëàâà 2. Ñîñòàâíûå òèïû äàííûõ.Òèïû äàííûõ, âñòðîåííûå â ÿçûê ïðîãðàììèðîâàíèÿ, íî ïðè ýòîì èìåþò âíóòðåííþþ ñòðóêòóðó.Ìàññèâû.Çàïèñè / ñòðóêòóðû / îáúåäèíåíèÿ.Ìíîæåñòâà.(Ñòàíäàðòíûé Ïàñêàëü)Ôàéëû (ñòàíäàðòíûé Ïàñêàëü)Ñòðîêè (íå ñîâñåì òèï (â ÿçûêå Ïàñêàëü) packed array of char).Êëàññû ÿçûêà Ñ++ íå ÿâëÿþòñÿ ñîñòàâíûìè òèïàìè äàííûõ.Îòäåëüíî ìîæíî äîáàâèòü àññîöèàòèâíûåìàññèâû è Hash òàáëèöû. ñîâðåìåííûõ ßÏ ìíîãèå òàêèå ñòðóêòóðû äàííûõ âìåñòî äîáàâëåíèÿ èõ â êîìïèëÿòîð, äîáàâëÿåòñÿ âñòàíäàðòíóþ áèáëèîòåêó ÿçûêà.
Äëÿ ìíîæåñòâà èç íèõ íå ñóùåñòâóåò óíèâåðñàëüíîãî, îäíîâðåìåííî ýôôåêòèâíîãî ñðåäñòâà ïðåäñòàâëåíèÿ äàííûõ. Âìåñòî ýòîãî âûáèðàåòñÿ íåêîòîðàÿ ðåàëèçàöèÿ êîòîðàÿ âõîäèò âñòàíäàðòíóþ áèáëèîòåêó. Ïðè ýòîì ñîõðàíÿåòñÿ âîçìîæíîñòü âûáîðà îïòèìàëüíîé ðåàëèçàöèè ïîä êîíêðåòíóþ çàäà÷ó. Äëÿ ïðèìåðà ðàññìîòðèì ñîðòèðîâêó. Äëÿ áîëüøèíñòâà çàäà÷ èñïîëüçóåòñÿ quick Sort, íî âî âñåáèáëèîòåêè ßÏ âêëþ÷àþò êàê ìèíèìóì åùå îäèí àëãîðèòì, íàïðèìåð heap Sort. Òî åñòü âñòðàèâàÿ ïîäîáíûåâåùè â êîìïèëÿòîð, ìû ñòàíîâèìñÿ çàâèñèìûìè îò ìåòîäà ðåàëèçàöèè, êîòîðûé ìîæåò áûòü è íå îïòèìàëåí.Ñ òî÷êè çðåíèÿ ïðîñòûõ òèïîâ äàííûõ, áàçèñ ßÏ ïîñòîÿííî ðàñøèðÿåòñÿ (íà÷èíàÿ ñ íà÷àëà ðàçâèòèÿ ßÏ),ïðè ýòî ñ òî÷êè çðåíèÿ ñîñòàâíûõ òèïîâ, íî ïîñòåïåííî ñóæàåòñÿ.Ïóíêò 2. Ñ# åñòü êëàññû string è dictionary. Ïðè ýòîì êîìïèëÿòîð çíàåò ïðî êëàññ string (âûãëÿäèò êàê áèáëèîòå÷íûé êëàññ, íî âñòðîåí â êîìïèëÿòîð), à ïðî êëàññ dictionary îí íå çíàåò íè÷åãî (ïðîñòî áèáëèîòå÷íûéêëàññ).Ðàññìîòðèì ñîñòàâíûå òèïû äàííûõ.1.Ìàññèâû.Àáñòðàêöèÿ ïîñëåäîâàòåëüíîñòè îäíîòèïíûõ ýëåìåíòîâ.DxDxDxD ìàññèâ.Dn ìàññèâ êàê äåêàðòîâî ïðîèçâåäåíèå îäíîìåðíûõ òèïîâ äàííûõ.Ïðè ýòîì ýòà ïîñëåäîâàòåëüíîñòü äîëæíà ïðåäñòàâëÿòüñÿ â ïàìÿòè â âèäå íåïðåðûâíîé ïîñëåäîâàòåëüíîñòèýëåìåíòîâ.
Òàêàÿ íåïðåðûâíîñòü ðàñïîëîæåíèÿ â ïàìÿòè òðåáóåòñÿ äëÿ îïòèìèçàöèè äîñòóïà. Ñàìàÿ ðàñïðîñòðàíåííàÿ îïåðàöèÿ äëÿ ìàññèâîâ îïåðàöèÿ èíäåêñèðîâàíèÿ. Ñóùåñòâóåò 2 ñïîñîáà èçîáðàæåíèÿ ýòîéîïåðàöèè.1.A[i]2.A (i)Èíäåêñàöèÿ âîçâðàùàåò ññûëêó íà ñîîòâåòñòâóþùèé îáúåêò. Ñ# è java îáÿçàòåëüíà èíèöèàëèçàöèÿ ìàññèâà. Ê îïåðàöèè èíäåêñèðîâàíèÿ çà÷àñòóþ äîáàâëÿåòñÿíàáîð àòðèáóòîâ.Àòðèáóòû ìàññèâîâ:1.Àòðèáóòû âñåõ îáúåêòîâ äàííûõ (áàçîâûå àòðèáóòû ëþáîãî òèïà äàííûõ).2.Áàçîâûé òèï.3.Òèï èíäåêñà. Äîëæåí áûòü íåêîòîðîé íåïðåðûâíîé ïîñëåäîâàòåëüíîñòüþ çíà÷åíèé.
Ïðè ýòîì îïòèìàëåíäèñêðåòíûé òèï. Äèñêðåòíûé òèï òàêîé òèï äàííûõ, ÷òî äëÿ íåãî îïðåäåëåíû îïåðàöèè succ è pred, ïðè÷åìèõ ðàáîòà íà âñåõ àðõèòåêòóðàõ îïðåäåëåíà îäíîçíà÷íî.4.Ãðàíèöû / Äëèíà ìàññèâà.Êîãäà ìû çíàåì áàçîâûé òèï ìàññèâà è îí íåïðåðûâíî ðàñïîëîæåí â ïàìÿòè, òî êîìïèëÿòîð ìîæåòýôôåêòèâíî îïðåäåëèòü îïåðàöèþ èíäåêñèðîâàíèÿ.  ðÿäå ÿçûêîâ òèï èíäåêñà ôèêñèðóåòñÿ ñòàòè÷åñêè âîâðåìÿ òðàíñëÿöèè. Ïðèìåð ÿçûê Ïàñêàëü array [Index] of T. Òàê æå ïðîèñõîäèò â ÿçûêå Àäà.  ÿçûêåÑ íàïðèìåð, òàê æå êàê è âî ìíîãèõ ïîäîáíûõ ÿçûêàõ, òèï èíäåêñà âñåãäà integer. Èòàê òèï èíäåêñàôèêñèðóåòñÿ ñàìîå ïîçäíåå íà ýòàïå òðàíñëÿöèè. Ìàññèâ ýòî âñåãäà êîìïðîìèññ ìåæäó òðåìÿ âåùàìè íàäåæíîñòü, ýôôåêòèâíîñòü, ãèáêîñòü.
Ñ òî÷êè çðåíèÿ ýòèõ òðåáîâàíèé îïòèìàëüíûé âàðèàíò ìàññèâûèç ÿçûêà Àäà. Äâå êðàéíîñòè ìàññèâû â Ñ è â Ïàñêàëå. Ìåæäó íèìè Ìîäóëà -2 è Îáåðîí à òàê æå Ñ#è java. ßçûêå ïàñêàëü âñå àòðèáóòû ñòàòè÷åñêèå, ñëåäîâàòåëüíî îí íàäåæåí. Òî åñòü ïðè èíäåêñàöèè ïðîèçâîäèòñÿ ñòàòè÷åñêèé/êâàçèñòàòè÷åñêèé êîíòðîëü. Áîëåå òîãî âñå àòðèáóòû íå òîëüêî ñòàòè÷åñêèå, íî èÿâëÿþòñÿ àòðèáóòàìè òèïà.
Òàêàÿ ðåàëèçàöèÿ äàåò íàäåæíîñòü è ýôôåêòèâíîñòü, íî ñèëüíî âðåäèò ãèáêîñòè. Ïðè ýòîì Ïàñêàëü íå ãíàëñÿ çà ãèáêîñòüþ, òî åñòü äëÿ ñâîèõ íóæä îí áûë äîñòàòî÷íî ãèáîê. Ïðè ýòîìòåðÿåòñÿ òîëüêî óíèâåðñàëüíîñòü, â óãîäó ïðîñòîòå.ßçûê Ñ. Îðèåíòèðîâàí íå íà ãèáêîñòü èëè íàäåæíîñòü, íî íà ýôôåêòèâíîñòü. Ñ ýòîé òî÷êè çðåíèÿ,ïàñêàëü è Ñ îáà îðèåíòèðîâàííû íà ýôôåêòèâíîñòü, íî åñòü è ðàçëè÷èÿ. êà÷åñòâå òèïà èíäåêñà áåðåòñÿ25âñåãäà integer. Ôèêñèðóåòñÿ ëåâàÿ ãðàíèöà 0. Òèï ýëåìåíòà è äëèíà ÿâëÿþòñÿ ñòàòè÷åñêèìè àòðèáóòàìèòèïà. Òàèì îáðàçîì ìû íåìíîãî óìåíüøèëè ãèáêîñòü. Â Ñ àäðåñ íà÷àëà ìàññèâà è åãî ðàçìåð îäíîçíà÷íîîïðåäåëÿåò ìàññèâ.
Ïðè ýòîì äëèíà òðåáóåòñÿ òîëüêî äëÿ ðàñïðåäåëåíèÿ ïàìÿòè. Òî åñòü ÷àùå âñåãî ìàññèâçàäàåòñÿ àäðåñîì ñâîåãî íà÷àëà. Çàäàíèå èíäåêñà îò 0 ïîçâîëÿåò òàê æå ìàêñèìàëüíî ýôôåêòèâíî âû÷èñëÿòüàäðåñ ýëåìåíòà ïðè èíäåêñèðîâàíèè.Òî åñòü âñå ÷òî íóæíî ÷òîá îïåðèðîâàòü ñ ìàññèâîì ýòî àäðåñ åãî íà÷àëà == àäðåñ åãî ïåðâîãî ýëåìåíòà÷òî ÿâëÿåòñÿ D*. Ñëåäîâàòåëüíî ëþáîé ìàññèâ ñîïîñòàâèì ñ D*.Òî åñòü:int a[20];a[1] = *(a+1);Ïðè ýòîì íèêàêîãî êâàçèñòàòè÷åñêîãî êîíòðîëÿ âûïîëíåíî íå áóäåò.
Òàêèì îáðàçîì îáåñïå÷åíà ìàêñèìàëüíàÿ ýôôåêòèâíîñòü è íåêîòîðàÿ ãèáêîñòü ñòî÷êè çðåíèÿ óíèâåðñàëüíîñòè.×òî æå êàñàåòñÿ ÿçûêà Ìîäóëà-2, òî òàì òàê æå êàê è â ÿçûêå ïàñêàëü ôèêñèðóåòñÿ áàçîâûé òèï è òèïèíäåêñà. Ïðè ýòîì ïðîöåäóðû è ôóíêöèè ìîãóò èìåòü îñîáûé òèï äàííûõ îòêðûòûé ìàññèâ. Íàïðèìåð:procedure P(var A:T) ãäå T îòêðûòûé ìàññèâ.ARRAY OF TO. Òî åñòü ìû íå ôèêñèðóåì òèï èíäåêñà.Ïðîöåäóðà, âûäàþùàÿ ñóììó ýëåìåíòîâ ìàññèâà.PROCEDURE SUM (VAR A:ARRAY OF T):T;var R:T;BeginT:=A[0];for I:=1 to HIGH(A) DOR:=R+A[i];return R; end SUM;Ñ òî÷êè çðåíèÿ ýôôåêòèâíîñòè äîñòóïà, Ìîäóëà-2 îïòèìàëüíûé êîìïðîìèññ. ÿçûêå Îáåðîí îñòàëîñü ïîíÿòèå îòêðûòîãî ìàññèâà.
È ôèêñèðóåòñÿ òîëüêî áàçîâûé òèï ìàññèâà è åãîäëèíà.Type T = array N of D;Àíàëîãè÷íî D T[N];Ìàêñèìàëüíûé êîìïðîìèññ äîñòèãíóò â ÿçûêå Àäà. Ðàçíûå òèïû äàííûõ àáñîëþòíî íåñîâìåñòèìû ìåæäóñîáîé. Ïðè ýòîì ýëåìåíòû ïîäòèïîâ ïðèâîäèìû ê áàçîâîìó òèïó. Type TNew is new T [îãðàíè÷åíèå]. Òóòìîæåò áûòü îãðàíè÷åíèå äèàïàçîíà.  ìàññèâàõ åñòü ïîíÿòèÿ íåîãðàíè÷åííîãî ìàññèâà è îãðàíè÷åííîãîìàññèâà.  íåîãðàíè÷åííîì ôèêñèðóåòñÿ òîëüêî òèï äàííûõ è òèï èíäåêñà.Type arr is array (Index range<>) of D;Type limarr is array (Index range 1..N) of D; êà÷åñòâå èíäåêñíîãî áåðåòñÿ ëþáîé äèñêðåòíûé òèï äàííûõ.
Íåîãðàíè÷åííûå ìàññèâû ìîãóò áûòüôîðìàëüíûìè ïàðàìåòðàìè ïðîöåäóð è ôóíêöèé.X:limarr; íîðìàëüíî.X: arr; íåëüçÿ.Ïðè ýòîìZ:arr range 0..10 íîðìàëüíî.Z- ïîäòèï òèïà arr.W:arr range 1..11;U:arr range 0..11;Âñå ýòè ïåðåìåííûå ïðèíàäëåæàò ðàçíûì ïîäòèïàì îäíîãî è òîãî æå òèïà. Íåÿâíàÿ ñîâìåñòèìîñòü âñëó÷àå åñëè êîìïèëÿòîð ïðîâåðèò äèàïàçîí çíà÷åíèé.
Òðåáîâàíèå äëèíû ìàññèâîâ äîëæíû ñîâïàäàòü. ÒîåñòüZ:=W;W:=Z; ìîæíî.Íî Z:=U íàðóøåíèå âî âðåìÿ ïðîâåðêè íà ýòàïå êâàçèñòàòè÷åñêîãî êîíòðîëÿ.function SUM(A:arr) return D isR:D;beginfor i in A'RANGE loopR:=R+A(i);end loop;return R;end SUM;A'LENGTHA'RANGE26Ëåêöè 12.Êàê óæå ãîâîðèëîñü, íàèëó÷øåãî êîìïðîìèññà ìåæäó íàäåæíîñòüþ è ãèáêîñòüþ óäàëîñü äîñòè÷ü â ÿçûêåÀäà.
Ïîâòîðíîå îïèñàíèå ìàññèâîâ ÿçûêà Àäà (áûëî â ëåêöèè 11). Ïåðåïèøåì ïðèìåð ñ ïðîøëîé ëåêöèè.Åñëè â îáúÿâëåíèè ôóíêöèè ÿâíî óêàçàòü ïîëíîñòüþ îïðåäåëåííûé òèï ìàññèâà, òî òåðÿåòñÿ ñâîéñòâîãèáêîñòè. Ïîýòîìó ïèøåì òàê.function SUM (A:ARRUNL) return real;R:real:=0.0;beginfor i in A'RANGE loopR:=R+A(i);end loop;return R;end SUM;A'LENGTHA'FIRSTA'LASTA'RANGE <=> A'FIRST..A'LASTX:ARRUNL range 0..9;êîððåêòíîY:ARRUNL range -10..10;êîððåêòíîi:=SUM (X);êîððåêòíîj:=SUM (Y);êîððåêòíîÄëèíû ìàññèâîâ ìîãóò áûòü ëþáûìè.
Íî òðåáóåòñÿ ÷òîá òèï èíäåêñà è òèï ýëåìåíòîâ ìàññèâîâ ñîâïàäàëè.Äëÿ òîãî ÷òîáû èçáàâèòüñÿ îò ýòèõ îãðàíè÷åíèé íåîáõîäèìî èñïîëüçîâàòü íåêèé àíàëîã øàáëîíîâ (íàïðèìåðèõ àíàëîã â ÿçûêå Àäà).Ðàññìîòðèì ñîâðåìåííûå ÿçûêè ïðîãðàììèðîâàíèÿ Ñ#, Java, Delphi.
 Delphi åñòü âñå ÷òî áûëî âñòàíäàðòíîì Pascal ïëþñ, äîáàâèëèñü íåîãðàíè÷åííûå ìàññèâû. Ñîâðåìåííûé ïîäõîä ê èíäåêñàöèè òèïèíäåêñà âñåãäà int è íà÷èíàåòñÿ ñ 0. Äëèíà ÿâëÿåòñÿ ñâîéñòâîì íå òèïà, íî ýêçåìïëÿðà. Ìàññèâû îáúåêòû îñîáîãî òèïà, êîòîðûå âûâîäÿòñÿ èç íåêîòîðîãî êëàññà èëè ïîääåðæèâàþò íåêîòîðûé êëàññ/èíòåðôåéñ.Èòàê ñòèðàåòñÿ ðàçëè÷èå ìåæäó ìàññèâîì è îáúåêòîì.
Íî ïðè ýòîì ñîõðàíÿåòñÿ ñâîéñòâî íåïðåðûâíîñòèðàñïîëîæåíèÿ â ïàìÿòè.Îáúÿâëåíèå:T[] x;òåïåðü x ññûëêà íà ìàññèâ. Äëèíà ïðè ýòîì íå óêàçûâàåòñÿ.x = new T[len]; Äëèíà óêàçûâàåòñÿ êàê ñâîéñòâî êîíêðåòíîãî îáúåêòà.len íå îáÿçàíà áûòü êîíñòàíòîé. Ìåñòî ïîä ìàññèâ îòâîäèòñÿ â äèíàìè÷åñêîé ïàìÿòè. Ïðè ýòîì ìàññèâûâåäóò ñåáÿ êàê êëàññû îíè èìåþò íå ñâîéñòâà, à ìåòîäû è ïîääåðæèâàþò íåêîòîðûå ñòàíäàðòíûå ìåòîäûâñåõ êëàññîâ. Ïîñëå âûäåëåíèÿ ïàìÿòè ïîä ìàññèâ, ìû íå ìîæåì èçìåíèòü åãî äëèíó, ìû òîëüêî ìîæåìïðîèçâåñòè ïåðåðàñïðåäåëåíèå ïàìÿòè, òî åñòü âûäåëèòü ïàìÿòü ïîä íîâûé ìàññèâ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
