|
Caìûé ïðîñòîé ñïîñîá ñâяçaòü ìíîæåñòâî ýëåìåíòîâ — ñäåëaòü òaê, ÷òîáû êaæ- äûé ýëåìåíò ñîäåðæaë ññûëêó ía ñëåäóþùèé. Òaêîé ñïèñîê íaçûâaåòñя îäíîía- ïðaâëåííûì (îäíîñâяçíûì). Åñëè äîáaâèòü â êaæäûé ýëåìåíò âòîðóþ ññûëêó — ía ïðåäûäóùèé ýëåìåíò, ïîëó÷èòñя äâóíaïðaâëåííûñ ñïèñîn (äâóñâяçíûñ), åñëè ïîñëåäíèé ýëåìåíò ñâяçaòü óêaçaòåëåì ñ ïåðâûì, ïîëó÷èòñя nîëüöåâîñ ñïèñîn.
Êaæäûé ýëåìåíò ñïèñêa ñîäåðæèò nëþ÷, èäåíòèôèöèðóþùèé ýòîò ýëåìåíò. Êëþ÷ îáû÷íî áûâaåò ëèáî öåëûì ÷èñëîì, ëèáî ñòðîêîé è яâëяåòñя ÷añòüþ ïîëя äaí- íûõ.  êa÷åñòâå êëþ÷a â ïðîöåññå ðaáîòû ñî ñïèñêîì ìîãóò âûñòóïaòü ðaçíûå
÷añòè ïîëя äaííûõ. Íaïðèìåð, åñëè ñîçäaåòñя ëèíåéíûé ñïèñîê èç çaïèñåé, ñî- äåðæaùèõ ôaìèëèþ, ãîä ðîæäåíèя, ñòaæ ðaáîòû è ïîë, ëþáaя ÷añòü çaïèñè ìî- æåò âûñòóïaòü â êa÷åñòâå êëþ÷a: ïðè óïîðяäî÷èâaíèè ñïèñêa ïî aëôaâèòó êëþ-
÷îì áóäåò ôaìèëèя, a ïðè ïîèñêå, ê ïðèìåðó, âåòåðaíîâ òðóäa êëþ÷îì áóäåò ñòaæ. Êëþ÷è ðaçíûõ ýëåìåíòîâ ñïèñêa ìîãóò ñîâïaäaòü.
Íaä ñïèñêaìè ìîæíî âûïîëíяòü ñëåäóþùèå îïåðaöèè:
ía÷aëüíîå ôîðìèðîâaíèå ñïèñêa (ñîçäaíèå ïåðâîãî ýëåìåíòa);
äîáaâëåíèå ýëåìåíòa â êîíåö ñïèñêa;
÷òåíèå ýëåìåíòa ñ çaäaííûì êëþ÷îì;
âñòaâêa ýëåìåíòa â çaäaííîå ìåñòî ñïèñêa (äî èëè ïîñëå ýëåìåíòa ñ çaäaííûì êëþ÷îì);
óäaëåíèå ýëåìåíòa ñ çaäaííûì êëþ÷îì;
óïîðяäî÷èâaíèå ñïèñêa ïî êëþ÷ó.
Ðaññìîòðèì äâóíaïðaâëåííûé ëèíåéíûé ñïèñîê. Äëя ôîðìèðîâaíèя ñïèñêa è ðaáîòû ñ íèì òðåáóåòñя èìåòü ïî êðaéíåé ìåðå îäèí óêaçaòåëü — ía ía÷aëî ñïèñ- êa. Óäîáíî çaâåñòè åùå îäèí óêaçaòåëü — ía êîíåö ñïèñêa. Äëя ïðîñòîòû äîïóñ- òèì, ÷òî ñïèñîê cîñòîèò èç öåëûõ ÷èñåë, òî åñòü îïèñaíèå ýëåìåíòa ñïèñêa âûãëя- äèò ñëåäóþùèì îáðaçîì:
struCt NOde{ int d;
NOde *next; NOde *prev;
};
Íèæå ïðèâåäåía ïðîãðaììa, êîòîðaя ôîðìèðóåò ñïèñîê èç 5 ÷èñåë, äîáaâëяåò
÷èñëî â ñïèñîê, óäaëяåò ÷èñëî èç ñïèñêa è âûâîäèò ñïèñîê ía ýêðaí. Óêaçaòåëü ía ía÷aëî ñïèñêa îáîçía÷åí pbeg, ía êîíåö ñïèñêa — pend, âñïîìîãaòåëüíûå óêaça- òåëè — pv è pkey.
inClude struCt NOde{
int d;
NOde *next;
NOde *prev;
};
//------------------------------------------------
NOde * first(int d);
vOid add(NOde **pend, int d);
NOde * find(NOde * COnst pbeg, int i);
bOOl remOve(NOde **pbeg, NOde **pend, int key);
NOde * insert(NOde * COnst pbeg, NOde **pend, int key, int d);
//------------------------------------------------
int main(){
NOde *pbeg = first(1); // Ôîðìèðîâaíèå ïåðâîãî ýëåìåíòa ñïèñêa NOde *pend = pbeg; // Cïèñîê çaêaí÷èâaåòñя, åäâa ía÷aâøèñü
// Äîáaâëåíèå â êîíåö ñïèñêa ÷åòûðåõ ýëåìåíòîâ 2, 3, 4, è 5: fOr (inti= 2; i<6; i++)add(&pend, i);
// Âñòaâêa ýëåìåíòa 200 ïîñëå ýëåìåíòa 2: insert(pbeg, &pend, 2, 200);
// Óäaëåíèå ýëåìåíòa 5:
if(!remOve (&pbeg, &pend, 5))COut << "íå íaéäåí"; NOde *pv= pbeg;
while (pv){ // âûâîä ñïèñêa ía ýêðaí COut << pv->d << ' ';
pv= pv->next;
}
return 0;
}
//------------------------------------------------
// Ôîðìèðîâaíèå ïåðâîãî ýëåìåíòa NOde * first(int d){
NOde *pv= new NOde;
pv->d = d; pv->next = 0; pv->prev = 0; return pv;
}
//------------------------------------------------
// Äîáaâëåíèå â êîíåö ñïèñêa vOid add(NOde **pend, int d){
NOde *pv= new NOde;
pv->d = d; pv->next = 0; pv->prev = *pend; (*pend)->next = pv;
*pend = pv;
}
//------------------------------------------------
// Ïîèñê ýëåìåíòa ïî êëþ÷ó
NOde * find(NOde * COnst pbeg, int d){ NOde *pv= pbeg;
while (pv){
if(pv->d == d)break; pv= pv->next;
}
return pv;
}
//------------------------------------------------
// Óäaëåíèå ýëåìåíòa
bOOl remOve(NOde **pbeg, NOde **pend, int key){
if(NOde *pkey = find(*pbeg, key)){ // 1 if (pkey == *pbeg){ // 2
*pbeg = (*pbeg)->next; (*pbeg)->prev= 0;}
else if (pkey == *pend){ // 3
*pend = (*pend)->prev; (*pend)->next = 0;}
else{ // 4
(pkey->prev)->next = pkey->next; (pkey->next)->prev= pkey->prev;}
delete pkey;
return true; // 5
}
return false; // 6
}
//------------------------------------------------
// Âñòaâêa ýëåìåíòa
NOde * insert(NOde * COnst pbeg, NOde **pend, int key, int d){ if(NOde *pkey = find(pbeg, key)){
NOde *pv= new NOde; pv->d = d;
// 1 - óñòaíîâëåíèå ñâяçè íîâîãî óçëa ñ ïîñëåäóþùèì: pv->next = pkey->next;
// 2 - óñòaíîâëåíèå ñâяçè íîâîãî óçëa ñ ïðåäûäóùèì: pv->prev = pkey;
// 3 - óñòaíîâëåíèå ñâяçè ïðåäûäóùåãî óçëa ñ íîâûì: pkey->next = pv;
// 4 - óñòaíîâëåíèå ñâяçè ïîñëåäóþùåãî óçëa ñ íîâûì: if( pkey != *pend) (pv->next)->prev = pv;
// Îáíîâëåíèå óêaçaòåëя ía êîíåö ñïèñêa,
// åñëè óçåë âñòaâëяåòñя â êîíåö: else *pend = pv;
return pv;
}
return 0;
}
Ðåçóëüòaò ðaáîòû ïðîãðaììû:
12 20034
Âñå ïaðaìåòðû, íå èçìåíяåìûå âíóòðè ôóíêöèé, äîëæíû ïåðåäaâaòüñя ñ ìîäè- ôèêaòîðîì COnst. Óêaçaòåëè, êîòîðûå ìîãóò èçìåíèòüñя (íaïðèìåð, ïðè óäaëå- íèè èç ñïèñêa ïîñëåäíåãî ýëåìåíòa óêaçaòåëü ía êîíåö ñïèñêa òðåáóåòñя ñêîð- ðåêòèðîâaòü), ïåðåäaþòñя ïî aäðåñó.
Ðaññìîòðèì ïîäðîáíåå ôóínöèþ óäaëåíèя ýëåìåíòa èç ñïèñna remOve. Åå ïaðaìåò- ðaìè яâëяþòñя óêaçaòåëè ía ía÷aëî è êîíåö ñïèñêa è êëþ÷ ýëåìåíòa, ïîäëåæaùå- ãî óäaëåíèþ.  ñòðîêå 1 âûäåëяåòñя ïaìяòü ïîä ëîêaëüíûé óêaçaòåëü pkey, êî- òîðîìó ïðèñâaèâaåòñя ðåçóëüòaò âûïîëíåíèя ôóíêöèè íaõîæäåíèя ýëåìåíòa ïî êëþ÷ó find. Ýòa ôóíêöèя âîçâðaùaåò óêaçaòåëü ía ýëåìåíò â ñëó÷aå óñïåøíîãî ïîèñêa è 0, åñëè ýëåìåíòa ñ òaêèì êëþ÷îì â ñïèñêå íåò. Åñëè pkey ïîëó÷aåò íåíó- ëåâîå çía÷åíèå, óñëîâèå â îïåðaòîðå if ñòaíîâèòñя èñòèííûì (ýëåìåíò ñóùåñòâó- åò), è óïðaâëåíèå ïåðåäaåòñя îïåðaòîðó 2, åñëè íåò — âûïîëíяåòñя âîçâðaò èç ôóíêöèè ñî çía÷åíèåì false (îïåðaòîð 6).
Óäaëåíèå èç ñïèñêa ïðîèñõîäèò ïî-ðaçíîìó â çaâèñèìîñòè îò òîãî, íaõîäèòñя ýëåìåíò â ía÷aëå ñïèñêa, â ñåðåäèíå èëè â êîíöå.  îïåðaòîðå 2 ïðîâåðяåòñя, ía- õîäèòñя ëè óäaëяåìûé ýëåìåíò â ía÷aëå ñïèñêa — â ýòîì ñëó÷aå ñëåäóåò ñêîððåê- òèðîâaòü óêaçaòåëü pbeg ía ía÷aëî ñïèñêa òaê, ÷òîáû îí óêaçûâaë ía ñëåäóþùèé ýëåìåíò â ñïèñêå, aäðåñ êîòîðîãî íaõîäèòñя â ïîëå next ïåðâîãî ýëåìåíòa. Íîâûé ía÷aëüíûé ýëåìåíò ñïèñêa äîëæåí èìåòü â ñâîåì ïîëå óêaçaòåëя ía ïðåäûäóùèé ýëåìåíò çía÷åíèå 0.
Åñëè óäaëяåìûé ýëåìåíò íaõîäèòñя â êîíöå ñïèñêa (îïåðaòîð 3), òðåáóåòñя ñìå- ñòèòü óêaçaòåëü pend êîíöa ñïèñêa ía ïðåäûäóùèé ýëåìåíò, aäðåñ êîòîðîãî ìîæ- íî ïîëó÷èòü èç ïîëя prev ïîñëåäíåãî ýëåìåíòa. Êðîìå òîãî, íóæíî îáíóëèòü äëя íîâîãî ïîñëåäíåãî ýëåìåíòa óêaçaòåëü ía ñëåäóþùèé ýëåìåíò. Åñëè óäaëåíèå ïðîèñõîäèò èç ñåðåäèíû ñïèñêa, òî åäèíñòâåííîå, ÷òî íaäî ñäåëaòü, — îáåñïå÷èòü äâóñòîðîííþþ ñâяçü ïðåäûäóùåãî è ïîñëåäóþùåãî ýëåìåíòîâ. Ïîñëå êîððåêòè- ðîâêè óêaçaòåëåé ïaìяòü èç-ïîä ýëåìåíòa îñâîáîæäaåòñя, è ôóíêöèя âîçâðaùaåò çía÷åíèå true.
Ðaáîòa ôóínöèè âñòaânè ýëåìåíòa â ñïèñîê ïðîèëëþñòðèðîâaía ía ðèñ. 3.2. Íî- ìåða îêîëî ñòðåëîê ñîîòâåòñòâóþò íîìåðaì îïåðaòîðîâ â êîììåíòaðèяõ.
Cîðòèðîâêa ñâяçaííîãî ñïèñêa çaêëþ÷aåòñя â èçìåíåíèè ñâяçåé ìåæäó ýëåìåíòa- ìè. Àëãîðèòì ñîñòîèò â òîì, ÷òî èñõîäíûé ñïèñîê ïðîñìaòðèâaåòñя, è êaæäûé ýëå- ìåíò âñòaâëяåòñя â íîâûé ñïèñîê ía ìåñòî, îïðåäåëяåìîå çía÷åíèåì åãî êëþ÷a.
pkey pkey->next
Do'stlaringiz bilan baham: |
