新手编程导论（七）

天狗

第6章 抽象之数据结构
6.1 所谓数据结构
编译时是编译期的事情，运行时是运行期的事情，这里的时可以理解为期间（运行期间），也可理解为空间(运行逻辑关于使用reg还是stack的逻辑)，
一门语言同时提供编译器，和这门语言实现的运行时解释器,一个编译逻辑，一个面向某平台的运行逻辑(针对本地机器的一般称为运行时，针对类JVM机器的一般称为解释器,所以jvm跟解释器是分开的，一个是平台，一个是平台下针对Java代码的runtime实现)，
在学习C++的运行期动态OO对象时，我们也要学习一个称为rtti的东西,,一切高级的语言机制，都可在运行期探求它的平台实现细节，如何用stack内存和reg展开,。。这样才是深克理解了高级语言该机制(因为了解了某一平台下具体实现的细节，而且是最细节的汇编逻辑，因此该语言抽象也被在高层次被体现并理解了)。。
比如C++类的成员函数，它实际上是一种变态的函数。。从他的汇编逻辑中可以看出来，，在压参时还压入一个this指针。从这个眼光来看。跟普通的cdel,fast,pascal函数都不一样，所以说，函数作为一种机制，有不同的实作品。
runtime的意思在这里进一步明显，，实际上不只执行函数要用到stack runtime和stack frame，在执行诸如堆栈队列数组链表树这些高级数据表示与组织的内存逻辑时(即运行时逻辑，这也属于运行时逻辑)，，不一定直接用到stack runtime机制，，虽然执行函数时的stack机制的是代表机器就是一种堆栈机运行时的典型。。
数组是编译期就指定的(数组大小固定，因此每个成员都被硬编码为内存地址，动态数组并非运行期数组，只是指定数组大小的是一个变量，实际上还是一种静态数组)，链表是动态运行时构造的，数组和链表都是一种存储机制，而堆栈队列数据结构是一种数据抽象机制(抽象了如何访问删除数据成员的通用接口)，数组可以摸拟这二者，当然链表也可以。。(这个道理表明，数据结构分存储数据结构和逻辑数据结构，中心是数据成员本身处理，不可能有离开数据存储地谈数据结构的道理(所以每一种抽象数据结构，必有存储机制
数组的特点就是可以下标索引，，抽象了对内存地址的需要作的干涉(只需操作索引就可操作数据)，从数组中增加删除一个数据是可能的，但数组本身业已变化，数组增删一个元素都要经过大量的重新对齐和移动操作(因为索引得视增加删除的位置重排)，，要形成一个新数组，从这个意思上看，，数组是根本运行期不可变的。它的变化只能发生在它的一个复制品上。 因为在静态期被固定了
数组的另一特点是它只存储同型数据
而链表则不一样，因为它内置了指针，没有抽象对内存地址需要做的干涉工作(对于程序员来说，这都是他们的工作，这样可以动态分配，开辟，增加删除成员)，，对数据的读写访问（我们知道，这是数据结构的中心存在意义所在）没有抽象上的索引可用，，只能操作指针和底层。。。
对链表的插入和删除是很方便的。因为只需往往改动一个指针，，所有的改变都是在这链表上发生并自更新，
树是一种可用链表和数组摸拟的抽象数据结构，，因为它内含了大小逻辑，，因此可以索引(左右索引，而不是一般数组的前后索引)，，也可指针索引

6.2 算法+数据结构的本质
高级语言编译器所涉及到的那些东西，就像OO一样，对于计算机来说，完全是一种迂回。
因为高级语言编译器的出现是为了迎合人类能读懂的文本源程序(面向行的编译器),所以它先提出一套语法,为了这套语法就造出了正规式,自动机,最终到语言本身这中间的诸多逻辑，而OO和框架(FrameWork)也是一样的道理,,计算机直接执行的是二进制,,但人类若要组织这些逻辑,就得用OO思想....因为这是人类工程的需要(对于计算机来说就是迂回了)
编程设计的本质在于将语言机机制逻辑转化为应用逻辑，完成它们之间的变换,任何语言都有算法+数据结构之说的设计，但C更为突出，因为C只有这种设计范式，相对其它语言众多的语言机制来说（除了基础流程，类型系统那些东西不说），这更像是C的设计全部，为C而生的，在用语言机机制表达应用方面，C++有“类”,有设计模式，有模板，有编译期多态，有范型，当然也有“算法加数据结构”，但C仿佛只有这种““算法加数据结构””，，，是设计的非常原始阶段和手段。

6.4 算法不是设计
（算法更多的不是代码逻辑的设计，用最小内核的流程控制比如C都可以实现算法跟数据结构），
一种算是通用的解决问题的方法,不限于编程开发
一种算法是算法设计方法,如递归
一种算法是计算机的执行方法,图灵算法,证明算法可行性
一种算法是跟某具体语言结合的数学问题的解答,如鸡免问题等
一种算法是设计算法,架构逻辑
一种算法是综合设计算法,

6.5 函数增长与算法复杂性分析
从这一节开始，我们就慢慢进入算法了，，为什么把算法放在这里而不是放在数据结构那一章呢，，因为算法是属于数学和计算机的，，跟它们的结合要更前于数据结构(虽然也严重与数据结构有关，但是数据结构是进入到计算机以后的抽象，算法是它以前的概念)
，，先讲讲什么是算法，，它的分类与有关证明
递归算法，，，分支定界，，二分法，，贪婪法，等都是用来描述算法的(它们本身不是算法，，，只是用来设计算法的方法)
程序正确性
算法的有效性包含二部分,算法的正确性和算法的复杂性,,这里讨论算法的正确性,,复杂性在前面2.2节函数增长部分讨论过了
对算法的正确性的研究用到逻辑规则，证明技术(如数学归纳法)，算法不考虑语法等其它因素,,,除非测试了所有可能的输入，，程序都给出正确的答案，这就是程序正确性的概念
如何把以上概念分解为形式定义使它具有可操作性呢？
在有输入的情况下，只要第一部分证明：若程序终止，则获得正确的答案，，第二部分证明：程序总是终止，就可以断言这个程序是正确的(二者之一成立是部分正确)
第三章讨论算法的正确性，这里讨论算法的复杂性,在假定输入值一样的条件下，，求算法的空间或时间复杂性
由于空间复杂性跟数据结构有关而本书不涉及太多的数据结构,因此在这里主要讨论算法的时间复杂性，，即步数,运算次数的单位是整数加法，减法，，等基本运算

6.6 数据结构初步引象(1)
一维数组(向量)
二维数组(包含行向量与列向量的矩阵)
表table也是二维数组，它的行是记录，列是字段
List有三种意义，VList,广义表，狭义指linked list，，普通意义下的list表是有序的,typed 的ordered的即线性表(alistis an orderedcollectionofentities/items)，但不一定是sorteded的(Asequenceis 循序而非顺序?anothername, emphasizing the ordering and suggesting that it may not be a linked list.)查找表是同型数据的无序(sorted or unsorted)有限序列。二叉查找树也叫二叉顺序树。
二叉树遍历的本质在于动态地将非线性树转化为线性表。,
线性数据结构就是逻辑上有头有尾的一对一的数据结点组成的结构,,当它用于表时，就是linear list,线性表用顺序存储的方法来存储就是顺序表sequences list了,注意线性表只指出结点有序(表的意义所在)一一对应(线性的意义所在)，至于如何有序它没有作规定，而数组是一种用下标index来体现’有序’的方式，indexied 的线性表即index list(与linked list对应)=vector，因此是一种顺序表的方式(当然index list就字眼上说并没有完全地指出它应有的限制，准确的说法是index linear list)。是顺序表最简单最基本的形式(注意数组是一种抽象数据结构)。与链式存储的单链表一样，是最基本的，因此常有sequence stack,link stack的对比（而其实数组有多维数组，链表有循环链表等）。当然这二种表都是属于逻辑上的linear list.6.7 数据结构初步引象(2)
数据结构的讨论是在抽象了数据类型之后才出现的(因此数据结构的准确含义是“计算机开发领域中的数据抽象学”)，汇编不需要变量是因为程序员包揽了内存分配，而高级语言提供变量，变量的内存分配由编译器或运行时完成，因此可在这个基础上发展基于靠近人的抽象数据结构，而OO既是对数据的一种抽象(当然，它跟数据结构对数据的抽象是站在不同角度的)，也是一种对代码的抽象
数据结构中也有文件的概念，实际上当这个文件(数据结构一般处理数据在内存中的模型)放在外存中(被持久化)就成了数据库，数据结构中也大量用到字段，记录，键等数据库概念，，在计算机领域，数据库和数据结构本来就是同根共源的，数据结构的抽象模式就是内模式，，关系数据库与其它数据库的区别在于关系数据库会返回一个集合，而不是一些特定记录，在数据结构的讨论中，频频用到关系代数的概念，比如排序线性表sorted list.它按照某种顺序来组织数据，比如<，这实际上是一种偏序关系。
List有三种意义1 linked list 2 广义表 3 (ordered) list，其中3就是普遍讲到的“有序线性表”，而sequence list=sequence order list（以顺序结构存储的线性表,区别于linked ordered list）,,,线性表除了有序线性表这种形式之外，还有sorted ordered list.即排序(线性)表。。
如 binary search tree,= binary sort tree
查找表(lookup table?search
table?)是一种无序的集合,这使得只能以顺序比较方式操作，因此我们必须对它们强加一些关系，形成sorted的,动态查找表必须动态变化以维持它的表序(即它是一种动态查找表，表是自变化的以维持某种利于查找的顺序)。。
键可以是一个记录中的某个字段，或字段的组合，单字段的以这个字段值作为键。。
（一般）树，森林，二叉树之间可以相互变换，，，树可以通过对节点的限制或修饰发展出多种抽象，比如平衡树，AVL树，B+(B_的一种变体)，红黑树。。。当然还有很多，因此数据结构实际上是一门可以无限深入的科学
如果说树是一种层次关系(树是严格分父子的)，那么图就是一种松散关系，在任何节点间都会产生关系，因此最符合现实模型。
对图的学习涉及到关系代数，线性代数中很多知识
其实要注意各种数据结构的存储结构，图的多重链表，树的最小带权路径，，图的多路查找
等等知识，这些都是高级话题。。

6.8 数据结构初步引象(3)
交换排序是置换顺序，插入排序更理应被称为交换排序。
双端队列是栈和队列的一种泛化（因为它的二头都可以出或入）。栈和队列跟其它数据结构遍历不同的是，对于栈和队列的内部是不可访问的，只有栈顶和队列头
这几个元素可以遍历到。
查找表是一种集合，是同类型数据的集合，，因为集合是一种无结构的无序松散排列（表是一对一更，树是一对多，图是多对多，那么集合对这些都没有规定，实际上有表，图，集合三种大数据结构，树是表的推广，图是树的推广，但表和树都有作为自身存在的意义和作为树和图的双重意义存在，在所有数据结构中，反而只有图才是用得最为广泛的。
用位向量可以表示集合（这有点像用邻接矩阵表示图），其它方法也可，比如链表等，，但位向量表达法在提供了位操的机器上产生的效益是很高的。
图也有根，还有无序链表unsorted 还是unordered？？连通和强连通，，，回路和路径，，环弧边，无向图是无向还是双向图，这些都是微妙差别的概念。。

天狗

6.9 数据结构初步引象(4)
线性表是最常见的数据结构和逻辑结构，然而只有图才是最常用的数据结构和逻辑结构。。
其实树状结构有天然的转化成线性结构的优势，因此也有作为线性表的树的存在(因此说树是树性表的一种推广,教学的时候完全可以从线性表引伸到树,, 树有作为线性表存在的树，树也有作为树本身意义存在的树，和作为树图意义存在的树，这三种情况都需要被讨论。)
此时从树的眼光来看这种原来是树的数据结构它还是存在父子关系，从线性表的眼光来看是变换了的平等关系.

6.10 ordered与sorted
Lists广义列表，list线性表
有些教科书混用ordered与sorted,比如二叉排序树它并非二叉有序树，当然，
为什么又有无序树，有序树呢。
Ordered表示一个接一个，顺序不可改变，如果被改变(比如一个元素后接的元素不再是以前那个了)，就不再是以前那个ordered list了，
所以如果一个unosorted表被sorted过了，它肯定不再是以前那个ordered list了(但它肯定是ordered的，因为它要维护它
线性表的特性即ordered不过它当中有些元素的ordered位置换动了而已)，而是一个新的ordered且sorted的表。
.
6.11 数据结构与抽象
(1)
程序如何分类呢，从算法和数据结构的角度看我们可以发现，数据结构加算法等于程序。
因为数据结构源于从一套相似的算法中找出操作对象的共性这个现实
而从复用来看呢，，又可以产生设计和接口就等于程序这种说法
因此这完全是不同事物的不同唯度而已。。根本没有可比性。（至少二者都可以产生程序这个概念，于是，程序=机器加电也是正确的）
OO化并不强求以靠近现实的模型来设计应用,而更多地是利用OO的访问控制以同一种方式看待代码与数据(设计代码，定义数据)
在命令式编程语言中，控制结构等等被证明为可以产生一切逻辑。。因此具备三种控制结构的语言都可以成为产生一切逻辑的语言。。
(2)
抽象完成了之后，只要不是过度抽象，那么所有后来的事情都是另外一回事了，比如抽象了数据类型，那么关于数据的逻辑都成了数据结构学了
算法并非代码逻辑，而只是附属于语言和数据结构学交界的那些东西（算法是从属数据结构的），只有设计模式才是代码逻辑和代码抽象学。。
从开发（者）的观点，我们可以把OS看成是提供API的软件抽象机制(这本书主要是从开发的角度抽象地讲解一系列专业概念)，同样从计算机开发领域的角度看，我们可以把算法看成是数据结构的附属，，因为数据结构是源于算法的，而数据结构是开发中的数据抽象，，,,因此作为从开发眼光来看的算法是数据结构的附属(因此人们说算法和数据结构是数学，计算机软件，计算机硬件三门学科之间的交叉学科，)。
在程序设计中，抽象无所不在，OO就是一种对数据和代码进行统一抽象的方式。。
在架构中，抽象也是很常见的，比如七层模型，只有解决了前面的问题，才能着手下一层更高级的问题，这是目的也是原因，，是起点也是下一个终点。
我们知道抽象的本质在于对人的简单性，比如OO的三重机制制造的抽象就在于统一数据和代码，于是产生了复用效益。抽象的本质在于远离问题，从靠近人的一
个高层角度去解决更高级的问题。
这就是抽象.

6.12 真正的逻辑数据结构只有二种
字符串这么平常，然而却需要涉及到不浅的数据结构和IO，，这使语言表达字串方面成为学习这种语言的一个重要方面。
当然，数据结构绝非仅仅数值数据结构。数据结构不仅用来研究数值，节点数据可以是任何类型。或adt
其实理解很多数据结构(data set 和data relation set)前要理解的东西就是什么是数据和数据节点，，这才是最重要的，但很多人忽略了它，那么数据节点体现了什么重要概念呢，1是order还是sorted,2是key value的分别，计算机能处理的数据节点是逻辑上存在order的，所以产生无order，即集合，有order，线性list，层次tree，，，另外，计算机能处理的数据节点是key value的，这就是计算机能处理的“数据‘和它能形成数据结构学这样的科学所加的二个traits，，数据结构绝对不是广义数据的结构，而是有一定条件的概念(我们人类目前的科学都是在一定的限制下讨论某具体问题的)。
明白了以上这样我们就可以理解一种特别的数据结构了，即hash table,首先它是key value对，如果不是，就是hash set hash map之类的东西，，这满足第二点条件traits。。。第二，它的hash，是针对数据结构来说的，hash一定要是hash个数据结构出来，而前一些数据结构是uniform的而hash table,map,set之类的都是uniform的而已。这满足第一个traits.
真正的数据结构其实只有二种，表和树，因为按order来看，前者是线性，后者是层次（我认为只有这二者才是划分和形成概念的标准），如果说硬有第三种，那是unordered的，即集合，集合才是取代图的概念，而不是图，图只是逻辑结构居先

6.12 树与图初步引象
树是图的一种特例（没有回路的连通图，树是sparse图），图的树的区别在于，树是严格分层次的(它的前驱是父，后继只能是子，因此产生出父子，节点的高，宽度，树的高，宽度等概念)，而图是任何顶点间都有可能发生关系(即存在边，存在边就叫邻接),除了树，图之外，还有森林（相比树对图的定义来说。它少了一个条件，森林是没有环，可能不连通的图,一棵树也可以是林林，但森林不一定是一棵树），,二叉树与一般树的区别在于1，一般树不可以无节点，而二叉树可以没有节点，2，二叉树的某个节点至多有二子节点，即二叉树不但分层次，而且子树也分顺序，因此对于一般树的边历过程有三种,,先（根）边历，中（根）边历，后（根）边历，，但是正是因为二叉树有左右子树之分，因此中序边历是二叉树特有的。
树和图都可以作为数据结构(主要作用在于存数据,附带一定逻辑的数据)或逻辑结构（主要作用在于表逻辑），节点可存任何东西，比如一个条件，一个值或一个结构都可以。边也可以加权表逻辑。。比如最小生成树是最小加权生成树的简称，，注意，树有最小子树，图也有最小生成树。
如何存储呢，因为用图可以用来解释树，因为决定图的特征在于它的节点，因此它也可以用跟图一样的存储结构来表示自己。但是因为树是图的稀疏表示，一般不用邻接数组存储节点的每个所有特征，,引线二叉树才这样做(因为它赖此达到一种维护它访问的能力)。
.
6.13 树初步引象
(1)
如果将树某个节点的从左到右的子树看成有序的（有左右的order之分），那么就是有序树，即ordered树，但却不是sorted的，因为只有二叉排序树binary sorted tree才是排序树（不过它不是左右子树之间的sorted，而是左右子树与它们的根之间的sortness）。
就特征的逐步放宽而言，存在，二叉树（order），二叉查找树(sorted)，N叉树(un ordered),多叉树(之所以不把N,多叉树这二者等同，是因为我们特别强调N叉树子树间不order,而多叉树根本不考虑这一点,根本不考虑左右子树之间的关系)
树为什么称为递归的呢，就是因为它的子树也是一棵树，，而这棵树的子子树也是一棵树，因此被称为递归定义的。
树的高度就是深度，因为根的深度就是高度。（因为递归定义中非叶节点就是子树，所以非叶节点的高度就是该子树的高度宽度等特征，即用根节点特征来代替子节点高度等特征）
线性表的线性“序order”和树的层次“序order”这二者有什么意义呢，这种意义决定了对于它们的遍历逻辑。搜索逻辑主要跟sortness有关，而不是orderness有关，线性表决定了它的元素顺序是有序ordered的(虽然并不一定经过排序sorted)因此遍历可按前驱的方向或后继的方向但不一定搜索一定要严格按这个顺序因为那是由sortness决定的，因此树的搜索方向可先（根）序，后（根）序。而树的遍历其实任何访问都是从根开始，，所谓中序，其实也是从根开始，只不过它处理数据的顺序是不跟它的访问顺序一样的而已。而且它是只有二叉排序树才有的。
兄弟是同一个节点为父的子节点，而堂兄弟是父节点在同一层的子节点。
通路跟回路，七桥问题解决的是欧拉通路而非回路，最小生成树是最小加权生成树的简称，但是存在另外一种最小非负加权生成树的东西，，就是最小代价cost生成树了。
在树中，有height balanced tree也有weight balanced tree,这个weight就是一个层上节点的最大值。。
作为图的树的深度优先有时要求回溯，深度优先遍历时，它从一个节点开始往下遍历时，在到达叶节点时需要重新向上“溯树”。
这就需要额外维护一个栈来记录已经访问过的节点。当访问到一开头那个节点时就“标记已访问并存入栈”，下次从这个节点的兄弟作下步向下遍历完成并作回溯时需要将其弹出堆栈，，，以此类推完成遍历（因此它是一个由树的递归特性决定的递归过程）。。
图的广度遍历用到了队列逻辑。
.
6.14 B减树
B-tree就是B减树（因为存在一个B+树所以会导致这样的误解，实际上并没有B减树这个概念存在，-号只是一个连字符而已也可写成B_），也不要跟二叉树binary tree混淆了。
那么什么是B减树呢，一般说它是Bayer’s tree的缩写（bayer是这种树的创建者之一的名字，另外一种最常见的命名方法是b=broad,bushy,因为这种树所有“外部叶节点”在同一level上聚 集）。它适用于树的内部节点被频繁访问，但又一般不常访问这些节点以下 节点的情况，比如计算机的二级存储器硬盘等设备，常以结点为目录，叶节点为文件，，一般我们频繁访问目录但又不常深入最终每个文件。
实际上b减树也是要求一定的balance的(有人也说B减树的B代表balance,不过这样的话就与普通的平衡树相重意义了所以并不常采用这种),,它是一种动态查找树，因为需要在每次update后都动态调整它的节点情况。只不过它并不需要作特别频繁的rebalancing动作，因为B减树将外部节点维护在同一层次上这个特点使它只需要只很少的调整便可保持balanced。
那么B减树到底具体是如何一种数据逻辑呢？它到底如何使保持平衡只需很少的调整呢？更重要的是，B减树到底有什么用呢？
首先，这种树的某个（或每个）“内部非叶节点”的下层子节点(直接子树)是数量可变的，而且在一个区间里变动（我们呆会再来讨论这个所谓的区间），这个非叶节点维护一堆elements和pointer,其中elments用来区别各个子树的取值范围，比如这个非叶节点有3个子节点为根的子树，那么它需要维护2个 (子节点数-1个)elments，假设为key1,key2，那么第一个子树的所有值都小于key1,中间子树的所有值都在key1和key2之间，最右边子树的所有值都小于key2(当然，这是N叉树，3叉树，这里不是说二叉树的左右)，很显然地，key1,key2这些elments是sorted有序线性表，那么points部分呢，它指向每个子树..有几个子树(子节点)就有几个pointer. 所以，每个内部节点维护（该节点所拥有子树数-1）个的elements和（子树数）个的pointer. 叶节点在同一层上，没有element也没有pointer.，不带任何信息。
现在来讨论那个所谓的区间，以m为order的B减树(称为B-tree of order m)，再设n是一个内部节点允许的最少节点数，那么那么区间就是[n上界,m下界]，以这种区间为表征的B减树一般呈现出以下特性
（1） 每个内部子节点（只要不是作为该子树的根或叶子）都至少有m/2个子节点；
注意，最多m,最少m/2;此时n相当于m/2
（2） 每个内部子节点(如果它就是作为子树的根并且不是叶子)那么最少可以有2个子节点；
这说明，该内部节点最大子elments数可以为m或m-1,最少elements数可以为m/2或m/2-1(n=m/2或n=m/2-1);
(3)每个内部子节点(如果它是叶子)，，，那么不带任何elemnets或pointers
所以，“子树数-1个elements”,“子树数个pointer”,“叶节点不带任何信息”，“n-m的区间所体现的上面三点”，，这些都说明了什么呢，这些特征都赋于了这种树什么样的特性和能力呢？
我们可以看到，如果内部节点不是作为最终叶节点，那么它(要讨论的这个内部节点)的子节点(它的下一级子节点)个数至少是半满half full的，这意味着，在[m,n]区间内(或称[m/2,m])二个半满的内部节点可以进行合并形成一个合法的新内部节点。一个全满的内部节点可以分离成二个合法的
新内部节点(只要父节点中可以容纳这些新子节点就可以)，从这层意义上，的确不需要太多的高度上的平衡。
更多的关于这种树的删除，插入算法可以从这层意义上引申而来.

天狗

6.15 图初步引象
在数据结构中，我们一般是从最普通的情况谈到施加了各件条件和限制的情况），比如有向图是无向图的一种特殊情况（施加了有向这个条件，而无向图是一种更一般的图，因此图论中一般是谈无向图及遍历等操作，再谈有向图及其特性。(特别DAG)。
线性表是数据项平等的集合（抽象数据的最高境界最一般情况是集合,因此在对各种ADT进行定义的时候都涉及有集合），无论对其进行什么操作，只有维护一 个线性关系而不管它是无序还是有序的，就是线性表，而树的各数据项是有层次level的，无论对其进行什么变换，只有作为树的眼光从根向下来看，它总存 在逻辑意义上的父子，这层逻辑意义是作为树的意义存在的，在对树的各种操作中都考虑进去了作为处理时的因素的)，
因此从逻辑意义上来说，树是线性表的推广,,,图却不是树的推广,,,因为虽然它也处理数据项集，但它处理的是数据项间连通关系而不是地位关系，在其各种存储表示和后来高级逻辑中都会加入邻接考虑。
如果说其它数据结构只有数据项集，那么图不但有数据项集，而且有顶点连通关系集。参见对其ad t的定义就知道了,,而显然连通关系并非前驱后继关系，，在关系代数中，，存在有全序偏序对称自反等关系。。
也即在图中，结点的地位关系我们不考虑，不存在线性平等也不存在树型父子，而是不考虑这样的地位关系,这一点上它像集合，（集合，是不考虑结点之间地位关系也不考虑连通的），图只考虑一种称为连通关系的不伦不类的关系，这一点上它区别所有的数据结构，它的二个顶点间可以连接，这一点跟树相同，但是顶点并不经常用作存储数据用，这一点又跟树不同，树的二顶点存在的是地位关系，而图的二顶点要处理的是连通不连通关系。。
因此我们规定，逻辑数据结构只有二种线性和非线性，只要不是线性，那就是非线性，而不管它是节点地位关系导致的非线性，还是其它关系，比如连通不连通导致的非线性（其实这二者无关，因为图也可用矩阵来存，，而矩阵，虽然是一种非线性结构，但以某种眼光看，它又是线性的）。
数据结构也可是逻辑结构，树可作为数据处理结构也可作为逻辑表达结构比如流程，因此图不但是一种数据结构而且还是一种组合数学中的离散结构(比如拓朴学就是关于有向图的)。。。.

6.16 树的平衡与旋转
一般教科书把广义表跟（多维）数组放在一起讲解，是因为有时泛意义上的数组就是广义表的一种。
如果你知道函数对于结构化程序设计的重要性的话，那么你也会明白堆栈对于函数调用逻辑的重要性，所以理解结构化程序设计范式的重要手段是理解堆栈这种ADT。
相比线性表O(n)的复杂度来说(输入的元素个数是最主要的影响因子)，对二叉树的各种操作（插入，查找删除）效益直接受制于高度，即h = O(logN)，即树提供了O(logN)的复杂度，其中N是节点数，（二叉树中）我们并不直接把N作为影响操作效益的因素，h才是，因此需要对height进行balancing才能控制操作效益。
BST的构造是严格取决于待输入系列的，当待输入系列本身就是一个sorted的系列时，那么当这些序列被用来构造BST时，它就是会退化成对应的“链表”。在操作上会失去树的优势。
一般存在“节点的深度”，“节点的高度”，“（子）树的高度”这三种说法，节点的深度是从根开发，到这节点为止的那条唯一路径的长，节点的高度就是从节点出发，到这个节点能到达的某个叶节点的最长路径的长度，因此如果这个节点是内部节点，那么其深度就是其所在层次（叶节点时为0，不存在时为-1），其高度就是从这个内部节点到与它相连通的最长路径的那个叶节点的长度，当为根节点时高度最高，当为叶节点时，高度为0，而树(或子树)的高度就是以此为根的那个树或子树的节点的高度。
实际上avl树只是自平衡二叉树的一种，高度差为一是这种树的最古老定义（self balanceing并不仅仅是height balancing 动作。而AVL仅仅是balanacing the height），还存在其它不以height的调整为其平衡方式的树，比如红黑树，但是只有AVL树是严格用平衡因子去定义的(因此是“平衡”的最正宗意义所在)，而红黑树不是，因此红黑树不是平衡二叉树，实际上它故意允许一定程序上的不平衡。
红黑树不是平衡二叉树但它“保证”2*O(logN)的最坏情况下的平衡度（人们往往根据这个原因把它归为跟AVL一类），AVL树是1.44*O(logN)，这二种树只“保证”（注意只是保证）最差情况下的下界为1.44*O(logN)或2*O(logN)，称它们为平衡树不是因为其内部是不是极力在保持平衡还是不是，重点在这里（最坏情况下保证了多少的平衡度），，综合考虑插入，查找，删除等操作来说，红黑树的效益要好于AVL，因为AVL是严格平衡的因此只对查找intensive。查找时只需向上查找1.44*O(logN)个节点就行(经过AVL平衡的树只需对height bounded at 1.44*O(logN)个节点进行处理)。。
一个节点的平衡因子是左右子树根节点深度之差(注意并非高度之差)，因此不要跟这个节点所处的深度本身搞混了，一个只有左子树无右子树的树，它的树根的深度是0(树根的高度越到根越大，树根的深度(相对整树来说)永远是0空树为-1,这个深度并不影响树根的平衡因子)，平衡因子是1(只跟左右子树的深度有关)，因为右子树不存在，深度为-1,（而左子树深度为0）,因此它们差的绝对值为1,,即平衡因子为1.
在建立AVL树（向一棵普通意义下的binary sort tree进入插入一系列key码）时，边插入边判断（插入点的平衡因子是否导致了不平衡），在发现因为插入动作导致的不平衡现象时进行rotation.，以维护其平衡性，直到所有的数据插完，这树依然维持binary sort性质（因此称sort tree为查找树，，即查找特性intensive的，作为数据结构的树，其实它的本名最开始是sort tree然后才是search tree，search tree一般有二种，第一种是每个节点都含key 和value的，所以它的每个节点都包含数据，而有些search tree只有叶节点含数据，其包括根在内的内部节点都用来search,只包含有key）和height balanced 性质。
那么怎么样进行判断并在需要的时克rot(根据情况不同有时是二次rot)呢？ 在这之前，我们需要规范一些概念。1.rot所涉及到的主体（插入点和支点privot）2,最小不平衡子树。3, 扁担原理。
最好的方法是举个例子。
比如我们将考虑把{20,35,40,15,30,25}制造为一棵binary sort并height balanced tree，，当插入20,35时，20为根(第一个插入的当然作为“整棵树”的根)，35为其右子树（因为binary sort要求它作为20的右子），当考虑插入40时，40>35也应该被插到作为35的右子树，此时虽然binary sorted了，但是却不height balanced,因为随着40的插入它将这(整棵)树变成了不平衡的树（明眼人一看就知道这属于明显的四种不平衡情况中的RR型不平衡，当然为了学习的目的我们还是打算仔细地说明一下，而且存在比这样的仅仅由三个节点构成的RR型不平衡的情况更复杂的情况，需要我们考虑一套更通用的处理方法，在这里第一个R是指整树的R，即35，第二个R是指整树的R35的R，即40，显然地，40节点处的深度为2，35节点处的深度为1，20节点处的深度为0，但在这样的树中35没有兄弟，整树没有左子树，而40也没有兄弟，即35没有左子树，这导致三个节点的平衡因子不一样，我们从上到下再一层一层考虑一遍，，首先拿20来说，它的右子树即35深为1，而“整树”左子树不存在为-1（这就是第一个R，因为只要左子树为-1就可能产生深度上不平衡的剧变开始），因此20平衡因子为2，请时克提醒自己牢记这是棵二叉树因此只有L，R的情况需要被考虑，，再看35的平衡因子，40作为35的右节点也作为整树的叶节点，其深度为0，而35的左子树不存在为-1（这就是第二个R，这里讨论的是35的R而非跟前面那个作为整树R的R，，这第二个R的左子树也不存在，因此提出这个R，，因为它也有可能产生深度上不平衡的剧变）,因此差绝对值还是在1之内，既然出现了不平衡，而且我们也知道为什么不平衡(就是整树根处平衡因子超出了1违规了，，由于前面那二个RR，终于在这里产生了真正的剧变)。那么接下来就是处理掉这个不平衡了。我们不妨细化这个不平衡到一个称为“最小不平衡子树”的地方。然后再考虑处理之。
即从插入点40的眼光来看，我们可以找出一个 “最小不平衡子树”， 不平衡的地方一定发生在这里(这个“最小不平衡子树与插入点相关，因为它就是距离插入点最近，而平衡因子却产生违规的第一个节点为根的子树”)，我们需要对其进行平衡处理主要在这里进行。(在上面的例子中，是“整树“作为“不平衡子树”。因为20处出现了违规而且那是整树的根, 这里提出了20这样我们就可以开始着手解决开篇提到的处理主体的问题，即一步一步导出“最小不平衡子树”这个概念相关的插入点和支点，下面我们谈到扁担原理)；
对这个以20为根的“最小不平衡子树”的处理涉及到“扁担原理”，在用扁担挑东西的实践中，如果前面重我们就把支点向后移动，如果后面重我们就把支点向前移动，（虽然都是以“支点”移动，但挑扁担中是移动，支点是我们的肩膀，在这里我们是作二叉树的平衡处理也称为“旋转”，那么树旋转中的“支点”呢，是不是也可以找到能类比的概念呢？是不是就是最小不平衡树的树根呢？），首先我们要明确提出“最小不平衡子树是为了确定作平衡处理的范围”，而找出“支点”却是另外一件事,(与找最小不平衡子树的目的不同，找支点是为确定从何处为轴进行旋转，我们找出了最小不平衡子树并不意味着这里的“支点”就是最小不平衡子树的根，-------其实上面情况中的支点即RR的第一个R35,,我们能找出它，是因为在RR模型中，这样的模型所在的最小不平衡子树中必定存在三个节点，即由“最小不平衡子树的根节点”，“根节点的右节点也即第一个R”，“再就是第一个R的再下面一级R即第二个R”这三者组成的模型中，“支点”就是第一个R（而不是最小不平衡树的根），上面问题中，显然35才是那个“支点”，至此我们找出了支点，接下来判断哪里重的问题)，“重”即“支点需要往支点的哪个方向移动”这个逻辑。
那么究竟往哪里移动呢？根据挑扁担原理，当然是往重了的方向移动，但这里有二个“重”的逻辑，首先第一个，我们知道20不是支点，20的右子树深1,而左子树深-1，这里存在一个以20为中心但左重右轻的情况，那么它是不是就是“重”的意义所在呢？显然在这里是右边过重了（平衡的情况是要么左子树大右子树一，要么右子树太左子树一，这里却大了二下，重了二下），如果这里是“重”的意义所在，支点就需要往轻的地方即左子树方向移。
再来看第二个重的意义，在RR模型中，如果说第一个R是支点，那么显然地比起上面提到的第一个“重了”的意义来说，这里的重是指代第一个R的父节点平衡因子过大为2，而R的R即第二个R为0,这也产生了左重右轻，（RR模型中，第一个R的父节点是产生违规的所在，正是它带出了RR，这三者由于旋转的需要又产生了“过重”，又需要找出一个“支点”进行平衡处理,这个道理也很自然，而且找出的支点是严格以平衡因子来决定其左轻右重或右重左轻的），但是显得有点蹩脚，因为这里的支点并不严格相当于现实生活中挑扁担的支点，，这里的支点完全是从一种模型中比如RR模型中选中的第一个R），这虽然成立，然而，以这样的意义导出的支点再层出的“重”不是上面第一个意义的直观的含义，是不太符合现实中扁担水平移动那么简单自然的道理，这里的重是考虑了“R的父节点”+“第一个R”+“第二个R”的，因此是一种有层次的树的模型（而不是对应于扁担加扁担二边的重物那样选肩膀就可以作为支点的模型，因为我们上面谈到的第一层重的意义不是支持支点移动的意义所在，，这里的是只需要从RR模型中选择前一个R作为支点，而且其旋转是一种左倾主义的旋转）产生的“非水平过重（从树的旋转图中可以明显看到）”。。。
但反而这里的“重了”才是“重”的真正意义所在， 在这第二层意义下，我们再看详细的例子就会理解它们了。
这样我们就解决了开篇提到的“扁担原理”，综上所述，我们讨论了RR的情况（如何判断违规以及如何作重平衡处理），，下面谈到的是LR的情况了。请自行理解。
.
6.17 完全与满
Vector之所以称为index list，，我们知道index是索引式存储，list是逻辑结构，于是四种存储结构和四种逻辑结构可以组合到16种组合方式。而index list正好是这其中的一种。
满二叉树的概念容易弄懂，而完全二叉树（二叉树都是从左到右有序的）这个概念实际上并不突出“编号”，它表现的是这样一种树：如果在某一层上，左边的节点为空，那么（在这个节点）右边就不能有节点，无论是这个节点右边的节点是个兄弟节点还是堂兄弟节点。所以满二叉树一定是个完全二叉树，而完全二叉树不一定是个满二叉树。。
树的遍历分先序，中序和后序，又分递归遍历法和非递归遍历法，故有6种遍历方法(也许只有前序才能递归？因为它是根，只有根才有递归意义？)。 当把对树的递归遍历转化为非递归遍历时需要一个辅助栈外加几个循环(我们知道加栈是递归算法转化为非递归的通用手段之一)。
完全二叉树中的完全跟完全(无向)图中的完全以及完全有向图的完全意思是不一样的，前者并不是一种规则形状(比起满二叉树来)而后两者是规则情况。
因为连通图对无向图有意义但对有向图却没有意义，因此对有向图引入强连通分量的概念。
.
6.18 多路234树与红黑树的导出
数据结构间都是有联系的，比如234树其实可以导出红黑树也可导出B树。
红黑树也是一种二叉排序树，因此一方面保证了查找效率（中序遍历时可以快速到达根部），另一方面，它也保证“最深的深度不大于最浅的深度的2倍”，这使得红黑树有一定程度的balance 特性，因此对于查找之外的另外操作，它也有很不错的效率。
红黑树主要是通过为每一个节点着色来达到以上特征的
1． 首先一个节点要么是红要么是黑只有二色可以被用来着色。
2． 根节点默认为黑色
3． 对于叶节点来说，不管它的父节点是黑色还是红色，一律着色为黑色。（每一个叶节点我们都可以假设它是一个内部节点因此有有二个不存在的子节点设为NULL）
4． 对于任何一个节点来说如果它是红色，那么它的二个子节点都为黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点，因为从叶子到根的路径是唯一的，也即它就是从根到这个叶子的路径，因此它是这个叶子的深度)
5． 高度方向上（注意这里不谈到具体的高度，而是指高度方向上），从任一节点到其每个子孙叶子的所有路径都包含相同数目的黑色节点。
以上五条特性导致了
深度上，“最深的深度不大于最浅的深度的2倍”， 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。
我们来推导一下上述性质，并规范一下“从节点到根，从根到节点，从节点到叶节点”这些说法的准确含义。(注意有时候高度就是深度，当一条边的层次决定它有多少个点附着上面的时候，这也就决定了它的高度和深度具有同一性)
.
6.19 快速排序思想
快排是一种交换排序，这种交换发生在待排序列本身之上，首先，将序列按中间位置分为二部分，随便从整个序列中取一个临时成员，这个成员就是“待排”的对象，这个待排对象完成它的一次排序后，那么整个快排也就完成了，因为它最终到了它应该被排在的位置。
取出这个待排元素后，以中间位置为基准，分别以从左趋向中间，从右趋向中间的顺序找二个对象与这个待排对象比较，，，这所谓的二个对象是满足条件的(从左趋向中间找的元素要大于待排对象，从右向中间找的元素要小于待排对象，首先是从右向中间找，然后才是。。)，而且可能有多个（显然在二边可能会有多个大于或小于待排对象的值），，所以这个过程要持续几次，，这个待排对象才能最终到他应该去的位置。
那么这是一种什么样的“交换”排序呢，我们知道待排元素所在位置空出后，，从右边找的值填充（右端第一个大于待排对象的值）这个位置后，那么这个值所在的位置我们置空它，到这里为止，待快排对象原来所处的位置被填充，，只是它的值尚未被放入一个确定位置，而且，这里又空出来一个位置，，就是在右端比较的那个值填充待排对象原来空位后空出来的位置。
现在在左端进行与待排对象比较的过程，同样在找到第一个小于待排对象的对象后，将这个左端这个空出来的位置空出来，将这个值填入上面右端比较时空出来的位，那么到现在为止，第一套左右值被找出来了，而且到现在为止，待排对象没有被置入一个位置（因为只是比较了第一套左右值），而且左端又空出来一个位置(但是此时还不是结束快排的机会，因为还存在其它的左右值对可供与待排对象比较并产生新的空位—左边或右边的)。。、
那么在进行第二套，最后一套左右值比较时，一定最终会多出一个左空位或右空位，此时将待排对象置入，，就算完成了快排。
.
6.20 数据结构之数组
数组是一种顺序数据结构，它本身独立作为数据结构来用时，也是一种线性结构，然而它用来模拟树时，或用来实现其它数据结构时，那么这些形成的数据结构就谈不上是线性结构了(当然作为底层的数组它还是顺序的)。。
线性是针对逻辑数据结构来说的，数据结构可按逻辑结构和存储结构分类，当数据结构按逻辑来分时，有一种是线性的，因为数据结构总有结点，线性数据结构中的结点存在线性关系，即每一个结点都有且只有一个前驱和后继，这种现象可用一种关系数学的表达符来表达(关系数学是关系数据库的数学基础，而计算机的数据结构学跟数据库学又是相通的)。。当然，头结点和尾结点除外，与线性对应的当然就是非线性了，比如树，除了根节点作为没有前驱的之外，包括根节点的任何节点却都在逻辑上（作为树的逻辑）有二个后继，还比如图，任何一个节点都在逻辑上可以包括多个前驱和后继，，，逻辑上都有前后之分只是线性的是一个对一个，而非线性的是一对多，或多对一。。
(下面我们用结点来表示逻辑数据结构中的独立项，用节点来表示存储结构中的独立项,用记录表达索引逻辑的独立项，这是三个完全不矛盾的词,)，
当数结按存储来分时，有一种是顺序的，即它申请了一块连续的内存来构见自己(至于它是用这内存实现了线性的还是非线性的逻辑上的数结我们不知道)，，数组用存储结构的相对位置来表达它的逻辑结构（这就是索引），，数组可以独立成为一种抽象数据结构(这就是普通的以数字为下标索引的数组)，，也可以用来实现更高级的抽象数据结构(比如树)。。
按存储来分时，还存在链接型数组结构，索引数据结构，离散(散列)数据结构，其中顺序的当节点没有使用完全部空间，它就显得有点浪费，而其它的还行。。下面一一介绍。。
链式的很普通，索引式的就是系统(你的应用逻辑)维护一张索引表，里面有各个记录(我们称要索引才会有记录)的记录，比如一个记录的长度，存储位置,等，通过查找表，就能找到记录。
而散列的，系统维护一个函数而非一张表，函数体的逻辑计算出“记录的存储位置”和"key(KEY就是索引逻辑面向用户的一层)"之间的对应关系。。
所以无论是顺序，链式，散列，索引表，我们都是在进行一种最终到记录的存储位置的索引工作。。数组名[下标]这样的一个形式，用计算机的眼光来看是内存地址，用人的抽象来看是索引工作。。而无论是顺序数组，还是链式，索引，散列，都是通过某种抽象形式(下标，，全局表，函数)来最终寻找到内存地址。。。
这个道理就像，我们通常不用&变量的形式来获得指针的意义，而是用*，因为&是面向内存的，而*是面向用户的抽象.

6.21 数据结构的抽象名字
在C中提供了很多支持数据结构和算法的元素，比如数组，链表，指针，struct,typedef,相比其它语言，c还提供了比其它语言的更好的支持数据结构的语言机制。。特别是，C中的一些语言机制，如位移(其实大都机器提供的位指令并不直接操作位，而是对整个字节进行位操作，进而间接控制所需要的位，我们常常通过对原字节进行位移的方法得出bit mask，再将这个bit mask跟原字节进行与，或，异或，最后得出需要的效果，比如提取1位，消去0位，颠倒特定位)，跟搜索算法中 特定一些算法直接相关，，相比之下，其它高级语言的数据结构都是基于高级语法结构的.甚至于像lisp这样的语言就将adt内置为其一级类型。
算法源于用计算机去解决实际问题，对由研究算法过程中出现的数据结构问题的研究也是一个很重要的工作，特定数据结构和作用于其上的算法们，就称为一个adt..
有时，上层的抽象adt可以有自己的一套算法独成一种adt,与它们的子adt一样，，，，有时，adt之间进行某种意义上的组合形成新的变种adt,,,又有自己的一种算法，如果组合了2种adt,那么就是一种带有2种意义的adt,有时，一种adt以另一种adt作为实现，自己作为一种抽象，，这样的方式演化成一种新的adt.我们必须明白这所有抽象叫法之间的关系，明确他们其实所指的东西有很大的不一样。。而且要明确这些叫法之间的特指与泛指的层次关系。。谁由谁通过谁抽象得来。
我们一般称线性表为list,或者sequences,但其实后者比前者意思更清楚一点，因为一般list就是指linked list,这字面上的相似给我们理解造成了麻烦，而sequences正好指出了线性表的二个方面，(1)，sequences这个词意思是序列，list不但是一种序列，它更是一种有序序列，即ordered list,这就是说，前面一个元素是接着后面一个元素的，可由相邻的节点按一定逻辑到达下一个元素，虽然list不一定是sorted list(各个节点按数组顺序或字母顺序排列)，但它至少是ordered list,(2)，sequences很好地与linked list在名字上区别开来,它跟linked list是泛指和特指的关系，除它之外，数组，集合，队列，堆栈这样的adt都是list.
关联数组包括普通数组，关联数组是一种可以被称为广义数组的数组，我们知道关联数组是key value索引对，只是它的key可以是任何类型，而普通数组只是interger,,,关联数组有很多抽象，甚至只是别名，比如在smalltalk,objectivec,.net,python,realbasic中被称为dictionaries，在perl和Ruby中被称为hashes，在C++和Java中被称为maps,在common lisp和Windows powershell中被称为hashetables,在php中存在关联数组，只是索引被限制成整型和字符串，这就变成普通数组和字典了，在lua中唯一只有关联数组这种数据结构，被称为table,这也是关联数组比较正统的称法之一，
我们知道集合也是一种关联数组，不过它把key value对中的value给忽略了，把key作为value,从有keyvalue对这一点来说它像关联数组，另外，它的索引就是1到n的某个子集，从这一点来说又像普通数组，联系一下bit vecotr.
数组跟向量这个说法的关系是什么呢，其实向量vector一般被实现为动态数组dymic array，我们知道静态数组的空间是在编译期被分配的，那么动态数组就是用malloc函数在运行期构成起来的数组逻辑，我们知道数组能线性时间随机访问，但是不好重建和插入，因为需要移动插入点后的所有元素，比起linked list来它的索引字段并非指针，而是直接对应内存位置的硬编码索引，因此比不上linked list在发生插入时可以仅仅通过转变指向的方式就可以实现数据结构内部的重建。。而动态数组就是这样一种在运行期有优化了的重建能力的数组逻辑。。
vector的学名叫向量，也即数组index list的一种,linked list也即链表而非索引表,跟数组有关的不只向量，还有队列，堆栈关于数组的表示，甚至还有树，图,矩阵(一种多维数组，C语言中把foo[m][n]看成是foo[m*n]的一维数组)，关联表等，除了数组是实现之外，，其它的叫法，它们有些不是指同一个东西(比如向量跟矩阵是不一样的东西，数学上的向量是矩阵中某维为1的情况下的子矩阵，是构成矩阵的量，向量是向量空间的概念，而矩阵是线性空间的概念，不过他们同构，于是在运算上涉及到了一起，数据结构上，一般vector就是一维数组，而matrix是多维数组)，，有些是一层一层的抽象关系(比如vector是index list的一种，index list又是顺序列表的一种,图有一种形式是树，而树又是bst的基础)。都是建交在C数组这个语言要素上的抽象(前者是实现，是存储抽象，后者是高层抽象叫法).

天狗

6.22 真正的ADT
在讲解算法与数据结构的教科书，有一种语言抽象机制屡屡被谈到，这就是ADT。
类是真正的数据，，比类的成员数据更能代表数据的意义，我们的程序就是一个一个的数据，类是用用户的观点来表达现实生活中出现的各种各样的数据的最好方式,因此会有面向对象数据库的出现(数据库技术中，关系模式的下表达的数据给人的引象似乎是它是为专门的数值数据而建立的)
ADT就是指封装了事物属性跟作用的指代物本身，它的属性和作用是ADT之所以为ADT的意义所在。即数据类型不再是基本类型，而是结合了数据跟代码的抽象了的模型（是一种数据类型）
人脑往往不适于长辐记忆，因此也需要对象来表达一些数据(类型)或事物.(抽象抽取对象的可用部分)，再在这里抽象上构建更为高层的抽象。也即，从问题到解决不是一步而就的，而是一层一层通过OO来建立抽象达成的，这就是多范型的“方案领域”和“应用领域”的概念。
多范型开发让你在高于面向对象的范畴里看待软件工程,所以真正的编程学习过程是要明白设计在先，这是基础的思想，然后去学习编码，，（以上二点都是方案领域）然后再去研究编程领域对现实问题的解法（这就是应用领域）
而且如果你知道可复用和可扩展对于软件工业来说是多么重要的一件事情，，，你就会知道面向对象是多么好的一种机制了(面向对象和面向构件，面向构件可以不用对象的方法，，但是很明显面向对象和面向构件都有一个共同点那就是它们都提供了可扩展，而这就促进了可复用)
数据接口是另一个很重要的概念
接口实际上就是将要用的部分作为某个接口提取出来(就是定制要使用的实现的某个子集而已)，而所有实现就是接口下的所有代码,即数据本身，故其实数据与数据接口是分离的
设计模式不致于使我们声明对象的过程变为硬编码，，，这样就使得整个软件的对象生成是动态的，这个过程就如同动态分配内存，寻求一种好的方式来组织类的过程称为设计模式或策略
接口这个概念其实无比自然，无论是为了隐藏实现的安全考虑，还是为了更好地让这些实现为用户所用这个方面来说，接口都是必需的，
接口几乎改变了现今我们开发软件的方式
举个例子，在现实生活中，经理人可以卖票，，，个人可以卖票，国家也可以卖票，，在面向对象的范畴里(注意这里并非指某个具体的面向对象设计)，我们一般是把国家，个人，经理人都各声明为一个对象，再为它们各自添加一个“卖票”服务，，但是事实上，我们需要的仅仅是卖票这个服务，(如果这个服务被包含在一个发布的第三方代码库中为我们所用)，我们只需提取这个可用部分，，而不是要知道提供这个服务的各个提供者的细节(还好上面只是列举了三个对象提供了这个服务，，然而现实生活是复杂的，还存在成千上万个对象也可以提供这个服务)，，因此，对于复用者我们来说，我们需要的仅仅是卖票这个服务，而不需要知道卖票服务这个背后的情况(而且，对于发布这个第三方代码库的第三方来说，这可以更有效地隐藏它的实现细节)
接口就是把我们所需要的对象部分封装起来提供给我们，而把我们压根不需要知道的关于对象的细节隐藏，，，也就是说，，接口是关于一个对象如何能被使用的形式的封装者(一个对象可以有多种形式被使用，因此可以一个对象提供多个接口)，是真正的对象(实现)和外界复用的包装器和桥梁，也称适配器(即接口就是直接面向使用的中间件,或封装了给二个不同架构提供适配作用使它们能协作运转的中间逻辑)
.
6.23 Vector的观点
vector就是数组的数组，我们知道逻辑上的多维数组必须转成一维数组的方式被存储，C中的一维数组是地地道道的数组，，这个意义上的数组是实实在在的，，因为它们是按内存线性地址存储的，，所以明显地，，C语言中的其它泛数组的adt都是抽象的，，从C用一维数组实现多维数组这个意思上，可以看出C语言的确是面向底层的，，它企图用底层解释一切。由于它的这种作为，导致了表示方式上的一些多义性，比如多维数组的指针跟元素的表示混淆不错。
C中泛数组有普通多维数组,动态数组和vector,其中又以vector最为典型，我们知道，多维数组要转为逻辑等价的一维数组，，有三种方式，，1，row列优先，这就是C的方式，，比如foo[3][4],它有三行4列row,它先每一行排3个，再4列,,2,行优先，这也就是pascal的方式，但是这二种方式都有局限，因为它们只能实现为方形规则的数组，要突然这种局限就是vector的事情了，
3,,就是vector方式，，C标准库中倒是没有一个vector,我们讲c++的stl中的vector,一门语言要模拟多维数组，必须要达到一种“多维数组就是数组的数组”这样的抽象，而vector就是这种思想的本质，，因为3维数组是2维的，这就是说，3维数组是2维数组的数组，而由3到2,就是把3维中的其中一维标准化了,,缩为1了，，这正是vector的思想，不要把线性代数中的矢量跟这里的混淆了，但在线性代数中这样的比较有巧合性，比如矩阵(对应多维数组)是由矢量(某维缩为1的矩阵）所组成的，，矢量就是数组中的数组了。。比如foo[3][4][5],可以是:
(1)一个下标为3的一维数组，，每个元素都是[4][5]的二维数组；
(2)..
(3)..

6.24 真正的数据结构
数据结构是什么？它是组织内存中对象或基本类型数值(primtive types)的形式，为了更好地组织和使用这些对象而慢慢发展起来的固有形式，惯用法(idioms),
数据分类与ADT
基本类型数值是没有构造函数的，而Java中对于数值类型的封装形式就有构造函数，这是它们二者本质的不同，像C++中用new动态声明一个对象，它一定用到了这个对象所属类的某个构造函数，可以说C与C++的最大区别就是C++用到了对象ADT，而C没用到(因此C压根不需要构造函数来着),STL可以说是一种总数据结构.
很多地方都用到到向量，，在学汇编时，，中断向量表就是一种向量,为什么STL没有arrary而只有vector呢？因为数组一般都用来实现vector，而且数组是语言的内含类型,一定程序上不提供太多的接口(根本因为是作为数值形式的数值没有被wrapper成一个first class因此不能作为函数的参数—因为没有复制构造函数，只能作为指针形式间接来操作它，也因此不能成为一个函数的返回值)，而Vector可以提供跟数组类似的结构（也有多维数组）和比数组更高级的使用接口(一般数组类型只能是静态的不可伸缩的，而Vector可作为动态数组动态改变大小)
实际上多维数组并不是在内存中是一个标准的矩阵(学过线代就知道，任何一种矩阵都可以化为它的等价三角矩阵)，比如C或C++就用一种行或列优先的方式来索引其元素。
数组是一个静态配置的空间，在命名方面JAVA做得比C++好（个人看法），比如INT MyVar[10];作为数组名的MyVar带了序列，而JAVA中INT[] MyVar;这就有点相当于type *是指向某种type的指针类型，而type[]是某种大小的数组类型一样好记
下面来阐述几个易混淆的概念
顺序线性表，，有序线性表(orderd list)，hasp map（可用关联容器来表达）都是列表,比如字典顺序，也即字母顺序的一种关联机制
线性表即通俗意义上的“线性数据结构”，线性的意思是什么呢，它一定要满足几个规则(1，有唯一的第一个元素和最后一个元素，2除了第一个元素都有一个前驱，，3，除了最后一个元素，都有一个后缀)
上述的元素就是数据结点的意思，数据和数据结点之间的关系可表达为B=(K,R)的二元组,满足关系的二个元素一个称为前驱一个为后继
计算机存储数据的方式只有二种，顺序存储与离散存储(又有链式，索引式，Hash式)，这是面向计算机端的存储结构，本向用户端的逻辑结构有集合(set),,哈希(hash map是一种map),,表(table),数组(array),,向量(vector),,图,树,map映射,线性表，节点链式表linked list,多维数据结构(matrix)等等，这种关系就有点像数据库的内外模式之分。逻辑结构间也有高级的演变方式，比如用vector来实现矩阵和table map是映射，，，set是集合,,都是关联型的数据结构，因此可用关联容器来表达 集合这种数据结构是用位集来描述数据集(可能以一个数组的形式存在),通过移位和位运算
线性表就是不能随机存储的表，像数组就是线性的，堆栈和队列也是线性的,有双向链表的存在(list),,dequece(double end quece),
表table就对应关系数据中的模式,,也即一个记录是一个表，它的各个字段就是表的竖维聚合数据类型就是像图(map)啊,树啊之类的，树是一种特别的图(每二个节点都有通路)而且是简单图
图的存储结构主要由它的邻接矩阵来表示，或邻接表，而树的存储表示主要由以下三种表示：结点表示法，兄弟子女表示法，等
这就是关联，，关联一定有key和一个value,,它们一同被存入数据结构，然后运用某种机制(可能是hash)通过key来索引value图是一种离散结构而非一种数据结构
图的边就是顶点之间的关系，这种关系是单向的或者双向的
像MFC的消息系统用的就是表驱动方式(它的消息映射表就是一个静态表)
我们知道，栈是一端开口的，往往从高端压和出栈(称为栈顶)后进先出的（但是后出先进这种说法是不存的，因为当一个栈没有数据时，它就不能出任何东西，因此只能说后进先出，先假设它有至少一个数据存在）因此它有当前指针和栈顶指针这二个元素来表示(当前指针指)，栈往往用数组来模拟(++p,p--这样的形式)，栈其实是一种跟它的实现形式无关的思想而已(是一种逻辑结构)，因此可以说是数组（指针数组）来摸拟（顺序存储的存储结构），可以用数组的一端，当，而队列是一种先进先出的，它二端开口，有三个描述元素(尾，头和当前指针)，它往往被实现作为一个管道（因为队列从意义上来讲它也其实就是一端进而从另一端出的数据结构啊）作为缓冲，或forward给其它处理list是列表的意思，有序列表orderdlist，链表(linked list是一种orderd list)，堆栈，队列都是一种orderd list就像链表和数组都可以仿真堆栈一样，，树啊，图啊都是思想模型，链表和数组才是实际存储的机制.对数据结构的讨论中经常用到递归，特别是树中，因为树本质就是一个递归结构，在回溯节点时就是回溯同一种节点(因此这个节点可用递归描述 )
递归跟回溯,栈
递推与迭代还是有区别的，递归就是用自己来定义自己，，一般不需要一个循环，，而迭代需要从1开始，将这个循环变量一直自加到最大值(循环不变量？)，，需要一个循环，一般来说，迭代比递归更有效率(在某些专门对递归进行了优化的环境中除外)
对一种数据结构的讨论常常不但要明白它们的工作原理，还要明白它们的操作，如查找，排序等，数据结构存储结构和这些操作就构成了ADT
《数据结构C语言版》
前言:这是我在2005.7月 - 2005.9月署假看《数据结构C语言版 - 清华大学出版社 黄国瑜叶艿菁著》时写的读书笔记,现在把它发布出来,希望对大家有用,也算是作个备忘录吧,不科学之处,还望高手斧正.

6.25 堆栈与队列
堆栈与队列都是数据结构(更复杂的还有树,图)在关系上是平等的数据结构,实际上堆栈与队列都是"内含在空间里的数据块",堆栈,队列的本质就是"数据块",不过它们都是包含在特定内存空间里的"有序数据块",如下图(4.bmp,用数组模拟"特定内存空间")
"特定内存空间"可以用数组表示,也可以用链表表示,数组是内存中的线形空间,也就是说,数组可以在内存中开辟一段空间,该空间是线性连续的,对该空间里任一元素的存取要根据"索引值"来进行,这些索引取从0~MS-1(如定义一个int queue[ms]或int stack[ms])是线性递增的,与数组空间从低地到高地的排列一一对应,数组的每一个空间都可有数据,也可无数据,每个空间的大小为一个int,整个数组大小就是ms个int,但是无论如何,对其中任何一个元素的存取(存是往数组任意位置里存入一个大小为int的空间,或在某个无数据内容的数组空单元空间里赋值,显然,这个数组空间是本来就存在于数组内的,而不同于链表要动态开辟一个新空间,而如果是前一种情况,数组就不再是静态的空间了,因为它的大小由ms变成了ms+1,而这是不可行的,同理,取是释放一个空间单元,这就使数组总空间大小由ms变为ms-1,或在某个空间里赋值0,术语称置0,而事先不管这个空间里有无值,如果有值,有的是什么值),其实,对数组索引的描述不但可用0~MS-1,当然也可用1~MS，但是为了方便考虑,把前一种看作为常用的,专业的方式,当然还可用2~ms+1(3种方式在定义了一个大小为ms的数组的情况下都可行可用),因为数组空间是一定的,对其的表示方式当然可以自由地使用不同的方法,一切的一切,只要保证能正确存取到所需的数据为程序所用为准,因为这是数组这种数据结构要最终达到的作用和总则,另外还要保持易用(像0~ms-1就显得专业并且简单易用,1~ms就人性化,而2~ms+1就什么都不是),上图中的数组示意图都开了"口",是表示只能从数组的开口的那一端存取数据(数组每个元素都是空间里包含的内容值,即数据,请搞清"元素","数组每个空间单元","内容值"等的说法),是一种形象的表示方法,而标准的数组图示方法可如下表示5.bmp)哪为什么要开口呢?一个数组为什么能开口呢?这是因为前面提到,这个"数组开辟的空间"将作"堆栈空间"使用,也就是"用数组模拟堆栈",因此标准数组示意图就要经过一些变形以适应能正确表示堆栈(空间)的要求,首先第一点变化就是"开了口",第二个变化就是还加入了一个top指针,这二个变化适应"能正确地表示堆栈(空间)"而生,其实要说top指针,它还不是标准意义上的指针,指针是一个32位的整型,而这里的top本质还是索引值,而非内存或外存地址单元名称代号,只是因为它发挥了类似指针"寻址"的作用,因此将其看作为"索引型"的指针,数组"堆栈"相比链表"堆栈",数组"堆栈"中的top是索引,而链表"堆栈"中的top才是真正的指针,因此数组的索引本质上是一种线性循序查找,而链表"堆栈"的top才是指针,分散在内存空间非线性不密集,只能由指针指定查找,这里就比较了数组与链表的本质(数组是内存中一段紧密的空间块,各个空间单元的连接是线性紧密的,这是对数组的低层讨论,反应到数组中就是其中的各个元素,将上一个元素的索引加1就可定向到下一个元素的索引位置,将上一个元素的内存空间地址加一个空间单元长度可定向到下一个元素在内存空间的位置,用0~ms-1或1~ms这样的递增性的索引就可表示数组的各个空间并引用它们,存取其中的空间或元素),有高地址和低地址之分,索引由小到大递增的方向就是内存地址低地到高地的线性递增方向,而堆栈是内存中各个分散的节点数据,各个节点数据就是元素或者更确切地讲,各个节点数据中的内容值,或称数据值而非指针值,就是链表的各个元素,相比起数组的空间单元的"连接",各个链表单元空间,也即节点空间的链表使用一种指定式的数值指定法而非数组采用的循序式的查找定位法,各个无素之间分散的链接由内含在各个元素(节点数据)中的指针字段而非内容字段,数据字段来完成,因此对其每个元素的存取前首先确定元素位置时是不能像数组中循序进行的,而是已被指定的,当前元素的内存位置就在上一个节点数据(元素)的指针字段里,而链表结构里,显然就没有高地与低地这种数组里才有的特征.
另外,要注意堆栈和队列中所说,它们都是有序列表,上面讲到,4.bmp中各个空间里的"有序数据块"才是确切意义上的"有序列表",即堆栈,队列这二个词语作为概念所指的实体所在,那么,它们的有序性是靠什么来体现的呢?堆栈靠的是游离于0~ms-1之间的索引值top,那么堆栈就是指0到top的数据块,top有一个特殊情况,top也可等于-1,显然,此时它指向序列为0的空间的更低地址的一个空间,表示堆栈为空(即堆栈中没有元素再供出栈了,出栈<=>从栈中输出一个元素<=>从堆栈中释放一个元素<=>删除一个元素),前面谈到,出口和top的引入都为用一个标准数组变为"堆栈"数组提供了可能,堆栈数据块是出入有序的,因此称为有序列表,那么,堆栈是如何依靠top来实现其空间里数据块元素出入的有序性的呢?在堆栈里,出口是唯一的数据输入输出(压入即输入push)通道,而队列有2个数据出入口,准确的说法是一个出口,一个入口,而堆栈的出口和入口集中在数组空间的一端而已,示意图就是只能从数组空间的高地址方向端输入输出数据(而堆栈有2端前端后端或称头端尾端,即front,end与head,rear),从rear端入栈,从f端出栈,堆栈数据实体就是从f到r的数据块,在数组表示的图示中f在下,r在上,在链表表堆栈中,f在前,r在后(f此时也可称为头,r也可称作后端),在数组表示中,各个数据实体是各个数组空间里的内容值,而在链表表堆栈中,各个数据实体(f到r),堆栈就是各个节点的内容字段链接而成的,这些内容字段链接起来构成的一串数据值就是堆栈数据块实体,从f到r,可见f到r不是从低地到高地,也不是从高地到低地,因为链表整个空间是分散于内存中的"节点空间"链接起来的,各个节点空间是分散布列在内存中的,因此,各个节点空间的value字段也是分散于内存里的,链表的各个空间间实际上没有一条一条的链,这只是示意图中的形象表示,链表的各个空间的链接桥梁就是内含在各个节点空间中的指针字段,链表与数组的一个重要区别与优点就是链表使用指针而非索引来寻址,这样就可以通过改变指针的值来重新形成链表空间或增删元素(实际上也是重新形成链表空间),这样链表就是一种动态配置的空间,而数组就是一种静态配置的空间,数组中的每个空间在数组被定义后就存在了,其中的任一个空间都不能被增删,只能向其赋值内容值0,表示置空此空间单元,这就是静态配置的空间.
.
6.26 真正的递归
递归是一种思想，只要问题本身满足递归你才能,递归涉及到三个概念，回溯
递归定义
即用递归来定义一些离散结构(集合，函数),3.4递归算法，用递归思想来解决问题的一般化步骤(算法即解决特定问题的一般化步骤，”停机问题”证明不存在解决所有问题的算法)
这种关系就如同二叉树的定义和查找，因为二叉权的定义就是指明它的左右节点存在次序关系，所以可以用这种定义作为思想来对二叉树进行查找，这并不难理解
用对象本身来定义对象就是递归，，这是递归的描述性定义，，是不确定的，，，非形式的，
集合的定义和算法的定义只有在形式语言里面才有形式定义,,(特别是图灵机证明不存在所有问题的一般化算法时用到的集合和算法的概念)
递归是用自身来定义自身这种说法成立吗，先来看一个问题

你能描述以上一副画吗？？（如果它的中心是无限循环的）
你可以这样描述，，，一副画的中心区域的内容是它自身(也是一副画，而且具有跟前面描述的一样的性质)，这样一副画就是如上的画的定义
显然递归的说法在这个例子是成立的
序列函数的定义比较容易理解,,集合的递归定义常常用来产生一些合式公式
迭代与递归在不同的情况下各有其优势
兔子和斐波那契数
例4 免子和斐波那契数 考虑如下问题,一对刚出生的免子(一公一母)被放到岛上，每对兔子出生后两个月后才开始繁殖后代，如下表所示，在出生两个月后，每对兔子在每个月都将繁殖一对新的兔子，假定兔子不会死去，找出n个月后关于岛上兔子对数的递推关系。



如何理解该月新生兔子即为距该月二个月前的兔子总对数?如6月新生的兔子为4月总兔数,4月新生的兔子为2月总兔数，3月新生兔数即为1月总兔数？
对某个月的讨论要追到与它的前二个月的情况(题目意思如此:每对兔子出生后二月才开始生育),这里是某个月的新生兔子与它二月前兔子总数“相等”的情况(注意这是一种递推说法,在任意差为二的月份间都存在这种联系,比如3-1,4-2,5-3,6-4，而6-2则不能考虑,因为它超出了递推为2阶的阶数2),从第三个月开始，放上岛的第一对兔子A+A-生下了一对兔子B+B-(假设每生下来的一对兔子都是一对公母可生育),在B+B-被生育下来的这个三月份，B+B-并不生育，这对A+A-在第四个月继续生育C+C-,而B+B-在第四个月也不生育，第五个月A+A-继续生育，B+B-终于开始生育出一对兔子D+D-,,
上面描述的可以作为典型,因为从第三个月开始，它就满足“每对兔子出生后二个月才开始繁殖后代”“任意出生在a月份的兔子在二个月后的b月后才生育,b-a=2”的题目要求,作为典型的3-1,5-3的情况被提出，后来处理任意相差二个月的兔子情况都可参照以上的描述了.
这样问题便被缩小到相邻二个月之间的情况，，
(为什么这是对的呢，作为典型的3-1,5-3为什么可代表一切相邻二月的情况,上面说了,这是题目意思告诉我们的,而不是递推，n个月后的兔子跟n-1总数与n-2总数才是递推,,这个递推也是在假设不知道存在这个递推的情况下列出的一个式子，列出之后才发现它是一个线性组合的递归,列出这个式子之间设了an,这并不表明事先就知道an一定是个满足某种递推的通项,只是在列出式子之后才明白是一个递推,而列出式子的过程仅仅依赖于题目意思)
既然已经得知,5月兔子与3月兔子间存在联系，那么这种联系是什么呢？重要的是知道这个联系本身,这个联系可用于任意相邻二月之间(题目意思)
从以上3-1,5-3的描述中容易看出,
  
汉诺塔问题：



图1 初始状态


图2 柱1 n-1个盘移到柱3后的情形
我们的目标是计数移动步数，，，并不是如题目所说得出移动的具体方法和每个书面步骤
因为等我们得出步数这个结论后，就会发现如果具体去得出移动步骤会多傻
而且，尊照规则(一次只能移动一块盘子，最后全部原样移动到柱2而不是柱3,并且最重要的大在下小在上)把n个盘子成功转移,移动的方法也可以千千万万,,所以我们要求的移动步数是最少的移动步数,那么对这个问题(求出最少移动步数)该如何建模呢?
首先，我们设想这样一个步骤:第一步,把柱1的n-1个盘子移到柱3,保持小在上大在下的顺序(如图2所示),保留最下面一个底盘，第二步，把底盘移到柱2，第三步，再把从柱1移过来的n-1个盘按步骤1的方法和顺序移动柱2,至此完成(注意方法和顺序的说法，方法:步骤1是怎么样移盘的这次也怎么移,顺序:保持小在上大在下)
容易看出，使用更小的步数是不可能求解这个难题的
下面具体建模
按照上面设想的所产生最少移动步数的移法,首先，设Sn是把n个盘子从一根柱子移动到另一根柱子的需要的总步数,(问题是什么我们就设什么,,虽然我们并不知道这其实是一个为了满足递推关系的设法,虽然我们也不知道有了以上设法,再用递推关系就可以很好地解此题,因为从形式来看Sn像一个序列的通项,它指明Sn就是把n个盘子从柱1到柱3所需要的Step,S2就是2个,S10就是10所需要的Step,这个设法假定Sn与n之间存在序列关系),按照步骤1，移动次数可用Sn-1来表示,步骤2可用1来表示，步骤3亦为Sn-1,故有
Sn=2Sn-1+1 (Sn为把n盘从柱1移到柱3所需步数或直接就是)
注意Sn为什么不直接说是“设Sn是把n盘从柱1移到柱2所需步数”呢,这样说当然没有错，不过为了严紧性和通用性考虑还是这样设(本题当然是从柱1移到柱3,如果没有规定其实移到柱2作为中转也可,最后求移动到柱3上的步数同样满足Sn=2Sn-1+1,,况且还有很多同类的题目，移奶酪到盘子里什么的,所以为了通用性考虑还是如上设)
最后的问题：我们用迭代方法来求解这个递推关系

天狗

5.2 求解递推关系
有一类重要的递推关系可以用一种系统的方法明确地求解,,在这种递推关系中（好像我们见过的都是这样的），序列的项由它前面的线性组合来表示
请注意,递归，递推，迭代在措词上的区别
递归是用自身定义自身的,或过程调用自身，用在序列通项表示上，，形如，an= an-1,用在过程体内，这仅仅是一种思想，而不能说是一种算法，，显然这种思想是成立的,,,递推关系和迭代是用了递归思想的2个概念而已,是用到了递归思想的所有东西的集合中的二个元素,
要对它们三者定性的话，递归是一种思想，递推只是一种说法，迭代是一种算法(常用来求解满足递推关系问题)
递推是一个序列的某个通项可由它的前几项组合推导而来的关系，，强调的是通项和推出它的前几项之间的关系满足这个“递归推导而出”说法,因此它一定用到了递归的思想,满足递归
序列中,递推是发生在某个项和它的相领项之间的关系，，但是指定了初始项和这个递推关系，可以得出所有的项，即通项,,实际上“某个项”的定义一旦被提出，它就表示了通项的意义,,因此序列所有项=由通项关系得出每个项后,这些项的组合=初始项+满足递推的相领的某几项
（我们设这里是二项,而不是前几项）所以，所谓递归只是二个项之间的关系，，但是由于这二个项可以是任意项,,因此，递归是所有项中任意二相领项的关系,可用来求解整个序列每一项,求此也求解所有项
定义X:一切序列可以用到递推要求它满足递归,这永远是前提(实际上并不是所有的序列都满足递推和递归)
迭代是用迭次代换，(常用来求解一个“线性组合”型递推关系的方法,也可求解不满足线性组合的一些递推关系)把一个项逐次展开，，用到一个迭代器i，比如求解an,必须使i从第n项到第k项逐次递减，(k通常情况下是1,即第一项),,迭代也只在几个相邻项之间进行，因为它也借用了递归和递推思想而已,这一切都是因为用到迭代的序列(或其它问题)也要由定义x而来,,不再赘述
.
6.27 树与单链表，图
除了单链表之外还有高级链表,包括双链表和循环链表,但是它们的基础依然是单链表,对单链表的讨论可运用于高级链表,也即无论单,高级链表,本质都是一样的数据结构,都是链表,即链表的本质是节点的单向或双向串连,注意"串连",这是所有链表区别于树这种数据结构的所在,因为树是一种节点的"分支"链接,(树是较线性表,图更为复杂的数据结构,它的任何二个结点间都可以发生联系)它们的共同点就是:这些节点都是分散于内存中的节点,由上一个节点(链表)或父的一方节点(树)的指段字段指向,树和链表的示意图中,圆形就代表节点,包含数据字段和指向下一个节点的指针字段,这是对链表来说的,而对于树来说(这里说的是二叉树)圆形节点就包含数据字段和指向其左右节点的指针字段,或称左右子树,因为这些左右子树是以这个节点为根的子树,注意左右是有顺序性的,不能颠倒,用Left,Right区别.无论是链表还是树示意图中的直线都是指针,有方向的,不是互逆的,这处互逆性决定了对单链表的"首->尾"遍历和对二叉树的"二叉查找"遍历方式(中序,左右序)的单向性,可见树与链表的实体数据都存在节点中,这是节点的主体存储空间,链表,树作为数据结构用于组织程序中要用到的数据,它们的节点单元的Data字段发挥的是主体存储作用,而它们节点的指针字段是辅助性且必要的,用于树,链表的查找,遍历,插入,删除等操作,严格来说,图并非一种数据结构,书中对图的讨论只能称为对"与线长,面积大小"无关的点线面的拓朴讨论,而由点边组成的图形中居然没有一个点或边发挥数据存储作用,而这是一种数据结构首要完成的任务.
3.数组,链表为什么能仿真堆栈?
其实这个问题被提出来一点都不可笑,对这个问题的讨论很有意义,它能让我们明白一些细微而重要的东西.
数组,链表,堆栈,队列,是四大数据结构,在关系是并列的,为什么又有"用数组和链表仿真堆 栈"之说呢,其实数组,链表是较高级的复杂的数据结构,还记得本书序言中的一句话吗?数据结构是人类在长期的编程过程中总结归纳出来的一套科学有序的方法,数组是,链表是,堆栈和队列也是,但是在人类总结归纳这些数据结构并形成术语进而形成数据结构这门计算机科学时,永远是从简单低级的数组和链表开始的,对它的讨论和总结归纳先于堆栈,队列之前进行,当人们总结出数组和链表数据结构时,并得出对数组和链表的删除,复制,插入等操作后,形成了数组链表等数据结构概念及其操作的一整套理论后,人们进一步探索数据结构,发现了堆栈的存在,而堆栈又是基于数组,链表的高一级的数据结构,对堆栈,队列的研究与讨论经历了与对数组链表相同的过程,对数组和链表的研究和技术总结业已成型的情况下,就应该采用现在的知识来描述新出现的知识,因此有以上的说法.

6.28 树
树是一种数据结构,称为树状结构,简称树,树的本质是一个或多个节点的有限集合,树只有一个节点的情况是例外的特殊的情况但也是允许的树的形式,而一般情况下,树都有不止一个的节点,有限集合这四个字指明:一棵树,无论它由多少个节点构成,这些节点的数量都是有限的,可以计数的,也即,从来没有一棵树,它的节点个数为无限不确定的.
在一棵树的所有节点中,它们的地位是不一样的,每棵树必定有一个特定的节点,称为根节点(root),根节点与这棵树的其它节点构成了这棵树(当然这些节点并不是单独地存在无联系的,不然就无法从这些节点中搞出一个为根的地位节点,这些就构不成一棵树),可见,"根"是相对于"树"来说的,根这个概念是树一级的概念,只要有树,便会有根,根的本质是一棵树的"特定节点"(第一个节点,其它节点由它分支而来),而树又是一种特定的数据结构,请记住,根是依附在树概念上的概念,脱离了树便无所谓根概念,总之,根是与树直接挂钩的一对概念,为什么我要在这里这么花心思地说明根是相对于树的概念呢?因为这是理解7.1节中关于树的其它概念的一个基本点,掌握了它,你便不会在理解这些概念中迷失.
说完了根,再来说其它节点,其它节点(实际上这里说的其它节点准确的意义不是说除了根节点外的一棵树的其它所有节点,而是说根节点的下一级节点,可以有0个,可以有n个,0个就是没有下一级节点,而n的大小便决定了这棵树的分类性质,如果n=2,便是二叉树,后面会谈到)是根的子节点.(8.bmp)
从树结构的图示来看,树与现实中的树虽然类似,但是,数据结构中的树是一棵倒树,根是相对于树的概念与树直接挂钩,而子节点的概念直接与根节点的概念挂钩,而与树不挂钩,根节点与子节点的概念仅仅存在于一个节点与该节点下一级节点之间,与树不挂钩,这就像主程序与子程序的概念,主程序与子程序永远是相对的概念,如果前面说的子程序它又有它的下一级程序,那么主程序与子程序有主子关系之外,还可以说前面谈到的子程序与该子程序调用的子程序也有主子关系,此时这里的子程序是主程序而子程序调用的子程序就是子程序,这2种说法都是可行的,因为主子关系是相对的可变的而非绝对的,主子这种说法存在于只要满足一方是调用者而另一方是被调用者之间,而非绝对不变的,再接着上图讲,那么B,C,D,M就是A的子节点,而不能说B,C,D,M是树T的子节点,没有这种说法,树只有根和子树,叶节点与其挂钩,而只能说(因为B作为根节点其下还有P,Q2个子节点)B,C是树T的子树(D,M不是),这里,B,C,D,M作为A的子节点,同时B,C又是树T的子树,子树B(以它的根节点为名称故根节点就是B)的根节点B又有自己的子节点,T的树C的根节点C又有自己的子节点R,若一棵树中的任意一级(根)节点最多有n个子节点,则称这样的树为n元树,二叉树的得名也来源于此.
12.树的本质是什么?
树是一种数据结构,所以树的本质是一种组织内存空间的方法,就像数组是静态配置内存空间的方法,且数组配置出来的空间不但是静态的,而且是紧密相连排列的线性的各个"小空间",是一块内存中的块状数据静态的存储区,由它的一个小空间的地址可以推导出下一个小空间在内存中的地址,而链表是一种动态的配置内存的方法,程序中,数组空间在数组被定义出来时就被开辟,在它的生命期内从此不能更改大小,而链表被定义出来时还要用内存开辟函数malloc()来实际分配内存,所以它开辟出来的空间是动态的,而且这些空间单元不是线性紧密排列的而是分散的,分散于内存中的各个"节点"空间,是不可通过索引下标循序查找定位的,只能通过内含于各个节点数据内的指针字段来"指定查找",形象示意如下1.bmp)那么树呢?树的本质是"节点的非空有限集合",跟链表有一定的相似性,首先,链表与树(基础树,书中所讲为二叉树,这属于简单树而非广度意义上的树,但是对二叉树的讨论可以延用扩展为整个树的范畴)都是动态内存配置的方式,链表空间间连接依赖于各个节点数据的指针字段,而树的节点空间连接的方法为"格式上的约定",树的节点空间和链表的节点空间都是这二种数据结构实际存储实体数据的存储场所,是怎么样一种"格式上的约定"呢?以二叉树为例(其实树各个空间之间没有什么链接,链表各空间发生关系的纽带与桥梁是指针字段,而树的各个节点空间间发生关系的钮带与桥梁为"格式上的约定","约定俗成的方法来格定"),二叉树的每一个节点空间实际各各分散布列于内存中,它们发生联系的手段就在于各个节点的性质,前面谈到,树是节点的非空有限集,如根就是树的第一个节点空间,如果是二叉树,这个节点自然会跟其下一阶的二个子节点发生关系,这就是父子节点关系,当然不止根与其下一阶节点,在其它节点间也存在父子关系,除此之外还有兄弟关系,树->子树关系这种"关系机制"是远远不同于链表依赖指针表示各节点空间联系的手段的,所以这是一种"节点关系"上的"约定",是一种全新的组织节点空间的手段和方法,而没有用到指针,当然可以用指针来模拟和仿真,这就涉及到"用链表来表示二叉树"的知识点,这是后来的内容.
13.图的本质是什么?
要说图是一种数据结构实在很难理解,因为我第一次碰到图的概念,根本就没有发现图形结构中的哪部分用于存储数据,378页对图形的定义"在图形G中包含了2个集合,一个是由顶点所构成的有限非空集,另一个是由边所构成的有限非空集,可用G(V,E)表示",按照这个定义,图形就是顶点和边的有限集合(至少要有一顶点一边),晕死,那么实体数据存在哪?顶点中?不是,边的描述值权吗?好像也不是,署假我只看了这本书17天,所以对图我没太多深入研究.

6.29 真正的散列表
一般抽象到了某个程度，为了获得计算机作为底层的冯氏能力，，就不应该再抽象下去了。
开发模型不需要再变了，数据抽象到数据结构级就是顶级了再抽象就不是开发问题了()
Hash表就是hashed list,,,它是逻辑上的list（所以也有hash map,hash set等）,但按hash方式存储地址作为存储，Hash是一种利于搜索的启发过程，一般的搜索是对搜索空间uniform的，而hash function是对搜索空间的目标问题建立的一种启发机制的函数。
Hash的最重要的意思不是提供一个映射函数，那反而是hash解决的第二个问题，即地址问题，，它最重要的意义，即第一个解决的问题是基于统计的本质。进行的对搜索空间的一种抽象（即hashtable而不是hashfunction问题，比如元素会出现一次，还是二次，这样抽象对操作元素有好处，但显然此时并不出现hasing function的意思），
一般设计散列时，说的都是设计散列表，然后处理冲突处理，，，如何散列所用的函数是附带问题。
也即其实hash table的第一层意思是table,,即形成数据结构才是他的第一层意义,,,而不是如何hash,,,并提供一套hash 机制,,,
它着手于"在解空间和目标数据空间建立一套具有inform关系"的数据结构,,,这才是它的第一层意思,即名字中的table一词
至于如何hash并解决冲突,,那反而是它解决的第二个问题..即名字中的hash一词
只有理解了这点之后,你才会明白hash table是如何来的,以及为什么存在,,与其它数据结构作比较时所呈现的那些不一样的特点(比如为什么要进行hash,,为什么要处理冲突,而其它的数据结构则不需要这样的分析过程).

6.30 算法设计方法
摊还分析不仅是解释数据结构性能的工具，而且也是设计时要考虑的因素。就跟NP完全一样（逊于图灵不可计算机的停机问题）。如果复杂度超过了10的确良8次方这个计算机的数量级就没有意义了。
存在很多类型的问题，比如最优化问题，，找点问题，理解诸如贪婪算法的前提是理解这些问题在先，比如最优化问题可以很好地解释什么是贪婪设计。
迭代是方程求根的一种方法，并且它也体现了一种算法设计方法。
递归体现了分治的算法设计思想，但它提出的子问题一定要跟原问题接口一致。。 递归的终结条件是不需要递归也可直接求解的条件，，因此是终止条件，，当以从下到上的眼光来看时，它是超始条件（直到问题规模n）
其实并不是只有所有明显递归性质的问题才可以用递归来解答，而是只有能把原问题分解为子问题并能制造一个接口的情况下就可以利用递归来求解它。
递归是从上而下，所以有时要求用辅助栈来保存中间结果，而递推只有一个函数，并不发生欠套的函数调用，并没有出入栈的时空开销。复杂的递归结构转化成递推时，需要回SU处理，二个概念仅一字之差，一个归，是向下，一个推是向上，
关键字相当于字典中的单词，，而数据项相当于这个词的词义，造句，等全部的词条信息，这样说你一定不会明白，说实话我第一次看到这样的说话也没能明白。。
实际上就是说，我们要查的是关于某个词的词条义，音等，，但我们是通过某个单词找到该单词的词条义，音的。。在字典中单词和其音义是一同被存入字典的，都是(某记录的)数据项，但单词是作为键的数据项。.