軟件技術(shù)基礎(chǔ)課件

第1章基礎(chǔ)知識(shí)1.1計(jì)算機(jī)軟件概述1.1.1計(jì)算機(jī)軟件及其分類計(jì)算機(jī)系統(tǒng)由計(jì)算機(jī)硬件系統(tǒng)和計(jì)算機(jī)軟件系統(tǒng)組成。計(jì)算機(jī)硬件系統(tǒng)是指實(shí)際的物理設(shè)備，包括計(jì)算機(jī)的主機(jī)和外圍設(shè)備。計(jì)算機(jī)軟件系統(tǒng)，是指能指揮計(jì)算機(jī)工作的程序、程序運(yùn)行時(shí)所需要的數(shù)據(jù)以及與這些程序和數(shù)據(jù)有關(guān)的文字說(shuō)明和圖表資料。其中文字說(shuō)明和圖表資料又稱為文檔。1．系統(tǒng)軟件系統(tǒng)軟件是指管理、監(jiān)控和維護(hù)計(jì)算機(jī)資源(包括硬件和軟件)，并提供用戶與計(jì)算機(jī)之間界面等工具的軟件。（1）操作系統(tǒng)（2）程序設(shè)計(jì)語(yǔ)言與語(yǔ)言處理程序（3）工具軟件2．應(yīng)用軟件常見的應(yīng)用軟件有以下幾種:①各種信息管理軟件。②辦公自動(dòng)化系統(tǒng)。③各種文字處理軟件。④各種輔助設(shè)計(jì)軟件以及輔助教學(xué)軟件。⑤各種軟件包，如數(shù)值計(jì)算程序庫(kù)、圖形軟件包等。1.1.2程序設(shè)計(jì)語(yǔ)言及其語(yǔ)言處理程序程序設(shè)計(jì)語(yǔ)言一般分為機(jī)器語(yǔ)言、匯編語(yǔ)言和高級(jí)語(yǔ)言三類。1．機(jī)器語(yǔ)言機(jī)器語(yǔ)言是最底層的計(jì)算機(jī)語(yǔ)言。用機(jī)器語(yǔ)言編寫的程序，計(jì)算機(jī)硬件可以直接識(shí)別。2．匯編語(yǔ)言匯編語(yǔ)言與機(jī)器語(yǔ)言一般是一一對(duì)應(yīng)的，用匯編語(yǔ)言編寫的程序也比機(jī)器語(yǔ)言程序易讀、易檢查、易修改。將匯編語(yǔ)言源程序翻譯成機(jī)器語(yǔ)言程序的程序稱為匯編程序。3．高級(jí)語(yǔ)言機(jī)器語(yǔ)言和匯編語(yǔ)言都是面向機(jī)器的語(yǔ)言，一般稱為低級(jí)語(yǔ)言。面向問(wèn)題的程序設(shè)計(jì)語(yǔ)言，稱為高級(jí)語(yǔ)言。高級(jí)語(yǔ)言與具體的計(jì)算機(jī)硬件無(wú)關(guān)，其表達(dá)方式接近于被描述的問(wèn)題，易為人們接受和掌握。1.2操作系統(tǒng)的基本概念1.2.1操作系統(tǒng)的功能與任務(wù)操作系統(tǒng)是最基本的和核心的系統(tǒng)軟件。操作系統(tǒng)實(shí)際上是由一些程序模塊組成的，它們是系統(tǒng)軟件中最基本的部分，其主要作用有以下幾個(gè)方面：①管理系統(tǒng)資源。②為用戶提供資源共享的條件和環(huán)境，并對(duì)資源的使用進(jìn)行合理調(diào)度。③提供輸入/輸出的方便環(huán)境，簡(jiǎn)化用戶的輸入/輸出工作，提供良好的用戶界面。④規(guī)定用戶的接口，發(fā)現(xiàn)、處理或報(bào)告計(jì)算機(jī)操作過(guò)程中所發(fā)生的各種錯(cuò)誤。操作系統(tǒng)的功能和任務(wù)主要有以下五個(gè)方面。1．處理機(jī)管理處理機(jī)管理的主要任務(wù)是：充分發(fā)揮處理機(jī)的作用，提高它的使用效率。2．存儲(chǔ)器管理存儲(chǔ)器管理的主要任務(wù)是：對(duì)有限的內(nèi)存儲(chǔ)器進(jìn)行合理的分配，以滿足多個(gè)用戶程序運(yùn)行的需要。3．設(shè)備管理設(shè)備管理的主要任務(wù)是：有效地管理各種外部設(shè)備，使這些設(shè)備充分發(fā)揮效率；并且還要給用戶提供簡(jiǎn)單而易于使用的接口，以便在用戶不了解設(shè)備性能的情況下，也能很方便地使用它們。4．文件管理文件管理的主要任務(wù)是：實(shí)現(xiàn)惟一地標(biāo)識(shí)計(jì)算機(jī)系統(tǒng)中的每一組信息，以便能夠?qū)λ鼈冞M(jìn)行合理地訪問(wèn)和控制；以及有條理地組織這些信息，使用戶能夠方便且安全地使用它們。5．作業(yè)管理它的主要任務(wù)是：對(duì)所有的用戶作業(yè)進(jìn)行分類，并且根據(jù)某種原則，源源不斷地選取一些作業(yè)交給計(jì)算機(jī)去處理。1.2.2操作系統(tǒng)的發(fā)展過(guò)程1．手工操作階段2．成批處理系統(tǒng)3．執(zhí)行程序系統(tǒng)4．多道程序系統(tǒng)的引入1.2.3操作系統(tǒng)的分類1．多道批處理操作系統(tǒng)多道批處理操作系統(tǒng)包含“多道”和“批處理”兩層意思。“多道”是指在計(jì)算機(jī)內(nèi)存中存入多個(gè)用戶作業(yè)?！芭幚怼笔侵高@樣一種操作方式，在外存中存入大量的后備作業(yè)，作業(yè)的運(yùn)行完全由系統(tǒng)控制，用戶與其作業(yè)之間沒(méi)有交互作用，用戶不能直接控制其作業(yè)的運(yùn)行，通常稱這種方式為批操作或脫機(jī)操作。2．分時(shí)操作系統(tǒng)在分時(shí)操作系統(tǒng)中，多個(gè)用戶分享使用同一臺(tái)計(jì)算機(jī)，即在一臺(tái)計(jì)算機(jī)上聯(lián)接若干臺(tái)終端，每個(gè)用戶可以獨(dú)占一臺(tái)終端。分時(shí)操作系統(tǒng)具有以下幾方面的特點(diǎn)：①同時(shí)性。②獨(dú)立性。③及時(shí)性。④交互性。3．實(shí)時(shí)操作系統(tǒng)所謂實(shí)時(shí)，是指對(duì)隨機(jī)發(fā)生的外部事件作出及時(shí)的響應(yīng)并對(duì)其進(jìn)行處理。具有實(shí)時(shí)要求的系統(tǒng)稱之為實(shí)時(shí)系統(tǒng)。4．通用操作系統(tǒng)5．優(yōu)良的操作環(huán)境

——多窗口系統(tǒng)所謂多窗口，就是把計(jì)算機(jī)的顯示屏幕劃分出多個(gè)區(qū)域，每個(gè)區(qū)域稱為一個(gè)窗口，每個(gè)窗口負(fù)責(zé)處理和顯示某一類信息。

向用戶提供友好界面是多窗口系統(tǒng)主要體現(xiàn)在以下幾方面：（1）靈活、方便的窗口操作（2）彈出式菜單（3）命令對(duì)話框1.3算法1.3.1算法的基本概念算法是指解題方案的準(zhǔn)確而完整的描述。通常，算法又分為數(shù)值型算法與非數(shù)值型算法。非數(shù)值型算法又稱為符號(hào)處理。1．算法的基本特征（1）可行性①算法中的每一個(gè)步驟必須能夠?qū)崿F(xiàn)。②算法執(zhí)行的結(jié)果要能夠達(dá)到預(yù)期的目的。（2）確定性算法的確定性（Definiteness），是指算法中的每一個(gè)步驟都必須是有明確定義的。（3）有窮性算法的有窮性（Finiteness），是指算法必須能在有限的時(shí)間內(nèi)做完，即算法必須能在執(zhí)行有限個(gè)步驟之后終止。（4）擁有足夠的情報(bào)2．算法的基本要素一個(gè)算法通常由兩種基本要素組成：一是對(duì)數(shù)據(jù)對(duì)象的運(yùn)算和操作，二是算法的控制結(jié)構(gòu)。（1）算法中對(duì)數(shù)據(jù)的運(yùn)算和操作（2）算法的控制結(jié)構(gòu)1.3.2算法描述語(yǔ)言1．符號(hào)與表達(dá)式符號(hào)是以字母開頭的字母和數(shù)字的有限串，主要用以表示變量名、數(shù)組名等，必要時(shí)也用來(lái)表示語(yǔ)句標(biāo)號(hào)。在語(yǔ)句標(biāo)號(hào)后應(yīng)跟隨一個(gè)冒號(hào)，然后是語(yǔ)句。例如：

loop：i=i+1在算法中，算術(shù)運(yùn)算符沿用數(shù)學(xué)中的表示法。關(guān)系運(yùn)算符用=、≠、＜、＞、≤、≥等表示。邏輯運(yùn)算符用and（與）、or（或）、not（非）來(lái)表示。2．賦值語(yǔ)句賦值語(yǔ)句的形式為：a=e3．控制轉(zhuǎn)移語(yǔ)句無(wú)條件轉(zhuǎn)移語(yǔ)句的形式為：GOTO標(biāo)號(hào)4．循環(huán)語(yǔ)句循環(huán)語(yǔ)句有兩種形式：一是WHILE語(yǔ)句，二是FOR語(yǔ)句。WHILE語(yǔ)句的形式為：

WHILECDOSFOR語(yǔ)句的形式為：FORi=initTOlimitBYstepDOS5．其他語(yǔ)句1.3.3算法設(shè)計(jì)基本方法1．列舉法列舉法的基本思想是，根據(jù)提出的問(wèn)題，列舉所有可能的情況，并用問(wèn)題中給定的條件檢驗(yàn)?zāi)男┦切枰?，哪些是不需要的?．枚舉歸納法枚舉歸納法的基本思想是，通過(guò)列舉足夠多（但不是全部）的特殊情況，發(fā)現(xiàn)其中的一些規(guī)律，經(jīng)過(guò)分析，最后找出一般的關(guān)系。3．遞推遞推是指從已知的初始條件出發(fā)，逐次推出所要求的各中間結(jié)果和最后結(jié)果。4．遞歸這種將問(wèn)題逐層分解的過(guò)程，實(shí)際上并沒(méi)有對(duì)問(wèn)題進(jìn)行求解，而只是當(dāng)解決了最后那些最簡(jiǎn)單的問(wèn)題后，再沿著原來(lái)分解的逆過(guò)程逐步進(jìn)行綜合，這就是遞歸的基本思想。由此可以看出，遞歸的基礎(chǔ)也是歸納。遞歸分為直接遞歸與間接遞歸兩種。如果一個(gè)算法P直接調(diào)用自己則稱為直接遞歸。如果算法P調(diào)用另一個(gè)算法Q，而算法Q又調(diào)用算法P，則稱為間接遞歸調(diào)用。5．減半遞推技術(shù)“減半”是指將問(wèn)題的規(guī)模減半，而問(wèn)題的性質(zhì)不變。“遞推”是指重復(fù)“減半”的過(guò)程。6．回溯法1.3.4算法的復(fù)雜度分析算法的復(fù)雜度主要包括時(shí)間復(fù)雜度和空間復(fù)雜度。1．算法的時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度，是指執(zhí)行算法所需要的計(jì)算工作量。（1）平均性態(tài)分析平均性態(tài)分析(AverageBehavior)，是指用各種特定輸入下的基本運(yùn)算次數(shù)的帶權(quán)平均值來(lái)度量算法的工作量。（2）最壞情況復(fù)雜性分析最壞情況分析(Worst–CaseComplexity)，是指在規(guī)模為n時(shí)，算法所執(zhí)行的基本運(yùn)算的最大次數(shù)。數(shù)據(jù)是計(jì)算機(jī)化的信息，即計(jì)算機(jī)處理的對(duì)象是數(shù)據(jù)。各數(shù)據(jù)之間的一定關(guān)系，稱為數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)位置有著一定的關(guān)系，稱為數(shù)據(jù)的物理結(jié)構(gòu)（或存儲(chǔ)結(jié)構(gòu)）。數(shù)據(jù)結(jié)構(gòu)作為計(jì)算機(jī)的一門學(xué)科，它研究的內(nèi)容，通常要涉及以下三個(gè)方面的問(wèn)題：①數(shù)據(jù)的邏輯結(jié)構(gòu)；②數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)；③對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算。主要目的是為了提高數(shù)據(jù)處理的效率。包括兩個(gè)方面：一是提高數(shù)據(jù)處理的速度，二是盡量節(jié)省在數(shù)據(jù)處理過(guò)程中所占用的計(jì)算機(jī)存儲(chǔ)空間。2.1數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素的集合。組成該數(shù)據(jù)結(jié)構(gòu)（包括邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)）的數(shù)據(jù)元素稱為一個(gè)結(jié)點(diǎn)。在數(shù)據(jù)處理領(lǐng)域中，每一個(gè)需要處理的對(duì)象都可以抽象成數(shù)據(jù)元素。在具有相同特征的數(shù)據(jù)元素集合中，各個(gè)數(shù)據(jù)元素之間存在有某種關(guān)系，反映了該集合中的數(shù)據(jù)元素所固有的一種結(jié)構(gòu)。數(shù)據(jù)元素之間的任何關(guān)系都可以用前后件關(guān)系來(lái)描述。1．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)所謂結(jié)構(gòu)實(shí)際上就是指數(shù)據(jù)元素之間的前后件關(guān)系。一個(gè)數(shù)據(jù)結(jié)構(gòu)應(yīng)包含以下兩方面的信息：①表示數(shù)據(jù)元素的信息。②表示各數(shù)據(jù)元素之間的前后件關(guān)系的信息。數(shù)據(jù)元素之間的前后件關(guān)系是指它們的邏輯關(guān)系，而與它們?cè)谟?jì)算機(jī)中的存儲(chǔ)位置無(wú)關(guān)。數(shù)據(jù)結(jié)構(gòu)實(shí)際上是數(shù)據(jù)的邏輯結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)，是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個(gè)要素：一是數(shù)據(jù)元素的集合，通常記為D；二是D上的關(guān)系，它反映了D中各數(shù)據(jù)元素之間的前后件關(guān)系，通常記為R。即一個(gè)數(shù)據(jù)結(jié)構(gòu)可以表示成

B=(D,R)例2.1一年四季的數(shù)據(jù)結(jié)構(gòu)可以表示成B=(D,R)D={春,夏,秋,冬}R={(春,夏),(夏,秋),(秋,冬)}例2.3n維向量X=(x1,x2,…,xn)也是一種數(shù)據(jù)結(jié)構(gòu)。即X=(D,R)，其中數(shù)據(jù)元素的集合為：D={x1,x2,…,xn}關(guān)系為：R={(x1,x2),(x2,x3),…,(xn–1,xn)}例如，m×n的矩陣是一個(gè)數(shù)據(jù)結(jié)構(gòu)。在這個(gè)數(shù)據(jù)結(jié)構(gòu)中，矩陣的每一行Ai=(ai1，ai2，…，ain)，i=1,2,…,m可以看成是它的一個(gè)數(shù)據(jù)元素。即這個(gè)數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)元素的集合為：D={A1，A2，…，Am}D上的一個(gè)關(guān)系為：R={(A1，A2)，(A2，A3)，…，(Ai，Ai+1)，…Am–1，Am}}顯然，數(shù)據(jù)結(jié)構(gòu)A中的每一個(gè)數(shù)據(jù)元素Ai（i=1,2,…,m）又是另一個(gè)數(shù)據(jù)結(jié)構(gòu)，即數(shù)據(jù)元素的集合為：Di={ai1，ai2,…，ain}Di上的一個(gè)關(guān)系為：Ri={(ai1，ai2)，(ai2，ai3)，…，(ai，ai,j+1)，…，(ai,n–1，ain)}一個(gè)數(shù)據(jù)結(jié)構(gòu)除了用二元關(guān)系表示外，還可以直觀地用圖形表示。反映家庭成員間輩份關(guān)系的數(shù)據(jù)結(jié)構(gòu)可以用圖2.2所示的圖形表示。例2.4用圖形表示數(shù)據(jù)結(jié)構(gòu)B=（D，R），其中D={di|1≤i≤7}={d1，d2，d3，d4，d5，d6，d7}R={(d1，d3)，(d1，d7)，(d2，d4)，(d3，d6)，(d4，d5)}這個(gè)數(shù)據(jù)結(jié)構(gòu)的圖形表示如圖2.3所示。在數(shù)據(jù)結(jié)構(gòu)中，沒(méi)有前件的結(jié)點(diǎn)稱為根結(jié)點(diǎn)；沒(méi)有后件的結(jié)點(diǎn)稱為終端結(jié)點(diǎn)（也稱為葉子結(jié)點(diǎn)）。通常，一個(gè)數(shù)據(jù)結(jié)構(gòu)中的元素結(jié)點(diǎn)可能是在動(dòng)態(tài)變化的。數(shù)據(jù)結(jié)構(gòu)中的結(jié)點(diǎn)（即數(shù)據(jù)元素）個(gè)數(shù)在動(dòng)態(tài)地變化，而且，各數(shù)據(jù)元素之間的關(guān)系也有可能在動(dòng)態(tài)地變化。如果在一個(gè)數(shù)據(jù)結(jié)構(gòu)中一個(gè)數(shù)據(jù)元素都沒(méi)有，則稱該數(shù)據(jù)結(jié)構(gòu)為空的數(shù)據(jù)結(jié)構(gòu)。在一個(gè)空的數(shù)據(jù)結(jié)構(gòu)中插入一個(gè)新的元素后就變?yōu)榉强?；在只有一個(gè)數(shù)據(jù)元素的數(shù)據(jù)結(jié)構(gòu)中，將該元素刪除后就變?yōu)榭盏臄?shù)據(jù)結(jié)構(gòu)。將數(shù)據(jù)結(jié)構(gòu)分為兩大類型：線性結(jié)構(gòu)與非線性結(jié)構(gòu)。如果一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)滿足下列兩個(gè)條件：①有且只有一個(gè)根結(jié)點(diǎn)；②每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)。線性結(jié)構(gòu)又稱線性表。例如，圖2.4所示的數(shù)據(jù)結(jié)構(gòu)顯然是滿足上述兩個(gè)條件的，但它不屬于線性結(jié)構(gòu)這個(gè)類型，因?yàn)槿绻谶@個(gè)數(shù)據(jù)結(jié)構(gòu)中刪除結(jié)點(diǎn)A后，就不滿足上述的條件①。一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱之為非線性結(jié)構(gòu)。線性結(jié)構(gòu)與非線性結(jié)構(gòu)都可以是空的數(shù)據(jù)結(jié)構(gòu)。如果對(duì)該數(shù)據(jù)結(jié)構(gòu)的運(yùn)算是按線性結(jié)構(gòu)的規(guī)則來(lái)處理的，則屬于線性結(jié)構(gòu)；否則屬于非線性結(jié)構(gòu)。2．?dāng)?shù)據(jù)的存儲(chǔ)結(jié)構(gòu)一個(gè)數(shù)據(jù)結(jié)構(gòu)中的各數(shù)據(jù)元素在計(jì)算機(jī)存儲(chǔ)空間中的位置關(guān)系與邏輯關(guān)系是有可能不同的。數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)。在數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)中，不僅要存放各數(shù)據(jù)元素的信息，還需要存放各數(shù)據(jù)元素之間的前后件關(guān)系的信息。常用的存儲(chǔ)結(jié)構(gòu)有順序、鏈接、索引、散列等存儲(chǔ)結(jié)構(gòu)。（1）順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)主要用于線性結(jié)構(gòu)。在這種存儲(chǔ)方式中，把邏輯上相鄰的數(shù)據(jù)元素結(jié)點(diǎn)存儲(chǔ)在物理上相鄰的存儲(chǔ)單元中，各結(jié)點(diǎn)之間的關(guān)系由存儲(chǔ)單元的鄰接關(guān)系來(lái)體現(xiàn)。圖2.5是將線性結(jié)構(gòu){(K1，K2)，(K2，K3)，(K3，K4)，(K4，K5)，(K5，K6)，(K6，K7)}順序地存放在存儲(chǔ)單元中的示意圖。（2）鏈接存儲(chǔ)結(jié)構(gòu)在鏈接存儲(chǔ)結(jié)構(gòu)中，每個(gè)存儲(chǔ)結(jié)點(diǎn)要有兩部分組成：一部分用于存放數(shù)據(jù)信息，另一部分用于存放指針。其中指針用于指向該結(jié)點(diǎn)的前件或后件。利用鏈接存儲(chǔ)方式也可以存儲(chǔ)非線性結(jié)構(gòu)。圖2.7（a）和（b）分別為一棵二叉樹的邏輯結(jié)構(gòu)與鏈接存儲(chǔ)結(jié)構(gòu)的示意圖。（3）索引存儲(chǔ)結(jié)構(gòu)索引存儲(chǔ)結(jié)構(gòu)是指將數(shù)據(jù)元素按索引函數(shù)值進(jìn)行分組，具有相同索引函數(shù)值的數(shù)據(jù)元素被分在同一組中，而同一組中的元素再按某種存儲(chǔ)方式（順序存儲(chǔ)或鏈接存儲(chǔ)）進(jìn)行存儲(chǔ)。（4）散列存儲(chǔ)結(jié)構(gòu)散列存儲(chǔ)結(jié)構(gòu)是指根據(jù)數(shù)據(jù)元素的關(guān)鍵字值來(lái)確定其存儲(chǔ)地址。2.2線性表2.2.1線性表順序存儲(chǔ)結(jié)構(gòu)線性表由一組數(shù)據(jù)元素構(gòu)成。數(shù)據(jù)元素可以是簡(jiǎn)單項(xiàng)（如上述例子中的數(shù)、字母、季節(jié)名等）。在稍微復(fù)雜的線性表中，一個(gè)數(shù)據(jù)元素還可以由若干個(gè)數(shù)據(jù)項(xiàng)組成。例如，某班的學(xué)生情況登記表，如表2.1所示。學(xué)生情況登記表就是一個(gè)文件，其中每一個(gè)學(xué)生的情況就是一個(gè)記錄。綜上所述，線性表是由n（n≥0）個(gè)數(shù)據(jù)元素a1，a2，…，an組成的一個(gè)有限序列。表中的每一個(gè)數(shù)據(jù)元素，除了第一個(gè)外，有且只有一個(gè)前件；除了最后一個(gè)外，有且只有一個(gè)后件。即線性表或是一個(gè)空表，或可以表示為：(a1，a2，…，ai，…，an)其中ai(i=1，2，…，n)是屬于數(shù)據(jù)對(duì)象的元素，通常也稱其為線性表中的一個(gè)結(jié)點(diǎn)。非空線性表有如下一些結(jié)構(gòu)特征：①有且只有一個(gè)根結(jié)點(diǎn)a1，它無(wú)前件。②有且只有一個(gè)終端結(jié)點(diǎn)an，它無(wú)后件。③除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其他所有結(jié)點(diǎn)有且只有一個(gè)前件，也有且只有一個(gè)后件。線性表中結(jié)點(diǎn)的個(gè)數(shù)n稱為線性表的長(zhǎng)度。當(dāng)n=0時(shí)，稱為空表。在計(jì)算機(jī)中存放線性表，一種最簡(jiǎn)單的方法是順序存儲(chǔ)，也稱為順序分配。順序存儲(chǔ)的線性表通常稱為順序表。線性表的順序存儲(chǔ)結(jié)構(gòu)具有以下兩個(gè)基本特點(diǎn)：①線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的。②線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。在計(jì)算機(jī)中的順序存儲(chǔ)結(jié)構(gòu)如圖2.8所示。在程序設(shè)計(jì)語(yǔ)言中，通常定義一個(gè)一維數(shù)組來(lái)表示線性表的順序存儲(chǔ)空間。因?yàn)槌绦蛟O(shè)計(jì)語(yǔ)言中的一維數(shù)組與計(jì)算機(jī)中實(shí)際的存儲(chǔ)空間結(jié)構(gòu)是類似的，這就便于用程序設(shè)計(jì)語(yǔ)言對(duì)線性表進(jìn)行各種運(yùn)算處理。建立一個(gè)空線性表的順序存儲(chǔ)空間（即初始化線性表的順序存儲(chǔ)空間）的C語(yǔ)言描述如下：#include"stdlib.h"voidinitsl(v,m,n)/*初始化順序表*/ET*v；/*v返回順序表空間的首地址,ET表示元素的數(shù)據(jù)類型*/intm,*n；/*m為順序表的空間容量（字節(jié)數(shù)）,n返回線性表的長(zhǎng)度*/{v=malloc(m*sizeof(ET))；/*申請(qǐng)順序表空間*/*n=0；/*線性表長(zhǎng)度為0*/return；}2.2.2順序表的插入與刪除1．順序表的插入運(yùn)算首先舉一個(gè)例子來(lái)說(shuō)明如何在順序存儲(chǔ)結(jié)構(gòu)的線性表中插入一個(gè)新元素。一般來(lái)說(shuō)，設(shè)長(zhǎng)度為n的線性表為：要在線性表的第i個(gè)元素ai之前插入一個(gè)新元素b，插入后得到長(zhǎng)度為n+1的線性表為：則插入前后的兩線性表中的元素滿足如下關(guān)系：在線性表順序存儲(chǔ)的情況下，要插入一個(gè)新元素，由于數(shù)據(jù)元素的移動(dòng)而消耗較多的處理時(shí)間，因此其效率是很低的，特別是在線性表比較大的情況下更為突出。下面是線性表在順序存儲(chǔ)結(jié)構(gòu)下插入算法的C語(yǔ)言描述。voidinsl(v,m,n,i,b)/*順序表的插入*/ETv[],b；/*v為順序表空間,b為插入的元素*/intm,*n,i；/*m為順序表空間容量,n為指向線性表長(zhǎng)度的指針,i為插入元素的序號(hào)*/{if(*n==m)/*順序表空間已滿,上溢錯(cuò)誤,返回*/{printf("overflow\n")；return；}if(i＞*n–1)i=*n+1；/*在線性表的最后插入*/if(i＜1＝i=1；/*在線性表的第1個(gè)元素之前插入*/for(j=*n；j＜=i；j––＝/*插入位置以后的元素依次往后移動(dòng)一個(gè)位置*/v[j]=v[j–1]；

v[i–1]=b；/*插入元素b*/*n=*n+1；/*線性表長(zhǎng)度加1*/return；}2．順序表的刪除運(yùn)算首先舉一個(gè)例子來(lái)說(shuō)明如何在順序存儲(chǔ)結(jié)構(gòu)的線性表中刪除一個(gè)元素。一般來(lái)說(shuō)，設(shè)長(zhǎng)度為n的線性表為：現(xiàn)要?jiǎng)h除第i個(gè)元素，刪除后得到長(zhǎng)度為n–1的線性表為：則刪除前后的兩線性表中的元素滿足如下關(guān)系：在線性表順序存儲(chǔ)的情況下，要?jiǎng)h除一個(gè)元素，由于數(shù)據(jù)元素的移動(dòng)而消耗較多的處理時(shí)間，其效率也是很低的，特別是在線性表比較大的情況下更為突出。下面是線性表在順序存儲(chǔ)結(jié)構(gòu)下刪除算法的C語(yǔ)言描述。voiddesl(v,m,n,i)/*順序表的刪除*/ETv[]；/*順序表空間*/intm,*n,i；/*m為順序表空間容量,n為指向線性表長(zhǎng)度的指針,i為刪除元素的序號(hào)*/{if(*n==0)/*線性表為空,下溢錯(cuò)誤,返回*/printf("underflow\n")；return；}if((i＜1)||(i＞*n))/*線性表中沒(méi)有這種下標(biāo)的元素,返回*/printf("Notthiselementinthelist\n")；return；}for(j=i；j＜=*n–1；j++＝/*第i個(gè)以后的元素依次往前移動(dòng)一個(gè)位置*/v[j–1]=v[j]；

*n=*n–1；/*線性表長(zhǎng)度減1*/return；}2.3棧及其應(yīng)用2.3.1棧的基本概念棧實(shí)際上也是線性表，只不過(guò)是一種特殊的線性表。棧(stack)是限定在一端進(jìn)行插入與刪除的線性表。往棧中插入一個(gè)元素稱為入棧運(yùn)算，從棧中刪除一個(gè)元素（即刪除棧頂元素）稱為退棧運(yùn)算。棧頂指針top動(dòng)態(tài)反映了棧中元素的變化情況。圖2.11是棧的示意圖。圖2.12中給出了具有嵌套調(diào)用關(guān)系的五個(gè)程序，其中主程序要調(diào)用子程序SUB1，SUB1要調(diào)用子程序SUB2，SUB2要調(diào)用子程序SUB3，SUB3要調(diào)用子程序SUB4，SUB4不再調(diào)用其他子程序了。計(jì)算機(jī)系統(tǒng)在處理時(shí)要用一個(gè)棧來(lái)動(dòng)態(tài)記憶調(diào)用過(guò)程中的路徑，其基本原則如下：①在開始執(zhí)行程序前，建立一個(gè)棧，其初始狀態(tài)為空。②當(dāng)發(fā)生調(diào)用時(shí)，將當(dāng)前調(diào)用的返回點(diǎn)地址（在圖2.12中用語(yǔ)句標(biāo)號(hào)表示）入棧。③當(dāng)遇到從某個(gè)子程序返回時(shí)，從棧頂取出返回點(diǎn)地址。2.3.2棧的順序存儲(chǔ)及其運(yùn)算在棧的順序存儲(chǔ)空間S（1：m）中，S（bottom）通常為棧底元素（在棧非空的情況下），S（top）為棧頂元素。top=0表示棧空；top=m表示棧滿。建立一個(gè)空棧的順序存儲(chǔ)空間（即初始化棧的順序存儲(chǔ)空間）的C語(yǔ)言描述如下：#include"stdlib.h"voidinit_stack(s,m,top)/*初始化?？臻g*/ET*s；/*?？臻g*/intm,*top；/*m為棧空間容量,top為棧頂指針*/{s=malloc(m*sizeof(ET))；/*申請(qǐng)容量為m的?？臻g*/*top=0；/*置?？?/return；}棧的基本運(yùn)算有三種：入棧、退棧與讀棧頂元素。下面分別介紹在順序存儲(chǔ)結(jié)構(gòu)下棧的這三種運(yùn)算。（1）入棧運(yùn)算入棧運(yùn)算是指在棧頂位置插入一個(gè)新元素。入棧運(yùn)算的C語(yǔ)言描述。voidpush(s,m,top,x)/*在容量為m的棧S中插入一個(gè)元素x（入棧運(yùn)算）*/ETs[],x；/*s為?？臻g,x為入棧元素*/intm,*top；/*m為?？臻g容量,top為棧頂指針*/{if(*top==m)/*棧滿,上溢錯(cuò)誤,返回*/{printf("Stack–overflow\n")；return；}*top=*top+1；/*棧頂指針進(jìn)一*/s[*top–1]=x；/*將元素x插入到棧頂位置*/return；}（2）退棧運(yùn)算退棧運(yùn)算是指取出棧頂元素并賦給一個(gè)指定的變量。這個(gè)運(yùn)算有兩個(gè)基本操作：首先將棧頂元素（棧頂指針指向的元素）賦給一個(gè)指定的變量，然后將棧頂指針退一（即top減1）。退棧運(yùn)算的C語(yǔ)言描述。voidpop(s,m,top,y)/*在容量為m的棧S中刪除棧頂元素（退棧運(yùn)算）*/ETs[],*y；/*s為?？臻g,y指向存放退棧元素的地址*/intm,*top；/*m為棧空間容量,top為棧頂指針*/{if(*top==0)/*?？?下溢錯(cuò)誤,返回*/{printf("Stack–underflow\n")；return；}*y=s[*top–1]；/*讀取棧頂元素*/*top=*top–1；/*棧頂指針退一*/return；}（3）讀棧頂元素讀棧頂元素是指將棧頂元素賦給一個(gè)指定的變量。必須注意，這個(gè)運(yùn)算不刪除棧頂元素，只是將它的值賦給一個(gè)變量，因此，在這個(gè)運(yùn)算中，棧頂指針不會(huì)改變。讀棧頂元素算法的C語(yǔ)言描述。voidtop(s,m,top,y)/*讀棧頂元素*/ETs[],*y；/*s為?？臻g,y指向存放棧頂元素的地址*/intm,*top；/*m為?？臻g容量,top為棧頂指針*/{if(*top==0)/*棧空錯(cuò)誤,返回*/{printf("Stackempty\n")；return；}*y=s[*top–1]；/*讀取棧頂元素*/return；}2.3.3棧的應(yīng)用2.3.1中討論的子程序嵌套調(diào)用就是棧的一個(gè)實(shí)際應(yīng)用。棧還用于實(shí)現(xiàn)遞歸調(diào)用過(guò)程、表達(dá)式的處理和中斷的處理。1．遞歸過(guò)程的實(shí)現(xiàn)例如，在本書的第1章例1.5中提到，對(duì)于輸入的參數(shù)n，依次打印輸出自然數(shù)1到n。為了不使用局部變量，其C函數(shù)如下：#include"stdio.h"wrt1(intn){if(n!=0){wrt1(n–1)；printf("%d\n",n)；}return；}2．表達(dá)式的計(jì)算在編譯系統(tǒng)或解釋系統(tǒng)中，常利用棧來(lái)處理表達(dá)式的計(jì)算問(wèn)題。2.4隊(duì)列及其應(yīng)用2.4.1隊(duì)列的基本概念隊(duì)列（equeue）是指允許在一端進(jìn)行插入、而在另一端進(jìn)行刪除的線性表。允許插入的一端稱為隊(duì)尾，允許刪除的一端稱為排頭。在隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)中，最先插入的元素將最先能夠被刪除，反之，最后插入的元素將最后才能被刪除。往隊(duì)列的隊(duì)尾插入一個(gè)元素稱為入隊(duì)運(yùn)算，從隊(duì)列的排頭刪除一個(gè)元素稱為退隊(duì)運(yùn)算。圖2.16是在隊(duì)列中進(jìn)行插入與刪除的示意圖。與棧類似，在程序設(shè)計(jì)語(yǔ)言中，用一維數(shù)組作為隊(duì)列的順序存儲(chǔ)空間。在操作系統(tǒng)中，用一個(gè)隊(duì)列來(lái)組織管理用戶程序的排隊(duì)執(zhí)行，原則是：①初始時(shí)隊(duì)列為空。②當(dāng)有用戶程序來(lái)到時(shí)，將該用戶程序加入到隊(duì)列的末尾進(jìn)行等待。③當(dāng)計(jì)算機(jī)系統(tǒng)執(zhí)行完當(dāng)前的用戶程序后，就從隊(duì)列的頭部取出一個(gè)用戶程序執(zhí)行。2.4.2循環(huán)隊(duì)列及其運(yùn)算在實(shí)際應(yīng)用中，隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)一般采用循環(huán)隊(duì)列的形式。所謂循環(huán)隊(duì)列，就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間，供隊(duì)列循環(huán)使用，如圖2.17所示。由圖2.18中循環(huán)隊(duì)列動(dòng)態(tài)變化的過(guò)程可以看出，當(dāng)循環(huán)隊(duì)列滿時(shí)有front=rear，而當(dāng)循環(huán)隊(duì)列空時(shí)也有front=rear。為了能區(qū)分隊(duì)列滿還是隊(duì)列空，通常還需增加一個(gè)標(biāo)志s，s值的定義如下：建立一個(gè)循環(huán)隊(duì)列順序存儲(chǔ)空間（即初始化循環(huán)隊(duì)列順序存儲(chǔ)空間）的C語(yǔ)言描述如下：#include"stdlib.h"voidinit_queue(q,m,front,rear,s)/*初始化循環(huán)隊(duì)列*/ET*q；/*循環(huán)隊(duì)列空間*/intm,*front,*rear,*s；/*m為循環(huán)隊(duì)列容量,front為排頭指針,rear為隊(duì)尾指針,s為標(biāo)志*/{q=malloc(m*sizeof(ET))；/*申請(qǐng)容量為m的循環(huán)隊(duì)列空間*/*front=m；*rear=m；/*置頭尾指針初值*/*s=0；/*置隊(duì)列空標(biāo)志*/return；}（1）入隊(duì)運(yùn)算入隊(duì)運(yùn)算是指在循環(huán)隊(duì)列的隊(duì)尾加入一個(gè)新元素。這個(gè)運(yùn)算有兩個(gè)基本操作：首先將隊(duì)尾指針進(jìn)一（即rear=rear+1）,并當(dāng)rear=m+1時(shí)置rear=1；然后將新元素插入到隊(duì)尾指針指向的位置。下面是入隊(duì)運(yùn)算的C語(yǔ)言描述。/*在容量為m的循環(huán)隊(duì)列Q中插入一個(gè)元素x（入隊(duì)運(yùn)算）*/voidaddcq(q,m,rear,front,s,x)ETq[],x；/*q為循環(huán)隊(duì)列空間,x為入隊(duì)的元素*/intm,*rear,*front,*s；/*m為循環(huán)隊(duì)列容量,front為排頭指針,rear為隊(duì)尾指針,s為標(biāo)志*/{if((*s==1)&&(*rear==*front))/*隊(duì)列滿,上溢錯(cuò)誤,返回*/{printf("Queue–OVERFLOW\n")；return；}*rear=*rear+1；/*隊(duì)尾指針進(jìn)一*/if(*rear==m+1)*rear=1；/*隊(duì)尾指針循環(huán)*/q[*rear–1]=x；/*元素x插入到隊(duì)尾*/*s=1；/*置隊(duì)列非空標(biāo)志*/return；}（2）退隊(duì)運(yùn)算退隊(duì)運(yùn)算是指在循環(huán)隊(duì)列的排頭位置退出一個(gè)元素并賦給指定的變量。這個(gè)運(yùn)算有兩個(gè)基本操作：首先將排頭指針進(jìn)一（即front=front+1）,并當(dāng)front=m+1時(shí)置front=1；然后將排頭指針指向的元素賦給指定的變量。下面是退隊(duì)運(yùn)算的C語(yǔ)言描述。/*在容量為m的循環(huán)隊(duì)列中刪除一個(gè)元素（退隊(duì)運(yùn)算）*/voiddelcq(q,m,rear,front,s,y)ETq[],*y；/*q為循環(huán)隊(duì)列空間,y存放退隊(duì)的元素*/intm,*rear,*front,*s；/*m為循環(huán)隊(duì)列容量,front為排頭指針,rear為隊(duì)尾指針,s為標(biāo)志*/{if(*s==0)/*隊(duì)列空,下溢錯(cuò)誤,返回*/{printf("Queue–UNDERFLOW\n")；return；}*front=*front+1；/*排頭指針進(jìn)一*/if(*front==m+1)*front=1；/*排頭指針循環(huán)*/*y=q[*front–1]；/*讀出排頭元素*/if(*front==*rear)*s=0；/*置隊(duì)列空標(biāo)志*/return；}2.4.3隊(duì)列的應(yīng)用凡是按“先來(lái)先服務(wù)”（即“先進(jìn)先出”）原則處理的問(wèn)題，都可以用隊(duì)列結(jié)構(gòu)來(lái)解決。下面再介紹三個(gè)用模擬隊(duì)列結(jié)構(gòu)來(lái)解決的問(wèn)題。1．給工人分配工作的模擬2.輸入輸出緩沖區(qū)的結(jié)構(gòu)為了解決上述這種兩個(gè)設(shè)備操作速度不匹配的矛盾，通常是在兩個(gè)設(shè)備之間設(shè)置一個(gè)緩沖區(qū)，如圖2.19所示。利用循環(huán)隊(duì)列結(jié)構(gòu)的緩沖區(qū)，就解決了計(jì)算機(jī)處理數(shù)據(jù)與打印機(jī)打印輸出的速度不匹配的矛盾，實(shí)現(xiàn)了兩個(gè)設(shè)備之間數(shù)據(jù)的正常傳送。3.汽車加油站的工作模擬2.5線性鏈表2.5.1線性鏈表的基本概念1．線性鏈表線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表。為了適應(yīng)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，計(jì)算機(jī)存儲(chǔ)空間被劃分為一個(gè)一個(gè)小塊，每一小塊占若干字節(jié)，通常稱這些小塊為存儲(chǔ)結(jié)點(diǎn)。將存儲(chǔ)空間中的每一個(gè)存儲(chǔ)結(jié)點(diǎn)分為兩部分：一部分用于存儲(chǔ)數(shù)據(jù)元素的值，稱為數(shù)據(jù)域；另一部分用于存放下一個(gè)數(shù)據(jù)元素的存儲(chǔ)序號(hào)（即存儲(chǔ)結(jié)點(diǎn)的地址），即指向后件結(jié)點(diǎn)，稱為指針域。線性鏈表中存儲(chǔ)結(jié)點(diǎn)的結(jié)構(gòu)如圖2.20所示。指向線性表中第一個(gè)結(jié)點(diǎn)的指針HEAD稱為頭指針。當(dāng)HEAD=NULL（或0）時(shí)稱為空表。對(duì)于線性鏈表，可以從頭指針開始，沿各結(jié)點(diǎn)的指針掃描到鏈表中的所有結(jié)點(diǎn)。為了彌補(bǔ)線性單鏈表的這個(gè)缺點(diǎn)，在某些應(yīng)用中，對(duì)線性鏈表中的每個(gè)結(jié)點(diǎn)設(shè)置兩個(gè)指針，一個(gè)稱為左指針（Llink），用以指向其前件結(jié)點(diǎn)；另一個(gè)稱為右指針（Rlink），用以指向其后件結(jié)點(diǎn)。這樣的線性鏈表稱為雙向鏈表，其邏輯狀態(tài)如圖2.23所示。2．帶鏈的棧棧也是線性表，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。圖2.24是棧在鏈?zhǔn)酱鎯?chǔ)時(shí)的邏輯狀態(tài)示意圖。在實(shí)際應(yīng)用中，帶鏈的?？梢杂脕?lái)收集計(jì)算機(jī)存儲(chǔ)空間中所有空閑的存儲(chǔ)結(jié)點(diǎn)，這種帶鏈的棧稱為可利用棧。如圖2.25所示。3．帶鏈的隊(duì)列與棧類似，隊(duì)列也是線性表，也可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。圖2.26（a）是隊(duì)列在鏈?zhǔn)酱鎯?chǔ)時(shí)的邏輯狀態(tài)示意圖。圖2.26(b)是將新結(jié)點(diǎn)p入隊(duì)的示意圖。圖2.26（c）是將排頭結(jié)點(diǎn)p退出隊(duì)列的示意圖。2.5.2線性鏈表的基本運(yùn)算線性鏈表的運(yùn)算主要有以下幾個(gè)：①在線性鏈表中包含指定元素的結(jié)點(diǎn)之前插入一個(gè)新元素。②在線性鏈表中刪除包含指定元素的結(jié)點(diǎn)。③將兩個(gè)線性鏈表按要求合并成一個(gè)線性鏈表。④將一個(gè)線性鏈表按要求進(jìn)行分解。⑤逆轉(zhuǎn)線性鏈表。⑥復(fù)制線性鏈表。⑦線性鏈表的排序。⑧線性鏈表的查找。1.在線性鏈表中查找指定元素對(duì)線性鏈表進(jìn)行掃描查找，在線性鏈表中尋找包含指定元素值的前一個(gè)結(jié)點(diǎn)。2．線性鏈表的插入線性鏈表的插入是指在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的線性表中插入一個(gè)新元素。為了要在線性鏈表中插入一個(gè)新元素，首先要給該元素分配一個(gè)新結(jié)點(diǎn)，然后將存放新元素值的結(jié)點(diǎn)鏈接到線性鏈表中指定的位置。3．線性鏈表的刪除線性鏈表的刪除指在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的線性表中刪除包含指定元素的結(jié)點(diǎn)。為了在線性鏈表中刪除包含指定元素的結(jié)點(diǎn)，首先要在線性鏈表中找到這個(gè)結(jié)點(diǎn)，然后將要?jiǎng)h除結(jié)點(diǎn)放回到可利用棧。2.5.3循環(huán)鏈表循環(huán)鏈表的結(jié)構(gòu)與前面所討論的線性鏈表相比，具有以下兩個(gè)特點(diǎn)：①循環(huán)鏈表的頭指針指向表頭結(jié)點(diǎn)。②在循環(huán)鏈表中，所有結(jié)點(diǎn)的指針構(gòu)成了一個(gè)環(huán)狀鏈。圖2.29是循環(huán)鏈表的示意圖。在實(shí)際應(yīng)用中，循環(huán)鏈表與線性單鏈表相比主要有以下兩個(gè)方面的優(yōu)點(diǎn)：①在循環(huán)鏈表中，只要指出表中任何一個(gè)結(jié)點(diǎn)的位置，就可以從它出發(fā)訪問(wèn)到表中其他所有的結(jié)點(diǎn)。②由于在循環(huán)鏈表中設(shè)置了一個(gè)表頭結(jié)點(diǎn)，因此，在任何情況下，循環(huán)鏈表中至少有一個(gè)結(jié)點(diǎn)存在，從而使空表與非空表的運(yùn)算統(tǒng)一。2.5.4多項(xiàng)式的表示及其運(yùn)算設(shè)多項(xiàng)式為：Pn(x)=anxn+an–1xn–1+…+a1x+a0在采用鏈表表示多項(xiàng)式時(shí)，對(duì)于多項(xiàng)式中每一個(gè)非零系數(shù)的項(xiàng)構(gòu)成鏈表中的一個(gè)結(jié)點(diǎn)，而對(duì)于系數(shù)為零的項(xiàng)就不用表示。多項(xiàng)式中非零系數(shù)項(xiàng)所構(gòu)成的結(jié)點(diǎn)如圖2.30所示。設(shè)只表示非零系數(shù)項(xiàng)的多項(xiàng)式為：其中ak≠0(k=1,2,…,m),em＞em–1＞…＞e1≥0。若用線性單鏈表表示，其邏輯狀態(tài)如圖2.31（a）所示。若用循環(huán)鏈表表示，其邏輯狀態(tài)如圖2.31（b）所示。多項(xiàng)式的運(yùn)算主要有以下五種：①多項(xiàng)式鏈表的生成。②多項(xiàng)式鏈表的釋放。③多項(xiàng)式的輸出。④多項(xiàng)式的相加。⑤多項(xiàng)式的相乘。下面以循環(huán)鏈表表示的多項(xiàng)式為例來(lái)討論各種運(yùn)算。1．多項(xiàng)式鏈表的生成主要包括以下兩步：①建立一個(gè)表頭結(jié)點(diǎn)，其指數(shù)域值為–1，指針域指向表頭結(jié)點(diǎn)自身，頭指針也指向表頭結(jié)點(diǎn)。②按降冪順序以數(shù)偶形式依次輸入多項(xiàng)式中非零系數(shù)項(xiàng)的指數(shù)ek和系數(shù)ak(k=m，m–1，…，1)，最后以輸入指數(shù)值–1為結(jié)束。2．多項(xiàng)式鏈表的釋放從表頭結(jié)點(diǎn)開始，逐步釋放鏈表中的各結(jié)點(diǎn)。3．多項(xiàng)式的輸出從表頭結(jié)點(diǎn)后的第一個(gè)結(jié)點(diǎn)開始，以數(shù)偶形式順鏈輸出各結(jié)點(diǎn)中的指數(shù)域與系數(shù)域的內(nèi)容。4．多項(xiàng)式的相加多項(xiàng)式相加的運(yùn)算規(guī)則很簡(jiǎn)單，只要從兩個(gè)多項(xiàng)式鏈表的第一個(gè)元素結(jié)點(diǎn)開始檢測(cè)。5．多項(xiàng)式的相乘2.6數(shù)組與字符串2.6.1數(shù)組的順序存儲(chǔ)結(jié)構(gòu)數(shù)學(xué)中的矩陣在程序設(shè)計(jì)語(yǔ)言中用二維數(shù)組表示。二維數(shù)組在計(jì)算機(jī)中是順序存儲(chǔ)的。1.二維數(shù)組以行為主的順序存儲(chǔ)二維數(shù)組以行為主的順序存儲(chǔ)是指將數(shù)組中的元素一行接一行地順序存儲(chǔ)在計(jì)算機(jī)的連續(xù)存儲(chǔ)空間中。例如，一個(gè)m×n的矩陣在計(jì)算機(jī)中以行為主的順序存儲(chǔ)形式如圖2.32所示。2.二維數(shù)組以列為主的順序存儲(chǔ)二維數(shù)組以列為主的順序存儲(chǔ)是指將數(shù)組中的元素一列接一列地順序存儲(chǔ)在計(jì)算機(jī)的連續(xù)存儲(chǔ)空間中。例如，一個(gè)m×n的矩陣在計(jì)算機(jī)中以列為主的順序存儲(chǔ)形式如圖2.33所示。2.6.2規(guī)則矩陣的壓縮規(guī)則矩陣是指，矩陣中非零元素的分布是有規(guī)律的。在存儲(chǔ)一個(gè)規(guī)則矩陣時(shí)，只需存儲(chǔ)非零元素即可，而對(duì)于大部分的零元素或者重復(fù)的非零元素（如對(duì)稱矩陣）不必存儲(chǔ)。規(guī)則矩陣的這種存儲(chǔ)方法稱為壓縮存儲(chǔ)。1.下三角矩陣的壓縮存儲(chǔ)存儲(chǔ)的原則是：用一個(gè)一維數(shù)組以行為主順序存放下三角矩陣中的所有下三角部分的元素。設(shè)n階下三角矩陣為：經(jīng)壓縮后，存放在一維數(shù)組B中的形式如圖2.34（a）所示。下三角矩陣A也可以用以列為主的方式壓縮存儲(chǔ)在一維數(shù)組B中，其存儲(chǔ)形式如圖2.34（b）所示。顯然，在以列為主壓縮存儲(chǔ)的情況下，訪問(wèn)下三角矩陣A中的元素時(shí)其下標(biāo)運(yùn)算要比以行為主壓縮存儲(chǔ)時(shí)稍為復(fù)雜一些。因此，在實(shí)際應(yīng)用時(shí)，一般采用以行為主壓縮存儲(chǔ)下三角矩陣。2.對(duì)稱矩陣的壓縮存儲(chǔ)對(duì)稱矩陣的壓縮存儲(chǔ)與下三角矩陣完全相同。3.三對(duì)角矩陣的壓縮存儲(chǔ)n階三對(duì)角矩陣的形式為：對(duì)于n階三對(duì)角矩陣，用一個(gè)長(zhǎng)度為3n–2的一維數(shù)組以行為主存放三條對(duì)角線上的元素，其存儲(chǔ)形式如圖2.35（a）所示。在用一維數(shù)組B以行為主存放三對(duì)角矩陣A中的元素aij時(shí)，其訪問(wèn)公式為：對(duì)于三對(duì)角矩陣，也可以用一維數(shù)組B以列為主存放三條對(duì)角線上的元素，如圖2.35（b）所示。在這種情況下，訪問(wèn)三對(duì)角矩陣A中元素aij的公式為：2.6.3一般稀疏矩陣的表示如果一個(gè)矩陣中絕大多數(shù)的元素值為零，只有很少的元素值非零，則稱該矩陣為稀疏矩陣。在實(shí)際存儲(chǔ)稀疏矩陣時(shí)，可以只存儲(chǔ)非零元素，而大量的零元素不存儲(chǔ)，這就是稀疏矩陣的壓縮存儲(chǔ)。1.稀疏矩陣的三列二維數(shù)組表示在壓縮存儲(chǔ)形式中，每一個(gè)非零元素應(yīng)包括以下三個(gè)信息：①非零元素所在的行號(hào)i；②非零元素所在的列號(hào)j；③非零元素的值V。即每一個(gè)非零元素可以用下列三元組表示： （i，j，V）為了表示的惟一性，除了每一個(gè)非零元素用一個(gè)三元組表示外，在所有表示非零元素的三元組之前再添加一個(gè)三元組 （I，J，t）一般來(lái)說(shuō)，具有t個(gè)非零元素的稀疏矩陣可以用t+1個(gè)三元組表示，其中第一個(gè)三元組用以表示稀疏矩陣的總體信息，其后的各三元組依次表示各非零元素，且按以行為主的順序排列。為了使各三元組的結(jié)構(gòu)更緊湊，通常將這些三元組組織成三列二維表格的形式，一般又表示成三列二維數(shù)組的形式，并簡(jiǎn)稱為三列二維數(shù)組。具有t個(gè)非零元素的稀疏矩陣，其對(duì)應(yīng)的三列二維數(shù)組為t+1行、3列，共有3(t+1)個(gè)元素。最后需要說(shuō)明一點(diǎn)，在用三列二維數(shù)組表示稀疏矩陣后，如果稀疏矩陣的運(yùn)算結(jié)果其非零元素的個(gè)數(shù)不發(fā)生變化（如矩陣轉(zhuǎn)置），則運(yùn)算結(jié)果可直接采用三列二維數(shù)組表示的形式；如果運(yùn)算結(jié)果其非零元素的個(gè)數(shù)發(fā)生了變化（如矩陣乘積），則運(yùn)算結(jié)果只能用一般的稀疏矩陣表示，如有必要，則再用三列二維數(shù)組表示。2．十字鏈表稀疏矩陣還可以用鏈?zhǔn)浇Y(jié)構(gòu)來(lái)表示。在用鏈?zhǔn)浇Y(jié)構(gòu)表示稀疏矩陣時(shí)，矩陣中的每一個(gè)非零元素對(duì)應(yīng)一個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)有五個(gè)域：行域、列域、值域、向下域與向右域，如圖2.40所示。用十字鏈表表示稀疏矩陣的結(jié)構(gòu)特點(diǎn)如下：①稀疏矩陣的每一行與每一列均用帶表頭結(jié)點(diǎn)的循環(huán)鏈表表示。②表頭結(jié)點(diǎn)中的行域與列域的值均置為0（即row=0，col=0）。③行、列鏈表的表頭結(jié)點(diǎn)合用，且這些表頭結(jié)點(diǎn)通過(guò)值域（即val）相鏈接，并再增加一個(gè)結(jié)點(diǎn)作為它們的表頭結(jié)點(diǎn)H，其行、列域值分別存放稀疏矩陣的行數(shù)與列數(shù)。例如，稀疏矩陣2.6.4字符串1．字符串的基本概念字符串（string）是字符的一個(gè)有限序列，它本質(zhì)上就是數(shù)據(jù)元素類型為字符的線性表。字符串一般表示為：

"a1a2…ai…an"對(duì)線性表的所有運(yùn)算，對(duì)字符串也適用。字符串除了具有一般線性表所具有的運(yùn)算外，由于字符串具有多種數(shù)據(jù)類型的特點(diǎn)，因此，對(duì)字符串的運(yùn)算要比一般的線性表更豐富。①連接運(yùn)算。②取子串運(yùn)算。③刪除子串運(yùn)算。④插入子串運(yùn)算。⑤求子串位置。

2．字符串匹配在一般的編輯軟件系統(tǒng)中，經(jīng)常要遇到在一個(gè)給定的文本中檢測(cè)一個(gè)特定的字符串的問(wèn)題。這就是字符串匹配。字符串匹配又稱模式匹配。（1）字符串匹配的簡(jiǎn)單算法（2）字符串匹配的KMP算法2.7樹與二叉樹2.7.1樹的基本概念樹（tree）是一種簡(jiǎn)單的非線性結(jié)構(gòu)。圖2.42表示了一棵一般的樹。在樹的圖形表示中，總是認(rèn)為在用直線連起來(lái)的兩端結(jié)點(diǎn)中，上端結(jié)點(diǎn)是前件，下端結(jié)點(diǎn)是后件，這樣，表示前后件關(guān)系的箭頭就可以省略。例如，圖2.43中的樹表示了學(xué)校行政關(guān)系結(jié)構(gòu)；圖2.44中的樹反映了一本書的層次結(jié)構(gòu)。在樹結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)只有一個(gè)前件，稱為父結(jié)點(diǎn)。在樹中，沒(méi)有前件的結(jié)點(diǎn)只有一個(gè)，稱為樹的根結(jié)點(diǎn)，簡(jiǎn)稱為樹的根。在樹結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，它們都稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒(méi)有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。在樹結(jié)構(gòu)中，一個(gè)結(jié)點(diǎn)所擁有的后件個(gè)數(shù)稱為該結(jié)點(diǎn)的度。在樹中，所有結(jié)點(diǎn)中的最大度稱為樹的度。樹結(jié)構(gòu)具有明顯的層次關(guān)系，即樹是一種層次結(jié)構(gòu)。根結(jié)點(diǎn)在第1層；同一層上所有結(jié)點(diǎn)的所有子結(jié)點(diǎn)在下一層。樹的最大層次稱為樹的深度。在樹中，以某結(jié)點(diǎn)的一個(gè)子結(jié)點(diǎn)為根構(gòu)成的樹稱為該結(jié)點(diǎn)的一棵子樹。在樹中，葉子結(jié)點(diǎn)沒(méi)有子樹。2.7.2二叉樹及其基本性質(zhì)1．什么是二叉樹二叉樹(binarytree)是一種很有用的非線性結(jié)構(gòu)。二叉樹具有以下兩個(gè)特點(diǎn)：（1）非空二叉樹只有一個(gè)根結(jié)點(diǎn)；（2）每一個(gè)結(jié)點(diǎn)最多有兩棵子樹，且分別稱為該結(jié)點(diǎn)的左子樹與右子樹。圖2.46（a）是一棵只有根結(jié)點(diǎn)的二叉樹，圖2.46（b）是一棵深度為4的二叉樹。2．二叉樹的基本性質(zhì)二叉樹具有以下幾個(gè)性質(zhì)：性質(zhì)1在二叉樹的第k層上，最多有2k–1（k≥1）個(gè)結(jié)點(diǎn)。根據(jù)二叉樹的特點(diǎn)，這個(gè)性質(zhì)是顯然的。性質(zhì)2深度為m的二叉樹最多有2m–1個(gè)結(jié)點(diǎn)。性質(zhì)3在任意一棵二叉樹中，度為0的結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）總是比度為2的結(jié)點(diǎn)多一個(gè)。性質(zhì)4具有n個(gè)結(jié)點(diǎn)的二叉樹，其深度至少為[log2n]+1，其中[log2n]表示取log2n的整數(shù)部分。3.滿二叉樹與完全二叉樹（1）滿二叉樹滿二叉樹是指除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)。（2）完全二叉樹完全二叉樹是指這樣的二叉樹：除最后一層外，每一層上的結(jié)點(diǎn)數(shù)均達(dá)到最大值；在最后一層上只缺少右邊的若干結(jié)點(diǎn)。性質(zhì)5具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為[log2n]+1。性質(zhì)6設(shè)完全二叉樹共有n個(gè)結(jié)點(diǎn)。如果從根結(jié)點(diǎn)開始，按層序（每一層從左到右）用自然數(shù)1，2，…，n給結(jié)點(diǎn)進(jìn)行編號(hào)，則對(duì)于編號(hào)為k(k=1，2，…，n)的結(jié)點(diǎn)有以下結(jié)論：①若k=1，則該結(jié)點(diǎn)為根結(jié)點(diǎn)，它沒(méi)有父結(jié)點(diǎn)；若k＞1，則該結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為INT(k/2)。②若2k≤n，則編號(hào)為k的結(jié)點(diǎn)的左子結(jié)點(diǎn)編號(hào)為2k；否則該結(jié)點(diǎn)無(wú)左子結(jié)點(diǎn)（顯然也沒(méi)有右子結(jié)點(diǎn)）。③若2k+1≤n，則編號(hào)為k的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號(hào)為2k+1；否則該結(jié)點(diǎn)無(wú)右子結(jié)點(diǎn)。2.7.3二叉樹的存儲(chǔ)結(jié)構(gòu)1．二叉鏈表在計(jì)算機(jī)中，二叉樹通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。與線性鏈表類似，用于存儲(chǔ)二叉樹中各元素的存儲(chǔ)結(jié)點(diǎn)也由兩部分組成：數(shù)據(jù)域與指針域。用于存儲(chǔ)二叉樹的存儲(chǔ)結(jié)點(diǎn)的指針域有兩個(gè)：一個(gè)用于指向該結(jié)點(diǎn)的左子結(jié)點(diǎn)的存儲(chǔ)地址，稱為左指針域；另一個(gè)用于指向該結(jié)點(diǎn)的右子結(jié)點(diǎn)的存儲(chǔ)地址，稱為右指針域。圖2.49為二叉樹存儲(chǔ)結(jié)點(diǎn)的示意圖。由于二叉樹的存儲(chǔ)結(jié)構(gòu)中每一個(gè)存儲(chǔ)結(jié)點(diǎn)有兩個(gè)指針域，因此，二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)也稱為二叉鏈表。圖2.50所示。2．二叉鏈表的生成二叉鏈表的生成是指根據(jù)給定的二叉樹在計(jì)算機(jī)中建立鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。2.7.4二叉樹的遍歷二叉樹的遍歷是指不重復(fù)地訪問(wèn)二叉樹中的所有結(jié)點(diǎn)。二叉樹的遍歷可以分為三種：前序遍歷、中序遍歷、后序遍歷。1．前序遍歷前序遍歷（DLR）是指在訪問(wèn)根結(jié)點(diǎn)、遍歷左子樹與遍歷右子樹這三者中，首先訪問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹；并且，在遍歷左、右子樹時(shí)，仍然先訪問(wèn)根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹。因此，前序遍歷二叉樹的過(guò)程是一個(gè)遞歸的過(guò)程。2．中序遍歷中序遍歷（LDR）是指在訪問(wèn)根結(jié)點(diǎn)、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然后訪問(wèn)根結(jié)點(diǎn)，最后遍歷右子樹；并且，在遍歷左、右子樹時(shí)，仍然先遍歷左子樹，然后訪問(wèn)根結(jié)點(diǎn)，最后遍歷右子樹。因此，中序遍歷二叉樹的過(guò)程也是一個(gè)遞歸的過(guò)程。3．后序遍歷后序遍歷（LRD）是指在訪問(wèn)根結(jié)點(diǎn)、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然后遍歷右子樹，最后訪問(wèn)根結(jié)點(diǎn)；并且，在遍歷左、右子樹時(shí)，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問(wèn)根結(jié)點(diǎn)。因此，后序遍歷二叉樹的過(guò)程也是一個(gè)遞歸的過(guò)程。2.7.5穿線二叉樹1．穿線二叉樹的概念二叉樹是一種非線性結(jié)構(gòu)，對(duì)二叉樹的遍歷，實(shí)際上是將二叉樹這種非線性結(jié)構(gòu)按某種需要轉(zhuǎn)化為線性序列，以便以后在對(duì)二叉樹進(jìn)行某種處理時(shí)直接使用。2．穿線二叉樹的構(gòu)造對(duì)二叉樹進(jìn)行不同的遍歷（前序遍歷、中序遍歷、后序遍歷）時(shí)，得到的遍歷序列也不同，因此，在二叉鏈表中鏈接遍歷序列的線索也是不同的。圖2.52是中序線索二叉樹的示意圖，圖中的虛線表示線索。3．穿線二叉樹的遍歷二叉樹經(jīng)過(guò)一次遍歷并生成遍歷線索以后，如果再次需要遍歷，則只需要根據(jù)遍歷序列的線索進(jìn)行即可。2.7.6表達(dá)式的線性化1．表達(dá)式樹在計(jì)算機(jī)中，可以用樹結(jié)構(gòu)來(lái)表示算術(shù)表達(dá)式。用樹來(lái)表示算術(shù)表達(dá)式的原則如下：①表達(dá)式中的每一個(gè)運(yùn)算符在樹中對(duì)應(yīng)一個(gè)結(jié)點(diǎn)，稱為運(yùn)算符結(jié)點(diǎn)。②運(yùn)算符的每一個(gè)運(yùn)算對(duì)象在樹中為該運(yùn)算符結(jié)點(diǎn)的子樹（在樹中的順序?yàn)閺淖蟮接遥?。③運(yùn)算對(duì)象中的單變量均為葉子結(jié)點(diǎn)。根據(jù)以上原則，可以將表達(dá)式

a*(b+c/d)+e*h–g*f(s，t，x+y)用如圖2.53所示的樹來(lái)表示。2．有序樹的二叉樹表示如果對(duì)某個(gè)結(jié)點(diǎn)的所有子結(jié)點(diǎn)按從左到右排上次序，則稱該樹為有序樹。即：在有序樹中，某個(gè)結(jié)點(diǎn)的所有子結(jié)點(diǎn)從左到右的次序是不能顛倒的。將有序樹轉(zhuǎn)化成二叉樹的原則如下：①有序樹T中的結(jié)點(diǎn)與二叉樹BT中的結(jié)點(diǎn)一一對(duì)應(yīng)。②有序樹T中某個(gè)結(jié)點(diǎn)N的第一個(gè)子結(jié)點(diǎn)（即最左邊的子結(jié)點(diǎn)）N1，在二叉樹BT中為對(duì)應(yīng)結(jié)點(diǎn)N的左子結(jié)點(diǎn)。③有序樹T中某個(gè)結(jié)點(diǎn)N的第一個(gè)子結(jié)點(diǎn)以后的其他子結(jié)點(diǎn)，在二叉樹BT中被依次鏈接成一串起始于N1的右子結(jié)點(diǎn)。將圖2.53（a）所示的有序樹轉(zhuǎn)化成的二叉樹如圖2.54所示。

3．表達(dá)式的線性化表達(dá)式的線性化，是指將一般的表達(dá)式化為波蘭表示式（即后綴表示）。利用樹結(jié)構(gòu)與二叉樹結(jié)構(gòu)對(duì)表達(dá)式線性化的步驟如下：①將表達(dá)式用有序樹表示，即構(gòu)造表達(dá)式樹。②將表達(dá)式樹化為二叉樹。③對(duì)相應(yīng)的二叉樹進(jìn)行中序遍歷，其遍歷序列即為表達(dá)式的波蘭表示式。2.8圖圖（graph）是比線性表、樹與二叉樹更為復(fù)雜的一種數(shù)據(jù)結(jié)構(gòu)。2.8.1圖的基本概念如果數(shù)據(jù)元素集合D中的各數(shù)據(jù)元素之間存在任意的前后件關(guān)系，則此數(shù)據(jù)結(jié)構(gòu)稱為圖。圖通常用G表示。在圖中，如果對(duì)于任意的兩個(gè)結(jié)點(diǎn)a與b，當(dāng)結(jié)點(diǎn)a是結(jié)點(diǎn)b的前件，且結(jié)點(diǎn)b也是結(jié)點(diǎn)a的前件時(shí)，則稱該圖為無(wú)向圖。如果對(duì)于任意的兩個(gè)結(jié)點(diǎn)a與b，當(dāng)結(jié)點(diǎn)a是結(jié)點(diǎn)b的前件，結(jié)點(diǎn)b不都是結(jié)點(diǎn)a的前件時(shí)，則稱該圖為有向圖。在有向圖中，通常用帶有箭頭的邊來(lái)連接兩個(gè)有關(guān)聯(lián)的結(jié)點(diǎn)（由前件結(jié)點(diǎn)指向后件結(jié)點(diǎn)）。如圖2.55為兩個(gè)有向圖。2.8.2圖的存儲(chǔ)結(jié)構(gòu)一般是根據(jù)對(duì)圖的具體運(yùn)算來(lái)選取合適的存儲(chǔ)結(jié)構(gòu)。1．關(guān)聯(lián)矩陣由上述關(guān)聯(lián)矩陣可以明顯地看出，無(wú)向圖的關(guān)聯(lián)矩陣是對(duì)稱矩陣，且對(duì)角線上的元素均為0。這是因?yàn)?，?duì)于無(wú)向圖來(lái)說(shuō)，各結(jié)點(diǎn)之間的前后件關(guān)系是對(duì)稱的，且不考慮結(jié)點(diǎn)自身之間的前后件關(guān)系。有向圖的關(guān)聯(lián)矩陣不一定是對(duì)稱的，且其對(duì)角線上的元素也不一定是0。關(guān)聯(lián)矩陣也稱為鄰接矩陣。2．求值矩陣關(guān)聯(lián)矩陣只表示了圖的結(jié)構(gòu)，即圖中各結(jié)點(diǎn)的后件關(guān)系。但在許多實(shí)際問(wèn)題中，還需要對(duì)兩個(gè)關(guān)聯(lián)結(jié)點(diǎn)之間的值進(jìn)行運(yùn)算。這就是說(shuō)，除了要存儲(chǔ)圖中各結(jié)點(diǎn)值以及各結(jié)點(diǎn)之間的關(guān)系外，還必須存儲(chǔ)圖中每?jī)蓚€(gè)結(jié)點(diǎn)之間的求值函數(shù)。為了完整地存儲(chǔ)一個(gè)有值圖，可以用一維數(shù)組存儲(chǔ)圖中各結(jié)點(diǎn)的數(shù)據(jù)信息，用關(guān)聯(lián)矩陣存儲(chǔ)圖中任意兩個(gè)結(jié)點(diǎn)之間的關(guān)聯(lián)信息，用求值矩陣存儲(chǔ)圖中任意兩個(gè)結(jié)點(diǎn)之間的求值函數(shù)。例如，有A，B，C，D，E，F(xiàn)，G，H八個(gè)城市，它們的交通情況及運(yùn)費(fèi)如圖2.57所示。3．鄰接表鄰接表這種存儲(chǔ)結(jié)構(gòu)也稱為“順序–索引–鏈接”存儲(chǔ)結(jié)構(gòu)。假設(shè)圖中共有n個(gè)結(jié)點(diǎn)，其結(jié)點(diǎn)值分別為d1，d2，…，dn，并用自然數(shù)將它們依次編號(hào)為1，2，…，n。首先，用一個(gè)順序存儲(chǔ)空間來(lái)存儲(chǔ)圖中各結(jié)點(diǎn)的信息。其次，對(duì)圖中每一個(gè)結(jié)點(diǎn)dk(k=1，2，…，n)構(gòu)造一個(gè)單鏈表。對(duì)于圖2.59所示的有值圖，其鄰接表如圖2.60所示。鄰接表特別適合于表示結(jié)點(diǎn)數(shù)多但邊數(shù)較少的圖。4．鄰接多重表在鄰接多重表中，每條邊用一個(gè)存儲(chǔ)結(jié)點(diǎn)表示，每個(gè)存儲(chǔ)結(jié)點(diǎn)由五個(gè)域組成，如圖2.61所示。2.8.3圖的遍歷在實(shí)際應(yīng)用中，往往需要從圖的某一結(jié)點(diǎn)出發(fā)訪問(wèn)到圖中的所有結(jié)點(diǎn)。這一訪問(wèn)過(guò)程稱為圖的遍歷。工程中常用的圖遍歷方法主要有縱向優(yōu)先搜索法和橫向優(yōu)先搜索法兩種。1．縱向優(yōu)先搜索法縱向優(yōu)先搜索法遍歷圖的基本思想如下。從圖中某一結(jié)點(diǎn)作為當(dāng)前結(jié)點(diǎn)，然后進(jìn)行以下過(guò)程：①處理或輸出當(dāng)前結(jié)點(diǎn)，并記錄當(dāng)前結(jié)點(diǎn)的查訪標(biāo)志。②若當(dāng)前結(jié)點(diǎn)有后件結(jié)點(diǎn)，則取第一個(gè)后件結(jié)點(diǎn)。若該后件結(jié)點(diǎn)未被查訪過(guò)，則以該后件結(jié)點(diǎn)為當(dāng)前結(jié)點(diǎn)用縱向優(yōu)先搜索法進(jìn)行查訪。2．橫向優(yōu)先搜索法橫向優(yōu)先搜索法又稱為廣度優(yōu)先搜索法。其基本思想如下。從圖的某一個(gè)結(jié)點(diǎn)出發(fā)，首先依次訪問(wèn)該結(jié)點(diǎn)的后件結(jié)點(diǎn)，然后再順序訪問(wèn)這些后件結(jié)點(diǎn)的所有未被訪問(wèn)過(guò)的后件結(jié)點(diǎn)。依此類推，直到所有被訪問(wèn)結(jié)點(diǎn)的后件結(jié)點(diǎn)均被訪問(wèn)過(guò)為止。2.9索引存儲(chǔ)結(jié)構(gòu)2.9.1索引存儲(chǔ)的概念索引存儲(chǔ)的結(jié)構(gòu)有兩部分組成，一是存儲(chǔ)各個(gè)子表，二是存儲(chǔ)索引表。為了實(shí)現(xiàn)索引存儲(chǔ)，需要解決以下兩個(gè)問(wèn)題：①對(duì)數(shù)據(jù)集合中的元素進(jìn)行劃分。②索引表的具體存儲(chǔ)結(jié)構(gòu)以及每個(gè)子表的存儲(chǔ)結(jié)構(gòu)。1．?dāng)?shù)據(jù)元素的劃分例2.5設(shè)有一個(gè)學(xué)生成績(jī)表如表2.2所示。2．索引存儲(chǔ)的方式索引存儲(chǔ)包括索引表的存儲(chǔ)以及各個(gè)子表的存儲(chǔ)。2.9.2“順序-索引-順序”存儲(chǔ)方式在“順序-索引-順序”存儲(chǔ)方式中，索引表以及各子表均采用順序分配的存儲(chǔ)方法。圖2.62是例2.5中學(xué)生成績(jī)表的“順序-索引-順序”存儲(chǔ)方式的物理狀態(tài)。2.9.3“順序-索引-鏈接”存儲(chǔ)方式“順序-索引-鏈接”存儲(chǔ)方式是指用順序分配的方法存儲(chǔ)索引表，而用鏈?zhǔn)椒峙涞姆椒ù鎯?chǔ)各子表。2.9.4多重索引存儲(chǔ)結(jié)構(gòu)如果在索引存儲(chǔ)結(jié)構(gòu)中，其索引表本身又是索引存儲(chǔ)結(jié)構(gòu)，則稱為二重索引存儲(chǔ)結(jié)構(gòu)。圖2.64（a）為“順序-索引-順序-索引-鏈接”方式的二重索引存儲(chǔ)結(jié)構(gòu)示意圖，圖2.64（b）為“順序-索引-鏈接-索引-鏈接”方式的二重索引存儲(chǔ)結(jié)構(gòu)示意圖。在數(shù)據(jù)處理領(lǐng)域中，最常見的運(yùn)算是在給定的數(shù)據(jù)結(jié)構(gòu)中查找所需要處理的數(shù)據(jù)元素。另一常見的運(yùn)算是對(duì)給定的數(shù)據(jù)結(jié)構(gòu)進(jìn)行重新分類，或按數(shù)據(jù)元素的大小重新進(jìn)行排序，以方便對(duì)數(shù)據(jù)元素的處理。查找與排序是數(shù)據(jù)處理的基本技術(shù)。本章主要介紹線性表查找與排序的基本方法，以及索引存儲(chǔ)結(jié)構(gòu)下的查找技術(shù)。3.1線性表的查找技術(shù)3.1.1順序查找順序查找的基本方法是，從線性表的第一個(gè)元素開始，依次將線性表中的元素與被查元素進(jìn)行比較，若遇到線性表中某位置上的元素與被查元素相等，則表示找到（即查找成功）；若線性表中所有的元素與被查元素進(jìn)行比較都不相等，則表示線性表中不存在需要找的元素（即查找失敗）。對(duì)于大的線性表來(lái)說(shuō)，順序查找的效率是很低的。3.1.2有序表的對(duì)分查找雖然順序查找的效率不高，但在下列兩種情況下也只能采用順序查找。①線性表為無(wú)序表（即表中元素的排列是無(wú)序的）②采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的有序線性表先將線性表中的元素按值非遞減進(jìn)行重新排列。這樣的線性表稱為有序表。設(shè)有序線性表的長(zhǎng)度為n，被查元素為x，則對(duì)分查找的方法如下。將x與線性表的中間項(xiàng)進(jìn)行比較：若被查元素x與該線性表的中間項(xiàng)的值相等，則說(shuō)明查到，查找結(jié)束；若被查元素x小于該線性表的中間項(xiàng)的值，則取線性表的前半部分作為子表（即取中間項(xiàng)以前的部分，而不再考慮線性表后半部分的元素）以相同的方法進(jìn)行查找；若被查元素x大于該線性表的中間項(xiàng)的值，則取線性表的后半部分作為子表（即取中間項(xiàng)以后的部分，而不再考慮線性表前半部分的元素）以相同的方法進(jìn)行查找。這個(gè)過(guò)程一直進(jìn)行到查找成功或子表長(zhǎng)度為0（說(shuō)明線性表中沒(méi)有這個(gè)元素）為止。當(dāng)有序線性表為順序存儲(chǔ)時(shí)才能采用對(duì)分查找，并且，對(duì)分查找的效率要比順序查找高得多。3.2Hash表技術(shù)3.2.1Hash表的基本概念1．直接查找技術(shù)設(shè)表的長(zhǎng)度為n。如果存在一個(gè)函數(shù)i=i(k)，對(duì)于表中的任意一個(gè)元素的關(guān)鍵字k，滿足以下條件：①1≤i≤n。②對(duì)于任意的元素關(guān)鍵字k1≠k2，恒存在i(k1)≠i(k2)。則稱此表為直接查找表。其中函數(shù)i=i(k)稱為關(guān)鍵字k的映象函數(shù)。對(duì)直接查找表的操作主要有以下兩種（1）直接查找表的填入（2）直接查找表的取出2．Hash表Hash表技術(shù)是直接查找技術(shù)的推廣，其主要目標(biāo)是提高查找效率。如果按照直接查找表的填入方法，填入結(jié)果如表3.1所示。設(shè)表的長(zhǎng)度為n。如果存在一個(gè)函數(shù)i=i(k)，對(duì)于表中的任意一個(gè)元素的關(guān)鍵字k，滿足1≤i≤n，則稱此表為Hash表。其中函數(shù)i=i(k)稱為關(guān)鍵字k的Hash碼。Hash表技術(shù)的關(guān)鍵是要處理好表中元素的沖突問(wèn)題，它主要包括以下兩方面的工作：（1）構(gòu)造合適的Hash碼，以便盡量減少表中元素沖突的次數(shù)。即Hash碼的均勻性要比較好。（2）當(dāng)表中元素發(fā)生沖突時(shí)，要進(jìn)行適當(dāng)?shù)奶幚怼?．Hash碼的構(gòu)造在實(shí)際設(shè)計(jì)Hash碼時(shí)，要考慮以下兩方面的因素：①使各關(guān)鍵字盡可能均勻地分布在Hash表中。②Hash碼的計(jì)算要盡量簡(jiǎn)單。比較簡(jiǎn)單的Hash碼的構(gòu)造方法。（1）截段法（2）分段疊加法（3）除法（4）乘法3.2.2幾種常用的Hash表1．線性Hash表設(shè)線性Hash表的長(zhǎng)度為n，對(duì)線性Hash表的查找過(guò)程如下。（1）線性Hash表的填入（2）線性Hash表的取出線性Hash表的優(yōu)點(diǎn)是簡(jiǎn)單，但它有以下兩個(gè)主要缺點(diǎn)。當(dāng)Hash碼的沖突較多時(shí)，在線性Hash表中會(huì)存在“堆聚”現(xiàn)象，即許多關(guān)鍵字被連續(xù)登記在一起，從而會(huì)降低查找效率。2．隨機(jī)Hash表當(dāng)Hash表的長(zhǎng)度n設(shè)計(jì)成n=2k時(shí)，還可以定義另外一種Hash表——隨機(jī)Hash表。隨機(jī)Hash表的填入與取出的過(guò)程。（1）隨機(jī)Hash表的填入（2）隨機(jī)Hash表的取出3．溢出Hash表前面所介紹的線性Hash表與隨機(jī)Hash表均存在兩個(gè)致命的缺點(diǎn)：一是在Hash表填入過(guò)程中不顧后效，從而在填入過(guò)程中其沖突的機(jī)會(huì)在不斷增多；二是當(dāng)Hash表填滿時(shí)，不能正常地進(jìn)行查找。如果將沖突的元素安排在另外的空間內(nèi)，不占用Hash表本身的空間，就不會(huì)產(chǎn)生新的沖突。這就是溢出Hash表。溢出Hash表包括Hash表和溢出表兩部分。

溢出Hash表的填入與取出的過(guò)程。（1）溢出Hash表的填入（2）溢出Hash表的取出4．拉鏈Hash表拉鏈Hash表又分為外鏈Hash表與內(nèi)鏈Hash表。外鏈Hash表由Hash表及表外結(jié)點(diǎn)組成。Hash表的第i項(xiàng)登記著Hash碼為i的所有關(guān)鍵字的表外結(jié)點(diǎn)。在初始狀態(tài)下，Hash表中的所有指針為空。外鏈Hash表的填入與取出過(guò)程如下。（1）外鏈Hash表的填入填入后的外鏈Hash表如圖3.1所示。（2）外鏈Hash表的取出5．指標(biāo)Hash表指標(biāo)Hash表包括指標(biāo)表與內(nèi)容表兩部分。3.3線性表的排序技術(shù)排序是指將一個(gè)無(wú)序序列整理成按值非遞減順序排列的有序序列。排序的方法有很多，根據(jù)待排序序列的規(guī)模、存儲(chǔ)結(jié)構(gòu)以及對(duì)數(shù)據(jù)處理的要求，可以采用不同的排序方法。本節(jié)主要介紹針對(duì)順序表的常用排序法。3.3.1互換排序互換排序是指借助數(shù)據(jù)元素之間的互相交換進(jìn)行排序的一種方法。1．冒泡排序冒泡排序是通過(guò)相鄰數(shù)據(jù)元素的交換逐步將線性表變成有序。冒泡排序的基本方法如下。首先，從表頭開始往后掃描線性表，在掃描過(guò)程中逐次比較相鄰兩個(gè)元素的大小。然后，從后到前掃描剩下的線性表，同樣，在掃描過(guò)程中逐次比較相鄰兩個(gè)元素的大小。在上述排序過(guò)程中，對(duì)線性表的每一次來(lái)回掃描，都將其中的最大者沉到了表的底部，最小者像氣泡一樣冒到表的前頭，冒泡排序由此而得名。冒泡排序又稱下沉排序。圖3.2是冒泡排序的示意圖。2．快速排序快速排序的關(guān)鍵是對(duì)線性表的分割，以及對(duì)各分割出的子表再進(jìn)行分割，這個(gè)過(guò)程如圖3.3所示?？焖倥判蛟谧顗那闆r下需要n(n–1)/2次比較，但實(shí)際的排序效率要比冒泡排序高得多。3.3.2插入排序插入排序是指將無(wú)序序列中的各元素依次插入到已經(jīng)有序的線性表中。1．簡(jiǎn)單插入排序首先將第j個(gè)元素放到一個(gè)變量T中。然后從有序子表的最后一個(gè)元素（即線性表中第j–1個(gè)元素）開始，往前逐個(gè)與T進(jìn)行比較，將大于T的元素均依次向后移動(dòng)一個(gè)位置，直到發(fā)現(xiàn)一個(gè)元素不大于T為止，此時(shí)就將T（即原線性表中的第j個(gè)元素）插入到剛移出的空位置上，有序子表的長(zhǎng)度就變?yōu)閖了。圖3.4給出了插入排序的示意圖。圖中畫有方框的元素表示剛被插入到有序子表中。2．希爾排序?qū)⒄麄€(gè)無(wú)序序列分割成若干小的子序列分別進(jìn)行插入排序。但這種分割不是逐段分割，而是將相隔某個(gè)增量h的元素構(gòu)成一個(gè)子序列。在排序過(guò)程中，逐次減小這個(gè)增量，最后當(dāng)h減到1時(shí)，進(jìn)行一次插入排序，排序就完成。圖3.5為希爾排序的示意圖。3.3.3選擇排序1．簡(jiǎn)單選擇排序簡(jiǎn)單選擇排序的基本方法是：掃描整個(gè)線性表，從中選出最小的元素，將它交換到表的最前面（這是它應(yīng)有的位置）；然后對(duì)剩下的子表采用同樣的方法，直到子表空為止。2．堆排序堆的定義如下：具有n個(gè)元素的序列(h1，h2，…，hn)，當(dāng)且僅當(dāng)滿足i=1，2，…，n/2時(shí)稱之為堆。調(diào)整建堆的問(wèn)題。在調(diào)整建堆的過(guò)程中，總是將根結(jié)點(diǎn)值與左、右子樹的根結(jié)點(diǎn)值進(jìn)行比較，若不滿足堆的條件，則將左、右子樹根結(jié)點(diǎn)值中的大者與根結(jié)點(diǎn)值進(jìn)行交換。這個(gè)調(diào)整過(guò)程一直做到所有子樹均為堆為止。堆排序的方法如下：①首先將一個(gè)無(wú)序序列建成堆。②然后將堆頂元素（序列中的最大項(xiàng)）與堆中最后一個(gè)元素交換（最大項(xiàng)應(yīng)該在序列的最后）。3.3.4其他排序方法簡(jiǎn)介1．歸并排序歸并(Merging)是將兩個(gè)或兩個(gè)以上的有序表合并成一個(gè)新的有序表。設(shè)線性表L(1：n)中的某段L(low：high)已經(jīng)部分有序，即它的兩個(gè)子表L(low：mid)與L(mid+1：high)（其中l(wèi)ow≤mid≤high）已經(jīng)有序，現(xiàn)要將這兩個(gè)有序子表歸并成一個(gè)有序子表L(low：high)。兩個(gè)子表的歸并基本做法。①開辟一個(gè)與線性表L同樣大小的表空間A。②設(shè)置三個(gè)指針i，j，k，其初始狀態(tài)分別指向兩個(gè)有序子表的首部及表空間A中與L中需要進(jìn)行排序段相對(duì)應(yīng)空間的首部。即i=low，j=mid+1，k=low。③沿兩個(gè)有序子表掃描：④將未取空的子表中的剩余元素依次放入表空間A中。⑤將A中的對(duì)應(yīng)段復(fù)制到L中。圖3.9所示的為歸并排序的示意圖。歸并排序的算法有遞歸和非遞歸兩種形式。2．基數(shù)排序基數(shù)排序（RadixSort）又稱為吊桶排序，它屬于分配類的排序方法。設(shè)線性表中各元素的關(guān)鍵字具有k位有效數(shù)字，則基數(shù)排序的基本思想是從有效數(shù)字的最低位開始直到最高位，對(duì)每一位有效數(shù)字在線性表中進(jìn)行重新排列，其調(diào)整的原則為：①將線性表依當(dāng)前位的有效數(shù)字為序排列。②當(dāng)前位的有效數(shù)字相同時(shí)，按原次序排列。這種基數(shù)排序法稱為最低位優(yōu)先法（LeastSignificantDigitfirst，LSD）。圖3.10是基數(shù)排序的示意圖。3.4索引查找3.4.1分塊查找從整體來(lái)看，線性表不是有序表，如果將線性表分成若干個(gè)子表，雖然每一子表也不是有序的，但各個(gè)子表之間卻是有序的，這樣的線性表稱為分塊有序表。分塊有序表的結(jié)構(gòu)可以分為兩部分。①線性表本身采用順序存儲(chǔ)結(jié)構(gòu)。②再建立一個(gè)索引表。圖3.11是將一個(gè)長(zhǎng)度n=19的線性表分成m=3個(gè)子表的分塊有序表示意圖。分塊查找又稱索引順序查找，用于在分塊有序表中進(jìn)行查找。分塊查找的過(guò)程可以分兩步進(jìn)行：（1）查找索引表，以便確定被查元素所在子表的位置。（2）在相應(yīng)的子表中用順序查找