【1】数据结构和算法绪论

数据结构

逻辑结构

• 集合结构：数据结构中的元素之间除了“同属一个集合” 的相互关系外，别无其他关系；
• 线性结构：数据结构中的元素存在一对一的相互关系；
  -. 树形结构：数据结构中的元素存在一对多的相互关系；
• 图形结构：数据结构中的元素存在多对多的相互关系。

逻辑结构

物理结构

• 顺序存储：把逻辑上相邻的节点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现。
• 链式存储：在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。
• 索引存储: 除建立存储结点信息外，还建立附加的索引表来标识结点的地址。
• 散列存储：根据结点的关键字直接计算出该结点的存储地址。

---

算法

特征

• 有穷性： 一个算法必须保证执行有限步之后结束；
• 确切性： 算法的每一步骤必须有确切的定义；
• 输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定除了初始条件；
• 输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；
• 可行性： 算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。

设计要求

• 正确性：算法的正确性是指算法至少具有输入，输出和加工处理无歧义，并且可以正确反映问题的需求，以及正确得到问题的答案。

1. 算法程序没有语法错误。
2. 算法程序能够根据正确的输入的值得到满足要求的输出结果。
3. 算法程序能够根据错误的输入的值得到满足规格说明的输出结果。
4. 算法程序对于精心设计的，极其刁难的测试数据都能满足要求的输出结果。

• 可读性：算法设计的另一个目的是为了便于阅读，理解和沟通，如果写的代码只有你和上帝能看懂，那这个算法只能说明很失败，因为算法越难理解，就越难找到他的bug，对于调试和修改就更难了
• 健壮性：当输入的数据不合法的时候，算法也能给出相关的处理，而不是产生异常或者莫名起码的错误。
• 时间效率高和空间存储量低：在满足以上几点以后，我们还可以考虑对算法程序进一步优化，尽量满足时间效率高和空间存储量低的需求。