6.9 数据构造初步引象(4)线性表是最常见的数据构造和逻辑构造，然而只有图才是最常用的数据构造和逻辑构造。。实在树状构造有天然的转化成线性构造的上风，因此也有作为线性表的树的存在(因此说树是树性表的一种推广,传授教化的时候完备可以从线性表引伸到树,, 树有作为线性表存在的树，树也有作为树本身意义存在的树，和作为树图意义存在的树，这三种情形都须要被谈论。)此时从树的眼力来看这种原来是树的数据构造它还是存在父子关系，从线性表的眼力来看是变换了的平等关系.6.10 ordered与sortedLists广义列表，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树是严格用平衡因子去定义的(因此是“平衡”的最正宗意义所在)，而红黑树不是，因此红黑树不是平衡二叉树，实际上它故意许可一定程序上的不平衡。红黑树不是平衡二叉树但它“担保”2O(logN)的最坏情形下的平衡度（人们每每根据这个缘故原由把它归为跟AVL一类），AVL树是1.44O(logN)，这二种树只“担保”（把稳只是担保）最差情形下的下界为1.44O(logN)或2O(logN)，称它们为平衡树不是由于其内部是不是极力在保持平衡还是不是，重点在这里（最坏情形下担保了多少的平衡度），，综合考虑插入，查找，删除等操作来说，红黑树的效益要好于AVL，由于AVL是严格平衡的因此只对查找intensive。查找时只需向上查找1.44O(logN)个节点就行(经由AVL平衡的树只需对height bounded at 1.44O(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[mn]的一维数组)，关联表等，除了数组是实现之外，，其它的叫法，它们有些不是指同一个东西(比如向量跟矩阵是不一样的东西，数学上的向量是矩阵中某维为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处理，二个观点仅一字之差，一个归，是向下，一个推是向上，关键字相称于字典中的单词，，而数据项相称于这个词的词义，造句，等全部的词条信息，这样说你一定不会明白，说实话我第一次看到这样的说话也没能明白。。实际上便是说，我们要查的是关于某个词的词条义，音等，，但我们是通过某个单词找到该单词的词条义，音的。。在字典中单词和其音义是一同被存入字典的，都是(某记录的)数据项，但单词是作为键的数据项。.
