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

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

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

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

存儲(chǔ)內(nèi)容

指針1345

元素1

14001346

元素4∧

…….

……..

…….

1400

元素21536

…….

……..

…….1536

元素31346

鏈?zhǔn)酱鎯?chǔ)

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

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

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

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

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

順序存儲(chǔ)

鏈?zhǔn)酱鎯?chǔ)線性表

棧、隊(duì)列

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

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

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

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

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

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

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

線性表接口或用戶界面數(shù)據(jù)類型的物理實(shí)現(xiàn)封裝信息隱蔽和數(shù)據(jù)封裝，使用與實(shí)現(xiàn)相分離291.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)抽象數(shù)據(jù)類型可以通過固有的數(shù)據(jù)類型（如整型、實(shí)型、字符型等）來表示和實(shí)現(xiàn)。它有些類似C語言中的結(jié)構(gòu)（struct)類型，但增加了相關(guān)的操作教材中用的是類C語言（介于偽碼和C語言之間）作為描述工具但上機(jī)時(shí)要用具體語言實(shí)現(xiàn)，如C或C++等30(1)預(yù)定義常量及類型//函數(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)存的動(dòng)態(tài)分配與釋放使用new和delete動(dòng)態(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）擴(kuò)展函數(shù)有：求最大值max求最小值min35算法定義：一個(gè)有窮的指令集，這些指令為解決某一特定任務(wù)規(guī)定了一個(gè)運(yùn)算序列算法的描述：

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

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

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

確定性

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

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

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

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

402.事前分析估計(jì)：一個(gè)高級(jí)語言程序在計(jì)算機(jī)上運(yùn)行所消耗的時(shí)間取決于：

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

時(shí)間復(fù)雜度的漸進(jìn)表示法漸進(jìn)符號(hào)（O）的定義：當(dāng)且僅當(dāng)存在一個(gè)正的常數(shù)C和n0

，使得對(duì)所有的

nn0

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

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

語句的頻度（FrequencyCount):重復(fù)執(zhí)行的次數(shù)：n*n;T(n)=O(n2)即：矩陣加法的運(yùn)算量和問題的規(guī)模n的平方是同一個(gè)量級(jí)43變量計(jì)數(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)鍵操作

}漸進(jìn)時(shí)間復(fù)雜度為

O(max(m*n,m))算法的時(shí)間復(fù)雜度是由嵌套最深層語句的頻度決定的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：分析以下程序段的時(shí)間復(fù)雜度i=1;①while(i<=n) i=i*2;②即f(n)≤log2n，取最大值f(n)=log2n所以該程序段的時(shí)間復(fù)雜度T(n)=O(log2n)48【例4】順序查找，在數(shù)組a[i]中查找值等于e的元素，返回其所在位置。

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

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

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

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