顺序表示
需熟练掌握顺序表的定义,并且能够用手写代码实现顺序表上的各种操作。
顺序表定义
顺序表(Sequential List) 是一种常见的数据结构,用于存储一组元素,并按照它们在内存中的物理顺序来排列和访问这些元素。顺序表通常由一个数组或列表构成,其中每个元素都占据一个连续的内存位置,并且可以通过索引值来访问。
假设线性表 A 存储的其实位置为LOC(A)
,每个元素占用的存储空间的大小为sizeof(Elem)
,则 A 所对应的顺序存储结构为:
- 顺序表 优点:
- 随机访问性强:顺序表支持通过索引直接访问元素,访问速度快,时间复杂度为 O(1)。
- 空间使用连续:顺序表中的元素存储在连续的内存块中,这有助于提高缓存的局部性,从而提高访问速度。
- 操作简单:无需处理复杂的指针操作。
- 顺序表 缺点:
- 固定大小或调整大小的开销:对于静态数组,大小是固定的,如果预分配的空间不足或过大,会导致内存浪费或数组溢出。动态数组可以重新分配大小,但这会增加时间和空间开销。
- 插入和删除的时间开销:如果要在顺序表的中间插入或删除元素,可能需要移动大量的元素,时间复杂度为 O(n)。
操作
以下是将每个操作整理为一个章节的版本,使用 ####
作为标题,并附上每段代码的核心思路说明:
数据结构定义
定义了一个顺序表 SeqList
,它使用固定大小的数组 data
来存储元素,length
记录当前表的长度。InitList
函数初始化顺序表,设置长度为 0,表示空表。
#define MAXSIZE 100
typedef struct {
ElementType data[MAXSIZE];
int length;
} SeqList;
void InitList(SeqList *L) {
L->length = 0;
}
插入
在第 pos
个位置插入新元素 e
。首先检查插入位置合法性和空间是否已满,然后从尾部向后移动元素,为插入留出位置,最后将元素插入并更新长度。
bool Insert(SeqList *L, int pos, ElementType e) {
if (L->length == MAXSIZE || pos < 1 || pos > L->length + 1) {
return false;
}
for (int i = L->length; i >= pos; i--) {
L->data[i] = L->data[i - 1];
}
L->data[pos - 1] = e;
L->length++;
return true;
}
删除
删除第 pos
个元素,并通过指针返回删除的元素值。删除后将该位置后的所有元素前移,最后更新长度。
bool Delete(SeqList *L, int pos, ElementType *e) {
if (pos < 1 || pos > L->length) {
return false;
}
*e = L->data[pos - 1];
for (int i = pos; i < L->length; i++) {
L->data[i - 1] = L->data[i];
}
L->length--;
return true;
}
查找操作
在线性表中顺序查找第一个值等于 e
的元素,返回其逻辑位置(从 1 开始);若未找到,返回 0。
int LocateElem(SeqList L, ElementType e) {
for (int i = 0; i < L.length; i++) {
if (L.data[i] == e) {
return i + 1;
}
}
return 0;
}
获取元素
获取顺序表中第 pos
个元素,返回值通过指针 *e
输出。若位置非法则返回 false
。
bool GetElem(SeqList L, int pos, ElementType *e) {
if (pos < 1 || pos > L.length) {
return false;
}
*e = L.data[pos - 1];
return true;
}
判空
判断顺序表是否为空,直接判断 length
是否为 0。
bool IsEmpty(SeqList L) {
return L.length == 0;
}
清空
清空顺序表,只需将 length
置 0,无需实际删除元素,等价于逻辑上的清空。
void ClearList(SeqList *L) {
L->length = 0;
}
长度
返回当前顺序表的长度,即有效元素个数。
int Length(SeqList L) {
return L.length;
}