第7章动态数据结构.ppt

1,第七章 动态数据结构,2,教学目标,动态数据结构的概念 动态申请和释放内存的方法 链表的建立 链表结点的插入和删除算法,3,7.1 从静态数据结构到动态数据结构 7.2 动态内存分配 7.3 链表 7.4 本章小结,4,7.1 从静态数据结构到动态数据结构,静态数据结构的特点是由系统分配固定大小的存储空间，以后在程序运行的过程中，存储空间的位置和容量都不会再改变。如数组、简单类型(int、float)等。 实际生活中常常有这样的问题，数据量的多少是动态变化的。如何解决？,5,动态数据结构不确定总的数据存储量，而是为现有的每一个数据元素定义一个确定的初始大小的空间，若干个数据元素分配若干个同样大小的空间；当数据量发生变化时，数据存储空间的大小也发生变化。如果数据量增加，就重新向系统申请新的空间；如果数据量减少，就将现有的多余空间归还给系统。,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 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(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：为一个有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函数,原型： void *realloc( void *p, unsigned int size); 功能：向系统重新申请一个确定大小的存储空间，并将原存储空间中的数据值传送到新的地址空间的低端，返回值为一个指向void类型的分配域起始地址的指针值。如果此函数操作失败，返回值为空,原存储空间的数据也将丢失。,15,使用格式： 指针型变量 =(基类型 *)realloc( 原存储空间的首地址，新的存储空间的字节数)； 例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 *)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; 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=0;i2;i+) printf(“%6d“, *(p+i); free(p); ,补充程序,18,realloc 函数主要用于当原分配空间已被占满，而新的数据又要加入到该空间时的状况。 优点是可以自动地将原空间的内容全部传递到新空间中，不必程序员再编语句来实现。 缺点是一旦新空间申请失败，原空间的内容也将丢失。对这一点，使用时应加以注意。,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(!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 运算符的一般格式： 变量指针 = new 类型(初值); 如果申请成功，返回指向新对象的指针；若返回的指针为空指针，表示动态空间分配失败。,23,例如： 申请一个存放整数的空间： 语句格式： p = new int； 执行结果：开辟了一个整数大小的空间，并将 该空间的首地址送入指向整型数据的指针变量 p中。 申请一个存放字符型数据的空间，并为该空间赋初值a： 语句格式： p = new char(a)； 执行结果：开辟了一个字节大小的空间，并将该空间的首地址送入指向字符型数据的指针变量p中。p所指空间中的数据值为字符 a 。,24,申请一个存放实数的空间： 语句格式： p = new float(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); 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; 执行结果：将该数组空间释放掉，即将该资源归还给系统。 注意：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() 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 需要明确指出所申请的空间的大小(总的字节数)。 new 的返回值是指向名字类型的确定的指针类型，不需要强制说明，而malloc的返回值是一个指向void类型的指针类型，需要强制转换成指向具体数据类型的指针类型。 当所申请的空间是一个变量所需的空间时，new 运算符还可以为所申请的空间赋初值，malloc不具有此功能。,32,7.3 链 表,计算机处理数据需要两方面的工作，一方面是对数据信息的描述，另一方面是对数据的操作，而操作的方式取决于数据的描述方式，数据的描述方式又取决于数据本身固有的内在联系。这里仅介绍数据之间的线性关系(线性表)。 线性表是 n 个数据元素的有限序列。各数据元素属于同一数据对象，相邻数据元素之间存在序偶关系。记为： （a1，a2，ai，ai+1，an）,33,7.3 链表,链表的定义 链表的建立 链表结点的插入 链表结点的删除 循环链表,34,线性表中的数据元素之间存在严格的顺序关系，有一个唯一的称为第一个的元素（首元），有唯一的称为最后一个的元素（尾元），其它元素都有唯一的直接后继元素和唯一的直接前趋元素。 线性表这种逻辑结构在计算机内表示时，可以采用链式存储结构，即一个数据元素存放于一个结点中，不同的数据元素之间的先后顺序用结点的指针域链接。一个结点就是一个结构体类型的变量。,35,链表的定义,链表是表示具有线性关系的一组数据元素的动态结构。 每个数据元素占据一个独立申请的存储空间，这个存储空间通常是一个结构体型变量，主要包括两部分，一部分用来存放数据元素的值称为值域，另一部分用来存放一个指向该结构体类型的指针变量值称为指针域。指针域的作用是存放逻辑上排在本结点后面的结点的存储空间的首地址。,36,数据元素结点的结构如图所示： 单向链表和单向循环链表如下图所示：,单向链表,单向循环链表,37,链表结点的 C 语句定义,首先用结构体类型描述一个数据元素结点，定义一个结点类型的语句格式： typedef struct LNode ElemType data; struct LNode *next; LNode, * LinkList;,38,typedef struct Node ElemType data; struct Node *next; LNode,* LinkList; 等价于 struct Node ElemType data; struct Node *next; ; typedef struct Node LNode; typedef struct Node* LinkList;,39,说明：,typedef 语句定义了一个结构体类型和链表类型(结构体指针类型)。 Node 是一个结点的类型名称。它有两个成员，一个名称为data ，类型为数据元素的类型，用来存放一个数据元素的值；另一个成员名称为next，类型为指向本结构体类型的指针类型，用来存放逻辑上排在本结点后面的结点的首地址。 LNode类型等价于struct Node类型，也等价于Node类型。 LinkList类型等价于LNode 的指针类型。 ElemType 是数据元素的类型的一般性描述，当我们具体写程序时，应该用确定类型名称来替换，例如，int、float 、char等。,40,例：链表中的数据元素用来存放整数，定义链表的结点类型的语句格式为： typedef struct Node int data; struct Node *next; LNode,*LinkList;,41,定义一个结点类型的变量的语句： struct Node q; LNode q ; 定义一个指向结点类型的指针变量的语句： struct Node * p; LNode* p ; LinkList L; 访问结点变量的各个成员： q.data , q.next p-data , p-next L-data , L-next,42,链表的建立,1. 构造一个空线性链表 首先，构造一个空的线性链表。为了描述方便，通常将链表的第一个结点空置，不存放数据元素，只是作为链表的开始标志，称为头结点。数据元素从链表的第二个结点开始存放。 空的线性表定义为没有数据元素的表。一个空的线性链表就规定为，只有一个头结点的链表。所以，构造一个空的线性链表就是建立只有一个头结点的链表。,43,算法描述: 申请一个结点的空间； 将该结点作为线性链表的头结点； 将该结点的 next 域置空；,44,程序：,/*构造一个空的线性链表*/ LNode* InitList () LinkList L;/头结点指针 L = (LNode*) malloc(sizeof(LNode ); /*申请一结点空间*/ if ( !L) exit ( 0 );/*申请不成功，异常结束程序运行*/ L-next = NULL;/*申请成功，头结点的next域置空*/ return(L); ,45,2逆序输入n个数据元素，建立带表头结点的单向链表,现在开始建立一个非空的线性链表。这里所建的链表的第一个结点都是头结点。数据元素从链表的第二个结点开始存放。 一个非空的线性链表是除了头结点以外至少有一个数据元素的链表。线性链表由若干个数据元素结点组成。那么，构造一个非空的线性链表的过程就是逐个建立数据元素结点，并将它们依次插入到链表中的过程。,46,头插入，即每次将数据元素结点插入到表头结点的之后，第一个数据元素结点之前。 插入过程如下图所示：,初始状态：,插入第一个结点之后：,头结点,47,插入第二个结点之后：,插入第三个结点之后：,插入最后一个结点之后：,48,LNode* CreateList(int n) int i; LNode *p; LinkList L ; L = (LNode*) malloc(sizeof(LNode); if (!L) exit ( 0 ); L-next = NULL; for(i=n;i0;i-) p = (LNode*) malloc(sizeof(LNode); if (!p) exit ( 0 ); scanf(“%d“, ,程序：,头结点,头插入,49,链表结点的插入,将一个数据元素插入到链表中，有三种情况：头插入，尾插入以及在链表中的第i个数据元素的位置处插入。 将一个新元素插入在链表的头结点的后面，其它的所有结点之前称为头插入。 将一个新元素插入在链表的尾结点的后面，使得新插入的结点成为尾结点称为尾插入。 将一个新元素插入在链表中的第i个数据元素的位置处，即插入在第i个数据元素结点之前，使得新插入的结点成为链表中的第i个结点。,50,例：已有链表L 如图所示,链表中的元素按递增有序排列：,其中每个结点中存放的值为学生的考试成绩。现在有另外三个学生的的成绩分别为65、82、90。将他们插入到链表L中，要求插入之后链表依然递增有序。,p,L,q,51,将65插入到链表L中:,s,p,L,q,头插入,52,将82插入到链表L中:,s,p,L,q,中间插入,53,将90插入到链表L中:,s,p=,L,q,尾插入,54,实现语句：,LNode *p,*q, *s; LinkList L; /头结点指针 q=L; p=L-next; while( p ,55,程序：,int ListInsert(LNode *L, int e) LNode *p,*q, *s; if(!L) return 0; q=L; p=L-next ; while(p ,56,链表结点的删除,例：已有链表如图所示：删除链表中数据元素值为76的结点。,q,p,L,57,q,p,L,q,p,L,q,L,58,程序:,int ListDelete ( LNode *L, int e ) LNode *q, *p; if ( !L ) return 0 ; p=L-next ; q=L; while ( p ,59,#include #include #include struct Node int data; struct Node *next; ; typedef struct Node LNode; typedef struct Node* LinkList;,综合程序,60,LNode* CreateList(int n) /创建链表 int i; LNode *p; LinkList L ; L = (LNode *) malloc(sizeof(LNode); if (!L) exit ( 0 ); L-next = NULL; for(i=n;i0;i-) p = (LNode *) malloc(sizeof(LNode); if (!p) exit ( 0 ); scanf(“%d“, ,61,int ListInsert(LNode *L, int e) )/插入元素 LNode *p,*q, *s; if(!L) return 0; q=L; p=L-next ; while(p ,62,int ListDelete ( LNode *L,int e ) /删除元素 LNode *q, *p; if ( !L ) return 0; p=L-next ; q=L; while ( p ,63,void ListPrint ( LNode *L ) /显示链表元素 LNode *p; p=L; while(p-next!=NULL) p=p-next; printf(“%d “,p-data); printf(“n“); void ListFree ( LNode *L ) /释放链表元素 LNode *p; p=L-next; free(L); while(p) printf(“free:%dn“,p-data); L=p-next; free(p); p=L; ,64,void main() LNode *LinkHead; LinkHead=CreateList(3);/创建链表 ListPrint(LinkHead);/显示链表数据 ListInsert(LinkHead, 65);/插入元素 ListInsert(LinkHead, 82); /插入元素 ListInsert(LinkHead, 90); /插入元素 ListPrint(LinkHead); /显示链表元素 ListDelete(LinkHead, 80); /删除元素 ListPrint(LinkHead); /显示链表元素 ListFree (LinkHead);/释放链表元素 ,65,循环链表,循环链表是在单链表的基础之上做一个简单的变化，将单链表中最后一个结点的指针域指向头结点，这样整个链表形成一个环。 从表中任意结点出发，均可找到表中其他结点。 表中任何一个结点的next域都不是空指针值。,66,7.4 小 结,本章介绍了线性链表的定义和建立算法，又介绍了插入一个结点、删除一个结点等算法的实现。通过这一章的学习，我们初步了解了动态数据结构的特点和使用方式。 还有许多的动态数据结构，如堆栈、队列、树、图等。它们都被广泛的应用于计算机系统中，在计算的系统和应用软件中起着非常重要的作用。动态数据结构的更详细内容将在后续课程数据结构讲述。,67,思考题：,只设尾指针的单循环链表的初始化、建立、插入和删除算法应怎样写？,