大神文獻:https://blog.csdn.net/weixin_73588765/article/details/128356985
目錄
一、鏈表概念
1. 什么是鏈表?
1.1 鏈表的構成
2. 鏈表和數組的區別
數組的特點:
鏈表的特點: ? ? ? ? ? ? ??
二者對比:
二、鏈表靜態添加和遍歷
三、統計鏈表節點個數、鏈表查詢及修改節點
四、在指定節點插入新的節點
1.在指定節點后插入新的節點
2.在指定節點的前方插入新節點
1.第一個節點之前插入新的節點;
2.在中間的節點插入新的節點;
完整代碼:
五、刪除指定節點
1.刪除第一個節點
2.刪除中間的節點
完整代碼:
六、動態創建節點?
頭插法
尾插法
一、鏈表概念
1. 什么是鏈表?
鏈表是一種數據結構,是一種數據存放的思想;
鏈表是一種物理存儲上非連續,數據元素的邏輯順序通過鏈表中的指針鏈接次序,實現的一種線性存儲結構。
1.1 鏈表的構成
構成:鏈表由一個個結點組成,每個結點包含兩個部分:數據域 和 指針域。
-
數據域(data field):每個結點中存儲的數據。
-
指針域(pointer field):每個結點中存儲下一個結點的地址。
2. 鏈表和數組的區別
數組的特點:
- 數組中的每一個元素都屬于同一數據類型的;
- 數組是一組有序數據的集合;
- 數組是在內存中開辟一段連續的地址空間用來存放一組數據,可以用數組名加下標來訪問數組中的元素;?
鏈表的特點: ? ? ? ? ? ? ??
- 動態地進行存儲分配的一種結構;
- 鏈表中的各節點在內存中的地址都是不連續的;
- 鏈表是由一個個節點組成,像一條鏈子一樣;
- 鏈表中的節點一般包括兩個部分:(1)用戶要用的數據(2)下一個節點的地址;? ? ? ? ??
二者對比:
一個數組只能存放同一種類型的數據,而鏈表中就可以存放不同的數據類型;
數組中的元素地址是連續的,想刪除或添加一個新的元素,十分的麻煩不靈活,而且用數組存放數據是都要先定義好數組的大小(即元素的個數),如果在定義數組時,定義小了,內存不夠用,定義大了,顯然會浪費內存;
鏈表就可以很好的解決這些問題,鏈表中每一項都是一個結構體,鏈表中各節點在內存中的地址可以是不連續的,所以你想刪除或添加一個新的節點很簡單和方便,直接把節點中存放的的地址拿去修改就ok了(具體怎么添加或刪除放在后用代碼詳細講)。因為鏈表是一種動態結構,所以鏈表在建立的時候并不用像數組一樣需要提前定義大小和位置(具體怎么創建也放在后面用代碼詳細講)。
二、鏈表靜態添加和遍歷
思路:
靜態創建的鏈表節點,都是不同內存地址,是不連續的。
所以我們要在每個節點的指針域中,存儲下一個節點的地址,如上圖:
- 節點 1 的next(指針域),存儲的是節點 2 的地址
- 節點 2 的next(指針域),存儲的是節點 3 的地址
- 節點 3 的next(指針域),存儲的是節點 4 的地址
- 節點 4 的next(指針域),存儲的是節點 5 的地址
通過這樣的操作,就可以把這 5?個節點連接在一起。
#include <stdio.h>struct Test
{int data;struct Test *next;
};// 打印鏈表(遍歷鏈表)
void printfLink(struct Test *p) // 當前 p 存儲的是 t1 的地址,也就是鏈表頭
{while ( p != NULL ) // p 現是鏈表頭節點,通過循環移動到下一個節點,直到 NULL {printf("%d ",p->data); // 輸出當前節點的 data 值p = p->next; // 使 p 移動至下一個節點}putchar('\n');
}int main()
{// 創建節點struct Test t1 = {1, NULL}; // t1.data賦值為1,t1.next賦值為NULLstruct Test t2 = {2, NULL};struct Test t3 = {3, NULL};struct Test t4 = {4, NULL};struct Test t5 = {5, NULL};// 鏈接節點t1.next = &t2; // t1.next存儲t2的地址,使t1.next指向t2這個結構體變量t2.next = &t3;t3.next = &t4;t4.next = &t5;// 打印鏈表printfLink(&t1); // 將 t1(鏈表頭)的地址傳遞給printfLink函數的結構體指針變量 preturn 0;
}
三、統計鏈表節點個數、鏈表查詢及修改節點
#include <stdio.h>struct Test
{int data;struct Test *next;
};// 打印鏈表
void printfLink(struct Test *p) // 當前 p 存儲的是 t1 的地址,也就是鏈表頭
{while ( p != NULL ) // p 現是鏈表頭節點,通過循環移動到下一個節點,直到 NULL {printf("%d ",p->data); // 輸出當前節點的 data 值p = p->next; // 使 p 移動至下一個節點}putchar('\n');
}// 統計鏈表個數
int statisticsNode(struct Test *head) // 當前 head 存儲的是 t1 的地址,也就是鏈表頭
{int cnt = 0; // 計數器,統計節點個數// 遍歷鏈表,直到 head == NULLwhile ( head != NULL ){cnt++; // 記錄每一個節點head = head->next; // 使 head 移動至下一個節點}return cnt; // 返回節點個數
}// 查詢鏈表
int seekNode(struct Test *head, int data) // 當前 p 存儲的是 t1 的地址,也就是鏈表頭。data:我們需要查詢的節點
{struct Test *p = head; // 備份頭節點地址// 遍歷鏈表,直到 p == NULLwhile ( p != NULL ){// 判斷每個節點的數據域(p->data) 是否等于 我們需要查詢的節點(data)if( p->data == data ){return 1; // 查詢到,返回 1}p = p->next; // 使 p 移動至下一個節點}return -1;// 查不到,返回 -1
}// 修改指定節點
int modifyNode(struct Test *head, int data) // 當前 p 存儲的是 t1 的地址,也就是鏈表頭。data:我們需要修改的節點
{struct Test *p = head; // 備份鏈表頭// 遍歷鏈表while ( p != NULL ){// 判斷每個節點的數據域(p->data) 是否等于 我們需要修改的節點(data)if( p->data == data ){// 找了,將這個節點的原數據域的數據,修改為100p->data = 100;return 1; // 返回 1,表示修改成功}p = p->next; // 使 p 移動至下一個節點}return -1; // 返回 -1,找不到這個節點
}int main()
{// 創建節點struct Test t1 = {1, NULL}; // t1.data賦值為1,t1.next賦值為NULLstruct Test t2 = {2, NULL};struct Test t3 = {3, NULL};struct Test t4 = {4, NULL};struct Test t5 = {5, NULL};// 鏈接節點t1.next = &t2; // t1.next存儲t2的地址,使t1.next指向t2這個結構體變量t2.next = &t3;t3.next = &t4;t4.next = &t5;// 打印鏈表printfLink(&t1);// 統計鏈表個數int ret = statisticsNode(&t1);printf("鏈表個數:%d\n", ret);// 查詢鏈表int seekNodeData = 3; // 需要查詢的節點ret = seekNode(&t1, seekNodeData); // 將 t1 的地址和需要查詢的節點,傳遞至 seekNode 函數中if( ret == 1 ) // 判斷返回值是否為1,如 1 表示找到了,非 1 表示找不到{printf("需查詢的值:%d,查詢結果:%d\n", seekNodeData, ret);}else{printf("需查詢的值:%d,查詢結果:%d\n", seekNodeData, ret);}// 修改指定節點int modifyNodeData = 5; // 需要修改的節點printf("修改之前的鏈表:");printfLink(&t1);ret = modifyNode(&t1, modifyNodeData); // 將 t1 的地址和需要修改的節點,傳遞至 modifyNode 函數中printf("修改之后的鏈表:");printfLink(&t1);return 0;
}
四、在指定節點插入新的節點
插入一個新節點有兩種方法:? ? ? ??
- ?在指定節點后插入新的節點
- ?在指定節點前插入新的節點
1.在指定節點后插入新的節點
如上圖,在節點 2 的后方插入新的節點:
- ?通過循環,遍歷到指定的節點
- 讓新節點的下一個節點,連接到節點 3
new->next = p->next - 使指定節點的下一個節點,連接到新節點
p->next = new;
#include <stdio.h>struct Test
{int data;struct Test *next;
};// 打印鏈表
void printfLink(struct Test *p) // 當前 p 存儲的是 t1 的地址,也就是鏈表頭
{while ( p != NULL ) // p 現是鏈表頭節點,通過循環移動到下一個節點,直到 NULL {printf("%d ",p->data); // 輸出當前節點的 data 值p = p->next; // 使 p 移動至下一個節點}putchar('\n');
}// 在指定節點后方插入新節點
void afterInsertionNode(struct Test **head, int appointNode, struct Test *new)
{// 備份鏈表頭地址struct Test *p = *head;// 遍歷鏈表while ( p != NULL ){// 判斷當前節點是否等于目標節點if( p->data == appointNode ){new->next = p->next; // 讓新節點的下一個節點存儲,原節點的下一個節點的地址p->next = new; // 讓當前節點指向新節點return; // 找到之后直接返回}p = p->next; // 讓當前節點移動到下一個節點}printf("沒有找到目標節點,插入失敗!\n");
}int main()
{// 創建節點struct Test t1 = {1, NULL}; // t1.data賦值為1,t1.next賦值為NULLstruct Test t2 = {2, NULL};struct Test t3 = {3, NULL};struct Test t4 = {4, NULL};struct Test t5 = {5, NULL};// 創建鏈表頭struct Test *head = NULL;// 定義新節點并賦初值struct Test new = {100,NULL};// 鏈接節點head = &t1; // 頭節點head,存儲結構體變量 t1 的地址t1.next = &t2; // t1.next存儲t2的地址,使t1.next指向t2這個結構體變量t2.next = &t3;t3.next = &t4;t4.next = &t5;// 打印鏈表printf("輸出插入之前的鏈表:\n");printfLink(head);// 在指定節點后方插入新節點afterInsertionNode(&head, 2,&new);printf("輸出插入之后的鏈表:\n");printfLink(head);return 0;
}
2.在指定節點的前方插入新節點
有兩種情況:
- 1.第一個節點之前插入新的節點;
- 2.在中間的節點插入新的節點;
1.第一個節點之前插入新的節點;
?
如上圖,在指定節點的節點 1,之前插入的新節點:
- 遍歷,判斷節點是否為指定節點
- 新節點的下一個,指向節點1的地址
new->next = p; - 因為此時新節點變成了頭節點,所以此時將new的地址賦值給head
head = new;
void forwardInsertionNode(struct Test **head, int appointNode, struct Test *new)
{struct Test *p = *head; // 備份鏈表頭的地址// 判斷第一個節點的data,是否等于目標節點if( p->data == appointNode ){// 將新節點的下一個節點指向,p的地址,此時new節點變成了鏈表頭new->next = p;// 更新鏈表頭的指向,使*head指向new的地址,讓*head重新變成鏈表頭*head = new;return;}
}
2.在中間的節點插入新的節點;
如上圖,如果指定節點是5,之前插入新的節點:
思路:
按照之前的后面插入新節點的方法,當我們遍歷到指定節點 5 的時候,如果將new的下一個節點,指向目標節點,是可以連接上的,但是new的節點如果訪問到指定節點的上一個節點呢?這個時候很難找到目標節點的上一個節點的地址。
可以這么做,我們要在目標節點 5 之前插入一個新節點,比如說:現在 p 指向的是節點 4 ,節點 4 的下一個節點是目標節點 5 。那節點 4 ->next,不就是目標節點 5 嗎?,節點 4 ->next->data,不就是節點 5 的data?然后將new->next指向目標節點 5 的地址,節點 4->next 指向new的地址,不就連上了。
// 判斷當前節點的下一個節點,是否為NULLwhile ( p->next != NULL ){// 判斷當前節點的下一個節點的data,是否等于目標節點if( p->next->data == appointNode ){// 將new的下一個節點,指向原當前節點的下一個節點new->next = p->next;// 將當前節點的下一個節點指向newp->next = new;return;}p = p->next; // 偏移到下一個節點}
完整代碼:
#include <stdio.h>struct Test
{int data;struct Test *next;
};// 打印鏈表
void printfLink(struct Test *p) // 當前 p 存儲的是 t1 的地址,也就是鏈表頭
{while ( p != NULL ) // p 現是鏈表頭節點,通過循環移動到下一個節點,直到 NULL {printf("%d ",p->data); // 輸出當前節點的 data 值p = p->next; // 使 p 移動至下一個節點}putchar('\n');
}// 在指定節點前方插入新節點
void forwardInsertionNode(struct Test **head, int appointNode, struct Test *new)
{struct Test *p = *head; // 備份鏈表的地址,// *head是一個二級指針,保存的是main函數t1的地址,是鏈表的頭地址// 除非鏈表頭發生改變,否則不要更改鏈表頭的地址// 判斷目標節點是否為鏈表的第一個節點if( p->data == appointNode ){new->next = p; // 將新節點的下一個節點指向,p的地址,此時new節點變成了鏈表頭*head = new; // 更新鏈表頭的指向,使*head指向new的地址,讓*head重新變成鏈表頭return; }// 判斷當前節點的下一個節點,是否為NULLwhile ( p->next != NULL ){// 判斷當前節點的下一個節點的data,是否等于目標節點if( p->next->data == appointNode ){// 將new的下一個節點,指向原當前節點的下一個節點new->next = p->next;// 將當前節點的下一個節點指向newp->next = new;return;}p = p->next; // 偏移到下一個節點}
}int main()
{// 創建節點struct Test t1 = {1, NULL}; // t1.data賦值為1,t1.next賦值為NULLstruct Test t2 = {2, NULL};struct Test t3 = {3, NULL};struct Test t4 = {4, NULL};struct Test t5 = {5, NULL};// 創建鏈表頭struct Test *head = NULL;// 定義新節點并賦初值struct Test new = {100,NULL};// 鏈接節點head = &t1; // 頭節點head,存儲結構體變量 t1 的地址t1.next = &t2; // t1.next存儲t2的地址,使t1.next指向t2這個結構體變量t2.next = &t3;t3.next = &t4;t4.next = &t5;// 打印鏈表printf("輸出插入之前的鏈表:\n");printfLink(head);forwardInsertionNode(&head, 5,&new);printf("輸出插入之后的鏈表:\n");printfLink(head);return 0;
}
五、刪除指定節點
有兩種情況:
- 刪除第一個節點
- 刪除中間的節點
1.刪除第一個節點
思路:
head指向的是第一個節點,如果我需要刪除第一個節點,需要free()釋放內存,此時應當將head指向第二個節點。
struct Test *p = *head; // 備份鏈表頭的地址// 判斷鏈表第一個節點的data,是否與目標節點相等if( p->data == appointNode ){// 將鏈表頭指向第二個節點的地址*head = p->next;return;}
2.刪除中間的節點
思路:
如果我們刪除的是節點 3,那么節點 2 應該繞過節點 3,使節點 2 連接節點 4
// 判斷當前節點的下一個節點是否為NULLwhile ( p->next != NULL ){// 判斷當前節點的下一個節點的data,是否等于目標節點if( p->next->data == appointNode ){// 當前節點的下一個,指向當前節點的下一個節點的下一個節點p->next = p->next->next;return;}p = p->next; // 將當前節點,移動到下一個節點}
完整代碼:
#include <stdio.h>struct Test
{int data;struct Test *next;
};// 打印鏈表
void printfLink(struct Test *p) // 當前 p 存儲的是 t1 的地址,也就是鏈表頭
{while ( p != NULL ) // p 現是鏈表頭節點,通過循環移動到下一個節點,直到 NULL {printf("%d ",p->data); // 輸出當前節點的 data 值p = p->next; // 使 p 移動至下一個節點}putchar('\n');
}// 刪除節點
void delectNode(struct Test **head, int appointNode)
{struct Test *p = *head; // 備份鏈表頭的地址// 判斷鏈表第一個節點的data,是否與目標節點相等if( p->data == appointNode ){// 將鏈表頭指向第二個節點的地址*head = p->next;return;}// 判斷當前節點的下一個節點是否為NULLwhile ( p->next != NULL ){// 判斷當前節點的下一個節點的data,是否等于目標節點if( p->next->data == appointNode ){// 當前節點的下一個,指向當前節點的下一個節點的下一個節點p->next = p->next->next;return;}p = p->next; // 將當前節點,移動到下一個節點}
}int main()
{// 創建節點struct Test t1 = {1, NULL}; // t1.data賦值為1,t1.next賦值為NULLstruct Test t2 = {2, NULL};struct Test t3 = {3, NULL};struct Test t4 = {4, NULL};struct Test t5 = {5, NULL};// 創建鏈表頭struct Test *head = NULL;// 鏈接節點head = &t1; // 頭節點head,存儲結構體變量 t1 的地址t1.next = &t2; // t1.next存儲t2的地址,使t1.next指向t2這個結構體變量t2.next = &t3;t3.next = &t4;t4.next = &t5;// 打印鏈表printf("輸出刪除之前的鏈表:\n");printfLink(head);delectNode(&head, 4);printf("輸出刪除之后的鏈表:\n");printfLink(head);return 0;
}
六、動態創建節點?
頭插法
如果鏈條為空,創建的第一個節點為鏈表頭,然后每一次創建的新節點插在之前的鏈表頭之前,再讓新節點做為新的鏈表頭;
#include <stdio.h>
#include <stdlib.h>struct Test
{int data;struct Test *next;
};// 頭插法
struct Test* insertionHead(struct Test *head, struct Test *new)
{// 如果head(頭節點)是NULLif( head == NULL ){// 讓head指向newhead = new;}else{// 如果head(頭節點)不是NULL,那么新節點指向head,此時new為新的鏈表頭new->next = head;// 讓head指向new,讓head重新成為鏈表頭head = new;}return head; // 返回鏈表頭的地址
}// 動態創建鏈表節點
void createNode(struct Test **head)
{struct Test *new = NULL;while(1){// 開辟內存空間new = (struct Test*)malloc( sizeof(struct Test) );// 判斷是否開辟成功if( new == NULL ){printf("malloc error\n");exit(-1);}// 將new的下一個節點指向NULLnew->next = NULL;printf("為新節點的數據域賦值,如果輸入0,表示退出\n");scanf("%d", &(new->data));// 判斷輸入的是否為 0if( new->data == 0 ){printf("輸入0,quit\n");free(new); // 釋放指針new = NULL; // 避免懸空指針return; }// 重新獲取鏈表頭的地址*head = insertionHead(*head,new);}
}// 打印鏈表
void printfLink(struct Test *head)
{struct Test *p = head;while( p != NULL ){printf("%d ", p->data);p = p->next;}putchar('\n');
}int main()
{struct Test *head = NULL;createNode(&head);printfLink(head);return 0;
}
尾插法
如果鏈表為空,創建的第一個節點做為鏈表頭,然后每一次創建的新節點插在鏈表最后一個節點的指針域(next)中;
#include <stdio.h>
#include <stdlib.h>// 定義鏈表節點結構體
struct Test
{int data; // 數據域struct Test *next; // 指針域,指向下一個節點
};// 在鏈表尾部插入新節點
struct Test* insertTail(struct Test *head, struct Test *new)
{struct Test *p = head;if (head == NULL) // 如果鏈表為空,新節點即為頭節點{head = new;}else{// 遍歷鏈表,找到最后一個節點while (p->next != NULL){p = p->next;}// 將新節點插入到鏈表尾部p->next = new;}return head; // 返回鏈表頭節點
}// 創建鏈表節點
void createNode(struct Test **head)
{struct Test *new = NULL;while (1){// 開辟內存空間,創建一個新節點new = (struct Test*)malloc(sizeof(struct Test));if (new == NULL) // 檢查內存分配是否成功{printf("malloc error\n");exit(-1); // 內存分配失敗,退出程序}new->next = NULL; // 初始化新節點的指針域為NULL// 為新節點的數據域賦值printf("為新節點的數據域賦值,輸入0,退出\n");scanf("%d", &(new->data));if (new->data == 0) // 如果輸入0,則退出循環{free(new); // 釋放內存new = NULL; // 避免指針懸空return;}// 將新節點插入鏈表尾部*head = insertTail(*head, new);}
}// 打印鏈表
void printfLink(struct Test *head)
{while (head != NULL){printf("%d ", head->data); // 打印當前節點的數據head = head->next; // 移動到下一個節點}putchar('\n'); // 打印換行符
}int main()
{struct Test *head = NULL; // 初始化鏈表頭節點為NULLcreateNode(&head); // 創建鏈表printfLink(head); // 打印鏈表return 0;
}