喬林計算機程序設計基礎Email:qiaolin@Tel:62780973清華大學計算機科學與技術(shù)系第八章

數(shù)組與字符串學習目標理解數(shù)據(jù)類型及數(shù)據(jù)在內(nèi)存中是如何存儲的了解數(shù)組的意義及數(shù)組的使用方法了解字符串的意義及字符串的使用方法8.1數(shù)據(jù)類型與數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)的關系數(shù)據(jù)結(jié)構(gòu)指數(shù)據(jù)的組織形式，即數(shù)據(jù)的抽象機制數(shù)據(jù)的邏輯結(jié)構(gòu)：元素間的邏輯關系線性數(shù)據(jù)結(jié)構(gòu)與非線性數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)的物理結(jié)構(gòu)：物理實現(xiàn)方法，與機器有關順序方式、鏈接方式、索引方式、散列方式數(shù)據(jù)結(jié)構(gòu)上的操作：檢索、插入、刪除、排序等同質(zhì)復合數(shù)據(jù)類型：數(shù)據(jù)元素具有同樣相同的性質(zhì)8.2數(shù)組數(shù)組的下標下標從0開始，一般使用半開半閉區(qū)間例：for(i=0;i<n;++i)a[i]=i;數(shù)組的內(nèi)部表示按維順序存放數(shù)組的基地址，元素的地址數(shù)組下標越界問題程序不檢查下標越界，為什么？數(shù)組應用示例一通過鍵盤輸入10個整數(shù)，然后逆序打印#include<stdio.h>#defineE10voidGet(int

a[],int

n);voidReverse(int

a[],int

n);voidSwap(int

a[],int

x,int

y);voidPrint(int

a[],int

n);voidmain(){

int

array[E];

Get(array,E);

Reverse(array,E);

Print(array,E);}數(shù)組應用示例一voidGet(int

a[],int

n){int

i;for(i=0;i<n;i++)scanf(“%d\n“,&a[i]);}voidReverse(int

a[],int

n){int

i;for(i=0;i<n/2;i++)Swap(a,i,n–i–1);}voidSwap(int

a[],int

x,int

y){int

t;t=a[x];a[x]=a[y];a[y]=t;}voidPrint(int

a[],int

n){int

i;for(i=0;i<n;i++)printf(“%d\n“,a[i]);}數(shù)組作為函數(shù)參數(shù)傳遞數(shù)組時需要傳遞元素個數(shù)信息。為什么？傳遞的其實是數(shù)組基地址，不提供元素個數(shù)信息就無法確知元素有多少個數(shù)組作為函數(shù)參數(shù)不恰當?shù)臄?shù)組傳遞方法數(shù)組參數(shù)聲明錯誤例：voidReverse(int

a[n]);不能在參數(shù)列表中使用變量聲明數(shù)組數(shù)組參數(shù)聲明不恰當例：voidReverse(int

a[10]);魔數(shù)10：在分析函數(shù)聲明時，編譯器忽略之，只對函數(shù)內(nèi)部代碼有意義函數(shù)只能操作10個元素的整數(shù)數(shù)組數(shù)組作為函數(shù)參數(shù)多維數(shù)組的傳遞方法：指定數(shù)組元素個數(shù)正確：voidDisplayBoard(charboard[19][19]);正確：voidDisplayBoard(charboard[19][],int

n);錯誤：voidDisplayBoard(charboard[][],int

m,int

n);數(shù)組應用示例二素數(shù)查找的埃拉托色尼篩法在公元前三世紀，希臘天文學家Eratosthenes發(fā)明了一種算法，用來找出某一范圍內(nèi)的全部素數(shù)算法過程：首先列寫從2到n的整數(shù)，假設n=20將第一個數(shù)圈起，表明已發(fā)現(xiàn)了一個素數(shù)，并將數(shù)列中所有該素數(shù)的倍數(shù)打上×，因為它們一定不是素數(shù)重復上述步驟，直到所有整數(shù)或者被圈起或者打上叉數(shù)組應用示例二#include<stdio.h>#defineMax1000typedefenum{FALSE,TRUE}bool;boolIsPrime[Max];voidInit();voidGetPrime();voidOutput();voidmain(){

Init();

GetPrime();

Output();}數(shù)組應用示例二voidInit(){int

i;for(i=0;i<Max;i++)IsPrime[i]=TRUE;}voidGetPrime(){

inttmp;

int

i;for(i=2;i<Max;i++)if(IsPrime[i]){

tmp=i+i;while(tmp<Max){IsPrime[tmp]=FALSE;tmp+=i;}}}數(shù)組應用示例二voidOutput(){

int

i;

int

count=0;for(i=2;i<Max;i++)if(IsPrime[i]){

count++;

printf(“Prime%d:%4d\t“,count,i);if(count%5==0)printf(“\n“);}

printf(“\nTotal:%4d\n“,count);}數(shù)組應用示例三學生成績查詢系統(tǒng)，假設有五名學生七門考試，要求程序完成如下功能根據(jù)輸入的學號，給出每次考試成績及平均成績根據(jù)輸入的考試號，打印出該次考試中每個學生的成績，并給出平均成績根據(jù)學號查出學生某次考試成績錄入考試成績數(shù)組應用示例三#include<stdio.h>voidmain(){

int

select;int

i,j;int

score[6][8];int

average=0;int

sum=0;do{

printf(“本程序有4項功能\n“);

printf(“1.根據(jù)學號查詢學生成績\n“);

printf(“2.根據(jù)考試號統(tǒng)計學生成績\n“);

printf(“3.根據(jù)考試號和學號查詢學生成績\n“);

printf(“4.成績錄入\n“);

printf(“0.退出\n“);

printf(“請輸入0~4進行選擇：\n“);

scanf(“%d\n“,&select);…數(shù)組應用示例三switch(select){case0:

printf(“Ok\n“);exit(0);break;case1:

printf(“輸入學號：”);scanf(“%d\n“,&i);for(j=1;j<8;j++){

printf(“第%d科成績是%d\n“,j,score[i][j]);

sum+=score[i][j];}

average=sum/7;

printf(“學生的平均成績是%d\n“,average);break;…數(shù)組應用示例三case2:

printf(“輸入考試號：”);scanf(“%d\n“,&j);for(i=1;i<6;i++){

printf(“第%d號學生本科成績是%d\n“,i,score[i][j]);

sum+=score[i][j];}

average=sum/5;

printf(“學生本科平均成績是%d\n“,average);break;case3:

printf(“輸入學生學號和考試號：”);

scanf(“%d%d\n“,&i,&j);

printf(“第%d號學生第%d科考試成績是%d\n“,i,j,score[i][j]);break;…數(shù)組應用示例三case4:

printf(“輸入成績：\n“);for(i=1;i<6;i++)for(j=1;j<8;j++)

scanf(“%d\n“,&score[i][j]);break;default:break;}}while(1);}本程序的設計有什么問題？字符串數(shù)組型字符串for(i=0;i<n;++i)str[i]=(char)(‘a(chǎn)’+i);指針型字符串for(p=str;*p!=‘\0’;++p)*q=*p;作為抽象數(shù)據(jù)的字符串typedefchar*string;字符串應用示例一編寫函數(shù)FindFirstVowel()，找出字符串中第一個元音字母intFindFirstVowel(charstr[],intn){

int

i;for(i=0;i<n;i++)if(IsVowel(str[i]))returni;return1;}intIsVowel(charch

){if(!isalpha(ch

))return0;

ch=toupper(ch

);if(ch==‘A‘||ch==‘E‘||ch==‘I‘||ch==‘O‘||ch==‘U‘)return1;return0;}使用字符數(shù)組字符串應用示例一編寫函數(shù)FindFirstVowel()，找出字符串中第一個元音字母intFindFirstVowel(charstr[]){

int

i;for(i=0;str[i]!=‘\0‘;i++)if(IsVowel(str[i]))returni;return1;}使用字符數(shù)組字符串應用示例一編寫函數(shù)FindFirstVowel()，找出字符串中第一個元音字母intFindFirstVowel(char*str){char*p;for(p=str;*p!=‘\0‘;p++)if(IsVowel(*p))return(p

str);return1;}使用字符指針字符串應用示例一編寫函數(shù)FindFirstVowel()，找出字符串中第一個元音字母intFindFirstVowel(string

str){

int

i;for(i=0;i<strlen(str);i++)if(IsVowel(IthChar(str,i))returni;return1;}charIthChar(stringstr,inti){returnstr[i];}使用抽象字符串字符串變量數(shù)組型字符串：使用前已經(jīng)分配空間例：charstr[9]=“Tsinghua”;Tsinghua\0str指針型字符串：使用前未分配空間例：char*p;p=str;pTsinghua\0str字符串應用示例二編寫程序，將英語人名從姓在后的形式轉(zhuǎn)換為姓在前的形式，如“FirstMiddleLast”轉(zhuǎn)換為“Last,FirstMiddle”#include<stdio.h>#include<string.h>#defineMaxName40staticvoidInvertName(charresult[],charname[]);字符串應用示例二voidmain(){charstandardName[MaxName+1];charinvertedName[MaxName+1];

printf(“Thisprogramconvertsanameinstandardorder\n“);

printf(“intoinvertedorderwiththelastnamefirst.\n“);

printf(“Indicatetheendofinputwithablankline.\n“);while(1){

printf(“Name:“);

gets(standardName

);if(strlen(standardName)==0)break;

InvertName(invertedName,standardName

);

printf(“%s\n“,invertedName

);}}字符串應用示例二staticvoidInvertName(charresult[],charname[]){

intlen;char*p;

len

=strlen(name);

p=strrchr(name,‘‘);if(p!=0)len++;if(len

>MaxName){printf(“Nametoolong\n“);exit(1);}if(p==0)strcpy(result,name);else{

strcpy(result,p+1);strcat(result,“,“);

strncat(result,name,p

name);

result[len]=‘\0‘;}}字符串應用示例三使用字符串處理函數(shù)編寫游戲hangman在游戲中，電腦隨機從某個范圍內(nèi)選擇一個單詞，然后輸出一列短橫，每個短橫代表一個字母使用者猜測該單詞，如果猜到了單詞中的字母，就會顯示出該字母所在的位置，而其他字母仍用短橫表示如果所猜的字母不在單詞中，就是一次不成功的猜測重復上述步驟，直到猜出整個單詞，或者累計8次不成功猜測字符串應用示例三#include<stdio.h>#include<dos.h>#include<string.h>#include<stdlib.h>#include<time.h>voidbegin(){//telluserhowtoplaythegame

printf(“Let‘splayhangman!Iwillpickasecretword.\n“);

printf(“Oneachturn,youguessaletter.\n“);

printf(“Iftheletterisinthesecretword,Iwillshowyouwhereitappears.\n“);

printf(“Ifyoumakeanincorrectguess,partof\n“);

printf(“yourbodygetsstrunguponthescaffold.\n“);

printf(“Theobjectistoguessitbeforehanged.\n\n“);return;}字符串應用示例三voidrun(char*letters,int

m)//themainpartofthegame{

/*guessmarksifaguessiscorrect,kmarksifthewordisguessedcorrectly*/

int

i,j,k,l,p,q,z,guess,times=8;

intabc[26];/*26markstomemorizeiftheletterguessed*/

int

condition[20];/*20markstomemorizeiftheletterinthesecretwordguessed*/charcc,tmp;/*markthatnoneofthe

lettershasbeenguessed*/for(j=0;j<m;j++)condition[j]=1;for(j=0;j<26;j++)abc[j]=0;

k=0;/*Thewordhasnotbeenguessed*/字符串應用示例三//checkthatthegamehasnotendedwhile((k==0)&&(times!=0)){

printf(“thewordnowlookslikethis:“);for(i=0;i<m;i++)//printthewordinsecretformif(condition[i]==1)

printf(““);else

printf(“%c“,letters[i]);

printf(“\n“);if(times>1)

printf(“Youhave%dguessesleft.\n\n“,times);else

printf(“Youhaveonlyoneguessleft.\n\n“);字符串應用示例三

printf(“Yourguess:“);

guess=0;

tmp=getchar();if(tmp!=‘\n‘)cc=tmp;

/*readotherletterssothattheydon'taffecttheguess*/for(q=0;getchar()!=‘\n‘;q++);for(p=0;p<m;p++)if(letters[p]==cc){guess=1;condition[p]=1;}if(abc[cc97]==1)//chechiftheletterhasbeenguessed{

guess=2;

printf(“Theletterhasbeenguessed,chooseanother\n“);}

abc[cc97]=1;//markthattheletterhasbeenguessed字符串應用示例三if(guess==0){printf(“\nThereisno%cintheword.\n“,cc);times;}elseif(guess==1)printf(“\nThatguessiscorrect.\n“);

//chechiftheconditionstoendthegamehasbeenreached

l=0;while(l<m){if(