① 如何用C 實現鏈表的查找、插入和刪除
如何用C語言實現鏈表的查找、插入和刪除，用C語言實現鏈表的查找、插入和刪除的方法。
鏈表
C語言中鏈表有很多種，我們來講C語言中最主要的鏈表——單向鏈表和雙向鏈表的查找，插入，刪除的實現方法。
單向鏈表
單鏈表使用按值查找，從鏈表的首元結點出發，依次將結點值和給定值e進行比較，返回查找結果。
其中單鏈表的查找的演算法步驟是： 1.使用指針P指向首元結點 2.從首元結點開始依次順著鏈域next向下查找，只要指向當前結點的指針P不為空，並且P所指結點的數據域不等於給定的值e，則循環執行「p指向下一個結點操作。 3.返回P。若查找成功，p此時即為結點的地址值，若查找失敗，P返回NULL 具體代碼如下。
SingleLinkList.h typedef int status;typedef int ElemType; //鏈表節點及鏈表數據表示定義typedef struct SingleLinkNode{ElemType data;struct SingleLinkNode *next;}SingleLinkNode,*SingleLinkList;//以下是單向鏈表操作函數原型 //初始化操作status InitSingleLinkList(SingleLinkList l);//鏈表銷毀操作void DestroySingleLinkList(SingleLinkList l);//鏈表清除操作void ClearSingleLinkList(SingleLinkList l);//鏈表長度int SingleLinkListLength(SingleLinkList l); //鏈表是否為空bool SingleLinkListEmpty(SingleLinkList l); //取鏈表中的第i個元素status GetSingleLinkListElem(SingleLinkList l,int i,ElemType e); //在鏈表的第i個位置插入元素status InsertSingleLinkList(SingleLinkList l,int i,ElemType e);//刪除鏈表的第i個元素status DeleteSingleLinkList(SingleLinkList l,int i); //列印鏈表void PrintSingleLinkList(SingleLinkList l);
SingleLinkList //必須包含此文件，因為它包含此文件中要用到的數據表示定義//以下實現的是帶頭節點的單向鏈表#include"SingleLinkList.h"#include"stdlib.h"#include"iostream.h"//初始化操作status InitSingleLinkList(SingleLinkList l){ //if(l)free(l); if(l=(SingleLinkList)malloc(sizeof(SingleLinkNode)))//如果分配成功，設置節點{l-next=NULL;return 1;}elsereturn 0;//表示失敗 }//鏈表銷毀操作void DestroySingleLinkList(SingleLinkList l){SingleLinkList p=l,q;while(p){q=p-next ;free(p);p=q;} }//鏈表清除操作void ClearSingleLinkList(SingleLinkList l){SingleLinkList p=l-next ,q;while(p){q=p-next ;free(p);p=q;}l-next =NULL; }//鏈表長度int SingleLinkListLength(SingleLinkList l){SingleLinkList p=l-next ;int i=0;if(l==NULL)return 0;while(p)i++,p=p-next; return i; } //鏈表是否為空bool SingleLinkListEmpty(SingleLinkList l){ return (l-next==NULL); } //取鏈表中的第i個元素status GetSingleLinkListElem(SingleLinkList l,int i,ElemType e){ int k=0;SingleLinkList p=l-next;if(i1||iSingleLinkListLength(l)) return 0;//1,尋找第i個節點 while(pki)k++,p=p-next; e =p-data ;return 1; } //在鏈表的第i個位置插入元素status InsertSingleLinkList(SingleLinkList l,int i,ElemType e){int k=0;SingleLinkList p,q ;if(SingleLinkListLength(l)==0)InitSingleLinkList(l);p=l ;if(i1||iSingleLinkListLength(l)+1) return 0;//1,尋找第i－1個節點 while(p-next ki-1)k++,p=p-next; //2,構造節點if(!(q=(SingleLinkList)malloc(sizeof(SingleLinkNode))))return 0;//3,設置節點並將節點鏈入q-data =e;q-next =p-next ;p-next =q;return 1;}//刪除鏈表的第i個元素status DeleteSingleLinkList(SingleLinkList l,int i){ int k=0;SingleLinkList p=l-next;if(i1||iSingleLinkListLength(l)) return 0;//1,尋找第i－1個節點 while(pki-1)k++,p=p-next; p-next =p-next-next ;free(p-next );return 1; } //列印鏈表void PrintSingleLinkList(SingleLinkList l){SingleLinkList p=l-next ;int i=1;while(p){coutp-data" " ;if(i%5==0)coutendl;p=p-next,i++ ;} }
Test #include"SingleLinkList.h"#includeiostream.h#includestdlib.h void main(void){ }
雙鏈表
雙鏈表的定義和各種操作實現方法，代碼如下；
DualLinkList.h typedef int status;typedef int ElemType; //鏈表節點及鏈表數據表示定義typedef struct DualLinkListNode{ElemType data;struct DualLinkListNode *next;}DualLinkListNode,*DualLinkListList;//以下是單向鏈表操作函數原型 //初始化操作status InitDualLinkListList(DualLinkListList l);//鏈表銷毀操作void DestroyDualLinkListList(DualLinkListList l);//鏈表清除操作void ClearDualLinkListList(DualLinkListList l);//鏈表長度int DualLinkListListLength(DualLinkListList l); //鏈表是否為空bool DualLinkListListEmpty(DualLinkListList l); //取鏈表中的第i個元素status GetDualLinkListListElem(DualLinkListList l,int i,ElemType e); //在鏈表的第i個位置插入元素status InsertDualLinkListList(DualLinkListList l,int i,ElemType e);//刪除鏈表的第i個元素status DeleteDualLinkListList(DualLinkListList l,int i); //列印鏈表void PrintDualLinkListList(DualLinkListList l);
② Zephyr 內核數據結構-單向鏈表
單項鏈表在Zephyr內核中的實現位於zephyr/include/zephyr/sys/slist.h。
Zephyr使用sys_slist_t存儲單向鏈表數據，每個鏈表元素存儲指向下一個元素的指針。通過這種方式，鏈表的第一個(head)和最後一個(tail)元素可以實現O(1)訪問。
刪除或插入指定節點需要從頭遍歷鏈表，時間復雜度為O(n)。Zephyr使用sys_snode_t存儲單向鏈表的節點，內部只包含一個指向下一個節點的指針。
用戶負責分配節點空間，通常將其嵌入用戶容器節點的結構中。當訪問單鏈表節點時，可以使用msg->node訪問，當有鏈表節點node時，可以使用SYS_SLIST_CONTAINER獲取用戶節點。
單項鏈表及其節點的組織如下：初始化時，sys_slist_t由用戶從可訪問的內存中分配，通過sys_slist_init()或SYS_SLIST_STATIC_INIT進行初始化。sys_slist_t內部欄位對用戶不透明，用戶不應訪問。
Zephyr提供了一系列操作節點的函數：sys_slist_peek_head()和sys_slist_peek_tail()用於peek頭和尾節點，sys_slist_peek_next()用於peek指定節點的下一個節點，如果列表為空則返回NULL。
此外，Zephyr提供了一組"for each"宏，如SYS_SLIST_FOR_EACH_NODE和SYS_SLIST_FOR_EACH_CONTAINER_SAFE，允許直接遍歷單項鏈表，無需手動遍歷下一個指針。在使用SYS_SLIST_FOR_EACH_CONTAINER_SAFE宏時，可以額外保存下一個節點的引用，允許在刪除節點後安全地訪問並遍歷下一個節點。
鏈表操作包括：判斷鏈表是否為空，將一條鏈表添加到現有鏈表的後面，將sys_slist_merge_slist添加到現有鏈表的後面，獲取鏈表中的節點數量。
帶符號單向鏈表sys_sflist_t在zephyr/include/zephyr/sys/sflist.h中實現。它與普通單向鏈表sys_slist_t原理相同，區別在於帶符號鏈表可以設置2位的符號。Zephyr為節點分配的內存至少為4位元組對齊，因此低2位沒有實際用途，帶符號鏈表利用這2位作為符號位。
通過sys_sfnode_flags_get和sys_sfnode_flags_set操作符號位，使用z_sfnode_next_peek取得下一個節點的地址。更多詳細信息請參考docs.zephyrproject.org...