这两天开始准备考研了,才回到 算法与数据结构,班里就我一个人选这门了,其他都选 自然地理.要做代码,如果不选 算法与数据结构,就没有意义了.一段时间以来,都把 算法和数据结构看得很重要了.所以这次要全力,定心,好好理解.

一,从问题到程序

　　1,需求模型

　　2,数学模型

　　3,实现模型

　　程序中描述的过程(算法)

　　求解程序的阶段:

　　　　1)分析阶段(需求/数学模型).

　　　　2)设计阶段(实现模型).

　　　　3)编码阶段

　　　　4)调试和维护

　　不同抽象数据类型的主要特征由它们具有的行为决定.

二,抽象数据类型

　　1,类型:一组值(对象)的集合.

　　2,数据类型:计算机中使用的一类型,既包括该类型值的集合,也包括定义在该类型上的一组操作.如,整数作为一个数据类型,指的是在计算机中表示的所有整数及其语言中定义的对于这些整数的全部操作.

三,数据结构

　　1,数据结构,是计算机中表示的具有一定逻辑关系的一组数据.亦可理解为,‘抽象数据类型的物理实现‘,所谓‘物理实现‘,主要意图是强调本课程关心的,‘实现‘应具体到可以用计算机的两个重要的物理量(即主机的运行时间和内存的存储空间).

　　2,逻辑结构:基本元素和元素之间的关系.

　　3,存储结构:结点的表示和关系的表示.

　　集合中的元素是各不相同且无序的(逻辑结构).用顺序表,单链表,散列表等多种不同的集合表示法(存储结构).

　　一种逻辑结构往往存在多种存储结构.

四,数据结构的分类

　　1)按逻辑分类:

　　　　B=<K,R>,k:有穷集合.R:K上的一个关系.‘关系‘为二元组的集合.K上的二元组是K中元素的有序对.若 k,k‘R,则k为k‘的前驱,k‘为k的后继.

　　　　开始结点:没有前驱的结点

　　　　终端结点:没有后继的结点

　　　　A,线性结构:K中每个结点最多只有一个前驱和一个后继的结构.

　　　　B,树形结构:一般而言,开始结点和最终结点可不唯一.

　　　　集合,可看成R为空的情况,即结点之间没有任何关系.

　　　　各种路基结构的包含关系:集合结构  线性结构  树形结构  复杂结构.

　　2)按存储结构分类:

　　　　解决逻辑结构在计算机中的存储或表示,包括结点的表示和关系的表示

　　　　A,顺序表示

　　　　B,链接表示

　　　　C,散列表示,‘关键码-地址‘转换法,根据关键码的值,将结点映射到给定的存储空间(通过函数).

　　　　D,索引表示,通过建立辅助索引结构解决.索引由索引项组成.索引项包含一个结点的关键码和该节点的存储位置.

　　　　结点:数据结构中的基本单位.

算法复习笔记-绪论