1. 线性结构

比如超市商品

2. 树结构

具有分支,层次的限制

3. 图结构

多岔路口需要设置几种颜色的交通灯才能使车辆相互之间不碰撞达到最大流量

每个数据元素用圆圈表示,节点之间的关系是任意的.

每个相连接的节点是不能统一颜色的.将交通灯的设置问题,转为图结构的上色问题

4. 集合

数据的逻辑结构

研究的问题,如何将实际问题进行抽象,

相关名词:

• 数据: 描述客观事物的数值,字符以及能输入机器且能被机器理解的.
• 数据元素: 组成数据的基本单位,是数据集合的个体.
• 数据对象: 性质相同的数据元素的集合.
• 数据结构: 指相互之间存在的一种或者多种特定关系的数据元素的集合,是带有结构的数据元素的集合.即数据的组织形式.
• 数据类型(data type): 一组性质相同的值集合以及定义在这个值集合上的一组操作的总称.{原子类型,结构类型}
• 抽象数据类型(abstract data type): 例如线性表.传统的面向过程的程序设计,"包","模型设计";面向对象编程

数据抽象: 用ADT描述程序处理实体时,强调的是本质的特征,其所能完成的功能以及它和外部用户的接口(即外界使用的方法)
数据封装: 将实体的外部5特征好其内部的实现细节分离,并对外部用户隐藏其内部实现的细节.

数据的逻辑结构和存储结构

• 逻辑结构:数据元素之间逻辑关系描述

集合结构: 除了属同一个集合,其他没有关系. 线性结构: 结构中的数据元素存在一对一关系.
树结构: 计算机的目录,族谱,博弈数,只有分支和层次关系. 图状结构: 结构中的数据之间存在着多对多的任意关系.例如城市交通问题

线性结构有: 顺序表,链表,栈和队列,串,数组和广义表 非线性结构: 树和图.

• 存储结构: 在计算机中的存储映像,是逻辑结构在计算机中的实现,包括数据元素的表示和关系的表示

数据元素的表述: 用若干个二进制的"位串"表示.

顺序结构和链式结构

数据结构: 按照某种逻辑关系组织起来的一批数据,按照一定的映像方式把它存放在计算机存储器中,并在这些数据上定义了一个运算的结合,就叫做数据结构.

算法及其时间复杂度的关系

算法: 是规则的有限集合,是为了解决特定问题而规定的一系列操作.

1. 有限性:
2. 确定性:
3. 无二义性:
4. 输入输出:
5. 可读性:

算法的特性

1. 正确性: 不含语法错误,多组数据能满足要求,某些刁难型的数据也能满足要求,一切的合法的输入数据都能满足规格数码的要求结果.
2. 可读性:结构清晰,命名按照它的含义
3. 健壮性
4. 高效率和低存储量的要求:

算法和语言,程序的关系

衡量算法

1. 事后统计法
2. 事前分析估算: 算法选用的策略,问题的规模,编写程序的语言,编译程序产生的机器码质量,机器运行的速度.

寻找算法里面的基本操作语句(源操作),对其语句的频度进行统计,从中得到时间的估算.

• 时间复杂度

T(n) = O(f(n))

• 空间复杂度

输入数据;程序本身;辅助变量 S(n) = O(f(n))

计算机导论

1673年莱布尼茨发明计算器,机械式
// 从计算辅助工具到计算机
算盘--> Pascal --> 巴贝奇差分机 --> 莱布尼茨 --> 计算机
// 元器件的发展 二极管--> 晶体管--> 集成电路 --> 
图灵机--> ENIAC --> 冯诺依曼体系EDVAC

"控制器" --> "运算器" --> "输入" --> "输出" --> "存储"

微处理器
字长 : 8位 -> 16位-> 32位-> 64位
主频 : 几MGz -> 几百MHz --> 几GHz
集体管数量: 几万--> 百万 --> 几亿
功能与规模: 微处理器 --> +协处理器 --> +GPU --> +3D + Media --> 多核处理器
 
 实验思维: 实验-> 观察-> -> 发现总结. 观察与归纳
 理论思维: 假设/预设->定义/性质/定理-> 证明.  推理演绎
 计算思维: 设计,构造与计算. 设计与构造