第一章 数据类型编程语言回顾
指针型变量
定义一个整型指针变量并初始化为A的地址：
int *p1 = &A;
定义一个浮点型指针变量并初始化为B的地址：
int *p2 = &B;
定义一个字符型指针变量并初始化为C的地址：
int *p3 = &C;
将一个整型变量的地址赋值给p1:
p1 = &D;//p1指向D
通过指针获得所指变量的值：
E = *p1;
初始化指针：
int *p4 = NULL
结构体
结构体是指不同变量组合在一起构成的变量，定义结构体的方式：
typedef struct
{
int a;
float b;
char c;
... ...
} 结构体名;
typedef struct 结构体名
{
int a;
float b;
char c;
struct 结构体名 *d；
... ...
} 结构体名;
结构体赋值：
typedef struct
{
int a;
float b;
char c;
... ...
} S;
S s;
s.a = 1;
s.b = 1.11;
s.c = 'A';
R = s.a;
存储结构
链式存储
链式存储不止存储数据，也存储与其他数据单元之间的关系，实现一个链式存储的结构：
typedef struct LNode
{
int data;
struct LNode *next;//重要
}LNode;
LNode *L;
L = (LNode*)malloc(sizeof(LNode));
A->next = B;
B->next = C;
顺序存储
顺序存储结构支持随机存储。
时间复杂度分析
把加，减，乘，除，比较和赋值都看作复杂度相同的问题。
含有控制语句函数的时间复杂度分析
int f(int N)
{
int i,sum;
sum = 0;
for(i = 0;i < N;i++)
{
sum += i*i*i;
}
return sum;
}
i = 0 执行1次；
i < N执行N+1次；
i++执行N次
一共是2N+2次；
然后循环体里的操作两次乘法，一次加法，一次赋值运算，执行了N次，4N
所以整个算法的时间复杂度为6N+4
O(N)
一次循环运行的时间是循环内所有语句的运行时间乘循环的次数；
嵌套循环运行时间是最内层语句执行次数乘以总循环次数；
并列的两个循环运行时间与执行次数数量级大的循环相同。
递归函数时间复杂度分析
习题
1.一个算法应该是(问题求解步骤的描述)
2.某算法的时间复杂度是O(n2),表明该算法的(执行时间与n2成正比
3.以下算法的时间复杂度为(O(log2n))
void fun(int n){
int i = 1;
while(i <= n)
i = i * 2;
}
首先找出基本运算 i = i * 2；
设运行次数为t ，2t<=n,t <= log2n
4.已知两个长度分别为m和n的升序链表，若将他们合并为一个长度为m+n的一个降序链表，则最坏情况下的时间复杂度是O(max(m,n))
5.下列函数的时间复杂度为O(n1/2)
int func(int n){
int i = 0,sum = 0;
while(sum<n)
sum += ++i;
return i;
6.下面说法中，错误的是(A)
A.算法原地工作的含义是指不需要任何额外的辅助空间
B.在相同规模n下，复杂度为O(n)的算法在时间上总是优于复杂度为O(2n)的算法
C.所谓时间复杂度，是指在最坏情况下估算算法执行时间的一个上界
D.同一个算法，实现语言的级别越高，执行效率越低。
总结
