数据结构 - c语言链表 *** 作

目录

前言：

链表的概念：

顺序表和链表的优缺点：

链表的结构与定义

接口函数

详解接口函数的实现

        创建新节点（BuySListNode）

        打印（SListPrint）

1、尾插（SListPushBack）

2、头插（SListPushFront）

3、尾删（SListPopBack）

4、头删（SListPopFront ）

5、查找（SListFind）

6、指定位置前插（SListInsert）

7、删除指定位置节点（SListEarse）

8、指定位置后插（SListInsertAfter）

9、删除指定位置之后的节点（SListEraseAfter）

10、销毁（SListDestroy）

完整代码

SList.h：头文件以及函数申明

SList.c：接口实现

OJ练习巩固

---

前言： 链表的概念：

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

简单的说，就是一些结构体相互关联起来，而关联的手段就是指针，通过存储下一个结构体的地址，就能挨个访问存在结构体里的数据。

顺序表和链表的优缺点：

顺序表：

顺序表的优点：

1. 支持随机访问，有些算法需要结构随机访问，比如二分查找和优化的快排等。
2. 数据是按顺序存放的，空间利用率高。
3. 通过下标直接访问，存取速度高效。

顺序表的缺陷：

1. 空间不够了就需要扩容，扩容是存在消耗的。
2. 头部或者中间位置的插入或删除，需要挪动，挪动数据时也是存在消耗的。
3. 避免频繁扩容，一次一般都是按倍数去扩容（2倍适中），可能存在一定空间的浪费现象。

链表：

链表的优点：

1. 按需申请空间，不用就释放空间（ 链表可以更合理地使用空间）。
2. 头部或者中间位置的插入和删除，不需要挪动数据。
3. 不存在空间浪费。

链表的缺陷：

1. 每一个数据，都要存一个指针去链接后面的数据节点。
2. 不支持随机访问（用下标直接访问第 i 个），必须得走 O(N) 。

顺序表详情：数据结构 - 顺序表基本 *** 作（简单易懂）

（建议先阅读顺序表，更好理解链表）

链表的结构与定义

typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data; // val
	struct SListNode* next; // 存储下一个节点的地址
}SListNode, SLN;

        解读：在顺序表章节讲过，为了方便后续使用我们将类型 typedef 一下。首先创建结构体，因为叫单链表（SingleListNode），所以我们将它取为 SListNode。结构体有两个变量，data 是用来存放节点的数据的变量，而 next 是用来指向后继节点指针的变量。

链表结构图：

        便于更形象方便地理解而想象出来的（比如这个箭头其实不存在），事实上在内存中是分散存储的，其中唯一联系就是指针，若指向某块链表的指针搞丢了，那么这块结构体以及其后接的结构体就再也找不到了

接口函数

void SListPrint(SListNode* phead);
void SListPushBack(SListNode** pphead, SLTDataType x);
void SListPushFront(SListNode** pphead, SLTDataType x);
void SListPopBack(SListNode** pphead);
void SListPopFront(SListNode** pphead);
SListNode* SListFind(SListNode* phead, SLTDataType x);

// 在pos位置之前插入
void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x);
// 删除pos 位置
void SListErase(SListNode** pphead, SListNode* pos);

// 在pos之后插入
void SListInsertAfter(SListNode* pos, SLTDataType x);
// 删除pos位置后面的值
void SListEraseAfter(SListNode* pos);

void SListDestroy(SListNode** pphead);

详解接口函数的实现

创建新节点（BuySListNode）

SListNode* BuySListNode(SLTDataType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	else
	{
		newnode->data = x;
		newnode->next = NULL;
	}

	return newnode;
}

考虑到创建新节点要经常用，为了方便复用，我们把它写成函数 

打印（SListPrint）

void SListPrint(SListNode* phead)
{
	SListNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

        我们想实现单链表的打印，我们就需要遍历整个链表。首先创建一个结构体指针 cur 来存放 pHead ，然后通过 cur 来把整个链表走一遍。只要 cur 不为 NULL，就说明还没有走完，就进入循环，循环体内打印出当前 cur->data 的内容，就实现了打印节点中的内容，随后将 cur 赋值成 cur->next ，使得 cur 指向它后面的节点。当 cur 为 NULL 时说明已经走完了，则跳出循环。最后我们再打印一个 "NULL" 把链表的尾部表示出来

主要作用：便于调试测试

1、尾插（SListPushBack）

void SListPushBack(SListNode** pphead, SLTDataType x)
{
	assert(pphead);

	SListNode* newnode = BuySListNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		// 找尾
		SListNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}

		tail->next = newnode;

		// 错误写法，这里没有链接起来
		/*SListNode* tail = *pphead;
		while (tail != NULL)
		{
		tail = tail->next;
		}

		tail = newnode;*/
	}
}

        当新节点创建完毕后，我们就可以开始写尾插了。如果链表没有数据的话我们就可以直接插入，所以我们先判断链表是否为空，这里记得对 *ppHead 解引用。 

        如果链表是有数据的，我们要实现尾部插入，我们就要找到尾节点。这里我们创建一个寻尾指针 SListNode* tail 作为工具人，来替代 *ppHead 去找尾节点。思路也很简单，如果 tail 的下一个节点不为空，就进入循环，令 tail 指向后继节点。这样tail 就成功找到了尾节点，最后 tail->next 就是尾节点了，我们把 newnode 赋给 end->next 即可完成插入。

2、头插（SListPushFront）

void SListPushFront(SListNode** pphead, SLTDataType x)
{
	assert(pphead);

	SListNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

创建一个新结构体，直接插到头结点的前面，非常简单

3、尾删（SListPopBack）

void SListPopBack(SListNode** pphead)
{
	assert(pphead);

	// 也可以暴力检查为空的情况
	//assert(*pphead != NULL);

	if (*pphead == NULL) // 1、空 
	{
		return;
	}
	else if ((*pphead)->next == NULL)// 2、一个节点
	{
		free(*pphead);
		*pphead = NULL;
	}
	else	// 3、多个节点
	{
		SListNode* prev = NULL;
		SListNode* tail = *pphead;
		while (tail->next != NULL)
		{
		    prev = tail;
		    tail = tail->next;
		}

		free(tail);    //找到最后一个
		tail = NULL;
		prev->next = NULL;    //好习惯



		/*SListNode* tail = *pphead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}
		free(tail->next);
		tail->next = NULL;*/
	}	
}

• 尾删我们需要注意的是防止没有东西可删除，所以我们需要预防出现为空的情况。这里本人更倾向的是温柔检查的方法
• 第二种情况时，我们就可以直接删除，使用 free 释放空间完空间后再把它置成空
• 第三种情况时，为了防止最后没法触及上一个节点从而没办法把它置空，所以这里在创建寻尾指针 tail 的同时，还要创建一个前驱指针 prev 以用来实时保存 tail 的值，让 tail 去送死。只要 tail->next 不是 NULL 时就进入循环，首先保存 tail 的值，然后令 tail 指向后继节点。当 tail->next 为 NULL 时，free 释放空间并置空，此时这个尾部节点就被删除了，但是上一个节点还存着这个已经删除的节点地址。这时，我们的前驱指针 prev 就能派上用场了，将 prev -> next 置为 NULL 就可以解决问题。这就是前驱指针的作用。

4、头删（SListPopFront ）

void SListPopFront(SListNode** pphead)
{
	assert(pphead);

	// 1、空
	// 2、非空
	if (*pphead == NULL)
	{
		return;
	}
	else
	{
		SListNode* next = (*pphead)->next;
		free(*pphead);
		*pphead = next;
	}
}

        头删我们要注意的是不能直接 free 掉，因为直接删的话就会导致找不到下一个节点了。创建 next 指针，用来保存我们要删除的头结点 *phead 指向的下一个结点的地址。保存好了之后我们就可以大胆的删除了，直接把头结点 free 掉，将我们刚才保存的 next 赋值给 *pphead 即可。

5、查找（SListFind）

SListNode* SListFind(SListNode* phead, SLTDataType x)
{
	SListNode* cur = phead;
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}

		cur = cur->next;
	}

	return NULL;
}

就是简单的遍历链表查找到相同则返回该结构体，否则返回NULL

6、指定位置前插（SListInsert）

void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);

	// 1、pos是第一个节点
	// 2、pos不是第一个节点
	if (pos == *pphead)    //在头结点插入，复用头插
	{
		SListPushFront(pphead, x);
	}
	else
	{
		SListNode* prev = *pphead;
		while (prev->next != pos)    //找到位置
		{
			prev = prev->next;
		}

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

一般默认是在pos位置之前去插入一个节点

简单理解为找到prve与pos（两个结构体）之间的链，将其断开，接上newnode

7、删除指定位置节点（SListEarse）

void SListErase(SListNode** pphead, SListNode* pos)
{
	assert(pphead);
	assert(pos);

	if (*pphead == pos)
	{
		SListPopFront(pphead);//复用头删
	}
	else
	{
		SListNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

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

简单理解为找到pos之前的结构体prve，让prve的链（原本接pos）直接接到pos之后的结构体上，删除pos（如果先删pos会找不到pos之后的结构体）；

8、指定位置后插（SListInsertAfter）

void SListInsertAfter(SListNode* pos, SLTDataType x)
{
	assert(pos);
	//SListNode* next = pos->next;
	//SListNode* newnode = BuySListNode(x);

	//pos->next = newnode;
	//newnode->next = next;

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

在 pos 后面插入就很简单了，因为不需要找 pos 前面的结点，没有什么好讲的

9、删除指定位置之后的节点（SListEraseAfter）

void SListEraseAfter(SListNode* pos)
{
	assert(pos);

	SListNode* next = pos->next;
	if (next)
	{
		pos->next = next->next;
		free(next);
		next = NULL;
	}
}

非常简单，与SListErase原理相同

10、销毁（SListDestroy）

void SListDestroy(SListNode** pphead)
{
	assert(pphead);

	SListNode* cur = *pphead;
	while (cur)
	{
		SListNode* next = cur->next;
		free(cur);
		cur = next;
	}

	*pphead = NULL;
}

        销毁得有东西才能销毁，所以断言 ppHead 不为空。通过 cur 逐个走一遍，为了防止删了一个下一个结点就找不到了，每次进入循环都先创建一个 next 指针来保存 cur->next，然后再 free 掉。全部结束后再把 *ppHead 置为空，就完成销毁了。

原理类似SListEraseAfter

完整代码 SList.h：头文件以及函数申明

#pragma once
#include 
#include 
#include 
#include 

typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data; // val
	struct SListNode* next; // 存储下一个节点的地址
}SListNode, SLN;

void SListPrint(SListNode* phead);
void SListPushBack(SListNode** pphead, SLTDataType x);
void SListPushFront(SListNode** pphead, SLTDataType x);
void SListPopBack(SListNode** pphead);
void SListPopFront(SListNode** pphead);
SListNode* SListFind(SListNode* phead, SLTDataType x);

// 在pos位置之前插入
void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x);
// 删除pos 位置
void SListErase(SListNode** pphead, SListNode* pos);

// 在pos之后插入
void SListInsertAfter(SListNode* pos, SLTDataType x);
// 删除pos位置后面的值
void SListEraseAfter(SListNode* pos);

void SListDestroy(SListNode** pphead);

SList.c：接口实现

#include "SList.h"

void SListPrint(SListNode* phead)
{
	SListNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

SListNode* BuySListNode(SLTDataType x)
{
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	else
	{
		newnode->data = x;
		newnode->next = NULL;
	}

	return newnode;
}

void SListPushBack(SListNode** pphead, SLTDataType x)
{
	assert(pphead);

	SListNode* newnode = BuySListNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		// 找尾
		SListNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}

		tail->next = newnode;

		// 错误写法，这里没有链接起来
		/*SListNode* tail = *pphead;
		while (tail != NULL)
		{
		tail = tail->next;
		}

		tail = newnode;*/
	}
}

void SListPushFront(SListNode** pphead, SLTDataType x)
{
	assert(pphead);

	SListNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

void SListPopBack(SListNode** pphead)
{
	assert(pphead);

	// 也可以暴力检查为空的情况
	//assert(*pphead != NULL);

	// 1、空
	// 2、一个节点
	// 3、多个节点
	if (*pphead == NULL)  // 温柔检查
	{
		return;
	}
	else if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		/*SListNode* prev = NULL;
		SListNode* tail = *pphead;
		while (tail->next != NULL)
		{
		prev = tail;
		tail = tail->next;
		}

		free(tail);
		tail = NULL;
		prev->next = NULL;*/

		SListNode* tail = *pphead;
		while (tail->next->next != NULL)
		{
			tail = tail->next;
		}

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

void SListPopFront(SListNode** pphead)
{
	assert(pphead);

	// 1、空
	// 2、非空
	if (*pphead == NULL)
	{
		return;
	}
	else
	{
		SListNode* next = (*pphead)->next;
		free(*pphead);
		*pphead = next;
	}
}

SListNode* SListFind(SListNode* phead, SLTDataType x)
{
	SListNode* cur = phead;
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;
		}

		cur = cur->next;
	}

	return NULL;
}

// 在pos位置之前插入
void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x)
{
	assert(pphead);
	assert(pos);

	// 1、pos是第一个节点
	// 2、pos不是第一个节点
	if (pos == *pphead)
	{
		SListPushFront(pphead, x);
	}
	else
	{
		SListNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

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

void SListInsertAfter(SListNode* pos, SLTDataType x)
{
	assert(pos);
	//SListNode* next = pos->next;
	//SListNode* newnode = BuySListNode(x);

	//pos->next = newnode;
	//newnode->next = next;

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

// 删除pos 位置
void SListErase(SListNode** pphead, SListNode* pos)
{
	assert(pphead);
	assert(pos);

	if (*pphead == pos)
	{
		SListPopFront(pphead);
	}
	else
	{
		SListNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

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

void SListEraseAfter(SListNode* pos)
{
	assert(pos);

	SListNode* next = pos->next;
	if (next)
	{
		pos->next = next->next;
		free(next);
		next = NULL;
	}
}

void SListDestroy(SListNode** pphead)
{
	assert(pphead);

	SListNode* cur = *pphead;
	while (cur)
	{
		SListNode* next = cur->next;
		free(cur);
		cur = next;
	}

	*pphead = NULL;
}

笔记篇：参考资料->比特科技

OJ练习巩固

链表的中间结点

 思路：运用快慢指针；fast指针一次走两步，slow指针一次走一步，fast到头则slow在中

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        struct ListNode*fast,*slow;
        slow=fast=head;
        while(fast&&fast->next){
            slow=slow->next;
            fast=fast->next->next;
        }
        return slow;
    }
};

链表中倒数第k个结点

 思路：同样是快慢指针，注意fast先走k步时是否越界

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

/**
 * 
 * @param pListHead ListNode类 
 * @param k int整型 
 * @return ListNode类
 */
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    // write code here
    struct ListNode*slow,*fast;
    slow=fast=pListHead;
    
    while(k--){
        if(fast==NULL)
            return NULL;   //易错点
        fast=fast->next;
    }
    
    while(fast){
        slow=slow->next;
        fast=fast->next;
    }
    return slow;
}

合并两个有序链表

 方法1：简单的模拟无头单链表

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    if(list1==NULL)    //如示例3所示的特判
        return list2;
    if(list2==NULL)
        return list1;

    struct ListNode*head=NULL,*tail=NULL;
    while(list1&&list2)
    {
        if(list1->valval)
        {
            if(tail==NULL){    //第一个元素
                head=tail=list1;
            }
            else
            {
                tail->next=list1;
                tail=list1;
            }
            list1=list1->next;
        }
        else
        {
            if(tail==NULL){
                head=tail=list2;
            }
            else
            {
                tail->next=list2;
                tail=list2;
            }
            list2=list2->next;
        }
      
    }
    if(list1)    //如果有一个空了，就直接将另一个接在后面即可
    {
        tail->next=list1;
    }
    if(list2){
        tail->next=list2;
    }
    return head;
}

方法二：带头节点单链表，在头部先生成一个节点，该节点不存储有效数据；有了该节点这不必特判头元素

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){

    struct ListNode*head=NULL,*tail=NULL;
    head=tail=(struct ListNode*)malloc(sizeof(struct ListNode));
    head->next=NULL;

    while(list1&&list2)
    {
        if(list1->valval)
        {

            tail->next=list1;
            tail=list1;
            list1=list1->next;
        }
        else
        {
            tail->next=list2;
            tail=list2;
            list2=list2->next;
        }
      
    }
    if(list1)
    {
        tail->next=list1;
    }
    if(list2){
        tail->next=list2;
    }
    struct ListNode* list=head->next;
    return list;
}