数据结构 Part 2

线性表

线性表的定义和基本操作

线性表的定义

线性表是具有相同数据类型的 $n(n>=0)$ 个数据元素的有限序列，其中 $n$ 为表长，当 $n=0$ 时线性表是一个空表，若用 $L$ 命名线性表，则其一般表示为：$L=(a_1,a_2,...,a_n)$，其中 $a_1$ 称为表头元素，$a_n$ 称为表尾元素。除了第一个元素之外，每个元素都有且只有一个直接前驱。除了最后一个元素之外，每个元素都有且只有一个直接后继。

线性表的特点如下所示：

• 表中的元素个数有限
• 表中元素具有逻辑上的顺序性，表中元素有其先后次序
• 表中元素都是数据元素，每个元素都是单个元素
• 表中元素的数据类型都相同，这意味着每个元素占据有相同大小的存储空间
• 表中元素具有抽象性，仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容

线性表是一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指存储结构，两者属于不同层面的概念。

线性表的基本操作

• LinkList(&L)：初始化表，构造一个空的线性表
• Length(L)：求表长，返回线性表 $L$ 的长度
• LocateElem(L,e)：按值查找操作，在表 $L$ 中查找具有给定关键字值的元素
• GetElem(L,i)：按位查找操作，获取表 $L$ 中第 $i$ 个位置的元素的值
• ListInsert(&L,i,e)：插入操作，在表 $L$ 中的第 $i$ 个位置插入指定元素 $e$
• ListDelete(&L,i,e)：删除操作，删除表中第 $i$ 个位置的元素，并用 $e$ 返回删除元素的值
• PrintList(L)：输出操作，按前后顺序输出线性表 $L$ 的所有元素值
• Empty(L)：判空操作，若 $L$ 为空表，则返回 true，否则返回 false
• DestoryList(&L)：销毁操作，销毁线性表，并释放线性表 $L$ 所占用的内存空间

线性表的顺序表示

顺序表的定义

线性表的顺序存储又称为顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。第 1 个元素存储在顺序表的起始位置，第 $i$ 个元素的存储位置后面紧接着存储的是第 $i+1$ 个元素，称 $i$ 为元素 $a_i$ 在顺序表中的位序。因此，顺序表的特点是表中元素的逻辑顺序与其存储的物理顺序相同。

在本篇文章中，ElemType 将统一使用 int，特此告知。

静态分配的顺序表存储结构为：

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

在对数组进行静态分配时，因为数组的大小和空间事先已经固定，所以一旦空间占满，再加入新的数据将会产生一处，进而程序出现崩溃。

因此，我们可以采用动态分配数组空间的方式，一旦数据空间占满，就另外开辟一块更大的存储空间，将原表中的元素全部拷贝到新空间，从而达到扩充数组存储空间的目的。动态分配的顺序表存储结构为：

#define InitSize 50
typedef struct 
{
	int *data;
	int MaxSize,length;
}SqList;

对于数组的动态分配，我们有着 c 语言的方式：

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

也有着 c++ 的方式(还是 c++ 方便，小声嘟囔)：

L.data = new int[InitSize]; 

动态分配并非链式存储，它仍是顺序存储结构，物理结构没有发生变化，依然是随机存取方式，只是分配的空间大小可以在运行时确定。

顺序表的优点：

• 可以进行随机访问
• 存储密度高

顺序表的缺点：

• 元素的插入和删除要移动大量的元素，插入操作平均要移动 $n/2$ 个元素，删除操作平均要移动 $(n-1)/2$ 个元素
• 顺序存储分配需要一段连续的存储空间，不够灵活

顺序表操作的实现

初始化

静态分配和动态分配顺序表的初始化操作是不同的，静态分配在声明一个顺序表时，就已经为其分配的存储空间，因此初始化时只需要将顺序表的当前长度设为 0。

静态分配初始化：

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

动态分配初始化：

SqList L;
void InitList(SqList &L)
{
	L.data = new int[InitSize];
	L.length = 0;
	L.MaxSize = InitSize;
}

遍历操作

首先学习一下如何遍历，学完之后，也方便检测一下其他操作是否能够正确实现。无论是静态分配的数组，还是动态分配的数组，都可以使用下面展示的方式进行遍历：

void Print(SqList L)
{
	for(int i = 0;i < L.length;i ++ )cout << L.data[i] << ' ';
}

插入操作

在顺序表的第 $i$ $(1\le i\le L.length+1)$ 个位置插入元素 $e$，若是 $i$ 的输入不合法，则返回 $false$ 表示插入失败。否则，将第 $i$ 个元素及其后的所有元素依次往后移动一个位置，腾出一个空位插入新元素 $e$，顺序表的长度增加 1，插入成功，返回 $true$。

bool InsertElem(SqList &L,int i,int 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$ $(1\le i\le L.length)$ 个位置的元素，并用变量 e 表示，若 i 的输入不合法，则返回 false。否则，将被删除的元素赋值给 e，并用第 i + 1 个元素及其后的所有元素依次往前移动一个位置，返回 true。

bool DeleteElem(SqList &L,int i,int &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;
} 

按值查找

在顺序表 L 中查找第一个元素值等于 e 的元素，并返回其位序：

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

线性表的链式表示

链式存储线性表时，不需要使用地址连续的存储单元，即不要求逻辑上相邻的元素在物理位置上也相邻，因此插入和删除操作不需要移动元素，而只需要修改指针，但同时也会失去顺序表可随机存取的特点。

线性表的链式存储又称为单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素，为了建立数据元素之间的线性关系，对每个链表结点，除了元素自身的信息之外，还需要存放一个指向其后继的指针。

单链表中结点类型的描述如下：

typedef struct Lnode
{
	int data;
	struct Lnode *next;
}Lnode,*LinkList;

利用单链表可以解决顺序表需要大量连续存储单元的缺点，但附加的指针域，也存在浪费存储空间的缺点。由于单链表的元素离散地分布在存储空间中，因此是非随机的存储结构，即不能直接找到表中某个特定的结点。查找特定结点时，需要从表头开始遍历，依次查找。

通常用头指针 $L$ 来标识一个单链表，指出链表的起始地址，头指针为 $NULL$ 时表示为一个空表。此外，为了操作上的方便，在单链表第一个数据结点之前附加一个结点，称为头结点。头结点是数据域可以不设任何信息，但也可以记录表长等信息。单链表带头结点是，头指针 $L$ 指向头结点，单链表不带头结点时，头指针 $L$ 指向第一个数据结点，表尾结点的指针域为 $NULL$。

头指针和头结点之间的关系：不管带不带头结点，头指针都始终指向链表的第一个结点，而头结点是带头结点的链表中的第一个结点，结点内通常不存储信息。引入头结点后可以有着以下优点：

• 由于第一个数据结点的位置被存放在头结点的指针域当中，因此在链表的第一个位置上的操作和在表的其他位置上从操作一致，无需进行特殊处理
• 无论链表是否为空，其头指针都是指向头结点的非空指针，因此空表和非空表也就得到了统一

单链表的基础操作

初始化

带头结点的单链表初始化

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

不带头结点的单链表初始化：

bool InitList(LinkList &L)
{
	L = NULL;
	return true;
}

求表长(带头结点)

从第一个结点开始依次访问表中每个结点，为此需要设置一个计数变量，每访问一个结点，其值加一，直到访问到空结点为止。

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

按序号查找结点

从单链表的第一个结点开始，沿着 $next$ 域从前向后依次搜索，直到找到第 $i$ 个结点为止，返回该结点对应的指针，否则返回 $NULL$。

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

按值查找结点

从单链表的第一个结点开始，从前往后依次比较表中各个结点的数据域，若某结点的 $data$ 域等于给定值 $e$，则返回该结点的指针；若整个单链表中没有这样的结点，则返回 $NULL$。

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

插入结点操作

将值为 $x$ 的新结点插入到单链表的第 $i$ 个位置。先检查插入位置的合法性，然后找到待插入位置的前驱，即第 $i-1$ 个结点，再在其后插入。

bool ListInsert(LinkList &L,int i,int e)
{
	Lnode *p = L;
	int len = 0;
	while(p != NULL && len < i - 1)
	{
		p = p -> next;
		len ++ ;
	}
	if(p == NULL)return false;
	Lnode *s = (Lnode *)malloc(sizeof(Lnode));
	s -> data = e;
	s -> next = p -> next;
	p -> next = s;
	return true;
}

若是对某一已知结点进行前插操作，我们需要找到该结点的前驱，然后再进行插入，时间复杂度为 $O(n)$。我们也可以采用另一种方式实现，设待插入结点为 $\ast s$，将 $\ast s$ 插入到 $\ast p$ 的前面，我们仍然可以将 $\ast s$ 插入到 $\ast p$ 的后面，交换二者的 $data$ 域值就可以：

s -> next = p -> next;
p -> next = s;
int temp = p -> data;
p -> data = s -> data;
s -> data = temp;

删除结点操作

将单链表的第 $i$ 个结点进行删除，先检查删除位置的合法性，然后查找表中第 $i-1$ 个结点，即被删除结点的前驱，再删除第 $i$ 个结点。

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

对于删除结点 $\ast p$ 的操作，我们也可以这样做，直接使用 $\ast p$ 的后继，交换 $\ast p$ 与其后继结点的 $data$ 域值，再将其后继元素删除即可，这样即可实现删除操作时间复杂度为 $O(1)$。

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

头插法建立单链表

从一个空表开始，生成新结点，并将读取到的数据存放到新结点的数据域当中，然后将新结点插入到当前链表的表头，即头结点之后。采用头插法建立单链表时，读入顺序与生成的链表中元素的顺序是相反的，可用来实现单链表的逆置：

LinkList LinkList_HeadInsert(LinkList &L)
{
	L = (Lnode *)malloc(sizeof(Lnode));
	L -> next = NULL;
	int x;
	while(cin >> x,x != -1)// -1 表示输入结束
	{
		Lnode *s = (Lnode *)malloc(sizeof(Lnode));
		s -> data = x;
		s -> next = L -> next;
		L -> next = s; 
	} 
	return L;
}

尾插法建立单链表

若是希望输入顺序与结点的次序一致，则可使用尾插法。尾插法将新结点插入到当前结点的表尾，因此必须新增一个尾指针 $r$，使其能够始终指向当前链表的尾结点。

LinkList List_TailInsert(LinkList &L)
{
	L = (Lnode *)malloc(sizeof(Lnode));
	L -> next = NULL;
	Lnode *r = L;
	int x;
	while(cin >> x,x != -1)// -1 表示输入结束
	{
		Lnode *s = (Lnode *)malloc(sizeof(Lnode));
		s -> data = x;
		r -> next = s;
		r = s;
	} 
	r -> next = NULL;
	return L;
}

双链表基础操作

单链表结点中只有一个指向其后继的指针，使得单链表只能从前往后依次遍历，计算前驱的时间复杂度为 $O(n)$。为了克服这个缺点，引入了双链表的概念。双链表结点中有 $prior$ 和 $next$，分别指向其直接前驱和直接后继。表头结点的 $prior$ 域和尾结点的 $next$ 域都是 $NULL$。

双链表中节点类型的描述如下：

typedef struct Dnode
{
	int data;
	struct Dnode *prior;
	struct Dnode *next;
}Dnode,*DLinklist; 

双链表在单链表结点中增加了一个指向其前驱的指针 $prior$，因此双链表的按值查找和按位查找操作与单链表的相同，但双链表在插入和删除操作的实现上，与单链表有着较大的不同。双链表可以很方便的找到当前结点的前驱，因此插入和删除操作的时间复杂度为 $ O(n)$。

插入

若想要将结点 $\ast s$ 插入到结点 $\ast p$ 之后(结点 $p$ 并非尾结点)，插入操作的代码片如下所示(不唯一)：

s -> next = p -> next;
p -> next -> prior = s;
s -> prior = p;
p -> next = s;

删除

若想要删除双链表中结点 $\ast p$ 的后继结点 $\ast q$，操作代码如下所示：

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

循环链表

循环单链表

循环链表与单链表的区别在于，表中最后一个结点的指针不是 $NULL$，而改为指向头结点，从而整个链表形成一个环。

在循环单链表中，表尾结点 $\ast r$ 的 next 域指向头结点(带头结点时)或第一个数据结点(不带头结点时)，故表中没有指针域为 NULL 的结点。因此，循环单链表的判空条件需根据是否带头结点区分：

• 对于带头结点的循环单链表，判空条件为 L->next == L(头结点的 next 域指向自身，表明链表中无数据结点)。
• 对于不带头结点的循环单链表，判空条件为 L == NULL(头指针为空，表明链表中无任何结点)。当链表中只有一个结点时，条件为 L->next == L(该结点的 next 域指向自身)，此为非空状态的特殊情况，而非判空条件。

在单链表中只能从表头结点开始往后顺序遍历整个链表，而循环链表可以从表中的任意一个结点开始遍历整个链表，有时会对循环单链表设置尾指针而不是头指针，因为这样的话对表头或表尾进行插入元素都仅需要 $O(1)$ 的时间复杂度。

循环双链表

在循环双链表中，头结点的 $prior$ 指针还要指向表尾结点，当某结点 $\ast p$ 为尾结点时，p -> next == L，当循环链表为空表时，其头结点的 $prior$ 域和 $next$ 域都为 $L$。

静态链表

静态链表是用数组来描述线性表的链式存储结构，结点也有数据域 $data$ 和指针与 $next$，与前面所讲的链表中的指针不同的是，这里的指针是结点在数组中的相对位置。和顺序表一样，静态链表也需要预先分配一块连续的内存空间。

静态链表结构类型的描述如下所示：

#define MaxSize 50
typedef struct
{
    int data;
    int next;  // 指针域，存储后继结点的数组下标，-1 表示无后继
}SLinklist[MaxSize]; 

静态链表以 next == -1 作为其结束的标志。静态链表的插入、删除操作与动态链表的相同，只需要修改指针，而不需要移动元素，总体来说，静态链表没有单链表使用起来方便，但在一些不支持指针的高级语言中，这是一种非常巧妙的设计方法。

顺序表和链表的比较

• 存储方式

  • 顺序表可以顺序存取，也可以随机存取
  • 链表只能从表头开始依次顺序存取

• 逻辑结构和物理结构：

  • 采用顺序存储时，逻辑上相邻的元素对应的物理位置也相邻
  • 采用链式存储时，逻辑上相邻的元素，物理位置不一定相邻

• 查找、插入和删除操作：

  • 对于按值查找，顺序表无序时顺序表和链表时间复杂度均为 $O(n)$，顺序表有序时，可以使用二分查找，时间复杂度可以优化为 $O(nlogn)$
  • 对于按序号查找，顺序表的平均时间复杂度为 $O(1)$，链表的平均时间复杂度为 $O(n)$
  • 顺序表的插入和删除平均需要移动半个表长的元素，链表的插入和删除仅需要修改相关节点的指针域即可

• 空间分配：

  • 顺序存储在静态存储分配情况下，一旦存储空间装满就不能扩充，若要再加入新元素，则会出现内存溢出，因此需要预先分配足够大的存储空间：预先分配过大，可能会导致顺序表候补大量元素闲置。预先分配国小，可能会导致溢出。动态存储分配虽然存储空间可以扩充，但需要移动大量元素，导致操作效率降低。且若是内存中没有更大块连续的存储空间，则会导致分配失败
  • 链式存储的结点空间只在需要时申请分配，只要内存有空间就可以分配，操作灵活、高效。此外，由于每个结点都带有指针域，因此存储密度不够大

  在选择存储结构时，要从以下三个方面考虑：

  • 基于存储考虑：难以估计线性表的长度或存储规模时，不宜采用顺序表。链表虽然不用实现估计存储规模，但其存储密度较低(小于 1)
  • 基于运算考虑：若是经常使用按需要访问元素的操作，建议使用顺序表。若是经常进行插入、删除操作，则建议使用链表
  • 基于环境的考虑：顺序表容易实现，链表相对于顺序表不太容易实现

参考自：《2025年王道数据结构考研复习指导》