【文档说明】-C程序设计课件第12章-PPT.ppt，共(92)页，943.512 KB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-2197.html

以下为本文档部分文字说明：

第十二章动态数据结构◼管理动态变量◼动态数据结构–栈──stack–队列──queue–链表——linkagetable–树——tree–图——graph◼程序设计实例◼本章小结◼作业◼考虑上一章的职工卡

片问题，用计算机管理这些卡片,要把卡片保存在计算机内。◼首先，用什么数据结构存储：一张卡片是一个结构体，所有卡片自然用结构体数组。◼第三，操作问题：–若增加一个人，应该在数组中加一个元素，会产生数组不够大的可能。–若增加一张卡片在数组中间，应该把加入位置以后的其它元素依次向后移动

。–若在中间删除一张卡片，会在数组中间留下一个“洞”，应该把“洞”以后的元素依次向前移动◼使用数组带来的问题是：–操作不方便；–数组尺寸不好确定。第二，数组多大：为保存全部卡片，并且人数不固定，就应该给一

个足够大的数组。◼最好把这些卡片存储成动态的，–需要多大存储量（有多少张卡片）就用多大。–中间加一张卡片时不要向后串别的卡片，–删除一张卡片时不要留下“洞”。如图的链式结构可以满足要求:◼当增加一张卡片时，只需要向计算机系统申请一块空间，联到链的适当位置上。例如，要增加一张卡

片50插入到2、3之间，则只需要如下修改指针：◼若删除一节，只需要将其从链上摘下来即可。例删除2节得链上已经没有2节了，删掉的节所占的存储空间还可以还回计算机系统，以便作其它用途。123…n.50◼这就是一种动态数据结构中的——链

表。动态数据结构上的一项是一个动态变量，指针是标识动态变量的有力手段。动态变量与静态变量的区别在于:◼静态变量是程序中由程序员“显式”说明的变量。它有一个名字，在编译时，编译程序已经给它分配存储空间。这块存储空间用变量的名字来标识。◼动

态变量在程序中没有“显式”说明，它没有名字◼在编译时编译程序不知道有该变量，不给（也不可能给）它分配空间。◼动态变量是在程序运行时–随程序存储数据的需要，申请空间函数（例如malloc，当然也是由程序员安排的）随机的动态的申请来的空间。

它没有名字，一般动态变量都由指针标识。–当使用完毕后，由释放空间函数（例如free）释放，还回计算机存储管理系统，以备它用。◼注意：这里所说的静态变量不是C语言中由静态存储类别static声明的变量；动态变量也不是C语言中由自动存储类别auto声明的变量。而是一般

程序设计概念中的静态变量、动态变量管理动态变量◼动态变量在程序运行时，随程序存储数据的需要，向计算机系统申请；使用完后还回计算机系统。◼本节介绍–申请计算机存储空间函数malloc–释放存储空间函数free目标代码空间静态区空间库代

码空间堆区空间栈区空间内存程序运行时，涉及用户程序的内存存储结构如右图所示，首先是目标代码区；然后是静态存储区，用于存放那些可用绝对地址标识的，主要是具有静态存储类别的数据和变量；接着是目标代码运行时用到的库程序代码区；最后剩余空间是栈区和堆区，栈区和堆区从剩余空间的两端，动态的向中间增长。栈区用

来存储程序中声明的函数的局部变量等具有自动存储类别的数据和变量；堆区用来存储经过动态申请空间函数申请的变量。◼sizeof运算符–单目运算符sizeof的▪操作数是类型。▪运算结果是求得相应类型的尺寸，即存储相应类型数据所需要的字节数。–sizeof(int)/*结果是2*/–sizeof(c

har)/*结果是1*/–sizeof(structdate)/*若structdate是第十一章定义的日期类型，结果是6*/◼malloc函数:–原型void*malloc(unsignedlongsize);–功能申请足够大内存区域用来存储长度为size的数据对象，返回该区域的首指针，并保

证该区域符合任何数据类型对存储区域开始地址和对齐的要求。返回指针是void类型的，调用者必须使用显示强制类型转换，把该指针转换成所需要类型的指针。◼例:float*p;p=(float*)malloc(sizeof(f

loat));structdate*pdate;pdate=(structdate*)malloc(sizeof(structdate));◼free函数–动态申请的内存如果不再使用，应当适时释放这样可

以提高程序运行效率。free函数用来释放经过malloc申请的动态空间。free的函数–原型voidfree(void*ptr);–功能释放由malloc申请的内存区域。free的参数ptr是一个指针，指向以前由malloc申请的一个内存区域。◼例–申请

float*p;p=(float*)malloc(sizeof(float));structdate*pdate;pdate=(structdate*)malloc(sizeof(structdate));–释放free(p);free(pdate);–free(p

tr)/*释放ptr所指向由malloc申请的内存空间*/–一块存储区域一经释放，便不能再使用。使用free特别注意，操作不当会产生不可预料的结果。如下情况下使用free都会造成灾难性后果。▪ptr无值；▪ptr的值为NULL；▪ptr所指向的空间不是经过malloc

申请来的；▪对一次申请的存储区进行多次释放（实际可能是ptr无值或值为NULL）。◼实用问题:–若指针变量指向的用malloc申请来的动态变量，是孤立的不能与其它变量相联系，显然作用不大。–引进动态变量的目的是构造动态数据结构。–例如象本章开始介绍的那样，构造

一个链表等。–这就要求一个数据项上除基本的数据信息外，还应包含与其它数据项相联系的信息，也就是包含指针。–该结构必须用结构体类型描述，链表上一节的类型定义形式。类型定义形式structt{基本数据部分；structt*next;}基本数据部分指针

部分一个数据项123…n.栈──stack◼在第六章已经用数组实现过栈和队列，但是，数组有一定的局限性。如图可以用单向链表实现栈，指针变量top指向栈顶。栈的操作有:①初始化：stackintial②压栈：stackpush③弹栈：stackpop设有声明:t

ypedef...items;typedefstructstackcell{itemsdata;structstackcell*predocessor;}stackcelltype;typedefstack

celltype*pstacktype;pstacktypetop;top:.......栈如下实现栈的操作：voidstackinitial(void){top=NULL;}voidstackpush(itemsx){pstacktypep;p=(pstacktype)mallo

c(sizeof(stackcelltype));p->data=x;p->prodocessor=top;top=p;}voidstackpop(items*x){pstacktypep;if(top!=NULL){*x=top->data;p=t

op;top=top->predecessor;free(p);}elseprintf(“栈下溢\n”);}看一下这三个操作:1.初始化后(调用stackinitail)得。2.调用一次stackpush(1)得。3.再调用一次s

tackpush(2)得。4.调用一次stackpop(&b)得。top:1.2b:2队列◼如图可用单向链表实现队列，现在要用两个指针变量，一个指向队头（front），一个指向队尾（rear）。队列的操

作有①初始化（queueinitial）②进队──排在队尾（inqueue）③出队──从队头删一项（outqueue）rear:front:....设有如下说明:typedef...items;typedefstructqueue

{itemsdatastructqueue*next;}queuetype;typedefqueuetype*pqueuetype;pqueuetypefront,rear;操作：voidqueueinital(void){front=N

ULL;rear=NULL;}voidinqueue(itemx){pqueuetypep;p=(pqueuetype)malloc(sizeof(queuetype));p->data=x;p->n

ext=NULL;if(rear==NULL){rear=p;front=p;}else{rear->next=p;rear=p;}}voidoutgueue(item*x){pqueuetypep;if(front==NULL)printf(“队空\n”);else

{*x=front->data;p=front;front=front->next;if(front==NULL)rear=NULL;free(p);}}看一下这三个操作:1.调用初始化后（调用一次queueinitail）得；2.调用一次ingueue(1)

得；再调用一次ingueue(2)得；再调用一次ingueue(3)得;3.调用一次outgueue(&a)得；再调用一次outgueue(&b)得;再调用一次outgueue(&a)得。1·a:re

ar:front:2·3·1p:b:23NULLNULL链表——linkagetablebase:1.2N-1N·...双向链base:12N-1N...单向链base:12N-1N...环形链base:12N-1N...双向环形链实际上前边讲的栈，队列都是单向链表，但是栈和队列只是单向链表

的两种特殊应用——操作只在头尾进行。下边介绍单向链表的一般操作:◼创建单向链表:创建单向链表，是指用一项一项的数据逐步建立、形成一个链表。可以分成向链头加入数据和向链尾加入数据两种方式。创建单向链表可以分成向链头加入数据和向链尾加入数据

两种方式。新项加入链头就是压栈的算法；新项加入链尾就是队列中入队的算法。只要反复调用那里的函数或将函数体放在循环语句中即可，这里不赘述。◼遍历单向链表:遍历是指从头到尾将链表上数据全部加工一遍。可用如下左端的算法。但实用中，经常

用如下右端的算法来遍历单向链表。p=base;p0=NULL;while(p!=NULL){p=base;加工p->while(p!=NULL){p=p->next;加工p->}p0=p;p=p->next;}◼在

单向链表上检索:检索是指在单向链表上查找关键字等于某给定值的节点,若找到则带回相应节点的指针；否则带回NULL。设关键字域域名为key；欲检索的关键字值为key0.如下算法实现检索：p0=NULL;p=b

ase;while(p!=NULL&&p->key!=key0){p0=p;p=p->next;}◼向单向链表插入一项:设有下图的链表，现在要把r所指示的数据项插入到p0、p所指两项之间。操作是:r->next=p;p0->next=r;p0=r/*

使p0仍为p的前一项*/r:5p0:p:1234......◼从单向链表上删除一项:设有下图的链表，现在要删除p所指项。删除算法是：q=p;p=p->next;p0->next=p;free(q)p0:1

234......p:q:◼交换单向链表上两项:设有如图所示链表。现在要把p所指的项与q所指的项交换为了表示操作方便，我们把该链表分两段画出。p0p123...q0q456......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*/树——tree◼两叉树，两叉树的每个数据项附带两个指针，分别指向它的两个

分支。两叉树的定义:–空是树；–一个结点连接两个不相交的树,仍为树；–所有结点具有相同的数据类型。*+-a/d*bcef(a+b/c)*(d–e*f)root:···········设ti为二叉树的一个结点，一

般ti由两部分组成：⚫基本数据部分------保存本结点上的基本数据；⚫指针部分连------接本结点以下的其它结点。结点ti的指针连接的结点称为ti的子结点，相应ti称为其子结点的父结点。ti的指针部分有两个指针：左指针、右指针。称ti

的左指针连接的部分为ti的左子树，ti的右指针连接的部分为ti的右子树。若左、右子树均空，则称ti为叶结点。ti78563124ti:◼为了检索操作方便，一般把两叉树组织成两叉检索树。两叉检索树的定义是：–设树中每个结点的数据部分有一个数据项k

ey是有序的,称该数据项为关键字。–一个两叉树称为检索树，–如果对每个结点ti，它的左子树中所有结点的key值都小于ti的key值；–ti的右子树中所有结点的key值都大于ti的key值。◼二叉检索树的操作有:–遍历–检索–插入一个结点–删除一个结点由于树是递归定义的，所以树的操

作用递归算法十分简洁。设有说明部分:typedef...keytype；typedef...datatype；typedefstructtree{keytypekey；datatypedata；str

ucttree*left；structtree*right；}treetype;typedeftreetype*treepointer；treepointerroot；◼遍历遍历二叉树是指按一定规律走遍树的每

个结点，使每一结点被访问一次，而且只被访问一次。在访问一个结点时，可以做任何信息加工工作。下例打印结点的data域，并设该域为char型的。◼遍历算法可分为前序，中序，后序遍历三种。–前序遍历：对任意一个结点ti来讲，先访问及处理该结点的数据域；然后遍历左子树；最后遍历右子

树。–中序遍历：对任意一个结点ti来讲，先遍历左子树；然后访问及处理该结点的数据域；最后遍历右子树。–后序遍历：对任意一个结点ti来讲，先遍历左子树；然后遍历右子树；最后访问及处理该结点的数据域。【例12-1

】设有下图所示树,这是由表达式(a+b/c)*(d-e*f)生成的树，这棵树反映了表达式的结构，同时也反映了表达式的运算次序。⚫前序遍历过程是：得到表达式的波兰表示式（运算符在两个运算分量前）。⚫前序遍历算法是：

voidpreorder(treepointerp){if(p!=NULL){printf(“%c”,p->data);preorder(p->left);preorder(p->right)}}*+-a/d*bcef＊＋a/bc-d*ef⚫中序遍历过程是：得到表达

式的原形式，只是没有括号。中序遍历算法是：voidinorder(treepointerp){/*中序遍历*/if(p!=NULL){inorder(p->left);printf(“%c”,p->data);in

order(p->right)}}*+-a/d*bcef＊＋a/bc-d*ef⚫后序遍历过程是：得到表达式的表达式的逆波兰表示式（运算符在两个运算分量之后）。后序遍历算法是：voidpostorder(tree

pointerp){/*后序遍历*/if(p!=NULL){postorder(p->left);postorder(p->right)printf(“%c”,p->data);}}*+-a/d*bcef＊＋a/bc-d*ef◼检

索检索是按给定关键字值c在树上找一个结点ti，且ti的关键字值key恰好等于c。若检索到，函数将带回相应结点指针；否则若没检索到，函数将带回NULL。下述检索算法的前提条件是，p是检索树。treepointersearc

h(typekeyc,treepointerp){if((p->key==c)||(p==NULL))returnp;elseif(c<p->key)returnsearch(c,p->left);elsereturnsearch(c,p->right);}◼插

入一个结点插入是指将一个数据项插入到树中某一恰当位置，使树仍保持检索树的性质。显然，首先要按key值查出应该插入的位置，然后再插入。voidinsert(keytypec,datatyped,treepoint

er*p){if(*p==NULL){*p=(treepointer)malloc(sizeof(structtree));(*p)->key=c;(*p)->data=d;(*p)->left=NULL;(*p)

->right=NULL;}elseif(c<(*p)->key)insert(c,d,&((*p)->left));elseinsert(c,d,&((*p)->right));}由于insert的参数p是指向指针的指针类型，在insert内p指向

指针类型的实在参数。所以在执行*p=(treepointer)malloc(sizeof(structtree))时，将使实在参数指针变量指向新申请来的结点。1)若调用insert时，如图root为空树。以&root作实在参数调用insert,即insert(c,d,

&root)insert的形式参数p指向root，而root值为NULL。转插入功能，执行*p=(treepointer)malloc(sizeof(structtree))得:再执行后边的几个赋值语句,得:root:c;d··p:2)若调用insert时，root非空，在中间某

一个结点查到空指针，如图；设查到该结点后，应该继续向右查，以&((*p)->right)作实在参数递归调用insert，即执行insert(c,d,&((*p)->right))insert的形式参数p指向本步的(*p)->right，而

(*p)->right值为NULL。转插入功能，执行*p=(treepointer)malloc(sizeof(structtree))再执行后边的几个赋值语句,得:c;d··......p:◼删除一结点设欲删除结点为r，则可能有

如下几种情况。针对不同情况删除算法不同.r是叶结点:简单删掉r结点，并把r的父结点连接处改成NULL即可。42513r:r只有一个左子树78563124r:78564231r:r只有一个子树:把r以下部分接入r

的父结点连接r处。然后删掉r结点。r只有一个右子树r两个方向都有子树:在r的左子树上找到关键字key值最大的结点s，把s结点的数据data及关键字key复制到r结点上，然后删除掉s结点。9s:10r:4514151213312118679当然也可以在r的右子树上找到关

键字key值最小的结点s，把s结点的数据data及关键字key复制到r结点上，然后删除掉s结点。8s:5r:410131411123129766使用在左子树上找最大结点的方法，按如下步骤进行:①沿r左子树的右方向，向下找一个没有右子树的结点s，图中结点(

9)。②把该结点s的值复制到结点r（即欲删除的结点。③把s的左子树连在s的父结点（图中为结点(5)）的右链上，在图中即连到(5)结点的右链上。④删除s结点，即图中的(9)结点。图3的情况r两个方向都有子树:在

r的左子树上找到关键字key值最大的结点s，把s结点的数据data及关键字key复制到r结点上，然后删除掉s结点。9s:10r:4514151213312118679综合上述三种情况，下述函数dele

tenode完成删除一个结点。deletenode的调用形式是：deletenode(valueofkey,&root)其中⚫value_of_key是欲删除结点的关键字值；⚫root是指针类型（treep

ointer）变量，指向树根。这里用指向指针的指针作参数。treepointerdel(treepointer*,treepointer*)；/*处理第三种情况的函数的函数原型*/voiddeletenode(keytypec,treepointer*p){/*删除关键字值等于c的结点

*/treepointerr;if(*p==NULL)printf(“notfound:%d\n”,c);elseif(c<(*p)->key)/*c<当前结点的key值，被删结点在左子树上*/delete

node(c,&((*p)->left));elseif(c>(*p)->key)/*c>当前结点的key值，被删结点在右子树上*/deletenode(c,&((*p)->right));else{r=*p;if(r->right

==NULL)*p=r->left/*右子树空，接左分支*/elseif(r->left==NULL)*p=r->right;/*左子树空，接右分支*/elser=del(&(r->left),p);/*左右均非空*/free(r);/*释放r*/}};45627138root:p:dele

tenode(4,&root)r:r只有一个左子树treepointerdel(treepointer*s,treepointer*p){/*处理第三种情况，仅第三种情况调用*/treepointerr;if((*s)->right!=NULL)/*右分支非空?*/r=del(&((*s)->ri

ght),p)//右分支非空,在右方向以下继续查找else{/*找到右分支为空的结点*s*/(*p)->key=(*s)->key;/*复制*s的关键字、数据到*p结点*/(*p)->data=(*s)->data;r=*s;/*r记载该*s

结点，为free做准备*/*s=(*s)->left；/*删除*s所指结点。由于s参数是指向指针的变量*//*本语句把*s左分支接到*s的父结点上，*//*从而在树上摘下了*s所指向的结点。*/}returnr;//把将释放的变量指针带回主程序}12345976810

1112131415p:s:9r:root:图G=(V，E)。其中,⚫V=(v1,v2,…,vn)为图G的结点集合⚫vi为图G中结点⚫E={(vi,vj)|vi,vj∈V}是图中边的集合⚫(vi,vj)表示连接结点vi到结点vj的边。

04316752图——graph(一)邻接表方法设图G有k个结点，使用一个k*k的int型矩阵g表示图G,矩阵g的第i行顺序列出与结点i直接相连的结点编号,最后以“-1”结尾。则图G表示成右图的邻接表。04316752012-11034-12045-1314-

1412367-15267-1645-1745-1(二)邻接矩阵方法设图G有k个结点，使用一个k*k的bool类型矩阵g表示图G矩阵元素利用这种表示法，左图的网表示成右图8*8的bool矩阵。gij[,]=trueijfalseij表示从结点到结点有直接路；表示从结点到

结点没有直接路；012345670tt1ttt2ttt3tt4ttttt5ttt6tt7tt04316752(三)邻接链表方法设图G中有k个结点，使用一个有k个元素的一维指针数组G,数组G的第i个元素对应网中第i个结点。

以它为链首,把与结点i直接相连的结点链成一个链。图G表示成右图的邻接链表:0431675245.12.14034.045.267.12367.45.76543210已知一个网g=(v,e)。其中,⚫v=(v1,

v2,…,vn)为网g的结点集合,⚫vi为网中结点。⚫e={(vi,vj)}是网中边的集合,⚫(vi,vj)表示连接结点vi到结点vj的边。找路径是指求从结点m到结点n的所有路径。04316752例12-5找

路径解:这样想该问题,1.从m点出发沿所有可能的路向前走一步;2.然后再站在新的点上，再向前走一步;...如此重复，直到走到结点n为止。在走的过程中，保证不走重复点，可以得到下图的算法:m==n输出p[0～r]m点的所有后

继结点ii∈p[0～r]p[r]=mroute(i,n,r+1)routem:开始点；n:终结点；r:路迹数组p尾标结束在该算法中，关键在于找出m点的所有后继点。(一)邻接链表方法04316752451214034045267123674576543210设有如下声明：#defineh1

0structnode{intno;structnode*link;};intp[h];/*路迹数组*/structnode*g[h];/*网的邻接链表*/voidprintp(int,int)；//函数原型：输出booliinp(int,i

nt,int);//函数原型：判断//点i是否已经走过（在P中）voidroute(intm,intn,intr){//开始结点、终结结点、路迹数组p的尾structnode*hh;inti;p[r]=m;if(m==n)printp(0,r

);else{hh=g[m];while(hh!=NULL){i=hh->no;if(!iinp(i,0,r))route(i,n,r+1);hh=hh->link;}}}booliinp(intii,intu,intv){intj;fo

r(j=u;j<=v;j++)if(ii==p[j])returntrue;returnfalse;}voidprintp(inte,intf){intj;for(j=e;j<=f;j++)printf("%

4d",p[j]);printf("\n");}程序设计实例◼一个排序算法◼法雷序列◼多项式加法例12-2排序算法◼数组排序已经很熟悉，而且有各种各样的算法。下边用逐步增加递增子序列的方法实现链表排序。设有说明:typedef...datatype;structitem{datatypeda

ta;intkey;structitem*next;};typedefstructitem*pt以base为链首的链表如下图所示。该算法的思想是:①开始假设空序列是递增的②若i个元素子序列已经递增，则加一个元素，

把插入到序列中一个适当位置使i+1个元素的子序列也递增③直到i=n为止datakeydatakeydatakeydatakey·...base:开始p=basep!=NULL使base～p递增p0=p;p=p->n

ext结束returnbase使base～p递增寻找p应该插入的位置r0,rp插入到r0、r之间结束p插入到r0、r之间结束defr≠p把p独立出来=>q;p指向p0插入到r0,r之间:q->next=r;r0->next=q插入到链头:q->next

=base;base=qr==base寻找位置r=baser->key<p->key∧r!=pr0=r;r=r->next结束def考查程序运行中各个参数、变量、链表的变化状态。如图所示：设从base到p0之间的子链表已经递增，现在加入p所指示的节；

在base~p0之间查找合适位置，设应该把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:ptsort(ptbase){/*链表排序，base为链首*/ptp,p0,r,r0,q;p0=N

ULL;p=base;while(p!=NULL){/*逐项处理，把p加入到子序列中，并保持“base--p”递增*/r=base;/*寻找位置*/while((r->key<p->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;}returnbase;}/*sort*/对任意给定的自然数n，把所有如下形式的不可约分数按递增顺序排列起来，称该序列为n级法雷序列Fn。例如F8为:编函数，对任意给定的正整数n，求

n级法雷序列，并带回n级法雷序列链指针。(0in;0ji)ji===01111121323143525345671,,,,,,,,,,,,,,,,,,,,,,18765473857275837456781例12-3法雷序列分析：法雷序列的每项是个分数，不能用实数精确的表示，而且这些数的排列

顺序是不规则的。用下图形式的链表来表示它。分子分母分子分母分子分母分子分母·...显然法雷序列的各项均在区间[0/1,1/1]之内。生成法雷序列算法⚫先把一阶法雷序列：0/1,1/1放入链表中；⚫然后顺序分别以i

=2,3,...,n作分母，对任意i以j=1,2,...,i-1作分子，作成分数j/i；⚫若j/i是不可约分数，则该j/i必然是法雷序列的一项；把该j/i插入到链表的合适位置上，并使链表仍保持按递增排序。0/1,1/1放入序列读入n生成n阶法雷序列链表结束for(i=2;i<=n;i

++)for(j=1;j<i;j++)把j/i放入序列j/i不可约分把j/i插入到r0,r之间查j/i应插入的位置r0,rstructfarlei_item{intnumerator,denominator;structfarlei_item*next;};ty

pedefstructfarlei_item*farleipointer;intgcd(intx,inty){/*求最大公约数*/if(y==0)returnx;elsereturngcd(y,x%y

);}/*构造法雷序列,并返回序列头指针*/farleipointerfarlei(intn){inti,j;farleipointerfn,r,r0,p;if(n<1)//如果n<=0,则没有法雷序列return

NULL;/*0/1,1/1送入序列，fn指向链首*/fn=(farleipointer)malloc(sizeof(structfarlei_item));//构造0/1fn->numerator=0;fn->denomin

ator=1;fn->next=(farleipointer)malloc(sizeof(structfarlei_item));//构造1/1fn->next->numerator=1;fn->next->den

ominator=1;fn->next->next=NULL;/*生成序列*/for(i=2;i<=n;i++)for(j=1;j<i;j++)if(gcd(i,j)==1){/*查j/i位置r0,r*/r=fn;while(j*r->denominator>i*r->numerator)

{r0=r;r=r->next;}/*j/i插入到r0,r之间*/p=(farleipointer)malloc(sizeof(structfarlei_item));p->numerator=j;p->denominator=i;r

0->next=p;p->next=r;}returnfn;}例12-4多项式加法多项式可以用如下形式的链表来存储；幂次系数...幂次系数幂次系数幂次系数．52()6.53.40.5pxXXX=+++52()6.53.40.5pxXX

X=+++56.523.41100.5·例如多项式可以表示成如下形式:编一个函数，实现多项式加法：p(X)+q(X)=>s(X)。设有类型说明：structitem{floatcoef;intexp;st

ructitem*next;};typedefstructitem*polynome;解:在本程序的算法中，在链表上利用了一个哨兵项。所谓哨兵是在链表的链首多加一节，该节不存储有效的链表项的值，而保存一个边界值或空值，本程序的哨兵项是空值。由于利用了哨兵变量，所以处理统一了。多项式加法的

算法如下图：开始p=>s;p=p->nextp+q=>s;q=q->next;p=p->nextq=>s;q=q->next结束(p!=NULL)&&(q!=NULL)p->exp>q->expp!=NULLq!=NULLp=>s;p=p->nextq=>s;q=q->

nextp->exp<q->exp程序如下：voidadds(intexp0,floatcoef0，polynomer){/*向s加入一项*/polynomer0;r0=(polynome)malloc(sizeof(

structitem));r0->exp=exp0;r0->coef=coef0;r0->next=NULL;r->next=r0;}polinomeaddpolynome(polinomep,polinomeq){polinomes，r//s为结果多项式链首；r始终

指向结果多项式s的最低次幂项。/*申请一个哨兵变量，以便算法统一*/s=(polynome)malloc(sizeof(structitem));r=s;while((p!=NULL)&&(q!=NULL))/*相加*/if(p->exp>q->exp){

adds(p->exp,p->coef，r);p=p->next;}elseif(p->exp<q->exp){adds(q->exp,q->coef，r);q=q->next;}else{adds(p->ex

p,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);returns;}◼本章讲述十分重要的动态数据

结构–动态数据结构概念–各种简单的动态数据结构▪栈▪队列▪链表▪树▪图重点掌握动态数据结构的操作本章小结作业①12.1②12.2③12.3④12.9⑤12.45