博客

【数据结构】单链表(线性表)的实现

  • Post author:
  • Post category:其他


目录


一、什么是链表


二、单链表的实现


1、动态申请一个结点


2、单链表打印


3、单链表尾插


4、单链表的尾删


5、单链表的头插


6、单链表头删


7、单链表查找


8、单链表在pos位置之后插入x


9、单链表删除pos位置之后的值


10、单链表在pos位置之前插入x


11、单链表删除pos位置的值


12、销毁链表


三、源代码


1、SList.h


2、SList.c


3、test.c

一、什么是链表

链表是一种

物理存储结构上非连续

、非顺序的存储结构，数据元素的

逻辑顺序

是通过链表中的

指针链接

次序实现的 。

单链表的声明如下： 

//声明单链表
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;


链表的逻辑结构：


链表的物理结构：


注意：

1、从上图可看出，链式结构在逻辑上是连续的，但是在物理上不一定连续。

2、现实中的结点一般都是从堆上申请出来的。

3、从堆上申请空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续。

假设在32位系统上，结点中值域为int类型，则一个节点的大小为8个字节，则也可能有下述链表：

每个链表都是由一节节的链结组成的，我们称之为

节点

。其中，每一个节点都是由两部分组成的，存储数据的部分叫做

数据域

，存储地址的部分叫做

指针域

。指向第一个节点的指针称之为

头指针

。

二、单链表的实现

1、动态申请一个结点

在链表中插入一个数据，首先需要先动态申请一个结点，并将该结点的数值域与指针域进行赋值，指针域都设置为NULL。 

//动态申请一个节点
SLTNode* BuySLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

2、单链表打印

在这里我的思路是用while循环将链表遍历一遍，从首个结点开始移动，直到NULL结束。 

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

3、单链表尾插

尾插就需要我们先动态开辟一个新的节点 。然后让前面的指针指向新的节点。但是要分两种情况如下图所示：

因为链表为NULL时，plist指针指向的是空，此时不能进行解引用操作，所以如果为NULL时，直接进行赋值就行。当链表不为空时，直接在后面进行尾插。


注意：

在这里使用的是二级指针，因为需要改变结构体里面的数值，而头指针是一个结构体类型的指针，而指针也是一种变量。假设我们用的是一级指针，当链表为空，我们进行尾插的时候，我们会将头指针内的数据改为新节点的地址。我们可以找到，一级指针的传递方式不会引起实参的变化。因此，当此函数结束后，我们的头指针依旧是空。因此，我们这里需要传入的是二级指针，从而实现地址传递。 

//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySLTNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		//找尾
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

4、单链表的尾删

在这里首先要要声明一下，保证链表不为空，然后再分两种情况：(1)如果链表长度大于1时，只需要将倒是第二个节点的指针域设置为空指针，并且将最后一个节点释放掉。(2)如果链表长度为1时，只需将头指针置空，第一个节点释放掉就行。 

//单链表尾删
void SLTPopBack(SLTNode** pphead)
{
	//暴力的检查
	assert(*pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next->next)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}	
}

5、单链表的头插

头插也是先要开辟一个新的节点，然后直接让新节点的next链接到头节点上，最后重新更新一下头节点。 

//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

6、单链表头删

头删首先还是要声明一下，保证链表不为空，然后保存头指针指向指针域中所对的地址空间，最后释放头节点即可。 

//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(*pphead);
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

7、单链表查找

直接用while循环将链表遍历一遍。注意返回值返回的是空指针或者所查元素的地址。 

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		else
			cur = cur->next;
	}
	return NULL;
}

8、单链表在pos位置之后插入x

在pos位置之后插入x时，pos位置所对的节点的指针域中就记录了后面的节点位置。因此可以直接插入x所对应的节点。 

//在pos之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

9、单链表删除pos位置之后的值

在删除pos位置之后的节点时，如果pos->next为空时，说明pos位置就是最后一个节点，它的后面已经没有节点了，所以直接返回即可，如果pos->next不为空时，要保存住这个位置，然后重新链接pos->next = pos->next->next(就相当于下面代码中pos->next = nextNode->next)，最后释放pos->next。 

//删除pos之后的值
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	if (pos->next == NULL)
	{
		return;
	}
	else
	{
		SLTNode* nextNode = pos->next;
		pos->next = nextNode->next;
		free(nextNode);
	}
}

10、单链表在pos位置之前插入x

在pos位置前面插入新的节点，分两种情况：(1)如果pos的位置就是头节点时，就相当于头插。(2)如果pos位置不是头节点时，要找到pos位置原链表的前方的节点。然后让该节点指向所插入的节点，然后让所插入的节点指向pos所对的节点。 

//在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pos);
	if (*pphead == pos)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuySLTNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

11、单链表删除pos位置的值

删除pos位置的节点，分两种情况：(1)如果pos的位置就是头节点时，就相当于头删。(2)如果pos的位置不是头节点时，先保存pos位置后面的节点，然后让该节点链接pos位置之前的节点，最后再释放掉pos位置的节点。 

//删除pos位置的数据
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pos);
	if (pos == *pphead)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}

12、销毁链表

销毁链表的时候，我们不能简单只释放头指针。这样是没有将空间完全释放掉的，这只是释放了头节点。所以可以设置一个指针cur，让它用while循环将链表从头到尾都释放一遍，最后将头指针设置为空。

一定要将头指针设置为空指针！否则会出现野指针的问题！
 

//销毁
void SLTDestroy(SLTNode** pphead)
{
	SLTNode* cur = *pphead;
	while (cur)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

三、源代码

1、SList.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>


typedef int SLTDataType;

//声明单链表
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

//动态申请一个节点
SLTNode* BuySLTNode(SLTDataType x);
//创建循环节点
SLTNode* CreateSList(int n);
//打印链表
void SLTPprint(SLTNode* phead);
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);

//尾插尾删
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
//头插头删
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopFront(SLTNode** pphead);


//在pos之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos之后的值
void SLTEraseAfter(SLTNode* pos);

//在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);

//删除pos位置的数据
void SLTErase(SLTNode** pphead, SLTNode* pos);

//销毁
void SLTDestroy(SLTNode** pphead);

2、SList.c

#include "SList.h"

//动态申请一个节点
SLTNode* BuySLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	return newnode;
}

//创建循环节点
SLTNode* CreateSList(int n)
{
	SLTNode* phead = NULL, * ptail = NULL;
	for (int i = 0; i < n; i++)
	{
		SLTNode* newnode = BuySLTNode(i);
		if (phead == NULL)
		{
			ptail = phead = newnode;
		}
		else
		{
			ptail->next = newnode;
			ptail = newnode;
		}
	}
	return phead;
}

//打印链表
void SLTPprint(SLTNode* phead)
{
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		//printf("[%d | %p]->", cur->data, cur->next);
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}
//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySLTNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		//找尾
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}
void SLTPopBack(SLTNode** pphead)
{
	//暴力的检查
	assert(*pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next->next)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;
	}	
}
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(*pphead);
	SLTNode* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		else
			cur = cur->next;
	}
	return NULL;
}

//在pos之后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);
	SLTNode* newnode = BuySLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

//在pos之前插入x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pos);
	if (*pphead == pos)
	{
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuySLTNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

//删除pos之后的值
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	if (pos->next == NULL)
	{
		return;
	}
	else
	{
		SLTNode* nextNode = pos->next;
		pos->next = nextNode->next;
		free(nextNode);
	}
}

//删除pos位置的数据
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pos);
	if (pos == *pphead)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}

//销毁
void SLTDestroy(SLTNode** pphead)
{
	SLTNode* cur = *pphead;
	while (cur)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}

3、test.c

TestSList1()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPushBack(&plist, 5);
	SLTPprint(plist);

	SLTPopBack(&plist);
	SLTPprint(plist);
	
	SLTPushFront(&plist, 100);
	SLTPushFront(&plist, 200);
	SLTPprint(plist);

	SLTPopFront(&plist);
	SLTPprint(plist);

	SLTNode* p = SLTFind(plist, 2);
	SLTInsertAfter(p, 30);
	SLTPprint(plist);

	p = SLTFind(plist, 1);
	SLTEraseAfter(p);
	SLTPprint(plist);
	SLTDestroy(&plist);

}
int main()
{
    TestSList1();
	return 0;
 }



本文要是有不足的地方，欢迎大家在下面评论，我会在第一时间更正。



老铁们，记着点赞加关注哦!!!



版权声明：本文为m0_63198468原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。