目錄
想要學(xué)好一門科目，首先得從根本上了解這門科目是做什么的。為了讓我們之后數(shù)據(jù)結(jié)構(gòu)與算法知識學(xué)習(xí)的更加方便，在我們數(shù)據(jù)理論與算法課程開始之前，先來了解一下什么是數(shù)據(jù)結(jié)構(gòu)與算法。本次博客重于理論計(jì)算機(jī)算法基礎(chǔ)第三版怎么樣，對于數(shù)據(jù)結(jié)構(gòu)與算法有一定基礎(chǔ)的伙伴們可以忽略，直接跳到下一篇博客進(jìn)行閱讀。那么閑話少說，就讓我們開始本次博客的內(nèi)容。
什么是數(shù)據(jù)結(jié)構(gòu)？
官方一點(diǎn)的回答是：數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲、組織數(shù)據(jù)的方式。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)反映數(shù)據(jù)的內(nèi)部構(gòu)成，即數(shù)據(jù)由那部分構(gòu)成，以什么方式構(gòu)成，以及數(shù)據(jù)元素之間呈現(xiàn)的結(jié)構(gòu)。但是這樣并不容易理解，所以我們只需要閱讀過后有大致的印象即可。下面我們來用我們自己的方式解釋數(shù)據(jù)結(jié)構(gòu)。
通俗一點(diǎn)來說呢，數(shù)據(jù)結(jié)構(gòu)并不單單是字面上的意思，一個數(shù)據(jù)的結(jié)構(gòu)？不計(jì)算機(jī)算法基礎(chǔ)第三版怎么樣，數(shù)據(jù)結(jié)構(gòu)其實(shí)指的是三部分。這三部分依次是
數(shù)據(jù)的邏輯結(jié)構(gòu)
數(shù)據(jù)的運(yùn)算
數(shù)據(jù)的物理結(jié)構(gòu)
下面我們就通過對這三點(diǎn)進(jìn)行說明，是我們對數(shù)據(jù)結(jié)構(gòu)獲得初步的了解和認(rèn)知。
1.數(shù)據(jù)的邏輯結(jié)構(gòu)
數(shù)據(jù)的邏輯結(jié)構(gòu)通俗來說就是數(shù)據(jù)元素之間的邏輯關(guān)系。主要可以分為一下三類：
NUM 1 : 集合 NUM 2 : 線性結(jié)構(gòu) NUM 2 : 樹形結(jié)構(gòu) NUM 4 :圖結(jié)構(gòu)（網(wǎng)狀結(jié)構(gòu)）
簡單一點(diǎn)來說我們的邏輯結(jié)構(gòu)就是我們對于數(shù)據(jù)在認(rèn)知上的結(jié)構(gòu)。據(jù)以一個例子：在排隊(duì)的時候我們自覺排成一隊(duì)，形狀成一條直線的模樣，假如把我們每一個人看成是一個數(shù)據(jù)，那么我們就可以說我們的邏輯結(jié)構(gòu)就是線性結(jié)構(gòu)。或者說：我們在一個學(xué)校里面上學(xué)，假如學(xué)校和學(xué)生都看成是不同的數(shù)據(jù)的話，那么學(xué)校和學(xué)生的邏輯關(guān)系就是集合。我們先對于這部分知識有一個預(yù)先的了解，在后面的學(xué)習(xí)中我們會對這些結(jié)構(gòu)有更加深入的理解。
接下來我們的在來認(rèn)識一下數(shù)據(jù)的物理結(jié)構(gòu)。
2.數(shù)據(jù)的物理結(jié)構(gòu)
數(shù)據(jù)的物理結(jié)構(gòu)實(shí)質(zhì)上就是數(shù)據(jù)在內(nèi)存中真實(shí)存儲的結(jié)構(gòu)。主要也是四種：
順序存儲 鏈?zhǔn)酱鎯? 索引存儲 散列存儲 順序存儲
所謂的順序存儲就是把邏輯上相鄰的元素存儲在物理位置也相鄰的存儲單元中。再利用我們上面排隊(duì)的例子進(jìn)行分析：我們排隊(duì)的邏輯結(jié)構(gòu)已經(jīng)知道了是線性結(jié)構(gòu)了，可是我們要從哪里站到哪里呢？通常情況下我們不同的窗口都會有不同的站隊(duì)區(qū)域就比如：
像是這樣邏輯結(jié)構(gòu)上為線性結(jié)構(gòu)，實(shí)際上的存儲形式也是連續(xù)的相鄰的存儲形式就叫做順序存儲。（將KFC 門前劃定的特定的排隊(duì)道路類比于在內(nèi)存中存儲的內(nèi)存位置。）
鏈?zhǔn)酱鎯?/p>
在介紹完我們的順序存儲之后我們再來看一看我們的鏈?zhǔn)酱鎯?。所謂的鏈?zhǔn)酱鎯褪沁壿嬌舷噜彽脑卮鎯υ谖锢砦恢蒙峡梢圆幌噜彽?，但是借助于我們的指針就可以找到我們的下一個元素的位置的存儲形式就就叫做鏈?zhǔn)酱鎯ΑＭǔＮ覀兊逆準(zhǔn)酱鎯梢詳U(kuò)大；零散內(nèi)存的利用效率。就比如：
我們可以像圖一的形式一樣將我們的數(shù)據(jù)連續(xù)保存在空閑的地址上，也可以像是圖二的形式一樣將我們的數(shù)據(jù)亂序存儲在空閑的地址上，我們都可以很容易的將我們的數(shù)據(jù)還原成有序的數(shù)據(jù)列表。這是因?yàn)槲覀冊趦?nèi)存中存儲的數(shù)據(jù)這部分中并不只包含了現(xiàn)實(shí)生活中的數(shù)據(jù)還包括了下一個數(shù)據(jù)的指針。形式如下圖所示：
所以我們就可以通過數(shù)據(jù)中包含的下一個數(shù)據(jù)的指針找到下一個數(shù)據(jù)，進(jìn)而便于還原。我們的存儲形式就形式有一條無形的鎖鏈將我們的數(shù)據(jù)串聯(lián)起來，所以這種存儲形式就叫做鏈?zhǔn)酱鎯Α?/p>
索引存儲
上面就是我們的鏈?zhǔn)酱鎯Φ男问剑酉聛硪榻B的就是我們的索引存儲了。要是我們大家學(xué)習(xí)過計(jì)算機(jī)網(wǎng)絡(luò)相關(guān)的知識的話我們就會對索引存儲比較熟悉。像是我們的路由表就是我們索引存儲的一種表現(xiàn)形式。索引存儲的主要形式如下：
像是上面的表格的形式一樣，我們的索引存儲就是在存儲數(shù)據(jù)的同時存儲一張可以記錄各部分?jǐn)?shù)據(jù)的表格，那樣的話我們對比表格同樣可以很快的查找到指定的數(shù)據(jù)，并將數(shù)據(jù)按順序還原。
散列存儲
最后一點(diǎn)就是我們的散列存儲的存儲方式了，我們的散列存儲表示可以根據(jù)關(guān)鍵字直接計(jì)算出該元素的存儲地址，又稱為哈希存儲，但是這一類存儲并不是簡單的三言兩語就能解釋的所以我們暫時只需要有一個印象即可。到后面我們會進(jìn)行專題講解。
Tips：
數(shù)據(jù)的存儲結(jié)構(gòu)不同會影響存儲空間的分配的方便程度。簡單一點(diǎn)來舉一個例子：假如我們已經(jīng)排好的隊(duì)伍（順序存儲）要是想要插入一個人的話就得然后面的人一次向后移動，這就會很不方便。但是我們要是采用的是鏈?zhǔn)酱鎯Φ脑捑涂梢噪S便找一個位置把指針交給指定的元素即可。
數(shù)據(jù)的存儲結(jié)構(gòu)會影響對數(shù)據(jù)的運(yùn)算的速度。就比如我們要是想找到第三個元素我們的順序存儲只需要查找位置為3的元素即可，但是我們要是使用的是索引存儲的話我們要想找到第三個元素就要從第一個元素開始查找，先找到第一個元素之后在進(jìn)行一系列的查找，1->2->3......
總之順序存儲（物理上是連續(xù)的存儲方式）和非順序存儲（物理上是離散的存儲方式）都各有利弊，我們需要在不同的情況下選擇合適的存儲方式進(jìn)行數(shù)據(jù)的存儲以達(dá)到最優(yōu)的效果。
3.數(shù)據(jù)的運(yùn)算
接著我們就來到了我們的數(shù)據(jù)的運(yùn)算的理解環(huán)節(jié)：數(shù)據(jù)的運(yùn)算主要包括兩部分：1.運(yùn)算的定義 2.運(yùn)算的實(shí)現(xiàn)
運(yùn)算的定義是針對邏輯結(jié)構(gòu)的，指運(yùn)算的功能。舉一個例子來便于理解：我們一共有十個人進(jìn)行排隊(duì)，每一個人都要買一個漢堡，一個漢堡十塊錢，每一個顧客買完漢堡店家的收入是多少？這一個例子表達(dá)的就是我們運(yùn)算的定義——我們運(yùn)算的功能是計(jì)算出店家每賣出一個漢堡所獲得的錢的數(shù)量。
之后我們來看一下運(yùn)算的實(shí)現(xiàn)：運(yùn)算的實(shí)現(xiàn)是針對數(shù)據(jù)的存儲結(jié)構(gòu)的，指出運(yùn)算的具體操作。我們依然運(yùn)用上面的例子來進(jìn)行理解：我們可以把上面每個顧客給的錢的數(shù)量都當(dāng)作一個數(shù)據(jù)，我們的存儲結(jié)構(gòu)不同那么所要實(shí)現(xiàn)的運(yùn)算也就不一樣，比如：我們用的是順序存儲，那么我們就需要按順序?qū)⒅颠M(jìn)行相加，直接求和。如果我們的鏈?zhǔn)酱鎯Ψ绞轿覀円龅木褪窍日业矫總€元素的位置，然后再將它們相加，得到的才是我們想要的結(jié)果。
以上就是我們的數(shù)據(jù)結(jié)構(gòu)的具體的三個要素，那么我們對數(shù)據(jù)結(jié)構(gòu)的初步認(rèn)識過程也就結(jié)束了，接下來就讓我們進(jìn)入我們對算法的初步認(rèn)識。
什么是算法？
相信學(xué)計(jì)算機(jī)的大家經(jīng)常會聽到這個算法怎么怎樣，那個算法怎么怎么樣的，但是要是被問到算法究竟是一個什么東西呢？也說不出一個所以然來，那么我們現(xiàn)在就來給大家介紹一下到底什么才是算法。
算法其實(shí)值得并不是一個程序的編碼，而是一個過程。算法其實(shí)指的是我們編寫代碼將我們數(shù)據(jù)結(jié)構(gòu)中所轉(zhuǎn)化的信息問題加以解決的過程。我們上面介紹到的數(shù)據(jù)結(jié)構(gòu)主要的作用就是將具體的場景轉(zhuǎn)化成數(shù)據(jù)信息并存儲在內(nèi)存中的過程，而我們的算法的作用就是將我們數(shù)據(jù)結(jié)構(gòu)中所得到的信息按照一定的程序進(jìn)行解決，所以我們的數(shù)據(jù)結(jié)構(gòu)才經(jīng)常和我們的算法聯(lián)系起來。
作為我們數(shù)據(jù)結(jié)構(gòu)與算法專題的第一次博客我們也肯定不能只是簡單的介紹一下算法的概念就不了了之，我們再來初步認(rèn)識一下算法的特性有哪些。
算法的特性 1.有窮性
一個算法必須在執(zhí)行又窮步驟之后結(jié)束，且每一步都可以在有窮的時間內(nèi)結(jié)束。要不然我們也得不到結(jié)果，那樣我們還要這個算法做什么呢？雖然算法是有窮的但是我們的程序可以是無窮的。我們的程序是由我們的算法組成的，每一個算法對應(yīng)著解決我們的一個問題，也就是說我們問題的解決時間必須是有限的但是我們問題的數(shù)量可以是無限的（程序的運(yùn)行時長）。
2.確定性
在算法中每一條指令必須有確切的含義，相對應(yīng)的輸入只能的到相同的輸出。簡單的來說就是我們對相同的實(shí)踐利用同一個算法的得到的結(jié)果應(yīng)該是相同的，只有這樣我們的運(yùn)算步驟才有意義。不知道大家看過三體沒有，里面的智子不就是改變我們的實(shí)驗(yàn)結(jié)果使我們相同的算法實(shí)驗(yàn)會的到不同的實(shí)驗(yàn)現(xiàn)象，進(jìn)而干擾我們的經(jīng)驗(yàn)總結(jié)的嗎？所以我們要記住，我們的唯一的算法對于相同的輸入只能有一組輸出與之對應(yīng)，這就是我們算法中的確定性。
3.可行性
這一點(diǎn)的理解和我們上面的有窮性比較像。指的是我們算法中描述的操作都可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)。換成我們的編程語言來理解就是說我們使用的內(nèi)容必須在之前已經(jīng)實(shí)現(xiàn)過了，比如我們要想使用一個Add函數(shù)，那么我們就一定要在使用之前就已經(jīng)將這個函數(shù)實(shí)現(xiàn)完畢了。這樣我們整個程序才能夠正常運(yùn)行。
4.輸入
一個算法可以有零個或者多個輸入，這些輸入取自某個特定的條件。這一點(diǎn)很好理解，我們編寫的算法程序可以從鍵盤輸入也可以直接打印一些值就體現(xiàn)了我們的輸入的原理。
5.輸出
一個算法至少有一個或者多組輸出，這些輸出是與輸入有著某種特定的關(guān)系的值。這點(diǎn)我們也很容易理解：我們的程序的編寫的價(jià)值就是的到一定的答案，假如沒有輸出我們就不會有答案，我們的程序的運(yùn)行也就沒有意義。
最后我們來了解一下一個好的算法所應(yīng)該擁有的特性：
1.正確性
我們的算法程序當(dāng)然是為了解決問題而產(chǎn)生的，所以我們的算法應(yīng)該能夠正確的解決問題才行。
2.可讀性
一個優(yōu)秀的算法應(yīng)該具有良好的可讀性，以幫助他人閱讀理解代碼。
3.健壯性
當(dāng)我們向代碼中輸入一個非法的數(shù)據(jù)時，一個好的算法應(yīng)該具有識別并改正錯誤數(shù)據(jù)的能力，即一個好的算法應(yīng)該具有一定的容錯能力，不會產(chǎn)生莫名其妙的結(jié)果。
4.高效率與低儲量需求
這里說的高效率與低存儲需求所想表達(dá)的意思就是一個好的算法應(yīng)該具有較小的時間復(fù)雜度與空間復(fù)雜度。同樣能解決問題的程序，運(yùn)行所花費(fèi)的時間較少，所占內(nèi)存的大小較小的算法相對較好。
經(jīng)過上面的介紹之后相信大家已經(jīng)對數(shù)據(jù)結(jié)構(gòu)與算法具有了一定的理解，我們本次的博客也就到此為止了。希望對你來說有幫助，感謝您的觀看，祝您天天開心。
