數(shù)據(jù)結(jié)構(gòu)(c語言版)第三四章習(xí)題答案-資料下載頁
2025-06-19 23:14本頁面
【正文】 ）（5）寫一個算法統(tǒng)計在輸入字符串中各個不同字符出現(xiàn)的頻度并將結(jié)果存入文件（字符串中的合法字符為AZ這26個字母和09這10個數(shù)字）。void Count（）//統(tǒng)計輸入字符串中數(shù)字字符和字母字符的個數(shù)。｛int i，num[36]；char ch； for（i＝0；i36；i++）num[i]＝０；// 初始化 while（（ch＝getchar（））!=‘’） //‘’表示輸入字符串結(jié)束?！ f（‘0’=ch=‘9’）｛i=ch－48。num[i]++；｝ // 數(shù)字字符 else if（‘A’=ch=‘Z’）｛i=ch65+10。num[i]++；｝// 字母字符 for（i=0；i10；i++） // 輸出數(shù)字字符的個數(shù) printf（“數(shù)字％d的個數(shù)＝％d\n”，i，num[i]）； for（i＝10；i36；i++）// 求出字母字符的個數(shù) printf（“字母字符％c的個數(shù)＝％d\n”，i＋55，num[i]）；｝// 算法結(jié)束。（6）寫一個遞歸算法來實(shí)現(xiàn)字符串逆序存儲，要求不另設(shè)串存儲空間。[題目分析]實(shí)現(xiàn)字符串的逆置并不難，但本題“要求不另設(shè)串存儲空間”來實(shí)現(xiàn)字符串逆序存儲，即第一個輸入的字符最后存儲，最后輸入的字符先存儲，使用遞歸可容易做到。 void InvertStore(char A[])//字符串逆序存儲的遞歸算法。{ char ch。static int i = 0。//需要使用靜態(tài)變量scanf (%c,amp。ch)。if (ch!= 39。.39。) //規(guī)定39。.39。是字符串輸入結(jié)束標(biāo)志 {InvertStore(A)。 A[i++] = ch。//字符串逆序存儲 }A[i] = 39。\039。 //字符串結(jié)尾標(biāo)記}//結(jié)束算法InvertStore。（7）編寫算法，實(shí)現(xiàn)下面函數(shù)的功能。函數(shù)void insert(char*s,char*t,int pos)將字符串t插入到字符串s中，插入位置為pos。假設(shè)分配給字符串s的空間足夠讓字符串t插入。（說明：不得使用任何庫函數(shù)）[題目分析]本題是字符串的插入問題，要求在字符串s的pos位置，插入字符串t。首先應(yīng)查找字符串s的pos位置，將第pos個字符到字符串s尾的子串向后移動字符串t的長度，然后將字符串t復(fù)制到字符串s的第pos位置后。 對插入位置pos要驗(yàn)證其合法性，小于1或大于串s的長度均為非法，因題目假設(shè)給字符串s的空間足夠大，故對插入不必判溢出。void insert(char *s,char *t,int pos)//將字符串t插入字符串s的第pos個位置。{int i=1,x=0。 char *p=s,*q=t。 //p，q分別為字符串s和t的工作指針 if(pos1) {printf(“pos參數(shù)位置非法\n”)。exit(0)。}while(*p!=’\0’amp。amp。ipos) {p++。i++。} //查pos位置 //若pos小于串s長度，則查到pos位置時，i=pos。 if(*p == 39。/039。) {printf(%d位置大于字符串s的長度,pos)。exit(0)。} else //查找字符串的尾 while(*p!= 39。/039。) {p++。 i++。} //查到尾時，i為字符‘\0’的下標(biāo)，p也指向‘\0’。 while(*q!= 39。\039。) {q++。 x++。 } //查找字符串t的長度x，循環(huán)結(jié)束時q指向39。\039。 for(j=i。j=pos 。j){*(p+x)=*p。 p。}//串s的pos后的子串右移，空出串t的位置。 q。 //指針q回退到串t的最后一個字符 for(j=1。j=x。j++) *p=*q。 //將t串插入到s的pos位置上 [算法討論] 串s的結(jié)束標(biāo)記(39。\039。)也后移了，而串t的結(jié)尾標(biāo)記不應(yīng)插入到s中。（8）已知字符串S1中存放一段英文，寫出算法format(s1,s2,s3,n),將其按給定的長度n格式化成兩端對齊的字符串S2, 其多余的字符送S3。[題目分析]本題要求字符串s1拆分成字符串s2和字符串s3，要求字符串s2“按給定長度n格式化成兩端對齊的字符串”，即長度為n且首尾字符不得為空格字符。算法從左到右掃描字符串s1，找到第一個非空格字符，計數(shù)到n，第n個拷入字符串s2的字符不得為空格，然后將余下字符復(fù)制到字符串s3中。void format (char *s1,*s2,*s3)//將字符串s1拆分成字符串s2和字符串s3，要求字符串s2是長n且兩端對齊{char *p=s1, *q=s2。 int i=0。 while(*p!= 39。\039。 amp。amp。 *p== 39。 39。) p++。//濾掉s1左端空格 if(*p== 39。\039。) {printf(字符串s1為空串或空格串\n)。exit(0)。 } while( *p!=39。\039。 amp。amp。 in){*q=*p。 q++。 p++。 i++。}//字符串s1向字符串s2中復(fù)制 if(*p ==39。\039。){ printf(字符串s1沒有%d個有效字符\n,n)。 exit(0)。} if(*(q)==39。 39。 ) //若最后一個字符為空格，則需向后找到第一個非空格字符 {p 。 //p指針也后退 while(*p==39。 39。amp。amp。*p!=39。\039。) p++。//往后查找一個非空格字符作串s2的尾字符 if(*p==39。\039。) {printf(s1串沒有%d個兩端對齊的字符串\n,n)。 exit(0)。 } *q=*p。 //字符串s2最后一個非空字符 *(++q)=39。\039。 //置s2字符串結(jié)束標(biāo)記 } *q=s3。p++。 //將s1串其余部分送字符串s3。 while (*p!= 39。\039。) {*q=*p。 q++。 p++。} *q=39。\039。 //置串s3結(jié)束標(biāo)記}(9)設(shè)二維數(shù)組a[1..m, 1..n] 含有m*n 個整數(shù)。① 寫一個算法判斷a中所有元素是否互不相同?輸出相關(guān)信息(yes/no)；② 試分析算法的時間復(fù)雜度。[題目分析]判斷二維數(shù)組中元素是否互不相同，只有逐個比較,找到一對相等的元素，就可結(jié)論為不是互不相同。如何達(dá)到每個元素同其它元素比較一次且只一次？在當(dāng)前行，每個元素要同本行后面的元素比較一次（下面第一個循環(huán)控制變量p的for循環(huán)），然后同第i+1行及以后各行元素比較一次，這就是循環(huán)控制變量k和p的二層for循環(huán)。int JudgEqual(ing a[m][n],int m,n) //判斷二維數(shù)組中所有元素是否互不相同，如是，返回1；否則，返回0。{for(i=0。im。i++) for(j=0。jn1。j++) { for(p=j+1。pn。p++) //和同行其它元素比較 if(a[i][j]==a[i][p]) {printf(“no”)。 return(0)。 } //只要有一個相同的，就結(jié)論不是互不相同 for(k=i+1。km。k++) //和第i+1行及以后元素比較 for(p=0。pn。p++) if(a[i][j]==a[k][p]) {printf(“no”)。 return(0)。 } }// for(j=0。jn1。j++)printf(yes”)。 return(1)。 //元素互不相同}//算法JudgEqual結(jié)束（2）二維數(shù)組中的每一個元素同其它元素都比較一次，數(shù)組中共m*n個元素，第1個元素同其它m*n1個元素比較，第2個元素同其它m*n2 個元素比較，……，第m*n1個元素同最后一個元素(m*n)比較一次,所以在元素互不相等時總的比較次數(shù)為 (m*n1)+(m*n2)+…+2+1=（m*n）(m*n1)/2。在有相同元素時,可能第一次比較就相同,也可能最后一次比較時相同,設(shè)在(m*n1)個位置上均可能相同,這時的平均比較次數(shù)約為（m*n）(m*n1)/4，總的時間復(fù)雜度是O(n4)。(10)設(shè)任意n個整數(shù)存放于數(shù)組A(1:n)中，試編寫算法，將所有正數(shù)排在所有負(fù)數(shù)前面（要求算法復(fù)雜性為0(n)）。 [題目分析]本題屬于排序問題，只是排出正負(fù)，不排出大小。可在數(shù)組首尾設(shè)兩個指針i和j，i自小至大搜索到負(fù)數(shù)停止，j自大至小搜索到正數(shù)停止。然后i和j所指數(shù)據(jù)交換，繼續(xù)以上過程，直到 i=j為止。void Arrange(int A[],int n) //n個整數(shù)存于數(shù)組A中，本算法將數(shù)組中所有正數(shù)排在所有負(fù)數(shù)的前面 {int i=0,j=n1,x。 //用類C編寫，數(shù)組下標(biāo)從0開始 while(ij){while(ij amp。amp。 A[i]0) i++。while(ij amp。amp。 A[j]0) j。 if(ij) {x=A[i]。 A[i++]=A[j]。 A[j]=x。 }//交換A[i] 與A[j]} }//算法Arrange結(jié)束.[算法討論]對數(shù)組中元素各比較一次，比較次數(shù)為n。最佳情況(已排好,正數(shù)在前,負(fù)數(shù)在后)不發(fā)生交換，最差情況(負(fù)數(shù)均在正數(shù)前面)發(fā)生n/2次交換。用類c編寫，數(shù)組界偶是0..n1?？臻g復(fù)雜度為O(1
研究報告相關(guān)推薦
鄂ICP備17016276號-1