当前位置:首页 > 高性能开发 > 数据结构与算法

数据结构与算法——线性表链式储存(双向循环链表)

优良自学吧提供数据结构与算法——线性表链式储存(双向循环链表),数据结构与算法——线性表链式存储(双向循环链表)今天总结线性表中的双向循环链表。 什么是双向循环链表?   看名字估计也就知道了,首相他是一个循环链表,也就是最后一个结点的指针域不为空,而是指向头结点,其次与单向循环链表相比,它是双向的。所谓双向,就是给每个结点再

数据结构与算法——线性表链式存储(双向循环链表)

今天总结线性表中的双向循环链表。

什么是双向循环链表?

  看名字估计也就知道了,首相他是一个循环链表,也就是最后一个结点的指针域不为空,而是指向头结点,其次与单向循环链表相比,它是双向的。所谓双向,就是给每个结点再增加一个指针域,这个指针域指向前一个结点。

 即是下面这样(来自百度图片):

数据结构与算法——线性表链式储存(双向循环链表)

为什么要用双向循环链表?

 无论单链表还是单向循环链表,都只有一个指针域,它们都是直接指向后继结点的,如果要查找当前结点的后继结点,会很方便。但是如果给定一个结点,要得到它的前继结点,就会很麻烦,必须从第一个元素开始遍历,然后判断当某个结点的指针域指向的是当前结点时,就判断该结点为当前结点的前继结点,时间复杂度为O(n)。而如果给每个结点增加一个指针域,指向其前继结点,那么给定一个结点时,直接就可以得到它的前继结点。

如何实现双向循环链表?

<span style="font-family:Courier New;font-size:14px;">#include <iostream>

using namespace std;
template <class T>
struct Node {
    T data;             //数据域
    struct Node<T> *pre; //指向前一个结点
    struct Node<T> *next; //指向后一个结点
};
template <class T>
//双向循环链表 模板类
class DoubleLinkList {
private:
    Node<T> *front; //头指针
public:
    //空的循环链表
    DoubleLinkList() {
        front = new Node<T>; //头结点
        front->next = front;
        front->pre = front;
    }
    ~DoubleLinkList(); //析构函数 释放节点空间
    DoubleLinkList(T a[],int n); //用数组a初始化链表
    void Insert(int i,T x); //插入元毒到指定位置
    T Delete(int i); //删除指定位置的元素
    Node<T> *GetNode(int i);   //返回指定位置的结点
    int GetLength();  //获取链表的长度
    void PrintLinkList(); //遍历链表
};
template <class T>
//尾插法
DoubleLinkList<T>::DoubleLinkList(T a[],int n) {
    front = new Node<T>;
    front->next = front->pre = front; //初始化空表
    for(int i=0;i<n;i++) {
        Node<T> *s = new Node<T>;
        s->next = front->next;  //让当前结点指向头结点
        s->data = a[i];
        s->pre = front;        //当前结点pre指针指向前一个结点
        front->next = s;      //前一个结点指向当前结点
        front->pre = s;
        front = front->next;   //指针后移
    }
}

template <class T>
DoubleLinkList<T>::~DoubleLinkList() {
    Node<T> *p = front->next; //获取头结点
    while(p!=front->next) {
        Node<T> *q = p;   //保存待删结点地址
        p=p->next;
        delete q;
    }
}

template <class T>
int DoubleLinkList<T>::GetLength() {
    Node<T> *p = front->next;
    int count = 1;
    while(p!=front->pre) {
        count++;
        p = p->next;
    }
    return count;

}


template <class T>
void DoubleLinkList<T>::PrintLinkList() {
    Node<T> *p = front->next->next;  //得到第一个结点
    for(int i=0;i<GetLength();i++) {
        cout<<p->data<<" ";
        p = p->next;
    }
    cout<<endl;
}

template <class T>
Node<T> * DoubleLinkList<T>::GetNode(int i) {
    Node<T> * p = front->next;
    for(int j=0;j<i;j++) {
        p = p->next;
    }
    return p;
}

template <class T>
T DoubleLinkList<T>::Delete(int i) {
    Node<T> *p = front;
    if(i!=1)
       p = GetNode(i-1); //获取待删结点的前一个结点
    if(p) {
        Node<T> *q = p->next;  //保存待删结点
        T x = q->data;         //待删元素
        p->next->next->pre = p; //使待删结点的后继结点的pre指针域指向前一个结点
        p->next = p->next->next;  //前一个结点next指针域指向待删结点后面的那个元素
        delete q;
        return x;
    }
    return 0;

}

/**
    插入操作实现
    思路:
    1.获取待插位置的前一个结点
    2.新建一个结点,将待插结点元素保存到其数据域中
    3.将待插结点指向插入位置后面的那个结点,其pre指向前面的那个结点
    4.将后面结点的pre指向待插结点,将前面结点指向待插结点
    技巧:这里可能结点指向操作的顺序容易弄混,导致出错.
    我的办法是,只要先把当前结点先分别指向后继结点和前继结点,然后再使前继结点和后继结点指向当前结点
    就一句话,记住先处理当前结点的指针域,顺序基本就不会错了。
*/
template <class T>
void DoubleLinkList<T>::Insert(int i,T x) {
    Node<T> *p = front;
    if(i!=1)
        p = GetNode(i-1);
    if(p) {
        Node<T> *s = new Node<T>;
        s->data = x;
        s->next = p->next; //指向后继结点
        s->pre = p;       //pre指针域指向前一结点
        p->next->pre = s;   //后继结点pre指向待插结点
        p->next = s;       //前一结点指向待插结点
    }

}
int main()
{
    int a[6] = {1,3,6,7,4,8};
    DoubleLinkList<int> list(a,6);
    cout<<"双向循环链表的长度为:"<<endl;
    cout<<list.GetLength()<<endl;
    cout<<"遍历双向循环链表"<<endl;
    list.PrintLinkList();
    cout<<"删除位置3的元素:"<<endl;
    cout<<"删除的元素为:"<<list.Delete(3)<<endl;
    list.PrintLinkList();
    cout<<"在位置3插入元素5"<<endl;
    list.Insert(3,5);
    list.PrintLinkList();
    return 0;
}
</span>
运行结果:

数据结构与算法——线性表链式储存(双向循环链表)


(本文来自互联网,不代表搜站(http://www.ylzx8.cn/)的观点和立场)
本站所有内容来自互联网,若本站收录的信息无意侵犯了贵司版权,请给我们来信(ylzx8cn@163.com),我们会及时处理和回复,谢谢