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

1、第十七 章动态存储空间管理与链表.一、动态存储分配及常见函数阐明隐式和显式.1. 引例要处置学生成果，需求用数组存放。但编程时并不知道运转时需求处置多少学生成果，每次处置的成果项数也能够不同。int n;.scanf(%d, &n);double scoresn; /* 不行！*/. /* 读入数据，然后处置 */不能用变量阐明scores大小必需静态确定。.2. 问题的本质及处理方案问题的本质程序运转中需求运用存储，有时程序对存储的需求量在写程序时不能确定。能够处理方案1分析问题，定义适当大小的数组。假设分析正确，普通都能处置。但数据很多时程序就不能用。2定义尽能够大的数组以满足任何需求。浪

2、费大量存储资源。如有多个这种数组就更难办。系统能够无法包容几个大数组，但实践上它们并不同时需求很大空间。处理的方法是“动态存储分配。在程序运转中做存储分配任务。.3. 动态存储分配动态存储分配根据运转中的需求分配存储，获得存储块运用，称为动态存储分配。在运转中根据需求动态进展。动态存储块具有起始地址，地址可以存储在指针里，因此可以借助于指针保管存储空间地址。用指针指向存储块，间接运用被指存储。访问动态分配存储是指针的最重要用途。.4. 动态存储释放及存储堆动态释放不用的动态存储块应交还系统，动态恳求的内存空间必需由程序代码以显式的方式自动释放。动态分配、释放由动态存储管理系统完成，这是程序运转

3、系统的子系统，管理着称作堆英文heap的存储区。大部分常规言语都有这种机制。.5. C言语的动态存储管理机制用规范库函数实现stdlib.hmalloc.h存储分配函数malloc()，原型：void *malloc(size_t n); /*size_t是某整型*/功能分配一块不小于n的存储，前往其地址。无法满足时前往空指针值。.例int n; double *data;. scanf(%d, &n);data=(double*)malloc(n*sizeof(double);if (data = NULL) . /* 分配未完成时的处置 */ .datai.*(data+j)./*正常处置

4、*/.malloc阐明malloc运用本卷须知：的前往值void*应经过类型强迫转为特定指针类型后赋给指针变量。分配存储块大小应该用sizeof计算动态分配必需检查胜利与否动态分配的块大小也是确定的。越界运用尤其是越界赋值是严重错误，能够导致程序或系统垮台.6. calloc带计数和清0的存储分配函数calloc，原型：void *calloc(size_t n, size_t size);size是元素大小，n是个数。分配一块存储，足够存n个大小为size的元素，并把元素全部清0；无法分配时前往空指针值。前面的存储分配问题也可用下面语句实现data = (double*)calloc(n,

5、sizeof(double);主要差别malloc对所分配的区域不做任何事情，calloc对整个区域自动清0。.7. 空间释放函数：free为保证动态存储的有效运用，动态分配块不再用时应释放。动态存储块的释放只能经过调用free完成。Memory leak函数原型void free(void *p);功能free释放p指的存储块。留意该块必需是经过动态存储分配得到的，不要对并非指向动态分配块的指针用本操作p值为空时什么也不做执行free(p)后p值未变，被指块能够已变。不允许再间接访问已释放存储块.8. 分配调整函数realloc函数原型void *realloc(void *p, size_

6、t n);功能更改已有分配。p指原分配块，n是新大小要求。前往大小至少为n的存储块指针，新块与原块一致：新块小时保管原块n范围内数据；新块大时原数据存在，新增部分不初始化。分配胜利后原块能够改动。无法满足时前往空指针，原块不变。常用写法(防止分配失败导致原存储块丧失) ：q = (double*)realloc(p, m * sizeof(double);if (q = NULL) /*未胜利，p仍指原块，特殊处置*/ else p = q; /* 令p指向新块，正常处置 */ .二、动态存储空间管理假设动态恳求了许多同类型缓冲区，该如何管理？.方法1：指针数组地址数组设置一段内存空间，例如数

7、组，用来保管存储空间的起始地址。数组中每个元素用来保管某种类型的存储空间的地址，等于每个元素都是一个指针变量。int *pnarr10; /定义一个长度为10的整型指针数组整型地址数组char *psz5; /定义一个长度为5的字符指针数组。0 x0012ff7d0 x0012ff800 x0012fe12其中每个元素都用来保管某种类型的存储空间的地址.例如设一个班最多有50人，但每个班的人数不定，为了表示这50用户，可以定义如下指针数组struct UserAccount *Accounts 50;完成如下功能初始化指针数组将新生成的某个班用户参与班级用户集，并存放在空位置上。将某个班指定用

8、户号的用户删除给某个班一切女生发m元补助将新生成的某个班用户插入到指定位置i上，i后面的用户顺序往后退。.指针数组构造例如0 x0012ff6dNULL0 x0012ff800 x0012ce000 x0012fe1208120001 张帅帅110108M0.1008120099 李美美350108F500.0008120002 赵小飞360108M20.0008120007 罗小花410108F88.200 x0012ff6d0 x0012ff800 x0012ce000 x0012fe12长度为50空指针，能够曾被删除后续元素或空或不空Accounts.功能实现初始化指针数组void In

9、itAccounts(struct UserAccount *Accounts, int nLen) for (int i = 0; i nLen; i+) Accountsi = NULL;寻觅一个空位置前往，-1表示无空位置int FindEmptyPlace(struct UserAccount *Accounts, int nLen) /可以有不同的搜索战略NULLNULL.功能实现续将新用户放在空位置上，不胜利前往-1，胜利前往位置号int AddNewAccountAtAnyEmptyPlace(struct UserAccount *Accounts, int nLen, str

10、uct UserAccount *pUser) int nPlace;if (nPlace = FindEmptyPlace(Accounts, nLen) = -1) return -1; AccountsnPlace = pUser; /完成放置操作 return nPlace; /前往位置.功能例如0 x0012ff6dNULL0 x0012ff800 x0012ce000 x0012fe1208120001 张帅帅110108M0.1008120099 李美美350108F500.0008120002 赵小飞360108M20.0008120007 罗小花410108F88.200 x

11、0012ff6d0 x0012ff800 x0012ce000 x0012fe12长度为50Accounts08120100 孙悟空110105M600.100 x0012ff300 x0012ff30新找到的空位新结点孙悟空报到.功能实现续将指定用户号的用户删除，前往该用户原来所在位置int DeleteAccountByNumber(struct UserAccount *Accounts, int nLen, char *pszUserNO) int i; for (i = 0; i szUserNO) = 0) free(Accountsi); /释放空间 Accountsi = NU

12、LL; /将当前位置置空 return i; return -1;用户构造体指针数组数组长度用户号字符串比较函数.删除功能例如0 x0012ff6d0 x0012ff300 x0012ff800 x0012ce000 x0012fe1208120001 张帅帅110108M0.1008120099 李美美350108F500.0008120002 赵小飞360108M20.0008120007 罗小花410108F88.200 x0012ff6d0 x0012ff800 x0012ce000 x0012fe12Accounts08120100 孙悟空110105M600.100 x0012ff

13、30NULL把孙悟空位置找到把孙悟空开除:DeleteAccountByNumber(Accounts, 50, “08120210)释放存储空间.功能实现续给指定性别的群体充值，前往充值人数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 nCounte

14、r;ChargeByGender(Accounts, 50, F, 10.0);/妇女节发补助.方法2：链接构造采用链式数据构造一环扣一扣，经过一个元素保管的其它元素的地址找到其它元素。经过链接构造实现动态数据添加元素：在铁链的某个位置加一铁环删除元素：去掉铁链的某一铁环问题铁链中的每一铁环是一样的吗？普通的铁链是单向的还是双向的？有没有一些特殊的铁链，比如有多个分叉的？铁链可以跟铜链拴一同吗？铁链的头部可以拴在柱子上吗？.链接构造实现原理链接构造中的元素需求保管的信息与结点本身有关的信息找到其它元素所需求的信息这些信息可以组织成构造问题：如何找到其它元素？保管其它元素在内存中的地址在构造中设

15、置指针分量，用来保管其它元素的地址的分量指针分量问题：指针的类型？需求指向元素的构造类型的指针类型假设需求指向的元素与本元素的类型一样的话，那么需求定义自援用的构造类型。.链接构造一个构造元素可以经过指针援用同类或不同类的构造元素，多个构造元素经过指针建立联络。指向构造的指针称为链接，构成的复杂数据构造称为链接构造最简单的链接构造线性链接构成的表，链接表。每个自援用构造有一个链接指针分量。.最简单的链接构造：单向链表单向链接表就像链条，自援用构造是链表中的一个链节，称为链表结点，结点间由指针衔接构成整个构造。一切结点构造由动态分配创建。从指向表首结点的指针出发，沿链接可顺序访问表中各结点。该指

16、针代表整个表。通常把最后结点的指针置空表示终了。.更复杂的援用链接构造.单向链表构造例如struct UserAccount char UserNO15; char Name20; char ID19; char Gender; double Balance;struct UserAccount *pNextUser;用来保管下一个结点的地址此处改成如下方式能否可行，为什么？struct UserAccount NextUser;.普通单向链表表示图08120001 张帅帅110108M0.1008120002 赵小飞360108M20.0008120007 罗小花410108F88.2008

17、120099 李美美350108F500.00NULLHeadTail.三、链表.1. 需求设有某系统的用户信息构造体，其中用户ID长度为10用户姓名长度不超越10需求处置的用户数据不定，假设某程序需求以链表方式处置用户的数据.普通单向链表表示DataDataDataDataNULLHeadTail.链表结点构造声明方法1:struct UserInfoNodechar szID11;/IDchar szName11;/姓名 struct UserInfoNode *pNextUser; /下个用户指针;方法2：typedef struct UserInfoNode USERNODE, *US

18、ERPOINTER;struct UserInfoNodechar szID11;/IDchar szName11;/姓名 USERPOINTER *pNextUser;/下个用户指针;.更好的方法：根本信息单独阐明/用户根本信息构造声明struct UserInfochar szID11;/ID，11个字符char szName11;/姓名，11个字符;或typedef structchar szID11;/ID，11个字符char szName11;/姓名，11个字符 USERINFO;.更常见合理的声明方法方法3：struct UserLinkNode struct UserInfo D

19、ata;/数据 struct UserLinkNode *pNextUser; /;struct UserInfo UserInfoArr100;或typedef struct USERINFO Data;/数据结点 struct UserLinkNode *pNextUser; / USERLINKNODE ;.添加一个链表描画信息结点NumberHeadTailDataDataDataDataNULLLinkInfoNode关于链表整体描画信息结点.描画结点构造阐明例如struct UserLinkstruct UserLinkNode *pHead; /头指针 struct UserLi

20、nkNode *pTail; /尾指针int nNumber;/链表中的结点计数;或typedef struct USERLINKNODE *pHead; /头指针 USERLINKNODE *pTail; /尾指针int nNumber;/链表中的结点计数 USERLINK;.可以添加一个不用的头结点NumberHeadTailDataDataDataNULLLinkInfoNode目的在于写程序方便，简化一些链表操作，数据构造课程中会有进一步的论述不用的头结点.关于后面的操作的假定链表为单向链表没有设置空的头结点设置有信息描画结点，记录如下信息头结点尾结点链表中结点个数.在链表中添加一个节

21、点有几种添加方式将新结点作为最后一个元素添加到链表的尾部，将新结点作为第一个元素添加到链表的头部将新结点按照某种次序要求插入到指定位置.加到尾部假设链表为空，那么需求做一些初始化任务，将新的结点当成头结点和尾结点假设链表不为空，那么将该结点作为尾结点的下一个结点，修正尾结点指针。假设没有记录尾结点指针，那么需求从头结点开场找到最后一个结点。pHeadpTailDataDataNULLpNewNode NULL.例如代码，加到尾部int AddUserToTail( struct UserLink *pUsers, /链表描画信息指针 struct UserLinkNode *pNewUser/

22、新结点指针) 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;.加到头部假设链表为空，

23、那么需求做一些初始化任务，将新的结点当成头结点和尾结点假设链表不为空，需求将新结点的下一个结点置为原来的头结点，并把新结点作为头结点pHeadpTailDataDataNULLNULLpNewNode .例如代码，加到头部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;.在链表中插入一个新结点根本操作q-pNext = p-pNe