計算機軟件基礎(chǔ)基本數(shù)據(jù)結(jié)構(gòu)修改

計算機軟件基礎(chǔ)基本數(shù)據(jù)結(jié)構(gòu)修改第1頁，課件共171頁，創(chuàng)作于2023年2月2.1數(shù)據(jù)結(jié)構(gòu)的基本概念2.1.1兩個例子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)2第2頁，課件共171頁，創(chuàng)作于2023年2月數(shù)據(jù)結(jié)構(gòu)三個方面的問題：(1)數(shù)據(jù)的邏輯結(jié)構(gòu)(2)數(shù)據(jù)的存儲結(jié)構(gòu)(3)對各種數(shù)據(jù)結(jié)構(gòu)進行的運算目的：提高數(shù)據(jù)處理的效率提高數(shù)據(jù)處理的速度盡量節(jié)省計算機存儲空間3第3頁，課件共171頁，創(chuàng)作于2023年2月2.1.1兩個例子

計算機已廣泛應(yīng)用于數(shù)據(jù)處理。實際問題中的各數(shù)據(jù)元素之間總是相互關(guān)聯(lián)的。所謂數(shù)據(jù)處理，是指對數(shù)據(jù)集合中的各元素以各種方式進行運算，包括插入、刪除、查找、更改等運算，以包括對數(shù)據(jù)元素進行分析。4第4頁，課件共171頁，創(chuàng)作于2023年2月

重要的是知道數(shù)據(jù)集合中各數(shù)據(jù)元素之間存在什么關(guān)系，為了提高處理效率，應(yīng)如何組織它們，即如何表示所需要處理的數(shù)據(jù)元素。5第5頁，課件共171頁，創(chuàng)作于2023年2月例2.1無序表的順序查找35167885432933215446

有序表的對分查找16212933354346547885數(shù)據(jù)元素在表中的排列順序?qū)Σ檎倚适怯泻艽笥绊?第6頁，課件共171頁，創(chuàng)作于2023年2月無序表的順序查找從第一個元素開始，逐個將表中的元素與被查數(shù)進行比較，直到表中的某個元素與被查數(shù)相等（即查找成功）或者表中所有元素都與被查數(shù)進行了比較且都不相等（即查找失?。橹?。最少次數(shù)：被查元素剛好是表中第一個元素時。只需比較一次。最多次數(shù)：被查元素剛好是表中最后一個元素時或表中不存在被查元素。在這種情況下順序查找是很費時間的。7第7頁，課件共171頁，創(chuàng)作于2023年2月有序表中的二分查找

將被查數(shù)與表中的中間這個元素進行比較：若相等，則表示查找成功，查找過程結(jié)束；若被查數(shù)大于表中的中間這個元素，則表示如果被查數(shù)在表中，只能在表的后半部，此時可以舍棄表中的前半部保留后半部；若被查數(shù)小于表中的中間元素，則表示如果被查數(shù)在表中，只能在表的前半部此時可以舍棄后半部而保留前半部。然后對剩下部分再按照上述方法進行查找，這個過程一直做到在某次的比較中相等（查找成功）或剩下的部分已空（查找失?。橹?。8第8頁，課件共171頁，創(chuàng)作于2023年2月

在有序表的對分查找中，不論查找的是什么數(shù)，也不論要查找的數(shù)在表中有沒有，都不需要與表中所有元素進行比較，并且只需要與表中很少的元素進行比較。但需要指出的是，對分查找只適用于有序表，而對于無序表是無法進行對分查找的。9第9頁，課件共171頁，創(chuàng)作于2023年2月例2.2學(xué)生情況登記表以學(xué)號為順序排列10第10頁，課件共171頁，創(chuàng)作于2023年2月11第11頁，課件共171頁，創(chuàng)作于2023年2月12第12頁，課件共171頁，創(chuàng)作于2023年2月結(jié)論：在對數(shù)據(jù)進行處理時，可以根據(jù)所做的運算不同，將數(shù)據(jù)組織成不同的形式，以便于做該種運算，從而提高數(shù)據(jù)處理的效率。13第13頁，課件共171頁，創(chuàng)作于2023年2月2.1.2什么是數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)(datastructure)是指相互有關(guān)聯(lián)的數(shù)據(jù)元素集合。數(shù)據(jù)元素（dataelement）是數(shù)據(jù)集合中的一個個體，是數(shù)據(jù)的基本單位。14第14頁，課件共171頁，創(chuàng)作于2023年2月例1：描述一年四季的季節(jié)名

春，夏，秋，冬

可以作為季節(jié)的數(shù)據(jù)元素；例2：數(shù)值集合N={1,2,3,4,5}中整數(shù)1至5均為數(shù)據(jù)元素。例3：表示家庭成員的各成員名

父親，兒子，女兒

可以作為家庭成員的數(shù)據(jù)元素。現(xiàn)實世界中客觀存在的一切個體都可以是數(shù)據(jù)元素。15第15頁，課件共171頁，創(chuàng)作于2023年2月

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

“父親”是“兒子”，“女兒”的前件，“兒子”，“女兒”是“父親”的后續(xù)。16第16頁，課件共171頁，創(chuàng)作于2023年2月1.數(shù)據(jù)的邏輯結(jié)構(gòu)是指反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)。研究數(shù)據(jù)元素及其關(guān)系的數(shù)學(xué)特性；（1）表示數(shù)據(jù)元素的信息；（2）表示各數(shù)據(jù)元素之間的前后件關(guān)系。17第17頁，課件共171頁，創(chuàng)作于2023年2月

數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個要素：數(shù)據(jù)元素的集合D；反映D中各數(shù)據(jù)元素之間的前后件關(guān)系R。

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

S＝（D，R）其中B表示數(shù)據(jù)結(jié)構(gòu)。18第18頁，課件共171頁，創(chuàng)作于2023年2月為了反映D中各數(shù)據(jù)元素之間的前后件關(guān)系，一般用二元組來表示。設(shè)a與b是D中的兩個數(shù)據(jù)，則二元組（a，b）表示a是b的前件，b是a的后件。例如

S＝（D，R）

D＝{春，夏，秋，冬}R＝{(春，夏)，(夏，秋)，(秋，冬)}19第19頁，課件共171頁，創(chuàng)作于2023年2月家庭成員數(shù)據(jù)結(jié)構(gòu)

S＝（D，R）

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

S＝（D，R）

D＝{x1，x2，…，xn}R＝{(x1，x2)，(x2，x3)，…，(xn－1，xn)}20第20頁，課件共171頁，創(chuàng)作于2023年2月m×n的矩陣是一個數(shù)據(jù)結(jié)構(gòu)。即

S＝（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)}21第21頁，課件共171頁，創(chuàng)作于2023年2月2.數(shù)據(jù)的存儲結(jié)構(gòu)（數(shù)據(jù)的物理結(jié)構(gòu)）數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機存儲空間中的存放形式。也就是具體實現(xiàn)，通常用高級語言中各種數(shù)據(jù)類型來描述這種實現(xiàn)。常用的存儲結(jié)構(gòu)有：順序、鏈接、索引等存儲結(jié)構(gòu)。采用不同的存儲結(jié)構(gòu)，其數(shù)據(jù)處理的效率是不同的。22第22頁，課件共171頁，創(chuàng)作于2023年2月2.1.3數(shù)據(jù)結(jié)構(gòu)的圖形表示數(shù)據(jù)集合D中的每一個數(shù)據(jù)元素用中間標有元素值的方框表示（數(shù)據(jù)結(jié)點，結(jié)點）用一條有向線段從前件結(jié)點指向后件結(jié)點。23第23頁，課件共171頁，創(chuàng)作于2023年2月

一年四季數(shù)據(jù)結(jié)構(gòu)的圖形表示24第24頁，課件共171頁，創(chuàng)作于2023年2月家庭成員間輩份關(guān)系數(shù)據(jù)結(jié)的圖形表示25第25頁，課件共171頁，創(chuàng)作于2023年2月S=(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是個無向圖26第26頁，課件共171頁，創(chuàng)作于2023年2月S=(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是一個有向圖27第27頁，課件共171頁，創(chuàng)作于2023年2月S=(D,R)D={a1,a2,a3,…,ak}R={<ai,ai+1>|{}}這說明這個關(guān)系R任何兩遞增下標的數(shù)據(jù)元素都有相鄰關(guān)系，如圖所示a1a2a3……ak數(shù)組的數(shù)據(jù)結(jié)構(gòu)28第28頁，課件共171頁，創(chuàng)作于2023年2月

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

（1）有且只有一個根結(jié)點；（2）每一個結(jié)點最多有一個前件，也最多有一個后件。線性結(jié)構(gòu)又稱線性表。31第31頁，課件共171頁，創(chuàng)作于2023年2月特別說明

在一個線性結(jié)構(gòu)中插入或刪除任何一個結(jié)點后還應(yīng)該是線性結(jié)構(gòu)。如果一個數(shù)據(jù)結(jié)構(gòu)滿足上述兩個條件，但當(dāng)在此數(shù)據(jù)結(jié)構(gòu)中插入或刪除任何一個結(jié)點后就不滿足這兩個條件了，則該數(shù)據(jù)結(jié)構(gòu)不能稱為線性結(jié)構(gòu)。32第32頁，課件共171頁，創(chuàng)作于2023年2月不是線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)特例

33第33頁，課件共171頁，創(chuàng)作于2023年2月

如果一個數(shù)據(jù)結(jié)構(gòu)不是線性結(jié)構(gòu)，則稱之為非線性結(jié)構(gòu)34第34頁，課件共171頁，創(chuàng)作于2023年2月2.2線性表及其順序存儲結(jié)構(gòu)2.2.1線性表及其運算2.2.2棧及其應(yīng)用2.2.3隊列及其應(yīng)用35第35頁，課件共171頁，創(chuàng)作于2023年2月2.2.1線性表及其運算1.什么是線性表(LinearList)線性表是最簡單最常用的一種數(shù)據(jù)結(jié)構(gòu)。線性表是由一組數(shù)據(jù)元素構(gòu)成。例如：n維向量(x1，x2，…，xn)是一個長度為n的線性表，其中的每一個分量就是一個數(shù)據(jù)元素。英文小寫字母表(a，b，c，…，z)是一個長度為26的線性表一年中的四個季節(jié)(春，夏，秋，冬)是一個長度為4的線性表矩陣是一個比較復(fù)雜的線性表36第36頁，課件共171頁，創(chuàng)作于2023年2月學(xué)生情況登記表是一個復(fù)雜的線性表,由若干數(shù)據(jù)項組成的數(shù)據(jù)元素稱為記錄(record)由多個記錄構(gòu)成的線性表又稱為文件(file)37第37頁，課件共171頁，創(chuàng)作于2023年2月

線性表是由n(n≥0)個數(shù)據(jù)元素a1，a2，…，an組成的一個有限序列，表中的每一個數(shù)據(jù)元素，除了第一個外，有且只有一個前件，除了最后一個外，有且只有一個后件。即線性表或是一個空表，或可以表示為

(a1，a2，…，ai，…，an)

其中ai(i＝1，2，…，n)是屬于數(shù)據(jù)對象的元素，通常也稱其為線性表中的一個結(jié)點。線性表的邏輯結(jié)構(gòu)38第38頁，課件共171頁，創(chuàng)作于2023年2月

非空線性表結(jié)構(gòu)特征：

(1)有且只有一個根結(jié)點a1，它無前件；

(2)有且只有一個終端結(jié)點an，它無后件；

(3)除根結(jié)點與終端結(jié)點外，其它所有結(jié)點有且只有一個前件，也有且只有一個后件。線性表中結(jié)點的個數(shù)n稱為線性表的長度。當(dāng)n＝0時，稱為空表。39第39頁，課件共171頁，創(chuàng)作于2023年2月2.線性表的順序存儲結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)基本特點：(1)線性表中所有元素所占的存儲空間是連續(xù)的；(2)線性表中各數(shù)據(jù)元素在存儲空間中是按邏輯順序依次存放的。線性表中第i個元素ai在計算機存儲空間中的存儲地址為

ADR(ai)＝ADR(a1)＋(i－1)k40第40頁，課件共171頁，創(chuàng)作于2023年2月長度為n的線性表(a1，a2，…，ai，…，an)順序存儲結(jié)構(gòu)41第41頁，課件共171頁，創(chuàng)作于2023年2月整型一維數(shù)組存放長度為8的線性表(29,18,56,63,35,24,31,47)42第42頁，課件共171頁，創(chuàng)作于2023年2月建立空線性表的順序存儲空間（即初始化線性表的順序存儲空間）

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

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

return；

}釋放線性表的順序存儲空間

free(v)；43第43頁，課件共171頁，創(chuàng)作于2023年2月

線性表順序存儲結(jié)構(gòu)下的主要運算：(1)在線性表的指定位置處加入一個新的元素（即線性表的插入）；(2)在線性表中刪除指定的元素（即線性表的刪除）；(3)在線性表中查找某個（或某些）特定的元素（即線性表的查找）；(4)對線性表中的元素進行整序（即線性表的排序）；(5)按要求將一個線性表分解成多個線性表（即線性表的分解）；(6)按要求將多個線性表合并成一個線性表（即線性表的合并）；(7)復(fù)制一個線性表（即線性表的復(fù)制）；(8)逆轉(zhuǎn)一個線性表（即線性表的逆轉(zhuǎn)）等。44第44頁，課件共171頁，創(chuàng)作于2023年2月3.線性表在順序存儲下的插入運算45第45頁，課件共171頁，創(chuàng)作于2023年2月46第46頁，課件共171頁，創(chuàng)作于2023年2月線性表在順序存儲下的插入算法輸入：線性表的存儲空間V(1：m)；線性表的長度n（n≤m）；插入的位置i（i表示在第i個元素之前插入）；插入的新元素b。輸出：插入后的線性表存儲空間V(1：m)及線性表的長度n。

47第47頁，課件共171頁，創(chuàng)作于2023年2月PROCEDUREINSL(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.RETURN48第48頁，課件共171頁，創(chuàng)作于2023年2月voidinsl(v，m，n，i，b)ETv[]，b；intm，*n，i；

{if(*n＝＝m){printf("overflow\n")；return；}if(i＞*n－1)i＝*n＋1；

if(i＜1)i＝1；

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

v[i－1]＝b；*n＝*n＋1；

return；

}49第49頁，課件共171頁，創(chuàng)作于2023年2月4.線性表在順序存儲下的刪除運算50第50頁，課件共171頁，創(chuàng)作于2023年2月51第51頁，課件共171頁，創(chuàng)作于2023年2月線性表在順序存儲下的刪除算法輸入：線性表的存儲空間V(1：m)；線性表的長度n（n≤m）；刪除的位置i（表示刪除第i個元素）。輸出：刪除后的線性表存儲空間V(1：m)及線性表的長度n。

52第52頁，課件共171頁，創(chuàng)作于2023年2月PROCEDUREDESL(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.RETURN53第53頁，課件共171頁，創(chuàng)作于2023年2月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；

}54第54頁，課件共171頁，創(chuàng)作于2023年2月1.什么是棧棧（stack）是一種特殊的線性表。對它的操作只能是“后進先出”（LIFO），也是使用最為廣泛的數(shù)據(jù)結(jié)構(gòu)之一。因為它的運算次序受到嚴格的規(guī)定，故又稱為限定性數(shù)據(jù)結(jié)構(gòu)。為了認識棧這種數(shù)據(jù)結(jié)構(gòu)，首先介紹一個例子。2.2.2棧及其應(yīng)用55第55頁，課件共171頁，創(chuàng)作于2023年2月主程序與子程序之間的調(diào)用關(guān)系

MAINSUB1SUB2SUB3SUB4

……

……

……

……

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

……

……

……

……

……

……ENDRETURNRETURNRETURNRETURN56第56頁，課件共171頁，創(chuàng)作于2023年2月

由這個例子可以看出，在這種特殊的線性表中，其插入與刪除運算都只能在線性表的一段進行。即在這種線性表的結(jié)構(gòu)中，一端是封閉的，不允許插入和刪除元素；另一端是開口的，允許插入與刪除元素。在順序存儲結(jié)構(gòu)下，對這種類型線性表的插入與刪除運算是不需要移動表中其它數(shù)據(jù)元素的。這種線性表成為棧。57第57頁，課件共171頁，創(chuàng)作于2023年2月棧(stack)是限定在一端進行插入與刪除的線性表。棧頂:允許插入與刪除的一端.棧底:不允許插入與刪除的另一端。棧是按照“先進后出”

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

(LIFO—LastInFirstOut)的原則組織數(shù)據(jù)的，因此，棧也被稱為“先進后出”表或“后進先出”表。棧具有記憶作用。用指針top來指示棧頂?shù)奈恢?，用指針bottom指向棧底。往棧中插入一個元素稱為入棧運算，從棧中刪除一個元素(即刪除棧頂元素)稱為退棧運算。關(guān)于棧的幾個基本概念58第58頁，課件共171頁，創(chuàng)作于2023年2月59第59頁，課件共171頁，創(chuàng)作于2023年2月2.棧的順序存儲及其運算60第60頁，課件共171頁，創(chuàng)作于2023年2月top＝0表示?？眨籺op＝m表示棧滿。建立空棧的順序存儲空間（即初始化棧的順序存儲空間）

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

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

return；

}釋放棧的順序存儲空間時free(s)；61第61頁，課件共171頁，創(chuàng)作于2023年2月(1)入棧運算

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－1]＝x；

return；

}62第62頁，課件共171頁，創(chuàng)作于2023年2月(2)退棧運算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－1]；*top＝*top－1；

return；}63第63頁，課件共171頁，創(chuàng)作于2023年2月PROCEDURETOP(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－1]；

return；}64第64頁，課件共171頁，創(chuàng)作于2023年2月3.表達式的計算運算符棧，用于在表達式處理過程中存放運算符。在開始時，運算符棧中先壓入一個表達式結(jié)束符“；”。操作數(shù)棧，用于在表達式處理過程中存放操作數(shù)。65第65頁，課件共171頁，創(chuàng)作于2023年2月從左到右依次讀出表達式中的各個符號：若是操作數(shù)，則壓入操作數(shù)棧，依次讀下一個符號。若是運算符，則作進一步判斷：66第66頁，課件共171頁，創(chuàng)作于2023年2月①若讀出運算符的優(yōu)先級大于運算符棧棧頂運算符的優(yōu)先級，則將讀出的運算符壓入運算符棧，并依次讀下一個符號。②若讀出的是表達式結(jié)束符“；”，且運算符棧棧頂?shù)倪\算符也是表達式結(jié)束符“；”，則表達式處理結(jié)束，最后的計算結(jié)果在操作數(shù)棧的棧頂位置。③若讀出運算符的優(yōu)先級不大于運算符棧棧頂運算符的優(yōu)先級，則從操作數(shù)棧連續(xù)退出兩個操作數(shù)，并從運算符棧退出一個運算符，然后作相應(yīng)的運算（運算符為剛從運算符棧退出的運算符，運算對象為剛從操作數(shù)棧退出的兩個操作數(shù)），并將運算結(jié)果壓入操作數(shù)棧。67第67頁，課件共171頁，創(chuàng)作于2023年2月A＋B*C－D/E；68第68頁，課件共171頁，創(chuàng)作于2023年2月A＋B*C－D/E；69第69頁，課件共171頁，創(chuàng)作于2023年2月A＋B*C－D/E；70第70頁，課件共171頁，創(chuàng)作于2023年2月A＋B*C－D/E；71第71頁，課件共171頁，創(chuàng)作于2023年2月4.遞歸依次打印輸出自然數(shù)1到n的非遞歸算法

PROCEDUREWRT(n)FORk＝1TOnDOOUTPUTkRETURN依次打印輸出自然數(shù)1到n的遞歸算法

PROCEDUREWRT(n)IF(n≠0)THEN{WRT(n)；OUTPUTn}RETURN72第72頁，課件共171頁，創(chuàng)作于2023年2月#include"stdio.h"wrt(intn){if(n!＝0){wrt(n－1)；printf("%d\n"，n)；}return；

}73第73頁，課件共171頁，創(chuàng)作于2023年2月2.2.3隊列及其應(yīng)用1.什么是隊列隊列(equeue)是指允許在一端進行插入、而在另一端進行刪除的線性表。數(shù)據(jù)結(jié)構(gòu)中的隊列與生活中的“排隊”極為相似，也是按“先來先解決”的原則行事的，并且既不允許“加塞”，也不允許“中途離隊”。74第74頁，課件共171頁，創(chuàng)作于2023年2月關(guān)于隊列的幾個基本概念允許插入的一端稱為隊尾，用尾指針(rear)指向隊尾元素。允許刪除的一端稱為排頭(也稱隊頭)，用排頭指針(front)指向排頭元素的前一個位置。隊列又稱為“先進先出”

(FIFO—FirstInFirst

Out)或“后進后出”

(LILO—LastInLastOut)的線性表，體現(xiàn)了“先來先服務(wù)”的原則。往隊列的隊尾插入一個元素稱為入隊運算，從隊列的排頭刪除一個元素稱為退隊運算。75第75頁，課件共171頁，創(chuàng)作于2023年2月76第76頁，課件共171頁，創(chuàng)作于2023年2月2.循環(huán)隊列及其運算77第77頁，課件共171頁，創(chuàng)作于2023年2月78第78頁，課件共171頁，創(chuàng)作于2023年2月隊列空的條件為s＝0隊列滿的條件為(s＝1)且front＝rear79第79頁，課件共171頁，創(chuàng)作于2023年2月建立循環(huán)隊列順序存儲空間（即初始化循環(huán)隊列順序存儲空間）#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)隊列的順序存儲空間free(q)；80第80頁，課件共171頁，創(chuàng)作于2023年2月(1)入隊運算PROCEDUREADDCQ(Q，m，rear，front，s，x)1.IF(s＝1)and(rear＝front)THEN{Queue－OVERFLOW；RETURN}2.rear＝rear＋13.IF(rear＝m＋1)THENrear＝14.Q(rear)＝x5.s＝16.RETURN81第81頁，課件共171頁，創(chuàng)作于2023年2月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－1]＝x；*s＝1；return；}82第82頁，課件共171頁，創(chuàng)作于2023年2月(2)退隊運算PROCEDUREDELCQ(Q，m，rear，front，s，y)1.IF(s＝0)THEN{Queue－UNDERFLOW；RETURN}2.front＝front＋13.IF(front＝m＋1)THENfront＝14.y＝Q(front)5.IF(front＝rear)THENs＝06.RETURN83第83頁，課件共171頁，創(chuàng)作于2023年2月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－1]；

if(*front＝＝*rear)*s＝0；

return；}84第84頁，課件共171頁，創(chuàng)作于2023年2月3.隊列的應(yīng)用

(1)給工人分配工作的模擬開辟一個隊列結(jié)構(gòu)的線性表。設(shè)置一個排頭指針和一個隊尾指針。初始時隊列為空。每當(dāng)有一個工人到調(diào)度員處報到時（包括新來的與完成任務(wù)后返回的），都將他加入到隊尾；當(dāng)需要一名工人去做某項工作時，就排頭的工人去做該項工作。85第85頁，課件共171頁，創(chuàng)作于2023年2月(2)輸入輸出緩沖區(qū)的結(jié)構(gòu)86第86頁，課件共171頁，創(chuàng)作于2023年2月2.3線性鏈表及其運算2.3.1線性鏈表的基本概念2.3.2線性鏈表的基本運算2.3.3循環(huán)鏈表87第87頁，課件共171頁，創(chuàng)作于2023年2月2.3.1線性鏈表的基本概念1.線性鏈表線性表的鏈式存儲結(jié)構(gòu)稱為線性鏈表。88第88頁，課件共171頁，創(chuàng)作于2023年2月89第89頁，課件共171頁，創(chuàng)作于2023年2月90第90頁，課件共171頁，創(chuàng)作于2023年2月91第91頁，課件共171頁，創(chuàng)作于2023年2月92第92頁，課件共171頁，創(chuàng)作于2023年2月依次輸出線性鏈表中的各結(jié)點值輸入：線性鏈表的存儲空間V(1：m)、NEXT(1：m)；線性鏈表的頭指針HEAD。輸出：依次輸出線性鏈表中各結(jié)點的值。

PROCEDUREPRTLL(HEAD)j＝HEADWHILE(j≠0)DO{OUTPUTV(j)；j＝NEXT(j)}RETURN93第93頁，課件共171頁，創(chuàng)作于2023年2月struct結(jié)構(gòu)體名

{數(shù)據(jù)成員表；

struct結(jié)構(gòu)體名*指針變量名；

}例如

structnode{charname[10]；/*數(shù)據(jù)域*/charsex；/*數(shù)據(jù)域*/structnode*next；/*指針域*/}94第94頁，課件共171頁，創(chuàng)作于2023年2月#include"stdlib.h"/*malloc函數(shù)需要包含頭文件stdlib.h*/structnode/*定義結(jié)點類型*/{intd；/*數(shù)據(jù)域*/structnode*next；/*指針域*/}main(){structnode*p；/*定義該類型的指針變量p*/

…p=(structnode*)malloc(sizeof(structnode))；

/*申請分配結(jié)點存儲空間*/

…free(p)；/*釋放結(jié)點存儲空間*/}95第95頁，課件共171頁，創(chuàng)作于2023年2月#include"stdlib.h"#include"stdio.h"structnode/*定義結(jié)點類型*/{intd；

structnode*next；

}main(){intx；

structnode*head，*p，*q；

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

scanf(“%d”，&x)；/*輸入一個正整數(shù)*/96第96頁，課件共171頁，創(chuàng)作于2023年2月while(x＞0)/*若輸入值大于0*/{p＝(structnode*)malloc(sizeof(structnode))；/*申請一個結(jié)點*/p－>d＝x；p－>next＝NULL；/*置當(dāng)前結(jié)點的數(shù)據(jù)域和指針域*/if(head＝＝NULL)head＝p；/*若鏈表空，則將頭指針指向當(dāng)前結(jié)點p*/elseq－>next＝p；/*將當(dāng)前結(jié)點鏈接在最后*/q＝p；/*置當(dāng)前結(jié)點為鏈表最后一個結(jié)點*/scanf("%d"，&x)；

}p＝head；

while(p!＝NULL)/*從鏈表第一個結(jié)點開始打印各結(jié)點元素值，并刪除*/{printf("%5d"，p－>d)；/*打印當(dāng)前結(jié)點中的數(shù)據(jù)*/q＝p；p＝p－>next；free(q)；/*刪除當(dāng)前結(jié)點并釋放該結(jié)點空間*/}printf("\n")；}97第97頁，課件共171頁，創(chuàng)作于2023年2月雙向鏈表98第98頁，課件共171頁，創(chuàng)作于2023年2月2.帶鏈的棧99第99頁，課件共171頁，創(chuàng)作于2023年2月可利用棧及其運算100第100頁，課件共171頁，創(chuàng)作于2023年2月將結(jié)點送回可利用棧輸入：可利用棧棧頂指針TOP（默認）；送回可利用棧的結(jié)點序號p。輸出：結(jié)點p入棧后的可利用棧棧頂指針TOP（默認）。

PROCEDUREDISPOSE(p)NEXT(p)＝TOP；TOP＝pRETURN從可利用棧取得一個結(jié)點輸入：可利用棧的棧頂指針TOP（默認）。輸出：退棧后的可利用棧棧頂指針TOP（默認）；存放取得結(jié)點序號的變量p。

PROCEDURENEW(p)p＝TOP；TOP＝NEXT(TOP)RETURN101第101頁，課件共171頁，創(chuàng)作于2023年2月帶鏈棧的入棧運算輸入：帶鏈棧的棧頂指針top；入棧的元素值x。輸出：元素x入棧后的帶鏈棧棧頂指針top。

PROCEDUREPUSHLL(top，x)NEW(p)[從可利用棧取得一個新結(jié)點]V(p)＝x[置新結(jié)點數(shù)據(jù)域]NEXT(p)＝top[置新結(jié)點指針域]top＝p[改變棧頂指針]RETURN102第102頁，課件共171頁，創(chuàng)作于2023年2月#include"stdlib.h"structnode/*定義結(jié)點類型*/{ETd；/*數(shù)據(jù)元素類型*/structnode*next；

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

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

p－>d＝x；p－>next＝*top；/*置新結(jié)點的數(shù)據(jù)域與指針域*/*top＝p；/*改變棧頂指針*/return；}103第103頁，課件共171頁，創(chuàng)作于2023年2月帶鏈棧的退棧運算輸入：帶鏈棧的棧頂指針top。輸出：退棧后的帶鏈棧棧頂指針top；存放退出結(jié)點元素值的變量y。

PROCEDUREPOPLL(top，y)y＝V(top)[取出棧頂元素值]

p＝toptop=NEXT(p)[改變棧頂指針]DISPOSE(p)[被刪除結(jié)點送回可利用棧]RETURN104第104頁，課件共171頁，創(chuàng)作于2023年2月#include"stdlib.h"structnode/*定義結(jié)點類型*/{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é)點后返回*/}105第105頁，課件共171頁，創(chuàng)作于2023年2月3.帶鏈的隊列106第106頁，課件共171頁，創(chuàng)作于2023年2月帶鏈隊列的入隊運算輸入：帶鏈隊列的隊尾指針rear；入隊的新元素x。輸出：元素x入隊后的帶鏈隊列隊尾指針rear。

PROCEDUREADDLL(rear，x)NEW(p)[從可利用棧取得一個新結(jié)點p]V(p)＝x[置新結(jié)點的數(shù)據(jù)域]NEXT(p)＝0[置新結(jié)點的指針為空]NEXT(rear)＝p[最后一個結(jié)點的指針指向新結(jié)點]rear＝p[改變隊尾指針]RETURN107第107頁，課件共171頁，創(chuàng)作于2023年2月#include"stdlib.h"structnode/*定義結(jié)點類型*/{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é)點的數(shù)據(jù)域與指針域*/*rear－>next＝p；/*置最后一個結(jié)點的指針指向新結(jié)點*/*rear＝p；/*改變隊尾指針*/return；}108第108頁，課件共171頁，創(chuàng)作于2023年2月帶鏈隊列的退隊運算輸入：帶鏈隊列的排頭指針front。輸出：退隊后的帶鏈隊列排頭指針front；存放退出結(jié)點值的變量y。

PROCEDUREDELLL(front，y)y=V(front)[取出排頭元素值]p＝frontfront＝NEXT(front)[改變排頭指針]DISPOSE(p)[釋放刪除的結(jié)點]RETURN109第109頁，課件共171頁，創(chuàng)作于2023年2月#include"stdlib.h"structnode/*定義結(jié)點類型*/{ETd；/*數(shù)據(jù)元素類型*/structnode*next；

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

y＝*front－>d；/*取出排頭元素值*/p＝*front；*front＝p－>next；/*改變排頭指針*/free(p)；/*釋放被刪除結(jié)點*/return；}110第110頁，課件共171頁，創(chuàng)作于2023年2月2.3.2線性鏈表的基本運算(1)在線性鏈表中包含指定元素的結(jié)點之前插入一個新元素。(2)在線性鏈表中刪除包含指定元素的結(jié)點。(3)將兩個線性鏈表按要求合并成一個線性鏈表。(4)將一個線性鏈表按要求進行分解。(5)逆轉(zhuǎn)線性鏈表。(6)復(fù)制線性鏈表。(7)線性鏈表的排序。(8)線性鏈表的查找。111第111頁，課件共171頁，創(chuàng)作于2023年2月1.在線性鏈表中查找指定元素在非空線性鏈表中尋找包含元素x的前一個結(jié)點p輸入：非空線性鏈表頭指針HEAD；被尋找元素x。輸出：非空線性鏈表中包含元素x的前一個結(jié)點p。PROCEDURELOOKST(HEAD，x，p)p＝HEADWHILE(NEXT(p)≠0)and(V(NEXT(p))≠x)DOp＝NEXT(p)RETURN112第112頁，課件共171頁，創(chuàng)作于2023年2月structnode/*定義結(jié)點類型*/{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)；}113第113頁，課件共171頁，創(chuàng)作于2023年2月2.線性鏈表的插入在鏈式存儲結(jié)構(gòu)下的線性表中插入一個新元素。114第114頁，課件共171頁，創(chuàng)作于2023年2月可利用棧與線性鏈表115第115頁，課件共171頁，創(chuàng)作于2023年2月(1)從可利用棧取得一個結(jié)點，設(shè)該結(jié)點號為p。并置結(jié)點p的數(shù)據(jù)域為插入的元素值b，即V(p)＝b。(2)在線性鏈表中尋找包含元素x的前一個結(jié)點q。116第116頁，課件共171頁，創(chuàng)作于2023年2月(3)將結(jié)點p插入到結(jié)點q之后：①使結(jié)點p指向包含元素x的結(jié)點，即

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

NEXT(q)＝p117第117頁，課件共171頁，創(chuàng)作于2023年2月線性鏈表的插入輸入：線性鏈表的頭指針HEAD；插入位置處的前一個結(jié)點值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.RETURN118第118頁，課件共171頁，創(chuàng)作于2023年2月#include"stdlib.h"structnode/*定義結(jié)點類型*/{ETd；structnode*next；}；inslst(head，x，b)ETx，b；structnode**head；{structnode*p，*q；

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

p－>d＝b；/*置結(jié)點的數(shù)據(jù)域*/if(*head＝＝NULL)/*鏈表為空*/{*head＝p；p－>next＝NULL；return；}if((*head－>d)＝＝x)/*在第一個結(jié)點前插入*/{p－>next＝*head；*head＝p；return；}q＝lookst(*head，x)；/*尋找包含元素x的前一個結(jié)點q*/p－>next＝q－>next；q－>next＝p；/*結(jié)點p插到結(jié)點q之后*/return；}119第119頁，課件共171頁，創(chuàng)作于2023年2月3.線性鏈表的刪除在鏈式存儲結(jié)構(gòu)下的線性表中刪除包含指定元素的結(jié)點。120第120頁，課件共171頁，創(chuàng)作于2023年2月可利用棧與線性鏈表121第121頁，課件共171頁，創(chuàng)作于2023年2月(1)尋找包含元素x的前一個結(jié)點q。則包含元素x的結(jié)點序號p＝NEXT(q)。(2)將結(jié)點q后的結(jié)點p刪除，即

NEXT(q)＝NEXT(p)。122第122頁，課件共171頁，創(chuàng)作于2023年2月(3)將包含元素x的結(jié)點p送回可利用棧。123第123頁，課件共171頁，創(chuàng)作于2023年2月線性鏈表的刪除輸入：線性鏈表的頭指針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.RETURN124第124頁，課件共171頁，創(chuàng)作于2023年2月#include"stdlib.h"structnode/*定義結(jié)點類型*/{ETd；structnode*next；}；delst(head，x)ETx；structnode**head；{structnode*p，*q；

if(*head＝＝NULL)/*鏈表為空*/{printf("Thisisaemptylist!\n")；return；}if((*head－>d)＝＝x)/*刪除第一個結(jié)點*/{p＝*head－>next；free(*head)；*head＝p；return；}q＝lookst(*head，x)；/*尋找包含元素x的前一個結(jié)點q*/if(q－>next＝＝NULL)/*鏈表中沒有包含元素x的結(jié)點*/{printf("Nothisnodeinthelist!\n")；return；}p＝q－>next；q－>next＝p－>next；/*刪除結(jié)點p*/free(p)；/*釋放結(jié)點p*/return；}125第125頁，課件共171頁，創(chuàng)作于2023年2月2.3.3循環(huán)鏈表(1)在循環(huán)鏈表中增加了一個表頭結(jié)點，其數(shù)據(jù)域為任意或根據(jù)需要來設(shè)置，指針域指向線性表第一個元素的結(jié)點。循環(huán)鏈表的頭指針指向表頭結(jié)點。(2)循環(huán)鏈表中最后一個結(jié)點的指針域不空，而是指向表頭結(jié)點。即在循環(huán)鏈表中，所有結(jié)點的指針構(gòu)成了一個環(huán)狀鏈。126第126頁，課件共171頁，創(chuàng)作于2023年2月(1)在循環(huán)鏈表中，只要指出表中任何一個結(jié)點的位置，就可以從它出發(fā)訪問到表中其他所有的結(jié)點。(2)空表與非空表的運算統(tǒng)一。127第127頁，課件共171頁，創(chuàng)作于2023年2月在頭指針為HEAD的循環(huán)鏈表中尋找包含元素x的前一個結(jié)點輸入：循環(huán)鏈表的頭指針HEAD；被尋找的元素x。輸出：循環(huán)鏈表中包含元素x的前一個結(jié)點p。PROCEDURELOOKCST(HEAD，x，p)p＝HEADWHILE(NEXT(p)≠HEAD)and(V(NEXT(p))≠x)DOp＝NEXT(p)RETURN128第128頁，課件共171頁，創(chuàng)作于2023年2月#include"stdlib.h"structnode/*定義結(jié)點類型*/{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)；}129第129頁，課件共171頁，創(chuàng)作于2023年2月在頭指針為HEAD的循環(huán)鏈表中包含元素x的結(jié)點前插入新元素b輸入：循環(huán)鏈表的頭指針HEAD；插入位置處的前一個結(jié)點值x；插入的新元素b。輸出：插入后的循環(huán)鏈表。PROCEDUREINSCST(HEAD，x，b)NEW(p)[從可利用棧取得一個新結(jié)點p]V(p)＝b[置新結(jié)點p的數(shù)據(jù)域（插入的元素值b）]LOOKCST(HEAD，x，q)[尋找循環(huán)鏈表中包含元素x的前一個結(jié)點q]NEXT(p)＝NEXT(q)；NEXT(q)＝p[將新結(jié)點p插入到結(jié)點q之后]RETURN130第130頁，課件共171頁，創(chuàng)作于2023年2月#include"stdlib.h"structnode/*定義結(jié)點類型*/{ETd；structnode*next；}；inscst(head，x，b)ETx，b；structnode*head；{structnode*p，*q；

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

p－>d＝b；/*置結(jié)點的數(shù)據(jù)域*/q＝lookcst(head，x)；/*尋找包含元素x的前一個結(jié)點q*/p－>next＝q－>next；q－>next＝p；/*結(jié)點p插入到結(jié)點q后*/return；}131第131頁，課件共171頁，創(chuàng)作于2023年2月在頭指針為HEAD的循環(huán)鏈表中刪除包含元素x的結(jié)點輸入：循環(huán)鏈表的頭指針HEAD；需刪除的元素x。輸出：刪除后的循環(huán)鏈表。PROCEDUREDELCST(HEAD，x)LOOKCST(HEAD，x，q)[尋找包含元素x的前一個結(jié)點q]IF(NEXT(q)＝HEAD)THEN[循環(huán)鏈表中沒有該結(jié)點]{“Nothisnodeinthelist!”；RETURN}p＝NEXT(q)；NEXT(q)＝NEXT(p)[刪除結(jié)點q后的結(jié)點]DISPOSE(p)[將被刪除的結(jié)點p送回可利用棧]RETURN132第132頁，課件共171頁，創(chuàng)作于2023年2月#include"stdlib.h"structnode/*定義結(jié)點類型*/{ETd；structnode*next；}；delcst(head，x)ETx；structnode*head；{structnode*p，*q；

q＝lookcst(head，x)；/*尋找包含元素x的前一個結(jié)點q*/if(q－>next＝＝NULL)/*鏈表中沒有包含元素x的結(jié)點*/{printf("Nothisnodeinthelist!\n")；return；}p＝q－>next；q－>next＝p－>next；/*刪除結(jié)點p*/free(p)；/*釋放結(jié)點p*/return；}133第133頁，課件共171頁，創(chuàng)作于2023年2月2.4樹與二叉樹2.4.1樹的基本概念2.4.2二叉樹及其基本性質(zhì)2.4.3二叉樹的存儲結(jié)構(gòu)2.4.4二叉樹的遍歷134第134頁，課件共171頁，創(chuàng)作于2023年2月2.4.1樹的基本概念135第135頁，課件共171頁，創(chuàng)作于2023年2月

用圖形表示樹這種數(shù)據(jù)結(jié)構(gòu)時，很像自然界中的樹。只不過是一顆倒置的樹。因此將這種數(shù)據(jù)結(jié)構(gòu)用“樹”來命名。在樹的圖形中總是認為在用直線連接起來的兩端結(jié)點中，上端結(jié)點是前件下端結(jié)點是后件，所以省略了箭頭。2.4.1樹的基本概念136第136頁，課件共171頁，創(chuàng)作于2023年2月

在現(xiàn)實世界中，能用樹這種數(shù)據(jù)結(jié)構(gòu)表示的例子很多！2.4.1樹的基本概念137第137頁，課件共171頁，創(chuàng)作于2023年2月2.4.1樹的基本概念138第138頁，課件共171頁，創(chuàng)作于2023年2月2.4.1樹的基本概念139第139頁，課件共171頁，創(chuàng)作于2023年2月

樹是n(n≥0)個結(jié)點的有限集。在任意一棵非空樹中：①有且僅有一個特定的稱為根(Root)的結(jié)點。②當(dāng)n＞1時，其余結(jié)點可分為m(m＞0)個互不相交的有限集T1,T2，…，Tm，其中每一集合本身又是一棵樹，并且稱為根的子樹。2.4.1樹的基本概念樹的概念140第140頁，課件共171頁，創(chuàng)作于2023年2月樹中的幾個基本術(shù)語父結(jié)點：在樹中，每一個結(jié)點只有一個前件稱為父結(jié)點。根：在樹中，沒有前件的結(jié)點只有一個，成為樹的根結(jié)點。簡稱根。子結(jié)點：在樹中，每一個結(jié)點可以有多個后件，稱為該結(jié)點的子結(jié)點。沒有后件的結(jié)點稱為葉子結(jié)點。2.4.1樹的基本概念141第141頁，課件共171頁，創(chuàng)作于2023年2月度：在樹中，一個結(jié)點所擁有的后件個數(shù)稱為該結(jié)點的度。樹的度：在樹中，所有結(jié)點中的最大度。樹的深度：樹的最大層次。子樹：在樹中，以某結(jié)點的一個子結(jié)點為根構(gòu)成的樹。2.4.1樹的基本概念142第142頁，課件共171頁，創(chuàng)作于2023年2月樹型結(jié)構(gòu)是一種非常重要的非線性結(jié)構(gòu)。樹是以分支關(guān)系定義的層次結(jié)構(gòu)。一般按以下原則分層：（1）根結(jié)點在第1層（2）同一層上所有結(jié)點的所有子結(jié)點在下一層2.4.1樹的基本概念143第143頁，課件共171頁，創(chuàng)作于2023年2月在計算機中，可以用樹表示算術(shù)表達式。原則如下：（1）表達式中的每一個運算符在樹中對應(yīng)一個結(jié)點，稱為運算符結(jié)點。（2）運算符的每一個運算對象在樹中為該運算符結(jié)點的子樹（在樹中的順序為從左到右）。（3）運算對象中的單變量均為葉子結(jié)點2.4.1樹的基本概念144第144頁，課件共171頁，創(chuàng)作于2023年2月a*(b＋c/d)＋e*h－g*f(s，t，x＋y)表達式樹一145第145頁，課件共171頁，創(chuàng)作于2023年2月a*(b＋c/d)＋e*h－g*f(s，t，x＋y)表達式樹二146第146頁，課件共171頁，創(chuàng)作于2023年2月樹鏈表中的結(jié)點結(jié)構(gòu)147第147頁，課件共171頁，創(chuàng)作于2023年2月1.什么是二叉樹（binarytree）

(1)非空二叉樹只有一個根結(jié)點；

(2)每一個結(jié)點最多有兩棵子樹，且分別稱為該結(jié)點的左子樹與右子樹。2.4.2二叉樹及其基本性質(zhì)148第148頁，課件共171頁，創(chuàng)作于2023年2月2.二叉樹的基本性質(zhì)性質(zhì)1在二叉樹的第k層上，最多有2k－1(k≥1)個結(jié)點。性質(zhì)2深度為m的二叉樹最多有2m－1個結(jié)點。性質(zhì)3在任意一棵二叉樹中，度為0的結(jié)點即葉子結(jié)點總是比度為2的結(jié)點多一個。性質(zhì)4具有n個結(jié)點的二叉樹，其深度至少為

[log2n]＋1

其中[log2n]表示取log2n的整數(shù)部分。149第149頁，課件共171頁，創(chuàng)作于2023年2月3.滿二叉樹與完全二叉樹(1)滿二叉樹150第150頁，課件共171頁，創(chuàng)作于2023年2月滿二叉樹是這樣一種二叉樹：除最后一層外，每一層上