循环链表_循环链表约瑟夫 - CSDN
循环链表 订阅
循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。 展开全文
循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。
信息
外文名
cycle chain或circular linked list
分    类
单循环,多重链
中文名
循环链表
属    性
另一种形式的链式存贮结构
循环链表分类
(1)单循环链表——在单链表中,将终端结点的指针域NULL改为指向表头结点或开始结点即可。(2)多重链的循环链表——将表中结点链在多个环上 [1]  。
收起全文
精华内容
参与话题
  • c语言循环链表的实现

    千次阅读 多人点赞 2018-09-01 13:22:57
    单链表有一定的缺陷,就是单向性,只能从一个结点到下一个节点,而不能访问到上一个结点,而循环链表就可以解决这一问题,当然,用双向链表更加方便 #include <stdio.h> #include <stdlib.h&...

    单链表有一定的缺陷,就是单向性,只能从一个结点到下一个节点,而不能访问到上一个结点,而循环链表就可以解决这一问题,当然,用双向链表更加方便

    #include <stdio.h>
    #include <stdlib.h>
    
    typedef struct node
    {
        int data;
        struct node *next;//指针域
        int size;//循环链表的长度
    }node,*linklist;//linklist为定义的指针结构体变量
    
    void create_list_head(linklist *l)//头插法建立循环链表
    {
        int i,j,x;
        linklist p,q;
        printf("please input length");
        scanf("%d",&j);
        (*l)=(node*)malloc(sizeof(node));
        (*l)->next=NULL;//必须定义,缺少error
        (*l)->size=j;
        for(i=0;i<j;i++)//头插法输入数据
        {
            scanf("%d",&x);
            p=(node*)malloc(sizeof(node));
            p->data=x;
            p->next=(*l)->next;
            (*l)->next=p;
        }
        //q=(node*)malloc(sizeof(node));
        q=(*l)->next;
        while(q->next!=NULL)//找到最后一个结点
        {
            q=q->next;
        }
        //printf("%d",q->data);
        q->next=(*l)->next;//将最后一个结点指向第一个结点
    
    
    
    }
    
    void create_list_tail(linklist *l)//尾插法建立循环链表
    {
        int i,j,x;
        linklist p,r,t;
        printf("please input the length");
        scanf("%d",&j);
        (*l)=(node*)malloc(sizeof(node));
        (*l)->next=NULL;
        (*l)->size=j;
        t=(*l);
        for(i=0;i<j;i++)
        {
            scanf("%d",&x);
            p=(node*)malloc(sizeof(node));
            p->data=x;
            t->next=p;
            t=p;//每新建一个结点在结束时都为最后一个结点,下一个节点在这个结点后面插入
    
        }
        t->next=NULL;
        r=(*l)->next;
        while(r->next!=NULL)
        {
            r=r->next;
        }
        r->next=(*l)->next;
    }
    
    void print_list_he(linklist *l)//打印输出
    {
        int i;
        linklist p;
        p=(*l)->next;
        for(i=0;i<(*l)->size;i++)
        {
            printf("%d\n",p->data);
            p=p->next;
        }
    }
    
    int main()
    {
        linklist a;
        create_list_head(&a);
        create_list_tail(&a);
        print_list_he(&a);
        return 0;
    }

     

    展开全文
  • 循环链表的操作详解

    千次阅读 2017-09-13 13:45:48
    循环链表循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。 从上图看出循环链表有两个成员:data 和 next 由此可创建循环链表和它的一些基本操作如下:...

    一、概述

    循环链表:循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。


    从上图看出循环链表有两个成员:data 和 next

    由此可创建循环链表和它的一些基本操作如下:

    注明:它的操作其实与单链的操作差不多,只要注意判断标志即可。

    #pragma once
    //循环链表,尾节点的next指向头
    
    typedef struct CNode  //宏定义
    {
    	int data;
    	struct CNode *next;
    }CNode,*CList;//CList==CNode*
    
    
    void InitList(CList plist);
    
    //头插
    bool Insert_head(CList plist,int val);
    //尾插
    bool Insert_tail(CList plist,int val);
    
    CNode *Search(CList plist,int key);
    
    bool Delete(CList plist,int key);
    
    bool IsEmpty(CList plist);
    
    int GetLength(CList plist);
    
    void Show(CList plist);
    
    void Destroy(CList plist);
    
    void Clear(CList plist);

    链表操作实现:

    void InitList(CList plist)
    {
    	assert(plist != NULL);
    
    	plist->next = plist;
    }
    
    //头插
    bool Insert_head(CList plist,int val)
    {
    	CNode *p = (CNode *)malloc(sizeof(CNode));//创建新节点
    	p->data = val;
    	
    	p->next = plist->next;//连线,防止数据丢失
    	plist->next = p;
    
    	return true;
    }
    //尾插
    bool Insert_tail(CList plist,int val)
    {
    	CNode *p = (CNode *)malloc(sizeof(CNode));
    	p->data = val;
    
    	CNode *q;
    	for(q=plist;q->next!=plist;q=q->next) ;//->next==NULL
    
    	//将p插入在q后面
    	p->next = q->next;
    	q->next = p;
    
    
    	return true;
    }
    
    CNode *Search(CList plist,int key)
    {
    	CNode *p;
    	
    	for( p = plist;plist->next != plist;p=p->next)//遍历找key,注意链表的有效数据节点既是它的头,也是尾。
    	{
    		if(p->data == key) 
    		{
    			return p;
    		}
    		
    	}
    	return NULL; 
    }
    
    
    bool Delete(CList plist,int key)
    {
    	CNode *p;
    	for(p=plist;p->next!=plist;p=p->next)
    	{
    		if(p->next->data == key)//找到key的上一个节点位置
    		{
    			break;
    		}
    	}
    	if(p->next == plist)//没有key
    	{
    		return false;
    	}//将节点从链表中删除
        CNode *q = p->next;
    	p->next = q->next;
    	//p->next = p->next->next;
    
    
    	free(q);//释放内存
    
    	return true;
    
    }
    
    bool IsEmpty(CList plist)
    {
    	return plist->next == NULL;
    
    }
    
    int GetLength(CList plist)
    {
    	int count = 0;//计数器
    	for(CNode *p = plist;p->next != plist;p=p->next)
    	{
    		count++;
    	}
    	return count;
    }
    
    
    
    void Destroy(CList plist)
    {
    
    	CNode *p;
    	while(plist->next != plist)
    	{
    		p = plist->next;
    		plist->next = p->next;
    		free(p);
    	}
    }
    
    void Clear(CList plist)
    {
    	Destroy( plist);
    
    }
    void Show(CList plist)
    {
    	CNode *q;
    
    	for(q=plist->next; q->next !=plist;q=q->next) 
    	{
    		printf("%d ",q->data);
    
    	}
    
    }

    程序测试:

    #include<stdio.h>
    #include<stdlib.h>
    #include<vld.h>
    #include"clist.h"//循环链表已完成
    
    int main()
    {
    	CNode sa;
    	
    	InitList(&sa);
    	
    	int i;
    	
    	for(i=0;i<10;i++)
    	{
    		Insert_tail(&sa,i);
    	}
    	//printf("%d ",Search(&sa,100));
    	Delete(&sa,2);
    	Delete(&sa,3);
    	Delete(&sa,12);
    	printf("%d\n",GetLength(&sa));
    	//Destroy(&sa);
    	//Destroy(&sa);
    	//Destroy(&sa);
    
    
    
    
    
    	Show(&sa);
    	
    	
       
    
    	return 0;
    
    }

    运行结果:






    展开全文
  • 数据结构学习—循环链表的实现(非常详细)

    万次阅读 多人点赞 2018-01-21 10:05:41
    今天我们来实现下循环链表的相关算法。LZ今天非常用心的写这个博客,一切解释说明都在代码中。 认真写篇博客还是挺费时间的,但是写博客不但是对我们学习成长的一个见证,而且会提高我们向别人解释问题的能力对面试...

    今天我们来实现下循环链表的相关算法。LZ今天非常用心的写这个博客,一切解释说明都在代码中。

    认真写篇博客还是挺费时间的,但是写博客不但是对我们学习成长的一个见证,而且会提高我们向别人解释问题的能力对面试非常有帮助,分享也是一件非常快乐的事情嘛

    下面贴代码:

    #define _CRT_SECURE_NO_WARNINGS
    #include <stdio.h>
    #define ERROR 0
    #define OK 1
    typedef int EleType;
    /*
    循环链表的结构和单链表结构一样,不过对于单链表,每个结点只存储了向后的指针,
    到了尾标志就停止了向后链的操作,这样知道某个结点却无法找到它的前驱结点。
    将单链表中的终端点的指针由空指针改为指向头结点,就使整个单链表形成一个环,
    这种头尾相接的单链表称为循环单链表,简称循环链表。
    */
    typedef struct CLinkNode
    {
    	EleType data;
    	struct CLinkNode *next;
    }CLinkNode,*CLinkList;
    
    /*
    初始化循环链表
    */
    int InitCLinkList(CLinkList *list)
    {
    	if (list == NULL)
    	{
    		return ERROR;
    	}
    
    	int data = 0;
    	CLinkNode* target = NULL;
    	CLinkNode* head_node = NULL;
    	printf("请输入结点数据,0代表结束初始化:\n");
    	//这里采用用户控制台输入数据,你也可以随机生成数据进行初始化
    	while (1)
    	{
    		scanf("%d", &data);
    		//fflush(stdin);
    		if (data == 0)
    		{
    			//退出循环标志,用户输入0 表示结束输入数据
    			break;
    		}
    
    		/*
    		判断初始化的链表有没有结点
    		没有结点 先创建头结点 然后插入数据
    		有结点 将结点用尾插法插入到链表中
    		最后 尾结点的 指针域 指向头结点 这样形成一个环
    		*/
    		if (*list == NULL)
    		{
    			CLinkNode* head= (CLinkNode*)malloc(sizeof(CLinkNode));
    			//分配结点空间失败
    			if (head == NULL)
    			{
    				exit(0);
    			}
    
    			*list = head;//链表指向头结点
    
    			CLinkNode* node = (CLinkNode*)malloc(sizeof(CLinkNode));
    			if (node == NULL)
    			{
    				exit(0);
    			}
    			node->data = data;
    			node->next = head;
    			head->next = node;
    		}
    		else
    		{
    			//如果循环链表不为空 链尾部插入数据
    			//通过循环 找到尾结点,怎样判断是否是尾结点?当结点的指针域指向头结点时为尾结点,这样才能形成环嘛
    			//循环结束后target 指向尾结点
    			//for 循环下好好理解下!target初始化为第一个结点指针
    			for (target = (*list)->next; target->next != *list; target = target->next);
    			head_node = target->next;
    
    			CLinkNode* node = (CLinkNode*)malloc(sizeof(CLinkNode));
    			if (node == NULL)
    			{
    				exit(0);
    			}
    			node->data = data;
    			node->next = head_node;
    
    			target->next = node;//将新结点插入尾部
    		}
    
    	}
    	return OK;
    }
    /*
    往链表指定位置插入数据
    list 循环链表
    loc 第loc位置插入元素,loc 从1 开始计数
    data 插入元素的数据域
    */
    int InsertCLinkNode(CLinkList list,int loc, EleType data)
    {
    	if (list == NULL || loc < 1)
    		return ERROR;
    	/*
    	循环目的:找到第loc-1位置结点
    	*/
    	int i = 1;// 按人类的读法 i表示第i个位置 和 loc 表达意思一致
    	CLinkNode* node = list;//刚开始node指向头结点
    	while (node->next!=list && i < loc)
    	{
    		node = node->next;
    		i++;
    	}
    	/*
    	这里while循环比较难理解,我们拿 3个元素循环链表 来讲解
    	loc = 1 时 往第1个位置插入元素
    	不进入循环 node 指向头结点 i == loc == 1 插入合法
    
    	loc = 2 时
    	node 指向 第1个结点,i = 2 跳出循环
    	
    	loc = 3 时
    	node 指向 第1个结点,i = 2 循环继续
    	node 指向 第2个结点,i = 3 跳出循环
    
    	loc = 4 时 注意:如果有3个元素 往第4位置插入元素 是合法!等于往链表尾部插入元素。 
    	node 指向 第1个结点,i = 2 循环继续
    	node 指向 第2个结点,i = 3 循环继续
    	node 指向 第3个结点,i = 4 跳出继续
    	
    	循环结束时 i==loc 才合法! 此时node 指向 第 loc-1 位置的结点
    	将 新结点的指针域 指向 第loc-1位置的后继结点
    	将 第loc-1位置的指针域 指向 新结点,这样新结点就插入到 循环链表的 第loc位置了!
    	*/
    
    	/*
    	循环结束时 i==loc 才合法! 此时node 指向 第 loc-1 位置的结点
    	将 新结点的指针域 指向 第loc-1位置的后继结点
    	将 第loc-1位置的指针域 指向 新结点,这样新结点就插入到 循环链表的 第loc位置了!
    	*/
    	if (i == loc)
    	{
    		CLinkNode* new_node = (CLinkNode*)malloc(sizeof(CLinkNode));
    		if (new_node == NULL)
    		{
    			exit(0);
    		}
    		new_node->data = data;
    		new_node->next = node->next;//新结点指针域 指向前驱结点的后继结点
    		node->next = new_node;//将新结点加入链表
    	}
    	else
    	{
    		return	ERROR;
    	}
    
    	return OK;
    }
    /*
    删除指定结点,通过指针返回删除结点的数据
    */
    int DelCLinkNode(CLinkList list,int loc, EleType* data)
    {
    	if (list == NULL || loc < 1)
    		return ERROR;
    	/*
    	循环目的:找到第loc-1位置结点
    	*/
    	int i = 1;// 按人类的读法 i表示第i个位置 和 loc 表达意思一致
    	CLinkNode* node = list;//刚开始node指向头结点
    	while (node->next != list && i < loc)
    	{
    		node = node->next;
    		i++;
    	}
    	//循环结束 node 指向 loc-1 位置 且 node 不能为尾结点,为什么不能为尾结点?因为不能删除 位置上没有元素的结点!
    	if (i == loc && node->next != list)
    	{
    		CLinkNode* del_node = node->next;//第loc 位置结点
    		*data = del_node->data;//返回删除结点的数据域
    
    		node->next = del_node->next;// 删除结点的 前驱结点 指向删除结点的 后继结点,这样删除位置的结点就不在链表中了
    		free(del_node);//释放空间
    
    	}
    	return OK;
    }
    /*
    展示循环链表元素
    */
    int ShowCLinkList(CLinkList list)
    {
    	if (list == NULL)
    	{
    		return ERROR;
    	}
    	CLinkNode* target = NULL;
    	printf("--------循环链表元素------\n");
    	for (target = list->next; target != list; target = target->next)
    		printf("%d \t",target->data);
    	printf("\n");
    	return OK;
    }
    /*
    获取链表元素个数
    */
    int LengthCLinkList(CLinkList list)
    {
    	if (list == NULL)
    	{
    		return ERROR;
    	}
    	CLinkNode* target = NULL;
    	int length = 0;
    	for (target = list->next; target != list; target = target->next)
    		length++;
    	printf("循环链表元素个数:%d\n", length);
    	return OK;
    }
    /*
    获取根据数据获取结点的位置
    */
    int IndexCLinkList(CLinkList list,int data)
    {
    	if (list == NULL)
    	{
    		return ERROR;
    	}
    	CLinkNode* target = NULL;
    	int length = 0;
    	int index = -1;
    	for (target = list->next; target != list; target = target->next)
    	{
    		length++;
    		if (target->data == data)
    		{
    			index = length;
    		}
    	}
    	if (index == -1)
    	{
    		printf("数据%d在循环链表中不存在\n", data);
    	}
    	else
    	{
    		printf("数据%d在第%d个位置\n", data, index);
    
    	}
    	return index;
    }
    /*
    获取第i个结点的数据内容
    */
    int IndexOfCLinkList(CLinkList list, int index)
    {
    	if (list == NULL || index < 1)
    	{
    		return ERROR;
    	}
    	CLinkNode* target = NULL;
    	int length = 0;
    	int data = -1;
    	for (target = list->next; target != list; target = target->next)
    	{
    		length++;
    		if (length == index)
    		{
    			data = target->data;
    		}
    	}
    	if (index > length)
    	{
    		printf("第%d个位置结点不存在\n", index);
    	}
    	else
    	{
    		printf("第%d个位置的数据:%d\n", index,data);
    	}
    	return data;
    }
    int main(int argc, char *argv[])
    {
    	int flag = 0;
    	CLinkList list = NULL;
    	while (1)
    	{
    		printf("===============循环链表功能菜单===========\n");
    		printf("===============1、初始化循环链表==========\n");
    		printf("===============2、插入元素================\n");
    		printf("===============3、删除元素================\n");
    		printf("===============4、展示元素================\n");
    		printf("===============5、循环链表元素个数========\n");
    		printf("===============6、根据数据查询结点位置====\n");
    		printf("===============7、根据位置查询结点数据====\n");
    		printf("===============0、退出菜单================\n");
    		scanf("%d", &flag);
    		//fflush(stdin);
    		if (flag == 0)
    			break;
    		if (flag == 1)
    		{
    			list = NULL;
    			InitCLinkList(&list);
    			ShowCLinkList(list);
    		}
    		else if(flag == 2)
    		{
    			int loc = 0;
    			int data = 0;
    			printf("请输入插入元素的位置和数据:\n");
    			scanf("%d", &loc);
    			scanf("%d", &data);
    			InsertCLinkNode(list, loc, data);
    			ShowCLinkList(list);
    		}
    		else if (flag == 3)
    		{
    			int loc = 0;
    			int data = 0;
    			printf("请输入删除元素的位置:\n");
    			scanf("%d", &loc);
    			DelCLinkNode(list, loc, &data);
    			ShowCLinkList(list);
    		}
    		else if (flag == 4)
    		{
    			ShowCLinkList(list);
    		}
    		else if (flag == 5)
    		{
    			LengthCLinkList(list);
    		}
    		else if (flag == 6)
    		{
    			int loc = 0;
    			printf("请输入查找元素的位置:\n");
    			scanf("%d", &loc);
    			IndexOfCLinkList(list,loc);
    		}
    		else if (flag == 7)
    		{
    			int data = 0;
    			printf("请输入查找元素的数据:\n");
    			scanf("%d", &data);
    			IndexCLinkList(list, data);
    		}
    	}
    	return 0;
    }
    

    验证结果截图:






    展开全文
  •  我们知道,线性表就是n个数据元素的有限序列,它有两种实现方式,其一为顺序表,即数组+伪指针的方式实现,另一为链表,采用的是指针的方式实现。由于顺序表的知识偏向基础且其应用灵活性不高,故在此不再介绍,...

        最近在学习严蔚敏教授的《数据结构》,有一些感想,在这里写下来,留做笔记,希望能对以后学习有所帮助。

        我们知道,线性表就是n个数据元素的有限序列,它有两种实现方式,其一为顺序表,即数组+伪指针的方式实现,另一为链表,采用的是指针的方式实现。由于顺序表的知识偏向基础且其应用灵活性不高,故在此不再介绍,本文主要说明几种常用的链表是如何实现的以及其基本操作。

    1.单链表:

        单链表节点结构可以用右图表示:单链表节点结构

        一个完整的单链表如下图:

            一个完整的单链表

          由此可见,链表每一个节点都是由数据域和指针域构成的,每一个指针域指向下一个节点,每个节点的数据域存储相应的数据,(头节点除外,一般头节点不存储任何数据,但也可以用来存储表长等信息),最后一个节点的指针域指向NULL,即空,表示链表结束。由于单链表的这种特性,想访问单链表中任何一个元素都必须通过头结点层层往下遍历,因此头节点是链表中最重要的节点,没有头节点就无法访问整个链表。这也是链表和顺序表最大的不同,顺序表是数组实现,访问节点以及返回表长都很容易实现,但是它没有动态分配空间的功能,只能一开始初始化一个较大的空间以便以后利用,一旦填满,则顺序表不能再插入元素,而链表则可以动态改变长度,加之指针的方式使得其遍历速度极为高效,其灵活性和可靠性使得链表成为线性表的主要实现方式,也是栈和队列等重要数据结构类型的基础。

        单链表的数据元素插入原理:

              单链表的数据元素插入原理

        若要在第i个位置上插入数据,则需要遍历单链表到第i-1个位置,然后利用malloc()函数向系统请求空间开辟新节点T

            1.先使得T的指针域 指向 第i-1个数据的指针域指向的位置(即第i个元素)

            2.再让第i-1个数据的指针域 指向 T;

            3.以上两步千万不能颠倒顺序,否则将使得整个链表丢失i位置后的所有数据元素;

        单链表的数据元素删除原理:

            单链表的数据元素删除原理

        若要删除第i个位置上的数据,也需遍历到第i-1个位置,然后利用malloc()函数向系统请求开辟新节点P

            1.P的指针域 指向 第i-1的指针域指向的位置(即第i个元素);

            2.第i-1个元素指针域 指向 第i个元素的指针域指向的位置(即第i+1个元素);

            3.释放P节点占用的空间(即删除了第i个节点);

        

        还有一些其他的操作,比如获得某个位置上的节点,返回单链表长度,清空/销毁链表,遍历整个链表,都是简单的方法,理解了指针就不难写,原理在此不提,关于单链表的代码,就在这里放出一段简单的实例:

    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    using namespace std;
    
    typedef struct Node
    {
        int data;
        struct Node *next;
    }*LinkedList,LNode;
    
    void CreatLinkedList(LinkedList &L,int n)   //尾插法创建单链表;
    {
        L = (LinkedList)malloc(sizeof(LNode));  //初始化;
        L->next = NULL;
        L->data = 0;
        LinkedList Tail = L;    //尾指针;
        cout<<"Enter "<<n<<" number(s)"<<endl;
        for(int i = 0 ; i < n; i++)
        {
            LinkedList Temp = (LinkedList)malloc(sizeof(LNode));
            cin>>Temp->data;
            Tail->next = Temp;
            Tail = Temp;
            Temp = NULL;
            L->data++;  //计数;
        }
        Tail->next = NULL;
    }
    
    bool GetElem(int &e,int i,LinkedList L) //获取结点;
    {
        while(L != NULL && i > 0)
        {
            i--;
            L = L->next;
        }
        if(i == 0 && L != NULL) //i=1时也有可能同时满足退出while的条件;
        {
            e = L->data;
            return true;
        }
        else return false;
    }
    
    bool InsertElem(int e,int i,LinkedList L)   //插入结点;
    {
        if(i > L->data+1 || i < 1)    return false;
        else
        {
            L->data++;
            while(i > 1)
            {
                i--;
                L = L -> next;
            }
            LinkedList Temp = (LinkedList)malloc(sizeof(LNode));
            Temp->data = e;
            Temp->next = L->next;
            L->next = Temp;
            Temp = NULL;
            return true;
        }
    }
    
    bool DeleteElem(int i,LinkedList L) //删除结点;
    {
        if(i > L->data || i < 1)    return false;
        else
        {
            L->data--;
            while(i > 1)
            {
                i--;
                L = L->next;
            }
            LinkedList Temp = (LinkedList)malloc(sizeof(LNode));
            Temp = L->next;
            L->next = Temp->next;
            free(Temp);
            Temp = NULL;
            return true;
        }
    }
    
    bool DestoryLinkedList(LinkedList &L)   //销毁单链表;
    {
        if(L->next != NULL)
            DestoryLinkedList(L->next);
        free(L);
        L = NULL;
        return true;
    }
    
    bool ClearLinkedList(LinkedList &L) //清空单链表;
    {
        DestoryLinkedList(L->next);
        L->next = NULL;
        L->data = 0;
        return true;
    }
    
    void GetLinkedList(LinkedList L)    //遍历单链表;
    {
        LinkedList Head = L->next;
        while(Head != NULL)
        {
            cout<<Head->data<<endl;
            Head = Head->next;
        }
    }
    
    int main()
    {
        int n,i,Elem;
        bool Flag;
        LinkedList L;
        cout<<"How many Elem(s) do you want to creat?"<<endl;
        cin>>n;
        CreatLinkedList(L,n);
        cout<<"Here is what they look like:"<<endl;
        GetLinkedList(L);
        cout<<"Which position of Elem do you want?"<<endl;
        cin>>i;
        Flag = GetElem(Elem,i,L);
        if(Flag == true)
            cout<<Elem<<endl;
        else
            cout<<"No maching Elem"<<endl;
        cout<<"What Elem you wanna insert , and where?"<<endl;
        cout<<"Elem :";
        cin >>Elem;
        cout<<"Position :";
        cin>>i;
        Flag = InsertElem(Elem,i,L);
        if(Flag == true)
        {
            cout<<"Succeeded!"<<endl;
            GetLinkedList(L);
        }
        else
            cout<<"Failed!"<<endl;
        cout<<"Which position of Elem do you want to delete :"<<endl;
        cin>>i;
        Flag = DeleteElem(i,L);
        if(Flag == true)
        {
            cout<<"Succeeded!"<<endl;
            GetLinkedList(L);
        }
        else
            cout<<"Failed!"<<endl;
        if(ClearLinkedList(L))   cout<<"LinkedListed Cleared!"<<endl;
        GetLinkedList(L);   //验证是否清空;
        if(DestoryLinkedList(L))    cout<<"LinkedList Destoryed!"<<endl;
        if(L == NULL) cout<<"Check"<<endl; //验证是否销毁;
        return 0;
    }
    

     

    2.循环链表

        和单链表极其相似的一种结构就是循环链表了,它的节点结构和单链表一模一样,唯一的区别就是它最后一个数据元素不指向NULL,而是指向头指针,这样的链表构成了一个环,因此成为循环链表。

        一个完整的循环链表如下图:

                一个完整的循环链表

        循环链表的操作和单链表基本一致,差别仅在于算法中的循环条件不是L或L->为空,而是它们是否等于头指针,因为当循环到头指针,说明链表已经完整遍历一次,下面给出代码:

    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    using namespace std;
    
    typedef struct LNode
    {
        int data;
        struct LNode *next;
    }*CircleLinkedList,LNode;
    
    void CreatLinkedList(CircleLinkedList &L,int n)   //尾插法创建循环链表;
    {
        L = (CircleLinkedList)malloc(sizeof(LNode));  //初始化;
        L->next = NULL;
        L->data = 0;
        CircleLinkedList Tail = L;    //尾指针;
        cout<<"Enter "<<n<<" number(s)"<<endl;
        for(int i = 0 ; i < n; i++)
        {
            CircleLinkedList Temp = (CircleLinkedList)malloc(sizeof(LNode));
            cin>>Temp->data;
            Tail->next = Temp;
            Tail = Temp;
            L->data++;
        }
        Tail->next = L;
    }
    
    bool GetElem(int &e,int i,CircleLinkedList L) //获取结点;
    {
        CircleLinkedList Head = L;
        while(L->next != Head && i > 0)
        {
            i--;
            L = L->next;
        }
        if(i == 0 && L != Head) //i=1时也有可能同时满足退出while的条件;
        {
            e = L->data;
            return true;
        }
        else return false;
    }
    
    bool InsertElem(int e,int i,CircleLinkedList L)   //插入结点;
    {
        if(i > L->data+1 || i < 1)    return false;
        else
        {
            L->data++;
            while(i > 1)
            {
                i--;
                L = L -> next;
            }
            CircleLinkedList Temp = (CircleLinkedList)malloc(sizeof(LNode));
            Temp->data = e;
            Temp->next = L->next;
            L->next = Temp;
            return true;
        }
    }
    
    bool DeleteElem(int i,CircleLinkedList L) //删除结点;
    {
        if(i > L->data || i < 1)    return false;
        else
        {
            L->data--;
            while(i > 1)
            {
                i--;
                L = L->next;
            }
            CircleLinkedList Temp = (CircleLinkedList)malloc(sizeof(LNode));
            Temp = L->next;
            L->next = Temp->next;
            free(Temp);
            Temp = NULL;
            return true;
        }
    }
    
    bool DestoryCircleLinkedList(CircleLinkedList &L,CircleLinkedList Head)    //销毁循环链表;
    {
        if(L->next != Head)
            DestoryCircleLinkedList(L->next,Head);
        free(L);
        L = NULL;
        return true;
    }
    
    bool ClearCircleLinkedList(CircleLinkedList &L,CircleLinkedList Head)   //清空循环链表;
    {
        DestoryCircleLinkedList(L->next,Head);
        L->next = Head;
        L->data = 0;
        return true;
    }
    
    void GetCircleLinkedList(CircleLinkedList L)    //遍历循环链表;
    {
        CircleLinkedList Head = L;
        L = L->next;
        while(L != Head)
        {
            cout<<L->data<<endl;
            L = L->next;
        }
    }
    
    int main()
    {
        int n,i,Elem;
        bool Flag;
        CircleLinkedList L;
        cout<<"How many Elem(s) do you want to creat?"<<endl;
        cin >>n;
        CreatLinkedList(L,n);
        cout<<"Here is what they look like:"<<endl;
        GetCircleLinkedList(L);
        cout<<"Which position of Elem do you want?"<<endl;
        cin >>i;
        Flag = GetElem(Elem,i,L);
        if(Flag == true)
            cout<<Elem<<endl;
        else
            cout<<"No maching Elem"<<endl;
        cout<<"What Elem you wanna insert , and where?"<<endl;
        cout<<"Elem :";
        cin>>Elem;
        cout<<"Position :";
        cin>>i;
        Flag = InsertElem(Elem,i,L);
        if(Flag == true)
        {
            cout<<"Succeeded!"<<endl;
            GetCircleLinkedList(L);
        }
        else
            cout<<"Failed!"<<endl;
        cout<<"Which position of Elem do you want to delete :"<<endl;
        cin>>i;
        Flag = DeleteElem(i,L);
        if(Flag == true)
        {
            cout<<"Succeeded!"<<endl;
            GetCircleLinkedList(L);
        }
        else
            cout<<"Failed!"<<endl;
        if(ClearCircleLinkedList(L,L))   cout<<"CircleLinkedListed Cleared!"<<endl;
        GetCircleLinkedList(L);   //验证是否清空;
        if(DestoryCircleLinkedList(L,L))    cout<<"CircleLinkedList Destoryed!"<<endl;
        if(L == NULL) cout<<"Check"<<endl;    //验证是否销毁;
        return 0;
    }
    

     

    3.双向链表

     

        由于单链表仅具有单向性的特点,我们引入了双向链表来克服这个缺点,顾名思义,双向链表就是能通过当前节点访问下一个/上一个节点的链表结构。

        双向链表的节点结构如下:双向链表的节点结构

        一个完整的双向链表

                一个完整的双向链表

        注:上图中方便起见,将最后一个节点指向NULL,实际上可以指向一个尾指针,这里可以灵活修改

        双向链表的数据元素插入原理:

                双向链表的数据元素插入

        若想在第i个位置上插入数据,则先遍历到第i-1个位置,使用malloc()函数向系统请求一个新节点T

            1.让T->pre 指向 第i-1个节点;

            2.让T->next 指向 第i-1个结点的下一个节点(即第i个节点);

            3.让i->next 指向 T;

            4.让i->pre指向T;(前提是第i个节点非空)

        双向链表的数据元素删除原理:

                双向链表的数据元素删除

     

           若想在第i个位置上插入数据,则先遍历到第i-1个位置,使用malloc()函数向系统请求一个新节点P,且让P指向第i个数据

                1.让P->next->pre 指向 P->pre;(前提是第i+1个节点非空)

                2.让i->next 指向 p->next;

                3.释放P节点所占用的空间;(即删除了第i个节点)

        放出一段双向链表代码实例:

     

    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    using namespace std;
    
    typedef struct LNode
    {
        int data;
        struct LNode *pre;
        struct LNode *next;
    }*DoubleLinkedList,LNode;
    
    void CreatDoubleLinkedList(DoubleLinkedList &L,int n)   //尾插法创建双链表;
    {
        L = (DoubleLinkedList)malloc(sizeof(LNode));
        L->pre = NULL;
        L->next = NULL;
        L->data = 0;
        DoubleLinkedList Tail = L;
        cout<<"Enter "<<n<<" Elem(s) :"<<endl;
        for(int i = 0; i < n; i++)
        {
            DoubleLinkedList Temp = (DoubleLinkedList)malloc(sizeof(LNode));
            cin>>Temp->data;
            Tail->next = Temp;
            Temp->pre = Tail;
            Tail = Temp;
            L->data++;
        }
        Tail->next = NULL;
    }
    
    bool GetElem(int &e,int i,DoubleLinkedList L)   //获取结点;
    {
        while(L != NULL && i > 0)
        {
            i--;
            L = L->next;
        }
        if(i == 0 && L != NULL)
        {
            e = L->data;
            return true;
        }
        else return false;
    }
    
    bool InsertElem(int e,int i,DoubleLinkedList L)    //插入结点;
    {
        if(i > L->data+1 || i < 1)
            return false;
        else
        {
            L->data++;
            while(i > 1)
            {
                L = L->next;
                i--;
            }
            DoubleLinkedList Temp = (DoubleLinkedList)malloc(sizeof(LNode));
            Temp->data = e;
            if(L->next != NULL)
            {
                Temp->next = L->next;
                Temp->pre = L;
                L->next->pre = Temp;
                L->next = Temp;
            }
            else
            {
                Temp->pre = L;
                L->next = Temp;
                Temp->next = NULL;
            }
        }
    }
    
    bool DeleteElem(int i,DoubleLinkedList L)   //删除结点;
    {
        if(i > L->data || i < 1)
            return false;
        else
        {
            L->data--;
            while(i > 1)
            {
                L = L->next;
                i--;
            }
            DoubleLinkedList Temp = (DoubleLinkedList)malloc(sizeof(LNode));
            Temp = L->next;
            if(L->next->next != NULL)
            {
                L->next->next->pre = L;
                L->next = L->next->next;
            }
            else
                L->next = NULL;
            free(Temp);
            Temp = NULL;
            return true;
        }
    }
    
    bool DestoryDoubleLinkedList(DoubleLinkedList &L)   //销毁双链表;
    {
        if(L->next != NULL)
            DestoryDoubleLinkedList(L->next);
        free(L);
        L = NULL;
        return true;
    }
    
    bool ClearDoubleLinkedList(DoubleLinkedList &L)     //清空双链表;
    {
        DestoryDoubleLinkedList(L->next);
        L->next = NULL;
        L->data = 0;
        return true;
    }
    
    void GetDoubleLinkedList(DoubleLinkedList L)    //遍历单链表;
    {
        DoubleLinkedList Head = L->next;
        while(Head != NULL)
        {
            cout<<Head->data<<endl;
            Head = Head->next;
        }
    }
    
    int main()
    {
        int n,i,Elem;
        bool Flag;
        DoubleLinkedList L;
        cout<<"How many Elem(s) do you want to creat?"<<endl;
        cin>>n;
        CreatDoubleLinkedList(L,n);
        cout<<"Here is what they look like:"<<endl;
        GetDoubleLinkedList(L);
        cout<<"Which position of Elem do you want?"<<endl;
        cin>>i;
        Flag = GetElem(Elem,i,L);
        if(Flag == true)
            cout<<Elem<<endl;
        else
            cout<<"No maching Elem"<<endl;
        cout<<"What Elem you wanna insert , and where?"<<endl;
        cout<<"Elem :";
        cin>>Elem;
        cout<<"Position :";
        cin>>i;
        Flag = InsertElem(Elem,i,L);
        if(Flag == true)
        {
            cout<<"Succeeded!"<<endl;
            GetDoubleLinkedList(L);
        }
        else
            cout<<"Failed!"<<endl;
        cout<<"Which position of Elem do you want to delete :"<<endl;
        cin>>i;
        Flag = DeleteElem(i,L);
        if(Flag == true)
        {
            cout<<"Succeeded!"<<endl;
            GetDoubleLinkedList(L);
        }
        else
            cout<<"Failed!"<<endl;
        if(ClearDoubleLinkedList(L))   cout<<"DoubleLinkedListed Cleared!"<<endl;
        GetDoubleLinkedList(L); //验证是否清空;
        if(DestoryDoubleLinkedList(L))    cout<<"DoubleLinkedList Destoryed!"<<endl;
        if(L == NULL)   cout<<"Check"<<endl;    //验证是否销毁;
        return 0;
    }
    

    以上就是要记录的内容了,下面说几点注意的地方:

        1.由于双链表具有双向性,它自然也就有单向性,因此它的清空和删除和单链表完全一致;

        2.循环链表清空删除和单链表不一致,主要体现在二者“空”状态不一致,可见上图;

        3.这里声明的变量:LinkedList a;     a是该结构体类型指针型的变量,见下面定义:

    typedef struct LNode
    {
        int data;
        struct LNode *next;
    }*LinkedList;

        4.关于free()函数,它只能释放由calloc(),malloc(),realloc()申请的动态空间,不可以释放用户自定义的空间,若把上面代码的清空单链表函数改为如下,则相当于没有清空,对单链表没任何影响,我看许多人都犯这个错误,特地写一下:

    bool free_list(LinkedList head)
    {
    	LinkedList pointer;
    	while(head != NULL)
    	{
    		pointer = head;
    		head = head->next;
    		free(pointer);
    	}
            return true;
    }

     

        5.实际上双链表也是有循环双链表的,我在这里不写,原理是一样的,感兴趣可以自己另作研究。

    展开全文
  • 循环链表的三个经典例子

    千次阅读 2018-07-20 16:23:13
    一.约瑟夫问题 据说著名犹太历史学家Josephus有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41个人排成...
  • 循环链表

    千次阅读 2017-09-08 14:50:10
    通常链表都是一条龙,现在首尾相连,使得从结尾又能一下子跳回到开头,这就是循环链表 这里从以下几个方面阐述循环链表: 重要方法分析全部代码 一.重要方法分析 这里的链表实现了我博客中的接口 ...
  • 循环链表的基本操作

    2020-10-11 17:16:13
    定义: typedef struct DuLNode ...构造循环链表 与单链表不同的是L->next = L;而不是L->next = NULL; bool InitDuList(DuLinkList &L) { L = (DuLinkList)malloc(sizeof(DuLNode)); if(L == NULL
  • 单向循环链表的简单实现

    万次阅读 多人点赞 2017-07-15 20:56:45
    单向循环链表:  在单向链表中,头指针是相当重要的,因为单向链表的操作都需要头指针,所以如果头指针丢失或者破坏,那么整个链表都会遗失,并且浪费链表内存空间。 单向循环链表的构成:  如果把单链表的...
  • 循环链表详解

    千次阅读 2019-03-20 10:59:56
    循环链表创建以及排序 1. 创建双链表 完整代码如下 #include<stdio.h> #include<stdlib.h> typedef struct node { int data; struct node *nex; struct node *pre; }NODE; void...
  • 双向链表与循环链表

    千次阅读 2018-09-16 09:04:17
    双向链表 单链表的一个优点是结构简单,但是它也有一个缺点,即在单链表中只能通过一个结点的引用访问其后续结点,而无法直接访问其前驱结点, 要在单链表中找到某个结点的前驱结点,必须从链表的首结点出发依次向...
  • 前段时间学习
  • 循环链表的创建、遍历

    千次阅读 2018-02-19 14:32:38
    循环链表 在单链表中遍历链表时,判断链表终端结点的next指针为空(node-&gt;next=NULL),则表示当前链表遍历完成。 循环链表中,将单链表中的终端结点的指针端由空指针改为指向头结点,就使整个单链表形成一...
  • 链表是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每个节点里存到下一个节点的指针。由于不须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比顺序表O(logn)快得多,但是...
  • 【数据结构】双向循环链表

    万次阅读 2018-08-09 23:14:20
    双向循环链表的结构体定义 初始化双向循环链表 尾插法构建双向循环链表 双向循环链表的后序遍历操作 主函数调用 目录: 目录: 各部分实现: 双向循环链表的结构体定义 初始化双向循环链表 尾插法构建双向...
  • 循环链表中设置尾指针比设置头指针更好的原因

    万次阅读 多人点赞 2016-07-11 21:12:52
    尾指针是指向终端结点的指针,用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便。 设一带头结点的单循环链表,其尾指针为rear,则开始结点和终端结点的位置分别是rear->next->next和rear,查找...
  • 结构体: struct DulNode{  int a;.../*中间是建循环链表和对链表其他操作的代码*/ //前提是s结点是循环链表中的一个结点 void del(struct DulNode * s) {  struct DulNode *q, *p1, *p2;  //
  • 循环链表与循环队列

    万次阅读 2017-03-07 15:37:25
    单向循环链表 和普通的链表结构不同,单向循环链表的最后一个节点的指针指向了头结点,也就是和Head指针有相同的引用 和普通链表相比,循环链表不需要头指针,能够从任意位置实现链表遍历 双向循环...
  • 如何判断一个链表是否为空?

    万次阅读 2018-05-07 22:24:19
    L为指向表头结点的指针,分别写出带有头结点的单链表、单项循环链表和双向循环链表判空的条件单链表 NULL==L-&gt;next单向循环 L==L-&gt;next双向循环 L==L-&gt;next&amp;&amp;L==L-&gt;...
  • 单链表,双链表,循环链表的区别

    千次阅读 2019-02-18 16:45:06
    单向链表(单链表)  单向链表,它包含两个域,一个信息域和一个指针域。这个链接指向表中的下一个节点,而最后一个节点则 指向一个空值NULL。 单向链表只可向一个方向遍历。 查找一个节点的时候需要从第一个节点...
  • 如何判断一个单链表是循环链表

    千次阅读 2014-08-17 20:07:45
    1.循环链表的特点是收尾相接,没有头指针,也没有尾指针。如果去遍历循环链表,则是s
1 2 3 4 5 ... 20
收藏数 216,568
精华内容 86,627
关键字:

循环链表