第一章緒論

第一章緒論

1.1數(shù)據(jù)結(jié)構(gòu)的主要研究內(nèi)容

1.2數(shù)據(jù)結(jié)構(gòu)的有關(guān)概念

1.3抽象數(shù)據(jù)類型

1.4算法及算法分析

1.5本課程用到的類C語言1.1數(shù)據(jù)結(jié)構(gòu)的主要研究內(nèi)容數(shù)據(jù)分類數(shù)值數(shù)據(jù)非數(shù)值數(shù)據(jù)程序

--數(shù)（整數(shù)，實(shí)數(shù)）

--字符字符串文字表格圖形圖像聲音應(yīng)用問題數(shù)值問題非數(shù)值問題數(shù)值問題例已知游泳池長、寬，設(shè)計(jì)求解面積的程序。建立模型

設(shè)計(jì)求解問題的方法（算法）編程

問題涉及的對(duì)象：長len、寬width、面積area；

對(duì)象之間的關(guān)系：area=lenwidth例2已知學(xué)生的選課情況，試設(shè)計(jì)安排課程考試日程的程序,要求在盡可能短的時(shí)間內(nèi)完成考試。非數(shù)值問題人工智能(F)形式語言(B)齊硯生算法分析(A)人工智能(F)模式識(shí)別(D)馬耀先人工智能(F)網(wǎng)絡(luò)(E)計(jì)算機(jī)圖形(C)魏慶濤

模式識(shí)別(D)計(jì)算機(jī)圖形(C)石磊網(wǎng)絡(luò)(E)形式語言(B)算法分析(A)楊潤生建立模型問題涉及的對(duì)象：課程對(duì)象之間的關(guān)系：同一學(xué)生選修的課程之間有

“沖突”關(guān)系。人工智能(F)形式語言(B)齊硯生算法分析(A)人工智能(F)模式識(shí)別(D)馬耀先人工智能(F)網(wǎng)絡(luò)(E)計(jì)算機(jī)圖形(C)魏慶濤

模式識(shí)別(D)計(jì)算機(jī)圖形(C)石磊網(wǎng)絡(luò)(E)形式語言(B)算法分析(A)楊潤生DEFCBA頂點(diǎn)表示課程同一學(xué)生選修的課程用邊連接無邊連接的課程可以在同一時(shí)間考試；有邊連接的課程不能在同一時(shí)間考試；人工智能(F)形式語言(B)齊硯生算法分析(A)人工智能(F)模式識(shí)別(D)馬耀先人工智能(F)網(wǎng)絡(luò)(E)計(jì)算機(jī)圖形(C)魏慶濤

模式識(shí)別(D)計(jì)算機(jī)圖形(C)石磊網(wǎng)絡(luò)(E)形式語言(B)算法分析(A)楊潤生DEFCBA設(shè)計(jì)求解問題的方法每一種顏色代表一個(gè)考試時(shí)間，著相同顏色的頂點(diǎn)（課程）在同一時(shí)間考試,希望用盡可能少的顏色為圖頂點(diǎn)著色；無邊相連的頂點(diǎn)著相同的顏色;(著色法）AC求解考試日程的流程

著色法的基本步驟

1）取一顏色，在圖的尚未著色頂點(diǎn)中,找出所有無邊相連的頂點(diǎn),著上該顏色;2）若圖中所有頂點(diǎn)都已著色，結(jié)束;否則，轉(zhuǎn)1）ACEFBDDEFCBA如下是一個(gè)考試日程：

1:算法分析(A)

計(jì)算機(jī)圖形學(xué)(C)2:形式語言(B)

模式識(shí)別人工智能(D)3:計(jì)算機(jī)網(wǎng)絡(luò)(E)4:人工智能(F)編程要考慮圖存儲(chǔ)實(shí)現(xiàn)圖操作:判斷圖的兩個(gè)頂點(diǎn)之間是否有邊相連;實(shí)現(xiàn)圖著色….ACEFBDDEFCBA數(shù)值問題與非數(shù)值問題的比較數(shù)值問題建立模型問題求解方法編程非數(shù)值問題建立模型問題求解方法編程對(duì)象:len、width、area

——用數(shù)值表示對(duì)象之間的關(guān)系

area=lenwidth

用方程或函數(shù)表示

-計(jì)算方法數(shù)據(jù)存儲(chǔ)：可用變量存儲(chǔ)數(shù)據(jù)對(duì)象:課程

——用課程名表示對(duì)象之間的關(guān)系：課程間有“沖突”關(guān)系

不能用方程或函數(shù)表示

-

著色法數(shù)據(jù)存儲(chǔ)：要保存數(shù)據(jù)及數(shù)據(jù)之間的關(guān)系

數(shù)據(jù)結(jié)構(gòu)的主要研究內(nèi)容數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值問題中,計(jì)算機(jī)的操作數(shù)據(jù)以及它們之間的關(guān)系和操作的學(xué)科。數(shù)據(jù)結(jié)構(gòu)的主要研究內(nèi)容是非數(shù)值數(shù)據(jù)之間的有哪些結(jié)構(gòu)關(guān)系如何表示，如何存儲(chǔ)，如何處理1.2.數(shù)據(jù)結(jié)構(gòu)的有關(guān)概念數(shù)據(jù)：客觀對(duì)象的符號(hào)表示。數(shù)據(jù)元素(記錄)

：是數(shù)據(jù)的基本單位。在程序中通常作為一個(gè)整體考慮和處理。通常具有完整確定的實(shí)際意義。數(shù)據(jù)項(xiàng)(字段):通常數(shù)據(jù)元素可由若干數(shù)據(jù)項(xiàng)組成,用于刻畫數(shù)據(jù)元素的某一方面特征.是不可分割的最小標(biāo)識(shí)單位。例圖書記錄數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏清華大學(xué)出版社學(xué)生記錄20090001王宏90

一副撲克牌{<黑桃,A>,<黑桃,Q>,…..,}

數(shù)據(jù)結(jié)構(gòu)(datastructure)：帶有結(jié)構(gòu)（關(guān)系）和操作的數(shù)據(jù)元素集合數(shù)據(jù)元素集合結(jié)構(gòu)：數(shù)據(jù)元素之間的結(jié)構(gòu)關(guān)系操作：數(shù)據(jù)操作每種數(shù)據(jù)結(jié)構(gòu)的討論可以分為兩個(gè)層面：概念層面：數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的基本操作實(shí)現(xiàn)層面：數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，基本操作的實(shí)現(xiàn)

數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)之間的邏輯關(guān)系,是具體關(guān)系的抽象學(xué)號(hào)

姓名學(xué)積分

01王洪42

02孫文4603謝軍4604李輝3805沈力32

學(xué)積分表學(xué)號(hào)

姓名學(xué)積分

02孫文4603謝軍4601王洪42

04李輝3805沈力32學(xué)積分表數(shù)據(jù)的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)的分類線性結(jié)構(gòu)（一對(duì)一）樹結(jié)構(gòu)（一對(duì)多）圖結(jié)構(gòu)（多對(duì)多）集合結(jié)構(gòu)（無關(guān)系）線性結(jié)構(gòu)——一對(duì)一的順序關(guān)系線性結(jié)構(gòu)：除第一個(gè)元素和最后一個(gè)元素外，其他元素都有且僅有一個(gè)直接前趨，有且僅有一個(gè)直接后繼。a1a2a3a4a5例01王洪42

02孫文4603謝軍4604李輝3805沈力32學(xué)積分表樹結(jié)構(gòu)——一對(duì)多的順序關(guān)系A(chǔ)GFDBE

IH

JC例家族樹（家譜）樹形結(jié)構(gòu)：除了根外，每一個(gè)元素只有一個(gè)直接前趨，有0個(gè)或多個(gè)直接后繼。圖結(jié)構(gòu)——多對(duì)多的關(guān)系DEFCBA圖形結(jié)構(gòu)：每一個(gè)元素可以有0個(gè)或多個(gè)直接前趨，有0個(gè)或多個(gè)直接后繼。集合結(jié)構(gòu)——無關(guān)系

DEFCBA

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)邏輯結(jié)構(gòu)在計(jì)算機(jī)(內(nèi)存)中的表示(邏輯結(jié)構(gòu)在存儲(chǔ)器中的映象)a1a2a3a4a5數(shù)據(jù)元素的表示數(shù)據(jù)關(guān)系的表示

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)常用的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)（順序映象）

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（鏈?zhǔn)接诚螅┧饕鎯?chǔ)結(jié)構(gòu)散列存儲(chǔ)結(jié)構(gòu)a1a2a3a4a5

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)（順序映象）用連續(xù)的內(nèi)存單元存儲(chǔ)數(shù)據(jù)元素通過數(shù)據(jù)元素在存儲(chǔ)器中的相對(duì)位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系a1a2a3a4a5a1a2a3a4a5例

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（鏈?zhǔn)接诚螅┯萌我庖唤M內(nèi)存單元存儲(chǔ)數(shù)據(jù)元素通過相關(guān)元素的存儲(chǔ)地址或存儲(chǔ)位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系a1a2a3a4a5a3a1a2a4a5例

數(shù)據(jù)操作操作的定義-是指操作功能的定義操作的實(shí)現(xiàn)-是指如何在計(jì)算機(jī)上實(shí)現(xiàn)操作的功能01王洪42

02孫文4603謝軍4604李輝3805沈力32

學(xué)積分表例：學(xué)積分表的操作：插入、刪除、查找、排序1.3抽象數(shù)據(jù)類型（AbstractDataType）數(shù)據(jù)類型定義了一個(gè)數(shù)據(jù)集合和該集合上的一組操作。例C語言整型類型:intC語言整型類型涉及的數(shù)據(jù)集合為某個(gè)范圍的整數(shù)，可以進(jìn)行的運(yùn)算有：加、減、乘、除、比較等。1.3抽象數(shù)據(jù)類型（AbstractDataType）以C語言整型類型為例,分析高級(jí)語言預(yù)定義數(shù)據(jù)類型的作用(好處)。隨時(shí)使用能隨時(shí)定義整型類型的變量，使用加、減、乘、除等操作。數(shù)據(jù)隱藏

隱藏了加、減、乘、除等運(yùn)算在計(jì)算機(jī)中的實(shí)現(xiàn)方法;使用與實(shí)現(xiàn)無關(guān);1.3抽象數(shù)據(jù)類型（AbstractDataType）抽象數(shù)據(jù)類型(簡稱ADT)，定義了一個(gè)數(shù)據(jù)模型和這個(gè)數(shù)據(jù)模型上的一組操作。例:集合與集合的并、交、差運(yùn)算就可定義為一個(gè)抽象數(shù)據(jù)類型。ADT抽象數(shù)據(jù)類型名{

數(shù)據(jù)對(duì)象：〈數(shù)據(jù)對(duì)象的定義〉

數(shù)據(jù)關(guān)系：〈數(shù)據(jù)關(guān)系的定義〉

基本操作：〈基本操作的定義〉}ADT抽象數(shù)據(jù)類型名ADT的定義格式ADTList{

數(shù)據(jù)對(duì)象:D={ai|aiElemTypei=1,2,..,nn≥0}

數(shù)據(jù)關(guān)系:r1={<a1,a2>,<a2,a3>,…,<an-1,an>}

基本操作:

InitList(&L)

操作結(jié)果：構(gòu)造一個(gè)空的表L；

ListEmpty(L)

初始條件：線性表L已存在操作結(jié)果：若L為空表返回TRUE，否則返回FALSE

InsertList(&L,i,e)

初始條件：線性表L已存在操作結(jié)果：將e

插到表尾

…}ADTList1.3抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型的作用(以List為例)數(shù)據(jù)抽象在List的ADT定義中,只刻畫List的邏輯結(jié)構(gòu)和操作功能;即List的ADT定義與List在計(jì)算機(jī)中如何實(shí)現(xiàn)無關(guān)。數(shù)據(jù)隱藏ADT隱藏了List的實(shí)現(xiàn)方法,使用與實(shí)現(xiàn)無關(guān)隨時(shí)使用(前提是List已實(shí)現(xiàn),可見)1.4算法與算法分析程序原始數(shù)據(jù)結(jié)果數(shù)據(jù)

1.4.1算法

1.4.2算法的評(píng)價(jià)

1.4.1算法算法的概念算法是求解特定問題的一個(gè)操作步驟。

例求兩個(gè)正整數(shù)m，n中最大數(shù)的算法1）若m>n則max=m

2）若m<=n則max=n算法的五個(gè)基本特征

1）有輸入、2）有輸出

3）有窮性、4）確定性、5）可行性

1.4.1算法算法的五個(gè)基本特征有輸入：算法必須有加工處理的數(shù)據(jù)；有輸出：算法對(duì)輸入數(shù)據(jù)進(jìn)行加工處理，必須有結(jié)果；有窮性：算法必須是有限的;確定性：算法的每一步必須有明確的含義可行性：算法中的操作必須足夠基本；能夠用已實(shí)現(xiàn)的基本操作實(shí)現(xiàn)；

不確定:若m>n則max=m或max=n算法的描述和實(shí)現(xiàn)描述---可采用自然語言、數(shù)學(xué)語言或約定的符號(hào)語言、程序設(shè)計(jì)語言。實(shí)現(xiàn)---借助程序設(shè)計(jì)語言提供的數(shù)據(jù)類型及其運(yùn)算。本課程算法的描述語言---類C語言

1.4.1算法1.4.1算法常用的算法設(shè)計(jì)方法窮舉法貪心法遞歸法,分治法回溯法寬度優(yōu)先和深度優(yōu)先搜索動(dòng)態(tài)規(guī)劃法α-β裁剪和分枝界限法并行算法算法評(píng)價(jià)重要指標(biāo)正確性:指算法實(shí)現(xiàn)所需要的功能可讀性:結(jié)構(gòu)簡單、易于理解時(shí)間復(fù)雜度:度量算法的時(shí)間效率空間復(fù)雜度:度量算法的空間效率1.4.2算法的評(píng)價(jià)1.4.2算法的評(píng)價(jià)

例求解四次多項(xiàng)式ax4＋bx3＋cx2＋dx＋e

另一種方法是在程序使用下列語句：

r＝a；

r=r*x+b; r=r*x+c; r=r*x+d; r=r*x+e;

一種方式是在程序中直接用下列表達(dá)求解：

r＝a*x*x*x*x+b*x*x*x+c*x*x+d*x+e;10次乘法4次加法4次乘法4次加法算法選用的策略問題的規(guī)模(輸入數(shù)據(jù)的數(shù)據(jù)量）編寫程序的語言編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量計(jì)算機(jī)的速度影響算法時(shí)間效率的因素1.4.2算法的評(píng)價(jià)-時(shí)間復(fù)雜度評(píng)價(jià)算法效率的方法事后統(tǒng)計(jì)法通過上機(jī)運(yùn)行，測(cè)試算法花費(fèi)的時(shí)間。算法的平均執(zhí)行時(shí)間，算法的最大執(zhí)行時(shí)間。缺點(diǎn)：

1)必須編寫、執(zhí)行程序

2）受軟硬件等因素的影響,掩蓋算法本質(zhì)1.4.2算法的評(píng)價(jià)-時(shí)間復(fù)雜度事前分析估算法

例n階矩陣相乘算法

for(i=0;i<n;++i)for(j=0;j<n;++j){c[i][j]=0;

for(k=1;k<=n;++k)c[i][j]+=a[i][k]*b[k][j];}事前分析估算法

-排除與計(jì)算機(jī)的軟硬件環(huán)境有關(guān)因素;1.4.2算法的評(píng)價(jià)-時(shí)間復(fù)雜度-算法的時(shí)間效率可以用算法執(zhí)行時(shí),基本操作執(zhí)行次數(shù)度量;1.4.2算法的評(píng)價(jià)-算法的時(shí)間復(fù)雜度用算法執(zhí)行時(shí)基本操作執(zhí)行次數(shù)度量;算法基本操作執(zhí)行次數(shù)是問題規(guī)模n的函數(shù)T(n);考量當(dāng)問題規(guī)模n增大時(shí),T(n)的增長趨勢(shì);用O-表示法度量假如隨著問題規(guī)模n的增長，T(n)的增長率與f(n)的增長率相同，則記作：T(n)=O(f(n))，稱O(f(n))為算法的時(shí)間復(fù)雜度。

T(n)=3n3+n2T(n)=O(n3)

例n階矩陣相乘算法

for(i=0;i<n;++i)for(j=0;j<n;++j){c[i][j]=0;

for(k=1;k<=n;++k)c[i][j]+=a[i][k]*b[k][j];}1.4.2算法的評(píng)價(jià)-算法的時(shí)間復(fù)雜度算法由控制語句和基本操作(數(shù)據(jù)處理部分對(duì)預(yù)定義數(shù)據(jù)類型的操作)組成;計(jì)算基本操作執(zhí)行次數(shù)的數(shù)量級(jí);3n3n2算法的時(shí)間復(fù)雜度O(n3)

1.4.2算法的評(píng)價(jià)-算法的時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度級(jí)別:O(1)、O(logn)、O(n)、O(nlogn)、O(n2)…;若算法基本操作的執(zhí)行次數(shù)不僅與問題規(guī)模有關(guān)關(guān)還與輸入數(shù)據(jù)有關(guān),則考慮最好情況、最壞情況、平均情況;一般考慮最壞情況、平均情況;2nn2nlognnLognfn1.4.2算法的評(píng)價(jià)-算法的空間復(fù)雜度算法空間:固定空間：輸入數(shù)據(jù)、結(jié)果數(shù)據(jù)、程序代碼所需的空間可變空間(輔助空間)：中間結(jié)果、遞歸調(diào)用所需的空間1.4.2算法的評(píng)價(jià)-算法的空間復(fù)雜度用算法所