数据结构是计算机课程中基础中的基础，将其学透彻百利而无一害，可惜自己当年学的时候没好好听，好在现在还不算晚。为了勉励自己以及复习，我将在此更新自己所学的笔记，所用教材为网易云课堂陈越、何钦铭老师所授课的《数据结构》课程。那么，就开始吧！

1.1 什么是数据结构

例1：书架摆书。

小结：解决问题方法的效率和数据的组织方式有关

例2：写程序实现一个函数PrintN,使传入正整数N的参数后，能顺序打印从1到N的全部正整数

结果：输入100000，循环算法跑了一会，递归算法直接挂掉
原因：计算机一般不愿意跑递归，因为对空间占用很恐怖，一旦空间不够便会爆掉。

小结：解决问题方法的效率和空间利用效率有关

例3：

image.png

辣鸡写法：

image.png

标准写法：

image.png

Clock()函数

image.png

若时间太短，就重复多次
自己写的例子：

  #include"stdio.h"
  #include"math.h"
  #include"time.h"

  clock_t start,stop;
  double duration;

  double f1(double x)
  {
    double p=0,i;
    for(i=1;i<100;i++)
    {
        p+=pow(x,i)/i;
    }
    return p+1;
  }
  
  int main()
  {
    double A1;
    double x=1.1;
    double i=100;
    start=clock();
    for(int j=1;j<10000;j++)
    {
        A1=f1(x);
    }
    stop=clock();
    duration=((double)(stop-start)/CLK_TCK/10000);
    printf("A1=%lf\n",A1);
    printf("%lf\n",duration);
    return 0;
  }

小结：解决问题方法的效率，和算法的巧妙程度有关

1.2 什么是算法

image.png

简单地说，f(n)是上界，g(n)为下界，第三种代表上界下界相同.

image.png

实战：

image.png

算法1：

image.png

算法2：

image.png

Ps:优秀的程序员发现时间复杂度为O（N^2）时会想着转换为O（NlogN）

算法3：

image.png

算法4：

image.png

自己写的代码：
#include"stdio.h"
#include"math.h"
#include"time.h"

  clock_t start,stop;
  double duration;
  int MaxSubseqSum1(int A[],int N)
  {
    int ThisSum,MaxSum=0;
    for (int i = 0; i < N; i++) {
      for (int j = i; j < N; j++){
        ThisSum=0;
        for (int k = i; k < j; k++) {
            ThisSum+=A[k];
            if(ThisSum>MaxSum)
            MaxSum=ThisSum;
          }
      }
  }
  return MaxSum;
}

int MaxSubseqSum2(int A[],int N)
{
  int ThisSum,MaxSum=0;
  for (int i = 0; i < N; i++) {
    ThisSum=0;
    for (int j = i; j < N; j++) {
      ThisSum += A[j];
      if(ThisSum>MaxSum)
      MaxSum=ThisSum;
      }
  }
  return MaxSum;
}

int MaxSubseqSum3(int A[],int N)
{
    int ThisSum,MaxSum=0;
    //分而治之
    return MaxSum;
}

int MaxSubseqSum4(int A[],int N)
{
    int ThisSum=0,MaxSum=0;
    int i;
    for (i = 0; i < N; i++) {
        ThisSum += A[i];
        if(ThisSum > MaxSum)
            MaxSum = ThisSum;
        else if ( ThisSum < 0 ) {
            ThisSum = 0;
        }
    }
    return MaxSum;
}

int main()
{
  int A[]={-1,3,-2,4,-6,1,6,-1},MAX=0;
  start=clock();
  for (int i = 0; i < 99999; i++) {
      MAX=MaxSubseqSum4(A,8);
  }
  stop=clock();
  duration=((double)(stop-start)/CLK_TCK/100000);
  printf("%d\n",MAX);
  printf("%lf\n",duration);
  return 0;
}