Detailed explanation of arrays and hash tables of js data structures and algorithms

1. Data structure

1. What is a data structureA data structure is a relationship. Yes, it is one or more specific relationships between data elements. Collection of relationships. Traditionally, we divide data structures into logical structures and physical structures. Logical structure: refers to the relationship between data elements in the data object. It is also the issue that we need to pay most attention to and discuss in the future. Physical structure: refers to the storage form of the logical structure of data in the computer.

2.Commonly used data structures are:
Array, queue, heap, stack, linked list, tree , graph (graph) and hash table (hash)

Stack (stack): The operation is only performed on one end of the table; Queue (Queue): The operation is only performed on both ends of the table.
A queue is a linear list that only allows insertion operations at one end and deletion operations at the other end.
Contrary to the stack, the queue is a linear list of First In First Out (FIFO).

Same as the stack, the queue is also an important linear structure. Implementing a queue also requires a sequence list or linked list as the basis.

2. Data structure analysis

(1). Array

The concept of array: array is an Construct type data structure. An array is a collection of many data of the same type.

Array classification: one-dimensional array, two-dimensional array [row and row], multi-dimensional array ( Three-dimensional or above [three-dimensional array row and column layer])

1. Split the string into an array split and splice the array elements into a string join

var sentence = "I love China";
/**1.字符串.split(分隔符) 将字符串生成为数组*/
var words = sentence.split(" ");
var arr=[];
for (var i = 0; i < words.length; ++i) {
	arr.push(words[i])
}
console.log(arr)// ["I", "love", "China"]

//2.数组转字符串   
/*.join(分隔符) 数组各元素间放分隔符并连接成一个字符串
 * join("") 就是 直接将数组个元素拼接起来生字符串
 * .toString()连接成字符串后 默认中间会用,隔开
 */
var object1=arr.join(" ");
var object2=arr.toString();
console.log(object1)//I love China
console.log(object2)//I,love,China

2.indexOf-Find whether an element exists in the array and its subscript

var names = ["David","Cynthia","Raymond","Clayton","Jennifer"];
var fondName ='Clayton';
/**1.
 * 数组.indexOf(参数值) 参数值是否存在于数组,
 * 存,返第一个出现该元素的下标;不存,返-1;
 *
 * 数组.lastIndexOf(参数值)
 * 反序找第一个的下标(如果出现,否则返-1)
 *
 * */
var position = names.indexOf(fondName);
if (position >= 0) {
    console.log("找到" + fondName + "在" + position+'位置');//找到Clayton在3位置
}else {
   console.log(fondName + "不选中数组中");
}

3. Add and delete modified elements in the middle of the array splice

/**
 * 1.splice() 将现有数组进行截取,返回所截取生成出来的数组,且现有数组改变,是截取后的数组
 * 可用于为一个数组增加或移除或修改元素
 * 参数一:截取(删除)的起始索引(0是第一个元素)
 * 参数二:截取(删除)的元素的个数
 * 参数三:删除截取后要添加进数组的元素(可以是个数组)
 * */

/**2.
 * 数组中间插入元素(放在数组里插入)
 * */
var nums = [1,2,3,7,8,9];
var newElements = [4,5,6];
nums.splice(3,0,newElements);
console.log(nums); //[1, 2, 3, Array(3), 7, 8, 9]

/**3.
 * 要插入数组的元素不必组织成一个数组， 它可以是任意的元素序列
 * */
var nums = [1,2,3,7,8,9];
nums.splice(3,0,4,5,6);
console.log(nums);// 1,2,3,4,5,6,7,8,9

/**4.
 * 从数组中删除元素
 * */
var nums = [1,2,3,100,200,300,400,4,5];
nums.splice(3,4);
console.log(nums); // 1,2,3,4,5

4 .Iterator method that does not generate a new array

forEach operates on each element--every all satisfies--some has one that satisfies--reduce cumulative operation

/**
 * 1. 数组.forEach(func) 对数组每个元素执行某操作
 * 它接受一个函数作为参数，对数组中的每个元素使用该函数
 * */
function squareFunc(num) {
    console.log(num, num * num); //打印多个字符的时候自动中间会加空格
}
var nums = [1, 2, 3];
nums.forEach(squareFunc);// 1 1   2 4  3  9

/**
 * 2. 数组.every(func)， 检查数组中每个元素是否满足某条件
 * 它接受一个返回值为布尔类型的函数， 对数组中的每个元素使用该函数。
 * 如果对于所有的元素，该函数均返回 true， 则该方法返回 true
 *
 * 数组.some(func)是否存在一个元素满足
 * 也接受一个返回值为布尔类型的函数， 只要有一个元素使得该函数返回 true，
 * 该方法就返回 true
 * */
function isEven(num) {
    return num % 2 == 0;
}
var nums = [1, 3, 5, 8, 11];
var even = nums.some(isEven);
if (even==true) {
    console.log("all numbers are even");
} else {
    console.log("not all numbers are even");
}

/**
 * 3.
 * reduce() 数组中的各个元素累计进行操作
 * 它接受一个函数， 返回一个值。 该方法会从一个累加值开始， 不断对累加值和
 * 数组中的后续元素调用该函数， 直到数组中的最后一个元素， 最后返回得到的累加值。
 * */

//使用 reduce() 方法为数组中的元素求和：
function add(runningTotal, currentValue) {
    return runningTotal + currentValue;
}
var nums = [1,2,3,4];
var sum = nums.reduce(add); //接受函数
console.log(sum); // 显示10

//reduce() 方法也可以用来将数组中的元素连接成一个长的字符串
function concat(accumulatedString, item) {
    return accumulatedString + item;
}
var words = ["the ", "quick ","brown ", "fox "];
var sentence = words.reduce(concat);
console.log(sentence); // 显示 "the quick brown fox"


/**
 * 4.reduceRight() 方法，从右到左执行。
 * 下面的程序使用 reduceRight() 方法将数组中的元素进行翻转：
 * */
function concat(accumulatedString, item) {
    return accumulatedString + item;
}
var words = ["the ", "quick ","brown ", "fox "];
var sentence = words.reduceRight(concat);
console.log(sentence); // 显示 "fox brown quick the"

5. Iterator method to generate a new array

map is an array composed of the results of performing a certain operation on each element - an array composed of elements in the filter array that meet certain conditions

/**
 * 1. 数组.map(func)
 * map() 和 forEach() 有点儿像，
 * 对数组中的每个元素使用某个函数。 两者的区别是
 * map() 返回一个新的数组， 该数组的元素是对原有元素应用某个函数得到的结果
 * */
function curve(grade) {
    return grade += 5;
}
var grades = [77, 65, 81, 92, 83];
var newgrades = grades.map(curve);
console.log(newgrades); // [82, 70, 86, 97, 88]

/**
 * 2.下面是对一个字符串数组使用 map() 方法的例子：
 * 数组 acronym 保存了数组 words 中每个元素的第一个字母。
 * 然而， 如果想将数组显示为真正的缩略形式， 必须想办法除掉连接每个数组元素的逗号，
 * 如果直接调用 toString() 方法， 就会显示出这个逗号。
 * 使用 join() 方法， 为其传入一个空字符串作为参数， 则可以帮助我们解决这个问题
 * */
function first(word) {
    return word[0];
}
var words = ["for", "your", "information"];
var acronym = words.map(first);
console.log(acronym)//["f", "y", "i"]
console.log(acronym.join("")); // 显示 "fyi"

/**
 * 3.filter() 传入一个返回值为布尔类型的函数。
 * 和 every() 方法不同的是，
 * 当对数组中的所有元素应用该函数，该方法并不返回 true，
 * 而是返回一个新数组， 该数组包含应用该函数后结果为 true 的元素。
 * */
//下列程序筛选数组中的奇数和偶数元素
function isEven(num) {
    return num % 2 == 0;
}

function isOdd(num) {
    return num % 2 != 0;
}
var nums = [];
for (var i = 0; i < 20; ++i) {
    nums[i] = i + 1;
}
var evens = nums.filter(isEven);
console.log("Even numbers: ");
console.log(evens);//[2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
var odds = nums.filter(isOdd);
console.log("Odd numbers: ");
console.log(odds);//[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

//下面使用 filter() 筛选所有成绩及格的分数：
function passing(num) {
    return num >= 60;
}
var grades = [];
for (var i = 0; i < 10; ++i) {
    grades[i] = Math.floor(Math.random() * 101);
}
var passGrades = grades.filter(passing);
console.log("All grades:");
console.log(grades);// [74, 86, 34, 49, 5, 5, 21, 28, 27, 47]
console.log("Passing grades: ");
console.log(passGrades);//[74, 86]

//还可以使用 filter() 方法过滤字符串数组，下面这个例子过滤掉了那些不包含“ cie” 的单词：
function afterc(str) {
    if (str.indexOf("cie") > -1) {
        return true;
    }
    return false;
}
var words = ["recieve","deceive","percieve","deceit","concieve"];
var misspelled = words.filter(afterc);
console.log(misspelled); // 显示 ["recieve", "percieve", "concieve"]

6. Two-dimensional arrays and multi-dimensional arrays

//直接初始化
 var arr=[[11,12,13],[21,22,23],[31,32,33]];
 console.log(arr[0][0])//11
/**
 * 2.创建二维数组
 * 比较好的方式是遵照 JavaScript: TheGood Parts（ O’Reilly） 一书第 64 页的例子，
 * 通过扩展 JavaScript 数组对象， 为其增加了一个新方法，
 * 该方法根据传入的参数， 设定了数组的行数、 列数和初始值
 * */
Array.matrix = function(numrows, numcols, initial) {
    var arr = [];
    for (var i = 0; i < numrows; ++i) {
        var columns = [];
        for (var j = 0; j < numcols; ++j) {
            columns[j] = initial;
        }
        arr[i] = columns;
    }
    return arr;
}

//测试该生成二维数组方法的一些测试代码
var nums = Array.matrix(3,3,2);
console.log(nums); // [ [2, 2, 2],[2, 2, 2], [2, 2, 2]]
nums[1][2]=4;
console.log(nums); // [ [2, 2, 2],[2, 2, 4], [2, 2, 2]] /把2改成4

/**
 * 3.处理二维数组的元素
 * 两种最基本的方式： 按行x访问和按列y访问
 * */

/**
 * 按行x访问:
 * 外层循环对应行，内层循环对应列,每次对每一行的元素进行一些操作
 *
 * 以数组 grades 为例， 每一行对应一个学生的成绩记录。
 * 可以将该学生的所有成绩相加， 然后除以科目数得到该学生的平均成绩。
 * (89+77+78)/3=81.33
 * toFixed()四省五入 保留几个小数点
 * */
var grades = [[89, 77, 78],[76, 82, 81],[91, 94, 89]];
var total = 0;
var average = 0.0;
for (var x = 0; x < grades.length; x++) {
    for (var y = 0; y < grades[x].length; y++) {
        total += grades[x][y];
    }
    average = total / grades[x].length;
    console.log("Student " + parseInt(x+1) + " average: " +average.toFixed(2));
    total = 0;
    average = 0.0;
}

/**
 * 按列访问:
 * 外层循环对应列，内层循环...,每次对每一列的元素进行一些操作
 *
 * 下面的程序计算了一个学生各科的平均成绩,即:每一列的数据想加取平均值:
 * 如(89+76+91)/3=885.33
 * */
var grades2 = [[89, 77, 78],[76, 82, 81],[91, 94, 89]];
var total2 = 0;
var average2 = 0.0;
for (var y = 0; y < grades2.length; y++) {
    for (var x = 0; x < grades2[y].length; x++) {
        total2 += grades2[x][y];
    } 
    average2 = total2 / grades2[y].length;
    console.log("Test " + parseInt(y+1) + " average2: " +average2.toFixed(2));
    total2 = 0;
    average2 = 0.0;
}

/**
 * 4.参差不齐的数组
 * 参差不齐的数组是指数组中每行的元素个数彼此不同。 有一行可能包含三个元素， 另一行
 * 可能包含五个元素， 有些行甚至只包含一个元素。 很多编程语言在处理这种参差不齐的数
 * 组时表现都不是很好， 但是 JavaScript 却表现良好， 因为每一行的长度是可以通过计算得到的
 * */
//假设数组 grades 中， 每个学生成绩记录的个数是不一样的， 不用修改代码， 依然可以正确计算出正确的平均分：
var grades3 = [[89, 77],[76, 82, 81],[91, 94, 89, 99]];
var total3 = 0;
var average3 = 0.0;
for (var x = 0; x < grades3.length; x++) {
    for (var y = 0; y < grades3[x].length; y++) {
        total3 += grades3[x][y];
    }
    average3 = total3 / grades3[x].length;
    console.log("Student3 " + parseInt(x+1) + " average3: " + average3.toFixed(2));
    total3 = 0;
    average3 = 0.0;
}

/**
 * 5.对象数组
 * 对象组成的数组，数组的方法和属性对对象依然适用。
 * */

/**
 * 注意 这里通过一个函数生成了一个对象    
 * 生成对象的函数里传入参数,然后设置   this.属性 = ...  this.方法 = function...
 * 这样的函数即构造函数
 * */
function Point(x,y) {
    this.x = x;
    this.y = y;
}
function displayPts(arr) {
    for (var i = 0; i < arr.length; ++i) {
        console.log(arr[i].x + ", " + arr[i].y);
    }
}

/**
 * 注意 这里通过 var ... = new 构造函数(实际参数)
 * 生成了该对象的一个实例对象
 * */
var p1 = new Point(1,2);
var p2 = new Point(3,5);
var p3 = new Point(2,8);
var p4 = new Point(4,4);
//对象组成的数组
var points = [p1,p2,p3,p4];
for (var i = 0; i < points.length; ++i) {
    console.log("Point " + parseInt(i+1) + ": " + points[i].x + ", " + points[i].y);
}
var p5 = new Point(12,-3);
//使用 push() 方法将点 (12, -3) 添加进数组， 使用 shift() 方法将点 (1, 2) 从数组中移除。
points.push(p5);
console.log("After push: ");
displayPts(points);
points.shift();
console.log("After shift: ");
displayPts(points);

/**
 * 6.对象中的数组
 * 在对象中， 可以使用数组存储复杂的数据。
 * 实际算法应用与解决方案中,很多数据都被实现成一个对象，对象内部使用数组保存数据。
 *
 * 下例中， 创建了一个对象， 用于保存观测到的周最高气温。
 * 该对象有两个方法， 一个方法用来增加一条新的气温记录，
 * 另外一个方法用来计算存储在对象中的平均气温
 *
 * 很实用和常用的技巧!!!
 * */
//对象构造函数
function WeekTemps() {
    this.dataStore = []; //对象构造函数里 设置某些属性为一个数组存储比较复杂的数据
    this.add = add; //设置对象的方法
    this.average = average;
}

//定义对象方法的操作,里面使用this.属性名 代表对象的某属性
function add(temp) {
    this.dataStore.push(temp);  //对对象的数组型数据进行数组式操作
}
function average() {
	console.log(this.dataStore)//[52, 55, 61, 65, 55, 50, 52, 49]
    var total = 0;
    for (var i = 0; i < this.dataStore.length; ++i) {
        total += this.dataStore[i];
    }
    return total / this.dataStore.length;
}
var thisWeek = new WeekTemps();
thisWeek.add(52);
thisWeek.add(55);
thisWeek.add(61);
thisWeek.add(65);
thisWeek.add(55);
thisWeek.add(50);
thisWeek.add(52);
thisWeek.add(49);
console.log(thisWeek.average()); // 54.875

(2).Hash table

1. List concept

In daily life, people often use lists. For example, when we sometimes go shopping, in order to buy all the things when shopping, we can make a list of the things we want to buy before going. This is where we use a list. Or when we were in school when we were young, after each exam, the school would list the rankings and transcripts of the top ten students who scored in the exam, and so on. These are all examples of the list. We also use lists in our computers, so where are lists suitable for use? Where is it not suitable for use?

Suitable for use in : When there are not many elements in the list, you can use the list, because when searching or sorting the elements in the list, the efficiency is quite high. On the contrary: if When there are very many list elements, it is not suitable to use lists. If the order of storage is not important (if the order is important, you can consider a stack, etc.) and there is no need to search for the data, then the list is a perfect data structure. For some other applications, the list seems too simple

Summary:A list is an ordered set of data. The data items in each list are called elements. In JavaScript, elements in a list can be of any data type. There is no prior agreement on how many elements can be stored in a list. However, in actual use, the number of elements is limited by the program memory.

2. Attributes

##3.Use

/**
 * 1.实现列表类,定义构造函数
 * 注意这里定义的删除查找等方法都是传入一整个元素的值,列表由一系列元素组成,元素即最小的那个单元
 * */
function List() {
    this.listSize = 0; //listSize是属性  列表的元素个数
    this.pos = 0;// 列表的当前位置 是第几个
    this.dataStore = []; // 初始化一个空数组来保存列表元素,即底层数据结构是数组  
}
List.prototype = {
    // 给列表末尾添加元素  变量 listSize 加 1
    append: function(element) {
        var self = this;
        self.dataStore[this.listSize++] = element;
    },

    /*remove()从列表中删除元素
    * 需要在列表中找到该元素， 然后删除它， 并且调整底层的数组对象以填补删除该元素后留下的空白。
 	* js中可以使用 splice() 方法简化这一过程。
 	* 
 	*  remove() 方法使用 find() 方法返回的位置对数组 dataStore 进行截取。 数组改变后， 将变
	* 量 listSize 的值减 1， 以反映列表的最新长度。 如果元素删除成功， 该方法返回 true，
	* 否则返回 false。
    */
    remove: function(element) {
        var self = this;
        var curIndex = self.find(element);
        if(curIndex > -1) {
            self.dataStore.splice(curIndex,1);
            --self.listSize;
            return true;
        }
        return false;
    },

    /*find() 方法通过对数组对象 dataStore 进行迭代，查找给定的元素。 
     * 查找列表中的元素 返回索引
     * 如果找到，就返回该元素在列表中的位置，否则返回 -1，
     */
    find: function(element) {
        var self = this;
        for(var i = 0,dataLen = self.dataStore.length; i < dataLen; i++) {
            if(self.dataStore[i] == element) {
                return i;
            }
        }
        return -1;
    },
    
    // 返回列表中元素的个数
    length: function() {
        return this.listSize;
    },

    /*显示列表中的元素
     * 该方法返回的是一个数组， 而不是一个字符串， 但它的目的是为了显示列表的
 	* 当前状态， 因此返回一个数组就足够了。
     */
    toString: function(){
        return this.dataStore;
    },

    /*insert() 在指定元素后面插入一个元素
     *  insert() 方法用到了 find() 方法， find() 方法会寻找传入的 after 参数在列
	 * 表中的位置， 找到该位置后， 使用 splice() 方法将新元素插入该位置之后， 然后将变量
	 * listSize 加 1 并返回 true， 表明插入成功。
	 * 
     * @param element 当前的元素
     * @param elementAfter 把当前的元素插入到此元素后面
     */
    insert: function(element,elementAfter){
        var self = this;
        var insertPos = self.find(elementAfter);
        if(insertPos > -1) {
            self.dataStore.splice(insertPos+1,0,element);
            ++self.listSize;
            return true;
        }
        return false;
    },
    
    /* 清空列表中的所有元素
    * clear() 方法使用 delete 操作符删除数组 dataStore， 接着在下一行创建一个空数组。 最
 	* 后一行将 listSize 和 pos 的值设为 1， 表明这是一个新的空列表
    */
    clear: function() {
        delete this.dataStore;
        this.dataStore = [];
        this.listSize = this.pos = 0;
    },
    
    // 判断给定的元素是否在列表中
    contains: function(element) {
        var self = this;
        for(var i = 0,ilen = self.dataStore.length; i < ilen; i++) {
            if(self.dataStore[i] == element) {
                return true;
            }
        }
        return false;
    },
  
  /**
 * 下面的方法都是通过控制当前位置 pos 和 listSize 来实现的
 * */

    // 将列表中的当前元素移动到第一个位置
    front: function(){
        this.pos = 0;
    },
    // 将列表中当前的元素移动到最后一个位置
    end: function(){
        this.pos = this.listSize - 1;
    },
    // 将当前位置 后移一位
    prev: function(){
        if(this.pos > 0) {
            --this.pos;
        }
    },
    // 将当前位置 前移一位
    next: function(){
        if(this.pos < this.listSize - 1) {
            ++this.pos;
        }
    },
    // 返回列表的当前位置
    curPos: function(){
        return this.pos;
    },
    // 当前位置移动移动到某个位置(传入的是位置数字,从零开始)
    moveTo: function(n) {
        this.pos = n;
    },
    // 返回当前位置的元素
    getElement:function(){
        return this.dataStore[this.pos];
    }
};

//  下面来执行上面的方法
//创建一个列表实例对象
var names = new List();
names.append("Clayton");
names.append("Raymond");
names.append("Cynthia");
names.append("Jennifer");
names.append("Bryan");
names.append("Danny");
/*console.log(names) 输出
 * dataStore:(6) ["Clayton", "Raymond", "Cynthia", "Jennifer", "Bryan", "Danny"]
 * listSize:6    pos:0
 */

//1.现在移动到列表中的第一个元素并且显示它：
names.front();
console.log(names.getElement()); // 显示 Clayton

//2.接下来向后移动一个单位并且显示它：
names.next();
console.log(names.getElement()); // 显示 Raymond


//3.先向前移动两次， 然后向后移动一次， 显示出当前元素， 看看 prev() 方法的应用
names.next();
names.next();
names.prev();
console.log(names.getElement()); // 如果2执行的话，显示 Cynthia 如果不执行2，则显示Raymond

/**
 * !遍历!
 * 由前向后遍历列表:
 * 在 for 循环的一开始， 将列表的当前位置设置为第一个元素。 只要 curPos 的值小于列表
 * 的长度-1 (因为pos是从0开始的,比较完之后才会移动next() )， 就一直循环， 每一次循环都调用 next() 方法将当前位置向前移动一位。
 * */
//这里用names.pos++比较好,因为next() pos永远到不了names.length(),会一直循环
for (names.front(); names.curPos() < names.length(); names.pos++) {
    console.log(names.getElement());
    //console.log(names.currPos());
}
//但注意经过上面的遍历操作,pos指向的是最后一位+1,所以要 -1一次
names.pos -= 1;

/**
 * 从后向前遍历列表
 * 循环从列表的最后一个元素开始， 当当前位置大于或等于 0 时， 调用 prev() 方法后移一位。
 *
 * 迭代器只是用来在列表上随意移动， 而不应该和任何为列表增加或删除元素的方法一起使用
 * */
//这里用names.pos--比较好,因为pre() pos永远到0就不会降了,会一直循环
for(names.end(); names.curPos() >= 0; names.pos--) {
    console.log(names.getElement());
}
//但注意经过上面的遍历操作,pos指向的是-1,所以要 +1一次
names.pos += 1;

Related recommendations:

Detailed explanation of stacks and queues of js data structures and algorithms

Data structures and algorithms 1

JavaScript Data Structures and Algorithms Graphs and Graph Algorithms_Basic Knowledge

The above is the detailed content of Detailed explanation of arrays and hash tables of js data structures and algorithms. For more information, please follow other related articles on the PHP Chinese website!