c程序设计课件卖第12章.ppt

第十二章 动态数据结构 管理动态变量 动态数据结构 栈 ── stack 队列 ── queue 链表——linkage table 树——tree 图—— graph 程序设计实例 本章小结 作业 考虑上一章的职工卡片问题，用计算机管理这些卡片, 要把卡片保存在计算机内。 首先，用什么数据结构存储：一张卡片是一个结构体，所有卡片自然用结构体数组。 第三，操作问题： 若增加一个人，应该在数组中加一个元素，会产生数组不够大的可能。 若增加一张卡片在数组中间，应该把加入位置以后的其它元素依次向后移动。 若在中间删除一张卡片，会在数组中间留下一个“洞”，应该把“洞”以后的元素依次向前移动 使用数组带来的问题是： 操作不方便； 数组尺寸不好确定。 第二，数组多大：为保存全部卡片，并且人数不固定，就应该给一个足够大的数组。 最好把这些卡片存储成动态的， 需要多大存储量（有多少张卡片）就用多大。 中间加一张卡片时不要向后串别的卡片， 删除一张卡片时不要留下“洞”。 这就是一种动态数据结构中的——链表。动态数据结构上的一项是一个动态变量，指针是标识动态变量的有力手段。动态变量与静态变量的区别在于: 静态变量是程序中由程序员“显式”说明的变量。它有一个名字，在编译时，编译程序已经给它分配存储空间。这块存储空间用变量的名字来标识。 动态变量在程序中没有“显式”说明，它没有名字 在编译时编译程序不知道有该变量，不给（也不可能给）它分配空间。 动态变量是在程序运行时 随程序存储数据的需要，申请空间函数（例如malloc，当然也是由程序员安排的）随机的动态的申请来的空间。它没有名字，一般动态变量都由指针标识。 当使用完毕后，由释放空间函数（例如free）释放，还回计算机存储管理系统，以备它用。 注意：这里所说的静态变量不是C语言中由静态存储类别static声明的变量；动态变量也不是C语言中由自动存储类别auto声明的变量。而是一般程序设计概念中的静态变量、动态变量 管理动态变量 动态变量在程序运行时，随程序存储数据的需要，向计算机系统申请；使用完后还回计算机系统。 本节介绍 申请计算机存储空间函数malloc 释放存储空间函数free 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申请来的动态变量，是孤立的不能与其它变量相联系，显然作用不大。 引