1.1 問題求解與程序設計

用計算機求解任何問題都離不開程序設計，只有最終在計算機上能夠運行良好的程序才能解決特定的實際問題，因此，程序設計的過程就是利用計算機求解問題的過程。

1.1.1 程序設計的一般過程

用計算機求解任何問題都離不開程序設計，但是計算機不能分析問題并產生問題的解決方案，必須由人（即程序設計者）分析問題，確定問題的解決方案，采用計算機能夠理解的指令描述這個問題的求解步驟（即編寫程序），然后讓計算機執行程序最終獲得問題的解。程序設計的一般過程如圖1-1所示。

由問題到想法需要分析問題，抽象出具體的數據模型（待處理的數據以及數據之間的關系，也稱數據結構），形成問題求解的基本思路。對于待求解的問題，首先搞清楚求解的目標是什么，給出了哪些已知信息、顯式條件或隱含條件，應該用什么形式的數據表達計算結果。如果沒有全面、準確和認真地分析問題，就急急忙忙地編寫程序，結果往往是事倍功半，造成不必要的反復，甚至給程序留下嚴重隱患。

算法用來描述問題的解決方案，是具體的、機械的操作步驟。利用計算機解決問題的最重要一步是將人的想法描述成算法，即設計算法，也就是從計算機的角度設想計算機是如何一步一步完成這個任務的。有些問題很簡單，很容易就可以得到問題的解決方案；如果問題比較復雜，就需要更多的思考才能得到問題的解決方案。由想法到算法需要完成數據表示和數據處理，即描述問題的數據模型（將數據從機外表示轉換為機內表示），描述問題求解的基本思路（將問題的解決方案形成算法）。數據結構課程主要討論非數值問題的數據表示和數據處理。

由算法到程序需要將算法的操作步驟轉換為某種程序設計語言對應的語句，轉換所依據的規則就是某種程序設計語言的語法，換言之，就是在某種編程環境下用程序設計語言描述要處理的數據以及數據處理的過程。

著名的計算機學者沃思給出了一個公式：數據結構+算法=程序。從這個公式可以看到，數據結構和算法是構成程序的兩個重要的組成部分，一個“好”程序首先是將問題抽象出一個適當的數據結構，然后基于該數據結構設計一個“好”算法。下面以著名的哥尼斯堡七橋問題為例，說明程序設計的一般過程。

【問題】 哥尼斯堡七橋問題（以下簡稱七橋問題）。17世紀的東普魯士有一座哥尼斯堡城（現在叫加里寧格勒，在波羅的海南岸），城中有一座島，普雷格爾河的兩條支流環繞其旁，并將整個城市分成北區、東區、南區和島區4個區域，全城共有七座橋將4個城區連接起來，如圖1-2（a）所示。于是，產生了一個有趣的問題：一個人是否能在一次步行中經過全部的七座橋后再回到起點，且每座橋只經過一次。

【想法】 將城區抽象為頂點，用A、B、C、D表示4個城區，將橋抽象為邊，用7條邊表示七座橋，抽象出七橋問題的數據模型如圖1-2（b）所示，從而將七橋問題抽象為一個數學問題：求經過圖中每條邊一次且僅一次的回路，后來人們稱之為歐拉回路。歐拉回路的判定規則是：

（1）如果通奇數個橋的城區多于兩個，則不存在歐拉回路；

（2）如果只有兩個城區通奇數個橋，則可以從這兩個城區之一出發找到歐拉回路；

（3）如果沒有一個城區通奇數個橋，則無論從哪里出發都能找到歐拉回路。

由上述判定規則得到求解七橋問題的基本思路：依次計算與每個頂點相關聯的邊的個數（稱為頂點的度），根據度為奇數的頂點個數判定是否存在歐拉回路。

【算法】 進一步地，將頂點A、B、C、D編號為0、1、2、3，用二維數組mat[4][4]存儲七橋問題的數據模型，如果頂點i（0≤i≤3）和頂點j（0≤i≤3）之間有k條邊，則元素mat[i][j]的值為k，如圖1-2（c）所示。求解七橋問題的關鍵是求與每個頂點相關聯的邊數，即在二維數組mat[4][4]中求每一行元素之和，算法描述如下：

【程序】 主函數首先初始化二維數組mat[4][4]，即建立七橋問題對應的數據模型，然后調用函數EulerCircuit計算圖模型中通奇數個橋的頂點個數，再根據歐拉規則判定是否存在歐拉回路。程序如下：

            #include＜stdio.h＞                              //使用庫函數printf和scanf
            intEulerCircuit（intmat[10][10]，intn）；        //函數聲明

                                                             //空行，以下是主函數
            intmain（）
            {
                  intmat[10][10]={{0，1，2，2}，{1，0，1，1}，{2，1，0，0}，{2，1，0，0}}；
                  intnum=EulerCircuit（mat，4）；            //調用函數得到通奇數個橋的頂點個數
                  if（num＞2）                               //多于兩個頂點通奇數個橋
                    printf（＂有%d個地方通奇數個橋，不存在歐拉回路\n＂，num）；
                  elseif（num==2||num==0）                   //兩個頂點通奇數個橋或沒有頂點通奇數個橋
                      printf（＂存在歐拉回路\n＂）；
                  return0；                                  //將0返回操作系統，表明程序正常結束
            }
                                                             //空行，以下是其他函數定義
            intEulerCircuit（intmat[10][10]，intn）          //函數定義，二維數組作為形參
            {
                  inti，j，degree，count=0；                 //count累計通奇數個橋的頂點個數
                  for（i=0；i＜n；i++）                      //依次累加每一行的元素
                  {
                    degree=0；                               //degree存儲通過頂點i的橋數，初始化為0
                    for（j=0；j＜n；j++）                    //依次處理每一列的元素
                    {
                      degree=degree+mat[i][j]；              //將通過頂點i的橋數求和
                    }
                    if（degree% 2！=0）                      //橋數為奇數
                      count++；
                  }
                  returncount；                              //結束函數，并將count返回到調用處
            }

1.1.2 數據結構在程序設計中的作用

有些問題難以求解的原因是無從下手，如果能將問題抽象出一個合適的數據模型，則問題可能會變得豁然開朗。下面這個著名的握手問題是愛丁堡大學的PeterRoss提出來的。

【例1-1】 握手問題。Smith先生和太太邀請4對夫妻來參加晚宴。每個人來的時候，房間里的一些人都要和其他人握手。當然，每個人都不會和自己的配偶握手，也不會跟同一個人握手兩次。之后，Smith先生問每個人和別人握了幾次手，他們的答案都不一樣。問題是，Smith太太和別人握了幾次手？

解：這個問題具有挑戰性的原因是因為它沒有一個明顯的起始點，但如果將此問題抽象出一個合適的數據模型，如圖1-3（a）所示，問題就變得簡單了。

讓我們來收集一下已知條件。Smith先生問了房間中的9個人，每個人的答案都不相同，因此，每個答案都在0和8之間，相應地修改模型如圖1-3（b）所示。

讓我們來列出所有的握手信息。例如，8號除了他（她）自己和配偶，與房間里的其他人總共握了8次手?；谶@個觀察，我們可以畫出8號的握手信息并且知道8號的配偶是0號；7號除了0號和1號，與房間里的其他人總共握了7次手，因此7號的配偶是1號；……問題是否變得豁然開朗了？

一個“好”程序首先是將問題抽象出一個適當的數據模型，基于不同數據模型的算法，其運行效率可能會有很大差別。舉例如下。

【例1-2】 手機電話號碼查詢問題。假設某手機中存儲了如表1-1所示的若干電話號碼，如何在手機中查找某人的電話號碼？

解：如果將電話號碼集合線性排列，則某個人的電話號碼只能進行順序查找。

如果將電話號碼集合進行分組，如圖1-4所示，則查找某個人的電話號碼可以只在某個分組中進行。顯然，后者的查找效率更高，當數據量較大時差別就更大。

1.1.3 算法在程序設計中的作用

算法是問題的解決方案，這個解決方案本身并不是問題的答案，而是能獲得答案的指令序列。對于許多實際的問題，寫出一個正確的算法還不夠，如果這個算法在規模較大的數據集上運行，那么運行效率就成為一個重要的問題。在選擇和設計算法時要有效率的觀念，這一點比提高計算機本身的速度更為重要。

【例1-3】 數組循環左移問題。將一個具有n個元素的數組向左循環移動i個位置。有許多應用程序會調用這個問題的算法，例如在文本編輯器中移動行的操作，磁盤整理時交換兩個不同大小的相鄰內存塊等。所以，解決這個問題的算法要求有較高的時間性能和空間性能。

解法1：先將數組中的前i個元素存放在一個臨時數組中，再將余下的n-i個元素左移i個位置，最后將前i個元素從臨時數組復制回原數組中后面的i個位置，這個算法總共需要移動i+（n-i）+i=i+n次數組元素，但使用了i個額外的存儲單元。

解法2：先設計一個函數將數組向左循環移動1個位置，然后再調用該算法i次，這個算法只使用了1個額外的存儲單元，但總共需要移動i× n次數組元素。

解法3：現在我們換一個角度看這個問題，將這個問題看作是把數組AB轉換成數組BA（A代表數組的前i個元素，B代表數組中余下的n-i個元素），先將A置逆得到A-1B，再將B置逆得到A-1B-1，最后將整個A-1B-1置逆得到（A-1B-1）-1=BA。設Reverse函數執行將數組元素置逆的操作，對abcdefgh向左循環移動3個位置的過程如下：

            Reverse（0，i-1）；              //得到cbadefgh
            Reverse（i，n-1）；              //得到cbahgfed
            Reverse（0，n-1）；              //得到defghabc

其原理可以用一個簡單的游戲來理解：將兩手的掌心對著自己，左手在右手上面，將一個具有10個元素的數組向左循環移動5位的操作過程如圖1-5所示。

這個算法總共需要交換i+（n-i）+n=2n次數組元素，只使用了1個用來交換的臨時單元，并且算法簡單、易懂，想出錯都很難。BrianKernighan在SoftwareToolsinPascal中使用了這個算法在文本編輯器中移動各行。

1.1.4 本書討論的主要內容

計算機能夠求解的問題一般可以分為數值問題和非數值問題。數值問題抽象出的數據模型通常是數學方程，非數值問題抽象出的數據模型通常是線性表、樹、圖等數據結構。下面請看幾個例子。

【例1-4】 為百元買百雞問題抽象數據模型。已知公雞5元一只，母雞3元一只，小雞1元三只，花100元錢買100只雞，問公雞、母雞、小雞各多少只？

解：設x、y和z分別表示公雞、母雞和小雞的個數，則有如下方程組成立：

【例1-5】 為學籍管理問題抽象數據模型。

解：用計算機來完成學籍管理，就是由計算機程序處理學生學籍登記表，實現增、刪、改、查等功能。圖1-6（a）所示為一張簡單的學生學籍登記表。在學籍管理問題中，計算機的操作對象是每個學生的學籍信息——表項，各表項之間的關系可以用線性結構來描述，如圖1-6（b）所示。

【例1-6】 為人機對弈問題抽象數據模型。

解：在對弈問題中，計算機的操作對象是對弈過程中可能出現的棋盤狀態——格局，而格局之間的關系是由對弈規則決定的。因為從一個格局可以派生出多個格局，所以，這種關系通常不是線性的。例如，從三子連珠游戲的某格局出發可以派生出五個新的格局，從新的格局出發，還可以再派生出新的格局，如圖1-7（a）所示；格局之間的關系可以用樹結構來描述，如圖1-7（b）所示。

【例1-7】 為七巧板涂色問題抽象數據模型。

解：假設有如圖1-8（a）所示的七巧板，使用至多4種不同顏色對七巧板涂色，要求每個區域涂一種顏色，相鄰區域的顏色互不相同。為了識別不同區域的相鄰關系，可以將七巧板的每個區域看成一個頂點，如果兩個區域相鄰，則這兩個頂點之間有邊相連，將七巧板抽象為圖結構，如圖1-8（b）所示。

本書討論非數值問題的數據組織和處理，主要內容如下：

（1）數據的邏輯結構：線性表、樹、圖等數據結構，其核心是如何組織待處理的數據以及數據之間的關系；

（2）數據的存儲結構：如何將線性表、樹、圖等數據結構存儲到計算機的存儲器中，其核心是如何有效地存儲數據以及數據之間的邏輯關系；

（3）算法：如何基于數據的某種存儲結構實現插入、刪除、查找等基本操作，其核心是如何有效地處理數據；

（4）常用的數據處理技術：包括查找技術和排序技術等；

（5）基本的算法設計技術：包括蠻力法、分治法、減治法、貪心法和動態規劃法等，并從算法設計技術的角度討論線性表、樹和圖等數據結構的基本操作，以及查找算法和排序算法的設計思想和設計過程。