1.2.2 什么是數據結構

一般而言，利用計算機解決一個具體問題時，大致需要經過如下3個步驟：

①從具體問題抽象出一個合適的數學模型。

②設計一個可解此數學模型的算法。

③編寫程序，進行測試、調整，直到問題得以解決。

尋求數學模型的實質是分析問題，從中提取操作的對象，并找出這些操作對象之間的關系，然后用數學的語言加以描述。為了說明這個問題，此處首先舉一個例子，然后給出明確的含義。

例1-1　對于八皇后問題，不是根據某種確定的計算法則進行處理，而是利用試探和回溯的探索技術求解。為了求得合理布局，在計算機中要存儲布局的當前狀態。從最初的布局狀態開始，一步步地進行試探，每試探一步產生一個新的狀態，整個試探過程形成一棵隱含的狀態樹，如圖1-1所示（此處為了描述方便，將八皇后問題簡化為四皇后問題）。用回溯法求解的過程實質上就是一個遍歷狀態樹的過程。在這個問題中所出現的樹也是一種數據結構，它可以應用在許多非數值計算的問題中。

圖1-1　四皇后問題隱含狀態樹

由例1-1可以看出，描述這類非數值計算問題的數學模型不再是數學方程，而主要是線性表、樹、圖這類的數據結構。因此，可以說數據結構主要是研究非數值計算的程序設計問題中所出現的計算機操作對象以及它們之間的關系和操作的學科。