数据结构知识总结

数据结构全书知识梳理总结第一章绪论数据就是指能够被计算机识别、存储和加工处理的信息的载体。数据元素是数据的基本单位，有时一个数据元素可以由若干个数据项组成。数据项是具有独立含义的最小标识单位。如整数这个集合中，10这个数就可称是一个数据元素.又比如在一个数据库(关系式数据库)中，一个记录可称为一个数据元素，而这个元素中的某一字段就是一个数据项。数据结构的定义包括以下三方面内容：逻辑结构、存储结构、和对数据的操作。数据的逻辑结构分为：线性结构、树形结构、复杂结构数据的存储结构分为：顺序表示、链接表示、散列表示、索引表示时间复杂度和渐近时间复杂度：前者是某个算法的时间耗费，它是该算法所求解问题规模n的函数，而后者是指当问题规模趋向无穷大时，该算法时间复杂度的数量级。当我们评价一个算法的时间性能时，主要标准就是算法的渐近时间复杂度，因此，在算法分析时，往往对两者不予区分，经常是将渐近时间复杂度T(n)=O(f(n))简称为时间复杂度，其中的f(n)一般是算法中频度最大的语句频度。算法中语句的频度不仅与问题规模有关，还与输入实例中各元素的取值相关。但是我们总是考虑在最坏的情况下的时间复杂度。以保证算法的运行时间不会比它更长。第二章线性表线性表的逻辑结构特征是很容易理解的，如其名，它的逻辑结构特征就好象是一条线，上面打了一个个结，很形象的，如果这条线上面有结，那么它就是非空表，只能有一个开始结点，有且只能有一个终端结点，其它的结前后所相邻的也只能是一个结点(直接前趋和直接后继)。关于线性表上定义的基本运算，主要有构造空表、求表长、取结点、查找、插入、删除等。线性表的逻辑结构和存储结构之间的关系。在计算机中，如何把线性表的结点存放到存储单元中，就有许多方法，最简单的方法就是按顺序存储。就是按线性表的逻辑结构次序依次存放在一组地址连续的存储单元中。在存储单元中的各元素的物理位置和逻辑结构中各结点相邻关系是一致的。在顺序表中实现的基本运算主要讨论了插入和删除两种运算。对于顺序表的插入和删除运算，其平均时间复杂度均为O(n)。线性表的链式存储结构。它与顺序表不同，链表是用一组任意的存储单元来存放线性表的结点，这组存储单元可以分布在内存中任何位置上。因此，链表中结点的逻辑次序和物理次序不一定相同。所以为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还存储了其后继结点的地址信息(即指针或链)。这两部分信息组成链表中的结点结构。对于单链表，其操作运算主要有建立单链表(头插法、尾插法和在链表开始结点前附加一个头结点的算法)、查找(按序号和按值)、插入运算、删除运算等。以上各运算的平均时间复杂度均为O(n).其主要时间是耗费在查找操作上。循环链表是一种首尾相接的链表。也就是终端结点的指针域不是指向NULL空而是指向开始结点(也可设置一个头结点)，形成一个环。采用循环链表在实用中多采用尾指针表示单循环链表。这样做的好处是查找头指针和尾指针的时间都是O(1)，不用遍历整个链表了。判别链表终止的条件也不同于单链表，它是以指针是否等于某一指定指针如头指针或尾指针来确定。双链表就是双向链表，就是在单链表的每个结点里再增加一个指向其直接前趋的指针域prior,这样形成的链表就有两条不同方向的链。使得从已知结点查找其直接前趋结点可以和查找其直接后继结点的时间一样缩短为O(1)。双链表一般也由头指针head惟一确定。双链表也可以头尾相链接构成双(向)循环链表。顺序表和链表的比较具体要求顺序表链表基于空间适于线性表长度变化不大，易于事先确定其大小时采用。适于当线性表长度变化大，难以估计其存储规模时采用。基于时间由于顺序表是一种随机存储结构，当线性表的操作主要是查找时，宜采用。链表中对任何位置进行插入和删除都只需修改指针，所以这类操作为主的线性表宜采用链表做存储结构。若插入和删除主要发生在表的首尾两端，则宜采用尾指针表示的单循环链表。第三章字符串串就是字符串，是一种特殊的线性表，它的每个结点仅由一个字符组成。空串：是指长度为零的串，也就是串中不包含任何字符(结点)。空白串：指串中包含一个或多个空格字符的串。不同与空串，它的结点就是一个空格字符。在一个串中任意个连续字符组成的子序列称为该串的子串，包含子串的串就称为主串。子串在主串中的序号就是指子串在主串中首次出现的位置。如A=Iloveyou,B=love,则B在A中的序号为3，注意空格也是字符。空串是任意串的子串，任意串是他自身的子串。串是特殊的线性表(结点是字符)，所以串的存储结构与线性表的存储结构类似。串的顺序存储结构简称为顺序串，顺序串又可按存储分配的不同分为静态存储分配的顺序串和动态存储分配的顺序串。静态的意思可简单地理解为一个确定的存储空间，它的长度是不可变的。如直接使用定长的字符数组来定义一个串。它的优点是涉及串长的操作速度快，因为它的最大长度是不变的。动态存储分配就是在定义串时不分配存储空间，直到需要使用时按所需串的长度分配存储单元给它，并且在运行中还可以根据需要变化串的长度，这就是动态分配。不过这样的串仍是顺序存储的，也就是说指针指向串的首地址，后面的结点是连续存储的。串的链式存储就是用单链表的方式存储串值，串的这种链式存储结构简称为链串。链串与单链表的差异只是它的结点数据域为单个字符。这种存储结构方便于串的插入和删除操作，但是空间利用率不高，因为存放每一个字符要搭配一个指向下一字符的地址,而地址所占空间是比较大的。为了解决这种存储密度过低的状况，可以让一个结点存储多个字符，事实上这是顺序串和链串的综合(折衷)。子串定位运算又称串的模式匹配或串匹配，就是在主串中查找出子串出现的位置，这在应用中非常广泛，比如文本编辑中的查找和替换用到的就是子串定位运算的算法。第四章栈与队列栈的逻辑结构和我们先前学过的线性表相同，如果它是非空的，则有且只有一个开始结点，有且只能有一个终端结点，其它的结点前后所相邻的也只能是一个结点(直接前趋和直接后继),但是栈的运算规则与线性表相比有更多的限制，栈(Stack)是仅限制在表的一端进行插入和删除运算的线性表，通常称插入、删除这一端为栈顶，另一端称为栈底。表中无元素时为空栈。栈的修改是按后进先出的原则进行的，我们又称栈为LIFO表(LastInFirstOut).栈的基本运算有六种：构造空栈：InitStack(S)、判栈空:StackEmpty(S)、判栈满：StackFull(S)、进栈：Push(S,x)、可形象地理解为压入，这时栈中会多一个元素退栈：Pop(S)、可形象地理解为弹出，弹出后栈中就无此元素了。取栈顶元素：StackTop(S),不同与弹出，只是使用栈顶元素的值，该元素仍在栈顶不会改变。由于栈也是线性表，因此线性表的存储结构对栈也适用，通常栈有顺序栈和链栈两种存储结构，这两种存储结构的不同，则使得实现栈的基本运算的算法也有所不同。队列也是一种运算受限的线性表，它的运算限制与栈不同，是两头都有限制，插入只能在表的一端进行(只进不出)，而删除只能在表的另一端进行(只出不进)，允许删除的一端称为队尾(rear)，允许插入的一端称为队头(Front),队列的操作原则是先进先出的，所以队列又称作FIFO表(FirstInFirstOut)队列的基本运算也有六种：置空队：InitQueue(Q)判队空：QueueEmpty(Q)判队满：QueueFull(Q)入队：EnQueue(Q,x)出队：DeQueue(Q)取队头元素：QueueFront(Q),不同与出队，队头元素仍然保留队列也有顺序存储和链式存储两种存储结构，前者称顺序队列，后者为链队。为了克服空间浪费，我们引入循环向量的概念，就好比是把向量空间弯起来，形成一个头尾相接的环形，这样，当存于其中的队列头尾指针移到向量空间的上界(尾部)时，再加1的操作(入队或出队)就使指针指向向量的下界，也就是从头开始。这时的队列就称循环队列。通常我们应用的大都是循环队列。由于循环的原因，光看头尾指针重叠在一起我们并不能判断队列是空的还是满的，这时就需要处理一些边界条件，以区别队列是空还是满。方法至少有三种，一种是另设一个布尔变量来判断(就是请别人看着，是空还是满由他说了算)，第二种是少用一个元素空间，当入队时，先测试入队后尾指针是不是会等于头指针，如果相等就算队已满，不许入队。第三种就是用一个计数器记录队列中的元素的总数，这样就可以随时知道队列的长度了，只要队列中的元素个数等于向量空间的长度，就是队满。队列的链式存储结构称为链队列，一个链队列就是一个操作受限的单链表。为了便于在表尾进行插入(入队)的操作，在表尾增加一个尾指针，一个链队列就由一个头指针和一个尾指针唯一地确定。链队列不存在队满和上溢的问题。在链队列的出队算法中，要注意当原队中只有一个结点时，出队后要同进修改头尾指针并使队列变空。第五章二叉树与树树的逻辑结构特征是：树中任一结点都可以有零个或多个直接后继(孩子)结点，但至多只能有一个直接前趋(双亲)结点。树形结构是非线性结构。二叉树的定义：二叉树是n(n≥0)个结点的有限集，它或者是空集(n=0),或者由一个根结点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成。一般二叉树的3个重要性质：第i层至多有2i个结点高度为k的二叉树中，最多有2k+1－1个结点叶子数＝度2结点数－1二叉树的顺序存储结构就是把二叉树的所有结点按照一定次序(从根结点起，从上层到下层，从左往右编号就得到了存放的次序)存储到一片连续的存储单元中用顺序存储方式对于完全二叉树而言其结构简单又节省空间，但是对于一般二叉树并不合适。因此树的存储结构更多的是用链式存储。结点的结构为两个指针域lchild和rchild分别指向该结点的左孩子和右孩子，另有一个数据域data存放结点数据。把所有二叉树的结点，加上一个指向根结点的指针就构成了二叉树的链式存储结构，称为二叉链表。它就是由根指针root唯一确定的。根据访问结点的次序不同可得三种遍历：先序遍历(前序遍历或先根遍历)，中序遍历(或中根遍历)、后序遍历(或后根遍历)。遍历的算法就是一个递归算法，以中序遍历为例，它的定义为若二叉树非空，则依次执行如下操作：(1)遍历左子树；(2)访问根结点；(3)遍历右子树。将(1)(2)对调则得先序遍历，将(2)(3)对调则得后序遍历。利用二叉链表中的n+1个空指针域来存放指向某种遍历次序下的前趋结点和后继结点的指针，这些附加的指针就称为线索，加上线索的二叉链表就称为线索链表。二叉树线索化的目的及其实质：利用线索化后的二叉树中的线索就可以直接找到该结点在某种遍历序列中的前趋和后继结点。其实质就是在遍历过程中用线索取代空指针。在中序线索树中查找给定结点的中序前趋和中序后继的方法：若结点*p的左子树(或右子树非空)，则*p的中序前趋是从*p的左孩子开始沿着右指针链往下查找直到找到一个没有右孩子的结点为止，而*p的中序后继是从它的右孩子开始沿着左指针链往下直到找到一个没有左孩子的结点为止。线索使得查找中序前趋和中序后继变得简单有效，但对于查找指定结点的前序前趋和后序后继并没有什么作用。其原因是查找前序前趋和后序后继结点常常要用到给定结点的双亲结点才能找到，而线索二叉树中的结点没有指向其双亲结点的指针，所以线索对于这两种序列的结点查找并非有效。树和森林及二叉树的转换：三者是唯一对应的，它们之间的转换办法应掌握。（口诀一则）树变二叉：兄弟相连留长子。林变二叉：树变二叉根相连。二叉变树：左孩右右连双亲，去掉原来右孩线。树的存储结构：有双亲链表表示法（就是在每个结点设一指针指向其双亲以唯一地表示任何一棵树，用向量表示），这种表示法中指针是向上链接的，所以对于求指定结点的双亲或祖先十分方便，但不适于求指定结点的孩子及后代。孩子链表表示法（就是为树中每个结点设置一个孩子链表，并将结点及相应的孩子链表的头指针存放在一个向量中）孩子链表表示便于实现涉及孩子结点及子孙的运算，但不便于实现与双亲有关的运算。因此可以两种表示法结合形成双亲孩子链表表示法。孩子兄弟链表表示法