javascript数据结构（还有剩余部分更新ing）

参考书籍《js数据结构与算法》

1.数组

1.1数组的声明和判断

//js中数组和其他语言不同，数据类型可以不一样
//以下是两种生明数组的方式，一般来说字面量[]的效率高于Array构造函数
var arr1 = new Array(1,2,3)
var arr2 = ["name",123,{username:"xml",password:123456}]//判断是否为数组 instanceof 数组圆形的方法 isArray() 返回布尔值
console.log(arr1 instanceof Array); //true
console.log(Array.isArray(arr2));   //true

1.2由字符串生成数组

//split方法切割，传递参数作为分隔符，将字符串分割成数组
var sentence = "my name is xml";
var words = sentence.split(' ');    //以空格切分字符串
console.log(words);  
//["my","name","is","xml"]//数组的方法 join(param) 将数组里的元素根据参数整理成字符串
//param默认为逗号
console.log(words.join(','));
// my,name,is,xml

1.3对数组的整体操作

//赋值，直接用等号赋值是浅拷贝，相当于为数组增加了一个引用，当一个数组改变时，另一个数组也会跟着改变
arr1 = arr2;
arr2[2] = 400;
console.log(arr1[2]);  //400//深拷贝，直接复制值，而不是地址，一个对象的改变不会影响另外一个的值
//一个简单的深拷贝函数(对象)
function deepCopy(newObj,oldObj){//使用对象的遍历方法for(let k in oldObj){//先判断数组，因为数组也属于Object-->数组let item = oldObj[k];if(item instanceof Array){let newArr[k] = [];deepCopy(newObj[k],item);}else if(oldObj[i] instanceof Object){let newObj[k] = {};deepCopy(newObj[k],item);}newObj[k] = item;}
}//indexof()函数是用来查找元素是否存在在目标数组中，存在返回位置序号（0开始），不存在则返回-1
let names = ["delay","maria","lisa","judy","ben"];
console.log(names.indexof("ben"));  //4//splice() & concat()
//splice()从数组中间删除元素,在原数组的基础上修改，返回删除元素之后的数组
//splice()在原数组上删除元素时，第一个参数为起始索引，第二个参数为截取长度，添加数组元素时，第二参数置为0，第三个参数为插入的数据
//concat()参数是要拼接的数组
console.log(names.splice(2,3)); //["delay","maria"]
let cat = ["123","456","nan"];
console.log(names.concat(cat));  //["delay","maria","123","456","nan"]

//数组添加元素
arr.push(param)  //将param添加到数组末尾，在原数组上修改，返回新数组长度
arr.unshift(param)   //将param添加到数组的开头，在原数组上修改，返回新数组的长度arr.pop()   //无参数，删除并返回数组的最后一个元素，在原数组上修改
arr.shift()  //无阐述，删除并返回数组的第一个元素，在原数组上修改arr.reverse();  //翻转数组
arr.sort();     //默认按照字典顺序排列，可以一个函数作为参数，修改排序规则

//迭代器方法
//传入一个函数作为参数，对数组的每一个元素都进行相应的函数操作

//（1）不生成新数组的迭代器方法 forEach() every() some() reduce()
let nums = [1,2,3,4];
let num = [];//arr.forEach() 接受一个函数作为参数，对item执行操作，没有返回值
nums.forEach((item,index,arr)=>{item = item*item;num[index] = item;
});
console.log(num);  //[1,4,9,16]//arr.every() 接受一个返回值为布尔值的函数作为参数，只有当数组中的所有值满足函数时最后才返回true
let boo = nums.every((item,index,arr)=>{return item%4 == 0;  //false//return item%1 == 0;  true
})
console.log(boo);  //false//arr.some()接受一个返回值为布尔值的函数作为参数，只要数组中有一个满足条件就返回true
console.log(nums.some((item,index,arr)=>{return item%2 == 0;
}))   //true//arr.reduce()接受一个函数作为参数，结果返回一个值，从第一个累加值开始，不断对累加值和数组中的后续元素调用该函数，返回得到的累加值
console.log(nums.reduce((total,item)=>{//total是累加值return total + item;
}))

//(2)生成新数组的迭代器方法 map() filter()
//arr.map()  接受一个函数作为参数，对数组的每一个元素都执行函数，返回一个新的数组
//例1
let grades = [88,90,56,45,23];
let newGrade = grades.map((item,index,arr)=>{return item + 10;
})
console.log(newGrade);  //[98,100,66,55,33]
//例2
console.log(newGrades);  //[ 98, 100, 66, 55, 33 ]
var words = ["wfh","qwd","wqdw","adad"];
var first = words.map((item,index,arr)=>{return item[0];
});
console.log(first);      //["w","q","w","a"]//arr.filter()  接受一个返回值为布尔值的函数作为参数，返回满足条件的元素组成的新数组
//例1
var mix = [12,"wfe",{name:"xml",age:18},[1,2,3]];
var newMix = mix.filter((item,index,arr)=>{return item instanceof Object;
});
console.log(newMix);  //[{name:"xml",age:18},[1,2,3]]
//例2  用filter过滤字符串组成数组
var a = ["recieve","deceive","precieve","deceit","concieve"];
var newa = a.filter((item)=>{if(item.indexOf("cie") > -1){return true;}else{return false;}
});
console.log(newa);  ["recieve","precieve","concieve"]

2.列表

2.1概念及理解

列表是一组有序的数字居，js中列表可以使=是任意数据类型，基本数据类型为数组；可以随意访问列表中的任一元素

//构造函数
function List(){this.listSize = 0;   //属性，元素个数this.pos = 0;        //属性，列表的当前位置this.dataStore = new Array();   //基础数据类型，初始化数组来保存列表元素this.append = append;  //给列表的下一位置添加元素this.length = length;  //返回列表的长度this.clear = clear;    //清空列表方法this.find = find;      //查找元素this.remove = remove;  //删除列表中指定的元素this.display = display;//显示列表元素this.insert = insert;  //在指定的元素之后插入指定元素
}//append()给列表的下一位置添加元素
function append(el){this.dataStore[this.listSize++] = el;//数组序号从0开始，所以应当先将dataStore[listSize]=el,再将listSize+1
};//find() 查找元素是否存在列表中,存在的话返回位置序号，否则返回-1
function find(el){for(let i = 0;i < this.listSize; i++){if(this.dataStore[i] === el){return i;}}return -1;
}//remove()  删除某指定元素,返回布尔值，表示删除是否成功
function remove(el){//先找到元素是否存在，再用splice删除元素if(this.find(el)>-1){this.dataStore.splice(this.find(el),1);this.listSize--;return true;}else{console.log("该列表不包含此元素！");return false;}
}//length  返回列表的长度
function length(){return this.listSize;
}//insert()  在某一元素之后插入指定元素,返回布尔值，表示插入元素是否成功
function insert(el,after){//先判断after元素是否存在，存在则将后面的元素都向后移动一位let index = this.find(after);if(index > -1){//从后向前遍历for(let k = this.listSize; k >index; k--){this.dataStore[k] = this.dataStore[k-1];}this.dataStore[index+1] = el;this.listSize += 1;return true;}else{console.log("该元素不存在！");return false;}
}//clear()  清除列表
function clear(){delete this.dataStore;this.dataStore = [];this.listSize = 0;this.pos = 0;
}//display() 显示列表元素
function display(){console.log(this.dataStore);
}// //列表test
// var list = new List();
// list.append(12);
// list.append('xml');
// list.insert("java",12);
// list.remove('xml');
// list.display();

3.栈 stack

栈 后进先出（LIFO) 基础数据类型为[ ]

//构造函数
function Stack(){this.dataStore = [];   //存储数据this.top = 0;   //栈顶this.push = push;  //向栈顶添加数据this.pop = pop;    //返回栈顶元素，并栈顶元素从栈里删除this.peek = peek;  //返回栈顶元素this.clear = clear; //清空栈this.display = display;  //显示栈里面的元素
}//push() 向栈里压入一个元素
function push(el){//栈顶位置先赋值el,top值+1this.dataStore[this.top++] = el;
}//pop()  删除栈顶元素，并返回栈顶元素
function pop(){return this.dataStore[--this.top];
}//peek()   返回栈顶元素
function peek(){return this.dataStore[this.top-1];
}//display()  显示栈里的元素
function display(){console.log(this.dataStore);
}//clear()  清空栈
function clear(){delete this.dataStore;this.dataStore = [];this.top = 0;
}// //stack test
// var stack = new Stack();
// stack.push("xml");
// stack.push("123");
// stack.push("top");
// stack.display();

4.队列

先进先出 （FIFO）基础数据类型为数组

//构造函数
function Queue(){this.append = append;   //向队尾添加一个元素this.del = del;         //删除队首的元素this.front = front;     //读取队首元素this.end = end;         //读取队尾元素this.display = display; //显示队列this.isEmpty = isEmpty; //判断队列是否为空
}//append()  向队尾添加一个元素
function append(el){//使用数组的push方法向数组末尾添加元素return dataStore.push(el);
}//del() 删除队首元素
function del(){//先判断队列是否为空，再决定是否进行删除操作if(this.isEmpty()){console.log("此队列为空！")return false;}else{this.dataStore.shift();return true;}}
//end() 读取队尾元素
function end(){if(this.isEmpty()){console.log("该队列为空！")；return false;}else{return this.dataStore[this.dataStore.length-1];}
}
//front() 读取队首元素
function front(){if(this.isEmpty()){return false;}else{return this.dataStore[0];}
}
//display() 展示队列元素
function display(){this.dataSotre;
}
//isEmpty()判断队列是否为空，返回布尔值
function isEmpty(){if(this.dataStore.length == 0){return true;}else{return false;}
}

5.单向链表

由多个节点（node）组成 node只包含data和next

不可以按照索引随意的访问一个元素，必须经过遍历，但是插入方便了

//节点和链表都是对象，都需要构造
//节点构造函数，需要传入参数为data
function Node(el){this.data = el;this.next = null;      //null是指向空地址对象
}
//链表构造函数
function linkList(){this.head = new Node('head');    //链表的头指针this.length = 0;                 //表示链表长度的属性this.insert = insert;            //向链表中插入新的元素this.search = search;            //查找链表元素this.findPre = findPre;          //查找指定元素之前的元素this.del = del;                  //删除链表指定元素this.show = show;                //显示链表的所有元素
}
//insert()  向链表中插入元素,返回布尔值
function insert(el,before){//先判断before是否存在，存在则修改指向,并修改链表长度let beforeNode = new Node(before);if(this.search(beforeNode)){let node = new Node(el);node.next = beforeNode.next;beforeNode.next = node;this.length++;return true;}else{return false;}
}
//search() 查找链表元素,返回布尔值
function search(el){let current = this.head;while(current.data != el){current = current.next;}return current;
}
//findPre()  查找指定元素之前的元素
function findPre(el){//before节点的next.data应该等于ellet before = this.head;while((before.next.data != el) && (before.next != null)){before = before.next;}return before;}
//del()  删除指定列表元素
function del(el){//查找到之前的元素，然后修改指向let before = this.findPre(el);before.next = before.next.next;
}
//show()  显示链表所有节点的data
function show(){let current = this.head;while(current.next != null){console.log(current.next.data);current = current.next;}
}//链表test
var Linklist = new linkedList();
Linklist.insert("head","zhangsan");
Linklist.insert("zhangsan","lisi");
Linklist.insert("lisi","zhaoqian");
Linklist.insert("zhaoqian","sunli");
Linklist.show();
Linklist.del("lisi");
Linklist.show(); 

6.双向链表+循环链表

7.字典

//字典  键值对形式，一一对应,基础数据类型为[]
//需要注意的是，当键为字符串时，length属性就失效了
function Dictionary(){this.dataStore = new Array();this.add = add;        //添加元素this.find = find;      //查找元素this.remove = remove;   //删除键值对this.show = show;       //显示字典中所有的键值对
}//add(key,value)  添加键值对
function add(key,value){this.dataStore[key] = value;
}//find(key)  以key作为参数，返回相应的value
function find(key){return this.dataStore[key];
}//remove(key)  以key为参数，删除这个键值对  使用js里内置函数delete
function remove(key){delete this.dataStore[key];
}//show() 显示所有键值对 
function show(){for(var key in this.dataStore){console.log(key + "->" + this.dataStore[key]);}
}//Dictionary test
let Dic = new Dictionary();
Dic.add('name','xml');
Dic.add('age',21);
Dic.show();
Dic.remove('name');
Dic.show();
console.log(Dic.find('age'));

8.散列

9.集合

10.二叉树和二叉查找树

11.图和图算法

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！