第五章1 數(shù)組

《第五章1 數(shù)組》由會員分享，可在線閱讀，更多相關《第五章1 數(shù)組（13頁珍藏版）》請在裝配圖網(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)個元素的一個集合，　下標范圍從0到ｎ－1.對數(shù)組中元素 ? /／可按下標所指示位置直接訪問。 ? private: ? Tｙｐｅ *ｅlｅｍenｔs；? ? ? ?? //數(shù)組 ?? inｔ AｒｒaySizｅ;

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

3、訪問數(shù)組元素 ? inｔ　Lenｇth （ ） const ｛ return?。羠raySizｅ； } ??//取數(shù)組長度 　　vｏｉd　ReSizｅ　(　inｔ sz ); ???? //修改數(shù)組長度 ? } ??順序表的類定義 ?＃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;? ? ?/／順序表的最大可容納項數(shù) ? int laｓt;? ????//順序表當前已存表項的最后位置 ? 　 ｉnt　current; ? ?／/順序表的當前指針(最近處理的表項) publiｃ： ?? ＳeqLiｓt　( int ＭaxSizｅ ）；? ??//構(gòu)造函數(shù) ? 　 　~SeqList (　) {　delete ［ ］　datａ； ｝ ??//析構(gòu)函數(shù) ? ｉnt Length?。?) const ｛　rｅｔurn ｌａst+1；?。??/／計算表長度 　int Ｆiｎd　( Ｔyｐｅ& ｘ ) consｔ；

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

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

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

8、過程以求得問題的解. 【解答】 出局人的順序為5， 1， 7, 4, 3, ６， 9, 2,?。?。 2－2　試編寫一個求解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ù)源程序清單如下： 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;? ? ? ／＊報名起始位置＊/ ? for　（?。搿? n； ｋ　〉 1; i—-　) {??? ?／*逐個出局，執(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 ＝ ０ ?報錯信息 　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 最終出局順序 當m = 1時，時間代價最大。達到( n—１ ） + ( n-２ ）?。?????? + １ = n（ｎ-1)/2　? O(ｎ2)。 ２—３　設有一個線性表?。╡0， e1，　…， ｅn－２， eｎ—1) 存放在一個一維數(shù)組A[ａrraｙＳize］中的前n個數(shù)組元素位置。請編寫一個函數(shù)將這個線性表原地逆置,即將數(shù)組的前ｎ個原址內(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ｅ］中有多個零元素， 試寫出一個函數(shù)， 將Ａ　中所有的非零元素依次移到數(shù)組A的前端A[ｉ］（0￡ i ￡?。醨ｒａySize）。 【解答】 因為數(shù)組是一種直接存取的數(shù)據(jù)結(jié)構(gòu),在數(shù)組中元素不是像順序表那樣集中存放于表的前端，而是根據(jù)元素下標直接存放于數(shù)組某個位置,所以將非零元素前移時必須檢測整個數(shù)組空間

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

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

19、刪除時平均移動元素個數(shù)AMＮ為 2－6 若矩陣Am′n中的某一元素A[i］［j］是第ｉ行中的最小值，同時又是第ｊ列中的最大值，則稱此元素為該矩陣的一個鞍點.假設以二維數(shù)組存放矩陣,試編寫一個函數(shù),確定鞍點在數(shù)組中的位置（若鞍點存在時)，并分析該函數(shù)的時間復雜度。 【解答】 ?iｎt ｍinmａx （ int?。粒?］［ ］, coｎst iｎt ｍ， const iｎｔ　n ） ｛ //在二維數(shù)組A［m]［n]中求所有鞍點， 它們滿足在行中最小同時在列中最大 int *row =　new ｉnｔ［m]； 　inｔ ＊ cｏl?。健eｗ　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; ｉ+＋　） {?? ? ／/檢測矩陣，尋找鞍點并輸出其位置 ? 　for　( j =　0； j ＜ n；　j++　） ? ｉｆ ( ｒow[i] ＝＝　col［j] ） couｔ <＜ “The ｓaｄｄｌｅ ｐoint is?。骸?” ＜〈 ｉ　〈< “,　"　〈＜　ｊ <<　“）” 〈〈 endl； ? deｌｅtｅ ［ ]　row；　?。鋏ｌete　［ ]　cｏl;　 } 此算法有3個并列二重循環(huán)，其時間復雜度

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

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

24、不合理或順序表為空則顯示出錯信息并退出運行。 (６） 從有序順序表中刪除其值在給定值s與t之間(要求ｓ小于ｔ）的所有元素，如果s或t不合理或順序表為空則顯示出錯信息并退出運行。 ?(7)　將兩個有序順序表合并成一個新的有序順序表并由函數(shù)返回結(jié)果順序表。 （8） 從順序表中刪除所有其值重復的元素，使表中所有元素的值均不相同。 【解答】 (１) 實現(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； ? ? ??／/假定０號元素的值最小 fｏr ( int?。?＝　1； i　<＝ ｌasｔ;　i+＋ ） {????//循環(huán), 尋找具有最小值的元素 ? ｉf?。?data[i] 〈 data［m］　） ｍ ＝ ｉ； ? ?//讓m指向當前具最小值的元素 Tyｐe?。鬳mp = dａt(yī)ａ[m］； datａ［m］ = data［lａｓt]； ｌast——； ? ?/／空出位置由最后元素填補, 表最后元素位置減1 ? 　 ｒetuｒ

26、ｎ　teｍp； ?｝ （2）　實現(xiàn)刪除第i個元素的函數(shù)如下（設第i個元素在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、?／/暫存第ｉ個元素的值 ｆor ( int j?。健；　j 〈　last；?。辏? ）　? ??//空出位置由后續(xù)元素順次填補 datａ［ｊ] =?。洌醫(yī)a[ｊ+1]； ｌａst－-； ? ???/／表最后元素位置減1 retｕｒn tｅmp； ｝ （３） 實現(xiàn)向第i個位置插入一個新的元素x的函數(shù)如下(設第i個元素在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++； ｝ ?（５）　實現(xiàn)刪除其值在給定值s與t之間(要求s小于t）的所有元素的函數(shù)如下: tｅmplate＜Type＞ void　SeqList〈Ｔype> :：?。膃lNo＃ｓｔo#ｔ (　Ｔyｐ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） 實現(xiàn)從有序順序表中刪除其值在給定值s與t之間的所有元素的函數(shù)如下： tｅｍplate〈Tｙpe＞?。鰋ｉd?。觘qList＜Type＞ ：： DｅlNo#ｓto#t１　(　Type& ｓ, Ｔypｅ&　t?。 ?。閒 （

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

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

34、〈Tyｐe＞& B　) { /／合并有序順序表A與Ｂ成為一個新的有序順序表并由函數(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　( )　) ? ?//當A表未檢測完，　繼續(xù)向結(jié)果表傳送 ｛ data[k] = value1； 　value1 = Ａ．Nｅｘt （ ); 　i+＋; ｋ+

36、＋；　} ?? wｈｉｌe （ j 〈 B.Leｎgtｈ （ ） ） ? ??/／當B表未檢測完, 繼續(xù)向結(jié)果表傳送 { ｄatａ[k] ＝ vａlue2; vａｌuｅ２ = B。Next (　); j++； k++； ｝ ? 　last = ｋ – １； ? 　　reｔurn ＊ｔhis； } （８) 實現(xiàn)從表中刪除所有其值重復的元素的函數(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)檢測 j = i + 1; temp ＝ daｔa［ｉ]； 　 while　(　j ＜= laｓt ） ｛??? //對于每一個ｉ， 重復檢測一遍后續(xù)元素 iｆ?。?ｔemp == ｄatａ［j]?。?{?? ? ／／如果相等，　后續(xù)元素前移 　for （ k = ｊ＋１; k　<＝ laｓt； k++ ） datａ［ｋ－1]　=　data［k]; 　? 　 last-－; ?

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

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

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

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

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

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

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

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

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

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

48、增的順序排列。試對右圖所示的稀疏矩陣,分別建立它的三元組表和帶行指針數(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ｄｃ”。試利用字符串的基本運算實現(xiàn)這個替換操作。 【解答】 Stｒing ＆?。觮rinｇ :：　Replace （ Ｓtrinｇ?。?ｔ， String ＆v) ｛ if　( ( ｉnt iｄ?。?Find　( t ） ） =＝ －1 ) ? /／沒有找到，當前字符串不改，返回 { cout 〈〈 ＂Ｔhe (replace）?。铮餰ratiｏn fａi

50、led．"　<＜ endｌ； 　returｎ *thｉs; } 　 Strｉng　temp（ ch ）; ? ?//用當前串建立一個空的臨時字符串 ch[０] =　’\0’; 　curLen ＝ ０;? ???／/當前串作為結(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?。?/p>

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é)果串連接后的長度 ｉ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]； //刪改原來的字符串??。鬳mp。cuｒLｅn?。?iｄ ＋ ｔ.curLen； ｉｄ = teｍｐ．Find （　t　)；? } 　rｅturn ＊this; ｝ 2—15 編寫一個算法ｆrequeｎcy，統(tǒng)計在一個輸入字符串中各個不同字符出現(xiàn)的頻度。用適當?shù)臏y試數(shù)據(jù)來驗證這個算法。 【解答】 ?ｉｎclｕde

53、符串,數(shù)組Ａ［ ]中記錄字符串中有多少種不同的字符，C［　]中記錄每 /／一種字符的出現(xiàn)次數(shù)。這兩個數(shù)組都應在調(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++ )?。?? ?? /＊檢測串中所有字符*/ ???　?。?＝ ０；?　 ｗhｉle　( ｊ?。?k ＆& A[j] !＝ s[ｉ] ) ｊ+＋；?/＊檢查s[i]是否已在A［ ］中＊/　 ?? if ( j == k ）?。?A[k] = s［i］；　C[k］＋+； ｋ＋+ ｝ ?/＊s［i］從未檢測過*/ ?? ｅｌｓe　C[j］++；? ? 　?/＊s［i］已經(jīng)檢測過*/ ? ? ｝ ???｝ ?} 　 測試數(shù)據(jù) s ＝ "caｓt cast　sat ａｔ a ｔaｓa\

55、0”測試結(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++?。????? /＊檢測串中所有字符＊/ Ｃ［ 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　設串s為“aａab",串t為“ａｂcａｂaａ”，串r為“ａｂcaａｂbabｃaｂaａcｂacba",試分別計算它們的失效函數(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ù)組B[m+1］［ｎ＋1]的數(shù)據(jù)在行、列方向上都按從小到大的順序排序，且整型變量ｘ中的數(shù)據(jù)在Ｂ中存在.試設計一個算法，找出一對滿足B[ｉ］[j] == ｘ的ｉ, j值。要求比較次數(shù)不超過m+n. 【解答】 ?算法的思想是逐次二維數(shù)組右上角的元素進行比較。每次比較有三種可能的結(jié)果:若相

58、等，則比較結(jié)束；若右上角的元素小于x，則可斷定二維數(shù)組的最上面一行肯定沒有與ｘ相等的數(shù)據(jù),下次比較時搜索范圍可減少一行；若右上角的元素大于x,則可斷定二維數(shù)組的最右面一列肯定不包含與x相等的數(shù)據(jù)，下次比較時可把最右一列剔除出搜索范圍。這樣,每次比較可使搜索范圍減少一行或一列,最多經(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-－; ?｝ 不足之處，敬請諒解 21 / 13