单链表的学习与基础运用p

当我们在实际做项目,或者是自主开发一点小东西的时候,往往会储存一些数据,有时候我们需要添加这些数据,有时候需要删除,而有时候,仅仅只需要查找到就行。链表中的每一个节点都是一个独立开辟的空间,就像一个个的小箱子。那我们要如何将这些箱子串联起来呢?这时候,链表就发挥了作用。一个最基本的节点,应当如下图组成

typedef char x;
typedef struct SlistNote SlistNote;

struct SlistNote
{
	x data;
	SlistNote* next;
};

因为我们可能需要不断的改变数据的类型,所以在最初我们利用typedef来进行重定义。并且因为结构体指针每次创建名都太长,索性直接将名字进行替换

而上图最重要的,其实是结构体中的内容:1.数据。在这个节点中存放着相应的数据  2.指向下一个节点的地址。如上图的next,便是指向下一个节点的地址。

因此,当我们想使用一个链表的时候,我们其实只要找到第一个节点的地址就可以了。

那么,我们要如何实现链表的初始化,前插后插,前删后删,查询,定点操作呢?让我们一个一个来。

初始化

SListNote* SltBuyNote(SLT_type x)
{
	SListNote* newnote = (SListNote*)malloc(sizeof(SListNote));
	assert(newnote);
	newnote->data = x;
	newnote->next = NULL;
	return newnote;
}

我们想要实现尾插和头插,需要先把要插入的节点准备好。以上代码,便是数据的初始化过程。先开辟出一片空间,并将这个空间的地址赋值给newnote这个指针。接着进行assert,避免前面的开辟空间失败进而导致后续的一系列错误。接着将数据进行赋值,暂时先把next指针定义为空指针,防止变成野指针,接着将刚刚创建的这个指针给return了。

尾插

void BackInsert(SListNote** pphead, SLT_type x)
{
	SListNote* newnote = SltBuyNote(x);
	if (*pphead == NULL)
	{
		*pphead = newnote;
	}
	else
	{
		SListNote* ppend = *pphead;
		while (ppend->next)
		{
			ppend = ppend->next;
		}
		ppend->next = newnote;
	}
}

当我们知道如何初始化节点以后,我们便可以开始一些基本的操作,比如尾插。在最开始,我们先创建出一个节点newnote,这个节点内部的数据就是我们要插入的数据。接着,我们判断一下被插入的节点的是否为空,若为空,则直接将newnote设置为初始节点,若不为空,那便先通过while循环找到ppend,也就是该结构体的末端。接着让结构体末端的next指针指向newnote,那便完成了尾插。

头插

void FrontInsert(SListNote** pphead, SLT_type x)
{
	SListNote* newnote = SltBuyNote(x);
	if (*pphead == NULL)
	{
		*pphead = newnote;
	}
	else
	{
		newnote->next = *pphead;
		*pphead = newnote;
	}
}

头插相比较于尾插要更简单一些,前面基本相似,在else这边,我们只需要把新节点的next指针指向*pphead,那其实就已经插上了。但是这样有一些错误,因为此时链表的头部已经发生改变,变成了newnote,因此,我们需要手动把节点地址改为newnote地址。

头删

void FrontDel(SListNote** pphead)
{
	assert(pphead && *pphead);

	SListNote* pcur = *pphead;
	if (pcur->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	SListNote* pcur = *pphead;
	*pphead = pcur->next;
	free(pcur);
}

头删也是比较简单的,在头删函数中,我们首先需要先判断到底有没有数据,利用assert函数完成,如果有,再判断有几个数据,如果只有一个,那便是将头地址给删除,如果多于一个,那就将原先的头地址赋给一个值做备份,接着将头地址改变为下一个节点地址,再释放掉之前的头地址,即可完成头删。

尾删

void BackDel(SListNote** pphead)
{
	assert(pphead && *pphead);

	SListNote* pcur = *pphead;
	if (pcur->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		while (pcur->next->next)
		{
			pcur = pcur->next;
		}
		free(pcur->next);
		pcur->next->next = NULL;
		pcur->next = NULL;
	}

尾删前面几部类似于头删,如果已经确定有大于1个的数据,那就利用while精确定位到最后一个数据处,接着释放掉最后一个数据的地址并赋NULL值。

指定位置删除

void PosDel(SListNote** pphead, int pos)
{
	int count = 0;
	SListNote* pcur = *pphead;
	assert(pphead && *pphead);
	if (pos == 0)
	{
		FrontDel(pphead);
	}
	else
	{
		while (pcur)
		{
			pcur = pcur->next;
			count++;
		}
		pcur = *pphead;
		count = 0;
		while (count < pos - 1)
		{
			pcur = pcur->next;
			count++;
		}
		SListNote* ppos = pcur->next;
		pcur->next = pcur->next->next;
		free(ppos);
		ppos = NULL;
	}
}

我们先断言待删链表不是空链表,接着看待删位置是不是首节点,如果是首节点,那么直接执行头删,如果不是,则接着进行下一步。通过while循环找到pos位置处的节点,接着将这个节点的上一个节点的next指针连接到pos位置的下一个节点,接着删除pos位置处的节点,将其free掉。

指定位置插入

指定位置插入分为前插和后插,不同的插入方式需要不同的代码来实现

前插:

void FrontPosInsert(SListNote** pphead, int pos, SLT_type x)
{
	SListNote* newnote = SltBuyNote(x);
	if (*pphead == NULL)
	{
		*pphead = newnote;
	}
	else
	{
		if (pos == 0)
		{
			FrontInsert(pphead, x);
		}
		else
		{
			SListNote* pcur = *pphead;
			int count = 0;
			while (count != pos-1)
			{
				pcur = pcur->next;
				count++;
				if (pcur == NULL)
				{
				printf("不在可执行范围内!");
				return 0;
				}

			}
				SListNote* ppos = pcur->next;
				pcur->next = newnote;
				newnote->next = ppos;
		}
	}
}

先创建一个节点newnote,接着判断链条是否为空链条,若是空链条,则将*pphead直接赋一个newnote,若不是,则开始判断pos的数值,若pos为0的话,那么就执行前插函数,若pos不为0,则在进行下一步。先找到pos所代表的节点的前一个节点,接着继续判断,若该节点已经超过已有的节点,则进行提醒并直接返回,当然,你也可以选择进行一次后插。若该pos符合以上规则,则开始进行插入。

后插

void BackPosInsert(SListNote** pphead, int pos, SLT_type x)
{
	SListNote* newnote = SltBuyNote(x);
	if (*pphead == NULL)
	{
		*pphead = newnote;
	}
	else
	{
		SListNote* pcur = *pphead;
		int count = 0;
		while (count != pos)
		{
			pcur = pcur->next;
			count++;
			if (pcur == NULL)
			{
				printf("不在可执行范围内!");
				return 0;
			}
		}
		SListNote* ppos = pcur->next;
		pcur->next = newnote;
		newnote->next = ppos;
	}
}

尾插与头插大体相似,在一些细节处略微改动,例如在后续找pos位置时,我们找到的是pos的位置,而之前是找到pos前面一个节点,这方面略有不同。其他大体相同。

查找节点

void Finding(SListNote** pphead, SLT_type x)
{
	assert(pphead && *pphead);
	SListNote* pcur = *pphead;
	int count = 0;
	while (pcur)
	{
		if (pcur->data == x)
		{
			printf("找到了!在%d处\n", count);
			return;
		}
		count++;
		pcur = pcur->next;
	}
	printf("没找到");
}

查找节点并不难,用到的方法和之前许多代码相似,可大致看看上图。

摧毁链表

void Sli_destory(SListNote** pphead)
{
	assert(pphead && *pphead);
	SListNote* pcur = *pphead;
	while (pcur)
	{
		SListNote* next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;

首先我们也还是先断言一下节点地址的存在性,接着从头到尾一个节点一个节点的去删除,为了方便显示,我在最后又让首节点显示了个NULL,已证明已经删除完成。

相关推荐

  1. 学习基础运用p

    2024-07-10 20:10:03       14 阅读
  2. 2024-07-10 20:10:03       12 阅读
  3. 通讯录(基于

    2024-07-10 20:10:03       15 阅读
  4. 删除

    2024-07-10 20:10:03       45 阅读

最近更新

  1. Redis和mysql如何保持数据一致?

    2024-07-10 20:10:03       0 阅读
  2. 达梦数据库DM8-mysql迁移后字符串长度问题

    2024-07-10 20:10:03       0 阅读
  3. pip简介与工作原理

    2024-07-10 20:10:03       0 阅读

热门阅读

  1. 如何正确使用Redisson实现分布式锁

    2024-07-10 20:10:03       8 阅读
  2. 开源软件项目的崛起:机遇、挑战与个人成长

    2024-07-10 20:10:03       6 阅读
  3. Electron 跨平台桌面应用开发工具

    2024-07-10 20:10:03       8 阅读
  4. 【linux】linux的特殊符号

    2024-07-10 20:10:03       7 阅读
  5. Rust:常见 GUI 框架

    2024-07-10 20:10:03       8 阅读
  6. 【C++ 】中类的成员函数和析构函数的作用

    2024-07-10 20:10:03       7 阅读
  7. HTTP与HTTPS详解及其请求与响应报文的查看方法

    2024-07-10 20:10:03       12 阅读
  8. Postgres 与 MapLibre 实时位置共享

    2024-07-10 20:10:03       8 阅读
  9. NestJs实现各种请求与参数解析

    2024-07-10 20:10:03       9 阅读