数据结构：线性表
1、线性表概述
1.1线性表的定义
线性表（list）：零个或多个数据元素的有限序列。
简单地来说，我们可以用下面这张图来描述一个线性表：
1.2 线性表的存储结构
1.2.1顺序存储结构——顺序表
顺序表是将数据全部存储到一整块内存空间中，数据元素之间按照次序挨个存放。
1.2.2链式存储结构——链表
链表不强制要求数据在内存中集中存放，各个元素可以分散存放在内存中。
2、顺序表
2.1顺序表的定义
接下来我们用代码进行描述：
#define LIST_MAX_NUM 100
typedef struct
{
int list[LIST_MAX_NUM];
int len;
}Linear_List_Type;
Linear_List_Type mylist;这段代码定义了一个结构体类型 Linear_List_Type，并创建了一个该类型的变量 mylist。
代码解析：
-
typedef struct { ... } Linear_List_Type;：这行代码定义了一个结构体，并使用typedef为该结构体起了一个别名Linear_List_Type。这意味着在以后使用Linear_List_Type这个名字就代表了这个结构体类型。 -
int list[LIST_MAX_NUM];：这是一个整数数组，数组的长度是LIST_MAX_NUM，这个宏应该在其他地方定义过，用来表示数组的最大长度。 -
int len;：这是一个整数变量，用来存储数组中当前有效元素的数量，也就是线性表的长度。 -
Linear_List_Type mylist;：这行代码定义了一个名为mylist的变量，类型是Linear_List_Type，也就是前面定义的结构体类型。mylist代表一个具体的线性表实例。
2.2顺序表的基本操作
2.2.1初始化
初始化操作的意义：
- 该函数将传入的线性表的长度
len设置为 0，从而将线性表重置为空状态。 - 在数据结构中，初始化操作是确保线性表在使用之前处于一个已知的、正确的状态。这通常是使用线性表的第一步操作。
void InitList(Linear_List_Type* p)
{
p->len = 0;
}代码解析：
-
函数声明
void InitList(Linear_List_Type* p)：void：表示该函数没有返回值。InitList：函数名称，用于初始化线性表。Linear_List_Type* p：函数的参数是一个指向Linear_List_Type类型的指针p。这个指针用于指向需要初始化的线性表。
-
p->len = 0;：p->len：通过指针p访问线性表结构体中的len成员。=：赋值运算符。0：将len设置为 0。- 这一步将线性表的长度初始化为 0，表示线性表为空，没有有效元素。
2.2.2插入
假设线性表的存储空间为V[1:m]，表长为n，插入位置i，插入元素b，则代码如下：
void InsertList(Linear_List_Type* p, int m, int i, int b)
{
int k;
if (p->len == m)
{
printf("overflow");
return;
}
if (i > p->len)
{
i = p->len + 1;
}
else if (i < 1)
{
i = 1;
}
for (k = p->len; k >= i; k--)
{
p->list[k] = p->list[k - 1];
}
p->list[i - 1] = b;
p->len += 1;
}-
参数说明：
- 线性表的指针用于操作目标线性表。
- 参数包括线性表的最大容量、插入位置、以及要插入的元素。
-
判断线性表是否已满：
- 首先检查线性表当前长度是否已达最大容量，如果已满，打印“overflow”提示并退出函数，防止溢出错误。
-
调整插入位置：
- 检查插入位置是否超出当前长度，如果插入位置大于当前长度，将位置调整为表的末尾。
- 如果插入位置小于 1，则将插入位置调整为第一个位置。
-
移动元素腾出插入空间：
- 从线性表的最后一个元素开始，逐个向后移动元素，为插入新元素腾出空间。
-
插入新元素：
- 将新元素插入到调整好的位置。
-
更新线性表长度：
- 插入后，更新线性表的长度以反映新的元素数量。
2.2.3删除
void DeleteList(Linear_List_Type* p, int i)
{
int k;
if (p->len == 0)
{
printf("underflow");
return;
}
if (i<1 || i>p->len)
{
printf("this element is not in the list");
return;
}
for (k = i; k < p->len; k++)
{
p->list[k - 1] = p->list[k];
}
p->len -= 1;
return;
}步骤解析：
-
函数定义与参数说明：
Linear_List_Type* p：指向线性表的指针，操作的目标是这个线性表。int i：表示要删除的元素的位置，从 1 开始计数。
-
检查线性表是否为空：
if (p->len == 0)：判断线性表是否为空，即当前长度是否为 0。- 如果线性表为空，则打印
"underflow"提示，表示删除操作无法进行，并立即返回。
-
检查删除位置是否有效：
if (i < 1 || i > p->len)：判断插入位置是否超出有效范围。- 如果
i小于 1 或大于当前线性表的长度，说明删除位置无效。 - 打印
"this element is not in the list"提示，并退出函数。
- 如果
-
移动元素填补空位：
for (k = i; k < p->len; k++)：从删除位置i开始，将其后的元素依次向前移动。p->list[k - 1] = p->list[k];：将第k位置的元素移动到k-1位置，逐步覆盖被删除的元素位置。
-
更新线性表的长度：
p->len -= 1;：删除元素后，线性表的长度减少 1。
-
函数返回：
return;：结束函数，返回到调用者。
总结：