js 데이터 구조와 알고리즘의 배열과 해시 테이블에 대한 자세한 설명

1. 데이터 구조란 무엇입니까? 데이터 구조는 데이터 요소 간의 하나 이상의 특정 관계의 모음입니다. 전통적으로 우리는 데이터 구조를 논리적 구조와 물리적 구조로 나눕니다. 논리적 구조: 데이터 객체에 포함된 데이터 요소 간의 관계를 말하며, 이는 앞으로 우리가 가장 관심을 갖고 논의해야 할 문제이기도 합니다. 물리적 구조(Physical Structure): 컴퓨터에 있는 데이터의 논리적 구조를 저장하는 형태를 말한다.

2.일반적으로 사용되는 데이터 구조에는 배열, 큐, 힙, 스택, 연결 목록, 트리, 그래프 및 해시가 포함됩니다.

스택: 작업은 테이블의 한쪽 끝에서만 수행됩니다. 작업은 테이블의 양쪽 끝에서만 수행됩니다. 큐는 한쪽 끝에서는 삽입 작업만 허용하고 다른 쪽 끝에서는 삭제 작업만 허용하는 선형 목록입니다.
스택과 달리 큐는 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 ='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. 배열 중간에 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차원 배열과 다차원 배열

//直接初始化
 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). 해시 테이블

1. 목록 개념

예를 들어 우리는 가끔 목록을 사용합니다. 쇼핑, 쇼핑할 때 모든 것을 사기 위해 가기 전에 사고 싶은 물건의 목록을 만들 수도 있습니다. 또는 우리가 어렸을 때 학교에 다닐 때마다 학교에서 사용하는 목록입니다. 시험에서 상위 10명의 학생의 순위와 성적표를 나열합니다. 이것들은 모두 목록의 예입니다. 우리는 컴퓨터에서도 목록을 사용하는데, 목록은 어디에 사용하기에 적합한가요? 사용하기에 적합하지 않은 곳은 어디입니까?

는 다음과 같은 경우에 사용하기에 적합합니다.

: 목록에 요소가 많지 않은 경우 목록을 사용할 수 있습니다. 반대로 목록에 있는 요소를 검색하거나 정렬할 때 효율성이 매우 높기 때문입니다. 목록에 요소가 많아 목록을 사용하는 것은 적합하지 않습니다. 저장 순서가 중요하지 않고(순서가 중요하면 스택 등을 고려할 수 있음) 데이터를 검색할 필요가 없다면 목록은 완벽한 데이터 구조입니다. 일부 다른 응용 프로그램의 경우 목록이 너무 간단합니다.

요약: 목록은 순서가 지정된 데이터 집합입니다. 각 목록의 데이터 항목을 요소라고 합니다. JavaScript에서 목록의 요소는 모든 데이터 유형이 될 수 있습니다. 목록에 얼마나 많은 요소를 저장할 수 있는지에 대한 사전 합의는 없습니다. 그러나 요소 수는 실제 사용 프로그램 메모리에 의해 제한됩니다.

2. 속성

3.

/**
 * 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;

사용 관련 권장 사항:

js 데이터 구조 및 알고리즘의 스택 및 큐에 대한 자세한 설명

데이터 구조 및 알고리즘 1

JavaScript 데이터 구조 및 알고리즘 그래프 및 그래프 알고리즘_기본 지식

위 내용은 js 데이터 구조와 알고리즘의 배열과 해시 테이블에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!