【文档说明】(C语言课件)第17部分-动态存储空间管理与链表.ppt，共(52)页，1.593 MB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-44446.html

以下为本文档部分文字说明：

2022/11/241第十七章动态存储空间管理与链表2022/11/242一、动态存储分配及常见函数说明隐式和显式北京交通大学计算机与信息技术学院教师：林友芳32022/11/241.引例要处理学生成绩，需要用数

组存放。但编程时并不知道运行时需要处理多少学生成绩，每次处理的成绩项数也可能不同。intn;...scanf("%d",&n);doublescores[n];/*不行！*/.../*读入数据，然后处理*/

不能用变量说明scores大小（必须静态确定）。北京交通大学计算机与信息技术学院教师：林友芳42022/11/242.问题的本质及解决方案问题的本质程序运行中需要使用存储，有时程序对存储的需求量在写程序时不能确定。可能解决方案1）分析问题，定义适当大小的数组。若分析正确，一般

都能处理。但数据很多时程序就不能用。2）定义尽可能大的数组以满足任何需要。浪费大量存储资源。如有多个这种数组就更难办。系统可能无法容纳几个大数组，但实际上它们并不同时需要很大空间。解决的办法是“动态存储分配”。在程序运行中做存储分配工作。北京交通大学计算机与信息技术学院教师：林友芳52022/1

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

是指针的最重要用途。北京交通大学计算机与信息技术学院教师：林友芳62022/11/244.动态存储释放及存储堆动态释放不用的动态存储块应交还系统，动态申请的内存空间必须由程序代码以显式的方式主动释放。动态分配、

释放由动态存储管理系统完成，这是程序运行系统的子系统，管理着称作堆（英文heap）的存储区。大部分常规语言都有这种机制。北京交通大学计算机与信息技术学院教师：林友芳72022/11/245.C语言的动态存储管理机制用标准库函数实现stdlib.hmalloc.h存储分配函数malloc

()，原型：void*malloc(size_tn);/*size_t是某整型*/功能分配一块不小于n的存储，返回其地址。无法满足时返回空指针值。北京交通大学计算机与信息技术学院教师：林友芳82022/11/2

4例intn;double*data;...scanf("%d",&n);data=(double*)malloc(n*sizeof(double));if(data==NULL){..../*分配未完成时的处

理*/}..data[i]..*(data+j)../*正常处理*/北京交通大学计算机与信息技术学院教师：林友芳92022/11/24malloc说明malloc使用注意事项：的返回值（void*）应通过类型强制转为特定指针类型后赋给

指针变量。分配存储块大小应该用sizeof计算动态分配必须检查成功与否动态分配的块大小也是确定的。越界使用（尤其是越界赋值）是严重错误，可能导致程序或系统垮台北京交通大学计算机与信息技术学院教师：

林友芳102022/11/246.calloc带计数和清0的存储分配函数calloc，原型：void*calloc(size_tn,size_tsize);size是元素大小，n是个数。分配一块存储，足够存n个大小为size的元素，并把元素全部清0；无

法分配时返回空指针值。前面的存储分配问题也可用下面语句实现data=(double*)calloc(n,sizeof(double));主要差别malloc对所分配的区域不做任何事情，calloc对整个区域自动清0。北京交通大

学计算机与信息技术学院教师：林友芳112022/11/247.空间释放函数：free为保证动态存储的有效使用，动态分配块不再用时应释放。动态存储块的释放只能通过调用free完成。Memoryleak函数原型voidfree(v

oid*p);功能free释放p指的存储块。注意该块必须是通过动态存储分配得到的，不要对并非指向动态分配块的指针用本操作p值为空时什么也不做执行free(p)后p值未变，被指块可能已变。不允许再间接访

问已释放存储块北京交通大学计算机与信息技术学院教师：林友芳122022/11/248.分配调整函数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指向新块，正常处理*/...2022/11/2413二、动态存储空间管理如果动态申请了许多同类型缓冲区，该如何管理？北京交通大学计算机与信息

技术学院教师：林友芳142022/11/24方法1：指针数组（地址数组）设臵一段内存空间，例如数组，用来保存存储空间的起始地址。数组中每个元素用来保存某种类型的存储空间的地址，等于每个元素都是一个指针

变量。int*pnarr[10];//定义一个长度为10的整型指针数组（整型地址数组）char*psz[5];//定义一个长度为5的字符指针数组。0x0012ff7d0x0012ff80…0x0012fe1

2其中每个元素都用来保存某种类型的存储空间的地址北京交通大学计算机与信息技术学院教师：林友芳152022/11/24例如设一个班最多有50人，但每个班的人数不定，为了表示这50用户，可以定义如下指针数组structUserAccount*Accounts[50

];完成如下功能初始化指针数组将新生成的某个班用户加入班级用户集，并存放在空位臵上。将某个班指定用户号的用户删除给某个班所有女生发m元补助将新生成的某个班用户插入到指定位臵i上，i后面的用户顺序往后退。北京交通大学计算机与信息技术学院教师：林友芳162022/

11/24指针数组结构示例0x0012ff6dNULL0x0012ff800x0012ce000x0012fe12…08120001张帅帅110108…M0.1008120099李美美350108…F50

0.0008120002赵小飞360108…M20.0008120007罗小花410108…F88.200x0012ff6d0x0012ff800x0012ce000x0012fe12…长度为50空指针，可能曾被删除后续元素或空或不空Accounts北京交通大学计算机与信息技术

学院教师：林友芳172022/11/24功能实现初始化指针数组voidInitAccounts(structUserAccount*Accounts[],intnLen){for(inti=0;i<nLen;i++)Accounts

[i]=NULL;}寻找一个空位臵返回，-1表示无空位臵intFindEmptyPlace(structUserAccount*Accounts[],intnLen){…}//可以有不同的搜索策略NULLNULL…北京交通大学计算机与信息技术学院教师：

林友芳182022/11/24功能实现（续）将新用户放在空位臵上，不成功返回-1，成功返回位臵号intAddNewAccountAtAnyEmptyPlace(structUserAccount*Ac

counts[],intnLen,structUserAccount*pUser){intnPlace;if((nPlace=FindEmptyPlace(Accounts,nLen))==-1)return

-1;Accounts[nPlace]=pUser;//完成放臵操作returnnPlace;//返回位臵}北京交通大学计算机与信息技术学院教师：林友芳192022/11/24功能示例0x0012ff6dNULL0x0012ff800x0012ce000x001

2fe12…08120001张帅帅110108…M0.1008120099李美美350108…F500.0008120002赵小飞360108…M20.0008120007罗小花410108…F88.200x0012ff6d0x0012ff800x0012ce000x00

12fe12…长度为50Accounts08120100孙悟空110105…M600.100x0012ff300x0012ff30新找到的空位新结点孙悟空报到北京交通大学计算机与信息技术学院教师：林友芳202022/11/24功能实现（续）将指定用户号的用户删除，返回该用户原来所在位臵int

DeleteAccountByNumber(structUserAccount*Accounts[],intnLen,char*pszUserNO){inti;for(i=0;i<nLen;i++)//找到指定用户{if((Accounts[i]!=NULL)&&(strcmp(pszUs

erNO,Accounts[i]->szUserNO)==0)){free(Accounts[i]);//释放空间Accounts[i]=NULL;//将当前位臵臵空returni;}}return-1;}用户结构体指针数组数组长度用户号字符串比较函数北京交通大学计算机与信息技术学院教师：林

友芳212022/11/24删除功能示例0x0012ff6d0x0012ff300x0012ff800x0012ce000x0012fe12…08120001张帅帅110108…M0.1008120099李美美3

50108…F500.0008120002赵小飞360108…M20.0008120007罗小花410108…F88.200x0012ff6d0x0012ff800x0012ce000x0012fe12…Accounts08120100孙悟空11010

5…M600.100x0012ff30NULL把孙悟空位臵找到把孙悟空开除:DeleteAccountByNumber(Accounts,50,“08120100”)释放存储空间北京交通大学计算机与信息技术学院教师：林友芳222022/11/24功能实现（续）给指定性别的群体充值，返回充

值人数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++;}}returnnCo

unter;}ChargeByGender(Accounts,50,„F‟,10.0);//妇女节发补助北京交通大学计算机与信息技术学院教师：林友芳232022/11/24方法2：链接结构采用链式数据结构一环扣一扣，通过一个元素

保存的其它元素的地址找到其它元素。通过链接结构实现动态数据增加元素：在铁链的某个位臵加一铁环删除元素：去掉铁链的某一铁环问题铁链中的每一铁环是一样的吗？普通的铁链是单向的还是双向的？有没有一些特殊的铁链，比如有多个分叉的？铁链可以跟铜链拴一起吗？铁链的头部可以拴在柱子上吗？

北京交通大学计算机与信息技术学院教师：林友芳242022/11/24链接结构实现原理链接结构中的元素需要保存的信息与结点本身有关的信息找到其它元素所需要的信息这些信息可以组织成结构问题：如何找到其它元素？

保存其它元素在内存中的地址在结构中设臵指针分量，用来保存其它元素的地址的分量指针分量问题：指针的类型？需要指向元素的结构类型的指针类型如果需要指向的元素与本元素的类型相同的话，则需要定义自引用的结构类型。北京交通大学计算机

与信息技术学院教师：林友芳252022/11/24链接结构一个结构元素可以通过指针引用同类或不同类的结构元素，多个结构元素通过指针建立联系。指向结构的指针称为链接，形成的复杂数据结构称为链接结构最简单的链接结构线性链接形成的表，链接表。每个自引用结构有一个链

接指针分量。北京交通大学计算机与信息技术学院教师：林友芳262022/11/24最简单的链接结构：单向链表单向链接表就像链条，自引用结构是链表中的一个链节，称为链表结点，结点间由指针连接形成整个结构。所有结点（结构）由动态分配创建。从指向表首结点的指针出发，沿链接

可顺序访问表中各结点。该指针代表整个表。通常把最后结点的指针臵空表示结束。0北京交通大学计算机与信息技术学院教师：林友芳272022/11/2400000000更复杂的引用链接结构北京交通大学计算机与信息技术学院教师：林

友芳282022/11/24单向链表结构示例structUserAccount{charUserNO[15];charName[20];charID[19];charGender;doubleBalance;structUserAccount*pNextUser;};用来保存下

一个结点的地址此处改成如下形式是否可行，为什么？structUserAccountNextUser;北京交通大学计算机与信息技术学院教师：林友芳292022/11/24普通单向链表示意图08120001张帅帅110108…M0.1008120

002赵小飞360108…M20.0008120007罗小花410108…F88.2008120099李美美350108…F500.00NULL…HeadTail2022/11/2430三、链表北京交通大学计算机与信息技术学院教师：林友芳312022/11/2

41.需求设有某系统的用户信息结构体，其中用户ID长度为10用户姓名长度不超过10需要处理的用户数据不定，假设某程序需要以链表方式处理用户的数据北京交通大学计算机与信息技术学院教师：林友芳322022/11/24普通单向链表示意DataD

ataDataDataNULL…HeadTail北京交通大学计算机与信息技术学院教师：林友芳332022/11/24链表结点结构声明方法1:structUserInfoNode{charszID[11];//IDcharszName[11];//姓名structUserInfoNode*pNe

xtUser;//下个用户指针};方法2：typedefstructUserInfoNodeUSERNODE,*USERPOINTER;structUserInfoNode{charszID[11];//IDcharszName[11];//姓名USERPOINTER*pNextUser;//下个

用户指针};北京交通大学计算机与信息技术学院教师：林友芳342022/11/24更好的方法：基本信息单独说明//用户基本信息结构声明structUserInfo{charszID[11];//ID，11个字符charszName[11];//姓名，11个字符};或typ

edefstruct{charszID[11];//ID，11个字符charszName[11];//姓名，11个字符}USERINFO;北京交通大学计算机与信息技术学院教师：林友芳352022/11/24更常见合理的声明方法方法3：s

tructUserLinkNode{structUserInfoData;//数据structUserLinkNode*pNextUser;//};structUserInfoUserInfoArr[100];或typedefstruct{USER

INFOData;//数据结点structUserLinkNode*pNextUser;//}USERLINKNODE;北京交通大学计算机与信息技术学院教师：林友芳362022/11/24增加一个链表描述信息结点NumberHeadTailDataDataDataDataNULL…LinkInf

oNode关于链表整体描述信息结点北京交通大学计算机与信息技术学院教师：林友芳372022/11/24描述结点结构说明示例structUserLink{structUserLinkNode*pHead;//头指针structUserLinkNode*pTai

l;//尾指针intnNumber;//链表中的结点计数};或typedefstruct{USERLINKNODE*pHead;//头指针USERLINKNODE*pTail;//尾指针intnNumber;//链表中的结点计数}USERLINK;北京交通大学计算机与信息技

术学院教师：林友芳382022/11/24可以增加一个不用的头结点NumberHeadTailDataDataDataNULL…LinkInfoNode目的在于写程序方便，简化一些链表操作，数据结构课程中会有进一步的阐述不用的头结点北京交通大学计算机与信息

技术学院教师：林友芳392022/11/24关于后面的操作的假定链表为单向链表没有设臵空的头结点设臵有信息描述结点，记录如下信息头结点尾结点链表中结点个数北京交通大学计算机与信息技术学院教师：林友芳402022/11/24在链表中增加一个节点有几种增加方式将新结点作为最

后一个元素增加到链表的尾部，将新结点作为第一个元素增加到链表的头部将新结点按照某种次序要求插入到指定位臵北京交通大学计算机与信息技术学院教师：林友芳412022/11/24加到尾部如果链表为空，则需要做一些初始化工作，将新的结点当成头结点和尾结点如果链表不为空，则

将该结点作为尾结点的下一个结点，修改尾结点指针。如果没有记录尾结点指针，则需要从头结点开始找到最后一个结点。pHeadpTailDataDataNULL……pNewNodeNULL北京交通大学计算机与信息

技术学院教师：林友芳422022/11/24示例代码，加到尾部intAddUserToTail(structUserLink*pUsers,//链表描述信息指针structUserLinkNode*pNewUser//新结点指针){if(pUsers==NU

LL||pNewUser==NULL)return-1;if(pUsers->nNumber<=0){//如果还没有元素pUsers->pHead=pNewUser;pUsers->pTail=pUsers->pHead;//头尾指针指向同一个结点}else{//把结点信息附到链表尾部pUser

s->pTail->pNext=pNewUser;//加到尾到pUsers->pTail=pNewUser;//修改尾结点指针}pUsers->pTail->pNext=NULL;//最后一个结点的后继臵空pUsers->nNumber++;//计数加

1return0;}北京交通大学计算机与信息技术学院教师：林友芳432022/11/24加到头部如果链表为空，则需要做一些初始化工作，将新的结点当成头结点和尾结点如果链表不为空，需要将新结点的下一个结点臵为原来的头结点，并把新结点

作为头结点pHeadpTailDataDataNULL……NULLpNewNode北京交通大学计算机与信息技术学院教师：林友芳442022/11/24示例代码，加到头部intAddUserToHead(structUserLink*pUsers,//链表描述信息指针structUserLin

kNode*pNewUser//新结点指针){if(pUsers==NULL||pNewUser==NULL)return-1;if(pUsers->nNumber<=0){//如果还没有元素pUsers->pHead=pNewUse

r;pUsers->pTail=pUsers->pHead;//头尾指针指向同一个结点pNewUser->pNext=NULL;}else{//把结点信息附到链表头部pUsers->pNewUser->pNext=pUsers->pHead;//加到头部pUsers->pHead=pNewUse

r;//修改头结点指针}pUsers->nNumber++;//计数加1return0;}北京交通大学计算机与信息技术学院教师：林友芳452022/11/24在链表中插入一个新结点基本操作q->pNex

t=p->pNext;p->pNext=q;其它用于保持链表指针完整性的操作。^^功能示意ppqqrr插入前插入后北京交通大学计算机与信息技术学院教师：林友芳462022/11/24去除链表中的某个结点基本操作p->pNext=q->pNext;外围附加

操作，用于保证链表的各种指针的完整性，如头指针，尾指针等。如：如果删除的是最后一个结点的话，需要修改尾指针功能示意pqrprq北京交通大学计算机与信息技术学院教师：林友芳472022/11/24遍历链表常见功能遍历

链表逐个访问所有结点，进行相应的处理，如将所有用户的某项指标求和，输出所有用户的信息查找某个或某些符合给定条件的结点，进行相应处理…北京交通大学计算机与信息技术学院教师：林友芳482022/11/24示例代码:输出所有

元素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,p

Node->Data.szName,}return0;}北京交通大学计算机与信息技术学院教师：林友芳492022/11/24参数改成头结点intShowData(structUserLinkNode*pHead)//给出头结点{structUserLinkNode*pNode;if(p

Head==NULL)return-1;for(pNode=pHead;//从第一个元素开始pNode!=NULL;//判断当前结点是否为空pNode=pNode->pNext//准备处理下一个结点){//对每个结点出输出信息printf("%11s\t%11s\t

\n",pNode->Data.szID,pNode->Data.szName,}return0;}北京交通大学计算机与信息技术学院教师：林友芳502022/11/24本章内容动态存储分配及其函数动态存储空间管理方法链表概念链表的定义和基本操作2022/11/2451本

章结束北京交通大学计算机与信息技术学院态度决定一切细节影响成败