数据结构第1-8章(清华大学出版社-唐宁九主编)

-1-第一章概论本章的重点是了解数据结构的逻辑结构、存储结构、数据的运算三方面的概念及相互关系，难点是算法复杂度的分析方法。基本概念和术语有：数据、数据元素、数据项、数据结构。特别是数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系。数据结构的两大类逻辑结构和四种常用的存储表示方法。算法、算法的时间复杂度和空间复杂度、最坏的和平均时间复杂度等概念，算法描述和算法分析的方法、对一般的算法要能分析出时间复杂度。第二章线性表本章的重点是掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分析，难点是使用本章所学的基本知识设计有效算法解决与线性表相关的应用问题。在顺序表中实现的基本运算主要讨论了插入和删除两种运算。相关的算法我们通过练习掌握。对于顺序表的插入和删除运算，其平均时间复杂度均为O(n)。一个单链表由头指针的名字来命名。对于单链表，其操作运算主要有建立单链表(头插法、尾插法和在链表开始结点前附加一个头结点的算法)、查找(按序号和按值)、插入运算、删除运算等。以上各运算的平均时间复杂度均为O(n).其主要时间是耗费在查找操作上。-2-循环链表是一种首尾相接的链表。也就是终端结点的指针域不是指向NULL空而是指向开始结点(也可设置一个头结点)，形成一个环。采用循环链表在实用中多采用尾指针表示单循环链表。这样做的好处是查找头指针和尾指针的时间都是O(1)，不用遍历整个链表了。双链表就是双向链表，就是在单链表的每个结点里再增加一个指向其直接前趋的指针域prior,这样形成的链表就有两条不同方向的链。使得从已知结点查找其直接前趋结点可以和查找其直接后继结点的时间一样缩短为O(1)。双链表一般也由头指针head惟一确定。双链表也可以头尾相链接构成双(向)循环链表。关于顺序表和链表的比较，请看下表：具体要求顺序表链表基于空间适于线性表长度变化不大，易于事先确定其大小时采用。适于当线性表长度变化大，难以估计其存储规模时采用。基于时间由于顺序表是一种随机存储结构，当线性表的操作主要是查找时，宜采用。链表中对任何位置进行插入和删除都只需修改指针，所以这类操作为主的线性表宜采用链表做存储结构。若插入和删除主要发生在表的首尾两端，则宜采用尾指针表示的单循环链表。第三章栈和队列掌握栈和队列在两种存储结构上实现的基本运算，了解循环队列中对边界条件的处理。栈的逻辑结构和线性表相同，栈(Stack)是仅限制在表的一端进行插入和删除运算的线性表，通常称插入、删除这一端为栈顶，另一端称为栈底。由于栈也是线性表，因此线性表的存储结构对栈也适用，通常栈有顺序栈和链栈两种存储结构，这两种存储结构的不同，则使得实现栈的基本运算的算法也有所不同。链栈没有上溢的限制，链栈不需要在头部附加头结点。-3-队列(Queue)是两头都有限制，插入只能在表的一端进行(只进不出)，而删除只能在表的另一端进行(只出不进)，允许删除的一端称为队尾(rear)，允许插入的一端称为队头(Front),队列的操作原则是先进先出的，所以队列又称作FIFO表。队列也有顺序存储和链式存储两种存储结构，前者称顺序队列，后者为链队。对于顺序队列，要理解假上溢的现象。为了克服这种现象造成的空间浪费，引入循环向量的概念。队列的链式存储结构称为链队列，一个链队列就是一个操作受限的单链表。为了便于在表尾进行插入(入队)的操作，在表尾增加一个尾指针，一个链队列就由一个头指针和一个尾指针唯一地确定。第四章串串的逻辑结构，存储结构及串上的基本运算，重点是掌握在串上实现的模式匹配算法。串就是字符串，是一种特殊的线性表，它的每个结点仅由一个字符组成。空串：是指长度为零的串，也就是串中不包含任何字符(结点)。空白串：指串中包含一个或多个空格字符的串。不同与空串，它的结点就是一个空格字符。在一个串中任意个连续字符组成的子序列称为该串的子串，包含子串的串就称为主串。子串在主串中的序号就是指子串在主串中首次出现的位置。串的顺序存储结构简称为顺序串，顺序串又可按存储分配的不同分为静态存储分配的顺序串和动态存储分配的顺序串。-4-第五章数组和广义表重点是熟悉多维数组的存储方式、矩阵的压缩存储方式、广义表的定义及其求表头和表尾的运算，难点是稀疏矩阵的压缩存储表示下实现的算法。多维数组：多维数组的顺序存储结构及其地址计算方式:计算机的内存结构是一维的，因此将数组元素排成线性序列，然后将这个线性序列存放在存储器中。排列的方式有两种，一是行优先顺序。二是列优先顺序。数组是一种随机存储结构的原因：因为在顺序存储的情况下，每一个元素都有与其下标相对应的地址，因此可以对数组中的元素进行随机存储。矩阵的压缩存储：稀疏矩阵的概念：一个矩阵中若其非零元素的个数远远小于零元素的个数，则该矩阵称为稀疏矩阵。稀疏矩阵的压缩存储方式三元组表就是把非零元素的值和它所在的行号列号做为一个结点存放在一起，用这些结点组成的一个线性表(三元组表)来表示这个稀疏矩阵。但是这种压缩存储方式将失去随机存储功能。广义表的概念：广义表又称列表(Lists),是线性表的推广。广义表是n(n≥0)个元素a1,a2,a3...an的有限序列，其中的ai或者是原子或者是一个广义表。广义表表头和表尾的概念：若广义表LS非空(n≥1),则这个广义表的第一个元素就是表头。而其余的元素组成的表称为LS的表尾,表尾必是一个子表。-5-第六章树和二叉树本章是重点章，二叉树又是本章的重点内容，了解树的定义熟悉二叉树的定义、性质、存储结构、遍历、线索化和树的存储结构、遍历以及树、森林与二叉树的转换，哈夫曼树及哈夫曼编码等内容。一、树的概念：关于树的概念，主要是应能理解有关树的一些名词术语的含义.树的逻辑结构特征是：树中任一结点都可以有零个或多个直接后继(孩子)结点，但至多只能有一个直接前趋(双亲)结点。树形结构是非线性结构。二、二叉树：二叉树的定义：二叉树是n(n≥0)个结点的有限集，它或者是空集(n=0),或者由一个根结点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成。二叉树的5个重要性质：1.二叉树上第i层上的结点数目最多为2i-1(i≥1)2.深度为k的二叉树至多有2k-1个结点(k≥1).3.在任意一棵二叉树中，若终端结点的个数为n0,度为2的结点数为n2，则n0=n2+1。4.具有n个结点的完全二叉树的深度为|_lgn_|+1树的存储结构更多的是用链式存储。结点的结构为两个指针域lchild和rchild分别指向该结点的左孩子和右孩子，另有一个数据域data存放结点数据。把所有二叉树的结点，加上一个指向根结点的指针就构成了二叉树的链式存储结构，称为二叉链表。由根指针root唯一确定的。-6-三、二叉树的遍历：根据访问结点的次序不同可得三种遍历：先序遍历，中序遍历、后序遍历。遍历的算法就是一个递归算法，以中序遍历为例，它的定义为若二叉树非空，则依次执行如下操作：(1)遍历左子树；(2)访问根结点；(3)遍历右子树。将(1)(2)对调则得先序遍历，将(2)(3)对调则得后序遍历。四、线索二叉树：利用二叉链表中的n+1个空指针域来存放指向某种遍历次序下的前趋结点和后继结点的指针，这些附加的指针就称为线索，加上线索的二叉链表就称为线索链表。五、树和森林：树和森林及二叉树的转换：三者是唯一对应的，它们之间的转换办法应掌握。树的存储结构：有双亲链表表示法（就是在每个结点设一指针指向其双亲以唯一地表示任何一棵树，用向量表示）。孩子链表表示法（就是为树中每个结点设置一个孩子链表，并将结点及相应的孩子链表的头指针存放在一个向量中）。因此可以两种表示法结合形成双亲孩子链表表示法。第三种是孩子兄弟链表表示法（就是在存储结点信息的同时，附加两个分别指向该结点的最左孩子和右邻兄弟的指针域）和二叉树的二叉链表表示完全一样，因此可利用二叉树的算法来实现对树的操作。六、哈夫曼树及其应用树的应用很广泛，哈夫曼树就是其中之一。-7-树的带权路径长度最小的二叉树就称为最优二叉树（即哈夫曼树）。哈夫曼首先提出了构造最优二叉树的算法，哈夫曼算法：（1）构造森林全是根（2）取出两小成新树（3）重复（2）步剩单根此树便是哈夫曼树。哈夫曼树的应用最广泛地是在编码技术。第七章图图是一种复杂的非线性结构，要熟悉的内容是图的基本概念，两种常用的存储结构(邻接矩阵和邻接表)，两种遍历算法(DFS和BFS)及图的应用算法(最小生成树。一、图的概念图的逻辑结构特征：图的逻辑结构特征就是其结点(顶点)的前趋和后继的个数都是没有限制的，即任意两个结点之间都可能相关。图的常用术语及含义二、图的存储结构：一是邻接矩阵表示法，用一个n(n为顶点数)阶方阵来表示图的结构。以第i行第j列上的数来表示顶点vi和vj之间是否有边或边的权值。对于无向图而言，邻接矩阵是对称的，用邻接矩阵表示的空间复杂度为S(n)=O(n^2).(方阶)建立邻接矩阵算法的时间是O(n+n^2+e),所以其时间复杂度为O(n^2)二是邻接表表示法，这种表示法类似于树的孩子链表表示法，它首先对每个顶点vi建立一个单链表(即邻接表)，这个单链表由邻接于vi的所有顶点的结点构成，然后给每个单链表设一头结点，头结点存放顶点vi的信息，把这些头-8-结点顺序存于一个向量中构成顶点表.对于有向图来说，若建立的是入边表为邻接表，则称之为逆邻接表表示法。从存储空间角度看，邻接表更适合于表示稀疏图而邻接矩阵适合于表示稠密图。三、图的遍历有两种常用遍历，一种是深度优先遍历，另一种是广度优先遍历。在深度优先遍历中要使用到栈来保存已访问的结点，或保存已访问顶点的所有尚未访问过的邻接点。在广度优先遍历中，使用到了队列来保存已访问过的顶点。四、生成树和最小生成树生成树的定义：若从图的某个顶点出发，可以系统地访问到图中所有顶点，则遍历时经过的边和图的所有顶点所构成的子图称作该图的生成树。最小生成树：由于图的生成树不是唯一的，从不同的顶点出发可以得到不同的生成树，对于带权的连通图，其生成树也是带权的，我们把权值最小的生成树称为最小生成树(MST).一是Prim算法，适合于稠密图。二是Kruskal算法，较适合于稀疏图。第八章查找本章介绍了线性表、树和散列表的查找方法、算法实现以及各种查找方法的时间性能分析，重点是顺序查找、二分查找、二叉树查找以及散列表上查找的基本思想和算法实现。-9-一、基本概念查找的同时对表做修改操作(如插入或删除)则相应的表称之为动态查找表，否则称之为静态查找表。衡量一个查找算法次序优劣的标准是在查找过程中对关键字需要执行的平均比较次数(即平均查找长度ASL).二、线性表的查找线性表上进行查找的方法主要有：顺序查找、二分查找。顺序查找方法可用链式存储结构和顺序存储结构实现。在等概率情况下，查找成功时其平均查找长度约为表长的一半(n+1)/2.查找失败的话其平均查找长度为n+1.二分查找(又称折半查找)，它的算法思想是对一有序表中的元素，从初始的查找区间开始，每经过一次与当前查找区间的中点位置上的结点关键字进行比较，若相等，则查找成功，否则，当前查找区间的缩小一半，按k值大小在某半个区间内重复相同的步骤进行查找，直到查找成功或失败为止。二分查找只适用于顺序存储结构而不能用链式存储结构实现。三、树的查找以树做为表的组织形式有一个好处，就是可以实现对动态查找表进行高效率的查找。二叉排序树(BST)又称二叉查找树，其定义是：二叉排序树要或者是空树或者满足如下性质的二叉树：(1)若它的左子树非空，则左子树上所有结点的值均小于根结点的值；(2)若它的右子树非空，则右子树上所有结点的值均大于根结点的值；-10-(3)左、右子树本身又是一棵二叉排序树。四、散列技术散列函数的定义将结点按其关键字的散列地址存储到散列表的过程称为散列。装填因子α表示表中填入的结点数与表长的比值，通常取α≤1，因为α越大，表越满，冲突的机会也越大。1.平方取中法2.除余法3.随机数法处理冲突的方法：当不可避免发生冲突时，就必须对冲突加以解决，使发生冲突的同义词能存储到表中。通常有两类方法处理冲突：开放定址