- 281.00 KB
- 2022-04-29 13:54:08 发布
- 1、本文档共5页，可阅读全部内容。
- 2、本文档内容版权归属内容提供方，所产生的收益全部归内容提供方所有。如果您对本文有版权争议，可选择认领，认领后既往收益都归您。
- 3、本文档由用户上传，本站不保证质量和数量令人满意，可能有诸多瑕疵，付费之前，请仔细先通过免费阅读内容等途径辨别内容交易风险。如存在严重挂羊头卖狗肉之情形，可联系本站下载客服投诉处理。
- 文档侵权举报电话：19940600175。
'第一章绪论1.16voidprint_descending(intx,inty,intz)//按从大到小顺序输出三个数{ scanf("%d,%d,%d",&x,&y,&z); if(xy;//<->为表示交换的双目运算符,以下同 if(yz; if(xy;//冒泡排序 printf("%d%d%d",x,y,z);}//print_descending1.17Statusfib(intk,intm,int&f)//求k阶斐波那契序列的第m项的值f{ inttempd; if(k<2||m<0)returnERROR; if(ma.length)returnINFEASIBLE; for(count=1;i+count-1<=a.length-k;count++)//注意循环结束的条件 a.elem[i+count-1]=a.elem[i+count+k-1]; a.length-=k; returnOK;}//DeleteK2.11StatusInsert_SqList(SqList&va,intx)//把x插入递增有序表va中{ if(va.length+1>va.listsize)returnERROR; va.length++; for(i=va.length-1;va.elem[i]>x&&i>=0;i--) va.elem[i+1]=va.elem[i]; va.elem[i+1]=x; returnOK;}//Insert_SqList2.12intListComp(SqListA,SqListB)//比较字符表A和B,并用返回值表示结果,值为1,表示A>B;值为-1,表示AB.elem[i]?1:-1; if(A.length==B.length)return0; returnA.length>B.length?1:-1; //当两个字符表可以互相比较的部分完全相同时,哪个较长,哪个就较大}//ListComp2.13LNode*Locate(LinkListL,intx)//链表上的元素查找,返回指针{ for(p=l->next;p&&p->data!=x;p=p->next); returnp;}//Locate2.14intLength(LinkListL)//求链表的长度{ for(k=0,p=L;p->next;p=p->next,k++); returnk;}//Length2.15voidListConcat(LinkListha,LinkListhb,LinkList&hc)//把链表hb接在ha后面形成链表hc{ hc=ha;p=ha; while(p->next)p=p->next; p->next=hb;}//ListConcat2.16见书后答案.2.17StatusInsert(LinkList&L,inti,intb)//在无头结点链表L的第i个元素之前插入元素
b{ p=L;q=(LinkList*)malloc(sizeof(LNode)); q.data=b; if(i==1) { q.next=p;L=q;//插入在链表头部 } else { while(--i>1)p=p->next; q->next=p->next;p->next=q;//插入在第i个元素的位置 }}//Insert2.18StatusDelete(LinkList&L,inti)//在无头结点链表L中删除第i个元素{ if(i==1)L=L->next;//删除第一个元素 else { p=L; while(--i>1)p=p->next; p->next=p->next->next;//删除第i个元素 }}//Delete2.19StatusDelete_Between(Linklist&L,intmink,intmaxk)//删除元素递增排列的链表L中值大于mink且小于maxk的所有元素{ p=L; while(p->next->data<=mink)p=p->next;//p是最后一个不大于mink的元素 if(p->next) //如果还有比mink更大的元素 { q=p->next; while(q->datanext;//q是第一个不小于maxk的元素 p->next=q; }}//Delete_Between2.20StatusDelete_Equal(Linklist&L)//删除元素递增排列的链表L中所有值相同的元素{ p=L->next;q=p->next;//p,q指向相邻两元素 while(p->next) { if(p->data!=q->data) { p=p->next;q=p->next;//当相邻两元素不相等时,p,q都向后推一步 } else { while(q->data==p->data) { free(q); q=q->next; } p->next=q;p=q;q=p->next;//当相邻元素相等时删除多余元素
}//else }//while}//Delete_Equal2.21voidreverse(SqList&A)//顺序表的就地逆置{ for(i=1,j=A.length;iA.elem[j];}//reverse2.22voidLinkList_reverse(Linklist&L)//链表的就地逆置;为简化算法,假设表长大于2{ p=L->next;q=p->next;s=q->next;p->next=NULL; while(s->next) { q->next=p;p=q; q=s;s=s->next;//把L的元素逐个插入新表表头 } q->next=p;s->next=q;L->next=s;}//LinkList_reverse分析:本算法的思想是,逐个地把L的当前元素q插入新的链表头部,p为新表表头.2.23voidmerge1(LinkList&A,LinkList&B,LinkList&C)//把链表A和B合并为C,A和B的元素间隔排列,且使用原存储空间{ p=A->next;q=B->next;C=A; while(p&&q) { s=p->next;p->next=q;//将B的元素插入 if(s) { t=q->next;q->next=s;//如A非空,将A的元素插入 } p=s;q=t; }//while}//merge12.24voidreverse_merge(LinkList&A,LinkList&B,LinkList&C)//把元素递增排列的链表A和B合并为C,且C中元素递减排列,使用原空间{ pa=A->next;pb=B->next;pre=NULL;//pa和pb分别指向A,B的当前元素 while(pa||pb) { if(pa->datadata||!pb) { pc=pa;q=pa->next;pa->next=pre;pa=q;//将A的元素插入新表 } else { pc=pb;q=pb->next;pb->next=pre;pb=q;//将B的元素插入新表 } pre=pc; } C=A;A->next=pc;//构造新表头}//reverse_merge分析:本算法的思想是,按从小到大的顺序依次把A和B的元素插入新表的头部pc处,最后处理A或B的剩余元素
.2.25voidSqList_Intersect(SqListA,SqListB,SqList&C)//求元素递增排列的线性表A和B的元素的交集并存入C中{ i=1;j=1;k=0; while(A.elem[i]&&B.elem[j]) { if(A.elem[i]B.elem[j])j++; if(A.elem[i]==B.elem[j]) { C.elem[++k]=A.elem[i];//当发现了一个在A,B中都存在的元素, i++;j++;//就添加到C中 } }//while}//SqList_Intersect2.26voidLinkList_Intersect(LinkListA,LinkListB,LinkList&C)//在链表结构上重做上题{ p=A->next;q=B->next; pc=(LNode*)malloc(sizeof(LNode));C=pc; while(p&&q) { if(p->datadata)p=p->next; elseif(p->data>q->data)q=q->next; else { s=(LNode*)malloc(sizeof(LNode)); s->data=p->data; pc->next=s;pc=s; p=p->next;q=q->next; } }//while}//LinkList_Intersect2.27voidSqList_Intersect_True(SqList&A,SqListB)//求元素递增排列的线性表A和B的元素的交集并存回A中{ i=1;j=1;k=0; while(A.elem[i]&&B.elem[j]) { if(A.elem[i]B.elem[j])j++; elseif(A.elem[i]!=A.elem[k]) { A.elem[++k]=A.elem[i];//当发现了一个在A,B中都存在的元素 i++;j++;//且C中没有,就添加到C中 } else{i++;j++;} }//while while(A.elem[k])A.elem[k++]=0;}//SqList_Intersect_True2.28voidLinkList_Intersect_True(LinkList&A,LinkListB)//在链表结构上重做上题
{ p=A->next;q=B->next;pc=A; while(p&&q) { if(p->datadata)p=p->next; elseif(p->data>q->data)q=q->next; elseif(p->data!=pc->data) { pc=pc->next; pc->data=p->data; p=p->next;q=q->next; } }//while}//LinkList_Intersect_True2.29voidSqList_Intersect_Delete(SqList&A,SqListB,SqListC){ i=0;j=0;k=0;m=0; //i指示A中元素原来的位置,m为移动后的位置 while(iC.elem[k])k++; else { same=B.elem[j]; //找到了相同元素same while(B.elem[j]==same)j++; while(C.elem[k]==same)k++; //j,k后移到新的元素 while(inext;q=C->next;r=A-next; while(p&&q&&r) { if(p->datadata)p=p->next; elseif(p->data>q->data)q=q->next; else { u=p->data;//确定待删除元素u while(r->next->datanext;//确定最后一个小于u的元素指针r if(r->next->data==u) { s=r->next; while(s->data==u) { t=s;s=s->next;free(t);//确定第一个大于u的元素指针s
}//while r->next=s;//删除r和s之间的元素 }//if while(p->data=u)p=p->next; while(q->data=u)q=q->next; }//else }//while}//LinkList_Intersect_Delete2.31StatusDelete_Pre(CiLNode*s)//删除单循环链表中结点s的直接前驱{ p=s; while(p->next->next!=s)p=p->next;//找到s的前驱的前驱p p->next=s; returnOK;}//Delete_Pre2.32StatusDuLNode_Pre(DuLinkList&L)//完成双向循环链表结点的pre域{ for(p=L;!p->next->pre;p=p->next)p->next->pre=p; returnOK;}//DuLNode_Pre2.33StatusLinkList_Divide(LinkList&L,CiList&A,CiList&B,CiList&C)//把单链表L的元素按类型分为三个循环链表.CiList为带头结点的单循环链表类型.{ s=L->next; A=(CiList*)malloc(sizeof(CiLNode));p=A; B=(CiList*)malloc(sizeof(CiLNode));q=B; C=(CiList*)malloc(sizeof(CiLNode));r=C;//建立头结点 while(s) { if(isalphabet(s->data)) { p->next=s;p=s; } elseif(isdigit(s->data)) { q->next=s;q=s; } else { r->next=s;r=s; } }//while p->next=A;q->next=B;r->next=C;//完成循环链表}//LinkList_Divide2.34voidPrint_XorLinkedList(XorLinkedListL)//从左向右输出异或链表的元素值{ p=L.left;pre=NULL; while(p) { printf("%d",p->data); q=XorP(p->LRPtr,pre); pre=p;p=q;//任何一个结点的LRPtr域值与其左结点指针进行异或运算即得到其右结点指针
}}//Print_XorLinkedList2.35StatusInsert_XorLinkedList(XorLinkedList&L,intx,inti)//在异或链表L的第i个元素前插入元素x{ p=L.left;pre=NULL; r=(XorNode*)malloc(sizeof(XorNode)); r->data=x; if(i==1)//当插入点在最左边的情况 { p->LRPtr=XorP(p.LRPtr,r); r->LRPtr=p; L.left=r; returnOK; } j=1;q=p->LRPtr;//当插入点在中间的情况 while(++jLRPtr,pre); pre=p;p=q; }//while//在p,q两结点之间插入 if(!q)returnINFEASIBLE;//i不可以超过表长 p->LRPtr=XorP(XorP(p->LRPtr,q),r); q->LRPtr=XorP(XorP(q->LRPtr,p),r); r->LRPtr=XorP(p,q);//修改指针 returnOK;}//Insert_XorLinkedList2.36StatusDelete_XorLinkedList(XorlinkedList&L,inti)//删除异或链表L的第i个元素{ p=L.left;pre=NULL; if(i==1)//删除最左结点的情况 { q=p->LRPtr; q->LRPtr=XorP(q->LRPtr,p); L.left=q;free(p); returnOK; } j=1;q=p->LRPtr; while(++jLRPtr,pre); pre=p;p=q; }//while//找到待删结点q if(!q)returnINFEASIBLE;//i不可以超过表长 if(L.right==q)//q为最右结点的情况 { p->LRPtr=XorP(p->LRPtr,q); L.right=p;free(q); returnOK; } r=XorP(q->LRPtr,p);//q为中间结点的情况,此时p,r分别为其左右结点 p->LRPtr=XorP(XorP(p->LRPtr,q),r); r->LRPtr=XorP(XorP(r->LRPtr,q),p);//修改指针
free(q); returnOK;}//Delete_XorLinkedList2.37voidOEReform(DuLinkedList&L)//按1,3,5,...4,2的顺序重排双向循环链表L中的所有结点{ p=L.next; while(p->next!=L&&p->next->next!=L) { p->next=p->next->next; p=p->next; }//此时p指向最后一个奇数结点 if(p->next==L)p->next=L->pre->pre; elsep->next=l->pre; p=p->next;//此时p指向最后一个偶数结点 while(p->pre->pre!=L) { p->next=p->pre->pre; p=p->next; } p->next=L;//按题目要求调整了next链的结构,此时pre链仍为原状 for(p=L;p->next!=L;p=p->next)p->next->pre=p; L->pre=p;//调整pre链的结构,同2.32方法}//OEReform分析:next链和pre链的调整只能分开进行.如同时进行调整的话,必须使用堆栈保存偶数结点的指针,否则将会破坏链表结构,造成结点丢失.2.38DuLNode*Locate_DuList(DuLinkedList&L,intx)//带freq域的双向循环链表上的查找{ p=L.next; while(p.data!=x&&p!=L)p=p->next; if(p==L)returnNULL;//没找到 p->freq++;q=p->pre; while(q->freq<=p->freq&&p!=L)q=q->pre;//查找插入位置 if(q!=p->pre) { p->pre->next=p->next;p->next->pre=p->pre; q->next->pre=p;p->next=q->next; q->next=p;p->pre=q;//调整位置 } returnp;}//Locate_DuList2.39floatGetValue_SqPoly(SqPolyP,intx0)//求升幂顺序存储的稀疏多项式的值{ PolyTerm*q; xp=1;q=P.data; sum=0;ex=0; while(q->coef) { while(exexp)xp*=x0; sum+=q->coef*xp; q++; } returnsum;}//GetValue_SqPoly2.40
voidSubtract_SqPoly(SqPolyP1,SqPolyP2,SqPoly&P3)//求稀疏多项式P1减P2的差式P3{ PolyTerm*p,*q,*r; Create_SqPoly(P3);//建立空多项式P3 p=P1.data;q=P2.data;r=P3.data; while(p->coef&&q->coef) { if(p->expexp) { r->coef=p->coef; r->exp=p->exp; p++;r++; } elseif(p->expexp) { r->coef=-q->coef; r->exp=q->exp; q++;r++; } else { if((p->coef-q->coef)!=0)//只有同次项相减不为零时才需要存入P3中 { r->coef=p->coef-q->coef; r->exp=p->exp;r++; }//if p++;q++; }//else }//while while(p->coef)//处理P1或P2的剩余项 { r->coef=p->coef; r->exp=p->exp; p++;r++; } while(q->coef) { r->coef=-q->coef; r->exp=q->exp; q++;r++; }}//Subtract_SqPoly2.41voidQiuDao_LinkedPoly(LinkedPoly&L)//对有头结点循环链表结构存储的稀疏多项式L求导{ p=L->next; if(!p->data.exp) { L->next=p->next;p=p->next;//跳过常数项 } while(p!=L) { p->data.coef*=p->data.exp--;//对每一项求导
p=p->next; }}//QiuDao_LinkedPoly2.42voidDivide_LinkedPoly(LinkedPoly&L,&A,&B)//把循环链表存储的稀疏多项式L拆成只含奇次项的A和只含偶次项的B{ p=L->next; A=(PolyNode*)malloc(sizeof(PolyNode)); B=(PolyNode*)malloc(sizeof(PolyNode)); pa=A;pb=B; while(p!=L) { if(p->data.exp!=2*(p->data.exp/2)) { pa->next=p;pa=p; } else { pb->next=p;pb=p; } p=p->next; }//while pa->next=A;pb->next=B;}//Divide_LinkedPoly第三章栈与队列3.15typedefstruct{ Elemtype*base[2]; Elemtype*top[2]; }BDStacktype;//双向栈类型StatusInit_Stack(BDStacktype&tws,intm)//初始化一个大小为m的双向栈tws{ tws.base[0]=(Elemtype*)malloc(sizeof(Elemtype)); tws.base[1]=tws.base[0]+m; tws.top[0]=tws.base[0]; tws.top[1]=tws.base[1]; returnOK;}//Init_StackStatuspush(BDStacktype&tws,inti,Elemtypex)//x入栈,i=0表示低端栈,i=1表示高端栈{ if(tws.top[0]>tws.top[1])returnOVERFLOW;//注意此时的栈满条件 if(i==0)*tws.top[0]++=x; elseif(i==1)*tws.top[1]--=x; elsereturnERROR; returnOK;}//pushStatuspop(BDStacktype&tws,inti,Elemtype&x)//x出栈,i=0表示低端栈,i=1表示高端栈{ if(i==0) { if(tws.top[0]==tws.base[0])returnOVERFLOW; x=*--tws.top[0]; } else
if(i==1) { if(tws.top[1]==tws.base[1])returnOVERFLOW; x=*++tws.top[1]; } elsereturnERROR; returnOK;}//pop3.16voidTrain_arrange(char*train)//这里用字符串train表示火车,"H"表示硬席,"S"表示软席{ p=train;q=train; InitStack(s); while(*p) { if(*p=="H")push(s,*p);//把"H"存入栈中 else*(q++)=*p;//把"S"调到前部 p++; } while(!StackEmpty(s)) { pop(s,c); *(q++)=c;//把"H"接在后部 }}//Train_arrange3.17intIsReverse()//判断输入的字符串中"&"前和"&"后部分是否为逆串,是则返回1,否则返回0{ InitStack(s); while((e=getchar())!="&") { if(e==’@’)return0;//不允许在’&’之前出现’@’ push(s,e); } while((e=getchar())!="@") { if(StackEmpty(s))return0; pop(s,c); if(e!=c)return0; } if(!StackEmpty(s))return0; return1;}//IsReverse3.18StatusBracket_Test(char*str)//判别表达式中小括号是否匹配{ count=0; for(p=str;*p;p++) { if(*p=="(")count++; elseif(*p==")")count--; if(count<0)returnERROR; } if(count)returnERROR;//注意括号不匹配的两种情况 returnOK;}//Bracket_Test3.19
StatusAllBrackets_Test(char*str)//判别表达式中三种括号是否匹配{ InitStack(s); for(p=str;*p;p++) { if(*p=="("||*p=="["||*p=="{")push(s,*p); elseif(*p==")"||*p=="]"||*p=="}") { if(StackEmpty(s))returnERROR; pop(s,c); if(*p==")"&&c!="(")returnERROR; if(*p=="]"&&c!="[")returnERROR; if(*p=="}"&&c!="{")returnERROR;//必须与当前栈顶括号匹配 } }//for if(!StackEmpty(s))returnERROR; returnOK;}//AllBrackets_Test3.20typedefstruct{. intx; inty; }coordinate;voidRepaint_Color(intg[m][n],inti,intj,intcolor)//把点(i,j)相邻区域的颜色置换为color{ old=g[i][j]; InitQueue(Q); EnQueue(Q,{I,j}); while(!QueueEmpty(Q)) { DeQueue(Q,a); x=a.x;y=a.y; if(x>1) if(g[x-1][y]==old) { g[x-1][y]=color; EnQueue(Q,{x-1,y});//修改左邻点的颜色 } if(y>1) if(g[x][y-1]==old) { g[x][y-1]=color; EnQueue(Q,{x,y-1});//修改上邻点的颜色 } if(x=0)s=0; elseif(m>0&&n>=0)s=n+g(m-1,2*n); elsereturnERROR; returnOK;}//g3.25StatusF_recursive(intn,int&s)//递归算法{ if(n<0)returnERROR; if(n==0)s=n+1; else { F_recurve(n/2,r); s=n*r; } returnOK;}//F_recursiveStatusF_nonrecursive(intn,ints)//非递归算法{ if(n<0)returnERROR; if(n==0)s=n+1; else { InitStack(s);//s的元素类型为struct{inta;intb;} while(n!=0) { a=n;b=n/2; push(s,{a,b}); n=b; }//while s=1; while(!StackEmpty(s)) { pop(s,t); s*=t.a; }//while } return
OK;}//F_nonrecursive3.26floatSqrt_recursive(floatA,floatp,floate)//求平方根的递归算法{ if(abs(p^2-A)<=e)returnp; elsereturnsqrt_recurve(A,(p+A/p)/2,e);}//Sqrt_recurvefloatSqrt_nonrecursive(floatA,floatp,floate)//求平方根的非递归算法{ while(abs(p^2-A)>=e) p=(p+A/p)/2; returnp;}//Sqrt_nonrecursive3.27这一题的所有算法以及栈的变化过程请参见《数据结构(pascal版)》,作者不再详细写出.3.28voidInitCiQueue(CiQueue&Q)//初始化循环链表表示的队列Q{ Q=(CiLNode*)malloc(sizeof(CiLNode)); Q->next=Q;}//InitCiQueuevoidEnCiQueue(CiQueue&Q,intx)//把元素x插入循环链表表示的队列Q,Q指向队尾元素,Q->next指向头结点,Q->next->next指向队头元素{ p=(CiLNode*)malloc(sizeof(CiLNode)); p->data=x; p->next=Q->next;//直接把p加在Q的后面 Q->next=p; Q=p; //修改尾指针}StatusDeCiQueue(CiQueue&Q,intx)//从循环链表表示的队列Q头部删除元素x{ if(Q==Q->next)returnINFEASIBLE;//队列已空 p=Q->next->next; x=p->data; Q->next->next=p->next; free(p); returnOK;}//DeCiQueue3.29StatusEnCyQueue(CyQueue&Q,intx)//带tag域的循环队列入队算法{ if(Q.front==Q.rear&&Q.tag==1)//tag域的值为0表示"空",1表示"满" returnOVERFLOW; Q.base[Q.rear]=x; Q.rear=(Q.rear+1)%MAXSIZE; if(Q.front==Q.rear)Q.tag=1;//队列满}//EnCyQueueStatusDeCyQueue(CyQueue&Q,int&x)//带tag域的循环队列出队算法{ if(Q.front==Q.rear&&Q.tag==0)returnINFEASIBLE; Q.front=(Q.front+1)%MAXSIZE; x=Q.base[Q.front]; if(Q.front==Q.rear)Q.tag=1;//队列空 return
OK;}//DeCyQueue分析:当循环队列容量较小而队列中每个元素占的空间较多时,此种表示方法可以节约较多的存储空间,较有价值.3.30StatusEnCyQueue(CyQueue&Q,intx)//带length域的循环队列入队算法{ if(Q.length==MAXSIZE)returnOVERFLOW; Q.rear=(Q.rear+1)%MAXSIZE; Q.base[Q.rear]=x; Q.length++; returnOK;}//EnCyQueueStatusDeCyQueue(CyQueue&Q,int&x)//带length域的循环队列出队算法{ if(Q.length==0)returnINFEASIBLE; head=(Q.rear-Q.length+1)%MAXSIZE;//详见书后注释 x=Q.base[head]; Q.length--;}//DeCyQueue3.31intPalindrome_Test()//判别输入的字符串是否回文序列,是则返回1,否则返回0{ InitStack(S);InitQueue(Q); while((c=getchar())!="@") { Push(S,c);EnQueue(Q,c);//同时使用栈和队列两种结构 } while(!StackEmpty(S)) { Pop(S,a);DeQueue(Q,b)); if(a!=b)returnERROR; } returnOK;}//Palindrome_Test3.32voidGetFib_CyQueue(intk,intn)//求k阶斐波那契序列的前n+1项{ InitCyQueue(Q);//其MAXSIZE设置为k for(i=0;i=avr)//根据x的值决定插入在队头还是队尾
{ Q.base[Q.rear]=x; Q.rear=(Q.rear+1)%MAXSIZE; }//插入在队尾 else { Q.front=(Q.front-1)%MAXSIZE; Q.base[Q.front]=x; }//插入在队头 returnOK;}//EnDQueueStatusDeDQueue(DQueue&Q,int&x)//输出受限的双端队列的出队操作{ if(Q.front==Q.rear)returnINFEASIBLE;//队列空 x=Q.base[Q.front]; Q.front=(Q.front+1)%MAXSIZE; returnOK;}//DeDQueue3.34voidTrain_Rearrange(char*train)//这里用字符串train表示火车,"P"表示硬座,"H"表示硬卧,"S"表示软卧,最终按PSH的顺序排列{ r=train; InitDQueue(Q); while(*r) { if(*r=="P") { printf("E"); printf("D");//实际上等于不入队列,直接输出P车厢 } elseif(*r=="S") { printf("E"); EnDQueue(Q,*r,0);//0表示把S车厢从头端入队列 } else { printf("A"); EnDQueue(Q,*r,1);//1表示把H车厢从尾端入队列 } }//while while(!DQueueEmpty(Q)) { printf("D"); DeDQueue(Q); }//while//从头端出队列的车厢必然是先S后H的顺序}//Train_Rearrange第四章串4.10voidString_Reverse(Stringtypes,Stringtype&r)//求s的逆串r{ StrAssign(r,"");//初始化r为空串
for(i=Strlen(s);i;i--) { StrAssign(c,SubString(s,i,1)); StrAssign(r,Concat(r,c));//把s的字符从后往前添加到r中 }}//String_Reverse4.11voidString_Subtract(Stringtypes,Stringtypet,Stringtype&r)//求所有包含在串s中而t中没有的字符构成的新串r{ StrAssign(r,""); for(i=1;i<=Strlen(s);i++) { StrAssign(c,SubString(s,i,1)); for(j=1;jStrlen(t))StrAssign(r,Concat(r,c)); } }//for}//String_Subtract4.12intReplace(Stringtype&S,StringtypeT,StringtypeV);//将串S中所有子串T替换为V,并返回置换次数{ for(n=0,i=1;i<=Strlen(S)-Strlen(T)+1;i++)//注意i的取值范围 if(!StrCompare(SubString(S,i,Strlen(T)),T))//找到了与T匹配的子串 {//分别把T的前面和后面部分保存为head和tail StrAssign(head,SubString(S,1,i-1)); StrAssign(tail,SubString(S,i+Strlen(T),Strlen(S)-i-Strlen(T)+1)); StrAssign(S,Concat(head,V)); StrAssign(S,Concat(S,tail));//把head,V,tail连接为新串 i+=Strlen(V);//当前指针跳到插入串以后 n++; }//if returnn;}//Replace分析:i+=Strlen(V);这一句是必需的,也是容易忽略的.如省掉这一句,则在某些情况下,会引起不希望的后果,虽然在大多数情况下没有影响.请思考:设S="place",T="ace",V="face",则省掉i+=Strlen(V);运行时会出现什么结果?4.13intDelete_SubString(Stringtype&s,Stringtypet)//从串s中删除所有与t相同的子串,并返回删除次数{ for(n=0,i=1;i<=Strlen(s)-Strlen(t)+1;i++) if(!StrCompare(SubString(s,i,Strlen(t)),t)) { StrAssign(head,SubString(S,1,i-1)); StrAssign(tail,SubString(S,i+Strlen(t),Strlen(s)-i-Strlen(t)+1)); StrAssign(S,Concat(head,tail));//把head,tail连接为新串 n++; }//if return
n,}//Delete_SubString4.14StatusNiBoLan_to_BoLan(Stringtypestr,Stringtype&new)//把前缀表达式str转换为后缀式new{ Initstack(s);//s的元素为Stringtype类型 for(i=1;i<=Strlen(str);i++) { r=SubString(str,i,1); if(r为字母)push(s,r); else { if(StackEmpty(s))returnERROR; pop(s,a); if(StackEmpty(s))returnERROR; pop(s,b); StrAssign(t,Concat(r,b)); StrAssign(c,Concat(t,a));//把算符r,子前缀表达式a,b连接为新子前缀表达式c push(s,c); } }//for pop(s,new); if(!StackEmpty(s))returnERROR; returnOK;}//NiBoLan_to_BoLan分析:基本思想见书后注释3.23.请读者用此程序取代作者早些时候对3.23题给出的程序.4.15voidStrAssign(Stringtype&T,charchars&#;)//用字符数组chars给串T赋值,Stringtype的定义见课本{ for(i=0,T[0]=0;chars[i];T[0]++,i++)T[i+1]=chars[i];}//StrAssign4.16charStrCompare(Stringtypes,Stringtypet)//串的比较,s>t时返回正数,s=t时返回0,ss[0]&&i>t[0])return0; elseif(i>s[0])return-t[i]; elseif(i>t[0])returns[i]; elsereturns[i]-t[i];}//StrCompare4.17intString_Replace(Stringtype&S,StringtypeT,StringtypeV);//将串S中所有子串T替换为V,并返回置换次数{ for(n=0,i=1;i<=S[0]-T[0]+1;i++) { for(j=i,k=1;T[k]&&S[j]==T[k];j++,k++); if(k>T[0])//找到了与T匹配的子串:分三种情况处理 { if(T[0]==V[0]) for(l=1;l<=T[0];l++)//新子串长度与原子串相同时:直接替换 S[i+l-1]=V[l]; elseif(T[0]=i+T[0];l--) S[l+V[0]-T[0]]=S[l]; for(l=1;l<=V[0];l++) S[i+l-1]=V[l]; } else//新子串长度小于原子串时:先将后部左移 { for(l=i+V[0];l<=S[0]+V[0]-T[0];l++) S[l]=S[l-V[0]+T[0]]; for(l=1;l<=V[0];l++) S[i+l-1]=V[l]; } S[0]=S[0]-T[0]+V[0]; i+=V[0];n++; }//if }//for returnn;}//String_Replace4.18typedefstruct{ charch; intnum; }mytype;voidStrAnalyze(StringtypeS)//统计串S中字符的种类和个数{ mytypeT[MAXSIZE];//用结构数组T存储统计结果 for(i=1;i<=S[0];i++) { c=S[i];j=0; while(T[j].ch&&T[j].ch!=c)j++;//查找当前字符c是否已记录过 if(T[j].ch)T[j].num++; elseT[j]={c,1}; }//for for(j=0;T[j].ch;j++) printf("%c: %dn",T[j].ch,T[j].num);}//StrAnalyze4.19voidSubtract_String(Stringtypes,Stringtypet,Stringtype&r)//求所有包含在串s中而t中没有的字符构成的新串r{ r[0]=0; for(i=1;i<=s[0];i++) { c=s[i]; for(j=1;jt[0])r[++r[0]]=c; } }//for}//Subtract_String4.20intSubString_Delete(Stringtype&s,Stringtypet)//从串s中删除所有与t相同的子串,并返回删除次数
{ for(n=0,i=1;i<=s[0]-t[0]+1;i++) { for(j=1;j<=t[0]&&s[i+j-1]==t[i];j++); if(j>m)//找到了与t匹配的子串 { for(k=i;k<=s[0]-t[0];k++)s[k]=s[k+t[0]];//左移删除 s[0]-=t[0];n++; } }//for returnn;}//Delete_SubString4.21typedefstruct{ charch; LStrNode*next; }LStrNode,*LString;//链串结构voidStringAssign(LString&s,LStringt)//把串t赋值给串s{ s=malloc(sizeof(LStrNode)); for(q=s,p=t->next;p;p=p->next) { r=(LStrNode*)malloc(sizeof(LStrNode)); r->ch=p->ch; q->next=r;q=r; } q->next=NULL;}//StringAssignvoidStringCopy(LString&s,LStringt)//把串t复制为串s.与前一个程序的区别在于,串s业已存在.{ for(p=s->next,q=t->next;p&&q;p=p->next,q=q->next) { p->ch=q->ch;pre=p; } while(q) { p=(LStrNode*)malloc(sizeof(LStrNode)); p->ch=q->ch; pre->next=p;pre=p; } p->next=NULL;}//StringCopycharStringCompare(LStrings,LStringt)//串的比较,s>t时返回正数,s=t时返回0,snext,q=t->next;p&&q&&p->ch==q->ch;p=p->next,q=q->next); if(!p&&!q)return0; elseif(!p)return-(q->ch); elseif(!q)returnp->ch; elsereturnp->ch-q->ch;}//StringCompareintStringLen(LStrings)//求串s的长度(元素个数){ for(i=0,p=s->next;p;p=p->next,i++); returni;}//StringLen
LString*Concat(LStrings,LStringt)//连接串s和串t形成新串,并返回指针{ p=malloc(sizeof(LStrNode)); for(q=p,r=s->next;r;r=r->next) { q->next=(LStrNode*)malloc(sizeof(LStrNode)); q=q->next; q->ch=r->ch; }//for//复制串s for(r=t->next;r;r=r->next) { q->next=(LStrNode*)malloc(sizeof(LStrNode)); q=q->next; q->ch=r->ch; }//for//复制串t q->next=NULL; returnp;}//ConcatLString*Sub_String(LStrings,intstart,intlen)//返回一个串,其值等于串s从start位置起长为len的子串{ p=malloc(sizeof(LStrNode));q=p; for(r=s;start;start--,r=r->next);//找到start所对应的结点指针r for(i=1;i<=len;i++,r=r->next) { q->next=(LStrNode*)malloc(sizeof(LStrNode)); q=q->next; q->ch=r->ch; }//复制串t q->next=NULL; returnp;}//Sub_String4.22voidLString_Concat(LString&t,LString&s,charc)//用块链存储结构,把串s插入到串t的字符c之后{ p=t.head; while(p&&!(i=Find_Char(p,c)))p=p->next;//查找字符c if(!p)//没找到 { t.tail->next=s.head; t.tail=s.tail;//把s连接在t的后面 } else { q=p->next; r=(Chunk*)malloc(sizeof(Chunk));//将包含字符c的节点p分裂为两个 for(j=0;jch[j]="#";//原结点p包含c及其以前的部分 for(j=i;jch[j]=p->ch[j]; p->ch[j]="#";//p的后半部分和r的前半部分的字符改为无效字符"#" } p->next=s.head;
s.tail->next=r; r->next=q;//把串s插入到结点p和r之间 }//else t.curlen+=s.curlen;//修改串长 s.curlen=0;}//LString_ConcatintFind_Char(Chunk*p,charc)//在某个块中查找字符c,如找到则返回位置是第几个字符,如没找到则返回0{ for(i=0;ich[i]!=c;i++); if(i==CHUNKSIZE)return0; elsereturni+1;}//Find_Char4.23intLString_Palindrome(LStringL)//判断以块链结构存储的串L是否为回文序列,是则返回1,否则返回0{ InitStack(S); p=S.head;i=0;k=1;//i指示元素在块中的下标,k指示元素在整个序列中的序号(从1开始) for(k=1;k<=S.curlen;k++) { if(k<=S.curlen/2)Push(S,p->ch[i]);//将前半段的字符入串 elseif(k>(S.curlen+1)/2) { Pop(S,c);//将后半段的字符与栈中的元素相匹配 if(p->ch[i]!=c)return0;//失配 } if(++i==CHUNKSIZE)//转到下一个元素,当为块中最后一个元素时,转到下一块 { p=p->next; i=0; } }//for return1;//成功匹配}//LString_Palindrome4.24voidHString_Concat(HStrings1,HStrings2,HString&t)//将堆结构表示的串s1和s2连接为新串t{ if(t.ch)free(t.ch); t.ch=malloc((s1.length+s2.length)*sizeof(char)); for(i=1;i<=s1.length;i++)t.ch[i-1]=s1.ch[i-1]; for(j=1;j<=s2.length;j++,i++)t.ch[i-1]=s2.ch[j-1]; t.length=s1.length+s2.length;}//HString_Concat4.25intHString_Replace(HString&S,HStringT,HStringV)//堆结构串上的置换操作,返回置换次数{ for(n=0,i=0;i<=S.length-T.length;i++) { for(j=i,k=0;k=i+T.length;l--) S.ch[l+V.length-T.length]=S.ch[l]; for(l=0;lS.length)pos=S.length+1;//当插入位置大于串长时,看作添加在串尾 S.ch=realloc(S.ch,(S.length+T.length)*sizeof(char)); for(i=S.length-1;i>=pos-1;i--) S.ch[i+T.length]=S.ch[i];//后移为插入字符串让出位置 for(i=0;it[0])returni-t[0];}//Index_New4.28voidLGet_next(LString&T)//链串上的get_next算法
{ p=T->succ;p->next=T;q=T; while(p->succ) { if(q==T||p->data==q->data) { p=p->succ;q=q->succ; p->next=q; } elseq=q->next; }//while}//LGet_next4.29LStrNode*LIndex_KMP(LStringS,LStringT,LStrNode*pos)//链串上的KMP匹配算法,返回值为匹配的子串首指针{ p=pos;q=T->succ; while(p&&q) { if(q==T||p->chdata==q->chdata) { p=p->succ; q=q->succ; } elseq=q->next; }//while if(!q) { for(i=1;i<=Strlen(T);i++) p=p->next; returnp; }//发现匹配后,要往回找子串的头 returnNULL;}//LIndex_KMP4.30voidGet_LRepSub(StringtypeS)//求S的最长重复子串的位置和长度{ for(maxlen=0,i=1;imaxlen)//发现了比以前发现的更长的重复子串 { lrs1=j-k+1;lrs2=mrs1+i;maxlen=k;//作记录 } }//for }//for if(maxlen) { printf("LongestRepeatingSubstringlength:%dn",maxlen); printf("Position1:%d Position2:%dn",lrs1,lrs2); } elseprintf("NoRepeatingSubstringfound!n");}//Get_LRepSub
分析:i代表"错位值".本算法的思想是,依次把串S的一个副本S2向右错位平移1格,2格,3格,...与自身S1相匹配,如果存在最长重复子串,则必然能在此过程中被发现.用变量lrs1,lrs2,maxlen来记录已发现的最长重复子串第一次出现位置,第二次出现位置和长度.题目中未说明"重复子串"是否允许有重叠部分,本算法假定允许.如不允许,只需在第二个for语句的循环条件中加上k<=i即可.本算法时间复杂度为O(Strlen(S)^2).4.31voidGet_LPubSub(StringtypeS,StringtypeT)//求串S和串T的最长公共子串位置和长度{ if(S[0]>=T[0]) { StrAssign(A,S);StrAssign(B,T); } else { StrAssign(A,T);StrAssign(B,S); }//为简化设计,令S和T中较长的那个为A,较短的那个为B for(maxlen=0,i=1-B[0];iA[0]-B[0]) { jmin=i;jmax=A[0]; }//B有一部分在A右端的右边 else { jmin=i;jmax=i+B[0]; }//B在A左右两端之间. //以上是根据A和B不同的相对位置确定A上需要匹配的区间(与B重合的区间)的端点:jmin,jmax. for(k=0,j=jmin;j<=jmax;j++) { if(A[j]==B[j-i])k++; elsek=0; if(k>maxlen) { lps1=j-k+1;lps2=j-i-k+1;maxlen=k; } }//for }//for if(maxlen) { if(S[0]>=T[0]) { lpsS=lps1;lpsT=lps2; } else { lpsS=lps2;lpsT=lps1; }//将A,B上的位置映射回S,T上的位置 printf("LongestPublicSubstringlength:%dn",maxlen); printf("PositioninS:%d PositioninT:%dn",lpsS,lpsT); }//if elseprintf("NoRepeatingSubstring
found!n");}//Get_LPubSub分析:本题基本思路与上题同.唯一的区别是,由于A,B互不相同,因此B不仅要向右错位,而且还要向左错位,以保证不漏掉一些情况.当B相对于A的位置不同时,需要匹配的区间的计算公式也各不相同,请读者自己画图以帮助理解.本算法的时间复杂度是o（strlrn（s）*strlen（t））。第五章数组和广义表5.18voidRSh(intA[n],intk)//把数组A的元素循环右移k位,只用一个辅助存储空间{ for(i=1;i<=k;i++) if(n%i==0&&k%i==0)p=i;//求n和k的最大公约数p for(i=0;iA[6],A[6]->A[12],A[12]->A[3],A[3]->A[9],A[9]->A[0].第二条链:A[1]->A[7],A[7]->A[13],A[13]->A[4],A[4]->A[10],A[10]->A[1].第三条链:A[2]->A[8],A[8]->A[14],A[14]->A[5],A[5]->A[11],A[11]->A[2].恰好使所有元素都右移一次.虽然未经数学证明,但作者相信上述规律应该是正确的.5.19voidGet_Saddle(intA[m][n])//求矩阵A中的马鞍点{ for(i=0;i=0;i--)//按降幂次序,可能出现的最高项次数为mn Get_All(a,m,i,0);//确定并输出所有次数为i的项}//Print_Poly_DescendvoidGet_All(int*a,intm,inti,intseq)//递归求出所有和为i的m个自然数{ if(seq==maxm)Print_Nomial(a,exps);//已经求完时,输出该项 else { min=i-(m-1)*n;//当前数不能小于min if(min<0)min=0; max=n0)printf("+");//系数为正时打印加号 elseif(coef<0)printf("-");//系数为负时打印减号 if(abs(coef)!=1)printf("%d",abs(coef));//当系数的绝对值不为1时打印系数 for(i=0;i1)printf("%d",exp[i]);//系数为1时无需打印 }}//Print_Nomial分析:本算法的关键在于如何按照降幂顺序输出各项.这里采用了一个递归函数来找到所有满足和为i的m个自然数作为各变元的指数.只要先取第一个数为j,然后再找到所有满足和为i-j的m-1个自然数就行了.要注意j的取值范围必须使剩余m-1个自然数能够找到,所以不能小于i-(m-1)*maxn,也不能大于i.只要找到了一组符合条件的数,就可以在存储多项式系数的数组中确定对应的项的系数的位置,并且在系数不为0时输出对应的项.5.21voidTSMatrix_Add(TSMatrixA,TSMatrixB,TSMatrix&C)//三元组表示的稀疏矩阵加法{ C.mu=A.mu;C.nu=A.nu;C.tu=0; pa=1;pb=1;pc=1; for(x=1;x<=A.mu;x++)//对矩阵的每一行进行加法 { while(A.data[pa].iB.data[pb].j) { C.data[pc].i=x;
C.data[pc].j=B.data[pb].j; C.data[pc].e=B.data[pb].e; pb++;pc++; } else { C.data[pc].i=x; C.data[pc].j=A.data[pa].j; C.data[pc].e=A.data[pa].e pa++;pc++; } }//while while(A.data[pa]==x)//插入A中剩余的元素(第x行) { C.data[pc].i=x; C.data[pc].j=A.data[pa].j; C.data[pc].e=A.data[pa].e pa++;pc++; } while(B.data[pb]==x)//插入B中剩余的元素(第x行) { C.data[pc].i=x; C.data[pc].j=B.data[pb].j; C.data[pc].e=B.data[pb].e; pb++;pc++; } }//for C.tu=pc;}//TSMatrix_Add5.22voidTSMatrix_Addto(TSMatrix&A,TSMatrixB)//将三元组矩阵B加到A上{ for(i=1;i<=A.tu;i++) A.data[MAXSIZE-A.tu+i]=A.data[i];/把A的所有元素都移到尾部以腾出位置 pa=MAXSIZE-A.tu+1;pb=1;pc=1; for(x=1;x<=A.mu;x++)//对矩阵的每一行进行加法 { while(A.data[pa].iB.data[pb].j) { A.data[pc].i=x; A.data[pc].j=B.data[pb].j; A.data[pc].e=B.data[pb].e; pb++;pc++; } else { A.data[pc].i=x; A.data[pc].j=A.data[pa].j; A.data[pc].e=A.data[pa].e pa++;pc++; } }//while while(A.data[pa]==x)//插入A中剩余的元素(第x行) { A.data[pc].i=x; A.data[pc].j=A.data[pa].j; A.data[pc].e=A.data[pa].e pa++;pc++; } while(B.data[pb]==x)//插入B中剩余的元素(第x行) { A.data[pc].i=x; A.data[pc].j=B.data[pb].j; A.data[pc].e=B.data[pb].e; pb++;pc++; } }//for A.tu=pc; for(i=A.tu;iright)//逐次遍历每一个行链表 printf("%d%d%dn",i,p->j,p->e; }}//Print_OLMatrix5.27voidOLMatrix_Add(OLMatrix&A,OLMatrixB)//把十字链表表示的矩阵B加到A上{ for(j=1;j<=A.nu;j++)cp[j]=A.chead[j];//向量cp存储每一列当前最后一个元素的指针 for(i=1;i<=A.mu;i++) { pa=A.rhead[i];pb=B.rhead[i];pre=NULL;
while(pb) { if(pa==NULL||pa->j>pb->j)//新插入一个结点 { p=(OLNode*)malloc(sizeof(OLNode)); if(!pre)A.rhead[i]=p; elsepre->right=p; p->right=pa;pre=p; p->i=i;p->j=pb->j;p->e=pb->e;//插入行链表中 if(!A.chead[p->j]) { A.chead[p->j]=p; p->down=NULL; } else { while(cp[p->j]->down)cp[p->j]=cp[p->j]->down; p->down=cp[p->j]->down; cp[p->j]->down=p; } cp[p->j]=p;//插入列链表中 }//if elseif(pa->jj) { pre=pa; pa=pa->right; }//pa右移一步 elseif(pa->e+pb->e) { pa->e+=pb->e; pre=pa;pa=pa->right; pb=pb->right; }//直接相加 else { if(!pre)A.rhead[i]=pa->right; elsepre->right=pa->right; p=pa;pa=pa->right;//从行链表中删除 if(A.chead[p->j]==p) A.chead[p->j]=cp[p->j]=p->down; elsecp[p->j]->down=p->down;//从列链表中删除 free(p); }//else
}//while }//for}//OLMatrix_Add分析:本题的具体思想在课本中有详细的解释说明.5.28voidMPList_PianDao(MPList&L)//对广义表存储结构的多元多项式求第一变元的偏导{ for(p=L->hp->tp;p&&p->exp;pre=p,p=p->tp) { if(p->tag)Mul(p->hp,p->exp); elsep->coef*=p->exp;//把指数乘在本结点或其下属结点上 p->exp--; } pre->tp=NULL; if(p)free(p);//删除可能存在的常数项}//MPList_PianDaovoidMul(MPList&L,intx)//递归算法,对多元多项式L乘以x{ for(p=L;p;p=p->tp) { if(!p->tag)p->coef*=x; elseMul(p->hp,x); }}//Mul 5.29voidMPList_Add(MPListA,MPListB,MPList&C)//广义表存储结构的多项式相加的递归算法{ C=(MPLNode*)malloc(sizeof(MPLNode)); if(!A->tag&&!B->tag)//原子项,可直接相加 { C->coef=A->coef+B->coef; if(!C->coef) { free(C); C=NULL; } }//if elseif(A->tag&&B->tag)//两个多项式相加 { p=A;q=B;pre=NULL; while(p&&q) { if(p->exp==q->exp)
{ C=(MPLNode*)malloc(sizeof(MPLNode)); C->exp=p->exp; MPList_Add(A->hp,B->hp,C->hp); pre->tp=C;pre=C; p=p->tp;q=q->tp; } elseif(p->exp>q->exp) { C=(MPLNode*)malloc(sizeof(MPLNode)); C->exp=p->exp; C->hp=A->hp; pre->tp=C;pre=C; p=p->tp; } else { C=(MPLNode*)malloc(sizeof(MPLNode)); C->exp=q->exp; C->hp=B->hp; pre->tp=C;pre=C; q=q->tp; } }//while while(p) { C=(MPLNode*)malloc(sizeof(MPLNode)); C->exp=p->exp; C->hp=p->hp; pre->tp=C;pre=C; p=p->tp; } while(q) { C=(MPLNode*)malloc(sizeof(MPLNode)); C->exp=q->exp; C->hp=q->hp; pre->tp=C;pre=C; q=q->tp; }//将其同次项分别相加得到新的多项式,原理见第二章多项式相加一题 }//elseif elseif(A->tag&&!B->tag)//多项式和常数项相加 { x=B->coef;
for(p=A;p->tp->tp;p=p->tp); if(p->tp->exp==0)p->tp->coef+=x;//当多项式中含有常数项时,加上常数项 if(!p->tp->coef) { free(p->tp); p->tp=NULL; } else { q=(MPLNode*)malloc(sizeof(MPLNode)); q->coef=x;q->exp=0; q->tag=0;q->tp=NULL; p->tp=q; }//否则新建常数项,下同 }//elseif else { x=A->coef; for(p=B;p->tp->tp;p=p->tp); if(p->tp->exp==0)p->tp->coef+=x; if(!p->tp->coef) { free(p->tp); p->tp=NULL; } else { q=(MPLNode*)malloc(sizeof(MPLNode)); q->coef=x;q->exp=0; q->tag=0;q->tp=NULL; p->tp=q; } }//else}//MPList_Add5.30intGList_Getdeph(GListL)//求广义表深度的递归算法{ if(!L->tag)return0;//原子深度为0 elseif(!L)return1;//空表深度为1 m=GList_Getdeph(L->ptr.hp)+1; n=GList_Getdeph(L->ptr.tp); returnm>n?m:n;}//GList_Getdeph5.31voidGList_Copy(GListA,GList&B)//复制广义表的递归算法
{ if(!A->tag)//当结点为原子时,直接复制 { B->tag=0; B->atom=A->atom; } else//当结点为子表时 { B->tag=1; if(A->ptr.hp) { B->ptr.hp=malloc(sizeof(GLNode)); GList_Copy(A->ptr.hp,B->ptr.hp); }//复制表头 if(A->ptr.tp) { B->ptr.tp=malloc(sizeof(GLNode)); GList_Copy(A->ptr.tp,B->ptr.tp); }//复制表尾 }//else}//GList_Copy5.32intGList_Equal(GListA,GListB)//判断广义表A和B是否相等,是则返回1,否则返回0{//广义表相等可分三种情况: if(!A&&!B)return1;//空表是相等的 if(!A->tag&&!B->tag&&A->atom==B->atom)return1;//原子的值相等 if(A->tag&&B->tag) if(GList_Equal(A->ptr.hp,B->ptr.hp)&&GList_Equal(A->ptr.tp,B->ptr.tp)) return1;//表头表尾都相等 return0;}//GList_Equal5.33voidGList_PrintElem(GListA,intlayer)//递归输出广义表的原子及其所在层次,layer表示当前层次{ if(!A)return; if(!A->tag)printf("%d%dn",A->atom,layer); else { GList_PrintElem(A->ptr.hp,layer+1); GList_PrintElem(A->ptr.tp,layer);//注意尾表与原表是同一层次 }}//GList_PrintElem5.34
voidGList_Reverse(GListA)//递归逆转广义表A{ GLNode*ptr[MAX_SIZE]; if(A->tag&&A->ptr.tp)//当A不为原子且表尾非空时才需逆转 { for(i=0,p=A;p;p=p->ptr.tp,i++) { if(p->ptr.hp)GList_Reverse(p->ptr.hp); //逆转各子表 ptr[i]=p->ptr.hp; } for(p=A;p;p=p->ptr.tp) //重新按逆序排列各子表的顺序 p->ptr.hp=ptr[--i]; }}//GList_Reverse5.35StatusCreate_GList(GList&L)//根据输入创建广义表L,并返回指针{ scanf("%c",&ch); if(ch=="") { L=NULL; scanf("%c",&ch); if(ch!=")")returnERROR; returnOK; } L=(GList)malloc(sizeof(GLNode)); L->tag=1; if(isalphabet(ch))//输入是字母 { p=(GList)malloc(sizeof(GLNode));//建原子型表头 p->tag=0;p->atom=ch; L->ptr.hp=p; } elseif(ch=="(")Create_GList(L->ptr.hp);//建子表型表头 elsereturnERROR; scanf("%c",&ch); if(ch==")")L->ptr.tp=NULL; elseif(ch==",")Create_GList(L->ptr.tp);//建表尾 elsereturnERROR; returnOK;}//Create_GList分析:本题思路见书后解答.5.36voidGList_PrintList(GListA)//按标准形式输出广义表
{ if(!A)printf("()");//空表 elseif(!A->tag)printf("%d",A->atom);//原子 else { printf("("); for(p=A;p;p=p->ptr.tp) { GList_PrintList(p->ptr.hp); if(p->ptr.tp)printf(","); //只有当表尾非空时才需要打印逗号 } printf(")"); }//else}//GList_PrintList5.37voidGList_DelElem(GList&A,intx)//从广义表A中删除所有值为x的原子{ if(A&&A->ptr.hp) { if(A->ptr.hp->tag)GList_DelElem(A->ptr.hp,x); elseif(!A->ptr.hp->tag&&A->ptr.hp->atom==x) { q=A; A=A->ptr.tp; //删去元素值为x的表头 free(q); GList_DelElem(A,x); } } if(A&&A->ptr.tp)GList_DelElem(A->ptr.tp,x);}//GList_DelElem5.39voidGList_PrintElem_LOrder(GListA)//按层序输出广义表A中的所有元素{ InitQueue(Q); for(p=L;p;p=p->ptr.tp)EnQueue(Q,p); while(!QueueEmpty(Q)) { DeQueue(Q,r); if(!r->tag)printf("%d",r->atom); else for(r=r->ptr.hp;r;r=r->ptr.tp)EnQueue(Q,r); }//while}//GList_PrintElem_LOrder分析:层序遍历的问题,一般都是借助队列来完成的,
每次从队头取出一个元素的同时把它下一层的孩子插入队尾.这是层序遍历的基本思想.第六章树和二叉树6.33intIs_Descendant_C(intu,intv)//在孩子存储结构上判断u是否v的子孙,是则返回1,否则返回0{ if(u==v)return1; else { if(L[v]) if(Is_Descendant(u,L[v]))return1; if(R[v]) if(Is_Descendant(u,R[v]))return1;//这是个递归算法 } return0;}//Is_Descendant_C6.34intIs_Descendant_P(intu,intv)//在双亲存储结构上判断u是否v的子孙,是则返回1,否则返回0{ for(p=u;p!=v&&p;p=T[p]); if(p==v)return1; elsereturn0;}//Is_Descendant_P6.35这一题根本不需要写什么算法,见书后注释:两个整数的值是相等的.6.36intBitree_Sim(BitreeB1,BitreeB2)//判断两棵树是否相似的递归算法{ if(!B1&&!B2)return1; elseif(B1&&B2&&Bitree_Sim(B1->lchild,B2->lchild)&&Bitree_Sim(B1->rchild,B2->rchild)) return1; elsereturn0;}//Bitree_Sim6.37voidPreOrder_Nonrecursive(BitreeT)//先序遍历二叉树的非递归算法{ InitStack(S); Push(S,T);//根指针进栈 while(!StackEmpty(S)) { while(Gettop(S,p)&&p) { visit(p->data); push(S,p->lchild); }//向左走到尽头 pop(S,p); if(!StackEmpty(S)) { pop(S,p); push(S,p->rchild);//向右一步
} }//while}//PreOrder_Nonrecursive6.38typedefstruct{ BTNode*ptr; enum{0,1,2}mark; }PMType;//有mark域的结点指针类型voidPostOrder_Stack(BiTreeT)//后续遍历二叉树的非递归算法,用栈{ PMTypea; InitStack(S);//S的元素为PMType类型 Push(S,{T,0});//根结点入栈 while(!StackEmpty(S)) { Pop(S,a); switch(a.mark) { case0: Push(S,{a.ptr,1});//修改mark域 if(a.ptr->lchild)Push(S,{a.ptr->lchild,0});//访问左子树 break; case1: Push(S,{a.ptr,2});//修改mark域 if(a.ptr->rchild)Push(S,{a.ptr->rchild,0});//访问右子树 break; case2: visit(a.ptr);//访问结点,返回 } }//while}//PostOrder_Stack分析:为了区分两次过栈的不同处理方式,在堆栈中增加一个mark域,mark=0表示刚刚访问此结点,mark=1表示左子树处理结束返回,mark=2表示右子树处理结束返回.每次根据栈顶元素的mark域值决定做何种动作.6.39typedefstruct{ intdata; EBTNode*lchild; EBTNode*rchild; EBTNode*parent; enum{0,1,2}mark; }EBTNode,EBitree;//有mark域和双亲指针域的二叉树结点类型voidPostOrder_Nonrecursive(EBitreeT)//后序遍历二叉树的非递归算法,不用栈{ p=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_Nonrecursive分析:本题思路与上一题完全相同,只不过结点的mark值是储存在结点中的,而不是暂存在堆栈中,所以访问完毕后要将mark域恢复为0,以备下一次遍历.6.40typedefstruct{ intdata; PBTNode*lchild; PBTNode*rchild; PBTNode*parent; }PBTNode,PBitree;//有双亲指针域的二叉树结点类型voidInorder_Nonrecursive(PBitreeT)//不设栈非递归遍历有双亲指针的二叉树{ p=T; while(p->lchild)p=p->lchild;//向左走到尽头 while(p) { visit(p); if(p->rchild)//寻找中序后继:当有右子树时 { p=p->rchild; while(p->lchild)p=p->lchild;//后继就是在右子树中向左走到尽头 } elseif(p->parent->lchild==p)p=p->parent;//当自己是双亲的左孩子时后继就是双亲 else { p=p->parent; while(p->parent&&p->parent->rchild==p)p=p->parent; p=p->parent; }//当自己是双亲的右孩子时后继就是向上返回直到遇到自己是在其左子树中的祖先 }//while}//Inorder_Nonrecursive6.41intc,k;//这里把k和计数器c作为全局变量处理voidGet_PreSeq(BitreeT)//求先序序列为k的结点的值{ if(T) { c++;//每访问一个子树的根都会使前序序号计数器加1 if(c==k) { printf("Valueis%dn",T->data); exit(1); } else { Get_PreSeq(T->lchild);//在左子树中查找 Get_PreSeq(T->rchild);//在右子树中查找 } }//if}//Get_PreSeq
main(){ ... scanf("%d",&k); c=0;//在主函数中调用前,要给计数器赋初值0 Get_PreSeq(T,k); ...}//main6.42intLeafCount_BiTree(BitreeT)//求二叉树中叶子结点的数目{ if(!T)return0;//空树没有叶子 elseif(!T->lchild&&!T->rchild)return1;//叶子结点 elsereturnLeaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子树的叶子数加上右子树的叶子数}//LeafCount_BiTree6.43voidBitree_Revolute(BitreeT)//交换所有结点的左右子树{ T->lchild<->T->rchild;//交换左右子树 if(T->lchild)Bitree_Revolute(T->lchild); if(T->rchild)Bitree_Revolute(T->rchild);//左右子树再分别交换各自的左右子树}//Bitree_Revolute6.44intGet_Sub_Depth(BitreeT,intx)//求二叉树中以值为x的结点为根的子树深度{ if(T->data==x) { printf("%dn",Get_Depth(T));//找到了值为x的结点,求其深度 exit1; } else { if(T->lchild)Get_Sub_Depth(T->lchild,x); if(T->rchild)Get_Sub_Depth(T->rchild,x);//在左右子树中继续寻找 }}//Get_Sub_DepthintGet_Depth(BitreeT)//求子树深度的递归算法{ if(!T)return0; else { m=Get_Depth(T->lchild); n=Get_Depth(T->rchild); return(m>n?m:n)+1; }}//Get_Depth6.45voidDel_Sub_x(BitreeT,intx)//删除所有以元素x为根的子树{ if(T->data==x)Del_Sub(T);//删除该子树 else { if(T->lchild)Del_Sub_x(T->lchild,x); if(T->rchild)Del_Sub_x(T->rchild,x);//在左右子树中继续查找
}//else}//Del_Sub_xvoidDel_Sub(BitreeT)//删除子树T{ if(T->lchild)Del_Sub(T->lchild); if(T->rchild)Del_Sub(T->rchild); free(T);}//Del_Sub6.46voidBitree_Copy_Nonrecursive(BitreeT,Bitree&U)//非递归复制二叉树{ InitStack(S1);InitStack(S2); push(S1,T);//根指针进栈 U=(BTNode*)malloc(sizeof(BTNode)); U->data=T->data; q=U;push(S2,U); while(!StackEmpty(S)) { while(Gettop(S1,p)&&p) { q->lchild=(BTNode*)malloc(sizeof(BTNode)); q=q->lchild;q->data=p->data; push(S1,p->lchild); push(S2,q); }//向左走到尽头 pop(S1,p); pop(S2,q); if(!StackEmpty(S1)) { pop(S1,p);pop(S2,q); q->rchild=(BTNode*)malloc(sizeof(BTNode)); q=q->rchild;q->data=p->data; push(S1,p->rchild);//向右一步 push(S2,q); } }//while}//BiTree_Copy_Nonrecursive分析:本题的算法系从6.37改写而来.6.47voidLayerOrder(BitreeT)//层序遍历二叉树{ InitQueue(Q);//建立工作队列 EnQueue(Q,T); while(!QueueEmpty(Q)) { DeQueue(Q,p); visit(p); if(p->lchild)EnQueue(Q,p->lchild); if(p->rchild)EnQueue(Q,p->rchild); }}//LayerOrder6.48intfound=FALSE;Bitree*Find_Near_Ancient(BitreeT,Bitreep,Bitreeq)//求二叉树T中结点p和q的最近共同祖先
{ Bitreepathp[100],pathq[100]//设立两个辅助数组暂存从根到p,q的路径 Findpath(T,p,pathp,0); found=FALSE; Findpath(T,q,pathq,0);//求从根到p,q的路径放在pathp和pathq中 for(i=0;pathp[i]==pathq[i]&&pathp[i];i++);//查找两条路径上最后一个相同结点 returnpathp[--i];}//Find_Near_AncientvoidFindpath(BitreeT,Bitreep,Bitreepath[],inti)//求从T到p路径的递归算法{ if(T==p) { found=TRUE; return;//找到 } path[i]=T;//当前结点存入路径 if(T->lchild)Findpath(T->lchild,p,path,i+1);//在左子树中继续寻找 if(T->rchild&&!found)Findpath(T->rchild,p,path,i+1);//在右子树中继续寻找 if(!found)path[i]=NULL;//回溯}//Findpath6.49intIsFull_Bitree(BitreeT)//判断二叉树是否完全二叉树,是则返回1,否则返回0{ InitQueue(Q); flag=0; EnQueue(Q,T);//建立工作队列 while(!QueueEmpty(Q)) { DeQueue(Q,p); if(!p)flag=1; elseif(flag)return0; else { EnQueue(Q,p->lchild); EnQueue(Q,p->rchild);//不管孩子是否为空,都入队列 } }//while return1;}//IsFull_Bitree分析:该问题可以通过层序遍历的方法来解决.与6.47相比,作了一个修改,不管当前结点是否有左右孩子,都入队列.这样当树为完全二叉树时,遍历时得到是一个连续的不包含空指针的序列.反之,则序列中会含有空指针.6.50StatusCreateBitree_Triplet(Bitree&T)//输入三元组建立二叉树{ if(getchar()!="^")returnERROR; T=(BTNode*)malloc(sizeof(BTNode)); p=T;p->data=getchar(); getchar();//滤去多余字符 InitQueue(Q); EnQueue(Q,T); while((parent=getchar())!="^"&&(child=getchar())&&(side=getchar())) { while(QueueHead(Q)!=parent&&!QueueEmpty(Q))DeQueue(Q,e); if(QueueEmpty(Q))returnERROR;//未按层序输入
p=QueueHead(Q); q=(BTNode*)malloc(sizeof(BTNode)); if(side=="L")p->lchild=q; elseif(side=="R")p->rchild=q; elsereturnERROR;//格式不正确 q->data=child; EnQueue(Q,q); } returnOK;}//CreateBitree_Triplet6.51StatusPrint_Expression(BitreeT)//按标准形式输出以二叉树存储的表达式{ if(T->data是字母)printf("%c",T->data); elseif(T->data是操作符) { if(!T->lchild||!T->rchild)returnERROR;//格式错误 if(T->lchild->data是操作符&&T->lchild->data优先级低于T->data) { printf("("); if(!Print_Expression(T->lchild))returnERROR; printf(")"); }//注意在什么情况下要加括号 elseif(!Print_Expression(T->lchild))returnERROR; if(T->rchild->data是操作符&&T->rchild->data优先级低于T->data) { printf("("); if(!Print_Expression(T->rchild))returnERROR; printf(")"); } elseif(!Print_Expression(T->rchild))returnERROR; } elsereturnERROR;//非法字符 returnOK;}//Print_Expression6.52typedefstruct{ BTNodenode; intlayer; }BTNRecord;//包含结点所在层次的记录类型intFanMao(BitreeT)//求一棵二叉树的"繁茂度"{ intcountd;//count数组存放每一层的结点数 InitQueue(Q);//Q的元素为BTNRecord类型 EnQueue(Q,{T,0}); while(!QueueEmpty(Q)) { DeQueue(Q,r); count[r.layer]++; if(r.node->lchild)EnQueue(Q,{r.node->lchild,r.layer+1}); if(r.node->rchild)EnQueue(Q,{r.node->rchild,r.layer+1}); }//利用层序遍历来统计各层的结点数 h=r.layer;//最后一个队列元素所在层就是树的高度 for(maxn=count[0],i=1;count[i];i++) if(count[i]>maxn)maxn=count[i];//求层最大结点数 return
h*maxn;}//FanMao分析:如果不允许使用辅助数组,就必须在遍历的同时求出层最大结点数,形式上会复杂一些,你能写出来吗?6.53intmaxh;StatusPrintpath_MaxdepthS1(BitreeT)//求深度等于树高度减一的最靠左的结点{ Bitreepathd; maxh=Get_Depth(T);//Get_Depth函数见6.44 if(maxh<2)returnERROR;//无符合条件结点 Find_h(T,1); returnOK;}//Printpath_MaxdepthS1voidFind_h(BitreeT,inth)//寻找深度为maxh-1的结点{ path[h]=T; if(h==maxh-1) { for(i=1;path[i];i++)printf("%c",path[i]->data); exit;//打印输出路径 } else { if(T->lchild)Find_h(T->lchild,h+1); if(T->rchild)Find_h(T->rchild,h+1); } path[h]=NULL;//回溯}//Find_h6.54StatusCreateBitree_SqList(Bitree&T,SqListsa)//根据顺序存储结构建立二叉链表{ Bitreeptr[sa.last+1];//该数组储存与sa中各结点对应的树指针 if(!sa.last) { T=NULL;//空树 return; } ptr[1]=(BTNode*)malloc(sizeof(BTNode)); ptr[1]->data=sa.elem[1];//建立树根 T=ptr[1]; for(i=2;i<=sa.last;i++) { if(!sa.elem[i])returnERROR;//顺序错误 ptr[i]=(BTNode*)malloc(sizeof(BTNode)); ptr[i]->data=sa.elem[i]; j=i/2;//找到结点i的双亲j if(i-j*2)ptr[j]->rchild=ptr[i];//i是j的右孩子 elseptr[j]->lchild=ptr[i];//i是j的左孩子 } returnOK;}//CreateBitree_SqList6.55intDescNum(BitreeT)//求树结点T的子孙总数填入DescNum域中,并返回该数{ if(!T)return
-1; elsed=(DescNum(T->lchild)+DescNum(T->rchild)+2);//计算公式 T->DescNum=d; returnd;}//DescNum分析:该算法时间复杂度为O(n),n为树结点总数.注意:为了能用一个统一的公式计算子孙数目,所以当T为空指针时,要返回-1而不是0.6.56BTNode*PreOrder_Next(BTNode*p)//在先序后继线索二叉树中查找结点p的先序后继,并返回指针{ if(p->lchild)returnp->lchild; elsereturnp->rchild;}//PreOrder_Next分析:总觉得不会这么简单.是不是哪儿理解错了?6.57BitreePostOrder_Next(Bitreep)//在后序后继线索二叉树中查找结点p的后序后继,并返回指针{ if(p->rtag)returnp->rchild;//p有后继线索 elseif(!p->parent)returnNULL;//p是根结点 elseif(p==p->parent->rchild)returnp->parent;//p是右孩子 elseif(p==p->parent->lchild&&p->parent->rtag) returnp->parent;//p是左孩子且双亲没有右孩子 else//p是左孩子且双亲有右孩子 { q=p->parent->rchild; while(q->lchild||!q->rtag) { if(q->lchild)q=q->lchild; elseq=q->rchild; }//从p的双亲的右孩子向下走到底 returnq; }//else}//PostOrder_Next6.58StatusInsert_BiThrTree(BiThrTree&T,BiThrTree&p,BiThrTree&x)//在中序线索二叉树T的结点p下插入子树x{ if(p->ltag)//x作为p的左子树 { s=p->lchild;//s为p的前驱 p->ltag=Link; p->lchild=x; q=x; while(q->lchild&&!q->ltag)q=q->lchild; q->lchild=s;//找到子树中的最左结点,并修改其前驱指向s x->rtag=Thread; x->rchild=p;//x的后继指向p } elseif(p->rtag)//x作为p的右子树 { s=p->rchild;//s为p的后继 p->rtag=Link; p->rchild=x;
q=x; while(q->lchild&&!q->ltag)q=q->lchild; q->lchild=p;//找到子树中的最左结点,并修改其前驱指向p x->rtag=Thread; x->rchild=s;//x的后继指向p的后继 } else//x作为p的左子树,p的左子树作为x的右子树 { s=p->lchild;t=s; while(t->lchild&&!t->ltag)t=t->lchild; u=t->lchild;//找到p的左子树的最左节点t和前驱u p->lchild=x; x->rtag=Link; x->rchild=s;//x作为p的左子树,p的左子树s作为x的右子树 t->lchild=x; q=x; while(q->lchild&&!q->ltag)q=q->lchild; q->lchild=u;//找到子树中的最左结点,并修改其前驱指向u } returnOK;}//Insert_BiThrTree6.59voidPrint_CSTree(CSTreeT)//输出孩子兄弟链表表示的树T的各边{ for(child=T->firstchild;child;child=child->nextsib) { printf("(%c,%c),",T->data,child->data); Print_CSTree(child); }}//Print_CSTree6.60intLeafCount_CSTree(CSTreeT)//求孩子兄弟链表表示的树T的叶子数目{ if(!T->firstchild)return1;//叶子结点 else { count=0; for(child=T->firstchild;child;child=child->nextsib) count+=LeafCount_CSTree(child); returncount;//各子树的叶子数之和 }}//LeafCount_CSTree6.61intGetDegree_CSTree(CSTreeT)//求孩子兄弟链表表示的树T的度{ if(!T->firstchild)return0;//空树 else { degree=0; for(p=T->firstchild;p;p=p->nextsib)degree++;//本结点的度 for(p=T->firstchild;p;p=p->nextsib) { d=GetDegree_CSTree(p); if(d>degree)degree=d;//孩子结点的度的最大值 } return
degree; }//else}//GetDegree_CSTree6.62intGetDepth_CSTree(CSTreeT)//求孩子兄弟链表表示的树T的深度{ if(!T)return0;//空树 else { for(maxd=0,p=T->firstchild;p;p=p->nextsib) if((d=GetDepth_CSTree(p))>maxd)maxd=d;//子树的最大深度 returnmaxd+1; }}//GetDepth_CSTree6.63intGetDepth_CTree(CTreeA)//求孩子链表表示的树A的深度{ returnSubDepth(A.r);}//GetDepth_CTreeintSubDepth(intT)//求子树T的深度{ if(!A.nodes[T].firstchild)return1; for(sd=1,p=A.nodes[T].firstchild;p;p=p->next) if((d=SubDepth(p->child))>sd)sd=d; returnsd+1;}//SubDepth6.64intGetDepth_PTree(PTreeT)//求双亲表表示的树T的深度{ maxdep=0; for(i=0;i=0;j=T.nodes[j].parent)dep++;//求每一个结点的深度 if(dep>maxdep)maxdep=dep; } returnmaxdep;}//GetDepth_PTree6.65charPred,Ind;//假设前序序列和中序序列已经分别储存在数组Pre和In中BitreeBuild_Sub(intPre_Start,intPre_End,intIn_Start,intIn_End)//由子树的前序和中序序列建立其二叉链表{ sroot=(BTNode*)malloc(sizeof(BTNode));//建根 sroot->data=Pre[Pre_Start]; for(i=In_Start;In[i]!=sroot->data;i++);//在中序序列中查找子树根 leftlen=i-In_Start; rightlen=In_End-i;//计算左右子树的大小 if(leftlen) { lroot=Build_Sub(Pre_Start+1,Pre_Start+leftlen,In_Start,In_Start+leftlen-1); sroot->lchild=lroot; }//建左子树,注意参数表的计算 if(rightlen) { rroot=Build_Sub(Pre_End-rightlen+1,Pre_End,In_End-rightlen+1,In_End);
sroot->rchild=rroot; }//建右子树,注意参数表的计算 returnsroot;//返回子树根}//Build_Submain(){ ... Build_Sub(1,n,1,n);//初始调用参数,n为树结点总数 ...}分析:本算法利用了这样一个性质,即一棵子树在前序和中序序列中所占的位置总是连续的.因此,就可以用起始下标和终止下标来确定一棵子树.Pre_Start,Pre_End,In_Start和In_End分别指示子树在前序子序列里的起始下标,终止下标,和在中序子序列里的起始和终止下标.6.66typedefstruct{ CSNode*ptr; CSNode*lastchild; }NodeMsg;//结点的指针和其最后一个孩子的指针StatusBuild_CSTree_PTree(PTreeT)//由树T的双亲表构造其孩子兄弟链表{ NodeMsgTree[MAXSIZE]; for(i=0;idata=T.node[i].data;//建结点 if(T.nodes[i].parent>=0)//不是树根 { j=T.nodes[i].parent;//本算法要求双亲表必须是按层序存储 if(!(Tree[j].lastchild))//双亲当前还没有孩子 Tree[j].ptr->firstchild=Tree[i].ptr;//成为双亲的第一个孩子 else//双亲已经有了孩子 Tree[j].lastchild->nextsib=Tree[i].ptr;//成为双亲最后一个孩子的下一个兄弟 Tree[j].lastchild=Tree[i].ptr;//成为双亲的最后一个孩子 }//if }//for}//Build_CSTree_PTree6.67typedefstruct{ chardata; CSNode*ptr; CSNode*lastchild; }NodeInfo;//结点数据,结点指针和最后一个孩子的指针StatusCreateCSTree_Duplet(CSTree&T)//输入二元组建立树的孩子兄弟链表{ NodeInfoTreed; n=1;k=0; if(getchar()!="^")returnERROR;//未按格式输入 if((c=getchar())=="^")T=NULL;//空树 Tree[0].ptr=(CSNode*)malloc(sizeof(CSNode)); Tree[0].data=c; Tree[0].ptr->data=c; while((p=getchar())!="^"&&(c=getchar())!="^") { Tree[n].ptr=(CSNode*)malloc(sizeof(CSNode)); Tree[n].data=c;
Tree[n].ptr->data=c; for(k=0;Tree[k].data!=p;k++);//查找当前边的双亲结点 if(Tree[k].data!=p)returnERROR;//未找到:未按层序输入 r=Tree[k].ptr; if(!r->firstchild) r->firstchild=Tree[n].ptr; elseTree[k].lastchild->nextsib=Tree[n].ptr; Tree[k].lastchild=Tree[n].ptr;//这一段含义同上一题 n++; }//while returnOK;}//CreateCSTree_Duplet6.68StatusCreateCSTree_Degree(charnode[],intdegree[])//由结点的层序序列和各结点的度构造树的孩子兄弟链表{ CSNode*ptr[MAXSIZE];//树结点指针的辅助存储 ptr[0]=(CSNode*)malloc(sizeof(CSNode)); i=0;k=1;//i为当前结点序号,k为当前孩子的序号 while(node[i]) { ptr[i]->data=node[i]; d=degree[i]; if(d) { ptr[k]=(CSNode*)malloc(sizeof(CSNode));//k为当前孩子的序号 ptr[i]->firstchild=ptr[k];//建立i与第一个孩子k之间的联系 for(j=2;j<=d;j++) { ptr[k]=(CSNode*)malloc(sizeof(CSNode)); ptr[k-1]->nextsib=ptr[k];//当结点的度大于1时,为其孩子建立兄弟链表 k++; }//for ptr[k-1]->nextsib=NULL; }//if i++; }//while}//CreateCSTree_Degree6.69voidPrint_BiTree(BiTreeT,inti)//按树状打印输出二叉树的元素,i表示结点所在层次,初次调用时i=0{ if(T->rchild)Print_BiTree(T->rchild,i+1); for(j=1;j<=i;j++)printf("");//打印i个空格以表示出层次 printf("%cn",T->data);//打印T元素,换行 if(T->lchild)Print_BiTree(T->rchild,i+1);}//Print_BiTree分析:该递归算法实际上是带层次信息的中序遍历,只不过按照题目要求,顺序为先右后左.6.70StatusCreateBiTree_GList(BiTree&T)//由广义表形式的输入建立二叉链表{ c=getchar(); if(c=="#")T=NULL;//空子树 else {
T=(CSNode*)malloc(sizeof(CSNode)); T->data=c; if(getchar()!="(")returnERROR; if(!CreateBiTree_GList(pl))returnERROR; T->lchild=pl; if(getchar()!=",")returnERROR; if(!CreateBiTree_GList(pr))returnERROR; T->rchild=pr; if(getchar()!=")")returnERROR;//这些语句是为了保证输入符合A(B,C)的格式 } returnOK;}//CreateBiTree_GList6.71voidPrint_CSTree(CSTreeT,inti)//按凹入表形式打印输出树的元素,i表示结点所在层次,初次调用时i=0{ for(j=1;j<=i;j++)printf("");//留出i个空格以表现出层次 printf("%cn",T->data);//打印元素,换行 for(p=T->firstchild;p;p=p->nextsib) Print_CSTree(p,i+1);//打印子树}//Print_CSTree6.72voidPrint_CTree(inte,inti)//按凹入表形式打印输出树的元素,i表示结点所在层次{ for(j=1;j<=i;j++)printf("");//留出i个空格以表现出层次 printf("%cn",T.nodes[e].data);//打印元素,换行 for(p=T.nodes[e].firstchild;p;p=p->next) Print_CSTree(p->child,i+1);//打印子树}//Print_CSTreemain(){ ... Print_CTree(T.r,0);//初次调用时i=0 ...}//main6.73charc;//全局变量,指示当前字符StatusCreateCSTree_GList(CSTree&T)//由广义表形式的输入建立孩子兄弟链表{ c=getchar(); T=(CSNode*)malloc(sizeof(CSNode)); T->data=c; if((c=getchar())=="(")//非叶结点 { if(!CreateCSTree_GList(fc))returnERROR;//建第一个孩子 T->firstchild=fc; for(p=fc;c==",";p->nextsib=nc,p=nc)//建兄弟链 if(!CreateCSTree_GList(nc))returnERROR; p->nextsib=NULL; if((c=getchar())!=")")returnERROR;//括号不配对 } elseT->firtchild=NULL;//叶子结点 returnOK;}//CreateBiTree_GList分析:书后给出了两个间接递归的算法,事实上合成一个算法在形式上可能更好一些.本算法另一个改进之处在于加入了广义表格式是否合法的判断
.6.74voidPrintGlist_CSTree(CSTreeT)//按广义表形式输出孩子兄弟链表表示的树{ printf("%c",T->data); if(T->firstchild)//非叶结点 { printf("("); for(p=T->firstchild;p;p=p->nextsib) { PrintGlist_CSTree(p); if(p->nextsib)printf(",");//最后一个孩子后面不需要加逗号 } printf(")"); }//if}//PrintGlist_CSTree6.75charc;intpos=0;//pos是全局变量,指示已经分配到了哪个结点StatusCreateCTree_GList(CTree&T,int&i)//由广义表形式的输入建立孩子链表{ c=getchar(); T.nodes[pos].data=c; i=pos++;//i是局部变量,指示当前正在处理的子树根 if((c=getchar())=="(")//非叶结点 { CreateCTree_GList(); p=(CTBox*)malloc(sizeof(CTBox)); T.nodes[i].firstchild=p; p->child=pos;//建立孩子链的头 for(;c==",";p=p->next)//建立孩子链 { CreateCTree_GList(T,j);//用j返回分配得到的子树根位置 p->child=j; p->next=(CTBox*)malloc(sizeof(CTBox)); } p->next=NULL; if((c=getchar())!=")")returnERROR;//括号不配对 }//if elseT.nodes[i].firtchild=NULL;//叶子结点 returnOK;}//CreateBiTree_GList分析:该算法中,pos变量起着"分配"结点在表中的位置的作用,是按先序序列从上向下分配,因此树根T.r一定等于0,而最终的pos值就是结点数T.n.6.76voidPrintGList_CTree(CTreeT,inti)//按广义表形式输出孩子链表表示的树{ printf("%c",T.nodes[i].data); if(T.nodes[i].firstchild)//非叶结点 { printf("("); for(p=T->firstchild;p;p=p->nextsib) { PrintGlist_CSTree(T,p->child); if(p->nextsib)printf(",");//最后一个孩子后面不需要加逗号
} printf(")"); }//if}//PrintGlist_CTree第七章图7.14StatusBuild_AdjList(ALGraph&G)//输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表{ InitALGraph(G); scanf("%d",&v); if(v<0)returnERROR;//顶点数不能为负 G.vexnum=v; scanf("%d",&a); if(a<0)returnERROR;//边数不能为负 G.arcnum=a; for(m=0;mnextarc;q=q->nextarc); q->nextarc=p; } p->adjvex=j;p->nextarc=NULL; }//while returnOK;}//Build_AdjList7.15//本题中的图G均为有向无权图,其余情况容易由此写出StatusInsert_Vex(MGraph&G,charv)//在邻接矩阵表示的图G上插入顶点v{ if(G.vexnum+1)>MAX_VERTEX_NUMreturnINFEASIBLE; G.vexs[++G.vexnum]=v; returnOK;}//Insert_VexStatusInsert_Arc(MGraph&G,charv,charw)//在邻接矩阵表示的图G上插入边(v,w){ if((i=LocateVex(G,v))<0)returnERROR; if((j=LocateVex(G,w))<0)returnERROR; if(i==j)returnERROR; if(!G.arcs[i][j].adj) { G.arcs[i][j].adj=1; G.arcnum++; } returnOK;}//Insert_ArcStatusDelete_Vex(MGraph&G,charv)//在邻接矩阵表示的图G上删除顶点
v{ n=G.vexnum; if((m=LocateVex(G,v))<0)returnERROR; G.vexs[m]<->G.vexs[n];//将待删除顶点交换到最后一个顶点 for(i=0;iadjvex=j;p->nextarc=NULL; if(!G.vertices[i].firstarc)G.vertices[i].firstarc=p; else { for(q=G.vertices[i].firstarc;q->q->nextarc;q=q->nextarc) if(q->adjvex==j)returnERROR;//边已经存在 q->nextarc=p; } G.arcnum++; returnOK;}//Insert_Arc7.17//为节省篇幅,本题只给出较为复杂的Delete_Vex算法.其余算法请自行写出.StatusDelete_Vex(OLGraph&G,charv)//在十字链表表示的图G上删除顶点v{ if((m=LocateVex(G,v))<0)returnERROR; n=G.vexnum; for(i=0;itailvex==m)//如果待删除的边是头链上的第一个结点 { q=G.xlist[i].firstin; G.xlist[i].firstin=q->hlink;
free(q);G.arcnum--; } else//否则 { for(p=G.xlist[i].firstin;p&&p->hlink->tailvex!=m;p=p->hlink); if(p) { q=p->hlink; p->hlink=q->hlink; free(q);G.arcnum--; } }//else }//for for(i=0;iheadvex==m)//如果待删除的边是尾链上的第一个结点 { q=G.xlist[i].firstout; G.xlist[i].firstout=q->tlink; free(q);G.arcnum--; } else//否则 { for(p=G.xlist[i].firstout;p&&p->tlink->headvex!=m;p=p->tlink); if(p) { q=p->tlink; p->tlink=q->tlink; free(q);G.arcnum--; } }//else }//for for(i=m;ihlink) p->headvex--; for(p=G.xlist[i].firstout;p;p=p->tlink) p->tailvex--;//修改各链中的顶点序号 } G.vexnum--; returnOK;}//Delete_Vex7.18//为节省篇幅,本题只给出Delete_Arc算法.其余算法请自行写出.StatusDelete_Arc(AMLGraph&G,charv,charw)////在邻接多重表表示的图G上删除边(v,w){ if((i=LocateVex(G,v))<0)returnERROR; if((j=LocateVex(G,w))<0)returnERROR; if(G.adjmulist[i].firstedge->jvex==j) G.adjmulist[i].firstedge=G.adjmulist[i].firstedge->ilink; else { for(p=G.adjmulist[i].firstedge;p&&p->ilink->jvex!=j;p=p->ilink); if(!p)returnERROR;//未找到 p->ilink=p->ilink->ilink; }//在i链表中删除该边
if(G.adjmulist[j].firstedge->ivex==i) G.adjmulist[j].firstedge=G.adjmulist[j].firstedge->jlink; else { for(p=G.adjmulist[j].firstedge;p&&p->jlink->ivex!=i;p=p->jlink); if(!p)returnERROR;//未找到 q=p->jlink; p->jlink=q->jlink; free(q); }//在i链表中删除该边 G.arcnum--; returnOK;}//Delete_Arc7.19StatusBuild_AdjMulist(AMLGraph&G)//输入有向图的顶点数,边数,顶点信息和边的信息建立邻接多重表{ InitAMLGraph(G); scanf("%d",&v); if(v<0)returnERROR;//顶点数不能为负 G.vexnum=v; scanf(%d",&a); if(a<0)returnERROR;//边数不能为负 G.arcnum=a; for(m=0;mivex=i;p->jvex=j; p->ilink=NULL;p->jlink=NULL;//边结点赋初值 if(!G.adjmulist[i].firstedge)G.adjmulist[i].firstedge=p; else { q=G.adjmulist[i].firstedge; while(q) { r=q; if(q->ivex==i)q=q->ilink; elseq=q->jlink; } if(r->ivex==i)r->ilink=p;//注意i值既可能出现在边结点的ivex域中, elser->jlink=p;//又可能出现在边结点的jvex域中 }//else//插入i链表尾部 if(!G.adjmulist[j].firstedge)G.adjmulist[j].firstedge=p; else { q=G.adjmulist[i].firstedge; while(q) { r=q; if(q->jvex==j)q=q->jlink; else
q=q->ilnk; } if(r->jvex==j)r->jlink=p; elser->ilink=p; }//else//插入j链表尾部 }//for returnOK;}//Build_AdjList7.20intPass_MGraph(MGraphG)//判断一个邻接矩阵存储的有向图是不是可传递的,是则返回1,否则返回0{ for(x=0;xnextarc) { y=p->adjvex; for(q=G.vertices[y].firstarc;q;q=q->nextarc) { z=q->adjvex; if(z!=x&&!is_adj(G,x,z))return0; }//for }//for}//Pass_ALGraphintis_adj(ALGraphG,intm,intn)//判断有向图G中是否存在边(m,n),是则返回1,否则返回0{ for(p=G.vertices[m].firstarc;p;p=p->nextarc) if(p->adjvex==n)return1; return0;}//is_adj7.22intvisited[MAXSIZE];//指示顶点是否在当前路径上intexist_path_DFS(ALGraphG,inti,intj)//深度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0{ if(i==j)return1;//i就是j else { visited[i]=1; for(p=G.vertices[i].firstarc;p;p=p->nextarc) { k=p->adjvex; if(!visited[k]&&exist_path(k,j))return1;//i下游的顶点到j有路径
}//for }//else}//exist_path_DFS7.23intexist_path_BFS(ALGraphG,inti,intj)//广度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0{ intvisited[MAXSIZE]; InitQueue(Q); EnQueue(Q,i); while(!QueueEmpty(Q)) { DeQueue(Q,u); visited[u]=1; for(p=G.vertices[i].firstarc;p;p=p->nextarc) { k=p->adjvex; if(k==j)return1; if(!visited[k])EnQueue(Q,k); }//for }//while return0;}//exist_path_BFS7.24voidSTraverse_Nonrecursive(GraphG)//非递归遍历强连通图G{ intvisited[MAXSIZE]; InitStack(S); Push(S,GetVex(S,1));//将第一个顶点入栈 visit(1); visited=1; while(!StackEmpty(S)) { while(Gettop(S,i)&&i) { j=FirstAdjVex(G,i); if(j&&!visited[j]) { visit(j); visited[j]=1; Push(S,j);//向左走到尽头 } }//while if(!StackEmpty(S)) { Pop(S,j); Gettop(S,i); k=NextAdjVex(G,i,j);//向右走一步 if(k&&!visited[k]) { visit(k); visited[k]=1; Push(S,k); } }//if }//while}//Straverse_Nonrecursive
分析:本算法的基本思想与二叉树的先序遍历非递归算法相同,请参考6.37.由于是强连通图,所以从第一个结点出发一定能够访问到所有结点.7.25见书后解答.7.26StatusTopoNo(ALGraphG)//按照题目要求顺序重排有向图中的顶点{ intnew[MAXSIZE],indegree[MAXSIZE];//储存结点的新序号 n=G.vexnum; FindInDegree(G,indegree); InitStack(S); for(i=1;inextarc) { k=p->adjvex; if(!(--indegree[k]))Push(S,k); }//for }//while if(count0) { visited[i]=1; for(p=G.vertices[i].firstarc;p;p=p->nextarc) { l=p->adjvex; if(!visited[l]) if(exist_path_len(G,l,j,k-1))return1;//剩余路径长度减一 }//for visited[i]=0;//本题允许曾经被访问过的结点出现在另一条路径中 }//else return0;//没找到}//exist_path_len7.28intpath[MAXSIZE],visited[MAXSIZE];//暂存遍历过程中的路径intFind_All_Path(ALGraphG,intu,intv,intk)//求有向图G中顶点u到v之间的所有简单路径,k表示当前路径长度{ path[k]=u;//加入当前路径中
visited[u]=1; if(u==v)//找到了一条简单路径 { printf("Foundonepath!n"); for(i=0;path[i];i++)printf("%d",path[i]);//打印输出 } else for(p=G.vertices[u].firstarc;p;p=p->nextarc) { l=p->adjvex; if(!visited[l])Find_All_Path(G,l,v,k+1);//继续寻找 } visited[u]=0; path[k]=0;//回溯}//Find_All_Pathmain(){ ... Find_All_Path(G,u,v,0);//在主函数中初次调用,k值应为0 ...}//main7.29intGetPathNum_Len(ALGraphG,inti,intj,intlen)//求邻接表方式存储的有向图G的顶点i到j之间长度为len的简单路径条数{ if(i==j&&len==0)return1;//找到了一条路径,且长度符合要求 elseif(len>0) { sum=0;//sum表示通过本结点的路径数 visited[i]=1; for(p=G.vertices[i].firstarc;p;p=p->nextarc) { l=p->adjvex; if(!visited[l]) sum+=GetPathNum_Len(G,l,j,len-1)//剩余路径长度减一 }//for visited[i]=0;//本题允许曾经被访问过的结点出现在另一条路径中 }//else returnsum;}//GetPathNum_Len7.30intvisited[MAXSIZE];intpath[MAXSIZE];//暂存当前路径intcycles[MAXSIZE][MAXSIZE];//储存发现的回路所包含的结点intthiscycle[MAXSIZE];//储存当前发现的一个回路intcycount=0;//已发现的回路个数voidGetAllCycle(ALGraphG)//求有向图中所有的简单回路{ for(v=0;vnextarc) { w=p->adjvex; if(!visited[w])DFS(G,w,k+1); else//发现了一条回路 { for(i=0;path[i]!=w;i++);//找到回路的起点 for(j=0;path[i+j];i++)thiscycle[j]=path[i+j];//把回路复制下来 if(!exist_cycle())cycles[cycount++]=thiscycle;//如果该回路尚未被记录过,就添加到记录中 for(i=0;i=0;i--)//第二次逆向的深度优先遍历 { v=finished(i); if(!visited[v]) { printf("n");//不同的强连通分量在不同的行输出 DFS2(G,v); } }//for}//Get_SGraphvoidDFS1(OLGraphG,intv)//第一次深度优先遍历的算法{ visited[v]=1; for(p=G.xlist[v].firstout;p;p=p->tlink) { w=p->headvex; if(!visited[w])DFS1(G,w); }//for finished[++count]=v;//在第一次遍历中建立finished数组}//DFS1voidDFS2(OLGraphG,intv)//第二次逆向的深度优先遍历的算法{ visited[v]=1; printf("%d",v);//在第二次遍历中输出结点序号 for(p=G.xlist[v].firstin;p;p=p->hlink) { w=p->tailvex; if(!visited[w])DFS2(G,w); }//for}//DFS2分析:求有向图的强连通分量的算法的时间复杂度和深度优先遍历相同,也为O(n+e).7.32voidForest_Prim(ALGraphG,intk,CSTree&T)//从顶点k出发,构造邻接表结构的有向图G的最小生成森林T,用孩子兄弟链表存储{ for(j=0;jnextarc) if(p->adjvex==k)closedge[j].lowcost=p->cost; }//if closedge[k].lowcost=0; for(i=1;inextarc) if(p->costadjvex].lowcost) closedge[p->adjvex]={k,p->cost}; }//if elseForest_Prim(G,k);//对另外一个连通分量执行算法 }//for}//Forest_PrimvoidAddto_Forest(CSTree&T,inti,intj)//把边(i,j)添加到孩子兄弟链表表示的树T中{ p=Locate(T,i);//找到结点i对应的指针p,过程略 q=(CSTNode*)malloc(sizeof(CSTNode)); q->data=j; if(!p)//起始顶点不属于森林中已有的任何一棵树 { p=(CSTNode*)malloc(sizeof(CSTNode)); p->data=i; for(r=T;r->nextsib;r=r->nextsib); r->nextsib=p; p->firstchild=q; }//作为新树插入到最右侧 elseif(!p->firstchild)//双亲还没有孩子 p->firstchild=q;//作为双亲的第一个孩子 else//双亲已经有了孩子 { for(r=p->firstchild;r->nextsib;r=r->nextsib); r->nextsib=q;//作为双亲最后一个孩子的兄弟 }}//Addto_Forestmain(){ ... T=(CSTNode*)malloc(sizeof(CSTNode));//建立树根 T->data=1; Forest_Prim(G,1,T); ...}//main分析:这个算法是在Prim算法的基础上添加了非连通图支持和孩子兄弟链表构建模块而得到的,其时间复杂度为O(n^2).7.33typedefstruct{ intvex;//结点序号 intecno;//结点所属的连通分量号 }VexInfo;VexInfovexs[MAXSIZE];//记录结点所属连通分量号的数组voidInit_VexInfo(VexInfo&vexs[],intvexnum)//初始化{ for(i=0;i1) { GetMinEdge(EdgeSet,u,v);//选出最短边 if(!is_ec(vexs,u,v))//u和v属于不同连通分量 { Addto_CSTree(T,u,v);//加入到生成树中 merge_ec(vexs,vexs[u].ecno,vexs[v].ecno);//合并连通分量 ecnum--; } DelMinEdge(EdgeSet,u,v);//从边集中删除 }//while}//MinSpanTree_KruscalvoidAddto_CSTree(CSTree&T,inti,intj)//把边(i,j)添加到孩子兄弟链表表示的树T中{ p=Locate(T,i);//找到结点i对应的指针p,过程略 q=(CSTNode*)malloc(sizeof(CSTNode)); q->data=j; if(!p->firstchild)//双亲还没有孩子 p->firstchild=q;//作为双亲的第一个孩子 else//双亲已经有了孩子 { for(r=p->firstchild;r->nextsib;r=r->nextsib); r->nextsib=q;//作为双亲最后一个孩子的兄弟 }}//Addto_CSTree分析:本算法使用一维结构体变量数组来表示等价类,每个连通分量所包含的所有结点属于一个等价类.在这个结构上实现了初始化,判断元素是否等价(两个结点是否属于同一个连通分量),合并等价类(连通分量)的操作.7.34StatusTopoSeq(ALGraphG,intnew[])//按照题目要求给有向无环图的结点重新编号,并存入数组new中{ intindegree[MAXSIZE];//本算法就是拓扑排序 FindIndegree(G,indegree); Initstack(S); for(i=0;inextarc) { k=p->adjvex; if(!(--indegree[k]))Push(S,k);
} }//while if(countnextarc) { w=p->adjvex; if(!visited[w])DFS(G,w); }}//DFS7.36voidFill_MPL(ALGraph&G)//为有向无环图G添加MPL域{ FindIndegree(G,indegree); for(i=0;inextarc) { j=p->adjvex; if(G.vertices[j].MPL==0)k=Get_MPL(G,j); if(k>max)max=k;//求其直接后继顶点MPL的最大者 } G.vertices[i]=max+1;//再加一,就是当前顶点的MPL returnmax+1; }//else}//Get_MPL7.37intmaxlen,path[MAXSIZE];//数组path用于存储当前路径intmlp[MAXSIZE];//数组mlp用于存储已发现的最长路径voidGet_Longest_Path(ALGraphG)//求一个有向无环图中最长的路径
{ maxlen=0; FindIndegree(G,indegree); for(i=0;imaxlen&&!G.vertices[i].firstarc)//新的最长路径 { for(j=0;j<=len;j++)mlp[j]=path[j];//保存下来 maxlen=len; } else { for(p=G.vertices[i].firstarc;p;p=p->nextarc) { j=p->adjvex; if(!visited[j])DFS(G,j,len+1); } }//else path[i]=0; visited[i]=0;}//DFS7.38voidNiBoLan_DAG(ALGraphG)//输出有向无环图形式表示的表达式的逆波兰式{ FindIndegree(G,indegree); for(i=0;iadjvex); PrintNiBoLan_DAG(G,p->nexarc->adjvex); printf("%c",c); }}//PrintNiBoLan_DAG7.39voidPrintNiBoLan_Bitree(BitreeT)//在二叉链表存储结构上重做上一题{ if(T->lchild)
PrintNiBoLan_Bitree(T->lchild); if(T->rchild)PrintNiBoLan_Bitree(T->rchild); printf("%c",T->data);}//PrintNiBoLan_Bitree7.40intEvaluate_DAG(ALGraphG)//给有向无环图表示的表达式求值{ FindIndegree(G,indegree); for(i=0;iadjvex); v2=Evaluate_imp(G,p->nextarc->adjvex); returncalculate(v1,G.vertices[i].optr,v2); }}//Evaluate_imp分析:本题中,邻接表的vertices向量的元素类型修改如下:struct{ enumtag{NUM,OPTR}; union{ intvalue; charoptr; }; ArcNode*firstarc; }Elemtype;7.41voidCritical_Path(ALGraphG)//利用深度优先遍历求网的关键路径{ FindIndegree(G,indegree); for(i=0;inextarc) { dut=*p->info; if(ve[i]+dut>ve[p->adjvex]) ve[p->adjvex]=ve[i]+dut; DFS1(G,p->adjvex); }}//DFS1voidDFS2(ALGraphG,inti){ if(!G.vertices[i].firstarc)
vl[i]=ve[i]; else { for(p=G.vertices[i].firstarc;p;p=p->nextarc) { DFS2(G,p->adjvex); dut=*p->info; if(vl[p->adjvex]-dutadjvex]-dut; } }//else}//DFS27.42voidALGraph_DIJ(ALGraphG,intv0,Pathmatrix&P,ShortestPathTable&D)//在邻接表存储结构上实现迪杰斯特拉算法{ for(v=0;vnextarc) D[p->adjvex]=*p->info;//给D数组赋初值 for(v=0;vnextarc) { w=p->adjvex; if(!final[w]&&(min+(*p->info)size; f=p+n-1;//f指向空闲块底部 if((p-1)->tag&&(f+1)->tag)//回收块上下邻块均为占用块 { p->tag=0;f->tag=0; f->uplink=p; if(!pav) { p->llink=p; p->rlink=p; } else { q=pav->llink; p->llink=q;p->rlink=pav; q->rlink=p;pav->llink=p; } pav=p; }//if elseif(!(p-1)->tag&&(f+1)->tag)//上邻块为空闲块 { q=(p-1)->uplink; q->size+=n; f->uplink=q; f->tag=0; } elseif((p-1)->tag&&!(f+1)->tag)//下邻块为空闲块 { q=f+1; s=q->llink;t=q->rlink; p->llink=s;p->rlink=t; s->rlink=p;t->llink=p; p->size+=q->size; (q+q->size-1)->uplink=p; p->tag=0; } else//上下邻块均为空闲块 { s=(p-1)->uplink; t=f+1; s->size+=n+t->size; t->llink->rlink=t->rlink; t->rlink->llink=t->llink; (t+t->size-1)->uplink=s; }}//Free_BT,该算法在课本里有详细的描述.8.14voidFree_BS(freelist&avail,char*addr,intn)//伙伴系统的空闲块回收算法{ buddy=addr%(2*n)?(addr-n):(addr+n);//求回收块的伙伴地址
addr->tag=0; addr->kval=n; for(i=0;avail[i].nodesizellink=addr; addr->rlink=addr; avail[i].first=addr;//作为唯一一个该大小的空闲块 } else { for(p=avail[i].first;p!=buddy&&p!=avail[i].first;p=p->rlink);//寻找伙伴 if(p==buddy)//伙伴为空闲块,此时进行合并 { if(p->rlink==p)avail[i].first=NULL;//伙伴是此大小的唯一空闲块 else { p->llink->rlink=p->rlink; p->rlink->llink=p->llink; }//从空闲块链中删去伙伴 new=addr>p?p:addr;//合并后的新块首址 Free_BS(avail,new,2*n);//递归地回收新块 }//if else//伙伴为占用块,此时插入空闲块链头部 { q=p->rlink; p->rlink=addr;addr->llink=p; q->llink=addr;addr->rlink=q; } }//else}//Free_BS8.15FBList*MakeList(char*highbound,char*lowbound)//把堆结构存储的的所有空闲块链接成可利用空间表,并返回表头指针{ p=lowbound; while(p->tag&&p=highbound)returnNULL;//没有空闲块 head=p; for(q=p;ptag) { q->next=p; q=p; }//if p->next=NULL; returnhead;//返回头指针}//MakeList8.16voidMem_Contract(Heap&H)//对堆H执行存储紧缩{ q=MemStart;j=0; for(i=0;itag)
{ s=H.list[i].length; p=H.list[i].stadr; for(k=0;kkey;i++); if(i>ST.length||ST.elem[i].keyhigh)return0;//查找不到时返回0 mid=(low+high)/2; if(ST.elem[mid].key==key)returnmid; elseif(ST.elem[mid].key>key) returnSearch_Bin_Recursive(ST,key,low,mid-1); elsereturnSearch_Bin_Recursive(ST,key,mid+1,high); }}//Search_Bin_Recursive9.27intLocate_Bin(SSTableST,intkey)//折半查找,返回小于或等于待查元素的最后一个结点号{ int*r; r=ST.elem; if(key=r[ST.length].key)returnST.length; low=1;high=ST.length; while(low<=high) { mid=(low+high)/2; if(key>=r[mid].key&&keyL.idx[L.blknum].maxkey)returnERROR;//超过最大元素 low=1;high=L.blknum; found=0; while(low<=high&&!found)//折半查找记录所在块号mid { mid=(low+high)/2; if(key<=L.idx[mid].maxkey&&key>L.idx[mid-1].maxkey) found=1; elseif(key>L.idx[mid].maxkey) low=mid+1; elsehigh=mid-1; } i=L.idx[mid].firstloc;//块的下界 j=i+blksize-1;//块的上界 temp=L.elem[i-1];//保存相邻元素 L.elem[i-1]=key;//设置监视哨 for(k=j;L.elem[k]!=key;k--);//顺序查找 L.elem[i-1]=temp;//恢复元素 if(kdata==key)returnL.t; elseif(L.t->data>key) for(p=L.h,i=1;p->data!=key;p=p->next,i++); else for(p=L.t,i=L.tpos;p->data!=key;p=p->next,i++); L.t=p;//更新t指针 returnp;}//Search_CSList分析:由于题目中假定每次查找都是成功的,所以本算法中没有关于查找失败的处理.由微积分可得,在等概率情况下,平均查找长度约为n/3.9.30typedefstruct{ DLNode*pre; int
data; DLNode*next; }DLNode;typedefstruct{ DLNode*sp; intlength; }DSList;//供查找的双向循环链表类型DLNode*Search_DSList(DSList&L,intkey)//在有序双向循环链表存储结构上的查找算法,假定每次查找都成功{ p=L.sp; if(p->data>key) { while(p->data>key)p=p->pre; L.sp=p; } elseif(p->datadatanext; L.sp=p; } returnp;}//Search_DSList分析:本题的平均查找长度与上一题相同,也是n/3.9.31intlast=0,flag=1;intIs_BSTree(BitreeT)//判断二叉树T是否二叉排序树,是则返回1,否则返回0{ if(T->lchild&&flag)Is_BSTree(T->lchild); if(T->datadata; if(T->rchild&&flag)Is_BSTree(T->rchild); returnflag;}//Is_BSTree9.32intlast=0;voidMaxLT_MinGT(BiTreeT,intx)//找到二叉排序树T中小于x的最大元素和大于x的最小元素{ if(T->lchild)MaxLT_MinGT(T->lchild,x);//本算法仍是借助中序遍历来实现 if(lastdata>=x)//找到了小于x的最大元素 printf("a=%dn",last); if(last<=x&&T->data>x)//找到了大于x的最小元素 printf("b=%dn",T->data); last=T->data; if(T->rchild)MaxLT_MinGT(T->rchild,x);}//MaxLT_MinGT9.33voidPrint_NLT(BiTreeT,intx)//从大到小输出二叉排序树T中所有不小于x的元素{ if(T->rchild)Print_NLT(T->rchild,x); if(T->datadata); if(T->lchild)Print_NLT(T->lchild,x);//先右后左的中序遍历}//Print_NLT9.34
voidDelete_NLT(BiTree&T,intx)//删除二叉排序树T中所有不小于x元素结点,并释放空间{ if(T->rchild)Delete_NLT(T->rchild,x); if(T->datalchild; free(q);//如果树根不小于x,则删除树根,并以左子树的根作为新的树根 if(T)Delete_NLT(T,x);//继续在左子树中执行算法}//Delete_NLT9.35voidPrint_Between(BiThrTreeT,inta,intb)//打印输出后继线索二叉排序树T中所有大于a且小于b的元素{ p=T; while(!p->ltag)p=p->lchild;//找到最小元素 while(p&&p->datadata>a)printf("%dn",p->data);//输出符合条件的元素 if(p->rtag)p=p->rtag; else { p=p->rchild; while(!p->ltag)p=p->lchild; }//转到中序后继 }//while}//Print_Between9.36voidBSTree_Insert_Key(BiThrTree&T,intx)//在后继线索二叉排序树T中插入元素x{ if(T->datartag)//T没有右子树时,作为右孩子插入 { p=T->rchild; q=(BiThrNode*)malloc(sizeof(BiThrNode)); q->data=x; T->rchild=q;T->rtag=0; q->rtag=1;q->rchild=p;//修改原线索 } elseBSTree_Insert_Key(T->rchild,x);//T有右子树时,插入右子树中 }//if elseif(T->data>x)//插入到左子树中 { if(!T->lchild)//T没有左子树时,作为左孩子插入 { q=(BiThrNode*)malloc(sizeof(BiThrNode)); q->data=x; T->lchild=q; q->rtag=1;q->rchild=T;//修改自身的线索 } elseBSTree_Insert_Key(T->lchild,x);//T有左子树时,插入左子树中 }//if}//BSTree_Insert_Key9.37StatusBSTree_Delete_key(BiThrTree&T,intx)//在后继线索二叉排序树T中删除元素
x{ BTNode*pre,*ptr,*suc;//ptr为x所在结点,pre和suc分别指向ptr的前驱和后继 p=T;last=NULL;//last始终指向当前结点p的前一个(前驱) while(!p->ltag)p=p->lchild;//找到中序起始元素 while(p) { if(p->data==x)//找到了元素x结点 { pre=last; ptr=p; } elseif(last&&last->data==x)suc=p;//找到了x的后继 if(p->rtag)p=p->rtag; else { p=p->rchild; while(!p->ltag)p=p->lchild; }//转到中序后继 last=p; }//while//借助中序遍历找到元素x及其前驱和后继结点 if(!ptr)returnERROR;//未找到待删结点 Delete_BSTree(ptr);//删除x结点 if(pre&&pre->rtag) pre->rchild=suc;//修改线索 returnOK;}//BSTree_Delete_keyvoidDelete_BSTree(BiThrTree&T)//课本上给出的删除二叉排序树的子树T的算法,按照线索二叉树的结构作了一些改动{ q=T; if(!T->ltag&&T->rtag)//结点无右子树,此时只需重接其左子树 T=T->lchild; elseif(T->ltag&&!T->rtag)//结点无左子树,此时只需重接其右子树 T=T->rchild; elseif(!T->ltag&&!T->rtag)//结点既有左子树又有右子树 { p=T;r=T->lchild; while(!r->rtag) { s=r; r=r->rchild;//找到结点的前驱r和r的双亲s } T->data=r->data;//用r代替T结点 if(s!=T) s->rchild=r->lchild; elses->lchild=r->lchild;//重接r的左子树到其双亲结点上 q=r; }//else free(q);//删除结点}//Delete_BSTree分析:本算法采用了先求出x结点的前驱和后继,再删除x结点的办法,这样修改线索时会比较简单,直接让前驱的线索指向后继就行了.如果试图在删除x结点的同时修改线索,则问题反而复杂化了.9.38
voidBSTree_Merge(BiTree&T,BiTree&S)//把二叉排序树S合并到T中{ if(S->lchild)BSTree_Merge(T,S->lchild); if(S->rchild)BSTree_Merge(T,S->rchild);//合并子树 Insert_Key(T,S);//插入元素}//BSTree_MergevoidInsert_Node(Bitree&T,BTNode*S)//把树结点S插入到T的合适位置上{ if(S->data>T->data) { if(!T->rchild)T->rchild=S; elseInsert_Node(T->rchild,S); } elseif(S->datadata) { if(!T->lchild)T->lchild=S; elseInsert_Node(T->lchild,S); } S->lchild=NULL;//插入的新结点必须和原来的左右子树断绝关系 S->rchild=NULL;//否则会导致树结构的混乱}//Insert_Node分析:这是一个与课本上不同的插入算法.在合并过程中,并不释放或新建任何结点,而是采取修改指针的方式来完成合并.这样,就必须按照后序序列把一棵树中的元素逐个连接到另一棵树上,否则将会导致树的结构的混乱.9.39voidBSTree_Split(BiTree&T,BiTree&A,BiTree&B,intx)//把二叉排序树T分裂为两棵二叉排序树A和B,其中A的元素全部小于等于x,B的元素全部大于x{ if(T->lchild)BSTree_Split(T->lchild,A,B,x); if(T->rchild)BSTree_Split(T->rchild,A,B,x);//分裂左右子树 if(T->data<=x)Insert_Node(A,T); elseInsert_Node(B,T);//将元素结点插入合适的树中}//BSTree_SplitvoidInsert_Node(Bitree&T,BTNode*S)//把树结点S插入到T的合适位置上{ if(!T)T=S;//考虑到刚开始分裂时树A和树B为空的情况 elseif(S->data>T->data)//其余部分与上一题同 { if(!T->rchild)T->rchild=S; elseInsert_Node(T->rchild,S); } elseif(S->datadata) { if(!T->lchild)T->lchild=S; elseInsert_Node(T->lchild,S); } S->lchild=NULL; S->rchild=NULL; }//Insert_Key9.40typedefstruct{ intdata; intbf; intlsize;//lsize域表示该结点的左子树的结点总数加1 BlcNode
*lchild,*rchild; }BlcNode,*BlcTree;//含lsize域的平衡二叉排序树类型BTNode*Locate_BlcTree(BlcTreeT,intk)//在含lsize域的平衡二叉排序树T中确定第k小的结点指针{ if(!T)returnNULL;//k小于1或大于树结点总数 if(T->lsize==k)returnT;//就是这个结点 elseif(T->lsize>k) returnLocate_BlcTree(T->lchild,k);//在左子树中寻找 elsereturnLocate_BlcTree(T->rchild,k-T->lsize);//在右子树中寻找,注意要修改k的值}//Locate_BlcTree9.41typedefstruct{ enum{LEAF,BRANCH}tag;//结点类型标识 intkeynum; BPLinkparent;//双亲指针 intkey[MAXCHILD];//关键字 union{ BPLinkchild[MAXCHILD];//非叶结点的孩子指针 struct{ rectype*info[MAXCHILD];//叶子结点的信息指针 BPNode*next;//指向下一个叶子结点的链接 }leaf; } }BPNode,*BPLink,*BPTree;//B+树及其结点类型StatusBPTree_Search(BPTreeT,intkey,BPNode*ptr,intpos)//B+树中按关键字随机查找的算法,返回包含关键字的叶子结点的指针ptr以及关键字在叶子结点中的位置pos{ p=T; while(p.tag==BRANCH)//沿分支向下查找 { for(i=0;ikeynum&&key>p->key[i];i++);//确定关键字所在子树 if(i==p->keynum)returnERROR;//关键字太大 p=p->child[i]; } for(i=0;ikeynum&&key!=p->key[i];i++);//在叶子结点中查找 if(i==p->keynum)returnERROR;//找不到关键字 ptr=p;pos=i; returnOK;}//BPTree_Search 9.42voidTrieTree_Insert_Key(TrieTree&T,StringTypekey)//在Trie树T中插入字符串key,StringType的结构见第四章{ q=(TrieNode*)malloc(sizeof(TrieNode)); q->kind=LEAF; q->lf.k=key;//建叶子结点 klen=key[0]; p=T;i=1; while(p&&i<=klen&&p->bh.ptr[ord(key[i])]) { last=p; p=p->bh.ptr[ord(key[i])]; i++; }//自上而下查找
if(p->kind==BRANCH)//如果最后落到分支结点(无同义词): { p->bh.ptr[ord(key[i])]=q;//直接连上叶子 p->bh.num++; } else//如果最后落到叶子结点(有同义词): { r=(TrieNode*)malloc(sizeof(TrieNode));//建立新的分支结点 last->bh.ptr[ord(key[i-1])]=r;//用新分支结点取代老叶子结点和上一层的联系 r->kind=BRANCH;r->bh.num=2; r->bh.ptr[ord(key[i])]=q; r->bh.ptr[ord(p->lf.k[i])]=p;//新分支结点与新老两个叶子结点相连 }}//TrieTree_Insert_Key分析:当自上而下的查找结束时,存在两种情况.一种情况,树中没有待插入关键字的同义词,此时只要新建一个叶子结点并连到分支结点上即可.另一种情况,有同义词,此时要把同义词的叶子结点与树断开,在断开的部位新建一个下一层的分支结点,再把同义词和新关键字的叶子结点连到新分支结点的下一层.9.43StatusTrieTree_Delete_Key(TrieTree&T,StringTypekey)//在Trie树T中删除字符串key{ p=T;i=1; while(p&&p->kind==BRANCH&&i<=key[0])//查找待删除元素 { last=p; p=p->bh.ptr[ord(key[i])]; i++; } if(p&&p->kind==LEAF&&p->lf.k=key)//找到了待删除元素 { last->bh.ptr[ord(key[i-1])]=NULL; free(p); returnOK; } elsereturnERROR;//没找到待删除元素}//TrieTree_Delete_Key9.44voidPrint_Hash(HashTableH)//按第一个字母顺序输出Hash表中的所有关键字,其中处理冲突采用线性探测开放定址法{ for(i=1;i<=26;i++) for(j=i;H.elem[j].key;j=(j+1)%hashsize[sizeindex])//线性探测 if(H(H.elem[j].key)==i)printf("%sn",H.elem[j]);}//Print_HashintH(char*s)//求Hash函数{ if(s)returns[0]-96;//求关键字第一个字母的字母序号(小写) elsereturn0;}//H9.45typedef*LNode[MAXSIZE]CHashTable;//链地址Hash表类型StatusBuild_Hash(CHashTable&T,intm)//输入一组关键字,建立Hash表,表长为m,用链地址法处理冲突
.{ if(m<1)returnERROR; T=malloc(m*sizeof(WORD));//建立表头指针向量 for(i=0;idata=key;q->next=NULL; n=H(key); if(!T[n])T[n]=q;//作为链表的第一个结点 else { for(p=T[n];p->next;p=p->next); p->next=q;//插入链表尾部.本算法不考虑排序问题. } }//while returnOK;}//Build_Hash9.46StatusLocate_Hash(HashTableH,introw,intcol,KeyTypekey,int&k)//根据行列值在Hash表表示的稀疏矩阵中确定元素key的位置k{ h=2*(100*(row/10)+col/10);//作者设计的Hash函数 while(H.elem[h].key&&!EQ(H.elem[h].key,key)) h=(h+1)%20000; if(EQ(H.elem[h].key,key))k=h; elsek=NULL;}//Locate_Hash分析:本算法所使用的Hash表长20000,装填因子为50%,Hash函数为行数前两位和列数前两位所组成的四位数再乘以二,用线性探测法处理冲突.当矩阵的元素是随机分布时,查找的时间复杂度为O(1).第十章内部排序10.23voidInsert_Sort1(SqList&L)//监视哨设在高下标端的插入排序算法{ k=L.length; for(i=k-1;i;--i)//从后向前逐个插入排序 if(L.r[i].key>L.r[i+1].key) { L.r[k+1].key=L.r[i].key;//监视哨 for(j=i+1;L.r[j].key>L.r[i].key;++j) L.r[j-1].key=L.r[j].key;//前移 L.r[j-1].key=L.r[k+1].key;//插入 }}//Insert_Sort110.24voidBiInsert_Sort(SqList&L)//二路插入排序的算法{ intd[MAXSIZE];//辅助存储 x=L.r.key;d
=x; first=1;final=1; for(i=2;i<=L.length;i++) { if(L.r[i].key>=x)//插入前部 { for(j=final;d[j]>L.r[i].key;j--) d[j+1]=d[j]; d[j+1]=L.r[i].key; final++; } else//插入后部 { for(j=first;d[j]L.r[i]; L.r[i].next=p; } p=q; }//for}//SLInsert_Sort10.26voidBubble_Sort1(inta[],intn)//对包含n个元素的数组a进行改进的冒泡排序{ change=n-1;//change指示上一趟冒泡中最后发生交换的元素 while(change) { for(c=0,i=0;ia[i+1]) {
a[i]<->a[i+1]; c=i+1;//c指示这一趟冒泡中发生交换的元素 } change=c; }//while}//Bubble_Sort110.27voidBubble_Sort2(inta[],intn)//相邻两趟是反方向起泡的冒泡排序算法{ low=0;high=n-1;//冒泡的上下界 change=1; while(lowa[i+1]) { a[i]<->a[i+1]; change=1; } high--;//修改上界 for(i=high;i>low;i--)//从下向上起泡 if(a[i]a[i-1]; change=1; } low++;//修改下界 }//while}//Bubble_Sort210.28voidBubble_Sort3(inta[],intn)//对上一题的算法进行化简,循环体中只包含一次冒泡{ intb[3];//b[0]为冒泡的下界,b[2]为上界,b[1]无用 d=1;b[0]=0;b[2]=n-1;//d为冒泡方向的标识,1为向上,-1为向下 change=1; while(b[0]0)//注意这个交换条件 { a[i]<->a[i+d]; change=1; } b[1+d]-=d;//修改边界 d*=-1;//换个方向 }//while}//Bubble_Sort310.29voidOE_Sort(inta[],intn)//奇偶交换排序的算法{ change=1; while(change) {
change=0; for(i=1;ia[i+1]) { a[i]<->a[i+1]; change=1; } for(i=0;ia[i+1]) { a[i]<->a[i+1]; change=1; } }//while}//OE_Sort分析:本算法的结束条件是连续两趟比较无交换发生10.30typedefstruct{ intlow; inthigh; }boundary;//子序列的上下界类型voidQSort_NotRecurve(intSQList&L)//快速排序的非递归算法{ low=1;high=L.length; InitStack(S);//S的元素为boundary类型 while(low2)//如果当前子序列长度大于3且尚未排好序 { pivot=Partition(L,low,high);//进行一趟划分 if(high-pivot>pivot-low) { Push(S,{pivot+1,high});//把长的子序列边界入栈 high=pivot-1;//短的子序列留待下次排序 } else { Push(S,{low,pivot-1}); low=pivot+1; } }//if elseif(low=pivotkey) high--; L.r[low]=L.r[high]; while(lowL.r[high].key)L.r[low]<->L.r[high]; else//子序列含有三个元素 { if(L.r[low].key>L.r[low+1].key)L.r[low]<->L.r[low+1]; if(L.r[low+1].key>L.r[high].key)L.r[low+1]<->L.r[high]; if(L.r[low].key>L.r[low+1].key)L.r[low]<->L.r[low+1]; }}//Easy_Sort10.31voidDivide(inta[],intn)//把数组a中所有值为负的记录调到非负的记录之前{ low=0;high=n-1; while(low=0)high--;//以0作为虚拟的枢轴记录 a[low]<->a[high]; while(lowa[high]; }}//Divide10.32typedefenum{RED,WHITE,BLUE}color;//三种颜色voidFlag_Arrange(colora[],intn)//把由三种颜色组成的序列重排为按照红,白,蓝的顺序排列{ i=0;j=0;k=n-1; while(j<=k) switch(a[j]) { caseRED: a[i]<->a[j]; i++; j++; break; caseWHITE: j++; break; caseBLUE: a[j]<->a[k]; k--;//这里没有j++;语句是为了防止交换后a[j]仍为蓝色的情况
}}//Flag_Arrange分析:这个算法中设立了三个指针.其中,j表示当前元素;i以前的元素全部为红色;k以后的元素全部为蓝色.这样,就可以根据j的颜色,把其交换到序列的前部或者后部.10.33voidLinkedList_Select_Sort(LinkedList&L)//单链表上的简单选择排序算法{ for(p=L;p->next->next;p=p->next) { q=p->next;x=q->data; for(r=q,s=q;r->next;r=r->next)//在q后面寻找元素值最小的结点 if(r->next->datanext->data; s=r; } if(s!=q)//找到了值比q->data更小的最小结点s->next { p->next=s->next;s->next=q; t=q->next;q->next=p->next->next; p->next->next=t; }//交换q和s->next两个结点 }//for}//LinkedList_Select_Sort10.34voidBuild_Heap(Heap&H,intn)//从低下标到高下标逐个插入建堆的算法{ for(i=2;iH.r[k].key) H.r[j]<->H.r[k]; j=k; } }//for}//Build_Heap10.35voidTriHeap_Sort(Heap&H)//利用三叉树形式的堆进行排序的算法{ for(i=H.length/3;i>0;i--) Heap_Adjust(H,i,H.length); for(i=H.length;i>1;i--) { H.r[1]<->H.r[i]; Heap_Adjust(H,1,i-1); }}//TriHeap_SortvoidHeap_Adjust(Heap&H,ints,intm)//顺序表H中,H.r[s+1]到H.r[m]已经是堆,把H.r[s]插入并调整成堆
{ rc=H.r[s]; for(j=3*s-1;j<=m;j=3*j-1) { if(j(n-1)?(n-1):(start2+l-1);//注意end2可能超出边界 Merge(a,start1,end1,start2,end2);//归并 }}//Merge_SortvoidMerge(inta[],ints1,inte1,ints2,inte2)//将有序子序列a[s1]到a[e1]和a[s2]到a[e2]归并为有序序列a[s1]到a[e2]{ intb[MAXSIZE];//设立辅助存储数组b for(i=s1,j=s2,k=s1;i<=e1&&j<=e2;k++) { if(a[i]next,e2=p;p->next;p=e2) { for(i=1,q=p;i<=l&&q->next;i++,q=q->next); e1=q; for(i=1;i<=l&&q->next;i++,q=q->next); e2=q;//求出两个待归并子序列的尾指针 if(e1!=e2)LinkedList_Merge(L,p,e1,e2);//归并 }}//LinkedList_Merge_Sort1voidLinkedList_Merge(LinkedList&L,LNode*p,LNode*e1,LNode*e2)//对链表上的子序列进行归并,第一个子序列是从p->next到e1,第二个是从e1->next到e2{ q=p->next;r=e1->next;//q和r为两个子序列的起始位置
while(q!=e1->next&&r!=e2->next) { if(q->datadata)//选择关键字较小的那个结点接在p的后面 { p->next=q;p=q; q=q->next; } else { p->next=r;p=r; r=r->next; } }//while while(q!=e1->next)//接上剩余部分 { p->next=q;p=q; q=q->next; } while(r!=e2->next) { p->next=r;p=r; r=r->next; }}//LinkedList_Merge10.38voidLinkedList_Merge_Sort2(LinkedList&L)//初始归并段为最大有序子序列的归并排序,采用链表存储结构{ LNode*end[MAXSIZE];//设立一个数组来存储各有序子序列的尾指针 for(p=L->next->next,i=0;p;p=p->next)//求各有序子序列的尾指针 if(!p->next||p->data>p->next->data)end[i++]=p; while(end[0]->next)//当不止一个子序列时进行两两归并 { j=0;k=0;//j:当前子序列尾指针存储位置;k:归并后的子序列尾指针存储位置 for(p=L->next,e2=p;p->next;p=e2)//两两归并所有子序列 { e1=end[j];e2=end[j+1];//确定两个子序列 if(e1->next)LinkedList_Merge(L,p,e1,e2);//归并 end[k++]=e2;//用新序列的尾指针取代原来的尾指针 j+=2;//转到后面两个子序列 } }//while}//LinkedList_Merge_Sort2voidLinkedList_Merge(LinkedList&L,LNode*p,LNode*e1,LNode*e2)//对链表上的子序列进行归并,第一个子序列是从p->next到e1,第二个是从e1->next到e2{ q=p->next;r=e1->next; while(q!=e1->next&&r!=e2->next) { if(q->datadata) { p->next=q;p=q; q=q->next; } else
{ p->next=r;p=r; r=r->next; } }//while while(q!=e1->next) { p->next=q;p=q; q=q->next; } while(r!=e2->next) { p->next=r;p=r; r=r->next; }}//LinkedList_Merge,与上一题完全相同10.39voidSL_Merge(inta[],intl1,intl2)//把长度分别为l1,l2且l1^2<(l1+l2)的两个有序子序列归并为有序序列{ start1=0;start2=l1;//分别表示序列1和序列2的剩余未归并部分的起始位置 for(i=0;ia[i])b[i].gt++; elseif(a[j]a[min];//与第i个记录交换 c[min]=INFINITY;//修改该记录的c值为无穷大以便下一次选取
}}//Count_Sort10.44voidEnum_Sort(inta[],intn)//对关键字只能取v到w之间任意整数的序列进行排序{ intnumber[w+1],pos[w+1]; for(i=0;i1&&change;i--)//对影子序列执行冒泡排序 { change=0; for(j=0;jd[j+1].key)
{ d[j]<->d[j+1]; change=1; } }//for for(i=0;i'
您可能关注的文档
- 东财13秋季《管理学B》随机(全套)在线作业参考答案.doc
- 东财15秋《工程设备》作业练习题及答案.doc
- 东财2013春季--2014秋季《管理学B》随机(超全)在线作业参考答案.doc
- 东财2013秋季《管理学B》随机(大全)在线作业参考答案.doc
- 东财《人力资源管理》题库,答案在题目后面.doc
- 东财《保险学概论》全部作业题及答案.docx
- 东财《内部控制与风险管理》在线作业最全题目集及答案.doc
- 东财《组织行为学》作业题库含答案(90分以上).docx
- 东财《财务管理》在线作业复习题及答案汇总.doc
- 严蔚敏C语言版《数据结构》习题集答案.pdf
- 严蔚敏数据结构题集(C语言版)完整答案.doc
- 严飞_《软件技术基础》沈被娜习题解答.doc
- 个人风险管理与保险规划练习题.doc
- 中内题库11—20及答案.doc
- 中医四大经典之《伤寒论》复习试题及答案.doc
- 中医基础理论习题及答案.doc
- 中医眼科习题集附答案.pdf
- 中医英语课后翻译习题答案(全).pdf
微信/支付宝扫码支付下载