數(shù)據(jù)結(jié)構(gòu)主講教師：李麗平1/19/20241課程要求課前請(qǐng)做好預(yù)習(xí)保持課堂安靜，頭腦清醒，思維活潑認(rèn)真、獨(dú)立、按時(shí)完成并提交作業(yè)重視上機(jī)實(shí)踐，有效利用珍貴的上機(jī)時(shí)間不遲到早退，不曠課，保證學(xué)習(xí)的連續(xù)性先序課：《C++程序設(shè)計(jì)》1/19/20242什么是數(shù)據(jù)結(jié)構(gòu)根本概念和術(shù)語算法描述算法分析第一章緒論1/19/202431.1數(shù)據(jù)結(jié)構(gòu)的根本概念和術(shù)語什么是數(shù)據(jù)結(jié)構(gòu)例1書目自動(dòng)檢索系統(tǒng)登錄號(hào)：書名：作者名：分類號(hào)：出版單位：出版時(shí)間：價(jià)格：書目卡片書目文件按書名按作者名按分類號(hào)索引表線性表1/19/20244例2人機(jī)對(duì)奕問題樹……..……..…...…...…...…...1/19/20245例3：在n個(gè)城市之間建立通信線路圖1/19/20246數(shù)據(jù)結(jié)構(gòu)定義:是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作等等的學(xué)科描述這類非數(shù)值計(jì)算問題的數(shù)學(xué)模型不是數(shù)學(xué)方程,而是樹、表和圖之類的數(shù)據(jù)結(jié)構(gòu)。1/19/20247根本概念和術(shù)語數(shù)據(jù)〔data)—所有能輸入到計(jì)算機(jī)中去的描述客觀事物的符號(hào)數(shù)據(jù)元素〔dataelement〕—數(shù)據(jù)的根本單位，在計(jì)算機(jī)程序中通常作為一個(gè)整體進(jìn)行考慮和處理數(shù)據(jù)項(xiàng)〔dataitem〕—有獨(dú)立含義的數(shù)據(jù)最小單位數(shù)據(jù)對(duì)象〔DataObject)性質(zhì)相同的數(shù)據(jù)元素的集合數(shù)據(jù)的邏輯結(jié)構(gòu)〔datalogicalstructure)—存在著一種或多種關(guān)系的數(shù)據(jù)元素的集合，也稱數(shù)據(jù)結(jié)構(gòu)〔datastructure)1/19/20248序偶：由有固定次序的兩個(gè)客體組成，常用來表示客體之間的關(guān)系序偶的表示：<a,b>前驅(qū)后繼1/19/20249根據(jù)數(shù)據(jù)元素間關(guān)系的根本特性，有四種根本數(shù)據(jù)結(jié)構(gòu)〔集合〕——數(shù)據(jù)元素間除“同屬于一個(gè)集合〞外，無其它關(guān)系線性結(jié)構(gòu)——一對(duì)一，如線性表、棧、隊(duì)列樹形結(jié)構(gòu)——一對(duì)多，如樹圖狀結(jié)構(gòu)——多對(duì)多，如圖1/19/202410數(shù)據(jù)的存儲(chǔ)〔物理〕結(jié)構(gòu)—數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的存放方式存儲(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)系1/19/202411元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲(chǔ)地址存儲(chǔ)內(nèi)容Loc(元素i)=Lo+（i-1)*m順序存儲(chǔ)1/19/2024121536元素21400元素11346元素3∧元素41345h存儲(chǔ)地址存儲(chǔ)內(nèi)容指針1345元素1

14001346元素4∧…….……..…….

1400

元素21536…….……..…….1536元素31346

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

h1/19/202413數(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ǔ)線性表?xiàng)ｊ?duì)樹形結(jié)構(gòu)圖形結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面：1/19/2024141.2算法和算法描述什么是算法算法〔algorithm〕：解決某一特定問題的具體步驟的描述，是指令的有限序列算法特性1/19/202415算法的描述工具框圖算法描述虛擬語言算法描述類語言算法描述程序設(shè)計(jì)語言1/19/2024161.3算法分析技術(shù)初步算法的評(píng)價(jià)—衡量算法優(yōu)劣的標(biāo)準(zhǔn)正確性(correctness)可讀性(readability)健壯性(robustness)效率：空間效率和時(shí)間效率1/19/202417算法效率的度量運(yùn)行時(shí)間=算法中每條語句執(zhí)行時(shí)間之和。每條語句執(zhí)行時(shí)間=該語句的執(zhí)行次數(shù)〔頻度〕*語句執(zhí)行一次所需時(shí)間。語句執(zhí)行一次所需時(shí)間取決于機(jī)器的指令性能和速度和編譯所產(chǎn)生的代碼質(zhì)量，很難確定。設(shè)每條語句執(zhí)行一次所需時(shí)間為單位時(shí)間，那么一個(gè)算法的運(yùn)行時(shí)間就是該算法中所有語句的頻度之和。一般情況下并不是計(jì)算所有的語句的頻度，而是只計(jì)算執(zhí)行次數(shù)最多的那些語句的頻度，這樣的語句對(duì)應(yīng)的操作叫根本操作?！哺静僮饕话闶亲顑?nèi)層循環(huán)的循環(huán)體〕。一般來說，設(shè)算法中根本操作的執(zhí)行次數(shù)是問題規(guī)模n的某個(gè)函數(shù)f(n)1/19/202418算法的時(shí)間復(fù)雜度記作：

T(n)=O(f(n))

它表示隨問題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率與f(n)的增長(zhǎng)率相同。分析一個(gè)算法的時(shí)間復(fù)雜度的步驟：找出根本操作計(jì)算根本操作執(zhí)行的次數(shù)忽略所有的常數(shù)和低次項(xiàng)，用大O表示法表示出來1/19/202419作業(yè)：100元買100支筆,其中鋼筆3元/支,圓珠筆2元/支,鉛筆0.5元/支.寫算法輸出各種組合方案解法1#defineN100voidscheme(){inti,j,k,count,money;for(i=0;i<=N;i++)

for(j=0;j<=N;j++)for(k=0;k<=N;k++){count=i+j+k;money=3*i+2*j+0.5*k;

if(count==N&&money==N)printf(“%d,%d,%d\n%〞,i,j,k);

}

}算法的時(shí)間復(fù)雜度為O(N3)1/19/202420例題：100元買100支筆,其中鋼筆3元/支,圓珠筆2元/支,鉛筆0.5元/支.寫算法輸出各種組合方案解法2#defineN100voidscheme(){inti,j;for(i=0;i<=N/3;i++)for(j=0;