数据结构笔记

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

举例:

队列、栈、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)
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 1 数据2 算法3 线性表4 栈5 队列6 串朴素模式匹配算法 -子串的定位操作:从主串中找到子串KMP模式匹配算...
    oldSix_Zhu阅读 1,544评论 0 4
  • 1 数据结构基本概念 1.1 数据结构分类 1. 逻辑结构 集合结构 数据元素间的关系是“属于同一个集合”。集合是...
    JaiUnChat阅读 1,493评论 0 1
  • 1、每个程序所花费的运行次数称为该程序的“时间复杂度”。判断该程序执行效率是否良好。 2、 3、内存的位置: 以行...
    EdwardSelf阅读 804评论 0 1
  • 前面说过,数据结构的类型大方向上来说分为线性结构和非线性结构,下面要说的线性表就是线性结构的一种。(复习一下,前面...
    泡泡不爱吃芹菜阅读 889评论 0 2
  • 教练说: 我的工作是幼师, 我要把你们这些成年人身上的种种盔甲一一卸下,让你们回复到童年时期的纯真和灿烂,单纯,没...
    W南茜阅读 509评论 0 0