數(shù)據(jù)結(jié)構(gòu)01-緒論.ppt

第1章緒論數(shù)據(jù)結(jié)構(gòu)主講教師：祝建華華中科技大學(xué)計(jì)算機(jī)學(xué)院21.基本數(shù)據(jù)結(jié)構(gòu)的定義、特性、運(yùn)算與算法1.1線性結(jié)構(gòu)：線性表；棧,隊(duì)列,雙隊(duì)列；數(shù)組,串。1.2非線性結(jié)構(gòu)：樹(shù),二叉樹(shù)；圖,網(wǎng)絡(luò)。2.數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)結(jié)構(gòu)與實(shí)現(xiàn)選擇存儲(chǔ)結(jié)構(gòu),設(shè)計(jì)算法3.查找算法：順序,折半,分塊,哈希,二叉排序樹(shù)等4.排序算法：內(nèi)部排序,外部排序5.文件6.基本應(yīng)用與綜合應(yīng)用本課程的任務(wù)華中科技大學(xué)計(jì)算機(jī)學(xué)院31.閱讀教材與參考書、聽(tīng)課、記筆記；2.完成一定數(shù)量的書面作業(yè)；3.使用C或C+完成上機(jī)作業(yè)。4.教材與參考書：數(shù)據(jù)結(jié)構(gòu)（c語(yǔ)言版）嚴(yán)蔚敏清華大學(xué)出版社數(shù)據(jù)結(jié)構(gòu)楊微微高等教育出版社數(shù)據(jù)結(jié)構(gòu)楊秀金西安電子科技大學(xué)出版社5.習(xí)題集數(shù)據(jù)結(jié)構(gòu)題集（c語(yǔ)言版）嚴(yán)蔚敏清華大學(xué)出版社基本要求華中科技大學(xué)計(jì)算機(jī)學(xué)院4c)-(s*b)-(s*a)-(s*s2cba則s=area=1.1數(shù)據(jù)結(jié)構(gòu)課程的任務(wù)建立數(shù)學(xué)模型是分析具體問(wèn)題的過(guò)程，包括：分析具體問(wèn)題中操作對(duì)象；找出這些對(duì)象間的關(guān)系，并用數(shù)學(xué)語(yǔ)言描述。數(shù)學(xué)模型分兩類：1）數(shù)值計(jì)算類：例：根據(jù)三條邊，求三角形面積。假定：三條邊依次為a,b,c三個(gè)實(shí)型數(shù)，滿足：a0,b0,c0,a+bc,b+ca,c+ab華中科技大學(xué)計(jì)算機(jī)學(xué)院52）非數(shù)值計(jì)算類：例1:5個(gè)整數(shù)組成的集合：D=20,-5，66,15,44其中:20,-5,66等稱為數(shù)據(jù)元素(元素)，元素與元素之間關(guān)系是它們同屬于集合D。元素與元素間無(wú)直接關(guān)系。例2:一列整數(shù)：(線性結(jié)構(gòu))L=(20,-5，66,15,44）其中:元素與元素之間在L中是前后關(guān)系或線性關(guān)系。L=(20,-5,66,15,44)是一個(gè)線性表。華中科技大學(xué)計(jì)算機(jī)學(xué)院6例3一張登記表其中：姓名、性別、年齡是數(shù)據(jù)項(xiàng)(item)、數(shù)據(jù)域(field)；(姓名，性別，年齡)是記錄(record),C語(yǔ)言將記錄(record)定義為”結(jié)構(gòu)”(struct)；登記表也是一個(gè)線性表。序號(hào)姓名性別年齡1李剛男25記錄12王霞女29記錄23劉大海男40記錄34李愛(ài)林男44記錄4華中科技大學(xué)計(jì)算機(jī)學(xué)院7其中:A、B、C等是結(jié)點(diǎn)(node)；A與B,B與E,A與C之間是層次關(guān)系或父子關(guān)系。華中科技大學(xué)(A)計(jì)算機(jī)學(xué)院(B)管理學(xué)院(C)成教學(xué)院(D)科學(xué)系(E)應(yīng)用系(F)工程系(G)例4樹(shù)狀結(jié)構(gòu)華中科技大學(xué)計(jì)算機(jī)學(xué)院8ABDCEFG其中：A、B、C等是頂點(diǎn)(vertex),圖中任意兩個(gè)頂點(diǎn)之間都可能有關(guān)系。例5圖狀結(jié)構(gòu)華中科技大學(xué)計(jì)算機(jī)學(xué)院9數(shù)據(jù)結(jié)構(gòu)是一門研究程序設(shè)計(jì)中的數(shù)據(jù)、數(shù)據(jù)間的關(guān)系和操作的技術(shù)在計(jì)算機(jī)發(fā)展初期，計(jì)算機(jī)主要是處理數(shù)值計(jì)算問(wèn)題，只涉及到簡(jiǎn)單的數(shù)據(jù)類型，程序員主要注重程序設(shè)計(jì)技巧，不太重視數(shù)據(jù)結(jié)構(gòu)。隨著計(jì)算機(jī)應(yīng)用領(lǐng)域的擴(kuò)大，“非數(shù)值性問(wèn)題”越來(lái)越顯得重要。據(jù)統(tǒng)計(jì)，如今處理非數(shù)值性問(wèn)題占用了90%以上的機(jī)器時(shí)間，這類問(wèn)題涉及到的數(shù)據(jù)