數(shù)據(jù)結(jié)構(gòu)第1章課件

1、第1章 緒論24 七月 2022課程簡(jiǎn)介 數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)的一門專業(yè)基礎(chǔ)課程，很多后續(xù)課程都要用到本課程所涉及的知識(shí)。例如，程序設(shè)計(jì)、編譯技術(shù)和操作系統(tǒng)等課程都要使用一些基本的數(shù)據(jù)結(jié)構(gòu)及其相關(guān)的算法；本課程討論的其他一些數(shù)據(jù)結(jié)構(gòu)，如廣義表、集合以及圖等也是很多應(yīng)用領(lǐng)域經(jīng)常涉及的。本課程的目的是介紹一些最常用的數(shù)據(jù)結(jié)構(gòu)，闡明數(shù)據(jù)結(jié)構(gòu)內(nèi)在的邏輯關(guān)系，討論它們?cè)谟?jì)算機(jī)中的存儲(chǔ)表示，并結(jié)合各種數(shù)據(jù)結(jié)構(gòu)，討論其各種操作的實(shí)現(xiàn)算法。24 七月 2022本章概述 本章將概括地介紹一些基本概念和術(shù)語，包括數(shù)據(jù)和數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)類型、算法的概念及描述、算法的復(fù)雜度分析等。24 七月

2、20221.1 引言 計(jì)算機(jī)應(yīng)用廣泛，加工處理的對(duì)象也在發(fā)展： 由純粹的數(shù)值數(shù)據(jù)發(fā)展到字符、表格和圖像等各種具有一定結(jié)構(gòu)的數(shù)據(jù)。 為了設(shè)計(jì)出一個(gè)“好”的程序，必須分析待處理的對(duì)象的特性以及各對(duì)象之間存在的關(guān)系，這就是數(shù)據(jù)結(jié)構(gòu)這門學(xué)科形成和發(fā)展的背景。24 七月 2022 用計(jì)算機(jī)解決一個(gè)具體問題時(shí)，一般需要經(jīng)過以下幾個(gè)步驟： 首先分析實(shí)際問題并從中抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型，然后設(shè)計(jì)一個(gè)解決此數(shù)學(xué)模型的算法，最后編制出程序上機(jī)調(diào)試，直至得到最終的解答，其過程如圖所示。24 七月 2022 尋求數(shù)學(xué)模型的實(shí)質(zhì)是分析問題，從中提取操作的對(duì)象，并找出這些操作對(duì)象之間的關(guān)系，然后使用數(shù)學(xué)模型加以描述。

3、數(shù)值計(jì)算問題的數(shù)學(xué)模型一般可用數(shù)學(xué)方程或數(shù)學(xué)公式來描述，而更多的非數(shù)值計(jì)算問題無法用數(shù)學(xué)方程加以描述。下面給出幾個(gè)例子。24 七月 2022 【例1-1】某單位職工檔案管理問題。為了簡(jiǎn)單，假定每個(gè)職工的檔案只包括以下5項(xiàng)：職工號(hào)、姓名、性別、出生日期和職稱。一般來說，檔案管理人員很可能將這些檔案組織成表格形式，如表所示，表中的每一行反映了一個(gè)職工的基本情況。24 七月 2022 本問題中的處理要求包括所有能用計(jì)算機(jī)完成的檔案管理工作，至少應(yīng)包含以下功能：(1)查找，需要時(shí)在表格中找出某人的檔案。(2)讀取，閱讀通過查找找到的檔案。(3)插入，調(diào)入新職工時(shí)將該職工的檔案加入表格中。(4)刪除，某

4、職工調(diào)離時(shí)，從表格中撤銷其檔案。(5)更新，某職工情況變化（如晉升職稱）時(shí)，修改檔案的有關(guān)內(nèi)容。24 七月 2022 上述每一項(xiàng)功能又可稱為一個(gè)“運(yùn)算”。由此，從職工檔案管理問題抽象出來的數(shù)學(xué)模型便包含職工檔案表和對(duì)此表進(jìn)行的各種運(yùn)算。在這類管理問題的數(shù)學(xué)模型中，計(jì)算機(jī)處理的對(duì)象之間通常存在著一種最簡(jiǎn)單的線性關(guān)系，這類數(shù)學(xué)模型可稱為線性的數(shù)據(jù)結(jié)構(gòu)。諸如此類的還有電話自動(dòng)查號(hào)系統(tǒng)、排課系統(tǒng)、倉庫庫存管理系統(tǒng)等各種應(yīng)用系統(tǒng)。24 七月 2022 【例1-2】UNIX操作系統(tǒng)中文件系統(tǒng)的系統(tǒng)結(jié)構(gòu)圖。UNIX操作系統(tǒng)中文件系統(tǒng)的底層是根目錄，根目錄下包含bin、lib、user、etc等一級(jí)子目錄，而

5、bin目錄下又包含math、ds、sw等二級(jí)子目錄，user目錄下又包含yin、xie、tang等二級(jí)子目錄，yin目錄下有Linklist.c、Stack.c和Tree.c等若干個(gè)文件，如圖所示。24 七月 2022 如果將這些目錄和文件都畫在一張圖上，它們之間所呈現(xiàn)的是一種層次關(guān)系，從上到下按層進(jìn)行展開形成一棵倒長(zhǎng)的“樹”?！皹涓笔窍到y(tǒng)的根目錄，其他目錄和文件是這棵樹上的“樹葉”，從根結(jié)點(diǎn)到某個(gè)葉子結(jié)點(diǎn)經(jīng)過的路徑就是當(dāng)前文件的絕對(duì)路徑。由此可見，“樹”也可以是某些非數(shù)值計(jì)算問題的數(shù)學(xué)模型，它也是一種數(shù)據(jù)結(jié)構(gòu)。 “樹”狀結(jié)構(gòu)的模型在生活中接觸的也比較多，如國(guó)家行政區(qū)域規(guī)劃、書籍目錄等。24

6、 七月 2022 【例1-3】比賽編排問題。有6支球隊(duì)進(jìn)行足球比賽，分別用V1、V2、V3、V4、V5、V6表示這6支球隊(duì)，它們之間的比賽情況也可以用一個(gè)稱為“圖”的數(shù)據(jù)結(jié)構(gòu)來表示，圖中的每個(gè)頂點(diǎn)表示一個(gè)球隊(duì)，如果從頂點(diǎn)Vi到Vj之間存在有向邊，則表示球隊(duì)Vi戰(zhàn)勝球隊(duì)Vj，如V1隊(duì)?wèi)?zhàn)勝V2隊(duì)，V2隊(duì)?wèi)?zhàn)勝V3隊(duì)，V3隊(duì)?wèi)?zhàn)勝V5隊(duì)等，這種勝負(fù)情況可以用圖表示。24 七月 2022 由此可以看出，用點(diǎn)、點(diǎn)與點(diǎn)之間的線所構(gòu)成的圖也可以反映實(shí)際生產(chǎn)和生活中的某些特定對(duì)象之間的特定關(guān)系。諸如此類有鐵路交通圖、教學(xué)編排圖等。 綜合以上3個(gè)例子可見，描述非數(shù)值計(jì)算問題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而是諸如表、樹、

7、圖之類的數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算。 因此可以說，數(shù)據(jù)結(jié)構(gòu)課程主要是研究非數(shù)值性程序設(shè)計(jì)中所出現(xiàn)的計(jì)算機(jī)操作對(duì)象以及它們之間的關(guān)系和運(yùn)算等的學(xué)科。24 七月 2022 在美國(guó)，數(shù)據(jù)結(jié)構(gòu)作為一門獨(dú)立的課程開始于1968年。當(dāng)時(shí)，數(shù)據(jù)結(jié)構(gòu)幾乎和圖論，特別是表、樹的理論為同義語。 數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)學(xué)科中起著承上啟下的作用，在計(jì)算機(jī)技術(shù)的各個(gè)領(lǐng)域也有著廣泛的應(yīng)用。 學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的目的是了解計(jì)算機(jī)處理對(duì)象的特性，將實(shí)際問題中所涉及的處理對(duì)象在計(jì)算機(jī)中表示出來并對(duì)它們進(jìn)行處理。24 七月 20221.2 基本術(shù)語 數(shù)據(jù)(data)：數(shù)據(jù)是客觀事物的符號(hào)表示，在計(jì)算機(jī)科學(xué)中是指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的

8、符號(hào)的總稱。 數(shù)據(jù)元素(data element)：數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在計(jì)算機(jī)程序中通常把它作為一個(gè)整體來處理。1.2.1 數(shù)據(jù)及相關(guān)概念24 七月 2022 例如，【例1-2】中的文件系統(tǒng)的系統(tǒng)結(jié)構(gòu)圖的一個(gè)目錄，【例1-3】中的“圖”的一個(gè)圓圈都被稱為一個(gè)數(shù)據(jù)元素。有時(shí)，一個(gè)數(shù)據(jù)元素又可以由若干個(gè)數(shù)據(jù)項(xiàng)(data item)組成。如表下所示學(xué)生成績(jī)表中的一條記錄為一個(gè)數(shù)據(jù)元素，而記錄中的學(xué)號(hào)、姓名、語文等都分別為一個(gè)數(shù)據(jù)項(xiàng)。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。數(shù)據(jù)元素也可以僅有一個(gè)數(shù)據(jù)項(xiàng)。24 七月 2022 數(shù)據(jù)對(duì)象(data object)：數(shù)據(jù)對(duì)象是性質(zhì)相同的數(shù)據(jù)元素組成的集合，

9、是數(shù)據(jù)的一個(gè)子集。數(shù)據(jù)元素是數(shù)據(jù)對(duì)象的數(shù)據(jù)成員。例如，正整數(shù)的數(shù)據(jù)對(duì)象是集合N=1,2,3,4,，字母字符數(shù)據(jù)對(duì)象是集合N=A,B,C,Z。 數(shù)據(jù)結(jié)構(gòu)(data structure)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)。24 七月 2022 邏輯結(jié)構(gòu)的4種形式(1)集合：數(shù)據(jù)元素間為松散的關(guān)系。在集合結(jié)構(gòu)中各元素之間，除了“同屬于某一個(gè)數(shù)據(jù)對(duì)象”的關(guān)系外，再無其他的關(guān)系，如圖(a)所示。1.2.2 數(shù)據(jù)的邏輯結(jié)構(gòu)24 七月 2022(2)線性結(jié)構(gòu)：數(shù)據(jù)元素間為嚴(yán)格的一對(duì)一關(guān)系，除第一個(gè)元素外，其他元素只有一個(gè)前驅(qū)，除最后一個(gè)元素外，其他元素只

10、有一個(gè)后繼，如圖(b)所示。(3)樹狀結(jié)構(gòu)：數(shù)據(jù)元素之間為嚴(yán)格的一對(duì)多的關(guān)系，即一個(gè)元素只有一個(gè)前驅(qū)，但可以有多個(gè)后繼，如圖(c)所示。(4)圖狀結(jié)構(gòu)：數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系，也就是說元素間的邏輯關(guān)系可以是任意的。圖狀結(jié)構(gòu)如圖(d)所示。24 七月 2022簡(jiǎn)單地說，數(shù)據(jù)結(jié)構(gòu)就是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)可以用二元組來進(jìn)行數(shù)學(xué)意義上的形式定義：Data_Structure=(D，R) 其中，D是數(shù)據(jù)元素的有限集，即數(shù)據(jù)對(duì)象；R是D中所有數(shù)據(jù)元素之間的關(guān)系的有限集。24 七月 2022 【例1-4】為畢業(yè)設(shè)計(jì)小組設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)。假設(shè)每個(gè)小組的關(guān)系是1名教師指導(dǎo)110名學(xué)生，則數(shù)據(jù)

11、結(jié)構(gòu)的二元組表示如下：Group=(P,R) 其中，P=T,G1,Gn,1n10； R=|1in,1n10。上述數(shù)據(jù)結(jié)構(gòu)的定義是一種數(shù)學(xué)意義上的定義。“數(shù)據(jù)結(jié)構(gòu)”定義中的“關(guān)系”是指數(shù)據(jù)間的邏輯關(guān)系，故也稱數(shù)據(jù)結(jié)構(gòu)為邏輯結(jié)構(gòu)。24 七月 2022 可將集合、樹狀結(jié)構(gòu)、圖狀結(jié)構(gòu)歸納為非線性結(jié)構(gòu)。因此，數(shù)據(jù)的邏輯結(jié)構(gòu)可分為兩大類，即線性結(jié)構(gòu)和非線性結(jié)構(gòu)。 然而，討論數(shù)據(jù)結(jié)構(gòu)的目的是在計(jì)算機(jī)中實(shí)現(xiàn)對(duì)它的操作，因此還需研究如何在計(jì)算機(jī)中表示它，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，又稱物理結(jié)構(gòu)。24 七月 2022 數(shù)據(jù)的邏輯結(jié)構(gòu)：指根據(jù)實(shí)際問題的需要而選擇設(shè)計(jì)，面向問題與計(jì)算機(jī)本身無關(guān)，是不依賴于機(jī)器的。 數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)

12、：指數(shù)據(jù)在計(jì)算機(jī)中的物理表示和存儲(chǔ)的方式。涉及數(shù)據(jù)元素及其關(guān)系在存儲(chǔ)器中的物理位置、機(jī)器響應(yīng)的速度等方面的因素，物理結(jié)構(gòu)的設(shè)計(jì)與計(jì)算機(jī)密切相關(guān)。1.2.3 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)24 七月 2022 計(jì)算機(jī)中存儲(chǔ)信息的最小單位叫做位(bit)，8位可表示一個(gè)字節(jié)(byte)，兩個(gè)字節(jié)稱為一個(gè)字(word)，字節(jié)、字或更多的二進(jìn)制位可稱為位串，這個(gè)位串稱為元素(element)或結(jié)點(diǎn)(node)。當(dāng)數(shù)據(jù)元素由若干個(gè)數(shù)據(jù)項(xiàng)組成時(shí)，則位串中對(duì)應(yīng)于每個(gè)數(shù)據(jù)項(xiàng)的子位串稱為數(shù)據(jù)域(data field)。24 七月 2022 線性表的邏輯結(jié)構(gòu)是：除第一個(gè)元素外，其他元素只有一個(gè)前驅(qū)，除最后一個(gè)元素外，其他元素只有

13、一個(gè)后繼。 線性表在計(jì)算機(jī)中的表示和存儲(chǔ)有兩種方式： 用連續(xù)的存儲(chǔ)單元存儲(chǔ)； 用分散的存儲(chǔ)單元存儲(chǔ)，并用指針將其連接。24 七月 2022 數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中有兩種不同的存儲(chǔ)方法： 順序存儲(chǔ) 鏈?zhǔn)酱鎯?chǔ)。 順序存儲(chǔ)：把數(shù)據(jù)元素依次存儲(chǔ)在一組地址連續(xù)的存儲(chǔ)單元中，元素間的邏輯關(guān)系由存儲(chǔ)單元的位置直接體現(xiàn)，由此得到的存儲(chǔ)表示稱為順序存儲(chǔ)。24 七月 2022順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是所有元素存放在一片連續(xù)的存儲(chǔ)單元中，邏輯結(jié)構(gòu)上相鄰的元素存放到計(jì)算機(jī)內(nèi)后仍然相鄰，如圖所示。24 七月 2022 鏈?zhǔn)酱鎯?chǔ)：將數(shù)據(jù)元素存儲(chǔ)在一組任意的存儲(chǔ)單元中，而用附加的指針(pointer)表示元素之間的邏輯關(guān)系

14、，由此得到的存儲(chǔ)表示稱為鏈?zhǔn)酱鎯?chǔ)。 存儲(chǔ)結(jié)構(gòu)的每個(gè)結(jié)點(diǎn)都由兩部分組成：數(shù)據(jù)域和指針域。其中,數(shù)據(jù)域存放元素本身的數(shù)據(jù)，指針域存放指針，如圖所示。24 七月 2022 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是所有元素可以存放在不連續(xù)的存儲(chǔ)單元中，元素之間的關(guān)系可以通過地址確定，邏輯結(jié)構(gòu)上相鄰的元素存放到計(jì)算機(jī)內(nèi)后不一定是相鄰的。 數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)是密不可分的兩個(gè)方面，任何一種算法的設(shè)計(jì)都取決于選定的數(shù)據(jù)的邏輯結(jié)構(gòu)，而算法的實(shí)現(xiàn)則依賴于所采用的存儲(chǔ)結(jié)構(gòu)。24 七月 2022 1.數(shù)據(jù)類型 數(shù)據(jù)類型(data type)是一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總稱。按“值”是否可分解，把數(shù)據(jù)類型分為兩類：

15、(1)原子類型：每一對(duì)象僅由單值構(gòu)成的類型，其值不可分解。 (2)結(jié)構(gòu)類型：每一對(duì)象可由若干成分按某種結(jié)構(gòu)構(gòu)成，其值可分成若干成分(或稱分量)。1.2.4 數(shù)據(jù)類型24 七月 2022 某種意義上，數(shù)據(jù)結(jié)構(gòu)可以看成一組具有相同結(jié)構(gòu)的值，而數(shù)據(jù)類型可以看成由一種數(shù)據(jù)結(jié)構(gòu)和定義在其上的一組操作組成。 2抽象數(shù)據(jù)類型 抽象數(shù)據(jù)類型(abstract data type，ADT)是指一個(gè)數(shù)學(xué)模型及定義在該模型上的一組操作。 抽象數(shù)據(jù)類型不僅包括數(shù)據(jù)類型的定義，而且為這個(gè)新類型指明了一個(gè)有效的操作集合。24 七月 2022 抽象強(qiáng)調(diào)數(shù)據(jù)類型的數(shù)學(xué)特性，而不管它們?cè)诓煌幚砥魃系膶?shí)現(xiàn)方法和細(xì)節(jié)。 抽象數(shù)據(jù)

16、類型和數(shù)據(jù)類型實(shí)質(zhì)上是同一個(gè)概念。 抽象數(shù)據(jù)類型的范疇更廣。 線性表是一個(gè)抽象數(shù)據(jù)類型。 把一個(gè)數(shù)據(jù)結(jié)構(gòu)以及定義在其上的一組操作封裝起來，使之成為一個(gè)抽象數(shù)據(jù)類型，則可以提高它們的復(fù)用率。24 七月 2022 抽象數(shù)據(jù)類型一般可以由數(shù)據(jù)對(duì)象、數(shù)據(jù)關(guān)系及基本操作3個(gè)要素來定義。 抽象數(shù)據(jù)類型可用以下三元組表示：ADT=(D，S，P) 其中，D是數(shù)據(jù)對(duì)象，用數(shù)據(jù)元素的有限集合表示；S是D上的關(guān)系集，用結(jié)點(diǎn)間序偶的集合表示；P是對(duì)D的基本操作集。24 七月 2022 根據(jù)上述定義，可用以下格式定義抽象數(shù)據(jù)類型：ADT 抽象數(shù)據(jù)類型名數(shù)據(jù)對(duì)象：數(shù)據(jù)關(guān)系：基本操作：ADT抽象數(shù)據(jù)類型名24 七月 202

17、2 其中，數(shù)據(jù)對(duì)象和數(shù)據(jù)關(guān)系的定義用偽代碼描述；基本操作的定義格式為：基本操作名（參數(shù)表）初始條件：操作結(jié)果： 基本操作有兩種參數(shù)：賦值參數(shù)為操作提供輸入值；引入?yún)?shù)以開始，除了提供輸入值外，還可以返回操作結(jié)果。24 七月 2022 “初始條件”說明了操作之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回錯(cuò)誤信息。 “操作結(jié)果”說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化情況和應(yīng)返回的結(jié)果。24 七月 2022 【例1-5】使用三元組定義描述抽象數(shù)據(jù)類型棧。ADT Stack 數(shù)據(jù)對(duì)象：棧的數(shù)據(jù)對(duì)象是一個(gè)數(shù)據(jù)元素序列a1,a2,an(n0),其中，數(shù)據(jù)元素ai屬于用戶自定義的數(shù)據(jù)類型。 數(shù)

18、據(jù)關(guān)系：棧是一種特殊的線性表，因此其數(shù)據(jù)元素也是一一對(duì)應(yīng)關(guān)系，并且約定an端為棧頂，a1端為棧底。 基本操作： InitStack(&S) 初始條件：棧S不存在。 操作結(jié)果：構(gòu)造一個(gè)空棧S。24 七月 2022DestoryStack(&S)初始條件：棧S已存在。操作結(jié)果：棧S被銷毀。StackEmpty(S)初始條件：棧S已存在。操作結(jié)果：若棧S為空，則返回TRUE,否則返回FALSE。StackLength(S)初始條件：棧S已存在。操作結(jié)果：返回S的元素個(gè)數(shù)，即棧的長(zhǎng)度。GetTop（S，&e）初始條件：棧S已存在且非空。操作結(jié)果：用e返回S的棧頂元素。24 七月 2022ClearSt

19、ack(&S)初始條件：棧S已存在。操作結(jié)果：將S清為空棧。Push(&S,e)初始條件：棧S存在。操作結(jié)果：插入元素e為新的棧頂元素。Pop（&S，&e）初始條件：棧S已存在且非空。操作結(jié)果：刪除S的棧頂元素，并用e返回其值。ADT Stack24 七月 20221.3 算法分析 1算法 算法(algorithm)是對(duì)特定問題求解步驟的描述，是指令的有限序列，其中每條指令表示一個(gè)或多個(gè)操作。 一個(gè)算法需具備下列5個(gè)重要特性： (1)有窮性：一個(gè)算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都可在有窮時(shí)間內(nèi)完成。1.3.1 算法的概念及描述24 七月 2022 (2)確定性：算法中的每條指令的含義

20、都必須明確，無二義性。在任何情況下，對(duì)于相同的輸入，必須能得出相同的輸出。 (3)可行性：算法是可行的，即算法中描述的操作均可通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算的有限次執(zhí)行來實(shí)現(xiàn)。 (4)輸入：一個(gè)算法有零個(gè)或者多個(gè)輸入，這些輸入取自于某個(gè)特定的對(duì)象的集合。 (5)輸出：一個(gè)算法至少有一個(gè)輸出，這些輸出是同輸入有著某些特定關(guān)系的量。沒有輸出的算法是沒有意義的。24 七月 2022 2算法的描述 借助各種工具來描述算法，通常有以下幾種描述工具： 自然語言 流程圖 形式化語言 具體的程序設(shè)計(jì)語言。 本書采用的描述工具是類C語言，以下對(duì)其作簡(jiǎn)要說明：24 七月 2022(1)預(yù)定義常量和類型： 函數(shù)結(jié)果狀態(tài)代碼

21、#defineTRUE 1#defineFALSE 0#defineOK 1#defineERROR 0#defineOVERFLOW-2 Status是函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼typedef int Status;24 七月 2022 (2)數(shù)據(jù)結(jié)構(gòu)的表示（存儲(chǔ)結(jié)構(gòu)）用類型定義(typedef)描述。數(shù)據(jù)元素類型約定為 ElemType，由用戶在使用該數(shù)據(jù)類型時(shí)自行定義。 (3)基本操作的算法都用以下形式的函數(shù)描述：函數(shù)類型 函數(shù)名（函數(shù)參數(shù)表） 算法說明語句序列 函數(shù)名24 七月 2022 常用a、b、c、d、e等用作數(shù)據(jù)元素名。 常用i、j、k、l、m、n等用作整型變量名， 常

22、用p、q、r等用作指針變量名。 當(dāng)函數(shù)返回值為函數(shù)結(jié)果狀態(tài)代碼時(shí)，函數(shù)定義為Status類型。 除了值調(diào)用方式外，增添了C+語言的引用調(diào)用的參數(shù)傳遞方式。24 七月 2022(4)賦值語句有：簡(jiǎn)單賦值語句：變量名=表達(dá)式；串聯(lián)賦值語句：變量名1=變量名2=變量名k=表達(dá)式；成組賦值語句：(變量名1，變量名k)=(表達(dá)式1，表達(dá)式k)；結(jié)構(gòu)名=結(jié)構(gòu)名；結(jié)構(gòu)名=(值1，值k)；變量名=表達(dá)式；變量名起始下標(biāo)終止下標(biāo)=變量名起始下標(biāo)終止下標(biāo)；24 七月 2022交換賦值語句：變量名變量名；條件賦值語句：變量名=條件表達(dá)式?表達(dá)式T：表達(dá)式F；(5)選擇語句有：條件語句1：if(表達(dá)式) 語句；條件語

23、句2：if(表達(dá)式) 語句； else語句；24 七月 2022 開關(guān)語句：switch(表達(dá)式)case值1：語句序列1；break；case值n：語句序列n；break；default：語句序列n+1； (6)循環(huán)語句有： for語句：for(賦初值表達(dá)式序列；條件；修改表達(dá)式序列) 語句；24 七月 2022while語句：while(條件)語句；dowhile語句：do語句序列； while(條件)；(7)結(jié)束語句有：函數(shù)結(jié)束語句：return表達(dá)式； return；case結(jié)束語句：break；異常結(jié)束語句：exit(異常代碼)；24 七月 2022(8)輸入和輸出語句有：輸入語句：

24、scanf(格式串，變量1，變量n)；輸出語句：printf(格式串，表達(dá)式1，表達(dá)式n)；(9)注釋：?jiǎn)涡凶⑨專?文字序列(10)基本函數(shù)有：求最大值：max(表達(dá)式1，表達(dá)式n)24 七月 2022求最小值：min(表達(dá)式1，表達(dá)式n)求絕對(duì)值：abs(表達(dá)式)文件結(jié)束：eof(文件變量)或eof行結(jié)束：eoln(文件變量)或eoln(11)邏輯運(yùn)算約定：與運(yùn)算&：對(duì)于A&B，當(dāng)A的值為0時(shí)，不再對(duì)B求值。或運(yùn)算：對(duì)于AB，當(dāng)A的值為非0時(shí)，不再對(duì)B求值。24 七月 2022【例1-6】計(jì)算兩數(shù)中的較大數(shù)，可以用類C語言描述。Status max(int a,int b)if(a=b) r

25、eturn(a);return(b);void main()int a=3,b=4,c;c=max(a,b);printf(The Max is %d,c);24 七月 2022 度量一個(gè)程序的執(zhí)行時(shí)間通常有兩種方法： (1)事前分析估算法：用數(shù)學(xué)方法直接對(duì)算法的效率進(jìn)行分析。要考慮以下因素： 問題的規(guī)模 編寫程序時(shí)所用的程序設(shè)計(jì)語言 機(jī)器的速度 算法所用的策略。1.3.2 算法的復(fù)雜度分析1算法的時(shí)間復(fù)雜度24 七月 2022 (2)事后統(tǒng)計(jì)法：計(jì)算機(jī)內(nèi)部均設(shè)有計(jì)時(shí)功能，可設(shè)計(jì)一組或若干組測(cè)試數(shù)據(jù)，然后分別運(yùn)行根據(jù)不同的算法編制的程序，并比較這些程序的實(shí)際運(yùn)行時(shí)間，從而確定算法的優(yōu)劣。這種方

26、法有兩個(gè)缺陷： 必須先運(yùn)行根據(jù)算法編制的程序，這通常比較麻煩； 這種方法得出的結(jié)果往往對(duì)計(jì)算機(jī)的硬件、軟件環(huán)境依賴性較強(qiáng)，有時(shí)容易掩蓋算法本身的優(yōu)劣。24 七月 2022 編譯程序時(shí)所產(chǎn)生的機(jī)器代碼的質(zhì)量也會(huì)對(duì)執(zhí)行效率產(chǎn)生影響。 算法由控制結(jié)構(gòu)和原操作構(gòu)成，其執(zhí)行的時(shí)間取決于兩者的綜合效果。 為了客觀地比較同一問題的不同算法的優(yōu)劣，通常從算法中選取一種對(duì)于所研究的問題來說是基本運(yùn)算的原操作，用該原操作執(zhí)行的次數(shù)作為算法的時(shí)間度量。24 七月 2022 一般情況下，算法中基本原操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個(gè)函數(shù)f(n)，因而算法的時(shí)間復(fù)雜度記作：T(n)=O(f(n) 當(dāng)問題的規(guī)模n增大時(shí)

27、，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，稱為算法的漸近時(shí)間復(fù)雜度(asymptotic time complexity)，簡(jiǎn)稱時(shí)間復(fù)雜度。24 七月 2022 當(dāng)T(n)與數(shù)據(jù)個(gè)數(shù)n無關(guān)時(shí)，T(n)=O(1)，稱為常量階； 當(dāng)T(n)與數(shù)據(jù)個(gè)數(shù)n為線性關(guān)系時(shí)，T(n)=O(n)，稱為線性階； 當(dāng)T(n)與數(shù)據(jù)個(gè)數(shù)n為平方關(guān)系時(shí)，算法的時(shí)間復(fù)雜度T(n)=O(n2)，稱為平方階。 算法還可能呈現(xiàn)的時(shí)間復(fù)雜度為對(duì)數(shù)階O(log n)、指數(shù)階O(2n)等。24 七月 2022 分析一個(gè)算法中基本語句執(zhí)行次數(shù)與數(shù)據(jù)個(gè)數(shù)n的函數(shù)關(guān)系，就可求出該算法的時(shí)間復(fù)雜度。通常把基本語句重復(fù)執(zhí)行的次數(shù)稱為語句

28、的頻度。例如，在下列3個(gè)程序段中：+x;sum=0;for(i=1;i=n;+i)+x;sum+=x;for(j=1;j=n;+j) for(k=1;k=n;+k)+x;sum+=x;24 七月 2022 含基本操作“x增1”的語句的頻度分別為1、n和n2，則這3個(gè)程序段的時(shí)間復(fù)雜度分別為O(1)、O(n)和O(n2)。下面看兩個(gè)例子?！纠?-7】求兩個(gè)n階方陣的乘積C=A*B的算法。#define n 10void MultiMatrix(int Ann,int Bnn,int Cnn)for(i=0;in;i+) for(j=0;jn;j+)Cij=0;for(k=0;k1 & chang

29、e;-i) change=FALSE; for(j=0;jaj+1)ajaj+1;change=TRUE;24 七月 2022 其算法思想是： 從a0起依次比較相鄰兩個(gè)數(shù)aj和aj+1(j=0，1，n-2)，若前一個(gè)數(shù)比后一個(gè)數(shù)大，則兩者相互交換位置，如此從前往后檢查一遍，必然將其中值最大的數(shù)交換到an-1的位置上。 之后對(duì)a0.n-2進(jìn)行同樣操作，直至所檢查的區(qū)間長(zhǎng)度到1為止。24 七月 2022 當(dāng)a中初始序列為自小至大有序時(shí)，基本操作的執(zhí)行次數(shù)為0； 當(dāng)初始序列為自大至小有序時(shí)，基本操作的執(zhí)行次數(shù)為n(n-1)/2。 這種情況下算法的時(shí)間復(fù)雜度除了依賴于所要解決的問題的規(guī)模外，還與問題的

30、實(shí)際輸入情況有關(guān)。24 七月 2022 分析此類算法，一種解決的辦法是計(jì)算它的平均值，此時(shí)相應(yīng)的時(shí)間復(fù)雜度為算法的平均時(shí)間復(fù)雜度。 另一種更可行也更常用的辦法是討論算法在最壞情況下的時(shí)間復(fù)雜度，在本書以后各章中討論的時(shí)間復(fù)雜度，除特別指明外，均指最壞情況下的時(shí)間復(fù)雜度。24 七月 2022 最壞情況下該算法的時(shí)間復(fù)雜度分析如下。 設(shè)基本操作的頻度為f(n)，最壞情況下有：f(n)=n+4n2/2 所以該算法的最壞時(shí)間復(fù)雜度為T(n)=O(n2)。 實(shí)踐中可以把事前估算和事后統(tǒng)計(jì)兩種辦法結(jié)合起來使用。24 七月 2022 2算法的空間復(fù)雜度 空間復(fù)雜度(space complexity)作為算法

31、所需存儲(chǔ)空間的量度，記作:S(n)=O(f(n) 其中，n為問題的規(guī)模。 算法所需的存儲(chǔ)空間，通常不含輸入數(shù)據(jù)和程序本身所占的存儲(chǔ)空間，而是指算法對(duì)輸入數(shù)據(jù)進(jìn)行運(yùn)算所需的輔助工作單元和存儲(chǔ)實(shí)現(xiàn)計(jì)算所需信息的輔助性空間，這類空間也稱額外空間。24 七月 2022 算法的輸入數(shù)據(jù)所占的空間一般是由具體問題決定的，不會(huì)因算法不同而改變。 算法本身占用的空間不僅和算法有關(guān)，而且和編譯程序產(chǎn)生的目標(biāo)代碼的質(zhì)量有關(guān)，所以也難以計(jì)算。 算法所占的額外空間卻是與算法的質(zhì)量密切相關(guān)，好的算法既節(jié)省時(shí)間又節(jié)省額外空間。 有時(shí)，算法的輸入數(shù)據(jù)所占的空間不是由問題本身決定的，而是由算法決定的，在這種情況下，算法所需的

32、存儲(chǔ)空間應(yīng)包括輸入數(shù)據(jù)的存儲(chǔ)空間。24 七月 20221.3.3 算法的設(shè)計(jì)要求 計(jì)算機(jī)界公認(rèn)的著名公式： 程序=算法+數(shù)據(jù)結(jié)構(gòu)它由瑞士科學(xué)家Niklaus Wirth提出，從邏輯上描 述了算法與數(shù)據(jù)結(jié)構(gòu)和程序之間的關(guān)系。由此可見：選好了數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，如果沒有行之有效的算法，則不能對(duì)數(shù)據(jù)進(jìn)行操作，不能解決實(shí)際問題；同樣，沒有數(shù)據(jù)結(jié)構(gòu)，算法也無用武之地。24 七月 2022 一個(gè)好的算法通常應(yīng)注意以下方面：(1)正確性(correctness)：算法本身應(yīng)該沒有語法錯(cuò)誤，一個(gè)有語法錯(cuò)誤的程序是不能在計(jì)算機(jī)上運(yùn)行的。(2)可讀性(readability)：算法主要是為了人的閱讀與交流，

33、其次才是機(jī)器執(zhí)行。24 七月 2022(3)健壯性(robustness)：當(dāng)輸入數(shù)據(jù)非法或運(yùn)行環(huán)境改變時(shí)，算法也能作出快速、恰當(dāng)?shù)姆磻?yīng)，不會(huì)產(chǎn)生莫名其妙的輸出結(jié)果，同時(shí)，輸出一定的錯(cuò)誤提示，終止程序的執(zhí)行。 (4)效率與存儲(chǔ)量要求：算法的效率指的是算法的執(zhí)行時(shí)間。24 七月 20221.4 實(shí)例解析【例1-9】設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)：tree=(D,R)，其中：D=A,B,C,D,E,F,G,H,I,JR=,試分析該數(shù)據(jù)結(jié)構(gòu)屬于哪種邏輯結(jié)構(gòu)?24 七月 2022數(shù)據(jù)的樹狀結(jié)構(gòu)示意圖如圖所示。24 七月 2022數(shù)據(jù)的樹狀結(jié)構(gòu)示意圖像倒著畫的一棵樹，在這棵樹中，最上面的一個(gè)結(jié)點(diǎn)沒有前驅(qū)只有后繼，稱為

34、樹根結(jié)點(diǎn)，最下面一層的結(jié)點(diǎn)只有前驅(qū)沒有后繼，稱為樹葉結(jié)點(diǎn)。在一棵樹中，每個(gè)結(jié)點(diǎn)有且只有一個(gè)前驅(qū)結(jié)點(diǎn)(除樹根結(jié)點(diǎn)外)，但可以有任意多個(gè)后繼結(jié)點(diǎn)(樹葉結(jié)點(diǎn)可看做具有0個(gè)后繼結(jié)點(diǎn))。這種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)是數(shù)據(jù)元素之間為1對(duì)N關(guān)系(N0)，即層次關(guān)系，因此本題所給定的數(shù)據(jù)結(jié)構(gòu)為樹狀結(jié)構(gòu)。24 七月 2022 【例1-10】設(shè)一個(gè)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)如圖所示，寫出其二元組的描述。24 七月 2022本題所給定的數(shù)據(jù)結(jié)構(gòu)為圖狀結(jié)構(gòu)，其二元組的描述為：Graph=（D，R）其中， D=1,2,3,4 R=(1,2),(1,3),(1,4),(2,3),(2,4),(3,4) 注意：在【例1-9】中尖括號(hào)表示的是一條有向邊，在【例1-10】中圓括號(hào)(1,2)表示的是一條無向邊。24 七月 2022 【例1-11】設(shè)n為一個(gè)正整數(shù)，求下列各算法的時(shí)間復(fù)雜度。(1)