文档介绍：逻辑结构
存储结构
算法
《数据结构》的研究内容
指数据元素之间抽
象化的相互关系。
独立于计算机,是
数据本身所固有的。
数据的逻辑结构
在计算机中的存
储形式(映象)。
数据结构在计算机中的表示方法
顺序影象
非顺序影象
——顺序存储结构
——链式存储结构
用元素在存储器中的相对位置来表示数据元素之间的逻辑关系。
在每一个数据元素中增加一个存放地址的指针(pointer),用此指
针来表示数据元素之间的逻辑关系。
存储结构的描述
直接以内存地址描述
用“数据类型”描述
一维数组——顺序结构
“指针”——链式结构
数据类型:
(data type)
指高级语言中各变量可取的数据种类。是高级语言
中的一个基本概念,和数据结构的概念密切相关。
是一组性质相同的值的集合以及定义于这个值集合上
的一组操作的总称。值的集合+值集合上的一组操作
数据类型的作用
是解释计算机内存中信息含义的一种手段。
实现了信息的隐蔽,将用户不必了解的细节封
装在类型中。强调的是其所能完成的功能以及
它和外部用户的接口(即外界使用它的方法) 。
抽象特性
是对信息的一种符号表示——人们利用文字符号、
数字符号以及其他规定的符号对现实世界的事物及
其活动所做的描述。
数据(Data)
基本概念和术语
在计算机科学中是指所有能输入到计算机中并被计
算机程序处理的符号的总称——包括数值型数据和
非数值型数据(包括文字、表格、图象、声音等,
都称为数据)。
数据元素(Data Element): (也称结点)
是数据的基本单位,在计算机程序中通常作为一个整体进行
考虑和处理。
数据元素是一个数据整体中相对独立的单位。但它还可以分
割成若干个具有不同属性的数据项(字段、域(field)), 故不是组
成数据的最小单位。
数据项(data item) 是数据的不可分割的最小单位。
数据对象(Data Object):
是性质相同的数据元素的集合。是数据
的一个子集。
数据结构(Data Structure):
是相互之间存在一种或多种特定关系
的数据元素的集合。
四类基本结构
集合: 数据元素除了同属于一种类型外,
别无其它关系。
线性结构:一对一。
树型结构:一对多。
图状结构或网状结构:多对多。
ADT 抽象数据类型名{ 数据对象:〈数据对象的定义〉 数据关系:〈数据关系的定义〉 基本操作:〈基本操作的定义〉 } ADT 抽象数据类型名
抽象数据类型(Abstract Data Type) 的描述方法:
抽象数据类型可用(D, S, P) 三元组表示,其中,D 是数据对
象,S 是 D 上的关系集,P 是对 D 的基本操作集。
用伪码(不真正执行的符号) 描述
基本操作的定义格式为: 基本操作名(参数表) 初始条件:〈初始条件描述〉 操作结果:〈操作结果描述〉
赋值参数只为操作提供输入值;
引用参数以&打头, 除了可以提供
输入值外,还将返回操作结果。
描述操作执行之前数据结构和参数
应满足的条件,若不满足,则操作
失败,并返回相应出错信息。
说明操作正常完成之后,数据结构的变化状况和应
返回的结果。若初始条件为空,则省略之。
算法和算法分析
算法
算法(Algorithm):通俗地讲,算法就是一种解题的方法。
严格地讲算法是对特定问题求解步骤的一种描述,它是指令
的有限序列,其中每一条指令表示一个或多个操作。
算法的五个特性:
(1) 有穷性: 一个算法必须总是在执行有穷步之后结束,且每一步
都在有穷时间内完成。
(2) 确定性: 算法中每一条指令必须有确切的含义,无二义性。并
且,在任何条件下,算法同时只有唯一的一条执行路
径,即对于相同的输入只能得出相同的输出。
(3) 可行性: 算法描述的所有操作都必须足够基本,都是可以通过
已经实现的基本运算执行有限次来实现的。
(4) 输入: 一个算法有零个或多个输入,这些输入取自于某个特定
的对象集合。它们可以使用输入语句由外部提供,也可
以使用赋值语句在算法内给定。
(5) 输出: 一个算法有一个或多个输出,这些输出是同输入有着某
些特定关系的量。
算法的含义与程序十分相似,但二者是有区别的。
注
1、一个程序不一定满足有穷性(如一个操作系统在用户未使用
前一直处于“等待”的循环中, 直到出现新的用户事件为止。
这样的系统可以无休止地运行,直到系统停工。);
2、程序中的指令必须是机器可执行的,而算法中的指令则无此
限制。算法若用计算机语言来书写,则它就可以是程序。
一个算法可以用自然语言、数学语言或约定的符号来描述,
也可以用