【數據結構】鏈表中二級指針的應用

🦄個人主頁:修修修也

🎏所屬專欄:數據結構

??操作環境:Visual Studio 2022

(注:為方便演示本篇使用的x86系統,因此指針的大小為4個字節)

📌形參的改變不影響實參!

1.調用函數更改整型時傳值調用與傳址調用的區別

🎏傳值調用

🎏傳址調用

2.調用函數更改指針的指向時傳值調用和傳址調用的區別

🎏傳值調用

🎏傳址調用

3.調用函數更改數組和結構體成員

🎏更改數組成員

🎏更改結構體成員

📌二級指針的作用

1.鏈表的頭指針結構

2.空鏈表時的鏈表尾插

3.非空鏈表時的尾插邏輯

📌不使用二級指針操作鏈表的兩種方法

1.使用帶頭結點的鏈表

2.在外部更改頭指針的指向

結語

相信大家在初學鏈表時一定被下面這些函數的二級指針搞得暈頭轉向的,疑惑包括但不限于:

什么是二級指針?
為什么鏈表要用到二級指針?
為什么同樣是鏈表的函數,有的要用二級指針而有的只要用一級指針?
為什么同樣是鏈表,有的鏈表中使用了二級指針?而有的函數卻只需要使用一級指針?

要搞清上面這些問題,我們就要先搞清楚二級指針在鏈表中的作用到底是什么,接下來我將帶大家一起探究二級指針的"前世今生".

📌形參的改變不影響實參!

1.調用函數更改整型時傳值調用與傳址調用的區別

🎏傳值調用

如下代碼,我們在主函數創建了一個變量a,并給其賦值為5.然后我們通過傳值調用函數test1,在函數內部將a的值改為10.并在過程中打印出a的值:

void test1(int a)
{a = 10;printf("調用函數時a=%d\n", a);
}int main()
{int a = 5;printf("沒有調用函數前a=%d\n", a);test1(a);printf("調用函數后a=%d\n", a);return 0;
}

在編譯器中查看運行結果:

可以看到,傳值調用雖然在函數調用時將a的值改為了10,但是一旦出了函數之后a的值是完全沒有改變的.

因此:形參的改變不影響實參!

??????? 形參的改變不影響實參!

??????? 形參的改變不影響實參!

🎏傳址調用

如下代碼,我們在主函數創建了一個變量a,并給其賦值為5.還創建了一個整型指針pa記錄下了變量a的地址.然后我們通過傳址調用函數test2,在函數內部使用指針將a的值改為10.并在過程中打印出a的值:

void test2(int *pa)
{*pa = 10;printf("調用函數時a=%d\n", *pa);
}int main()
{int a = 5;int* pa = &a;printf("沒有調用函數前a=%d\n", a);test2(pa);printf("調用函數后a=%d\n", a);return 0;
}

?在編譯器中查看運行結果:

可以看到,傳址調用的函數在內部修改a的值,出了函數依然是有效的.

這有些像快遞送貨上門時,如果按照人名派送快遞,可能在這個小區有3個人都叫"張偉",這時派送給哪個"張偉"都有可能派送錯,但是如果按照他下單時填寫的地址派送快遞,那就絕對不會出錯,名字可能出錯,但地址一定是唯一的.

傳值調用和傳址調用不同的核心原理：函數會對形參和中間變量重新分配空間?

2.調用函數更改指針的指向時傳值調用和傳址調用的區別

那么是否我們要改變形參時都傳指針就一勞永逸了呢?再來看個例子:

🎏傳值調用

如下代碼,我們在主函數創建了兩個變量a和b,并給其賦值為5和10.還創建了兩個整型指針pa和pb分別記錄下了變量a和b的地址.然后我們通過傳值調用函數test3,在函數內部將pb的值賦給pa.并在過程中打印出pa和pb的值:

void test3(int* pa,int* pb)
{pa = pb;printf("調用函數時:\n");printf("pa指針中存儲的內容:%p\n", pa);printf("pb指針中存儲的內容:%p\n", pb);printf("\n");
}int main()
{int a = 5;int b = 10;int* pa = &a;int* pb = &b;printf("調用函數前:\n");printf("pa指針中存儲的內容:%p\n", pa);printf("pb指針中存儲的內容:%p\n", pb);printf("\n");test3(pa,pb);printf("調用函數后:\n");printf("pa指針中存儲的內容:%p\n", pa);printf("pb指針中存儲的內容:%p\n", pb);printf("\n");return 0;
}

在編譯器中查看運行結果:

(注:為方便演示使用的x86系統,因此指針的大小為4個字節)

可以看到,傳值調用雖然在函數調用時將pa的指向改為了pb,但是一旦出了函數之后pa的指向是完全沒有改變的.

因此:在改變指針變量時形參的改變同樣不影響實參!

🎏傳址調用

既然改指針的時候給函數傳指針本身沒有用,那么要傳什么呢?沒錯,要傳"指針的指針",即二級指針.

如下代碼,我們在主函數創建了兩個變量a和b,并給其賦值為5和10.還創建了兩個整型指針pa和pb分別記錄下了變量a和b的地址.又創建了一個二級整型指針ppa用來記錄指針pa的地址,然后我們通過傳址調用函數test4,在函數內部將pb的值賦給解引用的ppa.并在過程中打印出pa和pb的值:

void test4(int** ppa, int* pb)
{*ppa = pb;printf("調用函數時:\n");printf("pa指針中存儲的內容:%p\n", *ppa);printf("pb指針中存儲的內容:%p\n", pb);printf("\n");
}int main()
{int a = 5;int b = 10;int* pa = &a;int* pb = &b;int** ppa = &pa;printf("調用函數前:\n");printf("pa指針中存儲的內容:%p\n", pa);printf("pb指針中存儲的內容:%p\n", pb);printf("\n");test4(ppa, pb);printf("調用函數后:\n");printf("pa指針中存儲的內容:%p\n", pa);printf("pb指針中存儲的內容:%p\n", pb);printf("\n");return 0;
}

在編譯器中查看運行結果:

可以看到,傳址調用的函數在內部修改指針pa的值,出了函數依然是有效的.

因此當我們想要在函數內修改指針的指向時,我們應該給函數傳入二級指針.

3.調用函數更改數組和結構體成員

🎏更改數組成員

如下代碼,我們在主函數創建了一個5個成員的數組arr,并給其初始化為0.然后我們通過調用函數test5,在函數內部將arr的成員賦為0,1,2,3,4.并在過程中打印出arr數組的成員值:

void test5(int arr[])
{//修改arr數組成員的值for (int i = 0; i < 5; i++){arr[i] = i;}printf("調用函數時arr數組的成員:\n");for (int i = 0; i < 5; i++){printf("%d ", arr[i]);}printf("\n");
}int main()
{int arr[5] = { 0 };printf("調用函數前arr數組的成員:\n");for (int i = 0; i < 5; i++){printf("%d ", arr[i]);}printf("\n");test5(arr);printf("調用函數后arr數組的成員:\n");for (int i = 0; i < 5; i++){printf("%d ", arr[i]);}printf("\n");return 0;
}

在編譯器中查看運行結果:

可以看到,test5函數成功修改了arr數組的成員值,但我們好像并沒有傳給函數arr數組的地址,為什么修改成功了呢?

這是因為在C語言中,數組名就是數組首元素的地址,因此我們看似給test5函數傳入的是arr的名字,但實際上test5函數接收到的卻是arr數組的地址,因此該函數同樣可以寫為:

void test5(int* arr)
{//修改arr數組成員的值for (int i = 0; i < 5; i++){*(arr+i) = i;}printf("調用函數時arr數組的成員:\n");for (int i = 0; i < 5; i++){printf("%d ", *(arr + i));}printf("\n");
}

測試運行結果和上面沒有任何差別:

🎏更改結構體成員

如下代碼,我們在主函數中創建了一個結構體變量stu,并給其賦值"張三",20,1006.

然后我們通過傳址調用函數test6,在函數內部將stu的成員賦為"李四",30,1024.并在過程中打印出stu結構體的成員值:

typedef struct Student
{char name[5];int age;int idea;
}Stu;void test6(Stu* stu)
{strcpy(stu->name, "李四");stu->age = 30;stu->idea = 1024;printf("調用函數時stu結構體的成員:\n");printf("%s ", stu->name);printf("%d ", stu->age);printf("%d ", stu->idea);printf("\n");
}int main()
{Stu stu = { "張三",20,1006 };printf("調用函數前stu結構體的成員:\n");printf("%s ", stu.name);printf("%d ", stu.age);printf("%d ", stu.idea);printf("\n");test6(&stu);printf("調用函數后stu結構體的成員:\n");printf("%s ", stu.name);printf("%d ", stu.age);printf("%d ", stu.idea);printf("\n");return 0;
}

?在編譯器中查看運行結果:

可以看到,要更改結構體的值,需要給函數傳入結構體的指針才可以完成修改.

📌二級指針的作用

1.鏈表的頭指針結構

我們在單鏈表程序的最開始曾經寫過這樣一句代碼:

這句代碼的作用是創建了一個鏈表的頭指針,其邏輯圖示如下:

其在計算機的棧上的物理結構(以下簡稱物理結構)圖示如下:

2.空鏈表時的鏈表尾插

尾插操作我們已經在之前單鏈表詳解中詳細介紹過了,

因此這里只演示其邏輯圖示:(紫色線條代表操作)

物理圖示:(紫色線條代表操作)

可以看到,在空鏈表時的鏈表尾插操作中,我們更改了頭指針plist的指向,因此在函數中要使用到二級指針.

3.非空鏈表時的尾插邏輯

邏輯圖示:(紫色線條代表操作)

物理圖示:(紫色線條代表操作)

可以看到,在非空鏈表時的尾插中我們更改的是d2結點結構體的指針域的存儲內容,因此這時我們操作只需要d2結構體的地址,即一級指針.

綜上可得:

鏈表中傳入二級指針的原因是我們會遇到需要更改頭指針plist的指向的情況.

如果我們僅是在不改變頭指針plist的指向的情況下對鏈表進行操作(如非空鏈表的尾刪,尾插,對非首結點(FirstNode)的結點的插入/刪除操作等),則不需要用到二級指針.

📌不使用二級指針操作鏈表的兩種方法

那么我們在寫鏈表程序時就必須要使用二級指針嗎?答案是否定的,下面給大家提供了兩種不使用二級指針就可以完成鏈表所有操作的方法,大家可以結合自身情況選擇合適的方法完成鏈表程序.

1.使用帶頭結點的鏈表

原理:如果我們為單鏈表設置一個哨兵位的頭結點,那么plist的指向就固定了.即:

帶頭結點空鏈表示意圖:

這時我們想改變鏈表的首結點(firstNode),如頭刪,頭插等操作就只需要改變頭結點的指針域即可.而plist只需要固定存儲頭結點(headNode)的地址,既然函數不需要改變plist的指向,也就不需要用到二級指針了.

帶頭結點空鏈表頭插邏輯示意圖:(紫色線條為操作)

帶頭結點空鏈表頭插邏輯物理示意圖:(紫色線條為操作)

可以看到,在帶頭結點空鏈表的頭插操作中,plist的值沒有被改變,我們通過改變頭結點指針域的值實現了鏈表的頭插,因此使用帶頭結點的鏈表就可以不使用二級指針操作鏈表.

2.在外部更改頭指針的指向

原理:既然我們在函數內部給plist賦值不會影響到函數外的plist的指向,那么我們直接將更改指向這步操作放在函數外即可.其實類似的操作我們在獲取新結點函數中就已經應用過了:

如單鏈表中的BuySLTNode()函數:

為了防止newnode指針記錄的動態開辟的空間的地址出了函數就被銷毀,我們將新結點的地址通過返回值返回到函數外并用一個指針接收,這樣雖然出了空間newnode被銷毀,但我們已經在函數外部使用指針記錄了下函數返回的它的地址,因此出了函數還可以正常使用這塊空間.

同理,函數中更改了頭指針的指向后,我們將新的頭指針的地址記錄下來并返回給主函數,然后在主函數中重新使用plist指針接收這個頭即可更新頭指針的指向:

該思路代碼示例如下(僅展示頭插部分主函數與頭插函數邏輯) :

//單鏈表頭插
SLTNode* SLTPushFront(SLTNode* phead, int x)
{//創建新結點SLTNode* newnode = BuySLTNode(x);//BuySLTNode函數的實現參照上文//先將newnode的next指向首結點newnode->next = phead;//再將phead指向newnodephead = newnode;//返回新頭pheadreturn phead;
}int main()
{SLTNode* plist=NULL;printf("請輸入要頭插的數據:>");int pushfront_data = 0;scanf("%d", &pushfront_data);plist=SLTPushFront(plist, pushfront_data);//把SLTPushFront函數返回的新頭的地址賦給plist,這樣plist就重新指向新頭了return 0;
}

經過測試,這種方法同樣可以不使用二級指針就能夠完成鏈表的一系列相關操作,但缺點是只要調用了有可能改變plist的函數,都必須在外面使用plist接收返回值以便更新新的頭結點.有時一旦忘了就會導致程序出錯,比較麻煩且容易出錯.

結語

希望這篇鏈表中二級指針的應用能對大家有所幫助,歡迎大佬們留言或私信與我交流.

學海漫浩浩,我亦苦作舟!關注我,大家一起學習,一起進步!

相關文章推薦

【數據結構】什么是線性表?

【數據結構】線性表的鏈式存儲結構

【數據結構】鏈表的八種形態

【數據結構】C語言實現單鏈表萬字詳解(附完整運行代碼)

【數據結構】C語言實現帶頭雙向循環鏈表萬字詳解(附完整運行代碼)

【實用編程技巧】不想改bug?初學者必須學會使用的報錯函數assert!(斷言函數詳解)