《C語言（第三版）》 課件 項(xiàng)目四 應(yīng)用 C 語言

04應(yīng)用C語言302任務(wù)1判定獎(jiǎng)學(xué)金等級——文件的操作任務(wù)2求水仙花數(shù)——實(shí)際問題的算法設(shè)計(jì)任務(wù)3安排運(yùn)動(dòng)員出場順序——排序算法的應(yīng)用

任務(wù)4解決猴子吃桃問題——遞歸算法的應(yīng)用303

判定獎(jiǎng)學(xué)金等級——文件的操作任務(wù)1304學(xué)習(xí)目標(biāo)1.能使用C語言標(biāo)準(zhǔn)函數(shù)庫編寫程序。2.理解流的概念。3.能熟練進(jìn)行文件的打開和關(guān)閉操作，完成讀文件、寫文件、定位文件等操作。305任務(wù)描述期末考試以后，學(xué)校要根據(jù)學(xué)生的考試成績進(jìn)行獎(jiǎng)學(xué)金等級的評定，即對分?jǐn)?shù)達(dá)標(biāo)者的成績進(jìn)行排序以確定獎(jiǎng)學(xué)金等級。閱卷教師會(huì)將學(xué)生的分?jǐn)?shù)保存在一個(gè)文件中，C語言判定獎(jiǎng)學(xué)金等級的程序需要通過C語言標(biāo)準(zhǔn)函數(shù)將文件中的信息讀出并做出排序、評級處理，再通過C語言標(biāo)準(zhǔn)函數(shù)將處理后的數(shù)據(jù)寫入文件。本任務(wù)通過編寫一個(gè)簡單的獎(jiǎng)學(xué)金等級判定程序，掌握文件的打開、關(guān)閉、讀取和寫入等操作，掌握讀文件、寫文件、定位文件的方法。306本任務(wù)的具體要求是編寫一個(gè)簡單的“判定獎(jiǎng)學(xué)金等級”程序，獎(jiǎng)學(xué)金等級判定標(biāo)準(zhǔn)為平均分在90分以上的為A等，80分（不含）到90分（含）的為B等。假設(shè)學(xué)生成績已經(jīng)輸入score.txt文件，內(nèi)容如下。LiuMing,2022123,100,80,91LiKai,2022124,90,70,84OuyangZhengsheng,2022125,68,74,80WangJiaming,2022126,91,59,60WangMing,2022127,80,77,95其中第一列是姓名，第二列是學(xué)號，第三列是數(shù)學(xué)成績，第四列是語文成績，第五列是英語成績?！芭卸í?jiǎng)學(xué)金等級”程序需要對文件進(jìn)行打開、讀取、寫入和關(guān)閉操作，實(shí)現(xiàn)輸入學(xué)號后輸出獎(jiǎng)學(xué)金等級功能。307相關(guān)知識一、C語言標(biāo)準(zhǔn)函數(shù)庫C語言標(biāo)準(zhǔn)函數(shù)庫是由美國國家標(biāo)準(zhǔn)協(xié)會(huì)（ANSI）統(tǒng)一制定的一套C語言函數(shù)標(biāo)準(zhǔn)，本書中所用到的頭文件stdio.h就是C語言標(biāo)準(zhǔn)函數(shù)庫中的一個(gè)子集，C語言標(biāo)準(zhǔn)函數(shù)庫被許多編譯器支持，使用C語言標(biāo)準(zhǔn)函數(shù)庫不用考慮硬件平臺(tái)的差異，只需要關(guān)心程序本身。308例如，早期的printf()函數(shù)在不同的操作系統(tǒng)平臺(tái)有不同的實(shí)現(xiàn)方法，程序員若忽略這種差異，就會(huì)帶來災(zāi)難，因?yàn)橥粋€(gè)程序在不同平臺(tái)會(huì)運(yùn)行出不同的結(jié)果，這對于使用者來說是無法接受的，而標(biāo)準(zhǔn)I/O（輸入/輸出）庫具有一組I/O函數(shù)，實(shí)現(xiàn)了很多函數(shù)的跨平臺(tái)使用，所以標(biāo)準(zhǔn)I/O庫提高了程序的可移植性。在前面的項(xiàng)目中，已經(jīng)多次使用過標(biāo)準(zhǔn)I/O庫stdio.h的printf()、scanf_s()等函數(shù)，這里更深入地研究怎樣使用標(biāo)準(zhǔn)I/O庫的文件操作函數(shù)。309二、I/O的概念計(jì)算機(jī)由大量的不同設(shè)備組成，很多設(shè)備都有I/O操作。光驅(qū)、硬盤、U盤、網(wǎng)絡(luò)連接、攝像頭等都屬于帶有I/O操作的設(shè)備，不同的設(shè)備具有不同的數(shù)據(jù)通信協(xié)議，操作系統(tǒng)提供統(tǒng)一的I/O操作接口，使用戶可以不必關(guān)心I/O設(shè)備數(shù)據(jù)通信協(xié)議細(xì)節(jié)。標(biāo)準(zhǔn)I/O庫將I/O的概念抽象為所有的I/O操作只是簡單地從程序移入或者移出字節(jié)，就像水流一樣，所以從程序移入或者移出的字節(jié)被稱為字節(jié)流，簡稱為流。程序只需要關(guān)心是否創(chuàng)建了正確的輸出字節(jié)流數(shù)據(jù)，以及讀入端是否能正確地讀取字節(jié)流數(shù)據(jù)。310流分為文本流和二進(jìn)制流兩種類型。文本流是指在流中的數(shù)據(jù)是以字符的形式出現(xiàn)，包括回車和換行等操作。文本流在不同的系統(tǒng)中可能有不同的類型，最典型的例子就是文本行的結(jié)束方式，在Windows的命令提示符界面中一個(gè)回車符“\r”和一個(gè)換行符“\n”都代表著一行的結(jié)束，而UNIX系統(tǒng)以及類UNIX系統(tǒng)的Linux系統(tǒng)中則以一個(gè)換行符“\n”代表一行的結(jié)束。二進(jìn)制流就不會(huì)存在這一問題，因?yàn)槎M(jìn)制流是完全根據(jù)輸入或輸出的字節(jié)順序?qū)懭牖蛘咦x出的，流中的數(shù)據(jù)沒有做任何形式的改變，這種流適用于非文本數(shù)據(jù)。311每個(gè)被使用的文件都在內(nèi)存中開辟了一個(gè)相應(yīng)的文件信息區(qū)，用來存放文件相關(guān)的信息。這些文件保存在一個(gè)結(jié)構(gòu)體變量中，這個(gè)結(jié)構(gòu)體類型是由系統(tǒng)聲明的，名稱是FILE（文件類型結(jié)構(gòu)體變量）。如果想訪問一個(gè)流，需要使用FILE類型的數(shù)據(jù)結(jié)構(gòu)，它被聲明在stdio.h中，每個(gè)操作系統(tǒng)都會(huì)提供至少三個(gè)流，即標(biāo)準(zhǔn)輸入（stdin）、標(biāo)準(zhǔn)輸出（stdout）、標(biāo)準(zhǔn)錯(cuò)誤輸出（stderr），它們都是FILE結(jié)構(gòu)體的指針，在默認(rèn)的情況下，標(biāo)準(zhǔn)輸入是默認(rèn)的輸入來源，標(biāo)準(zhǔn)輸出是默認(rèn)的輸出設(shè)置，標(biāo)準(zhǔn)錯(cuò)誤輸出代表在出錯(cuò)的時(shí)候錯(cuò)誤信息的輸出設(shè)置。312三、流的操作方法1.?打開流打開流使用的是文件操作函數(shù)fopen_s()，具體步驟如下。首先，使用下列語句定義兩個(gè)變量。然后，使用文件操作函數(shù)fopen_s()打開流，語句如下。313其中，第一個(gè)參數(shù)fp是文件的二級指針，后兩個(gè)參數(shù)都是字符串類型的，參數(shù)name代表的是打開的文件或者設(shè)備的名稱，應(yīng)輸入完整的路徑名或者相對路徑名，參數(shù)mode代表流的打開模式，表示流是可讀、可寫還是可讀寫，以及是文本流還是二進(jìn)制流。下表中列舉了一些常用流的模式。314常用流的模式參數(shù)mode是以r、w或者a開頭的字符串，r代表打開的流用于讀取，w代表將向打開的流中寫入內(nèi)容，a代表將向打開的流中添加內(nèi)容。mode為r時(shí)打開的文件必須是存在的。當(dāng)mode為w時(shí)，如果打開的文件不存在，系統(tǒng)就會(huì)自動(dòng)地創(chuàng)建一個(gè)文件；如果打開的文件是存在的，那么文件里原來的內(nèi)容會(huì)被刪除。但當(dāng)mode為a時(shí)，文件里原來的內(nèi)容不會(huì)被刪除，新內(nèi)容將被追加在源文件結(jié)尾。在上述語句中，函數(shù)fopen_s()打開文件成功返回0，失敗返回非0。所以變量err接收的是0或非0。3152.?關(guān)閉流與打開流文件操作函數(shù)fopen_s()對應(yīng)的是關(guān)閉流文件操作函數(shù)fclose()。fclose()函數(shù)的一般形式如下。intfclose(FILE*flow);316fclose()函數(shù)的參數(shù)flow是一個(gè)FILE結(jié)構(gòu)體指針，它其實(shí)就是fopen_s()函數(shù)返回的FILE指針，fclose()函數(shù)執(zhí)行成功時(shí)返回0，失敗時(shí)返回EOF，EOF的值通常為-1。在使用fclose()函數(shù)時(shí)仍然要判斷函數(shù)執(zhí)行是否成功。使用有返回值的函數(shù)時(shí)一定要檢查返回值是否合法，這有助于提高程序的質(zhì)量。使用fclose()函數(shù)就可以把緩沖區(qū)內(nèi)最后剩余的數(shù)據(jù)輸出到磁盤文件中，并釋放文件指針和有關(guān)的緩沖區(qū)。317【例】運(yùn)用已學(xué)的知識，使用文件操作函數(shù)fopen_s()打開名字為data.txt的文本文件，然后用fclose()函數(shù)關(guān)閉該文件。318C盤中存在文件data.txt時(shí)，程序運(yùn)行結(jié)果如圖所示。319文件存在時(shí)的程序運(yùn)行結(jié)果C盤中不存在data.txt時(shí)，程序運(yùn)行結(jié)果如圖所示。關(guān)閉文件是否成功只能通過檢查fclose()函數(shù)的返回值來判定，當(dāng)main()函數(shù)執(zhí)行完退出時(shí)也會(huì)自動(dòng)關(guān)閉打開的文件。320

文件不存在時(shí)的程序運(yùn)行結(jié)果3.?文件定位前面例子中對文件的訪問都是線性順序的，但有時(shí)程序需要對文件進(jìn)行隨機(jī)訪問，例如，一個(gè)學(xué)生學(xué)號和平均分對應(yīng)關(guān)系的文件，它的前半部分是學(xué)號，后半部分是分?jǐn)?shù)，當(dāng)程序需要讀取前半部分的時(shí)候只需要從頭開始讀，但當(dāng)需要讀取分?jǐn)?shù)的時(shí)候，則需要將流的起始位置定位到學(xué)號的后面。文件流的隨機(jī)訪問需要使用以下兩個(gè)函數(shù)來實(shí)現(xiàn)。321ftell()函數(shù)的參數(shù)是fopen_s()函數(shù)返回的FILE結(jié)構(gòu)體指針，即ftell()函數(shù)返回流當(dāng)前的位置，在文本流中這個(gè)位置其實(shí)是文件起始位置到當(dāng)前位置的一個(gè)偏移量，而在二進(jìn)制流中這個(gè)位置是當(dāng)前距離文件起始位置的字節(jié)數(shù)。fseek()函數(shù)用于在流中定位，它將改變下一次讀或?qū)懙牟僮魑恢茫梢岳斫鉃閒seek()函數(shù)臨時(shí)改變了流的起始位置。參數(shù)stream是需要改變的流，參數(shù)offset和whence共同決定了需要定位的位置，下表描述了不同的whence值所對應(yīng)的offset代表的意義。322使用fseek()函數(shù)時(shí)，不要將流定位到文件的起始位置之前的位置，而把流定位到文件結(jié)尾時(shí)將會(huì)從文件的尾部追加內(nèi)容。使用fseek()函數(shù)改變流的位置會(huì)引發(fā)一些問題，包括文件的行末符會(huì)被清除（Windows命令提示符下為“\r”“\n”，UNIX系統(tǒng)下為“\n”），以及定位允許流從寫入模式切換到讀取模式，或者回到打開的流以便更新。323

不同的whence值所對應(yīng)的offset代表的意義求水仙花數(shù)——實(shí)際問題的算法設(shè)計(jì)任務(wù)2324學(xué)習(xí)目標(biāo)1.能合理設(shè)計(jì)算法，應(yīng)用C程序解決實(shí)際問題。2.掌握現(xiàn)實(shí)世界到機(jī)器世界的基本抽象思維方法。325任務(wù)描述春天是鮮花盛開的季節(jié)，水仙花是最迷人的鮮花之一。而數(shù)學(xué)上也有個(gè)水仙花數(shù)，它是指一個(gè)各位數(shù)字的立方和等于它本身的整數(shù)，例如153=13+53+33。如何找出1000以內(nèi)的所有水仙花數(shù)呢？可以使用窮舉法，每個(gè)數(shù)試一遍，但是人工執(zhí)行這種做法太耗時(shí)也太耗力，而使用C語言，把重復(fù)性的工作交給計(jì)算機(jī)來做就簡單多了。本任務(wù)通過解決水仙花數(shù)問題，掌握如何應(yīng)用C語言將復(fù)雜問題變簡單，培養(yǎng)應(yīng)用C語言整體知識的意識，逐步提高通過編寫C程序解決實(shí)際問題的能力。326本任務(wù)的具體要求是編寫程序，求出1000以內(nèi)的所有水仙花數(shù)。把1000以內(nèi)每個(gè)3位數(shù)的個(gè)位、十位、百位上的數(shù)字計(jì)算出來，判斷這3個(gè)數(shù)字的立方和是否等于原3位數(shù)，輸出1000以內(nèi)的所有水仙花數(shù)。327相關(guān)知識一、應(yīng)用C語言設(shè)計(jì)簡單的應(yīng)用程序系統(tǒng)在信息化管理的超市里，商品的進(jìn)、銷、存都使用計(jì)算機(jī)程序來處理，超市的管理人員可隨時(shí)通過計(jì)算機(jī)查看商品的出售和庫存信息。結(jié)算員使用POS機(jī)掃描每件商品的標(biāo)碼，就會(huì)顯示商品的數(shù)量、金額，如果有打折商品，則顯示折后的價(jià)格。超市用的這一整套信息管理系統(tǒng)都可以通過C語言編程實(shí)現(xiàn)。以下示例中的程序就簡單模擬了這一系統(tǒng)。328二、應(yīng)用C語言解決邏輯思維的抽象問題所有的程序設(shè)計(jì)語言都提供抽象，抽象的類型和質(zhì)量直接影響著解決問題的難易，在C語言程序設(shè)計(jì)中，必須按照機(jī)器的結(jié)構(gòu)去思考，將實(shí)際問題轉(zhuǎn)化成機(jī)器世界中的問題并抽象出問題的模型。例如，在屏幕上輸出數(shù)字1099，使用printf()函數(shù)即可，如果分別輸出1099的個(gè)位、十位、百位、千位上的數(shù)，只使用printf()函數(shù)是不夠的，還需要對每一位的數(shù)取出的過程進(jìn)行抽象設(shè)計(jì)，取千位上的數(shù)，需要將原始數(shù)據(jù)除以1000后取整，取百位上的數(shù)，需要將原始數(shù)據(jù)減去千位上的數(shù)，然后除以100后取整，依此類推即可求出每個(gè)位上的數(shù)。329三、應(yīng)用C語言解決計(jì)算問題計(jì)算器是日常進(jìn)行數(shù)學(xué)運(yùn)算最常用的工具，應(yīng)用C語言可以編寫一個(gè)簡單的計(jì)算器程序。計(jì)算器最核心的部分是它的計(jì)算方法，簡單的運(yùn)算有加、減、乘、除運(yùn)算，復(fù)雜一點(diǎn)的運(yùn)算有冪運(yùn)算、開方運(yùn)算、三角函數(shù)運(yùn)算等。如果只實(shí)現(xiàn)加、減、乘、除運(yùn)算，可以將這四種運(yùn)算自定義成4個(gè)不同的函數(shù)；如果需要混合運(yùn)算，應(yīng)用函數(shù)的組合便能實(shí)現(xiàn)。自定義加、減、乘、除運(yùn)算函數(shù)的語句如下。330定義這四個(gè)函數(shù)后，在main()函數(shù)里調(diào)用相應(yīng)的函數(shù)即可實(shí)現(xiàn)一個(gè)簡單的計(jì)算器。331四、應(yīng)用C語言化復(fù)雜為簡單手動(dòng)計(jì)算1～10各數(shù)的5次方很容易，計(jì)算10～100各數(shù)的5次方就比較煩瑣了，但是用C語言計(jì)算這類問題都是一樣簡單的。C語言本身并不支持冪運(yùn)算，但是可以將冪運(yùn)算轉(zhuǎn)換成累乘運(yùn)算，即使用語句“number*number*···”，同時(shí)在程序中使用循環(huán)，從而化復(fù)雜為簡單。332安排運(yùn)動(dòng)員出場順序——排序算法的應(yīng)用任務(wù)3333學(xué)習(xí)目標(biāo)1.掌握排序的基本算法。2.能運(yùn)用常用的排序算法編寫排序程序。3.加深對數(shù)組的理解。4.提高應(yīng)用C語言解決實(shí)際問題的能力。334任務(wù)描述無論在運(yùn)動(dòng)會(huì)賽場，還是在歌唱比賽現(xiàn)場，參賽人員總是按一定順序出場的。參賽者實(shí)力不同，成績也就不同，但是每名參賽人員的成績和排名卻隨時(shí)能顯示在屏幕上，這是工作人員操作計(jì)算機(jī)排序的結(jié)果。上述排序是現(xiàn)場操作排序，序列比較短，實(shí)際工作中更多的是把大量無序記錄排列成有序的序列。應(yīng)用C語言編寫排序程序，無論數(shù)據(jù)量有多大，都能讓排序工作變得輕松、容易。本任務(wù)通過編寫安排運(yùn)動(dòng)員出場順序的程序，掌握按指定排序輸出數(shù)據(jù)的方法；結(jié)合數(shù)組知識加深對數(shù)組的理解，熟練利用C語言知識分析問題、解決問題；提升應(yīng)用C語言編寫綜合性程序的能力。335本任務(wù)的具體要求是編寫安排運(yùn)動(dòng)員出場順序的程序，以運(yùn)動(dòng)員號的大小表示運(yùn)動(dòng)員出場順序，并輸出結(jié)果。某項(xiàng)比賽的出場順序由初賽的成績來決定，成績越高出場越早，初賽成績見下表。336初賽成績相關(guān)知識排序是將一組無序的記錄序列調(diào)整為有序的記錄序列。排序分為內(nèi)部排序和外部排序。在整個(gè)排序過程中不需要訪問外存便能完成的排序稱為內(nèi)部排序。若參加排序的記錄數(shù)量很大，整個(gè)序列的排序過程不可能在內(nèi)存中完成，則稱此類排序?yàn)橥獠颗判?。?nèi)部排序的過程是一個(gè)逐步擴(kuò)大記錄的有序序列長度的過程。排序算法是一種基本且常用的算法。由于實(shí)際工作中處理的數(shù)據(jù)量巨大，所以排序算法對其本身的復(fù)雜度和運(yùn)行速度要求很高。337一、冒泡排序法冒泡排序法的基本思想是通過不斷對相鄰兩個(gè)數(shù)的比較和交換，逐漸使整個(gè)數(shù)列有序。具體過程是先比較前兩個(gè)數(shù)，并通過交換位置，確保較小的數(shù)在前，較大的數(shù)在后，此時(shí)第二個(gè)數(shù)一定是前兩個(gè)數(shù)中的較大數(shù)；繼續(xù)比較第二個(gè)數(shù)和第三個(gè)數(shù)，同樣通過交換，確保這兩個(gè)數(shù)中較小的數(shù)在前，較大的數(shù)在后，此時(shí)第三個(gè)數(shù)一定是前三個(gè)數(shù)中的最大數(shù)；類似的過程一直進(jìn)行下去，直到最后一個(gè)數(shù)是整個(gè)數(shù)列中的最大數(shù)，此時(shí)已經(jīng)確定了最大數(shù)在有序數(shù)列中的位置；繼續(xù)針對前面的數(shù)列進(jìn)行上述過程的排序（已找到并確定位置的數(shù)不需要參與排序），依次找出整個(gè)數(shù)列中第二大、第三大的數(shù)等，直到最終完成排序。338該方法之所以叫作冒泡排序法，是因?yàn)檎麄€(gè)排序過程與水中氣泡的上浮過程很相似。氣泡在上升過程中，由于水的密度比空氣大，氣泡中的空氣不斷與氣泡上方的水交換位置。類似地，如果將待排序的數(shù)列豎直排列，將不同大小的數(shù)據(jù)元素看作不同密度的氣泡，則根據(jù)“輕氣泡”不能在“重氣泡”之下的原則，從下到上掃描數(shù)列，凡掃描到違反本原則的“輕氣泡”，就使其向上“漂浮”（可以通過數(shù)的位置交換來實(shí)現(xiàn)），如此反復(fù)進(jìn)行，直至最后任何兩個(gè)“氣泡”都是輕者在上，重者在下為止。339在具體編程時(shí)，可以結(jié)合循環(huán)語句完成上述過程。例如，把10個(gè)整數(shù)按從小到大的順序排列，可以用二重循環(huán)方法實(shí)現(xiàn)。將外循環(huán)變量設(shè)為i，將內(nèi)循環(huán)變量設(shè)為j。外循環(huán)循環(huán)9次，內(nèi)循環(huán)依次循環(huán)9，8，…，1次。每次進(jìn)行比較的兩個(gè)元素都是與內(nèi)循環(huán)變量j有關(guān)的，它們可以分別用數(shù)組a[j]和a[j+1]標(biāo)識，i的值依次為1，2，…，9，對于每一個(gè)i，j的值依次為1，2，…，10-i。340例如，用冒泡排序法對數(shù)列49，38，65，97，76，13，27排序，第一次冒泡排序過程如下。[3849]6597761327（方括號表示每次比較的兩個(gè)數(shù)及比較結(jié)果）38[4965]977613273849[6597]761327384965[7697]132738496576[1397]273849657613[2797]341第二次冒泡排序過程重復(fù)上面的過程，最大數(shù)97不需再比較，因?yàn)樗呀?jīng)是最大數(shù)。第二次冒泡排序的結(jié)果如下。38496513277697第三次冒泡排序過程繼續(xù)重復(fù)上述過程，但是不需要比較最后的兩個(gè)數(shù)了。第三次冒泡排序的結(jié)果如下。38491327657697經(jīng)過6次冒泡排序，最終的排序結(jié)果如下。13273849657697342二、選擇排序法選擇排序法的基本思想是從無序數(shù)列中選擇最小數(shù)（或最大數(shù)）放在數(shù)列最前面，再從剩下的數(shù)中選擇最小數(shù)（或最大數(shù)）放在數(shù)列第二位，依次類推，得到排序結(jié)果。每次找到最小數(shù)后，只需將最小數(shù)和待放置位置的數(shù)做交換即可。選擇排序法的思想比較簡單，但在具體編程時(shí)，不僅需要記錄當(dāng)前最小數(shù)的值，還要隨時(shí)記錄這個(gè)最小數(shù)的位置或數(shù)組下標(biāo)，以方便之后的交換操作。343例如，用選擇排序法對數(shù)列49，38，65，97，76，13，27排序，其排序過程如下。第一次排序后13[386597764927]（只將最小數(shù)13和49交換位置）第二次排序后1327[6597764938]（將最小數(shù)27和38交換了位置）第三次排序后132738[97764965]第四次排序后13273849[769765]第五次排序后1327384965[7697]第六次排序后132738496576[97]選擇排序法排序的結(jié)果如下。13273849657697344三、插入排序法插入排序法的基本思想是將一個(gè)數(shù)插入已排好序的序列，得到一個(gè)新的有序序列，上述過程不斷進(jìn)行，有序序列的長度逐漸由小變大，最后整個(gè)序列都是有序的。首先序列中第一個(gè)數(shù)本身就是一個(gè)長度為1的序列，當(dāng)然也是排好序的；然后，將第二個(gè)數(shù)插入這個(gè)序列，并調(diào)整位置使得前兩個(gè)數(shù)之間有序；繼續(xù)將第三個(gè)數(shù)插入前兩個(gè)數(shù)組成的有序序列，并調(diào)整位置使得前三個(gè)數(shù)之間有序；不斷進(jìn)行類似過程，直到整個(gè)序列都變得有序。345對于數(shù)組元素排序，插入排序法的特點(diǎn)是每次插入元素后的調(diào)整位置都會(huì)帶來數(shù)組中一系列元素的整體移動(dòng)，而且是先移動(dòng)后插入。最壞情況是每次插入的位置都位于整個(gè)有序序列的前面，這就需要將當(dāng)前有序序列中的所有元素都向后移動(dòng)一位。例如，用插入排序法對數(shù)列49，38，65，97，76，13，27排序，其排序過程如下。346初始情況[49]386597761327（括號表示當(dāng)前的有序序列）第一次插入38[3849]6597761327第二次插入65[384965]97761327第三次插入97[38496597]761327第四次插入76[3849657697]1327第五次插入13[133849657697]27第六次插入27[13273849657697]該數(shù)列的排序結(jié)果如下。13273849657697347四、快速排序法快速排序法是目前程序設(shè)計(jì)中解決問題最快的排序方法之一（視解題的對象而定）?？焖倥判蚍ǖ幕舅枷胧窃跀?shù)列中找出比較合適的軸位置，根據(jù)各元素與軸元素的大小關(guān)系，將數(shù)列分成大于軸元素的數(shù)和小于軸元素的數(shù)兩部分，再分別對兩部分的數(shù)列進(jìn)行排序，快速排序法效率高低取決于軸位置的選擇。348快速排序法的整個(gè)過程可以分為兩步。首先，將數(shù)列中的數(shù)重新劃分成兩部分，即大于軸元素的數(shù)和小于軸元素的數(shù)，然后遞歸地計(jì)算這兩部分?jǐn)?shù)列的排序。排序的關(guān)鍵是第一步，即如何對數(shù)列進(jìn)行劃分。應(yīng)用快速排序法時(shí)，軸元素的設(shè)定一般有三種方式，即將數(shù)列中最左邊、中間和最右邊的數(shù)設(shè)為軸元素。3491.?將數(shù)列中最左邊的數(shù)設(shè)為軸元素例如，用快速排序法按從大到小的順序?qū)σ韵聰?shù)列進(jìn)行排序，設(shè)49作為軸元素，具體劃分過程如下。49386597761327（用[]表示已滿足劃分條件的元素，用下劃線表示待處理的元素）從右側(cè)找到第一個(gè)大于軸元素的數(shù)76，括號中均是小于等于軸元素的數(shù)，劃分情況如下。4938659776[1327]將76和左邊待處理的數(shù)交換位置，括號中的數(shù)均已完成劃分，劃分情況如下。[76]38659749[1327]350從左側(cè)找到第一個(gè)小于軸元素的數(shù)38，并與右邊待處理的數(shù)交換位置，劃分情況如下。[76]496597[381327]繼續(xù)從右側(cè)尋找第一個(gè)大于軸元素的數(shù)97，并與左側(cè)待處理的數(shù)交換位置，劃分情況如下。[7697]65

49[381327]此時(shí)在左側(cè)已經(jīng)找不到小于軸元素的數(shù)，劃分結(jié)束，劃分結(jié)果如下。[769765]49[381327]3512.?將數(shù)列中間的數(shù)設(shè)為軸元素快速排序法的第二種方法是將數(shù)列中間的數(shù)設(shè)為軸元素，以這個(gè)值作為基準(zhǔn)進(jìn)行比較，這可以提高快速排序法的效率。具體方法是先將中間的數(shù)與最左側(cè)的數(shù)交換位置，之后的過程與軸元素在最左側(cè)時(shí)的情況相同。3.?將數(shù)列中最右邊的數(shù)設(shè)為軸元素快速排序法的第三種方法是以數(shù)列中最右邊的數(shù)為軸元素作比較標(biāo)準(zhǔn)，將整個(gè)數(shù)列分為兩部分，第一部分是小于最右邊的數(shù)，第二部分是大于最右邊的數(shù)。352解決猴子吃桃問題——遞歸算法的應(yīng)用任務(wù)4353學(xué)習(xí)目標(biāo)1.能正確運(yùn)用遞歸算法編寫程序。2.能使用不同的算法解決同一問題。3.加深對C語言知識的理解和綜合應(yīng)用。354任務(wù)描述一只勤勞的猴子摘了很多桃子，當(dāng)天，它吃了其中的一半桃子，覺得不過癮，又多吃了一個(gè)桃子。第二天，它又吃了剩下的一半桃子，還是覺得不過癮，又多吃了一個(gè)桃子。在以后的日子里，它每天都吃掉前一天剩下桃子的一半加一個(gè)。到了第10天，只剩下了一個(gè)桃子。那么猴子一共摘了多少個(gè)桃子呢？解決這一經(jīng)典問題雖然有其他方法，但是用C語言編寫程序會(huì)很容易得到答案。運(yùn)行在計(jì)算機(jī)中大大小小的程序，其本質(zhì)就是合理的“數(shù)據(jù)結(jié)構(gòu)+高效的算法+健壯的代碼”。其中數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式；算法是程序的核心，指定了程序的運(yùn)行步驟；代碼是算法里的步驟和數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)。355本任務(wù)通過解決猴子吃桃問題，介紹如何應(yīng)用遞歸函數(shù)編寫程序，解決遞歸類的問題，通過對遞歸算法與循環(huán)算法的比較，加深對C語言算法的理解，掌握算法的應(yīng)用。本任務(wù)的具體要求是先應(yīng)用遞歸函數(shù)編寫程序，計(jì)算猴子一共摘了多少個(gè)桃子，再用循環(huán)結(jié)構(gòu)編寫程序，計(jì)算猴子一共摘了多少個(gè)桃子。比較兩種方法的異同，體會(huì)如何使用不同的算法解決同一問題。356相關(guān)知識一、遞歸算法遞歸算法是C程序設(shè)計(jì)時(shí)經(jīng)常用到的算法，也是循環(huán)的另一種表現(xiàn)形式。C程序中的遞歸指一個(gè)過程或函數(shù)在其