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

1、2020/7/9,1,第十七 章动态存储空间管理与链表,2020/7/9,2,一、动态存储分配及常见函数说明,隐式和显式,教师：林友芳,3,2020/7/9,1. 引例,要处理学生成绩，需要用数组存放。但编程时并不知道运行时需要处理多少学生成绩，每次处理的成绩项数也可能不同。 int n; . scanf(%d, /* 不行！*/ . /* 读入数据，然后处理 */ 不能用变量说明scores大小（必须静态确定）。,教师：林友芳,4,2020/7/9,2. 问题的本质及解决方案,问题的本质 程序运行中需要使用存储，有时程序对存储的需求量在写程序时不能确定。 可能解决方案 1）分析问题，定义适当

2、大小的数组。若分析正确，一般都能处理。但数据很多时程序就不能用。 2）定义尽可能大的数组以满足任何需要。浪费大量存储资源。如有多个这种数组就更难办。系统可能无法容纳几个大数组，但实际上它们并不同时需要很大空间。 解决的办法是“动态存储分配”。在程序运行中做存储分配工作。,教师：林友芳,5,2020/7/9,3. 动态存储分配,动态存储分配 根据运行中的需要分配存储，取得存储块使用，称为动态存储分配。在运行中根据需要动态进行。 动态存储块具有起始地址，地址可以存储在指针里，因此可以借助于指针保存存储空间地址。 用指针指向存储块，间接使用被指存储。访问动态分配存储是指针的最重要用途。,教师：林友芳

3、,6,2020/7/9,4. 动态存储释放及存储堆,动态释放 不用的动态存储块应交还系统，动态申请的内存空间必须由程序代码以显式的方式主动释放。 动态分配、释放由动态存储管理系统完成，这是程序运行系统的子系统，管理着称作堆（英文heap）的存储区。 大部分常规语言都有这种机制。,教师：林友芳,7,2020/7/9,5. C语言的动态存储管理机制,用标准库函数实现 stdlib.h malloc.h 存储分配函数malloc()，原型： void *malloc(size_t n); /*size_t是某整型*/ 功能 分配一块不小于n的存储，返回其地址。无法满足时返回空指针值。,教师：林友芳,

4、8,2020/7/9,例,int n; double *data; . scanf(%d, if (data = NULL) . /* 分配未完成时的处理 */ .datai.*(data+j)./*正常处理*/,教师：林友芳,9,2020/7/9,malloc说明,malloc使用注意事项： 的返回值（void*）应通过类型强制转为特定指针类型后赋给指针变量。 分配存储块大小应该用sizeof计算 动态分配必须检查成功与否 动态分配的块大小也是确定的。越界使用（尤其是越界赋值）是严重错误，可能导致程序或系统垮台,教师：林友芳,10,2020/7/9,6. calloc,带计数和清0的存储分配

5、函数calloc，原型： void *calloc(size_t n, size_t size); size是元素大小，n是个数。 分配一块存储，足够存n个大小为size的元素，并把元素全部清0； 无法分配时返回空指针值。前面的存储分配问题也可用下面语句实现 data = (double*)calloc(n, sizeof(double); 主要差别 malloc对所分配的区域不做任何事情，calloc对整个区域自动清0。,教师：林友芳,11,2020/7/9,7. 空间释放函数：free,为保证动态存储的有效使用，动态分配块不再用时应释放。动态存储块的释放只能通过调用free完成。Memor

6、y leak 函数原型 void free(void *p); 功能 free释放p指的存储块。 注意 该块必须是通过动态存储分配得到的，不要对并非指向动态分配块的指针用本操作 p值为空时什么也不做 执行free(p)后p值未变，被指块可能已变。不允许再间接访问已释放存储块,教师：林友芳,12,2020/7/9,8. 分配调整函数realloc,函数原型 void *realloc(void *p, size_t n); 功能 更改已有分配。p指原分配块，n是新大小要求。 返回大小至少为n的存储块指针，新块与原块一致： 新块小时保存原块n范围内数据； 新块大时原数据存在，新增部分不初始化。分配

7、成功后原块可能改变。 无法满足时返回空指针，原块不变。 常用写法(防止分配失败导致原存储块丢失) ： q = (double*)realloc(p, m * sizeof(double); if (q = NULL) /*未成功，p仍指原块，特殊处理*/ else p = q; /* 令p指向新块，正常处理 */ .,2020/7/9,13,二、动态存储空间管理,如果动态申请了许多同类型缓冲区，该如何管理？,教师：林友芳,14,2020/7/9,方法1：指针数组（地址数组）,设置一段内存空间，例如数组，用来保存存储空间的起始地址。 数组中每个元素用来保存某种类型的存储空间的地址，等于每个元素都

8、是一个指针变量。 int *pnarr10; /定义一个长度为10的整型指针数组（整型地址数组） char *psz5; /定义一个长度为5的字符指针数组。,其中每个元素都用来保存某种类型的存储空间的地址,教师：林友芳,15,2020/7/9,例如,设一个班最多有50人，但每个班的人数不定，为了表示这50用户，可以定义如下指针数组 struct UserAccount *Accounts 50; 完成如下功能 初始化指针数组 将新生成的某个班用户加入班级用户集，并存放在空位置上。 将某个班指定用户号的用户删除 给某个班所有女生发m元补助 将新生成的某个班用户插入到指定位置i上，i后面的用户顺序

9、往后退。,教师：林友芳,16,2020/7/9,指针数组结构示例,0 x0012ff6d,0 x0012ff80,0 x0012ce00,0 x0012fe12,长度为50,空指针，可能曾被删除,后续元素或空或不空,Accounts,教师：林友芳,17,2020/7/9,功能实现,初始化指针数组 void InitAccounts(struct UserAccount *Accounts, int nLen) for (int i = 0; i nLen; i+) Accountsi = NULL; 寻找一个空位置返回，-1表示无空位置 int FindEmptyPlace(struct Us

10、erAccount *Accounts, int nLen) /可以有不同的搜索策略,教师：林友芳,18,2020/7/9,功能实现（续）,将新用户放在空位置上，不成功返回-1，成功返回位置号 int AddNewAccountAtAnyEmptyPlace(struct UserAccount *Accounts, int nLen, struct UserAccount *pUser) int nPlace; if (nPlace = FindEmptyPlace(Accounts, nLen) = -1) return -1; AccountsnPlace = pUser; /完成放置操

11、作 return nPlace; /返回位置 ,教师：林友芳,19,2020/7/9,功能示例,0 x0012ff6d,0 x0012ff80,0 x0012ce00,0 x0012fe12,长度为50,Accounts,0 x0012ff30,0 x0012ff30,新找到的空位,新结点,孙悟空报到,教师：林友芳,20,2020/7/9,功能实现（续）,将指定用户号的用户删除，返回该用户原来所在位置 int DeleteAccountByNumber(struct UserAccount *Accounts, int nLen, char *pszUserNO) int i; for (i

12、= 0; i szUserNO) = 0) free(Accountsi); /释放空间 Accountsi = NULL; /将当前位置置空 return i; return -1; ,用户结构体指针数组 数组长度 用户号,字符串比较函数,教师：林友芳,21,2020/7/9,删除功能示例,0 x0012ff6d,0 x0012ff80,0 x0012ce00,0 x0012fe12,Accounts,0 x0012ff30,NULL,把孙悟空位置找到,把孙悟空开除: DeleteAccountByNumber(Accounts, 50, “08120100”),释放存储空间,教师：林友芳,

13、22,2020/7/9,功能实现（续）,给指定性别的群体充值，返回充值人数 int ChargeByGender(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);/妇女节发补助,教师：林友芳,23

14、,2020/7/9,方法2：链接结构,采用链式数据结构 一环扣一扣，通过一个元素保存的其它元素的地址找到其它元素。 通过链接结构实现动态数据 增加元素：在铁链的某个位置加一铁环 删除元素：去掉铁链的某一铁环 问题 铁链中的每一铁环是一样的吗？ 普通的铁链是单向的还是双向的？ 有没有一些特殊的铁链，比如有多个分叉的？ 铁链可以跟铜链拴一起吗？ 铁链的头部可以拴在柱子上吗？,教师：林友芳,24,2020/7/9,链接结构实现原理,链接结构中的元素需要保存的信息 与结点本身有关的信息 找到其它元素所需要的信息 这些信息可以组织成结构 问题：如何找到其它元素？ 保存其它元素在内存中的地址 在结构中设置

15、指针分量，用来保存其它元素的地址的分量指针分量 问题：指针的类型？ 需要指向元素的结构类型的指针类型 如果需要指向的元素与本元素的类型相同的话，则需要定义自引用的结构类型。,教师：林友芳,25,2020/7/9,链接结构,一个结构元素可以通过指针引用同类或不同类的结构元素，多个结构元素通过指针建立联系。 指向结构的指针称为链接，形成的复杂数据结构称为链接结构 最简单的链接结构 线性链接形成的表，链接表。 每个自引用结构有一个链接指针分量。,教师：林友芳,26,2020/7/9,最简单的链接结构：单向链表,单向链接表就像链条，自引用结构是链表中的一个链节，称为链表结点，结点间由指针连接形成整个结

16、构。 所有结点（结构）由动态分配创建。 从指向表首结点的指针出发，沿链接可顺序访问表中各结点。该指针代表整个表。通常把最后结点的指针置空表示结束。,教师：林友芳,27,2020/7/9,更复杂的引用链接结构,教师：林友芳,28,2020/7/9,单向链表结构示例,struct UserAccount char UserNO15; char Name20; char ID19; char Gender; double Balance; struct UserAccount *pNextUser; ;,用来保存下一个结点的地址,此处改成如下形式是否可行，为什么？ struct UserAccoun

17、t NextUser;,教师：林友芳,29,2020/7/9,普通单向链表示意图,2020/7/9,30,三、链表,教师：林友芳,31,2020/7/9,1. 需求,设有某系统的用户信息结构体，其中 用户ID长度为10 用户姓名长度不超过10 需要处理的用户数据不定， 假设某程序需要以链表方式处理用户的数据,教师：林友芳,32,2020/7/9,普通单向链表示意,教师：林友芳,33,2020/7/9,链表结点结构声明,方法1: struct UserInfoNode char szID11;/ID char szName11;/姓名 struct UserInfoNode *pNextUser

18、; /下个用户指针 ; 方法2： typedef struct UserInfoNode USERNODE, *USERPOINTER; struct UserInfoNode char szID11;/ID char szName11;/姓名 USERPOINTER *pNextUser;/下个用户指针 ;,教师：林友芳,34,2020/7/9,更好的方法：基本信息单独说明,/用户基本信息结构声明 struct UserInfo char szID11;/ID，11个字符 char szName11;/姓名，11个字符 ; 或 typedef struct char szID11;/ID，1

19、1个字符 char szName11;/姓名，11个字符 USERINFO;,教师：林友芳,35,2020/7/9,更常见合理的声明方法,方法3： struct UserLinkNode struct UserInfo Data;/数据 struct UserLinkNode *pNextUser; / ; struct UserInfo UserInfoArr100; 或 typedef struct USERINFO Data;/数据结点 struct UserLinkNode *pNextUser; / USERLINKNODE ;,教师：林友芳,36,2020/7/9,增加一个链表描述

20、信息结点,LinkInfoNode,关于链表整体描述信息结点,教师：林友芳,37,2020/7/9,描述结点结构说明示例,struct UserLink struct UserLinkNode *pHead; /头指针 struct UserLinkNode *pTail; /尾指针 int nNumber;/链表中的结点计数 ; 或 typedef struct USERLINKNODE *pHead; /头指针 USERLINKNODE *pTail; /尾指针 int nNumber;/链表中的结点计数 USERLINK;,教师：林友芳,38,2020/7/9,可以增加一个不用的头结点,

21、LinkInfoNode,目的在于写程序方便，简化一些链表操作，数据结构课程中会有进一步的阐述,不用的头结点,教师：林友芳,39,2020/7/9,关于后面的操作的假定,链表为单向链表 没有设置空的头结点 设置有信息描述结点，记录如下信息 头结点 尾结点 链表中结点个数,教师：林友芳,40,2020/7/9,在链表中增加一个节点,有几种增加方式 将新结点作为最后一个元素增加到链表的尾部， 将新结点作为第一个元素增加到链表的头部 将新结点按照某种次序要求插入到指定位置,教师：林友芳,41,2020/7/9,加到尾部,如果链表为空，则需要做一些初始化工作，将新的结点当成头结点和尾结点 如果链表不为

22、空，则将该结点作为尾结点的下一个结点，修改尾结点指针。 如果没有记录尾结点指针，则需要从头结点开始找到最后一个结点。,pHead,pTail,pNewNode,NULL,教师：林友芳,42,2020/7/9,示例代码，加到尾部,int AddUserToTail( struct UserLink *pUsers, /链表描述信息指针 struct UserLinkNode *pNewUser/新结点指针) if (pUsers = NULL | pNewUser = NULL) return -1; if (pUsers-nNumber pHead = pNewUser; pUsers-pTa

23、il = pUsers-pHead; /头尾指针指向同一个结点 else/把结点信息附到链表尾部 pUsers-pTail-pNext = pNewUser; /加到尾到 pUsers-pTail = pNewUser;/修改尾结点指针 pUsers-pTail-pNext = NULL;/最后一个结点的后继置空 pUsers-nNumber+;/计数加1 return 0; ,教师：林友芳,43,2020/7/9,加到头部,如果链表为空，则需要做一些初始化工作，将新的结点当成头结点和尾结点 如果链表不为空，需要将新结点的下一个结点置为原来的头结点，并把新结点作为头结点,pHead,pTail

24、,pNewNode,教师：林友芳,44,2020/7/9,示例代码，加到头部,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+;/计数加1 return 0; ,教师：林友芳,45,2020/7/9,在链表中插入一个新结点,基本操作 q-pNext = p-pNext; p-pNext = q; 其它用于保持链表指针完整性的操作。,功能示意,p,p,q,q,r,r,插入前,插入后,教师：林友芳,46,2020/7/9,去除链表中的某个结点,基本操作 p-pNext = q-pNext; 外