jsのデータ構造とアルゴリズムの配列とハッシュテーブルを詳しく解説-jsチュートリアル-php.cn

1. データ構造

1. データ構造とは何ですか? はい、データ要素間の 1 つ以上の特定の関係の集合です。従来、データ構造は論理構造と物理構造に分割されていました。論理構造: データオブジェクト内のデータ要素間の関係を指します。これは、今後最も注意を払い、議論する必要がある問題でもあります。物理構造: コンピュータ内のデータの論理構造の格納形式を指します。

一般的に使用されるデータ構造には、
配列、キュー、ヒープ、スタック、リンクリスト、ツリー、グラフ、ハッシュが含まれます。
スタック: 操作はテーブルの一方の端でのみ実行されます。操作はテーブルの両端でのみ実行されます。
キューは、一方の端で挿入操作、もう一方の端で削除操作のみを許可する線形リストです。
スタックとは対照的に、キューは先入れ先出し (FIFO) の線形リストです。

スタックと同様に、キューも重要な線形構造です。キューの実装には、基礎としてシーケンスリストまたはリンクリストが必要です。

2. データ構造分析

(1). 配列

配列の概念: 配列は構築型のデータ構造です。配列は、同じタイプの多数のデータのコレクションです。

配列の分類：1次元配列、2次元配列[行と行]、多次元配列(3次元以上[3次元配列の行と行の層])

1. 文字列を配列分割し、配列要素を文字列結合に分割します

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-配列内に要素と添字が存在するかどうかを確認します

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

ログイン後にコピー

3. 変更された要素を追加および削除します。配列の途中で 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. 新しいものを生成しない配列

forEachの反復子メソッドは各要素に対して動作します - すべてが満たされます - いくつかは満たすものがあります - 累積演算を削減します

/**
 * 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. 新しい配列を生成するイテレータメソッド

map each すべての要素に対して特定の操作を実行した結果で構成される配列 - フィルタ配列内の特定の条件を満たす要素で構成される配列

/**
 * 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. 二次元配列と多次元配列

(2). ハッシュテーブル

日常生活では、例えば、リストを使用することがあります。買い物をするときに、すべての物を買うために、私たちは行く前に買いたいもののリストを作ることができます。これは私たちが子供の頃、試験のたびに学生時代に使用したものです。学校では、試験の上位 10 位の生徒の順位と成績表がリストされます。これらはすべてリストの例です。私たちはコンピューターでもリストを使用しますが、リストはどこで使用するのに適しているのでしょうか?使用に適さない場所はどこですか?

は次のような場合に使用するのに適しています: リスト内の要素が少ない場合、リスト内の要素を検索または並べ替える際の効率が非常に高いため、リストを使用できます。逆に、リスト内の要素が非常に多い場合。リスト内の要素が多いため、リストの使用には適していません。ストレージの順序が重要ではなく (順序が重要な場合は、スタックなどを検討できます)、データを検索する必要がない場合、リストは完全なデータ構造です。他の一部のアプリケーションでは、リストは単純すぎます。

概要:
リストは順序付けられたデータのセットです。各リスト内のデータ項目は要素と呼ばれます。 JavaScript では、リスト内の要素は任意のデータ型にすることができます。リストに格納できる要素の数については、事前の合意はありません。ただし、要素数は実際に使用するプログラムメモリによって制限されます。

2. 属性

//直接初始化
 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

ログイン後にコピー

を使用する
関連する推奨事項: