計算機(jī)導(dǎo)論-基于計算思維PPT完整全套教學(xué)課件

計算機(jī)導(dǎo)論——基于計算思維1第1章計算機(jī)概述第2章數(shù)據(jù)表示第3章計算思維與常用算法第4章計算機(jī)系統(tǒng)第5章數(shù)據(jù)結(jié)構(gòu)第6章計算機(jī)網(wǎng)絡(luò)第7章計算機(jī)信息安全和職業(yè)道德第1章計算機(jī)概論2鏈棧用單鏈表表示目錄31.1計算機(jī)的產(chǎn)生與發(fā)展1.2人工智能1.3云計算1.4大數(shù)據(jù)1.1計算機(jī)的產(chǎn)生與發(fā)展41.1.1

計算機(jī)的產(chǎn)生1.1.2計算機(jī)的發(fā)展歷史1.1.3計算機(jī)的發(fā)展趨勢1.1.1計算機(jī)的產(chǎn)生5

手動式計算工具

機(jī)械式計算工具

機(jī)電式計算機(jī)

電子計算機(jī)問世6

手動式計算工具算籌：可以用加法和一位數(shù)乘法代替多位數(shù)乘法，也可以用除數(shù)為一位數(shù)的除法和減法代替多位數(shù)除法，從而大大簡化了數(shù)值計算過程。對數(shù)計算尺：不僅能進(jìn)行加、減、乘、除、乘方、開方運(yùn)算，甚至可以計算三角函數(shù)、指數(shù)函數(shù)和對數(shù)函數(shù)，它一直使用到袖珍電子計算器面世。納皮爾算籌對數(shù)計算尺7

機(jī)械式計算工具1642年，法國數(shù)學(xué)家帕斯卡發(fā)明了帕斯卡加法器，這是人類歷史上第一臺機(jī)械式計算工具；1822年，英國數(shù)學(xué)家巴貝奇研制出差分機(jī)，是最早采用寄存器來存儲數(shù)據(jù)的計算工具，體現(xiàn)了早期程序設(shè)計思想的萌芽，使計算工具從手動機(jī)械躍入自動機(jī)械的新時代；1834年，巴貝奇設(shè)計出了分析機(jī)采用了三個具有現(xiàn)代意義的裝置：存儲裝置、運(yùn)算裝置和控制裝置。8

機(jī)械式計算工具帕斯卡加法器分析機(jī)9

機(jī)電式計算機(jī)1886年，美國統(tǒng)計學(xué)家赫爾曼·霍勒瑞斯用穿孔卡片存儲數(shù)據(jù)，制造了第一臺可以自動進(jìn)行加減四則運(yùn)算、累計存檔、制作報表的制表機(jī)；1938年，德國工程師朱斯研制出Z-1計算機(jī)，這是第一臺采用二進(jìn)制的計算機(jī)。Z-3是世界上第一臺真正的通用程序控制計算機(jī)，不僅全部采用繼電器，同時采用了浮點(diǎn)記數(shù)法、二進(jìn)制運(yùn)算、帶存儲地址的指令形式等。10

機(jī)電式計算機(jī)1944年美國人霍華德·愛肯制造出了著名的MARK-I計算機(jī)，存儲容量為72個23位十進(jìn)制數(shù)，采用了穿孔紙帶進(jìn)行程序控制，執(zhí)行一次加法操作需要0.3秒；制表機(jī)Mark-I計算機(jī)11

電子計算機(jī)ENIAC計算機(jī)

ENIAC“埃尼阿克”，世界上第一臺電子計算機(jī)。

美國國防部用來進(jìn)行彈道計算。

該機(jī)器字長為10位十進(jìn)制數(shù)，計算速度每秒鐘可進(jìn)行5000次運(yùn)算。

每次至多只能存儲20個字長為10位的十進(jìn)制數(shù)。

計算程序是通過“外接”線路，而不是采用“存儲”方式。

為了在機(jī)器上運(yùn)行幾分鐘的計算程序，其準(zhǔn)備工作要花去幾小時甚至1~2天的時間。12

電子計算機(jī)ENIAC計算機(jī)13

馮·諾依曼計算機(jī)之父

馮·諾依曼被稱為計算機(jī)之父，他和他的同事們研制了電子數(shù)字計算機(jī)ENIAC，提出了存儲程序控制原理的數(shù)字計算機(jī)結(jié)構(gòu)，并在電子計算機(jī)EDVAC中采用了這一原理，對后來的計算機(jī)的體系結(jié)構(gòu)和工作原理產(chǎn)生了重大的影響。

電子計算機(jī)14

第一代計算機(jī)（1946年~1957年，電子管時代）

第二代計算機(jī)（1958年~1964年，晶體管時代）

第三代計算機(jī)（1965年~1970年）

第四代計算機(jī)（1970年至今）1.1.2計算機(jī)的發(fā)展歷史15邏輯元件是真空電子管；

主存儲器采用汞延遲線、陰極射線示波管靜電存儲器磁鼓、磁芯；

外存儲器采用的是磁帶；軟件方面采用的是機(jī)器語言、匯編語言；

應(yīng)用領(lǐng)域以軍事和科學(xué)計算為主；

代表機(jī)型：IBM公司的IBM700系列。第一代計算機(jī)（1946年~1957年，電子管時代）16馮諾依曼與莫爾小組合作，1950年第一臺馮?偌依曼結(jié)構(gòu)的計算機(jī)誕生；

該計算機(jī)根據(jù)馮諾依曼提出的計算機(jī)結(jié)構(gòu)和原理制造，改進(jìn)了第一臺計算機(jī)的不足；

提出了用二進(jìn)制代替十進(jìn)制，由運(yùn)算器、控制器、存儲器和輸入輸出設(shè)備構(gòu)成計算機(jī)。第一代計算機(jī)（1946年~1957年，電子管時代）17

馮·諾依曼計算機(jī)的功能①

把需要的程序和數(shù)據(jù)送至計算機(jī)中。②

必須具有長期記憶程序、數(shù)據(jù)、中間結(jié)果及最終運(yùn)算結(jié)果的能力。③

能夠完成各種算術(shù)、邏輯運(yùn)算和數(shù)據(jù)傳送等數(shù)據(jù)加工處理的能力。④

能夠根據(jù)需要控制程序走向，并能根據(jù)指令控制機(jī)器的各部件協(xié)調(diào)操作。⑤

能夠按照要求將處理結(jié)果輸出給用戶。第一代計算機(jī)（1946年~1957年，電子管時代）18

馮·諾依曼計算機(jī)的五大基本組成部件①

輸入數(shù)據(jù)和程序的輸入設(shè)備；②

記憶程序和數(shù)據(jù)的存儲器；③

完成數(shù)據(jù)加工處理的運(yùn)算器；④

控制程序執(zhí)行的控制器；⑤

輸出處理結(jié)果的輸出設(shè)備第一代計算機(jī)（1946年~1957年，電子管時代）19

馮·諾依曼計算機(jī)的基本思維

程序和數(shù)據(jù)事先存儲于存儲器中，由控制器從存儲器中一條接一條地讀取指令、分析指令并依據(jù)指令按時鐘節(jié)拍產(chǎn)生各種信號予以執(zhí)行。

它體現(xiàn)的是程序如何被存儲、如何被CPU執(zhí)行的基本思維。

理解馮·諾依曼計算機(jī)如何執(zhí)行程序?qū)τ诶盟惴ê统绦蚴侄谓鉀Q問題有重要的意義。第一代計算機(jī)（1946年~1957年，電子管時代）20第二代計算機(jī)（1958年~1964年，晶體管時代）邏輯元件是晶體管，主存儲器磁芯；

外存儲器采用的是磁盤和磁帶；

運(yùn)算速度可達(dá)每秒幾十萬次；軟件方面提出了操作系統(tǒng)的概念，開始使用FORTRAN、COBOL、ALGOL等高級語言；

應(yīng)用領(lǐng)域用于科學(xué)計算、商業(yè)數(shù)據(jù)處理和事務(wù)處理,并逐漸應(yīng)用于工業(yè)控制領(lǐng)域；

代表機(jī)型：IBM公司的IBM7000系列。21第三代計算機(jī)（1965年~1970年）

邏輯元件是中、小規(guī)模集成電路；

主存儲器是半導(dǎo)體存儲器，外存儲器采用的是磁盤；

運(yùn)算速度可達(dá)每秒幾百萬次；

軟件方面出現(xiàn)了操作系統(tǒng)和會話式語言以及結(jié)構(gòu)化程序設(shè)計的方法；計算機(jī)向標(biāo)準(zhǔn)化、多樣化和通用化發(fā)展，并開始應(yīng)用于各個領(lǐng)域；

代表機(jī)型：IBM公司的IBM360系列。22第四代計算機(jī)（1970年至今）

邏輯元件是大規(guī)模與超大規(guī)模集成電路，主存儲器是半導(dǎo)體存儲器；外存儲器采用的是大容量軟、硬磁盤，并開始引入光盤；

運(yùn)算速度可達(dá)億萬次以上；操作系統(tǒng)不斷完善，計算機(jī)軟件產(chǎn)業(yè)高度發(fā)展，已成為現(xiàn)代工業(yè)的一部分，計算機(jī)開始進(jìn)入了尖端科學(xué)，微型計算機(jī)進(jìn)入千家萬戶；

代表機(jī)型：我國國防科大“天河二號”，IBM公司的IBM4300系列等。1.1.3計算機(jī)的發(fā)展趨勢23

高性能計算

高性能計算(Highperformancecomputing)指通常使用很多處理器(作為單個機(jī)器的一部分)或者某一集群中組織的幾臺計算機(jī)(作為單個計算資源操作)的計算系統(tǒng)和環(huán)境。由于具有巨大的數(shù)值計算和數(shù)據(jù)處理能力，高性能計算能夠被廣泛地應(yīng)用于國民經(jīng)濟(jì)、國防建設(shè)和科技發(fā)展中具有深遠(yuǎn)影響的重大課題，如石油勘探、地震預(yù)測和預(yù)報、氣候模擬和大范圍天氣預(yù)報、航空航天飛行器、衛(wèi)星圖像處理、人類遺傳基因檢測等具有深遠(yuǎn)影響的領(lǐng)域，對國民經(jīng)濟(jì)和科學(xué)技術(shù)的發(fā)展，對軍事和國防建設(shè)具有十分重要的意義。1.1.3計算機(jī)的發(fā)展趨勢24

高性能計算

神威·太湖之光超級計算機(jī)是由國家并行計算機(jī)工程技術(shù)研究中心研制、安裝在國家超級計算無錫中心的超級計算機(jī)。

神威·太湖之光超級計算機(jī)安裝了40960個中國自主研發(fā)的“申威26010”眾核處理器，該眾核處理器采用64位自主申威指令系統(tǒng)，峰值性能為12.5億億次/秒，持續(xù)性能為9.3億億次/秒。1.1.3計算機(jī)的發(fā)展趨勢25

云計算定義：將計算資源，如計算節(jié)點(diǎn)、存儲節(jié)點(diǎn)等以服務(wù)的方式，即以可擴(kuò)展可組合的方式提供給客戶，客戶可按需定制、按需使用計算資源、這種計算能力被稱為云計算。分類：按照計算資源的劃分，可以將硬件部分，如計算節(jié)點(diǎn)、存儲節(jié)點(diǎn)等按服務(wù)提供，即基礎(chǔ)設(shè)施作為服務(wù)（InfrastructureasaService，IaaS）；也可以將操作系統(tǒng)、中間件等按服務(wù)提供，即平臺作為服務(wù)（PlatformasaService，PaaS）；也可以將應(yīng)用軟件等按服務(wù)提供，即軟件作為服務(wù)（SoftwareasaService，SaaS）。1.1.3計算機(jī)的發(fā)展趨勢26

智能計算

類似人的智能是使計算機(jī)能像人一樣的思考和判斷，讓計算機(jī)可以做過去只有人才能做的智能工作。1997年5月，超級計算機(jī)“深藍(lán)”戰(zhàn)勝了國際象棋特級大師卡斯帕羅夫。2016年3月15日，谷歌圍棋人工智能AlphaGo以4:1打敗世界頂尖圍棋高手韓國棋手李世石，標(biāo)志著這個“人類最后不能被計算機(jī)所打敗的游戲”告破。1.1.3計算機(jī)的發(fā)展趨勢27

智能計算

類似人的智能是使計算機(jī)能像人一樣的思考和判斷，讓計算機(jī)可以做過去只有人才能做的智能工作。1997年5月，超級計算機(jī)“深藍(lán)”戰(zhàn)勝了國際象棋特級大師卡斯帕羅夫。2016年3月15日，谷歌圍棋人工智能AlphaGo以4:1打敗世界頂尖圍棋高手韓國棋手李世石，標(biāo)志著這個“人類最后不能被計算機(jī)所打敗的游戲”告破。1.1.3計算機(jī)的發(fā)展趨勢28

智能計算的應(yīng)用（1）智能計算在利用搜索引擎進(jìn)行搜索時，輸入特征關(guān)鍵詞時使檢索結(jié)果越來越符合結(jié)果的期望值。（2）智能研究也在研究人的腦結(jié)構(gòu)并將其應(yīng)用于問題求解機(jī)器的設(shè)計中。（3）智能計算的例子就是模式識別。指紋識別技術(shù)及機(jī)器翻譯方面也得到廣泛應(yīng)用。1.1.3計算機(jī)的發(fā)展趨勢29

生物計算生物計算是指利用計算機(jī)技術(shù)研究生命體的特征和利用生命體的特征研究計算機(jī)的結(jié)構(gòu)、算法與芯片等技術(shù)的統(tǒng)稱。生物計算包含兩方面：

一方面，隨著新的計算機(jī)結(jié)構(gòu)和新的元器件的發(fā)展，計算機(jī)性能的提高，生物計算機(jī)成為一種新的選擇；

另一方面，借助計算機(jī)進(jìn)行分子生物信息研究，可以通過數(shù)量分析的途徑獲取突破性的成果。1.1.3計算機(jī)的發(fā)展趨勢30

生物計算

生物計算更重要的方面是利用計算機(jī)進(jìn)行基因組研究，運(yùn)用大規(guī)模高效的理論和數(shù)值計算，歸納、整理基因組的信息和特征，模擬生命體內(nèi)的信息流過程進(jìn)而揭示代謝、發(fā)育、分化、進(jìn)化的規(guī)律，探究人類健康和疾病的根源，并進(jìn)一步轉(zhuǎn)化為醫(yī)學(xué)領(lǐng)域的進(jìn)步從而為人類健康服務(wù)。1.2人工智能31

人工智能概念

人工智能的應(yīng)用1.2.1人工智能概念32

人工智能（ArtificialIntelligence），英文縮寫為AI。它是研究、開發(fā)用于模擬、延伸和擴(kuò)展人的智能的理論、方法、技術(shù)及應(yīng)用系統(tǒng)的一門新的技術(shù)科學(xué)。1.2.2人工智能的應(yīng)用33

人工智能的主要應(yīng)用領(lǐng)域有：（1）問題求解（2）邏輯推理與定理證明（3）自然語言理解（4）專家系統(tǒng)（5）機(jī)器學(xué)習(xí)（6）神經(jīng)網(wǎng)絡(luò)（7）機(jī)器人學(xué)（8）機(jī)器視覺1.3云計算34

云計算的概念

云計算的應(yīng)用

云計算的體系結(jié)構(gòu)1.3.1云計算的概念35

云計算是一種按使用量付費(fèi)的模式，這種模式提供可用的、便捷的、按需的網(wǎng)絡(luò)訪問，進(jìn)入可配置的計算資源共享池（資源包括網(wǎng)絡(luò)，服務(wù)器，存儲，應(yīng)用軟件，服務(wù)），這些資源能夠被快速提供，只需要投入的管理工作，或與服務(wù)供應(yīng)商進(jìn)行很少的交互。36云計算與分布式計算、效用計算、自主計算的差別：（1）分布式計算：把一個需要非常巨大的計算能力才能解決的問題分成許多小的部分，然后把這些部分分配給許多計算機(jī)進(jìn)行處理，最后把這些計算結(jié)果綜合起來得到最終結(jié)果。（2）效用計算：是一種提供服務(wù)的模型，在這個模型里服務(wù)提供商產(chǎn)生客戶需要的計算資源和基礎(chǔ)設(shè)施管理，并根據(jù)某個應(yīng)用，而不是僅僅按照速率進(jìn)行收費(fèi)。（3）自主計算：IBM將自主計算定義為“能夠保證電子商務(wù)基礎(chǔ)結(jié)構(gòu)服務(wù)水平的自我管理技術(shù)”。其最終目的在于使信息系統(tǒng)能夠自動地對自身進(jìn)行管理，并維持其可靠性。1.3.1云計算的概念37云計算的特點(diǎn)：（1）超大規(guī)模（2）虛擬化（3）高可靠性（4）通用性（5）高可靠性（6）按需服務(wù)（7）極其廉價1.3.2云計算的應(yīng)用38（1）存儲云（2）醫(yī)療云（3）金融云（4）教育云1.3.3云計算的體系結(jié)構(gòu)39服務(wù)接口服務(wù)注冊服務(wù)查找服務(wù)訪問服務(wù)工作流SOA構(gòu)建層服務(wù)接口用戶環(huán)境配置用戶交互管理使用計費(fèi)服務(wù)管理身份認(rèn)證訪問授權(quán)綜合防護(hù)安全審計安全管理任務(wù)調(diào)度任務(wù)執(zhí)行生命期管理映象部署和管理任務(wù)管理負(fù)載均衡故障檢測故障恢復(fù)監(jiān)視統(tǒng)計資源管理管理中間件層計算資源池存儲資源池網(wǎng)絡(luò)資源池數(shù)據(jù)資源池軟件資源池資源池層計算機(jī)存儲器網(wǎng)絡(luò)設(shè)施數(shù)據(jù)庫軟件物理資源層圖1云計算體系結(jié)構(gòu)1.4大數(shù)據(jù)40

大數(shù)據(jù)產(chǎn)生的背景

大數(shù)據(jù)的應(yīng)用場景

大數(shù)據(jù)的關(guān)鍵技術(shù)1.4.1大數(shù)據(jù)產(chǎn)生的背景41數(shù)據(jù)規(guī)模會急劇膨脹，有機(jī)器產(chǎn)生的結(jié)構(gòu)數(shù)據(jù)、人類產(chǎn)生的非結(jié)構(gòu)數(shù)據(jù)和機(jī)構(gòu)產(chǎn)生的混合數(shù)據(jù)，各行業(yè)積累的數(shù)據(jù)量越來越大，數(shù)據(jù)類型也越來越多、越來越復(fù)雜，已經(jīng)超越了傳統(tǒng)數(shù)據(jù)管理系統(tǒng)、處理模式的能力范圍，“大數(shù)據(jù)”也就應(yīng)運(yùn)而生了。大數(shù)據(jù)又稱巨量數(shù)據(jù)，指無法用常規(guī)軟件在特定時間范圍內(nèi)獲取、管理和處理的數(shù)據(jù)集合，是需要新處理模式才能適應(yīng)海量、高增長率和多樣化的信息資產(chǎn)。1.4.1大數(shù)據(jù)產(chǎn)生的背景42大數(shù)據(jù)的5V+1C的特征：（1）大量（Volume）：存儲數(shù)量巨大；（2）多樣（Variety）：數(shù)據(jù)來源及格式多樣化，包括格式化數(shù)據(jù)、半結(jié)構(gòu)化或非結(jié)構(gòu)化數(shù)據(jù)；（3）高速（Velocity）：數(shù)據(jù)增長速度快、處理速度快；（4）價值（Value）：在數(shù)據(jù)處理過程中挖掘數(shù)據(jù)潛在的價值；（5）準(zhǔn)確性（Veracity）：數(shù)據(jù)處理結(jié)果保證準(zhǔn)確性；（6）復(fù)雜（Complexity）：數(shù)據(jù)處理和分析難度大。1.4.2大數(shù)據(jù)的應(yīng)用場景43（1）醫(yī)療大數(shù)據(jù)的應(yīng)用（2）金融大數(shù)據(jù)的理財應(yīng)用（3）零售行業(yè)大數(shù)據(jù)的應(yīng)用（4）農(nóng)牧大數(shù)據(jù)量化生產(chǎn)（5）教育大數(shù)據(jù)因材施教（6）環(huán)境大數(shù)據(jù)對抗PM2.5（7）食品大數(shù)據(jù)的食品安全應(yīng)用（8）大數(shù)據(jù)在疫情中的應(yīng)用1.4.3大數(shù)據(jù)的關(guān)鍵技術(shù)44（1）大數(shù)據(jù)采集技術(shù)（2）大數(shù)據(jù)預(yù)處理技術(shù)（3）大數(shù)據(jù)存儲及管理技術(shù)（4）大數(shù)據(jù)處理技術(shù)（5）大數(shù)據(jù)分析及挖掘（6）大數(shù)據(jù)呈現(xiàn)技術(shù)第2章數(shù)據(jù)表示45鏈棧用單鏈表表示目錄462.1數(shù)值表示2.2二進(jìn)制數(shù)的運(yùn)算基礎(chǔ)2.3計算機(jī)中的編碼數(shù)值表示47計算機(jī)中的信息，都是用二進(jìn)制數(shù)代碼表示，但這些二進(jìn)制代碼有多種表現(xiàn)形式，如數(shù)值、字符、聲音、圖像與圖形數(shù)據(jù)等。2.1.1數(shù)制48

數(shù)制，也稱為“計數(shù)制”，是用一組固定的符號和統(tǒng)一的規(guī)則來表示數(shù)值的方法。

任何一個數(shù)制都包含兩個基本要素：基數(shù)和位權(quán)。

十進(jìn)制二進(jìn)制

八進(jìn)制

十六進(jìn)制2.1.1數(shù)制——十進(jìn)制49

數(shù)：用0、1、2、3、4、5、6、7、8、9這十個符號來描述。

基數(shù)：10。

計數(shù)規(guī)則：逢十進(jìn)一，處于不同位置上的數(shù)碼位權(quán)不同。從小數(shù)點(diǎn)向兩側(cè)數(shù)，整數(shù)部分第n位的數(shù)碼位權(quán)是10n-1,小數(shù)部分第m位的數(shù)碼位權(quán)是10-m。

2.1.1數(shù)制——二進(jìn)制50

數(shù)：用0、1這兩個符號來描述。

基數(shù)：2。

計數(shù)規(guī)則：逢二進(jìn)一，處于不同位置上的數(shù)碼位權(quán)不同。從小數(shù)點(diǎn)向兩側(cè)數(shù)，整數(shù)部分第n位的數(shù)碼位權(quán)是2n-1,小數(shù)部分第m位的數(shù)碼位權(quán)是2-m。

2.1.1數(shù)制——八進(jìn)制51

數(shù)：用0、1、2、3、4、5、6、7這八個符號來描述。

基數(shù)：8。

計數(shù)規(guī)則：逢八進(jìn)一，處于不同位置上的數(shù)碼位權(quán)不同。從小數(shù)點(diǎn)向兩側(cè)數(shù)，整數(shù)部分第n位的數(shù)碼位權(quán)是8n-1,小數(shù)部分第m位的數(shù)碼位權(quán)是8-m。

2.1.1數(shù)制——十六進(jìn)制52

數(shù)：用0、1、2、3、4、5、6、7、8、9、A、B、C、D、E、F這十六個符號來描述。

基數(shù)：16。

計數(shù)規(guī)則：逢十六進(jìn)一，處于不同位置上的數(shù)碼位權(quán)不同。從小數(shù)點(diǎn)向兩側(cè)數(shù)，整數(shù)部分第n位的數(shù)碼位權(quán)是16n-1,小數(shù)部分第m位的數(shù)碼位權(quán)是16-m。

2.1.2數(shù)制之間的轉(zhuǎn)換——十進(jìn)制與二進(jìn)制數(shù)相互轉(zhuǎn)換53（1）二進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)二進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)采用權(quán)相加法，即用位權(quán)表示法展開，而后進(jìn)行相加。

2.1.2數(shù)制之間的轉(zhuǎn)換——十進(jìn)制與二進(jìn)制數(shù)相互轉(zhuǎn)換54（2）十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)整數(shù)部分：除基數(shù)（2）取余法，直到商為0，然后將余數(shù)倒排得到的二進(jìn)制數(shù)。小數(shù)部分：乘基數(shù)（2）取整法，直到乘積的小數(shù)部分為0，或小數(shù)點(diǎn)后的位數(shù)達(dá)到了所需的精度，然后將積的整數(shù)部分順排得到的二進(jìn)制數(shù)。2.1.2數(shù)制之間的轉(zhuǎn)換——十進(jìn)制與二進(jìn)制數(shù)相互轉(zhuǎn)換55（2）十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)【例2.2】將十進(jìn)制數(shù)98.625轉(zhuǎn)換成二進(jìn)制數(shù)。十進(jìn)制數(shù)984920224121余數(shù)6312222210001低位高位整數(shù)部分0十進(jìn)制數(shù)0.625積的整數(shù)部分小數(shù)部分

21.2501

20.500.25

211.0低位高位所以，(98.625)10=(1100010.101)2

。2.1.2數(shù)制之間的轉(zhuǎn)換56二進(jìn)制數(shù)與八進(jìn)制、十六進(jìn)制數(shù)相互轉(zhuǎn)換因?yàn)?3=8,24=16，所以八進(jìn)制數(shù)的0-7八個數(shù)字可以用三位二進(jìn)制數(shù)表示，十六進(jìn)制數(shù)的0-15十六個數(shù)字可以用四位二進(jìn)制數(shù)表示。2.1.2數(shù)制之間的轉(zhuǎn)換——二進(jìn)制與八、十六進(jìn)制數(shù)相互轉(zhuǎn)換57（1）二進(jìn)制數(shù)轉(zhuǎn)換為八進(jìn)制數(shù)以小數(shù)點(diǎn)為基準(zhǔn)：整數(shù)部分：從右向左，每3位為一組，最左邊不足3位時，左邊加0補(bǔ)足3位。小數(shù)部分：從左向右，每3位為一組，最右邊不足3位時，右邊加0補(bǔ)足3位。

將以上每組中的3位二進(jìn)制數(shù)用1位八進(jìn)制數(shù)表示，依序排序即可得到對應(yīng)的八進(jìn)制數(shù)。2.1.2數(shù)制之間的轉(zhuǎn)換——二進(jìn)制與八、十六進(jìn)制數(shù)相互轉(zhuǎn)換58（1）二進(jìn)制數(shù)轉(zhuǎn)換為八進(jìn)制數(shù)【例2.3】將二進(jìn)制數(shù)1111011101.1011轉(zhuǎn)換為八進(jìn)制數(shù)。1111011101.1011=001111011101.101100=1735.54所以，(1111011101.1011)2=(1735.54)8。2.1.2數(shù)制之間的轉(zhuǎn)換——二進(jìn)制與八、十六進(jìn)制數(shù)相互轉(zhuǎn)換59（2）二進(jìn)制數(shù)轉(zhuǎn)換為十六進(jìn)制數(shù)以小數(shù)點(diǎn)為基準(zhǔn)：整數(shù)部分：從右向左，每4位為一組，最左邊不足4位時，左邊加0補(bǔ)足4位。小數(shù)部分：從左向右，每4位為一組，最右邊不足4位時，右邊加0補(bǔ)足4位。將以上每組中的4位進(jìn)二制數(shù)用1位十六進(jìn)制數(shù)表示，依序排序即可得到對應(yīng)的十六進(jìn)制數(shù)。2.1.2數(shù)制之間的轉(zhuǎn)換——二進(jìn)制與八、十六進(jìn)制數(shù)相互轉(zhuǎn)換60（2）二進(jìn)制數(shù)轉(zhuǎn)換為十六進(jìn)制數(shù)【例2.4】將二進(jìn)制數(shù)101100010111100.1110101轉(zhuǎn)換為十六進(jìn)制數(shù)。101100010111100.1110101=0101100010111100.11101010

=

5

8

B

C.EA所以，(101100010111100.1110101)2=(58BC.EA)16。2.1.2數(shù)制之間的轉(zhuǎn)換——二進(jìn)制與八、十六進(jìn)制數(shù)相互轉(zhuǎn)換61（3）八進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)將每位八進(jìn)制數(shù)用3位二進(jìn)制數(shù)替換，然后依序排列即可?！纠?.5】將八進(jìn)制數(shù)623.54轉(zhuǎn)換為二進(jìn)制數(shù)。

173.54=173.54=001111011.101100所以，(173.54)8=(1111011.1011)2。2.1.2數(shù)制之間的轉(zhuǎn)換——二進(jìn)制與八、十六進(jìn)制數(shù)相互轉(zhuǎn)換62（4）十六進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)將每位十六進(jìn)制數(shù)用4位二進(jìn)制數(shù)替換，然后依序排列即可。【例2.6】將十六進(jìn)制數(shù)7A9D.BC轉(zhuǎn)換為二進(jìn)制數(shù)。

7A9D.BC=7A

9D.BC

=0111101010011101.10111100所以，(7A9D.BC)16=(111101010011101.101111)2。提示：整數(shù)部分最前面的0和小數(shù)部分最后面的0均可以省略。2.2二進(jìn)制數(shù)的運(yùn)算基礎(chǔ)63計算機(jī)中的二進(jìn)制數(shù)基本運(yùn)算有兩類：算術(shù)運(yùn)算(ArithmeticOperation)：加、減、乘、除等四則運(yùn)算。邏輯運(yùn)算(LogicOperation)：包括邏輯與（邏輯乘）、邏輯或（邏輯加）、邏輯非及邏輯異或等運(yùn)算，它們都是按位進(jìn)行運(yùn)算的，也稱邏輯操作。2.2.1四則運(yùn)算64二進(jìn)制數(shù)的四則運(yùn)算加、減、乘、除運(yùn)算依據(jù)二進(jìn)制數(shù)的特點(diǎn)：只有兩個數(shù)字0、1；由低位到高位“逢二進(jìn)一”。加法：逢二進(jìn)一。減法：借一當(dāng)二。2.2.1四則運(yùn)算65加法：逢二進(jìn)一。0+0=0，0+1=1，1+0=1，1+1=10【例2.7】計算二進(jìn)制數(shù)的加法：1101+1011。1101+1011110002.2.1四則運(yùn)算66減法：向高位借一當(dāng)二。1-1=0，1-0=1，0-0=0，0-1=1【例2.8】計算二進(jìn)制數(shù)的減法：1101-1011。1101-101100102.2.1四則運(yùn)算67

1001

100100001001010110102.2.1四則運(yùn)算68

10011011000011011011111010商余數(shù)2.2.1四則運(yùn)算69從上述例2.9和例2.10看出：二進(jìn)制數(shù)乘法的結(jié)果可以通過逐次左移后的被乘數(shù)（或0）相加而獲得。即，乘法可以由“加法”和“移位”兩種操作實(shí)現(xiàn)。除法可以由“減法”和“移位”兩種操作實(shí)現(xiàn)。在計算機(jī)中，就是利用這一原理實(shí)現(xiàn)二進(jìn)制數(shù)乘法和除法，即在運(yùn)算器中只需進(jìn)行加、減法及左、右移位操作便可實(shí)現(xiàn)四則運(yùn)算。2.2.2邏輯運(yùn)算70邏輯是指條件與結(jié)論之間的關(guān)系，因此邏輯運(yùn)算是指對因果關(guān)系進(jìn)行分析的一種運(yùn)算。邏輯運(yùn)算的結(jié)果并不表示數(shù)值大小，而是表示一種邏輯概念，若成立用真或1表示；若不成立用假或0表示。常用的邏輯運(yùn)算有“或”運(yùn)算（邏輯加）、“與”運(yùn)算（邏輯乘）、“非”運(yùn)算（邏輯非）及“異或”運(yùn)算（邏輯異或）等。2.2.2邏輯運(yùn)算71“與”運(yùn)算

2.2.2邏輯運(yùn)算72“與”運(yùn)算邏輯“與”的功能：僅當(dāng)邏輯變量x與y的值均為1時，運(yùn)算結(jié)果f為1，即兩個邏輯變量的取值都為“真”時，結(jié)果才為“真”；兩個邏輯變量中只要有一個為“0”，邏輯“與”的運(yùn)算結(jié)果為0（邏輯“假”）。2.2.2邏輯運(yùn)算73“與”運(yùn)算

X=10001111B

F=00000110B

2.2.2邏輯運(yùn)算74“或”運(yùn)算

2.2.2邏輯運(yùn)算75“或”運(yùn)算邏輯“或”的功能：當(dāng)邏輯變量x或y中至少有一個為1時，運(yùn)算結(jié)果f為1，即只要有一個條件為“真”或兩個為“真”，結(jié)果就為“真”。僅當(dāng)兩個邏輯變量均為0時，運(yùn)算結(jié)果才為0。2.2.2邏輯運(yùn)算76“或”運(yùn)算

X=10000111B

F=11010111B2.2.2邏輯運(yùn)算77“非”運(yùn)算若條件與結(jié)果相反，當(dāng)條件滿足時結(jié)果不成立，條件不滿足時結(jié)果成立，那么結(jié)果與條件之間的關(guān)系成為“非”?！胺恰保∟OT）運(yùn)算的規(guī)則如下：

=10=01式中，“-”是“非”運(yùn)算符號。設(shè)x和y為邏輯變量，f表示邏輯運(yùn)算結(jié)果，則邏輯“非”的運(yùn)算表示為：f=xf=y2.2.2邏輯運(yùn)算78“非”運(yùn)算邏輯“非”的功能：當(dāng)邏輯變量為1時，其運(yùn)算結(jié)果為0；而當(dāng)邏輯變量為0時，其運(yùn)算結(jié)果為1?！纠?.13】設(shè)X=0FH,求XF=X=00001111BF==11110000BX所以，=F0HX2.2.2邏輯運(yùn)算79“異或”運(yùn)算如果決定一件事有兩個條件，當(dāng)只有一個條件滿足時就可行，兩個條件都滿足或兩個條件都不滿足時不可行，那么結(jié)果與各條件的關(guān)系成為“異或”?！爱惢颉保‥OR：ExclusiveOR）運(yùn)算的規(guī)則如下：

0⊕0=01⊕0=1 0⊕1=1 1⊕1=0

式中，“⊕”是“異或”運(yùn)算符號。設(shè)x和y為邏輯變量，f表示邏輯運(yùn)算結(jié)果，則邏輯“異或”的運(yùn)算表示為：f=x⊕y2.2.2邏輯運(yùn)算80“異或”運(yùn)算邏輯“異或”的功能：兩個邏輯變量x和y的取值相同，運(yùn)算結(jié)果則為0；x與y的取值不同（一個為1，另一個為0）時，運(yùn)算結(jié)果為1。這個功能可簡記為“相同為0，不同為1”?！纠?.14】設(shè)X=0FH,Y=55H,求F=X⊕Y。所以，F(xiàn)=X⊕Y=0FH⊕55H=5AH。X=00001111B⊕Y=01010101BF=01011010B2.3計算機(jī)中的編碼812.3.1

字符數(shù)據(jù)2.3.2音頻數(shù)據(jù)2.3.3圖像和圖形數(shù)據(jù)2.3.4視頻數(shù)據(jù)2.3計算機(jī)中的編碼82所謂編碼（Code），就是用按一定規(guī)則組合而成的若干位二進(jìn)制代碼來表示數(shù)值數(shù)據(jù)，它是計算機(jī)中所采用的按“形”表示數(shù)的一種方法。計算機(jī)中常用的編碼有十進(jìn)制編碼、可靠性編碼。不同的編碼，其編碼規(guī)則不同，具有不同的特性及應(yīng)用場合。2.3計算機(jī)中的編碼83十進(jìn)制編碼:十進(jìn)制編碼是指用若干位二進(jìn)制代碼來表示一位十進(jìn)制數(shù)，也稱BCD（BinaryCodedDecimal）碼。BCD碼可分為多種，其中最常用的是8421碼，它用4位權(quán)為8421的二進(jìn)制數(shù)來表示等值的一位十進(jìn)制數(shù)，其編碼規(guī)則如表2.2所示。按表中給定的規(guī)則，很容易實(shí)現(xiàn)十進(jìn)制數(shù)與8421碼之間的轉(zhuǎn)換。2.3計算機(jī)中的編碼84【例2.15】(651)10=(?)8421

(651)10=(011001010001)8421【例2.16】(1101.01)2=(?)8421

(1101.01)2=(13.25)10=(00010011.00100101)84212.3計算機(jī)中的編碼85可靠性編碼:在計算機(jī)中進(jìn)行數(shù)據(jù)傳輸或存取時，免不了要出錯。為了能及時發(fā)現(xiàn)錯誤，并及時檢測與校正錯誤，采用了可靠性編碼。常用的可靠性編碼有格雷碼（GrayCode）、奇偶校驗(yàn)碼（OddevenCheckCode）、海明碼（HammingCode）和循環(huán)冗余碼（CRC）等。2.3.1字符數(shù)據(jù)86計算機(jī)中采用的字符主要有西文、中文及控制符號；它們都以二進(jìn)制編碼方式存入計算機(jī)并得以處理，這種以字母和符號進(jìn)行編碼的二進(jìn)制代碼成為字符代碼（CharacterCode）。2.3.1字符數(shù)據(jù)87西文字符在計算機(jī)中常用的西文字符編碼有ASCII碼（美國標(biāo)準(zhǔn)信息交換代碼）和EBCDIC碼（擴(kuò)展的BCD交換代碼）。為書寫方便，常把ASCII碼的7位二進(jìn)制代碼寫成兩位十六進(jìn)制數(shù)，例如“A”的ASCII碼是41H，“a”的ASCII碼是61H，“0”的ASCII碼是30H。2.3.1字符數(shù)據(jù)882.中文字符漢字編碼（Chinesecharacterencoding）是為漢字設(shè)計的一種便于輸入計算機(jī)的代碼。漢字信息處理系統(tǒng)一般包括編碼、輸入、存儲、編輯、輸出和傳輸。計算機(jī)中漢字的表示也是用二進(jìn)制編碼。根據(jù)應(yīng)用目的的不同，漢字編碼分為外碼、交換碼、機(jī)內(nèi)碼和字形碼。2.3.1字符數(shù)據(jù)——中文字符89（1）外碼（輸入碼）外碼也叫輸入碼，是用來將漢字輸入到計算機(jī)中的一組鍵盤符號。常用的輸入碼有拼音碼、五筆字型碼、自然碼、表形碼、認(rèn)知碼、區(qū)位碼和電報碼等。一種好的編碼應(yīng)有編碼規(guī)則簡單、易學(xué)好記、操作方便、重碼率低、輸入速度快等優(yōu)點(diǎn)，每個人可根據(jù)自己的需要進(jìn)行選擇。2.3.1字符數(shù)據(jù)——中文字符90（2）交換碼（國際碼）計算機(jī)內(nèi)部處理的信息，都是用二進(jìn)制代碼表示的，漢字也不例外。而二進(jìn)制代碼使用起來是不方便的，于是需要采用信息交換碼，將輸入的漢字轉(zhuǎn)換為機(jī)內(nèi)代碼，以實(shí)現(xiàn)漢字在計算機(jī)內(nèi)的存儲與處理。中國標(biāo)準(zhǔn)總局1981年制定了中華人民共和國國家標(biāo)準(zhǔn)GB2312--80《信息交換用漢字編碼字符集--基本集》，即國標(biāo)碼。2.3.1字符數(shù)據(jù)——中文字符91（3）機(jī)內(nèi)碼根據(jù)國標(biāo)碼的規(guī)定，每一個漢字都有了確定的二進(jìn)制代碼，在微機(jī)內(nèi)部漢字代碼都用機(jī)內(nèi)碼，在磁盤上記錄漢字代碼也使用機(jī)內(nèi)碼。（4）漢字的字形碼

2.3.1字符數(shù)據(jù)——中文字符92（5）漢字地址碼漢字地址碼是指漢字庫中存儲漢字字形信息的邏輯地址碼。它與漢字內(nèi)碼有著簡單的對應(yīng)關(guān)系，以簡化內(nèi)碼到地址碼的轉(zhuǎn)換。2.3.2音頻數(shù)據(jù)93聲音是一種連續(xù)的隨時間變化的波，即聲波。用連續(xù)波形表示的聲音的信息，稱為模擬信息，或模擬信號。模擬信號主要由振幅和頻率來描述，振幅大小反映聲音的音量大小，頻率的大小反映聲音的音調(diào)高低。數(shù)字化的聲音數(shù)據(jù)就是音頻數(shù)據(jù)。2.3.2音頻數(shù)據(jù)94聲音在計算機(jī)內(nèi)表示時需要把聲波數(shù)字化，又稱量化。量化的過程實(shí)際上就是以一定的頻率（固定的時間間隔）。對連續(xù)的模擬聲音信號進(jìn)行模數(shù)轉(zhuǎn)換(ADC)得到音頻數(shù)據(jù)的過程。數(shù)字化聲音的播放就是將音頻數(shù)據(jù)進(jìn)行數(shù)模轉(zhuǎn)換(DAC)變成模擬聲音信號輸出。2.3.2音頻數(shù)據(jù)95量化的質(zhì)量與采樣頻率(SamplingRate)、采樣大小(SamplingSize)及聲道數(shù)有關(guān)。采樣頻率即單位時間內(nèi)的采樣次數(shù),采樣頻率越大,采樣點(diǎn)之間的間隔越小,數(shù)字化得到的聲音就越逼真,但相應(yīng)的數(shù)據(jù)量增大,處理起來就越困難。采樣大小即記錄每次樣本值大小的數(shù)值的位數(shù),它決定采樣的動態(tài)變化范圍,位數(shù)越多,所能記錄聲音的變化程度就越細(xì)膩,所得的數(shù)據(jù)量也越大。常見的CD，采樣率為44.1kHz。2.3.2音頻數(shù)據(jù)96

2.3.3圖像和圖形數(shù)據(jù)97在計算機(jī)中，圖像和圖形是兩個完全不同的概念。圖像是由真實(shí)的場景或現(xiàn)實(shí)存在的圖片輸入計算機(jī)產(chǎn)生的，圖像以位圖形式存儲。圖形一般是指通過計算機(jī)繪制工具繪制的由直線、圓、圓弧、任意曲線等組成的畫面，即圖形是由計算機(jī)產(chǎn)生的，且以矢量形式存儲。2.3.3圖像和圖形數(shù)據(jù)981.顏色表示法在計算機(jī)中，顏色通常用RGB（red-green-blue）值表示。RGB值是三個數(shù)字，每個數(shù)字用0到255的數(shù)字表示一種元素的份額，0表示這種顏色沒有參與，255表示它完全參與其中。例如，RGB值（255，255，0）最大化了紅色和綠色的份額，最小化了藍(lán)色的份額，結(jié)果生成的是嫩黃色。2.3.3圖像和圖形數(shù)據(jù)992.數(shù)字化圖像和圖形——位圖圖像位圖圖像（bitmap），亦稱為點(diǎn)陣圖像或柵格圖像，是由稱作像素（Pixels，圖片元素）的單個點(diǎn)組成的。用數(shù)碼相機(jī)拍攝的照片、掃描儀掃描的圖片以及計算機(jī)截屏圖等都屬于位圖。位圖的特點(diǎn)是可以表現(xiàn)色彩的變化和顏色的細(xì)微過渡，產(chǎn)生逼真的效果，缺點(diǎn)是在保存時需要記錄每一個像素的位置和顏色值，占用較大的存儲空間。2.3.3圖像和圖形數(shù)據(jù)1002.數(shù)字化圖像和圖形——位圖圖像一幅圖像可認(rèn)為是由若干行和若干列的像素組成的陣列，每個像素點(diǎn)用若干二進(jìn)制位進(jìn)行編碼，表示圖像的顏色，這就是圖像的數(shù)字化。描述圖像的主要屬性是圖像分辨率和顏色深度。圖像分辨率是指圖像的水平方向和垂直方向的像素個數(shù)。顏色深度是指每一個像素點(diǎn)表示顏色的二進(jìn)制位數(shù)。如單色圖像的顏色深度為1，而256色圖像的顏色深度為8，真彩色圖像的顏色深度為24。2.3.3圖像和圖形數(shù)據(jù)1012.數(shù)字化圖像和圖形——位圖圖像

2.3.3圖像和圖形數(shù)據(jù)1022.數(shù)字化圖像和圖形——矢量圖形矢量圖形是由一串可重構(gòu)圖形的指令構(gòu)成。在創(chuàng)建矢量圖片的時候，可以用不同的顏色來畫線和圖形。然后計算機(jī)用這一串線條和圖形轉(zhuǎn)換為能重構(gòu)圖形的指令。計算機(jī)只存儲這些指令，而不是真正的圖形，所以矢量圖形看起來沒有位圖圖像真實(shí)。矢量圖形文件的擴(kuò)展名為.wmf，.dxf，.mgx和.cgm。2.3.3圖像和圖形數(shù)據(jù)1032.數(shù)字化圖像和圖形矢量圖形與位圖圖像相比，有以下優(yōu)點(diǎn)：矢量圖形占用的存儲空間小。使用矢量圖形軟件，可以方便地修改圖形?？梢园咽噶繄D形的一部分當(dāng)做一個獨(dú)立的對象，單獨(dú)地加以拉伸、縮小、移動和刪除。2.3.4視頻數(shù)據(jù)104視頻數(shù)據(jù)是指連續(xù)的圖像序列，其實(shí)質(zhì)是由一組組連續(xù)的圖像構(gòu)成的，而對于圖像本身而言，除了其出現(xiàn)的先后順序而外，沒有任何結(jié)構(gòu)信息。視頻數(shù)據(jù)可用故事單元、場景、鏡頭、幀來描述。2.3.4視頻數(shù)據(jù)105計算機(jī)中的視頻數(shù)據(jù)一般分為兩類：①

動畫。其每一幅畫面都是通過一些工具軟件對圖像素材進(jìn)行編輯制作而成。它是用人工合成的方法對真實(shí)世界的一種模擬。②

視頻。對視頻信號源（如電視機(jī)、攝像機(jī)等）經(jīng)過采樣和量化處理后保存下來的信息。視頻影像是對真實(shí)世界的記錄。2.3.4視頻數(shù)據(jù)106視頻的數(shù)字化是指在一段時間內(nèi)，以一定的速度對視頻信號進(jìn)行捕獲，并加以采樣后形成數(shù)字化數(shù)據(jù)的處理過程。視頻是由一系列的幀組成，每幀是一幅靜止的圖像，可用位圖文件形式表示。視頻每秒中至少顯示30幀，所以視頻需要非常大的存儲空間。視頻文件的擴(kuò)展名為.avi，.mpg等。第3章計算思維107鏈棧用單鏈表表示目錄1083.13.23.33.43.5計算思維的概念計算思維的應(yīng)用領(lǐng)域計算思維的特點(diǎn)程序算法3.1計算思維的概念109什么是思維？思維（Thinking）是人腦對客觀事物的一種概括的、間接的反映，它反映客觀事物的本質(zhì)和規(guī)律。思維特征能動性能認(rèn)識和反映客觀世界，還能對客觀世界進(jìn)行改造。間接性非直接的、以其他事物作媒介來反映客觀事物概括性在人的感性基礎(chǔ)上，將一類事物的共同、本質(zhì)的特征和規(guī)律抽取出來，加以概括。3.1計算思維概念3.1計算思維概念實(shí)驗(yàn)思維理論思維思維計算思維日常思維科學(xué)思維3.1計算思維概念112什么是計算思維(ComputationalThinking)

計算思維是運(yùn)用計算機(jī)科學(xué)的基礎(chǔ)概念進(jìn)行問題求解、系統(tǒng)設(shè)計、以及人類行為理解等涵蓋計算機(jī)科學(xué)之廣度的一系列思維活動。----周以真3.1計算思維概念113計算機(jī)思維可以劃分為四個主要組成部分把問題進(jìn)行拆分，同時理清各個部分的屬性找出拆分后問題各部分之間的異同探尋形成這些模式背后的一般規(guī)律針對相似問題提供逐步的解決辦法解構(gòu)模式識別抽象化算法設(shè)計視頻1

視頻23.2計算思維的應(yīng)用領(lǐng)域114生物學(xué)化學(xué)藝術(shù)工程學(xué)腦科學(xué)經(jīng)濟(jì)學(xué)3.3計算思維的特點(diǎn)115概念化的抽象思維，而非程序思維。是一種基本技能。是人的思維，而非機(jī)器的思維。與數(shù)學(xué)和工程思維互補(bǔ)和融合。面向所有人、所有領(lǐng)域。計算思維特點(diǎn)是思想,而非人造品。3.4算法116算法設(shè)計是計算思維的關(guān)鍵組成部分之一算法（Algorithm）是指解題方案的準(zhǔn)確而完整的描述，是一系列解決問題的清晰指令，算法代表著用系統(tǒng)的方法描述解決問題的策略機(jī)制。3.4算法117算法特征01算法要素02算法流程圖03常用算法043.4.1算法特征118可行性(Effectiveness)算法中執(zhí)行的任何計算步驟都可以被分解為基本的可執(zhí)行的操作步驟，即每個計算步驟都可以在有限時間內(nèi)完成（也稱有效性）確切性(Definiteness)算法的每一步驟必須有確切的定義輸出項(xiàng)(Output)一個算法有一個或多個輸出，以反映對輸入數(shù)據(jù)加工后的結(jié)果有窮性(Finiteness)算法必須能在執(zhí)行有限個步驟之后終止輸入項(xiàng)(Input)一個算法有0個或多個輸入，以刻畫運(yùn)算對象的初始情況3.4.2算法要素11921數(shù)據(jù)對象的運(yùn)算和操作一個算法的功能結(jié)構(gòu)不僅取決于所選用的操作，而且還與各操作之間的執(zhí)行順序有關(guān)算法的控制結(jié)構(gòu)算術(shù)運(yùn)算：加、減、乘、除等邏輯運(yùn)算：與、或、非等關(guān)系運(yùn)算：大于、小于、等于、不等于等數(shù)據(jù)傳輸：輸入、輸出、賦值等3.4.3算法流程圖120流程圖是用一些圖框來表示各種類型的操作，在框內(nèi)寫出各個步驟，然后用帶箭頭的線把它們連接起來，以表示執(zhí)行的先后順序。3.4.3算法流程圖121處理框表示一般的處理功能判斷框?qū)σ粋€給定的條件進(jìn)行判斷，根據(jù)給定的條件是否成立決定如何執(zhí)行其后的操作。有一個入口，二個出口輸入輸出框表示數(shù)據(jù)的輸入輸出起止框表示流程開始或結(jié)束流程線表示流程的路徑和方向3.4.3算法流程圖12202選擇結(jié)構(gòu)01順序結(jié)構(gòu)03循環(huán)結(jié)構(gòu)算法的三種基本結(jié)構(gòu)順序結(jié)構(gòu)開始a=2,b=3;c=a+b輸出c的值結(jié)束求a+b和的流程圖順序結(jié)構(gòu)流程圖AB124根據(jù)判斷框中給定的條件P是否成立而選擇執(zhí)行A和B，條件P可以是“x>0”或“x>y”等。無論P(yáng)條件是否成立，只能執(zhí)行A或B之一，不可能既執(zhí)行A又執(zhí)行B。無論走哪一條路徑，在執(zhí)行完A或B之后將脫離選擇結(jié)構(gòu)。A或B兩個框中可以有一個是空的，即不執(zhí)行任何操作。選擇結(jié)構(gòu)P不成立AB成立選擇結(jié)構(gòu)流程圖125輸入變量a,b的值，輸出其中的較大的值開始輸入a，b的值a>=b?輸出a的值輸出b的值結(jié)束

輸出較大值的流程圖126循環(huán)結(jié)構(gòu)當(dāng)型循環(huán)流程圖直到型循環(huán)流程圖假真127在屏幕上輸出10次“hello”i<=10?用來判斷是否達(dá)到輸出次數(shù)10次？不成立開始設(shè)置一個用來記錄輸出次數(shù)的變量i，第一次輸出，i=1輸出“hello”i=i+1，準(zhǔn)備開始下一次輸出結(jié)束成立當(dāng)型循環(huán)流程圖128在屏幕上輸出10次“hello”成立不成立開始設(shè)置一個用來記錄輸出次數(shù)的變量i，第一次輸出，i=1輸出“hello”i=i+1，準(zhǔn)備開始下一次輸出i<=10?用來判斷是否達(dá)到輸出次數(shù)10次？結(jié)束直到型循環(huán)流程圖3.4.4常用算法129單擊此處添加標(biāo)題單擊此處添加標(biāo)題A數(shù)據(jù)交換B最大值最小值C累加累乘D求數(shù)據(jù)每位上的值E求素數(shù)EF排序F3.4.4常用算法130數(shù)據(jù)交換假設(shè)有兩個變量a=9,b=14,想交換變量a和b的值，使得a=14,b=9。9a14bc3.4.4常用算法131數(shù)據(jù)交換假設(shè)有兩個變量a=9,b=14,想交換變量a和b的值，使得a=14,b=9。abc914開始a=9b=14c=aa=bb=c輸出a，b的值結(jié)束132求最大值、最小值求兩個數(shù)a,b的最大值求三個及以上數(shù)的最大值假設(shè)第一個數(shù)為最大值max，其余數(shù)據(jù)和最大值進(jìn)行比較，若大于max，修改max值為較大的數(shù)。3.4.4常用算法3.4.4常用算法最大值算法流程圖否是開始輸入第一個數(shù)amax=a//假設(shè)第一個數(shù)a為最大值max再輸入一個數(shù)，依然用a表示a>max?判斷新輸入的數(shù)是否大于maxmax=a//將新輸入的數(shù)作為最大值max133求10個數(shù)最大值的算法流程圖3.4.4常用算法否是開始輸入第一個數(shù)amax=a，i=1再輸入一個數(shù)，依然用a表示a>max?max=a否i<=10?i=i+1結(jié)束是最小值？134a累加器累加、累乘3.4.4常用算法0b累加值求1到10的累加和1a=a+b123364105156217288369451055是否開始a=0b=1

b<=10?a=a+bb=b+1結(jié)束輸出a的值1到10累加和算法流程圖累乘積？135求數(shù)據(jù)每位上的值3.4.4常用算法A除減法B除余法1362343.4.4常用算法除減法2該數(shù)減去a*100，除以10，得到十位b。3該數(shù)減去a*100和b*10即得個位c。1該數(shù)除以100，得到百位a。十位數(shù)？不知道位數(shù)？1371383.4.4常用算法除減法流程圖c=x-a*100-b*10（c=4）

開始x=234a=x/100(a=2)

x=x-a*100(x=34)b=x/10(b=3)輸出a，b,c的值結(jié)束2343.4.4常用算法除余法2重復(fù)①得到十位b。3繼續(xù)重復(fù)①得到百位a。1該數(shù)除以10取余數(shù)得到個位c，將該數(shù)除以10，用得到的商代替該數(shù)。十位數(shù)？不知道位數(shù)？1391403.4.4常用算法x=x/10開始x=0?是否結(jié)束輸出a的值x=234

a=x%10除余法算法流程圖141素數(shù)（質(zhì)數(shù)）3.4.4常用算法把m被2到m-1之間的每一個整數(shù)去除，如果都不能被整除，那么m就是一個素數(shù)。

否判斷素數(shù)算法流程圖開始m%i=0?是結(jié)束輸出m不是素數(shù)i=i+1

i=2

輸入mi<=sqrt(m)?否是輸出m是素數(shù)3.4.4常用算法142AB把較小的數(shù)據(jù)往前調(diào)或者把較大的數(shù)據(jù)往后調(diào)兩兩比較相鄰記錄，如果反序則交換，直到?jīng)]有反序的記錄為止。冒泡排序穩(wěn)定排序49、38、65、97、76、13、27、49*3.4.4常用算法143AB為每一個位置選擇適當(dāng)?shù)脑孛看螐臒o序序列中選取最小元素放到有序序列的后面冒泡排序不穩(wěn)定排序49、38、65、97、76、13、27、49*3.4.4常用算法144試著繪制冒泡排序和選擇排序算法的流程圖課后練習(xí)一個算法在計算機(jī)上運(yùn)行所花費(fèi)的時間一個算法在計算機(jī)上運(yùn)行所花費(fèi)的空間時間復(fù)雜性空間復(fù)雜性3.3.6算法分析1453.5程序146計算機(jī)程序（ComputerProgram）是指一組指示計算機(jī)或其他具有信息處理能力裝置每一步動作的指令，通常用某種程序設(shè)計語言編寫，運(yùn)行于某種目標(biāo)體系結(jié)構(gòu)上。程序設(shè)計語言是用于書寫計算機(jī)程序的語言。3.5程序147第一代第二代第三代機(jī)器語言由二進(jìn)制0、1代碼指令構(gòu)成，不同的CPU具有不同的指令系統(tǒng)。高級語言面向用戶的、基本上獨(dú)立于計算機(jī)種類和結(jié)構(gòu)的語言。匯編語言匯編語言指令是機(jī)器指令的符號化程序設(shè)計語言可以分為三代148計算機(jī)程序開發(fā)是周而復(fù)始的，需要經(jīng)歷編寫新代碼、測試、分析，從事這種事件的工作人員叫做程序員。程序員第4章

計算機(jī)系統(tǒng)149鏈棧用單鏈表表示目錄1504.1ABCD4.24.44.3計算機(jī)系統(tǒng)的組成計算機(jī)軟件系統(tǒng)計算機(jī)硬件系統(tǒng)計算機(jī)體系結(jié)構(gòu)及其工作原理4.1計算機(jī)體系結(jié)構(gòu)及其工作原理1511524.1計算機(jī)體系結(jié)構(gòu)及其工作原理計算機(jī)處理的數(shù)據(jù)和指令一律用二進(jìn)制數(shù)表示01存儲程序02計算機(jī)硬件由運(yùn)算器、控制器、存儲器、輸入設(shè)備和輸出設(shè)備五大部分組成03馮·諾伊曼結(jié)構(gòu)的特點(diǎn)4.1計算機(jī)體系結(jié)構(gòu)及其工作原理153馮·諾伊曼結(jié)構(gòu)計算機(jī)的工作原理從計算機(jī)主存中讀出指令并送到計算機(jī)的控制器，控制器根據(jù)當(dāng)前指令的功能，控制全機(jī)執(zhí)行指令規(guī)定的操作，完成指令的功能。重復(fù)這一操作，直到程序中指令執(zhí)行完畢。程序控制將解題的步驟編成程序（通常由若干指令組成），并把程序存放在計算機(jī)的主存儲器中。存儲程序4.1計算機(jī)體系結(jié)構(gòu)及其工作原理154A指令是指示計算機(jī)執(zhí)行某種操作的命令，它由一串二進(jìn)制數(shù)碼組成。B一條指令通常由兩個部分組成：操作碼+地址碼什么是指令4.1計算機(jī)體系結(jié)構(gòu)及其工作原理155A指令系統(tǒng)是指一臺計算機(jī)所能執(zhí)行的全部指令的集合。B指令系統(tǒng)決定了一臺計算機(jī)硬件的主要性能和基本功能。什么是指令系統(tǒng)威脅網(wǎng)絡(luò)安全主要因素4.2計算機(jī)系統(tǒng)的組成156157計算機(jī)硬件系統(tǒng)是指構(gòu)成計算機(jī)的物理設(shè)備，即由機(jī)械、光、電、磁器件構(gòu)成的具有計算、控制、存儲、輸入和輸出功能的實(shí)體部件。4.3計算機(jī)硬件系統(tǒng)158計算機(jī)硬件系統(tǒng)是指構(gòu)成計算機(jī)的物理設(shè)備，即由機(jī)械、光、電、磁器件構(gòu)成的具有計算、控制、存儲、輸入和輸出功能的實(shí)體部件。4.3計算機(jī)硬件系統(tǒng)硬件系統(tǒng)中央處理器存儲器輸入輸出控制系統(tǒng)外部設(shè)備1594.3計算機(jī)硬件系統(tǒng)中央處理器01存儲器02輸入設(shè)備03輸出設(shè)備04總線05計算機(jī)的性能指標(biāo)061604.3.1中央處理器(CPU)CPU由控制器、運(yùn)算器和存儲器組成，通常集中在一塊芯片上，是計算機(jī)系統(tǒng)的核心設(shè)備。微型計算機(jī)的中央處理器又稱為微處理器。1614.3.1中央處理器(CPU)中央處理器主要包括兩部分0102控制器對輸入的指令進(jìn)行分析，并統(tǒng)一控制計算機(jī)的各個部件完成一定任務(wù)的部件。指揮計算機(jī)的各個部件按照指令的功能要求協(xié)調(diào)工作的部件，是計算機(jī)的神經(jīng)中樞和指揮中心，對協(xié)調(diào)整個電腦有序工作極為重要。運(yùn)算器主要任務(wù)是執(zhí)行各種算術(shù)運(yùn)算和邏輯運(yùn)算。1624.3.1中央處理器(CPU)影響CPU性能的主要指標(biāo)表示CPU的運(yùn)算速度，單位是MHz。主頻在單位時間內(nèi)能一次處理的二進(jìn)制數(shù)的位數(shù)。字長是指可以進(jìn)行高速數(shù)據(jù)交換的存儲器，它位于CPU與內(nèi)存之間，是一個讀寫速度比內(nèi)存更快的存儲器。緩存1634.3.2存儲器存儲器主存儲器(主存或內(nèi)存)輔助存儲器(輔存或外存)存儲器是用來存儲程序和各種數(shù)據(jù)信息的記憶部件。1644.3.2存儲器存儲器的性能指標(biāo)1存儲器所能容納的二進(jìn)制信息量的總和。存儲容量2計算機(jī)從存儲器讀出數(shù)據(jù)或?qū)懭霐?shù)據(jù)所需要的時間，表明了存儲器存取速度的快慢。存取周期位A字節(jié)BKB1KB=1024B=210BMB1MB=1024KB=220BGB1GB=1024MB=230BTB1TB=1024GB=240BPB1PB=1024TB=250B1654.3.2存儲器主存直接與CPU連接，用于存放當(dāng)前正在運(yùn)行的程序和數(shù)據(jù)，訪問速度快。主存儲器主存中存儲信息的載體稱為存儲體。存儲體被分為若干個單元。0101011101011000每個單元能夠存放一串二進(jìn)制碼表示的信息，該信息的總位數(shù)稱為一個存儲單元的字長。0X000000000X000000010XFFFFFFFF......指示每個單元的二進(jìn)制編碼稱為地址碼。存儲單元的地址碼只有一個，固定不變，而存儲在其中的信息是可以更換的。00000000000000001664.3.2存儲器01010111010110000X000000000X000000010XFFFFFFFF......主存的工作方式是按存儲單元的地址存放或讀取各類信息存放信息稱為“寫”讀取信息稱為“讀”“讀”和“寫”統(tǒng)稱訪問存儲器。

1674.3.2存儲器常用的微型計算機(jī)的存儲器有磁芯存儲器和半導(dǎo)體存儲器目前微型計算機(jī)的主存都采用半導(dǎo)體存儲器可讀、可寫易失性存儲器1隨機(jī)存儲器（RAM）可讀、不可寫非易失性存儲器2只讀存儲器（ROM）1684.3.2存儲器COMS電腦主板上的一塊可讀寫的RAM芯片，保存計算機(jī)系統(tǒng)配置信息。只需要極少電量就能存放數(shù)據(jù)由集成到主板上的一個小電池供電關(guān)機(jī)后信息不丟失1694.3.2存儲器高速緩沖存儲器(Cache)存取速度比一般RAM快的一種RAM，位于主存與CPU之間，容量小，速度快。當(dāng)中央處理器存取主存儲器某一單元時，自動將包括該單元在內(nèi)的那一組單元內(nèi)容調(diào)入高速緩沖存儲器1704.3.2存儲器通過主存與CPU間接連接，存放計算機(jī)暫時不需要使用的程序和數(shù)據(jù)。輔助存儲器非易失性存儲器容量大、價格低，存取速度慢硬盤光盤U盤最常用安裝的軟件1714.3.2存儲器根據(jù)存儲原理不同分類1利用磁記錄技術(shù)存儲數(shù)據(jù)的存儲器磁存儲器3通過存儲芯片內(nèi)部晶體管的開關(guān)狀態(tài)來存儲數(shù)據(jù)的固態(tài)存儲器2利用光學(xué)存儲技術(shù)存儲數(shù)據(jù)的存儲器光存儲器1724.3.2存儲器----磁存儲器A計算機(jī)主要的存儲介質(zhì)，可以存儲大量的二進(jìn)制數(shù)據(jù)，并且斷電后也能保持?jǐn)?shù)據(jù)不丟失。磁存儲器（disk）軟盤硬盤1734.3.2存儲器----磁存儲器磁存儲器是用某些磁性材料涂在金屬鋁片或塑料片的表面上作為載磁體來存儲信息的存儲器。涂覆在載體表面的磁性材料具有兩種不同的磁化狀態(tài)，分別表示二進(jìn)制信息的“0”和“1”。174磁存儲器的讀寫過程4.3.2存儲器----磁存儲器利用磁頭（讀寫頭）來形成和判別磁層中的不同磁化狀態(tài)磁頭是由軟磁材料做鐵芯繞有讀寫線圈的電磁鐵寫操作讀操作1754.3.2存儲器----硬盤硬盤是計算機(jī)系統(tǒng)中最主要的外存設(shè)備盤片一般由鋁合金制成，其表面涂有一層可被磁化的硬磁特性材料磁頭是用于向磁盤讀寫信息的工具，從0開始順序編號1764.3.2存儲器----硬盤磁盤上的一圈圈的圓周被稱之為磁道每圈磁道上的扇形小區(qū)域被稱為扇區(qū)扇區(qū)中有很多存儲單元用于存儲比特信息不同盤面上的每圈磁道所組成的柱形區(qū)域叫做柱面一面磁盤上的磁道數(shù)＝柱面數(shù)磁道的編號是從外到內(nèi)，從0開始編號，即最外面的一圈為第0磁道扇區(qū)的編號方式為固定標(biāo)記某塊為1號，然后順時針編號1774.3.2存儲器----硬盤優(yōu)點(diǎn)體積小重量輕可靠性高存取速度快防塵性好存儲容量大1不便于攜帶2價格昂貴缺點(diǎn)1784.3.2存儲器----光存儲器光盤的分類不可擦寫CD-ROMDVD-ROM可擦寫CD-RWDVD-RAM印刷層保護(hù)層反射層記錄層基板1794.3.2存儲器----光存儲器1804.3.2存儲器----固態(tài)存儲器181U盤的優(yōu)點(diǎn)4.3.2存儲器----U盤01小巧02速度快03容量大182U盤的組成機(jī)芯主控芯片、晶振、電容貼片電阻、USB接口貼片LED（不是所有的U盤都有）FLASH（閃存）芯片外殼4.3.2存儲器----U盤1834.3.3輸入設(shè)備輸入設(shè)備是用來接收用戶輸入的原始數(shù)據(jù)和程序，并將它們變?yōu)橛嬎銠C(jī)能識別的二進(jìn)制存入到內(nèi)存中。1844.3.3輸入設(shè)備字符輸入設(shè)備鍵盤光學(xué)閱讀設(shè)備光學(xué)標(biāo)記閱讀器光學(xué)字符閱讀器定位設(shè)備鼠標(biāo)、操縱桿、觸摸屏幕和觸摸板、軌跡球、光筆模擬輸入設(shè)備語音輸入設(shè)備數(shù)模轉(zhuǎn)換器圖像輸入設(shè)備攝像機(jī)、掃描儀數(shù)碼相機(jī)輸入設(shè)備按功能分類1854.3.4輸出設(shè)備輸出設(shè)備用于將內(nèi)存中計算機(jī)處理的結(jié)果轉(zhuǎn)變?yōu)槿藗兡芙邮艿男问捷敵?。常用的輸出設(shè)備有顯示器、打印機(jī)、繪圖儀及語音輸出設(shè)備等。186顯示器按工作原理分類4.3.4輸出設(shè)備01CRT顯示器02LCD顯示器03LED顯示器04PDP顯示器1874.3.4輸出設(shè)備顯示器的性能指標(biāo)亮度分辨率顯示尺寸色彩數(shù)刷新頻率點(diǎn)距1884.3.4輸出設(shè)備噴墨打印機(jī)激光打印機(jī)針式打印機(jī)常見的打印機(jī)1894.3.4輸出設(shè)備1分辨率2色彩飽和度3打印速度打印機(jī)的性能指標(biāo)1904.3.5總線總線是一種內(nèi)部結(jié)構(gòu)，它是CPU、內(nèi)存、輸入、輸出設(shè)備傳遞信息的公用通道。主機(jī)的各個部件通過總線相連接，外部設(shè)備通過相應(yīng)的接口電路再與總線相連接，從而形成了計算機(jī)硬件系統(tǒng)。1914.3.5總線計算機(jī)各芯片內(nèi)部傳送信息的通路片內(nèi)總線A將計算機(jī)系統(tǒng)內(nèi)部的各個組成部分連接在一起的線路系統(tǒng)總線B將計算機(jī)和其他的設(shè)備連接到一起的基礎(chǔ)線路通信總線C根據(jù)總線所連接的對象所在位置不同分類1924.3.5總線01并行總線02串行總線根據(jù)傳輸數(shù)據(jù)的方式不同分類1934.3.6計算機(jī)的性能指標(biāo)CPU類型字長運(yùn)算速度內(nèi)、外存儲器容量存取速度時鐘頻率1944.4計算機(jī)軟件系統(tǒng)計算機(jī)運(yùn)行的各種程序、數(shù)據(jù)及相關(guān)的文檔資料計算機(jī)軟件系統(tǒng)系統(tǒng)軟件應(yīng)用軟件擔(dān)負(fù)控制和協(xié)調(diào)計算機(jī)及其外部設(shè)備、支持應(yīng)用軟件的開發(fā)和運(yùn)行的一類計算機(jī)軟件為滿足用戶不同領(lǐng)域、不同問題的應(yīng)用需求而提供的那部分軟件MicrosoftOffice圖形編輯軟視頻編輯軟件聊天軟件……操作系統(tǒng)語言處理程序數(shù)據(jù)庫管理系統(tǒng)……1954.4計算機(jī)軟件系統(tǒng)操作系統(tǒng)是計算機(jī)系統(tǒng)的控制和管理中心04文件管理01處理器管理02存儲器管理03設(shè)備管理1964.4計算機(jī)軟件系統(tǒng)驅(qū)動程序是外設(shè)與計算機(jī)之間建立通信的軟件在安裝完成后，設(shè)備驅(qū)動程序就會在需要它時自動啟動設(shè)備驅(qū)動程序是運(yùn)行在后臺的程序，通常不會在屏幕上打開窗口1974.4計算機(jī)軟件系統(tǒng)A指將程序文件和文件夾添加到硬盤并將相關(guān)數(shù)據(jù)添加到注冊表，以使軟件能夠正常運(yùn)行的過程。安裝軟件應(yīng)用軟件根據(jù)安裝方式不同，可以分成本地應(yīng)用軟件和便攜式軟件（綠色軟件）。1984.4計算機(jī)軟件系統(tǒng)A從硬盤刪除程序文件和文件夾以及從注冊表刪除相關(guān)數(shù)據(jù)的操作，釋放原來占用的磁盤空間并使其軟件不再存在于系統(tǒng)中。卸載軟件A軟件開發(fā)者在編寫軟件的時候，由于設(shè)計人員考慮不全面或程序功能不完善，在軟件發(fā)行后，通過對程序的修改或加入新的功能后，以補(bǔ)丁或者新版本的形式發(fā)布。用戶把這些補(bǔ)丁更新或者安裝新版本，即完成升級。軟件升級第5章數(shù)據(jù)結(jié)構(gòu)199鏈棧用單鏈表表示目錄2005.2.1線性表的基本概念5.2.2線性表的存儲與處理5.2.3棧的存儲與處理5.2.4隊(duì)列的存儲與處理5.2線性表5.1基本概念5.3.1樹的基本概念5.3.2二叉樹的基本概念5.3.3二叉樹的遍歷5.3樹5.4.1圖的概念5.4.2圖的遍歷5.4圖5.1基本概念201數(shù)據(jù)：所有能輸入到計算機(jī)中并能被計算機(jī)程序識別和處理的符號集合。數(shù)值數(shù)據(jù)：整數(shù)、實(shí)數(shù)等非數(shù)值數(shù)據(jù)：圖形、圖象、聲音、文字等數(shù)據(jù)元素：數(shù)據(jù)的基本單位，在計算機(jī)程序中通常作為一個整體進(jìn)行考慮和處理。數(shù)據(jù)對象：數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素構(gòu)成的集合，是數(shù)據(jù)的一個子集。學(xué)號姓名性別出生日期班級20190001鹿鳴男1978/10/151班20190002王強(qiáng)男1972/09/141班20190003林淼淼女1575/02/092班數(shù)據(jù)元素數(shù)據(jù)項(xiàng)5.1基本概念202

數(shù)據(jù)結(jié)構(gòu)：是一個二元組DataStructure=（D，S），其中D是一個數(shù)據(jù)元素的有限集合，S是D上的關(guān)系的有限集合。按照視點(diǎn)的不同，數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)。集合結(jié)構(gòu)線性結(jié)構(gòu)樹結(jié)構(gòu)圖結(jié)構(gòu)

（a）集合（b）線性結(jié)構(gòu)（c）樹結(jié)構(gòu)（d）圖結(jié)構(gòu)圖5-2數(shù)據(jù)的邏輯結(jié)構(gòu)5.1基本概念203通常有兩種存儲結(jié)構(gòu)：1.順序存儲結(jié)構(gòu)：用一組連續(xù)的存儲單元依次存儲數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系由元素的存儲位置來表示。2.鏈接存儲結(jié)構(gòu)：用一組任意的存儲單元存儲數(shù)據(jù)元素，數(shù)據(jù)元素之間的邏輯關(guān)系用指針來表示。

圖5-3

數(shù)據(jù)的順序存儲結(jié)構(gòu)圖5-4數(shù)據(jù)的鏈?zhǔn)酱鎯Y(jié)構(gòu)線性表：它是由n（n≥0）個具有相同類型的數(shù)據(jù)元素組成的有限序列，如圖5-5所示。線性表的一般表示如下：L=（a1,a2,…,ai,ai+1,…,an）n：為線性表的長度。

L:表示線性表名稱ai:(1≤i≤n)稱為數(shù)據(jù)元素，下角標(biāo)i表示該元素在線性表中的位置或序號。

5.2線性表圖5-5

線性表結(jié)構(gòu)示意圖

5.2.2線性表的存儲與處理2051.順序存儲結(jié)構(gòu)及操作線性表的順序存儲結(jié)構(gòu)稱為順序表。順序表是用一段地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。用數(shù)組存儲順序表，用MaxSize表示數(shù)組的長度，用length表示線性表的長度，順序表的存儲示意圖如圖5-6所示。

圖5-6

數(shù)組的長度與線性表的長度具有不同的含義意圖

插入前：(a1,…,ai-1,ai,…,an)插入后：(a1,…,ai-1,x

,ai,…,an)ai-1和ai之間的邏輯關(guān)