C语言数据结构——线性表

前言

线性表是最基本、最简单、也是最常用的一种数据结构，是n个具有相同特性的数据元素的有限序列。

这篇文章讲的是线性表的基本概念，也是为后面几篇线性表的顺序表，线性表的链式表示和实现讲基础。

线性表的定义和特点

首先先讲一下什么是线性结构。线性结构描述了一种数据元素之间的关系，其中每个元素（除了第一个和最后一个）都有一个唯一的前驱元素和一个唯一的后继元素。简单来说，线性结构中的数据元素形成了一条线。

这里补充一下什么是前驱，什么是后继

前驱（Predecessor）

在线性结构中，前驱指一个元素前面的一个元素。除了第一个元素之外，每一个元素都有唯一的前驱。

例如：

在数组中的任意一个元素A_i，其前驱就是A_i-1（i＞1）。
对于第一个元素A_i就没有前驱。

后继（Successor）

在线性结构中，后继指一个元素后面的一个元素。除了最后一个元素之外，每一个元素都有唯一的后继。

例如：

在数组中的任意一个元素A_i，其后继就是A_i+1（i＜n，其中n是元素总数）。
对于最后一个元素A_i就没有后继。

常见的线性结构有：数组、链表、栈、队列、循环缓冲区、双向链表。

这里只罗列，详细的解释可以去对应的文章中查看。

线性表的特点包括：

有限性：线性表是一个有限的数据集合，即它包含的是有限数量的元素。
顺序性：线性表中的元素是有顺序的，每个元素按照一定的次序排列，这通常意味着元素间存在一种先后关系。
同一性：所有元素必须是同一种数据类型，这意味着我们可以对它们进行统一的操作。
可变性：线性表的长度是可以改变的，通过插入或删除操作可以增加或减少线性表中的元素数量。

这里举一个线性表的例子：

26个英文字母的字母表：（A,B,C......,Z）是一个线性表，表中的数据元素是单个字母。在稍复杂的线性表中，一个数据元素可以包含若干个数据项。例如：学生的基本信息，每个学生作为一个数据元素，包括学号、姓名、性别、籍贯、专业等数据项。

线性表可以通过不同的方式实现，最常见的是顺序存储结构（数组）和链式存储结构（链表）。顺序存储结构使用连续的内存空间来存储线性表中的元素，这种方式支持快速随机访问，但是插入和删除操作可能会比较慢，因为需要移动其他元素。链式存储结构则不依赖于连续的内存空间，每个元素作为一个结点，除了存储数据之外还存储指向下一个结点的指针，这样使得插入和删除操作变得高效，但访问特定位置的元素可能需要遍历整个链表。

线性表的类型定义

线性表的类型定义通常是通过编程语言中的抽象数据类型（ADT）来实现的。一个线性表 ADT 会定义一组操作，这些操作允许用户插入、删除、查找和遍历列表中的元素。

除了具体的存储结构外，我们还可以通过抽象数据类型 (Abstract Data Type, ADT) 来描述线性表的操作接口。ADT 定义了线性表应该提供的基本操作，而不关心这些操作的具体实现细节。以下是一些基本操作的例子：

InitList(&L): 初始化线性表。
DestroyList(&L): 销毁线性表并释放其占用的内存。
ClearList(&L): 清空线性表，使其变为空表。
ListEmpty(L): 判断线性表是否为空。
ListLength(L): 获取线性表的长度。
GetElem(L, i, &e): 获取线性表中第i个元素，并将其值赋给e。
LocateElem(L, e, compare()): 在线性表中查找具有给定值的元素。
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()。

抽象数据类型仅是一个模型的定义，并不涉及模型的具体实现，因此这里描述中所涉及的参数不必考虑具体数据类型。在实际应用中，数据元素可能有多种类型，到时可根据具体需要选择使用不同的数据类型。