笔记2：C语言的内存管理，用户栈的代码实现

概要

本节是笔记2：C语言的内存管理，用户栈的代码实现学习记录。

内存分区

C语言中的内存分区从上往下依次是：

  • 栈区：存放局部变量、函数传递的参数、函数返回值及返回地址、const定义的局部变量。
  • 堆区：一块可分配内存，堆区由程序员分配内存和释放
  • .bss段：存放未初始化或初始值为0的全局变量，特点是不占用可执行文件空间，.bss段通常需要进行清零操作。
  • .data段：存放有初始值的全局变量、静态变量，其中const修饰的变量存放在.rodata段。.data段涉及代码重定位，.data的初始值需要被拷贝至运行地址才能正常访问，在C标准函数__main中实现拷贝。
  • 常量区：const修饰的全局变量或静态变量，STM32中会将其保存在FLASH中，也叫.rodata段。
  • 代码段：存放程序的代码，即被转化为机器码的二进制数据。
  • 空字节段：从0地址开始直到代码段的区域， 是没有用到的字节区域，一般存放指向NULL的空指针。

堆

malloc

一般使用方式如下：

1
struct stack_t *p = (struct stack_t *)malloc(sizeof(struct stack_t));

申请一块想要的内存大小并返回首地址，Linux中内部是通过sbrk函数向内核申请内存来实现的，其内部还需要实现查找内存块、各种内存块链表操作等，这里不细说。

free

一般使用方式如下：

1
free(p);					//记得释放内存

free只能释放malloc返回的指针，否则会报错，free内部操作较为复杂，除了将已申请的malloc内存块插入到空闲内存块链表以外，还要完成相邻内存块合并等操作来最大限度利用空间，最大程度减少内存碎片。
==只malloc而不进行free将会导致内存泄漏，导致之前被申请的内存块处于空闲但不能被再次申请==

栈

栈操作通常由编译器自己完成，通常在程序需要调用函数跳转时进行栈的操作，栈操作有push入栈和pop出栈。可以通过编写简单的函数调用程序，然后观察其反汇编代码查看编译器入栈和出栈的过程。这里不细说，本节重点在下文。

用户栈的代码实现

用户栈分类

  • 数组栈：栈内存是数组，一块连续的内存，大小自定义指定，数组的索引作为栈顶指针。
  • 链表栈：栈内存需要动态分配，一个数据对应一个结点，大小视程序而定，不需要自己指定，以头结点的node属性作为索引。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#define STACK_MAX_SIZE	1*1024		//设置栈大小

#define ARRAY_STACK		1			//指定使用数组栈
#define LIST_STACK		2			//指定使用链表栈
#define STACK_TYPE ARRAY_STACK   	//指定使用哪种栈类型

//构建自定义栈结构体
typedef struct stack_t{
#if STACK_TYPE == ARRAY_STACK
    int stack_data[STACK_MAX_SIZE]; //栈内存
    int stack_sp;                   //栈顶指针
#elif STACK_TYPE == LIST_STACK
    int data;						//栈结点数据
    struct stack_t *next;			//指向下一个结点
#endif
}stacks;

新建栈和初始化栈

  • 数组栈：定义一个栈结构体，编译器自动分配内存，再把==栈顶指针==即数组索引值设置为0即可。
  • 链表栈：定义一个栈结构体，编译器自动分配内存，再把==栈顶指针==即栈链表头部next设置为NULL即可。
1
2
3
4
5
6
7
8
void StackUserInit(struct stack_t *pStack_User)
{
#if STACK_TYPE == ARRAY_STACK
	pStack_User->stack_sp = 0;
#elif STACK_TYPE == LIST_STACK
	pStack_User->next = NULL;
#endif
}

Push实现

  • 数组栈Push：先填入数据，再栈顶指针偏移。
  • 链表栈Push：先申请一个新的数据结点的内存并将数据填入，再插入到栈链表头部结点next属性之后。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    /********************************************************
    * Description   : 入栈
    * @pStack_User  : 目标栈的指针
    * @data  		: 入栈数据
    * Return        : 0:入栈成功    
    *				 -1：入栈失败，可能是栈满了
    **********************************************************/
    int Push(struct stack_t *pStack_User, int data)
    {
    #if STACK_TYPE == ARRAY_STACK
    	/* 如果栈还没满 */
    	if(pStack_User->stack_sp != STACK_MAX_SIZE){
    		pStack_User->stack_data[pStack_User->stack_sp] = data;	//数据入栈
    		pStack_User->stack_sp++;								//栈顶指针偏移
    		return 0;
    	}
    	else{
    		/* 栈已满 */
    		return -1;
    	}
    #elif STACK_TYPE == LIST_STACK
    	struct stack_t *p = (struct stack_t *)malloc(sizeof(struct stack_t));
    	if(p){
    		/* 先储存数据 */
    		p->data = data;
    		/* 再插入链表 */
    		p->next = pStack_User->next;
    		pStack_User->next = p;
    		return 0;
    	}
    	else{
    		/* 内存申请失败，入栈失败 */
    		return -1;
    	}
    #endif
    }

Pop实现

  • 数组栈Pop：先将栈顶指针偏移，再返回数据。
  • 链表栈Pop：先将当前栈顶指针next属性处数据储存，再删除该结点并释放内存，最后返回数据。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    /********************************************************
    * Description   : 出栈
    * @pStack_User  : 目标栈的指针
    * @data  		: 数据存储指针
    * Return        : 0:入栈成功    
    *				 -1：入栈失败，可能是栈满了
    **********************************************************/
    int Pop(struct stack_t *pStack_User, int *data)
    {
    #if STACK_TYPE == ARRAY_STACK
    	/* 如果栈不是空的 */
    	if(pStack_User->stack_sp != 0){
    		pStack_User->stack_sp--;								//栈顶指针偏移
    		*data = pStack_User->stack_data[pStack_User->stack_sp];	//数据出栈
    		return 0;
    	}
    	else{
    		/* 栈是空的 */
    		return -1;
    	}
    #elif STACK_TYPE == LIST_STACK
    	struct stack_t *p = pStack_User->next;	//获得头结点后第一个栈结点指针
    	/* 如果栈不是空的 */
    	if(p){
    		pStack_User->next = p->next;//删除该栈结点
    		*data = p->data;			//返回数据
    		free(p);					//记得释放内存
    		return 0;
    	}
    	else{
    		/* 栈是空的 */
    		return -1;
    	}
    #endif
    }

用户栈操作注意

  • Push与Pop都需要判断栈满与栈空的情况，代码中均已体现。

完整工程代码

  • 所有代码均已进行测试，在windows上可以正常运行。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include "stdio.h"
#include "stdlib.h"

#define STACK_MAX_SIZE	1*1024		//设置栈大小

#define ARRAY_STACK		1			//指定使用数组栈
#define LIST_STACK		2			//指定使用链表栈
#define STACK_TYPE ARRAY_STACK   	//指定使用哪种栈类型

//构建自定义栈结构体
typedef struct stack_t{
#if STACK_TYPE == ARRAY_STACK
    int stack_data[STACK_MAX_SIZE]; //栈内存
    int stack_sp;                   //栈顶指针
#elif STACK_TYPE == LIST_STACK
    int data;						//栈结点数据
    struct stack_t *next;			//指向下一个结点
#endif
}stacks;

/********************************************************
* Description   : 入栈
* @pStack_User  : 目标栈的指针
* @data  		: 入栈数据
* Return        : 0:入栈成功    
*				 -1：入栈失败，可能是栈满了
**********************************************************/
int Push(struct stack_t *pStack_User, int data)
{
#if STACK_TYPE == ARRAY_STACK
	/* 如果栈还没满 */
	if(pStack_User->stack_sp != STACK_MAX_SIZE){
		pStack_User->stack_data[pStack_User->stack_sp] = data;	//数据入栈
		pStack_User->stack_sp++;								//栈顶指针偏移
		return 0;
	}
	else{
		/* 栈已满 */
		return -1;
	}
#elif STACK_TYPE == LIST_STACK
	struct stack_t *p = (struct stack_t *)malloc(sizeof(struct stack_t));
	if(p){
		/* 先储存数据 */
		p->data = data;
		/* 再插入链表 */
		p->next = pStack_User->next;
		pStack_User->next = p;
		return 0;
	}
	else{
		/* 内存申请失败，入栈失败 */
		return -1;
	}
#endif
}

/********************************************************
* Description   : 出栈
* @pStack_User  : 目标栈的指针
* @data  		: 数据存储指针
* Return        : 0:入栈成功    
*				 -1：入栈失败，可能是栈满了
**********************************************************/
int Pop(struct stack_t *pStack_User, int *data)
{
#if STACK_TYPE == ARRAY_STACK
	/* 如果栈不是空的 */
	if(pStack_User->stack_sp != 0){
		pStack_User->stack_sp--;								//栈顶指针偏移
		*data = pStack_User->stack_data[pStack_User->stack_sp];	//数据出栈
		return 0;
	}
	else{
		/* 栈是空的 */
		return -1;
	}
#elif STACK_TYPE == LIST_STACK
	struct stack_t *p = pStack_User->next;	//获得头结点后第一个栈结点指针
	/* 如果栈不是空的 */
	if(p){
		pStack_User->next = p->next;//删除该栈结点
		*data = p->data;			//返回数据
		free(p);					//记得释放内存
		return 0;
	}
	else{
		/* 栈是空的 */
		return -1;
	}
#endif
}

void StackUserInit(struct stack_t *pStack_User)
{
#if STACK_TYPE == ARRAY_STACK
	pStack_User->stack_sp = 0;
#elif STACK_TYPE == LIST_STACK
	pStack_User->next = NULL;
#endif
}

void PrintStack(struct stack_t *pStack_User)
{
	int buf;
	int i=0;

	while(Pop(pStack_User, &buf) == 0)
	{
		printf("Stack_User_Pop top%d: %d\r\n",i++, buf);
	}
}


int main(int argc, char *argv[])
{
	struct stack_t Stack_User;
	StackUserInit(&Stack_User);

	Push(&Stack_User, 100);
	Push(&Stack_User, 200);
	Push(&Stack_User, 300);
	Push(&Stack_User, 400);
	Push(&Stack_User, 500);

	PrintStack(&Stack_User);

    printf("完成!\r\n");
}
笔记2：C语言的内存管理，用户栈的代码实现
http://example.com/2024/08/30/笔记2：C语言的内存管理，用户栈的代码实现/
作者
John Doe
发布于
2024年8月30日
许可协议