C语言实现链表【一】（无头单向非循环链表）

超、凢脫俗 2022-12-27 07:58 102阅读 0赞

#  #

# 无头单向非循环链表 #

看到这个标题，是不是有小伙伴已经懵了呢？

只学过链表，怎么还有个无头和有头呢？怎么还有个循环和非循环呢？怎么还有个单向和双向呢？一连串的疑问。。。

其实这些都是链表的表示形式，只不过大部分人只接触了最简单的单链表，也就是我们这里提到的无头单向非循环链表，最简单的链表结构表示形式

话不多说，直接上图更直观一些

![20201209092006401.png][]

*  ### 单链表结构定义： ###

熟悉了单链表的结构，下面来考虑如何在链表中实现数据存储呢？

链表是由多个节点按照一定的逻辑顺序连接形成的，每一个节点都由两部分组成，一部分存储数据，一部分存放下一节点的地址

![20201209092609659.png][]

代码实现结构如下：

typedef int LDatatype;
    
    //单个节点数据结构
    typedef struct listNode {
    	LDatatype data;
    	struct listNode* next;
    }listNode;

此处我们需要区分单链表和双链表：

单链表只能在前驱节点中存放后继节点的地址，而双链表不仅能够在前驱节点存放后继节点地址，还可以在后继节点中存放前驱节点的地址

区分不带头单链表和带头带头单链表

带不带头不是说看有没有head，而是看head节点是否存放数据

对此，即便是无头的单链表在构建链表结构的过程中，依然在头结点存放第一个节点的地址，但头结点仅仅放地址，而不存放数据

typedef struct linklist {
    	//保存第一个节点的地址
    	listNode* head;
    }linklist;

*  ### 单链表接口声明： ###

单链表主要也是实现数据管理存储功能，即增删查改的操作，包括在头节点插入，尾结点插入，头结点删除，尾结点删除，指定节点后删除插入操作等

void linklistInit(linklist* lst);
    
    void linklistPushBack(linklist* lst,LDatatype val);
    
    listNode* createNode(LDatatype val);
    
    void linklistPopBack(linklist* lst);
    
    void linklistPushFront(linklist* lst,LDatatype val);
    
    void linklistPopFront(linklist* lst);
    
    void linkInsertAfter(listNode* node, LDatatype val);
    
    void linkPopAfter(listNode* node);
    
    listNode* linkFind(linklist* lst, LDatatype val);
    
    void linkDestory(linklist* lst);
    
    void linkPrint(linklist* lst);

*  ### 单链表接口实现 ###
 *  **链表初始化：**

（1）初始化链表结构：

由于链表结构中有头结点，初始化只需要将头结点存放地址置为空

void linklistInit(linklist* lst)
    {
    	if (lst == NULL)
    		return;
    	lst->head = NULL;
    }

（2）创建节点

当执行插入操作的过程中，根据节点结构需要先构造出一个可以存放数据的节点

listNode* createNode(LDatatype val)
    {
    	listNode* node = (listNode*)malloc(sizeof(listNode));
    	if (node != NULL)
    	{
    		node->data = val;
    		node->next = NULL;
    	}
    	return node;
    }

注意到在创建节点中，将该节点存放下一节点地址给NULL，如果尾插，将不需在尾部节点置NULL，其余位置插入，更新地址即可

*  **单链表尾插**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70][]

![202012091011104.png][]

void linklistPushBack(linklist* lst, LDatatype val)
    {
    	//空 创建节点 赋值+next置空
    	if (lst == NULL || lst->head == NULL)
    	{
    		lst->head = createNode(val);
    	}
    	//非空  遍历找到尾结点  在其后插入
    	else
    	{
    		listNode* tail=lst->head;
    		while (tail->next != NULL)
    		{
    			tail = tail->next;
    		}
    		tail->next = createNode(val);
    	}
    }

*  **单链表尾删**

只有一个头结点情况：

![20201209101920962.png][]

遍历找最后一个节点：

![20201209102612142.png][]

![2020120910262591.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 1][]

代码如下：

void linklistPopBack(linklist* lst)
    {
    	if (lst == NULL || lst->head == NULL)
    		return;
    	//只有一个头结点  
    	if (lst->head->next == NULL)
    	{
    		lst->head = NULL;
    	}
    	//否则，遍历找到最后一个节点
    	listNode* prev = NULL;
    	listNode* tail = lst->head;
    	//两个指针同时后移查找
    	while (tail->next!=NULL)
    	{
    		prev = tail;
    		tail = tail->next;
    	}
    	free(tail);
    	prev->next = NULL;
    }

*  **单链表头插**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 2][]

void linklistPushFront(linklist* lst,LDatatype val)
    {
    	if (lst == NULL || lst->head == NULL)
    		return;
    	listNode* node = createNode(val);
    	node->next = lst->head;
    	lst->head = node;
    }

*  单链表头删

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 3][]

void linklistPopFront(linklist* lst)
    {
    	if (lst == NULL||lst->head==NULL)
    		return;
    	listNode* next= lst->head->next;
    	free(lst->head);
    	lst->head = next;
    }

*  **单链表指定节点后插入**

![20201209104439787.png][]

void linkInsertAfter(listNode* node, LDatatype val)
    {
    	if (node == NULL)
    		return;
    	listNode* newnode = createNode(val);
    	listNode* next = node->next;
    	node->next = newnode;
    	newnode->next = next;
    }

*  **单链表指定节点后删除**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 4][]

void linkPopAfter(listNode* node)
    {
    	if (node == NULL)
    		return;
    	//listNode* newnode = createNode(val);
    	listNode* next = node->next;
    	listNode* newnext = next->next;
    	free(next);
    	node->next = newnext;
    }

*  **单链表遍历**

listNode* linkFind(linklist* lst, LDatatype val)
    {
    	if (lst == NULL || lst->head == NULL)
    	{
    		return NULL;
    	}
    	listNode* cur = lst->head;
    	while (cur)
    	{
    		if (cur->data == val)
    		{
    			return cur;
    		}
    		cur = cur->next;
    	}
    	return NULL;
    }

*  **单链表销毁（删除所有节点，但需要从头开始删除，并保存后续节点）**

![20201209110043963.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 5][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 6][]

void linkDestory(linklist* lst)
    {
    	if (lst == NULL || lst->head == NULL)
    	{
    		return;
    	}
    	listNode* cur = lst->head;
    	//listNode* next = cur->next;
    	while (cur)
    	{
    		listNode* next = cur->next;
    		free(cur);
    		cur = next;
    		/*lst->head = next;
    		cur = lst->head;
    		next = next->next;*/
    	}
    	lst->head = NULL;
    }

*  **单链表某一指定节点删除**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 7][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 8][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 9][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 10][]

listNode* linkErase(linklist* lst,listNode* node)
    {
    	if (node == NULL)
    		return;
    	//listNode* newnode = createNode(val);
    	listNode* tmp = (listNode*)malloc(sizeof(listNode));
    	tmp->next = lst->head;
    	listNode* prev = tmp;
    	listNode* tail = lst->head;
    	//两个指针同时后移查找
    	while (tail)
    	{
    		if (tail == node)
    		{
    			prev->next = tail->next;
    			tail = tail->next;
    		}
    		else
    		{
    			prev = prev->next;
    			tail = tail->next;
    		}
    	}
    	lst->head = tmp->next;
    	free(tmp);
    	return lst->head;
    }

**正所谓千言万语的解释，不如一张图解释的清楚，不理解的小伙伴可以根据图示来理解链表的指向变化，**

**今天分享就到这，下一次分享带头双向循环链表的增删改查实现！**

[20201209092006401.png]: /images/20221120/76a56a86a6ba43a1b8d3334e75bbfc76.png
[20201209092609659.png]: /images/20221120/192a72b67fdc41bea915f2fb3b24d739.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70]: /images/20221120/e21c83b7e9514ed7b1170c78cf736d07.png
[202012091011104.png]: /images/20221120/fffd40a7e6a7452886eafe260f5793ba.png
[20201209101920962.png]: /images/20221120/3086cb2ff8ad4e6399cfe263fdb13c79.png
[20201209102612142.png]: /images/20221120/b9b75e76cc054816a35d028f4200dcdc.png
[2020120910262591.png]: /images/20221120/e2adf9349e9c417a8ba8fe903c960ee4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 1]: /images/20221120/1cd963d855e34f958b73803fb7978a01.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 2]: /images/20221120/a9d13ed3a0314464bfc860d28525d20d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 3]: /images/20221120/74cabbc656fa41d48ba41f582174082d.png
[20201209104439787.png]: /images/20221120/b851822d045f4a2ab8d67b9fa9059fd7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 4]: /images/20221120/53c4e79ed2234b72b215854752d65e7f.png
[20201209110043963.png]: /images/20221120/8294c82baaa84b4db6d7e61f85278cca.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 5]: /images/20221120/bca69069561a4db2b25b26ef48d7f086.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 6]: /images/20221120/adc0ae12b28b4d6b95963b967c376d82.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 7]: /images/20221120/55368408ef84491192cedf9bb4493a45.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 8]: /images/20221120/36f22166b03140d4b8028baffc4d6640.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 9]: /images/20221120/ed058dee2b954008975f820d5c67b129.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 10]: /images/20221120/ff81d675ae5141dd82d67c288dd2bc15.png