C程序设计课件第十二章.ppt

第十二章 动态数据结构;考虑上一章的职工卡片问题，用计算机管理这些卡片, 要把卡片保存在计算机内。 首先，用什么数据结构存储：一张卡片是一个结构体，所有卡片自然用结构体数组。 第三，操作问题： 若增加一个人，应该在数组中加一个元素，会产生数组不够大的可能。 若增加一张卡片在数组中间，应该把加入位置以后的其它元素依次向后移动。 若在中间删除一张卡片，会在数组中间留下一个“洞”，应该把“洞”以后的元素依次向前移动 ;使用数组带来的问题是： 操作不方便； 数组尺寸不好确定。 第二，数组多大：为保存全部卡片，并且人数不固定，就应该给一个足够大的数组。 最好把这些卡片存储成动态的， 需要多大存储量（有多少张卡片）就用多大。 中间加一张卡片时不要向后串别的卡片， 删除一张卡片时不要留下“洞”。; 如图的链式结构可以满足要求: 当增加一张卡片时，只需要向计算机系统申请一块空间，联到链的适当位置上。例如，要增加一张卡片 50 插入到 2 、3 之间，则只需要如下修改指针： 若删除一节，只需要将其从链上摘下来即可。例删除2节得 链上已经没有2节了，删掉的节所占的存储空间还可以还回计算机系统，以便作其它用途。;这就是一种动态数据结构中的——链表。动态数据结构上的一项是一个动态变量，指针是标识动态变量的有力手段。动态变量与静态变量的区别在于: 静态变量是程序中由程序员“显式”说明的变量。它有一个名字，在编译时，编译程序已经给它分配存储空间。这块存储空间用变量的名字来标识。;动态变量在程序中没有“显式”说明，它没有名字 在编译时编译程序不知道有该变量，不给（也不可能给）它分配空间。 动态变量是在程序运行时 随程序存储数据的需要，申请空间函数（例如malloc，当然也是由程序员安排的）随机的动态的申请来的空间。它没有名字，一般动态变量都由指针标识。 当使用完毕后，由释放空间函数（例如free）释放，还回计算机存储管理系统，以备它用。; 注意：这里所说的静态变量不是C语言中由静态存储类别static声明的变量；动态变量也不是C语言中由自动存储类别auto声明的变量。而是一般程序设计概念中的静态变量、动态变量;管理动态变量;目标代码空间;sizeof 运算符 单目运算符 sizeof 的 操作数是类型。 运算结果是求得相应类型的尺寸，即存储相应类型数据所需要的字节数。 sizeof(int) /* 结果是2 */ sizeof(char) /* 结果是1 */ sizeof(struct date) /* 若 struct date 是第十一章定义的日期类型，结果是6 */;malloc 函数: 原型 void *malloc(unsigned long size); 功能 申请足够大内存区域用来存储长度为size的数据对象，返回该区域的首指针，并保证该区域符合任何数据类型对存储区域开始地址和对齐的要求。 返回指针是void类型的，调用者必须使用显示强制类型转换，把该指针转换成所需要类型的指针。;例: float *p ; p = (float*)malloc( sizeof(float) ); struct date *pdate; pdate=(struct date*)malloc(sizeof(struct date));;free函数 动态申请的内存如果不再使用，应当适时释放这样可以提高程序运行效率。free函数用来释放经过malloc申请的动态空间。free的函数 原型 void free ( void *ptr ) ; 功能释放由malloc申请的内存区域。free的参数ptr是一个指针，指向以前由malloc申请的一个内存区域。;例 申请 float *p ; p = (float*)malloc( sizeof(float) ); struct date *pdate; pdate=(struct date*)malloc(sizeof(struct date)); 释放 free(p); free(pdate); ;free(ptr)  /* 释放ptr所指向由malloc申请的内存空间 */ 一块存储区域一经释放，便不能再使用。使用free特别注意，操作不当会产生不可预料的结果。如下情况下使用free都会造成灾难性后果。 ptr无值； ptr的值为NULL； ptr所指向的空间不是经过malloc申请来的； 对一次申请的存储区进行多次释放（实际可能是ptr无值或值为NULL）。;实用问题: 若指针变量指向的用malloc申请来的动态变量，是孤立的不能与其它变量相联系，显然作用不大。 引进动态变量的目的