參考第一章緒論

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

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

Wirth(

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

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

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

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

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

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

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

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

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

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

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

(501)8

(A

(101)8

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

signcom在計算機中有兩種表示方法（如<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例如對工資表的增、刪、改操作：基本工資工齡工資應扣工資實發(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運算集合1.3算法算法：是規(guī)則的有限集合，是為解決特定問題而規(guī)定的一系列操作。解決問題的法或一個過程(策略)。特性：有限性：有限步驟之內(nèi)正常結(jié)束，不能形成無窮循環(huán)。確定性：算法中的每一個步驟必須有確定含義，無二義性得以實現(xiàn)。輸 入：有多個或0個輸入。輸 出：至少有一個或多個輸出?？尚行裕涸瓌t上能精確進行，操作可通過已實現(xiàn)基本運算執(zhí)行有限次而完成。1.3算法算法、語言、程序語言：描述算法的工具（也可用自然語言、框圖描述算法）。程序是算法在計算機中的實現(xiàn)。程序可以不滿足有限性，如操作系統(tǒng)，它是在無限循環(huán)中執(zhí)行的程序，因而不是算法。一個好的算法一般應具有幾個基本特征：正確性可讀性健壯性（魯棒性）高效率與低

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

；i<=

n

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

(x>max)

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

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

+n41語句頻度：指該語句在一個算法中重復執(zhí)行的次數(shù)。例如：兩個矩陣相乘算法語句對應的語句頻度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時間2020/11/1842時間復雜度：語句頻度的數(shù)量級，算法的時間量度。T(n)=O(f(n))表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和

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

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

(i=1;

i<=

n;

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

(i=1;

i<=

n;

i++)for

(j=1;j<=

n;

j++)

x=x+1;－－時間復雜度為O(n2),稱為平方階。43時間2020/11/1844例如：兩個矩陣相乘算法語句對應的語句頻度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時間復雜度練習時間復雜度：O(n3)習題12020/11/18按時間復雜度由小到大排列：O(1)常數(shù)型＜O(log2n)對數(shù)型＜O(n)線性型＜O(nlog2n)二維型＜O(n2)平方型＜O(n3)立方型＜O(2n)指數(shù)型46數(shù)據(jù)結(jié)構(gòu)中常用的時間復雜度頻率計數(shù)有7個:O(1)

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

)時間復雜度練習例二：for

(i=1;

i