第7章 动态数据结构精选文档.ppt

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

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

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

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

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

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

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

7、alloc(n,每一个数组元素的每一个数组元素的存储空间的字节数存储空间的字节数)；例例7-2：为一个有：为一个有10个整数的一维数组分配存储空间，需要个整数的一维数组分配存储空间，需要的语句为：的语句为：在文件的头部：在文件的头部：#include 在说明部分：在说明部分：int*p;在程序中：在程序中：p=(int*)calloc(10,sizeof(int);12本讲稿第十二页，共六十七页【例7-2】使用calloc函数程序#include#include#include#define N 10void main()int*p;int x,i;p=(int*)calloc(N,sizeo

8、f(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本讲稿第十三页，共六十七页qrealloc函数函数原型原型：void*realloc(void*p,unsigned int size);功能功能：向系统：向系统重新申请重新申请一个确定大小的存储空间，一个确定大小的存储空间，并并将将原存储空间原存储空间中的数据值传送到新的地址空间的低中的数据值传送到新的地址空间的低端，端，返回值为一个指向返回值为一个指向void类型的分

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

10、大小；需要的语句为：在文件的头部：在文件的头部：#include 在说明部分：在说明部分：int*p;在程序中：在程序中：p=(int*)realloc(p,sizeof(int)*20);15本讲稿第十五页，共六十七页【例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本讲稿第十六页，共六十七页#i

11、nclude#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本讲稿第十七页，共六十七页 realloc 函数函数主要用于当原分配空间已被占满，而主要用于当原分配空间已被占满，而新

12、的数据又要加入到该空间时的状况。新的数据又要加入到该空间时的状况。优点优点是可以自动地将原空间的内容全部传递到新是可以自动地将原空间的内容全部传递到新空间中，不必程序员再编语句来实现。空间中，不必程序员再编语句来实现。缺点缺点是一旦新空间申请失败，原空间的内容也将是一旦新空间申请失败，原空间的内容也将丢失。对这一点，使用时应加以注意。丢失。对这一点，使用时应加以注意。18本讲稿第十八页，共六十七页qfree函数函数原型原型：void free(void *p);void free(void *p);功能功能：释放由：释放由p p所指的内存区，将一个存储空间归还所指的内存区，将一个存储空间归还给

13、系统。给系统。使用格式使用格式：free(free(指针型变量指针型变量););例例7-47-4：将一个已分配存储空间释放，需要的语句：将一个已分配存储空间释放，需要的语句:在文件的头部：在文件的头部：#include#include 在说明部分：在说明部分：int*p;int*p;在程序中：在程序中：freefree(p)(p)19本讲稿第十九页，共六十七页【例7-4】使用free函数程序#include#include#include main()int*p;p=(int*)malloc(sizeof(int);if(!p)exit(0);free(p);20本讲稿第二十页，共六十七页7.

14、3 链表v链表的定义v链表的建立v链表结点的插入v链表结点的删除v循环链表33本讲稿第三十三页，共六十七页v链表的定义链表的定义n链表是链表是表示表示具有线性关系具有线性关系的一组的一组数据元素数据元素的的动态结构动态结构。n每个数据元素占据一个独立申请的存储空间，这个存储每个数据元素占据一个独立申请的存储空间，这个存储空间通常是空间通常是一个结构体型变量，主要包括两部分，一个结构体型变量，主要包括两部分，一部分用来存放数据元素的值一部分用来存放数据元素的值称为称为值域值域，另一，另一部分用来存放一个指向该结构体类型的指针变量值部分用来存放一个指向该结构体类型的指针变量值称为称为指针域指针域。

15、指针域的作用是存放逻辑上排在本结指针域的作用是存放逻辑上排在本结点后面的结点的存储空间的首地址。点后面的结点的存储空间的首地址。35本讲稿第三十五页，共六十七页n数据元素结点的结构如图所示：数据元素结点的结构如图所示：n单向链表和单向循环链表单向链表和单向循环链表如下图所示：如下图所示：单向链表单向链表a1 an-1an值域指针域a1 an-1an单向循环链表单向循环链表36本讲稿第三十六页，共六十七页链表结点的链表结点的 C 语句定义语句定义n首先用结构体类型描述一个数据元素结首先用结构体类型描述一个数据元素结点，定义一个结点类型的语句格式：点，定义一个结点类型的语句格式：typedef s

16、truct LNode ElemType data;struct LNode *next;LNode,*LinkList;37本讲稿第三十七页，共六十七页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本讲稿第三十八页，共六十七页说明：说明：ntypedef 语句定义了一个结构体类型和链表类型语句

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

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

19、个结点类型的变量的语句：定义一个结点类型的变量的语句：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本讲稿第四十一页，共六十七页v链表的建立链表的建立 1.构造一个构造一个空线性链表空线性链表 首先，构造一个空的线性链表。为了描述方便，通首先，构造一个空的线性链表。为了描述方便，通常将链表的第一个结点空置，不存放数

20、据元素，只常将链表的第一个结点空置，不存放数据元素，只是作为链表的开始标志，称为是作为链表的开始标志，称为头结点头结点。数据元素从。数据元素从链表的第二个结点开始存放。链表的第二个结点开始存放。空的线性表空的线性表定义为没有数据元素的表定义为没有数据元素的表。一个空的线性一个空的线性链表就规定为，只有一个头结点的链表。链表就规定为，只有一个头结点的链表。所以，所以，构造构造一个空的线性链表就是建立只有一个头结点的链表。一个空的线性链表就是建立只有一个头结点的链表。42本讲稿第四十二页，共六十七页程序：程序：/*构造一个空的线性链表*/LNode*InitList()LinkList L;/头结

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

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

23、入第一个结点之后：插入第一个结点之后：an头结点46本讲稿第四十六页，共六十七页n插入第二个结点之后：插入第二个结点之后：n 插入第三个结点之后：插入第三个结点之后：n插入最后一个结点之后：插入最后一个结点之后：an-1anan-1an-2anan-1a1an 47本讲稿第四十七页，共六十七页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(

24、!p)exit(0);scanf(%d,&p-data);p-next=L-next;L-next=p;return L;程序：头结点头结点头插入头插入48本讲稿第四十八页，共六十七页v链表结点的插入n将一个数据元素插入到链表中，有三种情况：将一个数据元素插入到链表中，有三种情况：头头插入插入，尾插入尾插入以及以及在链表中的第在链表中的第i i个数据元素的位置个数据元素的位置处插入处插入。n将一个新元素插入在链表的头结点的后面，其它的将一个新元素插入在链表的头结点的后面，其它的所有结点之前称为所有结点之前称为头插入头插入。n将一个新元素插入在链表的尾结点的后面，使得新插将一个新元素插入在链表的

25、尾结点的后面，使得新插入的结点成为尾结点称为入的结点成为尾结点称为尾插入尾插入。n将一个新元素插入在链表中的第将一个新元素插入在链表中的第i i个数据元素的位个数据元素的位置处置处，即插入在第，即插入在第i i个数据元素结点之前，使得新个数据元素结点之前，使得新插入的结点成为链表中的第插入的结点成为链表中的第i i个结点。个结点。49本讲稿第四十九页，共六十七页例：已有链表例：已有链表L 如图所示如图所示,链表中的元素按递增链表中的元素按递增有序排列：有序排列：其中每个结点中存放的值为学生的考试成绩。现在有另其中每个结点中存放的值为学生的考试成绩。现在有另外三个学生的的成绩分别为外三个学生的的

26、成绩分别为65、82、90。将他们插入。将他们插入到链表到链表L中，要求插入之后链表依然递增有序。中，要求插入之后链表依然递增有序。pLq70808550本讲稿第五十页，共六十七页将将6565插入到链表插入到链表L L中中:s sp pL q65708085头插入头插入51本讲稿第五十一页，共六十七页将将8282插入到链表插入到链表L L中中:s sp pLq6570808285中间插入52本讲稿第五十二页，共六十七页将将9090插入到链表插入到链表L L中中:s sp=p=Lq657080828590尾插入53本讲稿第五十三页，共六十七页实现语句实现语句：LNode*p,*q,*s;Link

27、List 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本讲稿第五十四页，共六十七页程序：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本讲稿第

28、五十五页，共六十七页v链表结点的删除例：已有链表如图所示：删除链表中数据元素值为76的结点。80657690 qpL56本讲稿第五十六页，共六十七页80657690 qpL80657690 qpL806590 qL57本讲稿第五十七页，共六十七页程序程序: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本讲稿第五十八页，共六十七页#in

29、clude#include#include struct Node int data;struct Node *next;typedef struct Node LNode;typedef struct Node*LinkList;综合程序综合程序59本讲稿第五十九页，共六十七页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);i

30、f(!p)exit(0);scanf(%d,&p-data);p-next=L-next;L-next=p;return L;60本讲稿第六十页，共六十七页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本讲稿第六十一页，共六十七页int ListDelete (LNode *L,

31、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本讲稿第六十二页，共六十七页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)/释放链表元素释放链表元素 L

32、Node*p;p=L-next;free(L);while(p)printf(free:%dn,p-data);L=p-next;free(p);p=L;63本讲稿第六十三页，共六十七页void main()LNode*LinkHead;LinkHead=CreateList(3);/创建链表创建链表ListPrint(LinkHead);/显示链表数据显示链表数据ListInsert(LinkHead,65);/插入元素插入元素ListInsert(LinkHead,82);/插入元素插入元素ListInsert(LinkHead,90);/插入元素插入元素ListPrint(LinkHea

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