第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文件中。文件中。7第7页，本讲稿共67页q

4、malloc函数函数原型原型：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(p);10第10页，本讲稿共67页qcalloc函数函

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

7、个数组元素每一个数组元素的存储空间的字节数的存储空间的字节数)；例例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,i;p=(int*)calloc(N,sizeof(int);if(!

8、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);功能功能：向系统：向系统重新申请重新申请一个确定大小的存储空间，一个确定大小的存储空间，并并将将原存储空间原存储空间中的数据值传送到新的地址空间的低端，中的数据值传送到新的地址空间的低端，返回值为一个指向返回值为一个指向void类型的分配域起始地址的指类型的分

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

10、的头部：在文件的头部：#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)exit(0);free(p2);16第16页，本讲稿共67页#include#include#

11、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);功能功能：释放由：释放由p p所指的内存区，将一个存储空间归还给所指的内存区，将一个存储空间归还给系统。系统。使用格式使用格式：f

13、ree(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);if(!p)exit(0);free(p);20第20页，本讲稿共67页7.3 链表v链表的定义v链表的建立v链表

14、结点的插入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首先用结构体类型描述一个数据元素结首先用结构体类型描述一个数据元素结点，定义一个结点类型的语句格式：点，定义一个结点类型的语句格式：typedef struct LNode ElemType data

16、;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第38页，本讲稿共67页说明：说明：ntypedef 语句定义了一个结构体类型和链表类型语句定义了一个结构体类型和链表类型(结构体指针类型结构体指针类

17、型)。nNode 是一个结点的类型名称是一个结点的类型名称。它有两个成员，一个名称为。它有两个成员，一个名称为data，类，类型为数据元素的类型，用来存放一个数据元素的值；另一个成员名称型为数据元素的类型，用来存放一个数据元素的值；另一个成员名称为为next，类型为指向本结构体类型的指针类型，用来存放逻辑上排在本结点，类型为指向本结构体类型的指针类型，用来存放逻辑上排在本结点后面的结点的首地址。后面的结点的首地址。nLNode类型等价于类型等价于struct Node类型，也等价于类型，也等价于Node类型。类型。nLinkList类型等价于类型等价于LNode 的指针类型。的指针类型。nEl

18、emType 是数据元素的类型的一般性描述是数据元素的类型的一般性描述，当我们具体写程序时，当我们具体写程序时，应该用确定类型名称来替换，例如，应该用确定类型名称来替换，例如，int、float、char等。等。39第39页，本讲稿共67页例：链表中的数据元素用来存放整数，定义例：链表中的数据元素用来存放整数，定义链表的结点类型的语句格式为：链表的结点类型的语句格式为：typedef struct Node int data;struct Node *next;LNode,*LinkList;40第40页，本讲稿共67页1.定义一个结点类型的变量的语句：定义一个结点类型的变量的语句：struc

19、t 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页程序：程序：/*构造一个空的线性链表*/LNode*InitList()LinkList L;/头结点指针L=(LNode*)malloc(sizeof(LNode);/*

21、申请一结点空间*/if(!L)exit(0);/*申请不成功，异常结束程序运行*/L-next=NULL;/*申请成功，头结点的next域置空*/return(L);44第44页，本讲稿共67页2 2逆序输入逆序输入n n个数据元素，建立带表头结点的单向链表个数据元素，建立带表头结点的单向链表n现在开始建立一个非空的线性链表。这里所建的链现在开始建立一个非空的线性链表。这里所建的链表的第一个结点都是表的第一个结点都是头结点头结点。数据元素从链表的第二。数据元素从链表的第二个结点开始存放。个结点开始存放。n一个非空的线性链表一个非空的线性链表是除了头结点以外至少有一个数据是除了头结点以外至少有一

22、个数据元素的链表。元素的链表。线性链表由若干个数据元素结点组成。线性链表由若干个数据元素结点组成。那么，构造一个非空的线性链表的过程就是逐个建立那么，构造一个非空的线性链表的过程就是逐个建立数据元素结点，并将它们依次插入到链表中的过程。数据元素结点，并将它们依次插入到链表中的过程。45第45页，本讲稿共67页头插入头插入，即每次将数据元素结点插入到表头结点的，即每次将数据元素结点插入到表头结点的之后，第一个数据元素结点之前。之后，第一个数据元素结点之前。插入过程如下图所示：插入过程如下图所示：初始状态：初始状态：插入第一个结点之后：插入第一个结点之后：an头结点46第46页，本讲稿共67页n插

23、入第二个结点之后：插入第二个结点之后：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-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

24、-next=p;return L;程序：头结点头结点头插入头插入48第48页，本讲稿共67页v链表结点的插入n将一个数据元素插入到链表中，有三种情况：将一个数据元素插入到链表中，有三种情况：头头插入插入，尾插入尾插入以及以及在链表中的第在链表中的第i i个数据元素的位置个数据元素的位置处插入处插入。n将一个新元素插入在链表的头结点的后面，其它的所将一个新元素插入在链表的头结点的后面，其它的所有结点之前称为有结点之前称为头插入头插入。n将一个新元素插入在链表的尾结点的后面，使得新插将一个新元素插入在链表的尾结点的后面，使得新插入的结点成为尾结点称为入的结点成为尾结点称为尾插入尾插入。n将一个新元

25、素插入在链表中的第将一个新元素插入在链表中的第i i个数据元素的个数据元素的位置处位置处，即插入在第，即插入在第i i个数据元素结点之前，使个数据元素结点之前，使得新插入的结点成为链表中的第得新插入的结点成为链表中的第i i个结点。个结点。49第49页，本讲稿共67页例：已有链表例：已有链表L 如图所示如图所示,链表中的元素按递增链表中的元素按递增有序排列：有序排列：其中每个结点中存放的值为学生的考试成绩。现在有其中每个结点中存放的值为学生的考试成绩。现在有另外三个学生的的成绩分别为另外三个学生的的成绩分别为65、82、90。将他们插。将他们插入到链表入到链表L中，要求插入之后链表依然递增有序

26、。中，要求插入之后链表依然递增有序。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=Lq657080828590尾插入53第53页，本讲稿共67页实现语句实现语句：LNode*p,*q,*s;LinkList L;/头结点指针q=L;p=L-next;while(p&p-datanext;s=(LNode*)m

27、alloc(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(LNode);if(!s)exit(0);s-data=e;s-next=p;q-next=s;return 1;55第55页，本讲稿共67页v链表结点的删除例：已有链表如图所示：删除链表中数据元素值为76的结点。80657690 qpL56

28、第56页，本讲稿共67页80657690 qpL80657690 qpL806590 qL57第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-next=p-next;free(p);return(1);else return(0);58第58页，本讲稿共67页#include#include#include struct Node int data;struct Node *next;typed

29、ef 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)exit(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

30、页，本讲稿共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-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!=

31、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;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

32、=L;63第63页，本讲稿共67页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);/显示链表元素

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