第4章數(shù)組2025/6/171主要內(nèi)容● 數(shù)組與參數(shù)存值● 數(shù)組與排序● 數(shù)組的二分查找●數(shù)組的復制● 數(shù)組的比較● 數(shù)組與洗牌● 數(shù)組與生命游戲

數(shù)組是最常用的一種線性數(shù)據(jù)結構，數(shù)組一旦被創(chuàng)建，那么數(shù)組的長度（數(shù)組的元素的個數(shù)）就不可以再發(fā)生變化，即不可以對數(shù)組進行刪除，添加或插入操作。關于數(shù)組的算法還是非常多的，比如排序，復制，二分查找，動態(tài)遍歷等。4.1數(shù)組與參數(shù)存值

2025/6/1722025/6/1734.1數(shù)組與參數(shù)存值兩個數(shù)組名指向的地址相同，二者就具有相同的元素。

一個函數(shù)可以將某些數(shù)據(jù)存放在數(shù)組參數(shù)中，那么函數(shù)執(zhí)行完畢，保存在數(shù)組元素的值一直還存在、不會消失。2025/6/1744.1數(shù)組與參數(shù)存值

例子1ch4_1.cpptriangle.cpp2025/6/1754.1數(shù)組與參數(shù)存值例2出現(xiàn)次數(shù)最多的字母例子2ch4_2.cppfindLetters.cpp中的charfindMaxCountLetters(std::stringenglish,intsaveCount[])函數(shù)返回english中出現(xiàn)次數(shù)最多的字母之一，并將這個字母出現(xiàn)的次數(shù)和它在english中的位置索引存放到參數(shù)指定的int型數(shù)組的元素中。findLetters.cpp4.2數(shù)組與排序2025/6/176排序算法是重要的基礎算法。各種排序算法都是非常成熟的算法，C++標準庫中的<algorithm>算法庫提供了快速排序和歸并排序的函數(shù)，編寫程序時直接使用這些函數(shù)即可。2025/6/1774.2數(shù)組與排序1.快速排序

雙軸快速排序不是穩(wěn)定排序。穩(wěn)定排序是指，數(shù)組里大小一樣的數(shù)據(jù)，排序后，保持原始的先后順序不變。起泡法是穩(wěn)定排序，而選擇法是不穩(wěn)定排序?？焖倥判蚴且环N基于遞歸的經(jīng)典排序算法。它的思路是選定一個基準元素，然后把比這個元素小的元素放在它左邊，比它大的元素放在它右邊。再分別對它左邊和右邊的元素進行遞歸處理，直到排序完成。2025/6/1784.2數(shù)組與排序1.快速排序例子3快速排序例子3ch4_3.cppquick_sort.cpp

（1）定義存儲索引的位置的兩個變量left和right，初始值分別是數(shù)組的首元素的索引和數(shù)組的最后一個元素的索引。（2）用pivot存放基準數(shù)（單軸排序的軸點），選擇數(shù)組的首元素作為基準數(shù)pivot，即pivot=arr[left];（3）從right開始，向左遍歷，找到第一個小于等于基準數(shù)的數(shù)，記錄其位置為posRight。（4）從left開始，向右遍歷，找到第一個大于等于基準數(shù)的數(shù)，記錄其位置為posLeft。（5）如果posLeft小于posRight，交換arr[posRight]和arr[posLeft]。（6）交換arr[left]和arr[posLeft]。（7）遞歸地對基準數(shù)左邊和右邊的元素進行快速排序，直到完成排序。2025/6/1794.2數(shù)組與排序2.歸并排序例子4ch4_4.cppstudent.cpp一些人排隊買票，突然有人要求大家按體重重新排隊，那么原來兩位體重相同的人可能希望不改變他倆原始的先后順序，因此就不能用選擇法或std:sort()函數(shù)來排序。如果需要穩(wěn)定排序可以使用<algorithm>庫提供的std:stable_sort()函數(shù),該函數(shù)使用的算法是歸并排序算法，是一種穩(wěn)定的排序算法。choice.cpp

例子4穩(wěn)定排序與不穩(wěn)定排序ch4_4.cpp分別使用choice.cpp中的voidsort_choice()函數(shù)和<algorithm>庫提供的std:stable_sort()函數(shù)排序數(shù)組，演示了不穩(wěn)定排序和穩(wěn)定排序的效果，排序之前，(66,1)在（66,4）的前面（兩者的weight值相同都是66），穩(wěn)定排序后（66,1)仍然在（66,4）的前面，但不穩(wěn)定排序導致（66,4)在（66,1）的前面。2025/6/17104.2數(shù)組與排序2.歸并排序例子5ch4_5.cppmerge.cpp例5歸并排序歸并排序算法如下：（1）將待排序數(shù)組分成兩個子數(shù)組，每個子數(shù)組通過遞歸進行排序。（2）將兩個排好序的子數(shù)組合并成一個有序數(shù)組。merge.cpp給出了歸并排序算法是為了體現(xiàn)遞歸算法的重要性（歸并排序使用了遞歸算法），在實際應用中完全沒必要這樣做，只需要用<algorithm>算法庫提供的std::_stable_sort()函數(shù)即可，讓代碼更加簡練、有效。2025/6/17114.2數(shù)組與排序3.計數(shù)排序例子6ch4_6.cppcounting_sort.cpp例6計數(shù)排序計數(shù)排序算法如下：（1）統(tǒng)計每個整數(shù)出現(xiàn)的次數(shù)：創(chuàng)建一個稱作計數(shù)數(shù)組的int型數(shù)組，其長度是待排序數(shù)組中的最大整數(shù)再加1。遍歷待排序數(shù)組，統(tǒng)計每個整數(shù)出現(xiàn)的次數(shù)，并將統(tǒng)計結果存儲在int型計數(shù)數(shù)組中對應的位置。（2）計算每個整數(shù)的排序位置：遍歷int型計數(shù)數(shù)組，累加前面出現(xiàn)的整數(shù)的次數(shù)，得到每個整數(shù)在排序后的位置。（3）排序臨時數(shù)組：根據(jù)計數(shù)數(shù)組中的統(tǒng)計結果，將每個整數(shù)放到臨時數(shù)組中對應的位置。（4）將臨時數(shù)組復制回原數(shù)組：將臨時數(shù)組中的元素復制回原數(shù)組，完成排序。

2025/6/17124.2數(shù)組與排序4.動態(tài)排序例子7ch4_7.cppcompare.cpp例7動態(tài)排序doublemodf(doublenum,&integer)函數(shù)返回num的小數(shù)部分，并將整數(shù)部分存放到變量integer中。排序時如果需要按照自定義的排序規(guī)則進行排序，可以提供一個自定義的比較函數(shù)作為第三個參數(shù)傳遞給std::sort()或std::stablesort()函數(shù)。ch4_7.cpp在排序數(shù)組時使用compare.cpp中的比較函數(shù)作為第三個參數(shù)傳遞給std::sort()或std::stablesort()函數(shù)，讓std::sort()按著整數(shù)部分的大小降序排序數(shù)組，std::stable_sort()按著小數(shù)部分的大小升序排序數(shù)組。4.3數(shù)組的二分查找2025/6/1713

在開發(fā)程序時可以直接使用binary_search()函數(shù)，不必再像例2-9或例3-6去編寫算法的具體代碼，除非<algorithm>庫的binary_search()函數(shù)無法滿足程序的需求。2025/6/17144.3數(shù)組的二分查找1.二分法例子8ch4_8.cpp

例8用二分法統(tǒng)計數(shù)字出現(xiàn)的次數(shù)2025/6/17154.3數(shù)組的二分查找2.過濾數(shù)組例子9ch4_9.cppfilter_data.cppfilter_data.cpp中的int*filter_array(intarr[],intarr_size,intfilter[],intfilter_size)函數(shù)返回一個指向數(shù)組的指針，該指針指向的數(shù)組的元素值是數(shù)組arr經(jīng)過用數(shù)組filter過濾后的數(shù)據(jù)。過濾過程中使用了<algorithm>庫的binary_search()函數(shù)判斷數(shù)組中哪些值不在數(shù)組filter中，然后通過保留不在數(shù)組filter中值完成過濾過程。例子9過濾數(shù)組

有時候想過濾數(shù)組arr，即想去掉數(shù)組arr中的某些值。為了過濾數(shù)組arr，可以用另外一個數(shù)組filer做過濾器，即數(shù)組filer中的元素值都是數(shù)組arr準備去掉的值。4.4數(shù)組的復制2025/6/1716兩個類型相同的數(shù)組，例如數(shù)組a和數(shù)組b，如果將a的值（數(shù)組的地址）賦值給b，那么二者的元素就完全相同了（見4.1節(jié)）。如果想得到一個數(shù)組b，b的元素值和a的相同，但二者的地址不同，就需要使用復制的辦法，即把數(shù)組a的元素值賦值到數(shù)組b的元素中，而不是將a的值賦值給b。。2025/6/17174.4數(shù)組的復制1.復制數(shù)組的函數(shù)例子10ch4_10.cppget_rondom_number.cppstd::copy(source+index_start,source+index_end,destination)std::copy()是C++標準庫中的一個函數(shù),把一維數(shù)組source索引范圍[index_start,index_end)的index_end-index_start多個元素的值賦值到一個新數(shù)組destination中，即復制時包含索引是index_start的元素，但不包含索引是index_end的元素。

例10模擬買福利彩票“雙色球”2025/6/17184.4數(shù)組的復制1.復制數(shù)組的函數(shù)例子11ch4_11.cppleave_one_around.cpp圍圈留一是一個古老的問題（也稱約瑟夫問題）：若干個人圍成一圈，從某個人開始順時針（或逆時針）數(shù)到第3個人，該人從圈中退出，然后繼續(xù)順時針（或逆時針）數(shù)到第3個人，該人從圈中退出，依此類推，程序輸出圈中最后剩下的一個人。圍圈留1問題可以簡化為旋轉數(shù)組（向左或向右旋轉數(shù)組），旋轉數(shù)組2次即可確定出退出圈中的人，即此時數(shù)組首元素中的號碼就應該是要退出圈中的人。leave_one_around.cpp中的leave_one(intpeople[],intpeople_length)函數(shù)通過旋轉數(shù)組確定數(shù)組people中出圈的元素，并用std::copy()函數(shù)保留剩余的元素。例11圍圈留一問題2025/6/17194.4數(shù)組的復制2.處理重復數(shù)據(jù)例子12ch4_12.cpphandle_recurring.cpp有時候需要處理數(shù)組中重復的數(shù)據(jù)，即讓重復的數(shù)據(jù)只保留一個。handle_recurring.cpp中的handle_recurring(intarr[],intresult[],intsize)函數(shù)處理數(shù)組arr中重復的數(shù)據(jù)，result數(shù)組的元素中的數(shù)據(jù)是arr中去掉重復數(shù)據(jù)后的數(shù)據(jù)（重復的數(shù)據(jù)只保留一個）。該函數(shù)使用sdt::copy()函數(shù)將處理后的數(shù)據(jù)保存到一個數(shù)組中，使用std::binary_search()函數(shù)判斷一個數(shù)據(jù)是否是重復的數(shù)據(jù)。例12處理數(shù)組中重復的數(shù)據(jù)4.5數(shù)組的比較2025/6/1720<algorithm>提供了比較兩個一維數(shù)組的boolequals()函數(shù)，假如有一維數(shù)組arr_one和arr_two，那么std::equal(arr_one+start,arr_one+end,arr_two)比較數(shù)組arr_one索引范圍是[start,end）的元素是否依次和數(shù)組arr_two的元素相同，如果相同返回1(true),否則返回0（false）(比較時包含arr_one中索引是start的元素、不包含索引是end的元素)。2025/6/17214.5數(shù)組的比較例子13ch4_13.cppfind_word.cppfind_word.cpp的findWord(Stringstr,Stringword)函數(shù)輸出str中出現(xiàn)的word并返回word出現(xiàn)的次數(shù)。例13尋找單詞并輸出單詞出現(xiàn)的次數(shù)4.6數(shù)組與洗牌2025/6/1722

2025/6/17234.6數(shù)組與洗牌例子14shuffle_card.cpp

ch4_14.cpp例14洗牌算法4.7數(shù)組與生命游戲2025/6/1724生命游戲屬于二維細胞自動機的一種，是英國數(shù)學家JohnHortonConway(約翰.何頓.康威)在1970年發(fā)明的一種特殊二維細胞自動機。將二維平面上的每一個格子看成是一個細胞生命體，每個細胞生命都有“生和死”兩種狀態(tài)，每一個細胞旁邊都有鄰居細胞存在，比如把3*3的9個格子構成的正方形看成一個基本單位的話，那么這個正方形中心的細胞的鄰居就是它旁邊的8個細胞（至多8個）。4.7數(shù)組與生命游戲2025/6/1725一個細胞的下一代的生死狀態(tài)變化遵循下面的生命游戲算法。①細胞周圍有3個細胞為生，下一代該細胞為生（當前細胞若原先為死，則轉為生，若原先為生，則保持不變）。②細胞周圍有2個細胞為生，下一代該細胞的生死狀態(tài)保持不變。③細胞周圍是其它情況，下一代該細胞為死。（即該細胞若原先為生，則轉為死，若原先為死，則保持不變）。2