从头学数据结构--跟随浙大陈越姥姥的步伐
1.1什么是数据结构：
数据对象在计算机中的组织方式
逻辑结构 ：
线性结构：元素关系为一对一，除了第一个
树形结构：元素关系为一对多，树结构中的数据元素称为”结点“，且有一个称为”根节点“的元素，他们按照分支关系进行组织起来
集合结构：数据元素之间只有一种关系，即属于同一个集合，除此没有其他关系
图结构：数据元素之间关系存在多对多的关系，图结构中的任意两个数据元素（也称为”结点“）之间都可能相关。
逻辑结构一般也可以分为 线性结构 和 非线性结构
物理存储结构：顺序存储结构，链式存储结构
数据对象必定与一系列加在其上的操作相关联
完成这些操作所用的方法就是算法
描述数据结构的方法：抽象数据类型（Abstract Data Type）
抽象：
与存放数据的机器无关
与数据存储的物理结构无关
与实现操作的算法和编程语言均无关
数据类型：
数据对象集
数据集合相关联的操作集
只描述数据对象集和相关操作集”是什么“，并不涉及”如何做到“的问题
例：”矩阵“的抽象数据类型定义
类型名称：矩阵（Matrix）
数据对象集：一个MN的矩阵A（MN） = （A..........告辞！放弃了
伪代码。
）
1.2 什么是算法（Algorithm）
一个有限指令集
接收一些输入（有些情况下不需要输入）
产生输出
一定在有限步骤之后终止
每一条指令必须
有充足明确的目标，不可以有歧义
计算机处理的范围之内
描述应不依赖于任何一种计算机语言以及具体的实现手段
例一：选择排序算法的伪代码描述：
void SelectionSort (int List[],int N)
{/*将N个整数List[0]...List[N-1]进行非递减排序（可能有相同值排序，因此叫递增的话不是很确切）*/
for(int i= 0;i<N;i++){
MinPosition = ScanForMin(List,i,N-1);//ScanForMin为查找最小元所在位置函数
/*从List[i]到List[N-1]中找最小元，并将其位置赋给MinPosition;*/
Swap(List[i],List[MinPosition]);//swap为交换函数
/*将未排序部分的最小元(List[MinPosition])换到有序部分的最后位置(List[i-1])；*/
}
}
抽象--------
List到底是数组还是链表？（虽然看上去像数组）
Swap用函数还是用宏实现？
什么是好算法？
1：空间复杂度S（n）
2：时间复杂度T（n）
例二：递归
Void PrintN(int N){
if(N){
printN(N-1);
printf("%d\n",N);
}
return;
}
S(N) = C*N
两种复杂度：
最坏情况复杂度 T worst(n)
平均复杂度 T avg(n)
复杂度的渐进表示法
T（n） = O（f（n））表示存在常数C>0，n 0>0 使得当 n>=n 0时有T（n）<=C*f(n)
由图可知，当复杂度为log n 时为最好的算法
复杂度分析小窍门
1.3最大子列和问题
（N个整数，有正有负）
算法一：
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++){/*j是子列右端位置*/
ThisSum = 0;/*ThisSum是从A[i]到A[j]的子列和*/
for(k = i;k<=j;k++){
ThisSum +=A[k];
}
if(ThisSum >MaxSum){/*如果刚得到的这个子列和更大*/
MaxSum = ThisSum;/*则更新结果*/
}
}/*j循环结束*/
}/*i循环结束*/
return MaxSum;
}
复杂度：T（N） = O（N^3）,复杂度太大
算法二：优化K循环
int MaxSubseqSum2(int A[],int N){
int ThisSum,MaxSum = 0;
int i,j;
for(i = 0;i<N;i++){/*i是子列左端位置*/
ThisSum = 0;/*ThsiSum是从A[i]到A[j]的子列和*/
for(j = i;j<N;j++){/*j是子列右端位置*/
ThisSum += A[j];
/*对于相同的i,不同的j，只要在j-1次循环的基础上累加1项即可*/
if(ThisSum>MaxSum){/*如果刚得到的这个子列和更大*/
MaxSum = ThisSum;/*则更新结果*/
}
}/*j循环结束*/
}/*i循环结束*/
return MaxSum;
}
复杂度：T（N） = O（N^2）
算法三：分而治之（分治）
?（目前还在参考别人的代码，有空再写）