数据结构——基础1
printf("%lu\n", sizeof(int));开胃菜1： 求小于1000的自然数中所有3或5的倍数之和。
方法一：遍历1~1000中能被3或5整除的数并相加
参考程序如下所示
int ans = 0;
for(int i = 1; i < 1000; i++){
if(i % 3 == 0 || i % 5 == 0){
ans += i;
}
}
printf("%d\n",ans);//233168
方法二：寻找规律，3、5的倍数即等差数列，重复的部分是15的倍数，如下所示：
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
26 27 28 29 30
等差数列求和公式=（首项+末项）*数量/2，可得1000以内自然数中3的倍数之和=（3+999）*333/2
参考程序如下所示
int t3 = (3 + 999) * 333 / 2;
int t5 = (5 + 995) * 199 / 2;
int t15 = (15 + 990) * 66 / 2;
printf("%d\n", t3 + t5 - t15);//233168
知识点1：时间复杂度——不是执行时间，在数据规模发生变化时，执行时间如何变化
表示方式——O（n）
n=1000 n=4000
方法一 1000 4000 O(n)线性级
方法二 4 4 O(1)常数级
代码——>执行时间——>复杂度
例如下程序：
int n;
//scanf
for(int i = 0; i < n / 2; i++){
//printf
}
for(int i = 0; i < n; i++){
//printf
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
//printf
}
}
n/2+n+n*n=n*n+n*2/3
删常数n*n+n——>保留最大项n*n——>时间复杂度为O(n^2)
常见时间复杂度：
O(1) 常数级 几条语句
O(logn) 对数级 二分查找
O(n) 线性级 循环
O(nlogn) 线性对数 归并排序
O(n^2) 平方 冒泡排序
O(n^3) O(n!) O(2^n)......
练习程序：
int x = 0, s = 0, n;
scanf("%d", &n);
while(s < n){
x++;
s += x;
}
printf("%d\n", x);//n=100，x=14 n=400，x=20 n=4000，x约等于280
上面程序的分析：s为x的累加，即s = 1+ 2......+x=(1+x)*x/2=(x^2+x)/2<n
——>x^2<n——>x=>时间复杂度
问题1：方法O(nlogn)执行时间一定比O(n^2)快吗？
答：不一定（原因好好琢磨琢磨）
开胃菜2：斐波那契数列（1，2，3，5，8，13，21，34，55，89，......）中不超过四百万的项，求其中偶数的项之和。
方法一：循环判断数列中被2整除的数并累加求和
int num[4000005];//大数组保存在全局变量，存在栈区存在风险,+5防止数组越界
参考程序如下所示
int main(){
num[1] = num[2] = 1;
int ans = 0;
for(int i = 3; 1; i++){
num[i] = num[i - 1] + num[n - 2];
if(num[i] >= 4000000){
break;
}
if(num[i]%2 == 0){
ans += num[i];
}
}
printf("%d\n", ans);//4613732
return 0;
}
方法二：找规律：a，b,a+b,a+2b,2a+3b,3a+5b......
1 1 2 3 5 8 13...
参考程序如下所示
int a = 1, b = 1, ans = 0;
while(b < 4000000){
if (b%2 == 0){
ans += b;
}
b += a;
a = b - a;
}
printf("%d\n", ans);//4613732
知识点2：空间复杂度——不是内存空间，在数据规模发生变化时，内存空间如何变化
方法一空间复杂度O(n),方法二空间复杂度O(1)
常见的空间复杂度
O(1) 常数 几个变量
O(n) 线性 一维数组
O(n^2) 线性 二维数组
O(logn) 递归 深度
复习C语言基础
1、指针
int a = 5;
printf("%lu\n", sizeof(int));//%lu无符号长整形格式输出——>4
int *p = &a;
printf("%lu\n", sizeof(p));//8
printf("%p\n%p\n", &a,p);//%p指针输出相同
*p = 20;
printf("%d\n", a);//20
int num[10] = {1};//num[3]=0?
printf("%p\n%p\n", num, &num[0]);//数组名为数组首地址
int *q=num;//&num[0]
q[1] = 99;
printf("%d\n", num[1]);//99
printf("num size ->%lu",sizeof(num));//40
printf("*q size ->%lu",sizeof(q));//8
2、结构体——>把几个类型组合成一个类型
定义：
struct 类型名(node){
类型1(int) 变量1(a)；
类型2(double) 变量2(b)；
}；
使用结构体：struct node x;
类型（struct node） 类型名(x)——>定义
类型名.a——>成员访问
使用结构体指针：struct xxx *p = &x;
类型（struct node *） 类型名(p)——>定义
类型名->a——>成员访问
typedef struct node{
int a;
double b;
}aaaa;//重定义结构体
aaaa y;//定义结构体变量
3、动态内存管理
cpprerfence.com——C++、C参考手册
手动内存申请
1）malloc——仅申请
2）calloc——申请并清零
3）realloc——重新申请
4）free——释放空间
#include <stdlib.h>//引用头文件
int *num;
num = (int *)malloc(10000000*sizeof(int));//使用堆区空间
......
free(num);
总结：
时间复杂度、空间复杂度、C语言基础复习指针、结构体、动态内存管理
