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

《數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)（608頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、數(shù)據(jù)結(jié)構(gòu)實(shí)用教程（C語(yǔ)言版）第第1章章概論概論本章主要介紹以下內(nèi)容：本章主要介紹以下內(nèi)容：本章主要介紹以下內(nèi)容：本章主要介紹以下內(nèi)容：數(shù)據(jù)結(jié)構(gòu)中涉及的相關(guān)概念數(shù)據(jù)結(jié)構(gòu)中涉及的相關(guān)概念數(shù)據(jù)結(jié)構(gòu)中涉及的相關(guān)概念數(shù)據(jù)結(jié)構(gòu)中涉及的相關(guān)概念數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容數(shù)據(jù)結(jié)構(gòu)研究的主要內(nèi)容算法的概念、描述方法以及評(píng)價(jià)標(biāo)準(zhǔn)算法的概念、描述方法以及評(píng)價(jià)標(biāo)準(zhǔn)算法的概念、描述方法以及評(píng)價(jià)標(biāo)準(zhǔn)算法的概念、描述方法以及評(píng)價(jià)標(biāo)準(zhǔn)本章目錄本章目錄1.11.1什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu)什么是數(shù)據(jù)結(jié)構(gòu)11.21.2算法和算法分析算法和算法分析算法和算法分析算法和算法分析

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

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

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

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

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

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

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

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

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

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

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

13、教學(xué)計(jì)劃關(guān)系圖特點(diǎn)：特點(diǎn)：圖中數(shù)據(jù)元素存在著多對(duì)多的任意關(guān)系。一個(gè)圖中數(shù)據(jù)元素存在著多對(duì)多的任意關(guān)系。一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前驅(qū)和直接后繼。結(jié)點(diǎn)可能有多個(gè)直接前驅(qū)和直接后繼。返回到本節(jié)目錄1.1.2數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)1.1.3數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)表示稱為數(shù)據(jù)的存儲(chǔ)結(jié)數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)表示稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)，也稱為物理結(jié)構(gòu)。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏構(gòu)，也稱為物理結(jié)構(gòu)。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的實(shí)現(xiàn)。本書將介輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)器中的實(shí)現(xiàn)。本書將介紹常用的兩種基本的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)紹常用的兩種基本的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。構(gòu)和鏈?zhǔn)酱?/p>

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

15、單元開(kāi)始由低地址向高地址號(hào)單元開(kāi)始由低地址向高地址存放，對(duì)應(yīng)的順序存儲(chǔ)結(jié)構(gòu)如表存放，對(duì)應(yīng)的順序存儲(chǔ)結(jié)構(gòu)如表1-3所示。所示。返回到本節(jié)目錄1.1.3數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)的主要特點(diǎn)：順序存儲(chǔ)結(jié)構(gòu)的主要特點(diǎn)：v可實(shí)現(xiàn)對(duì)各數(shù)據(jù)元素的隨機(jī)訪問(wèn)。這是因?yàn)榭蓪?shí)現(xiàn)對(duì)各數(shù)據(jù)元素的隨機(jī)訪問(wèn)。這是因?yàn)橹灰来鎯?chǔ)的首地址以及每個(gè)數(shù)據(jù)元素所只要知道存儲(chǔ)的首地址以及每個(gè)數(shù)據(jù)元素所占的存儲(chǔ)單元，就可以計(jì)算出各數(shù)據(jù)元素的占的存儲(chǔ)單元，就可以計(jì)算出各數(shù)據(jù)元素的存儲(chǔ)地址。存儲(chǔ)地址。v不利于修改，在對(duì)數(shù)據(jù)元素進(jìn)行插入、刪除不利于修改，在對(duì)數(shù)據(jù)元素進(jìn)行插入、刪除運(yùn)算時(shí)可能要移動(dòng)一系列的數(shù)據(jù)元素。運(yùn)算時(shí)可能要移

16、動(dòng)一系列的數(shù)據(jù)元素。返回到本節(jié)目錄1.1.3數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)2.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：借助指示元素存儲(chǔ)地址的指針鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：借助指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素間的邏輯關(guān)系。表示數(shù)據(jù)元素間的邏輯關(guān)系?！纠?.5】對(duì)于表對(duì)于表1-1學(xué)生信息登記表進(jìn)行鏈學(xué)生信息登記表進(jìn)行鏈?zhǔn)酱鎯?chǔ)時(shí)，在每個(gè)數(shù)據(jù)元素后方附加一個(gè)指式存儲(chǔ)時(shí)，在每個(gè)數(shù)據(jù)元素后方附加一個(gè)指向向“下一個(gè)結(jié)點(diǎn)地址下一個(gè)結(jié)點(diǎn)地址”的指針字段，用于存的指針字段，用于存放后繼數(shù)據(jù)元素的存儲(chǔ)地址，每個(gè)數(shù)據(jù)元素放后繼數(shù)據(jù)元素的存儲(chǔ)地址，每個(gè)數(shù)據(jù)元素的地址是隨機(jī)的，可以不連續(xù)。對(duì)應(yīng)的鏈?zhǔn)降牡刂肥请S機(jī)的，可以不連續(xù)。對(duì)應(yīng)的

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

18、抽象數(shù)據(jù)類型1抽象數(shù)據(jù)類型的定義抽象數(shù)據(jù)類型的定義抽象數(shù)據(jù)類型（抽象數(shù)據(jù)類型（AbstractDataType，簡(jiǎn)，簡(jiǎn)稱稱ADT）是指一個(gè)數(shù)學(xué)模型以及定義在該模）是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。型上的一組操作。2抽象數(shù)據(jù)類型的表示抽象數(shù)據(jù)類型的表示抽象數(shù)據(jù)類型實(shí)際上就是對(duì)該數(shù)據(jù)結(jié)構(gòu)的定義。抽象數(shù)據(jù)類型實(shí)際上就是對(duì)該數(shù)據(jù)結(jié)構(gòu)的定義。因?yàn)樗x了一個(gè)數(shù)據(jù)的邏輯結(jié)構(gòu)以及在此因?yàn)樗x了一個(gè)數(shù)據(jù)的邏輯結(jié)構(gòu)以及在此結(jié)構(gòu)上的一組算法?？梢杂靡粋€(gè)三元組表示：結(jié)構(gòu)上的一組算法?？梢杂靡粋€(gè)三元組表示：ADT=（，）（，）其中，其中，D是數(shù)據(jù)對(duì)象，是數(shù)據(jù)對(duì)象，S是是D上的關(guān)系集，上的關(guān)系集，P是是對(duì)

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

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

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

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

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

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

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

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

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

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

29、越大，表示該算法的算法的效率越低，反之越高。例如效率越低，反之越高。例如O(1)為常數(shù)數(shù)常數(shù)數(shù)量量級(jí),，即算法的即算法的時(shí)間復(fù)復(fù)雜性與性與輸入入規(guī)模模n無(wú)無(wú)關(guān)。關(guān)。返回到本節(jié)目錄1.2.2算法分析算法分析【例例1.6】分析以下算法的時(shí)間復(fù)雜度。分析以下算法的時(shí)間復(fù)雜度。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)上述算法中的基本運(yùn)算是語(yǔ)句（上述算法中的基本運(yùn)算是語(yǔ)句（2），其執(zhí)行頻率為），其執(zhí)行頻率為n2。則則T(n)=n2=O(

30、n2)返回到本節(jié)目錄1.2.2算法分析算法分析【例例1.7】分析以下算法的時(shí)間復(fù)雜度。分析以下算法的時(shí)間復(fù)雜度。i=1;while(i=n)i=2*i;(1)執(zhí)行執(zhí)行f(n)次次解：設(shè)語(yǔ)句（解：設(shè)語(yǔ)句（1）執(zhí)行次數(shù)是）執(zhí)行次數(shù)是f(n)，則，則2f(n)n得到得到T(n)=O(log2n)返回到本節(jié)目錄1.2.2算法分析算法分析【例例1.8】求兩個(gè)矩陣相乘的函數(shù)的時(shí)間復(fù)雜度。求兩個(gè)矩陣相乘的函數(shù)的時(shí)間復(fù)雜度。voidmult(inta,intb,intc)/*以二維數(shù)組存儲(chǔ)矩陣元素，以二維數(shù)組存儲(chǔ)矩陣元素，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à)于：等價(jià)于：(*指針名指針名).成員名成員名等價(jià)于：結(jié)構(gòu)體變量名等價(jià)于：結(jié)構(gòu)體變量名.成員名成員名在本書中，在程序內(nèi)大量使用結(jié)構(gòu)體類型的指在本書中，在程序內(nèi)大量使用結(jié)構(gòu)體類型的指針，所以大都采用第一種寫法。針，所以大都采用第一種寫法。返回到本節(jié)目錄1.2.3相關(guān)相關(guān)C語(yǔ)言知識(shí)回顧語(yǔ)言知識(shí)回顧（4）用）用typedef定義類型定義類型除了可以直接使用除了可以直接使用C提供的標(biāo)準(zhǔn)類型名和自己提供的標(biāo)準(zhǔn)類型名和自己聲明的結(jié)構(gòu)體類型外，還可以用聲明的結(jié)構(gòu)體類型外，還可以用typedef聲聲明新的類型名來(lái)代替已有

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

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

34、名間用于何種數(shù)據(jù)類型。（類型名*）表示把）表示把malloc函數(shù)返回值強(qiáng)制轉(zhuǎn)換為該類型指針。函數(shù)返回值強(qiáng)制轉(zhuǎn)換為該類型指針。返回到本節(jié)目錄1.2.3相關(guān)相關(guān)C語(yǔ)言知識(shí)回顧語(yǔ)言知識(shí)回顧（2）釋放內(nèi)存空間函數(shù)）釋放內(nèi)存空間函數(shù)free()【格式格式】free(指向要釋放單元的指針名指向要釋放單元的指針名)【功能功能】釋放該指針?biāo)傅囊粔K存儲(chǔ)空間，該釋放該指針?biāo)傅囊粔K存儲(chǔ)空間，該空間系統(tǒng)可另作它用。注意這個(gè)指針?biāo)傅目臻g系統(tǒng)可另作它用。注意這個(gè)指針?biāo)傅目臻g必須是由空間必須是由malloc()函數(shù)和函數(shù)和calloc()函函數(shù)分配的才行。數(shù)分配的才行。free函數(shù)無(wú)返回值。例如：函數(shù)無(wú)返回值。例如

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

36、回語(yǔ)語(yǔ)句句返回到本節(jié)目錄1.2.3相關(guān)相關(guān)C語(yǔ)言知識(shí)回顧語(yǔ)言知識(shí)回顧（2）函數(shù)的調(diào)用）函數(shù)的調(diào)用【格式格式】函數(shù)類型函數(shù)類型函數(shù)名（實(shí)參表）函數(shù)名（實(shí)參表）;【說(shuō)明說(shuō)明】1實(shí)參表中各參數(shù)應(yīng)與形參表中各參數(shù)類型實(shí)參表中各參數(shù)應(yīng)與形參表中各參數(shù)類型及個(gè)數(shù)相符。及個(gè)數(shù)相符。2在調(diào)用函數(shù)時(shí)，表達(dá)式應(yīng)與該函數(shù)的類型在調(diào)用函數(shù)時(shí)，表達(dá)式應(yīng)與該函數(shù)的類型相符，如果該函數(shù)有返回值時(shí)，在調(diào)用時(shí)要相符，如果該函數(shù)有返回值時(shí)，在調(diào)用時(shí)要將該函數(shù)的返回值賦給相同類型的變量。將該函數(shù)的返回值賦給相同類型的變量。返回到本節(jié)目錄1.2.3相關(guān)相關(guān)C語(yǔ)言知識(shí)回顧語(yǔ)言知識(shí)回顧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相關(guān)相關(guān)C語(yǔ)言知識(shí)回顧語(yǔ)言知識(shí)回顧（1）將）將UCDOS的核心文件進(jìn)行兼容性設(shè)置的核心文件進(jìn)行兼容性設(shè)置（有的機(jī)器可省略這步，直接執(zhí)行（有的機(jī)器可省略這步，直接執(zhí)行（2）。）。點(diǎn)點(diǎn)“開(kāi)始開(kāi)始”菜單菜單-

38、“所有程序所有程序”-“附件附件”-“程序兼容性向?qū)С绦蚣嫒菪韵驅(qū)А?“我想手動(dòng)定位程序我想手動(dòng)定位程序”-“瀏覽瀏覽”--win98-256色，色，640X480-程序工程序工作正確嗎？選作正確嗎？選“是，設(shè)置此程序?yàn)橐恢笔褂檬牵O(shè)置此程序?yàn)橐恢笔褂眉嫒菪栽O(shè)置。兼容性設(shè)置?！蓖瓿?。有的完成。有的UCDOS版本的版本的核心文件是核心文件是knlvga.exe，也要照此進(jìn)行兼，也要照此進(jìn)行兼容性設(shè)置。容性設(shè)置。返回到本節(jié)目錄1.2.3相關(guān)相關(guān)C語(yǔ)言知識(shí)回顧語(yǔ)言知識(shí)回顧（2）運(yùn)行）運(yùn)行UCDOS系統(tǒng)文件的方法。系統(tǒng)文件的方法。進(jìn)入到命令提示符（進(jìn)入到命令提示符（MS-DOS狀態(tài)）（狀態(tài)）（“開(kāi)開(kāi)始

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

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

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

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

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

44、復(fù)雜度與空間復(fù)雜度。返回到總目錄返回到總目錄返回到總目錄返回到總目錄 數(shù)據(jù)結(jié)構(gòu)實(shí)用教程（C語(yǔ)言版）中國(guó)水利水電出版社第第2章章線性表線性表本章主要介紹下列內(nèi)容本章主要介紹下列內(nèi)容本章主要介紹下列內(nèi)容本章主要介紹下列內(nèi)容線性表的定義和基本操作線性表的定義和基本操作線性表的定義和基本操作線性表的定義和基本操作線性表的順序存儲(chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表的應(yīng)用舉例線性表的應(yīng)用舉例線性表的應(yīng)用舉例線性表的應(yīng)用舉例本章目錄本章目錄2.12.1線性表的基本概念線性表的基本概念線性表的基

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

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

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

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

49、查找一個(gè)與找一個(gè)與給定定值x相等的數(shù)據(jù)元素，其作相等的數(shù)據(jù)元素，其作用是若存在一個(gè)或多個(gè)與用是若存在一個(gè)或多個(gè)與x相等的數(shù)據(jù)元素，相等的數(shù)據(jù)元素，則返回返回的的元素所在位置的最小元素所在位置的最小值或地址或地址值；否否則返回返回0或或NULL值。2.1.2 線性表的基本操作線性表的基本操作返回到本節(jié)目錄（5）插入操作）插入操作InsElem(L,i,x)。其作用是在線性表。其作用是在線性表L的的第第i個(gè)位置上插入一個(gè)值為個(gè)位置上插入一個(gè)值為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個(gè)位置的數(shù)據(jù)元素并用個(gè)位置的數(shù)據(jù)元素并用x將其存儲(chǔ)，使線性表將其存儲(chǔ)，使線性表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.

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

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

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

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

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

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

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

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

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

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

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

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

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

64、返回到本節(jié)目錄2.2.2順序表的基本操作實(shí)現(xiàn)順序表的基本操作實(shí)現(xiàn)7順序表的輸出操作順序表的輸出操作掃描順序表掃描順序表L，輸出各元素的值，算法描述見(jiàn)，輸出各元素的值，算法描述見(jiàn)算法算法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單鏈表的基本操作實(shí)現(xiàn)單鏈表的基本操作實(shí)現(xiàn)v2.3.3鏈表的變形鏈表的變形返回到總目錄2.3.1單鏈表單鏈表1.單鏈表的定義單鏈表的定義線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是指用一組任意的存儲(chǔ)單元線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)

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

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