danh sach lien ket

spinner.gif

#include<stdio.h> 

#include<conio.h> 

#include<iostream.h>

template<class T> 

class List 

protected: 

class node 

{ public: 

node(const T& data = T(), node* prev=0, node* next=0) 

: _data(data), _prev(prev), _next(next) 

{ if(_prev==0) _prev = this ; 

if(_next==0) _next = this ; 

T _data ; 

node* _prev , * _next ; 

}; 

node* _ ; 

int _size ; 

public: 

class Iterator 

{ friend class List ; 

public: 

Iterator(node* p) : _p(p) { } 

T& operator*() { return _p->_data; } 

void operator=(const Iterator& it) { _p = it._p; } 

int operator==(const Iterator& it) { return _p==it._p; } 

int operator!=(const Iterator& it) { return _p!=it._p; } 

Iterator operator++(int) 

{ Iterator it(_p); 

_p = _p->_next ; 

return it ; 

Iterator operator++() { _p=_p->_next; return *this;} 

Iterator operator--(int) 

{ Iterator it(_p); 

_p = _p->_prev ; 

return it ; 

Iterator operator--() { _p=_p->_prev; return *this;} 

// private: 

List<T>::node* _p ; 

}; 

List() ; 

~List() ; 

int size() const ; 

int empty() const ; 

T& front() const ; 

T& back() const ; 

Iterator begin() { return Iterator(_->_next);} 

Iterator end() { return Iterator(_->_prev);} 

void push_front(const T&) ; 

void push_back(const T&) ; 

void printList() ; 

void showList(); 

void clear() ; 

Iterator insert(Iterator& it, const T& x) 

{it._p->_prev = it._p->_prev->_next = new node(x, it._p->_prev, it._p); 

it._p = it._p->_prev ; ++_size ; 

return it ; } 

void insert(Iterator& it,int n,const T& x) 

{ node* p = it._p , * q = p->_prev ; 

for(int i=0; i<n; i++) 

p = p->_prev = new node(x,q,p) ; 

it._p = it._p->_prev = q->_next = p ; 

_size += n ; 

void erase(Iterator& it) 

{ if(_size==0) return ; 

node* p = it._p ; //temp *p 

p->_prev->_next = p->_next ; 

p->_next->_prev = p->_prev ; 

it._p = p->_next ; 

delete p ; 

--_size ; 

}

};

template<class T> 

List<T>::List() : _size(0) 

{ _ = new node() ; }

template<class T> 

List<T>::~List() 

{ node* p = _->_next ; 

while(p!= _ ) 

{ node* pp = p->_next ; 

delete p ; 

p = pp ; 

delete _ ; 

}

template<class T> 

int List<T>::size() const 

{ return _size ; }

template<class T> 

int List<T>::empty() const 

{ return (_size==0 ) ; }

template<class T> 

T& List<T>::front() const 

{ return _->_next->_data ; }

template<class T> 

T& List<T>::back() const 

{ return _->_prev->_data ; }

template<class T> 

void List<T>::push_front(const T& x) 

{ _->_next = _->_next->_prev = new node( x , _ , _->_next ) ; 

++_size ; 

}

template<class T> 

void List<T>::push_back(const T& x) 

{ _->_prev = _->_prev->_next = new node( x , _->_prev , _ ) ; 

++_size ; 

}

template<class T> 

void List<T>::printList() 

{ node* p = _->_next ; 

while(p!= _ ) 

{ cout<<p->_data<<" " ; 

p = p->_next ; 

}

template<class T> 

void List<T>::clear() 

{ node* p = _ , * q=p->_next ; 

while(q!=p) 

{ p->_next = q->_next ; 

q->_next->_prev = p ; 

delete q ; 

q = p->_next ; 

_size = 0 ; 

}

template<class T> 

void List<T>::showList() 

{ Iterator ip(_),it(_->_next) ; 

while(it!=ip) 

{ cout<<*(it)<<" "; 

++it; 

}

void main() 

List<int> lst ; 

clrscr() ; 

lst.push_front(3) ; lst.push_front(9) ; 

lst.push_back(8) ; lst.push_back(4) ; 

lst.printList() ; 

cout<<endl<<lst.front()<<" "<<lst.back() ; 

getch(); 

cout<<endl; 

lst.erase(lst.begin()) ; 

cout<<*(lst.begin())<<" "<<*(lst.end()) ; 

getch(); 

cout<<endl; 

lst.showList() ; 

getch() ; 

}

Comments & Reviews

Login or Facebook Sign in with Twitter
library_icon_grey.png Add share_icon_grey.png Share

Who's Reading

Recommended