几种算法

核心提示：【题目】已知一棵二叉树按顺序方式存储在数组 A[1..n]中，设计算法求出下标分别为 i 和 j 的两个结点的最近的公共祖先结点的值，几种算法，【来源】武汉大学2000年第五（1）题（8’）【解答】#inlcude <stdio.h>parent(int A[],int i,int j){int k,m;m

　　【题目】已知一棵二叉树按顺序方式存储在数组 A[1..n]中。设计算法求出下标分别为 i 和 j 的两个结点的最近的公共祖先结点的值。

【来源】武汉大学2000年第五（1）题（8’）

【解答】
#inlcude <stdio.h>
parent(int A[],int i,int j)
{int k,m;
m=k=0;
if(i==1j==1A[i]==0A[j]==0i==j) // A[i]==0或A[j]==0表示不存在该结点
{PRintf("Error.\n");return;}
while(i!=1&&j!=1){
if(i<j){j=j/2;m=1;} // 结点 j 的最近祖先结点是 ┗ j/2 ┛
else if(j<i){i=i/2;k=1;}
else if(j==i){i=j;break;} // i=j 表示找到共同祖先
}
if(j==1i==1)i=1; // i 或 j 有一个到了根结点
else if(m==0k==0)i=i/2; // m、k 中有一个为 0 ，说明在查找过程中 i 或 j 有一个没移动
printf("The nearest common parent is A[%d].\n",i);
}


【分析】本题思路是使 i 和 j 交替追赶，直到相等。

------------------------------------------------------------------------
【题目】试写一个判别给定二叉树是否为二叉排序树的算法。

【来源】长沙铁道学院98年第五（1）题（12’）

【解答】
typedef strUCt node{
char data;
struct node *left,*right;
}*T;

issorttree(T)
{
initqueue(Q); // 初始化队列
inqueue(Q,T); // 树根结点进队列
while(!empty(Q)){
outqueue(Q,T);
if(T->data>T->left->data&&T->data<T->right->data){
if(T->left)inqueue(Q,T->left);
if(T->right)inqueue(Q,T->right);
}
else if(T->leftT->right)return 1; // 不符合二叉排序树的特征，则终止并返回‘ 1 ’
}
return 0; // 是二叉排序树，则返回 ‘0’
}

【分析】注重队列的运用，其他如图的广度搜索（教材《清华 C 版》）。

------------------------------------------------------------------------------
【题目】设一单向链表的头指针为head,链表的记录中包含着整数类型的key域,试设计算法,
将此链表的记录按照key递增的次序进行就地排序.（不答应使用数组做辅助存储）

【来源】中科院计算机技术研究所1999年第五（1）题 （10’）
华中理工大学2000年第八（2）题 （13’）

【解答】
typedef struct CircleList{ // 定义循环链表
int key;
struct CircleList *next;
}*listnode;

ListSort(listnode head)
{
int k,min,i,j;
listnode p,q,t;
p=head->next;
while(p->next!=head->next){p=p->next;k+=1;} // 统计链表中元素个数，保存在 K 中
p=head;j=1;
for(i=1;i<k;i++){
while(j<=i){p=p->next;j++;} // 找应填入当前最小元素的位置，该位置保存在 q 中
min=p->key;q=p; // 将当前位置元素的值设为初始最小值
while(p->next!=head->next){
if(min>p->key){min=p->key;t=p;} // 找当前最小元素，并保存在 t 所指位置中
p=p->next;
}
t->key=q->key;q->key=min;j=1; // 交换 q 位置元素和最小元素的值
}
}

【分析】本题不需要修改链表中的各个指针。

--------------------------------------------------------------------------
前几天根据快速排序 Quick Sort算法的基本思想，编写了如下分治策略的算法，供大家讨论： 
思路： 
设输入的序列L[p..r]，确定支点元素l[p]和l[r],并使l[p].key<=l[r].key 
分解(Divide)：将序列L[p..r]划分成三个子序列L[p..k-1]、L[k+1..m-1]和L[m+1..r]，使L[p..q]中关系为L[p..k-1]、l[k]、L[k+1..m-1]、l[m]、L[m+1..r]任一区间元素的值不大于其后区间元素的值。 
递归求解(Conquer)：通过递归调用快速排序算法分别对L[p..k-1]、L[k+1..m-1]和L[m+1..r]进行排序。 
算法的实现（用C语言实现） 
QSort(Sqlist &L,int low,int high){ 
c=high-low; /*循环次数*/ 
if(c<10)直接调用插入排序法; /*小数时直接调用插入排序法*/ 
if(L.r[low].key>L.r[high].key)L.r[low]<->L.r[high]; /*确保区间内第一个元素的值不大于区间内最后一个元素的值*/ 
ilow=low; /*小于区间内第一个元素的值数组边界下标*/ 
ihigh=high; /*大于区间内最后一个元素的值数组边界下标*/ 
for(i=low+1;i<c;i++){ 
if(L.r[i].key<L.r[low].key)L.r[i]<->L.r[++ilow]; /*小于区间内第一个元素的值放置ilow区间内*/ 
else 
if(L.r[i].key>L.r[high].key){ 
L.r[i]<->L.r[--ihigh]; /*大于区间内最后一个元素的值放置ihigh区间内*/ 
i--; /*下一个比较位置不变*/ 
c--; /*循环次数减一*/ 
} 
} 
L.r[ilow]<->L.r[low]; /*将小于区间内第一个元素的边界下标元素与第一个元素互换*/ 
L.r[ihigh]<->L.r[high]; /*将大于区间内最后一个元素的边界下标元素与最后一个元素互换*/ 
QSort(L,low,ilow-1); 
QSort(L,ilow+1,ihigh-1); 
QSort(L,ihigh+1,high); 
} 
void QuickSort(Sqlist &L) 
{ 
QSort(L,1,L.length); 
} 
优点： 
1、每次快速排序将确定二个元素位置 
2、每次快速排序将划分三个区间，优化后续平均时间和空间复杂度 
缺点： 
1、存在较多的元素交换（每次需要三步），不及改进快速排序法利用空穴赋值方便

--------------------------------------------------------------------------------------

四阶Runge-Kutta法 

一阶常微分方程： 
u'=f(t,u) a<t<b
u(t(0))=u(0) 


Runge-Kutta非线性高阶单步法，p阶R-K法的整体阶段误差为O(h^p)

R-K四阶算法：
u(i+1)=u(i)+h*(k1+3*k2+3*k3+k4)/8
k1=f(t(i),u(i))
k2=f(t(i+h/3),u(i+h*k1/3))
k3=f(t(i+h/3),u(i+h*k2/3))
k4=f(t(i+h),u(i+h*k3)) 

四阶程序如下：
class RK{
private:
double k1,k2,k3,k4;
double h,b,u,a;
public:
void seth(double l=0){h=l;} //设步长
void setf(double xa=0,double xb=0,double y=0) //设初值和范围（xa,xb）
{
b=xb;
a=xa;
u=y;
}
double f(double t,double u) //函数值，修改它以适应各自需要
{
//函数设定
double f=u-2*t/u; 
return f;
}
void dork() //R-K 主函数
{
for(int count=0;count<(b-a)/h;count++)
{
k1=f(a+count*h,u);
k2=f(a+count*h+h/3,u+h*k1/3);
k3=f(a+count*h+2*h/3,u-h*k1/3+h*k2);
k4=f(a+count*h+h,u+h*k1-h*k2+h*k3);
u=u+h*(k1+3*k2+3*k3+k4)/8;
count<<u<<endl;
}

}
}; 

void main()
{
RK my;
my.seth(0.1);
my.setf(0,1,1);
my.dork();
}

--------------------------------------------------------------------------------------
快速排序 

算法的基本思想：

快速排序的基本思想是基于分治策略的。对于输入的子序列ap..ar，假如规模足够小则直接进行排序，否则分三步处理：

分解(Divide)：将输入的序列ap..ar划分成两个非空子序列ap..aq和aq+1..ar，使ap..aq中任一元素的值不大于aq+1..ar中任一元素的值。 
递归求解(Conquer)：通过递归调用快速排序算法分别对ap..aq和aq+1..ar进行排序。 
合并(Merge)：由于对分解出的两个子序列的排序是就地进行的，所以在ap..aq和aq+1..ar都排好序后不需要执行任何计算ap..ar就已排好序。 
这个解决流程是符合分治法的基本步骤的。因此，快速排序法是分治法的经典应用实例之一。

算法Quick_Sort的实现：

Pascal实现：
Procedure Quick_Sort(p,r:TPosition;var L:TList); {快速排序}

var

q:TPosition;

begin

if L[p..r]足够小 then Sort(p,r,L) {若L[p..r]足够小则直接对L[p..r]排序}

else

begin

q:=Partition(p,r,L); {将L[p..r]分解为L[p..q]和L[q+1..r]两部分}

Quick_Sort(p,q,L); {递归排序L[p..q]}

Quick_Sort(q+1,r,L); {递归排序L[q+1..r]}

end;

end;

--------------------------------------------------------------------------------------
【题目】设中序线索二叉树的结点结构为：leftltagdatartagright. 现已知中序线索
二叉树的根结点地址root。设计一程序，打印出该线索二叉树的中序遍历结果.不得
再使用O(n)级的辅存空间。

【来源】上海交通大学96年第十题（15') 

【解答】intravers(root:bitree)
finished:=false;t:=root;
while not finished do
【
while t↑.ltag=0 do t:=t↑.lch // 左孩子不空
write(t↑.data); // 访问左孩子
if t↑.rtag=1 then 
【t:=t↑.rch;{后继结点}
write(t↑.data);{访问当前根结点}
t:=t↑.rch{访问当前根结点的右孩子}
】
else 
t:=t↑.rch; // 右孩子不空