循环链表 订阅
循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。 展开全文
循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。
信息
外文名
cycle chain或circular linked list
分    类
单循环,多重链
中文名
循环链表
属    性
另一种形式的链式存贮结构
循环链表分类
(1)单循环链表——在单链表中,将终端结点的指针域NULL改为指向表头结点或开始结点即可。(2)多重链的循环链表——将表中结点链在多个环上 [1]  。
收起全文
精华内容
下载资源
问答
  • 单向循环链表

    2021-01-20 03:32:26
    循环链表 循环链表是一种特殊的单链表。实际上,循环链表也很简单。它跟单链表唯一的区别就在尾结点。我们知道,单链表的尾结点指针指向空地址,表示这就是最后的结点了。而循环链表的尾结点指针是指向链表的头结点...
  • jdk1.7 HashMap中的”致命错误”:循环链表 jdk1.7 HashMap结构图 jdk1.7是数组+链表的结构 jdk1.7版本中主要存在两个问题 头插法会造成循环链表的情况 链表过长,会导致查询效率下降 jdk1.8版本针对jdk1.8进行优化...
  • 主要介绍了C语言数据结构之判断循环链表空与满的相关资料,希望通过本文能帮助到大家,让大家掌握这部分内容,需要的朋友可以参考下
  • 数据结构之双向循环链表 实例代码: #include #include #include typedef struct Node{ struct Node *pNext; int data; struct Node *prior; } NODE,*PNODE; PNODE CreatList(); void TreNode(PNODE pHead); ...
  • 本篇文章是对用C++实现单向循环链表的解决方法进行了详细的分析介绍,需要的朋友参考下
  • 主要介绍了C++循环链表之约瑟夫环的实现方法,对于学习数据结构与算法有一定的借鉴价值,需要的朋友可以参考下
  • c++实现的循环链表

    2019-04-09 09:15:06
    使用c++实现的循环链表程序,供大家学习数据结构参考使用
  • 循环链表C语言实现

    2018-02-03 17:48:33
    1.创建链表 2.销毁链表 3.获取链表长度 4.清空链表 5.获取第pos个元素操作 6.插入元素到位置pos 7.删除位置pos处的元素 8.获取当前游标指向的数据元素; 9.将游标重置指向链表中的第一个数据元素; 10.将游标移动...
  • 对于一个循环链表来说,其首节点和末节点被连接在一起。这种方式在单向和双向链表中皆可实现。要转换一个循环链表,可以选择开始于任意一个节点然后沿着列表的任一方向直到返回开始的节点。再来看另一种方法,循环...
  • 用C++和Java实现带头节点的双向循环链表,要继承linearList类,并实现它的所有功能,另外,必须实现双向迭代器。 实现带头节点的双向循环链表,要具有以下的功能: 判断表是否为空,如果为空则返回true,不空返回...
  • 看到题目后的主要思路:先判断链表是否为环,若为环再进行环入口的判断,否则直接返回null 1.判断链表是否为环形链表相对容易,代码如下。主要思路是创建两个指针–快指针fast,步长为2;慢指针slow,步长为1。若...
  • C++实现的带头结点的双向循环链表, 数据结构课设.。
  • 设计算法判断单循环链表是否每个结点的值都是偶数,建立链表,判断,显示。 对任意输入的一组数据,建立一个递增有序的单链表。 将单链表L中的奇数项和偶数项结点分解开,并分别连成一个单链表。 用递增有序的链表A...
  • 本文实例讲述了Python双向循环链表实现方法。分享给大家供大家参考,具体如下: 最近身边的朋友在研究用python来实现数据结构。遇到一个问题就是双向循环链表的实现,改指向的时候总是发蒙。 我自己尝实现了一个...
  • NULL 博文链接:https://128kj.iteye.com/blog/1744646
  • 双向循环链表C++实现

    2016-12-11 10:13:18
    数据结构课程设计实现双向循环链表,我这有详细的课程设计说明书以及答辩ppt,有需要的可以留言哈 ,仅供参考 嘿嘿
  • 循环链表

    千次阅读 2019-11-20 13:45:00
    单向循环链表的定义 循环链表与单向链表的结构比较类似,不同的地方在于其最后一个节点的指针域并不指向NULL,而是指向了首节点first,这样就构成了一个循环,其结构如下: 从上面也可以看出,其和单向链表的区别就...

    单向循环链表的定义

    循环链表与单向链表的结构比较类似,不同的地方在于其最后一个节点的指针域并不指向NULL,而是指向了首节点first,这样就构成了一个循环,其结构如下:
    在这里插入图片描述
    从上面也可以看出,其和单向链表的区别就在于最后一个节点的指针域的值不同,并且其还有一个节点作为表头节点,这个节点是的数据是空的。所以,对于单项循环链表的描述和单向链表是一致的,不过在插入等操作上会有不同,下面是其描述代码:

    template<class T>//声明链表类
    class Link;
    
    template<class T>//创建结点类
    class Node{
    	friend class Link<T>;
    	private:
    		Node<T>* next;//指针域
    		T data;//数据域
    		Node(T newdata){data=newdata;}//构造方法1
    		Node(){}//这个构造方法用来创建第一个空节点,即表头节点,这是
    }
    
    template<class T>//实现链表类
    class Link{
    	public:
    		Link();//构造方法
    		Insert(const int k,const T& x);//向k处插入数据x,k最小值为1
    		void Delete(T& x);//删除节点x
    		void Browser();//浏览链表中的所有数据
    		int Length();//获取链表长度
    		void Reserve();//反转链表
    	private:
    		Node<T>* first=NULL;
    }
    

    构造方法的实现

    与单向链表的构造方法不同,因为单向链表可以不需要表头,所以其构造方法可以什么都不做;但是循环单向链表必须要有表头,所以在其构造方法中,必须创建一个表头节点,这也是两者在构造方法上的不同。
    具体的代码实现如下:

    template<class T>
    Link<T>::Link(){
        Node<T>* head = new Node<T>(); //创建表头
        first=head;  //让first指向表头
        head->next=first; //让表头指向first
    }
    

    如果用上述构造方法创建一个链表,那么其初始的结构如下所示:
    在这里插入图片描述
    上述结构也表明链表是一个空链表,但是要注意,data域中没有数据。

    插入方法的实现

    与单向链表的插入不同,循环单链表插入时只能往表头节点的后面插入,由初始结构可知,想完成插入操作,必须先找到要插入位置的前一个节点,然后修改相应指针即可完成操作。图解如下:
    在这里插入图片描述
    在这里插入图片描述
    下面是代码实现示例:

    template<class T>
    void Link<T>::Insert(const int k,const T& x){
        if(k<1 || k>Length()+2){  //插入位置非法
            cerr<<"the value of k is too big"<<endl;
            throw this;
        }
        //满足条件,执行插入操作
        Node<T>* pt = first;
        for(int i=1;i<k;i++){ //将pt移动至插入位置的前一个元素
            pt = pt->next;
        }
        Node<T>* temp = new Node<T>(x); //封装要插入的数据
        Node<T>* ptn = pt->next; //保存上一个结点的下一个结点信息
        pt->next=temp;  //让上一个的下一个结点改为要插入的节点
        temp->next=ptn; //让插入的节点的下一个结点为其上一个结点原来的恶下一个结点
    }
    

    获取循环链表长度的方法

    template<class T>
    int Link<T>::Length(){
        int length=0;
        Node<T>* p = first;
        while(p->next!=first){ //如果其下一个结点不是first,长度+1
            length++;
            p=p->next;
        }
        return length;
    }
    
    

    浏览链表数据方法的实现

    template<class T>
    void Link<T>::Browser(){
        Node<T>* p = first->next; //指向第一个元素
        while(p!=first){  //如果第一个元素有数据,输出其,然后移动p指针
            cout<<p->data;
            p = p->next;
            if(p!=first){
                cout<<" -> ";//如果p不是最后一个元素,添加“->”符号
            }
        }
        cout<<endl;
    }
    

    删除操作的实现

    以下面一个循环链表为例,删除“2”节点的操作:
    在这里插入图片描述
    在这里插入图片描述

    template<class T>
    void Link<T>::Delete(const T& x){
    	Node<T>* pr=first;
    	Node<T>* middle=NULL;
    	Node<T>* right=NULL;
    	while(pr->next!=first){
    		middle=pr->next;//让当前结点为pr的下一个
    		if(middle->data==x){ //找到,删除
    			right = middle->next;
    			pr->next=right;
    			delete middle;
    			middle = NULL;
    			break;
    		}
    		pr=pr->next;
    	}
    }
    

    对循环链表制作简易迭代器,代码如下:

    //获取下一个值
    template<class T>
    class Iterator{
        public:
            T Next();
            Iterator(Link<T> x);
        private:
            Node<T>* p=NULL;
            Node<T>* temp=NULL;
    };
    
    //构造方法
    template<class T>
    Iterator<T>::Iterator(Link<T> x){
        p = x.getFirst();
        temp=x.getFirst();
    }
    
    //Next方法
    template<class T>
    T Iterator<T>::Next(){
        if(p==temp){
            p=p->next;
        }
        T data = p->data;
        p = p->next;
        return data;
    }
    

    注: 需要在最前面声明Iterator类,然后再将其声明为Node类的友元类。

    翻转循环链表的实现

    反转循环链表和反转单向链表很相似,可以先将循环链表从表头节点的下一个结点处断开,这样循环链表就成为了单向链表,然后运用反转单链表的方式即可,最后设置其表头节点的下一个结点为最后一个节点即q

    template<class T>
    void Link<T>::Reserve(){
    	Node<T>* p = first->next;//指向表头节点的下一个节点
    	Node<T>* q = first; //即将q节点设为first,这样q会指向最后一个节点,即表头节点
    	while(p!=first){
    		Node<T>* temp = q;
    		q = p;
    		p = p->next;
    		q->next = temp;
    	}
    	first->next = q;//让表头结点的下一个结点为最后一个节点
    }
    

    以上所有方法的测试程序

    int main(){
        //创建一个构造函数
        Link<int> Link1 = Link<int>();
        //创建两个变量,用于数据的插入,其中k表示插入的位置,而x表示插入的值
        int k=1;
        int x=5;
        Link1.Insert(k,x); //插入数据
        Link1.Browser(); //浏览数据
        int length = Link1.Length(); //获取当前长度
        k = 2;x=12;
        Link1.Insert(k,x);
        k = 3;x=15;
        Link1.Insert(k,x);
        k = 2;x=17;
        Link1.Insert(k,x);
        Link1.Browser();
        cout<<"the Length is "<<Link1.Length()<<endl;
        //下一轮测试开始
        Link1.Delete(15);
        Link1.Browser();
        cout<<"Length is "<<length<<endl;
        //测试Next方法
        Iterator<int>* It1 = new Iterator<int>(Link1);
        int data = It1->Next();
        cout<<"the data is "<<data<<endl;
        data = It1->Next();
        cout<<"the data is "<<data<<endl;
        data = It1->Next();
        cout<<"the data is "<<data<<endl;
        data = It1->Next();
        cout<<"the data is "<<data<<endl;
        data = It1->Next();
        cout<<"the data is "<<data<<endl;
        data = It1->Next();
        cout<<"the data is "<<data<<endl;
        data = It1->Next();
        cout<<"the data is "<<data<<endl;
        //测试Reverse方法
        Link1.Reserve();
        Link1.Browser();
        data = It1->Next();
        cout<<"the data is "<<data<<endl;
        data = It1->Next();
        cout<<"the data is "<<data<<endl;
        data = It1->Next();
        cout<<"the data is "<<data<<endl;
        data = It1->Next();
        cout<<"the data is "<<data<<endl;
        data = It1->Next();
        cout<<"the data is "<<data<<endl;
        data = It1->Next();
        cout<<"the data is "<<data<<endl;
        cout<<"Execute Successful!";
        return 0;
    }
    
    展开全文
  • 循环链表和约瑟夫环 循环链表的实现 单链表只有向后结点,当单链表的尾链表不指向NULL,而是指向头结点时候,形成了一个环,成为单循环链表,简称循环链表。当它是空表,向后结点就只想了自己,这也是它与单链表的...
  • C语言实现循环链表

    2020-08-18 17:40:11
    主要为大家详细介绍了C语言实现循环链表,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 本题在之前发布过,但发现方法略有复杂。本次将更新一下最简单的思想方法 。... 思想: 改进:不需要对每个结点的左链域进行置空初始化,因为最后还是会重新赋值。只需要对头结点 L 初始化: L->prior = L;...
  • 给出了双向循环链表的定义、介绍,提供了双向循环链表的建立插入与删除源代码
  • 本文实例讲述了C语言基于循环链表解决约瑟夫环问题的方法。分享给大家供大家参考,具体如下: 概述: 约瑟夫环问题,是一个经典的循环链表问题,题意是:已知 n 个人(以编号1,2,3,…,n分别表示)围坐在一张圆桌...
  • 通过循环链表实现约瑟夫环问题,用c语言实现。属于数据结构部分内容
  • VC++双向循环链表

    2021-03-17 11:12:19
    VC++双向循环链表,实现功能:创建新链表、添加新节点;链表数据排序、输入链表信息;查找和删除链表数据、清屏、清空链表等,如果你对VC++的双向循环链表不太熟悉,这个例子对你的是比较有用的。 运行环境:...
  • C数据结构循环链表实现约瑟夫环 本文代码均在turbo C 2.0 的环境下运行通过,并得到正确结果,本程序为用循环链表实现约瑟夫环,即有m个人站成一个圆环,从某人(队列第一个)开始报数,约定从某数开始的第n个人出列...
  • Java实现循环链表

    2020-03-22 23:21:24
    用Java定义一个循环链表,实现链表的基本操作: 初始化*、获取头结点、添加新元素*、删除链表元素 、获取链表元素*、查找链表元素*、更新链表中某个元素、 判断链表是否为空、求链表元素个数、输出链表元素、清空...
  • c语言实现单向循环链表
  • 数据结构-基本算法-不带头结点的循环链表(学生时代源码,调试可运行)
  • C语言数据结构之循环链表的简单实例 实例代码: # include # include typedef struct node //定义链表中结点的结构 { int code; struct node *next; }NODE,*LinkList; /*错误信息输出函数*/ void Error(char *...
  • 单链表、双向链表、循环链表

    千次阅读 多人点赞 2019-07-26 14:26:09
    学习三种常见的链表结构,他们分别是:单链表、双向链表和循环链表。 单链表 单链表有两个较特殊节点,头结点和尾节点。头结点用来记录链表的基地址,可以用来遍历整条链表。尾结点的指针不是指向下一个节点而是指向...

    常见链表

    学习三种常见的链表结构,他们分别是:单链表、双向链表和循环链表。

    单链表

    单链表有两个较特殊节点,头结点尾节点。头结点用来记录链表的基地址,可以用来遍历整条链表。尾结点的指针不是指向下一个节点而是指向一个空地址NULL,表示链表上的最后一个节点。

    和数组一样,链表也支持数据的查找、插入和删除操作。但相对于数据的插入删除需要做大量的搬移操作,链表的插入,删除的时间复杂度为O(1)。但是链表想要随机访问第k个元素,就没有数组高效,随机访问数据的时间复杂度为O(n)。单向链表的简单实现代码如下:

    link_list.h

    /*
     *****************************************************************************
     *
     * File:       linke_list.h
     *
     * Description: Single link list header file
     *
     *
     * History:
     *    Created:  Apri, 2019
     *
     * Copyright (c) 2019 
     * All rights reserved.
     *
     ****************************************************************************/
     #ifndef LINK_LIST_
     #define LINK_LIST_
     
     
     typedef struct _node{
    	 struct _node *next;
    	 int date;
     }node, *list;
    
    list init_single_link_list();
    int insert_to_link_list_head(list list, int date);
    int insert_to_link_list_tail(list list, int date);
    void show_single_link_list (list head);
    void delete_from_link_tail(list list_);
    #endif
    

    link_list.c

    /*
     *****************************************************************************
     *
     * File:        link_list.c
     *
     * Description: Single link list file
     *
     *
     * History:
     *    Created:  Apri, 2019
     *
     * Copyright (c) 2019 
     * All rights reserved.
     *
     ****************************************************************************/
    #include <stdio.h>
    #include <stdlib.h>
    #include "link_list.h"
    
     
    list init_single_link_list()
    {
    	list link_list = NULL;
    	
    	link_list = (list)malloc(sizeof(list));
    	if(NULL == link_list){
    		printf("malloc failed !!\n");
    		exit(1);
    	}
    	link_list->next = NULL;
    	return link_list;
    }
    
    /*
      insert a node to single link list
      头插法
    */
    int insert_to_link_list_head(list list_, int date)
    {
    	list p = NULL;
            
            if (NULL == list_) {
               printf("list is NULL ...\n");
               exit(1);
            }	
    	p = (list)malloc(sizeof(list));
    	if(p == NULL) {
    		printf("malloc failed \n");
    		exit(1);
    	}
    	p->date = date;
    	
    	p->next = list_->next;
    	list_->next = p;
    	
    	return 1;
    }
    /*
     * 尾插法实现
    */
    int insert_to_link_list_tail(list list_, int date)
    {
    	list p = NULL;
            
            if (NULL == list_) {
                printf("list is NULL ...\n");
                exit(1);
            }
    	p = (list)malloc(sizeof(list));
    	if(NULL == p) {
    		printf("malloc fialed !\n");
    		exit(1);
    	}
    	while(list_->next) {
                       
                list_ = list_->next;    
            } 
            p->date = date;
            list_->next = p;
            p->next = NULL; 
    	
    	return 1;
    	
    }
    
    void show_single_link_list (list head)
    {
    	if (NULL == head) {
    		printf(" list is null ...\n");
    		return;
    	}
    	head = head->next;
    	while(head) {
    		printf("date ---- > %d \n", head->date);
    		head = head->next;
    	}
    	
    	return;
    }
    /*
     * delete element from tail of link list
     * */
    void delete_from_link_tail(list list_)
    {
        if(NULL == list_) {
            printf("list is NULL ...\n");
            exit(1);
        }
        if(list_->next == NULL) {
            free(list_);
            list_ = NULL;
        }
        while(list_->next->next) {
            list_ = list_->next;
        }
        free(list_->next);
        list_->next= NULL;
        
        return ;
    }
    /*
     * delete from link head
     * */
    void delete_from_link_head(list list_)
    {   
        list p = NULL;
        if(NULL == list_) {
            printf("link is NULL ...\n");
            exit(1);
        }
        
        if(list_->next) {
            p = list_->next;
            list_->next = p->next;
            free(p);
        }
        return;
    }
    /*
     * get link list size
     * 
     * */
    int get_link_size(list list_)
    {
        int size = 0;
        if(NULL == list_) {
            printf("link is NULL ...\n");
            exit(1);
        }
        while(list_->next) {
            ++size;
            list_ = list_->next;
        }
        return size;
    }
    void delete_specific_date(list list_, int date)
    {
        list p = NULL;
        int size = 0;
        if(NULL == list_) {
            printf("list is NULL ...\n");
            exit(1);
        }
        size = get_link_size(list_);
        if (size <= 0) {
            printf("link hasn't element ...\n");
            exit(1);
        }
        p = list_->next;
        while(p->date != date) {
            p = list_->next;
        }
      
       list_->next = p;
       free(list_);
        
        return;
    }
    int main()
    {
    	list head = NULL;
    	int i;
    	
    	head = init_single_link_list();
    #if 0
    	for (i = 0; i < 2; i++) {
    		
               //insert_to_link_list_head(head, i);
               insert_to_link_list_tail(head, i);
    	}
    #endif
    	show_single_link_list(head);
            printf("list size is %d\n", get_link_size(head));
            //delete_from_link_tail(head);
            //delete_from_link_head(head);
            delete_specific_date(head, 0);
            show_single_link_list(head);	
    }
    
    
    

    双向链表

    双向链表支持两个方向,每个节点有一个后继指针next指向后面的节点,还有一个前驱指针指向前面的节点。
    在这里插入图片描述
    双向链表简单实现:
    double_linklist.h

    #ifndef DOUBLE_LINKLIST_
    #define DOUBLE_LINKLIST_
    
    #include "stdbool.h"
    typedef int ElementType;
    typedef struct _double_link {
        ElementType date;
        struct _double_link *next;
        struct _double_link *pre;     
    }double_linklist;
    
    double_linklist *init_double_linklist();
    bool insert_linklist_head(double_linklist* d_linklist, ElementType date);
    ElementType delete(double_linklist* d_linklist);
    void display(double_linklist* d_linklist);
    bool isEmpty(double_linklist* d_linklist);
    
    #endif
    

    double_linklist.c

    #include <stdio.h>
    #include <stdlib.h>
    #include "double_linklist.h"
    
    /*
    @func :创建头结点和尾结点,新增的节点插入头结点和尾结点之间
    */
    double_linklist *init_double_linklist()
    {
        double_linklist *head = (double_linklist *)malloc(sizeof(double_linklist));
        if (!head) {
            perror("malloc failed.");
            exit(1);
        }
        head->next = NULL;
        head->pre = NULL;
        double_linklist *pNew = (double_linklist *)malloc(sizeof(double_linklist));
        if (!pNew) {
            perror("malloc failed.");
            exit(1);
        }
        pNew->next = NULL;
        pNew->pre = head;
        head->next = pNew;
        
        return head;
    }
    /*
    @func: 头插法,新增的节点插入头结点后面
    */
    bool insert_linklist_head(double_linklist* head, ElementType date)
    {
        if (!head) {
            perror("d_linklist is NULL");
            exit(1);
        }
        double_linklist* pNew = (double_linklist *)malloc(sizeof(double_linklist));
        if (!pNew) {
            perror("malloc failed.");
            exit(1);
        }
        pNew->date = date;
        /*先确定新增节点的前后指针指向*/
        pNew->pre = head;
        pNew->next = head->next;
        head->next->pre = pNew;
        head->next = pNew;
        
        printf("insert %d\n", head->next->date);
        return true;
    }
    bool isEmpty(double_linklist* head)
    {
        if (!head) {
            perror("d_linklist is NULL.");
            exit(1);
        }
        if (head->next->next == NULL && head->next->pre == head)
            return true;
        else
            return false;
    }
    /*
    @func: 删除一个节点
    */
    ElementType delete(double_linklist* head)
    {
        if (!head) {
            perror("d_linklist is NULL.");
            exit(1);
        }
        if (isEmpty(head)) {
            printf("double linklist is empty.\n");
            exit(1);
        }
        double_linklist* pDel = head->next;
        ElementType val = pDel->date;
        
        pDel->next->pre = head;
        head->next = pDel->next;
        if (pDel) {
            free(pDel);
            pDel = NULL;
        }
        return val;
    }
    
    void display(double_linklist* head)
    {
        if (!head) {
            perror("d_linklist is NULL.\n");
            exit(1);
        }
        if (isEmpty(head)) {
            printf("double linklist is empty.\n");
            exit(1);
        }
        double_linklist* tmp = head->next;
        while (tmp->next != NULL) {
            printf("val ---> %d\n", tmp->date);
            tmp = tmp->next;
        }
    }
    int main()
    {
        double_linklist* d_link = init_double_linklist();
        insert_linklist_head(d_link, 20);
        insert_linklist_head(d_link, 10);
        printf("delete val is %d .\n", delete(d_link));
        printf("delete val is %d .\n", delete(d_link));
        display(d_link);
        
    }
    

    循环链表

    单向循环链表

    和单链表相比,循环链表的优点是从链尾到链头特别容易,适合处理具有环形结构特点的数据,如著名的约瑟夫问题。循环链表的简单实现如下:
    robin_linklist.h

    #ifndef ROBIN_LINKLIST_
    #define ROBIN_LINKLIST_
    
    #include "stdbool.h"
    typedef int ElementType;
    typedef struct _node {
        ElementType date;
        struct _node* next;
    }robin_linklist;
    
    robin_linklist* init_robin_linklist();
    bool insert_to_robin_linklist(robin_linklist* link, ElementType date);
    bool delete_from_robin_linklist(robin_linklist* link);
    void display_robin_linklist(robin_linklist* link);
    #endif
    

    robin_linklist.c

    #include <stdio.h>
    #include <stdlib.h>
    #include "robin_linklist.h"
    
    robin_linklist* init_robin_linklist()
    {
        robin_linklist *head = (robin_linklist *)malloc(sizeof(robin_linklist));
        if (!head) {
            perror("malloc failed.");
            exit(1);
        }
        /*next指针指向自己*/
        head->next = head;
        robin_linklist *node = (robin_linklist *)malloc(sizeof(robin_linklist));
        if (!node) {
            perror("malloc failed.");
            exit(1);
        }
        node->next = head;
        head->next = node;
        return head;
    }
    /*
    @func : insert a element to linklist
    */
    bool insert_to_robin_linklist(robin_linklist* link, ElementType date)
    {
        if (!link) {
            perror("link is NULL.");
            exit(1);
        }
        robin_linklist* node = (robin_linklist *)malloc(sizeof(robin_linklist));
        if (!node) {
            perror("malloc failed.");
            exit(1);
        }
        node->date = date;
        node->next = link->next;
        link->next = node;
        
        return true;  
    }
    /*
    @func : delete a element from linklist
    */
    bool delete_from_robin_linklist(robin_linklist* link)
    {
        if (!link) {
            perror("link is NULL.");
            exit(1);
        }
        if (link->next->next != link) {
            robin_linklist *tmp = link->next;
            link->next = tmp->next;
            return true;
        }else {
            printf("link is empty.\n");
            return false;
        }
    }
    void display_robin_linklist(robin_linklist* link)
    {
        if (!link) {
            perror("link is NULL.");
            exit(1);
        }
        robin_linklist *tmp = link->next;
        while(link != tmp->next) {
          printf("val ---> %d\n", tmp->date);
          tmp = tmp->next;
        }
    }
    int main()
    {
        /*test code*/
        robin_linklist *ro_linklist = init_robin_linklist();
        insert_to_robin_linklist(ro_linklist, 10);
        display_robin_linklist(ro_linklist);
        delete_from_robin_linklist(ro_linklist);
        display_robin_linklist(ro_linklist);
        delete_from_robin_linklist(ro_linklist);
          
    }
    
    

    双向循环链表

    在这里插入图片描述
    双向链表的简单实现:
    double_robin_linklist.h

    #ifndef DOUBLE_ROBIN_LINKLIST_
    #define DOUBLE_ROBIN_LINKLIST_
    
    #include "stdbool.h"
    
    typedef int ElementType;
    typedef struct _double_robin_link {
        ElementType date;
        struct _double_robin_link *next;
        struct _double_robin_link *pre;
    }dou_robin_link;
    
    dou_robin_link* init_double_robin_linklist();
    bool insert_head(dou_robin_link * link, ElementType date);
    ElementType delete(dou_robin_link* link);
    bool isEmpty(dou_robin_link* link);
    void display(dou_robin_link* link);
    
    #endif
    

    double_robin_linklist.c

    #include <stdio.h>
    #include <stdlib.h>
    #include "double_robin_linklist.h"
    
    
    dou_robin_link * init_double_robin_linklist()
    {
        dou_robin_link* head = (dou_robin_link *)malloc(sizeof(dou_robin_link));
        if (!head) {
            perror("malloc failed.");
            exit(1);
        }
        head->next = head;
        head->pre = head;
        
        /*创建尾节点*/
        dou_robin_link *tail = (dou_robin_link *)malloc(sizeof(dou_robin_link));
        if (!tail) {
            perror("malloc failed.");
            exit(1);
        }
        tail->pre = head;
        tail->next = head;
        head->next = tail;
        
        return head;
    }
    bool isEmpty(dou_robin_link* link)
    {
        if (!link) {
            perror("link is NULL.");
            exit(1);
        }
        if (link->next->next == link && link->next->pre == link) {
            
            printf("double robin linklist is empty.\n");
            return true;
        }
        else {
            return false;
        }
    }
    /*
    @func: 头插法
    */
    bool insert_head(dou_robin_link * link, ElementType date)
    {
        if (!link) {
            perror("link is NULL.");
            exit(1);
        }
        dou_robin_link *pNew = (dou_robin_link *)malloc(sizeof(dou_robin_link));
        if (!pNew) {
            perror("malloc is NULL.");
            exit(1);
        }
        pNew->date = date;
        pNew->next = link->next;
        pNew->pre = link;
        
        link->next = pNew;
        link->next->next->pre = pNew;
        printf("insert -->%d\n", link->next->date);
        
        return true;
    }
    /*
    @func: 头删法
    */
    ElementType delete(dou_robin_link* link)
    {
        if (!link) {
            perror("link is NULL.");
            exit(1);
        }
        if (isEmpty(link)) {
            exit(1);
        }
        dou_robin_link *pDel = link->next;
        ElementType val = pDel->date;
        link->next = pDel->next;
        pDel->next->pre = link;
        
        printf("delete ---> %d\n", val);
        if(pDel) {
            free(pDel);
            pDel = NULL;
        }
        return val;
    }
    
    void display(dou_robin_link* link)
    {
        if(!link) {
            perror("link is NULL.");
            exit(1);
        }
        if(isEmpty(link)) {
            exit(1);
        }
        dou_robin_link* tmp = link->next;
        while (tmp->next != link && tmp->next->pre != link) {
            printf("val ---> %d\n", tmp->date);
            tmp = tmp->next;
        }
    }
    int main()
    {
        dou_robin_link *head = init_double_robin_linklist();
        insert_head(head, 10);
        insert_head(head, 20);
        delete(head);
        display(head);
    }
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 282,688
精华内容 113,075
关键字:

循环链表