計(jì)算機(jī)公共基礎(chǔ)蘭州城市學(xué)院計(jì)算機(jī)公共基礎(chǔ)知識(shí)數(shù)學(xué)學(xué)院自2006級(jí)本科生開(kāi)始以專業(yè)任選課的形式開(kāi)設(shè)本課程返回課程內(nèi)容：《算法與數(shù)據(jù)結(jié)構(gòu)》《軟件工程》《程序設(shè)計(jì)方法》《數(shù)據(jù)庫(kù)系統(tǒng)概論》開(kāi)設(shè)學(xué)期:第二學(xué)期課時(shí)：周2先修課程:《計(jì)算機(jī)應(yīng)用基礎(chǔ)Ⅰ》同步課程:《計(jì)算機(jī)應(yīng)用基礎(chǔ)Ⅱ》高級(jí)語(yǔ)言程序設(shè)計(jì)返回算法與數(shù)據(jù)結(jié)構(gòu)常用算法1.4

1.5習(xí)題演練

詳細(xì)設(shè)計(jì)軟件工程基礎(chǔ)2.5軟件測(cè)試軟件維護(hù)2.6

習(xí)題演練2.7

程序設(shè)計(jì)方法習(xí)題演練3.4

數(shù)據(jù)庫(kù)系統(tǒng)概論習(xí)題演練4.4

計(jì)算機(jī)等級(jí)考試大綱及模擬訓(xùn)練

信息技術(shù)概述所以，現(xiàn)代計(jì)算機(jī)的功能就是集數(shù)值計(jì)算、數(shù)據(jù)處理、數(shù)據(jù)傳輸為一體。返回?cái)?shù)據(jù)信息收集到的原始資料對(duì)人們的生產(chǎn)生活有決策價(jià)值主要指借助計(jì)算機(jī)處理返回三個(gè)概念：數(shù)據(jù)、信息、數(shù)據(jù)處理

數(shù)據(jù)：一些在描述對(duì)象的屬性等時(shí)用的符號(hào)。是使用約定俗成的關(guān)鍵字，對(duì)客觀事物的數(shù)量、屬性、位置及其相互關(guān)系進(jìn)行抽象表示，以適合在這個(gè)領(lǐng)域中用人工或自然的方式進(jìn)行保存、傳遞和處理。數(shù)據(jù)處理：計(jì)算機(jī)把存儲(chǔ)的數(shù)據(jù)通過(guò)分析、組織、設(shè)計(jì)等工作把數(shù)據(jù)處理成對(duì)人們的生產(chǎn)、生活有幫助的信息的過(guò)程。信息：是有一定含義的、經(jīng)過(guò)加工處理的、對(duì)決策有價(jià)值的數(shù)據(jù)。組織數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)算法數(shù)學(xué)模型分析返回結(jié)論：“最高分90”、“11號(hào)同學(xué)補(bǔ)考”、“總評(píng)成績(jī)排名”等數(shù)據(jù)信息返回第1章算法與數(shù)據(jù)結(jié)構(gòu)返回1.1算法的基本概念和特征

算法的基本概念返回算法是為解決一個(gè)問(wèn)題采取的方法和步驟，換句話說(shuō)，算法是為實(shí)現(xiàn)某個(gè)計(jì)算過(guò)程而規(guī)定的基本動(dòng)作的執(zhí)行序列。準(zhǔn)確地說(shuō)：算法是指解題方案的準(zhǔn)確而完整的描述。（是一組嚴(yán)謹(jǐn)?shù)囟x運(yùn)算順序的規(guī)則，并且每個(gè)規(guī)則都是有效的、明確的；此順序在有限的次數(shù)下終止。）算法分兩類---數(shù)值計(jì)算方法和非數(shù)值計(jì)算方法。返回實(shí)例1.1求兩個(gè)正整數(shù)m和n(m>n)的最大公約數(shù)。實(shí)例1.1求兩個(gè)正整數(shù)m和n(m>n)的最大公約數(shù)。在公元300年左右，歐幾里德就在其著作《幾何原本》中闡述了求解該問(wèn)題的方法和步驟：（1）用m對(duì)n求余，所得余數(shù)為r；（2）若r為0，則得到問(wèn)題的解為n，否則令m=n，n=r繼續(xù)步驟（1）。

解決該問(wèn)題的算法返回·有窮性·確定性·可行性·有零個(gè)或多個(gè)輸入·至少有一個(gè)輸出

算法的特征返回1.2算法的評(píng)價(jià)和算法的描述標(biāo)準(zhǔn)目的返回分為平均性態(tài)和最壞情況復(fù)雜性兩種方法返回實(shí)例1.2在長(zhǎng)度為n的順序表中查找值為x的數(shù)據(jù)的算法。其時(shí)間復(fù)雜度是？分析：平均性態(tài)下：A(n)=(1+n)/2最壞情況復(fù)雜性：W(n)=max{t(x)}=n返回算法的空間復(fù)雜度：執(zhí)行這個(gè)算法所需要的內(nèi)存空間。包括：算法程序所占的空間；輸入的初始數(shù)據(jù)所占的空間；算法執(zhí)行過(guò)程中需要的額外空間。返回算法的描述：（1）自然語(yǔ)言描述----如實(shí)例1中的算法描述（2）傳統(tǒng)程序流程圖描述---如圖（3）N-S結(jié)構(gòu)化流程圖(N-S圖)----如圖返回實(shí)例1.1求兩個(gè)正整數(shù)m和n(m>n)的最大公約數(shù)。在公元300年左右，歐幾里德就在其著作《幾何原本》中闡述了求解該問(wèn)題的方法和步驟：（1）用m對(duì)n求余，所得余數(shù)為r；（2）若r為0，則得到問(wèn)題的解為n，否則令m=n，n=r繼續(xù)步驟（1）。

解決該問(wèn)題的算法返回圖形符號(hào)符號(hào)名稱說(shuō)明起始、終止框表示算法的開(kāi)始或結(jié)束輸入、輸出框框中標(biāo)明輸入、輸出的內(nèi)容處理框框中標(biāo)明進(jìn)行什么處理判斷框框中標(biāo)明判定條件并在框外標(biāo)明判定后的兩種結(jié)果的流向流程線表示從某一框到另一框的流向連接點(diǎn)表示算法流向出口或入口連接點(diǎn)傳統(tǒng)流程圖所用的基本符號(hào)返回開(kāi)始

Yr=mmodnm=nn=r結(jié)束輸入整數(shù)m,nr=0?輸出m用流程圖描述算法N返回返回輸入m和nr=mmodnm=n,n=r直到r=0輸出m用N-S圖描述算法返回1.3數(shù)據(jù)結(jié)構(gòu)返回

引言：算法與數(shù)據(jù)結(jié)構(gòu)的聯(lián)系

隨著科學(xué)技術(shù)的發(fā)展，人們要求計(jì)算機(jī)處理和傳輸?shù)男畔⒘吭絹?lái)越大，結(jié)構(gòu)也越來(lái)越復(fù)雜，對(duì)數(shù)據(jù)結(jié)構(gòu)的研究越來(lái)越高，要求構(gòu)造和使用各種數(shù)據(jù)結(jié)構(gòu)。而任何一種類型的數(shù)據(jù)需要施加各種運(yùn)算必須通過(guò)算法實(shí)現(xiàn)，任何算法的選擇也要聯(lián)系著處理的對(duì)象和結(jié)果。返回?fù)Q句話說(shuō)，數(shù)據(jù)結(jié)構(gòu)和算法之間有著本質(zhì)的聯(lián)系。因此，算法與數(shù)據(jù)結(jié)構(gòu)應(yīng)該結(jié)合起來(lái)研究，以達(dá)到使計(jì)算機(jī)高效可靠地處理數(shù)據(jù)。著名計(jì)算機(jī)科學(xué)家N.Wirth曾提出下面的公式，指出了算法與數(shù)據(jù)結(jié)構(gòu)的密切聯(lián)系。返回一、幾個(gè)基本概念數(shù)據(jù)、數(shù)據(jù)類型、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)數(shù)據(jù)：對(duì)客觀事物屬性的符號(hào)表示；數(shù)據(jù)類型：一般分為數(shù)值型和非數(shù)值型；數(shù)據(jù)元素：數(shù)據(jù)的基本單位，在程序中經(jīng)常作為一個(gè)整體加以考慮和處理。數(shù)據(jù)元素一般具有完整、確定的實(shí)際意義，有時(shí)也成稱元素、結(jié)點(diǎn)、頂點(diǎn)或記錄；數(shù)據(jù)項(xiàng)：數(shù)據(jù)不可分割的最小單位，一個(gè)數(shù)據(jù)元素由若干個(gè)數(shù)據(jù)項(xiàng)組成；返回

非數(shù)值型數(shù)據(jù)

數(shù)值型數(shù)據(jù)ST2ST3ST4ST5ST6ST7ST1ST1(no,name,grade,class,score)數(shù)據(jù)元素?cái)?shù)據(jù)項(xiàng)返回

二、數(shù)據(jù)結(jié)構(gòu)概念數(shù)據(jù)結(jié)構(gòu)指反映數(shù)據(jù)元素之間關(guān)系的數(shù)據(jù)元素集合的表示。（即帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。）線性結(jié)構(gòu)樹(shù)型結(jié)構(gòu)圖型結(jié)構(gòu)返回

三、數(shù)據(jù)結(jié)構(gòu)的分類

根據(jù)數(shù)據(jù)結(jié)構(gòu)中各數(shù)據(jù)元素之間的前后件關(guān)系的復(fù)雜程度，一般將數(shù)據(jù)結(jié)構(gòu)分成兩大類型：線性結(jié)構(gòu)和非線性結(jié)構(gòu)。線性結(jié)構(gòu)非線性結(jié)構(gòu)返回?cái)?shù)據(jù)結(jié)構(gòu)主要研究三方面的內(nèi)容：（1）數(shù)據(jù)的邏輯結(jié)構(gòu)（2）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（3）對(duì)每種邏輯結(jié)構(gòu)的運(yùn)算的集合數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式。（也稱為數(shù)據(jù)的物理結(jié)構(gòu)）反映數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)返回返回返回按順序存儲(chǔ)按鏈接存儲(chǔ)1、順序表中的所有元素所占的存儲(chǔ)空間是連續(xù)的；2、順序表中各元素在存儲(chǔ)空間是按照邏輯順序依次存放的；3、順序存儲(chǔ)結(jié)構(gòu)要求邏輯上相鄰的元素物理上也相鄰。1、不需要連續(xù)的存儲(chǔ)空間存放數(shù)據(jù)元素；2、第i個(gè)元素的存儲(chǔ)空間中還存放著第i+1個(gè)元素的存放地址；3、方便于數(shù)據(jù)的插入與刪除。單鏈表雙鏈表循環(huán)鏈表返回一、線性結(jié)構(gòu)如果一個(gè)非空的數(shù)據(jù)結(jié)構(gòu)滿足下列兩個(gè)條件：（1）有且只有一個(gè)根結(jié)點(diǎn)；（2）每個(gè)結(jié)點(diǎn)最多有一個(gè)前件，也最多有一個(gè)后件。則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)。否之，則稱為非線性結(jié)構(gòu)。線性結(jié)構(gòu)有很多類型，如線性表、棧、隊(duì)列、線性鏈表等。

返回一、線性結(jié)構(gòu)----線性表

線性表是由n(n>=0)個(gè)數(shù)據(jù)元素a1,a2,…an組成的一個(gè)有限序列，表中每個(gè)元素除第一個(gè)外，有且只有一個(gè)前件，除最后一個(gè)外，有且只有一個(gè)后件。即

線性表或者是一個(gè)空表；或者表示為：(a1,a2,…,an),其中ai是數(shù)據(jù)對(duì)象的元素，即線性表中的一個(gè)結(jié)點(diǎn)。返回順序表存儲(chǔ)結(jié)構(gòu)示意圖設(shè)首元素a1的存放地址為L(zhǎng)OC(a1)（稱為首地址），

設(shè)每個(gè)元素占用存儲(chǔ)空間（地址長(zhǎng)度）為L(zhǎng)字節(jié)，

則表中任一數(shù)據(jù)元素的存放地址為：

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

LOC(ai+1)=LOC(ai)+L返回順序表結(jié)點(diǎn)的插入動(dòng)態(tài)演示33例：（35，12，24，42），在i=2的位置上插入33。435122442a1a2a3a4422412335什么時(shí)候不能插入？注意邊界條件返回例：（35,33,12,24,42），刪除i=2的數(shù)據(jù)元素。535a1a2a3a4422412334a5122442順序表結(jié)點(diǎn)的刪除動(dòng)態(tài)演示返回鏈表存儲(chǔ)結(jié)構(gòu)示意圖線性表（bat，cat，eat，fat，hat，jat，lat，mat）返回單鏈表結(jié)構(gòu)示意圖返回雙鏈表結(jié)構(gòu)示意圖返回循環(huán)鏈表結(jié)構(gòu)示意圖返回線性鏈表的特點(diǎn)與優(yōu)點(diǎn)：返回a2a1a4a5a6head單鏈表結(jié)點(diǎn)的插入動(dòng)態(tài)演示返回a2a1a4a5a6head單鏈表結(jié)點(diǎn)的刪除動(dòng)態(tài)演示返回12345先進(jìn)------后出返回棧二、線性結(jié)構(gòu)----棧先進(jìn)后出表（FILO）---特殊的線性表?xiàng)＃╯tack)是限定在一端進(jìn)行插入和刪除運(yùn)算的線性表。棧頂(top)a1a2…antop棧底(bottom)棧的運(yùn)算有進(jìn)棧、出棧、判斷棧是否空、判斷棧是否滿、讀棧頂元素等返回3、順序棧的定義：

利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，這種形式的棧稱為順序棧。

4、順序棧的存儲(chǔ)：

可以使用一維數(shù)組來(lái)作為棧的順序存儲(chǔ)空間。設(shè)指針top指向棧頂元素的當(dāng)前位置，以數(shù)組小下標(biāo)的一端作為棧底，通常以top=-1時(shí)為空棧，（有時(shí)也以top=0時(shí)為空棧）在元素進(jìn)棧時(shí)指針top不斷地加1，當(dāng)top等于數(shù)組的最大下標(biāo)值時(shí)則棧滿。5、順序棧的基本運(yùn)算：

（1）入棧：入棧運(yùn)算是指在棧頂插入一個(gè)新元素，其基本步驟是首先將棧頂指針進(jìn)一(即top加1)，然后將新元素插入到棧頂指針指向的位置。

當(dāng)棧頂指針已經(jīng)指向存儲(chǔ)空間的最后一個(gè)位置時(shí)，說(shuō)明棧頂空間已滿，不可能再進(jìn)行入棧操作，這種情況稱為棧“上溢”錯(cuò)誤。

（2）退棧：退棧運(yùn)算是指取出棧頂元素并賦給一個(gè)指定的變量，分兩個(gè)基本步驟進(jìn)行：首先將棧頂元素(棧頂指針指向的元素)賦給一個(gè)指定的變量，然后將棧頂指針退一(即top減1)。

當(dāng)棧頂指針為-1時(shí)，說(shuō)明?？眨豢赡茉龠M(jìn)行退棧操作，這種情況稱為?！跋乱纭卞e(cuò)誤。（3）讀棧頂元素：讀棧頂元素是指將棧頂元素賦給一個(gè)指定的變量。需要注意的是，這個(gè)運(yùn)算不刪除棧頂元素，只是將它的值賦給一個(gè)變量，因此，在這個(gè)運(yùn)算中，棧頂指針不會(huì)改變。當(dāng)棧頂指針為-1時(shí)，說(shuō)明?？眨x不到棧頂元素。棧的操作的示意圖三、線性結(jié)構(gòu)----隊(duì)列隊(duì)列（先進(jìn)先出FIFO）--特殊的線性表a1a2…an隊(duì)尾隊(duì)頭出隊(duì)入隊(duì)隊(duì)列的運(yùn)算有入隊(duì)、出隊(duì)、判斷隊(duì)是否空、判斷隊(duì)是否滿等返回2、隊(duì)列的定義：

隊(duì)列是—種只允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除的線性表。

3、順序隊(duì)列的定義：

隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)稱為順序隊(duì)列，它是利用一組地址連續(xù)的存儲(chǔ)單元依次存放隊(duì)列中的數(shù)據(jù)元素。4、順序隊(duì)列的存儲(chǔ)：

一般情況下，用一維數(shù)組來(lái)作為隊(duì)列的順序存儲(chǔ)空間，另外再設(shè)立兩個(gè)指示器：一個(gè)為指向隊(duì)頭元素位置的指示器front，另一個(gè)為指向隊(duì)尾的元素位置的指示器rear。5、順序隊(duì)列的基本運(yùn)算：

（1）入隊(duì)列：入隊(duì)列運(yùn)算是指在隊(duì)尾插入一個(gè)新元素，其基本步驟是首先將隊(duì)尾指針進(jìn)一(即rear加1)，然后將新元素插入到隊(duì)尾指針指向的位置。

（2）出隊(duì)列：出隊(duì)列運(yùn)算是指在隊(duì)頭刪除一個(gè)元素，其基本步驟是將隊(duì)頭指針進(jìn)一(即front加1)。

隊(duì)列的操作的示意圖6、循環(huán)隊(duì)列的定義：

將順序隊(duì)列的存儲(chǔ)區(qū)假想為一個(gè)環(huán)狀的空間，當(dāng)發(fā)生假溢出時(shí)，將新元素插入到第—個(gè)位置上，這樣做，雖然物理上隊(duì)尾在隊(duì)首之前，但邏輯上隊(duì)首仍然在前。入列和出列仍按“先進(jìn)先出”的原則進(jìn)行，這就是循環(huán)隊(duì)列。

7、循環(huán)隊(duì)列的操作的示意圖8、循環(huán)隊(duì)列的基本運(yùn)算：

用s來(lái)表示循環(huán)隊(duì)列的狀態(tài)，假設(shè)循環(huán)隊(duì)列的初始狀態(tài)為空，即：s=0,且front=rear=m。

（1）入隊(duì)列：入隊(duì)運(yùn)算是指在循環(huán)隊(duì)列的隊(duì)尾加入—個(gè)新元素。這個(gè)運(yùn)算有兩個(gè)基本操作：首先將隊(duì)尾指針進(jìn)一(即rear=rear+1)，并當(dāng)rear=m+l時(shí)置rear=1：然后將新元素插入到隊(duì)尾指針指向的位置。

當(dāng)循環(huán)隊(duì)列非空(s=1)且隊(duì)尾指針等于隊(duì)頭指針時(shí)，說(shuō)明循環(huán)隊(duì)列已滿，不能進(jìn)行入隊(duì)運(yùn)算，這種情況稱為“上溢”。

（2）出隊(duì)列：

退隊(duì)運(yùn)算是指在循環(huán)隊(duì)列的隊(duì)頭位置退出一個(gè)元素并賦給指定的變量。這個(gè)運(yùn)算有兩個(gè)基本操作：首先將隊(duì)頭指針進(jìn)一(即front=front+1)，并當(dāng)front=m+1時(shí)置front=1：然后將隊(duì)頭指針指向的元素賦給指定的變量。

當(dāng)循環(huán)隊(duì)列為空(s=0)，不能進(jìn)行退隊(duì)運(yùn)算，這種情況稱為“下溢”。

四、非線性結(jié)構(gòu)----樹(shù)（二叉樹(shù)）樹(shù)：樹(shù)是一種簡(jiǎn)單的非線性結(jié)構(gòu)。這種結(jié)構(gòu)中，所有元素之間的關(guān)系具有明顯的層次特性。ABCEFGhijklmklmm樹(shù)根返回

樹(shù)的定義樹(shù)是n(n>=0)個(gè)結(jié)點(diǎn)的有限集合。在任意一顆非空樹(shù)中：有且只有一個(gè)特定的稱為根的結(jié)點(diǎn)；當(dāng)n>1時(shí)，其余結(jié)點(diǎn)分為m(m>0)個(gè)互不相交的非空集合T1、T2、…Tm，其中每個(gè)集合本身又是一顆樹(shù)稱為根的子樹(shù)。樹(shù)的結(jié)構(gòu)示意圖如上圖。返回樹(shù)的幾個(gè)概念1、層：結(jié)點(diǎn)的層數(shù)從根算起，根的層數(shù)為1，其余結(jié)點(diǎn)的層數(shù)為其雙親的層數(shù)加1。2、深度：一棵樹(shù)中所有結(jié)點(diǎn)的層數(shù)的最大值稱為該樹(shù)的高度或深度。3、度：樹(shù)中某個(gè)結(jié)點(diǎn)的分支數(shù)（子樹(shù)的個(gè)數(shù)）稱為該結(jié)點(diǎn)的度。一棵樹(shù)中所有結(jié)點(diǎn)的度的最大值稱為該樹(shù)的度。返回結(jié)點(diǎn)的層數(shù)從根算起，根的層數(shù)為1，其余結(jié)點(diǎn)的層數(shù)為其雙親的層數(shù)加1。一棵樹(shù)中所有結(jié)點(diǎn)的層數(shù)的最大值稱為該樹(shù)的高度或深度。樹(shù)中某個(gè)結(jié)點(diǎn)的分支數(shù)（子樹(shù)的個(gè)數(shù)）稱為該結(jié)點(diǎn)的度。一棵樹(shù)中所有結(jié)點(diǎn)的度的最大值稱為該樹(shù)的度。度為0的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。若樹(shù)中結(jié)點(diǎn)A是結(jié)點(diǎn)B的直接前驅(qū)，則稱A為B的雙親或父結(jié)點(diǎn)稱B為A的孩子或子結(jié)點(diǎn)父結(jié)點(diǎn)相同的結(jié)點(diǎn)互稱為兄弟結(jié)點(diǎn)返回ABCEFGhijklmklmm根結(jié)點(diǎn)第1層第2層第3層第4層這棵樹(shù)的深度為4該結(jié)點(diǎn)的度為4該結(jié)點(diǎn)的度為1這棵樹(shù)的度為4返回五、非線性結(jié)構(gòu)----二叉樹(shù)返回

二叉樹(shù)：或者為空；或者只有一個(gè)根結(jié)點(diǎn)；或每一個(gè)結(jié)點(diǎn)最多有兩個(gè)子樹(shù)，稱為該結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)。1、二叉樹(shù)的定義返回二叉樹(shù)有5種基本形態(tài)，如下所示。(1)空二叉樹(shù)(2)只有根結(jié)點(diǎn)(3)只有左子樹(shù)(4)只有右子樹(shù)(5)左、右子樹(shù)都不空其中，左右子樹(shù)又都可以是任意一種形態(tài)的二叉樹(shù)。2、二叉樹(shù)的基本形態(tài)返回ABCEFGhij根結(jié)點(diǎn)左子樹(shù)右子樹(shù)第1層第2層第3層第4層該二叉樹(shù)的深度為4返回ABCEFGhij該結(jié)點(diǎn)的度為2該結(jié)點(diǎn)的度為1該結(jié)點(diǎn)的度為0返回ABEFhij下面所示是二叉樹(shù)嗎？ABEFhijhk返回3、二叉樹(shù)的性質(zhì)（1）在二叉樹(shù)的第k層上，最多有2k-1(k>=1)個(gè)結(jié)點(diǎn)。（2）深度為m(m>=1)的二叉樹(shù)最多有2m-1個(gè)葉子結(jié)點(diǎn)；總結(jié)點(diǎn)數(shù)最多2m-1個(gè)。（3）在任意一個(gè)二叉樹(shù)中，度為0的結(jié)點(diǎn)（葉子結(jié)點(diǎn)，無(wú)子樹(shù)）總是比度為2（有2棵子樹(shù)）的結(jié)點(diǎn)多一個(gè)。（4）具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，其深度至少為[log2n]+1，其中[]表示取整。返回4、滿二叉樹(shù)和完全二叉樹(shù)

性質(zhì)：1、第k（k>=1）層上有2k-1個(gè)結(jié)點(diǎn);

2、深度為m(m>=1)的滿二叉樹(shù)中共有個(gè)2m-1葉子結(jié)點(diǎn)；3、滿二叉樹(shù)中沒(méi)有度為1的結(jié)點(diǎn)。（1）滿二叉樹(shù)定義：一棵深度為m且有2m-1個(gè)結(jié)點(diǎn)的二叉樹(shù),稱為滿二叉樹(shù)。

返回深度為3的滿二叉樹(shù)示意圖12345678910若深度為4呢？1112131415深度為4的滿二叉樹(shù)示意圖每層結(jié)點(diǎn)數(shù)2k-11248總結(jié)點(diǎn)數(shù)：2m-115返回滿二叉樹(shù)的特點(diǎn)：除最后一層外，每一層上的所有結(jié)點(diǎn)的度都為2；最后一層結(jié)點(diǎn)的度都為0。即，每一層上的結(jié)點(diǎn)數(shù)都達(dá)到了最大值。

返回（2）完全二叉樹(shù)定義：完全二叉樹(shù)是在滿二叉樹(shù)的最后一層從右到左連續(xù)地刪除若干個(gè)結(jié)點(diǎn)所得到的二叉樹(shù)。

特點(diǎn)：除最后一層外，每一層上的結(jié)點(diǎn)數(shù)都達(dá)到最大值；最后一層上只缺少右邊的若干結(jié)點(diǎn)。返回顯然：滿二叉樹(shù)一定是完全二叉樹(shù)；而完全二叉樹(shù)不一定是滿二叉樹(shù)；512346789101112131415返回性質(zhì)：①、具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為。

②、設(shè)完全二叉樹(shù)共有n個(gè)結(jié)點(diǎn)。如果從根結(jié)點(diǎn)開(kāi)始，按層序（每一層從左到右）用自然數(shù)1，2，…n給結(jié)點(diǎn)進(jìn)行編號(hào)，則對(duì)于編號(hào)為k（k=1,2,…n）的結(jié)點(diǎn)有如下結(jié)論：

返回若k=1，則該結(jié)點(diǎn)為根結(jié)點(diǎn)，它沒(méi)有父結(jié)點(diǎn)；若k>1，則該結(jié)點(diǎn)的父結(jié)點(diǎn)編號(hào)為int(k/2)；若2k<=n，則編號(hào)為k的結(jié)點(diǎn)的左子結(jié)點(diǎn)編號(hào)為2k；否則，該結(jié)點(diǎn)無(wú)左子結(jié)點(diǎn)（也沒(méi)有右子結(jié)點(diǎn)）；若2k+1<=n，則編號(hào)為k的結(jié)點(diǎn)的右子結(jié)點(diǎn)編號(hào)為2k+1；否則，該結(jié)點(diǎn)無(wú)右子結(jié)點(diǎn)。依據(jù)此性質(zhì)可以求已知某結(jié)點(diǎn)的序號(hào)，問(wèn)其父結(jié)點(diǎn)或子女結(jié)點(diǎn)序號(hào)問(wèn)題返回5、二叉樹(shù)的遍歷二叉樹(shù)的遍歷:二叉樹(shù)的遍歷是二叉樹(shù)的一種基本運(yùn)算，指不重復(fù)的訪問(wèn)二叉樹(shù)中的所有結(jié)點(diǎn)。返回遞歸(在常用算法中講)知識(shí)鏈接返回前序遍歷（根左右）的遞歸算法：若二叉樹(shù)為空，則結(jié)束遍歷；否則（1）訪問(wèn)根結(jié)點(diǎn)（2）前序遍歷左子樹(shù)（3）前序遍歷右子樹(shù)中序遍歷（即左根右）后序遍歷（即左右根）返回1、前序遍歷演示（根左右）ABCDEFA根左右BDCEF返回2、中序遍歷演示（左根右）ABCDEFA根左右BDCEF返回3、后序遍歷演示（左右根）ABCDEFA根左右BDCEF返回練習(xí)1：寫出下列二叉樹(shù)的三種遍歷結(jié)果。ABCDFEG返回練習(xí)2：寫出下列二叉樹(shù)的三種遍歷結(jié)果。ABCDEGF返回思考：

根據(jù)以上例題和練習(xí)的結(jié)果，可以看出對(duì)同一個(gè)二叉樹(shù)，三種遍歷結(jié)果中，哪些結(jié)點(diǎn)的前后順序始終是不變的？返回6、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)在計(jì)算機(jī)中，二叉樹(shù)通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。返回二、非線性結(jié)構(gòu)----圖圖（Graph）是一種表樹(shù)更復(fù)雜的非線性結(jié)構(gòu)。圖中結(jié)點(diǎn)之間具有的網(wǎng)狀結(jié)構(gòu)，即結(jié)點(diǎn)之間的關(guān)系可以是任意的，任意兩個(gè)數(shù)據(jù)元素之間都可能相關(guān)。返回返回1.有向圖與無(wú)向圖若圖G中的每條邊都是有方向的，則稱G為有向圖；有向邊也稱為??；若圖G中的每條邊都是沒(méi)有方向的，則稱G為無(wú)向圖。123412345

(a)有向圖(b)無(wú)向圖2.完全圖對(duì)有n個(gè)頂點(diǎn)的圖，若為無(wú)向圖且邊數(shù)為n(n-1)/2，則稱其為無(wú)向完全圖；若為有向圖且邊數(shù)為n(n-1)，則稱其為有向完全圖。6.連通圖在無(wú)向圖G中，若兩個(gè)頂點(diǎn)之間有路徑存在，則稱是連通的。若G中任意兩個(gè)頂點(diǎn)都是連通的，則稱G是連通圖。若無(wú)向圖G有n個(gè)頂點(diǎn)，且是連通的，則圖G至少應(yīng)該有n-1條邊。1.4查找與排序返回一、查找的定義： 查找是指在一個(gè)給定的數(shù)據(jù)結(jié)構(gòu)中尋找某個(gè)指定的元素。

二、常用的查找方法： 1、順序查找 2、二分法查找三、順序查找：1、基本思路： 從表中的第一個(gè)元素開(kāi)始，將給定的值與表中逐個(gè)元素的關(guān)鍵字進(jìn)行比較，直到兩者相符，查到所要找的元素為止。否則就是表中沒(méi)有要找的元素，查找不成功。2、查找效率分析：3、順序查找的優(yōu)缺點(diǎn)：4、只能采用順序查找的情況：四、二分法查找：1、適用前提： 二分法查找又稱折半查找，它只適用于順序存儲(chǔ)的有序表。2、基本思路：

首先選取表中間位置的記錄，將其關(guān)鍵字與給定關(guān)鍵字k進(jìn)行比較，若相等，則查找成功；否則，若k值比該關(guān)鍵字值大，則要找的元素一定在表的后半部分(或稱右子表)，則繼續(xù)對(duì)右子表進(jìn)行折半查找：若k值比該關(guān)鍵字值小，則要找的元素一定在表的前半部分(左子表)，同樣應(yīng)繼續(xù)對(duì)左子表進(jìn)行折半查找。每進(jìn)行一次比較，要么找到要查找的元素，要么將查找的范圍縮小一半。如此遞推，直到查找成功或把要查找的范圍縮小為空(查找失敗)。3、基本方法：

設(shè)表的長(zhǎng)度為n，表的被查找部分的頭為low，尾為high，初始時(shí)，low=1，high=n，k為關(guān)鍵字的值，key為記錄的關(guān)鍵字值。(1)計(jì)算中間記錄的序號(hào)mid=(low+high)／2，取整數(shù)：(2)若k=r[mid]．key，成功，否則：

若k<r[mid]．key，

則high=mid-1，重復(fù)(1)：

若k>r[mid]．key，

則low=mid+l，重復(fù)(1)；

直到成功或不成功(此時(shí)low>high)。查找23和79的過(guò)程如下圖：mid=(low+high)/2不進(jìn)位取整(08,14,23,37,46,55,68,79,91)(08,14,23,37,46,55,68,79,91)lowhighmid(08,14,23,37,46,55,68,79,91)lowhigh=mid-1mid(08,14,23,37,46,55,68,79,91)low=mid+1highmid(08,14,23,37,46,55,68,79,

91)lowhighmid(08,14,23,37,46,55,68,79,91)lowhighmid(08,14,23,37,46,55,68,79,91)lowhighmid排序技術(shù)

一、排序的定義： 所謂排序是指將一個(gè)無(wú)序序列整理成按值非遞減順序排列的有序序列。二、常用的排序方法：

排序方法插入類排序選擇類排序交換類排序簡(jiǎn)單插入排序希爾排序

簡(jiǎn)單選擇排序堆排序起泡排序快速排序三、插入類排序：定義：插入排序是指將無(wú)序序列中的各元素依次插入到已經(jīng)有序的線性表中。

（一）、簡(jiǎn)單插入排序：1、算法思路： 初始可認(rèn)為文件中的第1個(gè)記錄己排好序，然后將第2個(gè)到第n個(gè)記錄依次插入已排序的記錄組成的文件中。

在對(duì)第i個(gè)記錄Ri進(jìn)行插入時(shí)，R1，R2，…，Ri-1，己排序，將記錄Ri的排序碼與已經(jīng)排好序的排序碼從右向左依次比較，找到Ri應(yīng)插入的位置，將該位置以后直到Ri-1各記錄順序后移，空出該位置讓Ri插入。

該算法適合于n較小的情況，時(shí)間復(fù)雜度為O(n2).待排元素序列：[53]2736156942第一次排序：[2753]36156942第二次排序：[273653]156942第三次排序：[15273653]6942第四次排序：[1527365369]42第五次排序：[152736425369]

直接插入排序示例對(duì)于有n個(gè)數(shù)據(jù)元素的待排序列，插入操作要進(jìn)行n-1次2、時(shí)效分析：

最好情況下，即初始排序碼開(kāi)始就是有序的情況下，簡(jiǎn)單插入排序算法的比較次數(shù)為(n-1)次，移動(dòng)次數(shù)為0次。

最壞情況下，即初始排序碼開(kāi)始是逆序的情況下，比較次數(shù)為n(n-1)／2，移動(dòng)次數(shù)為n(n—1)／2。 簡(jiǎn)單插入排序算法的時(shí)間復(fù)雜度為O(n2)。（二）、希爾排序：1、算法思路：1)選擇—個(gè)增量序列并按遞減排列：h1，h2，…，hk，并且hk=l；(2)按增量序列個(gè)數(shù)k，對(duì)待排序列進(jìn)行k趟排序：(3)每趟排序，根據(jù)對(duì)應(yīng)的增量hi將待排序列分割成若干子序列，分別對(duì)各子表進(jìn)行直接插入排序。當(dāng)增量序列為1時(shí)，整個(gè)序列作為一個(gè)表來(lái)處理，進(jìn)行一次插入排序。

希爾排序示例：2、時(shí)效分析：

希爾排序方法是一個(gè)不穩(wěn)定的排序方法，在最壞情況下，所需要的比較次數(shù)是O(n1.5)。四、交換類排序：定義：所謂交換類排序法是指借助數(shù)據(jù)元素之間的相互交換進(jìn)行排序的一種方法。（一）、冒泡排序

：1、算法思路：首先，從表頭(假設(shè)線性表的長(zhǎng)度為n)開(kāi)始往后掃描線性表，在掃描過(guò)程中逐次比較相鄰兩個(gè)元素的大小。若相鄰兩個(gè)元素中，前面的元素大于后面的元素，則將它們互換，稱為消去了一個(gè)逆序。顯然，在掃描過(guò)程中，不斷地將兩相鄰元素中的大者往最后移動(dòng)，最后就將線性表中的最大者換到了表的最后。

然后對(duì)剩下的n-1個(gè)待排序記錄重復(fù)上述過(guò)程，又將一個(gè)排序碼放在最終位置，反復(fù)進(jìn)行n-1次，可將n-1個(gè)排序碼對(duì)應(yīng)的記錄放至最終位置，剩下的即為排序碼最小的記錄，它在第一的位置上。 如果某一趟沒(méi)有發(fā)生交換，則排序結(jié)束。第六趟排序后第五趟排序后第四趟排序后第三趟排序后第二趟排序后第一趟排序后初始關(guān)鍵字思想：小的浮起，大的沉底。49364165117836653641563641654136415611783636414911564925252511494956111111252525252、時(shí)效分析：

若記錄的初始狀態(tài)已經(jīng)排好序，則關(guān)鍵字的比較次數(shù)是n-1，記錄的移動(dòng)次數(shù)是0，其時(shí)間復(fù)雜度是O(n)。若記錄的初始狀態(tài)是逆序時(shí)，即最壞情況下，其關(guān)鍵字的比較次數(shù)是(n+2)(n-1)／2，記錄的移動(dòng)次數(shù)是3n(n-1)／2，此時(shí)的時(shí)間復(fù)雜度是O(n2)。

冒泡排序是穩(wěn)定的排序，其時(shí)間復(fù)雜度為O(n2)。

（二）、快速排序

：1、算法思路：從n個(gè)待排序的記錄中任取一個(gè)記錄K(不妨取第1個(gè)記錄)，將K后小于K的記錄移到K前，而K前大于K的記錄放置于K后，使它前面的記錄排序碼都不大于它的排序碼，而后面的記錄排序碼都大于它的排序碼，這樣就以K為分界線，把記錄分成了兩個(gè)子表。然后對(duì)前、后兩部分待排序記錄重復(fù)上述過(guò)程，直到所有子表為空，排序完成。。

2、做法：

附設(shè)兩個(gè)指針low和high，初值分別指向第一個(gè)記錄和最后一個(gè)記錄，設(shè)關(guān)鍵字為key，首先從high所指位置起向前