《數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)》（基于新課標(biāo)的高中信息科技教材之一）（1）

第1章 引言

章首語：

程序 = 數(shù)據(jù)結(jié)構(gòu) + 算法。

本章從計(jì)算機(jī)科學(xué)的視角，開啟關(guān)于數(shù)據(jù)類型和數(shù)據(jù)結(jié)構(gòu)的討論。數(shù)據(jù)類型是程序設(shè)計(jì)語言中的概念，讓我們能夠方便地表達(dá)豐富多樣的事物。數(shù)據(jù)結(jié)構(gòu)是與算法緊密關(guān)聯(lián)的概念，讓各種算法能夠有效地通過程序?qū)崿F(xiàn)。數(shù)據(jù)結(jié)構(gòu)中的“數(shù)據(jù)”，在計(jì)算機(jī)內(nèi)最底層的邏輯表示都是0、1串，其含義的解釋在于數(shù)據(jù)類型。數(shù)據(jù)結(jié)構(gòu)中的“結(jié)構(gòu)”，是本課程學(xué)習(xí)的主要內(nèi)容，在程序中既服務(wù)于算法，也是算法的結(jié)果。數(shù)據(jù)結(jié)構(gòu)并不神秘，從同學(xué)們開始學(xué)習(xí)程序設(shè)計(jì)的那一刻起，它就已經(jīng)悄無聲息地存在于代碼的字里行間啦。

本章學(xué)習(xí)目標(biāo)：

l  進(jìn)一步理解數(shù)據(jù)的概念，尤其是從計(jì)算機(jī)程序的角度看數(shù)據(jù)的含義

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

l  初步理解數(shù)據(jù)結(jié)構(gòu)的概念和意義

l  了解數(shù)據(jù)類型與數(shù)據(jù)結(jié)構(gòu)的關(guān)系

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

1.1  數(shù)據(jù)

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

1.1.1 數(shù)據(jù)的含義

從本課程的先導(dǎo)模塊《數(shù)據(jù)與計(jì)算》的學(xué)習(xí)中我們已經(jīng)了解，數(shù)據(jù)（Data）是一個(gè)含義十分寬泛的概念。人們需要對數(shù)據(jù)話題的語境有一定的共識(shí)，才能夠有效地討論與數(shù)據(jù)相關(guān)的問題。本模塊《數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)》中的“數(shù)據(jù)”，主要指計(jì)算機(jī)程序直接處理的數(shù)據(jù)，而不是人們?nèi)粘Ｌ岬降闹T如“我想了解上海學(xué)生的健康數(shù)據(jù)”，“今年國民經(jīng)濟(jì)運(yùn)行的主要數(shù)據(jù)”之中的“數(shù)據(jù)”。

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

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

如果說人們?nèi)粘Ｌ岬降臄?shù)據(jù)的含義是綜合應(yīng)用層面的，加上前面兩種含義的數(shù)據(jù)，從信息技術(shù)的角度看，它們由表及里，表達(dá)了數(shù)據(jù)作為一個(gè)概念的三種實(shí)用性解釋。為指代方便起見，不妨稱為三個(gè)層次。這樣一種概念上的區(qū)分有利于我們討論問題，看到不同含義下作為一個(gè)術(shù)語的數(shù)據(jù)，服務(wù)于不同的目的。例如，當(dāng)我們談?wù)摂?shù)據(jù)的價(jià)值，所指的數(shù)據(jù)，主要是第一層面的。在前面兩個(gè)必修模塊中已有充分討論。當(dāng)我們談?wù)搩蓚€(gè)功能相似但品牌不同的應(yīng)用程序的兼容性，則可能會(huì)涉及第二層面數(shù)據(jù)的問題 [1] 。而本課程中討論的數(shù)據(jù)，從第2章開始，主要關(guān)心第三層含義的數(shù)據(jù)，即計(jì)算機(jī)程序具體操作的數(shù)據(jù)。

關(guān)于數(shù)據(jù)概念的這樣一種劃分雖然不是完備的（即不一定每一個(gè)現(xiàn)實(shí)情境下的數(shù)據(jù)都能恰好歸到其中某一種），但它有益于我們在討論數(shù)據(jù)問題的時(shí)候保持適當(dāng)?shù)尼槍π院拖嚓P(guān)性。

最后，在一些場合可能與數(shù)據(jù)互換使用的術(shù)語還有數(shù)據(jù)集、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)，等等。它們的區(qū)別是第2章學(xué)習(xí)的內(nèi)容，在這里只需理解后者是相對具象的表達(dá)就可以了。在從第3章開始的數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)中，有時(shí)也用“數(shù)據(jù)單元”來表示能夠容納一個(gè)數(shù)據(jù)元素的存儲(chǔ)空間。

1.1.2數(shù)據(jù)的類型

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

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

圖 1.1 不同類型的文件

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

這就屬于從計(jì)算機(jī)應(yīng)用的角度看數(shù)據(jù)類型的問題，計(jì)算機(jī)需要用戶（以文件擴(kuò)展名的形式）顯示地告訴它數(shù)據(jù)文件的類型，方能正常有效地工作。同時(shí)，也是本課程的重點(diǎn)，在計(jì)算機(jī)應(yīng)用開發(fā)人員的視野下，數(shù)據(jù)類型也是一個(gè)重要的概念，幾乎無處不在。

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

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

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

a = ‘1’

b = ‘2’

c = a*b

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

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

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

a1 = 3; a2=3.0

b = 2

print (a1/b,a2/b)

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

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

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

1.2  數(shù)據(jù)結(jié)構(gòu)

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

1.2.1數(shù)據(jù)結(jié)構(gòu)的意義

數(shù)據(jù)結(jié)構(gòu)這個(gè)概念，并不是在計(jì)算機(jī)誕生之初就有的，它是伴隨著程序設(shè)計(jì)技術(shù)的發(fā)展，旨在彌合計(jì)算機(jī)硬件的簡單性和程序應(yīng)用的復(fù)雜性之間的鴻溝，逐步形成和發(fā)展起來的。我們通過一個(gè)應(yīng)用例子，來初步體會(huì)上面的陳述。

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

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

每收到一個(gè)數(shù)，就依次和空間中已有的數(shù)比較，發(fā)現(xiàn)有相等的，就停止；若一直到最后還沒有相等的，就把這個(gè)新數(shù)放在后面。

如果用比較次數(shù)作為效率衡量的指標(biāo)，對上面給出的8個(gè)數(shù)，在存儲(chǔ)空間中留下的結(jié)果是4，3，5，1，2，在每一個(gè)輸入數(shù)據(jù)上用的比較次數(shù)見表1.1，總的比較次數(shù)為17。

表1.1 簡單線性結(jié)構(gòu)下的比較次數(shù)

另一種方法是，想象有一種非線性的存儲(chǔ)結(jié)構(gòu)，每當(dāng)收到一個(gè)新的數(shù)，就在該結(jié)構(gòu)的引導(dǎo)下進(jìn)行判斷過程，必要的話，也對該結(jié)構(gòu)進(jìn)行動(dòng)態(tài)更新，以支持對后續(xù)數(shù)據(jù)的判斷。圖1.2展示在這個(gè)例子數(shù)據(jù)上該結(jié)構(gòu)的變化過程，其中有8個(gè)框，分別對應(yīng)8個(gè)數(shù)據(jù)依次到來判斷處理后的結(jié)果，虛線框表示收到的是已有的數(shù)據(jù)，也是要做判斷的，但對整個(gè)留存的結(jié)果沒影響。

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

    這樣的結(jié)構(gòu)稱為“二叉樹”（是后面要學(xué)習(xí)的重點(diǎn)內(nèi)容之一，這里只需要體會(huì)大致含義就夠了），它由一些“節(jié)點(diǎn)”和“邊”構(gòu)成。最頂上的節(jié)點(diǎn)稱為根節(jié)點(diǎn)，根節(jié)點(diǎn)左下方整個(gè)稱為“左子樹”，右下方的是“右子樹” [4] ?；谶@樣的結(jié)構(gòu)，具體操作是這樣的：

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

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

表1.2 二叉樹結(jié)構(gòu)下的比較次數(shù)

這里的重點(diǎn)不是要討論13和17相比到底有多好，而是要意識(shí)到，有可能通過采用不同的數(shù)據(jù)組織方式來提高計(jì)算的效率。類似于二叉樹這樣的（邏輯）結(jié)構(gòu)，計(jì)算機(jī)硬件是不懂的，需要計(jì)算機(jī)科學(xué)家發(fā)明出來，并通過軟件的方式體現(xiàn)在硬件的線性存儲(chǔ)空間上。幾十年來，人們根據(jù)不同的計(jì)算需求發(fā)明了多種數(shù)據(jù)組織的形態(tài)，以支持高效軟件的開發(fā)，統(tǒng)稱為數(shù)據(jù)結(jié)構(gòu)，是本課程學(xué)習(xí)的重點(diǎn)。其中，二叉樹是頗具代表性的，在本書多處都會(huì)涉及到。

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

1.2.2 數(shù)據(jù)結(jié)構(gòu)與算法

計(jì)算（過程）是操作（或指令執(zhí)行）的序列；算法（程序）是操作序列的描述：先做什么、后做什么、當(dāng)某個(gè)條件出現(xiàn)時(shí)該做什么，等等；操作是作用在數(shù)據(jù)（或數(shù)據(jù)項(xiàng)）上的，數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的組織形態(tài)，體現(xiàn)數(shù)據(jù)元素之間的某種關(guān)系，以支持算法的高效執(zhí)行。

有時(shí)候，數(shù)據(jù)之間有一種天然的結(jié)構(gòu) [7] ，算法設(shè)計(jì)者依據(jù)該結(jié)構(gòu)來編排操作序列，按照計(jì)算任務(wù)的需要，對該結(jié)構(gòu)上的數(shù)據(jù)進(jìn)行比較、交換、更新等操作。在整個(gè)過程中，數(shù)據(jù)結(jié)構(gòu)不發(fā)生變化。

還有些時(shí)候，數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系是在算法過程中形成的。上一節(jié)圖1.2就是一個(gè)示例。在這種情況下，算法設(shè)計(jì)者在腦子里有某種抽象的結(jié)構(gòu)，所設(shè)計(jì)的操作序列一邊在數(shù)據(jù)基礎(chǔ)上構(gòu)建具體的數(shù)據(jù)結(jié)構(gòu)，一邊依托已構(gòu)成的部分結(jié)構(gòu)完成計(jì)算任務(wù)所要求的數(shù)據(jù)操作。我們體會(huì)一下，按照這樣的算法編寫的程序，是不是有“邊執(zhí)行邊給自己創(chuàng)造條件”的意味？

上述兩種情形（不妨顧名思義，稱前者為靜態(tài)，后者為動(dòng)態(tài)），都是在計(jì)算機(jī)應(yīng)用中常見的，但后者更體現(xiàn)數(shù)據(jù)結(jié)構(gòu)應(yīng)用的精髓，體現(xiàn)了算法與數(shù)據(jù)結(jié)構(gòu)的精巧互動(dòng)。當(dāng)然，也有許多場合，在同一個(gè)算法中既用到靜態(tài)數(shù)據(jù)結(jié)構(gòu)，也用到動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)。

瑞士計(jì)算機(jī)科學(xué)家，Pascal等編程語言發(fā)明人，1984年圖靈獎(jiǎng)得主，尼古拉斯·沃斯（Niklaus Wirth）教授在1975年曾給出“算法+數(shù)據(jù)結(jié)構(gòu)=程序”的著名等式，是對數(shù)據(jù)結(jié)構(gòu)與算法關(guān)系的一個(gè)精辟詮釋。這樣一種見解，在動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)的運(yùn)用中顯得格外精彩。

1.2.3 數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)類型

    在1.1節(jié)，我們聚焦的是數(shù)據(jù)類型的含義和意義。數(shù)據(jù)類型是程序語言中的概念，幫助提高程序開發(fā)的效率。1.2節(jié)討論的數(shù)據(jù)結(jié)構(gòu)是程序設(shè)計(jì)中的概念，與算法一起，旨在開發(fā)運(yùn)行效率高的程序 [8] 。盡管有如此區(qū)別，在計(jì)算機(jī)科學(xué)的實(shí)踐中它們也有密切的聯(lián)系。

    首先，雖然各種數(shù)據(jù)結(jié)構(gòu)的概念本身是抽象的（或者說是邏輯的），但在程序中的實(shí)現(xiàn)總是具體的，由若干數(shù)據(jù)元素及其關(guān)系構(gòu)成。而數(shù)據(jù)元素（或其中的數(shù)據(jù)項(xiàng)）總會(huì)有一定的數(shù)據(jù)類型，同一種數(shù)據(jù)結(jié)構(gòu)在不同的應(yīng)用中其數(shù)據(jù)元素完全可能是不同的數(shù)據(jù)類型，例如1.2.1中的那個(gè)例子，數(shù)據(jù)可能是整數(shù)，也可能是實(shí)數(shù)，但數(shù)據(jù)結(jié)構(gòu)不變。這是一種簡單的“你中有我”。

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

    更復(fù)雜一些的，還可以基于諸如線性表、二叉樹等數(shù)據(jù)結(jié)構(gòu)定義數(shù)據(jù)類型。而在那樣的數(shù)據(jù)類型上的操作，就對應(yīng)在相應(yīng)數(shù)據(jù)結(jié)構(gòu)上支持的操作。以線性表為例，就可以做插入、刪除、讀取第i個(gè)元素等操作。

    鑒于上述數(shù)據(jù)類型和數(shù)據(jù)結(jié)構(gòu)概念在程序設(shè)計(jì)應(yīng)用中相互交織的情形，對一個(gè)具體的變量來說，取決于提及的場合，就可能有兩種身份，例如既可以說它是具有線性表（列表）類型的數(shù)據(jù)，也可以說它是一個(gè)線性表（數(shù)據(jù)結(jié)構(gòu)）。有些概念，在運(yùn)用上也具有兩重性，例如字符串和數(shù)組，在編程中主要看做是數(shù)據(jù)類型，但因?yàn)樗鼈円搀w現(xiàn)了其中數(shù)據(jù)元素之間的關(guān)系，有時(shí)人們也稱它們?yōu)閿?shù)據(jù)結(jié)構(gòu)。這樣的現(xiàn)象對初學(xué)者可能造成困擾，但他們一旦習(xí)慣，就能感受到那正是計(jì)算機(jī)科學(xué)的魅力之一。

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

學(xué)生活動(dòng)1：

1.  課堂上（也可以課后），實(shí)際動(dòng)手體驗(yàn)1.1.2節(jié)中的例子，回答所提出的問題，包括討論為什么修改文件名很順利，而修改文件擴(kuò)展名可能會(huì)得到警告。

2.  在Python中編一個(gè)會(huì)產(chǎn)生“TypeError”的小程序。

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

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

[2] 這個(gè)例子聽起來簡單，但它是許多實(shí)際應(yīng)用的抽象，例如互聯(lián)網(wǎng)路由器就需要有類似的功能。

[3] 計(jì)算機(jī)硬件的存儲(chǔ)器就是一個(gè)例子，在程序中用的一維數(shù)組也是一個(gè)例子。

[4] 每個(gè)節(jié)點(diǎn)可能左右兩個(gè)子樹都有，也可能只有一個(gè)，或者沒有。沒有子樹的節(jié)點(diǎn)稱為葉節(jié)點(diǎn)。

[5] 后面要學(xué)習(xí)的一個(gè)概念，此處可以比擬俄羅斯套娃的情景，在形態(tài)上都是一樣的，一個(gè)套一個(gè)，一個(gè)比一個(gè)小。

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

[7] 例如每小時(shí)測一次氣溫，一天得到24個(gè)數(shù)字，依時(shí)間順序成一列。這里的“一列”就可以看成是一種數(shù)據(jù)結(jié)構(gòu)。

[8] 嚴(yán)格講，合適數(shù)據(jù)類型的采用也可能提高程序運(yùn)行效率，良好數(shù)據(jù)結(jié)構(gòu)的采用也可能提高程序開發(fā)的效率，但它們的作用重點(diǎn)有區(qū)別。