2019年一章节基本概念课件.ppt

《2019年一章节基本概念课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章　基本概念資料結構與演算法徐熊健目錄1.1資料結構、演算法1.2資料結構與演算法1.3簡單的資料結構1.4演算法初探1.5演算法的效率分析1.1　資料結構、演算法「資料結構」(datastructure):在電腦中有效率地存放資料，使其方便處理的學問；「演算法」(algorithm):探討解決問題的策略。兩者相輔相成!1.2　資料結構與演算法電腦處理的對象稱為「資料」(data)，泛指所有輸入至電腦中，即將、正在或已經被電腦程式處理的符號總稱；包括了數值(numerical)資料、字串(string)資料等等，乃至於目前多媒體(multimedia)軟體所

2、處理的影像、聲音、視訊等多媒體資料。當這些資料集合在一起時，會因處理需求的不同而存在一種或多種彼此之間的特定關係，這些資料之間的邏輯關係，就稱為結構(structure)。研究資料的邏輯關係，探討這些邏輯關係在電腦中的表現(representation)和處理(manipulation)方式，即為「資料結構」。1.3　簡單的資料結構生活中常見的資料相互關係：(1)校園中有一群人；(2)每個中華民國國民皆有唯一的身分證字號；(3)每位同學在班上皆有唯一的座號、在學校皆有唯一的學號；(4)在大學中的科系有系別、年級別、甚至於班別；(5)排隊的時候，我們可能只關心排在

3、前一位的是誰？有時可能還在意排在自己前面的共有多少人？(6)外國旅行時，各景點間是否有班機直飛？(7)上網尋找資料，網頁間的鏈結，將網頁連結成複雜的全球性的網絡(world-wideweb)。1.4　演算法初探Horowitz,Sahni和Mehta，給予演算法的明確定義：演算法是一組可完成特定工作的指令集合，並且所有的演算法都需滿足下列條件：(1)輸入(input)：可以有多個其甚至是沒有輸入；(2)輸出(output)：至少產生一個輸出；(3)明確(definiteness)：每個指令都清楚明確；(4)有限(finiteness)：在任何情況下，如果逐步追蹤

4、演算法的每個指令，演算法會在有限的步驟內結束；(5)有效率(effectiveness)：原則上每個指令都需基本到人只需紙和筆即可實踐之，並且每個指令的運算不止如條件(3)般明確而已，還必須是可實行的。1.4.1程式撰寫流程撰寫程式解決問題流程圖問題的需求或限制思考與探索資料結構與演算法設計程式撰寫數學証明結果輸出驗証、測試與修善範例1-2　挑選排序法思考與探索：欲將整數由小至大排序，可把數字小者放在左邊，數字小者放在右邊，…可以挑出所有資料中最小者，做為左邊第一筆資料，接著再挑出剩下資料中最小者，放在左邊做為第二筆資料，依此類推，直至全部資料都排列完成。若所有

5、資料共計n筆，則會執行n次挑出最小的運算，其第i次的運算，即為挑出未排序資料中最小者，其結果做為第i筆資料。演算法1-1挑選排序法：輸入：data[0],data[1],data[2],…,data[n-1]，共n筆整數資料輸出：data[0],data[1],…,data[n-1]；其中若i

6、tionSort(intdata[],intn){inti,j;intmin,temp;for(i=0;i

7、遞迴(directrecursion)：當程序執行完成前呼叫了自己這個程序。間接遞迴(indirectrecursion)：在程序執行完成前呼叫了其它會再度引用到自己的程序。在設計遞迴程式時，切記終結條件(terminationcondition)的設立，否則易造形成無窮迴圈。程序呼叫時流程的轉換…SS(intdata[],intn)voidSS(intdata[],intn){}程式1-2計算階乘階乘的計算即可用遞迴的概念詮釋，請看：n!=n(n-1)!於是可以寫一個計算階乘的程序X(intn)，它接受傳入的整數n，傳回n*X(n-1)intX(intn){

8、if(n==1)retu