动态内存分配链表.pptxVIP

第10章链表开始

批量数据的存储批量数据的存储方式:数组存储的缺陷：必须预先指定数组的大小链表：不需要事先指定空间大小，动态分配与释放数组链表太小？太大？

主要内容动态内存分配单链表概述单链表结点的基本操作单链表的建立单链表的应用循环链表与约瑟夫环问题

C程序的内存划分内存分配方式动态内存分配函数1动态内存分配

栈区stack静态区static堆区heap代码区code数据区代码区memory存放程序的代码存放程序的全局数据和静态数据存放程序动态申请的数据存放程序的局部数据和参数1-1C程序的内存划分

栈区（stack）：编译器自动分配释放，存放函数参数、局部变量等。堆区（heap）：一般由程序员分配释放，若程序员不释放，程序结束时可能由操作系统回收。全局区（静态区）（static）：存放全局变量和静态变量，其中初始化的全局与静态变量在一块区域，未初始化的全局与静态变量在相邻的另一块区域。程序结束后由系统释放。文字常量区：存放常量字符串，程序结束后由系统释放。程序代码区：存放函数体的二进制代码。1-1C程序的内存划分

根据内存分配的时机，可分为：根据内存分配区域的不同，又可以分为：静态内存分配；动态内存分配；静态存储区分配；栈区分配；堆区分配；1-2内存分配方式

内存分配方式静态存储区域分配。编译阶段完成分配，在程序结束后内存空间才会被释放。例如全局变量，static?变量。栈区创建。在执行函数时，函数局部变量可在栈区创建，函数执行结束时自动释放。栈内存分配运算内置于处理器的指令集中，效率很高，但是分配的内存容量有限。

内存分配方式01堆区分配，亦称动态内存分配。程序在运行的时候用malloc?或new?申请任意内存，程序员负责用free?或delete?释放内存。生存期由程序员决定，使用非常灵活。02如何使用一个大数组：栈区分配?静态区分配堆区分配?03

1-2内存分配方式静态分配与动态分配的注意事项静态内存分配把内存的控制权交给了编译器，而动态内存分配则把内存的控制权交给了程序员动态内存管理水平严重依赖于程序员的水平，如果处理不当容易造成内存泄漏动态内存的分配与释放需要占用额外的CPU资源要避免频繁的使用动态内存分配

1-3C的动态内存分配函数

1-3C的动态内存分配函数malloc函数：void*malloc(unsignedintsize);向系统申请分配指定字节数的存储空间：分配成功：返回新分配存储空间的首地址，新分配存储空间未被初始化；分配失败：返回NULL例如：inti,*p=(int*)malloc(6*sizeof(int));if(p)for(i=0;i6;i++)p[i]=i;elseprintf(dynamicallocfailed!);

1-3C的动态内存分配函数#includestdio.h#includestdlib.hintmain(){ inti,j; int*array=NULL; scanf(%d,i); array=(int*)malloc(i*sizeof(int)); for(j=0;ji;j++) scanf(%d,array[j]); for(j=0;ji;j++) printf(%d\n,array[j]); return0;}

1-3C的动态内存分配函数

1-3C的动态内存分配函数#includestdio.h#includestdlib.hintmain(){ inti,j; int*array=NULL; scanf(%d,i); array=(int*)malloc(i*sizeof(int)); for(j=0;ji;j++) scanf(%d,array[j]); for(j=0;ji;j++) printf(%d\n,array[j]); free(array); return0;}

1-3C的动态内存分配函数

realloc函数：void*realloc(void*p_block,unsignedintsize);对指针所指向的已动态分配的存储空间重新进行动态存储分配如果缩小空间则返回的地址是原地址;如果是扩大空间，则有三种可能：0103021-3C的动态内存分配函数

原空间位置有足够的空间可以扩充，返回的地址与扩充前的地址相同；如果原位置无足够的空间而其它位置有足够的空间，按照size指定的大小重新分配空间，将原有数据从头到尾拷贝到新分配的内存区域，而后释放原来指针所指内存区域，同时返回新分配的内存区域的首地址；否则说明内存无足够的空间可以分配，分配失败，返回值为NULL。1231-3C的动态内存