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

數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)第一頁，共二十六頁，2022年，8月28日2第二頁，共二十六頁，2022年，8月28日數(shù)據(jù)結(jié)構(gòu)課程的地位

它是計(jì)算機(jī)專業(yè)及相關(guān)專業(yè)的核心課程之一，是計(jì)算機(jī)及相關(guān)專業(yè)的重要骨干基礎(chǔ)課程。它針對非數(shù)值計(jì)算的程序設(shè)計(jì)問題，研究計(jì)算機(jī)的操作對象以及它們之間的關(guān)系和操作。即其研究目的是研究有效地組織和處理非數(shù)值類型數(shù)據(jù)的理論、技術(shù)和方法。3第三頁，共二十六頁，2022年，8月28日數(shù)據(jù)結(jié)構(gòu)的核心研究內(nèi)容數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及它們之間的關(guān)系和相應(yīng)的基本操作運(yùn)算的定義和實(shí)現(xiàn)。本書圍繞數(shù)據(jù)結(jié)構(gòu)的三種基本結(jié)構(gòu)：線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)展開討論，研究解決如下問題：一個(gè)具體問題的邏輯數(shù)據(jù)結(jié)構(gòu)是什么？適宜選用什么樣的存儲結(jié)構(gòu)？采用什么樣的操作實(shí)現(xiàn)算法效率更高？4第四頁，共二十六頁，2022年，8月28日1、上課認(rèn)真聽講，適當(dāng)做好筆記，按時(shí)交作業(yè)。2、考試成績分兩部分：平時(shí)成績（包括出勤和上機(jī)實(shí)驗(yàn)）占40%，期末成績占60%。3、課后需要多讀課文和參考書，上網(wǎng)查看相關(guān)內(nèi)容，在理解基本內(nèi)容的基礎(chǔ)上，多看、多做習(xí)題。4、上機(jī)實(shí)驗(yàn)十分重要，一定要在上機(jī)前做好充分準(zhǔn)備，多采用不同的數(shù)據(jù)存儲結(jié)構(gòu)和不同的實(shí)現(xiàn)算法解決一個(gè)問題。對學(xué)生的幾點(diǎn)要求5第五頁，共二十六頁，2022年，8月28日第1章緒論討論5個(gè)問題：1.1數(shù)據(jù)結(jié)構(gòu)的基本概念1.2學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義1.3數(shù)據(jù)結(jié)構(gòu)涵蓋的主要內(nèi)容1.4算法效率的度量6第六頁，共二十六頁，2022年，8月28日1.1數(shù)據(jù)結(jié)構(gòu)的基本概念1、舉例

建立一個(gè)學(xué)生檔案。學(xué)生表包括學(xué)號、姓名、性別、籍貫。要求：查找“王紅”是否存在。解決的方法步驟：如何記錄所有學(xué)生記錄（及選擇何種邏輯數(shù)據(jù)結(jié)構(gòu)）？選擇何種存儲結(jié)構(gòu)？若把所有記錄依次存儲在一個(gè)數(shù)組中——采用順序存儲結(jié)構(gòu)若采用指針鏈表——采用鏈?zhǔn)酱鎯Y(jié)構(gòu)7第七頁，共二十六頁，2022年，8月28日2、基本術(shù)語(1)數(shù)據(jù)：所有能被計(jì)算機(jī)識別、存儲和處理的符號的集合（包括數(shù)字、字符、聲音、圖像等信息）。(2)數(shù)據(jù)元素:是數(shù)據(jù)的基本單位，具有完整確定的實(shí)際意義。在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理。一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成。(3)數(shù)據(jù)項(xiàng):構(gòu)成數(shù)據(jù)元素的項(xiàng)目。它是數(shù)據(jù)不可分割的最小單位。(4)數(shù)據(jù)類型：指一個(gè)類型和定義在這個(gè)類型上的操作集合。例：C語言（基本類型：整型、浮點(diǎn)型、字符型等構(gòu)造類型：數(shù)組、結(jié)構(gòu)、聯(lián)合、指針、枚舉等）(5)抽象數(shù)據(jù)元素：抽象定義的、沒有實(shí)際含義的數(shù)據(jù)元素。(6)抽象數(shù)據(jù)類型：用戶自己定義的數(shù)據(jù)類型。8第八頁，共二十六頁，2022年，8月28日2、基本術(shù)語(續(xù)）(7)數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。或按照一定邏輯關(guān)系組織，并按一定存儲方法存儲的數(shù)據(jù)的集合，且需要定義一系列運(yùn)算。邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和運(yùn)算合稱為三要素。表示為：

Data_Structure=（D,R）

其中，D—元素有限集，R—關(guān)系有限集

9第九頁，共二十六頁，2022年，8月28日程序設(shè)計(jì)＝好算法＋好結(jié)構(gòu)

同樣的數(shù)據(jù)對象，用不同的數(shù)據(jù)結(jié)構(gòu)來表示，運(yùn)算效率可能有明顯的差異。1.2學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義計(jì)算機(jī)內(nèi)的數(shù)值運(yùn)算依靠方程式，而非數(shù)值運(yùn)算（如表、樹、圖等）則要依靠數(shù)據(jù)結(jié)構(gòu)。

數(shù)據(jù)結(jié)構(gòu)是一門學(xué)科，針對非數(shù)值計(jì)算的程序設(shè)計(jì)問題，研究計(jì)算機(jī)的操作對象以及它們之間的關(guān)系和操作等等。10第十頁，共二十六頁，2022年，8月28日1.3數(shù)據(jù)結(jié)構(gòu)涵蓋的內(nèi)容11第十一頁，共二十六頁，2022年，8月28日集合結(jié)構(gòu)：僅同屬一個(gè)集合線性結(jié)構(gòu):一對一（1:1)

樹結(jié)構(gòu):一對多（1:n)

圖結(jié)構(gòu):多對多(m:n)非線性線性邏輯結(jié)構(gòu)可細(xì)分為4類：

指數(shù)據(jù)元素之間的邏輯關(guān)系。即從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲無關(guān)，是獨(dú)立于計(jì)算機(jī)的。解釋1：什么叫數(shù)據(jù)的邏輯結(jié)構(gòu)？12第十二頁，共二十六頁，2022年，8月28日（1）S=(D,R)D={a,b,c,d,e,f}R={(a,e),(b,c),(c,a),(e,f),(f,d)}解：上述表達(dá)式可用圖形表示為：bcaefd此結(jié)構(gòu)為線性的。例：用圖形表示下列數(shù)據(jù)結(jié)構(gòu)，并指出它們是屬于線性結(jié)構(gòu)還是非線性結(jié)構(gòu)。13第十三頁，共二十六頁，2022年，8月28日

d1d5d2d4d3該結(jié)構(gòu)是非線性的。解：上述表達(dá)式可用圖形表示為：（2）S=(D,R)

D={di|1≤i≤5}

R={(di,dj),i<j}14第十四頁，共二十六頁，2022年，8月28日

物理結(jié)構(gòu)亦稱存儲結(jié)構(gòu)，是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲器內(nèi)的表示（或映像）。它依賴于計(jì)算機(jī)。存儲結(jié)構(gòu)可分為4大類：例：復(fù)數(shù)3.0－2.3i的兩種存儲方式：順序、鏈?zhǔn)?、索引、散列?.303023.00300041503023.003000415－2.3法1：地址內(nèi)容法2：地址內(nèi)容2字節(jié)解釋2：什么叫數(shù)據(jù)的物理結(jié)構(gòu)？15第十五頁，共二十六頁，2022年，8月28日在數(shù)據(jù)的邏輯結(jié)構(gòu)上定義的操作算法。它在數(shù)據(jù)的存儲結(jié)構(gòu)上實(shí)現(xiàn)。最常用的數(shù)據(jù)運(yùn)算有5種：插入、刪除、修改、查找、排序解釋3：什么是數(shù)據(jù)的運(yùn)算？16第十六頁，共二十六頁，2022年，8月28日1.4算法效率的度量1什么是算法？如何評判算法的好壞？2時(shí)間復(fù)雜度和空間復(fù)雜度如何表示？3計(jì)算舉例討論：17第十七頁，共二十六頁，2022年，8月28日1什么是算法？如何評判一個(gè)算法的好壞？常用時(shí)間復(fù)雜度來衡量算法的基本特性：算法評價(jià)指標(biāo)：有窮性、確定性、可行性、必有輸出正確性、可讀性、健壯性、高效率與低存儲量需求常用空間復(fù)雜度來衡量好的程序設(shè)計(jì)：好算法＋好結(jié)構(gòu)

算法：是對特定問題求解步驟的一種描述，它是指令的有限序列，是一系列輸入轉(zhuǎn)換為輸出的計(jì)算步驟。18第十八頁，共二十六頁，2022年，8月28日注：1）O（）為漸近符號。2）空間復(fù)雜度S(n)按數(shù)量級遞增順序也與上表類似。復(fù)雜度高復(fù)雜度低時(shí)間復(fù)雜度T(n)按數(shù)量級遞增順序?yàn)椋?時(shí)間復(fù)雜度和空間復(fù)雜度如何表示？多項(xiàng)式階19第十九頁，共二十六頁，2022年，8月28日3n+2=O(n)因?yàn)?n+24n

forn26*2n+n2=O(2n)

因?yàn)?*2n+n27*2n

forn4例：漸進(jìn)符號（O）的定義：當(dāng)且僅當(dāng)存在一個(gè)正的常數(shù)C，使得對所有的

nn0

，有f(n)Cg(n)，則：f(n)=O(g(n))20第二十頁，共二十六頁，2022年，8月28日該算法的運(yùn)行時(shí)間由程序中所有語句的頻度（即該語句重復(fù)執(zhí)行的次數(shù)）之和構(gòu)成。解：分析：顯然，語句①的頻度是1。設(shè)語句2的頻度是f(n)，則有：算法的時(shí)間復(fù)雜度由嵌套最深層語句的頻度決定例：分析以下程序段的時(shí)間復(fù)雜度。i=1;①while(i<=n)i=i*2;②即f(n)≤log2n，取最大值f(n)=log2n所以該程序段的時(shí)間復(fù)雜度T(n)=1+f(n)=1+log2n=O(log2n)3計(jì)算舉例21第二十一頁，共二十六頁，2022年，8月28日該算法的運(yùn)行時(shí)間由程序中所有語句的頻度（即該語句重復(fù)執(zhí)行的次數(shù)）之和構(gòu)成。解：例：分析以下程序段的時(shí)間復(fù)雜度。i=1;k=0;①while(i<n)

{k=k+10*i;i++;}

②即f(n)≤log2n，取最大值f(n)=log2n所以該程序段的時(shí)間復(fù)雜度T(n)=1+f(n)=1+log2n=O(log2n)3計(jì)算舉例22第二十二頁，共二十六頁，2022年，8月28日T(n)=1+1+n+(n-1)+(n-1)=3n可表示為T(n)=O(n)3分析i=1;//1k=0;//1

while(i<n)//n{k=k+10*i;//n-1i++;//n-1}

23第二十三頁，共二十六頁，2022年，8月28日本章小結(jié)數(shù)據(jù)結(jié)構(gòu)課程——數(shù)據(jù)結(jié)構(gòu)＋算法＝程序，涉及數(shù)學(xué)、計(jì)算機(jī)硬件和軟件。數(shù)據(jù)結(jié)構(gòu)定義——指互相有關(guān)聯(lián)的數(shù)據(jù)元素的集合，可用data_Structure=(D,R)表示。數(shù)據(jù)結(jié)