數(shù)據(jù)結(jié)構(gòu)導論算法匯總

數(shù)據(jù)結(jié)構(gòu)導論算法匯總第2章線性表voiderror(charch_1[])/*['er?]*/{printf("\t%s\n",ch_1);return;}1、順序表（1）類型定義constmaxsize=順序表的容量;/*constn.常量，常數(shù)*/typedefstruct{datatypedata[maxsize];intlast;}sqlist;/*sequence['si:kw?ns]vt.按順序排好.list[list]n.列表*/（2）插入voidinsert_sqlist(sqlist*L,datatypex,inti)/*改成*L后就變成了值傳遞方式，這樣才成功*/{ intj; if((*L).last==maxsize)error("biaoman"); if((i<1)||(i>(*L).last+1))error("feifaweizhi"); for(j=(*L).last;j>=i;j--) (*L).data[j]=(*L).data[j-1]; (*L).data[i-1]=x; (*L).last++;}/*最壞情況時間復雜性n，平均時間復雜性n/2，平均時間復雜性量級O(n)*/（3）刪除voiddelete_sqlist(sqlist*L,inti){ intj;if((i<1)||(i>L->last))error("feifaweizhi");for(j=i+1;j<=L->last;j++)L->data[j-2]=L->data[j-1]; L->last--;}/*最壞情況時間復雜性n-1，平均時間復雜性(n-1)/2，平均移動(n-1)/2個元素，平均時間復雜性量級O(n)*/（4）定位intlocate_sqlist(sqlistL,datatypex){ inti=1; while((i<=L.last)&&(L.data[i-1]!=x)) i++; if(i<=L.last)return(i); elsereturn(0);}/*平均時間復雜性量級O(n)*/2.單鏈表（默認帶頭結(jié)點）（1）類型定義typedefstructnode*pointer;structnode{ datatypedata; pointernext;};/*此處的“；”不能少*/typedefpointerlklist;/*link[li?k]n.鏈環(huán)，環(huán)節(jié)pointer['p?int?]n.指針*/（2）初始化#defineNULL0lklistinitiate_lklist()/*[i'ni?ieit,i'ni?i?t,-eit]vt.開始，創(chuàng)始*/{ lklistt; t=(lklist)malloc(sizeof(lklist)); t->next=NULL; return(t);}（3）求表長intlength_lklist(lklisthead)/*[le?θ,le?kθ]*/{ pointerp=head; intj=0; while(p->next) { p=p->next; j++; } return(j);}/*時間復雜性量級O(n)*/（4）按序號查找#defineNULL0pointerfind_lklist(lklisthead,inti){pointerp=head;intj=0; while((p->next)&&(j<i)) { p=p->next; j++; } if(i==j)return(p); elsereturn(NULL);}/*查找成功需平均比較個結(jié)點*/（5）定位intlocate_lklist(lklisthead,datatypex){ pointerp=head; intj=0; while((p->next)&&(p->data!=x)) { p=p->next; j++; } if(p->data==x)return(j); elsereturn(0);}/*時間復雜性量級O(n)*/（6）刪除voiddelete_lklist(lklisthead,inti){ pointerp,q; p=find_lklist(head,i-1); if(p&&p->next) { q=p->next; p->next=q->next; free(q); } elseerror("bucuncaidi'i'gejiedian");}（7）插入voidinsert_lklist(lklisthead,datatypex,inti){ pointerp,s; p=find_lklist(head,i-1); if(p==NULL) error("bucunzaidi'i'geweizhi"); else { s=(pointer)malloc(sizeof(pointer)); s->data=x; s->next=p->next; p->next=s; }}/*時間復雜性量級O(n)*/（8）建表1lklistcreate_lklist1()/*[kri'eit]*/{ lklisthead; inti=1; datatypex; head=initiate_lklist(); scanf("%c",&x);/*如果datatype是int類型，%c就要改成%d*/ while(x!='$')/*輸入的不是結(jié)束標志時繼續(xù)鏈入，結(jié)束標志也要作相應的改動*/ { insert_lklist(head,x,i); i++; scanf("%c",&x);/*如果datatype是int類型，%c就要改成%d*/ } return(head);}/*時間復雜性≈n(n-1)/2，量級*/（9）建表2#defineNULL0lklistcreate_lklist2()/*[kri'eit]*/{ lklisthead; pointerp,q; datatypex; head=(lklist)malloc(sizeof(lklist)); p=head; scanf("%c",&x);/*如果datatype是int類型，%c就要改成%d*/ while(x!='$')/*如果datatype是int類型，用10000或別的數(shù)作結(jié)束標志*/ { q=(pointer)malloc(sizeof(pointer)); q->data=x; p->next=q; p=q; scanf("%c",&x);/*如果datatype是int類型，%c就要改成%d*/ } p->next=NULL; return(head);}/*時間復雜性量級O(n)*/（10）清除重復結(jié)點voidpurge_lklist(lklisthead)/*purge[p?:d?]vt.凈化；清洗*/{ pointerp,q,r; p=head->next; if(!p)return; while(p->next) { q=p; while(q->next) if(q->next->data==p->data) { r=q->next; q->next=r->next; free(r); } elseq=q->next; p=p->next; } }3.其它鏈表（1）循環(huán)鏈表①帶頭結(jié)點，只設(shè)尾指針<1>類型定義typedefstructlinked_queue{ datatypedata; structlinked_queue*next;}LqueueTp;typedefstructqueueptr{ LqueueTp*rear;}QueptrTp;<2>初始化voidInitQueue(QueptrTp*lq){ LqueueTp*p; p=(LqueueTp*)malloc(sizeof(LqueueTp)); lq->rear=p; lq->rear->next=lq->rear;}<3>入隊列voidEnQueue(QueptrTp*lq,datatypex){ LqueueTp*p; p=(LqueueTp*)malloc(sizeof(LqueueTp)); p->data=x; p->next=lq->rear->next; lq->rear->next=p; lq->rear=p;}<4>出隊列intOutQueue(QueptrTp*lq,datatype*x){ LqueueTp*p,*s; if(lq->rear->next==lq->rear) { error("Queueisempty!"); return(0); } else { p=lq->rear->next; s=p->next; *x=s->data; p->next=s->next; if(s==lq->rear)lq->rear=p;/*如果此時隊列中只剩下頭結(jié)點和尾結(jié)點，讓尾指針指向頭結(jié)點，這樣才能恢復到初始化狀態(tài)，這步不能少，而雙鏈表中卻不能有這步*/ free(s); return(1); }}（2）雙鏈表（當成有頭結(jié)點的隊列來處理）①類型定義typedefstructlinked_queue{ datatypedata; structlinked_queue*prior,*next;/*['prai?]adj.在先的，在前的*/}LqueueTp;typedefstructqueueptr{ LqueueTp*head;}QueptrTp;/*摘除*/p->prior->next=p->next;/*p指向待刪結(jié)點，兩語句可顛倒*/p->next->prior=p->prior;/*鏈入*/q->prior=p;/*p后面鏈入q*/q->next=p->next;p->next->prior=q;p->next=q;②初始化voidInitQueue(QueptrTp*lq){ LqueueTp*p; p=(LqueueTp*)malloc(sizeof(LqueueTp)); lq->head=p; lq->head->prior=lq->head; lq->head->next=lq->head;}③入隊列voidEnQueue(QueptrTp*lq,datatypex)/*插在頭結(jié)點之前*/{ LqueueTp*p; p=(LqueueTp*)malloc(sizeof(LqueueTp)); p->data=x; p->prior=lq->head->prior; p->next=lq->head; lq->head->prior->next=p; lq->head->prior=p;}=4\*GB3④出隊列intOutQueue(QueptrTp*lq,datatype*x){ LqueueTp*p,*s; if(lq->head->next==lq->head) { error("Queueisempty!"); return(0); } else { p=lq->head->next; s=p->next; *x=p->data; lq->head->next=s; s->prior=lq->head; free(p); return(1); }}=5\*GB3⑤定位intLocate_Queue(QueptrTp*lq,datatypex){ inti=1; LqueueTp*p; p=lq->head->next; while((p->data!=x)&&(p!=lq->head)) { p=p->next; i++; } if(p->data==x)returni; elsereturn0;}=6\*GB3⑥插入voidInsert_Queue(QueptrTp*lq,datatypex,inti){ intj=0; LqueueTp*p,*q; p=lq->head; while((j<i-1)&&(p->next!=lq->head)) { p=p->next; j++; } if(j==i-1) { q=(LqueueTp*)malloc(sizeof(LqueueTp)); q->data=x; q->prior=p; q->next=p->next; p->next->prior=q; p->next=q; } elseerror("bucuncaidi'i'geweizhi!");}=7\*GB3⑦刪除voidDelete_Queue(QueptrTp*lq,inti){ intj=0; LqueueTp*p,*q; p=lq->head; while((j<i-1)&&(p->next!=lq->head)) { p=p->next; j++; } if(j==i-1) { q=p->next; p->next=q->next; q->next->prior=p; free(q); } elseerror("bucuncaidi'i'geweizhi!");}4.串（1）順序串的類型定義constmaxlen=串的最大長度;typedefstruct{ charch[maxlen]; intcurlen;}string;/*current['k?r?nt]adj.現(xiàn)在的。length[le?θ,le?kθ]n.長度string[stri?]n.一串，一行*/（2）鏈串的類型定義constnodesize=用戶定義的結(jié)點大小;typedefstructnode*pointer;structnode{ charch[nodesize]; pointernext;};typedefpointerstrlist;當結(jié)點大小為1時，可將ch域簡單地定義為：charch;

第3章棧、隊列和數(shù)組voiderror(charch_1[])/*['er?]*/{printf("\t%s\n",ch_1);}1.棧（1）順序棧=1\*GB3①類型定義#definesqstack_maxsize6#definedatatypechartypedefstructsqstack{ datatypedata[sqstack_maxsize]; inttop;}SqStackTp;/*sequence['si:kw?ns]n.序列；順序。stack[st?k]n.堆。type[taip]n.類型，品種*/=2\*GB3②初始化intInitStack(SqStackTp*sq){ sq->top=0; return(1);}=3\*GB3③進棧intPush(SqStackTp*sq,datatypex)/*[pu?]*/{ if(sq->top==sqstack_maxsize-1) { error("Stackiffull!"); return(0); } else { sq->top++; sq->data[sq->top]=x; return(1); }}=4\*GB3④退棧intPop(SqStackTp*sq,datatype*x)/*[p?p]*/{ if(!(sq->top)) { error("Stackunderflow.");/*[‘?nd?fl?u]n.下溢*/ return(0); } else { *x=sq->data[sq->top]; sq->top--; return(1); }}=5\*GB3⑤判?？読ntEmptyStack(SqStackTpsq){ if(sq.top)return(0); elsereturn(1);}=6\*GB3⑥讀棧頂intGetTop(SqStackTp*sq,datatype*x){ if(sq->top) { *x=sq->data[sq->top]; return(1); } elsereturn(0);}（2）鏈棧=1\*GB3①類型定義/*為避免與單鏈表的結(jié)點定義重復，將node改成stacknode，并且類型定義也與教科書P45不同，按教科書P45的定義，編譯時不能通過。*/typedefstructstacknode{ datatypedata; structstacknode*next;}StackNode;typedefstruct{ StackNode*top;}LStackTp;/*link[li?k]stack[st?k]type[taip]的簡寫*/=2\*GB3②初始化voidInitStack(LStackTp*ls){ls->top=NULL;}=3\*GB3③進棧voidPush(LStackTp*ls,datatypex){StackNode*p=(StackNode*)malloc(sizeof(StackNode));p->data=x;p->next=ls->top;ls->top=p;}=4\*GB3④退棧intPop(LStackTp*ls,datatype*x){ StackNode*p=ls->top;if(!p) { error("Stackunderflow!");/*[‘?nd?fl?u]*/ return(0); } else { *x=p->data; ls->top=p->next; free(p); return(1); }}=5\*GB3⑤判?？読ntEmptyStack(LStackTp*ls){return(ls->top==NULL);}=6\*GB3⑥讀棧頂元素intGetTop(LStackTp*ls,datatype*x){ if(ls->top) { *x=ls->top->data; return(1); } else { error("Stackisempty."); return(0); }}=7\*GB3⑦置?？誺oidSetEmpty(LStackTp*ls){ while(ls->top) { StackNode*p=ls->top;/*不停定義，保存棧頂指針*/ ls->top=p->next;/*刪除原棧頂結(jié)點*/ free(p); } }2．隊列（1）順序隊列類型定義#definemaxsize20#definedatatypechartypedefstructsqqueue{ datatypedata[maxsize]; intfront,rear;/*[fr?nt],[ri?]*/}SqQueueTp;SqQueueTpsq;/*sequence['si:kw?ns]queue[kju:]type[taip]的簡寫*/（2）循環(huán)隊列=1\*GB3①類型定義#definemaxsize20#definedatatypechartypedefstructcycqueue{ datatypedata[maxsize]; intfront,rear;}CycqueueTp;CycqueueTpsq;/*cycle['saikl]queue[kju:]type[taip]的簡寫*/=2\*GB3②初始化voidInitCycQueue(CycqueueTp*sq){ sq->front=0; sq->rear=0;}=3\*GB3③入隊列intEnCycQueue(CycqueueTp*sq,datatypex){ if((sq->rear+1)%maxsize==sq->front) { error("Queueisfull!"); return(0); } else { sq->rear=(sq->rear+1)%maxsize; sq->data[sq->rear]=x; return(1); }}=4\*GB3④出隊列intOutCycQueue(CycqueueTp*sq,datatype*x){ if(sq->front==sq->rear) { error("Queueunderflow!"); return(0); } else { sq->front=(sq->front+1)%maxsize; *x=sq->data[sq->front]; return(1); }}=5\*GB3⑤判隊空intEmptyCycQueue(CycqueueTpsq){ return(sq.rear==sq.front);}=6\*GB3⑥取隊頭intGetHead(CycqueueTpsq,datatype*x){ if(sq.rear==sq.front)return(0); else { *x=sq.data[(sq.front+1)%maxsize]; return(1); }}=7\*GB3⑦求隊長/*教材p72習題6*/intLengthCycQueue(CycqueueTpsq){ Intlen; len=(sq.rear-sq.front+maxsize)%maxsize; return(len);}（3）鏈隊=1\*GB3①類型定義#defineNULL0typedefstructlinked_queue{ datatypedata; structlinked_queue*next;}LqueueTp;/*link[li?k]queue[kju:]type[taip]的簡寫*/typedefstructqueueptr/*queue[kju:]pointer['p?int?]的簡寫*/{ LqueueTp*front,*rear;}QueptrTp;/*queue[kju:]pointer['p?int?]type[taip]的簡寫*/QueptrTplq;=2\*GB3②初始化voidInitQueue(QueptrTp*lq){ LqueueTp*p; p=(LqueueTp*)malloc(sizeof(LqueueTp)); lq->front=p; lq->rear=p; lq->front->next=NULL;}=3\*GB3③入隊列voidEnQueue(QueptrTp*lq,datatypex){ LqueueTp*p; p=(LqueueTp*)malloc(sizeof(LqueueTp)); p->data=x; p->next=NULL; lq->rear->next=p; lq->rear=p;}=4\*GB3④出隊列intOutQueue(QueptrTp*lq,datatype*x){ LqueueTp*s; if(lq->front==lq->rear) { error("Queueunderflow!"); return(0); } else { s=lq->front->next; *x=s->data; lq->front->next=s->next; if(s->next==NULL)lq->rear=lq->front;/*如果此時隊列中只剩下頭結(jié)點，讓尾指針指向頭指針，這樣才能恢復到初始化狀態(tài)*/ free(s); return(1); }}=5\*GB3⑤判隊空intEmptyQueue(QueptrTplq){ return(lq.rear==lq.front);}=6\*GB3⑥讀隊頭intGetHead(QueptrTplq,datatype*x){ LqueueTp*p; if(lq.rear==lq.front)return(0); else { p=lq.front->next; *x=p->data; return(1); }}3.數(shù)組（1）三元組表的類型定義#definedatatypeint#definemaxnum10typedefstructnode{ inti,j; datatypev;}Node;typedefstructspmatrix{ intmu,nu,tu; Nodedata[maxnum+1];/*假定三元組的下標的起始值為1*/}SpMatrixTp;/*sparse[spɑ:s]adj.稀疏的；稀少的。matrix['meitriks]n.矩陣。type[taip]n.類型。*/（2）基于三元組的稀疏矩陣轉(zhuǎn)置=1\*GB3①按照A的列序轉(zhuǎn)置intTrans_Sparmat(SpMatrixTpa,SpMatrixTp*b)/*translate[tr?ns’leit]vt.轉(zhuǎn)變?yōu)?/{ intp,q,col;/*column['k?l?m]n.列*/ (*b).mu=a.nu,(*b).nu=a.mu, (*b).tu=a.tu; if(a.tu) { q=1; for(col=1;col<=a.nu;col++) for(p=1;p<=a.tu;p++) if(a.data[p].j==col) { (*b).data[q].i=a.data[p].j; (*b).data[q].j=a.data[p].i; (*b).data[q].v=a.data[p].v; q++; } } return(1);}算法的時間復雜度為O(nu×tu)，只有在tu<<mu×nu才有實際意義。=2\*GB3②按照A的三元組a.data的次序轉(zhuǎn)置voidFast_Trans_Sparmat(SpMatrixTpa,SpMatrixTp*b){ intcol,t,p,q,cpot[20],num[20];/*假設(shè)矩陣a的列數(shù)最大為19*/ (*b).mu=a.nu,(*b).nu=a.mu,(*b).tu=a.tu; if(a.tu) { for(col=1;col<=a.nu;col++) num[col]=0;/*num[col]表示矩陣a中第col列中非零元的個數(shù)，將它置0*/ for(t=1;t<=a.tu;t++)/*t是total的第1個字母*/ num[a.data[t].j]++; cpot[1]=1;/*cpot[col]表示a中第col列的第1個非零元在(*b).data中的恰當位置*/ for(col=2;col<=a.nu;col++) cpot[col]=cpot[col-1]+num[col-1]; for(p=1;p<=a.tu;p++) { col=a.data[p].j;q=cpot[col]; (*b).data[q].i=a.data[p].j; (*b).data[q].j=a.data[p].i; (*b).data[q].v=a.data[p].v; cpot[col]++; } }}算法的時間復雜度為O(nu+tu)。

第4章樹1、二叉鏈表的類型定義typedefstructbtnode*bitreptr;structbtnode{ datatypedata; bitreptrlchild,rchild;};bitreptrroot;/*bi-[bi:]表示“二”。tree[tri:]n.樹；pointer['p?int?]n.指針.root[ru:t,rut]n.根*/（1）二叉樹的遍歷=1\*GB3①先根遍歷<1>遞歸算法voidpreorder(bitreptrr)/*pre-[,pri:]表示“在…之前”之義.order[‘?:d?]vt.整理*/{ if(r) { visit(r); preorder(r->lchild); preorder(r->rchild); }}<2>非遞歸算法1（二叉樹存放在鏈式存儲結(jié)構(gòu)中，教材P91）voidpreorder1(bitreptrt)/*先根遍歷根結(jié)點為t的二叉樹*/{ bitreptrs,stack[stacksize];/*工作棧*/ inttop; top=0,stack[top]=t;/*根指針進棧*/ while(top>=0) { s=stack[top];/*讀棧頂元素到s中*/ top--;/*退棧*/ while(s) { visit(s);/*先根遍歷，該句處于第一位置*/ top++; stack[top]=s->rchild;/*右指針進棧保存*/ s=s->lchild;/*修改s以便繼續(xù)遍歷左子樹*/ } }}<3>非遞歸算法2（二叉樹存放在順序存儲結(jié)構(gòu)中，教材P104-9，輔P115-4）voidpreorder(datatypea[],intn)/*a[i]表示二叉樹以順序存儲，n為元素個數(shù)*/{ inti=1,j; SqStackTpsd; InitStack(&sd);/*初始化工作棧*/ Push(&sd,0); if(i<=n) { visit(a[i]);/*訪問此結(jié)點*/ Push(&sd,i); j=2*i;/*取左子樹*/ while(!EmptyStack(sd))/*若棧sd非空*/ { while(j<=n)/*若2i<=n則該結(jié)點有左子樹*/ { Push(&sd,j);/*進棧*/ i=j;/*取左子樹*/ visit(a[i]);/*訪問此結(jié)點*/ j=2*i; } i=Pop(&sd);/*出棧*/ j=2*i+1;/*取右子樹*/ } }}=2\*GB3②中根遍歷<1>遞歸算法voidinorder(bitreptrr)/*in[in]prep.在…之內(nèi)；ordervt.整理*/{ if(r) { inorder(r->lchild); visit(r); inorder(r->rchild); }}<2>非遞歸算法voidinorder(bitreptrT){ SqStackTps; InitStack(&s); while(T||(!EmptyStack(s))) { while(T) { Push(&s,T); T=T->lchild;/*向左下找下一結(jié)點*/ } if(!EmptyStack(s)) { Pop(&s,&T);/*退出下一結(jié)點*/ visit(T);/*中根遍歷，該句處于第二位置*/ T=T->rchild;/*遍歷右子樹*/ }elsereturn;/*沒這句將退不出最外層while循環(huán)*/ }}=3\*GB3③后根遍歷voidpostorder(bitreptrr)/*post-[p?ust]pref.表示“在…后”之義*/{ if(r) { postorder(r->lchild); postorder(r->rchild); visit(r); }}=4\*GB3④層次遍歷/*借用隊列來完成，只要隊列不空，就出隊，然后判斷該結(jié)點是否有左孩子和右孩子，如有就依次輸出左右孩子的值，然后讓左右孩子入隊*/voidlayorder(bitreptrT){ QueptrTpq; bitreptrp; InitQueue(&q); if(T) { visit(T); EnQueue(&q,T); while(!EmptyQueue(q)) { OutQueue(&q,p); if(p->lchild) { visit(p->lchild); EnQueue(&q,p->lchild); } if(p->rchild) { visit(p->rchild); EnQueue(&q,p->rchild); } } }}（2）求二叉樹的葉子數(shù)voidcountleaf(bitreptrt,int*count)/*count[kaunt]vi.計數(shù)；leaf[li:f]n.葉子；假定*count的初值為0*/{ if(t) { if((t->lchild==NULL)&&(t-rchild==NULL)) *count++; countleaf(t->lchild,&count); countleaf(t->rchild,&count); }}（3）遞歸消除計算n!intf1(intn){ inti,y=1; for(i=1;i<=n;i++) y=y*i; return(y);}斐波那齊函數(shù)的非遞歸算法（教材P89）intFib(intn){inti,x,y,z; if(n==0)return(0); else { x=0,y=1;/*x←Fib(0),y←Fib(1)*/ for(i=2;i<=n;i++)/*計算Fib(i),保持x=Fib(i-2),y=Fib(i-1)*/ { z=y;/*z←Fib(i-1)*/ y=x+y;/*y←Fib(i-1)+Fib(i-2)=Fib(i)*/ x=z;/*x←Fib(i-1)*/ } return(y); }}2、三叉鏈表的類型定義typedefstructttnode*ttnodeptr;structttnode{ datatypedata; ttnodeptrlchild,rchild,parent;};ttnodeptrroot;/*three[θri:]n.三.tree[tri:]n.樹；pointer['p?int?]n.指針*/3、樹的類型定義（1）不帶雙親的孩子鏈表類型定義typedefstructtagnode /*表結(jié)點類型tag[t?ɡ]n.標簽*/{ intchild; /*孩子結(jié)點在表頭數(shù)據(jù)組中的序號*/ structtagnode*next; /*表結(jié)點指針域*/}node,*link; typedefstruct /*頭結(jié)點類型*/{ datatypedata; /*結(jié)點數(shù)據(jù)元素*/ linkheadptr; /*頭結(jié)點指針域*/}headnode;typedefheadnodechildlink[axnode]; /*表頭結(jié)點數(shù)組，ax[?ks]n.斧頭*/（2）帶雙親的孩子鏈表類型定義typedefstructtagnode /*表結(jié)點類型*/{ intchild; /*孩子結(jié)點在表頭數(shù)據(jù)組中的序號*/ structtagnode*next; /*表結(jié)點指針域*/}node,*link; typedefstruct /*頭結(jié)點類型*/{ datatypedata; /*結(jié)點數(shù)據(jù)元素*/ intparent; linkheadptr; /*頭結(jié)點指針域*/}headnode;typedefheadnodechildlink[axnode]; /*表頭結(jié)點數(shù)組*/（3）孩子兄弟鏈表類型定義typedefstructbtnode*bitreptr;/*與二叉鏈表完全一樣*/structbtnode{ datatypedata; bitreptrlchild,rchild;/*lchild代表長子，rchild代表大弟*/};bitreptrroot;/*bi-[bi:]表示“二”。tree[tri:]n.樹；pointer['p?int?]n.指針.root[ru:t,rut]n.根*/（4）靜態(tài)雙親鏈表的類型定義#definesize結(jié)點數(shù)typedefstruct{ datatypedata; intparent;}node;typedefnodestatlist[size];/*static['st?tik]adj.靜態(tài)的*/4、哈夫曼樹（1）數(shù)組元素類型定義typedefstruct{ floatwt;/*weight[weit]【統(tǒng)】權(quán)*/ intparent,lchild,rchild;}node;typedefnodehftree[2*n-1];（2）哈夫曼算法#definemaxint32767/*maxint定義為int型的最大值32767*/voidhuffman(intk,floatW[k],hftreeT)/*k為有權(quán)值的原始葉結(jié)點的個數(shù)*/{ inti,j,x,y; floatm,n; for(i=0;i<2*k-1;i++)/*初始化*/ { T[i].parent=-1,T[i].lchild=-1,T[i].rchild=-1; if(i<k)T[i].wt=W[i]; elseT[i].wt=0; } for(i=0;i<k-1;i++)/*構(gòu)造新二叉樹，合并k-1次，見下面的詳解*/ { x=0,y=0,m=maxint,n=maxint; for(j=0;j<k+i;j++)/*在所有結(jié)點中找2棵權(quán)值最小的二叉樹,注意k+i,輔導P102錯*/ if((T[j].wt<m)&&(T[j].parent==-1)) { n=m,y=x,m=T[j].wt,x=j; } elseif((T[j].wt<n)&&(T[j].parent==-1)) { n=T[j].wt,y=j; } T[x].parent=k+i,T[y].parent=k+i; T[k+i].wt=m+n; T[k+i].lchild=x,T[k+i].rchild=y; }}詳解第2個for循環(huán)：for(i=0;i<5-1;i++)/*構(gòu)造新二叉樹，合并k-1次*/{i=0時： x=0,y=0,m=32767,n=32767;/*int型的最大值為32767*/ for(j=0;j<5+0;j++)/*在所有結(jié)點中找2棵權(quán)值最小的二叉樹,注意k+I,輔導P102錯*/ { j=0時：n=32767,y=0,m=0.2,x=0; j=1時：n=0.2,y=1; j=2時：空操作；因為T[2].wt=0.3 j=3時：空操作；因為T[3].wt=0.2 j=4時：n=0.2,y=0,m=0.1,x=4; } T[4].parent=5+0,T[0].parent=5+0; T[5].wt=0.2+0.1; T[5].lchild=4,T[5].rchild=0;構(gòu)造成下圖：i=1時： x=0,y=0,m=32767,n=32767; for(j=0;j<5+1;j++)/*在所有結(jié)點中找2棵權(quán)值最小的二叉樹,注意k+I,輔導P102錯*/ { j=0時：空操作；因為T[0].parent=5 j=1時：n=32767,y=0,m=0.2,x=1; j=2時：n=0.3,y=2; j=3時：空操作；因為T[3].wt=0.2 j=4時：空操作；因為T[4].parent=5 j=5時：空操作；因為T[5].wt=0.3 } T[1].parent=5+1,T[2].parent=5+1; T[6].wt=0.2+0.3; T[6].lchild=1,T[6].rchild=2;構(gòu)造成下圖：i=2時： x=0,y=0,m=32767,n=32767; for(j=0;j<5+2;j++)/*在所有結(jié)點中找2棵權(quán)值最小的二叉樹,注意k+I,輔導P102錯*/ { j=0時：空操作；因為T[0].parent=5 j=1時：空操作；因為T[1].parent=6 j=2時：空操作；因為T[2].parent=6 j=3時：n=32767,y=0,m=0.2,x=3; j=4時：空操作；因為T[4].parent=5 j=5時：n=0.3,y=5; j=6時：空操作；因為T[6].wt=0.5 } T[3].parent=5+2,T[5].parent=5+2; T[7].wt=0.2+0.3; T[7].lchild=1,T[7].rchild=2; 構(gòu)造成下圖：i=3時： x=0,y=0,m=32767,n=32767; for(j=0;j<5+3;j++)/*在所有結(jié)點中找2棵權(quán)值最小的二叉樹,注意k+I,輔導P102錯*/ { j=0時：空操作；因為T[0].parent=5 j=1時：空操作；因為T[1].parent=6 j=2時：空操作；因為T[2].parent=6 j=3時：空操作；因為T[3].parent=7 j=4時：空操作；因為T[4].parent=5 j=5時：空操作；因為T[5].parent=7 j=6時：n=32767,y=0,m=0.5,x=6; j=7時：n=0.5,y=7; } T[6].parent=5+3,T[7].parent=5+3; T[8].wt=0.5+0.5; T[8].lchild=6,T[8].rchild=7; 構(gòu)造成下圖：}

第5章圖1.圖的鄰接矩陣#definevnum20typedefstructgraph/*[ɡrɑ:f,ɡr?f]n.[數(shù)]圖表；曲線圖*/{ VertexTypevexs[vnum];/*vertex['v?:teks]n.頂點；頭頂；天頂*/ intarcs[vnum][vnum];/*arc[ɑ:k]n.?。ǘ龋?/ intvexnum,arcnum;}GraphTp;2.網(wǎng)的鄰接矩陣#definevnum20typedefstructgraph{ VertexTypevexs[vnum]; WeightTypearcs[vnum][vnum];/*weight[weit](統(tǒng)計)權(quán)，權(quán)重，權(quán)數(shù)*/ intvexnum,arcnum;}GraphTp;3.無向網(wǎng)鄰接矩陣的建立#defineINT_MAX32767voidCreatGraph(GraphTp*ga){ inti,j,n,e,w; charch; scanf("%d%d",&n,&e);/*讀入頂點個數(shù)和邊數(shù)*/ ga->vexnum=n; ga->arcnum=e; for(i=0;i<ga->vexnum;i++) { scanf("%c",&ch);/*讀入頂點信息*/ ga->vexs[i]=ch; } for(i=0;i<ga->vexnum;i++) for(j=0;j<ga->vexnum;j++) ga->arcs[i][j]=INT_MAX;/*初始化鄰接矩陣*/ for(k=0;k<ga->arcnum;k++) { scanf("%d%d%d",&i,&j,&w);/*讀入邊（頂點對）和權(quán)值*/ ga->arcs[i][j]=w; ga->arcs[j][i]=w; }}4.鄰接表（1）類型定義#definevnum20/*頂點數(shù)*/typedefstructarcnode/*邊結(jié)點*/{ intadjvex;/*下一條邊的始點編號,鄰接點*/ structarcnode*nextarc;/*指向下一條邊的指針，下一條邊*/}ArcNodeTp;/*adjacent[?'d?eis?nt]adj.鄰近的。邊結(jié)點類型*/typedefstructvexnode/*頂點結(jié)點*/{ intvertex;/*頂點編號，頂點*/ ArcNodeTp*firstarc;/*指向第一條邊的指針，第一條邊*/}AdjList[vnum];/*鄰接表*/typedefstructgraph/*圖*/{ AdjListadjlist;/*鄰接表*/ intvexnum,arcnum;/*頂點和邊的個數(shù)*/}GraphTp;/*圖類型*/（2）建立鄰接表CreatAdjlist(GraphTp*ga){ intn,e,i,j,k; ArcNodeTp*p; scanf("%d%d",n,e); ga->vexnum=n; ga->arcnum=e; for(i=0;i<n;i++) { ga->adjlist[i].vertex=i; ga->adjlist[i].firstarc=NULL; } for(k=0;k<e;k++) { scanf("%d%d",&i,&j); p=(ArcNodeTp*)malloc(sizeof(ArcNodeTp)); p->adjvex=j; p->nextarc=ga->adjlist[i].firstarc; ga->adjlist[i].firstarc=p; }} 以圖5-2G1為例詳解：ga->vexnum=4;ga->arcnum=5;for(i=1;i<=4;i++){ i=1,ga->adjlist[1].vertex=1; ga->adjlist[1].firstarc=NULL; i=2,ga->adjlist[2].vertex=1; ga->adjlist[2].firstarc=NULL; i=3,ga->adjlist[3].vertex=1; ga->adjlist[3].firstarc=NULL; i=4,ga->adjlist[4].vertex=1; ga->adjlist[4].firstarc=NULL;}for(k=1;k<=6;k++){ k=1; <1,2>,i=1,j=2; p=(ArcNodeTp*)malloc(sizeof(ArcNodeTp)); p->adjvex=2; p->nextarc=ga->adjlist[1].firstarc; ga->adjlist[1].firstarc=p; k=2; <2,3>,i=2,j=3; p=(ArcNodeTp*)malloc(sizeof(ArcNodeTp)); p->adjvex=3; p->nextarc=ga->adjlist[2].firstarc=NULL; ga->adjlist[2].firstarc=p; k=3; <3,1>,i=3,j=1; p=(ArcNodeTp*)malloc(sizeof(ArcNodeTp)); p->adjvex=1; p->nextarc=ga->adjlist[3].firstarc=NULL; ga->adjlist[3].firstarc=p; k=4; <3,4>,i=3,j=4; p=(ArcNodeTp*)malloc(sizeof(ArcNodeTp)); p->adjvex=4; p->nextarc=ga->adjlist[3].firstarc; ga->adjlist[3].firstarc=p; k=5; <1,4>,i=1,j=4; p=(ArcNodeTp*)malloc(sizeof(ArcNodeTp)); p->adjvex=4; p->nextarc=ga->adjlist[1].firstarc; ga->adjlist[1].firstarc=p;k=6; <2,1>,i=2,j=1; p=(ArcNodeTp*)malloc(sizeof(ArcNodeTp)); p->adjvex=1; p->nextarc=ga->adjlist[2].firstarc; ga->adjlist[2].firstarc=p;}說明：最后得到的鄰接表與教材P112圖5-9（a）不同，是由于按照教材P107，E={<v1,v2>,<v2,v3>,<v3,v1>,<v3,v4>,<v1,v4>,<v2,v1>}的順序輸入的；如果按照E={<v1,v4>,<v2,v3>,<v3,v4>,<v3,v1>,<v1,v2>,<v2,v1>}的順序輸入，結(jié)果就與教材P112圖5-9（a）相同。鄰接表只表達鄰接關(guān)系，不在意邊的先后。（3）深度優(yōu)先搜索=1\*GB3①圖的存儲結(jié)構(gòu)為鄰接表voidDfs(GraphTpg,intv)/*depth[depθ]n.深度；first,search[s?:t?]*/{ ArcNodeTp*p; printf("%d",v);/*訪問頂點*/ visited[v]=1;/*置已訪問標志*/ p=g.adjlist[v].firstarc; while(p) { if(!visited[p->adjvex])Dfs(g,p->adjvex); p=p->nextarc; }}/*visited為非局部量，第1次調(diào)用Dfs前需將visited的每個下標變量初始化為0*/=2\*GB3②圖的存儲結(jié)構(gòu)為鄰接矩陣voiddfs(inta[][],intv,intn)/*n為圖結(jié)點的個數(shù)，visited數(shù)組初值為0*/{ intw=1; printf("%d",v); visited[v]=1; while((w<=n)&&(a[v][w]==0)) w++; while(w<=n) { if(!visited[w]) dfs(a,w,n); w++; }}（4）廣度優(yōu)先搜索=1\*GB3①圖的存儲結(jié)構(gòu)為鄰接表，隊列采用鏈隊列voidBfs(GraphTpg,intv)/*breadth[bredθ]n.寬度，幅度；first,search[s?:t?]*/{ QueptrTpQ; ArcNodeTp*p; InitQueue(&Q); printf("%d",v); visited[v]=1; EnQueue(&Q,v); while(!EmptyQueue(Q)) { OutQueue(&Q,&v); p=g.adjlist[v].firstarc; while(p) { if(!visited[p->adjvex]) { printf("%d",p->adjvex); visited[p->adjvex]=1; EnQueue(&Q,p->adjvex); } p=p->nextarc; } }}/*visited為非局部量，第1次調(diào)用Dfs前需將visited的每個下標變量初始化為0*/=2\*GB3②圖的存儲結(jié)構(gòu)為鄰接矩陣，隊列采用鏈隊列voidbfs(inta[][],intv,intn)/*n為圖結(jié)點的個數(shù)，visited數(shù)組初值為0*/{ intw; QueptrTpQ; InitQueue(&Q); printf("%d",v); visited[v]=1; EnQueue(&Q,v); while(!EmptyQueue(Q)) { OutQueue(&Q,&v); w=1; while(w<=n) { if(!visited[w]) { printf("%d",w); visited[w]=1; EnQueue(&Q,w); } w++; } }}（5）圖的連通分量計算/*圖的存儲結(jié)構(gòu)為鄰接表，調(diào)用深度優(yōu)先算法*/intvisited[vnum];voidCount_Component(GraphTpg)/*component[k?m'p?un?nt]n.成分；組件*/{ intv,count=0; for(v=0;v<g.vexnum;v++) visited[v]=0; for(v=0;v<g.vexnum;v++) if(!visited[v]) { count++; printf("連通分量%d包含以下頂點：",count); Dfs(g,v); printf("\n"); } printf("共有%d個連通分量\n",count);} 5.最小生成樹#defineINT_MAX32767struct{ intadjvex;/*adjacent[?'d?eis?nt]adj.鄰近的,vertex['v?:teks]n.頂點*/ intlowcost;/*low[l?u]adj.低的.cost[k?st]n.費用，代價*/}closedge[vnum];/*closed[kl?uzd]adj.關(guān)著的；edge[ed?]n.邊*/voidprim(GraphTpg,intu)/*prim[prim]adj.循規(guī)蹈矩的*/{ intv,k,j,min; for(v=0;v<g.vexnum;v++) if(v!=u) { closedge[v].adjvex=u; closedge[v].lowcost=g.adjlist[u][v]; } closedge[u].lowcost=INT_MAX; for(k=0;k<g.vexnum;k++) { min=closedge[k].lowcost; v=k; for(j=0;j<g.vexnum;j++) if(closedge[j].lowcost<min) { min=closedge[j].lowcost; v=j; } printf("%d%d\n",closedge[v].adjvex,v); closedge[v].lowcost=INT_MAX; for(j=0;j<g.vexnum;j++) if(g.adjlist[v][j]<closedge[j].lowcost) { closedge[j].lowcost=g.adjlist[v][j]; closedge[j].adjvex=v; } }}/*時間復雜度為O()*/6.拓撲排序#definevnum20typedefstructarcnode{ intadjvex; structarcnode*nextarc;}ArcNodeTp;typedefstructvexnode{ VertexTypevertex; intin; ArcNodeTp*firstarc;}AdjList[vnum];typedefstructgraph{ AdjListadjlist; intvexnum,arcnum;}GraphTp;intTop_Sort(GraphTpg){ LStackTp*S; ArcNodeTp*p; intm=0,i,v; InitStack(S); for(i=0;i<g.vexnum;i++) if(g.adjlist[i].in==0) push(S,i) while(!EmptyStack(S)) { Pop(S,&v); printf("%d",v); m++; p=g.adjlist[v].firstarc; while(p) { (g.adjlist[p->adjvex].in)--; if(g.adjlist[p->adjvex].in==0) Push(S,p->adjvex); p=p->nextarc; } } if(m<g.vexnum)return0;/*圖含有環(huán)*/ elsereturn1;/*拓撲排序完成*/}/*時間復雜度為O(n+e)*/第6章查找表1.作為靜態(tài)查找表存儲結(jié)構(gòu)的順序表的類型定義：#definemaxsize靜態(tài)查找表的表長;typedefstruct{ keytypekey;/*關(guān)鍵字*/ ……/*其它域*/}rec;typedefstruct{ recitem[maxsize+1];/*['ait?m]n.條款，項目；一則*/ intn;/*最后一個數(shù)據(jù)元素的下標*/}sqtable;2.順序查找法intsearch_sqtable(sqtableR,keytypeK){inti; R.item[0].key=K;/*設(shè)置崗哨*/ i=R.n; while(R.item[i].key!=K)i--; return(i);}3.二分查找法（1）非遞歸算法intbinsearch1(sqtableR,keytypeK){ intlow=1,hig=R.n,mid; while(low<=hig) { mid=(low+hig)/2; switch { caseK==R.item[mid].key:return(mid); caseK<R.item[mid].key:hig=mid-1;break; caseK>R.item[mid].key:low=mid+1;break; } } return(0);}（2）遞歸算法intbinsearch2(sqtableR,intlow,inthigh,keytypeK){ intmid; if(low>high)return(0); else { mid=(low+hig)/2; switch { caseK==R.item[mid].key:return(mid); caseK<R.item[mid].key:return(binsearch2(R,low,mid-1,K)); caseK>R.item[mid].key:return(binsearch2(R,mid+1,high,K)); } }}4.二叉排序樹上的查找bitreptrsearch_bst(bitreptrt,keytypeK){ if(!t)return(NULL); elseswitch { caset->key==K:return(t); caset->key>K:return(search_bst(t->lchild,K)); caset->key<K:return(search_bst(t->rchild,K)); }}5.二叉排序樹上的插入bit