Задача этой книги дать краткое и четкое изложение языка С++ в соответствии со стандар том iso/iec 14882. Она предназначена для студентов, изучающих язык «с нуля»

Рис. 3.2. Вставка элемента в список

Íèæå ïðèâåäåía ôóínöèя ôîðìèðîâaíèя óïîðяäî÷åííîãî ñïèñna (ïðåäïîëaãaåòñя,

÷òî ïåðâûé ýëåìåíò ñóùåñòâóåò):
vOid add_sOrt(NOde **pbeg, NOde **pend, int d){ NOde *pv= new NOde; // äîáaâëяåìûé ýëåìåíò pv->d = d;
NOde * pt = *pbeg;
while (pt){ // ïðîñìîòð ñïèñêa
if (d < pt->d){ // çaíåñòè ïåðåä òåêóùèì ýëåìåíòîì (pt) pv->next = pt;
if (pt == *pbeg){ // â ía÷aëî ñïèñêa pv->prev = 0;
*pbeg = pv;}
else{ // â ñåðåäèíó ñïèñêa (pt->prev)->next = pv;
pv->prev = pt->prev;} pt->prev= pv;
return;
}
pt = pt->next;
}
pv->next = 0; // â êîíåö ñïèñêa pv->prev = *pend;
(*pend)->next = pv;
*pend = pv;
}

Стеки

Còåê — ýòî ÷añòíûé ñëó÷aé îäíîíaïðaâëåííîãî ñïèñêa, äîáaâëåíèå ýëåìåíòîâ â êîòîðûé è âûáîðêa èç êîòîðîãî âûïîëíяþòñя ñ îäíîãî êîíöa, íaçûâaåìîãî âåð- øèíîé ñòåêa. Äðóãèå îïåðaöèè ñî ñòåêîì íå îïðåäåëåíû. Ïðè âûáîðêå ýëåìåíò èñêëþ÷aåòñя èç ñòåêa. Ãîâîðяò, ÷òî ñòåê ðåaëèçóåò ïðèíöèï îáñëóæèâaíèя LIFO

(last in — first out, ïîñëåäíèì ïðèøåë — ïåðâûì óøåë). Còåê ïðîùå âñåãî ïðåä- ñòaâèòü ñåáå êaê çaêðûòóþ ñ îäíîãî êîíöa óçêóþ òðóáó, â êîòîðóþ áðîñaþò ìя÷è. Äîñòaòü ïåðâûé áðîøåííûé ìя÷ ìîæíî òîëüêî ïîñëå òîãî, êaê âûíóòû âñå îñòaëüíûå. Êñòaòè, ñåãìåíò ñòåêa íaçâaí òaê èìåííî ïîòîìó, ÷òî ïaìяòü ïîä ëî- êaëüíûå ïåðåìåííûå âûäåëяåòñя ïî ïðèíöèïó LIFO. Còåêè øèðîêî ïðèìåíяþò- ñя â ñèñòåìíîì ïðîãðaììíîì îáåñïå÷åíèè, êîìïèëяòîðaõ, â ðaçëè÷íûõ ðåêóð- ñèâíûõ aëãîðèòìaõ.

Íèæå ïðèâåäåía ïðîãðaììa, êîòîðaя ôîðìèðóåò ñòåê èç ïяòè öåëûõ ÷èñåë (1, 2, 3, 4, 5) è âûâîäèò åãî ía ýêðaí. Ôóíêöèя ïîìåùåíèя â ñòåê ïî òðaäèöèè íaçûâa- åòñя push, a âûáîðêè — pOp. Óêaçaòåëü äëя ðaáîòû ñî ñòåêîì (tOp) âñåãäa ññûëaåò- ñя ía åãî âåðøèíó.
inClude struCt NOde{
int d;
NOde *p;
};
NOde * first(int d);
vOid push(NOde **tOp, int d); int pOp(NOde **tOp);
//------------------------------------------------
int main(){
NOde *tOp = first(1);
fOr (inti= 2; i<6; i++)push(&tOp, i); while (tOp)
COut << pOp(&tOp) << ' '; return 0;
}
//------------------------------------------------
// Ía÷aëüíîå ôîðìèðîâaíèå ñòåêa NOde * first(int d){
NOde *pv= new NOde; pv->d = d;
pv->p = 0; return pv;
}
//------------------------------------------------
// Çaíåñåíèå â ñòåê
vOid push(NOde **tOp, int d){ NOde *pv= new NOde;
pv->d = d;
pv->p = *tOp;
*tOp = pv;
}
//------------------------------------------------
// Âûáîðêa èç ñòåêa int pOp(NOde **tOp){

int temp = (*tOp)->d; NOde *pv= *tOp;

*tOp = (*tOp)->p; delete pv;
return temp;
}
Ðåçóëüòaò ðaáîòû ïðîãðaììû:
54321

Очереди

Î÷åðåäü — ýòî ÷añòíûé ñëó÷aé îäíîíaïðaâëåííîãî ñïèñêa, äîáaâëåíèå ýëåìåíòîâ â êîòîðûé âûïîëíяåòñя â îäèí êîíåö, a âûáîðêa — èç äðóãîãî êîíöa. Äðóãèå îïå- ðaöèè ñ î÷åðåäüþ íå îïðåäåëåíû. Ïðè âûáîðêå ýëåìåíò èñêëþ÷aåòñя èç î÷åðåäè. Ãîâîðяò, ÷òî î÷åðåäü ðåaëèçóåò ïðèíöèï îáñëóæèâaíèя FIFO (first in — first out, ïåðâûì ïðèøåë — ïåðâûì óøåë). Î÷åðåäü ïðîùå âñåãî ïðåäñòaâèòü ñåáå, ïîñòîяâ â íåé ÷añ-äðóãîé.  ïðîãðaììèðîâaíèè î÷åðåäè ïðèìåíяþòñя, íaïðèìåð, â ìî- äåëèðîâaíèè, äèñïåò÷åðèçaöèè çaäa÷ îïåðaöèîííîé ñèñòåìîé, áóôåðèçîâaííîì ââîäå/âûâîäå.
Íèæå ïðèâåäåía ïðîãðaììa, êîòîðaя ôîðìèðóåò î÷åðåäü èç ïяòè öåëûõ ÷èñåë è âûâîäèò åe ía ýêðaí. Ôóíêöèя ïîìåùåíèя â êîíåö î÷åðåäè íaçûâaåòñя add, a âû- áîðêè — del. Óêaçaòåëü ía ía÷aëî î÷åðåäè íaçûâaåòñя pbeg, óêaçaòåëü ía êîíåö — pend.
inClude struCt NOde{
int d;
NOde *p;
};
NOde * first(int d);
vOid add(NOde **pend, int d); int del(NOde **pbeg);
//------------------------------------------------
int main(){
NOde *pbeg = first(1); NOde *pend = pbeg;
fOr (inti= 2; i<6; i++)add(&pend, i); while (pbeg)
COut << del(&pbeg) << ' '; return 0;
}
//------------------------------------------------
// Ía÷aëüíîå ôîðìèðîâaíèå î÷åðåäè NOde * first(int d){
NOde *pv= new NOde; pv->d = d;
pv->p = 0;

return pv;

}
//------------------------------------------------
// Äîáaâëåíèå â êîíåö
vOid add(NOde **pend, int d){ NOde *pv= new NOde;
pv->d = d; pv->p = 0;
(*pend)->p = pv;
*pend = pv;
}
//------------------------------------------------
// Âûáîðêa
int del(NOde **pbeg){
int temp = (*pbeg)->d; NOde *pv= *pbeg;
*pbeg = (*pbeg)->p; delete pv;
return temp;
}
Ðåçóëüòaò ðaáîòû ïðîãðaììû:
12345