第7章动态数据结构.ppt
《第7章动态数据结构.ppt》由会员分享,可在线阅读,更多相关《第7章动态数据结构.ppt(67页珍藏版)》请在三一文库上搜索。
1、1,第七章 动态数据结构,2,教学目标,动态数据结构的概念 动态申请和释放内存的方法 链表的建立 链表结点的插入和删除算法,3,7.1 从静态数据结构到动态数据结构 7.2 动态内存分配 7.3 链表 7.4 本章小结,4,7.1 从静态数据结构到动态数据结构,静态数据结构的特点是由系统分配固定大小的存储空间,以后在程序运行的过程中,存储空间的位置和容量都不会再改变。如数组、简单类型(int、float)等。 实际生活中常常有这样的问题,数据量的多少是动态变化的。如何解决?,5,动态数据结构不确定总的数据存储量,而是为现有的每一个数据元素定义一个确定的初始大小的空间,若干个数据元素分配若干个同
2、样大小的空间;当数据量发生变化时,数据存储空间的大小也发生变化。如果数据量增加,就重新向系统申请新的空间;如果数据量减少,就将现有的多余空间归还给系统。,6,7.2. 动态内存分配,ANSI C 中用于动态操作的标准函数 C+ 中用于动态操作的运算符new和delete(不要求),7,ANSI C 中用于动态操作的标准函数,ANSI C中提供了若干个动态内存操作标准函数,它们的名称分别是malloc、calloc、realloc、free等。这些函数可以使用在任何的C环境中,其原型定义在malloc.h文件中。,8,malloc函数,原型: void *malloc(unsigned int
3、size); 功能:向系统申请一个确定大小(size 个字节)的存储空间,返回值为一个指向void类型的分配域起始地址的指针值。如果此函数操作失败,返回值为空。,9,使用格式: 指针型变量=(基类型*)malloc(需要的存储空间的字节数); 例7-1:为一个整数分配存储空间,需要的语句为: 在文件的头部:#include 在说明部分: int *p; 在程序中:p = (int *)malloc(sizeof(int);,10,【例7-1】测试malloc的程序:,#include #include #include void main() int *p; p = (int *)malloc
4、(sizeof(int); if (!p) exit( 0 ); *p=10; printf(“*p=%dn“, *p); free(p); ,11,calloc函数,原型: void *calloc(unsigned int n , unsigned int size); 功能:向系统申请 n 个大小为size 个字节的连续存储空间,返回值为一个指向void类型的分配域起始地址的指针值。如果此函数操作失败,返回值为空。使用此函数可以为一维数组开辟一片连续的动态存储空间。,12,使用格式: 指针型变量 =(数组元素类型 *)calloc(n , 每一个数组元素的存储空间的字节数); 例7-2:
5、为一个有10个整数的一维数组分配存储空间,需要的语句为: 在文件的头部:#include 在说明部分: int *p; 在程序中:p = (int *)calloc(10 , sizeof(int) ;,13,【例7-2】使用calloc函数程序,#include #include #include #define N 10 void main() int *p; int x,i; p =(int *)calloc(N, sizeof(int); if(!p) exit(0); for(i=0;iN;i+) scanf(“%d“, ,scanf(“%d“,p+i);,14,realloc函数,
6、原型: void *realloc( void *p, unsigned int size); 功能:向系统重新申请一个确定大小的存储空间,并将原存储空间中的数据值传送到新的地址空间的低端,返回值为一个指向void类型的分配域起始地址的指针值。如果此函数操作失败,返回值为空,原存储空间的数据也将丢失。,15,使用格式: 指针型变量 =(基类型 *)realloc( 原存储空间的首地址,新的存储空间的字节数); 例7-3:现有一个为10个整数分配的存储空间,其首地址为p; 由于数据量的增加,原存储空间已满,需要扩大原空间为20个整数的大小;需要的语句为: 在文件的头部:#include 在说明部
7、分: int *p; 在程序中:p=(int *)realloc(p,sizeof(int)*20 );,16,【例7-3】使用realloc函数程序,#include #include #include void main() int *p1,*p2; p1 =(int *)malloc(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; in
8、t 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=0;i2;i+) printf(“%6d“, *(p+i); free(p); ,补充程序,18,realloc 函数主要用于当原分配空间已被占满,而新的数据又要加入到该空间时的状况。 优点是可以自动地将原空间的内容全部传递到新空间中,不必程
9、序员再编语句来实现。 缺点是一旦新空间申请失败,原空间的内容也将丢失。对这一点,使用时应加以注意。,19,free函数,原型: void free (void *p); 功能:释放由p所指的内存区,将一个存储空间归还给系统。 使用格式: free(指针型变量); 例7-4:将一个已分配存储空间释放,需要的语句: 在文件的头部:#include 在说明部分: int *p; 在程序中: free( p ),20,【例7-4】使用free函数程序,#include #include #include main() int *p; p =(int *)malloc(sizeof(int); if(!
10、p) exit(0); free(p); ,21,C+ 中用于动态操作的 运算符-new和delete,ANSI C中,在用malloc、calloc、reallloc等函数动态申请内存空间都要求程序设计者知道应开辟空间的确切大小(用sizeof),并且返回值的类型需要强制类型转换。 C+中对此进行了改进,为进行动态内存操作提供了运算符new和delete,代替malloc和free。但在C+中依然保留了malloc和free,以便和C兼容。 使用运算符new和delete程序文件的文件名后缀必须为cpp。,22,new 运算符,new 是C+中提供的用于开辟一个动态存储空间的运算符。 new
11、 运算符的一般格式: 变量指针 = new 类型(初值); 如果申请成功,返回指向新对象的指针;若返回的指针为空指针,表示动态空间分配失败。,23,例如: 申请一个存放整数的空间: 语句格式: p = new int; 执行结果:开辟了一个整数大小的空间,并将 该空间的首地址送入指向整型数据的指针变量 p中。 申请一个存放字符型数据的空间,并为该空间赋初值a: 语句格式: p = new char(a); 执行结果:开辟了一个字节大小的空间,并将该空间的首地址送入指向字符型数据的指针变量p中。p所指空间中的数据值为字符 a 。,24,申请一个存放实数的空间: 语句格式: p = new flo
12、at(1.414); 执行结果:开辟了一个实数大小的空间,并将该空间的首地址送入指向实型数据的指针变量p中。 p所指空间中的数据值为1.414。 申请一个存放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);
13、for(i=0;i3;i+) printf(“%f “,*(p+i); /delete p; ,补充程序,不用加头文件malloc.h,26,delete 运算符,delete 运算符是C+中提供的实现动态内存释放功能的运算符,类似于标准库函数 free。 一般格式为:delete 名字指针; 例如: 释放一个存放整数的空间: 如果 p = new int;,则释放一个存放整数的空间的语句为:delete p; 执行结果:将该整数空间释放掉,即将该资源归还给系统。,27,释放一个存放10个实数的数组的空间: 如果: p = new float10;,则释放一个数组空间的语句为:delete p
14、; 执行结果:将该数组空间释放掉,即将该资源归还给系统。 注意:delete只能用于用new分配的内存的释放。,28,例7-5 申请一个结构体类型的存储空间,用来存放相应类型的数据。 解决问题要点: 包含相关的头文件; 定义一个结构体类型; 定义结构体类型的变量; 申请空间; 对指定空间赋值; 释放申请的空间;,29,【例7-5】程序举例:,#include #include /#include #include typedef struct LNode int data; struct LNode *next; LNode; /typedef float REAL; void main()
15、LNode *p; p= new LNode; if ( !p ) exit(0); p-data=10; p-next=NULL; delete p; ,struct LNode int data; struct LNode *next; ;,30,new与malloc的相同点和不同点,相同点:它们的作用都是在程序的执行过程中向系统申请存储空间,返回值都是申请到的存储空间的首地址。 不同点: malloc 是C编译系统提供的标准库函数,new 是C+系统提供的运算符,new的操作效率要高于malloc。,31,new不需要使用显式的sizeof函数就能知道类型的大小,而malloc 需要明确
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 章动 数据结构
链接地址:https://www.31doc.com/p-2980395.html