线性表
1.线性结构
线性结构是n(>=0)个节点的有穷序列
假定该序列由a(1),a(2),a(3)…a(n)组成，每一个元素代表线性结构的每一个节点，那么，我们称a(1)为起始节点，a(n)为终端节点，而他们的下标i为a(i)在线性表中的序号或位置
现在我们取序列中不位于首端和尾端的三个元素:a(i-1),a(i),a(i+1),此时我们称a(i)为中间节点，a(i-1)和a(i+1)为前驱节点和后继节点,a(i-1)是a(i)的直接前驱，a(i+1)是a(i)的直接后继
为了满足运算的封闭性，通常允许一种逻辑结构出现不含任何节点的情况，此时我们称这种结构为空结构
线性结构的基本特征：若至少含有一个节点，那么除起始节点没有直接前驱，其他节点都有且仅有一个直接前驱；除终端节点没有直接后继，其他节点都有且仅有一个直接后继
2.线性表
线性表是线性结构，它具有以下特征：
- 线性表是有序的，即线性表中的元素是有序的
- 线性表是可索引的，即线性表中的元素可以通过索引访问
- 线性表是可插入的，即线性表可以插入元素
- 线性表是可删除的，即线性表可以删除元素
- 线性表是可复制的，即线性表可以复制
- 线性表是可连接的，即线性表可以连接
- 线性表是可枚举的，即线性表可以枚举
其中，所含节点个数称为线性表的长度（简称表长），表长为0的线性表称为空表
线性表的基本操作： - 创建：创建一个线性表
- 销毁：销毁一个线性表
- 清空：清空一个线性表
- 表间赋值：将线性表a赋给线性表b
- 取值：返回线性表a中序号为i的元素
- 元素赋值：将线性表a中序号为i的元素赋值为x
- 查找：在线性表a中查找值为x的元素，并返回其序号i
- 插入：将元素x插入到线性表a中，插入位置为i
- 删除：删除线性表a中序号为i的元素，并返回该元素
- 长度：返回线性表a的长度
- 判空：判断线性表a是否为空
- 连接：将线性表b连接在a的末尾
- 枚举：遍历线性表a，对线性表a中的每个元素执行一次操作
3.顺序表的结构实现
顺序表是线性表的顺序存储结构，顺序表的一个节点存储线性表的一个节点内容（数据元素），并且不包含其他信息，所有储存节点与其相对应的元素间的逻辑关系是一对一的邻接关系，那么即知顺序表的特点：逻辑结构中相邻的节点在存储结构中仍相邻
//**用一维数组实现线性表**
//假定*datatype*为线性表的数据元素类型
const maxsize = 顺序表的容量 //定义一个常量用以存储顺序表的元素个数
typedef struct //定义顺序表结构
{
datatype data[maxsize]; //在结构体中定义一个数组用以存储数据表的元素
int last; //定义一个变量last，记录顺序表中最后一个元素即终端元素的位置
} sqlist;
sqlist L;
L.last = -1; ///初始化顺序表,-1表示顺序表为空
L.data[L.last - 1];
//注意：last-1才是代表数据表中终端节点的位置，因为数组下标是从0开始线性表的连接实现
1.单链表
单链表节点结构图示：
┌─────────┬───────┐
│ Data │ Next │
├─────────┼───────┤
│ 数据 │ 指针 │
└─────────┴───────┘
▲ ▲
│ │
数据域 指针域如图，单链表的一个存储节点包括俩个部分，分别是Data部分数据域和Next部分指针域，数据域用于存储数据，指针域用于存储下一个节点的指点，在数据域中存放此节点的数据，在指针域中存放下一节点的指针
其中：
- NULL为空指针，他不指向任何节点，只起标志作用，比如终端节点的指针域就是NULL
- head称为头指针变量，改变量的值是指向第一个节点的指针，由于单链表的每一个节点都要被一个指针指向，并且任何节点只能通过指向它的指针才能被引用，因此，会有一个头指针变量，指向第一个节点，再按照各个指针域中的指针找到所需节点
单链表完整结构图解（包含头节点和终端节点）：头指针head │ ▼ ┌─────────┐ ┌─────────┬───────┐ ┌─────────┬───────┐ ┌─────────┬───────┐ ┌─────────┬───────────────┐ │ head │──▶│ Data │ Next │───▶│ Data │ Next │───▶│ Data │ Next │───▶│ Data │ Next（NULL） │───▶ NULL └─────────┘ └─────────┴───────┘ └─────────┴───────┘ └─────────┴───────┘ └─────────┴─────────────────┘ 头节点 节点1 节点2 节点3 终端节点
此时，我们仍然假设数据元素的类型为datatytpe，那么单链表结构定义如下：typedef struct node * pointer;
struct node
{
datatype data; //data是节点数据域
pointer next; //next是节点指针域
};
typedef pointer lklist;
但是这样子看起来似乎不是很清水，此处我们给出C语言中的单链表结构定义：
```C
struct node
{
int data;
struct node *next;
}
int length = 0;在上面这段代码中定义了一个node的结构体类型
data是节点数据域
next是节点指针域
随后我们将演示如何建立链表以及对链表的一些基本操作
1. 初始化链表
struct node *head;
head = NULL;在上面这俩行代码中，我们定义了一个头指针变量head，并初始化为NULL，表示此时链表为空
2. 创建第一个节点
struct node *p;
p = (struct node *)malloc(sizeof(struct node));在上面俩号代码中，我们先声明了node类型的指针变量p
随后我们使用malloc申请了一个内存空间，他的大小是xize参数为sizeof(struct node)，即申请一个node结构体的大小的空间
同时，我们知道malloc申请的内存空间是一个无类型的，也就是返回一个void的指针，因此，我们使用强制类型转换将void转换为node*，并且将其赋给p
scanf ("%d", &p->data);
p->next = NULL;
head = p;
length++;此处，我们从键盘得到一个数据，我们将他储存于p->data即节点数据域中
同时，将p->next指向NULL，表示此时p是链表的第一个节点，并且p是链表的终端节点
最后，将head指向p，表示此时链表头指针head指向第一个节点p
3. 创建第二个节点
struct node *q;
q = (struct node *)malloc(sizeof(struct node));
scanf ("%d", &q->data);
q->next = NULL;
p->next = q;
length++;在上面这段代码中，我们的操作与创建第一个节点大致相同，但是不一样的是，这里我们为了方便演示，使用的是p和q俩个不同的变量，这一点是不规范的，倘若我们要创建几百个节点，变量名远远不够，所以将会在此markdown后的Demo中给出一个较为标准的写法
对上方代码的解释如下：
首先创建一个node类型的指针变量q
创建一个内存空间，大小为sizeof(struct node)，并强制类型转换将其转换为node，将其赋给q
从键盘得到数据，将数据储存于q->data中
将q->next指向NULL，表示此时q是链表的终端节点
将p->next指向q，表示此时p是链表的第一个节点，并且p的next域指向q，表示p和q是相邻的
5. 链表数据的获取
对于数据的获取，我觉得应当加一个length参数，表示链表的长度，这样，我们就可以遍历整个链表，获取其中的数据，同时获取数据时可以避免越界问题，所以此时我们将对上方代码加上length参数，但是按照从上往下顺序阅读上方并没没有任何对length的说明，故此处做说明
5.1 单数据的获取
获取头元素
struct node *index;
index = head;
if (index == NULL) {
printf("链表为空！n");
} else {
printf("链表数据为：%dn", index->data);
}获取链表中任意长度的元素
//首先为了避免冲突，我们事先规定我们的链表中存储的都是int类型的数据
struct node *index;
index = head;
int target = 2;//此处我们设置我们要获取到链表第二个er个节点的数据
for (int i = 1; i <= target; i++) {
index = index->next;//移动到下一个节点
}
printf("链表数据为：%dn", index->data);5.2 遍历链表
遍历链表，获取所有数据
struct node *index;
index = head;
while (index != NULL) {
printf("链表数据为：%dn", index->data);
index = index->next;
}或者使用我们事先定义好的length
struct node *index;
index = head;
for (int i = 1; i <= length; i++) {
printf("链表数据为：%dn", index->data);
index = index->next;
}6. 链表数据的插入
此处我们假设要将元素“3”插入到链表第2个位置上
// 将元素"3"插入到链表第2个位置上
struct node *index;
index = head;
int data = 3;
int target = 2;
struct node *targetNext;
// 移动到插入位置的前一个节点
for (int i = 1; i < target; i++) {
index = index->next;
}
// 保存原节点的next域
targetNext = index->next;
// 创建新节点并插入
struct node *newNode;
newNode = (struct node *)malloc(sizeof(struct node));
newNode->data = data;
newNode->next = targetNext;
index->next = newNode;
length++;(为什么我越写越晕)
7. 链表数据的删除与清空
7.1 删除数据
struct node *index;
index = head;
int target = 2;//目标是删除链表第2个节点
for (int i = 1; i <= target - 1; i++) {
index = index->next;
}
struct node *targetNext;
targetNext = index->next;
length--;删除数据时，我们首先将index移动到目标节点的前一个节点，然后，将index的next域指向目标节点的next域，即index的next域指向目标节点的next域的next域，这样，我们就删除了目标节点
7.2 清空链表
length = 0;
head = NULL;清空链表时，我们直接将head指向NULL，表示此时链表为空
我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com.cn/developer/support-plan?invite_code=1r244lfzquqoz