无头单向非循环链表

一、头文件

Link.h这个头文件中包含了顺序表的定义和对顺序表进行操作的所有函数，所有的函数只传递结构体指针以加快程序运行速度。

#pragma once//排除包含重复头文件
#include
#include
#include//需要的头文件
 
 
#define TYPE int
typedef struct SListNode
{
	TYPE data;
	struct SListNode* next;
}SLNode;
 
 
 
 
 
//动态申请一个节点
SLNode* BuySListNode(TYPE x);
 
// 单链表打印
void SListPrint(SLNode* plist);
 
// 单链表尾插
void SListPushBack(SLNode** pplist,TYPE x);
 
// 单链表的头插
void SListPushFront(SLNode** pplist, TYPE x);
 
// 单链表的尾删
void SListPopBack(SLNode** pplist);
 
// 单链表头删
void SListPopFront(SLNode** pplist);
 
// 单链表查找
SLNode* SListFind(SLNode* plist, TYPE x);

二、函数

这些函数储存在一个function.c 文件中

1.动态申请一个节点

SLNode* BuySListNode(TYPE x);

顾名思义，在堆区开辟一块空间用于储存数据x，之后通过其他函数链接到链表内

//动态申请一个节点
SLNode* BuySListNode(TYPE x)
{
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	if (newnode == NULL)//判空，为空则退出
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;//赋值
	newnode->next = NULL;
	return newnode;
}

2.单链表的头插

void SListPushFront(SLNode** pplist, TYPE x);

单链表的维护需要一个头指针指向第一个节点。而且头插还有两种情况，一种是还没有有效数据时的头插，一种是不同的头插

注意：头插一定需要改变单独存储的头指针，所以改变地址就需要地址的地址，我们传递的参数就是二级指针

// 单链表的头插
void SListPushFront(SLNode** pplist, TYPE x)
{
	assert(pplist);
	if (*pplist == NULL)//无数据头插就直接将节点的地址作为头指针
	{
		SLNode* code = BuySListNode(x);
		*pplist = code;
	}
	else
	{
		SLNode* frontcode = (SLNode*)malloc(sizeof(SLNode));
		frontcode->data = x;
		frontcode->next = *pplist;//新建节点与头部链接
		*pplist = frontcode;//更新头指针
	}	
}

3.尾插

void enlarge(SList* p);

同样尾插也有两种情况，一种是还没有有效数据时的尾插，也就相当于头插；另一种是普通的尾插，先迭代寻找尾部，然后改变原尾部next指针为新节点地址，就直接将新节点与尾部链接了

// 单链表尾插
void SListPushBack(SLNode** pplist, TYPE x)
{
	assert(pplist);
	if (*pplist == NULL)//若还没有数据尾插就是头插，头插就需要改变头指针，传二级指针
	{
		SLNode* code = BuySListNode(x);
		*pplist = code;
	}
	else
	{
		SLNode* cur = *pplist;
		while (cur->next != NULL)
		{
			cur = cur->next;//单链表只储存头指针，只能通过一个一个向后找才能迭代到尾部
		}
		SLNode* backcode = BuySListNode(x);//新建一个节点
		cur->next = backcode;//将末尾与新的节点链接起来
		backcode->next = NULL;//保证next不为野指针
	}
}

4.打印

void SListPrint(SLNode* plist);

迭代逐个打印直到尾部即可

// 单链表打印
void SListPrint(SLNode* plist)//简单的打印并迭代
{
	SLNode* cur = plist;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

5.尾删

void SListPopBack(SLNode* plist);

*pplist表示就是头指针存储的地址，当链表为空时头地址为NULL也就达到当链表为空时，不进行删除的检查

单链表的尾删分为链表只有一个节点的尾删和链表有多个节点的尾删两种情况

一个节点：就只需要释放头节点，然后把头指针置空防止野指针

多个节点：先迭代寻找尾部的前一个，然后用指针找到再将尾部释放，此时前一个就变成了最后一个。但是，此时的尾部的next依旧指向被释放的那个空间，我们就需要将这个节点的next置空

// 单链表的尾删
void SListPopBack(SLNode** pplist)
{
	assert(pplist);
	assert(*pplist);//判断空
	SLNode* back = *pplist;//先把头节点赋给back指针
	//只有一个节点的尾删
	if ((*pplist)->next == NULL)
	{
		free(back);//释放头节点
		*pplist = NULL;//把头指针置空
	}
	//多个节点的尾删
	else
	{
		while (back->next->next != NULL)//迭代找倒数第二个节点
		{
			back = back->next;
		}
		free(back->next);//释放尾节点
		back->next = NULL;//置空野指针
	}
}

6.头删

void SListPopFront(SLNode** pplist);

*pplist表示就是头指针存储的地址，当链表为空时头地址为NULL也就达到当链表为空时，不进行删除的检查

首先储存一下头指针，头指针改为第二个节点，释放储存的原首节点

// 单链表头删
void SListPopFront(SLNode** pplist)
{
	assert(pplist);
	assert(*pplist);
	SLNode* code = *pplist;//定义指针指向头
	*pplist = code->next;//让头指针指向下一个位置
	free(code);
	code = NULL;//释放并置空
}

7.单链表查找

void SListPopFront(SLNode** pplist);

迭代查找数据，查找到就返回该节点的指针，找不到就返回空指针

// 单链表查找
SLNode* SListFind(SLNode* plist, TYPE x)
{
	SLNode* cur = plist;
	while (cur->next != NULL)
	{
		if (cur->data == x)
		{
			return cur;//找到返回对应节点
		}
		cur = cur->next;//迭代
	}
	return NULL;//找不到返回NULL
}

8.特定位置前插

void SListInsertbefore(SLNode** pplist, SLNode* pos, TYPE x);

如果这个pos指向的位置是头，就直接头插；如果pos指向的位置是其他位置，建立一个prev指针指向pos前面的节点，首先建立一个新的节点并储存对应数据，先让新节点指向pos以保证不破坏链表的连续性然后把prev的next赋值为新节点就完成了pos前插

// 在pos之前插入
void SListInsertbefore(SLNode** pplist, SLNode* pos, TYPE x)
{
	assert(pplist);
	assert(pos);
	if (pos == *pplist)//前插的对象为头，头插
	{
		SListPushFront(pplist, x);
	}
	else
	{
		SLNode* prev = *pplist;
		while (prev->next != pos)
		{
			prev = prev->next;
			assert(prev);//在查找完成后如果没有查找到pos，那么prev就会指向空位置，达到了检查的目的
		}
		SLNode* newnode = BuySListNode(x);
		prev->next = newnode;//先把该节点和它插入后的下一个链接，以防断开链表
		newnode->next = pos;//链接前面
	}
}

8.特定位置后插

void SListInsertAfter(SLNode* pos, TYPE x);

首先找到pos节点，建立一个节点并储存数据，将新节点与pos的下一个节点连接起来，最后将pos与新节点连接

void SListInsertAfter(SLNode* pos, TYPE x)
{
	assert(pos);
	SLNode* newnode = BuySListNode(x);
	newnode->next = pos->next;//此时原链表连续，先把新节点与pos链接
	pos->next = newnode;//将链表连接好
}

三、调试

通过test.c来进行操作

void test1()
{
	SLNode* plist = NULL;
	plist = BuySListNode(1);
	SListPrint(plist);
	SListPushFront(&plist, 0);
	SListPrint(plist);
	SListPushBack(&plist, 2);
	SListPrint(plist);
	SListPopFront(&plist);
	SListPrint(plist);
	destoy(&plist);
}
 
 
 
void test2()
{
	SLNode* plist = NULL;
	SListPushBack(&plist, 4);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 1);
	SListPrint(plist);
 
	printf("找到了：%d\n",SListFind(plist, 3)->data);
	SLNode* a = SListFind(plist, 3);
 
 
	SListPrint(plist);
	destoy(&plist);
}
 
 
int main()
{
	//test1();
	test2();
	return 0;
}