乐趣区

关于javascript:javascript学习数据结构数组列表

jiezi

算法 + 数据结构 = 程序，任何一个有些规模的程序都须要某种类型的数据结构来保留程序中用到的数据，学习数据结构和算法，不仅能够晓得哪种数据结构和算法更高效，还会晓得如何找出最适宜解决手头问题的数据结构和算法。本篇文章会应用 javascript 实现常见的数据结构

数组

数组的规范定义是：一个存储元素的线性汇合（collection），元素能够通过索引来任意存取，索引通常是数字，用来计算元素之间存储地位的偏移量。以下是数组的一些基本操作

创立数组

最简略的形式是通过 [] 操作符申明一个数组变量，应用这种形式创立数组，你将失去一个长度为 0 的空数组。

let numbers = [];
console.log(numbers.length)// 输入 0

间接在 [] 操作符内放入一组元素

let numbers = [1,2,3,4,5];

还能够调用 Array 的构造函数创立数组

let numbers = new Array(1,2,3,4,5);
console.log(numbers.length); // 显示 5

在调用 Array 的构造函数时，能够只传入一个参数，用来指定数组的长度

let numbers = new Array(10);

数组中的元素不用是同一种数据类型

let objects = [1, "Joe", true, null];

由字符串生成数组

let sentence = "the quick brown fox jumped over the lazy dog";
let words = sentence.split(" ");
console.log(words)

由已有数组创立新数组

concat 办法能够合并多个数组创立一个新数组

let arr1 = ["1", "2"];
let arr2 = ["a", "b", "c"];
let newarr = arr1.concat(arr2);//newarr 被赋值['1', '2', 'a', 'b', 'c']

splice() 办法截取一个数组的子集创立一个新数组。

array.splice(index, howmany, item1, ....., itemX)

参数值

参数 形容
index 必须。整数，指定在什么地位增加 / 删除我的项目，应用负值指定从数组开端开始的地位。
howmany 可选。要删除的项目数。如果设置为 0，则不会删除任何我的项目。
item1, …, itemX 可选。要增加到数组中的新我的项目。

这里只演示创立数组，增加和删除元素之后还会用上 splice()

let fruits = ['Banana', 'Orange', 'Lemon', 'Kiwi', 'Apple', 'Mango']
let arr = fruits.splice(2, 4);
console.log(arr)//['Lemon', 'Kiwi', 'Apple', 'Mango']

from() 办法从具备 length 属性或可迭代对象的任何对象返回 Array 对象。

let myArr = Array.from("ABCDEFG",(item)=>{return item+'1'});
console.log(myArr)// ['A1', 'B1', 'C1', 'D1', 'E1', 'F1', 'G1']

filter() 办法创立数组，其中填充了所有通过测试的数组元素

let ages = [32, 33, 16, 40];
let filterAges = ages.filter(age=>{return age >= 18;})
console.log(filterAges)//[32, 33, 40]

能够调用 Array.isArray() 来判断一个对象是否是数组，

let numbers = 3;
let arr = [7,4,1776];
console.log(Array.isArray(numbers)); //false
console.log(Array.isArray(arr)); //true

查找元素

find() 办法返回数组中第一个通过测试的元素的值

let ages = [3, 10, 18, 20];
let result = ages.find(age=>{return age>10})
console.log(result)//18

findIndex() 办法返回数组中通过测试的第一个元素的索引

let ages = [3, 10, 18, 20];
let result = ages.findIndex(age=>{return age>10})
console.log(result)//2

includes() 办法确定数组是否蕴含指定的元素。

let fruits = ["Banana", "Orange", "Apple", "Mango"];
let result = fruits.includes("Mango");
console.log(result)//true

indexOf() 在数组中搜寻元素并返回其地位。

let fruits = ["Banana", "Orange", "Apple", "Mango"];
let result = fruits.indexOf("Apple");
console.log(result)//2

lastIndexOf()，该函数返回雷同元素中最初一个元

let fruits = ["Banana","pear", "Apple", "Apple", "Mango"];
let result = fruits.lastIndexOf("Apple");
console.log(result)//3

打印数组

join()将数组的所有元素连接成一个字符串。元素将由指定的分隔符分隔。默认分隔符是逗号 (,)。

let fruits = ["Banana", "Orange", "Apple", "Mango"];
let str = fruits.join();
console.log(str)//Banana,Orange,Apple,Mango
let andStr = fruits.join("and");
console.log(andStr)//Banana and Orange and Apple and Mango

toString()将数组转换为字符串，并返回后果。

let fruits = ["Banana", "Orange", "Apple", "Mango"];
let string = fruits.toString();
console.log(string)//Banana,Orange,Apple,Mango

为数组增加元素

push() 办法会将一个元素增加到

// 增加单项
let arr = [1,2,3,4,5]
arr.push(6)
console.log(arr)//[1,2,3,4,5,6]

// 增加多项
arr = [1,2,3,4,5]
arr.push(6,7,8,9)
console.log(arr)//[1,2,3,4,5,6,7,8,9]

unshift() 办法能够将元素增加在数组的结尾，

let arr = [1,2,3,4,5]
arr.unshift(6,7,8)
console.log(arr)//[6, 7, 8, 1, 2, 3, 4, 5]

splice() 办法向数组增加我的项目，并返回删除的我的项目。

let arr = [1,2,3,4,5]
arr.splice(3,0,'a','b','c')
console.log(arr)//[1, 2, 3, 'a', 'b', 'c', 4, 5]

从数组中删除元素

应用 pop() 办法能够删除数组开端的元素：

let arr = [1,2,3,4,5]
arr.pop()// 返回 5
console.log(arr)//[1,2,3,4]

shift() 办法能够删除数组的第一个元素，

let arr = [1,2,3,4,5]
arr.pop()// 返回 1
console.log(arr)//[2,3,4,5]

应用 splice()从数组两头地位删除元素

let arr = [1,2,3,4,5]
arr.splice(1,3)
console.log(arr)//[1, 5]

数组排序操作

reverse()，该办法将数组中元素的程序进行翻转。

let arr = [1,2,3,4,5]
arr.reverse()
console.log(arr)//[5, 4, 3, 2, 1]

sort()办法对数组的我的项目进行排序。

var points = [40, 100, 1, 5, 25, 10];
points.sort(function(a, b){return a-b});
console.log(points)// [1, 5, 10, 25, 40, 100]

迭代器办法

forEach() 办法按程序为数组中的每个元素调用一次函数。

let arr = [1,2,3,4,5]
arr.forEach(item=>{console.log(item)})// 每个元素都会遍历一遍

filter() 办法创立数组，其中填充了所有通过测试的数组元素（作为函数提供）。

let ages = [32, 33, 16, 40];
let filterAges = ages.filter(age=>{return age >= 18;})

map() 办法应用为每个数组元素调用函数的后果创立新数组。

let arr = [1,2,3,4,5]
let newArr = arr.map(item=>{return item*10})// 返回新数组[10,20,30,40,50]

reduce() 办法为数组的每个值（从左到右）执行提供的函数。

let arr = [1,2,3,4,5]
arr.reduce((total,num)=>{return total+num},0);// 返回 15

reduceRight() 办法为数组的每个值（从右到左）执行提供的函数。

let arr = [1,2,3,4,50]
arr.reduceRight((total,num)=>{return total-num})// 返回 40

every() 办法查看数组中的所有元素是否都通过了测试

let arr = [1,2,3,4,50]
arr.every(item=>{return item<40})// 返回 false

some() 办法查看数组中的任何元素是否通过测试

let arr = [1,2,3,4,50]
arr.some(item=>{return item<40})// 返回 true

列表

列表是一组有序的数据。每个列表中的数据项称为元素。不蕴含任何元素的列表称为空列表。列表中蕴含元素的个数称为列表的 length。
上面实现列表类及其操作方法的实现
## 实现列表类
列表类中定义三个属性

  1. length 代表元素的个数
  2. position 代表以后指针地位

  3. dataStore 代表数据汇合

    class List{
  length= 0
  position = 0
  dataStore = []
  constructor(){}
}

    length()：获取元素个数

length(){return this.length}

append()：给列表增加元素

append(element){this.dataStore[this.length++] = element;
  }

find()：在列表中查找某一元素

find(element){for(let index = 0,length = this.length;index<length;index++){if(this.dataStore[index] ==element){return index}
    }
    return -1
  }

remove()：从列表中删除元素

remove(element){
    // 应用双指针
    let index = 0
    let moveIndex = 0 // 遍历所用的指针
    
    let size = this.listSize
    // 遍历数组
    while(moveIndex<=size){
      // 找到删除的元素后，仅遍历用的指针前移
      if(this.dataStore[moveIndex] ==element){
        moveIndex++
        this.length--
        continue
      }
      if(index<moveIndex){this.dataStore[index] = this.dataStore[moveIndex]
      }
      index++
      moveIndex++
    }
    // 有删除元素，返回 true, 否则, 返回 false
    if(index<moveIndex){
      this.dataStore.length = this.length
      return true
    }else{return false}  
  }

clear(): 革除列表数据的办法

clear(){
    this.length= 0
    this.dataStore = []
    this.position= 0
  }

toString(): 用来打印数据的办法

toString(){return this.dataStore}

getElement(): 失去以后地位的元素

getElement(){return this.dataStore[this.position]
  }

insertAfter(): 在某地位前面增加元素

insertAfter(element,after){
    // 边界判断
    if(after>=this.length||after<-1){return}
    this.listSize++
    this.dataStore.length = this.length
    
    // 双指针，从后往前挪动
    let index = this.length-1
    let moveIndex = this.length-2
    while(moveIndex>=-1){if(after==moveIndex&&index!=moveIndex){this.dataStore[index]= element
        index--
        break
      }
      this.dataStore[index]= this.dataStore[moveIndex]
      moveIndex--
      index--
    }
  }

insert(): 在指定地位插入元素

  insert(element,index){this.insertAfter(element,index-1)
  }

地位操作

  // 首部
  front(){this.position= 0;}
  // 尾部
  end(){this.position= this.length-1;}
  // 前一步
  prev(){this.position>0&&this.position--}
  // 后一步
  next(){this.position<(this.length-1)&& this.position++
  }
  // 以后地位
  currPos(){return this.position}
  // 挪动到指定地位
  moveTo(position){position<(this.length-1)&&(this.position=position)
  }

整体代码

class List {
    length = 0
    position = 0
    dataStore = []
    constructor() {}
    append(element) {this.dataStore[this.length++] = element;
    }
    remove(element) {
        let index = 0
        let moveIndex = 0
        let size = this.length
        while (moveIndex <= size) {if (this.dataStore[moveIndex] == element) {
                moveIndex++
                this.length--
                    continue
            }
            if (index < moveIndex) {this.dataStore[index] = this.dataStore[moveIndex]
            }
            index++
            moveIndex++
        }
        if (index < moveIndex) {
            this.dataStore.length = this.length
            return true
        } else {return false}
    }
    find(element) {for (let index = 0, length = this.length; index < length; index++) {if (this.dataStore[index] == element) {return index}
        }
        return -1
    }
    length() {return this.length}
    clear() {
        this.length = 0
        this.dataStore = []
        this.position = 0
    }
    toString() {return this.dataStore}
    getElement() {return this.dataStore[this.position]
    }
    insertAfter(element, after) {if (after >= this.length || after < -1) {return}
        this.length++
            this.dataStore.length = this.length
        let index = this.length - 1
        let moveIndex = this.length - 2
        while (moveIndex >= -1) {if (after == moveIndex && index != moveIndex) {this.dataStore[index] = element
                index--
                break
            }
            this.dataStore[index] = this.dataStore[moveIndex]
            moveIndex--
            index--
        }
    }
    insert(element, index) {this.insertAfter(element, index - 1)
    }
    front() {this.position = 0;}
    end() {this.position = this.length - 1;}
    prev() {this.position > 0 && this.position--}
    next() {this.position < (this.length - 1) && this.position++
    }
    currposition() {return this.position}
    moveTo(positionition) {positionition < (this.length - 1) && (this.position = positionition)
    }
}
退出移动版