数据结构第四篇——线性表的链式存储之双向链表

♥注：未经博主同意，不得转载。

　　前面讨论的单链表，每个结点中只有一个指针域，用来存放指向后继结点的指针，因此，从某个结点出发只能顺时针往后查找其他结点。若要查找某个结点的直接前驱，则需要从头指针开始沿链表探寻，处理起来十分不方便。为克服单链表的这一缺点，可引入双向链表。

　　双向链表中每一个结点含有两个指针域，一个指针指向其直接前驱结点，另一个指针指向直接后继结点。和单链表类似，双向链表一般也只有头指针唯一确定；同样也可设头结点，使得双向链表的某些操作简便一些。

双向链表结构定义如下：

　　 双向链表是一种对称结构，和单链表相比，虽然每个结点增加了一个指针域，多占用了空间，但这给操作的实现带来了方便。

在双向链表中，若p为指向表中某一结点的指针，则显然有：

p->next->prior=p->prior->next=p

这个表达式恰当的反映了这种结构的特性。

在双向链表中，有些操作如取元素、求表长、定位等，只涉及一个方向的指针，则这些操作的算法描述和单链表相同。但在进行插入、删除操作时有很大的不同，在双向链表中需同时修改两个方向上的指针，还要小心修改顺序。

1.结点删除操作：

删除结点p时，先从头结点开始搜索链表，找到p后做以下操作：

p->prior->next=p->next;

if(p->next)

p->next->prior=p->prior;

整个完整删除函数为：

//删除操作
Data DBList::Delete(int i)
{
    DNode* p = head;
    int k=0;
    while(p&&k<i-1)                //将p指到要删除的位置
    {
        p=p->next;
        ++k;
    }
    if(!p||p->next==NULL)        //判断删除位置是否存在和是否有后继
    {
        cout<<"删除位置非法"<<endl;
        exit(0);
    }
    DNode* q = p->next;            //暂存删除结点
    
    p->prior->next=p->next;
    if(!p->next)
    p->next->prior=p->prior;
    
    Data e=q->data;                //将删除的元素储存起来
    delete q;                    //释放将要删除的结点
    return e;
}

2.结点插入操作：

在结点p之前插入结点s，先从头结点开始搜索链表，找到p后做以下操作：

s = new DNode;   //创建此结点

 s->data=e;     //将元素存入创建的结点
 s->prior=p->prior;
 p->prior->next=s;
 p->prior=s;
 s->next=p;

整个完整插入函数为：

//插入操作
void DBList::Insert(Data x,int i)
{
    DNode* p=head;
    int k=0;
    while(p&&k<i-1)            //    将p指到第i个位置
    {
        p=p->next;
        ++k;
    }
    if(!p||k>i-1)            //判断是否存在第i个元素
    {
        cout<<"第"<<i<<"个元素不存在"<<endl;
        exit(0);
    }
    DNode* s = new DNode;            //创建此结点
    if(!s)
    {
        cout<<"空间分配失败"<<endl;
        exit(0);
    }
    
    s->data=x;                    //将元素存入创建的结点
    s->prior=p->prior;
    p->prior->next=s; 
    p->prior=s;
    s->next=p;
}

3.创建双向链表：

typedef int Data;

struct DNode
{
    Data data;            //数据
    DNode* prior;        //指向前驱的指针 
    DNode* next;        //指向后继的指针 
};

class DBList
{
    DNode* head;                //创建头结点
    public:
    DBList()                //构造函数
    {
        head = new DNode;
        head->next = NULL;
        head->prior = NULL;
    }
    ~DBList();                        //析构函数
    
    Data GetElem(int i);                //取第i个元素的值
    bool IsEmpty();                        //判断是否为空链表
    void Create(Data* a , int n);        //创建长度为n的双链表(头插法)
    void Create1(Data* a , int n);        //创建长度为n的双链表(尾插法)
    DNode* Locate(Data e,int* i);        //查找值为e的结点，返回指向e的指针
    
    DNode* Prior(Data e);                //返回元素e的前驱 
    DNode* Prior1(int i);                //返回第i个元素的前驱 
    DNode* Next(Data e);                //返回元素e的后继 
    DNode* Next1(int i);                //返回第i个元素的后继
     
    void Insert(Data x,int i);            //将数据元素x插入到第i个位置
    Data Delete(int i);                    //删除第i个元素
    //int _Delete(Data e);                //删除值为e的第一个元素
    int Size();                            //返回链表的长度
    void Clear();                        //清空
    void Print();                        //正向显示元素
    void Print1();                        //逆向显示元素
};

这里是其他部分函数的实现：

//计算链表长度
int DBList::Size()
{
    DNode* p;            //创建指针p
    int k;
    p=head->next;                //p指向第一个元素结点 
    k=0;
    while(p)
    {
        p=p->next;
        ++k;
    }
    return k;
}

//正向显示所有元素
void DBList::Print()
{
    DNode* p;            //创建指针p
    p=head->next;            //p指向第一个元素结点 
    while(p)    
    {
        cout<<p->data<<" ";
        p=p->next;
    }
    cout<<endl;
}

//逆向显示所有元素
void DBList::Print1()
{
    DNode* p;            //创建指针p
    p=head->next;            //p指向第一个元素结点 
    while(p)
    {
        if(p->next)
        p=p->next;
        else
        break;
    }    
    
    while(p)    
    {
        cout<<p->data<<" ";
        p=p->prior;
    }
    cout<<endl;
}


//取元素
Data DBList::GetElem(int i)
{
    if(head->next == NULL)            //为空链表
    {
        cout<<"此链表为空"<<endl;
        exit(0);
    }
    else
    {
        DNode* p;            //创建指针p
        int k;
        p=head;                //p指向头结点
        k=0;
        while(p&&k<i)        //p移到i的位置
        {
            p=p->next;
            k++;
        }
        if(!p||k>i)            //超出个数范围
        {
            cout<<"第"<<i<<"个元素不存在"<<endl;
            exit(0);
        }
        return (p->data);
    }
}    //此算法的时间复杂度为O(n)

//判断链表是否为空 
bool DBList::IsEmpty()
{
    if(head->next==NULL)
    {
        cout<<"此链表为空"<<endl;
        return true;
    }
    else
    {
        cout<<"此链表非空"<<endl;
        return false;
    }
}

//建立双链表
//第一种是头插法
void DBList::Create(Data* a,int n)
{
    DNode* p=NULL;
    DNode* q=head;
    for(int i=n-1;i>=0;--i)
    {
        p=new DNode;                    //创建新结点
        p->data=a[i];                    //将元素存入结点
        
        q=p->prior;
        p->next=head->next;            //将新加入结点指向头结点后面
        head->next=p;                //将头结点指向新加入的结点
        q=p;
    }
}

//查找给定值的结点
DNode* DBList::Locate(Data e,int *i)
{
    *i=1;
    DNode* p=NULL;
    p=head->next;
    while(p)                        //p不为空
    {
        if(p->data==e)                //找到元素
            return p;
        else
        {
            p=p->next;
            ++(*i);
        }
    }
    cout<<"当前链表中无此元素"<<endl;
    exit(0);
    return NULL;
}

//清空双链表
//保留表头结点，把双链表中的
//其余所有结点全部释放。
void DBList::Clear()
{
    DNode* p=NULL;
    DNode* q=NULL;
    p=head->next;
    while(p)
    {
        q=p;
        p=p->next;
        delete q;
    }
    head->next = NULL;
    head->prior = NULL;
}

//析构函数
//释放双链表中的所有元素。
DBList::~DBList()
{
    DNode* p;
    p=head;
    while(p)
    {
        p=p->next;
        delete head;
        head=p;
    }
}

其他操作请参考上篇文章的部分内容：http://www.cnblogs.com/tenjl-exv/p/7470075.html

本次内容到这里就结束了。

v、