资源描述
第七章动态数据结构,目录,态数据结构,本章开始介绍动态数据结构，主要介绍链表结构的建立、在链表中查找指定元素、插入一个新元素、删除一个元素等操作。学完本章内容后，要求深刻理解动态存储结构的概念，并正确运用。,7.1从静态数据结构到动态数据结构,在此之前，我们涉及到的都是静态数据结构，像数组、简单类型(int、float)等。静态数据结构的特点是由系统分配固定大小的存储空间，以后在程序运行的过程中，存储空间的位置和容量都不会再改变。而实际生活中常常有这样的问题，数据量的多少是动态变化的。,7.1从静态数据结构到动态数据结构,例如，图书馆的藏书量，在图书馆初建时，假设有10000本，随着时间的推移，藏书的数量必定要增加。有人可能会想，在定义一个静态变量时，预留出一部分空间，但这也会引起一些问题，首先多出的那部分空间不知何时才能使用，在没有被使用之前一直被闲置；其次，谁又能保证增加的空间就足够呢？,7.1从静态数据结构到动态数据结构,问题的关键在于，此问题的数据本身就是变化的，而且是不确定的变化，什么时候变、怎么变都是未知的。对这样的问题用静态存储结构来描述和存放显然捉襟见肘，存在隐患。动态数据结构不确定总的数据存储量，而是为现有的每一个数据元素定义一个确定的初始大小的空间，若干个数据元素分配若干个同样大小的空间；当问题的数据量发生变化时，数据的存储空间的大小也发生变化。如果数据量增加，就重新向系统申请新的空间；如果数据量减少，就将现有的多余的空间归还给系统。,7.2.动态内存分配,使用计算机解决问题的所有方法都是通过使用系统提供给我们的基本命令或函数来实现的。所以首先让我们来看看，c的标准函数中有哪些是用于动态内存分配的，怎样使用。,7.2.1ANSIC中动态内存操作标准函数,ANSIC中提供了若干个动态内存操作标准函数，它们的名称分别是malloc、calloc、realloc、free等。这些函数可以使用在任何的C环境中。,1malloc函数,malloc函数是C的标准函数之一。原型定义在malloc.h文件中。原型为：void*malloc(unsignedintsize);其作用是向系统申请一个确定大小(size个字节)的存储空间，返回值为一个指向void类型的分配域起始地址的指针值。如果此函数操作失败，返回值为空。,1malloc函数,使用格式：指针型变量=(基类型*)malloc(需要的存储空间的字节数);例7-1：为一个整数分配存储空间，需要的语句为：在文件的头部：#include在说明部分：int*p;在程序中：p=(int*)malloc(sizeof(int);,测试malloc的程序举例：,#include#include#includevoidmain()int*p;/*定义一个指向整型的指针变量*/intx;p=(int*)malloc(sizeof(int);if(!p)exit(0);p=,2calloc函数,calloc函数是C的标准函数之一。原型定义在malloc.h文件中。原型为：void*calloc(unsignedintn,unsignedintsize);其作用是向系统申请n个大小为size个字节的连续存储空间，返回值为一个指向void类型的分配域起始地址的指针值。如果此函数操作失败，返回值为空。可以为一维数组开辟一片连续的动态存储空间。,2calloc函数,使用格式：指针型变量=(数组元素类型*)calloc(n,每一个数组元素的存储空间的字节数)；例7-2：为一个有10个整数的一维数组分配存储空间，需要的语句为：在文件的头部：#include在说明部分：int*p;在程序中：p=(int*)calloc(10,sizeof(int);,使用calloc函数程序举例：,#include#include#includemain()int*p;intx;p=(int*)calloc(10,sizeof(int);if(!p)exit(0);for(i=0;idata=10;p-next=NULL;deletep;,new与malloc的相同点是他们的作用都是在程序的执行过程中向系统申请存储空间，返回值都是申请到的存储空间的首地址，不同点是，malloc是c编译系统提供的标准库函数，new是c+系统提供的运算符，new的操作效率要高于malloc；new不需要使用显式的sizeof函数就能知道名字的大小，而malloc需要明确指出所申请的空间的大小(总的字节数)；new的返回值是指向名字类型的确定的指针类型，不需要强制说明，而malloc的返回值是一个指向void类型的指针类型，需要强制转换成指向具体数据类型的指针类型。当所申请的空间是一个变量所需的空间时，new运算符还可以为所申请的空间赋初值，malloc不具有此功能。,7.3链表,计算机处理数据需要两方面的工作，一方面是对数据信息的描述，另一方面是对数据的操作，而操作的方式取决于数据的描述方式，数据的描述方式又取决于数据本身固有的内在联系。这里仅介绍数据之间的线性关系。对于图书馆的藏书这类数据信息可以用一种称为线性表的动态数据结构来描述。简单的说，线性表是n个数据元素的有限序列。各数据元素属于同一数据对象，相邻数据元素之间存在序偶关系。记为：（a1，a2，ai，ai+1，an）,线性表中的数据元素之间存在严格的顺序关系，有一个唯一的称为第一个的元素（首元），有唯一的称为最后一个的元素（尾元），其它元素都有唯一的直接后继元素和唯一的直接前趋元素。线性表这种逻辑结构在计算机内表示时，可以采用链式存储结构，即一个数据元素存放于一个结点中，不同的数据元素之间的先后顺序用结点的指针域链接。一个结点就是一个结构体类型的变量。,7.3.1链表的定义,链表是表示具有线性关系的一组数据元素的动态结构。每一个数据元素占据一个独立申请的存储空间，这个存储空间通常是一个结构体型变量，主要包括两部分，一部分用来存放数据元素的值称为值域，另一部分用来存放一个指向该结构体类型的指针变量值称为指针域。指针域的作用是存放逻辑上排在本结点后面的结点的存储空间的首地址。数据元素结点的结构如图所示：,若干个结点首尾相连按照其逻辑顺序链接成一排，称为线性链表。单向链表如下图所示：,图7.2单向链表,1.链表结点的C语句定义,对于链表这种数据结构，ANSIC中，按如下方式描述：首先用结构体类型描述一个数据元素结点，定义一个结点类型的语句格式：typedefstructLNodeElemTypedata；structLNode*next；LNode，*LinkList；,其中：,typedef语句定义了一个结构体类型和链表类型LNode是一个结点的类型名称。它有两个成员，一个名称为data，类型为数据元素的类型，用来存放一个数据元素的值；另一个成员名称为next，类型为指向本结构体类型的指针类型，用来存放逻辑上排在本结点后面的结点的首地址。LinkList是指向LNode类型的指针类型。ElemType是数据元素的类型的一般性描述，当我们具体写程序时，应该用确定类型名称来替换，例如，int、float、char等。,例7-6：链表中的数据元素用来存放整数，定义链表的结点类型的语句格式为：typedefstructLNodeintdata；structLNode*next；LNode，*LinkList；,定义一个指向结点类型的指针类型变量的语句：LNode*p;3定义一个链表类型的指针变量：LinkListL;4访问结点变量p的各个成员：p-data,p-next说明：本章的所有程序都是基于以上类型定义。,7.3.2链表的建立,1.构造一个空线性链表L首先，构造一个空的线性链表。为了描述方便，通常将链表的第一个结点空置，不存放数据元素，只是作为链表的开始标志，称为头结点。数据元素从链表的第二个结点开始存放。空的线性表定义为没有数据元素的表。一个空的线性链表就规定为，只有一个头结点的链表。所以，构造一个空的线性链表就是建立只有一个头结点的链表。,（1）算法描述:申请一个结点的空间；将该结点作为线性链表的头结点；将该结点的next域置空；,（2）完整程序（Example7_6.cpp）:,/*程序名：Example7_6.cpp*/voidInitList(LinkList*L)/*构造一个空的线性链表*/(*L)=(LNode*)malloc(sizeof(LNode)；/*申请一个结点空间*/if(!（*L）)exit(0)；/*申请不成功，异常结束程序运行*/（*L）-next=NULL；/*申请成功，头结点的next域置空*/return(1)；,2逆序输入n个数据元素，建立带表头结点的单线性链表L,现在开始建立一个非空的线性链表。我们这里所建的链表的第一个结点都是头结点。数据元素从链表的第二个结点开始存放。一个非空的线性链表是除了头结点以外至少有一个数据元素的链表。线性链表由若干个数据元素结点组成。那么，构造一个非空的线性链表的过程就是逐个建立数据元素结点，并将它们依次插入到链表中的过程。,所谓头插入，即每次将数据元素结点插入到表头结点的之后，第一个数据元素结点之前。插入过程如图7-3所示：,初始状态：,插入第一个结点之后：,插入第二个结点之后：,插入第三个结点之后：,插入最后一个结点之后：,voidCreateList(LinkList*L，intn)inti;LNode*P;(*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”,以上的算法只是建立链表的一种方法，它的核心是新的数据元素结点插在链表的第一个数据元素的位置；我们也可以将新建立的数据元素结点每次都插在链表的尾部，大家可以思考一下，以尾插入的方式建立链表，程序怎样编写？,7.3.3链表结点的插入,将一个数据元素插入到链表中，有三种情况：头插入，尾插入以及在链表中的第i个数据元素的位置处插入。将一个新元素插入在链表的头结点的后面，其它的所有结点之前称为头插入。将一个新元素插入在链表的尾结点的后面，使得新插入的结点成为尾结点称为尾插入。将一个新元素插入在链表中的第i个数据元素的位置处，即插入在第i个数据元素结点之前，使得新插入的结点成为链表中的第i个结点。下面我们详细介绍每一种插入的算法实现。,例7-8：已有链表L如图所示,链表中的元素按递增有序排列：,图7.4链表的插入过程其中每个结点中存放的值为学生的考试成绩。现在有另外三个学生的的成绩分别为65、82、90。将他们插入到链表L中，要求插入之后链表依然递增有序。,图7.5头插入过程,首先将65插入到链表L中:插入的过程：设p=L-next，因为p非空，判断p-data65,所以，65应该插在L的后面，70结点的前面，插入之后的链表为：L:,80,70,85,s,p,实现语句：,p=L-next;s=(LNode*)malloc(sizeof(LNode);s-data=x;s-next=p;L-next=s;,将82插入到链表L中:,插入的过程：首先应找到82应在的位置：82应该插在两个结点之间，82前面结点的data域值小于82；82后面结点的data域值大于等于82；如图所示：L:,实现语句：,q=*L;p=(*L)-next;while(p,将90插入到链表L中:,显然，90应插到链表的尾部，即：插到链表的最后一个结点的后面。插入的过程：首先找到插入的位置：设p=L-next，当p非空并且p-datanext;循环一定以p为空结束。将新结点90插在q的后面，插入之后的链表为：,L:,实现语句：,x=90;p=L-next;s=(LNode*)malloc(sizeof(LNode);s-data=x;while(pq-next=s;s-next=p;,用一个程序来实现，程序如下：,intListInsert(LNode*L，inte)LNode*s，*q,*p;if(!(*L)return0；s=(LNode*)malloc(sizeof(LNode)；if(!s)exit(0)；s-data=e；p=(*L)-next;q=*L;,while(pq-next=s；return(1)；,7.3.4链表结点的删除,在7.3.3节中，详细的讨论了在一个链表中插入一个数据元素结点的算法。本节将讨论删除链表中的结点的算法。例7-9：已有链表L如图所示：,删除链表中数据元素值为76,解答：首先查找值为76的结点：设p=L-next，q=L;L:,q,p,当p非空时，判断p-data=76吗？如果成立，则p所指的结点就是所要删除的结点；此时，q指示所要删除的结点的前驱结点；否则，继续查找；即p和q指针同时向后移。找到了值为76的结点：,q,p,删除p所指的结点：,删除之后的链表为：,q,p,程序如下:,intListdelete(LNode*L，int*e)LNode*q,*p;if(!(*L)return0；p=(*L)-next;q=*L;while(p,7.4小结,本章介绍了线性链表的定义和建立算法，又介绍了插入一个结点、删除一个结点等算法的实现。通过这一章的学习，我们初步了解了动态数据结构的特点和使用方式。还有许多的动态数据结构，如堆栈、队列、树、图等。它们都被广泛的应用于计算机系统中，在计算的系统和应用软件中起着非常重要的作用。动态数据结构的更详细内容将在后续课程数据结构讲述。,思考题：,只设尾指针的单循环链表的初始化、建立、插入和删除算法应怎样写？,
展开阅读全文