C语言动态数据结构_第1页
C语言动态数据结构_第2页
C语言动态数据结构_第3页
C语言动态数据结构_第4页
C语言动态数据结构_第5页
已阅读5页,还剩57页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

会计学1C语言动态数据结构态数据结构本章开始介绍动态数据结构,主要介绍链表结构的建立、在链表中查找指定元素、插入一个新元素、删除一个元素等操作。学完本章内容后,要求深刻理解动态存储结构的概念,并正确运用。第1页/共62页7.1从静态数据结构到动态数据结构在此之前,我们涉及到的都是静态数据结构,像数组、简单类型(int、float)等。静态数据结构的特点是由系统分配固定大小的存储空间,以后在程序运行的过程中,存储空间的位置和容量都不会再改变。而实际生活中常常有这样的问题,数据量的多少是动态变化的。第2页/共62页7.1从静态数据结构到动态数据结构例如,图书馆的藏书量,在图书馆初建时,假设有10000本,随着时间的推移,藏书的数量必定要增加。有人可能会想,在定义一个静态变量时,预留出一部分空间,但这也会引起一些问题,首先多出的那部分空间不知何时才能使用,在没有被使用之前一直被闲置;其次,谁又能保证增加的空间就足够呢?第3页/共62页7.1从静态数据结构到动态数据结构问题的关键在于,此问题的数据本身就是变化的,而且是不确定的变化,什么时候变、怎么变都是未知的。对这样的问题用静态存储结构来描述和存放显然捉襟见肘,存在隐患。动态数据结构不确定总的数据存储量,而是为现有的每一个数据元素定义一个确定的初始大小的空间,若干个数据元素分配若干个同样大小的空间;当问题的数据量发生变化时,数据的存储空间的大小也发生变化。如果数据量增加,就重新向系统申请新的空间;如果数据量减少,就将现有的多余的空间归还给系统。第4页/共62页7.2.动态内存分配使用计算机解决问题的所有方法都是通过使用系统提供给我们的基本命令或函数来实现的。所以首先让我们来看看,c的标准函数中有哪些是用于动态内存分配的,怎样使用。第5页/共62页7.2.1ANSIC中动态内存操作标准函数ANSIC中提供了若干个动态内存操作标准函数,它们的名称分别是malloc、calloc、realloc、free等。这些函数可以使用在任何的C环境中。第6页/共62页1.malloc函数malloc函数是C的标准函数之一。原型定义在malloc.h文件中。原型为:void*malloc(unsignedintsize);其作用是向系统申请一个确定大小(size个字节)的存储空间,返回值为一个指向void类型的分配域起始地址的指针值。如果此函数操作失败,返回值为空。第7页/共62页1.malloc函数使用格式:指针型变量=(基类型*)malloc(需要的存储空间的字节数);例7-1:为一个整数分配存储空间,需要的语句为:在文件的头部:#include<malloc.h>

在说明部分:int*p;

在程序中:p=(int*)malloc(sizeof(int));第8页/共62页测试malloc的程序举例:#include<malloc.h>#include<stdio.h>#include<stdlib.h>voidmain(){int*p;/*定义一个指向整型的指针变量*/intx;p=(int*)malloc(sizeof(int));if(!p)exit(0);p=&x;scanf(“%d”,p);printf(“x=%d”,x);

}第9页/共62页2.calloc函数calloc函数是C的标准函数之一。原型定义在malloc.h文件中。原型为:void*calloc(unsignedintn,unsignedintsize);其作用是向系统申请n个大小为size个字节的连续存储空间,返回值为一个指向void类型的分配域起始地址的指针值。如果此函数操作失败,返回值为空。可以为一维数组开辟一片连续的动态存储空间。第10页/共62页2.calloc函数使用格式:指针型变量=(数组元素类型*)calloc(n,每一个数组元素的存储空间的字节数);例7-2:为一个有10个整数的一维数组分配存储空间,需要的语句为:在文件的头部:#include<malloc.h>

在说明部分:int*p;

在程序中:p=(int*)calloc(10,sizeof(int));

第11页/共62页使用calloc函数程序举例:#include<malloc.h> #include<stdio.h> #include<stdlib.h> main(){int*p;intx;p=(int*)calloc(10,sizeof(int));if(!p)exit(0);for(i=0;i<10;i++) {scanf(“%d”,&x);*(p+i)=x;} for(i=0;i<10;i++) printf(“%6d”,*(p+i));}第12页/共62页3.realloc函数realloc函数是C的标准函数之一。原型定义在malloc.h文件中。原型为:void*realloc(void*p,unsignedintsize);其作用是向系统重新申请一个确定大小的存储空间,并将原存储空间中的数据值传送到新的地址空间的低端,返回值为一个指向void类型的分配域起始地址的指针值。如果此函数操作失败,返回值为空。原存储空间的数据将丢失。第13页/共62页3.realloc函数使用格式:指针型变量=(基类型*)realloc(原存储空间的首地址,新的存储空间的字节数);例7-3:现有一个为10个整数分配的存储空间,其首地址为p1;由于数据量的增加,原存储空间已满,需要扩大原空间为20个整数的大小;需要的语句为:在文件的头部:#include<malloc.h>

在说明部分:int*p2;

在程序中:p2=(int*)realloc(p1,sizeof(int)*20);第14页/共62页程序举例:

#include<malloc.h>#include<stdio.h>#include<stdlib.h>main(){int*p1,*p2;intx;p1=(int*)malloc(sizeof(int)*10);if(!p1)exit(0);p2=(int*)realloc(p1,sizeof(int)*20);if(!p2)exit(0);}第15页/共62页realloc函数主要的用于当原分配空间已被占满,而新的数据又要加入到该空间时的状况。它的优点是可以自动地将原空间的内容全部传递到新空间中,不必程序员再编语句来实现。缺点是一旦新空间申请失败,原空间的内容也将丢失。对这一点,使用时应加以注意。第16页/共62页4.free函数

free函数是

C的标准函数之一。原型定义在malloc.h文件中,原型为:voidfree(void*p)其作用是释放由p所指的内存区,将一个存储空间归还给系统。使用格式:

free(指针型变量);例7-4:将一个已分配存储空间释放,需要的语句为在文件的头部:#include<malloc.h>

在说明部分:int*p;

在程序中:free(p)第17页/共62页程序举例:#include<malloc.h>#include<stdio.h>#include<stdlib.h>main(){int*p;p=(int*)malloc(sizeof(int));if(!p)exit(0);free(p);}第18页/共62页c++中为进行动态操作提供的运算符——new和delete在软件的研制过程中,程序中动态申请内存空间和释放内存空间是一件很常见的事,前面一节中,我们讲解了ANSIC中的办法。利用标准库函数malloc、calloc、reallloc、free等。但malloc、calloc、reallloc等函数都要求程序设计者知道应开辟空间的确切大小,返回值的类型需要强制类型转换。c++中对此进行了改进,为进行动态内存操作提供了运算符new和delete,来代替malloc和free。但在c++中依然保留了malloc和free,以便和C兼容。第19页/共62页1.new运算符new是c++中提供的用于开辟一个动态存储空间的运算符。new运算符的一般格式:变量指针=new类型(初值);例如:(1)申请一个存放整数的空间:语句格式:p=newint;执行结果:开辟了一个整数大小的空间,并将该空间的首地址送入指向整型数据的指针变量p中。第20页/共62页(2)申请一个存放字符型数据的空间,并为该空间赋初值‘a’:语句格式:p=newchar(‘a’);执行结果:开辟了一个字节大小的空间,并将该空间的首地址送入指向字符型数据的指针变量p中。P所指空间中的数据值为字符’a’。(3)申请一个存放实数的空间:语句格式:p=newfloat(1.414);执行结果:开辟了一个实数大小的空间,并将该空间的首地址送入指向实型数据的指针变量p中。并将该空间中赋入初值1.414。第21页/共62页(4)申请一个存放10个实数的数组的空间:语句格式:p=newfloat[10];执行结果:开辟了一个10个实数大小的空间,将该空间的首地址送入指向实型数据的指针变量p中。注意:用new为数组分配空间不能指定初值。第22页/共62页2.delete运算符:delete运算符是c++中的提供的实现动态内存释放功能的运算符,类似于标准库函数free。一般格式为:delete名字指针;例如:(1)释放一个存放整数的空间:如果p=newint;则释放一个存放整数的空间的语句为:deletep;执行结果:将该整数空间释放掉,即将该资源归还给系统。第23页/共62页2.delete运算符:(2)释放一个存放10个实数的数组的空间:如果:p=newfloat[10];则释放一个数组空间的语句为:delete[]p;执行结果:将该数组空间释放掉,即将该资源归还给系统。第24页/共62页2.delete运算符:new试图创建一个名字类型的对象,向系统申请sizeof(名字)个字节大小的空间。新对象的生存周期始于创建点,直到delete将其释放或到程序结束。如果申请成功,返回指向新对象的指针;若返回的指针为空指针,表示动态空间分配失败。注意:delete只能用于用new分配的内存的释放。第25页/共62页例7-5申请一个结构体类型的存储空间,用来存放相应类型的数据。解决问题要点:包含相关的头文件;定义一个结构体类型;定义结构体类型的变量;申请空间;对指定空间赋值;释放申请的空间;第26页/共62页程序举例:#include<stdio.h>#include<stdlib.h>#include<malloc.h>#include<string.h>typedefstructLNode{intdata;structLNode*next;}LNode;main(){LNode*p;p=newLNode;if(!p)exit(0);p->data=10;p->next=NULL; deletep;}第27页/共62页new与malloc的相同点是他们的作用都是在程序的执行过程中向系统申请存储空间,返回值都是申请到的存储空间的首地址,不同点是,malloc是c编译系统提供的标准库函数,new是c++系统提供的运算符,new的操作效率要高于malloc;new不需要使用显式的sizeof函数就能知道名字的大小,而malloc需要明确指出所申请的空间的大小(总的字节数);new的返回值是指向名字类型的确定的指针类型,不需要强制说明,而malloc的返回值是一个指向void类型的指针类型,需要强制转换成指向具体数据类型的指针类型。当所申请的空间是一个变量所需的空间时,new运算符还可以为所申请的空间赋初值,malloc不具有此功能。第28页/共62页7.3链表计算机处理数据需要两方面的工作,一方面是对数据信息的描述,另一方面是对数据的操作,而操作的方式取决于数据的描述方式,数据的描述方式又取决于数据本身固有的内在联系。这里仅介绍数据之间的线性关系。 对于图书馆的藏书这类数据信息可以用一种称为线性表的动态数据结构来描述。简单的说,线性表是n个数据元素的有限序列。各数据元素属于同一数据对象,相邻数据元素之间存在序偶关系。记为:(a1,a2,…,ai,ai+1,…,an)第29页/共62页线性表中的数据元素之间存在严格的顺序关系,有一个唯一的称为第一个的元素(首元),有唯一的称为最后一个的元素(尾元),其它元素都有唯一的直接后继元素和唯一的直接前趋元素。 线性表这种逻辑结构在计算机内表示时,可以采用链式存储结构,即一个数据元素存放于一个结点中,不同的数据元素之间的先后顺序用结点的指针域链接。一个结点就是一个结构体类型的变量。第30页/共62页7.3.1链表的定义链表是表示具有线性关系的一组数据元素的动态结构。每一个数据元素占据一个独立申请的存储空间,这个存储空间通常是一个结构体型变量,主要包括两部分,一部分用来存放数据元素的值——称为值域,另一部分用来存放一个指向该结构体类型的指针变量值——称为指针域。指针域的作用是存放逻辑上排在本结点后面的结点的存储空间的首地址。数据元素结点的结构如图所示:值域指针域第31页/共62页若干个结点首尾相连按照其逻辑顺序链接成一排,称为线性链表。单向链表如下图所示:a1a2……an-1an^图7.2单向链表第32页/共62页1.链表结点的C语句定义对于链表这种数据结构,ANSIC中,按如下方式描述:首先用结构体类型描述一个数据元素结点,定义一个结点类型的语句格式:

typedefstructLNode{ ElemTypedata;structLNode*next;

}LNode,*LinkList;第33页/共62页其中:typedef语句定义了一个结构体类型和链表类型LNode是一个结点的类型名称。它有两个成员,一个名称为data,类型为数据元素的类型,用来存放一个数据元素的值;另一个成员名称为next,类型为指向本结构体类型的指针类型,用来存放逻辑上排在本结点后面的结点的首地址。LinkList是指向LNode类型的指针类型。ElemType是数据元素的类型的一般性描述,当我们具体写程序时,应该用确定类型名称来替换,例如,int、float、char等。第34页/共62页例7-6:链表中的数据元素用来存放整数,定义链表的结点类型的语句格式为:

typedefstructLNode{ intdata;

structLNode*next;

}LNode,*LinkList;第35页/共62页定义一个指向结点类型的指针类型变量的语句:LNode*p;3.定义一个链表类型的指针变量:LinkListL;4.访问结点变量p的各个成员:p->data,p->next说明:本章的所有程序都是基于以上类型定义。 第36页/共62页7.3.2链表的建立1.构造一个空线性链表L首先,构造一个空的线性链表。为了描述方便,通常将链表的第一个结点空置,不存放数据元素,只是作为链表的开始标志,称为头结点。数据元素从链表的第二个结点开始存放。空的线性表定义为没有数据元素的表。一个空的线性链表就规定为,只有一个头结点的链表。所以,构造一个空的线性链表就是建立只有一个头结点的链表。第37页/共62页(1)算法描述:申请一个结点的空间;将该结点作为线性链表的头结点;将该结点的next域置空;第38页/共62页(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);

}第39页/共62页2.逆序输入n个数据元素,建立带表头结点的单线性链表L现在开始建立一个非空的线性链表。我们这里所建的链表的第一个结点都是头结点。数据元素从链表的第二个结点开始存放。一个非空的线性链表是除了头结点以外至少有一个数据元素的链表。线性链表由若干个数据元素结点组成。那么,构造一个非空的线性链表的过程就是逐个建立数据元素结点,并将它们依次插入到链表中的过程。第40页/共62页所谓头插入,即每次将数据元素结点插入到表头结点的之后,第一个数据元素结点之前。

插入过程如图7-3所示:∧初始状态:插入第一个结点之后:an∧第41页/共62页插入第二个结点之后:插入第三个结点之后:插入最后一个结点之后:an-1an∧an-1an-2an∧an-1a1an∧……第42页/共62页voidCreateList(LinkList*L,intn){ inti; LNode*P;(*L)=(LNode*)malloc(sizeof(LNode));if(!(*L))exit(0);(*L)->next=NULL;for(i=n;i>0;i--){p=(LNode*)malloc(sizeof(LNode));if(!p))exit(0);scanf(“%d”,&p->data);p->next=(*L)->next;(*L)->next=p;}return(1);}第43页/共62页以上的算法只是建立链表的一种方法,它的核心是新的数据元素结点插在链表的第一个数据元素的位置;我们也可以将新建立的数据元素结点每次都插在链表的尾部,大家可以思考一下,以尾插入的方式建立链表,程序怎样编写?第44页/共62页7.3.3链表结点的插入将一个数据元素插入到链表中,有三种情况:头插入,尾插入以及在链表中的第i个数据元素的位置处插入。将一个新元素插入在链表的头结点的后面,其它的所有结点之前称为头插入。将一个新元素插入在链表的尾结点的后面,使得新插入的结点成为尾结点称为尾插入。将一个新元素插入在链表中的第i个数据元素的位置处,即插入在第i个数据元素结点之前,使得新插入的结点成为链表中的第i个结点。下面我们详细介绍每一种插入的算法实现。第45页/共62页例7-8:已有链表L如图所示,链表中的元素按递增有序排列:图7.4链表的插入过程其中每个结点中存放的值为学生的考试成绩。现在有另外三个学生的的成绩分别为65、82、90。将他们插入到链表L中,要求插入之后链表依然递增有序。807085∧第46页/共62页图7.5头插入过程首先将65插入到链表L中:插入的过程:设p=L->next,因为p非空,判断p->data>65,所以,65应该插在L的后面,70结点的前面,插入之后的链表为:L:

65807085∧sp65s第47页/共62页实现语句:

p=L->next;s=(LNode*)malloc(sizeof(LNode));s->data=x;s->next=p;L->next=s;第48页/共62页将82插入到链表L中:插入的过程:首先应找到82应在的位置:82应该插在两个结点之间,82前面结点的data域值小于82;82后面结点的data域值大于等于82;如图所示:L:65807085∧82第49页/共62页实现语句:q=*L;p=(*L)->next;while(p&&p->data<x) {q=p;p=p->next;}第50页/共62页将90插入到链表L中:

显然,90应插到链表的尾部,即:插到链表的最后一个结点的后面。插入的过程:首先找到插入的位置:设p=L->next,当p非空并且p->data<90,做:q=p;p=p->next;循环一定以p为空结束。将新结点90插在q的后面,插入之后的链表为:第51页/共62页L:6580708590∧第52页/共62页实现语句:x=90;p=L->next;s=(LNode*)malloc(sizeof(LNode));s->data=x;while(p&&p->data<x){q=p;p=p->next; }q->next=s;s->next=p;}第53页/共62页用一个程序来实现,程序如下: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;

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论