用C語言實現(xiàn)單鏈表的各種操作(一)

更新時間：2013年05月24日 17:32:49 作者：

本篇文章是對用C語言實現(xiàn)單鏈表的各種操作進行了詳細的分析介紹，需要的朋友參考下

最近，從新復習了一下數(shù)據(jù)結(jié)構(gòu)中比較重要的幾個部分，現(xiàn)在把自己的成果記錄下來，主要就是仿照嚴蔚敏的《數(shù)據(jù)結(jié)構(gòu)》（C 語言版），中的例子和后面的習題進行改編的。首先，是單鏈表的各種實現(xiàn)，其中，包含了一些?？嫉闹R點。例如，單鏈表的逆置，單鏈表的合并，找到單鏈表的中間節(jié)點等的算法實現(xiàn)。
下面這個是單鏈表的結(jié)構(gòu)體的定義：

復制代碼代碼如下:

typedef struct LNode
{
 ElemType data;
 struct LNode *next;
}LinkList;

下面的基本的單鏈表的操作：其中，有一些宏，沒有給出他們的一些定義，者可以通過，嚴蔚敏的《數(shù)據(jù)結(jié)構(gòu)》（C 語言版），查看得到。

復制代碼代碼如下:

/* 功能：構(gòu)建一個空的帶頭節(jié)點的單鏈表*/
Status InitList (struct LNode **L)
{
  (*L) = (struct LNode *)malloc(sizeof(struct LNode)); //產(chǎn)生頭節(jié)點
  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;

  }
}
/*返回單鏈表中元素的個數(shù)*/
int ListLength(struct LNode *L)
{
  int i=0;
  LinkList *p = L->next;
  while(p)
  {
    i++;
    p = p->next;
  }
  return i;
}
/* L為帶頭節(jié)點的單鏈表的頭指針，當?shù)趇個元素存在時，其值賦給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()的數(shù)據(jù)元素的位序，
 若給存在返回值為0，compare()是數(shù)據(jù)元素的判定函數(shù)*/
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中的數(shù)據(jù)元素，且給就第一個，則用pre_e返回它的前驅(qū)*/
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中的數(shù)據(jù)元素，且不是最后一個，則用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;
}
/* 在帶頭節(jié)點的單鏈表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;
}
/*在帶頭節(jié)點的單鏈表中刪除第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的每個元素調(diào)用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;
}