数据结构在计算机内存中的存储包括数据元素的存储和元素之间的关系的表示。
元素之间的关系在计算机中有两种不同的表示方法:顺序表示和非顺序表示。由此得出两种不
同的存储结构:顺序存储结构和链式存储结构。
数据结构的三个组成部分:
逻辑结构:数据元素之间逻辑关系的描述
D_S=(D,S)
存储结构:又称物理结构,是逻辑结构在计算机中存储映象,是逻辑结构在计算机中的实现,它包
括数据元素的表示和关系的表示。
数据操作:对数据要进行的运算。
数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。
抽象数据类型(AbstractDataType,简称 ADT):是指一个数学模型以及定义在该模型上的一组
操作。
ADT的形式化定义是三元组:ADT=(D,S,P)
其中:D是数据对象,S是 D上的关系集,P是对 D的基本操作集。
算法是对特定问题求解步骤的一种描述,它是指令的有限序列,其中每一条指令表示一个或多个
操作。
算法的特性
1.有穷性:有限步骤之内正常结束,不能形成无穷循环
2.确定性:算法中的每一个步骤必须有确定含义,无二义性得以实现。
3.可行性:一个算法是能行的,即算法中描述的操作都是可以执行有限次来实现。
4.输入:有多个或 0个输入,这些输入取自于某个特定的对象的集合。
5.输出:至少有一个或多个输出。
算法设计的要求
1.正确性(Correctness):算法应满足具体问题的需求。
2.可读性(Readability):算法应容易供人阅读和交流。可读性好的算法有助于对算法的理解和
修改。
3.健壮性(Robustness):算法应具有容错处理。当输入非法或错误数据时,算法应能适当地作出
反应或进行处理,而不会产生莫名其妙的输出结果。
4.通用性(Generality):算法应具有一般性 ,即算法的处理结果对于一般的数据集合都成立。
5.效率与存储量需求:效率指的是算法执行的时间;存储量需求指算法执行过程中所需要的最大
存储空间。一般地,这两者与问题的规模有关。
“正确”分 4个层次:
1.程序不含语法错误;
2.程序对于几组输入数据能够得出满足规格说明要求的结果;
3.程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的
结果;
—2—
考试点(www.kaoshidian.com)名师精品课程 电话:4006885365
评论0