精华内容
下载资源
问答
  • 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),为常量级。和其他结构的链表体现了其优越性。

    总结

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

    在这里插入图片描述

    展开全文
  • 单向循环链表 代码实现 class Node(object): '''设置节点''' def __init__(self,item): self.item = item # 节点的数据区 self.next = None # 节点的链接区 class SinCycLinkList(object): '''单项循环节点''' ...

    单向循环链表

    循环链表
    循环链表是一种特殊的单链表。实际上,循环链表也很简单。它跟单链表唯一的区别就在尾结点。我们知道,单链表的尾结点指针指向空地址,表示这就是最后的结点了。而循环链表的尾结点指针是指向链表的头结点。从我画的循环链表图中,你应该可以看出来,它像一个环一样首尾相连,所以叫作“循环”链表。
    在这里插入图片描述
    操作
    is_empty() 判断链表是否为空
    length() 返回链表的长度
    travel() 遍历
    add(item) 在头部添加一个节点
    append(item) 在尾部添加一个节点
    insert(pos, item) 在指定位置pos添加节点
    remove(item) 删除一个节点
    search(item) 查找节点是否存在

    其代码实现

    class Node(object):
        '''设置节点'''
        def __init__(self,item):
            self.item = item # 节点的数据区
            self.next = None # 节点的链接区
    class SinCycLinkList(object):
        '''单项循环节点'''
        def __init__(self,node = None):
            self.head = node # 设置首节点
            if node:
                node.next = node
    
        def is_empty(self):
            """判断链表是否为空"""
            if self.head == None:
                return True
            return False
    
        def length(self):
            """返回链表的长度"""
            cur = self.head # 设置游标cur指向头节点
            count = 1
            if self.is_empty(): # 判断链表是否为空
                return 0
            else:  # 链表不为空时
                while cur.next!= self.head: # 将游标移动到最后一个节点处,注意这里设置的是count= 1,是因为循环的时候游标在最后一个指向
                    count += 1
                    cur = cur.next
            return count # 返回count
    
        def travel(self):
            """遍历链表"""
            if self.is_empty(): # 判空
                return None
            else: # 当链表不为空时
                cur = self.head
                while cur.next != self.head:
                    print(cur.item,end = ' ')
                    cur = cur.next # 这里循环到最后一个节点处
                print(cur.item) # 打印最后一个节点的数据区
    
        def add(self, item):
            """链表头部添加元素"""
            node = Node(item) # 创建新节点
    
            if self.is_empty(): # 判空,如果为空
                self.head = node # 将新节点赋值给头节点
                node.next = self.head # 由于是单向循环链表,构成循环
    
            else: # 如果不为空
                cur = self.head # 将链表指向头节点
                while cur.next != self.head:
                    cur = cur.next # 将节点循环到最后一个节点处
                node.next = self.head # 将原来的头节点赋值给新节点的链接区
                self.head = node # 将新节点赋值给头节点
                cur.next = node # 新头节点和尾节点构成循环
    
        def append(self, item):
            """链表尾部添加元素"""
            node = Node(item) # 创建新节点
            if self.is_empty(): # 判空
                self.add(item) # 如果为空,就给头部添加
            else: # 如果不为空时
                cur = self.head # 设置cur游标指向头节点
                while cur.next != self.head:
                    cur = cur.next # 循环到最后一个节点处
                node.next = self.head # 将头节点赋值给新节点的链接区
                cur.next = node # 将新节点赋值给原尾节点的链接区
    
        def insert(self, pos, item):
            """指定位置添加元素"""
    
            if pos <= 0: # pos 为要添加到的位置,这里和单链表一样,按照坐标轴的顺序,当插入的位置小于0时,就默认判断给第一位添加
                self.add(item)
            elif pos > self.length() - 1: # # 当插入的位置大于链表长度时,默认给链表最后一位添加
                self.append(item)
            else: # 当添加的位置在链表长度之内时
                node = Node(item) # 创建新节点
                pre = self.head # pre为要添加位置的上一个节点,设置初始值为None
                count = 0
                while count < pos - 1:
                    count += 1
                    pre = pre.next # 将pre循环到要添加位置的上一个节点处
                node.next = pre.next # 将pre节点的链接区赋值给新节点的链接区
                pre.next = node # 将新节点指向pre的链接区
    
        def search(self, item):
            """查找节点是否存在"""
            if self.is_empty():# 判空
                return False
            else:
                cur = self.head # 设置游标为头节点
                while cur.next != self.head:
                    if cur.item == item: # 判断要查找的数据与节点数据区比较
                        return True
                    else:
                        cur = cur.next # 循环节点
                if cur.item == item: # 上面循环指向完之后游标指向尾节点
                    return True
                return False
    
        def remove(self, item):
            """删除节点"""
            if self.is_empty(): # 判空
                return
            cur = self.head # 设置游标
            pre = None # 设置要移除节点的上一个节点
    
            # 头节点是要删除的
            if cur.item == item:
                if cur.next != self.head: # 当链表长度不为1时
                    while cur.next != self.head:
                        cur = cur.next # 循环到最后一个节点
                    cur.next = self.head.next # 将头节点的链接区指向最后一个节点的链接区,构成循环
                    self.head = cur.next # 将尾节点的链接区指向首节点
            else:  # 头节点不是要删除的,这里和单链表一样
                while cur.next != self.head:
                    if cur.next == item :
                        pre.next = cur.next
                    else:
                        pre = cur
                        cur = cur.next
                if cur.item == item:# 最后循环到最后一个节点处,比较尾节点的数据区与要查找的数据
                    pre.next = cur.next
    

    在这里说明一下,只要是要循环到尾节点的操作的函数内,都要先判空,而且还要注意循环到尾节点处,尾节点的数据区还没有判断

    展开全文
  • 若是不清楚链表的结构,该篇文章不适合观看,这里只做文字说明,没有链表结构的图示
  • 循环链表: ①判空条件为:p==plist或者p->next==NULL; ②判断结尾不同:循环链表的结尾又回到了头(是一个圈圈一样的循环):p==plist;而单链表的结尾时NULL:p==NULL。 ③循环链表可以从一个结点到达任意...
  • 循环链表与双向链表

    2021-11-28 14:34:14
    线性表的顺序存储结构(例如:数组),存储空间是连续的因此我们不用担心元素之间的逻辑关系,线性表最大优点在于可以快速的存取表中任一位置的元素。 线性表顺序存储的缺点在于插入和删除操作时需要移动大量元素...
  • 链表,是Java中的一种重要的链式数据结构。 众所周知,我们日常用手机电脑收发信息,下载视频和软件,都要进行数据的传输。这些数据都要以一种特定的数据结构来进行传输和存储,否则数据将会是一串毫无意义的0和1,...
  • 目录1 单链表节点实现单链表操作单链表实现测试链表与顺序表对比2 单向循环链表操作实现测试3 双向链表操作实现测试 1 单链表 单向链表也叫单链表,是链表中最简单的一种形式,它的每个节点包含两个域,一个信息域...
  • 说明 相比Linux内核链表宿主结构可有多个链表结构的优点,本函数集侧重封装性和易用性,而灵活性和效率有所降低. 可基于该函数集方便地构造栈或队列集. 本函数集暂未考虑并发保护. 一 概念 链表是一种物理存储单元上非...
  • 双向循环链表,顾名思义就是在双向链表的基础上,将尾节点的“right”指针指向头结点,同时头结点的“left”指针指向尾节点,它和双向链表的不同是,其判断节点是否遍历完毕的条件不再是是否为空,而是是否回到了头...
  • 双向链表和循环链表的区别

    千次阅读 2020-11-14 11:01:03
    双向链表: 1、为了方便编程,以及节点的插入删除,可以在首尾增加一个空节点,方便一系列的操作和判断,最后一个节点指针指向空数据的节点或者指向空。 2、双向链表在访问元素时,可以从任何结点开始...3、循环链表
  • 2.3 静态链表 循环链表 双向链表 (注意:所有代码均已成功测试。编译环境:devC++) 1. 静态链表 用数组描述的链表叫做静态链表,又称游标实现法。 首先,让数组的元素都是由两个数据域组成,data和cur。即为,数组的...
  • 4--循环链表

    千次阅读 2016-04-19 15:29:41
    循环链表的定义:将单链表中最后一个数据元素的next指针指向第一个元素 循环链表拥有单链表的所有操作: 创建链表 销毁链表 获取链表长度 清空链表 获取第pos个元素操作 插入元素到位置pos 删除位置...
  • python数据结构之循环单链表的增删改查
  • 用C++和Java实现带头节点的双向循环链表,要继承linearList类,并实现它的所有功能,另外,必须实现双向迭代器。 实现带头节点的双向循环链表,要具有以下的功能: 判断表是否为空,如果为空则返回true,不空返回...
  • 循环链表的作用

    千次阅读 2019-07-26 10:30:29
    作用是循环链表是无须增加存储量,仅对表的链接方式稍作改变,即可使得表处理更加方便灵活。 ①循环链表中没有NULL指针。涉及遍历操作时,其终止条件就不再是像非循环链表那样判别p或p->next是否为空,而是判别...
  • n个链表有指针链组成一个链表。 单链表 --每个结点只有一个指针域。 二、使用步骤 1.单链表存储结构 代码如下(示例): typedef struct lnode { ElemType date; struct lnode* next; }lnode,*linklist;
  • C语言之链表:单向链表,循环链表,双向链表 提起链式存储结构,其与数组是两个非常基础的数据结构,每当提到链式存储结构时,一般情况下我们都会将其与数组放到一块儿来比较。 对于数组与链表,从结构上来看,数组...
  • 三、循环链表 总代码: 四、双向循环链表 1、存储方式: 2、插入和删除 3、正向遍历与反向遍历 总代码: 一、单链表 每个数据存储在结点中,单链表负责把这些结点串起来。(主要利用*next指针) 1、存储...
  • 这是双向链表的一个优点。 双向链表:单向链表只能向着一个方向遍历链表节点,而在节点指针域中增加了前向指针的双向链表,则可以向着两个方向遍历节点。这使得双向链表也可以在任何一个节点遍历整个链表。 ...
  • 链表不仅作为链式存储的一种实现方式,还表达了计算机不连续(离散)的存储思想。
  • 【2.4】单向循环链表

    千次阅读 2018-04-17 15:25:26
    一、单向循环链表结构特点。1、所有元素依次衔接,尾部元素链接到首元素。2、适用于环形结构处理的场合。3、便于特定步长循环遍历链表元素。二、单向循环链表的基本结构图。上图分别表示不带头结点和带头结点的单向...
  • 单向循环链表(Java版)单向循环链表(Java版)前面的文章中介绍到单链表,它的尾结点(最后一个结点)的指针域next都是指向null,如下图:单链表的指针域只存储了向后的指针,到了尾结点就无法继续向后的操作。...
  • 双向循环链表

    2019-01-28 11:47:55
    package 双向循环链表; public class DoubleNode {    public static void main(String[] args) {  //创建节点  DoubleNode dn1=new DoubleNode(20);  DoubleNode dn2=new DoubleNode(30);  ...
  • 顺序表和链表优缺点

    千次阅读 2021-06-21 09:24:36
    优点: 由于顺序表是用数组来存储数据,内存空间连续,当访问数据时可以达到使用数组下标的方式随机访问。 CPU高速缓存的命中率高。 解释: 数据保存在内存中,数据是在CPU里进行运算的(逻辑和算术)。但是CPU速度...
  • 很容易可以想到用循环链表来解决这个问题,但是在编写的时候遇到了一些问题。 思想很简单:用iskill=1或0来判断人的状态(1代表被杀,0代表没事),然后循环指针,指到谁谁的iskill改成1。 外层循环:首先你得让...
  • 带头双向循环链表:结构最复杂,一般用在单独存储数据(头尾中间插入删除时间复杂度都为0(1))。 实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来...
  • 双向带头循环链表实现,好兄弟,速看速掌握,附详细代码
  • 数据结构-循环链表

    2022-02-07 10:24:48
    循环链表 循环链表:是一种头尾相接的链表(即:表中最后一个结点的指针域指向头结点,整个链表形成一个环)。 优点:从表中任一结点出发均可找到表中其他结点。 注意: 由于循环链表中没有NULL指针,故涉及遍历操作时,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 59,440
精华内容 23,776
关键字:

循环链表主要优点