數(shù)據(jù)結(jié)構(gòu)與算法ch1Introduction

數(shù)據(jù)結(jié)構(gòu)與算法DataStructuresandAlgorithmAnalysis信息工程學(xué)院SchoolofInformationEngineering教材（1）MarkAllenWeiss.

DataStructuresandAlgorithmAnalysisinC++,ThirdEdition,人民郵電出版社，2013.

（2）李春葆.《數(shù)據(jù)結(jié)構(gòu)教程（第3版）》,清華大學(xué)出版社，2009.

References

（1）嚴(yán)蔚敏、吳偉民.《數(shù)據(jù)結(jié)構(gòu)(C語言版)》，清華大學(xué)出版社，2006.

（2）張乃孝.《算法與數(shù)據(jù)結(jié)構(gòu)-C語言描述（第3版）》，高等教育出版社，2012.（3）CliffordA.Shaffer.

DataStructuresandAlgorithmAnalysis,Edition3.2,電子工業(yè)出版社，2011.（電子版教材）第1章緒論

Chapter1Introduction1.1什么是數(shù)據(jù)結(jié)構(gòu)(WhatisDataStructure)1.2算法(Algorithm)1.3算法分析(AlgorithmAnalysis)1.4數(shù)據(jù)結(jié)構(gòu)＋算法＝程序(Program)本章小結(jié)(Summary)練習(xí)及上機(jī)(ExercisesandProjects)1.1.1數(shù)據(jù)結(jié)構(gòu)的定義(DefinitionofDataStucture)1.1.2邏輯結(jié)構(gòu)類型(LogicalStructureType)

1.1.3存儲(chǔ)結(jié)構(gòu)類型(PhysicalStructureType)1.1.4數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型

(DataStructureandDataType)1.1WhatisDataStructure1.1.1DefinitionofDataStucture數(shù)據(jù)(Data)：所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱（包括數(shù)字、字符、聲音、圖像等信息）。數(shù)據(jù)類型(DataType)：數(shù)據(jù)類型定義為：一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總稱。

數(shù)據(jù)元素(DataElement)：能獨(dú)立、完整地描述問題世界中的實(shí)體的最小數(shù)據(jù)單位稱為數(shù)據(jù)元素（也稱記錄）。構(gòu)成數(shù)據(jù)元素的不可分割的數(shù)據(jù)單位，稱為數(shù)據(jù)項(xiàng)（也稱字段）。數(shù)據(jù)對(duì)象(DataObject)：性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集(如整數(shù)數(shù)據(jù)對(duì)象)。

Example:電信工程10級(jí)為一個(gè)學(xué)生數(shù)據(jù)對(duì)象,而其中的“張三”是一個(gè)數(shù)據(jù)元素。

Example1由4個(gè)整數(shù)組成的數(shù)據(jù)對(duì)象D1={20,-30,88,45}Example2由正整數(shù)組成的數(shù)據(jù)對(duì)象D2={1,2,3,...}Example3由26個(gè)字母組成的數(shù)據(jù)對(duì)象D3={A,B,C,...,Z}其中：D1，D3是有窮集，D2是無窮集。DataStructureincludes：

(1)數(shù)據(jù)元素之間的邏輯關(guān)系,即數(shù)據(jù)的邏輯結(jié)構(gòu)(LogicalDataStructure)。(2)數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器中的存儲(chǔ)方式,即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu),也稱為數(shù)據(jù)的物理結(jié)構(gòu)(PhysicalDataStructure)。(3)施加在該數(shù)據(jù)上的操作,即數(shù)據(jù)的運(yùn)算(DataOperation)。

數(shù)據(jù)結(jié)構(gòu)(DataStructure)：是指數(shù)據(jù)以及數(shù)據(jù)元素相互之間的聯(lián)系。可以看作是相互之間存在著某種特定關(guān)系的數(shù)據(jù)元素的集合。因此,有時(shí)把數(shù)據(jù)結(jié)構(gòu)看成是帶結(jié)構(gòu)的數(shù)據(jù)元素的集合。NoNameSexClassNo1張斌男99018劉麗女990234李英女990120陳華男990212王奇男990126董強(qiáng)男99025王萍女9901Table1.1studenttable

Example1.1

有一個(gè)學(xué)生表如表1.1所示。這個(gè)表中的數(shù)據(jù)元素是學(xué)生記錄,每個(gè)數(shù)據(jù)元素由四個(gè)數(shù)據(jù)項(xiàng)(即學(xué)號(hào)、姓名、性別和班號(hào))組成。

該表中的記錄順序反映了數(shù)據(jù)元素之間的邏輯關(guān)系(LogicalRelationship),用學(xué)號(hào)標(biāo)識(shí)每個(gè)學(xué)生記錄,這種邏輯關(guān)系可以表示為：

<1,8>,<8,34>,<34,20>,<20,12>,<12,26>,<26,5>

其中尖括號(hào)“<ai,ai+1>”表示元素ai和ai+1之間是相鄰的,即ai在ai+1之前,ai+1在ai之后。

數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器中的存儲(chǔ)方式就是存儲(chǔ)結(jié)構(gòu)(StorageStructure)。C/C++語言中，通常采用結(jié)構(gòu)體數(shù)組和鏈表兩種方式實(shí)現(xiàn)其存儲(chǔ)結(jié)構(gòu)。存放學(xué)生表的結(jié)構(gòu)體數(shù)組(StructureArray)Stud定義為：

struct{ intno;/*存儲(chǔ)學(xué)號(hào)*/ charname[8];/*存儲(chǔ)姓名*/ charsex[2];/*存儲(chǔ)性別*/ charclass[4];/*存儲(chǔ)班號(hào)*/}Stud[7]={{1,“張斌”,“男”,“9901”},…,{5,"王萍","女","9901"}};結(jié)構(gòu)體數(shù)組Stud各元素在內(nèi)存中順序存放,即第i(0≤i≤6)個(gè)學(xué)生對(duì)應(yīng)的元素Stud[i]存放在第i+1個(gè)學(xué)生對(duì)應(yīng)的元素Stud[i+1]之前,Stud[i+1]正好在Stud[i]之后。9901女王萍5…9901男張斌1Stud[0]Stud[6]Stud數(shù)組起始地址

存放學(xué)生表的鏈表(LinkedList)的結(jié)點(diǎn)類型StudType定義為：

typedefstructstudnode{ intno; /*存儲(chǔ)學(xué)號(hào)*/ charname[8]; /*存儲(chǔ)姓名*/ charsex[2]; /*存儲(chǔ)性別*/ charclass[4]; /*存儲(chǔ)班號(hào)*/ structstudnode*next;/*存儲(chǔ)指向下一個(gè)學(xué)生的指針*/}StudType；鏈表首結(jié)點(diǎn)地址head1張斌男99018劉麗女990234李英女990120陳華男990212王奇男990126董強(qiáng)男99025王萍女9901∧

學(xué)生表構(gòu)成的鏈表如右圖所示。其中的head為第一個(gè)數(shù)據(jù)元素的指針。LinkedListofstudenttable

對(duì)于“學(xué)生表”這種數(shù)據(jù)結(jié)構(gòu),可以進(jìn)行一系列的運(yùn)算(operation),Forexample,insert,delete,query.從前面介紹的兩種存儲(chǔ)結(jié)構(gòu)看到,同樣的運(yùn)算,在不同的存儲(chǔ)結(jié)構(gòu)中,其實(shí)現(xiàn)過程是不同的。

例如,查找學(xué)號(hào)為20的學(xué)生的姓名：對(duì)于Stud數(shù)組,可以從Stud[0]開始比較,Stud[0].no不等于20,再與Stud[1].no比較,…,直到Stud[3].no等于20,返回Stud[3].name。

對(duì)于head為首結(jié)點(diǎn)指針的鏈表,從head所指結(jié)點(diǎn)開始比較,head->no不等于20,從它的next得到下一個(gè)結(jié)點(diǎn)的地址,再與下一個(gè)結(jié)點(diǎn)的no域比較,…,直到某結(jié)點(diǎn)的no域等于20,返回其name域。

為了更確切地描述一種數(shù)據(jù)結(jié)構(gòu),通常采用二元組表示：

B=(K,R)其中,B是一種數(shù)據(jù)結(jié)構(gòu),它由數(shù)據(jù)元素的集合K和K上二元關(guān)系的集合R所組成。其中：K={ki|1≤i≤n,n≥0}R={rj|1≤j≤m,m≥0}

Representationoflogicalstructure：

其中：

ki表示集合K中的第i個(gè)結(jié)點(diǎn)或數(shù)據(jù)元素。n為K中結(jié)點(diǎn)的個(gè)數(shù),特別地,若n=0,則K是一個(gè)空集,因而B也就無結(jié)構(gòu)可言,有時(shí)也可以認(rèn)為它具有任一結(jié)構(gòu)。

rj表示集合R中的第j個(gè)二元關(guān)系(后面均簡(jiǎn)稱關(guān)系)。m為R中關(guān)系的個(gè)數(shù),特別地,若m=0,則R是一個(gè)空集,表明集合K中的元結(jié)點(diǎn)間不存在任何關(guān)系,彼此是獨(dú)立的。

序偶<x,y>(x,y∈K)x為第一結(jié)點(diǎn),y為第二結(jié)點(diǎn)。

x為y的直接前驅(qū)結(jié)點(diǎn)(通常簡(jiǎn)稱前驅(qū)結(jié)點(diǎn))

y為x的直接后繼結(jié)點(diǎn)(通常簡(jiǎn)稱后繼結(jié)點(diǎn))。

若某個(gè)結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn),則稱該結(jié)點(diǎn)為開始結(jié)點(diǎn)；若某個(gè)結(jié)點(diǎn)沒有后繼結(jié)點(diǎn),則稱該結(jié)點(diǎn)為終端結(jié)點(diǎn)。說明：<x,y>表示有向關(guān)系，(x,y)表示無向關(guān)系。采用離散數(shù)學(xué)的表示方法。

例如,采用二元組表示例1.1的學(xué)生表。學(xué)生表中共有7個(gè)結(jié)點(diǎn),依次用k1～k7表示,則對(duì)應(yīng)的二元組表示為B=(K,R),其中：

K={k1,k2,k3,k4,k5,k6,k7} R={r}//只有一種關(guān)系 r={<k1,k2>,<k2,k3>,<k3,k4>,<k4,k5>,<k5,k6>,<k6,k7>}又例如,有如下數(shù)據(jù)即一個(gè)矩陣：

對(duì)應(yīng)的二元組表示為B=(K,R),其中：K={2,6,3,1,8,12,7,4,5,10,9,11}R={r1,r2}其中,r1表示行關(guān)系,r2表示列關(guān)系r1={<2,6>,<6,3>,<3,1>,<8,12>,<12,7>,<7,4>,<5,10>,<10,9>,<9,11>}r2={<2,8>,<8,5>,<6,12>,<12,10>,<3,7>,<7,9>,<1,4>,<4,11>}一個(gè)二維數(shù)組1.1.2LogicalStructureType

由數(shù)據(jù)元素間關(guān)系的不同特性，有下列四類基本的結(jié)構(gòu)：⑴集合結(jié)構(gòu)。數(shù)據(jù)元素間的關(guān)系是“屬于同一個(gè)集合”。集合是元素關(guān)系極為松散的一種結(jié)構(gòu)。(Set)⑵線性結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著一對(duì)一的關(guān)系。(LinearStructure)⑶樹型結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著一對(duì)多的關(guān)系。(Tree)⑷圖形結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著多對(duì)多的關(guān)系，圖形結(jié)構(gòu)也稱作網(wǎng)狀結(jié)構(gòu)。(Graph)1.1.2LogicalStructureType

（1）集合(Set)如果數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)元素之間不考慮關(guān)系問題（無前驅(qū)/后繼之分），則稱這種結(jié)構(gòu)為集合。在集合中，各元素是“平等”的，它們的共同關(guān)系是：都屬于同一個(gè)集合，無其他關(guān)系。集合結(jié)構(gòu)

(2)線性結(jié)構(gòu)(LinearStructure)

結(jié)點(diǎn)之間關(guān)系：一對(duì)一(OnetoOne)

特點(diǎn)：開始結(jié)點(diǎn)和終端結(jié)點(diǎn)都是惟一的,除了開始結(jié)點(diǎn)和終端結(jié)點(diǎn)以外,其余結(jié)點(diǎn)都有且僅有一個(gè)前驅(qū)結(jié)點(diǎn),有且僅有一個(gè)后繼結(jié)點(diǎn)。順序表就是典型的線性結(jié)構(gòu)。…1.1.2LogicalStructureType

Example1L=(20,-5,66,15,44)是一個(gè)線性表Example2一張登記表DL序號(hào)姓名性別年齡

1李剛男25記錄12王霞女29記錄23劉大海男40記錄34李愛林男44記錄4其中：姓名、性別、年齡是數(shù)據(jù)項(xiàng)(item)、數(shù)據(jù)域(field)；(姓名，性別，年齡)是記錄(record),C語言將"記錄"(record)定義為”結(jié)構(gòu)”(struct)；登記表也是一個(gè)線性表。

(3)樹形結(jié)構(gòu)(Tree)

結(jié)點(diǎn)之間關(guān)系：一對(duì)多(OnetoMany)

特點(diǎn)：開始結(jié)點(diǎn)唯一,終端結(jié)點(diǎn)不唯一。除終端結(jié)點(diǎn)以外,每個(gè)結(jié)點(diǎn)有一個(gè)或多個(gè)后續(xù)結(jié)點(diǎn)；除開始結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)有且僅有一個(gè)前驅(qū)結(jié)點(diǎn)。例3家族中父子關(guān)系是一種層次結(jié)構(gòu)--樹T

張一張三張二一張三一張三小張三大

張二張四層次結(jié)構(gòu)：部門之間的隸屬關(guān)系：學(xué)校->系->科->班領(lǐng)導(dǎo)和被領(lǐng)導(dǎo)之間領(lǐng)導(dǎo)關(guān)系：主席->部長(zhǎng)->司長(zhǎng)->處長(zhǎng)->科長(zhǎng)

(4)圖形結(jié)構(gòu)(Graph)

結(jié)點(diǎn)之間關(guān)系：多對(duì)多(ManytoMany)

特點(diǎn)：沒有開始結(jié)點(diǎn)和終端結(jié)點(diǎn)，所有結(jié)點(diǎn)都可能有多個(gè)前驅(qū)結(jié)點(diǎn)和多個(gè)后繼結(jié)點(diǎn)。例4無向圖G

ABDCEFG其中：A、B、C等是頂點(diǎn)(vertex),圖中任意兩個(gè)頂點(diǎn)之間都可能有關(guān)系。網(wǎng)絡(luò)結(jié)構(gòu)：電網(wǎng)，電信網(wǎng)，計(jì)算機(jī)通信網(wǎng)等。1.1.3存儲(chǔ)結(jié)構(gòu)類型(PhysicalStructureType)

數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)方式。

兩方面：內(nèi)容存儲(chǔ)：數(shù)據(jù)結(jié)構(gòu)中的各數(shù)據(jù)元素的內(nèi)容（數(shù)據(jù)），都分別存儲(chǔ)在一個(gè)獨(dú)立的可訪問的存儲(chǔ)區(qū)中;關(guān)系存儲(chǔ)：數(shù)據(jù)元素的存放方式方法，必須能顯示地或隱式地體現(xiàn)數(shù)據(jù)元素間的邏輯關(guān)系。(2)鏈?zhǔn)酱鎯?chǔ)方法

(LinkedStorage)(3)索引存儲(chǔ)方法(IndexingStorage)

(4)散列存儲(chǔ)方法(HashStorage)1.1.3PhysicalStructureType(1)順序存儲(chǔ)方法(SequentialStorage)（1）順序存儲(chǔ)(SequentialStorage)這是一種主要面向線性關(guān)系的存儲(chǔ)方法。對(duì)線性數(shù)據(jù)結(jié)構(gòu)，可將其數(shù)據(jù)元素，按相應(yīng)的線性關(guān)系下的前后次序，存儲(chǔ)在物理存儲(chǔ)器中，使得數(shù)據(jù)元素在此線性關(guān)系下的邏輯次序與它們?cè)诖鎯?chǔ)器中的存放次序一致。這種存儲(chǔ)方式稱為順序方法（也稱連續(xù)方法）。數(shù)據(jù)元素之間的線性關(guān)系由它們的存儲(chǔ)次序體現(xiàn)，而不需要專門存儲(chǔ)。1.1.3PhysicalStructureType（2）鏈?zhǔn)酱鎯?chǔ)(LinkedStorage)

每個(gè)數(shù)據(jù)元素的存儲(chǔ)區(qū)分兩大部分，第一部分為數(shù)據(jù)區(qū)，存儲(chǔ)元素的內(nèi)容；第二部分為指針區(qū)。

（存放該數(shù)據(jù)元素與其它數(shù)據(jù)元素之間的關(guān)系信息，這種關(guān)系信息一般為地址）

通常要借助于程序語言的指針類型來描述。1.1.3PhysicalStructureType（3）索引存儲(chǔ)(IndexingStorage)

索引存儲(chǔ)是面向檢索操作。在存儲(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)。優(yōu)點(diǎn)：檢索速度快。缺點(diǎn)：增加額外的索引表，占用較多的存儲(chǔ)空間。1.1.3PhysicalStructureType（4）散列存儲(chǔ)(HashStorage)

散列存儲(chǔ)（也稱雜湊法）是一種按元素內(nèi)容存儲(chǔ)元素的方法。其基本思想是：設(shè)置一個(gè)函數(shù)，稱為散列函數(shù)：元素內(nèi)容地址；規(guī)定元素內(nèi)容到存儲(chǔ)地址的映射；存儲(chǔ)時(shí)，通過散列函數(shù)求出元素對(duì)應(yīng)的存儲(chǔ)地址，按此地址存儲(chǔ)；讀取時(shí)，通過散列函數(shù)求出元素的存儲(chǔ)地址，按此地址讀取。1.1.3PhysicalStructureType上述四種基本存儲(chǔ)方法，既可以單獨(dú)使用，也可以組合起來對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行存儲(chǔ)映像。同一種邏輯結(jié)構(gòu)采用不同的存儲(chǔ)方法，可以得到不同的存儲(chǔ)結(jié)構(gòu)。選擇何種存儲(chǔ)結(jié)構(gòu)來表示相應(yīng)的邏輯結(jié)構(gòu)，視具體要求而定，主要考慮的是運(yùn)算方便及算法的時(shí)空要求。1.1.3PhysicalStructureType

(1)數(shù)據(jù)類型(DataType)

高級(jí)程序語言中,一般須對(duì)程序中出現(xiàn)的每個(gè)變量、常量或表達(dá)式,明確說明它們所屬的數(shù)據(jù)類型。不同類型的變量,其所能取的值的范圍不同,所能進(jìn)行的操作不同。

數(shù)據(jù)類型是一個(gè)值的集合和定義在此集合上的一組操作的總稱。1.1.4DataStructureandDataType

如C/C++中的int就是整型數(shù)據(jù)類型。它是所有整數(shù)的集合(在16位計(jì)算機(jī)中為－32768~32767的全體整數(shù))和相關(guān)的整數(shù)運(yùn)算(如＋、－、＊、／等)。

(2)抽象數(shù)據(jù)類型(AbstractDataType)

抽象數(shù)據(jù)類型(AbstractDataType簡(jiǎn)寫為ADT)指的是用戶進(jìn)行軟件系統(tǒng)設(shè)計(jì)時(shí)從問題的數(shù)學(xué)模型中抽象出來的邏輯數(shù)據(jù)結(jié)構(gòu)和邏輯數(shù)據(jù)結(jié)構(gòu)上的運(yùn)算,而不考慮計(jì)算機(jī)的具體存儲(chǔ)結(jié)構(gòu)和運(yùn)算的具體實(shí)現(xiàn)算法。

抽象數(shù)據(jù)類型=數(shù)據(jù)元素集合＋抽象運(yùn)算例如,抽象數(shù)據(jù)類型復(fù)數(shù)的定義：ADTComplex{數(shù)據(jù)對(duì)象(DataObject)：

D={e1,e2|e1,e2均為實(shí)數(shù)}數(shù)據(jù)關(guān)系(DataRelation)：

R1={<e1,e2>|e1是復(fù)數(shù)的實(shí)數(shù)部分,e2是復(fù)數(shù)的虛數(shù)部分}e1＋e2i基本操作(BasicOperation)：

AssignComplex(&Z,v1,v2)：構(gòu)造復(fù)數(shù)Z。DestroyComplex(&Z):復(fù)數(shù)Z被銷毀。GetReal(Z,&real):返回復(fù)數(shù)Z的實(shí)部值。GetImag(Z,&Imag):返回復(fù)數(shù)Z的虛部值。Add(z1,z2,&sum):返回兩個(gè)復(fù)數(shù)z1,z2的和。}ADTComplex1.2算法(Algorithm)1.2.1什么是算法(WhatisAlgorithm)

1.2.2算法描述(AlgorithmDescription)

數(shù)據(jù)元素之間的關(guān)系有邏輯關(guān)系和物理關(guān)系,對(duì)應(yīng)的操作有邏輯結(jié)構(gòu)上的操作功能和具體存儲(chǔ)結(jié)構(gòu)上的操作實(shí)現(xiàn)。通常把具體存儲(chǔ)結(jié)構(gòu)上的操作實(shí)現(xiàn)步驟或過程稱為算法。1.2.1什么是算法(WhatisAlgorithm)

算法的五個(gè)重要的特性

(1)有窮性:在有窮步之后結(jié)束。(2)確定性:無二義性。

(3)可行性:可通過基本運(yùn)算有限次執(zhí)行來實(shí)現(xiàn)。(4)有輸入

(5)有輸出

例如：確定性：無二義性。例.{x=5；y=10；z=x+++y；printf(“%d,%d,%d”,x,y,z)；}x+++y解釋為：x+(++y)？(x++)+y？Example1.2考慮下列兩段描述：(1)描述一 voidexam1() { n＝2; while(n%2＝＝0) n＝n+2; printf("%d\n",n); }

(2)描述二 voidexam2() { y=0; x=5/y; printf(“%d,%d\n”,x,y); }

這兩段描述均不能滿足算法的特征,試問它們違反了哪些特征？

解：(1)算法是一個(gè)死循環(huán),違反了算法的有窮性特征。(2)算法包含除零錯(cuò)誤,違反了算法的可行性特征。

本書中采用C/C++語言描述算法。說明：C++語言中提供了一種引用運(yùn)算符“&”,引用是別名,當(dāng)建立引用時(shí),程序用另一個(gè)已定義的變量或?qū)ο?目標(biāo))的名字初始化它；從那時(shí)起,引用作為目標(biāo)的別名而使用,對(duì)引用的改動(dòng)實(shí)際就是對(duì)目標(biāo)的改動(dòng)。注意：TurboC不支持引用類型。1.2.2算法描述(AlgorithmDescription)“引用”的概念例如：inta=4; /*a為普通的整型變量*/int&b=a;/*b是a的引用變量*/這里說明b變量是變量a的引用,b也等于4,之后這兩個(gè)變量同步改變。當(dāng)a改變時(shí)b也同步改變，同樣，當(dāng)b改變時(shí)a也同步改變。1.2.2AlgorithmDescriptionmain(){

inta=2;int&b=a;printf("a=%d,b=%d\n",a,b);/*輸出：a=2,b=2*/

b++;printf("a=%d,b=%d\n",a,b);/*輸出：a=3,b=3*/

a++;printf("a=%d,b=%d\n",a,b);/*輸出：a=4,b=4*/}引用與指針的區(qū)別

引用常用于函數(shù)形參中,采用引用型形參時(shí),在函數(shù)調(diào)用時(shí)將形參的改變回傳給實(shí)參。例如,有如下函數(shù)(其中的形參均為引用型形參)：

voidswap(int&x,int&y){inttmp=x;x=y;y=tmp；}當(dāng)用執(zhí)行語句swap(a,b)時(shí),a和b的值發(fā)生了交換。1.3算法分析(AlgorithmAnalysis)

1.3.1算法時(shí)間復(fù)雜度分析(TimeComplexityAnalysisofAlgorithm)

1.3.2算法空間復(fù)雜度分析

(SpaceComplexityAnalysisofAlgorithm)

一個(gè)算法是由控制結(jié)構(gòu)(順序、分支和循環(huán)三種)和原操作(指固有數(shù)據(jù)類型的操作)構(gòu)成的,則算法時(shí)間取決于兩者的綜合效果?？刂普Z句1原操作控制語句n原操作…一個(gè)算法1.3.1算法時(shí)間復(fù)雜度分析(TimeComplexityAnalysisofAlgorithm)

同一問題可以采用多種算法實(shí)現(xiàn)。如何比較算法執(zhí)行效率？

?算法描述的語言不同

?算法執(zhí)行的環(huán)境不同?其他因素

所以不能用絕對(duì)執(zhí)行時(shí)間進(jìn)行比較

為了便于比較同一問題的不同算法,通常從算法中選取一種對(duì)于所研究的問題來說是基本運(yùn)算的原操作(以下將基本運(yùn)算的原操作簡(jiǎn)稱為基本運(yùn)算)。算法執(zhí)行時(shí)間大致為基本運(yùn)算所需的時(shí)間與其運(yùn)算次數(shù)(也稱為頻度)的乘積。被視為算法基本運(yùn)算的一般是最深層循環(huán)內(nèi)的語句。

在一個(gè)算法中,進(jìn)行基本運(yùn)算的次數(shù)越少,其運(yùn)行時(shí)間也就相對(duì)地越少；基本運(yùn)算次數(shù)越多,其運(yùn)行時(shí)間也就相對(duì)地越多。所以,通常把算法中包含基本運(yùn)算次數(shù)的多少稱為算法的時(shí)間復(fù)雜度,也就是說,一個(gè)算法的時(shí)間復(fù)雜度是指該算法的基本運(yùn)算次數(shù)。

算法中基本運(yùn)算次數(shù)T(n)是問題規(guī)模n的某個(gè)函數(shù)f(n),記作：T(n)=O(f(n))

記號(hào)“O”讀作“大O”(big-Oh),它表示隨問題規(guī)模n的增大算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同?！癘”的形式定義為：

若f(n)是正整數(shù)n的一個(gè)函數(shù),則T(n)=O(f(n))表示存在一個(gè)正的常數(shù)M,使得當(dāng)n≥n0時(shí)都滿足：|T(n)|≤M|f(n)|

也就是只求出T(n)的最高階,忽略其低階項(xiàng)和常系數(shù),這樣既可簡(jiǎn)化T(n)的計(jì)算,又能比較客觀地反映出當(dāng)n很大時(shí),算法的時(shí)間性能。例如,T(n)=3n2-5n+10000=O(n2)本質(zhì)上講，是一種最高數(shù)量級(jí)的比較

一個(gè)沒有循環(huán)的算法的基本運(yùn)算次數(shù)與問題規(guī)模n無關(guān),記作O(1),也稱作常數(shù)階。

一個(gè)只有一重循環(huán)的算法的基本運(yùn)算次數(shù)與問題規(guī)模n的增長(zhǎng)呈線性增大關(guān)系,記作O(n),也稱線性階。

其余常用的還有平方階O(n2)、立方階O(n3)、對(duì)數(shù)階O(log2n)、指數(shù)階O(2n)等。

各種不同數(shù)量級(jí)對(duì)應(yīng)的值存在著如下關(guān)系：O(1)<O(log2n)<O(n)<O(n*log2n)<O(n2)<O(n3)<O(2n)<O(n!)

Example1.4

求兩個(gè)n階方陣的相加C=A+B的算法如下,分析其時(shí)間復(fù)雜度。#defineMAX20/*定義最大的方階*/voidmatrixadd(intn,intA[MAX][MAX],intB[MAX][MAX],intC[MAX][MAX]){ inti,j; for(i=0;i<n;i++) for(j=0;j<n;j++) C[i][j]=A[i][j]+B[i][j];}

該算法中的基本運(yùn)算是兩重循環(huán)中最深層的語句C[i][j]=A[i][j]+B[i][j],分析它的頻度,即：

T(n)==O(n2)Example1.5Giveananalysisoftherunningtimeintfun(intn){inti,j,k,s;s=0;for(i=0;i<=n;i++)for(j=0;j<=i;j++) for(k=0;k<=j;k++)s++;return(s);}基本語句或基本操作

解：該算法的基本操作是語句s++,其頻度：T(n)==O(n3)則該算法的時(shí)間復(fù)雜度為O(n3)。Example1.6Giveananalysisoftherunningtime

voidfunc(intn){inti=0,s=0;while(s<n){i++; s=s+i;}}基本語句

解：對(duì)于while循環(huán)語句，設(shè)執(zhí)行的次數(shù)為m，i從0開始遞增1，直到m為止，有：s=0+1+2+…+m-1=m(m-1)/2，并滿足s=m(m-1)/2<n，則有m＜。T(n)=O()所以，該算法的時(shí)間復(fù)雜度為O()。

Example1.7

有如下算法：voidfun(inta[],intn,intk)/*數(shù)組a共有n個(gè)元素*/{ inti; if(k==n-1) for(i=0;i<n;i++) printf("%d\n",a[i]); else {for(i=k;i<n;i++) a[i]=a[i]+i*i; fun(a,n,k+1); }}調(diào)用上述算法的語句為fun(a,n,0)，求其時(shí)間復(fù)雜度。解：設(shè)fun(a,n,0)的時(shí)間復(fù)雜度為T(n),則fun(a,n,k)的執(zhí)行時(shí)間為T1(n,k)，由fun()算法可知：

T1(n,k)=n 當(dāng)k=n-1時(shí)T1(n,k)=(n-k)+T1(n,k+1)其他情況

則T(n)=T1(n,0)=n+T1(n,1)=n+(n-1)+T1(n,2)=…=n+(n-1)+…+2+T1(n,n-1)=n+(n-1)+…+2+n=O(n2)所以調(diào)用fun(a,n,0)的時(shí)間復(fù)雜度為O(n2)。

空間復(fù)雜度是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用的存儲(chǔ)空間大小的量度,一般也作為問題規(guī)模n的函數(shù),以數(shù)量級(jí)形式給出,記作：S(n)=O(g(n))

若所需額外空間相對(duì)于輸入數(shù)據(jù)量來說是常數(shù),則稱此算法為原地工作。若所需存儲(chǔ)量依賴于特定的輸入,則通常按最壞情況考慮。1.3.2算法空間復(fù)雜度分析

(SpaceComplexityAnalysisofAlgorithm)Example1.8分析例1.4和例1.5的空間復(fù)雜度。解：由于這兩個(gè)算法中臨時(shí)變量的個(gè)數(shù)與問題規(guī)模n無關(guān),所以空間復(fù)雜度均為O(1)。1.4數(shù)據(jù)結(jié)構(gòu)＋算法＝程序DataStructure+Algorithm=program

數(shù)據(jù)結(jié)構(gòu)對(duì)算法的影響主要在兩方面（1）數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)能力

數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)能力強(qiáng)、存儲(chǔ)信息多＝＞算法將需要較好設(shè)計(jì)（時(shí)間少），存儲(chǔ)空間大。時(shí)間和空間的平衡（2）定義在數(shù)據(jù)結(jié)構(gòu)上的操作

在數(shù)據(jù)結(jié)構(gòu)上定義基本操作＝＞算法調(diào)用這些基本操作?；静僮髟酵暾?，算法設(shè)計(jì)就越容易算法基本操作基本算法應(yīng)用程序應(yīng)用程序是通過調(diào)用基本算法實(shí)現(xiàn)的選擇數(shù)據(jù)結(jié)構(gòu)需要考慮的幾個(gè)方面：（1）數(shù)據(jù)結(jié)構(gòu)要適應(yīng)問題的狀態(tài)描述（2）數(shù)據(jù)結(jié)構(gòu)應(yīng)與所選擇的算法相適應(yīng)（3）數(shù)據(jù)結(jié)構(gòu)的選擇同時(shí)要兼顧程序設(shè)計(jì)的方便（4）靈活應(yīng)用已有知識(shí)Example:有若干學(xué)生數(shù)據(jù)（學(xué)生數(shù)小于50），每個(gè)學(xué)生數(shù)據(jù)包含學(xué)號(hào)（每個(gè)學(xué)生學(xué)號(hào)是惟一的，但學(xué)生記錄不一定按學(xué)號(hào)順序存放）、姓名、班號(hào)和若干門課程成績(jī)（每個(gè)學(xué)生所選課程數(shù)目可能不等，但最多不超過6門）。要求設(shè)計(jì)一個(gè)程序輸出每個(gè)學(xué)生的學(xué)號(hào)、姓名和平均分以及每門課程（課程編號(hào)從1～6）的平均分。Solution1:將學(xué)生的全部數(shù)據(jù)項(xiàng)放在一個(gè)表中，一個(gè)學(xué)生的全部數(shù)據(jù)對(duì)應(yīng)一條記錄。由于課程最多可選6門，對(duì)應(yīng)的成績(jī)項(xiàng)也應(yīng)有6個(gè)。對(duì)應(yīng)的數(shù)據(jù)結(jié)構(gòu)如下：structstud{ intno; /*學(xué)號(hào)*/ charname[10]; /*姓名*/ intbno; /*班號(hào)*/ intdeg1; /*課程1分?jǐn)?shù)*/ intdeg2; /*課程2分?jǐn)?shù)*/ intdeg3; /*課程3分?jǐn)?shù)*/ intde