第7章C语言动态数据结构.ppt

《第7章C语言动态数据结构.ppt》由会员分享，可在线阅读，更多相关《第7章C语言动态数据结构.ppt（63页珍藏版）》请在优知文库上搜索。

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

2、藏书的数量必定要增加。有人可能会想，在定义一个静态变量时，预留出一部分空间，但这也会引起一些问题，首先多出的那部分空间不知何时才能使用，在没有被使用之前一直被闲置；其次，谁又能保证增加的空间就足够呢？7.1 从静态数据结构到动态数据结构n问题的关键在于，此问题的数据本身就是变化的，而且是不确定的变化，什么时候变、怎么变都是未知的。对这样的问题用静态存储结构来描述和存放显然捉襟见肘，存在隐患。n动态数据结构不确定总的数据存储量，而是为现有的每一个数据元素定义一个确定的初始大小的空间，若干个数据元素分配若干个同样大小的空间；当问题的数据量发生变化时，数据的存储空间的大小也发生变化。如果数据量增加，

3、就重新向系统申请新的空间；如果数据量减少，就将现有的多余的空间归还给系统。7.2.动态内存分配n使用计算机解决问题的所有方法都是通过使用系统提供给我们的基本命令或函数来实现的。所以首先让我们来看看，c的标准函数中有哪些是用于动态内存分配的，怎样使用。7.2.1 ANSI C 中动态内存操作标准函数nANSI C中提供了若干个动态内存操作标准函数，它们的名称分别是malloc、calloc、realloc、free等。这些函数可以使用在任何的C环境中。1malloc函数函数nmalloc函数是 C的标准函数之一。原型定义在malloc.h文件中。n原型为：nvoid*malloc(unsigne

4、d int size);n其作用是向系统申请一个确定大小(size 个字节)的存储空间，返回值为一个指向void类型的分配域起始地址的指针值。如果此函数操作失败，返回值为空。1malloc函数函数使用格式：指针型变量=(基类型*)malloc(需要的存储空间的字节数);例7-1：为一个整数分配存储空间，需要的语句为：在文件的头部：#include 在说明部分：int*p;在程序中：p=(int*)malloc(sizeof(int);测试malloc的程序举例：n#include n#include n#include nvoid main()nnint*p;/*定义一个指向整型的指针变量定义

5、一个指向整型的指针变量*/nint x;np=(int*)malloc(sizeof(int);nif(!p)exit(0);p=&x;nscanf(“%d”,p);printf(“x=%d”,x);n2calloc函数函数ncalloc函数是 C的标准函数之一。原型定义在malloc.h文件中。n原型为：nvoid*calloc(unsigned int n,unsigned int size);n其作用是向系统申请 n 个大小为size 个字节的连续存储空间，返回值为一个指向void类型的分配域起始地址的指针值。如果此函数操作失败，返回值为空。可以为一维数组开辟一片连续的动态存储空间。2c

6、alloc函数函数n使用格式：指针型变量=(数组元素类型*)calloc(n,每一个数组元素的存储空间的字节数)；n例7-2：为一个有10个整数的一维数组分配存储空间，需要的语句为：在文件的头部：#include 在说明部分：int*p;在程序中：p=(int*)calloc(10,sizeof(int);使用使用calloc函数程序举例：函数程序举例：#include#include#include main()int*p;int x;p=(int*)calloc(10,sizeof(int);if(!p)exit(0);for(i=0;i10;i+)scanf(“%d”,&x);*(p+i

7、)=x;for(i=0;i10;i+)printf(“%6d”,*(p+i);3realloc函数函数nrealloc函数是 C的标准函数之一。原型定义在malloc.h文件中。n原型为：nvoid*realloc(void*p,unsigned int size);n其作用是向系统重新申请一个确定大小的存储空间，并将原存储空间中的数据值传送到新的地址空间的低端，返回值为一个指向void类型的分配域起始地址的指针值。如果此函数操作失败，返回值为空。原存储空间的数据将丢失。3realloc函数函数使用格式：指针型变量=(基类型*)realloc(原存储空间的首地址，新的存储空间的字节数)；例7-

8、3：现有一个为10个整数分配的存储空间，其首地址为p1;由于数据量的增加，原存储空间已满，需要扩大原空间为20个整数的大小；需要的语句为：在文件的头部：#include 在说明部分：int*p2;在程序中：p2=(int*)realloc(p1,sizeof(int)*20);程序举例：n#include n#include n#include n main()n int*p1,*p2;n int x;n p1=(int*)malloc(sizeof(int)*10);n if(!p1)exit(0);n p2=(int*)realloc(p1,sizeof(int)*20);n if(!p2

9、)exit(0);nn realloc 函数主要的用于当原分配空间已被占满，而新的数据又要加入到该空间时的状况。它的优点是可以自动地将原空间的内容全部传递到新空间中，不必程序员再编语句来实现。缺点是一旦新空间申请失败，原空间的内容也将丢失。对这一点，使用时应加以注意。4free函数函数free函数是 C的标准函数之一。原型定义在malloc.h文件中，原型为：void free(void *p)其作用是释放由p所指的内存区，将一个存储空间归还给系统。使用格式：free(指针型变量);例7-4：将一个已分配存储空间释放，需要的语句为 在文件的头部：#include 在说明部分：int*p;在程序

10、中：free(p)程序举例：程序举例：n#include n#include n#include nmain()n int*p;n p=(int*)malloc(sizeof(int);n if(!p)exit(0);n free(p)；c+中为进行动态操作提供的运算符new和deleten在软件的研制过程中，程序中动态申请内存空间和释放内存空间是一件很常见的事，前面一节中，我们讲解了ANSI C 中的办法。利用标准库函数malloc、calloc、reallloc、free等。但malloc、calloc、reallloc等函数都要求程序设计者知道应开辟空间的确切大小，返回值的类型需要强制类

11、型转换。nc+中对此进行了改进，为进行动态内存操作提供了运算符new和delete，来代替malloc和free。但在c+中依然保留了malloc和free，以便和C兼容。1new 运算符运算符nnew 是c+中提供的用于开辟一个动态存储空间的运算符。nnew 运算符的一般格式：n变量指针=new 类型(初值)；n例如：n(1)申请一个存放整数的空间：语句格式：p=new int；执行结果：开辟了一个整数大小的空间，并将该空间的首地址送入指向整型数据的指针变量p中。(2)申请一个存放字符型数据的空间，并为该空间赋初值a：语句格式：p=new char(a)；执行结果：开辟了一个字节大小的空间，

12、并将该空间的首地址送入指向字符型数据的指针变量p中。P所指空间中的数据值为字符 a。(3)申请一个存放实数的空间：语句格式：p=new float(1.414)；执行结果：开辟了一个实数大小的空间，并将该空间的首地址送入指向实型数据的指针变量p中。并将该空间中赋入初值1.414。(4)申请一个存放10个实数的数组的空间：语句格式：p=new float10；执行结果：开辟了一个10个实数大小的空间，将该空间的首地址送入指向实型数据的指针变量p中。注意：用new 为数组分配空间不能指定初值。2delete 运算符：运算符：ndelete 运算符是c+中的提供的实现动态内存释放功能的运算符，类似于

13、标准库函数 free。n一般格式为：delete 名字指针；例如：n(1)释放一个存放整数的空间：如果 p=new int；则释放一个存放整数的空间的语句为：delete p;执行结果：将该整数空间释放掉，即将该资源归还给系统。2delete 运算符：运算符：n(2)释放一个存放10个实数的数组的空间：如果：p=new float10；则释放一个数组空间的语句为：delete p;执行结果：将该数组空间释放掉，即将该资源归还给系统。2delete 运算符：运算符：nnew 试图创建一个名字类型的对象，向系统申请sizeof(名字)个字节大小的空间。新对象的生存周期始于创建点，直到delete将

14、其释放或到程序结束。如果申请成功，返回指向新对象的指针；若返回的指针为空指针，表示动态空间分配失败。注意：delete只能用于用new分配的内存的释放。例7-5申请一个结构体类型的存储空间，用来存放相应类型的数据。解决问题要点：q包含相关的头文件；q定义一个结构体类型；q定义结构体类型的变量；q申请空间；q对指定空间赋值；q释放申请的空间；程序举例：程序举例：n#include n#include n#include n#include ntypedef struct LNode n int data;n struct LNode*next;n LNode;nmain()n n LNode*p

15、;n p=new LNode;n if(!p)exit(0);n p-data=10;n p-next=NULL;n delete p;n1.new 与malloc 的相同点是他们的作用都是在程序的执行过程中向系统申请存储空间，返回值都是申请到的存储空间的首地址，不同点是，malloc 是c编译系统提供的标准库函数，new 是c+系统提供的运算符，new的操作效率要高于malloc；2.new不需要使用显式的sizeof函数就能知道名字的大小，而malloc 需要明确指出所申请的空间的大小(总的字节数)；new 的返回值是指向名字类型的确定的指针类型，不需要强制说明，而malloc的返回值是一

16、个指向void类型的指针类型，需要强制转换成指向具体数据类型的指针类型。当所申请的空间是一个变量所需的空间时，new 运算符还可以为所申请的空间赋初值，malloc 不具有此功能。7.3 链链 表表n计算机处理数据需要两方面的工作，一方面是对计算机处理数据需要两方面的工作，一方面是对数据信息的描述，另一方面是对数据的操作，而数据信息的描述，另一方面是对数据的操作，而操作的方式取决于数据的描述方式，数据的描述操作的方式取决于数据的描述方式，数据的描述方式又取决于数据本身固有的内在联系。这里仅方式又取决于数据本身固有的内在联系。这里仅介绍数据之间的线性关系。介绍数据之间的线性关系。n对于图书馆的藏书这类数据信息可以用一种称对于图书馆的藏书这类数据信息可以用一种称为线性表的动态数据结构来描述。简单的说，线为线性表的动态数据结构来描述。简单的说，线性表是性表是 n 个数据元素的有限序列。各数据元素属个数据元素的有限序列。各数据元素属于同一数据对象，相邻数据元素之间存在序偶关于同一数据对象，相邻数据元素之间存在序偶关系。记为：系。记为：n（a1，a2，ai，ai+1，an）n线性表中的数据元素之