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

第十七章动态存储空间管理与链表9/22/20241一、动态存储分配及常见函数说明隐式和显式9/22/202421.引例要处理学生成绩，需要用数组存放。但编程时并不知道运行时需要处理多少学生成绩，每次处理的成绩项数也可能不同。intn;...scanf("%d",&n);doublescores[n];/*不行！*/.../*读入数据，然后处理*/不能用变量说明scores大小（必须静态确定）。9/22/20243教师：林友芳2.问题的本质及解决方案问题的本质程序运行中需要使用存储，有时程序对存储的需求量在写程序时不能确定。可能解决方案1）分析问题，定义适当大小的数组。若分析正确，一般都能处理。但数据很多时程序就不能用。2）定义尽可能大的数组以满足任何需要。浪费大量存储资源。如有多个这种数组就更难办。系统可能无法容纳几个大数组，但实际上它们并不同时需要很大空间。解决的办法是“动态存储分配”。在程序运行中做存储分配工作。9/22/20244教师：林友芳3.动态存储分配动态存储分配根据运行中的需要分配存储，取得存储块使用，称为动态存储分配。在运行中根据需要动态进行。动态存储块具有起始地址，地址可以存储在指针里，因此可以借助于指针保存存储空间地址。用指针指向存储块，间接使用被指存储。访问动态分配存储是指针的最重要用途。9/22/20245教师：林友芳4.动态存储释放及存储堆动态释放不用的动态存储块应交还系统，动态申请的内存空间必须由程序代码以显式的方式主动释放。动态分配、释放由动态存储管理系统完成，这是程序运行系统的子系统，管理着称作堆（英文heap）的存储区。大部分常规语言都有这种机制。9/22/20246教师：林友芳5.C语言的动态存储管理机制用标准库函数实现stdlib.hmalloc.h存储分配函数malloc()，原型：void*malloc(size_tn);/*size_t是某整型*/功能分配一块不小于n的存储，返回其地址。无法满足时返回空指针值。9/22/20247教师：林友芳例intn;double*data;...scanf("%d",&n);data=(double*)malloc(n*sizeof(double));if(data==NULL){..../*分配未完成时的处理*/}..data[i]..*(data+j)../*正常处理*/9/22/20248教师：林友芳malloc说明malloc使用注意事项：的返回值（void*）应通过类型强制转为特定指针类型后赋给指针变量。分配存储块大小应该用sizeof计算动态分配必须检查成功与否动态分配的块大小也是确定的。越界使用（尤其是越界赋值）是严重错误，可能导致程序或系统垮台9/22/20249教师：林友芳6.calloc带计数和清0的存储分配函数calloc，原型：void*calloc(size_tn,size_tsize);size是元素大小，n是个数。分配一块存储，足够存n个大小为size的元素，并把元素全部清0；无法分配时返回空指针值。前面的存储分配问题也可用下面语句实现data=(double*)calloc(n,sizeof(double));主要差别malloc对所分配的区域不做任何事情，calloc对整个区域自动清0。9/22/202410教师：林友芳7.空间释放函数：free为保证动态存储的有效使用，动态分配块不再用时应释放。动态存储块的释放只能通过调用free完成。Memoryleak函数原型voidfree(void*p);功能free释放p指的存储块。注意该块必须是通过动态存储分配得到的，不要对并非指向动态分配块的指针用本操作p值为空时什么也不做执行free(p)后p值未变，被指块可能已变。不允许再间接访问已释放存储块9/22/202411教师：林友芳8.分配调整函数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指向新块，正常处理*/...9/22/202412教师：林友芳二、动态存储空间管理如果动态申请了许多同类型缓冲区，该如何管理？9/22/202413方法1：指针数组（地址数组）设置一段内存空间，例如数组，用来保存存储空间的起始地址。数组中每个元素用来保存某种类型的存储空间的地址，等于每个元素都是一个指针变量。int*pnarr[10];//定义一个长度为10的整型指针数组（整型地址数组）char*psz[5];//定义一个长度为5的字符指针数组。0x0012ff7d0x0012ff80…0x0012fe12其中每个元素都用来保存某种类型的存储空间的地址9/22/202414教师：林友芳例如设一个班最多有50人，但每个班的人数不定，为了表示这50用户，可以定义如下指针数组structUserAccount*Accounts[50];完成如下功能初始化指针数组将新生成的某个班用户加入班级用户集，并存放在空位置上。将某个班指定用户号的用户删除给某个班所有女生发m元补助将新生成的某个班用户插入到指定位置i上，i后面的用户顺序往后退。9/22/202415教师：林友芳指针数组结构示例0x0012ff6dNULL0x0012ff800x0012ce000x0012fe12…08120001张帅帅110108…M0.1008120099李美美350108…F500.0008120002赵小飞360108…M20.0008120007罗小花410108…F88.200x0012ff6d0x0012ff800x0012ce000x0012fe12…长度为50空指针，可能曾被删除后续元素或空或不空Accounts9/22/202416教师：林友芳功能实现初始化指针数组voidInitAccounts(structUserAccount*Accounts[],intnLen){for(inti=0;i<nLen;i++)

Accounts[i]=NULL;}寻找一个空位置返回，-1表示无空位置intFindEmptyPlace(structUserAccount*Accounts[],intnLen){…}//可以有不同的搜索策略NULLNULL…9/22/202417教师：林友芳功能实现（续）将新用户放在空位置上，不成功返回-1，成功返回位置号intAddNewAccountAtAnyEmptyPlace(structUserAccount*Accounts[],intnLen,structUserAccount*pUser){intnPlace; if((nPlace=FindEmptyPlace(Accounts,nLen))==-1)return-1;

Accounts[nPlace]=pUser;//完成放置操作returnnPlace;//返回位置}9/22/202418教师：林友芳功能示例0x0012ff6dNULL0x0012ff800x0012ce000x0012fe12…08120001张帅帅110108…M0.1008120099李美美350108…F500.0008120002赵小飞360108…M20.0008120007罗小花410108…F88.200x0012ff6d0x0012ff800x0012ce000x0012fe12…长度为50Accounts08120100孙悟空110105…M600.100x0012ff300x0012ff30新找到的空位新结点孙悟空报到9/22/202419教师：林友芳功能实现（续）将指定用户号的用户删除，返回该用户原来所在位置intDeleteAccountByNumber(structUserAccount*Accounts[],intnLen,char*pszUserNO){inti;for(i=0;i<nLen;i++)//找到指定用户{if((Accounts[i]!=NULL)&&(strcmp(pszUserNO,Accounts[i]->szUserNO)==0)){

free(Accounts[i]);//释放空间

Accounts[i]=NULL;//将当前位置置空 returni;}}return-1;}用户结构体指针数组数组长度用户号字符串比较函数9/22/202420教师：林友芳删除功能示例0x0012ff6d0x0012ff300x0012ff800x0012ce000x0012fe12…08120001张帅帅110108…M0.1008120099李美美350108…F500.0008120002赵小飞360108…M20.0008120007罗小花410108…F88.200x0012ff6d0x0012ff800x0012ce000x0012fe12…Accounts08120100孙悟空110105…M600.100x0012ff30NULL把孙悟空位置找到把孙悟空开除:DeleteAccountByNumber(Accounts,50,“08120100”)释放存储空间9/22/202421教师：林友芳功能实现（续）给指定性别的群体充值，返回充值人数intChargeByGender(structUserAccount*Accounts[],intnLen,charcGender,doubledAmount){intnCounter=0;//计数器for(inti=0;i<nLen;i++)//遍历所有的用户{

if((NULL!=Accounts[i])&&(Accounts[i]->cGender==cGender)){Accounts[i]->dBalance+=dAmount;nCounter++;}}returnnCounter;}ChargeByGender(Accounts,50,‘F’,10.0);//妇女节发补助9/22/202422教师：林友芳方法2：链接结构采用链式数据结构一环扣一扣，通过一个元素保存的其它元素的地址找到其它元素。通过链接结构实现动态数据增加元素：在铁链的某个位置加一铁环删除元素：去掉铁链的某一铁环问题铁链中的每一铁环是一样的吗？普通的铁链是单向的还是双向的？有没有一些特殊的铁链，比如有多个分叉的？铁链可以跟铜链拴一起吗？铁链的头部可以拴在柱子上吗？9/22/202423教师：林友芳链接结构实现原理链接结构中的元素需要保存的信息与结点本身有关的信息找到其它元素所需要的信息这些信息可以组织成结构问题：如何找到其它元素？保存其它元素在内存中的地址在结构中设置指针分量，用来保存其它元素的地址的分量指针分量问题：指针的类型？需要指向元素的结构类型的指针类型如果需要指向的元素与本元素的类型相同的话，则需要定义自引用的结构类型。9/22/202424教师：林友芳链接结构一个结构元素可以通过指针引用同类或不同类的结构元素，多个结构元素通过指针建立联系。指向结构的指针称为链接，形成的复杂数据结构称为链接结构最简单的链接结构线性链接形成的表，链接表。每个自引用结构有一个链接指针分量。9/22/202425教师：林友芳最简单的链接结构：单向链表单向链接表就像链条，自引用结构是链表中的一个链节，称为链表结点，结点间由指针连接形成整个结构。所有结点（结构）由动态分配创建。从指向表首结点的指针出发，沿链接可顺序访问表中各结点。该指针代表整个表。通常把最后结点的指针置空表示结束。9/22/202426教师：林友芳更复杂的引用链接结构9/22/202427教师：林友芳单向链表结构示例structUserAccount{charUserNO[15];charName[20];charID[19];charGender;doubleBalance;

structUserAccount

*pNextUser;};用来保存下一个结点的地址此处改成如下形式是否可行，为什么？structUserAccount

NextUser;9/22/202428教师：林友芳普通单向链表示意图08120001张帅帅110108…M0.1008120002赵小飞360108…M20.0008120007罗小花410108…F88.2008120099李美美350108…F500.00NULL…HeadTail9/22/202429教师：林友芳三、链表9/22/2024301.需求设有某系统的用户信息结构体，其中用户ID长度为10用户姓名长度不超过10需要处理的用户数据不定，假设某程序需要以链表方式处理用户的数据9/22/202431教师：林友芳普通单向链表示意DataDataDataDataNULL…HeadTail9/22/202432教师：林友芳链表结点结构声明方法1:structUserInfoNode{ charszID[11]; //ID charszName[11]; //姓名structUserInfoNode*pNextUser; //下个用户指针};方法2：typedefstructUserInfoNodeUSERNODE,*USERPOINTER;structUserInfoNode{ charszID[11]; //ID charszName[11]; //姓名USERPOINTER*pNextUser; //下个用户指针};9/22/202433教师：林友芳更好的方法：基本信息单独说明//用户基本信息结构声明structUserInfo{ charszID[11]; //ID，11个字符 charszName[11]; //姓名，11个字符};或typedefstruct{ charszID[11]; //ID，11个字符 charszName[11]; //姓名，11个字符}USERINFO;9/22/202434教师：林友芳更常见合理的声明方法方法3：structUserLinkNode{structUserInfoData; //数据structUserLinkNode*pNextUser;//};structUserInfoUserInfoArr[100];或typedefstruct{USERINFOData; //数据结点structUserLinkNode*pNextUser;//}USERLINKNODE;9/22/202435教师：林友芳增加一个链表描述信息结点NumberHeadTailDataDataDataDataNULL…LinkInfoNode关于链表整体描述信息结点9/22/202436教师：林友芳描述结点结构说明示例structUserLink{ structUserLinkNode*pHead;//头指针 structUserLinkNode*pTail;//尾指针 intnNumber; //链表中的结点计数};或typedefstruct{ USERLINKNODE*pHead;//头指针 USERLINKNODE*pTail;//尾指针 intnNumber; //链表中的结点计数}USERLINK;9/22/202437教师：林友芳可以增加一个不用的头结点NumberHeadTailDataDataDataNULL…LinkInfoNode目的在于写程序方便，简化一些链表操作，数据结构课程中会有进一步的阐述不用的头结点9/22/202438教师：林友芳关于后面的操作的假定链表为单向链表没有设置空的头结点设置有信息描述结点，记录如下信息头结点尾结点链表中结点个数9/22/202439教师：林友芳在链表中增加一个节点有几种增加方式将新结点作为最后一个元素增加到链表的尾部，将新结点作为第一个元素增加到链表的头部将新结点按照某种次序要求插入到指定位置9/22/202440教师：林友芳加到尾部如果链表为空，则需要做一些初始化工作，将新的结点当成头结点和尾结点如果链表不为空，则将该结点作为尾结点的下一个结点，修改尾结点指针。如果没有记录尾结点指针，则需要从头结点开始找到最后一个结点。pHeadpTailDataDataNULL……pNewNode

NULL

9/22/202441教师：林友芳示例代码，加到尾部intAddUserToTail(structUserLink*pUsers,//链表描述信息指针 structUserLinkNode*pNewUser//新结点指针){ if(pUsers==NULL||pNewUser==NULL)return-1; if(pUsers->nNumber<=0){//如果还没有元素 pUsers->pHead=pNewUser; pUsers->pTail=pUsers->pHead;//头尾指针指向同一个结点 } else{//把结点信息附到链表尾部 pUsers->pTail->pNext=pNewUser;//加到尾到 pUsers->pTail=pNewUser; //修改尾结点指针 } pUsers->pTail->pNext=NULL;//最后一个结点的后继置空 pUsers->nNumber++;//计数加1 return0;}9/22/202442教师：林友芳加到头部如果链表为空，则需要做一些初始化工作，将新的结点当成头结点和尾结点如果链表不为空，需要将新结点的下一个结点置为原来的头结点，并把新结点作为头结点pHeadpTailDataDataNULL……NULLpNewNode

9/22/202443教师：林友芳示例代码，加到头部intAddUserToHead(structUserLink*pUsers,//链表描述信息指针 structUserLinkNode*pNewUser//新结点指针){ if(pUsers==NULL||pNewUser==NULL)return-1; if(pUsers->nNumber<=0){//如果还没有元素 pUsers->pHead=pNewUser; pUsers->pTail=pUsers->pHead;//头尾指针指向同一个结点 pNewUser->pNext=NULL; } else{//把结点信息附到链表头部 pUsers->pNewUser->pNext=pUsers->pHead;//加到头部 pUsers->pHead=pNewUser; //修改头结点指针 } pUsers->nNumber++;//计数加1 return0;}9/22/202444教师：林友芳在链表中插入一个新结点基本操作q->pNext=p->pNext;p->pNext=q;其它用于保持链表指针完整性的操作。^^功能示意ppqqrr插入前插入后9/22/202445教师：林友芳去除链表中的某个结点基本操作p->pNext=q->pNext;外围附加操作，用于保证链