### 数据结构基础篇

2021-05-25 本文已影响0人 xinmin

数据结构与算法

入门篇

复杂度分析

时间复杂度

大O时间复杂度表示法，表示代码执行时间随数据规模增长的变化趋势，也叫渐进时间复杂度，简称时间复杂度。

规律公式：T(n) = O(f(n))

// 求1,2,3,4...N的累加和
var numSum = function(n) {
 var sum = 0;
 for(var i=1; i<=n; ++i) {
     sum = sum + i
 }
 return sum
}
/** 假设每行代码执行的时间为u
nit_time则代码的执行总时间：`T(n) = (2n+1)*unit_time`
*/
var cal = function(n) {
 var sum = 0;
 for(var i=1; i<=n; ++i) {
     for(var j=1; j<=n; ++j) {
         sum = sum + i*j
     }
 }
 return sum
}
/** 假设每行代码执行的时间为unit_time则代码的执行总时间：
   T(n) = (2n^2+n+2)*unit_time
*/

总结：

只关注循环执行次数最多的一段代码
加法法则：总复杂度等于量级最大的那段代码的复杂度
乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
常见时间复杂度：

O(1) O(logn) O(nlogn) O(n) O(n^2)

基础篇

基于数组实现栈结构

function Stack() {
  // 栈中的属性
  this.items = []
  // 1. 入栈
  Stack.prototype.push = function (ele) {
    this.items.push(ele)
  }
  // 2. 出栈
  Stack.prototype.pop = function () {
    return this.items.pop()
  }
  // 3. 查看栈顶元素
  Stack.prototype.peek = function () {
    return this.items[this.items.length - 1]
  }
  // 4. 判断栈是否为空
  Stack.prototype.isEmpty = function () {
    return this.items.length === 0
  }
  // 5. 获取栈中元素的个数
  Stack.prototype.size = function () {
    return this.items.length
  }
  // 6. toString
  Stack.prototype.toString = function () {
    let resString = ''
    for (let i = 0; i < this.items.length; i++) {
      resString += this.items[i] + ''
    }
    return resString
  }
}

// 测试
// const s = new Stack()
// s.push(1)
// s.push(20)
// s.push(21)
// s.push(23)
// s.push(1001)
// console.log('push==', s)
// console.log('peek', s.peek())
// console.log('peek end==', s)
// s.pop()
// s.pop()
// console.log('pop==', s)
// console.log('size==', s.size())
// console.log('isEmpty==', s.isEmpty())
// console.log('toString', s.toString())

1.1 应用

// 栈的应用：十进制转二进制
function dec2bin(decNum) {
  // 1. 创建一个栈
  // 2. decNum % 2 取余数压入栈
  // 3. decNum = decNum / 2 整除后的结果赋值给decNum
  // 4. 循环结束条件，decNum <= 0
  const stack = new Stack()
  while (decNum > 0) {
    stack.push(decNum % 2)
    decNum = Math.floor(decNum / 2)
  }
  let res = ''
  while (!stack.isEmpty()) {
    res += stack.pop()
  }
  return res
}

// 测试十进制转二进制
console.log(dec2bin(100))

基于数组实现队列

function Queue() {
  // 属性
  this.items = []
  // 1. 向队尾加入一个或多个元素
  Queue.prototype.enqueue = function (ele) {
    this.items.push(ele)
  }
  // 2. 删除队列中最前面的一项，并返回被移除的元素（改变原队列）
  Queue.prototype.dequeue = function () {
    return this.items.shift()
  }
  // 3. 返回队列中最前面的一项(不改变原对列)
  Queue.prototype.front = function () {
    return this.items[0]
  }
  // 4. 检验对垒是否为空
  Queue.prototype.isEmpty = function () {
    return this.items.length === 0
  }
  // 5. 查看队列的元素个数
  Queue.prototype.size = function () {
    return this.items.length
  }
  // 6. tosTring
  Queue.prototype.toString = function () {
    let resString = ''
    for (let i = 0; i < this.items.length; i++) {
      resString += this.items[i] + ''
    }
    return resString
  }
}

// test
// const q = new Queue()
// q.enqueue(1)
// q.enqueue(2)
// q.enqueue(31)
// q.enqueue(14)
// console.log(q)
// q.dequeue()
// console.log(q)
// console.log(q.isEmpty())
// console.log(q.front())
// console.log(q)
// console.log(q.size())
// console.log(q.toString())

2.1 队列的应用

// 队列的应用：击鼓传花 -> n个人围成一圈数数，数到数字 m 时则退出游戏，
//                     最后剩下的一个人为胜利者，求胜利者是原来那个位置上的人
function passGame(nameList, num) {
  const queue = new Queue()
  // 将所有数据加入队列
  for (let i = 0; i < nameList.length; i++) {
    queue.enqueue(nameList[i])
  }
  // 开始数数，结束条件是只剩一个时
  while (queue.size() > 1) {
    // 不是 num 时，取出重新加入到队尾
    for (let j = 0; j < num - 1; j++) {
      queue.enqueue(queue.dequeue())
    }
    // 是 num 时，将其从队列中删除
    queue.dequeue()
  }
  // 获取剩下的那个人, 求他所在位置
  const endName = queue.front()
  console.log(endName)
  return nameList.indexOf(endName)
}

// // 测试
// console.log(passGame(['zs', 'ls', 'ww', '小明', '小凡凡', '小民哥'], 6))

基于数组的优先队列

function PriorityQueue() {
  // 可以看做内部类
  function QueueElement(element, priority) {
    this.element = element
    this.priority = priority
  }
  // 属性
  this.items = []

  // 1. 实现队列的插入数据方法
  PriorityQueue.prototype.enqueue = function (element, priority) {
    // 1.1 创建 QueueElement 实例
    const queueElement = new QueueElement(element, priority)
    // 1.2 判断队列是否为空，为空直接添加
    //     如果不为空，循环判断，加入合适位置添加，停止循环
    //     如果循环结束仍然没有添加进去，就直接添加到队尾
    if (this.items.length === 0) {
      this.items.push(queueElement)
    } else {
      let added = false
      for (let i = 0; i < this.items.length; i++) {
        if (queueElement.priority < this.items[i].priority) {
          this.items.splice(i, 0, queueElement)
          added = true
          break
        }
      }
      if (!added) {
        this.items.push(queueElement)
      }
    }
  }
  // 2. 删除队列中最前面的一项，并返回被移除的元素（改变原队列）
  PriorityQueue.prototype.dequeue = function () {
    return this.items.shift()
  }
  // 3. 返回队列中最前面的一项(不改变原队列)
  PriorityQueue.prototype.front = function () {
    return this.items[0]
  }
  // 4. 检验对列是否为空
  PriorityQueue.prototype.isEmpty = function () {
    return this.items.length === 0
  }
  // 5. 查看队列的元素个数
  PriorityQueue.prototype.size = function () {
    return this.items.length
  }
  // 6. tosTring
  PriorityQueue.prototype.toString = function () {
    let resString = ''
    for (let i = 0; i < this.items.length; i++) {
      resString += this.items[i].element + '' + this.items[i].priority + ' '
    }
    return resString
  }
}

// test
// const pq = new PriorityQueue()
// pq.enqueue('abc', 1)
// pq.enqueue('abc', 10)
// pq.enqueue('abc', 120)
// pq.enqueue('abc', 101)
// pq.enqueue('abc', 21)
// console.log(pq.toString())

实现单链表

function LinkedList() {
  // 内部类: 节点
  function Node(data) {
    this.data = data
    this.next = null
  }
  // 属性
  this.head = null
  this.length = 0
  // 1. 向链表尾部添加一个新的项
  LinkedList.prototype.append = function (data) {
    // 创建一个新节点
    const newNode = new Node(data)
    /**
     * 判断是否是第一个节点，如果是让 head 直接指向新节点
     * 如果不是第一个节点，就要循环，直到 next -> null
     * 这里定义了 current 变量代指循环过程中的节点，最终循环结束找到最后一个节点，current.next -> 新节点
     */
    if (this.length === 0) {
      this.head = newNode
    } else {
      let current = this.head
      while (current.next) {
        current = current.next
      }
      current.next = newNode
    }
    this.length += 1
  }
  // 2. 向链表特定的位置插入一个新的项
  LinkedList.prototype.insert = function (position, data) {
    /**
     *  情况一：插入position为0的位置，先把新节点的 next 指向 head，再让 head 指向新节点
     *  情况二：0 < position <= this.length 循环赋值前一个节点 previous 和 当前节点 current
     *         让前一个节点指向添加的新节点，添加的新节点指向 current
     */
    // 对 position 做越界处理
    if (position < 0 || position > this.length || typeof position != 'number')
      return false
    // 创建一个新节点
    const newNode = new Node(data)
    if (position === 0) {
      newNode.next = this.head
      this.head = newNode
    } else {
      let index = 0
      let current = this.head
      let previous = null
      while (index++ < position) {
        previous = current
        current = current.next
      }
      newNode.next = current
      previous.next = newNode
    }
    this.length += 1
    return true
  }
  // 3. 获取对应位置的元素
  LinkedList.prototype.get = function (position) {
    // 越界判断
    if (position < 0 || position >= this.length || typeof position != 'number')
      return null
    // 获取对应的 data 循环链表，移动 current
    let current = this.head
    let index = 0
    while (index++ < position) {
      current = current.next
    }
    return current.data
  }
  // 4. 返回元素在链表中的索引，如果链表中没有该元素返回-1
  LinkedList.prototype.indexOf = function (data) {
    // 定义指针变量和index
    let current = this.head
    let index = 0
    // 开始查找
    while (current) {
      if (current.data === data) return index
      current = current.next
      index += 1
    }
    return -1
  }
  // 5. 修改链表中某个位置的元素
  LinkedList.prototype.update = function (position, newData) {
    // 越界判断
    if (position < 0 || position >= this.length || typeof position != 'number')
      return false
    // 查找节点
    let current = this.head
    let index = 0
    while (index++ < position) {
      current = current.next
    }
    // 将 current 指向的node节点的data修改为新的data
    current.data = newData
    return true
  }
  // 6. 从链表中的特定位置移除一项
  LinkedList.prototype.removeAt = function (position) {
    /**
     *  情况一：删除 position 为 0 的位置的元素，直接将原来的head指向head.next
     *  情况二：0 < position < this.length 循环获取上一个节点和当前节点，直接让上一个节点的next指向当前节点的next
     */
    // 越界判断
    if (position < 0 || position >= this.length || typeof position != 'number')
      return null
    // position 为0，head 直接指向之前指向的下一个
    let current = this.head
    if (position === 0) this.head = this.head.next
    else {
      let index = 0
      let previous = null
      while (index++ < position) {
        previous = current
        current = current.next
      }
      // 前一个节点的 next 不在指向current，而是指向current.next
      previous.next = current.next
    }
    this.length -= 1
    return current.data
  }
  // 7. 从链表中移除一项
  LinkedList.prototype.remove = function (data) {
    // 1. 获取data在链表中的位置
    let position = this.indexOf(data)
    // 2. 根据位置信息，删除节点
    return this.removeAt(position)
  }
  // 8. 判断链表是否为空，true or false
  LinkedList.prototype.isEmpty = function () {
    return this.length === 0 ? true : false
  }
  // 9. 返回链表中的元素个数
  LinkedList.prototype.size = function () {
    return this.length
  }
  // 10. 输出元素的值 toString
  LinkedList.prototype.toString = function () {
    let current = this.head
    let listStr = ''
    while (current) {
      listStr += current.data + ' '
      current = current.next
    }
    return listStr
  }
}

// test
// const list = new LinkedList()
// console.log(list.isEmpty())
// // 添加
// list.append(1)
// list.append(2)
// list.append(3)
// list.append(4)
// // insert
// list.insert(3, '111')
// list.insert(5, '222')
// list.insert(0, '000')
// // update
// list.update(0, 'ccc')

// console.log(list.toString())
// console.log(list.get(6))
// console.log(list.indexOf('ccc'))
// console.log(list.removeAt(0))
// console.log(list.toString())
// console.log(list.remove(1))
// console.log(list.toString())
// console.log(list.size())
// console.log(list.isEmpty())

实现双向链表

function DoublyLinkedList() {
  // 节点类
  function Node(data) {
    this.data = data
    this.prev = null
    this.next = null
  }
  // 属性
  this.head = null
  this.tail = null
  this.length = 0

  // 1. 向列表尾部添加一个新的项
  DoublyLinkedList.prototype.append = function (data) {
    // 创建一个新节点
    const newNode = new Node(data)
    /**
     * 判断是否是第一个节点，如果是让 head，tail 都指向 newNode
     * 如果不是第一个节点， 新节点newNode.prev = tail 之前尾部节点 tail.next = newNode
     * 再将尾部节点指向新节点 tail = newNode
     */
    if (this.length === 0) {
      this.head = newNode
      this.tail = newNode
    } else {
      newNode.prev = this.tail
      this.tail.next = newNode
      this.tail = newNode
    }
    this.length += 1
  }
  // 2. 向列表特定位置插入一个新的项
  DoublyLinkedList.prototype.insert = function (position, data) {
    /**
     * 情况一：列表为空的情况（length = 0） tail指向newNode，head指向newNode
     * 情况二：position = 0 原来节点的 prev 指向 newNode
     *       新节点 newNode.next 指向原来的节点
     *       head指针指向新的节点 newNode
     * 情况三：position = length 则与 append 的逻辑相同
     * 情况四： 0 < position < length 循环找到替换位置的节点，
     *        新节点 prev 指向找到节点的上一个节点(即是：current.prev)，
     *        新节点的next 指向找到的节点（current)
     *        找到节点的上一个节点的next指向新节点（current.prev.next -> newNode）
     *        找到的节点的 prev 指向新的节点
     */
    // 对 position 做越界处理
    if (position < 0 || position > this.length || typeof position != 'number')
      return false
    // 创建新节点
    const newNode = new Node(data)
    if (this.length === 0) {
      this.head = newNode
      this.tail = newNode
    } else {
      if (position === 0) {
        this.head.prev = newNode
        newNode.next = this.head
        this.head = newNode
      } else if (position === this.length) {
        newNode.prev = this.tail
        this.tail.next = newNode
        this.tail = newNode
      } else {
        let current = this.head
        let index = 0
        while (index++ < position) {
          current = current.next
        }
        // 修改指针
        newNode.next = current
        newNode.prev = current.prev
        current.prev.next = newNode
        current.prev = newNode
      }
    }
    this.length += 1
    return true
  }
  // 3. 获取对应位置的元素
  DoublyLinkedList.prototype.get = function (position) {
    // 对 position 做越界处理
    if (position < 0 || position >= this.length || typeof position != 'number')
      return null
    // 优化: 利用length/2与position比较，判断是从后往前还是从前往后循环
    let poor = this.length / 2 - position
    // 循环，找到与 position 对应的项
    let current = null
    if (poor > 0) {
      current = this.head
      let index = 0
      while (index++ < position) {
        current = current.next
      }
    } else {
      current = this.tail
      let index = this.length - 1
      while (index-- > position) {
        current = current.prev
      }
    }
    return current.data
  }
  // 4. 返回元素在链表中的索引，如果链表中没有该元素返回-1
  DoublyLinkedList.prototype.indexOf = function (data) {
    // 循环（结束条件current -> null) 找到 current.data = data 结束，返回index
    let current = this.head
    let index = 0
    while (current) {
      if (current.data === data) {
        return index
      }
      current = current.next
      index += 1
    }
    return -1
  }
  // 5. 修改列表中某个位置的元素
  DoublyLinkedList.prototype.update = function (position, newData) {
    // 对 position 做越界处理
    if (position < 0 || position >= this.length || typeof position != 'number')
      return false
    // 优化: 利用length/2与position比较，判断是从后往前还是从前往后循环
    let poor = this.length / 2 - position
    // 循环，找到与 position 对应的项
    let current = null
    if (poor > 0) {
      current = this.head
      let index = 0
      while (index++ < position) {
        current = current.next
      }
    } else {
      current = this.tail
      let index = this.length - 1
      while (index-- > position) {
        current = current.prev
      }
    }
    current.data = newData
    return true
  }
  // 6. 从列表中特定位置移除某一项
  DoublyLinkedList.prototype.removeAt = function (position) {
    /**
     * 情况一：删除节点只有一个，则head和tail指向null
     * 情况二：列表不止一个节点，删除的节点为第一个position = 0,
     *        head 指向的节点的下一个节点的prev指向 null
     *        head 指向原来指向节点的下一个接点 head -> head.next
     * 情况三： 列表不止一个节点，删除的节点是最后一个节点 position = length-1
     *         tail指向节点的上一个节点的next 指向 null
     *         tail指向上一个节点的 prev
     * 情况四：0 < position < length-1
     *        从前往后循环，找到 current，current的上一个节点直接指向它的下一个节点
     *        current的下一个节点的prev直接指向它的上一个节点
     */
    // 对 position 做越界处理
    if (position < 0 || position >= this.length || typeof position != 'number')
      return null
    // 放到全局
    let current = this.head
    // 只有一个节点
    if (this.length === 1) {
      this.head = null
      this.tail = null
    } else {
      if (position === 0) {
        this.head.next.prev = null
        this.head = this.head.next
      } else if (position === this.length - 1) {
        current = this.tail
        this.tail.prev.next = null
        this.tail = this.tail.prev
      } else {
        let index = 0
        while (index++ < position) {
          current = current.next
        }
        current.prev.next = current.next
        current.next.prev = current.prev
      }
    }
    this.length -= 1
    return current.data
  }
  // 7. 从列表中移除一项
  DoublyLinkedList.prototype.remove = function (data) {
    // 根据data获取index
    let index = this.indexOf(data)
    // 根据index删除
    return this.removeAt(index)
  }
  // 8. 判断列表是否为空 return false or true
  DoublyLinkedList.prototype.isEmpty = function () {
    return this.length === 0
  }
  // 9. size 返回链表包含的元素个数
  DoublyLinkedList.prototype.size = function () {
    return this.length
  }
  // 10. toSting
  DoublyLinkedList.prototype.toString = function () {
    return this.backwardString()
  }
  // 11. 返回向前遍历的节点字符串形式
  DoublyLinkedList.prototype.forwardString = function () {
    let current = this.tail
    let resStr = ''
    // 依次向前遍历，获取每个节点，移动指针
    while (current) {
      resStr += current.data + ''
      current = current.prev
    }
    return resStr
  }
  // 12. 返回向后遍历的节点字符串形式
  DoublyLinkedList.prototype.backwardString = function () {
    let current = this.head
    let resStr = ''
    // 依次向后遍历，获取每个节点，移动指针
    while (current) {
      resStr += current.data + ''
      current = current.next
    }
    return resStr
  }
  // 13. 获取链表第一个元素
  DoublyLinkedList.prototype.getHead = function () {
    return this.head.data
  }
  // 14. 获取链表最后一个元素
  DoublyLinkedList.prototype.getTail = function () {
    return this.tail.data
  }
}

// test
// let list = new DoublyLinkedList()

// list.append('111')
// list.append('122')
// list.append('333')
// list.append('444')
// list.append('555')

// console.log(list)
// console.log(list.backwardString())
// console.log(list.forwardString())
// console.log(list.toString())

// list.insert(2, 'aaaa')
// list.insert(0, 'ccc')
// list.insert(5, 'zzz')

// console.log(list.toString())
// console.log(list.size())
// console.log(list.get(7))
// console.log(list.indexOf('zzz'))
// console.log(list.update(5, 'ggg'))
// console.log(list.update(8, 'ttt'))
// console.log(list.toString())
// console.log(list.removeAt(1))
// console.log(list.toString())
// console.log(list.remove(122))
// console.log(list.toString())

// console.log(list.isEmpty())
// console.log(list.getHead())
// console.log(list.getTail())

### 数据结构基础篇

数据结构与算法

猜你喜欢

热点阅读