鏈表是重要的數(shù)據(jù)結(jié)構(gòu)，它的特點是存儲不連續(xù)，需要使用指針進行邏輯排序，別著急，下面是武林技術(shù)頻道小編給大家介紹的實例詳解C語言單向鏈表的實現(xiàn)，希望對你學習有幫助。
1.概述：
C語言中的單向鏈表（單鏈表）是鏈表的一種，其特點是鏈表的鏈接方向是單向的，對鏈表的訪問要通過順序讀取從頭部開始。
鏈表中最簡單的一種是單向鏈表，它包含兩個域，一個信息域和一個指針域。這個鏈接指向列表中的下一個節(jié)點，而最后一個節(jié)點則指向一個空值。
如下圖所示：
一個單向鏈表包含兩個值: 當前節(jié)點的值和一個指向下一個節(jié)點的鏈接
一個單向鏈表的節(jié)點被分成兩個部分。第一個部分保存或者顯示關(guān)于節(jié)點的信息，第二個部分存儲下一個節(jié)點的地址。單向鏈表只可向一個方向遍歷。
鏈表最基本的結(jié)構(gòu)是在每個節(jié)點保存數(shù)據(jù)和到下一個節(jié)點的地址，在最后一個節(jié)點保存一個特殊的結(jié)束標記，另外在一個固定的位置保存指向第一個節(jié)點的指針，有的時候也會同時儲存指向最后一個節(jié)點的指針。一般查找一個節(jié)點的時候需要從第一個節(jié)點開始每次訪問下一個節(jié)點，一直訪問到需要的位置。但是也可以提前把一個節(jié)點的位置另外保存起來，然后直接訪問。當然如果只是訪問數(shù)據(jù)就沒必要了，不如在鏈表上儲存指向?qū)嶋H數(shù)據(jù)的指針。這樣一般是為了訪問鏈表中的下一個或者前一個節(jié)點。
相對于雙向鏈表，這種普通的，每個節(jié)點只有一個指針的鏈表也叫單向鏈表，或者單鏈表，通常用在每次都只會按順序遍歷這個鏈表的時候（例如圖的鄰接表，通常都是按固定順序訪問的）。
2.程序?qū)崿F(xiàn)：
/* c2-2.h 線性表的單鏈表存儲結(jié)構(gòu) */ struct LNode { ElemType data; struct LNode *next; }; typedef struct LNode *LinkList; /* 另一種定義LinkList的方法 *//* bo2-2.c 單鏈表線性表(存儲結(jié)構(gòu)由c2-2.h定義)的基本操作(12個) */ Status InitList(LinkList *L) { /* 操作結(jié)果：構(gòu)造一個空的線性表L */ *L=(LinkList)malloc(sizeof(struct LNode)); /* 產(chǎn)生頭結(jié)點,并使L指向此頭結(jié)點 */ if(!*L) /* 存儲分配失敗 */ exit(OVERFLOW); (*L)->next=NULL; /* 指針域為空 */ return OK; } Status DestroyList(LinkList *L) { /* 初始條件：線性表L已存在。操作結(jié)果：銷毀線性表L */ LinkList q; while(*L) { q=(*L)->next; free(*L); *L=q; } return OK; } Status ClearList(LinkList L) /* 不改變L */ { /* 初始條件：線性表L已存在。操作結(jié)果：將L重置為空表 */ LinkList p,q; p=L->next; /* p指向第一個結(jié)點 */ while(p) /* 沒到表尾 */ { q=p->next; free(p); p=q; } L->next=NULL; /* 頭結(jié)點指針域為空 */ return OK; } Status ListEmpty(LinkList L) { /* 初始條件：線性表L已存在。操作結(jié)果：若L為空表，則返回TRUE，否則返回FALSE */ if(L->next) /* 非空 */ return FALSE; else return TRUE; } int ListLength(LinkList L) { /* 初始條件：線性表L已存在。操作結(jié)果：返回L中數(shù)據(jù)元素個數(shù) */ int i=0; LinkList p=L->next; /* p指向第一個結(jié)點 */ while(p) /* 沒到表尾 */ { i++; p=p->next; } return i; } Status GetElem(LinkList L,int i,ElemType *e) /* 算法2.8 */ { /* L為帶頭結(jié)點的單鏈表的頭指針。當?shù)趇個元素存在時,其值賦給e并返回OK,否則返回ERROR */ int j=1; /* j為計數(shù)器 */ LinkList p=L->next; /* p指向第一個結(jié)點 */ while(p&&j<i) /* 順指針向后查找,直到p指向第i個元素或p為空 */ { p=p->next; j++; } if(!p||j>i) /* 第i個元素不存在 */ return ERROR; *e=p->data; /* 取第i個元素 */ return OK; } int LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType)) { /* 初始條件: 線性表L已存在,compare()是數(shù)據(jù)元素判定函數(shù)(滿足為1,否則為0) */ /* 操作結(jié)果: 返回L中第1個與e滿足關(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) { /* 初始條件: 線性表L已存在 */ /* 操作結(jié)果: 若cur_e是L的數(shù)據(jù)元素,且不是第一個,則用pre_e返回它的前驅(qū), */ /* 返回OK;否則操作失敗,pre_e無定義,返回INFEASIBLE */ LinkList q,p=L->next; /* p指向第一個結(jié)點 */ while(p->next) /* p所指結(jié)點有后繼 */ { 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) { /* 初始條件：線性表L已存在 */ /* 操作結(jié)果：若cur_e是L的數(shù)據(jù)元素，且不是最后一個，則用next_e返回它的后繼， */ /* 返回OK;否則操作失敗，next_e無定義，返回INFEASIBLE */ LinkList p=L->next; /* p指向第一個結(jié)點 */ while(p->next) /* p所指結(jié)點有后繼 */ { 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é)點的單鏈線性表L中第i個位置之前插入元素e */ int j=0; LinkList p=L,s; while(p&&j<i-1) /* 尋找第i-1個結(jié)點 */ { p=p->next; j++; } if(!p||j>i-1) /* i小于1或者大于表長 */ return ERROR; s=(LinkList)malloc(sizeof(struct LNode)); /* 生成新結(jié)點 */ 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é)點的單鏈線性表L中，刪除第i個元素,并由e返回其值 */ int j=0; LinkList p=L,q; while(p->next&&j<i-1) /* 尋找第i個結(jié)點,并令p指向其前趨 */ { p=p->next; j++; } if(!p->next||j>i-1) /* 刪除位置不合理 */ return ERROR; q=p->next; /* 刪除并釋放結(jié)點 */ p->next=q->next; *e=q->data; free(q); return OK; } Status ListTraverse(LinkList L,void(*vi)(ElemType)) /* vi的形參類型為ElemType，與bo2-1.c中相應函數(shù)的形參類型ElemType&不同 */ { /* 初始條件：線性表L已存在 */ /* 操作結(jié)果:依次對L的每個數(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個元素的值，建立帶表頭結(jié)構(gòu)的單鏈線性表L */ int i; LinkList p; *L=(LinkList)malloc(sizeof(struct LNode)); (*L)->next=NULL; /* 先建立一個帶頭結(jié)點的單鏈表 */ printf("請輸入%d個數(shù)據(jù)/n",n); for(i=n;i>0;--i) { p=(LinkList)malloc(sizeof(struct LNode)); /* 生成新結(jié)點 */ scanf("%d",&p->data); /* 輸入元素值 */ p->next=(*L)->next; /* 插入到表頭 */ (*L)->next=p; } } void CreateList2(LinkList *L,int n) { /* 正位序(插在表尾)輸入n個元素的值，建立帶表頭結(jié)構(gòu)的單鏈線性表 */ int i; LinkList p,q; *L=(LinkList)malloc(sizeof(struct LNode)); /* 生成頭結(jié)點 */ (*L)->next=NULL; q=*L; printf("請輸入%d個數(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 */ { /* 已知單鏈線性表La和Lb的元素按值非遞減排列。 */ /* 歸并La和Lb得到新的單鏈線性表Lc，Lc的元素也按值非遞減排列 */ LinkList pa=La->next,pb=(*Lb)->next,pc; *Lc=pc=La; /* 用La的頭結(jié)點作為Lc的頭結(jié)點 */ 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é)點 */ Lb=NULL; } void visit(ElemType c) /* ListTraverse()調(diào)用的函數(shù)(類型要一致) */ { printf("%d ",c); } void main() { int n=5; LinkList La,Lb,Lc; printf("按非遞減順序, "); CreateList2(&La,n); /* 正位序輸入n個元素的值 */ printf("La="); /* 輸出鏈表La的內(nèi)容 */ ListTraverse(La,visit); printf("按非遞增順序, "); CreateList(&Lb,n); /* 逆位序輸入n個元素的值 */ printf("Lb="); /* 輸出鏈表Lb的內(nèi)容 */ ListTraverse(Lb,visit); MergeList(La,&Lb,&Lc); /* 按非遞減順序歸并La和Lb,得到新表Lc */ printf("Lc="); /* 輸出鏈表Lc的內(nèi)容 */ ListTraverse(Lc,visit); }以上就是關(guān)于實例詳解C語言單向鏈表的實現(xiàn)，介紹的很詳細，如果你還有不明白的地方，請隨時來武林技術(shù)頻道學習和了解，相信我們定能為你提供最專業(yè)的服務。?
新聞熱點
疑難解答
圖片精選
