信息學(xué)奧賽-計算機(jī)基礎(chǔ)知識

TOC\o"1-5"\h\z第一章計算機(jī)基礎(chǔ)知識 2第一節(jié)數(shù)制及其轉(zhuǎn)換 2\o"CurrentDocument"第二節(jié)算術(shù)運(yùn)算和邏輯運(yùn)算 4\o"CurrentDocument"第三節(jié)原碼、反碼和補(bǔ)碼 7\o"CurrentDocument"第四節(jié)浮點(diǎn)數(shù)的表示方法 9\o"CurrentDocument"第五節(jié)奇偶校驗(yàn) 10\o"CurrentDocument"第六節(jié)ASCII碼表 12第二章計算機(jī)硬件基礎(chǔ) 13第一節(jié)中央處理器 13\o"CurrentDocument"第二節(jié)存儲器系統(tǒng) 15\o"CurrentDocument"第三節(jié)輸入輸出系統(tǒng) 17第三章網(wǎng)絡(luò)基礎(chǔ)知識 19第一節(jié)網(wǎng)絡(luò)的組成與結(jié)構(gòu) 19\o"CurrentDocument"第二節(jié)網(wǎng)絡(luò)協(xié)議 20\o"CurrentDocument"第三節(jié)Internet相關(guān)知識 20第三節(jié)Internet相關(guān)知識 21第四章其他相關(guān)基礎(chǔ)知識 23第一節(jié)計算機(jī)病毒 23\o"CurrentDocument"第二節(jié)數(shù)據(jù)庫系統(tǒng) 23第五章數(shù)據(jù)結(jié)構(gòu)之線性結(jié)構(gòu) 25第一節(jié) 線性表 25\o"CurrentDocument"第二節(jié) 棧 27\o"CurrentDocument"第三節(jié) 隊列 29第六章數(shù)據(jù)結(jié)構(gòu)之非線性結(jié)構(gòu) 31第一節(jié) 樹的概念 31\o"CurrentDocument"第二節(jié) 樹的表示方法和存儲結(jié)構(gòu) 33\o"CurrentDocument"第三節(jié) 二叉樹的概念 36\o"CurrentDocument"第四節(jié) 二叉樹的遍歷 40\o"CurrentDocument"第五節(jié) 普通樹的遍歷 44\o"CurrentDocument"第六節(jié) 根據(jù)兩種遍歷順序確定樹結(jié)構(gòu) 46\o"CurrentDocument"第七節(jié) 二叉排序樹 47\o"CurrentDocument"第八節(jié) 最優(yōu)二叉樹（哈夫曼樹） 48\o"CurrentDocument"AOE網(wǎng) 50第一章計算機(jī)基礎(chǔ)知識第一節(jié)數(shù)制及其轉(zhuǎn)換一、二、八、十六進(jìn)制轉(zhuǎn)十進(jìn)制的方法：乘權(quán)相加法。例如：(11010110)2=1x27+1x26+0x25+1x24+0x23+1x22+1x2"0x2。=(214)10(2365)8=2x83+3x82+6x81+5x8。=(1269)10(4BF)16=4x162+11x161+15x160=(1215)10帶小數(shù)的情況：(110.011)2=1x22+1x21+1x20+0x2-1+1x2-2+1x2-3=(6.375)10(5.76)8=5x80+7x8-1+6x8-2=(5.96875)10(D.1C)16=13x160+1x16-1+12*16-2=(13.109375)10二、十進(jìn)制化二進(jìn)制的方法：整數(shù)部分除二取余法，小數(shù)部分乘二取整法。例一：(43)10=(101011)2 例二：(0.375)10=(0.011)從下自上M列除二取余法0.375乘二期整法X2

075。從下自上M列除二取余法0.375乘二期整法X2

075。X20.500X20.000若除不盡可以保

留一定小數(shù)位數(shù)直上而下排列三、二進(jìn)制轉(zhuǎn)八進(jìn)制的方法一位數(shù)八進(jìn)制與二進(jìn)制對應(yīng)表八進(jìn)制二進(jìn)制轉(zhuǎn)換方法：對二進(jìn)制以小數(shù)點(diǎn)為分隔，往前往后每三位劃為一組，不足三位補(bǔ)0，按上表用對應(yīng)的八進(jìn)制數(shù)字代入即可。例如：(10111011.01100111)=010,111,011.011,001,110=(273.36)&800001001201030114100510161107111三、二進(jìn)制轉(zhuǎn)十六進(jìn)制的方法一位數(shù)十六進(jìn)制與二進(jìn)制對應(yīng)表十六進(jìn)制二進(jìn)制轉(zhuǎn)換方法：對二進(jìn)制以小數(shù)點(diǎn)為分隔，往前往后每四位劃為一組，不足四位補(bǔ)0，按上表用對應(yīng)的十六進(jìn)制數(shù)字代入即可。例如：(10111011.01100111)=1011,1011.0110,0111=(BB.67)1600000100012001030011401005010160110

以上都是用括號加數(shù)字的表示方法，另外還有英文表示法，就是以BIN、OCT、HEX、DEC分別代表二、八、十六、十進(jìn)制?；蛘咧粚懙谝粋€字母。例如1101B表示是二進(jìn)制。有些地方為了避免“0”跟“0”混淆，把O寫成Q。第二節(jié)算術(shù)運(yùn)算和邏輯運(yùn)算一、二進(jìn)制的算術(shù)運(yùn)算1、加法運(yùn)算規(guī)則：0+0=0 0+1=11+0=11+1=102、減法運(yùn)算規(guī)則：0-0=00-1=1（向高位借1）1-0=11-1=03、乘法運(yùn)算規(guī)則：0x0=00x1=01x0=01x1=1二、邏輯運(yùn)算1、基本運(yùn)算①邏輯乘，也稱“與”運(yùn)算，運(yùn)算符為“?”或“A”0-0=00-1=01-0=01-1=1使用邏輯變量時，A-B可以寫成AB②邏輯加，也乘“或”運(yùn)算，運(yùn)算符為“+”或“V”0+0=0 0+1=11+0=11+1=1③邏輯非，也稱“反”運(yùn)算，運(yùn)算符是在邏輯值或變量符號上加“一”0=1 1=02、常用運(yùn)算異或運(yùn)算：A十B=A-B+A-B2、基本公式①0，1律A-0=0AT=AA+0=AA+1=1②交換律A+B=B+AA-B=B-A③結(jié)合律A+B+C=(A+B)+C=A+(B+C)A-B-C=(A?B)?C=A?(B?C)④分配律A?(B+C)=A-B+A-C⑤重疊律A+A+...+A=AA-A-...-A=A⑥互補(bǔ)律A+A=1A-A=0⑦吸收律A+A-B=AA?(A+B)=AA+A-B=A+BA-(A+B)=A-B⑧對合律對一個邏輯變量兩次取反仍是它本身⑨德?摩根定理A+B=A-BA?B=A+B三、邏輯代數(shù)的應(yīng)用1、邏輯表達(dá)式化簡例如：F=A?B+A-B+A-B=A?B+A(B+B) (利用分配律)=A?B+A （利用互補(bǔ)律以及0，1律）=A+B （利用吸收律）2、對指定位進(jìn)行運(yùn)算，假設(shè)變量A有八位，容是d7d6d5d4d3d2d1d0①將變量A的d/立清零A?（11011111）-A②將變量A的各位置1A+（11111111）-A第三節(jié)原碼、反碼和補(bǔ)碼計算機(jī)中參與運(yùn)算的數(shù)有正負(fù)之分，計算機(jī)中的數(shù)的正負(fù)號也是用二進(jìn)制表示的。用二進(jìn)制數(shù)表示符號的數(shù)稱為機(jī)器碼。常用的機(jī)器碼有原碼、反碼和補(bǔ)碼。一、原碼求原碼的方法：設(shè)X；若XN0，則符號位（原碼最高位）為0，X其余各位取值照抄；若XW0，則符號位為1,其余各位照抄?！纠?】X=+1001001 [X]原=01001001【例2】X=-1001001 [X]原=11001001二、反碼求反碼的方法：設(shè)X；若XN0，則符號位（原碼最高位）為0，X其余各位取值照抄；若XW0，則符號位為1,其余各位按位取反?！纠?】X=+1001001 [X]反=01001001【例4】X=-1001001 [X]反=10110110三、補(bǔ)碼求補(bǔ)碼的方法：設(shè)X；若XN0，則符號位（原碼最高位）為0，X其余各位取值照抄；若XW0，則符號位為1,其余各位按位取反后，最低位加1?！纠?】X=+1001001 ［X］補(bǔ)=01001001【例6】X=-1001001 ［X］補(bǔ)=10110111四、補(bǔ)碼加減法計算機(jī)中實(shí)際上只有加法，減法運(yùn)算轉(zhuǎn)換成加法運(yùn)算進(jìn)行，乘法運(yùn)算轉(zhuǎn)換成加法運(yùn)算進(jìn)行，除法運(yùn)算轉(zhuǎn)換成減法運(yùn)算進(jìn)行。用補(bǔ)碼可以很方便的進(jìn)行這種運(yùn)算。1、補(bǔ)碼加法［X+丫卜卜=［X］補(bǔ)+［Y］補(bǔ)【例7】X=+0110011,Y=-0101001,求［X+Y］補(bǔ)［X］補(bǔ)=00110011［Y］補(bǔ)=11010111補(bǔ)補(bǔ)［X+Y］補(bǔ)=［X］補(bǔ)+［丫］補(bǔ)=00110011+11010111=00001010注：因?yàn)橛嬎銠C(jī)中運(yùn)算器的位長是固定的，上述運(yùn)算中產(chǎn)生的最高位進(jìn)位將丟掉，所以結(jié)果不是100001010，而是00001010。2、補(bǔ)碼減法匠丫］補(bǔ)=［X］補(bǔ)-［Y］補(bǔ)=［X］補(bǔ)+［-Y］補(bǔ)其中［-Y］補(bǔ)稱為負(fù)補(bǔ)，求負(fù)補(bǔ)的方法是：對補(bǔ)碼的每一位（包括符號位）求反，最后末位加“1”?！纠?】X=+0111001,Y=+1001101，求［X-Y］補(bǔ)［X］補(bǔ)=00111001［Y］補(bǔ)=01001101［-Y］補(bǔ)=10110011［X-Y］補(bǔ)=［X］補(bǔ)+［-丫］補(bǔ)=00111001+10110011=11101100五、數(shù)的表示圍通過上面的學(xué)習(xí)，我們就可以知道計算機(jī)如果用一個字節(jié)表示一個整數(shù)的時候，如果是無符號數(shù)，可以表示0~255共256個數(shù)(00000000~11111111)，如果是有符號數(shù)則能表示-128~127共256個數(shù)(10000000~01111111)。如果兩個字節(jié)表示一個整數(shù)，則共有65536個數(shù)可以表示，大部分程序設(shè)計語言中整數(shù)的圍都是-32768~32767的原因，可以看出這種整數(shù)類型是16位的有符號數(shù)，而且是補(bǔ)碼表示的。第四節(jié)浮點(diǎn)數(shù)的表示方法一、浮點(diǎn)數(shù)表示一個數(shù)的浮點(diǎn)形式(設(shè)基數(shù)是2)可寫成：N=Mx2E其中：M代表尾數(shù)江代表階碼。計算機(jī)中浮點(diǎn)數(shù)只用尾數(shù)和階碼表示，其形式如下：階碼尾數(shù)符號尾數(shù)浮點(diǎn)數(shù)的精度由尾數(shù)決定，數(shù)的表示圍由階碼的位數(shù)決定。為了最大限度提高精度，尾數(shù)采用規(guī)格化形式，既1/2WM<1。采用二進(jìn)制表示時，若尾數(shù)大于零，則規(guī)格化數(shù)應(yīng)該是01XXXX的形式；若尾數(shù)小于零，則規(guī)格化數(shù)應(yīng)為10XXXX的形式。二、機(jī)器零當(dāng)浮點(diǎn)數(shù)的尾數(shù)為0或階碼為最小值時，計算機(jī)通常把該數(shù)當(dāng)作零，因此程序中進(jìn)行浮點(diǎn)運(yùn)算時，判斷某數(shù)是否為零，通常可以用小于某個極小值來代替。三、實(shí)例【例1】設(shè)X=0.0110x23,用補(bǔ)碼、浮點(diǎn)數(shù)形式表示階碼為乂=011，尾數(shù)為00110，這時j由于乂尾數(shù)不符合01XXXX的形式，因此不是規(guī)格化數(shù)，必須先進(jìn)行規(guī)格化處理。方法：若尾數(shù)小于1/2，把尾數(shù)左移一位（不包括符號位），觀察結(jié)果是否滿足規(guī)格化條件，滿足則在把階碼減1即可，否則繼續(xù)左移和調(diào)整階碼；若尾數(shù)大于1，則把尾數(shù)右移一位（不包括符號位），觀察結(jié)果是否滿足規(guī)格化條件，滿足則在把階碼加1即可，否則繼續(xù)右移和調(diào)整階碼。上例中，00110左移一位為01100，符合規(guī)則化標(biāo)準(zhǔn)，此時階碼減1，為010即得到浮點(diǎn)表示形式。這個數(shù)具體在計算機(jī)中如何表示要看計算機(jī)中規(guī)定的階碼和尾數(shù)的位數(shù)，若階碼和尾數(shù)均為16位，則上面的數(shù)乂在計算機(jī)部表示就是00000000000000100110000000000000，不足均用零填充。第五節(jié)奇偶校驗(yàn)計算機(jī)中數(shù)據(jù)在進(jìn)行存儲和傳輸過程中可能會發(fā)生錯誤。為了及時發(fā)現(xiàn)和糾正這類錯誤，在數(shù)據(jù)傳輸（存儲）過程中要進(jìn)行校驗(yàn)，常用的校驗(yàn)方法就是奇偶校驗(yàn)。奇偶校驗(yàn)?zāi)馨l(fā)現(xiàn)一位或奇數(shù)位錯誤，且不能糾正錯誤。一般以字節(jié)（八位二進(jìn)制）為單位加1位奇偶校驗(yàn)位。奇偶校驗(yàn)分奇校驗(yàn)和偶校驗(yàn)兩種。一、奇校驗(yàn)：一個字節(jié)前面加一位校驗(yàn)位使得“1”的個數(shù)保持為奇數(shù)，若八位二進(jìn)制數(shù)中“1”的個數(shù)為偶數(shù)，則校驗(yàn)位為“1”；若八位二進(jìn)制數(shù)中“1”的個數(shù)為奇數(shù)，則校驗(yàn)位為“0”?！纠?】給1001100101101101加奇校驗(yàn)結(jié)果為110011001001101101二、偶校驗(yàn)：一個字節(jié)前面加一位校驗(yàn)位使得“1”的個數(shù)保持為偶數(shù)，若八位二進(jìn)制數(shù)中“1”的個數(shù)為偶數(shù)，則校驗(yàn)位為“0”；若八位二進(jìn)制數(shù)中“1”的個數(shù)為奇數(shù)，則校驗(yàn)位為“1”?！纠?】給1001100101101101加偶校驗(yàn)結(jié)果為010011001101101101第六節(jié)ASCII碼表目前使用最廣泛的西文字符集及其編碼是ASCII字符集和ASCII碼（ASCII是AmericanStandardCodeforInformationInterchange的縮寫），它同時也被國際標(biāo)準(zhǔn)化組織（InternationalOrganizationforStandardization,ISO）批準(zhǔn)為國際標(biāo)準(zhǔn)。基本的ASCII字符集共有128個字符，其中有96個可打印字符，包括常用的字母、數(shù)字、標(biāo)點(diǎn)符號等，另外還有32個控制字符。標(biāo)準(zhǔn)ASCII碼使用7個二進(jìn)位對字符進(jìn)行編碼，對應(yīng)的ISO標(biāo)準(zhǔn)為ISO646標(biāo)準(zhǔn)。下表展示了基本ASCII字符集及其編碼：字母和數(shù)字的ASCII碼的記憶是非常簡單的。我們只要記住了一個字母或數(shù)字的ASCII碼（例如記住A為65，0的ASCII碼為48），知道相應(yīng)的大小寫字母之間差32，就可以推算出其余字母、數(shù)字的ASCII碼。雖然標(biāo)準(zhǔn)ASCII碼是7位編碼，但由于計算機(jī)基本處理單位為字節(jié)（1byte=8bit），所以一般仍以一個字節(jié)來存放一個ASCII字符。每一個字節(jié)中多余出來的一位（最高位）在計算機(jī)部通常保持為0（在數(shù)據(jù)傳輸時可用作奇偶校驗(yàn)位）。由于標(biāo)準(zhǔn)ASCII字符集字符數(shù)目有限，在實(shí)際應(yīng)用中往往無法滿足要求。為此，國際標(biāo)準(zhǔn)化組織又制定了ISO2022標(biāo)準(zhǔn)，它規(guī)定了在保持與ISO646兼容的前提下將ASCII字符集擴(kuò)充為8位代碼的統(tǒng)一方法。ISO陸續(xù)制定了一批適用于不同地區(qū)的擴(kuò)充ASCII字符集，每種擴(kuò)充ASCII字符集分別可以擴(kuò)充128個字符，這些擴(kuò)充字符的編碼均為高位為1的8位代碼（即十進(jìn)制數(shù)128~255），稱為擴(kuò)展ASCII碼。下表展示的是最流行的一套擴(kuò)展ASCII字符集和編碼：

第二章計算機(jī)硬件基礎(chǔ)第一節(jié)中央處理器一、中央處理器的組成中央處理器簡稱CPU，由控制器、運(yùn)算器組成。一、中央處理器的組成中央處理器簡稱CPU，由控制器、運(yùn)算器組成。運(yùn)算器及控制器的基本功能：運(yùn)算器是計算機(jī)進(jìn)行算術(shù)和邏輯運(yùn)算的部件，控制器是整個計算機(jī)中統(tǒng)一指揮和控制計算機(jī)八控制、狀態(tài)信號線i一地址，數(shù)據(jù)信號線控制器-r*運(yùn)算器一寄存器組1泗J組成示意圖各部件進(jìn)行工作的控制中心。二、運(yùn)算器控制器由指令指針寄存器、指令寄存器、控制邏輯電路和時鐘控制電路等組成。指令指針寄存器（IP）用于 產(chǎn)生及存放一條待取指令的地址。指令寄存器用于存放指令。指令從存取出后放入指令寄存器。四、寄存器寄存器數(shù)量增多可以提高CPU運(yùn)行速度，但是不能太多，太多會使地址編碼和指令長度變長，增加復(fù)雜度。由累加器、通用寄存器組、狀態(tài)寄存器、指令寄存器、地址寄存器、其他寄存器等組成。五、指令基本格式單目運(yùn)算：操作碼地址碼二目運(yùn)算：操作碼第一地址第二地址六、尋址方式：CPU執(zhí)行指令時尋找數(shù)據(jù)地址的方式1、立即尋址：ADDAH,78其中ADD是操作碼，表示做加法；AH是寄存器名；78是個常數(shù)；該指令的意思是寄存器AH的值加上78。2、直接尋址：ADDAH,(78)78表示操作數(shù)的地址3、間接尋址：ADDAH,((78))78表示操作數(shù)地址的地址4、相對尋址：ADDAH,*78 *78表示本指令地址+78,78稱偏移量5、變址尋址：ADDAH,(DI+78)DI是變址寄存器，存放一個地址，操作數(shù)地址是寄存器地址+786、寄存器直接尋址:ADDAH,78AH是一個寄存器名，即寄存器直接尋址7、寄存器直接尋址:ADDAH,(BX)BX是一個寄存器名，存放操作數(shù)的地址七、指令分類1、數(shù)據(jù)傳送指令：MOVAH,BHINAH,3782、數(shù)據(jù)處理指令:算術(shù)運(yùn)算、邏輯運(yùn)算、移位、比較等3、程序控制指令：轉(zhuǎn)移、調(diào)用、返回4、狀態(tài)管理指令：中斷、屏蔽中斷八、指令的執(zhí)行過程1、CPU發(fā)出指令地址2、讀取指令3、指令送指令寄存器4、指令譯碼5、按指令操作碼執(zhí)行6、形成下條要執(zhí)行的指令的地址九、時鐘周期一個指令執(zhí)行的時間稱為指令周期計算機(jī)完成一個操作（如讀取指令等）所需時間稱為總線周期計算機(jī)中最基本的時間單位是時鐘周期，有CPU的主頻決定。第二節(jié)存儲器系統(tǒng)一、存儲器的分類分類方法名稱舉例按存儲介質(zhì)分半導(dǎo)體存儲器ROM^RAM（存）、閃存（優(yōu)盤）磁表面存儲器硬盤、軟盤、磁帶光存儲器CD-ROM、DVD-ROM按工作方式分隨機(jī)存儲器RAM（存）、硬盤、軟盤只讀存儲器ROM、CD-ROM順序存儲器磁帶

二、多層次存儲體系:如圖二、多層次存儲體系:如圖三、主存儲器1、特點(diǎn)：容量小、讀寫速度快、價格高2、編址方式：存儲容量與地址線條數(shù)相對應(yīng)，64M的存儲器至少需要26跟地址線(226=64M)注：我們目前的計算機(jī)大都是32位，也就是地址線條數(shù)有32條，所以其支持的最大存容量為4G3、分類：①隨機(jī)存儲器(RAM)：就是我們通常稱的存，主要參數(shù)是存儲容量和工作頻率。例如：一條64Mx8的存條表示該存條有64M個單元，每個單元8位。

②只讀存儲器（ROM）：只能讀不能寫，一般用于存放計算機(jī)啟動所需的最基本程序。③緩沖存儲器（Cache）：速度最快，一般集成于CPU中。四、輔助存儲器1、磁帶：順序存儲，一般只用在小型機(jī)以上的計算機(jī)中，用作數(shù)據(jù)備份。2、軟盤：目前常見的一般為3.5寸高密盤，容量為1.44MB，軟盤結(jié)構(gòu)如圖79點(diǎn)道露頭南孔 快門W.5英寸軟微結(jié)構(gòu)軟盤片外形示意圖79點(diǎn)道露頭南孔 快門W.5英寸軟微結(jié)構(gòu)軟盤片外形示意圖注意：盤面最外層的磁道稱為0磁道，0磁道如果損壞，則盤片報廢。3、硬盤：硬盤由多個盤面組成一個柱形結(jié)構(gòu)，其原來跟軟盤類似，但是磁道更多。4、光盤：利用光信號讀取或?qū)懭氲拇鎯ζ?。①CD-ROM：只讀，容量650MB左右，一倍速為150KB/s②DVD-ROM：只讀，容量4.7GB左右，一倍速為1200KB/s③CD-RW、DVD-RW：可擦寫的光盤，但必須專門的刻錄機(jī)。第三節(jié)輸入輸出系統(tǒng)一、輸入輸出控制方式1、程序查詢方式：軟件實(shí)現(xiàn)，效率低2、中斷方式：軟硬件結(jié)合實(shí)現(xiàn)中斷請求--＞中斷響應(yīng)--＞中斷處理--＞中斷返回3、直接存儲器訪問方式⑷乂人）：硬件實(shí)現(xiàn)DMA請求一＞CPU響應(yīng)并把總線控制權(quán)交給DMA控制器一＞數(shù)據(jù)交換一＞交還總線控制權(quán)二、系統(tǒng)總線分類：數(shù)據(jù)總線、地址總線、控制總線總線標(biāo)準(zhǔn)：ISA總線、PCI局部總線、MCA總線三、I/O接口1、顯卡：分辨率、顏色數(shù)決定顯示效果和所需顯存例如：顯示分辨率為1280x1024的32位真彩色，所需顯卡顯存最少為1280x1024x32:8=5MB2、硬盤接口：IDE、EIDEUltraDMASCSISATA3、串行口4、并行口：通常接針式打印機(jī)5、USB接口：通用串行總線四、顯示器的有關(guān)知識1、屏幕尺寸：15寸、17寸、19寸等

2、點(diǎn)間距：屏幕上象素與象素之間的距離，決定了顯示器能顯示的最大分辨率。越小表示能顯示的最大分辨率越大。五、打印機(jī)：針式打印機(jī)、噴墨打印機(jī)、激光打印機(jī)。激光打印機(jī)速度最快，針式打印機(jī)可以打印票據(jù)。第三章網(wǎng)絡(luò)基礎(chǔ)知識第一節(jié)網(wǎng)絡(luò)的組成與結(jié)構(gòu)一、網(wǎng)絡(luò)組成1、通信主體：服務(wù)器和工作站2、通信設(shè)備：傳輸介質(zhì)、網(wǎng)絡(luò)設(shè)備3、通信協(xié)議：通常是TCP/IP二、網(wǎng)絡(luò)分類按傳輸距離分：局域網(wǎng)（LAN）、城域網(wǎng)（MAN）、廣域網(wǎng)（WAN）按網(wǎng)絡(luò)結(jié)構(gòu)分：總線型、星型、環(huán)型、樹型三、網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)Qgg星型闕￥Qgg星型闕￥環(huán)型網(wǎng)V環(huán)型網(wǎng)V第二節(jié)網(wǎng)絡(luò)協(xié)議一、OSI網(wǎng)絡(luò)協(xié)議的層次國際標(biāo)準(zhǔn)化組織（ISO）提出的“開放系統(tǒng)互連模型（OSI）'是計算機(jī)網(wǎng)絡(luò)通信的基本協(xié)議。該協(xié)議分為七層。如下表亶國層應(yīng).用層應(yīng)用層域用層表達(dá)層表達(dá)層表達(dá)層表達(dá)層［會話層會話層■話層會話層傳輸層傳輸層傳輸層傳輸層二、網(wǎng)絡(luò)設(shè)備網(wǎng)絡(luò)層網(wǎng)貂層唯層網(wǎng)絡(luò)層極其作用數(shù)據(jù)陳路層數(shù)據(jù)的路層數(shù)據(jù)鏈路層網(wǎng)橋數(shù)據(jù)陳路層物理層物理層物理層物理層應(yīng)用層應(yīng)用層應(yīng)用層應(yīng)用層;表達(dá)層表達(dá)層慈達(dá)層表達(dá)層［會話層會話層會話層會話層傳輸層，傳端層據(jù)輸層?網(wǎng)天假輸層網(wǎng)絡(luò)層網(wǎng)絡(luò)層網(wǎng)絡(luò)層網(wǎng)絡(luò)層數(shù)據(jù)鑄路層路由器數(shù)據(jù)鏈路層數(shù)據(jù)鏈路層數(shù)據(jù)攘路層物理層物理層物理層物理層

第三節(jié)Internet相關(guān)知識一、IP地址每臺與Internet連接的主機(jī)都必須有一個IP地址，田地址采用分段式表示：共分4段，每段用一個字節(jié)即八個二進(jìn)制位表示，實(shí)際的IP把二進(jìn)制轉(zhuǎn)換成十進(jìn)制書寫。如61.153.238.132，因?yàn)槊慷螘r一個字節(jié)，因此IP每段的數(shù)字大小最大為255。IP地址分類如下表：目前32位IP地址資源幾近枯竭，有人提出用48位表示IP，即IPV6。分類二進(jìn)制表示十進(jìn)制表示第一段數(shù)字A類<128七位網(wǎng)絡(luò)地址24位主機(jī)地址B類14位網(wǎng)絡(luò)地址16位主機(jī)地址128?191C類192?223) 21位網(wǎng)絡(luò)地址8位主機(jī)地址二、域名：Internet的域名系統(tǒng)叫做DNS，DNS是樹形結(jié)構(gòu)的。域名跟田地址是多對一的關(guān)系1、域名分級系統(tǒng)：一個域名最右邊的部分通常叫頂級域名，往前依次為二級域名、三級域名等。2、我國域名管理機(jī)構(gòu)：CNNIC3、常見域名含義：gov政府edu教育int國際組織商業(yè)組織mil軍事部門net網(wǎng)絡(luò)運(yùn)行org其他組織中國hktwuk英國jp日本三、一些常見名詞解釋1、Intranet:企業(yè)部網(wǎng)2、ISP(InternetServiceProvider)：因特網(wǎng)服務(wù)供應(yīng)商3、ICP(InternetContentProvider)：因特網(wǎng)容供應(yīng)商4、IAP(InternetAcessProvider)：因特網(wǎng)接入供應(yīng)商，目前一般都被ISP包含5、BBS：電子公告欄，目前通常叫論壇四、接入Internet的方法1、PSTN撥號接入：必須設(shè)備MODEM，線，速度慢2、DDN專線接入：速度快，費(fèi)用高。3、ISDN專線接入：利用傳統(tǒng)網(wǎng)絡(luò)的綜合業(yè)務(wù)數(shù)字網(wǎng)。4、分組交換接入5、幀中繼接入第四章其他相關(guān)基礎(chǔ)知識第一節(jié)計算機(jī)病毒一、特點(diǎn)寄生性、隱蔽性、非法性、傳染性、破壞性二、分類：1、引導(dǎo)型病毒：寄生在系統(tǒng)引導(dǎo)區(qū)，比較容易被清除，現(xiàn)在已經(jīng)很少見。2、文件型病毒：寄生在可執(zhí)行文件中，感染速度快，較易清除。3、目錄型病毒：寄生在系統(tǒng)目錄結(jié)構(gòu)中4、混合型病毒：多種類型的混合5、宏病毒：專門感染MicrosoftOffice系列文件的病毒6、蠕蟲病毒：感染網(wǎng)絡(luò)，使網(wǎng)速大大降低。目前流行的病毒大多集成了黑客技術(shù)、木馬技術(shù)和病毒技術(shù)三種，非常難以清除而且很容易中。三、一些常見危害較大的病毒1、CIH病毒：文件型病毒，4月26日發(fā)作時破壞性最大，首個能破壞硬件系統(tǒng)的病毒。2、Melissa病毒：宏病毒，傳播3、沖擊波、震蕩波病毒：利用WINDOWS的漏洞，使計算機(jī)自動重啟并堵塞網(wǎng)絡(luò)。第二節(jié)數(shù)據(jù)庫系統(tǒng)一、數(shù)據(jù)庫是數(shù)據(jù)的一種組織形式，目前存儲大量數(shù)據(jù)基本都采用數(shù)據(jù)庫常見的數(shù)據(jù)庫軟件有：FoxBase、FoxPro、Access、SqlServer、MySql、Sybase、Oracel等。除了最早的如FoxBase等軟件，目前流行的數(shù)據(jù)庫軟件都是關(guān)系型數(shù)據(jù)庫。

二、數(shù)據(jù)庫數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)庫系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)可以認(rèn)為是多二維表，二維表中的列稱為字段，行存放數(shù)據(jù)。如下圖AtLtrss文件3】毋提?機(jī)圖⑼插入口）格■式⑼i曝依，工具⑺定口生:混”以他！當(dāng)4爭.,：t鳥m閨如,尋百號儂I眩^itjsdhTOtih:數(shù)據(jù)庫心「^itjsdhTOtih:數(shù)據(jù)庫心「e三密-la:|x|.國打開④?.以設(shè)計您j］籽建皿XI-b圣注堂使用設(shè)計離創(chuàng)建表使用向?qū)О北硗ㄟ^輪中據(jù)創(chuàng)建表adrinresDuicesinelcsrtudeiitLrifatestinf'：■UplDadfilE■虱ulgiliiilb;我_[xstidE'bL4JieECOTEene.il telepho&.e l?atfvd&iefwaquilI使用設(shè)計離創(chuàng)建表使用向?qū)О北硗ㄟ^輪中據(jù)創(chuàng)建表adrinresDuicesinelcsrtudeiitLrifatestinf'：■UplDadfilE■虱ulgiliiilb;我_[xstidE'bL4JieECOTEene.il telepho&.e l?atfvd&iefwaquilI+20050311十20050J39*20050129+20050332+20050335+20050144十20050341特靈睦沈坦掛整冏盛帽輝.趙不到孫仕緊100itj3te3-te]63.cDmIE345678iaai七：門。出口183.口即izm“5E，Tg100iUN”/伯寵匚通癡阻兄TE；lUi:idstastfl103.GDI1E34KTU1Q1] 1E345藐iaa；Ue仆鐘伯3.口由也二亞7白gqa6-T-5L2:LL:5B2口口6-T-UT：5EJ：WW2I106-T-4L4：3D?3g2口口b-T-414:0L:1F如郎-TTH;A5;5D2i]O6-T-lL4:24:1D200506382005OSS4齒分虐田如此即除餓桓j盤;14II[li]0itjstfl3t0]83.ctifi——=(——?"="="--=—="—=——=~100itistest0]O3.cdh在6103561E34BBT8|2口口VT714：4±1』 工1E343BT0faaO-T-tL4:5B:DB0laaitjatcsieies.Epriiem汨花lai31七1久1(1伯由1R孤痂100 1E34見T8lai]缶二打辿肛皿1E345B而I-a|rfl共有記錄封；里EdillTTM;3L;4B20a&-T-4L4:5G:DG|2,aa6-T-313：SB：19gaafl-T-l￡0:54:4371&U二、數(shù)據(jù)操作用以對數(shù)據(jù)庫進(jìn)行檢索和更新（添加、刪除、更新等）操作三、數(shù)據(jù)的完整性約束條件多個表之間的數(shù)據(jù)可能存在相互關(guān)聯(lián)，必須保證其完整性四、數(shù)據(jù)庫操作語言SQL數(shù)據(jù)庫常用的操作語言稱為SQL語言，是一種更高級化的語言，只須告訴計算機(jī)做什么事情即可。下面例舉幾條常用的語句。1、SELECT語句語法：select〈列名〉from〈表名〉where〈條件》功能：從表中選出滿足條件的記錄列2、INSERT語句語法：insertinto〈表名》［（列名表）］values（〈值表〉）功能：在表中插入一條新記錄。3、DELETE語句語法：delete*from〈表名〉where〈條件》功能：刪除滿足條件的記錄4、UPDATE語句語法：update〈表名〉set＜列名＞=＜值＞where〈條件》功能：修改滿足條件的表中某記錄某字段的值第五章數(shù)據(jù)結(jié)構(gòu)之線性結(jié)構(gòu)第一節(jié)線性表一、概念線性表是指由有限個類型相同的數(shù)據(jù)元素組成的集合，它有以下的特點(diǎn)：1.有唯一的頭結(jié)點(diǎn)（即第一個數(shù)據(jù)元素）和尾結(jié)點(diǎn)（即最后一個數(shù)據(jù)元素）；2.除結(jié)點(diǎn)外，集合中的每個數(shù)據(jù)元素均只有一個前驅(qū)；3.除尾結(jié)點(diǎn)外，集合中的每一個數(shù)據(jù)元素均只有一個后繼。二、線性表的存儲結(jié)構(gòu)1、順序結(jié)構(gòu)：是通過數(shù)組說明分配連續(xù)地址的存儲區(qū)，通過下標(biāo)引用數(shù)組的相應(yīng)元素。2、鏈?zhǔn)浇Y(jié)構(gòu)：通過指引元素類型的變量對線性表中元素進(jìn)行動態(tài)分配存儲。三、順序存儲結(jié)構(gòu)1、一維數(shù)組①數(shù)組存儲的結(jié)構(gòu)在數(shù)組聲明時就需要事先分配相應(yīng)的連續(xù)存空間用來存放數(shù)據(jù)。②按首地址(表中第一個元素的地址)的位移來訪問數(shù)組每一個元素的。若第一個元素的地址是a，每個元素占用的存儲空間為L，則數(shù)組的第i個元素的地址可以用如下公式計算：d(i)=a+(i-1)*L2、二維數(shù)組定義方法：＜數(shù)組名＞:array[1..n,1..m]of＜元素類型〉對于行為n，列為m的二維數(shù)組的元素訪問方法： 若第一個元素的地址是a，每個元素占用的存儲空間為1，則數(shù)組的第(i,j)個元素的地址可以用如下公式計算：按行尋址：d(i,j)=a+(i-1)*m*L+(j-1)*L按列尋址：d(i,j)=a+(j-1)*n*L+(i-1)*L四、鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈表是這樣一種線性表，它的元素由數(shù)據(jù)和指針兩部分組成，數(shù)據(jù)部分存放結(jié)點(diǎn)的有關(guān)信息，指針部分存放下一個結(jié)點(diǎn)的位置。優(yōu)點(diǎn)何根據(jù)需要分配數(shù)據(jù)元素的存儲區(qū)，也可隨時撤消鏈表中數(shù)據(jù)元素的存儲區(qū)，插入刪除操作只須改變指針，無須移動數(shù)據(jù)。缺點(diǎn)：它的數(shù)據(jù)元素必須在數(shù)據(jù)項(xiàng)以外至少增加一個指向后繼元素的指針類型的數(shù)據(jù)項(xiàng)，查找其中的某個元素時必須中從第一個元素開始逐個往后找。一個實(shí)例：Typepointer=°node;node=Record;data:real;next:pointer;End;Varhead,next:pointer;head.Head為表的首指針，指向鏈表的第一個結(jié)點(diǎn)。.整個鏈表的存取必須從head指針出發(fā)，沿著每個結(jié)點(diǎn)的next指針順序進(jìn)行，最后個結(jié)點(diǎn)的next指針為“空”（nil）.第二節(jié)棧一、棧的概念棧是一種線性表，對它的插入和刪除操作都限制在表的同一端進(jìn)行。這一端叫做棧頂，另一個端叫做棧底。棧又被成為“后進(jìn)先出表“（LIFO）。beginbegin定義方法：Const山=棧元素的上限；Typestack=array[1..m]of＜元素類型＞Vars:stack;t:integer;二、棧的基本運(yùn)算.入棧：過程push(x)，往棧s中壓入一個元素x。procedurepush(x:〈元素類型》);beginift=mthenwriteln(‘overflow’)elsebegint:=t+1;s[t]:=x;end;end;.出棧：函數(shù)pop(x)，從棧s中彈出一個元素。functionpop:〈元素類型〉；ift=0thenwriteln('empty')elsebeginpop:=s[t];t:=t-1;end;end;.讀棧頂元素：函數(shù)top，讀取棧s的棧頂元素。functiontop:〈元素類型〉；beginift=0thenwriteln('empty')elsetop:=s[t];end;第三節(jié)隊列一、棧的概念隊列是從日常生活中的排隊抽象出來的，根據(jù)排隊的原則“先來先服務(wù)”。所謂隊列就是允許在一端進(jìn)行插入，另一端進(jìn)行刪除的線性表。允許插入的一端稱為隊尾，通常用一個隊尾指針「指向隊尾元素；允許刪除的一端稱為隊首，通常也用一個隊首指針f指向排頭元素的前面。初始時，f=r=0。隊列又稱為“先進(jìn)先出(FIFO)"線性表。定義方法：Constelsebeginelsebegin川二隊列元素上限;Typeduilie=array[1..m]of＜元素類型＞;Varq:duilie;r,f:integer;二、隊列的基本運(yùn)算.過程add(x):隊列q插入元素xProcedureadd(x:integer);beginifr=mthenwriteln(‘overflow’)elsebeginr:=r+1;q[r]:=x;end;end;.過程del(x):取出隊列q的隊首元素yProceduredel(vary:integer);beginiff=rthenwriteln(‘empty’)f:=f+1;y：=q[f]；end;end;第六章數(shù)據(jù)結(jié)構(gòu)之非線性結(jié)構(gòu)第一節(jié)樹的概念一、樹的定義樹是一種常見的非線性的數(shù)據(jù)結(jié)構(gòu)。樹的定義：樹是n（n>0）個結(jié)點(diǎn)的有限集，這個集合滿足以下條件：⑴有且僅有一個結(jié)點(diǎn)沒有前驅(qū)（父親結(jié)點(diǎn)），該結(jié)點(diǎn)稱為樹的根；⑵除根外，其余的每個結(jié)點(diǎn)都有且僅有一個前驅(qū)；⑶除根外，每一個結(jié)點(diǎn)都通過唯一的路徑連到根上。這條路徑由根開始，而未端就在該結(jié)點(diǎn)上，且除根以外，路徑上的每一個結(jié)點(diǎn)都是前一個結(jié)點(diǎn)的后驅(qū)（兒子結(jié)點(diǎn)）；在樹中，一個結(jié)點(diǎn)包含一個元素以及所有指向其子樹的分支。結(jié)點(diǎn)一般分成三類:⑴根結(jié)點(diǎn)：沒有前驅(qū)的結(jié)點(diǎn)。在樹中有且僅有一個根結(jié)點(diǎn)。如上圖（b）中的r；⑵分支結(jié)點(diǎn)：除根結(jié)點(diǎn)外，有后驅(qū)的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)。如上圖（b）中的a，b，c，x，t，d，i。分支結(jié)點(diǎn)亦是其子樹的根；⑶葉結(jié)點(diǎn)：沒有后驅(qū)的結(jié)點(diǎn)稱為樹葉。如上圖（b）中的w，h，e，f，s，m，o，n，j，u為葉結(jié)點(diǎn)。由樹的定義可知，樹葉本身也是其父結(jié)點(diǎn)的子樹。 根結(jié)點(diǎn)到每一個分支結(jié)點(diǎn)或葉結(jié)點(diǎn)的路徑是唯一的。例如上圖（b）中，從根r到結(jié)點(diǎn)i的唯一路徑為rcti。三、有關(guān)度的定義⑴結(jié)點(diǎn)的度：一個結(jié)點(diǎn)的子樹數(shù)目稱為該結(jié)點(diǎn)的度。在上圖（b）中，結(jié)點(diǎn)i度為3，結(jié)點(diǎn)t的度為2，結(jié)點(diǎn)b的度為1。顯然，所有樹葉的度為0。⑵樹的度：所有結(jié)點(diǎn)中最大的度稱為該樹的度。圖（b）中的樹的度為3。四、樹的深度（高度）樹是分層次的。結(jié)點(diǎn)所在的層次是從根算起的。根結(jié)點(diǎn)在第一層，根的后件在第二層，其余各層依次類推。即若某個結(jié)點(diǎn)在第k層，則該結(jié)點(diǎn)的后件均處在第k+1層。圖（b）中的樹共有五層。在樹中，父結(jié)點(diǎn)在同一層的所有結(jié)點(diǎn)構(gòu)成兄弟關(guān)系。樹中最大的層次稱為樹的深度，亦稱高度。圖（b）中樹的深度為5。五、森林所謂森林，是指若干棵互不相交的樹的集合。如圖（6）去掉根結(jié)點(diǎn)r，其原來的三棵子樹Ta，Tb，Tc的集合仃@，Tb，Tc｝就為森林，這三棵子樹的具體形態(tài)如圖（c）。六、有序樹和無序樹

按照樹中同層結(jié)點(diǎn)是否保持有序性，可將樹分為有序樹和無序樹。如果樹中同層結(jié)點(diǎn)從左而右排列，其次序不容互換，這樣的樹稱為有序樹；如果同層結(jié)點(diǎn)的次序任意，這樣的樹稱為無序樹。第二節(jié)樹的表示方法和存儲結(jié)構(gòu)一、樹的表示方法樹的表示方法一般有兩種：⑴自然界的樹形表示法：用結(jié)點(diǎn)和邊表示樹，例如下圖采用的就是自然界的樹形表示法。樹形表示法一般用于分析問題。⑵括號表示法：先將根結(jié)點(diǎn)放入一對圓括號中，然后把它的子樹按由左而右的順序放入括號中，而對子樹也采用同樣方法處理：同層子樹與它的根結(jié)點(diǎn)用圓括號括起來，同層子樹之間用逗號隔開，最后用閉括號括起來。例如下圖（2可寫成如下形式（r（a（w，x（d（h），e）），b（f），c（s，t（i（m，o，n），j），u）））Cb）二、樹的存儲結(jié)構(gòu)樹的存儲結(jié)構(gòu)一般有兩種一箱一層 T.Tb■二Cb）二、樹的存儲結(jié)構(gòu)樹的存儲結(jié)構(gòu)一般有兩種一箱一層 T.Tb■二Af&一則層00 ?―第五層?（5GXD1.靜態(tài)的記錄數(shù)組所有結(jié)點(diǎn)存儲在一個數(shù)組中，數(shù)組元素為記錄類型，包括數(shù)據(jù)域和長度為n(n為樹的度)的數(shù)組，分別存儲該結(jié)點(diǎn)的每一個兒子的下標(biāo)。Constn=樹的度；max=結(jié)點(diǎn)數(shù)的上限；Typenode=recorddata:＜數(shù)據(jù)類型＞；｛數(shù)據(jù)域｝sch：array[1^n]ofinteger；｛指向各兒子的下標(biāo)｝end；treetype=array[1..max]ofnode；Vartree：treetype；該圖用靜態(tài)數(shù)組方法保存如右表下標(biāo)數(shù)據(jù)域tree[i].data該圖用靜態(tài)數(shù)組方法保存如右表下標(biāo)數(shù)據(jù)域tree[i].data兒子的下標(biāo)序列tree[i].ch1r2342a5603b7004c89105w0006x111202.動態(tài)的多重鏈表由于樹中結(jié)點(diǎn)可以有多個元素，所以可以用多重鏈表來描述比較方便。所謂多重鏈表，就是每個結(jié)點(diǎn)由數(shù)據(jù)域和n（n為樹的度）個指針域共n+1個域組成，其表示方法如下：treetype=°node；node=recorddata:datatype；｛數(shù)據(jù)域｝next：array[1^n]oftreetype；｛指向各兒子的指針域｝end；Varroot：treetype；上圖用多重鏈表表示如下：(A-nil)第三節(jié)二叉樹的概念一、二叉樹的遞歸定義和基本形態(tài).二叉樹是一種很重要的非線性數(shù)據(jù)結(jié)構(gòu)，它的特點(diǎn)是每個結(jié)點(diǎn)最多有兩個后繼，且其子樹有左右之分（次序不能任意顛倒）。.二叉樹是以結(jié)點(diǎn)為元素的有限集，它或者為空，或者滿足以下條件：⑴有一個特定的結(jié)點(diǎn)稱為根；（2）余下的結(jié)點(diǎn)分為互不相交的子集L和R，其中L是根的左子樹；R是根的右子樹；L和R又是二叉樹；由上述定義可以看出，二叉樹和樹是兩個不同的概念：⑴樹的每一個結(jié)點(diǎn)可以有任意多個后繼，而二叉樹中每個結(jié)點(diǎn)的后繼不能超過2；⑵樹的子樹可以不分次序（除有序樹外）；而二叉樹的子樹有左右之分。我們稱二叉樹中結(jié)點(diǎn)的左后繼為左兒子，右后繼為右兒子。.二叉樹的五種基本形態(tài)交二更樹只有一個根結(jié)點(diǎn)的二叉樹只有左子樹的二叉樹只有右孑掬的二叉樹左、右手相均有的二出樹二、二叉樹的兩個特殊形態(tài).滿二叉樹：如果一棵二叉樹的任何結(jié)點(diǎn)，或者是樹葉，或者恰有兩棵非空子樹，則此二叉樹稱作滿二叉樹。（例如下圖但））可以驗(yàn)證具有n個葉結(jié)點(diǎn)的滿二叉樹共有2n-1個結(jié)點(diǎn)。.完全二叉樹：如果一棵二叉樹最多只有最下面兩層結(jié)點(diǎn)度數(shù)可以小于2，并且最下面一層的結(jié)點(diǎn)都集中在該層最左邊的若干位置上，則稱此二叉樹為完全二叉樹（例如下圖（b））三、二叉樹的三個主要性質(zhì)性質(zhì)1：在二叉樹的第i(三1)層上，最多有2i-i個結(jié)點(diǎn)。性質(zhì)2：在深度為k(kN1)的二叉樹中最多有2k-1個結(jié)點(diǎn)。性質(zhì)3：在任何二叉樹中，葉子結(jié)點(diǎn)數(shù)總比度為2的結(jié)點(diǎn)多1。二叉樹的性質(zhì)(1)在二叉樹中，第i層的結(jié)點(diǎn)總數(shù)不超過2Xi-1)；(2)深度為h的二叉樹最多有2'-1個結(jié)點(diǎn)(h>=1)，最少有h個結(jié)點(diǎn)；(3)對于任意一棵二叉樹，如果其葉結(jié)點(diǎn)數(shù)為N0，而度數(shù)為2的結(jié)點(diǎn)總數(shù)為N2，則N0=N2+1；(4)具有n個結(jié)點(diǎn)的完全二叉樹的深度為int(log2n)+1(5)有N個結(jié)點(diǎn)的完全二叉樹各結(jié)點(diǎn)如果用順序方式存儲，則結(jié)點(diǎn)之間有如下關(guān)系：若I為結(jié)點(diǎn)編號則如果1<>1,則其父結(jié)點(diǎn)的編號為I/2；如果2*I<=N，則其左兒子(即左子樹的根結(jié)點(diǎn))的編號為2*1；若2*I>N，貝U無左兒子；如果2*I+1<=N，則其右兒子的結(jié)點(diǎn)編號為2*1+1；若2*I+1>N，則無右兒子。(6)給定N個節(jié)點(diǎn)，能構(gòu)成h(N)種不同的二叉樹。h(N)為卡特蘭數(shù)的第N項(xiàng)。h(n)=C(n,2*n)/(n+1)。四、普通有序樹轉(zhuǎn)換成二叉樹普通樹為有序樹丁，將其轉(zhuǎn)化成二叉樹T’的規(guī)則如下：⑴T中的結(jié)點(diǎn)與T’中的結(jié)點(diǎn)一一對應(yīng)，即T中每個結(jié)點(diǎn)的序號和值在丁中保持不變；⑵T中某結(jié)點(diǎn)v的第一個兒子結(jié)點(diǎn)為丫1，則在丁’中v1為對應(yīng)結(jié)點(diǎn)v的左兒子結(jié)點(diǎn)；⑶T中結(jié)點(diǎn)v的兒子序列，在丁’中被依次成一條開始于v1的右鏈；由上述轉(zhuǎn)化規(guī)則可以看出，一棵有序樹轉(zhuǎn)化成二叉樹的根結(jié)點(diǎn)是沒有右子樹的，并且除保留每個結(jié)點(diǎn)的最左分支外，其余分支應(yīng)去掉，然后從最左的兒子開始沿右兒子方向依次該結(jié)點(diǎn)的全部兒子。[a) Cb)五、森林轉(zhuǎn)換成二叉樹如果程棵互不相交的普遍有序樹組成了森林F={T1,…Tm}。我們可以按下述規(guī)則將森林F轉(zhuǎn)換成一棵二叉樹b={R，LB，RB}:⑴若F為空（m=0），則b為空樹；⑵若F非空（mK0），則b的根R即為森林中第一棵樹的根R（T1）；b的左子樹LB是從T1的根結(jié)點(diǎn)的子樹森林F1={T11,T12，…T1k}轉(zhuǎn)換而成的二叉樹；其右子樹RB是從森林F2={T2，T3，…，Tm}轉(zhuǎn)換成的二叉樹。第四節(jié)二叉樹的遍歷一、樹的存儲結(jié)構(gòu)1.順序存儲結(jié)構(gòu)將每個結(jié)點(diǎn)依次存放在一維數(shù)組中，用數(shù)組下標(biāo)指示結(jié)點(diǎn)編號，編號的方法是從根結(jié)點(diǎn)開始編號1,然后由左而右進(jìn)行連續(xù)編號。每個結(jié)點(diǎn)的信息包括⑴一個數(shù)據(jù)域（data）；⑵三個指針域，其中有父結(jié)點(diǎn)編號（prt）、左兒子結(jié)點(diǎn)編號（lch）和右兒子結(jié)點(diǎn)編號（rch）。滿二叉樹和完全二叉樹一般采用順序存儲結(jié)構(gòu)。Constm二樹中結(jié)點(diǎn)數(shù)上限；Typenode=record｛結(jié)點(diǎn)類型｝data:＜數(shù)據(jù)類型＞；｛數(shù)據(jù)值｝prt，lch，rch：0^m；｛父結(jié)點(diǎn)、左兒子、右兒子編號｝end；treetype=array[1^m]ofnode；｛二叉樹的順序表類型｝VarTree:treetype；｛二叉樹｝2.鏈?zhǔn)酱鎯Y(jié)構(gòu)對于一般的二叉樹，通常采用鏈?zhǔn)椒峙?，即用二重鏈表表示一般的二叉樹。這種鏈?zhǔn)椒峙浼纯梢圆捎渺o態(tài)數(shù)據(jù)結(jié)構(gòu)（數(shù)組），又可以采用動態(tài)數(shù)據(jù)結(jié)構(gòu)（指針）。如果二叉樹的存儲需求量超過64Kb，則采用后者。由于二叉樹中每個結(jié)點(diǎn)通常包括數(shù)據(jù)元素和兩個分支。因此二叉樹對應(yīng)的二重鏈表中每個結(jié)點(diǎn)應(yīng)有三個域:⑴值域:data⑵左指針域：lch⑶右指針域：rch這種鏈表也稱為二叉鏈表。二叉鏈表頭指針bt指向二叉樹的根結(jié)點(diǎn)Typebitrpetr=「node；｛結(jié)點(diǎn)指針類型｝node=record｛結(jié)點(diǎn)類型｝data：＜數(shù)據(jù)類型＞；｛值域｝lch，rch：bitreptr；｛左指針域和右指針域｝end；Varbt：bitreptr；｛頭指針｝二、二叉樹的遍歷.二叉樹遍歷的定義按照一定的規(guī)律不重復(fù)地訪問（或取出結(jié)點(diǎn)中的信息，或?qū)Y(jié)點(diǎn)作其它的處理）二叉樹中的每一個結(jié)點(diǎn)。.二叉樹遍歷的順序如果用L、D、R分別表示遍歷左子樹、訪問根結(jié)點(diǎn)、遍歷右子樹，則對二叉樹的遍歷可以有下列六種（3!=6）組合：LDR、LRD、DLR、DRL、RDL、RLD。若再限定先左后右的次序，則只剩下三種組合：LDR（中序遍歷）、LRD（后序遍歷）、DLR（前序遍歷）。a以下遍歷以該樹為例三、前序遍歷規(guī)則如下：若二叉樹為空，則退出。否則⑴訪問處理根結(jié)點(diǎn)；⑵前序遍歷左子樹；⑶前序遍歷右子樹；如上圖的前序遍歷結(jié)果為abdehicfg順序結(jié)構(gòu)：Proceduepreorder(i:integer);beginifi<>0鏈?zhǔn)浇Y(jié)構(gòu)：Proceduepreorder(bt:bitreptr);beginifbt<>nilthenbegin訪問處理tree[i].data;preorder(tree[i].lch);｛遞歸遍歷左子樹｝preorder(tree[i].rch);｛遞歸遍歷右子樹｝end;end;thenbegin訪問處理bt^.data;preorder(bt-.lch);｛遞歸遍歷左子樹｝preorder(bt-.rch);｛遞歸遍歷右子樹｝end;end;四、中序遍歷規(guī)則如下：若二叉樹為空，則退出；否則⑴中序遍歷左子樹；⑵訪問處理根結(jié)點(diǎn)；⑶中序遍歷右子樹；如上圖的中序遍歷結(jié)果為dbheiafcg順序結(jié)構(gòu)：Procedueinorder(i:integer);beginifi<>0thenbegininorder(tree[i].lch);｛遞歸遍歷左子樹｝訪問處理tree[i].data;inorder(tree[i].rch);｛遞歸遍歷右子樹｝end;end;鏈?zhǔn)浇Y(jié)構(gòu)：Procedueinorder(bt:bitreptr);beginifbt<>nilthenbegininorder(bt-.lch);｛遞歸遍歷左子樹｝訪問處理bt^.data;inorder(bt-.rch);｛遞歸遍歷右子樹｝end;end;五、后序遍歷規(guī)則如下：若二叉樹為空，則退出；否則⑴后序遍歷左子樹；⑵后序遍歷右子樹；

⑶訪問處理根結(jié)點(diǎn)；如上圖的后序遍歷結(jié)果為dhiebfgca順序結(jié)構(gòu)：Proceduepostorder(i:integer);順序結(jié)構(gòu)：Proceduepostorder(i:integer);beginifi<>0thenbeginpostorder(tree[i].lch);｛遞歸遍歷左子樹｝postorder(tree[i].rch);｛遞歸遍歷右子樹｝訪問處理tree[i].data;end;end;鏈?zhǔn)浇Y(jié)構(gòu)：Proceduepostorder(bt:bitreptr);beginifbt<>nilthenbeginpostorder(bt-.lch);｛遞歸遍歷左子樹｝postorder(bt-.rch);｛遞歸遍歷右子樹｝訪問處理bt^.data;end;end;第五節(jié)普通樹的遍歷一、先根次序遍歷樹規(guī)則：若樹為空，則退出；否則先根訪問樹的根結(jié)點(diǎn)，然后先根遍歷根的每棵子樹。上圖先根遍歷次序?yàn)閞awxdhebfcstimonju當(dāng)普遍有序樹轉(zhuǎn)化為二叉樹時，可借用二叉樹的前序遍歷實(shí)現(xiàn)普遍有序樹的先根遍歷。二、后根次序遍歷樹規(guī)則：若樹為空，則退出；否則先依次后根遍歷每棵子樹，然后訪問根結(jié)點(diǎn)。上圖后根遍歷次序?yàn)閣hdexafbsmonijtucr當(dāng)普遍有序樹轉(zhuǎn)化為二叉樹時，可借用二叉樹的中序遍歷實(shí)現(xiàn)普遍有序樹的后根遍歷。三、森林的遍歷.先根遍歷森林若森林非空，則可按下述規(guī)則遍歷之①訪問森林中第一棵樹的根結(jié)點(diǎn)；先根遍歷第一棵樹中根結(jié)點(diǎn)的子樹森林；先根遍歷其余樹構(gòu)成的森林；若對下圖的森林進(jìn)行先根遍歷，則得到森林的先根序列為ABDCEFGHJI。森林的先根遍歷即為其對應(yīng)的二叉樹的前序遍歷。.后根遍歷森林若森林非空，則可按下述規(guī)則遍歷之①后根遍歷森林中第一棵樹的根結(jié)點(diǎn)的子樹森林；②訪問第一棵樹的根結(jié)點(diǎn)；③后根遍歷其余樹構(gòu)成的森林；若對上圖（a）中的森林進(jìn)行先根遍歷，則得到森林的后根序列為BCDAFEHJIG。森林的后根遍歷即為其對應(yīng)的二叉樹的中序遍歷。例如，對上圖（c）中的二叉樹進(jìn)行中序遍歷，亦可得出對應(yīng)森林（上圖（a）的后根遍歷序列。第六節(jié)根據(jù)兩種遍歷順序確定樹結(jié)構(gòu)一、由兩種順序確定樹結(jié)構(gòu)遍歷二叉樹有三種規(guī)則：前序遍歷：根—左子樹—右子樹；中序遍歷：左子樹—根—右子樹；后序遍歷：左子樹—右子樹—根；由于前序遍歷的第一個字符和后序遍歷的最后一個字符為根，中序遍歷中位于根左方的子串和位于根右方的子串分別反映了左子樹和右子樹的結(jié)構(gòu)，因此二叉樹的形態(tài)可以由其中序與后序或者前序與中序唯一確定。但無法反映左子樹和右子樹結(jié)構(gòu)的前序遍歷與后序遍歷卻不能做到這一點(diǎn)，因此這兩個遍歷順序可對應(yīng)多種二叉樹的形態(tài)。二、由中序遍歷與后序遍歷確定前序遍歷由二叉樹的遍歷規(guī)則可以看出，后序遍歷的最后一個字符為根，中序遍歷中位于該字符左側(cè)的子串為左子樹中序遍歷的結(jié)果；中序遍歷中位于該字符右側(cè)的子串為右子樹中序遍歷的結(jié)果。設(shè)中序遍歷s1='s「q后序遍歷s2='s1 sn'顯然，后序遍歷中的sn為二叉樹的根。按照前序遍歷的規(guī)則輸出sn。在中序遍歷中與5口相同的字符為sk。若k>1,說明左子樹存在，位于sk左側(cè)的子串s1…sk-1為左子樹中序遍歷的結(jié)果，后序遍歷中的前綴s1…sk-1為左子樹后序遍歷的結(jié)果；若k<n，說明右子樹存在，位于sk右側(cè)的子串為右子樹中序遍歷的結(jié)果；后序遍歷中的sk…sn-1為右子樹后序遍歷的結(jié)果。按照按照前序遍歷的規(guī)則分別遞歸二叉樹的左子樹和右子樹。proceduresolve1(s1,s2:string)；｛計算和輸出中序遍歷si和后序遍歷s2對應(yīng)的前序遍歷｝vark:integer；beginiflength(s2)=1 ｛若當(dāng)前子樹僅剩一個節(jié)點(diǎn)，則輸出｝thenwrite(s2)elsebegink:=pos(s2[length(s2)]，si)；｛在中序遍歷中尋找子樹根｝write(s1[k])；ifk>1 ｛若左子樹存在，則遞歸遍歷左子樹｝thensolve1(copy(s1，1，k-1)，copy(s2，1，k-1))；ifk<length(s1)｛若右子樹存在，則遞歸遍歷右子樹｝thensolve1(copy(s1，k+1，length(sl)-k)，copy(s2，k，length(s2)-k))；end；

end;三、由中序遍歷與前序遍歷確定后序遍歷原理同前，程序略微有些不同，看下面：proceduresolve2(s1,s2:string)；｛計算和輸出中序遍歷si和前序遍歷s2對應(yīng)的后序遍歷｝vark:integer；beginiflength(s2)=1 ｛若當(dāng)前子樹僅剩一個節(jié)點(diǎn)，則輸出｝thenwrite(s2)elsebegink:=pos(s2[1]，si)； ｛在中序遍歷中尋找子樹根｝ifk>1｛若左子樹存在，則遞歸遍歷左子樹｝ifk>1｛若左子樹存在，則遞歸遍歷左子樹｝thensolve2(copy(s1，1，k-1)，copy(s2，2，k-1))；ifk<length(s1)｛若右子樹存在，則遞歸遍歷右子樹｝thensolve2(copy(s1，k+1，length(si)-k)，copy(s2，k+1，length(s2)-k))；end；write(s1[k])；｛或者輸出子樹根s2[1]｝end;第七節(jié)二叉排序樹一、概念所謂二叉排序樹是指具有下列性質(zhì)的非空二叉樹⑴若根結(jié)點(diǎn)的左子樹不空，則左子樹的所有結(jié)點(diǎn)值均小于根結(jié)點(diǎn)值；⑵若根結(jié)點(diǎn)的右子樹不空，則右子樹的所有結(jié)點(diǎn)值均不小于根結(jié)點(diǎn)值；⑶根結(jié)的左右樹也分別為二叉排序樹；顯然，對二叉排序樹進(jìn)行中序遍歷，可得出結(jié)點(diǎn)值遞增的排序序列。｛假設(shè)待排序的數(shù)存在數(shù)組a中｝procedurecreatetree;beginfillchar(b，sizeof(b)，0);b[1].data:=a[1]; ｛二叉排序樹初始化｝fori:=2tondobeginb[i].data:=a[i];p:=1;whiletruedobeginifa[i]<b[p]-data{若a[i]<b[p]