C語言單向鏈表的表示與實現(xiàn)實例詳解
更新時間：2014年07月07日 15:41:10 投稿：shichen2014
這篇文章主要介紹了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中相應(yīng)函數(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語言中String的常用函數(shù)用法，對學習String的小伙伴有一定的參考價值，感興趣的小伙伴可以借鑒一下2023-03-03
下面小編就為大家?guī)硪黄贑++中setiosflags()的用法詳解。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-10-10
這篇文章主要給大家介紹了關(guān)于C++解析特殊符號tab、換行符號的相關(guān)資料，這個功能在我們?nèi)粘ｉ_發(fā)中經(jīng)常會遇到，需要的朋友可以參考下2021-05-05
c++ 形狀類Shape(派生出圓類Circle和矩形類Rectangle)
通過C++方式，建立一個形狀類Shape作為基類，派生出圓類Circle和矩形類Rectangle 求出面積并獲取相關(guān)信息2020-11-11
C++11這次的更新帶來了令很多C++程序員期待已久的for?range循環(huán)，每次看到j(luò)avascript，?lua里的for?range，心想要是C++能有多好，心里別提多酸了。這次C++11不負眾望，再也不用羨慕別家人的for?range了。下面看下C++11的for循環(huán)的新用法2022-04-04
這篇文章主要介紹了C++ 結(jié)構(gòu)體與共用體的的相關(guān)資料，幫助大家更好的理解和學習c++，感興趣的朋友可以了解下，希望能夠給你帶來幫助2021-09-09
本文給大家分享的是個人寫的一段對C++中十種內(nèi)部排序算法的比較分析的代碼，主要在于測試10種排序方法的性能，給大家參考下吧。2015-03-03
基于C++ list中erase與remove函數(shù)的使用詳解
本篇文章是對C++ list中erase與remove函數(shù)的使用進行了詳細的分析介紹，需要的朋友參考下2013-05-05
這篇文章主要介紹了C語言中.c和.h文件區(qū)別講解,本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是本文的詳細內(nèi)容,需要的朋友可以參考下2021-07-07
在本篇文章里小編給大家整理的是關(guān)C語言數(shù)據(jù)存儲，小編覺得這篇文章寫的很不錯，有需要的朋友們可以學習參考下，希望能夠給你帶來幫助2021-10-10