C语言--day19

第十章 内存管理

当./a.out 运行起来后，系统会给a.out分配一段内存区域

1、code ，存放编写好的c语言代码。 只读特性，在运行期间不能修改

2、data 数据段。 存储全局变量，和被static 修改的变量

细分：

• data 数据段，有初值的全局变量和static 变量

• bss 未初始化的数据段。包含没有给初值的全局变量和static 变量。由系统负责初始化为0

• rodata 只读数据段。其中包含字符串常量

3、heap 堆区 <2.9G 程序在运行时，需要内存的时候，在堆中申请。相对堆空间比较大，可以自动增长

• 如果需要空间，需要手动申请(malloc)。使用完毕后需要手动释放内存(free). 申请内存后，没有释放的，那么这段空间一致存在，直到释放或程序关闭。由程序员决定生命周期

4、共享区 只存储库函数的实现。比如 ，printf，scanf ， 共享库(动态库文件) ldd ./a.out

5、栈区 （堆栈）8M 内存空间自动申请和释放。 局部变量，函数参数，返回地址。出了作用域，内存就会释放

作用：

1. 可以获得相对大的内存
2. 内存使用率提供
3. 内存的泄露

• 只申请堆内存空间不释放。 系统内存空间枯竭，程序会异常退出。
• 当申请堆空间后，不小心把保存堆空间地址的指针被覆盖了。 那么原来保存的堆空间，就丢失了

#include <stdlib.h> malloc 分配堆空间内存 ， 参数是需要内存的大小。 返回值是分配到堆内存空间的地址值。地址值需要 保留好，直到释放前。 void *malloc(size_t size); 释放对内存空间， 参数如要传入，当时malloc的返回值。这个值要和但是分配空间的地址值一致。 void free(void *ptr); 释放完后， ptr =NULL， 不然ptr 是野指针。 也不要试图去访问原来的堆空间数据。 从逻辑上认为，堆 空间数据生命周期结束

数据结构（程序设计 = 数据结构 + 算法）

定义：一组用来保存一种或多种特定关系的数据集合（组织和存储数据）

数据与数据之间的关系

逻辑结构：数据元素与元素之间的关系

• 集合：平等关系
• 线性结构：元素与元素之间一对一的关系(顺序表，链表，队列、栈)
• 树形结构：元素与元素之间一对多的关系(二叉树)
• 图形结构：元素与元素之间多对多的关系(图)

物理结构：数据元素在计算机内存中的存储方式

顺序结构：选用一段连续的内存空间(数组)

1. 数据访问方便（O（1））
2. 元素插入和删除需要移动大量数据，效率低
3. 预分配内存空间

链式结构：选用非连续的内存空间(链表)

1. 数据访问需要遍历（O（n））
2. 插入和删除元素方便
3. 不需要预分配，可以动态存储
4. 可以有效利用内存碎片 内存碎片：一些游离的小的内存空间

散列结构（哈希结构）：将要存储的数据的关键字和存储位置之间构建映射关系（哈希函数）；

1. 存储和查找都根据映射关系查找
2. 为了提高数据的查找效率

索引存储：通关索引表寻找数据的存储位置。

1. 为了提高数据的查找效率

设计思想：

封装-->>模块化-->>高内聚：一个功能模块只做一件事
低耦合：模块与模块之间的关联度低

链表

单向链表：

link.h

#ifndef __LINK_H__ #define __LINK_H__ //存储的数据类型 typedef int Datatype_t; //链表结点类型 typedef struct node { Datatype_t data; //链表数据域 struct node *pnext; //链表的指针域 }Node_t; //链表对象类型 typedef struct link { Node_t *phead; //链表头结点地址 int clen; //链表当前结点个数 }Link_t; extern Link_t *create_link(); extern int insert_link_head(Link_t *plink, Datatype_t data); extern void show_link(Link_t *plink); extern int insert_link_tail(Link_t *plink, Datatype_t data); extern int is_empty_link(Link_t *plink); extern int delete_link_head(Link_t *plink); extern int delete_link_tail(Link_t *plink); #endif

遍历：

#include "link.h" #include <stdio.h> #include <stdlib.h> Link_t *create_link() { Link_t *plink = malloc(sizeof(Link_t)); if (NULL == plink) { printf("malloc error\n"); return NULL; } plink->phead = NULL; plink->clen = 0; return plink; } void show_link(Link_t *plink) { Node_t *ptmp = plink->phead; while (NULL != ptmp) { printf("%d ", ptmp->data); ptmp = ptmp->pnext; } printf("\n"); }

头插：

int is_empty_link(Link_t *plink) { if (NULL == plink->phead) { return 1; } return 0; } int insert_link_tail(Link_t *plink, Datatype_t data) { Node_t *pnode = malloc(sizeof(Node_t)); if (NULL == pnode) { printf("malloc error\n"); return -1; } pnode->data = data; pnode->pnext = NULL; if (is_empty_link(plink)) { plink->phead = pnode; } else { Node_t *p = plink->phead; while (p->pnext != NULL) { p = p->pnext; } p->pnext = pnode; } plink->clen++; return 0; }

#include "link.h" #include <stdio.h> int main(int argc, const char *argv[]) { Link_t *plink = NULL; plink = create_link(); if (NULL == plink) { return -1; } insert_link_head(plink, 1); insert_link_head(plink, 2); insert_link_head(plink, 3); insert_link_head(plink, 4); insert_link_head(plink, 5); show_link(plink); }

尾插：

int delete_link_head(Link_t *plink) { if (is_empty_link(plink)) { return 0; } Node_t *pfree = plink->phead; plink->phead = pfree->pnext; free(pfree); plink->clen--; return 0; }

#include "link.h" #include <stdio.h> int main(int argc, const char *argv[]) { Link_t *plink = NULL; plink = create_link(); if (NULL == plink) { return -1; } insert_link_head(plink, 1); insert_link_head(plink, 2); insert_link_head(plink, 3); insert_link_head(plink, 4); insert_link_head(plink, 5); show_link(plink); insert_link_tail(plink, 6); insert_link_tail(plink, 7); insert_link_tail(plink, 8); insert_link_tail(plink, 9); insert_link_tail(plink, 10); show_link(plink); return 0； }

头删:

int delete_link_head(Link_t *plink) { if (is_empty_link(plink)) { return 0; } Node_t *pfree = plink->phead; plink->phead = pfree->pnext; free(pfree); plink->clen--; return 0; }

delete_link_head(plink); //直接调用函数

尾删：

int delete_link_tail(Link_t *plink) { if (is_empty_link(plink)) { return 0; } else if (1 == plink->clen) { delete_link_head(plink); } else { Node_t *p = plink->phead; while (p->pnext->pnext != NULL) { p = p->pnext; } free(p->pnext); p->pnext = NULL; plink->clen--; } return 0; }

delete_link_tail(plink); //直接调用函数

释放内存：

void destroy_link(Link_t *plink) { while (!is_empty_link(plink)) { delete_link_head(plink); } free(plink); }

内存泄露检查：

valgrind ：GNU提供的一个内存错误检查软件

安装：sudo apt-get install valgrind