【教学课件】第十二章动态数据结构.ppt

《【教学课件】第十二章动态数据结构.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第十二章动态数据结构.ppt（92页珍藏版）》请在三一办公上搜索。

1、第十二章 动态数据结构,管理动态变量动态数据结构栈 stack队列 queue 链表linkage table树tree图 graph程序设计实例本章小结作业,考虑上一章的职工卡片问题，用计算机管理这些卡片,要把卡片保存在计算机内。首先，用什么数据结构存储：一张卡片是一个结构体，所有卡片自然用结构体数组。第三，操作问题：若增加一个人，应该在数组中加一个元素，会产生数组不够大的可能。若增加一张卡片在数组中间，应该把加入位置以后的其它元素依次向后移动。若在中间删除一张卡片，会在数组中间留下一个“洞”，应该把“洞”以后的元素依次向前移动,使用数组带来的问题是：操作不方便；数组尺寸不好确定。第二，数组

2、多大：为保存全部卡片，并且人数不固定，就应该给一个足够大的数组。最好把这些卡片存储成动态的，需要多大存储量（有多少张卡片）就用多大。中间加一张卡片时不要向后串别的卡片，删除一张卡片时不要留下“洞”。,如图的链式结构可以满足要求:当增加一张卡片时，只需要向计算机系统申请一块空间，联到链的适当位置上。例如，要增加一张卡片 50 插入到 2、3 之间，则只需要如下修改指针：若删除一节，只需要将其从链上摘下来即可。例删除2节得链上已经没有2节了，删掉的节所占的存储空间还可以还回计算机系统，以便作其它用途。,这就是一种动态数据结构中的链表。动态数据结构上的一项是一个动态变量，指针是标识动态变量的有力手段

3、。动态变量与静态变量的区别在于:静态变量是程序中由程序员“显式”说明的变量。它有一个名字，在编译时，编译程序已经给它分配存储空间。这块存储空间用变量的名字来标识。,动态变量在程序中没有“显式”说明，它没有名字在编译时编译程序不知道有该变量，不给（也不可能给）它分配空间。动态变量是在程序运行时随程序存储数据的需要，申请空间函数（例如malloc，当然也是由程序员安排的）随机的动态的申请来的空间。它没有名字，一般动态变量都由指针标识。当使用完毕后，由释放空间函数（例如free）释放，还回计算机存储管理系统，以备它用。,注意：这里所说的静态变量不是C语言中由静态存储类别static声明的变量；动态变

4、量也不是C语言中由自动存储类别auto声明的变量。而是一般程序设计概念中的静态变量、动态变量,管理动态变量,动态变量在程序运行时，随程序存储数据的需要，向计算机系统申请；使用完后还回计算机系统。本节介绍申请计算机存储空间函数malloc释放存储空间函数free,内存 程序运行时，涉及用户程序的内存存储结构如右图所示，首先是目标代码区；然后是静态存储区，用于存放那些可用绝对地址标识的，主要是具有静态存储类别的数据和变量；接着是目标代码运行时用到的库程序代码区；最后剩余空间是栈区和堆区，栈区和堆区从剩余空间的两端，动态的向中间增长。栈区用来存储程序中声明的函数的局部变量等具有自动存储类别的数据和变

5、量；堆区用来存储经过动态申请空间函数申请的变量。,sizeof 运算符单目运算符 sizeof 的操作数是类型。运算结果是求得相应类型的尺寸，即存储相应类型数据所需要的字节数。sizeof(int)/*结果是2*/sizeof(char)/*结果是1*/sizeof(struct date)/*若 struct date 是第十一章定义的日期类型，结果是6*/,malloc 函数:原型 void*malloc(unsigned long size);功能 申请足够大内存区域用来存储长度为size的数据对象，返回该区域的首指针，并保证该区域符合任何数据类型对存储区域开始地址和对齐的要求。返回指针

6、是void类型的，调用者必须使用显示强制类型转换，把该指针转换成所需要类型的指针。,例:float*p;p=(float*)malloc(sizeof(float);struct date*pdate;pdate=(struct date*)malloc(sizeof(struct date);,free函数动态申请的内存如果不再使用，应当适时释放这样可以提高程序运行效率。free函数用来释放经过malloc申请的动态空间。free的函数原型 void free(void*ptr);功能释放由malloc申请的内存区域。free的参数ptr是一个指针，指向以前由malloc申请的一个内存区域。

7、,例申请float*p;p=(float*)malloc(sizeof(float);struct date*pdate;pdate=(struct date*)malloc(sizeof(struct date);释放free(p);free(pdate);,free(ptr)/*释放ptr所指向由malloc申请的内存空间*/一块存储区域一经释放，便不能再使用。使用free特别注意，操作不当会产生不可预料的结果。如下情况下使用free都会造成灾难性后果。ptr无值；ptr的值为NULL；ptr所指向的空间不是经过malloc申请来的；对一次申请的存储区进行多次释放（实际可能是ptr无值或值

8、为NULL）。,实用问题:若指针变量指向的用malloc申请来的动态变量，是孤立的不能与其它变量相联系，显然作用不大。引进动态变量的目的是构造动态数据结构。例如象本章开始介绍的那样，构造一个链表等。这就要求一个数据项上除基本的数据信息外，还应包含与其它数据项相联系的信息，也就是包含指针。该结构必须用结构体类型描述，链表上一节的类型定义形式。,栈 stack,在第六章已经用数组实现过栈和队列，但是，数组有一定的局限性。如图可以用单向链表实现栈，指针变量top指向栈顶。栈的操作有:初始化：stackintial 压栈：stackpush 弹栈：stackpop,设有声明:typedef.items

9、;typedef struct stackcell items data;struct stackcell*predocessor;stackcelltype;typedef stackcelltype*pstacktype;pstacktype top;,如下实现栈的操作：void stackinitial(void)top=NULL;void stackpush(items x)pstacktype p;p=(pstacktype)malloc(sizeof(stackcelltype);p-data=x;p-prodocessor=top;top=p;void stackpop(item

10、s*x)pstacktype p;if(top!=NULL)*x=top-data;p=top;top=top-predecessor;free(p);else printf(“栈下溢n”);,看一下这三个操作:初始化后(调用stackinitail)得。调用一次 stackpush(1)得。再调用一次stackpush(2)得。调用一次stackpop(&b)得。,2,队列,如图可用单向链表实现队列，现在要用两个指针变量，一个指向队头（front），一个指向队尾（rear）。队列的操作有 初始化（queueinitial）进队排在队尾（inqueue）出队从队头删一项（outqueue）,设

11、有如下说明:typedef.items;typedef struct queue items data struct queue*next;queuetype;typedef queuetype*pqueuetype;pqueuetype front,rear;操作：void queueinital(void)front=NULL;rear=NULL;,void inqueue(item x)pqueuetype p;p=(pqueuetype)malloc(sizeof(queuetype);p-data=x;p-next=NULL;if(rear=NULL)rear=p;front=p;e

12、lse rear-next=p;rear=p;,void outgueue(item*x)pqueuetype p;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(&a)得。,1,2,3,NULL

13、,NULL,链表linkage table,实际上前边讲的栈，队列都是单向链表，但是栈和队列只是单向链表的两种特殊应用操作只在头尾进行。下边介绍单向链表的一般操作:创建单向链表:创建单向链表，是指用一项一项的数据逐步建立、形成一个链表。可以分成向链头加入数据和向链尾加入数据两种方式。创建单向链表可以分成向链头加入数据和向链尾加入数据两种方式。新项加入链头就是压栈的算法；新项加入链尾就是队列中入队的算法。只要反复调用那里的函数或将函数体放在循环语句中即可，这里不赘述。,遍历单向链表:遍历是指从头到尾将链表上数据全部加工一遍。可用如下左端的算法。但实用中，经常用如下右端 的算法来遍历单向链表。,p

14、=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=base;while(p!=NULL,向单向链表插入一项:设有下图的链表，现在要把r所指示的数据项插入到 p0、p 所指两项之间。操作是:r-next=p;p0-next=r;p0=r/*使 p0 仍为 p 的前一项*/,p0:,

15、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;/*

16、6*/q=q0-next;/*7*/,树tree,两叉树，两叉树的每个数据项附带两个指针，分别指向它的两个分支。两叉树的定义:空是树；一个结点连接两个不相交的树,仍为树；所有结点具有相同的数据类型。,(a+b/c)*(d e*f),设 ti 为二叉树的一个结点，一般 ti 由两部分组成：基本数据部分-保存本结点上的基本数据；指针部分连-接本结点以下的其它结点。结点 ti 的指针连接的结点称为 ti 的子结点，相应 ti 称为其子结点的父结点。,ti的指针部分有两个指针：左指针、右指针。称 ti 的左指针连接的部分为 ti 的左子树，ti 的右指针连接的部分为 ti 的右子树。若左、右子树均空，

17、则称 ti 为叶结点。,ti,为了检索操作方便，一般把两叉树组织成两叉检索树。两叉检索树的定义是：设树中每个结点的数据部分有一个数据项 key 是有序的,称该数据项为关键字。一个两叉树称为检索树，如果对每个结点 ti，它的左子树中所有结点的 key 值都小于 ti 的 key 值；ti 的右子树中所有结点的 key 值都大于 ti 的 key 值。,二叉检索树的操作有:遍历检索插入一个结点删除一个结点 由于树是递归定义的，所以树的操作用递归算法十分简洁。,设有说明部分:typedef.keytype；typedef.datatype；typedef struct tree keytype ke

18、y；datatype data；struct tree*left；struct tree*right；treetype;typedef treetype*treepointer；treepointer root；,遍历遍历二叉树是指按一定规律走遍树的每个结点，使每一结点被访问一次，而且只被访问一次。在访问一个结点时，可以做任何信息加工工作。下例打印结点的data域，并设该域为char型的。遍历算法可分为前序，中序，后序遍历三种。前序遍历：对任意一个结点 ti 来讲，先访问及处理该结点的数据域；然后遍历左子树；最后遍历右子树。中序遍历：对任意一个结点 ti 来讲，先遍历左子树；然后访问及处理该结

19、点的数据域；最后遍历右子树。后序遍历：对任意一个结点 ti 来讲，先遍历左子树；然后遍历右子树；最后访问及处理该结点的数据域。,【例12-1】设有下图所示树,这是由表达式(a+b/c)*(d-e*f)生成的树，这棵树反映了表达式的结构，同时也反映了表达式的运算次序。前序遍历过程是：得到表达式的波兰表示式（运算符在两个运算分量前）。前序遍历算法是：void preorder(treepointer p)if(p!=NULL)printf(“%c”,p-data);preorder(p-left);preorder(p-right),a,/,b,c,-,d,*,e,f,中序遍历过程是：得到表达式的

20、原形式，只是没有括号。中序遍历算法是：void inorder(treepointer p)/*中序遍历*/if(p!=NULL)inorder(p-left);printf(“%c”,p-data);inorder(p-right),a,/,b,c,-,d,*,e,f,后序遍历过程是：得到表达式的表达式的逆波兰表示式（运算符在两个运算分量之后）。后序遍历算法是：void postorder(treepointer p)/*后序遍历*/if(p!=NULL)postorder(p-left);postorder(p-right)printf(“%c”,p-data);,a,/,b,c,-,d,

21、*,e,f,检索检索是按给定关键字值 c 在树上找一个结点 ti，且 ti 的关键字值 key 恰好等于 c。若检索到，函数将带回相应结点指针；否则若没检索到，函数将带回 NULL。下述检索算法的前提条件是，p 是检索树。treepointer search(typekey c,treepointer p)if(p-key=c)|(p=NULL)return p;else if(c key)return search(c,p-left);else return search(c,p-right);,插入一个结点插入是指将一个数据项插入到树中某一恰当位置，使树仍保持检索树的性质。显然，首先要按k

22、ey值查出应该插入的位置，然后再插入。void insert(keytype c,datatype d,treepointer*p)if(*p=NULL)*p=(treepointer)malloc(sizeof(struct tree);(*p)-key=c;(*p)-data=d;(*p)-left=NULL;(*p)-right=NULL;else if(c key)insert(c,d,由于 insert 的参数 p 是指向指针的指针类型，在 insert 内 p 指向指针类型的实在参数。所以在执行*p=(treepointer)malloc(sizeof(struct tree)时，

23、将使实在参数指针变量指向新申请来的结点。,1)若调用 insert 时，如图 root 为空树。以&root 作实在参数调用 insert,即 insert(c,d,&root)insert 的形式参数 p 指向 root，而 root 值为 NULL。转插入功能，执行*p=(treepointer)malloc(sizeof(struct tree)得:再执行后边的几个赋值语句,得:,c;d,2)若调用insert时，root非空，在中间某一个结点查到空指 针，如图；设查到该结点后，应该继续向右查，以&(*p)-right)作实在参数递归调用insert，即执行 insert(c,d,&(*

24、p)-right)insert 的形式参数 p 指向本步的(*p)-right，而(*p)-right 值为 NULL。转插入功能，执行*p=(treepointer)malloc(sizeof(struct tree)再执行后边的几个赋值语句,得:,c;d,删除一结点设欲删除结点为 r，则可能有如下几种情况。针对不同情况删除算法不同.r 是叶结点:简单删掉 r 结点，并把 r 的父结点连接处改成NULL 即可。,r:,r 只有一个左子树,r 只有一个子树:把 r 以下部分接入 r 的父结点连接 r 处。然后删掉r结点。,r 只有一个右子树,r 两个方向都有子树:在 r 的左子树上找到关键字

25、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 两个方向

26、都有子树:在 r 的左子树上找到关键字 key 值最大的结点 s，把 s 结点的数据 data及关键字 key 复制到 r 结点 上，然后删除掉 s 结点。,10,r:,9,综合上述三种情况，下述函数deletenode 完成删除一个结点。deletenode的调用形式是：deletenode(valueofkey,&root)其中value_of_key是欲删除结点的关键字值；root是指针类型（treepointer）变量，指向树根。这里用指向指针的指针作参数。,treepointer del(treepointer*,treepointer*)；/*处理第三种情况的函数的函数原型*/vo

27、id deletenode(keytype c,treepointer*p)/*删除关键字值等于 c 的结点*/treepointer r;if(*p=NULL)printf(“not found:%dn”,c);else if(c key)/*c left);else if(c(*p)-key)/*c 当前结点的 key 值，被删结点在右子树上*/deletenode(c,else r=*p;if(r-right=NULL)*p=r-left/*右子树空，接左分支*/else if(r-left=NULL)*p=r-right;/*左子树空，接右分支*/else r=del(,root:,p

28、:,deletenode(4,&root),r 只有一个左子树,treepointer del(treepointer*s,treepointer*p)/*处理第三种情况，仅第三种情况调用*/treepointer r;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

29、型矩阵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

30、)表示连接结点vi到结点vj的边。找路径是指求从结点m到结点n的所有路径。,例12-5找路径,解:这样想该问题,从m点出发沿所有可能的路向前走一步;然后再站在新的点上，再向前走一步;.如此重复，直到走到结点n为止。在走的过程中，保证不走重复点，可以得到下图的算法:,在该算法中，关键在于找出m点的所有后继点。(一)邻接链表方法,设有如下声明：#define h 10struct node int no;struct node*link;int ph;/*路迹数组*/struct node*gh;/*网的邻接链表*/void printp(int,int)；/函数原型：输出bool iinp(in

31、t,int,int);/函数原型：判断/点i是否已经走过（在P中）,void route(int m,int n,int r)/开始结点、终结结点、路迹数组p的尾 struct node*hh;int i;pr=m;if(m=n)printp(0,r);else hh=gm;while(hh!=NULL)i=hh-no;if(!iinp(i,0,r)route(i,n,r+1);hh=hh-link;,bool iinp(int ii,int u,int v)int j;for(j=u;j=v;j+)if(ii=pj)return true;return false;void printp(i

32、nt e,int f)int j;for(j=e;j=f;j+)printf(%4d,pj);printf(n);,程序设计实例,一个排序算法法雷序列多项式加法,例12-2 排序算法,数组排序已经很熟悉，而且有各种各样的算法。下边用逐步增加递增子序列的方法实现链表排序。设有说明:typedef.datatype;struct item datatype data;int key;struct item*next;typedef struct item*pt,以base为链首的链表如下图所示。该算法的思想是:开始假设空序列是递增的若i个元素子序列已经递增，则加一个元素，把插入到序列中一个适当位置

33、使i+1个元素的子序列也递增直到i=n为止,考查程序运行中各个参数、变量、链表的变化状态。如图所示：设从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；现在链表结构是：,.,pt sort(pt base)/*链表排序，base 为链首*/pt p,p0,r,r0,q;p0=NULL;p=base;while(p!=NULL)/*逐项处理，把p加入到子序列中，

34、并保持“base-p”递增*/r=base;/*寻找位置*/while(r-key key)/*sort*/,对任意给定的自然数 n，把所有如下形式的不可约分数 按递增顺序排列起来，称该序列为 n 级法雷序列 Fn。例如F8 为:编函数，对任意给定的正整数n，求n级法雷序列，并带回n级法雷序列链指针。,例12-3 法雷序列,分析：法雷序列的每项是个分数，不能用实数精确的表示，而且这些数的排列顺序是不规则的。用下图形式的链表来表示它。,显然法雷序列的各项均在区间0/1,1/1之内。生成法雷序列算法先把一阶法雷序列：0/1,1/1放入链表中；然后顺序分别以i=2,3,.,n 作分母，对任意i以j=

35、1,2,.,i-1作 分子，作成分数j/i；若j/i是不可约分数，则该j/i必然是法雷序列的一项；把该j/i插入到链表的合适位置上，并使链表仍保持按递增排序。,0/1,1/1 放入序列,读入 n,把 j/i 放入序列,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);,/*构造法雷序列,并返

36、回序列头指针*/farleipointer farlei(int n)int i,j;farleipointer fn,r,r0,p;if(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;idenominator i*r-numerator)r0=r;r=r-next;/*j/i 插入到 r0,r 之间*

37、/p=(farleipointer)malloc(sizeof(struct farlei_item);p-numerator=j;p-denominator=i;r0-next=p;p-next=r;return fn;,例12-4多项式加法,多项式可以用如下形式的链表来存储；,例如多项式,可以表示成如下形式:,编一个函数，实现多项式加法：p(X)+q(X)=s(X)。,设有类型说明：struct item float coef;int exp;struct item*next;typedef struct item*polynome;解:在本程序的算法中，在链表上利用了一个哨兵项。所谓哨兵

38、是在链表的链首多加一节，该节不存储有效的链表项的值，而保存一个边界值或空值，本程序的哨兵项是空值。由于利用了哨兵变量，所以处理统一了。多项式加法的算法如下图：,程序如下：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为结果多

39、项式链首；r 始终指向结果多项式s的最低次幂项。/*申请一个哨兵变量，以便算法统一*/s=(polynome)malloc(sizeof(struct item);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);return s;,本章讲述十分重要的动态数据结构动态数据结构概念各种简单的动态数据结构栈队列链表树图重点掌握动态数据结构的操作,本章小结,作业,12.112.212.312.912.45,