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

本文部分ppt、視頻截圖來自：[青島大學-王卓老師的個人空間-王卓老師個人主頁-嗶哩嗶哩視頻]

1. 單鏈表簡單算法 ☆

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

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

【算法步驟】

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

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

• 判斷鏈表是否為空

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

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

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

• 單鏈表的銷毀

鏈表銷毀后不存在。

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

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

• 清空鏈表

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

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

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

• 求鏈表的表長

【算法思路】
從首元結(jié)點開始，依次計數(shù)所有結(jié)點。若是非空結(jié)點，表長加1。

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