算法和資料結(jié)構(gòu)在信息科學領(lǐng)城扮演的角色目錄在學習本章之后，讀者們要能夠了解：1.何謂資料結(jié)構(gòu)2.認識算法和資料結(jié)構(gòu)在信息科學領(lǐng)城扮演的角色。3.學習用程序語言來撰寫各種資料結(jié)構(gòu)。4.了解資料結(jié)構(gòu)的實際應(yīng)用。資料、信息

與

資料結(jié)構(gòu)資料(Data)是用來表達一個觀念或一個事件的一群文字、數(shù)字、符號或圖表例如股票行情、火車時刻表及報章雜志等上的文字、數(shù)字及圖表從計算機處理的觀點來看，所謂「資料」就是指可以輸入到計算機中，并且被程序處理的文字、數(shù)字、符號或圖表。包括了數(shù)值資料、字符串資料及多媒體資料(影像、聲音及視訊)信息(information)利用大量的資料，經(jīng)過有系統(tǒng)的整理、分析、篩選處理而提鍊出來具有參考價格及提供決策依據(jù)的文字、數(shù)字、符號或圖表將有用資料作整理、歸納與分析。資料結(jié)構(gòu)(DataStructure)資料元素不是獨立存在的，它們之間存在著某稱的邏輯關(guān)系資料結(jié)構(gòu)應(yīng)包括兩部分：資料和結(jié)構(gòu)資料是指資料元素的有限集合結(jié)構(gòu)則是指資料元素間關(guān)系的集合資料結(jié)構(gòu)的目的主要有二節(jié)省資料儲存的所需的空間是加快資料處理的速度資料、信息與資料結(jié)構(gòu)資料結(jié)構(gòu)

算法

與程序資料結(jié)構(gòu)和算法是有著密切關(guān)系的，選擇一個好的資料結(jié)構(gòu)，有助于制造一個好的算法，寫出一個好的程序。一個好的資料結(jié)構(gòu)應(yīng)便于有效地進行資料的追加、刪除和檢索，應(yīng)能簡潔的表現(xiàn)復(fù)雜的結(jié)構(gòu)我們的目標在于將抽象的資料結(jié)構(gòu)及算法轉(zhuǎn)換成具體的計算機程序，用來解決問題。資料、信息與資料結(jié)構(gòu)資料結(jié)構(gòu)(DataStructure)+算法(Algorithms)=程序(Program)資料結(jié)構(gòu)、算法可以說是一切程序設(shè)計的基礎(chǔ)。只要有良好的資料結(jié)構(gòu)和算法，就可以設(shè)計出一個好的程序資料結(jié)構(gòu)研究的方向就是如何讓計算機能快速地從存儲器中，拿出我們所需的資料資料結(jié)構(gòu)和算法對一個執(zhí)行有效率的程序來說，扮演著非常重要的角色。資料結(jié)構(gòu)常見的資料結(jié)構(gòu)集合線性結(jié)構(gòu)樹狀結(jié)構(gòu)圖形結(jié)構(gòu)定義及特性指相互之間存在一種或多種特定關(guān)系的資料元素的集合，而根據(jù)資料元素之間關(guān)系的不同特性相關(guān)資料的組合，以某種方式組識而成，讓我們能把這樣的組合對應(yīng)到某種抽象的觀念或是實際的事物。資料結(jié)構(gòu)可能非常單純，也可能非常的復(fù)雜資料結(jié)構(gòu)的定義分成兩部分來討論：一是資料定義與組識的邏輯(logical)結(jié)構(gòu)另一個是和資料操作有關(guān)的實體(Physical)結(jié)構(gòu)。資料結(jié)構(gòu)可定義成：『如何安排資料以配合適當?shù)乃惴ń鉀Q問題的學問』。資料結(jié)構(gòu)簡化了解決問題的程序基本結(jié)構(gòu)集合(Set)：即數(shù)學中的集合關(guān)系一樣，資料元素的關(guān)系就是「一個集合」，它們之間沒有任何先后次序的關(guān)系，并著重在資料是否存在或?qū)儆诩系膯栴}。線性結(jié)構(gòu)：資料元素之間存在一對一的關(guān)系，我們稱之為有序的集合(Orderedset)，也就是資料與資料之間是有先后次序的例如陣列(Array)、串列(List)、堆棧(Stack)與隊列(Queue)等這樣的結(jié)構(gòu)不僅要知道資料是否存資料集合中，還要確定資料儲存的位置和前后資料之間的順序Chapter2,3,4,5章樹狀結(jié)構(gòu)：結(jié)構(gòu)中元素存在一對多的關(guān)系，如二元搜尋樹(binarysearchtree)、累堆(heap)也就是說資料具上下關(guān)系的階層化組織第6,7章圖形結(jié)構(gòu)：資料元素彼此間存在多對多關(guān)系，所謂的先后和上下關(guān)系，在此類的資料結(jié)構(gòu)中，變得更模糊了第8章算法定義算法描述解決問題的方法，而且是以程序式的描述為主，讓人一看就知道是怎么一回事可以用某種程序語言來撰寫算法所代表的程序，并由計算機來執(zhí)行這個程序在算法中，必須以適當?shù)馁Y料結(jié)構(gòu)來描述問題中抽象或具體的事物，有時還得定義資料結(jié)構(gòu)本身有那些操作。算法(Algorithm)代表一系列為達成某種目標而進行的工作，通常算法里的工作都是針對資料所做的某種處理有很多日常生活或工作中的事務(wù)可以用算法來描述計算機科學中所談的算法是比較嚴謹?shù)奶匦曰驐l件(criteria)輸入(Input)：算法通常是接受一些輸入，加以處理或運算，而

產(chǎn)生一些輸出值。這些輸入必須有清楚的型別和個數(shù)描述。輸出(Output)：結(jié)果的描述，至少輸出一個結(jié)果。有限的(Finiteness)：算法必須要能在有限的步驟內(nèi)完成或終止，而且所使用的資料量也是有限的。我們不需要知道執(zhí)行步驟的確實數(shù)目，但必須知道執(zhí)行此算法的步驟(或時間)不會超過某個上限。有效的(Effectiveness)：清楚而不造成混淆，并且能讓使用者用紙筆來執(zhí)行。表示法代數(shù)的表示法：表格式的表示法：利用像陣列或矩陣的結(jié)構(gòu)也可以描述算法例如申報所得稅時所用的累進稅表，從表格中的信息可計算出應(yīng)該繳的所得稅。假如用列表方式就能達到目的，其實并不需要復(fù)雜的表示法。資料流程圖(DFD，Dataflowdiagram)很多應(yīng)用系統(tǒng)以資料的處理為核心，適合用資料流程圖(DFD，Dataflowdiagram)來表示系統(tǒng)的功能DFD算是一種半正式的表示法，早在1970年代就被很多人所接受和采用?？刂屏鞒虉D：資料流程(Dataflow)和控制流程(Controlflow)是算法一體之兩面資料流程說明各操作之間交換的資料控制流程則強調(diào)各操作進行的順序，所以資料流程圖比較適合用來描述算法的功能，而控制流程圖則說明各功能是如何達成的?？刂屏鞒虉D（CFD，Control-flowdiagram）可采用圖的符號來表示，這些基本符號說明了操作除了能按順序進行外，也可以因某些條件成立與否而改變執(zhí)行的順序。CFD表示法所用的圖形符號虛擬碼虛擬碼兼具文字描述及流程圖的優(yōu)點，虛擬碼的方式是用文字加程序語言來描述算法的過程。下面即是描述如何進入學生選課系統(tǒng)的操作流程：進入選課系統(tǒng)讀入學生輸入之選課代碼；if（選課代碼是錯誤的） 告知錯誤，并回到主程序；if（所選科目已經(jīng)額滿） 告知額滿，并回到主程序；if（所選科目沖堂） 告知沖堂，并回到主程序；將所選科目加入此學生的選課清單內(nèi)；設(shè)計算法的目標與條件正確性(correctness)：根據(jù)輸入的資料內(nèi)容，便能得到預(yù)期的資料輸出，也就是可以正確的執(zhí)行，這是對算法的基本要求?？勺x性(readability)：算法的主要目的是為了讓使用者易于閱讀計算機程序處理的流程，如此才有助于程序日后的維護與修改。健全性：對于資料的錯誤輸入與輸出，算法仍能適當?shù)姆磻?yīng)或處理，而不至于使程序或計算機當?shù)簦@就是算法的健全性。效率性(performance)：面對同樣的問題，不同的算法所需的時間會有佷大的差別，故一個好的算法，其執(zhí)行時間效率必須控制在可以容忍范圍內(nèi)。存儲器需求低：資料的處理會占用存儲器資源，所占用的空間則愈小愈好。程序語言評估準則正確性：是否完成所有的事項，并正確的解決問題?？勺x性：是否讓人容易了解程序之原意。易維護性：是否具有程序、結(jié)構(gòu)化與模塊化的基礎(chǔ)。清晰性：程序中的變量及程序等名稱是否具有意義。文書性：是否有完備的程序說明文件。效率性：是否簡單明暸直接表示程序的意圖，以最簡要的程序碼，最快的執(zhí)行速度來完成。程序的編寫原則：程序要段落分明，并以有條不紊的階層式區(qū)塊排列；標識符或變量的命名須有意義；須簡單且直接表達程序的意義，盡可能使用內(nèi)建函數(shù)；撰寫結(jié)構(gòu)化程序，引用基本的控制流程結(jié)構(gòu)；少用GOTO，避免不必要之分支。多使用子程序以使程序單元化；因為子程序可以重復(fù)使用，且程序的測試工作亦容易多了。善用物件導(dǎo)向程序繼承、封裝與多型等，將軟件IC化可以提升軟件開發(fā)的生產(chǎn)力。盡量將輸入與輸出、處理邏輯與資料儲存分開來設(shè)計。不要將程序的效率性擺第一，先考慮程序的正確性、清晰性、易讀性及可維護性。程序必須加上注解，以提升程序的可讀性。算法的效率PerformanceMeasurement算法的效率算法是否要具有某種結(jié)構(gòu)？在設(shè)計上有那些考量？同一問題是不是可用多種算法來提供解答？我們要如何比較不同算法的優(yōu)劣？分析方式「空間復(fù)雜度」(Spacecomplexity)空間復(fù)雜度是指算法使用的存儲器空間的大小，當計算機執(zhí)行一個算法時，其實就是在執(zhí)行一個程序，這個程序所需要的空間包含了程序的指令，變量與常數(shù)等，假如占用的空間太大，程序在執(zhí)行時的效率可能會受到很明顯的影響?！笗r間復(fù)雜度」(Timecomplexity)兩方面來分析。決定于算法執(zhí)行完成所用的時間。在程序設(shè)計中，決定某程序區(qū)段的步驟計數(shù)是程序設(shè)計師在控制整體程序系統(tǒng)時間的重要因素，不過要決定精確的次數(shù)卻也真是個困難的工作。由于并無法精確的預(yù)知一個程序的細部行為，只能以「漸近式(AsymptoticNotation)」來討論其復(fù)雜度，再根據(jù)函數(shù)的成長率來判斷算法的優(yōu)劣。時間復(fù)雜度TimeComplexity定義在程序設(shè)計中，決定某程序區(qū)段的步驟計數(shù)是程序設(shè)計師在控制整體程序系統(tǒng)時間的重要因素往往以一種「概量」的精神來做為衡量的準則，稱為「時間復(fù)雜度」(Timecomplexity)。定義一個T(n)表示在一個完全理想狀態(tài)的計算機中程式所執(zhí)行的實際指令次數(shù)。時間復(fù)雜度是輸入量為n的一種函數(shù)一個程序的執(zhí)行時間并不完全和輸入量有關(guān)，算法的好壞也會影響對輸入量n而言，它的最大執(zhí)行時間就是時間復(fù)雜度(Timecomplexity)的衡量標準。時間復(fù)雜度可包含程序的編譯時間與執(zhí)行時間一個程序只要編譯一次即可執(zhí)行多次通常我們會比較在意程序的執(zhí)行時間常用所謂的「漸近式表示法」(AsymptoticNotation)來簡化時間復(fù)雜度的表示法。常見的時間復(fù)雜度按照復(fù)雜度排序O(1)＜O(㏒n)＜O(n)＜O(n㏒n)＜O(n2)＜O(n3)＜O(2n)O(1)：常數(shù)時間O(n)：線性時間O(logn)：次線性時間O(nlogn)：對數(shù)線性時間O(n2)：平方時間O(n3)：立方時間O(2n)：指數(shù)時間程序執(zhí)行的次數(shù)(Frequencycount)程序執(zhí)行所花費的執(zhí)行次數(shù)有些程序并非每一次執(zhí)行次數(shù)皆相同當不同的輸入值而有不同的次數(shù)。這樣的情況要將程序分為最佳狀況與最壞狀況最佳狀況就是1次，最壞狀況是無窮次(n次)。分析模式最佳狀況平均狀況最壞狀況最佳狀況分析算法對何種輸入資料，所需花費的時間最少。程序最低的時間復(fù)雜度,稱為Omega(W)也就是程序執(zhí)行的次數(shù)一定相等或大于最佳狀況。平均狀況(Average-Case)分析算法在所有可能的輸入組合下，平均所需要的時間。程序平均的時間復(fù)雜度,稱為Theta(Q)程序執(zhí)行的次數(shù)介于最佳與最壞狀況之間。最壞狀況(Worst-Case)分析算法在所有可能的輸入組合下，最多所需要的時間。程序最高的時間復(fù)雜度,稱為Big-O就是程序執(zhí)行的次數(shù)一定相等或小于最壞狀況較常以Big-Oh來表示算法的執(zhí)行效率。何謂Big-O定義f(n)＝O(g(n))若存在正的常數(shù)Ｃ和n0，則對所有n≥n0，必使得得0≤f(n)≤Cg(n)的條件成立。實例說明假設(shè)下列多項式各為某程序片斷或敘述的執(zhí)行次數(shù)，請利用Big-Oh來表示時間復(fù)雜度。

(a)3n+2

(b)10n2+5n+1

(c)7*2n+n2+n

【解析】

(a)3n+2＝O(n)，∵我們可找到c=4，n0=2，使得3n+2?4n

(b)10n2+5n+1＝O(n2)，∵我們可找到c=11，n0=6，使得10n2+5n+1?11n2

(c)7*2n+n2+n=O(2n)，∵我們可找到c=8，n0=4，使得7*2n+n2+n?8*2n

常見Big-Oh的幾種情形1、 O(1)或O(c)：常數(shù)時間(constanttime)

這表示算法則的執(zhí)行時間是一個常數(shù)倍，而忽略資料集合大小的變化。一個例子是在計算機中它存取RAM所花的時間，在存儲器中去讀取及寫入所用的時間是相同的，而不考慮整個存儲器的數(shù)量。如果有這樣的算法則存在，則我們可以在任何大小的資料集合中自由的使用，而不需要擔心時間或運算的次數(shù)會一直成長或變得很高。

2、 O(n)：稱為線性時間(lineartime)

它執(zhí)行的時間會隨資料集合的大小而線性成長。我們可以找到一個例子是在一個沒有排列過的資料集中要找一個最大元素，且我們以簡單的方式去解釋其內(nèi)容，直到我們將所有的資料都找過并且找到最大值為止。

3、 O(log2n)：稱為次線性時間(sub-lineartime)

這一種函式的成長速度比線性的程序還慢，而此常數(shù)(它是不成長的)的情形還快。

4、 O(n2)：稱為平方時間(quadratictime)

算法則執(zhí)行時間會成二次方的成長，這種會變的不切實際，特別是當資料集合的大小變的很大時。

5、 O(n3)：稱為立方時間(cubictime)

算法則執(zhí)行時間會成三次方的成長，這種會變的不切實際，特別是當資料集合的大小變的很大時。

6、 O(2n)：稱為指數(shù)時間(exponentialtime)

7、 O(n1og2n)：介于線性及三次方成長的中間之行為模式。何謂Ω(omega)定義f(n)=Ω(g(n))若存在正的常數(shù)C和n0，則對所有n≥n0，必使得0≤Cg(n)≤f(n)的條件成立。實例說明假設(shè)下列多項式各為某程序片斷或敘述的執(zhí)行次數(shù)，請利用Ω來表示時間復(fù)雜度。

(a)3n+2

(b)200n2+4n+5

【解析】

(a) 3n+2＝Ω(n)，∵我們可找到c=3，n0=1，使得3n+2?3n

(b) 200n2+4n+5＝Ω(n2)，∵我們可找到c=200，n0=1，使得200n2+4n+5?200n2何謂Θ(Theta)定義f(n)=Θ(g(n))

若存在正的常數(shù)C1，C2和n0，則對所有n≥n0，必使得0≤C1g(n)≤f(n)≤C2g(n)的條件成立結(jié)語對于使用漸近式表示法來描述時間復(fù)雜度到底那一種是最佳的方法﹖在前面我們就指出了「big-oh」是對算法的時間復(fù)雜度描述最常用的表示法。原因就是在漸近表示法中我們通常只關(guān)切其最大項目(leadingterm)的原因。

C語言與資料結(jié)構(gòu)C語言與資料結(jié)構(gòu)主要的特色具備低階語言與高階語言的特性。

是一種結(jié)構(gòu)化的語法且可以控制硬設(shè)備。

可以在DOS及WINDOWS環(huán)境下執(zhí)行。

其使用方式一般可以使用純文字編輯器，如NotePad(記事本)進行程序撰寫，再使用C語言編譯軟件，進行編譯及連結(jié)完成C語言；或者直接使用C語言編譯軟件來編寫C語言，并且進行編譯及連結(jié)。C語言的資料型別大致可分為基本型別：字符型、整數(shù)型、實數(shù)型。

資料型別：結(jié)構(gòu)型......陣列、結(jié)構(gòu)、記錄、等位(Union)、指標型。典型的資料結(jié)構(gòu)表(table)

堆棧(stack)

隊列(queue)

串列(list)

樹(tree)

圖(graph)淺談資料型態(tài)當我們學一種程序語言時，通常會從了解其語法與語意開始，其實程序語言就像一般口語，是溝通的工具，只不過溝通的對象更進一步延伸到計算機。在程序語言中，資料以常數(shù)或變量(Variable)的型態(tài)出現(xiàn)，并利用型式(type)來將資料分門別類，因此有所謂的整數(shù)(Integer)、浮點數(shù)(floating-pointnumbers)、字符串(string)等。另外將資料以各種不同的方式組合在一起。如C語言中的結(jié)構(gòu)及指標等敘述，亦可形成更多的型式。各種資料結(jié)構(gòu)的關(guān)系用程序語言描述資料結(jié)構(gòu)C語言程序主架構(gòu)voidmain()//主程序

{//中括號不可以省略

敘述式；//分號不可以省略

}//中括號不可以省略變量宣告一個整數(shù)變量的宣告方式是：intiAmt宣告字符及數(shù)值范圍如下表：類別位元長度表示方法數(shù)值范圍整數(shù)16int-32768到3276816short-32768到3276832long-2147483648到214748364816unsignedint0到6553516unsignedshort0到6553532unsignedlong0到4294967295浮點數(shù)32float10的負38次方到10的正38次方64double10的負308次方到10的正308次方字符8char0到225陣列宣告陣列(Array)是資料結(jié)構(gòu)中最常被使用到的資料格式之一；它的宣告方式如下：intiX[10]指標Pointer的宣告假設(shè)我們要宣告一個變量ptr為指標變量：int

*ptr;表示ptr指向型態(tài)為整數(shù)的存儲器位址，但并不能直接引用或設(shè)定任何給定值。動態(tài)存儲器的配罝陣列的大小宣告，一定是在程序開發(fā)階段就得確定宣告太小，程序執(zhí)行可能發(fā)生錯誤，宣告太大，則容易造成空間浪費指標最重要的意義在于資料量可以隨著需要而改變main(){intn,*p;scanf(“%d”,&n);p=(int*)malloc(sizeof(int)*n);}malloc()是系統(tǒng)提供的函數(shù)，它可以向系統(tǒng)要求配置指定大小的存儲器。結(jié)構(gòu)Structure的宣告C語言的基本資料型態(tài)有整數(shù)、字符、浮點數(shù)等陣列和指標則限制變量的資料型態(tài)必須一致真正在資料處理的實務(wù)上時，資料型態(tài)可能不同或需要更多的型態(tài)此C語言提供了使用者自定型態(tài)的功能，