數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)課件第1章-預(yù)覽頁
【正文】 2022年 9月 5日星期三 第 21頁 數(shù)據(jù)結(jié)構(gòu)的形式定義 為 : 數(shù)據(jù)結(jié)構(gòu) 是一個(gè)二元組 Data_Structures = (D, S) 其中 :D 是 數(shù)據(jù)元素的有限集 ， S 是 D上 關(guān)系的有限集 。 散列 (或哈希 )存儲方法 根據(jù)結(jié)點(diǎn)的關(guān)鍵字通過散列函數(shù)直接計(jì)算出一個(gè)值，并將這個(gè)值作為該結(jié)點(diǎn)的存儲地址。 typedef int Long_int [3] 定義長整數(shù) 為 : 2022年 9月 5日星期三 第 29頁 二、數(shù)據(jù)類型 在用高級程序語言編寫的程序中， 必須對程序中出現(xiàn)的每個(gè)變量、 常量或表達(dá)式， 明確說明 它們所 屬的 數(shù)據(jù)類型 。 2022年 9月 5日星期三 第 33頁 例如， 抽象數(shù)據(jù)類型 復(fù)數(shù) 的定義： 數(shù)據(jù)對象： D＝ {e1,e2｜ e1,e2∈ RealSet } 數(shù)據(jù)關(guān)系： R1＝ {e1,e2 | e1是復(fù)數(shù)的實(shí)數(shù)部分 | e2 是復(fù)數(shù)的虛數(shù)部分 } ADT Complex { 2022年 9月 5日星期三 第 34頁 基本操作： AssignComplex( amp。 GetReal( Z, amp。ImagPart ) 初始條件：復(fù)數(shù)已存在。 操作結(jié)果：用 sum返回兩個(gè)復(fù)數(shù) z1, z2 的 和值。 其中： D 是數(shù)據(jù)對象； S 是 D 上的關(guān)系集； P 是對 D 的基本操作集。 初始條件 描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出錯(cuò)信息。 例如，對以上定義的復(fù)數(shù)。sum ) { // 以 sum 返回兩個(gè)復(fù)數(shù) z1, z2 的和 = + 。 2． 確定性 對于 每種情況 下所應(yīng)執(zhí)行的操作，在算法中都有 確切 的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行。有些輸入量需要在算法執(zhí)行過程中輸入，而有的算法表面上可以沒有輸入，實(shí)際上已被嵌入算法之中。 d． 程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能得出滿足要求的結(jié)果； 2022年 9月 5日星期三 第 53頁 2. 可讀性 算法主要是為了人的 閱讀與交流 ，其次才是為計(jì)算機(jī)執(zhí)行，因此算法應(yīng)該 易于 人的 理解 ；另一方面，晦澀難讀的程序易于隱藏較多錯(cuò)誤而難以調(diào)試。 2022年 9月 5日星期三 第 56頁 三 、算法效率的 衡量方法和準(zhǔn)則 通常有 兩種 衡量算法效率的方法 : 事后統(tǒng)計(jì)法 事前分析估算法 缺點(diǎn)： 1．必須執(zhí)行程序 2．其它因素掩蓋算法本質(zhì) 2022年 9月 5日星期三 第 57頁 和算法執(zhí)行 時(shí)間 相關(guān)的 因素 ： 1． 算法 選用 的策略 2． 問題的規(guī)模 3． 編寫程序的 語言 4．編譯 程序產(chǎn)生的機(jī)器代碼 的質(zhì)量 5．計(jì)算機(jī) 執(zhí)行指令 的速度 2022年 9月 5日星期三 第 58頁 一個(gè)特定 算法的 “ 運(yùn)行工作量 ” 的大小，只依賴于 問題的規(guī)模（通常用整數(shù)量 n表示），或者說，它 是問題規(guī)模的函數(shù) 。 c[] ) { // 以二維數(shù)組存儲矩陣元素， c 為 a 和 b 的乘積 for (i=1。 ++j) { c[i,j] = 0。 } //for } //mult 基本操作 : 乘法 操作 時(shí)間復(fù)雜度 : O(n3) 2022年 9月 5日星期三 第 64頁 例 二 選 擇 排 序 void select_sort(intamp。 k n。 ++i ) { if ( j != i ) a[j] ←→ a[i] } 2022年 9月 5日星期三 第 65頁 例 三 起 泡 排 序 void bubble_sort(intamp。amp。 ji。 S(n) = O(g(n)) 2022年 9月 5日星期三 第 67頁 算法的存儲量 包括 : 1． 輸入數(shù)據(jù) 所占空間 2． 程序本身 所占空間 3． 輔助變量 所占空間 2022年 9月 5日星期三 第 68頁 若 輸入數(shù)據(jù) 所占空間只取決于問題 本身， 和算法無關(guān) ，則只需要分析 除 輸入和程序之外的 輔助變量 所占 額外 空間 。 數(shù)據(jù)是計(jì)算機(jī)操作對象的總稱，它是計(jì)算機(jī)處理的符號的集合，集合中的個(gè)體為一個(gè)數(shù)據(jù)元素。數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)邏輯結(jié)構(gòu)在計(jì)算機(jī)中的映象，由關(guān)系的兩種映象方法可得到兩類存儲結(jié)構(gòu)：一類是順序存儲結(jié)構(gòu)，它以數(shù)據(jù)元素相對的存儲位置表示關(guān)系，則存儲結(jié)構(gòu)中只包含數(shù)據(jù)元素本身的信息；另一類是鏈?zhǔn)酱鎯Y(jié)構(gòu)，它以附加的指針信息（后繼元素的存儲地址）表示關(guān)系。算法是對問題求解的一種描述，是為解決一個(gè)或一類問題給出的一種確定規(guī)則的描述。算法空間復(fù)雜度可作為算法所需存儲量的一種量度，它主要取決于算法的輸入量和輔助變量所占空間，若算法的輸入僅取決于問題本身而和算法無關(guān)，則算法空間復(fù)雜度的估算只需考察算法中所用輔助變量所占空間，若算法的空間復(fù)雜度為常量級，則稱該算法為原地工作的算法。 (1) i=1。i++。 (3) i=1。 y++。 while(y0) if(x100) {x=x1
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1