表格模板-C语言课件第17部分 动态存储空间管理与链表 精品.ppt

《表格模板-C语言课件第17部分 动态存储空间管理与链表 精品.ppt》由会员分享，可在线阅读，更多相关《表格模板-C语言课件第17部分 动态存储空间管理与链表 精品.ppt（51页珍藏版）》请在第一文库网上搜索。

1、2022-9-211第十七第十七 章章动态存储空间管理与动态存储空间管理与链表链表2022-9-212一、动态存储分配及常见函数说明隐式和显式教师：林友芳32022-9-211. 引例n要处理学生成绩，需要用数组存放。但编程时并不知道运行时需要处理多少学生成绩，每次处理的成绩项数也可能不同。nint n;n.nscanf(%d, &n);ndouble scoresn; /* 不行！*/n. /* 读入数据，然后处理 */n不能用变量说明scores大小（必须静态确定）。教师：林友芳42022-9-212. 问题的本质及解决方案n问题的本质n程序运行中需要使用存储，有时程序对存储的需求量在写程

2、序时不能确定。n可能解决方案1）分析问题，定义适当大小的数组。若分析正确，一般都能处理。但数据很多时程序就不能用。2）定义尽可能大的数组以满足任何需要。浪费大量存储资源。如有多个这种数组就更难办。系统可能无法容纳几个大数组，但实际上它们并不同时需要很大空间。n解决的办法是“动态存储分配”。在程序运行中做存储分配工作。教师：林友芳52022-9-213. 动态存储分配n动态存储分配n根据运行中的需要分配存储，取得存储块使用，称为动态存储分配。在运行中根据需要动态进行。n动态存储块具有起始地址，地址可以存储在指针里，因此可以借助于指针保存存储空间地址。n用指针指向存储块，间接使用被指存储。访问动态

3、分配存储是指针的最重要用途。教师：林友芳62022-9-214. 动态存储释放及存储堆n动态释放n不用的动态存储块应交还系统，动态申请的内存空间必须由程序代码以显式的方式主动释放。n动态分配、释放由动态存储管理系统完成，这是程序运行系统的子系统，管理着称作堆（英文heap）的存储区。n大部分常规语言都有这种机制。教师：林友芳72022-9-215. C语言的动态存储管理机制n用标准库函数实现用标准库函数实现nstdlib.hstdlib.hnmalloc.hmalloc.hn存储分配函数存储分配函数mallocmalloc() ()，原型：，原型：nvoid void * *malloc(si

4、ze_tmalloc(size_t n); / n); /* *size_tsize_t是某整型是某整型* */ /n功能功能n分配一块不小于分配一块不小于n n的存储，返回其地址。无法的存储，返回其地址。无法满足时返回空指针值。满足时返回空指针值。教师：林友芳82022-9-21例intint n; double n; double * *data;data;. scanf(%d. scanf(%d, &n);, &n);data=(doubledata=(double* *)malloc(n)malloc(n* *sizeof(doublesizeof(double););if (data

5、 = NULL) if (data = NULL) . / . /* * 分配未完成时的处理分配未完成时的处理 * */ / .datai.datai.* *(data+j(data+j)./)./* *正常处理正常处理* */ /教师：林友芳92022-9-21malloc说明nmalloc使用注意事项：n的返回值（void*）应通过类型强制转为特定指针类型后赋给指针变量。n分配存储块大小应该用sizeof计算n动态分配必须检查成功与否n动态分配的块大小也是确定的。越界使用（尤其是越界赋值）是严重错误，可能导致程序或系统垮台教师：林友芳102022-9-216. callocn带计数和清带计

6、数和清0 0的存储分配函数的存储分配函数calloccalloc，原型：，原型：nvoid void * *calloc(size_tcalloc(size_t n, size_t size); n, size_t size);nsizesize是元素大小，是元素大小，n n是个数。是个数。n分配一块存储，足够存分配一块存储，足够存n n个大小为个大小为sizesize的元素，并的元素，并把元素把元素全部清全部清0 0；n无法分配时返回空指针值。前面的存储分配问题无法分配时返回空指针值。前面的存储分配问题也可用下面语句实现也可用下面语句实现ndata = (doubledata = (doub

7、le* *)calloc(n, sizeof(double)calloc(n, sizeof(double););n主要差别主要差别nmallocmalloc对所分配的区域不做任何事情，对所分配的区域不做任何事情，calloccalloc对整个区对整个区域自动清域自动清0 0。教师：林友芳112022-9-217. 空间释放函数：freen为保证动态存储的有效使用，动态分配块不再用时应释放。动态存储块的释放只能通过调用free完成。Memory leakn函数原型nvoid free(void *p);n功能nfree释放p指的存储块。n注意n该块必须是通过动态存储分配得到的，不要对并非指向动

8、态分配块的指针用本操作np值为空时什么也不做n执行free(p)后p值未变，被指块可能已变。不允许再间接访问已释放存储块教师：林友芳122022-9-218. 8. 分配调整函数分配调整函数reallocn函数原型nvoid *realloc(void *p, size_t n);n功能n更改已有分配。p指原分配块，n是新大小要求。n返回大小至少为n的存储块指针，新块与原块一致：n新块小时保存原块n范围内数据；n新块大时原数据存在，新增部分不初始化。分配成功后原块可能改变。n无法满足时返回空指针，原块不变。n常用写法(防止分配失败导致原存储块丢失) ：nq = (double*)realloc

9、(p, m * sizeof(double);nif (q = NULL) /*未成功，p仍指原块，特殊处理*/ nelse p = q; /* 令p指向新块，正常处理 */ .2022-9-2113二、动态存储空间管理如果动态申请了许多同类型缓冲区，该如何管理？教师：林友芳142022-9-21方法1：指针数组（地址数组）n设置一段内存空间，例如数组，用来保存存储空间的起始地址。n数组中每个元素用来保存某种类型的存储空间的地址，等于每个元素都是一个指针变量。nint *pnarr10; /定义一个长度为10的整型指针数组（整型地址数组）nchar *psz5; /定义一个长度为5的字符指针数

10、组。0 x0012ff7d0 x0012ff800 x0012fe12其中每个元素都用来保存某种类型的存储空间的地址教师：林友芳152022-9-21例如n设一个班最多有50人，但每个班的人数不定，为了表示这50用户，可以定义如下指针数组nstruct UserAccount *Accounts 50;n完成如下功能n初始化指针数组n将新生成的某个班用户加入班级用户集，并存放在空位置上。n将某个班指定用户号的用户删除n给某个班所有女生发m元补助n将新生成的某个班用户插入到指定位置i上，i后面的用户顺序往后退。教师：林友芳162022-9-21指针数组结构示例0 x0012ff6dNULL0 x

11、0012ff800 x0012ce000 x0012fe1208120001 张帅帅110108M0.1008120099 李美美350108F500.0008120002 赵小飞360108M20.0008120007 罗小花410108F88.200 x0012ff6d0 x0012ff800 x0012ce000 x0012fe12长度为50空指针，可能曾被删除后续元素或空或不空Accounts教师：林友芳172022-9-21功能实现n初始化指针数组void InitAccounts(struct UserAccount *Accounts, int nLen) for (int i

12、= 0; i nLen; i+) Accountsi = NULL;n寻找一个空位置返回，-1表示无空位置int FindEmptyPlace(struct UserAccount *Accounts, int nLen) /可以有不同的搜索策略NULLNULL教师：林友芳182022-9-21功能实现（续）n将新用户放在空位置上，不成功返回-1，成功返回位置号int AddNewAccountAtAnyEmptyPlace(struct UserAccount *Accounts, int nLen, struct UserAccount *pUser) int nPlace;if (nPl

13、ace = FindEmptyPlace(Accounts, nLen) = -1) return -1; AccountsnPlace = pUser; /完成放置操作 return nPlace; /返回位置教师：林友芳192022-9-21功能示例0 x0012ff6dNULL0 x0012ff800 x0012ce000 x0012fe1208120001 张帅帅110108M0.1008120099 李美美350108F500.0008120002 赵小飞360108M20.0008120007 罗小花410108F88.200 x0012ff6d0 x0012ff800 x0012

14、ce000 x0012fe12长度为50Accounts08120100 孙悟空110105M600.100 x0012ff300 x0012ff30新找到的空位新结点孙悟空报到教师：林友芳202022-9-21功能实现（续）n将指定用户号的用户删除，返回该用户原来所在位置int DeleteAccountByNumber(struct UserAccount *Accounts, int nLen, char *pszUserNO) int i; for (i = 0; i szUserNO) = 0) free(Accountsi); /释放空间 Accountsi = NULL; /将当

15、前位置置空 return i; return -1;用户结构体指针数组数组长度用户号字符串比较函数教师：林友芳212022-9-21删除功能示例0 x0012ff6d0 x0012ff300 x0012ff800 x0012ce000 x0012fe1208120001 张帅帅110108M0.1008120099 李美美350108F500.0008120002 赵小飞360108M20.0008120007 罗小花410108F88.200 x0012ff6d0 x0012ff800 x0012ce000 x0012fe12Accounts08120100 孙悟空110105M600.10

16、0 x0012ff30NULL把孙悟空位置找到把孙悟空开除:DeleteAccountByNumber(Accounts, 50, “08120100”)释放存储空间教师：林友芳222022-9-21功能实现（续）n给指定性别的群体充值，返回充值人数int ChargeByGender(struct UserAccount *Accounts, int nLen, char cGender, double dAmount) int nCounter = 0; /计数器 for (int i = 0; i cGender = cGender) Accountsi-dBalance+= dAmount; nCounter+; return nCounter;ChargeByGender(Accounts, 50, F, 10.0);/妇女节发补助教师：林友芳232022-9-21方法2：链接结构n采用链式数据结构n一环扣一扣，通过一个元素保存的其它元素的地址找到其它元素。n通过链接结构实现动态数据n增加元素：在铁链的某个位置加一铁环n删除元素：去掉铁链的某一铁环n问题n铁链中的每一铁环是一