C語言_數據結構總結6：鏈式棧

?純c語言代碼，不涉及C++

順序棧的實現，歡迎查看這篇文章：C語言_數據結構總結5：順序棧-CSDN博客?

0. 結構單元

#include<stdio.h>
#include<stdlib.h>

typedef int ElemType;
typedef struct Linknode {
?? ?ElemType data; ?//數據域
?? ?struct Linknode* next; ?//指針域
}LinkStack;

1.1? 初始化（返回頭結點）推薦

LinkStack* InitLinkStack1() {LinkStack* L = (LinkStack*)malloc(sizeof(LinkStack));  //定義一個頭結點（棧頂結點）if (L == NULL) {printf("內存分配失敗\n");return NULL;}L->next = NULL;return L;
}

1.2??初始化方法2（不返回頭結點指針）不推薦

void InitLinkStack2(LinkStack** L) {*L = (LinkStack*)malloc(sizeof(LinkStack));  //定義一個頭結點if (*L == NULL){printf("內存分配失敗!\n");return;  //提前結束該函數}(*L)->next = NULL;
}

首先：在鏈式棧的初始化操作中，返回頭結點的指針是一種常見且推薦的做法，但并不是絕對必須的，
推薦返回頭結點指針的原因：
1.方便后續操作
返回頭結點的指針可以讓調用者方便地對鏈式棧進行后續操作。因為鏈式棧的各種操作（如入棧、出棧、獲取棧頂元素等）都需要通過頭結點來訪問棧中的元素，調用者持有頭結點的指針后，就可以直接將其作為參數傳遞給這些操作函數

2.符合模塊化設計原則
將初始化操作設計為返回頭結點指針，使得初始化函數的功能更加獨立和清晰。調用者可以明確知道初始化函數會返回一個指向鏈式棧頭結點的指針，便于在不同的代碼模塊中復用該函數。

2. 1 判空方法1?（采用指針傳遞）推薦

int LinkStackEmpty1(LinkStack* L) {return L->next == NULL;
}

2.2? 判空方法2?（采用值傳遞）不推薦

int LinkStackEmpty2(LinkStack L) {return L.next == NULL;
}

首先：從語法和功能角度來看，傳入 LinkStack L 是可行的。
因為判空操作僅僅是讀取棧的信息，不涉及對棧結構的修改，所以即使采用值傳遞，也能正確完成判空的邏輯。

在上述代碼中，LinkStackEmpty2 函數接收的是 LinkStack 類型的變量，通過判斷其 next 指針是否為 NULL 來確定棧是否為空。

不建議值傳遞（傳入LinkStack L）的原因（其它類似操作以此類推）：
1. 內存開銷較大
當使用值傳遞（傳入 LinkStack L）時，會在函數調用時復制整個 LinkStack 結構體。
對于鏈式棧來說，雖然結構體本身可能不大，但復制操作仍然會帶來額外的內存開銷。而使用指針傳遞（傳入 LinkStack* L），只需要復制一個指針，其內存開銷遠遠小于復制整個結構體。

2. 性能問題
值傳遞的復制操作會消耗一定的時間，尤其是在結構體較大或者頻繁調用判空函數的情況下，會對程序的性能產生影響。指針傳遞則避免了這種復制操作，能夠提高程序的執行效率。

3. 代碼一致性
在鏈式棧的其他操作（如入棧、出棧等）中，通常需要修改棧的結構，因此需要使用指針傳遞。為了保持代碼的一致性，建議在判空操作中也使用指針傳遞，這樣可以讓代碼更加統一和易于理解。

3. 入棧

int push(LinkStack* L, ElemType value) {LinkStack* s = (LinkStack*)malloc(sizeof(LinkStack));if (s == NULL){printf("內存分配失敗!\n");return -2;}s->data = value;s->next = L->next;L->next = s;return 0;  //入棧（插入成功）
}

4. 出棧

?value：用于存儲出棧元素的值，是一個指向元素類型的指針

int pop(LinkStack* L, ElemType* value) {if (LinkStackEmpty1(L)){printf("棧空，無法出棧!\n");return -2;}LinkStack* p = L->next;*value = p->data;L->next = p->next;free(p);return 0;  //出棧成功}

5. 獲取棧頂元素

int gettopValue(LinkStack* L, ElemType* value) {if (LinkStackEmpty1(L)){printf("棧空，無法獲取元素!\n");return -2;}LinkStack* p = L->next;*value = p->data;  // 合并：*value = L->next->datareturn 0;  //獲取棧頂信息成功
}

6. 打印棧內元素

void printLinkStack(LinkStack L) {if (LinkStackEmpty1(&L)){printf("棧空，無法獲取元素!\n");return;}LinkStack* p = L.next;printf("棧中的元素（從棧頂到棧底）為: ");while (p != NULL) {printf("%d ", p->data);p = p->next;}printf("\n-----------------------------------------------\n");
}

7.銷毀

void destroyLinkStack(LinkStack* L) {LinkStack* p = L;while (p != NULL) {LinkStack* s = p;p = p->next;free(s);}
}

8.測試

int main() {//第二種初始化方式LinkStack* L1;  // 定義一個頭指針InitLinkStack2(&L1);  // 初始化時，將該頭指針指向了頭結點//第一種初始化方式LinkStack* L = InitLinkStack1();if (L == NULL){return -1;  }printLinkStack(*L);  // 棧空，無法獲取元素!// 測試進棧操作push(L, 11);push(L, 22);push(L, 33);printLinkStack(*L);  // 棧中的元素（從棧頂到棧底）為: 33 22 11// 獲取棧頂元素ElemType value;if (gettopValue(L,&value) == 0){printf("當前棧頂元素為：%d\n", value);  // 當前棧頂元素為：33}// 測試出棧操作if (pop(L, &value) == 0) {printf("出棧的元素為：%d\n", value);  // 出棧的元素為：33}printf("元素出棧后，");printLinkStack(*L);  // 元素出棧后，棧中的元素（從棧頂到棧底）為: 22 11// 銷毀棧destroyLinkStack(L);return 0;
}

9. 完整代碼

//鏈式棧的基本實現
//頭結點的下一個結點是棧頂元素
#include<stdio.h>
#include<stdlib.h>typedef int ElemType;
typedef struct Linknode {ElemType data;  //數據域struct Linknode* next;  //指針域
}LinkStack;// 操作1——初始化（返回頭結點） 推薦
LinkStack* InitLinkStack1() {LinkStack* L = (LinkStack*)malloc(sizeof(LinkStack));  //定義一個頭結點（棧頂結點）if (L == NULL) {printf("內存分配失敗\n");return NULL;}L->next = NULL;return L;
}// 操作1.1——初始化（不返回頭結點指針） 不推薦
void InitLinkStack2(LinkStack** L) {*L = (LinkStack*)malloc(sizeof(LinkStack));  //定義一個頭結點if (*L == NULL){printf("內存分配失敗!\n");return;  //提前結束該函數}(*L)->next = NULL;
}// 操作2——判空（采用指針傳遞） 推薦
int LinkStackEmpty1(LinkStack* L) {return L->next == NULL;
}// 操作2.1——判空（采用值傳遞） 不推薦
int LinkStackEmpty2(LinkStack L) {return L.next == NULL;
}// 操作3——入棧
int push(LinkStack* L, ElemType value) {LinkStack* s = (LinkStack*)malloc(sizeof(LinkStack));if (s == NULL){printf("內存分配失敗!\n");return -2;}s->data = value;s->next = L->next;L->next = s;return 0;  //入棧（插入成功）
}// 操作4——出棧，類似于鏈表的頭刪法
// value：用于存儲出棧元素的值，是一個指向元素類型的指針
int pop(LinkStack* L, ElemType* value) {if (LinkStackEmpty1(L)){printf("棧空，無法出棧!\n");return -2;}LinkStack* p = L->next;*value = p->data;L->next = p->next;free(p);return 0;  //出棧成功}// 操作5——獲取棧頂元素
int gettopValue(LinkStack* L, ElemType* value) {if (LinkStackEmpty1(L)){printf("棧空，無法獲取元素!\n");return -2;}LinkStack* p = L->next;*value = p->data;  // 合并：*value = L->next->datareturn 0;  //獲取棧頂信息成功
}// 操作6——打印棧
void printLinkStack(LinkStack L) {if (LinkStackEmpty1(&L)){printf("棧空，無法獲取元素!\n");return;}LinkStack* p = L.next;printf("棧中的元素（從棧頂到棧底）為: ");while (p != NULL) {printf("%d ", p->data);p = p->next;}printf("\n-----------------------------------------------\n");
}// 操作7——銷毀棧
void destroyLinkStack(LinkStack* L) {LinkStack* p = L;while (p != NULL) {LinkStack* s = p;p = p->next;free(s);}
}int main() {//第二種初始化方式LinkStack* L1;  // 定義一個頭指針InitLinkStack2(&L1);  // 初始化時，將該頭指針指向了頭結點//第一種初始化方式LinkStack* L = InitLinkStack1();if (L == NULL){return -1;  }printLinkStack(*L);  // 棧空，無法獲取元素!// 測試進棧操作push(L, 11);push(L, 22);push(L, 33);printLinkStack(*L);  // 棧中的元素（從棧頂到棧底）為: 33 22 11// 獲取棧頂元素ElemType value;if (gettopValue(L,&value) == 0){printf("當前棧頂元素為：%d\n", value);  // 當前棧頂元素為：33}// 測試出棧操作if (pop(L, &value) == 0) {printf("出棧的元素為：%d\n", value);  // 出棧的元素為：33}printf("元素出棧后，");printLinkStack(*L);  // 元素出棧后，棧中的元素（從棧頂到棧底）為: 22 11// 銷毀棧destroyLinkStack(L);return 0;
}

10. 運行截圖

本人菜鳥一只，文章如有問題，歡迎評論區指正！

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/pingmian/71783.shtml
繁體地址，請注明出處：http://hk.pswp.cn/pingmian/71783.shtml
英文地址，請注明出處：http://en.pswp.cn/pingmian/71783.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！