程式=資料結(jié)構(gòu)DataStructure+演算法課件

2022/12/161第一章

資料結(jié)構(gòu)導(dǎo)論課程名稱：資料結(jié)構(gòu)授課老師：陳明瑤2022/12/121第一章

資料結(jié)構(gòu)導(dǎo)論課程名稱：資料2022/12/162本章學(xué)習(xí)目標(biāo)

讓讀者了解資料結(jié)構(gòu)、演算法及程式之間的關(guān)係，以及如何評(píng)估演算法的執(zhí)行效率。2.讓讀者了解結(jié)構(gòu)化程式設(shè)計(jì)與物件導(dǎo)向程式設(shè)計(jì)的差異。2022/12/122本章學(xué)習(xí)目標(biāo)讓讀者了解資料結(jié)構(gòu)、演算2022/12/163本章內(nèi)容

1-1認(rèn)識(shí)資料與資訊的關(guān)係1-2何謂資料結(jié)構(gòu)？1-3何謂演算法?1-4程式設(shè)計(jì)概念1-5結(jié)構(gòu)化程式設(shè)計(jì)1-6物件導(dǎo)向程式設(shè)計(jì)1-7演算法的效率評(píng)估2022/12/123本章內(nèi)容1-1認(rèn)識(shí)資料與資訊的關(guān)係2022/12/1641-1認(rèn)識(shí)資料與資訊的關(guān)係1.資料(Data)：是指未經(jīng)過(guò)處理的原始記錄，例如學(xué)生考試的原始成績(jī)。2.資訊(Information)：就是有經(jīng)過(guò)處理的結(jié)果，例如全班同學(xué)成績(jī)之排名

及分佈圖。*資料處理(DP)：是將「資料」轉(zhuǎn)換成「資訊」的一連串的處理過(guò)程。2022/12/1241-1認(rèn)識(shí)資料與資訊的關(guān)係1.資料(2022/12/1651.資料(Data)(1)是客觀存在的、具體的、事實(shí)的記錄。(2)簡(jiǎn)單來(lái)說(shuō)，日常生活中所記錄的事實(shí)資料(姓名、生日、電話及地址)

或?qū)W生在期中考的各科原始成績(jī)，這些都是未經(jīng)過(guò)資料處理的資料。如表1-1所示。2022/12/1251.資料(Data)(1)是客觀存在的2022/12/1662.資訊(Information)

(1)經(jīng)過(guò)資料處理之後的結(jié)果即為資訊。其資料與資訊的特性比較。如表1-2所示。2022/12/1262.資訊(Information)(2022/12/167(2)處理程序(例如：成績(jī)處理系統(tǒng))會(huì)將原始資料以加整理、計(jì)算及分析之後，變成有用的資訊(含總成績(jī)、平均及排名次)。如表1-3所示。2022/12/127(2)處理程序(例如：成績(jī)處理系統(tǒng))會(huì)2022/12/168(3)是決策者在思考某一個(gè)問(wèn)題時(shí)所需用到的資料，它是主觀認(rèn)定的。例如：班導(dǎo)師(決策者)在學(xué)生考完期中考之後，想依學(xué)生考試成績(jī)來(lái)獎(jiǎng)勵(lì)，因此，班導(dǎo)師必須要有一份全班排名的成績(jī)單(資訊)，以做為獎(jiǎng)勵(lì)的依據(jù)。

2022/12/128(3)是決策者在思考某一個(gè)問(wèn)題時(shí)所需用2022/12/1691-2何謂資料結(jié)構(gòu)？

「資料結(jié)構(gòu)」(DataStructures)主要是探討如何將資料更有組織地存放到電腦記憶體中，以提昇程式之執(zhí)行效率的一門學(xué)問(wèn)。因此，有良好的資料結(jié)構(gòu)（Datastructure）及有效率的演算法（Algorithm）將可以大大的提昇程式的執(zhí)行效率。

2022/12/1291-2何謂資料結(jié)構(gòu)？「資料結(jié)2022/12/1610在電腦科學(xué)(ComputerScience)的領(lǐng)域中，我們?nèi)绾瓮高^(guò)電腦來(lái)取得即時(shí)的、有用的資訊，那就必須先要撰寫(xiě)有效率及正確的「程式」去運(yùn)作，而「程式」就是由「資料結(jié)構(gòu)」和「演算法」所構(gòu)成的。其公式如下：程式=資料結(jié)構(gòu)(DataStructure)+演算法(Algorithms)其中：「資料結(jié)構(gòu)」：是指資料在記憶體中的儲(chǔ)存方式，「演算法」:則是如何將資料作有效率的處理過(guò)程。因此，當(dāng)我們?cè)谧珜?xiě)程式時(shí)，只有選擇適當(dāng)?shù)摹举Y料結(jié)構(gòu)】，才能夠設(shè)計(jì)出最有效率的【演算法】，進(jìn)而轉(zhuǎn)換成為有效率的【程式】。2022/12/1210在電腦科學(xué)(ComputerSci2022/12/1611

基本上，資料結(jié)構(gòu)包含有遞迴(Recursive)、陣列(Array)、堆疊(Stack)、佇列(Queue)、串列(List)、樹(shù)狀(Tree)、圖形(Graph)、排序(Sort)及搜尋(Search)等單元，雖然這幾種資料結(jié)構(gòu)單元乍看之下，好像非常理論與抽象，但是在我們?nèi)粘Ｉ钪校瑓s經(jīng)常可以看到。2022/12/1211基本上，資料結(jié)構(gòu)包含有遞迴(2022/12/1612【舉例】遞迴(Recursive)：老鼠走迷宮的問(wèn)題就是屬於「遞迴」結(jié)構(gòu)。陣列(Array)：教室座位排列方式就是屬於「陣列」結(jié)構(gòu)。堆疊(Stack)：碗盤的疊法、小朋友排積木、書(shū)本裝箱或座電梯等都具有後進(jìn)先出的特性就是屬於「堆疊」結(jié)構(gòu)。佇列(Queue)：排隊(duì)買票看球賽，先到先買的方式就是所謂的「佇列」結(jié)構(gòu)2022/12/1212【舉例】2022/12/1613【舉例】串列(List)：高鐵火車的車箱串接方式就是屬於「串列」結(jié)構(gòu)。樹(shù)狀(Tree)：如果球賽的賽程方式是採(cǎi)用淘汰制，就是一種「樹(shù)狀」結(jié)構(gòu)。圖形(Graph)：當(dāng)看完球賽要回家的行駛路線圖，則可視為所謂的「圖形」結(jié)構(gòu)。排序(Sort)：球賽成績(jī)的結(jié)果之排名方式就是屬於「排序」結(jié)構(gòu)。搜尋(Search)：球賽比賽之前找尋某一隊(duì)的賽程就是屬於「搜尋」結(jié)構(gòu)。2022/12/1213【舉例】2022/12/1614【老師上課動(dòng)態(tài)展示】檔案在附書(shū)光碟中。

2022/12/1214【老師上課動(dòng)態(tài)展示】檔案在附書(shū)光碟中2022/12/1615【實(shí)例】

撰寫(xiě)一個(gè)程式來(lái)計(jì)算5位同學(xué)的「資料結(jié)構(gòu)」平均成績(jī)，並且比較沒(méi)有使用資料結(jié)構(gòu)與演算法的差異。2022/12/1215【實(shí)例】撰寫(xiě)一個(gè)程式來(lái)計(jì)算5位同學(xué)2022/12/1616第一種方法沒(méi)有使用資料結(jié)構(gòu)與演算法，而是使用一般變數(shù)的宣告方式來(lái)個(gè)別存放成績(jī)資料。雖然也可以順利的計(jì)算出所需要的結(jié)果，但是，比較缺乏彈性，因?yàn)?，?dāng)我們要計(jì)算的學(xué)生人數(shù)異動(dòng)時(shí)，程式將會(huì)比較難以維護(hù)。例如：全班學(xué)生人數(shù)為50人時(shí)，則行號(hào)04的程式碼就會(huì)變數(shù)非常的長(zhǎng)，

容易產(chǎn)生錯(cuò)誤。

2022/12/1216第一種方法沒(méi)有使用資料結(jié)構(gòu)與演算法，2022/12/1617第二種方法是使用「陣列」資料結(jié)構(gòu)來(lái)存放5位同學(xué)的成績(jī)資料，然後再使用for迴圈的演算法來(lái)計(jì)算5位同學(xué)的成績(jī)，最後再列印出結(jié)果。比較分析：第二種方法的程式比較有彈性，也就是說(shuō)，當(dāng)我們要計(jì)算的學(xué)生人數(shù)異動(dòng)時(shí)，只要設(shè)定行號(hào)01的學(xué)生人數(shù)及行號(hào)05的陣列內(nèi)容即可。

2022/12/1217第二種方法是使用「陣列」資料結(jié)構(gòu)來(lái)存2022/12/16181-3何謂演算法?「演算法」在韋氏辭典中定義為：「在有限步驟內(nèi)解決數(shù)學(xué)問(wèn)題的程序」。我們可以把演算法(Algorithm)定義成：「解決問(wèn)題的方法」。它可以是利用文字?jǐn)⑹觥⒒蛄鞒虉D或虛擬碼的方式，來(lái)表示解決問(wèn)題的步驟。2022/12/12181-3何謂演算法?「演算法」在韋氏2022/12/1619一、撰寫(xiě)演算法應(yīng)遵守五點(diǎn)原則：

1.輸入(Input)：不一定要有輸入?？赡軟](méi)有，也可能是多個(gè)資料輸入。

例如(1)：取得系統(tǒng)目前的時(shí)間，不須要輸入，只要寫(xiě)一行now()函數(shù)，就可以輸出系統(tǒng)時(shí)間。例如(2)：求某數(shù)為奇偶數(shù)時(shí)，則必須先要有一個(gè)整數(shù)輸入，才能進(jìn)行判斷。2022/12/1219一、撰寫(xiě)演算法應(yīng)遵守五點(diǎn)原則：1.2022/12/1620一、撰寫(xiě)演算法應(yīng)遵守五點(diǎn)原則：(續(xù))

2.輸出(Output)：至少一個(gè)輸出。

例如：在電腦中，處理資料的基本過(guò)程有三個(gè)步驟：

輸入處理輸出

(原始資料)(程式)(有用的資訊)

所以，使用電腦來(lái)為我們處理資料時(shí)，有可能是系統(tǒng)自動(dòng)接收到一個(gè)訊號(hào)，來(lái)當(dāng)作輸入資料，但是系統(tǒng)至少會(huì)輸出一項(xiàng)讓使用者參考的有用資訊。

2022/12/1220一、撰寫(xiě)演算法應(yīng)遵守五點(diǎn)原則：(續(xù)2022/12/1621一、撰寫(xiě)演算法應(yīng)遵守五點(diǎn)原則：(續(xù))

3.明確性(Definiteness)：每一行指令都必須明確，不可模稜兩可。例如：判斷某一數(shù)值是否為偶數(shù)。首先我們?cè)囍孟铝形淖謥?lái)加以描述：

(1)輸入一個(gè)正整數(shù)。

(2)作餘除運(yùn)算是否為0。

(3)為0即為偶數(shù)。以上描述看來(lái)似乎正確，但是從演算法觀點(diǎn)來(lái)看，其中的第(2)點(diǎn)並不符合「明確性」，因它並未說(shuō)明「餘除運(yùn)算」是如何運(yùn)算，容易造成混淆與不解。我們應(yīng)該改寫(xiě)為：

(1)輸入一個(gè)正整數(shù)N。

(2)如果N除以2，其餘數(shù)為0。

(3)則其N為偶數(shù)。不具明確性具明確性2022/12/1221一、撰寫(xiě)演算法應(yīng)遵守五點(diǎn)原則：(續(xù)2022/12/1622一、撰寫(xiě)演算法應(yīng)遵守五點(diǎn)原則：(續(xù))例如：「用功的學(xué)生才能領(lǐng)獎(jiǎng)學(xué)金」就不具有明確性，因?yàn)槊恳粋€(gè)人對(duì)用功的定義可能不盡相同，而如果改為「成績(jī)90以上的學(xué)生才能領(lǐng)獎(jiǎng)學(xué)金」就是具有明確性，因?yàn)?0分是一個(gè)比較客觀的定義。2022/12/1222一、撰寫(xiě)演算法應(yīng)遵守五點(diǎn)原則：(續(xù)2022/12/1623一、撰寫(xiě)演算法應(yīng)遵守五點(diǎn)原則：(續(xù))4.有限性(Finiteness)：演算法不能有無(wú)窮迴路，必須能終止執(zhí)行。由於演算法並非是真正可以執(zhí)行的程式，而是設(shè)計(jì)者所推演出解決問(wèn)題的步驟，因此，必須在有限的步驟內(nèi)要完成解決問(wèn)題的程序。但是，真正的程式是可以有無(wú)窮迴路的動(dòng)作。例如：Windows作業(yè)系統(tǒng)除非系統(tǒng)關(guān)機(jī)或當(dāng)機(jī)，否則它會(huì)永遠(yuǎn)執(zhí)行一個(gè)「等待迴圈」，來(lái)等待使用者從鍵盤輸入或其他的輸入設(shè)備。

2022/12/1223一、撰寫(xiě)演算法應(yīng)遵守五點(diǎn)原則：(續(xù)2022/12/1624一、撰寫(xiě)演算法應(yīng)遵守五點(diǎn)原則：(續(xù))5.正確性(Correctness)

：既然演算法是解決問(wèn)題的方法，因此，正確性是最基本的要求。例如：以下判斷某數(shù)為奇偶數(shù)的演算法，雖然符合「明確性」，但是

「不正確」，因?yàn)镹除以2，其餘數(shù)為0，則N應(yīng)該為「偶數(shù)」，而非「奇數(shù)」。

輸入一個(gè)正整數(shù)N。

如果N除以2，其餘數(shù)為0。

則其N為奇數(shù)。應(yīng)該改為「偶數(shù)」

2022/12/1224一、撰寫(xiě)演算法應(yīng)遵守五點(diǎn)原則：(續(xù)2022/12/1625【日常生活中的例子】一組可用來(lái)解決特定問(wèn)題的有限指令或步驟，依循這些指令或步驟，可以進(jìn)行解題。食譜-做蛋糕圖片來(lái)源：6/cornliu/cornppt/第六章.ppt2022/12/1225【日常生活中的例子】一組可用來(lái)解決特2022/12/1626好吃的蛋糕怎麼來(lái)?輸入輸出明確性正確性有限性圖片來(lái)源：6/cornliu/cornppt/第六章.ppt2022/12/1226好吃的蛋糕怎麼來(lái)?輸入輸出明確性2022/12/1627二、描述演算法有三種方法：(一)文字?jǐn)⑹鲅菟惴捎梦淖旨右悦枋?，但是?cǎi)用口語(yǔ)化的文字?jǐn)⑹鰜?lái)加以描述，其缺點(diǎn)在於冗長(zhǎng)且較不精確，在撰寫(xiě)、閱讀、會(huì)意時(shí)可能會(huì)有誤差，因此一般較不常用。

例如：請(qǐng)利用「文字?jǐn)⑹觥故褂谜叩侨霂ぬ?hào)與密碼時(shí)，系統(tǒng)檢查的過(guò)程。步驟一：輸入使用者帳號(hào)與密碼步驟二：判斷帳號(hào)與密碼是否正確步驟三：如果正確時(shí)，則可以登入系統(tǒng)否則，就無(wú)法登入！2022/12/1227二、描述演算法有三種方法：(一)文字2022/12/1628(二)流程圖（Flowchart）『流程圖』是指利用圖形方式來(lái)表達(dá)欲解決問(wèn)題的步驟。當(dāng)我們想利用電腦程式語(yǔ)言來(lái)處理問(wèn)題時(shí)，先要了解問(wèn)題並想出許多方案來(lái)解決問(wèn)題，並且分析那些資料是要「輸入」，經(jīng)過(guò)「處理」之後，要「輸出」那些結(jié)果。

2022/12/1228(二)流程圖（Flowchart）2022/12/16292022/12/12292022/12/16302022/12/12302022/12/1631【舉例】請(qǐng)繪出使用者登入帳號(hào)與密碼時(shí)，系統(tǒng)檢查的流程圖。2022/12/1231【舉例】請(qǐng)繪出使用者登入帳號(hào)與密碼時(shí)2022/12/1632(三)虛擬碼（PseudoCode）虛擬碼兼具文字描述及流程圖的優(yōu)點(diǎn)，其方式是用文字摻雜程式語(yǔ)言，來(lái)描述解題步驟與方法。例如1：請(qǐng)利用「虛擬碼（PseudoCode）」敘述使用者登入帳號(hào)與密碼時(shí)，系統(tǒng)檢查的過(guò)程。(1)Input:UserName,Password(2)IF(UserNameAndPassword)ALLTrueOutput:YouCanPass!elseOutput:YouCannotPass!2022/12/1232(三)虛擬碼（PseudoCode2022/12/1633例如：1+2+3+…+10虛擬碼可以描述如下：(1)設(shè)Count=1,Total=0;(2)Total=Total+Count;(3)Count=Count+1;(4)若Count>10則至步驟(5)，否則回步驟(2)(5)印出Total2022/12/1233例如：1+2+3+…+10虛擬碼可以2022/12/16341-4程式設(shè)計(jì)概念我們要開(kāi)始程式設(shè)計(jì)時(shí)，一定要進(jìn)行下面五個(gè)步驟：2022/12/12341-4程式設(shè)計(jì)概念我們要開(kāi)始程式2022/12/16352022/12/12352022/12/16362022/12/12362022/12/1637〔實(shí)例〕計(jì)算國(guó)文與英文的平均成績(jī)，並依照平均成績(jī)來(lái)求顯示「及格」與「不及格」。1.分析及定義問(wèn)題。兩個(gè)等級(jí)分別如下：

(1)及格：60(含)以上。

(2)不及格：60以下。2.畫(huà)出整合問(wèn)題的流程圖或撰寫(xiě)問(wèn)題的演算法。2022/12/1237〔實(shí)例〕計(jì)算國(guó)文與英文的平均成績(jī)，並2022/12/16383.撰寫(xiě)及建立程式模組。2022/12/12383.撰寫(xiě)及建立程式模組。2022/12/16394.對(duì)每一個(gè)程式模組進(jìn)行測(cè)試及除錯(cuò)，直到?jīng)]有錯(cuò)誤為止。當(dāng)使用者輸入國(guó)文為60分，英文為61分時(shí)，是否可以計(jì)算出平均成績(jī)?yōu)?0.5，如果沒(méi)有則必須要進(jìn)行除錯(cuò)，亦即要將Average的資料型態(tài)改為Single(單精準(zhǔn)度)2022/12/12394.對(duì)每一個(gè)程式模組進(jìn)行測(cè)試及除錯(cuò)，2022/12/1640【重要觀念】

系統(tǒng)發(fā)展的生命週期與程式設(shè)計(jì)之步驟比較2022/12/1240【重要觀念】系統(tǒng)發(fā)展的生命週期2022/12/16411-4.1演算法與程式的差異？1.「演算法」是以「人」為主，亦即「任何人都可以閱讀的程式碼」，因此，必須特別強(qiáng)調(diào)「可讀性」。2.「程式」則是以「電腦」為主，它強(qiáng)調(diào)程式的執(zhí)行結(jié)果正確性、可維護(hù)性及執(zhí)行效率。2022/12/12411-4.1演算法與程式的差異？1.2022/12/16421-4.2為什麼要撰寫(xiě)程式?我們?yōu)槭颤N要花那麼多時(shí)間來(lái)撰寫(xiě)程式呢？其主要的目的：它可以快速解決「複雜的問(wèn)題」。甲同學(xué)說(shuō)：請(qǐng)電腦幫我計(jì)算1加到10的總合?；蛟S你會(huì)認(rèn)為這簡(jiǎn)單的問(wèn)題，你我都會(huì)算，何必寫(xiě)程式呢？但是，如果甲同學(xué)又說(shuō)：請(qǐng)電腦幫我計(jì)算1加到50000時(shí)，我想我們就無(wú)法馬上計(jì)算出結(jié)果。由上面的例子，我們可以非常清楚的知道，程式語(yǔ)言幫忙人類解決複雜的問(wèn)題。2022/12/12421-4.2為什麼要撰寫(xiě)程式?我們?yōu)槭?022/12/16431-5結(jié)構(gòu)化程式設(shè)計(jì)何謂結(jié)構(gòu)化程式設(shè)計(jì)呢？它是利用「由上而下」的技巧，將程式分解成多個(gè)具有獨(dú)立功能的模組。如圖1-5所示。圖1-5結(jié)構(gòu)化程式設(shè)計(jì)的示意圖2022/12/12431-5結(jié)構(gòu)化程式設(shè)計(jì)何謂結(jié)構(gòu)化程2022/12/1644結(jié)構(gòu)化程式設(shè)計(jì)由Dijkstra(1969)提出：1.消除程式因goto而造成如麵條式的混亂狀態(tài)。2.強(qiáng)調(diào)任何程式邏輯均可由三種結(jié)構(gòu)組成。如圖1-6所示。

(1)循序(Sequence)：簡(jiǎn)單命令式的指令如COMPUTE,READ,WRITE與代數(shù)指令如X=Y+Z。

(2)選擇(Condition)：需做決策時(shí)，用IF-THEN-ELSE指令與

CASE指令。

(3)重複(Repetition)：當(dāng)需反覆時(shí)，用DO-WHILE

與

DO-UNTIL指令。2022/12/1244結(jié)構(gòu)化程式設(shè)計(jì)由Dijkstra(2022/12/16452022/12/12452022/12/16461-5.1循序結(jié)構(gòu)所謂循序結(jié)構(gòu)，是指程式由上而下，依序逐一執(zhí)行。亦即『程式碼被執(zhí)行的順序?yàn)橛缮隙拢粋€(gè)敘述接著一個(gè)敘述依序執(zhí)行』。此種結(jié)構(gòu)是最基本的結(jié)構(gòu)。如圖1-7所示：2022/12/12461-5.1循序結(jié)構(gòu)所謂循序結(jié)構(gòu)，是2022/12/16471-5.2選擇結(jié)構(gòu)如果只希望在某種條件成立時(shí)才執(zhí)行某些敘述，而某種條件不成立才執(zhí)行另一種敘述，來(lái)過(guò)濾一些條件。那我們就必須使用「選擇結(jié)構(gòu)」的方式了。如圖1-8所示。

2022/12/12471-5.2選擇結(jié)構(gòu)如果只希望在某2022/12/1648此種結(jié)構(gòu)是最常被使用的方式，因?yàn)榇蟛糠莸倪x擇結(jié)構(gòu)的情況可能是兩種。例如：判斷及格與不及格、判斷奇數(shù)與偶數(shù)、判斷男生與女生

…等情況，都可以利用此種結(jié)構(gòu)來(lái)完成。2022/12/1248此種結(jié)構(gòu)是最常被使用的方式，因?yàn)榇蟛?022/12/16491.語(yǔ)法：其中(條件式)

是一關(guān)係運(yùn)算式或邏輯運(yùn)算式2.說(shuō)明：如果「條件式」成立(真)，就執(zhí)行Then後面的「敘述區(qū)塊1」，否則就執(zhí)行「敘述區(qū)塊2」。3.使用時(shí)機(jī)：當(dāng)條件只有二種情況時(shí)最佳方法。2022/12/12491.語(yǔ)法：2022/12/16505.流程圖：如圖1-9所示：2022/12/12505.流程圖：如圖1-9所示：2022/12/16511-5.3重複結(jié)構(gòu)

在處理一再重複的相同動(dòng)作，這對(duì)電腦而言，是一件非常Easy的事，但對(duì)我們?nèi)祟惗詤s是一件苦差事，因此驅(qū)使電腦做這樣的事情的方式，就是迴圈(Loop)，亦即讓某一段程式反覆執(zhí)行多次的敘述，我們稱此結(jié)構(gòu)為「迴圈結(jié)構(gòu)」。2022/12/12511-5.3重複結(jié)構(gòu)在2022/12/1652如果我們想要撰寫(xiě)一段程式，來(lái)輸出1,2,…,100時(shí)，怎麼辦？目前最少有兩種方法可以使用。如圖1-10所示：2022/12/1252如果我們想要撰寫(xiě)一段程式，來(lái)輸出1,2022/12/16531-6物件導(dǎo)向程式設(shè)計(jì)(選讀)

物件導(dǎo)向設(shè)計(jì)是以「物件」為主，首先規(guī)劃整個(gè)系統(tǒng)需要那些物件，再分析這些物件有什麼特性(屬性)、如何操作(方法)，以及物件與物件之間的關(guān)連性，然後開(kāi)始撰寫(xiě)各個(gè)物件模組，最後再依照系統(tǒng)的需求，將各個(gè)封裝良好的物件模組由下向上架構(gòu)出整個(gè)系統(tǒng)。2022/12/12531-6物件導(dǎo)向程式設(shè)計(jì)(選讀)2022/12/1654每一個(gè)物件模組就是一個(gè)定義好的類別，其內(nèi)容包括一些私有的資料項(xiàng)目和功能(即屬性)，以及供外界來(lái)操作的一些方法。如圖1-11所示。2022/12/1254每一個(gè)物件模組就是一個(gè)定義好的類別，2022/12/16551-6.1物件導(dǎo)向的基本觀念

「物件導(dǎo)向」可以說(shuō)是現(xiàn)代最新的一種思考方式，而每一個(gè)物件都具有其特有的屬性(Attribute)及行為(Behavior)及方法(Method)，並且可以是一個(gè)抽象物、觀念、概念、或是一個(gè)有明確界定範(fàn)圍的事物。2022/12/12551-6.1物件導(dǎo)向的基本觀念2022/12/1656一、何謂物件(Object)何謂物件？簡(jiǎn)單的說(shuō)，物件就是「東西」。日常生活中，看得到、摸得到、感覺(jué)得到的都是物件。任何東西都可以當(dāng)作物件，像人也可以當(dāng)作一個(gè)物件，每個(gè)人(物件)都有它的特性(屬性)，包括：身高、體重、性別、年齡…等描述。因此，我們就可以區(qū)別出人與人之間的不同之處。然而小物件還可以再組成一個(gè)大物件，例如：車子是一個(gè)大物件，它是由四個(gè)輪子、四個(gè)車門、方向盤…等其他小物件所組成的。2022/12/1256一、何謂物件(Object)何謂物件2022/12/1657若以電腦世界來(lái)說(shuō)，VB設(shè)計(jì)模式中的「工具箱」之所有元件，其實(shí)都可以當(dāng)作「物件」，而這物件就是撰寫(xiě)程式時(shí)的重要「零件」，我們可以把它當(dāng)成是在堆積木一般的排列組合，進(jìn)一步的設(shè)計(jì)屬於自己的程式。我們可以將下圖中的小算盤應(yīng)用程式視為一個(gè)大物件，它是由數(shù)個(gè)按鈕、一個(gè)文字方塊及功能表的小物件所組成的。2022/12/1257若以電腦世界來(lái)說(shuō)，VB設(shè)計(jì)模式中的「2022/12/16582022/12/12582022/12/16592022/12/12592022/12/1660二、何謂屬性(Property)

屬性可以說(shuō)是物件的性質(zhì)，是用來(lái)區(qū)分不同的物件。例如每一個(gè)「人」都具有「髮色」、「身高」、「體重」、「性別」…等不同的屬性。而屬性的內(nèi)容稱為「屬性值」，如人的「性別」屬性之屬性值有「男與女」兩種情況，因此我們就可以區(qū)分出不同性別的人，如圖1-13所示：

2022/12/1260二、何謂屬性(Property)2022/12/1661

每一個(gè)人(物件)都有他們的姓名、身高、性別及外貌等等，這些都是他們的屬性。每一個(gè)人一定會(huì)有這樣屬性，但是每一個(gè)人可能都有不同的屬性值，也就是說(shuō)小明與小華的姓名、身高、體重、性別及外貌有可能皆不相同，就是因?yàn)槿绱耍覀儾拍芊直娉鲂∶髋c小華的不同點(diǎn)。

2022/12/1261每一個(gè)人(物件)都有他們2022/12/16622022/12/12622022/12/1663因此，我們?cè)谧珜?xiě)物件導(dǎo)向的程式時(shí)，我們可以藉由改變屬性的屬性值，即可改變物件的外觀。而改變屬性的方法有二種：第一種：靜態(tài)設(shè)定(在「屬性」視窗的對(duì)話方塊中設(shè)定)。如圖1-15所示：在設(shè)計(jì)階段時(shí)，在該物件的屬性視窗直接設(shè)定之，馬上顯示效果。2022/12/1263因此，我們?cè)谧珜?xiě)物件導(dǎo)向的程式時(shí)，我2022/12/1664第二種：動(dòng)態(tài)設(shè)定(在程式碼視窗的程序中撰寫(xiě))。如圖1-16所示：物件名稱和屬性名稱中間使用點(diǎn)號(hào)加以區(qū)隔。2022/12/1264第二種：動(dòng)態(tài)設(shè)定(在程式碼視窗的程序2022/12/1665二、何謂事件(Event)所謂事件？可說(shuō)是一種被動(dòng)性的動(dòng)作或某一情境下所產(chǎn)生的行為。例如：當(dāng)小孩被父母「打」時(shí)，他的反應(yīng)動(dòng)作是「手痛得跳起來(lái)」，並發(fā)出「尖叫」的聲音，連下來(lái)可能「開(kāi)始哭」。綜合上述，小孩被父母「打」是一種「事件」，當(dāng)這個(gè)事件被啟動(dòng)之後，小孩便產(chǎn)生了一連串的動(dòng)作：「手痛得跳起來(lái)」、「尖叫」、「開(kāi)始哭」…等動(dòng)作，稱為「事件程序」，通常物件會(huì)具備設(shè)許多個(gè)「事件」，我們只要在必要的事件中，指定其動(dòng)作即可。事件是一種加在物件上的「作用」，而事件程序則是物件對(duì)此作用所產(chǎn)生的「反應(yīng)」。事件程序的表達(dá)方式。2022/12/1265二、何謂事件(Event)所謂事件？2022/12/16662022/12/12662022/12/1667四、何謂方法(Method)所謂「方法」，是指為了在物件完成某件事或達(dá)成某項(xiàng)目標(biāo)，所採(cǎi)取的處理方式。物件原來(lái)內(nèi)含的函數(shù)或程序就叫做方法。物件的「屬性」或「事件程序」都可以重新設(shè)定或修改，但是「方法」的內(nèi)容是固定、不能修改的。在VB中，物件與方法的表達(dá)方式為：2022/12/1267四、何謂方法(Method)所謂「方2022/12/1668例如，在表單物件中提供了清除、列印、畫(huà)點(diǎn)、畫(huà)線、…等功能，這些功能通稱為「方法」。譬如，我們想要將表單中的TextBox文字框內(nèi)容清除，只要撰寫(xiě)TextBox1.Clear()即可。

2022/12/1268例如，在表單物件中提供了清除、列印、2022/12/16691-6.2物件導(dǎo)向程式設(shè)計(jì)的特性

物件導(dǎo)向程式設(shè)計(jì)的最主要精神就是物件，但是支援物件的程式語(yǔ)言並不一定是物件導(dǎo)向程式語(yǔ)言(例如VB6.0)，它只是一種以物件為基礎(chǔ)的程式語(yǔ)言（Object-basedLanguages），亦即提供物件觀念。而VB.NET、VisualBasic2005、C#、C++及Java才是真正的物件導(dǎo)向程式語(yǔ)言。物件導(dǎo)向主要是由四個(gè)基礎(chǔ)概念所構(gòu)成，分別為封裝性(Encapsulation)、抽象化(Abstraction)、繼承性(Inheritance)及多型(Polymorphism)這四個(gè)觀念。

2022/12/12691-6.2物件導(dǎo)向程式設(shè)計(jì)的特性2022/12/1670一、封裝性(Encapsulation)封裝性就是將物件的「屬性」與「操作」或「方法」一起封裝到類別中。這是一種資訊隱藏（informationhiding）的概念。因此，可以提供安全性，因?yàn)槲锛臓顟B(tài)無(wú)法被外界直接控制；另一方面，介面可以簡(jiǎn)化對(duì)於物件狀態(tài)的了解，因?yàn)橥饨绮槐亓私馕锛顟B(tài)的細(xì)節(jié)。如圖1-18所示。2022/12/1270一、封裝性(Encapsulatio2022/12/1671例如以電視機(jī)來(lái)說(shuō)明封裝性的概念：如圖1-19所示。在日常生活中的“電視機(jī)”提供給使用者的是螢?zāi)缓鸵唤M功能按鈕，使用者透過(guò)對(duì)這組「功能按鈕」的操作和「螢?zāi)弧箒?lái)觀賞電視節(jié)目，而使用者不必知道電視機(jī)是如何實(shí)作這些功能的。因?yàn)殡娨暀C(jī)把選擇頻道、控制音量、調(diào)整色彩、對(duì)比度和亮度等功能的實(shí)作都「封裝」起來(lái)了，以避免使用者任意破壞。2022/12/1271例如以電視機(jī)來(lái)說(shuō)明封裝性的概念：如圖2022/12/1672二、繼承性(Inheritance)

繼承性就是物件可以繼承其他物件的「屬性」及「操作」。例如兒子繼承爸爸或媽媽的特色(屬性或方法)，且兒子會(huì)再擁有自己新的特色。繼承性的目的是增加再用性，避免了屬性及操作的重複。被繼承的類別可稱為「父類別(parentclass)」、「超類別(supperclass)」或「基底類別(baseclass)」，而繼承的類別可稱為「子類別(childclass)、「次類別(subclass)」或「衍生類別(derivedclass)」。2022/12/1272二、繼承性(Inheritance)2022/12/1673例如：當(dāng)我們將各物件抽象化為「交通工具」類別後，我們可以再依據(jù)物件導(dǎo)向的「繼承性」之特性，將交通工具再細(xì)分為陸上交通工具、水上交通工具、空中交通工具等三個(gè)類別。如圖1-20

所示。2022/12/1273例如：當(dāng)我們將各物件抽象化為「交通工2022/12/1674三、抽象化(Abstraction)在真實(shí)世界中，我們可以把汽車當(dāng)作是一個(gè)物件，也可以把貨車、吉普車等當(dāng)作是一個(gè)物件，若我們沒(méi)有從抽象化的觀點(diǎn)來(lái)看待這些物件時(shí)，則會(huì)發(fā)現(xiàn)這個(gè)世界將會(huì)充滿無(wú)數(shù)的類似物件，使我們會(huì)不知如何去了解它們。但若透過(guò)「抽象化」觀念來(lái)剔除物件間的差異，則我們可以將這些物件抽象化為「交通工具」這個(gè)類別。如圖1-21所示。2022/12/1274三、抽象化(Abstraction)2022/12/1675四、多型性(Polymorphism)多型的概念常以一句話來(lái)解釋：「一個(gè)介面，多個(gè)方法」。這代表有可能可以設(shè)計(jì)一個(gè)通用的介面給一組相關(guān)動(dòng)作。亦即同一個(gè)名稱的操作,在不同的類別當(dāng)中表示不同的行為。例如，父類別(SuperClass)中有一個(gè)名叫做show()的方法，用來(lái)顯示學(xué)生的姓名資料，子類別中也有一個(gè)名叫show()的方法，用來(lái)顯示學(xué)生的成績(jī)資料，這二個(gè)方法都稱為show()。2022/12/1275四、多型性(Polymorphism2022/12/16762022/12/12762022/12/16771-7演算法的效率評(píng)估演算法的效率評(píng)估指的是用來(lái)計(jì)算某些演算法所撰寫(xiě)的程式在經(jīng)過(guò)編譯之後實(shí)際執(zhí)行所需要的時(shí)間。但是，實(shí)務(wù)上有可能因?yàn)槌淌骄幾g的過(guò)程或是電腦設(shè)備的差異使得效率分析會(huì)因電腦的軟硬體不同而有不同的結(jié)果，因此，一般而言，效率的評(píng)估方式可分為兩大類：一、時(shí)間複雜度（TimeComplexity）二、空間複雜度（SpaceComplexity）2022/12/12771-7演算法的效率評(píng)估演算法的效2022/12/1678一、時(shí)間複雜度（TimeComplexity）是指從呼叫該副程式開(kāi)始到完成之過(guò)程，所有花費(fèi)的執(zhí)行時(shí)間。基本上，影響程式執(zhí)行時(shí)間的因素，有種兩因素：1.演算法效率的好壞2.機(jī)器的CPU執(zhí)行速度所以，執(zhí)行時(shí)間=執(zhí)行次數(shù)*每次執(zhí)行所需的時(shí)間。2022/12/1278一、時(shí)間複雜度（TimeCompl2022/12/1679由於每一行程式所需的時(shí)間必須考慮到機(jī)器本身的CPU執(zhí)行速度及編譯器的功能，所以，在評(píng)估上比較不客觀。因此，通常只考慮執(zhí)行的次數(shù)，所以，在相同功能的條件之下，執(zhí)行次數(shù)的多寡，往往是用來(lái)決定演算法效率的好壞。也就是說(shuō)，我們必須先計(jì)算出程式中每一敘述的執(zhí)行次數(shù)，再一一的加總起來(lái)，然後再求出其Big-O。例如：計(jì)算下列程式中變數(shù)Count被執(zhí)行的次數(shù)為何？2022/12/1279由於每一行程式所需的時(shí)間必須考慮到機(jī)2022/12/1680二、空間複雜度（SpaceComplexity）是指從呼叫該副程式開(kāi)始到完成之過(guò)程，所有佔(zhàn)用的記憶體空間。例如：參數(shù)、變數(shù)宣告，回傳值以及傳回位址時(shí)，都會(huì)佔(zhàn)用記憶體空間。2022/12/1280二、空間複雜度（SpaceComp2022/12/16812022/12/12812022/12/1682◆時(shí)間複雜度與空間複雜度之分析

基本上，時(shí)間複雜度的分析比空間複雜度來(lái)得重要，因?yàn)楫?dāng)資料量龐大時(shí)，時(shí)間複雜度會(huì)有較大的差異性，但是，空間複雜度則差異較小，再加上目前的記憶體相當(dāng)便宜，因此，目前在資料結(jié)構(gòu)所探討演算法之效率評(píng)估，都著重在時(shí)間複雜度方面的評(píng)估。2022/12/1282◆時(shí)間複雜度與空間複雜度之分析基本2022/12/16831-7.1時(shí)間複雜度(Timecomplexity)【舉例1】假設(shè)有一陣列a，其陣列的大小為n，如果要將陣列a的元素相加，請(qǐng)問(wèn)程式的執(zhí)行次數(shù)為何？【解析】行號(hào)04會(huì)執(zhí)行n+1次，而前n次會(huì)執(zhí)行迴圈主體，但是在第n+1次時(shí)沒(méi)有符合迴圈的條件，故離開(kāi)迴圈。2022/12/12831-7.1時(shí)間複雜度(Timec2022/12/1684【舉例2】假設(shè)兩矩陣a,b相加，並且矩陣大小皆為n*n，請(qǐng)計(jì)算出下列程式的執(zhí)行次數(shù)。【解析】行號(hào)04外層迴圈(for)的計(jì)數(shù)器i從0~n-1，共會(huì)執(zhí)行n+1次，而行號(hào)05內(nèi)層迴圈(for)的計(jì)數(shù)器j從0~n-1，也會(huì)執(zhí)行n+1次。因此，當(dāng)外層迴圈執(zhí)行1次時(shí)，則內(nèi)層迴圈要執(zhí)行一回合，也就是j從0~n-1(共有n次)

2022/12/1284【舉例2】假設(shè)兩矩陣a,b相加，並2022/12/1685【舉例3】假設(shè)兩矩陣a,b相乘，並且矩陣大小皆為n*n，相加請(qǐng)計(jì)算出下列程式的執(zhí)行次數(shù)。2022/12/1285【舉例3】假設(shè)兩矩陣a,b相乘，並2022/12/1686在經(jīng)過(guò)上面例子，來(lái)算出程式敘述的執(zhí)行次數(shù)後，我們雖然可以利用理論「上下限Θ(n)」比理論上限O(n)與理論下限Ω(n)都來(lái)得準(zhǔn)確，但是在通常利用理論上限O(n)之Big-O來(lái)表示此演算法的執(zhí)行時(shí)間，亦稱為該程式的「時(shí)間複雜度(timecomplexity)」。

2022/12/1286在經(jīng)過(guò)上面例子，來(lái)算出程式敘述的執(zhí)行2022/12/1687一、O(n)(Big-Oofn)的定義：

最常被使用，用來(lái)表示理論「上限」O(n)可視為某演算法在電腦中所需執(zhí)行時(shí)間，亦即某演算法的執(zhí)行時(shí)間T(n)的時(shí)間複雜度(timecomplexity)為O(n)(讀成Big-Oofn)?！綛ig-O的觀念】Big-O取執(zhí)行次數(shù)中最高次方或最大指數(shù)部份的項(xiàng)目即可。如：陣列元素相加為2n+3=O(n)矩陣相加為2n2+2n+2=O(n2)矩陣相乘為2n3+4n2+2n+2=O(n3)2022/12/1287一、O(n)(Big-Oofn2022/12/1688因此，透過(guò)時(shí)間複雜度分析之觀念，我們就可以判斷某些程式的執(zhí)行效率是否良好?！炯僭O(shè)】f(n)：統(tǒng)計(jì)的執(zhí)行次數(shù)。g(n)：Big-O取執(zhí)行次數(shù)中最高次方或最大指數(shù)部份的項(xiàng)目。f(n)=O(g(n))，若且唯若，存在一正整數(shù)c及n0，對(duì)所有的n，nn0時(shí)，則f(n)c*g(n)。2022/12/1288因此，透過(guò)時(shí)間複雜度分析之觀念，我們2022/12/1689【舉例】矩陣相加的執(zhí)行次數(shù)為2n2+2n+21.f(n)就會(huì)等於2n2+2n+2亦即：f(n)=2n2+2n+22.g(n)則取f(n)中的最高次方亦即：g(n)=n2∴f(n)=O(g(n))2022/12/1289【舉例】矩陣相加的執(zhí)行次數(shù)為2n2+2022/12/16902022/12/12902022/12/16912022/12/12912022/12/1692二、Ω(n)(Omegaofn)定義：

用來(lái)表示理論「下限」f(n)=(g(n))，若且唯若，存在正整數(shù)c及n0，對(duì)所有的n，nn0時(shí)，則f(n)c*g(n)。2022/12/1292二、Ω(n)(Omegaofn2022/12/16932022/12/12932022/12/1694三、Θ(n)(Thetaofn)定義：

表示理論上限與下限均為此函數(shù)是一種比Big-O與Ω更精確時(shí)間複雜度的漸近表示法。f(n)=(g(n))，若且唯若，存在正整數(shù)c1、c2及n0，對(duì)所有的n，nn0時(shí)，則c1*g(n)

f(n)

c2*g(n)。

2022/12/1294三、Θ(n)(Thetaofn2022/12/16952022/12/12952022/12/1696四、時(shí)間複雜度的等級(jí)若n代表資料的數(shù)量，時(shí)間複雜度可分為下列不同的等級(jí)：2022/12/1296四、時(shí)間複雜度的等級(jí)若n代表資料的數(shù)2022/12/16972022/12/12972022/12/16981-7.2空間複雜度(SpaceComplexity)一個(gè)程式P的空間複雜度(SpaceComplexity)包含固定的空間需求與變動(dòng)的空間需求兩個(gè)部分。一、固定的空間需求包含了程式在編譯時(shí)期(CompileTime)所產(chǎn)生的空間需求。例如程式本身的指令空間、常數(shù)、靜態(tài)變數(shù)及結(jié)構(gòu)等。二、變動(dòng)空間需求包含了動(dòng)態(tài)記憶體要求(DynamicMemoryAllocation)所配置的空間，以及遞迴函數(shù)執(zhí)行時(shí)所需要用來(lái)儲(chǔ)存活動(dòng)紀(jì)錄(ActivationRecord)的執(zhí)行時(shí)堆疊空間(RunTimeStack)。2022/12/12981-7.2空間複雜度(Space2022/12/1699通常我們會(huì)利用S(P)來(lái)表示一個(gè)程式P所需的空間需求，公式：S(P)=c+SP(I)其中：c代表這個(gè)程式的固定空間需求SP(I)則表示程式P針對(duì)特定的輸入資料集合I(Instance)

所需的變動(dòng)空間需求。2022/12/1299通常我們會(huì)利用S(P)來(lái)表示一個(gè)程式2022/12/16100【實(shí)例】試”著計(jì)算出三個(gè)整數(shù)之平均”的空間複雜度為何？【解答】在上面的例子中，Add函數(shù)有3個(gè)參數(shù)及1個(gè)傳回值，因此，固定的空間需求為(3+1)*2bytes=8bytes，而Add函數(shù)並沒(méi)有使用到動(dòng)態(tài)配置記憶體，所以，變動(dòng)空間需求為0byte，因此，空間複雜度的需求為8+0=8bytes2022/12/12100【實(shí)例】試”著計(jì)算出三個(gè)整數(shù)之平均2022/12/161011-7.3演算的效率分析-排序演算法的比較2022/12/121011-7.3演算的效率分析-排序演2022/12/161021-7.4常用的數(shù)學(xué)式子2022/12/121021-7.4常用的數(shù)學(xué)式子2022/12/161032022/12/121032022/12/16104第一章

資料結(jié)構(gòu)導(dǎo)論課程名稱：資料結(jié)構(gòu)授課老師：陳明瑤2022/12/121第一章

資料結(jié)構(gòu)導(dǎo)論課程名稱：資料2022/12/16105本章學(xué)習(xí)目標(biāo)

讓讀者了解資料結(jié)構(gòu)、演算法及程式之間的關(guān)係，以及如何評(píng)估演算法的執(zhí)行效率。2.讓讀者了解結(jié)構(gòu)化程式設(shè)計(jì)與物件導(dǎo)向程式設(shè)計(jì)的差異。2022/12/122本章學(xué)習(xí)目標(biāo)讓讀者了解資料結(jié)構(gòu)、演算2022/12/16106本章內(nèi)容

1-1認(rèn)識(shí)資料與資訊的關(guān)係1-2何謂資料結(jié)構(gòu)？1-3何謂演算法?1-4程式設(shè)計(jì)概念1-5結(jié)構(gòu)化程式設(shè)計(jì)1-6物件導(dǎo)向程式設(shè)計(jì)1-7演算法的效率評(píng)估2022/12/123本章內(nèi)容1-1認(rèn)識(shí)資料與資訊的關(guān)係2022/12/161071-1認(rèn)識(shí)資料與資訊的關(guān)係1.資料(Data)：是指未經(jīng)過(guò)處理的原始記錄，例如學(xué)生考試的原始成績(jī)。2.資訊(Information)：就是有經(jīng)過(guò)處理的結(jié)果，例如全班同學(xué)成績(jī)之排名

及分佈圖。*資料處理(DP)：是將「資料」轉(zhuǎn)換成「資訊」的一連串的處理過(guò)程。2022/12/1241-1認(rèn)識(shí)資料與資訊的關(guān)係1.資料(2022/12/161081.資料(Data)(1)是客觀存在的、具體的、事實(shí)的記錄。(2)簡(jiǎn)單來(lái)說(shuō)，日常生活中所記錄的事實(shí)資料(姓名、生日、電話及地址)

或?qū)W生在期中考的各科原始成績(jī)，這些都是未經(jīng)過(guò)資料處理的資料。如表1-1所示。2022/12/1251.資料(Data)(1)是客觀存在的2022/12/161092.資訊(Information)

(1)經(jīng)過(guò)資料處理之後的結(jié)果即為資訊。其資料與資訊的特性比較。如表1-2所示。2022/12/1262.資訊(Information)(2022/12/16110(2)處理程序(例如：成績(jī)處理系統(tǒng))會(huì)將原始資料以加整理、計(jì)算及分析之後，變成有用的資訊(含總成績(jī)、平均及排名次)。如表1-3所示。2022/12/127(2)處理程序(例如：成績(jī)處理系統(tǒng))會(huì)2022/12/16111(3)是決策者在思考某一個(gè)問(wèn)題時(shí)所需用到的資料，它是主觀認(rèn)定的。例如：班導(dǎo)師(決策者)在學(xué)生考完期中考之後，想依學(xué)生考試成績(jī)來(lái)獎(jiǎng)勵(lì)，因此，班導(dǎo)師必須要有一份全班排名的成績(jī)單(資訊)，以做為獎(jiǎng)勵(lì)的依據(jù)。

2022/12/128(3)是決策者在思考某一個(gè)問(wèn)題時(shí)所需用2022/12/161121-2何謂資料結(jié)構(gòu)？

「資料結(jié)構(gòu)」(DataStructures)主要是探討如何將資料更有組織地存放到電腦記憶體中，以提昇程式之執(zhí)行效率的一門學(xué)問(wèn)。因此，有良好的資料結(jié)構(gòu)（Datastructure）及有效率的演算法（Algorithm）將可以大大的提昇程式的執(zhí)行效率。

2022/12/1291-2何謂資料結(jié)構(gòu)？「資料結(jié)2022/12/16113在電腦科學(xué)(ComputerScience)的領(lǐng)域中，我們?nèi)绾瓮高^(guò)電腦來(lái)取得即時(shí)的、有用的資訊，那就必須先要撰寫(xiě)有效率及正確的「程式」去運(yùn)作，而「程式」就是由「資料結(jié)構(gòu)」和「演算法」所構(gòu)成的。其公式如下：程式=資料結(jié)構(gòu)(DataStructure)+演算法(Algorithms)其中：「資料結(jié)構(gòu)」：是指資料在記憶體中的儲(chǔ)存方式，「演算法」:則是如何將資料作有效率的處理過(guò)程。因此，當(dāng)我們?cè)谧珜?xiě)程式時(shí)，只有選擇適當(dāng)?shù)摹举Y料結(jié)構(gòu)】，才能夠設(shè)計(jì)出最有效率的【演算法】，進(jìn)而轉(zhuǎn)換成為有效率的【程式】。2022/12/1210在電腦科學(xué)(ComputerSci2022/12/16114

基本上，資料結(jié)構(gòu)包含有遞迴(Recursive)、陣列(Array)、堆疊(Stack)、佇列(Queue)、串列(List)、樹(shù)狀(Tree)、圖形(Graph)、排序(Sort)及搜尋(Search)等單元，雖然這幾種資料結(jié)構(gòu)單元乍看之下，好像非常理論與抽象，但是在我們?nèi)粘Ｉ钪?，卻經(jīng)常可以看到。2022/12/1211基本上，資料結(jié)構(gòu)包含有遞迴(2022/12/16115【舉例】遞迴(Recursive)：老鼠走迷宮的問(wèn)題就是屬於「遞迴」結(jié)構(gòu)。陣列(Array)：教室座位排列方式就是屬於「陣列」結(jié)構(gòu)。堆疊(Stack)：碗盤的疊法、小朋友排積木、書(shū)本裝箱或座電梯等都具有後進(jìn)先出的特性就是屬於「堆疊」結(jié)構(gòu)。佇列(Queue)：排隊(duì)買票看球賽，先到先買的方式就是所謂的「佇列」結(jié)構(gòu)2022/12/1212【舉例】2022/12/16116【舉例】串列(List)：高鐵火車的車箱串接方式就是屬於「串列」結(jié)構(gòu)。樹(shù)狀(Tree)：如果球賽的賽程方式是採(cǎi)用淘汰制，就是一種「樹(shù)狀」結(jié)構(gòu)。圖形(Graph)：當(dāng)看完球賽要回家的行駛路線圖，則可視為所謂的「圖形」結(jié)構(gòu)。排序(Sort)：球賽成績(jī)的結(jié)果之排名方式就是屬於「排序」結(jié)構(gòu)。搜尋(Search)：球賽比賽之前找尋某一隊(duì)的賽程就是屬於「搜尋」結(jié)構(gòu)。2022/12/1213【舉例】2022/12/16117【老師上課動(dòng)態(tài)展示】檔案在附書(shū)光碟中。

2022/12/1214【老師上課動(dòng)態(tài)展示】檔案在附書(shū)光碟中2022/12/16118【實(shí)例】

撰寫(xiě)一個(gè)程式來(lái)計(jì)算5位同學(xué)的「資料結(jié)構(gòu)」平均成績(jī)，並且比較沒(méi)有使用資料結(jié)構(gòu)與演算法的差異。2022/12/1215【實(shí)例】撰寫(xiě)一個(gè)程式來(lái)計(jì)算5位同學(xué)2022/12/16119第一種方法沒(méi)有使用資料結(jié)構(gòu)與演算法，而是使用一般變數(shù)的宣告方式來(lái)個(gè)別存放成績(jī)資料。雖然也可以順利的計(jì)算出所需要的結(jié)果，但是，比較缺乏彈性，因?yàn)?，?dāng)我們要計(jì)算的學(xué)生人數(shù)異動(dòng)時(shí)，程式將會(huì)比較難以維護(hù)。例如：全班學(xué)生人數(shù)為50人時(shí)，則行號(hào)04的程式碼就會(huì)變數(shù)非常的長(zhǎng)，

容易產(chǎn)生錯(cuò)誤。

2022/12/1216第一種方法沒(méi)有使用資料結(jié)構(gòu)與演算法，2022/12/16120第二種方法是使用「陣列」資料結(jié)構(gòu)來(lái)存放5位同學(xué)的成績(jī)資料，然後再使用for迴圈的演算法來(lái)計(jì)算5位同學(xué)的成績(jī)，最後再列印出結(jié)果。比較分析：第二種方法的程式比較有彈性，也就是說(shuō)，當(dāng)我們要計(jì)算的學(xué)生人數(shù)異動(dòng)時(shí)，只要設(shè)定行號(hào)01的學(xué)生人數(shù)及行號(hào)05的陣列內(nèi)容即可。

2022/12/1217第二種方法是使用「陣列」資料結(jié)構(gòu)來(lái)存2022/12/161211-3何謂演算法?「演算法」在韋氏辭典中定義為：「在有限步驟內(nèi)解決數(shù)學(xué)問(wèn)題的程序」。我們可以把演算法(Algorithm)定義成：「解決問(wèn)題的方法」。它可以是利用文字?jǐn)⑹?、或流程圖或虛擬碼的方式，來(lái)表示解決問(wèn)題的步驟。2022/12/12181-3何謂演算法?「演算法」在韋氏2022/12/16122一、撰寫(xiě)演算法應(yīng)遵守五點(diǎn)原則：

1.輸入(Input)：不一定要有輸入?？赡軟](méi)有，也可能是多個(gè)資料輸入。

例如(1)：取得系統(tǒng)目前的時(shí)間，不須要輸入，只要寫(xiě)一行now()函數(shù)，就可以輸出系統(tǒng)時(shí)間。例如(2)：求某數(shù)為奇偶數(shù)時(shí)，則必須先要有一個(gè)整數(shù)輸入，才能進(jìn)行判斷。2022/12/1219一、撰寫(xiě)演算法應(yīng)遵守五點(diǎn)原則：1.2022/12/16123一、撰寫(xiě)演算法應(yīng)遵守五點(diǎn)原則：(續(xù))

2.輸出(Output)：至少一個(gè)輸出。

例如：在電腦中，處理資料的基本過(guò)程有三個(gè)步驟：

輸入處理輸出

(原始資料)(程式)(有用的資訊)

所以，使用電腦來(lái)為我們處理資料時(shí)，有可能是系統(tǒng)自動(dòng)接收到一個(gè)訊號(hào)，來(lái)當(dāng)作輸入資料，但是系統(tǒng)至少會(huì)輸出一項(xiàng)讓使用者參考的有用資訊。

2022/12/1220一、撰寫(xiě)演算法應(yīng)遵守五點(diǎn)原則：(續(xù)2022/12/16124一、撰寫(xiě)演算法應(yīng)遵守五點(diǎn)原則：(續(xù))

3.明確性(Definiteness)：每一行指令都必須明確，不可模稜兩可。例如：判斷某一數(shù)值是否為偶數(shù)。首先我們?cè)囍孟铝形淖謥?lái)加以描述：

(1)輸入一個(gè)正整數(shù)。

(2)作餘除運(yùn)算是否為0。

(3)為0即為偶數(shù)。以上描述看來(lái)似乎正確，但是從演算法觀點(diǎn)來(lái)看，其中的第(2)點(diǎn)並不符合「明確性」，因它並未說(shuō)明「餘除運(yùn)算」是如何運(yùn)算，容易造成混淆與不解。我們應(yīng)該改寫(xiě)為：

(1)輸入一個(gè)正整數(shù)N。

(2)如果N除以2，其餘數(shù)為0。

(3)則其N為偶數(shù)。不具明確性具明確性2022/12/1221一、撰寫(xiě)演算法應(yīng)遵守五點(diǎn)原則：(續(xù)2022/12/16125一、撰寫(xiě)演算法應(yīng)遵守五點(diǎn)原則：(續(xù))例如：「用功的學(xué)生才能領(lǐng)獎(jiǎng)學(xué)金」就不具有明確性，因?yàn)槊恳粋€(gè)人對(duì)用功的定義可能不盡相同，而如果改為「成績(jī)90以上的學(xué)生才能領(lǐng)獎(jiǎng)學(xué)金」就是具有明確性，因?yàn)?0分是一個(gè)比較客觀的定義。2022/12/1222一、撰寫(xiě)演算法應(yīng)遵守五點(diǎn)原則：(續(xù)2022/12/16126一、撰寫(xiě)演算法應(yīng)遵守五點(diǎn)原則：(續(xù))4.有限性(Finiteness)：演算法不能有無(wú)窮迴路，必須能終止執(zhí)行。由於演算法並非是真正可以執(zhí)行的程式，而是設(shè)計(jì)者所推演出解決問(wèn)題的步驟，因此，必須在有限的步驟內(nèi)要完成解決問(wèn)題的程序。但是，真正的程式是可以有無(wú)窮迴路的動(dòng)作。例如：Windows作業(yè)系統(tǒng)除非系統(tǒng)關(guān)機(jī)或當(dāng)機(jī)，否則它會(huì)永遠(yuǎn)執(zhí)行一個(gè)「等待迴圈」，來(lái)等待使用者從鍵盤輸入或其他的輸入設(shè)備。

2022/12/1223一、撰寫(xiě)演算法應(yīng)遵守五點(diǎn)原則：(續(xù)2022/12/16127一、撰寫(xiě)演算法應(yīng)遵守五點(diǎn)原則：(續(xù))5.正確性(Correctness)

：既然演算法是解決問(wèn)題的方法，因此，正確性是最基本的要求。例如：以下判斷某數(shù)為奇偶數(shù)的演算法，雖然符合「明確性」，但是

「不正確」，因?yàn)镹除以2，其餘數(shù)為0，則N應(yīng)該為「偶數(shù)」，而非「奇數(shù)」。

輸入一個(gè)正整數(shù)N。

如果N除以2，其餘數(shù)為0。

則其N為奇數(shù)。應(yīng)該改為「偶數(shù)」

2022/12/1224一、撰寫(xiě)演算法應(yīng)遵守五點(diǎn)原則：(續(xù)2022/12/16128【日常生活中的例子】一組可用來(lái)解決特定問(wèn)題的有限指令或步驟，依循這些指令或步驟，可以進(jìn)行解題。食譜-做蛋糕圖片來(lái)源：6/cornliu/cornppt/第六章.ppt2022/12/1225【日常生活中的例子】一組可用來(lái)解決特2022/12/16129好吃的蛋糕怎麼來(lái)?輸入輸出明確性正確性有限性圖片來(lái)源：6/cornliu/cornppt/第六章.ppt2022/12/1226好吃的蛋糕怎麼來(lái)?輸入輸出明確性2022/12/16130二、描述演算法有三種方法：(一)文字?jǐn)⑹鲅菟惴捎梦淖旨右悦枋?，但是?cǎi)用口語(yǔ)化的文字?jǐn)⑹鰜?lái)加以描述，其缺點(diǎn)在於冗長(zhǎng)且較不精確，在撰寫(xiě)、閱讀、會(huì)意時(shí)可能會(huì)有誤差，因此一般較不常用。

例如：請(qǐng)利用「文字?jǐn)⑹觥故褂谜叩侨霂ぬ?hào)與密碼時(shí)，系統(tǒng)檢查的過(guò)程。步驟一：輸入使用者帳號(hào)與密碼步驟二：判斷帳號(hào)與密碼是否正確步驟三：如果正確時(shí)，則可以登入系統(tǒng)否則，就無(wú)法登入！2022/12/1227二、描述演算法有三種方法：(一)文字2022/12/16131(二)流程圖（Flowchart）『流程圖』是指利用圖形方式來(lái)表達(dá)欲解決問(wèn)題的步驟。當(dāng)我們想利用電腦程式語(yǔ)言來(lái)處理問(wèn)題時(shí)，先要了解問(wèn)題並想出許多方案來(lái)解決問(wèn)題，並且分析那些資料是要「輸入」，經(jīng)過(guò)「處理」之後，要「輸出」那些結(jié)果。

2022/12/1228(二)流程圖（Flowchart）2022/12/161322022/12/12292022/12/161332022/12/12302022/12/16134【舉例】請(qǐng)繪出使用者登入帳號(hào)與密碼時(shí)，系統(tǒng)檢查的流程圖。2022/12/1231【舉例】請(qǐng)繪出使用者登入帳號(hào)與密碼時(shí)2022/12/16135(三)虛擬碼（PseudoCode）虛擬碼兼具文字描述及流程圖的優(yōu)點(diǎn)，其方式是用文字摻雜程式語(yǔ)言，來(lái)描述解題步驟與方法。例如1：請(qǐng)利用「虛擬碼（PseudoCode）」敘述使用者登入帳號(hào)與密碼時(shí)，系統(tǒng)檢查的過(guò)程。(1)Input:UserName,Password(2)IF(UserNameAndPassword)ALLTrueOutput:YouCanPass!elseOutput:YouCannotPass!2022/12/1232(三)虛擬碼（PseudoCode2022/12/16136例如：1+2+3+…+10虛擬碼可以描述如下：(1)設(shè)Count=1,Total=0;(2)Total=Total+Count;(3)Count=Count+1;(4)若Count>10則至步驟(5)，否則回步驟(2)(5)印出Total2022/12/1233例如：1+2+3+…+10虛擬碼可以2022/12/161371-4程式設(shè)計(jì)概念我們要開(kāi)始程式設(shè)計(jì)時(shí)，一定要進(jìn)行下面五個(gè)步驟：2022/12/12341-4程式設(shè)計(jì)概念我們要開(kāi)始程式2022/12/161382022/12/12352022/12/161392022/12/12362022/12/16140〔實(shí)例〕計(jì)算國(guó)文與英文的平均成績(jī)，並依照平均成績(jī)來(lái)求顯示「及格」與「不及格」。1.分析及定義問(wèn)題。兩個(gè)等級(jí)分別如下：

(1)及格：60(含)以上。

(2)不及格：60以下。2.畫(huà)出整合問(wèn)題的流程圖或撰寫(xiě)問(wèn)題的演算法。2022/12/1237〔實(shí)例〕計(jì)算國(guó)文與英文的平均成績(jī)，並2022/12/161413.撰寫(xiě)及建立程式模組。2022/12/12383.撰寫(xiě)及建立程式模組。2022/12/161424.對(duì)每一個(gè)程式模組進(jìn)行測(cè)試及除錯(cuò)，直到?jīng)]有錯(cuò)誤為止。當(dāng)使用者輸入國(guó)文為60分，英文為61分時(shí)，是否可以計(jì)算出平均成績(jī)?yōu)?0.5，如果沒(méi)有則必須要進(jìn)行除錯(cuò)，亦即要將Average的資料型態(tài)改為Single(單精準(zhǔn)度)2022/12/12394.對(duì)每一個(gè)程式模組進(jìn)行測(cè)試及除錯(cuò)，2022/12/16143【重要觀念】

系統(tǒng)發(fā)展的生命週期與程式設(shè)計(jì)之步驟比較2022/12/1240【重要觀念】系統(tǒng)發(fā)展的生命週期2022/12/161441-4.1演算法與程式的差異？1.「演算法」是以「人」為主，亦即「任何人都可以閱讀的程式碼」，因此，必須特別強(qiáng)調(diào)「可讀性」。2.「程式」則是以「電腦」為主，它強(qiáng)調(diào)程式的執(zhí)行結(jié)果正確性、可維護(hù)性及執(zhí)行效率。2022/12/12411-4.1演算法與程式的差異？1.2022/12/161451-4.2為什麼要撰寫(xiě)程式?我們?yōu)槭颤N要花那麼多時(shí)間來(lái)撰寫(xiě)程式呢？其主要的目的：它可以快速解決「複雜的問(wèn)題」。甲同學(xué)說(shuō)：請(qǐng)電腦幫我計(jì)算1加到10的總合?；蛟S你會(huì)認(rèn)為這簡(jiǎn)單的問(wèn)題，你我都會(huì)算，何必寫(xiě)程式呢？但是，如果甲同學(xué)又說(shuō)：請(qǐng)電腦幫我計(jì)算1加到50000時(shí)，我想我們就無(wú)法馬上計(jì)算出結(jié)果。由上面的例子，我們可以非常清楚的知道，程式語(yǔ)言幫忙人類解決複雜的問(wèn)題。2022/12/12421-4.2為什麼要撰寫(xiě)程式?我們?yōu)槭?022/12/161461-5結(jié)構(gòu)化程式設(shè)計(jì)何謂結(jié)構(gòu)化程式設(shè)計(jì)呢？它是利用「由上而下」的技巧，將程式分解成多個(gè)具有獨(dú)立功能的模組。如圖1-5所示。圖1-5結(jié)構(gòu)化程式設(shè)計(jì)的示意圖2022/12/12431-5結(jié)構(gòu)化程式設(shè)計(jì)何謂結(jié)構(gòu)化程2022/12/16147結(jié)構(gòu)化程式設(shè)計(jì)由Dijkstra(1969)提出：1.消除程式因goto而造成如麵條式的混亂狀態(tài)。2.強(qiáng)調(diào)任何程式邏輯均可由三種結(jié)構(gòu)組成。如圖1-6所示。

(1)循序(Sequence)：簡(jiǎn)單命令式的指令如COMPUTE,READ,WRITE與代數(shù)指令如X=Y+Z。

(2)選擇(Condition)：需做決策時(shí)，用IF-THEN-ELSE指令與

CASE指令。

(3)重複(Repetition)：當(dāng)需反覆時(shí)，用DO-WHILE

與

DO-UNTIL指令。2022/12/1244結(jié)構(gòu)化程式設(shè)計(jì)由Dijkstra(2022/12/161482022/12/12452022/12/161491-5.1循序結(jié)構(gòu)所謂循序結(jié)構(gòu)，是指程式由上而下，依序逐一執(zhí)行。亦即『程式碼被執(zhí)行的順序?yàn)橛缮隙?，一個(gè)敘述接著一個(gè)敘述依序執(zhí)行』。此種結(jié)構(gòu)是最基本的結(jié)構(gòu)。如圖1-7所示：2022/12/12461-5.1循序結(jié)構(gòu)所謂循序結(jié)構(gòu)，是2022/12/161501-5.2選擇結(jié)構(gòu)如果只希望在某種條件成立時(shí)才執(zhí)行某些敘述，而某種條件不成立才執(zhí)行另一種敘述，來(lái)過(guò)濾一些條件。那我們就必須使用「選擇結(jié)構(gòu)」的方式了。如圖1-8所示。

2022/12/12471-5.2選擇結(jié)構(gòu)如果只希望在某2022/12/16151此種結(jié)構(gòu)是最常被使用的方式，因?yàn)榇蟛糠莸倪x擇結(jié)構(gòu)的情況可能是兩種。例如：判斷及格與不及格、判斷奇數(shù)與偶數(shù)、判斷男生與女生

…等情況，都可以利用此種結(jié)構(gòu)來(lái)完成。2022/12/1248此種結(jié)構(gòu)是最常被使用的方式，因?yàn)榇蟛?022/12/161521.語(yǔ)法：其中(條件式)

是一關(guān)係運(yùn)算式或邏輯運(yùn)算式2.說(shuō)明：如果「條件式」成立(真)，就執(zhí)行Then後面的「敘述區(qū)塊1」，否則就執(zhí)行「敘述區(qū)塊2」。3.使用時(shí)機(jī)：當(dāng)條件只有二種情況時(shí)最佳方法。2022/12/12491.語(yǔ)法：2022/12/161535.流程圖：如圖1-9所示：2022/12/12505.流程圖：如圖1-9所示：2022/12/161541-5.3重複結(jié)構(gòu)

在處理一再重複的相同動(dòng)作，這對(duì)電腦而言，是一件非常Easy的事，但對(duì)我們?nèi)祟惗詤s是一件苦差事，因此驅(qū)使電腦做這樣的事情的方式，就是迴圈(Loop)，亦即讓某一段程式反覆執(zhí)行多次的敘述，我們稱此結(jié)構(gòu)為「迴圈結(jié)構(gòu)」。2022/12/12511-5.3重複結(jié)構(gòu)在2022/12/16155如果我們想要撰寫(xiě)一段程式，來(lái)輸出1,2,…,100時(shí)，怎麼辦？目前最少有兩種方法可以使用。如圖1-10所示：2022/12/1252如果我們想要撰寫(xiě)一段程式，來(lái)輸出1,2022/12/161561-6物件導(dǎo)向程式設(shè)計(jì)(選讀)

物件導(dǎo)向設(shè)計(jì)是以「物件」為主，首先規(guī)劃整個(gè)系統(tǒng)需要那些物件，再分析這些物件有什麼特性(屬性)、如何操作(方法)，以及物件與物件之間的關(guān)連性，然後開(kāi)始撰寫(xiě)各個(gè)物件模組，最後再依照系統(tǒng)的需求，將各個(gè)封裝良好的物件模組由下向上架構(gòu)出整個(gè)系統(tǒng)。2022/12/12531-6物件導(dǎo)向程式設(shè)計(jì)(選讀)2022/12/16157每一個(gè)物件模組就是一個(gè)定義好的類別，其內(nèi)容包括一些私有的資料項(xiàng)目和功能(即屬性)，以及供外界來(lái)操作的一些方法。如圖1-11所示。2022/12/1254每一個(gè)物件模組就是一個(gè)定義好的類別，2022/12/161581-6.1物