C++自己實現list

C++自己實現list

　　前兩個博客發表了自己寫的stack（棧）和queue（隊列），感覺比較簡單，今天想試著實現list，結果發現，不是那么容易，感覺自己對STL的底層不是很了解，

真要自己實現還真的很難，看STL的源代碼，那個暈啊...那代碼也寫得太難理解了，當然跟我不了解有關，但我相信，在將來的某一天我會懂的，你看我的代碼也會懂的。

　　話說：STL中的list的內部結構就是一個雙向鏈表，這個東東以前還真沒有玩過，就憑他用的是雙向鏈表我就不想用他，指針太多，耗資源，當然存在就有他的價值，

他能快速訪問其中的元素。 廢話總該少說，代碼就該多些。

　　有那么一點高興的是實現雙向鏈表的翻轉，其他的沒什么了，list還沒有實現，由于現在能力有限，新的版本一定會發布的，你就將就著看吧！

源碼

#include <iostream>
usingnamespace std;

template<typename T>
class list 
{
    public :
        list()
        {
            initialize();
        }

        list(int count)
        {
            initialize();
            if(count>0)
            {
                for(int i=0;i<count;i++)
                {
                    push_front(0);
                }
            }
        }

        list(int count,T data)
        {
            initialize();
            if(count>0)
            {
                for(int i=0;i<count;i++)
                {
                    push_front(data);
                }
            }
        }

        //顯示最后一個節點
        T& back()
        {
            checkEmpty();
            return cur->data;
        }

        T& back() const
        {
            return back();
        }

        //顯示第一個節點
        T& front()
        {
            checkEmpty();
            return head->next->data;
        }

        T& front() const
        {
            return front();
        }

        //彈出最后一個節點
void pop_back()
        {
            checkEmpty();
            cur=cur->prev;
            delete cur->next;
            cur->next=NULL;
            --len;
        }

        //彈出第一個節點
void pop_front()
        {
            checkEmpty();
            node* tmp=head->next;
            head->next=tmp->next;
            tmp->prev=head;
            delete tmp;
            --len;
        }

        //前插節點
void push_front(const T& t)
        {
            node* newNode=new node(t);
            head->next=newNode;
            newNode->prev=head;
            ++len;
        }

        //后插節點
void push_back(const T& t)
        {
            node* newNode=new node(t);
            newNode->prev=cur;
            cur->next=newNode;
            cur=newNode;
            ++len;
        }
 
        //刪除所有值為t的節點
void remove(const T& t)
        {
            checkEmpty();
            node* tmp=head->next;
            for(int i=0;i<len;i++)
            {
                if(tmp->data!=t)
                {
                    tmp=tmp->next;
                    continue;
                }
                 
                if(tmp->next==NULL)//刪除最后一個節點
                {
                    cur=tmp->prev; //將當前節點指向最后一個節點的前一個節點
                    cur->next=NULL;//由于保持當前節點指向最后一個節點，他的下一個節點當然為空
                }else//刪除中間節點
                {
                    tmp->prev->next=tmp->next; //要刪除節點的前一個節點的next指針指向要刪除節點的下一個節點
                    tmp->next->prev=tmp->prev; //要刪除節點的下一個節點的prev指針指向要刪除節點的前一個節點
                }
                --len;
                node* t=tmp->next;
                delete tmp;
                tmp=t;
            }
        }
 

         //反轉鏈表
         //每次都修改當前節點的前后節點指針
         //最后一個節點的下一個指針指向前一個節點
void reverse()
         {
            checkEmpty();
            
            node* prev = head;// 上一個節點
            node* pcur = head->next;//當前節點
            node* next;
            while (pcur !=NULL)
            {
                if(!pcur->next)
                {
                    pcur->next=prev;//最后一個節點的下一個節點指向前一個節點
break;
                }

                next = pcur->next; //下一個節點
                 
                pcur->next=prev;  //修改當前節點的下一個節點
                pcur->prev=next;  //修改當前及誒單的上一個節點

                prev=pcur;        //將當前節點設為上一個節點
                pcur=next;        //將下一個節點設為當前節點
            }
            cur=head->next;       //末節點指向頭節點
            head->next=pcur;      //頭指針指向當前節點，也就是指向翻轉之前的末節點
         }

         //排序
         //節點之間直接交換數據，而沒有用修改指針指向
void sort()
         {
             if(empty())
             {
                return;
             }
             node *p,*t;
             p=head->next;
             T d;
             while(p!=NULL)
             {
                 t=p;
                while(t!=NULL)
                {
                    if(p->data>t->data)
                    {
                        d=p->data;
                        p->data=t->data;
                        t->data=d;
                    }
                    t=t->next;
                }
                p=p->next;
             }
         }


        //鏈表元素個數
int size()
        {
            return len;
        }

        void resize(int count)
        {
            resize(count,0);
        }

        //重新設置元素
void resize(int count,T t)
        {
            if(count<0)
            {
                thrownew exception("元素的個數不能小于0!");
            }
            clear();  //內存是必須釋放的    
while(count--)
            {
                push_front(t);
            }
        }

        //清空集合
void clear()
        {
            if(empty())
            {
                return;
            }
            node *tmp=head;
            node *t=tmp->next;
            while(t!=NULL)
            {
                tmp=t;
                t=t->next;
                delete tmp;
            }
            tmp=NULL;
            t=NULL;

            cur=head;//當前節點指向頭指針
        }
 

        //鏈表是否為空
bool empty() const
        {
            return len==0;
        }

        //判斷鏈表是否為空
void checkEmpty()
        {
            if(empty())
            {
                thrownew exception("集合中沒有元素!");
            }
        }


    private :
        typedef struct node1
        {
            node1 *prev,*next;
            T  data;
            node1(T t):data(t),prev(NULL),next(NULL){}
        }node;

        node* head;//頭節點
        node* cur; //當前節點，指向末節點
int len;   //節點個數

        void initialize()
        {
            cur=head=new node(-1);
            len=0;
        }
};

作者：陳太漢

posted @ 2011-07-21 19:00 古文觀芷閱讀(8383) 評論(16) 收藏舉報

刷新頁面返回頂部

C++自己實現list

公告