數(shù)據(jù)結構基礎

數(shù)據(jù)結構基礎第一頁，共三十頁，編輯于2023年，星期六第1章概述第二頁，共三十頁，編輯于2023年，星期六§1.1研究內(nèi)容和地位一、研究內(nèi)容：研究軟件設計中常用的基本技術。

>>二、地位：第三頁，共三十頁，編輯于2023年，星期六§1.2基本概念和術語數(shù)據(jù)(data)

——能夠輸入到計算機中并能被計算機處理的符號的集合。（廣義）

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

——構成數(shù)據(jù)的基本單位（具有完整的獨立意義）。在某些場合還被稱為元素、記錄、結點、頂點等。第四頁，共三十頁，編輯于2023年，星期六§1.2基本概念和術語數(shù)據(jù)結構(datastructure)

——構成數(shù)據(jù)元素之間的結構關系。線性結構樹形結構圖結構（網(wǎng)狀結構）集合第五頁，共三十頁，編輯于2023年，星期六§1.2基本概念和術語通常稱這幾類結構為邏輯結構，因為只考慮了元素之間的邏輯關系。存儲結構（物理結構）

——同樣的邏輯結構≠同樣的存儲結構運算（判斷存儲結構的好壞）第六頁，共三十頁，編輯于2023年，星期六學習數(shù)據(jù)結構的方法

①邏輯結構②運算定義③存儲結構④實現(xiàn)運算⑤分析第七頁，共三十頁，編輯于2023年，星期六§1.3算法和算法分析第八頁，共三十頁，編輯于2023年，星期六一、算法的概念算法（目前為止沒有統(tǒng)一的說法）：是某類問題的求解方法（粗略）：指令的有限序列滿足輸入0～n個輸出1～n個與輸入有特定聯(lián)系確定性（無二義性）相同的輸入只能有相同的輸出有窮性可行性算法在有限的時間內(nèi)結束第九頁，共三十頁，編輯于2023年，星期六二、衡量算法的度量（一）主要度量：

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

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

優(yōu)：靈活；缺：不易上機實現(xiàn)；3、偽語言(類語言)類pascal類c類c++第十三頁，共三十頁，編輯于2023年，星期六四、類c語言（一）算法的形式——函數(shù)返回類型函數(shù)名（參數(shù)表）

{

程序序列；

return（返回值）；//當返回類型為void可省

}返回類型：int，char，double，void等等第十四頁，共三十頁，編輯于2023年，星期六（二）語句1、賦值和交換：

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

第十五頁，共三十頁，編輯于2023年，星期六（二）語句－23、switch語句：switch（表達式）

{case常量表達式1：語句1[break；]case常量表達式2：語句2[break；]

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

case的執(zhí)行次序無關；第十六頁，共三十頁，編輯于2023年，星期六（二）語句－34、break語句：

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

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

(1)for語句

(2)while語句

(3)do-while語句7、輸入/輸出語句：scanf（格式控制，輸入列表）printf（格式控制，輸出列表）第十七頁，共三十頁，編輯于2023年，星期六（二）語句－48、出錯處理語句：

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

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

return（返回值）；

//返回一個值并退出當前運行函數(shù)第十八頁，共三十頁，編輯于2023年，星期六（三）指針和動態(tài)變量靜態(tài)變量：在程序運行過程中一直存在的變量；動態(tài)變量：在程序運行過程中產(chǎn)生和釋放的變量；如何實現(xiàn)動態(tài)變量？——借助指針第十九頁，共三十頁，編輯于2023年，星期六（三）指針和動態(tài)變量1、指針是一種簡單變量，用來記錄變量的地址。格式：數(shù)據(jù)類型*指針變量名指針所指向的第二十頁，共三十頁，編輯于2023年，星期六（三）指針和動態(tài)變量－例

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

R202000P=2000；*R=20

*P*RQ∧Q=Null

第二十一頁，共三十頁，編輯于2023年，星期六（三）指針和動態(tài)變量－例2假設分別做了以下操作：（1）*P=*R；P51000R202000*P*RQ∧P51000R202000*P*R執(zhí)行前：P51000R202000*P*R執(zhí)行后：\20第二十二頁，共三十頁，編輯于2023年，星期六（三）指針和動態(tài)變量－例2假設分別做了以下操作：（2）P=R；P51000R202000*P*RQ∧P51000R202000*P*R執(zhí)行前：P51000R202000*P*R執(zhí)行后：×第二十三頁，共三十頁，編輯于2023年，星期六課堂練習

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第二十四頁，共三十頁，編輯于2023年，星期六課堂練習解答int*P，*R，*Q；*P=10;*R=20;printf(“%d%d”,*P,*R);P10R20*P*R此時輸出為：1020第二十五頁，共三十頁，編輯于2023年，星期六課堂練習解答－2*P=*R;*Q=30;printf(“%d%d”,*P,*Q);P10R20*P*R此時輸出為：2030P10Q30*P*QR20*R\20第二十六頁，共三十頁，編輯于2023年，星期六P20*PQ30*Q×*P課堂練習解答－2P=Q;*P=40;*Q=50;printf(“%d%d”,*P,*Q);此時輸出為：5050P20Q30*P*QR20*R\40\50第二十七頁，共三十頁，編輯于2023年，星期六（三）指針和動態(tài)變量2、動態(tài)變量（1）產(chǎn)生變量：mallocP=(指針類型)malloc(sizeof(數(shù)據(jù)