初识数据结构

什么是数据

1.能够参与计算机处理计算的各种信息：包括符合，数值，文字，图都属于数据

数据元素

1.数据元素是数据的基本单位，在计算机中通常将数据元素作为一个整体进行处理

数据对象

1.一组相同性质的数据元素集合

数据结构

1.由一种或者多种相互存在关系的数据元素的集合（简单来说就是数据元素之间的关系）

数据结构分为：逻辑结构和物理结构

逻辑结构分四种：集合，线性，树形，图形

- 集合：描述同一种数据的关系

- 线性: 描述一对一关系的

- 树形：描述一对多关系的

- 图形：描述多对多关系的

数据逻辑结构一般用二元组的形式定义：

数据结构=（D,S）

其中 D：数据元素的集合 S：D中元素之间的关系集合

例1： 集合结构：set=(D,S)

​ D={1,2,3,4,5} S={}

例1： 树形结构 ：tree=(D,S)

​ D={1,2,3,4,5} S={<2,1>,<2,2>,<1,3>,<1.,4>,<1,5>} S存在一对多的关系就是树形

物理结构：就是数据逻辑结构在计算机中的存储表示。他有两种表示形式：

顺序存储，链式储存

- 顺序存储：一段连续的存储空间，数据之间紧挨在一起，数据的前驱和后驱的关系可以通过数据元素中的相对位置反应出来。

- 链式储存：每个元素保存下个元素的存储位置。

1.2 抽象数据类型

数据类型：一组性质相同的数据集合及该数据集合上的操作总称

如：java中的int类型，数据的集合是：-2147483648-2147483647，在这组数据上的操作：加减乘除求余

抽象数据类型 ：由一组数据模型及该模型上的操作总称

用三元组表示：（D，S, P）D：数据元素的集合 S：D中元素之间的关系集合 P:是在D上的一系列操作

1.3 算法和性能分析

1.3.1 算法

为解决某个特点问题而特定规定的一系列的操作，是一组有序的指令集合。

高斯求和算法：n*(n+1)/2 （n=求和次数）

1+2+3+4+....+100

100+99+98+....+1

101+101+101+...

101*100/2=5050

算法：至少有一个输入或者多个输入，至少有一个输出，没有输出的算法是没有意义的。

有穷性：执行指令的个数有限，执行有穷的步骤后能结束

确定性：每次合法输入，输出的值是确定的

可行性：算法能够被实现，并在有限时间内完成。

算法设计要求：正确性：没有语法错误，对于合理的输入满足要求的输出，可读性：为了方便交流，健壮性：对于不合理的输入需要提示，而不是崩溃

好的算法时间花费少和占用存储空间少