else {
for(maxd=0,p=T->firstchild;p;p=p->nextsib)
if((d=GetDepth_CSTree(p))>maxd) maxd=d; //子树的最大深度 return maxd+1; }
}//GetDepth_CSTree 6.63
int GetDepth_CTree(CTree A)//求孩子链表表示的树A的深度 {
return SubDepth(A.r); }//GetDepth_CTree
int SubDepth(int T)//求子树T的深度 {
if(!A.nodes[T].firstchild) return 1;
for(sd=1,p=A.nodes[T].firstchild;p;p=p->next) if((d=SubDepth(p->child))>sd) sd=d; return sd+1; }//SubDepth 6.64
int GetDepth_PTree(PTree T)//求双亲表表示的树T的深度 {
maxdep=0;
for(i=0;i dep=0; for(j=i;j>=0;j=T.nodes[j].parent) dep++; //求每一个结点的深度 if(dep>maxdep) maxdep=dep; } return maxdep; }//GetDepth_PTree 6.65 char Pred,Ind; //假设前序序列和中序序列已经分别储存在数组Pre和In中 Bitree Build_Sub(int Pre_Start,int Pre_End,int In_Start,int In_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; } //建右子树,注意参数表的计算 return sroot; //返回子树根 }//Build_Sub main() { ... Build_Sub(1,n,1,n); //初始调用参数,n为树结点总数 ... } 分析:本算法利用了这样一个性质,即一棵子树在前序和中序序列中所占的位置总是连续的.因此,就可以用起始下标和终止下标来确定一棵子树.Pre_Start,Pre_End,In_Start和In_End分别指示子树在前序子序列里的起始下标,终止下标,和在中序子序列里的起始和终止下标. 6.66 typedef struct{ CSNode *ptr; CSNode *lastchild; } NodeMsg; //结点的指针和其最后一个孩子的指针 Status Bulid_CSTree_PTree(PTree T)//由树T的双亲表构造其孩子兄弟链表 { NodeMsg Treed; for(i=0;i Tree[i].ptr=(CSNode*)malloc(sizeof(CSNode)); Tree[i].ptr->data=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 }//Bulid_CSTree_PTree 6.67 typedef struct{ char data; CSNode *ptr; CSNode *lastchild; } NodeInfo; //结点数据,结点指针和最后一个孩子的指针 Status CreateCSTree_Duplet(CSTree &T)//输入二元组建立树的孩子兄弟链表 { NodeInfo Treed; n=1;k=0; if(getchar()!='^') return ERROR; //未按格式输入 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) return ERROR; //未找到:未按层序输入 r=Tree[k].ptr; if(!r->firstchild) r->firstchild=Tree[n].ptr; else Tree[k].lastchild->nextsib=Tree[n].ptr; Tree[k].lastchild=Tree[n].ptr; //这一段含义同上一题 n++; }//while return OK; }//CreateCSTree_Duplet 6.68 Status CreateCSTree_Degree(char node[ ],int degree[ ])//由结点的层序序列和各结点的度构造树的孩子兄弟链表 { CSNode * ptrd; //树结点指针的辅助存储 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时,为其孩子建立兄弟链表 }//for }//if i++; }//while }//CreateCSTree_Degree 6.69 void Print_BiTree(BiTree T,int i)//按树状打印输出二叉树的元素,i表示结点所在层次,初次调用时i=0 { if(T->rchild) Print_BiTree(T->rchild,i+1); for(j=1;j<=i;j++) printf(\打印i个空格以表示出层次 printf(\打印T元素,换行 if(T->lchild) Print_BiTree(T->rchild,i+1); }//Print_BiTree 分析:该递归算法实际上是带层次信息的中序遍历,只不过按照题目要求,顺序为先右后左. 6.70 Status CreateBiTree_GList(BiTree &T)//由广义表形式的输入建立二叉链表 { c=getchar(); if(c=='#') T=NULL; //空子树 else { T=(CSNode*)malloc(sizeof(CSNode)); T->data=c; if(getchar()!='(') return ERROR; if(!CreateBiTree_GList(pl)) return ERROR; T->lchild=pl; if(getchar()!=',') return ERROR; if(!CreateBiTree_GList(pr)) return ERROR; T->rchild=pr; if(getchar()!=')') return ERROR; //这些语句是为了保证输入符合A(B,C)的格式 } return OK; }//CreateBiTree_GList 6.71 void Print_CSTree(CSTree T,int i)//按凹入表形式打印输出树的元素,i表示结点所在层次,初次调用时i=0 { for(j=1;j<=i;j++) printf(\留出i个空格以表现出层次 printf(\打印元素,换行 for(p=T->firstchild;p;p=p->nextsib) Print_CSTree(p,i+1); //打印子树 }//Print_CSTree 6.72 void Print_CTree(int e,int i)//按凹入表形式打印输出树的元素,i表示结点所在层次 { for(j=1;j<=i;j++) printf(\留出i个空格以表现出层次 printf(\打印元素,换行 for(p=T.nodes[e].firstchild;p;p=p->next) Print_CSTree(p->child,i+1); //打印子树 }//Print_CSTree main() { ... Print_CTree(T.r,0); //初次调用时i=0 ... }//main 6.73 char c; //全局变量,指示当前字符 Status CreateCSTree_GList(CSTree &T)//由广义表形式的输入建立孩子兄弟链表 { c=getchar(); T=(CSNode*)malloc(sizeof(CSNode)); T->data=c; if((c=getchar())=='(') //非叶结点 { if(!CreateCSTree_GList(fc)) return ERROR; //建第一个孩子 T->firstchild=fc; for(p=fc;c==',';p->nextsib=nc,p=nc) //建兄弟链 if(!CreateCSTree_GList(nc)) return ERROR; p->nextsib=NULL; if((c=getchar())!=')') return ERROR; //括号不配对 } else T->firtchild=NULL; //叶子结点 return OK; }//CreateBiTree_GList 分析:书后给出了两个间接递归的算法,事实上合成一个算法在形式上可能更好一些.本算法另一个改进之处在于加入了广义表格式是否合法的判断. 6.74 void PrintGlist_CSTree(CSTree T)//按广义表形式输出孩子兄弟链表表示的树 { printf(\ if(T->firstchild) //非叶结点 { printf(\ for(p=T->firstchild;p;p=p->nextsib) { PrintGlist_CSTree(p); if(p->nextsib) printf(\最后一个孩子后面不需要加逗号 } printf(\ }//if }//PrintGlist_CSTree 6.75 char c; int pos=0; //pos是全局变量,指示已经分配到了哪个结点 Status CreateCTree_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())!=')') return ERROR; //括号不配对 }//if else T.nodes[i].firtchild=NULL; //叶子结点 return OK; }//CreateBiTree_GList 分析:该算法中,pos变量起着\分配\结点在表中的位置的作用,是按先序序列从上向下分配,因此树根T.r一定等于0,而最终的pos值就是结点数T.n. 6.76 void PrintGList_CTree(CTree T,int i)//按广义表形式输出孩子链表表示的树 { printf(\ 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.14 Status Build_AdjList(ALGraph &G)//输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表 { InitALGraph(G); scanf(\ if(v<0) return ERROR; //顶点数不能为负 G.vexnum=v; scanf(\ if(a<0) return ERROR; //边数不能为负 G.arcnum=a; for(m=0;m G.vertices[m].data=getchar(); //输入各顶点的符号 for(m=1;m<=a;m++) { t=getchar();h=getchar(); //t为弧尾,h为弧头 if((i=LocateVex(G,t))<0) return ERROR; if((j=LocateVex(G,h))<0) return ERROR; //顶点未找到 p=(ArcNode*)malloc(sizeof(ArcNode)); if(!G.vertices.[i].firstarc) G.vertices[i].firstarc=p; else { for(q=G.vertices[i].firstarc;q->nextarc;q=q->nextarc); q->nextarc=p; } p->adjvex=j;p->nextarc=NULL; }//while return OK; }//Build_AdjList 7.15 //本题中的图G均为有向无权图,其余情况容易由此写出 Status Insert_Vex(MGraph &G, char v)//在邻接矩阵表示的图G上插入顶点v { if(G.vexnum+1)>MAX_VERTEX_NUM return INFEASIBLE; G.vexs[++G.vexnum]=v; return OK; }//Insert_Vex Status Insert_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上插入边(v,w) { if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; if(i==j) return ERROR; if(!G.arcs[i][j].adj) { G.arcs[i][j].adj=1; G.arcnum++; } return OK; }//Insert_Arc Status Delete_Vex(MGraph &G,char v)//在邻接矩阵表示的图G上删除顶点v { n=G.vexnum; if((m=LocateVex(G,v))<0) return ERROR; G.vexs[m]<->G.vexs[n]; //将待删除顶点交换到最后一个顶点