第五章1 數(shù)組

《第五章1 數(shù)組》由會(huì)員分享，可在線閱讀，更多相關(guān)《第五章1 數(shù)組（13頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、第5章 數(shù)組 作為抽象數(shù)據(jù)類型數(shù)組的類聲明。 ? #ｉnｃｌudｅ 〈ioｓｔreaｍ．h>?? //在頭文件“array．h”中 ? ＃incｌude　〈stdｌｉb．h〉 coｎst iｎt DeｆaultSize = 30; ?? template ＜clasｓ Ｔｙpe＞ cｌass　Array { ／/數(shù)組是數(shù)據(jù)類型相同的n（size)個(gè)元素的一個(gè)集合，　下標(biāo)范圍從0到ｎ－1.對(duì)數(shù)組中元素 ? /／可按下標(biāo)所指示位置直接訪問。 ? private: ? Tｙｐｅ *ｅlｅｍenｔs；? ? ? ?? //數(shù)組 ?? inｔ AｒｒaySizｅ;

2、???? ? //元素個(gè)數(shù) ?ｐublｉc： Array?。?iｎt　Sｉze = DefａultSｉze ）; ??? ?//構(gòu)造函數(shù) ?　 Aｒray?。āonｓｔ Ａrray〈Tyｐｅ> ＆ x )； ?????//復(fù)制構(gòu)造函數(shù) ?? ~Array　( ） ｛ dｅｌete ［ ] elemｅｎts； ｝ ???? ／/析構(gòu)函數(shù) ? 　 Ａｒray〈Typｅ〉 & ｏpｅrator　=?。?coｎｓt Array〈Type〉 ＆　A　)； //數(shù)組整體賦值 （復(fù)制) ?? Typｅ＆ oｐeraｔor [ ] ( int i ）； ? ?? ／/按下標(biāo)

3、訪問數(shù)組元素 ? inｔ　Lenｇth （ ） const ｛ return　ＡrraySizｅ； } ??//取數(shù)組長(zhǎng)度 　　vｏｉd　ReSizｅ　(　inｔ sz ); ???? //修改數(shù)組長(zhǎng)度 ? } ??順序表的類定義 ?＃includｅ ＜ ｉｏｓtreａm.h〉? ? ?/／定義在頭文件“seqｌist.h”中 #iｎclude 〈sｔdlｉb.h〉 ｔemplate <ｃｌass Type〉　ｃlａss ＳeｑLｉｓｔ　{? ? ??priｖaｔe: ? 　 　Type　*ｄata；? ? ?//順序表的存放數(shù)組 ? 　int　M

4、ａxSize;? ? ?/／順序表的最大可容納項(xiàng)數(shù) ? int laｓt;? ????//順序表當(dāng)前已存表項(xiàng)的最后位置 ? 　 ｉnt　current; ? ?／/順序表的當(dāng)前指針(最近處理的表項(xiàng)) publiｃ： ?? ＳeqLiｓt　( int ＭaxSizｅ ）；? ??//構(gòu)造函數(shù) ? 　 　~SeqList (　) {　delete ［ ］　datａ； ｝ ??//析構(gòu)函數(shù) ? ｉnt Length　（ ) const ｛　rｅｔurn ｌａst+1；?。??/／計(jì)算表長(zhǎng)度 　int Ｆiｎd　( Ｔyｐｅ& ｘ ) consｔ；

5、??//定位函數(shù)： 找x在表中位置,置為當(dāng)前表項(xiàng) ??　　?。閚t　IsIｎ （ Ｔｙｐｅ＆ x ）;? ? ?/／判斷x是否在表中，不置為當(dāng)前表項(xiàng) 　 ? 　Tｙpe ＊GetData （ ） ｛　reｔuｒn ｃurrｅnｔ　== —１？ＮULL ： dａｔa［cｕrｒent］； ｝?／／取當(dāng)前表項(xiàng)的值 　 int Insｅrt （　Type& ｘ?。?； ?? //插入ｘ在表中當(dāng)前表項(xiàng)之后,置為當(dāng)前表項(xiàng) iｎｔ Aｐｐend (　Tｙpｅ& x ）；????／/追加x到表尾,置為當(dāng)前表項(xiàng) ?　 Tｙpe ＊ Reｍoｖe ( Type& x )； ??

6、?//刪除ｘ,置下一表項(xiàng)為當(dāng)前表項(xiàng) ? Tyｐe * First?。ā。?； ? ? /／取表中第一個(gè)表項(xiàng)的值,置為當(dāng)前表項(xiàng) 　Type ＊ Next （　) ｛ rｅｔurn ｃurｒｅnｔ 〈　last ？ ＆data[＋+ｃｕｒrｅnt］ ： NUＬＬ；　｝ ? ? //取當(dāng)前表項(xiàng)的后繼表項(xiàng)的值，置為當(dāng)前表項(xiàng) ?　 Tｙpe?。?Pｒioｒ　( ）?。。騟turn ｃurrenｔ　> 0 ? &ｄata[--ｃuｒｒent］ : NＵLL; }? ? ?? //取當(dāng)前表項(xiàng)的前驅(qū)表項(xiàng)的值,置為當(dāng)前表項(xiàng) ?　 iｎt IsEmpｔｙ ( ）　{ rｅ

7、tuｒｎ ｌasｔ ＝＝　—1; }? //判斷順序表空否,　空則返回１;　否則返回0 ?? int ＩsFull （ ） {　return　last　=＝ MａxSｉze—１;　} //判斷順序表滿否,　滿則返回1； 否則返回0 ??} 2-1 設(shè)ｎ個(gè)人圍坐在一個(gè)圓桌周圍，現(xiàn)在從第s個(gè)人開始報(bào)數(shù),數(shù)到第ｍ個(gè)人，讓他出局;然后從出局的下一個(gè)人重新開始報(bào)數(shù),數(shù)到第m個(gè)人，再讓他出局,……,如此反復(fù)直到所有的人全部出局為止。下面要解決的Josｅphus問題是:對(duì)于任意給定的n， s和m，求出這ｎ個(gè)人的出局序列。請(qǐng)以n?。?9， s =　1， ｍ = 5為例,人工模擬Jｏｓephuｓ的求解

8、過程以求得問題的解. 【解答】 出局人的順序?yàn)?， 1， 7, 4, 3, ６， 9, 2,?。?。 2－2　試編寫一個(gè)求解Josｅｐhｕs問題的函數(shù)。用整數(shù)序列1， 2, 3， ……，　n表示順序圍坐在圓桌周圍的人，并采用數(shù)組表示作為求解過程中使用的數(shù)據(jù)結(jié)構(gòu).然后使用n ＝ 9， s ＝　1， m = 5，以及ｎ = 9， s　=　１, m ＝ 0,或者n =　9， ｓ ＝ 1， m = １0作為輸入數(shù)據(jù)，檢查你的程序的正確性和健壯性.最后分析所完成算法的時(shí)間復(fù)雜度。 【解答】函數(shù)源程序清單如下： void Joseｐｈus（ int A[?。? ｉnｔ n, s, m ) {

9、 ?int ｉ, j， k, tmｐ; ? if （ m == 0 ) ｛ cout 〈< "ｍ ＝ 0是無效的參數(shù)！” 〈＜ enｄl； retｕrn； } ｆor ( ｉ = 0； i 〈 ｎ; i++　) A[i］ = ｉ + 1；? ?/＊初始化,執(zhí)行n次*/ ?i = s - 1;? ? ? ／＊報(bào)名起始位置＊/ ? for　（?。搿? n； ｋ　〉 1; i—-　) {??? ?／*逐個(gè)出局，執(zhí)行n-1次*/ if　( i ==　k　) i　= 0; ? ｉ = (　i + m — 1 ） ％ k； ? /*尋找出局位置＊/ iｆ （?。?！

10、＝ k－1　） ｛ tmp =　A[ｉ]；??????/*出局者交換到第ｋ-1位置＊/ ?? 　　for （ j = ｉ； ｊ　〈　k-１；　j+＋ ） A[j］ = Ａ［j+１］; ? Ａ［k—1] =　tmp; ?? } ? } ? fｏr （　k　= ０； k ＜ ｎ /　2；?。?＋ ） { ? ／*全部逆置, 得到出局序列＊/ ?? tmp ＝ Ａ[k]； Ａ[k］ ＝?。粒郏睢猭+1］; Ａ［n-ｋ+1］ ＝ tmp; ? ｝ } 例:n = ９， s　= 1，　m =　5 0　 1 　2 3 4 5 　6 7

11、 8 k = 9 1 2 3 ?。? 5 6 　7 8 　９ 第5人出局, i = 4 k = ８ １ ２ ?。? ?。? ６ 　7 8 9 5 第1人出局， ｉ =　0 k = 7 　2 3 4 6 7 ８ ９ 1 　5 第7人出局, i = 4 k = 6 　2 3 4 6 8 　9 　7 1 　5 第4人出局, ｉ = 2 k = ５ 2 3 ?。? 8 9 4 　7 　1 5 第3人出局, i = １ k = 4

12、 ２ ６ 8 9 3 4 ７ ?。? ５ 第6人出局， i =?。? ｋ = ３ 　2 8 ?。? 　6 3 4 7 １ 5 第9人出局，　i ＝ 2 ｋ = 2 　2 8 9 6 3 ４ 7 　1 5 第2人出局， i =?。? 8 2 9 6 3 4 　7 1 5 第８人出局， i = 0 逆置 　5 1 　7 4 3 6 　9 ２ 　8 最終出局順序 ?例:n =　9， s ＝ １, m ＝ ０ ?報(bào)錯(cuò)信息 　m =

13、?。笆菬o效的參數(shù)！ 例：n　=　9, ｓ　= 1，?。?＝ 10　 　 0 １ ２ 3 4 5 　６ 7 8 k　= 9 1 2 3 4 5 　6 ７ 8 9 第1人出局, i　=?。? k =　8 　2 ３ 　4 5 6 7 8 　9 1 第3人出局，?。?= 1 k =　7 　2 4 ５ 　6 ７ 　8 9 　3 ?。? 第6人出局, i　= ３ k =　6 2 4 5 　7 8 ９ ６ ３ 　1

14、 第2人出局， i　= ０ k =　5 ４ 5 7 ８ ９ ?。? 6 3 １ 第9人出局, ｉ ＝　4 k?。?４ 　4 5 ７ ８ ９ 2 6 ?。? 1 第5人出局， i = 1 ｋ = 3 ４ 7 　8 5 9 2 ６ 3 1 第7人出局,?。椤? 1 k　=　2 ４ 　8 7 5 9 　２ 6 ３ 1 第4人出局, i　= 0 　8 ４ 7 5 9 2 ?。? 　3　 　1 第8人出局， i = 0 逆置

15、 ?。? 3 ６ 2 9 ５ 7 4 　8 最終出局順序 當(dāng)m = 1時(shí)，時(shí)間代價(jià)最大。達(dá)到( n—１ ） + ( n-２ ）?。?????? + １ = n（ｎ-1)/2　? O(ｎ2)。 ２—３　設(shè)有一個(gè)線性表?。╡0， e1，　…， ｅn－２， eｎ—1) 存放在一個(gè)一維數(shù)組A[ａrraｙＳize］中的前n個(gè)數(shù)組元素位置。請(qǐng)編寫一個(gè)函數(shù)將這個(gè)線性表原地逆置,即將數(shù)組的前ｎ個(gè)原址內(nèi)容置換為　(ｅn－１,　eｎ—2, …, ｅ1,　e０)。 【解答】 ?ｔｅmｐlａt(yī)e<ｃlass　Typｅ＞　ｖoｉd inverｓe　( Typｅ A[ ],　iｎ

16、ｔ n　） { ?Ｔype tｍｐ; ?foｒ (　int i = 0； i　〈= ( n－1 ） ／ ２; i++　) ｛ ?ｔmp ＝　A[i］； A[i] = A［ｎ-ｉ－1］; 　A[n—ｉ—1] ＝ tｍｐ; ｝ ?} 2-4 假定數(shù)組A［aｒraySizｅ］中有多個(gè)零元素， 試寫出一個(gè)函數(shù)， 將Ａ　中所有的非零元素依次移到數(shù)組A的前端A[ｉ］（0￡ i ￡　ａrｒａySize）。 【解答】 因?yàn)閿?shù)組是一種直接存取的數(shù)據(jù)結(jié)構(gòu),在數(shù)組中元素不是像順序表那樣集中存放于表的前端，而是根據(jù)元素下標(biāo)直接存放于數(shù)組某個(gè)位置,所以將非零元素前移時(shí)必須檢測(cè)整個(gè)數(shù)組空間

17、，并將后面變成零元素的空間清零。函數(shù)中設(shè)置一個(gè)輔助指針free，指示當(dāng)前可存放的位置，初值為0。 ?tempｌate ：：　coｍpact( ) { 　　int?。鎟ee = 0; fｏr （ int i　= 0； i <　ArraySize； i++ )? ? ?//檢測(cè)整個(gè)數(shù)組 ?ｉf (　elementｓ［I］ !=?。?） ?? ?／/發(fā)現(xiàn)非零元素 ? ?。lemｅｎtｓ［frｅｅ]　=　elｅments[i］；　 frｅe(cuò)＋+;　 elemｅnｔs［ｉ］　= 0; ｝?//前移 } ?

18、2—5 順序表的插入和刪除要求仍然保持各個(gè)元素原來的次序。設(shè)在等概率情形下, 對(duì)有１27個(gè)元素的順序表進(jìn)行插入， 平均需要移動(dòng)多少個(gè)元素？ 刪除一個(gè)元素， 又平均需要移動(dòng)多少個(gè)元素？ 【解答】 ?若設(shè)順序表中已有n ＝ lasｔ+1個(gè)元素，lasｔ是順序表的數(shù)據(jù)成員，表明最后表項(xiàng)的位置。又設(shè)插入或刪除表中各個(gè)元素的概率相等，則在插入時(shí)因有n+1個(gè)插入位置（可以在表中最后一個(gè)表項(xiàng)后面追加），每個(gè)元素位置插入的概率為1/（n+1），但在刪除時(shí)只能在已有n個(gè)表項(xiàng)范圍內(nèi)刪除,所以每個(gè)元素位置刪除的概率為１／n。 插入時(shí)平均移動(dòng)元素個(gè)數(shù)AＭN(Ａveragｙ Movｉｎｇ Ｎumｂer ）為

19、刪除時(shí)平均移動(dòng)元素個(gè)數(shù)AMＮ為 2－6 若矩陣Am′n中的某一元素A[i］［j］是第ｉ行中的最小值，同時(shí)又是第ｊ列中的最大值，則稱此元素為該矩陣的一個(gè)鞍點(diǎn).假設(shè)以二維數(shù)組存放矩陣,試編寫一個(gè)函數(shù),確定鞍點(diǎn)在數(shù)組中的位置（若鞍點(diǎn)存在時(shí))，并分析該函數(shù)的時(shí)間復(fù)雜度。 【解答】 ?iｎt ｍinmａx （ int?。粒?］［ ］, coｎst iｎt ｍ， const iｎｔ　n ） ｛ //在二維數(shù)組A［m]［n]中求所有鞍點(diǎn)， 它們滿足在行中最小同時(shí)在列中最大 int *row =　new ｉnｔ［m]； 　inｔ ＊ cｏl　＝　neｗ　iｎｔ［ｎ］; ? 　 int i

20、，　j; ? 　fｏr （ i = 0;　ｉ ＜ ｍ; i++ ）　{? ?／/在各行中選最小數(shù)組元素， 存于roｗ［ｉ］ ? ｒoｗ［ｉ] = A［i］[0]; 　 ? for?。ā = 1；　j?。?n; ｊ++ ) ｉf ( A[i］[ｊ] < rｏw［ｉ] ) rｏw［i]　= A[ｉ］［j］； ?　 } ? 　 for （?。?= 0; ｊ 〈 ｎ； j+＋ ）?。? ??/／在各列中選最大數(shù)組元素，　存于col［j］ ??。悖飈[i］ = A［0］［j］；?　　 　foｒ （　i = 1；　i　< m； i+＋ ）

21、 ｉf　( A[ｉ］［ｊ]　〉 ｃol［j] ） col[j］ =　A［ｉ］[j]； 　 ｝ 　 for （　i?。?0; i　＜ m; ｉ+＋?。?{?? ? ／/檢測(cè)矩陣，尋找鞍點(diǎn)并輸出其位置 ? 　for　( j =　0； j ＜ n；　j++　） ? ｉｆ ( ｒow[i] ＝＝　col［j] ） couｔ <＜ “The ｓaｄｄｌｅ ｐoint is?。骸?” ＜〈 ｉ　〈< “,　"　〈＜?。?<<　“）” 〈〈 endl； ? deｌｅtｅ ［ ]　row；　?。鋏ｌete?。?]　cｏl;　 } 此算法有3個(gè)并列二重循環(huán)，其時(shí)間復(fù)雜度

22、為O（m′n). ２－7 設(shè)有一個(gè)二維數(shù)組A[m]［ｎ］,假設(shè)Ａ[0］[０］存放位置在644（10)，A［2］[２］存放位置在６76(１0），每個(gè)元素占一個(gè)空間，問Ａ［３]［3］(10)存放在什么位置？腳注（10)表示用10進(jìn)制表示. 【解答】 設(shè)數(shù)組元素A[i]［j］存放在起始地址為L(zhǎng)oc （ i， ｊ ） 的存儲(chǔ)單元中。 ∵ Loc （ ２，　2 ） = Loc （ ０， 0 ）?。?2 * n　+ ２　= 644 +　2 ＊ n　＋　2 ＝?。叮罚叮? ∴ n =　( 676 - 2 － 644 ）　/　２　= 15 ∴ Ｌoｃ (　3, 3 )　= Loc （ 0， 0?。?

23、+ 3　* 1５　+　3 =　644 +　45　+ 3 ＝ 69２． 2-8 利用順序表的操作,實(shí)現(xiàn)以下的函數(shù)。 ?(1）　從順序表中刪除具有最小值的元素并由函數(shù)返回被刪元素的值?？粘龅奈恢糜勺詈笠粋€(gè)元素填補(bǔ)，若順序表為空則顯示出錯(cuò)信息并退出運(yùn)行?！? (2） 從順序表中刪除第i個(gè)元素并由函數(shù)返回被刪元素的值。如果i不合理或順序表為空則顯示出錯(cuò)信息并退出運(yùn)行。 ?(3) 向順序表中第ｉ個(gè)位置插入一個(gè)新的元素x。如果i不合理則顯示出錯(cuò)信息并退出運(yùn)行。 ?(4）　從順序表中刪除具有給定值ｘ的所有元素。 ?(5） 從順序表中刪除其值在給定值s與t之間(要求s小于t)的所有元素，如果s或t

24、不合理或順序表為空則顯示出錯(cuò)信息并退出運(yùn)行。 (６） 從有序順序表中刪除其值在給定值s與t之間(要求ｓ小于ｔ）的所有元素，如果s或t不合理或順序表為空則顯示出錯(cuò)信息并退出運(yùn)行。 ?(7)　將兩個(gè)有序順序表合并成一個(gè)新的有序順序表并由函數(shù)返回結(jié)果順序表。 （8） 從順序表中刪除所有其值重復(fù)的元素，使表中所有元素的值均不相同。 【解答】 (１) 實(shí)現(xiàn)刪除具有最小值元素的函數(shù)如下： templａt(yī)e :： DｅlMin （ ）　{ 　　 if?。?last ＝＝ -1 ) ? ?????//表空, 中止操作返回 {　cｅr

25、r <＜　“ Lｉｓt iｓ Eｍｐtｙ！ ”　〈< ｅndl； ｅｘiｔ(１）; ｝ 　 　int m = 0； ? ? ??／/假定０號(hào)元素的值最小 fｏr ( int?。?＝　1； i　<＝ ｌasｔ;　i+＋ ） {????//循環(huán), 尋找具有最小值的元素 ? ｉf?。?data[i] 〈 data［m］　） ｍ ＝ ｉ； ? ?//讓m指向當(dāng)前具最小值的元素 Tyｐe?。鬳mp = dａt(yī)ａ[m］； datａ［m］ = data［lａｓt]； ｌast——； ? ?/／空出位置由最后元素填補(bǔ), 表最后元素位置減1 ? 　 ｒetuｒ

26、ｎ　teｍp； ?｝ （2）　實(shí)現(xiàn)刪除第i個(gè)元素的函數(shù)如下（設(shè)第i個(gè)元素在data［i］， i=0，1，?,ｌａｓt）: ｔｅmplate〈Ｔyｐｅ〉　Tｙｐe ＳeqＬist〈Type> :： DelNo＃i?。āｎt?。?) ｛ 　iｆ?。?ｌasｔ == -1 ｜| ｉ <　0 ｜| ｉ　〉　last )　 ?//表空,　或i不合理，　中止操作返回 ｛　ceｒr 〈＜ “ Liｓt ｉｓ Empty ｏｒ?。衋ｒamｅｔer　is out rａnｇe！ ” ＜＜ endl; 　eｘit(1);　｝ 　 Type temp = data［i］；? ? ?

27、?／/暫存第ｉ個(gè)元素的值 ｆor ( int j　＝　i；　j 〈　last；　ｊ＋+ ）　? ??//空出位置由后續(xù)元素順次填補(bǔ) datａ［ｊ] =?。洌醫(yī)a[ｊ+1]； ｌａst－-； ? ???/／表最后元素位置減1 retｕｒn tｅmp； ｝ （３） 實(shí)現(xiàn)向第i個(gè)位置插入一個(gè)新的元素x的函數(shù)如下(設(shè)第i個(gè)元素在dａt(yī)ａ[i］， i＝0,1，?，last)： ?ｔeｍｐlate〈Typｅ〉 ｖｏiｄ SeqLisｔ

28、ze-1｜｜ ｉ 〈 ０ ｜｜ i 〉　lasｔ+１ ) ?//表滿或參數(shù)i不合理,　中止操作返回 ? ｛ cｅrr ＜< “ List is Fuｌl or Parａmeter iｓ　out range！　” <＜ eｎdｌ; ?。鍃it(1); ｝ 　　 fｏr （　int　j = lａsｔ; j >＝　i；?。辏? ） ? //空出位置以便插入, 若ｉ=last＋１， 此循環(huán)不做 　?。鋋ta［j＋1］ = data［j］； 　　 ｄata［i］ = x； ??? /／插入 　 lasｔ+＋；　 ?? ???//表最后元素位置加1 ?} ?（4)

29、 從順序表中刪除具有給定值x的所有元素。 tｅmpｌatｅ〈Tｙpe> void ＳｅqＬist〈Tyｐｅ〉 ：： DelValue （ Tｙpｅ＆ x ） { 　 　int i = 0, j; while　( i 〈= ｌast ） ??????/／循環(huán)， 尋找具有值x的元素并刪除它 ? if ( ｄaｔa[i] == x )　{ ??//刪除具有值x的元素, 后續(xù)元素前移 for ( j = i；　j

30、lse i++； ｝ ?（５）　實(shí)現(xiàn)刪除其值在給定值s與t之間(要求s小于t）的所有元素的函數(shù)如下: tｅmplate＜Type＞ void　SeqList〈Ｔype> :：?。膃lNo＃ｓｔo#ｔ (?。詙ｐe&?。?， Tyｐe& t ）　｛ 　if (　lａst　== -1　||?。?＞= t ）　 　｛ ｃｅrr 〈< “Lisｔ ｉｓ empｔy or paraｍetｅrｓ are　illegaｌ！" <〈 ｅnｄｌ;　 eｘit（1）； ｝ ｉnt i = 0， j;? ? ｗｈile　（ i ＜＝ ｌａst　) ?? ??//循環(huán)，　尋找具有值x的元

31、素并刪除它 ? iｆ　( daｔａ［ｉ] ＞= s　&＆ datａ［ｉ] <＝ ｔ　) ｛ ?//刪除滿足條件的元素, 后續(xù)元素前移 for?。ā = i;?。?< lasｔ; j＋+ ） daｔa[j]　= daｔa［j+1]; last——； ? ???? /／表最后元素位置減１ ??　 } else i+＋; ｝ ?（6） 實(shí)現(xiàn)從有序順序表中刪除其值在給定值s與t之間的所有元素的函數(shù)如下： tｅｍplate〈Tｙpe＞　ｖoｉd?。觘qList＜Type＞ ：： DｅlNo#ｓto#t１　(　Type& ｓ, Ｔypｅ&　t?。 ?。閒 （

32、　ｌaｓt ＝＝?。?|| ｓ >=　ｔ ) ｛ cerr <〈 “Liｓt ｉs empty or parameters arｅ ｉｌlegaｌ！” ＜〈 eｎｄｌ；　 exit（1); ｝ ?。鎜r （ iｎt i =　0; i <＝ laｓt； ｉ++ ） ??? //循環(huán),　尋找值 ≥s 的第一個(gè)元素 ? if ( datａ［ｉ］ 〉＝ s ） breａｋ； ? ?? //退出循環(huán)時(shí)， i指向該元素 　 if ( i ＜=　last ） { 　　for ( int　j =　1； i　+ ｊ　〈= last; j+＋ )? ?／／循環(huán), 尋找值?。?t 的第一

33、個(gè)元素 if （ ｄata[i+ｊ］?。?t?。?breaｋ; ? //退出循環(huán)時(shí)， ｉ+j指向該元素 　 foｒ （　iｎt k = ｉ+j； k 〈= last; k++ ) ?/／刪除滿足條件的元素, 后續(xù)元素前移 data[k－ｊ］?。?datａ[k]； 　lａst-＝ j； 　??? ? //表最后元素位置減j ? 　 ｝ ｝ （7） 實(shí)現(xiàn)將兩個(gè)有序順序表合并成一個(gè)新的有序順序表的函數(shù)如下： tｅmplａt(yī)ｅ〈Ｔyｐe〉 SｅqList　::　Ｍerge (?。觘ｑLiｓt〈Tｙpｅ〉＆　Ａ，?。樱錻List

34、〈Tyｐe＞& B　) { /／合并有序順序表A與Ｂ成為一個(gè)新的有序順序表并由函數(shù)返回 　 ?。閒?。?A．Length（） + B.Lengtｈ（)　＞　MaｘSiｚe ) 　{ cｅrr 〈＜ “The ｓｕmmarｙ　of Ｔhe ｌｅnｇtｈ ｏf?。蘨sｔs ｉs out MaxSize！” 〈< endｌ； eｘｉｔ(１)； } 　　Typｅ vａluｅ１ = A.Fist （　)， vaｌｕｅ２ ＝ B.Fｉｓrt （ ）; ?。閚ｔ i?。?０， j　= ０, k　=?。?； 　?。鱤ile ( i 〈 A．ｌｅngth （　)　＆&　j 〈 B.leng

35、th ( ） ） ｛ /／循環(huán),　兩兩比較, 小者存入結(jié)果表 ｉｆ ( value１ <= ｖａlue2 ） {　data[k] = valｕe1； vａｌuｅ1 = A。Next?。?)； i++； ｝ elsｅ ｛ dａt(yī)a[k] = valｕe2； value２ = B．Nｅxt (　）； j++； ｝ ｋ＋+; ? 　｝ 　 wｈilｅ ( i　< A.Lｅngth　( )　) ? ?//當(dāng)A表未檢測(cè)完，　繼續(xù)向結(jié)果表傳送 ｛ data[k] = value1； 　value1 = Ａ．Nｅｘt （ ); 　i+＋; ｋ+

36、＋；　} ?? wｈｉｌe （ j 〈 B.Leｎgtｈ （ ） ） ? ??/／當(dāng)B表未檢測(cè)完, 繼續(xù)向結(jié)果表傳送 { ｄatａ[k] ＝ vａlue2; vａｌuｅ２ = B。Next (　); j++； k++； ｝ ? 　last = ｋ – １； ? 　　reｔurn ＊ｔhis； } （８) 實(shí)現(xiàn)從表中刪除所有其值重復(fù)的元素的函數(shù)如下： templａｔe<Ｔｙｐｅ〉 vｏｉd SｅqLiｓt〈Ｔype＞　:： DｅlDｏｕｂle?。?） { 　 ｉｆ （ lａsｔ ＝= -1 ) 　{ cｅｒr　〈〈 “Liｓt ｉｓ ｅｍpty!”

37、<<　eｎｄl； ｅxit（1)；　} ｉｎt ｉ = ０, j, k； Ｔｙｐe temp; 　 wｈile ( i　<＝ lasｔ ） {? ? ?//循環(huán)檢測(cè) j = i + 1; temp ＝ daｔa［ｉ]； 　 while　(　j ＜= laｓt ） ｛??? //對(duì)于每一個(gè)ｉ， 重復(fù)檢測(cè)一遍后續(xù)元素 iｆ　（ ｔemp == ｄatａ［j]?。?{?? ? ／／如果相等，　后續(xù)元素前移 　for （ k = ｊ＋１; k　<＝ laｓt； k++ ） datａ［ｋ－1]　=　data［k]; 　? 　 last-－; ?

38、? /／表最后元素位置減1 } elsｅ j++； }　 i++； ???/／檢測(cè)完dａt(yī)a［i］， 檢測(cè)下一個(gè) ? ｝ ｝ ２—9 設(shè)有一個(gè)ｎ′n的對(duì)稱矩陣A，如圖（a)所示。為了節(jié)約存儲(chǔ)，可以只存對(duì)角線及對(duì)角線以上的元素，或者只存對(duì)角線或?qū)蔷€以下的元素。前者稱為上三角矩陣，后者稱為下三角矩陣。我們把它們按行存放于一個(gè)一維數(shù)組Ｂ中，如圖（ｂ）和圖(c)所示。并稱之為對(duì)稱矩陣A的壓縮存儲(chǔ)方式.試問: ?(１) 存放對(duì)稱矩陣A上三角部分或下三角部分的一維數(shù)組B有多少元素？ (2） 若在一維數(shù)組Ｂ中從0號(hào)位置開始存放，則如圖(ａ）所示的對(duì)稱矩陣

39、中的任一元素aiｊ在只存上三角部分的情形下（圖（b））應(yīng)存于一維數(shù)組的什么下標(biāo)位置？給出計(jì)算公式。 （3) 若在一維數(shù)組B中從0號(hào)位置開始存放,則如圖(a）所示的對(duì)稱矩陣中的任一元素ａij在只存下三角部分的情形下(圖（c））應(yīng)存于一維數(shù)組的什么下標(biāo)位置？給出計(jì)算公式. 【解答】 ?（１)　數(shù)組B共有ｎ ＋ ( n-１ ) +?????? +　1= n * (　n+1 ) / 2個(gè)元素。 （2)　只存上三角部分時(shí)，若i　￡ j,則數(shù)組元素A［i］[j］前面有i—１行（1~i—１，第0行第０列不算),第1行有n個(gè)元素，第2行有ｎ—1個(gè)元素,??????,第i—1行有n—i＋2個(gè)元素。

40、在第ｉ行中，從對(duì)角線算起，第j號(hào)元素排在第j-i+1個(gè)元素位置（從１開始)，因此,數(shù)組元素A［i］［j］在數(shù)組B中的存放位置為 ??n ＋ (ｎ—1) +　（n－2） +　?????? +　(ｎ－i+2） + j-i+1　 ＝?。?ｎ－i＋２） *?。ǎ椋?) ／ ２ + ｊ－i+１ = (2n-i） * （i—1） /　2 + j 若i 〉 j，數(shù)組元素Ａ［i］［j］在數(shù)組Ｂ中沒有存放,可以找它的對(duì)稱元素Ａ［j］[i]。在 數(shù)組B的第?。?n—j）?。。╦—1) / 2 ＋ i位置中找到。 ?如果第0行第0列也計(jì)入,數(shù)組B從０號(hào)位置開始存放，則數(shù)組元素A[i][ｊ]在數(shù)組B

41、中的存放位置可以改為 ??當(dāng)ｉ ￡ j時(shí)，= (2ｎ—ｉ+1) ＊ i　／ 2 + j　- i?。健。?２n — i　－ 1 ) * i / 2 + j ?當(dāng)ｉ > j時(shí)，= (2n　- ｊ?。?1） * j / 2　+ ｉ 　 ?（3）　只存下三角部分時(shí),若i 3　j，則數(shù)組元素A[i][ｊ］前面有i－１行(1~ｉ-1，第0行第0列不算）,第1行有1個(gè)元素，第2行有2個(gè)元素，??????,第i－1行有i－1個(gè)元素。在第i行中，第j號(hào)元素排在第ｊ個(gè)元素位置，因此,數(shù)組元素A［i][j]在數(shù)組B中的存放位置為 ??1 ＋ ２ +　?????? +?。╥—1） + j ＝ ( i—1）

42、*i　/ 2　+　j 若i 〈 j，數(shù)組元素Ａ［i］[ｊ]在數(shù)組B中沒有存放，可以找它的對(duì)稱元素Ａ[j][i］。在 數(shù)組B的第 (j-1）＊j?。?２ ＋ i位置中找到。 ?如果第0行第０列也計(jì)入,數(shù)組B從０號(hào)位置開始存放，則數(shù)組元素Ａ［i]［j］在數(shù)組B中的存放位置可以改為 ? 當(dāng)i　3 j時(shí)，= i*(i＋1）　/ 2 + j 當(dāng)i 〈　j時(shí),= j＊(ｊ＋1) / 2?。?i 2—10 設(shè)A和B均為下三角矩陣,每一個(gè)都有n行。因此在下三角區(qū)域中各有n（n+１)／2個(gè)元素。另設(shè)有一個(gè)二維數(shù)組Ｃ,它有n行n＋1列。試設(shè)計(jì)一個(gè)方案,將兩個(gè)矩陣A和B中的下三角區(qū)域元素存放于

43、同一個(gè)C中.要求將Ａ的下三角區(qū)域中的元素存放于C的下三角區(qū)域中,B的下三角區(qū)域中的元素轉(zhuǎn)置后存放于Ｃ的上三角區(qū)域中。并給出計(jì)算A的矩陣元素aiｊ和B的矩陣元素bｉｊ在Ｃ中的存放位置下標(biāo)的公式。 【解答】 計(jì)算公式 2—１1 在實(shí)際應(yīng)用中經(jīng)常遇到的稀疏矩陣是三對(duì)角矩陣,如右圖所示。在該矩陣中除主對(duì)角線及在主對(duì)角線上下最臨近的兩條對(duì)角線上的元素外，所有其它元素均為０?，F(xiàn)在要將三對(duì)角矩陣A中三條對(duì)角線上的元素按行存放在一維數(shù)組B中，且a１1存放于B［0］.試給出計(jì)算A在三條對(duì)角線上的元素ａiｊ?。?￡　i ￡ n,　i—1 ￡ ｊ　￡ i＋1)在一維數(shù)組B中的存放位置的計(jì)算公式.

44、 【解答】 在B中的存放順序?yàn)椤?。?1,　a12, ａ２１，　a22，　a２3, a32， ａ３３, a３4， …， an n-１， ann ］，總共有3n—2個(gè)非零元素。元素aｉｊ在第ｉ行,它前面有3(i-1）－1個(gè)非零元素，而在本行中第j列前面有j—i＋１個(gè)，所以元素ａij在B中位置為2*i＋j-３. 2-12　設(shè)帶狀矩陣是ｎ′n階的方陣,其中所有的非零元素都在由主對(duì)角線及主對(duì)角線上下各b條對(duì)角線構(gòu)成的帶狀區(qū)域內(nèi),其它都為零元素。試問： ?(1） 該帶狀矩陣中有多少個(gè)非零元素? (2）　若用一個(gè)一維數(shù)組Ｂ按行順序存放各行的非零元素，且設(shè)ａ１1存放在B[0］中,請(qǐng)給出

45、一個(gè)公式,計(jì)算任一非零元素aij在一維數(shù)組B中的存放位置。 【解答】 （１) 主對(duì)角線包含ｎ個(gè)非零元素，其上下各有一條包含n-1個(gè)非零元素的次對(duì)角線,再向外,由各有一條包含n—2個(gè)非零元素的次對(duì)角線，……，最外層上下各有一條包含ｎ-ｂ個(gè)非零元素的次對(duì)角線。則總共的非零元素個(gè)數(shù)有 ｎ +?。玻ǎ?1)　+　2（n—2） + … + 2（n-b） = n　+ 2（ (n-1）　+ （n－2 ） ＋ …　+ （ｎ－ｂ) ） (２）　在用一個(gè)一維數(shù)組B按行順序存放各行的非零元素時(shí),若設(shè)b≤n/２,則可按各行非零元素個(gè)數(shù)變化情況，分3種情況討論。 ①　當(dāng)1≤ｉ≤b+1時(shí),矩陣第1行有ｂ+１個(gè)

46、元素,第2行有b+2個(gè)元素，第3行有b＋3個(gè)元素,……,第i行存有b+i個(gè)元素，因此,數(shù)組元素A［i］[j］在B［ ］中位置分析如下: ?第ｉ行（ｉ≥1）前面有i—1行，元素個(gè)數(shù)為 （b+1)+（b+2）＋…+(ｂ+ｉ—1)　= (i—1）＊b+i＊（i—１）/２,在第i行第j列(ｊ≥１）前面有j—1個(gè)元素，則數(shù)組元素A[i］[j]在B［　]中位置為 ②　當(dāng)b+1

47、步減少。當(dāng)i=n—b+1時(shí)有2b個(gè)非零元素,當(dāng)i=ｎ—b+2時(shí)有2b-1個(gè)非零元素,當(dāng)i=n—b+3時(shí)有2ｂ-２個(gè)非零元素,…，當(dāng)ｉ=n時(shí)有b＋１個(gè)非零元素。因?yàn)榍懊鎛—ｂ行總共有ｂ＊（3＊b+1)/2+（n—2*b）＊(2＊b+１）個(gè)非零元素，所以在最后各行數(shù)組元素A[i］［j]在B［ ］中位置為 ２－1３ 稀疏矩陣的三元組表可以用帶行指針數(shù)組的二元組表代替。稀疏矩陣有多少行，在行指針數(shù)組中就有多少個(gè)元素:第i個(gè)元素的數(shù)組下標(biāo)i代表矩陣的第i行,元素的內(nèi)容即為稀疏矩陣第i行的第一個(gè)非零元素在二元組表中的存放位置。二元組表中每個(gè)二元組只記錄非零元素的列號(hào)和元素值,且各二元組按行號(hào)遞

48、增的順序排列。試對(duì)右圖所示的稀疏矩陣,分別建立它的三元組表和帶行指針數(shù)組的二元組表。 二元組表 ｄａt(yī)a cｏｌ vaｌue 0 0 １2 1 2 11 2 5 13 3 6 14 4 1 —4 5 5 3 6 3 8 7 １ —9 8 4 2 行指針數(shù)組 row 0 0 1 3 ２ 4 3 6 4 7 5 7 【解答】 ２－14 字符串的替換操作rｅplaｃｅ (Ｓｔring &ｓ， Strｉng?。，　Striｎｇ ＆v）是指:若ｔ是s的子串,則用串v替換串

49、t在串ｓ中的所有出現(xiàn);若t不是s的子串，則串s不變.例如，若串s為“ａabbabcbaabaaacbaｂ”,串t為“bab",串v為“abdc",則執(zhí)行rｅpｌaｃｅ操作后,串s中的結(jié)果為“ａababdｃcｂａabaaaｃａbｄｃ”。試?yán)米址幕具\(yùn)算實(shí)現(xiàn)這個(gè)替換操作。 【解答】 Stｒing ＆?。觮rinｇ :：　Replace （ Ｓtrinｇ　＆ ｔ， String ＆v) ｛ if　( ( ｉnt iｄ　＝ Find　( t ） ） =＝ －1 ) ? /／沒有找到，當(dāng)前字符串不改，返回 { cout 〈〈 ＂Ｔhe (replace）?。铮餰ratiｏn fａi

50、led．"　<＜ endｌ； 　returｎ *thｉs; } 　 Strｉng　temp（ ch ）; ? ?//用當(dāng)前串建立一個(gè)空的臨時(shí)字符串 ch[０] =　’\0’; 　curLen ＝ ０;? ???／/當(dāng)前串作為結(jié)果串,初始為空 int j， k　= 0， l;?? ? ?//存放結(jié)果串的指針 ?? while (　id != －1　） ｛? ? ｆｏr ( j = 0； j 〈 iｄ； j+＋） ch[k＋＋] = temp.ch［j]; ／／摘取temp.ch中匹配位置 ?　iｆ　(　cｕrLen+ id ＋ ｖ。curLen <= maxLen　）

51、 　　 ｌ　=?。觯甤urLen; ?? ?/／確定替換串v傳送字符數(shù)l ??　elsｅ ｌ = ｍaｘLen－ cｕｒLen- iｄ; ? for （ j =　0; j　〈 ｌ; j++ ） ch［k＋+］ =　ｖ。cｈ［j];? //連接替換串ｖ到結(jié)果串ch后面 ??　curLen ＋＝ id ＋ l;?? ? /／修改結(jié)果串連接后的長(zhǎng)度 ｉf (　curLen =＝ ｍaxLen ）　bｒeａk;????/／字符串超出范圍 ?? for （ j　= id ＋ t.cｕrＬen;　j 〈 tｅmp.curＬen; j++?。? ｔemｐ.cｈ［j- iｄ －

52、t。cｕrLen］ =　temｐ.ｃh［j]； //刪改原來的字符串?　ｔemp。cuｒLｅn?。?iｄ ＋ ｔ.curLen； ｉｄ = teｍｐ．Find （　t　)；? } 　rｅturn ＊this; ｝ 2—15 編寫一個(gè)算法ｆrequeｎcy，統(tǒng)計(jì)在一個(gè)輸入字符串中各個(gè)不同字符出現(xiàn)的頻度。用適當(dāng)?shù)臏y(cè)試數(shù)據(jù)來驗(yàn)證這個(gè)算法。 【解答】 ?ｉｎclｕde

53、符串,數(shù)組Ａ［ ]中記錄字符串中有多少種不同的字符，C［　]中記錄每 /／一種字符的出現(xiàn)次數(shù)。這兩個(gè)數(shù)組都應(yīng)在調(diào)用程序中定義。k返回不同字符數(shù). ??iｎｔ i,　j， len = s．ｌength( ）; if ( !leｎ ） { ｃout 〈〈 ＂Ｔｈe ｓtｒing ｉs emptｙ. " 〈＜　eｎｄｌ; ?。搿? 0； reｔuｒn； } ??else ｛ A［0］ = ｓ［０]; Ｃ［0] = １; k = １；?? 　 　 ?/＊語句s［i]是串的重載操作*／ 　fｏr （ i = 1;　i < len；　i++ ) Ｃ［i］ =　0; ??／*初

54、始化＊／ 　fｏr?。ā　＝ 1; i 〈 ｌeｎ; i++ )?。?? ?? /＊檢測(cè)串中所有字符*/ ???　　ｊ ＝ ０；?　 ｗhｉle　( ｊ?。?k ＆& A[j] !＝ s[ｉ] ) ｊ+＋；?/＊檢查s[i]是否已在A［ ］中＊/　 ?? if ( j == k ）?。?A[k] = s［i］；　C[k］＋+； ｋ＋+ ｝ ?/＊s［i］從未檢測(cè)過*/ ?? ｅｌｓe　C[j］++；? ? 　?/＊s［i］已經(jīng)檢測(cè)過*/ ? ? ｝ ???｝ ?} 　 測(cè)試數(shù)據(jù) s ＝ "caｓt cast　sat ａｔ a ｔaｓa\

55、0”測(cè)試結(jié)果 A 　c ａ s ?。? b C 2 ?。? 4 5 ?。? 【另一解答】 ｉnｃｌude 〈ioｓｔrｅam。h〉 incｌuｄe ＂strｉｎｇ。h” const?。閚t?。鉮arnumber = 1２8； ? ? /＊ASＣIＩ碼字符集的大?。? voiｄ freqｕeｎcy（ Ｓtｒinｇ＆?。?，　int＆　C[　]?。?｛ // s是輸入字符串,數(shù)組C[ ］中記錄每一種字符的出現(xiàn)次數(shù)。 ｆoｒ　( iｎt i = 0; i <　cｈａｒnｕmbeｒ；　i++ )　C[i］ ＝ 0; ? ?/*初始化＊/ ?

56、 ｆoｒ ( i =　0; ｉ <　s.leｎgtｈ　(　); i++?。????? /＊檢測(cè)串中所有字符＊/ Ｃ［ atoi?。ǎ螅郏椋荩。?＋;?? ???/＊出現(xiàn)次數(shù)累加＊/ fｏr?。ā。?= 0；　i ＜ cｈaｒnｕｍbｅr； ｉ＋+　) ?／*輸出出現(xiàn)字符的出現(xiàn)次數(shù)*/ 　 iｆ （　Ｃ［ｉ] ＞ ０ ） cout　〈< ”( " ＜<　i <<　" ) : \t＂ << Ｃ［i］ 〈〈 "\t”; ｝ ２—１6　設(shè)串s為“aａab",串t為“ａｂcａｂaａ”，串r為“ａｂcaａｂbabｃaｂaａcｂacba",試分別計(jì)算它們的失效函數(shù)f （j）的值。

57、 【解答】 j ０ 1 2 3 　j 0 1 2 3 4 5 6 　ｓ ａ a a ｂ t ａ ｂ c a b a a f　(j) -1 0 １ —１ f (j) —1 -1 －１ 0 1 0 0 2-17 設(shè)定整數(shù)數(shù)組B[m+1］［ｎ＋1]的數(shù)據(jù)在行、列方向上都按從小到大的順序排序，且整型變量ｘ中的數(shù)據(jù)在Ｂ中存在.試設(shè)計(jì)一個(gè)算法，找出一對(duì)滿足B[ｉ］[j] == ｘ的ｉ, j值。要求比較次數(shù)不超過m+n. 【解答】 ?算法的思想是逐次二維數(shù)組右上角的元素進(jìn)行比較。每次比較有三種可能的結(jié)果:若相

58、等，則比較結(jié)束；若右上角的元素小于x，則可斷定二維數(shù)組的最上面一行肯定沒有與ｘ相等的數(shù)據(jù),下次比較時(shí)搜索范圍可減少一行；若右上角的元素大于x,則可斷定二維數(shù)組的最右面一列肯定不包含與x相等的數(shù)據(jù)，下次比較時(shí)可把最右一列剔除出搜索范圍。這樣,每次比較可使搜索范圍減少一行或一列,最多經(jīng)過m+n次比較就可找到要求的與x相等的數(shù)據(jù)。 ?ｖoiｄ fｉnd ( inｔ B[ ]［ ］， inｔ m， iｎt　n， int x， int& i, int＆　ｊ ) ｛ //在二維數(shù)組B［ｍ][n]中尋找與x相等的元素, 找到后， 由i與j返回該數(shù)組元素的位置 ? ｉ = ０； 　j =　ｎ； 　 whiｌe　( B［ｉ］[j］ != ｘ ） if （ Ｂ[ｉ］［j] <　x?。?i++; ?? elｓe j-－; ?｝ 不足之處，敬請(qǐng)諒解 21 / 13