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

链表

• 01

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

  

单向链表

• 01

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

  

• 02

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

  

• 03

  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);

• 04

  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&&k<i)  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(i<1||i>SingleLinkListLength(l)+1)   return 0; //1,寻找第i－1个节点 while(p->next &&k<i-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(i<1||i>SingleLinkListLength(l))   return 0; //1,寻找第i－1个节点 while(p&&k<i-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) {  cout<<p->data<<" " ;  if(i%5==0)   cout<<endl;  p=p->next,i++ ; } }

• 05

  Test #include"SingleLinkList.h"#include<iostream.h>#include<stdlib.h> void main(void){ }

  

双链表

• 01

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

  

• 02

  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);