第十二章第十二章 动态数据组织动态数据组织n动态数据结构动态数据结构n动态变量动态变量n链表链表n程序设计实例程序设计实例n本章小结本章小结作业作业: 12.4 12.16 习题集：习题集：P13318 练习练习: 12.3 12.8 12.10-12.14 例例12.1 打印打印n阶法雷序列。对任意给定的自然数阶法雷序列。对任意给定的自然数 n ，把所有如下形式的不可约分数把所有如下形式的不可约分数 按递增顺序排列起来，称该序列为按递增顺序排列起来，称该序列为 n 级法雷序列级法雷序列 Fn 。 例如例如F8 为为: 编函数，对任意给定的正整数编函数，对任意给定的正整数n ，求，求n级法雷序列级法雷序列.12.1 打印法雷序列打印法雷序列-动态数据结构动态数据结构解：算法可以考虑为：顺序分别以解：算法可以考虑为：顺序分别以i=1,2,3, . ,n 作分母，对任作分母，对任意意i以以j=1,2, . , i作分子，作成分数作分子，作成分数j/i；若；若j/i是不可约分数，则该是不可约分数，则该j/i必然是法雷序列的一项；把该必然是法雷序列的一项；把该j/i放入法雷序列中。得放入法雷序列中。得PAD。生成生成 n 阶阶法雷序列链表法雷序列链表结束结束for(i=2;i=n;i+)for(j=1; j=i; j+)把把 j/i放入序列放入序列 考虑数据存储。分析法雷序列的一项，它的每项是个分数，考虑数据存储。分析法雷序列的一项，它的每项是个分数，不能用实数精确的表示，使用分数形式表示它，分子、分母都为不能用实数精确的表示，使用分数形式表示它，分子、分母都为整数，分别存储它们。再分析法雷序列，怎样存储？用以前学习整数，分别存储它们。再分析法雷序列，怎样存储？用以前学习的知识，应该保存在数组中。这样，整个法雷序列将被保存在两的知识，应该保存在数组中。这样，整个法雷序列将被保存在两行行m列的一个两维数组中。列的一个两维数组中。 问题问题: 第一，数组多大？由于不知道第一，数组多大？由于不知道n阶法雷序列有多少项，阶法雷序列有多少项，就应该给一个足够大的就应该给一个足够大的m。 第二，操作问题：第二，操作问题： 1. n阶法雷序列是从一阶开始，逐步生成的。当向序列增加阶法雷序列是从一阶开始，逐步生成的。当向序列增加一项时，应该在数组中加一个元素，不管给定一项时，应该在数组中加一个元素，不管给定m多大，都会产生多大，都会产生数组不够大的可能。数组不够大的可能。 2. 由于法雷序列是有序的，当增加一项时，应该把当前项插由于法雷序列是有序的，当增加一项时，应该把当前项插入到合适的位置。后边的项必须依次向后移动。入到合适的位置。后边的项必须依次向后移动。 最好把法雷序列存储成动态的，需要多大存储量（有多少最好把法雷序列存储成动态的，需要多大存储量（有多少项）就用多大。中间加项时不要向后串别的项。如图的链式结项）就用多大。中间加项时不要向后串别的项。如图的链式结构正好可以满足这些要求。构正好可以满足这些要求。 123 .n 5050 在这种结构中，链上的一节是法雷序列的一项，有多少在这种结构中，链上的一节是法雷序列的一项，有多少项就有多少节。当增加一项时，只需要向计算机系统申请一块项就有多少节。当增加一项时，只需要向计算机系统申请一块空间，联到链的适当位置上。空间，联到链的适当位置上。 例如，要增加一项例如，要增加一项 50 插入到插入到 2 、3 之间，则只需要修改之间，则只需要修改指针：指针： 这种链式结构对于删除一项也十分方便，只需要将其从链上这种链式结构对于删除一项也十分方便，只需要将其从链上摘下来即可。删除摘下来即可。删除2节得：节得： 这就是这就是“动态存储结构动态存储结构”中的链表结构。使用如下链表结构生成中的链表结构。使用如下链表结构生成法雷序列法雷序列分子分子分母分母分子分子分母分母分子分子分母分母分子分子分母分母. 显然法雷序列的各项均在区间显然法雷序列的各项均在区间 0/1 ，1/1 之内。为操作之内。为操作简单，先把一阶法雷序列：简单，先把一阶法雷序列：0/1、1/1先放入链表中；先放入链表中； 接着，逐步把接着，逐步把j/i插入到链表的合适位置上，并使链表仍保插入到链表的合适位置上，并使链表仍保持按递增排序；持按递增排序； 最后，结束时把链表头指针带回主程序。最后，结束时把链表头指针带回主程序。生成法雷序列算法生成法雷序列算法l先把一阶法雷序列：先把一阶法雷序列：0/1,1/1放入链表中；放入链表中；l然后顺序分别以然后顺序分别以i=2,3, . ,n 作分母，对任意作分母，对任意i以以j=1,2, . , i-1作作 分子，作成分数分子，作成分数j/i；l若若j/i是不可约分数，则该是不可约分数，则该j/i必然是法雷序列的一项；把该必然是法雷序列的一项；把该j/i插入到链表的合适位置上，并使链表仍保持按递增排序。插入到链表的合适位置上，并使链表仍保持按递增排序。0/1 , 1/1 放入序列放入序列读入读入 n开始开始结束结束 for(i=2; i=n; i+) for(j=1; ji; j+)把把 j/i 放入序列放入序列j/i 不可不可约分约分把把 j/i 插入到插入到 r0,r 之间之间查查 j/i 应插入应插入的位置的位置 r0,r struct farlei_item int numerator , denominator ; struct farlei_item *next ;typedef struct farlei_item * farleipointer ;int gcd( int x , int y ) /* 求最大公约数求最大公约数 */ if ( y=0 ) return x ; else return gcd( y , x % y ) ;/*构造法雷序列构造法雷序列,并返回序列头指针并返回序列头指针*/farleipointer farlei(int n) int i,j ; farleipointer fn , r , r0 , p ; if( n1 ) /如果如果nnumerator = 0 ; fn-denominator = 1 ; fn-next = (farleipointer) malloc(sizeof(struct farlei_item); /构造构造1/1 fn-next-numerator = 1 ; fn-next-denominator = 1 ; fn-next-next = NULL ; /* 生成序列生成序列 */ for ( i=2; i=n; i+) for (j=1; jdenominator i*r-numerator ) r0 = r ; r = r-next ; /* j/i 插入到插入到 r0,r 之间之间 */ p = (farleipointer)malloc(sizeof(struct farlei_item); p-numerator = j ; p-denominator = i ; r0-next = p ; p-next = r ; return fn ;运行结果演示运行结果演示 动态数据结构上的一项是一个动态变量，动态数据结构上的一项是一个动态变量，指针是标识动态变量的有力手段。动态变量指针是标识动态变量的有力手段。动态变量与静态变量的区别在于与静态变量的区别在于: 静态变量是程序中由程序员静态变量是程序中由程序员“显式显式”说说明的变量。它有一个名字，在编译时，编译明的变量。它有一个名字，在编译时，编译程序已经给它分配存储空间。这块存储空间程序已经给它分配存储空间。这块存储空间用变量的名字来标识。用变量的名字来标识。12.2 动态变量动态变量 动态变量在程序中没有动态变量在程序中没有“显式显式”说明，它没有说明，它没有名字在编译时编译程序不知道有该变量，不给（也名字在编译时编译程序不知道有该变量，不给（也不可能给）它分配空间。不可能给）它分配空间。 动态变量是在程序运行时动态变量是在程序运行时随程序存储数据的需要，申请空间函数（例如随程序存储数据的需要，申请空间函数（例如malloc，当然也是由程序员安排的）随机的动态，当然也是由程序员安排的）随机的动态的申请来的空间。它没有名字，一般动态变量都的申请来的空间。它没有名字，一般动态变量都由指针标识。由指针标识。当使用完毕后，由释放空间函数（例如当使用完毕后，由释放空间函数（例如free）释）释放，还回计算机存储管理系统，以备它用。放，还回计算机存储管理系统，以备它用。n注意：这里所说的静态变量不是注意：这里所说的静态变量不是C语言中由语言中由静态存储类别静态存储类别static声明的变量；动态变量声明的变量；动态变量也不是也不是C语言中由自动存储类别语言中由自动存储类别auto声明的声明的变量。而是一般程序设计概念中的静态变量、变量。而是一般程序设计概念中的静态变量、动态变量动态变量目标代码空间目标代码空间静态区空间静态区空间库代码空间库代码空间堆区空间堆区空间栈区空间栈区空间 内存内存 程序运行时，涉及用户程序的内存存储程序运行时，涉及用户程序的内存存储结构如右图所示，首先是目标代码区；然后是结构如右图所示，首先是目标代码区；然后是静态存储区，用于存放那些可用绝对地址标识静态存储区，用于存放那些可用绝对地址标识的，主要是具有静态存储类别的数据和变量；的，主要是具有静态存储类别的数据和变量；接着是目标代码运行时用到的库程序代码区；接着是目标代码运行时用到的库程序代码区；最后剩余空间是栈区和堆区，栈区和堆区从剩最后剩余空间是栈区和堆区，栈区和堆区从剩余空间的两端，动态的向中间增长。栈区用来余空间的两端，动态的向中间增长。栈区用来存储程序中声明的函数的局部变量等具有自动存储程序中声明的函数的局部变量等具有自动存储类别的数据和变量；堆区用来存储经过动存储类别的数据和变量；堆区用来存储经过动态申请空间函数申请的变量。态申请空间函数申请的变量。nsizeof 运算符运算符单目运算符单目运算符 sizeof 的的操作数操作数是类型。是类型。运算结果运算结果是求得相应类型的尺寸，即存储相是求得相应类型的尺寸，即存储相应类型数据所需要的字节数。应类型数据所需要的字节数。sizeof(int) /* 结果是结果是2 */sizeof(char) /* 结果是结果是1 */sizeof(struct date) /* 若若 struct date 是第十是第十一章定义的日期类型，结果是一章定义的日期类型，结果是6 */nmalloc 函数函数:原型原型 void *malloc(unsigned long size);功能功能 申请足够大内存区域用来存储长度为申请足够大内存区域用来存储长度为size的数据对象，返回该区域的首指针，并保证该的数据对象，返回该区域的首指针，并保证该区域符合任何数据类型对存储区域开始地址和区域符合任何数据类型对存储区域开始地址和对齐的要求。对齐的要求。 返回指针是返回指针是void类型的，调用者必须使用类型的，调用者必须使用强制类型转换，把该指针转换成所需要类型的强制类型转换，把该指针转换成所需要类型的指针。指针。n例例:float *p ;p = (float*)malloc( sizeof(float) );struct date *pdate;pdate=(struct date*)malloc(sizeof(struct date); fn = (farleipointer)malloc(sizeof(struct farlei_item); nfree函数函数动态申请的内存如果不再使用，应当适时释放动态申请的内存如果不再使用，应当适时释放这样可以提高程序运行效率。这样可以提高程序运行效率。free函数用来释函数用来释放经过放经过malloc申请的动态空间。申请的动态空间。free的函数的函数原型原型 void free ( void *ptr ) ;功能功能释放由释放由malloc申请的内存区域。申请的内存区域。free的参数的参数ptr是一个指针，指向以前由是一个指针，指向以前由malloc申请的一申请的一个内存区域。个内存区域。n例例free(p);free(pdate);free(ptr) /* 释放释放ptr所指向由所指向由malloc申请的内存空间申请的内存空间 */一块存储区域一经释放，便不能再使用。使用一块存储区域一经释放，便不能再使用。使用free特特别注意，操作不当会产生不可预料的结果。如下情况别注意，操作不当会产生不可预料的结果。如下情况下使用下使用free都会造成灾难性后果。都会造成灾难性后果。ptr无值；无值；ptr的值为的值为NULL；ptr所指向的空间不是经过所指向的空间不是经过malloc申请来的；申请来的；对一次申请的存储区进行多次释放（实际可能是对一次申请的存储区进行多次释放（实际可能是ptr无值或值为无值或值为NULL）。）。n实用问题实用问题:若指针变量指向的用若指针变量指向的用malloc申请来的动态变量，是孤申请来的动态变量，是孤立的不能与其它变量相联系，显然作用不大。立的不能与其它变量相联系，显然作用不大。引进动态变量的目的是构造动态数据结构。引进动态变量的目的是构造动态数据结构。例如象本章开始介绍的那样，构造一个链表等。例如象本章开始介绍的那样，构造一个链表等。这就要求一个数据项上除基本的数据信息外，还应包这就要求一个数据项上除基本的数据信息外，还应包含与其它数据项相联系的信息，也就是包含指针。含与其它数据项相联系的信息，也就是包含指针。该结构必须用结构体类型描述，链表上一节的类型定该结构必须用结构体类型描述，链表上一节的类型定义形式。义形式。类型定义形式类型定义形式 struct t 基本数据部分；基本数据部分； struct t *next ; 基本数基本数据部分据部分指针部分指针部分一个数据项一个数据项 123 n.structstruct farlei_itemfarlei_item intint numerator , denominator ; / numerator , denominator ; / 分子、分母分子、分母 structstruct farlei_itemfarlei_item *next ; *next ;/ / 连接部分连接部分;法雷序列一项法雷序列一项13.3 13.3 链表链表base:1.2N-1N.双向链双向链base:12N-1N.单向链单向链base:12N-1N.环形链环形链base:12N-1N.双向双向环形链环形链13.3.1 13.3.1 单向链表单向链表不介绍全部的链表，只介绍一下单向链表。设有声明不介绍全部的链表，只介绍一下单向链表。设有声明: typedef . items ; typedef struct cell items data ; struct cell *predocessor ; celltype ; typedef celltype *ptype ; ptype top ; 单向链表结构如图所示单向链表结构如图所示rear:top:.n创建单向链表创建单向链表: : 创建单向链表，是指用一项一项的数据创建单向链表，是指用一项一项的数据逐步建立、形成一个链表。可以分成向链头逐步建立、形成一个链表。可以分成向链头加入数据和向链尾加入数据两种方式。加入数据和向链尾加入数据两种方式。设有声明设有声明: typedef . items ; typedef struct stackcell items data ; struct stackcell *predocessor ; stackcelltype ; typedef stackcelltype *pstacktype ; pstacktype top ; pstacktype p ;top:. .链表链表向链头加入数据算法如下：向链头加入数据算法如下：p = (pstacktype)malloc(sizeof(stackcelltype);p-data = x ;p-prodocessor = top ;top = p ;设有如下声明设有如下声明: typedef . items ; typedef struct queue items data struct queue *next ; queuetype ; typedef queuetype *pqueuetype ; pqueuetype front,rear ; pqueuetype p;rear:top:.向链尾加入数据算法如下：向链尾加入数据算法如下：向链尾加入数据算法如下：向链尾加入数据算法如下： p = (pqueuetype)malloc(sizeof(queuetype); p- data = x ; p- next = NULL ; if ( rear=NULL ) rear = p ; front = p ; else rear- next = p ; rear = p ; rear:top:.运行结果演示运行结果演示n遍历单向链表遍历单向链表: 遍历是指从头到尾将链表上数据全部加工一遍历是指从头到尾将链表上数据全部加工一遍历是指从头到尾将链表上数据全部加工一遍历是指从头到尾将链表上数据全部加工一遍。可用如下左端的算法。但实用中，经常用如遍。可用如下左端的算法。但实用中，经常用如遍。可用如下左端的算法。但实用中，经常用如遍。可用如下左端的算法。但实用中，经常用如下右端下右端下右端下右端 的算法来遍历单向链表。的算法来遍历单向链表。的算法来遍历单向链表。的算法来遍历单向链表。p = base ; p0 = NULL;while (p != NULL ) p = base ; 加工加工 p - while (p != NULL ) p = p- next; 加工加工 p - p0 = p ; p = p- next; n在单向链表上检索在单向链表上检索: 检索是指在单向链表上查找关键字等于某给定检索是指在单向链表上查找关键字等于某给定值的节点值的节点, 若找到则带回相应节点的指针；否则带若找到则带回相应节点的指针；否则带回回NULL 。设关键字域域名为。设关键字域域名为key ；欲检索的关键；欲检索的关键字值为字值为key0 . 如下算法实现检索：如下算法实现检索： p0 = NULL; p = base ; while (p != NULL & p-key !=key0 ) p0 = p; p = p- next; n向单向链表插入一项向单向链表插入一项: 设有下图的链表，现在要把设有下图的链表，现在要把r所指示的数据项插所指示的数据项插入到入到 p0、p 所指两项之间。操作是所指两项之间。操作是: r- next = p ; p0- next = r ; p0 = r /* 使使 p0 仍为仍为 p 的前一项的前一项 */r:5p0: p: 1 2 3 4.n从单向链表上删除一项从单向链表上删除一项: 设有下图的链表，现在要删除设有下图的链表，现在要删除p所指项。删除所指项。删除算法是：算法是： q = p ; p = p- next ; p0- next = p ; free(q)p0:1234.p:q:n交换单向链表上两项交换单向链表上两项: 设有如图所示链表。现在要把设有如图所示链表。现在要把 p 所指的项与所指的项与 q 所指所指的项交换的项交换 为了表示操作方便，我们把该链表分两段画出。为了表示操作方便，我们把该链表分两段画出。p0p123.q0 q456.p0:p:123.q0q:456. g:/*交换交换 p- next 、q- next */ g = p- next; /* 1 */ p- next = q- next; /* 2 */ q- next = g; /* 3 */ /*交换交换 p0- next 、q0- next */ p0- next = q; /* 4 */ q0- next = p; /* 5 */*交换交换 p 、q */ p = p0- next ; /* 6 */ q = q0- next ; /* 7 */12.4 程序设计实例程序设计实例n一个排序算法一个排序算法n多项式加法多项式加法例例12.2 排序算法排序算法n数组排序已经很熟悉，而且有各种各样的算法。下边用逐数组排序已经很熟悉，而且有各种各样的算法。下边用逐步增加递增子序列的方法实现链表排序。设有说明步增加递增子序列的方法实现链表排序。设有说明: typedef . datatype ; struct item datatype data ; int key ; struct item *next ; ;typedef struct item *pt以以base为链首的链表如下图所示。该算法的思想是为链首的链表如下图所示。该算法的思想是:开始假设空序列是递增的开始假设空序列是递增的若若i个元素子序列已经递增，则加一个元素，把插入到序列中个元素子序列已经递增，则加一个元素，把插入到序列中一个适当位置使一个适当位置使i+1个元素的子序列也递增个元素的子序列也递增直到直到i=n为止为止datakeydatakeydatakeydatakey.base:开始开始p = basep!=NULL使使basep递增递增p0 = p ;p = p-next结束结束return base使使basep递增递增寻找寻找p应该插入的位置应该插入的位置r0,rp插入到插入到r0、r之间之间结束结束p插入到插入到r0、r之间之间结束结束defrp把把p独立出来独立出来=q ;p指向指向p0插入到插入到r0,r之间之间:q-next = r ; r0-next = q插入到链头插入到链头:q-next = base ; base = qr = base寻找位置寻找位置r = base r-keykey r!=pr0 = r;r = r-next 结束结束def考查程序运行中各个参数、变量、链表的变化状态。如图所示：考查程序运行中各个参数、变量、链表的变化状态。如图所示：设从设从base到到p0之间的子链表已经递增，现在加入之间的子链表已经递增，现在加入p所指示的节；所指示的节；在在basep0之间查找合适位置，设应该把之间查找合适位置，设应该把p所指的节插入到所指的节插入到r0,r所之间；所之间；把把p独立出来独立出来=q ， p指向指向p0： q = p ; p0-next = p-next ; p = p0 ;把把p（现在由（现在由q指示）插入到指示）插入到r0,r之间：之间： q-next = r ; r0-next = q；现在链表结构是：现在链表结构是：datakeydatakey.datakeydatakeybase:datakeydatakeydatakeydatakeyr0:r:p:p0:q:pt sort( pt base ) /* 链表排序，链表排序，base 为链首为链首 */ pt p , p0 , r , r0 , q ; p0 = NULL ; p = base ; while ( p!=NULL ) /* 逐项处理，把逐项处理，把p加入到子序列中，并保持加入到子序列中，并保持“base-p”递增递增 */ r = base ; /* 寻找位置寻找位置 */ while ( ( r-key key ) & ( r!=p ) ) r0 = r ; r = r- next ; if (r!=p) /* p插入到插入到r0、r之间之间 */ /* 若若 r=p ，在链尾，则不用插入，在链尾，则不用插入 */ q = p ; /* 把把 p 独立出来，令独立出来，令 q 指向它指向它 */ p0-next = p-next ; p = p0 ; if ( r = base ) /* 插入插入 */ /* 插在链首插在链首 */ q-next = base ; base = q ; else /* 插在链中插在链中r0 、r之间之间 */ q-next = r ; r0 - next = q ; p0 = p ; /* 前进一项前进一项 */ p = p-next ; return base ; /* sort */ 运行结果演示运行结果演示例例12.3多项式加法多项式加法多项式可以用如下形式的链表来存储；多项式可以用如下形式的链表来存储；幂次幂次系数系数.幂次幂次系数系数幂次幂次系数系数幂次幂次系数系数56.523.41100.5例如多项式例如多项式可以表示成如下形式可以表示成如下形式:编一个函数，实现多项式加法：编一个函数，实现多项式加法：p(X)+q(X) = s(X) 。设有类型说明：设有类型说明：struct item float coef; int exp; struct item *next;typedef struct item *polynome;解解:在本程序的算法中，在链表上利用了一个哨兵项。在本程序的算法中，在链表上利用了一个哨兵项。所谓哨兵是在链表的链首多加一节，该节不存储有效的所谓哨兵是在链表的链首多加一节，该节不存储有效的链表项的值，而保存一个边界值或空值，本程序的哨兵链表项的值，而保存一个边界值或空值，本程序的哨兵项是空值。由于利用了哨兵变量，所以处理统一了。多项是空值。由于利用了哨兵变量，所以处理统一了。多项式加法的算法如下图：项式加法的算法如下图：开始开始p = s ; p = p-next p+q=s;q = q-next; p = p-next q=s; q = q-next 结束结束(p!=NULL)&(q!=NULL)p -expq -exp p!=NULL q!=NULLp=s; p = p-nextq=s; q = q-nextp-expexp程序如下：程序如下：void adds( int exp0 , float coef0 ，polynome *r ) /* 向向s加入一项加入一项 */ polynome r0; r0 = ( polynome)malloc( sizeof(struct item) ); r0-exp = exp0; r0-coef = coef0; r0-next = NULL; (*r)-next=r0;polinome addpolynome(polinome p, polinome q ) polinome s ，r / s为结果多项式链首；为结果多项式链首；r 始终指向结果多项式始终指向结果多项式s的最低次幂项。的最低次幂项。 /* 申请一个哨兵变量申请一个哨兵变量 ，以便算法统一，以便算法统一 */ s = (polynome)malloc( sizeof(struct item) ); r = s; while ( (p!=NULL)&(q!=NULL) ) /* 相加相加 */ if ( p-exp q-exp ) adds( p-exp , p-coef ，&r ); p = p-next; else if ( p-exp exp ) adds( q-exp , q-coef ，&r ); q = q-next; else adds( p-exp , p-coef+q-coef ，&r ); q = q-next; p = p-next; r=r-next;运行结果演示运行结果演示/* p 多项式尾多项式尾 */ while (p!=NULL) adds( p-exp , p-coef ，&r ); p = p-next; r=r-next; /* q 多项式尾多项式尾 */ while (q!=NULL) adds( p-exp , p-coef ，&r ); q = q-next;r=r-next; /* 释放哨兵变量释放哨兵变量 */ r = s; s = s-next; free(r); return s ;n n本章讲述十分重要的动态数据结构，包括：本章讲述十分重要的动态数据结构，包括：本章讲述十分重要的动态数据结构，包括：本章讲述十分重要的动态数据结构，包括：动态数据结构概念、动态数据结构概念、简单的动态数据结构简单的动态数据结构链表。链表。 重点掌握动态数据结构的操作重点掌握动态数据结构的操作重点掌握动态数据结构的操作重点掌握动态数据结构的操作本章小结本章小结