首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

数据结构-静态链表及其插入删除操作

什么是静态链表 我们平常提及的链表一般指的是动态链表,是使用指针将一个一个的结点连起来,除了动态链表之外,还有静态链表,这种链表用数组来描述,主要为了解决没有指针或者不用指针的情况下具备链表插入删除操作便捷的特性...静态链表中有一些专属的概念,先贴上图: ?...至此,静态链表就构建完了。...静态链表的插入操作 从上面的图可以看到,其实数组的最后一个元素的cur存的是一般都是1,因为在使用元素构建链表时从第二个元素开始顺序插入,而插入的位置在哪,其实是由cur决定的,都不是顺序存储中由位置决定...静态链表的删除操作 删除操作是一样的,在插入中,插入一个元素影响了使用链和备用链。那么删除一个元素的话也会同时影响这两个链。 ?

1.2K90

【数据结构】静态链表

数据结构之静态链表 静态链表 用数组的方式实现的链表 优点 增,删操作不需要移动大量元素 缺点 不能随机存取 只能由头结点开始依次往后查找 容量固定不变 c代码实现 获取最后一个结点的下标以及获取第一个空闲节点的位置...size=i; break; } } } return size; } 初始化静态链表...next=-2只是为了做一个标记,代表该空间未被占用 //初始化一个静态链表 void initList(StaticList *list) { (*list)[0]=createStart(...这边对空节点进行标记,代表这些节点还未被使用 for(i; i<100; i++) { (*list)[i].next=-2; } } 在最后添加一个节点 //在最后添加数据...,Node; //创建一个头结点 Node createStart() { Node start; start.next=-1; return start; } //初始化一个静态链表

12910
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    数据结构:静态链表

    数据域data用来存放数据元素,也就是通常我们要处理的数据;而游标cur相当于单链表中的next指针, 存放该元素的后继在数组中的下标。我们把这种用数组描述的链表叫做静态链表。...示例代码:(改编自《大话数据结构》) #include using namespace std; #define MAXSIZE 100 typedef int ElemType...; /* 线性表的静态链表存储结构 */ typedef struct Node {     ElemType data;     int cur; //为0时表示无指向 } StaticLinkList...    while(i)     {         i = array[i].cur;         ++j;     }     return j; } /*  在array中第pos个元素之前插入新的数据元素...静态链表在插入和删除操作时不需要移动元素,只需要修改游标,从而改进了在顺序存储结构中插入和删除操作需要移动 大量元素的缺点;但并没有解决连续分配存储带来的表长难以确定的问题;并且失去了顺序存储结构随机存取的特性

    67460

    数据结构(4)双链表,循环链表,静态链表

    和单链表不同的操作在于插入和删除,不同点是双链表的插入和删除需要同时修改两个方向的指针。...循环链表 循环单链表 表尾指向头结点 循环双链表 在什么的双链表的插入和删除操作中,如果p是最后一个结点,那么p->next就是NULL ,但是使用循环链表的话就不会出现那种情况。...静态链表 链表的每个结点在内存中的分布是随机的,静态链表就是建立一个固定的区间,结点在这固定的区间内随机存储。...typedef struct { int data; int next;//下一个元素的数组下标 }SLinkList[MaxSize]; 初始化:把a[0]的next设为-1即可 关于静态链表的其他操作这里不写了...计划从明天开始栈和队列,静态链表这里先大概了解原理,具体实现之后再补。‍️

    43140

    数据结构(05)_链表01(单链表、静态单链表、单向循环链表)

    1.线性表的链式存储结构1.1.链式存储的定义:   为了表示每个数据元素与其直接后继之间的逻辑关系,数据元素除过存储本身的信息之外,还需要存储其后继元素的地址信息。   ...链式存储结构的逻辑结构:   1.2.单链表   单链表中的节点定义: 注意:这里的struct是用来定义一个类,与class的访问属性相反,默认为public单链表的内部结构:头节点在单链表中的意义是...:辅助数据元素的定位,方便插入和删除,因此,头节点不存储实际的数据。   ...1.3.单链表的插入与删除:   插入:    node->value = e; node->next = current->next; Current->next = node...& e) { bool ret = true; index = index % (this->m_length + 1); // 可插入点

    26310

    【数据结构】单链表(Singly Linked List ) && 静态链表(Static list)

    更多精彩尽在微信公众号【程序猿声】 [微信公众号] 数据结构-线性表|顺序表|链表(中) 本节纲要 预备知识 顺序表(Sequential List) 单链表(Singly Linked List )...#define status bool #define ERROR false #define OK true /* * 函数功能:指定位置后插 * 参数说明:phead链表头结点,IData插入的数据...直接看具体代码: /* * 函数功能:指定位置后插 * 参数说明:phead链表头结点,IData插入的数据,index索引 */ status InsertSListNodeBack(Node *...4.3 静态链表的插入操作 前面我们讲动态链表的时候说过,增加和删除一个节点我们可以用malloc()和free()函数(C++可用new和delete)来实现。...写完了这个函数,我们来看看静态表中具体如何插入: //在链表的第i个位置插入元素e void SlistInsert(SLinkList space, int i, ElemType e) {

    2.1K10

    【数据结构】链式家族的成员——循环链表与静态链表

    静态链表是通过数组来描述线性表的链式存储结构,链表中的结点结构与单链表一致,都是由数据域与指针与构成; 但是不同的是,静态链表中的结点的指针域存储的是结点的相对地址,也就是在数组中的下标,这里我们将它称为游标...在静态链表中,下标为0的元素被作为静态链表的头结点,它的数据域中可以不用存放信息,它的游标存放的是链表首元素的数组下标; 虽然静态链表是申请的一块连续的空间,但是表中的各个元素与单链表相同,不需要满足物理位置上相邻...; 2.2 静态链表的初始化 有看过【函数栈帧的创建与销毁】的朋友应该就会知道,我们在内存中申请空间时,申请的空间中会有一些初始的数据,这些初始数据如果我们将它们打印出来的会,会是一些随机的数据,因此为了避免我们创建的静态链表中存在这些随机值...; 2.3 小结 对于静态链表,我们需要掌握以下内容: 静态链表时通过数组实现的一个单链表; 在静态链表中,下标为0的首元素作为静态链表的头结点,数据域中不需要存放任何内容; 与静态顺序表一致,静态链表的大小是不可改变的...,我们需要对其初始化为-2; 静态链表的插入与删除操作与单链表的插入删除操作相同,只需要修改指针,不需要移动元素; 静态链表适用于一些不支持指针的高级语言(如:Basic); 静态链表还适用于数据元素数量固定不变的场景

    46410

    数据结构-单链表的读取,插入与删除

    链表定义: struct ListNode { int value; ListNode *next; }; 单链表读取 在顺序存储结构中,比如数组中,想要获取某一个位置的数据是非常容易的一件事,...但是在链表中却要麻烦一些,因为链表的存储单元并不是连续的,而且我们只知道链表的头结点,也就是想知道第i个位置的数据,只能从头找下去,并没有什么其他的好方法。...p || j>i) { return nullptr; } return p; } 在上面的代码中,传入GetElem函数的是链表的头结点,这个代码和《大话数据结构...单链表插入 相比于顺序存储结构,链表的读取确实麻烦了些,但是好在插入和删除方便。比如要在链表的第三个结点之后插入一个结点。 ? 这里的1-6只是结点里面存的数据,不决定结点的顺序。...单链表删除 要删除一个链表中第三个结点后面的结点,逻辑与插入操作很类似,同样要考虑原链表断开后的情况: ?

    1.1K70

    【数据结构与算法】链表之美-复杂链表的复制与链表的插入排序

    2.对链表进行插入排序 题目:给定单个链表的头 head ,使用 插入排序 对链表进行排序,并返回 排序后链表的头 。...插入排序 算法的步骤: 插入排序是迭代的,每次只移动一个元素,直到所有元素可以形成一个有序的输出列表。 每次迭代中,插入排序只从输入数据中移除一个待排序的元素,找到它在序列中适当的位置,并将其插入。...重复直到所有输入数据插入完为止。...但是这是链表啊,这样操作是不是代价也太高了,要是数组你发到一个合适的位置,只需要将后面的数据往后移动即可,链表不太行。...所以,我们的思路是,将第一个节点当作一个新链表的起始节点,之后从后面链表当中每次取一个节点,往新链表当中进行逐一比较进行插入,当然有可能头插,也有可能尾插,也可能中间插入,所以分三种情况,这就是我们的大致思想

    8310

    【数据结构】----链表--双向链表

    文章目录 基本定义 初始化和定义 插入 删除 查找 销毁 双向循环链表 双向链表的应用场景和作用 基本定义 双向链表每个元素都是一个对象,每个对象包括一个数据域和两个指针域next和prev。...phead; } 定义两个指针分别指向前和后,并且定义一个数据域来存放数据 typedef int ElemType; typedef struct LTNode{ ElemType data...phead; newnode->prev = phead->prev; phead->prev->next = newnode; phead->prev = newnode; } 在pos位置之后插入数据...//在pos位置之后插入数据 void LTInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* newnode = LTBuyNode...需要频繁在链表中间插入或删除节点的情况:双向链表可以在O(1)的时间复杂度内完成插入或删除操作,因此适合在需要频繁插入或删除节点的场景中使用。

    7410

    链表数据结构(单链表)

    链表:是一个有序的列表,但是它在内存中是分散存储的,使用链表可以解决类似约瑟夫问题,排序问题,搜索问题,广义表 单向链表,双向链表,环形链表 PHP的底层是C,当一个程序运行时,内存分成五个区(堆区,栈区...,全局区,常量区,代码区) 规定:基本数据类型,一般放在栈区 复合数据类型,比如对象,放在堆区 定义一个类Hero 定义成员属性排名 $no 定义成员属性姓名 $name 定义成员属性昵称 $nickname...定义成员属性 $next,是一个引用,指向下一个Hero对象 定义构造函数,传递参数:$no,$name,$nickname 创建一个头head,该head只是一个头,不放入数据 获取$head对象,...及时雨”) 连接两个对象,$head->next=$hero 获取第二个Hero对象$hero2,new Hero(2,”卢俊义”,”玉麒麟”) 连接两个对象,$hero->next=$hero2 遍历链表

    55220

    数据结构_链表

    数据结构_LinkedList链表 前言: 此类笔记仅用于个人复习,内容主要在于记录和体现个人理解,详细还请结合bite课件、录播、板书和代码。...,在指针方面的理解也算是比较到位了 ---- [toc] ---- 为什么要使用链表(顺序表的局限性) 顺序表的优点: 连续物理空间,方便通过下标随机访问 缺点: 插入数据,空间不足时需要扩容,扩容有性能消耗...头部或中间位置插入或删除数据,需要挪动其他数据,效率较低 可能存在一定的空间占用,浪费空间;不能按需申请和释放空间 基于顺序表的局限性,就设计出了链表 链表 链表的概念 链表是一种在物理存储结构上非顺序非连续的存储结构...NULL) 节点/结点:在数据结构中,每一个数据节点/结点对应一个存储单元,节点/结点就是存储单元的地址(比如在链表里,结点就是链表结构体的地址) 注意: 从上图中可以看出,链式结构在逻辑上一定是连续的...更多情况下是作为其他数据结构的子结构,比如哈希桶、图的邻接表等。另外这种结构在面试题中出现的概率比较高。 带头双向循环链表:结构最复杂,一般用来单独存储数据用。

    21610

    数据结构-----链表

    中间头部插入数据效率低下,增容时浪费空间,效率低下,链表可以解决这个问题: (1)准备工作 创建三个文件,一个头文件----slist.h文件,两个源文件------slist.c------test.c...; 尾部插入数据,首先要判断我们这个一直的链表是否有数据,没有就直接指向新建的节点;有的话进行循环找到尾部的节点,实现链接;因此尾插的时候需要划分为两种情况,否则空的话解引用就会报错,下面的是实参的三种形式...(5)头插数据 和尾部插入有些许类似,我们首先要新建一个节点,我们要想实现关联,我们首先就要让这个新建的节点只想我们的头节点,然后再让我们这个新建的节点成为头节点;这里只需要修改第一个指针的指向,就可以完成链表的头插数据...; (9)在指定位置之前插入数据 这个时候,我们就需要三个参数,我们的指针(二级指针),我们的插入的位置pos,以及我们想要插入的数据(sldatatype x),先要进行断言,我们的pos是一定存在的...4个数据的链表,我们只是为了说明问题:我们在指定的位置的后面插入数据,可有2种方案,一种就是先1后2,还有就是先2后1,先2后1才是正确的,先1后2是错误的(如果是先1后2的话,我们的pos->next

    5100

    【数据结构】链表

    @toc 在 ArrayList 任意位置插入或者删除元素时,就需要将后序元素整体往前或者往后搬移,时间复杂度为 O(n),效率比较低,因此 ArrayList 不适合做任意位置插入和删除比较多的场景...概念 顺序表是物理上连续,逻辑上也是连续的 链表是一种物理存储结构上非连续存储结构,数据元素的逻辑顺序是通过链表中的引用链接次序实现的。...,头结点的数据域可以不存储任何信息,也可以用来存储一些附加信息,如链表的长度等。...在编程和数据结构中,node 通常是一个对象或结构,它包含数据字段和一个或多个指向其他节点的指针或引用。 当我们说 node !...node 中的数据字段可以包含任何类型的值,包括 null(如果数据字段的类型允许)。但是,即使数据字段是 null,node 本身仍然可以是一个有效的对象,只是它的数据字段没有包含有用的信息。

    7210

    数据结构——链表

    链式存储结构 结点在存储器中的位置是任意的,即逻辑上相邻的数据元素在物理上不一定相邻 有关术语 结点:数据元素的存储映像。...由数据域和指针域两部分组成 数据域:存储元素数值数据 指针域:存储直接后继结点的存储位置 链表:n 个结点由指针链组成一个链表。...首元结点 指链表中存储第一个数据元素a1的结点 头结点 在链表的首元结点之前附设的一个结点;数据域内只放空表标志和表长等信息 设置头结点的好处 便于首元结点的处理 首元结点的地址保存在头结点的指针域中...链表的特点 结点在存储器中的位置是任意的,即逻辑上相邻的数据元素在物理上不一定相邻 访问时只能通过头指针进入链表,并通过每个结点的指针域向后扫描其余结点,所以寻找第一个结点和最后一个结点所花费的时间不等...链表的优缺点 优点 数据元素的个数可以自由扩充 插入、删除等操作不必移动数据,只需修改链接指针,修改效率较高 缺点 存储密度小 存取效率不高,必须采用顺序存取,即存取数据元素时,只能按链表的顺序进行访问

    47120

    数据结构——链表

    由数据域和指针域两部分组成 - 数据域:存储元素数值数据 - 指针域:存储直接后继结点的存储位置 链表:n 个结点由指针链组成一个链表。...- 首尾相接的链表称为循环链表 头指针 - 指向链表中第一个结点的指针 首元结点 - 指链表中存储第一个数据元素a1的结点 头结点 - 在链表的首元结点之前附设的一个结点;数据域内只放空表标志和表长等信息...链表的优缺点 优点 - 数据元素的个数可以自由扩充 - 插入、删除等操作不必移动数据,只需修改链接指针,修改效率较高 缺点 - 存储密度小 - 存取效率不高,必须采用顺序存取,即存取数据元素时...,时间复杂度为O(n) 不需移动元素,确定插入、删除位置后,时间复杂度为O(1) 适用情况 ① 表长变化不大,且能事先确定变化的范围 ② 很少进行插入或删除操作,经常按元素位置序号访问数据元素 ① 长度变化较大...; // 生成新结点*p cin >> p->data; // 输入元素赋值给新结点*p的数据域 p->next = L->next; L->next = p; // 将新结点*p插入到头结点之后

    68185

    数据结构——链表

    轻松无痛玩转链表 链表基础知识 链表的概念 链表是一种常见的数据结构,用于线性方式存储数据。...插入和删除操作:在链表中插入或删除节点通常比数组更快,因为这些操作不需要移动其他元素。...遍历:按顺序访问链表的所有节点。 所以总的来说,链表适用于当数据结合频繁变化,需要快速插入和删除,内存空间分散的场景。 单链表的实现 单链表也就是不带头单向非循环链表。...//在指定位置之前插入数据 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) { //链表不能为空链表,不能在一个空节点前插入一个节点...查找 寻找指定数据,返回该节点,遍历链表即可。 注意判断链表为空的情况。

    11410

    数据结构与算法(三)-线性表之静态链表

    前言:前面介绍的线性表的顺序存储结构和链式存储结构中,都有对对象地引用或指向,也就是编程语言中有引用或者指针,那么在没有引用或指针的语言中,该怎么实现这个的数据结构呢?...一、简介 定义:用数组代替指针或引用来描述单链表,即用数组描述的链表叫做静态链表,这种描述方法叫做游标实现法; ?   ...上面的静态链表图有两个数组游标和数据,其中数据数组存储数据,而游标数组存储同下标为数据的下一个数据的下标值,简单模拟一下静态链表遍历的过程: 先查看下标为999的游标数组值:1; 根据游标数组值1,查找下标为...1的数据:A; 然后查看游标数组为1的值:2; 根据游标数组值为2查找对应的数据数组的值:C; 然后循环3->4,直至游标数组的值为0; 二、代码实现 静态链表的创建: 我们对数组的第一个和最后一个元素做特殊处理...cur则存放第一个有数值的元素的下标,相当于单链表中的头结点作用;   静态链表创建代码实现: public class StaticChain { //数据链 private

    1.4K20

    数据结构:链表

    1.链表的定义: 链表(Linked List)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。...在计算机科学中,链表作为一种基础的数据结构可以用来生成其它类型的数据结构。...链表最明显的好处就是,常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序,数据的访问往往要在不同的排列顺序中转换。...而链表是一种自我指示数据类型,因为它包含指向另一个相同类型的数据的指针(链接)。 链表允许插入和移除表上任意位置上的节点,但是不允许随机存取。链表有很多种不同的类型:单向链表,双向链表以及循环链表。...链表通常可以衍生出循环链表,静态链表,双链表等。对于链表使用,需要注意头结点的使用。 2. 示例分析: 2.1例子1: leet-code:25.

    58420
    领券