数据结构——单链表

链表

1.链表的定义

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

链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。相比于线性表顺序结构，操作复杂。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。

2.链表的分类

链表有很多种不同的类型：单向链表，双向链表以及循环链表。

3.单链表

3.1 单链表的定义

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

单链表有一个数据域和一个指针域，那么在定义结点的时候，我们需要对这两方面的内容均进行定义。要注意的是，指针域指向的是一个结构体，而非指向数据域，所以我们需要定义一个结构体指针！定义代码如下：

typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

3.2 单链表的函数操作

我们定义一些函数对单链表进行增删改查。

void SLTPrint(SLTNode* phead);

SLTNode* BuySListNode(SLTDataType x);
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);

void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);

（1）单链表的打印

void SLTPrint(SLTNode* phead)
{
	SLTNode* cur = phead;
	//while (cur != NULL)
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}

	printf("NULL\n");
}

（2）单链表创建结点

SLTNode* BuySListNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}

（3）单链表的尾插

我们先来看一下尾插的基本实现思路：我们需要找到最后一个结点，也就是指针域此时为空的结点，然后将此结点指向的下一个结点接向newnode就可以实现尾插。示意图如下：

但我们需要对上述情况分类讨论，如果此时链表本身就为空，那尾插就要改变头结点，那么就需要二级指针了，传入头指针的地址。如果传的是头结点，形参是一份里临时拷贝，我们改变头结点，却无法改变实参。所以在这里我们定义二级指针pphead，储存头结点的地址。

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);

	if (*pphead == NULL)
	{
		// 改变的结构体的指针，所以要用二级指针
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}

		// 改变的结构体，用结构体的指针即可
		tail->next = newnode;
	}
}

（4）单链表的头插

单链表的头插实现思路如下：我们需要先让newnode->next=plist，然后再让plist=newnode；对应二级指针pphead，那么*pphead就是plist。上述顺序不能颠倒，不然就无法找到第一个结点。

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
	SLTNode* newnode = BuySListNode(x);

	newnode->next = *pphead;
	*pphead = newnode;
}

（5）单链表的尾删

我们来想一下尾删的实现思路：先来想可以是空节点吗？很明显空节点无法删除，所以我们对空节点进行限制，遇到空节点，断言。那一个节点的话就需要把plist置空，这就又需要一个二级指针了。那一个节点以上，我们可以找到节点为空将其free就好。

void SLTPopBack(SLTNode** pphead)
{
	// 1、空
	assert(*pphead);

	// 2、一个节点
	// 3、一个以上节点
	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);
		tail = NULL;
		//tailPrev->next = NULL;

		SLTNode* tail = *pphead;
		while (tail->next->next)
		{
			tail = tail->next;
		}

		free(tail->next);
		tail->next = NULL;
	}
}

（6）单链表的头删

void SLTPopFront(SLTNode** pphead)
{
	// 空
	assert(*pphead);

	// 非空
	SLTNode* newhead = (*pphead)->next;
	free(*pphead);
	*pphead = newhead;
}

（7）单链表的插入：在pos之前插入x

在pos之前插入x，实现思路如下：

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);

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

		SLTNode* newnode = BuySListNode(x);
		prev->next = newnode;
		newnode->next = pos;
	}
}

（8）单链表的插入：在pos之后插入x

实现思路如图：

// 在pos以后插入x
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);

	SLTNode* newnode = BuySListNode(x);
	pos->next = newnode;
	newnode->next = pos->next;
}

（9）单链表的删除：删除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 = NULL;
	}
}

（10）单链表的删除：pos后的位置

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

	// 检查pos是否是尾节点
	assert(pos->next);

	SLTNode* posNext = pos->next;

	pos->next = posNext->next;

	free(posNext);
	posNext = NULL;
}

文章出处登录后可见！

已经登录？立即刷新