数据结构:线性表的基本操作与链式表达
一、线性表的定义和基本操作
1.1 定义
线性表是具有相同数据类型的 n 个数据元素的有序数列,n 为表长。第一个元素称为表头元素,除了它,每个元素有且仅有一个直接前驱;最后一个元素称为表尾元素,除了它,每个元素有且仅有一个直接后继。
1.2 特点
- 个数有限
- 逻辑上有顺序性
- 每个元素都是数据元素,且数据类型都相同,占用空间相同
- 具有抽象性
注:线性表是逻辑结构,顺序表和链表是存储结构。
1.3 基本操作
InitList(&L): 初始化表。构造一个空的线性表。Length(L): 求表长。返回线性表 L 的长度,即 L 中数据元素的个数。LocateElem(L, e): 按值查找操作。在表中查找具有给定关键字值的元素。GetElem(L, i): 按位查找操作。获取表 L 中第 i 个位置的元素的值。ListInsert(&L, i, e): 插入操作。在表 L 中的第 i 个位置上插入指定元素 e。ListDelete(&L, i, &e): 删除操作。删除表 L 中第 i 个位置的元素,并用 e 返回删除元素的值。PrintList(L): 输出操作。按前后顺序输出线性表 L 的所有元素值。Empty(L): 判空操作。若 L 为空表,则返回 true,否则返回 false。DestroyList(&L): 销毁操作。销毁线性表,并释放线性表 L 所占用的内存空间。
二、线性表的顺序表示
2.1 定义
线性表的顺序存储称为顺序表,逻辑顺序与物理存储顺序相同,是一种随机存取的存储结构。
位序:就是第几个,相当于下标但不是下标。数组的下标从 0 开始,位序从 1 开始。
2.2 静态分配与动态分配
一维数组可以静态分配也可以动态分配。
静态分配:空间是固定的,多于最大值时,新数据就会溢出,导致数据崩溃。
#define MaxSize 50 // 定义线性表的最大长度
typedef struct {
ElemType data[MaxSize]; // 顺序表的元素
int length; // 顺序表的当前长度
} SqList; // 顺序表的类型定义
动态分配:不是一次性划分所有空间,多余最大值时,会重新开辟更大的新空间,并且把原来的数据 copy 到新的空间中(不是链式存储,仍是顺序存储结构)。
#define InitSize 100 // 表长度的初始定义
typedef {
ElemType *data;
MaxSize, length;
} SeqList;


