第一章　数据结构概念VIP免费

数据结构基础第一章数据结构概要一、什么是数据结构：（datastructure）一般来说，用计算机解决一个具体问题是，大致需要经过下列几个步骤：1）从具体问题抽象出一个适当的数学模型；2）设计一个解此数学模型的算法3）编出程序4）测试，调整，解答。寻求数学模型的实质就是分析问题，从中提取操作的对象，并找出这些操作对象之间的关系，然后用数学的语言加以描述。数据结构也就是非数值计算的问题的数学描述，因此研究数据结构的过程也就是数学建模的过程。二、基本概念和术语数据（data）输入到计算机中符号的总称。数据元素（dataelement）数据项（dataitem）数据对象（dataobject）数据元素的集合，是数据的一个子集。数据结构（datastructure）是相互之间存在的一种或多种特定关系的元素的集合。数据类型（datatype）高级语言中的数据类型一般有三类：1）简单类型：包括整型、实型和字符型数据；2）构造类型：是由已知类型按一定规则构造而成。如数组。3）指针类型：在构造时使用一种特殊的变量――指针，主要用于构造诸如链表、树、有向图等各种复杂的数据结构。元素之间的相互关系称之为结构（structure）系统论认为：世界中的一切事物都表现为系统，系统是由相互联系，相互制约的若干部分结合而成的，具有一定结构和功能的有机整体，它具有三个特点：1）集合性（元素）2）关联性（结构）3）目的性（功能）由此可以看出，用计算机来解决某一实际问题，这一问题我们就可以把它看作一个系统来研究，数据结构的任务就是来研究每一个元素之间的结构关系。理顺数据元素之间的关系。数据结构就是元素与关系的集合。数据结构的四种基本类型：1）集合结构2）线性结构3）树形结构4）图状结构（或网状结构）数据结构的数学定义：数据结构是一个二元组data_structure=(D,S)其中：D是数据元素的有限集S是D上关系的有限集与数据结构密切相关的是定义在数据结构上的一组操作，操作的种类和数目不同即使逻辑结构相同，这个数据结构的用途也会大为不同。基本的操作主要有：1）插入2）删除3）更新4）查找5）排序从操作特性来分：加工型操作(constructor)引用型操作（selector）（查找）算法（algorithm）是对特定问题求解步骤的一种描述，它是指令的有限序列。1）有穷性2）确定性3）可行性4）输入5）输出三、数据结构（datastructure）的发展1968年美国唐.欧.克努特教授开创了数据结构的最初体系，他所著的《计算机程序设计技巧》第一卷《基本算法》是第一次较系统地阐述数据的逻辑结构和存储结构及其操作的著作。