《Js數(shù)據(jù)結(jié)構(gòu)總結(jié)》課件

JS數(shù)據(jù)結(jié)構(gòu)總結(jié)JavaScript數(shù)據(jù)結(jié)構(gòu)是構(gòu)建復(fù)雜應(yīng)用程序的基礎(chǔ)。了解各種數(shù)據(jù)結(jié)構(gòu)及其應(yīng)用是高效代碼的關(guān)鍵。課程介紹11.學(xué)習(xí)目標(biāo)掌握J(rèn)avaScript數(shù)據(jù)結(jié)構(gòu)的基本概念、應(yīng)用場(chǎng)景和實(shí)現(xiàn)方式。22.課程內(nèi)容從基本數(shù)據(jù)類型到復(fù)雜數(shù)據(jù)結(jié)構(gòu)，涵蓋常用算法和數(shù)據(jù)結(jié)構(gòu)的分析與實(shí)現(xiàn)。33.學(xué)習(xí)方式理論講解與代碼實(shí)踐相結(jié)合，以項(xiàng)目案例的形式鞏固學(xué)習(xí)成果。JavaScript簡(jiǎn)介動(dòng)態(tài)網(wǎng)頁(yè)JavaScript是一種腳本語(yǔ)言，用于創(chuàng)建動(dòng)態(tài)網(wǎng)頁(yè)和Web應(yīng)用程序。交互式體驗(yàn)它使網(wǎng)站能夠響應(yīng)用戶操作，例如鼠標(biāo)懸停、點(diǎn)擊按鈕和表單提交?？蛻舳四_本JavaScript在用戶的瀏覽器中運(yùn)行，而不是服務(wù)器上，因此可以提供快速、流暢的交互體驗(yàn)?；緮?shù)據(jù)類型數(shù)字JavaScript使用64位浮點(diǎn)數(shù)表示數(shù)字。支持整數(shù)和浮點(diǎn)數(shù)。字符串字符串是字符序列。使用單引號(hào)或雙引號(hào)括起來。布爾值布爾值表示真或假，分別用true和false表示?？罩祅ull表示空值，它表示沒有值或不存在的值。引用數(shù)據(jù)類型對(duì)象對(duì)象是一組鍵值對(duì)的集合，表示復(fù)雜數(shù)據(jù)結(jié)構(gòu)。數(shù)組數(shù)組是一組有序的元素集合，可以使用索引訪問。函數(shù)函數(shù)是一段可重復(fù)執(zhí)行的代碼塊，可以接受參數(shù)并返回結(jié)果。變量聲明與賦值聲明變量使用`var`、`let`或`const`關(guān)鍵字聲明變量，并指定變量名稱。賦值使用賦值運(yùn)算符`=`將值分配給已聲明的變量。數(shù)據(jù)類型變量可以存儲(chǔ)不同的數(shù)據(jù)類型，例如數(shù)字、字符串、布爾值、對(duì)象等。作用域變量的作用域決定了變量在代碼中的可見范圍，例如全局變量和局部變量。數(shù)組順序存儲(chǔ)結(jié)構(gòu)數(shù)組是一種線性數(shù)據(jù)結(jié)構(gòu)，元素在內(nèi)存中按順序排列。隨機(jī)訪問可以通過索引直接訪問數(shù)組中的任何元素，速度快。固定大小數(shù)組的大小在創(chuàng)建時(shí)固定，無法動(dòng)態(tài)改變。數(shù)組遍歷1for循環(huán)for循環(huán)是最常用的遍歷方法，它可以精確控制循環(huán)次數(shù)。它適用于已知數(shù)組長(zhǎng)度的情況。2forEach循環(huán)forEach循環(huán)可以方便地遍歷數(shù)組元素，并對(duì)每個(gè)元素執(zhí)行回調(diào)函數(shù)。它不需要預(yù)先知道數(shù)組長(zhǎng)度。3for...in循環(huán)for...in循環(huán)用于遍歷對(duì)象的屬性，它可以訪問數(shù)組元素的索引，但無法直接獲取元素值。數(shù)組方法JavaScript數(shù)組方法JavaScript提供豐富的方法操作數(shù)組，簡(jiǎn)化編程，提高效率。添加和刪除元素push()方法向數(shù)組末尾添加新元素，pop()方法刪除數(shù)組的最后一個(gè)元素。開頭操作unshift()方法在數(shù)組開頭添加新元素，shift()方法刪除數(shù)組的第一個(gè)元素。靈活修改數(shù)組splice()方法允許在指定位置插入或刪除元素，甚至可以替換元素。對(duì)象11.數(shù)據(jù)集合對(duì)象是一組鍵值對(duì)，用于存儲(chǔ)和組織數(shù)據(jù)。鍵是字符串，值可以是任何數(shù)據(jù)類型。22.屬性和方法對(duì)象包含屬性和方法，屬性用于存儲(chǔ)數(shù)據(jù)，方法用于操作數(shù)據(jù)。33.訪問數(shù)據(jù)可以使用點(diǎn)運(yùn)算符或方括號(hào)運(yùn)算符訪問對(duì)象的屬性和方法。44.實(shí)例化可以使用構(gòu)造函數(shù)或字面量創(chuàng)建對(duì)象。對(duì)象遍歷1for...in循環(huán)遍歷對(duì)象所有可枚舉屬性2Object.keys()返回對(duì)象所有可枚舉屬性的鍵3Object.values()返回對(duì)象所有可枚舉屬性的值4Object.entries()返回對(duì)象所有可枚舉屬性的鍵值對(duì)對(duì)象遍歷用于訪問和操作對(duì)象中的屬性。常用的方法包括：for...in循環(huán)，它可以遍歷所有可枚舉屬性；Object.keys()方法可以獲取所有可枚舉屬性的鍵；Object.values()方法可以獲取所有可枚舉屬性的值；Object.entries()方法可以獲取所有可枚舉屬性的鍵值對(duì)。棧后進(jìn)先出棧是一種線性數(shù)據(jù)結(jié)構(gòu)，遵循后進(jìn)先出的原則。新元素添加到棧頂，最先添加的元素在棧底。常見操作棧支持的主要操作包括入棧（push）、出棧（pop）、獲取棧頂元素（peek）和判斷棧是否為空（isEmpty）。應(yīng)用場(chǎng)景棧在函數(shù)調(diào)用、表達(dá)式求值、瀏覽器歷史記錄和撤銷操作等場(chǎng)景中發(fā)揮著重要作用。隊(duì)列先進(jìn)先出隊(duì)列遵循先進(jìn)先出(FIFO)原則，與現(xiàn)實(shí)世界中的排隊(duì)等候類似。入隊(duì)新元素添加到隊(duì)列尾部。出隊(duì)從隊(duì)列頭部移除元素。鏈表定義鏈表是一種線性數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)節(jié)點(diǎn)線性排列，每個(gè)節(jié)點(diǎn)包含數(shù)據(jù)域和指針域，指針指向下一個(gè)節(jié)點(diǎn)。特點(diǎn)鏈表的內(nèi)存地址不連續(xù)，數(shù)據(jù)節(jié)點(diǎn)之間通過指針連接。鏈表可以動(dòng)態(tài)地添加或刪除節(jié)點(diǎn)，但訪問指定節(jié)點(diǎn)需要遍歷。雙向鏈表結(jié)構(gòu)特點(diǎn)每個(gè)節(jié)點(diǎn)包含數(shù)據(jù)、前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)的引用?？梢噪p向遍歷鏈表。插入操作在指定位置插入新節(jié)點(diǎn)，更新前后節(jié)點(diǎn)的引用，操作復(fù)雜度為O(1)。刪除操作刪除指定節(jié)點(diǎn)，更新前后節(jié)點(diǎn)的引用，操作復(fù)雜度為O(1)。應(yīng)用場(chǎng)景實(shí)現(xiàn)LRU緩存、undo/redo操作、音樂播放器等。集合無序集合集合元素沒有順序，集合中不允許重復(fù)元素。數(shù)據(jù)結(jié)構(gòu)集合是一種常用的數(shù)據(jù)結(jié)構(gòu)，用于存儲(chǔ)和管理一組數(shù)據(jù)。數(shù)學(xué)集合集合的概念來源于數(shù)學(xué)，它是一組對(duì)象的集合。字典鍵值對(duì)存儲(chǔ)字典是一種鍵值對(duì)集合，提供高效的數(shù)據(jù)存儲(chǔ)和檢索。快速查找通過鍵直接訪問值，實(shí)現(xiàn)快速查找操作，適用于頻繁查找的場(chǎng)景。靈活應(yīng)用字典在編程語(yǔ)言中廣泛使用，用于存儲(chǔ)配置、數(shù)據(jù)映射等。哈希表11.鍵值對(duì)存儲(chǔ)哈希表使用鍵值對(duì)存儲(chǔ)數(shù)據(jù)，通過鍵快速訪問值。22.哈希函數(shù)哈希函數(shù)將鍵映射到哈希表中的索引位置。33.沖突處理當(dāng)多個(gè)鍵映射到同一個(gè)索引位置時(shí)，需要處理沖突。44.應(yīng)用場(chǎng)景哈希表廣泛應(yīng)用于緩存、數(shù)據(jù)庫(kù)索引、查找等場(chǎng)景。樹樹的概念樹是一種非線性數(shù)據(jù)結(jié)構(gòu)，由節(jié)點(diǎn)組成，節(jié)點(diǎn)之間通過邊連接。樹的節(jié)點(diǎn)之間具有父子關(guān)系，樹的根節(jié)點(diǎn)沒有父節(jié)點(diǎn)，其他節(jié)點(diǎn)只有一個(gè)父節(jié)點(diǎn)。樹的種類樹的種類很多，常用的樹結(jié)構(gòu)包括二叉樹、堆、圖等等。每種樹結(jié)構(gòu)都有各自的特點(diǎn)，適用于不同的場(chǎng)景。二叉樹結(jié)構(gòu)每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)，分別稱為左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。遍歷常用的遍歷方式包括前序遍歷、中序遍歷和后序遍歷。查找根據(jù)節(jié)點(diǎn)的值進(jìn)行查找，找到目標(biāo)節(jié)點(diǎn)或返回空。二叉搜索樹定義二叉搜索樹是一種特殊的二叉樹，每個(gè)節(jié)點(diǎn)的值都大于左子樹中的所有節(jié)點(diǎn)，并且小于右子樹中的所有節(jié)點(diǎn)。它是一種高效的查找數(shù)據(jù)結(jié)構(gòu)，可以快速地進(jìn)行搜索、插入和刪除操作。特點(diǎn)二叉搜索樹支持多種操作，包括查找、插入、刪除、最小值、最大值、前驅(qū)、后繼等。由于二叉搜索樹具有獨(dú)特的結(jié)構(gòu)，因此它在實(shí)現(xiàn)各種算法和數(shù)據(jù)結(jié)構(gòu)中被廣泛應(yīng)用。二叉樹遍歷1前序遍歷根節(jié)點(diǎn)->左子樹->右子樹2中序遍歷左子樹->根節(jié)點(diǎn)->右子樹3后序遍歷左子樹->右子樹->根節(jié)點(diǎn)二叉樹遍歷是指按照某種順序訪問樹中所有節(jié)點(diǎn)的過程。常見的遍歷方式包括前序遍歷、中序遍歷和后序遍歷。每種遍歷方式都有其獨(dú)特的訪問順序，用于不同的場(chǎng)景。堆1堆結(jié)構(gòu)堆是一種特殊的二叉樹，滿足堆性質(zhì)。2完全二叉樹堆是一顆完全二叉樹，除了最后一層，其他層都是滿的，最后一層節(jié)點(diǎn)從左往右排列。3堆性質(zhì)最大堆：父節(jié)點(diǎn)值大于或等于子節(jié)點(diǎn)值，最小堆：父節(jié)點(diǎn)值小于或等于子節(jié)點(diǎn)值。圖定義圖是一種數(shù)據(jù)結(jié)構(gòu)，用于表示實(shí)體之間的關(guān)系。組成圖由頂點(diǎn)（節(jié)點(diǎn)）和邊組成，邊連接兩個(gè)頂點(diǎn)，表示它們之間的關(guān)系。類型圖可以是有向圖或無向圖，有向圖的邊有方向，無向圖的邊沒有方向。應(yīng)用圖廣泛應(yīng)用于各種領(lǐng)域，例如社交網(wǎng)絡(luò)、交通路線、地圖、計(jì)算機(jī)網(wǎng)絡(luò)等等。圖的遍歷1深度優(yōu)先搜索深度優(yōu)先搜索(DFS)是一種圖遍歷算法，它從一個(gè)頂點(diǎn)開始，沿著一條路徑盡可能深入地遍歷圖，直到到達(dá)一個(gè)沒有未訪問的鄰接頂點(diǎn)的頂點(diǎn)，然后回溯到上一個(gè)頂點(diǎn)，繼續(xù)探索其他路徑。2廣度優(yōu)先搜索廣度優(yōu)先搜索(BFS)是一種圖遍歷算法，它從一個(gè)頂點(diǎn)開始，首先訪問該頂點(diǎn)的所有直接鄰居，然后依次訪問這些鄰居的鄰居，以此類推，直到遍歷完所有可達(dá)頂點(diǎn)。3應(yīng)用場(chǎng)景圖的遍歷算法廣泛應(yīng)用于解決各種問題，例如路徑規(guī)劃、社交網(wǎng)絡(luò)分析、網(wǎng)頁(yè)爬取等。排序算法冒泡排序相鄰元素比較，交換位置，將較大的元素移動(dòng)到最后，重復(fù)操作直到所有元素有序。插入排序?qū)⑽磁判虻脑夭迦氲揭雅判虻男蛄兄?，維護(hù)有序序列，效率較高。歸并排序?qū)⒋判蛐蛄胁粩嗖鸱譃樽有蛄?，然后合并排序的子序列，最終得到有序序列?？焖倥判蜻x擇一個(gè)基準(zhǔn)元素，將大于基準(zhǔn)元素的元素放到右邊，小于基準(zhǔn)元素的元素放到左邊，遞歸排序左右兩側(cè)。時(shí)間復(fù)雜度時(shí)間復(fù)雜度是指算法運(yùn)行時(shí)間隨輸入規(guī)模增長(zhǎng)的變化趨勢(shì)，用來衡量算法效率。例如，如果算法的運(yùn)行時(shí)間與輸入規(guī)模呈線性關(guān)系，則其時(shí)間復(fù)雜度為O(n)，表示當(dāng)輸入規(guī)模增加一倍時(shí)，算法運(yùn)行時(shí)間也增加一倍。