数据结构电子书

插入排序就是把当前待排序的元素插入到一个已经排好序的列表里面。 一个非常形象的例子就是右手抓取一张扑克牌，并把它插入左手拿着的排好序的扑克里面。 插入排序的最坏运行时间是O(n2)， 所以并不是最优的排序算法。 如果输入数组已经是排好序的话，插入排序出现最佳情况，其运行时间是输入规模的一个线性函数。 如果输入数组是逆序排列的，将出现最坏情况。平均情况与最坏情况一样，其时间代价是Θ(n2)。 简单例子： public class Demo6 { public static void main(String[] args) { //定义一个整型数组 int[] nums = new int[]{4,3,-1,9,2,1,8,0,6}; //打印没有进行排序的数组 System.out.println("没有排序之前的结果:" + Arrays.toString(nums)); for(int index=0; indexnums.length; index++) { //获得需要插入的数值 int key = nums[index]; //取得下标值 int position = index; /循环比较之前排序好的数据，找……

本文实例讲述了JavaScript数据结构与算法之二叉树遍历算法。分享给大家供大家参考，具体如下： javascript数据结构与算法--二叉树遍历（先序） 先序遍历先访问根节点， 然后以同样方式访问左子树和右子树 代码如下： /* *二叉树中，相对较小的值保存在左节点上，较大的值保存在右节点中 * * * *//*用来生成一个节点*/function Node(data, left, right) { this.data = data;//节点存储的数据 this.left = left; this.right = right; this.show = show;}function show() { return this.data;}/*用来生成一个二叉树*/function BST() { this.root = null; this.insert = insert;}/*将数据插入二叉树 （1）设根节点为当前节点。 （2）如果待插入节点保存的数据小于当前节点，则设新的当前节点为原节点的左节点；反 之，执行第4步。 （3）如果当前节点的左节点为null，就将新的节点插入这个位置，退出循环；反之，继续 执……

作为我最近一直在进行的一些编码访谈的一部分，有时会出现不变性问题。我自己并不过分教条，但每当不需要可变状态时，我会试图摆脱导致可变性的代码，这在数据结构中通常是最明显的。然而，似乎对不可变性的概念存在一些误解，开发人员通常认为拥有final引用，或者val在Kotlin或Scala中，足以使对象不可变。这篇博客文章深入研究了不可变引用和不可变数据结构。 不可变数据结构的好处 不可变数据结构具有显着优势，例如： 没有无效的状态 线程安全 易于理解的代码 更容易测试代码 可用于值类型 没有无效的状态 当一个对象是不可变的时，很难让对象处于无效状态。该对象只能通过其构造函数实例化，这将强制对象的有效性。这样，可以强制执行有效状态所需的参数。一个例子： Address address = new Address();address.setCity("Sydney");// address is in in……

本文实例讲述了JavaScript数据结构与算法之队列原理与用法。分享给大家供大家参考，具体如下： 队列是一种列表，不同的是队列只能在队尾插入元素，在队首删除元素。队列用于存储按顺序排列的数据，先进先出，这点和栈不一样(后入先出)。在栈中，最后入栈的元素反而被优先处理。我们现在可以把队列想象对我们去餐馆吃饭的情景，很多人排队吃饭，排在最前面的人先打饭。新来的人只能在后面排队。直到轮到他们为止。 一：对队列的操作 队列有2种主要的操作，向队尾中插入新元素 enqueue() 方法和删除队列中的队首的元素的 dequeue() 方法，另外我们还有一个读取队头的元素，这个方法我们可以叫 front() 方法。该方法返回队头元素等等方法。 看到如上描述，我们很多人可能会想到数组，数组里面也有2个方法和上面的方法功能类似，数组中 push(……

本文实例讲述了javascript数据结构中栈的应用之符号平衡问题。分享给大家供大家参考，具体如下： 由于栈先进后出的结构，我们可以将其作为有用的工具，下面就介绍一下栈的应用。 首先是符号的平衡问题。有一串字符串，我们需要判断其中固定的字符是否成对出现，比如 {} [] () 等。当然实现的方法有很多，但是采用栈的实现会相对更加简单。 实现上述算法的JavaScript代码如下 !DOCTYPE htmlhtml head meta charset="utf-8" title/title /head bodyscript type="text/javascript" function isbalance(str){ var str=str.toString(), len=str.length, myArray=new Array(); for(var i=0;ilen;i++){ if(str[i]=='['||str[i]=='{'||str[i]=='('){ myArray.push(str[i]); } if(str[i]==']'||str[i]=='}'||str[i]==')'){ if(myArray.length==0){ document.write("the string 不平衡"); return false; } var popValue=myArray.pop(); switch(str[i]){ case ']':{ if('['!=popValue){ document.write('] 不平衡……

本文实例讲述了Python数据结构之双向链表的定义与使用方法。分享给大家供大家参考，具体如下： 和单链表类似，只不过是增加了一个指向前面一个元素的指针而已。 示意图： python 实现代码： #!/usr/bin/python# -*- coding: utf-8 -*-class Node(object): def __init__(self,val,p=0): self.data = val self.next = p self.prev = pclass LinkList(object): def __init__(self): self.head = 0 def __getitem__(self, key): if self.is_empty(): print 'linklist is empty.' return elif key 0 or key self.getlength(): print 'the given key is error' return else: return self.getitem(key) def __setitem__(self, key, value): if self.is_empty(): print 'linklist is empty.' return elif key 0 or key self.getlength(): print 'the given key is error' return else: self.delete(key) return self.insert(key) def initlist(self,data): self.head = Node(data[0]) p = self.head for i in data[1:]: node = Node(i) p.next = node node.prev = p p = p.next def getlength(self)……