C說話單向鏈表的表現與完成實例詳解。本站提示廣大學習愛好者：（C說話單向鏈表的表現與完成實例詳解）文章只能為提供參考，不一定能成為您想要的結果。以下是C說話單向鏈表的表現與完成實例詳解正文
1.概述：
C說話中的單向鏈表（單鏈表）是鏈表的一種，其特色是鏈表的鏈接偏向是單向的，對鏈表的拜訪要經由過程次序讀取從頭部開端。
鏈表中最簡略的一種是單向鏈表，它包括兩個域，一個信息域和一個指針域。這個鏈接指向列表中的下一個節點，而最初一個節點則指向一個空值。
以下圖所示：
一個單向鏈表包括兩個值: 以後節點的值和一個指向下一個節點的鏈接
一個單向鏈表的節點被分紅兩個部門。第一個部門保留或許顯示關於節點的信息，第二個部門存儲下一個節點的地址。單向鏈表只可向一個偏向遍歷。
鏈表最根本的構造是在每一個節點保留數據和到下一個節點的地址，在最初一個節點保留一個特別的停止標志，別的在一個固定的地位保留指向第一個節點的指針，有的時刻也會同時貯存指向最初一個節點的指針。普通查找一個節點的時刻須要從第一個節點開端每次拜訪下一個節點，一向拜訪到須要的地位。然則也能夠提早把一個節點的地位別的保留起來，然後直接拜訪。固然假如只是拜訪數據就沒需要了，不如在鏈表上貯存指向現實數據的指針。如許普通是為了拜訪鏈表中的下一個或許前一個節點。
絕對於雙向鏈表，這類通俗的，每一個節點只要一個指針的鏈表也叫單向鏈表，或許單鏈表，平日用在每次都只會按次序遍歷這個鏈表的時刻（例如圖的鄰接表，平日都是按固定次序拜訪的）。
2.法式完成：
/* c2-2.h 線性表的單鏈表存儲構造 */
struct LNode
{
ElemType data;
struct LNode *next;
};
typedef struct LNode *LinkList; /* 另外一種界說LinkList的辦法 */
/* bo2-2.c 單鏈表線性表(存儲構造由c2-2.h界說)的根本操作(12個) */
Status InitList(LinkList *L)
{ /* 操作成果：結構一個空的線性表L */
*L=(LinkList)malloc(sizeof(struct LNode)); /* 發生頭結點,並使L指向此頭結點 */
if(!*L) /* 存儲分派掉敗 */
exit(OVERFLOW);
(*L)->next=NULL; /* 指針域為空 */
return OK;
}
Status DestroyList(LinkList *L)
{ /* 初始前提：線性表L已存在。操作成果：燒毀線性表L */
LinkList q;
while(*L)
{
q=(*L)->next;
free(*L);
*L=q;
}
return OK;
}
Status ClearList(LinkList L) /* 不轉變L */
{ /* 初始前提：線性表L已存在。操作成果：將L重置為空表 */
LinkList p,q;
p=L->next; /* p指向第一個結點 */
while(p) /* 沒到表尾 */
{
q=p->next;
free(p);
p=q;
}
L->next=NULL; /* 頭結點指針域為空 */
return OK;
}
Status ListEmpty(LinkList L)
{ /* 初始前提：線性表L已存在。操作成果：若L為空表，則前往TRUE，不然前往FALSE */
if(L->next) /* 非空 */
return FALSE;
else
return TRUE;
}
int ListLength(LinkList L)
{ /* 初始前提：線性表L已存在。操作成果：前往L中數據元素個數 */
int i=0;
LinkList p=L->next; /* p指向第一個結點 */
while(p) /* 沒到表尾 */
{
i++;
p=p->next;
}
return i;
}
Status GetElem(LinkList L,int i,ElemType *e) /* 算法2.8 */
{ /* L為帶頭結點的單鏈表的頭指針。當第i個元素存在時,其值賦給e並前往OK,不然前往ERROR */
int j=1; /* j為計數器 */
LinkList p=L->next; /* p指向第一個結點 */
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()是數據元素剖斷函數(知足為1,不然為0) */
/* 操作成果: 前往L中第1個與e知足關系compare()的數據元素的位序。 */
/* 若如許的數據元素不存在,則前往值為0 */
int i=0;
LinkList p=L->next;
while(p)
{
i++;
if(compare(p->data,e)) /* 找到如許的數據元素 */
return i;
p=p->next;
}
return 0;
}
Status PriorElem(LinkList L,ElemType cur_e,ElemType *pre_e)
{ /* 初始前提: 線性表L已存在 */
/* 操作成果: 若cur_e是L的數據元素,且不是第一個,則用pre_e前往它的先驅, */
/* 前往OK;不然操作掉敗,pre_e無界說,前往INFEASIBLE */
LinkList q,p=L->next; /* p指向第一個結點 */
while(p->next) /* p所指結點有後繼 */
{
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已存在 */
/* 操作成果：若cur_e是L的數據元素，且不是最初一個，則用next_e前往它的後繼， */
/* 前往OK;不然操作掉敗，next_e無界說，前往INFEASIBLE */
LinkList p=L->next; /* p指向第一個結點 */
while(p->next) /* p所指結點有後繼 */
{
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 */
{ /* 在帶頭結點的單鏈線性表L中第i個地位之前拔出元素e */
int j=0;
LinkList p=L,s;
while(p&&j<i-1) /* 尋覓第i-1個結點 */
{
p=p->next;
j++;
}
if(!p||j>i-1) /* i小於1或許年夜於表長 */
return ERROR;
s=(LinkList)malloc(sizeof(struct LNode)); /* 生成新結點 */
s->data=e; /* 拔出L中 */
s->next=p->next;
p->next=s;
return OK;
}
Status ListDelete(LinkList L,int i,ElemType *e) /* 算法2.10。不轉變L */
{ /* 在帶頭結點的單鏈線性表L中，刪除第i個元素,並由e前往其值 */
int j=0;
LinkList p=L,q;
while(p->next&&j<i-1) /* 尋覓第i個結點,並令p指向其前趨 */
{
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;
}
Status ListTraverse(LinkList L,void(*vi)(ElemType))
/* vi的形參類型為ElemType，與bo2-1.c中響應函數的形參類型ElemType&分歧 */
{ /* 初始前提：線性表L已存在 */
/* 操作成果:順次對L的每一個數據元素挪用函數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個元素的值，樹立帶表頭構造的單鏈線性表L */
int i;
LinkList p;
*L=(LinkList)malloc(sizeof(struct LNode));
(*L)->next=NULL; /* 先樹立一個帶頭結點的單鏈表 */
printf("請輸出%d個數據\n",n);
for(i=n;i>0;--i)
{
p=(LinkList)malloc(sizeof(struct LNode)); /* 生成新結點 */
scanf("%d",&p->data); /* 輸出元素值 */
p->next=(*L)->next; /* 拔出到表頭 */
(*L)->next=p;
}
}
void CreateList2(LinkList *L,int n)
{ /* 正位序(插在表尾)輸出n個元素的值，樹立帶表頭構造的單鏈線性表 */
int i;
LinkList p,q;
*L=(LinkList)malloc(sizeof(struct LNode)); /* 生成頭結點 */
(*L)->next=NULL;
q=*L;
printf("請輸出%d個數據\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的頭結點作為Lc的頭結點 */
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的頭結點 */
Lb=NULL;
}
void visit(ElemType c) /* ListTraverse()挪用的函數(類型要分歧) */
{
printf("%d ",c);
}
void main()
{
int n=5;
LinkList La,Lb,Lc;
printf("按非遞加次序, ");
CreateList2(&La,n); /* 正位序輸出n個元素的值 */
printf("La="); /* 輸入鏈表La的內容 */
ListTraverse(La,visit);
printf("按非遞增次序, ");
CreateList(&Lb,n); /* 逆位序輸出n個元素的值 */
printf("Lb="); /* 輸入鏈表Lb的內容 */
ListTraverse(Lb,visit);
MergeList(La,&Lb,&Lc); /* 按非遞加次序合並La和Lb,獲得新表Lc */
printf("Lc="); /* 輸入鏈表Lc的內容 */
ListTraverse(Lc,visit);
}
