第7章动态数据结构.ppt

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

1、1第七章 动态数据结构2教学目标n动态数据结构的概念n动态申请和释放内存的方法n链表的建立n链表结点的插入和删除算法37.1 从静态数据结构到动态数据结构7.2 动态内存分配7.3 链表7.4 本章小结47.1 从静态数据结构到动态数据结构静态数据结构静态数据结构的特点是由系统分配固定大小的存的特点是由系统分配固定大小的存储空间，以后在程序运行的过程中，存储空间的储空间，以后在程序运行的过程中，存储空间的位置和容量都不会再改变位置和容量都不会再改变。如数组、简单类型。如数组、简单类型(int、float)等。等。实际生活中常常有这样的问题，数据量的多少是实际生活中常常有这样的问题，数据量的多少

2、是动态变化的。如何解决？动态变化的。如何解决？5动态数据结构动态数据结构不确定总的数据存储量，而是不确定总的数据存储量，而是为现为现有的每一个数据元素定义一个确定的初始大小的有的每一个数据元素定义一个确定的初始大小的空间，空间，若干个数据元素分配若干个同样大小的空若干个数据元素分配若干个同样大小的空间；当数据量发生变化时，数据存储空间的大小间；当数据量发生变化时，数据存储空间的大小也发生变化。如果数据量增加，就重新向系统申也发生变化。如果数据量增加，就重新向系统申请新的空间；如果数据量减少，就将现有的多余请新的空间；如果数据量减少，就将现有的多余空间归还给系统。空间归还给系统。67.2.动态内

3、存分配vANSI C 中用于动态操作的标准函数vC+中用于动态操作的运算符new和delete（不要求）7vANSI C 中用于动态操作的标准函数ANSI C中提供了若干个动态内存操作标准函数，中提供了若干个动态内存操作标准函数，它们的名称分别是它们的名称分别是malloc、calloc、realloc、free等。这些函数可以使用在任何的等。这些函数可以使用在任何的C环境中，环境中，其原型定义在其原型定义在malloc.h文件中。文件中。8qmalloc函数函数原型原型：void*malloc(unsigned int size);功能功能：向系统申请一个确定大小：向系统申请一个确定大小(s

4、ize 个字节个字节)的存储空间，返回值为一个指向的存储空间，返回值为一个指向void类型的分类型的分配域起始地址的指针值。如果此函数操作失败，配域起始地址的指针值。如果此函数操作失败，返回值为空。返回值为空。9使用格式使用格式：指针型变量指针型变量=(=(基类型基类型*)mallocmalloc(需要的存储空间的字需要的存储空间的字节数节数););例例7-17-1：为一个整数分配存储空间，需要的语句为：为一个整数分配存储空间，需要的语句为：在文件的头部：在文件的头部：#include#include 在说明部分：在说明部分：intint *p;p;在程序中：在程序中：p=p=(intint

5、*)mallocmalloc(sizeof(int(sizeof(int););10【例7-1】测试malloc的程序：#include#include#include void main()int*p;p=(int*)malloc(sizeof(int);if(!p)exit(0);*p=10;printf(*p=%dn,*p);free(p);11qcalloc函数函数原型原型：void*calloc(unsigned int n,unsigned int size);功能功能：向系统申请：向系统申请 n 个大小为个大小为size 个字节的连续个字节的连续存储空间，返回值为一个指向存储空间

6、，返回值为一个指向void类型的分配域类型的分配域起始地址的指针值。如果此函数操作失败，返回起始地址的指针值。如果此函数操作失败，返回值为空。值为空。使用此函数可以为一维数组开辟一片连使用此函数可以为一维数组开辟一片连续的动态存储空间。续的动态存储空间。12使用格式使用格式：指针型变量指针型变量=(数组元素类型数组元素类型*)calloc(n,每一个数组每一个数组元素的存储空间的字节数元素的存储空间的字节数)；例例7-2：为一个有：为一个有10个整数的一维数组分配存储空间，个整数的一维数组分配存储空间，需要的语句为：需要的语句为：在文件的头部：在文件的头部：#include 在说明部分：在说明

7、部分：int*p;在程序中：在程序中：p=(int*)calloc(10,sizeof(int);13【例7-2】使用calloc函数程序#include#include#include#define N 10void main()int*p;int x,i;p=(int*)calloc(N,sizeof(int);if(!p)exit(0);for(i=0;iN;i+)scanf(%d,&x);*(p+i)=x;for(i=0;iN;i+)printf(%6d,*(p+i);free(p);scanf(%d,p+i);14qrealloc函数函数原型原型：void*realloc(void*

8、p,unsigned int size);功能功能：向系统：向系统重新申请重新申请一个确定大小的存储空间，一个确定大小的存储空间，并将并将原存储空间原存储空间中的数据值传送到新的地址空间中的数据值传送到新的地址空间的低端，的低端，返回值为一个指向返回值为一个指向void类型的分配域起类型的分配域起始地址的指针值。如果此函数操作失败，返回值始地址的指针值。如果此函数操作失败，返回值为空为空,原存储空间的数据也将丢失。原存储空间的数据也将丢失。15使用格式使用格式：指针型变量指针型变量=(基类型基类型*)realloc(原存储空间的首地原存储空间的首地址，新的存储空间的字节数址，新的存储空间的字节

9、数)；例例7-3：现有一个为：现有一个为10个整数分配的存储空间，其首个整数分配的存储空间，其首地址为地址为p;由于数据量的增加，原存储空间已满，需要由于数据量的增加，原存储空间已满，需要扩大原空间为扩大原空间为20个整数的大小；需要的语句为：个整数的大小；需要的语句为：在文件的头部：在文件的头部：#include 在说明部分：在说明部分：int*p;在程序中：在程序中：p=(int*)realloc(p,sizeof(int)*20);16【例7-3】使用realloc函数程序#include#include#include void main()int*p1,*p2;p1=(int*)ma

10、lloc(sizeof(int)*10);if(!p1)exit(0);p2=(int*)realloc(p1,sizeof(int)*20);if(!p2)exit(0);free(p2);17#include#include#include void main()int*p;int i;p=(int*)malloc(sizeof(int)*3);/p=(int*)calloc(3,sizeof(int);if(!p)exit(0);for(i=0;i3;i+)scanf(%d,p+i);p=(int*)realloc(p,sizeof(int)*2);if(!p)exit(0);for(i

11、=0;i2;i+)printf(%6d,*(p+i);free(p);补充程序18 realloc 函数函数主要用于当原分配空间已被占满，主要用于当原分配空间已被占满，而新的数据又要加入到该空间时的状况。而新的数据又要加入到该空间时的状况。优点优点是可以自动地将原空间的内容全部传递到是可以自动地将原空间的内容全部传递到新空间中，不必程序员再编语句来实现。新空间中，不必程序员再编语句来实现。缺点缺点是一旦新空间申请失败，原空间的内容也是一旦新空间申请失败，原空间的内容也将丢失。对这一点，使用时应加以注意。将丢失。对这一点，使用时应加以注意。19qfree函数函数原型原型：void free(vo

12、id void free(void *p);p);功能功能：释放由：释放由p p所指的内存区，将一个存储空间归所指的内存区，将一个存储空间归还给系统。还给系统。使用格式使用格式：free(free(指针型变量指针型变量););例例7-47-4：将一个已分配存储空间释放，需要的语句：将一个已分配存储空间释放，需要的语句:在文件的头部：在文件的头部：#include#include 在说明部分：在说明部分：intint *p;p;在程序中：在程序中：freefree(p)(p)20【例7-4】使用free函数程序#include#include#include main()int*p;p=(int

13、*)malloc(sizeof(int);if(!p)exit(0);free(p);21v C+中用于动态操作的运算符-new和deletenANSI C中，在用malloc、calloc、reallloc等函数动态申请内存空间都要求程序设计者知道应开辟空间的确切大小(用sizeof)，并且返回值的类型需要强制类型转换。nC+中对此进行了改进，为进行动态内存操作提供了运算符new和delete，代替malloc和free。但在C+中依然保留了malloc和free，以便和C兼容。n使用运算符new和delete程序文件的文件名后缀必须为cpp。22qnew 运算符运算符nnew 是C+中提供

14、的用于开辟一个动态存储空间的运算符。new 运算符的一般格式：变量指针=new 类型(初值);如果申请成功，返回指向新对象的指针；若返回的指针为空指针，表示动态空间分配失败。23例如：n申请一个存放整数的空间：语句格式：p=new int；执行结果：开辟了一个整数大小的空间，并将该空间的首地址送入指向整型数据的指针变量p中。n申请一个存放字符型数据的空间，并为该空间赋初值a：语句格式：p=new char(a)；执行结果：开辟了一个字节大小的空间，并将该空间的首地址送入指向字符型数据的指针变量p中。p所指空间中的数据值为字符 a。24n申请一个存放实数的空间：语句格式：p=new float(

15、1.414)；执行结果：开辟了一个实数大小的空间，并将该空间的首地址送入指向实型数据的指针变量p中。p所指空间中的数据值为1.414。n申请一个存放10个实数的数组的空间：语句格式：p=new float10；执行结果：开辟了一个10个实数大小的空间，将该空间的首地址送入指向实型数据的指针变量p中。注意：用new 为数组分配空间不能指定初值。25#include#include void main()float*p;int i;p=new float3;if(!p)exit(0);for(i=0;i3;i+)scanf(%f,p+i);for(i=0;i3;i+)printf(%f ,*(p+

16、i);/delete p;补充程序不用加头文件malloc.h26qdelete 运算符运算符ndelete 运算符是C+中提供的实现动态内存释放功能的运算符，类似于标准库函数 free。一般格式为：delete 名字指针；例如：n释放一个存放整数的空间：n如果 p=new int；，则释放一个存放整数的空间的语句为：delete p;n执行结果：将该整数空间释放掉，即将该资源归还给系统。27n释放一个存放10个实数的数组的空间：n如果：p=new float10；，则释放一个数组空间的语句为：delete p;n执行结果：将该数组空间释放掉，即将该资源归还给系统。n注意：delete只能用于用new分配的内存的释放。28例例7-57-5 申请一个结构体类型的存储空间，用来存放相应类型的数据。解决问题要点：n包含相关的头文件；n定义一个结构体类型；n定义结构体类型的变量；n申请空间；n对指定空间赋值；n释放申请的空间；29【例7-5】程序举例：#include#include/#include#include typedef struct LNode int data;struct L