单链表的实现

前言

本问介绍了单链表的定义，结构，功能以及优化等内容。

---

一.单链表的定义

单链表是一种链式存储的数据结构，其逻辑结构为：一对一

---

二.单链表的结构

单链表结构图：

结构体代码：

//定义信息
typedef struct UsrInfo
{
   
	int id;//编号
	char name[SIZE];
}data_t;

//定义单链表的节点
typedef struct Node
{
   
	data_t data;//数据域
	struct Node *pNext;
}Node;

typedef struct sLink
{
   
	Node *pHead;//指向第一个结点的首地址
	int count;//结点数
}sLink;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

---

三.单链表的常用功能

1.创建单链表头

//创建单链表头
sLink *creatSLink()
{
   
	sLink *pLink = (sLink *)malloc(sizeof(sLink));
	if(NULL == pLink)
	{
   
		return NULL;
	}
	memset(pLink, 0, sizeof(sLink));
	return pLink;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2.创建单链表节点

//创建单链表节点
Node *creatSLinkNode(data_t data)
{
   
	Node * pNode = (Node *)malloc(sizeof(Node));
	if(NULL == pNode)
	{
   
		return NULL;
	}
	memset(pNode, 0, sizeof(Node));
	pNode->data = data;
	return pNode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3.头部插入节点

//头部插入节点
int pushItemFront(sLink *pLink, data_t data)
{
   
	if(NULL == pLink)
	{
   
		return LINK_ERROR; 
	}
	//创建一个节点
	Node *pNode = creatSLinkNode(data);
	//将新的节点插入头部
	pNode->pNext = pLink->pHead;
	pLink->pHead = pNode;
	pLink->count++;
	return LINK_OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

4.尾部插入节点

//尾部插入节点
int pushItemBack(sLink *pLink, data_t data)
{
   
	if(NULL == pLink)
	{
   
		return LINK_ERROR;
	}
	//创建一个节点
	Node *pNode = creatSLinkNode(data);
	//将新的节点插入尾部
	Node *pTmp = pLink->pHead;
	int i;
	for(i = 0; i < pLink->count-1; i++)
	{
   //遍历到最后一个节点
		pTmp = pTmp->pNext;
	}
	pTmp->pNext = pNode;
	pLink->count++;
	return LINK_OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

5.中间插入节点

//中间插入节点
int insertItemLink(sLink *pLink, int iOffset, data_t data)
{
   
	if(NULL == pLink || iOffset < 0 || iOffset > pLink->count)
	{
   
		return LINK_ERROR;
	}
	if(0 == iOffset)
	{
   //如果插入的值等于0时，调用头插入函数
		pushItemFront(pLink,data);
		return LINK_OK;
	}else if(iOffset == pLink->count)
	{
   //如果插入的值等于count时，调用尾部插入函数
		pushItemBack(pLink,data);
		return LINK_OK;
	}
	//创建一个节点
	Node *pNode = creatSLinkNode(data);
	//将节点插入到ioffset位置
	Node *pTmp = pLink->pHead;
	int i;
	for(i = 0; i < iOffset-1; i++)
	{
   
		pTmp = pTmp->pNext;
	}
	pNode->pNext = pTmp->pNext;
	pTmp->pNext = pNode;
	pLink->count++;
	return LINK_OK;	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

6.头部删除节点

//头部删除节点
int deleteItemFront(sLink *pLink)
{
   
	if(NULL == pLink)
	{
   
		return LINK_ERROR;
	}
	Node *pTmp = pLink->pHead;
	pLink->pHead = pTmp->pNext;
	free(pTmp);
	pTmp = NULL;
	pLink->count--;

	return LINK_OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

7.尾部删除节点

//尾部删除节点
int deleteItemLink(sLink *pLink, int iOffset)
{
   
	if(NULL == pLink || iOffset != pLink->count)
	{
   
		return LINK_ERROR;
	}
	//用pTmp找到要删除的前一个节点
	Node *pTmp = pLink->pHead;
	int i;
	for(i = 0; i < pLink->count-1; i++)
	{
   
		pTmp = pTmp->pNext;
	}
	pTmp->pNext = NULL;
	pDel = NULL;
	pLink->count--;
	return LINK_OK;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

8.中间删除节点

//中间删除节点
int deleteItemLink(sLink *pLink, int iOffset)
{
   
	if(NULL == pLink || iOffset < 0 || iOffset >= pLink->count)
	{
   
		return LINK_ERROR;
	}
	if(0 == iOffset)
	{
   //删除头部节点
		deleteItemFront(pLink);
		return LINK_OK;
	}
	//用pTmp找到要删除的前一个节点
	Node *pTmp = pLink->pHead;
	int i;
	for(i = 0; i < iOffset-1; i++)
	{
   
		pTmp = pTmp->pNext;
	}
	Node *pDel = pTmp->pNext;
	pTmp->pNext = pDel->pNext;
	free(pDel);
	pDel = NULL;
	pLink->count--;
	return LINK_OK;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

9.查找第一次节点出现的数据

//查找第一次节点出现的数据
int findItemLink(sLink *pLink, data_t *data)
{
   
	if(NULL == pLink)
	{
   
		return LINK_ERROR;
	}
	//遍历链表，找到与data数据相符的节点，并将数据带出去
	Node *pTmp = pLink->pHead;
	int i;
	for(i = 0; i < pLink->count; i++)
	{
   
		if(pTmp->data.id == data->id)
		{
   
			strcpy(data->name,pTmp->data.name);
			return LINK_OK;
		}
		pTmp = pTmp->pNext;
	}
	return NOT_FUND;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

10.更新节点数据

//更新节点数据
int updateItemLink(sLink *pLink, data_t data)
{
   
	if(NULL == pLink)
	{
   
		return LINK_ERROR;
	}
	//根据id查找节点并修改节点name值
	Node *pTmp = pLink->pHead;
	while(pTmp != NULL)
	{
   
		if(pTmp->data.id == data.id)
		{
   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16