計(jì)算機(jī)導(dǎo)論 課件 第5、6章 算法與數(shù)據(jù)結(jié)構(gòu)、計(jì)算機(jī)程序設(shè)計(jì)基礎(chǔ)

計(jì)算機(jī)導(dǎo)論教師：第5章算法與數(shù)據(jù)結(jié)構(gòu)05目錄CONTENTS1算法2數(shù)據(jù)結(jié)構(gòu)的概念3幾種常見的數(shù)據(jù)結(jié)構(gòu)4查找和排序本章學(xué)習(xí)目標(biāo)了解算法的概念了解算法與數(shù)據(jù)結(jié)構(gòu)的關(guān)系掌握數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)掌握數(shù)據(jù)結(jié)構(gòu)的存儲結(jié)構(gòu)了解常用的查找與排序算法本章學(xué)習(xí)目標(biāo)算法算法（Algorithm）是指對解題方案的準(zhǔn)確而完整的描述，是一系列解決問題的清晰指令，算法代表用系統(tǒng)的方法描述解決問題的策略機(jī)制。算法不是程序，但程序員可以使用某種編程語言來實(shí)現(xiàn)算法。算法被公認(rèn)為是計(jì)算機(jī)科學(xué)的靈魂。從理論角度來看，對算法的研究（有時(shí)稱為“算法學(xué)”）已經(jīng)被公認(rèn)為是計(jì)算機(jī)科學(xué)的基石。

算法的概念算法的基本特性一個(gè)算法必須在有限步驟之內(nèi)結(jié)束，不能形成死循環(huán)。這種有限性使算法不能保證一定有解。有限性算法中的每條指令必須有確定含義，無二義性，不會產(chǎn)生理解偏差。算法可以有多條執(zhí)行路徑，但是對某個(gè)確定的條件值只能選擇其中一條路徑執(zhí)行。確定性一個(gè)算法有多個(gè)或0個(gè)輸入，輸入取自某些特定對象的集合。有些輸入在算法執(zhí)行過程中輸入，有些算法不需要外部輸入。輸入至少有一個(gè)或多個(gè)輸出，輸出與輸入之間存在某些特定的關(guān)系。不同的輸入可以產(chǎn)生不同或相同的輸出，但是相同的輸入必須產(chǎn)生相同的輸出。輸出算法是可行的。描述的操作可通過已實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次而完成?？尚行杂米匀徽Z言描述算法用自然語言描述算法的優(yōu)點(diǎn)是簡單，但容易出現(xiàn)歧義。例5-1用自然語言描述求兩個(gè)整數(shù)的最大公約數(shù)的算法。步驟1：輸入兩個(gè)整數(shù)x和y；步驟2：x和y整除余數(shù)為r；步驟3：判斷余數(shù)r是否為0，如果為0，則轉(zhuǎn)步驟5；否則轉(zhuǎn)步驟4；步驟4：x的值是y的值，y的值是r的值,轉(zhuǎn)步驟2；步驟5：輸出y。y為所求的兩個(gè)整數(shù)的最大公約數(shù)。

算法的描述用流程圖描述算法美國國家標(biāo)準(zhǔn)化協(xié)會（AmericanNationalStandardsInstitute,ANSI）曾規(guī)定了一些常用的流程圖符號，可以用這些流程圖符號描述算法的執(zhí)行步驟。例5-2用流程圖描述求兩個(gè)整數(shù)的最大公約數(shù)的算法：如圖5-2所示。

算法的描述用偽代碼描述算法偽代碼（Pseudocode）是一種非正式的，用介于自然語言和計(jì)算機(jī)語言之間的文字和符號（包括數(shù)學(xué)符號）來描述算法。使用偽代碼的目的是使被描述的算法可以容易地以任何一種編程語言（Pascal、C、Java等）來實(shí)現(xiàn)。因此，偽代碼必須結(jié)構(gòu)清晰、代碼簡單、可讀性好，并且類似自然語言。

算法的描述用類C語言描述算法

算法的描述算法設(shè)計(jì)要求算法的正確性是指在給定有效輸入后，經(jīng)過有限時(shí)間的計(jì)算并產(chǎn)生正確的答案。正確性算法的可讀性是指一個(gè)算法可供人們閱讀的容易程度?？勺x性算法的健壯性是指一個(gè)算法對不合理數(shù)據(jù)輸入的反應(yīng)能力和處理能力，也稱為容錯(cuò)性。健壯性算法的效率通常是指算法的執(zhí)行時(shí)間。對于一個(gè)具體問題的解決，通常有多個(gè)算法，執(zhí)行時(shí)間短的算法其效率就高。計(jì)算機(jī)的另一個(gè)有限資源就是內(nèi)存，希望一個(gè)算法的執(zhí)行所需要的最大存儲空間盡可能得少。高效率和低存儲數(shù)據(jù)結(jié)構(gòu)的發(fā)展計(jì)算機(jī)加工處理對象范圍、類型不斷擴(kuò)展，由純數(shù)值發(fā)展到字符、表格、聲音和圖像的各種具有一定結(jié)構(gòu)的數(shù)據(jù)。為了應(yīng)對信息時(shí)代計(jì)算機(jī)處理對象特點(diǎn)的變化，迫切需要分析待處理數(shù)據(jù)對象的特性及其各處理對象間的關(guān)系。1968年，美國著名計(jì)算機(jī)科學(xué)家高德納（DonaldErvinKnuth）開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》第一卷《基本算法》是第一本系統(tǒng)闡述數(shù)據(jù)結(jié)構(gòu)的著作。瑞士計(jì)算機(jī)科學(xué)家尼古拉斯·沃斯（NiklausWirth）在1976年出版的著作中指出：“算法+數(shù)據(jù)結(jié)構(gòu)=程序”，可見數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計(jì)中的重要性。數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)結(jié)構(gòu)的定義數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)（Data）是描述客觀事物的數(shù)值、字符及能輸入機(jī)器且能被處理的各種符號的集合。數(shù)據(jù)元素（DataElement）作為數(shù)據(jù)的基本單位。一個(gè)數(shù)據(jù)元素可由一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)（DataItem）組成，數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的數(shù)據(jù)最小單位。數(shù)據(jù)對象（DataObject）是指性質(zhì)相同的數(shù)據(jù)元素的集合，它是數(shù)據(jù)的一個(gè)子集。數(shù)據(jù)結(jié)構(gòu)（DataStructure）是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素集合，數(shù)據(jù)結(jié)構(gòu)應(yīng)該包括數(shù)據(jù)元素集合及元素間關(guān)系的集合。因此，我們可以把數(shù)據(jù)結(jié)構(gòu)看成帶結(jié)構(gòu)的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容通常包括3個(gè)方面：數(shù)據(jù)結(jié)構(gòu)的概念數(shù)據(jù)的邏輯結(jié)構(gòu)由數(shù)據(jù)元素之間的邏輯關(guān)系構(gòu)成，是獨(dú)立于計(jì)算機(jī)的，因此數(shù)據(jù)邏輯結(jié)構(gòu)可以看作從具體問題抽象出來的數(shù)學(xué)模型。數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲器中的存儲表示，也稱為數(shù)據(jù)的物理結(jié)構(gòu)。顯然，數(shù)據(jù)的存儲結(jié)構(gòu)是依賴于計(jì)算機(jī)的。數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的運(yùn)算是施加在數(shù)據(jù)上的操作，常用的有查找、插入、刪除、更新和排序等。數(shù)據(jù)的運(yùn)算需要在對應(yīng)的存儲結(jié)構(gòu)上用算法實(shí)現(xiàn)。數(shù)據(jù)的運(yùn)算邏輯結(jié)構(gòu)的定義邏輯結(jié)構(gòu)

基本的數(shù)據(jù)結(jié)構(gòu)邏輯結(jié)構(gòu)集合結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間除“同屬于一個(gè)集合”的關(guān)系以外別無其他關(guān)系。線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對一的線性關(guān)系。其特點(diǎn)是，除第一個(gè)元素和最后一個(gè)元素外，每個(gè)元素都有且僅有一個(gè)前驅(qū)元素，有且僅有一個(gè)后繼元素。樹形結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著一對多的層次關(guān)系。其特點(diǎn)是，如果數(shù)據(jù)元素集合非空，則有且僅有一個(gè)元素被稱為根元素，除根元素以外的其他元素有且僅有一個(gè)前驅(qū)元素。所有元素有0個(gè)或多個(gè)后繼。圖形結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在著多對多的任意關(guān)系。其特點(diǎn)是，每個(gè)元素的前驅(qū)元素和后繼元素的個(gè)數(shù)可以是任意的。邏輯結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)存儲結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲器中的存儲表示被稱為數(shù)據(jù)的存儲結(jié)構(gòu)（也稱為映像），也就是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲實(shí)現(xiàn)，它包括數(shù)據(jù)對象的表示和數(shù)據(jù)對象中數(shù)據(jù)元素關(guān)系的表示。順序存儲結(jié)構(gòu)存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)采用一組連續(xù)的存儲單元存放所有的數(shù)據(jù)元素，并映射元素之間的邏輯關(guān)系。也就是說，所有的數(shù)據(jù)元素在計(jì)算機(jī)存儲器中占用一整塊存儲空間。一般來說，順序存儲結(jié)構(gòu)是高級語言的數(shù)組。鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)是指使用“鏈表”存儲映像數(shù)據(jù)的邏輯結(jié)構(gòu)，鏈表是由節(jié)點(diǎn)構(gòu)成的，每個(gè)節(jié)點(diǎn)對應(yīng)一個(gè)數(shù)據(jù)元素，每個(gè)節(jié)點(diǎn)是單獨(dú)分配的，所有節(jié)點(diǎn)的地址不一定是連續(xù)的。為了表示元素之間的邏輯關(guān)系，每個(gè)節(jié)點(diǎn)有一個(gè)或多個(gè)指針域，用于存儲邏輯上相鄰節(jié)點(diǎn)的地址，也就是通過指針域?qū)⑺泄?jié)點(diǎn)連接起來而形成鏈表。索引存儲結(jié)構(gòu)存儲結(jié)構(gòu)索引存儲結(jié)構(gòu)是指在存儲數(shù)據(jù)元素信息的同時(shí)還要建立附加的索引表。存儲所有數(shù)據(jù)元素信息的表稱為主數(shù)據(jù)表，其中每個(gè)數(shù)據(jù)元素有一個(gè)關(guān)鍵字和對應(yīng)的存儲地址。散列存儲結(jié)構(gòu)存儲結(jié)構(gòu)散列存儲也稱哈希存儲。散列存儲的基本思想是根據(jù)元素的關(guān)鍵字通過散列函數(shù)直接計(jì)算出一個(gè)值，并將這個(gè)值作為該元素的存儲地址。與前3種存儲結(jié)構(gòu)不同的是，散列存儲不涉及數(shù)據(jù)元素之間關(guān)系的映射，所以散列存儲主要應(yīng)用于元素間沒有邏輯關(guān)系的集合結(jié)構(gòu)，以便數(shù)據(jù)的查找和插入運(yùn)算。數(shù)據(jù)運(yùn)算數(shù)據(jù)運(yùn)算是指對數(shù)據(jù)實(shí)施的操作。每種數(shù)據(jù)結(jié)構(gòu)都有一組相應(yīng)的運(yùn)算，常用的運(yùn)算有查找、插入、刪除、遍歷、排序等。數(shù)據(jù)運(yùn)算分為運(yùn)算定義和運(yùn)算實(shí)現(xiàn)兩個(gè)層面。運(yùn)算定義是運(yùn)算功能的描述，是抽象的，基于邏輯結(jié)構(gòu)的。運(yùn)算實(shí)現(xiàn)是基于存儲結(jié)構(gòu)的，同樣的運(yùn)算定義，如果存儲結(jié)構(gòu)不同，運(yùn)算實(shí)現(xiàn)的算法基本不同。對于一種數(shù)據(jù)結(jié)構(gòu)，其邏輯結(jié)構(gòu)總是唯一的，但它可能對應(yīng)多種存儲結(jié)構(gòu)，并且在不同的存儲結(jié)構(gòu)中同一運(yùn)算的實(shí)現(xiàn)過程可能不同。線性表的定義線性表

線性表的存儲結(jié)構(gòu)線性表線性表的存儲結(jié)構(gòu)有兩種：順序存儲和鏈?zhǔn)酱鎯?。線性表的順序存儲，是把線性表中的所有元素按照邏輯順序依次存儲到一塊地址連續(xù)的存儲空間中，邏輯上相鄰的兩個(gè)元素，物理上也是相鄰的。線性表的順序存儲結(jié)構(gòu)簡稱為順序表。線性表的鏈?zhǔn)酱鎯σ卜Q鏈表。一般采用帶頭節(jié)點(diǎn)的單鏈表存儲線性表。操作受限的線性表線性表?xiàng)＃⊿tack）是指將線性表的插入和刪除運(yùn)算限制為僅在表的一端進(jìn)行。通常將表中允許進(jìn)行插入、刪除操作的一端稱為棧頂，將表的另一端稱為棧底。當(dāng)棧中沒有元素時(shí)稱為空棧。棧的插入操作被形象地稱為進(jìn)?；蛉霔＃瑒h除操作被稱為出?；蛲藯?。隊(duì)列（Queue）是另一種限定性的線性表，它只允許在表的一端插入元素，而在另一端刪除元素，所以隊(duì)列具有先進(jìn)先出的特性。在隊(duì)列中，允許插入的一端叫作隊(duì)尾，允許刪除的一端叫作隊(duì)頭。樹的基本概念和特征樹型結(jié)構(gòu)

二叉樹樹型結(jié)構(gòu)二叉樹（BinaryTree）是一個(gè)有限的節(jié)點(diǎn)集合，這個(gè)集合或?yàn)榭眨蛴梢粋€(gè)根節(jié)點(diǎn)和兩棵不相交的稱為左子樹和右子樹的二叉樹構(gòu)成。二叉樹的定義也是遞歸定義。二叉樹有5種基本形態(tài)。二叉樹中的節(jié)點(diǎn)最多有兩個(gè)孩子，分別稱為左孩子和右孩子。滿二叉樹和完全二叉樹樹型結(jié)構(gòu)在一棵二叉樹中，如果所有分支節(jié)點(diǎn)都有兩個(gè)孩子節(jié)點(diǎn)，并且葉子節(jié)點(diǎn)都集中在二叉樹的最下面一層，這樣的二叉樹稱為滿二叉樹。若二叉樹中最多只有最下面兩層節(jié)點(diǎn)的度數(shù)可以小于2，并且最下面一層的葉子節(jié)點(diǎn)都排列在該層最左邊的位置上，則這樣的二叉樹被稱為完全二叉樹。二叉樹的二叉鏈表存儲結(jié)構(gòu)樹型結(jié)構(gòu)二叉樹也有順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，常用的是鏈?zhǔn)酱鎯Y(jié)構(gòu)。因?yàn)槎鏄渥疃嘤袃蓚€(gè)孩子，因此鏈表節(jié)點(diǎn)有兩個(gè)指針域，分別指向左孩子和右孩子。二叉樹的順序存儲結(jié)構(gòu)樹型結(jié)構(gòu)二叉樹的順序存儲就是用一組地址連續(xù)的存儲單元來存放二叉樹的數(shù)據(jù)元素。對于完全二叉樹和滿二叉樹，樹中節(jié)點(diǎn)的層序編號可以唯一地反映節(jié)點(diǎn)之間的邏輯關(guān)系，所以可以用一維數(shù)組按從上到下，從左到右的順序存儲二叉樹中的所有節(jié)點(diǎn)的值，即編號為的節(jié)點(diǎn)存儲在下標(biāo)為的數(shù)組單元中。二叉樹的遍歷樹型結(jié)構(gòu)二叉樹的遍歷是指按照一定的次序訪問二叉樹中的所有節(jié)點(diǎn)，并且每個(gè)節(jié)點(diǎn)僅被訪問一次的過程。一棵二叉樹由3部分組成，即根節(jié)點(diǎn)、左子樹和右子樹，若規(guī)定遍歷時(shí)先左后右，則對于非空二叉樹，可以得到3種遞歸的遍歷方法，即先序遍歷、中序遍歷和后序遍歷。對于非空二叉樹：先序遍歷：訪問根節(jié)點(diǎn)、先序遍歷左子樹、先序遍歷右子樹。中序遍歷：中序遍歷左子樹、訪問根節(jié)點(diǎn)、中序遍歷右子樹。后序遍歷：后序遍歷左子樹、后序遍歷右子樹、訪問根節(jié)點(diǎn)除此之外，還可以對一棵二叉樹按層遍歷，即按照從上到下，從左到右的順序遍歷二叉樹。二叉樹的遍歷樹型結(jié)構(gòu)按層遍歷：ABCDEFG先序遍歷：ABDGCEF中序遍歷：BGDAECF后序遍歷：GDBEFCA圖的基本概念圖形結(jié)構(gòu)

圖的存儲結(jié)構(gòu)圖形結(jié)構(gòu)常用的兩種圖的存儲結(jié)構(gòu)是鄰接矩陣和鄰接表。鄰接矩陣：使用一個(gè)一維數(shù)組來存儲圖中的頂點(diǎn)信息，每個(gè)頂點(diǎn)都被分配了一個(gè)唯一的編號，該編號與數(shù)組下標(biāo)一一對應(yīng)。使用另一個(gè)二維數(shù)組，也即鄰接矩陣來存儲圖中頂點(diǎn)之間的連接關(guān)系，元素的值為0或1，1表示有邊或弧相連，而0則表示沒有。

圖的存儲結(jié)構(gòu)圖形結(jié)構(gòu)常用的兩種圖的存儲結(jié)構(gòu)是鄰接矩陣和鄰接表。鄰接表：使用一個(gè)一維數(shù)組存儲圖，一維數(shù)組元素包含兩個(gè)數(shù)據(jù)項(xiàng)：頂點(diǎn)信息及這個(gè)頂點(diǎn)所有鄰接點(diǎn)的單鏈表的頭指針。由于一個(gè)頂點(diǎn)的所有鄰接點(diǎn)以單鏈表存儲，因此這種存儲結(jié)構(gòu)是順序+鏈?zhǔn)酱鎯Y(jié)構(gòu)。圖的遍歷圖形結(jié)構(gòu)從圖中某一頂點(diǎn)出發(fā)訪問圖中的所有頂點(diǎn)，且每個(gè)頂點(diǎn)僅被訪問一次，這一過程就叫作圖的遍歷。通常有兩種遍歷策略：深度優(yōu)先遍歷和廣度優(yōu)先遍歷。深度優(yōu)先遍歷，也稱為深度優(yōu)先搜索(DepthFirstSearch,DFS)：從圖中某個(gè)頂點(diǎn)v出發(fā)，先訪問此頂點(diǎn)，然后從v的未被訪問的鄰接點(diǎn)出發(fā)進(jìn)行DFS，直至圖中所有和v有路徑相通的頂點(diǎn)都被訪問到。若圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未曾被訪問的頂點(diǎn)做起始點(diǎn)，重復(fù)上述過程，直至圖中的所有頂點(diǎn)都被訪問到為止。圖的遍歷圖形結(jié)構(gòu)從圖中某一頂點(diǎn)出發(fā)訪問圖中的所有頂點(diǎn)，且每個(gè)頂點(diǎn)僅被訪問一次，這一過程就叫作圖的遍歷。通常有兩種遍歷策略：深度優(yōu)先遍歷和廣度優(yōu)先遍歷。廣度優(yōu)先遍歷，又稱為廣度優(yōu)先搜索（BreathFirstSearch，BFS）：從圖中某頂點(diǎn)v出發(fā)，在訪問了v之后依次先訪問v的各個(gè)未曾訪問過的鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)依次訪問它們的鄰接點(diǎn)，并使得“先被訪問的頂點(diǎn)的鄰接點(diǎn)先于后被訪問的頂點(diǎn)的鄰接點(diǎn)被訪問”，直至圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到。如果此時(shí)圖中尚有頂點(diǎn)未被訪問，則需要另選一個(gè)未曾被訪問過的頂點(diǎn)作為新的起始點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到為止。查找查找和排序查找又稱檢索，是指在某種數(shù)據(jù)結(jié)構(gòu)中找出滿足給定條件的元素，主要有基于線性表的查找、基于樹的查找和哈希表查找。

查找查找和排序查找又稱檢索，是指在某種數(shù)據(jù)結(jié)構(gòu)中找出滿足給定條件的元素，主要有基于線性表的查找、基于樹的查找和哈希表查找。二分查找又稱折半查找，要求待查找的順序表是按關(guān)鍵字有序的。算法的思想是：將順序表中間位置的元素的關(guān)鍵字與查找關(guān)鍵字做比較，如果兩者相等，則查找成功；否則如果中間位置元素的關(guān)鍵字大于查找關(guān)鍵字，則在前半部分繼續(xù)查找，否則在后半部分繼續(xù)查找，重復(fù)以上過程，直到找到滿足條件的元素或查找范圍為空。因?yàn)槊勘容^一次或會查找成功，或使查找范圍縮小一半，因此該算法稱為折半查找算法。排序查找和排序排序是將一個(gè)數(shù)據(jù)元素（或記錄）的任意序列，重新排列成一個(gè)按關(guān)鍵字有序的序列。學(xué)習(xí)和研究各種排序方法是計(jì)算機(jī)領(lǐng)域的重要課題之一。冒泡排序查找和排序冒泡排序算法是一種典型的交換排序算法，基本思想是通過無序區(qū)中相鄰元素關(guān)鍵字的比較和相鄰元素的交換使關(guān)鍵字小的元素如氣泡般往上“漂浮”?？焖倥判蛩惴ú檎液团判蚩焖倥判蛩惴ú捎梅种尾呗?，對無序區(qū)，首先選取某個(gè)稱為基準(zhǔn)的元素（一般為無序區(qū)的第1個(gè)元素），利用這個(gè)基準(zhǔn)元素，把無序區(qū)分成兩個(gè)子序列，第1個(gè)子序列的所有元素值都小于或等于這個(gè)基準(zhǔn)，第2個(gè)子序列的所有元素都大于或等于這個(gè)基準(zhǔn)。然后遞歸對兩個(gè)子序列采用同樣的算法劃分，子序列規(guī)模越來越小，直到每個(gè)子序列只有一個(gè)元素或空為止。這時(shí)整個(gè)序列也就有序了。直接插入排序查找和排序直接插入排序算法的思想：初始時(shí)，將序列中第一個(gè)元素作為有序區(qū)，剩下的n-1個(gè)元素作為無序區(qū)。每一次，把無序區(qū)的第一個(gè)元素插入有序區(qū)，每插入一個(gè)元素后依然保持有序區(qū)有序，有序區(qū)元素個(gè)數(shù)增一，無序區(qū)元素個(gè)數(shù)減一，經(jīng)過n-1趟后即成為有序序列。簡單選擇排序查找和排序簡單選擇排序算法的基本思想：每次總是從無序序列中選出最小元素并把其放在無序序列的起始位置。每選擇一次會使無序序列元素個(gè)數(shù)減一，使有序序列元素個(gè)數(shù)增一，共需要n-1趟選擇。初始時(shí)，無序序列元素個(gè)數(shù)為n。擴(kuò)展閱讀：密碼與安全一直在國際上廣泛應(yīng)用的兩大密碼算法MD5、SHA-1，被一名中國密碼專家破解，這在當(dāng)時(shí)的國際社會尤其是國際密碼學(xué)領(lǐng)域引起了極大反響，也再次敲響了電子商務(wù)安全的警鐘。從密碼分析上找出這兩大國際通用密碼漏洞的是一位土生土長的中國專家——山東大學(xué)網(wǎng)絡(luò)空間安全學(xué)院院長王小云教授。SHA-1在美國等國家有更加廣泛的應(yīng)用，密碼被破的消息一出，在國際社會的反響可謂石破天驚。王小云教授的研究成果表明了從理論上講電子簽名可以偽造，必須及時(shí)添加限制條件，或者重新選用更為安全的密碼標(biāo)準(zhǔn)，以保證電子商務(wù)的安全。中國密碼專家王小云教授的密碼破解與信息安全擴(kuò)展閱讀：密碼與安全一直在國際上廣泛應(yīng)用的兩大密碼算法MD5、SHA-1，被一名中國密碼專家破解，這在當(dāng)時(shí)的國際社會尤其是國際密碼學(xué)領(lǐng)域引起了極大反響，也再次敲響了電子商務(wù)安全的警鐘。從密碼分析上找出這兩大國際通用密碼漏洞的是一位土生土長的中國專家——山東大學(xué)網(wǎng)絡(luò)空間安全學(xué)院院長王小云教授。SHA-1在美國等國家有更加廣泛的應(yīng)用，密碼被破的消息一出，在國際社會的反響可謂石破天驚。王小云教授的研究成果表明了從理論上講電子簽名可以偽造，必須及時(shí)添加限制條件，或者重新選用更為安全的密碼標(biāo)準(zhǔn)，以保證電子商務(wù)的安全。中國密碼專家王小云教授的密碼破解與信息安全擴(kuò)展閱讀：密碼與安全密碼學(xué)是信息安全的基石，信息安全屬于新興學(xué)科，隨著信息安全與網(wǎng)絡(luò)空間安全領(lǐng)域的迅猛發(fā)展，中國在很多方面達(dá)到了國際領(lǐng)先水平，但與國際整體水平還有一定差距，未來還需要更多的信息安全與網(wǎng)絡(luò)空間安全人才，以發(fā)展密碼防御體系，共筑國家安全。信息安全的重要性謝謝聆聽THANKS計(jì)算機(jī)導(dǎo)論教師：第6章計(jì)算機(jī)程序設(shè)計(jì)基礎(chǔ)06目錄CONTENTS1程序設(shè)計(jì)語言概述2高級語言程序的編譯執(zhí)行和解釋執(zhí)行3結(jié)構(gòu)化程序設(shè)計(jì)語言C語言4面向?qū)ο缶幊陶Z言Java動(dòng)態(tài)程序設(shè)計(jì)語言Python56如何學(xué)習(xí)程序設(shè)計(jì)本章學(xué)習(xí)目標(biāo)了解程序設(shè)計(jì)語言的發(fā)展歷史了解面向過程的語言和面向?qū)ο蟮恼Z言掌握高級程序語言的基本構(gòu)成了解C語言程序設(shè)計(jì)本章學(xué)習(xí)目標(biāo)機(jī)器語言機(jī)器語言是用二進(jìn)制代碼表示的計(jì)算機(jī)能直接識別和執(zhí)行的一種機(jī)器指令的集合。它是計(jì)算機(jī)的設(shè)計(jì)者通過計(jì)算機(jī)的硬件結(jié)構(gòu)賦予計(jì)算機(jī)的操作功能。機(jī)器語言具有靈活、直接執(zhí)行和速度快等特點(diǎn)，不同型號的計(jì)算機(jī)其機(jī)器語言是不相通的，機(jī)器語言使用絕對地址和絕對操作碼。用機(jī)器語言編寫的程序全是0和1的指令代碼，可讀性和可移植性差，容易出錯(cuò)。

程序設(shè)計(jì)語言概述匯編語言匯編語言是一種用于電子計(jì)算機(jī)、微處理器、微控制器或其他可編程器件的低級語言，亦稱為符號語言。在匯編語言中，用助記符代替機(jī)器指令的操作碼，用地址符號或標(biāo)號代替指令或操作數(shù)的地址。一般來說，匯編語言和特定的機(jī)器語言指令集是一一對應(yīng)的，不同平臺之間不可直接移植。匯編語言在一些對于時(shí)效性要求很高的程序、許多大型程序的核心模塊及工業(yè)控制方面大量被應(yīng)用。另外，驅(qū)動(dòng)程序、嵌入式操作系統(tǒng)和實(shí)時(shí)運(yùn)行程序都需要匯編語言。

程序設(shè)計(jì)語言概述高級語言高級語言相對于匯編語言，更接近自然語言和數(shù)學(xué)公式，編程過程基本脫離了機(jī)器硬件的細(xì)節(jié)。程序員使用更易理解的方式編寫源程序，然后通過編譯器或解釋器將其翻譯成機(jī)器代碼運(yùn)行。編譯器和解釋器是用來實(shí)現(xiàn)高級語言到機(jī)器語言轉(zhuǎn)換的工具。高級語言的出現(xiàn)使編程更加抽象，不再需要直接操作硬件指令，程序能夠更好地描述和解決實(shí)際問題。高級語言主要分為兩大類：以C語言為代表的面向過程的程序設(shè)計(jì)語言和以Java、C#語言等為代表的面向?qū)ο蟮某绦蛟O(shè)計(jì)語言。了解高級語言的核心概念，首先要理解四個(gè)要素：“變量”是內(nèi)存中的若干字節(jié)，通過命名使用，無需關(guān)心具體位置；“表達(dá)式”采用數(shù)學(xué)算式的形式描述數(shù)據(jù)計(jì)算過程；“語句”表示執(zhí)行特定任務(wù)的一段代碼；“賦值”將計(jì)算結(jié)果保存到變量中。計(jì)算機(jī)主要能做兩件事：執(zhí)行計(jì)算和保存結(jié)果，而高級語言以數(shù)學(xué)式子的方式描述數(shù)據(jù)計(jì)算，其中變量用于保存計(jì)算的初值、中間結(jié)果和最終結(jié)果。

程序設(shè)計(jì)語言概述編譯執(zhí)行和解釋執(zhí)行編譯執(zhí)行編譯是將高級語言程序（源程序）轉(zhuǎn)換成機(jī)器語言程序，也稱為可執(zhí)行程序。每種高級語言的開發(fā)者都會開發(fā)對應(yīng)的編譯器，用于將該語言的程序轉(zhuǎn)換為機(jī)器語言。源程序轉(zhuǎn)變?yōu)樽罱K可執(zhí)行程序經(jīng)歷兩個(gè)階段：編譯和連接。在編譯階段，源程序被翻譯成機(jī)器語言書寫的目標(biāo)模塊；而在連接階段，這些目標(biāo)模塊與編譯軟件提供的一些基本模塊連接在一起，形成可以直接在計(jì)算機(jī)上運(yùn)行的可執(zhí)行程序。在編譯過程中，編譯器一般會對源程序進(jìn)行兩遍掃描：第一遍做基本的預(yù)處理，而第二遍按照語言的語法定義的翻譯規(guī)則將源程序翻譯成目標(biāo)代碼。如果源程序沒有按照語言的嚴(yán)格語法定義寫，編譯器就會報(bào)編譯錯(cuò)誤，并指出錯(cuò)誤的位置和原因。編譯執(zhí)行和解釋執(zhí)行解釋執(zhí)行解釋執(zhí)行是由解釋器來完成的，它不像編譯器將整個(gè)源程序一次性轉(zhuǎn)換成目標(biāo)代碼，而是逐行解釋執(zhí)行源程序。結(jié)構(gòu)化程序設(shè)計(jì)語言C語言程序的基本框架一個(gè)C程序是由一個(gè)稱為main的主函數(shù)和若干個(gè)自定義函數(shù)構(gòu)成的。結(jié)構(gòu)化程序設(shè)計(jì)語言C語言C語言編程示例結(jié)構(gòu)化程序設(shè)計(jì)語言C語言數(shù)據(jù)存儲與運(yùn)算C語言提供了大量的運(yùn)算符用于各種計(jì)算，參與計(jì)算的是數(shù)據(jù)，數(shù)據(jù)需要保存在計(jì)算機(jī)內(nèi)存中。數(shù)據(jù)是分類型的，不同類型的數(shù)據(jù)需要的存儲空間大小不同，支持的運(yùn)算也不同，運(yùn)算主要涉及算術(shù)運(yùn)算、關(guān)系運(yùn)算和邏輯運(yùn)算等，通過這些運(yùn)算可以解決很多實(shí)際問題。數(shù)據(jù)存儲與運(yùn)算C語言的基本數(shù)據(jù)類型short：短整型，一般占2字節(jié)，表示的數(shù)的范圍是-215~215-1。int：整型，一般占4字節(jié)，表示的數(shù)的范圍是-231~231-1。long：長整型，一般也占4字節(jié)。longlong：長長整型，一般占8字節(jié)，表示的數(shù)的范圍是-263~263-1。以上4種類型可以用unsigned修飾，表示無符號整數(shù)類型。char：字符型，占1字節(jié)。從技術(shù)層面看，char類型也是一個(gè)標(biāo)準(zhǔn)的整數(shù)類型。因?yàn)閏har類型實(shí)際上存儲的是整數(shù)而不是字符，是字符的ASCII碼，如'a'的ASCII碼是97。float：單精度浮點(diǎn)型，一般占4字節(jié)。double:雙精度浮點(diǎn)型，一般占8字節(jié)。數(shù)據(jù)存儲與運(yùn)算C語言的運(yùn)算符C語言的運(yùn)算符有算術(shù)運(yùn)算符、賦值運(yùn)算符、關(guān)系運(yùn)算符、邏輯運(yùn)算符和位運(yùn)算符等多種。算術(shù)運(yùn)算符用于數(shù)值計(jì)算：+、-、*、/、%、++、--。賦值運(yùn)算符用于對變量進(jìn)行賦值：=、+=、-=、*=、/=、%=、&=、|=、^=,>>=、<<=。關(guān)系運(yùn)算符用于數(shù)值的大小比較：>、<、==、>=、<=、!=。邏輯運(yùn)算符用于數(shù)值的邏輯操作：&&、||、！。位運(yùn)算符用于對某個(gè)整數(shù)類型變量中的某一位進(jìn)行操作：&、|、^、~、<<、>>。一個(gè)表達(dá)式中可以有多個(gè)、多種運(yùn)算符。不同的運(yùn)算符優(yōu)化級不同，可以用括號來規(guī)定表達(dá)式的計(jì)算順序。分支語句if語句if語句的形式為：if(表達(dá)式1)

語句/語句組1elseif(表達(dá)式2)

語句/語句組2……else

語句/語句組n分支語句switch語句switch(表達(dá)式){

case常量表達(dá)式1:語句/語句組1case常量表達(dá)式2:語句/語句組2……case常量表達(dá)式n:語句/語句組ndefault:語句/語句組n+1}循環(huán)語句for語句for(表達(dá)式1;表達(dá)式2;表達(dá)式3)

語句/語句組循環(huán)語句while語句while(表達(dá)式)

語句/語句組循環(huán)語句do-while語句do

語句會/語句組while(表達(dá)式);循環(huán)語句break語句和continue語句break語句用來結(jié)束離它最近的do-while、for、switch或while語句。在do-while、for或while語句中，continue語句會使其后的語句被忽略，直接進(jìn)入下一輪循環(huán)。函數(shù)函數(shù)定義函數(shù)是一段相關(guān)代碼的抽象，它通過函數(shù)名將相關(guān)的代碼組織在一起，先對輸入的數(shù)據(jù)（稱為參數(shù)）進(jìn)行處理，然后返回特定的輸出（稱為返回值）。一旦定義好函數(shù)之后，就完成了對函數(shù)名和該函數(shù)對應(yīng)的相關(guān)代碼的綁定，以后就可以利用函數(shù)名調(diào)用這段代碼來完成相應(yīng)的功能。返回值類型函數(shù)名(形式參數(shù)列表){

語句1

語句2…return返回值;

}函數(shù)函數(shù)聲明、函數(shù)調(diào)用和函數(shù)定義示例一般情況下，在main函數(shù)的前面聲明函數(shù)，在main函數(shù)的后面定義函數(shù)。結(jié)構(gòu)化程序設(shè)計(jì)語言C語言數(shù)組如果需要保存一組類型相同、含義相同、作用域相同的數(shù)據(jù)，可以使用數(shù)組來保存它，而不用使用很多個(gè)獨(dú)立的變量來保存。數(shù)組一維數(shù)組編程示例一維數(shù)組的定義方法如下：類型名數(shù)組名[元素個(gè)數(shù)];數(shù)組二維數(shù)組編程示例二維數(shù)組的定義方法如下：類型名數(shù)組名[行數(shù)][列數(shù)];指針指針就是內(nèi)存地址，指針變量就是存儲地址的變量。指針變量的定義方式：類型名*指針變量名;結(jié)構(gòu)學(xué)生的個(gè)人信息無法用基本數(shù)據(jù)類型一次描述清楚，因?yàn)閭€(gè)人信息包括姓名、年齡、專業(yè)、班級等，這時(shí)就需要用到C語言提供的結(jié)構(gòu)（struct）數(shù)據(jù)類型。結(jié)構(gòu)數(shù)據(jù)類型可以把基本數(shù)據(jù)類型和派生類型組合起來，以描述復(fù)雜的事物。結(jié)構(gòu)數(shù)據(jù)類型定義的語法如下：struct結(jié)構(gòu)名{成員類型名成員變量名;成員類型名成員變量名;成員類型名成員變量名;……};面向?qū)ο缶幊陶Z言JavaJava是Sun公司（后被Oracle收購）推出的Java程序語言和Java平臺的總稱，是一種廣泛使用的計(jì)算機(jī)編程語言，擁有跨平臺、面向?qū)ο?、分布式、泛型、多線程等特點(diǎn)，用于開發(fā)在移動(dòng)設(shè)備、臺式計(jì)算機(jī)和服務(wù)器上運(yùn)行的軟件。Java采用了一種不同于傳統(tǒng)編程語言的方法來實(shí)現(xiàn)跨平臺的目標(biāo)。Java在編譯時(shí)將源代碼轉(zhuǎn)換成一種稱為字節(jié)碼的中間狀態(tài)。這種字節(jié)碼不針對特定的操作系統(tǒng)，而是針對Java虛擬機(jī)（JVM）設(shè)計(jì)的。JVM是一個(gè)在操作系統(tǒng)上的平臺層，它負(fù)責(zé)將Java字節(jié)碼轉(zhuǎn)換成特定平臺的機(jī)器指令并執(zhí)行。因此，Java程序可以在任何安裝了Java虛擬機(jī)的平臺上運(yùn)行，而不必關(guān)心底層操作系統(tǒng)的細(xì)節(jié)。盡管這種解釋執(zhí)行方式可能導(dǎo)致Java程序的執(zhí)行速度比編譯型語言慢一些，但它確保了跨平臺的兼容性，使得Java成為一種廣泛應(yīng)用的編程語言。面向?qū)ο缶幊陶Z言JavaJava語言從源代碼到可執(zhí)行程序的過程面向?qū)ο缶幊陶Z言JavaJava語言的面向?qū)ο缶幊蘆ava是面向?qū)ο蟮某绦蛟O(shè)計(jì)語言，面向?qū)ο蟮幕舅枷胧鞘褂脤ο?、類、方法、接口、消息、繼承、多態(tài)等基本概念進(jìn)行程序設(shè)計(jì)。對象（Object）是對程序中事物的描述，世間萬事萬物都是對象，對象是個(gè)體，如張三這名同學(xué)、你在淘寶網(wǎng)的一個(gè)訂單等。類（Class）是具有共同屬性和行為的一組對象的描述，任何對象都隸屬于某個(gè)類。使用類生成對象的過程稱為實(shí)例化。屬性是用來描述對象靜態(tài)特征的一組數(shù)據(jù)。例如，學(xué)生的姓名、學(xué)號、性別、專業(yè)等。方法是對對象動(dòng)態(tài)特征（行為）的描述。每一個(gè)方法能確定對象的一種行為或功能。例如，汽車的行駛、轉(zhuǎn)彎、停車等動(dòng)作，可分別用move()、rotate()、stop()等方法來描述。Java程序設(shè)計(jì)從類開始，類的程序結(jié)構(gòu)由類說明和類體兩部分組成。類說明部分由關(guān)鍵字class與類名組成；類體是類聲明中花括號所包括的全部內(nèi)容，它由數(shù)據(jù)字段（屬性）和方法（函數(shù)）兩部分組成。數(shù)據(jù)字段描述對象的屬性，方法描述對象的行為，每一個(gè)方法能確定一個(gè)功能或操作。面向?qū)ο缶幊陶Z言JavaJava程序示例動(dòng)態(tài)程序設(shè)計(jì)語言PythonPython簡介Python是一種具有動(dòng)態(tài)語義和面向?qū)ο蟮拈_源程序設(shè)計(jì)語言。它可以在Windows、Linux、Android等系統(tǒng)中使用，并可以實(shí)現(xiàn)Python與C/C++、Java、.Net等開發(fā)平臺的混合編程，因此程序員有時(shí)會把Python稱為“膠水語言”。Python的創(chuàng)始人是荷蘭人吉多·范羅蘇姆（GuidovanRossum）。Python是一種代表簡單主義思想的編程語言，具備高度的可讀性。Python不再有指針等復(fù)雜的數(shù)據(jù)類型，而且簡化了面向?qū)ο蟮膶?shí)現(xiàn)方法。Python提供了豐富的API和工具，以便程序員能夠使用C/C++語言、Java來編寫擴(kuò)充模塊。Python擁有豐富的軟件包。Python提供了功能豐富的標(biāo)準(zhǔn)庫。動(dòng)態(tài)程序設(shè)計(jì)語言PythonPython基本元素Python程序有時(shí)稱為腳本，是一系列定義和命令，通常稱為語句，用來指示解釋器做一些事情。Python解釋器用于解釋和執(zhí)行Python語句和程序，Python解釋器是解釋Python腳本執(zhí)行的程序。語句print('hello,world!')指示解釋器調(diào)用print函數(shù)，輸出字符串hello,world!。對象是Python程序處理的核心元素。每個(gè)對象都有類型，其定義了程序能夠在這個(gè)對象上做的操作。Python主要對象類型如下表所示：對象類型說明描述例子str字符由字符組成的不可修改元素'hello,world!'bytes字節(jié)由字節(jié)組成的不可修改元素b'hello'list列表包含多種類型的可修改的元素，類似于數(shù)組[4.0,'string',True]tuple元組包含多種類型的不可修改的元素，類似于記錄(4.0,'string',True)set集合一個(gè)無序且不重復(fù)的元素集合{4.0,'stri