本節(jié)主要介紹單鏈表的簡(jiǎn)單算法實(shí)現(xiàn)。

本文部分ppt、視頻截圖來(lái)自：[青島大學(xué)-王卓老師的個(gè)人空間-王卓老師個(gè)人主頁(yè)-嗶哩嗶哩視頻]

1. 單鏈表簡(jiǎn)單算法 ☆

• 單鏈表的初始化（帶頭結(jié)點(diǎn)）

即構(gòu)造一個(gè)如下圖所示的空表

【算法步驟】

1. 生成新結(jié)點(diǎn)作為頭結(jié)點(diǎn)，用頭指針L指向頭結(jié)點(diǎn)。
2. 將頭結(jié)點(diǎn)的指針域置空。

【算法描述】
Status InitList_L(LinkList &L){L = new LNode; //或L=(LinkList) malloc (sizeof(LNode));L -> next = NULL; //指針域置空return OK;
}

• 判斷鏈表是否為空

空表：鏈表中無(wú)元素，稱為空鏈表（頭指針和頭結(jié)點(diǎn)仍然在）

【算法思路】
判斷頭結(jié)點(diǎn)的指針域是否為空

【算法：判斷鏈表是否為空】
int ListEmpty(LinkList L){//若L為空表，則返回1，否則返回0if(L->next) //非空return 0;elsereturn 1;
}

• 單鏈表的銷毀

鏈表銷毀后不存在。

【算法思路】
從頭指針開(kāi)始，一次釋放所有結(jié)點(diǎn)。

【算法：銷毀單鏈表L】
Status DestroyList_L(LinkList &L){  //銷毀單鏈表LLnode *p;  //或LinkList p；while(L){p = L;L = L -> next;delete p;}return OK;
}

• 清空鏈表

鏈表仍然存在，但鏈表中無(wú)元素，稱為空鏈表（頭指針和頭結(jié)點(diǎn)仍然存在）

【算法思路】
依次釋放所有結(jié)點(diǎn)，并將頭結(jié)點(diǎn)指針域設(shè)置為空。

【算法：清空鏈表L】
Status ClearList(LinkList &L){  //將L重置為空表Lnode *p,*q;  //或LinkList p,q；p = L-> next;while(p){     //沒(méi)到表尾q = p -> next;delete p;p = q;}L -> next = NULL;  //頭結(jié)點(diǎn)指針域?yàn)榭?/span>return OK;
}

• 求鏈表的表長(zhǎng)

【算法思路】
從首元結(jié)點(diǎn)開(kāi)始，依次計(jì)數(shù)所有結(jié)點(diǎn)。若是非空結(jié)點(diǎn)，表長(zhǎng)加1。

【算法：求單鏈表L的表長(zhǎng)】
int ListLength_L(LinkList L){ //返回L中數(shù)據(jù)元素的個(gè)數(shù)LinkList p;p = L -> next; //p指向第一個(gè)結(jié)點(diǎn)i = 0;while(p){      //遍歷單鏈表，統(tǒng)計(jì)結(jié)點(diǎn)數(shù)i++;        p = p -> next;   //最后一個(gè)結(jié)點(diǎn)的下一結(jié)點(diǎn)指針域?yàn)榭?#xff0c;循環(huán)結(jié)束}return i;
}