#include <iostream>using namespace std;
class empty ...{ };
//sngly-linked list nodetemplate <class Elem> class Link ...{public: Elem element; //value for this node Link *next; Link(const Elem& elemval, Link * nextval =NULL) ...{element = elemval; next = nextval; } Link(Link* nextval = NULL) ...{ next = nextval; }};
//linked list implementationtemplate <class Elem> class LList: public Link<Elem> ...{private: Link<Elem>* head; Link<Elem>* tail; Link<Elem>* fence; int leftcnt; int rightcnt; void init()...{ fence = tail = head = new Link<Elem>; leftcnt = rightcnt = 0; }public: void removeall() ...{ while(head != NULL) ...{ fence = head; head = head->next; delete fence; } }
LList(int size = 10) ...{init(); } ~LList() ...{removeall();} void clear() ...{removeall();init(); } bool insert (const Elem&); bool append(const Elem&); bool remove(Elem&); void setStart() ...{ //cout<<"in setStart rightcnt="<<rightcnt<<";leftcnt="<<leftcnt<<endl; fence = head ; rightcnt += leftcnt; leftcnt = 0; //cout<<"at the end of setStart
rightcnt="<<rightcnt<<";leftcnt="<<leftcnt<<endl; } void setEnd() ...{ fence = tail; leftcnt +=rightcnt; rightcnt = 0; } void prev(); void next() ...{ if (fence != tail ) ...{ fence = fence->next; rightcnt--; leftcnt++; } } int leftLength() const ...{ return leftcnt; } int rightLength() const ...{ return rightcnt; } bool setPos (int pos); bool getValue(Elem& it) const...{ //let e = fence's element //cout<<"inLList out rightLength"<<rightLength()<<endl; //try if(rightLength() == 0) return false; it = fence->next->element; return true; } void print() const; };
template <class Elem>bool LList<Elem>::insert(const Elem& item) ...{ fence->next = new Link<Elem>(item, fence->next); if(tail == fence) tail = fence->next; rightcnt++; return true;}template <class Elem>bool LList<Elem>::append(const Elem& item) ...{ tail = tail->next = new Link<Elem>(item,NULL); rightcnt++; return true;}template <class Elem>bool LList<Elem>::remove(Elem& it) ...{ if(fence->next == NULL) return false; it = fence->next->element; Link<Elem>* ltemp = fence->next; fence->next = ltemp->next; if(tail == ltemp) tail = fence; delete ltemp; rightcnt--; return true; }template <class Elem> void LList<Elem>::prev() ...{ Link<Elem>* temp=head; if(fence == head) return; while(temp->next != fence) temp = temp->next; fence = temp; leftcnt--; rightcnt++; }template <class Elem> bool LList<Elem>::setPos(int pos) ...{ if((pos < 0) || (pos > rightcnt+leftcnt)) return false; fence = head; for(int i = 0; i<pos; i++) fence = fence->next; return true; }template <class Elem> void LList<Elem>::print() const ...{ Link<Elem>* temp = head; cout<<"< "; while(temp != fence)...{ cout<<temp->next->element<<" "; temp = temp->next; } cout<<"| "; while(temp->next != NULL) ...{ cout<<temp->next->element<<" "; temp = temp->next; } cout<<"> ";};
template <class Key ,class Elem>class Dictionary ...{public: virtual void clear()= 0; virtual bool insert(const Elem&) = 0; virtual bool remove(const Key&, Elem&) = 0; virtual bool removeAny(Elem&) = 0; virtual bool find(const Key&, Elem&) const =0; virtual int size() = 0;};
template <class Key ,class Elem>class LListDict: public Dictionary<Key,Elem> ...{public: LList<Elem>* list;public: LListDict( int size = 10 ) ...{ list = new LList<Elem>; } ~LListDict() ...{ list->removeall(); } void clear() ...{ list->clear(); } bool insert(const Elem& e) ...{ return list->append(e); } bool remove(const Key& K, Elem& e) ...{ for(list->setStart(); list->getValue(e); list->next() ) if(K == e)...{ list->remove(e);return true; } return false; } bool removeAny(Elem& e) ...{ if(size()==0)return false; list->setEnd(); list->prev(); list->remove(e); return true; } bool find(const Key& K,Elem& e)const ...{ //list->getValue(e); //cout<<"e="<<e; //cout<<"rightcnt="<<list->rightLength()<<endl; for(list->setStart(); list->getValue(e); list->next() ) ...{ //cout<<"k="<<K<<";e="<<e<<endl; if(K == e )return true; }//for return false; } int size() ...{ return list->leftLength()+list->rightLength(); }
};
int main()...{ LListDict<int, int>LDmanio; //add link for(int i = 0; i < 100; i++) LDmanio.insert(i); cout<<":::::::::::::::::::::::orginal list::::::::::::::::::::::::"<<endl; LDmanio.list->print(); //output the llist int K=23,e;
cout<<"find()="<<LDmanio.find(K,e)<<endl; //remove LDmanio.remove(K,e); cout<<":::::::::::::::::::::::remove done:::::::::::::::::::::::::"<<endl; LDmanio.list->print(); //output the llist //removeany LDmanio.removeAny(e); cout<<"::::::::::::::::::::::removeany done:::::::::::::::::::::::"<<endl; LDmanio.list->print(); //output the llist //size() cout<<"size()="<<LDmanio.size()<<endl; //clear() LDmanio.clear(); cout<<":::::::::::::::::::::::clear done:::::::::::::::::::::::::::"<<endl; LDmanio.list->print(); //output the llist
system("pause"); return 0;}
