6數(shù)據(jù)的組織結構與算法1(編輯修改稿)
2025-02-05 07:23 本頁面
【文章內(nèi)容簡介】 遍歷可分為 ? 先序遍歷 ? 中序遍歷 ? 后序遍歷 3．二叉樹的遍歷 22 1．先序遍歷遞歸算法定義： 若二叉樹非空，則依次執(zhí)行操作： (1) 訪問根結點； (2) 遍歷左子樹； (3) 遍歷右子樹。A?B?D?G?E?C?F ： 若二叉樹非空，則依次執(zhí)行操作： (1)遍歷左子樹； (2)訪問根結點； (3)遍歷右子樹。G?D?B?E?A?C?F 3．后序遍歷遞歸算法定義： 若二叉樹非空，則依次執(zhí)行操作： (1)遍歷左子樹； (2)遍歷右子樹； (3)訪問根結點。G?D?E?B?F?C?A 23 ? 一個圖由有限的頂點（ Vertices）和邊（ Edge）組成，所以可形式化地用 G＝（ V， E） 代表一個圖。圖中的結點稱為頂點，頂點之間的連線代表邊。 圖結構 24 ? 圖 (Graph)是由非空的頂點集合和一個描述頂點之間關系―― 邊（或者弧）的集合組成。 ? 其形式化定義為： G＝（ V， E） ? V＝ {vi| vi∈dataobject} ? E＝ {( vi,vj)| vi, vj ∈V ∧P(vi, vj)} ? 其中， G表示一個圖， V是圖 G中頂點的集合， E是圖 G中邊的集合，集合 E中 P(vi,vj)表示頂點 vi和頂點 vj之間有一條直接連線，即偶對 (vi,vj)表示一條邊 。 圖結構 25 ? 下圖（無向圖 G1）給出了一個圖的示例，在該圖中： ? 集合 V＝ {v1,v2,v3,v4}； ? 集合 E＝ {(v1,v3),(v1,v4),(v2,v3),(v2,v4),(V3,V4)} 圖結構 26 ?如果數(shù)據(jù)結構中，數(shù)據(jù)元素之間不考慮關系問題（無前趨 /后繼之分），則稱這種結構為 集合 。在集合中，各元素是“平等”的，它們的共同關系是：都屬于同一個集合。 集合 27 算法 ? 算法的特性 ? 算法是對問題求解過程的一種描述，是為解決一個或一類問題給出的一個確定的、有限長的操作序列。 28 算法的五個特性 （ 1） 有窮性： 對任何合法的輸入值，一個算法必須總是在執(zhí)行有窮步之后結束，且每一步都可在有窮時間內(nèi)完成； （ 2） 確定性： 算法中每一條指令必須有確切的含義，不會產(chǎn)生二義性，對于相同的輸入只能得出相同的輸出。 （ 3） 可行性： 即算法中描述的操作都可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有限次來實現(xiàn)的 。 （ 4） 輸入： 一個算法有 0個或多個輸入，這些輸入取自于某個特定的數(shù)據(jù)對象的集合，它可以使用 輸入語句 從外部提供，也可以在算法內(nèi)通過 賦初值 給定。 （ 5） 輸出： 一個算法有一個或多個的輸出，這些輸出是同輸入有著某些特定關系的量 。 29 ? 在設計算法時，通常應考慮以下原則： ? 首先設計的算法必須是“ 正確的 ” ? 其次應有很好的“ 可讀性 ”，還必須具有“ 健壯性 ” ? 最后還應考慮所設計算法的復雜性，即有“ 高效率與低存儲量 ”。 什么是“好”的算法 30 算法的正確性 ? 所謂算法的 正確性 ，也稱可靠性或有效性，是指： ? 程序不含語法錯誤。 ? 程序對于幾組輸入的數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結果。 ? 程序對于精心選擇的典型、苛刻而帶有刁難性的幾組輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結果。 ? 程序對于一切合法的輸入數(shù)據(jù)都能產(chǎn)生滿足規(guī)格說明要求的結果。 31 ? 在算法是正確的前提下，算法的 可讀性 是擺在第一位的?？勺x性好有助于人們對算法的理解，難懂的程序易隱藏較多錯誤，難以調(diào)試和修改。 ? 算法的 效率 指的是算法執(zhí)行時計算機資源的消耗，它包括運行時間代價和存儲空間代價。 ? 算法的 健壯性 指的是，算法應對非法輸入的數(shù)據(jù)做出恰當反映或進行相應處理。它強調(diào)的是，如果輸入非法數(shù)據(jù)時，算法應能加以識別并做出處理，而不是產(chǎn)生誤動作或陷入癱瘓。 32 ? 算法的復雜性是算法運行所需要的計算機資源的量。算法的復雜性是算法效率的度量，是評價算法優(yōu)劣的重要依據(jù)。 ? 算法的復雜性有 時間復雜性 和
環(huán)評公示相關推薦
鄂ICP備17016276號-1