數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)

數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)第1頁(yè)，共30頁(yè)，2023年，2月20日，星期五第1章概述第2頁(yè)，共30頁(yè)，2023年，2月20日，星期五§1.1研究?jī)?nèi)容和地位一、研究?jī)?nèi)容：研究軟件設(shè)計(jì)中常用的基本技術(shù)。

>>二、地位：第3頁(yè)，共30頁(yè)，2023年，2月20日，星期五§1.2基本概念和術(shù)語(yǔ)數(shù)據(jù)(data)

——能夠輸入到計(jì)算機(jī)中并能被計(jì)算機(jī)處理的符號(hào)的集合。（廣義）

數(shù)據(jù)元素(dataelement)

——構(gòu)成數(shù)據(jù)的基本單位（具有完整的獨(dú)立意義）。在某些場(chǎng)合還被稱為元素、記錄、結(jié)點(diǎn)、頂點(diǎn)等。第4頁(yè)，共30頁(yè)，2023年，2月20日，星期五§1.2基本概念和術(shù)語(yǔ)數(shù)據(jù)結(jié)構(gòu)(datastructure)

——構(gòu)成數(shù)據(jù)元素之間的結(jié)構(gòu)關(guān)系。線性結(jié)構(gòu)樹形結(jié)構(gòu)圖結(jié)構(gòu)（網(wǎng)狀結(jié)構(gòu)）集合第5頁(yè)，共30頁(yè)，2023年，2月20日，星期五§1.2基本概念和術(shù)語(yǔ)通常稱這幾類結(jié)構(gòu)為邏輯結(jié)構(gòu)，因?yàn)橹豢紤]了元素之間的邏輯關(guān)系。存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）

——同樣的邏輯結(jié)構(gòu)≠同樣的存儲(chǔ)結(jié)構(gòu)運(yùn)算（判斷存儲(chǔ)結(jié)構(gòu)的好壞）第6頁(yè)，共30頁(yè)，2023年，2月20日，星期五學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的方法

①邏輯結(jié)構(gòu)②運(yùn)算定義③存儲(chǔ)結(jié)構(gòu)④實(shí)現(xiàn)運(yùn)算⑤分析第7頁(yè)，共30頁(yè)，2023年，2月20日，星期五§1.3算法和算法分析第8頁(yè)，共30頁(yè)，2023年，2月20日，星期五一、算法的概念算法（目前為止沒有統(tǒng)一的說(shuō)法）：是某類問題的求解方法（粗略）：指令的有限序列滿足輸入0～n個(gè)輸出1～n個(gè)與輸入有特定聯(lián)系確定性（無(wú)二義性）相同的輸入只能有相同的輸出有窮性可行性算法在有限的時(shí)間內(nèi)結(jié)束第9頁(yè)，共30頁(yè)，2023年，2月20日，星期五二、衡量算法的度量（一）主要度量：

(1)正確性(correctness)(2)可讀性(readability)(3)健壯性(robustness)(4)效率（時(shí)間和空間）第10頁(yè)，共30頁(yè)，2023年，2月20日，星期五二、衡量算法的度量－2（二）時(shí)間性能：以時(shí)間復(fù)雜度來(lái)表示運(yùn)行算法所需的時(shí)間計(jì)算比較麻煩計(jì)算基本語(yǔ)句的執(zhí)行次數(shù)來(lái)代替具體的執(zhí)行時(shí)間次數(shù)數(shù)量級(jí)第11頁(yè)，共30頁(yè)，2023年，2月20日，星期五二、衡量算法的度量－3for（i=1；i<=n；i++）x=x+1；——O(n)如果limf(n)/g(n)=常數(shù)（≠0，∞）則f(n)，g(n)為同一數(shù)量級(jí)O(1)<O(log2n)<O(n)<O(nlog2n)<O(n2)<O(n3)<O(2n)<O(n!)例第12頁(yè)，共30頁(yè)，2023年，2月20日，星期五三、算法指定的語(yǔ)言1、計(jì)算機(jī)語(yǔ)言

優(yōu)：易上機(jī)實(shí)現(xiàn)；缺：死板；2、自然語(yǔ)言

優(yōu)：靈活；缺：不易上機(jī)實(shí)現(xiàn)；3、偽語(yǔ)言(類語(yǔ)言)

類pascal類c類c++第13頁(yè)，共30頁(yè)，2023年，2月20日，星期五四、類c語(yǔ)言（一）算法的形式——函數(shù)返回類型函數(shù)名（參數(shù)表）

{

程序序列；

return（返回值）；//當(dāng)返回類型為void可省

}返回類型：int，char，double，void等等第14頁(yè)，共30頁(yè)，2023年，2月20日，星期五（二）語(yǔ)句1、賦值和交換：

v=表達(dá)式；v1<=>v2；2、if語(yǔ)句：條件S1S2成立ifs1；elses2；條件S1成立或ifs1

第15頁(yè)，共30頁(yè)，2023年，2月20日，星期五（二）語(yǔ)句－23、switch語(yǔ)句：switch（表達(dá)式）

{case常量表達(dá)式1：語(yǔ)句1[break；]case常量表達(dá)式2：語(yǔ)句2[break；]

……case常量表達(dá)式n：語(yǔ)句n[break；][default：語(yǔ)句n+1]}switch括弧內(nèi)的表達(dá)式可以是任何類型；每一個(gè)case后的表達(dá)式必須互不相同；

case的執(zhí)行次序無(wú)關(guān)；第16頁(yè)，共30頁(yè)，2023年，2月20日，星期五（二）語(yǔ)句－34、break語(yǔ)句：

break；——跳出循環(huán)或開關(guān)語(yǔ)句；5、continue語(yǔ)句：

continue；——進(jìn)行下一層循環(huán)；6、循環(huán)語(yǔ)句：

(1)for語(yǔ)句

(2)while語(yǔ)句

(3)do-while語(yǔ)句7、輸入/輸出語(yǔ)句：scanf（格式控制，輸入列表）printf（格式控制，輸出列表）第17頁(yè)，共30頁(yè)，2023年，2月20日，星期五（二）語(yǔ)句－48、出錯(cuò)處理語(yǔ)句：

error（“錯(cuò)誤信息”）；9、最大最小函數(shù)：

max（n1，n2）；min（n1，n2）；10、注釋：語(yǔ)句；//……11、return語(yǔ)句：

return（返回值）；

//返回一個(gè)值并退出當(dāng)前運(yùn)行函數(shù)第18頁(yè)，共30頁(yè)，2023年，2月20日，星期五（三）指針和動(dòng)態(tài)變量靜態(tài)變量：在程序運(yùn)行過程中一直存在的變量；動(dòng)態(tài)變量：在程序運(yùn)行過程中產(chǎn)生和釋放的變量；如何實(shí)現(xiàn)動(dòng)態(tài)變量？——借助指針第19頁(yè)，共30頁(yè)，2023年，2月20日，星期五（三）指針和動(dòng)態(tài)變量1、指針是一種簡(jiǎn)單變量，用來(lái)記錄變量的地址。格式：數(shù)據(jù)類型*指針變量名指針?biāo)赶虻牡?0頁(yè)，共30頁(yè)，2023年，2月20日，星期五（三）指針和動(dòng)態(tài)變量－例

int*P，*R，*Q；例P51000P=1000；*P=5

R202000P=2000；*R=20

*P*RQ∧Q=Null

第21頁(yè)，共30頁(yè)，2023年，2月20日，星期五（三）指針和動(dòng)態(tài)變量－例2假設(shè)分別做了以下操作：（1）*P=*R；P51000R202000*P*RQ∧P51000R202000*P*R執(zhí)行前：P51000R202000*P*R執(zhí)行后：\20第22頁(yè)，共30頁(yè)，2023年，2月20日，星期五（三）指針和動(dòng)態(tài)變量－例2假設(shè)分別做了以下操作：（2）P=R；P51000R202000*P*RQ∧P51000R202000*P*R執(zhí)行前：P51000R202000*P*R執(zhí)行后：×第23頁(yè)，共30頁(yè)，2023年，2月20日，星期五課堂練習(xí)

int*P，*R，*Q；*P=10;*R=20;printf(“%d%d”,*P,*R);*P=*R;*Q=30;printf(“%d%d”,*P,*Q);P=Q;*P=40;*Q=50;printf(“%d%d”,*P,*Q);//*p是數(shù)值，p是地址102020305050第24頁(yè)，共30頁(yè)，2023年，2月20日，星期五課堂練習(xí)解答int*P，*R，*Q；*P=10;*R=20;printf(“%d%d”,*P,*R);P10R20*P*R此時(shí)輸出為：1020第25頁(yè)，共30頁(yè)，2023年，2月20日，星期五課堂練習(xí)解答－2*P=*R;*Q=30;printf(“%d%d”,*P,*Q);P10R20*P*R此時(shí)輸出為：2030P10Q30*P*QR20*R\20第26頁(yè)，共30頁(yè)，2023年，2月20日，星期五P20*PQ30*Q×*P課堂練習(xí)解答－2P=Q;*P=40;*Q=50;printf(“%d%d”,*P,*Q);此時(shí)輸出為：5050P20Q30*P*QR20*R\40\50第27頁(yè)，共30頁(yè)，2023年，2月20日，星期五（三）指針和動(dòng)態(tài)變量2、動(dòng)態(tài)變量（1）產(chǎn)生變量：mallocP=(指針類型)malloc(sizeof(數(shù)據(jù)類型