数据结构学习笔记（绪论）

开场白  If you give someone a program, you will ftustrate them for a day;  if you teach them how to program , you will frustrate them for a lifetime.

1.1数据结构的起源

数据结构最先出现在美国的高德纳教授所写的《计算机程序设计艺术》第一卷《基本算法》中。

数据结构是一门研究非数值计算的程序设计问题中的操作对象，以及它们之间的关系和操作等相关问题的学科。

1.2基本概念和术语

1.2.1数据：是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合，

数据必须具备两个前提：可以输入到计算机中；能被计算机程序处理。

 1.2.2 数据元素:是组成数据的，有一定意义的基本单位，在计算机中通常作为整体处理。也被成为记录。

     1.2.3数据项：一个数据元素可以有若干个数据项组成。

       数据项是数据不可分割的最小单位。

     1.2.4数据对象：是性质相同的数据元素的集合，是数据的子集。

                      性质相同是指数据元素具有相同数量和类型的数据项。

 1.2.5数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

1.3逻辑结构与物理结构

     1.3.1逻辑结构

              逻辑结构：是指数据对象中数据元素之间的相互关系。

              1.3.1.1集合结构

              集合结构：集合结构中的数据元素除了同属于一个集合外，它们之间没有其它关系。

              1.3.1.2线性结构

              线性结构：线性结构中的数据元素之间是一对一的关系。

              1.3.1.3树形结构

       树形结构：树形结构中的数据元素之间存在一种一对多的层次关系。

      1.3.1.4图形结构

       图形结构：图形结构的数据元素是一对多的关系。

1.3.2物理结构

              物理结构：是指数据的逻辑结构在计算机中的存储形式。

              1.3.2.1顺序存储结构

   顺序存储结构：是把数据元素存放在地址连续的存储单元里，其数据    间的逻辑关系和物理关系是一致的。

1.3.2.2链式存储结构

   链式存储结构：是把数据元素存放在任意的存储单元里，这组存储      单元可以是连续的，也可以是不连续的。

1.4抽象数据类型

       1.4.1数据类型

数据类型：是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。

       1.4.2抽象数据类型

                抽象数据类型（Abstract Data Type， ADT）：是指一个数学模型及定义在该模型上的一组操作。

                “抽象”的意义在于数据类型的数学抽象特性。

            抽象数据类型体现了程序设计中问题，抽象和信息隐蔽的特性。