Day27-【13003】短文，线性表两种基本实现方式空间效率、时间效率比较？兼顾优点的静态链表是什么？如何融入空闲单元链表来解决问题？

本次内容总览

第四节，两种基本实现方式概览

两种基本实现方式的比较

线性表有两种基本实现方式，分别是顺序实现和链式实现。

那么，哪一种方法更好呢?

这两种实现方式各有优势，在不同的情况下，对应于不同的操作，某一种方式可能会优于另外一种。但是哪种方式都不能适用于所有情况。

• 顺序表的优点是存储每个数据元素时空间比较紧凑，并且会占用连续的空间。

数组的每个单元中只需要保存数据本身，没有额外的开销。

• 与此相对的是，链表在每个结点上除存储数据元素以外，还要留出空间存放指针。

单链表中每个结点包含一个指针，双向链表中每个结点包含两个指针。这些指针占用的空间称为结构性开销。

存储一个指针的空间大小是固定的，与使用的具体系统相关。

如果数据域data占用的空间较小，则结构性开销的比例就会较大。

元素个数n大于多少时，使用顺序表存储的空间效率才会更高？

为顺序表分配的数组， 通常要宽松—些。 当线性表中元素个数没能达到顺序表的最大容量时，数组中 仍然会有空闲的空间， 此时并没能充分利用数组的全部空间。

而链表中占用的空间大小与链表中的元素个 数成正比， 分配的结点是全部使用的。

• 所以，当线性表的元素个数相对较少时，链表的实现比顺序表的实 现更节省空间。

  也就是说，链表方式的发现，在资源紧张时，起了很大的作用

• 反之， 当线性表中的元素个数接近数组分配的最大个数，数组几乎被填满时，空闲的单元不多，它的空间存储效率很高。

设n表示线性表中当前元素的个数，

D表示最多可以在数组中存储的元素个数， 也就是数组的大小，

P 表示指针的存储单元大小，

E表示数据元素的存储单元大小。

按照这个假设，

顺序表的空间需求为D x E；就是数组的元素总数，和每个元素存储单元，的乘积

单链表的空间需求为n x (P+E)。 就是线性表当前元素总数，和指针存储单元+元素存储单元之和，的乘积

对于给定的n值， 以上两个表达式中哪一个的值较小呢？

列方程后可以求 出n的临界值，

即n=D x E/(P+E)。

• 当线性表中元素个数小于这个值时，单链表的存储效率更优。

  双向链表的橾作实现起来与单链表类似，其空间效率要低于单链表，因为表中每个结点都带有两个指针，比单链表中每个结点的指针数多1个。

  所以双向链表的结构性开销是单链表的2倍。

• 当线性表中元素个数超过这个值时， 顺序表的空间效率更离，

如果P = E （如指针占2字节，数据元素也占2字节），

则临界值n = D/2。

• 也就是说，和数组本身的大小有关

【例2-12】 设采用单链表保存的线性表L的每个元素需要的空间为10字节， ；意思是数据元素空间大小，E，是10字节

—个指针占2字节。 ；意思是P，为2字节

若采 用单链表或含30个元素的数组保存L, ；数组大小D，为30；

试分析哪种方式的空间存储效率更高，

仅需要考虑L中的元素。

1、L中的元素个数n 的临界值

= 30 * 10 / ( 2+10 )

= 25

2、当L中元素个数小于 25时，采用链表的空间存储效率更高

​ 当L中元素个数大于 25时，采用数组的空间存储效率更高

​ 当L中元素个数等于 25时，两者空间存储效率一样

答案：

即在不考虑头结点所占用空间的前提下，（注意：这一点还是要注意一下，说不考虑链表的头结点的，也就是可能采用不带头结点的链表）

如果L中元素个数少于25个， 则采用单链表更省空间；

如果多于25个元素，则采用数组更省空间；

如果正好是25个元素， 则两种方式占用的空间是一样大的。

• 选择顺序表或链表的一个因素是， 当线性表元素个数变化较大或者未知时， 最好侍用链表实现。

• 也就是说，元素个数n未知，或者变化较大，其实也就是n可能会变得很小，那么尽量采用链表

• 如果 用户事先知道线性表的大致长度， 则使用顺序表的空间效率会更高些。

• 如果知道元素个数n的大概长度，就采用顺序表么，要么n很小，不仍然是链表更好

  并非如此，因为此时就可以限制一下数组大小D的值，让它尽量匹配，这样n的大概长度，肯定是超过了临界值n的

还有一个因素需要考虑， 即顺序表 占用的空间是连续的，

而链表占用的空间可能是零散的，

并且还需要程序员来管理空间的分配及释放。

时间效率比较？

再来看看操作的时间效率。

以访问线性表的第i个元素为例，

*、访问操作，也就是读运算，读操作

• 单链表不能随机访问指定的元素，访问时必须从表头开始逐个结点进行查找，直到找到第i个结点为止。这个操作的平均时间复杂度和最差时间复杂度均为O(n)

• 相比之下，在顺序表中是直接定位的，可以实现随机访问，操作的时间复杂度是O (1)

1、插入，2、删除操作

关于插入橾作和删除操作，

在给出指向链表合适位置的当前指针后，

见，Day27-【13003】短文，什么是单链表、循环链表、双向链表、双向循环链表？它们的操作时间复杂度是多少？如何进行存储单元的计算？，中：如果已经设定当前指针的指向，则进行插入、删除操作时，时间复杂度均为O(1)，

• 在单链表内进行插入和删除操作的时间复杂度也可以达到O (1)。

• 双向链表各个操作的时间复杂度分析留作习题。

• 而顺序表的插入操作和删除操作必须在数组内将当前位置之后的各元素分别向后与向前移动，这种移动的平均和最差时间复杂度均为O(n)。

对于线性表的许多应用，插入和删除都是主要的操作，因此它们的时间效率是举足轻重的，仅就这个原因而言，单链表通常比顺序表更灵活。

见，Day27-【13003】短文，什么是单链表、循环链表、双向链表、双向循环链表？它们的操作时间复杂度是多少？如何进行存储单元的计算？，中：如果已经设定当前指针的指向，则进行插入、删除操作时，时间复杂度均为O(1)，

什么是空闲单元链表？

在链表中，当需要在链表中插入— 个结点时，需要调用malloc函数分配相应的空间。

当在链表中删除一 个结点时，需要调用free函数释放空间。

如果在链表中频繁进行插入、删除结点的操作，则频繁调用这些函数的时间开销会是非常可观的。

如何解决？

​ 可以针对实际应用的每类链表，定义一 个 “伙伴链表” ，表结点的结构与所使用链表的结构一 致。

​ 伙伴链表用来管理暂时不用的结点，也可以将伙伴链表称为空闲单元链表。

​ 也就是freelist链表

freelist链表的作用是暂时保管要归还给系统的结点空间，结点中的数据是无意义的，

所以插入及删除的操作都可以在表头进行。

而且，链表中也不需要头结点。

因此，对freelist链表操作的效率非常高。

对于有相同结点结构的所有链表，可以共用一 个freelist链表，

也可以将其设詈为一个全局变量，

初始时，freelist是一 个空链表。

在程序的最后，freelist中结点占用的空间需要全部释放。

空闲单元链表如何实现？

假设保存数据的单链表为L。

2、删除

1、当从链表L中删除一个结点时，将这个结点插入到freelist中。

​ 这样就完成了删除，其实也就是挪到了临时表中，难怪说删除没有真的删，也可能只是挪走了，挪到了临时空间中

1、插入

1、当需要申请新的结点空间时，先查看链表freelist。

2、

​ a.如果freelist不为空，则从freelist中获取一 个结点，结点中保存相应的值，并将该结点插入到L的相应位詈，

​ b.否则调用malloc函数分配新的空间，并完成后续的插入橾作。

2、删除操作

在增加freelist链表后，可以修改前面实现的在单链表中进行插入结点及删除结点的橾作，实现如下。

int removeList(LinkList * head, Position curr, ELEMTType * x) {
    // 删除表head中位置curr处的元素,并通过x返回
    LinkNode * temp;
    if ((*head == NULL && curr == NULL) || curr->next == NULL) return FALSE;  // 指针无效
    if (isEmpty(head) == TRUE) return FALSE;  // 空表
    *x = curr->next->data;
    temp = curr->next;
    curr->next = curr->next->next;
    temp->next = freelist;
    freelist = temp;
    (*head)->data--;
    return TRUE;
}

1、插入操作

int insertList(LinkList * head, Position curr, ELEMTType x) {
    // 在表head的位置curr处插入元素x
    LinkNode * temp;
    if (*head == NULL && curr == NULL) return FALSE;  // 指针无效
    if (freelist == NULL) {
        temp = (LinkList)malloc(sizeof(LinkNode));
    }
    else {
        temp = freelist;
        freelist = freelist->next;
    }
    temp->data = x;
    temp->next = curr->next;
    curr->next = temp;
    (*head)->data++;
    return TRUE;
}

*、清空链表操作

int clear(LinkList * head) {
  								 // 将链表head置为空
    LinkNode * p;
    if (*head == NULL) {
        						 // 表头指针错误,返回0
        printf("链表错误\n");
        return FALSE;
    }
    p = (*head)->next;
    while (p != NULL) {
       							 // 将各结点依次放入freelist中
        (*head)->next = p->next;
        p->next = freelist;
        freelist = p;
        p = (*head)->next;
    }
    (*head)->data = 0;
    							 // 结点个数为0
    return TRUE;
}

什么是静态链表？

顺序表和链表的— 些特点是相互对立的，

比如，当插入元素时，在顺序表中可能要移动元素，但在链表中完全不需要移动。

顺序表的空间是一 次性预分配的，而链表的空间是随用随分配的。

顺序表中查找某位詈的元素非宫方便，但多数情况下在链表中进行查找则不是一 个便捷的橾作。

特别是，顺序表占用的空间完整，而链表占用的空间笭散。

在有些应用中，需要— 种兼具顺序表和链表特性的结构，

既要具有顺序表的空间整体性，不必进行零散的空间处理，

又要具有链表的灵活性，在插入或删除时不必进行数据的大量移动。

静态链表正好能满足这种需求。

数据结构中的静态链表，

即使用一 维数组实现的链表。

下面以单链表为例，介绍静态链表。

实际上，还可以实现静态双向链表及静态循环链表。

假设静态链表保存在— 维数组A中，

每个元素的类型与单链表结点类型— 致，

也有数据域data和指针域next。

将A[0]当作一 个特殊结点，类似于单链表中的表头结点，

• 表头结点，并非头结点，而是首结点！

  这里确实是类似首结点，因为静态链表没有头结点

在A[0]的数据域data中保存链表中元素的个数，

初始时，data的值是0

在指针域next中保存静态链表中第一 个元素在数组中的下标。

初始时，next的值1。

（注意，这里资料打错了，打成next初始值成-1了）

例如，将图2-17a所示的单链表head中的各元素，依次保存在数组A最前面的几个单元中，得到的静态链表如图2-17b所示。

静态链表插入操作过程示意？

在静态链表中实现基本橾作的过程类似于在链表中的实现过程。

例如，在静态链表中进图2-9所示的插入操作，

新元素E应在元素B与C之间。

1、在图2-17b所示的— 维数组中找到— 个空闲位詈，如下标5处，

• ​ 下标5，也就是静态链表的位置5

​ 这相当于在单链表中进行插入操作时调用malloc函数得到一个新的结点空间。

2、将元素E放在这个位置的data域中（类似于图2-9中的步骤①）。

E的后继是元素C, 所以下标5处的next值应为3 （类似千图2-9中的步骤②），

3、而E的前驱是元素B,即B的next值应为5 （类似于图2-9中的步骤③。

4、最后，将链表中的元素个数加1。

在插入操作完成后，得到的静态链表如图2-18所示。

静态链表删除操作过程示意？

现在，在图2-18所示的静态链表中删除元素D。

1、删除的元素D是静态链表中的表尾元素，

​ 删除后，它的前驱（元素C)的next值应为元素D的next值，即**－1,表示静态链表的结束**。

2、同时，在静态链表中将这个位詈标识为空闲位置，

​ 这相当于在单链表中进行删除橾作时调用delete函数。

得到的静态链表如图2-19所示。

静态链表单元的状态分类？未使用过的空闲单元是一片连续单元

在静态链表使用的数组中，可以将单元的状态分为两类，

• 一类是已经被占用的单元，

  如图2-19中下标为0、1、2、3、5的单元，；所谓下标，其实就是位置0,1,2,3,5

• 另一 类是空闲单元，

  如图2-19中下标为4、6、7、8的单元。

1. 空闲单元又分为两种，一 种是曾经使用过但现在空闲的，如下标为4的单元，
2. 另一 种是从未使用过的，如下标为6、7、8的单元。

在静态链表中，可以使用一 个特殊标记来标识空闲单元，

插入时将新元素放置在有特殊标记的单元中。

初始时，数组中所有单元均为空闲单元，故需要为每个单元设詈特殊标记。

在插入时，需要逐个单元进行查找。

当然，可以采用更有效的方法标记空闲单元，其目的是方便后面的插入操作。

数组中所有未曾使用过的单元必定是— 片连续单元，

可以使用整型变量unused记录这片连续单元的首位詈，

凡是下标大于等于unused且不越界的单元，均为空闲单元。

例如，在图2-19中，unused的值是6。

下标大于等于6且小于9的单元即这类空闲单元。

使用过的空闲单元，引入空闲单元链表，建立新链

对于数组中普经使用过且目前空闲的所有单元，建立另一个静态链表将其链接起来，可以将这个链表称为空闲单元链表，

用整型变量available记录这个链表首结点的下标。

• 把空闲单元链表，融合到静态链表中解决问题来了，难怪要先学空闲单元链表

例如，对于图2-19所示的静态链表，available值为4。

​ 因为目前只有这— 个空闲位詈，故它也是表尾，位置4的next值为－1。

如何实现静态链表？

程序中用到的一些常量及静态链表的定义如下。

#define TRUE 1
#define FALSE 0
#define ERROR -1
typedef int ELEMTType;
typedef struct node {
    ELEMTType data;  //数据域
    int next;  //指针域
} ArrayListNode;
typedef struct {
    ArrayListNode element[maxSize];  //保存元素的数组,最大容量为maxSize
    int available;  //空闲单元链表首位置,将释放的结点组成一个链表
    int unused;  //未用空间首位置
} ArrayList;
typedef int position;

初始化过程是构造一个空的静态链表，并给静态链表中的各个变量赋初值。

int initList(ArrayList * L) {
    // 构造一个空静态链表L
    L->element[0].data = 0;
    L->element[0].next = -1;
    L->available = -1;
    L->unused = 1;
    return TRUE;
}

清空静态链表与初始化过程是类似的。

int clear(ArrayList * L) {
    // 将表L置空
    L->element[0].data = 0;  //element[0]：头结点, data保存链表长度
    L->element[0].next = -1;  //element[0]：头结点, 链表结束, 置next为-1
    L->available = -1;  //空闲单元链表首位置, 初始时无空闲结点置为-1
    L->unused = 1;  //未用空间首位置, 初始为element[1]
    return TRUE;
}

判定静态链表的空或满状态是很容易实现的。数组第一个单元的data域保存了链表中元素的个数，如果该值是0，则链表是空链表，如果是maxSize-1，则表示链表已满。

int isEmpty(ArrayList * L) {
    // 如果表L为空,则返回1,否则返回0
    if (L->element[0].data == 0) return TRUE;
    else return FALSE;
}

int isFull(ArrayList * L) {
    // 如果表L为满,则返回1,否则返回0
    if (L->element[0].data == maxSize - 1) return TRUE;
    else return FALSE;
}

求表长的实现如下

int length(ArrayList * L) {
    // 返回表L的当前长度
    return L->element[0].data;
}

在静态链表中进行插入操作时，如果空闲单元链表为空，即available==-1，则使用unused位置的单元同时unused++;如果空闲单元链表不为空，即available!=-1，则取表头单元来使用，即使用available位置的单元，同时更新空闲单元链表，available值更新为链表中下一个元素的下标。

int insertArrayList(ArrayList * L, Position pos, ELEMTType x) {
    // 在表L的位置pos处插入元素x
    int i, k, curr;
    if (isFull(L) == TRUE) return FALSE;    // 表满
    if (pos < 0 || pos > L->element[0].data) return ERROR;  // 位置错误, 与表满区分开
    if (L->available == -1) {
        // 空闲单元链表为空
        k = L->unused;
        // 新申请的数据结点的下标
        L->element[L->unused++].data = x;
    }
    else {
        // 有空闲空间, 取出空闲单元链表的首结点
        k = L->available;
        // 新申请的数据结点的下标
        L->element[k].data = x;
        L->available = L->element[k].next;
        // 将新结点从空闲单元链表中删除
    }
    L->element[0].data++;
    curr = 0;
    // 头位置
    for (i = 0; i < pos; i++) {
        // 在数据链表中定位位置在pos的结点
        curr = L->element[curr].next;
    }
    L->element[k].next = L->element[curr].next;
    // 将新数据结点插入到链表中
    L->element[curr].next = k;
    // 放置x
    return TRUE;
}

当从静态链表中删除一个元素时，元素的值通过x带回。从表头开始找到被删除元素的前驱，修改该元素的next值，与被删除元素的后继相连。而该元素占用的空间会链接到空闲单元链表中。

int removeArrayList(ArrayList * L, Position pos, ELEMTType * x) {
    // 删除表L中位置position处的元素并通过x返回
    int i, k, curr;
    if (isEmpty(L) == 1) return FALSE;    // 表空
    if (pos < 0 || pos >= L->element[0].data) return ERROR;  // 位置错误, 与表空区分开
    curr = 0;
    // 头位置
    for (i = 0; i < pos; i++) {
        curr = L->element[curr].next;
    }
    k = L->element[curr].next;
    *x = L->element[k].data;
    // 记下被删除的元素值
    L->element[curr].next = L->element[k].next;
    // 删除
    L->element[k].next = L->available;
    L->available = k;
    L->element[0].data--;
    // 表长减1
    return TRUE;
}