如何用C 实现链表的查找、插入和删除

C语言中链表有很多种，我们来讲C语言中最主要的链表——单向链表和双向链表的查找，插入，删除的实现方法。END

单链表使用按值查找，从链表的首元结点出发，依次将结点值和给定值e进行比较，返回查找结果。

其中单链表的查找的算法步骤是：1.使用指针P指向首元结点2.从首元结点开始依次顺着链域next向下查找，只要指向当前结点的指针P不为空，并且P所指结点的数据域不等于给定的值e，则循环执行“p指向下一个结点操作。3.返回P。若查找成功，p此时即为结点的地址值，若查找失败，P返回NULL具体代码如下。

SingleLinkList.htypedef  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;} else  return 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(i<1||i>SingleLinkListLength(l))   return 0; //1,寻找第i个节点 while(p&&knext;   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(i<1||i>SingleLinkListLength(l)+1)   return 0; //1,寻找第i－1个节点 while(p->next &&knext;  //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(i<1||i>SingleLinkListLength(l))   return 0; //1,寻找第i－1个节点 while(p&&knext;   p->next =p->next->next ; free(p->next ); return 1;}//打印链表void PrintSingleLinkList(SingleLinkList l){ SingleLinkList p=l->next ; int i=1; while(p) {  cout<data<<' ' ;  if(i%5==0)   cout<next,i++ ; }}

Test#include'SingleLinkList.h'#include#includevoid main(void){}

双链表的定义和各种操作实现方法，代码如下；

DualLinkList.htypedef  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);END