數(shù)據(jù)結(jié)構(gòu)詳解

基本數(shù)據(jù)結(jié)構(gòu)與算法交流數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第1頁(yè)。CONTENTS緒論1線性表2棧與隊(duì)列3串4樹(shù)5圖6排序算法7數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第2頁(yè)。1緒論什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的基本概念抽象數(shù)據(jù)類型基本概念算法效率的度量數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第3頁(yè)。什么是數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計(jì)算機(jī)硬件和計(jì)算機(jī)軟件三者之間的一門(mén)核心課程關(guān)系對(duì)象關(guān)系操作數(shù)學(xué)軟件硬件對(duì)象關(guān)系操作數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第4頁(yè)。為什么學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)

程序設(shè)計(jì)的實(shí)質(zhì)是對(duì)實(shí)際問(wèn)題選擇一種好的數(shù)據(jù)結(jié)構(gòu)，加之設(shè)計(jì)一個(gè)好的算法，而好的算法在很大程度上取決于描述實(shí)際問(wèn)題的數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第5頁(yè)。

算法+數(shù)據(jù)結(jié)構(gòu)=程序6數(shù)據(jù)結(jié)構(gòu)的重要性：結(jié)構(gòu)化編程（代表語(yǔ)言TurboC）：程序=（算法）+（數(shù)據(jù)結(jié)構(gòu)）面向?qū)ο缶幊?代表語(yǔ)言Java、Delphi、c++)：對(duì)象=（算法+數(shù)據(jù)結(jié)構(gòu)）

程序=對(duì)象+對(duì)象程序設(shè)計(jì):為計(jì)算機(jī)處理問(wèn)題編制一組指令集算法:處理問(wèn)題的策略數(shù)據(jù)結(jié)構(gòu)：?jiǎn)栴}的數(shù)學(xué)模型數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第6頁(yè)。登錄號(hào)：書(shū)名：作者名：分類號(hào)：出版單位：出版時(shí)間：價(jià)格：書(shū)目卡片按書(shū)名按作者名按分類號(hào)數(shù)據(jù)結(jié)構(gòu)實(shí)際應(yīng)用——索引索引數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第7頁(yè)。8樹(shù)……..……..…...…...…...…...數(shù)據(jù)結(jié)構(gòu)實(shí)際應(yīng)用——人機(jī)對(duì)弈數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第8頁(yè)。FBDDAE54798612282數(shù)據(jù)結(jié)構(gòu)實(shí)際應(yīng)用——最短路徑圖C數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第9頁(yè)。數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第10頁(yè)。數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第11頁(yè)。數(shù)據(jù)結(jié)構(gòu)實(shí)際應(yīng)用——HashMap數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第12頁(yè)。數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第13頁(yè)。抽象數(shù)據(jù)類型基本概念數(shù)據(jù)(data)——所有能被計(jì)算機(jī)識(shí)別、存儲(chǔ)和處理的符號(hào)的集合（包括數(shù)字、字符、聲音、圖像等信息）。數(shù)據(jù)元素(dataelement)——是數(shù)據(jù)的基本單位，具有完整確定的實(shí)際意義(又稱元素、結(jié)點(diǎn)，頂點(diǎn)、記錄等）。數(shù)據(jù)項(xiàng)(Dataitem)——構(gòu)成數(shù)據(jù)元素的項(xiàng)目。是具有獨(dú)立含義的最小標(biāo)識(shí)單位（又稱字段、域、屬性等）。數(shù)據(jù)對(duì)象（Dataobject）——是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集（如整數(shù)數(shù)據(jù)，字母數(shù)據(jù)等）。三者之間的關(guān)系：數(shù)據(jù)>數(shù)據(jù)元素>數(shù)據(jù)項(xiàng)例：班級(jí)通訊錄>個(gè)人記錄>姓名、年齡……數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第14頁(yè)。數(shù)據(jù)結(jié)構(gòu)涵蓋的內(nèi)容數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第15頁(yè)。算法效率的度量Q1.什么是算法？算法的設(shè)計(jì)原則？Q2.算法效率的衡量方法與準(zhǔn)則？Q3.算法的存儲(chǔ)空間需求？問(wèn)題：數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第16頁(yè)。程序設(shè)計(jì)實(shí)質(zhì)＝好算法＋好結(jié)構(gòu)答：算法是解決某一特定類型問(wèn)題的有限運(yùn)算序列。是一系列輸入轉(zhuǎn)換為輸出的計(jì)算步驟。常用時(shí)間復(fù)雜度來(lái)衡量Q1.什么是算法？如何評(píng)判一個(gè)算法的好壞？算法有5個(gè)基本特性：算法評(píng)價(jià)有4個(gè)指標(biāo)：有窮性、確定性、可行性、輸入和輸出運(yùn)行時(shí)間、占用空間、正確性和簡(jiǎn)單性常用空間復(fù)雜度來(lái)衡量數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第17頁(yè)。Q2算法效率的衡量方法和準(zhǔn)則通常有兩種衡量算法效率的方法:1.事后統(tǒng)計(jì)法缺點(diǎn)：1．必須執(zhí)行程序

2．其它因素掩蓋算法本質(zhì)（如計(jì)算機(jī)的硬件、軟件等環(huán)境因素，有時(shí)掩蓋算法本身優(yōu)劣）數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第18頁(yè)。2.事前分析估算法（1）算法選用的策略（2）數(shù)據(jù)的規(guī)模（3）編寫(xiě)程序的語(yǔ)言（4）編譯程序產(chǎn)生的機(jī)器代碼的質(zhì)量（5）計(jì)算機(jī)執(zhí)行指令的速度算法執(zhí)行時(shí)間相關(guān)的因素：數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第19頁(yè)。時(shí)間復(fù)雜度的計(jì)算O(1)O(n)O(n2)intsum=0,n=100; /*執(zhí)行一次*/sum=(1+n)*n/2; /*執(zhí)行一次*/Printf(“%d”,sum); /*執(zhí)行一次*/intsum=0,n=100; /*執(zhí)行一次*/for(i=1;i<=n;i++){ /*執(zhí)行n+1次*/sum=sum+I; /*執(zhí)行n次*/}printf(“%d”,sum); /*執(zhí)行1次*/intsum=0,n=100; /*執(zhí)行一次*/for(i=1;i<=n;i++){ /*執(zhí)行n+1次*/for(j=1;j<=n;j++){x++; /*執(zhí)行n2次*/sum=sum+x;}}printf(“%d”,sum); /*執(zhí)行1次*/數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第20頁(yè)。時(shí)間復(fù)雜度的計(jì)算推導(dǎo)大O階：1.用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)2.在修改后的運(yùn)行次數(shù)函數(shù)中，只保留最高階項(xiàng)3.如果最高階項(xiàng)存在且不是1，則去除與這個(gè)項(xiàng)目相乘的常數(shù)。得到的結(jié)果就是大O階數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第21頁(yè)。2線性表2.1線性表的邏輯結(jié)構(gòu)2.2線性表的順序存儲(chǔ)結(jié)構(gòu)2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第22頁(yè)。（a1,a2,…ai-1，ai,ai＋1

，…,an）2.1

線性表的類型定義1.線性表的定義：零或多個(gè)數(shù)據(jù)元素的有限序列n=0時(shí)稱為數(shù)據(jù)元素線性起點(diǎn)ai的直接前趨ai的直接后繼下標(biāo)，是元素的序號(hào)，表示元素在表中的位置n為元素總個(gè)數(shù)，即表長(zhǎng)空表線性終點(diǎn)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第23頁(yè)。線性結(jié)構(gòu)的基本特征:3.除最后元素在外，均有唯一的后繼；4.除第一元素之外，均有唯一的前驅(qū)。在數(shù)據(jù)元素的非空有限集中線性表是一種最簡(jiǎn)單的線性結(jié)構(gòu)

1.集合中必存在唯一的一個(gè)“第一元素”；2.集合中必存在唯一的一個(gè)“最后元素”

；數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第24頁(yè)。例1分析26個(gè)英文字母組成的英文表

（A,B,C,D,……,Z）姓name性別年齡班級(jí)011810205于春梅女18電信016班011810260何仕鵬男18電信017班011810284王爽女18通信011班011810360王亞武男18通信012班：：：

：：例2分析學(xué)生情況登記表數(shù)據(jù)元素都是記錄;元素間關(guān)系是線性數(shù)據(jù)元素都是字母;元素間關(guān)系是線性同一線性表中的元素必定具有相同特性數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第25頁(yè)。2.線性表的類型定義數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第26頁(yè)。2.2線性表的順序存儲(chǔ)結(jié)構(gòu)2.2.1順序表的表示2.2.2順序表的實(shí)現(xiàn)2.2.3順序表的運(yùn)算效率分析數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第27頁(yè)。2.2.1順序表的表示指的是用一段地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素順序存儲(chǔ)定義：順序存儲(chǔ)示意圖：可用數(shù)組來(lái)實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第28頁(yè)。線性表順序存儲(chǔ)特點(diǎn)：1.

邏輯上相鄰的數(shù)據(jù)元素，其物理上也相鄰；2.

若已知表中首元素在存儲(chǔ)器中的位置，則其他元素存放位置亦可求出設(shè)首元素a1的存放地址為L(zhǎng)OC(a1)（稱為首地址），設(shè)每個(gè)元素占用存儲(chǔ)空間（地址長(zhǎng)度）為C字節(jié)，則表中任一數(shù)據(jù)元素的存放地址為： LOC(ai+1)=LOC(ai)+C

LOC(ai)=LOC(a1)+C*（i-1）

數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第29頁(yè)。2.2.2順序表基本操作修改、插入、刪除、查找、排序1)修改通過(guò)數(shù)組的下標(biāo)便可訪問(wèn)某個(gè)特定元素并修改。核心語(yǔ)句:

V[i]=x;顯然，順序表修改操作的時(shí)間效率是T(n)=O(1)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第30頁(yè)。2)插入在線性表的第i個(gè)位置前插入一個(gè)元素實(shí)現(xiàn)步驟：(n為表長(zhǎng)）將第n至第i位的元素向后移動(dòng)一個(gè)位置；將要插入的元素寫(xiě)到第i個(gè)位置；表長(zhǎng)加1。數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第31頁(yè)。實(shí)現(xiàn)步驟：(n為表長(zhǎng)）將第i至第n位的元素向前移動(dòng)一個(gè)位置；表長(zhǎng)減1。3)刪除刪除線性表的第i個(gè)位置上的元素?cái)?shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第32頁(yè)。2.2.3順序表的運(yùn)算效率分析最好情況：插入在最后一個(gè)位置，O(1)最壞情況：插入在第一個(gè)位置，O(n)平均情況：平均移動(dòng)n/2時(shí)間復(fù)雜度為O(n)插入時(shí)間效率分析:數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第33頁(yè)。2.2.3順序表的優(yōu)缺點(diǎn)優(yōu)點(diǎn)無(wú)須為表示表中元素之間的邏輯關(guān)系而增加額外的存儲(chǔ)空間可以快速地存取表中任一位置的元素缺點(diǎn)插入和刪除操作需要移動(dòng)大量元素當(dāng)線性表長(zhǎng)度變化較大時(shí)，難以確定存儲(chǔ)空間的容量造成存儲(chǔ)空間的“碎片”數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第34頁(yè)。2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2.3.1鏈表的表示2.3.2鏈表的實(shí)現(xiàn){單鏈表，循環(huán)鏈表，雙向鏈表}數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第35頁(yè)。特點(diǎn)：邏輯上相鄰，物理上不一定相鄰鏈表中第一個(gè)結(jié)點(diǎn)的存儲(chǔ)位置叫頭指針每個(gè)存儲(chǔ)結(jié)點(diǎn)都包含兩部分：數(shù)據(jù)域和指針域(鏈域)線性鏈表的最后一個(gè)結(jié)點(diǎn)指針為空，通常用NULL或^表示2.3.1鏈表的表示存儲(chǔ)結(jié)構(gòu)：如下圖示意數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第36頁(yè)。有時(shí)為了方便操作，會(huì)在單鏈表的第一個(gè)結(jié)點(diǎn)前附設(shè)一個(gè)結(jié)點(diǎn)，叫做頭結(jié)點(diǎn)頭結(jié)點(diǎn)數(shù)據(jù)域可不存儲(chǔ)任何信息，也可存儲(chǔ)線性表長(zhǎng)度等附加信息數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第37頁(yè)。2.3.2鏈表的實(shí)現(xiàn)1.單鏈表2.循環(huán)鏈表3.雙向鏈表數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第38頁(yè)。1.單鏈表空鏈表：讀取或修改：數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第39頁(yè)。1.單鏈表插入：數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第40頁(yè)。1.單鏈表刪除：數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第41頁(yè)。1.單鏈表單鏈表和順序存儲(chǔ)結(jié)構(gòu)對(duì)比數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第42頁(yè)。2.循環(huán)鏈表將單鏈表中斷結(jié)點(diǎn)的指針端由空指針改為指向頭結(jié)點(diǎn)，就使整個(gè)單鏈表形成一個(gè)環(huán)，這種頭尾相接的單鏈表稱為單循環(huán)鏈表，簡(jiǎn)稱循環(huán)鏈表空循環(huán)鏈表：添加、刪除操作與單鏈表對(duì)應(yīng)操作相同數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第43頁(yè)。3.雙向鏈表單鏈表的每個(gè)結(jié)點(diǎn)中，再設(shè)置一個(gè)指向其前驅(qū)結(jié)點(diǎn)的指針域，這樣的鏈表簡(jiǎn)稱循環(huán)鏈表空雙向鏈表：數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第44頁(yè)。3.雙向鏈表插入：刪除：數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第45頁(yè)。3.1棧（Stack）3.2隊(duì)列（Queue）

3棧和隊(duì)列1.基本介紹2.抽象數(shù)據(jù)類型3.順序存儲(chǔ)結(jié)構(gòu)4.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)1.基本介紹2.抽象數(shù)據(jù)類型3.順序存儲(chǔ)結(jié)構(gòu)4.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第46頁(yè)。3.1棧（Stack）1.基本介紹2.抽象數(shù)據(jù)類型3.順序存儲(chǔ)結(jié)構(gòu)4.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第47頁(yè)。例如：棧S=(a1,a2,a3,……….,an-1,an

)插入元素到棧頂?shù)牟僮?，稱為入棧。從棧頂刪除最后一個(gè)元素的操作，稱為出棧。an稱為棧頂元素a1稱為棧底元素強(qiáng)調(diào)：插入和刪除都只能在表的一端（棧頂）進(jìn)行！棧是僅在表尾進(jìn)行插入、刪除操作的線性表。表尾(即an端)稱為棧頂/top；表頭(a1端)稱為棧底/base子彈夾就是典型的棧數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第48頁(yè)。棧的抽象數(shù)據(jù)類型定義數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第49頁(yè)。棧的順序存儲(chǔ)結(jié)構(gòu)棧的順序存儲(chǔ)稱為順序棧，它是利用一組地址連續(xù)的存儲(chǔ)單元存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí)附設(shè)一個(gè)指針（top）指示當(dāng)前棧頂?shù)奈恢脭?shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第50頁(yè)。順序棧的入棧操作——例如用堆棧存放（A，B，C，D）AACBABAtoptoptoptoptop低地址L高地址MBCD數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第51頁(yè)。順序棧出棧操作——例如從棧中取出‘B’DCBAtoptopDCABDCBAtopDCBAtop低地址L高地址M數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第52頁(yè)。共享?xiàng)Ｋ伎迹簝蓚€(gè)相同類型的棧，各自開(kāi)辟了數(shù)組空間，極有可能第一個(gè)棧滿了，而另一個(gè)棧還有很多存儲(chǔ)空間，如何解決這個(gè)問(wèn)題？共享?xiàng)＃簩蓚€(gè)棧的棧底分別設(shè)置在共享空間的兩端，兩個(gè)棧頂向共享空間的中間延伸優(yōu)點(diǎn)：有效利用存儲(chǔ)空間，兩個(gè)棧的空間相互調(diào)節(jié)，只有在整個(gè)存儲(chǔ)空間被占滿時(shí)才會(huì)發(fā)生上溢，存取時(shí)間復(fù)雜度均為O(1)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第53頁(yè)。棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)采用鏈?zhǔn)酱鎯?chǔ)的棧稱為鏈棧。通常采用單鏈表實(shí)現(xiàn)，并規(guī)定所有操作都是在單鏈表的表頭進(jìn)行的優(yōu)點(diǎn)：便于多個(gè)棧共享存儲(chǔ)空間，和提高其效率，且不存在棧滿上溢的情況鏈棧的操作與鏈表類似，在此不做詳細(xì)討論對(duì)于帶頭結(jié)點(diǎn)和不帶頭結(jié)點(diǎn)的鏈棧，具體的實(shí)現(xiàn)方面有所不同需要注意數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第54頁(yè)。3.2隊(duì)列（Queue）1.基本介紹2.抽象數(shù)據(jù)類型3.順序存儲(chǔ)結(jié)構(gòu)4.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第55頁(yè)。隊(duì)列（Queue）是僅在表尾進(jìn)行插入操作，在表頭進(jìn)行刪除操作的線性表。它是一種先進(jìn)先出（ＦＩＦＯ）的線性表。例如：隊(duì)列Q=(a1

,a2,a3,……….,an-1,an)在隊(duì)尾插入元素稱為入隊(duì)；在隊(duì)首刪除元素稱為出隊(duì)。隊(duì)頭隊(duì)尾問(wèn)：為什么要設(shè)計(jì)隊(duì)列？它有什么獨(dú)特用途？離散事件的模擬（模擬事件發(fā)生的先后順序,例如CPU芯片中的指令譯碼隊(duì)列）；操作系統(tǒng)中的作業(yè)調(diào)度（一個(gè)CPU執(zhí)行多個(gè)作業(yè)）；3.簡(jiǎn)化程序設(shè)計(jì)。答：數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第56頁(yè)。隊(duì)列的抽象數(shù)據(jù)類型數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第57頁(yè)。隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)隊(duì)列的順序?qū)崿F(xiàn)是指分配一塊連續(xù)的存儲(chǔ)單元存放隊(duì)列中的元素，并附設(shè)兩個(gè)指針front和rear，隊(duì)頭指針指向隊(duì)頭元素，隊(duì)尾指針指向隊(duì)尾元素的下一個(gè)位置。Q(隊(duì)尾)(隊(duì)首)fronta1a2a3dataa40.......99rear隊(duì)尾后地址e數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第58頁(yè)。順序隊(duì)列的入隊(duì)操作：afrontrearrearfrontfrontfrontrearrear空隊(duì)5個(gè)元素入隊(duì)出隊(duì)1次出隊(duì)3次bcdebcdee數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第59頁(yè)。隊(duì)列順序存儲(chǔ)結(jié)構(gòu)的不足假溢出！數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第60頁(yè)。解決方案：循環(huán)隊(duì)列將順序隊(duì)列臆造為一個(gè)環(huán)狀的空間，即把存儲(chǔ)隊(duì)列元素的表從邏輯上看成一個(gè)環(huán)，稱為循環(huán)隊(duì)列數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第61頁(yè)。a3a2a10123N-1rearfront循環(huán)隊(duì)列（臆造）新問(wèn)題：在循環(huán)隊(duì)列中，空隊(duì)特征是front=rear；隊(duì)滿時(shí)也會(huì)有front=rear；判決條件將出現(xiàn)二義性！解決方案有三：①使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素個(gè)數(shù)（即隊(duì)列長(zhǎng)度）；②加設(shè)標(biāo)志位，刪除時(shí)置1,插入時(shí)置0,則可識(shí)別當(dāng)前front=rear屬于何種情況③人為浪費(fèi)一個(gè)單元，則隊(duì)滿特征可改為front=(rear+1)%N；順序隊(duì)列a3a2a1frontrear0123..N-1數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第62頁(yè)。隊(duì)空條件:front=rear(初始化時(shí)：front=rear)隊(duì)滿條件：front=(rear+1)%N(N=maxsize)隊(duì)列長(zhǎng)度（即數(shù)據(jù)元素個(gè)數(shù)）：L=（N＋rear－front）%NJ2J3

J1J4

J5frontrear

實(shí)際中常選用方案3（人為浪費(fèi)一個(gè)單元）：即front和rear二者之一指向?qū)嵲?，另一個(gè)指向空閑元素。

在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有N-1個(gè)元素左圖中隊(duì)列maxsizeN=6左圖中隊(duì)列長(zhǎng)度L=5數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第63頁(yè)。隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)隊(duì)列的鏈?zhǔn)奖硎痉Q為鏈隊(duì)列，它實(shí)際上是一個(gè)同時(shí)帶有隊(duì)頭指針和隊(duì)尾指針的單鏈表空隊(duì)列：數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第64頁(yè)。隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)入隊(duì)：出隊(duì)：數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第65頁(yè)。串（String）4.1串的基本概念4.2串的比較4.3串的抽象數(shù)據(jù)類型4.4串的存儲(chǔ)結(jié)構(gòu)4.5串的匹配算法數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第66頁(yè)。串長(zhǎng)：串中字符個(gè)數(shù)（n≥0）.n=0時(shí)稱為空串?？沾毫銈€(gè)字符的串?？瞻状河梢粋€(gè)或多個(gè)空格符組成的串。字串：串s中任意個(gè)連續(xù)的字符序列叫s的子串;s叫主串。字串的位置：子串的第一個(gè)字符的序號(hào)。字符位置：字符在串中的序號(hào)。串相等：串長(zhǎng)度相等，且對(duì)應(yīng)位置上字符相等。

串是由零個(gè)或多個(gè)字符組成的有限序列，又名叫字符串例如：串S=“a1a2a3……….an-1an

”數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第67頁(yè)。4.2串的比較給定兩個(gè)串：s=“a1a2……an”,t=“b1b2……bm”,當(dāng)滿足一下條件之一時(shí)，s<t。1.n<m，且ai=bi(i=1,2,……，n)例如：s=“hap”,t=“happy”,s<t2.存在某個(gè)k<=min(m,n),使得ai=bi(i=1,2,……，k-1),ak<bk例如：s=“happen”,t=“happy”,前四個(gè)字母相同，兩串第五個(gè)字母，s串‘e’的ASCII碼是101，而字母‘y’的ASCII碼是121，顯然e<y，所以s<t數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第68頁(yè)。4.3串的抽象數(shù)據(jù)類型數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第69頁(yè)。4.4串的存儲(chǔ)結(jié)構(gòu)定長(zhǎng)順序存儲(chǔ)表示——用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串值的字符序列堆分配存儲(chǔ)表示——用一組地址連續(xù)的存儲(chǔ)單元存儲(chǔ)串值的字符序列,但存儲(chǔ)空間是在程序執(zhí)行過(guò)程中動(dòng)態(tài)分配而得。串的塊鏈存儲(chǔ)表示——鏈?zhǔn)椒绞酱鎯?chǔ)首先強(qiáng)調(diào)：串與線性表的運(yùn)算有所不同，是以“串的整體”作為操作對(duì)象，例如查找某子串，在主串某位置上插入一個(gè)子串等。鏈?zhǔn)酱鎯?chǔ)順序存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第70頁(yè)。定長(zhǎng)順序存儲(chǔ)：

用一組連續(xù)的存儲(chǔ)單元來(lái)存放串，直接使用定長(zhǎng)的字符數(shù)組來(lái)定義，數(shù)組的上界預(yù)先給出，故稱為靜態(tài)存儲(chǔ)分配。堆分配存儲(chǔ)：

仍用一組連續(xù)的存儲(chǔ)單元來(lái)存放串，但存儲(chǔ)空間是在程序執(zhí)行過(guò)程中動(dòng)態(tài)分配而得。數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第71頁(yè)。討論：法1存儲(chǔ)密度為

；法2存儲(chǔ)密度為

；顯然，若數(shù)據(jù)元素很多，用法2存儲(chǔ)更優(yōu)—稱為塊鏈結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)：用鏈表存儲(chǔ)串值，易插入和刪除。法1：鏈表結(jié)點(diǎn)（數(shù)據(jù)域）大小取1法2：鏈表結(jié)點(diǎn)（數(shù)據(jù)域）大小取n(例如n=4)1/29/15=3/5存儲(chǔ)密度=串值所占的存儲(chǔ)位/實(shí)際分配的存儲(chǔ)位A.B.C.INULL……BACD.FEGH.#I##NULL數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第72頁(yè)。73算法目的：確定主串中所含子串第一次出現(xiàn)的位置（定位）

——即如何實(shí)現(xiàn)Index(S,T,pos)函數(shù)4.3串的模式匹配算法模式匹配(PatternMatching)即子串定位運(yùn)算（Index函數(shù)）兩種模式匹配算法： 1.樸素模式匹配算法 2.KMP模式匹配算法數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第73頁(yè)。樸素模式匹配算法(BF算法)簡(jiǎn)單的說(shuō)，就是對(duì)主串的每一個(gè)字符作為字串開(kāi)頭，與要匹配的字符串進(jìn)行匹配。對(duì)主串做大循環(huán)，每個(gè)字符開(kāi)頭做小循環(huán)，直到匹配成功，或全部遍歷完為止。若匹配成功，則將S中與T匹配的子序列第一個(gè)字符的序號(hào)返回舉例：主串S=“goodgoogle”,字串T=“google”數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第74頁(yè)。樹(shù)和二叉樹(shù)（Tree&BinaryTree）5.1樹(shù)的基本概念5.2樹(shù)的抽象數(shù)據(jù)類型5.3樹(shù)的存儲(chǔ)結(jié)構(gòu)5.4二叉樹(shù)5.5樹(shù)和森林5.6赫夫曼樹(shù)及其應(yīng)用數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第75頁(yè)。5.1樹(shù)的基本概念樹(shù)(Tree)是n(n>=0)個(gè)結(jié)點(diǎn)的有限集。n=0時(shí)稱為空樹(shù)。在任意一棵非空樹(shù)中：(1)有且僅有一個(gè)特定的稱為根(Root)的結(jié)點(diǎn)；(2)當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1、T2、……、Tm,其中每一個(gè)集合本身又是一棵樹(shù)，并且稱為根的子樹(shù)(SubTree)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第76頁(yè)。注意1.n>0時(shí)根結(jié)點(diǎn)是唯一的，不可能存在多個(gè)根結(jié)點(diǎn)2.m>0時(shí)子樹(shù)的個(gè)數(shù)沒(méi)有限制，但它們一定是互不相交的5.3樹(shù)的基本概念數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第77頁(yè)。結(jié)點(diǎn)分類結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹(shù)葉結(jié)點(diǎn)(終端結(jié)點(diǎn))：度為0的結(jié)點(diǎn)分支結(jié)點(diǎn)(非終端結(jié)點(diǎn))：度不為0的結(jié)點(diǎn)樹(shù)的度：樹(shù)內(nèi)各結(jié)點(diǎn)的度的最大值5.3樹(shù)的基本概念數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第78頁(yè)。結(jié)點(diǎn)間關(guān)系結(jié)點(diǎn)的子樹(shù)的根稱為該結(jié)點(diǎn)的孩子(Child)，相應(yīng)地，該結(jié)點(diǎn)稱為孩子的雙親(Parent)。同一個(gè)雙親的孩子之間互稱兄弟(Silbing)。結(jié)點(diǎn)的祖先是從根結(jié)點(diǎn)到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)。以某結(jié)點(diǎn)為根的子樹(shù)中任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫。對(duì)于H來(lái)說(shuō)，D、B、A都是它的祖先對(duì)B來(lái)說(shuō)，D、G、H、I都是它的子孫5.3樹(shù)的基本概念數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第79頁(yè)。樹(shù)的分層結(jié)點(diǎn)的層次(Level)：從根開(kāi)始定義起，根為第一層，根的孩子為第二層,以此類推。堂兄弟：雙親在同一層的結(jié)點(diǎn)。結(jié)點(diǎn)的深度：是從根節(jié)點(diǎn)開(kāi)始自頂向下逐層累加結(jié)點(diǎn)的高度：從葉節(jié)點(diǎn)開(kāi)始自底層向上逐層累加樹(shù)的深度(Depth)或高度：樹(shù)中結(jié)點(diǎn)最大層次5.3樹(shù)的基本概念數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第80頁(yè)。樹(shù)的其他概念D、E、F互為堂兄弟當(dāng)前樹(shù)的深度為4如果書(shū)中結(jié)點(diǎn)的各子樹(shù)看成從左至右是有次序的，不能互換的，則稱該樹(shù)為有序樹(shù)，否則稱為無(wú)序樹(shù)。路徑長(zhǎng)度：路徑上所經(jīng)過(guò)的邊的個(gè)數(shù)森林是m(m>=0)棵互不相交的樹(shù)的集合5.3樹(shù)的基本概念數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第81頁(yè)。樹(shù)的性質(zhì)1)樹(shù)中的結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的度數(shù)加12)度為m的樹(shù)中第i層上至多有mi-1個(gè)結(jié)點(diǎn)（i>=1）3)高度為h的m叉樹(shù)至多有(mh-1)/(m-1)個(gè)結(jié)點(diǎn)4)具有n個(gè)結(jié)點(diǎn)的m叉樹(shù)的最小高度為[logm(n(m-1)+1)]5.3樹(shù)的基本概念數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第82頁(yè)。樹(shù)與線性表的對(duì)比5.3樹(shù)的基本概念數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第83頁(yè)。5.3樹(shù)的抽象數(shù)據(jù)類型數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第84頁(yè)。5.3樹(shù)的存儲(chǔ)結(jié)構(gòu)說(shuō)到存儲(chǔ)，我們會(huì)想起順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)兩種結(jié)構(gòu)。簡(jiǎn)單的順序存儲(chǔ)結(jié)構(gòu)不能滿足樹(shù)的實(shí)現(xiàn)要求充分利用順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的特點(diǎn)，可以實(shí)現(xiàn)對(duì)樹(shù)的存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)存儲(chǔ)結(jié)構(gòu)：①雙親表示法②孩子表示法③孩子兄弟表示法數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第85頁(yè)。5.3樹(shù)的存儲(chǔ)結(jié)構(gòu)①雙親表示法思路：用一組連續(xù)空間來(lái)存儲(chǔ)樹(shù)的結(jié)點(diǎn)，同時(shí)在每個(gè)結(jié)點(diǎn)中附設(shè)一個(gè)指示器，指示其雙親結(jié)點(diǎn)在鏈表中的位置。parentsdata結(jié)點(diǎn)結(jié)構(gòu)dataparents1樹(shù)結(jié)構(gòu)

23n數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第86頁(yè)。缺點(diǎn)：求結(jié)點(diǎn)的孩子時(shí)需要遍歷整個(gè)結(jié)構(gòu)。5.3樹(shù)的存儲(chǔ)結(jié)構(gòu)①雙親表示法實(shí)際中權(quán)限菜單的結(jié)構(gòu)設(shè)計(jì)。數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第87頁(yè)。存儲(chǔ)結(jié)構(gòu)的設(shè)計(jì)是一個(gè)非常靈活的過(guò)程。一個(gè)存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)的是否合理，取決于基于該存儲(chǔ)結(jié)構(gòu)的運(yùn)算是否合適、是否方便，時(shí)間復(fù)雜度好不好等5.3樹(shù)的存儲(chǔ)結(jié)構(gòu)①雙親表示法拓展長(zhǎng)子域數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第88頁(yè)。5.3樹(shù)的存儲(chǔ)結(jié)構(gòu)②孩子表示法思路：將每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)都用單鏈表鏈接起來(lái)形成一個(gè)線性結(jié)構(gòu)，則N個(gè)結(jié)點(diǎn)就有N個(gè)孩子鏈表（葉子結(jié)點(diǎn)的孩子鏈表為空表）優(yōu)缺點(diǎn)：尋找子女的操作非常直接，而尋找雙親需要遍歷N個(gè)結(jié)點(diǎn)abecdfhgdefghgfedcbah12345678bc數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第89頁(yè)。5.3樹(shù)的存儲(chǔ)結(jié)構(gòu)③孩子兄弟表示法思路：用二叉鏈表來(lái)表示樹(shù)，但鏈表中的兩個(gè)指針域含義不同。左指針指向該結(jié)點(diǎn)的第一個(gè)孩子；右指針指向該結(jié)點(diǎn)的下一個(gè)兄弟結(jié)點(diǎn)。nextsiblingdatafirstchild指向左孩子指向右兄弟數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第90頁(yè)。abecdfhgbacedfgh③孩子兄弟表示法5.3樹(shù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第91頁(yè)。5.4二叉樹(shù)為何要重點(diǎn)研究每結(jié)點(diǎn)最多只有兩個(gè)“叉”的樹(shù)？二叉樹(shù)的結(jié)構(gòu)最簡(jiǎn)單，規(guī)律性最強(qiáng)；可以證明，所有樹(shù)都能轉(zhuǎn)為唯一對(duì)應(yīng)的二叉樹(shù)，不失一般性。1. 二叉樹(shù)的基本概念2. 二叉樹(shù)的性質(zhì)3. 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第92頁(yè)。1.二叉樹(shù)的基本概念定義：是n（n≥0）個(gè)結(jié)點(diǎn)的有限集合，該集合或者為空集，或者由一個(gè)根結(jié)點(diǎn)以及至多兩棵互不相交的、分別稱為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。5.4二叉樹(shù)特點(diǎn)：

每個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)

左右子樹(shù)有順序，次序不能任意顛倒

即使樹(shù)中某結(jié)點(diǎn)只有一棵子樹(shù)，也要區(qū)分它是左子樹(shù)還是右子樹(shù)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第93頁(yè)。5.4二叉樹(shù)

具有3個(gè)結(jié)點(diǎn)的二叉樹(shù)可能有幾種不同形態(tài)？普通樹(shù)呢？2、二叉樹(shù)的五種基本形態(tài)1.空二叉樹(shù)2.只有一個(gè)根結(jié)點(diǎn)3.根結(jié)點(diǎn)只有左子樹(shù)4.根結(jié)點(diǎn)只有右子樹(shù)5.根結(jié)點(diǎn)既有左子樹(shù)又有右子樹(shù)

數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第94頁(yè)。滿二叉樹(shù)：一棵高度為h，并且含有2h-1個(gè)結(jié)點(diǎn)的二叉樹(shù)稱為滿二叉樹(shù)，即樹(shù)中的每一層都含有最多的結(jié)點(diǎn)5.4二叉樹(shù)121234567111089131415滿二叉樹(shù)按層序編號(hào)：約定編號(hào)從根結(jié)點(diǎn)（根結(jié)點(diǎn)編號(hào)為1）起，自上而下，自左向右。這樣每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)編號(hào)，對(duì)編號(hào)為i的結(jié)點(diǎn)，如果有雙親，其雙親為[i/2]，如果有左孩子，則左孩子為2i；如果有右孩子，則右孩子為2i+13、特殊二叉樹(shù)——滿二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第95頁(yè)。4、特殊二叉樹(shù)——完全二叉樹(shù)完全二叉樹(shù)：設(shè)一個(gè)高度為h，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與高度為h的滿二叉樹(shù)編號(hào)為1~n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱為完全二叉樹(shù)5.4二叉樹(shù)12345671089完全二叉樹(shù)特點(diǎn)：1.葉子結(jié)點(diǎn)只能出現(xiàn)在最下兩層2.倒數(shù)第二層，若有葉子結(jié)點(diǎn)，一定都在右部連續(xù)位置3.去掉最后一層，則必為滿二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第96頁(yè)。5、特殊二叉樹(shù)——二叉排序樹(shù)、平衡二叉樹(shù)

二叉排序樹(shù)：一棵二叉樹(shù)或空二叉樹(shù)，或者是具有如下性質(zhì)的二叉樹(shù)：左子樹(shù)上所有結(jié)點(diǎn)的關(guān)鍵字均小于根結(jié)點(diǎn)的關(guān)鍵字；右子樹(shù)上的所有結(jié)點(diǎn)的關(guān)鍵字均大于根結(jié)點(diǎn)的關(guān)鍵字。左子樹(shù)和右子樹(shù)又各是一棵二叉排序樹(shù)5.4二叉樹(shù)平衡二叉樹(shù)：樹(shù)上任一結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的深度之差不超過(guò)1數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第97頁(yè)。1.二叉樹(shù)性質(zhì)性質(zhì)1：在二叉樹(shù)的第i層上至多有2i-1個(gè)結(jié)點(diǎn)(i>=1)5.4二叉樹(shù)性質(zhì)2：深度為k的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)(k>=1)性質(zhì)3：對(duì)任何一棵二叉樹(shù)T，如果其終端結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為[log2n]+1([x]表示不大于x的最大整數(shù))數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第98頁(yè)。2.二叉樹(shù)性質(zhì)性質(zhì)5：如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)(其深度為[log2n]+1)的結(jié)點(diǎn)按層編號(hào)（從第1層到第[log2n]+1層，每層從左到右），對(duì)任一結(jié)點(diǎn)i(1<=i<=n)有： 1）如果i=1，則結(jié)點(diǎn)i是二叉樹(shù)的根，無(wú)雙親；如果i>1，則其雙親是結(jié)點(diǎn)[i/2] 2）如果2i>n，則結(jié)點(diǎn)i無(wú)左孩子(結(jié)點(diǎn)i為葉子結(jié)點(diǎn))；否則其左孩子是結(jié)點(diǎn)2i 3）如果2i+1>n，則結(jié)點(diǎn)i無(wú)右孩子；否則其右孩子是結(jié)點(diǎn)2i+15.4二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第99頁(yè)。5.4二叉樹(shù)3.二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)按二叉樹(shù)的結(jié)點(diǎn)“自上而下、從左至右”編號(hào)，用一組連續(xù)的存儲(chǔ)單元存儲(chǔ)。可按照完全二叉樹(shù)的編號(hào)，把不存在的結(jié)點(diǎn)設(shè)置為缺點(diǎn)：①浪費(fèi)空間；②插入、刪除不便順序存儲(chǔ)結(jié)構(gòu)一般只用于完全二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第100頁(yè)。5.4二叉樹(shù)3.二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（二叉鏈表）數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第101頁(yè)。二叉樹(shù)的遍歷是指從根結(jié)點(diǎn)出發(fā)，按照某種次序一次訪問(wèn)二叉樹(shù)中所有的結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)被訪問(wèn)一次且僅被訪問(wèn)一次二叉樹(shù)遍歷方法：①前序遍歷②中序遍歷③后續(xù)遍歷④層序遍歷5.4二叉樹(shù)4.遍歷二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第102頁(yè)。①前序遍歷規(guī)則：若二叉樹(shù)為空，則空操作返回，否則先訪問(wèn)根結(jié)點(diǎn)，然后前序遍歷左子樹(shù)，再前序遍歷右子樹(shù)5.4二叉樹(shù)4.遍歷二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第103頁(yè)。②中序遍歷規(guī)則：若二叉樹(shù)為空，則空操作返回，否則從根結(jié)點(diǎn)開(kāi)始(注意并不是先訪問(wèn)根結(jié)點(diǎn))，中序遍歷根結(jié)點(diǎn)的左子樹(shù)，然后是訪問(wèn)根結(jié)點(diǎn)，最后中序遍歷右子樹(shù)5.4二叉樹(shù)4.遍歷二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第104頁(yè)。③后序遍歷規(guī)則：若二叉樹(shù)為空，則空操作返回，否則從左到右先葉子后結(jié)點(diǎn)的方式遍歷訪問(wèn)左右子樹(shù)，最后是訪問(wèn)根結(jié)點(diǎn)。4.遍歷二叉樹(shù)5.4二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第105頁(yè)。④層序遍歷規(guī)則：若二叉樹(shù)為空，則空操作返回，否則從樹(shù)的第一層，也就是根結(jié)點(diǎn)開(kāi)始訪問(wèn)，從上而下逐層遍歷，在同一層中，按從左到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問(wèn)。5.4二叉樹(shù)4.遍歷二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第106頁(yè)。④層序遍歷規(guī)則：若二叉樹(shù)為空，則空操作返回，否則從樹(shù)的第一層，也就是根結(jié)點(diǎn)開(kāi)始訪問(wèn)，從上而下逐層遍歷，在同一層中，按從左到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問(wèn)。5.4二叉樹(shù)4.遍歷二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第107頁(yè)。5.3樹(shù)和森林樹(shù)轉(zhuǎn)換為二叉樹(shù)1.加線：在所有兄弟結(jié)點(diǎn)之間加一條連線2.去線：對(duì)書(shū)中每個(gè)結(jié)點(diǎn)，只保留它與第一個(gè)孩子結(jié)點(diǎn)的連線，刪除它與其他孩子系欸但之間的連線3.層次調(diào)整：以樹(shù)的根結(jié)點(diǎn)為軸心，將整棵樹(shù)順時(shí)針旋轉(zhuǎn)一定角度，使之結(jié)構(gòu)層次分明。注意第一個(gè)孩子是二叉樹(shù)結(jié)點(diǎn)的左孩子，兄弟轉(zhuǎn)換過(guò)來(lái)的孩子是結(jié)點(diǎn)的右孩子。數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第108頁(yè)。5.3樹(shù)和森林樹(shù)轉(zhuǎn)換為二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第109頁(yè)。5.3樹(shù)和森林森林轉(zhuǎn)換為二叉樹(shù)步驟：1.把每個(gè)樹(shù)轉(zhuǎn)換為二叉樹(shù)2.第一棵二叉樹(shù)不動(dòng)，從第二棵二叉樹(shù)開(kāi)始，依次把后一棵二叉樹(shù)的根結(jié)點(diǎn)作為前一棵二叉樹(shù)的根結(jié)點(diǎn)的右孩子，用線連起來(lái)。當(dāng)所有的二叉樹(shù)連接起來(lái)后就得到了由森林轉(zhuǎn)換來(lái)的二叉樹(shù)森林是由若干棵樹(shù)組成的，所以完全可以理解為，森林中的每一棵樹(shù)都是兄弟，可以按照兄弟的處理辦法來(lái)操作數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第110頁(yè)。5.3樹(shù)和森林森林轉(zhuǎn)換為二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第111頁(yè)。5.3樹(shù)和森林二叉樹(shù)轉(zhuǎn)換為樹(shù)步驟：1.加線。若某結(jié)點(diǎn)的左孩子結(jié)點(diǎn)存在，則將左孩子的n個(gè)右孩子結(jié)點(diǎn)用線連接起來(lái)2.去線。刪除原二叉樹(shù)中所有結(jié)點(diǎn)與其右孩子結(jié)點(diǎn)的連線3.層次調(diào)整，使之結(jié)構(gòu)層次分明二叉樹(shù)轉(zhuǎn)換為樹(shù)是樹(shù)轉(zhuǎn)換為二叉樹(shù)的逆過(guò)程，也就是反過(guò)來(lái)做而已數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第112頁(yè)。5.3樹(shù)和森林二叉樹(shù)轉(zhuǎn)換為樹(shù)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第113頁(yè)。5.3樹(shù)和森林二叉樹(shù)轉(zhuǎn)換為森林步驟：1.從根結(jié)點(diǎn)開(kāi)始，若右孩子存在，則把與右孩子結(jié)點(diǎn)的連線刪除，再查看分離后的二叉樹(shù)，若右孩子存在，則連線刪除，直到所有的右孩子連線都刪除為止，得到分離的二叉樹(shù)2.將每棵分離后的二叉樹(shù)轉(zhuǎn)換為樹(shù)判斷一棵二叉樹(shù)能夠轉(zhuǎn)換成一棵樹(shù)還是森林，標(biāo)準(zhǔn)很簡(jiǎn)單，就是只要看這棵樹(shù)的根結(jié)點(diǎn)有沒(méi)有右孩子，有就是森林，沒(méi)有就是一棵樹(shù)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第114頁(yè)。5.3樹(shù)和森林二叉樹(shù)轉(zhuǎn)換為森林?jǐn)?shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第115頁(yè)。5.4哈夫曼樹(shù)哈夫曼樹(shù)的引例效率相對(duì)低效率相對(duì)高數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第116頁(yè)。5.4哈夫曼樹(shù)哈夫曼樹(shù)的定義在許多實(shí)際應(yīng)用中，樹(shù)中結(jié)點(diǎn)常常被賦予一個(gè)表示某種意義的數(shù)值，稱為該結(jié)點(diǎn)的權(quán)。從樹(shù)根結(jié)點(diǎn)到任意結(jié)點(diǎn)的路徑長(zhǎng)度與該結(jié)點(diǎn)上權(quán)值的乘積稱為該結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度樹(shù)中所有的葉結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和稱為該樹(shù)的帶權(quán)路徑長(zhǎng)度記為Wi是第i個(gè)葉結(jié)點(diǎn)所帶的權(quán)值；li是該葉結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長(zhǎng)度在含有N個(gè)帶權(quán)葉子結(jié)點(diǎn)的二叉樹(shù)中，其中帶權(quán)路徑長(zhǎng)度(WPL)最小的二叉樹(shù)稱為哈夫曼樹(shù)，也稱為最優(yōu)二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第117頁(yè)。5.4哈夫曼樹(shù)帶權(quán)路徑長(zhǎng)度計(jì)算(a)WPL=7*2+5*2+2*2+4*2=36(a)WPL=7*3+5*3+2*1+4*2=46(a)WPL=7*1+5*2+2*3+4*3=35(c)中樹(shù)的WPL最小，它為哈夫曼樹(shù)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第118頁(yè)。5.4哈夫曼樹(shù)哈夫曼樹(shù)的構(gòu)造給定N個(gè)權(quán)值分別為w1，w2,…，wn的結(jié)點(diǎn)，通過(guò)哈夫曼算法構(gòu)造出最優(yōu)二叉樹(shù)1.將這n個(gè)結(jié)點(diǎn)分別作為n棵僅含一個(gè)結(jié)點(diǎn)的二叉樹(shù)，構(gòu)成森林F2.構(gòu)造一個(gè)新結(jié)點(diǎn)，并從F中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹(shù)作為新結(jié)點(diǎn)的左、右子樹(shù)，并且將新結(jié)點(diǎn)的權(quán)值置為左、右子樹(shù)上根結(jié)點(diǎn)的權(quán)值之和3.從F中刪除剛才選出的兩棵樹(shù)，同時(shí)將新的到的樹(shù)加入F中4.重復(fù)步驟2和3，直至F中只剩下一棵樹(shù)為止數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第119頁(yè)。5.4哈夫曼樹(shù)哈夫曼樹(shù)的構(gòu)造過(guò)程數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第120頁(yè)。5.4哈夫曼樹(shù)哈夫曼樹(shù)的特點(diǎn)1.每個(gè)初始結(jié)點(diǎn)最終都稱為葉結(jié)點(diǎn)，并且權(quán)值越小的結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑長(zhǎng)度越大2.構(gòu)造過(guò)程中共新建了N-1個(gè)結(jié)點(diǎn)（雙分支結(jié)點(diǎn)），因此哈夫曼樹(shù)中結(jié)點(diǎn)總數(shù)為2N-13.每次構(gòu)造都選擇2棵樹(shù)作為新結(jié)點(diǎn)的孩子，因此哈夫曼樹(shù)中不存在度為1的結(jié)點(diǎn)

數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第121頁(yè)。圖6.1圖的基本概念6.2圖的存儲(chǔ)及基本操作(鄰接矩陣法；鄰接表法；鄰接多重表法；十字鏈表法)6.3圖的遍歷(深度優(yōu)先搜索；廣度優(yōu)先搜索)6.4圖的基本應(yīng)用(最小生成樹(shù)；最短路徑)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第122頁(yè)。6.1圖的基本概念圖G由頂點(diǎn)集V和邊集E組成，記為G=(V,E)，其中V(G)表示圖G中頂點(diǎn)的有限非空集；E(G)表示圖G中頂點(diǎn)之間的關(guān)系(邊)集合。若V={v1,v2,……,vn},用|V|表示圖G中頂點(diǎn)的個(gè)數(shù)，也稱為圖G的階，E={(u,v)|u∈V,v∈V},用|E|表示圖G中邊的條數(shù)注意：線性表可以是空表，樹(shù)可以是空樹(shù)，但圖不可以是空?qǐng)D圖中不能一個(gè)頂點(diǎn)也沒(méi)有，但邊集E可以為空數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第123頁(yè)。6.1圖的基本概念有向圖：若E是有向邊(也稱為弧)的有限集合時(shí)，則圖G為有向圖。弧是頂點(diǎn)的有序?qū)?，記?lt;v,w>，其中v,w是頂點(diǎn)，v稱為弧尾，w稱為弧頭，稱為從頂點(diǎn)v到頂點(diǎn)w的弧，也稱v鄰接到w，或w鄰接自v。123

G=(V,E)V={1,2,3}E={<1,2>,<2,1>,<2,3>}數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第124頁(yè)。6.1圖的基本概念無(wú)向圖：若E是無(wú)向邊(簡(jiǎn)稱邊)的有限集合時(shí)，則圖G為無(wú)向圖。邊：是頂點(diǎn)的無(wú)序?qū)?，記?v,w)或(w,v)。因?yàn)?v,w)=(w,v),其中v,w是頂點(diǎn)，可以說(shuō)頂點(diǎn)w和頂點(diǎn)v互為鄰接點(diǎn)。邊(v,w)依附于頂點(diǎn)w和v，或者說(shuō)邊(v,w)和頂點(diǎn)v,w相關(guān)聯(lián)。1234

G=(V,E)V={1,2,3,4}E={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第125頁(yè)。6.1圖的基本概念簡(jiǎn)單圖：一個(gè)圖G如果滿足：1.不存在重復(fù)邊；2.不存在頂點(diǎn)到自身的邊，則稱圖G為簡(jiǎn)單圖。(數(shù)據(jù)結(jié)構(gòu)中僅討論簡(jiǎn)單圖)DBCA數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第126頁(yè)。6.1圖的基本概念多重圖：若圖G中某兩個(gè)結(jié)點(diǎn)之間的邊數(shù)多于一條，又允許頂點(diǎn)通過(guò)同一條邊和自己關(guān)聯(lián)，則G為多重圖。(多重圖的定義和簡(jiǎn)單圖是相對(duì)的)DBCA數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第127頁(yè)。6.1圖的基本概念無(wú)向完全圖：在無(wú)向圖中，如果任意兩個(gè)頂點(diǎn)之間都存在邊，則稱該圖為無(wú)向完全圖。含有n個(gè)頂點(diǎn)的無(wú)向完全圖有n(n-1)/2條邊。有向完全圖：在有向圖中，如果任意兩個(gè)頂點(diǎn)之間都存在方向相反的兩條弧，則稱該圖為有向完全圖。含有n個(gè)頂點(diǎn)的有向完全圖有n(n-1)條有向邊DBCADBCA無(wú)向完全圖有向完全圖數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第128頁(yè)。6.1圖的基本概念子圖：設(shè)有兩個(gè)圖G1=(V1,E1)和G2=(V2,E2)，若V2是V1的子集，則稱G2是G的子圖。注意：

并非V和E的任何子集都能構(gòu)成G的子圖，因?yàn)檫@樣的子集可能不是圖，也就是說(shuō)，E的子集中的某些邊關(guān)聯(lián)的頂點(diǎn)可能不在這個(gè)V的子集中DBCADBCDBCADCA數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第129頁(yè)。6.1圖的基本概念連通：在無(wú)向圖中，若從頂點(diǎn)v到頂點(diǎn)w有路徑存在，則稱v和w是連通的。連通圖：若圖G中任意兩個(gè)頂點(diǎn)都是連通的，則稱圖G為連通圖。否則稱為非連通圖。ABCDEFABCD非連通圖連通圖數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第130頁(yè)。6.1圖的基本概念連通分量：無(wú)向圖中的極大連通子圖稱為連通分量。如果一個(gè)圖有n個(gè)頂點(diǎn)，并且有小于n-1條邊，則此圖必為非連通圖注意： 1.要是子圖 2.子圖要是連通的 3.連通子圖含有極大頂點(diǎn)數(shù) 4.具有極大頂點(diǎn)數(shù)的連通子圖包含依附于

這些頂點(diǎn)的所有邊數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第131頁(yè)。6.1圖的基本概念圖1是一個(gè)無(wú)向非連通圖，但是它有兩個(gè)連通分量，即圖2和圖3。圖4盡管是圖1的子圖，但是它卻不滿足連通子圖的極大頂點(diǎn)數(shù)，因此它不是圖1的無(wú)向圖的連通分量ABCDEF圖1ABCD圖2EF圖3ABD圖4數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第132頁(yè)。6.1圖的基本概念強(qiáng)連通：在有向圖中，若從頂點(diǎn)v到頂點(diǎn)w和從頂點(diǎn)w到頂點(diǎn)v之間都有路徑，則稱這兩個(gè)頂點(diǎn)是強(qiáng)連通的強(qiáng)連通圖：若圖中任何一對(duì)頂點(diǎn)都是強(qiáng)連通的，則此圖稱為強(qiáng)連通圖。DBCA123判斷是否是強(qiáng)連通圖數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第133頁(yè)。6.1圖的基本概念強(qiáng)連通分量：有向圖中極大強(qiáng)連通子圖稱為有向圖的強(qiáng)連通分量DBCADBA圖1圖2圖2是圖1的強(qiáng)連通分量數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第134頁(yè)。6.1圖的基本概念生成樹(shù)：連通圖的生成樹(shù)是包含圖中全部頂點(diǎn)的一個(gè)極小連通子圖。若圖中頂點(diǎn)數(shù)為n，則它的生成樹(shù)含有n-1條邊。對(duì)于生成樹(shù)而言，若砍去它的一條邊，則會(huì)變成非連通圖，若加上一條邊則會(huì)形成一個(gè)回路。生成森林：在非連通圖中，連通分量的生成樹(shù)構(gòu)成了非連通圖的生成森林?jǐn)?shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第135頁(yè)。6.1圖的基本概念頂點(diǎn)的度：以該頂點(diǎn)為一個(gè)端點(diǎn)的邊的數(shù)目對(duì)于無(wú)向圖，頂點(diǎn)v的度是指依附于該頂點(diǎn)的邊的條數(shù)，記為T(mén)D(v)對(duì)于有向圖，頂點(diǎn)v的度分為入度和出度，入度是以頂點(diǎn)v為終點(diǎn)的有向邊的數(shù)目，記為ID(v)；而出度是以頂點(diǎn)v為起點(diǎn)的有向邊的數(shù)目，記為OD(v)。頂點(diǎn)v的度等于其入度和出度之和，即TD(v)=ID(v)+OD(v)數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第136頁(yè)。6.1圖的基本概念邊上的權(quán)：在一個(gè)圖中，每條邊都可以標(biāo)上具有某種含義的數(shù)值，該數(shù)值稱為該邊的權(quán)值。網(wǎng)：邊上帶有權(quán)值的圖稱為帶權(quán)圖稀疏圖：邊數(shù)很少（相對(duì)的）的圖稱為稀疏圖稠密圖：邊數(shù)很多（相對(duì)的）的圖稱為稠密圖一般當(dāng)圖G滿足|E|<|V|*log|V|時(shí)，可以將G看成是稀疏圖數(shù)據(jù)結(jié)構(gòu)詳解全文共163頁(yè)，當(dāng)前為第137頁(yè)。6.1圖的基本概念路徑長(zhǎng)度:頂點(diǎn)Vp到頂點(diǎn)Vq之間有一條路徑是指頂點(diǎn)序列Vp，Vi1，Vi2，……，Vim，Vq。路徑上邊的數(shù)目稱為路徑長(zhǎng)度。回路或環(huán):第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑稱為回路或環(huán)。如果一個(gè)圖有n個(gè)頂點(diǎn)，并且有大于n-1條邊，則此圖一定有環(huán)。簡(jiǎn)單路徑：在路徑序列中，頂點(diǎn)不重復(fù)出現(xiàn)的路徑稱為簡(jiǎn)單路徑。簡(jiǎn)單回路：除第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路稱為簡(jiǎn)單回路。