C语言教学课件：第十七部分 动态存储空间管理与链表

1第十七部分

动态存储空间管理与链表一、程序与存储空间程序运行时需要的存储空间1.需要空间用来保存待执行的程序代码2.需要空间用来保存程序运行中用到的数据31.程序获取存储空间的途径途径1—在程序代码中定义某种类型的变量基本数据类型变量指针变量数组变量结构体变量…途径2—显式的内存空间申请在标准C中用malloc等函数申请一块存储空间在C++、JAVA或PASACAL中用new等命令申请存储空间或新建对象谁帮程序申请的存储空间?42026/11/22.C通过定义变量获取存储空间外部变量，静态内部变量编译器会生成申请内存空间的代码，程序一启动就分配固定的存储空间给这些变量使用，在程序执行期间，不再给这些变量换存储空间。自动型内部变量执行到定义处才将空间分配给自动型内部变量使用，函数结束后这些变量将不再存在（即原分配给变量的空间不再归这些自动型变量使用)。谁在分配和回收存储空间的使用权？编译后隐含在可执行程序中的申请和释放代码变量存在期开始时，隐含了将变量对应的存储空间分配给变量使用的动作变量存在期结束时，隐含了将变量对应的存储空间收回的动作52026/11/23.显式申请存储空间明确地向系统发出申请空间的指令malloc,…new明确地向系统发出释放指令freedelete问题回顾新申请的空间应该如何管理?解决方案把新申请得到的存储空间保存在可以保存地址的存储空间中6二、数据缓冲区—BufferBuffering&BufferArrayvsBufferPointervsBuffer72026/11/21.数据缓冲与缓冲区DataBufferingandBuffer什么叫缓冲?使用存储空间临时保存需要被处理的数据，这样的存储空间即称为缓冲区。为什么要缓冲?数据源数据流数据处理器数据的到达速度与数据加工速度不对等需要一次处理一批数据而不是单个数据前面收到数据要用来检验后来的数据不同数据包的到达速度不一致数据作为一个整体…82026/11/22.缓冲区每一段存储空间一般都是用于保存待处理的数据，因此只要是存储空间，常常被称为Buffer，即缓冲区。例如charszBuffer[1000];//定义一段长度为1000的字符缓冲区char*psz;//定义一个字符缓冲区指针变量intnBuffer[100];//定义一段长度为100（400个字节)的整型缓冲区int*pInt;//定义一个整型缓冲区指针92026/11/23.缓冲区与数组每个数组就是一个缓冲区,其缓冲区大小为数组长度*元素占用空间大小如果需要,每个缓冲区也可以看成是一个数组,可以设置一个指针变量保存缓冲区的首地址,而后通过指针变量按数组操作方式操作缓冲区。但并不是每个缓冲区都会被看成数组,有些缓冲区需要存放多种不同类型的数据。有些缓冲区在不同时候能起不同的作用,用于存放不同类别的数据,如Windows系统的剪粘板QQ的数据发送与接收缓冲区102026/11/24.缓冲区与动态存储管理许多缓冲区都是临时动态地从存储堆里分配得到,因此需要用到动态存储分配与释放程序例如,临时需要一块长度为n的double型缓冲区,用来存放n个双精度浮点数,则可以采用如下步骤完成显式地提交一个内存分配申请,分配成功后会得到申请得到的内存空间的首地址addr将addr存放在一个double型指针变量p中而后就可以用p来访问这个缓冲区常用分配和释放函数void*malloc(size_tn);//申请一块长度不小于n的缓冲型,返回缓冲区首地址voidfree(void*p);//释放p所指向缓冲区需要包含stdlib.h112026/11/2示例intn;double*pDouble;...scanf("%d",&n);pDouble=(double*)malloc(n*sizeof(double));if(pDouble==NULL){..../*分配未完成时的处理*/}..pDouble[i]..*(pDouble+j)../*正常处理*/…free(pDouble);//用完后释放申请存储空间122026/11/25.程序的模块间数据传递方法回顾方法1—针对批量顺序数据将缓冲区首地址传函数—设置指针参数将缓冲区长度告诉函数方法2—针对批量非顺序存储的数据指针数组,链表,…将数据的源头的地址传给函数…2026/11/2三、函数数据接口机制函数如何通过参数来接收及处理来自外部的批量数据?142026/11/21.函数数据接口与处理机制函数处理的数据的规模分成两种情况数目不多的零散数据批量数量零散数据用前述普通的函数参数即可实现向函数的数据传递批量数据分成两大类一批在内存中连续存放的数据一批在内存中非连续存放的数据152026/11/22.函数批量数据处理方法函数要进行批量数据处理，必须要解决的问题能通过一定途径找个每一个数据元素，并对数据元素进行逐个处理找到每一个元素并处理的过程一般称为遍历。问题在处理一批连续存放的数据时，函数需要知道的关于数据的信息有哪些?在处理一批非连续存放的数据时，函数需要知道的关于数据的信息有哪些?162026/11/23.批量连续存放数据接口机制通过简单分析可以知道，对于批量顺序存放的数据，函数若需要访问找到每一个元素，至少应知道如下信息需要处理的数据在哪儿放着?缓冲区首地址数据是什么类型的?数据类型需要处理的数据有多少个?缓冲区中的数据项个数…首地址数据类型数据项个数可用指针做参数172026/11/2批量连续存放数据的参数传递机制一般机制设置参数,让函数能接收到批量数据的首地址让函数能知道数据的类型让函数能接收到批量数据的长度C函数的解决办法设置一个相应类型的指针参数,用于接收批量数据缓冲区的首地址。设置一个整型变量用于接收缓冲区的长度。此类函数的常见样式return_typeFuncName(basetype*pBuffer,intnLen,…);…表示其它参数,return_type表示返回值类型,basetype是缓冲区中每一个元素的类型。

182026/11/2第4部分中的实例结构体structUserAccount{charszUserNO[15];charszName[20];charszID[19];charcGender;doubledBalance;}User,Users[100],*pUser;structUserAccount{charszUserNO[15]; //用户IDcharszName[20];//姓名

charszID[19]; //身份证号

charcGender; //性别

doubledBalance; //卡余额};structUserAccountUser,Users[100],*pUser;User为一个普通的结构体变量;Users是一个长度为100的结构体数组;pUser是一个指针变量，用于存放该类型结构体变量的所占存储空间的地址;192026/11/2结构体数组操作举例给用户充值,并返回充值后的余额。doubleCharge(structUserAccount*pUserAccount,doubledAmount){returnpUserAccount->dBalance+=dAmount;//充值返回}给全班学生发一定额度补助voidGroupCharge(structUserAccountAccounts[],intnCount,doubledAmount){ if(NULL==Accounts)//判断所给用户指针是否合法return;for(inti=0;i<nCount;i++)Accounts[i].dBalance+=dAmount;//Charge(&Accounts[i],dAmount);}指针的数组用法结构体的分量操作符结构体指针的分量操作符实质是指针参数202026/11/24.批量非连续存放数据接口机制批量非连续存放的数据是指一批彼此具有一定的关系的数据，但是出于各种原因，各个数据的存放位置并不一定是紧挨着的。位置不连续导致程序无法根据首地址和单元大小来自动推断出下一个元素的地址。因此，对于函数而言，要处理这些数据，必须具有途径能把各个数据的存储位置找出来。能把存储位置找出来的前提各个数据的存储位置被记录在某个地方而且数据的存储位置可以通过一些办法找到的。关键的问题数据存储位置在什么地方存着?与一些藏宝游戏类似212026/11/2数据存储地址的保管方案方法1在生成数据的时候，把各个数据的地址放在一个连续缓冲区中记下来，然后把记地址用的连续缓冲区的传给函数。方法2利用一些特殊的数据表示机制，通过一个数据能知道另外一个或多个跟它有关系的数据的存储地址。这样就需要知道第一个（或头几个)数据的存储位置，然后再顺藤摸瓜找到别的数据。

222026/11/2批量非连续存放数据参数机制针对前述方案1把记地址用的连续缓冲区和缓冲区长度的传给函数针对前述方案2把数据集的源头（第一个或头几个)的地址传给函数。具体接口方式取决于数据关系的表示方法。2026/11/223四、动态存储空间管理与链表隐式和显式242026/11/21.引例要处理学生成绩，需要用数组存放。但编程时并不知道运行时需要处理多少学生成绩，每次处理的成绩项数也可能不同。intn;...scanf("%d",&n);doublescores[n];/*不行！*/.../*读入数据，然后处理*/不能用变量说明scores大小（必须静态确定)。

252026/11/22.问题的本质及解决方案问题的本质程序运行中需要使用存储，有时程序对存储的需求量在写程序时不能确定。可能解决方案1)分析问题，定义适当大小的数组。若分析正确，一般都能处理。但数据很多时程序就不能用。2)定义尽可能大的数组以满足任何需要。浪费大量存储资源。如有多个这种数组就更难办。系统可能无法容纳几个大数组，但实际上它们并不同时需要很大空间。解决的办法是“动态存储分配”。在程序运行中做存储分配工作。

262026/11/23.动态存储分配动态存储分配根据运行中的需要分配存储,取得存储块使用,称为动态存储分配。在运行中根据需要动态进行。动态存储块具有起始地址,地址可以存储在指针里,因此可以借助于指针保存存储空间地址。用指针指向存储块,间接使用被指存储。访问动态分配存储是指针的最重要用途。

272026/11/24.动态存储释放及存储堆动态释放不用的动态存储块应交还系统，动态申请的内存空间必须由程序代码以显式的方式主动释放。动态分配、释放由动态存储管理系统完成，这是程序运行系统的子系统，管理着称作堆（英文heap)的存储区。大部分常规语言都有这种机制。

282026/11/25.C语言的动态存储管理机制用标准库函数实现stdlib.hmalloc.h存储分配函数malloc()，原型:void*malloc(size_tn);/*size_t是某整型*/功能分配一块不小于n的存储，返回其地址。无法满足时返回空指针值。292026/11/2例intn;double*data;...scanf("%d",&n);data=(double*)malloc(n*sizeof(double));if(data==NULL){..../*分配未完成时的处理*/}..data[i]..*(data+j)../*正常处理*/302026/11/2malloc说明malloc使用注意事项：的返回值（void*)应通过类型强制转为特定指针类型后赋给指针变量。分配存储块大小应该用sizeof计算动态分配必须检查成功与否动态分配的块大小也是确定的。越界使用（尤其是越界赋值)是严重错误，可能导致程序或系统垮台312026/11/26.calloc带计数和清0的存储分配函数calloc，原型：void*calloc(size_tn,size_tsize);size是元素大小，n是个数。分配一块存储，足够存n个大小为size的元素，并把元素全部清0;无法分配时返回空指针值。前面的存储分配问题也可用下面语句实现data=(double*)calloc(n,sizeof(double));主要差别malloc对所分配的区域不做任何事情，calloc对整个区域自动清0。

322026/11/27.空间释放函数:free为保证动态存储的有效使用,动态分配块不再用时应释放。动态存储块的释放只能通过调用free完成。Memoryleak函数原型voidfree(void*p);功能free释放p指的存储块。注意该块必须是通过动态存储分配得到的,不要对并非指向动态分配块的指针用本操作p值为空时什么也不做执行free(p)后p值未变,被指块可能已变。不允许再间接访问已释放存储块332026/11/28.分配调整函数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指向新块，正常处理*/...2026/11/234五、动态存储空间管理如果动态申请了许多同类型缓冲区，该如何管理?352026/11/2方法1：指针数组（地址数组)设置一段内存空间，例如数组，用来保存存储空间的起始地址。数组中每个元素用来保存某种类型的存储空间的地址，等于每个元素都是一个指针变量。int*pnarr[10];//定义一个长度为10的整型指针数组（整型地址数组)char*psz[5];//定义一个长度为5的字符指针数组。

0x0012ff7d0x0012ff80…0x0012fe12其中每个元素都用来保存某种类型的存储空间的地址362026/11/2例如设一个班最多有50人,但每个班的人数不定,为了表示这50用户,可以定义如下指针数组structUserAccount*Accounts[50];完成如下功能初始化指针数组将新生成的某个班用户加入班级用户集,并存放在空位置上。将某个班指定用户号的用户删除给某个班所有女生发m元补助将新生成的某个班用户插入到指定位置i上,i后面的用户顺序往后退。

372026/11/2指针数组结构示例0x0012ff6dNULL0x0012ff800x0012ce000x0012fe12…08120001

张帅帅110108…M0.1008120099

李美美350108…F500.0008120002

赵小飞360108…M20.0008120007

罗小花410108…F88.200x0012ff6d0x0012ff800x0012ce000x0012fe12…长度为50空指针,可能曾被删除后续元素或空或不空Accounts382026/11/2功能实现初始化指针数组voidInitAccounts(structUserAccount*Accounts[],intnLen){for(inti=0;i<nLen;i++)Accounts[i]=NULL;}寻找一个空位置返回,-1表示无空位置intFindEmptyPlace(structUserAccount*Accounts[],intnLen){…}//可以有不同的搜索策略NULLNULL…392026/11/2功能实现（续)将新用户放在空位置上,不成功返回-1,成功返回位置号intAddNewAccountAtAnyEmptyPlace(structUserAccount*Accounts[],intnLen,structUserAccount*pUser){intnPlace; if((nPlace=FindEmptyPlace(Accounts,nLen))==-1)return-1;Accounts[nPlace]=pUser;//完成放置操作returnnPlace;//返回位置}用户结构体指针数组数组长度新用户结构指针402026/11/2功能示例0x0012ff6dNULL0x0012ff800x0012ce000x0012fe12…08120001

张帅帅110108…M0.1008120099

李美美350108…F500.0008120002

赵小飞360108…M20.0008120007

罗小花410108…F88.200x0012ff6d0x0012ff800x0012ce000x0012fe12…长度为50Accounts08120100

孙悟空110105…M600.100x0012ff300x0012ff30新找到的空位新结点孙悟空报到412026/11/2功能实现（续)将指定用户号的用户删除,返回该用户原来所在位置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;}用户结构体指针数组数组长度用户号字符串比较函数422026/11/2删除功能示例0x0012ff6d0x0012ff300x0012ff800x0012ce000x0012fe12…08120001

张帅帅110108…M0.1008120099

李美美350108…F500.0008120002

赵小飞360108…M20.0008120007

罗小花410108…F88.200x0012ff6d0x0012ff800x0012ce000x0012fe12…Accounts08120100

孙悟空110105…M600.100x0012ff30NULL把孙悟空位置找到把孙悟空开除:DeleteAccountByNumber(Accounts,50,"08120100”)释放存储空间432026/11/2功能实现（续)给指定性别的群体充值,返回充值人数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);//妇女节发补助442026/11/2方法2:链接结构采用链式数据结构一环扣一环，通过一个元素保存的其它元素的地址找到其它元素。通过链接结构实现动态数据增加元素：在铁链的某个位置加一铁环删除元素：去掉铁链的某一铁环问题铁链中的每一铁环是一样的吗?普通的铁链是单向的还是双向的?有没有一些特殊的铁链，比如有多个分叉的?铁链可以跟铜链拴一起吗?铁链的头部可以拴在柱子上吗?452026/11/2链接结构实现原理链接结构中的元素需要保存的信息与结点本身有关的信息找到其它元素所需要的信息这些信息可以组织成结构问题：如何找到其它元素?保存其它元素在内存中的地址在结构中设置指针分量，用来保存其它元素的地址的分量指针分量问题：指针的类型?需要指向结构类型的指针类型如果需要指向的元素与本元素的类型相同的话，则需要定义自引用的结构类型。

462026/11/2链接结构一个结构元素可以通过指针引用同类或不同类的结构元素,多个结构元素通过指针建立联系。指向结构的指针称为链接,形成的复杂数据结构称为链接结构最简单的链接结构线性链接形成的表,链接表。每个自引用结构有一个链接指针分量。

472026/11/2最简单的链接结构:单向链表单向链接表就像链条，自引用结构是链表中的一个链节，称为链表结点，结点间由指针连接形成整个结构。所有结点（结构)由动态分配创建。从指向表首结点的指针出发，沿链接可顺序访问表中各结点。该指针代表整个表。通常把最后结点的指针置空表示结束。

482026/11/2更复杂的引用链接结构492026/11/2单向链表结构示例structUserAccount{charUserNO[15];charName[20];charID[19];charGender;doubleBalance;

structUserAccount

*pNextUser;};用来保存下一个结点的地址此处改成如下形式是否可行，为什么?structUserAccountNextUser;502026/11/2普通单向链表示意图08120001

张帅帅110108…M0.1008120002

赵小飞360108…M20.0008120007

罗小花410108…F88.2008120099

李美美350108…F500.00NULL…HeadTail512026/11/2例,需求设有某系统的用户信息结构体,其中用户ID长度为10用户姓名长度不超过10需要处理的用户数据不定,假设某程序需要以链表方式处理用户的数据522026/11/2普通单向链表示意DataDataDataDataNULL…HeadTail532026/11/2链表结点结构声明方法1:structUserInfoNode{ charszID[11]; //ID charszName[11]; //姓名structUserInfoNode*pNextUser; //下个用户指针};方法2:typedefstructUserInfoNodeUSERNODE,*USERPOINTER;structUserInfoNode{ charszID[11]; //ID charszName[11]; //姓名USERPOINTERpNextUser; //下个用户指针};542026/11/2更好的方法:基本信息单独说明//用户基本信息结构声明structUserInfo{ charszID[11]; //ID,11个字符 charszName[11]; //姓名,11个字符};或typedefstruct{ charszID[11]; //ID,11个字符 charszName[11]; //姓名,11个字符}USERINFO;552026/11/2更常见合理的声明方法方法3:structUserLinkNode{structUserInfoData; //数据structUserLinkNode*pNextUser;//};structUserInfoUserInfoArr[100];或typedefstruct{USERINFOData; //数据结点structUserLinkNode*pNextUser;//}USERLINKNODE;structUserInfo{ charszID[11];

charszName[11];};typedefstruct{ charszID[11];

charszName[11];}USERINFO;562026/11/2增加一个链表描述信息结点NumberHeadTailDataDataDataDataNULL…LinkInfoNode关于链表整体描述信息结点572026/11/2描述结点结构说明示例structUserLink{ structUserLinkNode*pHead;//头指针

structUserLinkNode*pTail;//尾指针

intnNumber; //链表中的结点计数};或typedefstruct{ USERLINKNODE*pHead;//头指针

USERLINKNODE*pTail;//尾指针

intnNumber; //链表中的结点计数}USERLINK;582026/11/2可以增加一个不用的头结点NumberHeadTailDataDataDataNULL…LinkInfoNode目的在于写程序方便,简化一些链表操作,数据结构课程中会有进一步的阐述不用的头结点592026/11/2关于后面的操作的假定链表为单向链表没有设置空的头结点设置有信息描述结点,记录如下信息头结点尾结点链表中结点个数602026/11/2在链表中增加一个节点有几种增加方式将新结点作为最后一个元素增加到链表的尾部,将新结点作为第一个元素增加到链表的头部将新结点按照某种次序要求插入到指定位置612026/11/2加到尾部如果链表为空,则需要做一些初始化工作,将新的结点当成头结点和尾结点如果链表不为空,则将该结点作为尾结点的下一个结点,修改尾结点指针。如果没有记录尾结点指针,则需要从头结点开始找到最后一个结点。

pHeadpTailDataDataNULL……pNewNode

NULL

622026/11/2示例代码,加到尾部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;}632026/11/2加到头部如果链表为空,则需要做一些初始化工作,将新的结点当成头结点和尾结点如果链表不为空,需要将新结点的下一个结点置为原来的头结点,并把新结点作为头结点pHeadpTailDataDataNULL……NULLpNewNode

642026/11/2示例代码,加到头部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;}652026/11/2在链表中插入一个新结点基本操作q->pNext=p->pNext;p->pNext=q;其它用于保持链表指针完整性的操作。^^功能示意ppqqrr插入前插入后662026/11/2去除链表中的某个结点基本操作p->pNext=q->pNext;外围附加操作，用于保证链表的各种指针的完整性，如头指针，尾指针等。如:如果删除的是最后一个结点的话，需要修改尾指针功能示意pqrprq672026/11/2遍历链表常见功能遍历链表逐个访问所有结点,进行相应的处理,如将所有用户的某项指标求和,输出所有用户的信息查找某个或某些符合给定条件的结点,进行相应处理…682026/11/2示例代码:输出所有元素intShowData(structUserLink*pUsers){ structUserLinkNode*pNode; if(pUsers->nNumber<=0) return-1; for( pNode=pUsers->pHead; //从第一个元素开始 pNode!=NULL; //判断当前结点是否为空 pNode=pNode->pNext //准备处理下一个结点 ) {//对每个结点出输出信息 printf("%11s\t%11s\t\n", pNode->Data.szID, pNode->Data.szName, } return0;}692026/11/2参数改成头结点intShowData(structUserLinkNode*pHead)//给出头结点{ structUserLinkNode*pNode; if(pHead==NULL) return-1; for( pNode=pHead; //从第一个元素开始 pNode!=NULL; //判断当前结点是否为空 pNode=pNode->pNext //准备处理下一个结点 ) {//对每个结点出输出信息 printf("%11s\t%11s\t\n", pNode->Data.szID, pNode->Data.szName, } return0;}70词频统计示例词频统计统计正文文件里各个字或单词出现的次数。统计前不知道有多少不同的词，无法在编程时准备好统计中使用的完整数据结构。可能方案动态分配计数器数组，必要时调整大小（用realloc)。问题新词逐个遇到，反复调整分配效率比较低，而且需要使用很大的块，不够灵活。如果词很多，能否找到足够大的存储块也是问题。

71词频统计实现#include<stdio.h>#include<ctype.h>#include<string.h>#include<stdlib.h>enum{MAXLEN=20};typedefstructnodeNODE,*LINK;structnode//定义链接结构{ charword[MAXLEN]; intcount; LINKnext;};intgetword(intlimit,charw[]);LINKaddwordL(LINKlist,charw[]);LINKaddwordR(LINK