编程预备_数据结构与算法教程

两个必备的函数知识（其均来自于stdlib.h库中）

1. Malloc函数

malloc（）函数在堆中申请分配一个大小为size个字节的连续内存空间，若成功分配，则返回一个指向所分配空间起始地址的指针，否则返回空指针（NULL）。

2.Free函数

free（）函数用来释放已分配的内存空间，参数p是待释放的内存空间的首指针

总结来说malloc就是用来申请内存空间，而free是为了释放内存空间，这两个函数在C/C++语言的数据结构中十分重要，也十分常用，请务必牢记，这里总结几个新手易犯的错误：

a)忽略判断是否内存申请失败，如果内存申请失败并没有执行一些中断之类的操作，程序会继续向下运行，直到各种错误把整个程序弄崩溃

b)使用malloc不适用free，这在做题中似乎无关紧要，但是一旦在工作中养成这样的习惯，则会制造出很多无用的内存垃圾，造成程序效率的低下，当然了，后面出现了内存回收机制可以自动帮我们free掉内存垃圾，但是依旧要养成即时释放内存的好习惯。

c)使用指针后胡乱进行移动，产生不知名的指针位移，这样的效果往往是不知道自己的程序究竟出了什么错误，也极其难修改。

一般而言，常规的内存分配，使用再到释放的过程如下：

#include<stdio.h>
#include<stdlib.h>
int main(){
    int *p;     //定义一个指向整形的指针变量
    p=(int*)malloc(5*sizeof(int));  //申请5个整形大小的内存空间并返回起始地址给p
    if(p==NULL){    //申请失败
        //执行申请失败的代码，一般print一个报错
        exit(1);    //退出
    }
    p[0]=1000;  //为空间中添加数据
    printf("%d",p[0]);  //打印这个数据
    free(p);    //释放p的内存空间，此时p依旧存在，只不过失去了指向的对象，成了野指针
    p=NULL; //为其赋NULL，此时它不再是一个野指针
    return 0;
}

很显然，我们设计一个数据结构程序的过程是先定义所需要的变量与指针变量---->进行内存分配---->判断是否分配成功(分配不成功就报错或者退出程序)---->对指针空间中的数据进行操作(如赋值，修改，查询，删除) ---->完成操作后释放指针

除上文提到的两个函数外，在C++中引入的对象思维，有一个极其类似于malloc函数的方法，就是new方法，但他们还是有一些区别的：

new操作符从自由存储区（free store）上为对象动态分配内存空间，而malloc函数从堆上动态分配内存。自由存储区是C++基于new操作符的一个抽象概念，凡是通过new操作符进行内存申请，该内存即为自由存储区。而堆是操作系统中的术语，是操作系统所维护的一块特殊内存，用于程序的内存动态分配，C语言使用malloc从堆上分配内存，使用free释放已分配的对应内存。