数据结构的基本概念与例子

数据结构概念：构成数据的数据元素之间的结构关系。

逻辑结构概念：独立于计算机且与数据的存储无关，是描述数据元素之间的抽象化的逻辑关系，包括集合，线性结构，树形结构，图结构。

存储结构概念：又叫物理结构，依赖于计算机，是数据的逻辑结构在内存中的实现形式，包括顺序存储，链式存储，索引存储，散列存储。

运算概念：又叫算法，依赖于逻辑结构和存储结构，是施加在数据结构上的一系列操作的总称，用来描述对特定问题进行求解，是指令的有限序列。

关系：数据结构包括逻辑结构，存储结构和运算三个方面；一种逻辑结构在计算机里可以由不同的存储结构实现，不同的存储结构的效率不同，在已有的逻辑结构和存储结构基础上可以设计相对合适的算法。

算法的基本特征：
1.有穷性：一个算法必须在执行有限步骤之后结束，不能无限执行，并且其中每一条指令必须在有限的时间内完成。
2.确定性：算法中的每一条指令必须有确定的含义，不能产生两种及以上的意思，任何条件下算法只能有唯一的一条执行路径，输入相同的数据必须输出相同的结果
3.可行性：算法的步骤可以被分解为有限的基本的可执行的并且可以在有限时间内完成的步骤
4.输入：有大于等于0个输入
5.输出：有大于等于1个输出

算法与程序之间的差异：
1.程序是算法在计算机等机器上的具体实现，是用计算机语言和数据结构相配套采用算法的步骤产生的代码的实现
2.算法有有穷性，程序无有穷性；
3.程序的指令必须严格规范机器可识别，算法的指令可以是自然语言，伪语言等多种形式。

【例1】

数据元素： 每一位公司职员
元素的字段： 姓名﹑所属月份﹑应发工资﹑待扣款项﹑实发工资
元素间的关系： 线性结构关系
基本运算： 实发工资 = 应发工资 - 代扣款项

【例2】

基本运算：可能存在同学关系有u人
u = a - v ;
a = m - b;
m = n - k;
即 u = n - k - b - v;