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

考研复习 Day13| 数据结构与算法--线性表

news 2026/4/17 1:37:14

一、线性表的定义和基本操作

1.1 线性表的定义

线性表：由n(n≥0)个相同数据类型的元素组成的有限序列。

表示形式：

L = (a₁, a₂, ···, aᵢ, aᵢ₊₁, ···, aₙ)

术语	说明
n	表长；n=0 时为空表
a₁	表头元素（唯一的“第一个”元素）
aₙ	表尾元素（唯一的“最后一个”元素）
直接前驱	除第一个元素外，每个元素有且仅有一个
直接后继	除最后一个元素外，每个元素有且仅有一个

线性表的特点：

特点	说明
元素个数有限	—
逻辑上的顺序性	元素之间存在明确的先后次序
元素不可分割	每个元素是独立单位
数据类型相同	每个元素占有相同大小的存储空间
抽象性	只讨论逻辑关系，不考虑具体内容

注：线性表是逻辑结构，顺序表和链表是存储结构，二者属于不同层面的概念，不要混淆。

1.2 线性表的基本操作

操作	描述
`InitList(&L)`	初始化表，构造空线性表
`Length(L)`	求表长，返回元素个数
`LocateElem(L, e)`	按值查找，返回元素位置
`GetElem(L, i)`	按位查找，获取第i个元素值
`ListInsert(&L, i, e)`	插入操作，在第i个位置插入e
`ListDelete(&L, i, &e)`	删除操作，删除第i个元素并用e返回
`PrintList(L)`	输出操作，按顺序输出所有元素
`Empty(L)`	判空操作
`DestroyList(&L)`	销毁操作，释放内存空间

注：
① 基本操作的具体实现取决于存储结构
② 符号&表示C++引用调用；C语言中可通过指针实现

第二部分：顺序表（线性表的顺序存储）

2.1 顺序表的定义

顺序表：用一组地址连续的存储单元依次存储线性表中的数据元素，逻辑上相邻的元素在物理位置上也相邻。

存储地址计算：

设顺序表L的起始地址为LOC(A)，每个元素占sizeof(ElemType)字节，则第i个元素的存储地址为：

LOC(aᵢ) = LOC(A) + (i-1) × sizeof(ElemType)

随机存取：可在 O(1) 时间内直接访问任意位置的元素。

存储结构描述：

（1）静态分配

#define MaxSize 50 typedef struct { ElemType data[MaxSize]; int length; } SqList;

静态分配时，数组大小在编译时固定，空间占满后无法插入新元素。

（2）动态分配

#define InitSize 100 typedef struct { ElemType *data; int MaxSize, length; } SeqList;

C语言动态分配：

L.data = (ElemType*)malloc(sizeof(ElemType) * InitSize);

C++动态分配：

L.data = new ElemType[InitSize];

注意：动态分配仍然是顺序存储结构，支持随机存取，只是存储空间可动态调整。

顺序表的优缺点：

优点	缺点
① 随机访问（O(1)时间）	① 插入删除需移动大量元素（O(n)）
② 存储密度高，无额外指针开销	② 需要连续存储空间，不够灵活

2.2 顺序表上基本操作的实现

考点追踪：顺序表上操作的时间复杂度分析（2023）

1. 顺序表的初始化

静态分配：

void InitList(SqList &L) { L.length = 0; }

动态分配：

void InitList(SeqList &L) { L.data = (ElemType*)malloc(InitSize * sizeof(ElemType)); L.length = 0; L.MaxSize = InitSize; }

2. 插入操作

可以就像一个排好队的一排人，要往其中某个位置插入一人（新元素），因此在插入位置后面的人要从尾部开始依次退后，不然就会踩脚（导致插入数据出现错误）

在第i个位置（1≤i≤L.length+1）插入新元素e。

bool ListInsert(SqList &L, int i, ElemType e) { if (i < 1 || i > L.length + 1) return false; if (L.length >= MaxSize) return false; for (int j = L.length; j >= i; j--) L.data[j] = L.data[j - 1]; L.data[i - 1] = e; L.length++; return true; }

时间复杂度分析：

情况	移动次数	时间复杂度
最好（表尾插入，i=n+1）	0	O(1)
最坏（表头插入，i=1）	n	O(n)
平均	n/2	O(n)

注意：位序从1开始，数组下标从0开始，注意转换。

3. 删除操作

删除第i个位置（1≤i≤L.length）的元素，用e返回其值。

bool ListDelete(SqList &L, int i, ElemType &e) { if (i < 1 || i > L.length) return false; e = L.data[i - 1]; for (int j = i; j < L.length; j++) L.data[j - 1] = L.data[j]; L.length--; return true; }

时间复杂度分析：

情况	移动次数	时间复杂度
最好（删除表尾，i=n）	0	O(1)
最坏（删除表头，i=1）	n-1	O(n)
平均	(n-1)/2	O(n)

4. 按值查找（顺序查找）

int LocateElem(SqList L, ElemType e) { for (int i = 0; i < L.length; i++) if (L.data[i] == e) return i + 1; return 0; }

时间复杂度：平均比较次数 (n+1)/2 →O(n)

第三部分：线性表的链式表示

3.1 单链表的定义

考点追踪：单链表的应用（2009、2012、2013、2015、2016、2019）

结点结构：

结点类型定义：

typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList;

头指针与头结点：

类型	空表判断
带头结点	`L->next == NULL`
不带头结点	`L == NULL`

引入头结点的优点（方便操作）：

操作统一性：首部插入/删除与其他位置逻辑一致
空表与非空表处理统一：头指针始终非空

3.2 单链表上基本操作的实现

注：默认链表带头结点

1. 单链表的初始化

bool InitList(LinkList &L) { L = (LNode*)malloc(sizeof(LNode)); L->next = NULL; return true; }

2. 求表长

int Length(LinkList L) { int len = 0; LNode *p = L->next; while (p != NULL) { len++; p = p->next; } return len; }

时间复杂度：O(n)

3. 按序号查找

LNode *GetElem(LinkList L, int i) { LNode *p = L; int j = 0; while (p != NULL && j < i) { p = p->next; j++; } return p; }

4. 按值查找

LNode *LocateElem(LinkList L, ElemType e) { LNode *p = L->next; while (p != NULL && p->data != e) p = p->next; return p; }

时间复杂度：O(n)

5. 插入结点操作

考点追踪：单链表插入操作的过程（2016、2024）

bool ListInsert(LinkList &L, int i, ElemType e) { LNode *p = L; int j = 0; while (p != NULL && j < i - 1) { p = p->next; j++; } if (p == NULL) return false; LNode *s = (LNode*)malloc(sizeof(LNode)); s->data = e; s->next = p->next; // 1 新结点指向原后继 p->next = s; // 2 前驱指向新结点 return true; }

重要：步骤①和②的顺序不可颠倒，否则会丢失后继地址。

时间复杂度：O(n)，主要开销在查找前驱。若已知结点指针，后插操作O(1)。

前插操作的技巧（O(1)时间）：将新结点*s插入目标结点*p之后，再交换*p与*s的数据域，逻辑上等效于前插

s->next = p->next; p->next = s; // 交换数据域 ElemType temp = p->data; p->data = s->data; s->data = temp;

6. 删除结点操作

bool ListDelete(LinkList &L, int i, ElemType &e) { LNode *p = L; int j = 0; while (p->next != NULL && j < i - 1) { p = p->next; j++; } if (p->next == NULL) return false; LNode *q = p->next; e = q->data; p->next = q->next; free(q); return true; }

时间复杂度：O(n)

删除给定结点*p的技巧（O(1)时间，不能用于尾结点）：将*p后继结点的（数据）值复制到*p中，然后删除其后继结点。

LNode *q = p->next; p->data = p->next->data; p->next = q->next; free(q);

7. 头插法建立单链表

LinkList List_HeadInsert(LinkList &L) { LNode *s; int x; L = (LNode*)malloc(sizeof(LNode)); L->next = NULL; scanf("%d", &x); while (x != 9999) { s = (LNode*)malloc(sizeof(LNode)); s->data = x; s->next = L->next; L->next = s; scanf("%d", &x); } return L; }

每插入一个结点O(1)，总时间复杂度O(n)。元素顺序与输入顺序相反。

8. 尾插法建立单链表

LinkList List_TailInsert(LinkList &L) { int x; L = (LNode*)malloc(sizeof(LNode)); LNode *s, *r = L; scanf("%d", &x); while (x != 9999) { s = (LNode*)malloc(sizeof(LNode)); s->data = x; r->next = s; r = s; scanf("%d", &x); } r->next = NULL; return L; }

附设尾指针，时间复杂度O(n)。元素顺序与输入顺序一致。
类比C++STL库中的<vector>的push_back尾插操作。

3.3 双链表

结点类型定义：

typedef struct DNode { ElemType data; struct DNode *prior, *next; } DNode, *DLinkList;

插入操作（在结点p之后插入s）：

考点追踪：双链表中插入操作的实现（2023）

s->next = p->next; // 1 p->next->prior = s; // 2 s->prior = p; // 3 p->next = s; // 4

步骤①必须在步骤④之前，否则会丢失后继地址。（这让我想到了一句话，干事之前要先安排好后路，即先要指向后继结点，防止丢失后继地址，也就是步骤1）

删除操作（删除结点p的后继q）：

考点追踪：双链表中删除操作的实现（2016）

p->next = q->next; q->next->prior = p; free(q);

3.4 循环链表

循环单链表：

尾结点的next指向头结点
判空条件：L->next == L
从任意结点出发可遍历整个链表

考点追踪：循环单链表中删除首元素的操作（2021）

循环双链表：

头结点的prior指向尾结点
尾结点的next指向头结点

3.5 静态链表

用数组模拟链式存储，指针用数组下标（游标）表示。

#define MaxSize 50 typedef struct { ElemType data; int next; // 下一个元素的数组下标 } SLinkList[MaxSize];

结束标志：next == -1

3.6 顺序表和链表的比较

比较维度	顺序表	链表
存取方式	随机存取 O(1)	顺序存取 O(n)
逻辑与物理结构	逻辑相邻⇔物理相邻	逻辑相邻≠物理相邻
按值查找	无序O(n)；有序O(log₂n)	O(n)
按序号查找	O(1)	O(n)
插入/删除	需移动约一半元素 O(n)	修改指针 O(1)（已知位置）
空间分配	需预分配容量	按需扩展，但每结点有指针开销
存储密度	高（=1）	低（<1）