博客

前言

本篇博客用C语言分模块的实现单链表的各个接口，先介绍其结构，后根据结构设计合适的算法（

c++版本在最后，若你的基础不错可以直接跳到最后

）。

链表基本结构

链表由一个个的节点连接成，这里的节点是一个结构体，由数据域与指针域组成。

typedef int SListDateType

typedef struct SListNode
{
	SListDataType data；    //data变量用来存储数据
	struct SListNode* next；//next指向下一个节点；
}SListNode；
//用SListNode重新声明节点类型

不同与顺序表，链表中节点的储存不是连续的，每个节点都是分散的，通过next指针来寻找下一个节点。

链表中：

尾节点

的next指向NULL，并且还有一个头指针phead指向链表中第一个节点（也就是不带哨兵位节点）。头指针为空，说明链表为空。

链表的尾插

分两种情况

• 链表为空：创建一个新的节点，使其指针域指向NULL，数据域放入要放的数据。最后让头指针指向该节点
• 链表不为空：同样也要创建一个节点。接着找到尾指针（指针域为空的节点），使其指向新的节点

先封装创建新节点的函数

SListNode* CreatSListNode(SListDataType x)
{
	SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
	if (newNode == NULL)
	{
		printf("申请空间失败\n:);
		return 0;
	}
	else
	{
		newNode->next = NULL;
		newNode->data = x;
	}
	return newNode;
}

创建新节点并填入数据到其数据域中，之后要找到尾节点（创建一个指针cur，cur最初指向链表的首节点，如果cur的next所指向的指针不为空，cur要继续往后走，直到cur的next指向了NULL，说明cur当前指向的是尾节点），将尾节点的指针指向新节点。

当链表为空时，将头指针指向新节点，需要把头指针的值从NULL改成新节点的地址（phead为指向链表第一个节点的指针，链表为空phead为空，链表不为空phead不为空，要通过函数修改一个变量的值，需要传递其地址，那么要修改phead指针的值就要传递指针的地址，也就是二级指针），所以这里要传址操作。

分成两种情况

void SListPushBack(SListNode** pphead, SListData x)
{
	SListNode* newNode = CreatSListNode(x);
	if (*pphead == NULL)
	{
		*phead = newNode;
		return;
	}
	else
	{
		SListNode* cur = *phead;
		while (cur->next != NULL)
			cur = cur->next;
		cur->next = newNode;
	}
}

链表的尾删

删除链表的尾节点，同样也要找到尾节点的位置，释放尾节点，将尾节点前一个节点的next指针指向空。用两个指针，一个tail最后指向尾节点，prev最后指向尾节点前一个节点。分为三种情况

• 链表为空不删除
• 只有一个节点，此时删除后头指针需要指向空，因此需要传递二级指针
• 有一个以上的节点

void SListPopBack(SListNode** pphead)
{
	if (*pphead == NULL)
		return;
	else if ((*pphead)->next == NULL)//只有一个节点
	{
		free((*pphead)->next);
		*pphead = NULL;
	}
	else
	{
		SListNode* prev = NULL;
		SListNode* tail = *pphead;
		while (tail->next)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	}	
}	

链表的头插与头删

头插

创建新节点，将新节点的指针指向phead。

如果链表为空，指针指向phead，也就指向了NULL，此时链表有一个节点，但需要改变头指针，所以需要传递二级指针。

如果链表有一个及以上的节点，其操作与链表为空时一样。

void SListPushFront(SListNode** pphead, SListDara x)
{
	SListNode* newNode = CreatSListNode(x);
	newNode->next = *pphead;
	*pphead = newNode;
}

头删

同样头删也要改变头指针，所以需要传递二级指针。将头指针实现第二个节点，释放第一个节点。

如果链表为空不删除

void SListPopFront(SListNode** pphead)
{
	if (*pphead == NULL)
		return;
	SListNode* first = *pphead;
	*pphead = (*ppehad)->next;
	free(first);
}

链表的查找与修改

查找

查找函数返回一个指针。指向要查找的节点，通过数据域查找节点，定义一个指针cur如果cur的data等于要查找的数据，函数返回，否则cur指向下一个节点。找不到返回NULL。

SListNode* SListNodeFind(SListNode* phead,SListData x)
{
	if (phead == NULL)
		return NULL; 
	SListNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
			return cur;
		else
			cur = cur->next;
	}
	return NULL；
}	

修改

假设要修改链表中的数据域为2的节点，通过调用

查找

函数，接收查找函数的返回值：对应节点的指针，对该指针解引用就能修改里面的数据。

SListNode* pList;
SListPushBack(pList, 3);
SListPushBack(pList, 4);
SListPushBack(pList, 2);
SListNode* pos = SListNodeFind(pList, 2);
if (pos != NULL)
	pos->data = 20; // 查找到2对应的节点后进行修改

任意位置的插入与删除

插入

单链表的插入是将节点插入另一个节点之后。先创建一个新的节点，将该节点插入pos指针指向节点的后面，使pos指向的next指向新的节点，新节点的next指向pos之前指向的next。所以先将newNode的next指向pos的next，再将pos的next指向newNode。

viod SListInsertAfter(SListNode* pos, SListData x)
{
	assert(pos);
	SListNode* newNode = CreatSListNode(x);
	newNode->next = pos->next;
	pos->next = newNode;
}

删除

删除一个数删除的不是内存而是指向该内存的指针，也就是释放该指针。



删除的是

pos后面的节点next

，先将该节点保存为next指针，需要使pos的指针指向nextnext，然后释放next节点。

有两种特殊情况：

• 如果pos是尾节点，pos后面没有节点，说明要删除的数不存在，不需要删除
• 如果pos后面只有一个节点，删除该节点后pos的指针将指向空指针，pos成为链表的尾节点

void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	// 下面的代码能同时针对两种特殊情况，不用分别做判断
	// next为尾节点时，if条件不会进入，不会进行删除操作
	// next后只有一个节点时，nextnext为NULL，pos的next会指向NULL
	if (pos->next) 
	{
		SListNode* next = pos->next;
		SListNode* nextnext = next->next;
		free(next);
		pos->next = nextnext;
	}
}

C++版本实现

以上是大一写的内容，现在博主大二复习数据结构时又手撕了一遍单链表，不过与C语言不同，这次是用C++实现的单链表。所以这里将forward_list.hpp的内容放出，其中，对于与之前不同的但又很关键的点会用注释的形式提醒，如果你理解了C语言版本的单链表，C++版本对你来说也不是难事

#include <iostream>

template <class T>
struct flist_node
{
	typedef T value_type;
	value_type _data;
	flist_node *_next;
	flist_node(const value_type& x)
	{
		_data = x;
		_next = nullptr;
	}
};

template <class T>
class forward_list
{
	typedef T value_type;
	typedef flist_node<T> node;
public:
	~forward_list();
	// 在第pos个节点后插入新节点
	bool insert(int pos, const value_type& x);
	bool push_front(const value_type& x) { return insert(0, x); }
	// 删除第pos个节点
	bool erase(int pos);
	bool pop_front() { return erase(1); }
	// 返回链表中第一个值为x的节点序号
	size_t find(const value_type& x);
	void print();
private:
	size_t _size = 0;
	node *_head = nullptr;
};

template <class T>
forward_list<T>::~forward_list()
{
	node *cur = _head;
	node *next = nullptr;
	while (cur)
	{
		next = cur->_next;
		delete cur;
		cur = next;
	}
}

// 注意，此版本只实现insert和erase，即任意位置的插入与删除
// 其他位置的插入与删除是对insert和erase的复用

// 在第pos个节点后插入节点，需要判断pos是否为0
// 要注意的是，链表没有第0个节点，节点下标从1开始
// 如果为0，即表示头插，需要修改_head
// 如果不为0，需要根据pos的值进行遍历，找到第pos个节点

// 函数最开始需要对pos的合法性进行判断
template <class T>
bool forward_list<T>::insert(int pos, const value_type& x)
{
	if (pos > _size || pos < 0)
		return false;
	
	node *new_node = new node(x);
	if (pos == 0)
	{
		new_node->_next = _head;
		_head = new_node;
	}
	else
	{
		node *cur = _head;
		for (int i = 1; i < pos; ++i)
		{
			cur = cur->_next;
		}
		
		node *next = cur->_next;
		cur->_next = new_node;
		new_node->_next = next;
	}

	++_size;
	return true;
}

// 删除第pos个节点，同样两种情况
// pos为1表示头删除，需要修改_head的值
// pos不为1，根据pos进行遍历，主要需要保存上一个节点的地址

// 同样的要对pos进行合法性的判断
template <class T>
bool forward_list<T>::erase(int pos)
{
	if (pos > _size || pos == 0 || pos < 0)
		return false;
	
	if (pos == 1)
	{
		node *second = _head->_next;
		delete _head;
		_head = second;
	}
	// 至少删除的是第二个节点 
	else
	{
		node *prev = _head;
		node *cur = _head->_next;

		for (int i = 2; i < pos; ++i)
		{
			prev = cur;
			cur = cur->_next;
		}

		prev->_next = cur->_next;
		delete cur;
	}
	--_size;
	return true;
}

template <class T>
size_t forward_list<T>::find(const value_type& x)
{
	node *cur = _head;
	int count = 1;
	while (cur)
	{
		if (cur->_data == x)
			return count;
		cur = cur->_next;
		++count;
	}

	return 0;
}

// for debug
template <class T>
void forward_list<T>::print()
{
	node *cur = _head;
	while (cur)
	{
		std::cout << cur->_data << ' ';
		cur = cur->_next;
	}
	std::cout << std::endl;
}