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  初始化（返回头结点） 保举

1. LinkStack* InitLinkStack1() {
2.         LinkStack* L = (LinkStack*)malloc(sizeof(LinkStack));  //定义一个头结点（栈顶结点）
3.         if (L == NULL) {
4.                 printf("内存分配失败\n");
5.                 return NULL;
6.         }
7.         L->next = NULL;
8.         return L;
9. }

复制代码

1.2  初始化方法2（不返回头结点指针） 不保举

1. void InitLinkStack2(LinkStack** L) {
2.         *L = (LinkStack*)malloc(sizeof(LinkStack));  //定义一个头结点
3.         if (*L == NULL)
4.         {
5.                 printf("内存分配失败!\n");
6.                 return;  //提前结束该函数
7.         }
8.         (*L)->next = NULL;
9. }

复制代码

首先：在链式栈的初始化操作中，返回头结点的指针是一种常见且保举的做法，但并不是绝对必须的，
保举返回头结点指针的原因：
1.方便后续操作
返回头结点的指针可以让调用者方便地对链式栈进行后续操作。因为链式栈的各种操作（如入栈、出栈、获取栈顶元素等）都需要通过头结点来访问栈中的元素，调用者持有头结点的指针后，就可以直接将其作为参数通报给这些操作函数
2.符合模块化设计原则
将初始化操作设计为返回头结点指针，使得初始化函数的功能更加独立和清晰。调用者可以明白知道初始化函数会返回一个指向链式栈头结点的指针，便于在差别的代码模块中复用该函数。
2. 1 判空方法1 （采用指针通报） 保举

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

复制代码

2.2  判空方法2 （采用值通报） 不保举

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

复制代码

首先：从语法和功能角度来看，传入 LinkStack L 是可行的。
因为判空操作仅仅是读取栈的信息，不涉及对栈布局的修改，所以纵然采用值通报，也能精确完成判空的逻辑。
在上述代码中，LinkStackEmpty2 函数吸收的是 LinkStack 类型的变量，通过判断其 next 指针是否为 NULL 来确定栈是否为空。
不建议值通报（传入LinkStack L）的原因（其它类似操作以此类推）：
1. 内存开销较大
当使用值通报（传入 LinkStack L）时，会在函数调用时复制整个 LinkStack 布局体。
对于链式栈来说，虽然布局体本身大概不大，但复制操作仍然会带来额外的内存开销。而使用指针通报（传入 LinkStack* L），只需要复制一个指针，其内存开销远远小于复制整个布局体。
2. 性能问题
值通报的复制操作会消耗一定的时间，尤其是在布局体较大或者频仍调用判空函数的情况下，会对程序的性能产生影响。指针通报则制止了这种复制操作，能够进步程序的实行效率。
3. 代码划一性
在链式栈的其他操作（如入栈、出栈等）中，通常需要修改栈的布局，因此需要使用指针通报。为了保持代码的划一性，建议在判空操作中也使用指针通报，这样可以让代码更加统一和易于理解。
3. 入栈

1. int push(LinkStack* L, ElemType value) {
2.         LinkStack* s = (LinkStack*)malloc(sizeof(LinkStack));
3.         if (s == NULL)
4.         {
5.                 printf("内存分配失败!\n");
6.                 return -2;
7.         }
8.         s->data = value;
9.         s->next = L->next;
10.         L->next = s;
11.         return 0;  //入栈（插入成功）
12. }

复制代码

4. 出栈

 value：用于存储出栈元素的值，是一个指向元素类型的指针

1. int pop(LinkStack* L, ElemType* value) {
2.         if (LinkStackEmpty1(L))
3.         {
4.                 printf("栈空，无法出栈!\n");
5.                 return -2;
6.         }
7.         LinkStack* p = L->next;
8.         *value = p->data;
9.         L->next = p->next;
10.         free(p);
11.         return 0;  //出栈成功
12. }

复制代码

5. 获取栈顶元素

1. int gettopValue(LinkStack* L, ElemType* value) {
2.         if (LinkStackEmpty1(L))
3.         {
4.                 printf("栈空，无法获取元素!\n");
5.                 return -2;
6.         }
7.         LinkStack* p = L->next;
8.         *value = p->data;  // 合并：*value = L->next->data
9.         return 0;  //获取栈顶信息成功
10. }

复制代码

6. 打印栈内元素

1. void printLinkStack(LinkStack L) {
2.         if (LinkStackEmpty1(&L))
3.         {
4.                 printf("栈空，无法获取元素!\n");
5.                 return;
6.         }
7.         LinkStack* p = L.next;
8.         printf("栈中的元素（从栈顶到栈底）为: ");
9.         while (p != NULL) {
10.                 printf("%d ", p->data);
11.                 p = p->next;
12.         }
13.         printf("\n-----------------------------------------------\n");
14. }

复制代码

7.烧毁

1. void destroyLinkStack(LinkStack* L) {
2.         LinkStack* p = L;
3.         while (p != NULL) {
4.                 LinkStack* s = p;
5.                 p = p->next;
6.                 free(s);
7.         }
8. }

复制代码

8.测试

1. int main() {
2.         //第二种初始化方式
3.         LinkStack* L1;  // 定义一个头指针
4.         InitLinkStack2(&L1);  // 初始化时，将该头指针指向了头结点
7.         //第一种初始化方式
8.         LinkStack* L = InitLinkStack1();
9.         if (L == NULL)
10.         {
11.                 return -1;  
12.         }
14.         printLinkStack(*L);  // 栈空，无法获取元素!
16.         // 测试进栈操作
17.         push(L, 11);
18.         push(L, 22);
19.         push(L, 33);
20.         printLinkStack(*L);  // 栈中的元素（从栈顶到栈底）为: 33 22 11
22.         // 获取栈顶元素
23.         ElemType value;
24.         if (gettopValue(L,&value) == 0)
25.         {
26.                 printf("当前栈顶元素为：%d\n", value);  // 当前栈顶元素为：33
27.         }
29.         // 测试出栈操作
30.         if (pop(L, &value) == 0) {
31.                 printf("出栈的元素为：%d\n", value);  // 出栈的元素为：33
32.         }
33.         printf("元素出栈后，");
34.         printLinkStack(*L);  // 元素出栈后，栈中的元素（从栈顶到栈底）为: 22 11
36.         // 销毁栈
37.         destroyLinkStack(L);
39.         return 0;
40. }

复制代码

9. 完备代码

1. //链式栈的基本实现//头结点的下一个结点是栈顶元素#include<stdio.h>#include<stdlib.h>typedef int ElemType;typedef struct Linknode {        ElemType data;  //数据域        struct Linknode* next;  //指针域}LinkStack;// 操作1——初始化（返回头结点） 保举LinkStack* InitLinkStack1() {
2.         LinkStack* L = (LinkStack*)malloc(sizeof(LinkStack));  //定义一个头结点（栈顶结点）
3.         if (L == NULL) {
4.                 printf("内存分配失败\n");
5.                 return NULL;
6.         }
7.         L->next = NULL;
8.         return L;
9. }// 操作1.1——初始化（不返回头结点指针） 不保举void InitLinkStack2(LinkStack** L) {
10.         *L = (LinkStack*)malloc(sizeof(LinkStack));  //定义一个头结点
11.         if (*L == NULL)
12.         {
13.                 printf("内存分配失败!\n");
14.                 return;  //提前结束该函数
15.         }
16.         (*L)->next = NULL;
17. }// 操作2——判空（采用指针通报） 保举int LinkStackEmpty1(LinkStack* L) {
18.         return L->next == NULL;
19. }// 操作2.1——判空（采用值通报） 不保举int LinkStackEmpty2(LinkStack L) {
20.         return L.next == NULL;
21. }
22. // 操作3——入栈int push(LinkStack* L, ElemType value) {
23.         LinkStack* s = (LinkStack*)malloc(sizeof(LinkStack));
24.         if (s == NULL)
25.         {
26.                 printf("内存分配失败!\n");
27.                 return -2;
28.         }
29.         s->data = value;
30.         s->next = L->next;
31.         L->next = s;
32.         return 0;  //入栈（插入成功）
33. }// 操作4——出栈，类似于链表的头删法// value：用于存储出栈元素的值，是一个指向元素类型的指针int pop(LinkStack* L, ElemType* value) {
34.         if (LinkStackEmpty1(L))
35.         {
36.                 printf("栈空，无法出栈!\n");
37.                 return -2;
38.         }
39.         LinkStack* p = L->next;
40.         *value = p->data;
41.         L->next = p->next;
42.         free(p);
43.         return 0;  //出栈成功
44. }// 操作5——获取栈顶元素int gettopValue(LinkStack* L, ElemType* value) {
45.         if (LinkStackEmpty1(L))
46.         {
47.                 printf("栈空，无法获取元素!\n");
48.                 return -2;
49.         }
50.         LinkStack* p = L->next;
51.         *value = p->data;  // 合并：*value = L->next->data
52.         return 0;  //获取栈顶信息成功
53. }// 操作6——打印栈void printLinkStack(LinkStack L) {
54.         if (LinkStackEmpty1(&L))
55.         {
56.                 printf("栈空，无法获取元素!\n");
57.                 return;
58.         }
59.         LinkStack* p = L.next;
60.         printf("栈中的元素（从栈顶到栈底）为: ");
61.         while (p != NULL) {
62.                 printf("%d ", p->data);
63.                 p = p->next;
64.         }
65.         printf("\n-----------------------------------------------\n");
66. }// 操作7——烧毁栈void destroyLinkStack(LinkStack* L) {
67.         LinkStack* p = L;
68.         while (p != NULL) {
69.                 LinkStack* s = p;
70.                 p = p->next;
71.                 free(s);
72.         }
73. }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. 运行截图

本人菜鸟一只，文章如有问题，欢迎评论区指正！



免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。