基礎(chǔ)實(shí)驗(yàn)題目

1、基礎(chǔ)實(shí)驗(yàn)題目目錄實(shí)驗(yàn)一 線性表的基礎(chǔ)訓(xùn)練（2次上機(jī)）2實(shí)驗(yàn)二 棧、隊(duì)列及其應(yīng)用（1.52.5次上機(jī)）3實(shí)驗(yàn)三 二叉樹(shù)及其應(yīng)用（2次上機(jī)）5實(shí)驗(yàn)四 圖及其應(yīng)用（23次上機(jī)）7附錄 Makefile 、GCC、pkg-config 使用說(shuō)明81GCC的使用82pkg-config的作用113Makefile的作用11實(shí)驗(yàn)一 線性表的基礎(chǔ)訓(xùn)練（12次上機(jī)）【上機(jī)時(shí)間】第12次【實(shí)驗(yàn)?zāi)康摹渴煜ふ莆毡鹃T(mén)課程所使用的程序設(shè)計(jì)語(yǔ)言(C語(yǔ)言)，體會(huì)算法與程序之間的區(qū)別：1、 熟悉VC等編程環(huán)境，學(xué)會(huì)單步跟蹤、調(diào)試自己的程序；2、 了解project的創(chuàng)建、使用以及意義；3、 熟練定義含指向結(jié)構(gòu)體自身的指針域的

2、結(jié)構(gòu)體類型，掌握此類變量、指針變量的初始化、賦值、輸入/輸出、參數(shù)傳遞；4、 熟練使用C中的動(dòng)態(tài)分配與釋放函數(shù)(malloc, realloc, free)；5、 熟悉帶參數(shù)的main函數(shù)的編寫(xiě)與運(yùn)行；6、 類C的引用參數(shù)在C中的變換處理；7、 利用輸入導(dǎo)向，從文件中獲取輸入數(shù)據(jù)。初步理解線性表的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)特性,掌握在不同存儲(chǔ)結(jié)構(gòu)、不同約定下，其基本操作的實(shí)現(xiàn)方法與差異。體會(huì)以下幾點(diǎn)（注意你所做的約定）：1、 靜態(tài)分配的順序表及增量式分配的順序表在表示與實(shí)現(xiàn)上的差別，各有何特點(diǎn)；2、 有頭結(jié)點(diǎn)的鏈表與無(wú)頭結(jié)點(diǎn)鏈表在操作實(shí)現(xiàn)上的區(qū)別；3、 頭插法與尾插法的操作方法及應(yīng)用效果對(duì)比；4、 插

3、入、刪除操作在順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)上的差別；5、 非循環(huán)單鏈表、循環(huán)單鏈表各適用于解決哪些問(wèn)題，它們?cè)跀?shù)據(jù)類型定義、操作的定義及實(shí)現(xiàn)上各有什么區(qū)別？6、 靜態(tài)鏈表與動(dòng)態(tài)鏈表之間的映射與差別（自選）?！緦?shí)驗(yàn)要求】1、 下載Gzip的相關(guān)資源，用VC為Gzip建立project，編譯并運(yùn)行Gzip；給出3種以上的命令行輸入，單步跟蹤Gzip對(duì)命令行參數(shù)的處理；學(xué)習(xí)帶參的main的使用與編程。消化理解一些標(biāo)識(shí)符和文件操作。目的：開(kāi)展程序理解的第一階段。2、 下載ch2.rar并閱讀其中的代碼。其中c1.h是第1章預(yù)設(shè)的一些宏和類型名， c2-1.h是順序表的類型定義，c2-2.h是鏈表的類型定義，bo

4、2-1.c是ADT List中基本操作的順序表實(shí)現(xiàn), bo2-2.c是ADT List中基本操作的鏈表實(shí)現(xiàn)，algo2-1.c是例2-1的順序表實(shí)現(xiàn)，algo2-12.c是例2-1的鏈表實(shí)現(xiàn)，algo2-12a.c是改寫(xiě)algo2-12.c的Union()函數(shù)。目的：體會(huì)用偽C表示的算法和C程序之間的差異。3、 閱讀數(shù)據(jù)結(jié)構(gòu)題集P79 1.2約瑟夫環(huán)，理解約瑟夫環(huán)的定義。編寫(xiě)一個(gè)程序，該程序根據(jù)輸入的命令行參數(shù)創(chuàng)建一個(gè)單循環(huán)鏈表表示的約瑟夫環(huán)，然后輸出約瑟夫環(huán)出列的順序。命令行格式： 可執(zhí)行程序名人數(shù)n初始的報(bào)數(shù)上限m密碼1 密碼n·第1個(gè)參數(shù)是你所編寫(xiě)的程序的可執(zhí)行文件名，

5、3;第2個(gè)參數(shù)是指定形成約瑟夫環(huán)的人數(shù)n·第3個(gè)參數(shù)是指定初始的報(bào)數(shù)上限m·后面n個(gè)參數(shù)是n個(gè)人所持有的整數(shù)密碼。當(dāng)除可執(zhí)行程序名外，沒(méi)有參數(shù)時(shí)，將繼續(xù)執(zhí)行程序并提示用戶輸入這些參數(shù)?；疽螅?）假設(shè)命令行參數(shù)是齊全的且是正確的，運(yùn)行所編寫(xiě)的程序能正確地輸出結(jié)果；2）能將輸出結(jié)果導(dǎo)到文件中。實(shí)驗(yàn)提示：該實(shí)驗(yàn)的處理可分以下幾個(gè)模塊：1）命令行參數(shù)的處理；2）單循環(huán)鏈表的創(chuàng)建；3）根據(jù)m和起始報(bào)數(shù)人對(duì)應(yīng)在單循環(huán)鏈表中的位置，確定出列人的位置；4）刪除出列人對(duì)應(yīng)的結(jié)點(diǎn)。選作要求：1）程序有對(duì)命令行參數(shù)不全或不正確的處理(如提示輸入、報(bào)錯(cuò)等)；2）將約瑟夫環(huán)用順序表實(shí)現(xiàn)。4、 撰

6、寫(xiě)實(shí)驗(yàn)報(bào)告?！緳z查期限】1、 上機(jī)內(nèi)容檢查時(shí)間：第2次和第3次上機(jī)時(shí)，以第3次上機(jī)為截止時(shí)間；2、 報(bào)告上交截止時(shí)間：第2次上機(jī)后的第一次課的上課前截止。實(shí)驗(yàn)二 棧、隊(duì)列及其應(yīng)用（1.52.5次上機(jī)）【上機(jī)時(shí)間】第3次，第4次【實(shí)驗(yàn)?zāi)康摹可钊肜斫鈼：完?duì)列的特性，領(lǐng)會(huì)它們各自的應(yīng)用背景。熟練掌握它們?cè)诓煌鎯?chǔ)結(jié)構(gòu)、不同的約定中，其基本操作的實(shí)現(xiàn)方法與差異。體會(huì)以下幾點(diǎn)（注意你所做的約定）：1、 棧：順序棧（?？?棧滿條件，入棧/出棧）、鏈棧（?？諚l件，入棧/出棧）；2、 隊(duì)列：鏈隊(duì)列（隊(duì)空條件，入隊(duì)/出隊(duì)）、順序隊(duì)列/循環(huán)順序隊(duì)列（隊(duì)空/隊(duì)滿條件，入隊(duì)/出隊(duì)）；【實(shí)驗(yàn)內(nèi)容】本次實(shí)驗(yàn)共五個(gè)題目，可

7、任選其中的一題或多題。1. 魔王語(yǔ)言解釋具體要求參見(jiàn)數(shù)據(jù)結(jié)構(gòu)題集P97,實(shí)習(xí)2.2中的描述。2. 算術(shù)表達(dá)式求值的演示具體要求參見(jiàn)數(shù)據(jù)結(jié)構(gòu)題集P99實(shí)習(xí)2.5中的描述。3. N-皇后問(wèn)題假設(shè)有一N×N的棋盤(pán)和N個(gè)皇后，請(qǐng)為這N個(gè)皇后進(jìn)行布局使得這N個(gè)皇后互不攻擊(即任意兩個(gè)皇后不在同一行、同一列、同一對(duì)角線上。要求：1) 輸入N，輸出N個(gè)皇后互不攻擊的布局；2) 要求用非遞歸方法來(lái)解決N-皇后問(wèn)題，即自己設(shè)置棧來(lái)處理。4. 背包問(wèn)題假設(shè)有一個(gè)能裝入總體積為T(mén)的背包和n件體積分別為w1 , w2 , , wn 的物品，能否從n件物品中挑選若干件恰好裝滿背包，即使w1 +w2 + + w

8、n=T，要求找出所有滿足上述條件的解。例如：當(dāng)T=10，各件物品的體積1，8，4，3，5，2時(shí)，可找到下列4組解：（1，4，3，2） （1，4，5） （8，2） （3，5，2）。提示：可利用回溯法的設(shè)計(jì)思想來(lái)解決背包問(wèn)題。首先將物品排成一列，然后順序選取物品裝入背包，假設(shè)已選取了前i 件物品之后背包還沒(méi)有裝滿，則繼續(xù)選取第i+1件物品，若該件物品“太大”不能裝入，則棄之而繼續(xù)選取下一件，直至背包裝滿為止。但如果在剩余的物品中找不到合適的物品以填滿背包，則說(shuō)明“剛剛”裝入背包的那件物品“不合適”，應(yīng)將它取出“棄之一邊”，繼續(xù)再?gòu)摹八蟆钡奈锲分羞x取，如此重復(fù)，直至求得滿足條件的解，或者無(wú)解。5

9、. MML命令解釋說(shuō)明：MML命令又稱人機(jī)交互語(yǔ)言，作用就是客戶端通過(guò)發(fā)送有意義的命令字符串來(lái)獲取服務(wù)器的服務(wù)。它的格式有很多種，它的格式有很多種，我們要支持下面兩種：1) 命令字：參數(shù)1=參數(shù)1值，參數(shù)2=參數(shù)2值，.,.,.有一個(gè)命令字和很多的參數(shù)塊，每個(gè)參數(shù)塊中有很多的參數(shù)，參數(shù)之間用逗號(hào)隔開(kāi)參數(shù)值的類型有兩種，整型和字符串。2) 命令字:.,.;命令字:.,.;命令字:.,.有很多的命令字，每?jī)蓚€(gè)命令字之間用分號(hào)隔開(kāi)，每個(gè)命令字可以有很多的參數(shù)塊，每個(gè)參數(shù)塊的內(nèi)容同格式1）；基本要求：1) 提取所有的參數(shù)及其值，其中值為用雙/單引號(hào)括住的字符串值或者整型值；2) 打印有多少個(gè)命令字和參

10、數(shù)塊個(gè)數(shù)以及參數(shù)的個(gè)數(shù)；3) 遇到非法輸入要報(bào)警；附加要求：1) 對(duì)非法輸入報(bào)告其類型，如字符串沒(méi)有引號(hào)等等；2) 限定參數(shù)必須為合法的標(biāo)識(shí)符(即字母或下劃線開(kāi)始的、由字母數(shù)字下劃線組成的字符串)，對(duì)非法的標(biāo)識(shí)符要報(bào)錯(cuò)；補(bǔ)充：如果程序的健壯性很強(qiáng)，即遇到精心設(shè)計(jì)的測(cè)試用例不會(huì)死機(jī)，可以提示輸入錯(cuò)，則加分?！緦?shí)驗(yàn)要求】1. 要求所編寫(xiě)的程序應(yīng)：a) 必須帶命令行參數(shù)；b) 必須通過(guò)命令行參數(shù)指定輸入、輸出文件的文件名，練習(xí)對(duì)文件的操作。2. 撰寫(xiě)實(shí)驗(yàn)報(bào)告?！緳z查期限】1 上機(jī)內(nèi)容檢查時(shí)間：第35次上機(jī)時(shí)，以第5次上機(jī)為截止時(shí)間；2 報(bào)告上交截止時(shí)間：第4次上機(jī)后的第一次課的上課前截止。實(shí)驗(yàn)三 二

11、叉樹(shù)及其應(yīng)用（2次上機(jī)）【上機(jī)時(shí)間】第57次【實(shí)驗(yàn)?zāi)康摹繕?shù)是一種應(yīng)用極為廣泛的數(shù)據(jù)結(jié)構(gòu)之一，是本課程的重點(diǎn)。樹(shù)是一種1:N的非線性結(jié)構(gòu)。本章首先以二叉樹(shù)這種特殊、簡(jiǎn)單的樹(shù)為原型，討論數(shù)據(jù)元素(結(jié)點(diǎn))之間的1:N(N=0,1,2)關(guān)系的表示(順序映像完全二叉樹(shù)的順序存儲(chǔ)；鏈?zhǔn)接诚穸骀湵?、三叉鏈?；重點(diǎn)介紹二叉樹(shù)的各種遍歷算法(先序、中序、后序、層次遍歷)；并以這些遍歷算法為基礎(chǔ)，進(jìn)一步討論二叉樹(shù)的其他各種問(wèn)題的求解算法。然后，展開(kāi)對(duì)一般樹(shù)的表示(雙親表示法、孩子表示法、孩子-兄弟表示法)和操作算法的討論；強(qiáng)調(diào)樹(shù)(森林)的孩子-兄弟表示法及其相關(guān)應(yīng)用；并將表示樹(shù)(森林)的孩子-兄弟鏈映射到表示

12、二叉樹(shù)的二叉鏈，從而獲得樹(shù)(森林)與二叉樹(shù)的相互轉(zhuǎn)換。本實(shí)驗(yàn)以二叉樹(shù)的鏈?zhǔn)奖硎尽⒔⒑蛻?yīng)用為基礎(chǔ)，旨在讓學(xué)生深入了解二叉樹(shù)的存儲(chǔ)表示特征以及遍歷次序與二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)之間的關(guān)系，進(jìn)一步掌握利用遍歷思想解決二叉樹(shù)中相關(guān)問(wèn)題的方法。本實(shí)驗(yàn)的另一個(gè)目的是讓學(xué)生通過(guò)思考、上機(jī)實(shí)踐與分析總結(jié)，理解計(jì)算機(jī)進(jìn)行算術(shù)表達(dá)式解析、計(jì)算的可能方法，初步涉及一些編譯技術(shù)，增加自己今后學(xué)習(xí)編譯原理的興趣，并奠定一些學(xué)習(xí)的基礎(chǔ)?！緦?shí)驗(yàn)內(nèi)容】本實(shí)驗(yàn)由以下環(huán)節(jié)組成：1） 存儲(chǔ)結(jié)構(gòu)以二叉鏈表或三叉鏈表作為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)；2） 二叉樹(shù)的創(chuàng)建(鏈?zhǔn)酱鎯?chǔ))以某一種遍歷的次序錄入二叉樹(shù)的元素，寫(xiě)出相應(yīng)的二/三叉鏈表的創(chuàng)建算法，并上

13、機(jī)實(shí)現(xiàn)該算法；二叉樹(shù)的輸入次序可以有如下幾種方法，你可以選擇其中之一來(lái)作為二/三叉鏈表創(chuàng)建程序的輸入：ABCEDFGH圖 1(1) 添加虛結(jié)點(diǎn)補(bǔ)足成完全二叉樹(shù)，對(duì)補(bǔ)足虛結(jié)點(diǎn)后的二叉樹(shù)按層次遍歷次序輸入。如圖1的二叉樹(shù)輸入次序?yàn)椋?A, B, C, F, D, E, F, F, F, G, F, F, H也可以通過(guò)添加虛結(jié)點(diǎn)，為每一實(shí)在結(jié)點(diǎn)補(bǔ)足其孩子，再對(duì)補(bǔ)足虛結(jié)點(diǎn)后的二叉樹(shù)按層次遍歷的次序輸入。如圖1的二叉樹(shù)輸入次序?yàn)椋?A, B, C, F, D, E, F, G, F, F, H, F, F, F, F, F, F進(jìn)一步改進(jìn)，可以在輸入列表中忽略出現(xiàn)在列表尾部的虛結(jié)點(diǎn)，即： A, B, C

14、, F, D, E, F, G, F, F, H(2) 通過(guò)添加虛結(jié)點(diǎn)，將二叉樹(shù)中的每一實(shí)在結(jié)點(diǎn)補(bǔ)足成度為2的結(jié)點(diǎn)，對(duì)補(bǔ)足虛結(jié)點(diǎn)后的二叉樹(shù)按先序遍歷的次序輸入。如圖1的二叉樹(shù)輸入次序?yàn)椋?A, B, F, D, G, F, F, F, C, E, F, H, F, F, F, F, F(3) 依次輸入二叉樹(shù)的中序和后序遍歷的結(jié)果。如圖1的二叉樹(shù)輸入次序?yàn)椋?中序：B, G, D, A, E, H, C, F 后序：G, D, B, H, E, F, C, A(4) 依次輸入二叉樹(shù)的中序和先序遍歷的結(jié)果。如圖1的二叉樹(shù)輸入次序?yàn)椋?中序：B, G, D, A, E, H, C, F 先序：A,

15、B, D, G, C, E, H, F3） 二叉樹(shù)的遍歷對(duì)所建的二叉樹(shù)進(jìn)行驗(yàn)證：按初始輸入元素采用的遍歷方法遍歷該二叉樹(shù)，看遍歷的結(jié)果是否與初始輸入一致；4） 二叉樹(shù)的應(yīng)用：線索二叉樹(shù)的創(chuàng)建基于二叉樹(shù)遍歷思想的其它問(wèn)題的求解：擴(kuò)展二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，增加表示直接后繼線索的鏈域，給出創(chuàng)建給定二叉樹(shù)的后序線索化二叉樹(shù)的程序；5） 線索二叉樹(shù)的遍歷編寫(xiě)在后序線索化樹(shù)上的遍歷算法。6） 二叉樹(shù)創(chuàng)建的特例表達(dá)式樹(shù)在2）基礎(chǔ)上，設(shè)計(jì)并實(shí)現(xiàn)為輸入表達(dá)式(僅考慮運(yùn)算符為雙目運(yùn)算符的情況)創(chuàng)建表達(dá)式樹(shù)的程序：A) 先實(shí)現(xiàn)輸入為合法的波蘭式；B) 進(jìn)一步考慮輸入為中綴表達(dá)式（需要分析優(yōu)先級(jí)和結(jié)合性）C) 考慮輸入為

16、合法的逆波蘭式；7） 二叉樹(shù)遍歷的特例表達(dá)式樹(shù)針對(duì)用6）創(chuàng)建的表達(dá)式樹(shù)，用3）遍歷(先序/中序/后序)該樹(shù)，比較它與實(shí)際的波蘭式、中綴式和逆波蘭式之間的區(qū)別；8） 二叉樹(shù)的應(yīng)用表達(dá)式求值與轉(zhuǎn)換基于3）的后序遍歷或基于5），A)完成給定表達(dá)式樹(shù)的表達(dá)式求值運(yùn)算；B)輸出表達(dá)式的另一種表示方法（如波蘭式、逆波蘭式或中綴表達(dá)式）。 【實(shí)驗(yàn)要求】1. 每一學(xué)生必須完成以下內(nèi)容：a) 1)至5)b) 6)中的A)、B)、C)之一c) 7）以及8）中的A)、B) 之一。2. 其余部分可以根據(jù)自己的實(shí)際情況酌情處理?！緳z查期限】1 上機(jī)內(nèi)容檢查時(shí)間：第68次上機(jī)時(shí)，以第8次上機(jī)為截止時(shí)間；2 報(bào)告上交截止時(shí)

17、間：第7次上機(jī)后的第1次課上課前截止。實(shí)驗(yàn)四 圖及其應(yīng)用（23次上機(jī)）【上機(jī)時(shí)間】第810次【實(shí)驗(yàn)?zāi)康摹繄D是另一種應(yīng)用極為廣泛的數(shù)據(jù)結(jié)構(gòu)，是本課程的重點(diǎn)。圖是一種M:N的非線性結(jié)構(gòu)。在圖的學(xué)習(xí)中，首先要解決如何表示圖中頂點(diǎn)之間的關(guān)系。在教材中給出了鄰接矩陣、鄰接表、鄰接多重表、十字鏈表四種存儲(chǔ)結(jié)構(gòu)，不同的存儲(chǔ)結(jié)構(gòu)有不同的應(yīng)用范圍（要求熟練掌握前兩種存儲(chǔ)結(jié)構(gòu)）。其次，必須理解深度優(yōu)先搜索和廣度優(yōu)先搜索的特征，熟練寫(xiě)出它們?cè)贏DT Graph以及在不同存儲(chǔ)結(jié)構(gòu)下的算法實(shí)現(xiàn)，并基于它們進(jìn)一步掌握生成森林(樹(shù))的構(gòu)造、連通分量的確定、關(guān)節(jié)點(diǎn)的查找等算法。再次，要能理解最小生成樹(shù)的普里姆和克魯斯卡爾算法

18、，分析它們各自的特征以及時(shí)空特性。最后，掌握有向無(wú)環(huán)圖的應(yīng)用，重點(diǎn)掌握拓?fù)渑判?入度)，理解如何利用拓?fù)渑判蜻M(jìn)行關(guān)鍵路徑的求解；理解在網(wǎng)中如何求從某源點(diǎn)到其它頂點(diǎn)以及任意兩個(gè)頂點(diǎn)之間的最短路徑(可以結(jié)合最小生成樹(shù)理解)。本實(shí)驗(yàn)是圖的基礎(chǔ)實(shí)驗(yàn)，旨在讓學(xué)生熟練掌握?qǐng)D的存儲(chǔ)表示特征，各類圖的創(chuàng)建、遍歷方法以及基于遍歷的算法應(yīng)用?！緦?shí)驗(yàn)題目】1、 圖的存儲(chǔ)結(jié)構(gòu)的定義和圖的創(chuàng)建圖的種類有：有向圖、無(wú)向圖、有向網(wǎng)、無(wú)向網(wǎng)。圖的存儲(chǔ)結(jié)構(gòu)可采用：鄰接矩陣、鄰接表。要求：分別給出鄰接矩陣和鄰接表在某一種圖上的創(chuàng)建算法2、 圖的遍歷：非遞歸的深度優(yōu)先搜索算法、廣度優(yōu)先搜索算法。3、 圖的深度遍歷的應(yīng)用：求無(wú)向連通

19、圖中的關(guān)節(jié)點(diǎn)（教材P177-178,算法7.10和7.11）4、 圖的廣度遍歷的應(yīng)用：給定圖G，輸出從頂點(diǎn)v0到其余每個(gè)頂點(diǎn)的最短路徑，要求輸出各路徑中的頂點(diǎn)信息?！緦?shí)驗(yàn)要求】1. 每一學(xué)生必須完成上述所有題2. 進(jìn)一步熟悉靜態(tài)鏈的應(yīng)用：習(xí)題集7.25,以及依據(jù)此存儲(chǔ)結(jié)構(gòu)的3和4的實(shí)現(xiàn)本項(xiàng)內(nèi)容可以根據(jù)自己的實(shí)際情況酌情處理，但是必須在實(shí)驗(yàn)報(bào)告中附上自己對(duì)靜態(tài)鏈的體會(huì)（可以結(jié)合在樹(shù)中的作業(yè)練習(xí)等來(lái)闡明）?！緳z查期限】1 上機(jī)內(nèi)容檢查時(shí)間：第910次上機(jī)時(shí)，以第10次上機(jī)為截止時(shí)間；2 報(bào)告上交截止時(shí)間：第10次上機(jī)后的第1次課上課前截止。附錄 Makefile 、GCC、pkg-config 使

20、用說(shuō)明1. GCC的使用2. pkg-config的作用3. Makefile的作用此教程還不夠完整，很多地方比較簡(jiǎn)陋，打算以后再不斷完整它，現(xiàn)在來(lái)說(shuō)用這個(gè)教程的內(nèi)容已經(jīng)能夠開(kāi)發(fā)程序了。1GCC的使用通常所說(shuō)的GCC是GUN Compiler Collection的簡(jiǎn)稱，除了編譯程序之外，它還含其他相關(guān)工具，所以它能把易于人類使用的高級(jí)語(yǔ)言編寫(xiě)的源代碼構(gòu)建成計(jì)算機(jī)能夠直接執(zhí)行的二進(jìn)制代碼。GCC是Linux平臺(tái)下最常用的編譯程序，它是Linux平臺(tái)編譯器的事實(shí)標(biāo)準(zhǔn)。同時(shí)，在Linux平臺(tái)下的嵌入式開(kāi)發(fā)領(lǐng)域，GCC也是用得最普遍的一種編譯器。GCC之所以被廣泛采用，是因?yàn)樗苤С指鞣N不同的目標(biāo)體

21、系結(jié)構(gòu)。例如，它既支持基于宿主的開(kāi)發(fā)（簡(jiǎn)單講就是要為某平臺(tái)編譯程序，就在該平臺(tái)上編譯），也支持交叉編譯（即在A平臺(tái)上編譯的程序是供平臺(tái)B使用的）。目前，GCC支持的體系結(jié)構(gòu)有四十余種，常見(jiàn)的有X86系列、Arm、 PowerPC等。同時(shí)，GCC還能運(yùn)行在不同的操作系統(tǒng)上，如Linux、Solaris、Windows等。除了上面講的之外，GCC除了支持C語(yǔ)言外，還支持多種其他語(yǔ)言，例如C+、Ada、Java、Objective-C、FORTRAN、Pascal等。程序的編譯過(guò)程對(duì)于GUN編譯器來(lái)說(shuō)，程序的編譯要經(jīng)歷預(yù)處理、編譯、匯編、連接四個(gè)階段。從功能上分，預(yù)處理、編譯、匯編是三個(gè)不同的階段，

22、但GCC的實(shí)際操作上，它可以把這三個(gè)步驟合并為一個(gè)步驟來(lái)執(zhí)行。在預(yù)處理階段，輸入的是C語(yǔ)言的源文件，通常為*.c。它們通常帶有.h之類頭文件的包含文件。這個(gè)階段主要處理源文件中的#ifdef、 #include和#define命令。該階段會(huì)生成一個(gè)中間文件*.i，但實(shí)際工作中通常不用專門(mén)生成這種文件，因?yàn)榛旧嫌貌坏剑蝗舴且蛇@種文件不可，可以利用下面的示例命令：gcc -E main.c -o main.i在編譯階段，輸入的是中間文件*.i，編譯后生成匯編語(yǔ)言文件*.s 。這個(gè)階段對(duì)應(yīng)的GCC命令如下所示：gcc -S main.i -o main.s在匯編階段，將輸入的匯編文件*.s轉(zhuǎn)換

23、成機(jī)器語(yǔ)言*.o。這個(gè)階段對(duì)應(yīng)的GCC命令如下所示：gcc -c main.s -o main.0最后，在連接階段將輸入的機(jī)器代碼文件*.s（與其它的機(jī)器代碼文件和庫(kù)文件）匯集成一個(gè)可執(zhí)行的二進(jìn)制代碼文件。這一步驟，可以利用下面的示例命令完成：gcc main.o -o mainGCC常用模式這里介紹GCC追常用的兩種模式：編譯模式和編譯連接模式。下面以一個(gè)例子來(lái)說(shuō)明各種模式的使用方法。為簡(jiǎn)單起見(jiàn)，假設(shè)我們?nèi)康脑创a都在一個(gè)文件main.c中，要想把這個(gè)源文件直接編譯成可執(zhí)行程序，可以使用以下命令：gcc -o main main.c這里main.c是源文件，生成的可執(zhí)行代碼存放在一個(gè)名為m

24、ain 的文件中（該文件是機(jī)器代碼并且可執(zhí)行）。-o 是生成可執(zhí)行文件的輸出選項(xiàng)。如果我們只想讓源文件生成目標(biāo)文件（給文件雖然也是機(jī)器代碼但不可執(zhí)行），可以使用標(biāo)記-c ，詳細(xì)命令如下所示：gcc -c main.c默認(rèn)情況下，生成的目標(biāo)文件被命名為main.o，但我們也可以為輸出文件指定名稱，如下所示：gcc -c main.c -o m.o上面這條命令將編譯后的目標(biāo)文件命名為m.o，而不是默認(rèn)的main.o。迄今為止，我們談?wù)摰某绦騼H涉及到一個(gè)源文件；現(xiàn)實(shí)中，一個(gè)程序的源代碼通常包含在多個(gè)源文件之中，這該怎么辦？沒(méi)關(guān)系，即使這樣，用GCC處理起來(lái)也并不復(fù)雜，見(jiàn)下例：gcc -o main

25、1.c 2.c 3.c需要注意的是，要生成可執(zhí)行程序時(shí)，一個(gè)程序無(wú)論有有一個(gè)源文件還是多個(gè)源文件，所有被編譯和連接的源文件中必須有且僅有一個(gè)main函數(shù)，因?yàn)閙ain 函數(shù)是該程序的入口點(diǎn)（換句話說(shuō)，當(dāng)系統(tǒng)調(diào)用該程序時(shí)，首先將控制權(quán)授予程序的main函數(shù)）。但如果僅僅是把源文件編譯成目標(biāo)文件的時(shí)候，因?yàn)椴粫?huì)進(jìn)行連接，所以main函數(shù)不是必需的。常用選項(xiàng)許多情況下，頭文件和源文件會(huì)單獨(dú)存放在不同的目錄中。例如，假設(shè)存放源文件的子目錄名為./src，而包含文件則放在層次的其他目錄下，如./inc。當(dāng)我們?cè)?/src 目錄下進(jìn)行編譯工作時(shí)，如何告訴GCC到哪里找頭文件呢？方法如下所示：gcc tes

26、t.c I./inc -o test上面的命令告訴GCC包含文件存放在./inc 目錄下，在當(dāng)前目錄的上一級(jí)。如果在編譯時(shí)需要的包含文件存放在多個(gè)目錄下，可以使用多個(gè)-I 來(lái)指定各個(gè)目錄：gcc test.c I./inc1 I././inc2 -o test這里指出了另一個(gè)包含子目錄inc2，較之前目錄它還要在再上兩級(jí)才能找到。另外，我們還可以在編譯命令行中定義符號(hào)常量。為此，我們可以簡(jiǎn)單的在命令行中使用-D選項(xiàng)即可，如下例所示：gcc -DTEST_CONFIGURATION test.c -o test上面的命令與在源文件中加入下列命令是等效的：#define TEST_CONFIGUR

27、ATION在編譯命令行中定義符號(hào)常量的好處是，不必修改源文件就能改變由符號(hào)常量控制的行為。 此外，還有一個(gè)比較重要的選項(xiàng)，就是指定編譯時(shí)需要用到的庫(kù)，用法如下：gcc    -lcurses    main.c 這個(gè)例子的意思是使用curses庫(kù)編譯程序。使用-L選項(xiàng)時(shí)后面可以放庫(kù)的路徑，編譯器就會(huì)在指定的目錄里尋找所需的庫(kù)。警告功能當(dāng)GCC 在編譯過(guò)程中檢查出錯(cuò)誤的話，它就會(huì)中止編譯；但檢測(cè)到警告時(shí)卻能繼續(xù)編譯生成可執(zhí)行程序，因?yàn)榫嬷皇轻槍?duì)程序結(jié)構(gòu)的診斷信息，它不能說(shuō)明程序一定有錯(cuò)誤，而是存在風(fēng)險(xiǎn)，或者可能存在錯(cuò)誤。雖然

28、GCC提供了非常豐富的警告，但前提是你已經(jīng)啟用了它們，否則它不會(huì)報(bào)告這些檢測(cè)到的警告。在眾多的警告選項(xiàng)之中，最常用的就是-Wall選項(xiàng)。該選項(xiàng)能發(fā)現(xiàn)程序中一系列的常見(jiàn)錯(cuò)誤警告，該選項(xiàng)用法舉例如下：gcc -Wall main.c -o main2pkg-config的作用（此部分教程還不完整，待添加新內(nèi)容）在使用GCC編譯和鏈接源代碼時(shí)，往往需要指定庫(kù)的頭文件地址和庫(kù)文件的位置。即使用-I和-L選項(xiàng)（或者-i和-l）。但是，當(dāng)編寫(xiě)程序時(shí)，往往會(huì)需要涉及到多個(gè)程序庫(kù)，比如編寫(xiě)GTK+程序時(shí)，需要用到的庫(kù)有pango、cairo、gobject、gdk等，涉及到的頭文件也很多，一一指定是非常麻煩的

29、。pkg-config簡(jiǎn)單來(lái)說(shuō)，就是一個(gè)負(fù)責(zé)替你指定所用到的頭文件和庫(kù)的地址給編譯器的工具，一般來(lái)說(shuō)，最常用的是兩個(gè)功能，一是指定編譯程序時(shí)需要用到的頭文件地址給編譯器，使用方法：gcc E main.c o main.i pkg-config cflags gtk+-2.0這條命令的意思是，假定main.c是一個(gè)GTK+程序，則pkg-config cflags gtk+-2.0這條命令會(huì)把這個(gè)程序里所用的頭文件地址告訴給gcc。注意，gcc使用-E選項(xiàng)，表示只對(duì)main.c做預(yù)處理，因?yàn)闆](méi)有指定庫(kù)函數(shù)的地址，不能加載庫(kù)函數(shù)，即不能可執(zhí)行生成模塊。另外一個(gè)重要的功能是告訴編譯器庫(kù)的位置，使用

30、方法：Gcc o main main.i pkg-config libs gtk+-.20這條命令的意思是，把main.i所可能用到的庫(kù)的目錄傳給編譯器，這樣就能編譯連接生成可知性文件了。關(guān)于pkg-config 就介紹到這里，其他內(nèi)容以后再作補(bǔ)充。3Makefile的作用3.1 Makefile簡(jiǎn)介Makefile是GNU Make的輸入文件，用來(lái)指示make怎樣自動(dòng)編譯源代碼。這個(gè)文 件里主要是有關(guān)哪些文件（target目的文件）是從哪些別的 文件（dependencies依靠文件）中產(chǎn)生的，用什么命令來(lái)進(jìn)行 這個(gè)產(chǎn)生過(guò)程。有了這些信息， make 會(huì)檢查硬盤(pán)上的文件，如果 目的文件的時(shí)間

31、戳（該文件生成或被改動(dòng)時(shí)的時(shí)間）比至少它的一個(gè)依靠文件舊的話， make 就執(zhí)行相應(yīng)的命令，以便更新目的文件。（目的文件不一定是最后的可執(zhí)行檔，它可以是任何一個(gè)文件。）Makefile 一般被叫做“Makefile”或“makefile”。當(dāng)然你可以 在 make 的命令行指定別的文件名。如果你不特別指定，它會(huì)尋 找“makefile”或“Makefile”，因此使用這兩個(gè)名字是最簡(jiǎn)單 的。一個(gè) makefile 主要含有一系列的規(guī)則，如下：: .(tab)<command>(tab)<command>.例如，考慮以下的 makefile ：-myprog : foo.

32、o bar.o gcc foo.o bar.o -o myprogfoo.o : foo.c foo.h bar.h gcc -c foo.c -o foo.obar.o : bar.c bar.h gcc -c bar.c -o bar.o-這是一個(gè)非?；镜?makefile make 從最上面開(kāi)始，把上 面第一個(gè)目的，myprog，做為它的主要目標(biāo)（一個(gè)它需要保 證其總是最新的最終目標(biāo)）。給出的規(guī)則說(shuō)明只要文件myprog 比文件foo.o或bar.o中的任何一個(gè)舊，下一行的命令將 會(huì)被執(zhí)行。但是，在檢查文件 foo.o 和 bar.o 的時(shí)間戳之前，它會(huì)往下查 找那些把 foo.o 或

33、 bar.o 做為目標(biāo)文件的規(guī)則。它找到的關(guān)于 foo.o 的規(guī)則，該文件的依靠文件是 foo.c, foo.h 和 bar.h 。 它從下面再找不到生成這些依靠文件的規(guī)則，它就開(kāi)始檢查磁碟 上這些依靠文件的時(shí)間戳。如果這些文件中任何一個(gè)的時(shí)間戳比 foo.o 的新，命令 'gcc -o foo.o foo.c' 將會(huì)執(zhí)行，從而更新 文件 foo.o 。接下來(lái)對(duì)文件 bar.o 做類似的檢查，依靠文件在這里是文件 bar.c 和 bar.h ?，F(xiàn)在， make 回到myprog的規(guī)則。如果剛才兩個(gè)規(guī)則中的任 何一個(gè)被執(zhí)行，myprog 就需要重建（因?yàn)槠渲幸粋€(gè) .o 檔就會(huì)比

34、myprog新），因此連接命令將被執(zhí)行。3.2 編寫(xiě) make 規(guī)則 (Rules)最簡(jiǎn)單的編寫(xiě)規(guī)則的方法是一個(gè)一個(gè)的查 看源碼文件，把它們的目標(biāo)文件做為目的，而源碼文件和被它 #include 的 header 檔做為依靠文件。但是你也要把其它被這些 header 檔 #include 的 header 檔也列為依靠文件，還有那些被 包括的文件所包括的文件然后你會(huì)發(fā)現(xiàn)要對(duì)越來(lái)越多的文件 進(jìn)行管理，然后你的頭發(fā)開(kāi)始脫落，你的脾氣開(kāi)始變壞，你的臉 色變成菜色，你走在路上開(kāi)始跟電線桿子碰撞，終于你搗毀你的 電腦顯示器，停止編程。到低有沒(méi)有些容易點(diǎn)兒的方法呢？ 當(dāng)然有！向編譯器要！在編譯每一個(gè)源碼文

35、件的時(shí)候，它實(shí)在應(yīng) 該知道應(yīng)該包括什么樣的 header 檔。使用 gcc 的時(shí)候，用 -M 開(kāi)關(guān)，它會(huì)為每一個(gè)你給它的文件輸出一個(gè)規(guī)則，把目標(biāo)文件 做為目的，而這個(gè)文件和所有應(yīng)該被 #include 的 header 文 件將做為依靠文件。注意這個(gè)規(guī)則會(huì)加入所有 header 文件，包 括被角括號(hào)(<', >')和雙引號(hào)("')所包圍的文件。其實(shí)我們可以 相當(dāng)肯定系統(tǒng) header 檔（比如 stdio.h, stdlib.h 等等）不會(huì) 被我們更改，如果你用 -MM 來(lái)代替 -M 傳遞給 gcc，那些用角括 號(hào)包圍的 header 檔將不會(huì)被包

36、括。（這會(huì)節(jié)省一些編譯時(shí)間） 由 gcc 輸出的規(guī)則不會(huì)含有命令部分；你可以自己寫(xiě)入你的命令 或者什么也不寫(xiě)，而讓 make 使用它的隱含的規(guī)則。3.3 Makefile 變量上面提到 makefiles 里主要包含一些規(guī)則。它們包含的其它的東西是變量定義。makefile 里的變量就像一個(gè)環(huán)境變量(environment variable)。 事實(shí)上，環(huán)境變量在 make 過(guò)程中被解釋成 make 的變量。這些 變量是大小寫(xiě)敏感的，一般使用大寫(xiě)字母。它們可以從幾乎任何 地方被引用，也可以被用來(lái)做很多事情，比如： i) 貯存一個(gè)文件名列表。在上面的例子里，生成可執(zhí)行文件的 規(guī)則包含一些目標(biāo)文件

37、名做為依靠。在這個(gè)規(guī)則的命令行 里同樣的那些文件被輸送給 gcc 做為命令參數(shù)。如果在這 里使用一個(gè)變數(shù)來(lái)貯存所有的目標(biāo)文件名，加入新的目標(biāo) 文件會(huì)變的簡(jiǎn)單而且較不易出錯(cuò)。 ii) 貯存可執(zhí)行文件名。如果你的項(xiàng)目被用在一個(gè)非 gcc 的系 統(tǒng)里，或者如果你想使用一個(gè)不同的編譯器，你必須將所 有使用編譯器的地方改成用新的編譯器名。但是如果使用一 個(gè)變量來(lái)代替編譯器名，那么你只需要改變一個(gè)地方，其 它所有地方的命令名就都改變了。 iii) 貯存編譯器旗標(biāo)。假設(shè)你想給你所有的編譯命令傳遞一組 相同的選項(xiàng)（例如 -Wall -O -g）；如果你把這組選項(xiàng)存 入一個(gè)變量，那么你可以把這個(gè)變量放在所有呼叫

38、編譯器 的地方。而當(dāng)你要改變選項(xiàng)的時(shí)候，你只需在一個(gè)地方改 變這個(gè)變量的內(nèi)容。要設(shè)定一個(gè)變量，你只要在一行的開(kāi)始寫(xiě)下這個(gè)變量的名字，后 面跟一個(gè) = 號(hào)，后面跟你要設(shè)定的這個(gè)變量的值。以后你要引用 這個(gè)變量，寫(xiě)一個(gè) $ 符號(hào)，后面是圍在括號(hào)里的變量名。比如在 下面，我們把前面的 makefile 利用變量重寫(xiě)一遍：-OBJS = foo.o bar.oCC = gccCFLAGS = -Wall -O -gmyprog : $(OBJS) $(CC) $(OBJS) -o myprogfoo.o : foo.c foo.h bar.h $(CC) $(CFLAGS) -c foo.c -o f

39、oo.obar.o : bar.c bar.h $(CC) $(CFLAGS) -c bar.c -o bar.o-還有一些設(shè)定好的內(nèi)部變量，它們根據(jù)每一個(gè)規(guī)則內(nèi)容定義。三個(gè) 比較有用的變量是 $, $< 和 $ （這些變量不需要括號(hào)括?。?。 $ 擴(kuò)展成當(dāng)前規(guī)則的目的文件名， $< 擴(kuò)展成依靠列表中的第 一個(gè)依靠文件，而 $ 擴(kuò)展成整個(gè)依靠的列表（除掉了里面所有重 復(fù)的文件名）。利用這些變量，我們可以把上面的 makefile 寫(xiě)成：-OBJS = foo.o bar.oCC = gccCFLAGS = -Wall -O -gmyprog : $(OBJS) $(CC) $ -o

40、$foo.o : foo.c foo.h bar.h $(CC) $(CFLAGS) -c $< -o $bar.o : bar.c bar.h $(CC) $(CFLAGS) -c $< -o $-你可以用變量做許多其它的事情，特別是當(dāng)你把它們和函數(shù)混合 使用的時(shí)候。如果需要更進(jìn)一步的了解，請(qǐng)參考 GNU Make 手冊(cè)。另外，配合使用pkg-config，你可以在把代碼所用的頭文件和庫(kù)函數(shù)位置放在變量里。比如，在編寫(xiě)GTK+程序時(shí)，可以這樣設(shè)置一個(gè)變量：GTK_FLAGS=$(shell pkg-config -libs -cflags "gtk+-2.0"

41、) 然后在規(guī)則里使用它：gcc main.c -o simple $(GTK_FLAGS)3.4 隱含規(guī)則 (Implicit Rules)請(qǐng)注意，在上面的例子里，幾個(gè)產(chǎn)生 .o 文件的命令都是一樣的。 都是從 .c 文件和相關(guān)文件里產(chǎn)生 .o 文件，這是一個(gè)標(biāo)準(zhǔn)的步 驟。其實(shí) make 已經(jīng)知道怎么做它有一些叫做隱含規(guī)則的內(nèi) 置的規(guī)則，這些規(guī)則告訴它當(dāng)你沒(méi)有給出某些命令的時(shí)候，應(yīng)該 怎么辦。 如果你把生成 foo.o 和 bar.o 的命令從它們的規(guī)則中刪除， make 將會(huì)查找它的隱含規(guī)則，然后會(huì)找到一個(gè)適當(dāng)?shù)拿?。它的命令?huì) 使用一些變量，因此你可以按照你的想法來(lái)設(shè)定它：它使用變量 CC 做為編譯器（象我們?cè)谇懊娴睦樱?，并且傳遞變量 CFLAGS （給 C 編譯器，C+ 編譯器用 CXXFLAGS ），CPPFLAGS （ C 預(yù) 處理器旗標(biāo)）， TARGET_ARCH （現(xiàn)在不用考慮這個(gè)），