首页 > 编程语言 >JavaScript数据结构和算法简述——数组

JavaScript数据结构和算法简述——数组

时间：2023-07-24 17:07:51浏览次数：65  
标签：arr 元素 int JavaScript length 简述 pArr 数组 数据结构


为什么先讲数组

数据结构可以简单的被分为线性结构和非线性结构。

线性结构大致包括：

  1. 数组（连续存储）；
  2. 链表（离散存储）；
  3. 栈（线性结构常见应用，由链表或数组增删和改进功能实现）；
  4. 队列（线性结构常见应用，由链表或数组增删和改进功能实现）；

非线性结构大致包括：

  1. 树；
  2. 图；

其中，数组是应用最广泛的数据存储结构。它被植入到大部分编程语言中。由于数组十分容易懂，所以它被用来作为介绍数据结构的起点非常合适。

JavaScript数组基础知识

在ECMAScript中数组是非常常用的引用类型了。ECMAScript所定义的数组和其他语言中的数组有着很大的区别。那么首先要说的就是数组在js中是一种特殊的对象。

特点：

  1. 数组是一组数据的线性集合；
  2. js数组更加类似java中的容器。长度可变，元素类型也可以不同；
  3. 数组的长度可以随时修改（length属性）；

常用操作方法：

  • push、pop
  • shift、unshift
  • splice、slice
  • concat、join、sort、reverse等

JavaScript数组操作

一、 数组方法：

 

1、 数组的创建


var array = [];
 
var array = new Array();　//创建一个数组
 
var array = new Array([size]);　//创建一个数组并指定长度，注意不是上限，是长度
 
var array = new Array([element0[, element1[, ...[, elementN]]]]);　//创建一个数组并赋值


 注意：虽然第三种方法创建数组指定了长度，但实际上所有情况下数组都是变长的，也就是说即使指定了长度为5，仍然可以将元素存储在规定长度以外的，并且这时长度会随之改变。



 

2、 数组元素的访问


var getArrItem=array[1]; //获取数组的元素值
 
array[1]= "new value"; //给数组元素赋予新的值


3、 数组元素的添加



array. push([item1 [item2 [. . . [itemN ]]]]);// 将一个或多个新元素添加到数组结尾，并返回数组新长度
 
array.unshift([item1 [item2 [. . . [itemN ]]]]);// 将一个或多个新元素添加到数组开始，数组中的元素自动后移，返回数组新长度
 
array.splice(insertPos,0,[item1[, item2[, . . . [,itemN]]]]);//将一个或多个新元素插入到数组的指定位置，插入位置的元素自动后移，返回""。



4、 数组元素的删除



array.pop(); //移除最后一个元素并返回该元素值
 
array.shift(); //移除最前一个元素并返回该元素值，数组中元素自动前移
 
array.splice(deletePos,deleteCount); //删除从指定位置deletePos开始的指定数量deleteCount的元素，数组形式返回所移除的元素
 
array.slice(start, [end]); //以数组的形式返回数组的一部分，注意不包括 end 对应的元素，如果省略 end 将复制 start 之后的所有元素



5、 数组的合并



array.concat([item1[, item2[, . . . [,itemN]]]]); //将多个数组（也可以是字符串，或者是数组和字符串的混合）连接为一个数组，返回连接好的新的数组


6、 数组的拷贝



array.slice(0); //返回数组的拷贝数组，注意是一个新的数组，不是指向
 
array.concat(); //返回数组的拷贝数组，注意是一个新的数组，不是指向


7、 数组元素的排序


array.reverse(); //反转元素（最前的排到最后、最后的排到最前），返回数组地址
 
array.sort(); //对数组元素排序，返回数组地址


 

8、 数组元素的字符串化



array.join(separator); //返回字符串，这个字符串将数组的每一个元素值连接在一起，中间用 separator 隔开。
 
//toLocaleString 、toString 、valueOf：可以看作是join的特殊用法，不常用


简单介绍了下数组各个方法的使用，也算是对js数组学习的一个review和总结，利用这些方法可以实现数组更复杂些的操作，具体大家可以自己去实践。可见，js数组的功能很强大。



 

二、 数组属性

 

1、 length属性

length 属性表示数组的长度，即其中元素的个数。因为数组的索引总是由0开始，所以一个数组的上下限分别是：0和length-1。和其他大多 数语言不同的是，JavaScript数组的length属性是可变的，这一点需要特别注意。当length属性被设置得更大时，整个数组的状态事实上不 会发生变化，仅仅是length属性变大；当length属性被设置得比原来小时，则原先数组中索引大于或等于length的元素的值全部被丢失。下面是 演示改变length属性的例子：



ar arr=[12,23,5,3,25,98,76,54,56,76];
 
//定义了一个包含10个数字的数组
 
print(arr.length); //显示数组的长度10
 
arr.length=12; //增大数组的长度
 
print(arr.length); //显示数组的长度已经变为12
 
print(arr[8]); //显示第9个元素的值，为56
 
arr.length=5; //将数组的长度减少到5，索引等于或超过5的元素被丢弃
 
print(arr[8]); //显示第9个元素已经变为"undefined"
 
arr.length=10; //将数组长度恢复为10
 
print(arr[8]); //虽然长度被恢复为10，但第9个元素却无法收回，显示"undefined"

 


 

由上面的代码我们可以 清楚的看到length属性的性质。但length对象不仅可以显式的设置，它也有可能被隐式修改。JavaScript中可 以使用一个未声明过的变量，同样，也可以使用一个未定义的数组元素（指索引超过或等于length的元素），这时，length属性的值将被设置为所使用 元素索引的值加1。例如下面的代码：



var arr=[12,23,5,3,25,98,76,54,56,76];
 
print(arr.length); // 10
 
arr[15]=34;
 
print(arr.length); // 16

 


 

代码中同样是先定义了一个包含10个数字的数组，可以看出其长度为10。随后使用了 索引为15的元素，将其赋值为15，即 arr[15]=34，这时再输出数组的长度，得到的是16。无论如何，对于习惯于强类型编程的开发人员来说，这是一个很令人惊讶的特性。事实上，使用 new Array()形式创建的数组，其初始长度就是为0，正是对其中未定义元素的操作，才使数组的长度发生变化。

综上，利用length属性可以方便的增加或者减少数组的容量。

 

2、 prototype属性

返回对象类型原型的引用。prototype 属性是 object 共有的。

objectName.prototype

objectName 参数是object对象的名称。

对于数组对象，以下例子说明 prototype 属性的用途。

给数组对象添加返回数组中最大元素值的方法。要完成这一点，声明一个函数，将它加入 Array.prototype， 并使用它。



function array_max() {
 
    var i,
 
    max = this[0];
 
    for (i = 1; i < this.length; i++) {
 
        if (max < this[i])
 
        max = this[i];
 
    }
 
    return max;
 
}
 
Array.prototype.max = array_max;
 
var x = new Array(1, 2, 3, 4, 5, 6);
 
print(x.max()); // 6


 

 

3、 constructor属性

表示创建对象的函数。

object.constructor // object是对象或函数的名称。

说明：constructor 属性是所有具有 prototype 的对象的成员。constructor 属性保存了对构造特定对象实例的函数的引用。



x = new Array();
 
print(x.constructor === Array); // true


 

JavaScript数组算法的C语言实现

使用没有指针的语言，个人觉得无法将数据结构和算法的精髓讲的出来，而且js底层已将数组相关算法封装好，所以这里不使用原生的js或者java等，而是使用c语言来实现。为了照顾没有学过指针的同学，我会尽可能的简单实现，并写好注释，画好图解，大家可以体会一下。



# include <stdio.h>
# include <malloc.h>  //包含了malloc函数
# include <stdlib.h>  //包含了exit函数
 
//定义了一个数据类型，该数据类型的名字叫做struct Arr, 该数据类型含有三个成员，分别是pBase, len, cnt
struct Arr
{
    int * pBase; //存储的是数组第一个元素的地址
    int len; //数组所能容纳的最大元素的个数
    int cnt; //当前数组有效元素的个数
};
 
void init_arr(struct Arr *, int);  //初始化数组
bool is_empty(struct Arr *); // 数组是否为空
bool is_full(struct Arr *); // 数组是否已满
bool push(struct Arr *, int); //追加元素
void sort(struct Arr *); // 排序
void reverse(struct Arr *); // 逆序
bool insert(struct Arr *, int, int); // 插入元素
bool del(struct Arr *, int, int *); // 删除元素
void show_arr(struct Arr *); // 打印数组
 
int main(void) {
    struct Arr arr;
 
    int val; // 存储删除元素
 
    init_arr(&arr, 6); // 初始化数组
    show_arr(&arr);
 
    push(&arr, 4); // 在尾部追加元素
    push(&arr, 1);
    push(&arr, -1);
    push(&arr, 10);
    push(&arr, 0);
    push(&arr, 6);
    show_arr(&arr);
 
    sort(&arr); // 排序
    show_arr(&arr);
 
    reverse(&arr); // 逆序
    show_arr(&arr);
 
    del(&arr, 4, &val); // 删除指定位置元素
    printf("您删除的元素是: %dn", val);
    show_arr(&arr);
 
    insert(&arr, 4, 20); // 在指定位置插入元素
    show_arr(&arr);
 
    return 0;
}
 
void init_arr(struct Arr * pArr, int length) {
    pArr->pBase = (int *)malloc(sizeof(int) * length);
    if(NULL == pArr->pBase) {
        printf("动态内存分配失败!n");
        exit(-1); //终止整个程序
    }
    else {
        pArr->len = length;
        pArr->cnt = 0;
    }
    return;
}
 
bool is_empty(struct Arr * pArr) {
    if(0 == pArr->cnt) {
        return true;
    } else {
        return false;  
    }      
}
 
bool is_full(struct Arr * pArr) {
    if (pArr->cnt == pArr->len) {
        return true;
    } else {
        return false;
    }
}
 
void show_arr(struct Arr * pArr) {
    if(is_empty(pArr)) {
        printf("数组为空!n");
    } else {
        for(int i=0; i<pArr->cnt; ++i) {
            printf("%d  ", pArr->pBase[i]);
        }
        printf("n");
    }
}
 
bool push(struct Arr * pArr, int val) {
    //满了就返回false
    if(is_full(pArr)) {
        return false;
    }
    //不满时追加
    pArr->pBase[pArr->cnt] = val;
    (pArr->cnt)++;
    return true;
}
 
void sort(struct Arr * pArr) {
    int i, j, t;
    // 简单的冒泡排序法实现，后面的章节会单独讲排序算法
    for(i=0; i<pArr->cnt; ++i) {
        for(j=i+1; j<pArr->cnt; ++j) {
            if(pArr->pBase[i] > pArr->pBase[j]) {
                t = pArr->pBase[i];
                pArr->pBase[i] = pArr->pBase[j];
                pArr->pBase[j] = t;
            }
        }
    }
}
 
void reverse(struct Arr * pArr) {
    int i = 0;
    int j = pArr->cnt-1;
    int t;
    // 当i<j时，置换i和j位置的元素
    while(i < j) {
        t = pArr->pBase[i];
        pArr->pBase[i] = pArr->pBase[j];
        pArr->pBase[j] = t;
        ++i;
        --j;
    }
    return;
}
 
bool insert(struct Arr * pArr, int pos, int val) {
    int i;
    // 满了就算了
    if(is_full(pArr)) {
        return false;
    }
    // 如果插入的位置不在数组有效范围内就算了
    if(pos<1 || pos>pArr->cnt+1) {
        return false;
    }
    // 从插入位置开始后移各元素，将插入位置空出
    for(i=pArr->cnt-1; i>=pos-1; --i) {
        pArr->pBase[i+1] = pArr->pBase[i];
    }
    // 给插入位置的元素赋值
    pArr->pBase[pos-1] = val;
    //数组有效长度自增
    (pArr->cnt)++;
    return true;
}
 
bool del(struct Arr * pArr, int pos, int * pVal) {
    int i;
    // 空就算了
    if(is_empty(pArr)) {
        return false;
    }
    // 不在有效范围内就算了
    if (pos<1 || pos>pArr->cnt) {
        return false;
    }
    // 存储被删除元素
    *pVal = pArr->pBase[pos-1];
    // 从删除位置开始，前移各元素，将删除位置堵死
    for (i=pos; i<pArr->cnt; ++i) {
        pArr->pBase[i-1] = pArr->pBase[i];
    }
    // 数组有效长度自减
    pArr->cnt--;
    return true;
}

 


 

执行结果：



JavaScript数据结构和算法简述——数组

程序图解：


JavaScript数据结构和算法简述——数组

衡量算法的标准

需要详细了解的同学请阅读相关书籍。这里我简单介绍一下。

 

1、 时间复杂度

程序大概要执行的次数，而非执行的时间

通 常使用大O表示法（含义："order of"大约是）来表示。比如无序数组的插入，无论数组中有多少数据项，都只需要在下一个有空的地方进行一步插入操作，那么可以说向一个无序数组中插入一个 数据项的时间T是一个常数K： T=K；又比如线性查找，查找特定数据项所需的比较次数平均为数据项总数的一半，因此可以说：T=KN/2，为了得到更加简洁的公式，可以将2并入K，可以得到：T=KN。大O表示法同上面的公式比较类似，但是它省略了常数K。当比较算法时，并不在乎具体的处理器或者编译器，真正需要比较的是对应不同的N值T是怎样变化的，而不是具体的数字。

 

用大O表示法表示数组相关算法运行时间：

算法

大O表示法

线性查找

O(N)

二分查找

O(logN)

无序数组的插入

O(1)

有序数组的插入

O(N)

无序数组的删除

O(N)

有序数组的删除

O(N)

注：O(1)是优秀；O(logN)是良好；O(N)还可以；O(N2)就差一些了。

 

2、 空间复杂度

算法执行过程中大概所占用的最大内存

 

3、 难易程度

写出来的算法不能只让自己看得懂，或者自己写完以后自己也看不懂了。。。

 

4、 健壮性

不能一用就崩溃。。。

为什么不用数组表示一切

仅用数组看似可以完成所有的工作，那么为什么不用它来进行所有的数据存储呢？

 

在一个无序数组中可以很快进行插入（O(1)），但是查找却要花费较多的时间O(N)。在一个有序数组中可以查找的很快（O(logN)），但是插入却要O(N)。对于有序和无序数组，由于平均半数的数据项需要移动，所以删除操作平均需要花费O(N)。

 

如果有一种数据结构进行任何插入、删除和查找操作都很快（O(1)或者O(logN)）,那就太爽了哈。后面我们会向这一目标靠近。


 

 

标签：arr,元素,int,JavaScript,length,简述,pArr,数组,数据结构
From： https://blog.51cto.com/u_8895844/6836732

相关文章

  • JavaScript 需要清楚的10件事
    文/谢传贵  在学习JavaScript的过程中，最需要搞清楚的10件事是什么？关于这个问题有人在Quora上给出了的答案。其中提到了一些很有代表性的知识点（坑），但描述比较杂乱。下面我将在他的基础上进行重新编排和解释。希望对你学习JavaScript有些帮助（为避免文章跑题，以下内容先不考虑ES5......
  • javascript基本数据类型与值类型引用类型说明
    DEMO:http://sources.ikeepstudying.com/jsdata/ 摘要：本文主要讲了javascript中的基本数据类型，以及值类型和引用类型的区别与使用一、基本数据类型在javascript中申明变量使用的关键字都是var，这点与其他的编程语言不尽相同，但是javascript亦含有五种基本的数据类型（也可以说是简......
  • 7.24 day1数据结构
    day1数据结构考试整场比赛打完了，没用数据结构？！结果：100+30+40+30=200T1正解异或好性质，100000以下最多128个因数枚举每个右端点，将前缀异或塞进桶里，同时枚举因数，看有几个和自己对应的前缀异或，直接计数即可T2暴力要输出分数，考场实在没办法，用浮点数做01分数规划，最后枚举分母（只......
  • JavaScript基础-数组（进阶）
    扩展运算符letarr1=[1,2],arr2=[3,4];letarr3=arr1.concat(arr2);letarr4=[...arr1,...arr2]console.log(arr4);用concat 连接然后...展开letarr1=[1,2];letarr2=[...arr1]console.log(arr1,arr2);把arr1的值传给arr2，输出[1,2][1,2]......
  • javaScript 小知识
    ??运算符只有前面的值是undefined才会执行letstatus=undefined;lettext=status??"暂无"console.log(text)//暂无?.运算符这在有时候处理对象时非常有用，看下面案例，person.name返回undefined然后在调用toString这时肯定会报错，这时使用?.运算符就不会产生错误，?.......
  • JavaScript复习知识点
    原型在JavaScript中，每个对象都有一个原型（prototype）。原型是一个对象，其他对象可以通过它来继承属性和方法。简单来说，对象通过其原型来共享和访问属性和方法。原型以原型链的形式连接在一起，形成了一个对象和原型之间的关系。当我们访问对象的属性或方法时，JavaScript引擎首先在......
  • 数组去重方法总结（JavaScript 记录）
    在进行项目开发的时候，有时候需要把一些前端的数组进行去重处理，得到一个去重后的数据，然后再进行相关的操作，这也是在前端面试中经常出现的问题数组去重的多种方法：利用ES6Set去重利用for嵌套for，然后splice去重利用indexOf去重利用sort()去重利用对象的属性不能相......
  • JavaScript jQuery 比对示例，ajax示例
    js教程：https://www.w3school.com.cn/js/index.aspjQuery教程：https://www.w3school.com.cn/jquery/index.asp以下是部分代码示例<!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><title>javascript</t......
  • JavaScript程序设计模式小技巧——策略模式，快看快用！！！
    ##前言>系列首发于公众号[『非同质前端札记』](https://mp.weixin.qq.com/s?__biz=MzkyOTI2MzE0MQ==&mid=2247485576&idx=1&sn=5ddfe93f427f05f5d126dead859d0dc8&chksm=c20d73c2f57afad4bbea380dfa1bcc15367a4cc06bf5dd0603100e8bd7bb317009fa65442cdb&token=1071012......
  • 简述倒排索引
    倒排索引是什么？1.2倒排索引倒排索引的概念是基于MySQL这样的正向索引而言的。1.2.1正向索引那么什么是正向索引呢？例如给下表（tb_goods）中的id创建索引：如果是根据id查询，那么直接走索引，查询速度非常快。但如果是基于title做模糊查询，只能是逐行扫描数据，流程如下：1）用户搜索数据......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99