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

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

下面这个是单链表的结构体的定义：

复制代码 代码如下:

typedef struct LNode

{

 ElemType data;

 struct LNode *next;

}LinkList;

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

复制代码 代码如下:

/* 功能：构建一个空的带头节点的单链表*/

Status InitList (struct LNode **L)

{

  (*L) = (struct LNode *)malloc(sizeof(struct LNode)); //产生头节点

  if(!*L)

   exit(OVERFLOW);

  (*L)->next = NULL;

  return OK;

}

/*销毁线性表*/

Status DestroyList(struct LNode *L)

{

  struct LNode *q;

  while(L)

  {

    q = L->next;

    free(L);

    L = q;

  }

  return OK;

}

/*将L重置为空表*/

Status ClearList(struct LNode *L)

{

  LinkList *p,*q;

  p = L->next;

  while(p)

  {

    q = p->next;

    free(p);

    p = q;

  }

  L->next = NULL;

  return OK;

}

/*判断链表是否为空表*/

Status ListEmpty(LinkList *L)

{

  if(L->next)

  {

    return FALSE;

  }

  else

  {

    return TRUE;

  }

}

/*返回单链表中元素的个数*/

int ListLength(struct LNode *L)

{

  int i=0;

  LinkList *p = L->next;

  while(p)

  {

    i++;

    p = p->next;

  }

  return i;

}

/* L为带头节点的单链表的头指针，当第i个元素存在时，其值赋给e,并返回OK */

Status GetElem(struct LNode *L,int i,ElemType *e)

{

  int j=1;

  LinkList *p = L->next;

  while(p && j<i)

  {

    p = p->next;

    j++;

  }

  if(!p || j>i)

    return ERROR;

  *e = p->data;

  return OK;

}

/*返回L中第一个与e满足关系compare()的数据元素的位序，

 若给存在返回值为0，compare()是数据元素的判定函数*/

int LocateElem(struct LNode *L,ElemType e,Status(*compare) (ElemType,ElemType))

{

  int i =0;

  LinkList *p = L->next;

  while(p)

  {

    i++;

    if(compare(p->data,e))

      return i;

    p=p->next;

  }

  return 0;

}

复制代码 代码如下:

/*所cur_e是L中的数据元素，且给就第一个，则用pre_e返回它的前驱*/

Status PriorElem(struct LNode *L,ElemType cur_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;

      return OK;

    }

    p = q;

  }

  return INFEASIBLE;

}

/* 若cur_e是L中的数据元素，且不是最后一个，则用next_e返回它的后继*/

Status NextElem(struct LNode *L,ElemType cur_e,ElemType *next_e)

{

  LinkList *p;

  p = L->next;

  while(p->next)

  {

    if(p->data == cur_e)

    {

     * next_e = p->next->data;

      return OK;

    }

    p = p->next;

  }

  return INFEASIBLE;

}

/* 在带头节点的单链表L中的第i个位置之前插入元素e*/

Status ListInsert(struct LNode *L,int i,ElemType e)

{

  int j =0;

  struct LNode *p=L,*s=NULL;

  while(p && j<i-1)

  {

    p=p->next;

    j++;

  }

  if(!p || j>i-1)

    return ERROR;

  s = (struct LNode *)malloc(sizeof(struct LNode));

  if(!s)

    printf("malloc error~\n");

  // p->next = s;

  s->data = e;

  // p->next = s;

   s->next = p->next;

   p->next = s;

   //s->next = NULL;

  // p = s;

  return OK;

}

/*在带头节点的单链表中删除第i个元素，并有e返回其值*/

Status ListDelete(LinkList *L,int i,ElemType *e)

{

  LinkList *p=L,*q;

   int j=0;

  while(p->next && j< i-1)

  {

    p = p->next;

    j++;

  }

  if(!p->next || j>i-1)

    return ERROR;

  q = p->next;

  p->next = q->next;

  *e = q->data;

  free(q);

  return OK;

  }

/* 依次对L的每个元素调用vi(),打印输出语句*/

Status ListTraverse(struct LNode *L,void (*vi)(ElemType))

{

  LinkList *p = L->next;

  while(p)

  {

    vi(p->data);

    p = p->next;

  }

  printf("\n");

  return OK;

}