1、計(jì)算概論 (Introduction to Computing),主講人：馬思偉 北京大學(xué)數(shù)字媒體研究所 ,第十二講 字符串,一維數(shù)組的定義,數(shù)組定義方法如下： 數(shù)據(jù)類型 變量名 數(shù)組元素個(gè)數(shù)= 數(shù)組元素初值; 其中“= 數(shù)組元素初值 ”部分可以省略。 一些數(shù)組定義的例子： int score5; char cards4 = a, 0, r, W; float point2 = 2.56, 23.43; double distances4 ;,一維數(shù)組的數(shù)據(jù)存儲(chǔ),多維數(shù)組,二維數(shù)組的定義：數(shù)組的數(shù)組 類型 變量名數(shù)組行數(shù)數(shù)組列數(shù)=初值列表,初值列表 二維數(shù)組的例子： int matrix101

2、0=0; int n2323=1,2,3,2,4,6; double scoresSTUDENT_NUMCOURSE_NUM; 其他多維數(shù)組可以此類推,多維數(shù)組數(shù)據(jù)存儲(chǔ),二維數(shù)組在內(nèi)存中的一維順序排放 for (j=0; j3; j+) for(i=0; i4; i+) scanf(“%d”, ,關(guān)于課堂練習(xí),編程序產(chǎn)生楊輝三角 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1,#include #define i 10 #define j 10 void main() int aij; for(i=0, i10, i+) for(j=0, j=i; j+) if(j=0|j=i)

3、aij=1; else aij=ai-1j-1+ai-1j; printf(“%d”, aij) return 0; ,#include int main() int yanghuiij; int i=0, j=0; for(i=0; i5; i+) for(j=1, j5; j+) if(j=0|j=i) yanghuiij=1; printf(“%d”, yanghuiij); else yanghuiij=yanghuii-1j-1+yanghuii-1j; printf(“%d”, yanghuiij); Return 0 ,#include int main() int a55, i

4、, j; a00=1; for(i=1; i5; i+) for(j=0, ji; j+) if(j1) aij=ai-1j; else aij=ai-1j+ai-1j-1; ,for(i=0; i5; i+) for(j=0, j字符串2，返回一個(gè)正整數(shù)；字符串1返回一個(gè)負(fù)整數(shù)。字符大小以ASCII碼比較 int strcmp(char str1, char str2) int i=0; while (str1i!=0 ,字符串處理函數(shù),測(cè)試字符串長度函數(shù)strlen() 一般調(diào)用格式：strlen(str) 其中，str可以是地址表達(dá)式（一般為數(shù)組名或指針變量）， 也可以是字符串常量。 功

5、能：統(tǒng)計(jì)字符串str中字符的個(gè)數(shù)（不包括結(jié)束符0）。 返回值：字符串中實(shí)際字符的個(gè)數(shù)。 如：char str10=china; printf(%d,stren(str); 輸出結(jié)果是5，不是10，也不是6。,字符串處理函數(shù),字符串小寫變大寫函數(shù)strupr() 一般調(diào)用格式：strupr(str) 其中，str可以是地址表達(dá)式（一般為數(shù)組名或指針變量）， 也可以是字符串常量。 功能：將字符串中的小寫字母轉(zhuǎn)換成大寫字母。 返回值：str的值，即字符串的首地址。 如：puts(strupr(aB3c); 輸出結(jié)果為：AB3C。,字符串處理函數(shù),字符串大寫變小寫函數(shù)strlwr() 一般調(diào)用格式：s

6、trlwr(str) 其中，str可以是地址表達(dá)式（一般為數(shù)組名或指針變量），也可以是字符串常量。 功能：將字符串中的大寫字母轉(zhuǎn)換成小寫字母。 返回值：str的值，即字符串的首地址。 如：puts(strupr(aB3c); 輸出結(jié)果為：ab3c。,字符串應(yīng)用,求字符串中大寫字母的個(gè)數(shù) #include int main() char str256; int count; scanf(“%s”, str); for (i=0; stri !=0; i+) if (stri=A ,字符串應(yīng)用,比較兩個(gè)字符串的大小，輸入兩個(gè)字符串，輸出兩個(gè)字符串比較的結(jié)果 #include int main()

7、char s1256, s2256; int cmp; scanf(“%s”, str); for (; s1i=s2i ,二維字符數(shù)組,存放多個(gè)字符串,char c510=“Basic”,“Foxpro”,“C+”; /可存放5個(gè)字符串，每串最大9個(gè)字符 char c10=Basic,Foxpro,C+; /初始化字符串的個(gè)數(shù)即為數(shù)組的行數(shù),二維字符數(shù)組,輸入輸出,char c510; for (i=0; i5; i+) scanf(“%s”, ci); printf(%s”, ci); ,思考題,問題描述 有 n 個(gè)人，編號(hào)為 1, 2, . . ., n, 站成一圈。沿著圈順序數(shù)，每到第

8、m個(gè)人就把他殺掉，這樣一直進(jìn)行下去，直到只剩下一個(gè)人，那個(gè)人就活下來。約瑟夫很聰明，他總會(huì)想辦法站到一個(gè)合適的位置上，使得自己能夠成為最后一個(gè)，從而活下來。例如：n = 6 ， m = 5 時(shí)，被殺的順序是5, 4, 6, 2, 3 ，而 1 最終活下來。 給定n, m,求出最后留下的人的編號(hào)位置,1,2,3,4,5,6,1,2,3,4,6,1,2,3,6,1,2,3,1,3,start,end,start,end,start,end,end,start,start,end,約瑟夫環(huán)問題,1。使用數(shù)組，刪除人移動(dòng)數(shù)組 2。使用數(shù)組，刪除人用一個(gè)標(biāo)記表示，不用移動(dòng)數(shù)據(jù),1,2,3,4,5,6,1

9、,2,3,4,6,1,2,3,6,1,2,3,1,3,start,end,start,end,start,end,end,start,start,end,1,2,3,4,5,6,start,end,start,end,start,end,end,start,start,end,1,2,3,4,-1,6,1,2,3,-1,-1,6,1,2,3,-1,-1,-1,1,-1,3,-1,-1,6,約瑟夫環(huán)問題,3。數(shù)學(xué)解法，復(fù)雜度低 n個(gè)人的序列 1 2 3 4m-1 m m+1 .n 殺掉一個(gè)人的序列 1 2 3 4m-1 m+1 .n 重排序列 m+1 .n 1 2.m-1 x序號(hào) 重新編號(hào)序列n-1人序列 1 2 3 .n-1 x 序號(hào) x = (m+x)%n . 最后 剩1個(gè)人 1,約瑟夫環(huán)問題,一直到最后剩一個(gè)人 1-標(biāo)號(hào)x,記為number 上一層的number number = (number+m)%2 一般化表示，對(duì)有i個(gè)人的序列，序號(hào)為 number i= (numberi-1+m)%i,課堂練習(xí),將字符串中的重復(fù)字符變?yōu)橐粋€(gè)字符輸出，如 abbccceb輸出為abceb,作業(yè),1、從鍵盤輸