1.1　什么是數據結構

隨著計算機應用領域的不斷擴大，簡單的數據類型遠遠不能滿足程序設計的需要，各元素之間的聯系也不再是普通數學方程所能表達的。掌握數據結構和算法在很大程度上取決于描述實際問題的數據結構，那么數據結構究竟是研究什么的呢？

1.1.1　從數據結構實驗演示系統認識數據結構

下面先介紹一個簡單的數據結構實驗演示系統。

在Windows等操作系統下運行本書提供的DS.exe文件，就會出現如下信息：

按提示進行選擇，例如選擇2，即進入棧子系統。

再按提示選擇4，進入二進制和十進制轉換的演示……

學過C（或C++）程序設計的人對結構化程序設計的一些特點應有一定的了解，但是對于數據，特別是數據結構往往缺乏更深層次的認識。著名的計算機科學家N.Writh提出“算法+數據結構=程序”的思想，明確地指出了數據結構實際上是程序的主要部分。

數據結構是一門介于數學、計算機硬件和計算機軟件三者之間的核心課程。在計算機科學中，數據結構不僅是一般非數值計算程序設計的基礎，還是設計和實現匯編語言、編譯程序、操作系統、數據庫系統，以及其他系統程序和大型應用程序的重要基礎。打好“數據結構”這門課程的扎實基礎，將會對程序設計有進一步的認識，使編程能力上一個臺階，從而使自己學習和開發應用軟件的能力有明顯的提高。

從我國計算機教學現狀來看，數據結構不僅僅是計算機專業教學計劃中的核心課程之一，而且已經逐步成為非計算機專業學生的重要選修課程。

1.1.2　數據結構研究的內容

用計算機解決一個具體問題時，大致需要經過以下幾個步驟：

（1）從具體問題抽象出適當的數學模型。

（2）設計求解數學模型的算法。

（3）編制、運行并調試程序，直到解決實際問題。

尋求數學模型的實質是分析問題，從中提取操作的對象，并找出這些操作對象之間的關系，然后用數學語言加以描述。

下面請看幾個例子。

【例1-1】學生入學情況登記簡表，如表1-1所示。

續表

表1-1稱為一個表數據結構，表中的每一行是一個結點（node），或稱記錄（record），由學號、姓名、性別、入學總分等數據項（item）組成。在此表中，第一條記錄沒有直接前驅，稱為開始結點；最后一條記錄沒有直接后繼，稱為終端結點。除了第一條記錄和最后一條記錄以外，其余的記錄，都有且僅有一條直接前驅記錄和一條直接后繼記錄。這些結點之間是“一對一”的關系，它構成了“學生入學情況登記簡表”的邏輯結構。

那么，“學生入學情況登記簡表”在計算機的存儲器中又是如何存儲的呢？表中各元素是存儲在存儲器中連續的存儲單元（順序存儲），還是用指針鏈接存儲在不連續的存儲單元（鏈接存儲）呢？它構成了“學生入學情況登記簡表”的存儲結構。

如何在“學生入學情況登記簡表”中查找、插入和刪除記錄，以及如何對記錄進行排序、統計、分析等，構成了數據的運算。

【例1-2】井字棋對弈問題。

圖1-1（a）是井字棋對弈過程中的一個格局，任何一方只要使相同的3個棋子連成一條直線（可以是一行、一列或一條對角線）即為勝方。如果下一步由“╳”方下，可以派生出5個子格局，如圖1-1（b）所示；隨后由“〇”方接著下，對于每個子格局又可以派生出4個子格局。

若將從對弈開始到結束的過程中所有可能的格局畫在一張圖上，即形成一棵倒掛的對弈“樹”。“樹根”是對弈開始時的第一步棋，而所有“葉子”便是可能出現的結局，對弈過程就是從樹根沿樹杈到某個葉子的過程。在本例中，對弈開始之前的棋盤格局沒有直接前驅，稱為開始結點（即根），以后每走一步棋，都有多種應對的策略，結點之間存在著“一對多”的關系，它構成了井字棋對弈的邏輯結構。

【例1-3】七橋問題。

位于俄羅斯境內的哥尼斯堡有一條小河叫勒格爾河，河有兩條支流，一條叫新河，一條叫老河，它們在市中心匯合，在合流的地方中間有一座小島，在小島和兩條支流上建有七座橋。于是哥尼斯堡可分為四塊陸地，四周均為河流，四塊陸地由七座橋相連。設四塊陸地分別為A、B、C、D，可以用圖1-2表示。

哥尼斯堡的居民有個傳統習慣，星期天沿著城市的河岸和小島散步，同時試圖找到一條可經過所有七座橋但又不重復經過任意一座橋的路線，這就是著名的“七橋問題”。1736年，正在哥尼斯堡的瑞士數學家歐拉對“七橋問題”產生了興趣。他化繁為簡，把四塊陸地和七座橋抽象為四個點和七條線組成的幾何圖形，如圖1-3所示，人們稱之為歐拉回路。

歐拉對“七橋問題”的結論是：“所有結點的度（一個結點擁有的邊數稱為度）均為偶數時，原問題才有解”。換言之，“七橋問題”永遠無解。在此，我們無意討論數學證明問題，而僅對圖1-3中每一個結點有多個直接前驅和多個直接后繼這樣一個結果產生興趣，即那些結點之間存在“多對多”的關系，稱之為圖。

綜上所述，非數值計算問題的數學模型不再是數學方程的問題，而是諸如上述的表（如例1-1）、樹（如例1-2）、圖（如例1-3）之類的數據結構。因此，簡單地說，數據結構是一門研究非數值計算的程序設計問題的學科，主要研究數據的邏輯結構、存儲結構和運算方法。

本章以下的三節就介紹這三方面的內容。