帶頭結(jié)點單鏈表(詳解)
更新時間：2023年07月02日 11:52:01 作者：CD4356
這篇文章主要介紹了帶頭結(jié)點單鏈表?(詳解),需要的朋友可以參考下
單鏈表結(jié)構(gòu)體
- 結(jié)構(gòu)體后的*List是一個指向結(jié)構(gòu)體的指針類型，我們通過它來定義該類型的指針。
- 如：List p ; 則這個p就是指向LinkedList結(jié)構(gòu)體的一個指針，也就是單鏈表的頭指針。（所以說頭指針是必然存在的，但單鏈表不一定有頭結(jié)點，注意區(qū)分頭指針和頭結(jié)點）
typedef struct LinkedList {
int data; //數(shù)據(jù)域
struct LinkedList *next; //指針域，指向后繼結(jié)點，存放后繼結(jié)點的地址
}*List; //List <==> List * ，這里的List是單鏈表的頭指針帶頭結(jié)點 和 不帶頭節(jié)點 的初始化 帶頭結(jié)點單鏈表的初始化。①頭結(jié)點初始化時，其next域必須置為空 head->next = NULL;。②頭結(jié)點的data數(shù)據(jù)域如果要用來記錄鏈表長度，則需初始化為0 head->data = 0;
//申請一個頭結(jié)點 或 初始化一張空表
List create_head_node() {
List head = (List)malloc(sizeof(LinkedList)); //創(chuàng)建頭結(jié)點，并讓頭指針指向頭結(jié)點 (帶頭結(jié)點單鏈表)
if (head == 0) { //結(jié)點空間申請失敗，該判斷語句可有可無
return NULL;
}
head->next = NULL; //head是頭結(jié)點，h->next是頭結(jié)點的地址，該地址是第一個結(jié)點的地址，地址為NULL，即為空表
//head->data不用操作，但若想用頭結(jié)點數(shù)據(jù)域保存鏈表長度，可以設(shè)置為head->data = 0;
head->data = 0;
return head;
}不帶頭結(jié)點單鏈表的初始化
List link_list_create(){
List p;
p = NULL;
return p;
}求鏈表長度
單鏈表求長度有兩種方式
① 用頭結(jié)點的data數(shù)據(jù)域記錄鏈表長度（只適用于帶頭結(jié)點的鏈表）。創(chuàng)建頭結(jié)點時，頭結(jié)點的data初始化為0。成功執(zhí)行插入操作后，頭結(jié)點數(shù)據(jù)域+1。成功執(zhí)行刪除操作后，頭結(jié)點數(shù)據(jù)域-1。時間復(fù)雜度為O(1),（故鏈表帶頭結(jié)點，則推薦用這種方式）
head->data = 0; //創(chuàng)建頭結(jié)點時，將頭結(jié)點數(shù)據(jù)域初始化為0 head->data++; //每插入一個元素，頭結(jié)點數(shù)據(jù)域+1 head->data--; //每刪除一個元素，頭結(jié)點數(shù)據(jù)域-1 head->data; //獲取鏈表長度
② 遍歷鏈表獲取長度，時間復(fù)雜度為O(n)
//求長度
int link_list_length(List head) {
List p = head->next;
int len = 0;
while (p) {
len++;
p = p->next;
}
return len;
}空表判斷 帶頭結(jié)點的空表判斷head是頭結(jié)點，h->next是頭結(jié)點的地址，該地址是第一個結(jié)點的地址，地址為NULL，即為空表
boolean isEmpty(List p){
if(p->next == NULL){
return TRUE;
}
return FALSE;
}
或者 (使用頭結(jié)點數(shù)據(jù)域記錄鏈表長度時，可用該方法)
boolean isEmpty(List p){
if(p->data == 0){
return TRUE;
}
return FALSE;
}不帶頭結(jié)點的空表判斷 p == NULL; p表示的是第一個結(jié)點的地址，p = NULL 表示第一個結(jié)點的地址為空，也就是空表
boolean isEmpty(List p){
if(p == NULL){
return TRUE;
}
return FALSE;
}頭插法
在鏈表頭部插入結(jié)點（即作為鏈表第一個元素），時間復(fù)雜度為O(1)
//頭插
boolean head_insert(List head, int x) {
List p = (List)malloc(sizeof(LinkedList)); //申請一個結(jié)點，并將要插入的元素填入該結(jié)點的數(shù)據(jù)域
p->data = x;
p->next = head->next;
head->next = p;
head->data++; //結(jié)點插入成功，鏈表長度+1
return TRUE;
}尾插法
在鏈表尾部插入結(jié)點（即作為鏈表最后一個元素），時間復(fù)雜度為O(n)。
新結(jié)點插入鏈表尾部時，新結(jié)點的next域必須置為空，即：newNode->next = NULL; 。因為單鏈表尾結(jié)點的next域必須為null，否則我們在調(diào)用尾結(jié)點的next指針p->next時，系統(tǒng)判斷尾結(jié)點的next沒有值，就會動態(tài)地給它分配一個未知地址（而不是幫你將next域置為空）。正常情況下，雖然并不會出現(xiàn)問題，但在遍歷鏈表 或 按內(nèi)容獲取結(jié)點 或 第二次插入為節(jié)點時，程序就會陷入死循環(huán)，最終耗盡cpu性能。你可以將tail_insert()方法中的newNode->next = NULL;這行代碼注釋掉，然后調(diào)用我們后面講到的show()方法進行測試，你就會看到show()方法會不停息的打印輸出一個個未知地址，直至內(nèi)存耗盡，系統(tǒng)奔潰
//尾插
boolean tail_insert(List head, int x) {
List newNode = (List)malloc(sizeof(LinkedList)); //申請一個結(jié)點，并將要插入的元素填入該結(jié)點的數(shù)據(jù)域
newNode->data = x;
//newNode->next是動態(tài)分配的，如果你不置為空，系統(tǒng)就會動態(tài)地給它分配一個未知地址。
newNode->next = NULL;
List p = head; //用p結(jié)點做記錄
while (p->next != NULL) { //遍歷鏈表，直至尾結(jié)點
p = p->next;
}
p->next = newNode; //讓尾結(jié)點指針，指向新結(jié)點
head->data++; //新結(jié)點插入成功，鏈表長度+1
return TRUE;
}指定位置插入 在第k個位置插入新結(jié)點。需要先遍歷鏈表，找到第k-1個結(jié)點，然后再修改新結(jié)點指針和第k-1個結(jié)點的指針，即可實現(xiàn)在第k個位置插入新結(jié)點操作。
//指定位置插入
boolean insert(List head, int k, int x) {
if (k < 1) {
printf("插入位置非法！");
return FALSE;
}
List p = head;
int i = 0; //用i來記錄結(jié)點位置
while (p->next != NULL && i < k - 1) {
i++;
p = p->next;
}
if (i + 1 == k) {
List tmp = (List)malloc(sizeof(LinkedList)); //申請一個結(jié)點，并將要插入的元素填入該結(jié)點的數(shù)據(jù)域
tmp->data = x;
tmp->next = p->next;
p->next = tmp;
head->data++; //新結(jié)點插入成功，鏈表長度+1
return TRUE;
} else {
printf("插入位置非法！");
return FALSE;
}
}按位序查找
//按位序查找
List get(List head, int k) {
if (k < 1) {
printf("查找位置非法！");
return NULL;
}
List p = head;
int i = 0;
while (p->next != NULL && i < k) { //找到第k個結(jié)點
i++;
p = p->next;
}
if (i == k) { //判斷i是否等于要查找結(jié)點的位序
return p;
}else{
printf("查找位置非法！");
return NULL;
}
}刪除第1個結(jié)點
//刪除第1個結(jié)點
boolean del_first(List head) {
if (head->next != NULL) {
head->next = head->next->next; //讓頭結(jié)點next指針，指向頭結(jié)點下一個結(jié)點的next指針?biāo)碌刂?
head->data--; //鏈表長度減1
return TRUE;
}
return FALSE;
}刪除第k個結(jié)點
//刪除第k個結(jié)點
boolean del(List head, int k) {
List p = head;
if (p->next == NULL && k < 1) {
printf("刪除位置非法！\n");
return FALSE;
}
int i = 0; //用i記錄結(jié)點位置
while (p->next != NULL && i < k - 1) { //找到待刪結(jié)點的前一個結(jié)點
i++;
p = p->next;
}
if (i + 1 == k) { //判斷i是不是k結(jié)點的前一個結(jié)點的位置
p->next = p->next->next;
head->data--; //鏈表長度減1
return TRUE;
} else {
printf("刪除位置非法！\n");
return FALSE;
}
}遍歷鏈表，顯示數(shù)據(jù) 前面講到了，如果在新結(jié)點插入鏈表尾部時，如果新結(jié)點next指針沒有置為NULL，則在show()遍歷鏈表時，將鏈表的結(jié)點數(shù)據(jù)輸出后，方法不會中斷，而是繼續(xù)輸出一個個未知地址，直至內(nèi)存空間耗盡。
//顯示數(shù)據(jù)
void show(List head) {
List p = head->next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
}全部代碼
#include <stdio.h>
#include <stdlib.h> //malloc需要此頭文件
typedef enum {FALSE, TRUE} boolean;
//結(jié)構(gòu)體
typedef struct LinkedList {
int data;
struct LinkedList *next;
} *List; //List <==> List *
//申請一個頭結(jié)點，并初始化
List create_head_node() {
List head = (List)malloc(sizeof(LinkedList)); //創(chuàng)建頭結(jié)點，并讓頭指針指向頭結(jié)點 (帶頭結(jié)點單鏈表)
if (head == 0) { //結(jié)點空間申請失敗，該判斷語句可有可無
return NULL;
}
head->next = NULL; //head表示的是頭結(jié)點的地址，h->next就是頭結(jié)點的下一個結(jié)點，即第一個結(jié)點的地址為空，也就是空表
//head->data不用操作，但若想用頭結(jié)點數(shù)據(jù)域保存鏈表長度，可以設(shè)置為head->data = 0;
head->data = 0;
return head;
}
//頭插
boolean head_insert(List head, int x) {
List p = (List)malloc(sizeof(LinkedList)); //申請一個結(jié)點，并將要插入的元素填入該結(jié)點的數(shù)據(jù)域
p->data = x;
p->next = head->next;
head->next = p;
head->data++; //結(jié)點插入成功，鏈表長度+1
return TRUE;
}
//尾插
boolean tail_insert(List head, int x) {
List newNode = (List)malloc(sizeof(LinkedList)); //申請一個結(jié)點，并將要插入的元素填入該結(jié)點的數(shù)據(jù)域
newNode->data = x;
//newNode->next是動態(tài)分配的，如果不置為空，系統(tǒng)就會默認分配一個未知地址
newNode->next = NULL;
List p = head; //用p結(jié)點做記錄
while (p->next != NULL) { //遍歷鏈表，直至尾結(jié)點
p = p->next;
}
p->next = newNode; //讓尾結(jié)點指針，指向新結(jié)點
head->data++; //新結(jié)點插入成功，鏈表長度+1
return TRUE;
}
//指定位置插入
boolean insert(List head, int k, int x) {
if (k < 1) {
printf("插入位置非法！");
return FALSE;
}
List p = head;
int i = 0; //用i來記錄結(jié)點位置
while (p->next != NULL && i < k - 1) {
i++;
p = p->next;
}
if (i + 1 == k) {
List tmp = (List)malloc(sizeof(LinkedList)); //申請一個結(jié)點，并將要插入的元素填入該結(jié)點的數(shù)據(jù)域
tmp->data = x;
tmp->next = p->next;
p->next = tmp;
head->data++; //新結(jié)點插入成功，鏈表長度+1
return TRUE;
} else {
printf("插入位置非法！");
return FALSE;
}
}
//按序號查找
List get(List head, int k) {
if (k < 1) {
printf("查找位置非法！");
return NULL;
}
List p = head;
int i = 0;
while (p->next != NULL && i < k) { //找到第k個結(jié)點
i++;
p = p->next;
}
if (i == k) {
return p;
} else {
printf("查找位置非法！");
return NULL;
}
}
//刪除第1個結(jié)點
boolean del_first(List head) {
if (head->next != NULL) {
head->next = head->next->next;
head->data--;
return TRUE;
}
return FALSE;
}
//刪除第k個結(jié)點
boolean del(List head, int k) {
List p = head;
if (p->next == NULL && k < 1) {
printf("刪除位置非法！\n");
return FALSE;
}
int i = 0; //用i記錄結(jié)點位置
while (p->next != NULL && i < k - 1) { //找到待刪結(jié)點的前一個結(jié)點
i++;
p = p->next;
}
if (i + 1 == k) { //判斷i是不是k結(jié)點的前一個結(jié)點的位置
p->next = p->next->next;
head->data--;
return TRUE;
} else {
printf("刪除位置非法！\n");
return FALSE;
}
}
//顯示數(shù)據(jù)
void show(List head) {
List p = head->next;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
}
int main() {
List head = create_head_node();
printf("當(dāng)前單鏈表長度為：%d\n\n", head->data);
head_insert(head, 15);
head_insert(head, 25);
head_insert(head, 35);
printf("第1個結(jié)點元素為：%d\n", get(head, 1)->data);
printf("第2個結(jié)點元素為：%d\n", get(head, 2)->data);
printf("第3個結(jié)點元素為：%d\n", get(head, 3)->data);
printf("當(dāng)前單鏈表長度為：%d\n\n", head->data);
tail_insert(head, 45);
tail_insert(head, 55);
printf("第1個結(jié)點元素為：%d\n", get(head, 1)->data);
printf("第2個結(jié)點元素為：%d\n", get(head, 2)->data);
printf("第3個結(jié)點元素為：%d\n", get(head, 3)->data);
printf("第4個結(jié)點元素為：%d\n", get(head, 4)->data);
printf("第5個結(jié)點元素為：%d\n", get(head, 5)->data);
printf("當(dāng)前單鏈表長度為：%d\n\n", head->data);
insert(head, 6, 65);
insert(head, 2, 75);
printf("第1個結(jié)點元素為：%d\n", get(head, 1)->data);
printf("第2個結(jié)點元素為：%d\n", get(head, 2)->data);
printf("第3個結(jié)點元素為：%d\n", get(head, 3)->data);
printf("第4個結(jié)點元素為：%d\n", get(head, 4)->data);
printf("第5個結(jié)點元素為：%d\n", get(head, 5)->data);
printf("第4個結(jié)點元素為：%d\n", get(head, 6)->data);
printf("第5個結(jié)點元素為：%d\n", get(head, 7)->data);
printf("當(dāng)前單鏈表長度為：%d\n\n", head->data);
show(head);
printf("\n\n");
del_first(head);
show(head);
printf("\n\n");
del(head, 4);
show(head);
return 0;
}到此這篇關(guān)于帶頭結(jié)點單鏈表 (詳解)的文章就介紹到這了,更多相關(guān)帶頭結(jié)點單鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要為大家詳細介紹了C++實現(xiàn)俄羅斯方塊游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-09-09
C++實現(xiàn)LeetCode(82.移除有序鏈表中的重復(fù)項之二)
這篇文章主要介紹了C++實現(xiàn)LeetCode(82.移除有序鏈表中的重復(fù)項之二),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下2021-07-07
這篇文章主要介紹了C++編譯/編輯器對OIer的必要功能，本文給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-04-04
這篇文章主要為大家詳細介紹了如何利用C語言實現(xiàn)軍旗游戲，文中的示例代碼講解詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-11-11
本篇文章是對C語言指針賦值的問題進行了詳細的分析介紹，需要的朋友參考下2013-05-05
這篇文章主要介紹了C++萬能庫頭文件在vs中的安裝步驟(圖文)，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-02-02
這篇文章主要為大家詳細介紹了基于easyx的C++實現(xiàn)貪吃蛇，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-07-07
在Qt中QMainWindow是一個為用戶提供主窗口程序的類，包含了：菜單欄、工具欄、錨接部件、狀態(tài)欄以及一個中部件。本文將利用QMainWindow制作一個文本編輯器，感興趣的可以試一試2022-01-01
其實，單調(diào)隊列和單調(diào)棧是類似的，在我看來，這兩個東西只是名字不一樣 - - ! 比較容易想的一道題啦！ 首先，這題的兩個關(guān)鍵點： 1、區(qū)間的和。這個簡單，地球人都知道！ 2、區(qū)間的最小值。2015-07-07
這篇文章主要介紹了C語言中數(shù)組的一些基本知識小結(jié),其中重點是對于數(shù)組的內(nèi)存分配相關(guān)方面的知識整理,需要的朋友可以參考下2016-04-04