數(shù)據(jù)結(jié)構(gòu)–單鏈表的定義
本節(jié)的學(xué)習(xí)目標(biāo)：
單鏈表的定義（如何用代碼實(shí)現(xiàn)）
優(yōu)點(diǎn):不要求大片連續(xù)空間，改變?nèi)萘糠奖?br> 缺點(diǎn):不可隨機(jī)存取，要耗費(fèi)一定空間存放指針
代碼實(shí)現(xiàn)
struct LNode
{
ElemType data; //數(shù)據(jù)域
struct LNode *next; //指針域
};
struct LNode *p = (struct LNode*)malloc(sizeof(struct LNode));
//增加一個(gè)新的結(jié)點(diǎn):在內(nèi)存中申請(qǐng)一個(gè)結(jié)點(diǎn)所需空間，并用指針p指向這個(gè)結(jié)點(diǎn)
為了方便 我們經(jīng)常使用typedef
t y p e d e f < 數(shù)據(jù)類型 > < 別名 > \color{purple}typedef <數(shù)據(jù)類型> <別名> typedef<數(shù)據(jù)類型><別名>
代碼一：
struct LNode
{
ElemType data; //數(shù)據(jù)域
struct LNode *next; //指針域
};
typedef struct LNode LNode;
typedef struct LNode* LinkList;
代碼二：
typedef struct LNode
{
ElemType data; //數(shù)據(jù)域
struct LNode *next; //指針域
} LNode, *LinkList;
代碼一與代碼二是等價(jià)的
我們一般使用代碼二
如何表示一個(gè)單鏈表
要表示一個(gè)單鏈表時(shí)，只需聲明一個(gè)頭指針L，指向單鏈表的第一個(gè)結(jié)點(diǎn)
LNode * L; //聲明一個(gè)指向單鏈表第一個(gè)結(jié)點(diǎn)的指針
//或:
LinkList L; //聲明一個(gè)指向單鏈表第一個(gè)結(jié)點(diǎn)的指針
// 這個(gè)可讀性更強(qiáng)
不帶頭結(jié)點(diǎn)的單鏈表
typedef struct LNode
{
ElemType data; //每個(gè)節(jié)點(diǎn)存放一個(gè)數(shù)據(jù)元素
struct LNode *next; //指針指向下一個(gè)節(jié)點(diǎn)
}LNode, *LinkList;
bool Empty(LinkList L) //判斷單鏈表是否為空
{
return L == NULL;
}
void InitList(LinkList&L)
{
L = NULL;
}
int main()
{
LinkList L; //聲明一個(gè)指向單鏈表的指針
InitList(L); //初始化一個(gè)空表
// ... ...
return 0;
}
帶頭結(jié)點(diǎn)的單鏈表
typedef struct LNode
{
ElemType data; //每個(gè)節(jié)點(diǎn)存放一個(gè)數(shù)據(jù)元素
struct LNode *next; //指針指向下一個(gè)節(jié)點(diǎn)
}LNode, *LinkList;
bool Empty(LinkList L) //判斷單鏈表是否為空
{
return L->next == NULL;
}
bool InitList(LinkList&L)
{
L = (LNode *)malloc(sizeof(LNode)); //分配一個(gè)頭結(jié)點(diǎn)
if (L == NULL) //內(nèi)存不足，分配失敗
return false;
L->next = NULL; //頭結(jié)點(diǎn)之后暫時(shí)還沒有節(jié)點(diǎn)
return true;
}
int main()
{
LinkList L; //聲明一個(gè)指向單鏈表的指針
InitList(L); //初始化一個(gè)空表
// ... ...
return 0;
}
不帶頭 VS 帶頭
帶頭結(jié)點(diǎn),寫代碼更方便
不帶頭結(jié)點(diǎn)，寫代碼更麻煩
對(duì)第一個(gè)數(shù)據(jù)結(jié)點(diǎn)和后續(xù)數(shù)據(jù)結(jié)點(diǎn)的處理需要用不同的代碼邏輯
對(duì)空表和非空表的處理需要用不同的代碼邏輯文章來源：http://www.zghlxwxcb.cn/news/detail-507206.html
一般我們使用帶頭結(jié)點(diǎn)的單鏈表文章來源地址http://www.zghlxwxcb.cn/news/detail-507206.html
知識(shí)點(diǎn)回顧與重要考點(diǎn)
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)--單鏈表的定義的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
