1.1什么是数据结构
数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及他们之间的关系和操作等的学科
数据结构是相互之间存在着的一种或多种特定关系的数据元素的集合。(数据结构简单解释,见第五页)
一般来说,用计算机解决一个具体的问题,大致需要经过下列几个步骤:首先需要具体问题中抽象出一个适当的数学模型然后设计一个解此数学模型的算法,最后编出程序进行测试,调整直至得到最终答案。
寻找数学模型的实质就是分析问题,从中提取操作的对象,并找出这些操作对象之间的几何关系,然后用数学的语言加以描述。
在这类文档管理的数学模型中,计算机处理的对象之间通常存在着一种最简单的线性关系,这类数学模型可称之为线性的数据结构。
对弈的过程就是从树根(对弈开始之前的棋盘格局)沿树叉到某个叶子之间的过程。“树”可以是某些非数值计算问题的数学模型,它也是一种数据结构。
在这类交通,道路问题中的数学模型可以称之为“图”的数据结构。
1.2基本的概念和术语
数据是对客观事物的符号表述,在计算机科学中是指所有能输入到计算机并被计算机程序处理问题的符号的总称。如实数,整数,字符串。
数据元素是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成,数据项是数据中不可分割的最小单位。
数据对象是性质相同的数据元素的集合
数据元素并不是孤立存在的,这种数据元素之间的相互关系称之为结构。
数据结构:是相互之间存在着的一种或多种特定关系的数据元素的集合
主要有四种结构:
(1)集合
(2)线性结构:结构中的数学元素之间存在着一个对应关系
(3)树形结构:结构中的数据元素之间存在着一个或多个对应的关系。
(4)图状或网状结构,结构中的数据元素存在着多个或多个对应关系。
数据对象:是性质相同的数据元素的集合是数据的一个子集
数据结构的形式定义为:数据结构是一种二元组
Data_Structure=(D,S)
其中,D是数据的有限集,S是D上关系的有限集
上述数据结构的定义仅是对操作对象的一种数学描述,换句话说,是从操作对象中,抽象出来的数据模型。结构定义中的“关系”描述的是元素之间的逻辑关系,因此又称之为,数据的逻辑结构
数据逻辑结构中的定义:
数据元素之间的关系可以是数据元素之间代表某种含义的自然关系,也可以是为了方便而人为的定义的一种关系,这种自然或人为定义的关系成为数据元素之间的逻辑关系,相应的结构称之为逻辑结构
逻辑结构又分为线性结构和非线性结构;
线性结构:线性表,栈,队列,字符串,数组,广义表
非线性结构:树图
数据结构在计算机中的表示(映像)称之为数据的物理结构,又称之为存储结构包含数据元素的表示和关系的表示。
数据结构的表示在计算机中有两种不同的表示方法:顺序映像和非顺序映像,有两种不同的存储结构顺序存储结构和链式存储结构
顺序存储结构表示:元素在存储器中的中的相对位置来表示数据元素之间的逻辑关系
链式存储结构表示:在每一个的数据元素中增加一个存放另一个元素地址的指针,用该指针来表示数据元素之间的逻辑关系
综上所述:数据结构的内容可分为三个部分,逻辑结构,存储结构,运算集合
数据结构:按某种逻辑关系组织起来的一批数据,按一定的映像方式把它存放在计算机存储器中,并在这些数据上定义了一个运算的集合就叫做数据结构
数据类型是一个值的集合和定义在这个值集的一组操作的总称。
按值的不同特性,数据类型可分为两类:一类是,非结构的原子类型,另一类是结构类型
结构类型可以看成一种由数据结构和定义在其上的一组操作的总称。
同时是可分得,而且他的成分也可以是结构的
数据类型的概念并非局限于高级语言中,每个处理器都提供了一组原子类型和结构类型
抽象数据类型(ADT)是指一个数学模型以及定义在该模型上的一组操作,仅取决于它的一组逻辑特性,而与其在计算机内的如何表示和实现都无关。
一个软件系统的框架应建立在数据上,而不是建立在操作上。
抽象数据类型的定义由一个值域和定义在该值域上的一组操作的总称
原子类型:属原子类型的变量的值是不可分割的。
固定聚合类型属该类型的变量,其值由确定数目的成分按某种结构组成
与固定聚合类型相比较,构成可变聚合类型的数据类型的值是保持不变的。
抽象数据类型可用
(D,S,P)表示,D是数据对象,S是D上的关系集,P是D的基本操作集
多行数据类型是指其值的成分不确定的数据类型
算法:对特定问题的求解步骤的一种描述,他是指令的有限序列,其中每一条指令表示一个或多个操作
一个算法还有以下几个属
性
(1)有穷性:要点一:算法在有穷步步之后结束,要点二:每一步都在有穷时间内完成
(2)确定性:确定性每一步指令都有确切含义,读者不会产生二义性。并且在任何条件下,算法只有唯一的一条执行路径。即对于相同的输入只能得出相同的输出
(3)可行性:一个算法是能行的,算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的
(4)输入:一个算法有零个或多个输入,这些输入取自于某个特定的对象的集合
(5)输出:一个算法有一个或多个输入,这些输出是同输入有着某种特定关系的量
算法设计的要求:
(1)正确性:算法应满足具体问题的需求
(2)可读性:容易供人阅读,可读性好的算法能加深对算法的印象
(3)健壮性:算法具有容错性,输入不符合要求的数据,算法都能够进行适当的处理
(4)效率与低存储量需求,效率指的是算法执行的时间,存储量是算法执行过程中所需要的最大存储空间
(5)通用性:算法具有一般性,及算法的处理要求对一般的数据集合都成立。
算法效率的测量,见书籍