当前位置：首页 -> AI编程基础 -> c++编程基础

双向链表之C++实现(一)

2014-11-23 21:27:58 · 作者: · 浏览: 15
标签: 双向 实现
双向链表只是在单向链表的基础上增加了一条前向链，其中的很多处理方法都是相似的。比如
求链表长、寻找某一节点等。所有相似的部分就不一一实现了。有兴趣可以参考前面的博文。
以下我实现的双向链表(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

3、dll.cpp双链表类函数 

#include   
#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<






data<<" ";  
        ptrNode = ptrNode->next;  
    }  
    cout<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;  
        }  
    }  
}

4、mian.cpp测试文件 
#include   
#include "dll.h"  
using namespace std;  
  
int main()  
{  
    dll exp;  
  
    //构建链表并打印  
    exp.create();  
    exp.print();