如果说，熟练掌握编程语言是外功，那么
数据结构可谓是内功心法了
以下是我学习数据结构的总结和一些笔记
数据结构（Data Structure）
- 抽象数据类型（ADT）的物理实现
- “数据结构”是计算机中存储，组织数据的方式。
- “数据结构是数据对象”以及存在于该对象的实例和组成实例的数据元素之间的各种联系
- 解决问题方法的效率跟
数据的组织方式、空间的利用效率和算法的巧妙程度有关
例子1：
void PrintN( int N )
{
int i;
for( i=1 ; i<N ; i++)
printf("%d\n",i);
return;
}
void PrintN( int N )
{
if( N )
{
PrintN(N-1);
printf("%d\n",N);
}
return;
}
这个程序前一个用了循环实现打印1-N，后面一个采用递归的方法实现的，很明显递归的效率很低，是因为，递归实现原理是以堆栈的方式，也就是说函数把 PrintN(N) 到PrintN(1)这N个函数压入栈中，在依次打印出来，内存消耗巨大。
图示：
内存图
例子2：
计算
多项式相加
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 ));
return p;
}
double f(int n , double a[], double x)
{
int i;
double p = a[0];
for( i=n ; i>0 ; i--)
p= a[i-1] +x*p;
return p;
}
在计算机中，有多次乘法与加法的运算时，一般按照权重，只需比较乘法次数就可以了，第一个算法每一次循环执行了i+1次乘法，一共执行了（N^2+3*N）/2次，第二种算法执行了N次乘法，显然第二种效率高，这就是算法的妙用
其实数据结构是由一些基本数据类型组合成了一个复杂的数据类型，用于解决某一类问题（基本问题有数据的增加，删除，条件查询，遍历等）
总结：到底什么是数据结构？
-
数据对象在计算机中的组织方式
- 逻辑结构
- 物理存储结构
数据对象必定与一系列加在其上的操作相关联
完成这些操作所用的方法就是算法
抽象数据类型（Abstract Data Type）
- 数据类型
- 数据对象集
- 数据集合相关联的操作集
- 抽象：描述数据类型的方法不依赖于具体实现
- 与存放的机器无关
- 与数据存储的物理结构无关
- 与实现操作的算法和编程语言无关
算法
什么是算法？
- 一个有限指令集
- 接受一些输入（有些时候不需要输入）
- 产生输出
- 一定在有限步骤之后终止
- 每一条指令必须
时间复杂度Tn
根据算法写成的程序在执行时占用存储单源的长度
空间复杂度Sn
根据算法写成的程序在执行时好费时间的长度
牛刀小试
用算法实现 求一个数列的最大子列和
题目一
给出下列四个算法：
//第一种算法：时间复杂度为 T(n^3)
int MaxSubseqSum1(int a[] , int N)
{
int thisSum=0 , MaxSum=0;
int i,j,k;
for( i=0 ; i<N ; i++ ) /* i 是子列左端位置 */
for( int j=i ; j<N ; j++ ) /* j是子列右端位置 */
{
thisSum = 0; /* thisSum 是从 a[i] 到 a[j] 的子列和 */
for(int k=i;k<j;k++)thisSum+=a[k];
/* 如果刚得到的这个子列和更大，则更新结果 */
if(thisSum>MaxSum) MaxSum = thisSum;
}
return MaxSum;
}
image.png
image.png
//最快的算法，时间复杂度为T(n)
int MaxSubseqSum1(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;
}
算法三可以尝试写一下。
以上资料来源于 MOOC 《数据结构》
