ch12-动态数据结构

《ch12-动态数据结构》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十二章动态数据结构动态变量动态数据结构栈──stack队列──queue链表——linkagetable树——tree图——graph程序设计实例本章小结作业考虑上一章的职工卡片问题，用计算机管理这些卡片,要把卡片保存在计算机内。首先，用什么数据结构存储：一张卡片是一个结构体，所有卡片自然用结构体数组。第三，操作问题：若增加一个人，应该在数组中加一个元素，会产生数组不够大的可能。若增加一张卡片在数组中间，应该把加入位置以后的其它元素依次向后移动。若在中间删除一张卡片，会在数组中间留下一个“洞”，应该把“洞”以后的元素依次向前移动使用数组带

2、来的问题是：操作不方便；数组尺寸不好确定。第二，数组多大：为保存全部卡片，并且人数不固定，就应该给一个足够大的数组。最好把这些卡片存储成动态的，需要多大存储量（有多少张卡片）就用多大。中间加一张卡片时不要向后串别的卡片，删除一张卡片时不要留下“洞”。如图的链式结构可以满足要求:当增加一张卡片时，只需要向计算机系统申请一块空间，联到链的适当位置上。例如，要增加一张卡片50插入到2、3之间，则只需要如下修改指针：若删除一节，只需要将其从链上摘下来即可。例删除2节得链上已经没有2节了，删掉的节所占的存储空间还可以还回计算机系统，以便作其它用途。1

3、23…n.50这就是一种动态数据结构中的——链表。动态数据结构上的一项是一个动态变量，指针是标识动态变量的有力手段。动态变量与静态变量的区别在于:静态变量是程序中由程序员“显式”说明的变量。它有一个名字，在编译时，编译程序已经给它分配存储空间。这块存储空间用变量的名字来标识。动态变量在程序中没有“显式”说明，它没有名字在编译时编译程序不知道有该变量，不给（也不可能给）它分配空间。动态变量是在程序运行时随程序存储数据的需要，申请空间函数（例如malloc，当然也是由程序员安排的）随机的动态的申请来的空间。它没有名字，一般动态变量都由指针标识。

4、当使用完毕后，由释放空间函数（例如free）释放，还回计算机存储管理系统，以备它用。注意：这里所说的静态变量不是C语言中由静态存储类别static声明的变量；动态变量也不是C语言中由自动存储类别auto声明的变量。而是一般程序设计概念中的静态变量、动态变量管理动态变量动态变量在程序运行时，随程序存储数据的需要，向计算机系统申请；使用完后还回计算机系统。本节介绍申请计算机存储空间函数malloc释放存储空间函数free目标代码空间静态区空间库代码空间堆区空间栈区空间内存程序运行时，涉及用户程序的内存存储结构如右图所示，首先是目标代码区；然后是

5、静态存储区，用于存放那些可用绝对地址标识的，主要是具有静态存储类别的数据和变量；接着是目标代码运行时用到的库程序代码区；最后剩余空间是栈区和堆区，栈区和堆区从剩余空间的两端，动态的向中间增长。栈区用来存储程序中声明的函数的局部变量等具有自动存储类别的数据和变量；堆区用来存储经过动态申请空间函数申请的变量。sizeof运算符单目运算符sizeof的操作数是类型。运算结果是求得相应类型的尺寸，即存储相应类型数据所需要的字节数。sizeof(int)/*结果是2*/sizeof(char)/*结果是1*/sizeof(structdate)/*若

6、structdate是第十一章定义的日期类型，结果是6*/malloc函数:原型void*malloc(unsignedlongsize);功能申请足够大内存区域用来存储长度为size的数据对象，返回该区域的首指针，并保证该区域符合任何数据类型对存储区域开始地址和对齐的要求。返回指针是void类型的，调用者必须使用显示强制类型转换，把该指针转换成所需要类型的指针。由于要保证该区域符合任何数据类型对存储区域开始地址和对齐的要求，所以实际申请的存储区域可能大于size。例:float*p;p=(float*)malloc(sizeof(floa

7、t));free函数动态申请的内存如果不再使用，应当适时释放这样可以提高程序运行效率。free函数用来释放经过malloc申请的动态空间。free的函数原型voidfree(void*ptr);功能释放由malloc申请的内存区域。free的参数ptr是一个指针，指向以前由malloc申请的一个内存区域。free(ptr)/*释放p所指向由malloc申请的内存空间*/一块存储区域一经释放，便不能再使用。使用free特别注意，操作不当会产生不可预料的结果。如下情况下使用free都会造成灾难性后果。ptr无值；ptr的值为NULL；ptr

8、所指向的空间不是经过malloc申请来的；对一次申请的存储区进行多次释放（实际可能是ptr无值或值为NULL）。实用问题:若指针变量指向的用malloc申请来的动态变量，是孤立的