c++常考算法知识点汇总

前言：写这篇博客完全是给自己当做笔记用的，考虑到自己的c++基础不是很踏实，只在大一学了一学期，c++的面向对象等更深的知识也一直没去学。就是想当遇到一些比较小的知识，切不值得用一整篇

博客去记述的时候，可以考虑到都汇总在这，时不时回来复习一下也挺好。总之，这篇博客可能会不断更新，emmm，内容上也完全是准对我啦（可能更多都是算法上的知识点），大家如果看到了也别吐槽内容太乱太杂或太基础，哈哈。

1三角函数，反三角函数，求夹角

C++中cos,sin,asin,acos这些三角函数操作的是弧度（实数，非复数）,而非角度,你需要把角度转化为弧度.

 弧度=角度*Pi/180;

对于两条边的夹角θ=acos(v1⋅v2/||v1||||v2||)，注意θ是弧度值。

demo如下

#include<bits/stdc++.h>
using namespace std;
struct Point{
 double x;
 double y;
};
double PI=3.1415926;
double Long=0;
double computeLength(Point p1,Point p2)
{
    double l=sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
    return l;
}
//求两条边的夹角大小
double jiaoDu(Point A,Point B,Point C)
{
    double BA=computeLength(A,B);
    double BC=computeLength(B,C);
    double X=(A.x-B.x)*(C.x-B.x)+(A.y-B.y)*(C.y-B.y);
    double X1=X/BA*BC;//角度变弧度
    return acos(X1)*180/PI;
}
//求弧长
double huChang(double r,double jiaodu){
    double huDu=jiaodu*3.1415926/180;
    return huDu*r;
}
int main()
{
    int n=3;
    cout << "请输入三个点的坐标" << endl;
    Point point[101];
    for(int i=1;i<=n;i++){
        cin >> point[i].x;
        cin >> point[i].y;
    }

    cout << "向量BA的长度为" <<  setiosflags(ios::fixed) << setprecision(2)<<computeLength(point[1],point[2]) << endl;
    cout << "向量BC的长度为" <<  setiosflags(ios::fixed) << setprecision(2)<<computeLength(point[2],point[3]) << endl;
    double a=jiaoDu(point[1],point[2],point[3]);
    cout << "角ABC的大小为为" << setiosflags(ios::fixed) << setprecision(2)<<jiaoDu(point[1],point[2],point[3]) << endl;
    return 0;
}

2malloc和new的区别

1,malloc与free是C++/C语言的标准库函数，new/delete是C++的运算符。它们都可用于申请动态内存和释放内存。
2,对于非内部数据类型的对象而言，光用maloc/free无法满足动态对象的要求。对象在创建的同时要自动执行构造函数，对象在消亡之前要自动执行析构函数。由于malloc/free是库函数而不是运算符，不在编译器控制权限之内，不能够把执行构造函数和析构函数的任务强加于malloc/free。
3,因此C++语言需要一个能完成动态内存分配和初始化工作的运算符new，以一个能完成清理与释放内存工作的运算符delete。注意new/delete不是库函数。
4,C++程序经常要调用C函数，而C程序只能用malloc/free管理动态内存。
5、new可以认为是malloc加构造函数的执行。new出来的指针是直接带类型信息的。而malloc返回的都是void指针。

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int *p=new int[10];
    p[0]=1;
    delete p;
    p=NULL;
    
    int *p1=(int *)malloc(sizeof(int)*10);
    p1[0]=2;
    cout << p1[0] << endl;
    free(p1);
    
    return 0;
}

3字符串和数组的几个小知识

 string str="hello";
    char arr[30];
    strcpy(arr,str.c_str());//字符串变字符数组 
    
    strlen(arr1)//求字符数组的长度
    str.length();//求字符串的长度
    sizeof(arr2)/sizeof(int);//求整数数组的长度 
    
    *max_element(array,array+n)//求数组里面的最大值是谁，不改变数组 
    *min_element(array,array+n)//求数组里面的最小值是谁，不改变数组 
    
    reverse(str.begin(),str.end());//反转字符串 
    
    reverse(arr,arr+n);
    puts(arr);//反转数组
    
    srand((unsigned)time(NULL));
    rand()%10;//产生随机数、
    
    bool cmp(int a,int b){
        return a>b;
    } 
    sort(a,a+n,cmp)//从大到大小排序
    
    void func(int **array,int m,int n){} <==> void func(int array[][],int m,int n){}

4两种全排列算法（排列的结果的顺序不同）

#include <bits/stdc++.h>
using namespace std;
int num1=0;
int num2=0; 
void Swap(int &a,int &b){
    int temp;
    temp=b;
    b=a;
    a=temp;
}

void  perm(int array[],int k,int m){
    if(k==m){
        for(int i=0;i<=m;i++){
            cout << array[i] << " ";
        }
        cout << endl;
        num1++;
    }
    else{
        for(int i=k;i<=m;i++){
            Swap(array[k],array[i]);
            perm(array,k+1,m);
            Swap(array[k],array[i]);
        }
    }
}

int main()
{
    int array[10]={3,2,1,5,6,7,8,9,4,0};
    sort(array,array+sizeof(array)/sizeof(int));
    perm(array,0,4);//方法一：自定义排序函数 
    cout << "0~4的全排列总有" << num1 << "种"  << endl;
   cout << "----------------------------------------------------------------" << endl;
   do{
       for(int i=0;i<5;i++){
           cout << array[i] << " ";
       }
       num2++;
       cout << endl;
   }while(next_permutation(array,array+5));//方法二：使用next_permutation（array,array+n）；实现排序 
     cout << "0~4的全排列总有" << num2 << "种"  << endl;
    return 0;
}

5二分查找

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int binarysearch(int array[],int x,int n){
 4     int left=0;
 5     int right=n-1;
 6     while(left<right){
 7         int middle=(left+right)/2;
 8         if(array[middle]==x) return middle;
 9         if(array[middle]<x) left=middle+1;
10         if(array[middle]>x) right=middle-1;
11     }
12    return -1;
13 } 
14 int main()
15 {
16     int array[10]={3,2,1,5,6,7,8,9,4,0};
17     sort(array,array+10);
18     int a=binarysearch(array,10,sizeof(array)/sizeof(int));
19     if(a==-1) cout << "没找到" << endl;
20     else   cout << "找到该数字,在顺序排列后的数组的下标为" <<  a<<  endl;
21     return 0;
22 }

 6合并排序

template<class Type>
void MergeSort(Type a[],int left,int right)
{
    if(left<right){//至少有两个元素 
        int i=(left+right)/2;//取中点 
        MergeSort(a,left,i);
        MergeSort(a,i+1,right);
        Merge(a,b,left,i,right);//合并到数组b 
        Copy(a,b,left,right);//复制回数组a 
    } 
}

#include <bits/stdc++.h>

using namespace std;
template<class Type>
int Merge(Type a[],Type c[],int l,int m,int r){
        int i=l;
        int j=m+1;
        int k=0;
        while((i<=m) && (j<=r)){
            if(a[i]<=a[j]) c[k++]=a[i++];
            if(a[i]>a[j]) c[k++]=a[j++];

        }
        if(i<=m)
        {
            for(int q=i;q<=m;q++){
                c[k++]=a[q];
            }
        }
        if(j<=r){
           for(int q=j;q<=r;q++){
                c[k++]=a[q];
            }
        }
        return 1;
}
template<class Type>
int MergeSort(Type a[],Type b[],int left,int right){
    if(left<right){
        int i=(left+right)/2;
        MergeSort(a,b,left,i);
        MergeSort(a,b,i+1,right);
        Merge(a,b,left,i,right);
    }
}
int main()
{
    int a[12]={1,3,5,7,9,2,4,6,8,10,12,14};
    int b[12];
    MergeSort(a,b,0,11);
    for(int i=0;i<=11;i++){
        cout << b[i] << " ";
    }
    return 0;
}

7快排

#include <bits/stdc++.h>
using namespace std;
void Swap(int &a,int &b)
{
    int temp;
    temp=a;
    a=b;
    b=temp;
}

int Partition(int a[],int p,int r)
{
    int i=p;
    int j=r+1;
    int x=a[p];
    while(true){
        while(a[++i] < x && i<r);
        while(a[--j] > x);
        if(i>=j) break;
        Swap(a[i],a[j]);
    }
    a[p]=a[j];
    a[j]=x;
    return j;
}
void QuickSort(int a[],int p,int r)
{
    if(p<r){
        int q=Partition(a,p,r);
        QuickSort(a,p,q-1);
        QuickSort(a,q+1,r);
    }
 } 
int main()
{
    int array[10]={0,5,2,7,9,1,3,4,6,8};
    QuickSort(array,0,9);
    for(int i=0;i<10;i++){
        cout << array[i]  << " ";
    }
    return 0;
}

 8半数集

long f(int n){
    long sum=1;
    if(a[n]>0) return a[n];

        for(int i=1;i<=n/2;i++){
            sum += f(i);
        }
        a[n]=sum;
        return sum;
}

9集合划分

int f(int n,int m)
{
    if(n==1) return 1;//只有一个集合
    if(m==m) return 1;//每个元素一个集合
    else{
        return m*f(n-1,m)+f(n-1,m+1);//向n-1个元素划分的m个集合里添加一个新元素，有m*f（n-1,m）种，
    }                                    //向n-1个元素划分的m个集合里添加一个独立元素，有f（n-1,m+1）种，
        
}

10整数因子分解问题

void f(n)
{
    if(n==1) num+=1;
    for(int i=2;i<=n;i++){
        if(n%2==0) f(n%i);
    }
}

 11利用二分法求最大值

#include<bits/stdc++.h>
using namespace std;
int getMax(int array[],int begin,int end)
{
    if(begin==end) return array[end];
    int mid=(begin+end)/2;
    int max1=getMax(array,begin,mid);
    int max2=getMax(array,mid+1,end);
    return max1>max2?max1:max2;
}
int main()
{
    int array[15]={18,1,3,5,7,9,7,5,3,4,11,44,5,3};
    cout << getMax(array,0,13);
    return 0;
}

12二叉树遍历（递归）

typedef struct node                           //定义二叉树的结点
{    int data;          //结点的数据
    struct node*lChild,*rChild;    //结点左右孩子
}Node;
void inOrder(Node *root)    //中序遍历
{
    if(root!=0)              //如果根节点不为0
    {
          inOrder(root->lChild);       //指向左孩子
          printf("%d ",root->data);   //打印当前结点
          inOrder(root->rChild);      //指向右孩子
    }
}

 13最大字段和

 int MaxSum(int n,int a[])
      {
          int sum = 0;
          int b = 0;
          for(int i = 1; i <= n; i++)
          {
              if(b > 0)
                  b += a[i];
              else
                  b = a[i];
              if(b > sum)
                  sum = b;
          }
          return sum;
      }

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~不断更新中。