C/C++数据结构---顺序表---链式存储结构2（不带头节点）-Toy模板网

这篇具有很好参考价值的文章主要介绍了C/C++数据结构---顺序表---链式存储结构2（不带头节点）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

个人主页：仍有未知等待探索_数据结构,小项目,洛谷刷题-CSDN博客

专题分栏：数据结构_仍有未知等待探索的博客-CSDN博客

前一篇链接：数据结构---顺序表---链式存储结构1（不带头节点）_仍有未知等待探索的博客-CSDN博客

一、前言

二、链表的基本操作

1.增加数据（增加节点）

1）思路

2）代码呈现

2.删除节点

1）思路

2）代码实现

3.改节点数据

1）思路

2）代码实现

4.查找数据

1)思路

2）代码实现

三、总结

一、前言

根据上一篇的讲解，想必大家已经能够自己创建和初始化链表了。但是对于链表来说，这些操作还不能够完成一些功能，不足以把它应用到一些场景中。接下来还需要实现对链表的增、删、改、查等操作，来让链表能够更方便我们使用。这两次讲的链表才是最基础的单链表，接下来还有双向链表，循环链表等，再学这些之前要打牢基础。

解释一个操作，问：为什么要给节点开辟空间以及什么时候应该开辟空间？（这也是我最近刚弄明白的，如果理解有误，请指出来，共同进步。）答：指针再内存中只占4/8字节（与电脑有关），指针只能存地址，所以指针里面没法存节点的数据域和指针域。所以需要开辟空间来给数据域和指针域存放数据。

二、链表的基本操作

1.增加数据（增加节点）

1）思路

老样子我们先捋思路，怎么进行增加节点的操作呢？

首先要有一个链表（仅有头指针head也行），然后要有一个待插入的节点p和具体的位置。

当找到位置P的时候，还需要考虑是插在P位置的前面还是后面，最后就开始进行插入操作了。如何插入呢？当head为空的时候能不能正常的进行这个操作呢？

将p节点插入如上链表中，无非就是上图所画的，把序号3黑线给断掉，然后把序号1和序号2的两条蓝线连上即可，（是不是head为空的时候也适用呢？等写代码的时候再来验证），那现在还有一个问题，是先连序号1的线还是序号2的线呢？那就假如先连序号1的线，就需要把序号3的黑线断掉然后连上序号1的线，当想连序号2的线的时候，发现连不上，因为之前序号3指向的节点的地址找不着了。

最后，根据推演，就先连序号2再连序号1.

2）代码呈现
List ListAdd(List head,int X,Position P)
{
	//前插
	List r = head,q;
	q = (List)malloc(sizeof(struct LNode));
	q->next = NULL;
	q->data = X;
	if (r == NULL)
	{
		r = q;
		return head;
	}
	while (r!=NULL)
	{
		if (r->next == P)
		{
			q->next = P;
			r->next = q;
			return head;
		}
		r = r->next;
	}
	return NULL;
}
head为空的时候，对上述的步骤是没影响。但是上述代码中要寻找需要插入的位置，需要找到要插入位置的前一个节点，遍历的时候需要用到其指针域，如果head为空的话，head->next将越界，所以需要把head是否为空给讨论出来。

上面写的是再给出数据的前面插入数据，那如何后插呢？答：后插可以再前插的基础上把插入节点的数据和具体位置的节点的数据进行交换，是不是就相当于执行了后插操作呢。

2.删除节点

1）思路

删除节点，也需要一个具体的删除的位置，只要将要删除的前一个节点的指针域指向要删除的后一个节点是不是就相当于直接把要删除的节点给跳过去了，最后要注意的是用free函数把要删除的节点的空间给释放掉。

2）代码实现

List ListDelete(List head, Position P)
{
	List r = head;
	if (r == NULL)
	{
		printf("链表为空，无需删除数据\n");
		return NULL;
	}
	while (r != NULL)
	{
		if (r->next == P)
		{
			if (P->next == NULL)//判断是否P为链表的最后一个
			{
				r->next = NULL;
			}
			else
			{
				r->next = P->next;
			}
			free(P);//释放P的空间
			return head;
		}
        r = r->next;
	}
	printf("未找到\n");
	return NULL;
}

3.改节点数据

1）思路

该节点数据最主要的是找到节点，然后再该节点里面的数据。

2）代码实现

List ListChange(List head, Position P)
{
	if (head == NULL)
	{
		printf("此链表为空\n");
		return NULL;
	}
	else
	{
		List r = head;
		while (r != NULL)
		{
			if (r == P)
			{
				int data;
				scanf("%d", &data);
				P->data = data;
				return head;
			}
			r = r->next;
		}
		printf("未找到\n");
		return NULL;
	}
}

这些功能都不算太难，只需要把每种情况都考虑全面了。

4.查找数据

1)思路

遍历，然后一个一个把节点的数据与查找的数据相比，然后输出结果。

2）代码实现

List ListSearch(List head, int data)
{
	List r = head;
	if (r == NULL)
	{
		printf("此为空链表，未找到\n");
		return NULL;
	}
	else
	{
		while (r->data == data)
		{
			printf("找到了\n");
			return r;
		}
		printf("未找到\n");
		return NULL;
	}
}