数据结构课程的起源
1968年高德纳教授开创了数据结构这门学科，同年，数据结构作为计算机科学的学位课程。
数据结构研究什么
研究非数值计算类型的程序问题；
研究数据之间的组织和操作方式；
研究数据的逻辑结构和存储结构；
为什么要学习数据结构
学习C语言或者C++只是学了一个语法，就像武侠片里面学武功不仅要学心法还要学招式，这个心法就对应语法，这个招式就要通过学习数据结构来提高。数据结构可以培养专业的程序设计思维，提高使用程序语言描述解决方案的能力。
数据结构与算法的关系
数据结构是研究数据之间的关系，解决实际问题的还是算法。
算法是在一定的数据结构基础上来完成的，数据结构与算法是相互交融的。
不下降序列问题
由n个数组成的数列，分别是：a[1]、a[2] 、a[3] ...... a[n]，
若存在i1<i2<......<im满足a[i1]<=a[i2]<=......<=a[im],
则称为长度为m的不下降序列。
例如：3，18，7，14，10，12，23，41，16， 24
则：3，18，23，24是一个长度为4的不下降序列；
3、 7、 10 、12、 16、 24是一个当度为6 的不下降序列；
求：如何求最长不下降序列？如何求所有不下降序列？
学习数据结构需要具备的三大技术点：
C++面向对象技术
C++模板技术
C++异常处理技术
为什么有各种各样的程序存在，程序的本质是什么？
程序 = 数据结构 + 算法
程序是为了解决实际问题而存在的没从本质上而言，程序是解决问题的步骤的描述。
比如：怎样把大象放到冰箱里？
步骤：
1、打开冰箱门；
2、把大象放进去；
3、关上冰箱门。
对应的程序
Elephan* e = new Elephan;
Fridge* f = new Fridge;
f->open();
f->put(e);
f->close();如何解决问题
首先确认问题的类型；
然后确认解决步骤；
解决问题的步骤也是有好差的区分的。
比如：求1到n之间的数累加和的三种算法
程序实例1：
#include <iostream>
using namespace std;
//方法1：使用两个for循环
long sum1(int n)
{
long ret = 0;
int* array = new int[n];
//将数组填充进数组
for(int i=0; i<n; i++)
{
array[i] = i + 1;
}
//数组元素累加
for(int i=0; i<n; i++)
{
ret += array[i];
}
delete[] array;
return ret;
}
//方法2：一个循环解决问题
long sum2(int n)
{
long ret = 0;
for(int i=1; i<=n; i++)
{
ret += i;
}
return ret;
}
//方法3：不用循环解决问题
long sum3(int n)
{
long ret = 0;
if(n>0)
{
ret = (1+n)*n/2;
}
else
{
ret = 0;
}
return ret;
}
int main()
{
cout <<"sum1 = " << sum1(100) << endl;
cout <<"sum2 = " << sum2(100) << endl;
cout <<"sum3 = " << sum3(100) << endl;
return 0;
}
int main()
{
cout << sum1(100) << endl;
return 0;
}显然3种方法都可以得出正确的结果，但是显然第三种方法的效率是最高的。好在哪里？
评价好程序的标准
用尽量少的时间解决问题；
用尽量少的步骤解决问题；
用尽量少的内存解决问题；
NASA用64K内存的代码就能实现探索外太空。
数据的概念
数据是程序的操作对象，用于描述客观事物，数据可以输入到计算机，可以被计算机程序处理。
数据元素：组成数据的基本单位
数据项：一个数据元素由若干数据项组成
数据对象：性质相同的数据元素的集合
struct Student //数据类型
{
char* name;
int age;
};
Student s; //数据元素
Student sArray[10]; //数据对象
s.name = "lili"; //数据项
s.age = 10; //数据项数据结构就是指数据对象中数据元素之间的关系。比如数组中，各元素之间存在固定的线性关系。
典型的数据结构
逻辑结构：
集合结构：数据元素之间没有特定的关系，仅同属相同集合；
线性关系：数据元素之间时一对一的关系；
树形关系：数据元素之间存在一对多的层次关系；
图形关系：数据元素之间时多对多的关系。
物理结构：
顺序存储结构：将数据存储在地址连续的存储单元中；
链式存储结构：将数据存储在任意的存储单元中，通过保存地址的方式找到相关联的数据元素。
算法是程序的灵魂
算法的特性：
算法有输入：
算法有输出：
算法的有穷性：算法在有限的步骤会结束，不会无限循环
算法的确定性：算法的每一步都有确定的含义
算法的可行性：算法的每一步都是可行的
如何评价算法的好坏
如果两个算法都能满足功能性需求，在工程中怎么评判，怎么选择？
性价比是工程上最关注的。
事后统计法：比较不同算法对同一组输入数据的运行处理时间。
事前分析估算： 依据统计的方法对算法效率进行评估。
如何学习数据结构
1、从概念上形象的理解数据元素之间的关系
2、思考数据关系能解决什么问题；
3、思考基于这种关系能够产生哪些算法；
4、理解并熟悉最终的算法；
5、选择一种熟悉的语言编码实战。