1、2022-10-241第十七第十七 章章动态存储空间管理与动态存储空间管理与链表链表2022-10-242一、动态存储分配及常见函数说明隐式和显式北京交通大学计算机与信息技术学院教师：林友芳32022-10-241.引例n要处理学生成绩，需要用数组存放。但编程时并不知道运行时需要处理多少学生成绩，每次处理的成绩项数也可能不同。nint n;n.nscanf(%d,&n);ndouble scoresn;/*不行！*/n./*读入数据，然后处理*/n不能用变量说明scores大小（必须静态确定）。北京交通大学计算机与信息技术学院教师：林友芳42022-10-242.问题的本质及解决方案n问题的本
2、质n程序运行中需要使用存储，有时程序对存储的需求量在写程序时不能确定。n可能解决方案1）分析问题，定义适当大小的数组。若分析正确，一般都能处理。但数据很多时程序就不能用。2）定义尽可能大的数组以满足任何需要。浪费大量存储资源。如有多个这种数组就更难办。系统可能无法容纳几个大数组，但实际上它们并不同时需要很大空间。n解决的办法是“动态存储分配”。在程序运行中做存储分配工作。北京交通大学计算机与信息技术学院教师：林友芳52022-10-243.动态存储分配n动态存储分配n根据运行中的需要分配存储，取得存储块使用，称为动态存储分配。在运行中根据需要动态进行。n动态存储块具有起始地址，地址可以存储在指
3、针里，因此可以借助于指针保存存储空间地址。n用指针指向存储块，间接使用被指存储。访问动态分配存储是指针的最重要用途。北京交通大学计算机与信息技术学院教师：林友芳62022-10-244.动态存储释放及存储堆n动态释放n不用的动态存储块应交还系统，动态申请的内存空间必须由程序代码以显式的方式主动释放。n动态分配、释放由动态存储管理系统完成，这是程序运行系统的子系统，管理着称作堆（英文heap）的存储区。n大部分常规语言都有这种机制。北京交通大学计算机与信息技术学院教师：林友芳72022-10-245.C语言的动态存储管理机制n用标准库函数实现用标准库函数实现nstdlib.hstdlib.hnm
4、alloc.hmalloc.hn存储分配函数存储分配函数malloc()malloc()，原型：，原型：nvoid void*malloc(size_t n);/malloc(size_t n);/*size_tsize_t是某整型是某整型*/n功能功能n分配一块不小于分配一块不小于n n的存储，返回其地址。无法的存储，返回其地址。无法满足时返回空指针值。满足时返回空指针值。北京交通大学计算机与信息技术学院教师：林友芳82022-10-24例int n;double int n;double*data;data;.scanf(%d,&n);.scanf(%d,&n);data=(doubled
5、ata=(double*)malloc(n)malloc(n*sizeof(double);sizeof(double);if(data=NULL)if(data=NULL)././*分配未完成时的处理分配未完成时的处理 */.datai.datai.*(data+j)./(data+j)./*正常处理正常处理*/北京交通大学计算机与信息技术学院教师：林友芳92022-10-24malloc说明nmalloc使用注意事项：n的返回值（void*）应通过类型强制转为特定指针类型后赋给指针变量。n分配存储块大小应该用sizeof计算n动态分配必须检查成功与否n动态分配的块大小也是确定的。越界使用（
6、尤其是越界赋值）是严重错误，可能导致程序或系统垮台北京交通大学计算机与信息技术学院教师：林友芳102022-10-246.callocn带计数和清带计数和清0 0的存储分配函数的存储分配函数calloccalloc，原型：，原型：nvoid void*calloc(size_t n,size_t size);calloc(size_t n,size_t size);nsizesize是元素大小，是元素大小，n n是个数。是个数。n分配一块存储，足够存分配一块存储，足够存n n个大小为个大小为sizesize的元素，并的元素，并把元素把元素全部清全部清0 0；n无法分配时返回空指针值。前面的存储
7、分配问题无法分配时返回空指针值。前面的存储分配问题也可用下面语句实现也可用下面语句实现ndata=(doubledata=(double*)calloc(n,sizeof(double);)calloc(n,sizeof(double);n主要差别主要差别nmallocmalloc对所分配的区域不做任何事情，对所分配的区域不做任何事情，calloccalloc对整个区对整个区域自动清域自动清0 0。北京交通大学计算机与信息技术学院教师：林友芳112022-10-247.空间释放函数：freen为保证动态存储的有效使用，动态分配块不再用时应释放。动态存储块的释放只能通过调用free完成。Memo
8、ry leakn函数原型nvoid free(void*p);n功能nfree释放p指的存储块。n注意n该块必须是通过动态存储分配得到的，不要对并非指向动态分配块的指针用本操作np值为空时什么也不做n执行free(p)后p值未变，被指块可能已变。不允许再间接访问已释放存储块北京交通大学计算机与信息技术学院教师：林友芳122022-10-248.8.分配调整函数分配调整函数reallocn函数原型nvoid*realloc(void*p,size_t n);n功能n更改已有分配。p指原分配块，n是新大小要求。n返回大小至少为n的存储块指针，新块与原块一致：n新块小时保存原块n范围内数据；n新块大
9、时原数据存在，新增部分不初始化。分配成功后原块可能改变。n无法满足时返回空指针，原块不变。n常用写法(防止分配失败导致原存储块丢失)：nq=(double*)realloc(p,m*sizeof(double);nif(q=NULL)/*未成功，p仍指原块，特殊处理*/nelse p=q;/*令p指向新块，正常处理*/.2022-10-2413二、动态存储空间管理如果动态申请了许多同类型缓冲区，该如何管理？北京交通大学计算机与信息技术学院教师：林友芳142022-10-24方法1：指针数组（地址数组）n设置一段内存空间，例如数组，用来保存存储空间的起始地址。n数组中每个元素用来保存某种类型的存
10、储空间的地址，等于每个元素都是一个指针变量。nint*pnarr10;/定义一个长度为10的整型指针数组（整型地址数组）nchar*psz5;/定义一个长度为5的字符指针数组。0 x0012ff7d0 x0012ff800 x0012fe12其中每个元素都用来保存某种类型的存储空间的地址北京交通大学计算机与信息技术学院教师：林友芳152022-10-24例如n设一个班最多有50人，但每个班的人数不定，为了表示这50用户，可以定义如下指针数组nstruct UserAccount*Accounts 50;n完成如下功能n初始化指针数组n将新生成的某个班用户加入班级用户集，并存放在空位置上。n将某
11、个班指定用户号的用户删除n给某个班所有女生发m元补助n将新生成的某个班用户插入到指定位置i上，i后面的用户顺序往后退。北京交通大学计算机与信息技术学院教师：林友芳162022-10-24指针数组结构示例0 x0012ff6dNULL0 x0012ff800 x0012ce000 x0012fe1208120001 张帅帅110108M0.1008120099 李美美350108F500.0008120002 赵小飞360108M20.0008120007 罗小花410108F88.200 x0012ff6d0 x0012ff800 x0012ce000 x0012fe12长度为50空指针，可能
12、曾被删除后续元素或空或不空Accounts北京交通大学计算机与信息技术学院教师：林友芳172022-10-24功能实现n初始化指针数组void InitAccounts(struct UserAccount*Accounts,int nLen)for(int i=0;i nLen;i+)Accountsi=NULL;n寻找一个空位置返回，-1表示无空位置int FindEmptyPlace(struct UserAccount*Accounts,int nLen)/可以有不同的搜索策略NULLNULL北京交通大学计算机与信息技术学院教师：林友芳182022-10-24功能实现（续）n将新用户放
13、在空位置上，不成功返回-1，成功返回位置号int AddNewAccountAtAnyEmptyPlace(struct UserAccount*Accounts,int nLen,struct UserAccount*pUser)int nPlace;if(nPlace=FindEmptyPlace(Accounts,nLen)=-1)return-1;AccountsnPlace=pUser;/完成放置操作 return nPlace;/返回位置北京交通大学计算机与信息技术学院教师：林友芳192022-10-24功能示例0 x0012ff6dNULL0 x0012ff800 x0012ce
14、000 x0012fe1208120001 张帅帅110108M0.1008120099 李美美350108F500.0008120002 赵小飞360108M20.0008120007 罗小花410108F88.200 x0012ff6d0 x0012ff800 x0012ce000 x0012fe12长度为50Accounts08120100 孙悟空110105M600.100 x0012ff300 x0012ff30新找到的空位新结点孙悟空报到北京交通大学计算机与信息技术学院教师：林友芳202022-10-24功能实现（续）n将指定用户号的用户删除，返回该用户原来所在位置int Dele
15、teAccountByNumber(struct UserAccount*Accounts,int nLen,char*pszUserNO)int i;for(i=0;i szUserNO)=0)free(Accountsi);/释放空间 Accountsi=NULL;/将当前位置置空 return i;return-1;用户结构体指针数组数组长度用户号字符串比较函数北京交通大学计算机与信息技术学院教师：林友芳212022-10-24删除功能示例0 x0012ff6d0 x0012ff300 x0012ff800 x0012ce000 x0012fe1208120001 张帅帅110108M0
16、.1008120099 李美美350108F500.0008120002 赵小飞360108M20.0008120007 罗小花410108F88.200 x0012ff6d0 x0012ff800 x0012ce000 x0012fe12Accounts08120100 孙悟空110105M600.100 x0012ff30NULL把孙悟空位置找到把孙悟空开除:DeleteAccountByNumber(Accounts,50,“08120100”)释放存储空间北京交通大学计算机与信息技术学院教师：林友芳222022-10-24功能实现（续）n给指定性别的群体充值，返回充值人数int Cha
17、rgeByGender(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-10-24方法2：链接结构n采用链式数据结构n一环扣一扣，通过一个元素保存的其它元素的地址找到其
18、它元素。n通过链接结构实现动态数据n增加元素：在铁链的某个位置加一铁环n删除元素：去掉铁链的某一铁环n问题n铁链中的每一铁环是一样的吗？n普通的铁链是单向的还是双向的？n有没有一些特殊的铁链，比如有多个分叉的？n铁链可以跟铜链拴一起吗？n铁链的头部可以拴在柱子上吗？北京交通大学计算机与信息技术学院教师：林友芳242022-10-24链接结构实现原理n链接结构中的元素需要保存的信息n与结点本身有关的信息n找到其它元素所需要的信息n这些信息可以组织成结构n问题：如何找到其它元素？n保存其它元素在内存中的地址n在结构中设置指针分量，用来保存其它元素的地址的分量指针分量n问题：指针的类型？n需要指向元
19、素的结构类型的指针类型n如果需要指向的元素与本元素的类型相同的话，则需要定义自引用的结构类型。北京交通大学计算机与信息技术学院教师：林友芳252022-10-24链接结构n一个结构元素可以通过指针引用同类或不同类的结构元素，多个结构元素通过指针建立联系。n指向结构的指针称为链接，形成的复杂数据结构称为链接结构n最简单的链接结构n线性链接形成的表，链接表。n每个自引用结构有一个链接指针分量。北京交通大学计算机与信息技术学院教师：林友芳262022-10-24最简单的链接结构：单向链表n单向链接表就像链条，自引用结构是链表中的一个链节，称为链表结点，结点间由指针连接形成整个结构。n所有结点（结构）
20、由动态分配创建。n从指向表首结点的指针出发，沿链接可顺序访问表中各结点。该指针代表整个表。通常把最后结点的指针置空表示结束。0北京交通大学计算机与信息技术学院教师：林友芳272022-10-2400000000更复杂的引用链接结构北京交通大学计算机与信息技术学院教师：林友芳282022-10-24单向链表结构示例struct UserAccount char UserNO15;char Name20;char ID19;char Gender;double Balance;struct UserAccount*pNextUser;用来保存下一个结点的地址此处改成如下形式是否可行，为什么？str
21、uct UserAccount NextUser;北京交通大学计算机与信息技术学院教师：林友芳292022-10-24普通单向链表示意图08120001 张帅帅110108M0.1008120002 赵小飞360108M20.0008120007 罗小花410108F88.2008120099 李美美350108F500.00NULLHeadTail2022-10-2430三、链表北京交通大学计算机与信息技术学院教师：林友芳312022-10-241.需求n设有某系统的用户信息结构体，其中n用户ID长度为10n用户姓名长度不超过10n需要处理的用户数据不定，n假设某程序需要以链表方式处理用户的
22、数据北京交通大学计算机与信息技术学院教师：林友芳322022-10-24普通单向链表示意DataDataDataDataNULLHeadTail北京交通大学计算机与信息技术学院教师：林友芳332022-10-24链表结点结构声明方法1:struct UserInfoNodechar szID11;/IDchar szName11;/姓名 struct UserInfoNode*pNextUser;/下个用户指针;方法2：typedef struct UserInfoNode USERNODE,*USERPOINTER;struct UserInfoNodechar szID11;/IDchar
23、 szName11;/姓名 USERPOINTER*pNextUser;/下个用户指针;北京交通大学计算机与信息技术学院教师：林友芳342022-10-24更好的方法：基本信息单独说明/用户基本信息结构声明struct UserInfochar szID11;/ID，11个字符个字符char szName11;/姓名，姓名，11个字符个字符;或typedef structchar szID11;/ID，11个字符个字符char szName11;/姓名，姓名，11个字符个字符 USERINFO;北京交通大学计算机与信息技术学院教师：林友芳352022-10-24更常见合理的声明方法方法3：st
24、ruct UserLinkNode struct UserInfo Data;/数据数据 struct UserLinkNode*pNextUser;/;struct UserInfo UserInfoArr100;或typedef struct USERINFO Data;/数据结点数据结点 struct UserLinkNode*pNextUser;/USERLINKNODE;北京交通大学计算机与信息技术学院教师：林友芳362022-10-24增加一个链表描述信息结点NumberHeadTailDataDataDataDataNULLLinkInfoNoden关于链表整体描述信息结点北京交
25、通大学计算机与信息技术学院教师：林友芳372022-10-24描述结点结构说明示例struct UserLinkstruct UserLinkNode*pHead;/头指针头指针 struct UserLinkNode*pTail;/尾指针尾指针int nNumber;/链表中的结点计数链表中的结点计数;或typedef struct USERLINKNODE*pHead;/头指针头指针 USERLINKNODE*pTail;/尾指针尾指针int nNumber;/链表中的结点计数链表中的结点计数 USERLINK;北京交通大学计算机与信息技术学院教师：林友芳382022-10-24可以增加一
26、个不用的头结点NumberHeadTailDataDataDataNULLLinkInfoNoden目的在于写程序方便，简化一些链表操作，数据结构课程中会有进一步的阐述不用的不用的头结点头结点北京交通大学计算机与信息技术学院教师：林友芳392022-10-24关于后面的操作的假定n链表为单向链表n没有设置空的头结点n设置有信息描述结点，记录如下信息n头结点n尾结点n链表中结点个数北京交通大学计算机与信息技术学院教师：林友芳402022-10-24在链表中增加一个节点n有几种增加方式n将新结点作为最后一个元素增加到链表的尾部，n将新结点作为第一个元素增加到链表的头部n将新结点按照某种次序要求插入
27、到指定位置北京交通大学计算机与信息技术学院教师：林友芳412022-10-24加到尾部n如果链表为空，则需要做一些初始化工作，将新的结点当成头结点和尾结点n如果链表不为空，则将该结点作为尾结点的下一个结点，修改尾结点指针。n如果没有记录尾结点指针，则需要从头结点开始找到最后一个结点。pHeadpTailDataDataNULLpNewNode NULL 北京交通大学计算机与信息技术学院教师：林友芳422022-10-24示例代码，加到尾部int AddUserToTail(struct UserLink*pUsers,/链表描述信息指针 struct UserLinkNode*pNewUser
28、/新结点指针)if(pUsers=NULL|pNewUser=NULL)return-1;if(pUsers-nNumber pHead=pNewUser;pUsers-pTail=pUsers-pHead;/头尾指针指向同一个结点 else/把结点信息附到链表尾部 pUsers-pTail-pNext=pNewUser;/加到尾到 pUsers-pTail=pNewUser;/修改尾结点指针 pUsers-pTail-pNext=NULL;/最后一个结点的后继置空pUsers-nNumber+;/计数加1return 0;北京交通大学计算机与信息技术学院教师：林友芳432022-10-24加
29、到头部n如果链表为空，则需要做一些初始化工作，将新的结点当成头结点和尾结点n如果链表不为空，需要将新结点的下一个结点置为原来的头结点，并把新结点作为头结点pHeadpTailDataDataNULLNULLpNewNode 北京交通大学计算机与信息技术学院教师：林友芳442022-10-24示例代码，加到头部int AddUserToHead(struct UserLink*pUsers,/链表描述信息指针 struct UserLinkNode*pNewUser/新结点指针)if(pUsers=NULL|pNewUser=NULL)return-1;if(pUsers-nNumber pHe
30、ad=pNewUser;pUsers-pTail=pUsers-pHead;/头尾指针指向同一个结点 pNewUser-pNext=NULL;else/把结点信息附到链表头部 pUsers-pNewUser-pNext=pUsers-pHead;/加到头部 pUsers-pHead=pNewUser;/修改头结点指针 pUsers-nNumber+;/计数加1return 0;北京交通大学计算机与信息技术学院教师：林友芳452022-10-24在链表中插入一个新结点n基本操作nq-pNext=p-pNext;np-pNext=q;n其它用于保持链表指针完整性的操作。功能示意ppqqrr插入前插
31、入后北京交通大学计算机与信息技术学院教师：林友芳462022-10-24去除链表中的某个结点n基本操作np-pNext=q-pNext;n外围附加操作，用于保证链表的各种指针的完整性，如头指针，尾指针等。n如：如果删除的是最后一个结点的话，需要修改尾指针功能示意pqrprq北京交通大学计算机与信息技术学院教师：林友芳472022-10-24遍历链表n常见功能n遍历链表逐个访问所有结点，进行相应的处理，如将所有用户的某项指标求和，输出所有用户的信息n查找某个或某些符合给定条件的结点，进行相应处理n北京交通大学计算机与信息技术学院教师：林友芳482022-10-24示例代码:输出所有元素int S
32、howData(struct UserLink*pUsers)struct UserLinkNode*pNode;if(pUsers-nNumber pHead;/从第一个元素开始 pNode!=NULL;/判断当前结点是否为空pNode=pNode-pNext/准备处理下一个结点 )/对每个结点出输出信息printf(%11st%11stn,pNode-Data.szID,pNode-Data.szName,return 0;北京交通大学计算机与信息技术学院教师：林友芳492022-10-24参数改成头结点int ShowData(struct UserLinkNode*pHead)/给出头
33、结点struct UserLinkNode*pNode;if(pHead=NULL)return-1;for(pNode=pHead;/从第一个元素开始 pNode!=NULL;/判断当前结点是否为空pNode=pNode-pNext/准备处理下一个结点 )/对每个结点出输出信息printf(%11st%11stn,pNode-Data.szID,pNode-Data.szName,return 0;北京交通大学计算机与信息技术学院教师：林友芳502022-10-24本章内容n动态存储分配及其函数n动态存储空间管理方法n链表概念n链表的定义和基本操作2022-10-2451本章结束北京交通大学计算机与信息技术学院态度决定一切态度决定一切细节影响成败细节影响成败
