基本數(shù)據(jù)結(jié)構(gòu)修改第一頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算22.1數(shù)據(jù)結(jié)構(gòu)的基本概念2.1.1兩個(gè)例子2.1.2什么是數(shù)據(jù)結(jié)構(gòu)2.1.3數(shù)據(jù)結(jié)構(gòu)的圖形表示2.1.4線性數(shù)據(jù)結(jié)構(gòu)與非線性數(shù)據(jù)結(jié)構(gòu)第二頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算3數(shù)據(jù)結(jié)構(gòu)三個(gè)方面的問(wèn)題：(1)數(shù)據(jù)的邏輯結(jié)構(gòu)(2)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)(3)對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行的運(yùn)算目的：提高數(shù)據(jù)處理的效率提高數(shù)據(jù)處理的速度盡量節(jié)省計(jì)算機(jī)存儲(chǔ)空間第三頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算42.1.1兩個(gè)例子

計(jì)算機(jī)已廣泛應(yīng)用于數(shù)據(jù)處理。實(shí)際問(wèn)題中的各數(shù)據(jù)元素之間總是相互關(guān)聯(lián)的。所謂數(shù)據(jù)處理，是指對(duì)數(shù)據(jù)集合中的各元素以各種方式進(jìn)行運(yùn)算，包括插入、刪除、查找、更改等運(yùn)算，以包括對(duì)數(shù)據(jù)元素進(jìn)行分析。第四頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算5重要的是知道數(shù)據(jù)集合中各數(shù)據(jù)元素之間存在什么關(guān)系，為了提高處理效率，應(yīng)如何組織它們，即如何表示所需要處理的數(shù)據(jù)元素。第五頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算6例2.1無(wú)序表的順序查找35167885432933215446

有序表的對(duì)分查找16212933354346547885數(shù)據(jù)元素在表中的排列順序?qū)Σ檎倚适怯泻艽笥绊懙诹?yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算7無(wú)序表的順序查找從第一個(gè)元素開(kāi)始，逐個(gè)將表中的元素與被查數(shù)進(jìn)行比較，直到表中的某個(gè)元素與被查數(shù)相等（即查找成功）或者表中所有元素都與被查數(shù)進(jìn)行了比較且都不相等（即查找失敗）為止。最少次數(shù)：被查元素剛好是表中第一個(gè)元素時(shí)。只需比較一次。最多次數(shù)：被查元素剛好是表中最后一個(gè)元素時(shí)或表中不存在被查元素。在這種情況下順序查找是很費(fèi)時(shí)間的。第七頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算8有序表中的二分查找將被查數(shù)與表中的中間這個(gè)元素進(jìn)行比較：若相等，則表示查找成功，查找過(guò)程結(jié)束；若被查數(shù)大于表中的中間這個(gè)元素，則表示如果被查數(shù)在表中，只能在表的后半部，此時(shí)可以舍棄表中的前半部保留后半部；若被查數(shù)小于表中的中間元素，則表示如果被查數(shù)在表中，只能在表的前半部此時(shí)可以舍棄后半部而保留前半部。然后對(duì)剩下部分再按照上述方法進(jìn)行查找，這個(gè)過(guò)程一直做到在某次的比較中相等（查找成功）或剩下的部分已空（查找失敗）為止。第八頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算9在有序表的對(duì)分查找中，不論查找的是什么數(shù)，也不論要查找的數(shù)在表中有沒(méi)有，都不需要與表中所有元素進(jìn)行比較，并且只需要與表中很少的元素進(jìn)行比較。但需要指出的是，對(duì)分查找只適用于有序表，而對(duì)于無(wú)序表是無(wú)法進(jìn)行對(duì)分查找的。第九頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算10結(jié)論：在對(duì)數(shù)據(jù)進(jìn)行處理時(shí)，可以根據(jù)所做的運(yùn)算不同，將數(shù)據(jù)組織成不同的形式，以便于做該種運(yùn)算，從而提高數(shù)據(jù)處理的效率。第十頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算112.1.2什么是數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素集合。

現(xiàn)實(shí)世界中客觀存在的一切個(gè)體都可以是數(shù)據(jù)元素。第十一頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算12描述一年四季的季節(jié)名

春，夏，秋，冬可以作為季節(jié)的數(shù)據(jù)元素；表示數(shù)值的各個(gè)數(shù)

18，11，35，23，16，…

可以作為數(shù)值的數(shù)據(jù)元素；表示家庭成員的各成員名

父親，兒子，女兒可以作為家庭成員的數(shù)據(jù)元素。第十二頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算13

前后件關(guān)系是數(shù)據(jù)元素之間的一個(gè)基本關(guān)系，但前后件關(guān)系所表示的實(shí)際意義是隨具體對(duì)象的不同而不同。一般來(lái)說(shuō)，數(shù)據(jù)元素之間的任何關(guān)系都可以用前后件關(guān)系來(lái)描述。例如：“春”是“夏”的前件，“夏”是“春”的后件。

“父親”是“兒子”，“女兒”的前件，“兒子”，“女兒”是“父親”的后續(xù)。第十三頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算141.數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。（1）表示數(shù)據(jù)元素的信息；（2）表示各數(shù)據(jù)元素之間的前后件關(guān)系。第十四頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算15數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個(gè)要素：數(shù)據(jù)元素的集合D；反映D中各數(shù)據(jù)元素之間的前后件關(guān)系R。

數(shù)據(jù)結(jié)構(gòu)可以表示成

B＝（D，R）其中B表示數(shù)據(jù)結(jié)構(gòu)。第十五頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算16為了反映D中各數(shù)據(jù)元素之間的前后件關(guān)系，一般用二元組來(lái)表示。設(shè)a與b是D中的兩個(gè)數(shù)據(jù)，則二元組（a，b）表示a是b的前件，b是a的后件。例如

B＝（D，R）

D＝{春，夏，秋，冬}R＝{(春，夏)，(夏，秋)，(秋，冬)}第十六頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算17家庭成員數(shù)據(jù)結(jié)構(gòu)

B＝（D，R）

D＝{父親，兒子，女兒}R＝{(父親，兒子），(父親，女兒）}n維向量X＝（x1，x2，…，xn）也是一種數(shù)據(jù)結(jié)構(gòu)。即

X＝（D，R）

D＝{x1，x2，…，xn}R＝{(x1，x2)，(x2，x3)，…，(xn－1，xn)}第十七頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算18m×n的矩陣是一個(gè)數(shù)據(jù)結(jié)構(gòu)。即

A＝（D，R）

D＝{A1，A2，…，Am}R＝{(A1，A2)，(A2，A3)，…，(Ai，Ai＋1)，…，(Am－1，Am)}其中Ai=（ai1，ai2，…，ain），i＝1，2，…，m

Ai＝（Di，Ri）

Di＝{ai1，ai2，…，ain}Ri＝{(ai1，ai2)，(ai2，ai3)，…，(aij，ai，j＋1)，…，(ai，n－1，ain)}第十八頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算192.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（數(shù)據(jù)的物理結(jié)構(gòu)）

數(shù)據(jù)的物理結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式。常用的存儲(chǔ)結(jié)構(gòu)有：順序、鏈接、索引等存儲(chǔ)結(jié)構(gòu)。采用不同的存儲(chǔ)結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的。第十九頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算202.1.3數(shù)據(jù)結(jié)構(gòu)的圖形表示數(shù)據(jù)集合D中的每一個(gè)數(shù)據(jù)元素用中間標(biāo)有元素值的方框表示（數(shù)據(jù)結(jié)點(diǎn)，結(jié)點(diǎn)）用一條有向線段從前件結(jié)點(diǎn)指向后件結(jié)點(diǎn)。第二十頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算21一年四季數(shù)據(jù)結(jié)構(gòu)的圖形表示第二十一頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算22家庭成員間輩份關(guān)系數(shù)據(jù)結(jié)的圖形表示第二十二頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算23DS1=(D1,R1)D1={a,b,c,d,e}R1={(a,b),(b,c),(c,d),(d,e),(e,a),(a,c),(a,d),(b,e),(c,e)}daebcDS1是個(gè)無(wú)向圖第二十三頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算24DS2=(D2,R2)D2={a,b,c,d,e}R2={〈a,b〉,〈b,c〉,〈c,d〉,〈d,e〉,〈e,a〉,〈a,c〉,〈a,d〉,〈b,e〉,〈c,e〉}daebcDS2是一個(gè)有向圖第二十四頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算25DS2=(D2,R2)D2={a1,a2,a3,…,ak}R2={<ai,ai+1>|{}}這說(shuō)明這個(gè)關(guān)系R2任何兩遞增下標(biāo)的數(shù)據(jù)元素都有相鄰關(guān)系，如圖所示a1a2a3……ak數(shù)組的數(shù)據(jù)結(jié)構(gòu)第二十五頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算26

用圖形表示數(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)}第二十六頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算27數(shù)據(jù)結(jié)構(gòu)的相關(guān)概念在數(shù)據(jù)結(jié)構(gòu)中，沒(méi)有前件的結(jié)點(diǎn)稱為根結(jié)點(diǎn)；沒(méi)有后件的結(jié)點(diǎn)成為終端結(jié)點(diǎn)（也稱為葉子結(jié)點(diǎn)）；除了根結(jié)點(diǎn)與終端結(jié)點(diǎn)外的其他結(jié)點(diǎn)一般稱為內(nèi)部結(jié)點(diǎn)。數(shù)據(jù)結(jié)構(gòu)中的相關(guān)運(yùn)算：插入運(yùn)算、刪除運(yùn)算。這兩個(gè)運(yùn)算是對(duì)數(shù)據(jù)結(jié)構(gòu)的兩種基本運(yùn)算。除此之外，對(duì)數(shù)據(jù)結(jié)構(gòu)的運(yùn)算還有查找、分類、合并、分解、復(fù)制和修改等。在一個(gè)數(shù)據(jù)結(jié)構(gòu)中元素結(jié)點(diǎn)和數(shù)據(jù)元素之間的關(guān)系都可能是動(dòng)態(tài)變化的。第二十七頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算282.1.4線性數(shù)據(jù)結(jié)構(gòu)與非線性數(shù)據(jù)結(jié)構(gòu)線性表的邏輯結(jié)構(gòu)是n個(gè)數(shù)據(jù)元素的有限序列(a1,a2,a3,……,an)其中n表示了線性表的長(zhǎng)度（n>=0）.n=0的表稱為空表。線性結(jié)構(gòu)：數(shù)據(jù)元素呈線性關(guān)系。隱含有序。

（1）有且只有一個(gè)根結(jié)點(diǎn)；（2）每一個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。線性結(jié)構(gòu)又稱線性表。第二十八頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算29特別說(shuō)明

在一個(gè)線性結(jié)構(gòu)中插入或刪除任何一個(gè)結(jié)點(diǎn)后還應(yīng)該是線性結(jié)構(gòu)。如果一個(gè)數(shù)據(jù)結(jié)構(gòu)滿足上述兩個(gè)條件，但當(dāng)在此數(shù)據(jù)結(jié)構(gòu)中插入或刪除任何一個(gè)結(jié)點(diǎn)后就不滿足這兩個(gè)條件了，則該數(shù)據(jù)結(jié)構(gòu)不能稱為線性結(jié)構(gòu)。第二十九頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算30不是線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)特例

第三十頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算31如果一個(gè)數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱之為非線性結(jié)構(gòu)第三十一頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算322.2線性表及其順序存儲(chǔ)結(jié)構(gòu)2.2.1線性表及其運(yùn)算2.2.2棧及其應(yīng)用2.2.3隊(duì)列及其應(yīng)用第三十二頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算332.2.1線性表及其運(yùn)算1.什么是線性表(LinearList)線性表是最簡(jiǎn)單最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表是由一組數(shù)據(jù)元素構(gòu)成。例如：n維向量(x1，x2，…，xn)是一個(gè)長(zhǎng)度為n的線性表，其中的每一個(gè)分量就是一個(gè)數(shù)據(jù)元素。英文小寫(xiě)字母表(a，b，c，…，z)是一個(gè)長(zhǎng)度為26的線性表一年中的四個(gè)季節(jié)(春，夏，秋，冬)是一個(gè)長(zhǎng)度為4的線性表矩陣是一個(gè)比較復(fù)雜的線性表第三十三頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算34學(xué)生情況登記表是一個(gè)復(fù)雜的線性表,由若干數(shù)據(jù)項(xiàng)組成的數(shù)據(jù)元素稱為記錄(record)由多個(gè)記錄構(gòu)成的線性表又稱為文件(file)第三十四頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算35

線性表是由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)第三十五頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算36非空線性表結(jié)構(gòu)特征：

(1)有且只有一個(gè)根結(jié)點(diǎn)a1，它無(wú)前件；

(2)有且只有一個(gè)終端結(jié)點(diǎn)an，它無(wú)后件；

(3)除根結(jié)點(diǎn)與終端結(jié)點(diǎn)外，其它所有結(jié)點(diǎn)有且只有一個(gè)前件，也有且只有一個(gè)后件。線性表中結(jié)點(diǎn)的個(gè)數(shù)n稱為線性表的長(zhǎng)度。當(dāng)n＝0時(shí)，稱為空表。第三十六頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算372.線性表的順序存儲(chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)結(jié)構(gòu)基本特點(diǎn)：(1)線性表中所有元素所占的存儲(chǔ)空間是連續(xù)的；(2)線性表中各數(shù)據(jù)元素在存儲(chǔ)空間中是按邏輯順序依次存放的。線性表中第i個(gè)元素ai在計(jì)算機(jī)存儲(chǔ)空間中的存儲(chǔ)地址為

ADR(ai)＝ADR(a1)＋(i－1)k第三十七頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算38長(zhǎng)度為n的線性表(a1，a2，…，ai，…，an)順序存儲(chǔ)結(jié)構(gòu)第三十八頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算39整型一維數(shù)組存放長(zhǎng)度為8的線性表(29,18,56,63,35,24,31,47)第三十九頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算40建立空線性表的順序存儲(chǔ)空間（即初始化線性表的順序存儲(chǔ)空間）

#include"stdlib.h"voidinitsl(v，m，n)ET*v；intm，*n；

{v＝malloc(m*sizeof(ET))；*n＝0；

return；

}釋放線性表的順序存儲(chǔ)空間

free(v)；第四十頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算41線性表順序存儲(chǔ)結(jié)構(gòu)下的主要運(yùn)算：(1)在線性表的指定位置處加入一個(gè)新的元素（即線性表的插入）；(2)在線性表中刪除指定的元素（即線性表的刪除）；(3)在線性表中查找某個(gè)（或某些）特定的元素（即線性表的查找）；(4)對(duì)線性表中的元素進(jìn)行整序（即線性表的排序）；(5)按要求將一個(gè)線性表分解成多個(gè)線性表（即線性表的分解）；(6)按要求將多個(gè)線性表合并成一個(gè)線性表（即線性表的合并）；(7)復(fù)制一個(gè)線性表（即線性表的復(fù)制）；(8)逆轉(zhuǎn)一個(gè)線性表（即線性表的逆轉(zhuǎn)）等。第四十一頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算423.線性表在順序存儲(chǔ)下的插入運(yùn)算第四十二頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算43第四十三頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算44線性表在順序存儲(chǔ)下的插入算法輸入：線性表的存儲(chǔ)空間V(1：m)；線性表的長(zhǎng)度n（n≤m）；插入的位置i（i表示在第i個(gè)元素之前插入）；插入的新元素b。輸出：插入后的線性表存儲(chǔ)空間V(1：m)及線性表的長(zhǎng)度n。

第四十四頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算45PROCEDUREINSL(V，m，n，i，b)1.IF(n＝m)THEN{OVERFLOW；RETURN}2.IF(i＞n)THENi＝n＋13.IF(i＜1)THENi＝14.FORj＝nTOiBY－1DOV(j＋1)＝V(j)5.V(i)＝b6.n＝n＋17.RETURN第四十五頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算46

voidinsl(v，m，n，i，b)ETv[]，b；intm，n，i；

{if(n＝＝m){printf("overflow\n")；return；}if(i＞n)i＝n＋1；在最后一個(gè)元素

if(i＜1)i＝1；在第一個(gè)元素之前

for(j＝n；j＜＝i；j――)v[j]＝v[j－1]；

v[i－1]＝b；

n＝n＋1；

return；

}第四十六頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算474.線性表在順序存儲(chǔ)下的刪除運(yùn)算第四十七頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算48第四十八頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算49線性表在順序存儲(chǔ)下的刪除算法輸入：線性表的存儲(chǔ)空間V(1：m)；線性表的長(zhǎng)度n（n≤m）；刪除的位置i（表示刪除第i個(gè)元素）。輸出：刪除后的線性表存儲(chǔ)空間V(1：m)及線性表的長(zhǎng)度n。

第四十九頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算50PROCEDUREDESL(V，m，n，i)1.IF(n＝0)THEN{UNDERFLOW；RETURN}2.IF(i＜1)or(i＞n)THEN{“Notthiselementinthelist”；RETURN}3.FORj＝iTOn－1DOV(j)＝V(j＋1)4.n＝n－15.RETURN第五十頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算51

voiddesl(v，m，n，i)ETv[]；intm，n，i；

{if(n＝＝0){printf("underflow\n")；return；}if((i＜1)||(i＞n)){printf("Notthiselementinthelist\n")；

return；

}for(j＝i；j＜＝n－1；j＋＋)v[j－1]＝v[j]；

n＝n－1；

return；

}第五十一頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算521.什么是棧棧（stack）是一種特殊的線性表。對(duì)它的操作只能是“后進(jìn)先出”（LIFO），也是使用最為廣泛的數(shù)據(jù)結(jié)構(gòu)之一。因?yàn)樗倪\(yùn)算次序受到嚴(yán)格的規(guī)定，故又稱為限定性數(shù)據(jù)結(jié)構(gòu)。為了認(rèn)識(shí)棧這種數(shù)據(jù)結(jié)構(gòu)，首先介紹一個(gè)例子。2.2.2棧及其應(yīng)用第五十二頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算53主程序與子程序之間的調(diào)用關(guān)系MAINSUB1SUB2SUB3SUB4

……

……

……

……

……CALLSUB1CALLSUB2CALLSUB3CALLSUB4……A：……B：……C：……D：……

……

……

……

……

……

……ENDRETURNRETURNRETURNRETURN第五十三頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算54由這個(gè)例子可以看出，在這種特殊的線性表中，其插入與刪除運(yùn)算都只能在線性表的一段進(jìn)行。即在這種線性表的結(jié)構(gòu)中，一端是封閉的，不允許插入和刪除元素；另一端是開(kāi)口的，允許插入與刪除元素。在順序存儲(chǔ)結(jié)構(gòu)下，對(duì)這種類型線性表的插入與刪除運(yùn)算是不需要移動(dòng)表中其它數(shù)據(jù)元素的。這種線性表稱為棧。第五十四頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算55棧(stack)是限定在一端進(jìn)行插入與刪除的線性表。棧頂:允許插入與刪除的一端.棧底:不允許插入與刪除的另一端。棧是按照“先進(jìn)后出”

(FILO—FirstInLastOut)或“后進(jìn)先出”

(LIFO—LastInFirstOut)的原則組織數(shù)據(jù)的，因此，棧也被稱為“先進(jìn)后出”表或“后進(jìn)先出”表。棧具有記憶作用。用指針top來(lái)指示棧頂?shù)奈恢茫弥羔榖ottom指向棧底。往棧中插入一個(gè)元素稱為入棧運(yùn)算，從棧中刪除一個(gè)元素(即刪除棧頂元素)稱為退棧運(yùn)算。關(guān)于棧的幾個(gè)基本概念第五十五頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算56第五十六頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算572.棧的順序存儲(chǔ)及其運(yùn)算第五十七頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算58top＝0表示棧空；top＝m表示棧滿。建立空棧的順序存儲(chǔ)空間（即初始化棧的順序存儲(chǔ)空間）

#include"stdlib.h"voidinit_stack(s，m，top)ETs；intm，*top；

{s＝malloc(m*sizeof(ET))；*top＝0；

return；

}釋放棧的順序存儲(chǔ)空間時(shí)free(s)；第五十八頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算59(1)入棧運(yùn)算

PROCEDUREPUSH(S，m，top，x)1.IF(top＝m)THEN{Stack－OVERFLOW；RETURN}2.top＝top＋13.S(top)＝x4.RETURN

voidpush(s，m，top，x)ETs[]，x；intm，*top；

{if(*top＝＝m){printf("Stack－overflow\n")；return；}*top＝*top＋1；s[*top]＝x；

return；

}第五十九頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算60(2)退棧運(yùn)算PROCEDUREPOP(S，m，top，y)1.IF(top＝0)THEN{Stack－UNDERFLOW；RETURN}2.y＝S(top)3.top＝top－14.RETURNvoidpop(s，m，top，y)ETs[]，y；intm，*top；{if(*top＝＝0){printf("Stack－underflow\n")；return；}y＝s[*top]；*top＝*top－1；

return；}第六十頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算61PROCEDURETOP(S，m，top，y)1.IF(top＝0)THEN{“Stackempty”；RETURN}2.y＝S(top)3.RETURN(3)讀棧頂元素voidtop(s，m，top，y)ETs[]，y；intm，*top；{if(*top＝＝0){printf("Stackempty\n")；return；}y＝s[*top]；

return；}第六十一頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算623.表達(dá)式的計(jì)算運(yùn)算符棧，用于在表達(dá)式處理過(guò)程中存放運(yùn)算符。在開(kāi)始時(shí)，運(yùn)算符棧中先壓入一個(gè)表達(dá)式結(jié)束符“；”。操作數(shù)棧，用于在表達(dá)式處理過(guò)程中存放操作數(shù)。第六十二頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算63從左到右依次讀出表達(dá)式中的各個(gè)符號(hào)：若是操作數(shù)，則壓入操作數(shù)棧，依次讀下一個(gè)符號(hào)。若是運(yùn)算符，則作進(jìn)一步判斷：第六十三頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算64①若讀出運(yùn)算符的優(yōu)先級(jí)大于運(yùn)算符棧棧頂運(yùn)算符的優(yōu)先級(jí)，則將讀出的運(yùn)算符壓入運(yùn)算符棧，并依次讀下一個(gè)符號(hào)。②若讀出的是表達(dá)式結(jié)束符“；”，且運(yùn)算符棧棧頂?shù)倪\(yùn)算符也是表達(dá)式結(jié)束符“；”，則表達(dá)式處理結(jié)束，最后的計(jì)算結(jié)果在操作數(shù)棧的棧頂位置。③若讀出運(yùn)算符的優(yōu)先級(jí)不大于運(yùn)算符棧棧頂運(yùn)算符的優(yōu)先級(jí)，則從操作數(shù)棧連續(xù)退出兩個(gè)操作數(shù)，并從運(yùn)算符棧退出一個(gè)運(yùn)算符，然后作相應(yīng)的運(yùn)算（運(yùn)算符為剛從運(yùn)算符棧退出的運(yùn)算符，運(yùn)算對(duì)象為剛從操作數(shù)棧退出的兩個(gè)操作數(shù)），并將運(yùn)算結(jié)果壓入操作數(shù)棧。第六十四頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算65A＋B*C－D/E；第六十五頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算66A＋B*C－D/E；第六十六頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算67A＋B*C－D/E；第六十七頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算68A＋B*C－D/E；第六十八頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算694.遞歸依次打印輸出自然數(shù)1到n的非遞歸算法PROCEDUREWRT(n)FORk＝1TOnDOOUTPUTkRETURN依次打印輸出自然數(shù)1到n的遞歸算法PROCEDUREWRT(n)IF(n≠0)THEN{WRT(n)；OUTPUTn}RETURN第六十九頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算70

#include"stdio.h"wrt(intn){if(n!＝0){wrt(n－1)；printf("%d\n"，n)；}return；

}第七十頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算712.2.3隊(duì)列及其應(yīng)用1.什么是隊(duì)列隊(duì)列(equeue)是指允許在一端進(jìn)行插入、而在另一端進(jìn)行刪除的線性表。數(shù)據(jù)結(jié)構(gòu)中的隊(duì)列與生活中的“排隊(duì)”極為相似，也是按“先來(lái)先解決”的原則行事的，并且既不允許“加塞”，也不允許“中途離隊(duì)”。第七十一頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算72關(guān)于隊(duì)列的幾個(gè)基本概念允許插入的一端稱為隊(duì)尾，用尾指針(rear)指向隊(duì)尾元素。允許刪除的一端稱為排頭(也稱隊(duì)頭)，用排頭指針(front)指向排頭元素的前一個(gè)位置。隊(duì)列又稱為“先進(jìn)先出”

(FIFO—FirstInFirst

Out)或“后進(jìn)后出”

(LILO—LastInLastOut)的線性表，體現(xiàn)了“先來(lái)先服務(wù)”的原則。往隊(duì)列的隊(duì)尾插入一個(gè)元素稱為入隊(duì)運(yùn)算，從隊(duì)列的排頭刪除一個(gè)元素稱為退隊(duì)運(yùn)算。第七十二頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算73第七十三頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算742.循環(huán)隊(duì)列及其運(yùn)算第七十四頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算75第七十五頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算76隊(duì)列空的條件為s＝0隊(duì)列滿的條件為(s＝1)且front＝rear第七十六頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算77建立循環(huán)隊(duì)列順序存儲(chǔ)空間（即初始化循環(huán)隊(duì)列順序存儲(chǔ)空間）#include"stdlib.h"voidinit_queue(q，m，front，rear，s)ET*q；intm，*front，*rear，s；{q＝malloc(m*sizeof(ET))；*front＝m；*rear＝m；s＝0；

return；}釋放循環(huán)隊(duì)列的順序存儲(chǔ)空間free(q)；第七十七頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算78入隊(duì)voidaddcq(q，m，rear，front，s，x)ETq[]，x；intm，*rear，*front，s；{if((s＝＝1)&&(rear＝＝front)){printf("Queue－OVERFLOW\n")；return；}rear＝rear＋1；if(rear＝＝m＋1)rear＝1；q[rear]＝x；s＝1；return；}第七十八頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算79退隊(duì)voiddelcq(q，m，rear，front，s，y)ETq[]，y；intm，*rear，*front，s；{if(s＝＝0){printf("Queue－UNDERFLOW\n")；return；}front＝front＋1；if(front＝＝m＋1)front＝1；y＝q[front]；if(front＝＝rear)s＝0；return；}第七十九頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算803.隊(duì)列的應(yīng)用

(1)給工人分配工作的模擬開(kāi)辟一個(gè)隊(duì)列結(jié)構(gòu)的線性表。設(shè)置一個(gè)排頭指針和一個(gè)隊(duì)尾指針。初始時(shí)隊(duì)列為空。每當(dāng)有一個(gè)工人到調(diào)度員處報(bào)到時(shí)（包括新來(lái)的與完成任務(wù)后返回的），都將他加入到隊(duì)尾；當(dāng)需要一名工人去做某項(xiàng)工作時(shí)，就排頭的工人去做該項(xiàng)工作。第八十頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算81(2)輸入輸出緩沖區(qū)的結(jié)構(gòu)第八十一頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算822.3線性鏈表及其運(yùn)算2.3.1線性鏈表的基本概念2.3.2線性鏈表的基本運(yùn)算2.3.3循環(huán)鏈表第八十二頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算832.3.1線性鏈表的基本概念1.線性鏈表線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為線性鏈表。第八十三頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算84第八十四頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算85第八十五頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算86第八十六頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算87第八十七頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算88依次輸出線性鏈表中的各結(jié)點(diǎn)值輸入：線性鏈表的存儲(chǔ)空間V(1：m)、NEXT(1：m)；線性鏈表的頭指針HEAD。輸出：依次輸出線性鏈表中各結(jié)點(diǎn)的值。

PROCEDUREPRTLL(HEAD)j＝HEADWHILE(j≠0)DO{OUTPUTV(j)；j＝NEXT(j)}RETURN第八十八頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算89

structnode{charname[10]；/*數(shù)據(jù)域*/charsex；/*數(shù)據(jù)域*/structnode*next；/*指針域*/}VoidPRTLL(node*head){node*p;p=head;while(p!=null){printf(“name=%c”,p->name);printf(“sex=%c”,p->sex);p=p->next;}}第八十九頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算90#include"stdlib.h"#include"stdio.h"structnode/*定義結(jié)點(diǎn)類型*/{intd；

structnode*next；

}main(){intx；

structnode*head，*p，*q；

head＝NULL；/*置鏈表空*/q＝NULL；

scanf(“%d”，&x)；/*輸入一個(gè)正整數(shù)*/第九十頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算91while(x＞0)/*若輸入值大于0*/{p＝(structnode*)malloc(sizeof(structnode))；/*申請(qǐng)一個(gè)結(jié)點(diǎn)*/p－>d＝x；p－>next＝NULL；/*置當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)域和指針域*/if(head＝＝NULL)head＝p；/*若鏈表空，則將頭指針指向當(dāng)前結(jié)點(diǎn)p*/elseq－>next＝p；/*將當(dāng)前結(jié)點(diǎn)鏈接在最后*/q＝p；/*置當(dāng)前結(jié)點(diǎn)為鏈表最后一個(gè)結(jié)點(diǎn)*/scanf("%d"，&x)；}}第九十一頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算92雙向鏈表第九十二頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算932.帶鏈的棧第九十三頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算94可利用棧及其運(yùn)算第九十四頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算95#include"stdlib.h"structnode/*定義結(jié)點(diǎn)類型*/{ETd；/*數(shù)據(jù)元素類型*/structnode*next；

}；ETx；structnode*top；pushll(top，x){structnode*p；

p＝(structnode*)malloc(sizeof(structnode))；

p－>d＝x；p－>next＝top；/*置新結(jié)點(diǎn)的數(shù)據(jù)域與指針域*/top＝p；/*改變棧頂指針*/return；}第九十五頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算96帶鏈棧的退棧運(yùn)算輸入：帶鏈棧的棧頂指針top。輸出：退棧后的帶鏈棧棧頂指針top；存放退出結(jié)點(diǎn)元素值的變量y。PROCEDUREPOPLL(top，y)y＝V(top)[取出棧頂元素值]p＝toptop=NEXT(p)[改變棧頂指針]DISPOSE(p)[被刪除結(jié)點(diǎn)送回可利用棧]RETURN第九十六頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算97#include"stdlib.h"structnode/*定義結(jié)點(diǎn)類型*/{ETd；/*數(shù)據(jù)元素類型*/structnode*next；}；popll(top，y)ETy；structnode*top；{structnode*p；y＝top－>d；/*取出棧頂元素值*/p＝top；top＝p－>next；/*改變棧頂指針*/free(p)；return；/*釋放被刪除結(jié)點(diǎn)后返回*/}第九十七頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算983.帶鏈的隊(duì)列第九十八頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算99帶鏈隊(duì)列的入隊(duì)運(yùn)算輸入：帶鏈隊(duì)列的隊(duì)尾指針rear；入隊(duì)的新元素x。輸出：元素x入隊(duì)后的帶鏈隊(duì)列隊(duì)尾指針rear。

PROCEDUREADDLL(rear，x)NEW(p)[從可利用棧取得一個(gè)新結(jié)點(diǎn)p]V(p)＝x[置新結(jié)點(diǎn)的數(shù)據(jù)域]NEXT(p)＝0[置新結(jié)點(diǎn)的指針為空]NEXT(rear)＝p[最后一個(gè)結(jié)點(diǎn)的指針指向新結(jié)點(diǎn)]rear＝p[改變隊(duì)尾指針]RETURN第九十九頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算100#include"stdlib.h"structnode/*定義結(jié)點(diǎn)類型*/{ETd；/*數(shù)據(jù)元素類型*/structnode*next；

}；addll(rear，x)ETx；structnode*rear；{structnode*p；

p＝(structnode*)malloc(sizeof(structnode))；

p－>d＝x；p－>next＝NULL；/*置新結(jié)點(diǎn)的數(shù)據(jù)域與指針域*/rear－>next＝p；/*置最后一個(gè)結(jié)點(diǎn)的指針指向新結(jié)點(diǎn)*/rear＝p；/*改變隊(duì)尾指針*/return；}第一百頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算101帶鏈隊(duì)列的退隊(duì)運(yùn)算輸入：帶鏈隊(duì)列的排頭指針front。輸出：退隊(duì)后的帶鏈隊(duì)列排頭指針front；存放退出結(jié)點(diǎn)值的變量y。

PROCEDUREDELLL(front，y)y=V(front)[取出排頭元素值]p＝frontfront＝NEXT(front)[改變排頭指針]DISPOSE(p)[釋放刪除的結(jié)點(diǎn)]RETURN第一百零一頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算102#include"stdlib.h"structnode/*定義結(jié)點(diǎn)類型*/{ETd；/*數(shù)據(jù)元素類型*/structnode*next；

}；delll(front，y)ETy；structnode*front；{structnode*p；

y＝front－>d；/*取出排頭元素值*/p＝front；

front＝p－>next；/*改變排頭指針*/free(p)；/*釋放被刪除結(jié)點(diǎn)*/return；}第一百零二頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算1032.3.2線性鏈表的基本運(yùn)算(1)在線性鏈表中包含指定元素的結(jié)點(diǎn)之前插入一個(gè)新元素。(2)在線性鏈表中刪除包含指定元素的結(jié)點(diǎn)。(3)將兩個(gè)線性鏈表按要求合并成一個(gè)線性鏈表。(4)將一個(gè)線性鏈表按要求進(jìn)行分解。(5)逆轉(zhuǎn)線性鏈表。(6)復(fù)制線性鏈表。(7)線性鏈表的排序。(8)線性鏈表的查找。第一百零三頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算1041.在線性鏈表中查找指定元素在非空線性鏈表中尋找包含元素x的前一個(gè)結(jié)點(diǎn)輸入：非空線性鏈表頭指針HEAD；被尋找元素x。輸出：非空線性鏈表中包含元素x的前一個(gè)結(jié)點(diǎn)。PROCEDURELOOKST(HEAD，x，p)p＝HEADWHILE(NEXT(p)≠0)and(V(NEXT(p))≠x)DOp＝NEXT(p)RETURN第一百零四頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算105structnode/*定義結(jié)點(diǎn)類型*/{ETd；/*數(shù)據(jù)元素類型*/structnode*next；

}；structnode*lookst(head，x)ETx；structnode*head；{structnode*p；

p＝head；

while((p－>next!＝NULL)&&(((p－>next)－>d)!＝x))p＝p－>next；

return(p)；}第一百零五頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算1062.線性鏈表的插入在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的線性表中插入一個(gè)新元素。第一百零六頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算107可利用棧與線性鏈表第一百零七頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算108(1)從可利用棧取得一個(gè)結(jié)點(diǎn)，設(shè)該結(jié)點(diǎn)號(hào)為p。并置結(jié)點(diǎn)p的數(shù)據(jù)域?yàn)椴迦氲脑刂礲，即V(p)＝b。(2)在線性鏈表中尋找包含元素x的前一個(gè)結(jié)點(diǎn)q。第一百零八頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算109(3)將結(jié)點(diǎn)p插入到結(jié)點(diǎn)q之后：①使結(jié)點(diǎn)p指向包含元素x的結(jié)點(diǎn)，即

NEXT(p)＝NEXT(q)②使結(jié)點(diǎn)q的指針域內(nèi)容改為指向結(jié)點(diǎn)p，即

NEXT(q)＝p第一百零九頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算110線性鏈表的插入輸入：線性鏈表的頭指針HEAD；插入位置處的前一個(gè)結(jié)點(diǎn)值x；插入的新元素b。輸出：插入后的線性鏈表。PROCEDUREINSLST(HEAD，x，b)1.NEW(p)2.V(p)＝b3.IF(HEAD＝0)THEN{HEAD＝p；NEXT(p)＝0；RETURN}4.IF(V(HEAD)＝x)THEN{NEXT(p)＝HEAD；HEAD＝p；RETURN}5.LOOKST(HEAD，x，q)6.NEXT(p)＝NEXT(q)；NEXT(q)＝p7.RETURN第一百一十頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算111#include"stdlib.h"structnode/*定義結(jié)點(diǎn)類型*/{ETd；structnode*next；}；inslst(head，x，b)ETx，b；structnode*head；{structnode*p，*q；

p＝(structnode*)malloc(sizeof(structnode))；

p－>d＝b；/*置結(jié)點(diǎn)的數(shù)據(jù)域*/if(head＝＝NULL)/*鏈表為空*/{head＝p；p－>next＝NULL；return；}if((head－>d)＝＝x)/*在第一個(gè)結(jié)點(diǎn)前插入*/{p－>next＝head；head＝p；return；}q＝lookst(head，x)；/*尋找包含元素x的前一個(gè)結(jié)點(diǎn)q*/p－>next＝q－>next；q－>next＝p；/*結(jié)點(diǎn)p插到結(jié)點(diǎn)q之后*/return；}第一百一十一頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算1123.線性鏈表的刪除在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的線性表中刪除包含指定元素的結(jié)點(diǎn)。第一百一十二頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算113可利用棧與線性鏈表第一百一十三頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算114(1)尋找包含元素x的前一個(gè)結(jié)點(diǎn)q。則包含元素x的結(jié)點(diǎn)序號(hào)p＝NEXT(q)。(2)將結(jié)點(diǎn)q后的結(jié)點(diǎn)p刪除，即

NEXT(q)＝NEXT(p)。第一百一十四頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算115(3)將包含元素x的結(jié)點(diǎn)p送回可利用棧。第一百一十五頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算116線性鏈表的刪除輸入：線性鏈表的頭指針HEAD；需刪除的元素x。輸出：刪除后的線性鏈表。PROCEDUREDELST(HEAD，x)1.IF(HEAD＝0)THEN{“Thisisaemptylist!”；RETURN}2.IF(V(HEAD)＝x)THEN{p＝NEXT(HEAD)；DISPOSE(HEAD)；HEAD＝p；RETURN}3.LOOKST(HEAD，x，q)4.IF(NEXT(q)＝0)THEN{“Nothisnodeinthelist!”；RETURN}5.p＝NEXT(q)；NEXT(q)＝NEXT(p)6.DISPOSE(p)7.RETURN第一百一十六頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算117#include"stdlib.h"structnode/*定義結(jié)點(diǎn)類型*/{ETd；structnode*next；}；delst(head，x)ETx；structnode*head；{structnode*p，*q；

if(head＝＝NULL)/*鏈表為空*/{printf("Thisisaemptylist!\n")；return；}if((head－>d)＝＝x)/*刪除第一個(gè)結(jié)點(diǎn)*/{p＝head－>next；free(head)；head＝p；return；}q＝lookst(head，x)；/*尋找包含元素x的前一個(gè)結(jié)點(diǎn)q*/if(q－>next＝＝NULL)/*鏈表中沒(méi)有包含元素x的結(jié)點(diǎn)*/{printf("Nothisnodeinthelist!\n")；return；}p＝q－>next；q－>next＝p－>next；/*刪除結(jié)點(diǎn)p*/free(p)；/*釋放結(jié)點(diǎn)p*/return；}第一百一十七頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算1182.3.3循環(huán)鏈表與線性鏈表相比，循環(huán)鏈表具有以下特點(diǎn)：(1)在循環(huán)鏈表中增加了一個(gè)表頭結(jié)點(diǎn)，其數(shù)據(jù)域?yàn)槿我饣蚋鶕?jù)需要來(lái)設(shè)置，指針域指向線性表第一個(gè)元素的結(jié)點(diǎn)。循環(huán)鏈表的頭指針指向表頭結(jié)點(diǎn)。(2)循環(huán)鏈表中最后一個(gè)結(jié)點(diǎn)的指針域不空，而是指向表頭結(jié)點(diǎn)。即在循環(huán)鏈表中，所有結(jié)點(diǎn)的指針構(gòu)成了一個(gè)環(huán)狀鏈。第一百一十八頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算119(1)在循環(huán)鏈表中，只要指出表中任何一個(gè)結(jié)點(diǎn)的位置，就可以從它出發(fā)訪問(wèn)到表中其他所有的結(jié)點(diǎn)。(2)空表與非空表的運(yùn)算統(tǒng)一。第一百一十九頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算120在頭指針為HEAD的循環(huán)鏈表中尋找包含元素x的前一個(gè)結(jié)點(diǎn)輸入：循環(huán)鏈表的頭指針HEAD；被尋找的元素x。輸出：循環(huán)鏈表中包含元素x的前一個(gè)結(jié)點(diǎn)p。PROCEDURELOOKCST(HEAD，x，p)p＝HEADWHILE(NEXT(p)≠HEAD)and(V(NEXT(p))≠x)DOp＝NEXT(p)RETURN第一百二十頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算121#include"stdlib.h"structnode/*定義結(jié)點(diǎn)類型*/{ETd；structnode*next；}；structnode*lookcst(head，x)ETx；structnode*head；{structnode*p；

p＝head；

while((p－>next!＝head)&&(((p－>next)－>d)!＝x))p＝p－>next；

return(p)；}第一百二十一頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算122在頭指針為HEAD的循環(huán)鏈表中包含元素x的結(jié)點(diǎn)前插入新元素b輸入：循環(huán)鏈表的頭指針HEAD；插入位置處的前一個(gè)結(jié)點(diǎn)值x；插入的新元素b。輸出：插入后的循環(huán)鏈表。PROCEDUREINSCST(HEAD，x，b)NEW(p)[從可利用棧取得一個(gè)新結(jié)點(diǎn)p]V(p)＝b[置新結(jié)點(diǎn)p的數(shù)據(jù)域（插入的元素值b）]LOOKCST(HEAD，x，q)[尋找循環(huán)鏈表中包含元素x的前一個(gè)結(jié)點(diǎn)q]NEXT(p)＝NEXT(q)；NEXT(q)＝p[將新結(jié)點(diǎn)p插入到結(jié)點(diǎn)q之后]RETURN第一百二十二頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算123#include"stdlib.h"structnode/*定義結(jié)點(diǎn)類型*/{ETd；structnode*next；}；inscst(head，x，b)ETx，b；structnode*head；{structnode*p，*q；

p＝(structnode*)malloc(sizeof(structnode))；

p－>d＝b；/*置結(jié)點(diǎn)的數(shù)據(jù)域*/q＝lookcst(head，x)；/*尋找包含元素x的前一個(gè)結(jié)點(diǎn)q*/p－>next＝q－>next；q－>next＝p；/*結(jié)點(diǎn)p插入到結(jié)點(diǎn)q后*/return；}第一百二十三頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算124在頭指針為HEAD的循環(huán)鏈表中刪除包含元素x的結(jié)點(diǎn)輸入：循環(huán)鏈表的頭指針HEAD；需刪除的元素x。輸出：刪除后的循環(huán)鏈表。PROCEDUREDELCST(HEAD，x)LOOKCST(HEAD，x，q)[尋找包含元素x的前一個(gè)結(jié)點(diǎn)q]IF(NEXT(q)＝HEAD)THEN[循環(huán)鏈表中沒(méi)有該結(jié)點(diǎn)]{“Nothisnodeinthelist!”；RETURN}p＝NEXT(q)；NEXT(q)＝NEXT(p)[刪除結(jié)點(diǎn)q后的結(jié)點(diǎn)]DISPOSE(p)[將被刪除的結(jié)點(diǎn)p送回可利用棧]RETURN第一百二十四頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算125#include"stdlib.h"structnode/*定義結(jié)點(diǎn)類型*/{ETd；structnode*next；}；delcst(head，x)ETx；structnode*head；{structnode*p，*q；

q＝lookcst(head，x)；/*尋找包含元素x的前一個(gè)結(jié)點(diǎn)q*/if(q－>next＝＝head)/*鏈表中沒(méi)有包含元素x的結(jié)點(diǎn)*/{printf("Nothisnodeinthelist!\n")；return；}p＝q－>next；q－>next＝p－>next；/*刪除結(jié)點(diǎn)p*/free(p)；/*釋放結(jié)點(diǎn)p*/return；}第一百二十五頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算1262.4樹(shù)與二叉樹(shù)2.4.1樹(shù)的基本概念2.4.2二叉樹(shù)及其基本性質(zhì)2.4.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)2.4.4二叉樹(shù)的遍歷第一百二十六頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算1272.4.1樹(shù)的基本概念第一百二十七頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算128用圖形表示樹(shù)這種數(shù)據(jù)結(jié)構(gòu)時(shí)，很像自然界中的樹(shù)。只不過(guò)是一顆倒置的樹(shù)。因此將這種數(shù)據(jù)結(jié)構(gòu)用“樹(shù)”來(lái)命名。在樹(shù)的圖形中總是認(rèn)為在用直線連接起來(lái)的兩端結(jié)點(diǎn)中，上端結(jié)點(diǎn)是前件下端結(jié)點(diǎn)是后件，所以省略了箭頭。第一百二十八頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算129在現(xiàn)實(shí)世界中，能用樹(shù)這種數(shù)據(jù)結(jié)構(gòu)表示的例子很多！第一百二十九頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算130第一百三十頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算131第一百三十一頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算132樹(shù)中的幾個(gè)基本術(shù)語(yǔ)父結(jié)點(diǎn)：在樹(shù)中，每一個(gè)結(jié)點(diǎn)只有一個(gè)前件稱為父結(jié)點(diǎn)。根：在樹(shù)中，沒(méi)有前件的結(jié)點(diǎn)只有一個(gè)，成為樹(shù)的根結(jié)點(diǎn)。簡(jiǎn)稱根。子結(jié)點(diǎn)：在樹(shù)中，每一個(gè)結(jié)點(diǎn)可以有多個(gè)后件，稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)。沒(méi)有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。度：在樹(shù)中，一個(gè)結(jié)點(diǎn)所擁有的后件個(gè)數(shù)稱為該結(jié)點(diǎn)的度。樹(shù)的度：在樹(shù)中，所有結(jié)點(diǎn)中的最大度。第一百三十二頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算133樹(shù)的深度：樹(shù)的最大層次。子樹(shù)：在樹(shù)中，以某結(jié)點(diǎn)的一個(gè)子結(jié)點(diǎn)為根構(gòu)成的樹(shù)。第一百三十三頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算134樹(shù)是一種層次結(jié)構(gòu)。一般按以下原則分層：（1）根結(jié)點(diǎn)在第1層（2）同一層上所有結(jié)點(diǎn)的所有子結(jié)點(diǎn)在下一層第一百三十四頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算135在計(jì)算機(jī)中，可以用樹(shù)表示算術(shù)表達(dá)式。原則如下：（1）表達(dá)式中的每一個(gè)運(yùn)算符在樹(shù)中對(duì)應(yīng)一個(gè)結(jié)點(diǎn)，稱為運(yùn)算符結(jié)點(diǎn)。（2）運(yùn)算符的每一個(gè)運(yùn)算對(duì)象在樹(shù)中為該運(yùn)算符結(jié)點(diǎn)的子樹(shù)（在樹(shù)中的順序?yàn)閺淖蟮接遥＃?）運(yùn)算對(duì)象中的單變量均為葉子結(jié)點(diǎn)第一百三十五頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算136a*(b＋c/d)＋e*h－g*f(s，t，x＋y)第一百三十六頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算137a*(b＋c/d)＋e*h－g*f(s，t，x＋y)第一百三十七頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算138樹(shù)鏈表中的結(jié)點(diǎn)結(jié)構(gòu)第一百三十八頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算1391.什么是二叉樹(shù)（binarytree）

(1)非空二叉樹(shù)只有一個(gè)根結(jié)點(diǎn)；

(2)每一個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)，且分別稱為該結(jié)點(diǎn)的左子樹(shù)與右子樹(shù)。2.4.2二叉樹(shù)及其基本性質(zhì)第一百三十九頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算1402.二叉樹(shù)的基本性質(zhì)性質(zhì)1在二叉樹(shù)的第k層上，最多有2k－1(k≥1)個(gè)結(jié)點(diǎn)。性質(zhì)2深度為m的二叉樹(shù)最多有2m－1個(gè)結(jié)點(diǎn)。性質(zhì)3在任意一棵二叉樹(shù)中，度為0的結(jié)點(diǎn)即葉子結(jié)點(diǎn)總是比度為2的結(jié)點(diǎn)多一個(gè)。性質(zhì)4具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，其深度至少為

[log2n]＋1

其中[log2n]表示取log2n的整數(shù)部分。第一百四十頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算1413.滿二叉樹(shù)與完全二叉樹(shù)(1)滿二叉樹(shù)第一百四十一頁(yè)，共一百六十二頁(yè)，2022年，8月28日第2章基本數(shù)據(jù)結(jié)構(gòu)及其運(yùn)算142滿二叉樹(shù)是這樣一種二叉樹(shù)：除最后一層外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)