數(shù)據(jù)結構第一章-文庫吧資料
2024-08-17 16:53本頁面
【正文】 “ 輸入 ” 有確定關系的量值，是算法進行信息加工后得到的結果，這種確定關系即為算法的功能 算法的特性 ? 算法 設計的原則 ? 正確性 (correctness) ? 可讀性 (readability) ? 健壯性 (robustness) ? 高效率與低存儲量 算法的特性 正確性：算法應當滿足具體問題的需求 可分為四個層次： 無語法錯誤 、隨意數(shù)據(jù)、 刻意數(shù)據(jù)、一切合法數(shù)據(jù) 可讀性： 算法主要是為了人的閱讀與 交流，其次才是為計算機執(zhí)行，因此 算法應該易于人的理解；晦澀難讀的 程序易于隱藏較多錯誤而難以調試 健壯性： 當輸入的數(shù)據(jù)非法時，算法應當 恰當?shù)刈鞒龇从郴蜻M行相應處理，而不是 產(chǎn)生莫名奇妙的輸出結果。 算法的特性 ? 算法的特性（續(xù)） ? 可行性 ? 算法中的所有操作都必須足夠基本，都可以通過已經(jīng)實現(xiàn)的基本操作運算有限次來實現(xiàn)。 算法的概念 算法的概念 ? 排序 問題 ： Input － n個數(shù)的序列（ a1， a2， … .an） Output－輸入序列的一種 變換 （ a1’， a2’， a3’ … an’）， 滿足 a1’ ≤ a2’ ≤ a3’ ≤… ≤ an’ ? 排序 問題的實例 任給一個輸入序列如： 31， 41， 59， 26， 41， 58 排序算法將其排序并輸出結果： 26， 31， 41， 41， 58， 59 Such an input sequence is called an instance of the sorting problem ? 算法的特性 ? 有窮性 ? 對于任意一組合法輸入值，在執(zhí)行有窮步驟之后一定能結束，即：算法中的每個步驟都能在有限時間內(nèi)完成 ? 確定性 ? 每一條指令必須有明確的含義，讀者理解時不會產(chǎn)生二義性。 } ADT Complex ? 對特定問題求解過程的描述，是指令的有限序列，也即，為解決某一特定問題而采取的有限的操作步驟。sum ) 初始條件： z1, z2是復數(shù)。 操作結果：用 ImagPart返回復數(shù) Z的虛部值。 GetImag( Z, amp。realPart ) 初始條件：復數(shù)已存在。Z) 操作結果：復數(shù) Z被銷毀。Z, v1, v2 ) 操作結果：構造復數(shù) Z,其實部和虛部分別被賦以參數(shù) v1 和 v2 的值。 ? 目的：使人們能夠獨立于程序的實現(xiàn)細節(jié)來理解數(shù)據(jù)結構的特性 抽象數(shù)據(jù)類型 ? 抽象數(shù)據(jù)類型的定義取決于它的一組邏輯特性，而與其在計算機內(nèi)部如何表示和實現(xiàn)無關 ? 即不論其內(nèi)部結構如何變化，只要它的數(shù)學特性不變，都不影響其外部的使用 ? 抽象數(shù)據(jù)類型的形式定義 ： ADT=（ D， S， P） ? 其中： D是數(shù)據(jù)對象； S是 D上的關系集； P是對 D的基本操作集。 數(shù)據(jù)結構 ? 數(shù)據(jù)的邏輯結構 ? 關系 S闡明數(shù)據(jù)結構的特性 ? 集合 ? 同屬于一個集合 ? 線性結構（ linear structure） ? 一個對一個 ? 線性關系；有向的；全序性和單索性 ? 樹形結構（ tree structure） ? 一個對多個 ? 層次關系；根節(jié)點；子結點和父結點 ? 圖狀結構（ graph structure） ? 多個對多個 ? 網(wǎng)狀關系； 數(shù)據(jù)結構 ? 數(shù)據(jù)的存儲（物理）結構 ? 數(shù)據(jù)的邏輯結構在計算機存儲器中的實現(xiàn)（ 邏輯結構在存儲器中的映象） ? 對于數(shù)據(jù)邏輯結構（ D , S ） ? “數(shù)據(jù)元素”的映象 ? 對它的結點集合 D建立一個從 D到存儲器的單元的映射：對于每一個結點 d∈ D都對應一個 唯一的連續(xù)存儲區(qū)域 。 }STUDENT。 char name[20]。 ? 通信專業(yè)課程安排。主 講：張偉 單 位：信息學院通信與信息系統(tǒng)研究所 日 期： 2022年 9月 東北大學 數(shù)據(jù)結構及應用算法 學習內(nèi)容 數(shù)據(jù)結構和算法概述（ 2學時） 基本數(shù)據(jù)結
公司管理相關推薦
鄂ICP備17016276號-1