, . C++.
( , .. ), new mall ( ). .
, , , . . , .
, , . .
, , , ( , ). , , . , , .
( struct), , , : . . : , .
:
struct Node{
Data d; // Data
Node *;
};
() , . () , . , .
, . , .
. , , , , , , . .
:
( );
|
|
;
;
( );
;
.
: 5 , , , . pbeg, pend, pv .
#include <iostream.h>
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); //
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;
}
//---------------------------
//
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 -
pv->prev = pkey;
// 3 -
pkey->next = pv;
// 4 -
if(k!= *pend)
(pv->next)->prev = pv;
// ,
else *pend = pv;
return pv;
}
return 0;
}
:
1 2 200 3 4
, , const. , . , .
|
|
remove.
. 1 , find. 0, . ( ), if 2, false ( 6).
- , . 2 , pbeg , , next . 0.
( 3), pend , prev . , . , . po - , true.
. 1.9. .
: (, ).
. , , , .
1.9
void add_sort (Node **pbeg, Node **pend, int d) {
Node *pv = new Node; //
pv->d = d;
Node * pt = *pbeg;
while (pt){ //
if (d < pt->d){ // (pt)
pv->next = pt;
if (pt == pbeg){ //
pv->prev = 0;
*pbeg = pv;
}
else { //
(pt->prev)->next = pv;
pv->prev = pt->prev;
}
pt->prev = pv;
return;
}
pt = pt->next;
}
pv->next = 0; //
pv->prev = *pend;
(*pend)->next = pv;
*pend = pv;
}
, , . . .
LIFO (last in first out, ). LIFO .
: (1,2, 3, 4, 5) . push, pop. (top) .
#include <iostream.h>
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 (int i = 2; i<6; i++) push(&top, i);
while (top)
cout << pop (&top) << ;
return 0;
}
//--------------------------
//
Node * first (int d){
Node *pv = new Node;
pv->d = d;
pv->p = 0;
|
|
return pv;
}
//--------------------------
//
void push(Node **top, int d){
Node *pv = new Node;
pv->d = d;
pv->p = *top;
*top = pv;
}
//--------------------------
//
int pop (Node **t){
int temp = (*top)->d;
Node *pv = *t;
*t = (*top)->p;
delete pv;
return temp;
}
:
5 4 3 2 1
, , . . .
FIFO (first in first out, ).
: . add, del, pbeg, pend.
#include <iostream.h>
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 (int i = 2; i<6; i++) add (&pend, i);
while (pbeg)
cout << del (&pbeg) << ;
return 0;
}
//-------------------------
//
Node * first (int d){
Node *pv = new Node;
pv->d = d;
pv->p = 0;
return pv;
}
//------------------------
//
void add(Node **pend, int d){
Node *pv = new Node;
pv->d = d;
pv->p = 0;
(*pend)->p = pv;
*pend = pv;
//------------------------
//
int del(Node **pbeg){
int temp = (*pbeg)->d;
Node *pv = *pbeg;
*pbeg = (*pbeg)->p;
delete pv;
return temp;
}
:
1 2 3 4 5
, , , , . . . , , . , . , .
1.10 .
1.10
, , . .
, . , , . , , .
, . .
:
,
,
,
.
, .
, .. . . , :
|
|
function way_around (){
way_around ( )
way_around ( )
}
(, , ), , , . , . 24.1: 1, 6, 8, 10, 20, 21, 25, 30.
, : 30, 25, 21, 20, 10, 8, 6, 1.
, . .
.
: . pv, pv prev. pnew .
. . , , . , .
, (prev) , , .
#include <iostream.h>
struct Node{
int d;
Node *left;
Node *right;
};
Node * first (int d);
Node * search_insert (Node *root, int d);
void print_tree (Node *root, int l);
//-----------------------
int main(){
int b[ ] = {10, 25, 20, 6, 21, 8, 1, 30};
Node *root = first(b[0]);
for (int i = 1; i < 8; i++) search_insert (root, b[i]);
print_tree (root, 0);
return 0;
}
//-----------------------
//
Node * first(int d){
Node *pv = new Node;
pv->d = d;
pv->left = 0;
pv->right = 0;
return pv;
}
//-----------------------
//
Node * search_insert (Node *root, int d) {
Node *pv = root, *prev;
bool found = false;
while (pv &&!found){
prev = pv;
if (d == pv->d) found = true;
else if (d < pv->d) pv = pv->left;
else pv = pv->right;
}
if (found) return pv;
//
Node *pnew = new Node;
pnew->d = d;
pnew->left = 0;
pnew->right = 0;
if (d < prev->d)
//
prev->left == pnew;
else
//
prev->right = pnew;
return pnew;
}
//--------------------------
//
void print_tree (Node *p, int level){
if (p){
print_tree (p->left, level +1); //
for (int i = 0; i < level; i++) cout << " ";
cout << p->d << endl; //
print_tree (p->right, level +1); //
}
}
, 1.10:
, , . 0.
, . , . , .
, , . , , . , . (, . 24.1 25, 21 30, 10 20 8, . .).