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

1數(shù)據(jù)結(jié)構(gòu)與算法（第二版）王昆侖李紅主編中國(guó)鐵道出版社

2007年6月2課程教學(xué)要求：1、上課做好筆記,可以在書(shū)上記錄；

2、按時(shí)、獨(dú)立、認(rèn)真完成作業(yè)；

3、實(shí)驗(yàn)課：認(rèn)真做實(shí)驗(yàn)，課后認(rèn)真寫(xiě)報(bào)告；

4、上課不遲到、不早退；

5、勤奮學(xué)習(xí)，積極思考，提出問(wèn)題，解決問(wèn)題。

?

6、上課時(shí)請(qǐng)不要講話。主講：王立新3第1章數(shù)據(jù)結(jié)構(gòu)和算法概述?

1.1數(shù)據(jù)與數(shù)據(jù)類型

1.2數(shù)據(jù)結(jié)構(gòu)

1.3算法的描述工具－C語(yǔ)言

1.4算法和算法評(píng)價(jià)

1.5算法性能分析41.1數(shù)據(jù)與數(shù)據(jù)類型?1.1.1數(shù)據(jù)和數(shù)據(jù)元素

1.1.2數(shù)據(jù)類型

1.1.3數(shù)據(jù)對(duì)象5數(shù)據(jù)

在計(jì)算機(jī)科學(xué)中，數(shù)據(jù)是指描述客觀事物的數(shù)值、字符、相關(guān)符號(hào)等所有能夠輸入到計(jì)算機(jī)中并能被計(jì)算機(jī)程序處理的符號(hào)的總稱。例如：

數(shù)值數(shù)據(jù)、字符、聲音、圖像、圖形等6

數(shù)據(jù)元素

我們將數(shù)據(jù)中具有獨(dú)立意義的個(gè)體稱為數(shù)據(jù)元素。

數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在程序設(shè)計(jì)時(shí)通常作為一個(gè)整體進(jìn)行考慮和處理。

有時(shí)，一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。7

為實(shí)現(xiàn)圖書(shū)館書(shū)目的自動(dòng)檢索，將與圖書(shū)相關(guān)的數(shù)據(jù)做成如圖所示的表，試分析表中的數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)。10002數(shù)據(jù)結(jié)構(gòu)陳英18.00書(shū)號(hào)書(shū)名作者價(jià)格10001計(jì)算機(jī)原理張明15.00…………答：表中某一本書(shū)的相關(guān)數(shù)據(jù)(表中每一行)都是一個(gè)數(shù)據(jù)元素，每一個(gè)數(shù)據(jù)元素其具有獨(dú)立意義。每一個(gè)數(shù)據(jù)元素由4個(gè)簡(jiǎn)單數(shù)據(jù)項(xiàng)(書(shū)號(hào)、書(shū)名、作者、價(jià)格)組成。數(shù)據(jù)元素也被稱為：記錄、節(jié)點(diǎn)。例1.1：81.1數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)1.1.1數(shù)據(jù)和數(shù)據(jù)元素

?1.1.2數(shù)據(jù)類型

1.1.3數(shù)據(jù)對(duì)象9?數(shù)據(jù)類型概念和定義

是一個(gè)同類值的集合和定義在這個(gè)值集上的一組操作的總稱。

當(dāng)我們?cè)诟呒?jí)程序語(yǔ)言中定義每一種數(shù)據(jù)類型，在程序編譯時(shí)計(jì)算機(jī)語(yǔ)言編譯系統(tǒng)就知道了以下信息：(1)一組性質(zhì)相同的值集合，(2)一個(gè)預(yù)定的存儲(chǔ)體系，(3)定義在這個(gè)值集合上的一組操作。

數(shù)據(jù)類型可分為兩類：數(shù)據(jù)類型簡(jiǎn)單數(shù)據(jù)類型、結(jié)構(gòu)數(shù)據(jù)類型10?簡(jiǎn)單數(shù)據(jù)類型

簡(jiǎn)單類型的數(shù)據(jù)是不可分解的整體，如整數(shù)、實(shí)數(shù)、字符、指針、枚舉量等。

請(qǐng)解釋整型數(shù)據(jù)類型。答：整型數(shù)據(jù)類型通常有short(2字節(jié))、int(2字節(jié))、long(4字節(jié))等形式，其值集為某個(gè)區(qū)間上的整數(shù)。如果整型是兩個(gè)字節(jié)表示的，其值集范圍是：-32768～32767，定義在整型數(shù)據(jù)上的操作為：?jiǎn)文空?+)操作、負(fù)(-)操作，雙目加(+)操作、減(-)操作、乘(*)操作、除(/)操作和取模(MOD)操作等算術(shù)運(yùn)算，雙目關(guān)系(>，<，>=，<=，<>等)操作運(yùn)算以及賦值(=)操作等。

例1.211?結(jié)構(gòu)數(shù)據(jù)類型

結(jié)構(gòu)類型由簡(jiǎn)單數(shù)據(jù)類型按照一定的規(guī)則構(gòu)造而成。結(jié)構(gòu)數(shù)據(jù)類型中還可包含結(jié)構(gòu)數(shù)據(jù)類型，所以結(jié)構(gòu)數(shù)據(jù)類型的數(shù)據(jù)可以分解成若干個(gè)簡(jiǎn)單數(shù)據(jù)類型的數(shù)據(jù)或子結(jié)構(gòu)數(shù)據(jù)類型。也稱作復(fù)合數(shù)據(jù)類型。

12

數(shù)組數(shù)據(jù)類型分析。答：數(shù)組是結(jié)構(gòu)數(shù)據(jù)類型，例如：

charname[20],一維數(shù)組由若干個(gè)同種簡(jiǎn)單數(shù)據(jù)類型順序排列而成，數(shù)組的每個(gè)值的數(shù)據(jù)類型相同；

inta[10][10]，二維數(shù)組看成是一個(gè)以“一行”為一個(gè)元素的一維數(shù)組；而“一行”中簡(jiǎn)單元素有序。

floatb[5][10][15]等。三維數(shù)組看成是一個(gè)以“一個(gè)面(行*列)”為一個(gè)元素的一維數(shù)組；“面”為二維數(shù)組。例1.313

定義表1.1表示的數(shù)據(jù)類型。解：表1.1中每一個(gè)數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)是由長(zhǎng)整型的書(shū)號(hào)、字符型的書(shū)名、作者名以及實(shí)型的價(jià)格，我們可以采用如下的C語(yǔ)言語(yǔ)句來(lái)定義一個(gè)稱為EmployeeType的、新的(用戶自定義)數(shù)據(jù)類型：

typedefstruct{longmun；

charname[10]，book[100]；

floatprice；

}EmployeeType；

例1.410002數(shù)據(jù)結(jié)構(gòu)陳英18.00書(shū)號(hào)書(shū)名作者價(jià)格10001計(jì)算機(jī)原理張明15.00…………14

然后，將這個(gè)名為EmployeeType的新數(shù)據(jù)類型當(dāng)作一個(gè)基本數(shù)據(jù)類型來(lái)使用。我們可以使用該數(shù)據(jù)類型定義一個(gè)變量x：

EmployeeTypex；它表達(dá)的是“變量x將在后面的程序中用到，它指稱一個(gè)大約118個(gè)字節(jié)的主存儲(chǔ)器區(qū)域，用于以二進(jìn)制依次存放四個(gè)值：一個(gè)整數(shù)、兩個(gè)字符串和一個(gè)實(shí)數(shù)”。151.1數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)1.1.1數(shù)據(jù)和數(shù)據(jù)元素

1.1.2數(shù)據(jù)類型

?

1.1.3數(shù)據(jù)對(duì)象16?數(shù)據(jù)對(duì)象

數(shù)據(jù)對(duì)象是數(shù)據(jù)類型的實(shí)例，簡(jiǎn)稱對(duì)象。數(shù)據(jù)對(duì)象舉例。答：例如：25，是整型數(shù)據(jù)對(duì)象?！瓵’，是字符數(shù)據(jù)對(duì)象。

char*p，定義p為一個(gè)字符指針對(duì)象。

inta[10]，定義a為一個(gè)含有10個(gè)整型數(shù)的整型數(shù)組對(duì)象。

Rectangler，定義r為一個(gè)Rectangle類型的對(duì)象。

RECtanglerec，定義rec為一個(gè)RECtangle抽象數(shù)據(jù)類型的對(duì)象。例1.517第1章數(shù)據(jù)結(jié)構(gòu)和算法1.1數(shù)據(jù)與數(shù)據(jù)類型

?

1.2數(shù)據(jù)結(jié)構(gòu)

1.3算法的描述工具－C語(yǔ)言

1.4算法和算法評(píng)價(jià)

1.5算法性能分析18

在計(jì)算機(jī)科學(xué)中，是指數(shù)據(jù)元素之間的關(guān)系，它包括三個(gè)方面的內(nèi)容：(1)數(shù)據(jù)元素間的邏輯關(guān)系，即數(shù)據(jù)的(2)數(shù)據(jù)元素以一定的存儲(chǔ)方式存放在計(jì)算機(jī)的存儲(chǔ)器中，形成數(shù)據(jù)元素的(3)在這些數(shù)據(jù)元素上定義的一組數(shù)據(jù)結(jié)構(gòu)邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)運(yùn)算集合19?數(shù)據(jù)的邏輯結(jié)構(gòu)定義：數(shù)據(jù)元素之間的相互聯(lián)系稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。數(shù)據(jù)元素的邏輯結(jié)構(gòu)的形式定義為一個(gè)二元組：

B＝(K，R)B是一種數(shù)據(jù)結(jié)構(gòu)，

K是數(shù)據(jù)元素的有限集合，K={ki|1

i

n，n

0}R是K上二元關(guān)系的有限集合，R={rj|1

j

m，m

0}。二元關(guān)系可以表示為序偶，<x，y>(x，y

K)，二元關(guān)系也可以表示為無(wú)序?qū)Γ?x，y)(x，y

K)。20

數(shù)據(jù)的邏輯結(jié)構(gòu)可以用圖形形象地表示。用圖形中的每一個(gè)節(jié)點(diǎn)(或叫頂點(diǎn))對(duì)應(yīng)著一個(gè)數(shù)據(jù)元素，用兩節(jié)點(diǎn)間的連線(稱有向邊或弧)對(duì)應(yīng)著關(guān)系中的一個(gè)序偶，其中第一個(gè)元素為起始點(diǎn)，第二個(gè)元素為終止點(diǎn)，箭頭指向終止點(diǎn)。21例：序偶和無(wú)序?qū)Φ膱D形表示如圖所示。(a)無(wú)序?qū)?A，B)，(無(wú)向邊)；(b)序偶<A，B>，<B，A>(也可以用2個(gè)單向箭頭邊)；(c)序偶<A，B>，(有向邊)；(d)序偶<B，A>，(有向邊)

22

根據(jù)數(shù)據(jù)元素之間關(guān)系的不同特性，通常有下列四類基本結(jié)構(gòu)。?線性邏輯結(jié)構(gòu)?樹(shù)型邏輯結(jié)構(gòu)?圖型邏輯結(jié)構(gòu)?集合邏輯結(jié)構(gòu)23

?

線性邏輯結(jié)構(gòu)

例：數(shù)據(jù)的邏輯結(jié)構(gòu)Linearity=(K，R)。其中K={01，02，03，04，05，06，07，08}；

R={r}，r={<05，01>，<01，03>，<03，08>，<08，02>，<02，07>，

<07，04>，<04，06>}。節(jié)點(diǎn)之間是一個(gè)對(duì)一個(gè)關(guān)系，呈線性關(guān)系，是線性邏輯結(jié)構(gòu)。它的特征是：若結(jié)構(gòu)為非空集，則該結(jié)構(gòu)有且只有一個(gè)開(kāi)始節(jié)點(diǎn)和一個(gè)終端節(jié)點(diǎn)，并且所有節(jié)點(diǎn)都最多只有一個(gè)直接前趨和一個(gè)直接后繼。24?

樹(shù)形邏輯結(jié)構(gòu)

例：數(shù)據(jù)的邏輯結(jié)構(gòu)Tree=(K，R)。其中K={A，B，C，D，E，F(xiàn)，G，H，I，J}，

R={r}，r={<A，B>，<A，C>，<A，D>，<B，E>，<B，F(xiàn)>，

<C，G>，<C，H>，<C，I>，<D，J>}。

它的特征是：節(jié)點(diǎn)之間是一個(gè)對(duì)多個(gè)的關(guān)系，一個(gè)節(jié)點(diǎn)可能有一個(gè)直接前趨和多個(gè)直接后繼。呈樹(shù)形關(guān)系，是樹(shù)形數(shù)據(jù)結(jié)構(gòu)(非線性結(jié)構(gòu))。25?圖形邏輯結(jié)構(gòu)

例：數(shù)據(jù)的邏輯結(jié)構(gòu)Graph=(K，R)。其中K={0.1，0.2，0.3，0.4，0.5，0.6，0.7}，

R={r}，r={(0.1，0.2)，(0.1，0.4)，(0.2，0.3)，(0.2，0.6)，(0.2，0.7)，(0.3，0.7)，(0.4，0.6)，(0.5，0.7)}，或者r={<0.1，0.2>，<0.1，0.4>，<0.2，0.3>，<0.2，0.6>，<0.2，0.7>，<0.3，0.7>，<0.4，0.6>，<0.5，0.7>，<0.2，0.1>，<0.4，0.1>，<0.3，0.2>，<0.6，0.2>，<0.7，0.2>，<0.7，0.3>，<0.6，0.4>，<0.7，0.5>}，它的特征是：節(jié)點(diǎn)之間是多個(gè)對(duì)多個(gè)的關(guān)系，一個(gè)節(jié)點(diǎn)可能有多個(gè)直接前趨和多個(gè)直接后繼。呈圖形關(guān)系(非線性結(jié)構(gòu))。

26?

集合邏輯結(jié)構(gòu)例：數(shù)據(jù)的邏輯結(jié)構(gòu)set=(K，R)。其中K={1，2，3，4，5，6，7，8，9，10}；

R={}，二元關(guān)系集為空，表示元素之間不存在關(guān)系，元素彼此是獨(dú)立的。是集合。

集合中數(shù)據(jù)元素之間的關(guān)系是松散的，實(shí)際運(yùn)算時(shí)可以用其它結(jié)構(gòu)來(lái)表示它。27?數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是計(jì)算機(jī)處理具體問(wèn)題時(shí)，須考慮由這個(gè)具體問(wèn)題抽象出的數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式，以便于運(yùn)算。通常情況下，數(shù)據(jù)在計(jì)算機(jī)中存儲(chǔ)方式有以下四種：?順序存儲(chǔ)?鏈接存儲(chǔ)?索引存儲(chǔ)?散列存儲(chǔ)指數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式28?

順序存儲(chǔ)

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

（3，5，6，8，23，12，54）=floata[n]

例1.6

29例1.730?

鏈接存儲(chǔ)

邏輯上相鄰的結(jié)點(diǎn)不一定存儲(chǔ)在物理位置相鄰的存儲(chǔ)單元中，結(jié)點(diǎn)間的邏輯關(guān)系由附加的指針字段來(lái)體現(xiàn)。一組數(shù)據(jù)元素的集合（3，5，6）

365

例1.8

31例1.9設(shè)有一組線性排列的數(shù)據(jù)元素(zhao，qian，sun，li，zhou，wu，zheng，wang)，其鏈接存儲(chǔ)形式如圖所示。32?

索引存儲(chǔ)

該方法在存儲(chǔ)結(jié)點(diǎn)信息的同時(shí)，建立附加的索引表。索引表中的每一個(gè)索引項(xiàng)由唯一標(biāo)識(shí)某結(jié)點(diǎn)的關(guān)鍵字以及該結(jié)點(diǎn)的地址組成。

例1.10

趙－1錢(qián)－23孫－56李－891、趙文36754232、趙五6754328……23、錢(qián)四896543224、錢(qián)進(jìn)3654237……56、孫軍2456398……89、李百5674382……33?

散列存儲(chǔ)

應(yīng)用一個(gè)函數(shù)，將每一個(gè)結(jié)點(diǎn)的關(guān)鍵字作為該函數(shù)的自變量，得到相應(yīng)的函數(shù)值作為該結(jié)點(diǎn)的存儲(chǔ)地址。有函數(shù)y=2x,集合（3，5，6）的存儲(chǔ)：12345678910111213356例1.1134?數(shù)據(jù)的運(yùn)算

正如整數(shù)和實(shí)數(shù)分別對(duì)應(yīng)不同的運(yùn)算一樣，不同邏輯結(jié)構(gòu)的數(shù)據(jù)有不同的運(yùn)算。數(shù)據(jù)運(yùn)算不僅僅是加、減、乘、除、矩陣、微分、積分、方程等等這些數(shù)值計(jì)算問(wèn)題，還包括像在一張表格中，進(jìn)行查找記錄，增加記錄，修改記錄，刪除記錄等等操作運(yùn)算，而怎樣才能進(jìn)行這樣的運(yùn)算呢?在數(shù)據(jù)結(jié)構(gòu)中，這些運(yùn)算常常涉及算法問(wèn)題。例如：線性結(jié)構(gòu)的數(shù)據(jù)數(shù)據(jù)可以非常方便地進(jìn)行插入、刪除數(shù)據(jù)元素，而對(duì)于樹(shù)和圖這樣的非線性結(jié)構(gòu)的數(shù)據(jù)可以有查詢數(shù)據(jù)元素之間的關(guān)系、遍歷數(shù)據(jù)元素等運(yùn)算。

通常情況下，邏輯關(guān)系不同的數(shù)據(jù)分別對(duì)應(yīng)一組運(yùn)算的集合；而數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)反映數(shù)據(jù)在計(jì)算機(jī)內(nèi)部的存儲(chǔ)安排，對(duì)具有相同邏輯關(guān)系的數(shù)據(jù)考慮其不同的物理存儲(chǔ)，目的是為了提高算法的效率。

35?數(shù)據(jù)的運(yùn)算棧的基本運(yùn)算集合：(1)初始化棧：Inistack(S)，將棧S置為一個(gè)空棧(不含任何元素)。(2)進(jìn)棧：Push(S，X)，將元素X插入到棧S中，也稱為“入棧”、“壓入”。(3)出棧：pop(S)，刪除棧S中的棧頂元素，也稱為”退棧”、“刪除”、“彈出”。(4)取棧頂元素：gettop(S)，取棧S中棧頂元素。(5)判棧空：StackEmpty(S)，判斷棧S是否為空，若為空，返回值為true，否則返回值為false。36

根據(jù)以上分析，我們可以看到數(shù)據(jù)結(jié)構(gòu)的概念主要包括如圖所示的三個(gè)方面的主要內(nèi)容：37

我們討論兩數(shù)據(jù)結(jié)構(gòu)是否相同，主要看它們的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和運(yùn)算集合是否相同，這三者中只要有一個(gè)不同，都不能稱這兩個(gè)數(shù)據(jù)結(jié)構(gòu)相同。

設(shè)有兩個(gè)呈線性排列的數(shù)據(jù)分別是{1,3,5,7,9}和{0.1,0.2,0.4,0.6,0.8}（其中的每個(gè)數(shù)是數(shù)據(jù)元素），現(xiàn)將它們分別存放在整型一維數(shù)組A[5]和實(shí)型一維數(shù)組B[5]中?，F(xiàn)在，我們來(lái)分析這兩個(gè)數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)是否相同。例1.1238

首先，這兩個(gè)數(shù)據(jù)都是呈線性排列，則它們的邏輯結(jié)構(gòu)均為線性邏輯結(jié)構(gòu)；其次，它們分別存儲(chǔ)在一維數(shù)組中，這使得邏輯位置相鄰的數(shù)據(jù)元素在物理存儲(chǔ)位置上也相鄰，這樣它們都屬于順序存儲(chǔ)結(jié)構(gòu)；另外，根據(jù)C語(yǔ)言語(yǔ)法規(guī)定，一維數(shù)組A[5]中的數(shù)據(jù)元素間可以進(jìn)行加、減、乘、除和模運(yùn)算，而一維數(shù)組B[5]中的數(shù)據(jù)元素間只能進(jìn)行加、減、乘、除運(yùn)算；這樣，數(shù)據(jù){1,3,5,7,9}和數(shù)據(jù){0.1,0.2,0.4,0.6,0.8}的運(yùn)算集合不同。可以斷定，這兩個(gè)數(shù)據(jù)有著完全不同的數(shù)據(jù)結(jié)構(gòu)。39第1章數(shù)據(jù)結(jié)構(gòu)和算法1.1數(shù)據(jù)與數(shù)據(jù)類型

1.2數(shù)據(jù)結(jié)構(gòu)

?

1.3算法的描述工具－C語(yǔ)言

1.4算法和算法評(píng)價(jià)

1.5算法性能分析40?數(shù)據(jù)類型

?簡(jiǎn)單類型

intfloatdoublechar?構(gòu)造類型數(shù)組int[5]char[25]

結(jié)構(gòu)體struct結(jié)構(gòu)型名

{數(shù)據(jù)類型名成員;};41例1.13structstudent{longnumber;charname[20];charsex;floatscore[3];};structstudentA[50];42?

指針型

inta,b,*p=&a,*q;q=&b；ap11011043定義1.12指針就是變量的地址，一個(gè)變量的地址稱為該變量的指針。指針變量(內(nèi)存單元)是存儲(chǔ)指針(地址)的變量。在Ｃ語(yǔ)言中，允許用一個(gè)變量來(lái)存放指針，這種變量稱為指針變量。在C語(yǔ)言中指針變量的定義和指針變量的引用格式如下：指針變量的定義格式為：類型標(biāo)識(shí)符*指針變量名指針變量的引用格式為：*指針變量名2/18/202444對(duì)指針變量的類型說(shuō)明包括三個(gè)內(nèi)容：(1)指針類型說(shuō)明，即定義變量為一個(gè)指針變量；(2)指針變量名；(3)變量值(指針)所指向的變量的數(shù)據(jù)類型。變量的地址是由編譯系統(tǒng)分配的，對(duì)用戶完全透明，用戶一般可以不知道變量的具體地址。嚴(yán)格地說(shuō)，一個(gè)指針是一個(gè)地址，是一個(gè)常量。而一個(gè)指針變量卻可以被賦予不同的指針值，是變量。但有時(shí)也把指針變量簡(jiǎn)稱為指針。為了避免混淆，我們約定：“指針”是指地址，是常量，“指針變量”是指取值為地址的變量。定義指針的目的是為了通過(guò)指針去訪問(wèn)內(nèi)存單元。45【例1.29】試解釋在Ｃ語(yǔ)言中，變量說(shuō)明語(yǔ)句：

int*p的意義是什么？答：因?yàn)樵谧兞空f(shuō)明語(yǔ)句中，*是類型說(shuō)明符，表示其后的變量是指針類型變量，即：p是一個(gè)指針變量，指針變量名為p，p所指向的變量的數(shù)據(jù)類型為int類型。所以該語(yǔ)句定義了一個(gè)整型指針變量p。注意：在變量說(shuō)明語(yǔ)句中，*是類型說(shuō)明符；在變量引用時(shí)，*是運(yùn)算符，注意區(qū)別。2/18/202446【例1.30】有如下指針說(shuō)明語(yǔ)句：

float*p1；//p1是指向浮點(diǎn)變量的指針變量

char*p2；//p2是指向字符變量的指針變量在使用時(shí)p1和p2可以互相混合使用嗎？答：在使用時(shí)不可以互相混合使用。一個(gè)指針變量只能存儲(chǔ)同類型的變量的地址，例如p1只能指向浮點(diǎn)變量，p2只能指向字符變量，p1和p2不能時(shí)而指向一個(gè)浮點(diǎn)變量，時(shí)而又指向一個(gè)字符變量。47【例1.31】指針說(shuō)明和使用中要注意什么問(wèn)題？答：例如有變量說(shuō)明語(yǔ)句：inta，*p，*q，下面一些問(wèn)題是要注意的。(1)p=&a；//&是地址運(yùn)算符，&a表示變示變量a的地址，p=&a表示把整型變量a的地址賦予整型指針變量p。(2)q=p；//由于p，q均為指向整型變量的指針變量，因此可以相互賦值。(3)*p=&a；//該賦值是錯(cuò)誤的，作為一條賦值語(yǔ)句，被賦值的指針變量p前不能再加“*”說(shuō)明符。因?yàn)樵谧兞恳脮r(shí)，*是取內(nèi)容運(yùn)算符。2/18/202448(4)p=1000；//該賦值是錯(cuò)誤的，指針變量的賦值只能賦予地址，決不能賦予任何其它數(shù)據(jù)，否則將引起錯(cuò)誤。(5)inti=3，*p=&i；//定義了一個(gè)整型變量i且初值為3；定義了一個(gè)整型指針變量p，同時(shí)將i的地址存放于指針變量p中。注意：此種方法是在定義變量并且賦初值，*p=&i的用法是可以的，其等價(jià)于：inti=3，*p；p=&i；。注意與第(3)小題的區(qū)別。49

已知定義：intx，*k=&x；試問(wèn)：表達(dá)式*k，&x，*&x，&*k，&*x和*&k各表示什么？答：對(duì)于*k，表示變量x。對(duì)于&x，&是地址運(yùn)算符，&x表示變示變量x的地址。對(duì)于*&x，表示*k，即變量x。對(duì)于&*k，*k表示變量x，&*k即表示變量x的地址(&x)。對(duì)于*&k，表示變量k。而&*x則存在語(yǔ)法錯(cuò)誤。xk200110110&k20050?用戶自定義類型

typedef類型名1類型名2;

(1)typedefintAB;(2)typedefstruct{ longnumber；……}stutable;stutableA[50];(3)typedefint*POINT;POINTp;例1.1551?運(yùn)算符

－＞指向結(jié)構(gòu)體成員的指針引用

·

結(jié)構(gòu)體成員的引用

structstudent{longnumber;floatscore;}x,*p=&x;p－>score=95;x.number=1001L;例1.1652?函數(shù)

?系統(tǒng)函數(shù)

?內(nèi)存分配函數(shù)（申請(qǐng)內(nèi)存函數(shù)）

void*malloc(intsize)

功能：申請(qǐng)大小為size個(gè)字節(jié)的內(nèi)存。

返回值：若申請(qǐng)成功，則返回所分配的內(nèi)存單元首地址。53?內(nèi)存釋放函數(shù)

voidfree(void*blocd)

功能：釋放由malloc等內(nèi)存分配函數(shù)申請(qǐng)到的內(nèi)存，其首地址放在參數(shù)block中。

返回值：無(wú)注：當(dāng)程序中使用了上述兩個(gè)函數(shù)時(shí)，應(yīng)在程序的開(kāi)頭使用：＃include“alloc.h”54例1.18char*p1;p1=malloc(80);scanf(“%s”,p1);printf(“%s”,p1);free(p1);55?用戶自定義函數(shù)

數(shù)據(jù)類型符函數(shù)名（形參表）形參說(shuō)明；

{函數(shù)體；

return語(yǔ)句；

}函數(shù)返回值的類型return(值or變量)；無(wú)返回值：return;56?函數(shù)調(diào)用

a.函數(shù)名（實(shí)參表）；

b.變量＝函數(shù)名（實(shí)參表）；求三個(gè)整數(shù)的和、積、最大值、最小值。

main(){ inta,b,c,x,y,v,w; scanf(“%d%d%d”,&a,&b,&c); x=sum(a,b,c);y=mul(a,b,c); v=max(a,b,c);w=min(a,b,c); printf(“%d%d%d%d”,x,y,v,w); }例1.192/18/202457 intsum(inta,intb,intc){ return(a+b+c);} intmul(inta,intb,intc){ return(a*b*c);}

intmax(inta,intb,intc){ intx; if(a>b)x=a;elsex=b; if(x<c)x=c; returnx;}下節(jié)58?文件操作

從鍵盤(pán)輸入兩個(gè)學(xué)生數(shù)據(jù)，寫(xiě)入一個(gè)文件中，再讀出這兩個(gè)學(xué)生的數(shù)據(jù)顯示在屏幕上。文件操作的C語(yǔ)言程序例如下。

tructstu{ charname[15]；

intnum；

intage；

charaddr[20]；

}boya[2]，boyb[2]，*pp，*qq；//定義兩個(gè)結(jié)構(gòu)數(shù)組boya和boyb以及兩個(gè)結(jié)構(gòu)指針變量pp和qq例1.2059 voidmain(){FILE*fp； //定義文件指針變量fp inti；

pp=boya； //pp指向boya qq=boyb； //qq指向boyb if((fp=fopen("stu_list"，"w+"))==NULL){ //以讀寫(xiě)方式打開(kāi)d盤(pán)根目錄下的文件“stu_list”，

//如果文件打開(kāi)出錯(cuò)(NULL)則輸出出錯(cuò)信息并退出程序

printf("Cannotopenfilestrikeanykeyexit!")；

exit(1)；

}}60printf("\ninputdata\n")；

for(i=0；i<2；i++，pp++)scanf(“%s%d%d%s”，pp->name，&pp->num，&pp->age，pp->addr)；//輸入二個(gè)學(xué)生數(shù)據(jù)

pp=boya；

fwrite(pp，sizeof(structstu)，2，fp)；

//寫(xiě)入fp文件指針?biāo)傅脑撐募腥?/p>

rewind(fp)； //把文件內(nèi)部位置指針移到文件首

fread(qq，sizeof(structstu)，2，fp)；

//讀出兩塊學(xué)生數(shù)據(jù)到qq指針?biāo)傅慕Y(jié)構(gòu)數(shù)組boybprintf("\n\nname\tnumberageaddr\n")；61

for(i=0；i<2；i++，qq++)printf(“%s\t%5d%5d%7s\n”，qq->name，qq->num，qq->age，qq->addr)；//在屏幕上顯示輸出

fclose(fp)； //關(guān)閉文件fp }該程序執(zhí)行結(jié)果如下：

inputdataJohn100122BeijingTom100221Shanghai<回車(chē)>namenumberageaddrJohn100122BeijingTom100221Shanghai

62?程序測(cè)試

是指在計(jì)算機(jī)上利用輸入數(shù)據(jù)(測(cè)試數(shù)據(jù))來(lái)實(shí)際運(yùn)行該程序，把程序的實(shí)際行為與所期望的行為進(jìn)行比較。如果兩種行為不同，就可判定程序中有問(wèn)題存在。但是，對(duì)于大多數(shù)實(shí)際的程序，可能的用于測(cè)試數(shù)據(jù)的數(shù)量太大了，不可能進(jìn)行窮盡測(cè)試。實(shí)際用來(lái)測(cè)試的輸入數(shù)據(jù)空間的子集稱之為程序測(cè)試測(cè)試集63?

測(cè)試數(shù)據(jù)的設(shè)計(jì)

測(cè)試的目的是找出程序中的錯(cuò)誤。如果用來(lái)尋找錯(cuò)誤的測(cè)試數(shù)據(jù)找不到錯(cuò)誤，那么我們對(duì)該程序的正確性就有了自信心。為此我們必須知道對(duì)于該測(cè)試數(shù)據(jù)，程序的正確結(jié)果應(yīng)是什么。

設(shè)計(jì)測(cè)試數(shù)據(jù)的技術(shù)分為兩類：

1、黑盒法

2、白盒法64黑盒法

黑盒法考慮的是程序的功能，而不是實(shí)際的代碼編寫(xiě)的如何。最流行的黑盒法是I/O分類及因果圖，本節(jié)僅探討I/O分類。在這種方法中，輸入數(shù)據(jù)和(或)輸出數(shù)據(jù)空間被分成若干類，不同類中的數(shù)據(jù)會(huì)使程序所表現(xiàn)出的行為有質(zhì)的不同，而相同類中的數(shù)據(jù)則使程序表現(xiàn)出本質(zhì)上類似的行為。65例1.21

一元二次方程求解的例子中有三種本質(zhì)上不同的行為：一是產(chǎn)生復(fù)數(shù)根，二是產(chǎn)生實(shí)數(shù)根且不同，產(chǎn)生實(shí)數(shù)根且相同?？梢愿鶕?jù)這三種行為把輸入空間分為三類。第一類中的數(shù)據(jù)將產(chǎn)生第一種行為；第二類中的數(shù)據(jù)將產(chǎn)生第二種行為；第三類中的數(shù)據(jù)將產(chǎn)生第三種行為。一個(gè)測(cè)試集應(yīng)至少?gòu)拿恳活愔谐槿∫粋€(gè)輸入數(shù)據(jù)進(jìn)行測(cè)試。66白盒法

白盒法是通過(guò)檢查程序代碼來(lái)設(shè)計(jì)測(cè)試數(shù)據(jù)，以便使測(cè)試數(shù)據(jù)的執(zhí)行結(jié)果能很好地覆蓋程序的語(yǔ)句以及執(zhí)行路徑。

對(duì)一個(gè)測(cè)試集最起碼的要求就是使程序中的每一條語(yǔ)句都至少執(zhí)行一次。這種要求被稱為“語(yǔ)句覆蓋”。67程序調(diào)試問(wèn)題：定義1.17調(diào)試是確定并糾正程序錯(cuò)誤的過(guò)程。在許多情況下，調(diào)試程序主要依靠程序員的經(jīng)驗(yàn)，一個(gè)有經(jīng)驗(yàn)的程序員能夠很快地確定并糾正程序中的錯(cuò)誤。在這里，詳細(xì)地介紹程序調(diào)試問(wèn)題顯然超出了我們課程的范圍，但我們可以提出一些建議，供讀者參考。調(diào)試程序主要采取以下方法：1．邏輯推理的方法。當(dāng)程序出現(xiàn)錯(cuò)誤時(shí)，一般首先用邏輯推理的方法，分析程序或者算法，來(lái)確定錯(cuò)誤語(yǔ)句。2．程序跟蹤的方法。利用調(diào)試工具對(duì)程序進(jìn)行跟蹤，以確定程序什么時(shí)候開(kāi)始出現(xiàn)錯(cuò)誤。2/18/2024683．代碼分離的方法，當(dāng)需要跟蹤得語(yǔ)句太多時(shí)，試著把可疑的代碼分離出來(lái)，專門(mén)跟蹤這段代碼。4．從獨(dú)立函數(shù)開(kāi)始的方法。在測(cè)試和調(diào)試一個(gè)有錯(cuò)的程序時(shí)，從一個(gè)與其他函數(shù)獨(dú)立的函數(shù)開(kāi)始，這個(gè)函數(shù)應(yīng)該是一個(gè)典型的輸入或輸出函數(shù)(請(qǐng)讀者考慮為什么？)。調(diào)試成功之后，再引入一個(gè)還沒(méi)有測(cè)試的函數(shù)。依次下去，調(diào)試的范圍一步一步地?cái)U(kuò)大。這種方法被稱為增量測(cè)試與調(diào)試。69第1章數(shù)據(jù)結(jié)構(gòu)和算法1.1數(shù)據(jù)與數(shù)據(jù)類型

1.2數(shù)據(jù)結(jié)構(gòu)

1.3算法的描述工具－C語(yǔ)言

?

1.4算法和算法評(píng)價(jià)

1.5算法性能分析70?

什么是算法

算法是為解決一個(gè)特定問(wèn)題而采取的確定的有限的步驟，是指令的有限序列。

算法具有輸入、輸出、有窮性、確定性和可行性特性。例1.51：在學(xué)數(shù)學(xué)時(shí)，對(duì)一道數(shù)學(xué)題解題過(guò)程的描述就是一個(gè)解題算法，對(duì)一個(gè)數(shù)學(xué)證明題的證明過(guò)程也是證題算法。但也并不是只有“計(jì)算”的問(wèn)題才有算法，對(duì)一個(gè)特定問(wèn)題的解決過(guò)程的描述也是算法例1.52：如手工書(shū)上對(duì)一個(gè)紙鶴折法的圖示描述就是一個(gè)算法。因?yàn)榘凑請(qǐng)D示的方法和步驟我們能完成一個(gè)紙鶴的制作，它解決了一個(gè)特定問(wèn)題。對(duì)于一首歌曲的樂(lè)譜也可以稱為該歌曲的算法。因?yàn)樗付搜葑嘣摳枨拿恳粋€(gè)步驟，按照它的描述就能演奏出預(yù)定的曲子。71?算法的特性

按照算法的定義，一個(gè)算法必須具備下列五個(gè)特性：?有窮性：必須在執(zhí)行有窮個(gè)操作之后結(jié)束，而且“有窮性”也應(yīng)在合理的范圍內(nèi)。?確定性：也稱無(wú)二義性。算法中，對(duì)每一個(gè)操作的描述都必須是精確的、有確切的含義，而不是模棱兩可的。

?可行性：一個(gè)算法必須由可執(zhí)行的步驟組成，即算法中的每一個(gè)步驟都應(yīng)當(dāng)能有效地執(zhí)行，并得到確定的結(jié)果。

?0－n個(gè)輸入：一般情況下，輸入的是算法的操作對(duì)象，可在算法執(zhí)行前臨時(shí)給出，也可以在編寫(xiě)算法時(shí)直接給出。?1－n個(gè)輸出：算法對(duì)輸入的操作對(duì)象執(zhí)行操作后合乎邏輯的操作結(jié)果。72

書(shū)寫(xiě)一個(gè)算法可以用多種算法描述工具。請(qǐng)看下面例子。【例1.53】用自然語(yǔ)言描述“按從小到大的順序重新排列x，y，z三個(gè)數(shù)值的內(nèi)容”的算法。算法如下(1)算法開(kāi)始；(2)輸入x，y，z三個(gè)數(shù)值；(3)從三個(gè)數(shù)值中挑選出最小者并換到x中；(4)從y，z中挑選出較小者并換到y(tǒng)中；(5)輸出排序后的結(jié)果x，y，z；(6)算法結(jié)束。73【例1.54】用類C語(yǔ)言描述“按從小到大的順序重新排列x，y，z三個(gè)數(shù)值的內(nèi)容”的算法。算法如下：viodThree_Sort(int*x，int*y，int*z){//將x，y，z三個(gè)指針?biāo)甘镜膬?nèi)容按從小到大的順序重新排列

if(*y<*x&&*y<*z)*x

*y；

elseif(*z<*x&&*z<*y)*x

*z；

//挑選出最小的數(shù)值并換到x指針?biāo)傅拇鎯?chǔ)單元中

if(*z<*y)*y

*z；

//在y和z所指示的存儲(chǔ)單元中挑選出較小者換到y(tǒng)中

printf(排序后的結(jié)果)；}74【例1.55】用C語(yǔ)言描述“按從小到大的順序重新排列x，y，z三個(gè)數(shù)值的內(nèi)容”的算法。算法如下：voidThree_Sort(int*x，int*y，int*z){//將x，y，z三個(gè)指針?biāo)甘镜膬?nèi)容按從小到大的順序重新排列

intt；

if(*y<*x&&*y<*z){ t=*x；*x=*y；*y=t；

} elseif(*z<*x&&*z<*y){ t=*x；*x=*z；*z=t；

} if(*z<*y){ t=*y；*y=*z；*z=t；

} //在y和z所指示的存儲(chǔ)單元中挑選出較小者換到y(tǒng)中

printf("x=%d，y=%d，z=%d."，*x，*y，*z)；}voidmain(){ inti=43，j=32，k=22；

Three_Sort(&i，&j，&k)；}75【例1.56】用流程圖描述“按從小到大的順序重新排列x，y，z三個(gè)數(shù)值的內(nèi)容”的算法如下：圖1.12算法流程圖761.4.3算法的評(píng)價(jià)標(biāo)準(zhǔn)對(duì)一個(gè)問(wèn)題可以有很多的解決方法，用計(jì)算機(jī)處理問(wèn)題也可以設(shè)計(jì)出不同的算法。那么，什么樣的算法是“好”的呢？設(shè)計(jì)和評(píng)價(jià)一個(gè)算法的好壞往往要從各個(gè)方面考慮。算法的評(píng)價(jià)有以下幾個(gè)標(biāo)準(zhǔn)：

1、正確性：該算法必須是正確的，要求算法能夠正確地執(zhí)行預(yù)先規(guī)定的功能，并達(dá)到所期望的性能要求。這方面的內(nèi)容在《計(jì)算機(jī)軟件學(xué)》有詳細(xì)介紹。另外，要證明算法正確性是一個(gè)比較困難的問(wèn)題。2/18/2024772、可讀性：為提高算法的可讀性，我們提倡模塊化程序設(shè)計(jì)理念，并在程序的適當(dāng)?shù)胤皆鎏碜⑨?。這使得算法易于理解、易于調(diào)試、易于移植；算法應(yīng)該具有良好的可讀性。

3、健壯性：算法中擁有對(duì)輸入數(shù)據(jù)、打開(kāi)文件、讀取文件記錄、分配內(nèi)存空間等操作的結(jié)果檢測(cè)，并通過(guò)與用戶對(duì)話的形式做出相應(yīng)的處理選擇。

4、時(shí)間與空間效率：算法的時(shí)間效率與空間效率是指將算法變換為程序后，該程序在計(jì)算機(jī)上運(yùn)行時(shí)所花費(fèi)的時(shí)間及所占據(jù)空間的度量。78第1章數(shù)據(jù)結(jié)構(gòu)和算法1.1數(shù)據(jù)與數(shù)據(jù)類型

1.2數(shù)據(jù)結(jié)構(gòu)

1.3算法的描述工具－C語(yǔ)言

1.4算法和算法評(píng)價(jià)?

1.5算法性能分析791.5算法性能分析?1.5.1算法的時(shí)間性能分析

1.5.2算法的空間性能分析80一個(gè)算法所耗費(fèi)的時(shí)間用各條語(yǔ)句執(zhí)行的次數(shù)之和來(lái)計(jì)量

又稱：時(shí)間復(fù)雜度T(n)又稱：頻度81【例】語(yǔ)句的執(zhí)行次數(shù)的計(jì)算

for(i=1;i<=n;i++) printf(“%d”,i);i<=ni=1輸出ii=i+11次n＋1次n次n次共3n＋2次即：

T(n)＝3n＋282

可以看出，算法的時(shí)間復(fù)雜度T(n)是問(wèn)題規(guī)模n的函數(shù)，它表示執(zhí)行該算法所需的時(shí)間隨問(wèn)題規(guī)模的增大而增加。其實(shí)，大多數(shù)算法的執(zhí)行時(shí)間都與問(wèn)題的規(guī)模成正比，在計(jì)算算法的時(shí)間性能時(shí)，我們通常考察時(shí)間復(fù)雜度T(n)隨問(wèn)題規(guī)模擴(kuò)大的增長(zhǎng)率83【例1.60】計(jì)算下列程序段中所有語(yǔ)句的執(zhí)行次數(shù)之和。語(yǔ)句號(hào)程序段語(yǔ)句執(zhí)行的頻度①for(i=0；i<n；i++)n+1②for(j=0；j<n；j++){ n(n+1)③C[i][j]=0； n2④for(k=0；k<n；k++) n2(n+1)⑤

C[i][j]=C[i][j]+C[i][k]n3}所以，該程序段中所有語(yǔ)句的頻度之和(也就是算法的時(shí)間復(fù)雜度)為：

T(n)=n+1+n(n+1)+n2+n2(n+1)+n3

=2n3

＋3n2

＋2n＋1(1-2)可以看出，算法的時(shí)間復(fù)雜度T(n)是問(wèn)題規(guī)模n的函數(shù)，它表示執(zhí)行該算法所需的時(shí)間隨問(wèn)題規(guī)模的增大而增加。T(n)是一個(gè)以數(shù)據(jù)量n為自變量的函數(shù)，表示一個(gè)算法所花費(fèi)時(shí)間，這個(gè)函數(shù)在正整數(shù)定義域范圍內(nèi)一定是單調(diào)遞增的。好的算法應(yīng)該能夠在數(shù)據(jù)量n增長(zhǎng)的同時(shí)，函數(shù)T(n)的增長(zhǎng)速度比較緩慢。84定義如果存在正常數(shù)c和n0，使得當(dāng)N≥n0時(shí)

T(N)≤cf(N)，則記為T(mén)(N)=O(f(N))

這個(gè)定義的目的就是在函數(shù)T(N)和f(N)間建立一種相對(duì)增長(zhǎng)率。85【例】令T(N)=1000N，f(N)=N2

對(duì)于正常數(shù)N，在N較小時(shí)，1000N要比N2大，但N2以更快的速度增長(zhǎng)，當(dāng)N=1000時(shí)情況發(fā)生逆轉(zhuǎn)。也就是說(shuō)，最后總會(huì)存在某個(gè)點(diǎn)n0=1000，從它以后cf(N)總是至少與T(N)一樣大，即

T(N)≤cf(N)。86

若忽略常數(shù)c(若c=1)，則f(N)至少T(N)與一樣大，表示T(N)是在以不快于f(N)的速度增長(zhǎng)，f(N)是T(N)的一個(gè)上限。

對(duì)于該例，按照該定義有1000N=O(N2)

我們可以稱1000N的增長(zhǎng)率為N平方級(jí)，或稱1000N增長(zhǎng)率的數(shù)量級(jí)為N平方級(jí)。這種記法稱為大O記法，讀作“大O……”87兩個(gè)函數(shù)f(n)和g(n)的相對(duì)增長(zhǎng)率可以這樣計(jì)算：

若變量n的函數(shù)f(n)和g(n)滿足：則稱f(n)和g(n)的相對(duì)增長(zhǎng)率是同一數(shù)量級(jí)，并用f(n)=О(g(n))的形式表示。定義88對(duì)上例T(n)＝3n＋2

有89【例】for(i=1;i<=n;i++)for(j=1;j<=i;j++)printf(“%d”,i);

執(zhí)行次數(shù)：90【例】

i=1;while(i<n)i=i*2;

次數(shù)：123……ki：222232k

若2k＝n次數(shù)k＝log2n

即：T(n)=O(log2n)常用數(shù)量級(jí)（時(shí)間復(fù)雜度）：

O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)<O(n!)2/18/2024911.intsum=0；//（1次）

for(i=1;i<=n;i++)//（n+1次）

for(j=1;j<=n;j++)//（n(n+1)次）

sum++；//（n^2次）

解：T(n)=n^2+n(n+1)+(n+1)+1=O(n^2)。

2.for(i=1;i<n;i++){

y=y+1;//①的頻度是n-1

for(j=0;j<=(2*n);j++)

x++;//②的頻度是(n-1)*(2n+1)=2n^2-n-1

}

解：f(n)=2n^2-n-1+(n-1)=2n^2-2。所以T(n)=O(n^2)。2/18/2024923.inti=1;//①的頻度是1

while(i<=n)

i=i*2;//②

解：設(shè)語(yǔ)句②的頻度是f(n),則：2^f(n)<=n;f(n)<=log2n

取最大值f(n)=log2n,T(n)=O(log2n)4.intk=1；//（1次）

for(i=1;i<=n;i++)//（n+1次）

for(j=1;j<=n;j++)//（n(n+1)次）

{k=1; while(k<=n)k=5*k；//(在while中頻度log5n)}

解：T(n)=。。。=O(n^2*log5n)。請(qǐng)擴(kuò)展為i=i*3;2/18/2024935.ints=0,i,j,k;for(i=0;i<=n;i++)

for(j=0;j<=i;j++)

for(k=0;k<j;k++)

s++;

解：6.inti=0,s=0;//①的頻度是1

w