数据结构（一）——线性表

1. 顺序表

1.1 顺序表的定义

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

1.2 顺序表的实现

1.2.1 静态分配

静态分配的顺序表存储结构，范围和大小已经事先固定（不可再更改），一旦空间占满，再加入新的数据就会产生溢出，进而导致程序崩溃。

1
2
3
4
5
6
7
8
9
//静态分配的顺序表存储结构
#define Maxsize 10 //设置最大长度
typedef struct {
	//用“静态”数组存放数据元素 
	//ElemType为元素类型代指，可定义为（int等）
	ElemType data[Maxsize]; 
	//顺序表当前长度
	int length; 
}Sqlist;  //顺序表的类型定义

1.2.2 动态分配

动态分配的顺序表存储结构，存储数组的空间是在程序执行过程中通过动态存储分配语句分配的，一旦数据空间占满，就另外开辟一块更大的存储空间，将原表中的元素全部拷贝到新空间，从而达到扩充数组存储空间的目的。

1
2
3
4
5
6
7
8
9
10
11
12
//动态分配的顺序表存储结构
//InitSize为表长度的初始定义，用来开辟表存储空间以及设置表最大容量
//使用方式可参考1.1.2动态存储结构的初始化
#define InitSize 10 
typedef struct {
	//指示动态分配数组的指针
	ElemType* data;
	//顺序表的最大容量
	int Maxsize;
	//顺序表的当前长度
	int length;
}SeqList; //顺序表的类型定义

1.2.3 顺序表的声明

顺序表存储结构建立以后，要在主函数声明一个顺序表变量，顺序表才算建立完成

1
2
3
4
5
6
7
int main(){
	//静态
	SqList L;
	//动态
	SeqList L;
	//二者根据自己的分配建立方式，声明一个即可。
}

1.3 动态存储结构的扩容

动态存储结构的扩容的核心思想就是开辟一个更大的存储空间，将原数据复制进新区域，再释放原存储内存。

需要注意的是，静态分配的顺序存储不可以类比动态存储结构一样扩容。这是因为静态分配的顺序存储是基于静态数组实现的，其大小在声明时就已经确定，并且在程序的整个生命周期（从程序启动到程序结束整个阶段的全过程）内都是固定的，无法改变。

静态如果需要扩容，只能程序员通过更改程序进行扩容（其实就是程序员建了一个存储空间更大的新表）。而动态分配的存储结构如果扩容，可以通过以下程序在程序的生命周期内进行扩容。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//动态存储结构扩容
void IncreaseSize(SeqList &L, int len) {
	//定义新的指针变量指向原存储结构首地址
	ElemType *p = L.data;
	//新分配一个存储空间更大动态存储结构
	L.data = (ElemType*)malloc((L.Maxsize+len) * sizeof(ElemType));
	//通过循环将数据复制到新区域
	for (int i = 0; i < L.length; i++)
	{
		L.data[i] = p[i];
	}
	//顺序表最大长度增加len
	L.Maxsize = L.Maxsize + len;
	//释放原来的内存空间
	free(p)
}

1.4 顺序表的初始化

1.4.1 静态分配存储结构初始化

静态分配初始化简单，只需要将表长设置为0即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//初始化表结构
void Initlist(Sqlist &L) {
//************************************************
//该段对表中数据进行初始化赋值为0。但是这段可以省略。
//如果省略这段，通过全部打印会发现，表中数据值可能会出现内存遗留“脏数据”。（也有可能不出现）
//但是正常情况下，我们不会通过Maxsize来全部打印。而是通过lenght来打印出表中已有的数据。
//所以，此段初始化循环可省略，但L.lenght初始化表长不可省略。
	for (int i = 0; i < Maxsize; i++)
	{
		L.data[i] = 0;
	}
//************************************************
	L.length = 0;
}

1.4.2 动态分配存储结构初始化

动态分配初始化就稍微麻烦点，首先要创建存储分配空间，还要指出存储空间首地址。其次要将表长和最大存储容量初始化。

1
2
3
4
5
6
7
8
9
//注意这里的InitSize，在1.1.2里已经定义，下面程序中两个使用InitSize的地方要保持一致。
void Initlist(Seqlist &L) {
	//用malloc函数申请一片连续的存储空间用来分配
	L.data = (ElemType*)malloc(InitSize * sizeof(ElemType));
	//初始化顺序表长度为0
	L.length = 0;
	//初始存储容量
	L.Maxsize = InitSize;
}

1.4.3 补充–malloc函数和free函数

malloc函数

malloc函数用于在堆上动态分配指定字节数的内存空间。其原型如下：

1
void *malloc(size_t size);

size 参数表示要分配的字节数。

如果分配成功，malloc返回一个指向分配的内存的指针；如果分配失败（例如，由于内存不足），则返回NULL。

使用malloc分配的内存空间在程序运行期间持续存在，直到使用free函数显式释放，或者程序结束。

free函数

free函数用于释放之前通过malloc（或calloc、realloc等）分配的内存空间。其原型如下：

1
void free(void *ptr);

ptr参数是一个指向之前分配的内存的指针。

调用free后，应将指针设置为NULL，以防止悬挂指针（dangling pointer），即指向已经被释放的内存的指针。

使用free释放内存后，这块内存空间就不再属于程序，并且不应再被访问。尝试访问已释放的内存可能导致未定义行为，包括程序崩溃。

1.5 顺序表的插入操作

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//顺序表的插入操作 时间复杂度为O(n)
bool ListInsert(Sqlist& L, int i, ElemType e)
{
	//判断i的范围是否有效
	if (i<1||i>L.length+1)
	{
		return false;
	}
	//判断数据是否溢出
	if (L.length>Maxsize)
	{
		return false;
	}
	//将第i个元素及之后的元素后移
	for ( int j = L.length; j >= i; j--)
	{
		L.data[j] = L.data[j - 1];
	}
	//在i位置放入e
	L.data[i - 1] = e;
	//表长加1
	L.length++;
	return true;
}

1.6 顺序表的删除操作

顺序表的删除操作即将表L中第i(1<=i<=L.length)个位置的元素，用引用变量e返回。若i的输入不合法，则返回false；否则，将被删元素赋给引用变量e，并将第i+1个元素及其后的所有元素依次往前移动一个位置，返回true。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//顺序表的删除操作 时间复杂度O(n)
bool ListDelete(Sqlist& L, int i, ElemType& e)
{
    //判断i的范围是否有效
	if (i<1||i>L.length)
	{
		return false;
	}
    //将被删除的元素赋值给e
	e = L.data[i - 1];
    //将第i个位置后的元素前移
	for (int j = i; j < L.length; j++)
	{
		L.data[j-1] = L.data[j];
	}
    //表长减1
	L.length--;
	return true;
}

1.7 顺序表的查找

1.7.1 按值查找

顺序表的按值查找就是在顺序表L中找第一个元素值等于e的元素，并返回其位序（注意位序是逻辑结构上的位置排序，而非物理结构）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//顺序表的按值查找操作，时间复杂度O(n)
int LocateElem(Sqlist L, ElemType e)
{
	int i;
	//查找元素e的下标
	for ( i = 0; i < L.length; i++)
	{
		if (L.data[i]==e)
		{
			return i+1;//下标为i的元素值等于e，返回其位序i+1
		}
	}
	return 0;//退出循环依旧未找到，返回false，说明查找失败
}

1.7.2 按位查找

顺序表的按位查找就是在顺序表L中直接查找指定位置的元素值，并将其返回出来。

1
2
3
4
5
//由于顺序表具有随机访问的优点，所以可以根据位序直接查找元素，时间复杂度为O(1)
ElemType GetElem(Sqlist L, int i)
{
	return L.data[i - 1];
}

2. 单链表

2.1 单链表的定义

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

2.2 单链表的实现

单链表结点结构由数据域和指针域组成。数据域可以定义为data，用来存放数据元素；指针域定义为next，用来存放后继结点。

1
2
3
4
5
6
7
8
9
10
11
12
//定义单链表结点类型
typedef struct LNode
{
	//数据域
	ElemType data;
	//指针域
	struct LNode* next;
}LNode, * LinkList;
//注意这里使用typedef将LNode类型重名为LNode和其指针类型的LinkList
//原理上LNode*等价于LinkList，但是仍旧选择这样定义的原因是为了方便程序的可阅读性
//使用LinkList，更突出想表达这是一个单链表
//使用LNode*，则是为了突出表达这是一个结点

2.3 单链表的初始化

单链表有两种写法，一种是带头结点的，一种是不带头结点的。具体区别如下图：

对于单链表，不管带不带头结点，头指针都指向单链表的第一个结点。而带头结点的单链表中，头结点作为第一个结点，往往不存储信息。所有带头结点和不带头结点的单链表的初始化操作是不同的。带头结点的单链表初始化时，需要创建一个头结点，并让头指针指向头结点，头结点的next域初始化为NULL。

1
2
3
4
5
6
7
8
9
//带头结点的单链表的初始化
bool InitList(LinkList& L)
{
	//创建头结点
	L = (LNode*)malloc(sizeof(LNode*));
	//头结点之后暂时还没有元素结点
	L->next = NULL;
	return true;
}

不带头结点的单链表初始化时，只需将头指针L初始化为NULL。

1
2
3
4
5
6
//不带头结点的单链表初始化
bool InitList(LinkList& L)
{
	L = NULL;
	return true;
}

2.4 单链表建立

2.4.1 头插法建立单链表

该方法从一个空表开始，生成新结点，并将读取到的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头，即头结点之后。具体实现过程如下图所示：

数据结构（一）——线性表_头插法建立表.png

算法实现过程如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//头插法建立带头结点的单链表
LinkList List_HeadInsert(LinkList& L)
{
    //创立结点变量，并设置一个输入的数据类型
	LNode* s; int x;
    //创建头结点
	L = (LNode*)malloc(sizeof(LNode));
	//初始为空链表，注意这一句最好加上，如果不加L->next会指向未知的区域，或许会存留脏数据，以后可能会出现bug
    L->next = NULL;
    //输入插入结点的值
	scanf("%d", &x);
    //设置特殊数字，输入9999，则插入结束
	while (x!=9999)
	{
        //创建新结点
		s = (LNode*)malloc(sizeof(LNode));
        // 如果分配内存失败，则处理错误  
        if (s == NULL) {  
            return false;
        }  
		//头插法建立表数据
        s->data = x;
		s->next = L->next;
		L->next = s;
        //输入下一个需要插入结点的数据
		scanf("%d", &x);
	}
	return L;
}

采用头插法建立单链表时，读入数据的顺序与生成的链表中元素的顺序是相反的，可用来实现链表的逆置。每个结点插入的时间为O(1)，设单链表长为n，则总时间复杂度为O(n)。

上述采用头插法建立的单链表是带有头结点的，接下来补充一下不带头结点的头插法建立单链表。不在头结点的单链表在进行头插法时，每次插入新结点后，都需要将它的地址赋值给头指针L。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 头插法建立不带头结点的单链表  
LinkList List_HeadInsert(LinkList& L) {  
    //创立结点变量，并设置一个输入的数据类型
	LNode* s; int x;
    // 初始化链表为空  
    L = NULL;  
    // 输入插入结点的值  
    scanf("%d", &x);  
    // 设置特殊数字，输入9999，则插入结束  
    while (x != 9999) 
    {  
        // 创建新结点  
        s = (LNode*)malloc(sizeof(LNode));  
        // 如果分配内存失败，则处理错误  
        if (s == NULL) {  
            return false;
        }  
        // 头插法建立表数据  
        s->data = x;  
        s->next = L; // 新节点指向当前头节点  
        L = s; // 更新头节点为新节点  
        // 输入下一个需要插入结点的数据  
        scanf("%d", &x);  
    }  
    return L;  
}

2.4.2 采用尾插法建立单链表

头插法建立单链表生成的链表中结点的次序和输入数据的顺序不一致。若希望两者次序一致，则可采用尾插法。该方法将新结点插入到当前链表的表尾，为此必须增加一个尾指针r（设置了尾指针r，其时间复杂度就和头插法相同。否则，每次插入都需要遍历查找到最后一个结点进行插入，时间复杂度达到O(n2)），使其始终指向当前链表的尾节点。具体过程如图所示：

数据结构（一）——线性表_尾插法建立表.png

算法实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//尾插法建立带头结点的单链表
LinkList List_TailInsert(LinkList& L)
{
    //设置插入结点的数据类型
	int x;
    //创建头结点
	L = (LNode*)malloc(sizeof(LNode));
	//定义一个结点变量S，以及尾指针r
    LNode* s, * r = L;
    //输入结点的值
	scanf("%d", &x);
	//输入特定数值9999表示结束
    while (x != 9999)
	{
        //开辟插入结点
		s = (LNode*)malloc(sizeof(LNode));
        if (s == NULL)
        {  
            // 如果分配内存失败，则处理错误  
            return false；
        }  
		//尾插法建立表
        s->data = x;
		r->next = s;
		r = s; //r指向新的表尾结点
        //输入新的插入数据
		scanf("%d", &x);
	}
    //尾结点指针置空
	r->next = NULL;
	return L;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 尾插法建立不带头结点的单链表  
LinkList List_TailInsert(LinkList& L) {  
    // 设置插入结点的数据类型  
    int x;  
    // 初始化链表为空  
    L = NULL;  
    // 定义一个尾指针r，初始时指向NULL  
    LNode* r = NULL;  
    // 输入结点的值  
    scanf("%d", &x);  
    // 输入特定数值9999表示结束  
    while (x != 9999) {  
        // 开辟插入结点  
        LNode* s = (LNode*)malloc(sizeof(LNode));  
        if (s == NULL)
        {  
            // 如果分配内存失败，则处理错误  
            return false；
        }  
        // 尾插法建立表  
        s->data = x;  
        s->next = NULL; // 新节点的next初始化为NULL  
        // 如果链表为空，新节点就是头节点  
        if (L == NULL) 
        {  
            L = s;  
        } 
        else 
        {  
            // 否则，将新节点插入到当前尾节点的后面  
            r->next = s;  
        }  
        // 更新尾指针  
        r = s;  
        // 输入新的插入数据  
        scanf("%d", &x);  
    }  
    return L;  
}

2.5 单链表的查找

2.5.1 按序号查找结点

从单链表的第一个结点开始，沿着next域从前往后依次搜索，直到找到第i个结点为止，则返回该结点的指针；若i小于单链表的表长，则返回NULL。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//按序号查找带头结点的单链表 时间复杂度O(n)
LNode* GetElem(LinkList L, int i)
{
	if (i<0)
	{
		return NULL;
	}
	//指针P指向当前扫描到的结点
	LNode* p;
	//当前P指向的是第几个结点
	int j = 0;
	//让p从头结点开始查找
	p = L;
	while (p!= NULL && j < i)
	{
		p = p->next;
		j++;
	}
    //找到后返回该结点指针，否则返回NULL
	return p;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 按序号查找不带头结点的单链表，时间复杂度O(n)  
LNode* GetElem(LinkList L, int i) {  
    if (i < 1 || L == NULL) 
    {  
        // 如果序号小于1或链表为空，则返回NULL  
        return NULL;  
    }  
    // 指针p指向当前扫描到的结点  
    LNode* p = L;  
    // 当前p指向的是第几个结点（从1开始计数）  
    int j = 1;  
    // 让p从第一个数据节点开始查找  
    while (p != NULL && j < i) {  
        p = p->next;  
        j++;  
    }  
    // 如果找到了第i个节点，返回它；否则返回NULL  
    if (j == i) {  
        return p;  
    } 
    else 
    {  
        return NULL;  
    }  
}

2.5.2 按值查找表结点

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

1
2
3
4
5
6
7
8
9
10
11
12
//按值查找带表头的表结点 时间复杂度为O(n)
LNode* LocateElem(LinkList L, ElemType e)
{
	LNode* p = L->next;
	//从第一个结点开始查找数据域为e的结点
	while (p!= NULL && p->data!= e)
	{
		p = p->next;
	}
	//找到后返回该结点指针，否则返回NULL
	return p;
}
1
2
3
4
5
6
7
8
9
10
11
// 按值查找不带头结点的单链表 时间复杂度为O(n)  
LNode* LocateElem(LinkList L, ElemType e) {  
    LNode* p = L; // 不带头结点，直接从第一个数据节点开始  
    // 从第一个数据节点开始查找数据域为e的结点  
    while (p != NULL && p->data != e)
    {  
        p = p->next;  
    }  
    // 找到后返回该结点指针，否则返回NULL  
    return p;  
}

2.6 插入结点操作

插入结点操作将值为x的新结点插入到单链表的第i个位置。先检查插入操作位置的合法性，然后找到待插入位置的前驱，即第i-1个结点，再在其后插入。操作过程如下图所示：

数据结构（一）——线性表_插入结点操作.png

具体算法如下，首先查找第i-1个结点，假设第i-1个结点为 *p，然后令新结点 *s 的指针域指向 *p 的后继，再令结点 *p的指针域指向新插入的结点 *s。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//带头结点的链表的插入操作 时间复杂度为O(n)
bool ListInsert(LinkList& L, int i, ElemType e)
{
    //指针p指向当前扫描到的结点
	LNode* p = L;
    //记录当前结点的位序
	int j = 0;
    //循环找找到第i-1个结点
	while (p!=NULL && j<i-1)
	{
		p = p->next;
		j++;
	}
    //i值不合法
	if (p==NULL)
	{
		return	false;
	}
	LNode* s = (LNode*)malloc(sizeof(LNode));
    //插入操作
	s->data = e;
    //步骤1和步骤2不能颠换
	s->next = p->next; //图中操作步骤1
	p->next = s;       //图中操作步骤2
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 不带头结点的链表的插入操作，时间复杂度为O(n)  
bool ListInsert(LinkList& L, int i, ElemType e) {  
    // 检查插入位置是否合法  
    if (i <= 0) {  
        return false; // 插入位置不合法  
    }  
    // 创建一个新节点  
    LNode* s = (LNode*)malloc(sizeof(LNode));  
    if (s == NULL) {  
        return false; // 内存分配失败  
    }  
    s->data = e;  
    s->next = NULL;   
    // 指针p指向当前扫描到的节点  
    LNode* p = L;  
    // 记录当前节点的位序（从1开始）  
    int j = 1;  
    // 找到第i-1个节点  
    while (p != NULL && j < i - 1) {  
        p = p->next;  
        j++;  
    }  
    // 如果p为NULL，说明链表长度小于i-1，插入位置不合法  
    if (p == NULL) {  
        free(s); // 释放新节点的内存  
        return false;  
    }  
    // 插入新节点  
    s->next = p->next;  
    p->next = s;  
    return true;  
}

在单链表的插入算法中，通常都采用后插操作。但是除了后插操作还可以采用前插操作，前插操作是指在某结点的前插入一个新结点。但是前插操作需要在传递链表时将表头也传输过来，否则在前插操作就会找不到前驱结点的位置。为了解决这个问题，可以采用伪前驱的方式进行插入操作，即将新结点插入需要进行前插结点的后方，然后将两个结点的数据域与指针域都进行交换，便可实现伪前插操作。代码片段如下(将元素e插入p结点前方)：

1
2
3
4
5
//传入元素e，申请新结点存储元素e
s->next = p->next;
p->next = s; //新结点s连到p之后
s->data = p->data; //将p中元素复制到s中
p->data = e; //p中元素覆盖为e

2.7 删除结点操作

删除结点操作是将单链表的第i个结点删除。先检查删除位置的合法性，然后查找表中第i-1个结点，即被删除结点的前驱，再删除第i个结点。操作过程如下图：

数据结构（一）——线性表_删除结点操作.png

具体算法如下，假设结点 *p 为找到的被删结点的前驱，为实现这一操作后的逻辑关系的变化，仅需修改 *p的指针域，将 *p的指针域next指向 *q的下一结点，然后释放 *q的存储空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
bool ListDelete(LinkList& L, int i, ElemType& e)
{
	if (i < 1)
		return false;
	//指针p指向当前扫描到的结点
    LNode* p;
    //当前p指向的结点
	int j = 0;
    //L指向头结点，头结点是第0个结点(不存数据)
	p = L;
    //循环找到第i-1个结点
	while (p!=NULL &&j<i-1)
	{
		p = p->next;
		j++;
	}
    //i值不合法
	if (p == NULL|| p->next == NULL)
		return false;
    //令q指向被删除结点
	LNode* q = p->next;
	//用e返回元素的值
    e = q->data;
    //将*q结点从链中断开
	p->next = q->next;
    //释放结点存储空间
	free(q);
	return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// 不带头结点的链表的删除操作  
bool ListDelete(LinkList& L, int i, ElemType& e) {  
    // 检查删除位置是否合法  
    if (i < 1 || L == NULL) 
    {  
        return false; // 删除位置不合法或链表为空  
    }   
    LNode* p = L; // 从第一个数据节点开始  
    int j = 1; // 从1开始计数  
    // 找到第i-1个节点  
    while (p != NULL && j < i) 
    {  
        p = p->next;  
        j++;  
    }  
    // 如果链表长度小于i，或p为NULL（即第i个节点不存在），返回false  
    if (p == NULL || p->next == NULL) 
    {  
        return false;  
    }  
    // q指向要删除的节点  
    LNode* q = p->next;  
    // 保存要删除节点的数据  
    e = q->data;  
    // 删除操作：将p的next指向q的next  
    p->next = q->next;  
    // 释放q节点占用的内存  
    free(q);  
    return true;  
}

要删除某个给定结点 *p，通常做法是先从链表头结点开始顺序找到其前驱，然后执行删除操作。除此以外，也可以用删除 *p 的后继来实现，实质就是将其后继的值赋予其自身，然后删除后继。代码片段如下：

1
2
3
4
q=p->next; //令q指向p的后继结点
p->data=p->next->data; //用后继结点的数据域覆盖
p->next=q->next; //将q结点从链中断开
free(q); //释放后继结点的存储空间

3. 双链表

3.1 双链表的实现

双链表示意图：

数据结构（一）——线性表_双链表示意图.png

双链表结点类型描述：

1
2
3
4
5
6
7
//双链表链表结构类型定义
typedef struct DNode {
	//数据域
	ElemType data;
	//前驱和后继指针
	struct DNode* prior, * next;
}DNode,*DLinklist;

3.2 双链表的插入操作

双链表中p所指的结点之后插入结点 *s。过程如下图：

数据结构（一）——线性表_双链表插入结点.png

操作代码片段如下：

1
2
3
4
5
//将结点s插入p之后
s->next = p->next;
p->next->prior = s; 
s->prior = p; 
p->next = s;

3.3 双链表的删除操作

删除双链表中结点 *p的后继 *q。过程如下图：

数据结构（一）——线性表_双链表删除结点.png

删除操作代码片段：

1
2
3
p->next = q->next;  //步骤1
q->next->prior = p; //步骤2
free(q);//释放空间结点

4. 循环链表

4.1 循环单链表

循环单链表和单链表的区别在于，表中最后一个结点的指针不是NULL，而改为指向头结点，从而整个链表形成一个环。在循环单链表中，表位结点 *r的next域指向L，故表中没有指针域为NULL的结点，因此，循环单链表的判空条件是r是否指向L。下图为循环单链表的示意图：

4.2 循环双链表

循环双链表中，多出一个头结点的prior指针还要指向表尾结点。当某结点 *p 为尾结点时，p->next==L；当循环双链表为空表时，其头结点的prior域和next域都等于L。下图为循环双链表的示意图：

数据结构（一）——线性表_循环双链表.png

5. 静态链表

静态链表是用数组来描述线性表的链式存储结构，结点也有数据域data和指针域next，但与链表不同的是，这里的指针是结点在数组中的相对地址（数组下标），又称游标。和顺序表一样，静态链表也要预先分配一块连续的内存空间。

静态链表和单链表对应关系如图（静态链表以next==-1作为其结束标志）：

数据结构（一）——线性表_静态链表.png

静态链表结构类型描述：

1
2
3
4
5
6
7
8
9
//静态链表的最大长度
#define MaxSize 50
//静态链表结构类型定义
typedef struct {
	//存储数据元素
	ElemType data;
	//下一个元素的数组下标
	int next;
}SLinkList[MaxSize];