1.2.2 什么是數(shù)據(jù)結(jié)構(gòu)

一般而言，利用計(jì)算機(jī)解決一個(gè)具體問題時(shí)，大致需要經(jīng)過如下3個(gè)步驟：

①從具體問題抽象出一個(gè)合適的數(shù)學(xué)模型。

②設(shè)計(jì)一個(gè)可解此數(shù)學(xué)模型的算法。

③編寫程序，進(jìn)行測試、調(diào)整，直到問題得以解決。

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

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

圖1-1　四皇后問題隱含狀態(tài)樹

由例1-1可以看出，描述這類非數(shù)值計(jì)算問題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而主要是線性表、樹、圖這類的數(shù)據(jù)結(jié)構(gòu)。因此，可以說數(shù)據(jù)結(jié)構(gòu)主要是研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中所出現(xiàn)的計(jì)算機(jī)操作對象以及它們之間的關(guān)系和操作的學(xué)科。