1. 创建节点

每个节点包含两个部分：

  • 数据域：存储节点的数据。
  • 指针域：指向下一个节点的指针。

2. 头插法

  • 操作：在链表的头部插入一个新节点。新节点的 next 指针指向当前的头节点，然后将新节点设为头节点。
  • 适用场景：快速在链表头部添加元素。

3. 尾插法

  • 操作：在链表的尾部插入一个新节点。需要先找到链表的最后一个节点，然后让最后一个节点的 next 指针指向新节点。
  • 适用场景：需要保持链表顺序或添加元素到链表末尾时。

4. 头删法

  • 操作：删除链表的第一个节点。头节点的 next 指针指向新的头节点，并释放原头节点。
  • 适用场景：快速删除链表的第一个元素。

5. 尾删法

  • 操作：删除链表的最后一个节点。需要找到倒数第二个节点，将其 next 指针设为 NULL，然后释放最后一个节点。
  • 适用场景：需要删除链表末尾的元素。

6. 查找节点

  • 操作：从链表的头部开始遍历，找到第一个数据域匹配目标值的节点，并返回该节点的指针。如果找不到，返回 NULL。
  • 适用场景：在链表中查找特定值的节点。

7. 插入节点

  • 在指定位置之前插入：在链表中找到指定位置的节点，将新节点的 next 指针指向该节点，并将前一个节点的 next 指针指向新节点。
  • 在指定位置之后插入：直接将新节点插入到指定节点的后面，修改相应指针。
  • 适用场景：在链表的特定位置插入元素。

8. 删除节点

  • 删除指定节点：找到要删除的节点及其前一个节点，将前一个节点的 next 指针指向要删除节点的下一个节点，然后释放要删除的节点。
  • 删除指定节点之后的节点：直接修改指定节点的 next 指针，跳过下一个节点，然后释放被跳过的节点。
  • 适用场景：从链表中删除特定位置的元素。

9. 遍历链表

  • 操作：从链表的头节点开始，依次访问每个节点，直到访问到链表末尾 (next 为 NULL)。
  • 适用场景：需要对链表中的每个元素进行操作时。

10. 销毁链表

  • 操作：依次释放链表中每个节点的内存，直到整个链表被清空。
  • 适用场景：链表不再使用，需要释放内存时。

下面我将完整的操作部分分为3个代码区部分；

1结点和链表的定义  具体操作函数的申明  （.h头文件）

  • SLTDataType：定义链表节点中存储的数据类型，这里设定为 int。
  • SLTNode：链表节点的结构体，包含数据和指向下一个节点的指针，用于构建链表。
  • 函数声明：
    • SLTPrint：打印链表内容的函数。
    • SLTPushBack：在链表的尾部插入新节点。
    • SLTPushFront：在链表的头部插入新节点。
    • SLTPopBack：删除链表最后一个节点。
    • SLTPopFront：删除链表第一个节点。
    • SLTFind：查找链表中第一个与给定值相等的节点，并返回该节点的指针。
    • SLTInsert：在给定节点之前插入新节点。
    • SLTInsertAfter：在指定节点后插入新节点。
    • SLTErase：删除指定节点。
    • SLTEraseAfter：删除指定节点之后的节点。
    • SListDesTroy：销毁整个链表并释放内存。
  • 代码1 
    #pragma once  // 确保头文件只被包含一次
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

// 定义数据类型为 int
typedef int SLTDataType;

// 定义链表节点结构体
typedef struct SListNode {
    SLTDataType data;          // 节点的数据部分
    struct SListNode* next;    // 指向下一个节点的指针
} SLTNode;

// 打印链表函数声明
void SLTPrint(SLTNode* phead);

// 尾插法：在链表的尾部插入一个新节点
void SLTPushBack(SLTNode** pphead, SLTDataType x);

// 头插法：在链表的头部插入一个新节点
void SLTPushFront(SLTNode** pphead, SLTDataType x);

// 尾删：删除链表的最后一个节点
void SLTPopBack(SLTNode** pphead);

// 头删：删除链表的第一个节点
void SLTPopFront(SLTNode** pphead);

// 查找：在链表中查找值为 x 的节点，返回该节点的指针
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);

// 在指定位置 pos 之前插入数据 x
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);

// 在指定位置 pos 之后插入数据 x
void SLTInsertAfter(SLTNode* pos, SLTDataType x);

// 删除指定节点 pos
void SLTErase(SLTNode** pphead, SLTNode* pos);

// 删除 pos 之后的节点（即 pos 的下一个节点）
void SLTEraseAfter(SLTNode* pos);

// 销毁链表：释放链表的所有节点内存
void SListDesTroy(SLTNode** pphead);

    2是上面操作函数的具体实现过程  实现了一个单链表的基本操作，包括节点的创建、插入、删除、查找、遍历和销毁等（.c源文件）。

  • 代码2

    #define _CRT_SECURE_NO_WARNINGS 1
#include"SeqList.h"

// 打印链表
void SLTPrint(SLTNode* phead)
{
    SLTNode* pcur = phead;
    while (pcur) // 当 pcur 不为 NULL 时循环
    {
        printf("%d->", pcur->data); // 打印当前节点的数据
        pcur = pcur->next; // 移动到下一个节点
    }
    printf("NULL\n"); // 打印链表结束标志
}

// 创建新节点
SLTNode* SLTBuyNode(SLTDataType x)
{
    SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode)); // 为新节点分配内存
    if (newnode == NULL) {
        perror("开辟空间失败"); // 如果分配失败，输出错误信息
        exit(1); // 退出程序
    }
    newnode->data = x; // 设置新节点的数据
    newnode->next = NULL; // 设置新节点的 next 指针为 NULL
    return newnode; // 返回新节点
}

// 尾插法：在链表尾部插入一个新节点
void SLTPushBack(SLTNode** pphead, SLTDataType x) {
    assert(pphead); // 断言 pphead 不为 NULL
    SLTNode* newnode = SLTBuyNode(x); // 创建新节点
    if (*pphead == NULL) { // 如果链表为空
        *pphead = newnode; // 新节点成为链表的头节点
    }
    else
    {    // 找到链表的尾节点
        SLTNode* pback = *pphead;
        while (pback->next) // 遍历链表直到尾节点
        {  
            pback = pback->next; // 移动到下一个节点
        }
        pback->next = newnode; // 将新节点插入到尾节点之后
    }
}

// 头插法：在链表头部插入一个新节点
void SLTPushFront(SLTNode** pphead, SLTDataType x) {
    assert(pphead); // 断言 pphead 不为 NULL
    SLTNode* newnode = SLTBuyNode(x); // 创建新节点
    newnode->next = *pphead; // 新节点的 next 指针指向当前头节点
    *pphead = newnode; // 更新头节点为新节点
}

// 尾删法：删除链表的最后一个节点
void SLTPopBack(SLTNode** pphead)
{
    // 链表不能为空
    assert(pphead && *pphead);
    // 链表只有一个节点
    if ((*pphead)->next == NULL) // -> 优先级高于*
    {
        free(*pphead); // 释放头节点
        *pphead = NULL; // 将头节点设为 NULL
    }
    else {
        // 链表有多个节点
        SLTNode* prev = *pphead;
        SLTNode* ptail = *pphead;
        while (ptail->next) // 遍历链表直到尾节点
        {
            prev = ptail; // 记录当前节点为前一个节点
            ptail = ptail->next; // 移动到下一个节点
        }
        // prev ptail
        free(ptail); // 释放尾节点
        ptail = NULL; // 将尾节点设为 NULL
        prev->next = NULL; // 更新前一个节点的 next 指针为 NULL
    }
}

// 头删法：删除链表的第一个节点
void SLTPopFront(SLTNode** pphead) {
    // 链表不可以为空
    assert(pphead && *pphead);
    // 找出要删除的头结点的下一个结点
    SLTNode* next = (*pphead)->next;
    free(*pphead); // 释放头节点
    *pphead = next; // 更新头节点为下一个节点
}

// 查找：在链表中查找第一个匹配指定数据的节点
SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {
    SLTNode* pcur = phead;
    while (pcur) // 遍历链表
    {
        if (pcur->data == x) { // 如果找到匹配的节点
            return pcur; // 返回该节点
        }
        pcur = pcur->next; // 移动到下一个节点
    }
    return NULL; // 如果未找到，返回 NULL
}

// 在指定位置之前插入数据 
// 在头结点之前插入，这样头结点就会改变 
// 我们需要找到指定位置的前一个结点，但是 pos 只能找到自己的下一个结点
// 所有需要头结点找到 pos 指定位置的前一个结点
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
    assert(pphead && *pphead); // 断言 pphead 和 *pphead 不为 NULL
    assert(pos); // 断言 pos 不为 NULL
    SLTNode* newnode = SLTBuyNode(x); // 创建新节点
    // 若 pos == *pphead;说明是头插
    if (pos == *pphead)
    {
        SLTPushFront(pphead, x); // 调用头插函数
    }
    else {
        SLTNode* prev = *pphead;
        // prev 是 pos 的前一个结点
        while (prev->next != pos) // 遍历链表直到找到 pos 的前一个节点
        {
            prev = prev->next; // 移动到下一个节点
        }
        // prev -> newnode -> pos  插入 newnode 
        newnode->next = pos; // 新节点的 next 指针指向 pos
        prev->next = newnode; // 前一个节点的 next 指针指向新节点
    }
}

// 在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
    assert(pos); // 断言 pos 不为 NULL
    SLTNode* newnode = SLTBuyNode(x); // 创建新节点
    // pos -> newnode -> pos->next
    newnode->next = pos->next; // 新节点的 next 指针指向 pos 的下一个节点
    pos->next = newnode; // pos 的 next 指针指向新节点
}

// 删除 pos 节点
void SLTErase(SLTNode** pphead, SLTNode* pos) // 用不到头结点
{
    assert(pphead && *pphead); // 断言 pphead 和 *pphead 不为 NULL
    assert(pos); // 断言 pos 不为 NULL
    // pos 是头结点/pos 不是头结点
    if (pos == *pphead)
    {
        // 头删
        SLTPopFront(pphead); // 调用头删函数
    }
    else {
        SLTNode* prev = *pphead;
        while (prev->next != pos) // 遍历链表直到找到 pos 的前一个节点
        {
            prev = prev->next; // 移动到下一个节点
        }
        // prev pos pos->next
        prev->next = pos->next; // 前一个节点的 next 指针指向 pos 的下一个节点
        free(pos); // 释放 pos 节点
        pos = NULL; // 将 pos 设为 NULL
    }
}

// 删除 pos 之后的节点
void SLTEraseAfter(SLTNode* pos)
{
    assert(pos && pos->next); // 断言 pos 和 pos->next 不为 NULL
    SLTNode* del = pos->next;
    // pos del del->next
    pos->next = del->next; // pos 的 next 指针指向 del 的下一个节点
    free(del); // 释放 del 节点
    del = NULL; // 将 del 设为 NULL
}

// 销毁链表
void SListDesTroy(SLTNode** pphead)
{
    assert(pphead && *pphead); // 断言 pphead 和 *pphead 不为 NULL
    SLTNode* pcur = *pphead;
    while (pcur) // 遍历链表
    {
        SLTNode* next = pcur->next; // 保存下一个节点
        free(pcur); // 释放当前节点
        pcur = next; // 移动到下一个节点
    }
    // pcur
    *pphead = NULL; // 将头节点设为 NULL
}

    3打印链表的操作（.c源文件）

代码3

#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"  // 包含头文件，定义了链表相关的结构和函数

// 测试1：手动创建节点并连接它们
void SListTest01()
{
	// 链表是由一个一个的节点组成
	// 创建几个节点
	
	SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));  // 创建第一个节点
	node1->data = 1;  // 设置节点数据

	SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));  // 创建第二个节点
	node2->data = 2;  // 设置节点数据

	SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));  // 创建第三个节点
	node3->data = 3;  // 设置节点数据

	SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));  // 创建第四个节点
	node4->data = 4;  // 设置节点数据

	// 将四个节点连接起来
	node1->next = node2;  // node1的下一个节点是node2
	node2->next = node3;  // node2的下一个节点是node3
	node3->next = node4;  // node3的下一个节点是node4
	node4->next = NULL;  // node4的下一个节点为空，表示链表结束

	// 调用链表的打印函数
	SLTNode* plist = node1;  // 链表的起始节点
	SLTPrint(plist);  // 打印链表内容
}

// 测试2：使用链表操作函数进行增删查改
void SListTest02() {
	// 尾插法：从链表尾部插入数据
	SLTNode* plist = NULL;  // 初始化链表为空
	SLTPushBack(&plist, 1);  // 尾插1
	SLTPushBack(&plist, 2);  // 尾插2
	SLTPushBack(&plist, 3);  // 尾插3
	SLTPushBack(&plist, 4);  // 尾插4
	SLTPrint(plist);  // 打印链表内容

	// 头插法：从链表头部插入数据
	SLTPushFront(&plist, 6);  // 头插6
	SLTPushFront(&plist, 7);  // 头插7
	SLTPrint(plist);  // 打印链表内容

	// 尾部删除：删除链表最后一个节点
	SLTPopBack(&plist);
	SLTPrint(plist);  // 打印链表内容

	// 头部删除：删除链表第一个节点
	SLTPopFront(&plist);
	SLTPrint(plist);  // 打印链表内容

	// 查找指定位置元素
	SLTNode* found = SLTFind(plist, 2);  // 查找元素2的节点
	if (found) {
		printf("元素下标是: %d\n", found->data);  // 打印找到的元素
	}
	else {
		printf("没有找到\n");
	}

	// 在指定位置之前插入数据
	SLTInsert(&plist, plist->next, 5);  // 在第二个节点之前插入5
	SLTPrint(plist);  // 打印链表内容

	// 在指定位置之后插入数据
	SLTInsertAfter(plist->next->next, 7);  // 在第三个节点之后插入7
	SLTPrint(plist);  // 打印链表内容

	// 删除指定位置的节点
	SLTErase(&plist, plist->next);  // 删除第二个节点
	SLTPrint(plist);  // 打印链表内容

	// 删除指定位置之后的节点
	SLTEraseAfter(plist->next);  // 删除第三个节点之后的节点
	SLTPrint(plist);  // 打印链表内容
}

int main() {
	//SListTest01();  // 调用测试1函数
	SListTest02();  // 调用测试2函数
	return 0;
}

# 算法 # 数据结构 # 链表
Logo
乐奇 Rokid 开放社区

更多推荐

cover

面向逻辑思维的程序设计方法——人形机器人最佳训练场景

avatar 乐奇 Rokid 开放社区
cover

支持国产硬件的AR巡检系统哪家好

avatar 乐奇 Rokid 开放社区
cover

AR巡检哪家好

avatar 乐奇 Rokid 开放社区