資料結(jié)構(gòu)導(dǎo)論課件

資料結(jié)構(gòu)

DataStructurechapter11.資料結(jié)構(gòu)

DataStructurechapter11.課程資訊Lecturer:江政杰Office:四合院301URL:.tw/plutoMail:pluto@.tw課程網(wǎng)頁(yè)URL:.tw/pluto/ds/ds.html教材、補(bǔ)充資訊作業(yè)相關(guān)連結(jié)2.課程資訊Lecturer:江政杰2.課程資訊TextBook:資料結(jié)構(gòu)–使用C語(yǔ)言

李春雄著上奇出版社成績(jī)?cè)u(píng)量期中、期末各佔(zhàn)30%、平時(shí)成績(jī)佔(zhàn)40%3.課程資訊TextBook:3.課程內(nèi)容資料結(jié)構(gòu)與演算法遞迴Recursion陣列Array堆疊Stack佇列Queue鏈結(jié)串列LinkedList樹(shù)狀結(jié)構(gòu)TreeStructure圖形GraphStructure排序Sorting搜尋Search4.課程內(nèi)容資料結(jié)構(gòu)與演算法4.修課基礎(chǔ)程式撰寫(xiě)對(duì)於變數(shù)、函數(shù)、陣列等基本程式語(yǔ)言的使用與掌握對(duì)於一個(gè)問(wèn)題，可以在找出解決方法之後，撰寫(xiě)出程式碼具備邏輯概念學(xué)習(xí)程式除了語(yǔ)法的熟悉外，最重要的是邏輯概念的訓(xùn)練，才有能力學(xué)習(xí)其他語(yǔ)言還無(wú)法順利掌握程式撰寫(xiě)??以資料結(jié)構(gòu)這門(mén)課程為程式設(shè)計(jì)的進(jìn)階訓(xùn)練程式設(shè)計(jì)能力的再次訓(xùn)練5.修課基礎(chǔ)程式撰寫(xiě)5.上課方式投影片展示，請(qǐng)自行搭配課本閱讀實(shí)例練習(xí)在課程中會(huì)搭配一些程式範(fàn)例，讓同學(xué)實(shí)際操作程式之撰寫(xiě)，以掌握程式撰寫(xiě)的能力作業(yè)練習(xí)每一段時(shí)間，會(huì)有一完整的題目要求撰寫(xiě)程式，計(jì)入平時(shí)成績(jī)內(nèi)期中、期末考試6.上課方式投影片展示，請(qǐng)自行搭配課本閱讀6.學(xué)習(xí)程式入門(mén)學(xué)習(xí)VB、DevC++等軟體的使用熟悉VB、C的語(yǔ)法撰寫(xiě)進(jìn)階學(xué)習(xí)資料結(jié)構(gòu)與演算法深入最好的練習(xí)就是實(shí)際克服困難的題目這學(xué)期的範(fàn)圍7.學(xué)習(xí)程式入門(mén)這學(xué)期的範(fàn)圍7.程式的組成資料：在程式中以變數(shù)的型態(tài)出現(xiàn)，每個(gè)變數(shù)都在記憶體有一席之地，包含變數(shù)型態(tài)：決定所佔(zhàn)記憶體的長(zhǎng)度變數(shù)值：實(shí)際的變數(shù)資料值變數(shù)位址：系統(tǒng)處理程序：即if、loop等程式語(yǔ)法與流程I/O：輸入與輸出，如scanf與printf輸入處理輸出8.程式的組成資料：在程式中以變數(shù)的型態(tài)出現(xiàn)，每個(gè)變數(shù)都在記憶體練習(xí)請(qǐng)撰寫(xiě)一個(gè)程式，可以顯示九九乘法表以?xún)蓪愚捜Ψ绞教幚硐饶軌蝻@示正確結(jié)果，才思考如何排的漂亮先示範(fàn)…9.練習(xí)請(qǐng)撰寫(xiě)一個(gè)程式，可以顯示九九乘法表9.資料與資訊資料是客觀存在的、具體的、事實(shí)的記錄資訊經(jīng)過(guò)資料處理之後的結(jié)果即為資訊資料資訊p1-210.資料與資訊資料資料資訊p1-210.資料結(jié)構(gòu)的概念當(dāng)我們解決問(wèn)題時(shí)，還沒(méi)開(kāi)始實(shí)際寫(xiě)程式，必須先規(guī)劃程式如何撰寫(xiě)I/O：輸入輸出的格式與資料內(nèi)容程序：處理的方法(演算法)資料：決定此問(wèn)題會(huì)用到那些類(lèi)型的資料有效率的程式=資料結(jié)構(gòu)+演算法所謂的資料結(jié)構(gòu)，就是針對(duì)一個(gè)問(wèn)題，決定如何設(shè)計(jì)資料部份，尤其是適合此問(wèn)題的特殊資料類(lèi)型資料在記憶體中的儲(chǔ)存方式11.資料結(jié)構(gòu)的概念當(dāng)我們解決問(wèn)題時(shí)，還沒(méi)開(kāi)始實(shí)際寫(xiě)程式，必須先規(guī)資料結(jié)構(gòu)的概念在任何問(wèn)題中，資料元素都不是孤立存在，彼此之間存在某些邏輯關(guān)係，這種關(guān)係可稱(chēng)為結(jié)構(gòu)(structure)，種類(lèi)有集合：元素間沒(méi)有次序性線(xiàn)性結(jié)構(gòu)：陣列、串列、佇列、堆疊樹(shù)狀結(jié)構(gòu)圖形結(jié)構(gòu)12.資料結(jié)構(gòu)的概念在任何問(wèn)題中，資料元素都不是孤立存在，彼此之間範(fàn)例說(shuō)明寫(xiě)一個(gè)程式計(jì)算五個(gè)同學(xué)的平均成績(jī)p1-513.範(fàn)例說(shuō)明寫(xiě)一個(gè)程式計(jì)算五個(gè)同學(xué)的平均成績(jī)p1-513.演算法的五原則演算法(Algorithm):解決問(wèn)題的方法輸入(Input)不一定要有輸入。可能沒(méi)有，也可能是多個(gè)資料輸入。p1-7例如(1)：取得系統(tǒng)目前的時(shí)間，不須要輸入，只要寫(xiě)一行now()函數(shù)，就可以輸出系統(tǒng)時(shí)間例如(2)：求某數(shù)為奇偶數(shù)時(shí)，則必須先要有一個(gè)整數(shù)輸入，才能運(yùn)算輸出(Output)至少要有一個(gè)輸出明確性(Definiteness)每一行指令都必須明確，不可模稜兩可「用功的學(xué)生才能領(lǐng)獎(jiǎng)學(xué)金」就不具有明確性，因?yàn)槊恳粋€(gè)人對(duì)用功的定義可能不盡相同。而如果改為「成績(jī)90以上的學(xué)生才能領(lǐng)獎(jiǎng)學(xué)金」就是具有明確性，因?yàn)?0分是一個(gè)比較客觀的定義。14.演算法的五原則演算法(Algorithm):解決問(wèn)題的方法演算法的五原則有限性(Finiteness)演算法不能有無(wú)窮迴路，必須能終止執(zhí)行由於演算法並非是真正可以執(zhí)行的程式，而是設(shè)計(jì)者所推演出解決問(wèn)題的步驟，因此，必須在有限的步驟內(nèi)要完成解決問(wèn)題的程序真正的程式是可以有無(wú)窮迴路的動(dòng)作正確性(Correctness)既然演算法是解決問(wèn)題的方法，因此正確性是最基本的要求15.演算法的五原則有限性(Finiteness)15.演算法的範(fàn)例演算法:一組可用來(lái)解決特定問(wèn)題的有限指令或步驟依循這些指令或步驟，可以完成工作案例:做蛋糕16.演算法的範(fàn)例演算法:16.演算法的範(fàn)例好吃的蛋糕怎麼來(lái)?輸入輸出明確性正確性有限性17.演算法的範(fàn)例好吃的蛋糕怎麼來(lái)?輸入輸出明確性正確性有限描述演算法的三種方法文字採(cǎi)用口語(yǔ)化的文字?jǐn)⑹鰜?lái)加以描述，容易冗長(zhǎng)且較不精確，在撰寫(xiě)、閱讀、會(huì)意時(shí)可能會(huì)有誤差，因此一般較不常用p1-10例如：請(qǐng)利用「文字?jǐn)⑹觥故褂谜叩侨霂ぬ?hào)與密碼時(shí)，系統(tǒng)檢查的過(guò)程。步驟一：輸入使用者帳號(hào)與密碼步驟二：判斷帳號(hào)與密碼是否正確步驟三：如果正確時(shí)，則可以登入系統(tǒng)否則，就無(wú)法登入！18.描述演算法的三種方法文字p1-10例如：請(qǐng)利用「文字?jǐn)⑹觥故姑枋鲅菟惴ǖ娜N方法流程圖利用圖形方式來(lái)表達(dá)欲解決問(wèn)題的步驟19.描述演算法的三種方法流程圖19.描述演算法的三種方法虛擬碼使用文字摻雜程式語(yǔ)言，來(lái)描述解題步驟與方法兼具文字描述及流程圖的優(yōu)點(diǎn)//登錄帳號(hào)密碼的檢查(1)Input:UserName,Password(2)IF(UserNameAndPassword)ALLTrueOutput:YouCanPass!elseOutput:YouCannotPass!//計(jì)算1+2+3+…+10(1)設(shè)Count=1,Total=0;(2)Total=Total+Count;(3)Count=Count+1;(4)若Count>10則至步驟(5)，否則回步驟(2)(5)印出Total不是可以執(zhí)行的指令只是說(shuō)明程式處理的流程20.描述演算法的三種方法虛擬碼//登錄帳號(hào)密碼的檢查//計(jì)算1+程式設(shè)計(jì)概念p1-1421.程式設(shè)計(jì)概念p1-1421.程式設(shè)計(jì)概念22.程式設(shè)計(jì)概念22.程式設(shè)計(jì)概念系統(tǒng)發(fā)展的生命週期與程式設(shè)計(jì)之步驟比較23.程式設(shè)計(jì)概念系統(tǒng)發(fā)展的生命週期與程式設(shè)計(jì)之步驟比較23程式設(shè)計(jì)範(fàn)例題目計(jì)算國(guó)文與英文的平均成績(jī)，並依照平均成績(jī)來(lái)求顯示「及格」與「不及格」1.分析及定義問(wèn)題。兩個(gè)等級(jí)分別如下：(1)及格：60(含)以上。(2)不及格：60以下。2.畫(huà)出整合問(wèn)題的流程圖或撰寫(xiě)問(wèn)題的演算法24.程式設(shè)計(jì)範(fàn)例題目1.分析及定義問(wèn)題。24.3.撰寫(xiě)及建立程式模組4.對(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)改為float(浮點(diǎn)數(shù))25.3.撰寫(xiě)及建立程式模組4.對(duì)每一個(gè)程式模組進(jìn)行測(cè)試及除錯(cuò)，直結(jié)構(gòu)化程式設(shè)計(jì)利用「由上而下」的技巧，將程式分解成多個(gè)具有獨(dú)立功能的模組強(qiáng)調(diào)任何程式邏輯均可由三種結(jié)構(gòu)組成循序(Sequence)：簡(jiǎn)單命令式的指令如X=Y+Z選擇(Condition)：做決策使用if-then-elseselectcase/switch重複(Repetition)：重複執(zhí)行do-whiledo-untilforp1-18循序選擇重複26.結(jié)構(gòu)化程式設(shè)計(jì)利用「由上而下」的技巧，將程式分解成多個(gè)具有獨(dú)演算法、資料結(jié)構(gòu)、程式演算法整個(gè)問(wèn)題的解決方法，以邏輯方式描述以文字、或虛擬碼方式，撰寫(xiě)整個(gè)程式的流程可對(duì)應(yīng)到程式的撰寫(xiě)，但是與程式語(yǔ)言的選擇無(wú)關(guān)資料結(jié)構(gòu)要解決問(wèn)題時(shí)所需要的資料，以及資料彼此之間的關(guān)連與結(jié)構(gòu)著重在資料的表現(xiàn)、資料之間的結(jié)構(gòu)關(guān)係程式實(shí)際可以執(zhí)行真實(shí)的解決問(wèn)題，以符合程式語(yǔ)言的規(guī)範(fàn)完成不同程式語(yǔ)言有不同的撰寫(xiě)方法，但是彼此的基本概念卻很相似27.演算法、資料結(jié)構(gòu)、程式演算法27.演算法、資料結(jié)構(gòu)、程式在討論問(wèn)題的解決方案時(shí)，大多以演算法搭配資料結(jié)構(gòu)為溝通的工具直接以程式語(yǔ)言討論太過(guò)於瑣碎程式撰寫(xiě)是基本的技能，更進(jìn)階的是針對(duì)特定問(wèn)題採(cǎi)用適當(dāng)?shù)馁Y料結(jié)構(gòu)設(shè)計(jì)有效率的演算法解決所面對(duì)的問(wèn)題有效率的演算法用較少的記憶體空間完成處理同一個(gè)問(wèn)題用較少的執(zhí)行時(shí)間完成處理同一個(gè)問(wèn)題28.演算法、資料結(jié)構(gòu)、程式在討論問(wèn)題的解決方案時(shí)，大多以演算法搭演算法的時(shí)間效率程式的執(zhí)行速度受到哪些因素影響程式需要執(zhí)行的指令數(shù)量CPU的速度電腦架構(gòu)例如記憶體大小等其他例如編譯程式的效率等演算法的設(shè)計(jì)並不考慮程式語(yǔ)言與硬體架構(gòu)，因此以指令數(shù)量為評(píng)估效率的主要依據(jù)Q:怎麼計(jì)算一個(gè)演算法的指令數(shù)量基本上是無(wú)法精確計(jì)算需要之指令數(shù)量，why?那該怎麼評(píng)估一個(gè)演算法所需的指令數(shù)量p1-2229.演算法的時(shí)間效率程式的執(zhí)行速度受到哪些因素影響p1-2229程式中指令數(shù)目的計(jì)算循序結(jié)構(gòu)(一般指令)例如:x=x+1每個(gè)指令執(zhí)行一次決策分支結(jié)構(gòu)(if)例如:if(x>1)then...只有條件為正時(shí)才會(huì)執(zhí)行重複結(jié)構(gòu)(loop)例如:fori=1to100迴圈內(nèi)的指令重複100次真正計(jì)算指令數(shù)量有困難，但是從以上三個(gè)結(jié)構(gòu)來(lái)看，顯然迴圈內(nèi)的執(zhí)行數(shù)量是重點(diǎn)Q:計(jì)算下列程式中變數(shù)Count被執(zhí)行的次數(shù)為何30.程式中指令數(shù)目的計(jì)算循序結(jié)構(gòu)(一般指令)Q:計(jì)算下列程式中迴圈敘述的頻率計(jì)數(shù)1.先根據(jù)「迴圈計(jì)數(shù)器」的範(fàn)圍算出迴圈重複的次數(shù)2.再乘上迴圈內(nèi)的行數(shù)。下列的程式片段，計(jì)算10組整數(shù)除法的商數(shù)及餘數(shù)1. Fori=0To92. Q=m[i]/n[i]3. R=m[i]Modn[i];4. Console.WriteLine(“{0}/{1}={2}…{3}”,m[i],n[i],Q,R)5. Next迴圈重複的次數(shù)為10次，迴圈內(nèi)有3個(gè)敘述，因此第2行到第4行（迴圈的主體）的頻率計(jì)數(shù)為30(=103)。第1行for迴圈的頭會(huì)執(zhí)行11次，前10次造成迴圈主體的重複執(zhí)行，第11次發(fā)現(xiàn)條件不符而離開(kāi)迴圈。因此整個(gè)迴圈（迴圈的頭加上迴圈的主體）的頻率計(jì)數(shù)為41(=11+30)。31.迴圈敘述的頻率計(jì)數(shù)1.先根據(jù)「迴圈計(jì)數(shù)器」的範(fàn)圍算出迴圈重【舉例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)迴圈。32.【舉例1】【解析】行號(hào)04會(huì)執(zhí)行n+1次，而前n次會(huì)執(zhí)行迴圈【舉例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次)33.【舉例2】【解析】行號(hào)04外層迴圈(for)的計(jì)數(shù)器i從0~【舉例3】假設(shè)兩矩陣a,b相乘，並且矩陣大小皆為n*n，相加請(qǐng)計(jì)算出下列程式的執(zhí)行次數(shù)34.【舉例3】34.雙層迴圈、內(nèi)圈不固定次數(shù)

1

Fori=1Ton 2 Forj=i+1Ton 3result+=14Next5Next

由於內(nèi)圈迴圈計(jì)數(shù)器j的範(fàn)圍，是隨著外圈迴圈計(jì)數(shù)器i的範(fàn)圍改變的，因此我們針對(duì)迴圈計(jì)數(shù)器i的變化來(lái)分析：

35.雙層迴圈、內(nèi)圈不固定次數(shù)35.數(shù)學(xué)式：總次數(shù)＝i的值j的範(fàn)圍第3行執(zhí)行次數(shù)12……nn-123……nn-234……nn-3……

n-1n……n1nn+1……n0總次數(shù)＝(n-1)+(n-2)+…+1=n*(n-1)/2

=

=

=

n2–

=36.數(shù)學(xué)式：i的值j的範(fàn)圍第3行執(zhí)行次數(shù)1n-123……範(fàn)例：計(jì)算n階乘(n!)的函式

1Functionfactor(ByValnAsInteger)AsInteger 2 Dimi,resultAsInteger 3

result=1 4

i=1 5

Dowhilei<=n 6

result=result*i; 7

i+=1; 8

Loop 9

Returnresult 10EndFunction37.範(fàn)例：計(jì)算n階乘(n!)的函式37.我們計(jì)算每一行敘述被執(zhí)行的次數(shù)：行號(hào)n>0時(shí)n<=0時(shí)1112113n+115n06n0811總次數(shù)3n+44

如果n>0，頻率計(jì)數(shù)為3n+4次，如果n<=0，頻率計(jì)數(shù)為4次多1次為最後一次比較條件不成立如果更複雜的程式，似乎很難真的計(jì)算出指令的數(shù)量仔細(xì)觀察，3n+4的值重點(diǎn)在n是多少，當(dāng)n很大時(shí)，4其實(shí)不重要一般計(jì)算時(shí)，主要依據(jù)n的狀況，也就是迴圈的層次38.我們計(jì)算每一行敘述被執(zhí)行的次數(shù)：行號(hào)n>0時(shí)n<=0Big-OBig-O符號(hào)的數(shù)學(xué)定義為：若且唯若f(n)=O(g(n))則存在大於0的常數(shù)c和n0，使得對(duì)所有的n值，當(dāng)n≧n0時(shí)，f(n)≦c*g(n)均成立。用數(shù)學(xué)式表示為：f(n)=O(g(n))

c,n0>0

n≧n0,f(n)≦c*g(n)用口語(yǔ)解釋為：f(n)取Big-O符號(hào)為O(g(n))，當(dāng)n夠大的時(shí)候，g(n)相當(dāng)於是f(n)的上限

nn0f(n)c*g(n)用圖示可表達(dá)為：

39.Big-OBig-O符號(hào)的數(shù)學(xué)定義為：若且唯若f(n)=◎5n2+6n+9＝O(n2)→f(n)=5n2+6n+9,g(n)=n2→f函數(shù)取Big-O符號(hào)為g函數(shù)→5n2+6n+9取Big-O符號(hào)為O(n2)◎

3nlgn+9n+10=O(nlgn)，因?yàn)閚lgn的次數(shù)比n大，取最高次項(xiàng)而不計(jì)係數(shù)時(shí)，自然取到nlgn(lgn=log2n)◎9n2+6nlgn+9=O(n2)，因?yàn)閚2的次數(shù)最大，取最高次項(xiàng)而不計(jì)係數(shù)時(shí)，自然取到n2

◎

19n3+9n2+6n+9=O(n3)，因?yàn)閚3的次數(shù)最大，取最高次項(xiàng)而不計(jì)係數(shù)時(shí)，自然取到n340.◎5n2+6n+9＝O(n2)◎3nl41.41.2nn3n2nlgnnlgn1248163264128將各種複雜度隨n值變化的結(jié)果繪成圖表，以便了解複雜度對(duì)程式效能的影響有多大：(X軸代表n值的成長(zhǎng)，Y軸代表g(n)值的成長(zhǎng))2521021522022523042.2nn3n2nlgnnlgn1248163264128將各種資料結(jié)構(gòu)

DataStructurechapter143.資料結(jié)構(gòu)

DataStructurechapter11.課程資訊Lecturer:江政杰Office:四合院301URL:.tw/plutoMail:pluto@.tw課程網(wǎng)頁(yè)URL:.tw/pluto/ds/ds.html教材、補(bǔ)充資訊作業(yè)相關(guān)連結(jié)44.課程資訊Lecturer:江政杰2.課程資訊TextBook:資料結(jié)構(gòu)–使用C語(yǔ)言

李春雄著上奇出版社成績(jī)?cè)u(píng)量期中、期末各佔(zhàn)30%、平時(shí)成績(jī)佔(zhàn)40%45.課程資訊TextBook:3.課程內(nèi)容資料結(jié)構(gòu)與演算法遞迴Recursion陣列Array堆疊Stack佇列Queue鏈結(jié)串列LinkedList樹(shù)狀結(jié)構(gòu)TreeStructure圖形GraphStructure排序Sorting搜尋Search46.課程內(nèi)容資料結(jié)構(gòu)與演算法4.修課基礎(chǔ)程式撰寫(xiě)對(duì)於變數(shù)、函數(shù)、陣列等基本程式語(yǔ)言的使用與掌握對(duì)於一個(gè)問(wèn)題，可以在找出解決方法之後，撰寫(xiě)出程式碼具備邏輯概念學(xué)習(xí)程式除了語(yǔ)法的熟悉外，最重要的是邏輯概念的訓(xùn)練，才有能力學(xué)習(xí)其他語(yǔ)言還無(wú)法順利掌握程式撰寫(xiě)??以資料結(jié)構(gòu)這門(mén)課程為程式設(shè)計(jì)的進(jìn)階訓(xùn)練程式設(shè)計(jì)能力的再次訓(xùn)練47.修課基礎(chǔ)程式撰寫(xiě)5.上課方式投影片展示，請(qǐng)自行搭配課本閱讀實(shí)例練習(xí)在課程中會(huì)搭配一些程式範(fàn)例，讓同學(xué)實(shí)際操作程式之撰寫(xiě)，以掌握程式撰寫(xiě)的能力作業(yè)練習(xí)每一段時(shí)間，會(huì)有一完整的題目要求撰寫(xiě)程式，計(jì)入平時(shí)成績(jī)內(nèi)期中、期末考試48.上課方式投影片展示，請(qǐng)自行搭配課本閱讀6.學(xué)習(xí)程式入門(mén)學(xué)習(xí)VB、DevC++等軟體的使用熟悉VB、C的語(yǔ)法撰寫(xiě)進(jìn)階學(xué)習(xí)資料結(jié)構(gòu)與演算法深入最好的練習(xí)就是實(shí)際克服困難的題目這學(xué)期的範(fàn)圍49.學(xué)習(xí)程式入門(mén)這學(xué)期的範(fàn)圍7.程式的組成資料：在程式中以變數(shù)的型態(tài)出現(xiàn)，每個(gè)變數(shù)都在記憶體有一席之地，包含變數(shù)型態(tài)：決定所佔(zhàn)記憶體的長(zhǎng)度變數(shù)值：實(shí)際的變數(shù)資料值變數(shù)位址：系統(tǒng)處理程序：即if、loop等程式語(yǔ)法與流程I/O：輸入與輸出，如scanf與printf輸入處理輸出50.程式的組成資料：在程式中以變數(shù)的型態(tài)出現(xiàn)，每個(gè)變數(shù)都在記憶體練習(xí)請(qǐng)撰寫(xiě)一個(gè)程式，可以顯示九九乘法表以?xún)蓪愚捜Ψ绞教幚硐饶軌蝻@示正確結(jié)果，才思考如何排的漂亮先示範(fàn)…51.練習(xí)請(qǐng)撰寫(xiě)一個(gè)程式，可以顯示九九乘法表9.資料與資訊資料是客觀存在的、具體的、事實(shí)的記錄資訊經(jīng)過(guò)資料處理之後的結(jié)果即為資訊資料資訊p1-252.資料與資訊資料資料資訊p1-210.資料結(jié)構(gòu)的概念當(dāng)我們解決問(wèn)題時(shí)，還沒(méi)開(kāi)始實(shí)際寫(xiě)程式，必須先規(guī)劃程式如何撰寫(xiě)I/O：輸入輸出的格式與資料內(nèi)容程序：處理的方法(演算法)資料：決定此問(wèn)題會(huì)用到那些類(lèi)型的資料有效率的程式=資料結(jié)構(gòu)+演算法所謂的資料結(jié)構(gòu)，就是針對(duì)一個(gè)問(wèn)題，決定如何設(shè)計(jì)資料部份，尤其是適合此問(wèn)題的特殊資料類(lèi)型資料在記憶體中的儲(chǔ)存方式53.資料結(jié)構(gòu)的概念當(dāng)我們解決問(wèn)題時(shí)，還沒(méi)開(kāi)始實(shí)際寫(xiě)程式，必須先規(guī)資料結(jié)構(gòu)的概念在任何問(wèn)題中，資料元素都不是孤立存在，彼此之間存在某些邏輯關(guān)係，這種關(guān)係可稱(chēng)為結(jié)構(gòu)(structure)，種類(lèi)有集合：元素間沒(méi)有次序性線(xiàn)性結(jié)構(gòu)：陣列、串列、佇列、堆疊樹(shù)狀結(jié)構(gòu)圖形結(jié)構(gòu)54.資料結(jié)構(gòu)的概念在任何問(wèn)題中，資料元素都不是孤立存在，彼此之間範(fàn)例說(shuō)明寫(xiě)一個(gè)程式計(jì)算五個(gè)同學(xué)的平均成績(jī)p1-555.範(fàn)例說(shuō)明寫(xiě)一個(gè)程式計(jì)算五個(gè)同學(xué)的平均成績(jī)p1-513.演算法的五原則演算法(Algorithm):解決問(wèn)題的方法輸入(Input)不一定要有輸入?？赡軟](méi)有，也可能是多個(gè)資料輸入。p1-7例如(1)：取得系統(tǒng)目前的時(shí)間，不須要輸入，只要寫(xiě)一行now()函數(shù)，就可以輸出系統(tǒng)時(shí)間例如(2)：求某數(shù)為奇偶數(shù)時(shí)，則必須先要有一個(gè)整數(shù)輸入，才能運(yùn)算輸出(Output)至少要有一個(gè)輸出明確性(Definiteness)每一行指令都必須明確，不可模稜兩可「用功的學(xué)生才能領(lǐng)獎(jiǎng)學(xué)金」就不具有明確性，因?yàn)槊恳粋€(gè)人對(duì)用功的定義可能不盡相同。而如果改為「成績(jī)90以上的學(xué)生才能領(lǐng)獎(jiǎng)學(xué)金」就是具有明確性，因?yàn)?0分是一個(gè)比較客觀的定義。56.演算法的五原則演算法(Algorithm):解決問(wèn)題的方法演算法的五原則有限性(Finiteness)演算法不能有無(wú)窮迴路，必須能終止執(zhí)行由於演算法並非是真正可以執(zhí)行的程式，而是設(shè)計(jì)者所推演出解決問(wèn)題的步驟，因此，必須在有限的步驟內(nèi)要完成解決問(wèn)題的程序真正的程式是可以有無(wú)窮迴路的動(dòng)作正確性(Correctness)既然演算法是解決問(wèn)題的方法，因此正確性是最基本的要求57.演算法的五原則有限性(Finiteness)15.演算法的範(fàn)例演算法:一組可用來(lái)解決特定問(wèn)題的有限指令或步驟依循這些指令或步驟，可以完成工作案例:做蛋糕58.演算法的範(fàn)例演算法:16.演算法的範(fàn)例好吃的蛋糕怎麼來(lái)?輸入輸出明確性正確性有限性59.演算法的範(fàn)例好吃的蛋糕怎麼來(lái)?輸入輸出明確性正確性有限描述演算法的三種方法文字採(cǎi)用口語(yǔ)化的文字?jǐn)⑹鰜?lái)加以描述，容易冗長(zhǎng)且較不精確，在撰寫(xiě)、閱讀、會(huì)意時(shí)可能會(huì)有誤差，因此一般較不常用p1-10例如：請(qǐng)利用「文字?jǐn)⑹觥故褂谜叩侨霂ぬ?hào)與密碼時(shí)，系統(tǒng)檢查的過(guò)程。步驟一：輸入使用者帳號(hào)與密碼步驟二：判斷帳號(hào)與密碼是否正確步驟三：如果正確時(shí)，則可以登入系統(tǒng)否則，就無(wú)法登入！60.描述演算法的三種方法文字p1-10例如：請(qǐng)利用「文字?jǐn)⑹觥故姑枋鲅菟惴ǖ娜N方法流程圖利用圖形方式來(lái)表達(dá)欲解決問(wèn)題的步驟61.描述演算法的三種方法流程圖19.描述演算法的三種方法虛擬碼使用文字摻雜程式語(yǔ)言，來(lái)描述解題步驟與方法兼具文字描述及流程圖的優(yōu)點(diǎn)//登錄帳號(hào)密碼的檢查(1)Input:UserName,Password(2)IF(UserNameAndPassword)ALLTrueOutput:YouCanPass!elseOutput:YouCannotPass!//計(jì)算1+2+3+…+10(1)設(shè)Count=1,Total=0;(2)Total=Total+Count;(3)Count=Count+1;(4)若Count>10則至步驟(5)，否則回步驟(2)(5)印出Total不是可以執(zhí)行的指令只是說(shuō)明程式處理的流程62.描述演算法的三種方法虛擬碼//登錄帳號(hào)密碼的檢查//計(jì)算1+程式設(shè)計(jì)概念p1-1463.程式設(shè)計(jì)概念p1-1421.程式設(shè)計(jì)概念64.程式設(shè)計(jì)概念22.程式設(shè)計(jì)概念系統(tǒng)發(fā)展的生命週期與程式設(shè)計(jì)之步驟比較65.程式設(shè)計(jì)概念系統(tǒng)發(fā)展的生命週期與程式設(shè)計(jì)之步驟比較23程式設(shè)計(jì)範(fàn)例題目計(jì)算國(guó)文與英文的平均成績(jī)，並依照平均成績(jī)來(lái)求顯示「及格」與「不及格」1.分析及定義問(wèn)題。兩個(gè)等級(jí)分別如下：(1)及格：60(含)以上。(2)不及格：60以下。2.畫(huà)出整合問(wèn)題的流程圖或撰寫(xiě)問(wèn)題的演算法66.程式設(shè)計(jì)範(fàn)例題目1.分析及定義問(wèn)題。24.3.撰寫(xiě)及建立程式模組4.對(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)改為float(浮點(diǎn)數(shù))67.3.撰寫(xiě)及建立程式模組4.對(duì)每一個(gè)程式模組進(jìn)行測(cè)試及除錯(cuò)，直結(jié)構(gòu)化程式設(shè)計(jì)利用「由上而下」的技巧，將程式分解成多個(gè)具有獨(dú)立功能的模組強(qiáng)調(diào)任何程式邏輯均可由三種結(jié)構(gòu)組成循序(Sequence)：簡(jiǎn)單命令式的指令如X=Y+Z選擇(Condition)：做決策使用if-then-elseselectcase/switch重複(Repetition)：重複執(zhí)行do-whiledo-untilforp1-18循序選擇重複68.結(jié)構(gòu)化程式設(shè)計(jì)利用「由上而下」的技巧，將程式分解成多個(gè)具有獨(dú)演算法、資料結(jié)構(gòu)、程式演算法整個(gè)問(wèn)題的解決方法，以邏輯方式描述以文字、或虛擬碼方式，撰寫(xiě)整個(gè)程式的流程可對(duì)應(yīng)到程式的撰寫(xiě)，但是與程式語(yǔ)言的選擇無(wú)關(guān)資料結(jié)構(gòu)要解決問(wèn)題時(shí)所需要的資料，以及資料彼此之間的關(guān)連與結(jié)構(gòu)著重在資料的表現(xiàn)、資料之間的結(jié)構(gòu)關(guān)係程式實(shí)際可以執(zhí)行真實(shí)的解決問(wèn)題，以符合程式語(yǔ)言的規(guī)範(fàn)完成不同程式語(yǔ)言有不同的撰寫(xiě)方法，但是彼此的基本概念卻很相似69.演算法、資料結(jié)構(gòu)、程式演算法27.演算法、資料結(jié)構(gòu)、程式在討論問(wèn)題的解決方案時(shí)，大多以演算法搭配資料結(jié)構(gòu)為溝通的工具直接以程式語(yǔ)言討論太過(guò)於瑣碎程式撰寫(xiě)是基本的技能，更進(jìn)階的是針對(duì)特定問(wèn)題採(cǎi)用適當(dāng)?shù)馁Y料結(jié)構(gòu)設(shè)計(jì)有效率的演算法解決所面對(duì)的問(wèn)題有效率的演算法用較少的記憶體空間完成處理同一個(gè)問(wèn)題用較少的執(zhí)行時(shí)間完成處理同一個(gè)問(wèn)題70.演算法、資料結(jié)構(gòu)、程式在討論問(wèn)題的解決方案時(shí)，大多以演算法搭演算法的時(shí)間效率程式的執(zhí)行速度受到哪些因素影響程式需要執(zhí)行的指令數(shù)量CPU的速度電腦架構(gòu)例如記憶體大小等其他例如編譯程式的效率等演算法的設(shè)計(jì)並不考慮程式語(yǔ)言與硬體架構(gòu)，因此以指令數(shù)量為評(píng)估效率的主要依據(jù)Q:怎麼計(jì)算一個(gè)演算法的指令數(shù)量基本上是無(wú)法精確計(jì)算需要之指令數(shù)量，why?那該怎麼評(píng)估一個(gè)演算法所需的指令數(shù)量p1-2271.演算法的時(shí)間效率程式的執(zhí)行速度受到哪些因素影響p1-2229程式中指令數(shù)目的計(jì)算循序結(jié)構(gòu)(一般指令)例如:x=x+1每個(gè)指令執(zhí)行一次決策分支結(jié)構(gòu)(if)例如:if(x>1)then...只有條件為正時(shí)才會(huì)執(zhí)行重複結(jié)構(gòu)(loop)例如:fori=1to100迴圈內(nèi)的指令重複100次真正計(jì)算指令數(shù)量有困難，但是從以上三個(gè)結(jié)構(gòu)來(lái)看，顯然迴圈內(nèi)的執(zhí)行數(shù)量是重點(diǎn)Q:計(jì)算下列程式中變數(shù)Count被執(zhí)行的次數(shù)為何72.程式中指令數(shù)目的計(jì)算循序結(jié)構(gòu)(一般指令)Q:計(jì)算下列程式中迴圈敘述的頻率計(jì)數(shù)1.先根據(jù)「迴圈計(jì)數(shù)器」的範(fàn)圍算出迴圈重複的次數(shù)2.再乘上迴圈內(nèi)的行數(shù)。下列的程式片段，計(jì)算10組整數(shù)除法的商數(shù)及餘數(shù)1. Fori=0To92. Q=m[i]/n[i]3. R=m[i]Modn[i];4. Console.WriteLine(“{0}/{1}={2}…{3}”,m[i],n[i],Q,R)5. Next迴圈重複的次數(shù)為10次，迴圈內(nèi)有3個(gè)敘述，因此第2行到第4行（迴圈的主體）的頻率計(jì)數(shù)為30(=103)。第1行for迴圈的頭會(huì)執(zhí)行11次，前10次造成迴圈主體的重複執(zhí)行，第11次發(fā)現(xiàn)條件不符而離開(kāi)迴圈。因此整個(gè)迴圈（迴圈的頭加上迴圈的主體）的頻率計(jì)數(shù)為41(=11+30)。73.迴圈敘述的頻率計(jì)數(shù)1.先根據(jù)「迴圈計(jì)數(shù)器」的範(fàn)圍算出迴圈重【舉例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)迴圈。74.【舉例1】【解析】行號(hào)04會(huì)執(zhí)行n+1次，而前n次會(huì)執(zhí)行迴圈【舉例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次)75.【舉例2】【解析】行號(hào)04外層迴圈(for)的計(jì)數(shù)器i從0~【舉例3】假設(shè)兩矩陣a,b相乘，並且矩陣大小皆為n*n，相加請(qǐng)計(jì)算出下列程式的執(zhí)行次數(shù)76.【舉例3】34.雙層迴圈、內(nèi)圈不固定次數(shù)

1

Fori=1Ton 2 Forj=i+1Ton 3result+=14Next5Next

由於內(nèi)圈迴圈計(jì)數(shù)器j的範(fàn)圍，是隨著外圈迴圈計(jì)數(shù)器i的範(fàn)圍改變的，因此我們針對(duì)迴圈計(jì)數(shù)器i的變化來(lái)分析：

77.雙層迴圈、內(nèi)圈不固定次數(shù)35.數(shù)學(xué)式：總次數(shù)＝i的值j的範(fàn)圍第3行執(zhí)行次數(shù)12……nn-123……nn-234……nn-3……

n-1n……n1nn+1……n0總次數(shù)＝(n-1)+(n-2)+…+1=n*(n-1)/2

=

=

=

n2–

=78.數(shù)學(xué)式：i的值j的範(fàn)圍第3行執(zhí)行次數(shù)1n-123……範(fàn)例：計(jì)算n階乘(n!)的函式

1Functionfactor(ByValnAsInteger)AsInteger 2 Dimi,re