電子教案-《數(shù)據(jù)結(jié)構(gòu)(C／C++描述)》-阮宏一

第10章文件與外排序10.1文件10.2外排序10.1.1

外存信息的存取

10.1.2文件的基本概念

10.1.3順序文件10.1.5索引順序文件10.1.6直接存取文件10.1.7多關(guān)鍵字文件10.1文件10.1.4索引文件一、文件與記錄文件即為記錄的集合，和“查找表”的差別在于，“文件”指的是存儲(chǔ)在外存儲(chǔ)器中的記錄的集合。

“記錄”是文件中可以存取的數(shù)據(jù)的基本單位。10.1.2

文件的基本概念

二、文件可按其中記錄的類型不同而分成兩類：

其一為操作系統(tǒng)的文件。文件中的記錄僅是一個(gè)字符組。由于操作系統(tǒng)中的文件僅是一維的連續(xù)字符序列，為了用戶存取和加工的方便，將文件中的信息劃分為若干組，其中每一組信息稱作一個(gè)記錄；10.1.2

文件的基本概念

其二為數(shù)據(jù)庫文件。文件中的記錄帶有結(jié)構(gòu)，是數(shù)據(jù)項(xiàng)的集合。記錄是文件中可以存取的數(shù)據(jù)基本單位，數(shù)據(jù)項(xiàng)是文件中可以使用的數(shù)據(jù)最小單位10.1.2

文件的基本概念

三、關(guān)鍵字

記錄中能識(shí)別不同記錄的數(shù)據(jù)項(xiàng)被稱為關(guān)鍵字。

若該數(shù)據(jù)項(xiàng)能唯一識(shí)別一個(gè)記錄，則稱為主關(guān)鍵字，若能識(shí)別多個(gè)記錄則稱為次關(guān)鍵字。10.1.2

文件的基本概念

四、文件的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)

文件的邏輯結(jié)構(gòu)指的是呈現(xiàn)在用戶面前的文件中記錄之間的邏輯關(guān)系；

文件的物理結(jié)構(gòu)指的是文件中的邏輯記錄在存儲(chǔ)器中的組織方式。10.1.2

文件的基本概念

五、文件的操作檢索修改排序10.1.2

文件的基本概念

結(jié)構(gòu)特點(diǎn)：

記錄在文件中的排列順序是由記錄進(jìn)入存儲(chǔ)介質(zhì)的次序決定的。

即文件物理結(jié)構(gòu)中記錄的排列順序和文件的邏輯結(jié)構(gòu)中記錄的排列順序一致。10.1.3順序文件

順序文件的具體組織形式有兩種：串聯(lián)文件：物理記錄之間的順序由指針相鏈.連續(xù)文件：

次序相繼的兩個(gè)物理記錄其存儲(chǔ)位置相鄰;10.1.3順序文件操作特點(diǎn)：1．便于進(jìn)行順序存??；2．不便于進(jìn)行直接存取，為取第i個(gè)記錄，必須先讀出前i-1個(gè)記錄，對(duì)于磁盤上的等長記錄的連續(xù)文件可以進(jìn)行折半查找；10.1.3順序文件3．插入新的記錄只能加在文件的末尾；4．刪除記錄時(shí)，只作標(biāo)記；5．更新記錄必須生成新的文件。10.1.3順序文件

順序文件的插入、刪除和更新操作在多數(shù)情況下都采用批處理方式。此時(shí)，為處理方便，通常將順序文件作成有序文件，稱作“主文件”，同時(shí)將所有的操作做成一個(gè)“事務(wù)文件”（經(jīng)過排序也成為有序文件）。所謂“批處理”，就是將這兩個(gè)文件“合”為一個(gè)新的主文件。具體操作相當(dāng)于“歸并兩個(gè)有序表”。10.1.3順序文件（1）對(duì)于事務(wù)文件中的每個(gè)操作首先要判別其“合法性”；（2）事務(wù)文件中可能存在多個(gè)操作是對(duì)主文件中同一個(gè)記錄進(jìn)行的。但有兩點(diǎn)不同：10.1.3順序文件一、結(jié)構(gòu)特點(diǎn)1．索引文件由“主文件”和多級(jí)“索引”組成。2．索引中的每個(gè)記錄由“關(guān)鍵字”和“指針”組成。3．通常，索引文件中的主文件是無序文件，索引是（按關(guān)鍵字有序）的有序文件。4．“索引”是在輸入數(shù)據(jù)建立文件時(shí)自動(dòng)生成。初建時(shí)的“靜態(tài)索引”為無序文件，經(jīng)過排序后成為有序文件。10.1.4索引文件二、操作的特點(diǎn)１．檢索方式為：直接存取和按關(guān)鍵字存取。“按關(guān)鍵字檢索”將分兩步進(jìn)行：先查索引，然后根據(jù)索引中指針?biāo)杆魅∮涗?。２．插入記錄時(shí)，“記錄”插入在主文件的末尾，而相應(yīng)的“索引項(xiàng)”必須插入在索引的合適位置上。因此，最好在建索引表時(shí)留有一定“空位”。10.1.4索引文件３．刪除記錄時(shí)，僅需刪除索引表中相應(yīng)的索引項(xiàng)即可。４．更新記錄時(shí)，應(yīng)將更新后的記錄插入在主文件的末尾，同時(shí)修改相應(yīng)的索引項(xiàng)。10.1.4索引文件１．多級(jí)靜態(tài)索引10.1.4索引文件

主文件

索引表

查找表

第二查找表

第三查找表…...…...…...…...此時(shí)的索引文件結(jié)構(gòu)：對(duì)主文件中每個(gè)記錄建立一個(gè)索引項(xiàng)：

主關(guān)鍵字

記錄在主文件中的存儲(chǔ)位置稱作稠密索引，由這些索引項(xiàng)構(gòu)成索引表；１．多級(jí)靜態(tài)索引

從索引表建立的索引稱查找表，其中每個(gè)索引項(xiàng)為：

最大關(guān)鍵字

其所在數(shù)據(jù)塊的存儲(chǔ)位置稱這類索引為非稠密索引。類似地，由查找表建立的索引為第二查找表；由第二查找表建立的索引為第三查找表。１．多級(jí)靜態(tài)索引10.1.4索引文件２．動(dòng)態(tài)索引索引表采用查找樹表或哈希表。

優(yōu)點(diǎn)：1.不需要建立多級(jí)索引;2.初建索引不需要進(jìn)行排序;3.插入或刪除記錄時(shí)，修改索引方便;２．動(dòng)態(tài)索引

用查找樹表作索引時(shí)，查找索引所需訪問外存次數(shù)的最大值恰為查找樹的深度。

稠密索引的優(yōu)點(diǎn)是，可以實(shí)現(xiàn)“預(yù)查找”；缺點(diǎn)是，索引表占用的存儲(chǔ)空間大。

可以作索引的樹表有：二叉排序樹、B-樹和鍵樹。２．動(dòng)態(tài)索引

主文件按主關(guān)鍵字有序，對(duì)一組記錄建立一個(gè)索引項(xiàng)，即建立非稠密索引。結(jié)構(gòu)特點(diǎn)：10.1.5索引順序文件一、ISAM文件

ISAM(IndexSequentialAccessMethod)

（索引順序存取方法）是一種專為磁盤存取設(shè)計(jì)的文件組織方法。有兩種典型的索引順序文件:10.1.5索引順序文件１．文件的組織方式：

主文件按柱面集中存放，同時(shí)建立

三級(jí)索引：磁道索引、柱面索引和主索引。

關(guān)鍵字

指針

關(guān)鍵字

指針

磁道索引結(jié)構(gòu)基本索引項(xiàng)溢出索引項(xiàng)一、ISAM文件2101024主索引

r(14)r(21)r(38)r(41)r(57)r(63)r(72)r(85)r(99)

溢出區(qū)

磁道索引

r(514)……

溢出區(qū)

磁道索引……r(1024)一個(gè)柱面

….柱面索引992101024T0T1T2T3T4T5２．操作的特點(diǎn)：檢索插入刪除一、ISAM文件檢索----

可有兩種方式：按關(guān)鍵字存取

—

從主索引開始,到柱面索引，到磁道索引，最后取得記錄，先后訪問四次外存。順序存取

—

依關(guān)鍵字最小至大順序存取。一、ISAM文件插入:

修改本磁道的索引項(xiàng)(包括基本索引項(xiàng)和溢出索引項(xiàng))。

將該磁道上關(guān)鍵字最大的記錄移出到本柱面的溢出區(qū)中;

將記錄插入在某個(gè)磁道的合適位置上;一、ISAM文件刪除:

在被刪記錄當(dāng)前存儲(chǔ)位置上作“刪除標(biāo)記”。一、ISAM文件３．文件重組

在經(jīng)過多次的插入和刪除操作之后，大量的記錄進(jìn)入文件的“溢出區(qū)”,而“基本存儲(chǔ)區(qū)”中出現(xiàn)很多已被刪去的記錄空間，此時(shí)的文件結(jié)構(gòu)很不合理。因此，對(duì)ISAM

文件，需要周期地進(jìn)行重整。一、ISAM文件４．柱面索引的位置

ISAM文件占有多個(gè)柱面，其柱面索引本身占有一個(gè)柱面，為使“磁頭”的平均移動(dòng)距離最小，柱面索引應(yīng)設(shè)在數(shù)據(jù)文件所占全部柱面的中間位置上。一、ISAM文件二、VSAM文件

VSAM(VistualStorageAccessMethod)

文件是利用操作系統(tǒng)中提供的虛擬存儲(chǔ)器的功能組織的文件；免除了用戶為讀/寫記錄時(shí)直接對(duì)外存進(jìn)行的操作。

對(duì)用戶而言，文件只有控制區(qū)間和控制區(qū)域等邏輯存儲(chǔ)單位?！?...........

索引集B+樹順序集控制區(qū)域控制區(qū)間數(shù)據(jù)集1.文件的結(jié)構(gòu)控制區(qū)間是用戶進(jìn)行一次存取的邏輯單位，可看成是一個(gè)邏輯磁道。但它的實(shí)際大小和物理磁道無關(guān)。

VSAM

文件初建時(shí)，每個(gè)控制區(qū)間內(nèi)的記錄數(shù)不足額定數(shù)，并且有的控制區(qū)間內(nèi)的記錄數(shù)為零。

控制區(qū)域由若干控制區(qū)間和它們的索引項(xiàng)組成，可看成是一個(gè)邏輯柱面.二、VSAM文件３．順序集

本身是一個(gè)單鏈表，它包含文件的全部索引項(xiàng)，同時(shí)，順序集中的每個(gè)結(jié)點(diǎn)即為B+樹的葉子結(jié)點(diǎn).

索引集中的結(jié)點(diǎn)即為B+樹的非葉結(jié)點(diǎn).二、VSAM文件４．文件的操作檢索：可進(jìn)行順序存取和按關(guān)鍵字存取;插入：按關(guān)鍵字大小插入在某個(gè)適當(dāng)?shù)目刂茀^(qū)間中，當(dāng)控制區(qū)間中的記錄數(shù)超過文件規(guī)定的大小時(shí)，要“分裂”控制區(qū)間，必要時(shí)，還需要“分裂”控制區(qū)域;刪除：必須“真實(shí)地”刪除記錄，因此要在控制區(qū)間內(nèi)“移動(dòng)”記錄;二、VSAM文件５．VSAM文件通常被作為大型索引順序文件的標(biāo)準(zhǔn)組織方式。其缺點(diǎn)是：占有較多的存儲(chǔ)空間，一般只能保持約75%

的存儲(chǔ)空間利用率。因此，一般情況下，極少產(chǎn)生需要分裂控制區(qū)域的情況。其優(yōu)點(diǎn)是：動(dòng)態(tài)地分配和釋放空間,不需要重組文件；能較快地實(shí)現(xiàn)對(duì)“后插入”

的記錄的檢索;二、VSAM文件１．直接存取文件的特點(diǎn)和前幾節(jié)討論的文件組織方法不同，直接存取文件的特點(diǎn)是，由記錄的關(guān)鍵字“直接”得到記錄在外存上的映象地址。

類似于哈希表的構(gòu)造方法，根據(jù)文件中關(guān)鍵字的特點(diǎn)設(shè)計(jì)一種“哈希函數(shù)”和“處理沖突的方法”將記錄散列到外存儲(chǔ)設(shè)備上，又稱“散列文件”。10.1.6直接存取文件２．哈希文件的結(jié)構(gòu)

由于記錄在外存上是成組存放的，因此允許多個(gè)記錄映象到同一個(gè)地址上。在此，稱外存儲(chǔ)器中存放多個(gè)記錄的“數(shù)據(jù)塊”為“桶”。因此由哈希函數(shù)得到的映象地址為“桶地址”。10.1.6直接存取文件例如：有一組關(guān)鍵字如下：

{589，063，269，505，764，182，166，330}假設(shè)哈希函數(shù)為keyMOD7，每個(gè)桶可以容納3個(gè)記錄（稱桶的容量為3），則哈希文件如下:基桶063182589505764269166330溢出桶

在哈希文件中，“沖突”和“溢出”是不同的概念。一般情況下，假設(shè)桶的大小為m，則允許哈希地址產(chǎn)生m-1次的沖突，當(dāng)發(fā)生第m次沖突時(shí)，才需要進(jìn)行“沖突處理”。對(duì)散列文件而言，通常采用鏈地址法出路沖突。為區(qū)別起見，稱直接“散列”的數(shù)據(jù)塊為“基桶”，而因“溢出”存放的數(shù)據(jù)塊為“溢出桶”.10.1.6直接存取文件３．文件的操作檢索：只能進(jìn)行按關(guān)鍵字的查找，不能進(jìn)行順序查找。檢索時(shí)，先在基桶內(nèi)進(jìn)行查找，若不存在，則再到溢出桶中進(jìn)行查找。插入：當(dāng)查找不成功時(shí)，將記錄插入在相應(yīng)的基桶或溢出桶內(nèi)。刪除：對(duì)被刪記錄作特殊標(biāo)記。10.1.6直接存取文件４．哈希文件分析

優(yōu)點(diǎn)：記錄隨機(jī)存放，不需要進(jìn)行排序；插入、刪除方便，存取速度快；節(jié)省存儲(chǔ)空間，不需要索引區(qū)。

缺點(diǎn)：不能進(jìn)行順序存?。辉诮?jīng)過多次插入和刪除操作之后，需進(jìn)行“重組文件”

的操作。10.1.6直接存取文件一、多關(guān)鍵字文件的特點(diǎn)

除需要對(duì)主關(guān)鍵字建立“主索引”外，尚需對(duì)各個(gè)次關(guān)鍵字建立“次索引”。次索引項(xiàng)：次關(guān)鍵字（指向記錄的）指針10.1.7多關(guān)鍵字文件二、次索引的組織方法1．多重鏈表文件

特點(diǎn)：將所有具有相同次關(guān)鍵字的記錄鏈接在同一鏈表中，該鏈表的頭指針即為次索引項(xiàng)中“指針域”的值。10.1.7多關(guān)鍵字文件2.倒排文件特點(diǎn)：將所有具有相同次關(guān)鍵字的記錄構(gòu)成一個(gè)次索引順序表，此時(shí)的次索引順序表中僅存放記錄的“主關(guān)鍵字”或記錄的“物理記錄號(hào)”。次索引項(xiàng)中的“指針”指向相應(yīng)的次索引順序表。10.1.7多關(guān)鍵字文件3．次關(guān)鍵字索引表本身的結(jié)構(gòu)可以是順序表，也可以是樹表或哈希表，視具體的次關(guān)鍵字的特性而定。

10.1.7多關(guān)鍵字文件10.2.1外排序的方法

10.2.2

多路平衡歸并及實(shí)現(xiàn)

10.2.3置換－選擇排序

10.2.4最佳歸并樹

10.2外排序外排序指的是大文件的排序。排序前不可能將全部數(shù)據(jù)讀入內(nèi)存，在排序過程中還需要進(jìn)行多次的內(nèi)、外存之間的交換。這種內(nèi)外存并用的排序方法稱為外排序。10.2.1外排序的方法

最常用的外排序方法是歸并排序法。這種方法由兩個(gè)階段組成：

第1階段是把文件逐段輸入到內(nèi)存，用有效的內(nèi)排序方法對(duì)文件的各個(gè)段進(jìn)行排序，經(jīng)排序的文件段稱為順串（或歸并段），當(dāng)它們生成后立即寫到外存上，這樣在外存上就形成了許多初始順串；10.2.1外排序的方法

第2階段是對(duì)這些順串用某種歸并方法（如2-路歸并）進(jìn)行多趟歸并，使順串的長度逐漸由小至大，直至變成一個(gè)順串，即整個(gè)文件有序?yàn)橹埂?0.2.1外排序的方法

2-路歸并過程示意R1R2R3R4R5R6R1’R2’R3’第1趟R1’’第2趟R1’’’第3趟10.2.2

多路平衡歸并及實(shí)現(xiàn)

為了減少歸并的趟數(shù)，可采用多路歸并。

3-路歸并過程示意R1R2R3R4R5R6R1’R2’第1趟R1’’第2趟在k路歸并中，為了確定下一個(gè)要輸出的記錄，就需要在k個(gè)記錄中尋找關(guān)鍵字值最小的那個(gè)記錄，這要比2-路歸并復(fù)雜些。為了減少這個(gè)代價(jià)，我們可采用選擇樹的方法來實(shí)現(xiàn)k路歸并由于非葉子結(jié)點(diǎn)總是代表優(yōu)勝者，所以可以把這種樹稱為勝者樹。10.2.2

多路平衡歸并及實(shí)現(xiàn)

用選擇樹進(jìn)行k-路歸并有一個(gè)缺點(diǎn)，就是當(dāng)輸出一個(gè)記錄之后，重構(gòu)選擇樹需要較多時(shí)間。另外，隨著歸并路數(shù)的增大，需要較多的緩沖區(qū)。

為了克服這些缺點(diǎn)，我們采用敗者樹（TreeofLoser）?！皵≌邩洹?，就是在選擇樹中，每個(gè)非葉子結(jié)點(diǎn)均存放其兩個(gè)子結(jié)點(diǎn)中的敗者，而讓勝者去參加更高一級(jí)的比賽。10.2.2

多路平衡歸并及實(shí)現(xiàn)

多路平衡歸并排序是在初始?xì)w并段已經(jīng)生成的基礎(chǔ)上進(jìn)行的，產(chǎn)生初始?xì)w并段的方法很多，前面講過的任何一種內(nèi)排序的方法都可以用來產(chǎn)生初始?xì)w并段。10.2.2

多路平衡歸并及實(shí)現(xiàn)

一種新的生成初始?xì)w并段的方法，稱之為置換-選擇排序。

置換-選擇排序（Replacement-SelectionSorting）是在屬性選擇排序的基礎(chǔ)上得來的，它的特點(diǎn)是：在整個(gè)排序（得到所有初始?xì)w并段）的過程中，選擇最?。ɑ蜃畲螅┑年P(guān)鍵字和輸入、輸出交叉或平行進(jìn)行。10.2.3

置換－選擇排序

10.2.4最佳歸并樹

一般情況下，利用置換-選擇排序生成的初始?xì)w并段的長度各不相等。對(duì)m個(gè)長度不等的初始?xì)w并段進(jìn)行k路歸并時(shí)，其執(zhí)行效率不僅與k的大小有關(guān)，而且還與這些歸并段被歸并的先后順序有關(guān)。

要得到最少的外存讀寫次數(shù)，對(duì)m個(gè)長度不等的初始?xì)w并段，我們可以構(gòu)造一棵哈夫曼樹作為歸并樹，按這樣構(gòu)造的歸并樹進(jìn)行歸并，可以保證對(duì)外存的讀寫次數(shù)達(dá)到最少，這棵哈夫曼樹就稱為“最佳歸并樹”。10.2.4最佳歸并樹

中國水利水電出版社6421世紀(jì)高等院校計(jì)算機(jī)系列教材數(shù)據(jù)結(jié)構(gòu)（C/C++描述）

中國水利水電出版社65內(nèi)容安排章內(nèi)容學(xué)時(shí)章內(nèi)容學(xué)時(shí)1緒論26樹和二叉樹122線性表87圖123棧和隊(duì)列68查找84串49內(nèi)部排序85多維數(shù)組、矩陣和廣義表610文件與外排序6中國水利水電出版社66第1章緒論中國水利水電出版社671.1數(shù)據(jù)結(jié)構(gòu)的概念1.2抽象數(shù)據(jù)類型1.3算法和算法分析中國水利水電出版社681.1

數(shù)據(jù)結(jié)構(gòu)的概念（數(shù)據(jù)結(jié)構(gòu)在軟件開發(fā)中的地位）系統(tǒng)分析系統(tǒng)設(shè)計(jì)系統(tǒng)實(shí)現(xiàn)系統(tǒng)維護(hù)系統(tǒng)設(shè)計(jì)中國水利水電出版社69程序設(shè)計(jì):算法:數(shù)據(jù)結(jié)構(gòu):為計(jì)算機(jī)處理問題編制一組指令集

處理問題的策略問題的數(shù)學(xué)模型系統(tǒng)設(shè)計(jì)中國水利水電出版社70非數(shù)值計(jì)算的程序設(shè)計(jì)問題:例1.1

學(xué)生信息檢索系統(tǒng)算法:?模型：？基本操作是：查詢線性表中國水利水電出版社71例1.2

計(jì)算機(jī)和人對(duì)弈問題

算法：?模型：?求從樹根到樹葉的一條路徑樹中國水利水電出版社72例1.3教學(xué)計(jì)劃編排問題

算法：?模型：?拓?fù)渑判驁D中國水利水電出版社73概括地說，

數(shù)據(jù)結(jié)構(gòu)是一門討論“描述現(xiàn)實(shí)世界實(shí)體的數(shù)學(xué)模型(非數(shù)值計(jì)算)及其上的操作在計(jì)算機(jī)中如何表示和實(shí)現(xiàn)”的學(xué)科。中國水利水電出版社74基本概念和術(shù)語中國水利水電出版社75

所有能被輸入到計(jì)算機(jī)中，且能被計(jì)算機(jī)處理的符號(hào)(包括數(shù)字、字符、聲音、圖像等信息)的集合。1.數(shù)據(jù)（data）是計(jì)算機(jī)操作的對(duì)象的總稱。

是計(jì)算機(jī)處理信息的某種特定符號(hào)的表示形式。中國水利水電出版社76

是數(shù)據(jù)（集合）中的一個(gè)“個(gè)體”,在計(jì)算機(jī)中通常作為一個(gè)整體進(jìn)行考慮和處理。是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位（又稱元素、結(jié)點(diǎn)，頂點(diǎn)、記錄）.2.數(shù)據(jù)元素（dataelement）如:整數(shù)“5”,字符“N”等。

----是不可分割的數(shù)據(jù)元素.中國水利水電出版社77

其中每一項(xiàng)，稱為一個(gè)“數(shù)據(jù)項(xiàng)”。

(又稱為：字段、域、屬性等。)它是數(shù)據(jù)結(jié)構(gòu)中討論的最小單位。數(shù)據(jù)元素也可以由若干項(xiàng)構(gòu)成。例如：描述一個(gè)學(xué)生的數(shù)據(jù)元素。稱之為組合項(xiàng)年月日姓名學(xué)號(hào)班號(hào)性別出生日期入學(xué)成績?cè)禹?xiàng)中國水利水電出版社783.數(shù)據(jù)項(xiàng)（Dataitem）構(gòu)成數(shù)據(jù)元素的項(xiàng)目，是具有獨(dú)立含義的最小標(biāo)識(shí)單位。（又稱字段、域、屬性等）。三者之間的關(guān)系：數(shù)據(jù)>數(shù)據(jù)元素>數(shù)據(jù)項(xiàng)例：班級(jí)通訊錄>個(gè)人記錄>姓名、年齡、……中國水利水電出版社794.數(shù)據(jù)結(jié)構(gòu)（datastructure）帶結(jié)構(gòu)的數(shù)據(jù)元素的集合有一個(gè)特性相同的數(shù)據(jù)元素的集合，如果在數(shù)據(jù)元素之間存在一種或多種特定的關(guān)系，則稱為一個(gè)數(shù)據(jù)結(jié)構(gòu)。指的是數(shù)據(jù)元素之間存在的關(guān)系。中國水利水電出版社80例如，在2行3列的二維數(shù)組中6個(gè)元素{a1,a2,a3,a4,a5,a6}之間存在兩個(gè)關(guān)系：行的次序關(guān)系:row={<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>}col={<a1,a4>,<a2,a5>,<a3,a6>}

a1a2a3a4a5a6列的次序關(guān)系:中國水利水電出版社81

若在

6個(gè)數(shù)據(jù)元素{a1,a2,a3,a4,a5,a6}之間存在如下的次序關(guān)系：{<ai,ai+1>|i=1,2,3,4,5}

數(shù)據(jù)結(jié)構(gòu)是相互之間存在著某種邏輯關(guān)系的數(shù)據(jù)元素的集合?？梢姡煌摹瓣P(guān)系”構(gòu)成不同的“結(jié)構(gòu)”則構(gòu)成一維數(shù)組的定義。中國水利水電出版社82

從關(guān)系或結(jié)構(gòu)分，數(shù)據(jù)結(jié)構(gòu)可歸結(jié)為以下4類:線性結(jié)構(gòu)樹形結(jié)構(gòu)圖狀結(jié)構(gòu)集合結(jié)構(gòu)一對(duì)一（1:1)一對(duì)多（1:n)多對(duì)多(m:n)僅同屬一個(gè)集合中國水利水電出版社83數(shù)據(jù)結(jié)構(gòu)涵蓋的內(nèi)容中國水利水電出版社845.邏輯結(jié)構(gòu)(logicstructure)

是對(duì)數(shù)據(jù)元素之間邏輯關(guān)系的描述，它可以用一個(gè)數(shù)據(jù)元素的集合和定義在此集合上的若干關(guān)系來表示。中國水利水電出版社85數(shù)據(jù)的邏輯結(jié)構(gòu)，簡稱為數(shù)據(jù)結(jié)構(gòu)其形式定義描述為:數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組

Data_Structures=（D,S）其中:D

是數(shù)據(jù)元素的有限集，

S

是D上關(guān)系的有限集。中國水利水電出版社86例如:定義“班集體”為一個(gè)數(shù)據(jù)結(jié)構(gòu)。Class=（D,S）D={a,b1,…,bn,c1,…cn,d1,…dn}S={R1,R2}

R1={<a,b1>,<a,c1>,<a,d1>}R2={<b1,bj>,<c1,cj>,<d1,dj>|j=2,3,…,n}樹結(jié)構(gòu)中國水利水電出版社87例：用圖形表示下列數(shù)據(jù)結(jié)構(gòu)，并指出它們是屬于線性結(jié)構(gòu)還是非線性結(jié)構(gòu)。（1）

S=（D,R）

D={a,b,c,d,e,f}

R={<a,e>,<b,c>,<c,a>,<e,f>,<f,d>}解：上述數(shù)據(jù)結(jié)構(gòu)表達(dá)式可用圖形表示為：bcaefd所以，此結(jié)構(gòu)為線性的。中國水利水電出版社88（2）

S=（D,R）

D={di|1≤i≤5}

R={<di,dj>|i<j}

d1d5d2d4d3該結(jié)構(gòu)是圖結(jié)構(gòu)。解：上述數(shù)據(jù)結(jié)構(gòu)表達(dá)式可用圖形表示為：中國水利水電出版社896.存儲(chǔ)結(jié)構(gòu)(storagestructure)

是數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示和實(shí)現(xiàn)，故又稱“物理結(jié)構(gòu)”。中國水利水電出版社90數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

——

邏輯結(jié)構(gòu)在存儲(chǔ)器中的映象“數(shù)據(jù)元素”的映象？“關(guān)系”的映象？中國水利水電出版社91數(shù)據(jù)元素的映象方法：用二進(jìn)制位(bit)的位串表示數(shù)據(jù)元素(321)10=(501)8=(101000001)2A=(101)8=(001000001)2中國水利水電出版社92關(guān)系的映象方法（表示

x,y

的方法）（1）順序映象--以相對(duì)的存儲(chǔ)位置表示后繼關(guān)系。例如:令y

的存儲(chǔ)位置和x

的存儲(chǔ)位置之間差一個(gè)常量C。而C

是一個(gè)隱含值，整個(gè)存儲(chǔ)結(jié)構(gòu)中只含數(shù)據(jù)元素本身的信息。xy中國水利水電出版社93（2）鏈?zhǔn)接诚?-以附加信息(指針)表示后繼關(guān)系。對(duì)前例，需要用一個(gè)和x

在一起的附加信息（指針）指示y

的存儲(chǔ)位置。yx中國水利水電出版社94在不同的編程環(huán)境中，存儲(chǔ)結(jié)構(gòu)可有不同的描述方法。

當(dāng)用高級(jí)程序設(shè)計(jì)語言進(jìn)行編程時(shí)，通?？捎酶呒?jí)編程語言中提供的數(shù)據(jù)類型描述存儲(chǔ)結(jié)構(gòu)。中國水利水電出版社95例如:

以3個(gè)帶有次序關(guān)系的整數(shù)表示一個(gè)長整數(shù)時(shí)，可利用C語言中提供的整數(shù)數(shù)組類型，

typedefintLong_int[3];定義長整數(shù)為:中國水利水電出版社96typedefstruct{

inty;//年號(hào)Year

intm;//月號(hào)Month

intd;//日號(hào)Day}

DateType;//日期類型定義“日期”為:定義“學(xué)生”為:typedefstruct{

charid[8];//學(xué)號(hào)

charname[16];//姓名

charsex;//性別‘M/F’:男/女

DateTypebdate;//出生日期}

Student;//學(xué)生類型中國水利水電出版社977.數(shù)據(jù)運(yùn)算

是在數(shù)據(jù)的邏輯結(jié)構(gòu)上定義的操作算法,它在數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)。最常用的數(shù)據(jù)運(yùn)算有5種：插入、刪除、修改、查找、排序中國水利水電出版社98數(shù)據(jù)類型

在用高級(jí)程序語言編寫的程序中：必須對(duì)程序中出現(xiàn)的每個(gè)變量、常量或表達(dá)式，明確說明它們所屬的數(shù)據(jù)類型。中國水利水電出版社99例如，C

語言中提供的基本數(shù)據(jù)類型有:整型int浮點(diǎn)型float字符型char邏輯型bool（C++語言）雙精度型double中國水利水電出版社100

數(shù)據(jù)類型

是一個(gè)值的集合和定義在此集合上的一組操作的總稱。

不同類型的變量，其所能取的值的范圍不同，所能進(jìn)行的操作不同。例如：整型值的范圍是：-32768--32767

操作是：+，-，*，/，%中國水利水電出版社1011.2抽象數(shù)據(jù)類型

(AbstractDataType

簡稱ADT)

是指一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作。中國水利水電出版社102例如:“整數(shù)”是一個(gè)抽象數(shù)據(jù)類型。

其數(shù)學(xué)特性和具體的計(jì)算機(jī)或語言無關(guān)?！俺橄蟆钡囊饬x在于強(qiáng)調(diào)數(shù)據(jù)類型的數(shù)學(xué)特性。中國水利水電出版社103例如，定義抽象數(shù)據(jù)類型“復(fù)數(shù)”

{數(shù)據(jù)對(duì)象：

D＝{e1,e2｜e1,e2∈RealSet}

數(shù)據(jù)關(guān)系：

R1＝{<e1,e2>

|e1

是復(fù)數(shù)的實(shí)數(shù)部分,

e2

是復(fù)數(shù)的虛數(shù)部分

}

ADTComplex中國水利水電出版社104基本操作：

AssignComplex(&Z,v1,v2)操作結(jié)果：構(gòu)造復(fù)數(shù)Z,其實(shí)部和虛部分別被賦以參數(shù)v1

和v2

的值。

DestroyComplex(&Z)操作結(jié)果：復(fù)數(shù)Z被銷毀。

GetReal(Z,&realPart)初始條件：復(fù)數(shù)已存在。操作結(jié)果：用realPart返回復(fù)數(shù)Z的實(shí)部值。中國水利水電出版社105

GetImag(Z,&ImagPart)初始條件：復(fù)數(shù)已存在。操作結(jié)果：用ImagPart返回復(fù)數(shù)Z的虛部值。

Add(z1,z2,&sum)初始條件：z1,z2是復(fù)數(shù)。操作結(jié)果：用sum返回兩個(gè)復(fù)數(shù)z1,z2的和值。}ADTComplex中國水利水電出版社106ADT有兩個(gè)重要特征:數(shù)據(jù)抽象

用ADT描述程序處理的實(shí)體時(shí)，強(qiáng)調(diào)的是其本質(zhì)的特征、其所能完成的功能以及它和外部用戶的接口（即外界使用它的方法）。數(shù)據(jù)封裝

將實(shí)體的外部特性和其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)分離，并且對(duì)外部用戶隱藏其內(nèi)部實(shí)現(xiàn)細(xì)節(jié)。中國水利水電出版社107抽象數(shù)據(jù)類型的描述方法：抽象數(shù)據(jù)類型可用三元組（D，S，P）表示。其中：

D

是數(shù)據(jù)對(duì)象，

S

是D上的關(guān)系集，

P

是對(duì)D的基本操作集。中國水利水電出版社108ADT

抽象數(shù)據(jù)類型名{

數(shù)據(jù)對(duì)象：〈數(shù)據(jù)對(duì)象的定義〉

數(shù)據(jù)關(guān)系：〈數(shù)據(jù)關(guān)系的定義〉

基本操作：〈基本操作的定義〉}ADT

抽象數(shù)據(jù)類型名其中基本操作的定義格式為:基本操作名（參數(shù)表）

初始條件：〈初始條件描述〉

操作結(jié)果：〈操作結(jié)果描述〉

中國水利水電出版社109賦值參數(shù)

只為操作提供輸入值；引用參數(shù)

以&打頭，除可提供輸入值外，還將返回操作結(jié)果。初始條件

描述了操作執(zhí)行之前數(shù)據(jù)結(jié)構(gòu)和參數(shù)應(yīng)滿足的條件，若不滿足，則操作失敗，并返回相應(yīng)出錯(cuò)信息。操作結(jié)果

說明了操作正常完成之后，數(shù)據(jù)結(jié)構(gòu)的變化狀況和應(yīng)返回的結(jié)果。若初始條件為空，則省略之。中國水利水電出版社110抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn)

抽象數(shù)據(jù)類型需要通過固有數(shù)據(jù)類型(高級(jí)編程語言中已實(shí)現(xiàn)的數(shù)據(jù)類型)來實(shí)現(xiàn)。例如，對(duì)以上定義的復(fù)數(shù)中國水利水電出版社111typedefstruct{

float

realpart；

float

imagpart；}complex；//-----存儲(chǔ)結(jié)構(gòu)的定義//-----基本操作的函數(shù)原型說明void

Assign(complex&Z,

floatrealval,floatimagval)；//

構(gòu)造復(fù)數(shù)Z,其實(shí)部和虛部分別被賦以參數(shù)//realval

和imagval

的值中國水利水電出版社112float

GetReal(cpmplexZ)；

//返回復(fù)數(shù)Z的實(shí)部值float

Getimag(cpmplexZ)；

//返回復(fù)數(shù)Z的虛部值voidadd(complexz1,complexz2,complex&sum)；

//以sum返回兩個(gè)復(fù)數(shù)z1,z2的和中國水利水電出版社113//-----基本操作的實(shí)現(xiàn)voidadd(complexz1,complexz2,complex&sum){

//以

sum

返回兩個(gè)復(fù)數(shù)z1,z2的和

sum.realpart=z1.realpart+z2.realpart;sum.imagpart=z1.imagpart+z2.imagpart;}

{其它省略}中國水利水電出版社1141.3算法和算法分析一、算法的特性二、算法描述三、算法性能分析與度量中國水利水電出版社115

算法是為了解決某類問題而設(shè)定的一個(gè)有限長的操作序列。一個(gè)算法必須滿足以下5個(gè)重要特性：1．有窮性

2．確定性

3．可行性4．有輸入

5．有輸出一、算法的特性中國水利水電出版社1161．有窮性對(duì)于任意一組合法輸入值，在執(zhí)行有窮步驟之后一定能結(jié)束，即：算法中的每個(gè)步驟都能在有限時(shí)間內(nèi)完成；

2.確定性

對(duì)于每種情況下所應(yīng)執(zhí)行的操作，在算法中都有確切的規(guī)定，使算法的執(zhí)行者或閱讀者都能明確其含義及如何執(zhí)行。并且在任何條件下，算法都只有一條執(zhí)行路徑；中國水利水電出版社1173．可行性算法中的所有操作都必須足夠基本，都可以通過已經(jīng)實(shí)現(xiàn)的基本操作運(yùn)算有限次實(shí)現(xiàn)之；4．有輸入作為算法加工對(duì)象的量值，通常體現(xiàn)為算法中的一組變量。有些輸入量需要在算法執(zhí)行過程中輸入，而有的算法表面上可以沒有輸入，實(shí)際上已被嵌入算法之中；中國水利水電出版社118

5．有輸出它是一組與“輸入”有確定關(guān)系的量值，是算法進(jìn)行信息加工后得到的結(jié)果，這種確定關(guān)系即為算法的功能。中國水利水電出版社119設(shè)計(jì)算法時(shí)，通常應(yīng)考慮達(dá)到以下目標(biāo)：1．正確性2.可讀性3．健壯性4．高效率與低存儲(chǔ)量需求二、算法描述中國水利水電出版社120三、算法性能分析與度量通常有兩種衡量算法效率的方法:

事后統(tǒng)計(jì)法事前分析估算法中國水利水電出版社121和算法執(zhí)行時(shí)間相關(guān)的因素：1．算法選用的策略2．問題的規(guī)模3．編寫程序的語言4．編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量5．計(jì)算機(jī)執(zhí)行指令的速度中國水利水電出版社122

一個(gè)特定算法的“運(yùn)行工作量”的大小，只依賴于問題的規(guī)模（通常用整數(shù)量n表示）。或者說，算法的“運(yùn)行工作量”是問題規(guī)模的函數(shù)。中國水利水電出版社123

假如，隨著問題規(guī)模n的增長，算法執(zhí)行時(shí)間的增長率和

f(n)的增長率相同，則可記作：T(n)=O(f(n))稱T(n)為算法的(漸近)時(shí)間復(fù)雜度中國水利水電出版社124如何估算算法的時(shí)間復(fù)雜度？中國水利水電出版社125算法=控制結(jié)構(gòu)+原操作（固有數(shù)據(jù)類型的操作）算法的執(zhí)行時(shí)間

=原操作(i)的執(zhí)行次數(shù)×原操作(i)的執(zhí)行時(shí)間

算法的執(zhí)行時(shí)間

與

原操作執(zhí)行次數(shù)之和成正比

中國水利水電出版社126

從算法中選取一種對(duì)于所研究的問題來說是基本操作

的原操作;

以該基本操作在算法中重復(fù)執(zhí)行的次數(shù)作為算法運(yùn)行時(shí)間的衡量準(zhǔn)則。中國水利水電出版社127例：分析以下程序段的時(shí)間復(fù)雜度。i=1;①while(i<=n)

i=i*2;②該算法的運(yùn)行時(shí)間由程序中所有語句的頻度（即該語句重復(fù)執(zhí)行的次數(shù)）之和構(gòu)成。解：分析：顯然，語句①的頻度是1。設(shè)語句②的頻度是f(n)，則有：即：f(n)≤log2n，取最大值：f(n)=log2n所以該程序段的時(shí)間復(fù)雜度：

T(n)=1+f(n)=1+log2n=

O(log2n)算法的時(shí)間復(fù)雜度是由嵌套最深層語句的頻度決定的。中國水利水電出版社128時(shí)間復(fù)雜度T(n)按數(shù)量級(jí)遞增順序?yàn)椋?/p>

注1：O()為漸近符號(hào)。注2：空間復(fù)雜度S(n)按數(shù)量級(jí)遞增順序也與上表類同。復(fù)雜度高復(fù)雜度低中國水利水電出版社129漸進(jìn)符號(hào)（O）的定義：

當(dāng)且僅當(dāng)存在一個(gè)正的常數(shù)

C，使得對(duì)所有的

nn0

有

g(n)

Cf(n)，則g(n)=

O(f(n))

3n+2=O(n)/*3n+24n,n2*/3n+3=O(n)/*3n+34n,n3*/100n+6=O(n) /*100n+6101n,n10*/10n2+4n+2=O(n2)/*10n2+4n+211n2,n5*/6*2n+n2=O(2n) /*6*2n+n27*2n,n4*/例：中國水利水電出版社130例1.9兩個(gè)矩陣相乘voidmult(inta[],intb[],int&c[]){

//以二維數(shù)組存儲(chǔ)矩陣元素，c為a和b的乘積

for(i=1;i<=n;++i)

for(j=1;j<=n;++j)

{c[i,j]=0;

for(k=1;k<=n;++k)c[i,j]+=a[i,k]*b[k,j];

}//for}//mult基本操作:

乘法操作時(shí)間復(fù)雜度:

O(n3)中國水利水電出版社131例1.10選擇排序

voidselect_sort(int&a[],intn)

{

//將a中整數(shù)序列重新排列成自小至大有序的整數(shù)序列。

}//select_sort基本操作:

比較(數(shù)據(jù)元素)操作時(shí)間復(fù)雜度:

O(n2)j=i;//選擇第i個(gè)最小元素for(k=i+1;k<n;++k)

if(a[k]<a[j])j=k;for(i=0;i<n-1;++i){if(j!=i)a[j]←→a[i]}中國水利水電出版社132算法的存儲(chǔ)空間需求算法的空間復(fù)雜度定義為:

表示隨著問題規(guī)模n

的增大，算法運(yùn)行所需存儲(chǔ)量的增長率與g(n)的增長率相同。S(n)=O(g(n))中國水利水電出版社133算法的存儲(chǔ)量包括:1．輸入數(shù)據(jù)所占空間2．程序本身所占空間；3．輔助變量所占空間。中國水利水電出版社1341.

熟悉各名詞、術(shù)語的含義，掌握基本概念。2.

理解算法5個(gè)要素的確切含義。本章學(xué)習(xí)要點(diǎn)3.

掌握計(jì)算語句頻度和估算算法時(shí)間復(fù)雜度的方法。數(shù)據(jù)結(jié)構(gòu)

（DataStructure）第2章線性表

線性結(jié)構(gòu)的基本特征:1．集合中必存在惟一的一個(gè)“第1元素”;2．集合中必存在惟一的一個(gè)“最后元素”3．除最后元素在外，均有惟一的后繼；4．除第1元素之外，均有惟一的前驅(qū)。線性結(jié)構(gòu)是一個(gè)數(shù)據(jù)元素的有序集。2.1

線性表的類型定義2.3線性表鏈?zhǔn)酱鎯?chǔ)及實(shí)現(xiàn)

2.4

線性表應(yīng)用舉例2.2線性表順序存儲(chǔ)及實(shí)現(xiàn)

2.1

線性表的

類型定義抽象數(shù)據(jù)類型線性表的定義如下：ADTList{數(shù)據(jù)對(duì)象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}//稱n

為線性表的表長;//稱n=0

時(shí)的線性表為空表。數(shù)據(jù)關(guān)系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}//設(shè)線性表為(a1，a2,...，ai，...，an),//稱i

為ai在線性表中的位序。

基本操作：初始化線性表銷毀線性表

……}ADTList常用操作：

GetElem(L,i,&e)

LocateElem(L,e,compare())

ListInsert(&L,i,e)

ListDelete(&L,i,&e)

利用上述定義的線性表類型

可以實(shí)現(xiàn)其它更復(fù)雜的操作

2.求

lc=la∪lb，其中，la、lb、lc有序

3.

靜態(tài)鏈表算法例：1.

求A=A∪B2.2線性表的順序存儲(chǔ)及實(shí)現(xiàn)最簡單的一種順序映象方法是：

令y

的存儲(chǔ)位置和x

的存儲(chǔ)位置相鄰。順序表示（映象）——

以x的存儲(chǔ)位置和y的存儲(chǔ)位置之間某種關(guān)系，表示邏輯關(guān)系<x,y>。

用一組地址連續(xù)的存儲(chǔ)單元

依次存放線性表中的數(shù)據(jù)元素

a1a2

…ai-1ai

…an線性表的起始地址，稱作線性表的基地址。線性表的順序表示：如何計(jì)算元素地址

？以“存儲(chǔ)位置相鄰”表示有序?qū)?lt;ai-1,ai>

即：LOC(ai)=LOC(ai-1)+

d

一個(gè)數(shù)據(jù)元素所占存儲(chǔ)量↑所有數(shù)據(jù)元素的存儲(chǔ)位置均取決于

第1個(gè)數(shù)據(jù)元素的存儲(chǔ)位置：

LOC(ai)=

LOC(a1)+(i-1)×d

↑基地址（若＝b）順序表動(dòng)態(tài)分配的順序存儲(chǔ)結(jié)構(gòu)描述：typedefstruct{

}SqList;//俗稱順序表ElemType*elem;//存儲(chǔ)空間基址int

length;

//當(dāng)前長度int

listsize;//當(dāng)前分配的存儲(chǔ)容量

//(以sizeof(ElemType)為單位)線性表的基本操作在順序表中的實(shí)現(xiàn)InitList(&L)

//結(jié)構(gòu)初始化LocateElem(L,e,compare())//查找ListInsert(&L,i,e)//插入元素ListDelete(&L,i)//刪除元素int

InitList_Sq(SqList&L,intmaxsize){//構(gòu)造一個(gè)最大容量為maxsize的順序表

}算法時(shí)間復(fù)雜度：O(1)L.elem=new

ElemType[maxsize];

//

為順序表動(dòng)態(tài)分配大小為maxsize

的數(shù)組空間if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=maxsize;returnOK;

ListInsert(&L,i,e)初始條件：操作結(jié)果：線性表L已存在，在L的第i個(gè)元素之前插入新的元素e，L的長度增1。//插入數(shù)據(jù)元素且1≤i≤LengthList(L)+1線性表插入操作－－算法2.4ListInsert(&L,i,e)的實(shí)現(xiàn)：首先分析:插入元素時(shí)，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？

(a1,…,ai-1,ai,…,an)改變?yōu)閍1a2

…ai-1ai

…ana1a2

…ai-1

…ai

ean<ai-1,ai><ai-1,e>,<e,ai>表的長度增加1(a1,…,

ai-1,

e,ai,…,an)

int

ListInsert_Sq(SqList&L,inti,ElemTypee){

//在順序表L的第i個(gè)元素之前插入新的元素e,

//i的合法范圍為1≤i≤L.length+1//算法的健壯性}算法時(shí)間復(fù)雜度為:O(ListLength(L))q=&(L.elem[i-1]);//q指示插入位置，指向第i個(gè)元素for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;//插入位置及之后的元素右移*q=e;//插入e++L.length;//表長增1returnOK;……元素右移if(L.length>=L.listsize)//當(dāng)前存儲(chǔ)空間已滿

returnOVERFLOW;或申請(qǐng)?jiān)俜峙洌≒.24）。if(i<1||i>L.length+1)

returnERROR;

//

插入位置不合法……//健壯性討論考慮移動(dòng)元素的平均情況:

假設(shè)在第

i個(gè)元素之前插入的概率，

則在長度為n

的線性表中插入一個(gè)元素所需移動(dòng)元素次數(shù)的期望值（平均次數(shù)）為：

若假定在線性表中任何一個(gè)位置上進(jìn)行插入的概率都是相等的，則移動(dòng)元素的期望值為：ListDelete(&L,i,&e)初始條件：操作結(jié)果：線性表L已存在且非空，刪除L

的第

i

個(gè)元素，并用e返回其值，L的長度減1。//刪除數(shù)據(jù)元素1≤i≤LengthList(L)線性表刪除操作－－算法2.5

ListDelete(&L,i,&e)的實(shí)現(xiàn)：首先分析：刪除元素時(shí)，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？

(a1,…,ai-1,ai,ai+1,…,an)改變?yōu)椋篴i+1…an<ai-1,ai>,<ai,ai+1><ai-1,ai+1>表的長度減少1a1a2

…

ai-1

ai

ai+1

…ana1a2

…

ai-1

(a1,…,

ai-1,

ai+1,…,an)int

ListDelete_Sq(SqList&L,int

i,ElemType&e){}for

(++p;p<=q;++p)

*(p-1)=*p;

//

被刪除元素之后的元素左移--L.length;//

表長減1returnOK;算法時(shí)間復(fù)雜度為:

O(ListLength(L))p=&(L.elem[i-1]);//p指向被刪除元素的位置e=*p;//被刪除元素的值賦給

eq=L.elem+L.length-1;//表尾元素的位置if((i<1)||(i>L.length))returnERROR;

//刪除位置不合法元素左移考慮刪除時(shí)移動(dòng)元素的平均情況:

假設(shè)刪除第

i個(gè)元素的概率為

,則在長度為n的線性表中刪除一個(gè)元素所需移動(dòng)元素次數(shù)的期望值（平均次數(shù)）為：若假定在線性表中任何一個(gè)位置上進(jìn)行刪除的概率都是相等的，則移動(dòng)元素的期望值為：LocateElem(L,e)初始條件：操作結(jié)果：線性表L已存在，e

為給定值返回L中第1個(gè)等于e的元素的

位序(≥1)。若這樣的元素不存在，則返回值為0。//定位函數(shù)順序表的查找與表中元素定位：23754138543817L.elemL.length=7L.listsizee=38pppppi12341850p可見，基本操作是，將順序表中的元素逐個(gè)和給定值e相比較。

intLocateElem_Sq(SqListL,ElemTypee)

{

//

在順序表中查詢第一個(gè)滿足判定條件的數(shù)據(jù)元素，

//若存在，則返回它的位序，否則返回0。

}

O(ListLength(L))if(i<=L.length)return

i;elsereturn0;算法的時(shí)間復(fù)雜度為：i=1;

//i的初值為第1元素的位序p=L.elem;

//p的初值為第1元素的存儲(chǔ)位置while(i<=L.length&&L.elem[i]!=e++i);//找到滿足條件的元素//沒有找到滿足條件的元素2.3線性表的鏈?zhǔn)酱婕皩?shí)現(xiàn)

一.概念

用一組地址任意的存儲(chǔ)單元存放線性表中的數(shù)據(jù)元素。2.3.1單鏈表的定義及存儲(chǔ)以元素（數(shù)據(jù)元素的映象－－數(shù)據(jù)域）

+

指針（指示后繼元素的存儲(chǔ)位置－－指針域）

=

結(jié)點(diǎn)（表示數(shù)據(jù)元素ai的存儲(chǔ)映象）以“結(jié)點(diǎn)的序列”表示的線性表

稱作鏈表

以線性表中第1個(gè)數(shù)據(jù)元素的存儲(chǔ)地址作為線性表的地址，稱作線性表的頭指針。頭結(jié)點(diǎn)

a1a2…...an^頭指針頭指針

有時(shí)為了操作方便，在第1個(gè)結(jié)點(diǎn)之前虛加一個(gè)“頭結(jié)點(diǎn)”，以指向頭結(jié)點(diǎn)的指針作為鏈表的頭指針?？罩羔樉€性表為空表時(shí)，頭結(jié)點(diǎn)的指針域?yàn)榭?/p>

TypedefstructLNode

{

ElemType

data;//數(shù)據(jù)域

struct

LNode

*next;//指針域

}

LNode,*LinkList;

二.結(jié)點(diǎn)和單鏈表的結(jié)構(gòu)描述2.3.2單鏈表基本操作的實(shí)現(xiàn)GetElem(L,i,e)//取第i個(gè)數(shù)據(jù)元素ListInsert(&L,i,e)//插入數(shù)據(jù)元素ListDelete(&L,i,e)//刪除數(shù)據(jù)元素ClearList(&L)

//將線性表置空CreateList(&L,n)

//生成含n個(gè)數(shù)據(jù)元素的鏈表L

線性表的取元素操作

GetElem(L,i,&e)

在單鏈表中的實(shí)現(xiàn):211830754256∧pppj123－－

算法2.10i=3i=7P=^j=7

因此，查找第i個(gè)數(shù)據(jù)元素的基本操作為移動(dòng)指針，比較

j

和

i.

單鏈表是一種順序存取的結(jié)構(gòu)，為找第

i個(gè)數(shù)據(jù)元素，必須從第1個(gè)數(shù)據(jù)元素起，依次順鏈查找。

令j為記數(shù)器，指針p

同步指向線性表中的第j

個(gè)數(shù)據(jù)元素。ai-1

線性表的操作

ListInsert

(&L,i,e)

在單鏈表中的實(shí)現(xiàn)－－算法2.11

有序?qū)?lt;ai-1,ai>

改變?yōu)?lt;ai-1,e>和<e,ai>

eaiai-1

因此，在單鏈表中第i個(gè)結(jié)點(diǎn)之前進(jìn)行插入的基本操作為:

找到線性表中第i-1個(gè)結(jié)點(diǎn)，然后修改其指向后繼的指針。

可見，在鏈表中插入結(jié)點(diǎn)只需要修改指針。若要在第i個(gè)結(jié)點(diǎn)之前插入元素，修改的是第i-1個(gè)結(jié)點(diǎn)的指針及為新插入結(jié)點(diǎn)的指針域賦值。s=newLNode;

//生成新結(jié)點(diǎn)if(s==NULL)returnERROR;s->data=e;s->next=p->next;p->next=s;

//插入returnOK;eai-1aiai-1sp//插入元素e線性表的操作ListDelete(&L,i,&e)在單鏈表中的實(shí)現(xiàn)－－算法2.12有序?qū)Γ?lt;ai-1,ai>和<ai,ai+1>

改變?yōu)椋?/p>

<ai-1,ai+1>ai-1aiai+1ai-1

在單鏈表中刪除第

i個(gè)結(jié)點(diǎn)的基本操作為:找到線性表中第i-1個(gè)結(jié)點(diǎn)，修改其指向后繼的指針。ai-1aiai+1ai-1q=p->next;p->next=q->next;

e=q->data;

delete(q);pq如何從線性表建立一個(gè)單鏈表？

鏈表是一個(gè)動(dòng)態(tài)的結(jié)構(gòu)，它不需要予分配空間，因此生成鏈表的過程，是一個(gè)一個(gè)結(jié)點(diǎn)逐個(gè)插入的過程。－－算法2.13例如：逆位序輸入n個(gè)數(shù)據(jù)元素的值，建立帶頭結(jié)點(diǎn)的單鏈表。操作步驟：1.建立一個(gè)“空表”；2.

輸入數(shù)據(jù)元素an，建立結(jié)點(diǎn)并插入；3.輸入數(shù)據(jù)元素an-1，建立結(jié)點(diǎn)并插入；ananan-14.依次類推，直至輸入a1為止。

最后一個(gè)結(jié)點(diǎn)的指針域的指針又指回第一個(gè)結(jié)點(diǎn)（頭結(jié)點(diǎn)）的鏈表。a1a2…...an2.3.3循環(huán)鏈表HH（a）帶頭結(jié)點(diǎn)的非空單循環(huán)鏈表（b）帶頭結(jié)點(diǎn)的空單循環(huán)鏈表單循環(huán)鏈表和非循環(huán)單鏈表的差別僅在于，判別鏈表中最后一個(gè)結(jié)點(diǎn)的條件不再是“后繼是否為空”：即p->next==NULL而是“后繼是否為頭結(jié)點(diǎn)”即

p->next==head

2.3.4雙向鏈表typedefstruct

DuLNode

{

ElemTypedata;

//數(shù)據(jù)域

struct

DuLNode

*prior;

//指向前驅(qū)的指針域

struct

DuLNode

*next;

//

指向后繼的指針域}

DuLNode,

*DuLinkList;數(shù)據(jù)域指針域結(jié)點(diǎn)指針域priordatanext

存儲(chǔ)數(shù)據(jù)元素存儲(chǔ)后繼結(jié)點(diǎn)的地址存儲(chǔ)前趨結(jié)點(diǎn)的地址

雙向鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向其直接后繼結(jié)點(diǎn)，另一個(gè)指向其直接前趨結(jié)點(diǎn)。雙向鏈表的操作特點(diǎn)：

“查詢”和單鏈表相同“插入”和“刪除”時(shí)需要同時(shí)修改兩個(gè)方向上的指針。ai-1aies->next=p->next;p->next=s;s->next->prior=s;s->prior=p;psai-1ai插入：在雙向鏈表中插入一個(gè)結(jié)點(diǎn)時(shí)指針的變化情況（2）：ai-1px①②③④ais->prior=p-prior;//完成圖示中的①p->prior->next=s;//完成圖示中的②

s->next=p;//完成圖示中的③p->prior=s;//完成圖示中的④sP.36圖2.16prior

nextai-1刪除aiai+1p->next=p