C語言：詳解單鏈表與例題

C語言：詳解單鏈表與例題

1.單鏈表的實現
2.例題：移除鏈表元素

1.單鏈表的實現

鏈表根據帶頭或不帶頭、單向或雙向、循環或不循環分類為8種，最常用的是單鏈表和雙向鏈表，單鏈表是 不帶頭單向不循環 鏈表。

鏈表由節點組成，節點分為兩部分，數據和指向下一節點的指針。

鏈表示意圖如下：
在這里插入圖片描述

創建頭文件SList.h，包含stdio.h、stdlib.h、assert.h，在文件中定義節點結構，聲明函數打印鏈表、尾/頭插、尾/頭刪、查找、定位前插入、定位后插入、刪除pos節點、刪除pos后節點、銷毀鏈表。

//SList.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
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);//頭刪SLTNode* SLTFind(SLTNode* phead, SLTDataType x);//查找void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//定位前插入void SLTInsertAfter(SLTNode* pos, SLTDataType x);//定位后插入void SLTErase(SLTNode** pphead, SLTNode* pos);//刪除pos節點void SLTEraseAfter(SLTNode* pos);//刪除pos后一個節點void SListDesTroy(SLTNode** pphead);//銷毀鏈表

創建SList.c文件，在文件中編寫函數。

打印鏈表：定義一個指針pcur指向鏈表首節點，遍歷并打印。
在這里插入圖片描述
在這里插入圖片描述

void SLTPrint(SLTNode* phead)//打印
{SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}

創建節點：接下來的函數在使用時常常需要創建節點，所以另寫一個函數用于創建節點。用malloc函數動態開辟空間，定義指針newnode指向這塊空間，把所需的數據和指向下一個節點指針賦給data和next。

SLTNode* SLTBuyNode(SLTDataType x)//創建節點
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}

尾插：尾插的關鍵是找到最后一個節點，讓這個尾節點的指向下一節點的指針next不再指向NULL，而是指向新節點newnode，此時newnode成為新的尾節點，所以最后還要讓newnode指向NULL。
在這里插入圖片描述

void SLTPushBack(SLTNode** pphead, SLTDataType x)//尾插
{                                                //*pphead為指向第一個節點的指針assert(pphead);SLTNode* newnode = SLTBuyNode(x);if (*pphead == NULL)//若為空鏈表*pphead = newnode;else //若為非空鏈表{SLTNode* ptail = *pphead;while (ptail->next)  //找尾ptail = ptail->next;ptail->next = newnode;}
}

尾插函數SLTPushBack的一個參數是二級指針，這個參數表示我們傳過去的是指向第一個節點的指針的地址。假設用的是一級指針phead，指向鏈表第一個節點的指針為plist，plist是實參，phead為形參，當為空鏈表時，phead被賦值為newnode，出了函數后形參phead被銷毀，實參plist仍指向NULL。

所以，要使形參的改變影響實參，就要傳地址。

頭插：先讓創建的新節點newnode的next指針指向原鏈表的第一個節點，再讓指向原鏈表第一個節點指針pphead指向newnode即可。這兩步的先后順序不可調換，若先讓pphead指向newnode，就無法找到原鏈表的第一個節點。
在這里插入圖片描述

void SLTPushFront(SLTNode** pphead, SLTDataType x)//頭插
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}

尾刪：定義指針ptail，把*pphead賦值ptail，用ptail遍歷鏈表，使ptail指向最后一個節點，然后用free釋放ptail指向的節點。這時還需要一個指針prev指向ptail指向節點的上一個節點，在尾節點被釋放后，prev指向的節點的next置為NULL。
在這里插入圖片描述
在這里插入圖片描述
在這里插入圖片描述

void SLTPopBack(SLTNode** pphead)//尾刪
{assert(pphead && *pphead);   //鏈表不為空if ((*pphead)->next == NULL) //只有一個節點{free(*pphead);*pphead = NULL;}else      //不止一個節點{SLTNode* prev = *pphead;SLTNode* ptail = *pphead;while (ptail->next)  //使ptail指向最后一個節點{prev = ptail;ptail = ptail->next;}free(ptail);ptail = NULL;prev->next = NULL;}
}

頭刪：定義指針next保存鏈表的第二個節點，釋放第一個節點后再把next賦值給*pphead。

void SLTPopFront(SLTNode** pphead)//頭刪
{assert(pphead && *pphead);SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}

查找節點：假設要找到data為x的節點，讓指針pcur=phead，遍歷鏈表，直到pcur->data等于x，找到了返回指向該節點的指針，沒找到返回NULL。

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)//查找
{SLTNode* pcur = phead;while (pcur){if (pcur->data == x)return pcur;  //找到了pcur = pcur->next;}return NULL;
}

定位前插入：給一個指向某個節點指針pos，若pos指向的是第一個節點，直接調用頭插函數SLTPushFront；若pos指向的不是第一個節點，則定義指針prev，遍歷鏈表，使prev指向pos指向節點的上一節點，然后插入新節點。
在這里插入圖片描述

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
//定位前插入，即pos之前插入，通過SLTFind得到pos
{assert(pphead && *pphead);assert(pos);SLTNode* newnode = SLTBuyNode(x);if (pos == *pphead)SLTPushFront(pphead, x);//頭插else{SLTNode* prev = *pphead;while (prev->next != pos)//找到pos,pos的前一個節點為prevprev = prev->next;newnode->next = pos;prev->next = newnode;}
}

定位后插入：給一個指向某個節點指針pos，在pos指向的節點和pos->next指向的節點之間插入新節點newnode即可。

void SLTInsertAfter(SLTNode* pos, SLTDataType x)//定位后插入，即pos后插入
{assert(pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;
}

刪除pos節點：給一個指向某個節點指針pos，定義指針prev，遍歷鏈表，使prev指向pos指向節點的上一節點，再讓prev指向pos后的節點，最后free釋放pos。
在這里插入圖片描述

void SLTErase(SLTNode** pphead, SLTNode* pos)//刪pos節點
{assert(pphead && *pphead);assert(pos);if (pos == *pphead)     //pos為頭節點SLTPopFront(pphead);//頭刪else     //pos不為頭節點{SLTNode* prev = *pphead;while (prev->next != pos)prev = prev->next;prev->next = pos->next;//prev  pos  pos->nextfree(pos);pos = NULL;}
}

刪除pos之后節點：先定義指針del指向pos之后節點，在用free釋放del之前，先pos->next指向del->next指向的節點，最后即可釋放del。

void SLTEraseAfter(SLTNode* pos)//刪pos之后的節點
{assert(pos && pos->next);SLTNode* del = pos->next;pos->next = del->next;//pos  del  del->nextfree(del);del = NULL;
}

銷毀鏈表：循環遍歷鏈表，循環一次，銷毀一次。

void SListDesTroy(SLTNode** pphead)//銷毀鏈表
{assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur)  //循環一次，銷毀一個節點{SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

在SList.c文件中代碼如下：

//SList.c
#include"SList.h"
void SLTPrint(SLTNode* phead)//打印
{SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}
SLTNode* SLTBuyNode(SLTDataType x)//創建節點
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;return newnode;
}
void SLTPushBack(SLTNode** pphead, SLTDataType x)//尾插
{                                                //*pphead為指向第一個節點的指針assert(pphead);SLTNode* newnode = SLTBuyNode(x);if (*pphead == NULL)//若為空鏈表*pphead = newnode;else //若為非空鏈表{SLTNode* ptail = *pphead;while (ptail->next)  //找尾ptail = ptail->next;ptail->next = newnode;}
}
void SLTPushFront(SLTNode** pphead, SLTDataType x)//頭插
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}
void SLTPopBack(SLTNode** pphead)//尾刪
{assert(pphead && *pphead);   //鏈表不為空if ((*pphead)->next == NULL) //只有一個節點{free(*pphead);*pphead = NULL;}else      //不止一個節點{SLTNode* prev = *pphead;SLTNode* ptail = *pphead;while (ptail->next)  //使ptail指向最后一個節點{prev = ptail;ptail = ptail->next;}free(ptail);ptail = NULL;prev->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;
}
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)//定位前插入，即pos之前插入，通過SLTFind得到pos
{assert(pphead && *pphead);assert(pos);SLTNode* newnode = SLTBuyNode(x);if (pos == *pphead)SLTPushFront(pphead, x);//頭插else{SLTNode* prev = *pphead;while (prev->next != pos)//找到pos,pos的前一個節點為prevprev = prev->next;newnode->next = pos;prev->next = newnode;}
}
void SLTInsertAfter(SLTNode* pos, SLTDataType x)//定位后插入，即pos后插入
{assert(pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next = newnode;
}
void SLTErase(SLTNode** pphead, SLTNode* pos)//刪pos節點
{assert(pphead && *pphead);assert(pos);if (pos == *pphead)     //pos為頭節點SLTPopFront(pphead);//頭刪else     //pos不為頭節點{SLTNode* prev = *pphead;while (prev->next != pos)prev = prev->next;prev->next = pos->next;//prev  pos  pos->nextfree(pos);pos = NULL;}
}
void SLTEraseAfter(SLTNode* pos)//刪pos之后的節點
{assert(pos && pos->next);SLTNode* del = pos->next;pos->next = del->next;//pos  del  del->nextfree(del);del = NULL;
}
void SListDesTroy(SLTNode** pphead)//銷毀鏈表
{assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur)  //循環一次，銷毀一個節點{SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

創建test.c文件進行測試。

例如：測試頭插和尾插

#include"SList.h"
void test1()
{SLTNode* phead = NULL;SLTPushBack(&phead, 2);SLTPushFront(&phead, 1);SLTPrint(phead);SListDesTroy(&phead);
}
int main()
{test1()return 0;
}

在這里插入圖片描述

2.例題：移除鏈表元素

給一個鏈表的頭節點head和一個整數val，刪除鏈表中所有滿足Node.data==val的節點，返回新的頭節點，節點數目在[ 0, 10^4 ]內。
例如：

  • 輸入 head=[1,2,6,3,4,5,6]，val=6
  • 輸出 [ 1,2,3,4,5 ]

方法：找值不為val的節點，尾插到新鏈表中。

#include<stdio.h>
typedef struct ListNode  //節點結構體
{int data;struct ListNode* next;
}ListNode;
ListNode* removeElements(ListNode* head,int val)
{ListNode* newHead;ListNode* newTail;  //定義兩個指向節點的指針newHead=newTail=NULL;ListNode* pcur=head;  //遍歷原鏈表while(pcur)  //pcur指向尾節點時跳出循環{if(pcur->data!=val){if(newHead==NULL)newHead=newTail=pcur;else{newTail->next=pcur;newTail=newTail->next;}}pcur=pcur->next;}if(newTail)newTail->next=NULL;return newHead;
}

以head=[1,2,6,3,4,5,6]，val=6為例分析：
在這里插入圖片描述
在這里插入圖片描述
在這里插入圖片描述
此時pcur->data==6，第三次循環后newTail不移動，pcur->data為3。

在這里插入圖片描述
在這里插入圖片描述
在這里插入圖片描述
第七次循環后，pcur為NULL，newTail不移動，跳出循環，newTail->next賦為NULL。

在這里插入圖片描述
構建的新鏈表如下：
在這里插入圖片描述
輸入head=[1,2,6,3,4,5,6]，val=6，vs2022中結果如圖：
在這里插入圖片描述

拙作一篇，望諸位同道不吝斧正。

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/diannao/93564.shtml
繁體地址，請注明出處：http://hk.pswp.cn/diannao/93564.shtml
英文地址，請注明出處：http://en.pswp.cn/diannao/93564.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

從0開始學習R語言--Day62--RE插補

從0開始學習R語言--Day62--RE插補

對于會有多次測量值的數據&#xff0c;用普通的回歸去插補&#xff0c;往往會忽略掉數據個體本身的特點&#xff0c;畢竟多次的測量值其實就代表了數據個體的不穩定性&#xff0c;存在額外的干擾。而RE的插補原理是結合個體本身的隨機效應和群體的固體效應再加上截距進行插補的…
閱讀更多...
RESTful API開發指南：使用Spring Boot構建企業級接口

RESTful API開發指南：使用Spring Boot構建企業級接口

目錄 1. 引言2. RESTful API基礎概念3. Spring Boot環境搭建4. 項目結構設計5. 核心組件開發6. 數據庫集成7. 安全認證8. 異常處理9. API文檔生成10. 測試策略11. 部署與監控12. 最佳實踐 1. 引言 在現代軟件開發中&#xff0c;RESTful API已成為構建分布式系統和微服務架構…
閱讀更多...
從 Print 到 Debug：用 PyCharm 掌控復雜程序的調試之道

從 Print 到 Debug：用 PyCharm 掌控復雜程序的調試之道

目錄摘要調試工具窗口會話工具欄調試工具欄單步工具欄調試器選項卡調用棧幀&#xff08;Frames&#xff09;變量&#xff08;Variables&#xff09;&#x1f4a1; 表達式求值區域&#xff08;Evaluate expression field&#xff09;&#x1f5b1;? 右鍵菜單&#xff08;Contex…
閱讀更多...
用于前列腺活檢分級的分層視覺 Transformer：邁向彌合泛化差距|文獻速遞-醫學影像算法文獻分享

用于前列腺活檢分級的分層視覺 Transformer：邁向彌合泛化差距|文獻速遞-醫學影像算法文獻分享

Title題目Hierarchical Vision Transformers for prostate biopsy grading: Towardsbridging the generalization gap用于前列腺活檢分級的分層視覺 Transformer&#xff1a;邁向彌合泛化差距01文獻速遞介紹前列腺癌是全球男性中第二常見的確診癌癥&#xff0c;也是第五大致命癌…
閱讀更多...
Apple基礎（Xcode②-Flutter結構解析）

Apple基礎（Xcode②-Flutter結構解析）

&#x1f3d7;? 目錄結構速查表&#xff08;your_project/ios/ 下&#xff09;ios/ ├── Runner/ ← 原生 iOS 工程根目錄&#xff08;Xcode 打開它&#xff09; │ ├── AppDelegate.swift ← App 入口&#xff08;類似 Android 的 MainActivity&…
閱讀更多...
X00229-基于深度強化學習的車聯網資源分配python完整

X00229-基于深度強化學習的車聯網資源分配python完整

X00229-基于深度強化學習的車聯網資源分配python完整
閱讀更多...
面向多模態自監督學習的共享表示與獨有表示解耦

面向多模態自監督學習的共享表示與獨有表示解耦

通俗說法&#xff1a;在多模態自監督學習中&#xff0c;將共享信息和獨有信息分離開來 Abstract 問題&#xff1a; 傳統方法通常假設在訓練和推理階段都可以訪問所有模態信息&#xff0c;這在實際應用中面對模態不完整輸入時會導致性能顯著下降。 解決方法&#xff1a;提出了一…
閱讀更多...
【iOS】weak修飾符

【iOS】weak修飾符

前言前面我們已經學習了解了sideTable&#xff0c;今天來看看在OC中&#xff0c;sideTable是如何在我們使用weak時工作的。在OC中&#xff0c;weak修飾符是一種用于聲明“弱引用”的關鍵字&#xff0c;其核心特性是不參與對象的引用計數管理&#xff0c;而且當被引用的對象被釋…
閱讀更多...
【JVM篇10】：三種垃圾回收算法對比詳解

【JVM篇10】：三種垃圾回收算法對比詳解

文章目錄1. 標記-清除算法2. 復制算法3. 標記-整理算法總結與面試要點在通過 可達性分析等算法識別出所有存活對象和垃圾對象后&#xff0c;垃圾收集器&#xff08;GC&#xff1a;Garbage Collector&#xff09;就需要執行回收操作來釋放垃圾對象所占用的內存。以下是三種最基礎…
閱讀更多...
JXD進步25.7.30

JXD進步25.7.30

1.為啥是update&#xff0c;因為你if判斷有問題。或者是你上來就給id賦值了。2. 這個是清空network歷史3.斷點位置打在這里&#xff1a;打在上面它進不來4.
閱讀更多...
Flutter開發實戰之網絡請求與數據處理

Flutter開發實戰之網絡請求與數據處理

第6章：網絡請求與數據處理 “數據是應用的血液，網絡是連接世界的橋梁。” 在移動應用開發中，與服務器進行數據交互是必不可少的功能。無論是獲取用戶信息、提交表單數據，還是上傳圖片、下載文件，都離不開網絡請求。本章將帶你深入掌握Flutter中的網絡編程技巧。 6.1 網絡…
閱讀更多...
快速分頁實現熱點功能-索引和order by

快速分頁實現熱點功能-索引和order by

需求:分頁求出進三天的發布視頻的權重熱度 權重 / 衰減時間 衰減時間 當前時間 - 視頻發布時間 小根堆來實現這個公式可以很好的利用半衰期來進行解決難點:如果一次性加載太多到springBoot服務器里面會造成堆內存占用過多&#xff0c;分頁又有可能造成深分頁問題&#xff0c;…
閱讀更多...
HAProxy（高可用性代理）

HAProxy（高可用性代理）

1 HAProxy 簡介 HAProxy&#xff08; High Availability Proxy&#xff09;是一個高性能的負載均衡器和代理服務器&#xff0c;為基于 TCP 和 HTTP 的應用程序提供高可用性、負載平衡和代理&#xff0c;廣泛應用于提高 web 應用程序的性能和可靠性。它支持多種協議&#xff0c…
閱讀更多...
Vulnhub靶場:ica1

Vulnhub靶場:ica1

一、信息收集nmap掃描一下IP。&#xff08;掃不出來的可以看一下前面幾篇找ip的步驟&#xff09;下面給了框架的版本是9.2的&#xff0c;我們去kali里搜一下有沒有已經公開的漏洞。searchsploit qdPM 9.2 locate 50176.txt more /usr/share/exploitdb/exploits/php/webapps/50…
閱讀更多...
【Dv3admin】ORM數據庫無法查詢的問題

【Dv3admin】ORM數據庫無法查詢的問題

Django 運行過程中&#xff0c;數據庫連接的健康狀態直接影響應用的穩定性和數據訪問準確性。長時間空閑的數據庫連接經常因外部機制被回收&#xff0c;進而引發數據查詢異常和返回無效結果。 本文圍繞 Django 中數據庫連接長時間空閑導致的連接失效問題&#xff0c;介紹相關的…
閱讀更多...
使用 Flownex 對機械呼吸機進行建模

使用 Flownex 對機械呼吸機進行建模

當患者無法獨立呼吸時&#xff0c;機械呼吸機通過氣管插管將富氧空氣輸送到患者的肺部。肺是敏感而復雜的器官&#xff0c;因此在無法忍受的壓力和體積范圍內提供空氣&#xff0c;根據每分鐘所需的呼吸次數計時&#xff0c;并適當加濕和加熱。機械呼吸機的精確建模對于其安全有…
閱讀更多...
力扣刷題日常(7-8)

力扣刷題日常(7-8)

力扣刷題日常(7-8) 第7題: 整數反轉(難度: 中等) 原題: 給你一個 32 位的有符號整數 x ,返回將 x 中的數字部分反轉后的結果. 如果反轉后整數超過 32 位的有符號整數的范圍 [?231, 231 ? 1] ,就返回 0. 假設環境不允許存儲 64 位整數&#xff08;有符號或無符號&#xff09;.…
閱讀更多...
串口接收數據包（協議帶幀頭幀尾）的編程實現方法：1、數據包格式定義結構體2、使用隊列進行數據接收、校驗解包

串口接收數據包（協議帶幀頭幀尾）的編程實現方法：1、數據包格式定義結構體2、使用隊列進行數據接收、校驗解包

這種帶幀頭幀尾的數據包處理流程可以簡單概括為 “識別邊界→提取有效數據→驗證完整性” 三個核心步驟&#xff0c;具體操作如下&#xff1a;1. 數據包格式定義&#xff08;先約定規則&#xff09;首先明確一個 “合格數據包” 的結構&#xff0c;比如&#xff1a; 幀頭&#…
閱讀更多...
JSON 對象封裝教程

JSON 對象封裝教程

JSON 對象封裝方法在 Java 中封裝 JSON 對象通常使用第三方庫&#xff0c;如 org.json、Gson 或 Jackson。以下是幾種常見的方法&#xff1a;使用 org.json 庫添加 Maven 依賴&#xff1a;<dependency><groupId>org.json</groupId><artifactId>json<…
閱讀更多...
【WRF-Chem】EDGAR 排放數據處理：分部門合并轉化為二進制（Python全代碼）

【WRF-Chem】EDGAR 排放數據處理：分部門合并轉化為二進制（Python全代碼）

目錄 process.py process_biofl.py process_fossil.py process_micro.py process_sector.py 參考 process.py 讀取 EDGAR 排放數據庫中 2000 至 2023 年間不同行業的甲烷（CH?）排放數據，進行合并處理，并將總排放以二進制格式保存到文件中。 導入必要的庫 import numpy as n…
閱讀更多...
最新文章

Copyright @ 2022~2023