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=;

 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)*/PI;

 }

 //求弧长

 double huChang(double r,double jiaodu){

     double huDu=jiaodu*3.1415926/;

     return huDu*r;

 }

 int main()

 {

     int n=;

     cout << "请输入三个点的坐标" << endl;

     Point point[];

     for(int i=;i<=n;i++){

         cin >> point[i].x;

         cin >> point[i].y;

     }

     cout << "向量BA的长度为" <<  setiosflags(ios::fixed) << setprecision()<<computeLength(point[],point[]) << endl;

     cout << "向量BC的长度为" <<  setiosflags(ios::fixed) << setprecision()<<computeLength(point[],point[]) << endl;

     double a=jiaoDu(point[],point[],point[]);

     cout << "角ABC的大小为为" << setiosflags(ios::fixed) << setprecision()<<jiaoDu(point[],point[],point[]) << endl;

     return ;

 }

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[];

     p[]=;

     delete p;

     p=NULL;

     int *p1=(int *)malloc(sizeof(int)*);

     p1[]=;

     cout << p1[] << endl;

     free(p1);

     return ;

 }

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

  string str="hello";

     char arr[];

     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()%;//产生随机数、

     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=;

 int num2=;

 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=;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+,m);

             Swap(array[k],array[i]);

         }

     }

 }

 int main()

 {

     int array[]={,,,,,,,,,};

     sort(array,array+sizeof(array)/sizeof(int));

     perm(array,,);//方法一：自定义排序函数

     cout << "0~4的全排列总有" << num1 << "种"  << endl;

    cout << "----------------------------------------------------------------" << endl;

    do{

        for(int i=;i<;i++){

            cout << array[i] << " ";

        }

        num2++;

        cout << endl;

    }while(next_permutation(array,array+));//方法二：使用next_permutation（array,array+n）；实现排序

      cout << "0~4的全排列总有" << num2 << "种"  << endl;

     return ;

 }

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)/;//取中点

         MergeSort(a,left,i);

         MergeSort(a,i+,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+;

         int k=;

         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 ;

 }

 template<class Type>

 int MergeSort(Type a[],Type b[],int left,int right){

     if(left<right){

         int i=(left+right)/;

         MergeSort(a,b,left,i);

         MergeSort(a,b,i+,right);

         Merge(a,b,left,i,right);

     }

 }

 int main()

 {

     int a[]={,,,,,,,,,,,};

     int b[];

     MergeSort(a,b,,);

     for(int i=;i<=;i++){

         cout << b[i] << " ";

     }

     return ;

 }

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+;

     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-);

         QuickSort(a,q+,r);

     }

  }

 int main()

 {

     int array[]={,,,,,,,,,};

     QuickSort(array,,);

     for(int i=;i<;i++){

         cout << array[i]  << " ";

     }

     return ;

 }

8半数集

 long f(int n){

     long sum=;

     if(a[n]>) return a[n];

         for(int i=;i<=n/;i++){

             sum += f(i);

         }

         a[n]=sum;

         return sum;

 }

9集合划分

 int f(int n,int m)

 {

     if(n==) return ;//只有一个集合

     if(m==m) return ;//每个元素一个集合

     else{

         return m*f(n-,m)+f(n-,m+);//向n-1个元素划分的m个集合里添加一个新元素，有m*f（n-1,m）种，

     }                                    //向n-1个元素划分的m个集合里添加一个独立元素，有f（n-1,m+1）种，

 }

10整数因子分解问题

 void f(n)

 {

     if(n==) num+=;

     for(int i=;i<=n;i++){

         if(n%==) 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)/;

     int max1=getMax(array,begin,mid);

     int max2=getMax(array,mid+,end);

     return max1>max2?max1:max2;

 }

 int main()

 {

     int array[]={,,,,,,,,,,,,,};

     cout << getMax(array,,);

     return ;

 }

12二叉树遍历（递归）

 typedef struct node                           //定义二叉树的结点

 {    int data;          //结点的数据

     struct node*lChild,*rChild;    //结点左右孩子

 }Node;

 void inOrder(Node *root)    //中序遍历

 {

     if(root!=)              //如果根节点不为0

     {

           inOrder(root->lChild);       //指向左孩子

           printf("%d ",root->data);   //打印当前结点

           inOrder(root->rChild);      //指向右孩子

     }

 }

13最大字段和

  int MaxSum(int n,int a[])

       {

           int sum = ;

           int b = ;

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

           {

               if(b > )

                   b += a[i];

               else

                   b = a[i];

               if(b > sum)

                   sum = b;

           }

           return sum;

       }

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

巴特西

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

最新文章

热门文章