數(shù)據(jù)結構第一章

1、1.1 程序設計的實質(zhì)是數(shù)據(jù)表示和數(shù)據(jù)處理。1.2 數(shù)據(jù)要能被計算機加工處理，首先必須能夠存儲在機器中，成為能被機器直接操作的對 象。數(shù)據(jù)在計算機存儲器中的這種存在形式稱為機內(nèi)表示。 將數(shù)據(jù)從機外表示轉化為機內(nèi)表 示，這項任務稱為數(shù)據(jù)表示。1.3 用適當?shù)目蓤?zhí)行語句編制程序，以便讓計算機去執(zhí)行對數(shù)據(jù)機內(nèi)表示的各種操作，從而 實現(xiàn)處理要求，即得到所需的結果，這項工作稱為數(shù)據(jù)處理。1.4 軟件工程學認為： 軟件系統(tǒng)的生存期可分為軟件計劃、 需求分析、 軟件設計、 軟件編碼、 軟件測試和軟件維護等六個階段。 程序設計包括前五個階段 （程序設計包括數(shù)據(jù)表示和數(shù)據(jù) 處理兩個方面） 。1.5 數(shù)據(jù)結構課程

2、集中討論以設計階段為核心、同時涉及編碼階段和分析階段的一個小范圍 內(nèi)的若干基本問題。 概括的說， 其主要內(nèi)容包括： 數(shù)據(jù)的邏輯結構、定義在邏輯結構上的基 本運算、數(shù)據(jù)的存儲結構和運算的實現(xiàn)。 其中，數(shù)據(jù)的邏輯結構是數(shù)據(jù)的組織形式，基本運 算規(guī)定了數(shù)據(jù)的基本操作方式。 由一種邏輯結構和一組基本運算構成的整體是實際問題的一 種數(shù)學模型，這種數(shù)學模型的建立、選擇和實現(xiàn)是數(shù)據(jù)結構的核心問題。1.6 數(shù)據(jù)表示任務是逐步完成的，即數(shù)據(jù)表示形式的變化過程是：機外表示邏輯結構 存儲結構。數(shù)據(jù)處理任務也是逐步完成的，即有轉化過程：處理需求基本運算和運算算法。數(shù)據(jù)表示與數(shù)據(jù)處理是密切相關的， 數(shù)據(jù)處理方式總是與數(shù)

3、據(jù)的相應的表示形式相聯(lián)系， 反之亦然。2.1 從數(shù)據(jù)結構的觀點看，數(shù)據(jù)就分成三個不同的層次，即數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項。凡能 被計算機存儲、 加工的對象通稱為數(shù)據(jù)； 數(shù)據(jù)元素是數(shù)據(jù)的基本單位， 在程序中作為一個整 體而加以考慮和處理， 即數(shù)據(jù)元素被當作運算的基本單位， 并且通常具有完整確定的實際意 義，又被稱為元素、結點、頂點或記錄；數(shù)據(jù)元素又是數(shù)據(jù)項組成的，但數(shù)據(jù)項通常不具有 完整確定的實際意義， 或不當作一個整體對待， 又稱為字段或域， 它是數(shù)據(jù)的不可分割的最 小標識單位。2.2 從數(shù)據(jù)結構的觀點看，重要的是數(shù)據(jù)元素之間的邏輯關系。所謂邏輯關系是指數(shù)據(jù)元素 之間的關聯(lián)方式或稱“鄰接關系” 。

4、數(shù)據(jù)元素之間邏輯關系的整體稱為邏輯結構。數(shù)據(jù)的邏 輯結構就是數(shù)據(jù)的組織形式。四類基本邏輯結構：集合、線性結構、樹形結構和圖狀結構。1）邏輯結構與數(shù)據(jù)元素本身的形式、內(nèi)容無關2）邏輯結構與數(shù)據(jù)元素的相對的相對位置無關3）邏輯結構與所含結點個數(shù)無關2.3 運算是指在任何邏輯結構上施加的操作，即對邏輯結構的加工。這種加工以一個或多個 邏輯結構及其他有關參數(shù)為對象， 以經(jīng)過修改的邏輯結構或從原邏輯結構中提取的有關信息 為結果。根據(jù)操作的效果將運算分成兩種基本類型：1）加工型運算，其操作改變了原邏輯結構的“值”2）引用型運算，其操作不改變原邏輯結構，只從中提取某些信息作為運算的結果2.4 假如 A 是

5、S 上的一些運算的集合， B 是 A 的一個子集，使得 A 中每一運算都可以“歸 約”為 B 中一個或多個運算，而 B 中任一運算不可歸約為別的運算，則稱 B 中運算為（相 對于 A 的）基本運算。2.5對某些邏輯結構 S和在S上的基本運算集 B，由S和B構成的整體（S, B）往往在大量 不同種類的實際問題的求解中反復出現(xiàn)， 在此將這樣的整體稱為一個 “數(shù)據(jù)結構” ；線性表、 隊列、棧等都是數(shù)據(jù)結構,這三個數(shù)據(jù)結構有相同的邏輯結構但有不同的基本運算集。3.1 存儲實現(xiàn)的基本目標是建立數(shù)據(jù)的機內(nèi)表示,存儲實現(xiàn)建立的機內(nèi)表示應遵循選定的邏 輯結構。數(shù)據(jù)的機內(nèi)表示稱為數(shù)據(jù)的存儲結構。3.2 通常，存

6、儲結點之間可以有四種關聯(lián)方式，稱為四種基本存儲方式：順序存儲方式、鏈 式存儲方式、索引存儲方式、散列存儲方式。 原則上，一種邏輯結構可以采用四種存儲方式 中的任何一種來實現(xiàn)，由此得到的存儲結構稱為給定邏輯結構的存儲實現(xiàn)或存儲映像。3.3 一個運算的實現(xiàn)是指一個完成該運算功能的程序。由于運算只描述處理功能，不包括處 理步驟和方法，因此運算實現(xiàn)的核心是處理步驟的規(guī)定，即算法設計。一個算法規(guī)定了求解給定類型問題所需的所有“處理步驟”及其執(zhí)行順序，使得給定類 型的任何問題能在有限時間內(nèi)被機械的求解。 根據(jù)描述算法的語言的不同， 算法可分為三類：1）運行終止的程序可執(zhí)行部分， 用程序設計語言描述的算法，

7、 這種算法可直接在計算機 上運行，有時也將這種算法稱為程序2）偽語言算法，采用某種“偽程序設計語言”描述的算法，該算法不可直接在計算機上 運行，但容易編寫和閱讀，故適合教學3）非形式算法， 用自然語言，同時可能還使用了程序設計語言或偽程序設計語言描述的 算法稱為非形式算法。4.1 通常從以下幾方面評價算法（包括程序）的質(zhì)量：1）正確性 算法應能正確的實現(xiàn)預定的功能2）易讀性 算法應易于閱讀和理解3）健壯性 當環(huán)境發(fā)生變化時，算法應能適當?shù)刈龀龇磻蜻M行處理4）高效率 即達到所需的時空性能 這些指標往往是互相沖突的，因此在實際評價中應根據(jù)需要有所側重；數(shù)據(jù)結構課程著重 討論算法的時空性能。確定一

8、個算法的時空性能，這項工作稱為“算法分析”4.2 一個算法的時空性能是指該算法的時間性能（或時間效率）和空間性能（或空間效率） 前者是算法包含的計算量，后者是算法需要的存儲量2.3 估算求解某類問題的各個算法在給定輸入下的計算量：1）根據(jù)該類問題的特點合理的選擇一種或幾種操作作為“標準操作”2）確定每個算法在給定輸入下共執(zhí)行了多少次標準操作，并將此次數(shù)規(guī)定為該算法在給定輸入下的計算量4.4 確定一個算法的計算量的兩種方式：1）以算法在所有輸入下的計算量的最大值作為算法的計算量， 這種計算量稱為算法的最壞 情況時間復雜性或最壞情況時間復雜度2）以算法在所有輸入下的計算量的加權平均值作為算法的計算

9、量， 這種計算量稱為算法的 平均時間復雜性或平均時間復雜度最壞情況時間復雜性和平均時間復雜性通稱為時間復雜性或時間復雜度；一個算法的輸入 規(guī)模或問題的規(guī)模是指作為該算法輸入的數(shù)據(jù)所含數(shù)據(jù)元素的數(shù)目， 或與此數(shù)目有關的其他 參數(shù)。4.5常見的量級：常數(shù)階 0 （ 1）、對數(shù)階O （Iog2n）、線性階O （n）、平方階O （n的平方）和指數(shù)階 O（ 2 的 n 次方）；通常認為，具有指數(shù)量級的算法是實際不可計算的，而量級低 于平方階的算法是高效率的。存儲量和空間復雜性的概念與計算量和時間復雜性的概念類 似，但通常更關心一個算法除輸入數(shù)據(jù)占用存儲空間之外所需的附加存儲空間的大小。4.6“數(shù)據(jù)結構”的兩種含義：一是作為一門課程的名稱，二是作為一個科學概念。作為一個科學概念，一種觀點認為，一個數(shù)據(jù)結構是由一個邏輯結構S、一個定義在S上的基本運算集和S的一個存儲實現(xiàn) D所構成的整體（S、A、D）；本書傾向另一觀點，一個數(shù)據(jù) 結構是由一個邏輯結構S和S上的一個基本運算集構成的整體（S、A）。數(shù)據(jù)結構的基 本任務可概括為數(shù)據(jù)結構的設計和實現(xiàn)，數(shù)據(jù)結構課程的主要內(nèi)容：1）數(shù)據(jù)結構（包括邏輯運算和基本運算集）的定義2）數(shù)據(jù)結構的實現(xiàn)（包括存儲實現(xiàn)和運算實現(xiàn)）3）數(shù)