寧夏大學(xué)國(guó)家稅收緒論課件

1、寧夏大學(xué)國(guó)家稅收緒論寧夏大學(xué)國(guó)家稅收緒論1教學(xué)輔助課件教學(xué)輔助課件主講人：牛三勇主講人：牛三勇寧夏大學(xué)寧夏大學(xué) 經(jīng)濟(jì)管理學(xué)院經(jīng)濟(jì)管理學(xué)院 工商管理系工商管理系寧夏大學(xué)國(guó)家稅收緒論寧夏大學(xué)國(guó)家稅收緒論2第一章第一章緒緒 論論工商管理系工商管理系 牛三勇牛三勇寧夏大學(xué)國(guó)家稅收緒論寧夏大學(xué)國(guó)家稅收緒論3第一節(jié)第一節(jié) 什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu)n例例 學(xué)生信息表格學(xué)生信息表格線性結(jié)構(gòu)線性結(jié)構(gòu) 學(xué)學(xué) 號(hào)號(hào) 姓姓 名名 性性別別 籍籍 貫貫 出出生生年年月月 1 98131 劉劉激激揚(yáng)揚(yáng) 男男 北北 京京 1979.12 2 98164 衣衣春春生生 男男 青青 島島 1979.07 3 98165 盧

2、盧聲聲凱凱 男男 天天 津津 1981.02 4 98182 袁袁秋秋慧慧 女女 廣廣 州州 1980.10 5 98224 洪洪 偉偉 男男 太太 原原 1981.01 6 98236 熊熊南南燕燕 女女 蘇蘇 州州 1980.03 7 98297 宮宮 力力 男男 北北 京京 1981.01 8 98310 蔡蔡曉曉莉莉 女女 昆昆 明明 1981.02 9 98318 陳陳 健健 男男 杭杭 州州 1979.12工商管理系工商管理系 牛三勇牛三勇寧夏大學(xué)國(guó)家稅收緒論寧夏大學(xué)國(guó)家稅收緒論4n例例 對(duì)弈樹(shù)對(duì)弈樹(shù)-樹(shù)型結(jié)構(gòu)樹(shù)型結(jié)構(gòu)工商管理系工商管理系 牛三勇牛三勇寧夏大學(xué)國(guó)家稅收緒論寧夏大學(xué)國(guó)

3、家稅收緒論5n數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象以及它們之間的關(guān)系和操作等的學(xué)科對(duì)象以及它們之間的關(guān)系和操作等的學(xué)科工商管理系工商管理系 牛三勇牛三勇寧夏大學(xué)國(guó)家稅收緒論寧夏大學(xué)國(guó)家稅收緒論6第二節(jié)第二節(jié) 基本概念和術(shù)語(yǔ)基本概念和術(shù)語(yǔ)n數(shù)據(jù)數(shù)據(jù)(data)數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入數(shù)據(jù)是信息的載體，是描述客觀事物的數(shù)、字符、以及所有能輸入到計(jì)算機(jī)中，被計(jì)算機(jī)程序識(shí)別和處理的符號(hào)的集合。到計(jì)算機(jī)中，被計(jì)算機(jī)程序識(shí)別和處理的符號(hào)的集合。n數(shù)據(jù)元素?cái)?shù)據(jù)元素(data element) 數(shù)

4、據(jù)的數(shù)據(jù)的基本單位基本單位。在計(jì)算機(jī)程序中常作為一個(gè)整體進(jìn)行考慮和處理。在計(jì)算機(jī)程序中常作為一個(gè)整體進(jìn)行考慮和處理。n有時(shí)一個(gè)數(shù)據(jù)元素可以由若干有時(shí)一個(gè)數(shù)據(jù)元素可以由若干數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)(Data Item)組成。組成。數(shù)據(jù)數(shù)據(jù)項(xiàng)項(xiàng)是是具有獨(dú)立含義的最小標(biāo)識(shí)單位具有獨(dú)立含義的最小標(biāo)識(shí)單位。n數(shù)據(jù)元素又稱(chēng)為元素、結(jié)點(diǎn)、記錄。數(shù)據(jù)元素又稱(chēng)為元素、結(jié)點(diǎn)、記錄。數(shù)據(jù)對(duì)象數(shù)據(jù)對(duì)象(data object)數(shù)據(jù)對(duì)象是具有相同性質(zhì)的數(shù)據(jù)元素的集合。數(shù)據(jù)對(duì)象是具有相同性質(zhì)的數(shù)據(jù)元素的集合。 例如整數(shù)數(shù)據(jù)對(duì)象、學(xué)生數(shù)據(jù)對(duì)象。例如整數(shù)數(shù)據(jù)對(duì)象、學(xué)生數(shù)據(jù)對(duì)象。工商管理系工商管理系 牛三勇牛三勇寧夏大學(xué)國(guó)家稅收緒論寧夏大

5、學(xué)國(guó)家稅收緒論7n數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(data structure)指某一數(shù)據(jù)對(duì)象的所有數(shù)據(jù)成員之間的關(guān)系。指某一數(shù)據(jù)對(duì)象的所有數(shù)據(jù)成員之間的關(guān)系。記為：記為： Data_Structure = D, R 其中，其中，D 是某一數(shù)據(jù)對(duì)象，是某一數(shù)據(jù)對(duì)象，R 是該對(duì)象中所有數(shù)據(jù)成員之間的關(guān)是該對(duì)象中所有數(shù)據(jù)成員之間的關(guān)系的有限集合。系的有限集合。四類(lèi)基本數(shù)據(jù)結(jié)構(gòu)：四類(lèi)基本數(shù)據(jù)結(jié)構(gòu)：n集合：結(jié)構(gòu)中的數(shù)據(jù)元素之間除了同性于一個(gè)集合的關(guān)系外，別集合：結(jié)構(gòu)中的數(shù)據(jù)元素之間除了同性于一個(gè)集合的關(guān)系外，別無(wú)其他關(guān)系。無(wú)其他關(guān)系。n線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在一個(gè)對(duì)一個(gè)的關(guān)系。線性結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之

6、間存在一個(gè)對(duì)一個(gè)的關(guān)系。集合關(guān)系圖集合關(guān)系圖線性關(guān)系圖線性關(guān)系圖工商管理系工商管理系 牛三勇牛三勇寧夏大學(xué)國(guó)家稅收緒論寧夏大學(xué)國(guó)家稅收緒論8n樹(shù)形結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素存在一個(gè)對(duì)多個(gè)的關(guān)系。樹(shù)形結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素存在一個(gè)對(duì)多個(gè)的關(guān)系。n圖狀結(jié)構(gòu)或網(wǎng)關(guān)結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多個(gè)對(duì)多個(gè)的圖狀結(jié)構(gòu)或網(wǎng)關(guān)結(jié)構(gòu)：結(jié)構(gòu)中的數(shù)據(jù)元素之間存在多個(gè)對(duì)多個(gè)的關(guān)系。關(guān)系。樹(shù)形關(guān)系圖樹(shù)形關(guān)系圖圖狀關(guān)系圖圖狀關(guān)系圖工商管理系工商管理系 牛三勇牛三勇寧夏大學(xué)國(guó)家稅收緒論寧夏大學(xué)國(guó)家稅收緒論9例：樹(shù)形結(jié)構(gòu)的數(shù)學(xué)模型例：樹(shù)形結(jié)構(gòu)的數(shù)學(xué)模型可以定義如下數(shù)據(jù)結(jié)構(gòu)：可以定義如下數(shù)據(jù)結(jié)構(gòu)：Tree=(P,R)其中：其中：

7、P=F1,Z1,Z2,S1,S2,S3 R=R1,R2 R1= R2=F1S3Z2Z1S2S1數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是數(shù)據(jù)的是數(shù)據(jù)的組織形式組織形式n數(shù)據(jù)元素間的數(shù)據(jù)元素間的邏輯關(guān)系邏輯關(guān)系，即數(shù)據(jù)的，即數(shù)據(jù)的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)；n數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)內(nèi)的表示，即數(shù)據(jù)的數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)內(nèi)的表示，即數(shù)據(jù)的存存儲(chǔ)表示儲(chǔ)表示；n數(shù)據(jù)的運(yùn)算，即對(duì)數(shù)據(jù)元素施加的數(shù)據(jù)的運(yùn)算，即對(duì)數(shù)據(jù)元素施加的操作操作。工商管理系工商管理系 牛三勇牛三勇寧夏大學(xué)國(guó)家稅收緒論寧夏大學(xué)國(guó)家稅收緒論10數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)n數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)從邏輯關(guān)系上描述數(shù)據(jù)從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)

8、與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)；n數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問(wèn)題抽象出來(lái)的數(shù)據(jù)模型從具體問(wèn)題抽象出來(lái)的數(shù)據(jù)模型；n數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的形式、內(nèi)容無(wú)關(guān)與數(shù)據(jù)元素本身的形式、內(nèi)容無(wú)關(guān)；n數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素的相對(duì)位置無(wú)關(guān)數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素的相對(duì)位置無(wú)關(guān)n數(shù)據(jù)的邏輯結(jié)構(gòu)分類(lèi)數(shù)據(jù)的邏輯結(jié)構(gòu)分類(lèi)n線性結(jié)構(gòu)線性結(jié)構(gòu)u 線性表線性表n非線性結(jié)構(gòu)非線性結(jié)構(gòu)u 樹(shù)樹(shù)u 圖（或網(wǎng)絡(luò)）圖（或網(wǎng)絡(luò)）工商管理系工商管理系 牛三勇牛三勇寧夏大學(xué)國(guó)家稅收緒論寧夏大學(xué)國(guó)家稅收緒論11數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)n數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)用計(jì)算機(jī)語(yǔ)言的實(shí)現(xiàn)；數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)

9、構(gòu)用計(jì)算機(jī)語(yǔ)言的實(shí)現(xiàn)；n數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)依賴于計(jì)算機(jī)語(yǔ)言。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)依賴于計(jì)算機(jī)語(yǔ)言。u 順序存儲(chǔ)表示順序存儲(chǔ)表示u 鏈接存儲(chǔ)表示鏈接存儲(chǔ)表示u 索引存儲(chǔ)表示索引存儲(chǔ)表示u 散列存儲(chǔ)表示散列存儲(chǔ)表示工商管理系工商管理系 牛三勇牛三勇寧夏大學(xué)國(guó)家稅收緒論寧夏大學(xué)國(guó)家稅收緒論12抽象數(shù)據(jù)類(lèi)型抽象數(shù)據(jù)類(lèi)型n數(shù)據(jù)類(lèi)型數(shù)據(jù)類(lèi)型 定義：定義：一組性質(zhì)相同的值的集合一組性質(zhì)相同的值的集合, 以及定義于這個(gè)值集合上的一以及定義于這個(gè)值集合上的一組操作的總稱(chēng)組操作的總稱(chēng).nC語(yǔ)言中的基本數(shù)據(jù)類(lèi)型語(yǔ)言中的基本數(shù)據(jù)類(lèi)型 char int float double voidn構(gòu)造數(shù)據(jù)類(lèi)型由構(gòu)造數(shù)據(jù)類(lèi)型由基本數(shù)據(jù)類(lèi)型

10、基本數(shù)據(jù)類(lèi)型或或構(gòu)造數(shù)據(jù)類(lèi)型構(gòu)造數(shù)據(jù)類(lèi)型組成。組成。n構(gòu)造數(shù)據(jù)類(lèi)型由構(gòu)造數(shù)據(jù)類(lèi)型由不同成分類(lèi)型不同成分類(lèi)型構(gòu)成。構(gòu)成。n基本數(shù)據(jù)類(lèi)型可以看作是基本數(shù)據(jù)類(lèi)型可以看作是計(jì)算機(jī)中已實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)計(jì)算機(jī)中已實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)。n數(shù)據(jù)類(lèi)型就是數(shù)據(jù)結(jié)構(gòu)，不過(guò)它是從編程者的角度來(lái)使用的。數(shù)據(jù)類(lèi)型就是數(shù)據(jù)結(jié)構(gòu)，不過(guò)它是從編程者的角度來(lái)使用的。n數(shù)據(jù)類(lèi)型是模板，必須定義屬于某種數(shù)據(jù)類(lèi)型的變量，才能參加數(shù)據(jù)類(lèi)型是模板，必須定義屬于某種數(shù)據(jù)類(lèi)型的變量，才能參加運(yùn)算。運(yùn)算。工商管理系工商管理系 牛三勇牛三勇寧夏大學(xué)國(guó)家稅收緒論寧夏大學(xué)國(guó)家稅收緒論13抽象數(shù)據(jù)類(lèi)型抽象數(shù)據(jù)類(lèi)型u由用戶定義，用以表示應(yīng)用問(wèn)題的由用戶定義，用以

11、表示應(yīng)用問(wèn)題的數(shù)據(jù)模型數(shù)據(jù)模型u由由基本的數(shù)據(jù)類(lèi)型基本的數(shù)據(jù)類(lèi)型組成組成, 并包括并包括一組相關(guān)的服務(wù)一組相關(guān)的服務(wù)（或稱(chēng)操作）（或稱(chēng)操作）u信息隱蔽信息隱蔽和和數(shù)據(jù)封裝數(shù)據(jù)封裝，使用與實(shí)現(xiàn)相分離，使用與實(shí)現(xiàn)相分離工商管理系工商管理系 牛三勇牛三勇寧夏大學(xué)國(guó)家稅收緒論寧夏大學(xué)國(guó)家稅收緒論14第四節(jié)第四節(jié) 算法和算法分析算法和算法分析n定義：定義：是對(duì)特定問(wèn)題求解步驟的一種描述，它是指令的有限序列，是對(duì)特定問(wèn)題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。其中每一條指令表示一個(gè)或多個(gè)操作。n特性：特性：u 輸入輸入 有有0個(gè)或多個(gè)輸入個(gè)或多個(gè)輸入u 輸出輸出 有一個(gè)或

12、多個(gè)輸出有一個(gè)或多個(gè)輸出(處理結(jié)果處理結(jié)果)u 確定性確定性 每步定義都是確切、無(wú)歧義的每步定義都是確切、無(wú)歧義的u 有窮性有窮性 算法應(yīng)在執(zhí)行有窮步后結(jié)束算法應(yīng)在執(zhí)行有窮步后結(jié)束u 有效性有效性 每一條運(yùn)算應(yīng)足夠基本每一條運(yùn)算應(yīng)足夠基本要求：要求：u正確性正確性 應(yīng)當(dāng)滿足具體問(wèn)題的需求應(yīng)當(dāng)滿足具體問(wèn)題的需求u可讀性可讀性 方便閱讀與交流方便閱讀與交流u健壯性健壯性 對(duì)于正確或錯(cuò)誤的數(shù)據(jù)應(yīng)具判斷能力對(duì)于正確或錯(cuò)誤的數(shù)據(jù)應(yīng)具判斷能力u效率與低存儲(chǔ)量需求效率與低存儲(chǔ)量需求 要達(dá)到高效低空間占用要達(dá)到高效低空間占用工商管理系工商管理系 牛三勇牛三勇寧夏大學(xué)國(guó)家稅收緒論寧夏大學(xué)國(guó)家稅收緒論15算法效率

13、的度量算法效率的度量n事后統(tǒng)計(jì)的方法事后統(tǒng)計(jì)的方法n事前分析估算的方法事前分析估算的方法u空間復(fù)雜度空間復(fù)雜度u時(shí)間復(fù)雜度時(shí)間復(fù)雜度u時(shí)間復(fù)雜度時(shí)間復(fù)雜度n運(yùn)行時(shí)間運(yùn)行時(shí)間 = 算法中每條語(yǔ)句執(zhí)行時(shí)間之和。算法中每條語(yǔ)句執(zhí)行時(shí)間之和。n每條語(yǔ)句執(zhí)行時(shí)間每條語(yǔ)句執(zhí)行時(shí)間 = 該語(yǔ)句的執(zhí)行次數(shù)（頻度）該語(yǔ)句的執(zhí)行次數(shù)（頻度）* 語(yǔ)句執(zhí)行一次語(yǔ)句執(zhí)行一次所需時(shí)間。所需時(shí)間。n語(yǔ)句執(zhí)行一次所需時(shí)間取決于語(yǔ)句執(zhí)行一次所需時(shí)間取決于機(jī)器的指令性能和速度機(jī)器的指令性能和速度和和編譯所產(chǎn)編譯所產(chǎn)生的代碼質(zhì)量生的代碼質(zhì)量，很難確定。很難確定。n設(shè)每條語(yǔ)句執(zhí)行一次所需時(shí)間為單位時(shí)間，則一個(gè)算法的運(yùn)行時(shí)設(shè)每條語(yǔ)句執(zhí)

14、行一次所需時(shí)間為單位時(shí)間，則一個(gè)算法的運(yùn)行時(shí)間就是該算法中所有語(yǔ)句的頻度之和。間就是該算法中所有語(yǔ)句的頻度之和。工商管理系工商管理系 牛三勇牛三勇寧夏大學(xué)國(guó)家稅收緒論寧夏大學(xué)國(guó)家稅收緒論16例：例：求兩個(gè)求兩個(gè)n階方陣的乘積階方陣的乘積C = A Bvoid MatrixMultiply ( int Ann, int Bnn, int Cnn ) for ( int i = 0; i n; i+ ) n for ( int j = 0; j n; j+ ) n Cij = 0; n2 for ( int k = 0; k n; k+ ) n2 Cij = Cij + Aik * Bkj; n3

15、 + n3 + 2n2 + 2n 工商管理系工商管理系 牛三勇牛三勇寧夏大學(xué)國(guó)家稅收緒論寧夏大學(xué)國(guó)家稅收緒論17n算法中所有語(yǔ)句的頻度之和是算法中所有語(yǔ)句的頻度之和是矩陣階數(shù)矩陣階數(shù)n的函數(shù)的函數(shù) T(n) = n3 + 2n2 + 2n n一般地，稱(chēng)一般地，稱(chēng) n 是問(wèn)題的規(guī)模。則時(shí)間復(fù)雜度是問(wèn)題的規(guī)模。則時(shí)間復(fù)雜度 T(n) 是問(wèn)題規(guī)模是問(wèn)題規(guī)模 n 的函數(shù)。的函數(shù)。n當(dāng)當(dāng)n趨于無(wú)窮大時(shí)，把時(shí)間復(fù)雜度的數(shù)量級(jí)（階）稱(chēng)為算法的漸趨于無(wú)窮大時(shí)，把時(shí)間復(fù)雜度的數(shù)量級(jí)（階）稱(chēng)為算法的漸進(jìn)時(shí)間復(fù)雜度進(jìn)時(shí)間復(fù)雜度 T(n) = O(n3)n漸進(jìn)時(shí)間復(fù)雜度漸進(jìn)時(shí)間復(fù)雜度n大大O表示法表示法n加法規(guī)則加法

16、規(guī)則 （主要（主要針對(duì)順序程序段針對(duì)順序程序段 ） T(n, m) = T1 (n) + T2 (m) = O(max (f (n), g (m)c log2n n nlog2n n2 n3 2n 3n n!工商管理系工商管理系 牛三勇牛三勇寧夏大學(xué)國(guó)家稅收緒論寧夏大學(xué)國(guó)家稅收緒論18變量計(jì)數(shù)變量計(jì)數(shù)x = 0; y = 0;for ( int k = 0; k n; k + ) x +;for ( int i = 0; i n; i+ ) for ( int j = 0; j n; j+ ) y +;T1(n) = O(1)T2(n) = O(n)T3(n) = O(n2)T(n) = T1(n)+T2(n)+T3(n) = O( max( 1, n, n2 ) ) = O(n2)例：求漸近時(shí)間復(fù)雜度例：求漸近時(shí)間復(fù)雜度工商管理系工商管理系 牛三勇牛三勇寧夏大學(xué)國(guó)家稅收緒論寧夏大學(xué)國(guó)家稅收緒論19n乘法規(guī)則乘法規(guī)則 （主要（主要針對(duì)嵌套程序段針對(duì)嵌套程序段 ）則漸進(jìn)時(shí)間復(fù)雜度為：則漸進(jìn)時(shí)間復(fù)雜度為：T(n)=Ti(n)*Tj(k)=O(n)*O(k)for ( int i = 1; i = n; i+ ) for ( int j = 1; j =k; j+ ) y +;工商管理系工商管理系 牛三