【昊昊带你学】基本数据结构(下)

《【昊昊带你学】基本数据结构(下)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

链表前面大家用队、栈的时候用的都是数组。数组挺好用的，不过蛋疼的是，数组里面要增、删数据就蛋疼了。不过咱们有链表，下面我来丑陋地给大家画个链表~哈哈，说了画给大家，就果断要亲手画，果然很丑陋的说O_o我来简单给大家先说一下链表的每个节点都是怎么个结构~看中间那一坨，这就是一个节点，prev部分指向它的前驱，而next则指向它的后继。这样，该节点就成功得与前后向链接了。而中间那个data（不是dota哟~）就是这个节点的数据部分，当然不一定只有一个，画成一个比较清晰而已。大家看到最右边节点的后继中是个“/”，这代表着指向null，即空。碰到这种情况，就是说，这已经是链表的一端了。当然头和尾都有可能。最左边那个head()就是这个链表的头指针，头指针可以让你能够找到链表中的第一个元素，大家应该明白，链表不像数组，可以通过下标直接找到节点（优化除外~），这时候，你要用链表中某一个节点的时候就得从头指针往后遍历。我们可以看到，链表比数组好在它能够很方便的在某处增加节点或删除节点，但同时，数组对于每个元素的定位又更加快速~两个数据结构都各有千秋，大家要结合实际问题灵活选用。下面来将一些具体的函数：LIST-SEARCH(L,k)X←head[L]Whilex≠NILandkey[x]≠kDox←next[x]ReturnxPS:这是在链表中搜索某结点的一个方法。L是一个链表，k是我们要搜索的KEY，我们先把L的头指针给x，然后当x还指向链表中节点并且没有发现KEY值的时候做x←next[x]这件事，那这件事是什么意思呢？有的孩纸应该看明白了，就是将x指向当前节点的后继，从而达到链表遍历的目的。LIST-INSERT(L,x)next[x]←head[L]Ifhead[L]≠NILThenprev[head[L]]←xHead[L]←xPrev[x]←NILPS：这是在链表头插入节点的方法。L是一个链表，x是一个节点（这个时候x还是孤零零 的一个~）。我们先让x的后继指向本来的头结点。如果头结点不为空，就将它的前驱指向x（之前前驱为空）。此时，头指针指向x。最后将x的前驱赋为空。大家可以自己在草稿纸上画一下上述过程。如果是在链表中插入结点，类似，希望童鞋们自行考虑该如何操作，只要注意四个地方的指向（可能会有点绕，不过结构是很对称的）：前驱，后继，前驱的后继，后继的前驱。搞清楚这四个的关系，其实也是链表最核心的东西~LIST-DELETE(L,x)Ifprev[x]≠NILThennext[prev[x]]←next[x]Elsehead[L]←next[x]Ifnext[x]≠NILThenprev[next[x]]←prev[x]PS:这是在链表中删除一个节点。L是一个链表，x是一个节点。首先如果x的前驱不为空，那么就将前驱的后继指向x本来的后继，否则x是头结点，那么直接将头指针指向x的后继。接下来，如果后继不为空则将后继的前驱指向x本来的前驱，当然如果是空的话，你不用理会。删除操作的核心，还是我们刚刚提到的四点：前驱，后继，前驱的后继，后继的前驱。大家看一眼下图，这是在链表中删除节点的情况。①所对应的就是第一个if的操作，它将前驱（prev[x]）的后继(next[prev[x]]==next[x])指向了原本的后继（next[x]）。第二步类似。对于链表还有一种哨兵的优化，如果大家有兴趣可以自行百度谷歌，也可以联系我来讨论哈。树（二叉树）链表整完了，咱们来说说树，这里我们重点讲二叉树。树的每个节点结构与链表挺类似的，只是原来的前驱、后继变为了父亲、左右孩子。 在网上给大家粘了个图下来，L就是左孩子，R就是右孩子，这个图没有把父亲的域画出来，大家应该可以明白是什么意思。我们以后再画二叉树就不会再带着左右两个域，请大家注意。最顶端的节点叫做根，当然也有单独把根拿出来的情况，个人感觉看情况吧。而最底层的节点（没有孩子节点）的叫做叶子节点。有了链表的基础，我相信这里的增、删、查找大家应该可以自行完成，就算不会我估计看代码也可以看得懂了，我就不再这矫情地一点一点分析了。直接来给大家讲一讲二叉树的一种建树方法，以及依靠递归来实现的三序遍历。首先来提一下三序遍历：先序遍历：首先访问根结点然后遍历左子树，最后遍历右子树。什么意思呢？遍历一棵树我们可以把问题分解开。遍历一整棵树，我们可以先访问根节点（这显然可以做到），然后遍历左子树，最后遍历右子树。可以看到我们把原来的问题分划成了三个子问题：第一个访问根节点，我们已经解决。后两个问题是，分别遍历左右子树。（场外观众小贤：咦？这不是原来的问题？）bingo！我们把原来的问题分成了三个规模更小的问题，一个已经解决，另两个跟原来的问题一样。这就是传说中的分治算法，分而治之！对于遍历左子树的问题，我们同样可以先访问左子树的根，再遍历下面的左右子树………………分划啊分划~直到分化到某一个叶节点的时候，访问该节点，无左右孩子，退回上一层。建议童鞋们自己画一个三层左右的二叉树，自己按这个过程体会一下分治的思想，分治的思想搞清楚之后，进一步去理解递归就会轻松的多了。下面我给大家粘一段我暑假作业的代码。是java的，我就不用伪代码了。TT《导论》上没有，不敢瞎写。staticpublicvoidpreOrder(Nodenode){if(node!=null){node.print();preOrder(node.leftChild);preOrder(node.rightChild);}else{System.out.print('#');} }PS:我给大家解读一下这段代码，不是很难。preOrder就是先序遍历。Nodenode说的是传进来一个Node类型的node，它是一个节点，(Node类有leftChild和rightChild两个域，还有data。)这就是我们要遍历子树的根节点。如果节点不为空的话我们先打印出node本身，然后我们分别先序遍历左右孩子，如果为空看具体情况操作，我编的这段代码是用#来表示NIL。这里递归的理解的确是个难点，大家静下心来手动走几遍过程就会改善许多。（艾玛累死了，苏海~~~~~~过来给爷揉揉肩）相信有了先序的铺垫，中序和后序就会轻松很多。中序遍历：中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。后序遍历：后序遍历首先遍历左子树，然后遍历右子树，最后遍历访问根结点。在递归实现的情况下，这三个几乎没有差别，就是在上面if语句中颠倒一下几个语句的位置。而在用栈来实现非递归的三序遍历时就会有较大的差别了~至少本菜自己编的时候这三种顺序差别很大。讲如何去建立一棵树：建树的方法有很多，我只讲一下我自己最常用的一种方法。输入的数据是按照先序给出的二叉树，‘#’代表叶节点。比如ABC##DE#G##F###就会建立出如下的一棵二叉树：下面给出java的一段代码：staticNodecreateTree(){Nodenode=null; if(ch[i]!='#'){node=newNode();node.data=ch[i];i++;node.leftChild=createTree();node.rightChild=createTree();}else{i++;}returnnode;}PS：i是Node类的一个静态变量，记录建树的进度。首先创建一个空结点，如果表达式中当前值不是#，那么给node赋值，再分别给左右孩子建树。这是按照先序来的。跟刚刚先序遍历几乎一样，大家可以对照看看，不过多敖述。下面给出的这个链接中，是一棵二叉排序树，它的建树规则就是左子树中的数<=根中的数<=右子树中的数http://www.cs.usfca.edu/~galles/visualization/BST.html