數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)知識(shí)總結(jié)_第1頁(yè)
數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)知識(shí)總結(jié)_第2頁(yè)
數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)知識(shí)總結(jié)_第3頁(yè)
數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)知識(shí)總結(jié)_第4頁(yè)
數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)知識(shí)總結(jié)_第5頁(yè)
已閱讀5頁(yè),還剩12頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)知識(shí)總結(jié)數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)知識(shí)總結(jié)數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)知識(shí)總結(jié)xxx公司數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)知識(shí)總結(jié)文件編號(hào):文件日期:修訂次數(shù):第1.0次更改批準(zhǔn)審核制定方案設(shè)計(jì),管理制度數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)知識(shí)總結(jié)1算法

算法:是指解題方案的準(zhǔn)確而完整的描述。

算法不等于程序,也不等計(jì)算機(jī)方法,程序的編制不可能優(yōu)于算法的設(shè)計(jì)。

算法的基本特征:是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則,每一個(gè)規(guī)則都是有效的,是明確的,此順序?qū)⒃谟邢薜拇螖?shù)下終止。特征包括:

(1)可行性;

(2)確定性,算法中每一步驟都必須有明確定義,不充許有模棱兩可的解釋?zhuān)辉试S有多義性;

(3)有窮性,算法必須能在有限的時(shí)間內(nèi)做完,即能在執(zhí)行有限個(gè)步驟后終止,包括合理的執(zhí)行時(shí)間的含義;

(4)擁有足夠的情報(bào)。

算法的基本要素:一是對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作;二是算法的控制結(jié)構(gòu)。

指令系統(tǒng):一個(gè)計(jì)算機(jī)系統(tǒng)能執(zhí)行的所有指令的集合。

基本運(yùn)算和操作包括:算術(shù)運(yùn)算、邏輯運(yùn)算、關(guān)系運(yùn)算、數(shù)據(jù)傳輸。

算法的控制結(jié)構(gòu):順序結(jié)構(gòu)、選擇結(jié)構(gòu)、循環(huán)結(jié)構(gòu)。

算法基本設(shè)計(jì)方法:列舉法、歸納法、遞推、遞歸、減斗遞推技術(shù)、回溯法。

算法復(fù)雜度:算法時(shí)間復(fù)雜度和算法空間復(fù)雜度。

算法時(shí)間復(fù)雜度是指執(zhí)行算法所需要的計(jì)算工作量。

算法空間復(fù)雜度是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。

2數(shù)據(jù)結(jié)構(gòu)的基本基本概念

數(shù)據(jù)結(jié)構(gòu)研究的三個(gè)方面:

(1)數(shù)據(jù)集合中各數(shù)據(jù)元素之間所固有的邏輯關(guān)系,即數(shù)據(jù)的邏輯結(jié)構(gòu);

(2)在對(duì)數(shù)據(jù)進(jìn)行處理時(shí),各數(shù)據(jù)元素在計(jì)算機(jī)中的存儲(chǔ)關(guān)系,即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu);

(3)對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。

數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。

數(shù)據(jù)的邏輯結(jié)構(gòu)包含:

(1)表示數(shù)據(jù)元素的信息;

(2)表示各數(shù)據(jù)元素之間的前后件關(guān)系。

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)有順序、鏈接、索引等。

線(xiàn)性結(jié)構(gòu)條件:

(1)有且只有一個(gè)根結(jié)點(diǎn);

(2)每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件,也最多有一個(gè)后件。

非線(xiàn)性結(jié)構(gòu):不滿(mǎn)足線(xiàn)性結(jié)構(gòu)條件的數(shù)據(jù)結(jié)構(gòu)。

3線(xiàn)性表及其順序存儲(chǔ)結(jié)構(gòu)

線(xiàn)性表由一組數(shù)據(jù)元素構(gòu)成,數(shù)據(jù)元素的位置只取決于自己的序號(hào),元素之間的相對(duì)位置是線(xiàn)性的。

在復(fù)雜線(xiàn)性表中,由若干項(xiàng)數(shù)據(jù)元素組成的數(shù)據(jù)元素稱(chēng)為記錄,而由多個(gè)記錄構(gòu)成的線(xiàn)性表又稱(chēng)為文件。

非空線(xiàn)性表的結(jié)構(gòu)特征:

(1)且只有一個(gè)根結(jié)點(diǎn)a1,它無(wú)前件;

(2)有且只有一個(gè)終端結(jié)點(diǎn)an,它無(wú)后件;

(3)除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外,其他所有結(jié)點(diǎn)有且只有一個(gè)前件,也有且只有一個(gè)后件。結(jié)點(diǎn)個(gè)數(shù)n稱(chēng)為線(xiàn)性表的長(zhǎng)度,當(dāng)n=0時(shí),稱(chēng)為空表。

線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)具有以下兩個(gè)基本特點(diǎn):

(1)線(xiàn)性表中所有元素的所占的存儲(chǔ)空間是連續(xù)的;

(2)線(xiàn)性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。

ai的存儲(chǔ)地址為:adr(ai)=adr(a1)+(i-1)k,,adr(a1)為第一個(gè)元素的地址,k代表每個(gè)元素占的字節(jié)數(shù)。

順序表的運(yùn)算:插入、刪除。(詳見(jiàn)14--16頁(yè))

4棧和隊(duì)列

棧是限定在一端進(jìn)行插入與刪除的線(xiàn)性表,允許插入與刪除的一端稱(chēng)為棧頂,不允許插入與刪除的另一端稱(chēng)為棧底。

棧按照“先進(jìn)后出”(filo)或“后進(jìn)先出”(lifo)組織數(shù)據(jù),棧具有記憶作用。用top表示棧頂位置,用bottom表示棧底。

棧的基本運(yùn)算:(1)插入元素稱(chēng)為入棧運(yùn)算;(2)刪除元素稱(chēng)為退棧運(yùn)算;(3)讀棧頂元素是將棧頂元素賦給一個(gè)指定的變量,此時(shí)指針無(wú)變化。

隊(duì)列是指允許在一端(隊(duì)尾)進(jìn)入插入,而在另一端(隊(duì)頭)進(jìn)行刪除的線(xiàn)性表。rear指針指向隊(duì)尾,front指針指向隊(duì)頭。

隊(duì)列是“先進(jìn)行出”(fifo)或“后進(jìn)后出”(lilo)的線(xiàn)性表。

隊(duì)列運(yùn)算包括(1)入隊(duì)運(yùn)算:從隊(duì)尾插入一個(gè)元素;(2)退隊(duì)運(yùn)算:從隊(duì)頭刪除一個(gè)元素。

循環(huán)隊(duì)列:s=0表示隊(duì)列空,s=1且front=rear表示隊(duì)列滿(mǎn)

5線(xiàn)性鏈表

數(shù)據(jù)結(jié)構(gòu)中的每一個(gè)結(jié)點(diǎn)對(duì)應(yīng)于一個(gè)存儲(chǔ)單元,這種存儲(chǔ)單元稱(chēng)為存儲(chǔ)結(jié)點(diǎn),簡(jiǎn)稱(chēng)結(jié)點(diǎn)。

結(jié)點(diǎn)由兩部分組成:(1)用于存儲(chǔ)數(shù)據(jù)元素值,稱(chēng)為數(shù)據(jù)域;(2)用于存放指針,稱(chēng)為指針域,用于指向前一個(gè)或后一個(gè)結(jié)點(diǎn)。

在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中,存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)空間可以不連續(xù),各數(shù)據(jù)結(jié)點(diǎn)的存儲(chǔ)順序與數(shù)據(jù)元素之間的邏輯關(guān)系可以不一致,而數(shù)據(jù)元素之間的邏輯關(guān)系是由指針域來(lái)確定的。

鏈?zhǔn)酱鎯?chǔ)方式即可用于表示線(xiàn)性結(jié)構(gòu),也可用于表示非線(xiàn)性結(jié)構(gòu)。

線(xiàn)性鏈表,head稱(chēng)為頭指針,head=null(或0)稱(chēng)為空表,如果是兩指針:左指針(llink)指向前件結(jié)點(diǎn),右指針(rlink)指向后件結(jié)點(diǎn)。

線(xiàn)性鏈表的基本運(yùn)算:查找、插入、刪除。

6樹(shù)與二叉樹(shù)

樹(shù)是一種簡(jiǎn)單的非線(xiàn)性結(jié)構(gòu),所有元素之間具有明顯的層次特性。

在樹(shù)結(jié)構(gòu)中,每一個(gè)結(jié)點(diǎn)只有一個(gè)前件,稱(chēng)為父結(jié)點(diǎn),沒(méi)有前件的結(jié)點(diǎn)只有一個(gè),稱(chēng)為樹(shù)的根結(jié)點(diǎn),簡(jiǎn)稱(chēng)樹(shù)的根。每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件,稱(chēng)為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒(méi)有后件的結(jié)點(diǎn)稱(chēng)為葉子結(jié)點(diǎn)。

在樹(shù)結(jié)構(gòu)中,一個(gè)結(jié)點(diǎn)所擁有的后件的個(gè)數(shù)稱(chēng)為該結(jié)點(diǎn)的度,所有結(jié)點(diǎn)中最大的度稱(chēng)為樹(shù)的度。樹(shù)的最大層次稱(chēng)為樹(shù)的深度。

二叉樹(shù)的特點(diǎn):(1)非空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn);(2)每一個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù),且分別稱(chēng)為該結(jié)點(diǎn)的左子樹(shù)與右子樹(shù)。

二叉樹(shù)的基本性質(zhì):

(1)在二叉樹(shù)的第k層上,最多有2k-1(k≥1)個(gè)結(jié)點(diǎn);

(2)深度為m的二叉樹(shù)最多有2m-1個(gè)結(jié)點(diǎn);

(3)度為0的結(jié)點(diǎn)(即葉子結(jié)點(diǎn))總是比度為2的結(jié)點(diǎn)多一個(gè);

(4)具有n個(gè)結(jié)點(diǎn)的二叉樹(shù),其深度至少為[log2n]+1,其中[log2n]表示取log2n的整數(shù)部分;

(5)具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為[log2n]+1;

(6)設(shè)完全二叉樹(shù)共有n個(gè)結(jié)點(diǎn)。如果從根結(jié)點(diǎn)開(kāi)始,按層序(每一層從左到右)用自然數(shù)1,2,….n給結(jié)點(diǎn)進(jìn)行編號(hào)(k=1,2….n),有以下結(jié)論:

①若k=1,則該結(jié)點(diǎn)為根結(jié)點(diǎn),它沒(méi)有父結(jié)點(diǎn);若k>1,則該結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為int(k/2);

②若2k≤n,則編號(hào)為k的結(jié)點(diǎn)的左子結(jié)點(diǎn)編號(hào)為2k;否則該結(jié)點(diǎn)無(wú)左子結(jié)點(diǎn)(也無(wú)右子結(jié)點(diǎn));

③若2k+1≤n,則編號(hào)為k的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號(hào)為2k+1;否則該結(jié)點(diǎn)無(wú)右子結(jié)點(diǎn)。

滿(mǎn)二叉樹(shù)是指除最后一層外,每一層上的所有結(jié)點(diǎn)有兩個(gè)子結(jié)點(diǎn),則k層上有2k-1個(gè)結(jié)點(diǎn)深度為m的滿(mǎn)二叉樹(shù)有2m-1個(gè)結(jié)點(diǎn)。

完全二叉樹(shù)是指除最后一層外,每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值,在最后一層上只缺少右邊的若干結(jié)點(diǎn)。

二叉樹(shù)存儲(chǔ)結(jié)構(gòu)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),對(duì)于滿(mǎn)二叉樹(shù)與完全二叉樹(shù)可以按層序進(jìn)行順序存儲(chǔ)。

二叉樹(shù)的遍歷:

(1)前序遍歷(dlr),首先訪(fǎng)問(wèn)根結(jié)點(diǎn),然后遍歷左子樹(shù),最后遍歷右子樹(shù);

(2)中序遍歷(ldr),首先遍歷左子樹(shù),然后訪(fǎng)問(wèn)根結(jié)點(diǎn),最后遍歷右子樹(shù);

(3)后序遍歷(lrd)首先遍歷左子樹(shù),然后訪(fǎng)問(wèn)遍歷右子樹(shù),最后訪(fǎng)問(wèn)根結(jié)點(diǎn)。

7查找技術(shù)

順序查找的使用情況:

(1)線(xiàn)性表為無(wú)序表;

(2)表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

二分法查找只適用于順序存儲(chǔ)的有序表,對(duì)于長(zhǎng)度為n的有序線(xiàn)性表,最壞情況只需比較log2n次。

8排序技術(shù)

排序是指將一個(gè)無(wú)序序列整理成按值非遞減順序排列的有序序列。

交換類(lèi)排序法:(

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論