twolink.h

是一本教程的实例代码,可以下载后直接运行,即可以得到答案.

#include <iostream.h>
#include "TwolinkNode.h"               //双向链表的结点类
class Twolink                          //双向链表类
{
  public:
    TwolinkNode *head;                 //头指针
    Twolink(int n=0,bool single=false);//构造函数
    ~Twolink();                        //析构函数
    bool isEmpty()
    {
        return  head==NULL;
    }
    int length();                      //返回双向链表的长度
    TwolinkNode* index(int i)const;    //定位
    int get(int i)const;               //返回第i个数据元素值
    bool set(int i,int k);             //设置第i个数据元素值为k
    TwolinkNode* insert(TwolinkNode *p,int k);
                                       //k值插入作为p结点的后继结点
    TwolinkNode* insert_before(TwolinkNode *p,int k);
                                       //k值插入作为p结点的前驱结点
    void remove(TwolinkNode *p);       //删除p结点自己
    TwolinkNode* search(int k);        //查找，返回k值首次出现的结点
    void remove(int k);                //删除k值首次出现的结点
    void removeall(int k);             //删除所有值为k的结点
    void output();                     //输出双向链表 
};

Twolink::Twolink(int n,bool single)    //以n个自然数建立双向链表
{                                      //single=true时,构造单方向（指向后继）的双向链表
    head=NULL;                         //n=0时，构造空链表
    if(n>0)                            //构造非空链表    
    {
        int i=1;
        TwolinkNode *rear,*q;
        head=new TwolinkNode(i++);
        rear=head;
        while(i<=n)              
        {
            q=new TwolinkNode(i++);
            rear->next=q;              //q结点链入rear结点之后
            if(!single) q->prior=rear; //比单链表多加这一句 
            rear=q;                    //rear指向新的链尾结点
        }
    }
}

Twolink::~Twolink()                    //析构函数
{
    TwolinkNode *p=head,*q;
    while(p!=NULL)
    {
        q=p;
        p=p->next;                     //到达p的后继结点
        delete q;                      //释放q结点所占用的存储单元
    }
    head=NULL;
}

int Twolink::length()                  //返回双向链表的长度
{
    int i=0;
    TwolinkNode *p=head;
    while(p!=NULL)
    {
        i++;
        p=p->next;
    }
    return i;
}

TwolinkNode* Twolink::index(int i)const    //定位
{                //当0<i<=length()时，返回指向第i个结点的指针；否则返回NULL
    if(i<=0) return NULL;
    int j=0;
    TwolinkNode *p=head;
    while(p!=NULL && j<i)
    {
        j++;
        p=p->next;
    }
    return p;
}

int Twolink::get(int i)const           //返回第i个数据元素值
{
    TwolinkNode *p=index(i);           //定位，p指向第i个结点
    if(p!=NULL)
        return  p->data;
    else 
        return -32768;
}

bool Twolink::set(int i,int k)         //设置第i个数据元素值为k
{
    TwolinkNode *p=index(i);           //定位，p指向第i个结点
    if(p!=NULL)
    {
        p->data=k;
        return true;                   //操作成功
    }
    else
        return false;                  //操作失败
}

TwolinkNode* Twolink::insert(TwolinkNode *p,int k)
{                                      //k值插入作为p结点的后继结点
    TwolinkNode *q=new TwolinkNode(k); //创建k值结点q
    if(p==NULL)
        p=q;                           //空表插入
    else                               //表中、表尾插入
    {   
        q->prior=p;                    //将q插入在p结点之后
        q->next=p->next;
        p->next->prior=q;
        p->next=q;
    }
    return p;
}

TwolinkNode* Twolink::insert_before(TwolinkNode *p,int k)
{                                      //k值插入作为p结点的前驱结点
    TwolinkNode *q=new TwolinkNode(k); //创建k值结点q
    if(p==NULL)
        p=q;                           //空表插入
    else                               //表中、表尾插入
    {   
        q->prior=p->prior;             //将q插入在p结点之前
        q->next=p;
        p->prior->next=q;
        p->prior=q;
    }
    return p;
}

void Twolink::remove(TwolinkNode *p)   //删除p结点自己
{
    if(head!=NULL && p!=NULL)
    {
        if(p==head)
        {
            head=head->next;           //修改了头指针
            if(head!=NULL) 
                head->prior=NULL;
        } 
        else                           //p!=head
        {
            p->prior->next=p->next;    //p->prior!=NULL
            if(p->next!=NULL)
                p->next->prior=p->prior;
        }
        delete p;
    }
}

TwolinkNode* Twolink::search(int k)    //查找，返回k值首次出现的结点
{                                      //未找到时，返回NULL
    TwolinkNode *p=head;
    while(p!=NULL && p->data!=k)
        p=p->next;
    return p;
}

void Twolink::remove(int k)            //删除k值首次出现的结点
{
    if(!isEmpty())
    {
        TwolinkNode *p=search(k);      //返回k值首次出现的结点
        remove(p);                     //删除p结点自己
    }
    else
        cout<<"链表空，无法删除值！\n";
}

void Twolink::removeall(int k)         //删除所有值为k的结点
{
    if(!isEmpty())
    {
        TwolinkNode *p=search(k);      //返回k值首次出现的结点
        while(p!=NULL)
        {
            remove(p);                 //删除p结点自己
            p=search(k);
        }
    }
    else
        cout<<"链表空，无法删除值！\n";
}

void Twolink::output()                 //分别沿前驱和后继两个方向输出双向链表 
{
    cout<<"Twolink:  ";
    TwolinkNode *p=head;
    while(p->next!=NULL)
    {
        cout<<p->data<<" -> ";
        p=p->next;
    }
    cout<<p->data<<"\nPrior:    ";
    while(p!=NULL)
    {
        cout<<p->data<<" -> ";
        p=p->prior;
    }
    cout<<"\n";
}