C语言第9章2动态数据结构(二级C的内容,可参考).ppt

1,1,第九章 结构体和指针,2,结构体概述 结构体类型和结构体变量的定义 结构体类型变量的引用 结构体与数组 结构体和指针 动态链表,主要内容,动态数据结构,本节开始介绍动态数据结构，主要介绍链表结构的建立、在链表中查找指定元素、插入一个新元素、删除一个元素等操作。 学完本节内容后，要求深刻理解动态存储结构的概念，并正确运用。,3,6 动态链表,6.1 从静态数据结构到动态数据结构 6.2 动态内存分配（4个函数） 6.3 链 表 6.4 小 结,6.1 从静态数据结构到动态数据结构,在此之前，我们涉及到的都是静态数据结构，像数组、简单类型(int、float)等。 静态数据结构的特点是由系统分配固定大小的存储空间，以后在程序运行的过程中，存储空间的位置和容量都不会再改变。 而实际生活中常常有这样的问题，数据量的多少是动态变化的。,5,6.1 从静态数据结构到动态数据结构,例如，图书馆的藏书量，在图书馆初建时，假设有10000本，随着时间的推移，藏书的数量必定要增加。 有人可能会想，在定义一个静态变量时，预留出一部分空间，但这也会引起一些问题， 首先多出的那部分空间不知何时才能使用，在没有被使用之前一直被闲置； 其次，谁又能保证增加的空间就足够呢？而且图书馆藏书也有减少的可能。,6,6.1 从静态数据结构到动态数据结构,问题的关键在于，此问题的数据本身就是变化的，而且是不确定的变化，什么时候变、怎么变都是未知的。 对这样的问题用静态存储结构来描述和存放显然捉襟见肘，存在隐患。,7,6.1 从静态数据结构到动态数据结构,动态数据结构不确定总的数据存储量，而是为现有的每一个数据元素定义一个确定的初始大小的空间，若干个数据元素分配若干个同样大小的空间；当问题的数据量发生变化时，数据的存储空间的大小也发生变化。 如果数据量增加，就重新向系统申请新的空间；如果数据量减少，就将现有的多余的空间归还给系统。,8,6.2 动态内存分配,使用计算机解决问题的所有方法都是通过使用系统提供给我们的基本命令或函数来实现的。所以首先让我们来看看，c的标准函数中有哪些是用于动态内存分配的，怎样使用。 ANSI C 中动态内存操作标准函数 ANSI C中提供了若干个动态内存操作标准函数，它们的名称分别是malloc、calloc、realloc、free等。这些函数可以使用在任何的C环境中。 c+ 中为进行动态操作提供了运算符new和delete,9,1malloc函数,malloc函数是 C的标准函数之一。 原型定义在malloc.h文件中。 原型为：void *malloc(unsigned int size); 其作用是向系统申请一个确定大小(size 个字节)的存储空间，返回值为一个指向void类型的分配域起始地址的指针值。如果此函数操作失败，返回值为空。 使用格式： 指针型变量 =(基类型*)malloc(需要的存储空间的字节数);,10,1malloc函数,malloc函数是 C的标准函数之一。原型定义在malloc.h文件中。 原型为： void *malloc(unsigned int size); 其作用是向系统申请一个确定大小(size 个字节)的存储空间，返回值为一个指向void类型的分配域起始地址的指针值。如果此函数操作失败，返回值为空。 使用格式： 指针型变量 =(基类型*)malloc(需要的存储空间的字节数);,指针有确定的数据类型，如果想把其他类型赋给某个类型指针，编译器会发出警告。为了解决这个问题，C语言引用了void *类型，即表示malloc函数的返回值可以指向任何类型。,为什么malloc函数返回值是void *而不是其它类型？,11,例：为一个整数申请一个存储空间,需要的语句为： 在文件的头部：#include 在说明部分： int *p; 在程序中：p = ( int * ) malloc ( sizeof ( int ) ) ; 说明： 动态管理内存的标准函数的说明在malloc.h中。 动态管理内存的标准函数的返回值都是指向void 类型的指针类型。在程序中需要的是指向具体类型的指针变量，应该进行强制类型转换，使得到的指针为指向确定类型的指针值。,12,测试malloc的程序举例：,13,测试malloc的程序举例：,14,2calloc函数,calloc函数是 C的标准函数之一。 原型定义在malloc.h文件中。 原型为： void *calloc(unsigned int n , unsigned int size); 其作用是向系统申请 n 个大小为size 个字节的连续存储空间，返回值为一个指向void类型的分配域起始地址的指针值。如果此函数操作失败，返回值为空。可以为一维数组开辟一片连续的动态存储空间。,15,例：为一个有10个整数的一维数组分配存储空间,使用格式： 指针型变量 =(数组元素类型*)calloc(n , 每一个数组元素的存储空间的字节数)； 需要的语句为： 在文件的头部：#include 在说明部分： int *p; 在程序中：p = (int *)calloc( 10 , sizeof(int) ;,16,程序：,#include #include #include void main() int *p; int x,i; p =(int *)calloc(10, sizeof(int); if(!p) exit(0) ; printf(“p=%ldn“, p); for(i=0;i10;i+) scanf(“%d“, ,17,程序：,#include #include #include void main() int *p; int x,i; p =(int *)calloc(10, sizeof(int); if(!p) exit(0) ; printf(“p=%ldn“, p); for(i=0;i10;i+) scanf(“%d“, ,18,将该问题作以下修改：不申请空间，看结果如何？,19,程序：,#include #include #include void main() int *p; int x,i; /*p =(int *)calloc(10, sizeof(int); */ /* if(!p) exit(0) ; */ printf(“p=%ldn“, p); for(i=0;i10;i+) scanf(“%d“, ,20,3realloc函数,realloc函数是 C的标准函数之一。原型定义在malloc.h文件中。 原型为：void *realloc( void *p, unsigned int size); 其作用是向系统重新申请一个确定大小的存储空间，并将原存储空间中的数据值传送到新的地址空间的低端，返回值为一个指向void类型的分配域起始地址的指针值。如果此函数操作失败，返回值为空。原存储空间的数据将丢失。,21,3realloc函数,使用格式： 指针型变量 =(基类型*)realloc( 原存储空间的首地址，新的存储空间的字节数)； realloc 函数主要的用于当原分配空间已被占满，而新的数据又要加入到该空间时的状况。 优点是可以自动地将原空间的内容全部传递到新空间中，不必程序员再编语句来实现。 缺点是一旦新空间申请失败，原空间的内容也将丢失。对这一点，使用时应加以注意。,22,例：现有一个为10个整数分配的存储空间，其首地址为p1; 由于数据量的增加，原存储空间已满，需要扩大原空间为20个整数的大小；,需要的语句为： 在文件的头部：#include 在说明部分： int *p2; 在程序中： p2 = ( int * )realloc( p1, sizeof( int ) * 20 );,23,程序：,#include #include #include void main() int *p1,*p2; int i; p1 =(int *)malloc(sizeof(int)*10); if(!p1) exit(0) ; for(i=0;i10;i+) scanf(“%d“, p1+i); printf(“p1=%u, p1中的值：“, p1); for(i=0;i10;i+) printf(“%4d“, *(p1+i); printf(“n“); p2 =(int *)realloc(p1,sizeof(int)*20); if(!p2) exit(0) ; printf(“p2=%u, p2中的值：“, p2); for(i=0;i20;i+) printf(“%4d“, *(p2+i); printf(“n“); ,24,4free函数,原型为：void free (void *p) 其作用是释放由p所指的内存区，将一个存储空间归还给系统。 使用格式：free(指针型变量); 例7-4：将一个已分配存储空间释放: 需要的语句为 在文件的头部：#include 在说明部分： int *p; 在程序中：free( p ),25,程序举例：,#include #include #include void main() int *p1; int i; p1 =(int *)malloc(sizeof(int)*10); if(!p1) exit(0) ; for(i=0;i10;i+) scanf(“%d“, p1+i); printf(“p1=%u, p1中的值：“, p1); for(i=0;i10;i+) printf(“%4d“, *(p1+i); printf(“n“); free(p1); printf(“free 之后 p1=%u, p1中的值：“, p1); for(i=0;i10;i+) printf(“%4d“, *(p1+i); printf(“n“); ,28,6.3 链 表,计算机处理数据需要两方面的工作，一方面是对数据信息的描述，另一方面是对数据的操作，而操作的方式取决于数据的描述方式，数据的描述方式又取决于数据本身固有的内在联系。这里仅介绍数据之间的线性关系。 数据本身固有的内在联系称为数据的逻辑结构。有很多种。譬如，线性关系、层次关系、网状（图）关系等，我们这里仅介绍数据之间的线性关系。,29,6.3 链 表,对于图书馆的藏书这类数据信息可以用一种称为线性表的动态数据结构来描述。 简单的说，线性表是 n 个数据元素的有限序列。 各数据元素属于同一数据对象，相邻数据元素之间存在序偶关系。 记为：（a1，a2，ai，ai+1，an）,30,线性表中的数据元素之间存在严格的顺序关系，有一个唯一的称为第一个的元素（首元），有唯一的称为最后一个的元素（尾元），其它元素都有唯一的直接后继元素和唯一的直接前趋元素。 线性表这种逻辑结构在计算机内表示时，可以采用链式存储结构，即一个数据元素存放于一个结点中，不同的数据元素之间的先后顺序用结点的指针域链接。一个结点就是一个结构体类型的变量。,31,1 链表的定义,链表是表示具有线性关系的一组数据元素的动态结构。每一个数据元素占据一个独立申请的存储空间，这个存储空间通常是一个结构体型变量， 主要包括两部分，一部分用来存放数据元素的值，称为值域，另一部分用来存放一个指向该结构体类型的指针变量值，称为指针域。 指针域的作用是存放逻辑上排在本结点后面的结点的存储空间的首地址。 数据元素结点的结构如图所示：,32,若干个结点首尾相连按照其逻辑顺序链接成一排，称为线性链表。 单向链表如下图所示：,单向链表,33,2 链表结点的 C 语句定义,首先用结构体类型描述一个数据元素结点，定义一个结点类型的语句格式： typedef struct LNode ElemType data； struct LNode *next； LNode，*LinkList；,34,typedef struct LNode ElemType data； struct LNode *next； LNode，*LinkList；,LNode 是一个结点的类型名称。它有两个成员，一个名称为data ，类型为数据元素的类型，用来存放一个数据元素的值；另一个成员名称为next，类型为指向本结构体类型的指针类型，用来存放逻辑上排在本结点后面的结点的首地址。 LinkList 是指向 LNode 类型的指针类型。ElemType 是数据元素的类型的一般性描述，当我们具体写程序时，应该用确定类型名称来替换，例如，int、float 、char等。,typedef 语句定义了两个数据类型结构体类型（LNode）和链表类型（LinkList） ；,35,例：链表中的数据元素用来存放整数，定义链表的结点类型的语句格式为：,typedef struct LNode int data； struct LNode *next； LNode，*LinkList； 定义一个指向结点类型的指针类型变量的语句： LNode *p ; 定义一个链表类型的指针变量：LinkList L; 访问结点变量 p 的各个成员： p-data , p-next 说明：本章的所有程序都是基于以上类型定义。,36,3 链表的建立,构造一个空线性链表 L ： 为了描述方便，通常将链表的第一个结点空置，不存放数据元素，只是作为链表的开始标志，称为头结点。数据元素从链表的第二个结点开始存放。 空的线性表定义为没有数据元素的表。 一个空的线性链表就规定为，只有一个头结点的链表。 所以，构造一个空的线性链表就是建立只有一个头结点的链表。,37,算法描述: 申请一个结点的空间； 将该结点作为线性链表的头结点； 将该结点的 next 域置空； 完整程序 void InitList ( LinkList L ) L=(LNode*)malloc(sizeof(LNode); if ( !L) exit ( 0 ); L-next = NULL; ,38,4逆序输入 n 个数据元素，建立带表头结点的单线性链表 L,现在开始建立一个非空的线性链表。我们这里所建的链表的第一个结点都是头结点。数据元素从链表的第二个结点开始存放。 一个非空的线性链表是除了头结点以外至少有一个数据元素的链表。线性链表由若干个数据元素结点组成。那么，构造一个非空的线性链表的过程就是逐个建立数据元素结点，并将它们依次插入到链表中的过程。,39,所谓头插入，即每次将数据元素结点插入到表头结点的之后，第一个数据元素结点之前。 插入过程如图所示：,初始状态：,插入第一个结点之后：,40,插入第二个结点之后：,插入第三个结点之后：,插入最后一个结点之后：,41,完整程序：,#include #include #include typedef struct LNode int data; struct LNode *next; LNode,*LinkList;,42,void CreateList ( LinkList L, int n ) int i; LNode *p; printf(“现在建立链表：n“); for ( i = n;i 0;i-) printf(“请输入第%d个结点的元素值：n“,i); p=(LNode*)malloc(sizeof(LNode); if ( !p ) exit (0); scanf(“%d“, ,43,void main() LNode *L,*p; int n; printf(“请输入链表中的元素个数：“); scanf(“%d“, ,44,以上的算法只是建立链表的一种方法，它的核心是新的数据元素结点插在链表的第一个数据元素的位置； 我们也可以将新建立的数据元素结点每次都插在链表的尾部。 大家可以思考一下，以尾插入的方式建立链表，程序怎样编写？,48,5 链表结点的插入,将一个数据元素插入到链表中，有三种情况： 头插入：将一个新元素插入在链表的头结点的后面，其它的所有结点之前称为头插入。 尾插入：将一个新元素插入在链表的尾结点的后面，使得新插入的结点成为尾结点称为尾插入。 在链表中的第i个数据元素的位置处插入：将一个新元素插入在链表中的第i个数据元素的位置处，即插入在第i个数据元素结点之前，使得新插入的结点成为链表中的第i个结点。,49,例：已有链表L 如图所示,链表中的元素按递增有序排列：,其中每个结点中存放的值为学生的考试成绩。现在有另外三个学生的的成绩分别为65、82、90。将他们插入到链表L中，要求插入之后链表依然递增有序。,链表的插入过程,L,50,头插入过程,将 65 插入到链表L中: 为65申请一个结点空间，首地址放入s中；,p,将s插入到链表中：,设p=L-next，,L,p-data65吗？,不小于！,65应在p结点之前。,即s插在L结点之后。,L-next=s;,s-next=p;,51,实现语句：,p=L-next; s=(LNode*)malloc(sizeof(LNode); s-data=x; s-next=p; L-next=s; 插入之后的链表状态：,L,52,将82 插入到链表L中:,插入的过程： 首先应找到82 应在的位置： 82应该插在两个结点之间，82前面结点的data域值小于82；82后面结点的data域值大于等于82；如图所示： L:,53,实现语句：,q=L; p=L-next; while( p ,插入之后的链表：,54,插入过程：,q=L;,while( p ,p=L-next;,s,L,q,p,p,q,p,q,p,q,q-next=s; s-next=p;,p,55,将90 插入到链表L中:,显然，90应插到链表的尾部，即：插到链表的最后一个结点的后面。 插入的过程： 首先找到插入的位置：设p=L-next，当p非空并且 p-data next; 循环一定以p为空结束。 将新结点90插在q的后面，插入过程如下：,56,找到90结点应该的位置之后：,L:,p=NULL,q,s,s-next=NULL,q-next=s,57,实现语句：,x=90; p=L-next; s=(LNode*)malloc(sizeof(LNode); s-data=x; while( p ,58,用一个函数来实现，程序如下：,void ListInsert(LNode *L,int e ) LNode *s,*q, *p; if ( !(*L) ) exit(0); s = ( LNode* ) malloc ( sizeof ( LNode ); if ( !s ) exit ( 0 ); s-data = e; p=L-next ; q=L;,while ( p ,59,6 链表结点的删除,例：已有链表L 如图所示：,60,删除链表中数据元素值为76,首先查找值为76的结点： 设p=L-next，q=L;,q,p,L:,61,当p非空时，判断p-data=76吗？如果成立，则p所指的结点就是所要删除的结点；此时，q指示所要删除的结点的前驱结点；否则，继续查找；即p和q指针同时向后移。找到了值为76的结点：,q,p,62,删除p所指的结点：,删除之后的链表为：,80,76,90,q,p,q-next=p-next;,free(p);,63,程序如下:,int Listdelete ( LNode *L, int *e ) LNode *q, *p; if ( !L ) return 0; p=L-next ; q=L; while ( p ,64,6.4 小 结,本节介绍了线性链表的定义和建立算法，又介绍了插入一个结点、删