В.А. Серебряков, М.П. Галочкин и др. - Теория и реализация языков программирования (2006) (1134633), страница 24
Текст из файла (страница 24)
Êðîìå òîãî, ðàçëè÷íûå îáúåêòû â îäíîé èëè â ðàçíûõ îáëàñòÿõ âèäèìîñòè ìîãóò èìåòü îäèíàêîâûå èìåíà, è íåò áîëüøîãî ñìûñëà çàíèìàòü ïàìÿòüäëÿ ïîâòîðíîãî õðàíåíèÿ èäåíòèôèêàòîðà. Òàêèì îáðàçîì,óäîáíî èìÿ îáúåêòà è åãî îïèñàíèå õðàíèòü ïî îòäåëüíîñòè. ýòîì ñëó÷àå èäåíòèôèêàòîðû õðàíÿòñÿ â îòäåëüíîéòàáëèöå òàáëèöå èäåíòèôèêàòîðîâ.  òàáëèöå ñèìâîëîâ æå õðàíèòñÿ óêàçàòåëü íà ñîîòâåòñòâóþùèé âõîä â òàáëèöó èäåíòèôèêàòîðîâ. Òàáëèöó èäåíòèôèêàòîðîâ ìîæíîîðãàíèçîâàòü, íàïðèìåð, â âèäå ñïëîøíîãî ìàññèâà.
Èäåí-7.1. Òàáëèöû èäåíòèôèêàòîðîâBfyh[t_dlZ167HibkZgb_h[t_dlZV R U WDU H D GLÐèñ. 7.1.HibkZgb_h[t_dlZV R U W (26 D (26U H D G (26 L (26 Ðèñ. 7.2.òèôèêàòîð â ìàññèâå çàêàí÷èâàåòñÿ êàêèì-ëèáî ñïåöèàëüíûì ñèìâîëîì EOS (ðèñ. 7.2). Âòîðîé âîçìîæíûé âàðèàíò â êà÷åñòâå ïåðâîãî ñèìâîëà èäåíòèôèêàòîðà â ìàññèâ çàíîñèòñÿ åãî äëèíà.168Ãëàâà 7. Îðãàíèçàöèÿ òàáëèö ñèìâîëîâ7.2. Òàáëèöû ðàññòàíîâêèÎäíèì èç ýôôåêòèâíûõ ñïîñîáîâ îðãàíèçàöèè òàáëèöû ñèìâîëîâ ÿâëÿåòñÿ òàáëèöà ðàññòàíîâêè (èëè õåøòàáëèöà). Ïîèñê â òàêîé òàáëèöå ìîæåò áûòü îðãàíèçîâàíìåòîäîì ïîâòîðíîé ðàññòàíîâêè. Ñóòü åãî çàêëþ÷àåòñÿ âñëåäóþùåì.Òàáëèöà ñèìâîëîâ ïðåäñòàâëÿåò ñîáîé ìàññèâ ôèêñèðîâàííîãî ðàçìåðà N . Èäåíòèôèêàòîðû ìîãóò õðàíèòüñÿ êàêâ ñàìîé òàáëèöå ñèìâîëîâ, òàê è â îòäåëüíîé òàáëèöå èäåíòèôèêàòîðîâ.Îïðåäåëèì íåêîòîðóþ ôóíêöèþ h1 (ïåðâè÷íóþ ôóíêöèþ ðàññòàíîâêè), îïðåäåë¼ííóþ íà ìíîæåñòâå èäåíòèôèêàòîðîâ è ïðèíèìàþùóþ çíà÷åíèÿ îò 0 äî N − 1 (òî åñòü0 6 h1 (id) 6 N −1, ãäå id ñèìâîëüíîå ïðåäñòàâëåíèå èäåíòèôèêàòîðà).
Òàêèì îáðàçîì, ôóíêöèÿ ðàññòàíîâêè ñîïîñòàâëÿåò èäåíòèôèêàòîðó íåêîòîðûé àäðåñ â òàáëèöå ñèìâîëîâ.Ïóñòü ìû õîòèì íàéòè â òàáëèöå èäåíòèôèêàòîð id. Åñëè ýëåìåíò òàáëèöû ñ íîìåðîì h1 (id) íå çàïîëíåí, òî ýòîîçíà÷àåò, ÷òî èäåíòèôèêàòîðà â òàáëèöå íåò. Åñëè æå çàíÿò,òî ýòî åù¼ íå îçíà÷àåò, ÷òî èäåíòèôèêàòîð id â òàáëèöó çàíåñ¼í, ïîñêîëüêó (âîîáùå ãîâîðÿ) ìíîãî èäåíòèôèêàòîðîâìîãóò èìåòü îäíî è òî æå çíà÷åíèå ôóíêöèè ðàññòàíîâêè.Äëÿ òîãî ÷òîáû îïðåäåëèòü, íàøëè ëè ìû íóæíûé èäåíòèôèêàòîð, ñðàâíèâàåì id ñ ýëåìåíòîì òàáëèöû h1 (id). Åñëèîíè ðàâíû èäåíòèôèêàòîð íàéäåí, åñëè íåò íàäî ïðîäîëæàòü ïîèñê äàëüøå.Äëÿ ýòîãî âû÷èñëÿåòñÿ âòîðè÷íàÿ ôóíêöèÿ ðàññòàíîâêè h2 (h) (çíà÷åíèåì êîòîðîé îïÿòü òàêè ÿâëÿåòñÿíåêîòîðûé àäðåñ â òàáëèöå ñèìâîëîâ).
Âîçìîæíû ÷åòûðåâàðèàíòà: ýëåìåíò òàáëèöû íå çàïîëíåí (òî åñòü èäåíòèôèêàòîðà âòàáëèöå íåò), èäåíòèôèêàòîð ýëåìåíòà òàáëèöû ñîâïàäàåò ñ èñêîìûì(òî åñòü èäåíòèôèêàòîð íàéäåí), àäðåñ ýëåìåíòà ñîâïàäàåò ñ óæå ïðîñìîòðåííûì (òî åñòüòàáëèöà âñÿ ïðîñìîòðåíà è èäåíòèôèêàòîðà íåò)7.2. Òàáëèöû ðàññòàíîâêè169 ïðåäûäóùèå âàðèàíòû íå âûïîëíÿþòñÿ, òàê ÷òî íåîáõîäèìî ïðîäîëæàòü ïîèñê.Äëÿ ïðîäîëæåíèÿ ïîèñêà ïðèìåíÿåòñÿ ñëåäóþùàÿôóíêöèÿ ðàññòàíîâêè h3 (h2 ), h4 (h3 ) è ò.ä. Êàê ïðàâèëî,hi = h2 äëÿ i > 2. Àðãóìåíòîì ôóíêöèè h2 ÿâëÿåòñÿ öåëîå âäèàïàçîíå [0, N − 1] è îíà ìîæåò áûòü óñòðîåíà ïî-ðàçíîìó.Ïðèâåä¼ì òðè âàðèàíòà.1) h2 (i) = (i + 1) mod N .Áåð¼òñÿ ñëåäóþùèé (öèêëè÷åñêè) ýëåìåíò ìàññèâà.Ýòîò âàðèàíò ïëîõ òåì, ÷òî çàíÿòûå ýëåìåíòû ¾ãðóïïèðóþòñÿ¿, îáðàçóþò ïîñëåäîâàòåëüíûå çàíÿòûå ó÷àñòêè è âïðåäåëàõ ýòîãî ó÷àñòêà ïîèñê ñòàíîâèòñÿ ïî-ñóùåñòâó ëèíåéíûì.2) h2 (i) = (i + k) mod N , ãäå k è N âçàèìíî ïðîñòû.Ïî-ñóùåñòâó ýòî ïðåäûäóùèé âàðèàíò, íî ýëåìåíòû íàêàïëèâàþòñÿ íå â ïîñëåäîâàòåëüíûõ ýëåìåíòàõ, à ¾ðàçíîñÿòñÿ¿.3) h2 (i) = (a ∗ i + c) mod N ¾ïñåâäîñëó÷àéíàÿ ïîñëåäîâàòåëüíîñòü¿.Çäåñü c è N äîëæíû áûòü âçàèìíî ïðîñòû, b = a − 1êðàòíî p äëÿ ëþáîãî ïðîñòîãî p, ÿâëÿþùåãîñÿ äåëèòåëåìN , b êðàòíî 4, åñëè N êðàòíî 4 [6].Ïîèñê â òàáëèöå ðàññòàíîâêè ìîæíî îïèñàòü ñëåäóþùåéôóíêöèåé:void Search(String Id, boolean *Yes, int *Point){int H0=h1(Id), H=H0;while (1){if (Empty(H)==NULL){*Yes=false;*Point=H;return;}else if (IdComp(H,Id)==0){*Yes=true;*Point=H;return;}170}Ãëàâà 7.
Îðãàíèçàöèÿ òàáëèö ñèìâîëîâ}else H=h2(H);if (H==H0){*Yes=false;*Point=NULL;return;}Ôóíêöèÿ IdComp(H,Id) ñðàâíèâàåò ýëåìåíò òàáëèöû íàâõîäå H ñ èäåíòèôèêàòîðîì è âûðàáàòûâàåò 0, åñëè îíèðàâíû. Ôóíêöèÿ Empty(H) âûðàáàòûâàåò NULL, åñëè âõîäH ïóñò. Ôóíêöèÿ Search ïðèñâàèâàåò ïàðàìåòðàì Yes èPointer ñîîòâåòñòâåííî ñëåäóþùèå çíà÷åíèÿ :true, P åñëè íàøëè òðåáóåìûé èäåíòèôèêàòîð, ãäåP óêàçàòåëü íà ñîîòâåòñòâóþùèé ýòîìó èäåíòèôèêàòîðóâõîä â òàáëèöå,false, NULL åñëè èñêîìûé èäåíòèôèêàòîð íå íàéäåí,ïðè÷¼ì â òàáëèöå íåò ñâîáîäíîãî ìåñòà, èfalse, P åñëè èñêîìûé èäåíòèôèêàòîð íå íàéäåí, íîâ òàáëèöå åñòü ñâîáîäíûé âõîä P.Çàíåñåíèå ýëåìåíòà â òàáëèöó ìîæíî îñóùåñòâèòü ñëåäóþùåé ôóíêöèåé:int Insert(String Id){boolean Yes;int Point=-1;Search(Id,&Yes,&Point);if (!Yes && (Point!=NULL)) InsertId(Point,Id);return(Point);}Çäåñü ôóíêöèÿ InsertId(Point,Id) çàíîñèò èäåíòèôèêàòîð Id äëÿ âõîäà Point òàáëèöû.7.3.
Òàáëèöû ðàññòàíîâêè ñî ñïèñêàìè1717.3. Òàáëèöû ðàññòàíîâêè ñî ñïèñêàìèÒîëüêî ÷òî îïèñàííàÿ ñõåìà ñòðàäàåò îäíèì íåäîñòàòêîì âîçìîæíîñòüþ ïåðåïîëíåíèÿ òàáëèöû. Ðàññìîòðèìå¼ ìîäèôèêàöèþ, êîãäà âñå ýëåìåíòû, èìåþùèå îäèíàêîâîåçíà÷åíèÿ (ïåðâè÷íîé) ôóíêöèè ðàññòàíîâêè, ñâÿçûâàþòñÿâ ñïèñîê (ïðè ýòîì îòïàäàåò íåîáõîäèìîñòü èñïîëüçîâàíèÿôóíêöèé hi äëÿ i > 2). Òàáëèöà ðàññòàíîâêè ñî ñïèñêàìè ýòî ìàññèâ óêàçàòåëåé íà ñïèñêè ýëåìåíòîâ (ðèñ.
7.3).Âíà÷àëå òàáëèöà ðàññòàíîâêè ïóñòà (âñå ýëåìåíòû èìåþò çíà÷åíèå NULL). Ïðè ïîèñêå èäåíòèôèêàòîðà Id âû÷èñëÿåòñÿ ôóíêöèÿ ðàññòàíîâêè h(Id) è ïðîñìàòðèâàåòñÿ ñîîòâåòñòâóþùèé ëèíåéíûé ñïèñîê. Ïîèñê â òàáëèöå ìîæåòáûòü îïèñàí ñëåäóþùåé ôóíêöèåé:struct Element{String IdentP;struct Element * Next;};struct Element * T[N];struct Element * Search(String Id){struct Element * P;P=T[h(Id)];while (1){if (P==NULL) return(NULL);else if (IdComp(P->IdentP,Id)==0) return(P);else P=P->Next;}}Çàíåñåíèå ýëåìåíòà â òàáëèöó ìîæíî îñóùåñòâèòü ñëåäóþùåé ôóíêöèåé:struct Element * Insert(String Id){struct Element * P,H;172Ãëàâà 7. Îðãàíèçàöèÿ òàáëèö ñèìâîëîâOmdZaZl_evgZLGmdZaZl_evgZLGOmdZaZl_evgZLGOmdZaZl_evgZLGmdZaZl_evgZLGmdZaZl_evgZLG1Ðèñ.
7.3.+O3OÐèñ. 7.4.P=Search(Id);if (P!=NULL) return(P);else {H=H(Id);P=alloc(sizeof(struct Element));P->Next=T[H];7.4. Ôóíêöèè ðàññòàíîâêè}173T[H]=P;P->IdentP=Include(Id);}return(P);Ïðîöåäóðà Include çàíîñèò èäåíòèôèêàòîð â òàáëèöóèäåíòèôèêàòîðîâ. Àëãîðèòì èëëþñòðèðóåòñÿ ðèñ. 7.4.7.4.
Ôóíêöèè ðàññòàíîâêèÌíîãî âíèìàíèÿ èññëåäîâàòåëÿìè áûëî óäåëåíî òîìó, êàêîé äîëæíà áûòü (ïåðâè÷íàÿ) ôóíêöèÿ ðàññòàíîâêè.Îñíîâíûå òðåáîâàíèÿ ê íåé î÷åâèäíû: îíà äîëæíà ëåãêîâû÷èñëÿòüñÿ è ðàñïðåäåëÿòü ðàâíîìåðíî. Îäèí èç âîçìîæíûõ ïîäõîäîâ çäåñü çàêëþ÷àåòñÿ â ñëåäóþùåì.1. Ïî ñèìâîëàì ñòðîêè s îïðåäåëÿåì ïîëîæèòåëüíîå öåëîå H . Ïðåîáðàçîâàíèå îäèíî÷íûõ ñèìâîëîâ â öåëûå îáû÷íî ìîæíî ñäåëàòü ñðåäñòâàìè ÿçûêà ðåàëèçàöèè.  Ïàñêàëåäëÿ ýòîãî ñëóæèò ôóíêöèÿ ord, â Ñè ïðè âûïîëíåíèè àðèôìåòè÷åñêèõ îïåðàöèé ñèìâîëüíûå çíà÷åíèÿ òðàêòóþòñÿ êàêöåëûå.2.
Ïðåîáðàçóåì H , âû÷èñëåííîå âûøå, â íîìåð ýëåìåíòà,òî åñòü öåëîå ìåæäó 0 è N −1, ãäå N ðàçìåð òàáëèöû ðàññòàíîâêè, íàïðèìåð, âçÿòèåì îñòàòêà ïðè äåëåíèè H íà N .Ôóíêöèè ðàññòàíîâêè, ó÷èòûâàþùèå âñå ñèìâîëûñòðîêè, ðàñïðåäåëÿþò ëó÷øå, ÷åì ôóíêöèè, ó÷èòûâàþùèåòîëüêî íåñêîëüêî ñèìâîëîâ, íàïðèìåð, â êîíöå èëè ñåðåäèíåñòðîêè. Íî òàêèå ôóíêöèè òðåáóþò áîëüøå âû÷èñëåíèé.Ïðîñòåéøèé ñïîñîá âû÷èñëåíèÿ H ñëîæåíèå êîäîâñèìâîëîâ. Ïåðåä ñëîæåíèåì ñ î÷åðåäíûì ñèìâîëîì ìîæíîóìíîæèòü ñòàðîå çíà÷åíèå H íà êîíñòàíòó q .
Òî åñòü ïîëàãàåì H0 = 0, Hi = q ∗ Hi−1 + ci äëÿ 1 6 i 6 k , k äëèíàñòðîêè. Ïðè q = 1 ïîëó÷àåì ïðîñòîå ñëîæåíèå ñèìâîëîâ.Âìåñòî ñëîæåíèÿ ìîæíî âûïîëíÿòü ñëîæåíèå ci è q ∗ Hj−1ïî ìîäóëþ 2. Ïåðåïîëíåíèå ïðè âûïîëíåíèè àðèôìåòè÷åñêèõ îïåðàöèé ìîæíî èãíîðèðîâàòü.174Ãëàâà 7. Îðãàíèçàöèÿ òàáëèö ñèìâîëîâÔóíêöèÿ Hashpjw, ïðèâåä¼ííàÿ íèæå [3], âû÷èñëÿåòñÿ,íà÷èíàÿ ñ H = 0 (ïðåäïîëàãàåòñÿ, ÷òî èñïîëüçóþòñÿ 32áèòîâûå öåëûå). Äëÿ êàæäîãî ñèìâîëà c ñäâèãàåì áèòû Híà 4 ïîçèöèè âëåâî è äîáàâëÿåì î÷åðåäíîé ñèìâîë. Åñëèêàêîé-íèáóäü èç ÷åòûð¼õ ñòàðøèõ áèò H ðàâåí 1, ñäâèãàåìýòè 4 áèòà íà 24 ðàçðÿäà âïðàâî, çàòåì ñêëàäûâàåì ïî ìîäóëþ 2 ñ H è óñòàíàâëèâàåì â 0 êàæäûé èç ÷åòûð¼õ ñòàðøèõáèò, ðàâíûõ 1.#define PRIME 211#define EOS '\0'int Hashpjw(char *s){char *p;unsigned H=0, g;for (p=s; *p!=EOS; p=p+1){H=(H<<4)+(*p);if (g=H&0xf0000000){H=H^(g>>24);H=H^g;}}return H%PRIME;}7.5.
Òàáëèöû íà äåðåâüÿõÐàññìîòðèì åù¼ îäèí ñïîñîá îðãàíèçàöèè òàáëèö ñèìâîëîâ ñ èñïîëüçîâàíèåì äâîè÷íûõ äåðåâüåâ.Îðèåíòèðîâàííîå äåðåâî íàçûâàåòñÿ äâîè÷íûì, åñëè óíåãî â êàæäóþ âåðøèíó, êðîìå îäíîé (êîðíÿ), âõîäèò îäíà äóãà, è èç êàæäîé âåðøèíû âûõîäèò íå áîëåå äâóõ äóã.Âåòâüþ äåðåâà íàçûâàåòñÿ ïîääåðåâî, ñîñòîÿùåå èç íåêîòîðîé äóãè äàííîãî äåðåâà, å¼ íà÷àëüíîé è êîíå÷íîé âåðøèí, à òàêæå âñåõ âåðøèí è äóã, ëåæàùèõ íà âñåõ ïóòÿõ,âûõîäÿùèõ èç êîíå÷íîé âåðøèíû ýòîé äóãè.
Âûñîòîé äåðåâà íàçûâàåòñÿ ìàêñèìàëüíàÿ äëèíà ïóòè â ýòîì äåðåâåîò êîðíÿ äî ëèñòà.Ïóñòü íà ìíîæåñòâå èäåíòèôèêàòîðîâ çàäàí íåêîòîðûéëèíåéíûé (íàïðèìåð, ëåêñèêîãðàôè÷åñêèé) ïîðÿäîê ≺, òî7.5. Òàáëèöû íà äåðåâüÿõ175åñòü íåêîòîðîå òðàíçèòèâíîå, àíòèñèììåòðè÷íîå è àíòèðåôëåêñèâíîå îòíîøåíèå. Òàêèì îáðàçîì, äëÿ ïðîèçâîëüíîéïàðû èäåíòèôèêàòîðîâ id1 è id2 ëèáî id1 ≺ id2 , ëèáîid2 ≺ id1 , ëèáî id1 ñîâïàäàåò ñ id2 .73,GHQW3/HIW 5LJKWÐèñ. 7.5.Êàæäîé âåðøèíå äâîè÷íîãî äåðåâà, ïðåäñòàâëÿþùåãîòàáëèöó ñèìâîëîâ, ñîïîñòàâèì èäåíòèôèêàòîð. Ïðè ýòîì,åñëè âåðøèíà (êîòîðîé ñîïîñòàâëåí id) èìååò ëåâîãî ïîòîìêà (êîòîðîìó ñîïîñòàâëåí idL ), òî idL ≺ id; åñëè èìååòïðàâîãî ïîòîìêà (idR ), òî id ≺ idR .
Ýëåìåíò òàáëèöûèçîáðàæ¼í íà ðèñ. 7.5.Ïîèñê â òàêîé òàáëèöå ìîæåò áûòü îïèñàí ñëåäóþùåéôóíêöèåé:struct TreeElement * SearchTree(String Id,struct TreeElement * TP){int comp;if (TP==NULL) return NULL;comp=IdComp(Id,TP->IdentP);if (comp<0) return(SearchTree(Id,TP->Left));if (comp>0) return(SearchTree(Id,TP->Right));return TP;}ãäå ñòðóêòóðà äëÿ ýëåìåíòà äåðåâà èìååò âèästruct TreeElement{String IdentP;struct TreeElement * Left, * Right;};Çàíåñåíèå â òàáëèöó îñóùåñòâëÿåòñÿ ôóíêöèåé176Ãëàâà 7.
Îðãàíèçàöèÿ òàáëèö ñèìâîëîâstruct TreeElement * InsertTree(String Id,struct TreeElement * TP){int comp=IdComp(Id,TP->IdentP);if (comp<0) return(Fill(Id,TP->Left,&(TP->Left)));if (comp>0) return(Fill(Id,TP->Right,&(TP->Right)));return(TP);}struct TreeElement * Fill(String Id,struct TreeElement * P,struct TreeElement ** FP){ if (P==NULL){P=alloc(sizeof(struct TreeElement));P->IdentP=Include(Id);P->Left=NULL;P->Right=NULL;*FP=P;return(P);}else return(InsertTree(Id,P));}Êàê ïîêàçàíî â ðàáîòå [10], ñðåäíåå âðåìÿ ïîèñêà â òàáëèöå ðàçìåðà n, îðãàíèçîâàííîé â âèäå äâîè÷íîãî äåðåâà,ïðè ðàâíîé âåðîÿòíîñòè ïîÿâëåíèÿ êàæäîãî îáúåêòà ðàâíî (2 ln 2) log 2 n + O(1). Îäíàêî, íà ïðàêòèêå ñëó÷àé ðàâíîé âåðîÿòíîñòè ïîÿâëåíèÿ îáúåêòîâ âñòðå÷àåòñÿ äîâîëüíîðåäêî.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
