数据结构之线性表

2026-02-04

数据结构之绪论与线性表

第二章_线性表

2.1 线性表的定义和基本操作

2.1.1 线性表的定义

线性表是由n(n>=0)个相同数据类型的元素组成的有限序列（数据类型相同，有限，有序）

本小节介绍的线性表是一种逻辑结构，在线性表的重要术语中需要特别注意位序这一概念与数组下标的不同之处：位序是线性表中元素的逻辑位置（从 1 开始编号），数组下标是存储结构中的物理索引（通常从 0 开始），只有在线性表采用数组实现时，二者才满足位序 = 下标 + 1。

2.1.2 线性表的基本操作

线性表的基本操作，本质上就是数据结构三要素中“数据的运算”的具体体现。由于大多数高校采用严蔚敏版教材，这里介绍的函数名也采用这版的：

InitList(&L)：初始化表。构造一个空的线性表 L，并分配内存空间。
DestroyList(&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，否则返回 false。

2.2 顺序表

本小节思维导图如下：

2.2.1 顺序表的定义

线性表的顺序存储也称顺序表。它是用一段地址连续的存储单元依次存储线性表中的数据元素，使得逻辑上相邻的元素在物理位置上也相邻。顺序表的逻辑顺序和存储顺序完全一致

由于任意元素的存储地址与顺序表起始地址之间的偏移量和位序之间存在着线性关系，所以访问表中任意位置元素的时间复杂度为O(1)，这种特性使得线性表的顺序存储结构属于随机存取（不按顺序遍历，直接访问任意一个位置的数据）。比如在《考研视角下的C语言(中)》这篇文章中提到过，访问数组中的元素只需使用 [ ]运算符(*(首地址+偏移量)) 即可，所以在高级程序设计语言中，我们也通常使用数组来实现顺序表。

2.2.2 顺序表的两种实现方式

下面使用静态数组（静态分配）示例顺序表的实现：

#include <stdio.h>
#define MaxSize 10    //定义最大长度
typedef struct{
    int data[MaxSize];//用静态的“数组”存放数据元素
    int length;       //顺序表的当前长度
}SqList;              //顺序表的类型定义

//基本操作—初始化一个顺序表
void InitList(SqList &L){
    L.length=0;       //顺序表初始长度为0
}

int main() {
    SqList L;         //声明一个顺序表
    InitList(L);      //初始化顺序表
    //尝试“违规”打印整个 data 数组,正常来说使用的是i<L.length
    //而且通常不直接写在mian函数中，使用GetElem()函数实现
    for(int i=0; i<MaxSize; i++) 
        printf("data[%d]=%d\n", i, L.data[i]);
    return 0;
}

上述代码中有一个初始化为0的函数操作，这是为了防止读取到脏数据，通常C语言会自动设置为0，但是这是C语言编译器的行为，如果换一个编译器可能就不行了，做题时最好写上InitList函数。

下面使用动态数组（动态分配）示例顺序表的实现，动态分配改变数组大小，本质上是重新申请一片更大的内存空间，然后全部迁移原数组，代码如下：

#include <stdio.h>
#include <stdlib.h>

#define InitSize 10  // 默认的最大长度

// 动态顺序表的结构定义
typedef struct {
    int *data;       // 指向动态分配数组的指针
    int MaxSize;     // 顺序表的最大容量
    int length;      // 顺序表的当前长度
} SeqList;

// 初始化顺序表
void InitList(SeqList &L) {
    // 用 malloc 申请一片连续的存储空间
    L.data = (int *)malloc(InitSize * sizeof(int));
    L.length = 0;
    L.MaxSize = InitSize;
}

// 增加动态数组的长度
void IncreaseSize(SeqList &L, int len) {
    int *p = L.data;
    // 申请更大的空间
    L.data = (int *)malloc((L.MaxSize + len) * sizeof(int));
    // 将数据复制到新区域
    for (int i = 0; i < L.length; i++) {
        L.data[i] = p[i];
    }
    // 更新最大容量
    L.MaxSize = L.MaxSize + len;
    // 释放原来的内存空间
    free(p);
}

int main() {
    SeqList L;          // 声明一个顺序表
    InitList(L);        // 初始化顺序表
    // ...往顺序表中随便插入几个元素...
    IncreaseSize(L, 5); // 增加顺序表长度
    return 0;
}

2.2.3 顺序表的插入

顺序表的插入操作实现代码如下：

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--) { //将第i个元素及以后的元素后移
		L.data[j] = L.data[j - 1];
	}
	L.data[i - 1] = e;
	L.length++;
	return true;
}

注意：i和L.length都是位序，所以1到L.length+1都是合法的插入位置。而在进行后移和插入操作的时候是对下标进行的操作所以最多从第L.length位开始后移

最好时间复杂度：在表尾插入元素（i=n+1)，时间复杂度为O(1)。最坏时间复杂度：在表头插入元素（i=1），需移动全部n个元素，时间复杂度为O(n) 平均时间复杂度：设元素插入任意一个位置的概率相同为p=1/(n+1)，则平均移动次数为：n*p+(n-1)*p+…+1*p = n*(n+1)/2 * 1/(n+1) = n/2，所以平均时间复杂度为O(n)

2.2.4 顺序表的删除

顺序表的删除操作实现代码如下：

bool ListDelete(Sqlist& L, int i, ElemType& e) {
	if (i<1 || i>L.length) {
		return false;
	}
	e = L.data[i - 1]; //将被删除的元素赋值给e带出去
	for (int j = i; j < L.length; j++) {  //将第i个元素之后的位置前移
		L.data[j - 1] = L.data[j];
	}
	L.length--;
	return true;
}

最好时间复杂度：在表尾删除元素（i=n+1)，时间复杂度为O(1)。最坏时间复杂度：在表头删除元素（i=1），需移动全部n个元素，时间复杂度为O(n) 平均时间复杂度：设元素插入任意一个位置的概率相同为p=1/n，则平均移动次数为：(n-1)*p+…+1*p = n*(n+1)/2 * 1/n = (n-1)/2，所以平均时间复杂度为O(n)

2.2.5 顺序表的查找

顺序表的查找操作分为两种，一种是按位序查找，一种是按值查找。按位序查找很简单时间复杂度为O(1)，按值查找的实现代码如下：

int LocalElem(Sqlist L, Elemtype e) {
	int i;
	for (i = 0; i < L.length; i++) {
		if (L.data[i] == e) {
			return i + 1;  //下标为i的元素值为e，返回其位序i+1
		}
	}
	return 0;  //查找失败
}

最好时间复杂度：目标元素在表头（i=1），比较一次，时间复杂度为O(1)。最坏时间复杂度：目标元素在表尾或者不存在，比较n次，时间复杂度为O(n)。平均时间复杂度：设目标元素在第i位的概率为p=1/n，则平均比较次数为(1+n)*n/2 * p = (n+1)/2，故平均时间复杂度为O(n)。

2.3 单链表

本小节思维导图如下：

2.3.1 单链表的定义

线性表的链式存储也称为单链表。他通过一组任意存储单元（不要求地址连续） 来存储线性表中的数据元素。

简单来说，单链表的每个节点组成为数据域+指针域（只有一个指向后继节点的指针） ，与顺序表相比，单链表以失去顺序表的随机存储能力为代价，获取了比顺序表更高效率的插入和删除操作。在《考研视角下的C语言(下)》这篇文章中已经详细介绍了单链表这一数据结构，我就直接贴出链表节点的定义代码如下：

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

//将LNode*重命名为LinkList，是为了在后续代码中强调节点和链表的不同，增加代码的可读性
typedef struct LNode * LinkList;

单链表的结构其表示如图：

2.3.2 单链表的两种初始化方式

单链表的初始化方式主要有两种，分别是带头结点和不带头结点（不是有节点和没节点，这是一种管理方式）。在《考研视角下的 C 语言（下）》中，采用的是不带头结点、通过双指针管理头指针的实现方式。这两种实现方式的主要区别在于：带头结点的单链表在初始化后，其后续的插入和删除操作在代码实现上更加简便。具体的插入与删除操作代码将在后续小节中给出，这里仅对这两种单链表的实现方式进行说明：

//带头结点的单链表初始化
bool InitList(Linklist &L){
    L=(LNode*)malloc(sizeof(LNode)); //创建头结点
    if(L==NULL){  //内存不足，分配失败
        return false;
    }
    L->next=NULL;
    return true;
}

//不带头结点的单链表初始化
bool InitList(Linklist &L){
    L=NULL;
    return true;
}

2.3.3 单链表的插入操作

在《考研视角下的 C 语言（下）》中，介绍了单链表在双指针管理和遍历模式的头插法和尾插法和有序插法，本节将进一步介绍在单指针管理和遍历模式下的按位序插法、指定节点插入、按位序删除、指定节点删除。

按位序插入（带头结点和不带头结点）: 注意：头结点始终是头结点，即使插入新节点到位序为1的位置也是在头结点之后

typedef struct node {
	int data;
	struct node* next;
}LNode;

typedef LNode* Linklist;
bool ListInsert(Linklist &L , int i, int data) {
	if (i < 1) {
		return false;
	}

	LNode* NewNode = (LNode*)malloc(sizeof(LNode));
	NewNode->data = data;
	NewNode->next = NULL;
    
    //不带头结点相对于带头节点，第一个元素需要特殊处理
    //不带头结点加下面代码
	//if (i == 1) {
	//	NewNode->next = L;
	//	L = NewNode;
	//	return true;
	//}

	LNode* p = L;
	int j = 0; //当前p指向的是第几个节点
	while (p != NULL && j < i - 1) {
		p = p->next;
		j++;
	}

	if (p == NULL) {
		return false;
	}

	//链接节点
	NewNode->next = p->next;
	p->next = NewNode;

	return true;
}

指定节点前插操作（给出一个节点，在其之前插入新节点）： 问题在于单指针方法并不知晓前驱节点，通过循环遍历找到其前驱节点的时间复杂度又为O(n)，于是我们采用伪后插方法来实现前插操作（后插节点，交换数据）时间复杂度仅为O(1)。

bool InsertNextNode(LNode* p, int data) {
	if (p == NULL) {
		return false;
	}

	LNode* s = (LNode*)malloc(sizeof(LNode));
	if (s == NULL) { //内存分配失败
		return false;
	}
    
	s->data = data;
	s->next = p->next;
	p->next = s;

    //交换数据
    int temp = s->data;
    s->data = p->data;
    p->data = temp;
	return true;
}

指定节点后插操作（给出一个节点，在其之后插入新节点）：

bool InsertNextNode(LNode* p, int data) {
	if (p == NULL) {
		return false;
	}

	LNode* s = (LNode*)malloc(sizeof(LNode));
	if (s == NULL) { //内存分配失败
		return false;
	}

	s->data = data;
	s->next = p->next;
	p->next = s;
	return true;
}

2.3.4 单链表的删除操作

按位序删除（带头结点和不带头结点）：

bool ListDelete(Linklist &L , int i, int &data) {
	if (i < 1) {
		return false;
	}

    //不带头结点加下面代码
    //if (i == 1) {
    //LNode* q = L;      // 指向第一个节点
    //data = q->data;     // 保存值
    //L = L->next;        // 头指针指向第二个节点
    //free(q);            // 释放原第一个节点
    //return true;
    //}

	LNode* p = L;
	int j = 0; //当前p指向的是第几个节点
	while (p != NULL && j < i - 1) {  //循环遍历让p指向被删除节点的前一个节点
		p = p->next;
		j++;
	}

	if (p == NULL) {
		return false;
	}

	//删除节点
	LNode *q = p->next;  //另q指向被删除节点
	data = q->data;  //用data返回元素的值
	p->next = q->next;  //断链
	free(q);  //释放q指向的节点
	return true;
}

指定节点删除：

bool DeleteNode(LNode *p) {
	if (p == NULL) {
		return false;
	}
	//删除节点
	LNode* q = p->next;  //另q指向被删除节点
	p->data = p->next->data;  //和后继节点交换数据域
	p->next = q->next;  //断链
	free(q);
	return true;
}

2.3.5 单链表的查找

本小节介绍的都是单链表在有头结点的管理方式下的按位查找和按值查找，代码如下：

//按位查找
LNode* GetElem(Linklist L, int i) {
	if (i < 0) {
		return NULL;
	}

	LNode* p;
	int j = 0;
	p = L;
	while (p != NULL && j < i) {  //头结点不存数据，但是也算下标为0的第一个节点
		p = p->next;
		j++;
	}
	return p;
}

//按值查找
LNode* GetElem(Linklist L, int data) {
	LNode* p;
	p = L->next;
	while (p != NULL && data != p->data) { 
		p = p->next;
	}
	return p;
}

2.3.6 单链表的建立

所谓建立，就是指为空链表添加数据。本小节介绍在单指针管理模式下的带头结点的头插法和尾插法。

头插法： 实现很简单，在头结点的位置调用前面定义的后插操作的函数 bool InsertNextNode(LNode* p, int data) 即可。代码如下：

void HeadInsert(Linklist& L, int data) {
	LNode *p = L;
	InsertNextNode(p, data);
}

尾插法： 同样简单，在前面定义的按位序插入的函数 bool ListInsert(Linklist &L , int i, int data) 中传入的i的值为length+1（要插入的位置）即可。

2.4 双链表

本小节思维导图如下：双链表思维导图

2.4.1 双链表的定义

单链表每个节点仅包含一个指向其后继的指针，故只能从前往后遍历。但若想访问一个链表中一个节点的前驱节点，除了在单链表中从头开始遍历或者双指针遍历外，还可采用双链表的这种数据结构。双链表的每个节点包含两个指针prior和next，分别指向直接前驱和直接后继，其中头结点的prior为NULL，尾节点的next为NULL。其结构示意图如下（带头结点）：

2.4.2 双链表的实现方式

带头结点初始化代码如下：

typedef struct node {
	int data;
	struct node *prior, *next;
}DNode;

typedef DNode* DLinkList;

bool InitDLinkList(DLinkList& L) {
	L = (DNode*)malloc(sizeof(DNode));
	if (L == NULL) {  //内存分配失败
		return false;
	}
	L->prior = NULL;
	L->next = NULL;
	return true;
}

2.4.3 双链表的插入操作

双链表的后插操作：

//在p节点之后插入s节点（尾插法也含括在内）
bool InsertNextNode(DNode* p, DNode* s) {
	if (p == NULL || s == NULL) {
		return false;
	}
	s->next = p->next;
	if (p->next != NULL) {
		p->next->prior = s;
	}
	s->prior = p;
	p->next = s;
	return true;

}

双链表的前插操作： 由于双链表可以轻松的找到给定节点的前驱节点，再对该前驱节点调用InsertNextNode()函数即可实现前插操作。

2.4.4 双链表的删除操作

删除该节点的后继节点：

//删除该节点的后继节点
bool DeleteNextNode(DNode* p) {
	if (p == NULL) {  //p的值不合法
		return false;
	}
	DNode* q = p->next;
	if (q == NULL) {  //p没有后继节点
		return false;
	}
	p->next = q->next;
	if (q->next != NULL) { //p的后继节点不是最后一个节点
		q->next->prior = p;
	}
	free(q);
	return true;
}

删除该节点的前驱节点： 同理，找到前驱节点的前一个节点，调用上述代码即可。

2.4.5 双链表的查找

双链表同单链表一样，不具有随机存取的性质，因此按值查找和按位查找，都只能通过遍历实现，时间复杂度都为O(n)。

//后向遍历
while (p != NULL) {
	//对该节点进行操作的代码
	p = p->next;
}
//前向遍历
while (p != NULL) {
	//对该节点进行操作的代码
	p = p->prior;
}
//跳过头结点前向遍历
while (p->prior != NULL) {
	//对该节点进行操作的代码
	p = p->prior;
}

2.5 循环链表

2.5.1 循环单链表

循环单链表与单链表主要区别在于：表中最后一个节点的指针域next不再指向NULL而是指向头结点。值得注意的是在初始化的时候，头结点的指针不设为NULL，而是指向自己，对应判空操作等也发生变化。初始化代码和结构图示如下：

bool InitDLinkList(DLinkList& L) {
	L = (DNode*)malloc(sizeof(DNode));
	if (L == NULL) {  //内存分配失败
		return false;
	}
	L->next = L;  //指针指向自己
	return true;
}

由于循环单链表是一个环，所以在任何位置进行插入和删除操作都是等价的，因此无需像单链表那样判断是否达到表尾。为了提高效率，循环单链表有时不设置头指针，仅设置尾指针，这样在表头或者表尾插入元素的时间复杂度仅为O(1)，若仅设置头指针，在表尾插入元素需要遍历整个链表，时间复杂度则为O(n)。

2.5.2 循环双链表

基于循环单链表的概念，不难推导出循环双链表。不同之处在于：循环双链表中每个节点还多了一个指向前一个节点的指针域prior（多了一个反向的环）。而双链表与循环双链表的不同之处在于：原先双链表头结点的指针域prior不再为NULL而是指向尾节点，原先双链表尾节点的指针域next不再为NULL而是指向头节点。值得注意的是在初始化的时候，头结点的两个指针同样不设为NULL，而是指向自己，对应判空操作等也发生变化。初始化代码和结构图示如下：

bool InitDLinkList(DLinkList& L) {
	L = (DNode*)malloc(sizeof(DNode));
	if (L == NULL) {  //内存分配失败
		return false;
	}
	L->prior = L; //指针指向自己
	L->next = L;  //指针指向自己
	return true;
}

同样，在进行插入操作时，不需判断是否达到表尾。

2.6 静态链表

静态链表是用数组来模拟线性表的链式存储结构。

静态链表在考研中考察的不多，这里简单介绍一二：静态链表的每个节点都包含两个域即data域和next域，与动态链表不同的是，这里的next域实际上是节点在数组中的相对位置（数组下标），也称游标。类似于顺序表，静态链表也要先分配一块连续的内存空间。静态链表以0号节点作为头结点，以游标为-1的节点作为尾节点，图示如下：

在初始化的时候为了防止内存中原本存在的脏数据，我们可以先将所有的游标都置为一个数（如-2），这样在后续进行插入操作时也方便判断哪些是空节点方便插入。静态链表节点定义和初始化操作代码如下：

#include <stdio.h>
#define MaxSize 10        // 静态链表的最大长度
typedef int ElemType;     // 数据元素类型，可根据需求改为char/结构体等
typedef struct {          // 静态链表结构类型的定义
    ElemType data;        // 存储数据元素
    int next;             // 下一个元素的数组下标，游标置为-2
} SLinkList[MaxSize];     // 这样的定义方式少见，和前面的LNode和LinkList一样，用于区分概念

// 静态链表初始化函数：所有元素的游标next统一置为-2
void InitSLinkList(SLinkList L) {
    for (int i = 0; i < MaxSize; i++) {
        L[i].next = -2;   // 核心：所有游标置为-2
        // 可选：数据域初始化（如置空/0，避免随机值）
        L[i].data = 0;
    }
}

//测试代码
void testSLinkList() {
    SLinkList a;
    // ......后续代码
}

2.7 顺序表和链表的比较

在第一章绪论中介绍过，探讨一个数据结构，一定要先看他的三要素。本小节将从数据结构三要素方面对顺序表和链表进行比较（简答题考察）。

2.7.1 逻辑结构比较

都是线性表，都属于线性结构。

2.7.2 存储结构比较

顺序表优点：支持随机存取、存储密度高。顺序表缺点：大片连续空间分配不方便，改变容量不方便。

链表优点：离散的小空间分配方便，改变容量方便。链表缺点：不可随机存取，存储密度低。

2.7.3 数据的运算比较（创销，增删改查）

创：链表更胜一筹

顺序表： 需要预分配大片连续空间。若分配空间过小，则之后不方便拓展容量；若分配空间过大，则浪费内存资源。静态分配：静态数组 -> 容量不可改变。动态分配：动态数组（malloc、free）容量可改变，但需要移动大量元素，时间代价高。
链表： 只需分配一个头结点（也可以不要头结点，只声明一个头指针），之后方便拓展。

销：

顺序表： 静态分配：将length设置为0即可，系统会自动回收空间（栈区）。动态分配：将首地址指针传给free(),手动回收空间。
链表： 每个节点都需单独free()回收。

增删：链表更胜一筹

顺序表： 插入 / 删除元素要将后续元素都后移/前移，时间复杂度 O(n)，时间开销主要来自移动元素
链表： 插入 / 删除元素只需修改指针即可，时间复杂度 O (n)，时间开销主要来自查找目标元素。
注意： 虽然时间复杂度都是O(n)，但是在实际过程中若若数据元素很大，则顺序表移动的时间代价很高，而查找元素的时间代价更低。所以链表更优。

改查：顺序表更胜一筹

顺序表： 按位查找：O (1) 按值查找：O (n) 若表内元素有序，可在 O (log₂n) 时间内找到（二分查找… ）
链表： 按位查找：O (n) 按值查找：O (n)

顺链比较

附言

本文参考文章：《考研视角下的C语言(下)》http://mrlxl.cn/index.php/2026/01/24/test-9/

文档