kok电子竞技

1、2022-5-111动态存储空间管理与动态存储空间管理与链表链表2022-5-112一、动态存储分配及常见函数说明隐式和显式教师：林友芳32022-5-111. 引例n要处理学生成绩，需要用数组存放。但编程时并不知道运行时需要处理多少学生成绩，每次处理的成绩项数也可能不同。nint n;n.nscanf(%d, &n);ndouble scoresn; /* 不行！*/n. /* 读入数据，然后处理 */n不能用变量说明scores大。ū匦刖蔡范ǎ。教师：林友芳42022-5-112. 问题的本质及解决方案n问题的本质n程序运行中需要使用存储，有时程序对存储的需求量在写程序时不能确定。n可

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

3、重要用途。教师：林友芳62022-5-114. 动态存储释放及存储堆n动态释放n不用的动态存储块应交还系统，动态申请的内存空间必须由程序代码以显式的方式主动释放。n动态分配、释放由动态存储管理系统完成，这是程序运行系统的子系统，管理着称作堆（英文heap）的存储区。n大部分常规语言都有这种机制。教师：林友芳72022-5-115. C语言的动态存储管理机制n用标准库函数实现用标准库函数实现nstdlib.hstdlib.hnmalloc.hmalloc.hn存储分配函数存储分配函数malloc()malloc()，原型：，原型：nvoid void * *malloc(size_t n); /

4、malloc(size_t n); /* *size_tsize_t是某整型是某整型* */ /n功能功能n分配一块不小于分配一块不小于n n的存储，返回其地址。无法的存储，返回其地址。无法满足时返回空指针值。满足时返回空指针值。82022-5-11例int n; double int n; double * *data;data;. scanf(%d, &n);. scanf(%d, &n);data=(doubledata=(double* *)malloc(n)malloc(n* *sizeof(double);sizeof(double);if (data = NULL) if (da

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

6、储分配函数calloccalloc，原型：，原型：nvoid void * *calloc(size_t n, size_t size);calloc(size_t n, size_t size);nsizesize是元素大。窃卮笮。琻 n是个数。是个数。n分配一块存储，足够存分配一块存储，足够存n n个大小为个大小为sizesize的元素，并的元素，并把元素把元素全部清全部清0 0；n无法分配时返回空指针值。前面的存储分配问题无法分配时返回空指针值。前面的存储分配问题也可用下面语句实现也可用下面语句实现ndata = (doubledata = (double* *)calloc(n,

7、 sizeof(double);)calloc(n, sizeof(double);n主要差别主要差别nmallocmalloc对所分配的区域不做任何事情，对所分配的区域不做任何事情，calloccalloc对整个区对整个区域自动清域自动清0 0。教师：林友芳112022-5-117. 空间释放函数：freen为保证动态存储的有效使用，动态分配块不再用时应释放。动态存储块的释放只能通过调用free完成。Memory leakn函数原型nvoid free(void *p);n功能nfree释放p指的存储块。n注意n该块必须是通过动态存储分配得到的，不要对并非指向动态分配块的指针用本操作np值为

8、空时什么也不做n执行free(p)后p值未变，被指块可能已变。不允许再间接访问已释放存储块教师：林友芳122022-5-118. 8. 分配调整函数分配调整函数reallocn函数原型nvoid *realloc(void *p, size_t n);n功能n更改已有分配。p指原分配块，n是新大小要求。n返回大小至少为n的存储块指针，新块与原块一致：n新块小时保存原块n范围内数据；n新块大时原数据存在，新增部分不初始化。分配成功后原块可能改变。n无法满足时返回空指针，原块不变。n常用写法(防止分配失败导致原存储块丢失) ：nq = (double*)realloc(p, m * sizeof(

9、double);nif (q = NULL) /*未成功，p仍指原块，特殊处理*/ nelse p = q; /* 令p指向新块，正常处理 */ .2022-5-1113二、动态存储空间管理如果动态申请了许多同类型缓冲区，该如何管理？教师：林友芳142022-5-11方法1：指针数组（地址数组）n设置一段内存空间，例如数组，用来保存存储空间的起始地址。n数组中每个元素用来保存某种类型的存储空间的地址，等于每个元素都是一个指针变量。nint *pnarr10; /定义一个长度为10的整型指针数组（整型地址数组）nchar *psz5; /定义一个长度为5的字符指针数组。0 x0012ff7d0

10、x0012ff800 x0012fe12其中每个元素都用来保存某种类型的存储空间的地址教师：林友芳152022-5-11例如n设一个班最多有50人，但每个班的人数不定，为了表示这50用户，可以定义如下指针数组nstruct UserAccount *Accounts 50;n完成如下功能n初始化指针数组n将新生成的某个班用户加入班级用户集，并存放在空位置上。n将某个班指定用户号的用户删除n给某个班所有女生发m元补助n将新生成的某个班用户插入到指定位置i上，i后面的用户顺序往后退。教师：林友芳162022-5-11指针数组结构示例0 x0012ff6dNULL0 x0012ff800 x0012

11、ce000 x0012fe1208120001 张帅帅110108M0.1008120099 李美美350108F500.0008120002 赵小飞360108M20.0008120007 罗小花410108F88.200 x0012ff6d0 x0012ff800 x0012ce000 x0012fe12长度为50空指针，可能曾被删除后续元素或空或不空Accounts教师：林友芳172022-5-11功能实现n初始化指针数组void InitAccounts(struct UserAccount *Accounts, int nLen) for (int i = 0; i nLen; i+

12、) Accountsi = NULL;n寻找一个空位置返回，-1表示无空位置int FindEmptyPlace(struct UserAccount *Accounts, int nLen) /可以有不同的搜索策略NULLNULL教师：林友芳182022-5-11功能实现（续）n将新用户放在空位置上，不成功返回-1，成功返回位置号int AddNewAccountAtAnyEmptyPlace(struct UserAccount *Accounts, int nLen, struct UserAccount *pUser) int nPlace;if (nPlace = FindEmpty

13、Place(Accounts, nLen) = -1) return -1; AccountsnPlace = pUser; /完成放置操作 return nPlace; /返回位置教师：林友芳192022-5-11功能示例0 x0012ff6dNULL0 x0012ff800 x0012ce000 x0012fe1208120001 张帅帅110108M0.1008120099 李美美350108F500.0008120002 赵小飞360108M20.0008120007 罗小花410108F88.200 x0012ff6d0 x0012ff800 x0012ce000 x0012fe12

14、长度为50Accounts08120100 孙悟空110105M600.100 x0012ff300 x0012ff30新找到的空位新结点孙悟空报到教师：林友芳202022-5-11功能实现（续）n将指定用户号的用户删除，返回该用户原来所在位置int DeleteAccountByNumber(struct UserAccount *Accounts, int nLen, char *pszUserNO) int i; for (i = 0; i szUserNO) = 0) free(Accountsi); /释放空间 Accountsi = NULL; /将当前位置置空 return i;

15、 return -1;用户结构体指针数组数组长度用户号字符串比较函数教师：林友芳212022-5-11删除功能示例0 x0012ff6d0 x0012ff300 x0012ff800 x0012ce000 x0012fe1208120001 张帅帅110108M0.1008120099 李美美350108F500.0008120002 赵小飞360108M20.0008120007 罗小花410108F88.200 x0012ff6d0 x0012ff800 x0012ce000 x0012fe12Accounts08120100 孙悟空110105M600.100 x0012ff30NULL

16、把孙悟空位置找到把孙悟空开除:DeleteAccountByNumber(Accounts, 50, “08120100”)释放存储空间教师：林友芳222022-5-11功能实现（续）n给指定性别的群体充值，返回充值人数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+;

17、return nCounter;ChargeByGender(Accounts, 50, F, 10.0);/妇女节发补助教师：林友芳232022-5-11方法2：链接结构n采用链式数据结构n一环扣一扣，通过一个元素保存的其它元素的地址找到其它元素。n通过链接结构实现动态数据n增加元素：在铁链的某个位置加一铁环n删除元素：去掉铁链的某一铁环n问题n铁链中的每一铁环是一样的吗？n普通的铁链是单向的还是双向的？n有没有一些特殊的铁链，比如有多个分叉的？n铁链可以跟铜链拴一起吗？n铁链的头部可以拴在柱子上吗？教师：林友芳242022-5-11链接结构实现原理n链接结构中的元素需要保存的信息n与结点本

18、身有关的信息n找到其它元素所需要的信息n这些信息可以组织成结构n问题：如何找到其它元素？n保存其它元素在内存中的地址n在结构中设置指针分量，用来保存其它元素的地址的分量指针分量n问题：指针的类型？n需要指向元素的结构类型的指针类型n如果需要指向的元素与本元素的类型相同的话，则需要定义自引用的结构类型。教师：林友芳252022-5-11链接结构n一个结构元素可以通过指针引用同类或不同类的结构元素，多个结构元素通过指针建立联系。n指向结构的指针称为链接，形成的复杂数据结构称为链接结构n最简单的链接结构n线性链接形成的表，链接表。n每个自引用结构有一个链接指针分量。教师：林友芳262022-5-11

19、最简单的链接结构：单向链表n单向链接表就像链条，自引用结构是链表中的一个链节，称为链表结点，结点间由指针连接形成整个结构。n所有结点（结构）由动态分配创建。n从指向表首结点的指针出发，沿链接可顺序访问表中各结点。该指针代表整个表。通常把最后结点的指针置空表示结束。0教师：林友芳272022-5-1100000000更复杂的引用链接结构教师：林友芳282022-5-11单向链表结构示例struct UserAccount char UserNO15; char Name20; char ID19; char Gender; double Balance;struct UserAccount *p

20、NextUser;用来保存下一个结点的地址此处改成如下形式是否可行，为什么？struct UserAccount NextUser;教师：林友芳292022-5-11普通单向链表示意图08120001 张帅帅110108M0.1008120002 赵小飞360108M20.0008120007 罗小花410108F88.2008120099 李美美350108F500.00NULLHeadTail2022-5-1130三、链表教师：林友芳312022-5-111. 需求n设有某系统的用户信息结构体，其中n用户ID长度为10n用户姓名长度不超过10n需要处理的用户数据不定，n假设某程序需要以链表

21、方式处理用户的数据教师：林友芳322022-5-11普通单向链表示意DataDataDataDataNULLHeadTail教师：林友芳332022-5-11链表结点结构声明方法1:struct UserInfoNodechar szID11;/IDchar szName11;/姓名 struct UserInfoNode *pNextUser; /下个用户指针;方法2：typedef struct UserInfoNode USERNODE, *USERPOINTER;struct UserInfoNodechar szID11;/IDchar szName11;/姓名 USERPOINTE

22、R *pNextUser;/下个用户指针;教师：林友芳342022-5-11更好的方法：基本信息单独说明/用户基本信息结构声明struct UserInfostruct UserInfo char szID11;char szID11;/ID/ID，1111个字符个字符char szName11;char szName11;/姓名，姓名，1111个字符个字符;或typedef structtypedef struct char szID11;char szID11;/ID/ID，1111个字符个字符char szName11;char szName11;/姓名，姓名，1111个字符个字符 US

23、ERINFO; USERINFO;教师：林友芳352022-5-11更常见合理的声明方法方法3：struct UserLinkNodestruct UserLinkNode struct UserInfo Data; struct UserInfo Data;/数据数据 struct UserLinkNode struct UserLinkNode * *pNextUser; /pNextUser; /;struct UserInfo UserInfoArr100;struct UserInfo UserInfoArr100;或typedef structtypedef struct USER

24、INFO Data; USERINFO Data;/数据结点数据结点 struct UserLinkNode struct UserLinkNode * *pNextUser; /pNextUser; / USERLINKNODE ; USERLINKNODE ;教师：林友芳362022-5-11增加一个链表描述信息结点NumberHeadTailDataDataDataDataNULLLinkInfoNoden关于链表整体描述信息结点教师：林友芳372022-5-11描述结点结构说明示例struct UserLinkstruct UserLink struct UserLinkNode st

25、ruct UserLinkNode * *pHead; /pHead; /头指针头指针 struct UserLinkNode struct UserLinkNode * *pTail; /pTail; /尾指针尾指针int nNumber;int nNumber;/链表中的结点计数链表中的结点计数;或typedef structtypedef struct USERLINKNODE USERLINKNODE * *pHead; /pHead; /头指针头指针 USERLINKNODE USERLINKNODE * *pTail; /pTail; /尾指针尾指针int nNumber;int

26、nNumber;/链表中的结点计数链表中的结点计数 USERLINK; USERLINK;教师：林友芳382022-5-11可以增加一个不用的头结点NumberHeadTailDataDataDataNULLLinkInfoNoden目的在于写程序方便，简化一些链表操作，数据结构课程中会有进一步的阐述不用的不用的头结点头结点教师：林友芳392022-5-11关于后面的操作的假定n链表为单向链表n没有设置空的头结点n设置有信息描述结点，记录如下信息n头结点n尾结点n链表中结点个数教师：林友芳402022-5-11在链表中增加一个节点n有几种增加方式n将新结点作为最后一个元素增加到链表的尾部，n将

27、新结点作为第一个元素增加到链表的头部n将新结点按照某种次序要求插入到指定位置教师：林友芳412022-5-11加到尾部n如果链表为空，则需要做一些初始化工作，将新的结点当成头结点和尾结点n如果链表不为空，则将该结点作为尾结点的下一个结点，修改尾结点指针。n如果没有记录尾结点指针，则需要从头结点开始找到最后一个结点。pHeadpTailDataDataNULLpNewNode NULL 教师：林友芳422022-5-11示例代码，加到尾部int AddUserToTail( struct UserLink *pUsers, /链表描述信息指针 struct UserLinkNode *pNewU

28、ser/新结点指针) 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;教师：林友芳43

29、2022-5-11加到头部n如果链表为空，则需要做一些初始化工作，将新的结点当成头结点和尾结点n如果链表不为空，需要将新结点的下一个结点置为原来的头结点，并把新结点作为头结点pHeadpTailDataDataNULLNULLpNewNode 教师：林友芳442022-5-11示例代码，加到头部int AddUserToHead( struct UserLink *pUsers, /链表描述信息指针 struct UserLinkNode *pNewUser/新结点指针) if (pUsers = NULL | pNewUser = NULL) return -1;if (pUsers-nNu

30、mber pHead = pNewUser; pUsers-pTail = pUsers-pHead; /头尾指针指向同一个结点 pNewUser-pNext = NULL; else/把结点信息附到链表头部 pUsers-pNewUser-pNext = pUsers-pHead ; /加到头部 pUsers-pHead = pNewUser;/修改头结点指针 pUsers-nNumber+;/计数加1return 0;教师：林友芳452022-5-11在链表中插入一个新结点n基本操作nq-pNext = p-pNext;np-pNext = q;n其它用于保持链表指针完整性的操作。功能示意

31、ppqqrr插入前插入后教师：林友芳462022-5-11去除链表中的某个结点n基本操作np-pNext = q-pNext;n外围附加操作，用于保证链表的各种指针的完整性，如头指针，尾指针等。n如：如果删除的是最后一个结点的话，需要修改尾指针功能示意pqrprq教师：林友芳472022-5-11遍历链表n常见功能n遍历链表逐个访问所有结点，进行相应的处理，如将所有用户的某项指标求和，输出所有用户的信息n查找某个或某些符合给定条件的结点，进行相应处理n教师：林友芳482022-5-11示例代码: 输出所有元素int ShowData(struct UserLink *pUsers)struct

32、 UserLinkNode *pNode;if (pUsers-nNumber pHead; /从第一个元素开始 pNode != NULL; /判断当前结点是否为空pNode = pNode-pNext /准备处理下一个结点 ) /对每个结点出输出信息printf( %11st%11stn,pNode-Data.szID,pNode-Data.szName,return 0;教师：林友芳492022-5-11参数改成头结点int ShowData(struct UserLinkNode *pHead) /给出头结点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-5-11本章内容n动态存储分配及其函数n动态存储空间管理方法n链表概念n链表的定义和基本操作2022-5-1151本章结束