提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  后端

当前栏目

用C语言实现单链表的各种操作(一)

C语言 实现 操作 各种 单链
2023-06-13 09:15:00 时间
最近，从新复习了一下数据结构中比较重要的几个部分，现在把自己的成果记录下来，主要就是仿照严蔚敏的《数据结构》（C语言版），中的例子和后面的习题进行改编的。首先，是单链表的各种实现，其中，包含了一些常考的知识点。例如，单链表的逆置，单链表的合并，找到单链表的中间节点等的算法实现。
下面这个是单链表的结构体的定义：
复制代码代码如下:

typedefstructLNode
{
 ElemTypedata;
 structLNode*next;
}LinkList;


下面的基本的单链表的操作：其中，有一些宏，没有给出他们的一些定义，者可以通过，严蔚敏的《数据结构》（C语言版），查看得到。
复制代码代码如下:

/*功能：构建一个空的带头节点的单链表*/
StatusInitList(structLNode**L)
{
 (*L)=(structLNode*)malloc(sizeof(structLNode));//产生头节点
 if(!*L)
  exit(OVERFLOW);
 (*L)->next=NULL;
 returnOK;
}
/*销毁线性表*/
StatusDestroyList(structLNode*L)
{
 structLNode*q;
 while(L)
 {
   q=L->next;
   free(L);
   L=q;
 }
 returnOK;
}
/*将L重置为空表*/
StatusClearList(structLNode*L)
{
 LinkList*p,*q;
 p=L->next;
 while(p)
 {
   q=p->next;
   free(p);
   p=q;
 }
 L->next=NULL;
 returnOK;
}
/*判断链表是否为空表*/
StatusListEmpty(LinkList*L)
{
 if(L->next)
 {
   returnFALSE;
 }
 else
 {
   returnTRUE;

 }
}
/*返回单链表中元素的个数*/
intListLength(structLNode*L)
{
 inti=0;
 LinkList*p=L->next;
 while(p)
 {
   i++;
   p=p->next;
 }
 returni;
}
/*L为带头节点的单链表的头指针，当第i个元素存在时，其值赋给e,并返回OK*/
StatusGetElem(structLNode*L,inti,ElemType*e)
{
 intj=1;
 LinkList*p=L->next;
 while(p&&j<i)
 {
   p=p->next;
   j++;
 }
 if(!p||j>i)
   returnERROR;
 *e=p->data;
 returnOK;
}
/*返回L中第一个与e满足关系compare()的数据元素的位序，
 若给存在返回值为0，compare()是数据元素的判定函数*/
intLocateElem(structLNode*L,ElemTypee,Status(*compare)(ElemType,ElemType))
{
 inti=0;
 LinkList*p=L->next;
 while(p)
 {
   i++;
   if(compare(p->data,e))
     returni;
   p=p->next;
 }
 return0;
}

复制代码代码如下:
/*所cur_e是L中的数据元素，且给就第一个，则用pre_e返回它的前驱*/
StatusPriorElem(structLNode*L,ElemTypecur_e,ElemType*pre_e)
{
 LinkList*q,*p=L->next;
 while(p->next)
 {
   q=p->next;//q指向p的后继
   if(q->data==cur_e)
   {
     *pre_e=p->data;
     returnOK;
   }
   p=q;
 }
 returnINFEASIBLE;

}
/*若cur_e是L中的数据元素，且不是最后一个，则用next_e返回它的后继*/
StatusNextElem(structLNode*L,ElemTypecur_e,ElemType*next_e)
{
 LinkList*p;
 p=L->next;
 while(p->next)
 {
   if(p->data==cur_e)
   {
    *next_e=p->next->data;
     returnOK;
   }
   p=p->next;
 }
 returnINFEASIBLE;
}
/*在带头节点的单链表L中的第i个位置之前插入元素e*/
StatusListInsert(structLNode*L,inti,ElemTypee)
{
 intj=0;
 structLNode*p=L,*s=NULL;
 while(p&&j<i-1)
 {
   p=p->next;
   j++;
 }
 if(!p||j>i-1)
   returnERROR;
 s=(structLNode*)malloc(sizeof(structLNode));
 if(!s)
   printf("mallocerror~\n");
 //p->next=s;
 s->data=e;
 //p->next=s;
  s->next=p->next;
  p->next=s;
  //s->next=NULL;
 //p=s;
 returnOK;
}
/*在带头节点的单链表中删除第i个元素，并有e返回其值*/
StatusListDelete(LinkList*L,inti,ElemType*e)
{

 LinkList*p=L,*q;

  intj=0;
 while(p->next&&j<i-1)
 {
   p=p->next;
   j++;
 }
 if(!p->next||j>i-1)
   returnERROR;
 q=p->next;
 p->next=q->next;
 *e=q->data;
 free(q);
 returnOK;
 }
/*依次对L的每个元素调用vi(),打印输出语句*/
StatusListTraverse(structLNode*L,void(*vi)(ElemType))
{
 LinkList*p=L->next;
 while(p)
 {
   vi(p->data);
   p=p->next;
 }
 printf("\n");
 returnOK;
}

相关文章