復(fù)旦課件第4章數(shù)組

1、要求：1）掌握一維、二維及多維數(shù)組的定義、 初始化與引用；2)掌握字符串?dāng)?shù)組與字符串操作；第4章 數(shù)組 數(shù)組是一些同名同類型變量的有序集合，它們存儲在內(nèi)存的一個連續(xù)的存儲區(qū)內(nèi)。 軟件設(shè)計中，應(yīng)用最多的是一維數(shù)組、二維數(shù)組和三維數(shù)組，其中尤其是一維數(shù)組和二維數(shù)組應(yīng)用最廣。4.1 數(shù)組的基本概念 C語言中的數(shù)據(jù)類型分為基本數(shù)據(jù)和構(gòu)造型數(shù)據(jù)?；绢愋蛿?shù)據(jù)包括：int，short，long，char，float，double 等構(gòu)造型數(shù)據(jù)包括：數(shù)組，指針，結(jié)構(gòu)，聯(lián)合,位域,枚舉(非本課程主要內(nèi)容) 構(gòu)造型數(shù)據(jù)是由若干基本類型或復(fù)雜類型的數(shù)據(jù)按一定的規(guī)則構(gòu)造而成。什么是數(shù)組數(shù)組是一種由若干個同類元素組成

2、的構(gòu)造型數(shù)據(jù)。數(shù)組的定義 數(shù)組的定義是在數(shù)組名的后面加成對的方括號，方括號內(nèi)是一個正整型的常量表達(dá)式，用以說明數(shù)組中有多少個成員。 數(shù)組元素的個數(shù)是一個確定的正整數(shù)，而且在程序中不能改變。如，數(shù)組a的元素個數(shù)為4例如：short a4;表示定義了一個數(shù)組 a，由4 個短整型的數(shù)組元素組成。4.2 一維數(shù)組一維數(shù)組的定義：數(shù)組變量也要遵循“先定義后引用”的原則。 一維數(shù)組定義語句的一般形式為： type nameelement;可以是整型常量或整型常量表達(dá)式其最小值默認(rèn)為0. 表示定義了一個名為name，由element個數(shù)據(jù)類型為type的成員組成的數(shù)組。其中，name是用標(biāo)識符命名的數(shù)組名，

3、方括號內(nèi)的element是一個正整型的常量表達(dá)式，是一個確定的正整數(shù)，用以說明數(shù)組中有多少個成員(數(shù)組元素，元素)，type是任何一種數(shù)據(jù)類型，表示數(shù)組中的所有成員都屬于這種數(shù)據(jù)類型，占有同樣的存儲單元。int a5;數(shù)組類型數(shù)組名數(shù)組長度數(shù)組名a是標(biāo)識符；數(shù)組長度為5,可以是常量、常量表達(dá)式或符號常量，不可是變量或變量表達(dá)式（即不能定義可變數(shù)組）。#define N 5int aN;int n, an;scanf(“%d”,&n);int an;數(shù)組元素的個數(shù)(數(shù)組長度)一經(jīng)定義，不允許再改變。例如：int a5; /* 如果由于某種原因 */int a10; /* 希望改變數(shù)組長度 */

4、再次定義數(shù)組a的長度是錯誤的，因為數(shù)組a由4個整型的數(shù)組元素組成，在程序中數(shù)組元素的個數(shù)是固定的，不能改變。一維數(shù)組的總字節(jié)數(shù)可按下式計算: 總字節(jié)數(shù)=sizeof ( 類型) *數(shù)組長度int a5;/5個元素，總字節(jié)數(shù)為20 在C語言中，與變量的定義一樣，數(shù)組也遵循“先定義后使用”的原則。當(dāng)定義數(shù)組時，它傳遞給編譯器兩方面的信息： 數(shù)組共有多少個元素？ 每個元素占多少個字節(jié)？ 數(shù)組的性質(zhì) 數(shù)組的每一個元素都可看作一個獨立的變量。各元素按下標(biāo)存取(引用)，下標(biāo)是方括號內(nèi)的整型表達(dá)式，n個元素的下標(biāo)取值為0到n-1。例如，數(shù)組a的3個元素分別記為a0, a1,和a2 每個數(shù)組有確定的數(shù)據(jù)類型。

5、例如，數(shù)組a為短整型，則a中所有的元素a0, a1, a2均為短整型，各占2個字節(jié)。 數(shù)組名是常量，數(shù)組名的數(shù)值等于數(shù)組中第一個元素(首個元素)的地址，也稱為數(shù)組的首地址。例如，a的數(shù)值等于a0的地址。 數(shù)組元素的存儲單元是按順序連續(xù)存儲的，因此數(shù)組元素的地址也是連續(xù)的。例如，如果a0的地址為FF10，則從第一個元素a0到元素a2的地址分別為：FF10，F(xiàn)F12，F(xiàn)F14。數(shù)組元素a0a1a2數(shù)組元素的地址FF10FF12FF14數(shù)組的維數(shù) 數(shù)組元素的下標(biāo)個數(shù)由數(shù)組的維數(shù)決定，數(shù)組有一維數(shù)組、二維數(shù)組或多維數(shù)組之分。例如，可以定義二維數(shù)組a和三維數(shù)組x如下：int a46,x432;一維數(shù)組的

6、存儲結(jié)構(gòu)數(shù)組在內(nèi)存中連續(xù)存放；每個元素所占內(nèi)存大小和數(shù)組類型相同；數(shù)組名指向第一個元素（類似于指針）。int a5;a0a1a454 bytesa&a0用printf可以查看數(shù)組地址情況運行結(jié)果&a0=12ff58&a1=12ff5c&a2=12ff60&a3=12ff64&a4=12ff68#include void main( ) int a5,i; for(i=0;i5;i+) printf(&a%d=%xn,i,&ai); 用數(shù)組優(yōu)點：表述簡潔，可讀性高便于使用循環(huán)結(jié)構(gòu)數(shù)組定義示例例如，以下各個數(shù)組的定義是正確的：#define M 20int a10; /* 由10個整型數(shù)組成的一維

7、數(shù)組a */char b70+4; /* 字符數(shù)組s，一行寬度為74個字符 */double cM*2; /* 由40個雙精度實數(shù)組成的向量數(shù)組c */int matrix610; /*6行10列整數(shù)矩陣數(shù)組matrix */6行10列而以下各個數(shù)組的定義是錯誤的：int n;int d1n, d2n+3; /* n 是變量 */char e-4; /* 數(shù)組元素個數(shù)不能是負(fù)數(shù) */double f2.5; /數(shù)組元素個數(shù)不能是小數(shù)float k,m5;/只能為方括號 一維數(shù)組元素的引用 C語言規(guī)定數(shù)組不能以整體形式參與各種運算。參與各種運算的只能是數(shù)組元素，即在程序中不能引用整個數(shù)組而只能逐

8、個引用數(shù)組元素。 一維數(shù)組元素的引用形式為： 數(shù)組名下標(biāo) 其中下標(biāo)可以是整型常量，整型變量或整型表達(dá)式。數(shù)組元素引用舉例int a5; /* 定義1 0個整型數(shù)的數(shù)組*/ 數(shù)組a中的5個元素可分別用a0、a1、a2、a3、a4來引用它們，如a4 = a0 + a1 + a2 + a3；a0 = ai+z; /* 通常要求 0=i+z=4 */ C語言并不檢驗數(shù)組邊界，因此，數(shù)組的兩端都有可能越界而使其它變量的數(shù)組甚至程序代碼被破壞。在需要的時候，數(shù)組的邊界檢驗便是程序員的職責(zé)。void main()/p65_1int d0,d1,d2,d3,d4,d5,d6,d7,d8,d9,x;d0=d1=

9、d2=d3=d4=d5=d6=d7=d8=d9=0;scanf(%d,&x);do if(x%10=0)d0+;else if(x%10=1)d1+;else if(x%10=2)d2+;else if(x%10=3)d3+;else if(x%10=4)d4+;else if(x%10=5)d5+;else if(x%10=6)d6+;else if(x%10=7)d7+;else if(x%10=8)d8+;else if(x%10=9)d9+;while(x/=10);printf(d0=%d,d1=%d,d2=%d,d3=%d,d4=%d,d5=%d,d6=%d,d7=%d,d8=%d

10、,d9=%dn,d0,d1,d2,d3,d4,d5,d6,d7,d8,d9);void main()int d0,d1,d2,d3,d4,d5,d6,d7,d8,d9,x;d0=d1=d2=d3=d4=d5=d6=d7=d8=d9=0;scanf(%d,&x);do switch( x%10 )case 0:d0+;break;case 1:d1+;break;case 2:d2+;break;case 3:d3+;break;case 4:d4+;break;case 5:d5+;break;case 6:d6+;break;case 7:d7+;break;case 8:d8+;break

11、;case 9:d9+;break;while(x/=10);printf(d0=%d,d1=%d,d2=%d,d3=%d,d4=%d,d5=%d,d6=%d,d7=%d,d8=%d,d9=%dn,d0,d1,d2,d3,d4,d5,d6,d7,d8,d9);void main()/p65_1int d10=0,i,x;scanf(%d,&x);do dx%10+;while(x/=10); for(i=0;i=k;i-) ai+1=ai;/*自an-1開始逆序至ak逐一后移*/ ak=x; /*x插入到k位置*/ n+; /*數(shù)組的元素增加了一個*/kn-1n【例4.4】 將數(shù)組的某個下標(biāo)位

12、置(k)的元素刪除 for(i = k+1; im) ，則后部分沒有獲得初值的元素則置相應(yīng)類型的默認(rèn)值（如int型置整數(shù)0， char型置字符0，float型置實0.000000等）。例如定義：intx5=1,2,3;則有：x0=1; x1=2; x2=3; x3=0; x4=0。 注意：初值個數(shù)不允許超過數(shù)組元素的總數(shù)例如以下的定義是錯誤的： int j5 = 0, 1, 2, 3, 4, 5； 初值個數(shù)（=6）超過了定義的數(shù)組長度（=5）。除了初始化，不能對整個數(shù)組直接賦值， 只能逐個賦值： a =0,1,2,3,4;no! for(i=0;i5;i+)ai=i; yes!如果需要賦初值的

13、m個元素不連續(xù)的話，則必須指定數(shù)組元素例如:int h3 = h0=0, h1, h2=1;注意：由于h1沒有賦初值，因此和沒有賦賦初值普通變量一樣，是一個很小的負(fù)數(shù)。而以下的定義是錯誤的：int h3 = 0, , 1;一維數(shù)組編程示例一維查找【例4.5】在數(shù)a的前n個元素中找值等于變量key值元素的下標(biāo)。在數(shù)組的前n個元素中找值為key的元素，有多種解法。(1)數(shù)據(jù)的順序查找（方案一） 從首元素開始，順序查找到數(shù)組的末尾，如果存在該元素，則結(jié)束（break）；按此想法編寫的程序代碼如下： for(i=0; in; i+)if(ai = key)break; /* 找到ai,終止循環(huán) */

14、if(in) /* 若in,表示查找成功 */ printf( %dn , i); /* 輸出ai的下標(biāo) */ else /* 否則，表示查找失敗 */ printf( search failedn ); /* 輸出失敗信息 */（方案二）不用 break 語句的程序代碼：for(i=0;in&key!=ai;i+) ; /* 無論是否找到，都將結(jié)束循環(huán) */ if(in) /* 若in,表示查找成功 */ printf( %dn , i); /* 輸出ai的下標(biāo) */else /*否則 i=n，表示查找失敗 */printf(search failedn); /* 輸出失敗信息 */假定每個

15、元素的查找機會均等，則采用上述查找方法，查找的平均次數(shù)v為： v = (1 + 2 + 3 + + n)/n = (n+1)/2 當(dāng)n足夠大時，(n+1)/2n，因此稱：在數(shù)組中查找的最多次數(shù)為n次。(2)數(shù)據(jù)的順序查找（方案三：設(shè)置哨兵）。首先將key復(fù)制到第n+1元素(an)的位置，稱為設(shè)置了一個哨兵，然后從第一個元素開始順序?qū)ふ?，這能簡化判斷條件，節(jié)省運行時間； an = key; /* 設(shè)置哨兵 */ for(i = 0; key != ai; i+);/* 無論是否找到，都將結(jié)束循環(huán) */ if(in) /* 若in,表示查找成功 */ printf(%dn, i); /* 輸出ai

16、的下標(biāo) */ else /* 否則，表示查找失敗 */ printf(search failedn); /* 輸出失敗信息 */這種寫法，數(shù)組需多用一個元素，但程序比前一種更簡單。 假定數(shù)組a的元素已按它們的值從小到大的順序存放(有序)。則二分法是很好的查找方法。 其算法基本思想是：對任意ai到aj(i am；下一輪的查找區(qū)間為 m+1，j。如果: key am；下一輪的查找區(qū)間為 i，m-1。當(dāng) ji 時，區(qū)間i，j變?yōu)橐粋€空區(qū)間，即表示在數(shù)組a中沒有值為key的元素。由于每輪查找后，使查找區(qū)間減半， 因此稱此查找方法為二分法查找。顯然，初始查找的區(qū)間為i=0，j=n-1。(3)數(shù)據(jù)的順序查

17、找（方案四：二分查找法）。二分法查找可用C代碼描述如下： i = 0 ; j = n-1 ; /* 設(shè)定初始查找區(qū)間 */ while(i am) i = m+1; /* 改變區(qū)間，繼續(xù)查找 */ else j = m-1; /* 改變區(qū)間，繼續(xù)查找 */ /* 找到時，i j */for(i=0, j=n-1; i am) i = m + 1; /* 改變區(qū)間，繼續(xù)查找 */ elsej = m - 1; /* 改變區(qū)間，繼續(xù)查找 */二分法算法演示a0a1a2a3a4a5a6a7a8a9a10a11a12a13a14247112736384042495052616872例 1:已知n=15

18、, key=360) i=0, j=14；1) m=(0+14)/2=7, a7=40key, j=m-1=6；12) m=(0+6)/2=3, a3=11key, i=m+1=4；23) m=(4+6)/2=5, a5=36=key, 找到，退出。3ia0a1a2a3a4a5a6a7a8a9a10a11a12a13a14247112736373842495051525672例 2: 已知n=15, key=450) i=0, j=14；1) m=(0+14)/2=7, a7=38key, j=m-1=10；3) m=(8+10)/2=9, a9=49key, j=m-1=9；4) m=(8+

19、9)/2=8, a8=42j，查找失敗，返回n=15，結(jié)束?！纠?.6】按遞增順序生成集合M 的前n 個元素。 （自學(xué)）集合 M 定義如下：（1）整數(shù)1 屬于M；（2）如果整數(shù)X 屬于M，則整數(shù)2*X+1 和3*X+1 也屬于M；（3）再沒有別的整數(shù)屬于M。根據(jù)集合 M 的定義，它的前幾個元素的枚舉過程為M = 1，= M = 1，3， 2 * 1 + 1 = 3= M = 1，3，4， 3 * 1 + 1 = 4= M = 1，3，4，7， 2 * 3 + 1 = 7= M = 1，3，4，7，9， 2 * 4 + 1 = 9 首先，為存儲M 的元素設(shè)計一個足夠大的整數(shù)組m，用j 表示集合M

20、 中已生成的元素個數(shù)。按題意，首先將1放入集合M 中，然后按遞增順序用M 中的現(xiàn)有元素枚舉出M 的新元素?！舅惴ǚ治龊驮O(shè)計】 設(shè)定義數(shù)組 mN來存儲M集合（N足夠大）。由于每個元素都可能施行兩種枚舉操作，因此需要兩個指針e2 和e3，用以分別指向即將執(zhí)行2*me2+1 和3*me3+1枚舉操作整數(shù)的位置（元素下標(biāo)）。另外，由于M 是按遞增順序排列的，所以需要對它們即將執(zhí)行枚舉產(chǎn)生的整數(shù)進(jìn)行比較大小，小的先枚舉產(chǎn)生M 的新元素。而每枚舉一次，e2 或者e3 需要加1。因此，算法描述如下：初始，令 m0為1，e2 和e3 均為0，當(dāng)前M中元素的個數(shù)j為1，集合的容量為n。如果 j =n，結(jié)束循環(huán)。

21、m0 = 1, e2 =e3 =0,j=1 結(jié)束輸出集合j=me2*2+1NYmj=me3*3+1Y mj=me3*3+1取2*me2+1排除兩者相等取3*me3+1j+【生成集合M 的程序】#include #define N 100void main() short mN=1, n, e2=0, e3=0, j=1; scanf(%d, &n); /生成n個元素 while(j=me2*2+1) /對me2執(zhí)行2*x+1枚舉操作 mj=me2+*2+1; if(me3*3+1=mj) e3+;/當(dāng)兩個元素枚舉值相同時,同時枚舉else mj=me3+*3+1; /對me2執(zhí)行2*x+1枚舉

22、操作 j+; for(j=0; jn; j+) printf(%dt, mj); printf(n);【生成集合 M 的改進(jìn)程序】#include #define N 1000void main()short mN, n, e2, e3, j, m2, m3;scanf(%d, &n); /生成n個元素for(m0=j=1, e2=e3=0; jn; j+) m2 = 2 * me2 + 1; /計算m2 和m3 m3 = 3 * me3 + 1; mj = m2 m3 ? m2 : m3; /從m2 和m3 中選擇小的送mj e2 += m2 = m3; /m2 = m3; /m3 = m2

23、,更新e3 for(j=0; jn; j+) printf(%dt,mj); printf(n);【例4.7】從含n個整數(shù)的數(shù)組中，找出其中出現(xiàn)次數(shù)最多且是最先出現(xiàn)的整數(shù)。 【解題思路】 設(shè)數(shù)組為a，為了找出a中出現(xiàn)次數(shù)最多且最早出現(xiàn)的元素，令變量pos存儲數(shù)組中出現(xiàn)次數(shù)最多的元素的下標(biāo)，c是該元素在數(shù)組中出現(xiàn)的次數(shù)(初值為0)。程序用循環(huán)順序考察數(shù)組的每個元素，對當(dāng)前正在考察的元素ai，用循環(huán)統(tǒng)計出數(shù)組中與ai等值的元素個數(shù)tc。統(tǒng)計結(jié)束后，讓tc與c比較，如果tc的值大于c，就用tc更新c，并用i更新pos；否則，不更新。for(c = i = 0; i n-1; i+) /c:記錄最多次

24、數(shù) for(tc=1,j=i+1;j c) /* 找到出現(xiàn)次數(shù)更多的整數(shù) */ c = tc; pos = i; /保留最大數(shù)和它的位置 printf(出現(xiàn)最多的值是%d 出現(xiàn)的次數(shù)是 %dn, apos,c);【例4.8】對數(shù)組作整理, 使其中小于0的元素移到前面,等于0的元素留在中間, 而大于0的元素移到后面。例如:5, -4, 0, -2, 7, 0, 8 將整理為: -4, -2, 0, 0, 7, 8, 5【算法分析和設(shè)計】在整理過程中，把數(shù)組分為三段左段 0 k-1 (a0ak-1)中存放負(fù)數(shù)元素，中段k j-1(ak aj-1) 存放0元素,右段h+1 n-1 (ah+1an-1

25、)中存放正數(shù)元素。引入變量k(負(fù)數(shù)的個數(shù))、h（大于0的個數(shù)）0 k-1 h+1 n-1左段：負(fù)數(shù) 中段:0元素 還沒考察 右段：正數(shù)k j-1 j h (1)aj0:交換 aj 和 ah;令h-,大于0的元素多了一個。由于交換前的ah是還未考察過的元素，所以j不能增1。 根據(jù)元素aj小于0、等于0和大于0這3種情況，分別有3種處理辦法: 初始時,令 j = 0， k = 0 , h = n-1 ，然后令j從0 開始向右搜索,直至jh 為止：0 k-1 h+1 n-1左段：負(fù)數(shù) 中段:0元素 還沒考察 右段：正數(shù)k j-1 j h 5, -4, 0, -2, 7, 0, 8 將整理為 -4,

26、-2, 0, 0, 7, 8, 5【算法演示】 -4 -2 0 0 7 8 5 k j,h -4 0 0 -2 7 8 5 k j h -4 0 0 -2 7 8 5 k, j h -4 0 0 -2 7 8 5 k j, h 0 -4 0 -2 7 8 5 k j h 0 -4 0 -2 7 8 5 j,k 8 -4 0 -2 7 0 5 j,k h 5 -4 0 -2 7 0 8 h 0 1 2 3 4 5 6 aj=0,j+;j=1,aj=-40,ajah,h-,h=5aj0,ajah,h-,h=4k+,k=1,j+,j=2aj=0,j+;j=3,aj=-20akaj,k+,k=2,j+

27、,j=4#include #define MAXN 1000void main() int j, n, k, temp, h,aMAXN; printf(Enter nn); scanf(%d, &n); / 輸入數(shù)組中實際數(shù)據(jù) printf(Enter a0 -a%dn, n-1); for(j=0; jn;j+)scanf(%d, &aj);【例4.8】數(shù)組整理程序: j = k = 0; h = n-1; while (j = h) if (aj0) temp=aj; aj=ak; ak=temp; j+; k+; else if (aj = 0) j+; else temp=aj; a

28、j=ah; ah=temp;h-; for(j=0;j n; j+)printf(“%4d”,aj);/*輸出*/ printf(nnn);【例4.9】輸入一個含n個元素的數(shù)組，要求數(shù)組中的元素互不相等。數(shù)組生成后，按每行10個整數(shù)的格式輸出?！窘忸}思路】 設(shè)數(shù)組為a，并引入已輸入的不同整數(shù)的計數(shù)器i，i的初值為0。用循環(huán)逐一輸入整數(shù)，將當(dāng)前輸入的整數(shù)存于ai中，并檢查該整數(shù)是否與早先已輸入并存儲于a0至ai-1的某個整數(shù)相等。如果發(fā)現(xiàn)當(dāng)前輸入的整數(shù)與早先輸入并存儲的某個整數(shù)相等，則忽略該元素，繼續(xù)輸入下一個整數(shù)。如果當(dāng)前輸入的整數(shù)與早先輸入的整數(shù)都不相等，說明ai是未曾輸入過的，則讓i增1。

29、在輸入不同整數(shù)個數(shù)i等于n時，結(jié)束循環(huán)。i = 0;while (i n) printf(Enter a%d , i); scanf(%d, &ai); for(k=0;ak!=ai; k+); /* 檢查是否有重復(fù) */ if(k i) /* ai與a0至ai-1的某個ak相等 */ printf(這是一個早先曾輸入過的整數(shù)!n); else i+ ; /* 當(dāng)前輸入的ai是一個不重復(fù)的整數(shù) */ for(i = 0; i n; i+) if(i % 10 = 0) /每輸出5個整數(shù)后，輸出一個換行 printf(n); printf(%4d, ai); 排序算法 排序算法是計算機算法中最常

30、用的算法之一。 排序是指對一個數(shù)據(jù)序列進(jìn)行處理，使得該序列中的數(shù)據(jù)按照一定規(guī)律按次序排列。最簡單的排序是整數(shù)的升序或者降序排列。例如，序列8, 4, 3, 6, 9, 2, 7的升序排序為2, 3, 4, 6, 7, 8, 9。 排序有許多種算法，例如插入法、選擇法、冒泡法、二分法、雜湊法、等等。本教材使用的是冒泡法?！纠?.10】輸入n個整數(shù)，對它們用冒泡法從小到大排序，然后輸出。 冒泡排序：一種類似于輕者上浮、重物下沉的排序算法，將相鄰元素進(jìn)行比較，小者置前，大者放后，不斷依次比較，直至最終結(jié)果。 冒泡排序算法的基本思想是對數(shù)據(jù)序列進(jìn)行 n-1 次循環(huán)。 具體做法是:對數(shù)組作多次比較調(diào)整遍

31、歷，在每次循環(huán)中，認(rèn)為數(shù)據(jù)序列中的 n 個數(shù)據(jù)是未排序的。依次對相鄰兩個數(shù)據(jù)進(jìn)行比較，如果較大數(shù)在前，則將兩數(shù)交換(設(shè)從小到大排序)。在一次循環(huán)結(jié)束后，最前面一個數(shù)據(jù)必然是最小的。e.g: 將序列 49,38,65,97,76,13,27,49,100,3用起泡排序的方法進(jìn)行排序。冒泡排序/* 冒泡排序算法描述 */for(i = 0;i i;j-) /* 需要比較 n-1-i 次 */ if(ajaj-1) /* aj與aj-1交換 */ temp = aj; aj = aj-1; aj-1 = temp; 結(jié)論：對于N個元素的數(shù)組：遍歷次數(shù)：N-1；第i輪遍歷的比較次數(shù)：N-1-i；總比較

32、次數(shù)：N*(N-1)/2方案二：冒泡法存在的問題觀察對數(shù)據(jù)序列1, 7, 8, 4, 5進(jìn)行冒泡排序的過程第2 次遍歷：第3 次遍歷：第4 次遍歷：1 7 8 4 5 1 7 8 4 51 7 4 8 51 4 7 8 51 4 7 8 51 4 7 8 51 4 7 5 81 4 5 7 81 4 5 7 81 4 5 7 81 4 5 7 81 4 5 7 81 4 5 7 81 4 5 7 8第1 次遍歷： 在第二次循環(huán)后，實際上已經(jīng)完成排序，后兩輪可以不做了。但由于冒泡法中外循環(huán)的次數(shù)是固定的,對數(shù)據(jù)序列1,4,5,7,8進(jìn)行冒泡排序時，雖然該數(shù)據(jù)序列已排序，冒泡法還是要作n-1次循環(huán)

33、。從例中得出,對于一個數(shù)據(jù)序列，如果存在某些子序列是已排序的話，應(yīng)該可以節(jié)省循環(huán)的次數(shù)的。改進(jìn)1：如果某次遍歷未發(fā)生任何交換，說明數(shù)組已經(jīng)排好序。設(shè)立flg標(biāo)志。 每次遍歷前，預(yù)置該變量的值為0。當(dāng)發(fā)生交換時，置該變量的值為1，一次遍歷結(jié)束時，就檢查該變量的值，若其值為1，說明發(fā)生過交換，繼續(xù)下一次遍歷；如該變量的值為0，說明未發(fā)生過交換，則立即結(jié)束排序循環(huán)。相應(yīng)的排序代碼改為：for(i=0;ii;j-)/* 比較 n-1-i 次 */ if(aj aj-1) temp = aj; aj = aj-1; aj-1 = temp; flg = 1;/有元素交換的情況 if (flg = 0)

34、break; 冒泡法排序優(yōu)化片斷改進(jìn)2：如果某次遍歷在某個位置發(fā)生過最后一次交換，則說明以后的元素都是排好序的。設(shè)立up標(biāo)志例如，數(shù)列a=1,2,3,6,4,7,5，第一次遍歷，j在6處發(fā)生元素交換，j在4處發(fā)生交換，j在3,2,1處都未發(fā)生元素交換。最后交換處是j為4。這次遍歷使序列變成：a = 1，2，3，4，6，5，70 1 2 3 4 5 6a = 1，2，3，4，6，5，7 下一次遍歷的范圍的上界可立即縮短至上一次遍歷的最后交換處之前，即位置5。 利用該性質(zhì)，引入變量up，k. k:記錄每次遍歷的最后元素交換位置。 考慮到可能某次遍歷時一次也不發(fā)生元素交換的情況，因此在每次遍歷前，預(yù)

35、置變量k=n。一次遍歷結(jié)束后，賦k給up，作為下一次遍歷的上界。up=n結(jié)束，up的初值為0。 up = 0; /* 一次遍歷至up之前，初始時，遍歷至首元素之前 */ while (up up; j-) /*比較至up*/ if(ajaj-1) /*aj與aj-1交換*/ temp = aj; aj = aj-1; aj-1 = temp; k = j; /*記錄發(fā)生交換的位置*/ up = k; 常用的選擇排序的算法描述其算法思想是： 首先從下標(biāo)為0的元素開始，在數(shù)組內(nèi)找最小元素，并將這最小元素與下標(biāo)為0的元素交換；接著從下標(biāo)為1的元素開始，在數(shù)組內(nèi)找最小元素，并將這最小元素與下標(biāo)為1的元

36、素交換；依次類推，直至從下標(biāo)為n-2的元素開始，在數(shù)組內(nèi)找最小元素，并將這最小元素與下標(biāo)為n-2的元素交換。到此，數(shù)組排序完畢。void main()int i,n,k,x,min,min_k,a100;scanf(%d,&n); /* */for (i=0;in;i+)scanf(%d,&ai);/*輸入10個整數(shù)*/for (k=0;kn-1;k+) /*控制排序n-1步 */ min=ak; /* 假設(shè)第k數(shù)是最小值，用min記錄*/ min_k=k; /* 用min_k 記錄當(dāng)前最小值的下標(biāo)*/ for (i=k+1;in;i+)/*在ak到an-1尋找最小數(shù)*/ if (aimin)

37、 /*成立，記錄新的最小數(shù)和它的下標(biāo)*/ min=ai; min_k=i; x=amin_k;amin_k=ak;ak=x; /*交換最小數(shù)和第k個數(shù)*/ for (i=0;i=n-1;i+) /*輸出排序后的n個數(shù)*/ printf(%5d,ai); printf(n); 【例4.11】設(shè)有順序編號為1至n的n（100）個人按順時針順序站成一個圓圈。首先從第1個人開始，按順時針順序從1開始報數(shù),報到第m（n）個人，令其出列。然后再從出列的下一個人開始，按順時針順序從1開始報數(shù)，報到第m個人，再令其出列， 。如此下去,直到圓圈不再有人為止。求這n個人出列的順序。例如：有10人，報數(shù)為3的出局，

38、則有下面的排列原排列： 1 2 3 4 5 6 7 8 9 10現(xiàn)排列： 3 6 9 2 7 1 8 5 10 4#include /p77#define N 100int main() int i, j, k, aN, n, m; printf(輸入n & mn);scanf(%d%d, &n, &m); for(i = 0; i n; i+)ai = i+1; for(j = 0, i = 0; i n; i+) /從第1人開始報數(shù)(j = 0)，共有n論報數(shù) for(k = 0; ;j = (j+1)%n) /尋找出局者 if(aj &+k = m) break;/找到出局者，退出 printf(%4d, aj); /打印出局者 aj = 0; /將出局者置0 printf(n程序結(jié)束n);return 0;#include