常用算法模板库(C++)_1

排序算法

冒泡排序

/*

函数功能：对数组中的某一部分进行冒泡排序。

函数原形：void BubSort(DataType a[], int l, int r, bool Up=true);

参数：

DataType a[]：欲排序的数组；

int l：有序序列在数组中的起始位置；

int r：有序序列在数组中的结束位置；

bool Up：true按升序排列，false按降序排列。

返回值：无。

备注：无。

*/

template

void BubSort(DataType a[], int l, int r, bool Up=true)

{

    int i,j;

    DataType k;

 

    if (Up)

    {

        for (i=l;i<=r-1;i++)

            for (j=r;j>=i+1;j--)

                if (a[j-1]>a[j])

                {

                    k=a[j-1];

                    a[j-1]=a[j];

                    a[j]=k;

                }

    }

    else

        for (i=l;i<=r-1;i++)

            for (j=r;j>=i+1;j--)

                if (a[j-1]

                {

                    k=a[j-1];

                    a[j-1]=a[j];

                    a[j]=k;

                }

}

选择排序

/*

函数功能：对数组中的某一部分进行选择排序。

函数原形：void SelectSort(DataType a[], int l, int r, bool Up=true);

参数：

DataType a[]：欲排序的数组；

int l：有序序列在数组中的起始位置；

int r：有序序列在数组中的结束位置；

bool Up：true按升序排列，false按降序排列。

返回值：无。

备注：无。

*/

/*普通版*/

template

void SelectSort(DataType a[], int l, int r, bool Up=true)

{

    int i,j;

    DataType k;

 

    if (Up)

    {

        for (i=l;i<=r-1;i++)

            for (j=i+1;j<=r;j++)

                if (a[i]>a[j])

                {

                    k=a[i];

                    a[i]=a[j];

                    a[j]=k;

                }

    }

    else

        for (i=l;i<=r-1;i++)

            for (j=i+1;j<=r;j++)

                if (a[i]

                {

                    k=a[i];

                    a[i]=a[j];

                    a[j]=k;

                }

}

/*优化版*/

template

void SelectSort(DataType a[], int l, int r, bool Up=true)

{

    int i,j,k;

    DataType x;

   

    if (Up)

    {

        for (i=l;i<=r-1;i++)

        {

            k=i;

            for (j=i+1;j<=r;j++)

                if (a[j]

            x=a[i];

            a[i]=a[k];

            a[k]=x;

        }

    }

    else

        for (i=l;i<=r-1;i++)

        {

            k=i;

            for (j=i+1;j<=r;j++)

                if (a[j]>a[k]) k=j;

            x=a[i];

            a[i]=a[k];

            a[k]=x;

        }

}

插入排序

/*

函数功能：向有序数组中插如元素，并使插入新元素后仍然有序。

函数原形：void InsertSort(DataType s[], int &Count, DataType x, bool Up=true);

参数：

DataType s[]：欲插入元素的有序序列；

int &Count：有序序列中现有元素个数；

DataType x：欲插入的元素；

bool Up：true按升序排列，false按降序排列。

返回值：无。

备注：无。

*/

template

void InsertSort(DataType s[], int &Count, DataType x, bool Up=true)

{

    int i,k=-1;

 

    if (Up)

    {

        for (i=0;i<=Count-1;i++)

            if (x

            {

                k=i;

                break;

            }

    }

    else

        for (i=0;i<=Count-1;i++)

            if (x>s[i])

            {

                k=i;

                break;

            }

    if (k==-1) s[++Count-1]=x;

    else

    {

        for (i=Count-1;i>=k;i--) s[i+1]=s[i];

        s[k]=x;

        Count++;

    }

}

快速排序

/*

函数功能：对数组中的某一部分进行快速排序。

函数原形：void QuickSort(DataType a[], int l, int r, bool Up=true);

参数：

DataType a[]：欲排序的数组；

int l：有序序列在数组中的起始位置；

int r：有序序列在数组中的结束位置；

bool Up：true按升序排列，false按降序排列。

返回值：无。

备注：无。

*/

template

void QuickSort(DataType a[], int l, int r, bool Up=true)

{

    int i,j;

    DataType Mid,k;

 

    i=l;

    j=r;

    Mid=a[(l+r)/2];

    if (Up)

    {

        do

        {

            while (a[i]

            while (Mid

            if (i<=j)

            {

                k=a[i];

                a[i]=a[j];

                a[j]=k;

                ++i;

                --j;

            }

        } while (i<=j);

    }

    else

        do

        {

            while (a[i]>Mid) ++i;

            while (Mid>a[j]) --j;

            if (i<=j)

            {

                k=a[i];

                a[i]=a[j];

                a[j]=k;

                ++i;

                --j;

            }

        } while (i<=j);

    if (i

    if (l

}

哈希排序

/*

函数功能：对数组中的某一部分进行哈希排序。

函数原形：void QuickSort(DataType a[], int l, int r, bool Up=true);

参数：

DataType a[]：欲排序的数组；

int l：有序序列在数组中的起始位置；

int r：有序序列在数组中的结束位置；

bool Up：true按升序排列，false按降序排列。

返回值：无。

备注：只能对0~32767范围内的整数排序。

*/

void HashSort(int a[], int l, int r, bool Up=true)

{

    int i,j,k,Hash[32767]={0};

 

    for (i=l;i<=r;i++) Hash[a[i]]++;

    k=l;

    if (Up)

    {

        for (i=0;i<=32767-1;i++)

        {

            for (j=1;j<=Hash[i];j++) a[k++]=i;

            if (k>r) break;

        }

    }

    else

        for (i=32767-1;i>=0;i--)

        {

            for (j=1;j<=Hash[i];j++) a[k++]=i;

            if (k>r) break;

        }

}

数学问题

求最大公约数最小公倍数

/*

函数功能：求两数的最大公约数。

函数原形：int GCD(int m, int n);

参数：

int m, int n：求这两个数的最大公约数。

返回值：int型，m、n的最大公约数。

备注：最小公倍数=m*n/GCD(m,n)。

*/

int GCD(int m, int n)

{

    int Temp,x,y;

   

    x=m;

    y=n;

    Temp=x%y;

    while (Temp!=0)

    {

        x=y;

        y=Temp;

        Temp=x%y;

    }

    return y;

}

求素数

2.2.1 穷举法

/*

函数功能：判断一个数是否是素数。

函数原形：bool Prime(int x);

参数：

int x：欲判断的数。

返回值：bool型，返回true表示x是素数，返回false表示x不是素数。

备注：需包含头文件。

*/

bool Prime(int x)

{

    int i;

 

    x=abs(x);

    if (x<=1) return false;

    for (i=2;i<=int(sqrt(float(x)));i++)

        if (x%i==0) return false;

    return true;

}

2.2.2筛法

/*

函数功能：判断小于等于n的数是否是素数。

函数原形：void Prime(bool Hash[], int n);

参数：

bool Hash[]：最终结果，Hash[i]=true表示i是素数，否则表示i不是素数；

int n：判断范围。

返回值：无。

备注：无。

*/

void Prime(bool Hash[], int n)

{

    int i,k;

   

    Hash[0]=false;

    Hash[1]=false;

    for (i=2;i<=n;i++) Hash[i]=true;

    i=2;

    while (i<=n/2)

    {

        k=i;

        while (k+i<=n)

        {

            k=k+i;

            Hash[k]=false;

        }

        i++;

        while (Hash[i]==false && i

    }

}

排列组合

2.3.1 排列数

/*

函数功能：排列数公式A(m,n)。

函数原形：int A(int m, int n);

参数：

int m, int n：排列数公式的两个参数。

返回值：int 型，排列数。

备注：无。

*/

int A(int m, int n)

{

    int i,Ans;

 

    Ans=1;

    for (i=1;i<=m;i++)

    {

        Ans=Ans*n;

        n--;

    }

    return Ans;

}

2.3.2 组合数

/*

函数功能：组合数公式C(m,n)。

函数原形：int C(int m, int n);

参数：

int m, int n：组合数公式的两个参数。

返回值：int 型，组合数。

备注：无。

*/

int C(int m, int n)

{

    int i,Ans;

 

    Ans=1;

    for (i=1;i<=m;i++)

    {

        Ans=Ans*n;

        n--;

    }

    for (i=2;i<=m;i++) Ans=Ans/i;

    return Ans;

}

2.3.3 全排列算法

/*

函数功能：输出n的全排列。

函数原形：void Arrange(int n);

参数：

int n：全排列元素个数。

返回值：无。

备注：无。

*/

void Swap(int &a, int &b)

{

    int k;

 

    k=a;

    a=b;

    b=k;

}

 

void Inverse(int Num[], int l, int r)

{

    int i,Count;

 

    Count=(r-l+1)/2;

    for (i=1;i<=Count;i++) Swap(Num[l++],Num[r--]);

}

 

void Arrange(int n)

{

    int *Num=new int[n+1];

    char i,x,y;

   

    Num[0]=0;

    for (i=1;i<=n;i++)  //输出原始序列

    {

        Num[i]=i;

        cout<

    }

    cout<<'\n';

    do

    {

        for (i=1;i<=n;i++)

            if (Num[i]>Num[i-1]) x=i;

        for (i=x;i<=n;i++)

            if (Num[i]>Num[x-1]) y=i;

        if (x>1)

        {

            Swap(Num[x-1],Num[y]);  //交换Num[x-1]和Num[y]

            Inverse(Num,x,n);  //对num[x]~num[n]作逆序处理

            for (i=1;i<=n;i++) cout<  //输出当前序列

            cout<<'\n';

        }

    } while(x!=1);

    delete[] Num;

}

2.3.4 从n个数中选m个的组合

/*

函数功能：输出n选m的组合方案。

函数原形：void Combination(int m, int n);

参数：

int m：欲选出的元素个数；

int n：元素总个数。

返回值：无。

备注：无。

*/

void Combination(int m, int n)

{

    int *a=new int[n+1],i,j;

 

    a[0]=1;

    for (i=1;i<=m;i++) a[i]=i;

    while (a[0]==1)

    {

        for (i=1;i<=m;i++) cout<  //输出当前序列

        cout<<'\n';

        j=m;

        while (a[j]==n-m+j && j>0) j--;

        a[j]++;

        for (i=j+1;i<=n;i++) a[i]=a[i-1]+1;

    }

    delete[] a;

}

进制转换

2.4.1 十进制转N进制

/*

函数功能：将一个十进制数转换成一个N进制数。

函数原形：string DecToN(DataType x, int n);

参数：

    DataType x：欲转换的数；

    int n：返回结果的进制。

返回值：string类对象，转换结果。

备注：需包含。

*/

template

string DecToN(DataType x, int n)

{

    string Ans;

    int Count,i,j=0,a[64];

 

    Count=0;

    if (x==0)

    {

        Ans[0]='0';

        Ans[1]='\0';

    }

    else

    {

        while (x>0)

        {

            a[Count++]=x%n;

            x=x/n;

        }

        for (i=Count-1;i>=0;i--)

            if (a[i]<10) Ans.append(1,a[i]+'0');

            else Ans.append(1,a[i]+'A'-10);

    }

    return Ans;

}

2.4.2 N进制转十进制

/*

函数功能：将一个N进制数转换成一个十进制数。

函数原形：long NToDec(string x, int n);

参数：

    string x：欲转换的数；

    int n：被转换数的进制。

返回值：long型，转换结果。

备注：需包含、。

*/

long NToDec(string x, int n)

{

    int a[32],y,Count,i,j;

    long Ans;

 

    Ans=0;

    for (i=0;i<=(int)x.length()-1;i++)

        if ('0'<=x[i] && x[i]<='9') a[i]=x[i]-'0';

        else a[i]=toupper(x[i])-'A'+10;

    Count=0;

    for (i=(int)x.length()-1;i>=0;i--)

    {

        y=1;

        for (j=1;j<=Count;j++) y=y*n;

        Count++;

        Ans=Ans+y*a[i];

    }

    return Ans;

}

查找

二分查找

/*

函数功能：查找指定元素在数组中的位置。

函数原形：int BinarySearch(DataType a[], DataType x, int l, int r);

参数：

    DataType a[]：目标数组；

DataType x：待查找的元素；

int l：数组下标上限；

int r：数组下标下限。

返回值：int型，元素x在数组a中的下标。

备注：无。

*/

template

int BinarySearch(DataType a[], DataType x, int l, int r)

{

    int Mid;

 

    while (l<=r)

    {

        Mid=(l+r)/2;

        if (x==a[Mid]) return Mid;

        else

        {

            if (x

            if (x>a[Mid]) l=Mid+1;

        }

    }

    return -1;

}

栈

栈的定义

template

class StackClass

{

private:

    struct BodyNodeStruct

    {

        DataType Data;

        BodyNodeStruct *Pre,*Next;

    } Bottom,*Top;

 

public:

    StackClass();  //构造函数，创建一个空栈

    bool Empty();  //判断栈是否为空，若为空则返回true，否则返回false

    int Push(DataType Data);  //将Data压栈，如果压栈成功则返回0，否则返回1

    int Pop(DataType &Data);  //弹出栈顶元素，保存在Data中，若栈不为空则返回0，否则返回1

    int GetTop(DataType &Data);  //读取栈顶元素，保存在Data中，若栈不为空则返回0，否则返回1

    int Size();  //返回栈中元素个数

    void Clear();  //清空栈

    ~StackClass();  //析构函数

} ;

 

template

StackClass::StackClass()

{

    Top=&Bottom;

    Top->Pre=NULL;

    Top->Next=NULL;

}

 

template

bool StackClass::Empty()

{

    if (Top==&Bottom) return true;

    else return false;

}

 

template

int StackClass::Push(DataType Data)

{

    BodyNodeStruct *Temp=new BodyNodeStruct;

 

    if (Temp!=NULL)

    {

        Temp->Pre=Top;

        Temp->Next=NULL;

        Top->Next=Temp;

        Top->Data=Data;

        Top=Temp;

        return 0;

    }

    else return 1;

}

 

template

int StackClass::Pop(DataType &Data)

{

    if (!Empty())

    {

        Top=Top->Pre;

        Data=Top->Data;

        delete Top->Next;

        Top->Next=NULL;

        return 0;

    }

    else return 1;

}

 

template

int StackClass::GetTop(DataType &Data)

{

    if (!Empty())

    {

        Data=Top->Pre->Data;

        return 0;

    }

    else return 1;

}

 

template

int StackClass::Size()

{

    BodyNodeStruct *Temp=&Bottom;

    int Count=0;

 

    while (Temp!=Top)

    {

        Count++;

        Temp=Temp->Next;

    }

    return Count;

}

 

template

void StackClass::Clear()

{

    DataType Temp;

 

    while (!Empty()) Pop(Temp);

}

 

template

StackClass::~StackClass()

{

    Clear();

}

表达式求值

/*

函数功能：计算四则运算表达式的值。

函数原形：long Evaluate(string Exp);

参数：

    string Exp：欲求值的四则运算表达式。

返回值：long型，表达式的值。

备注：需包含。

*/

long Evaluate(string Exp)

{

    StackClass Optr;

    StackClass Opnd;

    long a,b,Ans;

    int TempOptr,x,i,Length,Operator[7][7]={{2,2,0,0,0,2,2},{2,2,0,0,0,2,2},{2,2,2,2,0,2,2},{2,2,2,2,0,2,2},{0,0,0,0,0,1,-1},{2,2,2,2,-1,2,2},{0,0,0,0,0,-1,1}};

    char TempOpnd[6];

 

    Optr.Push(6);

    Opnd.Push(0);

    Length=0;

    i=0;

    Optr.GetTop(x);

    while (Exp[i]!='=' || x!=6)

    {

        if (48<=Exp[i] && Exp[i]<=57)

        {

            TempOpnd[Length++]=Exp[i];

            i++;

        }

        else

            if (Exp[i]=='+' || Exp[i]=='-' || Exp[i]=='*' || Exp[i]=='/' || Exp[i]=='(' || Exp[i]==')' || Exp[i]=='=')

            {

                if (Length>0)

                {

                    TempOpnd[Length]='\0';

                    Length=0;

                    Opnd.Push(atoi(TempOpnd));

                }

                switch (Exp[i])

                {

                case '+':

                    TempOptr=0;

                    break;

                case '-':

                    TempOptr=1;

                    break;

                case '*':

                    TempOptr=2;

                    break;

                case '/':

                    TempOptr=3;

                    break;

                case '(':

                    TempOptr=4;

                    break;

                case ')':

                    TempOptr=5;

                    break;

                case '=':

                    TempOptr=6;

                    break;

                }

                Optr.GetTop(x);

                switch (Operator[x][TempOptr])

                {

                case 0:

                    Optr.Push(TempOptr);

                    i++;

                    break;

                case 1:

                    Optr.Pop(x);

                    i++;

                    break;

                case 2:

                    Optr.Pop(TempOptr);

                    Opnd.Pop(b);

                    Opnd.Pop(a);

                    switch (TempOptr)

                    {

                    case 0:

                        Opnd.Push(a+b);

                        break;

                    case 1:

                        Opnd.Push(a-b);

                        break;

                    case 2:

                        Opnd.Push(a*b);

                        break;

                    case 3:

                        Opnd.Push(a/b);

                        break;

                    }

                    break;

                }

            }

        Optr.GetTop(x);

    }

    Opnd.Pop(Ans);

    return Ans;

}

队列

队列的定义

template

class QueueClass

{

private:

    struct BodyNodeStruct

    {

        DataType Data;

        BodyNodeStruct *Pre,*Next;

    } *Front,*Rear;

 

public:

    QueueClass();  //构造函数，构造一个空队列

    bool Empty();  //判断队列是否为空，若为空则返回true，否则返回false

    int Push(DataType Data);  //将Data压入队尾，如果压入成功则返回0，否则返回1

    int Pop(DataType &Data);  //弹出队头元素，保存在Data中，若队列不为空则返回0，否则返回1

    int GetFront(DataType &Data);  //读取队头元素，保存在Data中，若队列不为空则返回0，否则返回1

    int Size();  //返回队列中元素个数

    void Clear();  //清空队列

    ~QueueClass();  //析构函数

} ;

 

template

QueueClass::QueueClass()

{

    Front=new BodyNodeStruct;

    Front->Pre=NULL;

    Front->Next=NULL;

    Rear=Front;

}

 

template

bool QueueClass::Empty()

{

    if (Front==Rear) return true;

    else return false;

}

 

template

int QueueClass::Push(DataType Data)

{

    BodyNodeStruct *Temp=new BodyNodeStruct;

 

    if (Temp!=NULL)

    {

        Temp->Pre=Rear;

        Temp->Next=NULL;

        Rear->Next=Temp;

        Rear->Data=Data;

        Rear=Temp;

        return 0;

    }

    else return 1;

}

 

template

int QueueClass::Pop(DataType &Data)

{

    if (!Empty())

    {

        Data=Front->Data;

        Front=Front->Next;

        delete Front->Pre;

        Front->Pre=NULL;

        return 0;

    }

    else return 1;

}

 

template

int QueueClass::GetFront(DataType &Data)

{

    if (!Empty())

    {

        Data=Front->Data;

        return 0;

    }

    else return 1;

}

 

template

int QueueClass::Size()

{

    BodyNodeStruct *Temp=Front;

    int Count=0;

 

    while (Temp!=Rear)

    {

        Count++;

        Temp=Temp->Next;

    }

    return Count;

}

 

template

void QueueClass::Clear()

{

    DataType Temp;

 

    while (!Empty()) Pop(Temp);

}

 

template

QueueClass::~QueueClass()

{

    Clear();

    delete Front;

}