【数据结构】单链表实现

数据结构与算法 11月前 0 2

结构体

文章目录

一、链表概念结构及定义
二、链表分类
三、单链表实现逻辑
四、单链表实现代码
五、单链表测试结果

串口发送接收数据

一、链表概念结构及定义

单链表是一种链式存取的，物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表的数据是以结点来表示，每个结点的构成是元素+指针。
元素：是存储数据的存储单元
指针：是连接每个结点的地址数据
在这里插入图片描述

restful

从上图结构可以看到，链式结构再逻辑上是连续的，再物理上不一定连续
现实中的结点一般都是从堆上申请出来的
从堆上申请的空间，是按照一定策略来分配，两次申请的空间可能连续，也可能不连续。
C语言结构定义：

typedef int DataType//便于改类型
typedef struct Node
{
     DataType data；//结点的数据域
     struct Node* next；//结点的指针域
}LTNode；

二、链表分类

链表的结构非常多样，以下情况组合起来就有8种链表结构：
（1）单向或者双向：
在这里插入图片描述
（2）带头或者不带头：

（3）循环或者非循环：
（4）无头单向非循环和带头双向循环链表：

ACM 模式

我们实际中最常用的是这两种结构：
1、无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单。
而今天实现是无头单向非循环链表

新浪微博

三、单链表实现逻辑

（1）创建结构体

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

先使用typedef int SLTDateType是为了方便更改数据类型，因为链表是以结点表示的，所以在结构体里创建2个变量来表示结点SLTDateType data;
struct SListNode* next;，分别表示结点的数据域和指针域
数据域是存放数据的
指针域是存放的是下一个结点的地址

AMBA协议

（2）具体函数实现及解析

（*）动态申请一个节点

SLTNode* BuySListNode(SLTDateType x)//动态申请节点
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

动态申请结点，那函数返回的应该是一个指针类型，用malloc开辟一个SLTNode大小的空间，并用newnode指向这个空间，再判断是否为空，如为空就perror，显示错误信息。反之则把要存的数据x存到newnode指向的空间里面，把指针置为空。

英雄算法联盟

（*）单链表打印

void SListPrint(SLTNode* plist)//打印链表
{
	SLTNode* cur = plist;
	while (cur)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

因为当前的指针是变化的，所以先把头指针存到定义的cur里面，在来一个while循环，终止条件是cue为空，里面是先用printf函数打印值，再更新cur。

SIP协议

（*）单链表尾插

void SListPushBack(SLTNode** pplist, SLTDateType x)// 单链表尾插
{
	assert(pplist);
	SLTNode* newnode=BuySListNode(x);
	if (*pplist == NULL)
	{
		*pplist = newnode;
	}
	else
	{
		SLTNode* tail = *pplist;
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

这里所用的是二级指针pplist，因为它在程序里面需要改变，这样传参传指针的地址的才能改变，而接收就要用二级指针。

哈希算法

尾插先用assert断言一下指针，用来检测异常情况，来提供警告信息并退出程序，再申请结点并用newnode指向，尾插有两种情况当头指针的为空，就把刚申请的结点赋给头指针，否则进行尾插尾插，先把头指针赋给定义的为指针，再用while循环来找尾部，直到为空停止，最用tail->next来链接刚申请的结点

内存越界

（*）单链表的头插

void SListPushFront(SLTNode** pplist, SLTDateType x)//单链表的头插
{
	assert(pplist);
	SLTNode* newnode = BuySListNode(x);
	newnode->next = *pplist;
    *pplist=newnode;
}

头插直接就是插，不用找尾，先申请结点，再next链接头结点，即连到前面，在更新头指针，以方便下一次连接。

IaaS

（*）单链表的尾删

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

}

尾删先找尾，如果头指针为空直接释放，并置指针为空，以防止成为野指针，再把头指针赋给定义的为指针，用while循环找尾部，用tail的下下个结点来判断，如果为空就是放下个结点，并置下个结点为空。

Floyd算法

（*）单链表头删

void SListPopFront(SLTNode** pplist)//单链表头删
{
	    assert(pplist);
	    assert(*pplist != NULL);
		SLTNode* next = (*pplist)->next;
		free(*pplist);
		*pplist = next;
}

先把头指针下个结点地址存放到定义的next指针里面，再释放头指针，最后更新头指针。

python3

（*）单链表查找

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

查找也是一个当前指针发生变化的过程，先把头指针存到定义的cur指针里面，再用while来查找，用if语句来判断，如果找到直接返回cur指针，没有则更新当前指针，遍历下一个。最后都没有返回空。

sed命令使用

（*）单链表在pos位置之前插入x

void SListInsertFront(SLTNode** plist, SLTNode* pos, SLTDateType x)// 单链表在pos位置之前插入x
{
	assert(plist);
	assert(pos);
	if (*plist == pos)
	{
		SListPushFront(plist, x);
	}
	else
	{
		SLTNode* pre = *plist;
		while (pre->next != pos)
		{
			pre = pre->next;
		}
		SLTNode* newnode = BuySListNode(x);
		pre->next=newnode;
		newnode->next = pos;
	}
}

在pos位置之前插入，分两种情况，第一头指针正好是pos，直接调用头插，否则进行二种情况，多个结点：先把头指针存放到定义的前驱指针pre，再用while循环来找pos，不等于pos更新pre继续找，找到之后先申请一个要插入的结点，再用前驱指针pre来链接刚申请的结点，然后申请的结点再链接pos。

jquery

（*）单链表在pos位置之后插入x

void SListInsertAfter(SLTNode * pos, SLTDateType x)//单链表在pos位置之后插入x
{
	    assert(pos);
		SLTNode* newnode = BuySListNode(x);
		SLTNode* next = pos->next;
		pos->next = newnode;
		newnode->next = next;
		
}

这个函数要结合查找函数来用。在这里面先申请结点，再把pos下个结点地址存放到next里面，再用pos来连接刚申请的结点，之后再用刚申请的结点来链接next也即是pos下一个的结点。

图标

（*）删除pos位置之后的值

void SListEraseAfter(SLTNode* pos)//删除pos位置之后的值
{
	assert(pos);
	if (pos == NULL)
	{
		return;
	}
	SLTNode* del = pos->next;
	pos->next = del->next;
	free(del);
	del = NULL;

}

先判断pos是否为空，如是则return终止函数执行，反之先把pos之后的结点地址存到del指针里面，然后直接让pos链接del的下一个结点，再释放掉中间的del。

VMware16

（*）单链表删除pos位置的值

void SListErase(SLTNode** plist, SLTNode* pos)// 单链表删除pos位置的值
{
	assert(plist);
	assert(pos);
	if (*plist == pos)
	{
		free(*plist);
		*plist = NULL;
	}
	else
	{
		SLTNode* pre = *plist;
		while (pre->next!= pos)
		{
			pre = pre->next;
		}
		pre->next = pos->next;
		free(pos);
		pos= NULL;
	}
}

删除pos位置的值，如果头指针刚好是直接释放头指针并置为空，否则，把头指针赋给前驱指针，再用while循环找pos，找到则pre直接链接pos下一个结点，并释放掉中间的pos，并置为空。

selenium

（*）单链表的销毁

void SListDestroy(SLTNode** plist)// 单链表的销毁
{
	assert(plist);
	SLTNode* tail = *plist;
	while (*plist)
	{
		while (tail)
		{
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
	}
}

释放链表，先从尾部进行逐个删除，把头指针赋给定义的尾指针，再用两个while循环来控制，第一层是控制头指针，第二层是控制为尾指针，找到则释放并置为空，然后直到头指针为空则停止。

spidermonkey

（3）函数对比和摒弃

我们需要摒弃单链表在pos位置之前插入x函数和单链表删除pos位置的值函数。
原因和对比：

tomcat

摒弃pos之前插入：因为是单向链表，需要从头遍历查找pos，如果在pos之前插入，找到pos还需要找pos之前的地址，对传参数不友好，所以一般再pos之后插入
摒弃删除pos位置：因为是单向链表，需要从头遍历查找pos，如果删除pos位置，找到pos还需要找pos之前的地址，对传参数不友好，而且这样就少传参数了，所以一般不删除pos，一般删除pos后面的值。

四、单链表实现代码

（1）Slist.c

#include"Slist.h"
SLTNode* BuySListNode(SLTDateType x)//动态申请节点
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}
void SListPrint(SLTNode* plist)//打印链表
{
	SLTNode* cur = plist;
	while (cur)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
void SListPushBack(SLTNode** pplist, SLTDateType x)// 单链表尾插
{
	assert(pplist);
	SLTNode* newnode=BuySListNode(x);
	if (*pplist == NULL)
	{
		*pplist = newnode;
	}
	else
	{
		SLTNode* tail = *pplist;
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}
void SListPushFront(SLTNode** pplist, SLTDateType x)//单链表的头插
{
	assert(pplist);
	SLTNode* newnode = BuySListNode(x);
	newnode->next = *pplist;
    *pplist=newnode;
}
void SListPopBack(SLTNode** pplist)//单链表的尾删
{
	assert(pplist);
	assert(*pplist);
	if (*pplist == NULL)
	{
		free(*pplist);
		*pplist = NULL;
	}
	SLTNode* tail = *pplist;
	while (tail->next->next)
	{
		tail = tail->next;
	}
	free(tail->next);
	tail->next = NULL;

}
void SListPopFront(SLTNode** pplist)//单链表头删
{
	    assert(pplist);
	    assert(*pplist != NULL);
		SLTNode* next = (*pplist)->next;
		free(*pplist);
		*pplist = next;
}
SLTNode* SListFind(SLTNode* plist, SLTDateType x)// 单链表查找
{
	SLTNode* cur = plist;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
void SListInsertFront(SLTNode** plist, SLTNode* pos, SLTDateType x)// 单链表在pos位置之前插入x
{
	assert(plist);
	assert(pos);
	if (*plist == pos)
	{
		SListPushFront(plist, x);
	}
	else
	{
		SLTNode* pre = *plist;
		while (pre->next != pos)
		{
			pre = pre->next;
		}
		SLTNode* newnode = BuySListNode(x);
		pre->next=newnode;
		newnode->next = pos;
	}
}
void SListInsertAfter(SLTNode * pos, SLTDateType x)//单链表在pos位置之后插入x
{
	    assert(pos);
		SLTNode* newnode = BuySListNode(x);
		SLTNode* next = pos->next;
		pos->next = newnode;
		newnode->next = next;
		
}
void SListEraseAfter(SLTNode* pos)//删除pos位置之后的值
{
	assert(pos);
	if (pos == NULL)
	{
		return;
	}
	SLTNode* del = pos->next;
	pos->next = del->next;
	free(del);
	del = NULL;

}
void SListErase(SLTNode** plist, SLTNode* pos)// 单链表删除pos位置的值
{
	assert(plist);
	assert(pos);
	if (*plist == pos)
	{
		free(*plist);
		*plist = NULL;
	}
	else
	{
		SLTNode* pre = *plist;
		while (pre->next!= pos)
		{
			pre = pre->next;
		}
		pre->next = pos->next;
		free(pos);
		pos= NULL;
	}
}
void SListDestroy(SLTNode** plist)// 单链表的销毁
{
	assert(plist);
	SLTNode* tail = *plist;
	while (*plist)
	{
		while (tail)
		{
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
	}
}

（2）Slist.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SLTNode;
SLTNode* BuySListNode(SLTDateType x);// 动态申请一个节点

//SLTNode* CreateSList(int n);//创建链表

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

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


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

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

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

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

void SListInsertFront(SLTNode** plist, SLTNode* pos,SLTDateType x);// 单链表在pos位置之前插入x

void SListInsertAfter(SLTNode * pos,SLTDateType x); //单链表在pos位置之后插入x

void SListEraseAfter(SLTNode* pos);//删除pos位置之后的值

void SListErase(SLTNode** plist, SLTNode* pos);// 单链表删除pos位置的值

void SListDestroy(SLTNode* plist);// 单链表的销毁

（3）test.c

#include"Slist.h"
void test1()
{
	SLTNode* plist = NULL;
	SListPushBack(&plist, 1);//尾插测试
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPrint(plist);

}
void test2()
{
	SLTNode* plist = NULL;
	SListPushFront(&plist, 1);//头插+尾删+头删测试
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 3);
	SListPushFront(&plist, 4);
	SListPopBack(&plist);
	SListPopFront(&plist);
	SListPrint(plist);

}
void test3()
{
	SLTNode* plist = NULL;

	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPrint(plist);

	SLTNode* ret = SListFind(plist, 3);
	if (ret)
	{
		printf("%d\n",ret->data);
	}

	SLTNode* pos = SListFind(plist, 4);
	if (pos)
	{
		SListInsertFront(&plist, pos, 5);
	}
	SListPrint(plist);

	pos = SListFind(plist, 5);
	if (pos)
	{
		SListErase(&plist, pos);
	}
	SListPrint(plist);
}
int main()
{
	test1();//尾插测试
	test2();//头插+尾删+头删测试
	test3();//尾插+查找+在pos位置之前插入x+单链表删除pos位置的值

}

五、单链表测试结果

在这里插入图片描述

安全区

声明：本站博客内容版权均属于原作者所有，这里所提供资源均只能用于参考学习用，书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。

c#c语言开发语言数据结构链表