c语言单向链表

c语言实现简单的单向链表

---

一、单向链表是什么？

单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始；链表是使用指针进行构造的列表；又称为结点列表，因为链表是由一个个结点组装起来的；其中每个结点都有指针成员变量指向列表中的下一个结点；（下图来自百度）

 

二、功能代码实现

1.包含头文件

#include<Stdio.h>
#include<string.h>
#include<stdlib.h>
#include<assert.h>

2.结构体（结点）

typedef int SLTDataType;//宏定义成员为整形
typedef struct SListNode
{
	SLTDataType data;//资料
	struct SListNode* next;//连接下一个节点的链子
}SLTNode;

3.定义

SLTNode* BuyNewNode(SLTDataType X);//创建新节点
void SListPrint(SLTNode* phead);//打印
void SListDestory(SLTNode**phead);//销毁
void SListPushFront(SLTNode** pphead, SLTDataType X);//头插
void SListPushBack(SLTNode** pphead, SLTDataType X);//尾插
void SListPopFront(SLTNode** pphead);//头删
void SListPopBack(SLTNode** pphead);//尾删
SLTNode* SListFind(SLTNode* pphead, SLTDataType X);//查询
void SListInsert(SLTNode** pphead,SLTNode*pos, SLTDataType X);//插入-在pos之前插入
void SListInsert( SLTNode* pos, SLTDataType X);//插入-在pos之后插入

4.各类功能实现

SLTNode* BuyNewNode(SLTDataType X);//创建新节点-结构体指针类型函数-传值

SLTNode* BuyNewNode(SLTDataType X)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//先开辟一块空间给新节点
	if (newnode == NULL)//如果新节点为空-即开辟失败则报错
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = X;//把X的值赋给新节点的data
	newnode->next = NULL;//把链子设为空指针
	return newnode;//把节点传回去
}

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

void SListPrint(SLTNode* phead)
{
	SListNode* cur = phead;//新建一个结构体指针为表头
	while (cur != NULL)//如果指针指向的内容不为空则打印内容
	{
		printf("%d->", cur->data);
		cur = cur->next;
}
	printf("NULL\n");//为空则打印空指针
}

void SListDestory(SLTNode**phead);//销毁

void SListDestory(SLTNode** pphead)
{
	assert(pphead);//指向节点的指针不能为空
	SLTNode* cur = *pphead;//新建一个临时节点为链表头
	while (cur)//临时节点不为空时
	{
		SLTNode* next = cur->next;//链表下一个节点为临时节点的的下一个节点
		free(cur);//释放当前节点
		cur = next;//当前节点为下一个节点
	}
	*pphead = NULL;//最后释放完链表后置指针为空
}

void SListPushFront(SLTNode** pphead, SLTDataType X);//头插

void SListPushFront(SLTNode** pphead, SLTDataType X)//头插-链表吧不为空，要改变的是SList-用地址
{
	assert(pphead);
	SLTNode* newnode = BuyNewNode(X);//新建其含有对应内容的新节点
	newnode->next = *pphead;//新节点的下一个节点为表头
	*pphead = newnode;//新节点充当表头
}

void SListPopFront(SLTNode** pphead);//头删

void SListPopFront(SLTNode** pphead)//头删
{
	assert(pphead);
//	if (*pphead == NULL)//温柔检查
//	{
//		return;
//
//}
	assert(*pphead != NULL);//暴力检查
	
	SLTNode* del = *pphead;//建立新节点为表头
	*pphead = (*pphead)->next;//表头的下一个节点为表头
	free(del);//释放表头
	del = NULL;//新节点指针置为空
}

void SListPushBack(SLTNode** pphead, SLTDataType X);//尾插

void SListPushBack(SLTNode** pphead, SLTDataType X)//尾插-链表不为空，要改变的是SList 的成员-用结构体指针即可
{
	assert(pphead);
	SLTNode* newnode = BuyNewNode(X);//新建
	if (*pphead == NULL)//一种情况为表头为空-即链表只有一个空节点
	{
		*pphead = newnode;
	}
	else//另一种情况要找尾巴
	{
		//找尾
		SLTNode* tail = *pphead;//建立新节点为表头，依次找到表尾
		while(tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;//表尾替换为含有对应内容的新节点
	}
}

void SListPopBack(SLTNode** pphead);//尾删

A-单指针法

void SListPopBack(SLTNode** pphead)//尾删
{
	//	if (*pphead == NULL)//温柔检查
//	{
//		return;
//
//}
	assert(*pphead != NULL);//暴力检查
	assert(pphead);
	//对应链表只有一个节点-直接释放
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else//对应链表有多个节点
	{
		//找尾
		SLTNode* tail = *pphead;//新建节点为表头-开始找尾
 
		if (tail->next->next != NULL)//表尾为空指针-即要删除表尾前一个节点
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}

B-双指针（快慢指针法）

void SListPopBack(SLTNode** pphead)//尾删
{
	assert(pphead);
		//找尾
		SLTNode* tail = *pphead;
		SLTNode* open = NULL;
		while (tail->next != NULL)
		{
			open = tail;
			tail = tail->next;
		}
		open->next = NULL;
		free(tail->next);
		tail = NULL;
	
}

SLTNode* SListFind(SLTNode* pphead, SLTDataType X);//查询

SLTNode* SListFind(SLTNode* phead, SLTDataType X)
{
	SLTNode* cur = phead;//临时节点为表头
	while (cur)//临时节点不为空-还没遍历完链表
	{
		if (cur->data == X)//找到就返回临时节点
		{
			return cur;
		}
			cur = cur->next;
	}
	return NULL;//没找到返回空指针
	
}

void SListInsert(SLTNode** pphead,SLTNode*pos, SLTDataType X);//插入-在pos之前插入

void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType X)//插入-在pos之前插入
{
	assert(pphead);
	assert(pos);
	if (pos == *pphead)//pos为表头直接用头插
	{
		SListPushFront(pphead,X);
	}
	else {
		SListNode* pre = *pphead;
		while (pre->next != pos)
		{
			pre = pre->next;
			assert(pre);//找到NULL还没找到pos说明pos传错了
		}
		SListNode* newnode = BuyNewNode(X);//串连起来
		pre->next = newnode;
		newnode->next = pos;
	}
}

void SListInsert( SLTNode* pos, SLTDataType X);//插入-在pos之后插入

void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType X)//插入-在pos之后插入
{
	assert(pos);
	SListNode* newnode = BuyNewNode(X);
	newnode->next = pos->next;
	pos->next = newnode;
}

三、代码实现单向链表

SList.h

#include<Stdio.h>
#include<string.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;
SLTNode* BuyNewNode(SLTDataType X);//创建新节点
void SListPrint(SLTNode* phead);//打印
void SListDestory(SLTNode**phead);//销毁
void SListPushFront(SLTNode** pphead, SLTDataType X);//头插
void SListPushBack(SLTNode** pphead, SLTDataType X);//尾插
void SListPopFront(SLTNode** pphead);//头删
void SListPopBack(SLTNode** pphead);//尾删
SLTNode* SListFind(SLTNode* pphead, SLTDataType X);//查询
void SListInsert(SLTNode** pphead,SLTNode*pos, SLTDataType X);//插入-在pos之前插入
void SListInsert( SLTNode* pos, SLTDataType X);//插入-在pos之后插入
void SListEarse(SLTNode** pphead,SLTNode*pos);//删除-删除pos

SList.cpp

//顺序表的缺点
//1.中间或中部的插入和删除，时间复杂度为o（n）
//2.增容需要申请空间，拷贝数据，释放旧空间，会有消耗
//3.扩容一般以2倍的增长，易造成空间浪费
 
//链表
//无头单向非循环单链表：结构简单，一般不会单独用来存数据，实际上更多作为其他数据结构的子结构，如哈希表，图的邻接表
#include"SList.h"
 
void SListPrint(SLTNode* phead)
{
	SListNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
}
	printf("NULL\n");
}
SLTNode* BuyNewNode(SLTDataType X)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = X;
	newnode->next = NULL;
	return newnode;
}
void SListPushFront(SLTNode** pphead, SLTDataType X)//头插-链表吧不为空，要改变的是SList-用地址
{
	assert(pphead);
	SLTNode* newnode = BuyNewNode(X);
	newnode->next = *pphead;
	*pphead = newnode;
}
 
void SListPushBack(SLTNode** pphead, SLTDataType X)//尾插-链表不为空，要改变的是SList 的成员-用结构体指针即可
{
	assert(pphead);
	SLTNode* newnode = BuyNewNode(X);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找尾
		SLTNode* tail = *pphead;
		while(tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}
void SListPopFront(SLTNode** pphead)//头删
{
	assert(pphead);
//	if (*pphead == NULL)//温柔检查
//	{
//		return;
//
//}
	assert(*pphead != NULL);//暴力检查
	
	SLTNode* del = *pphead;
	*pphead = (*pphead)->next;
	free(del);
	del = NULL;
}
//void SListPopBack(SLTNode** pphead)//尾删
//{
//	assert(pphead);
//		//找尾
//		SLTNode* tail = *pphead;
//		SLTNode* open = NULL;
//		while (tail->next != NULL)
//		{
//			open = tail;
//			tail = tail->next;
//		}
//		open->next = NULL;
//		free(tail->next);
//		tail = NULL;
//	
//}
void SListPopBack(SLTNode** pphead)//尾删
{
	//	if (*pphead == NULL)//温柔检查
//	{
//		return;
//
//}
	assert(*pphead != NULL);//暴力检查
	assert(pphead);
	//一个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else//多个节点
	{
		//找尾
		SLTNode* tail = *pphead;
 
		if (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}
}
 
void SListDestory(SLTNode** pphead)
{
	assert(pphead);
	SLTNode* cur = *pphead;
	while (cur)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}
SLTNode* SListFind(SLTNode* phead, SLTDataType X)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == X)
		{
			return cur;
		}
			cur = cur->next;
	}
	return NULL;
	
}
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType X)//插入-在pos之前插入
{
	assert(pphead);
	assert(pos);//在pos之前插入
	if (pos == *pphead)
	{
		SListPushFront(pphead,X);
	}
	else {
		SListNode* pre = *pphead;
		while (pre->next != pos)
		{
			pre = pre->next;
			assert(pre);//找到NULL还没找到pos说明pos传错了
		}
		SListNode* newnode = BuyNewNode(X);
		pre->next = newnode;
		newnode->next = pos;
	}
}
void SListEarse(SLTNode** pphead, SLTNode* pos)//删除-删除pos
{
 
}
void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType X)//插入-在pos之后插入
{
	assert(pos);
	SListNode* newnode = BuyNewNode(X);
	newnode->next = pos->next;
	pos->next = newnode;
}

test.cpp

#include"SList.h"
void TestSList1()
{
	SLTNode* plist = NULL;
	SListPushFront(&plist, 1);
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 3);
	SListPushFront(&plist, 4);
	SListPrint(plist);
	SLTNode* pos = SListFind(plist, 4);
	if (pos)
	{
		pos->data *= 2;
		printf("找到了\n");
	}
	else
	{
		printf("没找到\n");
	}
	SListPrint(plist);
	SListInsert(&plist,pos, 20);
	SListPrint(plist);
	SListDestory(&plist);
	SListPrint(plist);
}
int main()
{
	TestSList1();
	return 0;
}

以上只实现了部分功能，具体可以参考上功能代码实现，或者进到我的链接看噢

https://github.com/divertlee/opening.git

---

四、总结

本人纯新手昂，有啥问题评论区cue我噢，谢谢观看！！！