第14章C語(yǔ)言程序設(shè)計(jì)實(shí)例實(shí)例一成績(jī)處理程序?qū)嵗娮釉~典程序?qū)嵗叭硕珊映绦虻?4章C語(yǔ)言程序設(shè)計(jì)實(shí)例實(shí)例一成績(jī)處理程序1實(shí)例一成績(jī)處理程序1.問(wèn)題描述進(jìn)行若干個(gè)學(xué)生、若干門(mén)課程的成績(jī)處理，要求計(jì)算：(1)每門(mén)課程的平均分和方差。(2)每個(gè)學(xué)生的總分、平均分及方差。(3)按總分對(duì)學(xué)生由高分到低分排序。實(shí)例一成績(jī)處理程序1.問(wèn)題描述2

2.數(shù)據(jù)說(shuō)明(1)學(xué)生人數(shù)假定不超過(guò)1000人，課程門(mén)數(shù)假定不超過(guò)30門(mén)，分別用符號(hào)常量N、M描述。(2)實(shí)際學(xué)生人數(shù)、實(shí)際課程門(mén)數(shù)分別用整型量n、m描述。(3)M門(mén)課程名稱(chēng)用二維字符數(shù)組sname描述。(4)學(xué)生數(shù)據(jù)考慮學(xué)號(hào)num、姓名name、M門(mén)課程成績(jī)，用結(jié)構(gòu)體stt描述。M門(mén)課程成績(jī)用一維數(shù)組score描述。N個(gè)學(xué)生數(shù)據(jù)用結(jié)構(gòu)體數(shù)組sta描述。2.數(shù)據(jù)說(shuō)明3(5)每門(mén)課程的平均分和方差分別用一維實(shí)型數(shù)組avs1、sus1描述。(6)每個(gè)學(xué)生的總分、平均分及方差分別用一維實(shí)型數(shù)組total、avs2和實(shí)型量sus2描述。(7)排序結(jié)果引入一序號(hào)數(shù)組sort保存。以上變量定義為全局變量，同時(shí)利用這些變量在函數(shù)之間傳遞數(shù)據(jù)。(8)數(shù)據(jù)源文件、處理結(jié)果文件分別用字符指針變量ps、pt與文件指針變量fps、fpt描述。(5)每門(mén)課程的平均分和方差分別用一維實(shí)型4(9)引入中間整型變量i、j、k，i用于循環(huán)中控制學(xué)生，j用于循環(huán)中控制課程，k對(duì)應(yīng)總分最高的學(xué)生序號(hào)。(10)數(shù)據(jù)源文件前面存放學(xué)生實(shí)際學(xué)生人數(shù)、實(shí)際課程門(mén)數(shù)與課程名稱(chēng)；處理結(jié)果文件中學(xué)生數(shù)據(jù)增加總分、平均分及名次，課程的平均分和方差、學(xué)生的平均分和方差存放于文件的最后。(9)引入中間整型變量i、j、k，i用于5

3．算法分析(1)整個(gè)程序由主控模塊main()、輸入模塊input()、每門(mén)課程的平均分和方差計(jì)算模塊asfun()、每個(gè)學(xué)生的平均分及方差計(jì)算模塊tasfun()、排序模塊sortfun()、輸出模塊output()六個(gè)模塊組成。各模塊之間順序執(zhí)行。(2)實(shí)際學(xué)生人數(shù)n、實(shí)際課程門(mén)數(shù)m、原始成績(jī)數(shù)據(jù)由鍵盤(pán)輸入或從磁盤(pán)數(shù)據(jù)文件讀取。3．算法分析6(3)原始成績(jī)數(shù)據(jù)由鍵盤(pán)輸入時(shí)，將送磁盤(pán)文件SCORE.DAT保存。(4)方差計(jì)算公式為數(shù)據(jù)平方和的平均值減去數(shù)據(jù)平均值的平方。方差大，表示數(shù)據(jù)相互之間差別較大；方差小，表示數(shù)據(jù)相互之間差別較小。(5)排序采用選擇排序方法，利用序號(hào)數(shù)組保存學(xué)生名次，無(wú)需交換數(shù)據(jù)。(6)處理結(jié)果與原始成績(jī)數(shù)據(jù)合并后用另一磁盤(pán)文件STUDEN.DAT保存。(3)原始成績(jī)數(shù)據(jù)由鍵盤(pán)輸入時(shí)，將送磁盤(pán)文74.參考程序＃include″stdio.h″＃include″math.h″＃defineN1000＃defineM30voidinput（）；voidasfun（）；voidtasfun（）；voidsortfun（）；voidoutput（）；4.參考程序8intn，m；structstt{intnum；char*name；floatscore［M］；}sta［N］；charsname［M］［16］；floatavs1［M］，svs1［M］；floattotal［N］，avs2［N］，svs2；intsort［N］；intn，m；9main（）/*主控函數(shù)*/{clrscr（）；input（）；asfun（）；tasfun（）；sortfun（）；output（）；}main（）/*主控函數(shù)*/10voidinput()/*獲取數(shù)據(jù)*/{charch；inti，j；char*ps；FILE*fps；printf("請(qǐng)選擇數(shù)據(jù)源(K—鍵盤(pán)輸入F—磁盤(pán)文件讀取)：\n")；ch=getch()；switch(ch){case'K'：/*數(shù)據(jù)從鍵盤(pán)輸入*/case'k'：{printf("請(qǐng)輸入實(shí)際學(xué)生人數(shù)：")；scanf("%d"，&n)；printf("請(qǐng)輸入實(shí)際課程門(mén)數(shù)：")；voidinput()/*獲取數(shù)據(jù)*/11scanf("%d"，&m)；if(n<=0||n>1000||m<=0||m>30){printf("數(shù)據(jù)無(wú)效!")；exit(0)；}printf("請(qǐng)輸入%d門(mén)課程名稱(chēng)："，m)；for(j=0；j<m；j++)scanf("%s"，sname[j])；for(i=0；i<n；i++){printf("請(qǐng)輸入第%d個(gè)學(xué)生學(xué)號(hào)，姓名，%d門(mén)課程成績(jī)："，i+1，m)；scanf("%d%s"，&sta[i].num，sta[i].name)；for(j=0；j<m；j++)scanf("%f"，&sta[i].score[j])；}scanf("%d"，&m)；12ps="SCORE.DAT"；/*送磁盤(pán)文件保存*/if((fps=fopen(ps，"wb"))==NULL){printf("文件建立錯(cuò)誤!")；exit(0)；}fwrite(&n，2，1，fps)；fwrite(&m，2，1，fps)；fwrite(sname，16，m，fps)；fwrite(sta，sizeof(structstt)，n，fps)；fclose(fps)；break；}case'F'：/*數(shù)據(jù)從磁盤(pán)文件讀取*/case'f'：ps="SCORE.DAT"；/*送磁盤(pán)文件保存*/13{printf(“請(qǐng)輸入數(shù)據(jù)文件名：”)；scanf("%s"，ps)；if((fps=fopen(ps，"rb"))==NULL){printf("文件打開(kāi)錯(cuò)誤!")；exit(0)；}fread(&n，2，1，fps)；fread(&m，2，1，fps)；fread(sname，16，m，fps)；fread(sta，sizeof(structstt)，n，fps)；fclose(fps)；break；}{printf(“請(qǐng)輸入數(shù)據(jù)文件名：”)；14defautl： {printf("數(shù)據(jù)源選擇錯(cuò)誤!")； exit(0)；}}}

voidasfun()/*計(jì)算每門(mén)課程的平均分和方差*/{intj；floatt[M]，ts[M]；for(j=0；j<m；j++){t[j]=0；ts[j]=0；for(i=0；i<n；i++)defautl：15{t[j]+=sta[i].score[j]；ts[j]+=sta[i].score[j]*sta[i].score[j]；}avs1[j]=t[j]/n；sus1[j]=ts[j]/n-avs1[j]*avs1[j]；}}

voidtasfun()/*計(jì)算每個(gè)學(xué)生的總分、平均分和方差*/{inti，j；floatta=0，ts=0；for(i=0；i<n；i++){total[i]=0；{t[j]+=sta[i].score[16for(j=0；j<m；j++)total[i]+=sta[i].score[j]；avs2[i]=total[i]/n；ta+=avs2[i]；ts+=avs2[i]*avs2[i]；}sus2=ts/n?(ta/n)*(ta/n)；}

voidsortfun()/*按總分排序*/{inti，j，k；for(i=0；i<n；i++){k=i；for(j=i+1；j<m；j++)if(total[j]>total[k])k=j；sort[i]=k+1；}}for(j=0；j<m；j++)17voidoutput()/*輸出數(shù)據(jù)*/{inti，l，j；intis；char*pt；FILE*fpt；clrscr()；/*輸出數(shù)據(jù)送屏幕*/printf("%d個(gè)學(xué)生%d門(mén)課程成績(jī)數(shù)據(jù)如下：\n")；printf("學(xué)號(hào)姓名")；for(j=0；j<m；j++)printf("%16s"，sname[j])；printf("|總分平均分名次\n")；for(i=0；i<n；i++){for(l=0；l<n；l++)voidoutput()/*輸出數(shù)據(jù)*/18if(sort[l]==i+1)is=l；printf("%8d%12s"，sta[is].num，sta[is].name)；for(j=0；j<m；j++)printf("%16.2f"，sta[is].score[j])；printf("|%8.2f%8.2f%6d\n"，total[is]，avs2[is]，sort[is])；}printf("課程平均分")；for(j=0；j<m；j++)printf("%16.2f"，avs1[j])；printf("\n")；printf("方差")；for(j=0；j<m；j++)printf("%16.2f"，sus1[j])；if(sort[l]==i+1)19printf("%16.2\n"，sus2)；pt="STUDENT.DAT"；/*輸出數(shù)據(jù)送磁盤(pán)*/if((fpt=fopen(pt，"wb"))==NULL){printf("文件建立錯(cuò)誤!")；exit(0)；}fwrite(&n，2，1，fpt)；fwrite(&m，2，1，fpt)；fwrite(sname，16，m，fpt)；for(i=0；i<n；i++){fwrite(&sta[i]，sizeof(structstt)，1，fpt)；fwrite(&total[i]，4，1，fpt)；fwrite(&avs2[i]，4，1，fpt)；printf("%16.2\n"，sus2)；20 fwrite(&sort[i]，2，1，fpt)；}fwrite(avs1，4，m，fpt)；fwrite(&sus2，4，1，fpt)；fclose(fpt)；} fwrite(&sort[i]，2，1，fpt)；215.幾點(diǎn)說(shuō)明(1)數(shù)據(jù)源文件可用字處理軟件直接建立。(2)程序的實(shí)現(xiàn)可以不用數(shù)組，而用鏈表。(3)函數(shù)之間數(shù)據(jù)可改用參數(shù)傳遞。(4)處理結(jié)果還可考慮打印輸出。(5)流程圖請(qǐng)讀者畫(huà)出。(6)所做的數(shù)據(jù)與算法分析可轉(zhuǎn)化成本程序的簡(jiǎn)單技術(shù)文檔。5.幾點(diǎn)說(shuō)明22實(shí)例二電子詞典程序

1.問(wèn)題描述在計(jì)算機(jī)中建立有限規(guī)模的電子英漢詞典（文件），利用程序?qū)崿F(xiàn)電子英漢詞典的查找與增、刪、改等維護(hù)。實(shí)例二電子詞典程序1.問(wèn)題描述232.數(shù)據(jù)說(shuō)明(1)對(duì)單詞和釋義字符串長(zhǎng)度的限定分別為不超過(guò)20個(gè)與40個(gè)字符，詞條數(shù)限定為不超過(guò)1000條。(2)單詞數(shù)組words，字符串?dāng)?shù)組。釋義數(shù)組expls，字符串?dāng)?shù)組。詞典中詞條總數(shù)len，整型變量。(3)標(biāo)志變量flag，在主函數(shù)中為0則執(zhí)行菜單，為1則退出程序；在進(jìn)入詞典操作命令后，為1則繼續(xù)執(zhí)行同一命令，為0則退回到菜單。以上變量定義為全局變量。2.數(shù)據(jù)說(shuō)明24(4)命令序號(hào)num，整型。在main（）函數(shù)中用于散轉(zhuǎn)執(zhí)行對(duì)應(yīng)操作。(5)一維字符數(shù)組（字符串）word在lookup（）函數(shù)中為待查單詞，在insert（）函數(shù)中為r待插入單詞，在delete（）函數(shù)中為待刪除單詞，在modify（）函數(shù)中為待修改單詞，在display（）函數(shù)中為待顯示單詞。(6)一維字符數(shù)組（字符串）expl為待插入釋義或待改成的釋義。(7)在search1（）和search2（）中，正整數(shù)l，查找下限，形參；正整數(shù)r，查找上限，形參；正整數(shù)m，中點(diǎn)位置，計(jì)算得到。(4)命令序號(hào)num，整型。在main（253.算法分析(1)執(zhí)行該程序要求在磁盤(pán)上有一個(gè)詞典文件，可使用任何中文編輯軟件生成。其內(nèi)容是每行對(duì)應(yīng)一個(gè)詞條，每詞條包括用若干空格符分開(kāi)兩個(gè)字符串，前一個(gè)是單詞字符串（英文），后一個(gè)是釋義字符串（中文），使用分號(hào)作為多個(gè)釋義的分隔符（無(wú)空格）。事實(shí)上，即使該文件內(nèi)無(wú)一詞條，也可用本程序在線生成所需詞典，但必須有一個(gè)已存在的合乎上述格式的，哪怕是空白的文件。3.算法分析(1)執(zhí)行該程序要求在磁盤(pán)上26(2)采用菜單工作方式。在一個(gè)操作命令執(zhí)行之后，程序詢(xún)問(wèn)是否繼續(xù)執(zhí)行該命令。如輸入y或Y，則重復(fù)同一操作，不退回到菜單；如輸入其它信息，則回到菜單等待另一次選擇。僅當(dāng)選擇退出操作時(shí)，程序會(huì)詢(xún)問(wèn)是否將修改后的詞典存盤(pán)，并根據(jù)用戶(hù)的選擇存盤(pán)或不存盤(pán)退出。(2)采用菜單工作方式。在一個(gè)操作命令執(zhí)行之27(3)除主函數(shù)之外，程序包含其它11個(gè)函數(shù)：

input（file）：從文件file中讀入詞典各詞條的單詞和釋義分別到字串?dāng)?shù)組words和expls中。對(duì)每個(gè)字符串長(zhǎng)度進(jìn)行檢查，發(fā)現(xiàn)非法長(zhǎng)度后會(huì)顯示出錯(cuò)信息并退出程序。menu（）：顯示控制菜單。lookup（）：查詢(xún)一個(gè)單詞的釋義。insert（）：在詞典中適當(dāng)位置插入一個(gè)給定詞條的單詞和釋義。delete（）：從詞典中刪去一個(gè)詞條的單詞和釋義。modify（）：修改詞典中給定單詞的釋義。display（）：顯示詞典中在給定單詞前后的部分詞條的單詞和釋義。(3)除主函數(shù)之外，程序包含其它11個(gè)函28quit（）：在詢(xún)問(wèn)是否要存盤(pán)之后退出程序。search1（l，r，word）:在單詞數(shù)組words的1~r位置中查找給定單詞word的位置。查到，返回該位置；查不到返回-1。分別由lookup（）、delete（）、modify（）和display（）調(diào)用。search2（1，r，word）:在單詞數(shù)組words的1~r位置中查找給定單詞word的插入位置。查到，返回該位置；查不到，不必插入，返回-1。分別由insert（）和display（）調(diào)用。continue（）:詢(xún)問(wèn)用戶(hù)是否繼續(xù)執(zhí)行詞典的操作。除了退出，查詢(xún)、插入、刪除、修改、顯示均調(diào)用該函數(shù)。quit（）：在詢(xún)問(wèn)是否要存盤(pán)之后退出程序294.參考程序＃include″stdio.h″＃include″string.h″＃defineMAXLEN1000＃defineSTRLEN120＃defineSTRLEN240voidmenu（）；voidinput（）；voidlookup（）；voidinsert（）；voiddelete（）；voidmodify（）；voiddisplay（）；voidquit（）；4.參考程序＃include″stdio.h″30intsearch1（）；intsearch2（）；voidcontinue（）；char*words［MAXLEN］，*expls［MAXLEN］；intlen，flag=0；main（）/*主控函數(shù)*/{char*file；intnum；printf（″請(qǐng)輸入詞典文件名：\n″）；scanf（″%s″，file）；input（file）；while（！flag）{menu（）；intsearch1（）；31scanf（″%d″，&num）；switch（num）{case1：lookup（）；break；case2：insert（）；break；case3：delete（）；break；case4：modify（）；break；case5：display（）；break；case6：qiut（file）；break；default：printf（″選擇錯(cuò)，按任一鍵返回菜單！″）；getch（）；}}}scanf（″%d″，&num）；32voidinput（file）/*讀取詞典*/charfile［］；{inti；FILLE*fp；charstr［STRLEN1］；if（（fp=fopen（file，″r″））==NULL）{printf（″不能打開(kāi)文件%s！″，file）；exit（0）；}i=0；fscanf（fp，″%s″，str）；while（！feof（fp））voidinput（file）/*讀取詞典*/33{strcpy（words［i］，str）；fscanf（fp，″%s″，expls［i++］）；fscanf（fp，″%s″，str）；}len=i；fclose（fp）；}voidmenu（）/*菜單*/{clrscr（）；printf（″電子詞典程序\n″）；printf（″\n\n1-單詞查詢(xún)\n″）；printf（″2-增加詞條\n″）；{strcpy（words［i］，str）；34printf（″3-刪除詞條\n″）；printf（″4-修改詞條\n″）；printf（″5-顯示詞條\n″）；printf（″6-退出\n\n\n″）；printf（″\n\n請(qǐng)選擇（1~6）\n″）；}voidlookup（）/*查找單詞釋義*/{charword［STRLEN1］；inti；flag=1；while（flag）{printf（″請(qǐng)輸入查詢(xún)單詞：″）；scanf（″%s″，word）；i=search1（0，len-1，word）；printf（″3-刪除詞條\n″）；35if（i==-1）printf（″無(wú)此單詞！\n″）；elseprintf（″%s\n″，expls［i］）；continue（）；}}voidinsert（）/*插入*/{charword［STRLEN1］，expl［STRLEN2］；inti，j；flag=1；while（flag）{printf（″請(qǐng)輸入待插入的單詞和釋義：″）；scanf（″%s%s″，word，expl）；if（i==-1）36i=search2（0，len，word）；if（i==-1）printf（″已有此單詞！\n″）；else{for（j=len；j>i；j--）{strcpy（words［j］，words［j-1］）；strcpy（expls［j］，expls［j-1］）；}strcpy（words［i］，word）；strcpy（expls［i］，expls）；len++；}i=search2（0，len，word）；37continue（）；}}voiddelete（）/*刪除*/{charword［STRLEN1］；inti，j；flag=1；while（flag）{printf（″請(qǐng)輸入待刪除的單詞：″）；continue（）；38scanf（″%s″，word）；i=search1（0，len-1，word）；if（i==-1）printf（″無(wú)此單詞！\n″）；else{for（j=i；j<len-1；j++）{strcpy（words［j］，words［j+1］）；strcpy（expls［j］，expls［j+1］）；}len--；}continue（）；}}scanf（″%s″，word）；39voidmodify（）/*修改*/{charword［STRLEN1］，expl［STRLEN2］；inti；flag=1；while（flag）{printf（″請(qǐng)輸入待修改的單詞：″）；scanf（″%s″，word）；i=search1（0，len-1，word）；if（i==-1）printf（″無(wú)此單詞！\n″）；else{printf（″輸入新釋義：″）；scanf（″%s″，expl）；voidmodify（）/*修改*/40strcpy（expls［i］，expl）；}continue（）；}}voidquit（file）/*退出*/charfile［］；{inti；FILE*fp；charch；printf（″是否存入詞典（Y/N）？″）；strcpy（expls［i］，expl）；41ch=getch（）；if（ch==′Y′‖ch==′y′）{if（（fp=fopen（file，″w″））==NULL）{printf（″不能打開(kāi)文件%s！\n″，file）；exit（0）；}for（i=0；i<len；i++）fprintf（fp，″%-20s%-40s\n″，words［i］，expls［i］）；fclose（fp）；}ch=getch（）；42flag=1；}voiddisplay（）/*顯示*/{inti，i1，i2；charword［STRLEN1］；flag=1；while（flag）{printf（″請(qǐng)輸入待顯示的單詞：″）；scanf（″%s″，word）；i=search1（0，len-1，word）；flag=1；43if（i==-1）i=search2（0，len，word）；i1=i>=8？i-8：0；i2=i<=len-8？i+8：len-1；for（i=i1；i<=i2；i++）printf（″%-20s%-40s\n″，words［i］，expls［i］）；continue（）；}}intsearch1（1，r，word）/*查找單詞位置*/intl，r；charword［］；{intm；if（i==-1）44while（l<=r）{m=（l+r）/2；if（strcmp（word，words［m］）==0）returnm；elseif（strcmp（word，words［m］）>0）l=m+1；elser=m-1；}return（-1）；}intsearch2（l，r，word）/*查找插入位置*/intl，r；charword[]；while（l<=r）45{intm；while（l<r）{m=（l+r）/2；if（strcmp（word，words［m］）==0）return（-1）；elseif（strcmp（word，words［m］）>0）l=m+1；elser=m；}return（l）；}{intm；46voidcontinue（）/*重復(fù)執(zhí)行操作*/{charch；printf（″繼續(xù)執(zhí)行嗎（Y/N）？″）；ch=getch（）；if（ch==′Y′‖ch=′y′）flag=1；elseflag=0；}voidcontinue（）/*重復(fù)執(zhí)行操作*/47

5.說(shuō)明(1)如果需增加單詞及釋義字串長(zhǎng)度，應(yīng)修改源程序中有關(guān)參數(shù)。(2)對(duì)單詞除了釋義外，還可增加發(fā)音、同義詞、反義詞等考慮。(3)流程圖、簡(jiǎn)單技術(shù)文檔亦請(qǐng)讀者給出。(4)延伸考慮電子新華字典程序。5.說(shuō)明48實(shí)例三野人渡河程序1．問(wèn)題描述3個(gè)野人和3個(gè)傳教士來(lái)到河邊，打算乘一只船從右岸到左岸去。該船的負(fù)載能力為兩人。在任何時(shí)候，如果野人人數(shù)超過(guò)傳教士人數(shù)，野人就會(huì)把傳教士吃掉。他們?cè)鯓硬拍苡眠@條船安全地把所有人都渡過(guò)河去呢？本問(wèn)題是一個(gè)簡(jiǎn)單的人工智能問(wèn)題，是個(gè)典型的狀態(tài)圖搜索問(wèn)題。這個(gè)問(wèn)題還可以拓展為m個(gè)野人和n個(gè)傳教士，而船一次可以裝下r個(gè)人的情況。實(shí)例三野人渡河程序1．問(wèn)題描述492．參考程序#include<stdio.h>#include<stdlib.h>#definemaxloop100 //最大層數(shù)#definepristnum3 //傳教士默認(rèn)值#defineslavenum3 //野人默認(rèn)值structSPQ{intsr,pr; //船運(yùn)行一個(gè)來(lái)回后河右岸的野人、傳教士的人數(shù)intsl,pl; //船運(yùn)行一個(gè)來(lái)回后河左岸的野人、傳教士的人數(shù)intssr,spr; //回來(lái)(由左向右時(shí))船上的人數(shù)intsst,spt; //去時(shí)(由右向左時(shí))船上的人數(shù)intloop;//本結(jié)點(diǎn)所在的層數(shù)2．參考程序50structSPQ*upnode,*nextnode;//本結(jié)點(diǎn)的父結(jié)點(diǎn)和同層的下一個(gè)結(jié)點(diǎn)的地址}spq;intloopnum;//記錄總的擴(kuò)展次數(shù)intopenednum;//記錄已擴(kuò)展節(jié)點(diǎn)個(gè)數(shù)intunopenednum;//記錄待擴(kuò)展節(jié)點(diǎn)個(gè)數(shù)intresultnum;structSPQ*opened;structSPQ*oend;structSPQ*unopened;structSPQ*uend;structSPQ*result;voidinitiate();voidreleasemem();structSPQ*upnode,*nextn51voidshowresult();voidaddtoopened(structSPQ*ntx);intsearch();voidgoon();intstretch(structSPQ*ntx);voidrecorder();

voidmain(){intflag;//標(biāo)記擴(kuò)展是否成功 for(;;){initiate();flag=search();if(flag==1)voidshowresult();52{recorder();releasemem();showresult();goon();}else{printf("無(wú)法找到符合條件的解");releasemem();goon();}}}voidinitiate(){intx;charchoice;{recorder();53uend=unopened=(structSPQ*)malloc(sizeof(spq));if(uend==NULL){printf("\n內(nèi)存不夠!\n");exit(0);}unopenednum=1;openednum=0;unopened->upnode=unopened;//保存父結(jié)點(diǎn)的地址以成鏈表unopened->nextnode=unopened;unopened->sr=slavenum;unopened->pr=pristnum;unopened->sl=0;unopened->pl=0;uend=unopened=(structSPQ*54unopened->sst=0;unopened->spt=0;unopened->ssr=0;unopened->spr=0;unopened->loop=0;printf("題目：設(shè)有n個(gè)傳教士和m個(gè)野人來(lái)到河邊，打算乘一只船從右岸到左岸去。\n");printf("該船的負(fù)載能力為兩人。在任何時(shí)候，如果野人人數(shù)超過(guò)傳教士人數(shù)，野人\n");printf("就會(huì)把傳教士吃掉。他們?cè)鯓硬拍苡眠@條船安全地把所有人都渡過(guò)河去呢?\n");printf("\n默認(rèn)的n、m值皆為3\n");for(;;)unopened->sst=0;55 {printf("\n是否修改？(Y/N)："); scanf("%s",&choice); choice=toupper(choice); if(choice=='Y') {printf("\n請(qǐng)輸入傳教士人數(shù)："); for(;;) {scanf("%d",&x); if(x>0) {unopened?>pr=x; break; } elseprintf("\n輸入值應(yīng)大于0！\n請(qǐng)重新輸入"); } {printf("\n是否修56 printf("請(qǐng)輸入野人人數(shù)："); for(;;) {scanf("%d",&x); if(x>0) {unopened?>sr=x; break; } elseprintf("\n輸入值應(yīng)大于0！\n請(qǐng)重新輸入"); } break; } if(choice=='N')break; }} printf("請(qǐng)輸入野人人數(shù)：");57intsearch(){intflag;structSPQ*ntx;//提供將要擴(kuò)展的結(jié)點(diǎn)的指針for(;;){ntx=unopened;//從待擴(kuò)展鏈表中提取最前面的一個(gè)if(ntx->loop==maxloop)return0;addtoopened(ntx);//將ntx加入已擴(kuò)展鏈表，并將這個(gè)節(jié)點(diǎn)從待擴(kuò)展鏈表中去掉flag=stretch(ntx);//對(duì)ntx進(jìn)行擴(kuò)展,返回-1,0,1if(flag==1) return1; }}intsearch()58intstretch(structSPQ*ntx){intfsr,fpr;//在右岸上的人數(shù)intfsl,fpl;//在左岸上的人數(shù)intsst,spt;//出發(fā)時(shí)在船上的人數(shù)intssr,spr;//返回時(shí)船上的人數(shù)structSPQ*newnode;for(sst=0;sst<=2;sst++)//討論不同的可能性并判斷是否符合條件{fsr=ntx->sr;fpr=ntx->pr;fsl=ntx->sl;fpl=ntx->pl;if((sst<=fsr)&&((2-sst)<=fpr))//滿(mǎn)足人數(shù)限制{spt=2-sst;fsr=fsr-sst;intstretch(structSPQ*ntx)59 fpr=fpr-spt; if((fpr==0)&&(fsr==0))//搜索成功 {newnode=(structSPQ*)malloc(sizeof(spq)); if(newnode==NULL) {printf("\n內(nèi)存不夠！\n"); exit(0); } newnode->upnode=ntx;//保存父結(jié)點(diǎn)的地址以成鏈表 newnode->nextnode=NULL; newnode->sr=0; newnode->pr=0; newnode->sl=opened?>sr; newnode->pl=opened?>pr; fpr=fpr-spt;60 newnode->sst=sst; newnode->spt=spt; newnode->ssr=0; newnode->spr=0; newnode->loop=ntx?>loop+1; oend->nextnode=newnode; oend=newnode; openednum++; return1; }elseif((fpr-fsr)*fpr>=0)//判斷是否滿(mǎn)足傳教士人數(shù)大于或等于野人人數(shù) {fsl=fsl+sst; newnode->sst=sst;61 fpl=fpl+spt; for(ssr=0;ssr<=1;ssr++)//返回 {intffsl,ffpl; if((ssr<=fsl)&&((1-ssr)<=fpl)) {spr=1-ssr; ffsl=fsl-ssr; ffpl=fpl-spr; if((ffpl-ffsl)*ffpl>=0)//若符合條件則分配內(nèi)存并賦值 {intffsr,ffpr; ffsr=fsr+ssr; ffpr=fpr+spr; newnode=(structSPQ*)malloc(sizeof(spq)); if(newnode==NULL) {printf("\n內(nèi)存不夠！\n"); exit(0); } fpl=fpl+spt;62 newnode->upnode=ntx;//保存父結(jié)點(diǎn)的地址 newnode->sr=ffsr; newnode->pr=ffpr; newnode->sl=ffsl; newnode->pl=ffpl; newnode->sst=sst; newnode->spt=spt; newnode->ssr=ssr; newnode->spr=spr; newnode->loop=ntx?>loop+1; uend->nextnode=newnode; uend=newnode; unopenednum++; } } }}}} return0;} newnode->upnode=ntx;/63voidaddtoopened(structSPQ*ntx){unopened=unopened?>nextnode;unopenednum??;if(openednum==0)oend=opened=ntx;oend?>nextnode=ntx;oend=ntx;openednum++;}voidaddtoopened(structSPQ*n64voidrecorder(){inti,loop;structSPQ*newnode;structSPQ*ntx;loop=oend?>loop;ntx=oend;resultnum=0;for(i=0;i<=loop;i++) {newnode=(structSPQ*)malloc(sizeof(spq)); if(newnode==NULL) {printf("\n內(nèi)存不夠！\n"); exit(0); }voidrecorder()65 newnode->sr=ntx->sr; ewnode->pr=ntx->pr; ewnode->sl=ntx->sl; ewnode->pl=ntx->pl; ewnode->sst=ntx->sst; ewnode->spt=ntx->spt; ewnode->ssr=ntx->ssr; ewnode->spr=ntx->spr; ewnode->nextnode=NULL; tx=ntx->upnode; f(i==0) result=newnode; ewnode->nextnode=result; esult=newnode; esultnum++; }} newnode->sr=ntx->s66voidreleasemem(){inti;structSPQ*nodefree;for(i=1;i<openednum;i++){nodefree=opened; opened=opened?>nextnode; free(nodefree);}for(i=0;i<unopenednum;i++){nodefree=unopened;unopened=unopened?>nextnode;free(nodefree);}}voidreleasemem()67voidshowresult(){inti;intfsr,fpr;//在右岸上的人數(shù)intfsl,fpl;//在左岸上的人數(shù)structSPQ*nodefree;printf("\n");printf("%d個(gè)傳教士和%d個(gè)野人渡河:",result?>pr,result?>sr);for(i=1;i<resultnum;i++){nodefree=result; result=result?>nextnode; free(nodefree); printf("\n\n\t左岸人數(shù)船上人數(shù)及方向右岸人數(shù)\n");voidshowresult()68 printf("第%d輪\n",i); fpl=result->pl-result->spt+result->spr; fpr=result->pr-result->spr; fsl=result->sl-result->sst+result->ssr; fsr=result->sr-result->ssr; printf("傳教士%8d%8d\t<-\t%8d\n",fpl,result->spt,fpr); printf("野人%8d%8d\t<-\t%8d\n",fsl,result->sst,fsr); printf("傳教士%8d%8d\t->\t%8d\n",result->pl,result->spr,result->pr-result->spr); printf("野人%8d%8d\t->\t%8d\n",result->sl,result->ssr,result->sr-result->ssr); }printf("\n全體傳教士和野人全部到達(dá)對(duì)岸！");free(result);} printf("第%d輪\n",i);69voidgoon(){charchoice; for(;;){printf("\n是否繼續(xù)？(Y/N)：");scanf("%s",&choice);choice=toupper(choice);if(choice=='Y')break;if(choice=='N')exit(0);}}voidgoon()703．運(yùn)行結(jié)果圖14-1野人渡河問(wèn)題的解答3．運(yùn)行結(jié)果圖14-1野人渡河問(wèn)題的解答71

4．?dāng)?shù)據(jù)與算法分析本題的數(shù)據(jù)與算法分析以及問(wèn)題拓展后的情況，請(qǐng)讀者基于上面的程序，作為本章的練習(xí)去完成。4．?dāng)?shù)據(jù)與算法分析72第14章C語(yǔ)言程序設(shè)計(jì)實(shí)例實(shí)例一成績(jī)處理程序?qū)嵗娮釉~典程序?qū)嵗叭硕珊映绦虻?4章C語(yǔ)言程序設(shè)計(jì)實(shí)例實(shí)例一成績(jī)處理程序73實(shí)例一成績(jī)處理程序1.問(wèn)題描述進(jìn)行若干個(gè)學(xué)生、若干門(mén)課程的成績(jī)處理，要求計(jì)算：(1)每門(mén)課程的平均分和方差。(2)每個(gè)學(xué)生的總分、平均分及方差。(3)按總分對(duì)學(xué)生由高分到低分排序。實(shí)例一成績(jī)處理程序1.問(wèn)題描述74

2.數(shù)據(jù)說(shuō)明(1)學(xué)生人數(shù)假定不超過(guò)1000人，課程門(mén)數(shù)假定不超過(guò)30門(mén)，分別用符號(hào)常量N、M描述。(2)實(shí)際學(xué)生人數(shù)、實(shí)際課程門(mén)數(shù)分別用整型量n、m描述。(3)M門(mén)課程名稱(chēng)用二維字符數(shù)組sname描述。(4)學(xué)生數(shù)據(jù)考慮學(xué)號(hào)num、姓名name、M門(mén)課程成績(jī)，用結(jié)構(gòu)體stt描述。M門(mén)課程成績(jī)用一維數(shù)組score描述。N個(gè)學(xué)生數(shù)據(jù)用結(jié)構(gòu)體數(shù)組sta描述。2.數(shù)據(jù)說(shuō)明75(5)每門(mén)課程的平均分和方差分別用一維實(shí)型數(shù)組avs1、sus1描述。(6)每個(gè)學(xué)生的總分、平均分及方差分別用一維實(shí)型數(shù)組total、avs2和實(shí)型量sus2描述。(7)排序結(jié)果引入一序號(hào)數(shù)組sort保存。以上變量定義為全局變量，同時(shí)利用這些變量在函數(shù)之間傳遞數(shù)據(jù)。(8)數(shù)據(jù)源文件、處理結(jié)果文件分別用字符指針變量ps、pt與文件指針變量fps、fpt描述。(5)每門(mén)課程的平均分和方差分別用一維實(shí)型76(9)引入中間整型變量i、j、k，i用于循環(huán)中控制學(xué)生，j用于循環(huán)中控制課程，k對(duì)應(yīng)總分最高的學(xué)生序號(hào)。(10)數(shù)據(jù)源文件前面存放學(xué)生實(shí)際學(xué)生人數(shù)、實(shí)際課程門(mén)數(shù)與課程名稱(chēng)；處理結(jié)果文件中學(xué)生數(shù)據(jù)增加總分、平均分及名次，課程的平均分和方差、學(xué)生的平均分和方差存放于文件的最后。(9)引入中間整型變量i、j、k，i用于77

3．算法分析(1)整個(gè)程序由主控模塊main()、輸入模塊input()、每門(mén)課程的平均分和方差計(jì)算模塊asfun()、每個(gè)學(xué)生的平均分及方差計(jì)算模塊tasfun()、排序模塊sortfun()、輸出模塊output()六個(gè)模塊組成。各模塊之間順序執(zhí)行。(2)實(shí)際學(xué)生人數(shù)n、實(shí)際課程門(mén)數(shù)m、原始成績(jī)數(shù)據(jù)由鍵盤(pán)輸入或從磁盤(pán)數(shù)據(jù)文件讀取。3．算法分析78(3)原始成績(jī)數(shù)據(jù)由鍵盤(pán)輸入時(shí)，將送磁盤(pán)文件SCORE.DAT保存。(4)方差計(jì)算公式為數(shù)據(jù)平方和的平均值減去數(shù)據(jù)平均值的平方。方差大，表示數(shù)據(jù)相互之間差別較大；方差小，表示數(shù)據(jù)相互之間差別較小。(5)排序采用選擇排序方法，利用序號(hào)數(shù)組保存學(xué)生名次，無(wú)需交換數(shù)據(jù)。(6)處理結(jié)果與原始成績(jī)數(shù)據(jù)合并后用另一磁盤(pán)文件STUDEN.DAT保存。(3)原始成績(jī)數(shù)據(jù)由鍵盤(pán)輸入時(shí)，將送磁盤(pán)文794.參考程序＃include″stdio.h″＃include″math.h″＃defineN1000＃defineM30voidinput（）；voidasfun（）；voidtasfun（）；voidsortfun（）；voidoutput（）；4.參考程序80intn，m；structstt{intnum；char*name；floatscore［M］；}sta［N］；charsname［M］［16］；floatavs1［M］，svs1［M］；floattotal［N］，avs2［N］，svs2；intsort［N］；intn，m；81main（）/*主控函數(shù)*/{clrscr（）；input（）；asfun（）；tasfun（）；sortfun（）；output（）；}main（）/*主控函數(shù)*/82voidinput()/*獲取數(shù)據(jù)*/{charch；inti，j；char*ps；FILE*fps；printf("請(qǐng)選擇數(shù)據(jù)源(K—鍵盤(pán)輸入F—磁盤(pán)文件讀取)：\n")；ch=getch()；switch(ch){case'K'：/*數(shù)據(jù)從鍵盤(pán)輸入*/case'k'：{printf("請(qǐng)輸入實(shí)際學(xué)生人數(shù)：")；scanf("%d"，&n)；printf("請(qǐng)輸入實(shí)際課程門(mén)數(shù)：")；voidinput()/*獲取數(shù)據(jù)*/83scanf("%d"，&m)；if(n<=0||n>1000||m<=0||m>30){printf("數(shù)據(jù)無(wú)效!")；exit(0)；}printf("請(qǐng)輸入%d門(mén)課程名稱(chēng)："，m)；for(j=0；j<m；j++)scanf("%s"，sname[j])；for(i=0；i<n；i++){printf("請(qǐng)輸入第%d個(gè)學(xué)生學(xué)號(hào)，姓名，%d門(mén)課程成績(jī)："，i+1，m)；scanf("%d%s"，&sta[i].num，sta[i].name)；for(j=0；j<m；j++)scanf("%f"，&sta[i].score[j])；}scanf("%d"，&m)；84ps="SCORE.DAT"；/*送磁盤(pán)文件保存*/if((fps=fopen(ps，"wb"))==NULL){printf("文件建立錯(cuò)誤!")；exit(0)；}fwrite(&n，2，1，fps)；fwrite(&m，2，1，fps)；fwrite(sname，16，m，fps)；fwrite(sta，sizeof(structstt)，n，fps)；fclose(fps)；break；}case'F'：/*數(shù)據(jù)從磁盤(pán)文件讀取*/case'f'：ps="SCORE.DAT"；/*送磁盤(pán)文件保存*/85{printf(“請(qǐng)輸入數(shù)據(jù)文件名：”)；scanf("%s"，ps)；if((fps=fopen(ps，"rb"))==NULL){printf("文件打開(kāi)錯(cuò)誤!")；exit(0)；}fread(&n，2，1，fps)；fread(&m，2，1，fps)；fread(sname，16，m，fps)；fread(sta，sizeof(structstt)，n，fps)；fclose(fps)；break；}{printf(“請(qǐng)輸入數(shù)據(jù)文件名：”)；86defautl： {printf("數(shù)據(jù)源選擇錯(cuò)誤!")； exit(0)；}}}

voidasfun()/*計(jì)算每門(mén)課程的平均分和方差*/{intj；floatt[M]，ts[M]；for(j=0；j<m；j++){t[j]=0；ts[j]=0；for(i=0；i<n；i++)defautl：87{t[j]+=sta[i].score[j]；ts[j]+=sta[i].score[j]*sta[i].score[j]；}avs1[j]=t[j]/n；sus1[j]=ts[j]/n-avs1[j]*avs1[j]；}}

voidtasfun()/*計(jì)算每個(gè)學(xué)生的總分、平均分和方差*/{inti，j；floatta=0，ts=0；for(i=0；i<n；i++){total[i]=0；{t[j]+=sta[i].score[88for(j=0；j<m；j++)total[i]+=sta[i].score[j]；avs2[i]=total[i]/n；ta+=avs2[i]；ts+=avs2[i]*avs2[i]；}sus2=ts/n?(ta/n)*(ta/n)；}

voidsortfun()/*按總分排序*/{inti，j，k；for(i=0；i<n；i++){k=i；for(j=i+1；j<m；j++)if(total[j]>total[k])k=j；sort[i]=k+1；}}for(j=0；j<m；j++)89voidoutput()/*輸出數(shù)據(jù)*/{inti，l，j；intis；char*pt；FILE*fpt；clrscr()；/*輸出數(shù)據(jù)送屏幕*/printf("%d個(gè)學(xué)生%d門(mén)課程成績(jī)數(shù)據(jù)如下：\n")；printf("學(xué)號(hào)姓名")；for(j=0；j<m；j++)printf("%16s"，sname[j])；printf("|總分平均分名次\n")；for(i=0；i<n；i++){for(l=0；l<n；l++)voidoutput()/*輸出數(shù)據(jù)*/90if(sort[l]==i+1)is=l；printf("%8d%12s"，sta[is].num，sta[is].name)；for(j=0；j<m；j++)printf("%16.2f"，sta[is].score[j])；printf("|%8.2f%8.2f%6d\n"，total[is]，avs2[is]，sort[is])；}printf("課程平均分")；for(j=0；j<m；j++)printf("%16.2f"，avs1[j])；printf("\n")；printf("方差")；for(j=0；j<m；j++)printf("%16.2f"，sus1[j])；if(sort[l]==i+1)91printf("%16.2\n"，sus2)；pt="STUDENT.DAT"；/*輸出數(shù)據(jù)送磁盤(pán)*/if((fpt=fopen(pt，"wb"))==NULL){printf("文件建立錯(cuò)誤!")；exit(0)；}fwrite(&n，2，1，fpt)；fwrite(&m，2，1，fpt)；fwrite(sname，16，m，fpt)；for(i=0；i<n；i++){fwrite(&sta[i]，sizeof(structstt)，1，fpt)；fwrite(&total[i]，4，1，fpt)；fwrite(&avs2[i]，4，1，fpt)；printf("%16.2\n"，sus2)；92 fwrite(&sort[i]，2，1，fpt)；}fwrite(avs1，4，m，fpt)；fwrite(&sus2，4，1，fpt)；fclose(fpt)；} fwrite(&sort[i]，2，1，fpt)；935.幾點(diǎn)說(shuō)明(1)數(shù)據(jù)源文件可用字處理軟件直接建立。(2)程序的實(shí)現(xiàn)可以不用數(shù)組，而用鏈表。(3)函數(shù)之間數(shù)據(jù)可改用參數(shù)傳遞。(4)處理結(jié)果還可考慮打印輸出。(5)流程圖請(qǐng)讀者畫(huà)出。(6)所做的數(shù)據(jù)與算法分析可轉(zhuǎn)化成本程序的簡(jiǎn)單技術(shù)文檔。5.幾點(diǎn)說(shuō)明94實(shí)例二電子詞典程序

1.問(wèn)題描述在計(jì)算機(jī)中建立有限規(guī)模的電子英漢詞典（文件），利用程序?qū)崿F(xiàn)電子英漢詞典的查找與增、刪、改等維護(hù)。實(shí)例二電子詞典程序1.問(wèn)題描述952.數(shù)據(jù)說(shuō)明(1)對(duì)單詞和釋義字符串長(zhǎng)度的限定分別為不超過(guò)20個(gè)與40個(gè)字符，詞條數(shù)限定為不超過(guò)1000條。(2)單詞數(shù)組words，字符串?dāng)?shù)組。釋義數(shù)組expls，字符串?dāng)?shù)組。詞典中詞條總數(shù)len，整型變量。(3)標(biāo)志變量flag，在主函數(shù)中為0則執(zhí)行菜單，為1則退出程序；在進(jìn)入詞典操作命令后，為1則繼續(xù)執(zhí)行同一命令，為0則退回到菜單。以上變量定義為全局變量。2.數(shù)據(jù)說(shuō)明96(4)命令序號(hào)num，整型。在main（）函數(shù)中用于散轉(zhuǎn)執(zhí)行對(duì)應(yīng)操作。(5)一維字符數(shù)組（字符串）word在lookup（）函數(shù)中為待查單詞，在insert（）函數(shù)中為r待插入單詞，在delete（）函數(shù)中為待刪除單詞，在modify（）函數(shù)中為待修改單詞，在display（）函數(shù)中為待顯示單詞。(6)一維字符數(shù)組（字符串）expl為待插入釋義或待改成的釋義。(7)在search1（）和search2（）中，正整數(shù)l，查找下限，形參；正整數(shù)r，查找上限，形參；正整數(shù)m，中點(diǎn)位置，計(jì)算得到。(4)命令序號(hào)num，整型。在main（973.算法分析(1)執(zhí)行該程序要求在磁盤(pán)上有一個(gè)詞典文件，可使用任何中文編輯軟件生成。其內(nèi)容是每行對(duì)應(yīng)一個(gè)詞條，每詞條包括用若干空格符分開(kāi)兩個(gè)字符串，前一個(gè)是單詞字符串（英文），后一個(gè)是釋義字符串（中文），使用分號(hào)作為多個(gè)釋義的分隔符（無(wú)空格）。事實(shí)上，即使該文件內(nèi)無(wú)一詞條，也可用本程序在線生成所需詞典，但必須有一個(gè)已存在的合乎上述格式的，哪怕是空白的文件。3.算法分析(1)執(zhí)行該程序要求在磁盤(pán)上98(2)采用菜單工作方式。在一個(gè)操作命令執(zhí)行之后，程序詢(xún)問(wèn)是否繼續(xù)執(zhí)行該命令。如輸入y或Y，則重復(fù)同一操作，不退回到菜單；如輸入其它信息，則回到菜單等待另一次選擇。僅當(dāng)選擇退出操作時(shí)，程序會(huì)詢(xún)問(wèn)是否將修改后的詞典