C語言程序設(shè)計(jì)（第三版）課件第8章數(shù)組

第八章數(shù)組問題的提出

假設(shè)班上有4個學(xué)生，如果使用基本數(shù)據(jù)類型int，使用“inta1,a2,a3,a4;”這4個整型變量來表示這4個學(xué)生的年齡。這4個學(xué)生的年齡可以用下面的語句輸出。printf("%d%d%d%d\n",a1,a2,a3,a4);當(dāng)班上的學(xué)生數(shù)為40個時或者更多時，怎樣輸出這些學(xué)生的年齡呢？

數(shù)組數(shù)組是同類型數(shù)據(jù)的有序集合。1、數(shù)據(jù)類型相同2、有序3、構(gòu)造數(shù)據(jù)類型1、一維數(shù)組2、二維數(shù)組主要內(nèi)容：3、字符數(shù)組4、數(shù)組的應(yīng)用定義：

類型說明

數(shù)組名[正整型常量表達(dá)式];

定義數(shù)組名數(shù)組中元素的個數(shù)[]:下標(biāo)的界定符，不能用()例

int

a[6];a[0]a[1]a[2]a[3]a[4]a[5]a基本的數(shù)據(jù)類型8.1一維數(shù)組【例8.1】現(xiàn)舉例說明一維數(shù)組的定義方法。inta[10];

a[0]，a[1]，a[2]，a[3]，a[4]，a[5]，a[6]，a[7]，a[8]，a[9]。從0開始n-1結(jié)束10個元素都可作為整型變量使用

floatb[5];b[0]，b[1]，b[2]，b[3]，b[4]floatb[5];b[0]，b[1]，b[2]，b[3]，b[4]說明：（1）數(shù)組名命名規(guī)則遵從標(biāo)識符命名規(guī)則并遵循“見名知義”原則。（2）數(shù)組名后為方括號[]（取下標(biāo)運(yùn)算符），不能用圓括號。如：inta(10)是非法的。（3）定義格式中的“常量表達(dá)式”表示元素的個數(shù)，即數(shù)組長度。數(shù)組元素的下標(biāo)（有的地方也稱索引）始終從0開始，到n-1結(jié)束（4）數(shù)組定義格式中的“常量表達(dá)式”可以包含正整型常量和符號常量（僅限正整型），但不能包含變量。intm;scanf("%d",&m);inta[m];m為變量非法！#defineN10inta[N];合法！n為符號常量（5）數(shù)組中每個元素的數(shù)據(jù)類型相同，這些元素在內(nèi)存里面是連續(xù)存放的。（1）定義數(shù)組時對所有元素逐一賦初值inta[5]={1,2,3,4,5};a[0]=1;a[1]=2;a[2]=3;a[3]=4;a[4]=5;（2）可以只給一部分元素賦初值inta[5]={1,3,5};a[0]=1;a[1]=3;a[2]=5;（3）對數(shù)組元素全部賦初值時，可以不指定長度。inta[]={1,2,3,4,5};a[0]=1;a[1]=2;a[2]=3;a[3]=4;a[4]=5;a[3]a[4]一維數(shù)組的初始化=0;

=0;（4）指定初始化式的情況（C99標(biāo)準(zhǔn)）

經(jīng)常會有這樣的情況：數(shù)組中只有相對較少的元素需要進(jìn)行顯示的初始化，而其他元素可以默認(rèn)賦值。

考慮下面的情況：inta[10]={0,0,29,0,0,13,0,0,35,0};我們希望索引為2的元素為29，索引為5的元素為13，索引為8的元素為35，其它的元素為0。C99標(biāo)準(zhǔn)中的指定初始化式可以將上面問題指定初始化式為：inta[10]={[2]=29,[5]=13,[8]=35};inta[10]={[5]=13,[2]=29,[8]=35};inta[10]={[8]=35,[2]=29,[5]=13};也可以指定初始化式為：還可以指定初始化式為：一維數(shù)組元素的引用

【例8.3】體會下面給數(shù)組元素賦值和數(shù)組元素的引用的過程。main(){inti,a[5];for(i=0;i<=4;i++)a[i]=i;for(i=4;i>=0;i--)printf("%5d",a[i]);}a[0]a[1]a[2]a[3]a[4]a[0]=00a[1]=11a[2]=2234i012443210【例8.4】一維數(shù)組的輸入與輸出。#include"stdio.h"main(){inti;inta[4];printf("\n輸入數(shù)組a(共4個整數(shù))：");for(i=0;i<4;i++){scanf("%d",&a[i]);}printf("\n輸出數(shù)組a：");for(i=0;i<4;i++){printf("a[%d]=%d",i,a[i]);}}&第i個元素的地址???

兔子繁殖問題。設(shè)有一對新生的兔子，從第三個月開始，它們每個月都生一對兔子。按照這樣的規(guī)律，并假設(shè)兔子沒有死亡，一年后共有多少對兔子。

1 n=1f(n)=1 n=2f(n-2)+f(n-1)n>=311f1f2ff1f23ff1f2f?258f=f1+f2;f1=f2;f2=f;for(i=3;i<=n;i++){}

intf,f1=1,f2=1,i,n;反復(fù)的覆蓋f[0]f[1]f[2]f[3]f[4]f[5]f[19]……...1101452319235【例8.5】:用數(shù)組求

Fibonacci數(shù)列的前20項(xiàng)f[i]=f[i-2]+f[i-1];for(i=2;i<20;i++)#defineNUM20main(){inti;intfib[NUM]={0,1};

for(i=2;i<NUM;i++)

fib[i]=fib[i-2]+fib[i-1];

for(i=0;i<NUM;i++){if(i%5==0)printf("\n");printf("%6d",fib[i]);}return0;}【例28.6】求數(shù)組元素中的最大值與最小值。inta[10];inti,max,min;for(i=0;i<=9;i++)scanf("%d",&a[i]);max=min=a[0];for(i=0;i<=9;i++){}if(a[i]<min)min=a[i];if(a[i]>max)max=a[i];找出最大值和最小值的位置？,m,n{min=a[i];m=i;}{max=a[i];n=i;}

【例8.7】從鍵盤輸入10個學(xué)生的成績，求這10個學(xué)生的平均成績，并統(tǒng)計(jì)其中不及格的人數(shù)。main(){inti;floatf,n=0,sum;for(i=1,sum=0;i<=10;i++){scanf("%f",&f);sum+=f;if(f<60)n++;}printf("%d,%f\n",n,sum/10);}采取反復(fù)覆蓋的方法輸出每個學(xué)生與平均成績的差反復(fù)覆蓋的方法數(shù)組的方法main(){inti;floatf,n=0,sum;for(i=1,sum=0;i<=10;i++){

scanf("%f",&f);sum+=f;if(f<60)n++;}printf("%d,%f\n",n,sum/10);}inta[10],i,n=0,sum,a;for(i=0,sum=0;i<10;i++){scanf("%d",&a[i]);sum+=a[i]if(a[i]<60)n++;}a=sum/10.0;for(i=0,sum=0;i<10;i++)printf("%f",a[i]-a);printf("%d",n);【例8.8】用冒泡法（下沉法）將8個數(shù)排序3849657613273097238496513273076

973384913273065769743813273049657697513273038496576976132730384965769774938659776132730

1n=83849769797279797137676762730136527653065131349493049273827383038步驟:3027139730if(a[i]>a[i+1]){t=a[i];a[i]=a[i+1];a[i+1]=t;}

for(i=0;i<N-1;i++)for(j=0;j<N;j++)-1-j#defineN8intmain(){inta[N],i,j,t;for(i=0;i<N;i++)scanf("%d",&a[i]);for(i=0;i<N-1;i++)

for(j=0;j<N-i-1;j++)if(a[j]>a[j+1]){t=a[j];a[j]=a[j+1];a[j+1]=t;}for(i=0;i<N;i++)printf("%5d",a[i]);printf("\n");return0;}

線性查找

從數(shù)組的第一個元素開始，依次將要查找的數(shù)和數(shù)組中的元素比較，直到找到該數(shù)或找遍整個數(shù)組為止。思路：inttable[10]={0,2,4,6,8,10,12,14,16,18},x;scanf("%d",&x);if(x==table[i])for(i=0;i<10;i++),mm=i;if(find==1)printf("%d在table[%d]中\(zhòng)n",x,i);elseprintf("沒有找到數(shù)%d\n",x);}return0;}main(){inttable[10]={0,2,4,6,8,10,12,14,16,18};intx,i,find=0;scanf("%d",&x);for(i=0;i<10;i++){if(x==table[i]){find=1;break;}考慮到數(shù)字在某個數(shù)組中有重復(fù)出現(xiàn)的可能，我們引入Bool值，將這個程序修改為：#include"stdbool.h"main(){inttable[10]={0,2,4,2,8,10,2,14,2,2},b[10];intx,i,j=0,find=false;scanf("%d",&x);for(i=0;i<10;i++){if(x==table[i]){find=true;b[j++]=i;}if(find==true){printf("%d在table數(shù)組中，其索引值為：\n",x);for（inti=0;i<j;i++)printf("%3d",b[i]);}else

printf("沒有找到數(shù)%d\n",x);}return0;}數(shù)組是用于按順序存儲同類型數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。如果有一個一維數(shù)組，它的每一個元素是類型相同的一維數(shù)組（數(shù)組的類型相同包括其大小相同并且各元素的類型相同）時，就形成了一個二維數(shù)組。

二維數(shù)組如圖8-2所示，當(dāng)一維數(shù)組age的各元素age[0]，age[1]，age[2]又分別是一個一維數(shù)組時，便可以用一個二維數(shù)組來描述。

二維數(shù)組定義：

類型說明

數(shù)組名[常量表達(dá)式1][常量表達(dá)式2]

數(shù)組元數(shù)的排列順序:按行存放，即在內(nèi)存中先順序存放第一行的元素，再存放第二行的元素。行數(shù)列數(shù)數(shù)組元素個數(shù)=行數(shù)*列數(shù)inta[3][2]a[0][1]a[1][0]a[1][1]a[2][0]a[2][1]014523a[0][0]a[0][0]a[0][1]a[1][0]a[1][1]a[2][0]a[2][1]二維數(shù)組各元素在內(nèi)存中的排列順序號假設(shè)有一個m×n的二維數(shù)組a，其中第i行第j列元素a[i][j]在數(shù)組中的位置計(jì)算公式為：i×n+j+1。inta[3][4]對一個元素a[i][j]，在它前面有i行，這i行共有i×n個元素。在a[i][j]所在的行中，a[i][j]前面還有j個元素，因此在數(shù)組a中a[i][j]前面共有(i×n+j)個元素。那么a[i][j]就是第(i×n+j)+1個元素。如果順序號從0算起，那么a[i][j]在a數(shù)組中的順序號計(jì)算公式為i×n+j。a[i][j]的順序號為2×4+1=9。即按從0號算起的話，它的順序號為9，或者說它前面有9個元素，如圖8-4所示。例

inta[2][3]={{1,2,3},{4,5,6}};a[0][0]a[0][1]a[0][2]a[1][0]a[1][1]a[1][2]123456分行全部賦初值

例

inta[2][3]={1,2,3,4,5,6};a[0][0]a[0][1]a[0][2]a[1][0]a[1][1]a[1][2]123456全部元素賦初值

例

inta[][3]={1,2,3,4,5,6};a[0][0]a[0][1]a[0][2]a[1][0]a[1][1]a[1][2]123456全部元素賦初值第一維可省例

inta[2][3]={1,2,4};a[0][0]a[0][1]a[0][2]a[1][0]a[1][1]a[1][2]124000部分元素賦初值例

inta[][3]={{1},{4,5}};a[0][0]a[0][1]a[0][2]a[1][0]a[1][1]a[1][2]100450賦初值時指定行數(shù)第一維可以省略例

inta[2][3]={{1,2},{4}};a[0][0]a[0][1]a[0][2]a[1][0]a[1][1]a[1][2]120400分行部分賦值二維數(shù)組的初始化

二維數(shù)組的應(yīng)用

【例8.11】從鍵盤輸入一個3行4列的矩陣，查找其中的最大數(shù)以及該數(shù)的行、列下標(biāo)?！纠?.7】求數(shù)組元素中的最大值與最小值。inta[10];inti,max,min;for(i=0;i<=9;i++)scanf("%d",&a[i]);max=min=a[0];for(i=0;i<=9;i++){}if(a[i]<min)min=a[i];if(a[i]>max)max=a[i];找出最大值和最小值的位置？,m,n{min=a[i];m=i;}{max=a[i];n=i;}

【例8.11】從鍵盤輸入一個3行4列的矩陣，查找其中的最大數(shù)以及該數(shù)的行、列下標(biāo)。inta[3][4],i,j,max;for(i=0;i<3;i++)for(j=0;j<4;j++)scanf("%d",&a[i][j]);max=a[0][0];,m,nm=n=0;if(max<a[i][j])max=a[i][j];m=i;n=j;

{}for(i=1;i<3;i++)for(j=1;j<4;j++)二維數(shù)組的應(yīng)用

a:123456b:142536【例8.12】矩陣轉(zhuǎn)置，即將矩陣的行和列互換。a[0][0]=1b[0][0]=1a[0][1]=2b[1][0]=2a[1][2]=6b[2][1]=6a[i][j]b[j][i]=for(i=0;i<2;i++)for(j=0;j<3;j++)b[j][i]=a[i][j];課程1課程2課程3學(xué)生1：897856學(xué)生2：8899100學(xué)生3：728061學(xué)生4：607075【例8.13】有a個學(xué)生，每個學(xué)生學(xué)b門課，從鍵盤輸入學(xué)生各門課的成績，分別求每門課的平均成績和每個學(xué)生的平均成績。223287213205main(){intx[5][4],i,j;for(i=0;i<4;i++)for(j=0;j<3;j++)scanf("%d",&x[i][j]);x[0][3]=x[1][3]=x[2][3]=x[3][3]=0;x[4][0]=x[4][1]=x[4][2]=0;for(i=0;i<4;i++)for(j=0;j<3;j++)x[i][3]+=x[i][j];for(i=0;i<4;i++)for(j=0;j<3;j++)x[4][j]=+x[i][j];for(i=0;i<5;i++){for(j=0;j<4;j++)printf("%5d\t",x[i][j]);printf("\n");}}字符數(shù)組

char

數(shù)組名

[常量表達(dá)式]定義格式為：例如：

char

c[5];

C[0]C[1]C[2]C[3]C[4]下標(biāo)不能越界初始化例

charch[5]={'H','e','l','l','o'};ch[0]Hello逐個字符初始化ch[1]ch[2]ch[3]ch[4]

例

charch[5]={'B’,'o','y'};ch[0]Boy\0\0部分初始化ch[1]ch[2]ch[3]ch[4]

例

charch[5]="Boy";ch[0]Boy\0\0字符串常量初始化ch[1]ch[2]ch[3]ch[4]例

charch[6]={"Hello"};charch[6]="Hello";charch[]="Hello";字符串常量初始化ch[0]Helloch[1]ch[2]ch[3]ch[4]\0ch[5]

charch[5]={'H','e','l','l','o'};ch[0]Helloch[1]ch[2]ch[3]ch[4]二維字符數(shù)組的初始化例

chardiamond[][5]={{'','','*'},{'','*','','*'}, {'*','','','','*'},{'','*','','*'},{'','','*'}};二維數(shù)組按行初始化*\0\0**\0****\0*\0\0diamond[0]diamond[1]diamond[2]diamond[3]diamond[4]

例

charfruit[][7]={"Apple","Orange",

"Grape","Pear","Peach"};二維數(shù)組初始化fruit[0]fruit[1]fruit[2]fruit[3]fruit[4]Apple\0\0Orange\0Grape\0\0Pear\0\0\0Peach\0\0應(yīng)用舉例【例8.16】使用%c格式進(jìn)行單個字符的輸入輸出。main(){inti;charc[]={'C','h','i','n','a'};for(i=0;i<5;i++)printf("%c",c[i]);}China【例8.17】使用%s格式對整個字符串的輸入輸出。main(){charc[]={"China"};printf("%s",c);}Chinamain(){inti;charc[]={'C','h','i','n','a'};for(i=0;i<5;i++)printf("%c",c[i]);}【例8.18】整個字符串的輸入輸出。main(){charch[15];printf("Enterastring:");scanf("%s",ch);printf("%s\n",ch);}Wonderful!Wonderful!

charch;scanf("%c",&ch);字符串C語言沒有字符串變量,字符串用字符數(shù)組來處理的

一個字符串用\0作結(jié)束標(biāo)志。

例：

"

hello"有5

個字符，存儲在6

個字符的字符數(shù)組中。

chara[]="hello"

h

e

l

l

o

\0應(yīng)用舉例1、將一個字符串復(fù)制給一個字符數(shù)組

charstr1[20],str2[]=“CCTV.";str1[i]=str2[i];i++;{}

while(str2[i])str1[i]='\0';2、求一個字符串的長度abcdeinti=0;charstr1[]="abcde";while(str1[i])i++;3、將一個指定的字符串翻轉(zhuǎn)輸入的是abcde，輸出的是edcbacharstr1[]="abcde";abcde交換交換首先要求出給定字符串的長度：while(str1[k])k++;intk=0;t=str1[0];str1[0]=str1[k-1-0];str1[k-1-0]=t;與輸入輸出有關(guān)的函數(shù)putchar(a);a=getchar();scanf("%c",&a);printf("%c",a);格式化的字符輸入輸出函數(shù)：scanf("%s",a);printf("%s",a);格式化的字符串輸入輸出函數(shù)：chara;chara[10];1、字符數(shù)組輸出函數(shù)

puts(字符數(shù)組名)stdio.hputs

輸出字符串，可以包含轉(zhuǎn)義字符;

字符數(shù)組必須具有字符串結(jié)束標(biāo)記'\0';

2、字符數(shù)組輸入函數(shù)

gets(字符數(shù)組名)stdio.h

gets

輸入一個字符串到字符數(shù)組，換行表示輸入字符串結(jié)束;

自動在輸入字符串后加入結(jié)束標(biāo)志'\0';

字符串長小于數(shù)組長度函數(shù)的返回值是數(shù)組的首地址。字符串處理函數(shù)putchar(ch);getchar();【例8.19】用puts輸出一個字符串。main(){charstr[]={"Huabei\nChina"};puts(str);return0;}【例8.20】用gets輸入、用puts輸出一個字符串

#include<stdio.h>main(){charstring[80];gets(string);puts(string);}將字符數(shù)組2

連接到字符數(shù)組1的后面，連接時自動取消字符數(shù)組1后面的結(jié)束標(biāo)志，在連接后的結(jié)束部分自動加上結(jié)束標(biāo)志'\0';結(jié)果存放到字符數(shù)組1中,函數(shù)返回值是字符數(shù)組1的首地址;

字符數(shù)組1要有足夠的空間存放結(jié)果;3、連接函數(shù)strcatstrcat(字符數(shù)組名1,字符數(shù)組名2)string.h【例8.21】字符串連接函數(shù)strcat的用法。#include"string.h"main(){charstr1[30]={"Thehouseis"};charstr2[]={"neartheriver."};printf("%s\n",strcat(str1,str2));return0;}將字符串2

復(fù)制到字符數(shù)組1,包括

'\0';字符數(shù)組1

必須有足夠的空間存放結(jié)果;字符串2可以是數(shù)組名?？梢詫⒆址?前面的若干個字符賦值到字符數(shù)組1中去。不能用賦值語句將一個字符串賦值給字符數(shù)組4、拷貝函數(shù)strcpystrcpy(字符數(shù)組1,字符串2)string.h【例8.22】字符串拷貝函數(shù)strcpy的用法。#include"string.h"main(){charstr1[20],str2[]="BVTC.";strcpy(str1,str2);puts(str1);return0;}strcpy和strcat應(yīng)用舉例#include<string.h>#include<stdio.h>main(){charstr1[25];charstr2[]="",str3[]="C++",str4[]="Turbo";strcpy(str1,str4);strcat(str1,str2);strcat(str1,str3);printf("%s\n",str1);}TurboC++TrboC++0123456789u\024…….Trbo0123456789u\024…….…….Trbo\00123456789u24…….…...6、比較函數(shù)

strcmp(字符串1,字符串2)

string.h7、字符串轉(zhuǎn)小寫函數(shù)strlwr(字符串)8、字符串轉(zhuǎn)大寫函數(shù)strupr(字符串)

5、測串長函數(shù)

strlen(字符數(shù)組)

string.h

返回字符串的長度;

函數(shù)的值是字符串的實(shí)際長度,不包括

'\0'.（1）charchars[10]={'A','\0','B','C','\0','D'};（2）chars[]="\t\b\\\0will\n";（3）chars[]="\x69\072\n";結(jié)果：133例strlen(s)的結(jié)果：【例8.25】strlwr函數(shù)的用法。#include"string.h"main(){charmst[50]="ABCDEfghij1234567890";printf("%s\n",mst);printf("%s\n",strlwr(mst));return0;}【例8.26】strupr函數(shù)的用法。#include"string.h"main(){charmst[50]="ABCDEfghij1234567890";printf("%s\n",mst);printf("%s\n",strupr(mst));return0;}字符數(shù)組的使用

【例8.27】編寫程序?qū)崿F(xiàn)如下功能：把字符串中所有的字符右移一個位置，串中的最后一個字符移到最前面，即abcdef\0\0fedcbafstrlen(s)

chars[80]

t=s[strlen(s)-1];

s[i]=s[i-1];

for(i=strlen(s)-1;i>0;i--)

s[0]=tmain(){chars[80],temp;inti,len;clrscr();printf("inputastring:");gets(s);len=strlen(s);temp=s[len-1];for(i=len-1;i>0;i--)s[i]=s[i-1];s[0]=temp;puts(s);}【例8.28】利用二維字符數(shù)組對給定的字符串排序。

#include"string.h"#defineNUM5main(){chartemp[10];charnation[][10]={"Russia","France","Britain","America","China"};inti,j,done;for(i=0;i<5;i++)printf("%s",nation[i]);printf("\n");for(i=0;i<NUM-1;i++){done=0;

for(j=0;j<NUM-1-i;j++)

{if(strcmp(nation[j],nation[j+1])>0){strcpy(temp,nation[j]);strcpy(nation[j],nation[j+1]);strcpy(nation[j+1],temp);done=1;}if(!done)break;}}for(i=0;i<NUM;i++)printf("%s\t",nation[i]);}8.3.5常數(shù)數(shù)組無論是一位數(shù)組，多維數(shù)組，還是字符數(shù)組，都可以通過在聲明的開始部分加上關(guān)鍵字const而成為“常量”：const

charch[]={'2','3','4','5','6','7','8','9','t','J','Q','k','A'};把數(shù)組聲明為const有兩個好處：它表明程序不可能改變數(shù)組元素的值，給我們會帶來閱讀理解的方便，還有一個好處就是，它有助于編譯器發(fā)現(xiàn)錯誤，因?yàn)閏onst會告訴編譯器，該數(shù)組元素的值不可能被修改。8.3.6C99標(biāo)準(zhǔn)中的變長數(shù)組在前面8.1節(jié)中我們說到，數(shù)組的長度必須用常量表達(dá)式進(jìn)行定義，但在C99標(biāo)準(zhǔn)中有時也可以使用非常量表達(dá)式，下面的程序是對【例8.4】的修改。#include"stdio.h"main(){inti,n;scanf("%d",&n);

inta[n];

for(i=0;i<n;i++)scanf("%d",&a[i]);printf("\n輸出數(shù)組a：");for(i=0;i<n;i++)printf("a[%d]=%d",i,a[i]);return0;}【例8.4】一維數(shù)組的輸入與輸出。#include"stdio.h"main(){inti;

inta[4];

printf("\n輸入數(shù)組a(共4個整數(shù))：");for(i=0;i<4;i++)scanf("%d",&a[i]);printf("\n輸出數(shù)組a：");for(i=0;i<4;i++)printf("a[%d]=%d",i,a[i]);}直接插入排序法

直接插入排序法是按元素原來的順序，先將下標(biāo)為0的元素作為已排好數(shù)據(jù)，然后從下標(biāo)為1的元素開始，依次把后面的元素按大小插入到前面的元素中間，直到將全部元素插完為止，從而完成排序功能。732597t=a[1]a[1]=a[0]3a[0]=t372t=a[2]a[2]=a[1]a[1]=t3727322t=a[1]a[1]=a[0]a[0]=t325t=a[i]

j=i-1;

while(j>=0&&t<a[j]){a[j+1]=a[j];

j--;}a[j+1]=t;237575【例8.29】用插入排序法對數(shù)組元素進(jìn)行排序。#include"stdio.h"main(){inti,j;inta[5],t;printf("請輸入5個整數(shù)：");for(i=0;i<5;i++)scanf("%d",&a[i]);for(i=1;i<5;i++){t=a[i];j=i-1;

while(j>=0&&t<a[j]){a[j+1]=a[j];j--;}a[j+1]=t;}printf("排序結(jié)果為：");for(i=0;i<5;i++)printf("%5d",a[i]);return0;}基本思想:shell排序允許第一次跳過較大的間隔去和后面的元素進(jìn)行比較再跳過較小的間隔和后面的元素進(jìn)行比較直到間隔為1才進(jìn)行相鄰元素的比較。

間隔的簡單方案:間隔是數(shù)組長度的一半

原始數(shù)據(jù)：9817634541shell排序跳步為：10/2=5981763454133817694541834176985411534176985417434146985716134141985764jump=5;5/2=23414198576jump=2;3114341985764414341985763114143985761414398576**********1414357689for(i=0;i<n-jump;i++)j=i+jump;if(a[i]>a[j]){t=a[i];a[i]=a[j];a[j]=t;}{}jump=jump/2;

while(jump>=1){}#defineM500main(){intt,i,j,n,jump,count,times,a[M],alldone;scanf("%d",&n);for(i=0;i<=n-1;i++)scanf("%d",&a[i]);}count=times=0;jump=n/2;while(jump>=1){alldone=1;while(alldone==1){alldone=0;for(i=0;i<n-jump;i++){j=i+jump;

if(a[i]>a[j]){t=a[i];a[i]=a[j];a[j]=t;alldone=1;times++;}}count++;

}jump=jump/2;}for(i=0;i<=n-1;i++)

{printf("%3d",a[i]);if((i+1)%10==0)printf("\n");}printf("\n比較次數(shù)=%d\n交換次數(shù)=%d\n",count,times);}二分查找

二分查找又稱為對半查找。它的基本意思是：假定數(shù)據(jù)是按升序排列的，對給定值k，從序列的中間位置開始比較，如果當(dāng)前位置值等于k，則查找成功；否則若k小于當(dāng)前位置值，則在序列的前半段數(shù)據(jù)中繼續(xù)查找；若k大于當(dāng)前位置值，則在序列的后半段數(shù)據(jù)中繼續(xù)查找，直到找到給定值k，則查找成功；或表示序列查找范圍的上、下界數(shù)值顛倒，查找不成功。01245789leftrightmid=(left+right)/2;mid要求查找給定值k=2

if(k==table[mid])if(k<table[mid])right=mid-1;01245789leftrightmid

else

left=mid+1;01245789leftrightmid

find=1;elsewhile(!find&&left<right){}find=0;【例8.32】二分查找實(shí)例。要求用戶輸入一個數(shù)，輸出有關(guān)查找信息。#include"stdio.h"#defineN10main(){intk,i;inttable[N]={0,2,4,6,8,10,12,14,16,18};intfind=0;printf("請輸入要找的數(shù)：");scanf("%d",&k);while(!find&&left<right){mid=(left+right)/2;if(k==table[mid])find=1;

else{if(k<table[mid])right=mid-1;elseleft=mid+1;} } if(find==1)printf("%d在table[%d]中\(zhòng)n",k,mid);elseprintf("沒有找到數(shù)%d\n",k);return0;}1：[4938659776132730]j13492：13

[38659776492730]27383：1327

[659776493830]4：132730

[9776493865]5：13273038

[76496597]6：1327303849

[7665