【数据结构】线性表的定义和基本操作
线性表的定义和基本操作
在学习一个具体的数据结构的时候，需要关注数据结构的三要素：① 逻辑结构（定义）；② 物理结构（存储结构）；③ 数据的运算（基本操作）
【线性表的物理结构分为：①顺序表（顺序存储）和 ②链表（链式存储），会在之后进行详细介绍】
线性表的定义
线性表是具有相同数据类型的 n（n≥0）个数据元素的有限序列，其中 n 为表长，当 n=0 时线性表是一个空表
【注意：① 元素的数据类型相同意味着每个元素所占空间一样大；② 线性表是有限序列意味着各元素之间有先后次序且数量是有限的】
若用 L 命名线性表，则其一般表示为 L = ( a 1 , a 2 , … , a i , a i + 1 , … , a n ) L=(a_1,a_2,…,a_i,a_{i+1},…,a_n) L=(a1,a2,…,ai,ai+1,…,an)
- a i a_i ai 是线性表中的 “第 i 个” 元素线性表中的位序【注意位序是从1开始的，数组下标是从0开始的】
- “ a 1 a_1 a1” 是表头元素，“ a n a_n an” 是表尾元素
- 除第一个元素外，每个元素有且仅有一个直接前驱；除最后一个元素外，每个元素有且仅有一个直接后继
线性表的基本操作
- InitList(&L)：初始化表，构造一个空的线性表 L，分配内存空间
- DestoryList(&L)：销毁操作，销毁线性表，并释放线性表 L 所占用的内存空间
- ListInsert(&L,i,e)：插入操作，在表 L 中的第 i 个位置上插入指定元素 e
- ListDelete(&L,i,&e)：删除操作，删除表 L 中第 i 个位置的元素，并用 e 返回删除元素的值
- LocateElem(L,e)：按值查找操作，在表 L 中查找具有给定关键字值的元素
- GetElem(L,i)：按位查找操作，获取表 L 中第 i 个位置的元素的值
其他常用操作
- Length(L)：求表长，返回线性表 L 的长度，即 L 中数据元素的个数
- PrintList(L)：输出操作，按前后顺序输出线性表 L 的所有元素值
- Empty(L)：判空操作，若 L 为空表，则返回 true，否则返回 fales
实现数据结构的基本操作的原因：
① 团队合作编程，某人定义的数据结构要让其他人能够很方便的使用（封装）
② 将常用的操作/运算封装成函数，避免重复工作，降低出错风险
本文主要参考《王道计算机考研 数据结构》课程视频