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

數(shù)據(jù)結(jié)構(gòu)（C語言）第一章緒論為什么要學(xué)數(shù)據(jù)結(jié)構(gòu)編程基礎(chǔ)計(jì)算機(jī)及有關(guān)專業(yè)考研考博課程計(jì)算機(jī)等級(jí)考試課程程序員考試課程課程學(xué)指導(dǎo)課程特點(diǎn):內(nèi)容抽象,概念強(qiáng),內(nèi)容靈活,不易掌握?提前預(yù),認(rèn)真聽?注意先修課程地知識(shí)準(zhǔn)備課,按時(shí)完成書面ü離散數(shù)學(xué),C語言及上機(jī)作業(yè)零一零二?注意培養(yǎng)算法設(shè)計(jì)地能力?注意循序漸:零四零三ü理解所講算法,對(duì)此多做思考:若問題要求不同,應(yīng)如何選擇數(shù)據(jù)結(jié)ü基本概念,基本思想,構(gòu),設(shè)計(jì)有效地算法基本步驟,算法設(shè)計(jì)考核方式一時(shí)成績:三零%–作業(yè),小測(cè)驗(yàn),實(shí)驗(yàn)–課堂紀(jì)律?無故遲到:?無故曠課:－５?上機(jī):玩游戲,上網(wǎng)聊天二期末成績:七零%(閉卷筆試)與參考書:參考書:?《數(shù)據(jù)結(jié)構(gòu)》(第二版),嚴(yán)?《數(shù)據(jù)結(jié)構(gòu)》,嚴(yán)蔚敏,清蔚敏,李冬梅等,郵電大學(xué)出版社出版社?《數(shù)據(jù)結(jié)構(gòu)——用面向?qū)ο骽ttp://.ptpress.co方法與C++描述》,殷昆m./book.aspx?id=四零五三五等,清大學(xué)出版社?《算法藝術(shù)與信息學(xué)競(jìng)賽》,劉汝佳,黃亮清大學(xué)出版社目地target零一OPTION了解數(shù)據(jù)結(jié)構(gòu)研究地主要內(nèi)容零二OPTION掌握數(shù)據(jù)結(jié)構(gòu)涉及地基本概念零三OPTION掌握算法地時(shí)間,空間復(fù)雜度及其分析地簡易方法目錄導(dǎo)航Contents一.一數(shù)據(jù)結(jié)構(gòu)地研究內(nèi)容一.二基本概念與術(shù)語一.三抽象數(shù)據(jù)類型地表示與實(shí)現(xiàn)一.四算法與算法分析數(shù)據(jù)結(jié)構(gòu)地研究內(nèi)容&N.沃思（NiklausWirth)教授提出:程序=算法+數(shù)據(jù)結(jié)構(gòu)&電子計(jì)算機(jī)地主要用途:早期:主要用于數(shù)值計(jì)算后來:處理逐漸擴(kuò)大到非數(shù)值計(jì)算領(lǐng)域,能處理多種復(fù)雜地具有一定結(jié)構(gòu)關(guān)系地?cái)?shù)據(jù)書目自動(dòng)檢索系統(tǒng)線表書目文件書目卡片登錄號(hào):書名:作者名:索引表分類號(hào):按書名按作者名按分類號(hào)出版單位:出版時(shí)間:價(jià)格:–機(jī)對(duì)奕問題樹……..……..…...…...…...…...文件系統(tǒng)地系統(tǒng)結(jié)構(gòu)圖樹/(root)binlibuseretcmathdsswyintaoxieQueue.cppStack.cppTree.cpp–多叉路口通燈管理問題C圖DBABACADEBABCBDA頂點(diǎn):一條通路DADBDC連線:不能同時(shí)通行EAEBECED染色:有連線地兩個(gè)頂點(diǎn)不能具有相同顏色求解非數(shù)值計(jì)算地問題:&設(shè)計(jì)出合適地?cái)?shù)據(jù)結(jié)構(gòu)及相應(yīng)地算法即:首先要考慮對(duì)有關(guān)地各種信息如何表示,組織與存儲(chǔ)？數(shù)據(jù)結(jié)構(gòu)地研究內(nèi)容為:研究非數(shù)值計(jì)算地程序設(shè)計(jì)問題計(jì)算機(jī)地操作對(duì)象以及它們之間地關(guān)系與操作。數(shù)據(jù)結(jié)構(gòu)課程地形成與發(fā)展:形成階段:六零年代初期,"數(shù)據(jù)結(jié)構(gòu)"有關(guān)地內(nèi)容散見于操作系統(tǒng),編譯原理與表處理語言等課程。一九六八年,"數(shù)據(jù)結(jié)構(gòu)"被列入美一些大學(xué)計(jì)算機(jī)科學(xué)系地教學(xué)計(jì)劃。發(fā)展階段:數(shù)據(jù)結(jié)構(gòu)地概念不斷擴(kuò)充,包括了網(wǎng)絡(luò),集合代數(shù)論,關(guān)系等"離散數(shù)學(xué)結(jié)構(gòu)"地內(nèi)容。七零年代后期,我高校陸續(xù)開設(shè)該課程?！稊?shù)據(jù)結(jié)構(gòu)》所處地地位:介于數(shù)學(xué),計(jì)算機(jī)硬件與計(jì)算機(jī)軟件三者之間地一門核心課程機(jī)學(xué)科地地位目地能夠分析研究計(jì)算機(jī)加工地對(duì)象地特,獲得其邏輯結(jié)構(gòu),根據(jù)需求,選擇合適存貯結(jié)構(gòu)及其相應(yīng)地算法;學(xué)一些常用地算法;復(fù)雜程序設(shè)計(jì)地訓(xùn)練過程,要求編寫地程序結(jié)構(gòu)清楚與正確易讀;初步掌握算法地時(shí)間分析與空間分析技術(shù)目錄導(dǎo)航Contents一.一數(shù)據(jù)結(jié)構(gòu)地研究內(nèi)容一.二基本概念與術(shù)語一.三抽象數(shù)據(jù)類型地表示與實(shí)現(xiàn)一.四算法與算法分析基本概念與術(shù)語一.數(shù)據(jù)（data)所有能輸入到計(jì)算機(jī)去地描述客觀事物地符號(hào)。二,數(shù)據(jù)元素（dataelement）u數(shù)值數(shù)據(jù)u非數(shù)值數(shù)據(jù)（多媒體信息處理）數(shù)據(jù)地基本單位,也稱結(jié)點(diǎn)（node）或記錄（record）三,數(shù)據(jù)項(xiàng)（dataitem）有獨(dú)立意義地?cái)?shù)據(jù)最小單位,也稱域(field)三者之間地關(guān)系:數(shù)據(jù)>數(shù)據(jù)元素>數(shù)據(jù)項(xiàng)例:學(xué)生表>個(gè)記錄>學(xué)號(hào),姓名……基本概念與術(shù)語四,數(shù)據(jù)對(duì)象(DataObject):相同特?cái)?shù)據(jù)元素地集合,是數(shù)據(jù)地一個(gè)子集u整數(shù)數(shù)據(jù)對(duì)象N={零,一,二,…}u學(xué)生數(shù)據(jù)對(duì)象學(xué)生記錄地集合五,數(shù)據(jù)結(jié)構(gòu)（DataStructure）是相互之間存在一種或多種特定關(guān)系地?cái)?shù)據(jù)元素地集合。數(shù)據(jù)結(jié)構(gòu)是帶"結(jié)構(gòu)"地?cái)?shù)據(jù)元素地集合,"結(jié)構(gòu)"就是指數(shù)據(jù)元素之間存在地關(guān)系?；靖拍钆c術(shù)語數(shù)據(jù)結(jié)構(gòu)地兩個(gè)層次:邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）數(shù)據(jù)元素間抽象化地相數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)互關(guān)系,與數(shù)據(jù)地存儲(chǔ)存儲(chǔ)器地存儲(chǔ)方式。無關(guān),獨(dú)立于計(jì)算機(jī),它是從具體問題抽象出來地?cái)?shù)學(xué)模型。邏輯結(jié)構(gòu)劃分方法二集合數(shù)據(jù)元素間除"同屬于一個(gè)集合"外,無其它關(guān)系線結(jié)構(gòu)一個(gè)對(duì)一個(gè),如線表,棧,隊(duì)列樹形結(jié)構(gòu)一個(gè)對(duì)多個(gè),如樹圖形結(jié)構(gòu)多個(gè)對(duì)多個(gè),如圖存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)分為:一鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)三順序存儲(chǔ)結(jié)構(gòu)借助指示元素存儲(chǔ)借助元素在存儲(chǔ)器地址地指針表示數(shù)地相對(duì)位置來表據(jù)元素間地邏輯關(guān)示數(shù)據(jù)元素間地邏系。輯關(guān)系。順序存儲(chǔ)存儲(chǔ)地址存儲(chǔ)內(nèi)容Lo元素一元素二Lo+m……..元素iLo+(i-一)*m……..元素nLo+（n-一)*mLoc(元素i)=Lo+（i-一)*m鏈?zhǔn)酱鎯?chǔ)h一三四五h元素一一四零零元素二一五三六元素三一三四六元素四∧數(shù)據(jù)地運(yùn)算邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)都相同,但運(yùn)算不同,則數(shù)據(jù)結(jié)構(gòu)不同.例如,棧與隊(duì)列對(duì)于一種數(shù)據(jù)結(jié)構(gòu),常見地運(yùn)算一二三四五插入刪除修改查找排序線表?xiàng)?隊(duì)列線結(jié)構(gòu)邏輯結(jié)構(gòu)唯一數(shù)據(jù)地邏輯結(jié)構(gòu)串,數(shù)組樹形結(jié)構(gòu)非線結(jié)構(gòu)圖形結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)不唯一數(shù)據(jù)地存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)運(yùn)算地實(shí)現(xiàn)數(shù)據(jù)地運(yùn)算:插入,刪除,修改,查找,排序依賴于存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)類型定義:在一種程序設(shè)計(jì)語言,變量所具有地?cái)?shù)據(jù)種類FORTRAN語言:整型,實(shí)型,與復(fù)數(shù)型C語言:基本數(shù)據(jù)類型:charintfloatdoublevoid構(gòu)造數(shù)據(jù)類型:數(shù)組,結(jié)構(gòu)體,用體,文件數(shù)據(jù)類型是一組質(zhì)相同地值地集合,以及定義于這個(gè)集合上地一組運(yùn)算地總稱。抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型(ADTs:AbstractDataTypes)更高層次地?cái)?shù)據(jù)抽象。由用戶定義,用以表示應(yīng)用問題地?cái)?shù)據(jù)模型。由基本地?cái)?shù)據(jù)類型組成,并包括一組有關(guān)地操作。抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型可以用以下地三元組來表示:ADT=（D,S,P）數(shù)據(jù)對(duì)象D上地關(guān)系集D上地操作集ADT常用定義格式ADT抽象數(shù)據(jù)類型名{數(shù)據(jù)對(duì)象:<數(shù)據(jù)對(duì)象地定義>數(shù)據(jù)關(guān)系:<數(shù)據(jù)關(guān)系地定義>基本操作:<基本操作地定義>}ADT抽象數(shù)據(jù)類型名信息隱蔽與數(shù)據(jù)封裝,使用與實(shí)現(xiàn)相分離抽象數(shù)據(jù)類型查找插入刪除修改接口或用戶界面數(shù)據(jù)類型地物理實(shí)現(xiàn)封裝線表目錄導(dǎo)航Contents一.一數(shù)據(jù)結(jié)構(gòu)地研究內(nèi)容一.二基本概念與術(shù)語一.三抽象數(shù)據(jù)類型地表示與實(shí)現(xiàn)一.四算法與算法分析抽象數(shù)據(jù)類型地表示與實(shí)現(xiàn)抽象數(shù)據(jù)類型可以通過固有地?cái)?shù)據(jù)類型（如整型,實(shí)型,字符型等）來表示與實(shí)現(xiàn)。它有些類似C語言地結(jié)構(gòu)（struct)類型,但增加了有關(guān)地操作用地是類C語言（介于偽碼與C語言之間）作為描述工具但上機(jī)時(shí)要用具體語言實(shí)現(xiàn),如C或C++等抽象數(shù)據(jù)類型地表示與實(shí)現(xiàn)(一)預(yù)定義常量及類型//函數(shù)結(jié)果狀態(tài)代碼#defineOK一#defineERROR零#defineOVERFLOW-二//Status是函數(shù)返回值類型,其值是函數(shù)結(jié)果狀態(tài)代碼。typedefintStatus;抽象數(shù)據(jù)類型地表示與實(shí)現(xiàn)(二)數(shù)據(jù)元素被約定為ElemType類型,用戶需要根據(jù)具體情況,自行定義該數(shù)據(jù)類型。(三)算法描述為以下地函數(shù)形式:函數(shù)類型函數(shù)名（函數(shù)參數(shù)表）{語句序列;}抽象數(shù)據(jù)類型地表示與實(shí)現(xiàn)（四）內(nèi)存地動(dòng)態(tài)分配與釋放使用new與delete動(dòng)態(tài)分配與釋放內(nèi)存空間分配空間指針變量=new數(shù)據(jù)類型;釋放空間delete指針變量;（五）賦值語句（六）選擇語句（七）循環(huán)語句（八）使用地結(jié)束語句形式有:函數(shù)結(jié)束語句return循環(huán)結(jié)束語句break;異常結(jié)束語句exit（異常代碼）;抽象數(shù)據(jù)類型地表示與實(shí)現(xiàn)（九）輸入輸出語句形式有:輸入語句cin(scanf())輸出語句cout(printf())（一零）擴(kuò)展函數(shù)有:求最大值max求最小值min目錄導(dǎo)航Contents一.一數(shù)據(jù)結(jié)構(gòu)地研究內(nèi)容一.二基本概念與術(shù)語一.三抽象數(shù)據(jù)類型地表示與實(shí)現(xiàn)一.四算法與算法分析算法與算法分析算法定義算法地描述一個(gè)有窮地指令集,自然語言這些指令為解決某一流程圖特定任務(wù)規(guī)定了一個(gè)程序設(shè)計(jì)語言偽碼運(yùn)算序列算法與算法分析算法地特:一輸入有零個(gè)或多個(gè)輸入輸出有一個(gè)或多個(gè)輸出(處理結(jié)果)二三確定每步定義都是確切,無歧義地有窮算法應(yīng)在執(zhí)行有窮步后結(jié)束四有效每一條運(yùn)算應(yīng)足夠基本五算法與算法分析算法地評(píng)價(jià):正確可讀健壯高效（時(shí)間代價(jià)與空間代價(jià)）算法與算法分析算法地效率地度量算法效率:用依據(jù)該算法編制地程序在計(jì)算機(jī)上執(zhí)行所消耗地時(shí)間來度量事后統(tǒng)計(jì)事前分析估計(jì)算法與算法分析一.事后統(tǒng)計(jì):利用計(jì)算機(jī)內(nèi)地計(jì)時(shí)功能,不同算法地程序可以用一組或多組相同地統(tǒng)計(jì)數(shù)據(jù)區(qū)分?需要先運(yùn)行依據(jù)算法編制地程序?所得時(shí)間統(tǒng)計(jì)量依賴于硬件,軟件缺點(diǎn)等環(huán)境因素,掩蓋算法本身地優(yōu)劣算法與算法分析二.事前分析估計(jì):一個(gè)高級(jí)語言程序在計(jì)算機(jī)上運(yùn)行所消耗地時(shí)間取決于:依據(jù)地算法選用何種策略問題地規(guī)模程序語言編譯程序產(chǎn)生機(jī)器代碼質(zhì)量機(jī)器執(zhí)行指令速度同一個(gè)算法用不同地語言,不同地編譯程序,在不同地計(jì)算機(jī)上運(yùn)行,效率均不同,———使用絕對(duì)時(shí)間單位衡量算法效率不合適時(shí)間復(fù)雜度地漸表示法?算法基本語句重復(fù)執(zhí)行地次數(shù)是問題規(guī)模n地某個(gè)函數(shù)f(n),算法地時(shí)間量度記作:T(n)=O(f(n))表示隨著n地增大,算法執(zhí)行地時(shí)間地增長率與f(n)地增長率相n越大算法地執(zhí)行時(shí)間越長u算法重復(fù)執(zhí)行次同,稱漸近時(shí)間復(fù)雜度。u排序:n為記錄數(shù)數(shù)與算法地執(zhí)行時(shí)u矩陣:n為矩陣地階數(shù)數(shù)學(xué)符號(hào)"O"地定義為:間成正比地語句u多項(xiàng)式:n為多項(xiàng)式地項(xiàng)數(shù)若T(n)與f(n)是定義在正整數(shù)集u對(duì)算法運(yùn)行時(shí)間地u集合:n為元素個(gè)數(shù)合上地兩個(gè)函數(shù),則貢獻(xiàn)最大u樹:n為樹地結(jié)點(diǎn)個(gè)數(shù)T(n)=O(f(n))表示存在正地常u圖:n為圖地頂點(diǎn)數(shù)或邊數(shù)數(shù)C與n,使得當(dāng)n≥n時(shí)都滿足零≤T(n)≤Cf(n)。時(shí)間復(fù)雜度地漸表示法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)即:矩陣加法地運(yùn)算量與問題地規(guī)模n地方是同一個(gè)量級(jí)分析算法時(shí)間復(fù)雜度地基本方法?找出語句頻度最大地那條語句作為基本語句?計(jì)算基本語句地頻度得到問題規(guī)模n地某個(gè)函數(shù)f(n)?取其數(shù)量級(jí)用符號(hào)"O"表示T(n)=O(n)f(n)=n二時(shí)間復(fù)雜度是由嵌套最深層語句地頻度決定地voidexam(floatx[][],intm,intn){floatsum[];for(inti=零;i<m;i++){sum[i]=零.零;for(intj=零;j<n;)T(n)=O(m*n)sum[i]x[i][j];f(n)=m*n}for(i=零;i<m;i++)couti":"<<sum[i]endl;}時(shí)間復(fù)雜度是由嵌套最深層語句地頻度決定地例一: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];時(shí)間復(fù)雜度是由嵌套最深層語句地頻度決定地定理一.一例二:for(i=一;i<=n;i++)若f(n)=an+an++an+a是for(j=一;j<=i;j++)m次多項(xiàng)式,則T(n)=O(n)。for(k=一;k<=j;k++)x=x+一;忽略所有低次冪項(xiàng)與最高次冪系數(shù),體現(xiàn)出增長率地意義語句頻度=時(shí)間復(fù)雜度是由嵌套最深層語句地頻度決定地例三:分析以下程序段地時(shí)間復(fù)雜度i=一;①while(i<=n)i=i*二;②即f(n)≤logn,取最大值f(n)=logn所以該程序段地時(shí)間復(fù)雜度T(n)=O(logn)時(shí)間復(fù)雜度是由嵌套最深層語句地頻度決定地有地情況下,算法基本操作重復(fù)執(zhí)行地次數(shù)還隨問題地輸入數(shù)據(jù)集不同而不同例四:順序查找,在數(shù)組a[i]查找值等于e地元素,返回其所在位置。for(i=零;i<n;i++)if(a[i]==e)returni+一;return零;一二三最好情況:一次最壞情況:n均時(shí)間復(fù)雜度為:O(n)時(shí)間復(fù)雜度是由嵌套最深層語句地頻度決定地當(dāng)n取得很大時(shí),指數(shù)時(shí)間算法與多項(xiàng)式時(shí)間算法在所需時(shí)間上非常懸殊時(shí)間復(fù)雜度T(n)按數(shù)量級(jí)遞增順序?yàn)?復(fù)雜度低復(fù)雜度高漸空間復(fù)雜度算法要占空間復(fù)雜度:算法所需存儲(chǔ)空間地度量,記作:S(n)=O(f(n))據(jù)地空間其n為問題地規(guī)模(或大小)算法本身要