西電數(shù)據(jù)結(jié)構(gòu)教學(xué)課件第1章

教材

數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）嚴(yán)蔚敏，吳偉民作業(yè)及考核作業(yè)：時(shí)間：周二數(shù)量：每次交三分之一考核：期末筆試：50%期末機(jī)試：30%上機(jī)實(shí)驗(yàn)：10%作業(yè)：10%課件

帳號(hào)：courseware_ds密碼：123abcC語(yǔ)言數(shù)據(jù)結(jié)構(gòu)軟件工程掌握基本編程方法掌握數(shù)據(jù)組織和數(shù)據(jù)處理的方法掌握大型軟件開(kāi)發(fā)方法學(xué)習(xí)識(shí)字學(xué)習(xí)寫(xiě)作文學(xué)習(xí)寫(xiě)小說(shuō)基本要求課程關(guān)系與語(yǔ)文學(xué)習(xí)過(guò)程類(lèi)比前期課程數(shù)據(jù)結(jié)構(gòu)計(jì)算機(jī)基礎(chǔ)C語(yǔ)言離散數(shù)學(xué)后期課程操作系統(tǒng)編譯原理數(shù)據(jù)庫(kù)原理軟件工程承上啟下第1章緒論1.1什么是數(shù)據(jù)結(jié)構(gòu)（定義）1.2數(shù)據(jù)結(jié)構(gòu)的內(nèi)容1.3算法1.4算法描述的工具1.5對(duì)算法作性能評(píng)價(jià)1.6關(guān)于學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)第一章緒論計(jì)算機(jī)的應(yīng)用:科學(xué)計(jì)算；控制、管理及數(shù)據(jù)處理等非數(shù)值計(jì)算的處理工作；計(jì)算機(jī)加工的對(duì)象:純粹的數(shù)值；文本、表格和圖像數(shù)據(jù)；如何表示、處理這些新的、具有一定結(jié)構(gòu)的數(shù)據(jù)？《數(shù)據(jù)結(jié)構(gòu)》是一門(mén)什么課程數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題時(shí)處理的操作對(duì)象以及它們之間的關(guān)系和操作等等的學(xué)科。解決數(shù)值計(jì)算問(wèn)題的中心:建立適當(dāng)?shù)臄?shù)學(xué)模型。解決非數(shù)值計(jì)算問(wèn)題的中心:尋找適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)。數(shù)值問(wèn)題:例1，求解梁架結(jié)構(gòu)中的應(yīng)力。數(shù)學(xué)模型:KU=Ma11ann×x1xn…＝b1bn…例2，預(yù)報(bào)人口增長(zhǎng)情況。數(shù)學(xué)模型:dN(t)d

t＝rN(t)N(t)|t=t

＝N00N(t)＝N0e

r

t非數(shù)值問(wèn)題:例1，圖書(shū)館的書(shū)目檢索系統(tǒng)自動(dòng)化問(wèn)題。通過(guò)提供書(shū)名、作者或分類(lèi)信息，你就可以從圖書(shū)館中檢索某一本書(shū)。數(shù)據(jù)結(jié)構(gòu):線性表。D01曲守寧數(shù)據(jù)庫(kù)004S01王永燕數(shù)據(jù)結(jié)構(gòu)003L01潘玉奇程序設(shè)計(jì)002S01周勁數(shù)據(jù)結(jié)構(gòu)001………………………004數(shù)據(jù)庫(kù)002程序設(shè)計(jì)001,003數(shù)據(jù)結(jié)構(gòu)…004曲守寧003王永燕002潘玉奇001周勁004D002L001,003S…例2，計(jì)算機(jī)和人對(duì)奕問(wèn)題。計(jì)算機(jī)可以根據(jù)當(dāng)前棋盤(pán)格局，來(lái)預(yù)測(cè)棋局發(fā)展的趨勢(shì)，甚至最后結(jié)局。數(shù)據(jù)結(jié)構(gòu):對(duì)弈樹(shù)。O××O當(dāng)前格局派生格局O××O××O××O×O××O×O××O×O××O例3，地圖的著色問(wèn)題。對(duì)地圖上的每個(gè)區(qū)域染一種顏色，并且要求相鄰的兩個(gè)區(qū)域不能具有相同顏色。數(shù)據(jù)結(jié)構(gòu):圖。12435671234567紅綠綠藍(lán)紅黑綠1243567用最少的顏色染色數(shù)學(xué)計(jì)算機(jī)硬件計(jì)算機(jī)軟件數(shù)據(jù)結(jié)構(gòu)1.數(shù)據(jù)（Data）對(duì)客觀事物的符號(hào)描述，能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱(chēng)；能被計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的信息的載體。例，數(shù)字：自然數(shù)、整數(shù) 字母：a~z,單詞 圖像： 視頻、音頻信號(hào)等 表格：2.數(shù)據(jù)元素（DataElement）數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位,是數(shù)據(jù)集合的個(gè)體，在計(jì)算機(jī)中通常作為一個(gè)整體進(jìn)行考慮和處理。例，“對(duì)弈樹(shù)”中的一個(gè)格局 書(shū)目信息中的一條書(shū)目數(shù)據(jù)項(xiàng):

一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成。例，一條書(shū)目信息是由書(shū)名、作者名、分類(lèi)等多個(gè)數(shù)據(jù)項(xiàng)組成的數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。例如有一個(gè)學(xué)生表如下所示。這個(gè)表中的數(shù)據(jù)元素是學(xué)生記錄,每個(gè)數(shù)據(jù)元素由四個(gè)數(shù)據(jù)項(xiàng)(即學(xué)號(hào)、姓名、性別和班號(hào))組成。學(xué)號(hào)姓名性別班號(hào)1張斌男99018劉麗女990234李英女990120陳華男990212王奇男990126董強(qiáng)男99025王萍女99013.數(shù)據(jù)結(jié)構(gòu)（DataStructure）數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素集合，

結(jié)構(gòu)（Structure）數(shù)據(jù)元素相互之間的關(guān)系。在形式上可用二元組表示：

Data_Structure=(D,S)D:數(shù)據(jù)元素的有限集

S:D上關(guān)系的有限集D=

{

ki

|1≤i≤n,n≥0}ki表示集合D中的第i個(gè)結(jié)點(diǎn)或數(shù)據(jù)元素n為D中結(jié)點(diǎn)的個(gè)數(shù)若n=0,

則D是一個(gè)空集,

表示D無(wú)結(jié)構(gòu)可言,

有時(shí)也可以認(rèn)為它具有任意的結(jié)構(gòu)S={rj|1≤j≤m,m≥0}rj

表示集合S中的第j個(gè)二元關(guān)系(簡(jiǎn)稱(chēng)關(guān)系)m為S中關(guān)系的個(gè)數(shù)若m=0,

則S是一個(gè)空集,

表明集合D中的元結(jié)點(diǎn)間不存在任何關(guān)系,

彼此是獨(dú)立的

D上的一個(gè)關(guān)系r是序偶的集合,

對(duì)于r中的任一序偶<x,y>(x,y∈D),我們稱(chēng)序偶的第一結(jié)點(diǎn)為第二結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)(通常簡(jiǎn)稱(chēng)前驅(qū)結(jié)點(diǎn)),稱(chēng)第二結(jié)點(diǎn)為第一結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)(通常簡(jiǎn)稱(chēng)后繼結(jié)點(diǎn))。如在<x,y>的序偶中,x為y的前驅(qū)結(jié)點(diǎn),而y為x的后繼結(jié)點(diǎn)。若某個(gè)結(jié)點(diǎn)沒(méi)有前驅(qū),則稱(chēng)該結(jié)點(diǎn)為開(kāi)始結(jié)點(diǎn)；若某個(gè)結(jié)點(diǎn)沒(méi)有后繼,則稱(chēng)該結(jié)點(diǎn)為終端結(jié)點(diǎn)；除此之外的節(jié)點(diǎn)稱(chēng)為內(nèi)部節(jié)點(diǎn)。“尖括號(hào)”表示有向關(guān)系，“圓括號(hào)”表示無(wú)向關(guān)系。

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

Data_Structure=(D,S)其中：

D={k1,k2,k3,k4,k5,k6,k7}

S={<k1,k2>,<k2,k3>,<k3,k4>,<k4,k5>,<k5,k6>,<k6,k7>}邏輯結(jié)構(gòu)圖：可以將數(shù)據(jù)結(jié)構(gòu)用圖形形象地表示出來(lái),圖形中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)著一個(gè)數(shù)據(jù)元素,兩結(jié)點(diǎn)之間的連線對(duì)應(yīng)著關(guān)系中的一個(gè)序偶。上述“學(xué)生表”數(shù)據(jù)結(jié)構(gòu)用下圖的圖形表示。例1，內(nèi)部關(guān)系，復(fù)數(shù)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ù)的虛部。其中:C是數(shù)據(jù)記錄的集合{ai}；R={P}，而P是定義在集合C上的一種關(guān)系{<ai-1,ai>}，其中有序偶<ai-1,ai>表示ai-1是ai的直接前驅(qū)元素，ai是ai-1的直接后繼元素。例2，外部關(guān)系，線性表List=(C，R)OOOOO線性a1a2a3a4a5例3、設(shè)數(shù)據(jù)的結(jié)構(gòu)描述如下：

Tree=(D,R) D={1,2,3,4,5,6} R={<1,2>,<1,3>,<3,4>,<3,5>,<4,6>}

畫(huà)出其邏輯結(jié)構(gòu)圖？1.2數(shù)據(jù)結(jié)構(gòu)的內(nèi)容邏輯結(jié)構(gòu)數(shù)據(jù)元素之間的關(guān)系。邏輯結(jié)構(gòu)可看作是從具體問(wèn)題抽象出來(lái)的數(shù)學(xué)模型。按照邏輯關(guān)系的不同特性分類(lèi)：集合：（同屬于一個(gè)集合）線性結(jié)構(gòu)：（一對(duì)一）非線性結(jié)構(gòu)：樹(shù)型結(jié)構(gòu)：（一對(duì)多）圖形結(jié)構(gòu)：（多對(duì)多）邏輯結(jié)構(gòu)類(lèi)型的分類(lèi)

(1)線性結(jié)構(gòu)所謂線性結(jié)構(gòu),該結(jié)構(gòu)中的結(jié)點(diǎn)之間存在一對(duì)一的關(guān)系。其特點(diǎn)是：開(kāi)始結(jié)點(diǎn)和終端結(jié)點(diǎn)都是惟一的,除了開(kāi)始結(jié)點(diǎn)和終端結(jié)點(diǎn)以外,其余結(jié)點(diǎn)都有且僅有一個(gè)前驅(qū)結(jié)點(diǎn),有且僅有一個(gè)后繼結(jié)點(diǎn)。

順序表就是典型的線性結(jié)構(gòu)。邏輯結(jié)構(gòu)類(lèi)型

(2)非線性結(jié)構(gòu)所謂非線性結(jié)構(gòu),該結(jié)構(gòu)中的結(jié)點(diǎn)之間存在一對(duì)多或多對(duì)多的關(guān)系。它又可以細(xì)分為樹(shù)形結(jié)構(gòu)和圖形結(jié)構(gòu)兩類(lèi)。

所謂樹(shù)形結(jié)構(gòu),該結(jié)構(gòu)中的結(jié)點(diǎn)之間存在一對(duì)多的關(guān)系。其特點(diǎn)是每個(gè)結(jié)點(diǎn)最多只有一個(gè)前驅(qū),但可以有多個(gè)后繼,可以有多個(gè)終端結(jié)點(diǎn)。非線性結(jié)構(gòu)樹(shù)形結(jié)構(gòu)簡(jiǎn)稱(chēng)為樹(shù)。

A

C

G

J

B

E

D

F

I

H

M

K

L

UNIX文件系統(tǒng)的系統(tǒng)結(jié)構(gòu)圖所謂圖形結(jié)構(gòu),該結(jié)構(gòu)中的結(jié)點(diǎn)之間存在多對(duì)多的關(guān)系。其特點(diǎn)是每個(gè)結(jié)點(diǎn)的前驅(qū)和后繼的個(gè)數(shù)都可以是任意的。因此,可能沒(méi)有開(kāi)始結(jié)點(diǎn)和終端結(jié)點(diǎn),也可能有多個(gè)開(kāi)始結(jié)點(diǎn)、多個(gè)終端結(jié)點(diǎn)。圖形結(jié)構(gòu)簡(jiǎn)稱(chēng)為圖。2.存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）邏輯結(jié)構(gòu)在計(jì)算機(jī)中的存儲(chǔ)映象，是邏輯結(jié)構(gòu)在計(jì)算機(jī)中的實(shí)現(xiàn)，它包括數(shù)據(jù)元素的表示和關(guān)系的表示。順序存儲(chǔ)結(jié)構(gòu)非順序存儲(chǔ)結(jié)構(gòu)（鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)）索引存儲(chǔ)結(jié)構(gòu)散列存儲(chǔ)結(jié)構(gòu)例如用順序存儲(chǔ)法和鏈?zhǔn)酱鎯?chǔ)法表示下面的學(xué)生表。學(xué)號(hào)姓名性別班號(hào)1張斌男99018劉麗女990234李英女990120陳華男990212王奇男990126董強(qiáng)男99025王萍女9901用順序存儲(chǔ)法存放學(xué)生表的結(jié)構(gòu)體定義為：

structStud{ intno;/*學(xué)號(hào)*/ charname[8];/*姓名*/ charsex[2];/*性別*/ charclass[4];/*班號(hào)*/}Studs[7]={ {1,“張斌”,“男”,“9901”}, …,{5,"王萍","女","9901"}};

結(jié)構(gòu)體數(shù)組Studs各元素在內(nèi)存中按順序存放,即第i(1≤i≤6)個(gè)學(xué)生對(duì)應(yīng)的元素Studs[i]存放在第i+1個(gè)學(xué)生對(duì)應(yīng)的元素Studs[i+1]之前,Studs[i+1]正好在Studs[i]之后。1張斌男99018劉麗女990234李英女990120陳華男990212王奇男990126董強(qiáng)男99025王萍女9901用鏈?zhǔn)酱鎯?chǔ)法存放學(xué)生表的結(jié)構(gòu)體定義為：

typedefstructnode{ intno; /*學(xué)號(hào)*/ charname[8]; /*姓名*/ charsex[2]; /*性別*/ charclass[4]; /*班號(hào)*/

structnode*next;

/*指向下個(gè)學(xué)生的指針*/}StudType；head1張斌男99018劉麗女990234李英女990120陳華男990212王奇男990126董強(qiáng)男99025王萍女9901∧學(xué)生表構(gòu)成的鏈表如右圖所示。其中的head為第一個(gè)數(shù)據(jù)元素的指針。學(xué)生表構(gòu)成的鏈表鏈?zhǔn)酱鎯?chǔ)法的缺點(diǎn)：存儲(chǔ)空間占用大無(wú)法隨機(jī)訪問(wèn)鏈?zhǔn)酱鎯?chǔ)法的優(yōu)點(diǎn)：便于修改（插入、刪除、移動(dòng)）

邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)的關(guān)系存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)用計(jì)算機(jī)語(yǔ)言的實(shí)現(xiàn)；如何用計(jì)算機(jī)語(yǔ)言表示數(shù)據(jù)元素之間的各種關(guān)系。存儲(chǔ)結(jié)構(gòu)是邏輯關(guān)系的映象與元素本身的映象。邏輯結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的抽象，存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)，兩者綜合起來(lái)建立了數(shù)據(jù)元素之間的結(jié)構(gòu)關(guān)系。

3.數(shù)據(jù)的運(yùn)算就是施加于數(shù)據(jù)的操作，如查找、添加、修改、刪除等。在數(shù)據(jù)結(jié)構(gòu)中運(yùn)算不僅僅實(shí)加減乘除這些算術(shù)運(yùn)算，它的范圍更為廣泛，常常涉及算法問(wèn)題。 舉例：線性表的初始化、查找、插入、刪除操作等算法的設(shè)計(jì)取決于選定的數(shù)據(jù)（邏輯）結(jié)構(gòu)，而算法的實(shí)現(xiàn)依賴(lài)于采用的存儲(chǔ)結(jié)構(gòu)。抽象運(yùn)算定義在邏輯結(jié)構(gòu)上，而實(shí)現(xiàn)在存儲(chǔ)結(jié)構(gòu)上。數(shù)據(jù)結(jié)構(gòu)的內(nèi)容可歸納為三個(gè)部分：邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和運(yùn)算集合。按某種邏輯關(guān)系組織起來(lái)的一批數(shù)據(jù)，按一定的映象方式把它存放在計(jì)算機(jī)的存儲(chǔ)器中，并在這些數(shù)據(jù)上定義了一個(gè)運(yùn)算的集合，就叫做數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)類(lèi)型在用高級(jí)程序語(yǔ)言編寫(xiě)的程序中,必須對(duì)程序中出現(xiàn)的每個(gè)變量、常量或表達(dá)式,明確說(shuō)明它們所屬的數(shù)據(jù)類(lèi)型。不同類(lèi)型的變量,其所能取的值的范圍不同,所能進(jìn)行的操作不同。數(shù)據(jù)類(lèi)型是一個(gè)值的集合和定義在此集合上的一組操作的總稱(chēng)。

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

(2)抽象數(shù)據(jù)類(lèi)型

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

一個(gè)抽象數(shù)據(jù)類(lèi)型的模塊通常應(yīng)包含定義、表示和實(shí)現(xiàn)三部分。抽象數(shù)據(jù)類(lèi)型的形式定義:

抽象數(shù)據(jù)類(lèi)型是一個(gè)三元組(D，S

，P)其中:D是數(shù)據(jù)對(duì)象S是D上數(shù)據(jù)關(guān)系的有限集P是對(duì)D的基本操作的有限集數(shù)據(jù)對(duì)象的定義數(shù)據(jù)關(guān)系的定義基本操作的定義}ADT抽象數(shù)據(jù)類(lèi)型名{ADT抽象數(shù)據(jù)類(lèi)型名其中,數(shù)據(jù)對(duì)象、數(shù)據(jù)關(guān)系用偽碼描述；基本操作定義格式為 基本操作名（參數(shù)表） 初始條件：〈初始條件描述〉

操作結(jié)果：〈操作結(jié)果描述〉基本操作有兩種參數(shù)：賦值參數(shù)只為操作提供輸入值；引用參數(shù)以&打頭，除可提供輸入值外，還將返回操作結(jié)果?！俺跏紬l件”描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿(mǎn)足的條件，若不滿(mǎn)足，則操作失敗，并返回相應(yīng)出錯(cuò)信息。“操作結(jié)果”說(shuō)明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若初始條件為空，則省略之。例如，定義抽象數(shù)據(jù)類(lèi)型“復(fù)數(shù)”

數(shù)據(jù)對(duì)象：

D＝{e1,e2｜e1,e2∈RealSet}

數(shù)據(jù)關(guān)系：

R1＝{<e1,e2>|e1是復(fù)數(shù)的實(shí)數(shù)部分,

|e2

是復(fù)數(shù)的虛數(shù)部分}ADTComplex{基本操作：

AssignComplex(&Z,v1,v2)操作結(jié)果：構(gòu)造復(fù)數(shù)Z,其實(shí)部和虛部分別被賦以參數(shù)v1和v2的值。

DestroyComplex(&Z)操作結(jié)果：復(fù)數(shù)Z被銷(xiāo)毀。

GetReal(Z,&realPart)初始條件：復(fù)數(shù)已存在。操作結(jié)果：用realPart返回復(fù)數(shù)Z的實(shí)部值。

GetImag(Z,&ImagPart)初始條件：復(fù)數(shù)已存在。操作結(jié)果：用ImagPart返回復(fù)數(shù)Z的虛部值。

Add(z1,z2,&sum)初始條件：z1,z2是復(fù)數(shù)。操作結(jié)果：用sum返回兩個(gè)復(fù)數(shù)z1,z2的和值。}ADTComplex

#include<iostream.h>#include"complex.h"

voidmain()

{

}…

…

complexz1,z2,z3,z4,z; floatRealPart,ImagPart;

AssignComplex(z1,8.0,6.0);

AssignComplex(z2,4.0,3.0);

Add(z1,z2,z3);

Multiply(z1,z2,z4); if(Division(z4,z3,z)){

GetReal(z,RealPart);

GetImag(z,ImagPart);}//ifADT有兩個(gè)重要特征:數(shù)據(jù)抽象

用ADT描述程序處理的實(shí)體時(shí)，強(qiáng)調(diào)的是其本質(zhì)的特征、其所能完成的功能以及它和外部用戶(hù)的接口（即外界使用它的方法）數(shù)據(jù)封裝

將實(shí)體的外部特性和其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)分離，并且對(duì)外部用戶(hù)隱藏其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)抽象數(shù)據(jù)類(lèi)型的表示和實(shí)現(xiàn)

抽象數(shù)據(jù)類(lèi)型需要通過(guò)固有數(shù)據(jù)類(lèi)型(高級(jí)編程語(yǔ)言中已實(shí)現(xiàn)的數(shù)據(jù)類(lèi)型)來(lái)實(shí)現(xiàn)。例如，對(duì)以上定義的復(fù)數(shù)typedefstruct{

floatrealpart；

floatimagpart；}complex；//-----存儲(chǔ)結(jié)構(gòu)的定義//-----基本操作的函數(shù)原型說(shuō)明void

AssignComplex(complex&Z,

floatrealval,floatimagval)；//

構(gòu)造復(fù)數(shù)Z,其實(shí)部和虛部分別被賦以參數(shù)//realval

和imagval

的值float

GetReal(complexZ)；

//返回復(fù)數(shù)Z的實(shí)部值float

Getimag(complexZ)；

//返回復(fù)數(shù)Z的虛部值voidadd(complexz1,complexz2,complex&sum)；

//以sum返回兩個(gè)復(fù)數(shù)z1,z2的和//-----基本操作的實(shí)現(xiàn)voidadd(complexz1,complexz2,complex&sum){

//以sum返回兩個(gè)復(fù)數(shù)z1,z2的和

sum.realpart=z1.realpart+z2.realpart;sum.imagpart=z1.imagpart+z2.imagpart;}

{其它省略}1.3算法1.算法（Algorithm）的定義

Algorithmisafinitesetofruleswhichgivesasequenceofoperationforsolvingaspecifictypeofproblem.(算法是規(guī)則的有限集合，是為解決特定問(wèn)題而規(guī)定的一系列操作。)2.算法的特性

(1)有窮性：有限步驟之內(nèi)正常結(jié)束，不能形成無(wú)窮循環(huán)。

(2)確定性：算法中的每一個(gè)步驟必須有確定含義，無(wú)二義性。

(3)可行性：原則上能精確進(jìn)行，操作可通過(guò)已實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次而完成。

(4)輸入：有多個(gè)或0個(gè)輸入。

(5)輸出：至少有一個(gè)或多個(gè)輸出。

在算法的五大特性中，最基本的是有限性、確定性和可行性。voidexam1(){n=2;while(n%2==0)n=n+2;printf(“%d\n”,n);}voidexam2(){y=0;x=3/y;printf(“%d,%d\n”,x,y);}違反了有窮性。違反了可行性。算法和數(shù)據(jù)結(jié)構(gòu)是兩個(gè)不可分割的統(tǒng)一體程序=數(shù)據(jù)結(jié)構(gòu)+算法數(shù)據(jù)結(jié)構(gòu)通過(guò)算法實(shí)現(xiàn)操作算法根據(jù)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)程序算法設(shè)計(jì)的要求:

正確性正確反映需求(通過(guò)測(cè)試)

可讀性有助于理解、調(diào)試和維護(hù)

健壯性完備的異常和出錯(cuò)處理

高效率與低存儲(chǔ)的需求時(shí)間、空間的要求描述算法的方法自然語(yǔ)言：優(yōu)點(diǎn)——簡(jiǎn)單。缺點(diǎn)——有歧異，表達(dá)復(fù)雜思想不明晰，不能和實(shí)現(xiàn)方式很好結(jié)合高級(jí)程序設(shè)計(jì)語(yǔ)言，如Pascal,C/C++,Java等。優(yōu)點(diǎn)——克服了自然語(yǔ)言的缺點(diǎn)，可直接執(zhí)行。缺點(diǎn)——對(duì)部分問(wèn)題的描述比較煩雜，啰嗦*類(lèi)語(yǔ)言。和高級(jí)程序設(shè)計(jì)語(yǔ)言類(lèi)似，但是對(duì)其中一些比較煩雜的部分進(jìn)行簡(jiǎn)化（原因：算法主要目的是為了清晰的表述思想）*舉例：兩個(gè)數(shù)據(jù)a,b交換空間 自然語(yǔ)言：交換a,b的存儲(chǔ)空間； 高級(jí)語(yǔ)言：{x=a;a=b;b=x;}

類(lèi)語(yǔ)言：ab;//交換空間1.4算法描述的工具衡量算法效率的方法主要有兩大類(lèi)：

事后統(tǒng)計(jì)：利用計(jì)算機(jī)的時(shí)鐘；事前分析估算：用高級(jí)語(yǔ)言編寫(xiě)的程序運(yùn)行的時(shí)間主要取決于如下因素：算法；問(wèn)題規(guī)模；使用語(yǔ)言：級(jí)別越高，效率越低；編譯程序；機(jī)器；1.5對(duì)算法作性能評(píng)價(jià)通常，從算法中選取一種對(duì)于研究的問(wèn)題來(lái)說(shuō)是基本操作的原操作，以該基本操作重復(fù)執(zhí)行的次數(shù)作為算法執(zhí)行的時(shí)間度量。例，for(j=1

；j<=n；j++)X=X+1；for(i=1

；i<=n；i++)(c)for(i=1

；i<=n；i++)X=X+1；(b)X=X+1；(a)基本操作重復(fù)執(zhí)行的次數(shù)分別為1，n，n2頻度:

語(yǔ)句重復(fù)執(zhí)行的次數(shù)稱(chēng)為該語(yǔ)句的頻度，記f(n)。設(shè)算法的問(wèn)題規(guī)模為n；時(shí)間復(fù)雜度:

算法執(zhí)行時(shí)間度量,記T(n)=O(maxlevel(f(n)))。對(duì)算法各基本操作的頻度求和，便可得算法的時(shí)間復(fù)雜度。但實(shí)際中我們所關(guān)心的主要是一個(gè)算法所花時(shí)間的數(shù)量級(jí)，即取算法各基本操作的最大頻度數(shù)量級(jí)。f(n)=1+n+n2+n3T(n)=O(n3)O的數(shù)學(xué)定義:若T(n)和f(n)是定義在正整數(shù)集合上的兩個(gè)函數(shù)，則如果存在正常數(shù)C和n0,使得當(dāng)n≥n0時(shí)，總滿(mǎn)足0≤T(n)≤Cf(n),則記做T(n)=O(f(n))也就是只求出T(n)的最高階（數(shù)量級(jí)）,忽略其低階項(xiàng)和常系數(shù),這樣既可簡(jiǎn)化T(n)的計(jì)算,又能比較客觀地反映出當(dāng)n很大時(shí),算法的時(shí)間性能。2個(gè)N*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];}n+1n(n+1)n2n2(n+1)n3T(n)=O(n3)

（1）x=x+1；其時(shí)間復(fù)雜度為O(1)，我們稱(chēng)之為常量階；（2）for(i=1;i<=n;i++)x=x+1;其時(shí)間復(fù)雜度為O(n)，我們稱(chēng)之為線性階；（3）for(i=1;i<=n;i++)for(j=1;j<=n;j++)x=x+1;其時(shí)間復(fù)雜度為O(n2),我們稱(chēng)之為平方階。此外算法還能呈現(xiàn)的時(shí)間復(fù)雜度有對(duì)數(shù)階O(log2n),指數(shù)階O(2n)等。

常數(shù)階對(duì)數(shù)階線性階線性對(duì)數(shù)階平方階立方階………K次方階指數(shù)階常見(jiàn)的時(shí)間復(fù)雜度，按數(shù)量級(jí)遞增排序：例如：下列程序段：

for(i=1;i<=n;i++)for(j=i;j<=n;j++)x++;語(yǔ)句x++的執(zhí)行頻度為

n+(n-1)+(n-2)+…+3+2+1=n(n+1)/2而該語(yǔ)句執(zhí)行次數(shù)關(guān)于n的增長(zhǎng)率為n2,