第2章數(shù)據(jù)結(jié)構(gòu)及應(yīng)用概念及順序表-wenkub
2022-08-17 09:18:50 本頁面
【正文】 關(guān)系的集合。 數(shù)據(jù)元素是一個(gè)數(shù)據(jù)整體中相對(duì)獨(dú)立的單位 。下一頁 上一頁 停止放映 第 2章數(shù)據(jù)結(jié)構(gòu)及應(yīng)用 概念及順序表 西安交通大學(xué)計(jì)教中心 下一頁 上一頁 停止放映 [第 2/42頁 ] 思考問題 數(shù)據(jù)結(jié)構(gòu)要研究什么問題？ 什么是線性數(shù)據(jù)結(jié)構(gòu)和線性表？ 如何描述線性表？ 線性表在計(jì)算機(jī)中如何存放？有幾種存儲(chǔ)形式？它們的特點(diǎn)是什么？ 如何處理線性數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)？ …… 下一頁 上一頁 停止放映 [第 3/42頁 ] 數(shù)據(jù)結(jié)構(gòu)問題的由來 計(jì)算機(jī)求解問題的過程步驟： 調(diào)試程序 編制 程序 求解 結(jié)果 運(yùn)行 程序 結(jié)果輸出 用戶 需求 數(shù)據(jù)類型、格式、 邏輯結(jié)構(gòu) 數(shù)據(jù) 邏輯 運(yùn)算 數(shù)據(jù)的物理 操作 分析抽象 實(shí)際問題 模型求解 問題 模型 命令 編程 求解算法 下一頁 上一頁 停止放映 [第 4/42頁 ] 數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)的專業(yè)技術(shù)基礎(chǔ)課。 但它還可以分割成若干個(gè)具有不同屬性的項(xiàng) （ 字段 ） ， 故不是組成數(shù)據(jù)的最小單位 下一頁 上一頁 停止放映 [第 6/42頁 ] 數(shù)據(jù)結(jié)構(gòu) （ data structure） 是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素所組成的集合 。 與數(shù)據(jù)在計(jì)算機(jī)中的存放的 物理位置無關(guān) 下一頁 上一頁 停止放映 [第 8/42頁 ] 舉例 ? 課題組由 1名教師、 1~3名研究生、 1~6名本科生組成；成員關(guān)系是：教師指導(dǎo)研究生、研究生指導(dǎo) 1~2名本科生。 ?任何一個(gè) 算法的設(shè)計(jì) 取決于選定的邏輯結(jié)構(gòu)；而算法的最終實(shí)現(xiàn) 依賴于采用的存儲(chǔ)結(jié)構(gòu)。 ? 結(jié)構(gòu)簡單，易實(shí)現(xiàn)。 ? 插入、刪除操作簡單，只要修改指針即可； ? 結(jié)構(gòu)較復(fù)雜，需要額外存儲(chǔ)空間。 序 號(hào)： 1 2 3 4 5 6 7 數(shù)據(jù)項(xiàng)： 索引號(hào)： 下一頁 上一頁 停止放映 [第 15/42頁 ] 散列存儲(chǔ)結(jié)構(gòu) ? 在數(shù)據(jù)元素與存儲(chǔ)位置之間建立一種存儲(chǔ)關(guān)系 F，根據(jù)這種關(guān)系 F，已知元素 E，就可以得到它的存儲(chǔ)地址，即D=F（ E）。 常見操作有： – 輸入、檢索、插入、刪除、修改、排序等。 ⑷ 確定性 ： 每條指令的含義都必須明確 ， 無二義性 。一個(gè)算法中的時(shí)間復(fù)雜度一般用語句執(zhí)行次數(shù)的數(shù)量級(jí)來衡量。 j=i。常見的時(shí)間復(fù)雜度有： O（ 1） O（ logn） O（ n ） O（ n2 ） 常數(shù)階 對(duì)數(shù)階 線性階 平方階 空間復(fù)雜度 指算法在計(jì)算機(jī)上運(yùn)行所占用的存儲(chǔ)空間。討論方法與時(shí)間復(fù)雜度類似，不再贅述。 例如，一星期七天的英文縮寫表示： （ Sun， Mon， The， wed， Thu， Fri， Sat） 是一個(gè)線性表，其中的元素是字符串，表的長度為 7。 下一頁 上一頁 停止放映 [第 26/42頁 ] 順序表 采用順序存儲(chǔ)結(jié)構(gòu)的線性表稱為順序表，它的數(shù)據(jù)元素按照邏輯順序依次存放在一組連續(xù)的存儲(chǔ)單元中。 // 順序表最大允許長度 int length。數(shù)組的下標(biāo)從 0開始。 Llength = 0。 ②從最后一個(gè)元素開始依次向前，將每個(gè)元素向后移動(dòng)一個(gè)位置，直到第 i個(gè)元素為止。 算法描述： ?從數(shù)列右邊開始，即從第 8個(gè)元素開始； ?為在第 5個(gè)元素“ 21”后插入“ 25”，則要把其后的 3個(gè)元素右移，移動(dòng)元素個(gè)數(shù)是 3（ 85）； for( int j=Llength1。 Ldata[i1] = x。 j=i1。 // 表長度加一 } } 順序表插入算法 下一頁 上一頁 停止放映 [第 35/42頁 ] （ 3） 在表中刪除第 i個(gè)元素 算法實(shí)現(xiàn)的主要步驟是： ① 判斷刪除位置的合理性。 下一頁 上一頁 停止放映 [第 36/42頁 ] 0 1 2 i 2 i 1 i n1 maxsize a 1 a 2 a 3 a i 1 a i + 1 a n 0 1 2 … i 2 i 1 i … n
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1