现在位置: > > 外语学习 > 韩语学习

2011年河南省JAVA最新版本摘要

2011年河南省JAVA最新版本摘要

1、因为后序遍历栈中保留当前结点的祖先的信息,用一变量保存栈的最高栈顶指针,每当退栈时,栈顶指针高于保存最高栈顶指针的值时,则将该栈倒入辅助栈中,辅助栈始终保存最长路径长度上的结点,直至后序遍历完毕,则辅助栈中内容即为所求。
void LongestPath(BiTree bt)//求二叉树中的第一条最长路径长度
{BiTree p=bt,l[],s[]; //l, s是栈,元素是二叉树


结点指针,l中保留当前最长路径中的结点
int i,top=0,tag[],longest=0;
while(p || top>0)
{ while(p) {s[++top]=p;tag[top]=0; p=p->Lc;} //沿左分枝向下
if(tag[top]==1) //当前结点的右分枝已遍历
{if(!s[top]->Lc && !s[top]->Rc) //只有到叶子结点时,才查看路径长度
if(top>longest) {for(i=1;i<=top;i++) l[i]=s[i]; longest=top; top--;}
//保留当前最长路径到l栈,记住最高栈顶指针,退栈
}
else if(top>0) {tag[top]=1; p=s[top].Rc;} //沿右子分枝向下
}//while(p!=null||top>0)
}//结束LongestPath

2、题目中要求矩阵两行元素的平均值按递增顺序排序,由于每行元素个数相等,按平均值排列与按每行元素之和排列是一个意思。所以应先求出各行元素之和,放入一维数组中,然后选择一种排序方法,对该数组进行排序,注意在排序时若有元素移动,则与之相应的行中各元素也必须做相应变动。
void Translation(float *matrix,int n)
//本算法对n×n的矩阵matrix,通过行变换,使其各行元素的平均值按递增排列。
{int i,j,k,l;
float sum,min; //sum暂存各行元素之和
float *p, *pi, *pk;
for(i=0; i<n; i++)
{sum=0.0; pk=matrix+i*n; //pk指向矩阵各行第1个元素.
for (j=0; j<n; j++){sum+=*(pk); pk++;} //求一行元素之和.
*(p+i)=sum; //将一行元素之和存入一维数组.
}//for i
for(i=0; i<n-1; i++) //用选择法对数组p进行排序
{min=*(p+i); k=i; //初始设第i行元素之和最小.
for(j=i+1;j<n;j++) if(p[j]<min) {k=j; min=p[j];} //记新的最小值及行号.
if(i!=k) //若最小行不是当前行,要进行交换(行元素及行元素之和)
{pk=matrix+n*k; //pk指向第k行第1个元素.
pi=matrix+n*i; //pi指向第i行第1个元素.
for(j=0;j<n;j++) //交换两行中对应元素.
{sum=*(pk+j); *(pk+j)=*(pi+j); *(pi+j)=sum;}
sum=p[i]; p[i]=p[k]; p[k]=sum; //交换一维数组中元素之和.
}//if
}//for i
free(p); //释放p数组.
}// Translation
[算法分析]

算法中使用选择法排序,比较次数较多,但数据交换(移动)较少.若用其它排序方法,虽可减少比较次数,但数据移动会增多.算法时间复杂度为O(n2).

3、 二叉树的层次遍历序列的第一个结点是二叉树的根。实际上,层次遍历序列中的每个结点都是“局部根”。确定根后,到二叉树的中序序列中,查到该

相关文档
2011年河南省JAVA最新版本摘要
2011年河南省JAVA最新版本摘要_韩语学习_外语学习_教育专区。2011年河南省JAVA最新版本摘要 1、二部图(bipartite graph) G=(V,E)是一个能将其结点集 V 分为...
2011年河南省JAVA最新版本摘要
2011年河南省JAVA最新版本摘要_韩语学习_外语学习_教育专区。2011年河南省JAVA最新版本摘要 1、在有向图 G 中,如果 r 到 G 中的每个结点都有路径可达,则称...
2011年河南省JAVA最新版本摘要
2011年河南省JAVA最新版本摘要_韩语学习_外语学习_教育专区。2011年河南省JAVA最新版本摘要 1、 假设以邻接矩阵作为图的存储结构, 编写算法判别在给定的有向图中...
2011年河南省JAVA最新版本摘要
2011年河南省JAVA最新版本摘要_韩语学习_外语学习_教育专区。2011年河南省JAVA最新版本摘要 1、 假设以邻接矩阵作为图的存储结构, 编写算法判别在给定的有向图中...
2010年河南省java最新版本摘要
2010年河南省java最新版本摘要_互联网_IT/计算机_专业资料。1、#define maxsize 栈空间容量 void InOutS(int s[maxsize]) //s 是元素为整数的栈,本算法进行入...
2010年河南省java最新版本摘要
2010年河南省java最新版本摘要_互联网_IT/计算机_专业资料。1、#define maxsize 栈空间容量 void InOutS(int s[maxsize]) //s 是元素为整数的栈,本算法进行入...
2010年河南省JAVA最新版本摘要
2010年河南省JAVA最新版本摘要_韩语学习_外语学习_教育专区。2010年河南省JAVA最新版本摘要 1、对一般二叉树,仅根据一个先序、中序、后序遍历,不能确定另一个...
2013年河南省JAVA最新版本摘要
2013年河南省JAVA最新版本摘要_韩语学习_外语学习_教育专区。2013年河南省JAVA最新版本摘要 1、设一棵树 T 中边的集合为{(A,B),(A,C),(A,D),(B,E),(...
2013年河南省JAVA最新版本摘要
2013年河南省JAVA最新版本摘要_韩语学习_外语学习_教育专区。2013年河南省JAVA最新版本摘要 1、设一棵树 T 中边的集合为{(A ,B),(A ,C),(A ,D),(B ,...
2014年河南省JAVA最新版本摘要
2014年河南省JAVA最新版本摘要_韩语学习_外语学习_教育专区。2014年河南省JAVA最新版本摘要 1、根据二叉排序树中序遍历所得结点值为增序的性质,在遍历中将当前遍历...
相关主题
返回顶部
热门文档