C程序設(shè)計(jì)課件4.6

選擇排序思想對(duì)整數(shù)序列{70,83,100,65,10,32,7,65,9},用簡單選擇排序法進(jìn)行升序排序。排序過程演示【例1】用選擇排序法將數(shù)組a中的N個(gè)整型數(shù)升序排序。第1趟:下標(biāo)為0的元素依次與其后面的元素比較,逆序則交換,最終將N個(gè)數(shù)中的最小數(shù)存放到下標(biāo)為0的位置。第2趟:下標(biāo)為1的元素依次與其后面的元素比較,逆序則交換,最終將N-1個(gè)數(shù)中的最小數(shù)存放到下標(biāo)為1的位置。

如此下去,直到剩下一個(gè)最大數(shù)在下標(biāo)為N-1的位置。830123456787083100651032765970831006510327659100100100779791079103279103265791032656579103265657083701006532106598370100653210658370100653265837010065658370657083第1趟:第2趟:第3趟:第4趟:第5趟:第6趟:第7趟:第8趟:思考題：對(duì)N個(gè)整數(shù)排序,需要多少趟？每趟比較多少次？為了避免過多地交換記錄,需對(duì)算法進(jìn)行改進(jìn)第1趟:從N個(gè)元素中找出值最小元素,并與第一個(gè)元素值交換。第2趟:從剩下N-1元素中找出值最小元素,并與第二個(gè)元素值交換。如此下去,直到剩下一個(gè)最大數(shù)在第N個(gè)元素中存放。

#include"stdio.h"#defineN10voidmain(){inti,j,a[N],t;for(i=0;i<N;i++)scanf("%d",&a[i]);

for(=0;i<N-1;i++){}for(i=0;i<N;i++)printf("%4d",a[i]);}for(j=i+1;j<N;j++)if(a[i]>a[j]){t=a[i];a[i]=a[j];a[j]=t;}i選擇排序程序/*輸入N個(gè)待排序的數(shù)*//*排序*//*輸出排序后的N個(gè)數(shù)*/0iN-1已排序的i個(gè)數(shù)據(jù)7010010065100831070836532

65

971070831006532

65

9701234567810701006532

65

97第1趟:第2趟:第3趟:708310032

65

97第4趟:1070836532

65

97第5趟:1070836532

65

97第6趟:10836510032

65

97第7趟:1070836510032

65

97第8趟:

對(duì)整數(shù)序列{70,83,100,65,10,32,7,65,9},用改進(jìn)的簡單選擇排序法進(jìn)行升序排序。10改進(jìn)后排序過程演示思考題：對(duì)N個(gè)整數(shù)排序,需要多少趟？每趟交換多少次？改進(jìn)后選擇排序程序#defineN10#include"stdio.h"voidmain(){inti,j,k,a[N],t;for(i=0;i<N;i++)/*輸入N個(gè)待排序的數(shù)*/scanf("%d",&a[i]);

for(=0;i<N-1;i++)/*排序總共進(jìn)行N-1趟*/{}for(i=0;i<N;i++)/*輸出排序后的N個(gè)數(shù)*/printf("%4d",a[i]);}k=i;/*初始化最小數(shù)的下標(biāo)*/for(j=i+1;j<N;j++)/*尋找最小數(shù)下標(biāo)*/if(a[j]<a[k])k=j;/*記錄新的最小數(shù)下標(biāo)*/if(k!=i){t=a[i];a[i]=a[k];a[k]=t;}/*第i個(gè)數(shù)和最小數(shù)交換*/i程序1?0iN-1已排序的i個(gè)數(shù)據(jù)起泡排序思想

已知整數(shù)序列{70,83,100,65,10,32,7,65,9},采用起泡排序法進(jìn)行升序排序。第1趟:從下標(biāo)為0的元素開始,相鄰兩元素比較,若前者大于后者,交換兩個(gè)元素的值,反復(fù)執(zhí)行N-1次,結(jié)果最大數(shù)存入第N個(gè)元素。第2趟:對(duì)前N-1個(gè)元素進(jìn)行同樣的操作,反復(fù)執(zhí)行N-2次,

結(jié)果次最大數(shù)存入第N-1個(gè)元素。如此下去,直到剩下一個(gè)最小數(shù)在第一個(gè)元素中存放?！纠?】用起泡排序法將數(shù)組a中N個(gè)整型數(shù)升序排序。排序過程演示7070831006510101010101010765977777776565656599999998370656532323232323265﹤﹤﹥﹥﹥﹥﹥﹥﹤﹥﹥﹥﹥﹥﹥﹥﹥﹥﹥﹥﹥﹥﹥﹥﹦﹥﹤﹥﹤﹥﹥﹤﹥﹤﹥初始值第1趟第2趟第3趟第4趟第5趟第6趟第7趟第8趟12345678910010765983706532﹤起泡排序程序#include"stdio.h"#defineN10voidmain(){inti,j,a[N],t;/*輸入待排序的數(shù)據(jù)*/for(i=0;i<N;i++)scanf("%d",&a[i]);/*排序*/

for(=0;i<N-1;i++)/*進(jìn)行N-1趟排序*/{

}/*輸出排序后的數(shù)據(jù)*/for(i=0;i<N;i++)printf("%4d",a[i]);}程序2?for(j=0;j<N-i-1;j++)/*進(jìn)行N-i-1次相鄰元素比較*/if(a[j]>a[j+1])/*若前者大于后者，則交換*/{t=a[j];a[j]=a[j+1];a[j+1]=t;}i0N-i-1N-1已排序的i個(gè)數(shù)據(jù)若初始序列已有序,則沒有必要進(jìn)行n-1趟掃描。#include"stdio.h"#defineN10voidmain(){inti,j,a[N],t,flag=1;for(i=0;i<N;i++)/*輸出待排序的N個(gè)數(shù)據(jù)*/scanf("%d",&a[i]);

for(i=0;flag==1&&i<N-1;i++)/*前一趟有交換,flag=1;否則,flag=0*/{flag=0;for(j=0;j<N-i-1;j++)/*進(jìn)行N-i-1次相鄰元素比較*/if(a[j]>a[j+1])/*若前者大于后者，則交換*/{t=a[j];a[j]=a[j+1];a[j+1]=t;flag=1;}}for(i=0;i<N;i++)/*輸出排序后的數(shù)據(jù)*/printf("%4d",a[i]);}改進(jìn)方法：若某一趟排序后沒有數(shù)據(jù)交換,則排序結(jié)束。改進(jìn)后選擇排序程序【例3】不用函數(shù)strcat(),將兩個(gè)字符串連接并輸出。#include"stdio.h"#include"string.h"voidmain(){chara[81],b[81],*p1,*p2;gets(a);gets(b);p1=a;p2=b;

while(*p1)p1++;/*p1指向a的結(jié)束標(biāo)志*/

while(*p2){*p1=*p2;p1++;p2++;}/*將b復(fù)制到a的尾部*/*p1='\0'

;/*字符串結(jié)束標(biāo)志*/puts(a);}程序3?ABCaDEF\0b\0\0DEFp1p2/*輸入*//*連接*//*輸出*/【例4】輸入一個(gè)英文句子,將每個(gè)英文單詞的頭字母變?yōu)榇髮?單詞之間用空格隔開。解析:若當(dāng)前字符不是空格,但它前面的字符為空格,表示新單詞開始,判斷當(dāng)前字母是否為大寫,若不是,將其變?yōu)榇髮?若當(dāng)前字符和前一個(gè)字符都不是空格,則是原來單詞的繼續(xù),不用判斷當(dāng)前字母的大小寫。#include"stdio.h"#include"string.h"voidmain(){chara[81],*p;intword=0;gets(a);

p=a;

while(*p){

}puts(a);}pword=01owreou\0yY(標(biāo)識(shí)當(dāng)前字符的前一個(gè)字符是否為空格)aAhHif(*p=='

')word=0;elseif(word==0){if(*p>='a'

&&*p<='z'

)*p-=32;word=1;}p++;/*輸入*//*處理*//*輸出*/程序4?【例5】輸出楊輝三角形的前10行。解析：用二維數(shù)組a來存放數(shù)據(jù),對(duì)數(shù)組中的元素a[i][j],若j>i,則a[i][j]的值不用,否則,按下列公式計(jì)算。11112113311464115101051161520156117213535217118285670562881193684126126843691#include"stdio.h"#defineN10voidmain(){inti,j,a[N][N];for(i=0;i<N;i++)for(j=0;j<=i;j++)

if(j==0||j==i)a[i][j]=1;elsea[i][j]=a[i-1][j]+a[i-1][j-1];for(i=0;i<10;i++){for(j=0;j<=i;j++)printf("%4d",a[i][j]);printf("\n");}}程序5?/*計(jì)算下三角陣值*//*輸出下三角陣值*/【例6】將4×4矩陣轉(zhuǎn)置并輸出。解析:

用一個(gè)二維數(shù)組a存放矩陣,下三角的a[i][j]與a[j][i]交換即可#include"stdio.h"#defineN4voidmain(){inti,j,a[N][N],t;for(i=0;i<N;i++)for(j=0;j<N;j++)scanf("%d",&a[i][j]);

for(i=0;i<N;i++)for(j=0;j<i;j++){t=a[i][j];a[i][j]=a[j][i];a[j][i]=t;}for(i=0;i<N;i++){for(j=0;j<N;j++)printf("%4d",a[i][j]);printf("\n");}}程序6?/*輸入*//*轉(zhuǎn)置*//*輸出*/【例7】在一個(gè)N×N矩陣中填入1到N2的數(shù)字(N為奇數(shù)),使得每一列、每一行、每一條對(duì)角線的累加和都相等。

程序7?#include"stdio.h"#defineN3voidmain(){inta[N][N]={0},i,j,m;m=1;i=0;j=N/2;

while(m<=N*N){a[i][j]=m;m++;if(a[(i-1+N)%N][(j-1+N)%N]!=0)i=(i+1)%N;else{i=(i-1+N)%N;j=(j-1+N)%N;}}for(i=0;i<N;i++){for(j=0;j<N;j++)printf("%5d",a[i][j]);printf("\n");}}123456789(1)由1開始填數(shù)，將1放在第1行中間位置；(2)從當(dāng)前位置向