数据结构笔记

什么是数据结构
跟语言无关，跟实现无关

举例：

队列、栈、Hash（表）、树

队列(queue)：先进先出（FIFO)

例：
取号

<button id=takeNumber>取号</button>
<div id="output"></div>
<div id="screenDiv"></div>

var queue = []

function 取号 (name){
    let number = Math.round(Math.random() * 10000)
    queue.push(number)
    //output.textContent = 你取的号码是${number},
    //你前面有 ${queue.length -1}个人
    return number
}
function 取号(){
    //if(queue.length === 0){
    return
    }
    let theNumber = queue.shift()
    screenDiv.textContent = '请 ${theNumber} 到服务台'
    retun theNumber
}

//takeNumber.onclick = function(){
    取号()
}
//setInterval(function(){
    叫号()
},3000)

栈(stack):先进后出

<button id=button1>放书</button>
<button id=button2>取书</button>
<div id="output"></div>
<div id="screenDiv"></div>

var 箱子 = []

function 放书(name){
    箱子.push(name)
    output.textContent = name + '已放入箱子'
    return
}

function 取书(){
    if( 箱子.length === 0)
    output.textContent = '没书'
    return
}
var theBook = 箱子.pop()
    output.textContent = theBook + '已取出'
    return theBook
}

button1.onclick = function(){
    放书(Math.random())
}
button2.onclick = function(){
    取书()
}

Hash 哈希（表）

给我一个东西我给你另外一个东西

(1)用Hash找出字母出现的次数(已知参数的情况下)

var string = "I am Frank,I am 18 years old"

var hash = {}

for(var i = 0;i<string.length;i++){
    var letter = string[i]
    if(letter in hash){
        hash[letter] += 1
    }else{
        hash[letter] = 1
    }
}

console.log(hash)

用Hash找出字母出现的次数(不知参数的情况下)

function sort(string){
var str={};
for(var i=0;i<string.length;i++){
    if(string[i] in str){
    str[string[i]]+=1;
    }else{
    str[string[i]]=1;
    }
}
return str;
}
console.log(sort("hello"));

（2）排序(桶排序)已知参数

var array = [2,11,3,12,4,5,12]

var hash = []//每个数字出现几次
//写hash
for(var i = 0; i<array.length; i++){
    var number = array[i]
    if(number in hash){
        hash[number]+= 1
    }else{
    hash[number] = 1
    }
}

//读hash

var result = []
for(var i=0;i<hash.length; i++){
    if(hash[i] !== undefined){
        for(var iCount = 0; iCount < hash[i]; iCount ++){
            result.push(i)
        }
    }
}
console.log(result)

排序(桶排序)不知参数

function bucketsort(array){
    var buckets=[];
    var result = [];
    for(var i=0;i<array.length;i++){
        if([array[i]] in buckets){
            buckets[array[i]]+=1;
        }else{
            buckets[array[i]]=1;
        }
    }
    for(var a=0;a<buckets.length; a++){
        if(buckets[a] !== undefined){
            for(var Count = 0; Count < buckets[a]; Count ++){
                result.push(a);
            }
        }
    }
        return result;
}
console.log(bucketsort([21,15,19,35,62,0,1]));

树:

添加生物

var root = {
    name:'生物',
    children:[]
}

function addChild(parent,child){
    parent.children.push(child)
}
addChild(root,{
    name:'动物',
    children:[]
})

addChild(root,{
    name:'植物',
    children:[]
})

addChild(root.children[0],{
    name:'哺乳动物',
    children:[]
})
addChild(root.children[0],{
    name:'爬行动物',
    children:[]
})
addChild(root.children[0],{
    name:'两栖动物',
    children:[]
})
addChild(root.children[1],{
    name:'花草',
    children:[]
})
addChild(root.children[1],{
    name:'树木',
    children:[]
})

console.log(root)

遍历

function travelTree(node){
    console.log(node.name)
    for(var i= 0; i<node.children.length; i++){
        travelTree(node.children[i])
    }
}
travelTree(root)