帶頭結(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ù)域保存鏈表長度，可以設置為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。時間復雜度為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; //獲取鏈表長度
② 遍歷鏈表獲取長度，時間復雜度為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é)點（即作為鏈表第一個元素），時間復雜度為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é)點（即作為鏈表最后一個元素），時間復雜度為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指針所致地址
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ù)域保存鏈表長度，可以設置為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\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\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\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\n\n", head->data);
show(head);
printf("\n\n");
del_first(head);
show(head);
printf("\n\n");
del(head, 4);
show(head);
return 0;
}到此這篇關于帶頭結(jié)點單鏈表 (詳解)的文章就介紹到這了,更多相關帶頭結(jié)點單鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章給大家介紹了CPU的局部性原理,包括時間局部性、空間局部性以及如何通過緩存利用這些局部性來提高程序性能,局部性原理是現(xiàn)代計算機體系結(jié)構(gòu)和高性能編程的核心思想,感興趣的朋友跟隨小編一起看看吧2026-02-02
文章主要介紹了C++標準模板庫中的優(yōu)先級隊列(priority_queue)的功能、實現(xiàn)原理、使用方法及應用場景,優(yōu)先級隊列提供按優(yōu)先級排序的數(shù)據(jù)存儲方式,默認為最大堆實現(xiàn),通過分析其構(gòu)造函數(shù)、操作函數(shù)、性能考慮等內(nèi)容,展示了優(yōu)先級隊列在實際應用中的優(yōu)勢與注意事項2026-04-04
桶排序即是先把每個桶中的元素進行排序然后遍歷桶依次列出元素的算法,桶排序在元素較少的情況下很高效,以下我們就來詳解桶排序算法的思路及C++編程中的代碼實現(xiàn):2016-07-07
C++11引入的可變參數(shù)模板是一項非常強大的特性,它極大地提升了模板的擴展性,可變參數(shù)模板允許我們定義可以接受任意數(shù)量和類型參數(shù)的模板,這在處理不定數(shù)量參數(shù)的場景中非常有用,感興趣的可以了解一下2025-06-06
本文主要介紹了C語言實現(xiàn)帶頭雙向循環(huán)鏈表，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
這篇文章主要介紹了C++命名空間5種常見用法實例解析,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-06-06
這篇文章主要為大家介紹了C/C++開發(fā)中extern一些使用注意事項的事例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-01-01
這篇文章主要介紹了C++11 線程休眠函數(shù)的相關資料，幫助大家更好的理解和學習C++11,感興趣的朋友可以了解下2020-10-10
select函數(shù)實現(xiàn)高性能IO多路訪問的關鍵示例深入解析
這篇文章主要為大家介紹了select函數(shù)實現(xiàn)高性能IO多路訪問的關鍵示例深入解析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-09-09
C語言數(shù)據(jù)結(jié)構(gòu)之堆排序的優(yōu)化算法
堆排序Heap?Sort就是利用堆進行排序的方法,下面這篇文章主要給大家介紹了關于C語言數(shù)據(jù)結(jié)構(gòu)之堆排序的優(yōu)化算法的相關資料,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下2022-04-04