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

1、第十七第十七 章章动态存储空间管理与动态存储空间管理与链表链表12/28/20211一、动态存储分配及常见函数说明隐式和显式12/28/20212北京交通大学计算机与信息技术学院1. 引例n要处理学生成绩，需要用数组存放。但编程时并不知道运行时需要处理多少学生成绩，每次处理的成绩项数也可能不同。nint n;n.nscanf(%d, &n);ndouble scoresn; /* 不行！*/n. /* 读入数据，然后处理 */n不能用变量说明scores大小（必须静态确定）。12/28/20213教师：林友芳北京交通大学计算机与信息技术学院2. 问题的本质及解决方案n问题的本质n程序运

2、行中需要使用存储，有时程序对存储的需求量在写程序时不能确定。n可能解决方案1）分析问题，定义适当大小的数组。若分析正确，一般都能处理。但数据很多时程序就不能用。2）定义尽可能大的数组以满足任何需要。浪费大量存储资源。如有多个这种数组就更难办。系统可能无法容纳几个大数组，但实际上它们并不同时需要很大空间。n解决的办法是“动态存储分配”。在程序运行中做存储分配工作。12/28/20214教师：林友芳北京交通大学计算机与信息技术学院3. 动态存储分配n动态存储分配n根据运行中的需要分配存储，取得存储块使用，称为动态存储分配。在运行中根据需要动态进行。n动态存储块具有起始地址，地址可以存储在指针里，因

3、此可以借助于指针保存存储空间地址。n用指针指向存储块，间接使用被指存储。访问动态分配存储是指针的最重要用途。12/28/20215教师：林友芳北京交通大学计算机与信息技术学院4. 动态存储释放及存储堆n动态释放n不用的动态存储块应交还系统，动态申请的内存空间必须由程序代码以显式的方式主动释放。n动态分配、释放由动态存储管理系统完成，这是程序运行系统的子系统，管理着称作堆（英文heap）的存储区。n大部分常规语言都有这种机制。12/28/20216教师：林友芳北京交通大学计算机与信息技术学院5. C语言的动态存储管理机制n用标准库函数实现用标准库函数实现nstdlib.hstdlib.hnmal

4、loc.hmalloc.hn存储分配函数存储分配函数mallocmalloc() ()，原型：，原型：nvoid void * *malloc(size_tmalloc(size_t n); / n); /* *size_tsize_t是某整型是某整型* */ /n功能功能n分配一块不小于分配一块不小于n n的存储，返回其地址。无法的存储，返回其地址。无法满足时返回空指针值。满足时返回空指针值。12/28/20217教师：林友芳北京交通大学计算机与信息技术学院例intint n; double n; double * *data;data;. . scanf(%dscanf(%d, &

5、n);, &n);data=(doubledata=(double* *) )malloc(nmalloc(n* *sizeof(doublesizeof(double););if (data = NULL) if (data = NULL) . / . /* * 分配未完成时的处理分配未完成时的处理 * */ / . .dataidatai.* *( (data+jdata+j)./)./* *正常处理正常处理* */ /12/28/20218教师：林友芳北京交通大学计算机与信息技术学院malloc说明nmalloc使用注意事项：n的返回值（void*）应通过类型强制转为特定指针类型

6、后赋给指针变量。n分配存储块大小应该用sizeof计算n动态分配必须检查成功与否n动态分配的块大小也是确定的。越界使用（尤其是越界赋值）是严重错误，可能导致程序或系统垮台12/28/20219教师：林友芳北京交通大学计算机与信息技术学院6. callocn带计数和清带计数和清0 0的存储分配函数的存储分配函数calloccalloc，原型：，原型：nvoid void * *calloc(size_tcalloc(size_t n, size_t size); n, size_t size);nsizesize是元素大小，是元素大小，n n是个数。是个数。n分配一块存储，足够存分配一块存储，足

7、够存n n个大小为个大小为sizesize的元素，并的元素，并把元素把元素全部清全部清0 0；n无法分配时返回空指针值。前面的存储分配问题无法分配时返回空指针值。前面的存储分配问题也可用下面语句实现也可用下面语句实现ndata = (doubledata = (double* *) )calloc(ncalloc(n, , sizeof(doublesizeof(double););n主要差别主要差别nmallocmalloc对所分配的区域不做任何事情，对所分配的区域不做任何事情，calloccalloc对整个区对整个区域自动清域自动清0 0。12/28/202110教师：林友芳北京交通大学计

8、算机与信息技术学院7. 空间释放函数：freen为保证动态存储的有效使用，动态分配块不再用时应释放。动态存储块的释放只能通过调用free完成。Memory leakn函数原型nvoid free(void *p);n功能nfree释放p指的存储块。n注意n该块必须是通过动态存储分配得到的，不要对并非指向动态分配块的指针用本操作np值为空时什么也不做n执行free(p)后p值未变，被指块可能已变。不允许再间接访问已释放存储块12/28/202111教师：林友芳北京交通大学计算机与信息技术学院8. 8. 分配调整函数分配调整函数reallocn函数原型nvoid *realloc(void *p,

9、 size_t n);n功能n更改已有分配。p指原分配块，n是新大小要求。n返回大小至少为n的存储块指针，新块与原块一致：n新块小时保存原块n范围内数据；n新块大时原数据存在，新增部分不初始化。分配成功后原块可能改变。n无法满足时返回空指针，原块不变。n常用写法(防止分配失败导致原存储块丢失) ：nq = (double*)realloc(p, m * sizeof(double);nif (q = NULL) /*未成功，p仍指原块，特殊处理*/ nelse p = q; /* 令p指向新块，正常处理 */ .12/28/202112教师：林友芳二、动态存储空间管理如果动态申请了许多同类型缓

10、冲区，该如何管理？12/28/202113北京交通大学计算机与信息技术学院方法1：指针数组（地址数组）n设置一段内存空间，例如数组，用来保存存储空间的起始地址。n数组中每个元素用来保存某种类型的存储空间的地址，等于每个元素都是一个指针变量。nint *pnarr10; /定义一个长度为10的整型指针数组（整型地址数组）nchar *psz5; /定义一个长度为5的字符指针数组。0 x0012ff7d0 x0012ff800 x0012fe12其中每个元素都用来保存某种类型的存储空间的地址12/28/202114教师：林友芳北京交通大学计算机与信息技术学院例如n设一个班最多有50人，但每个班的人

11、数不定，为了表示这50用户，可以定义如下指针数组nstruct UserAccount *Accounts 50;n完成如下功能n初始化指针数组n将新生成的某个班用户加入班级用户集，并存放在空位置上。n将某个班指定用户号的用户删除n给某个班所有女生发m元补助n将新生成的某个班用户插入到指定位置i上，i后面的用户顺序往后退。12/28/202115教师：林友芳北京交通大学计算机与信息技术学院指针数组结构示例0 x0012ff6dNULL0 x0012ff800 x0012ce000 x0012fe1208120001 张帅帅110108M0.1008120099 李美美350108F500.00

12、08120002 赵小飞360108M20.0008120007 罗小花410108F88.200 x0012ff6d0 x0012ff800 x0012ce000 x0012fe12长度为50空指针，可能曾被删除后续元素或空或不空Accounts12/28/202116教师：林友芳北京交通大学计算机与信息技术学院功能实现n初始化指针数组void InitAccounts(struct UserAccount *Accounts, int nLen) for (int i = 0; i nLen; i+) Accountsi = NULL;n寻找一个空位置返回，-1表示无空位置int Find

13、EmptyPlace(struct UserAccount *Accounts, int nLen) /可以有不同的搜索策略NULLNULL12/28/202117教师：林友芳北京交通大学计算机与信息技术学院功能实现（续）n将新用户放在空位置上，不成功返回-1，成功返回位置号int AddNewAccountAtAnyEmptyPlace(struct UserAccount *Accounts, int nLen, struct UserAccount *pUser) int nPlace;if (nPlace = FindEmptyPlace(Accounts, nLen) = -1) r

14、eturn -1; AccountsnPlace = pUser; /完成放置操作 return nPlace; /返回位置12/28/202118教师：林友芳北京交通大学计算机与信息技术学院功能示例0 x0012ff6dNULL0 x0012ff800 x0012ce000 x0012fe1208120001 张帅帅110108M0.1008120099 李美美350108F500.0008120002 赵小飞360108M20.0008120007 罗小花410108F88.200 x0012ff6d0 x0012ff800 x0012ce000 x0012fe12长度为50Account

15、s08120100 孙悟空110105M600.100 x0012ff300 x0012ff30新找到的空位新结点孙悟空报到12/28/202119教师：林友芳北京交通大学计算机与信息技术学院功能实现（续）n将指定用户号的用户删除，返回该用户原来所在位置int DeleteAccountByNumber(struct UserAccount *Accounts, int nLen, char *pszUserNO) int i; for (i = 0; i szUserNO) = 0) free(Accountsi); /释放空间 Accountsi = NULL; /将当前位置置空 retu

16、rn i; return -1;用户结构体指针数组数组长度用户号字符串比较函数12/28/202120教师：林友芳北京交通大学计算机与信息技术学院删除功能示例0 x0012ff6d0 x0012ff300 x0012ff800 x0012ce000 x0012fe1208120001 张帅帅110108M0.1008120099 李美美350108F500.0008120002 赵小飞360108M20.0008120007 罗小花410108F88.200 x0012ff6d0 x0012ff800 x0012ce000 x0012fe12Accounts08120100 孙悟空110105

17、M600.100 x0012ff30NULL把孙悟空位置找到把孙悟空开除:DeleteAccountByNumber(Accounts, 50, “08120100”)释放存储空间12/28/202121教师：林友芳北京交通大学计算机与信息技术学院功能实现（续）n给指定性别的群体充值，返回充值人数int ChargeByGender(struct UserAccount *Accounts, int nLen, char cGender, double dAmount) int nCounter = 0; /计数器 for (int i = 0; i cGender = cGender) Ac

18、countsi-dBalance+= dAmount; nCounter+; return nCounter;ChargeByGender(Accounts, 50, F, 10.0);/妇女节发补助12/28/202122教师：林友芳北京交通大学计算机与信息技术学院方法2：链接结构n采用链式数据结构n一环扣一扣，通过一个元素保存的其它元素的地址找到其它元素。n通过链接结构实现动态数据n增加元素：在铁链的某个位置加一铁环n删除元素：去掉铁链的某一铁环n问题n铁链中的每一铁环是一样的吗？n普通的铁链是单向的还是双向的？n有没有一些特殊的铁链，比如有多个分叉的？n铁链可以跟铜链拴一起吗？n铁链的头

19、部可以拴在柱子上吗？12/28/202123教师：林友芳北京交通大学计算机与信息技术学院链接结构实现原理n链接结构中的元素需要保存的信息n与结点本身有关的信息n找到其它元素所需要的信息n这些信息可以组织成结构n问题：如何找到其它元素？n保存其它元素在内存中的地址n在结构中设置指针分量，用来保存其它元素的地址的分量指针分量n问题：指针的类型？n需要指向元素的结构类型的指针类型n如果需要指向的元素与本元素的类型相同的话，则需要定义自引用的结构类型。12/28/202124教师：林友芳北京交通大学计算机与信息技术学院链接结构n一个结构元素可以通过指针引用同类或不同类的结构元素，多个结构元素通过指针建

20、立联系。n指向结构的指针称为链接，形成的复杂数据结构称为链接结构n最简单的链接结构n线性链接形成的表，链接表。n每个自引用结构有一个链接指针分量。12/28/202125教师：林友芳北京交通大学计算机与信息技术学院最简单的链接结构：单向链表n单向链接表就像链条，自引用结构是链表中的一个链节，称为链表结点，结点间由指针连接形成整个结构。n所有结点（结构）由动态分配创建。n从指向表首结点的指针出发，沿链接可顺序访问表中各结点。该指针代表整个表。通常把最后结点的指针置空表示结束。012/28/202126教师：林友芳北京交通大学计算机与信息技术学院00000000更复杂的引用链接结构12/28/20

21、2127教师：林友芳北京交通大学计算机与信息技术学院单向链表结构示例struct UserAccount char UserNO15; char Name20; char ID19; char Gender; double Balance;struct UserAccount *pNextUser;用来保存下一个结点的地址此处改成如下形式是否可行，为什么？struct UserAccount NextUser;12/28/202128教师：林友芳北京交通大学计算机与信息技术学院普通单向链表示意图08120001 张帅帅110108M0.1008120002 赵小飞360108M20.00081

22、20007 罗小花410108F88.2008120099 李美美350108F500.00NULLHeadTail12/28/202129教师：林友芳三、链表12/28/202130北京交通大学计算机与信息技术学院1. 需求n设有某系统的用户信息结构体，其中n用户ID长度为10n用户姓名长度不超过10n需要处理的用户数据不定，n假设某程序需要以链表方式处理用户的数据12/28/202131教师：林友芳北京交通大学计算机与信息技术学院普通单向链表示意DataDataDataDataNULLHeadTail12/28/202132教师：林友芳北京交通大学计算机与信息技术学院链表结点结构声明方法1

23、:struct UserInfoNodechar szID11;/IDchar szName11;/姓名 struct UserInfoNode *pNextUser; /下个用户指针;方法2：typedef struct UserInfoNode USERNODE, *USERPOINTER;struct UserInfoNodechar szID11;/IDchar szName11;/姓名 USERPOINTER *pNextUser;/下个用户指针;12/28/202133教师：林友芳北京交通大学计算机与信息技术学院更好的方法：基本信息单独说明/用户基本信息结构声明struct Use

24、rInfochar szID11;/ID，11个字符个字符char szName11;/姓名，姓名，11个字符个字符;或typedef structchar szID11;/ID，11个字符个字符char szName11;/姓名，姓名，11个字符个字符 USERINFO;12/28/202134教师：林友芳北京交通大学计算机与信息技术学院更常见合理的声明方法方法3：struct UserLinkNode struct UserInfo Data;/数据数据 struct UserLinkNode *pNextUser; /;struct UserInfo UserInfoArr100;或ty

25、pedef struct USERINFO Data;/数据结点数据结点 struct UserLinkNode *pNextUser; / USERLINKNODE ;12/28/202135教师：林友芳北京交通大学计算机与信息技术学院增加一个链表描述信息结点NumberHeadTailDataDataDataDataNULLLinkInfoNoden关于链表整体描述信息结点12/28/202136教师：林友芳北京交通大学计算机与信息技术学院描述结点结构说明示例struct UserLinkstruct UserLinkNode *pHead; /头指针头指针 struct UserLink

26、Node *pTail; /尾指针尾指针int nNumber;/链表中的结点计数链表中的结点计数;或typedef struct USERLINKNODE *pHead; /头指针头指针 USERLINKNODE *pTail; /尾指针尾指针int nNumber;/链表中的结点计数链表中的结点计数 USERLINK;12/28/202137教师：林友芳北京交通大学计算机与信息技术学院可以增加一个不用的头结点NumberHeadTailDataDataDataNULLLinkInfoNoden目的在于写程序方便，简化一些链表操作，数据结构课程中会有进一步的阐述不用的不用的头结点头结点12/

27、28/202138教师：林友芳北京交通大学计算机与信息技术学院关于后面的操作的假定n链表为单向链表n没有设置空的头结点n设置有信息描述结点，记录如下信息n头结点n尾结点n链表中结点个数12/28/202139教师：林友芳北京交通大学计算机与信息技术学院在链表中增加一个节点n有几种增加方式n将新结点作为最后一个元素增加到链表的尾部，n将新结点作为第一个元素增加到链表的头部n将新结点按照某种次序要求插入到指定位置12/28/202140教师：林友芳北京交通大学计算机与信息技术学院加到尾部n如果链表为空，则需要做一些初始化工作，将新的结点当成头结点和尾结点n如果链表不为空，则将该结点作为尾结点的下一

28、个结点，修改尾结点指针。n如果没有记录尾结点指针，则需要从头结点开始找到最后一个结点。pHeadpTailDataDataNULLpNewNode NULL 12/28/202141教师：林友芳北京交通大学计算机与信息技术学院示例代码，加到尾部int AddUserToTail( struct UserLink *pUsers, /链表描述信息指针 struct UserLinkNode *pNewUser/新结点指针) if (pUsers = NULL | pNewUser = NULL) return -1;if (pUsers-nNumber pHead = pNewUser; pUs

29、ers-pTail = pUsers-pHead; /头尾指针指向同一个结点 else/把结点信息附到链表尾部 pUsers-pTail-pNext = pNewUser; /加到尾到 pUsers-pTail = pNewUser;/修改尾结点指针 pUsers-pTail-pNext = NULL;/最后一个结点的后继置空pUsers-nNumber+;/计数加1return 0;12/28/202142教师：林友芳北京交通大学计算机与信息技术学院加到头部n如果链表为空，则需要做一些初始化工作，将新的结点当成头结点和尾结点n如果链表不为空，需要将新结点的下一个结点置为原来的头结点，并把新结

30、点作为头结点pHeadpTailDataDataNULLNULLpNewNode 12/28/202143教师：林友芳北京交通大学计算机与信息技术学院示例代码，加到头部int AddUserToHead( struct UserLink *pUsers, /链表描述信息指针 struct UserLinkNode *pNewUser/新结点指针) if (pUsers = NULL | pNewUser = NULL) return -1;if (pUsers-nNumber pHead = pNewUser; pUsers-pTail = pUsers-pHead; /头尾指针指向同一个结点 pNewUser-pNext = NULL; else/把结点信息附到链表头部 pUsers-pNewUser-pNext = pUsers-pHead ; /加到头部 pUsers-pHead = pNewUser;/修改头结点指针 pUsers-nNumber+;/计数加1return 0;12/28/202144教师：林友芳北京交通大学计算机与信息技术学院在链表中插入一