參考第一章緒論

第一章緒論數(shù)據(jù)結(jié)構(gòu)

的范疇與數(shù)據(jù)結(jié)構(gòu)相關(guān)的概念數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)類型和抽象數(shù)據(jù)類型算法及其描述和分析時(shí)間復(fù)雜度Niklaus

Wirth(

)：算法+數(shù)據(jù)結(jié)構(gòu)=程序設(shè)計(jì)程序設(shè)計(jì)：為計(jì)算機(jī)處理問(wèn)題編制一組指令集算法： 處理問(wèn)題的策略(怎么解決？)數(shù)據(jù)結(jié)構(gòu)：?jiǎn)栴}的數(shù)學(xué)模型(數(shù)據(jù)怎么表示？)算法與數(shù)據(jù)結(jié)構(gòu)的關(guān)系例子：求一組(n個(gè))整數(shù)中的最大值。算法：

通過(guò)依次比較兩個(gè)數(shù)的大小，找到最大值數(shù)據(jù)結(jié)構(gòu)(模型)：?用什么樣的數(shù)據(jù)結(jié)構(gòu)來(lái)表示整數(shù)？例子：已知5名學(xué)生的成績(jī)（語(yǔ)、數(shù)、英），請(qǐng)求出他們的平均分，并按平均分高低進(jìn)行由低到高排序。sigwww.nn.問(wèn)題求解的基本步驟2020/11/1871.7

關(guān)于學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)課程地位數(shù)據(jù)結(jié)構(gòu)課程學(xué)習(xí)特點(diǎn)（之后說(shuō)明）關(guān)于本書(shū)內(nèi)容編寫(xiě)說(shuō)明（之后說(shuō)明）8數(shù)據(jù)結(jié)構(gòu)課程地位2020/11/18數(shù)據(jù)結(jié)構(gòu)與其它課程關(guān)系圖：數(shù)據(jù)庫(kù)人工智能專業(yè)基礎(chǔ)課操作系統(tǒng)編譯原理非線性程序設(shè)計(jì)離散數(shù)學(xué)語(yǔ)言程序設(shè)計(jì)計(jì)算機(jī)原理設(shè)計(jì)數(shù)

據(jù)結(jié)構(gòu)1.2數(shù)據(jù)結(jié)構(gòu)的相關(guān)概念數(shù)據(jù)數(shù)據(jù)元素?cái)?shù)據(jù)對(duì)象數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)類型抽象數(shù)據(jù)類型(Data

Type--ADT)定義：數(shù)據(jù)是描述客觀事物的數(shù)值、字符以及能輸入機(jī)器且能被處理的各種符號(hào)集合。包含數(shù)值、字符、聲音、圖像等一切可以輸入到計(jì)算機(jī)中的符號(hào)集合。例如對(duì)C源程序（VC6.0）C編譯程序源程序（.cpp）目標(biāo)程序（.obj）可執(zhí)行程序（.exe）C

程序數(shù)據(jù)定義：數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位

，是數(shù)據(jù)集合的 ，在計(jì)算機(jī)中通常作為一個(gè)整體進(jìn)行考慮和處理。例如：數(shù)據(jù)元素學(xué)號(hào)籍貫出生年月住址101女河北1983.11..................數(shù)據(jù)項(xiàng)數(shù)據(jù)元素名稱出生日期參加日期職務(wù)業(yè)績(jī)年月日定義：數(shù)據(jù)對(duì)象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。例如：整數(shù)集合：N={0，±1，±2，…} 無(wú)限集字符集合：C={ˊAˊ，Bˊ，…，ˊZˊ}有限集運(yùn)動(dòng)員信息(數(shù)據(jù)元素)組成的信息表：數(shù)據(jù)對(duì)象組合項(xiàng)定義：數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素集合，是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合，它指的是數(shù)據(jù)元間的相互關(guān)系，即數(shù)據(jù)的組織形式。例如表結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)學(xué)號(hào)籍貫出生年月住址101女河北1983.11..................數(shù)據(jù)結(jié)構(gòu)教研室系處研究機(jī)構(gòu)學(xué)校樹(shù)型結(jié)構(gòu)圖結(jié)構(gòu)12543數(shù)據(jù)類型定義：數(shù)據(jù)類型是一組性質(zhì)相同的值集合以及定義在這個(gè)值集合上的一組操作的總稱。如在高級(jí)語(yǔ)言中，整型類型的取值范圍為：-32768至 ，運(yùn)算符集合（一組操作）為加、減、乘、除、取模，即+、-、*、/、%。數(shù)據(jù)類型決定了兩個(gè)方面的內(nèi)容：--取值范圍--允許使用的一組運(yùn)算（C語(yǔ)言中的基本數(shù)據(jù)類型.doc）高級(jí)語(yǔ)言中的數(shù)據(jù)類型分為兩大類：原子類型：其值不可分解。如C語(yǔ)言中的標(biāo)準(zhǔn)類型（整型、實(shí)型、字符型、）。結(jié)構(gòu)類型:其值是由若干成分按某種結(jié)構(gòu)組成的，因此是可以分解的，并且它的成分可以是非結(jié)構(gòu)的，也可以是結(jié)構(gòu)的。數(shù)據(jù)類型事實(shí)上，高級(jí)程序語(yǔ)言中的數(shù)據(jù)類型本身也是一種抽象：十進(jìn)制表示的數(shù)據(jù)98.65、9.6E3等,它們是二進(jìn)制數(shù)據(jù)的抽象;高級(jí)語(yǔ)言中，給出更高一級(jí)的數(shù)據(jù)抽象，如整型、實(shí)型、字符型等，更高級(jí)的數(shù)據(jù)抽象，如各種表、隊(duì)、棧、樹(shù)、圖、窗口、管理器等復(fù)雜的抽象數(shù)據(jù)類型。抽象數(shù)據(jù)類型－ADT抽象數(shù)據(jù)類型－ADTADT定義了一個(gè)數(shù)據(jù)對(duì)象、數(shù)據(jù)對(duì)象中各元素間的結(jié)構(gòu)關(guān)系以及一組處理數(shù)據(jù)的操作。抽象數(shù)據(jù)類型與數(shù)據(jù)類型實(shí)質(zhì)上是一個(gè)概念，只不過(guò)ADT更為廣義，不僅限于各種不同計(jì)算機(jī)處理器中已定義并實(shí)現(xiàn)的數(shù)據(jù)類型，還包括用戶自己定義的復(fù)雜數(shù)據(jù)類型。信息隱蔽：將實(shí)體的外部特征和其節(jié)分離，并且對(duì)外部用戶隱藏其實(shí)現(xiàn)細(xì)實(shí)現(xiàn)細(xì)節(jié)。抽象數(shù)據(jù)類型－.

ADesTig是數(shù)據(jù)類型的進(jìn)一步抽象。把數(shù)據(jù)類型和數(shù)據(jù)類型上的運(yùn)算綁定并封裝。有兩個(gè)重要特征：數(shù)據(jù)抽象：強(qiáng)調(diào)程序處理的實(shí)體的本質(zhì)特征、其所能完成的功能以及它和外部用戶的接口(即外界使用它的方法)。數(shù)據(jù)結(jié)構(gòu)的內(nèi)容數(shù)據(jù)結(jié)構(gòu)：帶結(jié)構(gòu)的數(shù)據(jù)元素的集合。數(shù)據(jù)元素間的相互關(guān)系包括三個(gè)方面：數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的物理結(jié)構(gòu)數(shù)據(jù)的運(yùn)算集合sig數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)可歸結(jié)為以下四類：線性結(jié)構(gòu)：樹(shù)形結(jié)構(gòu)：圖形結(jié)構(gòu)(網(wǎng)狀結(jié)構(gòu))：集合結(jié)構(gòu)：邏輯結(jié)構(gòu).集合結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元

間除了同屬于一個(gè)集合的關(guān)系外，無(wú)任何其它關(guān)系。圖例：線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元間存在著一對(duì)一的線性關(guān)系。圖例：樹(shù)形結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元間存在著一對(duì)多的線性關(guān)系。圖例：樹(shù)圖狀結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元間存在著多對(duì)多的線性關(guān)系。圖例：圖sig邏輯結(jié)構(gòu).邏輯結(jié)構(gòu)也可歸結(jié)為：線性結(jié)構(gòu)——線性表、棧、隊(duì)、字符串、數(shù)組、廣義表邏輯結(jié)構(gòu)非線性結(jié)構(gòu)——樹(shù)、圖sig反映成分?jǐn)?shù)據(jù)在計(jì)算機(jī)內(nèi)的

安排。邏輯結(jié)構(gòu)在

器中的映像。物理結(jié)構(gòu).sig數(shù)據(jù)元素的映像方法：例如：用二進(jìn)制位(bit)的位串表示數(shù)據(jù)元素(321)10

(501)8

(A

(101)8

(00100物理結(jié)構(gòu)..

signcom在計(jì)算機(jī)中有兩種表示方法（如<x,y>--x先于y）順序 結(jié)構(gòu)

(數(shù)組結(jié)構(gòu))xy非順序結(jié)構(gòu)(記錄結(jié)構(gòu))xy物理結(jié)構(gòu)2

2

/11/130例如對(duì)工資表的增、刪、改操作：基本工資工齡工資應(yīng)扣工資實(shí)發(fā)工資100001女345．67145．4530．00451．12100002李

林男445．90185．6045．00586．50100003男345．00130．0025．00450．00100004趙

俊女560．90225．9065．00721．80100005孫

濤男450．60190．8050．00591．80…………………100121男1025．98365．53100．001291.51運(yùn)算集合1.3算法算法：是規(guī)則的有限集合，是為解決特定問(wèn)題而規(guī)定的一系列操作。解決問(wèn)題的法或一個(gè)過(guò)程(策略)。特性：有限性：有限步驟之內(nèi)正常結(jié)束，不能形成無(wú)窮循環(huán)。確定性：算法中的每一個(gè)步驟必須有確定含義，無(wú)二義性得以實(shí)現(xiàn)。輸 入：有多個(gè)或0個(gè)輸入。輸 出：至少有一個(gè)或多個(gè)輸出?？尚行裕涸瓌t上能精確進(jìn)行，操作可通過(guò)已實(shí)現(xiàn)基本運(yùn)算執(zhí)行有限次而完成。1.3算法算法、語(yǔ)言、程序語(yǔ)言：描述算法的工具（也可用自然語(yǔ)言、框圖描述算法）。程序是算法在計(jì)算機(jī)中的實(shí)現(xiàn)。程序可以不滿足有限性，如操作系統(tǒng)，它是在無(wú)限循環(huán)中執(zhí)行的程序，因而不是算法。一個(gè)好的算法一般應(yīng)具有幾個(gè)基本特征：正確性可讀性健壯性（魯棒性）高效率與低

量1.3算法設(shè)計(jì)正確性：例如要求n個(gè)數(shù)的最大值問(wèn)題：max=0;for（i=1

；i<=

n

;i++）{ scanf("%f",x);if

(x>max)

max=x;}語(yǔ)法錯(cuò)誤？當(dāng)輸入的全為正數(shù)時(shí)，結(jié)果正確？當(dāng)輸入的全為負(fù)數(shù)時(shí)，結(jié)果正確？時(shí)，算法應(yīng)當(dāng)能夠加以識(shí)別并做出健壯性：當(dāng)輸入的數(shù)據(jù)處理高效率與低

量需求：效率：算法執(zhí)行時(shí)間(T)量：算法執(zhí)行過(guò)程中所需的最大空間。(S)兩者都與問(wèn)題的規(guī)模(n)有關(guān)耗費(fèi)的時(shí)間T(n,I)算法性能C(n,I)占用的空間S(n,I)與算法執(zhí)行時(shí)間相關(guān)的因素：算法執(zhí)行的策略問(wèn)題的規(guī)模n編寫(xiě)程序的語(yǔ)言編譯程序產(chǎn)生的機(jī)器語(yǔ)言的質(zhì)量計(jì)算機(jī)執(zhí)行指令的速度時(shí)間2020/11/1840定義：一個(gè)算法的執(zhí)行時(shí)間大致上等于其所有語(yǔ)句執(zhí)行時(shí)間的總和，對(duì)于語(yǔ)句的執(zhí)行時(shí)間是指該條語(yǔ)句的執(zhí)行次數(shù)和執(zhí)行一次所需時(shí)間的乘積。分析：不是針對(duì)實(shí)際執(zhí)行時(shí)間的精確地算出算法執(zhí)行具體時(shí)間，而是針對(duì)算法中語(yǔ)句的執(zhí)行次數(shù)做出估計(jì)，從中得到算法執(zhí)行時(shí)間的信息。時(shí)間2020/11/18}總執(zhí)行次數(shù)：Tn=2n3+2n2

+n41語(yǔ)句頻度：指該語(yǔ)句在一個(gè)算法中重復(fù)執(zhí)行的次數(shù)。例如：兩個(gè)矩陣相乘算法語(yǔ)句對(duì)應(yīng)的語(yǔ)句頻度nn2n2n3{

c[i][j]=0;for

(k=0;k<

n;

k++)for（i=0；i<

n;i++）for

（j=0；j<n;j++）345c[i][j]=c[i][j]+a[i][k]*b[k][j];

n3時(shí)間2020/11/1842時(shí)間復(fù)雜度：語(yǔ)句頻度的數(shù)量級(jí)，算法的時(shí)間量度。T(n)=O(f(n))表示隨問(wèn)題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和

f(n)的增長(zhǎng)率相同，稱做算法的漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。時(shí)間2020/11/18例如：給出X=X+1x=x+1

；－－時(shí)間復(fù)雜度為O(1)，稱為常量階；for

(i=1;

i<=

n;

i++)x=x+1;－－時(shí)間復(fù)雜度為O(n)，稱為線性階；for

(i=1;

i<=

n;

i++)for

(j=1;j<=

n;

j++)

x=x+1;－－時(shí)間復(fù)雜度為O(n2),稱為平方階。43時(shí)間2020/11/1844例如：兩個(gè)矩陣相乘算法語(yǔ)句對(duì)應(yīng)的語(yǔ)句頻度nn2n2n3for

(k=0;k<

n;

k++)for（i=0；i<

n;i++）for

（j=0；j<n;j++）{

c[i][j]=0;45c[i][j]=c[i][j]+a[i][k]*b[k][j];

n3}總執(zhí)行次數(shù)：Tn=2n3+2n2

+n時(shí)間復(fù)雜度練習(xí)時(shí)間復(fù)雜度：O(n3)習(xí)題12020/11/18按時(shí)間復(fù)雜度由小到大排列：O(1)常數(shù)型＜O(log2n)對(duì)數(shù)型＜O(n)線性型＜O(nlog2n)二維型＜O(n2)平方型＜O(n3)立方型＜O(2n)指數(shù)型46數(shù)據(jù)結(jié)構(gòu)中常用的時(shí)間復(fù)雜度頻率計(jì)數(shù)有7個(gè):O(1)

常數(shù)型O(n)線性型O(n2)平方型O(n3)立方型O(nlog2n)二維型O(2n)指數(shù)型O(log2n)對(duì)數(shù)型時(shí)間例一：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];{時(shí)間復(fù)雜度：O(n3

)時(shí)間復(fù)雜度練習(xí)例二：for

(i=1;

i