《Js数据结构总结》课件

JS数据结构总结JavaScript数据结构是构建复杂应用程序的基础。了解各种数据结构及其应用是高效代码的关键。课程介绍11.学习目标掌握JavaScript数据结构的基本概念、应用场景和实现方式。22.课程内容从基本数据类型到复杂数据结构，涵盖常用算法和数据结构的分析与实现。33.学习方式理论讲解与代码实践相结合，以项目案例的形式巩固学习成果。JavaScript简介动态网页JavaScript是一种脚本语言，用于创建动态网页和Web应用程序。交互式体验它使网站能够响应用户操作，例如鼠标悬停、点击按钮和表单提交。客户端脚本JavaScript在用户的浏览器中运行，而不是服务器上，因此可以提供快速、流畅的交互体验。基本数据类型数字JavaScript使用64位浮点数表示数字。支持整数和浮点数。字符串字符串是字符序列。使用单引号或双引号括起来。布尔值布尔值表示真或假，分别用true和false表示。空值null表示空值，它表示没有值或不存在的值。引用数据类型对象对象是一组键值对的集合，表示复杂数据结构。数组数组是一组有序的元素集合，可以使用索引访问。函数函数是一段可重复执行的代码块，可以接受参数并返回结果。变量声明与赋值声明变量使用`var`、`let`或`const`关键字声明变量，并指定变量名称。赋值使用赋值运算符`=`将值分配给已声明的变量。数据类型变量可以存储不同的数据类型，例如数字、字符串、布尔值、对象等。作用域变量的作用域决定了变量在代码中的可见范围，例如全局变量和局部变量。数组顺序存储结构数组是一种线性数据结构，元素在内存中按顺序排列。随机访问可以通过索引直接访问数组中的任何元素，速度快。固定大小数组的大小在创建时固定，无法动态改变。数组遍历1for循环for循环是最常用的遍历方法，它可以精确控制循环次数。它适用于已知数组长度的情况。2forEach循环forEach循环可以方便地遍历数组元素，并对每个元素执行回调函数。它不需要预先知道数组长度。3for...in循环for...in循环用于遍历对象的属性，它可以访问数组元素的索引，但无法直接获取元素值。数组方法JavaScript数组方法JavaScript提供丰富的方法操作数组，简化编程，提高效率。添加和删除元素push()方法向数组末尾添加新元素，pop()方法删除数组的最后一个元素。开头操作unshift()方法在数组开头添加新元素，shift()方法删除数组的第一个元素。灵活修改数组splice()方法允许在指定位置插入或删除元素，甚至可以替换元素。对象11.数据集合对象是一组键值对，用于存储和组织数据。键是字符串，值可以是任何数据类型。22.属性和方法对象包含属性和方法，属性用于存储数据，方法用于操作数据。33.访问数据可以使用点运算符或方括号运算符访问对象的属性和方法。44.实例化可以使用构造函数或字面量创建对象。对象遍历1for...in循环遍历对象所有可枚举属性2Object.keys()返回对象所有可枚举属性的键3Object.values()返回对象所有可枚举属性的值4Object.entries()返回对象所有可枚举属性的键值对对象遍历用于访问和操作对象中的属性。常用的方法包括：for...in循环，它可以遍历所有可枚举属性；Object.keys()方法可以获取所有可枚举属性的键；Object.values()方法可以获取所有可枚举属性的值；Object.entries()方法可以获取所有可枚举属性的键值对。栈后进先出栈是一种线性数据结构，遵循后进先出的原则。新元素添加到栈顶，最先添加的元素在栈底。常见操作栈支持的主要操作包括入栈（push）、出栈（pop）、获取栈顶元素（peek）和判断栈是否为空（isEmpty）。应用场景栈在函数调用、表达式求值、浏览器历史记录和撤销操作等场景中发挥着重要作用。队列先进先出队列遵循先进先出(FIFO)原则，与现实世界中的排队等候类似。入队新元素添加到队列尾部。出队从队列头部移除元素。链表定义链表是一种线性数据结构，数据节点线性排列，每个节点包含数据域和指针域，指针指向下一个节点。特点链表的内存地址不连续，数据节点之间通过指针连接。链表可以动态地添加或删除节点，但访问指定节点需要遍历。双向链表结构特点每个节点包含数据、前驱节点和后继节点的引用。可以双向遍历链表。插入操作在指定位置插入新节点，更新前后节点的引用，操作复杂度为O(1)。删除操作删除指定节点，更新前后节点的引用，操作复杂度为O(1)。应用场景实现LRU缓存、undo/redo操作、音乐播放器等。集合无序集合集合元素没有顺序，集合中不允许重复元素。数据结构集合是一种常用的数据结构，用于存储和管理一组数据。数学集合集合的概念来源于数学，它是一组对象的集合。字典键值对存储字典是一种键值对集合，提供高效的数据存储和检索。快速查找通过键直接访问值，实现快速查找操作，适用于频繁查找的场景。灵活应用字典在编程语言中广泛使用，用于存储配置、数据映射等。哈希表11.键值对存储哈希表使用键值对存储数据，通过键快速访问值。22.哈希函数哈希函数将键映射到哈希表中的索引位置。33.冲突处理当多个键映射到同一个索引位置时，需要处理冲突。44.应用场景哈希表广泛应用于缓存、数据库索引、查找等场景。树树的概念树是一种非线性数据结构，由节点组成，节点之间通过边连接。树的节点之间具有父子关系，树的根节点没有父节点，其他节点只有一个父节点。树的种类树的种类很多，常用的树结构包括二叉树、堆、图等等。每种树结构都有各自的特点，适用于不同的场景。二叉树结构每个节点最多有两个子节点，分别称为左子节点和右子节点。遍历常用的遍历方式包括前序遍历、中序遍历和后序遍历。查找根据节点的值进行查找，找到目标节点或返回空。二叉搜索树定义二叉搜索树是一种特殊的二叉树，每个节点的值都大于左子树中的所有节点，并且小于右子树中的所有节点。它是一种高效的查找数据结构，可以快速地进行搜索、插入和删除操作。特点二叉搜索树支持多种操作，包括查找、插入、删除、最小值、最大值、前驱、后继等。由于二叉搜索树具有独特的结构，因此它在实现各种算法和数据结构中被广泛应用。二叉树遍历1前序遍历根节点->左子树->右子树2中序遍历左子树->根节点->右子树3后序遍历左子树->右子树->根节点二叉树遍历是指按照某种顺序访问树中所有节点的过程。常见的遍历方式包括前序遍历、中序遍历和后序遍历。每种遍历方式都有其独特的访问顺序，用于不同的场景。堆1堆结构堆是一种特殊的二叉树，满足堆性质。2完全二叉树堆是一颗完全二叉树，除了最后一层，其他层都是满的，最后一层节点从左往右排列。3堆性质最大堆：父节点值大于或等于子节点值，最小堆：父节点值小于或等于子节点值。图定义图是一种数据结构，用于表示实体之间的关系。组成图由顶点（节点）和边组成，边连接两个顶点，表示它们之间的关系。类型图可以是有向图或无向图，有向图的边有方向，无向图的边没有方向。应用图广泛应用于各种领域，例如社交网络、交通路线、地图、计算机网络等等。图的遍历1深度优先搜索深度优先搜索(DFS)是一种图遍历算法，它从一个顶点开始，沿着一条路径尽可能深入地遍历图，直到到达一个没有未访问的邻接顶点的顶点，然后回溯到上一个顶点，继续探索其他路径。2广度优先搜索广度优先搜索(BFS)是一种图遍历算法，它从一个顶点开始，首先访问该顶点的所有直接邻居，然后依次访问这些邻居的邻居，以此类推，直到遍历完所有可达顶点。3应用场景图的遍历算法广泛应用于解决各种问题，例如路径规划、社交网络分析、网页爬取等。排序算法冒泡排序相邻元素比较，交换位置，将较大的元素移动到最后，重复操作直到所有元素有序。插入排序将未排序的元素插入到已排序的序列中，维护有序序列，效率较高。归并排序将待排序序列不断拆分为子序列，然后合并排序的子序列，最终得到有序序列。快速排序选择一个基准元素，将大于基准元素的元素放到右边，小于基准元素的元素放到左边，递归排序左右两侧。时间复杂度时间复杂度是指算法运行时间随输入规模增长的变化趋势，用来衡量算法效率。例如，如果算法的运行时间与输入规模呈线性关系，则其时间复杂度为O(n)，表示当输入规模增加一倍时，算法运行时间也增加一倍。