[院校資料]第一章-緒論-wenkub
2022-10-31 23:54:43 本頁面
【正文】 算法選用的策略 ?問題的規(guī)模 ?編寫程序的語言 ?編譯程序產(chǎn)生的機(jī)器代碼質(zhì)量 ?計(jì)算機(jī)執(zhí)行指令的速度 算法復(fù)雜度 ?時間復(fù)雜度： 基本操作重復(fù)執(zhí)行的次數(shù) ? 一個特定算法的時間復(fù)雜度，只依賴于問題的規(guī)模 (通常用 n表示 ), 或者說它是問題規(guī)模的函數(shù) T(n) = O(f(n)) 時間復(fù)雜度 時間復(fù)雜度 例：兩個 nxn矩陣相乘 for (i=1。Z , v1 , v2 ) 操作結(jié)果：構(gòu)造復(fù)數(shù) Z, 其實(shí)部和虛部分別被賦 于參數(shù) v1和 v2的 ?DestroyComplex( amp。 三元組基本操作實(shí)現(xiàn) 舉例 Status Get( Triplet T,int i, Elemtype*e ) { if ( i 1 || i3 ) return ERROR 。 ?Min(T,amp。 否則返回 FALSE。 操作結(jié)果 : 如果三元組 T的三個元素按升序排列 ,則返回TRUE。 操作結(jié)果 : 銷毀三元組 T 抽象數(shù)據(jù)類型 ? Get(T,i,amp。 ?P – 對 D的基本操作集 抽象數(shù)據(jù)類型 ? 抽象數(shù)據(jù)類型的定義格式 ?ADT抽象數(shù)據(jù)類型名 { 數(shù)據(jù)對象：＜數(shù)據(jù)對象的定義＞ 數(shù)據(jù)關(guān)系：＜數(shù)據(jù)關(guān)系的定義＞ 基本操作：＜基本操作的定義＞ ｝ ADT抽象的數(shù)據(jù)類型名 ? 基本操作的定義格式為： 基本操作名（參數(shù)表） 初始條件：＜初始條件描述＞ 操作結(jié)果：＜操作結(jié)果描述＞ 抽象數(shù)據(jù)類型 ? ADT Triplet{ 數(shù)據(jù)對象 :D={e1,e2,e3|e1,e2,e3屬于集合 數(shù)據(jù)關(guān)系 :R1={＜ e1,e2＞ |＜ e2,e3＞ } 基本操作： ?InitTriplet(amp。 ? 數(shù)值性數(shù)據(jù) ? 非數(shù)值性數(shù)據(jù) ? 數(shù)據(jù)元素 (Data Element):是數(shù)據(jù)的基本單位 ，在計(jì)算機(jī)程序中通常作為一個整體進(jìn)行考慮和處理 。 假定名字和其電話號碼邏輯上已安排成 N元向量的形式，它的每個元素是一個數(shù)對 (ai， bi)， 1≤i≤n ? 數(shù)據(jù)結(jié)構(gòu)還要提供每種結(jié)構(gòu)類型所定義的各種運(yùn)算的算法。 什么是數(shù)據(jù)結(jié)構(gòu) ? 算法的設(shè)計(jì)，依賴于計(jì)算機(jī)如何存儲人的名字和對應(yīng)的電話號碼，或者說依賴于名字和其電話號碼的結(jié)構(gòu)。為了編寫一個“好”的程序，必須分析待處理的對象的特征及各對象之間存在的關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)所要研究的問題。算法與數(shù)據(jù)結(jié)構(gòu) 陳 羽 中 ?課程名稱 :算法與數(shù)據(jù)結(jié)構(gòu) ?預(yù)修課程 :C語言 , 高等數(shù)學(xué) ?教材 :數(shù)據(jù)結(jié)構(gòu) C語言版 ,清華大學(xué)出版社 ,1997 緒論 ? 什么是數(shù)據(jù)結(jié)構(gòu) ? 基本概念和術(shù)語 ? 抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn) ? 算法和算法分析 ? 算法 ? 算法設(shè)計(jì)的要求 ? 算法效率的度量 ? 算法的存儲空間的需求 緒論 ? 計(jì)算機(jī)是一門研究用計(jì)算機(jī)進(jìn)行信息表示和處理的科學(xué)。 什么是數(shù)據(jù)結(jié)構(gòu) ? 計(jì)算機(jī)的程序是對信息進(jìn)行加工處理。數(shù)據(jù)的結(jié)構(gòu)，直接影響算法的選擇和效率。 例 :某專業(yè)有若干課程 ,其中有些課程必需先于其它課程學(xué)習(xí) .試制定課程的學(xué)習(xí)先后順序 ,使教學(xué)活動能順利進(jìn)行 . 記號 :課程 A若先于課程 AB. 特定例子 .有 10門課 :A1,A2,A3,… A10, 課程間關(guān)系如下 : A1A2, A1A3, A2A4, A2A10, A3A5, A4A6, A4A8, A5A8, A6A3, A7A5, A7A9, A9A10,A9A4. 什么是數(shù)據(jù)結(jié)構(gòu) 建立模型 :用有向圖來描述上述關(guān)系 1 5 2 3 6 4 8 7 10 9 1 算法設(shè)計(jì) : 拓?fù)渑判? (略 ) 什么是數(shù)據(jù)結(jié)構(gòu) 例 3. 多叉路口交通燈的管理問題 :如何在交通路口設(shè)置交通燈，使得車輛之間相互不碰撞 ,又能達(dá)到最大流通。 ? 數(shù)據(jù)項(xiàng) (Data Item)：數(shù)據(jù)的不可分割的最小單位 ， 一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項(xiàng)構(gòu)成 。T,v1,v2,v3) 初始條件 : 操作結(jié)果 : 構(gòu)造三元組 T,元素 e1,e2和 e3分別被賦予參 數(shù) v1,v2和 v3的值 。e) 初始條件 : 三元組 T已經(jīng)存在 ,1=i=3
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1