数据结构导论算法汇总

数据结构导论算法汇总第2章线性表voiderror(charch_1[])/*['erə]*/{printf("\t%s\n",ch_1);return;}1、顺序表（1）类型定义constmaxsize=顺序表的容量;/*constn.常量，常数*/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.单链表（默认带头结点）（1）类型定义typedefstructnode*pointer;structnode{ datatypedata; pointernext;};/*此处的“；”不能少*/typedefpointerlklist;/*link[liŋk]n.链环，环节pointer['pɔintə]n.指针*/（2）初始化#defineNULL0lklistinitiate_lklist()/*[i'niʃieit,i'niʃiət,-eit]vt.开始，创始*/{ 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);}/*查找成功需平均比较个结点*/（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!='$')/*输入的不是结束标志时继续链入，结束标志也要作相应的改动*/ { 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或别的数作结束标志*/ { 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）清除重复结点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）循环链表①带头结点，只设尾指针<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;/*如果此时队列中只剩下头结点和尾结点，让尾指针指向头结点，这样才能恢复到初始化状态，这步不能少，而双链表中却不能有这步*/ free(s); return(1); }}（2）双链表（当成有头结点的队列来处理）①类型定义typedefstructlinked_queue{ datatypedata; structlinked_queue*prior,*next;/*['praiə]adj.在先的，在前的*/}LqueueTp;typedefstructqueueptr{ LqueueTp*head;}QueptrTp;/*摘除*/p->prior->next=p->next;/*p指向待删结点，两语句可颠倒*/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)/*插在头结点之前*/{ 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.现在的。length[leŋθ,leŋkθ]n.长度string[striŋ]n.一串，一行*/（2）链串的类型定义constnodesize=用户定义的结点大小;typedefstructnode*pointer;structnode{ charch[nodesize]; pointernext;};typedefpointerstrlist;当结点大小为1时，可将ch域简单地定义为：charch;

第3章栈、队列和数组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⑤判栈空intEmptyStack(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①类型定义/*为避免与单链表的结点定义重复，将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⑤判栈空intEmptyStack(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⑦置栈空voidSetEmpty(LStackTp*ls){ while(ls->top) { StackNode*p=ls->top;/*不停定义，保存栈顶指针*/ ls->top=p->next;/*删除原栈顶结点*/ free(p); } }2．队列（1）顺序队列类型定义#definemaxsize20#definedatatypechartypedefstructsqqueue{ datatypedata[maxsize]; intfront,rear;/*[frʌnt],[riə]*/}SqQueueTp;SqQueueTpsq;/*sequence['si:kwəns]queue[kju:]type[taip]的简写*/（2）循环队列=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;/*如果此时队列中只剩下头结点，让尾指针指向头指针，这样才能恢复到初始化状态*/ 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.数组（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）基于三元组的稀疏矩阵转置=1\*GB3①按照A的列序转置intTrans_Sparmat(SpMatrixTpa,SpMatrixTp*b)/*translate[træns’leit]vt.转变为*/{ 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的次序转置voidFast_Trans_Sparmat(SpMatrixTpa,SpMatrixTp*b){ intcol,t,p,q,cpot[20],num[20];/*假设矩阵a的列数最大为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列中非零元的个数，将它置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（二叉树存放在链式存储结构中，教材P91）voidpreorder1(bitreptrt)/*先根遍历根结点为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以便继续遍历左子树*/ } }}<3>非递归算法2（二叉树存放在顺序存储结构中，教材P104-9，辅P115-4）voidpreorder(datatypea[],intn)/*a[i]表示二叉树以顺序存储，n为元素个数*/{ inti=1,j; SqStackTpsd; InitStack(&sd);/*初始化工作栈*/ Push(&sd,0); if(i<=n) { visit(a[i]);/*访问此结点*/ Push(&sd,i); j=2*i;/*取左子树*/ while(!EmptyStack(sd))/*若栈sd非空*/ { while(j<=n)/*若2i<=n则该结点有左子树*/ { Push(&sd,j);/*进栈*/ i=j;/*取左子树*/ visit(a[i]);/*访问此结点*/ j=2*i; } i=Pop(&sd);/*出栈*/ j=2*i+1;/*取右子树*/ } }}=2\*GB3②中根遍历<1>递归算法voidinorder(bitreptrr)/*in[in]prep.在…之内；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;/*向左下找下一结点*/ } if(!EmptyStack(s)) { Pop(&s,&T);/*退出下一结点*/ visit(T);/*中根遍历，该句处于第二位置*/ T=T->rchild;/*遍历右子树*/ }elsereturn;/*没这句将退不出最外层while循环*/ }}=3\*GB3③后根遍历voidpostorder(bitreptrr)/*post-[pəust]pref.表示“在…后”之义*/{ if(r) { postorder(r->lchild); postorder(r->rchild); visit(r); }}=4\*GB3④层次遍历/*借用队列来完成，只要队列不空，就出队，然后判断该结点是否有左孩子和右孩子，如有就依次输出左右孩子的值，然后让左右孩子入队*/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）求二叉树的叶子数voidcountleaf(bitreptrt,int*count)/*count[kaunt]vi.计数；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);}斐波那齐函数的非递归算法（教材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 /*表结点类型tag[tæɡ]n.标签*/{ intchild; /*孩子结点在表头数据组中的序号*/ structtagnode*next; /*表结点指针域*/}node,*link; typedefstruct /*头结点类型*/{ datatypedata; /*结点数据元素*/ linkheadptr; /*头结点指针域*/}headnode;typedefheadnodechildlink[axnode]; /*表头结点数组，ax[æks]n.斧头*/（2）带双亲的孩子链表类型定义typedefstructtagnode /*表结点类型*/{ intchild; /*孩子结点在表头数据组中的序号*/ structtagnode*next; /*表结点指针域*/}node,*link; typedefstruct /*头结点类型*/{ datatypedata; /*结点数据元素*/ intparent; linkheadptr; /*头结点指针域*/}headnode;typedefheadnodechildlink[axnode]; /*表头结点数组*/（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）静态双亲链表的类型定义#definesize结点数typedefstruct{ datatypedata; intparent;}node;typedefnodestatlist[size];/*static['stætik]adj.静态的*/4、哈夫曼树（1）数组元素类型定义typedefstruct{ floatwt;/*weight[weit]【统】权*/ intparent,lchild,rchild;}node;typedefnodehftree[2*n-1];（2）哈夫曼算法#definemaxint32767/*maxint定义为int型的最大值32767*/voidhuffman(intk,floatW[k],hftreeT)/*k为有权值的原始叶结点的个数*/{ 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++)/*构造新二叉树，合并k-1次，见下面的详解*/ { x=0,y=0,m=maxint,n=maxint; for(j=0;j<k+i;j++)/*在所有结点中找2棵权值最小的二叉树,注意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循环：for(i=0;i<5-1;i++)/*构造新二叉树，合并k-1次*/{i=0时： x=0,y=0,m=32767,n=32767;/*int型的最大值为32767*/ for(j=0;j<5+0;j++)/*在所有结点中找2棵权值最小的二叉树,注意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;构造成下图：i=1时： x=0,y=0,m=32767,n=32767; for(j=0;j<5+1;j++)/*在所有结点中找2棵权值最小的二叉树,注意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;构造成下图：i=2时： x=0,y=0,m=32767,n=32767; for(j=0;j<5+2;j++)/*在所有结点中找2棵权值最小的二叉树,注意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; 构造成下图：i=3时： x=0,y=0,m=32767,n=32767; for(j=0;j<5+3;j++)/*在所有结点中找2棵权值最小的二叉树,注意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; 构造成下图：}

第5章图1.图的邻接矩阵#definevnum20typedefstructgraph/*[ɡrɑ:f,ɡræf]n.[数]图表；曲线图*/{ VertexTypevexs[vnum];/*vertex['və:teks]n.顶点；头顶；天顶*/ intarcs[vnum][vnum];/*arc[ɑ:k]n.弧（度）；*/ intvexnum,arcnum;}GraphTp;2.网的邻接矩阵#definevnum20typedefstructgraph{ VertexTypevexs[vnum]; WeightTypearcs[vnum][vnum];/*weight[weit](统计)权，权重，权数*/ intvexnum,arcnum;}GraphTp;3.无向网邻接矩阵的建立#defineINT_MAX32767voidCreatGraph(GraphTp*ga){ inti,j,n,e,w; charch; scanf("%d%d",&n,&e);/*读入顶点个数和边数*/ 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);/*读入边（顶点对）和权值*/ ga->arcs[i][j]=w; ga->arcs[j][i]=w; }}4.邻接表（1）类型定义#definevnum20/*顶点数*/typedefstructarcnode/*边结点*/{ intadjvex;/*下一条边的始点编号,邻接点*/ structarcnode*nextarc;/*指向下一条边的指针，下一条边*/}ArcNodeTp;/*adjacent[ə'dʒeisənt]adj.邻近的。边结点类型*/typedefstructvexnode/*顶点结点*/{ intvertex;/*顶点编号，顶点*/ ArcNodeTp*firstarc;/*指向第一条边的指针，第一条边*/}AdjList[vnum];/*邻接表*/typedefstructgraph/*图*/{ AdjListadjlist;/*邻接表*/ intvexnum,arcnum;/*顶点和边的个数*/}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>}的顺序输入，结果就与教材P112图5-9（a）相同。邻接表只表达邻接关系，不在意边的先后。（3）深度优先搜索=1\*GB3①图的存储结构为邻接表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次调用Dfs前需将visited的每个下标变量初始化为0*/=2\*GB3②图的存储结构为邻接矩阵voiddfs(inta[][],intv,intn)/*n为图结点的个数，visited数组初值为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）广度优先搜索=1\*GB3①图的存储结构为邻接表，队列采用链队列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次调用Dfs前需将visited的每个下标变量初始化为0*/=2\*GB3②图的存储结构为邻接矩阵，队列采用链队列voidbfs(inta[][],intv,intn)/*n为图结点的个数，visited数组初值为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）图的连通分量计算/*图的存储结构为邻接表，调用深度优先算法*/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.关着的；edge[edʒ]n.边*/voidprim(GraphTpg,intu)/*prim[prim]adj.循规蹈矩的*/{ 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;/*图含有环*/ elsereturn1;/*拓扑排序完成*/}/*时间复杂度为O(n+e)*/第6章查找表1.作为静态查找表存储结构的顺序表的类型定义：#definemaxsize静态查找表的表长;typedefstruct{ keytypekey;/*关键字*/ ……/*其它域*/}rec;typedefstruct{ recitem[maxsize+1];/*['aitəm]n.条款，项目；一则*/ intn;/*最后一个数据元素的下标*/}sqtable;2.顺序查找法intsearch_sqtable(sqtableR,keytypeK){inti; R.item[0].key=K;/*设置岗哨*/ 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