数据结构和算法绪论

什么是数据结构？

数据结构是一门研究非数值计算的程序设计问题中的操作对象，以及它们之间的关系和操作等相关问题。

数据结构就是关系，是数据元素相互之间存在的一种或多种特定关系的集合。

传统上，把数据结构分为逻辑结构和物理结构。

逻辑结构：是数据对象中数据元素之间的相互关系

物理结构：是指数据的逻辑结构在计算机中的存储形式

逻辑结构：

1 集合结构：集合结构中的数据元素除了同属于一个集合外，没有其他关系
001数据结构和算法绪论

2 线性结构：线性结构中的数据元素之间是一对一的关系
001数据结构和算法绪论
3 树形结构：树形结构中的数据元素之间是一对多的关系

4 图形结构：图形结构中的数据元素之间是多对多的关系

物理结构：

数据元素的存储结构有两种形式：顺序存储和链式存储。

顺序存储结构：是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。
001数据结构和算法绪论
【例】：数组

类比排队。一个挨着一个等待。但考虑到更紧急的事情需要插队的情况。出现了更灵活的链式存储结构。

链式存储结构：是把数据元素存放在任意的存储单元里，这组存储单元可以连续，也可以不连续。

链式存储结构的数据元素存储关系并不能反映其逻辑关系，因此需要用一个指针存放数据元素的地址，这样通过地址就可以找到相关联数据元素的位置。
001数据结构和算法绪论
类比叫号。无所谓在哪里等待，只需关注前一个号有没有被叫到。

什么是算法？

1+2+3+4+5+…+98+99+100

高斯

算法是解决特定问题的求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。

对于给定的问题是可以有多种算法来解决的。

算法的基本特征：

输入，输出，有穷性，确定性，可行性

输入：

算法具有零个或多个输入

输出：

算法至少要有一个输出

有穷性：

指算法在执行有限的步骤后，自动结束而不会出现无限循环。且每个步骤都要在可接受的时间内完成。

确定性：

算法的每一个步骤都具有确定的含义，不会出现二义性。

算法在一定条件下只有一条执行路径，相同的输入只能有唯一的输出结果。

算法的每个步骤都应该被精确定义而无歧义，

可行性：

算法的每一步都必须是可行的，即每一步都能通过执行有限次数完成。

算法的要求：

正确性，可读性，健壮性，时间效率高，存储量低。

正确性：

算法至少应该有输入输出和加工处理无歧义性，能正确反应问题的需求、能得到问题的正确答案。

四个层次：

没有语法错误。
对于合法输入能够产生满足要求的输出。
对于非法输入能够产生满足规格的说明。
对于故意刁难的测试输入都有满足要求的输出结果。

可读性：

算法设计另一目的是为了便于阅读、理解和交流。

健壮性：

当输入数据不合法时，算法也能做出相关处理，而不是产生异常，崩溃或莫名其妙的结果。

时间效率高，存储量低：

运行效率越高越好，占用空间越低越好。

的是为了便于阅读、理解和交流。