1.数据结构 --- 绪论

数据 : 是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号总称。它是计算机程序加工的'原料'。
数据元素 : 是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。有时候，一个数据元素可由若干个数据项组成。
数据对象 : 是性质相同的数据元素的集合，是数据的一个子集。
数据结构 : 是互相之间存在一种或多种特定关系的数据元素的集合。	
	1.集合
	2.线性 (1对1)
	3.树 (1对多)
	4.图 (多对多)

数据类型 : 因此数据类型是一个值的集合和定义在这个值集上的一组操作的总称
抽象数据类型(abstract data type,简称ADT) : 是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。

算法的5个特性：
	1.有穷性
	2.确定性
	3.可行性
	4.输入
	5.输出

算法的要求：
	1.正确性
	2.可读性
	3.健壮性
	4.效率与低存储量需求


1.什么是数据结构
	一般来说，用计算机解决一个具体问题时，大致需要经过以下几个步骤：首先要从具体问题抽象出一个适当的数学模型，然后设计一个解此数学模型的算法，最后
  编出程序，进行测试，调整直到得到最终答案。寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言
  加以描述。
  具体问题 => 数学模型 => 设计算法 => 编写程序

    数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。
    程序设计的实质是对确定的问题选择一种好的结构，加上一种好的算法。

2.基本概念和术语
	数据 : 是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号总称。它是计算机程序加工的'原料'。
	数据元素 : 是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。有时候，一个数据元素可由若干个数据项组成。
	数据对象 : 是性质相同的数据元素的集合，是数据的一个子集。
	数据结构 : 是互相之间存在一种或多种特定关系的数据元素的集合。

	在任何问题中，数据元素都不是孤立存在的，而是它们之间存在某种关系，这种数据元素之间的关系称之为结构。根据数据元素之间的不同特性，通常有下列4类
  基本结构：
  	1.集合
  		结构中的数据元素之间除了'同属于一个集合'的关系外，别无其他关系
  	2.线性结构
  		结构中的数据元素之间存在一个对一个的关系
  	3.树形结构
  		结构中的数据元素之间存在一个对多个的关系
  	4.图状结构或网状结构
  		结构中的数据元素之间存在多个对多个的关系

  	数据结构的形式定义为：数据结构是一个二元组 : Data_Structure = (D,S)。其中：D是数据元素的有限集，S是D上关系的有限集。

  	结构定义中的'关系'描述的是数据元素之间的逻辑关系，因此又称为数据的逻辑结构。然后，讨论数据结构的目的是为了在计算机中实现对它的操作，因此还需要研究
  如何在计算机中表示它。
  	数据结构在计算机中的表示称为数据的物理结构，又称为存储结构。它包含数据元素的表示和关系的表示。在计算机中表示信息的最小单位是二进制数的一位，叫做位(bit)。
  在计算机中，我们可以用一个由若干位组合起来形成的一个位串表示一个数据元素(如用一个字长的位串表示一个整数，用8位二进制数表示一个字符等)，通常称这个位串为元素
  或者结点。当数据元素由若干数据项组成时，位串对应于各个数据项的子位串称为数据域。因此，元素或结点可以看成是数据元素在计算机中的映像。
  	数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和非顺序映像，并由此得到两种不同的存储结构：顺序存储结构和非顺序存储结构。顺序映像的特点是借助元素
  在存储器中的相对位置来表示数据元素之间的逻辑关系。假如，假设用两个字长的位串表示一个实数，则可以用地址相邻的4个字长的位串来表示一个复数；非顺序映像的特点是借助
  指示元素存储地址的指针表示数据元素之间的逻辑关系，如为表示复数z1的链式存储结构，其中的虚部和实部之间的关系用值为'0415'的指针来表示(0415是虚部的存储地址)。数据
  的逻辑结构和物理结构是密切相关的两个方面，任何一个算法的设计取决于选定的数据结构，而算法的实现依赖于采用的存储结构。

  	数据类型和数据结构密切相关的一个概念，它最早出现在高级程序设计语言中，用以刻画(程序)操作对象的特性。在用高级语言编写的程序中，每个变量，常量和表达式都有一个
  它所属的确定的数据类型。类型明显或隐式的规定了在程序执行期间变量或表达式所有可能取值的范围，以及在这些值上允许进行的操作。因此数据类型是一个值的集合和定义在
  这个值集上的一组操作的总称。例如，C语言中的整型变量，其值集为某个区间上的整数(区间大小依赖于不同的机器)，定义在其上的操作为加，减，乘，除和取模等算数运算。
  	按'值'的不同特性，高级程序语言中的数据类型可分为两类：一类是非结构的原子类型。原子类型的值是不可分解的，例如C语言中的基本类型(整型，实型，字符型和枚举类型)，
  指针类型和空类型。另一类是结构类型，结构类型的值是由若干成分按某种结构组成的，因此是可以分解的，并且它的成分可以是非结构的，也可以是结构的。如数组。
    实际上，在计算机中，数据类型的概念并非局限于高级语言中，每个处理器(包括计算机硬件系统，操作系统，高级语言，数据库等)都提供了一组原子类型或结构类型。例如，
  一个计算机硬件系统通常包含'位','字节','字'等原子类型，它们的操作通过计算机设计的一套指令系统直接由电路系统完成，而高级程序语言提供的数据类型，其操作需要通过
  编译器或解释器转换成底层，即汇编语言或机器语言的数据类型来实现。引入'数据类型'的目的，从硬件角度看，是作为解释计算机内存中信息含义的一种手段，而对使用数据类型
  的用户来说，实现了信息的屏蔽，即将一切用户不必要了解的细节都封装在类型中。例如，用户在使用'整数'类型时，既不需要了解'整数'在计算机内部是如何表示的，也不需要知道
  其操作是如何实现的。如'两整数求和'，程序设计者注重的仅仅是其'数学上求和'的抽象特性，而不是其硬件的'位'操作如何进行。

  	抽象数据类型(abstract data type,简称ADT)是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示
  实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。
    抽象数据类型和数据类型实质上是一个概念。例如，各个计算机都拥有的'整数'类型是一个抽象数据类型，尽管它们在不同处理器上实现的方法可以不同，但由于其定义的数据特性
  相同，在用户看来都是相同的。因此，'抽象'的意义在于数据类型的数学抽象特性。

    另一方面，抽象数据类型的范围更广，它不再局限于前述各处理器已经定义并实现的数据类型(也可称为这类数据类型为固有数据类型)，还包括用户在设计软件系统时自己定义的
  数据类型。为了提高软件的复用率，在近代程序设计方法学中指出，一个软件系统的框架应该建立在数据之上，而不是建立在操作之上(后者是传统的软件设计方法所为)。即在构成
  软件系统的每个相对独立的模块上，定义一组数据和施于这些数据上的一组操作，并在模块内部给出这些数据的表示及其操作细节，而在模块外部使用的只是抽象的数据和抽象的操作。
  显然，所定义的数据类型的抽象层次越高，含有该抽象数据类型的软件模块的复用程度也越高。

  	一个含有抽象数据类型的软件模块通常包含定义，表示和实现3个部分。
  	如前所述，抽象数据类型的定义由一个值域和定义在该值域上的一组操作组成。若按其值的不同，可细分为3种：
  	1.原子类型 : 属原子类型的变量的值是不可分解的。这类抽象数据类型较少，因为一般情况下，已有的固有的数据类型足以满足需求。但有时也有必要定义新的原子数据类型，
    例如，位数为100的整数。
  	2.固定聚合类型 : 属该类型的变量，其值由确定数目的成分按某种结构组成。例如，复述是由两个实数依确定的次序关系构成。
  	3.可变聚合类型 : 和固定聚合类型相比，构成可变聚合类型'值'的成分的数目不确定。例如，可定义一个'有序整数序列'的抽象数据类型，其中序列的长度是可变的。

  	显然，后两种类型可统称为结构类型。
  	和数据结构的形式定义相对应，抽象数据类型可用以下三元组表示：
  	(D,S,P)
  	其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。
  	ADT 后续数据类型名 {
  		数据对象 : <数据对象的定义>
  		数据关系 : <数据关系的定义>
  		基本操作 : <基本操作的定义>
  	}ADT 抽象数据类型名
  	其中，数据对象和数据关系的定义用伪代码描述，基本操作的定义格式为：
  	基本操作名(参数表)
  		初始条件:<初始条件描述>
  		操作结果:<操作结果描述>
  	基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以&打头，除可提供输入值外，还将返回操作结果。'初始条件'描述了操作执行之前数据结构和参数应满足的条件，
  若不满足，则操作失败，并返回相应出错信息。'操作结果'说明了操作正常完成之后，数据结构的变化情况和应返回的结果。若初始条件为空，则省略之。

  	多型数据类型是指其值的成分不确定的数据类型。从抽象数据类型的角度看，具有相同的数学抽象特性，故称之为多行数据类型。

3.抽象数据类型的表示与实现
	抽象数据类型可以通过固有数据类型来表示和实现，即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。

4.算法和算法分析
	算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作；此外，一个算法还具有下列5个重要特性：
	1.有穷性
		一个算法必须总是在执行有穷步之后结束，且每一步都可在有穷时间内完成。
	2.确定性
		算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。并且，在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。
	3.可行性
		一个算法是可行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。
	4.输入
		一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集合。
	5.输出
		一个算法有一个或者多个的输出，这些输出是同输入有着某些特定关系的量。

	算法设计的要求，一个好的算法应该考虑以下目标：
		1.正确性
		2.可读性
		3.健壮性
		4.效率与低存储的需求

	算法效率的度量:
		算法执行时间需要通过依据该算法编制的程序在计算机上运行时所消耗的时间来度量。而度量一个程序的执行时间通常有2个方法：
		1.事后统计法
		2.事前分析估算的方法

	一个算法是由控制结构(顺序，分支，循环)和原操作(指固有的数据类型的操作)构成的，则算法时间取决于两者的综合效果。为了便于比较同一问题的不同算法，通常的做法
  是，从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间度量。
    一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间度量记作:
    	T(n) = O(f(n))
    它表示随问题规模n的增大，算法执行的时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称为时间复杂度。
    显然，被称作问题的基本操作的原操作应是其重复执行次数和算法的执行时间成正比的原操作，多数情况下它是最深层循环内的语句中的原操作，它的执行次数和包含它的语句的
  频度相同。语句的频度指的是该语句重复执行的次数。
    由于算法的时间复杂度考虑的只是对于问题规模n的增长率，则在难以精确计算基本操作执行次数的情况下，只需求出它关于n的增长率即可。

    算法的空间复杂度:
    	S(n) = O(f(n))
    其中，n为问题的规模。一个上机执行的程序除了需要存储空间来寄存本身所用指令，常数，变量和输入数据等，也需要一些对数据进行操作的工作单元和存储一些为实现计算
  所需信息的辅助空间。