第11章 动态数据结构

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

1、第11章动态数据结构第11章动态数据结构°本章开始介绍动态数据结构，主要介绍链表结构的建立、在链表中查找指定元素、插入一个新元素、删除一个元素等操作。学完本章内容后，要求深刻理解动态存储结构的概念，并正确运用。11.1从静态数据结构到动态数据结构°在此之前，我们涉及到的都是静态数据结构，像数组、简单类型(int、float)等。静态数据结构的特点是由系统分配固定大小的存储空间，以后在程序运行的过程中，存储空间的位置和容量都不会再改变。而实际生活中常常有这样的问题，数据量的多少是动态变化的。11.1从静态数据结构到动态数据结构°例如，图书馆的藏书量，在图书馆初建时，假设有10000本，随着时间

2、的推移，藏书的数量必定要增加。有人可能会想，在定义一个静态变量时，预留出一部分空间，但这也会引起一些问题，首先多出的那部分空间不知何时才能使用，在没有被使用之前一直被闲置；其次，谁又能保证增加的空间就足够呢？11.1从静态数据结构到动态数据结构°动态数据结构不确定总的数据存储量，而是为现有的每一个数据元素定义一个确定的初始大小的空间，若干个数据元素分配若干个同样大小的空间；当问题的数据量发生变化时，数据的存储空间的大小也发生变化。如果数据量增加，就重新向系统申请新的空间；如果数据量减少，就将现有的多余的空间归还给系统。11.2.动态内存分配°使用计算机解决问题的所有方法都是通过使用系统提供给

3、我们的基本命令或函数来实现的。所以首先让我们来看看，c的标准函数中有哪些是用于动态内存分配的，怎样使用。11.2.1ANSIC中动态内存操作标准函数°ANSIC中提供了若干个动态内存操作标准函数，它们的名称分别是malloc、calloc、realloc、free等。这些函数可以使用在任何的C环境中。1．malloc函数°malloc函数是C的标准函数之一。原型定义在malloc.h文件中。°原型为：°void*malloc(unsignedintsize);°其作用是向系统申请一个确定大小(size个字节)的存储空间，返回值为一个指向void类型的分配域起始地址的指针值。如果此函数操作失败

4、，返回值为空。1．malloc函数使用格式：指针型变量=(基类型*)malloc(需要的存储空间的字节数);例11.1：为一个整数分配存储空间，需要的语句为：在文件的头部：#include在说明部分：int*p;在程序中：p=(int*)malloc(sizeof(int));求字节长度运算符测试malloc的程序举例：#include#include#includevoidmain(){int*p;/*定义一个指向整型的指针变量*/intx;p=(int*)malloc(sizeof(int));if(!p)ex

5、it(0);p=&x;scanf(“%d”,p);printf(“x=%d”,x);}2．calloc函数°calloc函数是C的标准函数之一。原型定义在malloc.h文件中。°原型为：°void*calloc(unsignedintn,unsignedintsize);°其作用是向系统申请n个大小为size个字节的连续存储空间，返回值为一个指向void类型的分配域起始地址的指针值。°如果此函数操作失败，返回值为空。可以为一维数组开辟一片连续的动态存储空间。2．calloc函数°使用格式：指针型变量=(数组元素类型*)calloc(n,每一个数组元素的存储空间的字节数)；°例11.2：为一

6、个有10个整数的一维数组分配存储空间，需要的语句为：在文件的头部：#include在说明部分：int*p;在程序中：p=(int*)calloc(10,sizeof(int));使用calloc函数程序举例：#include#include#includevoidmain(){int*p;intx;p=(int*)calloc(10,sizeof(int));if(!p)exit(0);for(i=0;i<10;i++){scanf(“%d”,&x);*(p+i)=x;}for(i=0;i<10;i++)print

7、f(“%6d”,*(p+i));}3．realloc函数°realloc函数是C的标准函数之一。原型定义在malloc.h文件中。°原型为：°void*realloc(void*p,unsignedintsize);°其作用是向系统重新申请一个确定大小的存储空间，并将原存储空间中的数据值传送到新的地址空间的低端，返回值为一个指向void类型的分配域起始地址的指针值。如果此函数操作失败，返回值为空。原存储空间的