數(shù)據(jù)結(jié)構(gòu)-使用C語言講稿ch1

1、第一章 緒論1.1 數(shù)據(jù)結(jié)構(gòu)的基本概念 1.2 抽象數(shù)據(jù)類型和軟件構(gòu)造方法 1.3 算法和算法的時(shí)間復(fù)雜度 1.4 算法書寫規(guī)范1.1 數(shù)據(jù)結(jié)構(gòu)的基本概念一.學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義1. 算法和數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)科學(xué)的兩大支柱計(jì)算機(jī)科學(xué)早期定義為: 研究算法的科學(xué)近期定義為: 研究數(shù)據(jù)的科學(xué)2. 數(shù)據(jù)結(jié)構(gòu)是程序設(shè)計(jì)的基礎(chǔ)Program=Algorithms+Data Structure數(shù)據(jù)結(jié)構(gòu)是設(shè)計(jì)OS、DBMS、編譯等系統(tǒng)程序和 各種應(yīng)用程序的重要基礎(chǔ)3. 是計(jì)算機(jī)專業(yè)的一門綜合性專業(yè)基礎(chǔ)課是計(jì)算機(jī)專業(yè)本科生必修學(xué)位課程是計(jì)算機(jī)研究生入學(xué)考試必考科目是軟件人員水平考試內(nèi)容二.學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的要求1.

2、掌握各類基本數(shù)據(jù)結(jié)構(gòu)類型和相應(yīng)的存儲(chǔ)結(jié)構(gòu)2. 提高閱讀和編寫算法的能力3. 能針對(duì)給定問題，選擇相適應(yīng)的數(shù)據(jù)結(jié)構(gòu)，并能設(shè)計(jì)和分析算法三、 數(shù)據(jù)結(jié)構(gòu)的主要內(nèi)容98080-3 班號(hào) 2321527-8009 理學(xué)院辦公室電話號(hào)碼313000 湖州師范學(xué)院郵編320102780618748 身份證號(hào)碼 例1：98080-33202670610054510102780618748結(jié)論1.雜亂的數(shù)據(jù)不能表達(dá)和交流信息三、 數(shù)據(jù)結(jié)構(gòu)的主要內(nèi)容例2: 電話號(hào)碼簿 (a1，b1) (a2，b2)(an，bn)其中： ai為某人姓名，bi為該人的電話號(hào)碼。要求：設(shè)計(jì)一個(gè)算法，給定一個(gè)姓名時(shí)，能查出此人的電話號(hào)碼

3、。 如果姓名和電話號(hào)碼的排列次序無規(guī)律， 則只能逐一比較姓名進(jìn)行查找 如果姓名按字典順序組織，則查找就快捷多了結(jié)論2.數(shù)據(jù)之間是有聯(lián)系的這些聯(lián)系常常影響算法的選擇和效率。 DS就是要研究數(shù)據(jù)之間的聯(lián)系。三、 數(shù)據(jù)結(jié)構(gòu)的主要內(nèi)容(續(xù))例3：大學(xué)學(xué)生管理機(jī)構(gòu)學(xué)校一系八系一年級(jí)二年級(jí)三年級(jí)四年級(jí)班班張三李四結(jié)論數(shù)據(jù)之間是有結(jié)構(gòu)的例中數(shù)據(jù)之間呈分層結(jié)構(gòu)（樹狀結(jié)構(gòu)）DS就是要研究數(shù)據(jù)之間的各類結(jié)構(gòu)。三、 數(shù)據(jù)結(jié)構(gòu)的主要內(nèi)容(續(xù))例：圖書目錄管理設(shè)每個(gè)書目含：書名，作者，登錄號(hào)，分類，出版年月對(duì)圖書目錄常有如下操作：查找：某書在書庫中是否存在？插入：購進(jìn)新書時(shí)的登錄；刪除：報(bào)廢或丟失的書，需從目錄中去掉；

4、結(jié)論在某種數(shù)據(jù)結(jié)構(gòu)上可定義一組運(yùn)算DS就是要研究各類數(shù)據(jù)結(jié)構(gòu)上的各種運(yùn)算。三、 數(shù)據(jù)結(jié)構(gòu)的主要內(nèi)容(續(xù))綜上所述： DS主要研究?jī)?nèi)容：數(shù)據(jù)的各種邏輯結(jié)構(gòu)和物理結(jié)構(gòu)，以及它們之間的相應(yīng)關(guān)系；并對(duì)每種結(jié)構(gòu)定義相適應(yīng)的各種運(yùn)算；設(shè)計(jì)出相應(yīng)的算法；分析算法的效率。 常見的數(shù)據(jù)結(jié)構(gòu)有：數(shù)組、棧、隊(duì)列、表、串、樹、圖和文件等。四、 基本術(shù)語數(shù)據(jù)（Data)：所有能被計(jì)算機(jī)處理的符號(hào)的集合。數(shù)據(jù)元素（Data Element）：表示一個(gè)事物的一組數(shù)據(jù)稱作一個(gè)數(shù)據(jù)元素，是數(shù)據(jù)這個(gè)集合中的一個(gè)個(gè)體。 例如，要描述學(xué)生信息，可包括學(xué)生的學(xué)號(hào)、姓名、性別、年齡等數(shù)據(jù)就構(gòu)成學(xué)生情況描述的數(shù)據(jù)項(xiàng)；包括學(xué)生的學(xué)號(hào)、姓名、

5、性別、年齡等數(shù)據(jù)項(xiàng)的一組數(shù)據(jù)就構(gòu)成了學(xué)生信息的一個(gè)數(shù)據(jù)元素。數(shù)據(jù)項(xiàng)（Data Item）：構(gòu)成數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)稱作該數(shù)據(jù)元素的數(shù)據(jù)項(xiàng)，數(shù)據(jù)項(xiàng)是數(shù)據(jù)具有意義的最小單位。四、 基本術(shù)語（續(xù)）數(shù)據(jù)對(duì)象（Data Object）: 具有相同特性的數(shù)據(jù)元素的集合。例如：數(shù)據(jù)集合D=0，1，A，B，Z則：數(shù)據(jù)對(duì)象正整數(shù)N 0，1，數(shù)據(jù)對(duì)象字母C A，B，Z 數(shù)據(jù)元素是數(shù)據(jù)的一個(gè)個(gè)體，數(shù)據(jù)對(duì)象是數(shù)據(jù)的一個(gè)子集。數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)的描述數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)的描述都使用某種高級(jí)程序設(shè)計(jì)語言來描述，本課程采用C語言描述。通常用C語言中的結(jié)構(gòu)體來定義數(shù)據(jù)元素的數(shù)據(jù)類型。抽象數(shù)據(jù)元素：沒有實(shí)際含義的數(shù)據(jù)元素稱作抽象數(shù)據(jù)元素

6、。抽象數(shù)據(jù)元素類型：沒有確切定義的數(shù)據(jù)類型稱作抽象數(shù)據(jù)元素類型。在以后討論中，用符號(hào)DataType表示抽象數(shù)據(jù)類型。在C語言中可通過類型定義符typedef實(shí)現(xiàn)抽象數(shù)據(jù)類型為具體數(shù)據(jù)類型。四、 基本術(shù)語（續(xù)）數(shù)據(jù)結(jié)構(gòu)（Data Structure）：是帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。所謂結(jié)構(gòu)就是數(shù)據(jù)元素之間的關(guān)系，即描述數(shù)據(jù)元素之間的運(yùn)算及運(yùn)算規(guī)則。用集合的形式描述，數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組：DS=(D，R) 其中：D是數(shù)據(jù)元素的集合，R是D上關(guān)系的集合。 簡(jiǎn)言之，數(shù)據(jù)元素和其相互關(guān)系稱為數(shù)據(jù)結(jié)構(gòu)四、 基本術(shù)語（續(xù)）數(shù)據(jù)的邏輯結(jié)構(gòu)（Logical Structure）：指數(shù)據(jù)元素之間的相互聯(lián)系方式或結(jié)

7、構(gòu)關(guān)系。例如：線性結(jié)構(gòu)，樹結(jié)構(gòu)，圖結(jié)構(gòu)線性結(jié)構(gòu)：n個(gè)數(shù)據(jù)元素的有限序列，數(shù)據(jù)元素之間是順序關(guān)系。樹結(jié)構(gòu)：除根結(jié)點(diǎn)外每個(gè)數(shù)據(jù)元素只有一個(gè)前驅(qū)數(shù)據(jù)元素，可有零個(gè)或若干個(gè)后繼數(shù)據(jù)元素。圖結(jié)構(gòu)：每個(gè)數(shù)據(jù)元素可有零個(gè)或若干個(gè)前驅(qū)數(shù)據(jù)元素和可有零個(gè)或若干個(gè)后繼數(shù)據(jù)元素。數(shù)據(jù)的物理結(jié)構(gòu)（Physical Structure）：指數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)的存儲(chǔ)方式?；拘问接袃煞N：順序存儲(chǔ)方式和鏈?zhǔn)酱鎯?chǔ)方式數(shù)據(jù)的操作：對(duì)一種數(shù)據(jù)類型的數(shù)據(jù)進(jìn)行的某種處理稱作數(shù)據(jù)的操作，對(duì)一種數(shù)據(jù)類型的所有操作稱作數(shù)據(jù)的操作集合1.2 抽象數(shù)據(jù)類型類型：是一組織的集合。例如：整數(shù)類型就是計(jì)算機(jī)內(nèi)所能表示的整數(shù)的集合。數(shù)據(jù)類型：是指一個(gè)

8、類型和定義在這個(gè)類型上的操作集合。例如：C語言中的整數(shù)類型，不僅指整數(shù)數(shù)值的集合，而且包括對(duì)整數(shù)類型進(jìn)行的操作抽象數(shù)據(jù)類型（Abstract Data Type，縮寫為ADT）是指一個(gè)邏輯概念上的類型和這個(gè)類型上的操作。數(shù)據(jù)類型與抽象數(shù)據(jù)類型的區(qū)別：數(shù)據(jù)類型指的是高級(jí)程序設(shè)計(jì)語言支持的基本數(shù)據(jù)類型，而抽象數(shù)據(jù)類型指的是在基本數(shù)據(jù)類型支持下用戶新設(shè)計(jì)的數(shù)據(jù)類型。軟件的設(shè)計(jì)采用模塊化方法，抽象數(shù)據(jù)類型（如表、堆棧、隊(duì)列、串、樹、二叉樹、圖的等）就是構(gòu)造大型軟件的最基本的模塊。1.算法和算法的時(shí)間復(fù)雜度一算法（Algorithm）算法概念：算法是一個(gè)有限的指令集， 遵循指令流可以完成特定的功能。算法

9、基本特性： 有窮性：算法經(jīng)有限步后結(jié)束； 確定性：下一步必須是明確的； 可行性：每一步是可執(zhí)行的；1.3 算法和算法的時(shí)間復(fù)雜度算法與程序的區(qū)別算法是解決問題的一種方法或一個(gè)過程，考慮如何將輸入轉(zhuǎn)換成輸出，一個(gè)問題可以有多種算法。程序是用某種程序設(shè)計(jì)語言對(duì)算法的具體實(shí)現(xiàn)。主要區(qū)別在：有窮性和描述方法 程序可以是無窮的，例如OS，算法是有窮的； 程序是用程序設(shè)計(jì)語言描述，在機(jī)器上可以執(zhí)行； 算法還可以用框圖、自然語言等方式描述。1.算法和算法的時(shí)間復(fù)雜度二算法描述語言c語言為了便于理解掌握算法的思想和實(shí)質(zhì)，本課程采用c語言來描述各種算法。抽象數(shù)據(jù)類型:抽象數(shù)據(jù)類型名 變量名；抽象數(shù)據(jù)類型 操作:

10、抽象數(shù)據(jù)類型名 函數(shù)名（形參）語句；1.算法和算法的時(shí)間復(fù)雜度 數(shù)據(jù)類型 函數(shù)名 (參數(shù)表) 函數(shù)體 調(diào)用過程語句為：函數(shù)名（參數(shù)表）調(diào)用函數(shù)語句為：變量名函數(shù)名（參數(shù)表）1.算法和算法的時(shí)間復(fù)雜度賦值語句：變量名表達(dá)式；分支語句：IF (條件) 語句ELSE語句；SWITCH(表達(dá)式) CASE 常量表達(dá)式：語句； CASE 常量表達(dá)式n ： 語句n； DEFAULT: 語句n+1； 1.算法和算法的時(shí)間復(fù)雜度循環(huán)語句：FOR （變量名初值；邏輯表達(dá)式；表達(dá)式）循環(huán)體WHILE （條件） 循環(huán)體；Do 循環(huán)體 WHILE 條件；標(biāo)準(zhǔn)輸入輸出過程：printf（格式輸出符，變量表）； scanf（輸入格式符，變量表）；1.算法和算法的時(shí)間復(fù)雜度三算法分析如何衡量一個(gè)正確算法的好壞？衡量的三個(gè)尺度：運(yùn)行所花費(fèi)的時(shí)間（算法的時(shí)間特性）；所占用存儲(chǔ)空間的大?。ㄋ惴ǖ目臻g特）；其他（可讀性、易調(diào)性、健壯性等）。時(shí)間和空間特性的巨大改進(jìn)源于更好的數(shù)據(jù)結(jié)構(gòu)或算法。1.算法和算法的時(shí)間復(fù)雜度語句頻度（Frequency Count）：語句可能重復(fù)執(zhí)行的最大次數(shù)。時(shí)間復(fù)雜度（Time Complexity）：設(shè)算法中所有語句的語句頻度為t(n)，f(n)是當(dāng)n趨向無窮大時(shí)與t(n)為同階無窮大，則算法的時(shí)間復(fù)雜度T(n)=O(f(n)其中：n為算法計(jì)算量或稱為規(guī)模（size）； f(n)是運(yùn)算