計(jì)算機(jī)科學(xué)導(dǎo)論數(shù)據(jù)結(jié)構(gòu)與算法

計(jì)算機(jī)科學(xué)導(dǎo)論數(shù)據(jù)結(jié)構(gòu)與算法第1頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月理解數(shù)據(jù)結(jié)構(gòu)的概念，理解數(shù)據(jù)結(jié)構(gòu)的邏輯和存儲(chǔ)結(jié)構(gòu)；理解算法的概念和算法的基本特性，了解算法復(fù)雜度的度量方法；理解線性數(shù)據(jù)結(jié)構(gòu)，理解順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的存儲(chǔ)方法；描述棧和隊(duì)列、串和數(shù)組這幾個(gè)線性數(shù)據(jù)結(jié)構(gòu)的概念；了解非線性的數(shù)據(jù)結(jié)構(gòu)，了解樹(shù)、二叉樹(shù)以及圖的概念和數(shù)據(jù)結(jié)構(gòu)；理解排序的概念，描述插入、選擇、氣泡和快速排序的算法；理解查找的概念，描述順序查找和折半查找的算法，并能夠比較它們理解遞歸的概念，能夠在實(shí)踐中了解遞歸的應(yīng)用。

教學(xué)目的第2頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月學(xué)習(xí)重點(diǎn)數(shù)據(jù)結(jié)構(gòu)的基本概念算法的描述、流程圖的使用以及算法的復(fù)雜度的衡量順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的方法棧、隊(duì)列、串和數(shù)組的概念和用法二叉樹(shù)數(shù)據(jù)結(jié)構(gòu)查詢、排序和遞歸算法第3頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月第一節(jié)數(shù)據(jù)結(jié)構(gòu)概述第4頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月1.數(shù)據(jù)結(jié)構(gòu)概述1.1《數(shù)據(jù)結(jié)構(gòu)》研究的對(duì)象(1)對(duì)所加工的對(duì)象進(jìn)行邏輯組織(2)如何把加工對(duì)象存儲(chǔ)到計(jì)算機(jī)中去(3)數(shù)據(jù)運(yùn)算數(shù)據(jù)結(jié)構(gòu)正是討論非數(shù)值類問(wèn)題的對(duì)象描述、信息組織方法及其相應(yīng)的操作

[例5-1]設(shè)有一個(gè)電話號(hào)碼薄，有N個(gè)人的姓名和電話號(hào)碼。要求設(shè)計(jì)一個(gè)程序，按人名查找號(hào)碼，若不存在則給出不存在的信息。第5頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月1.數(shù)據(jù)結(jié)構(gòu)概述第6頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月1.2數(shù)據(jù)結(jié)構(gòu)相關(guān)概念1.基本概念和術(shù)語(yǔ)

數(shù)據(jù)元素、結(jié)點(diǎn)、數(shù)據(jù)項(xiàng)、關(guān)鍵字或主關(guān)鍵字、次關(guān)鍵字、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)

2.數(shù)據(jù)結(jié)構(gòu)

特性相同的數(shù)據(jù)元素構(gòu)成的集合中，如果在數(shù)據(jù)元素之間存在一種或多種特定的關(guān)系，則稱之為數(shù)據(jù)結(jié)構(gòu)。

Data-Structure=(D,R)

其中，D是數(shù)據(jù)元素的有限集，R是D上關(guān)系的有限集。1.數(shù)據(jù)結(jié)構(gòu)概述第7頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月1.數(shù)據(jù)結(jié)構(gòu)概述3.四類基本的數(shù)據(jù)結(jié)構(gòu)集合結(jié)構(gòu)。在集合結(jié)構(gòu)中，數(shù)據(jù)元素間的關(guān)系是“屬于同一個(gè)集合”。集合是元素關(guān)系極為松散的一種結(jié)構(gòu)，各元素間沒(méi)有直接的關(guān)聯(lián)。線性結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著一對(duì)一的關(guān)系。樹(shù)型結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著一對(duì)多的關(guān)系。圖形結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著多對(duì)多的關(guān)系，圖形結(jié)構(gòu)也稱作網(wǎng)狀結(jié)構(gòu)。

123456第8頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月[例5-2]線性數(shù)據(jù)結(jié)構(gòu)=(D,S)

D={1,2,3,4,5,6,7,8,9,10}

S={<1,2>,<2,3>,<3,4>,<4,5>,<5,6>,<6,7>,<7,8>,

<8,9>,<9,10>}

1.數(shù)據(jù)結(jié)構(gòu)概述第9頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月[例5-3]圖形數(shù)據(jù)結(jié)構(gòu)=(D,R)D={1,2,3,4,5,6,7,8,9}R={<1,2>,<1,3>,<2,4>,<2,5>,<2,6>,<2,8>,<3,2>,<3,4>,<4,5>,<5,7>,<6,7>,<6,9>,<7,9>,<8,9>}1.數(shù)據(jù)結(jié)構(gòu)概述第10頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月

[例5-4]樹(shù)形結(jié)構(gòu)=（D,R）D={a,b,c,d,e,f,g,h,i,j,k,l}R={<a,b>,<a,c>,<a,d>,<b,e>,<b,f>,<b,g>,<c,h>,<c,i>,<c,j>,<d,k>,<d,l>}1.數(shù)據(jù)結(jié)構(gòu)概述第11頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月1.3數(shù)據(jù)結(jié)構(gòu)的分類

1、按數(shù)據(jù)結(jié)構(gòu)的性質(zhì)劃分

數(shù)據(jù)的邏輯結(jié)構(gòu)——數(shù)據(jù)元素之間的邏輯關(guān)系（設(shè)計(jì)算法——

數(shù)學(xué)模型）數(shù)據(jù)的物理結(jié)構(gòu)——數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的映像（存儲(chǔ)結(jié)構(gòu)，算法的實(shí)現(xiàn)）

2、按數(shù)據(jù)結(jié)構(gòu)的操作來(lái)劃分

靜態(tài)結(jié)構(gòu)——經(jīng)過(guò)操作后，數(shù)據(jù)的結(jié)構(gòu)特征保持不變（如數(shù)組）。

半靜態(tài)結(jié)構(gòu)——經(jīng)過(guò)操作后，數(shù)據(jù)的結(jié)構(gòu)特性只允許很小變遷（如棧、隊(duì)列）。

動(dòng)態(tài)結(jié)構(gòu)——經(jīng)過(guò)操作后，數(shù)據(jù)的結(jié)構(gòu)特性變化比較靈活，可隨機(jī)地重新組織結(jié)構(gòu)（如指針）。1.數(shù)據(jù)結(jié)構(gòu)概述第12頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月1.3數(shù)據(jù)結(jié)構(gòu)的分類

3、按數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)的存儲(chǔ)方式來(lái)劃分

順序存儲(chǔ)結(jié)構(gòu)——借助元素在存儲(chǔ)器的相對(duì)位置來(lái)表示數(shù)據(jù)元素之的邏輯關(guān)系。

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——借助指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系

索引存儲(chǔ)結(jié)構(gòu)——在存儲(chǔ)結(jié)點(diǎn)的同時(shí)，建立附加的索引表，索引表中的每一項(xiàng)稱為索引項(xiàng)，形式為：關(guān)鍵字，地址。

散列存儲(chǔ)結(jié)構(gòu)——根據(jù)結(jié)點(diǎn)的關(guān)鍵字直接計(jì)算出該結(jié)點(diǎn)的存儲(chǔ)地址。說(shuō)明：四種存儲(chǔ)方法可結(jié)合起來(lái)對(duì)數(shù)據(jù)結(jié)構(gòu)進(jìn)行存儲(chǔ)映像。1.數(shù)據(jù)結(jié)構(gòu)概述第13頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月1.4算法及其描述和算法分析

1、算法的概念及特征

算法:

對(duì)問(wèn)題求解的描述，為解決問(wèn)題給出的一個(gè)確定的、有限長(zhǎng)的操作序列。

算法具有以下五個(gè)重要的特征：

1）有窮性：一個(gè)算法必須保證執(zhí)行有限步之后結(jié)束。

2）確切性：算法的每一步驟必須有確切的定義。

3）輸入：一個(gè)算法有0個(gè)或多個(gè)輸入，以刻畫(huà)運(yùn)算對(duì)象的初始情況，所謂0個(gè)輸入是指算法本身定除了初始條件。

4）輸出：一個(gè)算法有一個(gè)或多個(gè)輸出，以反映對(duì)輸入數(shù)據(jù)加工后的結(jié)果。沒(méi)有輸出的算法沒(méi)有實(shí)際意義。

5）可行性：算法原則上能夠精確地運(yùn)行，而且人們用筆和紙做有限次運(yùn)算后即可完成。1.數(shù)據(jù)結(jié)構(gòu)概述第14頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月1.4算法及其描述和算法分析

2、算法的描述:

1）流程圖

2）偽代碼——類程序設(shè)計(jì)語(yǔ)言

3、算法的基本結(jié)構(gòu):

1）順序結(jié)構(gòu)

2）分支結(jié)構(gòu)

3）循環(huán)結(jié)構(gòu)1.數(shù)據(jù)結(jié)構(gòu)概述第15頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月1.數(shù)據(jù)結(jié)構(gòu)概述

算法基本結(jié)構(gòu)示意圖第16頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月1.4算法及其描述和算法分析

4、算法效率衡量方法與準(zhǔn)則:

時(shí)間復(fù)雜度：指算法從開(kāi)始執(zhí)行到處理結(jié)束所需要的總時(shí)間。

T（n）=O（f(n)）

空間復(fù)雜度：指算法從開(kāi)始執(zhí)行到處理結(jié)束所需的存儲(chǔ)量空間的總和。

S（n）=O（g(n)）1.數(shù)據(jù)結(jié)構(gòu)概述第17頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月1.4算法及其描述和算法分析

5、算法與數(shù)據(jù)結(jié)構(gòu)的關(guān)系:計(jì)算機(jī)科學(xué)家沃斯（N.Wirth）提出的:“算法+數(shù)據(jù)結(jié)構(gòu)=程序”揭示了程序設(shè)計(jì)的本質(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)是互相依賴、互相聯(lián)系的。一個(gè)算法總是建立在一定數(shù)據(jù)結(jié)構(gòu)上的；反之，算法不確定，就無(wú)法決定如何構(gòu)造數(shù)據(jù)。1.數(shù)據(jù)結(jié)構(gòu)概述第18頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月第二節(jié)線性結(jié)構(gòu)第19頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月2.1線性表

1.線性表的定義

線性表是n(n>=0)個(gè)數(shù)據(jù)元素的有限序列，表中各個(gè)元素具有相同的屬性，表中相鄰元素間存在“序偶”關(guān)系。 記做：(a1,a2,…….ai-1,ai,ai+1,…,an-1,an)

其中，ai-1稱為ai

的直接前驅(qū)元素，ai+1是ai的直接后繼元素

線性表的長(zhǎng)度：表中的元素個(gè)數(shù)n

位序：i稱元素ai在線性表中的位序2.線性結(jié)構(gòu)第20頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月2.1線性表

2.線性表的順序表示和實(shí)現(xiàn)

線性表的順序存儲(chǔ)是指在內(nèi)存中用地址連續(xù)的一塊存儲(chǔ)空間順序存放線性表的各元素，用這種存儲(chǔ)形式存儲(chǔ)的線性表稱其為順序表。

2.線性結(jié)構(gòu)第21頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月2.1線性表

2.線性表的順序表示和實(shí)現(xiàn)

順序表——線性表的順序存儲(chǔ)表示

ConstLIST_INIT_SIZE=100;(C++規(guī)范) ConstLISTINCREMENT=10; #defineLIST_INIT_SIZE100(C規(guī)范) TypedefStruct{ Elemtype *elem; Int length; Int listsize; Int incrementsize; }SqList;2.線性結(jié)構(gòu)第22頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月2.線性結(jié)構(gòu)第23頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月2.1線性表3.線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)

鏈表是通過(guò)一組任意的存儲(chǔ)單元來(lái)存儲(chǔ)線性表中的數(shù)據(jù)元素的，為建立起數(shù)據(jù)元素之間的關(guān)系，對(duì)每個(gè)數(shù)據(jù)元素ai，除了存放數(shù)據(jù)元素的自身的信息ai之外，還需要和ai一起存放其后繼ai+1所在的存貯單元的地址，這兩部分信息組成一個(gè)“節(jié)點(diǎn)”。2.線性結(jié)構(gòu)第24頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月2.1線性表

3.線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)

單鏈表——線性表的鏈?zhǔn)酱鎯?chǔ)表示

數(shù)據(jù)域（data）和指針域（next）存儲(chǔ)表示

typedefstructLnode{ ElemType data; StructLnode *next; }Lnode,*LinkList;

2.線性結(jié)構(gòu)第25頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月2.線性結(jié)構(gòu)第26頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月2.1線性表

3.線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)

雙向鏈表（循環(huán)鏈表）——線性表的鏈?zhǔn)酱鎯?chǔ)表示

概念：兩個(gè)指針，分別指向前驅(qū)元素和后繼元素

typedefstructDuLnode{ ElemType data; StructDuLnode *prior; StructDuLnode *next;}DuLnode,*DuLinkList;2.線性結(jié)構(gòu)第27頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月2.2棧和隊(duì)列1.棧的定義

棧（Stack）是限定只能在表得一端進(jìn)行插入和刪除操作得線性表，又稱限定性線性表結(jié)構(gòu)。2.棧的結(jié)構(gòu)特點(diǎn)和操作棧頂(Top)、棧底(Bottom),先入后出(LIFO)棧的基本操作

InitStack（&S）GetTop(S,&e)DestroyStack(&S)Push(&S,e)ClearStack(&S)Pop(&S,&e)StackEmpty（S）StackTraverse(S)StackLength（S）2.線性結(jié)構(gòu)第28頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月堆棧結(jié)構(gòu)示意圖2.線性結(jié)構(gòu)第29頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月2.2棧和隊(duì)列3.隊(duì)列的定義

隊(duì)列（Queue）是限定只能在表得一端進(jìn)行插入在表的另一端進(jìn)行刪除操作的線性表。4.隊(duì)列的結(jié)構(gòu)特點(diǎn)和操作隊(duì)列頭(front)、隊(duì)列尾(rear)，先入先出(FIFO)隊(duì)列的基本操作

InitQueue(&Q)GetHead(Q,&e)DestroyStack(&S)EnQueue(&Q,e)ClearQueue(&Q)Dequeue(&Q,&e)QueueEmpty(Q)QueueTraverse(Q)QueueLength(Q)2.線性結(jié)構(gòu)第30頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月2.3串和數(shù)組1.串的定義和表示方法串定義

串（即字符串）是一種特殊的線性表，它的數(shù)據(jù)元素僅由一個(gè)字符組成字符串，由零個(gè)或多個(gè)字符組成的有限序列。

S＝“a0a1.....an-1”串的長(zhǎng)度：n空串：n=0，NullString子串與主串，子串的位置（從0開(kāi)始）串的比較：最大相等前綴子序列2.線性結(jié)構(gòu)第31頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月2.3串和數(shù)組1.串的定義和表示方法串的表示方法

定長(zhǎng)順序存儲(chǔ)表示

兩種表示方法：

1)下標(biāo)為0的數(shù)組存放長(zhǎng)度(pascal) typedefunsignedcharSString[MAXSTLEN+1];2)在串值后面加‘\0’結(jié)束(C語(yǔ)言)

堆分配存儲(chǔ)表示串變量的存儲(chǔ)空間是在程序執(zhí)行過(guò)程中動(dòng)態(tài)分配的，程序中出現(xiàn)的所有串變量可用的存儲(chǔ)空間是一個(gè)共享空間，稱為“堆”。2.線性結(jié)構(gòu)第32頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月2.3串和數(shù)組2.數(shù)組的定義和操作數(shù)組定義數(shù)組是一個(gè)具有固定格式和數(shù)量的數(shù)據(jù)有序集，每一個(gè)數(shù)據(jù)元素有唯一的一組下標(biāo)來(lái)標(biāo)識(shí)。數(shù)組可以看作線性表的推廣。數(shù)組作為一種數(shù)據(jù)結(jié)構(gòu)其特點(diǎn)是結(jié)構(gòu)中的元素本身可以是具有某種結(jié)構(gòu)的數(shù)據(jù)，但屬于同一數(shù)據(jù)類型。二維數(shù)組定義其數(shù)據(jù)元素是一維數(shù)組的線形表。N維數(shù)組定義其數(shù)據(jù)元素是N－1維數(shù)組的線形表。2.線性結(jié)構(gòu)第33頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月2.3串和數(shù)組2.數(shù)組的定義和操作數(shù)組的操作initarray(&A,n,bound1,bound2...boundn)——初始化Destroyarray(&A)——?jiǎng)h除數(shù)組value(A,&e,index1,index2......indexn)——賦值assign(&A,e,index1,index2......indexn)——分配數(shù)組2.線性結(jié)構(gòu)第34頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月2.3串和數(shù)組3.數(shù)組的存儲(chǔ)方式和表示數(shù)組元素的兩種存儲(chǔ)方式行主序存儲(chǔ)列主序存儲(chǔ)數(shù)組中元素在內(nèi)存映象中的關(guān)系:二維數(shù)組A[m][n] LOC[i,j]=LOC[0,0]+(i*n+j)*L三維數(shù)組B[p][m][n] LOC[i,j,k]=LOC[0,0,0]+(i*m*n+j*n+k)*L2.線性結(jié)構(gòu)第35頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月第三節(jié)非線性結(jié)構(gòu)第36頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月3.1樹(shù)

1.樹(shù)的定義與結(jié)構(gòu)特點(diǎn)

樹(shù)的定義

n(n>=0)個(gè)數(shù)據(jù)元素（結(jié)點(diǎn)）的有限集D，若D為空集，則為空樹(shù)。否則：在D中存在唯一的稱為根的數(shù)據(jù)元素；當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m（m>0）個(gè)互不相交的有限子集T1，T2，......，Tm，其中每個(gè)子集本身又是一顆樹(shù)，并成為根的子樹(shù)。

3.非線性結(jié)構(gòu)第37頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月3.1樹(shù)1.樹(shù)的定義與結(jié)構(gòu)特點(diǎn)

樹(shù)的結(jié)構(gòu)特點(diǎn)

樹(shù)具有下面兩個(gè)特點(diǎn)：

(1)樹(shù)的根節(jié)點(diǎn)沒(méi)有前驅(qū)節(jié)點(diǎn)，除根節(jié)點(diǎn)之外的所有節(jié)點(diǎn)有且只有一個(gè)前驅(qū)節(jié)點(diǎn)。

(2)樹(shù)中所有節(jié)點(diǎn)可以有零個(gè)或多個(gè)后繼節(jié)點(diǎn)。3.非線性結(jié)構(gòu)第38頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月3.非線性結(jié)構(gòu)典型的樹(shù)結(jié)構(gòu)第39頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月3.1樹(shù)

2.二叉樹(shù)

二叉樹(shù)的定義二叉樹(shù)（BinaryTree）是個(gè)有限元素的集合，該集合或者為空、或者由一個(gè)稱為根(root)的元素及兩個(gè)不相交的、被分別稱為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。

3.非線性結(jié)構(gòu)二叉樹(shù)的五種基本形態(tài)

第40頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月

2.二叉樹(shù)

滿二叉樹(shù)和完全二叉樹(shù)

滿二叉樹(shù)（fullbinarytree）：所有結(jié)點(diǎn)度為2，葉子結(jié)點(diǎn)在同一層次。

完全二叉樹(shù)（completebinarytree）：一棵深度為k的有n個(gè)節(jié)點(diǎn)的二叉樹(shù)，對(duì)樹(shù)中的節(jié)點(diǎn)按從上至下、從左到右的順序進(jìn)行編號(hào)，如果編號(hào)為i（1≤i≤n）的節(jié)點(diǎn)與滿二叉樹(shù)中編號(hào)為i的節(jié)點(diǎn)在二叉樹(shù)中的位置相同，則這棵二叉樹(shù)稱為完全二叉樹(shù)。3.非線性結(jié)構(gòu)第41頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月3.1樹(shù)

3.樹(shù)的運(yùn)算

樹(shù)的運(yùn)算主要是插入節(jié)點(diǎn)、刪除節(jié)點(diǎn)和遍歷等幾種。插入節(jié)點(diǎn)、刪除節(jié)點(diǎn)運(yùn)算改變樹(shù)的結(jié)構(gòu)，但要求在改變結(jié)構(gòu)的同時(shí)，保持樹(shù)的特性不變，對(duì)于二叉樹(shù)，插入和刪除操作后的樹(shù)仍然是一棵二叉樹(shù)。這兩個(gè)操作過(guò)于復(fù)雜，在專業(yè)書(shū)籍中介紹，在此不做詳細(xì)討論。

3.非線性結(jié)構(gòu)第42頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月3.1樹(shù)

3.樹(shù)的運(yùn)算樹(shù)的基本運(yùn)算操作：

InitTree（&T）

DestroyTree（&T）

CreateTree(&T,definition)TreeEmpty(T)TreeDepth(T)Parent(T,e)LeftChild（T，e）

Rightsibling(T,e)InsertChild（&T,&p,i,C）

DeleteChild（&T,&p,i）

Traverse（T）3.非線性結(jié)構(gòu)第43頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月3.2圖

1.圖的定義與相關(guān)概念

圖的定義

圖是由一組節(jié)點(diǎn)（vertex）的有窮集V(G)和和一組頂點(diǎn)間的連線(arc)的集合E(G)組成的一種抽象數(shù)據(jù)結(jié)構(gòu)。記做：G＝(V，E)。V是數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素，E是集合上的關(guān)系

3.非線性結(jié)構(gòu)第44頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月3.2圖

1.圖的定義與相關(guān)概念

圖的相關(guān)概念弧(arc)、弧頭（終點(diǎn)）、弧尾（起點(diǎn)）：<v,w>表示從v到w的弧

有向圖(digraph)、無(wú)向圖(undigraph)、邊:(v,w)代表<v,w>和<w,v>

有向網(wǎng)、無(wú)向網(wǎng)：帶權(quán)的有向圖和無(wú)向圖

完全圖（completegraph）：邊e為n(n-1)/2有向完全圖：弧e為n(n-1)

3.非線性結(jié)構(gòu)第45頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月3.非線性結(jié)構(gòu)第46頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月3.2圖

2.圖的運(yùn)算

圖的基本運(yùn)算添加頂點(diǎn)——將一個(gè)新頂點(diǎn)插入到圖中添加邊——連接一個(gè)頂點(diǎn)和一個(gè)目標(biāo)頂點(diǎn)刪除頂點(diǎn)——從一個(gè)圖里移除一個(gè)頂點(diǎn)，同時(shí)刪除連接頂點(diǎn)的邊。查找頂點(diǎn)——通過(guò)遍歷圖來(lái)查找特定的頂點(diǎn)。圖的遍歷——指從圖中的任一頂點(diǎn)出發(fā)，對(duì)圖中的所有頂點(diǎn)訪問(wèn)一次且只訪問(wèn)一次說(shuō)明：圖的遍歷是圖的一種基本操作，圖的許多其他操作都是建立在遍歷操作的基礎(chǔ)之上。3非線性結(jié)構(gòu)第47頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月第四節(jié)算法第48頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月主要內(nèi)容一、算法概念二、算法結(jié)構(gòu)三、算法表示（流程圖、偽代碼、N-S圖等）四、基本算法（計(jì)數(shù)，累加，值交換，求最大（?。┲?，窮舉、迭代、遞推、遞歸）

第49頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月一、算法的概念1.算法的定義為解決問(wèn)題而采取的方法和步驟。（非正式）算法是一組明確步驟的有序集合，它產(chǎn)生結(jié)果并在有限的時(shí)間內(nèi)終止。（正式）第50頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月

2.算法的分類計(jì)算機(jī)算法可分為兩大類：數(shù)值運(yùn)算算法：求解數(shù)值非數(shù)值運(yùn)算算法：事務(wù)管理例1:

數(shù)值計(jì)算問(wèn)題：結(jié)構(gòu)靜力分析計(jì)算需要解線性代數(shù)方程組。例2:

非數(shù)值計(jì)算問(wèn)題：計(jì)算機(jī)對(duì)弈

算法—對(duì)弈的規(guī)則和策略

模型—棋盤及棋盤的格局第51頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月3.算法的基本特征有窮性：任何算法都會(huì)在有限步后終止；確定性：算法的每一步都有唯一的含義；有效性：算法的每一步都可以被執(zhí)行；有輸入：可以有多個(gè)輸入，也可能沒(méi)有輸入；有輸出：算法至少有一個(gè)輸出結(jié)果。第52頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月

4.算法設(shè)計(jì)的原則正確性：對(duì)于一切合法的輸入數(shù)據(jù)都能得出滿足要求的結(jié)果?？勺x性：算法應(yīng)該易理解，便于交流。健壯性：當(dāng)輸入非法數(shù)據(jù)時(shí)，算法應(yīng)恰當(dāng)?shù)刈鞒龇磻?yīng)或進(jìn)行相應(yīng)處理。高效率與低存儲(chǔ)量需求：算法執(zhí)行時(shí)間較少，算法執(zhí)行所需存儲(chǔ)空間較小。第53頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月定義動(dòng)作確定一系列的步驟，每一步都只完成一個(gè)動(dòng)作。精化剔除重復(fù)的步驟；不同的步驟完成的動(dòng)作可能相同，但它們產(chǎn)生的結(jié)果不能相同。泛化使算法對(duì)盡可能多的具體問(wèn)題具有適應(yīng)性。5.如何設(shè)計(jì)一個(gè)算法第54頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月例1：從一組正整數(shù)中找到最大的數(shù)。（正整數(shù)個(gè)數(shù)＝2，3，…N）例如,

12,8;

12,8,13;

12,8,13,9; 12,8,13,9,11,…..方法1：第一步:

比較第一個(gè)數(shù)和第二個(gè)數(shù);第二步:

比較第一個(gè)數(shù)和第三個(gè)數(shù);第三步:比較第二個(gè)數(shù)和第三個(gè)數(shù);第55頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月方法2：第一步：將最大值置為第一個(gè)數(shù)；第二步：將第二個(gè)數(shù)和最大值進(jìn)行比較，如果第二個(gè)數(shù)大于最大值，將最大值置為第二個(gè)數(shù)，反之保持最大值不變。第三步：將第三個(gè)數(shù)和最大值進(jìn)行比較，如果第三個(gè)數(shù)大于最大值，將最大值置為第三個(gè)數(shù)，反之保持最大值原值不變。第二、三步程序功能相同，程序描述語(yǔ)言相似和第二、三步不同第56頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月方法3：第零步：將最大值置為零；第一步：如果當(dāng)前數(shù)大于最大值，那么將最大值置為當(dāng)前數(shù)，否則保留原最大值；第二步：重復(fù)第一步直至所有數(shù)全比較完。第57頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月二、算法的三種基本結(jié)構(gòu)任何算法（或程序）都由三種基本結(jié)構(gòu)組成：順序結(jié)構(gòu)判斷（選擇）結(jié)構(gòu)循環(huán)結(jié)構(gòu)任何算法都是上述三種結(jié)構(gòu)的組合。第58頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月1.順序結(jié)構(gòu)S1S2第59頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月2.選擇結(jié)構(gòu)N條件S1S2Y

雙選擇結(jié)構(gòu)N條件S1Y單選擇結(jié)構(gòu)第60頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月3.循環(huán)結(jié)構(gòu)

條件A塊NY直到型循環(huán)結(jié)構(gòu)條件A塊YN

當(dāng)型循環(huán)結(jié)構(gòu)第61頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月三種基本結(jié)構(gòu)的特點(diǎn)：一個(gè)入口

一個(gè)出口不出現(xiàn)死循環(huán)和死語(yǔ)句第62頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月63T+ITI≤10YN1I，0K,0TK>10YNT+KT第63頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月T+ITI≤10YN1I，0K,0TK>10YNT+KT死循環(huán)死語(yǔ)句第64頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月用順序結(jié)構(gòu)描述將華氏溫度F轉(zhuǎn)換成攝氏溫度C的流程。算法：C=5/9*（F-32）4.順序結(jié)構(gòu)設(shè)計(jì)順序結(jié)構(gòu)中，按語(yǔ)句的自然順序依次執(zhí)行。開(kāi)始5/9bb*(F-32)C輸出F，C結(jié)束輸入F第65頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月已知三角形的3條邊邊長(zhǎng)，求三角形面積。用順序結(jié)構(gòu)描述求三角形面積的流程。開(kāi)始(a+b+c)/2ss*(s-a)*(s-b)*(s-c)t輸出area結(jié)束輸入a,b,c第66頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月用順序結(jié)構(gòu)描述兩個(gè)值（a=1,b=2）交換的流程

12bca1開(kāi)始1a，2babba

輸出a，b結(jié)束acbacb2112ab21第67頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月選擇結(jié)構(gòu)（分支結(jié)構(gòu)），根據(jù)選擇結(jié)構(gòu)中判斷的結(jié)果，選擇執(zhí)行相應(yīng)的語(yǔ)句。5.選擇結(jié)構(gòu)及其程序設(shè)計(jì)開(kāi)始輸出MAX結(jié)束輸入R,HRMAXHMAXR≥HYN例用選擇結(jié)構(gòu)描述求兩個(gè)數(shù)中的最大值的流程第68頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月例用選擇結(jié)構(gòu)描述檢查某年是否閏年的流程。X年為閏年滿足下列條件之一：1.N能被400整除2.N能被4整除，但不能被100整除開(kāi)始輸出XYES結(jié)束輸入XX被400整除YNX被4整除YNX被100整除YN輸出XNO第69頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月用選擇結(jié)構(gòu)描述檢查某成績(jī)級(jí)別的流程。成績(jī)N的級(jí)別：A級(jí)--X≥90B級(jí)—90>X≥80C級(jí)—80>X≥60D級(jí)—X<60開(kāi)始輸出X-A結(jié)束輸入XX≥90YNX≥80YNYNX≥60輸出X-B輸出X-C輸出X-D第70頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月循環(huán)結(jié)構(gòu)：當(dāng)循環(huán)控制條件為真時(shí)反復(fù)執(zhí)行循環(huán)體中的語(yǔ)句，直到循環(huán)控制條件為假時(shí)為止。開(kāi)始輸出T的值結(jié)束輸入KT+KTI+1II≤10YN1I，0T累加器計(jì)數(shù)器用循環(huán)結(jié)構(gòu)描述求10個(gè)學(xué)生成績(jī)之和的流程用T累計(jì)10個(gè)學(xué)生的成績(jī)（K），用I記錄累加的次數(shù)（I=1,2,…,10）6.循環(huán)結(jié)構(gòu)及其程序設(shè)計(jì)第71頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月例用循環(huán)結(jié)構(gòu)描述求10到100之間所有不能被3整除的整數(shù)的流程開(kāi)始結(jié)束I+1II≤100YN10II不能被3整除輸出IYN對(duì)10到100之間所有數(shù)逐一驗(yàn)證，凡滿足“不能被3整除”的整數(shù)即可輸出。第72頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月

循環(huán)嵌套結(jié)構(gòu)：

一個(gè)循環(huán)結(jié)構(gòu)的循環(huán)體中又出現(xiàn)另一個(gè)循環(huán)結(jié)構(gòu)。外循環(huán)

內(nèi)循環(huán)

J+1JI≤3YN1I輸出IJ≤21J輸出JI+1IYNI=1，輸出1

J=1，輸出1J=2，輸出2I=2，輸出2

J=1，輸出1J=2，輸出2I=3，輸出3

J=1，輸出1J=2，輸出2第73頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月

例

打印邊長(zhǎng)為m的正方型 要求：從鍵盤輸入m值，輸出m行每行m個(gè)*號(hào)。 例：輸入m=4，輸出的圖形如下：****************算法：

1.輸入m 2.重復(fù)打印

m行，每行打印

m個(gè)*第74頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月開(kāi)始結(jié)束輸入MI+1II≤MYN1IAB

對(duì)行循環(huán)(I=1,2,…，M)

對(duì)I行的各列循環(huán)(J=1,2,…，M)輸出*J+1JJ≤MYN1JAB換行輸出I行的M個(gè)*第75頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月I=1，J=1輸出**

J=2輸出***

J=3輸出****

J=4輸出*****換行I=2J=1，2，3，4********……I=4J=1，2，3，4************

****第76頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月例從鍵盤輸入n值，輸出n行用*號(hào)組成等腰三角形。例：輸入n=4，輸出的圖形如下：****************

*k=1,n-1=3個(gè)空，2*1-1=1個(gè)*??***k=2,n-2=2個(gè)空，2*2-1=3個(gè)*?*****k=3,n-3=1個(gè)空，2*3-1=5個(gè)********k=4,n-4=0個(gè)空，2*4-1=7個(gè)*共n行，其中第K行由n-k個(gè)空格和2k-1個(gè)*組成第77頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月

分析：

1、輸出n

行。

2、圖形的第k

行(1<=k<=n)由n-k個(gè)空格和2k-1個(gè)*組成。算法設(shè)計(jì)：1.輸入n;2.重復(fù)輸出n行。對(duì)于第

k

行，每行輸出n-k

個(gè)空格和2k-1個(gè)*

第78頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月開(kāi)始結(jié)束輸入nk+1kk≤nYN1kAB

對(duì)行循環(huán)(k=1,2,…，n)輸出空J(rèn)+1JJ≤n-kYN1JA輸出*J+1JJ≤2k-1YN1JB換行

對(duì)每個(gè)k行各列循環(huán)，輸出n-k個(gè)空格和2k-1個(gè)*第79頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月三、

算法的表示

自然語(yǔ)言

流程圖偽代碼

結(jié)構(gòu)圖

N-S結(jié)構(gòu)圖

PAD結(jié)構(gòu)圖計(jì)算機(jī)語(yǔ)言√√√√第80頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月

用規(guī)定的一系列圖形、流程線和文字說(shuō)明算法中的基本操作和控制流程。流程圖包括：

表示相應(yīng)操作的框；帶箭頭的流程線；

框內(nèi)外必要的文字說(shuō)明。1.流程圖第81頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月（1）圖形符號(hào)起止框判斷框處理框輸入/輸出框注釋框流向線連接點(diǎn)第82頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月例：求給定半徑R的圓面積和圓周長(zhǎng)。算法：圓面積

S=π*R2圓周長(zhǎng)

L=2*π*R開(kāi)始輸出S、L的值結(jié)束輸入半徑Rπ*R*RS2*π*R

L順序（2）用流程圖表示算法第83頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月例：求給定數(shù)R的絕對(duì)值。算法：|R|=RR≥0

-RR<0開(kāi)始輸出S的值結(jié)束輸入RRS-R

SR≥0YN選擇第84頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月求S=1+2+3+......+1000s;s+1ss+2s......s+100s0ss+is(循環(huán)體)(i=1,2,...,100)第85頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月例:給定K值，求T=1+2+3+…+K。K=5，T=0I=1：T=0+1=1，I=1+1=2I=2：T=1+2=3，I=2+1=3I=3：T=3+3=6，I=3+1=4I=4：T=6+4=10，I=4+1=5I=5：T=10+5=15，I=5+1=60

TT+I

T(I=1,2,3,…K)開(kāi)始輸出T的值結(jié)束輸入KT+ITI+1II≤KYN1I，0T循環(huán)第86頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月

由于流程線的任意轉(zhuǎn)向性，傳統(tǒng)流程圖無(wú)法保證自頂向下的程序設(shè)計(jì)，使模塊之間的調(diào)用關(guān)系難以表達(dá)。故兩位美國(guó)學(xué)者Nassi和Shneiderman于1973年提出了無(wú)流程線的N-S流程圖。2.N–S流程圖第87頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月S1S2流程圖S1S2N-S流程圖（1）圖形符號(hào)第88頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月YNS1S2條件流程圖條件YNS1S2N-S流程圖第89頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月YN循環(huán)體條件流程圖循環(huán)體循環(huán)條件N-S流程圖第90頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月流程圖NY循環(huán)體條件循環(huán)體循環(huán)條件N–S流程圖第91頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月（2）用N-S流程圖表示算法輸入半徑R輸出S、L的值π*R*RS2*π*R

L例：求給定半徑R的圓面積和圓周長(zhǎng)開(kāi)始輸出S、L的值結(jié)束輸入半徑Rπ*R*RS2*π*R

L順序第92頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月開(kāi)始輸出S的值結(jié)束輸入RRS-R

SR≥0YN選擇輸入R輸出S的值RS-RSYR≥0N例：求給定數(shù)R的絕對(duì)值第93頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月例:

給定K值，求T=1+2+3+…+K開(kāi)始輸出T的值結(jié)束輸入KT+ITI+1II≤KYN1I，0T循環(huán)輸入K輸出T的值I≤K

1I，0TT+ITI+1I第94頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月偽代碼是算法的一種類似英語(yǔ)的表示法。它是部分英語(yǔ)和部分結(jié)構(gòu)化代碼的組合。英文代碼部分采用不嚴(yán)格的語(yǔ)法，很容易看懂；代碼部分包含基本算法結(jié)構(gòu)（順序、選擇和循環(huán)）的擴(kuò)展形式。目前還沒(méi)有偽代碼的標(biāo)準(zhǔn)。3.偽代碼第95頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月偽代碼描述算法的一般組成：算法頭：算法的名字。目的、條件和返回值：

目的：有關(guān)算法要做什么的簡(jiǎn)短說(shuō)明

前置條件：列出算法所有前驅(qū)條件

后置條件：指出算法產(chǎn)生的影響

返回值：算法返回的結(jié)果或無(wú)返回值語(yǔ)句序號(hào)：表示語(yǔ)句之間的附屬關(guān)系。第96頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月例：用偽代碼描述在一數(shù)列中找最小值的算法Algorithm（算法）：FindingSmallestPurpose（目的）：在一數(shù)列中找最小值Pre（前置條件）：Listofnumbers（數(shù)列）Post（后置條件）：NoneReturn（返回值）：Thesmallest32416a:S3

21算法：設(shè)數(shù)列中第一個(gè)數(shù)為最小值S，然后用后續(xù)數(shù)依次與S比較，若比S小，則用該數(shù)替換原S的值，全部比較完成后S即最小值。第97頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月1.Setsmallesttothefirstnumber2.Loop(notendoflist)

2.1if(nextnumber<smallest)

2.1.1setsmallesttonextnumber

2.2endif3.endloop4.returnsmallestEndFindingSmallest數(shù)列ai(i=1,5)a1S,2ii≤5Yai<SNaiSi+1i返回最小值S第98頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月1.數(shù)列ai(i=1,5)2.

a1S,2i3.while(i≤5)

3.1if(ai<S)thenaiS

endif3.2i+1i

endwhile4.

returnS偽代碼不一定按上述嚴(yán)格的格式，且可以使用漢字，只要把算法表達(dá)清楚即可。數(shù)列ai(i=1,5)a1S,2ii≤5Yai<SNaiSi+1i返回最小值S第99頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月s=a[1];i=2;while(i<=5)

{if(a[i]<s)s=a[i];i=i+1;}returns;數(shù)列ai(i=1,5)a1S,2ii≤5Yai<SNaiSi+1i返回最小值S4.計(jì)算機(jī)語(yǔ)言第100頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月計(jì)數(shù)累加值交換求最大（?。┲邓?、基本算法窮舉迭代遞推遞歸第101頁(yè)，課件共115頁(yè)，創(chuàng)作于2023年2月1.窮舉法基本思想首先根據(jù)問(wèn)題的部分條件預(yù)估