快捷導(dǎo)航

C語(yǔ)言單向鏈表的表示與實(shí)現(xiàn)實(shí)例詳解

更新時(shí)間：2014年07月07日 15:41:10 投稿：shichen2014

這篇文章主要介紹了C語(yǔ)言單向鏈表的表示與實(shí)現(xiàn),需要的朋友可以參考下

1.概述：

C語(yǔ)言中的單向鏈表（單鏈表）是鏈表的一種，其特點(diǎn)是鏈表的鏈接方向是單向的，對(duì)鏈表的訪(fǎng)問(wèn)要通過(guò)順序讀取從頭部開(kāi)始。
鏈表中最簡(jiǎn)單的一種是單向鏈表，它包含兩個(gè)域，一個(gè)信息域和一個(gè)指針域。這個(gè)鏈接指向列表中的下一個(gè)節(jié)點(diǎn)，而最后一個(gè)節(jié)點(diǎn)則指向一個(gè)空值。
如下圖所示：

一個(gè)單向鏈表包含兩個(gè)值: 當(dāng)前節(jié)點(diǎn)的值和一個(gè)指向下一個(gè)節(jié)點(diǎn)的鏈接

一個(gè)單向鏈表的節(jié)點(diǎn)被分成兩個(gè)部分。第一個(gè)部分保存或者顯示關(guān)于節(jié)點(diǎn)的信息，第二個(gè)部分存儲(chǔ)下一個(gè)節(jié)點(diǎn)的地址。單向鏈表只可向一個(gè)方向遍歷。

鏈表最基本的結(jié)構(gòu)是在每個(gè)節(jié)點(diǎn)保存數(shù)據(jù)和到下一個(gè)節(jié)點(diǎn)的地址，在最后一個(gè)節(jié)點(diǎn)保存一個(gè)特殊的結(jié)束標(biāo)記，另外在一個(gè)固定的位置保存指向第一個(gè)節(jié)點(diǎn)的指針，有的時(shí)候也會(huì)同時(shí)儲(chǔ)存指向最后一個(gè)節(jié)點(diǎn)的指針。一般查找一個(gè)節(jié)點(diǎn)的時(shí)候需要從第一個(gè)節(jié)點(diǎn)開(kāi)始每次訪(fǎng)問(wèn)下一個(gè)節(jié)點(diǎn)，一直訪(fǎng)問(wèn)到需要的位置。但是也可以提前把一個(gè)節(jié)點(diǎn)的位置另外保存起來(lái)，然后直接訪(fǎng)問(wèn)。當(dāng)然如果只是訪(fǎng)問(wèn)數(shù)據(jù)就沒(méi)必要了，不如在鏈表上儲(chǔ)存指向?qū)嶋H數(shù)據(jù)的指針。這樣一般是為了訪(fǎng)問(wèn)鏈表中的下一個(gè)或者前一個(gè)節(jié)點(diǎn)。
相對(duì)于雙向鏈表，這種普通的，每個(gè)節(jié)點(diǎn)只有一個(gè)指針的鏈表也叫單向鏈表，或者單鏈表，通常用在每次都只會(huì)按順序遍歷這個(gè)鏈表的時(shí)候（例如圖的鄰接表，通常都是按固定順序訪(fǎng)問(wèn)的）。

2.程序?qū)崿F(xiàn)：

/* c2-2.h 線(xiàn)性表的單鏈表存儲(chǔ)結(jié)構(gòu) */
 struct LNode
 {
  ElemType data;
  struct LNode *next;
 };
 typedef struct LNode *LinkList; /* 另一種定義LinkList的方法 */

/* bo2-2.c 單鏈表線(xiàn)性表(存儲(chǔ)結(jié)構(gòu)由c2-2.h定義)的基本操作(12個(gè)) */
 Status InitList(LinkList *L)
 { /* 操作結(jié)果：構(gòu)造一個(gè)空的線(xiàn)性表L */
  *L=(LinkList)malloc(sizeof(struct LNode)); /* 產(chǎn)生頭結(jié)點(diǎn),并使L指向此頭結(jié)點(diǎn) */
  if(!*L) /* 存儲(chǔ)分配失敗 */
   exit(OVERFLOW);
  (*L)->next=NULL; /* 指針域?yàn)榭?*/
  return OK;
 }
 Status DestroyList(LinkList *L)
 { /* 初始條件：線(xiàn)性表L已存在。操作結(jié)果：銷(xiāo)毀線(xiàn)性表L */
  LinkList q;
  while(*L)
  {
   q=(*L)->next;
   free(*L);
   *L=q;
  }
  return OK;
 }
 Status ClearList(LinkList L) /* 不改變L */
 { /* 初始條件：線(xiàn)性表L已存在。操作結(jié)果：將L重置為空表 */
  LinkList p,q;
  p=L->next; /* p指向第一個(gè)結(jié)點(diǎn) */
  while(p) /* 沒(méi)到表尾 */
  {
   q=p->next;
   free(p);
   p=q;
  }
  L->next=NULL; /* 頭結(jié)點(diǎn)指針域?yàn)榭?*/
  return OK;
 }
 Status ListEmpty(LinkList L)
 { /* 初始條件：線(xiàn)性表L已存在。操作結(jié)果：若L為空表，則返回TRUE，否則返回FALSE */
  if(L->next) /* 非空 */
   return FALSE;
  else
   return TRUE;
 }
 int ListLength(LinkList L)
 { /* 初始條件：線(xiàn)性表L已存在。操作結(jié)果：返回L中數(shù)據(jù)元素個(gè)數(shù) */
  int i=0;
  LinkList p=L->next; /* p指向第一個(gè)結(jié)點(diǎn) */
  while(p) /* 沒(méi)到表尾 */
  {
   i++;
   p=p->next;
  }
  return i;
 }
 Status GetElem(LinkList L,int i,ElemType *e) /* 算法2.8 */
 { /* L為帶頭結(jié)點(diǎn)的單鏈表的頭指針。當(dāng)?shù)趇個(gè)元素存在時(shí),其值賦給e并返回OK,否則返回ERROR */
  int j=1; /* j為計(jì)數(shù)器 */
  LinkList p=L->next; /* p指向第一個(gè)結(jié)點(diǎn) */
  while(p&&j<i) /* 順指針向后查找,直到p指向第i個(gè)元素或p為空 */
  {
   p=p->next;
   j++;
  }
  if(!p||j>i) /* 第i個(gè)元素不存在 */
   return ERROR;
  *e=p->data; /* 取第i個(gè)元素 */
  return OK;
 }
 int LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
 { /* 初始條件: 線(xiàn)性表L已存在,compare()是數(shù)據(jù)元素判定函數(shù)(滿(mǎn)足為1,否則為0) */
  /* 操作結(jié)果: 返回L中第1個(gè)與e滿(mǎn)足關(guān)系compare()的數(shù)據(jù)元素的位序。 */
  /*      若這樣的數(shù)據(jù)元素不存在,則返回值為0 */
  int i=0;
  LinkList p=L->next;
  while(p)
  {
   i++;
   if(compare(p->data,e)) /* 找到這樣的數(shù)據(jù)元素 */
    return i;
   p=p->next;
  }
  return 0;
 }
 Status PriorElem(LinkList L,ElemType cur_e,ElemType *pre_e)
 { /* 初始條件: 線(xiàn)性表L已存在 */
  /* 操作結(jié)果: 若cur_e是L的數(shù)據(jù)元素,且不是第一個(gè),則用pre_e返回它的前驅(qū), */
  /*      返回OK;否則操作失敗,pre_e無(wú)定義,返回INFEASIBLE */
  LinkList q,p=L->next; /* p指向第一個(gè)結(jié)點(diǎn) */
  while(p->next) /* p所指結(jié)點(diǎn)有后繼 */
  {
   q=p->next; /* q為p的后繼 */
   if(q->data==cur_e)
   {
    *pre_e=p->data;
    return OK;
   }
   p=q; /* p向后移 */
  }
  return INFEASIBLE;
 }
 Status NextElem(LinkList L,ElemType cur_e,ElemType *next_e)
 { /* 初始條件：線(xiàn)性表L已存在 */
  /* 操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是最后一個(gè)，則用next_e返回它的后繼， */
  /*      返回OK;否則操作失敗，next_e無(wú)定義，返回INFEASIBLE */
  LinkList p=L->next; /* p指向第一個(gè)結(jié)點(diǎn) */
  while(p->next) /* p所指結(jié)點(diǎn)有后繼 */
  {
   if(p->data==cur_e)
   {
    *next_e=p->next->data;
    return OK;
   }
   p=p->next;
  }
  return INFEASIBLE;
 }
 Status ListInsert(LinkList L,int i,ElemType e) /* 算法2.9。不改變L */
 { /* 在帶頭結(jié)點(diǎn)的單鏈線(xiàn)性表L中第i個(gè)位置之前插入元素e */
  int j=0;
  LinkList p=L,s;
  while(p&&j<i-1) /* 尋找第i-1個(gè)結(jié)點(diǎn) */
  {
   p=p->next;
   j++;
  }
  if(!p||j>i-1) /* i小于1或者大于表長(zhǎng) */
   return ERROR;
  s=(LinkList)malloc(sizeof(struct LNode)); /* 生成新結(jié)點(diǎn) */
  s->data=e; /* 插入L中 */
  s->next=p->next;
  p->next=s;
  return OK;
 }
 Status ListDelete(LinkList L,int i,ElemType *e) /* 算法2.10。不改變L */
 { /* 在帶頭結(jié)點(diǎn)的單鏈線(xiàn)性表L中，刪除第i個(gè)元素,并由e返回其值 */
  int j=0;
  LinkList p=L,q;
  while(p->next&&j<i-1) /* 尋找第i個(gè)結(jié)點(diǎn),并令p指向其前趨 */
  {
   p=p->next;
   j++;
  }
  if(!p->next||j>i-1) /* 刪除位置不合理 */
   return ERROR;
  q=p->next; /* 刪除并釋放結(jié)點(diǎn) */
  p->next=q->next;
  *e=q->data;
  free(q);
  return OK;
 }
 Status ListTraverse(LinkList L,void(*vi)(ElemType))
 /* vi的形參類(lèi)型為ElemType，與bo2-1.c中相應(yīng)函數(shù)的形參類(lèi)型ElemType&不同 */
 { /* 初始條件：線(xiàn)性表L已存在 */
  /* 操作結(jié)果:依次對(duì)L的每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)vi()。一旦vi()失敗,則操作失敗 */
  LinkList p=L->next;
  while(p)
  {
   vi(p->data);
   p=p->next;
  }
  printf("\n");
  return OK;
 }

/* algo2-5.c 主程序 */
 #include"c1.h"
 typedef int ElemType;
 #include"c2-2.h"
 #include"bo2-2.c"
 void CreateList(LinkList *L,int n) /* 算法2.11 */
 { /* 逆位序(插在表頭)輸入n個(gè)元素的值，建立帶表頭結(jié)構(gòu)的單鏈線(xiàn)性表L */
  int i;
  LinkList p;
  *L=(LinkList)malloc(sizeof(struct LNode));
  (*L)->next=NULL; /* 先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表 */
  printf("請(qǐng)輸入%d個(gè)數(shù)據(jù)\n",n);
  for(i=n;i>0;--i)
  {
   p=(LinkList)malloc(sizeof(struct LNode)); /* 生成新結(jié)點(diǎn) */
   scanf("%d",&p->data); /* 輸入元素值 */
   p->next=(*L)->next; /* 插入到表頭 */
   (*L)->next=p;
  }
 }
 void CreateList2(LinkList *L,int n)
 { /* 正位序(插在表尾)輸入n個(gè)元素的值，建立帶表頭結(jié)構(gòu)的單鏈線(xiàn)性表 */
  int i;
  LinkList p,q;
  *L=(LinkList)malloc(sizeof(struct LNode)); /* 生成頭結(jié)點(diǎn) */
  (*L)->next=NULL;
  q=*L;
  printf("請(qǐng)輸入%d個(gè)數(shù)據(jù)\n",n);
  for(i=1;i<=n;i++)
  {
   p=(LinkList)malloc(sizeof(struct LNode));
   scanf("%d",&p->data);
   q->next=p;
   q=q->next;
  }
  p->next=NULL;
 }
 void MergeList(LinkList La,LinkList *Lb,LinkList *Lc)/* 算法2.12 */
 { /* 已知單鏈線(xiàn)性表La和Lb的元素按值非遞減排列。 */
  /* 歸并La和Lb得到新的單鏈線(xiàn)性表Lc，Lc的元素也按值非遞減排列 */
  LinkList pa=La->next,pb=(*Lb)->next,pc;
  *Lc=pc=La; /* 用La的頭結(jié)點(diǎn)作為L(zhǎng)c的頭結(jié)點(diǎn) */
  while(pa&&pb)
   if(pa->data<=pb->data)
   {
    pc->next=pa;
    pc=pa;
    pa=pa->next;
   }
   else
   {
    pc->next=pb;
    pc=pb;
    pb=pb->next;
   }
  pc->next=pa?pa:pb; /* 插入剩余段 */
  free(*Lb); /* 釋放Lb的頭結(jié)點(diǎn) */
  Lb=NULL;
 }
 void visit(ElemType c) /* ListTraverse()調(diào)用的函數(shù)(類(lèi)型要一致) */
 {
  printf("%d ",c);
 }
 void main()
 {
  int n=5;
  LinkList La,Lb,Lc;
  printf("按非遞減順序, ");
  CreateList2(&La,n); /* 正位序輸入n個(gè)元素的值 */
  printf("La="); /* 輸出鏈表La的內(nèi)容 */
  ListTraverse(La,visit);
  printf("按非遞增順序, ");
  CreateList(&Lb,n); /* 逆位序輸入n個(gè)元素的值 */
  printf("Lb="); /* 輸出鏈表Lb的內(nèi)容 */
  ListTraverse(Lb,visit);
  MergeList(La,&Lb,&Lc); /* 按非遞減順序歸并La和Lb,得到新表Lc */
  printf("Lc="); /* 輸出鏈表Lc的內(nèi)容 */
  ListTraverse(Lc,visit);
 }

您可能感興趣的文章: