资源描述
第十二章动态数据结构,管理动态变量动态数据结构栈stack队列queue链表linkagetable树tree图graph程序设计实例本章小结作业,考虑上一章的职工卡片问题，用计算机管理这些卡片,要把卡片保存在计算机内。首先，用什么数据结构存储：一张卡片是一个结构体，所有卡片自然用结构体数组。第三，操作问题：若增加一个人，应该在数组中加一个元素，会产生数组不够大的可能。若增加一张卡片在数组中间，应该把加入位置以后的其它元素依次向后移动。若在中间删除一张卡片，会在数组中间留下一个“洞”，应该把“洞”以后的元素依次向前移动,使用数组带来的问题是：操作不方便；数组尺寸不好确定。第二，数组多大：为保存全部卡片，并且人数不固定，就应该给一个足够大的数组。最好把这些卡片存储成动态的，需要多大存储量（有多少张卡片）就用多大。中间加一张卡片时不要向后串别的卡片，删除一张卡片时不要留下“洞”。,如图的链式结构可以满足要求:当增加一张卡片时，只需要向计算机系统申请一块空间，联到链的适当位置上。例如，要增加一张卡片50插入到2、3之间，则只需要如下修改指针：若删除一节，只需要将其从链上摘下来即可。例删除2节得链上已经没有2节了，删掉的节所占的存储空间还可以还回计算机系统，以便作其它用途。,这就是一种动态数据结构中的链表。动态数据结构上的一项是一个动态变量，指针是标识动态变量的有力手段。动态变量与静态变量的区别在于:静态变量是程序中由程序员“显式”说明的变量。它有一个名字，在编译时，编译程序已经给它分配存储空间。这块存储空间用变量的名字来标识。,动态变量在程序中没有“显式”说明，它没有名字在编译时编译程序不知道有该变量，不给（也不可能给）它分配空间。动态变量是在程序运行时随程序存储数据的需要，申请空间函数（例如malloc，当然也是由程序员安排的）随机的动态的申请来的空间。它没有名字，一般动态变量都由指针标识。当使用完毕后，由释放空间函数（例如free）释放，还回计算机存储管理系统，以备它用。,注意：这里所说的静态变量不是C语言中由静态存储类别static声明的变量；动态变量也不是C语言中由自动存储类别auto声明的变量。而是一般程序设计概念中的静态变量、动态变量,管理动态变量,动态变量在程序运行时，随程序存储数据的需要，向计算机系统申请；使用完后还回计算机系统。本节介绍申请计算机存储空间函数malloc释放存储空间函数free,内存程序运行时，涉及用户程序的内存存储结构如右图所示，首先是目标代码区；然后是静态存储区，用于存放那些可用绝对地址标识的，主要是具有静态存储类别的数据和变量；接着是目标代码运行时用到的库程序代码区；最后剩余空间是栈区和堆区，栈区和堆区从剩余空间的两端，动态的向中间增长。栈区用来存储程序中声明的函数的局部变量等具有自动存储类别的数据和变量；堆区用来存储经过动态申请空间函数申请的变量。,sizeof运算符单目运算符sizeof的操作数是类型。运算结果是求得相应类型的尺寸，即存储相应类型数据所需要的字节数。sizeof(int)/*结果是2*/sizeof(char)/*结果是1*/sizeof(structdate)/*若structdate是第十一章定义的日期类型，结果是6*/,malloc函数:原型void*malloc(unsignedlongsize);功能申请足够大内存区域用来存储长度为size的数据对象，返回该区域的首指针，并保证该区域符合任何数据类型对存储区域开始地址和对齐的要求。返回指针是void类型的，调用者必须使用显示强制类型转换，把该指针转换成所需要类型的指针。,例:float*p;p=(float*)malloc(sizeof(float);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(ptr)/*释放ptr所指向由malloc申请的内存空间*/一块存储区域一经释放，便不能再使用。使用free特别注意，操作不当会产生不可预料的结果。如下情况下使用free都会造成灾难性后果。ptr无值；ptr的值为NULL；ptr所指向的空间不是经过malloc申请来的；对一次申请的存储区进行多次释放（实际可能是ptr无值或值为NULL）。,实用问题:若指针变量指向的用malloc申请来的动态变量，是孤立的不能与其它变量相联系，显然作用不大。引进动态变量的目的是构造动态数据结构。例如象本章开始介绍的那样，构造一个链表等。这就要求一个数据项上除基本的数据信息外，还应包含与其它数据项相联系的信息，也就是包含指针。该结构必须用结构体类型描述，链表上一节的类型定义形式。,栈stack,在第六章已经用数组实现过栈和队列，但是，数组有一定的局限性。如图可以用单向链表实现栈，指针变量top指向栈顶。栈的操作有:初始化：stackintial压栈：stackpush弹栈：stackpop,设有声明:typedef.items;typedefstructstackcellitemsdata;structstackcell*predocessor;stackcelltype;typedefstackcelltype*pstacktype;pstacktypetop;,如下实现栈的操作：voidstackinitial(void)top=NULL;voidstackpush(itemsx)pstacktypep;p=(pstacktype)malloc(sizeof(stackcelltype);p-data=x;p-prodocessor=top;top=p;voidstackpop(items*x)pstacktypep;if(top!=NULL)*x=top-data;p=top;top=top-predecessor;free(p);elseprintf(“栈下溢n”);,看一下这三个操作:初始化后(调用stackinitail)得。调用一次stackpush(1)得。再调用一次stackpush(2)得。调用一次stackpop(typedefstructqueueitemsdatastructqueue*next;queuetype;typedefqueuetype*pqueuetype;pqueuetypefront,rear;操作：voidqueueinital(void)front=NULL;rear=NULL;,voidinqueue(itemx)pqueuetypep;p=(pqueuetype)malloc(sizeof(queuetype);p-data=x;p-next=NULL;if(rear=NULL)rear=p;front=p;elserear-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(再调用一次outgueue(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=base;while(p!=NULL,向单向链表插入一项:设有下图的链表，现在要把r所指示的数据项插入到p0、p所指两项之间。操作是:r-next=p;p0-next=r;p0=r/*使p0仍为p的前一项*/,p0:,p:,1,2,3,4,.,.,从单向链表上删除一项:设有下图的链表，现在要删除p所指项。删除算法是：q=p;p=p-next;p0-next=p;free(q),p0:,1,2,4,.,.,p:,交换单向链表上两项:设有如图所示链表。现在要把p所指的项与q所指的项交换为了表示操作方便，我们把该链表分两段画出。,/*交换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+b/c)*(de*f),设ti为二叉树的一个结点，一般ti由两部分组成：基本数据部分-保存本结点上的基本数据；指针部分连-接本结点以下的其它结点。结点ti的指针连接的结点称为ti的子结点，相应ti称为其子结点的父结点。,ti的指针部分有两个指针：左指针、右指针。称ti的左指针连接的部分为ti的左子树，ti的右指针连接的部分为ti的右子树。若左、右子树均空，则称ti为叶结点。,ti,为了检索操作方便，一般把两叉树组织成两叉检索树。两叉检索树的定义是：设树中每个结点的数据部分有一个数据项key是有序的,称该数据项为关键字。一个两叉树称为检索树，如果对每个结点ti，它的左子树中所有结点的key值都小于ti的key值；ti的右子树中所有结点的key值都大于ti的key值。,二叉检索树的操作有:遍历检索插入一个结点删除一个结点由于树是递归定义的，所以树的操作用递归算法十分简洁。,设有说明部分:typedef.keytype；typedef.datatype；typedefstructtreekeytypekey；datatypedata；structtree*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,/,b,c,-,d,*,e,f,中序遍历过程是：得到表达式的原形式，只是没有括号。中序遍历算法是：voidinorder(treepointerp)/*中序遍历*/if(p!=NULL)inorder(p-left);printf(“%c”,p-data);inorder(p-right),a,/,b,c,-,d,*,e,f,后序遍历过程是：得到表达式的表达式的逆波兰表示式（运算符在两个运算分量之后）。后序遍历算法是：voidpostorder(treepointerp)/*后序遍历*/if(p!=NULL)postorder(p-left);postorder(p-right)printf(“%c”,p-data);,a,/,b,c,-,d,*,e,f,检索检索是按给定关键字值c在树上找一个结点ti，且ti的关键字值key恰好等于c。若检索到，函数将带回相应结点指针；否则若没检索到，函数将带回NULL。下述检索算法的前提条件是，p是检索树。treepointersearch(typekeyc,treepointerp)if(p-key=c)|(p=NULL)returnp;elseif(ckey)returnsearch(c,p-left);elsereturnsearch(c,p-right);,插入一个结点插入是指将一个数据项插入到树中某一恰当位置，使树仍保持检索树的性质。显然，首先要按key值查出应该插入的位置，然后再插入。voidinsert(keytypec,datatyped,treepointer*p)if(*p=NULL)*p=(treepointer)malloc(sizeof(structtree);(*p)-key=c;(*p)-data=d;(*p)-left=NULL;(*p)-right=NULL;elseif(ckey)insert(c,d,由于insert的参数p是指向指针的指针类型，在insert内p指向指针类型的实在参数。所以在执行*p=(treepointer)malloc(sizeof(structtree)时，将使实在参数指针变量指向新申请来的结点。,1)若调用insert时，如图root为空树。以d,2)若调用insert时，root非空，在中间某一个结点查到空指针，如图；设查到该结点后，应该继续向右查，以d,删除一结点设欲删除结点为r，则可能有如下几种情况。针对不同情况删除算法不同.r是叶结点:简单删掉r结点，并把r的父结点连接处改成NULL即可。,r:,r只有一个左子树,r只有一个子树:把r以下部分接入r的父结点连接r处。然后删掉r结点。,r只有一个右子树,r两个方向都有子树:在r的左子树上找到关键字key值最大的结点s，把s结点的数据data及关键字key复制到r结点上，然后删除掉s结点。,10,r:,9,当然也可以在r的右子树上找到关键字key值最小的结点s，把s结点的数据data及关键字key复制到r结点上，然后删除掉s结点。,s:,5,r:,6,使用在左子树上找最大结点的方法，按如下步骤进行:沿r左子树的右方向，向下找一个没有右子树的结点s，图中结点(9)。把该结点s的值复制到结点r（即欲删除的结点。把s的左子树连在s的父结点（图中为结点(5)）的右链上，在图中即连到(5)结点的右链上。删除s结点，即图中的(9)结点。,图3的情况r两个方向都有子树:在r的左子树上找到关键字key值最大的结点s，把s结点的数据data及关键字key复制到r结点上，然后删除掉s结点。,10,r:,9,综合上述三种情况，下述函数deletenode完成删除一个结点。deletenode的调用形式是：deletenode(valueofkey,if(*p=NULL)printf(“notfound:%dn”,c);elseif(ckey)/*cleft);elseif(c(*p)-key)/*c当前结点的key值，被删结点在右子树上*/deletenode(c,elser=*p;if(r-right=NULL)*p=r-left/*右子树空，接左分支*/elseif(r-left=NULL)*p=r-right;/*左子树空，接右分支*/elser=del(,root:,p:,deletenode(4,if(*s)-right!=NULL)/*右分支非空?*/r=del(/把将释放的变量指针带回主程序,p:,s:,9,root:,图G=(V，E)。其中,V=(v1,v2,vn)为图G的结点集合vi为图G中结点E=(vi,vj)|vi,vjV是图中边的集合(vi,vj)表示连接结点vi到结点vj的边。,图graph,(一)邻接表方法设图G有k个结点，使用一个k*k的int型矩阵g表示图G,矩阵g的第i行顺序列出与结点i直接相连的结点编号,最后以“-1”结尾。则图G表示成右图的邻接表。,(二)邻接矩阵方法设图G有k个结点，使用一个k*k的bool类型矩阵g表示图G矩阵元素利用这种表示法，左图的网表示成右图8*8的bool矩阵。,(三)邻接链表方法设图G中有k个结点，使用一个有k个元素的一维指针数组G,数组G的第i个元素对应网中第i个结点。以它为链首,把与结点i直接相连的结点链成一个链。图G表示成右图的邻接链表:,已知一个网g=(v,e)。其中,v=(v1,v2,vn)为网g的结点集合,vi为网中结点。e=(vi,vj)是网中边的集合,(vi,vj)表示连接结点vi到结点vj的边。找路径是指求从结点m到结点n的所有路径。,例12-5找路径,解:这样想该问题,从m点出发沿所有可能的路向前走一步;然后再站在新的点上，再向前走一步;.如此重复，直到走到结点n为止。在走的过程中，保证不走重复点，可以得到下图的算法:,在该算法中，关键在于找出m点的所有后继点。(一)邻接链表方法,设有如下声明：#defineh10structnodeintno;structnode*link;intph;/*路迹数组*/structnode*gh;/*网的邻接链表*/voidprintp(int,int)；/函数原型：输出booliinp(int,int,int);/函数原型：判断/点i是否已经走过（在P中）,voidroute(intm,intn,intr)/开始结点、终结结点、路迹数组p的尾structnode*hh;inti;pr=m;if(m=n)printp(0,r);elsehh=gm;while(hh!=NULL)i=hh-no;if(!iinp(i,0,r)route(i,n,r+1);hh=hh-link;,booliinp(intii,intu,intv)intj;for(j=u;jnext=p-next;p=p0;把p（现在由q指示）插入到r0,r之间：q-next=r;r0-next=q；现在链表结构是：,.,ptsort(ptbase)/*链表排序，base为链首*/ptp,p0,r,r0,q;p0=NULL;p=base;while(p!=NULL)/*逐项处理，把p加入到子序列中，并保持“base-p”递增*/r=base;/*寻找位置*/while(r-keykey)/*sort*/,对任意给定的自然数n，把所有如下形式的不可约分数按递增顺序排列起来，称该序列为n级法雷序列Fn。例如F8为:编函数，对任意给定的正整数n，求n级法雷序列，并带回n级法雷序列链指针。,例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,把j/i放入序列,structfarlei_itemintnumerator,denominator;structfarlei_item*next;typedefstructfarlei_item*farleipointer;intgcd(intx,inty)/*求最大公约数*/if(y=0)returnx;elsereturngcd(y,x%y);,/*构造法雷序列,并返回序列头指针*/farleipointerfarlei(intn)inti,j;farleipointerfn,r,r0,p;if(nnumerator=0;fn-denominator=1;fn-next=(farleipointer)malloc(sizeof(structfarlei_item);/构造1/1fn-next-numerator=1;fn-next-denominator=1;fn-next-next=NULL;,/*生成序列*/for(i=2;idenominatori*r-numerator)r0=r;r=r-next;/*j/i插入到r0,r之间*/p=(farleipointer)malloc(sizeof(structfarlei_item);p-numerator=j;p-denominator=i;r0-next=p;p-next=r;returnfn;,例12-4多项式加法,多项式可以用如下形式的链表来存储；,例如多项式,可以表示成如下形式:,编一个函数，实现多项式加法：p(X)+q(X)=s(X)。,设有类型说明：structitemfloatcoef;intexp;structitem*next;typedefstructitem*polynome;解:在本程序的算法中，在链表上利用了一个哨兵项。所谓哨兵是在链表的链首多加一节，该节不存储有效的链表项的值，而保存一个边界值或空值，本程序的哨兵项是空值。由于利用了哨兵变量，所以处理统一了。多项式加法的算法如下图：,程序如下：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),/*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.112.212.312.912.45,
展开阅读全文