【数据结构与算法学习】线性表（顺序表、单链表、双向链表、循环链表）

实现语言：C++

1. 线性表相关概念

线性表（Linear List）

是由n(n≥0)个具有相同特性（数据类型）的数据元素（结点）a₁，a₂，...，a_i-1，a_i，a_i+1，...，a_n组成的有限序列。

其中，a₁为线性起点（起始结点），a_n为线性终点（终端结点）。对于每一个数据元素a_i，我们称a_i-1为它的直接前驱，a_i+1为它的直接后继。i（1≤i≤n）为下标，是元素的序号，表示元素在表中的位置；n为数据元素总个数，即表长。当n=0时，称线性表为空表。

线性表的存储结构

在计算机中，线性表有两种基本的存储结构：顺序存储结构和链式存储结构。

2. 顺序存储

线性表的顺序表示又称为顺序存储结构或顺序映像。顺序存储，即把逻辑上相邻的数据元素存储在物理上相邻的存储单元中。其特点是依次存储，地址连续——中间没有空出存储单元，且任一元素可随机存取。

线性表的第一个数据元素a₁的存储位置，称为线性表的起始位置或基地址。

顺序表中元素存储位置的计算

　　LOC(a_i） = LOC(a₁) + (i-1) x m  （m为每个元素占用的存储单元）

每个元素的存取时间复杂度为O(1)，我们称之为随机存取。

顺序表的表示

#define LIST_INIT_SIZE 100  // 线性表存储空间的初始分配量
typedef struct{
    ElemType elem[LIST_INIT_SIZE];
    int length;  // 当前长度
}SqList;

例如：多项式 P_n(x) = p₁x^e₁ + p₂x^e₂ + ... + p_mx^e_m 的顺序存储结构类型定义如下：

#include <stdlib.h>
#define MAXSIZE 1000    // 多项式可能达到的最大长度

typedef struct {        // 多项式非零项的定义
    float p;            // 系数
    int e;              // 指数 
}Polynomial;

typedef struct {
    Polynomial* data;   // 存储空间的基地址
    int length;         // 多项式中当前项的个数  
}SqList;                // 多项式的顺序存储结构类型定义为SqList   

int main(int argc, char** argv) {
    SqList L;
    // 开辟指定长度的地址空间，并返回这段空间的首地址
    L.data = (Polynomial*)malloc(sizeof(Polynomial) * MAXSIZE);
    // 释放申请的内存空间
    free(L.data);

    SqList L2;
    // 动态申请存放Polynomial类型对象的内存空间，成功则返回Polynomial类型的指针，指向新分配的内存
    L2.data = new Polynomial();
    // 释放指针L2.data所指向的内存
    delete L2.data;

    return 0;
}

2.1 顺序表基础操作

// 初始化顺序表（构造一个空的顺序表）
Status InitList_Sq(SqList& L) {
    L.elem = new ElemType[MAXSIZE]; // 为顺序表分配存储空间
    if (!L.elem) exit(OVERFLOW);    // 存储分配失败
    L.length = 0;                   // 空表长度为0
    return OK;
}

// 销毁顺序表
void DestroyList(SqList& L) {
    if(L.elem) delete L.elem;   // 释放存储空间
}

// 清空线性表
void ClearList(SqList& L) {
    L.length = 0;   // 将顺序表的长度置0
}

// 求线性表的长度
int GetLength(SqList L) {
    return (L.length);
}

// 判断顺序表L是否为空
int IsEmpty(SqList L) {
    if (L.length == 0) return 1;
    else return 0;
}

// 顺序表的取值（根据位置i获取相应位置数据元素的内容）
int GetElem(SqList L, int i, ElemType& e) {
    if (i<1 || i>L.length) return 0;
    e = L.elem[i - 1];  // 第i-1个单元存储着第i个数据
    return 1;
}

顺序表初始化、销毁顺序表、清空顺序表、求顺序表长度、判断顺序表是否为空及顺序表的取值等操作，它们的时间复杂度都为O(1)

2.2 顺序表的查找

// 顺序表的查找
int LocateElem(SqList L, ElemType e) {
    for (int i = 0; i < L.length; i++) {
        if (L.elem[i] == e)
            return i + 1;
    }
    return 0;
}

平均查找长度ASL（Average Search Length）：为确定记录在表中的位置，需要与给定值进行比较的关键字的个数的期望值叫做查找算法的平均查找长度。

含有n个记录的表，查找成功时：

　　ASL = 1/n * (1+2+...+n) = (n+1)/2

所以，顺序表查找算法的平均时间复杂度为：O(n)

2.3 顺序表的插入

【算法思路】

1. 判断插入位置i是否合法；
2. 判断顺序表的存储空间是否已满，若已满返回ERROR；
3. 将第n至第i位的元素依次向后移动一个位置，空出第i个位置；
4. 将要插入的新元素e放入第i个位置；
5. 表长加1，插入成功返回OK。

【代码】

// 顺序表的插入（在顺序表L的第i个位置插入元素e）
int ListInsert(SqList& L, int i, ElemType e) {
    L.length += 1;
    if (i <= 0 || i > L.length + 1) return 0;   // 判断i值是否合法
    if (L.length == MAXSIZE) return 0;          // 判断当前存储空间是否已满
    for (int k = L.length - 1; k >= i - 1; k--)
        L.elem[k + 1] = L.elem[k];              // 插入位置及之后的元素后移
    L.elem[i-1] = e;
    L.length ++;
    return 1;
}

【算法分析】

　　算法时间主要耗费在移动元素的操作上。

　　若插入在尾结点之后，则需要移动0次；若插入在首结点之前，则需要移动n次；在各个位置插入（共n+1种可能）的平均移动次数为：E = 1/(n+1) * (0+1+...+n) = n/2

　　所以，顺序表插入算法的平均时间复杂度为：O(n)

2.4 顺序表的删除

【算法思路】

1. 判断删除位置i是否合法；
2. 将第i+1至第n位的元素依次向前移动一个位置；
3. 表长减1，删除成功返回OK。

【代码】

// 顺序表的删除（删除顺序表L第i个位置的元素e）
int ListDelete(SqList& L, int i, ElemType& e) {
    if (i < 1 || i > L.length) return 0;    // 判断i值是否合法(1<=i<=L.length)
    for (int k = i; k < L.length - 1; k++)
        L.elem[k - 1] = L.elem[k];          // 被删除之后的元素前移
    L.length--;
    return 1;
}

【算法分析】

　　算法时间主要耗费在移动元素的操作上。

　　若删除尾结点，则需要移动0次；若删除首结点，则需要移动n-1次；在各个位置删除（共n种可能）的平均移动次数为：E = 1/n * (0+1+...+n-1) = (n-1)/2

　　所以，顺序表删除算法的平均时间复杂度为：O(n)

　　由于没有占用辅助空间，顺序表所有操作的空间复杂度都为：O(1)

2.5 顺序表的优缺点

优点：

1. 存储密度大（结点本身所占存储量 / 结点结构所占存储量 = 1）；
2. 可以随机存取表中任一元素。

缺点：

1. 在插入、删除某一元素时，需要移动大量元素；
2. 浪费存储空间；
3. 属于静态存储形式，数据元素的个数不能*扩充。

3. 链式存储

链式存储结构又称为非顺序映像或链式映像。其特点是：

1. 结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。
2. 访问时只能通过头指针进入链表，并通过每个结点的指针域依次向后顺序扫描其余结点，所以寻找第一个结点和最后一个结点所花费的时间不等。这种存取元素的方法被称为顺序存取法。

链式存储相关术语：

• 结点：数据元素的存储映像。由数据域和指针域两部分组成。
• 链表：n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。
• 单链表：结点只有一个指针域的链表，结点包括当前元素的数据和其后继元素的地址。
• 双链表：结点有两个指针域的链表，结点当前元素的数据、其前驱元素的地址以及其后继元素的地址。
• 循环链表：首尾相接的链表。
• 头指针：指向链表中第一个结点的指针。
• 首元结点：链表中存储第一个数据元素a₁的结点。
• 头结点：在链表的首元结点之前附设的一个结点。
• 空表：链表中无元素，称为空链表（头指针和头结点仍然在）。

Q1：如何表示空表？

1. 无头结点时，头指针为空时表示空表。
2. 有头结点时，当头结点的指针域为空时表示空表。

Q2：在链表中附设头结点有什么好处？

1. 便于首元结点的处理：首元结点的地址保存在头结点的指针域中，所以在链表的第一个位置上的操作和其他位置一致，无需进行特殊处理。
2. 便于空表和非空表的统一处理：无论链表是否为空，头指针都是指向头结点的非空指针，因此空表和非空表的处理也就统一了。

Q3：头结点的数据域内装的是什么？

　　头结点的数据域可以为空，也可以存放线性表长度等附加信息，但此结点不能计入链表长度值。

3.1 单链表

单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。若头指针名为L，则把链表称为表L。

单链表的存储结构

typedef char ElemType;
typedef struct Lnode {		// 声明结点的数据类型和指向结点的指针类型
	ElemType data;			// 结点的数据域
	struct Lnode* next;		// 结点的指针域
}Lnode, *LinkList;			// LinkList为指向结构体Lnode的指针类型

定义链表和节点指针可以用 LinkList L; 或LNode* L;

这两种方式等价，但为了表述清晰，一般建议使用LinkList定义链表，Lnode定义结点指针。即：

定义链表：LinkList L;

定义节点指针：Lnode* p;

3.1.1 单链表的初始化（带头结点）

即构造一个如图的空表：

【算法思路】

1. 生成新结点作头结点，用头指针L指向头结点；
2. 将头结点的指针域置空。

【代码】

// 单链表的初始化（带头结点）
int InitList(LinkList& L) {
	L = new LNode;  // 或L = (LinkList)malloc(sizeof(LNode));
	L->next= NULL;
	return 1;	
}

3.1.2 判断单链表是否为空

【算法思路】

　　判断头结点指针域是否为空。

【代码】

int ListEmpty(LinkList L) {
	if (L->next)
		return 0;
	else
		return 1;
}

3.1.3 单链表的销毁

【算法思路】

　　从头指针开始，依次释放所有节点。

【代码】

// 单链表的销毁
int DestroyList_L(LinkList& L) {
	Lnode* p;
	while (L) {
		p = L;
		L = (LinkList)L->next;
		delete p;
	}
	return 1;
}

3.1.4 清空单链表

【算法思路】

　　从首元结点开始，依次释放所有结点，并将头结点指针域设置为空。

【代码】

// 清空单链表
int ClearList(LinkList& L) {
	Lnode *p, *q;
	p = (Lnode*)L->next;
	while (L) {
		q = (Lnode*)p->next;
		delete p;
		p = q;
	}
	L->next = nullptr;
}　

3.1.5 求单链表的表长

【算法思路】

　　从首元结点开始，依次计数所有结点。

【代码】

// 求单链表的表长
int ListLength(LinkList L) {
	Lnode* p;
	int len;
	p = (Lnode*)L->next;	// p指向第一个结点（首元结点）
	while (p) {
		len++;
		p = (Lnode*)p->next;
	}
	return len;
}

3.1.6 取值

【算法思路】

　　从链表的头指针出发，顺着链域next逐个结点往下搜索，直至搜索到第i个结点位置。我们称之为顺序存取。

【代码】

// 取值：取单链表中第i个元素的内容,通过变量e返回
int GetElem(LinkList L, int i, ElemType& e)
{
	Lnode* p;
	p = (Lnode*)L->next;
	int j = 1;
	while (p && j < i) {	// 向后扫描，直到p指向第i个元素或p为空
		p = (Lnode*)p->next;
		j++;
	}
	// 第i个元素不存在，分三种情况：i<1，i超过表长，L为空表）
	if (!p || i < 1) return 0;
	e = p->data;
	return 1;
}

3.1.7 查找

【算法思路】

1. 从第一个结点起，依次与待查找数据e相比较；
2. 如果找到一个其值与e相等的数据元素，则返回其在链表中的位置或地址；
3. 如果查遍整个链表都没有找到其值和e相等的元素，则返回0或NULL。

【代码】

// 按值查找—根据指定数据获取该数据所在的位置（地址）
Lnode* LocateElemAddress(LinkList L, ElemType e) {
	Lnode* p = (Lnode*)L->next;
	while (p && p->data != e)
		p = (Lnode*)p->next;
	// if (!p) return nullptr;  // 空表或未查找到返回NULL
	return p;
}

// 按值查找—根据指定数据获取该数据的位置序号
int LocateElemIndex(LinkList L, ElemType e) {
	Lnode* p = (Lnode*)L->next;
	int j = 1;
	while (p && p->data != e) {
		p = (Lnode*)p->next;
		j++;
	}	
	if (!p) return 0;	// 空表或未查找到返回0
	return j;
}

【算法分析】

　　因线性链表只能顺序存取，即在查找时要从头指针找起，因此查找的时间复杂度为：O(n)

3.1.8 插入新结点

【算法思路】

1. 首先找到a_i-1的存储位置p；
2. 生成一个数据域为e的新结点s；
3. 插入新结点：首先新结点的指针域指向结点a_i，然后结点a_i-1的指针域指向新结点。

【代码】

// 在单链表L中第i个元素之前插入数据元素e
int ListInsert(LinkList& L, int i, ElemType e) {
	// 先找到第i-1个元素的位置
	Lnode* p = L;
	int j = 0;
	while (p && j < i - 1) {
		p = (Lnode*)p->next;
		j++;
	}
	if (!p || i < 1) return 0;	// i<1或i超过表长+1，插入位置非法
	
	// 将结点s插入L中
	LinkList s = new Lnode;		// 生成新结点s
	s->data = e;				// 结点s的数据域置为e
	s->next = p->next;			// 新结点s指针域指向第i个结点
	p->next = s;				// 第i-1个结点的指针域指向新结点s
	return 1;
}

【算法分析】

　　在编译 p->next = s 这句代码是会报异常：“不能将Lnode*类型的值分配到Lnode类型的实体”。

　　因线性链表不需要移动元素，只要修改指针，一般情况下插入操作的时间复杂度为：O(1)。但是，如果要在单链表中进行前插操作，由于要从头查找前驱结点，其时间复杂度为：O(n)。

3.1.9 删除结点

【算法思路】

1. 首先找到a_i-1的存储位置p，保存要删除的a_i的值（如果有必要）；
2. p的指针域指向结点a_i+1；
3. 释放结点a_i的空间。

【代码】

// 删除单链表L中第i个数据元素（结点）
int ListDelete(LinkList& L, int i, ElemType& e) {
	// 先找到第i-1个元素的位置
	Lnode* p = L;
	int j = 0;
	while (p && j < i - 1) {
		p = (Lnode*)p->next;
		j++;
	}
	if (!p || i < 1) return 0;	// i<1或i超过表长，删除位置非法

	// 删除第i个结点
	Lnode* q = (Lnode*)p->next;	// 临时保存被删结点的地址以备释放
	p->next = q->next;			// 改变删除结点前驱结点的指针域
	e = q->data;				// 保存删除结点的数据域
	delete q;					// 释放删除结点的空间
	return 1;
}

【算法分析】

　　其时间复杂度和插入操作一致。

3.1.10 建立单链表

（1）头插法——元素插入在链表头部，也叫前插法。

【算法思路】

1. 从一个空表开始，重复读入数据；
2. 生成新结点，将读入数据存放到新结点的数据域中；
3. 从最后一个结点开始，依次将各结点插入到链表的前端。

【代码】

// 建立单链表：头插法
void CreateList(LinkList& L, int n) {
	L = new Lnode;
	L->next = nullptr;

	for (int i = n; i > 0; i--) {
		Lnode* p = new Lnode;	// 输入新结点 p = (Lnode*)malloc(sizeof(Lnode));
		std::cin >> p->data;	// 输入元素值 scanf(&p->data);
			
		p ->next = L->next;		// 插入到表头
		L->next = p;			// 不能将Lnode*类型的值分配到Lnode类型的实体
	}
}

（2）尾插法——元素插入在链表尾部，也叫后插法。

【算法思路】

1. 从一个空表L开始，将新结点逐个插入到链表尾部，尾指针r指向链表的尾结点；
2. 初始时，r和L都指向头结点。每读入一个数据元素则申请一个新结点，将新结点插入到尾结点后，r指向新结点。

【代码】

// 建立单链表：尾插法
void CreateList_R(LinkList& L, int n) {
	L = new Lnode;
	L->next = nullptr;
	Lnode* r = L;	// 尾指针r指向头结点

	for (int i = 0; i < n; i++) {
		Lnode* p = new Lnode;	// 输入新结点
		std::cin >> p->data;	// 输入元素值
		p->next = nullptr;		// 指针域置空

		r->next = p;			// 插入到表尾
		r = p;					// r指向新的尾结点
	}
}

【算法分析】

 　　建立单链表时间复杂度为：O(n)

3.2 双向链表

双向链表：在单链表的每个结点里再增加一个指向其直接前驱的指针域prior，这样链中就形成了两个方向不同的链，故称为双向链表。

双向循环链表：让头结点的前驱指针指向链表的最后一个结点；让最后一个节点的后继指针指向头结点。

双向链表的结构定义

// 双向链表结点结构定义
typedef struct DuLnode {
	ElemType data;
	struct DuLnode* prior, * next;
}DuLnode, *DuLinkList;　

双向链表结构具有对称性（设指针p指向某一结点）：

　　p -> prior -> next = p = p ->next -> prior

在双向链表中有些操作（求表长、取值等），因仅涉及一个方向的指针，所以他们的算法与线性链表相同。但在插入、删除时，则需要同时修改两个方向上的指针，两者的时间复杂度都为O(n)。

3.2.1 双向链表的插入

【算法思路】 

【代码】

// 双向链表的插入
int ListInsert_Dbl(DblLinkList& L, int i, ElemType e) {
	// 先找到第i个元素的位置
	DblLnode* p = L->next;
	int j = 1;
	while (p != L && j < i) {
		p = (DblLnode*)p->next;
		j++;
	}
	if (p == L || i < 1) return 0;	// i<1或i超过表长+1，插入位置非法

	// 插入新结点
	DblLnode* s = new DblLnode;
	s->data = e;
	s->prior = p->prior;	// ①
	p->prior->next = s;		// ②
	s->next = p;			// ③
	p->prior = s;			// ④
	return 1;
}

3.2.2 双向链表的删除

【算法思路】

【代码】

// 双向链表删除结点
int ListDelete_Dbl(DblLinkList& L, int i, ElemType e) {
	// 先找到第i个元素的位置
	DblLnode* p = L->next;
	int j = 1;
	while (p!=L && j < i) {
		p = (DblLnode*)p->next;
		j++;
	}
	if (p==L || i < 1) return 0;	// i<1或i超过表长，删除位置非法

	// 删除新结点
	p->prior->next = p->next;	// ①
	p->next->prior = p->prior;	// ②
	return 1;
}

3.3 循环链表

 循环链表是一种头尾相接的链表，表中最后一个结点的指针域指向头结点，整个链表形成一个环。

优点：从表中任一结点出发均可找到表中其他结点。

示例：带尾指针循环链表的合并（将Tb合并在Ta之后）

【算法思路】

【代码】

// 带尾指针循环链表的合并
LinkList Connect(LinkList Ta, LinkList Tb) {
	Lnode* p;
	p = (Lnode*)Ta->next;			// p存表头结点
	Ta->next = Tb->next->next;		// Tb表头连接到Ta表尾
	delete Tb->next;				// 释放Tb表头结点
	Tb->next = p;					// Tb表尾指向Ta头结点
	return Tb;
}　

3.4 单链表、双向链表和循环链表的时间效率比较

4. 顺序表和链表的比较

存储密度定义：

　　存储密度 = 结点数据本身占用的空间 / 结点占用的空间总量

比如单链表某个节点p，其数据域占8个字节，指针域占4个字节，其存储密度 = 8/12 = 67%。

5. 线性表的应用

5.1 有序表的合并

已知线性表La和Lb中的数据元素按值非递减有序排列，现要求将La和Lb归并为一个新的线性表Lc，且Lc中的数据元素仍按值非递减有序排列。

例如：La=(1,7,8)  Lb=(2,4,6,8,10,11)  →  Lc=(1,2,4,6,7,8,8,10,11)

（1）顺序表实现有序表合并

【算法思路】

1.  创建一个空表Lc；
2. 依次从La和Lb中“摘取”元素值较小的结点插入到Lc表的最后，直至其中一个表变为空；
3. 继续将La或Lb其中一个表的剩余结点插入到Lc表的最后。

【代码】

// 有序表合并：用顺序表实现
void MergeList_Sq(SqList La, SqList Lb, SqList& Lc) {
	ElemType* pa = La.elem;
	ElemType* pb = Lb.elem;							// 指针pa和pb的初值分别指向两个表的第一个元素
	Lc.length = La.length + Lb.length;				// 新表长为待合并两表的长度之和
	Lc.elem = new ElemType[Lc.length];				// 为合并后的新表分配一个数组空间
	ElemType* pc = Lc.elem;							// 指针pc指向新表的第一个元素
	ElemType* pa_last = La.elem + La.length - 1;	// 指针pa_last指向La表的最后一个元素
	ElemType* pb_last = Lb.elem + Lb.length - 1;	// 指针pb_last指向Lb表的最后一个元素

	while (pa <= pa_last && pb <= pb_last) {
		if (*pa < *pb) *pc++ = *pa++;				// 依次“摘取”两表中较小的结点加入Lc
		else *pc++ = *pb++;
	}
	while (pa <= pa_last) *pc++ = *pa++;			// Lb表已到达表尾，将La中剩余元素加入Lc
	while (pb <= pb_last) *pc++ = *pb++;			// La表已到达表尾，将Lb中剩余元素加入Lc
}

【算法分析】

　　时间复杂度：O(ListLength(La) + ListLength(Lb))

　　空间复杂度：O(ListLength(La) + ListLength(Lb))

（2）链表实现有序表合并

【算法思路】

【代码】

// 有序表合并：用链表实现
void MergeList_L(LinkList& La, LinkList& Lb, LinkList& Lc) {
	Lnode* pa = (Lnode*)La->next;
	Lnode* pb = (Lnode*)Lb->next;
	Lnode* pc = Lc = La;			// 用La的头结点作为Lc的头结点

	while (pa && pb) {
		if (pa->data <= pb->data) {
			pc->next = pa;
			pc = pa;
			pa = (Lnode*)pa->next;
		}
		else {
			pc->next = pb;
			pc = pb;
			pb = (Lnode*)pb->next;
		}
	}
	pc->next = pa ? pa : pb;		// 插入剩余段
	delete Lb;						// 释放Lb的头结点
}

【算法分析】

　　时间复杂度：O(ListLength(La) + ListLength(Lb))

　　空间复杂度：O(1)

参考资料

1. 数据结构与算法基础（青岛大学王卓）

2. 数据结构和算法C++实现