數(shù)據(jù)結構與算法（Python語言版）課件 第4章 數(shù)組VIP

第4章數(shù)組2025/6/111

數(shù)組是Python中非?；A的一種順序存儲的數(shù)據(jù)結構，也被稱為順序表，首先介紹順序表，然后介紹數(shù)組。順序表的特點；

array類；數(shù)組與圍圈留一問題；數(shù)組與參數(shù)存值；數(shù)組與穩(wěn)定排序；二分法與數(shù)組；數(shù)組的相等；數(shù)組與洗牌。4.1順序表的特點2025/6/112順序表也是線性表的一種具體體現(xiàn)，順序表節(jié)點形成的邏輯結構是線性結構、節(jié)點的存儲結構是順序存儲，即節(jié)點的物理地址是依次相鄰的。注意：由于順序表使用數(shù)組實現(xiàn)順序存儲，因此也稱順序表的節(jié)點為元素。2025/6/1134.1順序表的特點順序表使用數(shù)組來實現(xiàn)，順序表的節(jié)點的物理地址是依次相鄰的，因此可以隨機訪問任何一個節(jié)點，不必從頭節(jié)點計數(shù)查找其它節(jié)點。1查詢節(jié)點

2025/6/1144.1順序表的特點

3刪除節(jié)點

4.2array類2025/6/115Python的array模塊（數(shù)組模塊）提供了array類，該array類可為用戶程序實現(xiàn)動態(tài)數(shù)組（屬于順序表結構）。array模塊的array類同時也提供了操作數(shù)組的方法，例如添加元素、插入元素、刪除元素等方法（Python中把獨立的算法稱作函數(shù)，把和類有關的算法稱作方法）。2025/6/1164.2array類1.創(chuàng)建數(shù)組注意：無法動態(tài)指定數(shù)組的大小，即元素的個數(shù)。

使用array模塊的array類的構造函數(shù)array(typecode,initalize)創(chuàng)建數(shù)組時需要指定數(shù)組的元素的類型和初始元素，即指定typecode的具體類型和initalize的具體值。

2025/6/1174.2array類2.數(shù)組的使用3.數(shù)組的長度數(shù)組通過索引來訪問元素，索引從0開始，例如：

使用Python提供的內置len()函數(shù)來獲取數(shù)組的長度。例如：2025/6/1184.2array類4.數(shù)組的引用array數(shù)組屬于引用型變量。如果兩個array數(shù)組具有相同的引用，他們就有完全相同的元素。2025/6/1194.2array類5.數(shù)組的復制可以用已有的數(shù)組arr得到一個新的數(shù)組arr_new，新數(shù)組arr_new和arr的元素值相同，但二者是兩個不同的數(shù)組。2025/6/11104.2array類6.array類的常用方法（1）append(value)：在數(shù)組末尾添加一個新元素2025/6/11114.2array類6.array類的常用方法（2）extend(iterable)：在數(shù)組末尾添加一個可迭代對象中的所有元素（3）insert(index,value)：在指定索引位置插入一個值為value的新元素2025/6/11124.2array類6.array類的常用方法（4）remove(value)：移除數(shù)組中的第一個匹配指定值value的元素（5）pop(index)：移除指定元素并返回該元素的值，如果不指定index的值，即pop()移除尾元素并返回尾元素的值。2025/6/11134.2array類6.array類的常用方法index(value)：從索引開始0開始至數(shù)組最后一個索引查找第一個匹配指定值value的元素的索引（如果沒有找到返回-1）；index(value,start)從索引start開始至數(shù)組最后一個索引查找第一個匹配指定值value的元素的索引（如果沒有找到返回-1）。2025/6/11144.2array類6.array類的常用方法（7）count(value)：返回數(shù)組中指定值value出現(xiàn)的次數(shù)。（8）reverse()：將數(shù)組的元素值反轉。（9）tolist()：返回和數(shù)組有相同元素值的列表。2025/6/11154.2array類7.array數(shù)組的類型array模塊中的數(shù)組類型可以是基本的類型，即類型可以是以下幾種：'b'：有符號字節(jié)(signedchar)'B'：無符號字節(jié)(unsignedchar)'u'：Unicode字符(Py_UNICODE)'h'：有符號短整數(shù)(signedshort)'H'：無符號短整數(shù)(unsignedshort)'i'：有符號整數(shù)(signedint)'I'：無符號整數(shù)(unsignedint)'l'：有符號長整數(shù)(signedlong)'L'：無符號長整數(shù)(unsignedlong)'f'：單精度浮點數(shù)(float)'d'：雙精度浮點數(shù)(double)array模塊中的數(shù)組類型不支持對象，即不能在array數(shù)組中直接存儲Python對象，如字符串、列表、字典等。4.3數(shù)組與圍圈留一問題

圍圈留一是一個古老的問題（也稱約瑟夫問題）：若干個人圍成一圈，從某個人開始順時針（或逆時針）數(shù)到第3個人，該人從圈中退出，然后繼續(xù)順時針（或逆時針）數(shù)到第3個人，該人從圈中退出，以此類推，程序輸出圈中最后剩下的一個人。2025/6/11162025/6/11174.3數(shù)組與圍圈留一問題例子1圍圈留一問題可以簡化為向左旋轉數(shù)組（向右），旋轉數(shù)組兩次即可確定出退出圈中的人，即此時數(shù)組首元素（末尾元素）中的號碼就應該是要退出圈中的人。ch4_1.py

4.4數(shù)組與參數(shù)存值如果兩個數(shù)組的引用相同，那么這兩個數(shù)組的元素就完全相同，因此一個函數(shù)可以將某些數(shù)據(jù)存放在數(shù)組參數(shù)中，那么函數(shù)執(zhí)行完畢，保存在數(shù)組元素中的值一直還存在、不會消失。2025/6/11182025/6/11194.4數(shù)組與參數(shù)存值例子2數(shù)組存放三角形面積ch4_2.pyALG4_2.pyALG4_2.py中的函數(shù)judge_triangle(a,b,c,area)，當a，b，c構成等邊三角形時返回3，將三角形面積存放在數(shù)組area的元素中；當構成等腰（不是等邊）三角形時返回2，將三角形面積存放在數(shù)組area的元素中；當構成普通（不是等邊，也不是等腰）三角形時返回1，將三角形面積存放在數(shù)組area的元素中；當不構成三角形時返回0，將nan（notanumber）存放在數(shù)組area的元素中.2025/6/11204.4數(shù)組與參數(shù)存值例子2出現(xiàn)次數(shù)最多的字母ch4_3.pyALG4_3.pyALG4_3.py中的find_max_count_letters(english,saveCount)函數(shù)返回english中出現(xiàn)次數(shù)最多的字母之一，并將這個字母出現(xiàn)的次數(shù)和他在english中的索引存放到參數(shù)指定的saveCount數(shù)組的元素中。4.5數(shù)組與穩(wěn)定排序2025/6/1121

2025/6/11224.5數(shù)組與穩(wěn)定排序1.sorted(arr)函數(shù)sorted(arr)函數(shù)不會修改原始數(shù)組arr，而是創(chuàng)建一個新的數(shù)組來保存排序結果,并返回新數(shù)組的引用。向sorted(arr,reverse=True或False)傳遞第二個參數(shù)的值是reverse=True，讓sorted()函數(shù)按降序排序。2025/6/11234.5數(shù)組與穩(wěn)定排序2.比較函數(shù)與排序sortd(arr,key=比較函數(shù))：讓數(shù)組arr的元素值按著“比較函數(shù)”的返回值進行排序。讓整數(shù)按個位數(shù)字的大小排序2025/6/11244.5數(shù)組與穩(wěn)定排序3.Lambda表達式與排序2025/6/11254.5數(shù)組與穩(wěn)定排序3.Lambda表達式與排序sortd(arr,key=Lambda)：讓數(shù)組的元素值按著Lambda表達式的返回值進行排序。按整數(shù)平方大小排序2025/6/11264.5數(shù)組與穩(wěn)定排序例子4穩(wěn)定排序與不穩(wěn)定排序ch4_4.py起泡法和插入法是穩(wěn)定排序，而選擇法是不穩(wěn)定排序。不穩(wěn)定排序改變了個位數(shù)字相同的兩個整數(shù)在數(shù)組中的前后位置。排序前263在33的前面，選擇法（不穩(wěn)定）排序后導致263在33的后面。4.6二分法與數(shù)組2025/6/1127

在Python語言中，對于array模塊的數(shù)組arr：numinarr的時間復雜度是O(n)，因為它會遍歷整個數(shù)組來查找元素num。2025/6/11284.6二分法與數(shù)組二分法是成熟的經典算法，所以Python將其作為內置模塊bisect中的一個函數(shù):bisect_left(arr,value)(該函數(shù)使用的是二分法）,如果在有序數(shù)組arr中找到一個元素值是value，該函數(shù)返回此元素的索引，如果沒有找到這樣的元素該返函數(shù)回數(shù)組arr的長度。2025/6/11294.6二分法與數(shù)組例子5用二分法統(tǒng)計數(shù)字出現(xiàn)的次數(shù)ch4_5.py

4.7數(shù)組的相等2025/6/1130兩個數(shù)組可以通過==運算符比較二者是否相等。當兩個數(shù)組arr1、arr2的元素值依次一一對應相等時arr1==arr2表達式的值是True，否則是False。另外，數(shù)組arr1也可以取索引start~end之間的元素(不含end索引的元素)和數(shù)組arr2比較是否相等：arr1[