精华内容
下载资源
问答
  • 循环链表优缺点
    2022-03-26 17:17:38

    这二个结构其实是,相辅相成的结构

    顺序表的优点

    1.物理空间是连续的,方便用下标来访问(但这其实也算是它的缺点,效率比较低)

    2.cpu高速缓存命中率更高

    cpu不会直接访问内存,因为它会嫌弃内存访问太慢,通常都是把数据加载到缓存或寄存器里面,但是由于寄存器不算多,所以特别大的数据是加载在缓存里面的

    cpu会看数据在不在缓存在就叫命中,直接访问,不在就不命中,先把数据加载到缓存在访问

    那么cpu访问有个局部性原理,会访问这个局部,当这个不命中会把下一个局部加载到缓存里,由于顺序表的物理空间是连续的,所以命中高

    顺序表的缺点

    1.由于物理空间连续,空间不够需要扩容。扩容本身就有损耗,而且扩容机制也有损耗(比如要200字节,你扩容了250)因为你无法知道需要多少空间

    2.头部删除或者中部插入删除,挪动数据,效率低。 O(N);

    带头双向循环链表优点

    1.按需申请释放空间。

    2.任意位置可以O(1)任意插入删除数据

    带头双向循环链表缺点

    1.不支持下标的随机访问,有些算法不适合在它上面实现比如:二分查找,排序等等;

    更多相关内容
  • 双向带头循环链表实现代码二、双向带头循环链表优缺点1.双向带头循环链表优缺点2.顺序表优缺点 前言 链表的结构有很多种,其中用的比较多的就是单向不带头不循环链表和双向带头循环链表,这两种链表都有各自应用的...


    前言

    链表的结构有很多种,其中用的比较多的就是单向不带头不循环链表和双向带头循环链表,这两种链表都有各自应用的场合。
    双向带头循环链表结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。今天就用C语言来实现一下带头双向链表的增删查改。


    一、双向带头循环链表

    1.双向带头循环链表结构

    首先:来看一下双向带头循环链表的结构

    在这里插入图片描述
    可以看到双向带头循环链表的每一个节点都与前后相连接,因此组成了一个循环,要实现该结构,需要先创造一个头结点,该头结点的尾指针指向自己,头指针也指向自己,在此基础上实现其他节点的插入和删除。

    1.双向带头循环链表实现代码

    以下是代码部分:
    头文件
    ListNode.h

    #define pragama once
    #include<stdio.h>
    #include<stdlib.h>
    #include<string.h>
    #include<assert.h>
    
    //typedef方便修改结构体变量的类型
    typedef int LTDataType;
    
    //构建链表结构体,结构体变量包括头指针,尾指针及data值
    typedef struct ListNode {
    	
    	struct ListNode* pre;
    	struct ListNode* next;
    	LTDataType data;
    
    }ListNode;
    
    //创建新节点
    ListNode* BuyListNode(LTDataType x);
    //链表初始化->创造头结点
    ListNode* InitListNode();
    //打印链表
    void ListPrint(ListNode* phead);
    //销毁链表
    void ListDistory(ListNode* phead);
    
    //增删查改
    void ListPushBack(ListNode* phead, LTDataType x);
    void ListPushFront(ListNode* phead, LTDataType x);
    void ListPopBack(ListNode* phead);
    void ListPopFront(ListNode* phead);
    ListNode* ListFind(ListNode* phead, LTDataType x);
    void ListInsert(ListNode* pos, LTDataType x);
    void ListErase(ListNode* pos);
    void Listchange(ListNode* pos, LTDataType x);
    

    主体
    ListNode.c

    #include"ListNode.h"
    
    
    
    ListNode* BuyListNode(LTDataType x)
    {
    	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
    	newnode->data = x;
    	newnode->next = NULL;
    	newnode->pre = NULL;
    
    
    	return newnode;
    }
    
    
    ListNode* InitListNode()
    {
    	//构造头结点
    	ListNode* phead = (ListNode*)malloc(sizeof(ListNode));
    	phead->next = phead;
    	phead->pre = phead;
    
    	return phead;
    }
    
    void ListPrint(ListNode* phead)
    {
    	assert(phead);
    
    	//从头结点后开始,到头结点结束
    	ListNode* cur = phead->next;
    	while (cur != phead)
    	{
    		printf("%d", cur->data);
    		cur = cur->next;
    	}
    	printf("\n");
    }
    
    void ListDistory(ListNode* phead)
    {
    	ListNode* cur = phead->next;
    	while (cur != phead)
    	{
    		ListNode* next = cur->next;
    		ListErase(cur);
    		cur = next;
    	}
    	free(phead);
    	phead = NULL;
    }
    
    //以下注释掉的代码段和留下的代码功能是一样的
    void ListPushBack(ListNode* phead, LTDataType x)
    {
    	/*assert(phead);
    
    	ListNode* newnode = BuyListNode(x);
    	ListNode* tail = phead->pre;
    
    	tail->next = newnode;
    	newnode->pre = tail;
    	newnode->next = phead;
    	phead->pre = newnode;*/
    	ListInsert(phead, x);
    }
    
    void ListPushFront(ListNode* phead, LTDataType x)
    {
    	/*assert(phead);
    
    	ListNode* next = phead->next;
    	ListNode* newnode = buyListNode(x);
    
    	newnode->next = next;
    	next->pre = newnode;
    	phead->next = newnode;
    	newnode->pre = phead;*/
    	ListInsert(phead->next, x);
    
    }
    
    void ListPopBack(ListNode* phead)
    {
    	/*assert(phead);
    	assert(phead->next != phead);
    	
    	ListNode* tail = phead->pre;
    	ListNode* tailpre = tail ->pre;
    	
    	tailpre->next = phead;
    	phead->pre = tailpre;
    	
    	free(tail);*/
    	ListErase(phead->pre);
    }
    
    void ListPopFront(ListNode* phead)
    {
    	/*assert(phead);
    	assert(phead->next != phead);
    	
    	ListNode* next = phead->next;
    	ListNode* newnext = next ->next;
    	
    	phead->next = newnext;
    	newnext->pre = phead;
    
    	free(next);*/
    	ListErase(phead->next);
    }
    
    ListNode* ListFind(ListNode* phead, LTDataType x)
    {
    	assert(phead);
    
    	ListNode* cur = phead->next;
    	while (cur != phead)
    	{
    		if (cur->data == x)
    		{
    			return cur;
    		}
    		cur = cur->next;
    	}
    	return NULL;
    }
    
    //POS之前插入
    void ListInsert(ListNode* pos, LTDataType x)
    {
    	assert(pos);
    	ListNode* pospre = pos->pre;
    	ListNode* newnode = BuyListNode(x);
    	
    	pospre->next = newnode;
    	newnode->pre = pospre;
    	newnode->next = pos;
    	pos->pre = newnode;
    
    }
    //pos不能是phead! 否则会破坏双向链表的结构;
    void ListErase(ListNode* pos)
    {
    	assert(pos);
    	ListNode* pospre = pos->pre;
    	ListNode* posnext = pos->next;
    
    	pospre->next = posnext;
    	posnext->pre = pospre;
    	free(pos);
    }
    void Listchange(ListNode* pos, LTDataType x)
    {
    	assert(pos);
    	pos->data = x;
    }
    

    测试代码
    test.c

    #include"ListNode.h"
    
    
    void test()
    {
    	ListNode* phead = InitListNode();
    	ListPushBack(phead, 1);
    	ListPushBack(phead, 2);
    	ListPushBack(phead, 3);
    	ListPushBack(phead, 4);
    	ListPushBack(phead, 5);
    	ListPushFront(phead, 6);
    	ListPrint(phead);
    
    	ListNode* pos = ListFind(phead, 2);
    	ListInsert(pos, 8);
    	ListErase(pos);
    	ListPrint(phead);
    	ListNode* pos2 = ListFind(phead, 4);
    	Listchange(pos2, 9);
    
    	//ListDistory(phead);
    	ListPrint(phead);
    
    }
    int main()
    {
    	test();
    	return 0;
    }
    

    运行结果
    ![在这里插入图片描述](https://img-blog.csdnimg.cn/20210202194546953.png

    二、双向带头循环链表优缺点

    以下双向循环列表的优缺点都是与顺序表和单向不循环链表相比较的,因此同时总结了了下顺序表的优缺点。

    1.双向带头循环链表优缺点

    • 优点:支持任意位置时间复杂度为O(1)的插入和删除,不需要扩容、不存在空间浪费。
    • 缺点:不支持随机访问,缓存命中率相对低。

    2.顺序表优缺点

    优点:

    • 相对而言空间利用率更高,不需要额外空间,占用空间小(链表需要存指针)。
    • 物理空间是连续的。支持随机访问,可以用下标访问(最大优势);缓存命中率较高。

    缺点:

    • 头部或中间插入或删除数据,需要一个一个挪动数据,时间复杂度是O(N)。
    • 空间不够时需要增容,一般增容是按照倍数增加的、因此可能存在一定内存浪费。
    展开全文
  • 单链表、循环链表、双向循环链表总结

    千次阅读 多人点赞 2019-11-23 18:56:31
    链表介绍 不带头结点的单向链表 带头结点的单向链表 循环链表 双向循环链表

    链表介绍

    结点的概念:

    一个结点包含两个信息,一个是数据域和一个是指针域:

    • 数据域存储该结点的数据信息
    • 指针域存储其直接后继的位置,其示意图如下:
      在这里插入图片描述

    链表的概念:

    每个结点的存储单元是独立的,若干个结点通过指针域依次相链接可构成一个链表,这样的结构称为线性表的链式存储,简称链表。其示意图如下:
    在这里插入图片描述

    为了能够表示链表的开始和结束,需要增加头指针L表示链表的开始,而指针域设置为NULL表示结点的结束。

    不带头结点的单向链表

    在这里插入图片描述
    不带头结点的单向链表是最原始的链表,其头指针指向第一个数据元素,若是空链表其头指针的值为NULL。
    在这里插入图片描述
    由于不带头结点的链表在第一个元素插入和删除时带来不方便,因此链表初始化时,我们都需要增加一个头结点,并令头指针指向头结点,后续的链表默认都是带头结点的。其区别参见这篇文章 链表头结点和不带头结点的区别

    带头结点的单向链表

    在没有特殊指明情况下,我们创建的链表默认都应该带头结点,其初始化状态为如下图所示:
    在这里插入图片描述
    带有数据元素的链表示意图:
    在这里插入图片描述

    循环链表

    循环链表是单向链表的一种特殊形式,可以用于解决约瑟夫环问题。循环链表的最后一个结点的后继指向的是头结点,而不是NULL。其空循环链表的示意图如下:
    在这里插入图片描述
    带有数据元素的循环链表示意图如下:
    在这里插入图片描述

    在某些特殊情况下(比如需要频繁以追加方式插入新结点),我们可以令头指针指向最后一个结点,或者新增加一个尾指针一直指向最后一个结点,其示意图如下:
    在这里插入图片描述
    当头指针指向最后一个结点时或者增加尾指针,可以使得查找链表的开始结点和最后一个结点都方便,其执行时间为O(1). 而在一般情况下,其执行时间为O(n)。

    双向循环链表

    单向链表存在一个弊端就是,当需要获取某个结点p的前驱时,需要从头指针开始遍历链表,获得“前驱”的执行时间为O(n),为了克服单向链表的这种缺点,可以利用双向链表。

    在双向链表中有两个指针域,一个是指向前驱结点的prev,一个是指向后继结点的next指针。下图是空的双向循环链表示意图:

    在这里插入图片描述

    带有数据元素的双向循环链表示意图如下:

    在这里插入图片描述

    双向循环链表的插入和删除结点执行时间均为O(1),为常量级。和其他结构的链表体现了其优越性。

    总结

    以下这张是带头结点的单链表、循环链表以及双向循环链表的总结:

    在这里插入图片描述

    展开全文
  • 数组与链表优缺点

    2020-10-19 11:03:39
    数组和链表是我们在开发过程中最常见的数据结构(树:“有被冒犯到!”),面试种惊颤有提到的数组查询快,增删慢;链表查询慢,增删快 那么,为什么哪?我们今天就来一个追根探底。 首先,我们需要明确一点,数组...

    数组和链表是我们在开发过程中最常见的数据结构(树:“有被冒犯到!”),面试种惊颤有提到的数组查询快,增删慢;链表查询慢,增删快

    那么,为什么哪?我们今天就来一个追根探底。

    首先,我们需要明确一点,数组查询快,链表查询慢,这句话表达是不准确的。正确的描述应该是数组支持随机查询,根据首地址+下标的查询,时间复杂度位O(1),查询效率快,链表不支持随机查询,必须从第一个开始遍历,时间复杂度为0(N),查询效率慢
    在这里插入图片描述

    在内存中,数组是一整块连续的区域,链表是随机分散在内存中。我们需要知道的是计算机会给每一个内存单元分配一个地址,当我们需要随机查询某个数据时,计算机会根据寻址公式:目标地址=首地址+i*元素大小。

    因为数组是连续的,因此我们可以根基首地址+下标得到目标地址,而链表只能根据链表的记录,从首地址进行遍历查询。

    其次数组增删慢,链表增删快,这句话表述的也不准确。
    在这里插入图片描述

    链表中的元素会保存两个属性,一个是值,一个是下一个元素的指针,当需要插入或者删除时,只需要更改相信元素的指针就可以了。

    数组的增删比较复杂,插入数据时,待插入位置的的元素和它后面的所有元素都需要向后搬移,删除数据时,待删除位置后面的所有元素都需要向前搬移。在尾部插入或者删除元素时,数组的增删和链表的增删速度都是O(1),另外数组还涉及到扩容。

    数组的缺点:需要提前设置好内存大小,如果设置的大小不合适,可能会浪费内存空间。

    数组应用场景:
    1、数据量可控,大小稳定,变动小;
    2、经常做的运算是按序号访问数据元素;
    链表应用场景:
    1、数据大小位置;
    2、频繁做插入删除操作;

    链表家族

    单链表:单链表的元素有两个属性,一个是值,一个是指向下一个元素
    双向链表:双向链表的元素有三个属性,一个是值,一个是指向下一个元素,一个是指向上一个元素
    循环链表:循环链表值得是链表的尾节点指向的下一个元素的地址是链表的首节点

    展开全文
  • 4、无头单向非循环链表一般不会单独用来存放数据,实际中更多是作为其他数据结构的子结构,例如哈希桶、图的邻接矩阵。5、带头双向循环链表一般用在单独存放数据,也是实际中常用的链表数据结构。...
  • 4--循环链表

    千次阅读 2016-04-19 15:29:41
    循环链表的定义:将单链表中最后一个数据元素的next指针指向第一个元素 循环链表拥有单链表的所有操作: 创建链表 销毁链表 获取链表长度 清空链表 获取第pos个元素操作 插入元素到位置pos 删除位置...
  • 数据结构系列前言: 数据结构作为程序员的基本知识,需要我们每个人牢牢掌握。近期我也展开了对数据结构的二次...链表是一种物理存储单元上非线性、非连续性的数据结构(它在数据逻辑上是线性的),它的每个节点由两
  • 顺序表和链表优缺点

    千次阅读 2021-06-21 09:24:36
    链表(带头双向循环链表) 定义:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。 优点: 按需分配内存,需要存储一个数据时,就申请一块空间,不会存在...
  • 数组和链表优缺点总结
  • 主要介绍了C++的循环链表与双向链表设计的API实现,文中的示例对于链表结点的操作起到了很好的说明作用,需要的朋友可以参考下
  • 顺序表和链表优缺点(图解)

    千次阅读 2022-04-03 23:01:32
    顺序表: 首先我们先来随意定义一个顺序表 #include<stdio.h> typedef int SLDataType; typedef struct SeqList { SLDataType* arr;//指向开辟的数组 size_t size;...但是缺点也是显而易见
  • 初阶数据结构 —— 顺序表和链表(带头双向循环链表)的优缺点 + CPU缓存的知识。
  • 单向链表优缺点: 1、优点:单向链表增加删除节点简单。遍历时候不会死循环; 2、缺点:只能从头到尾遍历。只能找到后继,无法找到前驱,也就是只能前进。 双向链表优缺点: 1、优点:可以找到前驱和后继,可进...
  • 单向链表和双向链表优缺点及使用场景

    万次阅读 多人点赞 2018-09-28 16:16:39
    遍历时候不会死循环缺点:只能从头到尾遍历。只能找到后继,无法找到前驱,也就是只能前进。 适用于节点的增加删除。 双向链表:有两个指针,一个指向前一个节点,一个后一个节点。 优点:可以找到前驱和...
  • 单链表的优缺点_链表优缺点

    千次阅读 2020-09-15 00:11:54
    单链表的优缺点Here you will learn about advantages and ... 在这里,您将了解链表优缺点。 It is a data structure in which elements are linked using pointers. A node represents an element in link...
  • 线性表 遍历查找比较简便 插入删除很复杂 链表 跟线性表相反 链表的分类有,单链表,双向链表,循环链表 双向链表就是每一个结点有两个指针pre和next指针,分别指向前驱结点和后继结点
  • 转载于:https://www.cnblogs.com/FengZeng666/p/9425117.html
  • 若是不清楚链表的结构,该篇文章不适合观看,这里只做文字说明,没有链表结构的图示
  • 单链表实现双向循环链表单向链表存在一个弊端就是,当需要获取某个结点p的前驱时,需要从头指针开始遍历链表,获得“前驱”的执行时间为O(n),为了克服单向链表的这种缺点,可以利用双向链表。在双向链表中有两个...
  • 循环链表与双向链表

    2021-11-28 14:34:14
    线性表顺序存储的缺点在于插入和删除操作时需要移动大量元素时间复杂度为O(n),线性表的长度也难以适应变化较大的情况,且线性表的扩容需要重新开辟出一块满足大小需求且连续的空间,这容易造成空间碎片。...
  • 双向循环链表,顾名思义就是在双向链表的基础上,将尾节点的“right”指针指向头结点,同时头结点的“left”指针指向尾节点,它和双向链表的不同是,其判断节点是否遍历完毕的条件不再是是否为空,而是是否回到了头...
  • 2.3 静态链表 循环链表 双向链表 (注意:所有代码均已成功测试。编译环境:devC++) 1. 静态链表 用数组描述的链表叫做静态链表,又称游标实现法。 首先,让数组的元素都是由两个数据域组成,data和cur。即为,数组的...
  • 顺序表优点: 1.按下标进行随机访问(比如二分查找,和方便一些排序) 顺序表缺点 1.空间不够需要增容(增容其实算是...链表缺点 1.不支持按下标随机访问 总结:两数据结构是相辅相成的,没有谁是完美的...
  • 【线性表】顺序表和链表优缺点

    千次阅读 2022-03-27 11:44:33
    【线性表】顺序表和链表优缺点
  • C语言之链表:单向链表,循环链表,双向链表 提起链式存储结构,其与数组是两个非常基础的数据结构,每当提到链式存储结构时,一般情况下我们都会将其与数组放到一块儿来比较。 对于数组与链表,从结构上来看,数组...
  • 数据结构-线性表(四)循环链表 本文介绍了单循环链表和双循环链表以及它们的代码实现; 还详细对比了顺序表和链表以及如何选取。
  • 链表,是Java中的一种重要的链式数据结构。 众所周知,我们日常用手机电脑收发信息,下载视频和软件,都要进行数据的传输。这些数据都要以一种特定的数据结构来进行传输和存储,否则数据将会是一串毫无意义的0和1,...
  • 链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的. 定义结点和链表 结点定义(1)值(2)next下一个结点的地址 链表的定义定义头 typedef int SListDataType; //...
  • 双链表-循环链表-静态链表.pdf
  • n个链表有指针链组成一个链表。 单链表 --每个结点只有一个指针域。 二、使用步骤 1.单链表存储结构 代码如下(示例): typedef struct lnode { ElemType date; struct lnode* next; }lnode,*linklist;

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 60,704
精华内容 24,281
关键字:

循环链表优缺点