C/C++【数据结构笔记】(链表)

文章目录

链表
- 不带头单向非循环链表
- - 1.结构及特点
  - 2. SList.h头文件
  - 3.SList.cpp源文件
  - 4.mian函数测试
  - 5.易错点和重点大总结
- 带头双向循环链表（List）：
- - 1.结构及特点
  - 2.List.h头文件
  - 3.List.cpp源文件
  - 4. main函数测试
  - 5.精华和细节

链表

链表是数据结构中重要部分，其存储结构特点是物理存储单元上非连续、非顺序，数据元素由链表中的指针链接次而成。链表的基本单位是结点，结点包括两个部分：存储数据元素的数据域和存储结点地址的指针域。链表有很多种不同的类型：单向或者双向，带头或者不带头，循环或者非循环自由组合等八类链表（2*2*2）。下面为链表种类的物理结构：

1. 单向或者双向：

2. 带头或者不带头（带头指针的链表不需要用到二级指针）：

3. 循环（尾结点指向头结点）或者非循环（尾结点指向NULL）：

但实际中我们主要都用的是两种链表：无头单向非循环和带头双向循环链表如下：

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希、图的邻接表等等。
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，代码实现变简单了。

不带头单向非循环链表 1.结构及特点

不带头单向非循环链表结构：

单向链表由结点（结构体）组成，结构体有数据域和指针域，数据域存储数据，指针域是一个指向结构体类型的指针，起到链接每个结点的作用。

单向链表缺点：找不到前驱，只能从前往后读取信息！要对某个结点操作，必须找到他的前一个结点！所以尾插函数PushBack，尾删函数PopBack，插入元素函数Insert，删除元素函数Erase的时间复杂度都是O(N)。单向不带头非循环链表的主要接口函数有：打印数据，尾插，头插，尾删，头删，查找指定元素，插入元素，删除元素等等。

无头单向非循环链表的结点定义：

（其实只要是单向链表其结点定义均一致，只是不同的操作罢了）

typedef int SLTDataType;
//更改typedef使结构体中Data类型改变（提高数组灵活性和可维护性-平台无关性）
typedef struct SListNode//单向链表的节点
{
	SLTDataType Data;
	SListNode* next;
	//定义一个指向下一个结构体的指针，起串联的作用
	//结构体中不能再次定义结构体（套娃），但可以有指针
}SLTNode;
//为了C中少写struct，在C++中没有必要

无头单向非循环链表主要函数物理结构（代码实现原理）：

删除指定位置元素（代码实现原理）：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lPGA8yNI-1658900429987)(data:image/gif;base64,R0lGODlhAQABAPABAP///wAAACH5BAEKAAAALAAAAAABAAEAAAICRAEAOw==)]

插入元素（代码实现原理）：

以下是标准的单向链表的头文件和源文件（备注有详细解释）单向链的易错点和难点，在本部分结尾处有总结

2. SList.h头文件

#pragma once
#include
using namespace std; 
typedef int SLTDataType;
//更改typedef使结构体中Data类型改变（提高数组灵活性和可维护性-平台无关性）
typedef struct SListNode//单向链表的节点
{
	SLTDataType Data;
	SListNode* next;
	//定义一个指向下一个结构体的指针，起串联的作用
	//结构体中不能再次定义结构体（套娃），但可以有指针
}SLTNode;
//为了C中少写struct，在C++中没有必要

void SListPrint(SLTNode* phead);//打印

//void SListPushBack(SLTNode* phead, SLTDataType x)//传值尾插是标准错误
void SListPushBack(SLTNode** pphead, SLTDataType x);//尾插
//也可以用void SListPushBack(SLTNode*& phead, SLTDataType x)；//最好用

void SListPushFront(SLTNode** pphead,SLTDataType x);//头插
//这里需要改变头指针，所以要传二级指针

void SListPopBack(SLTNode **pphead);//尾删
//如果是只有一个节点需要释放*pphead，要改变头指针，传二级指针

void SListPopFront(SLTNode **pphead);//头删
//需要改变头指针，用二级指针

SLTNode* SListFind(SLTNode* phead,SLTDataType x);//在链表中查找x元素
//不用改变头指针，用一级指针

void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//插入元素
//在pos前面插入x，pos通常是函数查找链表数据返回的地址

void SListErase(SLTNode** pphead, SLTNode* pos);//删除pos位置元素
//pos通常是函数查找链表数据返回的地址

//void SListInsert(SLTNode* phead, int i, SLTDataType x);//插入元素，在i位置前插入x（i是下标）不太规范的写法
//void SListErase(SLTNode* phead,int i);//删除i位置的元素（i是下标）不太规范的写法

3.SList.cpp源文件

（注意想要在链表中存储数据，必须是要一节点的形式存储进去，所以在写链表的时候都会包装一个函数：实现将x包装成结点并返回结点地址的函数，如下第一个函数）

#include"SList.h"
SLTNode* BuySLTNode(SLTDataType x)//构造节点的函数（包装）
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	//首先开辟空间存储数据
	newnode->next = NULL;
	newnode->Data = x;//建立相应的节点
	return newnode;
}

void SListPrint(SLTNode* phead)//打印链表数据
{
	SLTNode* cur = phead;
	//cur是当前位置的英文（见名思意）将头地址给cur，此时cur指向第一个节点
	while (cur != NULL)//当cur==NULL的时，即为最后一个节点，停止打印
	{
		cout << cur->Data << "->";
		cur = cur->next;
		//cur->next为下个节点的首地址，cur=cur->next执行后，cur指向下一个节点的首地址
	}cout << "NULL" << endl;
}

//void SListPushBack(SLTNode* phead, SLTDataType x)//传值尾插标准错
void SListPushBack(SLTNode** pphead, SLTDataType x)	//尾插
//也可以用void SListPushBack(SLTNode*& phead, SLTDataType x)；最好用
{
	SLTNode* newnode = BuySLTNode(x);//调用函数构造节点，返回首地址
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;//tail是尾部的意思
		while (tail->next != NULL)//这里容易写成（tail!=NULL）
		{
			tail = tail->next;
		}//在最后一个节点停止，出循环后tail是最后节点的首地址（尾节点的next==NULL）
		tail->next = newnode;
		//newnode链接在表尾
	}
}

void SListPushFront(SLTNode** pphead, SLTDataType x)//头插,要么传二级指针，要么传指针引用
{
	SLTNode* newnode = BuySLTNode(x);//调用函数构造节点，返回首地址
	newnode->next = *pphead;
	*pphead = newnode;
}

void SListPopBack(SLTNode** pphead)//尾删
{
	//如果链表有没有或者只有一个节点要特别考虑
	if (*pphead == NULL)
	{
		return;
	}
	else if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		//用两个指针找到最后一个节点的前一个节点（双指针的玩法）
		SLTNode* prev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	}
}

void SListPopFront(SLTNode** pphead)//头删
{
	SLTNode* next = (*pphead)->next;
	//释放之前需要保存地址，否则整个链表全部丢失！
	//传地址 
void SListPushBack(SLTNode*& phead, SLTDataType x)；//传引用 
引用很好理解，引用即是别名，别名就是本身。这里解释传地址的方式：传地址由于传是指针的地址，所以用到了二级指针，为了方便理解，如下示图：pphead是指针变量的地址，pphead是pphead地址解引用一次，也就是指针值本身，而pphead里面存放的是结构体的地址，可通过*pphead访问结构体。 
 
需注意，两种函数（传地址方式和传引用方式）的时候传实参也是不同的。 
 尾插：尾插函数在定义的时候需要考虑链表本身一个节点都没有得情况，否则会bug（会看函数体自行体悟）尾删：需要考虑到空链表和指头一个链表的情况，否则会bug（会看函数体自行体悟）此外删除pos位置元素的函数和在pos（节点地址）前插入元素的函数都需要考虑pos是第一个节点的情况。当然这些问题时建立在上文的函数实现上的，不同函数实现注意点不同。最重要实现函数的时候需要考虑到特殊情况是否满足要求———即空链表是否满足？
 
 SLTNode* next = (*pphead)->next;
 *和->都是解引用的意思，优先及相同需要加上括号，否组可能会报错
  
带头双向循环链表（List）： 
1.结构及特点 
带头双向循环链表结构及作用： 
 
*带头双向循环链表：*结构在链表中最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但这个链表设计的是非常完美的，后续代码实现中会发现此结构的优势很多。 
带头双向循环链表概述： 
带头双向循环链表是由结点组成，第一个称为哨兵位的头节点head，（这里简述哨兵位的作用，哨兵位其实是为了方便操作而引入的结点，不存储有效数据，在很多时候,我们处理某个节点需要用到它的前驱节点，比如删除链表的某个节点,对于没有哨兵的单链表，当待删除的节点为链表的第一个节点,，由于没有前驱,需要进行特殊处理.从而代码的复杂性增加.而如有哨兵节点,则第一个节点的处理方式与其他节点相同,可以统一进行处理。）带头双向循环链表后续就是由结点组成，结点中由有效数据成员和两个指向自身类型的结构体指针，两个指针分别叫做结点的前驱和后继，分别指向上一个结点和下一个结点。每个结点都是一前一后链接在链表上的，下面是结点的定义： 
typedef int LTDataType;//提高维护性和平台无关性
struct ListNode
{
	ListNode* next;//后继，指向后一个指针
	ListNode* prev;//前驱，指向前一个结点
	LTDataType Data;//存储有效数据成员
};
 
本部分思路为：先弄清楚带头双向循环链表的实现，接着介绍如何在10分钟内完整实现带头双向循环链表，老规矩！链表的增删查改功能请看头文件和源文件！代码精华会在后面详细解答！ 
2.List.h头文件 
#pragma once
#include
#include
using namespace std;
typedef int LTDataType;//提高维护性和平台无关性
struct ListNode
{
	ListNode* next;//后继，指向后一个指针
	ListNode* prev;//前驱，指向前一个结点
	LTDataType Data;//存储有效数据成员
};
void ListInit(ListNode*& phead);//初始化

void ListPrint(ListNode*phead);//打印链表

void ListDestory(ListNode* phead);//消除数据

void ListPushBack(ListNode* phead, LTDataType x);//尾插

void ListPushFront(ListNode* phead, LTDataType x);//头插

void ListPopBack(ListNode* phead);//尾删

void ListPopFront(ListNode* phead);//头删

ListNode* ListFind(ListNode* phead, LTDataType x);//查找存有x的结点，并返回该节点地址

void ListInsert(ListNode* pos, LTDataType x);
//在pos位置前插入存有x的结点,pos一般是ListFind函数查找返回的地址

void ListErase(ListNode* pos);
//删除pos位置的结点，pos一般是ListFind函数查找返回的地址

bool ListEmpty(ListNode* phead);//判断空
int ListSize(ListNode* phead);//判断大小
 
3.List.cpp源文件 
（注意想要在链表中存储数据，必须是要一节点的形式存储进去，所以在写链表的时候都会包装一个函数：实现将x包装成结点并返回结点地址的函数，如下第一个函数） 
#include"List.h"
ListNode* BuyListNode(LTDataType x) //创造结点功能的函数包装
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	newnode->Data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}

void ListInit(ListNode*& phead)//初始化,改变指针用指针和引用均可，此处用引用
{
	phead = BuyListNode(0);//head哨兵位头节点，不存有效数据
	phead->next = phead;
	phead->prev = phead;
	//head哨兵位指针都是自己指向自己，很完美的设计，后面详解
}

void ListPrint(ListNode* phead)//打印链表
{
	assert(phead);//排除空指针闯传入
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		//当cur=phead时说明刚好遍历一次或者该链表没有数据
		cout << cur->Data << " ";
		cur = cur->next;
	}
	cout << endl;
}

void ListIniDestory(ListNode* phead)//消除数据
{
	assert(phead);//排除空指针闯传入
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}//要每个指针都释放，而不是不负责的只释放phead
	free(phead);
	phead = NULL;
}

void ListPushBack(ListNode* phead, LTDataType x)//尾插
{
	//循环链表中哨兵位的prev指针指向的就是尾结点！
	assert(phead);//排除空指针闯传入
	ListNode* tail = phead->prev;//tail就是尾结点地址
	ListNode* newnode = BuyListNode(x);//将x包装成结点
	//三个结点之间链接！phead newnode tail
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}

void ListPushFront(ListNode* phead, LTDataType x)//头插
{
	assert(phead);//排除空指针闯传入
	ListNode* newnode = BuyListNode(x);//将x包装成结点
	ListNode* first = phead->next;//first就是第一个结点地址
	//三个结点之间链接！phead,first,newnode
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = first;
	first->prev = newnode;
}

void ListPopBack(ListNode* phead)//尾删
{
	assert(phead);//排除空指针闯传入
	assert(phead->next != phead);//只有哨兵位头节点不能删
	ListNode* tail = phead->prev;//tail就是尾结点地址
	ListNode* prev = tail->prev;//prev是倒数第二个结点的地址
	prev->next = phead;
	phead->prev = prev;
	free(tail);
	tail = NULL;//别忘了释放指针并置空
}

void ListPopFront(ListNode* phead)//头删
{
	assert(phead);//排除空指针闯传入
	assert(phead->next != phead);//只有哨兵位头节点不能删
	ListNode* first = phead->next;//first就是第一个结点地址
	ListNode* second = first->next;//second就是第二个结点地址
	phead->next = second;
	second->prev = phead;
	free(first);
	first = NULL;//别忘了释放指针并置空
}

ListNode* ListFind(ListNode* phead, LTDataType x)//查找存x的结点,返回该结点的地址
{   //ListFind函数是可以修改结点有效数据的，对函数返回值解引用"->"可修改特定位置的数值
	assert(phead);//排除空指针闯传入
	ListNode* cur = phead->next;
	while (cur != phead)//cur=phead就遍历一次或者链表为空链表
	{
		if (cur->Data == x)
		{
			return cur;//找到x的结点返回结点地址
		}
		cur = cur->next;
	}return NULL;
}

//在pos位置前插入存有x的结点,pos一般是ListFind函数查找返回的地址
void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);//排除空指针闯传入
	ListNode* prev = pos->prev;
	ListNode* newnode = BuyListNode(x);
	//三个结点之间链接！prev newnode pos
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}

//删除pos位置的结点，pos一般是ListFind函数查找返回的地址
void ListErase(ListNode* pos)
{
	assert(pos);//排除空指针闯传入
	ListNode* prev = pos->prev;
	ListNode* next = pos->next;
	//找到pos的前一个prev，和后一个next，链接next和prev释放free
	prev->next = next;
	next->prev = prev;
	free(pos);
	pos = NULL;
}

bool ListEmpty(ListNode* phead)//判断空 空返回1，非空返回零
{
	assert(phead);
	return phead->next == phead;
}

int ListSize(ListNode* phead)//判断大小
{
	assert(phead);
	int Size = 0;
	ListNode* cur = phead;
	do
	{
		Size++;
		cur = cur->next;
	} while (cur != phead);
	return Size;
}
 
4. main函数测试 
#include"List.h"
void ListTest()
{
	ListNode* A;
	ListInit(A);
	错误写法！
	ListPushBack(A, 1);
	ListPushBack(A, 2);
	ListPushBack(A, 3);//尾插测试
	ListPrint(A);
	ListPushFront(A, -1);
	ListPushFront(A, -2);
	ListPushFront(A, -3);//头插测试
	ListPrint(A);
	ListPopBack(A);//尾删测试
	ListPrint(A);
	ListPopFront(A);//头删测试
	ListPrint(A);
	ListNode* tmp = ListFind(A, 1);//查找元素测试
	ListInsert(tmp,666);//插入元素测试
	ListErase(tmp->next);//删除元素测试
	cout << "List NULL or not ?(NULL:1,not NULL:0) =" << ListEmpty(A) << endl;
	cout << "there is " << ListSize(A) << " nodes in the List" << endl;
}
int main()
{
	ListTest();
}
 
结果： 
5.精华和细节 
一分钟之内完整实现带头双向循环链表：不难发现所谓头删，尾删，头插，尾插其实不过是最后两个再pos位置删除插入函数（ListInsert，ListErase）的特殊形式，所以实现带头双向循环链表的头删，尾删，头插，尾插函数只需要写两个再pos位置删除插入函数（ListInsert，ListErase）的函数其余就行啦！看cpp代码！ 
void ListPushBack(ListNode* phead, LTDataType x)//尾插
{
	assert(phead);//排除空指针闯传入
	ListInsert(phead->prev，x);
}

void ListPushFront(ListNode* phead, LTDataType x)//头插
{
	assert(phead);//排除空指针闯传入
	ListInsert(phead->next,x);
}

void ListPopBack(ListNode* phead)//尾删
{
	assert(phead);//排除空指针闯传入
	ListErase(phead->prev);
}

void ListPopFront(ListNode* phead)//头删
{
	assert(phead);//排除空指针闯传入
	ListErase(phead)一句化搞定上面所有，当然还是要断言以下的
}
 
带头双向循环链表的结构完美性：任意位置都可以删除插入都是O(1),但查找还是O(N)。以后查找会用平衡搜索树（AVL树和红黑树），哈希表，B树，B+树系列，跳表，布隆过滤器，位图等。此外会发现在无头单向非循环链表中，头插尾插头删尾删等函数需要考虑链表的特殊情况，如链表只有一个结点或者空链表的情况都需要单独考虑，但在带头双向循环链表中是不需要考虑的（不信回试），**带头双向循环链表的代码实现满足一般情况也能满足特殊情况！**所以写代码的时候只需要按下面这个结构写： 
 
头插，尾插的代码实现最好的思路是，找到插入的结点newnode和前一个结点prev和后一个结点next，然后再对这三个结点newnode，prev，next进行链接，这样的链接方式不需要考虑链接顺序，思路清晰不会出错。直接插入的方式代码简单一丢丢，需要注意链接顺序，必须先链接后面再链接前面，否则会出现修改了前面的指针找不到后面的指针的情况，以头插为例子： 
//正确写法：
void ListPushFront(ListNode* phead, LTDataType x)//头插
{
	assert(phead);//排除空指针闯传入
	ListNode* newnode = BuyListNode(x);//将x包装成结点
    newnode->next=phead->next;//先把后面链接
	phead->next->prev = newnode;//先把后面链接
	phead->next = newnode;//再链接前面
	newnode->prev = phead;//再链接前面
}

//错误写法：
void ListPushFront(ListNode* phead, LTDataType x)//头插
{
	assert(phead);//排除空指针闯传入
	ListNode* newnode = BuyListNode(x);//将x包装成结点
	phead->next = newnode;//先链接了前面
	newnode->prev = phead;//先链接了前面
    newnode->next=phead->next;//此处出现问题phead->next就是newnode本身！
	phead->next->prev = newnode;//phead->next->prev是phead
     //可以发现已经乱套了！
}
 
哨兵位头节点中的哨兵位的头节点一定不要存有效数据！存了会在某些类型问题上出现问题： 
typedef int LTDataType;
struct ListNode
{
	ListNode* next;
	LTDataType Data;
};
 
不少人希望通过再哨兵位数据中存储数组中元素个数来达到遍历的方便，但在一些情况会出现问题，当这里LTDataType是int类型一般没有问题，但LTDataType是char类型的时候，当数组元素超过128时，再插入数据就会出现溢出现象，此外还有其他情况也可能出现问题，就不在此一一列举了。 
assert断言的好处，未来在大厂工作，代码少则都时万行，assert的好处在于程序出现问题，会告诉你出发了那个断点，当程序代码多时，告诉你错误的位置好处不言而喻，维护性大大提高。

C/C++【数据结构笔记】(链表)

C/C++/C#相关栏目本月热门文章