js数据结构和算法之数组和散列表详解
1.什么是数据结构数据结构就是关系,没错,就是数据元素相互之间存在的一种或多种特定关系的集合。传统上,我们把数据结构分为逻辑结构和物理结构。逻辑结构:是指数据对象中数据元素之间的相互关系,也是我们今后最需要关注和讨论的问题。物理结构:是指数据的逻辑结构在计算机中的存储形式。
2.常用的数据结构有:
数组,队列(queue),堆(heap),栈(stack),链表(linked list ),树(tree),图(graph)和散列表(hash)
栈(stack):运算只在表的一端进行;队列(Queue):运算只在表的两端进行。
队列(queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表。
与栈相反,队列是一种先进先出(First In First Out, FIFO)的线性表。
与栈相同的是,队列也是一种重要的线性结构,实现一个队列同样需要顺序表或链表作为基础。
二.数据结构分析
(一).数组
数组的概念:数组是一个构造类型的数据结构。数组是许多个相同类型的数据的集合。
数组分类:一维数组,二维数组【行 列】,多维数组(三维以上【三维数组 行 列 层】)
1.字符串分割为数组split与数组元素拼接转字符串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-查找数组是否存在某元素及下标
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每个元素都操作--every所有都满足--some有一个满足--reduce累计操作
/** * 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每个元素都执行某操作结果组成的数组-filter数组中满足某条件的元素组成的数组
/** * 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.二维数组和多维数组
//直接初始化 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
(二).散列表
1.列表概念
在日常生活中,人们经常要使用列表,比如我们有时候要去购物时,为了购物时东西要买全,我们可以在去之前,列下要买的东西,这就要用的列表了,或者我们小时候上学那段时间,每次考完试后,学校都会列出这次考试成绩前十名的同学的排名及成绩单,等等这些都是列表的列子。我们计算机内也在使用列表,那么列表适合使用在什么地方呢?不适合使用在什么地方呢?
适合使用在:当列表的元素不是很多的情况下,可以使用列表,因为对列表中的元素查找或者排序时,效率还算非常高,反之:如果列表元素非常多的情况下,就不适合使用列表了。如果存储的顺序不重要(顺序重要的话可以考虑如堆栈等), 也不必对数据进行查找, 那么列表就是一种再好不过的数据结构。 对于其他一些应用, 列表就显得太过简陋了
总结:列表是一组有序的数据。每个列表中的数据项称为元素。在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数据结构和算法之数组和散列表详解的详细内容,更多请关注其它相关文章!