【数据结构与算法】【C】 - 无头非循环单向链表

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

🐱作者：傻响
🐱专栏：《数据结构与算法》
🔥格言：你只管努力，剩下的交给时间！

                                                              ​

目录

 (一)、无头单向非循环链表的实现

1.1 链表中数据元素的构成

1.2 开辟节点空间函数

1.3 单链表打印函数

1.4 单链表头插函数

1.5 单链表尾插函数

1.6 单链表内存销毁函数

1.7 单链表头删函数

1.8 单链表尾删函数

1.9 单链表查找函数

2.0 单链表在pos位置之前插函数

2.1 单链表在pos位置之后插函数

2.2 单链表在pos位置前删函数

2.3 单链表在pos位置后删函数

 (一)、无头单向非循环链表的实现

1.1 链表中数据元素的构成

每个元素本身由两部分组成:

  1. 存储数据的区域，称为“数据域"；

  2. 指向直接后继的指针，称为“指针域”。

                                     

这两部分信息组成数据元素的存储结构，称之为“结点”。n个结点通过指针域相互链接，组成一个链表。

 

由于每个结点中只包含一个指针域，生成的链表又被称为单链表。

链表中存放的不是基本数据类型，需要用结构体实现自定义：

// 单链表的数据结构
typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;			// 节点数据存储区。
	struct SListNode* next;		// 指向下一个节点的结构体指针。

}SListNode;

// 单链表开辟新节点 - 函数声明
SListNode* BuySListNode(SLTDataType val);

// 单链表内存销毁 - 函数声明
void SListDestort(SListNode** ppHead);

// 单链表头插 - 函数声明
void SListPushFront(SListNode** ppHead, SLTDataType val);

// 单链表尾插 - 函数声明
void SListPushBack(SListNode** ppHead, SLTDataType val);

// 单链表头删 - 函数声明
void SListPopFront(SListNode** ppHead);

// 单链表尾删 - 函数声明
void SListPopBack(SListNode** ppHead);

// 单链表在pos位置之前插 - 函数声明
void SListInsert(SListNode** ppHead, SListNode* pos, SLTDataType val);

// 单链表在pos位置之后插 - 函数声明
void SListInsertAfter(SListNode* pos, SLTDataType val);

// 单链表在pos位置前删 - 函数声明
void SListErase(SListNode** ppHead, SListNode* pos);

// 单链表在pos位置后删 - 函数声明
void SListEraseAfter(SListNode* pos);

// 单链表查找 - 函数声明
SListNode* SListFind(SListNode* pHead, SLTDataType val);

// 单链表打印函数 - 函数声明
void SListPrint(SListNode* pHead);

 

1.2 开辟节点空间函数

开辟节点空间就是直接开辟一个节点空间，这里直接使用malloc这个函数就可以开辟了，开辟是主要返回的指针不能是空指针，所以要进行判断一下。

// 单链表开辟新节点空间
SListNode* BuySListNode(SLTDataType val)
{
	SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
	if (newNode == NULL)
	{
		perror("BuySListNode realloc fail!\n");
		exit(-1);
	}

	// 初始化新的节点，。
	newNode->data = val;
	newNode->next = NULL;
	// 新节点的地址返回
	return newNode;
}

1.3 单链表打印函数

void SListPrint(SListNode* pHead)
{
	// 这里不可以断言，因为链表可以是空。
	// assert(pHead);


	// 这里不要动pHead这个指针，因为这个指针一动就找不到链表的头的位置了。
	SListNode* pCurrent = pHead;

	if (pCurrent == NULL)
	{
		printf("SListNode NULL!\n");
		return;
	}
	else
	{
		// 判断指针不是Null指针。
		while (pCurrent != NULL)
		{
			printf("%d ", pCurrent->data);
			// pCurrent去下一个节点的起始位。
			pCurrent = pCurrent->next;
		}
	}
}

1.4 单链表头插函数

头插只需要将原来头结点中的指针域给新插入元素的指针域，然后再将新结点的地址给原来头结点的指针域即可。

// 单链表头插
void SListPushFront(SListNode** ppHead, SLTDataType val)
{
	// 因为ppHead拿的是pList的地址，所以一定不为空。
	assert(ppHead);

	// 开辟新的节点。
	SListNode* newNode =  BuySListNode(val);

	// 程序走到这里新的节点开辟好了，和老的节点进行链接。
	newNode->next = *ppHead;
	*ppHead = newNode;
}

// ①为什么要传入二级指针?
	如果传入的是一级指针phead，根据函数栈帧的知识我们知道，phead是头节点的临时拷贝，phead内存放头节点的地址值，但两者是独立的，我们对phead重新赋值（如接收malloc返回的地址值），是不会改变头节点的。这也就是C语言中经典的传值调用错误，所以我们需要传值调用，即传入phead的地址，所以应该传二级指针。

1.5 单链表尾插函数

尾插的话可能会分为两种情况：1、链表中有节点了 2、链表中没有节点

// 单链表尾插 - 函数声明
void SListPushBack(SListNode** ppHead, SLTDataType val)
{
	// 因为ppHead拿的是pList的地址，所以一定不为空。
	assert(ppHead);

	// 开辟新的节点。
	SListNode* newNode = BuySListNode(val);

	// 尾插分为两种情况：
	// 1、链表中没有节点   2、链表中已经有节点了（需要找尾巴）
    SListNode* pTail = *ppHead;
	if (pTail == NULL)
	{
		pTail = newNode;
		*ppHead = pTail;
		return;
	}
	// 寻找尾节点
	while (pTail->next != NULL)
	{
		pTail = pTail->next;
	}

	// 链接节点、
	pTail->next = newNode;
}

1.6 单链表内存销毁函数

消除内存空间，无非就是挨个遍历一边，挨个free，最后将*ppHead指向的pList指向NULL。

// 单链表内存销毁 - 函数声明
void SListDestort(SListNode** ppHead)
{
	// 因为ppHead拿的是pList的地址，所以一定不为空。
	assert(ppHead);

	// 从头遍历遍历一个free一个，最后把*ppHead也变成NULL
	SListNode* pCurrent = *ppHead;
	while (pCurrent != NULL)
	{
		SListNode* pTemp = pCurrent->next;
		free(pCurrent);
		pCurrent = pTemp;
	}

	// 遍历完成后,将ppHead指向的指针变为NULL
	*ppHead = NULL;
}

1.7 单链表头删函数

链表在删除数据的时候要注意释放内存 先找一个指针保存一下pList的位置， pList指向下一个节点，free到之前pList指向的位置，还要注意的就是要注意如果链表空了就不能删除啦，否则就是引用NULL指针了。

// 单链表头删
void SListPopFront(SListNode** ppHead)
{
	// 因为ppHead拿的是pList的地址，所以一定不为空。
	assert(ppHead);

	// 先保存链表的头节点。
	SListNode* del = *(ppHead);
	*ppHead = (*ppHead)->next;	// 将头指向的位置指向下一个位置。

	// 将之前头节点释放掉。
	free(del);
	del = NULL;
}

1.8 单链表尾删函数

尾删的时候要注意1个节点的时候需要直接将这个节点free掉，如果是多个节点需要采用图序的方式进行删除 有两种解法。

第一种解法：

// 单链表尾删 - 函数声明
void SListPopBack(SListNode** ppHead)
{
	// 因为ppHead拿的是pList的地址，所以一定不为空。
	assert(ppHead);
    assert(*ppHead != NULL);

	// 尾删要分为：
// 1个节点和多个节点
	if ((*ppHead)->next == NULL)
	{
		free(*ppHead);
		*ppHead = NULL;
	}
	else
	{
		// 寻找尾巴上的节点。
		SListNode* last = NULL;
		SListNode* tail = *(ppHead);
		while (tail->next != NULL)
		{
			last = tail;
			tail = tail->next;
		}

		// 程序走到这里说明找到了尾巴上的那个节点。
		last->next = NULL;
		free(tail);
		tail = NULL;
	}
}

第二种解法：

// 单链表尾删 - 函数声明
void SListPopBack(SListNode** ppHead)
{
	//  因为ppHead拿的是pList的地址，所以一定不为空。
	assert(ppHead);
    assert(*ppHead != NULL);

	// 尾删要分为：
	// 1个节点和多个节点
	if ((*ppHead)->next == NULL)
	{
		free(*ppHead);
		*ppHead = NULL;
	}
	else
	{
		// 寻找尾巴上的节点。
		SListNode* tail = *(ppHead);
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}

		// 程序走到这里说明找到了尾巴上的那个节点。
		free(tail->next);
		tail->next = NULL;
	}
}

1.9 单链表查找函数

查找的函数比较简单不解释：

当然查找其实还可以充当一些别的功能，比如：修改、某个位置插入、某个位置删除

// 单链表查找
SListNode* SListFind(SListNode* pHead, SLTDataType val)
{
	if (pHead == NULL)
		return NULL;

	// 每个节点都进行遍历，找到相等存放的值返回节点指针。
	SListNode* pCurrent = pHead;
	while (pCurrent != NULL)
	{
		if (pCurrent->data == val)
			return pCurrent;

		// 指针移动
		pCurrent = pCurrent->next;
	}

	// 程序跑到这个return说明没有找到数据。
	return NULL;
}

2.0 单链表在pos位置之前插函数

对于单链表来说，在pos前插入数据是比较麻烦的，要找到pos之前的上一个数据，那就要从头进行便利了。

当然还有一种情况就是pos的位置正好在第一个节点的位置上，这时候可以直接头插入

第一种情况：

第二种情况：

// 单链表在pos位置之前插 - 函数声明
void SListInsert(SListNode** ppHead, SListNode* pos, SLTDataType val)
{
	//  因为ppHead拿的是pList的地址，所以一定不为空。
	assert(ppHead);
	assert(pos != NULL);	// pos的位置不能为空。

	// 判断如果只有一个节点的时候,调用头插函数
	if (pos == *ppHead)
	{
		SListPushFront(ppHead, val);
	}
	else
	{
		SListNode* prev = *ppHead;
		while (prev->next != pos)
		{
			prev = prev->next;
			// 如果prev一直在往前走，走到空的位置，说明所有的节点中都没有要插入的数据。
			assert(prev);
		}

		// 程序跑到这里说明已经找到了要插入的数据。
		SListNode* newNode = BuySListNode(val);
		prev->next = newNode;
		newNode->next = pos;
		newNode = NULL;
	}

}

2.1 单链表在pos位置之后插函数

// 单链表在pos位置之后插
// 单链表不太适合pos之前插入。
void SListInsertAfter(SListNode* pos, SLTDataType val)
{
	// pos的位置不能为空。
	assert(pos);

	// 创建新节点
	SListNode* newNode = BuySListNode(val);
	
	// 将新节点出入中间，要注意时序。
	newNode->next = pos->next;
	pos->next = newNode;
}

2.2 单链表在pos位置前删函数

在pos位置删除实际和上面的代码本质有点相似！

第一种情况：

第二种情况：

// 单链表在pos位置删除 - 函数声明
void SListErase(SListNode** ppHead, SListNode* pos)
{
	//  因为ppHead拿的是pList的地址，所以一定不为空。
	assert(ppHead);
	assert(pos != NULL);	// pos的位置不能为空。

	// 判断如果只有一个节点的时候,调用头删函数
	if (pos == *ppHead)
		SListPopFront(ppHead);
	else
	{
		// 移动到pos的前一个位置。
		SListNode* prev = *ppHead;
		while (prev->next != pos)
		{
			prev = prev->next;

			// 如果prev一直在往前走，走到空的位置，说明所有的节点中都没有要删除的数据。
			assert(prev);
		}

		// 程序跑到这里说明已经找到了要删除的数据。
		SListNode* pTemp = pos;
		prev->next = pos->next;
		free(pTemp);
		pTemp = NULL;
	}

}

2.3 单链表在pos位置后删函数

单链表在pos位置后删除，是指删除pos后的数据，pos不能是尾节点。

第一种删除

 

// 单链表在pos位置后删
void SListEraseAfter(SListNode* pos)
{
	assert(pos != NULL);	// pos的位置不能为空。

	// 判断pos->next是不是NULL，如果是的话那就不能删除了
	if (pos->next == NULL)
		return;
	else
	{
		// 记忆pos之后的节点，当前pos->next指向下一个的下一个，最后free。
		SListNode* pTemp = pos->next;
		pos->next = pTemp->next;
		free(pTemp);
	}
}

本文含有隐藏内容，请 开通VIP 后查看

网站公告

今日签到

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

热门文章

最新发布