《數(shù)據(jù)結(jié)構(gòu)》課件(C語言)new

主講：吳婷婷南京信息工程大學(xué)計(jì)算機(jī)與軟件學(xué)院

數(shù)據(jù)結(jié)構(gòu)寫在前面的話本課程學(xué)習(xí)的是什么？學(xué)習(xí)在思考問題時(shí)，不僅按人的邏輯方式思考，也按計(jì)算機(jī)的邏輯思維方式思考學(xué)習(xí)在解決問題時(shí)，不僅考慮人的處理方式，也要考慮計(jì)算機(jī)的處理方式我是你親密的朋友，你要理解和尊重我，也要能被我理解。對(duì)你而言，是一場(chǎng)有趣的思維體操；對(duì)我而言，是一座順暢溝通的橋梁寫在前面的話如何和我聯(lián)系？辦公室：電子樓201辦公電話：Mobilmail：christina_tingting@126.com

考試方式閉卷筆試平時(shí)成績(jī)(30%)到課率作業(yè)上機(jī)實(shí)習(xí)期終考試（70%）課程設(shè)計(jì)（單獨(dú)測(cè)試）設(shè)計(jì)報(bào)告（30%），程序（40%），答辯（30%）《數(shù)據(jù)結(jié)構(gòu)》課程概況英文名稱

DataStructure先修課程離散數(shù)學(xué),計(jì)算機(jī)高級(jí)語言后續(xù)課程數(shù)據(jù)庫原理與應(yīng)用,操作系統(tǒng),軟件工程等授課學(xué)時(shí)

48學(xué)時(shí)上機(jī)實(shí)踐

16機(jī)時(shí)教學(xué)對(duì)象計(jì)算機(jī)科學(xué)與技術(shù)專業(yè),信息工程專業(yè)參考文獻(xiàn)教材：嚴(yán)蔚敏，吳偉民。數(shù)據(jù)結(jié)構(gòu)（C語言版），清華大學(xué)出版社，2010.4配套習(xí)題：數(shù)據(jù)結(jié)構(gòu)題集（C語言版），嚴(yán)蔚敏等編，清華大學(xué)出版社，2010.4參考教材：數(shù)據(jù)結(jié)構(gòu)（C++版），王艷華，戴小鵬編，武漢大學(xué)出版社，2007.4數(shù)據(jù)結(jié)構(gòu)（C++）復(fù)習(xí)題要與上機(jī)指導(dǎo)，王艷華，戴小鵬，武漢大學(xué)出版社，2007.4數(shù)據(jù)結(jié)構(gòu)考研指導(dǎo)，李春葆等編，清華大學(xué)出版社，2003.1注意：請(qǐng)參看相關(guān)的C/C++的教材課程地位本課程不僅是一般的程序設(shè)計(jì)的基本訓(xùn)練，而且是設(shè)計(jì)和實(shí)現(xiàn)編譯程序、數(shù)據(jù)庫系統(tǒng)、人工智能系統(tǒng)和其它系統(tǒng)程序的重要基礎(chǔ)，是一門核心課程，對(duì)培養(yǎng)計(jì)算機(jī)及有關(guān)專業(yè)人才具有重要意義。

1.熟悉各類典型的數(shù)據(jù)結(jié)構(gòu)的邏輯特性、不同的存儲(chǔ)方法與存儲(chǔ)量、算法及效率的關(guān)系、定義于數(shù)據(jù)結(jié)構(gòu)上的主要基本操作及其算法，了解它們的應(yīng)用環(huán)境,為學(xué)習(xí)后續(xù)課程奠定基礎(chǔ)；

2.進(jìn)一步提高軟件設(shè)計(jì)和編程水平；

3.增強(qiáng)根據(jù)求解問題性質(zhì),選擇合適的數(shù)據(jù)結(jié)構(gòu)及控制求解算法的時(shí)間與空間復(fù)雜性的能力。課程要求知識(shí)體系數(shù)據(jù)結(jié)構(gòu)在軟件從業(yè)人員的知識(shí)與技能結(jié)構(gòu)中的地位系統(tǒng)分析員需求分析系統(tǒng)設(shè)計(jì)高級(jí)程序員詳細(xì)設(shè)計(jì)程序設(shè)計(jì)程序員、初級(jí)程序員程序設(shè)計(jì)程序測(cè)試數(shù)據(jù)結(jié)構(gòu)在軟件從業(yè)人員的知識(shí)與技能結(jié)構(gòu)中的地位編程語言解決問題的思想

任何受過專業(yè)訓(xùn)練的程序員，對(duì)“數(shù)據(jù)結(jié)構(gòu)”這門課程中涉及到的各種數(shù)據(jù)結(jié)構(gòu)都不會(huì)陌生，但是在實(shí)際的編程工作中，大部分的數(shù)據(jù)結(jié)構(gòu)都不會(huì)用到，而且也永遠(yuǎn)都不會(huì)用到。雖然如此，深入地理解基本數(shù)據(jù)結(jié)構(gòu)的概念和實(shí)現(xiàn)細(xì)節(jié)，仍然是每個(gè)程序員的任務(wù)。這不僅僅是因?yàn)?，掌握這些知識(shí)將有利于更加正確和靈活地應(yīng)用它們，而且也是因?yàn)椋瑢?duì)于語言背后的實(shí)現(xiàn)細(xì)節(jié)的求知欲是一個(gè)優(yōu)秀程序員的素質(zhì)。

--摘自《最基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)》為什么要學(xué)數(shù)據(jù)結(jié)構(gòu)？數(shù)據(jù)結(jié)構(gòu)研究什么？重新理解算法。如何分析算法的優(yōu)劣？第一章概論第一問題：

為什么要學(xué)數(shù)據(jù)結(jié)構(gòu)Data

Structure？電子計(jì)算機(jī)的主要用途：早期：主要用于數(shù)值計(jì)算。后來：

處理逐漸擴(kuò)大到非數(shù)值計(jì)算領(lǐng)域（能處理多種復(fù)雜的具有一定結(jié)構(gòu)關(guān)系的數(shù)據(jù)）。1）數(shù)值問題例1已知：游泳池的長len和寬wide，求面積area◆設(shè)計(jì)求解問題的方法◆

編程main(){ intlen,wide,area;

scanf(“%d%d%\n”,&l,&w);

area=len*wide;

printf(“area=%d”,area);}◆建模型：

問題涉及的對(duì)象：游泳池的長len寬wide，面積area；

對(duì)象之間的關(guān)系：area=lenwide數(shù)值計(jì)算解決問題的一般步驟：在計(jì)算機(jī)發(fā)展初期，人們主要應(yīng)用計(jì)算機(jī)來完成科學(xué)計(jì)算，即處理數(shù)值計(jì)算問題，對(duì)于這類問題，可以通過抽象出合適的數(shù)學(xué)模型，然后設(shè)計(jì)一個(gè)相應(yīng)的算法來解決。數(shù)學(xué)模型→選擇計(jì)算機(jī)語言→編出程序→測(cè)試→最終解答。數(shù)值計(jì)算的關(guān)鍵是：如何得出數(shù)學(xué)模型（方程）？非數(shù)值計(jì)算問題：隨著計(jì)算機(jī)應(yīng)用領(lǐng)域的不斷擴(kuò)大，計(jì)算機(jī)更多地應(yīng)用于處理非數(shù)值計(jì)算問題，這類問題涉及到數(shù)據(jù)元素間復(fù)雜的相互關(guān)系，一般無法用數(shù)學(xué)方程來描述。2）非數(shù)值問題例2已知某級(jí)學(xué)生情況,要求分班按入學(xué)成績(jī)排列順序。

學(xué)號(hào)姓名性別出生日期籍貫入學(xué)成績(jī)所在班級(jí) 00201楊潤生男82/06/01廣州56100計(jì)算機(jī)2

00102石磊男83/12/21汕頭51200計(jì)算機(jī)1

00202李梅女83/02/23陽江53200計(jì)算機(jī)200301馬耀先男82/07/12廣州50900計(jì)算機(jī)3在這類文檔管理的數(shù)學(xué)模型中,計(jì)算機(jī)處理的對(duì)象之間通常存在著一種最簡(jiǎn)單的線性關(guān)系,這類數(shù)學(xué)模型稱為線性模型。例

電話號(hào)碼查詢問題：（1）按順序存儲(chǔ)方式：須遍歷表（2）按姓氏索引方式：索引要寫出好的查找算法，取決于這張表的結(jié)構(gòu)及存儲(chǔ)方式。電話號(hào)碼表的結(jié)構(gòu)和存儲(chǔ)方式?jīng)Q定了查找（算法）的效率。非數(shù)值計(jì)算問題：例

田徑賽的時(shí)間安排問題（無向圖的著色問題）：設(shè)有六個(gè)比賽項(xiàng)目，規(guī)定每個(gè)選手至多可參加三個(gè)項(xiàng)目，有五人報(bào)名參加比賽（如下表所示）設(shè)計(jì)比賽日程表，使得在盡可能短的時(shí)間內(nèi)完成比賽。非數(shù)值計(jì)算問題：（1）設(shè)用如下六個(gè)不同的代號(hào)代表不同的項(xiàng)目：跳高跳遠(yuǎn)標(biāo)槍鉛球100米200米A B CDE F（2）用頂點(diǎn)代表比賽項(xiàng)目不能同時(shí)進(jìn)行比賽的項(xiàng)目之間連上一條邊。（3）某選手比賽的項(xiàng)目必定有邊相連（不能同時(shí)比賽）。非數(shù)值計(jì)算問題

----田徑賽的時(shí)間安排問題解法姓名項(xiàng)目1項(xiàng)目2項(xiàng)目3丁一

A

B

E馬二

C

D

張三

C

E

F李四

D

F

A王五

B

FAEBFDC比賽時(shí)間比賽項(xiàng)目1A，C2B，D3E4F只需安排四個(gè)單位時(shí)間進(jìn)行比賽多叉路口交通燈管理問題

為了設(shè)計(jì)一個(gè)交通信號(hào)燈的管理系統(tǒng)，首先需要分析一下所有車輛的行駛路線的沖突問題。這個(gè)問題可以歸結(jié)為對(duì)車輛的可能行駛方向作某種分組，對(duì)分組的要求是使任一個(gè)組中各個(gè)方向行駛的車輛可以同時(shí)安全行駛而不發(fā)生碰撞。

根據(jù)這個(gè)路口的實(shí)際情況可以確定13個(gè)可能通行方向：A→B，A→C，A→D，B→A，B→C，B→D，D→A，D→B，D→C，E→A，E→B，E→C，E→D?？梢园袮→B簡(jiǎn)寫成AB，用一個(gè)結(jié)點(diǎn)表示，在不能同時(shí)行駛問題分析:的結(jié)點(diǎn)間畫一條連線(表示它們互相沖突)，便可以得到如右圖所示的表示。這樣得到的表示可以稱之為“圖”。例3多叉路口交通燈管理問題ABACADBABCBDDADBDCEAEBECED圖CEDAB求解非數(shù)值計(jì)算的問題：主要考慮的是設(shè)計(jì)出合適的數(shù)據(jù)結(jié)構(gòu)及相應(yīng)的算法。即：首先要考慮對(duì)相關(guān)的各種信息如何表示、組織和存儲(chǔ)？因此，可以認(rèn)為：數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作的學(xué)科?，F(xiàn)實(shí)中對(duì)象之間的關(guān)系線性關(guān)系：如列車中各車箱之間的關(guān)系、排隊(duì)買車票人之間的關(guān)系、一疊盤子中各盤子之間的關(guān)系等。層次關(guān)系：如學(xué)校的組織結(jié)構(gòu)、人的輩分關(guān)系等。網(wǎng)狀關(guān)系：如城市鐵路交通網(wǎng)、電話網(wǎng)、計(jì)算機(jī)網(wǎng)絡(luò)等。實(shí)際問題中對(duì)象之間的關(guān)系——

學(xué)生成績(jī)管理學(xué)號(hào)姓名大學(xué)英語C語言數(shù)據(jù)結(jié)構(gòu)…A07001王萍908595…A07002馬玲808590…A07003張?zhí)m959199…A07004李建708486…A07005黃勇827678…:：：：：：A07001王萍908595學(xué)生成績(jī)表A07002馬玲808590A07003張?zhí)m959199A07004李建708486A07005黃勇827678關(guān)系：線性特征：一個(gè)直接前趨，一個(gè)直接后繼例2書目自動(dòng)檢索系統(tǒng)登錄號(hào)：書名：作者名：分類號(hào)：出版單位：出版時(shí)間：價(jià)格：書目卡片書目文件按書名按作者名按分類號(hào)索引表線性表實(shí)際問題中對(duì)象之間的關(guān)系例2：“井字棋”的人機(jī)對(duì)弈××OO××OOO××OOO××OOO××OOO××OOO××O×OO××OO×O…×××OOO×××OOO關(guān)系：樹型特征：一個(gè)直接前趨，多個(gè)直接后繼…實(shí)際問題中對(duì)象之間的關(guān)系例3：交通圖的最短路徑問題A4A2A6A3A1A554798612關(guān)系：圖型特征：多個(gè)直接前趨，多個(gè)直接后繼第一問題：

為什么要學(xué)數(shù)據(jù)結(jié)構(gòu)？解決非數(shù)值問題的首要任務(wù)是選取一種合適的數(shù)據(jù)結(jié)構(gòu)表示該問題，然后才考慮如何編寫有效的算法。計(jì)算機(jī)處理的大多屬于非數(shù)值計(jì)算問題。什么是數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)義：數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作等的學(xué)科。

數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)專業(yè)的一門核心課程，它的研究對(duì)象為問題求解方法、程序設(shè)計(jì)方法及一些典型數(shù)據(jù)結(jié)構(gòu)的算法。

《數(shù)據(jù)結(jié)構(gòu)》在計(jì)算機(jī)科學(xué)技術(shù)中是一門綜合性的專業(yè)基礎(chǔ)課，計(jì)算機(jī)科學(xué)技術(shù)各個(gè)領(lǐng)域都要用到多種數(shù)據(jù)結(jié)構(gòu)。在我國計(jì)算機(jī)及相關(guān)專業(yè)的教學(xué)計(jì)劃中，它是核心課程之一。在我院教學(xué)計(jì)劃中，《數(shù)據(jù)結(jié)構(gòu)》已成為我院各計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)和信息工程專業(yè)必修課程。其基本內(nèi)容包括：基本數(shù)據(jù)結(jié)構(gòu)，抽象數(shù)據(jù)類型，遞歸算法，復(fù)雜性分析，排序和查找，算法分析等。數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)科學(xué)中所處的地位：什么是數(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í)用的算法簡(jiǎn)潔、高效的程序什么是數(shù)據(jù)結(jié)構(gòu)第二問題

數(shù)據(jù)結(jié)構(gòu)研究什么？數(shù)據(jù)結(jié)構(gòu)涵蓋的內(nèi)容客觀事物的符號(hào)表示，是計(jì)算機(jī)程序加工的原料。它是信息的載體，能被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理。隨著計(jì)算機(jī)軟、硬件的發(fā)展，計(jì)算機(jī)應(yīng)用領(lǐng)域的不斷擴(kuò)大，數(shù)據(jù)的含義也隨之拓廣。文字、表格、圖像、聲音、光和電的輸入等等均可列入數(shù)據(jù)的范疇?！駭?shù)據(jù)(Data)1、基本概念和術(shù)語是數(shù)據(jù)的基本單位，即數(shù)據(jù)這個(gè)集合中的一個(gè)實(shí)體。通常作為整體進(jìn)行考慮和處理。有些情況下，數(shù)據(jù)元素也稱為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄等。一個(gè)數(shù)據(jù)元素可能僅含一個(gè)數(shù)據(jù)項(xiàng)，亦可包含若干個(gè)數(shù)據(jù)項(xiàng)。●數(shù)據(jù)元素(DataElement)1、基本概念和術(shù)語●數(shù)據(jù)項(xiàng)(DataItem)亦稱字段、域,數(shù)據(jù)項(xiàng)是具有獨(dú)立含義的不可分割的最小標(biāo)識(shí)單位?！駭?shù)據(jù)對(duì)象(DataObject)性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。數(shù)據(jù)對(duì)象可以是有限的，也可以是無限的。如：整數(shù)對(duì)象是集合N={0,±1,±2,….}；字母字符的集合等。1、基本概念和術(shù)語●數(shù)據(jù)類型(DataType)簡(jiǎn)稱類型，一個(gè)值的集合和定義在值集上的一組操作的總稱。它顯式地或隱含地規(guī)定了變量或表達(dá)式所有可能的取值范圍以及在這些值上允許進(jìn)行的操作。原子類型(AtomicType)：如C中的標(biāo)量類型（整型、實(shí)型、字符型）以及指針類型等。結(jié)構(gòu)類型(StructuredType）：亦稱結(jié)構(gòu)類型，如C中的數(shù)組、記錄、文件類型等。抽象數(shù)據(jù)類型(AbstractDataType,ADT）：下面有專門介紹。1、基本概念和術(shù)語●數(shù)據(jù)處理(DataProcessing)對(duì)數(shù)據(jù)進(jìn)行諸如查找、插入、刪除、合并、排序、統(tǒng)計(jì)、簡(jiǎn)單計(jì)算、輸入、輸出等的操作過程。1、基本概念和術(shù)語●結(jié)構(gòu)(Structure)相互關(guān)聯(lián)的元素之間的構(gòu)成關(guān)系。這種關(guān)系可以是物理上的，也可以是邏輯上的，或其它關(guān)系。

定義：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。

組成：由某一數(shù)據(jù)對(duì)象及該對(duì)象中所有數(shù)據(jù)成員之間的關(guān)系組成。DataStructure

=（DataObject,Relationships）

數(shù)據(jù)結(jié)構(gòu)是指在程序中信息的邏輯組織方法，一般來說，這種方法也受到所選擇的程序設(shè)計(jì)語言的限制。

●數(shù)據(jù)結(jié)構(gòu)(DataStructure)1、基本概念和術(shù)語數(shù)據(jù)結(jié)構(gòu)可描述為DS=（D，R）有限個(gè)數(shù)據(jù)元素的集合有限個(gè)節(jié)點(diǎn)間關(guān)系的集合

數(shù)據(jù)的邏輯結(jié)構(gòu)：指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶按使用需要建立起來的，呈現(xiàn)在用戶面前的結(jié)構(gòu)形式。數(shù)據(jù)的物理結(jié)構(gòu)：亦稱數(shù)據(jù)的物理結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)，是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)的表示方法，即存儲(chǔ)形式?！駭?shù)據(jù)結(jié)構(gòu)(DataStructure)1、基本概念和術(shù)語1）數(shù)據(jù)元素之間的邏輯關(guān)系，亦稱數(shù)據(jù)的邏輯結(jié)構(gòu)；●數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面（數(shù)據(jù)結(jié)構(gòu)的三要素）2）數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示，亦稱數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)；3）數(shù)據(jù)的運(yùn)算，即對(duì)數(shù)據(jù)施加的操作。2、基本概念和術(shù)語

1．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)

2、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)3、數(shù)據(jù)的運(yùn)算：檢索、排序、插入、刪除、修改等。A．線性結(jié)構(gòu)

B．非線性結(jié)構(gòu)A順序存儲(chǔ)

B鏈?zhǔn)酱鎯?chǔ)線性表?xiàng)ｊ?duì)樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個(gè)主要問題數(shù)據(jù)結(jié)構(gòu)可描述為DS=（D，R）我和你們的邏輯結(jié)構(gòu)是師生結(jié)構(gòu)我和你們?cè)诮淌抑械奈恢酶鶕?jù)要求而不同●數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面例1：

一個(gè)線性表

邏輯結(jié)構(gòu)：哪個(gè)元素是表中第一個(gè)元素；哪個(gè)元素是表中最后一個(gè)元素；哪些元素在一個(gè)給定元素之前或之后；等等。

存儲(chǔ)結(jié)構(gòu)：它的元素在存儲(chǔ)器中是順序地鄰接存放，還是用指針連接在一起的；等等。

運(yùn)算：在表中查找一個(gè)元素；從表中刪去一個(gè)元素；向表中插入一個(gè)元素；等等。1、基本概念和術(shù)語●數(shù)據(jù)的四種基本邏輯結(jié)構(gòu)與四種基本存儲(chǔ)結(jié)構(gòu)1）從邏輯角度看，數(shù)據(jù)可歸結(jié)為四種基本結(jié)構(gòu)：集合、線性結(jié)構(gòu)、樹結(jié)構(gòu)和圖結(jié)構(gòu)2）從存儲(chǔ)角度看，數(shù)據(jù)可歸結(jié)為四種基本結(jié)構(gòu)：順序結(jié)構(gòu)、鏈接結(jié)構(gòu)、索引結(jié)構(gòu)和散列結(jié)構(gòu)1、基本概念和術(shù)語1）數(shù)據(jù)的四種基本邏輯結(jié)構(gòu)●線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系●樹結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一對(duì)多的關(guān)系●圖結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系?！窦希航Y(jié)構(gòu)中的數(shù)據(jù)元素之間除“同屬于一個(gè)集合”的關(guān)系，無其他關(guān)系1）數(shù)據(jù)的四種基本邏輯結(jié)構(gòu)線性結(jié)構(gòu)樹結(jié)構(gòu)圖結(jié)構(gòu)本課程主要討論三種結(jié)構(gòu)例：用圖形表示下列數(shù)據(jù)結(jié)構(gòu)，并指出它們是屬于線性結(jié)構(gòu)還是非線性結(jié)構(gòu)。（1）S=(D,R)D={a,b,c,d,e,f}R={<a,e>,<b,c>,<(c,a>,<e,f>,<f,d>}解：上述表達(dá)式可用圖形表示為：此結(jié)構(gòu)為線性的。b

c

a

e

f

d該結(jié)構(gòu)是非線性的。解：上述表達(dá)式可用圖形表示為：（2）S=(D,R)

D={di|1≤i≤5}

R={(di,dj),i<j}

d1d5d2d4d32）數(shù)據(jù)的四種基本存儲(chǔ)結(jié)構(gòu)●鏈接存儲(chǔ)結(jié)構(gòu)

不要求邏輯上相鄰的結(jié)點(diǎn)其物理位置上亦相鄰，結(jié)點(diǎn)間的邏輯關(guān)系是由附加的指針字段表示的。●順序存儲(chǔ)結(jié)構(gòu)

把邏輯上相鄰的結(jié)點(diǎn)存儲(chǔ)在物理位置上相鄰存儲(chǔ)單元里，結(jié)點(diǎn)間的邏輯關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來體現(xiàn)。

●散列存儲(chǔ)結(jié)構(gòu)

根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址?！袼饕鎯?chǔ)結(jié)構(gòu)

通常在存儲(chǔ)結(jié)點(diǎn)信息的同時(shí)，還建立附加的索引表，索引表中的每一項(xiàng)稱為索引項(xiàng)，索引項(xiàng)的一般形式是：（關(guān)鍵字，地址），關(guān)鍵字是能唯一標(biāo)識(shí)一個(gè)結(jié)點(diǎn)的那些數(shù)據(jù)項(xiàng)。2）數(shù)據(jù)的四種基本存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2）數(shù)據(jù)的四種基本存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

順序存儲(chǔ)結(jié)構(gòu)：把數(shù)據(jù)元素存儲(chǔ)在一塊連續(xù)地址空間的內(nèi)存中，其特點(diǎn)是邏輯上相鄰的數(shù)據(jù)元素在物理上也相鄰，數(shù)據(jù)間的邏輯關(guān)系表現(xiàn)在數(shù)據(jù)元素存儲(chǔ)位置關(guān)系上。指針是指向物理存儲(chǔ)單元地址的變量。由數(shù)據(jù)元素域和指針域組成的一個(gè)結(jié)構(gòu)體稱為結(jié)點(diǎn)。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：使用指針把相互直接關(guān)聯(lián)的結(jié)點(diǎn)(即直接前驅(qū)結(jié)點(diǎn)或直接后繼結(jié)點(diǎn))鏈接起來，其特點(diǎn)是邏輯上相鄰的數(shù)據(jù)元素在物理上不一定相鄰，數(shù)據(jù)間的邏輯關(guān)系表現(xiàn)在結(jié)點(diǎn)的鏈接關(guān)系上。－2.303023.00300041503023.003000415－2.3法1：地址內(nèi)容法2：地址內(nèi)容2字節(jié)例：復(fù)數(shù)3.0－2.3i的兩種存儲(chǔ)方式：元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲(chǔ)地址存儲(chǔ)內(nèi)容Loc(a)=Lo+（i-1)*m順序存儲(chǔ)每個(gè)元素所占用的存儲(chǔ)單元個(gè)數(shù)元素n……..元素i……..元素2元素1存儲(chǔ)內(nèi)容順序存儲(chǔ)結(jié)構(gòu)常用于線性數(shù)據(jù)結(jié)構(gòu)，將邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上相鄰的存儲(chǔ)單元里。順序存儲(chǔ)結(jié)構(gòu)的三個(gè)弱點(diǎn)：1.作插入或刪除操作時(shí)，需移動(dòng)大量元數(shù)。2.長度變化較大時(shí)，需按最大空間分配。3.表的容量難以擴(kuò)充。1536元素21400元素11346元素3∧元素41345h

鏈?zhǔn)酱鎯?chǔ)每個(gè)節(jié)點(diǎn)都由兩部分組成：數(shù)據(jù)域和指針域。數(shù)據(jù)域存放元素本身的數(shù)據(jù)，指針域存放指針。數(shù)據(jù)元素之間邏輯上的聯(lián)系由指針來體現(xiàn)。1536元素21400元素11346元素3∧元素4head

1346元素3

1536

…….

……..

…….

1536元素2

1400

…….

……..

…….∧元素4

1346

1400元素1

1345指針存儲(chǔ)內(nèi)容存儲(chǔ)地址

鏈?zhǔn)酱鎯?chǔ)13451536元素21400元素11346元素3∧元素41345h

鏈?zhǔn)酱鎯?chǔ)1.比順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)密度小

(每個(gè)節(jié)點(diǎn)都由數(shù)據(jù)域和指針愈組成)。2.邏輯上相鄰的節(jié)點(diǎn)物理上不必相鄰。3.插入、刪除靈活

(不必移動(dòng)節(jié)點(diǎn)，只要改變節(jié)點(diǎn)中的指針)。鏈接存儲(chǔ)結(jié)構(gòu)特點(diǎn)：數(shù)據(jù)的操作

從抽象角度，數(shù)據(jù)的操作主要討論某種數(shù)據(jù)類型數(shù)據(jù)應(yīng)具備的操作的邏輯功能，抽象角度下的操作一般和數(shù)據(jù)的邏輯結(jié)構(gòu)一起討論；具體來說，數(shù)據(jù)的操作主要討論操作的具體實(shí)現(xiàn)算法。具體問題的操作實(shí)現(xiàn)必須在數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)確定后才能進(jìn)行。

數(shù)據(jù)結(jié)構(gòu)課程主要討論表、堆棧、隊(duì)列、串、數(shù)組、樹、二叉樹、圖等典型的常用數(shù)據(jù)結(jié)構(gòu)。在討論這些典型數(shù)據(jù)結(jié)構(gòu)時(shí)，主要從它們的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)操作三個(gè)方面進(jìn)行分析討論。1、基本概念和術(shù)語●定義在數(shù)據(jù)結(jié)構(gòu)上的基本操作刪除(Delete)

刪去數(shù)據(jù)結(jié)構(gòu)中某個(gè)指定的數(shù)據(jù)元素。插入(Insert)

在數(shù)據(jù)結(jié)構(gòu)中的指定位置上增添新的數(shù)據(jù)元素。更新(Update)

改變數(shù)據(jù)結(jié)構(gòu)中某個(gè)數(shù)據(jù)元素的值，在概念上等價(jià)于刪除和插入操作的組合。查找(Find)

在數(shù)據(jù)結(jié)構(gòu)中尋找滿足某個(gè)特定要求的數(shù)據(jù)元素(位置或值)。1、基本概念和術(shù)語●定義在數(shù)據(jù)結(jié)構(gòu)上的基本操作排序(Sort)

（在線性結(jié)構(gòu)中）重新安排數(shù)據(jù)元素之間的邏輯順序關(guān)系，使之按值由小到大或大到?。催f增、不降或遞減、不增）的次序排列。注：一般將插入、刪除與修改統(tǒng)稱為更新；查找亦稱搜索(Search)

。

1、基本概念和術(shù)語

同一種邏輯結(jié)構(gòu)采用不同的存儲(chǔ)方法，可以得到不同的存儲(chǔ)結(jié)構(gòu)。選擇何種存儲(chǔ)結(jié)構(gòu)來表示相應(yīng)的邏輯結(jié)構(gòu)，主要是使其運(yùn)算方便及根據(jù)算法的時(shí)空要求來具體確定。常將同一邏輯結(jié)構(gòu)的不同存儲(chǔ)結(jié)構(gòu)以不同的數(shù)據(jù)結(jié)構(gòu)的命名。如線性表——順序表、鏈表、散列表。給定了數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，若定義的運(yùn)算集合及其運(yùn)算的性質(zhì)不同，也可能導(dǎo)致完全不同的數(shù)據(jù)結(jié)構(gòu)。如線性表中的棧、隊(duì)列、順序棧、鏈棧、鏈隊(duì)列。1、基本概念和術(shù)語抽象數(shù)據(jù)類型(AbstractDataType,ADT)是指一個(gè)數(shù)學(xué)模型以及定義在這個(gè)模型上的一組操作。抽象數(shù)據(jù)類型僅取決于它的邏輯特性，與其在計(jì)算集中的表示無關(guān)。即無論其內(nèi)部結(jié)構(gòu)如何變化，只要它的數(shù)學(xué)特性沒有變化，都不影響其外部使用。一個(gè)ADT的定義并不涉及它的實(shí)現(xiàn)細(xì)節(jié)，這些實(shí)現(xiàn)細(xì)節(jié)對(duì)于ADT的用戶是隱蔽的——封裝性/信息隱蔽數(shù)據(jù)結(jié)構(gòu)是ADT的物理實(shí)現(xiàn)。2、抽象數(shù)據(jù)類型(ADT)例2：整數(shù)的數(shù)學(xué)概念和施加于整數(shù)的運(yùn)算構(gòu)成一個(gè)ADT，不同計(jì)算機(jī)中實(shí)現(xiàn)可能不同，其數(shù)學(xué)特性是相同，因此對(duì)用戶完全相同。2、抽象數(shù)據(jù)類型(ADT)例3：一個(gè)整數(shù)線性表的ADT應(yīng)包含下列操作：

插入一個(gè)整數(shù)到線性表尾刪除線性表中特定位置上的整數(shù)在線性表中查找特定整數(shù)ADT包括以下三部分內(nèi)容：ADT的規(guī)格說明(Specification)ADT的表示(Representation)ADT的實(shí)現(xiàn)(Implementation)用三元組表示：ADT=(數(shù)據(jù)對(duì)象D,關(guān)系集R,處理集P)2、抽象數(shù)據(jù)類型(ADT)本書的表示格式：ADT

抽象數(shù)據(jù)類型名

{

數(shù)據(jù)對(duì)象：<數(shù)據(jù)對(duì)象的定義>

數(shù)據(jù)關(guān)系：<數(shù)據(jù)關(guān)系的定義>

基本操作：<基本操作的定義>}ADT

抽象數(shù)據(jù)類型名2、抽象數(shù)據(jù)類型(ADT)用偽碼表示基本操作名(參數(shù)表)

初始條件：<初始條件描述>

操作結(jié)果：<操作結(jié)果描述>

在具體實(shí)現(xiàn)時(shí)，完成任務(wù)的算法、數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)、程序的邏輯組織，甚至采用哪種程序設(shè)計(jì)語言都是可以自由選擇的－－

與具體實(shí)現(xiàn)無關(guān)。

ADT的主要目的之一是對(duì)用戶隱蔽所有的表示方法，算法的詳細(xì)細(xì)節(jié)、實(shí)現(xiàn)操作的具體代碼以及其它所有對(duì)外界不必要的細(xì)節(jié)，都被局限于具體實(shí)現(xiàn)的模塊內(nèi)部，從而實(shí)現(xiàn)了信息的隱蔽。

ADT的一個(gè)重要優(yōu)點(diǎn)是其簡(jiǎn)單性。ADT的目的是將數(shù)據(jù)的本質(zhì)特征、它們的結(jié)構(gòu)及操作同它們的非本質(zhì)的具體表示及實(shí)現(xiàn)細(xì)節(jié)相區(qū)分開來，從而得到了簡(jiǎn)化。2、抽象數(shù)據(jù)類型(ADT)例4：在數(shù)據(jù)結(jié)構(gòu)中，復(fù)數(shù)可定義為一種簡(jiǎn)單的抽象數(shù)據(jù)類型：Complex=(C,R)其中C是含有兩個(gè)實(shí)數(shù)的集合{C1,C2}，R={P}，P是定義在集合C上的一種關(guān)系{<C1,C2>}，有序偶<C1,C2>表示C1是復(fù)數(shù)的實(shí)部，C2是復(fù)數(shù)的虛部。2、抽象數(shù)據(jù)類型(ADT)SpecificationComplex元素（Elements）

元素的集合為兩個(gè)實(shí)數(shù)的笛卡兒乘積

Z

=

R×R

其中R表示實(shí)數(shù)集，Z表示復(fù)數(shù)集。結(jié)構(gòu)（Structure）

Complex的元素之間不存在任何結(jié)構(gòu)，每一個(gè)元素表示定義在復(fù)數(shù)域Z中的一個(gè)孤立的值。抽象數(shù)據(jù)類型Complex的規(guī)格說明：2、抽象數(shù)據(jù)類型(ADT)ADTComplex{DataObjects:D={C1,C2|C1,C2

∈實(shí)數(shù)};DataRelationships:R={<C1,C2>|C1,C2

∈實(shí)數(shù)}Operations:InitComplex(&T,E1,E2)

操作結(jié)果：構(gòu)造復(fù)數(shù)，E1,E2分別代替C1,C2。

Add(&T,E1,E2);

初始條件：復(fù)數(shù)T已知

操作結(jié)果：E1,E2分別加C1,C2Sub(&T,E1,E2);

初始條件：復(fù)數(shù)T已知

操作結(jié)果：E1,E2分別減C1,C2………}ADTComplex抽象數(shù)據(jù)類型Complex的規(guī)格說明：2、抽象數(shù)據(jù)類型(ADT)抽象數(shù)據(jù)類型Complex具體的表示和實(shí)現(xiàn)依賴于所采用的計(jì)算機(jī)語言。用戶可以用某種高級(jí)語言的固有數(shù)據(jù)類型和自定義數(shù)據(jù)類型，并借助于過程和函數(shù)來表示和實(shí)現(xiàn)抽象數(shù)據(jù)類型Complex。C語言表示如下：抽象數(shù)據(jù)類型Complex的表示：2、抽象數(shù)據(jù)類型(ADT)structComplex{realRealPart;realImagPart;}；Operation在Complex上可定義下列操作1）函數(shù)InitComplex生成一個(gè)復(fù)數(shù)Z，Z=x+iyComplexInitComplex(realx,realy);2）函數(shù)Add求兩個(gè)復(fù)數(shù)Z1與Z2之和。ComplexAdd(ComplexZ1,ComplexZ2);或ComplexAdd(ComplexZ,realR1,realR2);3）函數(shù)Sub，求兩個(gè)復(fù)數(shù)Z1與Z2之差ComplexSub(ComplexZ1,ComplexZ2);或ComplexSub(ComplexZ,realR1,realR2);2、抽象數(shù)據(jù)類型(ADT)繼下頁Operation4）函數(shù)Multiply求兩個(gè)復(fù)數(shù)之積ComplexMultiply(ComplexZ1,ComplexZ2);ComplexMultiply(ComplexZ,realR1,realR2);5）函數(shù)GetRealPart取復(fù)數(shù)Z的實(shí)部realGetRealPart(ComplexZ);6）函數(shù)GetImagPart取函數(shù)Z的虛部

realGetImagPart(ComplexZ);2、抽象數(shù)據(jù)類型(ADT)續(xù)上頁以上關(guān)于ADT的定義（規(guī)格說明、表示）沒有涉及到實(shí)現(xiàn)。正象ADT的名字所暗示的那樣，它是作為實(shí)現(xiàn)的公共特征的抽象。但是，從ADT的角度研究數(shù)據(jù)結(jié)構(gòu)的最終目的仍在于應(yīng)用，因此必須仔細(xì)考慮表示方法、算法、實(shí)現(xiàn)的技術(shù)及細(xì)節(jié)。而當(dāng)ADT被實(shí)現(xiàn)時(shí)，ADT中的元素成了數(shù)據(jù)結(jié)構(gòu)的一個(gè)實(shí)例,而那些操作就成了算法。由于在ADT的規(guī)格說明中，只指明了其功能而未指定要采用何種方法，因此，實(shí)現(xiàn)的獨(dú)立性是顯而易見的。抽象數(shù)據(jù)類型Complex的實(shí)現(xiàn)：2、抽象數(shù)據(jù)類型(ADT)ComplexCreate(realx,realy){ComplexZ;Z.RealPart=x;Z.ImagPart=y;returnZ;}ComplexAdd(ComplexZ1,ComplexZ2){ComplexSum;Sum.RealPart=Z1.RealPart+Z2.RealPart;Sum.ImagPart=Z1.ImagPart+Z2.ImagPart;returnSum;}(以下略)……抽象數(shù)據(jù)類型Complex的C語言實(shí)現(xiàn)：2、抽象數(shù)據(jù)類型(ADT)實(shí)現(xiàn)ADT2、抽象數(shù)據(jù)類型(ADT)由于C語言是面向過程的語言，它能支持ADT的實(shí)現(xiàn)，但是不能很好的反映ADT的數(shù)據(jù)隱蔽原則。在Pascal語言中，庫單元(Unit)是ADT的較好表示和實(shí)現(xiàn)。隨著面向?qū)ο蠹夹g(shù)的成熟，用面向?qū)ο笾械膶?duì)象/類來描述和實(shí)現(xiàn)ADT是非常好的方法。這種方法在面向?qū)ο蟪绦蛟O(shè)計(jì)方面已經(jīng)成熟，已經(jīng)廣泛應(yīng)用于不同程序設(shè)計(jì)語言及開發(fā)環(huán)境當(dāng)中（如：C++，ObjectPascal,VB,Java,

PowerBuilder等等）。下面是Complex采用C++的定義：classComplex{private:realRealPart;realImagPart;public:Complex(realx,realy); //構(gòu)造函數(shù)

Complex(Complex&Z); //拷貝構(gòu)造函數(shù)

ComplexAdd(ComplexZ); //加法

ComplexSub(ComplexZ); //減法

ComplexMultiply(ComplexZ); //乘法

realGetRealPart(void); //取實(shí)部

realGetImagPart(void); //取虛部

………}{C++實(shí)現(xiàn)略}C++實(shí)現(xiàn)ADT2、抽象數(shù)據(jù)類型(ADT)3、類C語言語法規(guī)則類C語言是介于偽碼語言和高級(jí)語言之間的一種算法描述語言。使用類C語言描述算法的好處：1.保持C結(jié)構(gòu)清晰、明確直觀等特色；2.但又略去一些次要環(huán)節(jié)，抓住主干精華。2、類C語言語法規(guī)則函數(shù)類型過程名(參數(shù)表){//算法說明語句組;return結(jié)果；}//過程名當(dāng)返回狀態(tài)結(jié)果時(shí)，函數(shù)定義為Status類型。

1）算法以過程或函數(shù)的形式表示3、類C語言語法規(guī)則2）賦值語句簡(jiǎn)單賦值

變量名=表達(dá)式；串聯(lián)賦值

變量1=變量2=···=表達(dá)式；成組賦值

(變量名1,···,變量名k)=(表達(dá)式1,···,表達(dá)式k);結(jié)構(gòu)名=結(jié)構(gòu)名; 結(jié)構(gòu)名=(值1,···,值k)；3、類C語言語法規(guī)則2）賦值語句變換賦值

變量1變量2； if(

條件

)語句1;if(

條件

)語句1;

else語句2；//可以嵌套3）IF語句3、類C語言語法規(guī)則switch(

表達(dá)式){case

條件1：語句1；break;

?

?

?

case

條件n：語句n;break;

default:

語句n+1}4）Switch語句switch{case

條件1：語句1；break;

?

?

?

case

條件n：語句n;break;

default:

語句n+1}3、類C語言語法規(guī)則For語句：

for(

處置表達(dá)式序列;條件;修改表達(dá)式系列)語句；While語句：

while(

條件

)

語句；

Do-While語句：

do{

語句;}while(條件

);5）循環(huán)語句3、類C語言語法規(guī)則6）基本函數(shù)7）布爾運(yùn)算符8）標(biāo)識(shí)符9）常量和類型第二問題

數(shù)據(jù)結(jié)構(gòu)研究什么？運(yùn)算邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)第三問題

重新理解算法Algorithm●算法的概念●算法的描述●算法設(shè)計(jì)的要求●算法效率的度量●算法的存儲(chǔ)空間需求4、算法的描述和算法分析算法==程序？算法是為了描述解決某一問題的方法，而不涉及具體的實(shí)現(xiàn)細(xì)節(jié)。算法存在的辨證關(guān)系

數(shù)據(jù)結(jié)構(gòu)與算法的辨證關(guān)系給定了數(shù)據(jù)的邏輯結(jié)構(gòu)后，對(duì)同一邏輯結(jié)構(gòu)而言，由于存儲(chǔ)結(jié)構(gòu)的不同，定義的運(yùn)算也是不同的。如線性表是一種邏輯結(jié)構(gòu)，若采用順序存儲(chǔ)方法表示，則稱為順序表；若采用鏈?zhǔn)酱鎯?chǔ)方法表示，則稱為鏈表。相同的運(yùn)算在順序表和鏈表上的實(shí)現(xiàn)方法是不同的?！袼惴ǖ母拍?、算法的描述和算法分析算法(Algorithm)是對(duì)特定問題求解步驟的一種描述，是能在計(jì)算機(jī)上經(jīng)過有限時(shí)間完成的、毫不含糊的指令的有限序列。其中每一條指令表示一個(gè)或多個(gè)操作。問題（Problem）是一個(gè)函數(shù)，或是輸入和輸出的一種聯(lián)系。程序（Program）是用計(jì)算機(jī)程序設(shè)計(jì)語言實(shí)現(xiàn)的完成一定功能的代碼。算法的實(shí)現(xiàn)一定是程序，但程序不一定是算法的實(shí)現(xiàn)。4、算法的描述和算法分析算法的五個(gè)重要特性

1）有窮性：執(zhí)行有限步，每步均在有窮時(shí)間內(nèi)完成。2）確定性：對(duì)相同的輸入，必產(chǎn)生相同的輸出，即無二義性。3）可行性：計(jì)算機(jī)可使用已實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來完成。4）輸入：零個(gè)或多個(gè)輸入。5）輸出：一個(gè)或多個(gè)輸出。4、算法的描述和算法分析關(guān)于算法性質(zhì)的另一種描述1、正確性(Correctness)

它必須完成所期望的功能，把每一次輸入轉(zhuǎn)化為正確的輸出。2、具體步驟(ConcreteSteps)

一個(gè)算法應(yīng)該由一系列具體步驟組成。3、確定性(NoAmbiguity)

下一步（通常是指算法描述中的下一步）應(yīng)執(zhí)行的步驟必須明確。4、有限性(Finite)

一個(gè)算法必須由有限步組成。5、可終止性(Terminable)

算法必須可以終止，即不能進(jìn)入死循環(huán)?！袼惴ǖ拿枋?、算法的描述和算法分析一個(gè)算法可以用各種不同的方法來進(jìn)行描述。比如可使用某種高級(jí)語言、匯編語言甚至機(jī)器語言來描述某個(gè)算法，亦可使用偽碼語言或框圖等其它形式來描述它?！袼惴ǖ拿枋?、算法的描述和算法分析描述算法的語言形式1.文字形式:用中文或英文這樣的文字來描述算法。2.偽碼形式:用一種仿程序設(shè)計(jì)語言的語言來描述算法。3.程序設(shè)計(jì)語言形式:用某種程序設(shè)計(jì)語言描述算法。其優(yōu)點(diǎn)是算法不用修改，直接作為程序語句鍵入計(jì)算機(jī)，計(jì)算機(jī)能調(diào)用和運(yùn)行。這里我們采用上講介紹的類C語言來描述算法4、算法的描述和算法分析例:設(shè)計(jì)一個(gè)把存儲(chǔ)在數(shù)組中的有n個(gè)抽象數(shù)據(jù)元素a0,a1,…,an-1逆置的算法，即要求逆置后的數(shù)組中數(shù)據(jù)元素序列為an-1,…,a1,a0,并要求原數(shù)組中的數(shù)據(jù)元素值不能被改變。voidReverse(intn,DataTypea[],DataTypeb[]){inti;for(i=0;i<n;i++)b[i]=a[n-1-i];//把數(shù)組a的元素逆置后賦給數(shù)組b}4、算法的描述和算法分析例1-2:設(shè)計(jì)一個(gè)把存儲(chǔ)在數(shù)組中的有n個(gè)抽象數(shù)據(jù)元素a0,a1,…,an-1逆置的算法，即要求逆置后的數(shù)組中數(shù)據(jù)元素序列為an-1,…,a1,a0,并要求原數(shù)組中的數(shù)據(jù)元素值被改變。voidReverse(intn,DataTypea[]){inti,m=n/2;DataTypetemp;for(i=0;i<m;i++)//進(jìn)行m次調(diào)換{

temp=a[i];a[i]=a[n-1-i];a[n-1-i]=temp;}}在程序設(shè)計(jì)中，對(duì)算法進(jìn)行分析是十分重要的。對(duì)于一個(gè)具體的應(yīng)用實(shí)例，通?？赡苡腥舾蓚€(gè)算法可供選用，應(yīng)判斷哪一個(gè)算法在現(xiàn)有的計(jì)算機(jī)環(huán)境中對(duì)解決某個(gè)問題是最優(yōu)的。例5：寫一函數(shù)，用以計(jì)算1+2+???+n的值，其中n為已知。longSumWork(intn){intsum=0;

for(inti=1;i++;i<=n)sum+=i;returnsum;}

●算法設(shè)計(jì)的要求4、算法的描述和算法分析longBetterSum(intn){return(n+1)*n/2;}●算法設(shè)計(jì)的要求4、算法的描述和算法分析在計(jì)算機(jī)科學(xué)中，通常使用算法的計(jì)算（執(zhí)行）時(shí)間和所需的存儲(chǔ)空間來評(píng)價(jià)算法或程序的優(yōu)劣。在選擇算法時(shí)，除了要考慮算法的運(yùn)算時(shí)間和所需內(nèi)存外，往往還要考慮其它一些重要的因素，即所謂設(shè)計(jì)一個(gè)“好”的算法應(yīng)考慮達(dá)到的下列目標(biāo)。

1）正確性

2）可讀性

3）健壯性

4）效率與低存儲(chǔ)量需求●算法設(shè)計(jì)的要求4、算法的描述和算法分析1）正確性(Correctness)

能滿足具體問題的需求。正確性對(duì)于選擇算法來說，是首要的問題。正確性的四個(gè)層次：

a.程序不含語法錯(cuò)誤；

b.程序?qū)τ谳斎霐?shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果

(要算對(duì))；

c.程序?qū)τ诰倪x擇的典型、苛刻而帶有刁難性的輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果；

d.程序?qū)τ谝磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足規(guī)格說明要求的結(jié)果?！袼惴ㄔO(shè)計(jì)的要求4、算法的描述和算法分析2）可讀性(Readability)希望一個(gè)算法易于理解、易于編碼，也易于調(diào)試。3）健壯性(Robustness)對(duì)于異常的處理能力。能作出判斷，并給出適當(dāng)?shù)奶崾净蚓嫘畔?，以等待操作員的干預(yù)或能自動(dòng)進(jìn)行適當(dāng)處理。4）效率(Efficiency)與低存儲(chǔ)需求效率指算法執(zhí)行時(shí)間。同一問題，算法執(zhí)行時(shí)間越短，效率越高。存儲(chǔ)量需求指算法執(zhí)行過程中所需的最大存儲(chǔ)空間。此所謂時(shí)（執(zhí)行時(shí)間）、空（運(yùn)行空間）效應(yīng)?！袼惴ㄐ实亩攘?、算法的描述和算法分析算法執(zhí)行時(shí)間的度量——時(shí)間復(fù)雜度執(zhí)行時(shí)間取決于下列因素：

a.選用哪種算法

b.問題的規(guī)模（輸入的大小/復(fù)雜程度）；

c.所選用的語言；

d.編譯程序所產(chǎn)生可執(zhí)行代碼的質(zhì)量；

e.機(jī)器執(zhí)行指令的速度。1）事后統(tǒng)計(jì)

對(duì)算法程序的執(zhí)行進(jìn)行計(jì)時(shí)。（有缺陷）2）事前估計(jì)

事先估算的主要因素——問題的規(guī)模?！袼惴ㄐ实亩攘?、算法的描述和算法分析

一個(gè)算法是由控制結(jié)構(gòu)（順序、分支和循環(huán)）和原操作（指固有數(shù)據(jù)類型的操作）構(gòu)成的，算法時(shí)間取決于兩者的綜合效果。但是，為便于比較同一問題的不同算法，通常的做法是：從算法中選取一種對(duì)于所研究的問題（或算法類型）來說是基本運(yùn)算的原操作，以該基本運(yùn)算重復(fù)執(zhí)行的次數(shù)作為算法的時(shí)間量度的依據(jù)。2）事前估計(jì)

●算法效率的度量4、算法的描述和算法分析例6：兩個(gè)n×n矩陣相乘，令乘法運(yùn)算作為基本運(yùn)算for(i=1;i<=n;i++)for(j=1;j<=n;j++){C[i][j]=0;for(k=1;k<=n;k++)C[i][j]+=A[i][k]*B[k][j];};

整個(gè)算法執(zhí)行時(shí)間與乘法操作重復(fù)執(zhí)行的次數(shù)n3成正比，記作T(n)=O(n3).

兩個(gè)n×n矩陣相乘的時(shí)間復(fù)雜度為O(n3).●算法效率的度量4、算法的描述和算法分析定義：某算法執(zhí)行時(shí)間T(n)是O(f(n))，意指存在正的常數(shù)M和n0，使對(duì)于一切n>n0，T(n)≤Mf(n)都成立。如果一個(gè)程序的時(shí)間復(fù)雜度是O(f(n))，就說該程序的運(yùn)行時(shí)間增加率的一個(gè)上界為f(n)，或說T(n)是f(n)的大O函數(shù)。

例7：設(shè)T(n)=n2+4n，則有f(n)=n2，即有：n2+4n=O(n2).因?yàn)榇嬖贛=2，n0=4，使對(duì)于一切n>n0，恒有n2+4n≤2n24、算法的描述和算法分析大O運(yùn)算規(guī)則

規(guī)則一

對(duì)于任何的常數(shù)k和任何的函數(shù)f，恒有kf(n)=O(f(n))，即大O忽略常數(shù)因子。

規(guī)則二若f(n)=O(g(n))且g(n)=O(h(n))，則f(n)=O(h(n))，即大O的概念是傳遞的。

規(guī)則三

若定義max{f(n)，g(n)}為f(n)與g(n)兩者中增長率較快的函數(shù)，則有f(n)+g(n)=O(max{f(n),g(n)}).

規(guī)則四若f1(n)=O(g1(n))且f2(n)=O(g2(n))，則f1(n)?f2(n)=O(g1(n)?g2(n))，即大O符合乘法規(guī)則。有關(guān)數(shù)學(xué)問題：/型不定式極限有關(guān)數(shù)學(xué)定理：羅比塔法則例8

求時(shí)間函數(shù)8nlog(n)+4n3/2的大O.(1)log(n)=O(n1/2)定義

(2)nlog(n)=O(n?n1/2)=O(n3/2)

規(guī)則四

(3)8nlog(n)=8O(n3/2)=O(n3/2)

規(guī)則一

(4)4n3/2=O(n3/2)

規(guī)則一

(5)8nlog(n)+4n3/2

=O(max{8nlog(n)，4n3/2}）規(guī)則三

max{8nlog(n)，4n3/2}=max{O(n3/2)，O(n3/2)}=O(n3/2)8nlog(n)+4n3/2=O(O(n3/2))

所以有=O(n3/2)規(guī)則二

8nlog(n)+4n3/2=O(n3/2).4、算法的描述和算法分析例9:設(shè)數(shù)組a和b在前邊部分已賦值，求如下兩個(gè)n階矩陣相乘運(yùn)算算法的時(shí)間復(fù)雜度。for(i=0;i<n;i++)for(j=0;j<n;j++){c[i][j]=0;//基本語句1for(k=0;k<n;k++) c[i][j]=c[i][j]+a[i][k]*b[k][j];//基本語句2}解:設(shè)基本語句的執(zhí)行次數(shù)為f(n),有f(n)=c1×n2+c2×n3,因 T(n)=f(n)=c1×n2+c2×n3≤c×n3,其中c1,c2,c均為常數(shù)，所以該算法的時(shí)間復(fù)雜度為

T(n)=O(n3)例：求兩個(gè)方陣的乘積C＝A*B＃definen自然數(shù)MATRIXMLT(floatA[n][n],floatB[n][n],floatC[n][n]){inti,j,k;for(i=0;i<n;i++)for(j=0;j<n;j++){C[i][j]=0;for(k=0;k<n;k++)C[i][j]=A[i][k]*B[k][j]}}//n+1//n(n+1)//n*n//n*n*(n+1)//n*n*n

例10:設(shè)n為如下算法處理的數(shù)據(jù)個(gè)數(shù)，求如下算法的時(shí)間復(fù)雜度。

for(i=1;i<=n;i=2*i)cout<<"i="<<i;解:設(shè)基本語句的執(zhí)行次數(shù)為f(n),有2f(n)≤n,即有f(n)≤log2n。因T(n)=f(n)≤log2n≤c×

log2

n,所以該算法的時(shí)間復(fù)雜度為

T(n)=O(log2n)。例11:下邊的算法是用冒泡排序法對(duì)數(shù)字a中的n個(gè)整數(shù)類型的數(shù)據(jù)元素(a[0]~a[n-1])，從小到大進(jìn)行排序，求該算法的時(shí)間復(fù)雜度。voidBubbleSort(inta[],intn){inti,j,flag=1;inttemp;for(i=1;i<n&&flag==1;i++){flag=0;for(j=0;j<n-i;j++){if(a[j]>a[j+1]){flag=1;temp=a[j];a[j]=a[j+1];a[j+1]=temp;}}}}解:設(shè)基本語句的執(zhí)行次數(shù)為f(n),最壞情況下有

f(n)≈n+4*n2/2因 T(n)=f(n)≈n+2*n2≤c*

n2,其中c為常數(shù)，所以該算法的時(shí)間復(fù)雜度為

T(n)=O(n2)。

算法的時(shí)間復(fù)雜度是衡量一個(gè)算法好壞的重要指標(biāo)。一般來說，具有多項(xiàng)式時(shí)間復(fù)雜度的算法，是可接受、可實(shí)際使用的算法;具有指數(shù)時(shí)間復(fù)雜度的算法，是只有當(dāng)n足夠小時(shí)才可使用的算法。例12下面的算法是在一個(gè)有n個(gè)數(shù)據(jù)元素的數(shù)組a中刪除第I個(gè)位置的數(shù)組元素，要求當(dāng)刪除成功時(shí)數(shù)組元素個(gè)數(shù)減1，求該算法的時(shí)間復(fù)雜度。其中數(shù)組下標(biāo)從0至Delete(inta[],int&n,inti){intj;if(i<0||i>=n)return0;//刪除位置錯(cuò)誤，失敗返回f