推荐订阅源

#include <iostream>
using namespace std;

class empty {
      };

//sngly-linked list node
template <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 implementation
template <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<<">\n";
};




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;
}

元素的比较本来要用一个类来比较，我懒得写了，就用了==来比。要注意。