1、大學(xué)程序設(shè)計技能訓(xùn)練（C）,第3講 程序填空,課程安排,9月21日(周二)第1次理論課， 9月28日(周二)第2次理論課， 10月12日(周二)第3次理論課， 10月19日(周二)第4次理論課， 上課時間：18：0020：30,上機安排,9月26日第1次上機 18：0020：30） 10月15日（周五）第2次上機 （18：0020：30） 10月22日第3次上機（周五） （18：0020：30） 10月26日模擬考試（18：0020：30） 11月23日課程考試（18：3020：30）,上機安排,9月26日第1次上機 18：0020：30） 10月15日（周五）第2次上機 （18：0020：3

2、0） 10月26日實驗（18：0020：30） 11月16日模擬考試（18：0020：30） 11月23日課程考試（18：3020：30）,二、程序填空題 ( 本大題 3 道小題 ，每空 2.5 分，共 30 分）。,1. 程序運行時輸出如圖所示的數(shù)字倒三角形 1234567 12345 123 1,源程序： #include void main() int i,j; _1_; for(i=1;i0;j-) printf(%d, k ); _2_; putchar(_3_); ,int k,k+,n,考核點: 變量的定義, 循環(huán)控制變量的變化 輸出換行問題,2. 輸入一行字符串，分別統(tǒng)計字符串

3、中各元音字母（AEIOU）的個數(shù)（不分大小寫）。 源程序：,#include void main() char a80; int n5=0,0,0,0,0; /* 數(shù)組n存放各元音字母個數(shù) */ _1_; gets(a);,int i,for(_2_; ai!=0; i+) switch(_3_) case A: case a: n0+; break; case E: case e: n1+; break; case I: case i: n2+; break; case O: case o: n3+; break; case U: case u: n4+; break; ,i=0,ai,fo

4、r(i=0;i5;i+) printf(%dn,_4_); /* 輸出各元音字母個數(shù) */ ,ni,例 輸入一行字符，統(tǒng)計其中有多少個單詞,字符數(shù)組和字符串,字符數(shù)組和字符串,#include main() char string81; int i, num=0,word=0; char c; gets(string); for(i=0;(c=stringi)!=0;i+) if(c= ) word=0; else if(word=0) word=1; num+; printf(There are %d words in the linen,num); ,字符數(shù)組和字符串,2、以下程序的功能是

5、：按順序讀入10名學(xué)生4門課程的成績，計算出每位學(xué)生的平均分并輸出，請?zhí)羁帐钩绦蛲暾?【程序2】 #include stdio.h main() int n,k; float score,sum,ave; for(n=1;n=10;n+) _（1）_; for(_（2）_) scanf(%f,_（3）_); sum+=score; _（4）_; printf(NO%d:%fn,n,ave); ,#include stdio.h main() int n,k; float score,sum,ave; for(n=1;n=0,i-,以下程序輸入n和n個大于1的正整數(shù)，輸出其中素數(shù)。 如輸入：5

6、 19 93 11 37 15 則輸出：19 11 37 例示說明：先輸入n為5，再輸入5個正整數(shù)，輸出5個整數(shù)中的素數(shù),源程序： #include #include void main() int n, a, i, j, ct; scanf( %d, ,in,ct=0,a%j=0,考核點: 變量的定義, 計數(shù)器清空 函數(shù)定義與調(diào)用,以下程序從文件“student.txt”讀取學(xué)生的學(xué)號、姓名、平時成績和考試成績，再從鍵盤上輸入一個成績，將所有考試成績達(dá)到或超過該成績的學(xué)生數(shù)據(jù)寫到新的文本文件“studentD.txt”。文件的最后一行為0表示學(xué)生數(shù)據(jù)結(jié)束。 設(shè)文件student.txt的內(nèi)容

7、為 101 Zhao 95 58 103 Qian 75 81 105 Sun 99 91 107 Li 80 67 0,運行時鍵盤輸入：80 則生成新文件studentD.txt的內(nèi)容為： 103 Qian 75 81 105 Sun 99 91 0 例示說明：student.txt中考試成績在80分以上的Qian與Sun信息寫到studentD.txt,源程序： #include void select( FILE *fp1, FILE *fp2, int x ) int num, score1, score2; char name20; while ( 1 ) num = 0; fsca

8、nf( fp1, %d%s%d%d, ,break,x=score2,void main() FILE *fp1, *fp2; int x; fp1 = fopen( student.txt, r ); fp2 = fopen( studentD.txt, _（3）_ ); if ( fp1=NULL | fp2=NULL ) /* 文件打開失敗 */ printf( File Open Error!n ); return; scanf( %d, ,w,fp1, fp2, x,程序填空的考核點,基本算法 數(shù)據(jù)結(jié)構(gòu),基本算法,與函數(shù)相關(guān)的算法 判斷素數(shù) 驗證歌德巴赫猜想 求回文數(shù) 求兩自然數(shù)的最

9、大公約數(shù)和最小公倍數(shù) 分類統(tǒng)計問題 判別降序數(shù) 進(jìn)制轉(zhuǎn)換,求回文數(shù),編一函數(shù)，功能為判斷一字符串是否為回文?；匚氖侵疙樧x和倒讀都一樣的字符串，如“deed”和“l(fā)evel”是回文。在主函數(shù)中對輸入的5個字符串統(tǒng)計其中回文的個數(shù)。輸出形式見圖2.6.2。函數(shù)形式為：int huiwen(char s); 提示：構(gòu)造一個逆序的字符串， 思想：數(shù)組的首尾元素進(jìn)行交換，其數(shù)組元素下標(biāo)分別為0和n-1（n為字符串長度），接著對剩下的首尾元素進(jìn)行交換，其數(shù)組元素下標(biāo)分別為1和n-2，以此類推，即下標(biāo)為i的數(shù)組元素和下標(biāo)為n-i-1的數(shù)組元素交換，直到所有元素均交換或只剩一個元素為止，交換的次數(shù)為n/2。,

10、求回文數(shù),#include #include int huiwen(char s) int i,n=0; char ch,s180; strcpy(s1,s); /原來的字符串保留在s1中 while(sn)n+; /求字符串長度 for(i=0;in/2;i+) /構(gòu)造逆序的字符串 ch=si; si=sn-i-1; sn-i-1=ch; if(strcmp(s1,s)=0) return 1; else return 0; ,void main() char s580,ss580; int i,count=0; printf(輸入5個字符串：n); for(i=0;iap ,求矩陣最大值,

11、在一個34的矩陣中，輸出其中值最大的元素的值，以及它的行號和列號。,求矩陣最大值,#define M 3 #define N 4 #include stdio.h main() int max,i,j,r,c; static int aN=123,94,-10,218,3,9,10,-83,45,16,44,-99; max=a00; for(i=0;imax) max=aij; r=i; c=j; printf(max=%d ,row=%d,colum=%dn,max,r,c); ,找鞍點,找出一個二維數(shù)組中的鞍點，即該位置上的元素在該行中最大，同時在該列中最小。也可能不存在鞍點，如果有，打

12、印出其位置和值。,找鞍點,#include #include int main() int a35,x,y,i,j,k; int max,min; for(i=0;i 1) n! = 1 (n = 0,1) 遞歸函數(shù) fact(n),#include double fact(int n)； int main(void) int n; scanf (%d, ,遞歸出口,遞歸式,折半查找(也稱二分查找 ) 如果順序查找表的元素按照關(guān)鍵字的值有序存放，那么可利用高效的折半查找來完成查詢。 假定元素按關(guān)鍵字的值升序排列，折半查找的思路是將給定的數(shù)據(jù)與有序表中間位置的元素做比較，若兩者相等則查找成功；若

13、前者小于后者則在中間位置左邊的元素中繼續(xù)查找；若前者大于后者則在中間位置右邊的元素中繼續(xù)查找。不斷重復(fù)這一過程直到查找成功，或者直到查找區(qū)間縮小為一個元素時卻仍未找到目標(biāo)，則查找失敗。,折半查找算法的步驟描述如下： 設(shè)置查找區(qū)間初值，設(shè)下界low = 0，設(shè)上界high = length-1。 若lowhigh則計算中間位置mid = (low +high)/2。 若keyamid，則設(shè)low = mid+1并繼續(xù)執(zhí)行步驟； 若key=amid則查找成功，返回目標(biāo)元素位置mid+1（位置從1計數(shù)）。 若當(dāng)low=high時，key!=amid則查找失敗，返回0。,折半查找算法的C語言描述如下：

14、 int BinSearch(int a, int n,int key ) int low, high, mid; low = 0; high = n-1; /設(shè)置查找區(qū)間初值 while (low = high) mid = (low + high) / 2; if(key=amid) return mid+1; /查找成功 else if( keyamid ) high = mid-1; /繼續(xù)在前半?yún)^(qū)間進(jìn)行查找 else low = mid + 1; /繼續(xù)在后半?yún)^(qū)間進(jìn)行查找 return 0; /不存在待查元素 ,對給定有序數(shù)列 5，6，11，17，21，23，28，30，32，40進(jìn)

15、行半查找算法，查找關(guān)鍵字值為30的數(shù)據(jù)元素。則查找過程如下： 第1次： 5，6，11，17，21，23，28，30，32，40 low=0 mid=(0+9)/2 =4 high=9 第2次： 5，6，11，17，21，23，28，30，32，40 low=5 mid=7 high=9,選擇排序（比較排序） 簡單選擇排序的基本思想是：將記錄分為有序和無序兩個序列，假定第k趟排序時，前面的R1，R2，,Rk-1已經(jīng)排好序，而后面的Rk，Rk+1，,Rn仍然無序。則選擇Rk到Rn中的關(guān)鍵字最小的記錄與Rk交換，交換后有序序列增加了第k個記錄。當(dāng)?shù)趎-1趟選擇執(zhí)行完,待排序記錄只剩下1個,就不用再選

16、了。在初始狀態(tài)可以認(rèn)為有序序列為空。,下圖顯示了在序列35，22，16，19，22上應(yīng)用選擇排序的過程。 初始狀態(tài)： 35 22 16 19 22 第1趟 ： 16 22 35 19 22 第2趟 ： 16 19 35 22 22 第3趟 ： 16 19 22 35 22 第4趟 ： 16 19 22 22 35,選擇排序算法C語言描述： void SelectSort( int v , int n ) int i,j,k,temp; for( i=0; in-1; i+ ) int k = i; /k存放最小記錄位置 for( j=i+1; jnext; ,插入一個結(jié)點,s-next=p-n

17、ext p-next=s,s,刪除一個結(jié)點,p-next=p-next-next;,動態(tài)鏈表,結(jié)點在程序執(zhí)行時動態(tài)創(chuàng)建 struct link *s; s=(struct link *)malloc(sizeof(struct link); 刪除結(jié)點需要釋放結(jié)點 free(p); 頭指針，頭結(jié)點和next成員為NULL的結(jié)點控制鏈表的開頭和結(jié)尾。,動態(tài)鏈表的創(chuàng)建(1),1。創(chuàng)建頭結(jié)點，由頭指針指向 sturct link *head,*s,*p; head=(struct link*)malloc(sizeof(struct link);,頭指針 頭結(jié)點 新結(jié)點,P,動態(tài)鏈表的創(chuàng)建(2),創(chuàng)建

18、新結(jié)點 s=(struct link*)malloc(sizeof(struct link); 為新結(jié)點賦值 s-data s-next=NULL; 將新結(jié)點插入入鏈表 p=head;/p指針指向鏈表最后一個結(jié)點 p-next=s; p=s;,動態(tài)鏈表的創(chuàng)建(3),循環(huán)控制多個新結(jié)點的創(chuàng)建和鏈入 （1）個數(shù)控制 （2）輸入特殊標(biāo)志,文件,#include stdio.h main() FILE *fin,*fout; char ch; if(fout=fopen(file_a.dat,w)=NULL) printf(acan not open this file!);exit(0); whil

19、e(ch=getchar()!=) fputc(ch,fout); fclose(fout); printf(nout file:n);,if(fin=fopen(file_a.dat,r)=NULL) printf(acan not open this file!);exit(0); while(!feof(fin) ch=fgetc(fin); putchar(ch); fclose(fin); ,#include stdio.h #define N 3 typedef struct char name20; char num10; USER; void getdata(USER *sp)

20、; void outdata(USER *sp); USER input(); void savedata(USER *sp); void readrec(int i);,void getdata(USER *sp) int i; for(i=0;iN;i+) printf(%d:,i+1); printf(name:); gets(); printf( num:); gets(spi.num); ,main() USER spN; clrscr(); getdata(sp); clrscr(); printf(user listn); outdata(sp); savedat

21、a(sp); readrec(2); ,void outdata(USER *sp) int i; for(i=0;iN;i+) printf(%s,%sn,,spi.num); void savedata(USER *sp) FILE *fp; int i; if(fp=fopen(user.dat,wb)=NULL) printf(file open error); exit(0); for(i=0;iscore=ps2-score; ps2-score=tmp.score; strcpy(,ps1-name); strcpy(ps1-name,ps2-na

22、me); strcpy(ps2-name,); ,void sort(struct student st, int n) int i, j, temp; for(i=0; i sttemp.score) temp=j; swap ( ,void main() int i, score90, score80, score70, score60, score_failed; for(i=0; ilink=top; top=p; ,while(top) p=top ; /* 獲取當(dāng)前結(jié)點 */ putchar(p-info); top=top-link; free(p) ; /* 釋

23、放結(jié)點 */ ,試題五（15分，每個空格3分） 【07試題】,閱讀下列問題描述和相應(yīng)的程序，把應(yīng)填入其中 (n) 處的內(nèi)容寫在答卷紙的對應(yīng)欄內(nèi)。 【問題描述】以下程序輸入10行字符串，要求按字典順序從小到大排序。,試題五（15分，每個空格3分） 【07試題】,【程序5】 #include #define N 10 int biggerthan( char *str1, char *str2 ) /*若字符串str1大于 str2時，則返回1*/ for ( ; *str1 | *str2; (1) ) str1+,str2+ if ( *str1 *str2 ) return (2) ; 1 else if (*str1*str2) return 0 ; return 0; /* 兩個字符串相等 */ ,void main() char lsN100; char *psN, *t; int i, j; for ( i = 0; i N; i+ ) gets( lsi ); psi = lsi; for ( i = 0; i N-1; i+ ) /* 冒泡法排序 */ for ( j = 0; j N-i-1; j+ ) if ( biggerthan( (3) ) ) psj,psj+1 t