在本文中的顺序存储结构、链式存储结构等都是对线性表而言的

线性表(Linear List)：零个或多个数据元素的有限序列，元素的个数定义为线性表的长度，无元素时称为空表；每个元素的位置称为位序(类似下标)，某元素的前一个元素称作直接先驱元素，后一个元素称作直接后继元素

顺序存储结构：

用一段地址连续的存储单元依次存储线性表的数据元素，在C中用一维数组来实现(Python中可以用列表来实现)，描述该结构需要三个属性：

  • 存储空间的存储位置：数组的存储位置
  • 线性表的最大存储容量：即数组长度(如果不动态分配，这个长度是不变的)
  • 线性表的当前长度；
  1. 地址：存储器中的每个存储单元所独有的编号，若每个a(代表数据元素)所占c个存储单元，LOC为获得存储位置的函数，那么计算方法为：
    • LOC(下标为i+1的a) = LOC(下标为i的a) + c
    • LOC(下标为i的a) = LOC(下标为1的a) + (i-1) * c
  2. 顺序存储结构的操作：
    • 读取：若要取第i个元素，就访问下标为i-1的元素，注意i值的范围(小于表长、不小于1)，时间复杂度为O(1)
    • 插入：需注意插入后线性表的长度；从最后一个元素向前遍历到第i个位置，并分别向后移一个位置(即下标+1)，插入后表长度+1，时间复杂度每插一个为O(n)
    • 删除：与插入操作相反，不再赘述
  3. 线性表顺序存储结构的优劣：
    • 优点：不用为表中元素之间的逻辑关系添加额外的存储空间；可以快速存取表中任一位置元素
    • 缺点：插入和删除操作时间复杂度高；长度变化大时难以确定存储空间容量；造成存储空间的”碎片”

链式存储结构

在链式结构中，除了要存数据元素信息外，还要存储它的后继元素的存储地址，其中存储数据元素信息的域称为数据域，存储直接后继位置的域称为指针域；指针域中存储的信息称作指针或链。这两部分信息组成数据元素ai(下标为i的a)的存储映像，称为结点(Node)

单链表

N个结点链结成一个链表，即为线性表的链式存储结构，因为此链表的每个结点中只包含一个指针域，所以叫做单链表

  1. 头指针(必须要素)：链表中的第一个结点的存储位置，指向第一个结点(最后一个节点的指针为空(NULL或”^”表示))
  2. 头结点(非必须)：有时为了方便操作第一结点，会在单链表的第一个结点前附设一个节点，其数据域可以为空
  3. 若p是指向线性表第i个元素的指针，ai的数据域用p->data表示，指针域用p->next表示，那么ai+1的数据域的表示可以用p->next->data
  4. 链式存储结构的操作：
    • 读取：若要取第i个元素，从第一个结点开始遍历链表让指针不断向后移动直至第i个结点随后进行读取(元素存在)或到末尾指针为空(元素不存在)
    • 插入：若要在第i个元素插入数据e，声明指针p指向头结点，遍历链表使p到指定位置(即第i-1个结点)并生成一个空节点s，将e赋值给s->data，使用单链表的插入标准语句:s->next=p->next; p->next=s(将p的后继结点赋值给s的后继；将s赋值给p的后继)，插入完成
    • 删除：大体与插入类似；假设在链表中存在结点p, d, q，d是要删除的结点，把p的后继结点改成q即可 (也就是p的后继的后继结点)，删除标准语句：q=p->next; p->next=q->next
    • 整表创建：头插法(把新结点插在头结点后)、尾插法(比头插法多需要一个指向尾结点的变量)
    • 整表删除：先声明p和q：第一个结点赋给p；循环：p->next赋给q，释放p，q赋给p；直至p指针为空
  5. 单链表结构(单)与顺序存储结构(顺)优劣：
    • 存储上：顺用是的一段连续的存储单元依次存储；单不受固定的存储空间限制
    • 时间性能：查找：顺为O(1), 单为O(n)；插入和删除：顺为O(n), 单(找出位置后)为O(1)
    • 空间性能：顺需要预分配；单可以动态生成
    • 总结：查找多时用顺结构，频繁增改时用单结构；表长可确定用顺结构，表长没准时用单结构

静态链表

不用指针，而是用数组描述的链表；让数组的元素由两个数据域组成，每个下标都对应一个data和cur(称作游标, 相当于next指针)，也称作游标实现法

  1. 数组中的首尾元素作为特殊元素处理不存数据，把未使用的数组元素称为备用链表，首元素的cur存放备用链表的第一个结点的下标，尾元素的cur存放第一个有数值的元素的下标，最后一个有值元素的cur为0
  2. 插入操作：先把要插入的数据赋给备用链表元素，再通过把插入位置前的元素的cur指向备用链表元素同时把原指向赋给备用链表元素的cur(需定义类似malloc()的函数来分配备用下标，以实现动态链表的节点申请)
  3. 删除操作：把首元素的cur赋给将目标元素的cur，再把首元素的cur指向目标元素
  4. 静态链表优劣：
    • 优点：插入和删除只需修改游标，免去移动元素的操作
    • 缺点：连续存储分配使表长难以确定；失去顺序存储结构随机存取的特性
    • 总结：静态链表是为了给没有指针的高级语言设计的一种实现单链表的方法，根据实际需要使用

循环链表

将单链表中终端结点的指针端由空指针改为指向头结点，使整个单链表形成一个环，这种头尾相接的单链表称为单链表循环，简称循环链表

  1. 与单链表的主要差异在于循环的判断条件上：若p->next不等于头结点，则循环未结束
  2. 将两个循环链表合并成一个表时用尾指针操作会方便很多

双向链表

在单链表中，查找下一结点需要O(1)，若要查找上个结点最坏需要O(n)，为解决此问题人们设计出了双向链表：在单链表的每个结点中再设置一个指向其前驱节点的指针域(prior)，也就是用空间换时间

  1. 一个节点前驱的后续等于本身： p->next->prior= p = p->prior->next
  2. 与单链表不同的是：在插入和删除时需要更改两个指针变量(注意顺序)