投稿
  1. 首页
  2. C

单链表的简单实现

code • 2022-4-11 • C • 阅读 32

单链表的简单实现,第1张

 

目录

1、链表与顺序表的差异

2、定义一个SListNode结构体

3、动态申请一个节点

4、单链表的打印

5、单链表的尾插

6、 单链表的头插

7、单链表的尾删

8、 单链表的头删

9、单链表的查找

10、在pos之后插入数据

11、在pos之后删除数据

12、单链表的销毁

13、完整代码

14、结尾

1、链表与顺序表的差异

上一篇我们简单实现了顺序表，那么这一篇来简单实现一下单链表。


顺序表缺陷：

1. 中间/头部的插入删除，时间复杂度为O(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间。


会有不小的消耗。



3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。


例如当前容量为100，满了以后增容到200，我们
再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。


因此我们引入了链表，链表：概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。


由此可见，链表在结构上给我们提供了顺序表所不能提供的便利。


2、定义一个SListNode结构体 
typedef int SLTDateType;

typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;

不难发现我们在SListNode 中定义了一个 struct SListNode * 的next指针变量 用来指向后面数据的地址。


3、动态申请一个节点 
//动态申请一个节点
SListNode* BuyListNode(SLTDateType x)
{
	SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
	if (newNode == NULL)
		return NULL;
	newNode->data = x;
	return newNode;
}

 此 *** 作为了方便创建新节点，这样的话只要调用此函数就可以创建新的节点了。


4、单链表的打印 

//单链表打印
void SListPrint(SListNode* plist)
{
	assert(plist);

	while (plist)
	{
		printf("%d->", plist->data);
		plist = plist->next;
	}
}

此函数可以将链表中的数据进行逐个打印出来。


5、单链表的尾插 
//单链表的尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
	SListNode* newNode = BuyListNode(x);
	SListNode* tail = *pplist;
	while (tail->next != NULL)
	{
		tail = tail->next;
	}
	tail->next = newNode;
	newNode->next = NULL;
}

此函数用于在单链表中进行尾插数据。


6、 单链表的头插 
void SListPushFront(SListNode** pplist, SLTDateType x)
{
	SListNode* newNode = BuyListNode(x);
	newNode->next = *pplist;
	*pplist = newNode;
}

此函数用于在单链表的头部进行插入数据。


 

7、单链表的尾删 
//单链表的尾删
void SListPopBack(SListNode** pplist)
{
	assert(pplist);
	SListNode* tail = *pplist;
	SListNode* prev = NULL;
	if (tail == NULL || tail->next == NULL)
	{
		free(tail);
		*pplist = NULL;
	}
	else
	{
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		/*if (prev == NULL)
			return NULL;*/
		prev->next = NULL;
		free(tail);
		tail = NULL;
		
	}

	
}

此函数用于单链表的尾删。


8、 单链表的头删 
//单链表头删
void SListPopFront(SListNode** pplist)
{
	assert(pplist);
	SListNode* cur = *pplist;
	if (*pplist == NULL)
	{
		return;
	}
	else if (cur->next == NULL)
	{
		free(cur);
		*pplist = NULL;
	}
	else
	{
		*pplist = cur->next;
		free(cur);
	}
}

此函数用于单链表的头删。


9、单链表的查找 
//单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	assert(plist);
	SListNode* cur = plist;
	while (cur)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}

 此函数可以在单链表中遍历用来查找你要查找的数据。


10、在pos之后插入数据 
//单链表在pos位置之后插入x
//分析思考为什么不在pos位置之前插入？
//因为单链表的指向是单一的 只能指向后一个位置
//所以如果在pos前边插入 将非常复杂
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
	SListNode* newNode = BuyListNode(x);
	SListNode* cur = NULL;
	cur = pos;
	if (cur->next == NULL)
	{
		SListPushBack(&pos, x);
	}
	newNode->next = cur->next;
	cur->next = newNode;
}
11、在pos之后删除数据 

//单链表删除pos位置之后的值
//分析思考为什么不删除pos位置？
//答案同上
void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	//pos next nextnext
	SListNode* next = pos->next;
	if (next != NULL)
	{
		SListNode* nextnext = next->next;
		free(next);
		pos->next = nextnext;
	}
}
12、单链表的销毁 
void SListDestory(SListNode* plist)
{
	SListNode* cur = plist;
	SListNode* next = NULL;
	while (cur)
	{
		next = cur->next;
		free(cur);
		cur = NULL;
		next = next->next;
	}
}
13、完整代码

我们可以分别创建一个 slist.c   一个 test.c  一个  slist.h  。


分别用来存放代码，使代码更加清晰。


slist.h 里面存放函数的定义和一些头文件的包含。


slist.c 里面来存放函数的实现。


test.c 里面来存放你所需要测试的每个函数。


slist.c

代码如下：

#include"slist.h"

//动态申请一个节点
SListNode* BuyListNode(SLTDateType x)
{
	SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
	if (newNode == NULL)
		return NULL;
	newNode->data = x;
	return newNode;
}

//单链表打印
void SListPrint(SListNode* plist)
{
	assert(plist);

	while (plist)
	{
		printf("%d->", plist->data);
		plist = plist->next;
	}
}

//单链表的尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
	SListNode* newNode = BuyListNode(x);
	SListNode* tail = *pplist;
	while (tail->next != NULL)
	{
		tail = tail->next;
	}
	tail->next = newNode;
	newNode->next = NULL;
}


//单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{
	SListNode* newNode = BuyListNode(x);
	newNode->next = *pplist;
	*pplist = newNode;
}

//单链表的尾删
void SListPopBack(SListNode** pplist)
{
	assert(pplist);
	SListNode* tail = *pplist;
	SListNode* prev = NULL;
	if (tail == NULL || tail->next == NULL)
	{
		free(tail);
		*pplist = NULL;
	}
	else
	{
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		/*if (prev == NULL)
			return NULL;*/
		prev->next = NULL;
		free(tail);
		tail = NULL;
		
	}

	
}

//单链表头删
void SListPopFront(SListNode** pplist)
{
	assert(pplist);
	SListNode* cur = *pplist;
	if (*pplist == NULL)
	{
		return;
	}
	else if (cur->next == NULL)
	{
		free(cur);
		*pplist = NULL;
	}
	else
	{
		*pplist = cur->next;
		free(cur);
	}
}

//单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{
	assert(plist);
	SListNode* cur = plist;
	while (cur)
	{
		if (cur->data == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}


//单链表在pos位置之后插入x
//分析思考为什么不在pos位置之前插入？
//因为单链表的指向是单一的 只能指向后一个位置
//所以如果在pos前边插入 将非常复杂
void SListInsertAfter(SListNode* pos, SLTDateType x)
{
	SListNode* newNode = BuyListNode(x);
	SListNode* cur = NULL;
	cur = pos;
	if (cur->next == NULL)
	{
		SListPushBack(&pos, x);
	}
	newNode->next = cur->next;
	cur->next = newNode;
}


//单链表删除pos位置之后的值
//分析思考为什么不删除pos位置？
//答案同上
void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	//pos next nextnext
	SListNode* next = pos->next;
	if (next != NULL)
	{
		SListNode* nextnext = next->next;
		free(next);
		pos->next = nextnext;
	}
}

//单链表的销毁
void SListDestory(SListNode* plist)
{
	SListNode* cur = plist;
	SListNode* next = NULL;
	while (cur)
	{
		next = cur->next;
		free(cur);
		cur = NULL;
		next = next->next;
	}
}

slist.h

代码如下：

#pragma once
#include
#include
#include

typedef int SLTDateType;

typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;

//动态申请一个节点
SListNode* BuyListNode(SLTDateType x);

//单链表打印
void SListPrint(SListNode* plist);

//单链表的尾插
void SListPushBack(SListNode** pplist, SLTDateType x);

//单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);

//单链表的尾删
void SListPopBack(SListNode** pplist);

//单链表头删
void SListPopFront(SListNode** pplist);

//单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);

//单链表在pos位置之后插入x
//分析思考为什么不在pos位置之前插入？
//因为单链表的指向是单一的 只能指向后一个位置
//所以如果在pos前边插入 将非常复杂
void SListInsertAfter(SListNode* pos, SLTDateType x);

//单链表删除pos位置之后的值
//分析思考为什么不删除pos位置？
//答案同上
void SListEraseAfter(SListNode* pos);

//单链表的销毁
void SListDestory(SListNode* plist);

test.c

代码如下：

#include"slist.h"

void Test1()
{
	SListNode* phead = NULL;
	SListPushFront(&phead, 1);
	SListPushFront(&phead, 2);
	SListPushFront(&phead, 3);
	/*SListPushBack(&phead, 1);
	SListPushBack(&phead, 2);
	SListPushBack(&phead, 3);*///321123
	/*SListPopBack(&phead);
	SListPopBack(&phead);
	SListPopBack(&phead);*/
	/*SListPopFront(&phead);*/
	SListPrint(phead);
	SListInsertAfter(phead,3);
	printf("\n");
	SListPrint(phead);

	SListDestory(phead);

}
int main()
{
	Test1();
	return 0;
}
14、结尾

上述代码若有遗漏错误指出，希望兄弟们能指出，互相学习，互相进步。


也感谢兄弟们的观看，感谢！

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/578243.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
code code 管理员组
0 0
上一篇 2022-04-11
下一篇 2022-04-11

发表评论

登录后才能评论

评论列表（0条）

保存