第1章 引言

章首語：

程序 = 數據結構 + 算法。

本章從計算機科學的視角，開啟關于數據類型和數據結構的討論。數據類型是程序設計語言中的概念，讓我們能夠方便地表達豐富多樣的事物。數據結構是與算法緊密關聯的概念，讓各種算法能夠有效地通過程序實現。數據結構中的“數據”，在計算機內最底層的邏輯表示都是0、1串，其含義的解釋在于數據類型。數據結構中的“結構”，是本課程學習的主要內容，在程序中既服務于算法，也是算法的結果。數據結構并不神秘，從同學們開始學習程序設計的那一刻起，它就已經悄無聲息地存在于代碼的字里行間啦。

本章學習目標：

l  進一步理解數據的概念，尤其是從計算機程序的角度看數據的含義

l  理解數據類型的意義，了解有哪些不同的數據類型，理解不同數據類型的適用性和針對性

l  初步理解數據結構的概念和意義

l  了解數據類型與數據結構的關系

-----------------------------------------------------  

1.1  數據

數據是信息技術/計算機學科中一個最常用的術語，其內涵和外延都十分豐富。作為對本課程后面學習內容的一個引導，本小節首先描述對數據概念的一個多視角認識，同時指出在本課程中數據概念的主要定位，并通過幾個例子討論了數據類型的基本意義。

1.1.1 數據的含義

從本課程的先導模塊《數據與計算》的學習中我們已經了解，數據（Data）是一個含義十分寬泛的概念。人們需要對數據話題的語境有一定的共識，才能夠有效地討論與數據相關的問題。本模塊《數據與數據結構》中的“數據”，主要指計算機程序直接處理的數據，而不是人們日常提到的諸如“我想了解上海學生的健康數據”，“今年國民經濟運行的主要數據”之中的“數據”。

對于一般電腦用戶而言，能看到電腦桌面上和文件夾中有各種數據文件，例如一個電子表格，一個MP4視頻文件，等等。它們通常是由某些特定的應用程序生成，也需要特定的應用程序才能打開。因此，我們可以說它們是應用程序的輸入或輸出數據。

對于計算機編程人員，或者說計算機應用開發人員，他們除了要理解上述輸入數據外，還要理解程序內部的數據，具體就是每一個常量，每一個變量，它們代表什么，能對它們做些什么（施行什么操作）。

如果說人們日常提到的數據的含義是綜合應用層面的，加上前面兩種含義的數據，從信息技術的角度看，它們由表及里，表達了數據作為一個概念的三種實用性解釋。為指代方便起見，不妨稱為三個層次。這樣一種概念上的區分有利于我們討論問題，看到不同含義下作為一個術語的數據，服務于不同的目的。例如，當我們談論數據的價值，所指的數據，主要是第一層面的。在前面兩個必修模塊中已有充分討論。當我們談論兩個功能相似但品牌不同的應用程序的兼容性，則可能會涉及第二層面數據的問題 [1] 。而本課程中討論的數據，從第2章開始，主要關心第三層含義的數據，即計算機程序具體操作的數據。

關于數據概念的這樣一種劃分雖然不是完備的（即不一定每一個現實情境下的數據都能恰好歸到其中某一種），但它有益于我們在討論數據問題的時候保持適當的針對性和相關性。

最后，在一些場合可能與數據互換使用的術語還有數據集、數據元素、數據項，等等。它們的區別是第2章學習的內容，在這里只需理解后者是相對具象的表達就可以了。在從第3章開始的數據結構學習中，有時也用“數據單元”來表示能夠容納一個數據元素的存儲空間。

1.1.2數據的類型

當下常見的計算機又稱通用計算機，即同一套硬件設施，能運行各種各樣的應用程序，讓我們感到它“什么都能干”。為什么能做到呢？在理論層面，計算機科學家（圖靈）證明了，類似于乘法操作可以通過若干次加法完成，任何復雜的指令都可以由幾條簡單的指令實現；在實踐層面，數據分類是一個重要基礎，它讓我們能夠比較方便高效地表達各種事物。

下面是一個可以通過實際操作，體會數據分類的含義及其意義的例子。打開電腦中的某一個目錄，你很可能一個看到類似于圖1.1所示的情形。

圖 1.1 不同類型的文件

里面有9個文件，由不同的圖標代表。用鼠標雙擊某一個圖標，就會啟動某一個應用程序，然后你可以做有關的事情，編輯文檔、看視頻，等等。作為一個電腦用戶，這似乎已經成為了自然，不會想為什么這種過程能夠發生。但你現在可以嘗試回答三個問題，（1）為什么點擊左上角的那個文件（A.docx），文本編輯軟件Word就會啟動，點擊第二排第一個文件（D.mp4），視頻播放器就會啟動呢？（2）如果修改文件名，將A.docx改成X.docx，情況會改變嗎？如果將A.docx改成A.mp4呢？（3）C.png和G.jpg的文件名和擴展名都不相同，分別點擊它們，會成功啟動同一個應用程序嗎？為什么呢？

這就屬于從計算機應用的角度看數據類型的問題，計算機需要用戶（以文件擴展名的形式）顯示地告訴它數據文件的類型，方能正常有效地工作。同時，也是本課程的重點，在計算機應用開發人員的視野下，數據類型也是一個重要的概念，幾乎無處不在。

在先導模塊《數據與計算》中我們已經知道，計算機硬件最核心的抽象是“CPU+存儲器”。存儲器由若干能夠存放固定字長（即基本存取單元中0或1的個數，稱為“位數”是統一的，例如8位或一個字節）的數據單元構成，CPU按照程序指令安排的次序將其中的數據取出，做某種簡單操作，然后再放回去。這意味著任何二進制碼對計算機（硬件）而言沒有特定的含義。例如，我們知道在ASCII編碼中，00100011表示“#”，00111111表示“?”，如果讓計算機做00100011+00111111，它會做，并正確地給出01100010，即ASCII編碼的“b”。但一般看來這沒有任何意義。這里只是說計算機做了沒有意義的操作，在其他情況下則有可能由于程序員的疏忽，讓計算機做了明顯不該做的操作而導致錯誤，造成損失。

在計算機發展的早期，程序員只能用機器語言，情況就是這樣的。他們必須帶著對各個二進制串的理解，小心翼翼地編程序，避免讓計算機做不該做的操作。這樣，軟件生產率很低，也難以編出大規模復雜的程序，呈現出一個明顯的瓶頸，阻礙著計算機在人們經濟社會生活中的普及應用。

高級程序設計語言（例如Fortran, C, Java, Python，等等）及其編譯（解釋）技術的發展，是解決這個瓶頸問題的基本途徑。程序語言中讓程序員指出數據的類型（數值型、邏輯型、字符型、指針型，等等），編譯器根據不同數據類型的語義，檢查是否有“不合法”的操作，若發現，則在程序調試階段就報告給程序員，從而避免在生產運行時出錯，造成損失。例如在Python中，如果你試圖運行如下程序：

a = ‘1’

b = ‘2’

c = a*b

就會被告知一個類型錯誤（TypeError），說a和b是兩個字符串，不能相乘。這個例子看起來簡單，但要做好各種類型錯誤的檢查是很不容易的，是現代編譯器的一個重要功能。

    數據類型，作為程序設計語言中的一個重要概念，也是不斷發展的，其不懈的追求是希望給程序員提供更有效地向計算機表達問題求解算法的能力，提高程序開發的效率。所謂“更有效地”含義之一就是表達層次更高。例如要寫一個將100個數求和的程序，原則上可以用100個標量來表示那些數，然后在程序中顯式寫出99次加法，但那真的很麻煩。而有了數組類型后，就是一個變量名，用下標來指示不同的數，99次加法蘊含在循環語句的1次加法中，大大方便。

程序設計語言中各種數據類型的有效運用，離不開編譯（解釋）技術的配合。我們有時侯可能聽人說，程序語言中規定了某種功能，但某一版本的編譯器“不支持”，過了一段時間后，又聽說出新版編譯器了，支持那種功能，就是這個道理。例如，當賦值語句兩邊類型不相同時，Python2會做一些缺省的處理（看起來省事，但容易隱含錯誤），而Python3則要求程序員在程序中顯式表達類型轉換，以避免疏忽造成的錯誤。舉個例子，下面這段程序，在Python2和Python3中的執行結果是不同的：

a1 = 3; a2=3.0

b = 2

print (a1/b,a2/b)

Python2給出(1, 1.5)，Python3給出(1.5, 1.5)。也就是說，Python2如果看到兩個操作數都是整數，算的結果就自動取整（稱為“缺省”操作）。這有時候似乎很方便，但更多的是帶來潛在的錯誤。在Python3中，如果就是想“取整”，則需要做print(int(a1/b))或者print(a1//b)，把意圖顯式地表達出來。

在計算機領域，與數據類型相關的，還有一個概念是“數據格式”，它們與采用數據的應用程序相關，通常用文件擴展名標識，例如我們可以說圖1.1中有9個文件，代表8種數據格式。就程序開發而言，針對程序的輸入和輸出，我們常聽見純文本文件和二進制文件兩種說法。前者是指文件內容都是ASCII編碼（在中文情形就是國標漢字編碼）的字符，可以用任何常用的文本編輯軟件打開，因而具有人工可讀性。二進制文件則常常是特定應用生成的，包含一些（或者全部）非ASCII編碼的內容，只有知道其生成規則（格式）的程序才能正常打開。常常，我們會聽到說“這文件是亂碼”。有時候不一定真是亂碼，而是試圖打開它的程序不對。從1.1.2節的例子及其練習中我們可以得到切身體會。初學程序設計，通常喜歡用純文本文件，而成熟的商業應用程序，絕大多數都采用二進制文件。

進而，數據類型還是其他一些學科領域的基礎概念。最明顯的，當屬統計學科。在那里，有類別數據和數值數據之分，例如性別就是一種類別數據，它可以取值“男”或“女”。當用計算機做統計數據處理的時候（這是當下大數據時代經常出現的需求），例如本書第2章的項目活動，我們需要在兩個學科不同數據類型體系之間建立某種方便的對應，如用計算機中的數值0和1分別表示統計類別數據值“男”和“女”。

1.2  數據結構

如果說數據類型是多個學科都可能有的概念（含義有別），數據結構則是計算機學科的特有概念。關于數據結構的知識是計算機學科的專業基礎知識，運用數據結構的能力是開發高水平程序必需的能力，理解了數據結構及其運用中蘊含的邏輯常常令人欣喜。本節從總體上討論數據結構的意義及其與數據類型的關系，各種典型的數據結構與應用是本書的主體，將在第3、4、5章詳細介紹。

1.2.1數據結構的意義

數據結構這個概念，并不是在計算機誕生之初就有的，它是伴隨著程序設計技術的發展，旨在彌合計算機硬件的簡單性和程序應用的復雜性之間的鴻溝，逐步形成和發展起來的。我們通過一個應用例子，來初步體會上面的陳述。

假設要有一個程序，不斷接收輸入數據（即它面對的是一個“數據流”），對每一個新到的數據（嚴格講，數據元素），它要判斷是否曾經收到過。如果是，則拋棄；如果否，則保留。我們關心如何讓這個判斷過程的效率比較高 [2] 。作為一個例子，設輸入數據流中來了8個數：4，3，5，1，4，2，3，1。

一種方法是采用簡單的線性存儲結構 [3] ，即存儲空間中的存儲單元是順序編號的 0，1，2，3，…，n-1，處理過程可如下描述：

每收到一個數，就依次和空間中已有的數比較，發現有相等的，就停止；若一直到最后還沒有相等的，就把這個新數放在后面。

如果用比較次數作為效率衡量的指標，對上面給出的8個數，在存儲空間中留下的結果是4，3，5，1，2，在每一個輸入數據上用的比較次數見表1.1，總的比較次數為17。

表1.1 簡單線性結構下的比較次數

另一種方法是，想象有一種非線性的存儲結構，每當收到一個新的數，就在該結構的引導下進行判斷過程，必要的話，也對該結構進行動態更新，以支持對后續數據的判斷。圖1.2展示在這個例子數據上該結構的變化過程，其中有8個框，分別對應8個數據依次到來判斷處理后的結果，虛線框表示收到的是已有的數據，也是要做判斷的，但對整個留存的結果沒影響。

圖1.2 在輸入序列4, 3, 4, 1, 4, 2, 3, 1下的二叉查找樹變化過程

    這樣的結構稱為“二叉樹”（是后面要學習的重點內容之一，這里只需要體會大致含義就夠了），它由一些“節點”和“邊”構成。最頂上的節點稱為根節點，根節點左下方整個稱為“左子樹”，右下方的是“右子樹” [4] 。基于這樣的結構，具體操作是這樣的：

當收到一個新的數（x），首先和樹根相比，如果相等，就停止；如果較小，就試圖和左子樹比，若左邊沒有可比的，就把x放到左下，讓它成為左子樹的根；如果較大，就試圖和右子樹比，若右邊沒有可比的，就把x放到右下，讓它成為右子樹的根。其中“試圖和左子樹比”和“試圖和右子樹比”，是一個遞歸的過程 [5] ，即把它們也看成是二叉樹（但要小一些），照樣進行。

對我們的例子數據跟蹤這個過程，可以看到在每一個輸入數據上用的比較次數 [6] 見表1.2，總的比較次數為13。

表1.2 二叉樹結構下的比較次數

這里的重點不是要討論13和17相比到底有多好，而是要意識到，有可能通過采用不同的數據組織方式來提高計算的效率。類似于二叉樹這樣的（邏輯）結構，計算機硬件是不懂的，需要計算機科學家發明出來，并通過軟件的方式體現在硬件的線性存儲空間上。幾十年來，人們根據不同的計算需求發明了多種數據組織的形態，以支持高效軟件的開發，統稱為數據結構，是本課程學習的重點。其中，二叉樹是頗具代表性的，在本書多處都會涉及到。

上述例子讓我們得到了數據結構的一種直觀印象，即它表達了程序數據之間的某種關系。這里特別值得認識到的是，此例圖1.2中數據之間的那種關系，是由算法邏輯派生出來的，反過來又支持算法邏輯的貫徹執行。一般而言，數據結構上的數據，可能是程序的輸入數據，也可能不是，常常也包括程序運行過程中產生的中間結果數據或控制數據。即便數據結構上的數據就是程序輸入數據，由數據結構表達出來的關系，可能是那些數據之間的一種天然關系，也可能不是。一般而言，數據結構中數據的關系是根據算法邏輯的需要形成的關系。

1.2.2 數據結構與算法

計算（過程）是操作（或指令執行）的序列；算法（程序）是操作序列的描述：先做什么、后做什么、當某個條件出現時該做什么，等等；操作是作用在數據（或數據項）上的，數據結構是數據的組織形態，體現數據元素之間的某種關系，以支持算法的高效執行。

有時候，數據之間有一種天然的結構 [7] ，算法設計者依據該結構來編排操作序列，按照計算任務的需要，對該結構上的數據進行比較、交換、更新等操作。在整個過程中，數據結構不發生變化。

還有些時候，數據之間的結構關系是在算法過程中形成的。上一節圖1.2就是一個示例。在這種情況下，算法設計者在腦子里有某種抽象的結構，所設計的操作序列一邊在數據基礎上構建具體的數據結構，一邊依托已構成的部分結構完成計算任務所要求的數據操作。我們體會一下，按照這樣的算法編寫的程序，是不是有“邊執行邊給自己創造條件”的意味？

上述兩種情形（不妨顧名思義，稱前者為靜態，后者為動態），都是在計算機應用中常見的，但后者更體現數據結構應用的精髓，體現了算法與數據結構的精巧互動。當然，也有許多場合，在同一個算法中既用到靜態數據結構，也用到動態數據結構。

瑞士計算機科學家，Pascal等編程語言發明人，1984年圖靈獎得主，尼古拉斯·沃斯（Niklaus Wirth）教授在1975年曾給出“算法+數據結構=程序”的著名等式，是對數據結構與算法關系的一個精辟詮釋。這樣一種見解，在動態數據結構的運用中顯得格外精彩。

1.2.3 數據結構與數據類型

    在1.1節，我們聚焦的是數據類型的含義和意義。數據類型是程序語言中的概念，幫助提高程序開發的效率。1.2節討論的數據結構是程序設計中的概念，與算法一起，旨在開發運行效率高的程序 [8] 。盡管有如此區別，在計算機科學的實踐中它們也有密切的聯系。

    首先，雖然各種數據結構的概念本身是抽象的（或者說是邏輯的），但在程序中的實現總是具體的，由若干數據元素及其關系構成。而數據元素（或其中的數據項）總會有一定的數據類型，同一種數據結構在不同的應用中其數據元素完全可能是不同的數據類型，例如1.2.1中的那個例子，數據可能是整數，也可能是實數，但數據結構不變。這是一種簡單的“你中有我”。

    如我們要在第2章重點學習的，現代高級程序設計語言，除了提供我們在《數據與計算》模塊中已經熟悉的數值型、字符型等基本數據類型外，還支持程序員定義比較復雜的數據類型。例如一個表達個人信息的數據元素，可以定義為由一個字符串（姓名），一個數字（年齡）和一個字符（性別）構成的數據類型（例如命名為“Person”）。這樣的數據元素也可以看成是一個數據結構。于是我們可以說基于數據結構定義了一個數據類型。這是簡單的“我中有你”。

    更復雜一些的，還可以基于諸如線性表、二叉樹等數據結構定義數據類型。而在那樣的數據類型上的操作，就對應在相應數據結構上支持的操作。以線性表為例，就可以做插入、刪除、讀取第i個元素等操作。

    鑒于上述數據類型和數據結構概念在程序設計應用中相互交織的情形，對一個具體的變量來說，取決于提及的場合，就可能有兩種身份，例如既可以說它是具有線性表（列表）類型的數據，也可以說它是一個線性表（數據結構）。有些概念，在運用上也具有兩重性，例如字符串和數組，在編程中主要看做是數據類型，但因為它們也體現了其中數據元素之間的關系，有時人們也稱它們為數據結構。這樣的現象對初學者可能造成困擾，但他們一旦習慣，就能感受到那正是計算機科學的魅力之一。

最后，在討論數據結構相關問題時，常常會涉及“邏輯結構”與“物理實現”之類的說法。理解后者中的“物理”不是物理學科中的物理的含義，本質上是另一個層次的“邏輯”（甚至只是另一種邏輯），是有意義的。這樣我們就能意識到，當我們在程序中實現某種數據結構，一切都只是發生在相應程序設計語言管理的程序數據空間中，與計算機硬件的存儲器（物理）其實沒有直接的映射關系。這樣，當我們在一些數據結構教材中看到“計算機存儲器”和“內存”等術語，一種合適的理解是它們不過是“線性地址空間”的一種方便的講法，包括但不一定就是計算機硬件存儲器。

學生活動1：

1.  課堂上（也可以課后），實際動手體驗1.1.2節中的例子，回答所提出的問題，包括討論為什么修改文件名很順利，而修改文件擴展名可能會得到警告。

2.  在Python中編一個會產生“TypeError”的小程序。

3.  參照1.2.1節中的例子，對16個數的序列：5，3，5，4，2，1，6，8，3，3，4，1，7，8，4，2，給出類似于表1.1和表1.2那樣的結果。

[1] 例如有的視頻播放器能讀入多種格式的視頻文件并正常播放，有的則只能播放單一格式的。前者被認為是兼容性強。還例如我們經常會碰到某些網站只能通過特定品牌（或版本）的瀏覽器訪問，也屬于這類問題。因為網頁就可以看成是瀏覽器程序的輸入數據。

[2] 這個例子聽起來簡單，但它是許多實際應用的抽象，例如互聯網路由器就需要有類似的功能。

[3] 計算機硬件的存儲器就是一個例子，在程序中用的一維數組也是一個例子。

[4] 每個節點可能左右兩個子樹都有，也可能只有一個，或者沒有。沒有子樹的節點稱為葉節點。

[5] 后面要學習的一個概念，此處可以比擬俄羅斯套娃的情景，在形態上都是一樣的，一個套一個，一個比一個小。

[6] 鑒于此處例子不可能用太多數據，這里假設了用1次比較就能給出<, =, >的判斷。在本書的5.2節將會看到，這個假設不影響二叉樹優于線性查找的基本結論。

[7] 例如每小時測一次氣溫，一天得到24個數字，依時間順序成一列。這里的“一列”就可以看成是一種數據結構。

[8] 嚴格講，合適數據類型的采用也可能提高程序運行效率，良好數據結構的采用也可能提高程序開發的效率，但它們的作用重點有區別。