第4章數組2025/6/111

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

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

2025/6/1144.1順序表的特點

3刪除節點

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

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

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

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

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

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

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

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

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