雙向鏈表之C++實現

 雙向鏈表只是在單向鏈表的基礎上增加了一條前向鏈，其中的很多處理方法都是相似的。比如   求鏈表長、尋找某一節點等。所有相似的部分就不一一實現了。有興趣可以參考前面的博文。          以下我實現的雙向鏈表(VC6下實現)。錯誤之處還請指正。   1、代碼組織         2、dll.h雙鏈表及節點的說明    

#ifndef _DLL_H_  
#define _DLL_H_  
  
#define dataType int  
#define endOfData 0  
  
class node  
{  
public:  
    dataType data;    //節點數據  
    node *next;       //後向指針(離尾節點近)  
    node *pre;        //前向指針(離head近)  
};  
  
class dll  
{  
public:  
    dll();  
    ~dll();  
    void create();                      //構造雙向鏈表  
    void print();                       //打印鏈表  
    bool insert(int pos,dataType num);  //在位置pos插入num節點.插入完成返回true,否則返回false  
    void del(dataType num);             //刪除鏈表中所有的num節點  
  
private:  
    int getLength();                    //獲取鏈表包含的節點數目  
    node *head;                         //鏈表頭指針  
};  
  
#endif  

#include <iostream>  
#include "dll.h"  
using namespace std;  
  
dll::dll()  
{  
    head = NULL;  
}  
  
dll::~dll()  
{  
    node *ptrNode = head;  
    node *ptrNodeTmp = NULL;  
  
    while(ptrNode != NULL)  
    {  
        ptrNodeTmp =ptrNode->next;  
        delete ptrNode;  
        ptrNode = ptrNodeTmp;  
    }  
}  
  
void dll::create()  
{  
    //第一個節點  
    node *ptrNode = new node;  
    ptrNode->pre = NULL;  
    ptrNode->data = endOfData;  
    head = ptrNode;  
  
    bool firstNode = true;      //是否是第一個節點  
    dataType num = endOfData;  
  
    while(1)  
    {  
        cout<<"請輸入一個節點數據: ";  
        cin>>num;  
  
        if(num == endOfData)  
        {  
            ptrNode->next = NULL;  
            break;  
        }  
  
        if(firstNode == false)         //以後的節點都需要new node  
        {  
            node *ptrNodeTmp = new node;  
            ptrNodeTmp->data = num;  
            ptrNode->next = ptrNodeTmp;  
            ptrNodeTmp->pre = ptrNode;  
            ptrNode = ptrNodeTmp;  
        }  
  
        if(firstNode == true)         //第一個不需要new node  
        {  
            ptrNode->data = num;  
            firstNode = false;  
        }  
    }  
  
    if(head->data == endOfData)       //鏈表中並無數據,需要將第一個節點刪除  
    {  
        delete head;  
        head = NULL;  
    }  
}  
  
void dll::print()  
{  
    node *ptrNode = head;  
  
    while(ptrNode != NULL)  
    {  
        cout<<ptrNode->data<<" ";  
        ptrNode = ptrNode->next;  
    }  
    cout<<endl;  
}  
  
int dll::getLength()  
{  
    node *ptrNode = head;  
    int num = 0;  
  
    while(ptrNode != NULL)  
    {  
        num++;  
        ptrNode = ptrNode->next;  
    }  
  
    return num;  
}  
  
bool dll::insert(int pos,dataType num)  
{  
    if(pos < 0 || pos >= getLength())   //插入的pos不正確(0-getLength()-1)  
    {  
        return false;  
    }  
  
    //找到待插入pos的指針和後一個指針  
    node *ptrNodeAhead = head;  
    node *ptrNodeFellow = NULL;  
    int count = 0;  
    while(1)  
    {  
        if(count++ == pos) break;  
  
        ptrNodeFellow = ptrNodeAhead;  
        ptrNodeAhead = ptrNodeAhead->next;  
    }  
  
    node *ptr = new node;  
    ptr->data = num;  
    ptr->pre = ptrNodeFellow;  
    ptr->next = ptrNodeAhead;  
    if(ptrNodeFellow != NULL)      //不是插入頭節點  
    {  
        ptrNodeFellow->next = ptr;  
    }  
    else                           //插入頭節點,head要改變  
    {  
        head = ptr;  
    }  
    ptrNodeAhead->pre = ptr;  
  
    return true;  
}  
  
void dll::del(dataType num)  
{  
    node *ptrNodeAhead = head;    //ptrNodeAhead指向待刪除的節點  
    node *ptrNodeFellow = NULL;   //ptrNodeFellow指向待刪除節點的前一節點(離head近的節點)  
  
    while(ptrNodeAhead != NULL)  
    {  
        while(ptrNodeAhead->data != num && ptrNodeAhead->next != NULL)  //找到num節點或是搜索結束  
        {  
            ptrNodeFellow = ptrNodeAhead;  
            ptrNodeAhead = ptrNodeAhead->next;  
        }  
  
        if(ptrNodeAhead->data == num)          //找到num節點  
        {  
            node *ptrNode = ptrNodeAhead->next;  
              
            if(ptrNodeAhead != head)            //不是刪除頭節點  
            {  
                ptrNodeFellow->next = ptrNode;  
            }  
            else                                //刪除頭結點要注意head指針的賦值  
            {  
                head = ptrNodeAhead->next;  
            }  
            if(ptrNodeAhead->next != NULL)       //不是刪除尾節點  
            {  
                ptrNode->pre = ptrNodeFellow;  
            }  
  
            delete ptrNodeAhead;                 //釋放num節點  
  
            ptrNodeAhead = ptrNode;  
        }  
        else                                     //搜索結束  
        {  
            ptrNodeAhead = NULL;  
        }  
    }  
}  

#include <iostream>  
#include "dll.h"  
using namespace std;  
  
int main()  
{  
    dll exp;  
  
    //構建鏈表並打印  
    exp.create();  
    exp.print();  
  
    //在位置2插入99999並打印  
    exp.insert(2,99999);  
    exp.print();  
      
    //刪除位置2的節點並打印  
    exp.del(2);  
    exp.print();  
  
    return 0;  
}