C程序设计课件第12章.ppt

1、50 目标代码空间目标代码空间静态区空间静态区空间库代码空间库代码空间堆区空间堆区空间栈区空间栈区空间类型定义形式类型定义形式 struct t 基本数据部分；基本数据部分；struct t *next;基本数基本数据部分据部分指针部分指针部分一个数据项一个数据项 top:.栈栈top:1.2b:2rear:front:.1a:rear:front:231 p:b:23NULLNULLbase:1.2N-1N.双向链双向链base:12N-1N.单向链单向链base:12N-1N.环形链环形链base:12N-1N.双向双向环形链环形链p =base;p0=NULL;while(p!=NULL

2、)p =base;加工加工 p-while(p!=NULL)p =p-next;加工加工 p-p0 =p;p =p-next;r:5p0:p:1 2 3 4.p0:1234.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*/*+-a/

3、d*bcef(a+b/c)*(d e*f)root:设设 ti 为二叉树的一个结点，一般为二叉树的一个结点，一般 ti 由两部分组成：由两部分组成：l基本数据部分基本数据部分-保存本结点上的基本数据；保存本结点上的基本数据；l指针部分连指针部分连-接本结点以下的其它结点。接本结点以下的其它结点。结点结点 ti 的指针连接的结点称为的指针连接的结点称为 ti 的的子结点子结点，相应相应 ti 称为其子结点的称为其子结点的父结点父结点。ti的指针部分有两个指针：左指针、右指针。的指针部分有两个指针：左指针、右指针。称称 ti 的左指针连接的部分为的左指针连接的部分为 ti 的的左子树左子树，ti

4、的右指针连接的部分为的右指针连接的部分为 ti 的的右子树右子树。若左、右子树均空，则称若左、右子树均空，则称 ti 为为叶结点叶结点。ti78563124ti:*+-a/d*bcef a/b c-d*e f*+-a/d*bcefa/bc-d*ef*+-a/d*bcefa/b c-d*e f由于由于 insert 的参数的参数 p 是指向指针的指针类型，在是指向指针的指针类型，在 insert 内内 p 指向指向指针类型的实在参数指针类型的实在参数。所以在执行。所以在执行*p=(treepointer)malloc(sizeof(struct tree)时，将使实在参数指针变量指向新申请来的结

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

6、空，在中间某一个结点查到空指 针，如图；设查到该结点后，应该继续向右查，以针，如图；设查到该结点后，应该继续向右查，以&(*p)-right)作实在参数递归调用作实在参数递归调用insert，即执行，即执行 insert(c,d,&(*p)-right)insert 的形式参数的形式参数 p 指向本步的指向本步的(*p)-right，而，而(*p)-right 值为值为 NULL。转插入功能，执行转插入功能，执行 *p=(treepointer)malloc(sizeof(struct tree)再执行后边的几个赋值语句再执行后边的几个赋值语句,得得:c;d .p:n删除一结点删除一结点设欲删

7、除结点为设欲删除结点为 r，则可能有如下几种情况。针对不同，则可能有如下几种情况。针对不同情况删除算法不同情况删除算法不同.r 是叶结点是叶结点:简单删掉简单删掉 r 结点，并把结点，并把 r 的父结点连接处改的父结点连接处改成成NULL 即可即可。42513r:r 只有一个左子树只有一个左子树78563124r:78564231r:r 只有一个子树只有一个子树:把把 r 以下部分接入以下部分接入 r 的父结点连接的父结点连接 r 处。处。然后删掉然后删掉r结点结点。r 只有一个右子树只有一个右子树r 两个方向都有子树两个方向都有子树:在在 r 的左子树上找到关键字的左子树上找到关键字 key

8、 值值最大的结点最大的结点 s，把，把 s 结点的数据结点的数据 data及关键字及关键字 key 复制复制到到 r 结点上，然后删除掉结点上，然后删除掉 s 结点。结点。9s:10r:4514151213312118679当然也可以在当然也可以在r的右子树上找到关键字的右子树上找到关键字key值最小的结点值最小的结点s，把，把s结点的数据结点的数据data及关键字及关键字key复制到复制到r结点上，然结点上，然后删除掉后删除掉s结点。结点。8s:5r:410131411123129766使用在左子树上找最大结点的方法，按如使用在左子树上找最大结点的方法，按如下步骤进行下步骤进行:沿沿 r 左

9、子树的右方向，向下找一个没有左子树的右方向，向下找一个没有右子树的结点右子树的结点s，图中结点，图中结点(9)。把该结点把该结点 s 的值复制到结点的值复制到结点r（即欲删除（即欲删除的结点。的结点。把把 s 的左子树连在的左子树连在 s 的父结点（图中为的父结点（图中为结点结点(5)）的右链上，在图中即连到）的右链上，在图中即连到(5)结点的右链上。结点的右链上。删除删除s结点，即图中的结点，即图中的(9)结点。结点。图图3的情况的情况 r 两个方向都有子树两个方向都有子树:在在 r 的左子树上找到关键字的左子树上找到关键字 key 值值最大的结点最大的结点 s，把，把 s 结点的数据结点的

10、数据 data及关键字及关键字 key 复制到复制到 r 结点结点 上，然后删除掉上，然后删除掉 s 结点。结点。9s:10r:4514151213312118679综合上述三种情况，下述函数综合上述三种情况，下述函数deletenode 完成删除完成删除一个结点。一个结点。deletenode的调用形式是：的调用形式是：deletenode(valueofkey,&root)其中其中lvalue_of_key是欲删除结点的关键字值；是欲删除结点的关键字值；lroot是指针类型（是指针类型（treepointer）变量，指向树）变量，指向树根。这里根。这里用指向指针的指针作参数。用指向指针的指

11、针作参数。45627138root:p:deletenode(4,&root)r:r 只有一个左子树只有一个左子树123459768101112131415p:s:9r:root:0431675204316752g i j,=truetrue i j falsefalse i j 表示从结点表示从结点到结点到结点有直接路；有直接路；表示从结点表示从结点到结点到结点没有直接路；没有直接路；0431675204316752 4 5 .1 2 .1 4 0 3 4 .0 4 5 .2 6 7 .1 2 3 6 7 .4 5 .04316752m=n输出输出p0rm点的所有点的所有后继结点后继结点 i

12、ip0rpr=mroute(i,n,r+1)route m:开始点；开始点；n:终结点；终结点；r:路迹数组路迹数组p尾标尾标结束结束04316752 4 5 1 2 1 4 0 3 4 0 4 5 2 6 7 1 2 3 6 7 4 5设有如下声明：设有如下声明：#define h 10struct node int no;struct node *link;int ph;/*路迹数组路迹数组*/struct node*gh;/*网的邻接链表网的邻接链表*/void printp(int,int)；/函数原型：输出函数原型：输出bool iinp(int,int,int);/函数原型：判断函

13、数原型：判断 /点点i是否已经走过（在是否已经走过（在P中）中）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(int e,int f)int j;for(j=e;jnext结束结束return base使使basep递增递增寻找寻找p应该插入的位置应该插入的位置r0,rp插入到插入到r0、r之间之间结束结束p插入到插入到r0、r之间之间结束结束defrp把把p独立出来独立出来=q;p指向指向p0插入到插入到r0,r之间之间:q-next=r;r0-n

14、ext=q插入到链头插入到链头:q-next=base;base=qr=base寻找位置寻找位置r=base r-keykey r!=pr0=r;r=r-next 结束结束defdatakeydatakey.datakeydatakeybase:datakeydatakeydatakeydatakeyr0:r:p:p0:q:(0in;0ji)ji=0 1 1 1 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4 5 6 7 1,1 8 7 6 5 4 7 3 8 5 7 2 7 5 8 3 7 4 5 6 7 8 1分子分子分母分母分子分子分母分母分子分子分母分母分子分子分母分母.显

15、然法雷序列的各项均在区间显然法雷序列的各项均在区间0/1,1/1之内。生成法雷序列算法之内。生成法雷序列算法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生成生成 n

16、 阶阶法雷序列链表法雷序列链表结束结束 for(i=2;i=n;i+)for(j=1;ji;j+)把把 j/i 放入序列放入序列j/i 不可不可约分约分把把 j/i 插入到插入到 r0,r 之间之间查查 j/i 应插入应插入的位置的位置 r0,r/*构造法雷序列构造法雷序列,并返回序列头指针并返回序列头指针*/farleipointer farlei(int n)int i,j;farleipointer fn,r,r0,p;if(n1)/如果如果nnumerator =0;fn-denominator =1;fn-next=(farleipointer)malloc(sizeof(struc

17、t farlei_item);/构造构造1/1 fn-next-numerator =1;fn-next-denominator =1;fn-next-next =NULL;幂次幂次系数系数.幂次幂次系数系数幂次幂次系数系数幂次幂次系数系数52()6.53.40.5p xXXX=52()6.53.40.5p xXXX=56.523.41100.5例如多项式例如多项式可以表示成如下形式可以表示成如下形式:编一个函数，实现多项式加法：编一个函数，实现多项式加法：p(X)+q(X)=s(X)。设有类型说明：设有类型说明：struct item float coef;int exp;struct it

18、em *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