线性表
线性表由具有相同数据类型的n个元素构成，这些元素之间存在一一对应的线性关系。其中n为表长，当n=0的时候线性表是一个空表。简单来说，线性表中的元素排列成一条线，每个元素最多有一个直接的前驱和后继（除第一个和最后一个元素外）。线性表的第一个数据元素称为表头元素，最后一个数据元素称为表尾元素。
线性表的特点
- 表中元素的个数有限。
- 表中元素具有逻辑上的顺序，有先后次序。
- 表中元素都是数据元素，每个元素都是单独的基本单位。
- 表中元素的数据类型相同，占用相同大小的存储空间。
- 表中元素具有抽象性，表示逻辑上的数据对象。
- 表中每个元素除首末元素外，有且仅有一个直接前驱和一个直接后继，保证线性关系。
- 线性表可用顺序存储（如数组）或链式存储（如链表）两种方式实现。
- 支持按位置访问元素，比如通过索引或指针遍历。
- 线性表的逻辑结构独立于物理存储，实现方式多样。
线性表的基本操作
InitList(&L); // 初始化线性表
Length(L); // 求表长。返回表L的长度，即L中数据元素的个数
LocateElem(L, e); // 按值查找操作，即查找表中具有给定e的元素
GetElem(L, i); // 按位查找操作，获取表L中第i个位置的元素的值
ListInsert(&L, i, e); // 将元素e插入表L的第i个位置
ListDelete(&L, i, &e); // 删除表L第i个位置的元素，并用e返回删除元素的值
PrintList(L); // 按先后顺序打印出表L的所有元素值
Empty(L); // 判断表L是否为空，为空返回true，否则返回false
DestyoyList(&L); // 销毁线性表
线性表的顺序表示：顺序表
线性表的顺序存储也称顺序表。
顺序表是一种线性表的存储结构，也叫做“顺序存储结构”或“顺序结构”。它将线性表中的元素按顺序存放在一块连续的存储空间中（通常是数组），每个元素占用相同大小的存储单元。通过元素的下标，可以快速访问和定位元素。简单来说，顺序表就是利用数组实现的线性表。
由于每个数据元素的存储位置都和顺序表的起始位置相差一个和该数据元素的位序乘正比的常数，因此顺序表的任意数据元素都支持随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。
随机存取：只要一种数据结构能够在常数时间 O(1) 内直接找到任意元素的地址，就可以称之为支持随机存取。支持随机存取的数据结构具有以下特征：
直接访问：能够直接访问任何元素而不需要依赖于顺序遍历。例如，通过索引或其他唯一标识符（如键）可以直接获取到数据。
时间复杂度：支持随机存取的关键是，在访问任何元素时，不论元素在数据结构中的位置，都能保持常数时间的访问复杂度 O(1)。这意味着，无论数据的大小如何，访问时间始终是固定的。
静态分配内存空间的顺序表实例
#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
#define MaxSize 100
// 描述一个顺序表的存储结构
typedef struct
{
unsigned char data[MaxSize];
unsigned int length;
} SqList;
// 顺序表初始化
void InitList(SqList *L)
{
L->length = 0;
}
// 求表长
int Length(SqList L)
{
return L.length;
}
// 按值查找操作，即查找表中具有给定值e的元素
int LocateElem(SqList L, unsigned char e)
{
for (int i = 0; i < L.length; i++)
{
if (L.data[i] == e)
return i + 1;
}
return 0;
}
// 按位查找操作，获取表L中第i个位置的元素的值
int GetElem(SqList L, unsigned int i)
{
if (i < 1 || i > L.length)
return 0;
else
return (L.data[i - 1]);
}
// 将元素e插入表L的第i个位置
bool ListInsert(SqList *L, unsigned int i, unsigned char e)
{
if (i < 1 || i > L->length + 1)
return false;
if (L->length >= MaxSize)
return false;
// 搬运元素的时候注意要从后往前开始搬运，从前往后会导致前面的数据元素把后面的元素覆盖掉
for (int j = L->length; j >= i; j--)
L->data[j] = L->data[j - 1];
L->data[i - 1] = e;
L->length++;
return true;
}
// 删除表L第i个位置的元素，并用e返回删除元素的值
bool ListDeleteSqList(SqList *L, unsigned int i, unsigned char *e)
{
if (i < 1 || i > L->length + 1)
return false;
if (L->length >= MaxSize)
return false;
*e = L->data[i-1];
for (int j = i; j < L->length; j++)
L->data[j-1] = L->data[j];
L->length--;
return true;
}
// 按先后顺序打印出表L的所有元素值
void PrintList(SqList *L)
{
for (int i = 0; i < L->length; i++)
{
printf("Array index:%d, data:%d\r\n", i, L->data[i]);
}
}
// 判断表L是否为空，为空返回true，否则返回false
bool Empty(SqList L)
{
if (L.length == 0)
return true;
else
return false;
}
// 销毁顺序表
void DestyoyList(SqList *L)
{
L->length = 0;
L = NULL;
}
线性表的链式表示：链表
顺序表虽然具有随机存取的优点，但是进行删除和插入的操作时需要移动大量的元素，并且需要一段连续的内存空间进行存储。而链式存储的线性表，不需要使用连续的一段内存空间来存储整个线性表，它是利用 “链” 建立元素之间的逻辑关系，因此插入和删除操作不需要移动元素，只需要修改指针，但这样也就失去了顺序表随机存取的优点。
链表是一种线性表的链式存储结构。每个节点包含数据部分和指针部分，指针指向下一个节点的位置，这样节点按逻辑顺序连接起来，形成一个线性结构。通过指针的连接，可以方便地进行插入和删除操作，不需要像顺序表那样移动大量元素。
- 单链表：
- 除尾节点外，每个节点只有一个指针，指向下一个节点。
- 尾节点的指针指向
NULL，表示链表结束。
- 双链表：
- 除头尾节点外，每个节点有两个指针，分别指向上一个节点和下一个节点。
- 头节点的前驱指针指向
NULL，后继指针指向下一个节点。 - 尾节点的后继指针指向
NULL，前驱指针指向上一个节点。
- 循环单链表：
- 每个节点都有一个指针指向下一个节点。
- 尾节点指针不指向
NULL，而是指向头节点，形成环状结构。
- 循环双链表：
- 每个节点有两个指针，分别指向上一个节点和下一个节点。
- 头节点的前驱指针指向尾节点，尾节点的后继指针指向头节点，形成双向环状结构。
动态分配内存空间的单链表实例
#include <stdio.h>
#include <stdint.h>
#include <stdbool.h>
#include <stdlib.h>
typedef struct Node
{
int data;
struct Node *next;
} Node, *Linklist;
/**
* 方法1：初始化链表头指针（通过入口参数传入指针的地址）
* @param L 指向链表头指针的指针（二级指针）
* @return true 分配成功，false 分配失败
*
* 说明：
* - 函数接收一个指向头指针变量的指针（Linklist *L），
* 可以在函数内部修改调用者的头指针变量，使其指向新节点。
* - malloc 分配一块内存空间存储一个 Node 结构体。
* - 如果分配失败，返回 false。
* - 分配成功后，设置头节点的数据成员和指针域。
* - 这种写法充分利用了 C 语言的值传递特性，通过传入指针的地址，
* 修改指针本身，实现头指针的初始化。
*/
bool init_Linklist(Linklist *L)
{
*L = malloc(sizeof(Node));
if (*L == NULL)
{
return false;
}
(*L)->data = 1;
(*L)->next = NULL;
return true;
}
/**
* 方法2：初始化链表头指针（通过函数返回新分配的节点指针）
* @return 返回指向链表头节点的指针，分配失败返回 NULL
*
* 说明：
* - 函数内部通过 malloc 分配一个 Node 节点。
* - 给新节点赋予初始数据和指针值。
* - 函数直接返回新分配节点的指针。
* - 调用者通过接收返回值获得链表头指针。
* - 这种写法简洁，调用方便，适用于不需要返回其它状态码，
* 只需要通过 NULL 判断失败的情况。
*/
Linklist INIT2_Linklist(void)
{
Linklist L = malloc(sizeof(Node));
L->data = 1;
L->next = NULL;
return L;
}
// 在头节点后面插入新的节点
bool insert_below_head(Linklist *head, int new_data)
{
Node *new_node = malloc(sizeof(Node));
if (new_node == NULL)
return false;
new_node->data = new_data;
new_node->next = (*head)->next;
(*head)->next = new_node;
return true;
}
// 在头节点前面插入新的节点
bool insert_front_head(Linklist *head, int new_data)
{
// 创建新节点
Node *new_node = malloc(sizeof(Node));
if (new_node == NULL)
return false;
new_node->data = new_data;
// 插入新节点
new_node->next = (*head);
// 更新头指针为新的节点
*head = new_node;
return true;
}
// 在尾节点后面插入新的节点
bool insert_tail(Linklist *head, int new_data)
{
Node *new_node = malloc(sizeof(Node));
if(new_node == NULL)
return false;
new_node->data = new_data;
new_node->next = NULL; // 尾节点的next为NULL
Node *node = *head;
// 遍历找到最后一个节点，循环退出时node为尾节点
while(node->next != NULL)
{
node = node->next;
}
node->next = new_node;
return true;
}
// 在尾节点前面插入新的节点
bool insert_front_tail(Linklist *head, int new_data, int length)
{
Node *new_node = malloc(sizeof(Node));
if(new_node == NULL)
return false;
new_node->data = new_data;
new_node->next = NULL; // 尾节点的next为NULL
Node *node = *head;
while (node->next->next != NULL)
{
node = node->next;
}
new_node->next = node->next;
node->next = new_node;
return true;
}
// 打印链表所有节点
void print_node(Linklist *head)
{
Node *new_node = *head;
if (*head == NULL)
{
printf("链表为空\n");
return;
}
// 遍历打印出所有节点，循环退出时new_node为NULL
while (new_node != NULL)
{
printf("node:%p,DATA:%d\r\n", new_node, new_node->data);
new_node = new_node->next;
}
}
// 删除链表
void delete_list(Linklist *head)
{
while((*head) != NULL)
{
Node *node = *head;
*head = (*head)->next;
free(node);
}
}
// 求链表长度
int getlistlength(Linklist *head)
{
if (*head == NULL)
{
printf("链表长度为:0\n");
return 0;
}
Node *node = *head;
int i = 0;
while(node->next != NULL)
{
i++;
node = node->next;
}
printf("链表长度为:%d (不包含头节点)\n",i);
return i;
}
// 按值查找某个节点，返回该节点的位号
int seek_node_by_value(Linklist *head, int value)
{
Node *current = *head;
int i = 0;
while (current != NULL && current->data != value)
{
current = current->next;
i++;
}
printf("[check by value] index:%d,DATA:%d\r\n",i,current->data);
return i;
}
// 按位置查找某个节点，返回该节点的值,eg：查找第3个节点的值
int seek_node_by_index(Linklist *head, int index)
{
Node *current = *head;
int i = 0;
while (current != NULL && i < index - 1)
{
current = current->next;
i++;
}
printf("[check by index] index:%d,DATA:%d\r\n",i,current->data);
return current->data;
}
// 将某个节点插入第i个位置（不考虑头尾需要的额外处理）
bool insert_node_by_index(Linklist *head, int index, int data)
{
Node *new_node = malloc(sizeof(Node));
if(new_node == NULL)
return false;
new_node->data = data;
Node *current_node = *head;
int i = 0;
// while (i < index - 1) 这个条件正是为了让循环结束时 current_node 指向插入位置的前驱节点，方便在这个位置插入新节点。
while(current_node != NULL && i < index - 1)
{
current_node = current_node->next;
i++;
}
new_node->next = current_node->next;
current_node->next = new_node;
return true;
}
// 删除表中第i个节点
bool delete_node_by_index(Linklist *head, int index)
{
Node *current = *head;
int i = 0;
while(current != NULL && i < index - 1)
{
current = current->next;
i++;
}
// 先保存待删除的节点指针
Node *node_to_delete = current->next;
// 修改指针来断开链表中的该节点
current->next = current->next->next;
// 最后释放内存
free(node_to_delete);
return true;
}
顺序表和链表的比较
存取方式
- 顺序表：采用顺序存取，通过数组的下标可以直接访问任意位置的元素，访问速度快（时间复杂度为O(1)）。
- 链表：采用链式存取，访问元素时需从表头开始沿指针逐个访问，访问特定位置元素时间复杂度为O(n)。
逻辑结构和物理结构
顺序表
逻辑结构是线性表，元素按顺序排列。物理结构是连续的内存空间（数组）。
链表
逻辑结构也是线性表，元素按顺序连接。物理结构是分散的节点，节点通过指针连接，内存地址不必连续。
查找、插入和删除操作
| 操作 | 顺序表 | 链表 |
|---|---|---|
| 查找 | 支持随机访问，时间O(1) | 需顺序遍历，时间O(n) |
| 插入 | 插入位置后元素需移动，时间O(n) | 插入位置通过指针调整，时间O(1)（已找到插入点） |
| 删除 | 删除后元素需移动，时间O(n) | 通过指针调整删除，时间O(1)（已找到删除点） |
空间分配
顺序表：需要预先分配一块连续的固定大小的内存空间，可能造成浪费或空间不够。
链表：动态分配内存，根据需要申请和释放节点空间，节省空间但需要额外指针的存储开销。