前言

  • 数组
  • 队列
  • 链表
  • 集合
  • 字典
  • 散列表

1. 数组

创建和初始化数组

由于数组太常见了,一些基本的使用就不说明了

求斐波拉契数列前二十个数字

var fibonacci = []; //{1}
fibonacci[1] = 1; //{2}
fibonacci[2] = 1; //{3}
for (var i = 3; i < 20; i++) {
  fibonacci[i] = fibonacci[i - 1] + fibonacci[i - 2]; ////{4}
}
for (var i = 1; i < fibonacci.length; i++) { //{5}
  console.log(fibonacci[i]); //{6}
}

添加和删除元素

var numbers = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
// 添加元素
// 尾部添加
numbers[numbers.length] = 10;
numbers.push(11);
numbers.push(12, 13);
// 首部添加
numbers.unshift(-2);
numbers.unshift(-4, -3);
//对应的 你懂得
numbers.pop();
numbers.shift();

// 在数组的任意位置上添加和删除元素
// 使用splice方法,简单地通过指定位置/索引,就可以删除相应位置和数量的元素
numbers.splice(5, 3);
// 把数字2、3、4插入数组里
numbers.splice(5, 0, 2, 3, 4);
// splice方法接收的第一个参数,表示想要删除或插入的元素的索引值。第二个参数是删除 元素的个数(这个例子里,我们的目的不是删除元素,所以传入0)。第三个参数往后,就是要添 加到数组里的值(元素2、3、4)。输出会发现值又变成了从3到12。

二维数组和多维数组

JavaScript只支持一维数组,并不支持矩阵。但是,我们可以像上面的代码一样,用数组套数组,实现矩阵或任一多维数组

function printMatrix(myMatrix) {
  for (var i = 0; i < myMatrix.length; i++) {
    for (var j = 0; j < myMatrix[i].length; j++) {
      console.log(myMatrix[i][j]);
    }
  }
}

以此类推,也可以用这种方式来处理多维数组。假如我们要创建一个3×3的矩阵,每一格里包含矩阵的i(行)、j(列)及z(深度)之和:

var matrix3x3x3 = [];
for (var i = 0; i < 3; i++) {
  matrix3x3x3[i] = [];
  for (var j = 0; j < 3; j++) {
    matrix3x3x3[i][j] = [];
    for (var z = 0; z < 3; z++) {
      matrix3x3x3[i][j][z] = i + j + z;
    }
  }
}

JavaScript数组方法参考

方法 解释
concat 连接2个或更多数组,并返回结果
every 对数组中的每一项运行给定函数,如果该函数对每一项都返回true,则返回true
filter 对数组中的每一项运行给定函数,返回该函数会返回true的项组成的数组
forEach 对数组中的每一项运行给定函数。这个方法没有返回值
join 将所有的数组元素连接成一个字符串
indexOf 返回第一个与给定参数相等的数组元素的索引,没有找到则返回-1
lastIndexOf 返回在数组中搜索到的与给定参数相等的元素的索引里最大的值
map 对数组中的每一项运行给定函数,返回每次函数调用的结果组成的数组
reverse 颠倒数组中元素的顺序,原先第一个元素现在变成最后一个,同样原先的最后一个元素变成了现在 的第一个
slice 传入索引值,将数组里对应索引范围内的元素作为新数组返回
some 对数组的每一项运行指定函数,如果有真则为真
sort 按照字母顺序对数组进行排序,支持传入指定排序函数作为参数
toString 将数组作为字符串返回
valueOf 和toString类似,将数组作为字符串返回

迭代器函数

JavaScript内置了许多数组可用的迭代方法。对于本节的例子,我们需要数组和函数。假如有 一个数组,它值是从1到15,如果数组里的元素可以被2整除(偶数),函数就返回true,否则返回false

var isEven = function(x) {
  return (x % 2 === 0 ? true : false);
}
var numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15];

numbers.every(isEven); //数组numbers的第一个元素是1,它不是2的倍数(1是奇数),因此isEven 函 数返回false,然后every执行结束。
numbers.some(isEven); //numbers数组中第一个偶数是2(第二个元素)。第一个被迭代的元素是1,isEven会返回false。第二个被迭代的元素是2,isEven返回true——迭代结束。

// 如果要迭代整个数组,可以用forEach方法。它和使用for循环的结果相同:
numbers.forEach(function(x) {
  console.log((x % 2 == 0));
});
var myMap = numbers.map(isEven); //[false, true, false, true, false, true, false, true, false, true, false, true, false, true, false]

var evenNumbers = numbers.filter(isEven); //[2, 4, 6, 8, 10, 12, 14]

numbers.reduce(function(previous, current, index) {
  return previous + current;
}); //120

搜索和排序

首先,我们想反序输出数组numbers(它本来的排序是1, 2, 3, 4,…15)。要实现这样的功能, 可以用reverse方法,然后数组内元素就会反序。

numbers.reverse();

现在,输出numbers的话就会看到[15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]。然后,我们用sort方法:

numbers.sort(function(a, b){
  return a-b;
});

对于一些自定义排序可以这么玩

var friends = [{
    name: 'John',
    age: 30
  },
  {
    name: 'Ana',
    age: 20
  },
  {
    name: 'Chris',
    age: 25
  }
];

function comparePerson(a, b) {
  if (a.age < b.age) {
    return -1
  }
  if (a.age > b.age) {
    return 1
  }
  return 0;
}
console.log(friends.sort(comparePerson));

2. 栈

栈是一种遵从先进后出(LIFO)原则的有序集合。新添加的或待删除的元素都保存在栈的末尾,称作栈顶,另一端就叫栈底。在栈里,新元素都靠近栈顶,旧元素都接近栈底。

而栈主要是在编程语言的编译器里用来保存变量和方法调用等。

创建栈

function Stack() {
  this.dataStore = []; //保存栈内元素
  this.top = 0; //标记可以插入新元素的位置
  this.push = push; //入栈操作
  this.pop = pop; //出栈操作
  this.peek = peek; //返回栈顶元素
  this.clear = clear; //清空栈
  this.length = length; //栈的长度
}
//向栈中压入元素 同时让指针top+1 一定注意++
function push(element) {
  this.dataStore[this.top++] = element;
}
//出栈操作 同时将top-1
function pop() {
  return this.dataStore[--this.top];
}
//返回栈顶元素,变量top值减1 返回不删除
function peek() {
  return this.dataStore[this.top - 1];
}
//返回栈内元素个数
function length() {
  return this.top;
}
//清空一个栈
function clear() {
  this.top = 0;
}

回文算法

//回文算法

function isPalindrome(word){  
  var s = new Stack();
  for(var i=0;i<word.length;i++){
    s.push(word[i]);
  }
  var rword = "";
  while(s.length()>0){
    rword+=s.pop();
  }
  if(rword == word){
    return true;
  }else{
    return false
  }
}
var word = "12321";  
console.log(isPalindrome(word)); 

3. 队列

队列是遵循先入先出(FIFO)原则的有序的项。队列在尾部添加新元素,并在顶部移除元素。最新添加的元素必须排列在队列的尾部

function Queue(){  
  this.dataStore = [];
  this.enqueue = enqueue;//像队尾增加一个元素
  this.dequeue = dequeue;//删除队列元素
  this.front = front;//读取队首的元素
  this.back = back;//读取队尾的元素
  this.toString = toString;//显示队列中的所有元素
  this.empty = empty;//判断队列是否为空
}
function enqueue(element){  
  this.dataStore.push(element);
}
function dequeue(){  
  return this.dataStore.shift();
}
function front(){  
  return this.dataStore[0];
}
function back(){  
  return this.dataStore[this.dataStore.length-1];
}
function empty(){  
  if(this.dataStore.length == 0)return true;
  else return false;
}
function toString(){  
  var reStr = "";
  for (var i = 0; i < this.dataStore.length; i++) {
    reStr += this.dataStore[i] + "\n";
  }
  return reStr;
}

算法:实现方块舞的舞伴分配问题

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

function Patient(name, code) {
  this.name = name;
  this.code = code;
}

function dequeue() {
  var priarity = 0;
  for (var i = 1; i < this.dataStore.length; ++i) {
    if (this.dataStore[i].code > this.dataStore[priarity].code) {
      priarity = i;
    }
  }
  return this.dataStore.splice(priarity, 1);
}

function toString() {
  var retStr = "";
  for (var i = 0; i < this.dataStore.length; ++i) {
    retStr += this.dataStore[i].name + " code" + this.dataStore[i].code + "\n";
  }
  return retStr;
}

var pa = new Patient("小王", 1);
var pa1 = new Patient("小张", 4);
var pa2 = new Patient("小明", 9);
var pa3 = new Patient("小红", 3);

var quePatient = new Queue();
quePatient.enqueue(pa);
quePatient.enqueue(pa1);
quePatient.enqueue(pa2);
quePatient.enqueue(pa3);

console.log("第一个人" + quePatient.dequeue());
console.log(quePatient.toString());

3. 链表

链表是一种动态的数据结构,这就意味着我们可以从中任意添加和移除元素,他也可以按需扩容。

链表存储有序的元素集合,但不同于数组,链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(也称指针或链接)组成。

相对于传统的数组,链表的一个好处在于,添加或移除元素的时候不需要移动其他元素。然而,链表需要使用指针,因此实现链表时需要额外注意。数组的另一个细节是可以直接访问任何位置的任何元素,而要想访问链表中间的一个元素,需要从起点(表头)开始迭代列表直到找到所需的元素。

单向链表

function Node(element){  
  this.element = element;
  this.next = null;
}
function LList(){  
  this.head = new Node("head");
  this.find = find;
  this.insert = insert;
  this.display = display;
  this.findPrevious = findPrevious;
  this.remove = remove;
}
function find(item){  
  var currNode = this.head;
  while(currNode.element != item){
    currNode = currNode.next;
  }
  return currNode;
}
function insert(newElement, item){  
  var newNode = new Node(newElement);
  var currNode = this.find(item);
  newNode.next = currNode.next;
  currNode.next = newNode;
}
function display(){  
  var currNode = this.head;
  while(currNode.next != null){
    console.log(currNode.next.element);
    currNode=currNode.next;
  }
}
function findPrevious(item){  
  var currNode = this.head;
  while ((currNode.next!=null)&&(currNode.next.element!=item)) {
    currNode = currNode.next;
  }
  return currNode;
}
function remove(item){  
  var preNode = this.findPrevious(item);
  var currNode = this.find(item);
  if(preNode.next!=null){
    preNode.next = currNode.next;
    currNode.next = null;
  }
}
var cities = new LList();  
cities.insert('first','head');  
cities.insert('second','first');  
cities.insert('third','second');  
cities.display();  
console.log(cities.find('third'));  
console.log("=====================");  
// cities.remove('second');
// cities.display();

双向链表

function Node(element,next,pre){  
  this.element = element;
  this.next = null;
  this.pre = null;
}
function LList(){  
  this.head = new Node('head');
  this.find = find;
  this.insert = insert;
  this.display = display;
  this.remove = remove;
  this.displReverse = displReverse;
  this.findLast = findLast;
}
function find(item){  
  var currNode = this.head;
  while (currNode.element != item) {
    currNode = currNode.next;
  }
  return currNode;
}
function insert(newElement, item){  
  var newNode = new Node(newElement);
  var currNode = this.find(item);
  newNode.next = currNode.next;
  newNode.pre = currNode;
  currNode.next = newNode;
  if(newNode.next == null){
    newNode.next.pre = newNode;
  }
}
function display(){  
  var currNode = this.head;
  while(currNode.next != null){
    console.log(currNode.next.element);
    currNode=currNode.next;
  }
}
function remove(item){  
  var currNode = this.find(item);
  if(currNode.next != null){
    currNode.pre.next = currNode.next;
    currNode.next.pre = currNode.pre;
    currNode.next = null;
    currNode.pre = null;
  }else{
    currNode.pre.next = null;
    currNode.pre = null;
  }
}
function findLast(){  
  var currNode = this.head;
  while (!(currNode.next == null)) {
    currNode = currNode.next;
  }
  return currNode;
}
function displReverse(){  
  var currNode = this.findLast();
  while (!(currNode.pre==null)) {
    console.log(currNode.element);
    currNode = currNode.pre;
  }
}

try{  
  var cities = new LList();
  cities.insert('first','head');
  cities.insert('second','first');
  cities.insert('third','second');
  cities.remove('second');
  cities.display();
  cities.displReverse();
}catch(err){
  console.log(err);
}

4. 集合

集合是由一组无序且唯一(即不能重复)的项组成的。这个数据结构使用了与有限集合相同 的数学概念,但应用在计算机科学的数据结构中。

  • 结合是一种包含不同元素数据结构
  • 在很多编程语言中并不把集合当成一种数据类型,当你想要创建一个数据结构,用来保存一段独一无二的文字的时候集合就非常有用
  • 集合的成员是无序的
  • 集合中不允许相同成员存在
function Set(){  
  this.dataStore = [];
  this.add = add;
  this.remove = remove;
  this.show = show;
  this.union = union;//并集
  this.intersect = intersect;//交集
  this.difference = difference;//补集
  this.contains = contains;
  this.size = size;
  this.subset = subset;
}
function add(data){  
  if(this.dataStore.indexOf(data) < 0){
    this.dataStore.push(data);
  }else{
    return false;
  }
}
function remove(data){  
  var pos = this.dataStore.indexOf(data);
  if(pos > -1){
    this.dataStore.splice(pos, 1);
  }else{
    return false;
  }
}
function show(){  
  return this.dataStore;
}
function union(set){//全集  
  var tempSet = new Set();
  for(var i=0;i<this.dataStore.length;i++){
    tempSet.add(this.dataStore[i]);
  }
  for(var i=0;i<set.dataStore.length;i++){
    if(!tempSet.contains(set.dataStore[i])){
      tempSet.add(set.dataStore[i]);
    }
  }
  return tempSet
}
function contains(data){  
  if(this.dataStore.indexOf(data)>-1) return true;
  else return false;
}
function intersect(set){//交集  
  var tempSet = new Set();
  for(var i=0;i<this.dataStore.length;i++){
    if(set.contains(this.dataStore[i])){
      tempSet.add(this.dataStore[i]);
    }
  }
  return tempSet;
}
function difference(set){//补集  
  var tempSet = new Set();
  for(var i=0;i<this.dataStore.length;i++){
    if(!set.contains(this.dataStore[i])){
      tempSet.add(this.dataStore[i]);
    }
  }
  return tempSet;
}
function size(){  
  return this.dataStore.length;
}
function subset(set){  
  if(set.size()>this.size()){
    return false;
  }else{
    for(var i=0;i<set.dataStore.length;i++){
      if(!this.contains(set.dataStore[i])){
        return false;
      }
    }
    return true;
  }
}

var names = new Set();  
names.add("小红");  
names.add("小丽");  
names.add("小张");  
names.add("Tom");  
names.add("Jack");  
//console.log(names.show());
var cis = new Set();  
cis.add('小张');  
cis.add('Jack');  
cis.add('Tom');  
var it = new Set();  
it = names.union(cis);  
console.log("并集+++++++"+it.show());  
it = names.intersect(cis);  
console.log("交集+++++++"+it.show());  
it = names.difference(cis);  
console.log("补集+++++++"+it.show());  
console.log(names.subset(cis)); 

5. 字典

  • 字典以一种键-值对形式存储
  • JavaScript的Object类就是以字典的形式设计的。我们要实现一个Dictionary类,这样会比Object方便,比如显示字典中的所有元素,对属性进行排序等
function Dictionary(){  
  this.dataStore = new Array();
  this.add = add;
  this.find = find;
  this.count = count;
  this.clear = clear;
  this.remove = remove;
  this.showAll = showAll;
}
function add(key, value){  
  this.dataStore[key] = value;
}
function find(key){  
  return this.dataStore[key];
}
function remove(key){  
  delete this.dataStore[key];
}
function showAll(){  
  var datakeys = Object.keys(this.dataStore).sort();
  for(var keys in datakeys){
    console.log(datakeys[keys]+"-->"+this.dataStore[datakeys[keys]]);
  }
}
function count(){  
  return Object.keys(this.dataStore).length;
}
function clear(){  
  var datakeys = Object.keys(this.dataStore);
  for(var keys in datakeys){
    delete this.dataStore[datakeys[keys]];
  }
}
var pbook = new Dictionary();  
pbook.add('e','1');  
pbook.add('b','2');  
pbook.add('f','3');  
pbook.add('d','4');  
//console.log(pbook.find('c'));
pbook.showAll(); 

6. 散列

散列算法的作用是尽可能快地在数据结构中找到一个值。在之前的章节中,你已经知道如果 要在数据结构中获得一个值(使用get方法),需要遍历整个数据结构来找到它。如果使用散列函数,就知道值的具体位置,因此能够快速检索到该值。散列函数的作用是给定一个键值,然后返回值在表中的地址。

  • 散列后的数据可以快速插入取用
  • 在散列表上插入、删除和取用数据非常快,但是查找数据却效率低下,比如查找一组数据中的最大值和最小值
  • JavaScript散列表基于数组设计,理想情况散列函数会将每一个键值映射为唯一的数组索引,数组长度有限制,更现实的策略是将键均匀分布

散列关键概念

  • 数组长度是预先设定的,可以随时增加,所有元素根据和该元素对应的键,保存数组特定位置
  • 即使使用高效的散列函数,仍然存在两个键值相同的情况,这种现象成为碰撞
  • 对数组的长度应该是一个质数,所有的策略都基于碰撞
  • 开链法:两个键相同保存位置一样。开辟第二数组,也称第二个数组为链
  • 线性探测法属于开放寻址散列,查找散列位置如果当前位置没有继续寻找下一个位置。存储数据较大较适合。数组大小 >= 1.5 数据(开链法),数组大小 >=2 数据(线性探测法
// 线性探测法

function HashTable(){  
  this.table = new Array(137);
  this.simpleHash = simpleHash;
  this.put = put;
  this.get = get;
  this.showDistro = showDistro;
  this.betterHash = betterHash;
  this.buildChians = buildChians;
}
function buildChians(){  
  for(var i=0;i<this.table.length;i++){
    this.table[i] = new Array();
  }
}
//除留余数法
function simpleHash(data){  
  var total = 0;
  for(var i=0;i<data.length;i++){
    total+=data.charCodeAt(i);
  }
  return total%this.table.length;
}
function betterHash(data){  
  var H = 31;
  var total = 0;
  for(var i=0;i<data.length;i++){
    total += H * total + data.charCodeAt(i);
  }
  if(total<0){
    total += this.table.length-1;
  }
  return total%this.table.length;
}
function put(data){  
  var pos = this.simpleHash(data);
  if(this.table[pos] == undefined){
    this.table[pos] = data;
  }else{
    while(this.table[pos]!=undefined){
      pos++;
    }
    this.table[pos] = data;
  }
}
function get(key){  
  var hash = this.simpleHash(key);
  console.info(hash);
  for(var i=0;i<this.table.length;i++){
    if(this.table[i] == key){
      return i;
    }
  }
  return undefined;
}
function showDistro(){  
  var n = 0;
  for(var i=0;i<this.table.length;i++){
    if(this.table[i]!=undefined){
      console.log("键值是-》"+i+"值是【"+this.table[i]+"】");
    }
  }
}
function remove(data){  
  this.table[this.simpleHash[data]] = undefined;
}
var hTable = new HashTable();  
hTable.put("china");  
hTable.put("japan");  
hTable.put("america");  
hTable.put("nicha");  
console.log(hTable.get('nicha'));  
hTable.showDistro();  

8. 树

非顺序数据结构我们之前学习的有散列表,现在,我们接着学习另一个非顺序数据结构,树。树是一种分层数据的抽象模型。现实生活中最常见的树的例子是家谱,或是公司的组织架构图

位于树顶部的节点叫做根节点,它没有父节点。节点分为内部节点和外部节点,至少有一个子节点的节点成为内部节点,一个子节点也没有的成为外部节点也叫做叶节点。

一个节点可以有祖先和后代,一个节点(除了根节点)的祖先包括父节点、祖父节点、曾祖 父节点等。一个节点的后代包括子节点、孙子节点、曾孙节点等。

节点的一个属性是深度,节点的深度取决于它的祖先节点的数量。树的高度取决于所有节点深度的最大值。

二叉树和二叉搜索树

二叉树中的节点最多只能有两个子节点:一个是左侧子节点,另一个是右侧子节点。这些定 义有助于我们写出更高效的向/从树中插入、查找和删除节点的算法。二叉树在计算机科学中的 应用非常广泛。

二叉搜索树(BST)是二叉树的一种,但是它只允许你在左侧节点存储(比父节点)小的值, 在右侧节点存储(比父节点)大(或者等于)的值。

而我们今天主要研究的就是二叉搜索树

function Node(data, left, right){  
  this.data = data;
  this.left = left;
  this.right = right;
  this.show = show;
}
function show(){  
  return this.data;
}
function BST(){  
  this.root = null;
  this.insert = insert;
  this.inOrder = inOrder;
  this.getMin = getMin;
  this.getMax = getMax;
  this.find = find;
  this.remove = remove;
}
function insert(data){  
  var n = new Node(data, null, null);
  if(this.root == null){
    this.root = n;
  }else{
    var current = this.root;
    var parent;
    while(true){
      parent = current;
      if(data<current.data){
        current = current.left;
        if(current == null){
          parent.left = n;
          break;
        }

      }else{
        current = current.right;
        if(current == null){
          parent.right = n;
          break;
        }
      }
    }
  }
}
function inOrder(node){  
  if(!(node == null)){
    inOrder(node.left);
    console.log(node.data);
    inOrder(node.right);
  }
}
function getMin(root){  
  var current = this.root || root;
  while(!(current.left == null)){
    current = current.left;
  }
  return current.data;
}
function getMax(){  
  var current = this.root || root;
  while(!(current.right == null)){
    current = current.right;
  }
  return current.data;
}
function find(data){  
  var current = this.root;
  while(current != null){
    if(current.data == data){
      return current;
    }else if(data < current.data){
      current = current.left;
    }else{
      current = current.right;
    }
  }
  return null;
}
function remove(data){  
  removeNode(this.root, data);
}
function removeNode(node, data){  
  if(node == null){
    return null;
  }
  if(data == node.data){
    if(node.left == null && node.right == null){
      return null
    }
    if(node.left == null){
      return node.right;
    }
    if(node.right == null){
      return node.left;
    }
    var tempNode = getmin(node.right);
    node.data = tempNode.data;
    node.right = removeNode(node.right, tempNode.data);
    return node;
  }else if(data<node.data){
    node.left = removeNode(node.left, data);
    return node;
  }else{
    node.right = removeNode(node.right, data);
    return node;
  }
}

var nums = new BST();  
nums.insert(23);  
nums.insert(45);  
nums.insert(26);  
nums.insert(47);  
nums.insert(37);  
nums.insert(3);  
nums.insert(101);  
//console.log(nums.getMin())
nums.remove(3);  
nums.inOrder(nums.root);