【数据结构】单链表详解_链表头文件

目录

一、链表的定义和分类

1.链表的定义

2.链表的分类

二、单链表的创建

三、单链表函数的接口实现

1.头文件SListNode.h

2.源文件SListNode.c

3.源文件test.c

---

一、链表的定义和分类

1.链表的定义

  链表是指物理地址不连续，逻辑上连续的一种数据结构，可以通过指针访问各节点。

2.链表的分类

分类标准：单向和双向；带(哨兵位)头节点和不带(哨兵位)头节点；循环和不循环。

总共可以分为8类。

 

  虽然分类比较多，但常用的链表是普通的单链表和双向带头循环链表。

（双向带头循环链表在下篇博客中会进行介绍。）

二、单链表的创建

单链表由一个个节点连接而成，节点要包含的信息除了一个有效值之外，还需包含下一个节点的地址。故节点的实现需要利用结构体。

节点的创建：

typedef int SLTDataType;
struct SListNode
{
	SLTDataType data;//有效值
	struct SListNode* next;//下一个节点的地址
};

三、单链表函数的接口实现

1.头文件SListNode.h

节点的定义和单链表增删查改函数的声明。

#pragma once
 
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
 
typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SListNode;
 
// 动态申请一个节点
SListNode* BuySListNode(SLTDataType x);
 
// 单链表打印
void SListPrint(SListNode* plist);
 
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDataType x);
 
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDataType x);
 
// 单链表的尾删
void SListPopBack(SListNode** pplist);
 
// 单链表头删
void SListPopFront(SListNode** pplist);
 
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDataType x);
 
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
void SListInsertAfter(SListNode* pos, SLTDataType x);
 
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？
void SListEraseAfter(SListNode* pos);
 
// 单链表的销毁
void SListDestroy(SListNode* plist);

2.源文件SListNode.c

进行单链表增删查改接口函数的实现(定义）。

#define _CRT_SECURE_NO_WARNINGS 1
#include "SListNode.h"
 
// 动态申请一个节点
SListNode* BuySListNode(SLTDataType x)
{
	//用malloc在堆区上动态申请一个节点
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	//初始化节点内容
	newnode->data = x;
	newnode->next = NULL;
}
 
// 单链表打印
void SListPrint(SListNode* plist)
{
	SListNode* cur = plist;
    //遍历链表
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}
 
// 单链表尾插
//链表尾插前不需要断言，断言是为了保证指针不为空；
//而链表为空时也能插入节点
//但是因为链表为空时插入节点，需要将新的节点的地址赋值给plist，
//所以形参必须为二级指针，用来接收plist的地址
void SListPushBack(SListNode** pplist, SLTDataType x)
{
	//创建一个data值为x的节点
	SListNode* tmp = BuySListNode(x);
	//链表为空
	if (*pplist == NULL)
	{
		*pplist = tmp;
		return;
	}
	//链表不为空
	SListNode* cur = *pplist;
	while (cur->next != NULL)
	{
		cur = cur->next;
	}
	cur->next = tmp;
}
 
// 单链表的头插
//需要更新头节点，在更新之前先将原头节点的地址赋值给新节点的next，实现逻辑上的连接
void SListPushFront(SListNode** pplist, SLTDataType x)
{
	//创建一个data值为x的节点
	SListNode* tmp = BuySListNode(x);
	tmp->next = *pplist;
	*pplist = tmp;
}
 
// 单链表的尾删
//链表尾删前需要断言，断言是为了保证指针不为空；
//因为链表为空时不能进行删除节点的操作。
//因为链表只有一个节点时删除节点节点，需要将plist置为空指针，
//所以形参必须为二级指针，用来接收plist的地址。
void SListPopBack(SListNode** pplist)
{
	assert(*pplist);//避免链表为空
	//链表只有一个节点
	if ((*pplist)->next == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	//链表有两个及以上节点
	SListNode* tail = *pplist;
	while (tail->next->next != NULL)//tail最后指向倒数第二个节点
	{
		tail = tail->next;
	}
	free(tail->next);
	tail->next = NULL;
}
 
// 单链表头删
//与尾删相同的原因，头删也需要先断言，避免链表为空。
//头删需要改变plist的值，所以需要传二级指针，
//记录第二个节点的地址后，将第一个节点的空间释放；
//最后将第二个节点的地址赋值给plist（若原链表只有一个节点，该操作后plist为空，故不需要分类特别处理。
void SListPopFront(SListNode** pplist)
{
	//避免链表为空
	assert(*pplist);
 
	SListNode* tmp = (*pplist)->next;//记录第二个节点的位置(只有一个节点则该指针置为NULL
	(*pplist)->next = NULL;
	free(*pplist);
	*pplist = tmp;
}
 
// 单链表查找
//遍历链表，找到了返回对应节点的地址；遍历整个链表还没找到就返回NULL
SListNode* SListFind(SListNode* plist, SLTDataType x)
{
	assert(plist);//避免链表为空
 
	SListNode* cur = plist;
	while (cur != NULL)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}
 
//单链表在pos位置之后插入x
//需要断言
//分析思考为什么不在pos位置之前插入：
//原因：能够通过将data值为x的节点的地址传给pos位置节点的next，
//而我们无法直接得到pos位置前一个节点的next，需要遍历链表才能做到，效率低
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
	assert(pos);
	SListNode* newnode = BuySListNode(x);
 
	newnode->next = pos->next;
	pos->next = newnode;
}
 
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？
//删除pos位置需要将pos-1位置的next置为pos+1的地址，但是无发通过pos访问到pos-1位置
void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	if (pos->next == NULL)
		return;
	SListNode* tmp = pos->next;
	pos->next = pos->next->next;
	//tmp->next = NULL;   不要这个也可以，为什么可以?
	free(tmp);
}
 
// 单链表的销毁
//遍历链表进行节点的销毁，遍历一个释放一个节点的空间；
//指针不用置空，因为cur为局部变量，函数调用结束后就会销毁
void SListDestroy(SListNode** pplist)
{
	assert(*pplist);
	SListNode* cur = *pplist;
	while (cur)
	{
		SListNode* tmp_next = cur->next;//记录下一个节点的地址
		free(cur);
		cur = tmp_next;
	}
}

3.源文件test.c

测试接口函数的实现是否正确。

#define _CRT_SECURE_NO_WARNINGS 1
#include "SListNode.h"
 
int main()
{
	SListNode* plist = NULL;
	//测试尾插函数   测试成功
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 1);
	//打印链表内容
	SListPrint(plist);//3->2->1->NULL
 
	//测试头插函数  测试成功
	SListPushFront(&plist, 4);
	SListPushFront(&plist, 5);
	SListPushFront(&plist, 6);
	//打印链表内容
	SListPrint(plist);//6->5->4->3->2->1->NULL
 
	//测试尾删函数   测试成功
	SListPopBack(&plist);
	SListPopBack(&plist);
	//打印链表内容
	SListPrint(plist);//6->5->4->3->NULL
 
	//测试头删函数   测试成功
	SListPopFront(&plist);
	SListPopFront(&plist);
	//打印链表内容
	SListPrint(plist);//4->3->NULL
 
	//测试查找函数   测试成功
	SListNode* pos = SListFind(plist,3);
	//SListNode* pos = SListFind(plist,5));
	if (pos)
		printf("链表中有该元素\n");
	else
		printf("链表中没有该元素\n");
 
	//测试在pos位置之后插入x的函数   测试成功
	SListInsertAfter(plist->next, 2);
	//打印链表内容
	SListPrint(plist);//4->3->2->NULL
 
	//测试删除位置之后的值的函数    测试成功
	SListEraseAfter(plist);
	//打印链表内容
	SListPrint(plist);//4->2->NULL
 
	//销毁动态申请的内存
	SListDestroy(&plist);//如果plist已经为空链表了，assert会报错
	plist = NULL;//避免野指针
 
	return 0;
}

四、总结

单链表较顺序表而言，头插头删效率更高(时间复杂度O(1)），缺点是不能随机访问链表元素。其次，链表只能从前向后访问，后续博客会讲到的双向带头循环俩表就可以做到从后往前访问，更加灵活方便。