几种算法

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

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

　　【解答】

　　#inlcude

　　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.

");return;}

　　while(i!=1&&j!=1){

　　if(i

　　else if(j

　　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].

",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->dataright->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

　　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

　　if(L.r[i].keyL.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

　　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<

　　}

　　}

　　};

　　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; // 右孩子不空