第1章 緒論

1.1 什么是數據結構

計算機的迅猛發展早已使其擺脫了單純的科學計算。而今各部門各個行業都有大量的計算機在從事著行政事務管理、生產作業調度和實時控制以及通信、教育等方面工作。近年來人工智能領域的研究成果更加提高了計算機的“智力”，使其在很多方面已能輔助人們或代替人們做出決策、診斷等具有專家性質的工作。

計算機的普及和發展，使人們要求計算機能處理的問題愈來愈多，愈來愈復雜，問題的規模愈來愈大。要使計算機發揮更大的作用，人們就必須設計出更好的程序來。要做到這一點，就應該掌握一系列程序設計知識，其中數據結構的知識是不可少的。因為人們著手處理問題時，必須分析該問題涉及到哪些數據，這些數據具有什么性質，數據之間有什么關系，采用什么方式存儲數據并體現出它們之間的關系，所涉及的問題又包含有哪些運算，可采用什么算法。這些正是數據結構這門學科所研究的內容。

一般來說，用計算機解決一個具體問題時，大致需要經過下列幾個步驟：首先要從具體問題中抽象出一個適當的數學模型，然后設計一個解此數學模型的算法，最后編寫出程序、進行測試、調整直至得到最終解答。尋求數學模型的實質是對問題的分析，即從問題中提取出操作對象并找出這些操作對象之間含有的關系，加以簡化、抽象后，用數學語言加以描述。例如，求解梁架結構中應力的數學模型為線性方程組；預報人口增長情況的數學模型為微分方程。然而，更多的非數值計算問題無法用數學方程加以描述，下面是三個例子。

例1.1 表1.1中列出的是某班級學生的基本情況表，表中每一行包含的信息有：學號、姓名、性別、出生日期、所在院系、政治面貌。對于這類文檔管理的數學模型，在計算機處理的對象之間通常存在一種最簡單的線性關系，這類數學模型可稱為線性模型。

表1.1 某班級學生基本情況表

例1.2 在迷宮問題中，計算機之所以能找到迷宮的出口，是因為人們已將搜索出口的策略事先存入計算機中。在迷宮中，每走到一處，接下來可走的通路有三條，如圖1.1所示。計算機處理的這類對象之間通常存在的關系不是線性關系。例如，若將從迷宮入口處到出口的過程中所有可能的通路都畫出，則可得到一棵倒長的“樹”。“樹根”是迷宮入口，“樹葉”是出口或死路。所以，“樹”可以是某些非數值計算問題的數學模型。

圖1.1 迷宮下一步的通路

例1.3 在一個由若干個城市組成的交通網中，現要將一些原有的公路修建成高速公路，使所有城市之間都有高速通道存在。這時，有多種方案可選擇，但若要考慮投入和效益，最佳的方案是在交通網中構造最小生成樹，即確定n-1條線路連通這n個城市，并且代價最小。這類交通、道路問題的數學模型是一種被稱為“圖”的數據結構。

綜上三個例子可見，描述這類非數值計算問題的數學模型不再是數學方程，而是諸如表、樹和圖之類的數據結構。因此，數據結構是一門研究非數值計算程序中數據對象及其關系和操作的學科。