ghost79

二叉树类的定义和实现

C家家 — Sun, 27 Sep 2009 22:22:00 GMT

/////////////////////////////////////////
//   BinaryTree.h

#ifndef _BINARYTREE_H
#define _BINARYTREE_H

typedef char TElemType;

enum Status {
    ERROR,
    OK
};

typedef struct BiTNode {
    TElemType data;            //数据域
    BiTNode *lchild, *rchild;        //左子树右子树指针

    BiTNode() { lchild = NULL; rchild = NULL; }        //构造空树
    BiTNode( TElemType e ) { data = e; lchild = NULL; rchild = NULL; }    //构造只有根结点的树
    BiTNode( TElemType e, BiTNode *lptr, BiTNode *rptr );    //将两棵子树森林转为树

    bool operator == ( BiTNode &root );        //判断两棵树是否相等

    void Release();        //释放空间
}BiTNode, *BiTree;

class BinaryTree {
private:
    BiTree m_pRoot;        //树根

    BiTNode *CreateBiTree( const char *PreOrderStr, int &pos, const TElemType empty );
    BiTNode *CopyTree( const BiTree &T );

public:
    BinaryTree() { m_pRoot = NULL; }
    BinaryTree( const char *PreOrderStr, const TElemType empty );        //根据先序序列建树
    BinaryTree( BinaryTree &T );    //复制二叉树
    ~BinaryTree();

    bool operator == ( BinaryTree &T );    //判断两棵树是否相等

    Status Clear();        //清为空树
    inline bool IsEmpty() { return m_pRoot == 0; };        //判空
    int GetDepth( BiTree T );        //求树的深度
    inline BiTree &GetRoot() { return m_pRoot; };    //求树根
    inline TElemType GetValue( BiTNode *e ) { return e->data; };    //求结点e的值
    inline void SetValue( BiTNode *e, TElemType value ) { e->data = value; };    //给结点e赋值
    BiTNode *GetParent( BiTNode *e );    //求结点e的双亲
    BiTNode *GetLeftChild( BiTNode *e );    //求结点e的左孩子
    BiTNode *GetRightChild( BiTNode *e );    //求结点e的右孩子
    BiTNode *GetLeftSibling( BiTNode *e );    //求结点e的左兄弟
    BiTNode *GetRightSibling( BiTNode *e );    //求结点e的右兄弟

    Status PreOrderTraverse( BiTree &T, Status ( *Visit )( TElemType e ) );    //先序遍历
    Status InOrderTraverse( BiTree &T, Status ( *Visit )( TElemType e ) );        //中序遍历
    Status PostOrderTraverse( BiTree &T, Status ( *Visit )( TElemType e ) );    //后序遍历

    int CountLeaf( BiTree &T );        //统计二叉树上叶子结点的个数
};

#endif

////////////////////////////////////////////////////////////////////////
//  BinaryTree.cpp

#include <iostream>
#include "BinaryTree.h"

using namespace std;

//////////////////////////////////////////////////////////////////////
// BiTNode

BiTNode::BiTNode( TElemType e, BiTNode *lptr, BiTNode *rptr )
{
    data = e;
    lchild = lptr;
    rchild = rptr;
}

void BiTNode::Release()
{
    if( lchild ) lchild->Release();
    if( rchild) rchild->Release();
    delete this;
}

bool BiTNode::operator == ( BiTNode &root )
{
    if( !this && !&root ) return true;
    if( ( !this && &root ) || ( this && !&root ) ) return false;
    if( data != root.data ) return false;
    return *this->lchild == *root.lchild && *this->rchild == *root.rchild;
}

///////////////////////////////////////////////////////////////////////
// BinaryTree

BiTNode *BinaryTree::CreateBiTree( const TElemType *PreOrderStr, int &pos, const TElemType empty )
{
    if( pos >= int( strlen( PreOrderStr ) ) ) return NULL;

    BiTNode *T;
    if( PreOrderStr[ ++ pos ] == empty )
        T = NULL;
    else
    {
        if( !( T = new BiTNode( PreOrderStr[ pos ] ) ) ) exit( 1 );
        T->lchild = CreateBiTree( PreOrderStr, pos, empty );
        T->rchild = CreateBiTree( PreOrderStr, pos, empty );
    }

    return T;
}

BinaryTree::BinaryTree( const TElemType *PreOrderStr, const TElemType empty )
{
    int pos = -1;
    m_pRoot = CreateBiTree( PreOrderStr, pos, empty );
}

BiTNode *BinaryTree::CopyTree( const BiTree &T )
{
    if( T )
    {
        BiTNode *lptr = CopyTree( T->lchild );
        BiTNode *rptr = CopyTree( T->rchild );
        return new BiTNode( T->data, lptr, rptr );
    }
    else
        return NULL;
}

BinaryTree::BinaryTree ( BinaryTree &T )
{
    m_pRoot = CopyTree( T.GetRoot() );
}

BinaryTree::~BinaryTree()
{
    if( m_pRoot ) m_pRoot->Release();
}

bool BinaryTree::operator == ( BinaryTree &T )
{
    return ( *m_pRoot ) == *T.GetRoot();
}

int BinaryTree::GetDepth( BiTree T )
{
    return T ? 1 + max( GetDepth( T->lchild ), GetDepth( T->rchild ) ) : 0;
}

Status BinaryTree::PreOrderTraverse( BiTree &T, Status( *Visit )( TElemType e ) )
{
    if( T )
    {
        Visit( T->data );
        PreOrderTraverse( T->lchild, Visit );
        PreOrderTraverse( T->rchild, Visit );
    }

    return OK;
}

Status BinaryTree::InOrderTraverse( BiTree &T, Status( *Visit )( TElemType e ) )
{
    if( T )
    {
        InOrderTraverse( T->lchild, Visit );
        Visit( T->data );
        InOrderTraverse( T->rchild, Visit );
    }

    return OK;
}

Status BinaryTree::PostOrderTraverse( BiTree &T, Status( *Visit )( TElemType e ) )
{
    if( T )
    {
        PostOrderTraverse( T->lchild, Visit );
        PostOrderTraverse( T->rchild, Visit );
        Visit( T->data );
    }

    return OK;
}

Status BinaryTree::Clear()
{
    if( m_pRoot ) m_pRoot->Release();

    return OK;
}

int BinaryTree::CountLeaf( BiTree &T )
{
    return T ? ( !T->lchild && !T->rchild ) + CountLeaf( T->lchild ) + CountLeaf( T->rchild ) : 0;
}

等比数列公式及推导

C家家 — Fri, 18 Sep 2009 03:35:00 GMT

公比为q，第一项为a1，则第n项an=a1*q^(n-1)，第n+1项a(n+1)=a1*q^n。

前n项之和sn=a1+a2+……+an。

q*sn=a2+a3+a4+……+a(n+1)。

q*sn-sn=a(n+1)-a1=a1*q^n-a1。

(q-1)*sn=a1*(q^n-1)->sn=a1(q^n-1)/(q-1)。

或者表示为sn=a1*(1-q^n)/(1-q)。

递归版二分查找

C家家 — Sat, 12 Sep 2009 03:55:00 GMT

int a[ 100 ], y;
int Search( int left, int right )
{
    if( left > right )
        return -1;
    else
    {
        int mid = ( left + right ) / 2;
        if( a[ mid ] == y )
            return mid;
        else if( a[ mid ] > y )
            return Search( left, mid - 1 );
        else
            return Search( mid + 1, right );
    }
}

合并排序之C++实现

C家家 — Thu, 10 Sep 2009 02:57:00 GMT

void merge( int *A, int p, int q, int r )
{
    int n1 = q - p + 1,
        n2 = r - q,
        *L = new int[ n1 + 1 ],
        *R = new int[ n2 + 1 ];

    for( int k = 0; k < n1; k ++ ) L[ k ] = A[ p + k ];
    for( int k = 0; k < n2; k ++ ) R[ k ] = A[ q + k + 1 ];
    L[ n1 ] = 2147483647, R[ n2 ] = 2147483647;

    int i = 0, j = 0;
    for( int k = 0; k < r - p + 1; k ++ )
        if( L[ i ] <= R[ j ] )
        {
            A[ p + k ] = L[ i ];
            i ++;
        }
        else
        {
            A[ p + k ] = R[ j ];
            j ++;
        }

    delete []L;
    delete []R;
}

void merge_sort( int *A, int p, int r )
{
    if( p < r )
    {
        int q = ( p + r ) / 2;
        merge_sort( A, p, q );
        merge_sort( A, q + 1, r );
        merge( A, p, q, r );
    }
}

约瑟夫问题的数组实现

C家家 — Thu, 09 Apr 2009 05:18:00 GMT

[问题描述]

有N个人，其编号分别为1－N。这N个人按顺序排成一个圈。现在给定一个正整数M，从第一个人开始依次报数，数到M的人出列，然后又从下一个人开始又从1开始依次报数，数到M的人又出列．．．如此循环，直到最后一个人出列为止。

[输入]

输入只有一行，包括2个整数N，M。之间用一个空格分开。

[输出]

输出只有一行，包括N个整数。

[示例]

输入：
8 5

输出：
5 2 8 7 1 4 6 3

[问题解答]

#include <iostream>

using namespace std;

int main( void )
{
    int n, m;
    cin >> n >> m;

    int *p = new int[ n ];
    for( int i = 0; i < n; i++ ) p[ i ] = i + 1;

    int outPos = 0;
    for( int totalPerson = n; totalPerson > 0; totalPerson-- )
    {
        outPos = ( outPos +  m - 1 ) % totalPerson ;
        cout << p[ outPos ] << " ";

        for( int j = outPos; j < totalPerson; j++ ) p[ j ] = p[ j + 1 ];
    }

    delete []p;
    system( "PAUSE" );
    return 0;
}

用筛法求2-n之间的所有素数

C家家 — Thu, 09 Apr 2009 05:16:00 GMT

[问题描述]

用筛法求2-100之间所有的素数可以这样做，将2的倍数但不包括2都划掉，再将3的倍数但不包括3全部划掉，然后是5的，7的但不包括5、7全部划掉，最后剩下的就都是素数。

[输入]

只有一行，即整数n

[输出]

2-n的所有素数

[示例]

输入：
11
输出：
2 3 5 7 11

[问题解答]

#include <iostream>
#include <math.h>

using namespace std;

int main( void )
{
    int n;
    cin >> n;
    int *p = new int[ n + 1 ];
    for( int i = 2; i <= n; i++ ) p[ i ] = i;

    int z = 2, i;
    while( z * z <=  n ) {
        i = z * 2;
        while( i <= n ) {
            p[ i ] = 0;
            i = i + z;
        }

        do z++; while( !p[ z ] );
    }

    for( int i = 2; i <= n; i++ )
        if( p[ i ] ) cout << i << " ";

    delete []p;

    system( "PAUSE" );
    return 0;
}

计算N的阶乘

C家家 — Thu, 09 Apr 2009 05:15:00 GMT

N可以很大，阶乘的结果位数在10000以内的都可以算出，如果想再多一些，可以修改“const unsigned long MAX=10000;”中MAX的值。

附源代码：

#include <iostream>

using namespace std;

const unsigned long MAX=10000;

int main( int argc, char *argv[] )
{
   char a[MAX];
   memset(a,0,MAX);
   a[0]=1;
   int N,len=1;

   cin>>N;

   int num;
   for(int i=2;i<=N;i++)
   {
        num=0;
        for(int j=0;j<len;j++)
       {
           num+=i*a[j];
           a[j]=num%10;
           num/=10;
        }

        while(num) { a[len++]=num%10; num/=10; }
     }

     while(!a[len]) len--;

     for(int i=len;i>=0;i--) printf("%d",a[i]);

     system("PAUSE");
}

N阶奇数幻方题解

C家家 — Thu, 09 Apr 2009 05:14:00 GMT

幻方指在N*N的方阵中，将1~N*N个数放入N*N个格子，使横、竖、斜的和都相等。奇数幻方指N为奇数。如3*3幻方其中的一个解是：
8 1 6
3 5 7
4 9 2

5*5幻方其中的一个解是：
17 24   1    8  15
23 5    7   14 16
4 6  13 20 22
10 12 19 21   3
11 18 25   2   9

这种填法总的规则是“非右上则下”。

附源代码如下：

#include <iostream>

#define CELL( y, x ) t[ ( y ) * n + ( x ) ]

using namespace std;

int main( void )
{
    int n;
    cin >> n;

    unsigned int *t = new unsigned int[ n * n ];

    int i = 0, j = ( n - 1 ) / 2;

    for( int k = 1; k <= n * n; k++ )
    {
        CELL( i, j ) = k;
        if( !( k % n ) )
            i++;
        else
        {
            i--;
            j++;
        }

        if( i == -1 ) i = n - 1;
        if( j == n ) j = 0;
    }

    for( int i = 0; i < n; i++ )
    {
        for( int j = 0; j < n; j++ ) printf( "%-4d", CELL( i, j ) );
        printf( "\n" );
    }

    delete []t;

    system("PAUSE");
    return 0;
}

用计算机来计算圆周率

C家家 — Thu, 09 Apr 2009 05:11:00 GMT

　　目前PC机上流行的最快的圆周率计算程序是PiFast。它除了计算圆周率，还可以计算e和sqrt(2)。PiFast可以利用磁盘缓存，突破物理内存的限制进行超高精度的计算，最高计算位数可达240亿位，并提供基于Fabrice Bellard公式的验算功能。
最高记录：12,884,901,372位
时间：2000年10月10日
记录创造者：Shigeru Kondo
所用程序：PiFast ver3.3
机器配置：Pentium III 1G, 1792M RAM，WindowsNT4.0，40GBx2(IDE,FastTrak66)
计算时间：1,884,375秒 (21.8天)
验算时间：29小时

·G++编译器中的运算程序微机ＷindowsXP中Dev-cpp中的运算程序（30000位）（C++）

#include <iostream>
#include <fstream>

#define N 30010

using namespace std;

void mult (int *a,int b,int *s)
{
    for (int i=N,c=0;i>=0;i--)
    {
        int y=(*(a+i))*b+c;
        c=y/10;
        *(s+i)=y%10;
    }
}

void divi (int *a,int b,int *s)
{
    for (int i=0,c=0;i<=N;i++)
    {
        int y=(*(a+i))+c*10;
        c=y%b;
        *(s+i)=y/b;
    }
}

void incr(int *a,int *b,int *s)
{
    for (int i=N,c=0;i>=0;i--)
    {
        int y=(*(a+i))+(*(b+i))+c;
        c=y/10;
        *(s+i)=y%10;
    }
}

bool eqs(int *a,int *b)
{
    int i=0;
    while (((*(a+i))==(*(b+i)))&&(i<=N)) i++;
    return i>N;
}

int main(int argc, char *argv[])
{
    int lpi[N+1],lls[N+1],lsl[N+1],lp[N+1];
    int *pi=lpi,*ls=lls,*sl=lsl,*p=lp;
    for (int i=0;i<=N;i++)*(pi+i)=*(ls+i)=*(sl+i)=*(p+i)=0;
    memset(pi,0,sizeof(pi));
    memset(ls,0,sizeof(ls));
    memset(sl,0,sizeof(sl));
    memset(p,0,sizeof(p));
    *pi=*ls=*sl=1;
    for (int i=1;true;i++)
    {
        mult(ls,i,sl);
        divi(sl,2*i+1,ls);
        incr(pi,ls,p);
        if (eqs(pi,p)) break;
        int *t;
        t=p;
        p=pi;
        pi=t;
        if (i%50==0) cout << i << "   ";
    }
    cout << endl;
    mult(p,2,pi);
    ofstream fout("pi.txt");
    fout << *pi << ".";
    for (int i=1;i<=N;i++)
    {
        fout << *(pi+i);
        if (i%10==0) fout << " ";
        if (i%80==0) fout << endl;
    }
    return 0;
}

注：①运行时会有数据弹出，那是无关紧要的，只为了加快了感觉速度；
②最后的txt文本里有30010位，其中最后10位可能是错的。

经典递归问题——汉诺塔

C家家 — Thu, 09 Apr 2009 02:14:00 GMT

汉诺塔（又称河内塔）问题是印度的一个古老的传说。开天辟地的神勃拉玛在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面。面对庞大的数字(移动圆片的次数)18446744073709551615，看来，众僧们耗尽毕生精力也不可能完成金片的移动。后来，这个传说就演变为汉诺塔游戏:
　　1.有三根杆子A,B,C。A杆上有若干碟子
　　2.每次移动一块碟子,小的只能叠在大的上面
　　3.把所有碟子从A杆全部移到C杆上
　　经过研究发现，汉诺塔的破解很简单，就是按照移动规则向一个方向移动金片：
　　如3阶汉诺塔的移动：A→C,A→B,C→B,A→C,B→A,B→C,A→C
　　此外，汉诺塔问题也是程序设计中的经典递归问题。
　　算法思路：
　　1.如果只有一个金片，则把该金片从源移动到目标棒，结束。
　　2.如果有n个金片，则把前n-1个金片移动到辅助的棒，然后把自己移动到目标棒，最后再把前n-1个移动到目标棒.

　　以下是程序实现：（Dec-C++ 4.9.9.2）

#include <iostream>

using namespace std;

unsigned long int k=0;

void Move(int n,char a,char c,char b)
{
     if(n==0) return;
     Move(n-1,a,b,c);
     k=k+1;
     cout<<k<<":from "<<a<<" to "<<c<<"\n";
     Move(n-1,b,c,a);
}

int main( void )
{
    cout<<"请输入盘子数：";
    int n;
    cin>>n;
    Move(n,'A','C','B');

    system("PAUSE");
    return 0;
}