數(shù)據(jù)結(jié)構(gòu)第一章-文庫(kù)吧
2024-08-03 16:53 本頁面
【正文】 對(duì)應(yīng)一個(gè) 唯一的連續(xù)存儲(chǔ)區(qū)域 。 ? “關(guān)系”的映象 ? 每一個(gè)關(guān)系元組（ d1 ,d2） ∈ S（其中 d1, d2∈ D是結(jié)點(diǎn)）， d1 ,d2的邏輯后繼關(guān)系應(yīng)映射為存儲(chǔ)單元的地址順序關(guān)系（或鏈接關(guān)系） 數(shù)據(jù)結(jié)構(gòu) ? 數(shù)據(jù)的存儲(chǔ)（物理）結(jié)構(gòu) ? 順序存儲(chǔ)結(jié)構(gòu) ? 用一塊無空隙的存儲(chǔ)區(qū)域存儲(chǔ)數(shù)據(jù)稱為順序存儲(chǔ) ? 借助元素在存儲(chǔ)器中的相對(duì)位置來表示數(shù)據(jù)元素間的邏輯關(guān)系 ? 元素間的邏輯后繼關(guān)系用存儲(chǔ)單元的自然順序關(guān)系來表達(dá) ? 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) ? 借助指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素間的邏輯關(guān)系 ? 兩個(gè)結(jié)點(diǎn)的邏輯后繼關(guān)系可以用指針的指向來表達(dá) 數(shù)據(jù)結(jié)構(gòu) ? 數(shù)據(jù)的存儲(chǔ)（物理）結(jié)構(gòu) Lo Lo+m Lo+(i1)*m Lo+（ n1)*m 存儲(chǔ)地址 存儲(chǔ)內(nèi)容 Loc(元素 i)=Lo+（ i1)*m 順序存儲(chǔ) 元素 1 元素 2 元素 i 元素 n head ^ 數(shù)據(jù)結(jié)構(gòu) 鏈?zhǔn)酱鎯?chǔ) ? 抽象 的本質(zhì) ? 簡(jiǎn)化 ? 忽略非本質(zhì)的部分 ? 高級(jí)語言中的數(shù)據(jù)類型實(shí)現(xiàn)了數(shù)據(jù)和操作的抽象化，但對(duì) 數(shù)據(jù)關(guān)系和操作能力 的抽象不強(qiáng) ? 抽象數(shù)據(jù)類型 （ Abstract Data Type， ADT） 描述數(shù)據(jù)結(jié)構(gòu)的一種理論工具 ? 是指一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作 。 ? 目的：使人們能夠獨(dú)立于程序的實(shí)現(xiàn)細(xì)節(jié)來理解數(shù)據(jù)結(jié)構(gòu)的特性 抽象數(shù)據(jù)類型 ? 抽象數(shù)據(jù)類型的定義取決于它的一組邏輯特性，而與其在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)無關(guān) ? 即不論其內(nèi)部結(jié)構(gòu)如何變化，只要它的數(shù)學(xué)特性不變，都不影響其外部的使用 ? 抽象數(shù)據(jù)類型的形式定義 ： ADT=（ D， S， P） ? 其中： D是數(shù)據(jù)對(duì)象； S是 D上的關(guān)系集； P是對(duì) D的基本操作集。 ADT 抽象數(shù)據(jù)類型名 { 數(shù)據(jù)對(duì)象： 〈 數(shù)據(jù)對(duì)象的定義 〉 數(shù)據(jù)關(guān)系： 〈 數(shù)據(jù)關(guān)系的定義 〉 基本操作： 〈 基本操作的定義 〉 } ADT 抽象數(shù)據(jù)類型名 抽象數(shù)據(jù)類型 例如，抽象數(shù)據(jù)類型復(fù)數(shù)的定義： ADT Complex { 數(shù)據(jù)對(duì)象： D＝ {e1,e2｜ e1,e2∈ RealSet } 數(shù)據(jù)關(guān)系： R1＝ {e1,e2 | e1是復(fù)數(shù)的實(shí)數(shù)部分； e2 是復(fù)數(shù)的虛數(shù)部分 } 基本操作： AssignComplex( amp。Z, v1, v2 ) 操作結(jié)果：構(gòu)造復(fù)數(shù) Z,其實(shí)部和虛部分別被賦以參數(shù) v1 和 v2 的值。 DestroyComplex( amp。Z) 操作結(jié)果：復(fù)數(shù) Z被銷毀。 GetReal( Z, amp。realPart ) 初始條件：復(fù)數(shù)已存在。 操作結(jié)果：用 realPart返回復(fù)數(shù) Z的實(shí)部值。 GetImag( Z, amp。ImagPart ) 初始條件：復(fù)數(shù)已存在。 操作結(jié)果：用 ImagPart返回復(fù)數(shù) Z的虛部值。 Add( z1,z2, amp。sum ) 初始條件： z1, z2是復(fù)數(shù)。 操作結(jié)果：用 sum返回兩個(gè)復(fù)數(shù) z1, z2 的和值。 } ADT Complex ? 對(duì)特定問題求解過程的描述，是指令的有限序列，也即，為解決某一特定問題而采取的有限的操作步驟。 ? 程序是算法的一種實(shí)現(xiàn)，計(jì)算機(jī)按照程序逐步執(zhí)行算法，實(shí)現(xiàn)對(duì)問題的求解。 算法的概念 算法的概念 ? 排序 問題 ： Input － n個(gè)數(shù)的序列（ a1， a2， … .an） Output－輸入序列的一種 變換 （ a1’， a2’， a3’ … an’）， 滿足 a1’ ≤ a2’ ≤ a3’ ≤… ≤ an’ ? 排序 問題的實(shí)例 任給一個(gè)輸入序列如： 31， 41， 59， 26， 41， 58 排序算法將其排序并輸出結(jié)果： 26， 31， 41， 41， 58，
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1