? ? ? 結(jié)構(gòu)化的算法概況
結(jié)構(gòu)化算法是由一些基本結(jié)構(gòu)順序組成的,就是把一個(gè)大的功能的實(shí)現(xiàn)分隔為許多個(gè)小功能的實(shí)現(xiàn)。在基本結(jié)構(gòu)之間不存在向前或向后的跳轉(zhuǎn),流程的轉(zhuǎn)移只存在于一個(gè)基本的結(jié)構(gòu)范圍內(nèi)。一個(gè)非結(jié)構(gòu)化的算法可以用一個(gè)等價(jià)的結(jié)構(gòu)化算法代替,其功能不變。這樣的好處是可以將復(fù)雜問(wèn)題簡(jiǎn)單化,讓編程更容易,提高代碼維護(hù)和可讀性。
跟結(jié)構(gòu)化算法比較起來(lái),非結(jié)構(gòu)化算法有以下缺點(diǎn)。
流程不受限制的隨意轉(zhuǎn)來(lái)轉(zhuǎn)去,使流程圖豪無(wú)規(guī)律。使人在閱讀的時(shí)候難以理解算法的邏輯。難以閱讀,也難以修改。從而使算法的可靠性和可維護(hù)性難以保證。
?
算法和結(jié)構(gòu)化數(shù)據(jù)初識(shí)
數(shù)據(jù)結(jié)構(gòu)定義:
我們?nèi)绾伟熏F(xiàn)實(shí)中大量而復(fù)雜的問(wèn)題以特定的數(shù)據(jù)類型和特定的存儲(chǔ)結(jié)構(gòu)保存到主存儲(chǔ)器(內(nèi)存)中,以及在此基礎(chǔ)上為實(shí)現(xiàn)某個(gè)功能(如元素的CURD、排序等)而執(zhí)行的相應(yīng)操作,這個(gè)相應(yīng)的操作也叫算法。
數(shù)據(jù)結(jié)構(gòu) = 元素 + 元素的關(guān)系 ;算法 = 對(duì)數(shù)據(jù)結(jié)構(gòu)的操作;
算法:算法就是:解決問(wèn)題的方法和步驟;
如計(jì)算機(jī)內(nèi)存中棧和堆的區(qū)別,不懂?dāng)?shù)據(jù)結(jié)構(gòu)的人可能會(huì)認(rèn)為內(nèi)存就是分兩大部分,一塊叫棧,一塊叫堆,顯然這是非常膚淺且不正確的結(jié)論。
實(shí)際上如果一塊內(nèi)存是以壓棧出棧的方式分配的內(nèi)存,那么這塊內(nèi)存就叫棧內(nèi)存,如果是以堆排序的方式分配的內(nèi)存,那么這塊內(nèi)存就叫堆內(nèi)存,其最根本的區(qū)別還是其內(nèi)存分配算法的不同。
例如,函數(shù)的調(diào)用方式也是通過(guò)壓棧出棧的方式來(lái)調(diào)用的,或者操作系統(tǒng)中多線程操作有隊(duì)列的概念,隊(duì)列用于保證多線程的操作順序,這也是數(shù)據(jù)結(jié)構(gòu)里面的內(nèi)容、或者計(jì)算機(jī)編譯原理里面有語(yǔ)法樹(shù)的概念,這實(shí)際上就是數(shù)據(jù)結(jié)構(gòu)里面的樹(shù),比如軟件工程、數(shù)據(jù)庫(kù)之類都有數(shù)據(jù)結(jié)構(gòu)的影子。
在計(jì)算機(jī)系統(tǒng)中,CPU 可以直接操作內(nèi)存,關(guān)于 CPU 對(duì)內(nèi)存的操作與控制原理可以簡(jiǎn)單理解如下圖:
地址線 : 確定操作哪個(gè)地址單元
控制線 : 控制該數(shù)據(jù)單元的讀寫(xiě)屬性
數(shù)據(jù)線 : 傳輸 CPU 和內(nèi)存之間的數(shù)據(jù)
什么叫結(jié)構(gòu)體:結(jié)構(gòu)體是用戶根據(jù)實(shí)際需要,自己定義的復(fù)合數(shù)據(jù)類型
指針:
指針就是地址,地址就是指針。
指針變量是存放內(nèi)存單元地址的變量,它內(nèi)部保存的值是對(duì)應(yīng)的地址,地址就是內(nèi)存單元的編號(hào)(如內(nèi)存地址值:0xffc0)。
指針的本質(zhì)是一個(gè)操作受限的非負(fù)整數(shù)
引用Quora上的回答:
I see it time and again in Google interviews or new-grad hires: The way data structures and algorithms—among the most important subjects in a proper computer science curriculum—are learnt is often insufficient. That‘s not to say students read the wrong books (see my recommendation below) or professors teach the wrong material, but how students ultimately come to understand the subject is lacking.(我多次在google面試或者畢業(yè)招聘的時(shí)候看到這樣的情形:學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)和算法--CS課程里面幾乎最重要的課程--的方式很不科學(xué)!!到不是說(shuō)大家用的書(shū)或者老師用的材料不對(duì),而是說(shuō)學(xué)生們對(duì)于這些課程本身的理解非常缺乏。)
The key to a solid foundation in data structures and algorithms is not an exhaustive survey of every conceivable data structure and its subforms, with memorization of each’s Big-O value and amortized cost. Such knowledge is great and impressive if you‘ve got it, but you will rarely need it. For better or worse, your career will likely never require you to implement a red-black tree node removal algorithm. But you ought be able—with complete ease!—to identify when a binary search tree is a useful solution to a problem, because you will often need that skill.(打好數(shù)據(jù)結(jié)構(gòu)和算法基礎(chǔ)的關(guān)鍵并不在于對(duì)于所有數(shù)據(jù)結(jié)構(gòu)的細(xì)致的了解,不是記住每一個(gè)大O值或者攤余成本。. )。
如果這些知識(shí)你都掌握了,當(dāng)然很棒并且可以給人留下很深的印象,但是你基本上用不著啊!
你的職業(yè)生涯中或許永遠(yuǎn)都不會(huì)要求你實(shí)現(xiàn)一個(gè)紅黑樹(shù)刪除節(jié)點(diǎn)的算法。但是!你必須有能力而且手起刀落輕輕松松的識(shí)別出什么時(shí)候使用二叉樹(shù)更簡(jiǎn)單更有效, 因?yàn)槟闶中枰@樣的技巧。)
So stop trying to memorize everything. Instead, start with the basics and learn to do two things:
Visualize the data structure. Intuitively understand what the data structurelooks like, what it feels like to use it, and how it is structured both in the abstract and physically in your computer’s memory. This is the single most important thing you can do, and it is useful from the simplest queues and stacks up through the most complicated self-balancing tree. Draw it, visualize it in your head, whatever you need to do: Understand the structure intuitively.
Learn when and how to use different data structures and their algorithms in your own code. This is harder as a student, as the problem assignments you‘ll work through just won’t impart this knowledge. That‘s fine. Realize you won’t master data structures until you are working on a real-world problem and discover that a hash is the solution to your performance woes. But even as a student you should focus on learning not the minutia details but the practicalities: When do you want a hash? When do you want a tree? When is a min-heap the right solution?
(所以,不要試圖記住所有的東西。而是從基礎(chǔ)開(kāi)始,做兩件事:
第一件事。 把數(shù)據(jù)結(jié)構(gòu)圖形化,視覺(jué)化。(突然想起來(lái)我高中競(jìng)賽老師說(shuō)的一句話:數(shù)形結(jié)合千般好,一旦不做萬(wàn)事休啊! 就是要畫(huà)圖! )在直覺(jué)上感受一個(gè)數(shù)據(jù)結(jié)構(gòu)是什么樣子的。使用它是什么感覺(jué),抽象上和具體實(shí)現(xiàn)上是什么樣子的。這就是最重要的事情。并且無(wú)論是對(duì)于簡(jiǎn)單的隊(duì)列,棧還是天殺的平衡樹(shù)都很重要而且有效。把數(shù)據(jù)結(jié)構(gòu)畫(huà)出來(lái),在你的腦袋瓜里面就能想象出來(lái),總之,你需要做的就是,直觀的去了解這些數(shù)據(jù)結(jié)構(gòu)。
第二件事。學(xué)習(xí)什么時(shí)候用什么樣的數(shù)據(jù)結(jié)構(gòu)和算法。對(duì)于學(xué)生來(lái)說(shuō)這很難,而且你要做作業(yè)的時(shí)候老師也沒(méi)告訴你們這該怎么辦。不過(guò)沒(méi)關(guān)系。 你要認(rèn)識(shí)到當(dāng)你真正處理到現(xiàn)實(shí)問(wèn)題的時(shí)候或許你才能掌握某些數(shù)據(jù)結(jié)構(gòu),比如哈希表。但是即使是個(gè)學(xué)生,你也應(yīng)該知道數(shù)據(jù)結(jié)構(gòu)的實(shí)用性:什么時(shí)候你需要個(gè)哈希表,什么時(shí)候你需要個(gè)樹(shù),什么時(shí)候你需要個(gè)堆? 而不是一開(kāi)始就陷入到追求細(xì)節(jié)中去。)
One of the questions I ask in Google engineering interviews has a binary search tree as a potential solution (among others)。 Good candidates can arrive at the binary search tree as the right path in a few minutes, and then take 10-15 minutes working through the rest of the problem and the other roadblocks I toss out. But occasionally I get a candidate who intuitively understands trees and can visualize the problem I‘m presenting. They might stumble on the exact algorithmic complexity of some operation, but they can respond to roadblocks without pause because they can visualize the tree. They get it.
(我在google面試的時(shí)候,我經(jīng)常會(huì)問(wèn)一個(gè)可以由二叉樹(shù)搜索解決的問(wèn)題。 好的應(yīng)聘者可以幾分鐘內(nèi)就可以想到用二叉樹(shù)來(lái)解決,而且對(duì)于我的其他問(wèn)題也差不多10-15分鐘就可以解決。當(dāng)然,偶爾會(huì)有一個(gè)應(yīng)聘者,他能直觀的認(rèn)識(shí)樹(shù)這種結(jié)構(gòu),而且可以把我的問(wèn)題形象化,圖形化的描述出來(lái)。當(dāng)然他或許對(duì)于某些操作的時(shí)間復(fù)雜度不甚了解,但是對(duì)于問(wèn)題他卻可以立馬回應(yīng),因?yàn)樗麄兡X袋里就有這樣的樹(shù)結(jié)構(gòu)啊,所以他也能拿到工作啊。)
As for a book, there is but one: Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein, otherwise known as CLRS.
至于書(shū),只推薦一本--- 《算法導(dǎo)論》
If you want another text, perhaps one with more examples in a specific language, I recommend Robert Sedgewick’s Algorithms in C++ orAlgorithms in Java, as appropriate. I prefer CLRS as a text, but you might find these a better teaching aid.
對(duì)于某個(gè)數(shù)據(jù)結(jié)構(gòu),幾步:
1、理解該數(shù)據(jù)結(jié)構(gòu)的基本概念(定義、實(shí)現(xiàn))
2、嘗試?yán)斫膺@個(gè)數(shù)據(jù)結(jié)構(gòu)的意義(為什么它會(huì)被發(fā)明)
3、用這種數(shù)據(jù)結(jié)構(gòu)解決一些對(duì)應(yīng)的例題(書(shū)本上的習(xí)題、Online Judge上的水題)
4、嘗試用這個(gè)數(shù)據(jù)結(jié)構(gòu)解決一些以往你用別的數(shù)據(jù)結(jié)構(gòu)解決的問(wèn)題,能否解決,為什么。
5、再次嘗試?yán)斫膺@個(gè)數(shù)據(jù)結(jié)構(gòu)的意義
6、嘗試改變這個(gè)數(shù)據(jù)結(jié)構(gòu)以應(yīng)對(duì)各種現(xiàn)實(shí)的問(wèn)題(Online Judge的好題)
7、學(xué)好數(shù)學(xué),別數(shù)都不會(huì)數(shù)。
初級(jí)篇
記住都有哪些算法,解決什么問(wèn)題
去試圖解決實(shí)際的問(wèn)題,自然會(huì)碰到之前算法解決的問(wèn)題,使用這些算法
中極篇
先完成初級(jí)篇
記住算法的具體解決辦法
實(shí)際的問(wèn)題 如果有與標(biāo)準(zhǔn)算法相似但是不完全一樣的,仔細(xì)分析差別,修改原有算法
高級(jí)篇
先完成中極篇
分析一下算法的解決辦法是如何才能想到,最核心和最精妙的地方在哪兒
實(shí)際的問(wèn)題如果與標(biāo)準(zhǔn)算法都不太象,仔細(xì)想想這個(gè)問(wèn)題的本質(zhì),借鑒經(jīng)典算法精妙之處,自己設(shè)計(jì)自己要用的算法
骨灰篇
先完成高級(jí)篇
忘掉所有算法
解決實(shí)際問(wèn)題
評(píng)論