44
Тізімнің әрбір элементінің оны анықтайтын кілті болады. Кілт не бүтін сан, не
тіркес, не мәлімет ӛрісінің белгілі бір бӛлігі болуы мүмкін. Мысалы, тізімді алфа-вит
бойынша орналастыру үшін кілт рӛлін фамилия атқарса, еңбек ардагерін анықтаудағы кілт
– стаж (жұмыс ӛтілі) бола алады.
Тізіммен келесі операцияларды орындауға болады:
• тізімнің бастапқы қалыптасуы (1-элементті жасау);
• тізімнің соңына элемент қосу;
• кілті берілген элементті оқу;
• элементті тізімнің берілген жеріне кірістіріп қою;
• кілті берілген элементті жою;
• кілт кӛмегімен тізімді реттеу.
Енді екі бағытты сызықтық тізімді қарастырайық.
Тізім жасау кезінде оның бас жағына бір нұсқауыш болуы тиіс. Екінші нұсқауыш –
сол тізім соңына сілте-ме ретінде жасайық. Тізім бүтін сандардан тұратын болсын деп
есептейміз. Оны құрылым ретінде келесі-дей түрде жазамыз:
struct Node{
int d;
Node *next;
Node *prev;
};
Тӛменде 5 саннан тұратын тізім жасалып, оған сан енгізіп және тізімнен санды алып
тастап, тізімді экранға шығаратын программа мәтіні келтірілген. Тізім басына нұсқауыш
pbeg деп аталған, ал тізім соңына нұсқауыш pend деп, қосымша нұсқауыштар 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); //Тізімнің 1-элементін қалыптастыру
Node *pend = pbeg; /* Тізім аяқталды, енді тізім соңына тӛрт элементті 2, 3, 4, 5
қосамыз:*/
for (int i = 2; i<6; i++) add(&pend, i);
// жаңа элементті (200) 2-элементтен соң енгізу:
insert(pbeg, &pend, 2, 200); // Енді 5-элементті ӛшіреміз:
if(!remove (&pbeg, &pend, 5)) cout << "табылмады";
Node *pv = pbeg;
while (pv){ // тізімді экранға шығару
cout << pv->d << ' ';
pv = pv->next;
}
return 0;
}
45
//----------------------------------------------------------
// Бірінші элементті қалыптастыру
Node * first(int d){
Node *pv = new Node;
pv->d = d; pv->next = 0; pv->prev = 0;
return pv;
}
//---------------------------------------------------------
// Тізім соңына қосу
void add(Node **pend, int d){
Node *pv = new Node;
pv->d = d; pv->next = 0; pv->prev = *pend;
(*pend) -> next = pv;
*pend = pv;
}
//--------------------------------------------------------
//----------------------------------------------------------
// Элементті кілт бойынша іздеу
Node * find(Node * const pbeg, int d){
Node *pv = pbeg;
while (pv){
if(pv->d == d)break;
pv = pv->next;
}
return pv;
}
//-----------------------------------------------------------------
// Элементті ӛшіру (жою)
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
}
//-----------------------------------------------------------------------
// Элементті енгізу (кірістіріп қою)
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 – жаңа түйінді келесі түйінмен байланыстыру:
pv->next = pkey->next;
// 2 - жаңа түйінді алдыңғы түйінмен байланыстыру:
46
pv->prev = pkey;
// 3 - алдыңғы түйінді жаңа түйінмен байланыстыру:
pkey->next = pv;
// 4 - келесі түйінді жаңа түйінмен байланыстыру:
if( pkey != *pend) (pv->next)->prev = pv;
// Егер түйін тізім соңына қойылатын болса,
// нұсқауышты тізім соңына қарай жаңалау :
else *pend = pv;
return pv;
}
return 0;
}
Программа жұмысының нәтижесі:
2. Стектер
Стек – бір бағытты тізімнің жеке бір түрі, оның тӛбесі болып сналатын бір шетінен
ғана элементті таңдап алуға және жаңа элементті қосуға болады. Стекпен басқа
операцияларды орындау қарасты-рылмаған.
Элементті таңдау кезінде ол элемент стектен алынып тасталынады. Стек LIFO (last
in – first out) ―соңынан кірді – бірінші шықты‖ қағидасына сүйенеді деп айтылады. Стекті
бір жақ шеті
жабық түтікше ретінде қарастырады. Оған бірнеше допты салсақ, оның біріншісін
алу үшін
үстіңгілерін түгел алу керек. Компьютер жадын-дағы стек сегменті осылай
құрылған. Келесі бетте 5 бүтін саннан құрылған стек келтірілген, оның элементтері
экранға шығарылады.
Мұнда стекке орналастыру – push-функциясы және стектен алу (таңдау) pop –
функциясы. Стекпен жұмыс істеуге арналған нұсқауыш оның тӛбесіне (top) сілтеме жасап
(нұсқап) тұрады.
Мысалы: стекке нӛмірленген шарларды салайық (1, 2, 3, 4, 5). Сол шарларды стектен
біртіндеп алып тастау керек (5, 4, 3, 2, 1).
#include
struct Node {
int d;
Node *p;
};
Node *first(int d);
void push(Node**top, int d);
int pop(Node**top);
//-------------------------------------------------------------
//------------------------------------------------------
int main(){
Достарыңызбен бөлісу: |
