数据结构学习心得——双链表和循环链表

向右看齐 2022-06-09 00:08 168阅读 0赞

## 双链表 ##

若要寻查结点的前驱，则需要从表头指针出发。为了克服单链表这种单向性的缺点，可以利用双链表。顾名思义，在双链表的结点中有两个指针域，其一指向直接后继，另一指向直接前驱。  
![这里写图片描述][SouthEast]

## 循环链表 ##

循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。由此，从表中任一结点出发均可找到表中其他结点。  
![这里写图片描述][SouthEast 1]

## 代码实现 ##

这里的代码只实现了创建部分的代码，其他的一些查找，删除，添加操作，请参照上一篇博客单链表操作部分，基本上差不多少。  
连接：[http://blog.csdn.net/u012350430/article/details/77338132][http_blog.csdn.net_u012350430_article_details_77338132]

#include <iostream>
    
    using namespace std;
    
    typedef struct LNode
    {
        int data;
        struct LNode *next;
    }LNode;
    
    typedef struct DLNode
    {
        int data;
        struct DLNode *prior;
        struct DLNode *next;
    }DLNode;
    
    //双链表的创建同样有尾插法和头插法两种创建方法
    //这里使用的是尾插法
    void createDlist(DLNode *&L,int a[],int n)
    {
        DLNode *q;
        DLNode *p = L;
        int i;
        for(i=0;i<n;i++)
        {
            q = new DLNode;
            q->data = a[i];
            p->next = q;
            q->prior = p;
            p = q;
        }
        p->next = NULL;
    }
    
    //用尾插法创建循环链表
    void createList(LNode *&L,int a[],int n)
    {
        LNode *q;
        LNode *p = L;
        int i;
        for(i=0;i<n;i++)
        {
            q = new LNode;
            q->data = a[i];
            p->next = q;
            p = q;
        }
        p->next = L;
    }
    
    //输出双链表中所有元素的值
    void printDList(DLNode *head)
    {
        DLNode *p = head->next;
        while(p!=NULL)
        {
            cout<<p->data<<" ";
            p=p->next;
        }
        cout<<endl;
    }
    
    //输出循环链表中的所有元素
    void printList(LNode *head,int n)
    {
        int i;
        LNode *p = head->next;
        for(i=0;i<n;i++)
        {
            cout<<p->data<<" ";
            p=p->next;
        }
        cout<<endl;
    }
    
    int main()
    {
        DLNode *Dhead = new DLNode;
        Dhead->next = NULL;
        Dhead->prior = NULL;
    
        LNode *head = new LNode;
        head->next = NULL;
        int a[6]={
       2,3,4,7,9,8};
    
        createDlist(Dhead,a,6);
        createList(head,a,6);
    
        printDList(Dhead);
        printList(head,6);
        return 0;
    }

代码运行截图：  
![这里写图片描述][SouthEast 2]

[SouthEast]: /images/20220609/2537bce209a24872840ff4e39249e6d3.png
[SouthEast 1]: /images/20220609/77abb220b3e64d8a8ef3306a055f0397.png
[http_blog.csdn.net_u012350430_article_details_77338132]: http://blog.csdn.net/u012350430/article/details/77338132
[SouthEast 2]: /images/20220609/1a9675f385ef406393a3c9c2483d69e6.png