第7章 动态数据结构PPT讲稿.ppt

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

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

2、组、简单类型(int、float)等。等。实际生活中常常有这样的问题，数据量的多少是动态实际生活中常常有这样的问题，数据量的多少是动态变化的。如何解决？变化的。如何解决？4第4页，共67页，编辑于2022年，星期一动态数据结构动态数据结构不确定总的数据存储量，而是不确定总的数据存储量，而是为现有的为现有的每一个数据元素定义一个确定的初始大小的空间，每一个数据元素定义一个确定的初始大小的空间，若干个数据元素分配若干个同样大小的空间；当数据量若干个数据元素分配若干个同样大小的空间；当数据量发生变化时，数据存储空间的大小也发生变化。如果数发生变化时，数据存储空间的大小也发生变化。如果数据量增加，就重

3、新向系统申请新的空间；如果数据量减据量增加，就重新向系统申请新的空间；如果数据量减少，就将现有的多余空间归还给系统。少，就将现有的多余空间归还给系统。5第5页，共67页，编辑于2022年，星期一7.2.动态内存分配vANSI C 中用于动态操作的标准函数vC+中用于动态操作的运算符new和delete（不要求）6第6页，共67页，编辑于2022年，星期一vANSI C 中用于动态操作的标准函数ANSI C中提供了若干个动态内存操作标准函数，它中提供了若干个动态内存操作标准函数，它们的名称分别是们的名称分别是malloc、calloc、realloc、free等。等。这些函数可以使用在任何的这些

4、函数可以使用在任何的C环境中，其原型定义在环境中，其原型定义在malloc.h文件中。文件中。7第7页，共67页，编辑于2022年，星期一qmalloc函数函数原型原型：void*malloc(unsigned int size);功能功能：向系统申请一个确定大小：向系统申请一个确定大小(size 个字节个字节)的的存储空间，返回值为一个指向存储空间，返回值为一个指向void类型的分配域类型的分配域起始地址的指针值。如果此函数操作失败，返回起始地址的指针值。如果此函数操作失败，返回值为空。值为空。8第8页，共67页，编辑于2022年，星期一使用格式使用格式：指针型变量指针型变量=(=(基类型基

5、类型*)malloc()malloc(需要的存储空间的字节数需要的存储空间的字节数););例例7-17-1：为一个整数分配存储空间，需要的语句为：为一个整数分配存储空间，需要的语句为：在文件的头部：在文件的头部：#include#include 在说明部分：在说明部分：int*p;int*p;在程序中：在程序中：p=p=(int*)(int*)mallocmalloc(sizeof(int);(sizeof(int);9第9页，共67页，编辑于2022年，星期一【例7-1】测试malloc的程序：#include#include#include void main()int*p;p=(int*

6、)malloc(sizeof(int);if(!p)exit(0);*p=10;printf(*p=%dn,*p);free(p);10第10页，共67页，编辑于2022年，星期一qcalloc函数函数原型原型：void*calloc(unsigned int n,unsigned int size);功能功能：向系统申请：向系统申请 n 个大小为个大小为size 个字节的连续存储个字节的连续存储空间，返回值为一个指向空间，返回值为一个指向void类型的分配域起始地址的类型的分配域起始地址的指针值。如果此函数操作失败，返回值为空。指针值。如果此函数操作失败，返回值为空。使用此使用此函数可以为一

7、维数组开辟一片连续的动态存储空间。函数可以为一维数组开辟一片连续的动态存储空间。11第11页，共67页，编辑于2022年，星期一使用格式使用格式：指针型变量指针型变量=(数组元素类型数组元素类型*)calloc(n,每一个数组元素的每一个数组元素的存储空间的字节数存储空间的字节数)；例例7-2：为一个有：为一个有10个整数的一维数组分配存储空间，需个整数的一维数组分配存储空间，需要的语句为：要的语句为：在文件的头部：在文件的头部：#include 在说明部分：在说明部分：int*p;在程序中：在程序中：p=(int*)calloc(10,sizeof(int);12第12页，共67页，编辑于2

8、022年，星期一【例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);13第13页，共67页，编辑于2022年，星期一qrealloc函数函数原型原型：void*realloc(void*p,unsigned int size);

9、功能功能：向系统：向系统重新申请重新申请一个确定大小的存储空间，一个确定大小的存储空间，并并将将原存储空间原存储空间中的数据值传送到新的地址空间的低端，中的数据值传送到新的地址空间的低端，返回值为一个指向返回值为一个指向void类型的分配域起始地址的指类型的分配域起始地址的指针值。如果此函数操作失败，返回值为空针值。如果此函数操作失败，返回值为空,原存储原存储空间的数据也将丢失。空间的数据也将丢失。14第14页，共67页，编辑于2022年，星期一使用格式使用格式：指针型变量指针型变量=(基类型基类型*)realloc(原存储空间的首地址，新原存储空间的首地址，新的存储空间的字节数的存储空间的字

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

11、)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页，编辑于2022年，星期一#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*

12、)realloc(p,sizeof(int)*2);if(!p)exit(0);for(i=0;i2;i+)printf(%6d,*(p+i);free(p);补充程序17第17页，共67页，编辑于2022年，星期一 realloc 函数函数主要用于当原分配空间已被占满，而主要用于当原分配空间已被占满，而新的数据又要加入到该空间时的状况。新的数据又要加入到该空间时的状况。优点优点是可以自动地将原空间的内容全部传递到新空是可以自动地将原空间的内容全部传递到新空间中，不必程序员再编语句来实现。间中，不必程序员再编语句来实现。缺点缺点是一旦新空间申请失败，原空间的内容也将丢是一旦新空间申请失败，原空

13、间的内容也将丢失。对这一点，使用时应加以注意。失。对这一点，使用时应加以注意。18第18页，共67页，编辑于2022年，星期一qfree函数函数原型原型：void free(void *p);void free(void *p);功能功能：释放由：释放由p p所指的内存区，将一个存储空间归还给系统。所指的内存区，将一个存储空间归还给系统。使用格式使用格式：free(free(指针型变量指针型变量););例例7-47-4：将一个已分配存储空间释放，需要的语句：将一个已分配存储空间释放，需要的语句:在文件的头部：在文件的头部：#include#include 在说明部分：在说明部分：int*p;i

14、nt*p;在程序中：在程序中：freefree(p)(p)19第19页，共67页，编辑于2022年，星期一【例7-4】使用free函数程序#include#include#include main()int*p;p=(int*)malloc(sizeof(int);if(!p)exit(0);free(p);20第20页，共67页，编辑于2022年，星期一7.3 链表v链表的定义v链表的建立v链表结点的插入v链表结点的删除v循环链表33第33页，共67页，编辑于2022年，星期一v链表的定义链表的定义n链表是链表是表示表示具有线性关系具有线性关系的一组的一组数据元素数据元素的的动态结构动态结构

15、。n每个数据元素占据一个独立申请的存储空间，这个存每个数据元素占据一个独立申请的存储空间，这个存储空间通常是储空间通常是一个结构体型变量，主要包括两部分，一个结构体型变量，主要包括两部分，一部分用来存放数据元素的值一部分用来存放数据元素的值称为称为值域值域，另一，另一部分用来存放一个指向该结构体类型的指针变量值部分用来存放一个指向该结构体类型的指针变量值称为称为指针域指针域。指针域的作用是存放逻辑上排在本指针域的作用是存放逻辑上排在本结点后面的结点的存储空间的首地址。结点后面的结点的存储空间的首地址。35第35页，共67页，编辑于2022年，星期一n数据元素结点的结构如图所示：数据元素结点的结

16、构如图所示：n单向链表和单向循环链表单向链表和单向循环链表如下图所示：如下图所示：单向链表单向链表a1 an-1an值域指针域a1 an-1an单向循环链表单向循环链表36第36页，共67页，编辑于2022年，星期一链表结点的链表结点的 C 语句定义语句定义n首先用结构体类型描述一个数据元素结首先用结构体类型描述一个数据元素结点，定义一个结点类型的语句格式：点，定义一个结点类型的语句格式：typedef struct LNode ElemType data;struct LNode *next;LNode,*LinkList;37第37页，共67页，编辑于2022年，星期一typedef st

17、ruct 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页，编辑于2022年，星期一说明：说明：ntypedef 语句定义了一个结构体类型和链表类型语句定义了一个结构体类型和链表类型(结构体指针类型结构体指针类型)。nNode 是一个结点的类型名称是一个结点的类型名称。它有两个成员，一个名称为。它有两个成员，

18、一个名称为data，类，类型为数据元素的类型，用来存放一个数据元素的值；另一个成员名称型为数据元素的类型，用来存放一个数据元素的值；另一个成员名称为为next，类型为指向本结构体类型的指针类型，用来存放逻辑上，类型为指向本结构体类型的指针类型，用来存放逻辑上排在本结点后面的结点的首地址。排在本结点后面的结点的首地址。nLNode类型等价于类型等价于struct Node类型，也等价于类型，也等价于Node类型。类型。nLinkList类型等价于类型等价于LNode 的指针类型。的指针类型。nElemType 是数据元素的类型的一般性描述是数据元素的类型的一般性描述，当我们具体写程序时，应，当我

19、们具体写程序时，应该用确定类型名称来替换，例如，该用确定类型名称来替换，例如，int、float、char等。等。39第39页，共67页，编辑于2022年，星期一例：链表中的数据元素用来存放整数，定义例：链表中的数据元素用来存放整数，定义链表的结点类型的语句格式为：链表的结点类型的语句格式为：typedef struct Node int data;struct Node *next;LNode,*LinkList;40第40页，共67页，编辑于2022年，星期一1.定义一个结点类型的变量的语句：定义一个结点类型的变量的语句：struct Node q;LNode q;2.定义一个指向结点类型

20、的指针变量的语句：定义一个指向结点类型的指针变量的语句：struct Node*p;LNode*p;LinkList L;3.访问结点变量的各个成员：访问结点变量的各个成员：q.data ,q.next p-data ,p-nextL-data,L-next41第41页，共67页，编辑于2022年，星期一v链表的建立链表的建立 1.构造一个构造一个空线性链表空线性链表 首先，构造一个空的线性链表。为了描述方便，通常首先，构造一个空的线性链表。为了描述方便，通常将链表的第一个结点空置，不存放数据元素，只是作将链表的第一个结点空置，不存放数据元素，只是作为链表的开始标志，称为为链表的开始标志，称为

21、头结点头结点。数据元素从链表。数据元素从链表的第二个结点开始存放。的第二个结点开始存放。空的线性表空的线性表定义为没有数据元素的表定义为没有数据元素的表。一个空的线一个空的线性链表就规定为，只有一个头结点的链表。性链表就规定为，只有一个头结点的链表。所以，所以，构构造一个空的线性链表就是建立只有一个头结点的造一个空的线性链表就是建立只有一个头结点的链表。链表。42第42页，共67页，编辑于2022年，星期一程序：程序：/*构造一个空的线性链表*/LNode*InitList()LinkList L;/头结点指针L=(LNode*)malloc(sizeof(LNode);/*申请一结点空间*/

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

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

24、页，共67页，编辑于2022年，星期一n插入第二个结点之后：插入第二个结点之后：n 插入第三个结点之后：插入第三个结点之后：n插入最后一个结点之后：插入最后一个结点之后：an-1anan-1an-2anan-1a1an 47第47页，共67页，编辑于2022年，星期一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);sc

25、anf(%d,&p-data);p-next=L-next;L-next=p;return L;程序：头结点头结点头插入头插入48第48页，共67页，编辑于2022年，星期一v链表结点的插入n将一个数据元素插入到链表中，有三种情况：将一个数据元素插入到链表中，有三种情况：头头插入插入，尾插入尾插入以及以及在链表中的第在链表中的第i i个数据元素的位置个数据元素的位置处插入处插入。n将一个新元素插入在链表的头结点的后面，其它的所将一个新元素插入在链表的头结点的后面，其它的所有结点之前称为有结点之前称为头插入头插入。n将一个新元素插入在链表的尾结点的后面，使得新插将一个新元素插入在链表的尾结点的后

26、面，使得新插入的结点成为尾结点称为入的结点成为尾结点称为尾插入尾插入。n将一个新元素插入在链表中的第将一个新元素插入在链表中的第i i个数据元素的位置个数据元素的位置处处，即插入在第，即插入在第i i个数据元素结点之前，使得新插个数据元素结点之前，使得新插入的结点成为链表中的第入的结点成为链表中的第i i个结点。个结点。49第49页，共67页，编辑于2022年，星期一例：已有链表例：已有链表L 如图所示如图所示,链表中的元素按递增链表中的元素按递增有序排列：有序排列：其中每个结点中存放的值为学生的考试成绩。现在其中每个结点中存放的值为学生的考试成绩。现在有另外三个学生的的成绩分别为有另外三个学

27、生的的成绩分别为65、82、90。将。将他们插入到链表他们插入到链表L中，要求插入之后链表依然递增有序。中，要求插入之后链表依然递增有序。pLq70808550第50页，共67页，编辑于2022年，星期一将将6565插入到链表插入到链表L L中中:s sp pLq65708085头插入头插入51第51页，共67页，编辑于2022年，星期一将将8282插入到链表插入到链表L L中中:s sp pLq6570808285中间插入52第52页，共67页，编辑于2022年，星期一将将9090插入到链表插入到链表L L中中:s sp=p=Lq657080828590尾插入53第53页，共67页，编辑于2

28、022年，星期一实现语句实现语句：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页，编辑于2022年，星期一程序：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)

29、;s-data=e;s-next=p;q-next=s;return 1;55第55页，共67页，编辑于2022年，星期一v链表结点的删除例：已有链表如图所示：删除链表中数据元素值为76的结点。80657690 qpL56第56页，共67页，编辑于2022年，星期一80657690 qpL80657690 qpL806590 qL57第57页，共67页，编辑于2022年，星期一程序程序: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

30、)q-next=p-next;free(p);return(1);else return(0);58第58页，共67页，编辑于2022年，星期一#include#include#include struct Node int data;struct Node *next;typedef struct Node LNode;typedef struct Node*LinkList;综合程序综合程序59第59页，共67页，编辑于2022年，星期一LNode*CreateList(int n)/创建链表创建链表int i;LNode*p;LinkList L;L=(LNode*)malloc(siz

31、eof(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页，共67页，编辑于2022年，星期一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)

32、;if(!s)exit(0);s-data=e;s-next=p;q-next=s;return 1;61第61页，共67页，编辑于2022年，星期一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页，编辑于2022年，星期一void ListPrint (LNode *L)/显示链表元素显示链表元素

33、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;63第63页，共67页，编辑于2022年，星期一void main()LNode*LinkHead;LinkHead=CreateList(3);/创建链表创建链表ListPrint(LinkHead);/显示链表数据显示链表数据

34、ListInsert(LinkHead,65);/插入元素插入元素ListInsert(LinkHead,82);/插入元素插入元素ListInsert(LinkHead,90);/插入元素插入元素ListPrint(LinkHead);/显示链表元素显示链表元素ListDelete(LinkHead,80);/删除元素删除元素ListPrint(LinkHead);/显示链表元素显示链表元素ListFree (LinkHead);/释放链表元素释放链表元素64第64页，共67页，编辑于2022年，星期一v循环链表n循环链表是在单链表的基础之上做一个简单的变化，将单链表中最后一个结点的指针域指

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