数据结构与算法

程序设计 = 数据结构 + 算法

一、四大逻辑结构

1. 集合结构

2.线性结构

3.树形结构

4.图形结构

5.物理结构

二、数据元素的存储结构形式

数据元素：组成数据的基本单位

                    称为元素、记录、结点、顶点

数据项

数据

注意：数据是由数据元素组成的

           数据元素是由数据项组成的

           

数据对象：性质相同的数据元素

                   是数据的一个子集

注意：数据元素是组成数据的基本单位                与数据的关系：是集合的个体

           数据对象是性质相同的数据元素的集合     与数据的关系：集合的子集

   

数据结构：数据元素相互之间存在某种关系

                  逻辑结构：数据元素之间的逻辑关系，与存储无关

                  存储（物理）结构：数据元素在计算机内存中的表示（映像）

    注意：存储结构是逻辑关系的映象与元素本身的映象

               逻辑关系是数据结构的抽象，存储结构是数据结构的实现

               二者综合起来建立了数据元素之间的结构关系

逻辑结构：

                 划分一：  

                 线性结构：一对一                       例如：线性表

                 非线性结构：一对多、多对多     例如：图、树

                 

                  划分二：

                   集合结构：结构中的数据元素只有同属一个集合这一个关系

                   线性结构：结构中的元素之间存在一对一的线性结构

                   树形结构：数据元素之间一对多的层次关系

                   图状结构或网状结构：数据元素之间存在多对多的任意关系

：

存储结构

1.顺序存储 ：把数据元素存放在地址连续的存储单元里，其数据数据间的逻辑关系和物理关系是                          一 致的；例如：数组结构

2.链式存储结构：是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是                              不连续的。利用指针来将数据联系起来

>>>>>>在存储一个元素本身的同时也存储了下一个元素的地址>>>>>从而找到下一个元素

3.索引存储结构>>>>>建立了目录

例如通讯录

4.散列存储

根据关键字直接计算

三、数据类型和抽象数据类型

数据类型：类型就可以明确告诉计算机，需要约束常量变量的取值范围等

                 数据类型是一组性质相同的值的集合以及定义于这个值集合上一组操作的总称

            数据类型 = 值的集合 + 值集合上的一组操作

抽象数据类型 ADT : 不考虑在计算机里如何存储

>>>> 一个数学模型已经定义在此数学模型上的一组操作

>>>> 从问题抽象出数据模型（逻辑结构）

>>>> 包括定义在数据模型上的一组抽象运算

>>>> 三元组：DSP

                        D：数据对象

                         S：D上的关系集

                         P：D的基本操作集

>>>> 一个抽象数类型的定义格式

            ADT 抽象数据类型名

                     {

                      数据对象：<数据对象的定义>

                      数据关系：<数据关系的定义>

                       基本操作：<基本操作的定义>

                    } ADT 抽象数据类型名

其中：

              数据对象、数据关系的定义用伪代码

               基本操作的定义格式为：

                             基本操作名

                              初始条件

                              操作结果

               说明：

               参数表 ：赋值参数只为操作提供输入值

                            以 & 打头，除可提供输入值外，还将返回操作结果

                初始条件：  满足和不满足相应的结果

                操作结果：说明操作完成后，数据结构的变化状况和相应返回的结果

举个例子：

总结：

具体抽象函数的例子，对比C语言

四、算法------用类C语言（伪代码）

算法与程序：程序 = 数据结构 + 算法

一、特点：

输入：0个或者多个输入

输出; 至少有一个或多个输出

有穷性：有限步骤后可以自动结束而不会出现无限循环

确定性：每个步骤都有确定的含义

               只有一条执行路径

               相同输入只能有唯一的输出结果

可行性：每一步都可以在当前环境下实现

二、算法设计

（一）特点

 正确性

 可读性 

 健壮性：对于异常情况下计算机怎么去应对

 高效性：时间少效率高

（二）算法时间效率、空间效率

时间效率：

    1.度量方法

                   事后统计：将算法实现、测算时间和空间开销

                   事前分析：对算法所消耗资源的估算>>>>>>一般用这个方法

                                             

（计算时候可以省略该语句执行一次所需的时间）

举个例子：每条语句执行的次数

>>>>> 简化>>>>>>比较算法的数量级，数量级越小越好

                   >>>>>为算法的渐进时间复杂度

如何计算算法的渐进时间复杂度 ？？

定理：去掉低次幂项和最高次幂系数----------找嵌套最多的语句

重点看每一句的次数该怎么数？

级数求和！！！！