數(shù)據(jù)結構與算法實行大綱

1、數(shù)據(jù)結構與算法實驗大綱一）遠程教育輔導教師基本條件（要求）1. 熟練掌握C語言及其調試開發(fā)環(huán)境;2. 具有用C語言編寫調試中等規(guī)模以上（數(shù)百行源碼）程序的經驗；3. 掌握數(shù)據(jù)結構與算法課程有關的知識,具有較好的算法設計和分析的能力4. 有一定的教學經驗。（二）算法實驗要求綜述根據(jù)目前遠程教育計算機專業(yè)的學生的實際情況和他們的C語言基礎,嚴格按照本科教學要求進行算法實驗上機并完成相應的實驗報告,對多數(shù)學生是有一定困難的.為適應不同基礎的學生循序漸進地學習，我們把實驗要求分成四個層次,希望學生不斷往更高層次要求自己,最終能達到本課程的實驗基本要求.這四個層次的要求是：一. 以熟練使用c語言的開發(fā)環(huán)

2、境（如TC2.0或VC6.0）為主，進行簡單問題的程序設計和調試分析二. 編寫主程序調用調試教材中描述并在課堂中詳細講解過的算法三. 完成習題中的算法設計題并書寫實驗報告四. 獨立完成一個小的應用系統(tǒng)并規(guī)范書寫實驗報告，以進一步提高算法描述和算法分析的能力以上一至三層次作為本課程的基本實驗要求，第四層次作為有能力的學生的提高要求。實驗輔導教師也可以根據(jù)當?shù)貙W生的具體情況,本著能提高學生兩個能力（C語言的編程和調試能力,算法設計和分析能力）的目的,循序漸進地引導學生掌握算法和程序的上機實驗并參考題集的實驗報告范例書寫實驗報告。按教學計劃，本課程實驗課時為15學時，安排6-7次實驗。由于課時數(shù)有限

3、，要求學生在實驗前作好充分準備，否則很難在兩個學時內完成相關的上機與調試。上機前的準備工作主要有兩項：一是仔細閱讀理解書中的相關算法，需要寫解題算法的還要在紙上寫好算法；二是準備好要調試算法的數(shù)據(jù)，并寫好調用算法的主程序。實驗1至實驗6都分為AB兩個實驗。A實驗對應第二層次的能力培養(yǎng)訓練，B實驗對應第三層次的能力培養(yǎng)訓練。下面就每一層次的要求作如下說明。一. 以熟練使用c語言的開發(fā)環(huán)境（如TC2.0或VC6.0）為主，進行一般問題的程序設計和調試分析該能力實際上是預修課C語言的要求，由于有相當部分學生C語言掌握不是很好，影響了數(shù)據(jù)結構算法的描述和理解所以開始應該注意彌補C語言的能力根據(jù)經驗，C

4、語言中函數(shù)定義與調用（形參和實參的對應等），指針，類型定義與使用、結構的定義和使用、動態(tài)內存的申請等難點卻是數(shù)據(jù)結構算法描述的重點，C語言的這些障礙嚴重影響了學生對數(shù)據(jù)結構與算法的理解，也影響了學習數(shù)據(jù)結構的興趣.所以實驗指導教師在鼓勵學生主動補習C語言知識的同時，有意識安排一些符合學生基礎的程序設計練習作為本課程實驗的前導補充與本課程的相公的算法題目可以推后幾周上機本實驗教學計劃的預備實驗（即實驗0）是為完成該任務而設計的。如果學生的困難比較大，盡量在教學計劃時間以外鼓勵學生多做上機，打好基礎。二. 編寫主程序調用調試教材中描述并在課堂中詳細講解過的算法為加深對課堂講解的算法的理解，選擇部分

5、（尤其是基礎部分，如線性表，堆棧與隊列等的順序和鏈式存儲的最常用的基本操作）算法進行上機調試，如第二章的InitList_Sq、Listlnsert_Sq和ListDelete_Sq組算法和第三章的InitStack、GotTop、Push和Pop組算法等。這些算法是后面章節(jié)更復雜算法的基礎（如樹和圖中的算法），算法的積累過程象滾雪球，所以基礎必不可少。調試這些算法要注意兩點。一是適當修改教材算法中的非C語言的語句和增加部分局部變量的定義。由于算法的描述是類C語言的，所以要改為完整的C語言的函數(shù)。不過需要修改（增加）的地方不多。二是書寫一個主程序來調用并調試描述算法的函數(shù)。主程序的設計要根據(jù)算

6、法的功能和調試需要來編寫。本實驗教學計劃的實驗1至實驗6的A實驗是為完成該任務而設計的。三. 完成習題中的算法設計題并書寫實驗報告我們在題集的每章的算法設計題中選擇少量“小問題”的算法設計練習，以培養(yǎng)和提高學生自己動手寫算法的能力。這些算法或者與教材中基本算法類似，或者是延伸，或者是它們的應用。做這些算法設計題時，要注意過程的完整性：題目理解、功能分析、算法思想、描述算法的C函數(shù)、調用算法的主程序、運行結果、調試過程的體會等等，都盡可能書寫出來。養(yǎng)成書寫文檔的好習慣。本實驗教學計劃的實驗1至實驗6的B實驗是為完成該任務而設計的。四完成一個小的應用系統(tǒng)并規(guī)范書寫實驗報告，以進一步提高算法描述和算

7、法分析的能力本實驗教學計劃沒有列出相應的實驗內容。有余力的學生可以選擇一到二個題集中的實習題做。（三）算法實驗內容與指導實驗0:C語言中函數(shù)定義與調用、指針和類型的定義與使用、結構的定義、動態(tài)內存的申請等預備知識（1）實驗目的：回顧復習C語言的重點與難點，熟悉C程序調試環(huán)境，掌握一個完整程序的構成，為以后的實驗打下基礎。（2）實驗要求：熟練掌握C語言及其上機調試環(huán)境（如TC2.0或VC6.0）的操作使用。（3）實驗內容：根據(jù)學生基礎，選擇若干編程題（如C語言中函數(shù)定義與調用、指針和類型的定義與使用、結構的定義、動態(tài)內存的申請等），進行編譯、連接和運行調試。掌握動態(tài)跟蹤調試方法。（4）實驗指導：

8、可以選擇簡單的問題編程，不要求算法的難度，但要能使用相關C語言成分。把注意力集中在編譯和連接錯誤的修改，運行數(shù)據(jù)的輸入輸出和結果分析上。實驗1:線性表的順序表示與鏈式表示的插入與刪除1. A實驗：算法調試（1）實驗目的：加深理解線性表的順序表示與鏈式表示的意義和區(qū)別，理解用它們表示時插入與刪除操作的算法。（2）實驗要求：理解InitList_Sq、Listlnsert_Sq、ListDelete_Sq和InitList_L、Listlnsert_L、ListDelete_L等算法。（3）實驗內容：設計一組輸入數(shù)據(jù)并編寫主程序分別調用上述算法（順序表示的算法為InitList_Sq、Listln

9、sert_Sq、ListDelete_Sq等，鏈式表示的算法為InitList_L、Listlnsert_L、ListDelete_L等），調試程序并對相應的輸出作出分析；修改輸入數(shù)據(jù)，預期輸出并驗證輸出的結果，加深對有關算法的理解。（4）實驗指導：順序表示和鏈式表示可以分成兩個程序來調試（見示例程序1和2）。教材中的算法一般要作少許修改才能運行，這些修改包括：1、算法函數(shù)中局部變量的定義，如Listlnsert_Sq中的i,newbase,p,q等；2、可能出現(xiàn)的“類”C語言的語句，必須改為C語言語句，如數(shù)據(jù)交換語句x>y;3、如果采用TC作為C語言調試環(huán)境，算法函數(shù)的“引用”類型參數(shù)

10、要改為指針類型參數(shù)并修改程序中的使用方法，如Listlnsert_Sq中的參數(shù)&L要改為忙。程序中使用L方法的修改見示例程序1。一個簡單程序通常主要由三部分構成：1、常量定義（#define）,類型定義（typedef）及函數(shù)原型定義（#include）;2、算法函數(shù)，即InitList_Sq、Listlnsert_Sq、ListDelete_Sq等；3、主函數(shù)。示例程序1,InitList_Sq、Listlnsert_Sq、ListDelete_Sq在TC2.0中的調試：#include"stdio.h"#include"malloc.h"#d

11、efineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2#defineLIST_INIT_SIZE10#defineLISTINCREMENT4typedefintStatus;typedefintElemType;typedefstructElemType*elem;intlength;intlistsize;SqList;StatusInitList_Sq(SqList*L)L->elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(Elem

12、Type);if(!L->elem)return(OVERFLOW);L->length=0;L->listsize=LIST_INIT_SIZE;returnOK;StatusListInsert_Sq(SqList*L,inti,ElemTypee)ElemType*q,*p,*newbase;if(i<1|i>L->length+1)returnERROR;if(L->length>=L->listsize)newbase=(ElemType*)realloc(L->elem,(L->listsize+LISTINCREM

13、ENT)*sizeof(ElemType);if(!newbase)return(OVERFLOW);L->elem=newbase;L->listsize+=LISTINCREMENT;q=&(L->elemi-1);for(p=&(L->elemL->length-1);p>=q;-p)*(p+1)=*p;*q=e;+L->length;returnOK;StatusListDelete_Sq(SqList*L,inti,ElemType*e)ElemType*p,*q;if(i<1)|(i>L->length)r

14、eturnERROR;p=&(L->elemi-1);*e=*p;q=(L->elem+L->length-1);for(+p;p<=q;+p)*(p-1)=*p;-L->length;returnOK;voidmain()SqListLst;inti,n=15;ElemTypee;if(InitList_Sq(&Lst)=OK)for(i=1;i<=n;i+)if(ListInsert_Sq(&Lst,i,i)!=OK)break;printf("n");for(i=0;i<Lst.length;i+)pr

15、intf("i,e=%d,%dn",i,Lst.elemi);getch();if(ListDelete_Sq(&Lst,10,&e)=OK)printf("delete_elem=%dn",e);getch();for(i=0;i<Lst.length;i+)printf("i,e=%d,%dn",i,Lst.elemi);elseprintf("delete_elemisfailedn");在VC6.0中的調試：示例程序2,InitList_L、Listlnsert_L、ListDelet

16、e_L#include"math.h"#include"malloc.h"#include"stdio.h"#defineERROR0#defineTRUE1#defineFLASE0#defineOK1#defineINFEASIBLE-1#defineOVERFLOW-2typedefstructLnodeElemTypedata;structLnode*next;Lnode,*LinkList;StatusListInsert_L(LinkList&L,inti,ElemTypee)LinkLists,p;intj;p=

17、L;j=0;while(p&&j<i-1)p=p->next;+j;if(!p|j>i-1)returnERROR;s=(Lnode*)malloc(sizeof(Lnode);if(!s)returnOVERFLOW;s->data=e;s->next=p->next;p->next=s;returnOK;StatusListDelete_L(LinkList&L,inti,ElemType&e)LinkLists,p;intj;p=L;j=0;while(p->next&&j<i-1)p=

18、p->next;+j;if(!(p->next)|j>i-1)returnERROR;s=p->next;p->next=s->next;e=s->data;free(s);returnOK;StatusInitList_L(LinkList&L)L=(Lnode*)malloc(sizeof(Lnode);if(L)L->next=NULL;returnOK;elsereturnERROR;intcmp(Eventa,Eventb);StatusOrderInsert_L(LinkList&L,ElemTypee,int(*cm

19、p)(Eventa,Eventb)Lnode*p,*q;p=(Lnode*)malloc(sizeof(Lnode);if(!p)return(OVERFLOW);p->data=e;q=L;while(q->next&&cmp(e,q->next->data)>0)q=q->next;p->next=q->next;q->next=p;returnOK;intEmptyList(LinkListL)if(!L->next)return1;return0;LinkListGetHead(LinkListL)if(!L-

20、>next)returnNULL;returnL->next;StatusDelFirst(LinkListL,LinkList&p)p=L_>next;if(!p)returnERROR;L->next=p->next;returnOK;voidmain()/主程序略2.B實驗：練習2.11(1) 實驗目的：加深理解線性表的順序表示的插入操作的算法，學會使用現(xiàn)有算法來解決其他問題。(2) 實驗要求：進一步理解InitList_Sq、ListInsert_Sq算法并在其他問題中的使用。(3) 實驗內容：設計一組輸入數(shù)據(jù)并編寫主程序。調試程序并對相應的輸出作

21、出分析；修改輸入數(shù)據(jù)，預期輸出并驗證輸出的結果。(4) 實驗指導：第一步，編寫主程序，首先讀入數(shù)據(jù)并保存在順序表中(可以用ListInsert_Sq進行逐個插入，也可以用循環(huán)語句直接讀入數(shù)組中)，然后讀入一個待插入的數(shù)x;再尋找x應該插入的順序表中的位置i，然后調用ListInsert_Sq插入第i個元素即可。第二步，設計調試數(shù)據(jù)，例如一組遞增有序輸入數(shù)據(jù)(1,3,5,6,7,9,12)以及一個待插入的數(shù)x=8。調試程序。能夠正確插入后再考驗算法的“健壯性”第三步，再取x=0或x=15或x=6進行調試，以考驗算法在“邊界情況”下的正確性。即插入在表頭，表尾以及有重復情況的插入是否正確。還可以再

22、考慮一組遞增有序輸入數(shù)據(jù)為空表時插入元素的正確性。實驗2:順序棧的實現(xiàn)與插入刪除操作1.A實驗：基本算法調試及數(shù)制的轉換算法(1) 實驗目的：加深理解順序棧的意義，理解用它的插入與刪除操作的算法。(2) 實驗要求：理解InitStack、StackEmpty、Push、Pop和conversion等算法。(3) 實驗內容：用數(shù)制的轉換算法調試順序棧的基本操作算法。編寫主程序調用數(shù)制的轉換conversion算法，再由conversion調用InitStack、StackEmpty、Push、Pop修改輸入數(shù)據(jù)，算法。用不同的數(shù)轉換成不同的進制調試程序并對相應的輸出作出分析；預期輸出并驗證輸出的

23、結果，加深對Push和Pop算法的理解。(4) 實驗指導：建立程序的三部分構架：1、常量定義(#define)，類型定義(typedef)2、算法函數(shù)，即InitStack、StackEmpty、3、主函數(shù)。示例程序1,InitStack、StackEmpty、Push和Pop、typedefintSElemType;typedefstructSElemType*base;/*SElemType*top;/*intstacksize;/*SqStack;及函數(shù)原型定義(#include)；Push和Pop、conversion等；conversion等在VC6.0中的調試:在棧構造之前和銷毀之

24、后，棧頂指針*/當前已分配的存儲空間，以元素為單位base的值為NULL*/*/#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineOK1#defineOVERFLOW-1#defineERROR0typedefintStatus;#include<malloc.h>#include<stdio.h>StatusInitStack(SqStack&s)s.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!s.base)return(

25、OVERFLOW);s.top=s.base;s.stacksize=STACK_INIT_SIZE;returnOK;/*InitStack*/StatusPush(SqStack&s,SElemTypee)SElemType*l_temp;if(s.top-s.base>=s.stacksize)/*棧滿,追加存儲空間*/l_temp=(SElemType*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!l_temp)return(OVERFLOW);s.base=l_temp;s.top=

26、s.base+s.stacksize;s.stacksize+=STACKINCREMENT;*(s.top+)=e;returnOK;StatusPop(SqStack&s,SElemType&e)if(s.top=s.base)returnERROR;e=*(-s.top);returnOK;/*Pop*/intStackEmpty(SqStacks)if(s.base=s.top)return1;elsereturn0;voidconversion()SqStacks;intN,b;SElemTypee;InitStack(s);scanf("%d%d"

27、;,&N,&b);while(b>=2&&N)Push(s,N%b);N=N/b;while(!StackEmpty(s)Pop(s,e);printf("%d",e);/*conversion*/voidmain(void)conversion();2.B實驗：練習3.15(1) 實驗目的：加深對堆棧理解，學會靈活運用已有知識，拓廣思路。(2) 實驗要求：按照對InitStack、StackEmpty、Push、Pop等算法理解，理解雙向棧的含義與意義，建立與調試對雙向棧的基本操作算法。(3) 實驗內容：設計一組對雙向棧的操作算法In

28、itStackTws、StackTwsEmpty、PushTws、PopTws并編寫一個主程序調試它們。設計一組輸入數(shù)據(jù)并對相應的輸出作出分析；著重調試空棧、滿棧時的情況。(4) 實驗指導：第一步，理解雙向棧的意義是為了節(jié)省空間，減少棧溢出(滿棧)機會。第二步，寫出雙向棧的操作算法InitStackTws、StackTwsEmpty、PushTwsPopTws第三步，編寫主程序。第四步，設計若干組數(shù)據(jù)調試來算法。實驗3:鏈式隊列與循環(huán)隊列的實現(xiàn)與插入刪除操作1.A實驗：循環(huán)隊列的實現(xiàn)算法實驗目的：(1) 實驗要求：(2) 實驗內容：(3) 實驗指導：示例程序，InitQueue、EnQueue

29、DeQueue等在VC6.0或TC2.0中的調試：#defineNULL0#defineERROR0#defineOVERFLOW-2#defineOK1#defineMAXSIZE10typedefintQElemType;typedefintStatus;typedefstructQElemType*base;intfront;intrear;intsize;SqQueue;StatusInitQueue(SqQueue*Q)Q->base=(QEIemType*)malloc(MAXSIZE*sizeof(QEIemType);if(!Q->base)exit(OVERFLO

30、W);Q_>front=Q->rear=0;Q->size=0;StatusEnQueue(SqQueue*Q,QElemTypee)if(Q->rear+1)%MAXSIZE=Q->front)returnERROR;Q->baseQ->rear=e;Q->rear=(Q->rear+1)%MAXSIZE;returnOK;StatusDeQueue(SqQueue*Q,QElemType*e)if(Q->front=Q->rear)returnERROR;*e=Q->baseQ->front;Q->fron

31、t=(Q->front+1)%MAXSIZE;returnOK;main()SqQueueQ;QEIemTypee,x;inti;InitQueue(&Q);for(i=1;i<=12;i+)scanf("%d",&e);if(EnQueue(&Q,e)=ERROR)printf("toomanynumberinput!n");DeQueue(&Q,&x);DeQueue(&Q,&x);e=12;EnQueue(&Q,e);while(DeQueue(&Q,&x)

32、printf("e=%dn",x);2.B實驗：練習3.28實驗目的：(1) 實驗要求：(2) 實驗內容：(3) 實驗指導：實驗4:數(shù)組的順序存儲表示1.A實驗：數(shù)組的順序存儲表示實現(xiàn)與調試實驗目的：(1) 實驗要求：(2) 實驗內容：(3) 實驗指導：示例程序，InitArray、DestroyArray、Assign、Value等在VC6.0中的調試:#include<malloc.h>#include<stdio.h>#include<stdarg.h>#defineOK1#defineERROR-1#defineOVERFLOW-

33、2#defineNULL0#defineUNDERFLOW-3typedefintElemType;#defineMAX_ARRAY_DIM8typedefstructElemType*base;intdim;int*bounds;int*constants;Array;typedefintStatus;StatusInitArray(Array&A,intdim,.)va_listap;intelemtotal,i;if(dim<1|dim>MAX_ARRAY_DIM)returnERROR;A.dim=dim;A.bounds=(int*)malloc(dim*size

34、of(int);if(!A.bounds)return(OVERFLOW);elemtotal=1;va_start(ap,dim);for(i=0;i<dim;+i)A.boundsi=va_arg(ap,int);if(A.boundsi<0)returnUNDERFLOW;elemtotal*=A.boundsi;va_end(ap);A.base=(ElemType*)malloc(elemtotal*sizeof(ElemType);if(!A.base)return(OVERFLOW);A.constants=(int*)malloc(dim*sizeof(int);i

35、f(!A.constants)return(OVERFLOW);A.constantsdim-1=1;for(i=dim-2;i>=0;-i)A.constantsi=A.boundsi+1*A.constantsi+1;returnOK;StatusDestroyArray(Array&A)if(!A.base)returnERROR;free(A.base);A.base=NULL;if(!A.bounds)returnERROR;free(A.bounds);A.bounds=NULL;if(!A.constants)returnERROR;free(A.constants

36、);A.constants=NULL;returnOK;StatusLocate(ArrayA,va_listap,int&off)inti,ind;off=0;for(i=0;i<A.dim;+i)ind=va_arg(ap,int);if(ind<0|ind>=A.boundsi)returnOVERFLOW;off+=A.constantsi*ind;returnOK;StatusValue(ArrayA,ElemType*e,.)va_listap;va_start(ap,e);Statusresult;intoff;if(result=Locate(A,ap

37、,off)<=0)returnresult;*e=*(A.base+off);va_end(ap);returnOK;StatusAssign(Array&A,ElemTypee,.)va_listap;va_start(ap,e);Statusresult;intoff;if(result=Locate(A,ap,off)<=0)returnresult;*(A.base+off)=e;va_end(ap);returnOK;voidmain()ArrayA;inti,j,e;intm=3,n=4;InitArray(A,2,m,n);for(i=0;i<m;i+)

38、for(j=0;j<n;j+)Assign(A,(i+1)*10+j,i,j);for(i=0;i<m;i+)printf("n");for(j=0;j<n;j+)Value(A，&e,i,j);printf("%4d",e);DestroyArray(A);2.B實驗：練習5.21實驗目的：(1) 實驗要求：(2) 實驗內容：(3) 實驗指導：實驗5:二叉樹的二叉鏈表示與三種遞歸遍歷1.A實驗：算法6.1,6.4的實現(xiàn)與調試實驗目的：(1) 實驗要求：(2) 實驗內容：(3) 實驗指導：示例程序，CreateBiTree、Pr

39、eOrderTraverse、InOrderTraversePostOrderTraverse等在VC6.0中的調試：#include"stdio.h"#include"malloc.h"#defineOK1#defineERROR0#defineOVERFLOW-2#defineNULL0typedefcharTElemType;typedefintStatus;typedefstructBiTNodeTElemTypedata;左右孩子指針structBiTNode*lchild,*rchild;/BiTNode,*BiTree;intn=0;Sta

40、tusCreateBiTree(BiTree&T)charch;scanf("%c",&ch);if(ch='#')T=NULL;elseif(!(T=(BiTNode*)malloc(sizeof(BiTNode)return(OVERFLOW);T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);returnOK;/CreateBiTreeStatusPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)if

41、(T)if(Visit(T->data)if(PreOrderTraverse(T->lchild,Visit)if(PreOrderTraverse(T->rchild,Visit)returnOK;returnERROR;elsereturnOK;/PreOrderTraverseStatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)if(T)if(InOrderTraverse(T->lchild,Visit)if(Visit(T->data)if(InOrderTraverse(T->rchi

42、ld,Visit)returnOK;returnERROR;elsereturnOK;/InOrderTraverseStatusPostOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)if(T)if(PostOrderTraverse(T->lchild,Visit)if(PostOrderTraverse(T->rchild,Visit)if(Visit(T->data)returnOK;returnERROR;elsereturnOK;/PostOrderTraverseStatusprntnode(TEIemTypee)

43、printf(”c",e);returnOK;Statuscountnode(TElemTypee)n+;returnOK;voidmain()BiTreeT;CreateBiTree(T);printf("n”);PreOrderTraverse(T,prntnode);printf("n”);InOrderTraverse(T,prntnode);printf("n”);PostOrderTraverse(T,prntnode);printf("n”);PreOrderTraverse(T,countnode);printf("t

44、henumberofnodeis:%dn",n);2.B實驗：算法6.2實驗目的：(1) 實驗要求：實驗內容：(4)實驗指導：實驗6:二叉樹的線索化1.A實驗:算法6.5,6.6,6.7的調試實驗目的：(1) 實驗要求：InOrderTraverse_Thr(2) 實驗內容：(3) 實驗指導：InOrderThreading等在#include"malloc.h"#include"stdio.h"#defineERROR0#defineOVERFLOW-2#defineOK1示例程序，InThreadingVC6.0中的調試：typedefch

45、arTElemType;typedefintStatus;指針,Thread=1:線索typedefenumLink,ThreadPointerTag;/Link=0:typedefstructBiThrNodeTElemTypedata;左右孩子指針左右標志structBiThrNode*lchild,*rchild;/PointerTagLTag,RTag;/BiThrNode,*BiThrTree;BiThrTreepre;voidInThreading(BiThrTreep)左子樹線索化前驅線索后繼線索保持pre指向p的前驅右子樹線索化/一個全程指針preif(p)InThreading(p->lchild