數(shù)據(jù)結(jié)構(gòu)DOC講義第5章

1、第五章 樹樹是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，是以分支關(guān)系定義的層次結(jié)構(gòu)5.1樹的定義定義定義：樹(tree)是n(n0)個結(jié)點的有限集T，其中：有且僅有一個特定的結(jié)點，稱為樹的根(root)當(dāng)n1時，其余結(jié)點可分為m(m0)個互不相交的有限集T1,T2,Tm，其中每一個集合本身又是一棵樹，稱為根的子樹(subtree)特點：樹中至少有一個結(jié)點一一根樹中各子樹是互不相交的集合根子樹基本術(shù)語結(jié)點(node)表示樹中的元素，包括數(shù)據(jù)項及若干指向其子樹的分支結(jié)點的度(degree)結(jié)點擁有的子樹數(shù)葉子(leaf)度為0的結(jié)點孩子(child)一一結(jié)點子樹的根稱為該結(jié)點的孩子雙親(parents)孩子結(jié)點的

2、上層結(jié)點叫該結(jié)點的兄弟(sibling)同一雙親的孩子樹的度一一一棵樹中最大的結(jié)點度數(shù)結(jié)點的層次(level)一一從根結(jié)點算起，根為第一層，它的孩子為第二層深度(depth)樹中結(jié)點的最大層次數(shù)森林(forestm(m口 0棵互不相交的樹的集合結(jié)點A的度：3結(jié)點B的度：2結(jié)點M的度：0葉子：K，L，F(xiàn)，G，M，I，J結(jié)點A的孩子：B，C，D結(jié)點B的孩子：E，F(xiàn)結(jié)點【的雙親：D結(jié)點L的雙親：E結(jié)點B，C，D為兄弟結(jié)點K，L為兄弟樹的度：3結(jié)點A的層次：1結(jié)點M的層次：4樹的深度：4結(jié)點F，G為堂兄弟結(jié)點A是結(jié)點F，G的祖先5.2二叉樹定義定義：二叉樹是n(n口 0個結(jié)點的有限集，它或為空樹(n=

3、0)，或由一個根結(jié)點和兩棵分別稱 為左子樹和右子樹的互不相交的二叉樹構(gòu)成特點每個結(jié)點至多有二棵子樹(即不存在度大于2的結(jié)點)二叉樹的子樹有左、右之分，且其次序不能任意顛倒基本形態(tài)二叉樹性質(zhì)性質(zhì)1：性質(zhì)3：對任何一棵二叉樹T，如果其終端結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2,則n0=n2+1證明：n1為二叉樹T中度為1的結(jié)點數(shù)因為：二叉樹中所有結(jié)點的度均小于或等于2所以：其結(jié)點總數(shù)n=n0+n1+n2又二叉樹中，除根結(jié)點外，其余結(jié)點都只有一個分支進入設(shè)B為分支總數(shù)，則n=B+1又：分支由度為1和度為2的結(jié)點射出， B=n1+2n2于是，n=B+1=n1+2n2+1=n0+n1+n2 n0=n2+1幾

4、種特殊形式的二叉樹滿二叉樹定義：特點：每一層上的結(jié)點數(shù)都是最大結(jié)點數(shù)完全二叉樹定義：深度為k，有n個結(jié)點的二叉樹當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為k的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)時，稱為特點葉子結(jié)點只可能在層次最大的兩層上出現(xiàn)對任一結(jié)點，若其右分支下子孫的最大層次為1，則其左分支下子孫的最大層次必為l或1+1性質(zhì)性質(zhì)4：性質(zhì)5：如果對一棵有n個結(jié)點的完全二叉樹的結(jié)點按層序編號，則對任一結(jié)點i(1口記n) 有：如果i=1，則結(jié)點i是二叉樹的根，無雙親；如果i1，則其雙親是口 i/2口如果2in，則結(jié)點i無左孩子；如果2迢n則其左孩子是2i如果2i+1n，則結(jié)點i無右孩子；如果2i+1 n則其

5、右孩子是2i+15.3樹的存儲結(jié)構(gòu)樹的存儲結(jié)構(gòu)雙親表示法實現(xiàn)：定義結(jié)構(gòu)數(shù)組存放樹的結(jié)點，每個結(jié)點含兩個域：數(shù)據(jù)域：存放結(jié)點本身信息雙親域：指示本結(jié)點的雙親結(jié)點在數(shù)組中位置特點：找雙親容易，找孩子難typedef struct node( datatype data;int parent;JD;JD tM;0122355510號單元不用或存結(jié)點個數(shù)如何找孩子結(jié)點孩子表示法多重鏈表：每個結(jié)點有多個指針域，分別指向其子樹的根結(jié)點同構(gòu)：結(jié)點的指針個數(shù)相等，為樹的度D結(jié)點不同構(gòu)：結(jié)點指針個數(shù)不等，為該結(jié)點的度d孩子鏈表：每個結(jié)點的孩子結(jié)點用單鏈表存儲，再用含n個元素的結(jié)構(gòu)數(shù)組指向每個孩子鏈 表孩子結(jié)點：

6、typedef struct node int child;該結(jié)點在表頭數(shù)組中下標struct node *next; /指向下一孩子結(jié)點JD;表頭結(jié)點：typedef struct tnode datatype data;/數(shù)據(jù)域struct node *fc;指向第一個孩子結(jié)點TD;TD tM;/t0不用如何找雙親結(jié)點帶雙親的孩子鏈表孩子兄弟表示法（二叉樹表示法）實現(xiàn)：用二叉鏈表作樹的存儲結(jié)構(gòu)，鏈表中每個結(jié)點的兩個指針域分別指向其第一個孩子結(jié)點和下一個兄弟結(jié)點特點操作容易破壞了樹的層次typedef struct node datatype data;struct node *fch, *

7、nsib;JD;二叉樹的存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)實現(xiàn)：按滿二叉樹的結(jié)點層次編號，依次存放二叉樹中的數(shù)據(jù)元素特點：結(jié)點間關(guān)系蘊含在其存儲位置中浪費空間，適于存滿二叉樹和完全二叉樹鏈式存儲結(jié)構(gòu)二叉鏈表typedef struct node( datatype data;struct node *lchild, *rchild;JD;在n個結(jié)點的二叉鏈表中，有n+1個空指針域三叉鏈表typedef struct node ( datatype data;struct node *lchild, *rchild, *parent; JD;樹與二叉樹轉(zhuǎn)換將樹轉(zhuǎn)換成二叉樹加線：在兄弟之間加一連線抹線：對每個結(jié)

8、點，除了其左孩子外，去除其與其余孩子之間的關(guān)系旋轉(zhuǎn)：以樹的根結(jié)點為軸心，將整樹順時針轉(zhuǎn)45樹轉(zhuǎn)換成的二叉樹其右子樹一定為空將二叉樹轉(zhuǎn)換成樹加線：若p結(jié)點是雙親結(jié)點的左孩子，則將p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都與？的雙親用線連起來抹線：抹掉原二叉樹中雙親與右孩子之間的連線調(diào)整：將結(jié)點按層次排列，形成樹結(jié)構(gòu)森林轉(zhuǎn)換成二叉樹將各棵樹分別轉(zhuǎn)換成二叉樹將每棵樹的根結(jié)點用線相連以第一棵樹根結(jié)點為二叉樹的根，再以根結(jié)點為軸心，順時針旋轉(zhuǎn)，構(gòu)成二叉樹型結(jié)構(gòu)二叉樹轉(zhuǎn)換成森林抹線:將二叉樹中根結(jié)點與其右孩子連線，及沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成孤立的二叉樹還原：將孤立的二

9、叉樹還原成樹5.4樹和二叉樹的遍歷樹的遍歷遍歷一一按一定規(guī)律走遍樹的各個頂點，且使每一頂點僅被訪問一次，即找一個完整而有規(guī)律的走法，以得到樹中所有結(jié)點的一個線性排列常用方法先根（序）遍歷：先訪問樹的根結(jié)點，然后依次先根遍歷根的每棵子樹后根（序）遍歷：先依次后根遍歷每棵子樹，然后訪問根結(jié)點按層次遍歷：先訪問第一層上的結(jié)點，然后依次遍歷第二層，第n層的結(jié)點先序遍歷：后序遍歷：層次遍歷：ABEFIGCDHNOMEIFGBCJKNOLMHDAABCDEFGHIJKLMNO二叉樹的遍歷方法先序遍歷：先訪問根結(jié)點，然后分別先序遍歷左子樹、右子樹中序遍歷：先中序遍歷左子樹，然后訪問根結(jié)點，最后中序遍歷右子樹

10、后序遍歷：先后序遍歷左、右子樹，然后訪問根結(jié)點按層次遍歷：從上到下、從左到右訪問各結(jié)點DLR先序遍歷序列：A B D C先序遍歷：LDR中序遍歷序列：B D A C中序遍歷：LRD后序遍歷序列：D B C A后序遍歷：先序遍歷：中序遍歷：后序遍歷：層次遍歷：-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef*b-cd/ef算法遞歸算法Ch5_1.cvoid preorder(JD *bt) if(bt!=NULL)( printf(%dt”,bt-data);preorder(bt-lchild);preorder(bt-rchild);返回返回返回返回ACBD返回先序序列：A

11、 B D C非遞歸算法Ch5_4.cCh5_40.C后序遍歷非遞歸算法遍歷算法應(yīng)用按先序遍歷序列建立二叉樹的二叉鏈表，已知先序序列為：ABC D E G F 求二叉樹深度算法Ch5_5.cch5_6.cCh5_1.c統(tǒng)計二叉樹中葉子結(jié)點個數(shù)算法5.5二叉樹的應(yīng)用哈夫曼樹(Huffman)帶權(quán)路徑長度最短的樹定義路徑：從樹中一個結(jié)點到另一個結(jié)點之間的分支構(gòu)成這兩個結(jié)點間的 路徑長度：路徑上的分支數(shù)樹的路徑長度：從樹根到每一個結(jié)點的路徑長度之和 樹的帶權(quán)路徑長度：樹中所有帶權(quán)結(jié)點的路徑長度之和Huffman樹設(shè)有n個權(quán)值w1,w2,wn，構(gòu)造一棵有n個葉子結(jié)點的二叉樹，每個葉子的權(quán)值為wi,則wp

12、l最小的二叉樹叫 例 有4個結(jié)點，權(quán)值分別為7，5，2，4，構(gòu)造有4個葉子結(jié)點的二叉樹WPL=7*2+5*2+2*2+4*2=36WPL=7*3+5*3+2*1+4*2=46WPL=7*1+5*2+2*3+4*3=35 構(gòu)造Huffman樹的方法Huffman算法構(gòu)造Huffman樹步驟根據(jù)給定的n個權(quán)值w1,w2,wn，構(gòu)造n棵只有根結(jié)點的二叉樹，令起權(quán)值為wj在森林中選取兩棵根結(jié)點權(quán)值最小的樹作左右子樹，構(gòu)造一棵新的二叉樹，置新二叉樹根結(jié) 點權(quán)值為其左右子樹根結(jié)點權(quán)值之和在森林中刪除這兩棵樹，同時將新得到的二叉樹加入森林中 重復(fù)上述兩步，直到只含一棵樹為止，這棵樹即哈夫曼樹 例 w=5,

13、29, 7, 8, 14, 23, 3, 11 Huffman算法實現(xiàn)Ch5_8.c一棵有n個葉子結(jié)點的Huffman樹有2n-1個結(jié)點采用順序存儲結(jié)構(gòu)一一一維結(jié)構(gòu)數(shù)組 結(jié)點類型定義 typedef struct int data;int pa,lc,rc;JD;Ch5_8.cHuffman樹應(yīng)用最佳判定樹Huffman編碼：數(shù)據(jù)通信用的二進制編碼 思想：根據(jù)字符出現(xiàn)頻率編碼，使電文總長最短編碼：根據(jù)字符出現(xiàn)頻率構(gòu)造Huffman樹，然后將樹中結(jié)點引向其左孩子的分支標“0”， 引向其右孩子的分支標“1”；每個字符的編碼即為從根到每個葉子的路徑上得到的0、1序 列例要傳輸?shù)淖址疍=C,A,S,

14、T, ; 字符出現(xiàn)頻率w=2,4,2,3,3 TOC o 1-5 h z T :00;:01A :10C :110S :111譯碼：從Huffman樹根開始，從待譯碼電文中逐位取碼。若編碼是“0”，則向左走；若編 碼是“1”，則向右走，一旦到達葉子結(jié)點，則譯出一個字符；再重新從根出發(fā)，直到電文結(jié)束例 電文是CAS;CAT;SAT;AT其編碼“1101011101110100001111100001100”電文為“1101000”譯文只能是“ CAT”線索二叉樹定義：前驅(qū)與后繼：在二叉樹的先序、中序或后序遍歷序列中兩個相鄰的結(jié)點互稱為線索：指向前驅(qū)或后繼結(jié)點的指針稱為線索二叉樹：加上線索的二叉鏈

15、表表示的二叉樹叫線索化：對二叉樹按某種遍歷次序使其變?yōu)榫€索二叉樹的過程叫實現(xiàn)在有n個結(jié)點的二叉鏈表中必定有n+1個空鏈域在線索二叉樹的結(jié)點中增加兩個標志域lt :若lt =0, lc域指向左孩子；若lt=1, lc域指向其前驅(qū)rt :若rt =0, rc域指向右孩子；若rt=1, rc域指向其后繼結(jié)點定義：typedef struct node int data;int lt, rt;struct node *lc, *rc;JD;00001111A1100001111A110000111111A頭結(jié)點：lt=O, 1c指向根結(jié)點rt=l, rc指向遍歷序列中最后一個結(jié)點遍歷序列中第一個結(jié)點的

16、lc域和最后 一個結(jié)點的rc域都指向頭結(jié)點 算法按中序線索化二叉樹Ch5_20.cJD *zxxsh(JD *bt) JD *p,*pr,*sM,*t;int i=0;t=(JD *)malloc(sizeof(JD);t-lt=O; t-rt=l; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt;do while(p!=NULL) (si+=p; p=p-lc; if(i0) (P=s-i;printf(%c ,p-data); if(p-lc=NULL) p-lt=l; p-lc=pr; if(pr-rc=NULL) pr-rt=l

17、; pr-rc=p; pr=p; p=p-rc;while(iOllp!=NULL);pr-rc=t; pr-rt=l; t-rc=pr; return(t);算法按中序線索化二叉樹Ch5_20.cJD *zxxsh(JD *bt) JD *p,*pr,*sM,*t;int i=0;t=(JD *)malloc(sizeof(JD); t-lt=O; t-rt=l; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt;do while(p!=NULL) (si+=p; p=p-lc; if(i0) (P=s-i;printf(%c ,p-d

18、ata); if(p-lc=NULL) p-lt=l; p-lc=pr; if(pr-rc=NULL) pr-rt=l; pr-rc=p; pr=p; p=p-rc;while(iOllp!=NULL);pr-rc=t; pr-rt=l; t-rc=pr; return(t);算法按中序線索化二叉樹Ch5_20.cJD *zxxsh(JD *bt) JD *p,*pr,*sM,*t;int i=0;t=(JD *)malloc(sizeof(JD); t-lt=O; t-rt=l; t-TC=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt;do

19、while(p!=NULL) (si+=p; p=p-lc; if(i0) (P=s-i;printf(%c ,p-data); if(p-lc=NULL) p-lt=l; p-lc=pr; if(pr-rc=NULL) pr-rt=l; pr-rc=p; pr=p; p=p-rc;while(iOllp!=NULL);pr-rc=t; pr-rt= 1; t-rc=pr; return(t);算法按中序線索化二叉樹Ch5_20.c輸出:BJD *zxxsh(JD *bt) JD *p,*pr,*sM,*t;int i=0;t=(JD *)malloc(sizeof(JD); t-lt=O;

20、t-rt=l; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt;do while(p!=NULL) (si+=p; p=p-lc; if(i0) (P=s-i;printf(%c ,p-data); if(p-lc=NULL) p-lt= 1; p-lc=pr; if(pr-rc=NULL) pr-rt=l; pr-rc=p; pr=p; p=p-rc;while(iOllp!=NULL);pr-rc=t; pr-rt=l; t-rc=pr; return(t);1算法按中序線索化二叉樹Ch5_20.c輸出:BP-CJD *zxxsh(

21、JD *bt) JD *p,*pr,*sM,*t;int i=0;t=(JD *)malloc(sizeof(JD); t-lt=O; t-rt=l; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt;do while(p!=NULL) (si+=p; p=p-lc; if(i0) (P=s-i;printf(%c ,p-data); if(p-lc=NULL) p-lt=l; p-lc=pr; if(pr-rc=NULL) pr-rt=l; pr-rc=p; pr=p; p=p-rc;while(iOllp!=NULL);pr-rc=t

22、; pr-rt=l; t-rc=pr; return(t);算法按中序線索化二叉樹Ch5_20.cP-C輸出:BJD *zxxsh(JD *bt) JD *p,*pr,*sM,*t;int i=0;t=(JD *)malloc(sizeof(JD); t-lt=O; t-rt=l; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt;do while(p!=NULL) (si+=p; p=p-lc; if(i0)(P=s-i;printf(%c ,p-data); if(p-lc=NULL) p-lt=l; p-lc=pr; if(pr-r

23、c=NULL) pr-rt= 1; pr-rc=p;pr=p; p=p-rc;while(iOllp!=NULL);pr-rc=t; pr-rt=l; t-rc=pr;return(t);算法按中序線索化二叉樹Ch5_20.c輸出:B CJD *zxxsh(JD *bt)( JD *p,*pr,*sM,*t;int i=0;t=(JD *)malloc(sizeof(JD); t-lt=O; t-rt=l; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt;do while(p!=NULL) (si+=p; p=p-lc; if(i0)

24、(P=s-i;printf(%c ,p-data); if(p-lc=NULL) p-lt=l; p-lc=pr; if(pr-rc=NULL) pr-rt=l; pr-rc=p; pr=p; p=p-rc;while(iOllp!=NULL);pr-rc=t; pr-rt=l; t-rc=pr;return(t);1算法按中序線索化二叉樹 Ch5_20.c i 輸出:B C JD *zxxsh(JD *bt) JD *p,*pr,*sM,*t; int i=0;t=(JD *)malloc(sizeof(JD); t-lt=O; t-rt=l; t-rc=t; if(bt=NULL) t-l

25、c=t; else t-lc=bt; pr=t; p=bt; do while(p! =NULL) (si+=p; p=p-lc; if(i0) (P=s-i;printf(%c ,p-data); if(p-lc=NULL) p-lt=l; p-lc=pr; if(pr-rc=NULL) pr-rt=l; pr-rc=p; pr=p; p=p-rc; while(iOllp!=NULL); pr-rc=t; pr-rt=l; t-rc=pr; return(t); 算法 按中序線索化二叉樹 Ch5_20.c i 輸出:B C A JD *zxxsh(JD *bt) JD *p,*pr,*sM

26、,*t;int i=0; t=(JD *)malloc(sizeof(JD); t-lt=O; t-rt=l; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt;do while(p! =NULL) (si+=p; p=p-lc; if(i0)(p=s-i;printf(%c ,p-data); if(p-lc=NULL) p-lt=l; p-lc=pr; if(pr-rc=NULL) pr-rt=l; pr-rc=p; pr=p; p=p-rc;while(iOllp!=NULL);pr-rc=t; pr-rt=l; t-rc=pr;

27、return(t);1算法按中序線索化二叉樹Ch5_20.c輸出:B C AP-DJD *zxxsh(JD *bt) JD *p,*pr,*sM,*t;int i=0;t=(JD *)malloc(sizeof(JD); t-lt=O; t-rt=l; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt;do while(p!=NULL) (si+=p; p=p-lc; if(i0) (P=s-i;printf(%c ,p-data); if(p-lc=NULL) p-lt=l; p-lc=pr; if(pr-rc=NULL) pr-rt=

28、l; pr-rc=p; pr=p; p=p-rc;while(iOllp!=NULL);pr-rc=t; pr-rt=l; t-rc=pr; return(t);算法按中序線索化二叉樹Ch5_20.c輸出:B C AP-DP-EJD *zxxsh(JD *bt) JD *p,*pr,*sM,*t;int i=0;t=(JD *)malloc(sizeof(JD); t-lt=O; t-rt=l; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt;do while(p!=NULL) (si+=p; p=p-lc; if(i0) (P=s-i

29、;printf(%c ,p-data); if(p-lc=NULL) p-lt=l; p-lc=pr; if(pr-rc=NULL) pr-rt=l; pr-rc=p; pr=p; p=p-rc;while(iOllp!=NULL);pr-rc=t; pr-rt=l; t-rc=pr; return(t);算法按中序線索化二叉樹Ch5_20.c輸出:B C AP-DP-EJD *zxxsh(JD *bt) JD *p,*pr,*sM,*t;int i=0;t=(JD *)malloc(sizeof(JD); t-lt=O; t-rt=l; t-rc=t; if(bt=NULL) t-lc=t;

30、else t-lc=bt; pr=t; p=bt; do while(p! =NULL) (si+=p; p=p-lc; if(i0) (P=s-i;printf(%c ,p-data); if(p-lc=NULL) p-lt=l; p-lc=pr; if(pr-rc=NULL) pr-rt=l; pr-rc=p; pr=p; p=p-rc;while(iOllp!=NULL);pr-rc=t; pr-rt=l; t-rc=pr; return(t);算法按中序線索化二叉樹Ch5_20.c輸出:B CAEP-DJD *zxxsh(JD *bt) JD *p,*pr,*sM,*t;int i=0

31、;t=(JD *)malloc(sizeof(JD); t-lt=O; t-rt=l; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt; do while(p! =NULL) (si+=p; p=p-lc; if(i0) (P=s-i;printf(%c ,p-data); if(p-lc=NULL) p-lt=l; p-lc=pr; if(pr-rc=NULL) pr-rt=l; pr-rc=p; pr=p; p=p-rc;while(iOllp!=NULL);pr-rc=t; pr-rt=1; t-rc=pr;return(t);1

32、算法按中序線索化二叉樹Ch5_20.ci輸出:B CAEP-DJD *zxxsh(JD *bt) JD *p,*pr,*sM,*t;int i=0;t=(JD *)malloc(sizeof(JD);t-lt=0; t-rt=1; t-rc=t;if(bt=NULL) t-lc=t;else t-lc=bt; pr=t; p=bt;do while(p!=NULL)si+=p; p=p-lc; if(i0)p=s-i;printf(%c ,p-data);if(p-lc=NULL)p-lt=1; p-lc=pr;if(pr-rc=NULL)pr-rt=1; pr-rc=p;pr=p; p=p-

33、rc;while(i0|p!=NULL);pr-rc=t; pr-rt=1; t-rc=pr;return(t);算法按中序線索化二叉樹Ch5_20.ci輸出: B C A E DJD *zxxsh(JD *bt) JD *p,*pr,*sM,*t;int i=0;t=(JD *)malloc(sizeof(JD);t-lt=O; t-rt=l; t-rc=t; if(bt=NULL) t-lc=t; else t-lc=bt; pr=t; p=bt;do while(p!=NULL) (si+=p; p=p-lc; if(i0) (p=s-i;printf(%c ,p-data); if(p-lc=NULL) p-lt=l; p-lc=pr; if(pr-rc=NULL) pr-rt=l; pr-rc=p; pr=p; p=p-rc;while(iOllp!=NULL);pr-rc=t; pr-rt=l; t-r