数据结构习题集

《数据结构习题集》由会员分享，可在线阅读，更多相关《数据结构习题集（54页珍藏版）》请在金锄头文库上搜索。

1、数据结构题集数据结构题集-2P14：2.6、2.7P15:2.9P17:2.11、2.191 1数据结构数据结构- -复习复习 ai-1aies-next=p-next;p-next=s;p-next-prior=s;s-prior=p;psai-1ai插入元素算法插入元素算法2.8(a)在在P所指所指向的向的结点结点后后插插入新入新结点结点2 2数据结构数据结构- -复习复习 在在 P P 所指所指向的向的结点结点前前插插入新入新结点结点插入元素算法插入元素算法2.8(b)ai-1aies-prior=p-prior;p-prior-next=s;s-next=p;p-prior=s;psa

2、i-1ai3 3数据结构数据结构- -复习复习 ai-1aiai+1p-next=p-next-next;p-next-prior=p;pai-1删除元素算法删除元素算法2.8(c)删除删除结点结点P的的后继后继元素元素4 4数据结构数据结构- -复习复习 ai-1aiai+1p-prior-next=p-next;p-next-prior=p-prior;pai-1删除元素算法删除元素算法2.8(e)删除删除结点结点P指指向的向的元素元素5 5数据结构数据结构- -复习复习 2.11StatusInsert_SqList(SqList&va,intx)/把x插入递增有序表va中if(va.l

3、ength+1va.listsize)returnERROR;va.length+;for(i=va.length-1;va.elemix&i=0;i-)va.elemi+1=va.elemi;va.elemi+1=x;returnOK;/Insert_SqList6 6数据结构数据结构- -复习复习 2.19StatusStatusDelete_Between(LinklistDelete_Between(Linklist&L,intL,int mink,intmink,int maxkmaxk) )/删除元素递增排列的链表删除元素递增排列的链表L L中值大于中值大于minkmink且小于且

4、小于maxkmaxk的所有元的所有元素素 if(L=null&minkif(L=null&minkmaxkmaxk)returnerror;)returnerror;p=L;p=L; while(pwhile(p-next-datanext;-next-datanext;/p/p是最后一个不大于是最后一个不大于minkmink的元素的元素 if(pif(p-next)/-next)/如果还有比如果还有比minkmink更大的元素更大的元素 q=p-next;q=p-next;while(qwhile(q-datadatanext;)q=q-next;/q/q是第一个不小于是第一个不小于maxk

5、maxk的元素的元素p-next=q;p-next=q;free(qfree(q); );/Delete_BetweenDelete_Between7 7数据结构数据结构- -复习复习 其它习题其它习题P16:2.102.12P18:2.212.222.242.292.338 8数据结构数据结构- -复习复习 2.10StatusStatusDeleteK(SqListDeleteK(SqList&a,inta,int i,inti,intk)/k)/删除线删除线性表性表a a中第中第i i个元素起的个元素起的k k个元素个元素 if(iif(i1|k1|ka.lengtha.length)r

6、eturn)returnINFEASIBLE;INFEASIBLE; for(countfor(count=1;i+count-1=1;i+count-1B;AB;值为值为-1,-1,表示表示AB;AB;值为值为0,0,表示表示A=BA=B for(ifor(i=1;i=1;i=A.length&iA.length&i=B.elemiB.elemi?1:-1;?1:-1; if(A.lengthif(A.length=B.lengthB.length)return0;)return0;returnreturnA.lengthA.length B.lengthB.length?1:-1;?1:-

7、1;/当两个字符表可以互相比较的部分完全相同时当两个字符表可以互相比较的部分完全相同时, ,哪个哪个较长较长, ,哪个就较大哪个就较大/ListCompListComp1010数据结构数据结构- -复习复习 2.21voidreverse(SqList&A)/顺序表就地逆置for(i=1,j=A.length;ij;i+,j-)A.elemiA.elemj;/reverse1111数据结构数据结构- -复习复习 2.22 voidvoidLinkList_reverse(LinklistLinkList_reverse(Linklist&L)/&L)/链表的就地链表的就地逆置逆置; ;为简化算

8、法为简化算法, ,假设表长大于假设表长大于2 2 p=L-p=L-next;qnext;q=p-=p-next;snext;s=q-next;=q-next;p-next=NULL;p-next=NULL; while(swhile(s-next)-next)q-next=q-next=p;pp;p=q;=q;q=q=s;ss;s=s-next;/=s-next;/把把L L的元素逐个插入新表的元素逐个插入新表表头表头 q-next=q-next=p;sp;s-next=-next=q;Lq;L-next=s;-next=s;/LinkList_reverseLinkList_reverse1

9、212数据结构数据结构- -复习复习 2.24voidvoidreverse_merge(LinkListreverse_merge(LinkList&A,LinkListA,LinkList&B,LinkListB,LinkList&C)/&C)/把把元素递增排列的链表元素递增排列的链表A A和和B B合并为合并为C,C,且且C C中元素递减排列中元素递减排列, ,使用原使用原空间空间 pa=A-pa=A-next;pbnext;pb=B-=B-next;prenext;pre=NULL;=NULL; while(pa|pbwhile(pa|pb) )if(paif(pa-datadata-

10、data|!pbdata|!pb) )pc=pc=pa;qpa;q=pa-=pa-next;panext;pa-next=-next=pre;papre;pa=q;=q;/将将A A的元素插入新表的元素插入新表 elseelsepc=pc=pb;qpb;q= =pbpb-next;pbnext;pb-next=-next=pre;pbpre;pb=q;=q;pre=pc;pre=pc;C=A;A-next=pc;/C=A;A-next=pc;/构造新表头构造新表头/reverse_mergereverse_merge1313数据结构数据结构- -复习复习 2.29voidvoidSqList_

11、Intersect_Delete(SqListSqList_Intersect_Delete(SqList&A,SqListA,SqList B,SqListB,SqListC)C) i=0;j=0;k=0;m=0;i=0;j=0;k=0;m=0;/i/i指示指示A A中元素原来的位置中元素原来的位置,m,m为移动后的位置为移动后的位置 while(iwhile(i A.length&jA.length&j B.lengthB.length&k&kC.lengthC.length) )if(B.elemjif(B.elemjC.elemkC.elemk)k+;)k+;elseelsesame=

12、same=B.elemjB.elemj; ;/找到了相同元素找到了相同元素samesamewhile(B.elemjwhile(B.elemj=same)j+;=same)j+;while(C.elemkwhile(C.elemk=same)k+;=same)k+; /j,kj,k后移到新的元素后移到新的元素while(iwhile(i A.length&A.elemiA.length&A.elemisame)same)A.elemmA.elemm+=+=A.elemiA.elemi+;+;/需保留的元素移动到新位置需保留的元素移动到新位置while(iwhile(i A.length&A.e

13、lemiA.length&A.elemi=same)i+;=same)i+;/跳过相同的元素跳过相同的元素 /while/while while(iwhile(i p=B-next;qnext;q=C-=C-next;rnext;r=A-next;=A-next; while(p&q&rwhile(p&q&r) )if(pif(p-datadata)p=p-next;-datadata)p=p-next;elseelseif(pif(p-dataq-data)q=q-next;-dataq-data)q=q-next;elseelseu=p-data;/u=p-data;/确定待删除元素确定待

14、删除元素u uwhile(rwhile(r-next-datanext;/-next-datanext;/确定最后一个小于确定最后一个小于u u的元素指针的元素指针r rif(rif(r-next-data=u)-next-data=u)s=r-next;s=r-next;while(swhile(s-data=u)-data=u)t=t=s;ss;s=s-=s-next;free(tnext;free(t);/);/确定第一个大于确定第一个大于u u的元素指针的元素指针s s/while/whiler-next=s;/r-next=s;/删除删除r r和和s s之间的元素之间的元素/if/i

15、fwhile(pwhile(p-data=u)p=p-next;-data=u)p=p-next;while(qwhile(q-data=u)q=q-next;-data=u)q=q-next;/else/else/while/while/LinkList_Intersect_DeleteLinkList_Intersect_Delete 1515数据结构数据结构- -复习复习 2.33StatusStatusLinkList_Divide(LinkListLinkList_Divide(LinkList&L,CiListL,CiList&A,CiListA,CiList&B,CiListB,

16、CiList &C&Cs=L-next;s=L-next;A=(A=(CiListCiList*)*)malloc(sizeof(CiLNode);pmalloc(sizeof(CiLNode);p=A;=A;B=(B=(CiListCiList*)*)malloc(sizeof(CiLNode);qmalloc(sizeof(CiLNode);q=B;=B;C=(C=(CiListCiList*)*)malloc(sizeof(CiLNode);rmalloc(sizeof(CiLNode);r=C;/=C;/建立头结点建立头结点 while(swhile(s) )if(isalphabet

17、(sif(isalphabet(s-data)-data)p-next=p-next=s;ps;p=s;=s;elseelseif(isdigit(sif(isdigit(s-data)-data)q-next=q-next=s;qs;q=s;=s;elseelser-next=r-next=s;rs;r=s;=s;/while/whilep-next=p-next=A;qA;q-next=-next=B;rB;r-next=C;/-next=C;/完成循环链表完成循环链表/LinkList_DivideLinkList_Divide 1616数据结构数据结构- -复习复习 数据结构题集数据结

18、构题集-3P22:3.3P23:3.93.12P24:3.16P25:3.281717数据结构数据结构- -复习复习 3.16voidvoidTrain_arrange(charTrain_arrange(char*train)/*train)/这里用字这里用字符串符串traintrain表示火车表示火车,H,H表示硬席表示硬席,S,S表示软表示软席席 p=p=train;qtrain;q=train;=train; InitStack(sInitStack(s); );while(*p)while(*p)if(*p=H)if(*p=H)push(spush(s,*p);/,*p);/把把HH

19、存入栈存入栈中中else*(q+)=*p;/else*(q+)=*p;/把把SS调到前部调到前部p+;p+; while(!StackEmpty(swhile(!StackEmpty(s)pop(s,cpop(s,c); );*(q+)=c;/*(q+)=c;/把把HH接在后部接在后部 /Train_arrangeTrain_arrange 1818数据结构数据结构- -复习复习 3.28voidInitCiQueue(CiQueue&Q)/初始化循环链表表示的队列QQ=(CiLNode*)malloc(sizeof(CiLNode);Q-next=Q;/InitCiQueue1919数据结构

20、数据结构- -复习复习 voidvoidEnCiQueue(CiQueueEnCiQueue(CiQueue&Q,intQ,intx)x)/把元素把元素x x插入循环链表表示的队列插入循环链表表示的队列Q,QQ,Q指向队尾元素指向队尾元素,Q-next,Q-next指向头结点指向头结点,Q-next-next,Q-next-next指向队头元素指向队头元素 p=(p=(CiLNodeCiLNode*)*)malloc(sizeof(CiLNodemalloc(sizeof(CiLNode););p-data=x;p-data=x;p-next=Q-next;/p-next=Q-next;/直接

21、把直接把p p加在加在Q Q的后面的后面 Q-next=p;Q-next=p;Q=p;/Q=p;/修改尾指针修改尾指针3.282020数据结构数据结构- -复习复习 StatusStatusDeCiQueue(CiQueueDeCiQueue(CiQueue&Q,intQ,intx)x)/从循环链表表示的队列从循环链表表示的队列Q Q头部删除元素头部删除元素x x if(Qif(Q=Q-next)returnINFEASIBLE;=Q-next)returnINFEASIBLE;/队列已空队列已空 p=Q-next-next;p=Q-next-next;x=p-data;x=p-data;Q-

22、next-next=p-next;Q-next-next=p-next; free(pfree(p); );returnOK;returnOK;/DeCiQueueDeCiQueue 3.282121数据结构数据结构- -复习复习 P22:3.4P23:3.10P24:3.133.153.173.193.21P26:3.303.31其它习题其它习题2222数据结构数据结构- -复习复习 typedeftypedef structstruct ElemtypeElemtype*base2;*base2;ElemtypeElemtype*top2;*top2;BDStacktypeBDStackt

23、ype;/;/双向栈类型双向栈类型 StatusStatusInit_Stack(BDStacktypeInit_Stack(BDStacktype&tws,inttws,intm)m)tws.base0=(tws.base0=(ElemtypeElemtype*)*)malloc(sizeof(Elemtypemalloc(sizeof(Elemtype); ;tws.base1=tws.base0+m;tws.base1=tws.base0+m;tws.top0=tws.base0;tws.top0=tws.base0;tws.top1=tws.base1;tws.top1=tws.bas

24、e1;returnOK;returnOK;/Init_StackInit_Stack 3.152323数据结构数据结构- -复习复习 typedeftypedef structstruct ElemtypeElemtype*base2;*base2;ElemtypeElemtype*top2;*top2;BDStacktypeBDStacktype;/;/双向栈类型双向栈类型 StatusStatuspush(BDStacktypepush(BDStacktype&tws,inttws,int i,Elemtypei,Elemtypex)x)/x/x入栈入栈,i=0,i=0表示低端栈表示低端栈

25、,i=1,i=1表示高端栈表示高端栈 if(tws.top0tws.top1)returnOVERFLOW;if(tws.top0tws.top1)returnOVERFLOW;if(iif(i=0)*tws.top0+=x;=0)*tws.top0+=x;elseelseif(iif(i=1)*tws.top1-=x;=1)*tws.top1-=x;elsereturnERROR;elsereturnERROR;returnOK;returnOK;/push/push3.152424数据结构数据结构- -复习复习 typedeftypedef structstruct ElemtypeEle

26、mtype*base2;*base2;ElemtypeElemtype*top2;*top2;BDStacktypeBDStacktype;/;/双向栈类型双向栈类型 StatusStatuspop(BDStacktypepop(BDStacktype&tws,inttws,int i,Elemtypei,Elemtype&x)&x) if(iif(i=0)=0)if(tws.top0=tws.base0)returnOVERFLOW;if(tws.top0=tws.base0)returnOVERFLOW;x=*-tws.top0;x=*-tws.top0;elseelseif(iif(i=

27、1)=1)if(tws.top1=tws.base1)returnOVERFLOW;if(tws.top1=tws.base1)returnOVERFLOW;x=*+tws.top1;x=*+tws.top1;elsereturnERROR;elsereturnERROR;returnOK;returnOK;/pop/pop3.152525数据结构数据结构- -复习复习 intint IsReverseIsReverse()() InitStack(sInitStack(s); ); while(ewhile(e= =getchargetchar()!=&)()!=&)if(eif(e=)re

28、turn0;=)return0;push(s,epush(s,e););while(e=while(e=getchargetchar()!=)()!=)if(StackEmpty(sif(StackEmpty(s)return0;)return0;pop(s,cpop(s,c); );if(eif(e!=c)return0;!=c)return0; if(!StackEmpty(sif(!StackEmpty(s)return0;)return0;return1;return1;/IsReverseIsReverse3.172626数据结构数据结构- -复习复习 StatusStatusAll

29、Brackets_Test(charAllBrackets_Test(char*strstr) )InitStack(sInitStack(s); ); for(pfor(p= =strstr;*;*p;pp;p+)+)if(*p=(|*p=|*p=)if(*p=(|*p=|*p=)push(spush(s,*p);,*p);elseif(*p=)|*p=|*p=)elseif(*p=)|*p=|*p=)if(StackEmpty(sif(StackEmpty(s)returnERROR;)returnERROR;pop(s,cpop(s,c); );if(*p=)&c!=()returnER

30、ROR;if(*p=)&c!=()returnERROR;if(*p=&c!=)returnERROR;if(*p=&c!=)returnERROR;if(*p=&c!=)returnERROR;if(*p=&c!=)returnERROR;/for/for if(!StackEmpty(sif(!StackEmpty(s)returnERROR;)returnERROR;returnOK;returnOK;/AllBrackets_TestAllBrackets_Test 3.192727数据结构数据结构- -复习复习 2828数据结构数据结构- -复习复习 voidvoidNiBoLan(

31、charNiBoLan(char*str,charstr,char*new)*new)p=p=str;qstr;q=new;=new; InitStack(sInitStack(s);/s);/s为运算符栈为运算符栈为运算符栈为运算符栈 while(*p)while(*p)if(*pif(*p是字母是字母是字母是字母)*q+=*p;/)*q+=*p;/直接输出直接输出直接输出直接输出elseelsec=c=gettop(sgettop(s););if(*pif(*p优先级比优先级比优先级比优先级比c c高高高高) )push(spush(s,*p);,*p);elseelsewhile(get

32、top(swhile(gettop(s) )优先级不比优先级不比优先级不比优先级不比* *p p低低低低) )pop(s,cpop(s,c);*(q+)=c;);*(q+)=c;/while/whilepush(spush(s,*p);,*p);/else/else/else/elsep+;p+;/while/while/NiBoLanNiBoLan3.212929数据结构数据结构- -复习复习 StatusStatusEnCyQueue(CyQueueEnCyQueue(CyQueue&Q,intQ,intx)x) if(Q.lengthif(Q.length=MAXSIZE)returnO

33、VERFLOW;=MAXSIZE)returnOVERFLOW; Q.rearQ.rear=(Q.rear+1)%MAXSIZE;=(Q.rear+1)%MAXSIZE; Q.baseQ.rearQ.baseQ.rear=x;=x; Q.lengthQ.length+;+;returnOK;returnOK;/EnCyQueueEnCyQueue 3.30StatusStatusDeCyQueue(CyQueueDeCyQueue(CyQueue&Q,intQ,int&x)&x) if(Q.lengthif(Q.length=0)returnINFEASIBLE;=0)returnINFEAS

34、IBLE;head=(Q.rear-Q.length+1)%MAXSIZE;head=(Q.rear-Q.length+1)%MAXSIZE;x=x=Q.baseheadQ.basehead; ; Q.lengthQ.length-;-;/DeCyQueueDeCyQueue3030数据结构数据结构- -复习复习 intint Palindrome_TestPalindrome_Test()() InitStack(S);InitQueue(QInitStack(S);InitQueue(Q); ); while(cwhile(c= =getchargetchar()!=)()!=)Push(

35、S,c);EnQueue(Q,cPush(S,c);EnQueue(Q,c);); while(!StackEmpty(Swhile(!StackEmpty(S)Pop(S,a);DeQueue(Q,bPop(S,a);DeQueue(Q,b););if(aif(a!=b)returnERROR;!=b)returnERROR;returnOK;returnOK;/Palindrome_TestPalindrome_Test3.313131数据结构数据结构- -复习复习 数据结构题集数据结构题集-5P31:5.1P32:5.2P35:5.215.223232数据结构数据结构- -复习复习 vo

36、idvoidTSMatrix_Add(TSMatrixTSMatrix_Add(TSMatrix A,TSMatrixA,TSMatrix B,TSMatrixB,TSMatrix&C&C C.muC.mu= =A.mu;C.nuA.mu;C.nu= =A.nu;C.tuA.nu;C.tu=0;=0;pa=1;pb=1;pc=1;pa=1;pb=1;pc=1; for(xfor(x=1;x=1;x=A.mu;xA.mu;x+)+)while(A.datapa.iwhile(A.datapa.ix)pa+;x)pa+; while(B.datapb.iwhile(B.datapb.ix) B.d

37、atapb.jB.datapb.j) ) C.datapc.iC.datapc.i=x;=x;C.datapc.jC.datapc.j= =B.datapb.jB.datapb.j; ;C.datapc.eC.datapc.e= =B.datapb.eB.datapb.e; ;pb+;pcpb+;pc+;+;elseelseC.datapc.iC.datapc.i=x;=x;C.datapc.jC.datapc.j= =A.datapa.jA.datapa.j; ;C.datapc.eC.datapc.e= =A.datapa.eA.datapa.epa+;pcpa+;pc+;+;/while

38、/while5.213333数据结构数据结构- -复习复习 while(A.datapawhile(A.datapa=x)/=x)/插入插入A A中剩余的元素中剩余的元素( (第第x x行行) )C.datapc.iC.datapc.i=x;=x;C.datapc.jC.datapc.j= =A.datapa.jA.datapa.j; ;C.datapc.eC.datapc.e= =A.datapa.eA.datapa.epa+;pcpa+;pc+;+;while(B.datapbwhile(B.datapb=x)/=x)/插入插入B B中剩余的元素中剩余的元素( (第第x x行行) )C.d

39、atapc.iC.datapc.i=x;=x;C.datapc.jC.datapc.j= =B.datapb.jB.datapb.j; ;C.datapc.eC.datapc.e= =B.datapb.eB.datapb.e; ;pb+;pcpb+;pc+;+;/for/for C.tuC.tu=pc;=pc;/TSMatrix_AddTSMatrix_Add3434数据结构数据结构- -复习复习 数据结构题集数据结构题集-6P38:6.1P38:6.1P41:6.226.236.24P41:6.226.236.246.266.276.286.266.276.28P42:6.376.386.3

40、9P42:6.376.386.393535数据结构数据结构- -复习复习 voidPreOrder_Nonrecursive(BitreeT)InitStack(S);Push(S,T);/根指针进栈1.while(!StackEmpty(S)2.while(Gettop(S,p)&p)3.visit(p-data);push(S,p-lchild);/向左走到尽头pop(S,p);1.if(!StackEmpty(S)2.pop(S,p);push(S,p-rchild);/向右一步/while/PreOrder_Nonrecursive6.373636数据结构数据结构- -复习复习 voi

41、dPostOrder_Stack(BiTreeT)PMTypea;InitStack(S);Push(S,T,0);/根结点入栈1.while(!StackEmpty(S)2.Pop(S,a);3.switch(a.mark)case0:Push(S,a,1);if(a-lchild)Push(S,a-lchild,0);break;case1:2.Push(S,a,2);3.if(a-rchild)Push(S,a-rchild,0);break;case2:visit(a);/访问结点,返回/while/PostOrder_Stack6.383737数据结构数据结构- -复习复习 void

42、PostOrder_Nonrecursive(EBitreeTp=T;while(p)switch(p-mark)case0:p-mark=1;if(p-lchild)p=p-lchild;/访问左子树break;case1:p-mark=2;if(p-rchild)p=p-rchild;/访问右子树break;case2:visit(p);p-mark=0;/恢复mark值p=p-parent;/返回双亲结点/PostOrder_Nonrecursive6.393838数据结构数据结构- -复习复习 数据结构题集数据结构题集-7P47:7.8P48:7.157.163939数据结构数据结构-

43、 -复习复习 最小生成树最小生成树-普里姆算法普里姆算法取图中任意一个顶点v作为生成树的根，之后往生成树上添加新的顶点w。在添加在添加的顶点的顶点w和已经在生成树上的顶点和已经在生成树上的顶点v之之间必定存在一条边，并且该边的权值在所间必定存在一条边，并且该边的权值在所有连通顶点有连通顶点v和和w之间的边中取值最小之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有n-1个顶点为止。4040数据结构数据结构- -复习复习 最小生成树最小生成树-克鲁斯卡尔算法克鲁斯卡尔算法先构造一个只含n个顶点的子图SG，然后从权值最小的边开始，若它的添加不使SG中产生回路，则在SG上加上这条边，如

44、此重复，直至加上n-1条边为止4141数据结构数据结构- -复习复习 constMAXNUM=20;typedefenumDG,UDGGraphKind;typedef struct ArcCell VRType adj; AdjMatrix MAXNUM MAXNUM; typedef struct VType vexsMAXNUM; AdjMatrix arcs; int vexnum, arcnum; GraphKind kind; MGraph;图的数组表示法图的数组表示法4242数据结构数据结构- -复习复习 无向图无向图4343数据结构数据结构- -复习复习 有向图有向图4444数

45、据结构数据结构- -复习复习 1.1.StatusInsert_Vex(MGraph&G,charv)2.2.if(G.vexnum+1)MAX_VERTEX_NUM)returnINFEASIBLE;3.3.G.vexs+G.vexnum=v;4.4.returnOK;/Insert_Vex4545数据结构数据结构- -复习复习 1.1.StatusStatusInsert_Arc(MGraphInsert_Arc(MGraph&G,charG,char v,charv,char w)/w)/在邻接矩阵表示的图在邻接矩阵表示的图G G上插入边上插入边( (v,wv,w) ) 2.2. if(

46、iif(i= =LocateVex(G,vLocateVex(G,v)0)returnERROR;)0)returnERROR;3.3. if(jif(j= =LocateVex(G,wLocateVex(G,w)0)returnERROR;)0)returnERROR;4.4. if(iif(i=j)returnERROR;=j)returnERROR;5.5. if(!G.arcsij.adjif(!G.arcsij.adj) )6.6.G.arcsij.adjG.arcsij.adj=1;=1;7.7.G.arcnumG.arcnum+;+;8.8.returnOK;returnOK;/

47、Insert_ArcInsert_Arc 4646数据结构数据结构- -复习复习 1.1.StatusStatusDelete_Vex(MGraphDelete_Vex(MGraph&G,charG,charv)v)2.2.n=n=G.vexnumG.vexnum; ;3.3. if(mif(m= =LocateVex(G,vLocateVex(G,v)0)returnERROR;)0)returnERROR;4.4. G.vexsmG.vexsmG.vexsnG.vexsn; ;5.5. for(ifor(i=0;i=0;in;in;i+)+)6.6.G.arcsimG.arcsim=G.a

48、rcsinG.arcsin; ;7.7.G.arcsmiG.arcsmi=G.arcsniG.arcsni; 8.8. G.arcsmm.adjG.arcsmm.adj=0;=0;9.9. G.vexnumG.vexnum-;-;10.10.returnOK;returnOK;/Delete_VexDelete_Vex4747数据结构数据结构- -复习复习 StatusStatusDelete_Arc(MGraphDelete_Arc(MGraph&G,charG,char v,charv,charw)/w)/在邻接在邻接矩阵表示的图矩阵表示的图G G上删除边上删除边( (v,wv,w) )

49、if(iif(i= =LocateVex(G,vLocateVex(G,v)0)returnERROR;)0)returnERROR; if(jif(j= =LocateVex(G,wLocateVex(G,w)0)returnERROR;)0)returnERROR; if(G.arcsij.adjif(G.arcsij.adj) )G.arcsij.adjG.arcsij.adj=0;=0;G.arcnumG.arcnum-;-;returnOK;returnOK;/Delete_ArcDelete_Arc 4848数据结构数据结构- -复习复习 1. 1. 无向图邻接表无向图邻接表对图中

50、每个顶点对图中每个顶点对图中每个顶点对图中每个顶点ViViViVi建立一个单链表建立一个单链表建立一个单链表建立一个单链表每个链表附设一个头结点每个链表附设一个头结点每个链表附设一个头结点每个链表附设一个头结点A10图的链式存储结构图的链式存储结构邻接表邻接表4949数据结构数据结构- -复习复习 DBACFEA14B045C35D25E01F123012345无向图邻接表无向图邻接表5050数据结构数据结构- -复习复习 ABECF有向图的邻接表有向图的邻接表142301201234ABCDE5151数据结构数据结构- -复习复习 constMAX_VERTEX_NUM=20;constMA

51、X_VERTEX_NUM=20;typedeftypedef structstruct ArcNodeArcNode intint adjvexadjvex; ;structstruct ArcNodeArcNode* *nextarcnextarc; ;VRTypeVRTypeweight;weight;InfoTypeInfoType*info;*info;typedefstructVNodeVertexTypedata;ArcNode*firstarc;AdjListMAX_VERTEX_NUM;typedefstructAdjListvertices;intvexnum,arcnum;

52、GraphKindkind;ALGraph;5252数据结构数据结构- -复习复习 1.1.StatusStatusInsert_Arc(ALGraphInsert_Arc(ALGraph&G,charG,char v,charv,charw)w)2.2. if(iif(i= =LocateVex(G,vLocateVex(G,v)0)returnERROR;)0)returnERROR;3.3. if(jif(j= =LocateVex(G,wLocateVex(G,w)0)returnERROR;)p-adjvexadjvex=j;p-=j;p-nextarcnextarc=NULL;=N

53、ULL;6.6. if(!G.verticesi.firstarcif(!G.verticesi.firstarc) )G.verticesi.firstarcG.verticesi.firstarc=p;=p;7.7.elseelse8.8. for(qfor(q= =G.verticesi.firstarcG.verticesi.firstarc; ;q-q-nextarcnextarc= =null;qnull;q=q-=q-nextarcnextarc) )9.9.if(qif(q-adjvexadjvex=j)returnERROR;/=j)returnERROR;/边已经存在边已经存在10.10.if(qif(q-adjvexadjvex=j)returnERROR;=j)returnERROR;11.11.elseq-elseq-nextarcnextarc=p;=p;12.12. G.arcnumG.arcnum+;+;13.13.returnOK;returnOK;/Insert_ArcInsert_Arc5353数据结构数据结构- -复习复习 ABECF有向图的邻接表有向图的邻接表142301201234ABCDEi=0,j=4i=1,j=25454数据结构数据结构- -复习复习