數(shù)據(jù)結(jié)構(gòu)習(xí)題解析及實(shí)訓(xùn)第一章

1、第1章 緒論本書(shū)對(duì)應(yīng)數(shù)據(jù)結(jié)構(gòu)教材上的章節(jié),給出每一章的習(xí)題分析及程序解答。習(xí)題中所有的程序都用C語(yǔ)言編寫(xiě)并上機(jī)調(diào)試通過(guò),并在本書(shū)所配的光盤(pán)中提供了程序的源文件?？紤]到函數(shù)調(diào)用的共享性,有的章節(jié)中還給出一些匯總性的習(xí)題及其解答和源程序。每一章的習(xí)題程序放在光盤(pán)同名目錄下。所有習(xí)題用到的數(shù)據(jù)結(jié)構(gòu)類型說(shuō)明定義都放在頭文件“datastru.h”中,頭文件“datastru.h”在光盤(pán)根目錄下。程序中的輸入、輸出和注釋均以中文描述和表達(dá)。程序可以在Windows98操作系統(tǒng)(或DOS操作系統(tǒng))、TurboC軟件環(huán)境下編譯運(yùn)行,也可以在Windows98操作系統(tǒng)、VisualC+60軟件環(huán)境下編譯運(yùn)行,

2、因?yàn)槌绦虻脑创a用的全是VisualC+中的語(yǔ)句,所以源程序不作任何修改就可以在VisualC+下編譯運(yùn)行。本書(shū)中有幾個(gè)程序和教材上應(yīng)用舉例中的程序相同,這是為了方便手中無(wú)教科書(shū)的讀者可從本書(shū)中學(xué)到比較多的數(shù)據(jù)結(jié)構(gòu)應(yīng)用程序。下面介紹在3種不同的運(yùn)行環(huán)境下編譯運(yùn)行C語(yǔ)言源程序的過(guò)程,供上機(jī)練習(xí)時(shí)參考。1.1Windows98操作系統(tǒng)、VisualC+6.0軟件環(huán)境下編譯運(yùn)行VisualC+6.0是Microsoft公司推出的、目前使用非常廣泛的可視化編程環(huán)境,為使用者提供了強(qiáng)大的開(kāi)發(fā)能力。本書(shū)中的每一個(gè)程序的源代碼用的全是VisualC+中的C語(yǔ)言語(yǔ)句,所以可以不作任何修改就可在VisualC+

3、下編譯運(yùn)行。只要使用中文版的Windows98操作系統(tǒng),程序就可在中文版或英文版VisualC+6.0環(huán)境下編譯運(yùn)行。在運(yùn)行程序前,應(yīng)先安裝MicrosoftVisualC+6.0的開(kāi)發(fā)環(huán)境。在運(yùn)行每個(gè)程序時(shí),請(qǐng)先閱讀這個(gè)程序的題目要求、結(jié)構(gòu)說(shuō)明及有關(guān)的分析和解釋。下面以第6章的“二叉樹(shù)中序遍歷”習(xí)題為示例,說(shuō)明運(yùn)行程序的操作步驟。(1)在硬盤(pán)上建立一個(gè)C+程序運(yùn)行的目錄,如“c:temp數(shù)據(jù)結(jié)構(gòu)”。(2)把附帶光盤(pán)“二叉樹(shù)”子目錄下的“二叉樹(shù)中序遍歷.c”源程序及有關(guān)文件包括l2數(shù)據(jù)結(jié)構(gòu)習(xí)題解析與實(shí)訓(xùn)“二叉樹(shù).c”源程序、根目錄下的“datastru.h”頭文件復(fù)制到上面建立的“c:temp

4、數(shù)據(jù)結(jié)構(gòu)”目錄之下。(3)進(jìn)入MicrosoftVisualC+6.0開(kāi)發(fā)環(huán)境,如圖11所示。這是對(duì)應(yīng)運(yùn)行每一個(gè)數(shù)據(jù)結(jié)構(gòu)習(xí)題最基本的VisualC+6.0開(kāi)發(fā)環(huán)境界面。屏幕的最上端是標(biāo)題欄,標(biāo)題欄用于顯示應(yīng)用程序名和所打開(kāi)的文件名。標(biāo)題欄下面是菜單欄和工具欄。工具欄左下方是工作區(qū)窗口,右下方是編輯窗口,因?yàn)閿?shù)據(jù)結(jié)構(gòu)的習(xí)題是用C語(yǔ)言編寫(xiě)的,所以工具欄下方的工作區(qū)窗口沒(méi)有用到,可將其關(guān)閉。最下方是狀態(tài)欄。狀態(tài)欄上面是輸出窗口,用于顯示程序編譯、連接、運(yùn)行過(guò)程中的有關(guān)信息。圖1.1VisualC+6.0(中文版)開(kāi)發(fā)環(huán)境界面(4)打開(kāi)源程序:選擇“文件”(File)“打開(kāi)”(Open),選擇“c:t

5、emp數(shù)據(jù)結(jié)構(gòu)”目錄下的“二叉樹(shù)中序遍歷.c”文件。在編輯窗口即可觀察到這個(gè)文件的源代碼,如圖12所示。(5)對(duì)源程序進(jìn)行編譯操作:選擇“編譯”(Build)“編譯二叉樹(shù)中序遍歷.c”(Compile)執(zhí)行編譯。編譯過(guò)程中出現(xiàn)的錯(cuò)誤會(huì)顯示在下面的輸出窗口,根據(jù)錯(cuò)誤信息提示,修改程序錯(cuò)誤,直至錯(cuò)誤和警告信息為0,如圖13所示。(6)程序運(yùn)行:選擇“編譯”“執(zhí)行二叉樹(shù)中序遍歷.exe”(Execute)執(zhí)行連接和運(yùn)行操作。當(dāng)程序運(yùn)行時(shí),將會(huì)彈出一個(gè)窗口,運(yùn)行程序,顯示信息,或等待用戶的輸入數(shù)據(jù)。程序運(yùn)行的結(jié)果也顯現(xiàn)在同一窗口內(nèi),如圖14所示。第1章緒論l3圖1.2打開(kāi)源程序圖1.3對(duì)源程序進(jìn)行編譯

6、操作l4數(shù)據(jù)結(jié)構(gòu)習(xí)題解析與實(shí)訓(xùn)圖1.4程序運(yùn)行顯示(7)本習(xí)題集中全部程序均在Windows98操作系統(tǒng)、MicrosoftVisualC+6.0軟件環(huán)境下調(diào)試通過(guò)。(8)有關(guān)MicrosoftVisualC+6.0軟件本身的內(nèi)容,請(qǐng)讀者參考相關(guān)的書(shū)籍。(9)最后需要說(shuō)明的一點(diǎn)是:程序主要是在功能和邏輯上實(shí)現(xiàn)了題目的要求,而沒(méi)有對(duì)輸入數(shù)據(jù)的合法性進(jìn)行嚴(yán)格的判斷和校驗(yàn),輸入數(shù)據(jù)的合法性由用戶保證。因而如果發(fā)生用戶輸入數(shù)據(jù)不當(dāng)時(shí),程序可能會(huì)呈現(xiàn)出錯(cuò)的異常情況,遇到這種情況發(fā)生,只需重新運(yùn)行源程序即可。1.2Windows操作系統(tǒng)、TurboC軟件環(huán)境下編譯運(yùn)行在運(yùn)行程序前,應(yīng)安裝TurboC軟件。

7、有關(guān)TurboC軟件本身的內(nèi)容,請(qǐng)讀者參考相關(guān)的書(shū)籍。在運(yùn)行每個(gè)程序時(shí),請(qǐng)先閱讀這個(gè)程序的題目要求、結(jié)構(gòu)說(shuō)明及有關(guān)的分析和解釋。下面以第2章的“順序表并集運(yùn)算”題目為示例,說(shuō)明程序運(yùn)行的操作步驟。(1)在硬盤(pán)上建立一個(gè)TurboC程序運(yùn)行的目錄如“c:tempsjjg”。(2)把附帶光盤(pán)“線性表”子目錄下的“順序表并集.c”源程序及根目錄下的“datastru.h”頭文件復(fù)制到“c:tempsjjg”所在的目錄之下。(3)進(jìn)入MicrosoftTurboC開(kāi)發(fā)環(huán)境,如圖15所示。在這個(gè)開(kāi)發(fā)環(huán)境下,程序中的中文輸入和中文輸出以及源程序中的中文注釋均可正常顯示。(4)打開(kāi)源程序:選擇FileLod

8、e打開(kāi)“c:tempsjjg順序表并集.c”文件。在編輯第1章緒論l5圖1.5Windows操作系統(tǒng)、MicrosoftTurboC開(kāi)發(fā)環(huán)境圖1.6打開(kāi)源程序窗口即可觀察到這個(gè)文件的源代碼,如圖16所示。(5)對(duì)源程序進(jìn)行編譯操作:選擇CompileCompiletoOBJ執(zhí)行編譯。編譯中出現(xiàn)的錯(cuò)誤會(huì)顯示在下方Message窗口中,當(dāng)編譯通過(guò),TC窗口顯示如圖17所示。(6)編譯通過(guò)后選擇RunRun執(zhí)行連接和運(yùn)行操作。當(dāng)程序運(yùn)行時(shí),將會(huì)彈出一l6數(shù)據(jù)結(jié)構(gòu)習(xí)題解析與實(shí)訓(xùn)圖1.7程序進(jìn)行編譯操作圖1.8TC程序運(yùn)行窗口顯示個(gè)窗口,運(yùn)行程序,顯示信息,或等待用戶的輸入數(shù)據(jù)。程序運(yùn)行的結(jié)果數(shù)據(jù)顯示在

9、另一窗口內(nèi),如圖18所示。(7)本習(xí)題集中全部程序均在Windows98操作系統(tǒng)、TurboC軟件環(huán)境下調(diào)試通過(guò)。要注意的是,在Windows98操作系統(tǒng)、TurboC軟件環(huán)境下編譯運(yùn)行時(shí),程序中包第1章緒論l7含的頭文件均應(yīng)改為;包含的“二叉樹(shù).c”文件須改為包含完整路徑的英文文件名方可。1.3DOS操作系統(tǒng)、TurboC軟件環(huán)境下編譯運(yùn)行程序如果在DOS操作系統(tǒng)、TurboC軟件環(huán)境下編譯運(yùn)行,則程序的中文名、程序的中文輸入、輸出及中文注釋的正確顯示都依賴于DOS操作系統(tǒng)的漢化,DOS操作系統(tǒng)的漢化工作由用戶處理?；谝陨?種環(huán)境下編譯運(yùn)行的介紹,建議使用第一種即在Windows98操作系

10、統(tǒng)、VisualC+6.0軟件環(huán)境下編譯運(yùn)行各源程序。1.4習(xí)題解析【習(xí)題1】分析下面語(yǔ)句段執(zhí)行的時(shí)間復(fù)雜度。(1)for(i=1;i=n;i+)for(j=1;j=n;j+)s+;【解答】雙重for循環(huán)語(yǔ)句,其中外循環(huán)n次,對(duì)每一次外循環(huán),內(nèi)循環(huán)s+;語(yǔ)句執(zhí)行n次?？偟膕+;語(yǔ)句共執(zhí)行n2次,時(shí)間復(fù)雜度為O(n2)。(2)for(i=1;i=n;i+)for(j=i;j=n;j+)s+;【解答】雙重for循環(huán)語(yǔ)句,其中外循環(huán)n次,對(duì)每一次外循環(huán),內(nèi)循環(huán)s+;語(yǔ)句執(zhí)行次數(shù)都在變化。第一次外循環(huán)時(shí),內(nèi)循環(huán)s+;語(yǔ)句執(zhí)行次數(shù)為n次;第二次外循環(huán)時(shí),內(nèi)循環(huán)s+;語(yǔ)句執(zhí)行次數(shù)為n-1次;第三次外循環(huán)時(shí)

11、,內(nèi)循環(huán)s+;語(yǔ)句執(zhí)行次數(shù)為n-2次;第n次外循環(huán)時(shí),內(nèi)循環(huán)s+;語(yǔ)句執(zhí)行次數(shù)為1次;總的s+;語(yǔ)句共執(zhí)行n+(n-1)+(n-2)+2+1=n(n+1)2次,時(shí)間復(fù)雜度為O(n2)。l8數(shù)據(jù)結(jié)構(gòu)習(xí)題解析與實(shí)訓(xùn)(3)for(i=1;i=n;i+)for(j=1;j=i;j+)s+;【解答】雙重for循環(huán)語(yǔ)句,其中外循環(huán)n次,對(duì)每一次外循環(huán),內(nèi)循環(huán)s+;語(yǔ)句執(zhí)行次數(shù)都在變化。第一次外循環(huán)時(shí),內(nèi)循環(huán)s+;語(yǔ)句執(zhí)行次數(shù)為1次;第二次外循環(huán)時(shí),內(nèi)循環(huán)s+;語(yǔ)句執(zhí)行次數(shù)為2次;第三次外循環(huán)時(shí),內(nèi)循環(huán)s+;語(yǔ)句執(zhí)行次數(shù)為3次;第n次外循環(huán)時(shí),內(nèi)循環(huán)s+;語(yǔ)句執(zhí)行次數(shù)為n次;總的s+;語(yǔ)句共執(zhí)行1+2+3+

12、(n-2)+(n-1)+n=n(n+1)2次,時(shí)間復(fù)雜度為O(n2)。(4)i=1;k=0;while(i=n-1)k+=10i;i+;【解答】i=1;語(yǔ)句執(zhí)行1次;k=0;語(yǔ)句執(zhí)行1次;while循環(huán)語(yǔ)句在(i=n-1)條件滿足時(shí),執(zhí)行k+=10i;和i+;兩條語(yǔ)句。當(dāng)n=1時(shí);while循環(huán)條件(i=n-1)不滿足,k+=10i;和i+;兩條語(yǔ)句不執(zhí)行。當(dāng)n=2時(shí);while循環(huán)條件(i=n-1)滿足一次,k+=10i;和i+;兩條語(yǔ)句執(zhí)行一次。當(dāng)n=3時(shí);while循環(huán)條件(i=n-1)滿足二次,k+=10i;和i+;兩條語(yǔ)句執(zhí)行二次。以此類推,總的語(yǔ)句執(zhí)行次數(shù)為1+1+2(n-1)次,時(shí)間復(fù)雜度為O(n)?！玖?xí)題2】試畫(huà)出與下列程序段等價(jià)的框圖。(1)p=1;i=1;while(i=n)p=i;i+;第1章緒論l9【解答】(2)i=0;doi+