美文网首页
数据结构与算法学习

数据结构与算法学习

作者: gem_Y | 来源:发表于2020-05-28 10:02 被阅读0次

    书: 《数据结构与算法JavaScript描述》--Michael McMillan

    1.JavaScript的编程环境和模型

    (1)JavaScript 拥有的是函数作用域,其含义是 JavaScript 中没有块级作用域,这一点有别于其他很多现代编程语言。

    2. 数组

    数组的标准定义是:一个存储元素的线性集合(collection),元素可以通过索引来任意存取。

    2.4.3 从数组中间位置添加和删除元素

    两种操作都需要将数组中的剩余元素向前或向后移,然而 splice() 方法可以帮助我们执行其中任何一种操作

    var nums = [1,2,3,7,8,9];
    var newElements = [4,5,6];
    nums.splice(3,0,newElements);
    print(nums); // 1,2,3,4,5,6,7,8,9
    
    var nums = [1,2,3,100,200,300,400,4,5];
    nums.splice(3,4);
    print(nums); // 1,2,3,4,5
    
    2.4.4 为数组排序
    1. reverse()
    2. sort
    var names = ["David","Mike","Cynthia","Clayton","Bryan","Raymond"];
    names.sort();
    print(names); // Bryan,Clayton,Cynthia,David,Mike,Raymond
    
    var nums = [3,1,2,100,4,200];
    nums.sort();
    print(nums); // 1,100,2,200,3,4
    

    sort() 方法是按照\color{blue}{ 字典 }顺序对元素进行排序的,因此它假定元素都是字符串类型,在上一
    个例子中,即使元素是数字类型,也被认为是字符串类型。为了让 sort() 方法也能排序数
    字类型的元素,可以在调用方法时传入一个大小比较函数,排序时,sort() 方法将会根据
    该函数比较数组中两个元素的大小,从而决定整个数组的顺序

    function compare(num1, num2) {
    return num1 - num2;
    }
    var nums = [3,1,2,100,4,200];
    nums.sort(compare);
    print(nums); // 1,2,3,4,100,200
    

    sort() 函数使用了 compare() 函数对数组按照数字大小进行排序,而不是按照字典顺序

    2. 二维数组

    2.6.2 处理二维数组的元素

    4. 栈

    栈是一种特殊的列表,栈内的元素只能通过列表的一端访问,这一端称为栈顶。
    后进先出,咖啡厅内的一摞盘子是现实世界中常见的栈的例子

    // 实现一个栈
    export function Stack() {
      this.dataStore = []
      this.top = 0
      this.push = push
      this.pop = pop
      this.peek = peek
      this.clear = clear
      this.length = length
    }
    
    function push(element) {
      this.dataStore[this.top++] = element
    }
    
    function pop() {
      return this.dataStore[--this.top]
    }
    
    function peek() {
      return this.dataStore[this.top - 1]
    }
    
    function clear() {
      this.top = 0
    }
    
    function length() {
      return this.top
    }
    
        var s = new Stack()
        s.push('David-1')
        s.push('David-2')
        console.log('peek', s.peek())
        console.log('top:', s.top)
        s.pop()
        console.log('peek', s.peek())
    

    应用:
    利用栈将一个数字从一种数制转换成另一种数制

        mulBase(num, base) {
          const s = new Stack()
          do {
            s.push(num % base)
            num = Math.floor(num /= base)
          } while (num > 0)
    
          let converted = ""
          while(s.length() > 0) {
            converted += s.pop()
          }
          return converted
        }
    
        const newNum = this.mulBase(32, 2)
        console.log('32 convert to 二进制', newNum) // 32 convert to 二进制 100000
    

    相关文章

      网友评论

          本文标题:数据结构与算法学习

          本文链接:https://www.haomeiwen.com/subject/pzkoahtx.html