數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版本)課件

數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版本）

嚴(yán)蔚敏吳偉民

編著1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新

數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版本）12/28/2022華僑大1前言

二十一世紀(jì)是科學(xué)技術(shù)高速發(fā)展的信息時(shí)代，而計(jì)算機(jī)是處理信息的主要工具，因此，人們已經(jīng)認(rèn)識(shí)到，計(jì)算機(jī)知識(shí)已成為人類當(dāng)代文化的一個(gè)重要組成部分。計(jì)算機(jī)科學(xué)技術(shù)以驚人的速度向前發(fā)展，它的廣泛應(yīng)用已從傳統(tǒng)的數(shù)值計(jì)算領(lǐng)域發(fā)展到各種非數(shù)值計(jì)算領(lǐng)域。在非數(shù)值計(jì)算領(lǐng)域里，數(shù)據(jù)處理的對(duì)象已從簡(jiǎn)單的數(shù)值發(fā)展到一般的符號(hào)，進(jìn)而發(fā)展到具有一定結(jié)構(gòu)的數(shù)據(jù)。在這里，面臨的主要問題是：針對(duì)每一種新的應(yīng)用領(lǐng)域的處理對(duì)象，如何選擇合適的數(shù)據(jù)表示（結(jié)構(gòu)），如何有效地組織計(jì)算機(jī)存貯，并在此基礎(chǔ)上又如何有效地實(shí)現(xiàn)對(duì)象之間的“運(yùn)算”關(guān)系。傳統(tǒng)的解決數(shù)值計(jì)算的許多理論、方法和技術(shù)已不能滿足解決非數(shù)值計(jì)算問題的需要，必須進(jìn)行新的探索。數(shù)據(jù)結(jié)構(gòu)就是研究和解決這些問題的重要基礎(chǔ)理論。因此，“數(shù)據(jù)結(jié)構(gòu)”課程已成為計(jì)算機(jī)類專業(yè)的一門重要專業(yè)基礎(chǔ)課。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新前言12/28/2022華僑大學(xué)數(shù)學(xué)2第1章緒論[目的]介紹數(shù)據(jù)結(jié)構(gòu)中常用的基本概念和術(shù)語(yǔ)以及學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義。[要求]了解本章介紹的各種基本概念和術(shù)語(yǔ)，掌握算法描述和分析的方法。[重點(diǎn)]了解數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及數(shù)據(jù)的運(yùn)算三方面的概念及相互關(guān)系。[難點(diǎn)]算法復(fù)雜度的分析方法。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新第1章緒論[目的]介紹數(shù)據(jù)結(jié)構(gòu)中常用的基3

1.1引言

眾所周知，二十世紀(jì)四十年代，電子數(shù)字計(jì)算機(jī)問世的直接原因是解決彈道學(xué)的計(jì)算問題。早期，電子計(jì)算機(jī)的應(yīng)用范圍，幾乎只局限于科學(xué)和工程的計(jì)算，其處理的對(duì)象是純數(shù)值性的信息，通常，人們把這類問題稱為數(shù)值計(jì)算。近三十年來(lái)，電子計(jì)算機(jī)的發(fā)展異常迅猛，這不僅表現(xiàn)在計(jì)算機(jī)本身運(yùn)算速度不斷提高、信息存儲(chǔ)量日益擴(kuò)大、價(jià)格逐步下降，更重要的是計(jì)算機(jī)廣泛地應(yīng)用于情報(bào)檢索、企業(yè)管理、系統(tǒng)工程等方面，已遠(yuǎn)遠(yuǎn)超出了科技計(jì)算的范圍，而滲透到人類社會(huì)活動(dòng)的一切領(lǐng)域。與此相應(yīng)，計(jì)算機(jī)的處理對(duì)象也從簡(jiǎn)單的純數(shù)值性信息發(fā)展到非數(shù)值性的和具有一定結(jié)構(gòu)的信息。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新

1.1引言12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新4因此，再把電子數(shù)字計(jì)算機(jī)簡(jiǎn)單地看作是進(jìn)行數(shù)值計(jì)算的工具，把數(shù)據(jù)僅理解為純數(shù)值性的信息，就顯得太狹隘了?，F(xiàn)代計(jì)算機(jī)科學(xué)的觀點(diǎn)，是把計(jì)算機(jī)程序處理的一切數(shù)值的、非數(shù)值的信息，乃至程序統(tǒng)稱為數(shù)據(jù)（Data），而電子計(jì)算機(jī)則是加工處理數(shù)據(jù)（信息）的工具。由于數(shù)據(jù)的表示方法和組織形式直接關(guān)系到程序?qū)?shù)據(jù)的處理效率，而系統(tǒng)程序和許多應(yīng)用程序的規(guī)模很大，結(jié)構(gòu)相當(dāng)復(fù)雜，處理對(duì)象又多為非數(shù)值性數(shù)據(jù)。因此，單憑程序設(shè)計(jì)人員的經(jīng)驗(yàn)和技巧已難以設(shè)計(jì)出效率高、可靠性強(qiáng)的程序。于是，就要求人們對(duì)計(jì)算機(jī)程序加工的對(duì)象進(jìn)行系統(tǒng)的研究，即研究數(shù)據(jù)的特性以及數(shù)據(jù)之間存在的關(guān)系——數(shù)據(jù)結(jié)構(gòu)（DateStructure）。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新51.2數(shù)據(jù)結(jié)構(gòu)的發(fā)展簡(jiǎn)史及其在計(jì)算機(jī)科學(xué)中所處的地位發(fā)展史：1、“數(shù)據(jù)結(jié)構(gòu)”作為一門獨(dú)立的課程在國(guó)外是從1968年才開始設(shè)立的。2、1968年美國(guó)唐·歐·克努特教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的《計(jì)算機(jī)程序設(shè)計(jì)技巧》第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)及其操作的著作。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新1.2數(shù)據(jù)結(jié)構(gòu)的發(fā)展簡(jiǎn)史及其在計(jì)算機(jī)科學(xué)中所處的地位126地位：“數(shù)據(jù)結(jié)構(gòu)”在計(jì)算機(jī)科學(xué)中是一門綜合性的專業(yè)基礎(chǔ)課。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間的一門核心課程。數(shù)據(jù)結(jié)構(gòu)這一門課的內(nèi)容不僅是一般程序設(shè)計(jì)（特別是非數(shù)值性程序設(shè)計(jì)）的基礎(chǔ)，而且是設(shè)計(jì)和實(shí)現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫(kù)系統(tǒng)及其他系統(tǒng)程序的重要基礎(chǔ)。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新地位：12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新7

1.3什么是數(shù)據(jù)結(jié)構(gòu)

計(jì)算機(jī)解決一個(gè)具體問題時(shí)，大致需要經(jīng)過下列幾個(gè)步驟：首先要從具體問題中抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型，然后設(shè)計(jì)一個(gè)解此數(shù)學(xué)模型的算法（Algorithm），最后編出程序、進(jìn)行測(cè)試、調(diào)整直至得到最終解答。尋求數(shù)學(xué)模型的實(shí)質(zhì)是分析問題，從中提取操作的對(duì)象，并找出這些操作對(duì)象之間含有的關(guān)系，然后用數(shù)學(xué)的語(yǔ)言加以描述。計(jì)算機(jī)算法與數(shù)據(jù)的結(jié)構(gòu)密切相關(guān)，算法無(wú)不依附于具體的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)直接關(guān)系到算法的選擇和效率。運(yùn)算是由計(jì)算機(jī)來(lái)完成，這就要設(shè)計(jì)相應(yīng)的插入、刪除和修改的算法。也就是說(shuō)，數(shù)據(jù)結(jié)構(gòu)還需要給出每種結(jié)構(gòu)類型所定義的各種運(yùn)算的算法。直觀定義：數(shù)據(jù)結(jié)構(gòu)是研究程序設(shè)計(jì)中計(jì)算機(jī)操作的對(duì)象以及它們之間的關(guān)系和運(yùn)算的一門學(xué)科。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新

1.3什么是數(shù)據(jù)結(jié)構(gòu)

12/28/2022華僑大學(xué)數(shù)學(xué)81.4基本概念和術(shù)語(yǔ)

1．?dāng)?shù)據(jù)

數(shù)據(jù)是人們利用文字符號(hào)、數(shù)字符號(hào)以及其他規(guī)定的符號(hào)對(duì)現(xiàn)實(shí)世界的事物及其活動(dòng)所做的描述。在計(jì)算機(jī)科學(xué)中，數(shù)據(jù)的含義非常廣泛，我們把一切能夠輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的信息，包括文字、表格、圖象等，都稱為數(shù)據(jù)。例如，一個(gè)個(gè)人書庫(kù)管理程序所要處理的數(shù)據(jù)可能是一張如表1-1所示的表格。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新1.4基本概念和術(shù)語(yǔ)12/28/2022華僑大學(xué)數(shù)學(xué)系9

表1-1個(gè)人書庫(kù)1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新

102．結(jié)點(diǎn)結(jié)點(diǎn)也叫數(shù)據(jù)元素，它是組成數(shù)據(jù)的基本單位。在程序中通常把結(jié)點(diǎn)作為一個(gè)整體進(jìn)行考慮和處理。例如，在表1-1所示的個(gè)人書庫(kù)中，為了便于處理，把其中的每一行（代表一本書）作為一個(gè)基本單位來(lái)考慮，故該數(shù)據(jù)由10個(gè)結(jié)點(diǎn)構(gòu)成。一般情況下，一個(gè)結(jié)點(diǎn)中含有若干個(gè)字段（也叫數(shù)據(jù)項(xiàng)）。例如，在表1-1所示的表格數(shù)據(jù)中，每個(gè)結(jié)點(diǎn)都有登錄號(hào)、書號(hào)、書名、作者、出版社和價(jià)格等六個(gè)字段構(gòu)成。字段是構(gòu)成數(shù)據(jù)的最小單位。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新113．邏輯結(jié)構(gòu)結(jié)點(diǎn)和結(jié)點(diǎn)之間的邏輯關(guān)系稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。在表1-1所示的表格數(shù)據(jù)中，各結(jié)點(diǎn)之間在邏輯上有一種線性關(guān)系，它指出了10個(gè)結(jié)點(diǎn)在表中的排列順序。根據(jù)這種線性關(guān)系，可以看出表中第一本書是什么書，第二本書是什么書，等等。4．存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)表示稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。在表1-1所示的表格數(shù)據(jù)在計(jì)算機(jī)中可以有多種存儲(chǔ)表示，例如，可以表示成數(shù)組，存放在內(nèi)存中；也可以表示成文件，存放在磁盤上，等等。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新125．?dāng)?shù)據(jù)處理數(shù)據(jù)處理是指對(duì)數(shù)據(jù)進(jìn)行查找、插入、刪除、合并、排序、統(tǒng)計(jì)以及簡(jiǎn)單計(jì)算等的操作過程。在早期，計(jì)算機(jī)主要用于科學(xué)和工程計(jì)算，進(jìn)入八十年代以后，計(jì)算機(jī)主要用于數(shù)據(jù)處理。據(jù)有關(guān)統(tǒng)計(jì)資料表明，現(xiàn)在計(jì)算機(jī)用于數(shù)據(jù)處理的時(shí)間比例達(dá)到80%以上，隨著時(shí)間的推移和計(jì)算機(jī)應(yīng)用的進(jìn)一步普及，計(jì)算機(jī)用于數(shù)據(jù)處理的時(shí)間比例必將進(jìn)一步增大。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新136．?dāng)?shù)據(jù)結(jié)構(gòu)（DataStructure）數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)元素（DataElement）之間抽象化的相互關(guān)系和這種關(guān)系在計(jì)算機(jī)中的存儲(chǔ)表示（即所謂數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)），并對(duì)這種結(jié)構(gòu)定義相適應(yīng)的運(yùn)算，設(shè)計(jì)出相應(yīng)的算法，而且確保經(jīng)過這些運(yùn)算后所得到的新結(jié)構(gòu)仍然是原來(lái)的結(jié)構(gòu)類型。為了敘述上的方便和避免產(chǎn)生混淆，通常我們把數(shù)據(jù)的邏輯結(jié)構(gòu)統(tǒng)稱為數(shù)據(jù)結(jié)構(gòu)，把數(shù)據(jù)的物理結(jié)構(gòu)統(tǒng)稱為存儲(chǔ)結(jié)構(gòu)（StorageStructure）。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新6．?dāng)?shù)據(jù)結(jié)構(gòu)（DataStructure）12/28/2014四種基本基本結(jié)構(gòu)：（1）集合：結(jié)構(gòu)中的數(shù)據(jù)元素之間除了“同屬于一個(gè)集合”的關(guān)系外，別無(wú)其他關(guān)系。（2）線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個(gè)對(duì)一個(gè)的關(guān)系。如：圖書館的書目檢索系統(tǒng)（3）樹形結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素存在一個(gè)對(duì)多個(gè)的關(guān)系。如：計(jì)算機(jī)和人對(duì)奕問題工廠的組織管理（4）圖狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素存在多個(gè)對(duì)多個(gè)的關(guān)系。如：多叉路口的交通燈管理問題最短路徑問題

同一個(gè)邏輯結(jié)構(gòu)可以有不同的內(nèi)部存儲(chǔ)結(jié)構(gòu)；反之，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)一定要映像數(shù)據(jù)之間的邏輯關(guān)系。數(shù)據(jù)結(jié)構(gòu)的形式定義：數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組data_structure=(D,S)其中：D是數(shù)據(jù)元素的有限集，S是D上關(guān)系的有限集。

1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新四種基本基本結(jié)構(gòu)：12/28/2022華僑大學(xué)數(shù)學(xué)系黃建15例1一種結(jié)構(gòu)lineority=(K,R）K={k1,k2,k3,k4,k5,k6,k7}R={r}r={<k3,k1>,<k1,k5>,<k5,k6>,<k6,k4>,<k4,k2>,<k2,k7>}則有：k3->k1->k5->k6->k4->k2->k7一種線性結(jié)構(gòu)例2tree=(K,R)K={01,02,03,04,05,06,07,08}R={r}r={<01,02>,<01,03>,<02,04>,<02,05>,<03,06>,<03,07>,<07,08>}樹形結(jié)構(gòu)

1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新例1一種結(jié)構(gòu)lineority=(K,R）12/28/16例3graph=(K,R)K={01,02,03,04,05,06}R={r}r={<01,02>,<02,01>,<01,04>,<04,01>,<02,03>,<02,06>,<06,02>,<05,03>,<03,04>,<04,03>}圖形結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)分類：數(shù)據(jù)的邏輯結(jié)構(gòu)線性結(jié)構(gòu)非線性結(jié)構(gòu)線性表樹形結(jié)構(gòu)圖一般線性表特殊線性表線性表推廣樹二叉樹有向圖無(wú)向圖線性表?xiàng)ｊ?duì)列串?dāng)?shù)組廣義表

1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新例3graph=(K,R)12/28/2022華僑大17數(shù)據(jù)的物理結(jié)構(gòu)方面二種類型：順序存儲(chǔ)結(jié)構(gòu)和非順序存儲(chǔ)結(jié)構(gòu)

順序存儲(chǔ)結(jié)構(gòu)：邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理位置上相比鄰的存儲(chǔ)單元里，其關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)（向量、數(shù)組）。

非順序存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)元素在計(jì)算機(jī)內(nèi)任意位置上存放，其關(guān)系用指針來(lái)鏈接，稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)-鏈表。按指針個(gè)數(shù)分為：?jiǎn)捂湵?、雙向鏈表、多重鏈表

索引存儲(chǔ)結(jié)構(gòu)：按（地址關(guān)鍵字）的偶對(duì)集合，關(guān)鍵字是唯一標(biāo)識(shí)結(jié)點(diǎn)；地址指出該結(jié)點(diǎn)的存儲(chǔ)地址。

散列存儲(chǔ)結(jié)構(gòu)：根據(jù)結(jié)點(diǎn)關(guān)鍵字來(lái)直接算出該結(jié)點(diǎn)的存儲(chǔ)地址。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新數(shù)據(jù)的物理結(jié)構(gòu)方面12/28/2022華僑大學(xué)數(shù)學(xué)系187．?dāng)?shù)據(jù)類型數(shù)據(jù)類型是一個(gè)值的集合和定義在這個(gè)值上的一組操作的總稱。數(shù)據(jù)類型是高級(jí)程序設(shè)計(jì)語(yǔ)言中的一個(gè)基本概念，它和數(shù)據(jù)結(jié)構(gòu)的概念密切相關(guān)。一方面，在程序設(shè)計(jì)語(yǔ)言中，每一個(gè)數(shù)據(jù)都屬于某種數(shù)據(jù)類型。類型明顯或隱含地規(guī)定了數(shù)據(jù)的取值范圍、存儲(chǔ)方式以及允許進(jìn)行的運(yùn)算?？梢哉J(rèn)為，數(shù)據(jù)類型是在程序設(shè)計(jì)中已經(jīng)實(shí)現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)。另一方面，在程序設(shè)計(jì)過程中，當(dāng)需要引入某種新的數(shù)據(jù)結(jié)構(gòu)時(shí)，總是借助編程語(yǔ)言所提供的數(shù)據(jù)類型來(lái)描述數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新7．?dāng)?shù)據(jù)類型12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新19抽象數(shù)據(jù)類型（AbstractDataType,ADT)是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作，它僅取決于它的一組邏輯特性，而與其在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)無(wú)關(guān)。一個(gè)含抽象數(shù)據(jù)類型的軟件模塊通常應(yīng)包含定義、表示和實(shí)現(xiàn)三個(gè)部分。抽象數(shù)據(jù)類型的三元組表示(DSP),其中，D是數(shù)據(jù)對(duì)象，S是D上的關(guān)系集，P是對(duì)D的基本操作集。ADT抽象數(shù)據(jù)類型名{數(shù)據(jù)對(duì)象：<數(shù)據(jù)對(duì)象的定義>數(shù)據(jù)關(guān)系：<數(shù)據(jù)關(guān)系的定義>基本操作：<基本操作的定義>}ADT抽象數(shù)據(jù)類型名其中，數(shù)據(jù)對(duì)象和數(shù)據(jù)關(guān)系的定義用偽碼描述，基本操作的定義格式為：基本操作名（參數(shù)表）初始條件：<初始條件描述>操作結(jié)果：<操作結(jié)果描述>1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新抽象數(shù)據(jù)類型（AbstractData20基本操作有兩種參數(shù)：賦值參數(shù)只為操作提供輸入值；引用參數(shù)以&打頭，除可提供輸入值外，還將返回操作結(jié)果。例抽象數(shù)據(jù)類型三元組的定義：ADTTriplet{數(shù)據(jù)對(duì)象：D={e1,e2,e3|e1,e2,e3屬于Elemset}數(shù)據(jù)關(guān)系：R1={<e1,e2>,<e2,e3>}基本操作：InitTriplet(&T,v1,v2,v3)操作結(jié)果：構(gòu)造了三元組T,元素e1,e2,和e3分別被賦以參數(shù)v1,v2和v3的值。DestroyTriplet(&T)操作結(jié)果：三元組T被銷毀。Get（T,I,&e)初始條件：三元組T已存在，1<=I<=3操作結(jié)果：用e返回T的第I元的值。}1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新基本操作有兩種參數(shù)：賦值參數(shù)只為操作提供輸入值；引用參21

8．算法簡(jiǎn)單地說(shuō)就是解決特定問題的方法（關(guān)于算法的嚴(yán)格定義，在此不作討論）。特定的問題可以是數(shù)值的，也可以是非數(shù)值的。解決數(shù)值問題的算法叫做數(shù)值算法，科學(xué)和工程計(jì)算方面的算法都屬于數(shù)值算法，如求解數(shù)值積分，求解線性方程組、求解代數(shù)方程、求解微分方程等。解決非數(shù)值問題的算法叫做非數(shù)值算法，數(shù)據(jù)處理方面的算法都屬于非數(shù)值算法。例如各種排序算法、查找算法、插入算法、刪除算法、遍歷算法等。數(shù)值算法和非數(shù)值算法并沒有嚴(yán)格的區(qū)別。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新8．算法12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新22一般說(shuō)來(lái)，在數(shù)值算法中主要進(jìn)行算術(shù)運(yùn)算，而在非數(shù)值算法中主要進(jìn)行比較和邏輯運(yùn)算。另一方面，特定的問題可能是遞歸的，也可能是非遞歸的，因而解決它們的算法就有遞歸算法和非遞歸算法之分。從理論上講，任何遞歸算法都可以通過循環(huán)，堆棧等技術(shù)轉(zhuǎn)化為非遞歸算法。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新231.5算法和算法的描述

1.5.1算法算法是執(zhí)行特定計(jì)算的有窮過程。這個(gè)過程有5個(gè)特點(diǎn)：1.動(dòng)態(tài)有窮：當(dāng)執(zhí)行一個(gè)算法時(shí)，不論是何種情況，在經(jīng)過了有限步驟后，這個(gè)算法一定要終止。2.確定性：算法中的每條指令都必須是清楚的，指令無(wú)二義性。3.輸入：具有0個(gè)或0個(gè)以上由外界提供的量。4.輸出：產(chǎn)生1個(gè)或多個(gè)結(jié)果。5.可行性：每條指令都充分基本，原則上可由人僅用筆和紙?jiān)谟邢薜臅r(shí)間內(nèi)也能完成。

注意：算法和程序是有區(qū)別的，即程序未必能滿足動(dòng)態(tài)有窮。在本書中，我們只討論滿足動(dòng)態(tài)有窮的程序，因此“算法”和“程序”是通用的。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新1.5算法和算法的描述

1.5.1算法12/28/224

1.5.2算法的描述

一個(gè)算法可以用自然語(yǔ)言、數(shù)字語(yǔ)言或約定的符號(hào)來(lái)描述，也可以用計(jì)算機(jī)高級(jí)程序語(yǔ)言來(lái)描述，如Pascal語(yǔ)言、C語(yǔ)言或偽代碼等。本書選用C語(yǔ)言作為描述算法的工具?，F(xiàn)簡(jiǎn)單說(shuō)明C語(yǔ)言的語(yǔ)法結(jié)構(gòu)如下：1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新

1.5.2算法的描述12/28/2022華僑大學(xué)數(shù)251．預(yù)定義常量和類型：#defineTRUE1；#defineFALSE-1；#defineERRORNULL；1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新262．函數(shù)的形式[數(shù)據(jù)類型]函數(shù)名（[形式參數(shù)]）[形式參數(shù)說(shuō)明；]{內(nèi)部數(shù)據(jù)說(shuō)明；執(zhí)行語(yǔ)句組；}/*函數(shù)名*/〈函數(shù)的定義主要由函數(shù)名和函數(shù)體組成，函數(shù)體用花括號(hào)“{”和“}”括起來(lái)。函數(shù)中用方括號(hào)括起來(lái)的部分為可選項(xiàng)，函數(shù)名之間的圓括號(hào)不可省略。函數(shù)的結(jié)果可由指針或別的方式傳遞到函數(shù)之外。執(zhí)行語(yǔ)句可由各種類型的語(yǔ)句所組成，兩個(gè)語(yǔ)句之間用“；”號(hào)分隔?？蓪⒑瘮?shù)中的表達(dá)式的值通過return語(yǔ)句返回給調(diào)用它的函數(shù)。最后的花括號(hào)“}”之后的/*函數(shù)名*/為注釋部分，可舍。

1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新2．函數(shù)的形式12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新273．賦值語(yǔ)句簡(jiǎn)單賦值：〈變量名〉=〈表達(dá)式〉，它表示將表達(dá)式的值賦給左邊的變量；〈變量〉++，它表示變量加1后賦值給變量；〈變量〉--，它表示變量減1后賦值給變量；1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新3．賦值語(yǔ)句12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新28成組賦值：1.（〈變量1〉，〈變量2〉，〈變量3〉，…〈變量k〉）=（〈表達(dá)式1〉，〈表達(dá)式2〉，〈表達(dá)式3〉，…〈表達(dá)式k〉）；2.〈數(shù)組名1〉[下標(biāo)1…下標(biāo)2]=〈數(shù)組名2〉[下標(biāo)1…下標(biāo)2]1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新29串聯(lián)賦值：〈變量1〉=〈變量2〉=〈變量3〉=…=〈變量k〉=〈表達(dá)式〉；條件賦值：〈變量名〉=〈條件表達(dá)式〉？〈表達(dá)式1〉：〈表達(dá)式2〉；交換賦值：〈變量1〉←→〈變量2〉，表示變量1和變量2互換；1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新串聯(lián)賦值：12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新304．條件選擇語(yǔ)句if（〈表達(dá)式〉）語(yǔ)句；if（〈表達(dá)式〉）語(yǔ)句1；else語(yǔ)句2；情況語(yǔ)句switch（〈表達(dá)式〉）{case判斷值1；語(yǔ)句組1；break；case判斷值2；語(yǔ)句組2；break；……case判斷值n；語(yǔ)句組n；break；[default：語(yǔ)句組；break；]}注意：switchcase語(yǔ)句是先計(jì)算表達(dá)式的值，然后用其值與判斷值相比較，若它們相一致時(shí)，就執(zhí)行相應(yīng)的case下的語(yǔ)句組；若不一致，則執(zhí)行default下的語(yǔ)句組；其中的方括號(hào)代表可選項(xiàng)。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新4．條件選擇語(yǔ)句12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新31

5．循環(huán)語(yǔ)句⑴for語(yǔ)句for（〈表達(dá)式1〉；〈表達(dá)式2〉；〈表達(dá)式3〉）{循環(huán)體語(yǔ)句；}

首先計(jì)算表達(dá)式1的值，然后求表達(dá)式2的值，若結(jié)果非零則執(zhí)行循環(huán)體語(yǔ)句，最后對(duì)表達(dá)式3運(yùn)算，如此循環(huán)，直到表達(dá)式2的值為零時(shí)止。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新

5．循環(huán)語(yǔ)句12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新32⑵while語(yǔ)句while（〈條件表達(dá)式〉）{循環(huán)體語(yǔ)句；}while循環(huán)首先計(jì)算條件表達(dá)式的值，若條件表達(dá)式的值非零，則執(zhí)行循環(huán)體語(yǔ)句，然后再次計(jì)算條件表達(dá)式，重復(fù)執(zhí)行，直到條件表達(dá)式的值為假時(shí)退出循環(huán)，執(zhí)行該循環(huán)之后的語(yǔ)句。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新33⑶do-while語(yǔ)句do{循環(huán)體語(yǔ)句}while（〈條件表達(dá)式〉）該循環(huán)語(yǔ)句首先執(zhí)行循環(huán)體語(yǔ)句。然后再計(jì)算條件表達(dá)式的值，若條件表達(dá)式成立，則再次執(zhí)行循環(huán)體，再計(jì)算條件表達(dá)式的值，直到條件表達(dá)式的值為零，即條件不成立時(shí)結(jié)束循環(huán)。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新⑶do-while語(yǔ)句12/28/2022華僑大學(xué)數(shù)學(xué)系346．輸入、輸出語(yǔ)句輸入語(yǔ)句：用函數(shù)scanf實(shí)現(xiàn)，特別當(dāng)數(shù)據(jù)為字符時(shí)，用getchar函數(shù)實(shí)現(xiàn)。輸出語(yǔ)句：用printf函數(shù)實(shí)現(xiàn)，當(dāng)要輸出字符數(shù)據(jù)時(shí)，用putchar函數(shù)實(shí)現(xiàn)。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新357．其他一些語(yǔ)句（1）return表達(dá)式或return：用于函數(shù)結(jié)束。（2）break語(yǔ)句：可用在循環(huán)語(yǔ)句或case語(yǔ)句中結(jié)束循環(huán)過程或跳出情況語(yǔ)句。（3）exit語(yǔ)句：表示出現(xiàn)異常情況時(shí)，控制退出語(yǔ)句。8．注釋形式可用/*字符串*/或者單行注釋或//文字序列。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新7．其他一些語(yǔ)句12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新369．一些基本的函數(shù)如：max函數(shù)，用于求一個(gè)或幾個(gè)表達(dá)式中的最大值；min函數(shù)，用于求一個(gè)或幾個(gè)表達(dá)式中的最小值；abs函數(shù)，用于求表達(dá)式的絕對(duì)值；eof函數(shù)，用于判定文件是否結(jié)束；eoln函數(shù)，用于判斷文本行是否結(jié)束。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新37例計(jì)算f=1！+2！+3！+…+n！，用C語(yǔ)言描述。voidfactorsum（n）intn；{inti，j；intf，w；f=0；for（i=1，i〈=n；i++）{w=1；for（j=1，j〈=i；j++）w=w*j；f=f+w；}return；}上述算法所用到的運(yùn)算有乘法、加法、賦值和比較，其基本運(yùn)算為乘法操作。在上述算法的執(zhí)行過程中，對(duì)外循環(huán)變量i的每次取值，內(nèi)循環(huán)變量j循環(huán)i次。因?yàn)閮?nèi)循環(huán)每執(zhí)行一次，內(nèi)循環(huán)體語(yǔ)句w=w*j只作一次乘法操作，即當(dāng)內(nèi)循環(huán)變量j循環(huán)i次時(shí)，內(nèi)循環(huán)體的語(yǔ)句w=w*j作i次乘法。所以，整個(gè)算法所作的乘法操作總數(shù)是：f（n）=1+2+3+…n=n（n-1）/2。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新例計(jì)算f=1！+2！+3！+…+n！，用C語(yǔ)言描述。12381.5.3算法評(píng)價(jià)設(shè)計(jì)一個(gè)好的算法應(yīng)考慮以下幾個(gè)方面：1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新391．正確性

“正確”的含義在通常的用法中有很大的差別，大體可分為以下四個(gè)層次：①程序不含語(yǔ)法錯(cuò)誤；②程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足規(guī)格說(shuō)明要求的結(jié)果；③程序?qū)τ诰倪x擇的典型、苛刻而帶有刁難性的幾組數(shù)據(jù)能夠得出滿足規(guī)格說(shuō)明要求的結(jié)果；④程序?qū)σ磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足規(guī)格說(shuō)明要求的結(jié)果。

1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新1．正確性12/28/2022華僑大學(xué)數(shù)學(xué)系黃402．運(yùn)行時(shí)間運(yùn)行時(shí)間是指一個(gè)算法在計(jì)算機(jī)上運(yùn)算所花費(fèi)的時(shí)間。它大致等于計(jì)算機(jī)執(zhí)行一種簡(jiǎn)單操作（如賦值操作、轉(zhuǎn)向操作、比較操作等等）所需要的時(shí)間與算法中進(jìn)行簡(jiǎn)單操作次數(shù)的乘積。通常把算法中包含簡(jiǎn)單操作次數(shù)的多少叫做算法的時(shí)間復(fù)雜性，它是一個(gè)算法運(yùn)行時(shí)間的相對(duì)量度。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新413．占用的存儲(chǔ)空間一個(gè)算法在計(jì)算機(jī)存儲(chǔ)器上所占用的存儲(chǔ)空間，包括存儲(chǔ)算法本身所占用的存儲(chǔ)空間，算法的輸入、輸出數(shù)據(jù)所占用的存儲(chǔ)空間和算法運(yùn)行過程中臨時(shí)占用的存儲(chǔ)空間。分析一個(gè)算法所占用的存儲(chǔ)空間要從各方面綜合考慮。算法在運(yùn)行過程中所占用的存儲(chǔ)空間的大小被定義為算法的空間復(fù)雜性。它包括局部變量所占用的存儲(chǔ)空間和系統(tǒng)為了實(shí)現(xiàn)遞歸所使用的堆棧這兩個(gè)部分。算法的空間復(fù)雜性一般以數(shù)量級(jí)的形式給出。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新3．占用的存儲(chǔ)空間12/28/2022華僑大學(xué)數(shù)學(xué)系黃建424．簡(jiǎn)單性最簡(jiǎn)單和最直接的算法往往不是最有效的，但算法的簡(jiǎn)單性使得證明其正確性比較容易，同時(shí)便于編寫、修改、閱讀和調(diào)試，所以還是應(yīng)當(dāng)強(qiáng)調(diào)和不容忽視的。不過對(duì)于那些需要經(jīng)常使用的算法來(lái)說(shuō)，高效率（即盡量減少運(yùn)行時(shí)間和壓縮存儲(chǔ)空間）比簡(jiǎn)單性更為重要。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新431.5.4算法效率的度量1、時(shí)間復(fù)雜度算法時(shí)間的量度T(n)=算法中基本操作重復(fù)執(zhí)行的次數(shù)。一般情況下，T(n)是問題規(guī)模n的某個(gè)函數(shù)f(n)，記作：T(n)=O(f(n))它表示隨問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，稱作時(shí)間復(fù)雜度。

例1:{++x;s=0;}時(shí)間復(fù)雜度O(1)例2:for{I=1;I<=n;++I}{++x;s+=x;}時(shí)間復(fù)雜度為O(n)例3：for(j=1;j<=n;++j)for(k=1;k<=n;++k){++x;s+=x;}時(shí)間復(fù)雜度為O(n2)1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新1.5.4算法效率的度量例1:{++x;s=0;}44例4for(I=2;I<=n;++I)for(j=2;j<=I-1;++j){++x;a[I][j]=x;}其中語(yǔ)句++x的執(zhí)行次數(shù)為(n-1)(n-2)/2，這時(shí)，取增長(zhǎng)最快的項(xiàng)n2，因此，

時(shí)間復(fù)雜度為O(n2)。例5voidbubble_sort(inta[],intn){for(I=n-1,change=TRUE;I>=1&&change;--I){change=FALSE;for(j=0;j<I;++j)if(a[j]>a[j+1]){a[j]>a[j+1];change=TRUE;}}}1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新例4for(I=2;I<=n;++I)12/28/20245情況1當(dāng)a中初始序列為自小到大有序時(shí)，基本操作的執(zhí)行次數(shù)為0。情況2當(dāng)a中初始序列為自大至小有序時(shí)，基本操作的執(zhí)行次數(shù)為n(n-1)/2。情況3計(jì)算平均值假設(shè)a中初始輸入數(shù)據(jù)可出現(xiàn)n!種的排列次序的概率相等，則起泡排序的平均時(shí)間復(fù)雜度Targ(n)=O(n2)。在很多情況下，各種輸入數(shù)據(jù)集出現(xiàn)的規(guī)律難以確定，算法的平均時(shí)間復(fù)雜度也就難以確定。因此，常用的辦法是討論算法在最壞情況下的時(shí)間復(fù)雜度。2、空間復(fù)雜度空間復(fù)雜度是算法所需存儲(chǔ)空間的量度，記作：S(n)=O(f(n))其中n為問題的規(guī)模（或大?。?。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新情況1當(dāng)a中初始序列為自小到大有序時(shí)，基本操作的執(zhí)行次46本章小結(jié)本章主要介紹了如下一些基本概念：數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)元素之間抽象化的相互關(guān)系和這種關(guān)系在計(jì)算機(jī)中的存儲(chǔ)表示（即所謂數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)），并對(duì)這種結(jié)構(gòu)定義相適應(yīng)的運(yùn)算，設(shè)計(jì)出相應(yīng)的算法，而且確保經(jīng)過這些運(yùn)算后所得到的新結(jié)構(gòu)仍然是原來(lái)的結(jié)構(gòu)類型。數(shù)據(jù)：數(shù)據(jù)是人們利用文字符號(hào)、數(shù)字符號(hào)以及其他規(guī)定的符號(hào)對(duì)現(xiàn)實(shí)世界的事物及其活動(dòng)所做的描述。在計(jì)算機(jī)科學(xué)中，數(shù)據(jù)的含義非常廣泛，我們把一切能夠輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的信息，包括文字、表格、圖象等，都稱為數(shù)據(jù)。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新本章小結(jié)本章主要介紹了如下一些基本概念：12/28/202247結(jié)點(diǎn)：結(jié)點(diǎn)也叫數(shù)據(jù)元素，它是組成數(shù)據(jù)的基本單位。邏輯結(jié)構(gòu)：結(jié)點(diǎn)和結(jié)點(diǎn)之間的邏輯關(guān)系稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)表示稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。數(shù)據(jù)處理：數(shù)據(jù)處理是指對(duì)數(shù)據(jù)進(jìn)行查找、插入、刪除、合并、排序、統(tǒng)計(jì)以及簡(jiǎn)單計(jì)算等的操作過程。數(shù)據(jù)類型：數(shù)據(jù)類型是指程序設(shè)計(jì)語(yǔ)言中各變量可取的數(shù)據(jù)種類。數(shù)據(jù)類型是高級(jí)程序設(shè)計(jì)語(yǔ)言中的一個(gè)基本概念，它和數(shù)據(jù)結(jié)構(gòu)的概念密切相關(guān)。

1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新結(jié)點(diǎn)：結(jié)點(diǎn)也叫數(shù)據(jù)元素，它是組成數(shù)據(jù)的基本單位。12/28/48習(xí)

題

一1．簡(jiǎn)述下列術(shù)語(yǔ)：數(shù)據(jù)、結(jié)點(diǎn)、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)處理、數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型。2．試根據(jù)以下信息：校友姓名、性別、出生年月、畢業(yè)時(shí)間、所學(xué)專業(yè)、現(xiàn)在工作單位、職稱、職務(wù)、電話等，為校友錄構(gòu)造一種適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)（作圖示意），并定義必要的運(yùn)算和用文字?jǐn)⑹鱿鄳?yīng)的算法思想。3．什么是算法？算法的主要特點(diǎn)是什么？4．如何評(píng)價(jià)一個(gè)算法？1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新習(xí)題一1．簡(jiǎn)述下列術(shù)語(yǔ)：數(shù)據(jù)、結(jié)點(diǎn)、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)49編程題：一個(gè)班有6個(gè)學(xué)生，開五門課。（1）求第一門課的平均分；（2）找出有2門以上不及格的學(xué)生，輸出他們的學(xué)號(hào)、姓名和全部課程成績(jī)和平均成績(jī)；（3）找出平均成績(jī)90分以上或全部課程成績(jī)?cè)?5分以上的學(xué)生。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新編程題：12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新50練習(xí)題1、給出以下算法的時(shí)間復(fù)雜度。(1)x=n;y=0;while(x>=(y+1)*(y+1))y++;(2)voidfunc(intn){inti=1;k=100;while(I<n){k++;i+=2;}}(3)voidfunc(intn){inti=0,s=0;while(s<n){i++;s=s+i;}}2、在以下邏輯結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)可能有多個(gè)直接后繼結(jié)點(diǎn)的是A.線性結(jié)構(gòu)B.樹形結(jié)構(gòu)C.圖形結(jié)構(gòu)3、在以下邏輯結(jié)構(gòu)中，只有一個(gè)開始結(jié)點(diǎn)的有；可能有多個(gè)終端結(jié)點(diǎn)的有。A.線性結(jié)構(gòu)B.樹形結(jié)構(gòu)C.圖形結(jié)構(gòu)1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新練習(xí)題12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新514、數(shù)據(jù)結(jié)構(gòu)包括的三個(gè)方面的內(nèi)容分別是：A.線性結(jié)構(gòu)B.邏輯結(jié)構(gòu)C.順序結(jié)構(gòu)D.存儲(chǔ)結(jié)構(gòu)E.查找運(yùn)算F.數(shù)據(jù)運(yùn)算5、以下屬于數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)的是：A.二叉樹B.索引C.散列D.線性表1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新4、數(shù)據(jù)結(jié)構(gòu)包括的三個(gè)方面的內(nèi)容分別是：12/28/202252答案：1、解：(1)設(shè)while語(yǔ)句的執(zhí)行頻度為T(n)，顯然有;即，所以算法的時(shí)間復(fù)雜度為

（2）設(shè)while循環(huán)語(yǔ)句執(zhí)行的次數(shù)為m,i從1開始遞增，最后取值為1+2m，有i=1+2m<n,即m<(n-1)/2=O(n)，所以該算法的時(shí)間復(fù)雜度為O(n)。（3）對(duì)于while循環(huán)語(yǔ)句，設(shè)執(zhí)行的次數(shù)為m,I從0開始遞增1，直到m為止，即s=)+1+2+…+m-1=m(m-1)/2，并滿足s=m(m-1)/2<n，則有,，所以該算法的時(shí)間復(fù)雜度為。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新答案：12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新53

數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版本）

嚴(yán)蔚敏吳偉民

編著1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新

數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版本）12/28/2022華僑大54前言

二十一世紀(jì)是科學(xué)技術(shù)高速發(fā)展的信息時(shí)代，而計(jì)算機(jī)是處理信息的主要工具，因此，人們已經(jīng)認(rèn)識(shí)到，計(jì)算機(jī)知識(shí)已成為人類當(dāng)代文化的一個(gè)重要組成部分。計(jì)算機(jī)科學(xué)技術(shù)以驚人的速度向前發(fā)展，它的廣泛應(yīng)用已從傳統(tǒng)的數(shù)值計(jì)算領(lǐng)域發(fā)展到各種非數(shù)值計(jì)算領(lǐng)域。在非數(shù)值計(jì)算領(lǐng)域里，數(shù)據(jù)處理的對(duì)象已從簡(jiǎn)單的數(shù)值發(fā)展到一般的符號(hào)，進(jìn)而發(fā)展到具有一定結(jié)構(gòu)的數(shù)據(jù)。在這里，面臨的主要問題是：針對(duì)每一種新的應(yīng)用領(lǐng)域的處理對(duì)象，如何選擇合適的數(shù)據(jù)表示（結(jié)構(gòu)），如何有效地組織計(jì)算機(jī)存貯，并在此基礎(chǔ)上又如何有效地實(shí)現(xiàn)對(duì)象之間的“運(yùn)算”關(guān)系。傳統(tǒng)的解決數(shù)值計(jì)算的許多理論、方法和技術(shù)已不能滿足解決非數(shù)值計(jì)算問題的需要，必須進(jìn)行新的探索。數(shù)據(jù)結(jié)構(gòu)就是研究和解決這些問題的重要基礎(chǔ)理論。因此，“數(shù)據(jù)結(jié)構(gòu)”課程已成為計(jì)算機(jī)類專業(yè)的一門重要專業(yè)基礎(chǔ)課。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新前言12/28/2022華僑大學(xué)數(shù)學(xué)55第1章緒論[目的]介紹數(shù)據(jù)結(jié)構(gòu)中常用的基本概念和術(shù)語(yǔ)以及學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義。[要求]了解本章介紹的各種基本概念和術(shù)語(yǔ)，掌握算法描述和分析的方法。[重點(diǎn)]了解數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及數(shù)據(jù)的運(yùn)算三方面的概念及相互關(guān)系。[難點(diǎn)]算法復(fù)雜度的分析方法。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新第1章緒論[目的]介紹數(shù)據(jù)結(jié)構(gòu)中常用的基56

1.1引言

眾所周知，二十世紀(jì)四十年代，電子數(shù)字計(jì)算機(jī)問世的直接原因是解決彈道學(xué)的計(jì)算問題。早期，電子計(jì)算機(jī)的應(yīng)用范圍，幾乎只局限于科學(xué)和工程的計(jì)算，其處理的對(duì)象是純數(shù)值性的信息，通常，人們把這類問題稱為數(shù)值計(jì)算。近三十年來(lái)，電子計(jì)算機(jī)的發(fā)展異常迅猛，這不僅表現(xiàn)在計(jì)算機(jī)本身運(yùn)算速度不斷提高、信息存儲(chǔ)量日益擴(kuò)大、價(jià)格逐步下降，更重要的是計(jì)算機(jī)廣泛地應(yīng)用于情報(bào)檢索、企業(yè)管理、系統(tǒng)工程等方面，已遠(yuǎn)遠(yuǎn)超出了科技計(jì)算的范圍，而滲透到人類社會(huì)活動(dòng)的一切領(lǐng)域。與此相應(yīng)，計(jì)算機(jī)的處理對(duì)象也從簡(jiǎn)單的純數(shù)值性信息發(fā)展到非數(shù)值性的和具有一定結(jié)構(gòu)的信息。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新

1.1引言12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新57因此，再把電子數(shù)字計(jì)算機(jī)簡(jiǎn)單地看作是進(jìn)行數(shù)值計(jì)算的工具，把數(shù)據(jù)僅理解為純數(shù)值性的信息，就顯得太狹隘了?，F(xiàn)代計(jì)算機(jī)科學(xué)的觀點(diǎn)，是把計(jì)算機(jī)程序處理的一切數(shù)值的、非數(shù)值的信息，乃至程序統(tǒng)稱為數(shù)據(jù)（Data），而電子計(jì)算機(jī)則是加工處理數(shù)據(jù)（信息）的工具。由于數(shù)據(jù)的表示方法和組織形式直接關(guān)系到程序?qū)?shù)據(jù)的處理效率，而系統(tǒng)程序和許多應(yīng)用程序的規(guī)模很大，結(jié)構(gòu)相當(dāng)復(fù)雜，處理對(duì)象又多為非數(shù)值性數(shù)據(jù)。因此，單憑程序設(shè)計(jì)人員的經(jīng)驗(yàn)和技巧已難以設(shè)計(jì)出效率高、可靠性強(qiáng)的程序。于是，就要求人們對(duì)計(jì)算機(jī)程序加工的對(duì)象進(jìn)行系統(tǒng)的研究，即研究數(shù)據(jù)的特性以及數(shù)據(jù)之間存在的關(guān)系——數(shù)據(jù)結(jié)構(gòu)（DateStructure）。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新581.2數(shù)據(jù)結(jié)構(gòu)的發(fā)展簡(jiǎn)史及其在計(jì)算機(jī)科學(xué)中所處的地位發(fā)展史：1、“數(shù)據(jù)結(jié)構(gòu)”作為一門獨(dú)立的課程在國(guó)外是從1968年才開始設(shè)立的。2、1968年美國(guó)唐·歐·克努特教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的《計(jì)算機(jī)程序設(shè)計(jì)技巧》第一卷《基本算法》是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)及其操作的著作。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新1.2數(shù)據(jù)結(jié)構(gòu)的發(fā)展簡(jiǎn)史及其在計(jì)算機(jī)科學(xué)中所處的地位1259地位：“數(shù)據(jù)結(jié)構(gòu)”在計(jì)算機(jī)科學(xué)中是一門綜合性的專業(yè)基礎(chǔ)課。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間的一門核心課程。數(shù)據(jù)結(jié)構(gòu)這一門課的內(nèi)容不僅是一般程序設(shè)計(jì)（特別是非數(shù)值性程序設(shè)計(jì)）的基礎(chǔ)，而且是設(shè)計(jì)和實(shí)現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫(kù)系統(tǒng)及其他系統(tǒng)程序的重要基礎(chǔ)。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新地位：12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新60

1.3什么是數(shù)據(jù)結(jié)構(gòu)

計(jì)算機(jī)解決一個(gè)具體問題時(shí)，大致需要經(jīng)過下列幾個(gè)步驟：首先要從具體問題中抽象出一個(gè)適當(dāng)?shù)臄?shù)學(xué)模型，然后設(shè)計(jì)一個(gè)解此數(shù)學(xué)模型的算法（Algorithm），最后編出程序、進(jìn)行測(cè)試、調(diào)整直至得到最終解答。尋求數(shù)學(xué)模型的實(shí)質(zhì)是分析問題，從中提取操作的對(duì)象，并找出這些操作對(duì)象之間含有的關(guān)系，然后用數(shù)學(xué)的語(yǔ)言加以描述。計(jì)算機(jī)算法與數(shù)據(jù)的結(jié)構(gòu)密切相關(guān)，算法無(wú)不依附于具體的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)直接關(guān)系到算法的選擇和效率。運(yùn)算是由計(jì)算機(jī)來(lái)完成，這就要設(shè)計(jì)相應(yīng)的插入、刪除和修改的算法。也就是說(shuō)，數(shù)據(jù)結(jié)構(gòu)還需要給出每種結(jié)構(gòu)類型所定義的各種運(yùn)算的算法。直觀定義：數(shù)據(jù)結(jié)構(gòu)是研究程序設(shè)計(jì)中計(jì)算機(jī)操作的對(duì)象以及它們之間的關(guān)系和運(yùn)算的一門學(xué)科。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新

1.3什么是數(shù)據(jù)結(jié)構(gòu)

12/28/2022華僑大學(xué)數(shù)學(xué)611.4基本概念和術(shù)語(yǔ)

1．?dāng)?shù)據(jù)

數(shù)據(jù)是人們利用文字符號(hào)、數(shù)字符號(hào)以及其他規(guī)定的符號(hào)對(duì)現(xiàn)實(shí)世界的事物及其活動(dòng)所做的描述。在計(jì)算機(jī)科學(xué)中，數(shù)據(jù)的含義非常廣泛，我們把一切能夠輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的信息，包括文字、表格、圖象等，都稱為數(shù)據(jù)。例如，一個(gè)個(gè)人書庫(kù)管理程序所要處理的數(shù)據(jù)可能是一張如表1-1所示的表格。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新1.4基本概念和術(shù)語(yǔ)12/28/2022華僑大學(xué)數(shù)學(xué)系62

表1-1個(gè)人書庫(kù)1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新

632．結(jié)點(diǎn)結(jié)點(diǎn)也叫數(shù)據(jù)元素，它是組成數(shù)據(jù)的基本單位。在程序中通常把結(jié)點(diǎn)作為一個(gè)整體進(jìn)行考慮和處理。例如，在表1-1所示的個(gè)人書庫(kù)中，為了便于處理，把其中的每一行（代表一本書）作為一個(gè)基本單位來(lái)考慮，故該數(shù)據(jù)由10個(gè)結(jié)點(diǎn)構(gòu)成。一般情況下，一個(gè)結(jié)點(diǎn)中含有若干個(gè)字段（也叫數(shù)據(jù)項(xiàng)）。例如，在表1-1所示的表格數(shù)據(jù)中，每個(gè)結(jié)點(diǎn)都有登錄號(hào)、書號(hào)、書名、作者、出版社和價(jià)格等六個(gè)字段構(gòu)成。字段是構(gòu)成數(shù)據(jù)的最小單位。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新643．邏輯結(jié)構(gòu)結(jié)點(diǎn)和結(jié)點(diǎn)之間的邏輯關(guān)系稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。在表1-1所示的表格數(shù)據(jù)中，各結(jié)點(diǎn)之間在邏輯上有一種線性關(guān)系，它指出了10個(gè)結(jié)點(diǎn)在表中的排列順序。根據(jù)這種線性關(guān)系，可以看出表中第一本書是什么書，第二本書是什么書，等等。4．存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)表示稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。在表1-1所示的表格數(shù)據(jù)在計(jì)算機(jī)中可以有多種存儲(chǔ)表示，例如，可以表示成數(shù)組，存放在內(nèi)存中；也可以表示成文件，存放在磁盤上，等等。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新655．?dāng)?shù)據(jù)處理數(shù)據(jù)處理是指對(duì)數(shù)據(jù)進(jìn)行查找、插入、刪除、合并、排序、統(tǒng)計(jì)以及簡(jiǎn)單計(jì)算等的操作過程。在早期，計(jì)算機(jī)主要用于科學(xué)和工程計(jì)算，進(jìn)入八十年代以后，計(jì)算機(jī)主要用于數(shù)據(jù)處理。據(jù)有關(guān)統(tǒng)計(jì)資料表明，現(xiàn)在計(jì)算機(jī)用于數(shù)據(jù)處理的時(shí)間比例達(dá)到80%以上，隨著時(shí)間的推移和計(jì)算機(jī)應(yīng)用的進(jìn)一步普及，計(jì)算機(jī)用于數(shù)據(jù)處理的時(shí)間比例必將進(jìn)一步增大。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新666．?dāng)?shù)據(jù)結(jié)構(gòu)（DataStructure）數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)元素（DataElement）之間抽象化的相互關(guān)系和這種關(guān)系在計(jì)算機(jī)中的存儲(chǔ)表示（即所謂數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)），并對(duì)這種結(jié)構(gòu)定義相適應(yīng)的運(yùn)算，設(shè)計(jì)出相應(yīng)的算法，而且確保經(jīng)過這些運(yùn)算后所得到的新結(jié)構(gòu)仍然是原來(lái)的結(jié)構(gòu)類型。為了敘述上的方便和避免產(chǎn)生混淆，通常我們把數(shù)據(jù)的邏輯結(jié)構(gòu)統(tǒng)稱為數(shù)據(jù)結(jié)構(gòu)，把數(shù)據(jù)的物理結(jié)構(gòu)統(tǒng)稱為存儲(chǔ)結(jié)構(gòu)（StorageStructure）。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新6．?dāng)?shù)據(jù)結(jié)構(gòu)（DataStructure）12/28/2067四種基本基本結(jié)構(gòu)：（1）集合：結(jié)構(gòu)中的數(shù)據(jù)元素之間除了“同屬于一個(gè)集合”的關(guān)系外，別無(wú)其他關(guān)系。（2）線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個(gè)對(duì)一個(gè)的關(guān)系。如：圖書館的書目檢索系統(tǒng)（3）樹形結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素存在一個(gè)對(duì)多個(gè)的關(guān)系。如：計(jì)算機(jī)和人對(duì)奕問題工廠的組織管理（4）圖狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素存在多個(gè)對(duì)多個(gè)的關(guān)系。如：多叉路口的交通燈管理問題最短路徑問題

同一個(gè)邏輯結(jié)構(gòu)可以有不同的內(nèi)部存儲(chǔ)結(jié)構(gòu)；反之，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)一定要映像數(shù)據(jù)之間的邏輯關(guān)系。數(shù)據(jù)結(jié)構(gòu)的形式定義：數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組data_structure=(D,S)其中：D是數(shù)據(jù)元素的有限集，S是D上關(guān)系的有限集。

1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新四種基本基本結(jié)構(gòu)：12/28/2022華僑大學(xué)數(shù)學(xué)系黃建68例1一種結(jié)構(gòu)lineority=(K,R）K={k1,k2,k3,k4,k5,k6,k7}R={r}r={<k3,k1>,<k1,k5>,<k5,k6>,<k6,k4>,<k4,k2>,<k2,k7>}則有：k3->k1->k5->k6->k4->k2->k7一種線性結(jié)構(gòu)例2tree=(K,R)K={01,02,03,04,05,06,07,08}R={r}r={<01,02>,<01,03>,<02,04>,<02,05>,<03,06>,<03,07>,<07,08>}樹形結(jié)構(gòu)

1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新例1一種結(jié)構(gòu)lineority=(K,R）12/28/69例3graph=(K,R)K={01,02,03,04,05,06}R={r}r={<01,02>,<02,01>,<01,04>,<04,01>,<02,03>,<02,06>,<06,02>,<05,03>,<03,04>,<04,03>}圖形結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)分類：數(shù)據(jù)的邏輯結(jié)構(gòu)線性結(jié)構(gòu)非線性結(jié)構(gòu)線性表樹形結(jié)構(gòu)圖一般線性表特殊線性表線性表推廣樹二叉樹有向圖無(wú)向圖線性表?xiàng)ｊ?duì)列串?dāng)?shù)組廣義表

1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新例3graph=(K,R)12/28/2022華僑大70數(shù)據(jù)的物理結(jié)構(gòu)方面二種類型：順序存儲(chǔ)結(jié)構(gòu)和非順序存儲(chǔ)結(jié)構(gòu)

順序存儲(chǔ)結(jié)構(gòu)：邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理位置上相比鄰的存儲(chǔ)單元里，其關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)（向量、數(shù)組）。

非順序存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)元素在計(jì)算機(jī)內(nèi)任意位置上存放，其關(guān)系用指針來(lái)鏈接，稱為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)-鏈表。按指針個(gè)數(shù)分為：?jiǎn)捂湵?、雙向鏈表、多重鏈表

索引存儲(chǔ)結(jié)構(gòu)：按（地址關(guān)鍵字）的偶對(duì)集合，關(guān)鍵字是唯一標(biāo)識(shí)結(jié)點(diǎn)；地址指出該結(jié)點(diǎn)的存儲(chǔ)地址。

散列存儲(chǔ)結(jié)構(gòu)：根據(jù)結(jié)點(diǎn)關(guān)鍵字來(lái)直接算出該結(jié)點(diǎn)的存儲(chǔ)地址。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新數(shù)據(jù)的物理結(jié)構(gòu)方面12/28/2022華僑大學(xué)數(shù)學(xué)系717．?dāng)?shù)據(jù)類型數(shù)據(jù)類型是一個(gè)值的集合和定義在這個(gè)值上的一組操作的總稱。數(shù)據(jù)類型是高級(jí)程序設(shè)計(jì)語(yǔ)言中的一個(gè)基本概念，它和數(shù)據(jù)結(jié)構(gòu)的概念密切相關(guān)。一方面，在程序設(shè)計(jì)語(yǔ)言中，每一個(gè)數(shù)據(jù)都屬于某種數(shù)據(jù)類型。類型明顯或隱含地規(guī)定了數(shù)據(jù)的取值范圍、存儲(chǔ)方式以及允許進(jìn)行的運(yùn)算?？梢哉J(rèn)為，數(shù)據(jù)類型是在程序設(shè)計(jì)中已經(jīng)實(shí)現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)。另一方面，在程序設(shè)計(jì)過程中，當(dāng)需要引入某種新的數(shù)據(jù)結(jié)構(gòu)時(shí)，總是借助編程語(yǔ)言所提供的數(shù)據(jù)類型來(lái)描述數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新7．?dāng)?shù)據(jù)類型12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新72抽象數(shù)據(jù)類型（AbstractDataType,ADT)是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作，它僅取決于它的一組邏輯特性，而與其在計(jì)算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)無(wú)關(guān)。一個(gè)含抽象數(shù)據(jù)類型的軟件模塊通常應(yīng)包含定義、表示和實(shí)現(xiàn)三個(gè)部分。抽象數(shù)據(jù)類型的三元組表示(DSP),其中，D是數(shù)據(jù)對(duì)象，S是D上的關(guān)系集，P是對(duì)D的基本操作集。ADT抽象數(shù)據(jù)類型名{數(shù)據(jù)對(duì)象：<數(shù)據(jù)對(duì)象的定義>數(shù)據(jù)關(guān)系：<數(shù)據(jù)關(guān)系的定義>基本操作：<基本操作的定義>}ADT抽象數(shù)據(jù)類型名其中，數(shù)據(jù)對(duì)象和數(shù)據(jù)關(guān)系的定義用偽碼描述，基本操作的定義格式為：基本操作名（參數(shù)表）初始條件：<初始條件描述>操作結(jié)果：<操作結(jié)果描述>1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新抽象數(shù)據(jù)類型（AbstractData73基本操作有兩種參數(shù)：賦值參數(shù)只為操作提供輸入值；引用參數(shù)以&打頭，除可提供輸入值外，還將返回操作結(jié)果。例抽象數(shù)據(jù)類型三元組的定義：ADTTriplet{數(shù)據(jù)對(duì)象：D={e1,e2,e3|e1,e2,e3屬于Elemset}數(shù)據(jù)關(guān)系：R1={<e1,e2>,<e2,e3>}基本操作：InitTriplet(&T,v1,v2,v3)操作結(jié)果：構(gòu)造了三元組T,元素e1,e2,和e3分別被賦以參數(shù)v1,v2和v3的值。DestroyTriplet(&T)操作結(jié)果：三元組T被銷毀。Get（T,I,&e)初始條件：三元組T已存在，1<=I<=3操作結(jié)果：用e返回T的第I元的值。}1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新基本操作有兩種參數(shù)：賦值參數(shù)只為操作提供輸入值；引用參74

8．算法簡(jiǎn)單地說(shuō)就是解決特定問題的方法（關(guān)于算法的嚴(yán)格定義，在此不作討論）。特定的問題可以是數(shù)值的，也可以是非數(shù)值的。解決數(shù)值問題的算法叫做數(shù)值算法，科學(xué)和工程計(jì)算方面的算法都屬于數(shù)值算法，如求解數(shù)值積分，求解線性方程組、求解代數(shù)方程、求解微分方程等。解決非數(shù)值問題的算法叫做非數(shù)值算法，數(shù)據(jù)處理方面的算法都屬于非數(shù)值算法。例如各種排序算法、查找算法、插入算法、刪除算法、遍歷算法等。數(shù)值算法和非數(shù)值算法并沒有嚴(yán)格的區(qū)別。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新8．算法12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新75一般說(shuō)來(lái)，在數(shù)值算法中主要進(jìn)行算術(shù)運(yùn)算，而在非數(shù)值算法中主要進(jìn)行比較和邏輯運(yùn)算。另一方面，特定的問題可能是遞歸的，也可能是非遞歸的，因而解決它們的算法就有遞歸算法和非遞歸算法之分。從理論上講，任何遞歸算法都可以通過循環(huán)，堆棧等技術(shù)轉(zhuǎn)化為非遞歸算法。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新761.5算法和算法的描述

1.5.1算法算法是執(zhí)行特定計(jì)算的有窮過程。這個(gè)過程有5個(gè)特點(diǎn)：1.動(dòng)態(tài)有窮：當(dāng)執(zhí)行一個(gè)算法時(shí)，不論是何種情況，在經(jīng)過了有限步驟后，這個(gè)算法一定要終止。2.確定性：算法中的每條指令都必須是清楚的，指令無(wú)二義性。3.輸入：具有0個(gè)或0個(gè)以上由外界提供的量。4.輸出：產(chǎn)生1個(gè)或多個(gè)結(jié)果。5.可行性：每條指令都充分基本，原則上可由人僅用筆和紙?jiān)谟邢薜臅r(shí)間內(nèi)也能完成。

注意：算法和程序是有區(qū)別的，即程序未必能滿足動(dòng)態(tài)有窮。在本書中，我們只討論滿足動(dòng)態(tài)有窮的程序，因此“算法”和“程序”是通用的。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新1.5算法和算法的描述

1.5.1算法12/28/277

1.5.2算法的描述

一個(gè)算法可以用自然語(yǔ)言、數(shù)字語(yǔ)言或約定的符號(hào)來(lái)描述，也可以用計(jì)算機(jī)高級(jí)程序語(yǔ)言來(lái)描述，如Pascal語(yǔ)言、C語(yǔ)言或偽代碼等。本書選用C語(yǔ)言作為描述算法的工具?，F(xiàn)簡(jiǎn)單說(shuō)明C語(yǔ)言的語(yǔ)法結(jié)構(gòu)如下：1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新

1.5.2算法的描述12/28/2022華僑大學(xué)數(shù)781．預(yù)定義常量和類型：#defineTRUE1；#defineFALSE-1；#defineERRORNULL；1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新792．函數(shù)的形式[數(shù)據(jù)類型]函數(shù)名（[形式參數(shù)]）[形式參數(shù)說(shuō)明；]{內(nèi)部數(shù)據(jù)說(shuō)明；執(zhí)行語(yǔ)句組；}/*函數(shù)名*/〈函數(shù)的定義主要由函數(shù)名和函數(shù)體組成，函數(shù)體用花括號(hào)“{”和“}”括起來(lái)。函數(shù)中用方括號(hào)括起來(lái)的部分為可選項(xiàng)，函數(shù)名之間的圓括號(hào)不可省略。函數(shù)的結(jié)果可由指針或別的方式傳遞到函數(shù)之外。執(zhí)行語(yǔ)句可由各種類型的語(yǔ)句所組成，兩個(gè)語(yǔ)句之間用“；”號(hào)分隔?？蓪⒑瘮?shù)中的表達(dá)式的值通過return語(yǔ)句返回給調(diào)用它的函數(shù)。最后的花括號(hào)“}”之后的/*函數(shù)名*/為注釋部分，可舍。

1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新2．函數(shù)的形式12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新803．賦值語(yǔ)句簡(jiǎn)單賦值：〈變量名〉=〈表達(dá)式〉，它表示將表達(dá)式的值賦給左邊的變量；〈變量〉++，它表示變量加1后賦值給變量；〈變量〉--，它表示變量減1后賦值給變量；1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新3．賦值語(yǔ)句12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新81成組賦值：1.（〈變量1〉，〈變量2〉，〈變量3〉，…〈變量k〉）=（〈表達(dá)式1〉，〈表達(dá)式2〉，〈表達(dá)式3〉，…〈表達(dá)式k〉）；2.〈數(shù)組名1〉[下標(biāo)1…下標(biāo)2]=〈數(shù)組名2〉[下標(biāo)1…下標(biāo)2]1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新82串聯(lián)賦值：〈變量1〉=〈變量2〉=〈變量3〉=…=〈變量k〉=〈表達(dá)式〉；條件賦值：〈變量名〉=〈條件表達(dá)式〉？〈表達(dá)式1〉：〈表達(dá)式2〉；交換賦值：〈變量1〉←→〈變量2〉，表示變量1和變量2互換；1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新串聯(lián)賦值：12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新834．條件選擇語(yǔ)句if（〈表達(dá)式〉）語(yǔ)句；if（〈表達(dá)式〉）語(yǔ)句1；else語(yǔ)句2；情況語(yǔ)句switch（〈表達(dá)式〉）{case判斷值1；語(yǔ)句組1；break；case判斷值2；語(yǔ)句組2；break；……case判斷值n；語(yǔ)句組n；break；[default：語(yǔ)句組；break；]}注意：switchcase語(yǔ)句是先計(jì)算表達(dá)式的值，然后用其值與判斷值相比較，若它們相一致時(shí)，就執(zhí)行相應(yīng)的case下的語(yǔ)句組；若不一致，則執(zhí)行default下的語(yǔ)句組；其中的方括號(hào)代表可選項(xiàng)。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新4．條件選擇語(yǔ)句12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新84

5．循環(huán)語(yǔ)句⑴for語(yǔ)句for（〈表達(dá)式1〉；〈表達(dá)式2〉；〈表達(dá)式3〉）{循環(huán)體語(yǔ)句；}

首先計(jì)算表達(dá)式1的值，然后求表達(dá)式2的值，若結(jié)果非零則執(zhí)行循環(huán)體語(yǔ)句，最后對(duì)表達(dá)式3運(yùn)算，如此循環(huán)，直到表達(dá)式2的值為零時(shí)止。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新

5．循環(huán)語(yǔ)句12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新85⑵while語(yǔ)句while（〈條件表達(dá)式〉）{循環(huán)體語(yǔ)句；}while循環(huán)首先計(jì)算條件表達(dá)式的值，若條件表達(dá)式的值非零，則執(zhí)行循環(huán)體語(yǔ)句，然后再次計(jì)算條件表達(dá)式，重復(fù)執(zhí)行，直到條件表達(dá)式的值為假時(shí)退出循環(huán)，執(zhí)行該循環(huán)之后的語(yǔ)句。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新86⑶do-while語(yǔ)句do{循環(huán)體語(yǔ)句}while（〈條件表達(dá)式〉）該循環(huán)語(yǔ)句首先執(zhí)行循環(huán)體語(yǔ)句。然后再計(jì)算條件表達(dá)式的值，若條件表達(dá)式成立，則再次執(zhí)行循環(huán)體，再計(jì)算條件表達(dá)式的值，直到條件表達(dá)式的值為零，即條件不成立時(shí)結(jié)束循環(huán)。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新⑶do-while語(yǔ)句12/28/2022華僑大學(xué)數(shù)學(xué)系876．輸入、輸出語(yǔ)句輸入語(yǔ)句：用函數(shù)scanf實(shí)現(xiàn)，特別當(dāng)數(shù)據(jù)為字符時(shí)，用getchar函數(shù)實(shí)現(xiàn)。輸出語(yǔ)句：用printf函數(shù)實(shí)現(xiàn)，當(dāng)要輸出字符數(shù)據(jù)時(shí)，用putchar函數(shù)實(shí)現(xiàn)。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新887．其他一些語(yǔ)句（1）return表達(dá)式或return：用于函數(shù)結(jié)束。（2）break語(yǔ)句：可用在循環(huán)語(yǔ)句或case語(yǔ)句中結(jié)束循環(huán)過程或跳出情況語(yǔ)句。（3）exit語(yǔ)句：表示出現(xiàn)異常情況時(shí)，控制退出語(yǔ)句。8．注釋形式可用/*字符串*/或者單行注釋或//文字序列。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新7．其他一些語(yǔ)句12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新899．一些基本的函數(shù)如：max函數(shù)，用于求一個(gè)或幾個(gè)表達(dá)式中的最大值；min函數(shù)，用于求一個(gè)或幾個(gè)表達(dá)式中的最小值；abs函數(shù)，用于求表達(dá)式的絕對(duì)值；eof函數(shù)，用于判定文件是否結(jié)束；eoln函數(shù)，用于判斷文本行是否結(jié)束。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新90例計(jì)算f=1！+2！+3！+…+n！，用C語(yǔ)言描述。voidfactorsum（n）intn；{inti，j；intf，w；f=0；for（i=1，i〈=n；i++）{w=1；for（j=1，j〈=i；j++）w=w*j；f=f+w；}return；}上述算法所用到的運(yùn)算有乘法、加法、賦值和比較，其基本運(yùn)算為乘法操作。在上述算法的執(zhí)行過程中，對(duì)外循環(huán)變量i的每次取值，內(nèi)循環(huán)變量j循環(huán)i次。因?yàn)閮?nèi)循環(huán)每執(zhí)行一次，內(nèi)循環(huán)體語(yǔ)句w=w*j只作一次乘法操作，即當(dāng)內(nèi)循環(huán)變量j循環(huán)i次時(shí)，內(nèi)循環(huán)體的語(yǔ)句w=w*j作i次乘法。所以，整個(gè)算法所作的乘法操作總數(shù)是：f（n）=1+2+3+…n=n（n-1）/2。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新例計(jì)算f=1！+2！+3！+…+n！，用C語(yǔ)言描述。12911.5.3算法評(píng)價(jià)設(shè)計(jì)一個(gè)好的算法應(yīng)考慮以下幾個(gè)方面：1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新921．正確性

“正確”的含義在通常的用法中有很大的差別，大體可分為以下四個(gè)層次：①程序不含語(yǔ)法錯(cuò)誤；②程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足規(guī)格說(shuō)明要求的結(jié)果；③程序?qū)τ诰倪x擇的典型、苛刻而帶有刁難性的幾組數(shù)據(jù)能夠得出滿足規(guī)格說(shuō)明要求的結(jié)果；④程序?qū)σ磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足規(guī)格說(shuō)明要求的結(jié)果。

1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新1．正確性12/28/2022華僑大學(xué)數(shù)學(xué)系黃932．運(yùn)行時(shí)間運(yùn)行時(shí)間是指一個(gè)算法在計(jì)算機(jī)上運(yùn)算所花費(fèi)的時(shí)間。它大致等于計(jì)算機(jī)執(zhí)行一種簡(jiǎn)單操作（如賦值操作、轉(zhuǎn)向操作、比較操作等等）所需要的時(shí)間與算法中進(jìn)行簡(jiǎn)單操作次數(shù)的乘積。通常把算法中包含簡(jiǎn)單操作次數(shù)的多少叫做算法的時(shí)間復(fù)雜性，它是一個(gè)算法運(yùn)行時(shí)間的相對(duì)量度。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新12/28/2022華僑大學(xué)數(shù)學(xué)系黃建新943．占用的存儲(chǔ)空間一個(gè)算法在計(jì)算機(jī)存儲(chǔ)器上所占用的存儲(chǔ)空間，包括存儲(chǔ)算法本身所占用的存儲(chǔ)空間，算法的輸入、輸出數(shù)據(jù)所占用的存儲(chǔ)空間和算法運(yùn)行過程中臨時(shí)占用的存儲(chǔ)空間。分析一個(gè)算法所占用的存儲(chǔ)空間要從各方面綜合考慮。算法在運(yùn)行過程中所占用的存儲(chǔ)空間的大小被定義為算法的空間復(fù)雜性。它包括局部變量所占用的存儲(chǔ)空間和系統(tǒng)為了實(shí)現(xiàn)遞歸所使用的堆棧這兩個(gè)部分。算法的空間復(fù)雜性一般以數(shù)量級(jí)的形式給出。1/4/2023華僑大學(xué)數(shù)學(xué)系黃建新3．占用的存儲(chǔ)空間12/28/2022華僑大學(xué)數(shù)學(xué)系黃建954．簡(jiǎn)單性最簡(jiǎn)單和最直接的算法往往不是最有效的，但算法的簡(jiǎn)單性使得證明其正確性比較容易，同時(shí)便于編寫、修改、閱讀和調(diào)試，所以還是應(yīng)當(dāng)強(qiáng)調(diào)和不容忽視的。不過對(duì)于那些需要經(jīng)常使用的