当前位置：首页 > news >正文

Chapter2.1：线性表基础

news 2025/6/25 21:35:13

该系列属于计算机基础系列中的《数据结构基础》子系列，参考书《数据结构考研复习指导》(王道论坛组编)，完整内容请阅读原书。

线性表是具有相同数据类型的 $n (n \geq 0)$ 个数据元素的有限序列，其中 $n$ 为表长，当 $n = 0$ 时，线性表为一个空表；
若用 $L$ 命名线性表，则一般表示为： $L(a1,a2,⋯,ai,ai+1,⋯,an)L(a_1,a_2,\cdots,a_i,a_{i+1},\cdots,a_n)$ ；其中： $a_1$ 是唯一的"第一个"数据元素，称为表头元素， $a_n$ 是唯一的"最后一个"数据元素，称为表尾元素；
除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继；
线性表的特点：
- 表中元素的个数有限；
- 表中元素具有逻辑上的顺序性，表中元素有其先后次序；
- 表中元素都是数据元素，每个元素都是单个元素；
- 表中元素的数据类型都相同，即每个元素占有相同大小的存储空间；
- 表中元素具有抽象性，即仅讨论元素间的逻辑关系，不考虑元素究竟表示什么内容；
注：线性表是一种逻辑结构，表示元素间一对一的相邻关系；顺序表和链表是指存储结构；

线性表的主要操作：

$InitList(&L){\rm InitList(\&L)}$ ：初始化表，构造一个空的线性表；
$Length(L){\rm Length(L)}$ ：求表长，返回线性表 $L$ 的长度，即 $L$ 中数据元素的个数；
$LocateElem(L,e){\rm LocateElem(L,e)}$ ：按值查找操作，在表 $L$ 中查找具有给定关键字值的元素；
$GetElem(L,i){\rm GetElem(L,i)}$ ：按位查找操作，获取表 $L$ 中第 $i$ 个位置的元素的值；
$ListInsert(&L,i,e){\rm ListInsert(\&L,i,e)}$ ：插入操作，在表 $L$ 中的第 $i$ 个位置上插入指定元素 $e$ ；
$ListDelete(&L,i,&e){\rm ListDelete(\&L,i,\&e)}$ ：删除操作，删除表 $L$ 中第 $i$ 个位置的元素，并用 $e$ 返回删除元素的值；
$PrintList(L){\rm PrintList(L)}$ ：输出操作，按前后顺序输出线性表 $L$ 的所有元素值；
$Empty(L){\rm Empty(L)}$ ：判空操作，若 $L$ 为空表，则返回 $true{\rm true}$ ，否则返回 $false{\rm false}$ ；
$DestroyList(&L){\rm DestroyList(\&L)}$ ：销毁操作，销毁线性表，并释放线性表 $L$ 所占用的内存空间；