1、第1章 緒論本書對應數據結構教材上的章節,給出每一章的習題分析及程序解答。習題中所有的程序都用c語言編寫并上機調試通過,并在本書所配的光盤中提供了程序的源文件。考慮到函數調用的共享性,有的章節中還給出一些匯總性的習題及其解答和源程序。每一章的習題程序放在光盤同名目錄下。所有習題用到的數據結構類型說明定義都放在頭文件“datastru.h”中,頭文件“datastru.h”在光盤根目錄下。程序中的輸入、輸出和注釋均以中文描述和表達。程序可以在windows98操作系統(或dos操作系統)、turboc軟件環境下編譯運行,也可以在windows98操作系統、visualc+60軟件環境下編譯運行,

2、因為程序的源代碼用的全是visualc+中的語句,所以源程序不作任何修改就可以在visualc+下編譯運行。本書中有幾個程序和教材上應用舉例中的程序相同,這是為了方便手中無教科書的讀者可從本書中學到比較多的數據結構應用程序。下面介紹在3種不同的運行環境下編譯運行c語言源程序的過程,供上機練習時參考。1.1windows98操作系統、visualc+6.0軟件環境下編譯運行visualc+6.0是microsoft公司推出的、目前使用非常廣泛的可視化編程環境,為使用者提供了強大的開發能力。本書中的每一個程序的源代碼用的全是visualc+中的c語言語句,所以可以不作任何修改就可在visualc+

3、下編譯運行。只要使用中文版的windows98操作系統,程序就可在中文版或英文版visualc+6.0環境下編譯運行。在運行程序前,應先安裝microsoftvisualc+6.0的開發環境。在運行每個程序時,請先閱讀這個程序的題目要求、結構說明及有關的分析和解釋。下面以第6章的“二叉樹中序遍歷”習題為示例,說明運行程序的操作步驟。(1)在硬盤上建立一個c+程序運行的目錄,如“c:temp數據結構”。(2)把附帶光盤“二叉樹”子目錄下的“二叉樹中序遍歷.c”源程序及有關文件包括l2數據結構習題解析與實訓“二叉樹.c”源程序、根目錄下的“datastru.h”頭文件復制到上面建立的“c:temp

4、數據結構”目錄之下。(3)進入microsoftvisualc+6.0開發環境,如圖11所示。這是對應運行每一個數據結構習題最基本的visualc+6.0開發環境界面。屏幕的最上端是標題欄,標題欄用于顯示應用程序名和所打開的文件名。標題欄下面是菜單欄和工具欄。工具欄左下方是工作區窗口,右下方是編輯窗口,因為數據結構的習題是用c語言編寫的,所以工具欄下方的工作區窗口沒有用到,可將其關閉。最下方是狀態欄。狀態欄上面是輸出窗口,用于顯示程序編譯、連接、運行過程中的有關信息。圖1.1visualc+6.0(中文版)開發環境界面(4)打開源程序:選擇“文件”(file)“打開”(open),選擇“c:t

5、emp數據結構”目錄下的“二叉樹中序遍歷.c”文件。在編輯窗口即可觀察到這個文件的源代碼,如圖12所示。(5)對源程序進行編譯操作:選擇“編譯”(build)“編譯二叉樹中序遍歷.c”(compile)執行編譯。編譯過程中出現的錯誤會顯示在下面的輸出窗口,根據錯誤信息提示,修改程序錯誤,直至錯誤和警告信息為0,如圖13所示。(6)程序運行:選擇“編譯”“執行二叉樹中序遍歷.exe”(execute)執行連接和運行操作。當程序運行時,將會彈出一個窗口,運行程序,顯示信息,或等待用戶的輸入數據。程序運行的結果也顯現在同一窗口內,如圖14所示。第1章緒論l3圖1.2打開源程序圖1.3對源程序進行編譯

6、操作l4數據結構習題解析與實訓圖1.4程序運行顯示(7)本習題集中全部程序均在windows98操作系統、microsoftvisualc+6.0軟件環境下調試通過。(8)有關microsoftvisualc+6.0軟件本身的內容,請讀者參考相關的書籍。(9)最后需要說明的一點是:程序主要是在功能和邏輯上實現了題目的要求,而沒有對輸入數據的合法性進行嚴格的判斷和校驗,輸入數據的合法性由用戶保證。因而如果發生用戶輸入數據不當時,程序可能會呈現出錯的異常情況,遇到這種情況發生,只需重新運行源程序即可。1.2windows操作系統、turboc軟件環境下編譯運行在運行程序前,應安裝turboc軟件。

7、有關turboc軟件本身的內容,請讀者參考相關的書籍。在運行每個程序時,請先閱讀這個程序的題目要求、結構說明及有關的分析和解釋。下面以第2章的“順序表并集運算”題目為示例,說明程序運行的操作步驟。(1)在硬盤上建立一個turboc程序運行的目錄如“c:tempsjjg”。(2)把附帶光盤“線性表”子目錄下的“順序表并集.c”源程序及根目錄下的“datastru.h”頭文件復制到“c:tempsjjg”所在的目錄之下。(3)進入microsoftturboc開發環境,如圖15所示。在這個開發環境下,程序中的中文輸入和中文輸出以及源程序中的中文注釋均可正常顯示。(4)打開源程序:選擇filelod

8、e打開“c:tempsjjg順序表并集.c”文件。在編輯第1章緒論l5圖1.5windows操作系統、microsoftturboc開發環境圖1.6打開源程序窗口即可觀察到這個文件的源代碼,如圖16所示。(5)對源程序進行編譯操作:選擇compilecompiletoobj執行編譯。編譯中出現的錯誤會顯示在下方message窗口中,當編譯通過,tc窗口顯示如圖17所示。(6)編譯通過后選擇runrun執行連接和運行操作。當程序運行時,將會彈出一l6數據結構習題解析與實訓圖1.7程序進行編譯操作圖1.8tc程序運行窗口顯示個窗口,運行程序,顯示信息,或等待用戶的輸入數據。程序運行的結果數據顯示在

9、另一窗口內,如圖18所示。(7)本習題集中全部程序均在windows98操作系統、turboc軟件環境下調試通過。要注意的是,在windows98操作系統、turboc軟件環境下編譯運行時,程序中包第1章緒論l7含的頭文件<malloc.h>均應改為<alloc.h>包含的“二叉樹.c”文件須改為包含完整路徑的英文文件名方可。1.3dos操作系統、turboc軟件環境下編譯運行程序如果在dos操作系統、turboc軟件環境下編譯運行,則程序的中文名、程序的中文輸入、輸出及中文注釋的正確顯示都依賴于dos操作系統的漢化,dos操作系統的漢化工作由用戶處理。基于以上3種環境

10、下編譯運行的介紹,建議使用第一種即在windows98操作系統、visualc+6.0軟件環境下編譯運行各源程序。1.4習題解析【習題1】分析下面語句段執行的時間復雜度。(1)for(i=1;i<=n;i+)for(j=1;j<=n;j+)s+;【解答】雙重for循環語句,其中外循環n次,對每一次外循環,內循環s+;語句執行n次。總的s+;語句共執行n2次,時間復雜度為o(n2)。(2)for(i=1;i<=n;i+)for(j=i;j<=n;j+)s+;【解答】雙重for循環語句,其中外循環n次,對每一次外循環,內循環s+;語句執行次數都在變化。第一次外循環時,內循環

11、s+;語句執行次數為n次;第二次外循環時,內循環s+;語句執行次數為n-1次;第三次外循環時,內循環s+;語句執行次數為n-2次;第n次外循環時,內循環s+;語句執行次數為1次;總的s+;語句共執行n+(n-1)+(n-2)+2+1=n(n+1)2次,時間復雜度為o(n2)。l8數據結構習題解析與實訓(3)for(i=1;i<=n;i+)for(j=1;j<=i;j+)s+;【解答】雙重for循環語句,其中外循環n次,對每一次外循環,內循環s+;語句執行次數都在變化。第一次外循環時,內循環s+;語句執行次數為1次;第二次外循環時,內循環s+;語句執行次數為2次;第三次外循環時,內循

12、環s+;語句執行次數為3次;第n次外循環時,內循環s+;語句執行次數為n次;總的s+;語句共執行1+2+3+(n-2)+(n-1)+n=n(n+1)2次,時間復雜度為o(n2)。(4)i=1;k=0;while(i<=n-1)k+=10i;i+;【解答】i=1;語句執行1次;k=0;語句執行1次;while循環語句在(i<=n-1)條件滿足時,執行k+=10i;和i+;兩條語句。當n=1時;while循環條件(i<=n-1)不滿足,k+=10i;和i+;兩條語句不執行。當n=2時;while循環條件(i<=n-1)滿足一次,k+=10i;和i+;兩條語句執行一次。當n=3時;while循環條件(i<=n-1)滿足二次,k+=10i;和i+;兩條語句執行二次。以此類推,總的語句執行次數為1+1+2(n-1)次,時間復雜度為o(n)。【習題2】試畫出與下列程序段等價的框圖。(1)p=1;i=1;while(i<=n)p=i;i+;第1章緒論l9【解答】(2)i=0;doi+;while(i!=n)&