【数据结构初阶】单链表（附全部码源）

单链表

- 1，单链表的概念及结构
- 2，单链表的实现
- - 2.1初始化内容（所需文件，接口）
  - 2.2申请结点
  - 2.3打印单链表
  - 2.4尾插
  - 2.5头插
  - 2.6尾删
  - 2.7头删
  - 2.8查找
  - 2.9在pos位置之后插入
  - 2.10在pos位置前面插入
  - 2.11删除pos之后的值
  - 2.12删除pos位置的值
  - 2.13销毁链表
- 3.全部码源

1，单链表的概念及结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

现实中数据结构中

2，单链表的实现

2.1初始化内容（所需文件，接口）

所需文件

头文件->SLTNode.h
源文件->test.c
源文件->SLTNode.c

接口（SList.h中）

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

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

//打印单链表
void SLTPrint(SLTNode* phead);

//创造结点
SLTNode* BuySListNode(SLTDateType x);

//尾插
void SLTPushBack(SLTNode** pphead, SLTDateType x);

//头插
void SLTPushFront(SLTNode** pphead, SLTDateType x);

//尾删
void SLTPopBack(SLTNode** pphead);

//头删
void SLTPopFront(SLTNode** pphead);

//查找
SLTNode* FindSLTNode(SLTNode* phead, SLTNode* pos);

//pos位置插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);

//pos位置之后插入
void SLTInsertAfter(SLTNode* pos, SLTDateType x);

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

//删除pos位置下一个
void SLTEraseAfter(SLTNode* pos);

//销毁单链表
void SLTDestroy(SLTNode* phead);

2.2申请结点

//创造结点
SLTNode* BuySListNode(SLTDateType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->date = x;
	newnode->next = NULL;
	return newnode;
}

2.3打印单链表

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

2.4尾插

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

2.5头插

头插显然是要改变头指针存放的地址，因此形参也需要传递二级指针。头插无需单独考虑空链表的情况

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

2.6尾删

尾删先要遍历一遍链表找到最后一个节点将其释放掉，还要找到倒数第二个节点将它的指针域中存的地址改为NULL。所以定义两个指针让他们同时去遍历链表，一个找尾，另一个找倒数第二个节点。需要注意的是空链表和只有一个节点的链表的情况，空链表无法进行尾删，而只有一个节点的链表在尾删后会变成一个空链表，这意味着要改变头指针里面存放的地址，所以尾删形参也要传递二级指针。

//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(*pphead);

	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* tailPrev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next)
		{
			tailPrev = tail;
			tail = tail->next;
		}
		free(tail);
		tailPrev->next = NULL;
		/*SLTNode* tail = *pphead;
		while (tail->next->next)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;*/
	}
}

2.7头删

头删很明显需要改变头指针中存放的地址，所以形参仍然需要传递二级指针。头删只需要注意链表是否为空，空链表无法进行删除。此外在进行头删的时候记得将原来的头节点释放掉，因此在改变头节点之前需要先保留原来头结点的地址，否则在更换完新的头节点后就找不到原来的头节点了。

//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);

	assert(*pphead);

	SLTNode* newnode = (*pphead)->next;
	free(*pphead);
	*pphead = newnode;
}

2.8查找

其实就是遍历一遍链表，但是只能返回第一次出现的地址。查找可以当修改来使用，我们查找到节点的地址后就可以通过地址去修改数据域中存储的数据。

//查找
SLTNode* FindSLTNode(SLTNode* phead, SLTDateType x)
{
	
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->date == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}

2.9在pos位置之后插入

先让newnode的指针域存储pos后一个节点的地址，再让pos的指针域存newnode的地址

//在pos位置之后插入
void SLTInsertAfter(SLTNode* pos, SLTDateType x)
{
	SLTNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;

	//err 死循环
	//pos->next = newnode;
	//newnode->next = pos->next;
}

2.10在pos位置前面插入

和尾插类似，但此时只需要遍历链表找到pos位置的前一个节点即可，同样需要注意pos是头结点的情况，此时就成头插了，需要改变头指针中存的地址，因此函数的形参需要传二级指针。

//在pos位置插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
	assert(*pphead);
	assert(pos);

	if (*pphead == pos)
	{
		//头插
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuySListNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

2.11删除pos之后的值

注意不能写成后面这样：pos->next = pos->next->next。这样写虽然把pos位置后面的节点从链表中剔除出去了，但并没有真正意义上的实现删除，因为每一个节点都是通过malloc在堆上申请的，不使用的时候要主动的去释放掉，也就是free掉，把这块空间归还给操作系统，否则会导致内存泄漏。而上面那样写，就会导致pos后面的节点丢失，无法进行释放，正确的做法是在执行这条语句之前把pos后边节点的地址先保存起来。

void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);
	//检查pos是不是尾结点
	assert(pos->next);

	SLTNode* posNext = pos->next;

	pos->next = posNext->next;
	free(posNext);
	posNext = NULL;
}

2.12删除pos位置的值

pos可能是头结点的地址，因此形参要用二级指针。

void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead);
	assert(pos);

	if (pos == *pphead)
	{
		SLTPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}

2.13销毁链表

void SListDestroy(SLTNode* plist)
{
	assert(plist);
	SLTNode* cur = plist;
	while (cur)
	{
		SLTNode* pur = cur;
		cur = cur->next;
		free(pur);
	}
}

3.全部码源

SLTNode.c

#include"SLTNode.h"

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

//创造结点
SLTNode* BuySListNode(SLTDateType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->date = x;
	newnode->next = NULL;
	return newnode;
}

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

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

//尾删
void SLTPopBack(SLTNode** pphead)
{
	assert(*pphead);

	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* tailPrev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next)
		{
			tailPrev = tail;
			tail = tail->next;
		}
		free(tail);
		tailPrev->next = NULL;
		/*SLTNode* tail = *pphead;
		while (tail->next->next)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;*/
	}
}

//头删
void SLTPopFront(SLTNode** pphead)
{
	assert(pphead);

	assert(*pphead);

	SLTNode* newnode = (*pphead)->next;
	free(*pphead);
	*pphead = newnode;
}

//查找
SLTNode* FindSLTNode(SLTNode* phead, SLTDateType x)
{
	
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->date == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}

//在pos位置插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x)
{
	assert(*pphead);
	assert(pos);

	if (*pphead == pos)
	{
		//头插
		SLTPushFront(pphead, x);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLTNode* newnode = BuySListNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

//在pos位置之后插入
void SLTInsertAfter(SLTNode* pos, SLTDateType x)
{
	SLTNode* newnode = BuySListNode(x);
	newnode->next = pos->next;
	pos->next = newnode;

	//err 死循环
	//pos->next = newnode;
	//newnode->next = pos->next;
}

//删除pos位置
void SLTErase(SLTNode** pphead, SLTNode* pos)
{
	assert(*pphead);
	assert(pos);

	if (pos == *pphead)
	{
		SLTPopFront(*pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
		//pos
	}
}

//删除pos下一个位置
void SLTEraseAfter(SLTNode* pos)
{
	assert(pos);

	//检查pos是不是尾结点
	assert(pos->next);

	SLTNode* posNext = pos->next;
	pos->next = posNext->next;
	free(posNext);
	posNext = NULL;
}

//销毁单链表
void SLTDestroy(SLTNode* phead)
{
	assert(phead);
	SLTNode* cur = phead;
	while (cur)
	{
		SLTNode* pur = cur;
		cur = cur->next;
		free(pur);
	}
}

SLTNode.h

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

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

//打印单链表
void SLTPrint(SLTNode* phead);

//创造结点
SLTNode* BuySListNode(SLTDateType x);

//尾插
void SLTPushBack(SLTNode** pphead, SLTDateType x);

//头插
void SLTPushFront(SLTNode** pphead, SLTDateType x);

//尾删
void SLTPopBack(SLTNode** pphead);

//头删
void SLTPopFront(SLTNode** pphead);

//查找
SLTNode* FindSLTNode(SLTNode* phead, SLTNode* pos);

//pos位置插入
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDateType x);

//pos位置之后插入
void SLTInsertAfter(SLTNode* pos, SLTDateType x);

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

//删除pos位置下一个
void SLTEraseAfter(SLTNode* pos);

//销毁单链表
void SLTDestroy(SLTNode* phead);

test.c

#include"SLTNode.h"

void SLTNodeTest1()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPrint(plist);
	SLTPushBack(&plist, 2);
	SLTPrint(plist);
	SLTPushBack(&plist, 3);
	SLTPrint(plist);
	SLTPushBack(&plist, 4);
	SLTPrint(plist);
	SLTPushBack(&plist, 5);
	SLTPrint(plist);
	SLTPushBack(&plist, 6);
	SLTPrint(plist);
}

void SLTNodeTest2()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);

	SLTPushFront(&plist, 200);
	SLTPrint(plist);
}

void SLTNodeTest3()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);

	SLTPopBack(&plist);
	SLTPrint(plist);

	SLTPopBack(&plist);
	SLTPrint(plist);

	SLTPopBack(&plist);
	SLTPrint(plist);

	SLTPopBack(&plist);
	SLTPrint(plist);
}

void SLTNodeTest4()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);

	SLTPopFront(&plist);
	SLTPrint(plist);

	SLTPopFront(&plist);
	SLTPrint(plist);

	SLTPopFront(&plist);
	SLTPrint(plist);

	SLTPopFront(&plist);
	SLTPrint(plist);
}
void SLTNodeTest5()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);

	SLTNode* pos = FindSLTNode(plist, 3);
	SLTInsert(&plist, pos, 30);

	SLTPrint(plist);
}

void SLTNodeTest6()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);

	SLTNode* pos = FindSLTNode(plist, 3);
	SLTInsertAfter(pos, 30);

	SLTPrint(plist);
}

void SLTNodeTest7()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);

	SLTNode* pos = FindSLTNode(plist, 3);
	SLTErase(&plist, pos);

	SLTPrint(plist);
}

void SLTNodeTest8()
{
	SLTNode* plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);

	SLTNode* pos = FindSLTNode(plist, 3);
	SLTEraseAfter(pos);

	SLTPrint(plist);
}


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

💘不知不觉，【数据结构初阶】单链表以告一段落。通读全文的你肯定收获满满，让我们继续为数据结构学习共同奋进!!!

文章出处登录后可见！

已经登录？立即刷新