gblw

列表

日常生活中我们的购物清单，代办项都属于列表，计算机中的也是一样。 列表是一组有序的数据，每个列表中的数据项都成为元素，元素的数量受内存控制。

  • 元素不是很多
  • 不需要很长序列查找元素或排序
  • 是一种最自然的数据组织方式

迭代器有点:

  1. 访问元素时不必关心底层数据结构
  2. 增加或删除元素比for更灵活
  3. 迭代器为访问列表中的元素提供统一方法
        function List() {
            this.listSize = 0 //列表元素个数
            this.pos = 0 //列表当前位置
            this.dataStore = [] //初始化一个数组来存储列表
            this.clear = clear //清除列表
            this.find = find  //查找元素
            this.toString = toString //返回列表字符串形式
            this.insert = insert //在当前元素后面插入元素
            this.append = append //在末尾插入元素
            this.remove = remove //列表删除某个元素
            this.front = front // 将列表的位置移动到第一个元素
            this.end = end // 将列表的位置移动到最后一个元素
            this.prev = prev //当前元素向前移动一位
            this.next = next //当前元素向后移动一位
            this.moveTo = moveTo //将当前位置移动到某个位置
            this.length = length //当前列表数量
            this.currPos = currPos //返回当前位置
            this.getElement = getElement //返回元素当前位置
            this.contains = contains //列表是否包含元素
        }
        function length() {
            return this.listSize
        }

        function toString() {
            return this.dataStore
        }

        function find(ele) {
            // ++应该放到前面，以便返回正确的索引
            for( var i=0; i < this.dataStore.length; ++i) {
                if (this.dataStore[i] === ele) {
                    return i
                }
            }
                return -1
        }
        function remove(ele){
            let index = this.find(ele)
            if(index > -1) {
                this.dataStore.slice(index,1)
                --this.listSize
                return true
            }
            return false

        }
        // 在当前元素后面插入
        function insert(ele,afterEle) {
            var insertPos = this.find(afterEle)
            console.log(insertPos)
            if (insertPos >-1) {
                this.dataStore.splice(insertPos+1,0,ele)
                ++this.listSize
                return true
            }
            return false
        }

        function append(ele) {
            this.dataStore[this.listSize++] = ele
        }
        function clear() {
            delete this.dataStore
            this.dataStore = []
            this.listSize = this.pos = 0
        }

        function front() {
            this.pos = 0
        }

        function end() {
            this.pos = this.listSize - 1
        }

        function prev() {
            if (this.pos > 0) {
                --this.pos
            }
        }

        function next() {
            if (this.pos <this.listSize) {
                ++this.pos
            }
        }

        function currPos() {
            return this.pos
        }

        function moveTo(position) {
            this.pos = position
        }

        function getElement() {
            return this.dataStore[this.pos]
        }

        function contains(ele) {
            return this.find(ele) > -1
        }


        let name = new List()

        name.append('王猛')
        name.append('吴岑')
        name.append('王毅')
        name.next()
        // console.log(name.getElement())
        let s = name.insert('xx','王毅')
        console.log(s)
        console.log(name.toString())
        // 迭代器
        for (name.front();name.currPos()<name.length();name.next()) {
            console.log(name.getElement())
        }

栈

  • 栈是一种特殊的列表 是一种高效的数据结构，只能在栈顶增加或删除
  • (后出先入)LIFO(last in first out)(叠盘子)
  • 栈内的元素只能通过列表的一端访问，成为栈顶(反之 栈底)
  • 新增一个元素成为 入栈 或者进栈 压栈，删除-出栈退栈
    function Stack() {
        this.dataStore = []
        this.top = 0 //标记可以插入新元素的位置 入栈则增大 出栈则减小
        this.push = push //入栈
        this.pop = pop //出栈
        this.length = length
        this.clear = clear
        this.peek = peek //返回栈顶元素
    }
    //入栈 同时让指针top +1
    function push(ele) {
        this.dataStore[this.top++] = ele
    }

    //出栈 同时让指针-1 注意 --
    function pop() {
        return this.dataStore[--this.top]
    }

    // 注意指针不变，不删除
    function peek() {
        return this.dataStore[this.top - 1]
    }

    function length() {
        return this.top
    }

    function clear() {
        // this.dataStore = []
        this.top = 0
    }

    // let s = new Stack()

    // s.push('a')
    // s.push('b')
    // s.push('c')
    // s.push('d')
    // console.log(s)
    // console.log(s.length())
    // console.log('栈顶',s.peek())
    // console.log('出栈',s.pop())

    // 回文算法 abcdcba

    let word = 'abcdcba'

    function isPalindrome(word) {
        let s = new Stack()
        for (var i = 0, len = word.length; i < len; i++) {
            console.log(word[i])
            s.push(word[i])
        }
        let rword = ''

        while (s.length() > 0) {
            rword += s.pop()
            console.log(rword)
        }
        if (rword === word) {
            return true
        } else {
            return false
        }
    }
    let a = isPalindrome(word)
    console.log(a)

队列

  • 队列只能在队尾插入，队首删除
  • FIFO(First-In-First-Out) 插入的元素叫入队 删除元素叫出队
  • 有一种特殊的情况不需按着FIFO的约定，比如急诊，这种需要 优先队列的数据结构来模拟
function Queue() {
    this.dataStore = []
    this.enqueue = enqueue
    this.dequeue = dequeue
    this.priorityDequeue = priorityDequeue //根据level优先出队
    this.first = first
    this.back = back
    this.empty = empty
    this.toString = toString
}
// 入队
function enqueue(val) {
    this.dataStore.push(val)
}
// 出队
function dequeue() {
    return this.dataStore.shift()
}
// 队首
function first() {
    return this.dataStore[0]
}
// 队尾
function back() {
    return this.dataStore[this.dataStore.length - 1]
}
// 是否为空队列
function empty() {
    return this.dataStore.length === 0
}

function toString() {
    let str = ''
    for (var i = 0, len = this.dataStore.length; i < len; i++) {
        str += this.dataStore[i] + '\n'
    }
    return str
}

let q = new Queue()

// 入队
q.enqueue('wm')
q.enqueue('wmm')
q.enqueue('wmmm')
console.log(q)
// 出队
q.dequeue()
console.log(q)
console.log(q.first())
console.log(q.back())
console.log(q.empty())
console.log(q.toString())

// 实现方块舞的舞伴分配问题

let manDancer = new Queue()
manDancer.enqueue('老王')
manDancer.enqueue('老李')

let womenDancer = new Queue()
womenDancer.enqueue('小王')
womenDancer.enqueue('小李')

function getDancers() {
    return '👱'+ manDancer.dequeue() + '  👩' + womenDancer.dequeue()
}

console.info('第一队舞伴'+ getDancers())
console.info('第二队舞伴'+ getDancers())


// 优先队列 数组

function Patient(name,level) {
    this.name = name
    this.level = level //优先级
}
// 优先出队
function priorityDequeue() {
    let priority = 0;
    for (let i=0,len=this.dataStore.length;i<len;i++) {
        if (this.dataStore[priority].level > this.dataStore[i].code) {
            priority = i
        }
        return this.dataStore.splice(priority,1)
    }
}
const ins1 = new Patient('小王',4)
const ins2 = new Patient('小李',1)
const ins3 = new Patient('小明',3)
const ins4 = new Patient('小岑',2)

const PatientQueue = new Queue()

PatientQueue.enqueue(ins1)
PatientQueue.enqueue(ins2)
PatientQueue.enqueue(ins3)
PatientQueue.enqueue(ins4)

let out = PatientQueue.priorityDequeue()
console.log('出队', out)

链表

  • 数组不是数据最佳结构。
  • js的数组被实现成了对象，与其他语言相比，效率低很多。
  • 如果你发现数据实际使用时很慢，就可以用链表替代他，除了对数据的随机访问，链表几乎可以用在使用所有使用以为数组的地方。
  • 链表是有由一系列 节点组成的集合，每个节点都使用一个对象的引用指向他的后续，

字典

  • 以键值 key-value 对形式存储，js中object就是以字典形式设计的
改善此页
Last Updated: 10/23/2019, 1:02:24 PM