: . , . , .
:
class Node{
public:
int d; //
Node *next; //
Node *prev; //
Node (int dat = 0){ //
d = dat; next = 0; prev = 0;
}
};
, ( List), (public). .
class List{
class Node{};
Node *pbeg, *pend; //
public:
List(){pbeg = 0; pend =0;} //
~List (); //
void add(int d); //
Node * find (int i); //
Node * insert (int key, int d); // d key:
bool remove (int key); //
void print(); //
void print_back(); //
};
add Node , :
void List::add(int d) {
Node *pv = new Node(d); //
if (pbeg == 0) pbeg = pend = pv; //
else {
// :
pv->prev = pend;
pend->next = pv;
pend = pv; } //
}
, , add_sort ( ).
find 0 :
Node * List::find(int d){
Node *pv = pbeg;
while (pv){
if (pv->d == d) break;
pv = pv->next;
}
return pv;
}
insert key . , 0:
Node * List::insert(int key, int d){
if(Node *pkey = find(key)){ // key
// :
Node *pv = new Node(d);
// :
pv->next = pkey->next;
// :
pv->prev = k;
// :
pkey->next = pv;
// :
if (k!= pend) (pv->next)->prev = pv;
// .
// :
else pend = pv;
return pv;
}
return 0;
}
remove true false, :
|
|
|
bool List::remove(int key){
if(Node *pkey = find(key)){
if (pkey == pbeg){ //
pbeg = pbeg->next;
pbeg->prev = 0;}
else if (pkey == pend){ //
pend = pend->prev;
pend->next - 0;}
else { //
(pkey->prev)->next = pkey->next;
(pkey->next)->prev = pkey->prev;}
delete pkey;
return true;
}
return false;
}
, :
void List::print (){
Node *pv = pbeg;
cout << endl << "1ist: ";
while (pv){
cout << pv->d << ' ';
pv = pv->next;}
cout << endl;
}
void List::print_back(){
Node *pv = pend;
cout << endl << "List back: ";
while (pv){
cout << pv->d << ' ';
pv = pv->prev;}
cout << endl;
}
- :
List::~List () {
if (pbeg!= 0){
Node *pv = pbeg;
while (pv){
pv = pv->next;
delete pbeg;
pbeg = pv;}
}
}
main, List: 5 , , , :
int main(){
List L;
for (int i = 2; i<6; i++) L.add(i);
L.print();
L.print_back();
L.insert(2, 200);
if (!L.remove(5)) cout << "not found";
L.print();
L.print_back(); }
2.11
. - , , .
. - . C++ .
, , .
:
( ).
List . , .
:
template <__> _;
. , . . class. , :
template <class Data> class List{
class Node{
public:
Data d;
Node *next;
Node *prev;
Node (Data dat = 0){d = dat; next = 0; prev = 0;}
};
}
Data . .
:
|
|
|
template <class > class myarray {/*..*/};
template <class K, class V, template <class T> class = myarray>
class Map{
C<K> key;
C<V> value;
};
, :
template <class , * p, class U = > class X { /*... */ };
. , :
template <__>
_ _ <_>::
_ (_ )
. .
template <class Data> void List<Data>::print()
{ / * */ }
<class Data> - , void , List , <Data> - , print .
<__> <_> :
template<class T1, class T2> struct A{
void f1 ();
};
template <class T2, class T1> void A<T2, T1>::f1() {... }
:
,
,
, ,
, ,
friend-.
: List.
template <class Data> class List{
class Node{
public:
Data d;
Node *next, *prev;
Node (Data dat = 0){d = dat; next = 0; prev = 0;}
};
Node *pbeg, *pend;
public:
List(){pbeg = 0; pend = 0;}
~List ();
void add(Data d);
Node * find(Data i);
Node * insert(Data key, Data d);
bool remove(Data key);
void print();
void print_back();
};
//--------------------------
template <class Data>
List <Data>::~List(){
if (pbeg!=0){
Node *pv = pbeg;
while (pv){
pv = pv->next;
delete pbeg;
pbeg = pv;
}
}
}
//-------------------------
template <class Data>
void List <Data>::print(){
Node *pv = pbeg;
cout << endl << "list: ";
while (pv){
cout << pv->d << ' ';
pv = pv->next;
}
cout << endl;
}
//---------------------------------
template <class Data>
void List <Data>::print_back(){
Node *pv = pend;
cout << endl << " list back: ";
while (pv){
cout << pv->d << ' ';
pv = pv->prev;
}
cout << endl;
}
//--------------------------
template <class Data>
void List <Data>::add(Data d){
Node *pv = new Node(d);
if (pbeg == 0) pbeg = pend = pv;
else{
pv->prev = pend;
pend->next = pv;
pend = pv;
}
}
//------------------------------
template <class Data>
Node * List <Data>::find(Data d){
Node *pv = pbeg;
while (pv){
if(pv->d == d) break;
pv = pv->next;
}
return pv;
}
//-----------------------------------
template <class Data>
Node * List <Data>::insert(Data key, Data d){
if(Node *pkey = find(key)){
Node *pv = new Node(d);
pv->next = pkey->next;
pv->prev = k;
pkey->next = pv;
if (k!= pend) (pv->next)->prev = pv;
else pend = pv;
return pv;
}
return 0;
}
// ---------------------------------
template <class Data>
bool List <Data>::remove(Data key){
if(Node *pkey = find(key)){
|
|
|
if (pkey == pbeg){
pbeg = pbeg->next;
pbeg->prev = 0;
}
else if (pkey == pend){
pend = pend->prev;
pend->next = 0;
}
else {
(pkey->prev)->next = pkey->next;
(pkey->next)->prev = pkey->prev;
}
delete pkey;
return true;
}
return false;
}
List , , , .
, , , . , .
: , :
template <class Type, int kol>
class Block{
public:
Block(){p = new Type [kol];}
~Block(){delete [] p;}
operator Type *();
protected:
Type * p;
}:
template <class Type, int kol>
Block <Type, kol>:: operator Type *(){
return p;
}
.
