《數(shù)據(jù)結構(C語言版)》由會員分享，可在線閱讀，更多相關《數(shù)據(jù)結構(C語言版)（608頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、數(shù)據(jù)結構實用教程（C語言版）第第1章章概論概論本章主要介紹以下內容：本章主要介紹以下內容：本章主要介紹以下內容：本章主要介紹以下內容：數(shù)據(jù)結構中涉及的相關概念數(shù)據(jù)結構中涉及的相關概念數(shù)據(jù)結構中涉及的相關概念數(shù)據(jù)結構中涉及的相關概念數(shù)據(jù)結構研究的主要內容數(shù)據(jù)結構研究的主要內容數(shù)據(jù)結構研究的主要內容數(shù)據(jù)結構研究的主要內容算法的概念、描述方法以及評價標準算法的概念、描述方法以及評價標準算法的概念、描述方法以及評價標準算法的概念、描述方法以及評價標準本章目錄本章目錄1.11.1什么是數(shù)據(jù)結構什么是數(shù)據(jù)結構什么是數(shù)據(jù)結構什么是數(shù)據(jù)結構11.21.2算法和算法分析算法和算法分析算法和算法分析算法和算法分析

2、25.55.5哈夫曼樹哈夫曼樹哈夫曼樹哈夫曼樹51.31.3本章小結本章小結本章小結本章小結3結束結束1.1什么是數(shù)據(jù)結構什么是數(shù)據(jù)結構v1.1.1基本概念及術語基本概念及術語v1.1.2數(shù)據(jù)的邏輯結構數(shù)據(jù)的邏輯結構v1.1.3數(shù)據(jù)的存儲結構數(shù)據(jù)的存儲結構v1.1.4抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型返回到本節(jié)目錄返回到總目錄返回到總目錄返回到總目錄返回到總目錄1.1.1基本概念及術語基本概念及術語在系統(tǒng)的學習數(shù)據(jù)結構知識之前，先了解一些相在系統(tǒng)的學習數(shù)據(jù)結構知識之前，先了解一些相關概念和術語。關概念和術語。1數(shù)據(jù)（數(shù)據(jù)（Data）指所有能輸入到計算機中并被計算機程序處理的指所有能輸入到計算機中并被計算

3、機程序處理的符號的總稱。例如，整數(shù)、實數(shù)、字符、圖像、符號的總稱。例如，整數(shù)、實數(shù)、字符、圖像、聲音等都是數(shù)據(jù)。聲音等都是數(shù)據(jù)。2數(shù)據(jù)元素（數(shù)據(jù)元素（DataElement）數(shù)據(jù)元素（也稱為結點）是數(shù)據(jù)的基本單位，在數(shù)據(jù)元素（也稱為結點）是數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考慮和處計算機程序中通常作為一個整體進行考慮和處理。一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項組成。理。一個數(shù)據(jù)元素可以由若干個數(shù)據(jù)項組成。數(shù)據(jù)項是數(shù)據(jù)處理中不可分割的最小單位。數(shù)據(jù)項是數(shù)據(jù)處理中不可分割的最小單位。返回到本節(jié)目錄3數(shù)據(jù)結構（數(shù)據(jù)結構（DataStructure）是相互之間存在一種或多種特定關系的數(shù)據(jù)元是

4、相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合。這些數(shù)據(jù)元素不是孤立存在的，素的集合。這些數(shù)據(jù)元素不是孤立存在的，而是有著某種關系，這種關系稱為結構。而是有著某種關系，這種關系稱為結構。數(shù)據(jù)結構一般包括以下三個方面內容：數(shù)據(jù)結構一般包括以下三個方面內容：（1）數(shù)據(jù)元素之間的邏輯關系，也稱數(shù)據(jù)的）數(shù)據(jù)元素之間的邏輯關系，也稱數(shù)據(jù)的邏輯結構。邏輯結構。（2）數(shù)據(jù)元素及其關系在計算機存儲器內的）數(shù)據(jù)元素及其關系在計算機存儲器內的表示，稱為數(shù)據(jù)的存儲結構。表示，稱為數(shù)據(jù)的存儲結構。（3）數(shù)據(jù)的運算，即對數(shù)據(jù)施加的操作。）數(shù)據(jù)的運算，即對數(shù)據(jù)施加的操作。返回到本節(jié)目錄1.1.1基本概念及術語基本概念及術

5、語數(shù)據(jù)結構定義：按某種邏輯關系組織起來的一批數(shù)據(jù)，數(shù)據(jù)結構定義：按某種邏輯關系組織起來的一批數(shù)據(jù)，按一定的映像方式把它存放在計算機存儲器中，并按一定的映像方式把它存放在計算機存儲器中，并在這些數(shù)據(jù)上定義了一個運算的集合，就叫做數(shù)據(jù)在這些數(shù)據(jù)上定義了一個運算的集合，就叫做數(shù)據(jù)結構。結構。簡言之，數(shù)據(jù)結構簡言之，數(shù)據(jù)結構=邏輯結構邏輯結構+存儲結構存儲結構+運算集合運算集合。4數(shù)據(jù)類型數(shù)據(jù)類型(DataType)數(shù)據(jù)類型是一組性質相同的值集合以及定義在這個值數(shù)據(jù)類型是一組性質相同的值集合以及定義在這個值集合上的一組操作的總稱。集合上的一組操作的總稱。如在高級語言中，整型類型的取值范圍為：如在高級語

6、言中，整型類型的取值范圍為：-32768+32767，運算符集合為加、減、乘、除、取模，運算符集合為加、減、乘、除、取模，即即+、-、*、/、%。返回到本節(jié)目錄1.1.1基本概念及術語基本概念及術語5數(shù)據(jù)數(shù)據(jù)類型型(DataType)高高級語言中的數(shù)據(jù)言中的數(shù)據(jù)類型分型分為兩大兩大類：（1）原子）原子類型型其其值是是不可分解不可分解的的。如。如C語言中的言中的標準準類型型（整型、（整型、實型、字符型）。型、字符型）。（2）結構構類型型其其值是由若干成分按某種是由若干成分按某種結構構組成的，因此是成的，因此是可以分解的。如可以分解的。如C語言中言中的的的構造的構造類型（型（結構體、共用體、枚構體

7、、共用體、枚舉等等類型）。型）。返回到本節(jié)目錄1.1.1基本概念及術語基本概念及術語1.1.2數(shù)據(jù)的邏輯結構數(shù)據(jù)的邏輯結構1定義定義數(shù)據(jù)的邏輯結構是指數(shù)據(jù)元素之間邏輯關系描數(shù)據(jù)的邏輯結構是指數(shù)據(jù)元素之間邏輯關系描述?？梢杂靡粋€二元組表示，其形式化描述述。可以用一個二元組表示，其形式化描述為：為：Data_Structure=（D，R）其中其中D是數(shù)據(jù)元素的有限集合，是數(shù)據(jù)元素的有限集合，R是是D上關系的上關系的有限集合。數(shù)據(jù)的邏輯結構是從邏輯關系上有限集合。數(shù)據(jù)的邏輯結構是從邏輯關系上描述數(shù)據(jù)，與數(shù)據(jù)的存儲無關，是獨立于計描述數(shù)據(jù)，與數(shù)據(jù)的存儲無關，是獨立于計算機的。算機的。返回到本節(jié)目錄2數(shù)

8、據(jù)的邏輯結構的分類數(shù)據(jù)的邏輯結構的分類根據(jù)數(shù)據(jù)元素之間的邏輯關系的不同特性，分根據(jù)數(shù)據(jù)元素之間的邏輯關系的不同特性，分為下列四類基本結構，如圖為下列四類基本結構，如圖1-1所示。所示。（a）集合結構）集合結構（b）線性結構）線性結構（c）樹型結構）樹型結構（d）圖形結構）圖形結構圖圖1-1數(shù)據(jù)結構的四種基本邏輯結構數(shù)據(jù)結構的四種基本邏輯結構返回到本節(jié)目錄1.1.2數(shù)據(jù)的邏輯結構數(shù)據(jù)的邏輯結構（1）集合）集合結構中的數(shù)據(jù)元素之間除了結構中的數(shù)據(jù)元素之間除了“同屬于一個集合同屬于一個集合”的關系外，別無其他關系，這是一種最簡的關系外，別無其他關系，這是一種最簡單的數(shù)據(jù)結構。單的數(shù)據(jù)結構。（2）線性

9、結構）線性結構結構中的數(shù)據(jù)元素之間存在著結構中的數(shù)據(jù)元素之間存在著“一對一一對一”的關的關系。系?！纠?.1】學籍檔案管理學籍檔案管理假設一個學籍檔案管理系統(tǒng)應包含如表假設一個學籍檔案管理系統(tǒng)應包含如表1-1所所示的學生信息。示的學生信息。返回到本節(jié)目錄1.1.2數(shù)據(jù)的邏輯結構數(shù)據(jù)的邏輯結構特點：特點：表中的每一行是一個數(shù)據(jù)元素（或記錄、結點），它表中的每一行是一個數(shù)據(jù)元素（或記錄、結點），它由學號、姓名、性別及出生年月等數(shù)據(jù)項組成。由學號、姓名、性別及出生年月等數(shù)據(jù)項組成。表中數(shù)據(jù)元素之間是一種先后關系，對于表中任一結表中數(shù)據(jù)元素之間是一種先后關系，對于表中任一結點，與它相鄰且在它前面的結

10、點（稱為直接前驅）點，與它相鄰且在它前面的結點（稱為直接前驅）最多只有一個；與表中任一結點相鄰且在其后的結最多只有一個；與表中任一結點相鄰且在其后的結點（稱為直接后繼）也最多只有一個。我們將這種點（稱為直接后繼）也最多只有一個。我們將這種關系稱為關系稱為“線性結構線性結構”。返回到本節(jié)目錄1.1.2數(shù)據(jù)的邏輯結構數(shù)據(jù)的邏輯結構（3）樹型結構）樹型結構結構中的數(shù)據(jù)元素之間存在著結構中的數(shù)據(jù)元素之間存在著“一對多一對多”的關的關系。系。【例例1.2】人機對弈人機對弈人與計算機進行對弈的部分圖如圖人與計算機進行對弈的部分圖如圖1-2為所示。為所示。圖圖1-2人機對弈圖人機對弈圖返回到本節(jié)目錄1.1.

11、2數(shù)據(jù)的邏輯結構數(shù)據(jù)的邏輯結構特點：特點：圖中將每一個棋盤看作一個數(shù)據(jù)元素，則數(shù)據(jù)圖中將每一個棋盤看作一個數(shù)據(jù)元素，則數(shù)據(jù)元素之間的關系要比表元素之間的關系要比表1-1要復雜許多。要復雜許多。圖中數(shù)據(jù)元素之間是一對多關系，即一個數(shù)據(jù)圖中數(shù)據(jù)元素之間是一對多關系，即一個數(shù)據(jù)元素向上和一個數(shù)據(jù)元素相連（稱為雙親結元素向上和一個數(shù)據(jù)元素相連（稱為雙親結點），向下和多個數(shù)據(jù)元素相連（稱為孩子點），向下和多個數(shù)據(jù)元素相連（稱為孩子結點）。我們將這種關系稱為結點）。我們將這種關系稱為“樹型結構樹型結構”。4）圖形結構或網(wǎng)狀結構）圖形結構或網(wǎng)狀結構結構中的任意數(shù)據(jù)元素之間都可以有關系，元結構中的任意數(shù)據(jù)元素

12、之間都可以有關系，元素之間存在著素之間存在著“多對多多對多”的關系。的關系。返回到本節(jié)目錄1.1.2數(shù)據(jù)的邏輯結構數(shù)據(jù)的邏輯結構（【例例1.3】制定教學制定教學計劃劃在制定教學在制定教學計劃劃時，需要考，需要考慮各各門課程的開程的開設順序。有些序。有些課程需要程需要先先導先修先修課程，有些程，有些課程程則不需要，而有些不需要，而有些課程又是其他程又是其他課程的程的先先導先修先修課程。比如，程。比如，計算機算機專業(yè)課程的開程的開設情況如表情況如表1-2所示。所示。返回到本節(jié)目錄1.1.2數(shù)據(jù)的邏輯結構數(shù)據(jù)的邏輯結構教學計劃的關系圖如圖教學計劃的關系圖如圖1-3所示。所示。圖圖1-3教學計劃關系圖

13、教學計劃關系圖特點：特點：圖中數(shù)據(jù)元素存在著多對多的任意關系。一個圖中數(shù)據(jù)元素存在著多對多的任意關系。一個結點可能有多個直接前驅和直接后繼。結點可能有多個直接前驅和直接后繼。返回到本節(jié)目錄1.1.2數(shù)據(jù)的邏輯結構數(shù)據(jù)的邏輯結構1.1.3數(shù)據(jù)的存儲結構數(shù)據(jù)的存儲結構數(shù)據(jù)在計算機中的存儲表示稱為數(shù)據(jù)的存儲結數(shù)據(jù)在計算機中的存儲表示稱為數(shù)據(jù)的存儲結構，也稱為物理結構。數(shù)據(jù)的存儲結構是邏構，也稱為物理結構。數(shù)據(jù)的存儲結構是邏輯結構在計算機存儲器中的實現(xiàn)。本書將介輯結構在計算機存儲器中的實現(xiàn)。本書將介紹常用的兩種基本的存儲結構：順序存儲結紹常用的兩種基本的存儲結構：順序存儲結構和鏈式存儲結構。構和鏈式存

14、儲結構。數(shù)據(jù)的邏輯結構和存儲結構的關系是：存儲結數(shù)據(jù)的邏輯結構和存儲結構的關系是：存儲結構是邏輯關系的映像與元素本身映像，是數(shù)構是邏輯關系的映像與元素本身映像，是數(shù)據(jù)結構的實現(xiàn)；邏輯結構是數(shù)據(jù)結構的抽象。據(jù)結構的實現(xiàn)；邏輯結構是數(shù)據(jù)結構的抽象。返回到本節(jié)目錄1.順序存儲結構順序存儲結構順序存儲結構：借助元素在存儲器中的相對位順序存儲結構：借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素間的邏輯關系。置來表示數(shù)據(jù)元素間的邏輯關系?！纠?.4】對于表對于表1-1提出的學生信息登記表提出的學生信息登記表進行存儲，假定每個元素占用進行存儲，假定每個元素占用50個存儲單元，個存儲單元，數(shù)據(jù)從數(shù)據(jù)從1000號

15、單元開始由低地址向高地址號單元開始由低地址向高地址存放，對應的順序存儲結構如表存放，對應的順序存儲結構如表1-3所示。所示。返回到本節(jié)目錄1.1.3數(shù)據(jù)的存儲結構數(shù)據(jù)的存儲結構順序存儲結構的主要特點：順序存儲結構的主要特點：v可實現(xiàn)對各數(shù)據(jù)元素的隨機訪問。這是因為可實現(xiàn)對各數(shù)據(jù)元素的隨機訪問。這是因為只要知道存儲的首地址以及每個數(shù)據(jù)元素所只要知道存儲的首地址以及每個數(shù)據(jù)元素所占的存儲單元，就可以計算出各數(shù)據(jù)元素的占的存儲單元，就可以計算出各數(shù)據(jù)元素的存儲地址。存儲地址。v不利于修改，在對數(shù)據(jù)元素進行插入、刪除不利于修改，在對數(shù)據(jù)元素進行插入、刪除運算時可能要移動一系列的數(shù)據(jù)元素。運算時可能要移

16、動一系列的數(shù)據(jù)元素。返回到本節(jié)目錄1.1.3數(shù)據(jù)的存儲結構數(shù)據(jù)的存儲結構2.鏈式存儲結構鏈式存儲結構鏈式存儲結構：借助指示元素存儲地址的指針鏈式存儲結構：借助指示元素存儲地址的指針表示數(shù)據(jù)元素間的邏輯關系。表示數(shù)據(jù)元素間的邏輯關系?！纠?.5】對于表對于表1-1學生信息登記表進行鏈學生信息登記表進行鏈式存儲時，在每個數(shù)據(jù)元素后方附加一個指式存儲時，在每個數(shù)據(jù)元素后方附加一個指向向“下一個結點地址下一個結點地址”的指針字段，用于存的指針字段，用于存放后繼數(shù)據(jù)元素的存儲地址，每個數(shù)據(jù)元素放后繼數(shù)據(jù)元素的存儲地址，每個數(shù)據(jù)元素的地址是隨機的，可以不連續(xù)。對應的鏈式的地址是隨機的，可以不連續(xù)。對應的

17、鏈式存儲結構見表存儲結構見表1-4所示。所示。返回到本節(jié)目錄1.1.3數(shù)據(jù)的存儲結構數(shù)據(jù)的存儲結構鏈式存儲結構的主要特點：鏈式存儲結構的主要特點：v利于修改，在對數(shù)據(jù)元素進行插入、刪除運利于修改，在對數(shù)據(jù)元素進行插入、刪除運算時，僅需修改數(shù)據(jù)元素的指針字段值，而算時，僅需修改數(shù)據(jù)元素的指針字段值，而不必移動數(shù)據(jù)元素。不必移動數(shù)據(jù)元素。v由于邏輯上相鄰的數(shù)據(jù)元素在存儲位置中不由于邏輯上相鄰的數(shù)據(jù)元素在存儲位置中不一定相鄰，因此，鏈式存儲結構不能對數(shù)據(jù)一定相鄰，因此，鏈式存儲結構不能對數(shù)據(jù)元素進行隨機訪問。元素進行隨機訪問。返回到本節(jié)目錄1.1.3數(shù)據(jù)的存儲結構數(shù)據(jù)的存儲結構1.1.4抽象數(shù)據(jù)類型

18、抽象數(shù)據(jù)類型1抽象數(shù)據(jù)類型的定義抽象數(shù)據(jù)類型的定義抽象數(shù)據(jù)類型（抽象數(shù)據(jù)類型（AbstractDataType，簡，簡稱稱ADT）是指一個數(shù)學模型以及定義在該模）是指一個數(shù)學模型以及定義在該模型上的一組操作。型上的一組操作。2抽象數(shù)據(jù)類型的表示抽象數(shù)據(jù)類型的表示抽象數(shù)據(jù)類型實際上就是對該數(shù)據(jù)結構的定義。抽象數(shù)據(jù)類型實際上就是對該數(shù)據(jù)結構的定義。因為它定義了一個數(shù)據(jù)的邏輯結構以及在此因為它定義了一個數(shù)據(jù)的邏輯結構以及在此結構上的一組算法?？梢杂靡粋€三元組表示：結構上的一組算法?？梢杂靡粋€三元組表示：ADT=（，）（，）其中，其中，D是數(shù)據(jù)對象，是數(shù)據(jù)對象，S是是D上的關系集，上的關系集，P是是對

19、對D的基本操作集。的基本操作集。返回到本節(jié)目錄抽象數(shù)據(jù)類型通常是指由用戶定義，用以表示應用問抽象數(shù)據(jù)類型通常是指由用戶定義，用以表示應用問題的數(shù)據(jù)類型，抽象數(shù)據(jù)類型由基本的數(shù)據(jù)類型組題的數(shù)據(jù)類型，抽象數(shù)據(jù)類型由基本的數(shù)據(jù)類型組成，并包括一組相關的服務（或稱操作）。成，并包括一組相關的服務（或稱操作）。抽象數(shù)據(jù)類型有些類似于抽象數(shù)據(jù)類型有些類似于pascal語言中的記錄語言中的記錄（record）類型和）類型和c語言中的構造（語言中的構造（struct）類型，）類型，但它增加了相關的服務。但它增加了相關的服務。3ADT的兩個重要特征的兩個重要特征（1）數(shù)據(jù)抽象用）數(shù)據(jù)抽象用ADT描述程序處理的實

20、體時，強調描述程序處理的實體時，強調的是其本質的特征、其所能完成的功能以及它和外的是其本質的特征、其所能完成的功能以及它和外部用戶的接口（即外界使用它的方法）。部用戶的接口（即外界使用它的方法）。（2）數(shù)據(jù)封裝將實體的外部特性和其內部實現(xiàn)細節(jié)分）數(shù)據(jù)封裝將實體的外部特性和其內部實現(xiàn)細節(jié)分離，并且對外部用戶隱藏其內部實現(xiàn)細節(jié)。離，并且對外部用戶隱藏其內部實現(xiàn)細節(jié)。返回到本節(jié)目錄1.1.4抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型1.2算法和算法分析算法和算法分析v1.2.1算法的概念算法的概念v1.2.2算法分析算法分析v1.2.3相關相關C語言知識回顧語言知識回顧返回到總目錄返回到總目錄返回到總目錄返回到總目錄

21、1.2.1算法的概念算法的概念1算法的定義算法的定義瑞士著名的計算機科學家瑞士著名的計算機科學家N.Wirth所提出的著所提出的著名公式名公式“程序程序=算法算法+數(shù)據(jù)結構數(shù)據(jù)結構”，所謂算，所謂算法，就是為解決特定問題而采取的步驟和方法，就是為解決特定問題而采取的步驟和方法。法。2算法的特性算法的特性一個算法應該具有下列特性：一個算法應該具有下列特性：（1）有窮性：一個算法必須（對任何合法的）有窮性：一個算法必須（對任何合法的輸入值）在執(zhí)行有限步之后結束。輸入值）在執(zhí)行有限步之后結束。（2）確定性：算法中的每一條指令必須有確）確定性：算法中的每一條指令必須有確切的含義，不會產(chǎn)生二義性。切的含

22、義，不會產(chǎn)生二義性。返回到本節(jié)目錄（3）可行性：算法中描述的操作都可以通過）可行性：算法中描述的操作都可以通過執(zhí)行有限次基本操作來實現(xiàn)。執(zhí)行有限次基本操作來實現(xiàn)。（4）輸入：一個算法有零個或多個輸入。）輸入：一個算法有零個或多個輸入。（5）輸出：一個算法必有一個或多個輸出。）輸出：一個算法必有一個或多個輸出。3算法的評價算法的評價要設計一個好的算法通常需要考慮以下幾方面要設計一個好的算法通常需要考慮以下幾方面的要求：的要求：（1）正確性：要求算法能夠正確地執(zhí)行預先）正確性：要求算法能夠正確地執(zhí)行預先規(guī)定的功能，并達到所期望的性能要求。規(guī)定的功能，并達到所期望的性能要求。（2）可讀性：為了便于理

23、解、測試和修改算）可讀性：為了便于理解、測試和修改算法，算法應該具有良好的可讀性。法，算法應該具有良好的可讀性。返回到本節(jié)目錄1.2.1算法的概念算法的概念（3）健壯性：當輸入非法的數(shù)據(jù)時，算法應）健壯性：當輸入非法的數(shù)據(jù)時，算法應能恰當?shù)刈龀龇磻蜻M行相應處理，而不是能恰當?shù)刈龀龇磻蜻M行相應處理，而不是產(chǎn)生莫名奇妙的輸出結果。并且處理出錯的產(chǎn)生莫名奇妙的輸出結果。并且處理出錯的方法不應是中斷程序的執(zhí)行，而是返回一個方法不應是中斷程序的執(zhí)行，而是返回一個表示錯誤或錯誤性質的值，以便在更高的抽表示錯誤或錯誤性質的值，以便在更高的抽象層次上進行處理。象層次上進行處理。（4）高效性：對同一個問題，

24、執(zhí)行時間越短，）高效性：對同一個問題，執(zhí)行時間越短，算法的效率越高。算法的效率越高。（5）低存儲量：完成相同的功能，執(zhí)行算法）低存儲量：完成相同的功能，執(zhí)行算法所占用的存儲空間應盡可能的少。所占用的存儲空間應盡可能的少。返回到本節(jié)目錄1.2.1算法的概念算法的概念4算法的描述算法的描述為了表示一個算法，可以用多種不同的方法，為了表示一個算法，可以用多種不同的方法，常用的有自然語言、傳統(tǒng)流程圖、結構化流常用的有自然語言、傳統(tǒng)流程圖、結構化流程圖、程圖、N-S流程圖等表示。本書采用流程圖等表示。本書采用C的描的描述語言實現(xiàn)對各種數(shù)據(jù)結構及算法的操作描述語言實現(xiàn)對各種數(shù)據(jù)結構及算法的操作描述，算法是

25、以函數(shù)形式描述，描述如下：述，算法是以函數(shù)形式描述，描述如下：類類型型標識標識符符函數(shù)名函數(shù)名(形式參數(shù)表形式參數(shù)表)/*算法算法說說明明*/語語句序列句序列返回到本節(jié)目錄1.2.1算法的概念算法的概念1.2.2算法分析算法分析在算法滿足正確性的前提下，如何評價不同算法的優(yōu)在算法滿足正確性的前提下，如何評價不同算法的優(yōu)劣呢？通常主要考慮算法的時間復雜度和空間復雜劣呢？通常主要考慮算法的時間復雜度和空間復雜度這兩方面。一般情況下，鑒于運算空間（內存）度這兩方面。一般情況下，鑒于運算空間（內存）較為充足，所以把算法的時間復雜度作為重點分析。較為充足，所以把算法的時間復雜度作為重點分析。1.時間復雜

26、度（時間復雜度（TimeComplexity）一個算法所需的運算時間通常與所解決問題的規(guī)模大一個算法所需的運算時間通常與所解決問題的規(guī)模大小有關。問題規(guī)模是一個和輸入有關的量，用小有關。問題規(guī)模是一個和輸入有關的量，用n表表示問題規(guī)模的量，把算法運行所需的時間示問題規(guī)模的量，把算法運行所需的時間T表示為表示為n的函數(shù)，記為的函數(shù)，記為T(n)。不同的。不同的T(n)算法，當算法，當n增長時，增長時，運算時間增長的快慢很不相同。一個算法所需的執(zhí)運算時間增長的快慢很不相同。一個算法所需的執(zhí)行時間就是該算法中所有語句執(zhí)行次數(shù)之和。當行時間就是該算法中所有語句執(zhí)行次數(shù)之和。當n逐逐漸增大時漸增大時T(

27、n)的極限情況，一般簡稱為時間復雜度。的極限情況，一般簡稱為時間復雜度。返回到本節(jié)目錄當討論一個程序的運行時間時，注重的不是當討論一個程序的運行時間時，注重的不是T(n)的具體值，而是它的增長率。的具體值，而是它的增長率。T(n)的的增長率與算法中數(shù)據(jù)的輸入規(guī)模緊密相關，增長率與算法中數(shù)據(jù)的輸入規(guī)模緊密相關，而數(shù)據(jù)輸入規(guī)模往往用算法中的某個變量的而數(shù)據(jù)輸入規(guī)模往往用算法中的某個變量的函數(shù)來表示，通常是函數(shù)來表示，通常是f(n)。隨著數(shù)據(jù)輸入規(guī)。隨著數(shù)據(jù)輸入規(guī)模的增大，模的增大，f(n)的增長率與的增長率與T(n)的增長率的增長率相近，因此相近，因此T(n)同同f(n)在數(shù)量級上是一致在數(shù)量級上

28、是一致的。記作：的。記作：T(n)=O(f(n)其中，大寫字母其中，大寫字母O為為Order(數(shù)量級數(shù)量級)的字頭，的字頭，f(n)為函數(shù)形式，如為函數(shù)形式，如T(n)=O(n2)。返回到本節(jié)目錄1.2.2算法分析算法分析注意，當注意，當T(n)為多多項式式時，可只取其最高次，可只取其最高次冪項并省略其系數(shù)，其它的次并省略其系數(shù)，其它的次冪項及系數(shù)均略及系數(shù)均略去不寫。一般地，去不寫。一般地，對于足于足夠大的大的n，常用的，常用的時間復復雜性存在以下性存在以下順序：序：O(1)O(log2n)O(n)O(nlog2n)O(n2)O(n3)O(2n)算法算法時間復復雜度的數(shù)量度的數(shù)量級越大，表示

29、越大，表示該算法的算法的效率越低，反之越高。例如效率越低，反之越高。例如O(1)為常數(shù)數(shù)常數(shù)數(shù)量量級,，即算法的即算法的時間復復雜性與性與輸入入規(guī)模模n無無關。關。返回到本節(jié)目錄1.2.2算法分析算法分析【例例1.6】分析以下算法的時間復雜度。分析以下算法的時間復雜度。x=0;y=0;for(k=1;k=n;k+)x+;（1）執(zhí)行）執(zhí)行n次次for(i=1;i=n;i+)for(j=1;j=n;j+)y+;（2）執(zhí)行）執(zhí)行n2次次解：解：T(n)=n+n2T(n)=O(n2)上述算法中的基本運算是語句（上述算法中的基本運算是語句（2），其執(zhí)行頻率為），其執(zhí)行頻率為n2。則則T(n)=n2=O(

30、n2)返回到本節(jié)目錄1.2.2算法分析算法分析【例例1.7】分析以下算法的時間復雜度。分析以下算法的時間復雜度。i=1;while(i=n)i=2*i;(1)執(zhí)行執(zhí)行f(n)次次解：設語句（解：設語句（1）執(zhí)行次數(shù)是）執(zhí)行次數(shù)是f(n)，則，則2f(n)n得到得到T(n)=O(log2n)返回到本節(jié)目錄1.2.2算法分析算法分析【例例1.8】求兩個矩陣相乘的函數(shù)的時間復雜度。求兩個矩陣相乘的函數(shù)的時間復雜度。voidmult(inta,intb,intc)/*以二維數(shù)組存儲矩陣元素，以二維數(shù)組存儲矩陣元素，c為為a和和b的乘積的乘積*/for(i=1;i=n;+i)(1)執(zhí)行執(zhí)行n次次for(

31、j=1;j=n;+j)(2)執(zhí)行執(zhí)行n2次次ci,j=0;for(k=1;k成員名成員名等價于：等價于：(*指針名指針名).成員名成員名等價于：結構體變量名等價于：結構體變量名.成員名成員名在本書中，在程序內大量使用結構體類型的指在本書中，在程序內大量使用結構體類型的指針，所以大都采用第一種寫法。針，所以大都采用第一種寫法。返回到本節(jié)目錄1.2.3相關相關C語言知識回顧語言知識回顧（4）用）用typedef定義類型定義類型除了可以直接使用除了可以直接使用C提供的標準類型名和自己提供的標準類型名和自己聲明的結構體類型外，還可以用聲明的結構體類型外，還可以用typedef聲聲明新的類型名來代替已有

32、的類型名。其基本明新的類型名來代替已有的類型名。其基本定義格式如下：定義格式如下：【格式格式】typedef原類型名原類型名新類型名新類型名;其中，其中，typedef為關鍵字，表示重定義。原類為關鍵字，表示重定義。原類型名是型名是C語言提供的任語言提供的任意意一種數(shù)據(jù)類型，可一種數(shù)據(jù)類型，可以是簡單數(shù)據(jù)類型，也可以是構造數(shù)據(jù)類型。以是簡單數(shù)據(jù)類型，也可以是構造數(shù)據(jù)類型。新類型名為原類型名的一個別名。使用新類新類型名為原類型名的一個別名。使用新類型名就像使用原類型名那樣定義變量。型名就像使用原類型名那樣定義變量。返回到本節(jié)目錄1.2.3相關相關C語言知識回顧語言知識回顧2動態(tài)存儲分配函數(shù)動態(tài)存

33、儲分配函數(shù)C語言提供了動態(tài)分配函數(shù)來實現(xiàn)動態(tài)存儲分配。最常語言提供了動態(tài)分配函數(shù)來實現(xiàn)動態(tài)存儲分配。最常用的動態(tài)存儲分配函數(shù)有以下兩個。用的動態(tài)存儲分配函數(shù)有以下兩個。（1）分配內存空間函數(shù)）分配內存空間函數(shù)malloc()【格式格式】(類型名類型名*)malloc(要分配的內存字節(jié)數(shù)要分配的內存字節(jié)數(shù)size)【功能功能】在內存中分配一個長度為在內存中分配一個長度為size的連續(xù)存儲空的連續(xù)存儲空間，返回值是新分配存儲空間的首地址，若內存不間，返回值是新分配存儲空間的首地址，若內存不足，則返回足，則返回NULL。其中，類型名表示把該存儲空。其中，類型名表示把該存儲空間用于何種數(shù)據(jù)類型。（類型

34、名間用于何種數(shù)據(jù)類型。（類型名*）表示把）表示把malloc函數(shù)返回值強制轉換為該類型指針。函數(shù)返回值強制轉換為該類型指針。返回到本節(jié)目錄1.2.3相關相關C語言知識回顧語言知識回顧（2）釋放內存空間函數(shù)）釋放內存空間函數(shù)free()【格式格式】free(指向要釋放單元的指針名指向要釋放單元的指針名)【功能功能】釋放該指針所指的一塊存儲空間，該釋放該指針所指的一塊存儲空間，該空間系統(tǒng)可另作它用。注意這個指針所指的空間系統(tǒng)可另作它用。注意這個指針所指的空間必須是由空間必須是由malloc()函數(shù)和函數(shù)和calloc()函函數(shù)分配的才行。數(shù)分配的才行。free函數(shù)無返回值。例如：函數(shù)無返回值。例如

35、：int*pt;pt=(int*)malloc(sizeof(int);free(pt);程序段表示釋放程序段表示釋放pt指向的存儲空間。指向的存儲空間。返回到本節(jié)目錄1.2.3相關相關C語言知識回顧語言知識回顧3函數(shù)的定義與調用函數(shù)的定義與調用在本書中，絕大多數(shù)的算法都是編寫成在本書中，絕大多數(shù)的算法都是編寫成C語言的函數(shù)，語言的函數(shù)，這些函數(shù)需要通過編寫相應的主函數(shù)才能被執(zhí)行。這些函數(shù)需要通過編寫相應的主函數(shù)才能被執(zhí)行。（1）函數(shù)的定義）函數(shù)的定義函數(shù)的定義如下：函數(shù)的定義如下：【格式格式】函數(shù)函數(shù)類類型型函數(shù)名（形參表函數(shù)名（形參表）內部內部變變量定量定義義函數(shù)主體函數(shù)主體語語句句返回返

36、回語語句句返回到本節(jié)目錄1.2.3相關相關C語言知識回顧語言知識回顧（2）函數(shù)的調用）函數(shù)的調用【格式格式】函數(shù)類型函數(shù)類型函數(shù)名（實參表）函數(shù)名（實參表）;【說明說明】1實參表中各參數(shù)應與形參表中各參數(shù)類型實參表中各參數(shù)應與形參表中各參數(shù)類型及個數(shù)相符。及個數(shù)相符。2在調用函數(shù)時，表達式應與該函數(shù)的類型在調用函數(shù)時，表達式應與該函數(shù)的類型相符，如果該函數(shù)有返回值時，在調用時要相符，如果該函數(shù)有返回值時，在調用時要將該函數(shù)的返回值賦給相同類型的變量。將該函數(shù)的返回值賦給相同類型的變量。返回到本節(jié)目錄1.2.3相關相關C語言知識回顧語言知識回顧4TurboC2.0中的漢字顯示中的漢字顯示在在Tu

37、rboC2.0中，如果想輸入和顯示漢字，中，如果想輸入和顯示漢字，需要使用需要使用UCDOS漢字系統(tǒng)。但現(xiàn)在的漢字系統(tǒng)。但現(xiàn)在的Windows操作系統(tǒng)不支持操作系統(tǒng)不支持UCDOS漢字系漢字系統(tǒng)的統(tǒng)的16位顯示。下面介紹一種能在位顯示。下面介紹一種能在WindowsXP系統(tǒng)環(huán)境下，在系統(tǒng)環(huán)境下，在TurboC2.0中使用中使用UCDOS的漢字系統(tǒng)的方法。的漢字系統(tǒng)的方法。返回到本節(jié)目錄1.2.3相關相關C語言知識回顧語言知識回顧（1）將）將UCDOS的核心文件進行兼容性設置的核心文件進行兼容性設置（有的機器可省略這步，直接執(zhí)行（有的機器可省略這步，直接執(zhí)行（2）。）。點點“開始開始”菜單菜單-

38、“所有程序所有程序”-“附件附件”-“程序兼容性向導程序兼容性向導”-“我想手動定位程序我想手動定位程序”-“瀏覽瀏覽”-win98-256色，色，640X480-程序工程序工作正確嗎？選作正確嗎？選“是，設置此程序為一直使用是，設置此程序為一直使用兼容性設置。兼容性設置?！蓖瓿伞Ｓ械耐瓿?。有的UCDOS版本的版本的核心文件是核心文件是knlvga.exe，也要照此進行兼，也要照此進行兼容性設置。容性設置。返回到本節(jié)目錄1.2.3相關相關C語言知識回顧語言知識回顧（2）運行）運行UCDOS系統(tǒng)文件的方法。系統(tǒng)文件的方法。進入到命令提示符（進入到命令提示符（MS-DOS狀態(tài)）（狀態(tài)）（“開開始始

39、”-“程序程序”-“附件附件”-“命令提示符命令提示符”）切換到）切換到UCDOS目錄。（帶下劃線文字目錄。（帶下劃線文字為輸入的命令信息，為輸入的命令信息，“”表示回車鍵。假表示回車鍵。假設設UCDOS文件夾在文件夾在C盤根目錄內，可輸入盤根目錄內，可輸入如下命令：）如下命令：）C:DocumentsandSettingscd（回到（回到C盤根目錄下）盤根目錄下）C:cdUcdos（進入（進入UCDOS的目錄）的目錄）返回到本節(jié)目錄1.2.3相關相關C語言知識回顧語言知識回顧這時不要運行這時不要運行UCDOS.BAT，分別一項一項，分別一項一項命令運行。如：命令運行。如：C:UDOS C:U

40、DOS C:UDOS C:UDOS C:UDOS（五筆輸入，如不（五筆輸入，如不用五筆可省略此步）用五筆可省略此步）（注：可直接輸入命令名，如輸入（注：可直接輸入命令名，如輸入“rd16”，省略擴展名，省略擴展名“.com”）返回到本節(jié)目錄1.2.3相關相關C語言知識回顧語言知識回顧就可以順利進入就可以順利進入ucdos。然后，退出。然后，退出UCDOS目錄，再進入目錄，再進入tc目錄運行目錄運行tc.exe文件就可以文件就可以在在TurboC2.0中順利的輸入和顯示漢字了。中順利的輸入和顯示漢字了。如：如：C:UDOScd C:cdtc（假定（假定TurboC2.0的文的文件夾名稱為件夾名稱

41、為TC）C:TCtc.exe(可直接輸入可直接輸入tc 即可即可)即可進行即可進行TurboC2.0輸入并運行輸入并運行C語言源程語言源程序了。序了。返回到本節(jié)目錄1.2.3相關相關C語言知識回顧語言知識回顧（3）常用的）常用的TurboC2.0快捷鍵快捷鍵Alt+F：文件菜單：文件菜單Load打開文件打開文件Save保存保存Writeto另存為另存為Quit退出退出Alt+R：運行菜單：運行菜單Run（或（或Ctrl+F9）運行程序運行程序UserScreen(或或Alt+F5)查看運行結果查看運行結果Alt+E：編輯（顯示光標，有時調試有錯時可：編輯（顯示光標，有時調試有錯時可將光標重新顯

42、示在編輯區(qū)）將光標重新顯示在編輯區(qū)）F9：編譯系統(tǒng)查錯：編譯系統(tǒng)查錯返回到本節(jié)目錄1.2.3相關相關C語言知識回顧語言知識回顧（4）更改漢字輸入法）更改漢字輸入法Alt+F1區(qū)位區(qū)位Alt+F2全拼全拼Alt+F3雙拼雙拼Alt+F5五筆（必須在五筆（必須在UCDOS中輸入中輸入wb命命令才能用此項）令才能用此項）Alt+F6英文英文單次按右單次按右shift鍵鍵可顯示或隱藏中文輸入法可顯示或隱藏中文輸入法返回到本節(jié)目錄1.2.3相關相關C語言知識回顧語言知識回顧1.3本章小結本章小結本章主要介紹了有關數(shù)據(jù)結構的以下幾方面：本章主要介紹了有關數(shù)據(jù)結構的以下幾方面：（1）數(shù)據(jù)結構主要研究數(shù)據(jù)的邏

43、輯結構、存）數(shù)據(jù)結構主要研究數(shù)據(jù)的邏輯結構、存儲結構和運算方法。儲結構和運算方法。（2）數(shù)據(jù)的邏輯結構包括：集合、線性結構、）數(shù)據(jù)的邏輯結構包括：集合、線性結構、樹型結構、圖形結構四種基本類型。樹型結構、圖形結構四種基本類型。（3）數(shù)據(jù)的存儲結構包括：順序存儲結構和）數(shù)據(jù)的存儲結構包括：順序存儲結構和鏈式存儲結構。鏈式存儲結構。（4）算法是對特定問題求解步驟的一種描述，）算法是對特定問題求解步驟的一種描述，是指令的有限序列。算法具有：有窮性、確是指令的有限序列。算法具有：有窮性、確定性、正確性、輸入、輸出等特性。定性、正確性、輸入、輸出等特性。（5）算法的時間復雜度與空間復雜度。）算法的時間復

44、雜度與空間復雜度。返回到總目錄返回到總目錄返回到總目錄返回到總目錄 數(shù)據(jù)結構實用教程（C語言版）中國水利水電出版社第第2章章線性表線性表本章主要介紹下列內容本章主要介紹下列內容本章主要介紹下列內容本章主要介紹下列內容線性表的定義和基本操作線性表的定義和基本操作線性表的定義和基本操作線性表的定義和基本操作線性表的順序存儲結構線性表的順序存儲結構線性表的順序存儲結構線性表的順序存儲結構線性表的鏈式存儲結構線性表的鏈式存儲結構線性表的鏈式存儲結構線性表的鏈式存儲結構線性表的應用舉例線性表的應用舉例線性表的應用舉例線性表的應用舉例本章目錄本章目錄2.12.1線性表的基本概念線性表的基本概念線性表的基本

45、概念線性表的基本概念12.22.2順序表順序表順序表順序表22.32.3鏈表鏈表鏈表鏈表32.42.4線性表的應用舉例線性表的應用舉例線性表的應用舉例線性表的應用舉例42.52.5本章小結本章小結本章小結本章小結5結束2.1 2.1 線性表的基本概念線性表的基本概念v2.1.1線性表的定義線性表的定義v2.1.2線性表的基本操作線性表的基本操作返回到總目錄2.1.1 線性表的定義線性表的定義1.線性表的定義線性表的定義線性表是具有相同數(shù)據(jù)類型的線性表是具有相同數(shù)據(jù)類型的n（n=0）個）個數(shù)據(jù)元素的有限序列，通常記為：數(shù)據(jù)元素的有限序列，通常記為：（a1，a2，ai-1，ai，ai+1，an）其

46、中其中n為表長，當為表長，當n=0時稱為空表。時稱為空表。在線性表中相鄰元素之間存在著順序關系。如在線性表中相鄰元素之間存在著順序關系。如對于元素對于元素ai而言，而言，ai-1稱為稱為ai的直接前驅，的直接前驅，ai+1稱為稱為ai的直接后繼。的直接后繼。返回到本節(jié)目錄2.線性表的特點線性表的特點（1）有且僅有一個開始結點（）有且僅有一個開始結點（a1），它沒有），它沒有直接前驅；直接前驅；（2）有且僅有一個終端結點（）有且僅有一個終端結點（an），它沒有），它沒有直接后繼；直接后繼；（3）除了開始結點和終端結點以外，其余的）除了開始結點和終端結點以外，其余的結點都有且僅有一個直接前驅和一個

47、直接后結點都有且僅有一個直接前驅和一個直接后繼。繼。2.1.1 線性表的定義線性表的定義返回到本節(jié)目錄2.1.2 線性表的基本操作線性表的基本操作數(shù)據(jù)結構的運算是定義在邏輯結構層次上的，數(shù)據(jù)結構的運算是定義在邏輯結構層次上的，而運算的具體實現(xiàn)是建立在存儲結構上的。而運算的具體實現(xiàn)是建立在存儲結構上的。下面定義的線性表的基本操作僅是定義在邏下面定義的線性表的基本操作僅是定義在邏輯結構上的，每一個操作的具體實現(xiàn)只有在輯結構上的，每一個操作的具體實現(xiàn)只有在確定了線性表的存儲結構之后才能完成。確定了線性表的存儲結構之后才能完成。線性表的基本操作有：線性表的基本操作有：（1）初始化線性表）初始化線性表I

48、nitList(L)。其作用是建立一個空表其作用是建立一個空表L（即建立線性表的構（即建立線性表的構架，但不包含任何數(shù)據(jù)元素）。架，但不包含任何數(shù)據(jù)元素）。返回到本節(jié)目錄（2）求）求線性表的性表的長度度GetLength(L)。其作。其作用是返回用是返回線性表性表L的的長度（即所含數(shù)據(jù)元素度（即所含數(shù)據(jù)元素的個數(shù)）。的個數(shù)）。（3）求）求線性表中第性表中第i個元素個元素GetElem(L,i,x)。其作用是在其作用是在1iGetLength(L)返回成功，返回成功，并用并用x存存儲線性表性表L的第的第i個元素的個元素的值。（4）按）按值查找操作找操作Locate(L,x)。在。在線性表性表L查

49、找一個與找一個與給定定值x相等的數(shù)據(jù)元素，其作相等的數(shù)據(jù)元素，其作用是若存在一個或多個與用是若存在一個或多個與x相等的數(shù)據(jù)元素，相等的數(shù)據(jù)元素，則返回返回的的元素所在位置的最小元素所在位置的最小值或地址或地址值；否否則返回返回0或或NULL值。2.1.2 線性表的基本操作線性表的基本操作返回到本節(jié)目錄（5）插入操作）插入操作InsElem(L,i,x)。其作用是在線性表。其作用是在線性表L的的第第i個位置上插入一個值為個位置上插入一個值為x的新元素，使線性表的新元素，使線性表L由由（a1，a2，ai-1，ai，ai+1，an）變?yōu)椋ǎ┳優(yōu)椋╝1，a2，ai-1，x，ai，ai+1，an）。其中

50、）。其中1iGetLength(L)+1。（6）刪除操作）刪除操作DelElem(L,i,x)。其作用是刪除線性表。其作用是刪除線性表L的第的第i個位置的數(shù)據(jù)元素并用個位置的數(shù)據(jù)元素并用x將其存儲，使線性表將其存儲，使線性表L由由（a1，a2，ai-1，ai，ai+1，an）變?yōu)椋ǎ┳優(yōu)椋╝1，a2，ai-1，ai+1，an）。其中）。其中1iGetLength(L)。（7）輸出元素值）輸出元素值DispList(L)。其作用是依次掃描線性。其作用是依次掃描線性表表L，并輸出各元素的值。，并輸出各元素的值。2.1.2 線性表的基本操作線性表的基本操作返回到本節(jié)目錄2.2順序表順序表v2.2.1

51、順序表順序表v2.2.2順序表的基本操作實現(xiàn)順序表的基本操作實現(xiàn)返回到總目錄1.順序表的定義順序表的定義數(shù)據(jù)結構在內存中的表示通常有兩種形式，即順序存數(shù)據(jù)結構在內存中的表示通常有兩種形式，即順序存儲表示和鏈式存儲表示。線性表的順序存儲表示又儲表示和鏈式存儲表示。線性表的順序存儲表示又稱為順序表。線性表的順序存儲是指用一組地址連稱為順序表。線性表的順序存儲是指用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素，我們把續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素，我們把用這種存儲形式存儲的線性表稱為順序表。用這種存儲形式存儲的線性表稱為順序表。假設順序表假設順序表(a1，a2，ai-1，ai，ai+1，an

52、)，每，每個數(shù)據(jù)元素占用個數(shù)據(jù)元素占用d個存儲單元，則元素個存儲單元，則元素ai的存儲位置的存儲位置為：為：Loc(ai)=Loc(a1)+(i-1)d1in2.2.1順序表順序表返回到本節(jié)目錄其中，其中，Loc(a1)是順序表第一個元素是順序表第一個元素a1的存儲位置，的存儲位置，通稱為順序表的起始地址。順序存儲結構示意圖如通稱為順序表的起始地址。順序存儲結構示意圖如圖圖2-1所示。所示。順序表的存儲特點：順序表的存儲特點：（1）順序表的邏輯順序和物理順序是一致的。）順序表的邏輯順序和物理順序是一致的。（2）順序表中任意一個數(shù)據(jù)元素都可以隨機存取，所）順序表中任意一個數(shù)據(jù)元素都可以隨機存取，

53、所以順序表是一種隨機存取的存儲結構。以順序表是一種隨機存取的存儲結構。2.2.1順序表順序表返回到本節(jié)目錄2.順序表的類型定義順序表的類型定義#defineMAXLEN100/*定義常量定義常量MAXLEN為為100表示存表示存儲空間總量儲空間總量*/#defineOK/*定義常量定義常量OK為為1表示成功表示成功*/#defineERROR0/*定義常量定義常量ERROR為為0表示失敗表示失敗*/#defineOVER-1/*定義常量定義常量OVER為為-1表示結束表示結束*/typedefintElemType;/*定義定義ElemType為為int類型類型*/typedefstruct/

54、*順序表存儲類型順序表存儲類型*/ElemTypedataMAXLEN;/*存放線性表的數(shù)組存放線性表的數(shù)組*/intLength;/*Length是順序表的長度是順序表的長度*/SeqList;2.2.1順序表順序表返回到本節(jié)目錄2.2.2順序表的基本操作實現(xiàn)順序表的基本操作實現(xiàn)1順序表的初始化序表的初始化順序表的初始化即構造一個空序表的初始化即構造一個空順序表序表L，將表，將表L的的實際長度置度置0，算法描述，算法描述見算法算法2.1。算法算法2.1voidInitList(SeqList*L)L-Length=0;/*初初始始的的化化順序表序表為空空*/返回到本節(jié)目錄2順序表的建立順序表

55、的建立初始化順序表后向表中輸入初始化順序表后向表中輸入n個元素建立表個元素建立表L，算法描，算法描述見算法述見算法2.2。算法算法2.2voidCreateList(SeqList*L,intn)inti;printf(請輸入各個元素值：請輸入各個元素值：n);for(i=0;idatai);L-Length=i;2.2.2順序表的基本操作實現(xiàn)順序表的基本操作實現(xiàn)返回到本節(jié)目錄3求順序表的長度操作求順序表的長度操作返回順序表返回順序表L的的Length值，算法描述見算法值，算法描述見算法2.3。算法算法2.3intGetLength(SeqList*L)returnL-Length;4查找操作

56、查找操作順序表的查找分為按值與按序號查找，下面將分別介順序表的查找分為按值與按序號查找，下面將分別介紹這兩種方法的實現(xiàn)，讀者可根據(jù)具體的問題相應紹這兩種方法的實現(xiàn)，讀者可根據(jù)具體的問題相應選擇所需的查找方法。選擇所需的查找方法。2.2.2順序表的基本操作實現(xiàn)順序表的基本操作實現(xiàn)返回到本節(jié)目錄（1）按號查找）按號查找查找順序表中第查找順序表中第i個元素的值，在個元素的值，在i無效時返回出錯，有無效時返回出錯，有效時返回成功，并用效時返回成功，并用x存儲第存儲第i個元素的值，算法描述個元素的值，算法描述見算法見算法2.4。算法算法2.4intGetElem(SeqList*L,inti,ElemT

57、ype*x)if(iL-Length)returnERROR;else*x=L-datai-1;returnOK;2.2.2順序表的基本操作實現(xiàn)順序表的基本操作實現(xiàn)返回到本節(jié)目錄2）按值查找操作）按值查找操作順序表中的按值查找是指在順序表中查找與給定值順序表中的按值查找是指在順序表中查找與給定值x相等的數(shù)據(jù)元相等的數(shù)據(jù)元素的所在位置，算法描述見算法素的所在位置，算法描述見算法2.5。算法算法2.5intLocate(SeqList*L,ElemTypex)inti=0;while(iLength&L-datai!=x)i+;if(iL-Length)returnERROR;elsereturn

58、i+1;/*返回的是元素位置返回的是元素位置*/2.2.2順序表的基本操作實現(xiàn)順序表的基本操作實現(xiàn)返回到本節(jié)目錄2.2.2順序表的基本操作實現(xiàn)順序表的基本操作實現(xiàn)5插入操作插入操作線性表的插入是指在表的第線性表的插入是指在表的第i個位置上插入一個值為個位置上插入一個值為x的新元素，插入后使原表長增的新元素，插入后使原表長增1，原順序表如圖，原順序表如圖2-2所示。所示。返回到本節(jié)目錄5插入操作插入操作步驟如下：步驟如下：(1)將將anai之間的所有結點依次后移，為之間的所有結點依次后移，為新元素讓出第新元素讓出第i個位置，如圖個位置，如圖2-3所示。所示。返回到本節(jié)目錄5插入操作插入操作步驟如

59、下：步驟如下：(2)將新結點將新結點x插入到第插入到第i個位置，如圖個位置，如圖2-4所示。所示。(3)順序表的長度增順序表的長度增1，插入成功，并返回，算法描，插入成功，并返回，算法描述見算法述見算法2.6。返回到本節(jié)目錄5插入操作插入操作算法算法2.6intInsElem(SeqList*L,inti,ElemTypex)intj;if(L-Length=MAXLEN)printf(順序表已滿！順序表已滿！);returnOVER;/*表滿，不能插入表滿，不能插入*/if(iL-Length+1)/*檢查給定的插入位置的正確性檢查給定的插入位置的正確性*/printf(插入位置出錯！插入位

60、置出錯！);returnERROR;if(i=L-Length+1)L-datai-1=x;L-Length+;returnOK;/*插入的位置為表尾，則不需移動直接插入即可插入的位置為表尾，則不需移動直接插入即可*/for(j=L-Length-1;j=i-1;j-)/*結點移動結點移動*/L-dataj+1=L-dataj;L-datai-1=x;/*新元素插入新元素插入*/L-Length+;/*順序表長度增順序表長度增1*/returnOK;/*插入成功，返回插入成功，返回*/返回到本節(jié)目錄5插入操作插入操作插入算法的時間性能分析：插入算法的時間性能分析：順序表插入操作大約需移動表中一

61、半數(shù)據(jù)元順序表插入操作大約需移動表中一半數(shù)據(jù)元素，其時間復雜度為素，其時間復雜度為(n)。返回到本節(jié)目錄2.2.2順序表的基本操作實現(xiàn)順序表的基本操作實現(xiàn)6.刪除操作刪除操作線性表的刪除操作是指將第線性表的刪除操作是指將第i個元素從順序表中去個元素從順序表中去掉，刪除后順序表表長減掉，刪除后順序表表長減1，原順序表如圖，原順序表如圖2-5所示。所示。返回到本節(jié)目錄6.刪除操作刪除操作步驟如下：步驟如下：(1)將要刪除的元素值賦給指針變量將要刪除的元素值賦給指針變量*x，如圖，如圖2-6所示所示返回到本節(jié)目錄6.刪除操作刪除操作步驟如下：步驟如下：(2)將將ai+1an之間的結點依次順序向前移之

62、間的結點依次順序向前移動，如圖動，如圖2-7所示。所示。(3)順序表的長度減順序表的長度減1，刪除成功，并返回，算，刪除成功，并返回，算法描述見算法法描述見算法2.7。返回到本節(jié)目錄6.刪除操作刪除操作算法算法2.7intDelElem(SeqList*L,inti,ElemType*x)intj;if(L-Length=0)printf(順序表為空！順序表為空！);returnERROR;/*表空，不能刪除表空，不能刪除*/if(iL-Length)/*檢查是否空表及刪除位置的合法性檢查是否空表及刪除位置的合法性*/printf(不存在第不存在第i個元素個元素);returnERROR;*x

63、=L-datai-1;/*用指針變量用指針變量*x返回刪除的元素值返回刪除的元素值*/for(j=i;jLength-1;j+)/*結點移動結點移動*/L-dataj-1=L-dataj;L-Length-;/*順序表長度減順序表長度減1*/returnOK;/*刪除成功，返回刪除成功，返回*/返回到本節(jié)目錄6.刪除操作刪除操作刪除算法的時間性能分析：刪除算法的時間性能分析：與插入操作相同，其時間主要消耗在了移動表與插入操作相同，其時間主要消耗在了移動表中元素上，（大約需要移動表中一半的元素）中元素上，（大約需要移動表中一半的元素），顯然該算法的時間復雜度為，顯然該算法的時間復雜度為(n)。返

64、回到本節(jié)目錄2.2.2順序表的基本操作實現(xiàn)順序表的基本操作實現(xiàn)7順序表的輸出操作順序表的輸出操作掃描順序表掃描順序表L，輸出各元素的值，算法描述見，輸出各元素的值，算法描述見算法算法2.8。算法算法2.8voidDispList(SeqList*L)inti;for(i=0;iLength;i+)printf(%5d,L-datai);返回到本節(jié)目錄2.3鏈表鏈表v2.3.1單鏈表單鏈表v2.3.2單鏈表的基本操作實現(xiàn)單鏈表的基本操作實現(xiàn)v2.3.3鏈表的變形鏈表的變形返回到總目錄2.3.1單鏈表單鏈表1.單鏈表的定義單鏈表的定義線性表的鏈式存儲結構是指用一組任意的存儲單元線性表的鏈式存儲結構

65、是指用一組任意的存儲單元（可以連續(xù)，也可以不連續(xù)）存儲線性表中的數(shù)（可以連續(xù)，也可以不連續(xù)）存儲線性表中的數(shù)據(jù)元素。為了反映數(shù)據(jù)元素之間的邏輯關系，對據(jù)元素。為了反映數(shù)據(jù)元素之間的邏輯關系，對于每個數(shù)據(jù)元素不僅要表示它的具體內容，還要于每個數(shù)據(jù)元素不僅要表示它的具體內容，還要附加一個表示它的直接后繼元素存儲位置的信息，附加一個表示它的直接后繼元素存儲位置的信息，這樣構成的鏈表稱為線性單向鏈接表，簡稱單鏈這樣構成的鏈表稱為線性單向鏈接表，簡稱單鏈表，其結點結構如圖表，其結點結構如圖2-8所示。所示。數(shù)據(jù)域數(shù)據(jù)域后繼指針域后繼指針域datanext圖圖2-8單鏈表的結點示意圖單鏈表的結點示意圖其中

66、，其中，data部分稱為數(shù)據(jù)域，用于存儲一個數(shù)據(jù)元素部分稱為數(shù)據(jù)域，用于存儲一個數(shù)據(jù)元素（結點（結點Node）的信息。）的信息。next部分稱為指針域，用于存儲部分稱為指針域，用于存儲其直接后繼的存儲地址的信息。其直接后繼的存儲地址的信息。返回到本節(jié)目錄2.3.1單鏈表單鏈表v單鏈表分為帶頭結點（其單鏈表分為帶頭結點（其next域指向鏈表第一個結點的存儲地址）和域指向鏈表第一個結點的存儲地址）和不帶頭結點兩種類型。在許多情況下，帶頭結點的鏈表中每個結點的不帶頭結點兩種類型。在許多情況下，帶頭結點的鏈表中每個結點的存儲地址均放在其前驅結點中，這樣算法對所有的結點處理可一致化，存儲地址均放在其前驅結點中，這樣算法對所有的結點處理可一致化，因此，本節(jié)討論的單鏈表均指帶頭結點的單鏈表。帶頭結點的單鏈表因此，本節(jié)討論的單鏈表均指帶頭結點的單鏈表。帶頭結點的單鏈表如圖如圖2-9所示。所示。圖圖2-9帶頭結點的單鏈表帶頭結點的單鏈表其中，頭結點的數(shù)據(jù)域可以不存儲任何信息，也可以存放特殊的信息；其中，頭結點的數(shù)據(jù)域可以不存儲任何信息，也可以存放特殊的信息；頭結點的指針域存儲鏈表中第一個結點的地址。當