当前位置： 首页 > news >正文

单链表：多米诺骨牌的奇妙旅程

news 2025/7/5 10:01:11

1.多米诺骨牌的结构定义

角色和工具：

你----首席设计师（通常在main函数中）:手握关键的设计蓝图

SLTNode* phead : 蓝图上的红色“起点标记”，指向第一块骨牌。若蓝图为空(phead = NULL)，则表示桌上无骨牌。

SLTNode : 一块精心设计的骨牌

data : 骨牌上的数字

next : 骨牌的“瞄准器”，指向倒下后将撞倒的下一块骨牌的位置。若是最后一块，瞄准器指向“虚无”(NULL)。

SLTNode**  pphead(万能修改笔) :一种特权工具，当函数(助理)需要直接修改你蓝图上的“起点标记”本身(即改变phead指向何处)时，你必须通过传递&phead(“起点标记”在蓝图上的存储位置)将万能修改笔交给助理，助理拿到的就是pphead。

//定义骨牌上面的数字类型
typedef int SLTDataType;
//结构定义
typedef struct SListNode
{SLDataType data;//骨牌上面的数字struct SListNode* next;//内置“瞄准器”（指向下一块骨牌）
｝SLTNode;

data:存储骨牌上的独特数字 

next:一个指针，存储下一块SLTNode骨牌在内存中的地址，若为最后一块，next为NULL。

红色起点标记        骨牌1              骨牌2              骨牌3🚩       +------+------+    +------+------+    +------+------+phead ---> | 数据 | 瞄准 |--->| 数据 | 瞄准 |--->| 数据 | NULL |+------+------+    +------+------+    +------+------+

 phead就像一个红色箭头，永远指向第一块骨牌。每块骨牌上都有一个数字，还有一个小箭头指向下一块骨牌。最后一块骨牌的箭头指向虚无(NULL)，表示链表结束。

2.多米诺骨牌的核心操作

设定：

assert( )：安全检查员，条件为假时停止程序并报告错误，调试时非常有用

malloc( )：向“骨牌工厂”(内存堆)申请空间制造新骨牌

free( )：将不再需要的骨牌送回工厂回收

标记起点(SLTNode* phead)

设计师在摆放阵列时，首先会在蓝图上指定"起点标记"phead。

//在main函数中，你的蓝图
SLTNode* phead = NULL;//最初，蓝图为空，桌上无骨牌，“起点标记”指向虚无

 phead是一个SLTNode*类型的一级指针。

它不属于任何骨牌，是你用来标记第一块骨牌位置的独立工具。

2.1 创建一块新骨牌

SLTNode* SLTbuyNode(SLTDataType x) {//从工厂定制新骨牌SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));//⚠️工厂资源不足if (newnode == NULL) {perror("骨牌制造失败(malloc failed)!");exit(1);}//为骨牌添加数字x并初始化瞄准器new->data = x;new->next = NULL;//瞄准器暂指向虚无return newnode;//全新骨牌出厂
}

2.2 查看整个多米诺阵列（打印链表）

void SLTPrint(SLTNode* phead) {
//从第一块骨牌开始检查SLTNode* pcur = phead;while(pcur) {printf("%d -> ", pcur->data); //打印当前骨牌数字pcur = pcur->next; //顺着瞄准器看下一块}printf("NULL\n");
}

 2.3 在最前面添加骨牌   (头插)

【开始状态】+------+------+              +------+------+
🚩---> |  2   | next |------------> |  3   | next |---> NULL+------+------+              +------+------+【创建新骨牌】
+------+------+
|  1   | next |---> NULL  <- 新骨牌
+------+------+【调整新骨牌的next指针】
+------+------+              +------+------+              +------+------+
|  1   | next |------------> |  2   | next |------------> |  3   | next |---> NULL
+------+------+              +------+------+              +------+------+【使用万能修改笔修改起点标记】+------+------+              +------+------+              +------+------+
🚩---> |  1   | next |------------> |  2   | next |------------> |  3   | next |---> NULL+------+------+              +------+------+              +------+------+

1）创建新骨牌；

2）让新骨牌的next指针指向原来的第一块；

3）移动起点标记，让它指向新骨牌（使用万能修改笔）。 

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead); // 确保万能修改笔有效// 1⃣ 创建新骨牌SLTNode* newnode = SLTbuyNode(x);// 2⃣ 调整新骨牌的next指针，指向原来的第一块骨牌// *pphead表示原始的phead值，即原来第一块骨牌newnode->next = *pphead;// 3⃣ 使用万能修改笔，修改起点标记指向新骨牌*pphead = newnode;// 这一步是关键！通过*pphead修改了主函数中的phead
}

2.4 在末尾添加新骨牌（尾插）

【情况1：桌面上没有骨牌】
🚩---> NULL (空桌面)【创建并放置第一块骨牌】+------+------+
🚩---> |  1   | next |---> NULL  <- 需要万能修改笔！✏️+------+------+【情况2：已有骨牌】+------+------+              +------+------+
🚩---> |  1   | next |------------> |  2   | next |---> NULL+------+------+              +------+------+【创建新骨牌】
+------+------+
|  3   | next |---> NULL  <- 新骨牌
+------+------+【寻找最后一块骨牌】+------+------+              +------+------+
🚩---> |  1   | next |------------> |  2   | next |---> NULL <- 找到！+------+------+              +------+------+^|ptail【调整最后一块骨牌的next指针】+------+------+              +------+------+              +------+------+
🚩---> |  1   | next |------------> |  2   | next |------------> |  3   | next |---> NULL+------+------+              +------+------+              +------+------+^                             ^|                             |ptail                    ptail->next = newnode

1)桌面上没有骨牌(需要万能修改笔)；

2)已有骨牌(需要找到最后一块并调整其next指针)。

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead); // 确保万能修改笔有效// 1⃣ 创建新骨牌SLTNode* newnode = SLTbuyNode(x);// 2⃣ 处理特殊情况：桌面上没有骨牌if (*pphead == NULL){// 使用万能修改笔，将起点标记指向新骨牌*pphead = newnode;}else {// 3⃣ 寻找最后一块骨牌SLTNode* ptail = *pphead; // 从第一块开始找while (ptail->next) // 当next指针不是指向虚无时{ptail = ptail->next; // 移动到下一块骨牌}// 4⃣ 调整最后一块骨牌的next指针，指向新骨牌ptail->next = newnode;}
}

2.5 头部移除骨牌（头删）

【开始状态】+------+------+              +------+------+              +------+------+
🚩---> |  1   | next |------------> |  2   | next |------------> |  3   | next |---> NULL+------+------+              +------+------+              +------+------+【记住第二块骨牌】+------+------+              +------+------+              +------+------+
🚩---> |  1   | next |------------> |  2   | next |------------> |  3   | next |---> NULL+------+------+              +------+------+              +------+------+^| next【移除第一块骨牌】💥 砰！💥                    +------+------+              +------+------+|  2   | next |------------> |  3   | next |---> NULL+------+------+              +------+------+^| next【使用万能修改笔修改起点标记】+------+------+              +------+------+🚩--------------------->     |  2   | next |------------> |  3   | next |---> NULL+------+------+              +------+------+

1）记住第二块骨牌的位置（next）；

2）移除第一块骨牌；

3）移动起点标记，让他指向原来的第二块骨牌（需要使用万能修改笔）。

void SLTPopFront(SLTNode** pphead)
{// 确保万能修改笔有效且桌上有骨牌assert(pphead && *pphead);// 1⃣ 记住第二块骨牌的位置(next)SLTNode* next = (*pphead)->next;// 2⃣ 移除第一块骨牌free(*pphead); // 骨牌爆炸！💥// 3⃣ 使用万能修改笔修改起点标记// 让起点标记指向原来的第二块骨牌*pphead = next;
}

 2.6 移除阵列末尾的骨牌（尾删）

【情况1：只有一块骨牌】+------+------+
🚩---> |  1   | next |---> NULL+------+------+【移除唯一骨牌】💥 砰！💥【使用万能修改笔修改起点标记】
🚩---> NULL (空桌面)  <- 需要万能修改笔！✏️【情况2：多块骨牌】+------+------+              +------+------+              +------+------+
🚩---> |  1   | next |------------> |  2   | next |------------> |  3   | next |---> NULL+------+------+              +------+------+              +------+------+【找到倒数第二块骨牌】+------+------+              +------+------+              +------+------+
🚩---> |  1   | next |------------> |  2   | next |------------> |  3   | next |---> NULL+------+------+              +------+------+              +------+------+^                             ^|                             |prev                          ptail【调整倒数第二块骨牌的next指针，移除最后一块】+------+------+              +------+------+
🚩---> |  1   | next |------------> |  2   | next |---> NULL    💥 砰！💥+------+------+              +------+------+              ^|prev->next = NULL

1）只有一块骨牌（相当于头删）；

2）有多块骨牌（需要找到倒数第二块，调整其next指针，然后移除最后一块） 

void SLTPopBack(SLTNode** pphead)
{// 确保万能修改笔有效且桌上有骨牌assert(pphead && *pphead);// 1⃣ 处理特殊情况：只有一块骨牌if ((*pphead)->next == NULL){free(*pphead); // 骨牌爆炸！💥*pphead = NULL; // 使用万能修改笔将起点标记指向虚无}else {// 2⃣ 找到倒数第二块骨牌SLTNode* prev = NULL; // 前一块骨牌SLTNode* ptail = *pphead; // 当前骨牌while (ptail->next) // 当next指针不是指向虚无时{prev = ptail; // 记住前一块骨牌ptail = ptail->next; // 移动到下一块骨牌}// 3⃣ 调整倒数第二块骨牌的next指针，指向虚无prev->next = NULL;// 4⃣ 移除最后一块骨牌free(ptail); // 骨牌爆炸！💥ptail = NULL; // 安全起见，将指针置空}
}

2.7 骨牌寻宝之旅（查找）

【寻找数字为2的骨牌】+------+------+              +------+------+              +------+------+
🚩---> |  1   | next |------------> |  2   | next |------------> |  3   | next |---> NULL+------+------+              +------+------+              +------+------+🔍                            🔍                            🔍"不是2"                      "找到2！"                      "不需要看了"pcur = pcur->next          return pcur

查找操作过程： 查找就像一次寻宝之旅，从第一块骨牌开始，沿着next指针挨个检查骨牌上的数字，直到找到目标或者到达队伍末尾。

SLTNode* SLTFind(SLTNode* phead,SLTDataType x)
{//准备好探险家（不需要万能修改笔，因为不修改链表）SLTNode* pcur = phead;//从第一块骨牌开始，逐块检查while(pcur){//检查当前骨牌上的数字是不是我们要找的if(pcur->next == x){return pcur;//找到了！返回这块骨牌} 移动到下一块骨牌pcur = pcur->next;}//遍历完所有骨牌都没有找到return NULL;}

2.8 在指定位置前插入骨牌

 

【开始状态】(要在数字2前插入)+------+------+              +------+------+              +------+------+
🚩---> |  1   | next |------------> |  2   | next |------------> |  3   | next |---> NULL+------+------+              +------+------+              +------+------+^|pos【创建新骨牌】
+------+------+
|  1.5 | next |---> NULL  <- 新骨牌
+------+------+【找到pos前一块骨牌】+------+------+              +------+------+              +------+------+
🚩---> |  1   | next |------------> |  2   | next |------------> |  3   | next |---> NULL+------+------+              +------+------+              +------+------+^                           ^|                           |prev                        pos【调整骨牌的next指针】+------+------+              +------+------+              +------+------+              +------+------+
🚩---> |  1   | next |------------> |  1.5 | next |------------> |  2   | next |------------> |  3   | next |---> NULL+------+------+              +------+------+              +------+------+              +------+------+^                           ^                            ^|                           |                            |prev                   newnode = prev->next             pos = newnode->next

前插操作过程： 前插就是在指定骨牌前面插入新骨牌。这需要先找到指定骨牌的前一块，然后调整next指针。如果指定骨牌是第一块，就变成了头插操作。

 

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{// 确保万能修改笔和目标位置都有效assert(pphead && pos);// 1⃣ 处理特殊情况：插入位置是第一块骨牌if (pos == *pphead){// 直接调用头插函数SLTPushFront(pphead, x);}else {// 2⃣ 创建新骨牌SLTNode* newnode = SLTbuyNode(x);// 3⃣ 找到pos前一块骨牌SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}// 4⃣ 调整骨牌的next指针// prev->newnode->posprev->next = newnode; // 前一块指向新骨牌newnode->next = pos;  // 新骨牌指向目标位置}
}

首先检查万能修改笔和目标位置是否有效。如果插入位置是第一块骨牌(pos == *pphead)，就直接调用头插函数。否则，创建新骨牌，然后找到pos前一块骨牌(prev)。接着调整next指针，将前一块指向新骨牌(prev->next = newnode)，新骨牌指向pos(newnode->next = pos)。

2.9 在指定位置之后插入骨牌

 

【开始状态】(要在数字1后插入)+------+------+              +------+------+              +------+------+
🚩---> |  1   | next |------------> |  2   | next |------------> |  3   | next |---> NULL+------+------+              +------+------+              +------+------+^|pos【创建新骨牌】
+------+------+
|  1.5 | next |---> NULL  <- 新骨牌
+------+------+【调整骨牌的next指针】+------+------+              +------+------+              +------+------+              +------+------+
🚩---> |  1   | next |------------> |  1.5 | next |------------> |  2   | next |------------> |  3   | next |---> NULL+------+------+              +------+------+              +------+------+              +------+------+^                           ^                            ^|                           |                            |pos                 newnode = pos->next        pos原来的next = newnode->next

后插就是在指定骨牌后面插入新骨牌。这比前插简单，因为我们已经有了前一块骨牌(pos)，只需调整next指针即可。

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{// 确保目标位置有效assert(pos);// 1⃣ 创建新骨牌SLTNode* newnode = SLTbuyNode(x);// 2⃣ 调整骨牌的next指针（这里顺序很重要！）// pos->newnode->pos原来指向的骨牌newnode->next = pos->next; // 先让新骨牌指向pos原来指向的骨牌pos->next = newnode;       // 再让pos指向新骨牌
}

首先确保目标位置有效，然后创建新骨牌。接着调整next指针，将新骨牌的next指针指向pos原来指向的骨牌(newnode->next = pos->next)，再将pos的next指针指向新骨牌(pos->next = newnode)。

为什么顺序很重要？ 如果先修改pos->next再修改newnode->next，新骨牌就会指向自己，形成环！正确的顺序是：先连接新骨牌的下一步，再调整前面的连接。

2.10 删除指定位置的骨牌

【开始状态】(要删除数字2)+------+------+              +------+------+              +------+------+
🚩---> |  1   | next |------------> |  2   | next |------------> |  3   | next |---> NULL+------+------+              +------+------+              +------+------+^|pos【找到pos前一块骨牌】+------+------+              +------+------+              +------+------+
🚩---> |  1   | next |------------> |  2   | next |------------> |  3   | next |---> NULL+------+------+              +------+------+              +------+------+^                           ^                            ^|                           |                            |prev                        pos                        pos->next【调整前一块骨牌的next指针，移除pos骨牌】+------+------+                                          +------+------+
🚩---> |  1   | next |----------------------------------------> |  3   | next |---> NULL+------+------+                                          +------+------+^                                                       ^|                                                       |prev                                                 prev->next = pos->next💥 砰！💥 (pos骨牌被移除)

 删除指定骨牌需要先找到它的前一块，然后调整前一块的next指针，跳过要删除的骨牌，直接指向后面的骨牌。如果要删除的是第一块骨牌，就变成了头删操作。

void SLTErase(SLTNode** pphead, SLTNode* pos)
{// 确保万能修改笔和目标位置都有效assert(pphead && pos);// 1⃣ 处理特殊情况：删除第一块骨牌if (pos == *pphead){// 直接调用头删函数SLTPopFront(pphead);}else {// 2⃣ 找到pos前一块骨牌SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}// 3⃣ 调整前一块骨牌的next指针// prev->pos->pos的下一块 变成 prev->pos的下一块prev->next = pos->next;// 4⃣ 移除pos骨牌free(pos); // 骨牌爆炸！💥pos = NULL; // 安全起见，将指针置空}
}

首先检查万能修改笔和目标位置是否有效。如果要删除的是第一块骨牌(pos == *pphead)，就直接调用头删函数。否则，找到pos前一块骨牌(prev)，调整其next指针指向pos后面的骨牌(prev->next = pos->next)，然后释放pos骨牌。

2.11 删除指定位置后的骨牌

【开始状态】(要删除数字1后面的骨牌，即数字2)+------+------+              +------+------+              +------+------+
🚩---> |  1   | next |------------> |  2   | next |------------> |  3   | next |---> NULL+------+------+              +------+------+              +------+------+^                           ^                            ^|                           |                            |pos                         del                        del->next【找到要删除的骨牌】+------+------+              +------+------+              +------+------+
🚩---> |  1   | next |------------> |  2   | next |------------> |  3   | next |---> NULL+------+------+              +------+------+              +------+------+^                           ^|                           |pos                    del = pos->next【调整pos的next指针，移除del骨牌】+------+------+                                          +------+------+
🚩---> |  1   | next |----------------------------------------> |  3   | next |---> NULL+------+------+                                          +------+------+^                                                       ^|                                                       |pos                                                 pos->next = del->next💥 砰！💥 (del骨牌被移除)

void SLTEraseAfter(SLTNode* pos)
{// 确保目标位置有效且其后有骨牌assert(pos && pos->next);// 1⃣ 记住要删除的骨牌SLTNode* del = pos->next;// 2⃣ 调整pos的next指针// pos->del->del的下一块 变成 pos->del的下一块pos->next = del->next;// 3⃣ 移除del骨牌free(del); // 骨牌爆炸！💥del = NULL; // 安全起见，将指针置空
}

首先确保目标位置有效且其后有骨牌。然后记住要删除的骨牌(del = pos->next)。接着调整pos的next指针，指向del后面的骨牌(pos->next = del->next)。最后释放del骨牌。

2.12 销毁整个骨牌系统

【开始状态】+------+------+              +------+------+              +------+------+
🚩---> |  1   | next |------------> |  2   | next |------------> |  3   | next |---> NULL+------+------+              +------+------+              +------+------+^                           ^                             |                           |                            pcur                        next                      【第一轮：释放第一块骨牌】💥 砰！💥                    +------+------+              +------+------+|  2   | next |------------> |  3   | next |---> NULL+------+------+              +------+------+^                           ^|                           |pcur                        next【第二轮：释放第二块骨牌】💥 砰！💥                   +------+------+|  3   | next |---> NULL+------+------+^|pcur = next【第三轮：释放最后一块骨牌】💥 砰！💥pcur = NULL【使用万能修改笔修改起点标记】
🚩---> NULL (完全清空)

销毁就是从头到尾逐一释放所有骨牌。关键是在释放当前骨牌之前，先记住下一块骨牌的位置。最后，将起点标记指向NULL表示链表为空。

void SLTDestroy(SLTNode** pphead)
{assert(pphead);// 从第一块骨牌开始SLTNode* pcur = *pphead;// 遍历并释放所有骨牌while (pcur){// 记住下一块骨牌的位置SLTNode* next = pcur->next;// 释放当前骨牌free(pcur); // 骨牌爆炸！💥// 移动到下一块骨牌pcur = next;}// 使用万能修改笔将起点标记指向NULL*pphead = NULL;
}

首先确保万能修改笔有效。然后从第一块骨牌开始遍历链表。在每一轮循环中，先记住下一块骨牌的位置(next = pcur->next)，然后释放当前骨牌(free(pcur))，最后移动到下一块骨牌(pcur = next)。循环直到处理完所有骨牌(pcur = NULL)。最后，使用万能修改笔将起点标记设为NULL，表示链表为空。

3.总结

时间复杂度特点

  1. 头部操作高效：所有头部操作（添加/删除）均为O(1)时间复杂度，无需遍历链表

  2. 尾部操作耗时：尾部操作（添加/删除）均为O(n)时间复杂度，需要遍历至链表末尾

  3. 已知位置优势：在已知节点位置时，操作效率高

    • 已知节点后插入/删除：O(1)

    • 已知节点前操作：需要找到前驱节点，仍为O(n)

  4. 查找操作线性：查找节点为O(n)，必须从头开始顺序查找，无法随机访问

操作时间复杂度说明
创建新节点 (SLTbuyNode)O(1)只需分配内存并初始化一个节点
从头部添加节点 (SLTPushFront)O(1)直接修改头指针和新节点指针
尾部添加节点 (SLTPushBack)O(n)需要遍历找到最后一个节点
特殊情况：空链表时为O(1)
头部移除节点 (SLTPopFront)O(1)只需修改头指针并释放第一个节点
尾部移除节点 (SLTPopBack)O(n)需要遍历找到倒数第二个节点
查找节点 (SLTFind)O(n)最坏情况需要遍历整个链表
在指定位置前插入节点 (SLTInsert)O(n)需要遍历找到前一个节点
特殊情况：在头部插入为O(1)
在指定位置后插入节点 (SLTInsertAfter)O(1)已有节点位置，直接修改指针
删除指定位置的节点 (SLTErase)O(n)需要遍历找到前一个节点
特殊情况：删除头节点为O(1)
删除指定位置后的节点 (SLTEraseAfter)O(1)已有前一个节点位置，直接修改指针
销毁链表 (SLTDestroy)O(n)需要遍历并释放整个链表的所有节点

结构特点

  1. 动态内存：链表节点动态分配内存，可根据需求增长或缩减

  2. 指针连接：节点通过next指针链接，形成线性结构

  3. 单向访问：单链表只能从头到尾单向访问

  4. 头指针关键：头指针是访问整个链表的唯一入口点

  5. 二级指针必要性：修改头指针需要使用二级指针，否则修改不会反映到主函数

优点

  1. 插入删除优势：已知位置时的插入删除非常高效，无需移动其他元素

  2. 内存利用灵活：不需要连续内存空间，适合动态变化的数据

  3. 查找劣势：不支持随机访问，查找效率低于数组

  4. 空间开销：每个节点需要额外的指针空间开销

单链表适合频繁在已知位置插入删除的场景，不适合需要随机访问或频繁查找的场景。

 

http://www.xdnf.cn/news/428257.html

相关文章：

  • Shinkai开源程序 是一个双击安装 AI 管理器（本地和远程），它允许您使用简单的 UI 在 5 分钟或更短的时间内创建 AI 代理
  • 量化感知训练与 PyTorch 的哪些事
  • 力扣-226.翻转二叉树
  • 51c嵌入式~电路~合集27
  • 整数和浮点数转换时的精度损失
  • 拓扑排序（竞赛）
  • 按键精灵ios脚本新增元素功能助力辅助工具开发（二）
  • 春秋云镜 Time Writeup
  • 面试中被问到谈谈你对threadlocal的理解
  • 2025年5月-信息系统项目管理师高级-软考高项一般计算题
  • 基于Session实现短信登录全流程详解
  • 数据治理的核心
  • 论文知识总结
  • 日常知识点之随手问题整理（vcpkg安装osgearth并进行测试简单整理）
  • 【Ubuntu】扩充磁盘大小
  • 求1+3+5+7+9+…,其和小于等于500 的最大项
  • Java线程池性能优化全解析：从配置到实践
  • Redis学习笔记
  • SAP Business One（B1）打开自定义对象报错【Failed to initialize document numbering:】
  • 大模型核心运行机制
  • 玩转ChatGPT：DeepSeek实战（统一所在地格式）
  • 基于STM32、HAL库的TDA7719TR音频接口芯片驱动程序设计
  • RK3568移植鸿蒙系统openharmony-5.1.0-release
  • 【愚公系列】《Manus极简入门》036-物联网系统架构师：“万物互联师”
  • 数据结构基础--蓝桥杯备考
  • 在Flutter上如何实现按钮的拖拽效果
  • Ceph 集群常用管理命令
  • esp32硬件支持AT指令
  • 什么类型的网站适合用WAF？Web应用防火墙的适用场景解析
  • Python(1) 做一个随机数的游戏