問題 6 查找

查找(search)和插入(insert)這兩個普遍的操作不僅本身有直接的應(yīng)用，還是計算機(jī)中許多其他復(fù)雜操作和功能的基礎(chǔ)。重要性無需贅述。

查找和插入操作的問題描述很簡潔：

一個數(shù)據(jù)元素集合A={a1, a2, …?,an}和一個數(shù)據(jù)元素x，問x是否在A中。當(dāng)發(fā)現(xiàn)x不在A中的時候，如果需要，則把x放入A中。

這個問題值得研究，是因為提高查找和插入的效率太重要了。在計算機(jī)領(lǐng)域優(yōu)化查找和插入問題的求解方法，有兩條維度，不同的數(shù)據(jù)結(jié)構(gòu)（數(shù)據(jù)元素集合中數(shù)據(jù)存儲的方式）和優(yōu)化的查找和插入算法。

?

本章，書中給出了4個方面的討論

1.?無序元素列表上的查找和插入（用列表或數(shù)組存儲，線性查找、尾端插入）

2.?有序元素列表上的查找與插入（用列表或數(shù)組存儲，對分（折半）查找、有序插入）

3.?搜索二叉樹上的查找與插入（搜索二叉樹存儲）

4.?平衡二叉樹上的查找與插入（AVL存儲）

?

【作者感受】

查找和插入是數(shù)據(jù)結(jié)構(gòu)、算法課程的重點核心內(nèi)容之一。

如果想從專業(yè)的角度學(xué)習(xí)，還是建議直接看數(shù)據(jù)結(jié)構(gòu)或算法教材，收獲會更大，學(xué)習(xí)曲線不難。

如果想從科普的角度學(xué)習(xí)，個人覺得本書的趣味性（當(dāng)然這本書不是以趣味性這個角度來寫書的）或者說吸引度不夠，因為作者還是用專業(yè)術(shù)語在描述，對初學(xué)者有學(xué)習(xí)壁壘。

?

初學(xué)時，建議可以去聽聽一個好的講者來講查找，然后再自己學(xué)習(xí)，再次強(qiáng)調(diào)，學(xué)習(xí)查找和插入是很能訓(xùn)練計算思維的。我還記得，以前給非計算機(jī)專業(yè)的學(xué)生講計算機(jī)通識課時，只有一節(jié)課時間，用的就是查找問題，當(dāng)然講的會更加不專業(yè)一些，試圖有些趣味性，勾起學(xué)生的興趣，能夠促進(jìn)其主動取學(xué)習(xí)就好了。