計(jì)算機(jī)科學(xué)導(dǎo)論講稿

1、第第4 4章章 程序設(shè)計(jì)基礎(chǔ)程序設(shè)計(jì)基礎(chǔ)2021-12-52計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論學(xué)習(xí)目標(biāo)學(xué)習(xí)目標(biāo)u了解程序設(shè)計(jì)的基礎(chǔ)知識、程序設(shè)計(jì)風(fēng)格的重要性、了解程序設(shè)計(jì)的基礎(chǔ)知識、程序設(shè)計(jì)風(fēng)格的重要性、基本的查找和排序方法。基本的查找和排序方法。u掌握結(jié)構(gòu)化程序設(shè)計(jì)方法和面向?qū)ο蟪绦蛟O(shè)計(jì)方法的掌握結(jié)構(gòu)化程序設(shè)計(jì)方法和面向?qū)ο蟪绦蛟O(shè)計(jì)方法的思想、幾種基本的數(shù)據(jù)結(jié)構(gòu)。思想、幾種基本的數(shù)據(jù)結(jié)構(gòu)。u學(xué)習(xí)計(jì)算機(jī)首先要學(xué)習(xí)程序設(shè)計(jì)，良好的程序設(shè)計(jì)技學(xué)習(xí)計(jì)算機(jī)首先要學(xué)習(xí)程序設(shè)計(jì)，良好的程序設(shè)計(jì)技能和風(fēng)格有助于加深對計(jì)算機(jī)的理解和進(jìn)一步學(xué)習(xí)。能和風(fēng)格有助于加深對計(jì)算機(jī)的理解和進(jìn)一步學(xué)習(xí)。第第4 4章章 程序設(shè)計(jì)基

2、礎(chǔ)程序設(shè)計(jì)基礎(chǔ)2021-12-53計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論4.1 程序設(shè)計(jì)基礎(chǔ)程序設(shè)計(jì)基礎(chǔ)程序設(shè)計(jì)步驟如下：程序設(shè)計(jì)步驟如下：(1)(1)確定要解決的問題確定要解決的問題。(2)(2)分析問題分析問題。在著手解決問題之前，應(yīng)該通過分。在著手解決問題之前，應(yīng)該通過分析，充分理解問題，明確原始數(shù)據(jù)、解題要求、析，充分理解問題，明確原始數(shù)據(jù)、解題要求、需要輸出的數(shù)據(jù)及形式等。需要輸出的數(shù)據(jù)及形式等。(3)(3)選擇計(jì)算方法選擇計(jì)算方法。(4)(4)確定數(shù)據(jù)結(jié)構(gòu)和算法確定數(shù)據(jù)結(jié)構(gòu)和算法。算法是解題的過程。首。算法是解題的過程。首先集中精力于算法的總體規(guī)劃，然后逐層降低問先集中精力于算法的總體規(guī)劃，

3、然后逐層降低問題的抽象性，逐步充實(shí)細(xì)節(jié)，直到最終把抽象的題的抽象性，逐步充實(shí)細(xì)節(jié)，直到最終把抽象的問題具體化成可用程序語句表達(dá)的算法。這是一問題具體化成可用程序語句表達(dá)的算法。這是一個(gè)自上而下、逐步細(xì)化的過程。個(gè)自上而下、逐步細(xì)化的過程。2021-12-54計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論4.1 程序設(shè)計(jì)基礎(chǔ)程序設(shè)計(jì)基礎(chǔ)(5)(5)繪制流程圖繪制流程圖。(6)(6)編寫程序編寫程序。利用程序設(shè)計(jì)語言表示算法，編寫。利用程序設(shè)計(jì)語言表示算法，編寫代碼。代碼。(7)(7)調(diào)試并測試程序調(diào)試并測試程序。調(diào)試程序包括編譯和連接等。調(diào)試程序包括編譯和連接等操作。程序員還要對程序執(zhí)行的結(jié)果進(jìn)行分析，只操作。程

4、序員還要對程序執(zhí)行的結(jié)果進(jìn)行分析，只有能夠得到正確結(jié)果的程序才是所需的程序。有能夠得到正確結(jié)果的程序才是所需的程序。(8)(8)整理資料，交付使用整理資料，交付使用。高質(zhì)量程序設(shè)計(jì)目標(biāo)是結(jié)構(gòu)化程度高、可讀性好、效高質(zhì)量程序設(shè)計(jì)目標(biāo)是結(jié)構(gòu)化程度高、可讀性好、效率高、可靠性高、便于維護(hù)。率高、可靠性高、便于維護(hù)。2021-12-55計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論u1自上而下自上而下與與自下而上自下而上先將一個(gè)大問題分解成若干個(gè)子問題，把比較復(fù)先將一個(gè)大問題分解成若干個(gè)子問題，把比較復(fù)雜的子問題繼續(xù)分解成更加簡單的二級子問題，雜的子問題繼續(xù)分解成更加簡單的二級子問題，直至每個(gè)子問題都有顯而易見的解決辦

5、法，然后直至每個(gè)子問題都有顯而易見的解決辦法，然后在在實(shí)現(xiàn)時(shí)采用自下而上的方法實(shí)現(xiàn)時(shí)采用自下而上的方法，逐一編寫解決各，逐一編寫解決各個(gè)子問題的程序。個(gè)子問題的程序。設(shè)計(jì)程序時(shí)采用自上而下的方設(shè)計(jì)程序時(shí)采用自上而下的方法法比采用自下而上的方法效率要高得多。比采用自下而上的方法效率要高得多。4.2.1 結(jié)構(gòu)化程序設(shè)計(jì)方法結(jié)構(gòu)化程序設(shè)計(jì)方法2021-12-56計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論 采用自上而下解決問題的思路如圖采用自上而下解決問題的思路如圖: . . . . . . 二級子問題 二級子問題 二級子問題 需要解決的復(fù)雜問題 三級子問題 三級子問題 三級子問題 . . . . . . . .

6、. 最小問題 最小問題 最小問題 4.2.1 結(jié)構(gòu)化程序設(shè)計(jì)方法結(jié)構(gòu)化程序設(shè)計(jì)方法2021-12-57計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論 用這種方法逐步分解，直到作者認(rèn)為可以直接將各小段表達(dá)為文字語句為止。這種方法就叫 做“自頂向下，逐步細(xì)化”。 2021-12-58計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論u2結(jié)構(gòu)化方法結(jié)構(gòu)化方法結(jié)構(gòu)化方法有助于在正式編寫程序之前充分結(jié)構(gòu)化方法有助于在正式編寫程序之前充分理解問題的實(shí)質(zhì)和實(shí)現(xiàn)方法，并且可以在具理解問題的實(shí)質(zhì)和實(shí)現(xiàn)方法，并且可以在具體編碼過程中提供指導(dǎo)。體編碼過程中提供指導(dǎo)。4.2.1 結(jié)構(gòu)化程序設(shè)計(jì)方法結(jié)構(gòu)化程序設(shè)計(jì)方法2021-12-59計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科

7、學(xué)導(dǎo)論u結(jié)構(gòu)化方法通常遵循以下原則結(jié)構(gòu)化方法通常遵循以下原則:(1) (1) 用戶參與的原則用戶參與的原則(2) (2) 先分析、再設(shè)計(jì)、后實(shí)現(xiàn)的原則。先分析、再設(shè)計(jì)、后實(shí)現(xiàn)的原則。(3) (3) 自上而下的原則自上而下的原則(4) (4) 階段成果文檔化階段成果文檔化4.2.1 結(jié)構(gòu)化程序設(shè)計(jì)方法結(jié)構(gòu)化程序設(shè)計(jì)方法2021-12-510計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論u3結(jié)構(gòu)化程序設(shè)計(jì)方法結(jié)構(gòu)化程序設(shè)計(jì)方法 使用使用順序、選擇、循環(huán)順序、選擇、循環(huán)3 3種基本控制結(jié)構(gòu)。種基本控制結(jié)構(gòu)。4.2.1 結(jié)構(gòu)化程序設(shè)計(jì)方法結(jié)構(gòu)化程序設(shè)計(jì)方法2021-12-511計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論A AB Ba

8、 ab b順序結(jié)構(gòu)示意圖順序結(jié)構(gòu)示意圖 順序結(jié)構(gòu)順序結(jié)構(gòu) 順序結(jié)構(gòu)是一種最簡單、最基本的結(jié)構(gòu)，在順序順序結(jié)構(gòu)是一種最簡單、最基本的結(jié)構(gòu)，在順序結(jié)構(gòu)內(nèi)，結(jié)構(gòu)內(nèi)，各塊是按照它們出現(xiàn)的先后順序依次執(zhí)行各塊是按照它們出現(xiàn)的先后順序依次執(zhí)行。下圖表示了一個(gè)順序結(jié)構(gòu)形式，從圖中可以看出。下圖表示了一個(gè)順序結(jié)構(gòu)形式，從圖中可以看出它有一個(gè)入口它有一個(gè)入口a a點(diǎn)，一個(gè)出口點(diǎn)，一個(gè)出口b b點(diǎn)，在結(jié)構(gòu)內(nèi)點(diǎn)，在結(jié)構(gòu)內(nèi)A A框和框和B B框都是順序執(zhí)行的處理框。框都是順序執(zhí)行的處理框。2021-12-512計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論已知梯形兩底已知梯形兩底a、b和高和高h(yuǎn)，設(shè)計(jì)一個(gè)求梯形面積的算，設(shè)計(jì)一個(gè)求梯形

9、面積的算法，并畫出流程圖。法，并畫出流程圖。2021-12-513計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論 選擇結(jié)構(gòu)選擇結(jié)構(gòu) 選擇結(jié)構(gòu)中包含一個(gè)判斷框，根據(jù)給定的條件選擇結(jié)構(gòu)中包含一個(gè)判斷框，根據(jù)給定的條件S S是否成立而選擇執(zhí)行是否成立而選擇執(zhí)行A A框或框或B B框，當(dāng)條件成立時(shí)，執(zhí)框，當(dāng)條件成立時(shí)，執(zhí)行行A A，否則執(zhí)行否則執(zhí)行B B。判斷框中的兩個(gè)分支，執(zhí)行完。判斷框中的兩個(gè)分支，執(zhí)行完A A或或B B后都必須匯合在一起，從出口后都必須匯合在一起，從出口b b 退出，然后接著執(zhí)退出，然后接著執(zhí)行其后的過程。行其后的過程。 SABabYN選擇結(jié)構(gòu)流程圖選擇結(jié)構(gòu)流程圖2021-12-514計(jì)算機(jī)科學(xué)導(dǎo)

10、論計(jì)算機(jī)科學(xué)導(dǎo)論設(shè)計(jì)一個(gè)算法，輸出設(shè)計(jì)一個(gè)算法，輸出a，b，c中的最大值。中的最大值。 2021-12-515計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論 循環(huán)結(jié)構(gòu)循環(huán)結(jié)構(gòu) 循環(huán)結(jié)構(gòu)是指在一定條件下反復(fù)執(zhí)行一個(gè)循環(huán)結(jié)構(gòu)是指在一定條件下反復(fù)執(zhí)行一個(gè)程序塊的結(jié)構(gòu)。循環(huán)結(jié)構(gòu)也是只有一個(gè)入口，程序塊的結(jié)構(gòu)。循環(huán)結(jié)構(gòu)也是只有一個(gè)入口，一個(gè)出口。一個(gè)出口。 whilewhile循環(huán)循環(huán) 當(dāng)給定的條件當(dāng)給定的條件S S成立時(shí)，執(zhí)行成立時(shí)，執(zhí)行A A框操作，執(zhí)行完框操作，執(zhí)行完A A操作后，再判操作后，再判斷斷S S條件是否成立，如果成立，條件是否成立，如果成立，再次執(zhí)行再次執(zhí)行A A操作，如此重復(fù)執(zhí)行操作，如此重復(fù)執(zhí)行A

11、A操作，直到判斷操作，直到判斷p p條件不成立條件不成立才停止循環(huán)。此時(shí)不執(zhí)行才停止循環(huán)。此時(shí)不執(zhí)行A A操作，操作，而從出口而從出口b b脫離循環(huán)結(jié)構(gòu)。脫離循環(huán)結(jié)構(gòu)。ASabYN2021-12-516計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論abYNSA do-whiledo-while循環(huán)循環(huán) 先執(zhí)行先執(zhí)行A A框操作，然后判斷給定框操作，然后判斷給定條件條件S S是否成立，如果成立，再是否成立，如果成立，再次執(zhí)行次執(zhí)行A A操作；然后再對操作；然后再對S S進(jìn)行進(jìn)行判斷，如此反復(fù)，直到給定的判斷，如此反復(fù)，直到給定的S S條件不成立為止。此時(shí)不再執(zhí)條件不成立為止。此時(shí)不再執(zhí)行行A A框，從出口框，從出

12、口b b脫離循環(huán)。脫離循環(huán)。2021-12-517計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論設(shè)計(jì)一個(gè)算法，計(jì)算設(shè)計(jì)一個(gè)算法，計(jì)算1+2+3+100的值。的值。 2021-12-518計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論u3結(jié)構(gòu)化程序設(shè)計(jì)方法結(jié)構(gòu)化程序設(shè)計(jì)方法 使用使用順序、選擇、循環(huán)順序、選擇、循環(huán)3 3種基本控制結(jié)構(gòu)。種基本控制結(jié)構(gòu)。4.2.1 結(jié)構(gòu)化程序設(shè)計(jì)方法結(jié)構(gòu)化程序設(shè)計(jì)方法2021-12-519計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論u4模塊化方法模塊化方法一個(gè)復(fù)雜的問題可以劃分為多個(gè)簡單問題的組合。一個(gè)復(fù)雜的問題可以劃分為多個(gè)簡單問題的組合。在自頂向下、逐步細(xì)化的過程中，把復(fù)雜問題分解在自頂向下、逐步細(xì)化的過程中，

13、把復(fù)雜問題分解成一個(gè)個(gè)簡單問題的最基本方法就是模塊化。成一個(gè)個(gè)簡單問題的最基本方法就是模塊化。模塊化便于問題的分析，模塊體現(xiàn)了信息隱藏的概模塊化便于問題的分析，模塊體現(xiàn)了信息隱藏的概念。模塊常用子程序加以實(shí)現(xiàn)。念。模塊常用子程序加以實(shí)現(xiàn)。4.2.1 結(jié)構(gòu)化程序設(shè)計(jì)方法結(jié)構(gòu)化程序設(shè)計(jì)方法2021-12-520計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論模塊設(shè)計(jì)的方法：模塊化設(shè)計(jì)的思想實(shí)際上是一種模塊化設(shè)計(jì)的思想實(shí)際上是一種“分而治之分而治之”的思想，把一個(gè)大任務(wù)分為若干個(gè)子任務(wù)，的思想，把一個(gè)大任務(wù)分為若干個(gè)子任務(wù)，每一個(gè)子任務(wù)就相對簡單了。每一個(gè)子任務(wù)就相對簡單了。在拿到一個(gè)程序模塊以后，根據(jù)程序模塊的在拿到

14、一個(gè)程序模塊以后，根據(jù)程序模塊的功能將它劃分為若干個(gè)子模塊，如果這些子功能將它劃分為若干個(gè)子模塊，如果這些子模塊的規(guī)模還嫌大，還再可以劃分為更小的模塊的規(guī)模還嫌大，還再可以劃分為更小的模塊。這個(gè)過程采用自頂向下方法來實(shí)現(xiàn)。模塊。這個(gè)過程采用自頂向下方法來實(shí)現(xiàn)。2021-12-521計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論4.2.2 面向?qū)ο蟮某绦蛟O(shè)計(jì)方法面向?qū)ο蟮某绦蛟O(shè)計(jì)方法u1 1面向?qū)ο蟮乃枷朊嫦驅(qū)ο蟮乃枷?OO(Object Oriented，面向?qū)ο螅嫦驅(qū)ο?的程序設(shè)計(jì)把客觀事的程序設(shè)計(jì)把客觀事物看作具有屬性和行為的對象，通過抽象找出同一類物看作具有屬性和行為的對象，通過抽象找出同一類對象的共同

15、屬性對象的共同屬性(靜態(tài)特征靜態(tài)特征)和行為和行為(動態(tài)特征動態(tài)特征)，形成類。，形成類。2021-12-522計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論 對象在現(xiàn)實(shí)生活中到處可見。對象在現(xiàn)實(shí)生活中到處可見。，一個(gè)人是一個(gè)對象，一臺，一個(gè)人是一個(gè)對象，一臺PCPC機(jī)是一個(gè)對象；機(jī)是一個(gè)對象；再將一臺再將一臺PCPC機(jī)拆開看，便有顯示器、機(jī)箱、硬盤、主板機(jī)拆開看，便有顯示器、機(jī)箱、硬盤、主板、處理器、鼠標(biāo)等，這每一個(gè)部件又是一個(gè)對象，即、處理器、鼠標(biāo)等，這每一個(gè)部件又是一個(gè)對象，即PCPC機(jī)對象是由多個(gè)機(jī)對象是由多個(gè)“子子”對象組成的，此時(shí)對象組成的，此時(shí)PCPC機(jī)可看作為機(jī)可看作為一個(gè)容器對象。一個(gè)容器對象

16、。 4.2.2 面向?qū)ο蟮某绦蛟O(shè)計(jì)方法面向?qū)ο蟮某绦蛟O(shè)計(jì)方法2021-12-523計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論 在在橋梁是抽象的概念橋梁是抽象的概念, ,重慶長江大橋、西湖斷橋就是重慶長江大橋、西湖斷橋就是具體的。我們把抽象的具體的。我們把抽象的“橋橋”看成類看成類, ,而具體的一座橋，而具體的一座橋，如重慶長江大橋看成是對象。如重慶長江大橋看成是對象。類是抽象。類是抽象的，對象是具體的。的，對象是具體的。 如水果是基類，蘋果是子類，而紅富士、黃元帥等蘋如水果是基類，蘋果是子類，而紅富士、黃元帥等蘋果品種又是蘋果類的子類，在這里，水果也稱為是蘋果的果品種又是蘋果類的子類，在這里，水果也稱為是蘋

17、果的父類，蘋果也可稱為是紅富士、黃元帥等的父類。具體的父類，蘋果也可稱為是紅富士、黃元帥等的父類。具體的一個(gè)紅富士蘋果就是一個(gè)對象。一個(gè)紅富士蘋果就是一個(gè)對象。4.2.2 面向?qū)ο蟮某绦蛟O(shè)計(jì)方法面向?qū)ο蟮某绦蛟O(shè)計(jì)方法2021-12-524計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論4.2.2 面向?qū)ο蟮某绦蛟O(shè)計(jì)方法面向?qū)ο蟮某绦蛟O(shè)計(jì)方法2021-12-525計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論 子類不但具有父類的全部屬性和方法，而且允許用戶根據(jù)子類不但具有父類的全部屬性和方法，而且允許用戶根據(jù)需要對已有的屬性和方法進(jìn)行修改，或添加新的屬性和方法需要對已有的屬性和方法進(jìn)行修改，或添加新的屬性和方法，這種特性稱為類的繼承

18、性。，這種特性稱為類的繼承性。 。如同一臺。如同一臺電視機(jī)的使用者只需了解其外部按鈕（用戶接口）的功能與電視機(jī)的使用者只需了解其外部按鈕（用戶接口）的功能與用法，而無需知道電視機(jī)的內(nèi)部構(gòu)造與工作原理一樣。用法，而無需知道電視機(jī)的內(nèi)部構(gòu)造與工作原理一樣。 ，但，但方法程序的內(nèi)容不同。方法程序的內(nèi)容不同。4.2.2 面向?qū)ο蟮某绦蛟O(shè)計(jì)方法面向?qū)ο蟮某绦蛟O(shè)計(jì)方法2021-12-526計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論4.3 基本數(shù)據(jù)結(jié)構(gòu)基本數(shù)據(jù)結(jié)構(gòu)u數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(Data Structure)是系統(tǒng)設(shè)計(jì)是系統(tǒng)設(shè)計(jì)和程序開發(fā)的重要基礎(chǔ)。和程序開發(fā)的重要基礎(chǔ)。2021-12-527計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)

19、導(dǎo)論4.3.1 基本概念基本概念u1數(shù)據(jù)、數(shù)據(jù)類型數(shù)據(jù)、數(shù)據(jù)類型 數(shù)據(jù)是對客觀事物的符號表示。數(shù)據(jù)是對客觀事物的符號表示。在計(jì)算機(jī)系統(tǒng)內(nèi)，在計(jì)算機(jī)系統(tǒng)內(nèi)，數(shù)據(jù)通常是指能夠輸入到計(jì)算機(jī)中并被計(jì)算機(jī)進(jìn)行數(shù)據(jù)通常是指能夠輸入到計(jì)算機(jī)中并被計(jì)算機(jī)進(jìn)行處理的符號的集合處理的符號的集合。例如，數(shù)字、字母、漢字、圖例如，數(shù)字、字母、漢字、圖形、圖像、聲音等信息在計(jì)算機(jī)內(nèi)部的表示都是數(shù)據(jù)，形、圖像、聲音等信息在計(jì)算機(jī)內(nèi)部的表示都是數(shù)據(jù)，可以是數(shù)值數(shù)據(jù)，也可以是非數(shù)值數(shù)據(jù)?？梢允菙?shù)值數(shù)據(jù)，也可以是非數(shù)值數(shù)據(jù)。 數(shù)據(jù)類型是指具有相同取值范圍和可以實(shí)施同種操數(shù)據(jù)類型是指具有相同取值范圍和可以實(shí)施同種操作的數(shù)據(jù)的集合

20、。作的數(shù)據(jù)的集合。例如，在程序設(shè)計(jì)語言中，通常例如，在程序設(shè)計(jì)語言中，通常定義了字符型、整數(shù)型、數(shù)組等多種數(shù)據(jù)類型。定義了字符型、整數(shù)型、數(shù)組等多種數(shù)據(jù)類型。2021-12-528計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論u2數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對象數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對象 能夠獨(dú)立并完整地描述客觀世界實(shí)體的能夠獨(dú)立并完整地描述客觀世界實(shí)體的基本數(shù)據(jù)單基本數(shù)據(jù)單元稱為數(shù)據(jù)元素元稱為數(shù)據(jù)元素，它是組成數(shù)據(jù)的基本單位。在不同，它是組成數(shù)據(jù)的基本單位。在不同的應(yīng)用環(huán)境中，數(shù)據(jù)元素有時(shí)可以稱為結(jié)點(diǎn)、記錄的應(yīng)用環(huán)境中，數(shù)據(jù)元素有時(shí)可以稱為結(jié)點(diǎn)、記錄等。等。 數(shù)據(jù)項(xiàng)是組成數(shù)據(jù)元素的不可分割的最小單位數(shù)據(jù)項(xiàng)是組成數(shù)據(jù)

21、元素的不可分割的最小單位。最簡。最簡單的數(shù)據(jù)元素是由一個(gè)數(shù)據(jù)項(xiàng)構(gòu)成的。單的數(shù)據(jù)元素是由一個(gè)數(shù)據(jù)項(xiàng)構(gòu)成的。 同類數(shù)據(jù)元素的集合稱為數(shù)據(jù)對象。同類數(shù)據(jù)元素的集合稱為數(shù)據(jù)對象。4.3.1 基本概念基本概念2021-12-529計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論學(xué)學(xué) 號號姓姓 名名高等數(shù)學(xué)高等數(shù)學(xué)大學(xué)英語大學(xué)英語政治經(jīng)濟(jì)學(xué)政治經(jīng)濟(jì)學(xué)平均成績平均成績1王五王五807678782李四李四907887853張三張三888989894高二高二789095875蘇三蘇三80999491表中的每一行是一個(gè)結(jié)點(diǎn)（或記錄），即數(shù)據(jù)元素；表中的每一行是一個(gè)結(jié)點(diǎn)（或記錄），即數(shù)據(jù)元素；它是由學(xué)號、姓名、各科成績及平均成績等數(shù)據(jù)

22、項(xiàng)組成。它是由學(xué)號、姓名、各科成績及平均成績等數(shù)據(jù)項(xiàng)組成。4.3.1 基本概念基本概念u2數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對象數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對象2021-12-530計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論u3 3數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)元素之間的相互關(guān)系的集是指數(shù)據(jù)元素之間的相互關(guān)系的集合，包括了數(shù)據(jù)的合，包括了數(shù)據(jù)的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)邏輯結(jié)構(gòu)、物理結(jié)構(gòu)以及以及數(shù)據(jù)的運(yùn)算。數(shù)據(jù)的運(yùn)算。4.3.1 基本概念基本概念2021-12-531計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論31u數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)主要研究主要研究：1.1. 數(shù)據(jù)集合中數(shù)據(jù)元素之間所數(shù)據(jù)集合中數(shù)據(jù)元素之間所固有固有的關(guān)系的關(guān)系，即，即數(shù)據(jù)

23、數(shù)據(jù)邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)；2.2. 數(shù)據(jù)處理時(shí)數(shù)據(jù)在計(jì)算機(jī)中的數(shù)據(jù)處理時(shí)數(shù)據(jù)在計(jì)算機(jī)中的存儲關(guān)系存儲關(guān)系，即，即數(shù)據(jù)數(shù)據(jù)存儲結(jié)構(gòu)存儲結(jié)構(gòu)；3.3. 對數(shù)據(jù)所進(jìn)行的對數(shù)據(jù)所進(jìn)行的操作操作，即，即算法算法。4.3.1 基本概念基本概念2021-12-532計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論4.3.1 基本概念基本概念2021-12-533計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論33數(shù)據(jù)邏輯結(jié)構(gòu)數(shù)據(jù)邏輯結(jié)構(gòu) u數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素之間所數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素之間所固有的關(guān)系固有的關(guān)系描描述成述成前后件前后件（前驅(qū)與后繼）關(guān)系。（前驅(qū)與后繼）關(guān)系。 u數(shù)據(jù)之間數(shù)據(jù)之間前后件關(guān)系前后件關(guān)系是是它們之間的它們之間的邏輯關(guān)邏輯關(guān)系系，

24、與與它們在計(jì)算機(jī)中它們在計(jì)算機(jī)中存儲位置無關(guān)存儲位置無關(guān)，因，因此將這種關(guān)系此將這種關(guān)系稱為數(shù)據(jù)邏輯結(jié)構(gòu)稱為數(shù)據(jù)邏輯結(jié)構(gòu)。2021-12-534計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論34一個(gè)數(shù)據(jù)結(jié)構(gòu)可以表示為：一個(gè)數(shù)據(jù)結(jié)構(gòu)可以表示為： S=S=（D D，R R）S S: : 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)D D: : 數(shù)據(jù)元素集合數(shù)據(jù)元素集合R: R: D D中數(shù)據(jù)元素之間中數(shù)據(jù)元素之間前后件關(guān)系前后件關(guān)系集合集合， 即數(shù)據(jù)邏輯結(jié)構(gòu)即數(shù)據(jù)邏輯結(jié)構(gòu)兩個(gè)兩個(gè)元素之間前后件關(guān)系用一個(gè)元素之間前后件關(guān)系用一個(gè)二元組二元組表示，如：表示，如：( (a a1 1, ,a a2 2) ) 2021-12-535計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)

25、科學(xué)導(dǎo)論35事實(shí)上可能有：事實(shí)上可能有： 如如樹形樹形結(jié)構(gòu)中的結(jié)構(gòu)中的一個(gè)元素一個(gè)元素有多個(gè)后件有多個(gè)后件或如或如網(wǎng)狀網(wǎng)狀結(jié)構(gòu)中的結(jié)構(gòu)中的一個(gè)元素一個(gè)元素有多個(gè)前件有多個(gè)前件因此一般來說，數(shù)據(jù)之間有因此一般來說，數(shù)據(jù)之間有4 4種種基本邏輯結(jié)構(gòu)：基本邏輯結(jié)構(gòu)：u 集合集合u 線性線性u 樹形樹形u 圖形圖形2021-12-536計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論36線性結(jié)構(gòu)線性結(jié)構(gòu)一對一關(guān)系一對一關(guān)系 集合集合 松散關(guān)系松散關(guān)系樹形結(jié)構(gòu)樹形結(jié)構(gòu)一對多關(guān)系一對多關(guān)系圖形結(jié)構(gòu)圖形結(jié)構(gòu)多對多關(guān)系多對多關(guān)系2021-12-537計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論37u非線性結(jié)構(gòu)非線性結(jié)構(gòu)：有多個(gè)有多個(gè)開始開始結(jié)點(diǎn)

26、和多個(gè)結(jié)點(diǎn)和多個(gè)終端終端結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)可有多個(gè)前件和多個(gè)后件結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)可有多個(gè)前件和多個(gè)后件u線性結(jié)構(gòu)線性結(jié)構(gòu)：有且只有有且只有一個(gè)一個(gè)開始開始結(jié)點(diǎn)和一個(gè)結(jié)點(diǎn)和一個(gè)終端終端結(jié)點(diǎn)，并且每個(gè)結(jié)點(diǎn)最多只有一個(gè)前結(jié)點(diǎn)，并且每個(gè)結(jié)點(diǎn)最多只有一個(gè)前件和一個(gè)后件，線性結(jié)構(gòu)件和一個(gè)后件，線性結(jié)構(gòu)也稱為也稱為線性表線性表。 u根據(jù)根據(jù)前后件關(guān)系的前后件關(guān)系的復(fù)雜程度復(fù)雜程度，數(shù)據(jù)邏輯結(jié)，數(shù)據(jù)邏輯結(jié)構(gòu)分為構(gòu)分為2 2類類。 2021-12-538計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論38數(shù)據(jù)物理結(jié)構(gòu)數(shù)據(jù)物理結(jié)構(gòu) u定義：定義：數(shù)據(jù)在計(jì)算機(jī)數(shù)據(jù)在計(jì)算機(jī)存儲器中的存儲方式存儲器中的存儲方式 稱為稱為數(shù)據(jù)存儲結(jié)構(gòu)數(shù)據(jù)存儲結(jié)構(gòu)

27、（或數(shù)據(jù)物理結(jié)構(gòu)）。（或數(shù)據(jù)物理結(jié)構(gòu)）。u數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素之間數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素之間在計(jì)算機(jī)中的在計(jì)算機(jī)中的位置關(guān)系位置關(guān)系與與邏輯關(guān)系邏輯關(guān)系不一定相同不一定相同。 u在數(shù)據(jù)在數(shù)據(jù)存儲結(jié)構(gòu)中，存儲結(jié)構(gòu)中，不僅要不僅要存放各個(gè)數(shù)據(jù)元素信息，存放各個(gè)數(shù)據(jù)元素信息，還要還要存放數(shù)據(jù)元素之間存放數(shù)據(jù)元素之間前后件關(guān)系前后件關(guān)系信息。信息。u數(shù)據(jù)數(shù)據(jù)存儲結(jié)構(gòu)存儲結(jié)構(gòu)是是邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲器中的在計(jì)算機(jī)存儲器中的表示表示2021-12-539計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論39數(shù)據(jù)元素在計(jì)算機(jī)中通常有數(shù)據(jù)元素在計(jì)算機(jī)中通常有四種四種存儲方式：存儲方式：u 順序順序u 鏈?zhǔn)芥準(zhǔn)絬 索引索引u 散列

28、散列常用常用順序順序存儲結(jié)構(gòu)和存儲結(jié)構(gòu)和鏈?zhǔn)芥準(zhǔn)酱鎯Y(jié)構(gòu)。存儲結(jié)構(gòu)。 數(shù)據(jù)物理結(jié)構(gòu)數(shù)據(jù)物理結(jié)構(gòu) 2021-12-540計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論40順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)u在存儲器中開辟一塊在存儲器中開辟一塊連續(xù)連續(xù)的單元用于存放數(shù)據(jù)，的單元用于存放數(shù)據(jù)，邏輯上相鄰的邏輯上相鄰的結(jié)點(diǎn)結(jié)點(diǎn)在物理位置上也鄰接在物理位置上也鄰接，結(jié)點(diǎn)之，結(jié)點(diǎn)之間的邏輯關(guān)系是由存儲單元間的邏輯關(guān)系是由存儲單元相鄰關(guān)系相鄰關(guān)系來體現(xiàn)。來體現(xiàn)。數(shù)據(jù)地址A12000HA22001HA32002HA42003H2021-12-541計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論41鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)結(jié)點(diǎn)結(jié)點(diǎn)由兩部分組成由兩部分組成：

29、 數(shù)據(jù)域數(shù)據(jù)域用于存放數(shù)據(jù)元素用于存放數(shù)據(jù)元素值值 指針域指針域用于存放前件或后件的用于存放前件或后件的存儲地址存儲地址鏈?zhǔn)酱鎯Y(jié)構(gòu)是鏈?zhǔn)酱鎯Y(jié)構(gòu)是通過指針通過指針反映數(shù)據(jù)間的邏輯關(guān)系。反映數(shù)據(jù)間的邏輯關(guān)系。a14003Ha22506Ha32509Ha42000H2001H4003H3004H2506H2507H2509H2510H2021-12-542計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論回回 顧顧程序設(shè)計(jì)步驟程序設(shè)計(jì)步驟程序設(shè)計(jì)方法程序設(shè)計(jì)方法l結(jié)構(gòu)化程序設(shè)計(jì)方法結(jié)構(gòu)化程序設(shè)計(jì)方法l面向?qū)ο蟮某绦蛟O(shè)計(jì)方法面向?qū)ο蟮某绦蛟O(shè)計(jì)方法 數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)的基本概念2021-12-543計(jì)算機(jī)科學(xué)導(dǎo)論

30、計(jì)算機(jī)科學(xué)導(dǎo)論4.3.2 幾種典型的數(shù)據(jù)結(jié)構(gòu)幾種典型的數(shù)據(jù)結(jié)構(gòu)1 1線性表線性表2 2棧棧3 3隊(duì)列隊(duì)列4 4線性表線性表5 5圖圖2021-12-544計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論 定義定義 線性表是一組線性表是一組特征相同特征相同數(shù)據(jù)的有限序列，表數(shù)據(jù)的有限序列，表示為：示為： L=(a1,a2,a3,an) L=(a1,a2,a3,an)。 有限個(gè)有限個(gè)同類的數(shù)據(jù)元素同類的數(shù)據(jù)元素構(gòu)成的序列。構(gòu)成的序列。4.3.2 幾種典型的數(shù)據(jù)結(jié)構(gòu)幾種典型的數(shù)據(jù)結(jié)構(gòu)1 1線性表線性表2021-12-545計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論 有且僅有一個(gè)有且僅有一個(gè)“第一個(gè)第一個(gè)”數(shù)據(jù)元素?cái)?shù)據(jù)元素 有且僅有一

31、個(gè)有且僅有一個(gè)“最后一個(gè)最后一個(gè)”數(shù)據(jù)元素?cái)?shù)據(jù)元素 除第一個(gè)數(shù)據(jù)元素外，其它元素有且僅有一個(gè)除第一個(gè)數(shù)據(jù)元素外，其它元素有且僅有一個(gè)直直接前驅(qū)接前驅(qū) 除最后一個(gè)數(shù)據(jù)元素外，其它元素有且僅有一個(gè)除最后一個(gè)數(shù)據(jù)元素外，其它元素有且僅有一個(gè)直接后繼直接后繼4.3.2 幾種典型的數(shù)據(jù)結(jié)構(gòu)幾種典型的數(shù)據(jù)結(jié)構(gòu)1 1線性表線性表2021-12-546計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論u例如英文字母表（例如英文字母表（A A，B B，C C，Z Z）是線）是線性表，表中的每個(gè)字母就是一個(gè)數(shù)據(jù)元素性表，表中的每個(gè)字母就是一個(gè)數(shù)據(jù)元素。u一副撲克的點(diǎn)數(shù)（一副撲克的點(diǎn)數(shù)（2 2，3 3，4 4，J J，Q Q，K K，A

32、 A）也是線性表，其中每一張牌的點(diǎn)數(shù)是）也是線性表，其中每一張牌的點(diǎn)數(shù)是一個(gè)數(shù)據(jù)元素。一個(gè)數(shù)據(jù)元素。4.3.2 幾種典型的數(shù)據(jù)結(jié)構(gòu)幾種典型的數(shù)據(jù)結(jié)構(gòu)1 1線性表線性表2021-12-547計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論 線性表通常采用順序和鏈表兩種物理實(shí)現(xiàn)。線性表通常采用順序和鏈表兩種物理實(shí)現(xiàn)。對于經(jīng)常變化的表，通常采取鏈表結(jié)構(gòu)。對于經(jīng)常變化的表，通常采取鏈表結(jié)構(gòu)。 線性表常用的運(yùn)算主要有：插入、刪除、線性表常用的運(yùn)算主要有：插入、刪除、查詢和遍歷。查詢和遍歷。4.3.2 幾種典型的數(shù)據(jù)結(jié)構(gòu)幾種典型的數(shù)據(jù)結(jié)構(gòu)1 1線性表線性表2021-12-548計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論482. 2. 棧棧

33、棧是只能棧是只能在表的在表的一端一端進(jìn)行插入和刪除運(yùn)算的線性表進(jìn)行插入和刪除運(yùn)算的線性表 u允許插入和刪除允許插入和刪除運(yùn)算的一端稱為運(yùn)算的一端稱為棧頂棧頂，另一端稱，另一端稱為為棧底棧底。插入插入元素操作稱為元素操作稱為入棧入棧刪除刪除元素操作稱為元素操作稱為出棧出棧4.3.2 幾種典型的數(shù)據(jù)結(jié)構(gòu)幾種典型的數(shù)據(jù)結(jié)構(gòu)2021-12-549計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論49 a a1 1 a a2 2 a an n棧底棧底bottombottom棧頂棧頂toptop入棧入棧出棧出棧2021-12-550計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論 D C B A 入棧數(shù)據(jù)元素 E E D C B A D C B

34、A 出棧數(shù)據(jù)元素D C B A 4.3.2 幾種典型的數(shù)據(jù)結(jié)構(gòu)幾種典型的數(shù)據(jù)結(jié)構(gòu)棧是一種棧是一種“后進(jìn)先出后進(jìn)先出”或或“先進(jìn)后出先進(jìn)后出”的數(shù)據(jù)結(jié)構(gòu)。的數(shù)據(jù)結(jié)構(gòu)。2021-12-551計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論 例如用桶堆積物品，先堆進(jìn)來的壓在底下例如用桶堆積物品，先堆進(jìn)來的壓在底下，隨后一件一件往堆。取走時(shí)，只能從上，隨后一件一件往堆。取走時(shí)，只能從上面一件一件取。面一件一件取。4.3.2 幾種典型的數(shù)據(jù)結(jié)構(gòu)幾種典型的數(shù)據(jù)結(jié)構(gòu)2021-12-552計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論523. 3. 隊(duì)列隊(duì)列 只允許：只允許：在在一端一端進(jìn)行進(jìn)行插入插入運(yùn)算，運(yùn)算， 而在而在另一端另一端進(jìn)行進(jìn)行刪

35、除刪除運(yùn)算的線性表。運(yùn)算的線性表。u允許允許刪除刪除的一端稱為的一端稱為隊(duì)首（隊(duì)頭）隊(duì)首（隊(duì)頭）u允許允許插入插入的一端稱為的一端稱為隊(duì)尾隊(duì)尾4.3.2 幾種典型的數(shù)據(jù)結(jié)構(gòu)幾種典型的數(shù)據(jù)結(jié)構(gòu)2021-12-553計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論533. 3. 隊(duì)列隊(duì)列4.3.2 幾種典型的數(shù)據(jù)結(jié)構(gòu)幾種典型的數(shù)據(jù)結(jié)構(gòu) a a1 1 a a2 2 a an n隊(duì)頭隊(duì)頭出隊(duì)出隊(duì)隊(duì)尾隊(duì)尾入隊(duì)入隊(duì)2021-12-554計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論 A B C D E 頭指針 尾指針 A B C D E F G 頭指針 尾指針 F，G 入隊(duì) 4.3.2 幾種典型的數(shù)據(jù)結(jié)構(gòu)幾種典型的數(shù)據(jù)結(jié)構(gòu)2021-12-55

36、5計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論 A B C D E 頭指針 尾指針 D E F G 頭指針 尾指針 A，B，C 出隊(duì) 4.3.2 幾種典型的數(shù)據(jù)結(jié)構(gòu)幾種典型的數(shù)據(jù)結(jié)構(gòu)2021-12-556計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論4. 4. 樹樹在樹型結(jié)構(gòu)中，每個(gè)數(shù)據(jù)元素稱為一在樹型結(jié)構(gòu)中，每個(gè)數(shù)據(jù)元素稱為一個(gè)結(jié)點(diǎn)，除了唯一的根結(jié)點(diǎn)外，其他每個(gè)結(jié)點(diǎn)，除了唯一的根結(jié)點(diǎn)外，其他每個(gè)結(jié)點(diǎn)都有且僅有一個(gè)父結(jié)點(diǎn)，每個(gè)元個(gè)結(jié)點(diǎn)都有且僅有一個(gè)父結(jié)點(diǎn)，每個(gè)元素可以有多個(gè)子結(jié)點(diǎn)。素可以有多個(gè)子結(jié)點(diǎn)。 樹結(jié)構(gòu)在客觀世界中廣泛存在，如樹結(jié)構(gòu)在客觀世界中廣泛存在，如人類社會的族譜和各種社會組織機(jī)構(gòu)都人類社會的族譜和各種社會組織機(jī)構(gòu)

37、都可用樹形象表示可用樹形象表示。4.3.2 幾種典型的數(shù)據(jù)結(jié)構(gòu)幾種典型的數(shù)據(jù)結(jié)構(gòu)2021-12-557計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論 Left A Right Left B Right C Right D E F 4.3.2 幾種典型的數(shù)據(jù)結(jié)構(gòu)幾種典型的數(shù)據(jù)結(jié)構(gòu)2021-12-558計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論5. 5. 圖圖圖形結(jié)構(gòu)是一種比樹型結(jié)構(gòu)更復(fù)雜的非線圖形結(jié)構(gòu)是一種比樹型結(jié)構(gòu)更復(fù)雜的非線性結(jié)構(gòu)。在圖形結(jié)構(gòu)中，每個(gè)數(shù)據(jù)元素稱性結(jié)構(gòu)。在圖形結(jié)構(gòu)中，每個(gè)數(shù)據(jù)元素稱為一個(gè)頂點(diǎn)，為一個(gè)頂點(diǎn)，任意兩個(gè)頂點(diǎn)之間都可能相任意兩個(gè)頂點(diǎn)之間都可能相關(guān)關(guān)，這種相關(guān)性用一條邊來表示，頂點(diǎn)之，這種相關(guān)性用一條邊

38、來表示，頂點(diǎn)之間的鄰接關(guān)系可以是任意的間的鄰接關(guān)系可以是任意的。4.3.2 幾種典型的數(shù)據(jù)結(jié)構(gòu)幾種典型的數(shù)據(jù)結(jié)構(gòu)2021-12-559計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論 A B C D E A B E B A C E C B D E A B D D C E 0 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 1 1 1 0 1 0 A B C D E A B C D E (a) (b) (c) 2021-12-560計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論4.3.2 幾種典型的數(shù)據(jù)結(jié)構(gòu)幾種典型的數(shù)據(jù)結(jié)構(gòu)1 1線性表線性表2 2棧棧3 3隊(duì)列隊(duì)列4 4線性表線性表5 5圖圖2021-12-

39、561計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論4.3.3 查找查找u查找是指根據(jù)給定的某個(gè)值，在查找表中查找是指根據(jù)給定的某個(gè)值，在查找表中確定一確定一個(gè)其關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素個(gè)其關(guān)鍵字等于給定值的記錄或數(shù)據(jù)元素。u若表中存在這樣的一個(gè)記錄，則稱查找是成功的，若表中存在這樣的一個(gè)記錄，則稱查找是成功的，此時(shí)查找的結(jié)果為給出整個(gè)記錄的信息，或指示此時(shí)查找的結(jié)果為給出整個(gè)記錄的信息，或指示該記錄在查找表中的位置；該記錄在查找表中的位置；u若表中不存在關(guān)鍵字等于給定值的記錄，則稱查若表中不存在關(guān)鍵字等于給定值的記錄，則稱查找失敗，此時(shí)查找的結(jié)果可給出一個(gè)找失敗，此時(shí)查找的結(jié)果可給出一個(gè)“空空”記錄記

40、錄或或“空空”指針。指針。2021-12-562計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論1 1順序查找順序查找2 2二分查找二分查找3 3分塊查找分塊查找4.3.3 查找查找2021-12-563計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論1 1順序查找順序查找 順序查找是在一個(gè)隊(duì)列中順序查找是在一個(gè)隊(duì)列中找出與給定關(guān)鍵找出與給定關(guān)鍵字相同數(shù)值的具體位置字相同數(shù)值的具體位置。 原理是讓關(guān)鍵字與隊(duì)列中的數(shù)原理是讓關(guān)鍵字與隊(duì)列中的數(shù)從第一個(gè)開從第一個(gè)開始逐個(gè)比較始逐個(gè)比較，直到找出與給定關(guān)鍵字相同的數(shù)，直到找出與給定關(guān)鍵字相同的數(shù)值為止值為止。4.3.3 查找查找2021-12-564計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論2 2二分查

41、找二分查找l將表將表中間位置中間位置記錄的關(guān)鍵字與查找關(guān)鍵字進(jìn)行記錄的關(guān)鍵字與查找關(guān)鍵字進(jìn)行比較，比較，l如果兩者相等，則查找成功；否則如果兩者相等，則查找成功；否則利用中間位利用中間位置記錄將表分成前、后兩個(gè)子表置記錄將表分成前、后兩個(gè)子表，l如果中間位置記錄的關(guān)鍵字小于查找關(guān)鍵字，如果中間位置記錄的關(guān)鍵字小于查找關(guān)鍵字，則進(jìn)一步查找前一子表（假定隊(duì)列是從小到大則進(jìn)一步查找前一子表（假定隊(duì)列是從小到大排列），否則進(jìn)一步查找后一子表。排列），否則進(jìn)一步查找后一子表。l重復(fù)以上過程，直至找到滿足條件的記錄，使重復(fù)以上過程，直至找到滿足條件的記錄，使查找成功，或直至子表不存在為止，此時(shí)查找查找成功

42、，或直至子表不存在為止，此時(shí)查找失敗。失敗。4.3.3 查找查找2021-12-565計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論一個(gè)有序表中有一個(gè)有序表中有1313個(gè)記錄，記錄的關(guān)鍵字序列個(gè)記錄，記錄的關(guān)鍵字序列為（為（7 7，1414，1818，2121，2323，2929，3131，3535，3838，4242，4646，4949，5252），給定值），給定值k k為為1414，在表中查找關(guān)，在表中查找關(guān)鍵字與鍵字與k k相等的記錄。相等的記錄。2021-12-566計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論2021-12-567計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論3 3分塊查找分塊查找分塊查找又稱索引順序查找，它是順序查找

43、的分塊查找又稱索引順序查找，它是順序查找的一種改進(jìn)方法。一種改進(jìn)方法。分塊的原則是將分塊的原則是將n n個(gè)數(shù)據(jù)元素個(gè)數(shù)據(jù)元素“按塊有序按塊有序”劃劃分為分為m m塊（塊（m nm n）。）。每一塊中的結(jié)點(diǎn)不必有每一塊中的結(jié)點(diǎn)不必有序，但塊與塊之間必須序，但塊與塊之間必須“按塊有序按塊有序”；即第；即第1 1塊中任一元素的關(guān)鍵字都必須小于第塊中任一元素的關(guān)鍵字都必須小于第2 2塊中任塊中任一元素的關(guān)鍵字；而第一元素的關(guān)鍵字；而第2 2塊中任一元素又都必塊中任一元素又都必須小于第須小于第3 3塊中的任一元素等。塊中的任一元素等。4.3.3 查找查找2021-12-568計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論

44、3 3分塊查找分塊查找分塊查找是首先選取各塊中的分塊查找是首先選取各塊中的最大關(guān)鍵字最大關(guān)鍵字構(gòu)構(gòu)成一個(gè)索引表；成一個(gè)索引表；然后查找分兩個(gè)部分：先對索引表進(jìn)行二分然后查找分兩個(gè)部分：先對索引表進(jìn)行二分查找或已確定待查記錄在哪一塊中；最后在查找或已確定待查記錄在哪一塊中；最后在已確定的塊中用順序法進(jìn)行查找。已確定的塊中用順序法進(jìn)行查找。4.3.3 查找查找2021-12-569計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論2021-12-570計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論1 1順序查找順序查找2 2二分查找二分查找3 3分塊查找分塊查找4.3.3 查找查找2021-12-571計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論4.3

45、.4 排序排序排序是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作。排序是計(jì)算機(jī)程序設(shè)計(jì)中的一種重要操作。簡單地說，排序就是要整理文件中的記錄，簡單地說，排序就是要整理文件中的記錄，使之按使之按關(guān)鍵字遞增關(guān)鍵字遞增( (或遞減或遞減) )次序排列起來次序排列起來。2021-12-572計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論4.3.4 排序排序如果按排序過程中依據(jù)的不同原則對內(nèi)部如果按排序過程中依據(jù)的不同原則對內(nèi)部排序方法進(jìn)行分類，則可分為排序方法進(jìn)行分類，則可分為直接插入排直接插入排序、冒泡排序、快速排序序、冒泡排序、快速排序等。等。2021-12-573計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論1 1直接插入排序直接插入排序基本操

46、作是將一個(gè)記錄插入到已排好序的基本操作是將一個(gè)記錄插入到已排好序的有序表中，從而得到一個(gè)新的、記錄數(shù)增有序表中，從而得到一個(gè)新的、記錄數(shù)增1 1的有序表。的有序表。4.3.4 排序排序2021-12-574計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論1 1直接插入排序直接插入排序基本思想是：基本思想是：每步將一個(gè)待排序的對象，按其每步將一個(gè)待排序的對象，按其關(guān)鍵碼大小，插入到前面已經(jīng)排好序的一組對關(guān)鍵碼大小，插入到前面已經(jīng)排好序的一組對象的象的適當(dāng)位置適當(dāng)位置上，直到對象全部插入為止。上，直到對象全部插入為止。簡言之，邊插入邊排序，保證子序列中隨時(shí)都是排好簡言之，邊插入邊排序，保證子序列中隨時(shí)都是排好序的序的

47、。4.3.4 排序排序2021-12-575計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論初始關(guān)鍵字序列：初始關(guān)鍵字序列：【13】, 6, 3, 31, 9, 27, 5, 11第一次排序：第一次排序： 【6, 13】, 3, 31, 9, 27, 5, 11第二次排序：第二次排序： 【3, 6, 13】, 31, 9, 27, 5, 11第三次排序：第三次排序： 【3, 6, 13，31】, 9, 27, 5, 11第四次排序：第四次排序： 【3, 6, 9, 13，31】, 27, 5, 11第五次排序：第五次排序： 【3, 6, 9, 13，27, 31】, 5, 11第六次排序：第六次排序： 【3, 5

48、, 6, 9, 13，27, 31】, 11第七次排序：第七次排序： 【3, 5, 6, 9, 11，13，27, 31】 例：例：關(guān)鍵字序列關(guān)鍵字序列T=（13，6，3，31，9，27，5，11），）， 請寫出直接插入排序的中間過程序列。請寫出直接插入排序的中間過程序列。注：注：方括號方括號 中為已排序記錄的關(guān)鍵字，下劃橫線的中為已排序記錄的關(guān)鍵字，下劃橫線的 關(guān)鍵字關(guān)鍵字表示它對應(yīng)的記錄后移一個(gè)位置。表示它對應(yīng)的記錄后移一個(gè)位置。2021-12-576計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論2 2冒泡排序冒泡排序 冒泡排序是通過冒泡排序是通過交換兩個(gè)元素交換兩個(gè)元素實(shí)現(xiàn)的，它的思想是：設(shè)有數(shù)組實(shí)現(xiàn)的，

49、它的思想是：設(shè)有數(shù)組An+1(nAn+1(n為序列中元素個(gè)數(shù)為序列中元素個(gè)數(shù)) )，第一趟在序列，第一趟在序列(A0-An-1)(A0-An-1)中中從前往后進(jìn)行兩個(gè)元素的比較，如后者小，則交換，比較從前往后進(jìn)行兩個(gè)元素的比較，如后者小，則交換，比較n-1n-1次；次；第一趟排序結(jié)束，最大元素被交換到第一趟排序結(jié)束，最大元素被交換到An-1An-1中中( (即沉底即沉底) )，下一趟排序只要在子序列下一趟排序只要在子序列(A0-An-2)(A0-An-2)中進(jìn)行；如果在某一中進(jìn)行；如果在某一趟排序中未交換元素，說明子序列已經(jīng)有序，則不再進(jìn)行下一趟排序中未交換元素，說明子序列已經(jīng)有序，則不再進(jìn)行

50、下一趟排序。趟排序。4.3.4 排序排序2021-12-577計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論2 2冒泡排序冒泡排序基本思路：基本思路：每趟不斷將記錄兩兩比較，每趟不斷將記錄兩兩比較，并按并按“前小后大前小后大”規(guī)則交換。規(guī)則交換。優(yōu)點(diǎn)：優(yōu)點(diǎn)：每趟結(jié)束時(shí)，不僅能擠出一個(gè)最每趟結(jié)束時(shí)，不僅能擠出一個(gè)最大值到最后面位置，還能大值到最后面位置，還能同時(shí)部分理順同時(shí)部分理順其他元素其他元素；一旦下趟沒有交換發(fā)生，還；一旦下趟沒有交換發(fā)生，還可以可以提前結(jié)束排序提前結(jié)束排序。4.3.4 排序排序2021-12-578計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論例：例：關(guān)鍵字序列關(guān)鍵字序列 T=(21，25，49，25*，1

51、6，08），），請按從小到大的順序，寫出冒泡排序請按從小到大的順序，寫出冒泡排序的具體實(shí)現(xiàn)過程。的具體實(shí)現(xiàn)過程。初態(tài)：初態(tài)：第第1趟趟第第2趟趟第第3趟趟第第4趟趟第第5趟趟21，25，49， 25*，16， 0821，25，25*，16， 08 ， 4921，25， 16， 08 ，25*，4921，16， 08 ，25， 25*，4916，08 ，21， 25， 25*，4908，16， 21， 25， 25*，492021-12-579計(jì)算機(jī)科學(xué)導(dǎo)論計(jì)算機(jī)科學(xué)導(dǎo)論3 3快速排序快速排序 基本思想是：對任意給定的系列中存在元素基本思想是：對任意給定的系列中存在元素R R，經(jīng)過一趟排，經(jīng)過一

52、趟排序后，將原序列分割成兩個(gè)子序列序后，將原序列分割成兩個(gè)子序列( (R Rp(0)p(0), , R Rp(1)p(1), , ,R Rp(s-1)p(s-1) )和和( (R Rp(s+1)p(s+1), , R Rp(s+2)p(s+2), , ,R Rp(n-1)p(n-1),),其中其中前一個(gè)子序列中的所有前一個(gè)子序列中的所有元素的關(guān)鍵字均小于或等于該元素的關(guān)鍵字值元素的關(guān)鍵字均小于或等于該元素的關(guān)鍵字值K Kp(sp(s) ), ,后一個(gè)后一個(gè)子序列中元素的關(guān)鍵字均大于或等于子序列中元素的關(guān)鍵字均大于或等于K Kp(sp(s) )。稱該元素。稱該元素R R= =R Rp(sp(s) )為分割元素，子序列為分割元素，子序列( (R Rp(0)p(0), , R Rp(1)p(1), , ,R Rp(s-1)p(s-1) )為其低端系列，為其低端系列，( (R Rp(s+1)p