數(shù)據(jù)結(jié)構(gòu)：chapter1緒論

數(shù)據(jù)結(jié)構(gòu)為什么學習這門課？專業(yè)基礎(chǔ)課計算機專業(yè)入門必備緊密相關(guān)課程：計算機編程，算法設(shè)計，。。。計算機類考試必考課程計算機等級考試程序員考試公務(wù)員考試（計算機類）考研找工作IT企業(yè)筆試+面試2課程簡介先修課程及條件程序設(shè)計語言，離散數(shù)學，。。。教材：數(shù)據(jù)結(jié)構(gòu)(C語言版)，嚴蔚敏，清華大學出版社考核：考試+上機+平時（出勤，提問）參考書1.C++數(shù)據(jù)結(jié)構(gòu)與算法(第4版)（國外計算機科學經(jīng)典教材），(美)

喬茲德克(Drozdek,A.)著，清華大學出版社2.數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC++語言描述）第二版，殷人昆主編，清華大學出版社3課程學習方法課程特點內(nèi)容抽象、概念性強、內(nèi)容豐富、靈活掌握。學習方法1.提前預習、認真聽課、按時完成書面及上機作業(yè)2.注意先修課程的知識準備：離散數(shù)學、C語言等3.注意循序漸進：基本概念基本思想基本步驟算法設(shè)計4.注意培養(yǎng)算法設(shè)計的能力：理解所講算法、對此多做思考：若問題要求不同，應(yīng)如何選擇數(shù)據(jù)結(jié)構(gòu)，設(shè)計有效的算法，做到舉一反三4第一章：緒論1.1數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容1.2基本概念和術(shù)語1.3抽象數(shù)據(jù)類型的表示與實現(xiàn)1.4算法與算法分析5NiklausWirth教授（1984年圖靈獎得主）提出：程序=算法+數(shù)據(jù)結(jié)構(gòu)電子計算機的主要用途：早期：主要用于數(shù)值計算后來：處理逐漸擴大到非數(shù)值計算領(lǐng)域，能處理多種復雜的具有一定結(jié)構(gòu)關(guān)系的數(shù)據(jù)1.1數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容6書目自動檢索系統(tǒng)登錄號：書名：作者名：分類號：出版單位：出版時間：價格：書目卡片書目文件按書名按作者名按分類號索引表線性表7人機對奕問題樹……..……..…...…...…...…...8/(root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp文件系統(tǒng)的系統(tǒng)結(jié)構(gòu)圖樹9多叉路口交通燈管理問題CEDABABACADBABCBDDADBDCEAEBECED圖頂點：一條通路連線：不能同時通行染色：有連線的兩個頂點不能具有相同顏色圖中節(jié)點染色需要幾種顏色？10求解非數(shù)值計算的問題：設(shè)計出合適的數(shù)據(jù)結(jié)構(gòu)及相應(yīng)的算法即：首先要考慮對相關(guān)的各種信息如何表示、組織和存儲？數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容為：研究非數(shù)值計算的程序設(shè)計問題中計算機的操作對象以及它們之間的關(guān)系和操作。11數(shù)據(jù)結(jié)構(gòu)課程的形成和發(fā)展：形成階段：60年代初期，“數(shù)據(jù)結(jié)構(gòu)”有關(guān)的內(nèi)容散見于操作系統(tǒng)、編譯原理和表處理語言等課程。1968年，“數(shù)據(jù)結(jié)構(gòu)”被列入美國一些大學計算機科學系的教學計劃。發(fā)展階段：數(shù)據(jù)結(jié)構(gòu)的概念不斷擴充，包括了網(wǎng)絡(luò)、集合代數(shù)論、關(guān)系等“離散數(shù)學結(jié)構(gòu)”的內(nèi)容。70年代后期，我國高校陸續(xù)開設(shè)該課程。12《數(shù)據(jù)結(jié)構(gòu)》所處的地位：介于數(shù)學、計算機硬件和計算機軟件三者之間的一門核心課程13課程目的能夠分析研究計算機加工的對象的特性，獲得其邏輯結(jié)構(gòu)，根據(jù)需求，選擇合適存貯結(jié)構(gòu)及其相應(yīng)的算法；學習一些常用的算法；復雜程序設(shè)計的訓練過程，要求編寫的程序結(jié)構(gòu)清楚和正確易讀；初步掌握算法的時間分析和空間分析技術(shù)141、數(shù)據(jù)（data)—所有能輸入到計算機中去的描述客觀事物的符號數(shù)值性數(shù)據(jù)非數(shù)值性數(shù)據(jù)（多媒體信息處理）2、數(shù)據(jù)元素（dataelement）—數(shù)據(jù)的基本單位，也稱結(jié)點（node）或記錄（record）3、數(shù)據(jù)項（dataitem）—有獨立含義的數(shù)據(jù)最小單位，也稱域(field)三者之間的關(guān)系：數(shù)據(jù)>數(shù)據(jù)元素>數(shù)據(jù)項例：學生表>個人記錄>學號、姓名……1.2基本概念和術(shù)語15整數(shù)數(shù)據(jù)對象

N={0,1,2,…}學生數(shù)據(jù)對象學生記錄的集合4、數(shù)據(jù)對象(DataObject)：相同特性數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集165、數(shù)據(jù)結(jié)構(gòu)（DataStructure）是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。數(shù)據(jù)結(jié)構(gòu)是帶“結(jié)構(gòu)”的數(shù)據(jù)元素的集合，“結(jié)構(gòu)”就是指數(shù)據(jù)元素之間存在的關(guān)系。17數(shù)據(jù)結(jié)構(gòu)的兩個層次：邏輯結(jié)構(gòu)---數(shù)據(jù)元素間抽象化的相互關(guān)系，與數(shù)據(jù)的存儲無關(guān)，獨立于計算機，它是從具體問題抽象出來的數(shù)學模型。存儲結(jié)構(gòu)（物理結(jié)構(gòu)）---數(shù)據(jù)元素及其關(guān)系在計算機存儲器中的存儲方式。18劃分方法一（1）線性結(jié)構(gòu)----有且僅有一個開始和一個終端結(jié)點，并且所有結(jié)點都最多只有一個直接前趨和一個后繼。例如：線性表、棧、隊列、串（2）非線性結(jié)構(gòu)----一個結(jié)點可能有多個直接前趨和直接后繼。例如：樹、圖邏輯結(jié)構(gòu)19線性結(jié)構(gòu)——一個對一個，如線性表、棧、隊列樹形結(jié)構(gòu)——一個對多個，如樹集合——數(shù)據(jù)元素間除“同屬于一個集合”外，無其它關(guān)系圖形結(jié)構(gòu)——多個對多個，如圖邏輯結(jié)構(gòu)劃分方法二20存儲結(jié)構(gòu)分為：順序存儲結(jié)構(gòu)——借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素間的邏輯關(guān)系鏈式存儲結(jié)構(gòu)——借助指示元素存儲地址的指針表示數(shù)據(jù)元素間的邏輯關(guān)系存儲結(jié)構(gòu)21元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲地址存儲內(nèi)容Loc(元素i)=Lo+（i-1)*m順序存儲221536元素21400元素11346元素3∧元素41345h存儲地址

存儲內(nèi)容

指針1345

元素1

14001346

元素4∧

…….

……..

…….

1400

元素21536

…….

……..

…….1536

元素31346

鏈式存儲

h23邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)都相同,但運算不同,則數(shù)據(jù)結(jié)構(gòu)不同.例如,棧與隊列對于一種數(shù)據(jù)結(jié)構(gòu),常見的運算插入刪除修改查找排序數(shù)據(jù)的運算24

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

數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的運算：插入、刪除、修改、查找、排序

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

非線性結(jié)構(gòu)

順序存儲

鏈式存儲線性表

棧、隊列

串、數(shù)組樹形結(jié)構(gòu)圖形結(jié)構(gòu)邏輯結(jié)構(gòu)唯一存儲結(jié)構(gòu)不唯一運算的實現(xiàn)依賴于存儲結(jié)構(gòu)25定義：在一種程序設(shè)計語言中，變量所具有的數(shù)據(jù)種類數(shù)據(jù)類型FORTRAN語言：整型、實型、和復數(shù)型C語言：基本數(shù)據(jù)類型：

charintfloatdoublevoid構(gòu)造數(shù)據(jù)類型：數(shù)組、結(jié)構(gòu)體、共用體、文件

數(shù)據(jù)類型是一組性質(zhì)相同的值的集合,以及定義于這個集合上的一組運算的總稱26(ADTs:AbstractDataTypes)更高層次的數(shù)據(jù)抽象由用戶定義，用以表示應(yīng)用問題的數(shù)據(jù)模型由基本的數(shù)據(jù)類型組成,并包括一組相關(guān)的操作抽象數(shù)據(jù)類型27抽象數(shù)據(jù)類型可以用以下的三元組來表示：

ADT=（D，S，P）數(shù)據(jù)對象D上的關(guān)系集D上的操作集ADT抽象數(shù)據(jù)類型名{

數(shù)據(jù)對象：<數(shù)據(jù)對象的定義>

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

基本操作：<基本操作的定義>}ADT抽象數(shù)據(jù)類型名ADT常用定義格式28抽象數(shù)據(jù)類型查找插入刪除修改

線性表接口或用戶界面數(shù)據(jù)類型的物理實現(xiàn)封裝信息隱蔽和數(shù)據(jù)封裝，使用與實現(xiàn)相分離291.3抽象數(shù)據(jù)類型的表示與實現(xiàn)抽象數(shù)據(jù)類型可以通過固有的數(shù)據(jù)類型（如整型、實型、字符型等）來表示和實現(xiàn)。它有些類似C語言中的結(jié)構(gòu)（struct)類型，但增加了相關(guān)的操作教材中用的是類C語言（介于偽碼和C語言之間）作為描述工具但上機時要用具體語言實現(xiàn)，如C或C++等30(1)預定義常量及類型//函數(shù)結(jié)果狀態(tài)代碼#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2//Status是函數(shù)返回值類型，其值是函數(shù)結(jié)果狀態(tài)代碼。typedefintStatus;31(2)數(shù)據(jù)元素被約定為ElemType類型，用戶需要根據(jù)具體情況，自行定義該數(shù)據(jù)類型。(3)算法描述為以下的函數(shù)形式：

函數(shù)類型函數(shù)名（函數(shù)參數(shù)表）

{

語句序列；

}32（4）內(nèi)存的動態(tài)分配與釋放使用new和delete動態(tài)分配和釋放內(nèi)存空間分配空間指針變量=new數(shù)據(jù)類型;釋放空間delete指針變量;（5）賦值語句（6）選擇語句（7）循環(huán)語句33（8）使用的結(jié)束語句形式有：函數(shù)結(jié)束語句return循環(huán)結(jié)束語句break;異常結(jié)束語句exit（異常代碼）；34（9）輸入輸出語句形式有：輸入語句cin(scanf())輸出語句cout(printf())（10）擴展函數(shù)有：求最大值max求最小值min35算法定義：一個有窮的指令集，這些指令為解決某一特定任務(wù)規(guī)定了一個運算序列算法的描述：

自然語言流程圖程序設(shè)計語言

偽碼1.4算法和算法分析36算法的特性：輸入有0個或多個輸入輸出

有一個或多個輸出(處理結(jié)果)

確定性

每步定義都是確切、無歧義的有窮性

算法應(yīng)在執(zhí)行有窮步后結(jié)束有效性

每一條運算應(yīng)足夠基本37算法的評價正確性可讀性健壯性高效性（時間代價和空間代價）38算法效率：用依據(jù)該算法編制的程序在計算機上執(zhí)行所消耗的時間來度量 算法的效率的度量事后統(tǒng)計事前分析估計391.事后統(tǒng)計：利用計算機內(nèi)的計時功能，不同算法的程序可以用一組或多組相同的統(tǒng)計數(shù)據(jù)區(qū)分

缺點：必須先運行依據(jù)算法編制的程序所得時間統(tǒng)計量依賴于硬件、軟件等環(huán)境因素，掩蓋算法本身的優(yōu)劣

402.事前分析估計：一個高級語言程序在計算機上運行所消耗的時間取決于：

依據(jù)的算法選用何種策略問題的規(guī)模程序語言編譯程序產(chǎn)生機器代碼質(zhì)量機器執(zhí)行指令速度同一個算法用不同的語言、不同的編譯程序、在不同的計算機上運行，效率均不同，———使用絕對時間單位衡量算法效率不合適41算法中關(guān)鍵操作（循環(huán)和遞歸）重復執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)f(n),算法的時間量度記作：T(n)=O(f(n))

時間復雜度的漸進表示法漸進符號（O）的定義：當且僅當存在一個正的常數(shù)C和n0

，使得對所有的

nn0

，有T(n)Cf(n)，則

T(n)=O(f(n))表示隨著n的增大，算法執(zhí)行的時間的增長率和f(n)的增長率相同，稱漸近時間復雜度。42n*n階矩陣加法：for(i=0;i<n;i++) for(j=0;j<n;j++) c[i][j]=a[i][j]+b[i][j];

語句的頻度（FrequencyCount):重復執(zhí)行的次數(shù)：n*n;T(n)=O(n2)即：矩陣加法的運算量和問題的規(guī)模n的平方是同一個量級43變量計數(shù)x=0;y=0;for(intk=0;k<n;k++)x++;for(inti=0;i<n;i++)

for(intj=0;j<n;j++)y++;T1(n)=O(1)T2(n)=O(n)T3(n)=O(n2)T(n)=T1(n)+T2(n)+T3(n)=O(max(1,n,n2))=O(n2)44

voidexam(floatx[][],intm,intn){floatsum[];for(inti=0;i<m;i++){//x中各行

sum[i]=0.0;//數(shù)據(jù)累加

for(intj=0;j<n;j++)

sum[i]+=x[i][j];//關(guān)鍵操作

}

for(i=0;i<m;i++)//打印各行數(shù)據(jù)和

cout<<i<<“:”<<sum[i]<<endl;//關(guān)鍵操作

}漸進時間復雜度為

O(max(m*n,m))算法的時間復雜度是由嵌套最深層語句的頻度決定的45例1：N×N矩陣相乘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]=c[i][j]+a[i][k]*b[k][j];} 算法中的基本操作語句為c[i][j]=c[i][j]+a[i][k]*b[k][j];

46例2：for(i=1;i<=n;i++)

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

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

x=x+1;語句頻度

=47T(n)=O(n3)例3：分析以下程序段的時間復雜度i=1;①while(i<=n) i=i*2;②即f(n)≤log2n，取最大值f(n)=log2n所以該程序段的時間復雜度T(n)=O(log2n)48【例4】順序查找，在數(shù)組a[i]中查找值等于e的元素，返回其所在位置。

for(i=0;i<n;i++)if(a[i]==e)returni+1;return0;有的情況下，算法中基本操作重復執(zhí)行的次數(shù)還隨問題的輸入數(shù)據(jù)集不同而不同最好情況：1次最壞情況：n平均時間復雜度為:O(n)49時間復雜度T(n)按數(shù)量級遞增順序為：

復雜度高復雜度低指數(shù)時間的關(guān)系為：

O(2n)<O(n!)<O(nn)

當n取得很大時，指數(shù)時間算法和多項式時間算法在所需時間上非常懸殊50空間復雜度:算法所需存儲空間的度量，記作:S(n)=O(f(n))其中n為問題的規(guī)模(或大小)算法要占據(jù)的空間算法本身要占據(jù)的空間，輸入/輸出，指令，常數(shù)，變量等算法要使用的輔