首页 > > 程序设计 > C/C++ >

C++编写双向链表

2018-08-02 05:44:02来源：博客园阅读 ()

创建双向链表类，该类有默认构造函数、类的拷贝函数、类的、实现链表添加数据、升序排序、查找链表中某个节点及删除链表中某个节点的操作

代码实现：

#include<iostream>
#include<string.h>
using namespace std;

typedef int ElemData;

struct node{ //节点类
    ElemData data;
    node *next;
    node *prev;
};

class LinkList //双向链表类
{
    public:
        node *head;//指向头结点
        node *tail;//指向尾节点
        int len;//链表长度
    public:
        LinkList();//构造函数
        LinkList(const LinkList &l);//拷贝函数
        ~LinkList();//析构函数
        void addNode(ElemData data);//往尾部添加元素
        void upSort();//升序排序
        void findNode(int n);//查找某个节点
        void delNode(int n);//删除某个节点
        void showNode();//输出所有节点数据
};

LinkList::LinkList()
{
    head = NULL;
    tail = NULL;
    len = 0;
}

LinkList::LinkList(const LinkList &l)
{
    if(l.head!=NULL)
    {
        node *pHc = l.head;
        head = new node();//为节点申请空间
        head->data = pHc->data;
        len++;
        pHc = pHc->next;
        node *pH = head;
        while(pHc!=l.tail)
        {
            pH->next = new node();
            len++;
            pH->data = pHc->data;
            pHc = pHc->next;
        }
    }
    else
    {
        head=tail=NULL;
        len = 0;
    }
}
LinkList::~LinkList()
{
    node *bgn = head;
    while(head!=tail)
    {
        head = head->next;
        delete bgn;//释放内存
        bgn = head;
    }
    len = 0;
}

void LinkList::addNode(ElemData data)
{
    if(head==NULL)
    {
        head = new node();
        head->data = data;
        len++;
        tail = head;
    }
    else
    {
        tail->next = new node();
        tail->next->data = data;
        len++;
        tail->next->prev = tail;
        tail = tail -> next;
    }
}

void LinkList::showNode()
{
    node *p;
    p=head;
    if(p==NULL)
        cout<<"List id empty"<<endl;
    else
    {
        while(p!=tail->next)
        {
            cout<<p->data<<" ";
            p = p ->next;
        }
        cout<<endl;
    }
}

void LinkList::upSort()
{
    node *p,*q;
    ElemData temp;
    for(p=head;p!=tail->next;p=p->next)
    {
        for(q=p->next;q!=tail->next;q=q->next)
        {
            if(p->data>q->data)
            {
                temp = p->data;
                p->data = q->data;
                q->data = temp;
            }
        }
    }
}
void LinkList::findNode(int n)
{
    node *p;
    p = head;
    if(n>len)
        cout<<"超出链表长度";
    else
    {
        for(int i=1;i<n;i++)
        {
            p = p->next;
        }
        cout<<"该节点是:"<<p->data<<endl;
    }
}
void LinkList::delNode(int n)
{
    node *p,*q;
    p = head;
    q = head->next;
    if(n>len)
        cout<<"超出链表长度";
    else
    {
        for(int i=2;i<n;i++)
        {
            p = p->next;
            q = q->next;
        }
        p->next = q->next;
        q->next->prev = p;
        delete q;
    }
}

int main()
{
    int n;
    LinkList lin;
    cout<<"插入节点:"<<endl;
    lin.addNode(5);
    lin.addNode(8);
    lin.addNode(7);
    lin.addNode(4);
    lin.addNode(3);
    lin.addNode(4);
    lin.addNode(1);
    lin.addNode(0);
    lin.showNode();
    lin.upSort();
    cout<<"输出所有节点:"<<endl;
    lin.showNode();
    cout<<"输入要查找第几个节点："<<endl;
    cin>>n;
    lin.findNode(n);
    cout<<"输入要删除第几个节点："<<endl;
    cin>>n;
    lin.delNode(n);
    lin.showNode();
    return 0;
}