数据结构
🎐线性结构
00 分钟
2023-10-9
2023-10-9
type
status
date
slug
summary
tags
category
icon
password
💡
存在唯一的一个被称为第一个的数据元素
存在唯一的一个被称作最后一个元素
只有第一个元素没有前驱，别的元素都有唯一前驱
只有最后一个元素没有后驱，别的元素都有后驱

按操作方法不同：

普通线性表

是n个数据元素（也称为节点或表元素）组成的有限序列。
L = (A1 , A2…An)

顺序存储结构

  • 各个元素储存地址空间连续，逻辑相邻的元素在物理内存中也相邻，如数组。
  • 顺序表的逻辑下标从1开始，物理下标从0开始。
  • 可以通过第一个元素加上物理下标乘元素的空间。
      • Arr[i] = Arr[0] + (i - 1) * sizeof(元素)
  • 线性表是随机存储的，可以通过下标任意存取。

顺序表的定义方式

  1. 静态方式
  1. 动态方式

线性表的基本操作实现

  • 初始化：Initlist(&L)
      • 动态开辟空间：
  • 插入：ListInsert(&L,i,e)
      • 可以插入的位置：1 ≤ i ≤ length +1 < max
 
 
 

链式线性表

顺序存储结构有个缺点，就是开辟的空间是连续的，而且是固定的，在使用之前需要手动开辟固定空间，会出现不够用的情况。

单链表储存结构

用任意的存储单元来依次存放线性表的结点，这组单元既可以是连续的，也可以是不连续的，甚至是零散的分布在内存中的任意位置上。
每一个元素都称为节点，每个节点由两部分组成：数据域和指针域。数据域用来存放数据，指针域用来存放下一个节点的地址。所以链式线性表称为单链表。
头结点开始进行，头指针指向head指向第一个结点。同时，由最后一个结点无后继，故其指针域为空，即NULL。
  • 头节点（非必须）：包含数据域和指针域，数据域可以是空，也可以是自定义值
  • 头指针（必须）：头指针值访问数据链表的唯一入口，链表为空头节点也不能为空
💡
单链表指针从头向下寻找和存储，所以链表是顺序存取的

单链表的定义方式

  • 如何申请一个节点：
    • 如何释放一个节点
      • 释放后数据p依然存在
      • 如何引用数据
        • 引用指针域

        单链表的基本操作

        • 取元素：
            • GetElem(L,i,&e);
            由于每个节点只知道自己下一个节点的位置，所以我们只能从第一个头节点（头指针）开始寻找。
        • 插入元素
            • ListInsert(&L,i,e);
          • 先查找到i-1的位置，再插入
        • 删除操作
            • ListDelete(&L,i,&e);
          • 同样先找 i-1，再修改指针

        单链表的创建

        • 头插法：每次插入都在表头附近
          • 尾插法：总是向尾部添加

            链式线性表的其他形式

            循环链表

            最后一个节点的指针域指向第一个节点

            双向链表

            每个节点再多设置一个节点指向前驱
            💡
            存在唯一的一个被称为第一个的数据元素
            存在唯一的一个被称作最后一个元素
            只有第一个元素没有前驱，别的元素都有唯一前驱
            只有最后一个元素没有后驱，别的元素都有后驱

            按操作方法不同：

            普通线性表

            是n个数据元素（也称为节点或表元素）组成的有限序列。
            L = (A1 , A2…An)

            顺序存储结构

            • 各个元素储存地址空间连续，逻辑相邻的元素在物理内存中也相邻，如数组。
            • 顺序表的逻辑下标从1开始，物理下标从0开始。
            • 可以通过第一个元素加上物理下标乘元素的空间。
                • Arr[i] = Arr[0] + (i - 1) * sizeof(元素)
            • 线性表是随机存储的，可以通过下标任意存取。

            顺序表的定义方式

            1. 静态方式
            1. 动态方式

            线性表的基本操作实现

            • 初始化：Initlist(&L)
                • 动态开辟空间：
            • 插入：ListInsert(&L,i,e)
                • 可以插入的位置：1 ≤ i ≤ length +1 < max
             
             
             

            链式线性表

            顺序存储结构有个缺点，就是开辟的空间是连续的，而且是固定的，在使用之前需要手动开辟固定空间，会出现不够用的情况。

            单链表储存结构

            用任意的存储单元来依次存放线性表的结点，这组单元既可以是连续的，也可以是不连续的，甚至是零散的分布在内存中的任意位置上。
            每一个元素都称为节点，每个节点由两部分组成：数据域和指针域。数据域用来存放数据，指针域用来存放下一个节点的地址。所以链式线性表称为单链表。
            头结点开始进行，头指针指向head指向第一个结点。同时，由最后一个结点无后继，故其指针域为空，即NULL。
            • 头节点（非必须）：包含数据域和指针域，数据域可以是空，也可以是自定义值
            • 头指针（必须）：头指针值访问数据链表的唯一入口，链表为空头节点也不能为空
            💡
            单链表指针从头向下寻找和存储，所以链表是顺序存取的

            单链表的定义方式

            • 如何申请一个节点：
              • 如何释放一个节点
                • 释放后数据p依然存在
                • 如何引用数据
                  • 引用指针域

                  单链表的基本操作

                  • 取元素：
                      • GetElem(L,i,&e);
                      由于每个节点只知道自己下一个节点的位置，所以我们只能从第一个头节点（头指针）开始寻找。
                  • 插入元素
                      • ListInsert(&L,i,e);
                    • 先查找到i-1的位置，再插入
                  • 删除操作
                      • ListDelete(&L,i,&e);
                    • 同样先找 i-1，再修改指针

                  单链表的创建

                  • 头插法：每次插入都在表头附近
                    • 尾插法：总是向尾部添加

                      链式线性表的其他形式

                      循环链表

                      最后一个节点的指针域指向第一个节点

                      双向链表

                      每个节点再多设置一个节点指向前驱。其插入和删除则需要修改两个指针域（即前驱和后驱）

                      顺序表和链表的对比

                      储存方式

                      • 顺序表用连续的储存单元
                      • 单链表采用链式的储存结构用任意一组存储单元

                      时间性能

                      • 查找
                        • 顺序表：O(1)
                        • 链表：O(n)
                      • 插入和删除
                        • 顺序表平均移动长一半的元素O(n)
                        • 单链表找出某位在的指针后直接修改，事件为O(1)

                      空间性能

                      • 顺序表
                       
                      上一篇
                      实现链表表的基本操作
                      下一篇
                      Unity常用API
                      评论
                      Loading...