【数据结构与算法】三、线性表

定义

抽象数据类型

线性表抽象数据类型（ADT，Abstract Data Type）是一种逻辑结构，它描述了一组数据元素的有序集合，以及在这些元素上可以进行的基本操作，而不关心具体的实现方式。抽象数据类型强调：只描述“做什么”，不描述“怎么做”。具体实现可以用数组（顺序表）、链表等多种方式。

线性表ADT的特点：

数据元素有先后次序（线性关系）。
每个元素最多只有一个前驱和一个后继（第一个元素无前驱，最后一个元素无后继）。
可以进行插入、删除、查找等操作。

常见的线性表ADT操作有：

初始化线性表
销毁线性表
判断线性表是否为空
求表长
取元素
插入元素
删除元素
按值查找元素

ADT 标准定义通常如下:

ADT 线性表（List）
Data：
    D = {a1, a2, ..., an}，其中 n ≥ 0，每个元素类型为 ElemType。
数据关系集：除第一个元素 a1 外，每个元素有且只有一个前驱，除最后一个元素 an 外，每个元素有且只有一个后继。

Operation：
    InitList(*L)         // 初始化线性表L
    DestroyList(*L)      // 销毁线性表L
    ClearList(*L)        // 清空线性表L
    ListEmpty(L)         // 判断线性表是否为空
    ListLength(L)        // 返回线性表长度
    GetElem(L, i, *e)    // 取第i个元素，用e返回
    LocateElem(L, e)     // 查找元素e，返回其位置
    PriorElem(L, cur_e, *pre_e)   // 求前驱
    NextElem(L, cur_e, *next_e)   // 求后继
    ListInsert(*L, i, e) // 在第i个位置插入元素e
    ListDelete(*L, i, *e)// 删除第i个元素，用e返回
    ListTraverse(L, visit()) // 遍历线性表，对每个元素调用visit()

物理结构

链式结构适合插入、删除操作频繁且元素数量变化大的场景，但不适合频繁随机访问的场景。
顺序存储结构适合元素个数变化不大、需要频繁随机访问的场景，不适合频繁插入和删除的场景。

线性表的顺序存储结构

定义

用一段地址连续的存储单元依次存储线性表的数据元素。示意图：

数组长度和线性表长度区别

数组的长度：存放线性表的存储空间的长度，存储分配后这个量是一般不变的。 线性表的长度：线性表中数据元素的个数，随着线性表的插入和删除操作的进行，这个量是变化的。在任意时刻，线性表的长度应该 <= 数组的长度。

地址计算方式

由于我们数数都是从 1 开始，线性表的定义也相同，起始是1，但是C语言中数组是从 0 开始第一个下标，于是线性表的第 i 个元素是要存储在数组下标为 i – 1的位置。对应关系如图：
用数组存储顺序表意味着要分配固定长度的数组空间，由于线性表中可以进行插入和删除操作，因此分配的数组空间要大于等于当前线性表的长度。

获得算法

对于线性表的顺序存储结构来说，就是将第 i 个位置元素值返回；就程序而言，只要 i 的数值在数组下标范围内，把 i – 1 下标的值返回即可。

插入算法

插入操作不仅可以在已有元素之间插入新元素，还可以在顺序表的末尾插入新元素，顺序表的长度都会+1。在线性表中，哪些情况下会插入失败？

情况1： 插入的位置不对（超过范围）。

举例：如下图，顺序表长度 n = 4, 如果把小球插入位置 i = 0 或者 i = 6（即>n+1=5）的位置就会失败。

情况2： 位置满了。

举例：顺序表装满了球，这时候执行插入会失败。

C语言实现

如何转化为程序。

先设计数据结构。
明确函数参数和返回值。
按照算法步骤写出每一步的代码。
注意边界条件和特殊情况处理。

如下图：

#include <stdio.h>

#define OK 1        /* 执行成功 */
#define ERROR 0     /* 执行失败 */
#define MAXSIZE 100 /* 顺序表最大长度 */

typedef int Status;   /* 返回执行状态 */
typedef int ElemType; /* 元素类型，这里假设为int */

typedef struct {
  ElemType data[MAXSIZE]; /* 存储元素的数组 */
  int length;             /* 当前顺序表长度 */
} SqList;

Status ListInsert(SqList *L, int i, ElemType e) {
  if (L->length == MAXSIZE) /* 顺序表已满 */
    return ERROR;

  if (i < 1 || i > L->length + 1) /* 插入位置不合法 */
    return ERROR;

  if (i <= L->length) /* 如果插入位置不在表尾。因为表尾不需要移动元素 */
  {
    for (int k = L->length - 1; k >= i - 1; k--) /* 移动元素 */
      L->data[k + 1] = L->data[k];
  }
  L->data[i - 1] = e; /* 插入新元素 */
  L->length++;        /* 更新顺序表长度 */

  return OK; /* 返回成功状态 */
}

int main(void) {
  SqList L = {{1, 2, 3, 4, 5}, 5}; /* 初始化顺序表 */
  ElemType newElement = 10;        /* 要插入的新元素 */
  int pos = 3;                     /* 要插入的位置 */

  printf("插入前顺序表的元素为：");
  for (int i = 0; i < L.length; i++) {
    printf("%d ", L.data[i]);
  }
  printf("\n");

  if (ListInsert(&L, pos, newElement) == OK) {
    printf("在位置 %d 插入元素 %d 成功！\n", pos, newElement);
    printf("插入后顺序表的元素为：");
    for (int i = 0; i < L.length; i++) {
      printf("%d ", L.data[i]);
    }
    printf("\n");
  } else {
    printf("在位置 %d 插入元素失败！\n", pos);
  }

  return 0;
}

测试结果：

插入前顺序表的元素为：1 2 3 4 5 
在位置 3 插入元素 10 成功！
插入后顺序表的元素为：1 2 10 3 4 5 

[Done] exited with code=0 in 0.358 seconds

删除算法

删除算法的思路：

删除的位置不合理，抛出异常。
取出删除元素。
从删除元素开始遍历到最后一个元素，分别将他们都向前移动一个位置。
表长减1。

c语言实现：

#include <stdio.h>

#define OK 1          /* 执行成功 */
#define ERROR 0       /* 执行失败 */
#define MAXSIZE 100   /* 顺序表最大长度 */

typedef int Status;   /* 状态信息 */
typedef int ElemType; /* 元素类型 */

typedef struct {
  ElemType data[MAXSIZE]; /* 存储元素的数组 */
  int length;             /* 当前顺序表长度 */
} SqList;                 /* 顺序表类型 */

Status ListDelete(SqList *L, int i, ElemType *e) {
  /* 1.错误判断 */
  if (L->length == 0) /* 顺序表为空 */
    return ERROR;
  if (i < 1 || i > L->length) /* 删除位置不合法 */
    return ERROR;

  /* 2. 取出要删除的元素，存放到指针e中 */
  *e = L->data[i - 1];

  /* 3. 移动线性表的元素：从删除位置开始，依次把后面的元素往前移1位 */
  if (i < L->length) /* 如果删除位置不是表尾 */
  {
    for (int k = i; k < L->length; k++)
      L->data[k - 1] = L->data[k]; /* 移动元素 */
  }

  /* 4. 线性表长度减一 */
  L->length--; /* 更新顺序表长度 */

  /* 5. 返回成功状态 */
  return OK; /* 返回成功状态 */
}
int main(void) {

  SqList L = {{1, 2, 3, 4, 5}, 5}; /* 初始化顺序表 */
  int deleted;
  int pos = 3; /* 要删除的元素位置 */

  printf("删除前顺序表的元素为：");
  for (int i = 0; i < L.length; i++) {
    printf("%d ", L.data[i]);
  }
  printf("\n");

  if (ListDelete(&L, pos, &deleted) == OK) {
    printf("删除位置 %d 的元素 %d 成功！\n", pos, deleted);
    printf("删除后顺序表的元素为：");
    for (int i = 0; i < L.length; i++) {
      printf("%d ", L.data[i]);
    }
    printf("\n");
  } else {
    printf("删除位置 %d 的元素失败！\n", pos);
  }

  return 0;
}

测试结果：

删除前顺序表的元素为：1 2 3 4 5 
删除位置 3 的元素 3 成功！
删除后顺序表的元素为：1 2 4 5 

[Done] exited with code=0 in 0.354 seconds

插入和删除的时间复杂度

最好的情况：要插入元素到最后一个位置，或者删除最后一个元素，此时时间复杂度为O(1)。因为不需要移动任何元素。

最坏的情况：要插入元素到第一个位置，或者删除第一个元素，此时时间复杂度为O(n),因为要移动所有元素向前或者向后。

平均情况：元素插入到第 i 个位置，或者删除第 i 个位置的元素，需要移动 n – i + 1个位置。举例如图：

因为顺序表长度为 n, 允许插入到第 1 个位置和 n + 1 的位置，共有 n + 1 个位置可选，所以插入到每个位置的概率就是

插入位置等概率分布，平均移动次数为：

删除第 i 个元素，需要移动 n-i 个元素（即 i+1 到 n 的元素都要前移）。删除只能删除存在的元素，即 n 个元素。删除位置等概率分布，平均移动次数为：

总结：由大O记法插入和删除的平均时间复杂度为O(n)。所以它比较适合元素个数不太变化，而更多是存取数据的应用。

线性表的链式存储结构

定义

为了表示每个数据元素 ai 与其直接后继数据元素 ai+1 之间的逻辑关系，对数据元素 ai 来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素 ai 的存储映像，称为结点（Node）。

如图所示：

带有头节点的单链表:

空链表：

单链表结构体C语言代码描述

typedef struct Node {
    int data;               /* 数据域*/ 
    struct Node* next;      /* 指针域，指向下一个结点 */ 
} Node;

Node* LinkeList;            /* 头结点指针 */

因为结点 = 数据域 + 指针域，在下图所示链表中：假设结点 p 指向线性表第 i 个元素的指针，则该结点的数据域用 p -> data 表示，指向的数据是 a(i), 指针域用 p->next 表示，指向下一个结点（即指向元素 a(i+1)），则下一个元素可以表示为 p->next->data。

单链表的读取算法

获得链表第 i 个数据算法思路：

从头节点的下一个结点（第一个有效数据结点）开始遍历。
设置计数器 j = 1,表示当前结点是第一个结点。
依次向后遍历链表，每访问 1 个结点，计数器 +1.
当计数器 = i 时，当前结点就是第 i 个元素，返回其数据域。
如果遍历到链表末尾还未找到第 i 个元素（即超出链表长度），则返回失败。

C语言实现：

#include <stdio.h>

#define OK 1
#define ERROR 0

typedef int Status;   /* 状态信息 */
typedef int ElemType; /* 元素类型 */

typedef struct Node {
  int data;          /* 数据域*/
  struct Node *next; /* 指针域，指向下一个结点 */
} Node;

Status GetElem(Node *L, int i, ElemType *e) {
  int j = 1;         /* 计数器 */
  Node *p = L->next; /* p指向头结点的下一个结点 */

  while (p && j < i) {
    p = p->next; /* p指向下一个结点 */
    j++;         /* 计数器加1 */
  }

  if (!p) /* 如果p为空，说明第i个元素不存在 */
  {
    return ERROR; /* 返回错误状态 */
  }

  *e = p->data; /* 取出数据 */

  return OK; /* 返回成功状态 */
}

int main(void) {
  Node head = {0, NULL}; // 初始化头结点
  Node second = {2, NULL};
  Node third = {3, NULL};

  head.next = &second;  // 头结点指向第二个结点
  second.next = &third; // 第二个结点指向第三个结点

  ElemType e;
  if (GetElem(&head, 2, &e) == OK) {
    printf("Element at position 2: %d\n", e);
  } else {
    printf("Error retrieving element at position 2.\n");
  }

  return 0;
}

运行结果：

Element at position 2: 3

[Done] exited with code=25 in 3.236 seconds

单链表的插入算法

下图中，结点 s 存储元素 e，要实现结点 s 插入到结点 p 和结点 p->next 中间，只需要将结点 s 的指针指向结点 p->next，结点 p 的指针指向结点 s 即可。

即

s->next = p->next;
p->next = s;

注意：

交换顺序不能错，如果先将结点 p 的指针指向结点 s（即 p->next = s）,会覆盖原来的 p->next 地址，在执行 s->next = p->next,就会造成 s = s。

插入算法思路：

声明一个指针 p，指向链表的头结点。
初始化计数器 j = 1,用于记录当前位置。
遍历链表，找到第 (i-1)个结点（即插入位置的前驱结点）：当 j < 1 就遍历链表，让 p 的指针后移，不断指向下一个结点，j累加1。
判断插入位置是否合法：如果链表末尾为空（ P == NULL），则说明第 i 个元素不存在，插入位置不合法，返回错误。
创建新结点 s,并赋值数据域。
将新结点插入链表： S->next = P->next; P->next = S;
返回成功状态

C语言实现：

定义链表数据结构->声明链表插入函数（入口参数，返回值）->main测试实现。

#include <stdio.h>
#include <stdlib.h>

#define OK 1
#define ERROR 0

typedef int Status;   /* 状态信息 */
typedef int ElemType; /* 元素类型 */

typedef struct Node {
  ElemType data;     /* 数据域*/
  struct Node *next; /* 指针域，指向下一个结点 */
} Node;

Status ListInsert(Node *L, int i, ElemType e) {
  Node *p = L; /* p指向头结点 */
  int j = 1;   /* 计数器 */

  while (j < i && p) {
    p = p->next; /* p指向下一个结点 */
    j++;         /* 计数器加1 */
  }

  if (p == NULL) {
    return ERROR; /* 如果p为空，说明第i个位置不存在 */
  }
  Node *s = (Node *)malloc(sizeof(Node)); /* 创建新结点 */
  if (s == NULL) {
    return ERROR; /* 内存分配失败 */
  }
  s->data = e;       /* 设置新结点的数据 */
  s->next = p->next; /* 新结点的next指向p的下一个结点 */
  p->next = s;       /* p的next指向新结点 */

  return OK; /* 返回成功状态 */
}

int main(void) {
  Node head = {0, NULL}; /* 头结点 */
  Node second = {2, NULL};
  Node third = {3, NULL};

  head.next = &second;  /* 头结点指向第二个结点 */
  second.next = &third; /* 第二个结点指向第三个结点 */
  ElemType e = 4;

  printf("插入前的链表元素： %d -> %d -> %d\n", head.data, second.data,
         third.data);
  if (ListInsert(&head, 2, e) == OK) {
    printf("插入成功！\n");
    printf("插入后的链表元素： %d -> %d -> %d -> %d\n", head.data, second.data,
           e, third.data);
  } else {
    printf("插入失败！\n");
  }

  return 0;
}

运行结果：

插入前的链表元素： 0 -> 2 -> 3
插入成功！
插入后的链表元素： 0 -> 2 -> 4 -> 3

[Done] exited with code=0 in 1.856 seconds

单链表的删除算法

要实现单链表的删除，如下图所示。设存储元素 a(i) 的结点为 q, p->next表示它是 p 结点的后继。要删除 q 结点，只需断掉前驱和后继的链接指针，将 p 的指针域指向 q 的后继即可。

删除算法思路：

声明一个指针 p,指向链表的头结点。
初始化计数器 j = 1,用于记录当前位置。
遍历链表，找到第（i-1）个结点（即待删除结点的前驱）：循环：while (p != NULL && j < i)，每次 p = p->next; j++;
判断删除位置是否合法：如果 p 为 NULL，说明第 i 个元素不存在，删除失败。
保存待删除结点指针 q，即 q = p->next.
将前驱结点 p 的 next 指向 q 的下一个结点，即 p->next = q->next.
释放结点 q 的空间。
返回成功状态。

C语言实现：

在函数实现中，声明 2 个 Node 类型的指针 p 和 q，p 用于遍历链表，初始指向传入的线性表 L 的头结点, q 用于暂存待删除结点。
使用计数器 j 来记录当前结点的位置。
使用 while 循环的原因是单链表的结构体中没有表长，无法预知循环次数，因此不方便使用 for 来控制循环。其主要核心思想就是工作指针后移，直到找到第 i-1 个结点（即待删除结点的前驱）。
- 循环条件是 p->next 存在（即还没到链表末尾）且 j < i（还没到第 i-1 个结点）。
- 循环体内容是让 p 指向下一个结点，并计数器加1。
循环结束后，若 p->next == NULL，说明第 i 个结点不存在，返回错误。
否则，将 p->next（即第 i 个结点）赋给 q，保存待删除结点。
用 *e = q->data 保存被删除结点的数据。令 p->next = q->next，即跳过第 i 个结点，完成删除。
最后用 free(q) 释放被删除结点的内存。

#include <stdio.h>
#include <stdlib.h>

#define OK 1
#define ERROR 0

typedef int Status;   /* 状态信息 */
typedef int ElemType; /* 元素类型 */

typedef struct Node {
  ElemType data;     /* 数据域 */
  struct Node *next; /* 指针域，指向下一个结点 */
} Node;

Status ListDelete(Node *L, int i, ElemType *e) {

  Node *p, *q;
  p = L; /* p指向头结点 */

  int j = 1; /* j为计数器,记录当前结点的位置 */

  while (p->next && j < i) {
    p = p->next; /* p指向第i个结点 */
    ++j;
  }

  if (p->next == NULL) {
    return ERROR; /* 如果p的下一个结点为空，说明第i个位置不存在 */
  }

  q = p->next;       /* q指向第i个结点 */
  *e = q->data;      /* 将第i个结点的数据存入e */
  p->next = q->next; /* p的next指向q的下一个结点 */

  free(q); /* 释放第i个结点的内存 */

  return OK; /* 返回成功状态 */
}

int main(void) {
  Node *head = malloc(sizeof(Node));
  Node *second = malloc(sizeof(Node));
  Node *third = malloc(sizeof(Node));
  head->data = 0;
  head->next = second;
  second->data = 2;
  second->next = third;
  third->data = 3;
  third->next = NULL;

  ElemType deleted;
  int pos = 2; /* 要删除的元素位置 */

  printf("删除前的链表元素： %d -> %d -> %d\n", head->data, second->data,
         third->data);

  if (ListDelete(head, pos, &deleted) == OK) {
    printf("删除位置 %d 的元素 %d 成功！\n", pos, deleted);
    printf("删除后的链表元素：");
    Node *p = head;
    while (p) {
      printf("%d", p->data);
      if (p->next)
        printf(" -> ");
      p = p->next;
    }
    printf("\n");
  } else {
    printf("删除位置 %d 的元素失败！\n", pos);
  }

  return 0;
}

对于单链表的插入和删除算法，都是遍历查找第 i 个元素，然后插入和删除元素。如果不知道第 i 个元素的指针位置，他们的时间复都是O（n）。如果希望从第 i 个位置插入 10 个元素，对于顺序表存储结构，每一次擦汗如都需要移动 n-i 个元素，每次都是O(n),单链表来说，找到第 i 个位置的指针，此时为 O（n），然后就是简单的移动指针赋值，时间复杂度都是 O（1）。显然，对于插入和删除数据越频繁的操作，单链表的效率要高。

单链表的整表创建

创建单链表的过程就是一个动态生成链表的过程。即从“空表”的初始状态起，依次建立各元素结点，并逐个插入链表。

算法思路：

声明一个结点 p 和计数器变量 i.
初始化一空表L.
让L的头结点的指针指向NULL，即建立一个带头结点的单链表。
循环：
- 生成一新结点赋值给p.
- 随机生成一数字赋值给p的数据域p->data.
- 将p插入到头结点与前一新结点之间。

头插法：

始终让新结点在第一的位置。

尾插法：

把每次新结点都插在终端结点的后面。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct Node {
  int data;
  struct Node *next;
} Node;

/* 头插法 */
void CreateListHead(Node **L, int n) {
  Node *p;
  int i;

  srand(time(0)); /* 生成随机数种子 */

  *L = (Node *)malloc(sizeof(Node)); /* 创建头结点 */

  (*L)->next = NULL; /* 初始化头结点的next指针 */

  for (i = 0; i < n; i++) {
    p = (Node *)malloc(sizeof(Node)); /* 创建新结点 */
    p->data = rand() % 100 + 1;       /* 生成0-100之间的随机数 */
    p->next = (*L)->next;             /* 将新结点插入到头结点之后 */
    (*L)->next = p;                   /* 更新头结点的next指针 */
  }
  (*L)->next = NULL; /* 确保头结点的next指针为NULL */
}

/* 尾插法 */
void CreateListTail(Node **L, int n) {
  Node *p, *tail; /* 尾指针 */

  int i; /* 生成随机数的循环变量 */

  srand(time(0)); /* 生成随机数种子 */

  *L = (Node *)malloc(sizeof(Node));

  (*L)->next = NULL; /* 初始化头结点的next指针 */
  tail = *L;         /* 尾指针指向头结点 */

  for (i = 0; i < n; i++) {
    p = (Node *)malloc(sizeof(Node)); /* 创建新结点 */
    p->data = rand() % 100 + 1;       /* 生成0-100之间的随机数 */
    p->next = NULL;                   /* 新结点的next指针初始化为NULL */
    tail->next = p;                   /* 将新结点插入到尾部 */
    tail = p;                         /* 更新尾指针 */
  }
  tail->next = NULL; /* 确保尾结点的next指针为NULL */
}
int main(void) {
  Node *L = NULL; /* 初始化头结点 */
  int n = 5;      /* 要创建的结点数 */

  CreateListHead(&L, n); /* 创建链表 */

  Node *p = L->next; /* 从头结点的下一个开始遍历 */

  printf("L -> ");

  while (p != NULL) {
    printf("%d -> ", p->data); /* 打印结点数据 */
    p = p->next;               /* 移动到下一个结点 */
  }
  printf("NULL\n"); /* 链表结束标志 */

  /* 释放链表内存 */
  p = L->next; /* 从头结点的下一个开始释放 */

  while (p != NULL) {
    Node *temp = p; /* 保存当前结点 */
    p = p->next;    /* 移动到下一个结点 */
    free(temp);     /* 释放当前结点内存 */
  }

  free(L); /* 释放头结点内存 */

  return 0; /* 程序结束 */
}

单链表的整表删除

当我们不打算使用这个单链表时，我们需要把它销毁，其实也就是在内存中释放掉，以便于留出空间给其他程序或软件使用。

单链表整表删除的算法思路如下:

声明一结点p和q;
将第一个结点赋值给p;
循环:
- 将下一结点赋值给q;
- 释放p;
- 将q赋值给p。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef int Status;

typedef struct Node {
  int data;
  struct Node *next;
} Node;

Status ClearList(Node **L) {
  Node *p, *q;
  p = (*L)->next; // 从头结点的下一个开始

  while (p) {
    q = p->next; // 保存下一个节点
    free(p);     // 释放当前节点
    p = q;       // 移动到下一个节点
  }
  (*L)->next = NULL; // 清空链表后，头结点的next指针指向NULL

  return 0; // 返回成功状态
}

int main(void) {
  Node *L = (Node *)malloc(sizeof(Node)); // 创建头结点
  L->next = NULL;                         // 初始化头结点的next指针
  int n = 5;                              // 假设我们要创建5个节点

  srand(time(0)); // 生成随机数种子

  for (int i = 0; i < n; i++) {
    Node *p = (Node *)malloc(sizeof(Node)); // 创建新节点
    p->data = rand() % 100 + 1;             // 生成0-100之间的随机数
    p->next = L->next;                      // 将新节点插入到头结点之后
    L->next = p;                            // 更新头结点的next指针
  }

  printf("Before clearing: ");

  Node *p = L->next; // 从头结点的下一个开始遍历

  while (p != NULL) {
    printf("%d -> ", p->data); // 打印节点数据
    p = p->next;               // 移动到下一个节点
  }

  printf("NULL\n");

  ClearList(&L);

  printf("After clearing: ");

  p = L->next;

  while (p != NULL) {
    printf("%d -> ", p->data);
    p = p->next;
  }

  printf("NULL\n");

  free(L);

  return 0;
}

单链表结构与顺序存储结构优缺点

存储结构	优点	缺点
顺序存储结构	支持随机访问，查找快（O(1））
结构简单，易实现存储空间连续，利于批量操作	插入、删除效率低（O(n)）容量固定，扩容不灵活可能造成空间浪费或溢出	查找多、改动少、元素数量固定
链式存储结构	插入、删除效率高（O(1)）
空间利用灵活，易扩展不需预分配大块内存	不支持随机访问，查找慢（O(n)）需额外存储指针，空间开销大结构复杂，实现难	插入、删除多，元素数量变化大

静态链表

定义

如果不允许使用指针，就可以用数组来代替指针描述单链表。即用数组描述的链表叫静态链表。

备用链表:未使用的数组元素

静态链表存储结构

数组的元素有2个数据域组成：

数据域 data 存放数据。
游标 cur(Cursor)相当于单链表中的 next 指针，存放该元素后继在数组中的下标, 如下图。

/* 线性表的静态链表存储结构 */
#define MAXSIZE 1000 /* 假设链表的最大长度是1000 */

typedef struct
{
    ElemType data;
    int cur;            /* 游标（Cursor）,为 0 时表示无指向*/
} Component,StaticLinkList[MAXSIZE];

特点：

数组第一个和最后一个元素做特殊处理，不存数据。
数组第一个元素（下标为 0 的元素）的 cur 存放备用链表的第一个结点的下标。
数组最后一个元素的 cur 存放第一个有数值元素的下标，相当于链表头结点的作用，当整个链表为空时，cur 为 0。

没有元素的时候：

有元素的时候：

静态链表的插入操作

动态链表中：结点的申请和释放借用 malloc 和 free 2个函数实现。在静态链表中：操作的是数组，需要自己实现这 2 个函数。

/* 申请静态链表节点 */
static int Malloc_SLL(StaticLinkList space)
{
    int i = space[0].cur; /* 获取第一个空闲节点的索引 */

    if(i)
        space[0].cur = space[i].cur; /* 更新头结点的空闲指针,指向下一个位置 */

    return i; /* 返回分配的节点索引 */
}

space[0].cur: 第一个元素的 cur 存放空闲链表的首元素下标。
space[i].cur：存放 i + 1 位置的下标。

统计有效链表长度：

数组最后一个元素的 cur 存放有效数据的下标。
在静态链表的实现中，约定 cur == 0 代表没有下一个节点，即链表到此结束。
i = L[i].cur 控制结点移动。

static int ListLength(StaticLinkList L) 
{
    int len = 0;
    int i = L[MAXSIZE-1].cur;
    while(i !=0)
    {
        len++;
        i = L[i].cur; /* 移动到下一个节点,下一位置数据为空，则cur用0表示 */
    }
    return len;
}

静态链表插入算法思路：

找到空闲结点：通过数组第一个元素（通常下标为0）的 cur 字段，获得空闲链表的第一个结点下标。
分配新结点：将要插入的数据存入该空闲结点的 data 字段,并准备好它的 cur 字段。
找到插入位置的前驱结点：从有效链表头结点（通常下标为 MAXSIZE-1）出发，遍历到插入位置的前一个结点。
调整指针（游标）：
- 新结点的 cur 指向插入位置的结点（即前驱结点原本的cur）。
- 前驱结点的 cur指向新结点下标。
跟新空闲链表：将空闲链表头结点的 cur指向下一个空闲结点。

#include <stdio.h>

#define MAXSIZE 100
#define OK 1
#define ERROR 0

typedef int Status;
typedef int ElemType;

typedef struct {
  ElemType data;
  int cur; /* 当前节点的索引 */
} Component, StaticLinkList[MAXSIZE];

/* 申请静态链表节点 */
static int Malloc_SLL(StaticLinkList space) {
  int i = space[0].cur; /* 获取第一个空闲节点的索引 */

  if (i)
    space[0].cur = space[i].cur; /* 更新头结点的空闲指针,指向下一个位置 */

  return i; /* 返回分配的节点索引 */
}

/* 统计有效链表长度 */
static int ListLength(StaticLinkList L) {
  int len = 0;
  int i = L[MAXSIZE - 1].cur; /* 最后元素的 cur 存有效数据的下标 */
  while (i != 0) {
    len++;
    i = L[i].cur; /* 移动到下一个节点,下一位置数据为空，则cur用0表示 */
  }
  return len;
}

/* 插入元素 */
static Status ListInsert(StaticLinkList L, int i, ElemType e) {
  int j, k, l;

  k = MAXSIZE - 1; /* 头结点的索引 */
  int len = ListLength(L);
  if (i < 1 || i > len + 1)
    return ERROR;

  j = Malloc_SLL(L); /* 分配新节点 */

  if (j) {
    L[j].data = e;
    for (l = 1; l < i; l++)
      k = L[k].cur;      /* 找到插入位置的前一个节点 */
    L[j].cur = L[k].cur; /* 新节点的cur指向插入位置的下一个节点 */
    L[k].cur = j;        /* 前一个节点的cur指向新节点 */
    return OK;           /* 插入成功 */
  }

  return ERROR; /* 插入失败，空间不足 */
}

int main(void) {
  StaticLinkList L;
  int i, n;

  /* 初始化静态链表 */
  for (i = 0; i < MAXSIZE - 1; i++)
    L[i].cur = i + 1; /* 设置每个节点的cur指向下一个节点 */

  L[MAXSIZE - 1].cur = 0; /* 尾节点的cur指向0 */
  L[0].cur = 1;           /* 头结点的cur指向第一个空闲节点 */

  n = 5;
  int test_data[5] = {10, 20, 30, 40, 50};

  for (i = 1; i <= n; i++) {
    if (ListInsert(L, i, test_data[i - 1]) == OK)
      printf("Element %d inserted successfully.\n", test_data[i - 1]);
    else
      printf("Failed to insert element %d.\n", test_data[i - 1]);
  }

  /* 打印插入前链表内容 */
  printf("Static Linked List before insert: ");

  int print_cnt = 0;

  for (i = L[MAXSIZE - 1].cur; i != 0 && print_cnt < MAXSIZE;
       i = L[i].cur, print_cnt++)
    printf("%d ", L[i].data);

  if (print_cnt >= MAXSIZE)
    printf("[Error] Possible loop detected!\n");
  else
    printf("\n");

  /* 在第3个位置插入99 */
  if (ListInsert(L, 3, 99) == OK)
    printf("Element 99 inserted at position 3 successfully.\n");
  else
    printf("Failed to insert element 99 at position 3.\n");

  /* 打印插入后链表内容 */
  printf("Static Linked List after insert: ");

  print_cnt = 0;

  for (i = L[MAXSIZE - 1].cur; i != 0 && print_cnt < MAXSIZE;
       i = L[i].cur, print_cnt++)
    printf("%d ", L[i].data);

  if (print_cnt >= MAXSIZE)
    printf("[Error] Possible loop detected!\n");
  else
    printf("\n");

  return 0;
}

静态链表的删除

算法思路

合法性检查：检查要删除的位置 i 是否有效（1 ≤ i ≤ 当前链表长度）。如果不合法，直接返回错误。
找到前驱节点：从头结点（通常是数组最后一个元素）开始，遍历链表，找到第 i-1 个节点（即要删除节点的前一个节点）。
修改指针：令前驱节点的 cur 指向被删除节点的下一个节点（即 L[k].cur = L[index].cur），这样就把要删除的节点从链表中摘除。
释放节点：将被删除节点的 cur 指向空闲链表的头结点，并更新空闲链表头指针（即调用 Free_SLL），实现节点的复用。
返回状态：删除成功返回 OK，失败返回 ERROR。

#include <stdio.h>

#define MAXSIZE 100
#define OK 1
#define ERROR 0

typedef int Status;
typedef int ElemType;
typedef struct {
    ElemType data;
    int cur; /* 当前节点的索引 */
}Component, StaticLinkList[MAXSIZE];

/* 释放一个静态链表结点 */
void Free_SLL(StaticLinkList space, int index)
{
    space[index].cur = space[0].cur; /* 将当前节点的 cur 指向空闲链表的头 */
    space[0].cur = index; /* 更新空闲链表头指针 */
}

int ListLength(StaticLinkList L)
{
    int j = 0;
    int i = L[MAXSIZE - 1].cur; /* 最后元素的 cur 存有效数据的下标 */

    while(i)
    {
        i = L[i].cur; /* 获取下一个结点 */
        j++; /* 计数结点个数 */
    }

    return j; /* 返回链表长度 */
}

/* 删除在 L 中第 i 个数据元素 e */
Status ListDelete(StaticLinkList L, int i)
{
    int index, k;

    if(i < 1 || i > ListLength(L))
        return ERROR;               /* i 不合法 */

    k = MAXSIZE - 1;            /* 头结点的索引 */

    for(index = 1; index <= i - 1; index++)
        k = L[k].cur;           /* 找到要删除元素的前一个节点 */

    index = L[k].cur;                   /* j 是要删除的节点的索引 */
    L[k].cur = L[index].cur;        /* 前一个节点的 cur 指向要删除节点的下一个节点 */

    Free_SLL(L, index);             /* 释放被删除的节点 */

    return OK;                      /* 删除成功 */
}

int main(void)
{
    StaticLinkList L;
    int i;

    /* 初始化静态链表 */
    for (i = 0; i < MAXSIZE - 1; i++) {
        L[i].cur = i + 1; /* 设置每个节点的 cur 指向下一个节点 */
    }
    L[MAXSIZE - 1].cur = 0; /* 最后一个节点的 cur 指向空 */
    L[0].cur = 1; /* 空闲链表的头指针指向第一个节点 */

    // 插入数据到有效链表（头插法）
    int n = 5;
    int test_data[5] = {10, 20, 30, 40, 50};
    int tail = MAXSIZE - 1; // 有效链表的尾部
    for(i = 0; i < n; i++) {
        int j = L[0].cur; // 取空闲链表头
        if (j) {
            L[0].cur = L[j].cur; // 空闲链表头后移
            L[j].data = test_data[i];
            L[j].cur = 0; // 新节点尾部
            L[tail].cur = j; // 有效链表尾部指向新节点
            tail = j; // 更新尾部
        }
    }

    /* 测试 ListDelete 函数 */
    printf("删除前的链表元素:\n");
    for(i = L[MAXSIZE - 1].cur; i != 0; i = L[i].cur) 
    {
        printf("%d ", L[i].data);
    }
    if (ListDelete(L, 2) == OK) {
        printf("删除成功\n");
    } else {
        printf("删除失败\n");
    }
    printf("删除后的链表元素:\n");
    for(i = L[MAXSIZE - 1].cur; i != 0; i = L[i].cur) 
    {
        printf("%d ", L[i].data);
    }

    return 0;
}

运行结果

删除前的链表元素:
10 20 30 40 50 删除成功
删除后的链表元素:
10 30 40 50 
[Done] exited with code=0 in 0.426 seconds

静态链表优缺点

优点	缺点
在插入和删除操作时，只需要修改游标，不需要移动元素,从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点	没有解决连续存储分配带来的表长难以确定的问题，失去了顺序存储结构随机存取的特性

静态链表其实是为了给没有指针的高级语言设计的一种实现单链表能力的方法。

循环链表

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

循环链表带有头结点的空链表如图:

非空的循环链表就如图：

循环链表和单链表的主要差异就在于循环的判断条件上，原来是判断 p->next 是否为空，现在则是 p-next ≠ 头结点，则循环未结束。

如何合并2个循环链表？ 如图：

这样操作：

p=reaA->next;            /* 保存A表tou头结点，即① */
reaA->next = rearB->next->next;         /* 将本是指向B表的第一个结点（不是tou头结点）赋值给reaA->next,即② */
reaB->next = p;             /* 将原A表的头结点赋值给reaB->next,即③ */
free(p);            /* 释放p */

双向链表

双向链表（double linked list）是在单链表的每个结点中，在设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。

双向链表的循环带头结点的空链表如图：

非空的循环的带头结点的双向链表如图：

线性表的双向链表存储结构：

typedef struct DulNode
{
    ElemType data;
    struct DuLNode *prior;      /* 直接前驱指针 */
    struct DuLNode *next;       /* 直接后继指针 */
} DuLNode, *DuLinkList;

双向链表的插入操作：

s->prior = p;           /* ①把p赋值给s的前驱 */
s->nex t= p->next;      /* ②把p->next赋值给s的后继 */
p->next->prior = s;     /* ③把s赋值给p->next的前驱 */
p->next = s;            /* ④把s赋值给p的后继 */

总结：先搞定s的前驱和后继，在搞定后结点的前驱，最后解决前结点的后继。

双向链表的删除操作：

p->prior->next = p->next;    /*① 把p->next赋值给p->prior的后继 */ 
p->next->prior = p->prior;   /*② 把p->prior赋值给p->next的前驱 */
free (p) : /* 释放结点 */

定义

抽象数据类型

物理结构

线性表的顺序存储结构

定义

数组长度和线性表长度区别

地址计算方式

获得算法

插入算法

删除算法

插入和删除的时间复杂度

线性表的链式存储结构

定义

单链表结构体C语言代码描述

单链表的读取算法

单链表的插入算法

单链表的删除算法

单链表的整表创建

单链表的整表删除

单链表结构与顺序存储结构优缺点

静态链表

定义

静态链表存储结构

静态链表的插入操作

静态链表的删除

静态链表优缺点

循环链表

双向链表

发送评论 编辑评论

推荐文章

发送评论编辑评论