数据结构初步（五）- 线性表之单链表的分析与C语言实现

发布于：2022-12-22 ⋅ 阅读:(532) ⋅ 点赞:(0)

目录~

前言

上节介绍了顺序表，本节将继续数据结构的学习：介绍链表的有关概念与知识，并着重于分析单链表的具体实现。
本节多组动图预警！！！

链表

顺序表存在着一定的缺陷，所以有了链表尝试去填补顺序表存在的缺陷。

1. 概念

链表是逻辑上连续，物理储存结构上非连续、非顺序的储存结构。
数据元素的逻辑连续是通过额外的指针链接次序实现并保持的。

2. 结构

与顺序表基本单元只储存一个数据不同，链表中的基本单元节点不仅需要储存数据，还要储存下一个基本单元节点的地址。因此这个基本单元至少包括一个储存数据的变量和一个结点指针。
如下：
image.png

2.1 基本逻辑结构：

image.png

2.2 实际物理储存结构

image.png

  1. 实际使用时的节点一般是从堆上申请出来。
  2. 从对上申请的空间是按照一定的策略分配的，两次申请的节点的空间不一定连续。

3. 链表的分类

3.1 单向链表与双向链表

image.png

3.2 不带头节点（哨兵头）与带头结点（哨兵头）的链表

image.png

3.3 循环链表与不循环链表

image.png

无头单向不循环链表：结构简单，一般不会单独用来储存数据。实际中更多的是作为其他数据结构的子结构，如哈希桶等；
带头双向循环链表：结构最复杂，一般用于单独储存数据。实际中使用的链表数据结构，都是带头双向循环链表。这个结构虽然复杂，但是使用代码实现时反而简单，这是优势的结构所带来的便利。

4. 单向链表的功能分析与C语言代码实现

4.1 有关单链表的说明

链表的具体代码实现方式不止一种，包括但不限于有：

方式一：
接口函数接受头指针，通过头指针的副本完成对链表的操作后接口函数返回新的头指针，需要调用者接受函数的返回值以应对可能的头指针的改变。
方式二：
接口函数接受头指针的地址，故接口函数在完成对链表相应操作的同时，如果头指针需要改变也在函数内部通过头指针地址直接完成了对头指针的改变。
方式三：
在一开始就在外部定义一个不储存任何数据的头节点或者叫哨兵头，并让头指针指向这个头节点哨兵头，所以头指针并不直接指向存放有效数据的节点，而是通过头节点哨兵头内部的指针来指向存放有效数据的节点；这样头指针就不需要改变了，改变的是头节点哨兵头内部指针；
这样接口函数接受的是就不需要是头指针的地址了，接受头指针本身就可以了。
哨兵头的引入方便的解决了不使用二级指针是怎样传头指针的问题。

本文主要介绍方式二：对于可能会改变头指针的大部分接口函数接受头指针的地址即使用二级指针，对于不会改变头指针的接口函数我们既可以选择接受头指针的地址二级指针的方式也可以选择不接受头指针的地址一级指针的方式。

4.2 功能分析

1. 防止头文件被重复包含

方法1：条件编译指令

#ifndef __SeqList__
#define __SeqList__
//....
#endif

方法2：在头文件最开始的位置加上一行代码

#pragma once

2. 头文件的包含

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

3. 定义节点结构体类型

节点包括储存数据的变量和指向下一个节点的结构体指针。
同时为了书写方便，把定义的结构体类型再定义一个较短的名字。

typedef int SLTDataType;
typedef struct SListNode {
	SLTDataType data;
	struct SListNode* next;
}SLNode;

结构体内部的储存数据的变量类型是不确定的，为了能够灵活储存不同类型的数据，减少将来写好代码后再修改数据类型的次数，我们定义了一个通用的数据类型的名字，当我们需要储存不同类型的数据时只需要修改一次数据类型即可，也减少了时间的浪费。

4. 数据输出到控制台

//数据输出到控制台
void SListPrint(SLNode* phead) {
	while (phead) {
		printf("%d ", phead->data);
		phead = phead->next;
	}
	printf("\n");
}

因为输出各个节点储存的数据并不需要改变外部链表的头指针phead，所以这里函数参数是结构体类型一级指针SLNode*，是头指针的副本。
链表节点之间通过指针联系起来，单向链表只能从当前节点找到下一个节点而不能从当前节点找到上一个接待你，末尾节点的指针指向NULL。
传入的头指针可能有两种正常情况：

  1. 头指针为NULL，说明链表为空；
  2. 头指针不为NULL，说明链表至少有一个节点。

我们使用while循环遍历每个节点，打印节点储存的数据，然后更新头指针副本phead，使其指向下一个节点，直到头指针副本phead为NULL时说明链表数据已经打印完成。

image.png

5. 申请一个新节点并对其初始化

SLNode* BuyNode(SLTDataType x) {
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	if (!newnode) {
		perror("newnode\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
}

该函数是为了配合增加数据时需要申请新节点的操作。
使用malloc()函数向内存的堆区申请一个新节点，同时创建一个结构体类型的指针newnode接受malloc()返回的值。如果malloc()申请空间成功即返回申请空间的起始地址，如果申请空间失败就返回NULL。所以我们需要对newnode储存的值进行判断：
如果是NULL就借助perror()输出错误信息，然后程序退出；
如果不是NULL说明申请新节点成功，把新增的数据存入新节点中，然后把节点内部的指针初始化NULL。

6. 尾插节点

void SListPushBack(SLNode** pphead, SLTDataType x) {
	assert(pphead);
	SLNode* newnode = BuyNode(x);
    //头节点为NULL
	if (*pphead == NULL) {
		*pphead = newnode;
	}
	else {
        //头节点不为NULL
		SLNode* cur = *pphead;
		while (cur->next) {
			cur = cur->next;
		}
		cur->next = newnode;
	}
}

单链表尾插数据，时间复杂度为 O ( N ) O(N) O(N)
如果单链表空，需要改变外部头指针phead的指向，使其指向新增加的节点newnode。这种情况函数需要得到外部头指针的地址&phead，即二级结构体指针SLNode** pphead；
如果单链表不为空，就不需要改变外部头指针phead的指向，只需要从第一个节点开始向后遍历链表，直到找到尾节点，然后使尾节点内部的指针指向新节点即可。这种情况函数只需要知道外部头指针phead的值副本即可。
综合考虑这个函数参数设置为SLNode** pphead，接受外部头指针的地址。
在尾插函数内部开始具体执行功能之前，需要先对二级指针pphead进行判断，我们知道头指针phead有空和非空两种情况，二级指针pphead存放phead的地址，那么pphead一定是不为空的。为了预防任何原因传入了NULL作为pphead的值，我们对pphead进行断言处理assert(pphead)，当pphead为NULL时程序将在此处报断言错误；只有当pphead不为NULL时，代码才能继续执行。

image.png

我们为了防止对头指针副本的修改，便借助一个结构体指针变量cur进行相应的操作。

image.png
PushBack_1.gif
PushBack_2.gif

7. 头插节点

void SListPushFront(SLNode** pphead, SLTDataType x) {
	assert(pphead);
	SLNode* newnode = BuyNode(x);
	if (*pphead == NULL) {
		*pphead = newnode;
	}
	else {
		newnode->next = *pphead;
		*pphead = newnode;
	}
}

单链表头插数据，时间复杂度为 O ( 1 ) O(1) O(1)
每次头插数据都必须要改变外部头指针phead的指向，使其指向新增加的节点newnode。函数需要得到外部头指针的地址&phead，即二级结构体指针SLNode** pphead。
将这个函数参数设置为SLNode** pphead，接受外部头指针的地址。
对二级指针pphead进行断言处理：

image.png

对于单链表本身是否为空我们需要进行分开考虑：

  1. 如果单链表为空，通过二级指针pphead改变外部头指针的指向（值），使其指向新申请的节点newnode即可；
  2. 如果单链表不为空，则此时单链表至少有一个节点。

先改变新节点newnode内部的指针，使其指向头指针所指向的节点；
再通过二级指针pphead改变外部的头指针，使其指向新节点newnode，头插操作完成。

PushBack_1.gif
PushFront_2.gif

8. 尾删节点

void SListPopBack(SLNode** pphead) {
	assert(pphead);
	//暴力检查
	assert(*pphead);
    //温柔检查
    //if(*pphead == NULL){
    //    return;   
    //}
	if ((*pphead)->next == NULL) {
		free(*pphead);
		*pphead = NULL;
	}
	else {
        //法1
		SLNode* prev = NULL;
		SLNode* tail = *pphead;
		while (tail->next) {
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		//tail = NULL;
		prev->next = NULL;
        
		法2
		//SLNode* cur = *pphead;
		//while (cur->next->next) {
		//	cur = cur->next;
		//}
		//free(cur->next);
		//cur->next = NULL;
	}
}

单链表尾删数据，时间复杂度为 O ( N ) O(N) O(N)

尾删分为三种情况：

  1. 链表为空，一个节点也没有。这时外部头指针phead指向NULL，不能对链表进行删除节点操作。接口函数函数可以不进行操作而直接返回；也可以对头指针为NULL进行断言assert()，只有当头指针phead不为NULL时才继续删除操作。
  1. 链表中只有一个节点，这个节点是头节点也是尾节点tail，删除之后链表为空，及时释放free被删除节点空间，外部头指针phead此时需要改变指向（值），需要使其指向NULL；所以此情况我们需要二级结构体指针pphead接受外部头指针phead的地址。

对二级指针pphead进行断言处理：

image.png
PopBack_2.gif

  1. 链表有两个及以上的节点，链表尾节点tail被删除后需要释放free()申请的尾节点tail的空间，改变尾节点tail上一个节点prev内部指针的指向，使prev内部指针指向NULL即可。

第3种情况需要找到尾节点tail和为节点的上一个节点，
方法1：使用结构体指针tail指向尾节点，使用结构体指针prev指向尾节点的上一个节点。从头开始遍历一遍链表即可找到需要的tail与prev。

PopBack_3_1.gif

方法2：只是用一个结构体指针cur找尾节点的上一个节点，我们其实只需要找到尾节点的上一个节点即可，这样尾节点自然也就知道了。cur开始指向第一个节点，当cur->next->next == NULL，即当前节点的下一个节点的内部指针指向NULL说明找到了尾节点的上一个节点。

PopBack_3_2.gif

9. 头删节点

void SListPopFront(SLNode** pphead) {
	assert(pphead);
    //暴力检查
	assert(*pphead);
    //温柔检查
    //if(*pphead == NULL){
    //    return;   
    //}
	
    SLNode* del = *pphead;
    *pphead = del->next;
    free(del);
    //del == NULL;
}

单链表头删数据，时间复杂度为 O ( 1 ) O(1) O(1)
尾删分为三种情况：

  1. 链表为空，一个节点也没有。这时外部头指针phead指向NULL，不能对链表进行删除节点操作。接口函数函数可以不进行操作而直接返回（柔和检查）；也可以对头指针为NULL进行断言assert()（暴力检查），只有当头指针phead不为NULL时才继续删除操作。
  2. 链表中只有一个节点，删除此节点之后链表为空，及时释放free()被删除节点空间，外部头指针phead此时需要改变指向（值），需要使其指向NULL；所以此情况我们需要二级结构体指针pphead接受外部头指针phead的地址。

对二级指针pphead进行断言处理：

image.png
PopBack_2.gif

  1. 链表有两个及以上的节点，头指针phead所指节点就是需要删除的节点，使用结构体指针del临时指向该节点。先更新头指针phead使其通过del内部的指针指向的下一个节点，再释放free()待删除节点del申请的空间即可。

PopFront_3.gif

10. 查找数据

//查找数据，找到返回所在节点的地址
SLNode* SListFind(SLNode* phead, SLTDataType x) {
	SLNode* cur = phead;
	while (cur) {
		if (cur->data == x) {
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

查找节点储存的数据，最坏时间复杂度为 O ( N ) O(N) O(N)。
该函数参数SLNode* phead接受节点的地址并认为其是链表的头节点的地址，至于为什么此参数不是二级指针的形式，是因为本函数只是依次遍历访问结点，但并不修改外部的头指针phead；参数SLTDataType x是待查找的数据；函数返回类型是结构体类型SLNode*指针（结点指针），找到就返相应结点的地址，否则返回NULL。
为了防止传入的头指针副本phead被随便改变以至于在本函数内部找不到头结点，我们通过创建临时结构体指针cur的方式代替头结点副本phead遍历访问整个链表。
循环遍历整个链表，直到遍历完链表停止循环返回NULL或者遇到链表中某一个节点储存的数据与待查找的数据x相同停止循环，并返回相应结点地址。

Find.gif

11. 在pos节点之前插入数据

//在pos节点之前插入数据
void SListInsert(SLNode** pphead, SLNode* pos, SLTDataType x) {
	assert(pphead);	
	
	//法1：遍历链表找到pos前一个再插入
	if ((*pphead) == pos) {
		/*SLNode* newnode = BuyNode(x);
		newnode->next = *pphead;
		*pphead = newnode;*/
		SListPushFront(pphead, x);
	}
	else {
		SLNode* prev = *pphead;
		//找pos前一个位置
		while (prev->next != pos) {
			prev = prev->next;
			//如果prev为NULL，说明遍历完链表也没找到pos，传参错误，暴力检查
			assert(prev);
		}
		SLNode* newnode = BuyNode(x);
		newnode->next = pos;
		prev->next = newnode;
	}
}

方法1：在某一个节点pos之前插入数据，最坏时间复杂度为 O ( n ) O(n) O(n)
分为3种情况

  1. 链表为空，在没有节点时无法在节点之前插入数据，说明调用本函数的使用者传参传错了，使用者应该至少保证链表有一个结点的情况下使用此函数，函数内部并不需要对此情况做出判断。
  2. 如果传入的结点地址pos等于头指针phead，或者说pos等于头结点的地址，则在该节点之前插入数据，相当于对单链表的头插操作，可以手动实现该操作，也可以直接调用头插函数接口实现。头插操作需要外部头指针phead的地址，所以参数是二级结构体指针。

Insert_1_2.gif

  1. 如果传入的结点地址pos不等于头指针phead，或者说pos不等于头结点的地址，那么就是在非头结点之前插入数据。这时就不涉及外部头指针phead的改变了，但因为是在pos结点之前插入，我们需要找到pos节点的上一个节点，借助结构体指针prev通过while循环从头结点开始遍历链表找到pos节点上一个节点。

注意循环的条件prev->next != pos，找的是pos的上一个结点，所以循环停止时prev就指向了pos的上一个结点。
为了防止使用者传入了不是本链表内的结点，导致循环结束时也找不到pos，prev就指向了NULL，对prev此时就是空指针，while循环的条件便可能会对空指针解引用，而导致程序出错。所以在while循环内部我们需要对每次更新后的prev进行暴力判断assert(prev)，是NULL直接报错。

Insert_1.gif

//在pos节点之前插入数据
void SListInsert(SLNode* pos, SLTDataType x) {
	assert(pphead);	
    
    //法2：狸猫换太子，插入到pos后面，在交换两个节点的值
	//这种方法不涉及头指针，更不会改变头指针的值，相比法1减少了对头指针参数的使用
    SLNode* newnode = BuyNode(x);
    newnode->next = pos->next;
    pos->next = newnode;
    int tmp = pos->data;
    pos->data = newnode->data;
    newnode->data = tmp;
}

方法2：在某一个节点pos之前插入数据，时间复杂度为 O ( 1 ) O(1) O(1)
两种情况：

  1. 链表为空，在没有节点时无法在节点之前插入数据，说明调用本函数的使用者传参传错了，使用者应该至少保证链表有一个结点的情况下使用此函数，函数内部并不需要对此情况做出判断。
  2. 我们知道，再插入数据时，其实也创建了一个储存数据的新节点。不是要求新创建的节点要在pos节点之前，而是待插入的数据x要在pos储存数据的相对之前。也就是说只要保持这两个数据的相对顺序即可，至于节点的相对顺序可以不管。

于是有了一个思路：因为直接在pos头插数据x要遍历链表找prev，所以先在pos节点之后插入新节点newnode，因此不需要头节点来遍历链表了，也就不需要接受头节点的参数，pos尾插数据更加简单。尾插完成后，新结点中储存着数据x，这时不需要改变pos节点与新节点newnode的顺序，只需要交换两个节点的数据就可以实现X头插在了pos节点之前的效果了。

Insert_2.gif

12. 在pos结点之后插入数据

//在pos节点之后插入数据
void SListInsertAfter(SLNode* pos, SLTDataType x) {
	SLNode* newnode = BuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

在pos结点之后插入数据只需创建一个新节点newnode，然后改变newnode内部指针使其指向pos的下一个节点，再改变pos内部的节点使其指向newnode新节点。
时间复杂度为 O ( 1 ) O(1) O(1)

13. 删除pos节点

//删除pos节点
void SListErase(SLNode** pphead, SLNode* pos) {
	assert(pphead);
	if (*pphead == pos) {
		//头删数据
		SListPopFront(pphead);
	}
	else
	{
		SLNode* prev = *pphead;
		while (prev->next != pos) {
			prev = prev->next;
			assert(prev);//prev为NULL时说明遍历完链表了，但没有找到pos，说明pos传错了
		}
		
		prev -> next = pos->next;
		free(pos);
		//pos = NULL;把局部变量tmp置为NULL对主调函数的pos无任何影响，调用者应该自己手动置NULL
	}
}

删除pos节点及数据，分为两种情况：

  1. pos节点就是头节点，此时删除的相当与是链表的头节点，是头删数据。可以直接调用头删函数接口，也可以手动实现头删操作。需要涉及外部头指针phead的改变，所以需要二级指针pphead接受外部头指针的地址。

ErasePos_1_1.gif

  1. pos节点不是头节点，是一般情况，不涉及外部头指针phead的改变。但此时删除pos节点同时要使pos节点的前一个节点的内部指针从指向pos变为指向pos的下一个节点。我们需要先找到pos节点的上以一个节点，借助结构体指针变量prev通过循环找到，找到prev节点后，使prev内部指针指向pos下一个结点，再手动释放free()待删除节点pos。由于传入的pos是一级指针，我们修改内部的pos无法对外部的pos产生任何影响，调用该函数者需要手动把外部pos置为NULL，free()之后内部pos是否置为NULL都无所谓。

ErasePos_1_2.gif

14. 删除pos节点之后的节点

//删除pos节点之后的节点
void SListEraseAfter(SLNode* pos) {
	//pos不为空
	assert(pos);
	//pos->next也不为空
	assert(pos->next);
	SLNode* del = pos->next;
	pos->next = del->next;
	free(del);
	//把局部变量del置为NULL对主调函数的pos无任何影响，调用者应该自己手动置NULL
	//del = NULL;
}

删除pos节点之后的结点，不需要找pos的上一个结点prev，所以并不需要链表的头指针；也不需要该表外部头指针phead的指向，故也不需要头指针的地址。我们在本接口函数内部只改变结点pos的内部成员，故需要传结点pos地址一级指针即可。
时间复杂度为 O ( 1 ) O(1) O(1)
要删除传入节点pos的下一个节点，要求pos结点和下一个节点都要存在，这里进行了暴力断言assert(pos)和assert(pos->next)检查。
当断言检查完毕，借助一个临时结构体变量del储存pos节点的下一个节点待删除节点的地址，使pos内部指针next置为pos下一个节点的内部指针next的值；然后手动释放free()待删除节点del的空间，在本函数内部把del置为NULL并不会影响外部的节点，局部指针变量del在本接口函数返回时就被销毁了，所以del置不置为NULL都可以。

ErasePosAfter.gif

15. 销毁单链表

//销毁单链表
void SListDestroy(SLNode** pphead) {
	assert(pphead);
	SLNode* cur = *pphead;
	while (cur) {
		SLNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

销毁链表，也就是释放掉链表中所有节点申请的空间，把头指针置为NULL的过程。
时间复杂度为 O ( n ) O(n) O(n)
销毁单链表需要改变外部头指针phead的值，使其指向NULL，防止野指针的情况。所以销毁功能的接口函数需要的到头指针的地址，即二级结构体指针pphead。
同时我们使用临时指针变量cur从头节点开始一次访问链表各个节点并释放这些节点。这样不直接通过二级指针pphead使用外部头指针phead避免了外部头指针的改变。
一级指针cur遍历链表用while循环实现，每一次循环借助临时结构体指针变量next储存cur内部next的值（也就是cur下一个节点的地址），然后手动释放free``cur所指向的当前节点，最后借助临时指针变量next更新cur；当cur为NULL时说明遍历完成。
直到最后把外部头指针phead置为空即可。

DestroyList.gif

4.3 代码实现

分文件实现：

头文件SList.h

#pragma once
//本程序大部分通过二级指针实现单向、不循环、无头节点(无哨兵头)的链表
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

typedef int SLTDataType;
//节点类型
typedef struct SListNode {
	SLTDataType data;
	struct SListNode* next;
}SLNode;


//数据输出到控制台
void SListPrint(SLNode* phead);

//销毁单链表
void SListDestroy(SLNode** pphead);

//申请一个新节点
SLNode* BuyNode(SLTDataType x);

//头插尾插 头删尾删
void SListPushBack(SLNode** pphead, SLTDataType x);
void SListPushFront(SLNode** pphead, SLTDataType x);
void SListPopBack(SLNode** pphead);
void SListPopFront(SLNode** pphead);

//查找数据，找到返回所在节点的地址
SLNode* SListFind(SLNode* phead, SLTDataType x);

//在pos节点之前插入数据
void SListInsert(SLNode** pphead, SLNode* pos, SLTDataType x);

//在pos节点之后插入数据
void SListInsertAfter(SLNode* pos, SLTDataType x);

//删除pos节点
void SListErase(SLNode** pphead, SLNode* pos);

//删除pos节点之后的节点
void SListEraseAfter(SLNode* pos);

函数定义源文件SList.c

#include "SList.h"

//数据输出到控制台
void SListPrint(SLNode* phead) {
	while (phead) {
		printf("%d ", phead->data);
		phead = phead->next;
	}
	printf("\n");
}

//销毁单链表
void SListDestroy(SLNode** pphead) {
	assert(pphead);
	SLNode* cur = *pphead;
	while (cur) {
		SLNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

SLNode* BuyNode(SLTDataType x) {
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	if (!newnode) {
		perror("newnode\n");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
}

//尾插
void SListPushBack(SLNode** pphead, SLTDataType x) {
	assert(pphead);
	SLNode* newnode = BuyNode(x);
	if (*pphead == NULL) {
		*pphead = newnode;
	}
	else {
		SLNode* cur = *pphead;
		while (cur->next) {
			cur = cur->next;
		}
		cur->next = newnode;
	}
}

//头插
void SListPushFront(SLNode** pphead, SLTDataType x) {
	assert(pphead);
	SLNode* newnode = BuyNode(x);
	if (*pphead == NULL) {
		*pphead = newnode;
	}
	else {
		newnode->next = *pphead;
		*pphead = newnode;
	}
}

//尾删
void SListPopBack(SLNode** pphead) {
	assert(pphead);
	//暴力检查
	assert(*pphead);
	//温柔检查
	//if(*pphead == NULL){
	//    return;   
	//}
	if ((*pphead)->next == NULL) {
		free(*pphead);
		*pphead = NULL;
	}
	else {
		//法1
		SLNode* prev = NULL;
		SLNode* tail = *pphead;
		while (tail->next) {
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		//tail = NULL;
		prev->next = NULL;

		法2
		//SLNode* cur = *pphead;
		//while (cur->next->next) {
		//	cur = cur->next;
		//}
		//free(cur->next);
		//cur->next = NULL;
	}
}

//头删
void SListPopFront(SLNode** pphead) {
	assert(pphead);
	//暴力检查
	assert(*pphead);
	//温柔检查
	//if(*pphead == NULL){
	//    return;   
	//}

	SLNode* del = *pphead;
	*pphead = del->next;
	free(del);
	//del == NULL;	
}

//查找数据，找到返回所在节点的地址
SLNode* SListFind(SLNode* phead, SLTDataType x) {
	SLNode* cur = phead;
	while (cur) {
		if (cur->data == x) {
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

//在pos节点之前插入数据
void SListInsert(SLNode** pphead, SLNode* pos, SLTDataType x) {
	assert(pphead);
	
	//法1：遍历链表找到pos前一个再插入
	if ((*pphead) == pos) {
		/*SLNode* newnode = BuyNode(x);
		newnode->next = *pphead;
		*pphead = newnode;*/
		SListPushFront(pphead, x);
	}
	else {
		SLNode* prev = *pphead;
		//找pos前一个位置
		while (prev->next != pos) {
			prev = prev->next;
			//如果prev为NULL，说明遍历完链表也没找到pos，传参错误，暴力检查
			assert(prev);
		}
		SLNode* newnode = BuyNode(x);
		newnode->next = pos;
		prev->next = newnode;
	}

	法2：狸猫换太子，插入到pos后面，在交换两个节点的值
	这种方法不涉及头指针，更不会改变头指针的值，相比法1减少了对头指针参数的使用
	//if (*pphead == NULL) {
	//	SListPushFront(pphead, x);
	//}
	//else {
	//	SLNode* newnode = BuyNode(x);
	//	newnode->next = pos->next;
	//	pos->next = newnode;
	//	int tmp = pos->data;
	//	pos->data = newnode->data;
	//	newnode->data = tmp;
	//}
}

//在pos节点之后插入数据
void SListInsertAfter(SLNode* pos, SLTDataType x) {
	SLNode* newnode = BuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

//删除pos节点
void SListErase(SLNode** pphead, SLNode* pos) {
	assert(pphead);
	if (*pphead == pos) {
		//头删数据
		SListPopFront(pphead);
	}
	else
	{
		SLNode* prev = *pphead;
		while (prev->next != pos) {
			prev = prev->next;
			assert(prev);//prev为NULL时说明遍历完链表了，但没有找到pos，说明pos传错了
		}
		prev -> next = pos->next;
		free(pos);
		//pos = NULL;把局部变量tmp置为NULL对主调函数的pos无任何影响，调用者应该自己手动置NULL
	}
}

//删除pos节点之后的节点
void SListEraseAfter(SLNode* pos) {
	//pos不为空
	assert(pos);
	//pos->next也不为空
	assert(pos->next);
	SLNode* del = pos->next;
	pos->next = del->next;
	free(del);
	//把局部变量del置为NULL对主调函数的pos无任何影响，调用者应该自己手动置NULL
	//del = NULL;
}

至于调用以上接口函数的main()函数不包括在内。

结语

本文较详细的讲解了单链表的一种实现形式：二级指针的形式。希望能够帮助到需要的朋友！

END

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布