第7章 动态数据结构优秀PPT.ppt

《第7章 动态数据结构优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第7章 动态数据结构优秀PPT.ppt（67页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第7章 动态数据结构1现在学习的是第1页，共67页教学目标n动态数据结构的概念n动态申请和释放内存的方法n链表的建立n链表结点的插入和删除算法2现在学习的是第2页，共67页7.1 从静态数据结构到动态数据结构7.2 动态内存分配7.3 链表7.4 本章小结3现在学习的是第3页，共67页7.1 从静态数据结构到动态数据结构静态数据结构静态数据结构的特点是由系统分配固定大小的存储空的特点是由系统分配固定大小的存储空间，以后在程序运行的过程中，存储空间的位置和容间，以后在程序运行的过程中，存储空间的位置和容量都不会再改变量都不会再改变。如数组、简单类型。如数组、简单类型(int、float)等。等。

2、实际生活中常常有这样的问题，数据量的多少是动实际生活中常常有这样的问题，数据量的多少是动态变化的。如何解决？态变化的。如何解决？4现在学习的是第4页，共67页动态数据结构动态数据结构不确定总的数据存储量，而是不确定总的数据存储量，而是为现有为现有的每一个数据元素定义一个确定的初始大小的空间，的每一个数据元素定义一个确定的初始大小的空间，若干个数据元素分配若干个同样大小的空间；当数据若干个数据元素分配若干个同样大小的空间；当数据量发生变化时，数据存储空间的大小也发生变化。如量发生变化时，数据存储空间的大小也发生变化。如果数据量增加，就重新向系统申请新的空间；如果数果数据量增加，就重新向系统申请新

3、的空间；如果数据量减少，就将现有的多余空间归还给系统。据量减少，就将现有的多余空间归还给系统。5现在学习的是第5页，共67页7.2.动态内存分配vANSI C 中用于动态操作的标准函数vC+中用于动态操作的运算符new和delete（不要求）6现在学习的是第6页，共67页vANSI C 中用于动态操作的标准函数ANSI C中提供了若干个动态内存操作标准函数，它们中提供了若干个动态内存操作标准函数，它们的名称分别是的名称分别是malloc、calloc、realloc、free等。这等。这些函数可以使用在任何的些函数可以使用在任何的C环境中，其原型定义在环境中，其原型定义在malloc.h文件中

4、。文件中。7现在学习的是第7页，共67页qmalloc函数函数原型原型：void*malloc(unsigned int size);功能功能：向系统申请一个确定大小：向系统申请一个确定大小(size 个字节个字节)的的存储空间，返回值为一个指向存储空间，返回值为一个指向void类型的分配类型的分配域起始地址的指针值。如果此函数操作失败，返域起始地址的指针值。如果此函数操作失败，返回值为空。回值为空。8现在学习的是第8页，共67页使用格式使用格式：指针型变量指针型变量=(=(基类型基类型*)malloc()malloc(需要的存储空间的字节数需要的存储空间的字节数););例例7-17-1：为一

5、个整数分配存储空间，需要的语句为：为一个整数分配存储空间，需要的语句为：在文件的头部：在文件的头部：#include#include 在说明部分：在说明部分：int*p;int*p;在程序中：在程序中：p=p=(int*)(int*)mallocmalloc(sizeof(int);(sizeof(int);9现在学习的是第9页，共67页【例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(

6、p);10现在学习的是第10页，共67页qcalloc函数函数原型原型：void*calloc(unsigned int n,unsigned int size);功能功能：向系统申请：向系统申请 n 个大小为个大小为size 个字节的连续存储个字节的连续存储空间，返回值为一个指向空间，返回值为一个指向void类型的分配域起始地址类型的分配域起始地址的指针值。如果此函数操作失败，返回值为空。的指针值。如果此函数操作失败，返回值为空。使用使用此函数可以为一维数组开辟一片连续的动态存储空间。此函数可以为一维数组开辟一片连续的动态存储空间。11现在学习的是第11页，共67页使用格式使用格式：指针型变

7、量指针型变量=(数组元素类型数组元素类型*)calloc(n,每一个数组元素的每一个数组元素的存储空间的字节数存储空间的字节数)；例例7-2：为一个有：为一个有10个整数的一维数组分配存储空间，需要的个整数的一维数组分配存储空间，需要的语句为：语句为：在文件的头部：在文件的头部：#include 在说明部分：在说明部分：int*p;在程序中：在程序中：p=(int*)calloc(10,sizeof(int);12现在学习的是第12页，共67页【例7-2】使用calloc函数程序#include#include#include#define N 10void main()int*p;int x

8、,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);13现在学习的是第13页，共67页qrealloc函数函数原型原型：void*realloc(void*p,unsigned int size);功能功能：向系统：向系统重新申请重新申请一个确定大小的存储空间，一个确定大小的存储空间，并将并将原存储空间原存储空间中的数据值传送到新的地址空间的低端，中的数据值传送到新的地址空间的

9、低端，返回值为一个指向返回值为一个指向void类型的分配域起始地址的指针值。类型的分配域起始地址的指针值。如果此函数操作失败，返回值为空如果此函数操作失败，返回值为空,原存储空间的数据也原存储空间的数据也将丢失。将丢失。14现在学习的是第14页，共67页使用格式使用格式：指针型变量指针型变量=(基类型基类型*)realloc(原存储空间的首地址，新原存储空间的首地址，新的存储空间的字节数的存储空间的字节数)；例例7-3：现有一个为：现有一个为10个整数分配的存储空间，其首地址为个整数分配的存储空间，其首地址为p;由于数据量的增加，原存储空间已满，需要扩大原空间由于数据量的增加，原存储空间已满，

10、需要扩大原空间为为20个整数的大小；需要的语句为：个整数的大小；需要的语句为：在文件的头部：在文件的头部：#include 在说明部分：在说明部分：int*p;在程序中：在程序中：p=(int*)realloc(p,sizeof(int)*20);15现在学习的是第15页，共67页【例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)exi

11、t(0);free(p2);16现在学习的是第16页，共67页#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);补充程序17现在学习的是第17页，共67页 realloc 函数

12、函数主要用于当原分配空间已被占满，而主要用于当原分配空间已被占满，而新的数据又要加入到该空间时的状况。新的数据又要加入到该空间时的状况。优点优点是可以自动地将原空间的内容全部传递到新是可以自动地将原空间的内容全部传递到新空间中，不必程序员再编语句来实现。空间中，不必程序员再编语句来实现。缺点缺点是一旦新空间申请失败，原空间的内容也将丢失。是一旦新空间申请失败，原空间的内容也将丢失。对这一点，使用时应加以注意。对这一点，使用时应加以注意。18现在学习的是第18页，共67页qfree函数函数原型原型：void free(void *p);void free(void *p);功能功能：释放由：释放

13、由p p所指的内存区，将一个存储空间归还给系统。所指的内存区，将一个存储空间归还给系统。使用格式使用格式：free(free(指针型变量指针型变量););例例7-47-4：将一个已分配存储空间释放，需要的语句：将一个已分配存储空间释放，需要的语句:在文件的头部：在文件的头部：#include#include 在说明部分：在说明部分：int*p;int*p;在程序中：在程序中：freefree(p)(p)19现在学习的是第19页，共67页【例7-4】使用free函数程序#include#include#include main()int*p;p=(int*)malloc(sizeof(int);

14、if(!p)exit(0);free(p);20现在学习的是第20页，共67页7.3 链表v链表的定义v链表的建立v链表结点的插入v链表结点的删除v循环链表33现在学习的是第33页，共67页v链表的定义链表的定义n链表是链表是表示表示具有线性关系具有线性关系的一组的一组数据元素数据元素的的动态结构动态结构。n每个数据元素占据一个独立申请的存储空间，这个存每个数据元素占据一个独立申请的存储空间，这个存储空间通常是储空间通常是一个结构体型变量，主要包括两部分，一个结构体型变量，主要包括两部分，一部分用来存放数据元素的值一部分用来存放数据元素的值称为称为值域值域，另一，另一部分用来存放一个指向该结构

15、体类型的指针变量值部分用来存放一个指向该结构体类型的指针变量值称为称为指针域指针域。指针域的作用是存放逻辑上排在本指针域的作用是存放逻辑上排在本结点后面的结点的存储空间的首地址。结点后面的结点的存储空间的首地址。35现在学习的是第35页，共67页n数据元素结点的结构如图所示：数据元素结点的结构如图所示：n单向链表和单向循环链表单向链表和单向循环链表如下图所示：如下图所示：单向链表单向链表a1 an-1an值域指针域a1 an-1an单向循环链表单向循环链表36现在学习的是第36页，共67页链表结点的链表结点的 C 语句定义语句定义n首先用结构体类型描述一个数据元素结首先用结构体类型描述一个数据

16、元素结点，定义一个结点类型的语句格式：点，定义一个结点类型的语句格式：typedef struct LNode ElemType data;struct LNode *next;LNode,*LinkList;37现在学习的是第37页，共67页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;38现在学

17、习的是第38页，共67页说明：说明：ntypedef 语句定义了一个结构体类型和链表类型语句定义了一个结构体类型和链表类型(结构体指针类型结构体指针类型)。nNode 是一个结点的类型名称是一个结点的类型名称。它有两个成员，一个名称为。它有两个成员，一个名称为data，类型，类型为数据元素的类型，用来存放一个数据元素的值；另一个成员名为数据元素的类型，用来存放一个数据元素的值；另一个成员名称为称为next，类型为指向本结构体类型的指针类型，用来存放逻辑，类型为指向本结构体类型的指针类型，用来存放逻辑上排在本结点后面的结点的首地址。上排在本结点后面的结点的首地址。nLNode类型等价于类型等价于

18、struct Node类型，也等价于类型，也等价于Node类型。类型。nLinkList类型等价于类型等价于LNode 的指针类型。的指针类型。nElemType 是数据元素的类型的一般性描述是数据元素的类型的一般性描述，当我们具体写程序时，当我们具体写程序时，应该用确定类型名称来替换，例如，应该用确定类型名称来替换，例如，int、float、char等。等。39现在学习的是第39页，共67页例：链表中的数据元素用来存放整数，定义例：链表中的数据元素用来存放整数，定义链表的结点类型的语句格式为：链表的结点类型的语句格式为：typedef struct Node int data;struct

19、Node *next;LNode,*LinkList;40现在学习的是第40页，共67页1.定义一个结点类型的变量的语句：定义一个结点类型的变量的语句：struct Node q;LNode q;2.定义一个指向结点类型的指针变量的语句：定义一个指向结点类型的指针变量的语句：struct Node*p;LNode*p;LinkList L;3.访问结点变量的各个成员：访问结点变量的各个成员：q.data ,q.next p-data ,p-nextL-data,L-next41现在学习的是第41页，共67页v链表的建立链表的建立 1.构造一个构造一个空线性链表空线性链表 首先，构造一个空的线性

20、链表。为了描述方便，通首先，构造一个空的线性链表。为了描述方便，通常将链表的第一个结点空置，不存放数据元素，只常将链表的第一个结点空置，不存放数据元素，只是作为链表的开始标志，称为是作为链表的开始标志，称为头结点头结点。数据元素从链。数据元素从链表的第二个结点开始存放。表的第二个结点开始存放。空的线性表空的线性表定义为没有数据元素的表定义为没有数据元素的表。一个空的线一个空的线性链表就规定为，只有一个头结点的链表。性链表就规定为，只有一个头结点的链表。所以，所以，构构造一个空的线性链表就是建立只有一个头结点的链表。造一个空的线性链表就是建立只有一个头结点的链表。42现在学习的是第42页，共67

21、页程序：程序：/*构造一个空的线性链表*/LNode*InitList()LinkList L;/头结点指针L=(LNode*)malloc(sizeof(LNode);/*申请一结点空间*/if(!L)exit(0);/*申请不成功，异常结束程序运行*/L-next=NULL;/*申请成功，头结点的next域置空*/return(L);44现在学习的是第44页，共67页2 2逆序输入逆序输入n n个数据元素，建立带表头结点的单向链个数据元素，建立带表头结点的单向链表表n现在开始建立一个非空的线性链表。这里所建的链表的现在开始建立一个非空的线性链表。这里所建的链表的第一个结点都是第一个结点都是

22、头结点头结点。数据元素从链表的第二个结点。数据元素从链表的第二个结点开始存放。开始存放。n一个非空的线性链表一个非空的线性链表是除了头结点以外至少有一个数是除了头结点以外至少有一个数据元素的链表。据元素的链表。线性链表由若干个数据元素结点组线性链表由若干个数据元素结点组成。那么，构造一个非空的线性链表的过程就是逐成。那么，构造一个非空的线性链表的过程就是逐个建立数据元素结点，并将它们依次插入到链表中个建立数据元素结点，并将它们依次插入到链表中的过程。的过程。45现在学习的是第45页，共67页头插入头插入，即每次将数据元素结点插入到表头结点的，即每次将数据元素结点插入到表头结点的之后，第一个数据

23、元素结点之前。之后，第一个数据元素结点之前。插入过程如下图所示：插入过程如下图所示：初始状态：初始状态：插入第一个结点之后：插入第一个结点之后：an头结点46现在学习的是第46页，共67页n插入第二个结点之后：插入第二个结点之后：n 插入第三个结点之后：插入第三个结点之后：n插入最后一个结点之后：插入最后一个结点之后：an-1anan-1an-2anan-1a1an 47现在学习的是第47页，共67页LNode*CreateList(int n)int i;LNode*p;LinkList L;L=(LNode*)malloc(sizeof(LNode);if(!L)exit(0);L-nex

24、t=NULL;for(i=n;i0;i-)p=(LNode*)malloc(sizeof(LNode);if(!p)exit(0);scanf(%d,&p-data);p-next=L-next;L-next=p;return L;程序：头结点头结点头插入头插入48现在学习的是第48页，共67页v链表结点的插入n将一个数据元素插入到链表中，有三种情况：将一个数据元素插入到链表中，有三种情况：头头插入插入，尾插入尾插入以及以及在链表中的第在链表中的第i i个数据元素的位个数据元素的位置处插入置处插入。n将一个新元素插入在链表的头结点的后面，其它的所将一个新元素插入在链表的头结点的后面，其它的所有

25、结点之前称为有结点之前称为头插入头插入。n将一个新元素插入在链表的尾结点的后面，使得新将一个新元素插入在链表的尾结点的后面，使得新插入的结点成为尾结点称为插入的结点成为尾结点称为尾插入尾插入。n将一个新元素插入在链表中的第将一个新元素插入在链表中的第i i个数据元素的位个数据元素的位置处置处，即插入在第，即插入在第i i个数据元素结点之前，使得新插个数据元素结点之前，使得新插入的结点成为链表中的第入的结点成为链表中的第i i个结点。个结点。49现在学习的是第49页，共67页例：已有链表例：已有链表L 如图所示如图所示,链表中的元素按递链表中的元素按递增有序排列：增有序排列：其中每个结点中存放的

26、值为学生的考试成绩。现在有另其中每个结点中存放的值为学生的考试成绩。现在有另外三个学生的的成绩分别为外三个学生的的成绩分别为65、82、90。将他们插。将他们插入到链表入到链表L中，要求插入之后链表依然递增有序。中，要求插入之后链表依然递增有序。pLq70808550现在学习的是第50页，共67页将将6565插入到链表插入到链表L L中中:s sp pLq65708085头插入头插入51现在学习的是第51页，共67页将将8282插入到链表插入到链表L L中中:s sp pLq6570808285中间插入52现在学习的是第52页，共67页将将9090插入到链表插入到链表L L中中:s sp=p=

27、Lq657080828590尾插入53现在学习的是第53页，共67页实现语句实现语句：LNode*p,*q,*s;LinkList L;/头结点指针q=L;p=L-next;while(p&p-datanext;s=(LNode*)malloc(sizeof(LNode);s-data=e;s-next=p;q-next=s;54现在学习的是第54页，共67页程序：int ListInsert(LNode*L,int e)LNode*p,*q,*s;if(!L)return 0;q=L;p=L-next;while(p&p-data next;s=(LNode*)malloc(sizeof(L

28、Node);if(!s)exit(0);s-data=e;s-next=p;q-next=s;return 1;55现在学习的是第55页，共67页v链表结点的删除例：已有链表如图所示：删除链表中数据元素值为76的结点。80657690qpL56现在学习的是第56页，共67页80657690qpL80657690qpL806590qL57现在学习的是第57页，共67页程序程序:int ListDelete (LNode *L,int e)LNode*q,*p;if(!L)return 0;p=L-next;q=L;while(p&p-data!=e)q=p;p=p-next;if(p)q-nex

29、t=p-next;free(p);return(1);else return(0);58现在学习的是第58页，共67页#include#include#include struct Node int data;struct Node *next;typedef struct Node LNode;typedef struct Node*LinkList;综合程序综合程序59现在学习的是第59页，共67页LNode*CreateList(int n)/创建链表创建链表int i;LNode*p;LinkList L;L=(LNode*)malloc(sizeof(LNode);if(!L)exi

30、t(0);L-next=NULL;for(i=n;i0;i-)p=(LNode*)malloc(sizeof(LNode);if(!p)exit(0);scanf(%d,&p-data);p-next=L-next;L-next=p;return L;60现在学习的是第60页，共67页int ListInsert(LNode*L,int e)/插入元素插入元素 LNode*p,*q,*s;if(!L)return 0;q=L;p=L-next;while(p&p-data next;s=(LNode*)malloc(sizeof(LNode);if(!s)exit(0);s-data=e;s-

31、next=p;q-next=s;return 1;61现在学习的是第61页，共67页int ListDelete (LNode *L,int e)/删除元素删除元素 LNode*q,*p;if(!L)return 0;p=L-next;q=L;while(p&p-data!=e)q=p;p=p-next;if(p)q-next=p-next;free(p);return(1);else return(0);62现在学习的是第62页，共67页void ListPrint (LNode *L)/显示链表元素显示链表元素LNode*p;p=L;while(p-next!=NULL)p=p-next;

32、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;63现在学习的是第63页，共67页void main()LNode*LinkHead;LinkHead=CreateList(3);/创建链表创建链表ListPrint(LinkHead);/显示链表数据显示链表数据ListInsert(LinkHead,65);/插入元素插入元素ListInsert(Link

33、Head,82);/插入元素插入元素ListInsert(LinkHead,90);/插入元素插入元素ListPrint(LinkHead);/显示链表元素显示链表元素ListDelete(LinkHead,80);/删除元素删除元素ListPrint(LinkHead);/显示链表元素显示链表元素ListFree (LinkHead);/释放链表元素释放链表元素64现在学习的是第64页，共67页v循环链表n循环链表是在单链表的基础之上做一个简单的变化，将单链表中最后一个结点的指针域指向头结点，这样整个链表形成一个环。n从表中任意结点出发，均可找到表中其他结点。n表中任何一个结点的next域都不是空指针值。65现在学习的是第65页，共67页7.4 小 结n本章介绍了线性链表的定义和建立算法，又介绍了插入一个结点、删除一个结点等算法的实现。通过这一章的学习，我们初步了解了动态数据结构的特点和使用方式。n还有许多的动态数据结构，如堆栈、队列、树、图等。它们都被广泛的应用于计算机系统中，在计算的系统和应用软件中起着非常重要的作用。动态数据结构的更详细内容将在后续课程数据结构讲述。66现在学习的是第66页，共67页思考题：n只设尾指针的单循环链表的初始化、建立、插入和删除算法应怎样写？67现在学习的是第67页，共67页