計算機軟件技術基礎(郵電)

1、1.1數據結構的基本概念數據結構的基本概念1.1.1數據結構的研究內容及其重要性用計算機處理問題的步驟用計算機處理問題的步驟 首先需要把客觀對象抽象為某種形式的數據首先需要把客觀對象抽象為某種形式的數據 然后設計對這些數據進行處理的算法，由計算機執(zhí)然后設計對這些數據進行處理的算法，由計算機執(zhí)行設計好的算法，行設計好的算法， 用某種計算機語言（例如：用某種計算機語言（例如：C C語言）描述交計算機處語言）描述交計算機處理。理。數據結構的重要性數據結構的重要性 程序程序= =數據結構算法數據結構算法數據結構的學科地位數據結構的學科地位數學數學代數系統代數系統編碼理論編碼理論數據類型數據類型算子關系

2、算子關系數據表示數據表示數據運算數據運算數據結構數據結構數據存取數據存取機器組織機器組織存儲裝置存儲裝置硬件硬件（計算機系統設計）（計算機系統設計）文件系統文件系統數據組織數據組織信息檢索信息檢索軟件軟件（計算機程序設計）（計算機程序設計）19681968年美國的唐納德年美國的唐納德克努特（克努特（Donald E. Donald E. KunthKunth）教授出版了其名著）教授出版了其名著計算機程序設計藝術計算機程序設計藝術第一卷第一卷基本算法基本算法，首次系統地闡述了，首次系統地闡述了數據結構數據結構的主要內容，即：的主要內容，即： 數據的邏輯結構數據的邏輯結構 數據的存儲結構數據的存儲

3、結構 對對數據的操作數據的操作1.1.2數據結構中的基本概念和術語數據數據 非數值性數據非數值性數據（字符、指令等不表示數值的代碼（字符、指令等不表示數值的代碼) ) 數值性數據數值性數據（整數、實數、復數（整數、實數、復數) )數據元素數據元素(data element)是數據的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。 數據項（數據項（data item） 數據項是具有獨立含義的最小標識單位。 數據對象數據對象(data object) 數據的子集。具有相同性質的數據成員（數據元素）的集合。 整數數據對象 N = 0, 1, 2, ， 學生數據對象 英文字母數據對象 LETT

4、ER A ， B,Z學號學號姓名姓名數學數學計算機計算機外語外語021001王強王強879096021002李一龍李一龍699189021003張映月張映月877971021004何一端何一端848868一個若干值的集合以及在這些值上定義的一組操作的總稱。 結構結構(structure)(structure) 數據元素相互之間的關系稱為結構結構。 四類基本結構四類基本結構 集合集合 結構中的數據元素之間除了“同屬于一個集合”的關系外，別無其它關系。如下圖所示：集合 線性結構線性結構 結構中的數據元素之間存在著一對一的關系（結點結構中的數據元素之間存在著一對一的關系（結點之間的連線表示關系）。例

5、如：學生名單。如圖所示：之間的連線表示關系）。例如：學生名單。如圖所示：樹形結構樹形結構 結構中的數據元素之間存在著一對多的關系。只能結構中的數據元素之間存在著一對多的關系。只能與上一層的一個結點相關，可與下一層的多個結點相關。與上一層的一個結點相關，可與下一層的多個結點相關。例如：博弈。例如：博弈。 如圖所示：如圖所示：樹：樹：圖狀結構或網狀結構圖狀結構或網狀結構 結構中的數據元素之間存在著多對多的關系。圖中任結構中的數據元素之間存在著多對多的關系。圖中任一結點都可與多個其它結點關聯，即圖的結點之間的關系一結點都可與多個其它結點關聯，即圖的結點之間的關系是任意的。樹是圖的一種特例。是任意的。

6、樹是圖的一種特例。 例如：交通規(guī)劃；郵遞員問題。例如：交通規(guī)劃；郵遞員問題。 如下圖所示：如下圖所示：圖二、基本概念 數據結構(data structure)： 相互之間存在著一種或多種特定關系的數據元素的集合。學號學號姓名姓名語文語文數學數學物理物理021001王強王強879096021002李一龍李一龍699189021003張映月張映月877971021004何一端何一端848868 數據結構的分類 邏輯結構邏輯結構 邏輯結構就是數據元素之間的邏輯關系。 線性結構線性結構 數據邏輯結構中的一類,它的特征是若結構為非空集,則該結構有且只有一個開始結點和一個終端結點,并且所有結點都最多只有一

7、個直接前趨和一個直接后繼。線性表就是一個典型的線性結構。 非線性結構非線性結構 非線性結構的邏輯特征是該結構中一個數據元素可能有多個直接前趨和直接后繼,非線性結構中最普遍的就是圖的結構。數據數據存儲結構存儲結構 ( (物理結構物理結構) ) 反映數據元素在計算機中的存儲方法就是數據的物理結構反映數據元素在計算機中的存儲方法就是數據的物理結構。有時也稱為存儲結構。它是邏輯結構在存儲器里的實現。有時也稱為存儲結構。它是邏輯結構在存儲器里的實現。 數據存儲結構的四種基本存儲方式 順序存儲（Sequential Storage StructureSequential Storage Structure

8、） 該方式把邏輯上相鄰的數據元素存儲在物理位置上相鄰的該方式把邏輯上相鄰的數據元素存儲在物理位置上相鄰的存儲單元里，數據元素間的邏輯關系由存儲單元的鄰接關系來存儲單元里，數據元素間的邏輯關系由存儲單元的鄰接關系來體現。體現。 數組數組內存內存 鏈式存儲 (Linked Storage Structure)(Linked Storage Structure)該方法不要求邏輯上相鄰的數據元素在物理位置上該方法不要求邏輯上相鄰的數據元素在物理位置上亦相鄰，數據元素間的邏輯關系由附加的指針字段表示。亦相鄰，數據元素間的邏輯關系由附加的指針字段表示。由此得到的存儲表示稱為鏈式存儲結構。可以將物理上由此得

9、到的存儲表示稱為鏈式存儲結構?？梢詫⑽锢砩喜贿B續(xù)的數據元素在邏輯上相鄰。例：鏈表。不連續(xù)的數據元素在邏輯上相鄰。例：鏈表。 數據指針數據指針數據指針數據指針數據指針數據指針數據指針數據指針數組數組內存內存 索引存儲 （ Index Structure）該方法通常在儲存數據元素信息的同時，還建立附加的索該方法通常在儲存數據元素信息的同時，還建立附加的索引表。索引表由若干索引項組成。例如：圖書檢索（按書名、引表。索引表由若干索引項組成。例如：圖書檢索（按書名、作者、出版社、分類號索引）。作者、出版社、分類號索引）。 索引項的一般形式索引項的一般形式 (1) (1) 關鍵字是能唯一標識一個數據元素的

10、那些數據項。關鍵字是能唯一標識一個數據元素的那些數據項。 (2) (2) 稠密索引中索引項的地址指示數據元素所在的存儲位置；稠密索引中索引項的地址指示數據元素所在的存儲位置； (3) (3) 稀疏索引中索引項的地址指示一組結點的起始存儲位置。稀疏索引中索引項的地址指示一組結點的起始存儲位置。關鍵字：地址關鍵字：地址若每個數據元素在索引表中都有一個索引項若每個數據元素在索引表中都有一個索引項,則該索引表稱之則該索引表稱之為稠密索引（為稠密索引（Dense Index）。）。若一組數據元素在索引表中只對應一個索引項若一組數據元素在索引表中只對應一個索引項,則該索引表稱則該索引表稱為稀疏索引（為稀疏

11、索引（Spare Index） 。散列存儲方法（Structure） 根據數據元素的關鍵字直接計算出該結點的存儲地根據數據元素的關鍵字直接計算出該結點的存儲地址。（哈希函數（算法）址。（哈希函數（算法）哈希函數哈希函數地址地址主存儲器主存儲器地址地址對數據的操作（運算）對數據的操作（運算） 數據結構除邏輯結構和物理結構外，第三個內容就是數據結構除邏輯結構和物理結構外，第三個內容就是數據的操作，例如表的使用和維護（排序、查找、增加、數據的操作，例如表的使用和維護（排序、查找、增加、修改、刪除等）。修改、刪除等）。在數據結構中，數據的操作涉及比加減乘除算術運在數據結構中，數據的操作涉及比加減乘除算

12、術運算更廣義的運算，這些運算常常涉及算法問題。高效率算更廣義的運算，這些運算常常涉及算法問題。高效率地存儲數據和管理數據需要分析和選擇合適的算法。地存儲數據和管理數據需要分析和選擇合適的算法。 算法算法的定義（算法的定義（lgorithmlgorithm ） 一個有窮的指令集，這些指令為解決某一特定任務規(guī)定了一個運一個有窮的指令集，這些指令為解決某一特定任務規(guī)定了一個運算序列。算序列。算法的算法的特性特性輸入輸入: :有0個或多個輸入輸出輸出: :有一個或多個輸出(處理結果)確定性確定性: :每步定義都是確切、無歧義的有窮性有窮性: :算法應在執(zhí)行有窮步后結束有效性有效性: :每一條運算應足夠

13、基本算法的分析算法的分析( (lgorithmlgorithm nalysisnalysis) ) 算法分析(algorithm analysis)是指對算法的執(zhí)行時間和所需內存空間的估算。同一問題的求解往往可以使用不同的算法,通過算法分析,可以比較兩個算法的效率高低。 算法的時間復雜度算法的時間復雜度 執(zhí)行一個算法所花費的時間代價執(zhí)行一個算法所花費的時間代價。 當要解決的問題的規(guī)模以某種單位由當要解決的問題的規(guī)模以某種單位由1 1增至增至n n時，對應算時，對應算法所耗費的時間也以某種單位由法所耗費的時間也以某種單位由f(1)f(1)增至增至f(n)f(n)。此時稱該算。此時稱該算法的時間復

14、雜度為法的時間復雜度為f(n)f(n)。 問題的規(guī)模問題的規(guī)模例：例：順序查找算法的關鍵操作是順序查找算法的關鍵操作是ai ai 的值與給定值做比較。的值與給定值做比較。 順序查找成功的平均比較次數為（設：有個數據）：順序查找成功的平均比較次數為（設：有個數據）：2111ninni2/ ) 1(1)2() 1(1)(nnnnnnf時間代價（最壞、最好和平均情況） 最好情況下的時間代價。 在平均情況下的時間代價。 最壞情況下的時間代價，主要采用大 表示法來描述。大大O表示法表示法O(n)f(n)T(n) 一般提法一般提法 當且僅當存在正整數c和n0,使得T(n) cf (n)對所有的nn0成立,

15、則稱該算法的漸進時間復雜度為T( n ) = O(f( n )。這時也稱該算法的時間代價的增長率為f(n)，意味著當充分大時，該算法的復雜度不大于f(n)的一個常數倍。 基本思想基本思想 關注復雜性的數量級，而忽略數量級的系數，這樣在分析算法的復雜度時，可以忽略個別語句的執(zhí)行時間，重點分析算法的主要代價。假設：f(n) = 2n3 +2n2 + 2n + 1， 當n充分大時： T( n ) = O(n3 )算法的空間復雜度算法的空間復雜度執(zhí)行一個算法所需占用的空間代價。當要解決的問題的規(guī)模以某種單位由1增至n時，對應算法所需占用的空間也以某種單位由g(1)增至g(n)。此時稱該算法的空間復雜度

16、為g(n)。設S (n) 是算法的漸進空間復雜度，在最壞情況下它可以表示為實例特性n的某個函數f (n)的數量級，記為 ： 是為解決問題所需要的輔助存儲空間。 只有完成同一功能的幾個算法之間才具有可比性 可以使用大O表示法來標記這些空間復雜度,用以比較各算法的優(yōu)劣。 這樣在分析算法的空間復雜度時，可以忽略零星變量的存儲空間S (n) = O(f (n)常見的時間復雜度常見的時間復雜度常數階O(1)對數階O(log2n) 線性階O(n) 線性對數階O(nlog2n) 平方階O(n2) 立方階O(n3) k次方階O(nk) 指數階O(2n)1.1.3 數據結構、數據類型和抽象數據類型 數據結構 數

17、據結構是數據存在的形式。邏輯上的數據結構反映數據元素之間的邏輯關系。物理上的數據結構反映數據元素在計算機內的存儲安排。數據類型數據以數據結構分類，具有相同數據結構的數據屬同一類，數據類型表示某數據在數據分類中的歸屬，是數據的一種屬性。 一組性質相同的值的集合, 以及定義于 這個值集合上的一組操作的總稱。雙精度型double基本數據類型整型int字符型單字符型char寬字符型w_char實型單精度型float邏輯型bool數組type 指針type * 空類型 void結構 struct聯合 union枚舉enum類 class數據類型非基本數據類型char int float double v

18、oid 字符型 整型 浮點型 雙精度型 無類型 數據類型 在高級程序設計語言中已實現了的，或非高級語言直接支持的數據結構。 變量的數據類型 在程序設計語言中，一個變量的數據類型不僅規(guī)定了這個變量的取值范圍，而且定義了這個變量可用的操作。數據結構與數據類型 基本數據類型對應于簡單的數據結構 數據結構反映數據內部的構成方式，它常常用一個結構圖來描述非基本數據類型對應于復雜的數據結構。 數據結構有線性與非線性之分 在非線性數據結構中又有層次與網狀之分。 由于數據類型是按照數據結構劃分的，因此，一類數據結構對應著一種數據類型。數據類型有線性與非線性之分 數據類型按照該類型中的數據所呈現的結構也有線性與

19、非線性之分，層次與網狀之分。一個數據變量，在高級語言中的類型說明必須是該變量所具有的數據結構所對應的數據類型。 數組結構的特點 數據元素的個數固定，它們之間的邏輯關系由數據元素的序號(或叫數組的下標)來體現。這些數據元素按照序號的先后順序一個挨一個地排列起來。 每一個數據元素具有相同的結構(可以是簡單結構，也可以是復雜結構)，因而屬于同一個數據類型(相應地是簡單數據類型或構造數據類型)。這種同一的數據類型稱為基類型。 所有的數據元素被依序安排在一片連續(xù)的存儲單元中。 記錄結構的特點 與數組結構一樣，成分數據的個數固定。但成分數據之間沒有自然序，它們處于平等地位。每一個成分數據被稱為一個域并賦予域名。