一吧享、數(shù)據(jù)結(jié)構(gòu)
1、概述
數(shù)據(jù)結(jié)構(gòu)是是帶有結(jié)構(gòu)特性的數(shù)據(jù)元素的集合廊勃。
數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合,即帶“結(jié)構(gòu)”的數(shù)據(jù)元素的集合演顾」┎螅“結(jié)構(gòu)”就是指數(shù)據(jù)元素之間存在的關(guān)系,分為邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)钠至。
數(shù)據(jù)結(jié)構(gòu)中最基本的五個(gè)概念:數(shù)據(jù),數(shù)據(jù)元素,數(shù)據(jù)項(xiàng),數(shù)據(jù)對(duì)象,數(shù)據(jù)結(jié)構(gòu);
1.1數(shù)據(jù):
是描述客觀事物的符號(hào)葛虐,是計(jì)算機(jī)中可以操作的對(duì)象,是能被計(jì)算機(jī)識(shí)別棉钧,并輸入給計(jì)算機(jī)處理的符號(hào)集合屿脐。
1.2數(shù)據(jù)元素:
是組成數(shù)據(jù)的,且有一定意義的基本單位,在計(jì)算機(jī)中通常作為整體處理. 也被稱作"記錄"
1.3數(shù)據(jù)項(xiàng)
?一個(gè)數(shù)據(jù)元素可以由若干數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)不可分割的最小單位
1.4數(shù)據(jù)對(duì)象
是性質(zhì)相同的數(shù)據(jù)元素的集合,是數(shù)據(jù)的子集.
1.5數(shù)據(jù)結(jié)構(gòu)
結(jié)構(gòu),簡(jiǎn)單理解就是關(guān)系. 比如分子結(jié)構(gòu),就是說組成分子原子的排列方式. 不同數(shù)據(jù)元素之間不是獨(dú)立的,而是存在特定的關(guān)系.我們將這些關(guān)系成為結(jié)構(gòu). 那么數(shù)據(jù)結(jié)構(gòu)是什么? 數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合.
2、邏輯結(jié)構(gòu)和物理結(jié)構(gòu):
數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的兩個(gè)密切相關(guān)的方面的诵,同一邏輯結(jié)構(gòu)可以對(duì)應(yīng)不同的存儲(chǔ)結(jié)構(gòu)万栅。算法的設(shè)計(jì)取決于數(shù)據(jù)的邏輯結(jié)構(gòu),而算法的實(shí)現(xiàn)依賴于指定的存儲(chǔ)結(jié)構(gòu)西疤。
數(shù)據(jù)的邏輯結(jié)構(gòu):
指反應(yīng)數(shù)據(jù)元素之間的邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)烦粒,其中的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素之間的前后關(guān)系,而與他們?cè)谟?jì)算機(jī)中的存儲(chǔ)位置無關(guān)代赁。邏輯結(jié)構(gòu)包括:
1扰她、集合:數(shù)據(jù)結(jié)構(gòu)中的元素之間除了“同屬一個(gè)集合” 的相互關(guān)系外,別無其他關(guān)系芭碍;
2徒役、線性結(jié)構(gòu):數(shù)據(jù)結(jié)構(gòu)中的元素存在一對(duì)一的相互關(guān)系;(例如:線性表窖壕,棧忧勿,隊(duì)列等)
3、樹形結(jié)構(gòu):數(shù)據(jù)結(jié)構(gòu)中的元素存在一對(duì)多的相互關(guān)系瞻讽;(例如:二叉樹鸳吸,哈夫曼樹等)
4、圖形結(jié)構(gòu):數(shù)據(jù)結(jié)構(gòu)中的元素存在多對(duì)多的相互關(guān)系卸夕。(例如:鄰接矩陣)
數(shù)據(jù)的物理結(jié)構(gòu):
指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間的存放形式
通常包括:順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
設(shè)計(jì)好邏輯數(shù)據(jù)結(jié)構(gòu)之后,數(shù)據(jù)的存儲(chǔ)也是非常重要的.?數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)應(yīng)該正確反映數(shù)據(jù)元素之間的邏輯關(guān)系.這才是關(guān)鍵! 如何存儲(chǔ)數(shù)據(jù)元素之間的邏輯關(guān)系,是實(shí)現(xiàn)物理結(jié)構(gòu)的重點(diǎn)和難點(diǎn).
抽象數(shù)據(jù)類型:
1.1數(shù)據(jù)類型
在C語言中,按照取值不同,數(shù)據(jù)類型可以分為2類:
原子類型: 是不可以在分解的基本數(shù)據(jù)類型,包含整型,浮點(diǎn)型,字符型等;
結(jié)構(gòu)類型: 由若干類型組合而成,是可以再分解的.例如,整型數(shù)組就是由若干整型數(shù)據(jù)組成的.
1.2抽象數(shù)據(jù)類型
是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作; 例如,我們?cè)诰帉懹?jì)算機(jī)繪圖軟件系統(tǒng)時(shí),經(jīng)常會(huì)使用到坐標(biāo). 也就是說,會(huì)經(jīng)常使用x,y來描述橫縱坐標(biāo). 而在3D系統(tǒng)中,Z深度就會(huì)出現(xiàn). 既然這3個(gè)整型數(shù)字是始終出現(xiàn)在一起. 那就可以定義成一個(gè)Point的抽象數(shù)據(jù)類型. 它有x,y,z三個(gè)整型變量. 這樣開發(fā)者就非常方便操作Point 數(shù)據(jù)變量.
二层释、算法
1、什么是算法快集?
算法是指解題方案的準(zhǔn)確而完整的描述,在計(jì)算機(jī)中表現(xiàn)為指令的有限序列列,并且每個(gè)指令表示?一個(gè)或多個(gè)操作廉白。
2个初、算法的特性
1、輸入輸出
2猴蹂、有窮性
3院溺、確定性
4、可行性
5磅轻、正確性
6珍逸、可讀性
7、健壯性
8聋溜、事件效率高和存儲(chǔ)量低
3谆膳、算法的評(píng)估
同一個(gè)問題可用不同的算法解決,而不同的算法撮躁,也可能可以解決多個(gè)問題漱病。而一個(gè)算法的質(zhì)量?jī)?yōu)劣將影響到算法乃至程序的效率問題。我們對(duì)算法的分析的目的就是選擇合適算法和改進(jìn)算法。
一個(gè)算法的評(píng)價(jià)主要從時(shí)間復(fù)雜度和空間復(fù)雜度來考慮
時(shí)間復(fù)雜度:
指算法需要的計(jì)算工作量杨帽,通常我們所遇見的時(shí)間復(fù)雜度包括:
其中:O(1) < O(log n) < O(n) < O(nlog n) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)
空間復(fù)雜度:
算法的空間復(fù)雜度是指算法需要消耗的內(nèi)存空間
通過計(jì)算算法所需的存儲(chǔ)空間實(shí)現(xiàn),算法空間復(fù)雜度的計(jì)算公式記做: S(n) = n(f(n)),其中,n為問題的規(guī)模,f(n)為語句句關(guān)于n所占存儲(chǔ)空間的函數(shù)
算法就簡(jiǎn)單介紹到這里漓穿!
轉(zhuǎn)載至:
https://juejin.im/post/5d6a2fa85188255eef1a7199
https://baike.baidu.com/item/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/1450?fr=aladdin