1.1 數據結構的作用和意義

數據是外部世界信息的計算機化，是計算機加工處理的對象。運用計算機處理數據時，必須解決四個方面的問題：一是如何在計算機中方便、高效地表示和組織數據；二是如何在計算機存儲器（內存和外存）中存儲數據；三是如何對存儲在計算機中的數據進行操作，可以有哪些操作，如何實現這些操作以及如何對同一問題的不同操作方法進行評價；四是必須理解每種數據結構的性能特征，以便選擇一個適合于某個特定問題的數據結構。這些問題就是數據結構這門課程所要研究的主要問題。

1.1.1 數據結構的作用

我們知道，雖然每個人都懂得英語的語法與基本類型，但是對于同樣的題目，每個人寫出的作文，水平卻高低不一。程序設計也和寫英語作文一樣，雖然程序員都懂得語言的語法與語義，但是對于同樣的問題，不同的程序員會寫出來不一樣的程序。有的人寫出來的程序效率很高，有的人卻用復雜的方法來解決一個簡單的問題。

當然，程序設計水平的提高僅僅靠看幾本程序設計書是不行的。只有多思索，多練習，才能提高自己的程序設計水平，否則，書看得再多，提高也不大。程序設計水平要想提高，要多看別人寫的程序，多去思考問題。從別人寫的程序中，我們可以發現效率更高的解決方法；從思考問題的過程中，我們可以了解解決問題的方法常常不只一個。運用先前解決問題的經驗，來解決更復雜更深入的問題，是提高程序設計水平的最有效途徑。

數據結構正是前人在思索問題的過程中所想出的解決方法。一般而言，在學習程序設計一段時間后，學習“數據結構”便能讓你的程序設計水平上一個臺階。如果只學會了程序設計的語法和語義，那么你只能解決程序設計三分之一的問題，而且運用的方法并不是最有效的。但如果學會了數據結構的概念，就能在程序設計上，運用最有效的方法來解決絕大多數的問題。

《數據結構》這門課程的目的有三個。第一個是講授常用的數據結構，這些數據結構形成了程序員處理數據問題的基本工具。對于許多常見的問題，這些數據結構是理想的選擇。程序員可以直接拿來或經過少許的修改就可以使用，非常方便。第二個是講授常用的算法，這和數據結構一樣，是人們在長期實踐過程中的總結，程序員也可以直接拿來或經過少許的修改就可以使用，并且可以通過算法訓練來提高程序設計水平。第三個目的是通過程序設計的技能訓練促進程序員綜合能力的提高。

1.1.2 數據結構的意義

當我們用計算機解決一個問題時，必須告訴計算機如何去做。這需要先分析問題，確定一個適合的數據模型；然后，需要設計一個求解這個數據模型的算法，最后編寫程序，經過反復調試直至得到正確結果。這就像我們求解一個數學的應用題時，需要通過問題的描述列出一個方程或方程組，然后求解該方程（組）一樣。但是，需要計算機求解的大多數問題比數學方程要復雜得多。下面給出幾個簡單的例子加以說明。

【例1-1】某公司有50名員工，現在需要設計一個管理系統，完成對員工信息的查找、修改、插入或刪除。

首先需考慮如何表示這50名員工的信息。員工信息之間的關系可以看成是一個接一個排列的一對一關系，這是一種線性結構。可以建立一個線性表，線性表中的每一個元素表示一個員工信息，如表1-1所示，對員工信息的查找、修改、插入或刪除都應該基于該線性表進行操作。

員工信息是按工號一個接一個存放的。要查找某個員工信息，可以從第一個員工開始，依次向后一一比較，找到后，就可以修改了。如果要插入一個員工信息，可以先找到插入位置，把插入位置到最后的所有員工信息依次向后移動，空出位置后插入。如果要刪除一個員工信息，可以先找到刪除位置，然后將后面的員工信息依次前移即可。

【例1-2】計算機和人對弈問題。由于對弈的過程是在一定的規則下進行的，為使計算機能靈活對弈就必須將對弈過程中所有可能發生的情況以及相應的對策都考慮周全，同時，作為一名“好”的棋手，還應能預測棋局的發展趨勢，所以，為使計算機能夠和人進行對弈，必須事先將對弈的策略存入計算機，圖1.1（a）所示為一個九宮格的棋盤格局。

黑白雙方交替落子，如將從對弈開始到結束過程中可能出現的棋盤格局畫出來，則可得到一個倒長的“樹”，圖1.1（b）所示的是其中的一部分。“樹根”是對弈開始前的棋盤格局，而“葉子”是可能出現的結局。可以看到與線性結構不同，一個格局可以派生出幾個格局，也就是說，一個格局只能有一個前驅，而可以有多個后繼。如果計算機對弈開始前就計算出這樣一顆樹，就可以知道在對弈過程哪一種走法獲勝的概率大一些，就像一位高手能預測棋局發展的趨勢一樣，從而選擇一種較好的走法。

【例1-3】田徑比賽賽程安排問題。在一名選手參加多個項目的情況下，這些項目不能同時開始，否則會產生沖突。假設有一個比賽的參賽項目表如表1-2如示，那么A、B、E就不能同時開始。那么應如何安排賽程呢？

在此例中，可以把一個參賽項表示為圖中的一個頂點，而當兩個項目不能同時舉行時，以兩個頂點之間的連線表示互相矛盾的關系。如圖1.2（a）所示，每個圓圈表示一個比賽項目，兩個圓圈之間的連線表示這兩個圓圈不能在同一時間安排。所以當安排項目A時，只能同時安排沒有和A連線的項目，在此例中，應為C，可以按此方法將沒有沖突（互相沒有連線）的項目用同一種顏色涂色，圖1.2（b）所示為一種涂色結果。該結果表示的安排方法為（A、C），（B、D），（E），（F）。

通常，這種模型中，每個項目表示為一個頂點。每個頂點可以和其他任意個頂點聯系。這類問題的數學模型是一種稱為“圖”的數據結構。

綜合前面3個例子，這類非數值計算問題的數學模型是諸如表、樹、圖之類的數據結構，因此，數據結構是一門研究非數值計算的程序設計問題中計算機的操作對象以及它們之間的關系及操作的學科。

數據結構是一門介于數學、計算機硬件和計算機軟件三者之間的核心課程。數據結構不僅是一般程序設計的基礎，而且是設計和實現編譯程序、操作系統、數據庫系統及其他系統程序和大型應用程序的重要基礎。

學習“數據結構”既為進一步學習其他計算機專業課程提供必要的準備知識，也有助于提高軟件設計和程序編制水平。1968年，美國D.E.Kunth教授開創了數據結構的最初體系，他的名著《計算機程序設計技巧》較為系統地闡述了數據的邏輯結構和存儲結構及其操作。隨著計算機科學的飛速發展和應用領域的不斷擴大，到20世紀80年代初期，數據結構的基礎研究日臻成熟，已成為一門完整的學科。