表ADT

ADT 是 Abstract Data Type，中文叫：
抽象数据类型
你可以先这样理解：
ADT 只关心“这个东西是什么、能干什么”，暂时不关心“底层怎么实现”。
比如“表”这个 ADT 关心的是：
表里面有一堆元素；
元素之间有前后顺序；
可以插入、删除、查找、取元素。
但它暂时不关心底层是用：
数组实现，还是链表实现。
所以 ADT 是一种逻辑层面的定义。

二、表 ADT 的核心概念
数据结构里的“表”通常指：线性表 Linear List
线性表是由 n 个数据元素组成的有限序列：
L = (a1, a2, a3, ..., an)
比如：(10, 20, 30, 40)
就是一个线性表。
它的特点是：
除了第一个元素，每个元素有且仅有一个直接前驱；
除了最后一个元素，每个元素有且仅有一个直接后继。
也就是说，它是“一条线”：
a1 -> a2 -> a3 -> ... -> an

三、表 ADT 的标准定义
ADT List {
数据对象：
D = { ai | ai 属于 ElemType, i = 1, 2, ..., n, n >= 0 }
数据关系：
R = { <ai, ai+1> | i = 1, 2, ..., n - 1 }

基本操作：
    InitList(&L)
    DestroyList(&L)
    ClearList(&L)
    ListEmpty(L)
    ListLength(L)
    GetElem(L, i, &e)
    LocateElem(L, e)
    PriorElem(L, cur_e, &pre_e)
    NextElem(L, cur_e, &next_e)
    ListInsert(&L, i, e)
    ListDelete(&L, i, &e)
    ListTraverse(L)

} ADT List

1. 初始化表
   InitList(&L)
   作用：创建一个空表 L。
   比如原来没有表，初始化后：
   L = ()

2. 销毁表
   DestroyList(&L)
   作用：
   释放表占用的空间。
   对于链表来说，就是把所有 malloc 出来的结点 free 掉。

3. 清空表
   ClearList(&L)
   作用:
   把表里的元素清空，但表本身还存在。
   区别是：
   DestroyList：表没了
   ClearList：表还在，只是元素没了

4. 判断表是否为空
   ListEmpty(L)
   作用：
   如果表为空，返回 true；
   否则返回 false。
   例如：L = ()为空。
   L = (1, 2, 3)不为空。

5. 求表长
   ListLength(L)
   作用：返回表中元素个数。
   例如：L = (10, 20, 30)

长度是：3

6. 按位置取元素
   GetElem(L, i, &e)
   作用：取出线性表 L 中第 i 个元素，用 e 返回。

比如：L = (10, 20, 30, 40)

那么：GetElem(L, 3, &e)

结果：e = 30
注意：教材里的第 i 个位置一般从 1 开始，不是从 0 开始。

7. 按值查找
   LocateElem(L, e)

作用：在线性表 L 中查找值为 e 的元素。

比如：L = (10, 20, 30, 40)

查找：LocateElem(L, 30)

返回位置：3

如果找不到，一般返回 0 或 NULL，具体看教材定义。

8. 找前驱
   PriorElem(L, cur_e, &pre_e)

作用：如果 cur_e 有前驱，就用 pre_e 返回它的前驱。

例如：L = (10, 20, 30, 40)

30 的前驱是：20

第一个元素没有前驱。

9. 找后继
   NextElem(L, cur_e, &next_e)

作用：如果 cur_e 有后继，就用 next_e 返回它的后继。

例如：L = (10, 20, 30, 40)

30 的后继是：40

最后一个元素没有后继。

10. 插入元素
    ListInsert(&L, i, e)

作用：在线性表 L 的第 i 个位置插入元素 e。

例如：L = (10, 20, 30)

执行：

ListInsert(&L, 2, 99)

结果：

L = (10, 99, 20, 30)

原来的第 2 个元素往后移动。

11. 删除元素
    ListDelete(&L, i, &e)

作用：

删除线性表 L 的第 i 个元素，并用 e 返回被删除的元素。

例如：

L = (10, 20, 30, 40)

执行：

ListDelete(&L, 2, &e)

结果：

L = (10, 30, 40)
e = 20
12. 遍历表
ListTraverse(L)

作用：

依次访问表中每个元素。

比如打印：

10 20 30 40
五、表 ADT 和存储结构的关系

线性表的底层实现有两种常见方式：

1. 顺序表
2. 链表

也就是：

线性表 ADT
├── 顺序存储：顺序表
└── 链式存储：链表

1. 顺序表结构

顺序表本质是：

数组 + 当前长度

代码可以写成：

#define MAXSIZE 100

struct SqList {
int data[MAXSIZE];
int length;
};

其中：

data：存放元素
length：当前表中有多少个元素

例如：

L = (10, 20, 30)

对应：

data[0] = 10
data[1] = 20
data[2] = 30
length = 3
2. 初始化顺序表
void InitList(struct SqList* L) {
L->length = 0;
}

意思是：

表刚开始没有元素，所以 length = 0。
3. 按位置取元素

假设教材说取第 i 个元素，位置从 1 开始。

int GetElem(struct SqList L, int i, int* e) {
if (i < 1 || i > L.length) {
return 0;
}

*e = L.data[i - 1];
return 1;

}

注意：

逻辑位置 i 从 1 开始
数组下标从 0 开始
所以第 i 个元素是 data[i - 1]
4. 插入元素

在第 i 个位置插入元素 e：

int ListInsert(struct SqList* L, int i, int e) {
if (i < 1 || i > L->length + 1) {
return 0;
}

if (L->length >= MAXSIZE) {
    return 0;
}

for (int j = L->length; j >= i; j--) {
    L->data[j] = L->data[j - 1];
}

L->data[i - 1] = e;
L->length++;

return 1;

}

核心规律：

顺序表插入：从后往前移动元素。
5. 删除元素

删除第 i 个元素：

int ListDelete(struct SqList* L, int i, int* e) {
if (i < 1 || i > L->length) {
return 0;
}

*e = L->data[i - 1];

for (int j = i; j < L->length; j++) {
    L->data[j - 1] = L->data[j];
}

L->length--;

return 1;

}

核心规律：

顺序表删除：从前往后移动元素。
七、链表：指针实现线性表

1. 链表结点结构

不用 typedef，直接写：

struct ListNode {
int data;
struct ListNode* next;
};

其中：

data：当前结点的数据
next：指向下一个结点

一个结点可以看成：

[data | next]

一个链表可以看成：

10 -> 20 -> 30 -> NULL
2. 初始化带头结点链表

教材里常用带头结点链表。

head -> 10 -> 20 -> 30 -> NULL

其中 head 本身不存有效数据。

初始化：

struct ListNode* InitList() {
struct ListNode* head = malloc(sizeof(struct ListNode));
if (head == NULL) {
return NULL;
}

head->next = NULL;
return head;

}

这样写比二级指针简单。

使用时：

struct ListNode* head = InitList();
3. 遍历链表

如果是带头结点链表：

void TraverseList(struct ListNode* head) {
struct ListNode* p = head->next;

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

}

如果是不带头结点链表，比如：

void TraverseList(struct ListNode* head) {
struct ListNode* p = head;

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

}

区别：

带头结点：从 head->next 开始
不带头结点：从 head 开始
4. 头插法建表

头插法：每次把新结点插到头结点后面。

void CreateListHead(struct ListNode* head, int arr[], int n) {
for (int i = 0; i < n; i++) {
struct ListNode* node = malloc(sizeof(struct ListNode));
node->data = arr[i];

    node->next = head->next;
    head->next = node;
}

}
之后再插入时就在头节点和已有节点之间插入，建立head和新node之间的关系之后，比如说head-> node1
再插入把node2连接到head 然后把原有head和node1之间的指针给node2.next 最后实现的结果就是head->node2->node1
如果数组是：1 2 3
头插后是：3 -> 2 -> 1
规律：头插法会逆序。

5. 尾插法建表
   尾插法：每次把新结点插到链表尾部。
   void CreateListTail(struct ListNode* head, int arr[], int n) {
   struct ListNode* tail = head;

   for (int i = 0; i < n; i++) {
   struct ListNode* node = malloc(sizeof(struct ListNode));
   node->data = arr[i];
   node->next = NULL;

    tail->next = node;
    tail = node;
   

   }
   }
   这个思路是不断把head->node1->node2 其中tail作为一个临时的结构体变量表明位置，一开始tail指向head，表面尾端在head，之后把node1连接过来，head.next=node 之后tail指向node作为新的尾端

如果数组是：1 2 3
尾插后是：1 -> 2 -> 3
规律：
尾插法保持原顺序。
LeetCode 第二题就是这个思想：
tail->next = newNode;
tail = newNode;
6. 按位置查找

查找第 i 个结点，位置从 1 开始。

带头结点版本：
创建一个结构体指针函数，i作为遍历的循环次数，p作为临时结构体变量，只要不到循环次数就一直遍历
struct ListNode* GetElem(struct ListNode* head, int i) {
if (i < 1) {
return NULL;
}

struct ListNode* p = head->next;
int j = 1;

while (p != NULL && j < i) {
    p = p->next;
    j++;
}

return p;

}
如果返回 NULL，说明第 i 个结点不存在。

7. 按值查找
   struct ListNode* LocateElem(struct ListNode* head, int e) {
   struct ListNode* p = head->next;

   while (p != NULL && p->data != e) {
   p = p->next;
   }
   return p;
   }

找到就返回对应结点指针。

找不到就返回：NULL
8. 在第 i 个位置插入

带头结点链表，在第 i 个位置插入 e。

思路：

先找到第 i - 1 个结点 p
再把新结点插到 p 后面

代码：

int ListInsert(struct ListNode* head, int i, int e) {
if (i < 1) {
return 0;
}

struct ListNode* p = head;
int j = 0;

while (p != NULL && j < i - 1) {
    p = p->next;
    j++;
}

if (p == NULL) {
    return 0;
}

struct ListNode* node = malloc(sizeof(struct ListNode));
if (node == NULL) {
    return 0;
}

node->data = e;

node->next = p->next;
p->next = node;

return 1;

}

核心两句：

node->next = p->next;
p->next = node;

口诀：先接后面，再接前面。
9. 删除第 i 个结点

思路：

先找到第 i - 1 个结点 p
q = p->next
让 p 跳过 q
释放 q

代码：

int ListDelete(struct ListNode* head, int i, int* e) {
if (i < 1) {
return 0;
}

struct ListNode* p = head;
int j = 0;

while (p != NULL && j < i - 1) {
    p = p->next;
    j++;
}

if (p == NULL || p->next == NULL) {
    return 0;
}

struct ListNode* q = p->next;
*e = q->data;

p->next = q->next;
free(q);

return 1;

}

核心三句：

struct ListNode* q = p->next;
p->next = q->next;
free(q);

口诀：

先保存，再绕过，最后释放。

答：

顺序表连续存储，支持随机访问，但插入删除需要移动元素；
链表链式存储，不支持随机访问，但插入删除只需修改指针。
4. 问什么时候用顺序表

答：

元素个数变化不大，经常按位置访问。

比如：

数组、成绩表、固定长度数据。
5. 问什么时候用链表

答：

元素个数变化频繁，经常插入删除。

比如：

频繁增删的任务队列、动态集合。
十一、表 ADT

表 ADT，也叫线性表 ADT，是由 n 个数据元素组成的有限序列。
其逻辑特点是：除第一个元素外，每个元素有唯一直接前驱；除最后一个元素外，每个元素有唯一直接后继。

ADT List 由三部分组成：

1. 数据对象
2. 数据关系
3. 基本操作
   线性表有两种主要存储方式：
4. 顺序存储：顺序表，用数组实现，支持随机访问，插入删除慢。
5. 链式存储：链表，用指针连接，随机访问慢，插入删除方便。

ADT 关注“能做什么”，存储结构关注“怎么实现”。
同一个 ListInsert 操作，在顺序表中需要移动元素，在链表中需要修改指针。

最核心一句：
ADT 是逻辑定义，顺序表和链表是物理实现。
线性表 ADT
= 数据对象 + 数据关系 + 基本操作
= 可以用顺序表实现，也可以用链表实现