什么是数据结构
1.是关于数据对象在计算机中的组织方式 就例如书店里如果摆放书籍，应该在哪个区域的问题
其中有两个概念有关于数据对象在计算机的组织方式：
one.数据对象的逻辑结构（什么是逻辑结构：比如说 把书架想象成一长条的架子，所有书是一个挨着一个放的，除了一
头一尾书以外，其他书在它前面只有一本书在后面也只有一本书，每本书对应一个编号，这种结构就是一对一的结构，称
为线性结构 另外一种方法就是给图书分类，每一类一个编号，每一个编号对应多本书，这种结构是一对多的结构，称为
树，即树形结构 再进行假设:统计这本书有哪些人买过，买过这本书的人还买过其他的什么书，即一本书对应很多
人，一个人又对应了很多本书，这个是一个多对多的复杂关系网，这个关系网对应的是一个图的结构）
two:数据对象在计算机里的物理存储结构
也就是这些逻辑机构在机器的内存里的存放方法，是连续放，还是隔开放，也就是使用一个数组存放还是用链表存放，这个属于物理存储结构
2.数据对象必定与一系列加在其上的操作相关联
3.完成这些操作所用的方法就是算法
如何描述数据类型
有一个很好的方法叫做：抽象数据类型（Abstract Data Type）
数据类型包含两个东西：
1. 数据对象集
2.数据集合相关联的操作集
抽象：描述数据结构的方法不依赖于具体实现
与存放数据的机器无关
与数据存储的物理结构无关
与实现操作的算法和编程语言均无关
只描述数据对象集合相关操作集“是什么”，并不涉及“如何做到“的问题
什么是好的算法？
空间复杂度S(n)—根据算法写成的程序在执行时
占用存储单元的长度。这个长度往往与输入数据的规模有关。空间复杂度过高的算法可能导致使用的内存超限，造成程序非正常中断。
时间复杂度T(n)——根据算法写成的程序在执行时
耗费时间的长度。这个长度往往也与输入数据的规模有关。时间复杂度过高的低效算法可能导致我们在有生之年都等不到运行结果。
例如：这个是一个递归的程序
但是它非正常跳出了，为什么？
假设上图正方形是程序可以调用的内存空间，pirntN（100000），
判断为True后，于是递归调用 传入的参数是 99999 ，调用这个函数之前，系统需要把当前的这个函数现有的状态 存入，即100000这个数存入内存
，直到调用到1，即 程序在内存里占用的空间数量实际上是跟原始的N的大小成正比。。
以下是两个例子：
#include<stdio.h>
double f(int n,double a[],double x)
{
int i;
double p = a[0];
for (i = 1; i<=n; i++)
p += (a[i] * pow(x, i)); //pow 是算x的i次方
return p;
}
//一共做了（1+2+....+n）=(n方+n)/2次乘法
#include<stdio.h>
double f(int n,double a[],double x)
{
int i;
double p = a[n];
for(i=n;i>0;i--)
p = a[i-1] + x*p;
return p;
}
// n次乘法
第二个算法明显比第一个好，因为所涉及的乘法次数少，运算速度快。。。
在分析一般算法的效率时，我们经常关注下面两种复杂度
最坏 情况复杂度T worse(n )
平均复杂度T avg( n )
一般分析最坏复杂度
复杂度的渐进表示法
即：简单来说 O(f(n))就表示f(n)是T(n)的某种上界 对于充分大的n而言
这个形式表示g（n）是T（n）的某种下界
对于h（n）这个函数来说，大O的大Ω是同时成立的，也就是它既是上界，也是下界
程序员的直觉，当有一个算法是O(n的平法)，下意识想能不能变成O(nlogn)
复杂度分析小窍门
一个for循环的时间复杂度等于循环次数乘以循环体代码的复杂度 一个for循环的时间复杂度等于循环次数乘以循环体代码的复杂度
if-else结构的复杂度取决于if的条件判断复杂度和两个分枝部分的复杂度，总体复杂度取三者中最大 如果-否则结构的复杂度取决于if的条件判断
复杂度和两个分枝部分的复杂度，总体复杂度取三者中最大
待续………….
例子：给定N个整数的序列{A1,A2,…An},求函数f(i,j)=max{0,sum(Ak)}的最大值。也就是求出最大子序列的和（就是连续的子集！加起来最大）
//算法一：
int MaxSubseqSum1(int A[],int N){
int ThisSum,MaxSum =0;
int i,j,k;
for(i = 0;i<N;i++){ /* i是子列左端位置 */
for(j=i;j<N;j++){ /* i是子列左端位置,且 i小于j */
ThisSum =0; /* ThisSum是从A[i]到A[j]的子列和 */
for(k =i;k<=j;k++)
ThisSum += A[k];
if(ThisSum>MaxSum)
MaxSum = ThisSum;
}
}
return MaxSum;
}
int main(){
int A[6],N,P,i; //定义输出和函数调用
for(i = 0;i<=5;i++){
scanf("%d",&A[i]);
}
scanf("%d",&N);
P = MaxSubseqSum1(A,N);
printf("MaxSum = %d", P);
return 0;
}
//例子：{ -2, 11, -4, 13, -5, -2 }
//MaxSum = 20;
//成功输出！！！！！
//算法复杂度为：T(N) = O（N的三次方），三层嵌套，暴力求值，算法很笨
接下来看另一种方法：
int MaxSubseqSum2(int A[],int N)
{
int ThisSum,MaxSum = 0;
int i,j;
for(i = 0; i<N; i++){
ThisSum = 0;
for(j = i; j<N;j++){
ThisSum += A[j];
//对于相同的i，不同的j，只要在j-1次循环的基础上累加1项即可
if(ThisSum > MaxSum)
MaxSum = ThisSum;
}
}
return MaxSum;
}
int main(){
int A[6],N,P,i;
for(i = 0;i<=5;i++){
scanf("%d",&A[i]);
}
scanf("%d",&N);
P = MaxSubseqSum1(A,N);
printf("MaxSum = %d", P);
return 0;
}
//例子：{ -2, 11, -4, 13, -5, -2 }
//MaxSum = 20; //成功输出！！！！！
//算法复杂度为：T(N) = O（N的二次方），二层嵌套，暴力求值，算法比第一个聪明
//方法三
//在线处理,意思是指每一个输入一个数据就进行即时处理，在任何
//一个地方终止输入，算法都能正确给出当前的解
#include<stdio.h>
int MaxSubseqSum3(int A[],int N)
{
int ThisSum,MaxSum;
int i;
ThisSum = MaxSum = 0;
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[6],N,P,i; //定义输出和函数调用
for(i = 0;i<=5;i++){
scanf("%d",&A[i]);
}
scanf("%d",&N);
P = MaxSubseqSum3(A,N);
printf("MaxSum = %d", P);
return 0;
}
//算法复杂度为：T(N) = O（N）