数据结构的学习笔记

数据结构的学习

早期:计算机科学是研究算法的科学
近期:计算机科学是研究数据的科学

数据结构是程序设计的基础

程序=算法+数据结构(两大支柱)
通过算法对数据结构进行操作与控制

早期:程序就是软件,软件就是程序
近期:接口、消息的传递、技术文档、模块化、数据类型,软件=程序+文档
现在:只需要学会一门语言,对相应的指导性文件进行翻译即可。

DS主要研究内容

数据的各种逻辑结构和物理结构,以及他们直接按的相应关系
对各种结构定义相适应的各种运算
设计出相应的算法
分析算法的效率

基本术语

数据可以根据不同特性,分解为若干个不同的数据对象。数据对象由包含了若干个不同的个体,称为数据元素。每个数据元素由不同的数据项加以描述,数据项是数据集合中最小的有意义单位。
数据结构:是带有结构的数据元素的集合
结构:数据元素之间的关系,即数据元素之间的运算及运算规则
DS=(D,R)
D是数据元素的集合,R是D上关系的集合
逻辑结构(Logical Structure):指数据元素之间的结构关系
物理结构(Physical Structure):指数据结构在机内的表示
物理结构要满足逻辑结构的定义
算法的基本特性:有穷性、确定性、可行性

程序生命周期:
1、需求调研,得出需求规格说明书,对需求分析,划分子系统、模块、功能,并描述
2、概要分析,做出概要设计说明书
3、通过自然语言设计算法
4、编码实现,将自然语言翻译成为某种程序语言

程序与算法区别:
程序可以是无穷的,算法是有穷的
程序可以是错误的,算法是正确的
程序是用程序设计语言描述,在机器上可以执行
算法还可以用框图、自然语言等方式描述
程序是给机器执行的,算法是给人看的

过程与函数的区别:
过程没有返回值,函数有返回值

衡量算法的三个尺度:
时间
空间
可读性、易调性、健壮性
(时间和空间特性的巨大改进源于更好的数据结构或算法)