《數(shù)組4學時》課件

《數(shù)組4學時》PPT課件contents目錄數(shù)組的基本概念數(shù)組的創(chuàng)建與初始化數(shù)組的遍歷與搜索數(shù)組的排序與查找數(shù)組的應(yīng)用案例數(shù)組的基本概念01CATALOGUE總結(jié)詞描述數(shù)組的基本定義詳細描述數(shù)組是一種用于存儲有序數(shù)據(jù)集合的數(shù)據(jù)結(jié)構(gòu)，它由相同類型的元素組成，每個元素在數(shù)組中都有一個唯一的索引。數(shù)組的定義總結(jié)詞描述數(shù)組的分類方式詳細描述根據(jù)數(shù)組中元素的類型，可以將數(shù)組分為整數(shù)數(shù)組、浮點數(shù)數(shù)組、字符數(shù)組等；根據(jù)數(shù)組的維度，可以將數(shù)組分為一維數(shù)組、二維數(shù)組、三維數(shù)組等。數(shù)組的分類列舉數(shù)組的常用操作總結(jié)詞數(shù)組的操作包括索引、添加、刪除、修改和遍歷等。通過這些操作，可以對數(shù)組中的元素進行訪問、修改和管理。詳細描述數(shù)組的常用操作數(shù)組的創(chuàng)建與初始化02CATALOGUE總結(jié)詞通過直接賦值方式進行數(shù)組的初始化。靜態(tài)初始化是指在聲明數(shù)組時直接為其元素賦值，無需使用循環(huán)或方法調(diào)用。例如，`int[]array={1,2,3,4,5};`。靜態(tài)初始化適用于固定大小的數(shù)組，且在聲明時已經(jīng)知道所有元素的值。由于靜態(tài)初始化在聲明時就需要指定所有元素的值，因此無法在運行時改變數(shù)組的大小。這種初始化方式適用于已知元素值的場景，如常量數(shù)組或預(yù)定義的數(shù)據(jù)集。詳細描述總結(jié)詞詳細描述靜態(tài)初始化總結(jié)詞通過循環(huán)或方法調(diào)用動態(tài)地填充數(shù)組元素。詳細描述動態(tài)初始化是指在程序運行過程中，通過循環(huán)或方法調(diào)用逐個賦值給數(shù)組元素。例如，使用循環(huán)結(jié)構(gòu)如`for`或`while`來遍歷數(shù)組并為其賦值?？偨Y(jié)詞動態(tài)初始化允許在運行時改變數(shù)組的大小。詳細描述由于動態(tài)初始化是在運行時逐個賦值給數(shù)組元素，因此可以在程序運行過程中動態(tài)地改變數(shù)組的大小。這種初始化方式適用于需要根據(jù)某些條件或輸入來填充數(shù)組的場景。01020304動態(tài)初始化總結(jié)詞使用花括號括起來的值列表進行數(shù)組的初始化。詳細描述初始化器列表是一種特殊的靜態(tài)初始化方式，使用花括號`{}`括起來的值列表來初始化數(shù)組。這種初始化方式與靜態(tài)初始化類似，但語法上略有不同。例如，`int[]array={1,2,3};`?？偨Y(jié)詞初始化器列表適用于固定大小的數(shù)組，且在聲明時已經(jīng)知道所有元素的值。詳細描述與靜態(tài)初始化一樣，初始化器列表也需要在聲明時指定所有元素的值，因此無法在運行時改變數(shù)組的大小。這種初始化方式適用于已知元素值的場景，如常量數(shù)組或預(yù)定義的數(shù)據(jù)集。初始化器列表數(shù)組的遍歷與搜索03CATALOGUE逆序遍歷按照數(shù)組元素順序，從尾到頭依次訪問每個元素。順序遍歷按照數(shù)組元素順序，從頭到尾依次訪問每個元素。二分查找法在已排序的數(shù)組中，通過比較中間元素與目標值，逐步縮小查找范圍，直到找到目標值或確定不存在于數(shù)組中。跳躍搜索法通過跳過一定數(shù)量的元素來減少比較次數(shù)，提高搜索效率。線性搜索法從數(shù)組的第一個元素開始，逐個比較每個元素與目標值，直到找到目標值或遍歷完整個數(shù)組。遍歷數(shù)組適用場景已排序的數(shù)組。查找過程將數(shù)組分成左右兩部分，比較中間元素與目標值，如果目標值等于中間元素，則查找成功；如果目標值小于中間元素，則在左半部分繼續(xù)查找；如果目標值大于中間元素，則在右半部分繼續(xù)查找。重復(fù)此過程，直到找到目標值或確定不存在于數(shù)組中。二分查找法O(logn)。時間復(fù)雜度二分查找法要求數(shù)組已排序，否則結(jié)果不準確。注意事項二分查找法適用場景：任何情況下的數(shù)組。查找過程：從頭到尾依次比較每個元素與目標值，直到找到目標值或遍歷完整個數(shù)組。時間復(fù)雜度：O(n)。注意事項：線性搜索法適用于任何情況下的數(shù)組，但當數(shù)組較大時，效率較低。01020304線性搜索法適用場景：已排序的數(shù)組。時間復(fù)雜度：O(n)。注意事項：跳躍搜索法在某些情況下可以提高搜索效率，但并不總是優(yōu)于線性搜索法和二分查找法。同時，跳躍搜索法的實現(xiàn)較為復(fù)雜，容易出錯。查找過程：通過跳過一定數(shù)量的元素來減少比較次數(shù)，從而提高搜索效率。具體實現(xiàn)時，可以每次跳過固定數(shù)量的元素，也可以根據(jù)元素的分布情況動態(tài)調(diào)整跳躍步長。跳躍搜索法數(shù)組的排序與查找04CATALOGUEO(n^2)，其中n是數(shù)組的長度。適用于較小的數(shù)組或部分有序的數(shù)組。冒泡排序法適用場景時間復(fù)雜度O(n^2)，其中n是數(shù)組的長度。時間復(fù)雜度適用于數(shù)據(jù)量較小的情況。適用場景選擇排序法插入排序法O(n^2)，其中n是數(shù)組的長度。時間復(fù)雜度適用于數(shù)據(jù)量較小的情況。適用場景二分查找法時間復(fù)雜度O(logn)，其中n是數(shù)組的長度。適用場景適用于有序數(shù)組的查找操作。數(shù)組的應(yīng)用案例05CATALOGUE冒泡排序通過相鄰元素之間的比較和交換，將較大的元素逐步“冒泡”到數(shù)組的末尾，從而實現(xiàn)排序。選擇排序在未排序的序列中找到最?。ɑ蜃畲螅┰?，存放到排序序列的起始位置，然后再從剩余未排序元素中繼續(xù)尋找最?。ɑ蜃畲螅┰?，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。插入排序?qū)?shù)組分為已排序和未排序兩部分，初始時已排序部分包含一個元素。從未排序部分取出元素，并在已排序部分找到合適的位置插入，并保持已排序部分一直有序。重復(fù)此過程，直到未排序部分元素為空。數(shù)組在排序算法中的應(yīng)用背包問題01給定一組物品，每種物品都有自己的重量和價值，在限定的總重量內(nèi)，求最大價值。可以使用數(shù)組來存儲物品的價值和重量，以及當前的總重量和總價值。最長公共子序列02給定兩個字符串，求它們的最長公共子序列?？梢允褂脛討B(tài)規(guī)劃算法，用一個二維數(shù)組來存儲子問題的解，最終得到最長公共子序列的長度。矩陣鏈乘法03給定一組矩陣和它們的乘法順序，求最小乘法次數(shù)?？梢允褂脛討B(tài)規(guī)劃算法，用一個二維數(shù)組來存儲子問題的解，最終得到最小乘法次數(shù)。數(shù)組在動態(tài)規(guī)劃中的應(yīng)用VS線性表是一種具有固定數(shù)量元素的數(shù)據(jù)結(jié)構(gòu)，可以使用數(shù)組來實現(xiàn)。數(shù)組的每個元素可以存儲線性表中