数据结构学习笔记

先放上数据结构的学习建议的链接知乎，如何学习数据结构 我使用的学习视频链接清华大学：数据结构学堂在线慕课网

---

学习动机

在大二的时候，刚入门学习，还没有计算机知识的学习框架。拿到数据结构这本书的时候，翻了一下， 很多概念都不知道，感觉挺晦涩的。之后的学习也因为*缺少上机实践*而学习的不好——自认为算法的思路 是知道了，到真正要用的时候又不知如何具体的实现。 本人的专业是“物联网工程”。刚新创的专业，那方向是大啊。学的都是基础知识，在计算机技术方面 雨露均沾（网络技术、通信技术、软件技术、硬件技术、系统）。在剩余大学时间也摸索过自己想深入学习 的方向，主要学习过java编程，嵌入式编程。但现在从事的工作是计算机软件开发（c++)............ 当然，我知道现行的热门方向更靠向移动端开发和嵌入式，所使用系统也趋向于开源和跨平台。不过基 础知识都是相通的，学了准没错，日新月异的技术也必须依靠基础的知识搭建起来。 首先，语言、系统和编译环境都是编程的工具和手段而已，各有所长，没有绝对的好与坏。在日新月异 的技术发展时期，绝不能只学一门语言。更重要的是掌握思想和有一个整体的框架。而数据结构就是一种编 是摆脱搬运工码农的旅程开始之一。

---

数据结构的第一个案例

这是自己印象比较深刻的一个案例，先写出来作引子。

先给出一个调论较多的斐波那契数列的求解问题： 对于f(n)有f(n) = f(n-1)+f(n-2);f(0) = 1,f(1) = 1; 这也是跳台阶问题:一只青蛙可以跳一个台阶，也可以跳二个台阶，问它跳n个台阶时一共有多少种跳法？ 其答案就是斐波那契f(n)的解。 如果用编程如何实现呢？ 观察数学等式可以轻易发现，其是递归函数。所以, 一找出递归过程及f(n) = f(n-1) + f(n-2); 二找出递归基，及f(0) = 1,f(1) = 1; 于是有递归方案： long Fibonacci(int n) { if(n == 0 || n == 1)//递归基 return 1; else return Fibonacci(n-1)+Fibonacci(n-2); } 递归能很好的把问题简化的分析出来，代码也是只要有递归过程和递归基，两三行就写出来。 其计算是符合有输入、有输出、有穷性、可行性、切确性的基本特征。但其效率性是很低的。其时间 复杂度为O(2^n)，在设计中该时间复杂度的算法被认为是不可行的，因为其时间复杂度远大于计算机 在有限时间内能处理的能力。 所以，得到问题的解决方法，再来考虑解决问题的效率。 递归是由后往前再由前往后计算的，这是数学等式给我们的规律。而回到青蛙跳台阶，其是从 前往后计算的过程的。是原来问题的逆过程。及，要知道到达n的结果，不妨放弃要知道n-1和n-2 的结果和往后推的结果。改为由前往后计算的顺过程，先有f(0) = 1,f(1) = 1, f(2) = f(0)+f(1) = 2,f(3) = f(2)+f(1) = 3...f(n-1) = f(n-2)+f(n-3), f(n) = f(n-1)+f(n-2)这样顺推下去,于是有 long Fibonacci(int n) { long g = 1,f = 1;//表示第n = 1，n = 0时 //while(--n) for(int i = 1;i < n; ++i)//从底向高求 { g = g+f;//f(n) = f(n-1)+f(n-2);f(n-1),f(n-2)已知 f = g-f;//f(n-1) = f(n)-f(n-2);保留f(n-1),去掉f(n-2)把计数向上移 } return g; } 递归帮我们轻易的了解到计算的规律，我们把问题规模为n的，分解成规模为n-1的规模，且n 和n-1又具有完全相同的性质，所以可以延用解决n规模的方法解决n-1规模的问题，一直把问题分 解成我们能轻易解决的一个个简单子问题，这是“减而治之”的解决思想。在递归的解决方法中还有 一个“分而治之”的思想，这个例子中直接给出了数学等式，在实际问题中可能我们要将问题以数学的 方式抽象出来。其大概的过程是先找到问题可行的解决方案，再在此基础上找规律得到高效率的解决方法。