① 如何用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...