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

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

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

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

數(shù)據(jù)元素、結(jié)點、數(shù)據(jù)項、關(guān)鍵字或主關(guān)鍵字、次關(guān)鍵字、數(shù)據(jù)對象、數(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頁，課件共115頁，創(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)系是“屬于同一個集合”。集合是元素關(guān)系極為松散的一種結(jié)構(gòu)，各元素間沒有直接的關(guān)聯(lián)。線性結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著一對一的關(guān)系。樹型結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著一對多的關(guān)系。圖形結(jié)構(gòu)。該結(jié)構(gòu)的數(shù)據(jù)元素之間存在著多對多的關(guān)系，圖形結(jié)構(gòu)也稱作網(wǎng)狀結(jié)構(gòu)。

123456第8頁，課件共115頁，創(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頁，課件共115頁，創(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頁，課件共115頁，創(chuàng)作于2023年2月

[例5-4]樹形結(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頁，課件共115頁，創(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è)計算法——

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

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

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

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

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

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

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

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

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

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

1、算法的概念及特征

算法:

對問題求解的描述，為解決問題給出的一個確定的、有限長的操作序列。

算法具有以下五個重要的特征：

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

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

3）輸入：一個算法有0個或多個輸入，以刻畫運算對象的初始情況，所謂0個輸入是指算法本身定除了初始條件。

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

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

2、算法的描述:

1）流程圖

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

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頁，課件共115頁，創(chuàng)作于2023年2月1.數(shù)據(jù)結(jié)構(gòu)概述

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

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

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

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

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

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

5、算法與數(shù)據(jù)結(jié)構(gòu)的關(guān)系:計算機科學(xué)家沃斯（N.Wirth）提出的:“算法+數(shù)據(jù)結(jié)構(gòu)=程序”揭示了程序設(shè)計的本質(zhì)：對實際問題選擇一種好的數(shù)據(jù)結(jié)構(gòu)，加上設(shè)計一個好的算法，而好的算法很大程度上取決于描述實際問題的數(shù)據(jù)結(jié)構(gòu)。算法與數(shù)據(jù)結(jié)構(gòu)是互相依賴、互相聯(lián)系的。一個算法總是建立在一定數(shù)據(jù)結(jié)構(gòu)上的；反之，算法不確定，就無法決定如何構(gòu)造數(shù)據(jù)。1.數(shù)據(jù)結(jié)構(gòu)概述第18頁，課件共115頁，創(chuàng)作于2023年2月第二節(jié)線性結(jié)構(gòu)第19頁，課件共115頁，創(chuàng)作于2023年2月2.1線性表

1.線性表的定義

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

其中，ai-1稱為ai

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

線性表的長度：表中的元素個數(shù)n

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

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

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

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

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

順序表——線性表的順序存儲表示

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頁，課件共115頁，創(chuàng)作于2023年2月2.線性結(jié)構(gòu)第23頁，課件共115頁，創(chuàng)作于2023年2月2.1線性表3.線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)

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

3.線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)

單鏈表——線性表的鏈?zhǔn)酱鎯Ρ硎?/p>

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

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

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

3.線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)

雙向鏈表（循環(huán)鏈表）——線性表的鏈?zhǔn)酱鎯Ρ硎?/p>

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

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

棧（Stack）是限定只能在表得一端進(jìn)行插入和刪除操作得線性表，又稱限定性線性表結(jié)構(gòu)。2.棧的結(jié)構(gòu)特點和操作棧頂(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頁，課件共115頁，創(chuàng)作于2023年2月堆棧結(jié)構(gòu)示意圖2.線性結(jié)構(gòu)第29頁，課件共115頁，創(chuàng)作于2023年2月2.2棧和隊列3.隊列的定義

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

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頁，課件共115頁，創(chuàng)作于2023年2月2.3串和數(shù)組1.串的定義和表示方法串定義

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

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

定長順序存儲表示

兩種表示方法：

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

堆分配存儲表示串變量的存儲空間是在程序執(zhí)行過程中動態(tài)分配的，程序中出現(xiàn)的所有串變量可用的存儲空間是一個共享空間，稱為“堆”。2.線性結(jié)構(gòu)第32頁，課件共115頁，創(chuàng)作于2023年2月2.3串和數(shù)組2.數(shù)組的定義和操作數(shù)組定義數(shù)組是一個具有固定格式和數(shù)量的數(shù)據(jù)有序集，每一個數(shù)據(jù)元素有唯一的一組下標(biāo)來標(biāo)識。數(shù)組可以看作線性表的推廣。數(shù)組作為一種數(shù)據(jù)結(jié)構(gòu)其特點是結(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頁，課件共115頁，創(chuàng)作于2023年2月2.3串和數(shù)組2.數(shù)組的定義和操作數(shù)組的操作initarray(&A,n,bound1,bound2...boundn)——初始化Destroyarray(&A)——刪除數(shù)組value(A,&e,index1,index2......indexn)——賦值assign(&A,e,index1,index2......indexn)——分配數(shù)組2.線性結(jié)構(gòu)第34頁，課件共115頁，創(chuàng)作于2023年2月2.3串和數(shù)組3.數(shù)組的存儲方式和表示數(shù)組元素的兩種存儲方式行主序存儲列主序存儲數(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頁，課件共115頁，創(chuàng)作于2023年2月第三節(jié)非線性結(jié)構(gòu)第36頁，課件共115頁，創(chuàng)作于2023年2月3.1樹

1.樹的定義與結(jié)構(gòu)特點

樹的定義

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

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

樹的結(jié)構(gòu)特點

樹具有下面兩個特點：

(1)樹的根節(jié)點沒有前驅(qū)節(jié)點，除根節(jié)點之外的所有節(jié)點有且只有一個前驅(qū)節(jié)點。

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

2.二叉樹

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

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

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

2.二叉樹

滿二叉樹和完全二叉樹

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

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

3.樹的運算

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

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

3.樹的運算樹的基本運算操作：

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頁，課件共115頁，創(chuàng)作于2023年2月3.2圖

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

圖的定義

圖是由一組節(jié)點（vertex）的有窮集V(G)和和一組頂點間的連線(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頁，課件共115頁，創(chuàng)作于2023年2月3.2圖

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

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

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

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

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

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

2.圖的運算

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

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

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

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

非數(shù)值計算問題：計算機對弈

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

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

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

12,8;

12,8,13;

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

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

比較第一個數(shù)和第三個數(shù);第三步:比較第二個數(shù)和第三個數(shù);第55頁，課件共115頁，創(chuàng)作于2023年2月方法2：第一步：將最大值置為第一個數(shù)；第二步：將第二個數(shù)和最大值進(jìn)行比較，如果第二個數(shù)大于最大值，將最大值置為第二個數(shù)，反之保持最大值不變。第三步：將第三個數(shù)和最大值進(jìn)行比較，如果第三個數(shù)大于最大值，將最大值置為第三個數(shù)，反之保持最大值原值不變。第二、三步程序功能相同，程序描述語言相似和第二、三步不同第56頁，課件共115頁，創(chuàng)作于2023年2月方法3：第零步：將最大值置為零；第一步：如果當(dāng)前數(shù)大于最大值，那么將最大值置為當(dāng)前數(shù)，否則保留原最大值；第二步：重復(fù)第一步直至所有數(shù)全比較完。第57頁，課件共115頁，創(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頁，課件共115頁，創(chuàng)作于2023年2月1.順序結(jié)構(gòu)S1S2第59頁，課件共115頁，創(chuàng)作于2023年2月2.選擇結(jié)構(gòu)N條件S1S2Y

雙選擇結(jié)構(gòu)N條件S1Y單選擇結(jié)構(gòu)第60頁，課件共115頁，創(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頁，課件共115頁，創(chuàng)作于2023年2月三種基本結(jié)構(gòu)的特點：一個入口

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

12bca1開始1a，2babba

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

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

一個循環(huán)結(jié)構(gòu)的循環(huán)體中又出現(xiàn)另一個循環(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頁，課件共115頁，創(chuàng)作于2023年2月

例

打印邊長為m的正方型 要求：從鍵盤輸入m值，輸出m行每行m個*號。 例：輸入m=4，輸出的圖形如下：****************算法：

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

m行，每行打印

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

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

對I行的各列循環(huán)(J=1,2,…，M)輸出*J+1JJ≤MYN1JAB換行輸出I行的M個*第75頁，課件共115頁，創(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頁，課件共115頁，創(chuàng)作于2023年2月例從鍵盤輸入n值，輸出n行用*號組成等腰三角形。例：輸入n=4，輸出的圖形如下：****************

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

分析：

1、輸出n

行。

2、圖形的第k

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

k

行，每行輸出n-k

個空格和2k-1個*

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

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

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

算法的表示

自然語言

流程圖偽代碼

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

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

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

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

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

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

S=π*R2圓周長

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

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

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

SR≥0YN選擇第84頁，課件共115頁，創(chuàng)作于2023年2月求S=1+2+3+......+1000s;s+1ss+2s......s+100s0ss+is(循環(huán)體)(i=1,2,...,100)第85頁，課件共115頁，創(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)開始輸出T的值結(jié)束輸入KT+ITI+1II≤KYN1I，0T循環(huán)第86頁，課件共115頁，創(chuàng)作于2023年2月

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

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

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

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

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

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

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

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

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

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

21算法：設(shè)數(shù)列中第一個數(shù)為最小值S，然后用后續(xù)數(shù)依次與S比較，若比S小，則用該數(shù)替換原S的值，全部比較完成后S即最小值。第97頁，課件共115頁，創(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頁，課件共115頁，創(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頁，課件共115頁，創(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.計算機語言第100頁，課件共115頁，創(chuàng)作于2023年2月計數(shù)累加值交換求最大（?。┲邓摹⒒舅惴ǜF舉迭代遞推遞歸第101頁，課件共115頁，創(chuàng)作于2023年2月1.窮舉法基本思想首先根據(jù)問題的部分條件預(yù)估