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

數(shù)據(jù)結(jié)構(gòu)〔C語言描述〕1整理ppt前言

二十一世紀是科學技術(shù)高速開展的信息時代，而計算機是處理信息的主要工具，因此，人們已經(jīng)認識到，計算機知識已成為人類當代文化的一個重要組成局部。計算機科學技術(shù)以驚人的速度向前開展，它的廣泛應(yīng)用已從傳統(tǒng)的數(shù)值計算領(lǐng)域開展到各種非數(shù)值計算領(lǐng)域。在非數(shù)值計算領(lǐng)域里，數(shù)據(jù)處理的對象已從簡單的數(shù)值開展到一般的符號，進而開展到具有一定結(jié)構(gòu)的數(shù)據(jù)。在這里，面臨的主要問題是：針對每一種新的應(yīng)用領(lǐng)域的處理對象，如何選擇適宜的數(shù)據(jù)表示〔構(gòu)構(gòu)〕，如何有效地組織計算機存貯，并在此根底上又如何有效地實現(xiàn)對象之間的“運算〞關(guān)系。傳統(tǒng)的解決數(shù)值計算的許多理論、方法和技術(shù)已不能滿足解決非數(shù)值計算問題的需要，必須進行新的探索。數(shù)據(jù)結(jié)構(gòu)就是研究和解決這些問題的重要根底理論。因此，“數(shù)據(jù)結(jié)構(gòu)〞課程已成為計算機類專業(yè)的一門重要專業(yè)根底課。2整理ppt數(shù)據(jù)結(jié)構(gòu)是程序設(shè)計的中級課程，主要培養(yǎng)學生分析數(shù)據(jù)、組織數(shù)據(jù)的能力，告訴學生如何編寫效率高、結(jié)構(gòu)好的程序。本書作為計算機大專系列教材之一，在內(nèi)容的選取、概念的引入、文字的表達以及例題和習題的選擇等方面，都力求遵循面向應(yīng)用、邏輯結(jié)構(gòu)簡明合理、由淺入深、深入淺出、循序漸進、便于自學的原那么，突出其實用性與應(yīng)用性。全書共分十章。書中，安排了相當?shù)钠鶃斫榻B這些根本數(shù)據(jù)結(jié)構(gòu)的實際應(yīng)用。進入章節(jié)3整理ppt1引言

2數(shù)據(jù)結(jié)構(gòu)的開展簡史及其在計算機科學中所處的地位3什么是數(shù)據(jù)結(jié)構(gòu)

4根本概念和術(shù)語5算法和算法的描述

第一章緒論

本章介紹了數(shù)據(jù)結(jié)構(gòu)這門學科誕生的背景、開展歷史以及在計算機科學中所處的地位，重點介紹了數(shù)據(jù)結(jié)構(gòu)有關(guān)的概念和術(shù)語，讀者學習本章后應(yīng)能掌握數(shù)據(jù)、數(shù)據(jù)元素、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、數(shù)據(jù)處理、數(shù)據(jù)結(jié)構(gòu)、算法設(shè)計等根本概念，并了解如何評價一個算法的好壞。4整理ppt

1.1引言眾所周知，二十世紀四十年代，電子數(shù)字計算機問世的直接原因是解決彈道學的計算問題。早期，電子計算機的應(yīng)用范圍，幾乎只局限于科學和工程的計算，其處理的對象是純數(shù)值性的信息，通常，人們把這類問題稱為數(shù)值計算。近三十年來，電子計算機的開展異常迅猛，這不僅表現(xiàn)在計算機本身運算速度不斷提高、信息存儲量日益擴大、價格逐步下降，更重要的是計算機廣泛地應(yīng)用于情報檢索、企業(yè)管理、系統(tǒng)工程等方面，已遠遠超出了科技計算的范圍，而滲透到人類社會活動的一切領(lǐng)域。與此相應(yīng)，計算機的處理對象也從簡單的純數(shù)值性信息開展到非數(shù)值性的和具有一定結(jié)構(gòu)的信息。5整理ppt因此，再把電子數(shù)字計算機簡單地看作是進行數(shù)值計算的工具，把數(shù)據(jù)僅理解為純數(shù)值性的信息，就顯得太狹隘了。現(xiàn)代計算機科學的觀點，是把計算機程序處理的一切數(shù)值的、非數(shù)值的信息，乃至程序統(tǒng)稱為數(shù)據(jù)〔Data〕，而電子計算機那么是加工處理數(shù)據(jù)〔信息〕的工具。由于數(shù)據(jù)的表示方法和組織形式直接關(guān)系到程序?qū)?shù)據(jù)的處理效率，而系統(tǒng)程序和許多應(yīng)用程序的規(guī)模很大，結(jié)構(gòu)相當復雜，處理對象又多為非數(shù)值性數(shù)據(jù)。因此，單憑程序設(shè)計人員的經(jīng)驗和技巧已難以設(shè)計出效率高、可靠性強的程序。于是，就要求人們對計算機程序加工的對象進行系統(tǒng)的研究，即研究數(shù)據(jù)的特性以及數(shù)據(jù)之間存在的關(guān)系——數(shù)據(jù)結(jié)構(gòu)〔DateStructure〕。6整理ppt1.2數(shù)據(jù)結(jié)構(gòu)的開展簡史及其在計算機科學中所處的地位開展史：1、“數(shù)據(jù)結(jié)構(gòu)〞作為一門獨立的課程在國外是從1968年才開始設(shè)立的。2、1968年美國唐·歐·克努特教授開創(chuàng)了數(shù)據(jù)結(jié)構(gòu)的最初體系，他所著的?計算機程序設(shè)計技巧?第一卷?根本算法?是第一本較系統(tǒng)地闡述數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)及其操作的著作。7整理ppt地位：“數(shù)據(jù)結(jié)構(gòu)〞在計算機科學中是一門綜合性的專業(yè)根底課。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學、計算機硬件和計算機軟件三者之間的一門核心課程。數(shù)據(jù)結(jié)構(gòu)這一門課的內(nèi)容不僅是一般程序設(shè)計〔特別是非數(shù)值性程序設(shè)計〕的根底，而且是設(shè)計和實現(xiàn)編譯程序、操作系統(tǒng)、數(shù)據(jù)庫系統(tǒng)及其他系統(tǒng)程序的重要根底。8整理ppt

1.3什么是數(shù)據(jù)結(jié)構(gòu)

計算機解決一個具體問題時，大致需要經(jīng)過以下幾個步驟：首先要從具體問題中抽象出一個適當?shù)臄?shù)學模型，然后設(shè)計一個解此數(shù)學模型的算法〔Algorithm〕，最后編出程序、進行測試、調(diào)整直至得到最終解答。尋求數(shù)學模型的實質(zhì)是分析問題，從中提取操作的對象，并找出這些操作對象之間含有的關(guān)系，然后用數(shù)學的語言加以描述。計算機算法與數(shù)據(jù)的結(jié)構(gòu)密切相關(guān)，算法無不依附于具體的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)直接關(guān)系到算法的選擇和效率。運算是由計算機來完成，這就要設(shè)計相應(yīng)的插入、刪除和修改的算法。也就是說，數(shù)據(jù)結(jié)構(gòu)還需要給出每種結(jié)構(gòu)類型所定義的各種運算的算法。直觀定義：數(shù)據(jù)結(jié)構(gòu)是研究程序設(shè)計中計算機操作的對象以及它們之間的關(guān)系和運算的一門學科。9整理ppt1.4根本概念和術(shù)語1．數(shù)據(jù)

數(shù)據(jù)是人們利用文字符號、數(shù)字符號以及其他規(guī)定的符號對現(xiàn)實世界的事物及其活動所做的描述。在計算機科學中，數(shù)據(jù)的含義非常廣泛，我們把一切能夠輸入到計算機中并被計算機程序處理的信息，包括文字、表格、圖象等，都稱為數(shù)據(jù)。例如，一個個人書庫管理程序所要處理的數(shù)據(jù)可能是一張如表1-1所示的表格。10整理ppt

表1-1個人書庫11整理ppt2．結(jié)點結(jié)點也叫數(shù)據(jù)元素，它是組成數(shù)據(jù)的根本單位。在程序中通常把結(jié)點作為一個整體進行考慮和處理。例如，在表1-1所示的個人書庫中，為了便于處理，把其中的每一行〔代表一本書〕作為一個根本單位來考慮，故該數(shù)據(jù)由10個結(jié)點構(gòu)成。一般情況下，一個結(jié)點中含有假設(shè)干個字段〔也叫數(shù)據(jù)項〕。例如，在表1-1所示的表格數(shù)據(jù)中，每個結(jié)點都有登錄號、書號、書名、作者、出版社和價格等六個字段構(gòu)成。字段是構(gòu)成數(shù)據(jù)的最小單位。12整理ppt3．邏輯結(jié)構(gòu)結(jié)點和結(jié)點之間的邏輯關(guān)系稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。在表1-1所示的表格數(shù)據(jù)中，各結(jié)點之間在邏輯上有一種線性關(guān)系，它指出了10個結(jié)點在表中的排列順序。根據(jù)這種線性關(guān)系，可以看出表中第一本書是什么書，第二本書是什么書，等等。4．存儲結(jié)構(gòu)數(shù)據(jù)在計算機中的存儲表示稱為數(shù)據(jù)的存儲結(jié)構(gòu)。在表1-1所示的表格數(shù)據(jù)在計算機中可以有多種存儲表示，例如，可以表示成數(shù)組，存放在內(nèi)存中；也可以表示成文件，存放在磁盤上，等等。13整理ppt5．數(shù)據(jù)處理數(shù)據(jù)處理是指對數(shù)據(jù)進行查找、插入、刪除、合并、排序、統(tǒng)計以及簡單計算等的操作過程。在早期，計算機主要用于科學和工程計算，進入八十年代以后，計算機主要用于數(shù)據(jù)處理。據(jù)有關(guān)統(tǒng)計資料說明，現(xiàn)在計算機用于數(shù)據(jù)處理的時間比例到達80%以上，隨著時間的推移和計算機應(yīng)用的進一步普及，計算機用于數(shù)據(jù)處理的時間比例必將進一步增大。14整理ppt6．數(shù)據(jù)結(jié)構(gòu)〔DataStructure〕數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)元素〔DataElement〕之間抽象化的相互關(guān)系和這種關(guān)系在計算機中的存儲表示〔即所謂數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)〕，并對這種結(jié)構(gòu)定義相適應(yīng)的運算，設(shè)計出相應(yīng)的算法，而且確保經(jīng)過這些運算后所得到的新結(jié)構(gòu)仍然是原來的結(jié)構(gòu)類型。為了表達上的方便和防止產(chǎn)生混淆，通常我們把數(shù)據(jù)的邏輯結(jié)構(gòu)統(tǒng)稱為數(shù)據(jù)結(jié)構(gòu)，把數(shù)據(jù)的物理結(jié)構(gòu)統(tǒng)稱為存儲結(jié)構(gòu)〔StorageStructure〕。15整理ppt7．數(shù)據(jù)類型數(shù)據(jù)類型是指程序設(shè)計語言中各變量可取的數(shù)據(jù)種類。數(shù)據(jù)類型是高級程序設(shè)計語言中的一個根本概念，它和數(shù)據(jù)結(jié)構(gòu)的概念密切相關(guān)。一方面，在程序設(shè)計語言中，每一個數(shù)據(jù)都屬于某種數(shù)據(jù)類型。類型明顯或隱含地規(guī)定了數(shù)據(jù)的取值范圍、存儲方式以及允許進行的運算?？梢哉J為，數(shù)據(jù)類型是在程序設(shè)計中已經(jīng)實現(xiàn)了的數(shù)據(jù)結(jié)構(gòu)。另一方面，在程序設(shè)計過程中，當需要引入某種新的數(shù)據(jù)結(jié)構(gòu)時，總是借助編程語言所提供的數(shù)據(jù)類型來描述數(shù)據(jù)的存儲結(jié)構(gòu)。16整理ppt8．算法簡單地說就是解決特定問題的方法〔關(guān)于算法的嚴格定義，在此不作討論〕。特定的問題可以是數(shù)值的，也可以是非數(shù)值的。解決數(shù)值問題的算法叫做數(shù)值算法，科學和工程計算方面的算法都屬于數(shù)值算法，如求解數(shù)值積分，求解線性方程組、求解代數(shù)方程、求解微分方程等。解決非數(shù)值問題的算法叫做非數(shù)值算法，數(shù)據(jù)處理方面的算法都屬于非數(shù)值算法。例如各種排序算法、查找算法、插入算法、刪除算法、遍歷算法等。數(shù)值算法和非數(shù)值算法并沒有嚴格的區(qū)別。17整理ppt一般說來，在數(shù)值算法中主要進行算術(shù)運算，而在非數(shù)值算法中主要進行比較和邏輯運算。另一方面，特定的問題可能是遞歸的，也可能是非遞歸的，因而解決它們的算法就有遞歸算法和非遞歸算法之分。從理論上講，任何遞歸算法都可以通過循環(huán)，堆棧等技術(shù)轉(zhuǎn)化為非遞歸算法。18整理ppt1.5算法和算法的描述

1.5.1算法算法是執(zhí)行特定計算的有窮過程。這個過程有5個特點：1.動態(tài)有窮：當執(zhí)行一個算法時，不管是何種情況，在經(jīng)過了有限步驟后，這個算法一定要終止。2.確定性：算法中的每條指令都必須是清楚的，指令無二義性。3.輸入：具有0個或0個以上由外界提供的量。4.輸出：產(chǎn)生1個或多個結(jié)果。5.可行性：每條指令都充分根本，原那么上可由人僅用筆和紙在有限的時間內(nèi)也能完成。注意：算法和程序是有區(qū)別的，即程序未必能滿足動態(tài)有窮。在本書中，我們只討論滿足動態(tài)有窮的程序，因此“算法〞和“程序〞是通用的。19整理ppt

1.5.2算法的描述

一個算法可以用自然語言、數(shù)字語言或約定的符號來描述，也可以用計算機高級程序語言來描述，如Pascal語言、C語言或偽代碼等。本書選用C語言作為描述算法的工具。現(xiàn)簡單說明C語言的語法結(jié)構(gòu)如下：20整理ppt1．預(yù)定義常量和類型：

#defineTRUE1；

#defineFALSE-1；

#defineERRORNULL；21整理ppt2．函數(shù)的形式[數(shù)據(jù)類型]函數(shù)名〔[形式參數(shù)]〕[形式參數(shù)說明；]{內(nèi)部數(shù)據(jù)說明；執(zhí)行語句組；}/*函數(shù)名*/〈函數(shù)的定義主要由函數(shù)名和函數(shù)體組成，函數(shù)體用花括號“{〞和“}〞括起來。函數(shù)中用方括號括起來的局部為可選項，函數(shù)名之間的圓括號不可省略。函數(shù)的結(jié)果可由指針或別的方式傳遞到函數(shù)之外。執(zhí)行語句可由各種類型的語句所組成，兩個語句之間用“；〞號分隔。可將函數(shù)中的表達式的值通過return語句返回給調(diào)用它的函數(shù)。最后的花括號“}〞之后的/*函數(shù)名*/為注釋局部，可舍。

22整理ppt3．賦值語句簡單賦值：〈變量名〉=〈表達式〉，它表示將表達式的值賦給左邊的變量；

〈變量〉++，它表示變量加1后賦值給變量；

〈變量〉--，它表示變量減1后賦值給變量；23整理ppt成組賦值：1.〔〈變量1〉，〈變量2〉，〈變量3〉，…〈變量k〉〕=〔〈表達式1〉，〈表達式2〉，〈表達式3〉，…〈表達式k〉〕；2.〈數(shù)組名1〉[下標1…下標2]=〈數(shù)組名2〉[下標1…下標2]24整理ppt串聯(lián)賦值：〈變量1〉=〈變量2〉=〈變量3〉=…=〈變量k〉=〈表達式〉；條件賦值：〈變量名〉=〈條件表達式〉？〈表達式1〉：〈表達式2〉；交換賦值：〈變量1〉←→〈變量2〉，表示變量1和變量2互換；25整理ppt4．條件選擇語句if〔〈表達式〉〕語句；if〔〈表達式〉〕語句1；else語句2；情況語句switch〔〈表達式〉〕{case判斷值1；語句組1；break；case判斷值2；語句組2；break；……case判斷值n；語句組n；break；[default：語句組；break；]}注意：switchcase語句是先計算表達式的值，然后用其值與判斷值相比較，假設(shè)它們相一致時，就執(zhí)行相應(yīng)的case下的語句組；假設(shè)不一致，那么執(zhí)行default下的語句組；其中的方括號代表可選項。26整理ppt

5．循環(huán)語句⑴for語句for〔〈表達式1〉；〈表達式2〉；〈表達式3〉〕{循環(huán)體語句；}

首先計算表達式1的值，然后求表達式2的值，假設(shè)結(jié)果非零那么執(zhí)行循環(huán)體語句，最后對表達式3運算，如此循環(huán)，直到表達式2的值為零時止。27整理ppt⑵while語句while〔〈條件表達式〉〕{循環(huán)體語句；}while循環(huán)首先計算條件表達式的值，假設(shè)條件表達式的值非零，那么執(zhí)行循環(huán)體語句，然后再次計算條件表達式，重復執(zhí)行，直到條件表達式的值為假時退出循環(huán)，執(zhí)行該循環(huán)之后的語句。28整理ppt⑶do-while語句do{循環(huán)體語句}while〔〈條件表達式〉〕該循環(huán)語句首先執(zhí)行循環(huán)體語句。然后再計算條件表達式的值，假設(shè)條件表達式成立，那么再次執(zhí)行循環(huán)體，再計算條件表達式的值，直到條件表達式的值為零，即條件不成立時結(jié)束循環(huán)。29整理ppt6．輸入、輸出語句輸入語句：用函數(shù)scanf實現(xiàn)，特別當數(shù)據(jù)為字符時，用getchar函數(shù)實現(xiàn)。輸出語句：用printf函數(shù)實現(xiàn)，當要輸出字符數(shù)據(jù)時，用putchar函數(shù)實現(xiàn)。30整理ppt7．其他一些語句〔1〕return表達式或return：用于函數(shù)結(jié)束?！?〕break語句：可用在循環(huán)語句或case語句中結(jié)束循環(huán)過程或跳出情況語句?！?〕exit語句：表示出現(xiàn)異常情況時，控制退出語句。8．注釋形式可用/*字符串*/或者單行注釋或//文字序列。31整理ppt9．一些根本的函數(shù)如：max函數(shù)，用于求一個或幾個表達式中的最大值；min函數(shù)，用于求一個或幾個表達式中的最小值；abs函數(shù)，用于求表達式的絕對值；eof函數(shù)，用于判定文件是否結(jié)束；eoln函數(shù)，用于判斷文本行是否結(jié)束。32整理ppt例計算f=1！+2！+3！+…+n！，用C語言描述。voidfactorsum〔n〕intn；{inti，j；intf，w；f=0；for〔i=1，i〈=n；i++〕{w=1；for〔j=1，j〈=i；j++〕w=w*j；f=f+w；}return；}上述算法所用到的運算有乘法、加法、賦值和比較，其根本運算為乘法操作。在上述算法的執(zhí)行過程中，對外循環(huán)變量i的每次取值，內(nèi)循環(huán)變量j循環(huán)i次。因為內(nèi)循環(huán)每執(zhí)行一次，內(nèi)循環(huán)體語句w=w*j只作一次乘法操作，即當內(nèi)循環(huán)變量j循環(huán)i次時，內(nèi)循環(huán)體的語句w=w*j作i次乘法。所以，整個算法所作的乘法操作總數(shù)是：f〔n〕=1+2+3+…n=n〔n-1〕/2。33整理ppt1.5.3算法評價設(shè)計一個好的算法應(yīng)考慮以下幾個方面：34整理ppt1．正確性“正確〞的含義在通常的用法中有很大的差異，大體可分為以下四個層次：①程序不含語法錯誤；②程序?qū)τ趲捉M輸入數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果；③程序?qū)τ诰倪x擇的典型、苛刻而帶有刁難性的幾組數(shù)據(jù)能夠得出滿足規(guī)格說明要求的結(jié)果；④程序?qū)σ磺泻戏ǖ妮斎霐?shù)據(jù)都能產(chǎn)生滿足規(guī)格說明要求的結(jié)果。35整理ppt2．運行時間運行時間是指一個算法在計算機上運算所花費的時間。它大致等于計算機執(zhí)行一種簡單操作〔如賦值操作、轉(zhuǎn)向操作、比較操作等等〕所需要的時間與算法中進行簡單操作次數(shù)的乘積。通常把算法中包含簡單操作次數(shù)的多少叫做算法的時間復雜性，它是一個算法運行時間的相對量度。36整理ppt3．占用的存儲空間一個算法在計算機存儲器上所占用的存儲空間，包括存儲算法本身所占用的存儲空間，算法的輸入、輸出數(shù)據(jù)所占用的存儲空間和算法運行過程中臨時占用的存儲空間。分析一個算法所占用的存儲空間要從各方面綜合考慮。算法在運行過程中所占用的存儲空間的大小被定義為算法的空間復雜性。它包括局部變量所