• 嵌入式学习——数据结构（双向无头有环链表、内核链表、栈）——day48

    1. 约瑟夫环问题——双向无头回环链表

    1.1 问题描述

            给定 ( n ) 个人（编号为 ( 1, 2, \ldots, n )），他们围成一个圈。从第一个人开始报数，每报到第 ( k ) 个人时，杀掉这个人，然后从下一个人重新开始报数。重复这个过程，直到所有人都被杀死。约瑟夫环问题是要确定最后一个幸存者的编号。

    1.2 实质

            每次删除循环链表中的一个节点，直到链表中仅剩一个节点结束

    2. 双向无头循环链表代码

    2.1 makefile

    1. OBJ:=a.out
    2. OBJS+=main.c doublelink.c
    3. CCl=gcc
    4.  
    5. $(OBJ):$(OBJS)
    6. 	$(CC) $^ -o $@
    7. .PHONY:
    8. clean:
    9. 	rm $(OBJ)
    10. test:
    11. 	valgrind --tool=memcheck --leak-check=full ./$(OBJ)

    2.2 double.h

    1. #ifndef _DOUBLELINK_H_
    2. #define _DOUBLELINK_H_
    3.  
    4. typedef struct stu
    5. {
    6.     int id;
    7.     char name[32];
    8.     int score;
    9. }DataType;
    10.  
    11. typedef struct node
    12. {
    13.     DataType data;
    14.     struct node *ppre;
    15.     struct node *pnext;
    16. }DouNode;
    17.  
    18. typedef struct list
    19. {
    20.     DouNode *phead;
    21.     int clen;
    22. }DouList;
    23.  
    24. extern DouList *create_dou_link();
    25. extern int is_empty_dou_link(DouList *plist);
    26. extern void dou_link_for_each(DouList *plist, int dir);
    27. extern int push_head_dou_link(DouList *plist, DataType data);
    28. extern int  push_tail_dou_link(DouList *plist, DataType data);
    29. extern int pop_head_dou_link(DouList *plist);
    30. extern int pop_tail_dou_link(DouList *plist);
    31. extern void loop_dou_link(DouList *plist);
    32. extern DouNode *Joseph_loop(DouList *plist);
    33. extern void dou_link_for_remain(DouList *plist);
    34.  
    35. #endif

    2.3 double.c

    1. #include "doublelink.h"
    2. #include 
    3. #include 
    4. #include 
    5.  
    6. DouList *create_dou_link()//创建标签
    7. {
    8.     DouList *plist = NULL;
    9.  
    10.     plist = (DouList *)malloc(sizeof(DouList));
    11.     if (NULL == plist)
    12.     {
    13.         perror("fail to malloc");
    14.         return NULL;
    15.     }
    16.  
    17.     plist->phead = NULL;
    18.     plist->clen = 0;
    19.  
    20.     return plist;
    21. }
    22.  
    23. int is_empty_dou_link(DouList *plist)//判断空链表
    24. {
    25.     if (NULL == plist->phead)
    26.     {
    27.         return 1;
    28.     }
    29.  
    30.     return 0;
    31. }
    32.  
    33. int push_head_dou_link(DouList *plist, DataType data)//头插
    34. {
    35.     DouNode *pnode = NULL;
    36.  
    37.     pnode = malloc(sizeof(DouNode));
    38.     if (NULL == pnode)
    39.     {
    40.         perror("fail to malloc");
    41.         return -1;
    42.     }
    43.  
    44.     pnode->data = data;
    45.     pnode->ppre = NULL;
    46.     pnode->pnext = NULL;
    47.  
    48.     if (is_empty_dou_link(plist))//空链表直接插
    49.     {
    50.         plist->phead = pnode;
    51.     }
    52.     else
    53.     {
    54.         pnode->pnext = plist->phead;
    55.         plist->phead->ppre = pnode;
    56.         plist->phead = pnode;
    57.     }
    58.     plist->clen++;
    59.  
    60.     return 0;
    61. }
    62.  
    63. int push_tail_dou_link(DouList *plist, DataType data)//头插
    64. {
    65.     DouNode *p = NULL;
    66.     DouNode *pnode = NULL;
    67.  
    68.     pnode = malloc(sizeof(DouNode));
    69.     if (NULL == pnode)
    70.     {
    71.         perror("fail to malloc");
    72.         return -1;
    73.     }
    74.     pnode->data = data;
    75.     pnode->ppre = NULL;
    76.     pnode->pnext = NULL;
    77.  
    78.     if (is_empty_dou_link(plist))//空链表直接插
    79.     {
    80.         plist->phead = pnode;
    81.     }
    82.     else
    83.     {   
    84.         p = plist->phead;
    85.         while (p->pnext != NULL)
    86.         {
    87.             p = p->pnext;
    88.         }
    89.  
    90.         p->pnext = pnode;
    91.         pnode->ppre = p;
    92.     }
    93.     plist->clen++;
    94.  
    95.     return 0;
    96. }
    97.  
    98. int pop_head_dou_link(DouList *plist)//头删
    99. {
    100.     if (is_empty_dou_link(plist))//空链表直接结束程序
    101.     {
    102.         return -1;
    103.     }
    104.  
    105.     DouNode *pfree = NULL;
    106.     pfree = plist->phead;
    107.  
    108.     plist->phead = pfree->pnext;//标签指向第二个节点首地址
    109.     if (plist->phead != NULL)//判断是否空链表
    110.     {
    111.         plist->phead->ppre = NULL;//将第二个节点的ppre变为NULL
    112.     }
    113.     free(pfree);
    114.  
    115.     plist->clen--;
    116.  
    117.     return 0;
    118. }
    119.  
    120. int pop_tail_dou_link(DouList *plist)//尾删
    121. {
    122.     if (is_empty_dou_link(plist))//空链表程序结束
    123.     {
    124.         return -1;
    125.     }
    126.  
    127.     DouNode *pfree = NULL;
    128.  
    129.     pfree = plist->phead;
    130.  
    131.     while (pfree->pnext)//指针指向最后一个节点
    132.     {
    133.         pfree = pfree->pnext;
    134.     }
    135.  
    136.     if (pfree->ppre != NULL)//链表有两个以上节点
    137.     {
    138.         pfree->ppre->pnext = NULL;
    139.     }
    140.     else //链表只有一个节点
    141.     {
    142.         plist->phead = NULL;
    143.     }
    144.  
    145.     free(pfree);
    146.     plist->clen--;
    147.  
    148.     return 0;
    149. }
    150.  
    151. void loop_dou_link(DouList *plist)//将非回环链表改为双向回环链表
    152. {
    153.     DouNode *ptmpnode = NULL;
    154.  
    155.     ptmpnode = plist->phead;
    156.     while (ptmpnode->pnext != NULL)//将指针移动到末尾节点
    157.     {
    158.         ptmpnode = ptmpnode->pnext;
    159.     }
    160.  
    161.     ptmpnode->pnext = plist->phead;
    162.     plist->phead->ppre = ptmpnode;
    163. }
    164.  
    165. void dou_link_for_remain(DouList *plist)//打印约瑟夫回环一次处理后链表中剩下的成员信息
    166. {
    167.     int i = 0;
    168.     DouNode *ptmpnode = plist->phead;
    169.  
    170.     for (i = 0; i < plist->clen; i++)
    171.     {
    172.         printf("%d  ", ptmpnode->data.id);
    173.         printf("%s  ", ptmpnode->data.name);
    174.         printf("%d\n", ptmpnode->data.score);
    175.         ptmpnode = ptmpnode->pnext;
    176.     }
    177.     printf("=========================\n");
    178. }
    179.  
    180. DouNode *Joseph_loop(DouList *plist)//约瑟夫回环、实质是删除链表节点直到留下最后一个节点为止
    181. {
    182.     DouNode *pfreenode = NULL;//
    183.     DouNode *ptmpnode = NULL;//指向回环
    184.  
    185.     ptmpnode = plist->phead;
    186.  
    187.     while (ptmpnode != ptmpnode->pnext)//判断回环是否只剩下一个节点
    188.     {
    189.         
    190.         pfreenode = ptmpnode;//指向当前所在回环的位置
    191.  
    192.         pfreenode = pfreenode->pnext->pnext;//回环向后移动两个单位
    193.         pfreenode->ppre->pnext = pfreenode->pnext;
    194.         pfreenode->pnext->ppre = pfreenode->ppre; 
    195.  
    196.         ptmpnode = pfreenode->pnext;//记录要删除的回环的下一个位置，保证循环的延续
    197.         if (pfreenode == plist->phead)//判断要删除的节点是否是表头后的第一个节点、若是，给表头接入要删除节点的下一个节点
    198.         {
    199.             plist->phead = ptmpnode;
    200.         }
    201.  
    202.         free(pfreenode);
    203.         plist->clen--;
    204.         dou_link_for_remain(plist);//打印链表中剩下的节点信息
    205.     }
    206.  
    207.     return ptmpnode;
    208. }
    209.

    2.4 main.c

    1. #include 
    2. #include 
    3. #include "doublelink.h"
    4.  
    5. int main(void)
    6. {
    7.     DataType stus[] = {{1, "doinb", 100},
    8.                         {2, "lwx", 67},
    9.                         {3, "lqs", 99},
    10.                         {4, "tian", 98},
    11.                         {5, "gimgoon", 78},
    12.                         {6, "xinyi", 88},
    13.                         {7, "nuguri", 99},
    14.                         {8, "khan", 77},
    15.                         {9, "bo", 94},
    16.                         {10, "xiaolaohu", 60}
    17.                         };
    18.     DouNode *ptmpnode = NULL;
    19.     int i = 0;
    20.  
    21.     DouList *plist = create_dou_link();//表头创建
    22.     if (NULL == plist)
    23.     {
    24.         return -1;
    25.     }
    26.  
    27.     for (i = 0; i < sizeof(stus) / sizeof(stus[0]); i++)//给链表中插入结构体中的所有内容
    28.     {
    29.         push_tail_dou_link(plist, stus[i]);//尾插
    30.     }
    31.     dou_link_for_each(plist, 1);
    32.     dou_link_for_each(plist, 0);
    33.  
    34.     loop_dou_link(plist);//创建双向回环链表
    35.     
    36.     ptmpnode = Joseph_loop(plist);//约瑟夫回环
    37.     printf("%s\n", ptmpnode->data.name); 
    38.  
    39.     return 0;
    40. }

    2.5  判断单向链表是否有环

            利用快慢指针，慢指针走一步，快指针走两步

            快指针每走一步，判断是否为空或者是否与慢指针相遇，相遇为有环链表

    3. 内核链表（有头、双向循环链表）

    3.1 定义

            Linux内核链表是一种双向循环链表，它的实现非常简洁而高效，主要通过一些宏和内联函数来操作链表。链表节点的结构定义在头文件 中。

    3.1 offsetof宏

            获取结构体某个成员到结构体开头的偏移量

    3.2 container_of宏

            通过offsetof偏移量获取结构体的首地址

    3. 栈

    3.1 定义

            栈（Stack）是一种抽象的数据结构，它遵循后进先出（LIFO, Last In First Out）的原则。也就是说，最后放入栈中的元素最先被取出。

    3.2 栈的基本操作

            1. 入栈、压栈：将一个元素放入栈顶。

            2. 出栈、弹栈：从栈顶移除一个元素。

            3. 取栈顶元素：查看栈顶元素但不移除它。

            4. 判断栈是否为空：检查栈中是否有元素。

    3.3 分类

            （1）按实现方式分类：栈分为顺序栈和链式栈

            1. 顺序栈

                   使用数组实现的栈，数组中的元素按顺序存储。优点是实现简单，访问效率高；缺点是栈的容量固定，扩展不便。 

            2. 链式栈

            使用链表实现的栈，链表的每个节点存储一个栈元素。优点是栈的容量可以动态扩展；缺点是指针操作复杂，访问效率相对较低。

            （2）按用途来分类

            1. 操作系统栈

            用于管理程序执行时的函数调用，保存函数调用的返回地址、本地变量等信息。操作系统栈通常是顺序栈，采用固定大小。

                    1. 局部变量

                    2. 函数的形参、返回值

                    3. 函数调用关系——保护现场、恢复现场

    3.4 数据结构中的栈——链式栈

    4. 面试考点

            区分满增栈、满减栈、空增栈、空减栈（前提：仅限于顺序栈，数组方式构成的）

    4.1 满栈和空栈——判断栈顶所在位置是否存有数据而非整个栈有没有数据

            1. 满栈：栈顶所在位置有数据

                    入栈操作流程：先向上移动栈顶指针，再将数据压入栈中

            2. 空栈：栈顶所在位置没有数据

                    入栈操作流程：先将数据压入栈顶，再向上移动栈顶指针


     

    4.2 增栈和减栈——判断栈的生长方向

            0x1000与0x2000，内存高地址为0x2000，内存低地址为0x1000

            1. 增栈：数据入栈时栈顶指针向内存高地址移动

            2. 减栈：数据入栈时栈顶指针向内存低地址移动

    （1） 满增栈

            1. 出栈时：栈顶指针向内存高地址移动，再向栈顶入栈数据，

            2. 出栈时：出栈数据，栈顶指针向内存低地址移动，

    （2） 满减栈

    （3） 空增栈

            1. 出栈时：先向栈顶入栈数据，栈顶指针向内存高地址移动

            2. 出栈时：栈顶指针向内存低地址移动，出栈数据

    （4） 空减栈

    5. 数据结构中的栈——链式栈

    5.1 代码

    （1）makefile

    1. OBJ:=a.out
    2. OBJS+=main.c stack.c
    3. CCl=gcc
    4.  
    5. $(OBJ):$(OBJS)
    6. 	$(CC) $^ -o $@
    7. .PHONY:
    8. clean:
    9. 	rm $(OBJ)
    10. test:
    11. 	valgrind --tool=memcheck --leak-check=full ./$(OBJ)

    注意：在终端输入make test可以测试销毁是否成功以及是否有内存泄漏

    （2）stack.h

    1. #ifndef _STACK_H_
    2. #define _STACK_H_
    3.  
    4. typedef int DataType;
    5.  
    6. typedef struct stact_node
    7. {
    8.     DataType data;
    9.     struct stact_node *pnext;
    10. }StackNode;
    11.  
    12. typedef struct Stack
    13. {
    14.     StackNode *ptop;
    15.     int clen;
    16. }StackList;
    17.  
    18. extern StackList *create_stack();
    19. extern int is_empty_stack(StackList *plist);
    20. extern int push_stack(StackList *plist, DataType data);//入栈头插
    21. extern void stack_for_each(StackList *plist);
    22. extern int pop_stack(StackList *plist, DataType *pdata);//出栈头删
    23. extern void clear_stack(StackList *plist);
    24. extern void destory_stack(StackList *plist);
    25. extern int get_stack_top(StackList *plist, DataType *pdata);
    26.  
    27. #endif

    （3）stack.c

    1. #include 
    2. #include 
    3. #include "stack.h"
    4.  
    5. StackList *create_stack()
    6. {
    7.     StackList *plist = malloc(sizeof(StackList));
    8.     if (NULL == plist)
    9.     {
    10.         perror("fail to malloc");
    11.         return NULL;
    12.     }
    13.     plist->ptop = NULL;
    14.     plist->clen = 0;
    15.     
    16.     return plist;
    17. }
    18.  
    19. int is_empty_stack(StackList *plist)
    20. {
    21.     if (NULL == plist->ptop)
    22.     {
    23.         return 1;
    24.     }
    25.  
    26.     return 0;
    27. }
    28.  
    29. int push_stack(StackList *plist, DataType data)//入栈头插
    30. {
    31.     StackNode *pnode = malloc(sizeof(StackNode));
    32.     if (NULL == pnode)
    33.     {
    34.         perror("fail to malloc");
    35.         return -1;
    36.     }
    37.     pnode->data = data;
    38.     pnode->pnext = NULL;
    39.  
    40.     pnode->pnext = plist->ptop;
    41.     plist->ptop = pnode;
    42.  
    43.     plist->clen++;
    44.     
    45.     return 0;
    46. }
    47.  
    48. void stack_for_each(StackList *plist)
    49. {
    50. 	StackNode *ptmp = plist->ptop;
    51.  
    52. 	while (ptmp != NULL)
    53. 	{
    54. 		printf("%d ", ptmp->data);
    55. 		ptmp = ptmp->pnext;
    56. 	}
    57.  
    58. 	printf("\n");
    59. }
    60.  
    61. int pop_stack(StackList *plist, DataType *pdata)//出栈头删
    62. {
    63.     if (is_empty_stack(plist))
    64.     {
    65.         return -1;
    66.     }
    67.  
    68.     StackNode *pfree = plist->ptop;
    69.  
    70.     plist->ptop = pfree->pnext;
    71.     if (pdata != NULL)//传入非空地址，将删除的节点的数据传出
    72.     {
    73.         *pdata = pfree->data;
    74.     }
    75.  
    76.     free(pfree);
    77.     plist->clen--;
    78.  
    79.     return 0;
    80. }
    81.  
    82. void clear_stack(StackList *plist)//清空栈区
    83. {
    84.     while (!is_empty_stack(plist))
    85.     {
    86.         pop_stack(plist, NULL);
    87.     }
    88. }
    89.  
    90. void destory_stack(StackList *plist)
    91. {
    92.     if (!is_empty_stack(plist))
    93.     {
    94.         clear_stack(plist);
    95.     }
    96.     free(plist);
    97. }
    98.  
    99. int get_stack_top(StackList *plist, DataType *pdata)//获得栈顶数据
    100. {
    101.     if (is_empty_stack(plist))
    102.     {
    103.         return -1;
    104.     }
    105.  
    106.     *pdata = plist->ptop->data;
    107.  
    108.     return 0;
    109. }

    （4）main.c

    1. #include 
    2. #include 
    3. #include "stack.h"
    4.  
    5. int main(void)
    6. {
    7.     DataType tmpdata = 0;
    8.     DataType data[] = {1, 2, 3, 4, 5};
    9.     StackNode *ptmpnode = NULL;
    10.     int i = 0;
    11.     int ret = 0;
    12.  
    13.     StackList *plist = create_stack();//创建栈表头
    14.     if (NULL == plist)
    15.     {
    16.         return -1;
    17.     }
    18.     
    19.     for (i = 0; i < sizeof(data) / sizeof(data[0]); i++)//入栈所有数据
    20.     {
    21.         push_stack(plist, data[i]);//入栈头插
    22.     }
    23.     stack_for_each(plist);//遍历打印所有数据
    24.  
    25. #if 0
    26.     for (i = 0; i < sizeof(data)/sizeof(data[0]); i++)//获取栈顶元素并打印，出栈数据，打印栈中的剩下元素
    27.     {
    28.         printf("======== %d ========", i);
    29.         ret = get_stack_top(plist, &tmpdata);
    30.         if (0 == ret)
    31.         {
    32.             printf("ptop data:%d   ", tmpdata);
    33.         }
    34.  
    35.         pop_stack(plist, NULL);
    36.         stack_for_each(plist);//遍历打印所有数据
    37.     }
    38. #endif
    39.  
    40. #if 0
    41.     clear_stack(plist);//清理栈中所有节点
    42.     if (is_empty_stack(plist))
    43.     {
    44.         printf("clear_stack success!\n");
    45.     }
    46. #endif
    47.  
    48. #if 1
    49.     destory_stack(plist);
    50. #endif
    51.  
    52.     return 0;
    53. }

    5.2  应用

                    1. 撤回操作

                    2. 浏览器返回上一层操作

                    3. 计算器

            示例：利用链式栈实现四则运算

            1. makefile

    1. OBJ:=a.out
    2. OBJS+=calculate.c stack.c
    3. CCl=gcc
    4.  
    5. $(OBJ):$(OBJS)
    6. 	$(CC) $^ -o $@
    7. .PHONY:
    8. clean:
    9. 	rm $(OBJ)
    10. test:
    11. 	valgrind --tool=memcheck --leak-check=full ./$(OBJ)

            2. calculate.c

    1. #include 
    2. #include 
    3. #include 
    4. #include "stack.h"
    5.  
    6. int is_char_num(char ch)//判断此指针是否指向数字
    7. {
    8. 	if (ch >= '0' && ch <= '9')
    9. 	{
    10. 		return 1;
    11. 	}
    12. 	return 0;
    13. }
    14.  
    15. int get_opt_level(char opt)//获得运算符优先级
    16. {
    17. 	switch(opt)
    18. 	{
    19. 		case '+':
    20. 		case '-':
    21. 			return 1;
    22.         case '*':
    23.         case '/':
    24. 			return 2;
    25. 	}
    26. }
    27.  
    28. int get_result(int num1, int num2, char opt)//获得运算结果
    29. {
    30. 	switch(opt)
    31. 	{
    32. 		case '+':return num1 + num2;
    33. 		case '-':return num1 - num2;
    34. 		case '/':return num1 / num2;
    35. 		case '*':return num1 * num2;
    36. 	}
    37. }
    38.  
    39. int main(int argc, const char *argv[])
    40. {
    41. 	char press[128] = {0};//运算表达式
    42. 	DataType num = 0;//存储每个运算数
    43. 	DataType data;
    44. 	DataType opt;
    45. 	DataType num1;
    46. 	DataType num2;
    47. 	DataType res = 0;   //计算器返回值
    48.  
    49. 	StackList *pNumStack = create_stack();//存储数字的栈
    50. 	StackList *pOptStack = create_stack();//存储运算符的栈
    51.  
    52. 	fgets(press, sizeof(press), stdin);
    53. 	press[strlen(press)-1] = '\0';
    54. 	
    55. 	char *p = press;//遍历运算式字符串
    56. 	
    57. 	while (1)
    58. 	{
    59. 		if ('\0' == *p && is_empty_stack(pOptStack))//循环结束的条件，指针遍历到字符串末尾，运算符栈为空
    60. 		{
    61. 			break;
    62. 		}
    63.         
    64.         /*判断条件1*/
    65. 		while (is_char_num(*p))//拆解数字
    66. 		{
    67. 			num = num * 10 + (*p - '0');
    68. 			p++;
    69. 			if (!is_char_num(*p))
    70. 			{
    71. 				push_stack(pNumStack, num);//入栈数字
    72. 				num = 0;
    73. 			}
    74. 		}
    75. 		
    76.         /*判断条件2*/
    77. 		if (is_empty_stack(pOptStack))//运算符栈为空，入栈
    78. 		{
    79. 			push_stack(pOptStack, *p);
    80. 			p++;
    81. 			continue;
    82. 		}
    83.  
    84.         /*判断条件3*/
    85. 		if ('\0' == *p && !is_empty_stack(pOptStack))//结束条件
    86. 		{
    87. 			pop_stack(pOptStack, &opt);
    88. 			pop_stack(pNumStack, &num2);
    89. 			pop_stack(pNumStack, &num1);
    90. 			res = get_result(num1, num2, opt);
    91. 			push_stack(pNumStack, res);	
    92. 			continue;
    93. 		}
    94.  
    95.         /*判断条件4*/
    96. 		get_stack_top(pOptStack, &data);
    97. 		if (get_opt_level(data) < get_opt_level(*p))//运算符栈不为空,本次运算符优先级大于栈顶中运算符优先级
    98. 		{
    99. 			push_stack(pOptStack, *p);
    100. 			p++;
    101. 		}
    102. 		else if (get_opt_level(data) >= get_opt_level(*p))
    103. 		{
    104. 			pop_stack(pOptStack, &opt);
    105. 			pop_stack(pNumStack, &num2);
    106. 			pop_stack(pNumStack, &num1);
    107. 			res = get_result(num1, num2, opt);
    108. 			push_stack(pNumStack, res);
    109. 		}
    110. 	}
    111.  
    112. 	get_stack_top(pNumStack, &res);
    113. 	printf("res = %d\n", res);
    114. 	
    115. 	destaroy_stack(pNumStack);
    116. 	destaroy_stack(pOptStack);
    117.  
    118. 	return 0;
    119. }

            3. stack.c

    1. #include "stack.h"
    2. #include 
    3. #include 
    4.  
    5. StackList *create_stack()
    6. {
    7. 	StackList *pstack = malloc(sizeof(StackList));
    8. 	if (NULL == pstack)
    9. 	{
    10. 		perror("fail malloc");
    11. 		return NULL;
    12. 	}
    13. 	pstack->ptop = NULL;
    14. 	pstack->clen = 0;
    15.  
    16. 	return pstack;
    17. }
    18. int is_empty_stack(StackList *pstack)
    19. {
    20. 	if (NULL == pstack->ptop)
    21. 	{
    22. 		return 1;
    23. 	}
    24. 	return 0;
    25. }
    26. int push_stack(StackList *pstack, DataType data)
    27. {
    28. 	StackNode *pnode = malloc(sizeof(StackNode));
    29. 	if (NULL == pnode)
    30. 	{
    31. 		perror("fail malloc");
    32. 		return -1;
    33. 	}
    34. 	pnode->data = data;
    35. 	pnode->pnext = NULL;
    36.  
    37. 	pnode->pnext = pstack->ptop;
    38. 	pstack->ptop = pnode;
    39.  
    40. 	pstack->clen++;
    41.  
    42. 	return 0;
    43. }
    44. int pop_stack(StackList *pstack, DataType *pdata)
    45. {
    46. 	if (is_empty_stack(pstack))
    47. 	{
    48. 		return 1;
    49. 	}
    50. 	
    51. 	StackNode *pfree = pstack->ptop;
    52. 	pstack->ptop = pfree->pnext;
    53. 	if (pdata != NULL)
    54. 	{
    55. 		*pdata = pfree->data;
    56. 	}
    57. 	free(pfree);
    58. 	pstack->clen--;
    59. 	
    60. 	return 0;
    61. }
    62. void clear_stack(StackList * pstack)
    63. {
    64. 	while (!is_empty_stack(pstack))
    65. 	{
    66. 		pop_stack(pstack, NULL);
    67. 	}
    68. }
    69. void destaroy_stack(StackList *pstack)
    70. {
    71. 	clear_stack(pstack);
    72. 	free(pstack);
    73. }
    74. int get_stack_top(StackList *pstack, DataType *pdata)
    75. {
    76. 	if (is_empty_stack(pstack))
    77. 	{
    78. 		return 1;
    79. 	}
    80. 	*pdata = pstack->ptop->data;
    81. 	return 0;
    82. }

            4. stack.h

    1. #ifndef __STACK_H__
    2. #define __STACK_H__
    3.  
    4. typedef int DataType;
    5.  
    6. typedef struct stk_node
    7. {
    8. 	DataType data;
    9. 	struct stk_node *pnext;
    10. }StackNode;
    11.  
    12. typedef struct Stack
    13. {
    14. 	StackNode *ptop;
    15. 	int clen;
    16. }StackList;
    17.  
    18. StackList *create_stack();
    19. int is_empty_stack(StackList *);
    20. int push_stack(StackList *, DataType );
    21. int pop_stack(StackList *, DataType *);
    22. void clear_stack(StackList *);
    23. void destaroy_stack(StackList *);
    24. int get_stack_top(StackList *, DataType *);
    25.  
    26. #endif

            

            

  • 相关阅读:
    云原生Docker网络管理
    SpringCach
    零基础学算法100天第8天——双指针（基础算法）
    AJAX之数据交换
    centos7安装git客户端
    【buildroot】buildroot使用笔记-03 | 系统初始化的三种方式
    linux用户及用户组的分类、管理
    手把手教会你|Sockets多用户-服务器数据库编程
    18. 机器学习——集成学习
    腾讯云轻量应用服务器性能如何？来自学生的评价
  • 原文地址：https://blog.csdn.net/qq_47798402/article/details/139793109