資源描述：
《最新數(shù)據(jù)結(jié)構(gòu)緒論教學(xué)講義PPT課件.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、數(shù)據(jù)結(jié)構(gòu)緒論主要教學(xué)內(nèi)容：1.1本課程的研究對象；1.2數(shù)據(jù)結(jié)構(gòu)的有關(guān)基本概念；1.3數(shù)據(jù)結(jié)構(gòu)的分類及表示；1.4算法及算法分析（算法評價(jià)）1.1本課程研究的問題?計(jì)算機(jī)的發(fā)展軟件硬件應(yīng)用領(lǐng)域?數(shù)據(jù)處理的種類和能力?數(shù)據(jù)數(shù)值數(shù)據(jù)非數(shù)值數(shù)據(jù)數(shù)(整數(shù),實(shí)數(shù))字符字符串文字圖形圖象聲音數(shù)據(jù)：客觀對象的符號(hào)表示數(shù)學(xué)中的整數(shù)、實(shí)數(shù)， 課程名，地名、書名程序原始數(shù)據(jù)結(jié)果數(shù)據(jù)城市間交通網(wǎng)問題1.1本課程研究的問題數(shù)據(jù)結(jié)構(gòu)的研究問題：非數(shù)值數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系，及如何表示，如何存儲(chǔ)，如何處理。本課程討論的問題：應(yīng)用中常用的幾種數(shù)據(jù)間的結(jié)構(gòu)關(guān)系，及如何表示,如何存儲(chǔ)，如何處理。1．2數(shù)據(jù)結(jié)構(gòu)的有關(guān)概念數(shù)據(jù)：客觀對
2、象的符號(hào)表示。例如：學(xué)號(hào)，姓名，班名都是數(shù)據(jù)。數(shù)據(jù)元素：數(shù)據(jù)的基本單位。相當(dāng)于“記錄”,在計(jì)算機(jī)程序中通常作為一個(gè)整體考慮和處理數(shù)據(jù)項(xiàng):相當(dāng)于記錄的“域”,是數(shù)據(jù)的不可分割的最小單位,如學(xué)號(hào)數(shù)據(jù)對象：性質(zhì)相同的數(shù)據(jù)元素的集合.例如:所有班名相同的記錄集合數(shù)據(jù)結(jié)構(gòu)：是相互間存在關(guān)系的數(shù)據(jù)元素集合。1.2數(shù)據(jù)結(jié)構(gòu)的有關(guān)概念對每種數(shù)據(jù)結(jié)構(gòu)，主要討論如下兩方面的問題：1）數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)的基本操作； 2）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)基本操作的實(shí)現(xiàn)；數(shù)據(jù)的邏輯結(jié)構(gòu)：數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系，是具體關(guān)系的抽象。1．2數(shù)據(jù)結(jié)構(gòu)的有關(guān)概念數(shù)據(jù)結(jié)構(gòu)的基本操作：指對數(shù)據(jù)結(jié)構(gòu)的加工處理數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)(物理結(jié)構(gòu))：數(shù)據(jù)
3、結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示數(shù)據(jù)結(jié)構(gòu)基本操作的實(shí)現(xiàn)：基本操作在計(jì)算機(jī)上的實(shí)現(xiàn)（方法)某班學(xué)生基本情況登記表，記錄了每個(gè)學(xué)生的學(xué)號(hào)姓名專業(yè)政治面貌，表中的記錄是按學(xué)生的學(xué)號(hào)順序排列的。學(xué)號(hào)姓名專業(yè)政治面藐 001王洪計(jì)算機(jī)黨員 002孫文計(jì)算機(jī)團(tuán)員 003謝軍計(jì)算機(jī)團(tuán)員 004李輝計(jì)算機(jī)團(tuán)員 005沈祥福計(jì)算機(jī)黨員006余斌計(jì)算機(jī)團(tuán)員 007鞏力計(jì)算機(jī)團(tuán)員 008孔令輝計(jì)算機(jī)團(tuán)員學(xué)生基本情況登記表的圖示001003002004006005008007學(xué)生間學(xué)號(hào)順序關(guān)系是一種線性結(jié)構(gòu)關(guān)系例一常用的數(shù)據(jù)結(jié)構(gòu)1）集合 2）線性結(jié)構(gòu) 3）樹結(jié)構(gòu) 4）圖結(jié)構(gòu)5）其它復(fù)雜結(jié)構(gòu)1.3數(shù)據(jù)結(jié)構(gòu)的分類及表示家族的族譜
4、 假設(shè)某家族有10個(gè)成員A，B，C，D，E，F(xiàn)，G，H，I，J，他們之間的血緣關(guān)系可以用如下圖表示。JIACBDHGFE1．3數(shù)據(jù)結(jié)構(gòu)的分類及表示例數(shù)據(jù)結(jié)構(gòu)的表示圖示表示圖示表示是由頂點(diǎn)和邊構(gòu)成的圖，其中頂點(diǎn)表示數(shù)據(jù)，邊表示數(shù)據(jù)之間的結(jié)構(gòu)關(guān)系；001003002004006005008007學(xué)生基本情況表的圖示表示JIACBDHGFE家族樹的圖示表示1．3數(shù)據(jù)結(jié)構(gòu)的分類及表示學(xué)生基本情況表的二元組表示（D，S）二元組表示二元組表示是用一個(gè)二元組（D，S）表示數(shù)據(jù)結(jié)構(gòu)，其中D是數(shù)據(jù)元素集合，S是D上關(guān)系的集合。D={001，002，003，004，005，006，007，008}S={R}R={
5、<001,002>,<002,003>,<003,004>,<004,005>,<005,006>,<006,007>,<007,008>}家族樹的二元組表示（D，S）D={A，B，C，D，E，F(xiàn)，G，H，I，J} S={R} R={〈A,B>,,,,,,,,}1．3數(shù)據(jù)結(jié)構(gòu)的分類及表示JIACBDHGFE0010030020040060050080071．4算法與算法分析1.4算法與算法分析一算法的概念算法是求解問題的操作序列算法的基本特征： 1）輸入：0個(gè)或多個(gè)輸入； 2）輸出：1個(gè)或多個(gè)輸出； 3）有窮性：算
6、法必須在有限步內(nèi)結(jié)束； 4）確定性：組成算法的操作必須清晰無二義性。 5）可行性：組成算法的操作必須能夠在計(jì)算機(jī)上實(shí)現(xiàn)。求兩個(gè)正整數(shù)m，n中的最大數(shù)MAX的算法（1）若m>n則max=m （2）若m<=n則max=n例描述算法的書寫規(guī)則所有算法均以函數(shù)形式給出,算法的輸入數(shù)據(jù)來自參數(shù)表參數(shù)表的參數(shù)在算法之前均進(jìn)行類型說明有關(guān)結(jié)點(diǎn)結(jié)構(gòu)的類型定義,以及全局變量的說明等均在算法之前進(jìn)行說明評價(jià)算法標(biāo)準(zhǔn)算法的正確性，可讀性，可維護(hù)性，健壯性等，1算法時(shí)間復(fù)雜度T（n）本課程采用以求解問題的基本操作（原操作）的執(zhí)行次數(shù)作為算法時(shí)間的度量。1．4算法與算法分析O（n3）稱為矩陣相乘算法時(shí)間復(fù)雜度；O（n3
7、）表示矩陣相乘算法執(zhí)行時(shí)間與n3成正比,即O（n3）與n3同一數(shù)量級(jí)；n階矩陣相乘的算法For(i=1;i<=n;i++) For(j=1;j<=n;j++){c[i][j]=0; For(k=1;k<=n;k++) c[i][j]+=a[i][k]*b[k][j]}乘法加法執(zhí)行次數(shù)均為n3例矩陣相乘的基本運(yùn)算：乘法加法；有些算法，基本操作執(zhí)行次數(shù)與問題的輸入數(shù)據(jù)有關(guān)，這時(shí)可考慮 （1）算法平均時(shí)
