(C语言课件)第17部分 动态存储空间管理与链表

2019/9/201第十七章动态存储空间管理与链表2019/9/202一、动态存储分配及常见函数说明隐式和显式北京交通大学计算机与信息技术学院教师：林友芳32019/9/201.引例要处理学生成绩，需要用数组存放。但编程时并不知道运行时需要处理多少学生成绩，每次处理的成绩项数也可能不同。intn;...scanf(%d,&n);doublescores[n];/*不行！*/.../*读入数据，然后处理*/不能用变量说明scores大小（必须静态确定）。北京交通大学计算机与信息技术学院教师：林友芳42019/9/202.问题的本质及解决方案问题的本质程序运行中需要使用存储，有时程序对存储的需求量在写程序时不能确定。可能解决方案1）分析问题，定义适当大小的数组。若分析正确，一般都能处理。但数据很多时程序就不能用。2）定义尽可能大的数组以满足任何需要。浪费大量存储资源。如有多个这种数组就更难办。系统可能无法容纳几个大数组，但实际上它们并不同时需要很大空间。解决的办法是“动态存储分配”。在程序运行中做存储分配工作。北京交通大学计算机与信息技术学院教师：林友芳52019/9/203.动态存储分配动态存储分配根据运行中的需要分配存储，取得存储块使用，称为动态存储分配。在运行中根据需要动态进行。动态存储块具有起始地址，地址可以存储在指针里，因此可以借助于指针保存存储空间地址。用指针指向存储块，间接使用被指存储。访问动态分配存储是指针的最重要用途。北京交通大学计算机与信息技术学院教师：林友芳62019/9/204.动态存储释放及存储堆动态释放不用的动态存储块应交还系统，动态申请的内存空间必须由程序代码以显式的方式主动释放。动态分配、释放由动态存储管理系统完成，这是程序运行系统的子系统，管理着称作堆（英文heap）的存储区。大部分常规语言都有这种机制。北京交通大学计算机与信息技术学院教师：林友芳72019/9/205.C语言的动态存储管理机制用标准库函数实现stdlib.hmalloc.h存储分配函数malloc()，原型：void*malloc(size_tn);/*size_t是某整型*/功能分配一块不小于n的存储，返回其地址。无法满足时返回空指针值。北京交通大学计算机与信息技术学院教师：林友芳82019/9/20例intn;double*data;...scanf(%d,&n);data=(double*)malloc(n*sizeof(double));if(data==NULL){..../*分配未完成时的处理*/}..data[i]..*(data+j)../*正常处理*/北京交通大学计算机与信息技术学院教师：林友芳92019/9/20malloc说明malloc使用注意事项：的返回值（void*）应通过类型强制转为特定指针类型后赋给指针变量。分配存储块大小应该用sizeof计算动态分配必须检查成功与否动态分配的块大小也是确定的。越界使用（尤其是越界赋值）是严重错误，可能导致程序或系统垮台北京交通大学计算机与信息技术学院教师：林友芳102019/9/206.calloc带计数和清0的存储分配函数calloc，原型：void*calloc(size_tn,size_tsize);size是元素大小，n是个数。分配一块存储，足够存n个大小为size的元素，并把元素全部清0；无法分配时返回空指针值。前面的存储分配问题也可用下面语句实现data=(double*)calloc(n,sizeof(double));主要差别malloc对所分配的区域不做任何事情，calloc对整个区域自动清0。北京交通大学计算机与信息技术学院教师：林友芳112019/9/207.空间释放函数：free为保证动态存储的有效使用，动态分配块不再用时应释放。动态存储块的释放只能通过调用free完成。Memoryleak函数原型voidfree(void*p);功能free释放p指的存储块。注意该块必须是通过动态存储分配得到的，不要对并非指向动态分配块的指针用本操作p值为空时什么也不做执行free(p)后p值未变，被指块可能已变。不允许再间接访问已释放存储块北京交通大学计算机与信息技术学院教师：林友芳122019/9/208.分配调整函数realloc函数原型void*realloc(void*p,size_tn);功能更改已有分配。p指原分配块，n是新大小要求。返回大小至少为n的存储块指针，新块与原块一致：新块小时保存原块n范围内数据；新块大时原数据存在，新增部分不初始化。分配成功后原块可能改变。无法满足时返回空指针，原块不变。常用写法(防止分配失败导致原存储块丢失)：q=(double*)realloc(p,m*sizeof(double));if(q==NULL){/*未成功，p仍指原块，特殊处理*/}else{p=q;/*令p指向新块，正常处理*/...2019/9/2013二、动态存储空间管理如果动态申请了许多同类型缓冲区，该如何管理？北京交通大学计算机与信息技术学院教师：林友芳142019/9/20方法1：指针数组（地址数组）设置一段内存空间，例如数组，用来保存存储空间的起始地址。数组中每个元素用来保存某种类型的存储空间的地址，等于每个元素都是一个指针变量。int*pnarr[10];//定义一个长度为10的整型指针数组（整型地址数组）char*psz[5];//定义一个长度为5的字符指针数组。0x0012ff7d0x0012ff80…0x0012fe12其中每个元素都用来保存某种类型的存储空间的地址北京交通大学计算机与信息技术学院教师：林友芳152019/9/20例如设一个班最多有50人，但每个班的人数不定，为了表示这50用户，可以定义如下指针数组structUserAccount*Accounts[50];完成如下功能初始化指针数组将新生成的某个班用户加入班级用户集，并存放在空位置上。将某个班指定用户号的用户删除给某个班所有女生发m元补助将新生成的某个班用户插入到指定位置i上，i后面的用户顺序往后退。北京交通大学计算机与信息技术学院教师：林友芳162019/9/20指针数组结构示例0x0012ff6dNULL0x0012ff800x0012ce000x0012fe12…08120001张帅帅110108…M0.1008120099李美美350108…F500.0008120002赵小飞360108…M20.0008120007罗小花410108…F88.200x0012ff6d0x0012ff800x0012ce000x0012fe12…长度为50空指针，可能曾被删除后续元素或空或不空Accounts北京交通大学计算机与信息技术学院教师：林友芳172019/9/20功能实现初始化指针数组voidInitAccounts(structUserAccount*Accounts[],intnLen){for(inti=0;inLen;i++)Accounts[i]=NULL;}寻找一个空位置返回，-1表示无空位置intFindEmptyPlace(structUserAccount*Accounts[],intnLen){…}//可以有不同的搜索策略NULLNULL…北京交通大学计算机与信息技术学院教师：林友芳182019/9/20功能实现（续）将新用户放在空位置上，不成功返回-1，成功返回位置号intAddNewAccountAtAnyEmptyPlace(structUserAccount*Accounts[],intnLen,structUserAccount*pUser){intnPlace;if((nPlace=FindEmptyPlace(Accounts,nLen))==-1)return-1;Accounts[nPlace]=pUser;//完成放置操作returnnPlace;//返回位置}北京交通大学计算机与信息技术学院教师：林友芳192019/9/20功能示例0x0012ff6dNULL0x0012ff800x0012ce000x0012fe12…08120001张帅帅110108…M0.1008120099李美美350108…F500.0008120002赵小飞360108…M20.0008120007罗小花410108…F88.200x0012ff6d0x0012ff800x0012ce000x0012fe12…长度为50Accounts08120100孙悟空110105…M600.100x0012ff300x0012ff30新找到的空位新结点孙悟空报到北京交通大学计算机与信息技术学院教师：林友芳202019/9/20功能实现（续）将指定用户号的用户删除，返回该用户原来所在位置intDeleteAccountByNumber(structUserAccount*Accounts[],intnLen,char*pszUserNO){inti;for(i=0;inLen;i++)//找到指定用户{if((Accounts[i]!=NULL)&&(strcmp(pszUserNO,Accounts[i]-szUserNO)==0)){free(Accounts[i]);//释放空间Accounts[i]=NULL;//将当前位置置空returni;}}return-1;}用户结构体指针数组数组长度用户号字符串比较函数北京交通大学计算机与信息技术学院教师：林友芳212019/9/20删除功能示例0x0012ff6d0x0012ff300x0012ff800x0012ce000x0012fe12…08120001张帅帅110108…M0.1008120099李美美350108…F500.0008120002赵小飞360108…M20.0008120007罗小花410108…F88.200x0012ff6d0x0012ff800x0012ce000x0012fe12…Accounts08120100孙悟空110105…M600.100x0012ff30NULL把孙悟空位置找到把孙悟空开除:DeleteAccountByNumber(Accounts,50,“08120100”)释放存储空间北京交通大学计算机与信息技术学院教师：林友芳222019/9/20功能实现（续）给指定性别的群体充值，返回充值人数intChargeByGender(structUserAccount*Accounts[],intnLen,charcGender,doubledAmount){intnCounter=0;//计数器for(inti=0;inLen;i++)//遍历所有的用户{if((NULL!=Accounts[i])&&(Accounts[i]-cGender==cGender)){Accounts[i]-dBalance+=dAmount;nCounter++;}}returnnCounter;}ChargeByGender(Accounts,50,‘F’,10.0);//妇女节发补助北京交通大学计算机与信息技术学院教师：林友芳232019/9/20方法2：链接结构采用链式数据结构一环扣一扣，通过一个元素保存的其它元素的地址找到其它元素。通过链接结构实现动态数据增加元素：在铁链的某个位置加一铁环删除元素：去掉铁链的某一铁环问题铁链中的每一铁环是一样的吗？普通的铁链是单向的还是双向的？有没有一些特殊的铁链，比如有多个分叉的？铁链可以跟铜链拴一起吗？铁链的头部可以拴在柱子上吗？北京交通大学计算机与信息技术学院教师：林友芳242019/9/20链接结构实现原理链接结构中的元素需要保存的信息与结点本身有关的信息找到其它元素所需要的信息这些信息可以组织成结