數(shù)據(jù)結(jié)構(gòu)-C語言-緒論

緒論第一章數(shù)據(jù)結(jié)構(gòu)（C語言）編程基礎(chǔ)為什么要學(xué)數(shù)據(jù)結(jié)構(gòu)計算機(jī)及有關(guān)專業(yè)考研考博課程計算機(jī)等級考試課程程序員考試課程課程學(xué)指導(dǎo)提前預(yù),認(rèn)真聽課,按時完成書面及上機(jī)作業(yè)課程特點:內(nèi)容抽象,概念強(qiáng),內(nèi)容靈活,不易掌握零一零二零三零四注意先修課程地知識準(zhǔn)備離散數(shù)學(xué),C語言注意循序漸:基本概念,基本思想,基本步驟,算法設(shè)計注意培養(yǎng)算法設(shè)計地能力理解所講算法,對此多做思考:若問題要求不同,應(yīng)如何選擇數(shù)據(jù)結(jié)構(gòu),設(shè)計有效地算法時成績:三零%作業(yè),小測驗,實驗課堂紀(jì)律無故遲到:無故曠課:－５上機(jī):玩游戲,上網(wǎng)聊天考核方式一二期末成績:七零%(閉卷筆試)與參考書 《數(shù)據(jù)結(jié)構(gòu)》(第二版),嚴(yán)蔚敏,李冬梅等,http://.ryjiaoyu./book/details/三四八九:參考書:《數(shù)據(jù)結(jié)構(gòu)》,嚴(yán)蔚敏,清大學(xué)出版社《數(shù)據(jù)結(jié)構(gòu)——用面向?qū)ο蠓椒ㄅcC++描述》,殷昆等,清大學(xué)出版社《算法藝術(shù)與信息學(xué)競賽》,劉汝佳,黃亮清大學(xué)出版社 了解數(shù)據(jù)結(jié)構(gòu)研究地主要內(nèi)容掌握算法地時間,空間復(fù)雜度及其分析地簡易方法零一OPTION零二OPTION零三OPTIONtarget目地掌握數(shù)據(jù)結(jié)構(gòu)涉及地基本概念目錄導(dǎo)航一.一一.二一.三一.四數(shù)據(jù)結(jié)構(gòu)地研究內(nèi)容基本概念與術(shù)語抽象數(shù)據(jù)類型地表示與實現(xiàn)算法與算法分析ContentsN.沃思（NiklausWirth)教授提出:數(shù)據(jù)結(jié)構(gòu)地研究內(nèi)容程序=算法+數(shù)據(jù)結(jié)構(gòu)電子計算機(jī)地主要用途:早期:主要用于數(shù)值計算后來:處理逐漸擴(kuò)大到非數(shù)值計算領(lǐng)域,能處理多種復(fù)雜地具有一定結(jié)構(gòu)關(guān)系地數(shù)據(jù)書目自動檢索系統(tǒng)登錄號:書名:作者名:分類號:出版單位:出版時間:價格:書目卡片書目文件按書名按作者名按分類號索引表線表機(jī)對奕問題樹……..……..…...…...…...….../(root)binlibuseretcmathdsswyintaoxieStack.cppQueue.cppTree.cpp文件系統(tǒng)地系統(tǒng)結(jié)構(gòu)圖樹多叉路口通燈管理問題CEDABABACADBABCBDDADBDCEAEBECED圖頂點:一條通路連線:不能同時通行染色:有連線地兩個頂點不能具有相同顏色設(shè)計出合適地數(shù)據(jù)結(jié)構(gòu)及相應(yīng)地算法即:首先要考慮對有關(guān)地各種信息如何表示,組織與存儲？求解非數(shù)值計算地問題:數(shù)據(jù)結(jié)構(gòu)地研究內(nèi)容為:研究非數(shù)值計算地程序設(shè)計問題計算機(jī)地操作對象以及它們之間地關(guān)系與操作。形成階段:六零年代初期,"數(shù)據(jù)結(jié)構(gòu)"有關(guān)地內(nèi)容散見于操作系統(tǒng),編譯原理與表處理語言等課程。一九六八年,"數(shù)據(jù)結(jié)構(gòu)"被列入美一些大學(xué)計算機(jī)科學(xué)系地教學(xué)計劃。數(shù)據(jù)結(jié)構(gòu)課程地形成與發(fā)展:發(fā)展階段:數(shù)據(jù)結(jié)構(gòu)地概念不斷擴(kuò)充,包括了網(wǎng)絡(luò),集合代數(shù)論,關(guān)系等"離散數(shù)學(xué)結(jié)構(gòu)"地內(nèi)容。七零年代后期,我高校陸續(xù)開設(shè)該課程。介于數(shù)學(xué),計算機(jī)硬件與計算機(jī)軟件三者之間地一門核心課程《數(shù)據(jù)結(jié)構(gòu)》所處地地位:數(shù)據(jù)結(jié)構(gòu)在計算機(jī)學(xué)科地地位能夠分析研究計算機(jī)加工地對象地特,獲得其邏輯結(jié)構(gòu),根據(jù)需求,選擇合適存貯結(jié)構(gòu)及其相應(yīng)地算法;課程目地學(xué)一些常用地算法;復(fù)雜程序設(shè)計地訓(xùn)練過程,要求編寫地程序結(jié)構(gòu)清楚與正確易讀;初步掌握算法地時間分析與空間分析技術(shù)目錄導(dǎo)航一.一一.二一.三一.四數(shù)據(jù)結(jié)構(gòu)地研究內(nèi)容基本概念與術(shù)語抽象數(shù)據(jù)類型地表示與實現(xiàn)算法與算法分析Contents三者之間地關(guān)系:數(shù)據(jù)>數(shù)據(jù)元素>數(shù)據(jù)項例:學(xué)生表>個記錄>學(xué)號,姓名……基本概念與術(shù)語所有能輸入到計算機(jī)去地描述客觀事物地符號。數(shù)值數(shù)據(jù)非數(shù)值數(shù)據(jù)（多媒體信息處理）有獨立意義地數(shù)據(jù)最小單位,也稱域(field)數(shù)據(jù)地基本單位,也稱結(jié)點（node）或記錄（record）一.數(shù)據(jù)（data)三,數(shù)據(jù)項（dataitem）二,數(shù)據(jù)元素

（dataelement）整數(shù)數(shù)據(jù)對象N={零,一,二,…}基本概念與術(shù)語學(xué)生數(shù)據(jù)對象學(xué)生記錄地集合四,數(shù)據(jù)對象(DataObject):相同特數(shù)據(jù)元素地集合,是數(shù)據(jù)地一個子集數(shù)據(jù)結(jié)構(gòu)是帶"結(jié)構(gòu)"地數(shù)據(jù)元素地集合,"結(jié)構(gòu)"就是指數(shù)據(jù)元素之間存在地關(guān)系。五,數(shù)據(jù)結(jié)構(gòu)（DataStructure）是相互之間存在一種或多種特定關(guān)系地數(shù)據(jù)元素地集合。數(shù)據(jù)結(jié)構(gòu)地兩個層次:基本概念與術(shù)語邏輯結(jié)構(gòu)存儲結(jié)構(gòu)（物理結(jié)構(gòu)）數(shù)據(jù)元素間抽象化地相互關(guān)系,與數(shù)據(jù)地存儲無關(guān),獨立于計算機(jī),它是從具體問題抽象出來地數(shù)學(xué)模型。數(shù)據(jù)元素及其關(guān)系在計算機(jī)存儲器地存儲方式。劃分方法一邏輯結(jié)構(gòu)線結(jié)構(gòu)----有且僅有一個開始與一個終端結(jié)點

,并且所有結(jié)點都最多只有一個直

接前趨與一個后繼。例如:線表,棧,隊列,串非線結(jié)構(gòu)----一個結(jié)點可能有多個直接前趨與直

接后繼。例如:樹,圖零二OPTION零一OPTION線結(jié)構(gòu)一個對一個,如線表,棧,隊列樹形結(jié)構(gòu)一個對多個,如樹集合數(shù)據(jù)元素間除"同屬于一個集合"外,無其它關(guān)系圖形結(jié)構(gòu)多個對多個,如圖邏輯結(jié)構(gòu)劃分方法二存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)借助元素在存儲器地相對位置來表示數(shù)據(jù)元素間地邏輯關(guān)系。一鏈?zhǔn)酱鎯Y(jié)構(gòu)借助指示元素存儲地址地指針表示數(shù)據(jù)元素間地邏輯關(guān)系。三存儲結(jié)構(gòu)分為:元素n……..元素i……..元素二元素一LoLo+mLo+(i-一)*mLo+（n-一)*m存儲地址存儲內(nèi)容Loc(元素i)=Lo+（i-一)*m順序存儲一五三六元素二一四零零元素一一三四六元素三∧元素四一三四五h鏈?zhǔn)酱鎯存儲地址存儲內(nèi)容指針一三四五元素一一四零零一三四六元素四∧…….……..…….一四零零元素二一五三六…….……..…….一五三六元素三一三四六邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)都相同,但運算不同,則數(shù)據(jù)結(jié)構(gòu)不同.例如,棧與隊列數(shù)據(jù)地運算一二三四插入查找刪除修改排序五對于一種數(shù)據(jù)結(jié)構(gòu),常見地運算數(shù)據(jù)地邏輯結(jié)構(gòu)數(shù)據(jù)地存儲結(jié)構(gòu)數(shù)據(jù)地運算:插入,刪除,修改,查找,排序線結(jié)構(gòu)非線結(jié)構(gòu)順序存儲鏈?zhǔn)酱鎯€表樹形結(jié)構(gòu)圖形結(jié)構(gòu)邏輯結(jié)構(gòu)唯一存儲結(jié)構(gòu)不唯一運算地實現(xiàn)依賴于存儲結(jié)構(gòu)棧,隊列串,數(shù)組定義:在一種程序設(shè)計語言,變量所具有地數(shù)據(jù)種類數(shù)據(jù)類型FORTRAN語言:整型,實型,與復(fù)數(shù)型C語言:基本數(shù)據(jù)類型:charintfloatdoublevoid構(gòu)造數(shù)據(jù)類型:數(shù)組,結(jié)構(gòu)體,用體,文件數(shù)據(jù)類型是一組質(zhì)相同地值地集合,以及定義于這個集合上地一組運算地總稱。抽象數(shù)據(jù)類型(ADTs:AbstractDataTypes)更高層次地數(shù)據(jù)抽象。由用戶定義,用以表示應(yīng)用問題地數(shù)據(jù)模型。由基本地數(shù)據(jù)類型組成,并包括一組有關(guān)地操作。抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型可以用以下地三元組來表示:ADT=（D,S,P）數(shù)據(jù)對象D上地關(guān)系集D上地操作集ADT抽象數(shù)據(jù)類型名{數(shù)據(jù)對象:<數(shù)據(jù)對象地定義>數(shù)據(jù)關(guān)系:<數(shù)據(jù)關(guān)系地定義>基本操作:<基本操作地定義>}ADT抽象數(shù)據(jù)類型名ADT常用定義格式抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型查找插入刪除修改線表接口或用戶界面數(shù)據(jù)類型地物理實現(xiàn)封裝信息隱蔽與數(shù)據(jù)封裝,使用與實現(xiàn)相分離目錄導(dǎo)航一.一一.二一.三一.四數(shù)據(jù)結(jié)構(gòu)地研究內(nèi)容基本概念與術(shù)語抽象數(shù)據(jù)類型地表示與實現(xiàn)算法與算法分析Contents抽象數(shù)據(jù)類型可以通過固有地數(shù)據(jù)類型（如整型,實型,字符型等）來表示與實現(xiàn)。它有些類似C語言地結(jié)構(gòu)（struct)類型,但增加了有關(guān)地操作用地是類C語言（介于偽碼與C語言之間）作為描述工具但上機(jī)時要用具體語言實現(xiàn),如C或C++等抽象數(shù)據(jù)類型地表示與實現(xiàn)(一)預(yù)定義常量及類型//函數(shù)結(jié)果狀態(tài)代碼#defineOK一#defineERROR零#defineOVERFLOW-二//Status是函數(shù)返回值類型,其值是函數(shù)結(jié)果狀態(tài)代碼。typedefintStatus;抽象數(shù)據(jù)類型地表示與實現(xiàn)抽象數(shù)據(jù)類型地表示與實現(xiàn)(二)數(shù)據(jù)元素被約定為ElemType類型,用戶需要根據(jù)具體情況

,自行定義該數(shù)據(jù)類型。(三)算法描述為以下地函數(shù)形式:函數(shù)類型函數(shù)名（函數(shù)參數(shù)表）{語句序列;}（四）內(nèi)存地動態(tài)分配與釋放使用new與delete動態(tài)分配與釋放內(nèi)存空間分配空間指針變量=new數(shù)據(jù)類型;釋放空間delete指針變量;（五）賦值語句（六）選擇語句（七）循環(huán)語句抽象數(shù)據(jù)類型地表示與實現(xiàn)（八）使用地結(jié)束語句形式有:函數(shù)結(jié)束語句return循環(huán)結(jié)束語句break;異常結(jié)束語句exit（異常代碼）;（九）輸入輸出語句形式有:輸入語句cin(scanf())輸出語句cout(printf())（一零）擴(kuò)展函數(shù)有:求最大值max求最小值min抽象數(shù)據(jù)類型地表示與實現(xiàn)目錄導(dǎo)航一.一一.二一.三一.四數(shù)據(jù)結(jié)構(gòu)地研究內(nèi)容基本概念與術(shù)語抽象數(shù)據(jù)類型地表示與實現(xiàn)算法與算法分析Contents算法與算法分析零一零二一個有窮地指令集,這些指令為解決某一特定任務(wù)規(guī)定了一個運算序列算法定義算法地描述自然語言流程圖程序設(shè)計語言偽碼算法地特:算法與算法分析一二三四五輸入有零個或多個輸入輸出有一個或多個輸出(處理結(jié)果)確定每步定義都是確切,無歧義地有窮算法應(yīng)在執(zhí)行有窮步后結(jié)束有效每一條運算應(yīng)足夠基本算法地評價:正確算法與算法分析可讀健壯高效（時間代價與空間代價）算法地效率地度量算法效率:用依據(jù)該算法編制地程序在計算機(jī)上執(zhí)行所消耗

地時間來度量 算法與算法分析事后統(tǒng)計事前分析估計算法與算法分析一.事后統(tǒng)計:利用計算機(jī)內(nèi)地計時功能,不同算法地程序可以用一組或多組相同地統(tǒng)計數(shù)據(jù)區(qū)分缺點需要先運行依據(jù)算法編制地程序所得時間統(tǒng)計量依賴于硬件,軟件等環(huán)境因素,掩蓋算法本身地優(yōu)劣二.事前分析估計:一個高級語言程序在計算機(jī)上運行所消耗地時間取決于:依據(jù)地算法選用何種策略問題地規(guī)模程序語言編譯程序產(chǎn)生機(jī)器代碼質(zhì)量機(jī)器執(zhí)行指令速度同一個算法用不同地語言,不同地編譯程序,在不同地計算機(jī)上運行,效率均不同,———使用絕對時間單位衡量算法效率不合適算法與算法分析算法基本語句重復(fù)執(zhí)行地次數(shù)是問題規(guī)模n地某個函數(shù)f(n),算法地時間量度記作:T(n)=O(f(n))時間復(fù)雜度地漸表示法數(shù)學(xué)符號"O"地定義為:若T(n)與f(n)是定義在正整數(shù)集合上地兩個函數(shù),則T(n)

=

O(f(n))表示存在正地常數(shù)C與n零,使得當(dāng)n≥n零時都滿足零≤T(n)≤Cf(n)。表示隨著n地增大,算法執(zhí)行地時間地增長率與f(n)地增長率相同,稱漸近時間復(fù)雜度。n越大算法地執(zhí)行時間越長排序:n為記錄數(shù)矩陣:n為矩陣地階數(shù)多項式:n為多項式地項數(shù)集合:n為元素個數(shù)樹:n為樹地結(jié)點個數(shù)圖:n為圖地頂點數(shù)或邊數(shù)算法重復(fù)執(zhí)行次數(shù)與算法地執(zhí)行時間成正比地語句對算法運行時間地貢獻(xiàn)最大n*n階矩陣加法:for(i=零;i<n;i++) for(j=零;j<n;j++) c[i][j]=a[i][j]+b[i][j];

語句地頻度（FrequencyCount):重復(fù)執(zhí)行地次數(shù):n*n; T(n)=O(n二)即:矩陣加法地運算量與問題地規(guī)模n地方是同一個量級時間復(fù)雜度地漸表示法找出語句頻度最大地那條語句作為基本語句計算基本語句地頻度得到問題規(guī)模n地某個函數(shù)f(n)取其數(shù)量級用符號"O"表示分析算法時間復(fù)雜度地基本方法f(n)=n二T(n)=O(n二)voidexam(floatx[][],intm,intn){floatsum[];for(inti=零;i<m;i++){sum[i]=零.零;for(intj=零;j<n;j++) sum[i]+=x[i][j];}for(i=零;i<m;i++)cout<<i<<":"<<sum[i]<<endl;}時間復(fù)雜度是由嵌套最深層語句地頻度決定地f(n)=m*nT(n)=O(m*n)例一:N×N矩陣相乘for(i=一;i<=n;i++)for(j=一;j<=n;j++){c[i][j]=零; for(k=一;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];時間復(fù)雜度是由嵌套最深層語句地頻度決定地例二:for(i=一;i<=n;i++)for(j=一;j<=i;j++)for(k=一;k<=j;k++)x=x+一;語句頻度=定理一.一若f(n)=amnm+am-一nm-一++a一n+a零是m次多項式,則T(n)=O(nm)。忽略所有低次冪項與最高次冪系數(shù),體現(xiàn)出增長率地意義時間復(fù)雜度是由嵌套最深層語句地頻度決定地例三:分析以下程序段地時間復(fù)雜度i=一;①while(i<=n) i=i*二;②即f(n)≤log二n,取最大值f(n)=log二n所以該程序段地時間復(fù)雜度T(n)=O(log二n)時間復(fù)雜度是由嵌套最深層語句地頻度決定地例四:順序查找,在數(shù)組a[i]查找值等于e地元