數據結構與算法第1頁，課件共58頁，創作于2023年2月Chapter1第2頁，課件共58頁，創作于2023年2月Section1數據結構討論的范疇第3頁，課件共58頁，創作于2023年2月計算機程序設計的兩大要素程序=數據結構+算法程序→為計算機解題而編寫的一組指令集數據結構→問題的數學模型算法→處理問題的策略（計算的方法）第4頁，課件共58頁，創作于2023年2月計算機如何解題要處理的現實問題怎么表示？即怎樣用數學形式（函數、公式、符號）抽象地表示現實問題？也就是問題的數學模型是什么？這就是數據結構要討論的問題。怎樣對問題進行信息處理？也就是處理問題的策略是什么？這就是算法要討論的問題。第5頁，課件共58頁，創作于2023年2月計算機解題的步驟從現實問題中抽象出一個具體的數學模型設計一個解此數學模型的合適算法使用某種編程語言將算法“翻譯”成程序并調試正確通過多方位的測試，使程序投入實際運行，即使問題獲得目標結果第6頁，課件共58頁，創作于2023年2月計算機的兩大應用領域數值計算（科學與工程計算）數據：數值數據計算：解方程（組）、函數求值、概略統計、運籌等非數值計算（邏輯計算/數值處理）數據：文字、符號、表格、圖象、聲音、視頻等計算：比較、歸類、統計、查找、排序、轉換以及傳輸等第7頁，課件共58頁，創作于2023年2月數值計算對于數值計算問題的解決方法，主要是用各種數學方程建立數學模型，例如：天氣預報的數學模型為二階橢圓偏微分方程，預測人口增長的數學模型為常微分方程。求解這些數學方程的方法是計算數學（數值分析）研究的領域，例如差分算法、有限元算法、無限元算法等。第8頁，課件共58頁，創作于2023年2月例1-1：雞兔同籠問題數學模型算法二元一次方程如：x+y=m2x+4y=n(m≥2,n≥6且n%2=0)枚舉法for(x=1;x<=m-1;x++)for(y=1;y<=m-1;y++)if((x+y==m)and(2*x+4*y==n)){print(“雞＝”x”,兔子＝”y)；

break;}第9頁，課件共58頁，創作于2023年2月非數值計算當今計算機能夠處理的應用問題90%以上是非數值計算問題——包括數據的比較、歸類、統計、查找、排序、轉換以及傳輸等。而絕大多數非數值計算問題是無法用數學方程式來描述的，它們需要使用特定的離散數學模型，如線性表樹圖這些模型及其算法就是數據結構學科所要研究的內容。第10頁，課件共58頁，創作于2023年2月例1-2圖書數目檢索數學模型：各種書目表（線性結構）書目信息如：書名、作者、出版社、出版日期、書號、分類號、內容提要等。問題：如何表示和組織書目信息？算法：按照某個特定要求（如給定書名）對相關書目表進行查詢的方法。第11頁，課件共58頁，創作于2023年2月001數據結構張山清華出版社T01……002高等數學李司高教出版社S01……003數據結構王武清華出版社T02……004經濟學原理馬魯三聯出版社J01……………………………

……

數據結構001,003,…高等數學002,……經濟學原理004,………………張山001,023李司002,…王武003,……………圖1-1書目表示例T001,003…S002…J004…………第12頁，課件共58頁，創作于2023年2月例1-3人機對弈數學模型：對弈樹（樹結構）問題：如何表示、組織棋盤和棋子信息，如何表示、組織并保存動態變化的棋局狀態（格局）算法：對弈／走棋操作的算法——使格局發生變化，由一種格局派生出另一種格局，并從多種可選路徑中選擇一種最優／合理路徑，最后達到輸／贏狀態第13頁，課件共58頁，創作于2023年2月圖1-2井字棋對弈樹的局部

井字棋游戲的規則：從一個空的棋盤開始，白子先行，輪流走棋。判定勝負的標準是：三枚同色棋子占據了一橫行或一豎行或一對角線，則獲勝；如果直到棋盤被占滿時還沒有一方獲勝，則為和局。第14頁，課件共58頁，創作于2023年2月例1-4：多叉路口的交通燈管理問題目標：如何保證多叉路口的交通暢通有序，并使交通流量達到最大，且不會發生交通事故，數學模型：通路狀態圖（圖／網結構）需解決的問題：①當某一條通路通行時，有哪些通路不能同時通行？②當某一條通路通行時，有哪些通路可同時通行？③如何表示和組織通路狀態信息？算法：結點的動態分組著色（綠色）策略，相鄰結點不能同時為綠色。第15頁，課件共58頁，創作于2023年2月ABCDE可通路非通路

A→B:BCBDDAEA

A→C:BDDADBEAEBA→D:EAEBECB→A:B→C:ABDBEBB→D:ACDAECD→A:ABACBDEBD→B:ACBCECD→C:E→A:ABACADE→B:ACADBCBDDAE→C:ADBDDBE→D:圖1-3五叉路口示意圖第16頁，課件共58頁，創作于2023年2月ABACADDCBABCBDEBEDEADADBEC每個結點代表一條通路；不能同時通行的結點用一條連線連接(相鄰）；相鄰結點用不同顏色標記，表示不能同時通行；相同顏色的結點表示這些通路可同時通行。孤立結點表示任何時候都可以通行，恒為綠色。圖1-4通路狀態圖第17頁，課件共58頁，創作于2023年2月數據結構研究現實問題的數學模型（非數值計算）及其上的算法在計算機中的表示和實現。數據結構是一門研究非數值計算的程序設計問題中計算機的操作對象以及它們之間的關系和操作等等的學科。數據結構是一門不斷發展的核心學科，隨著計算機處理的非數值計算問題越來越廣泛、深入和復雜，數據結構需要研究越來越復雜的結構和算法。第18頁，課件共58頁，創作于2023年2月Section2基本概念第19頁，課件共58頁，創作于2023年2月基本術語數據（Data）客觀事物的符號表示，是計算機可操作的對象。所有能被輸入到計算機中并被計算機程序處理的符號的總稱。信息在計算機中的表示。數據元素（DataElement）數據中的一個“個體”，數據結構中討論的基本單位。一個數據元素也可以由一個或若干個數據項（DataItem）組成。數據項是有意義的數據的最小原子單位。數據對象（DataObject）性質相同的數據元素的集合。第20頁，課件共58頁，創作于2023年2月example數據對象數據元素數據項整數集單個整數單個整數（不可再分）復數集單個復數實部，虛部學生檔案單個學生記錄多個數據項（學號、姓名、性別等）第21頁，課件共58頁，創作于2023年2月數據結構的定義帶結構的數據元素的集合/帶結構的數據對象。這里的結構是指數據元素之間的某種約束關系，即數據結構中討論的數據元素都不是孤立的，而是相互之間必定存在著一定的關系。相互之間存在一種或多種特定關系的數據元素的集合。關系決定了結構。對于同樣的數據元素，不同的關系將構成不同的結構。第22頁，課件共58頁，創作于2023年2月數據結構的類型邏輯結構（LogicalStructure）存儲結構（StorageStructure）第23頁，課件共58頁，創作于2023年2月邏輯結構“數據結構”通常指的只是數據的邏輯結構，它描述的是數據元素之間的邏輯關系，即數據元素之間固有的（內在的）、本質的聯系，它們反映在人們的概念上，是抽象的，與物理的計算機無關。集合結構線性結構樹形結構圖狀結構第24頁，課件共58頁，創作于2023年2月集合結點之間不存在關系，或說僅僅存在“同屬一個數據對象”的關系。第25頁，課件共58頁，創作于2023年2月線性結構元素（結點node）之間存在線性關系／1:1關系；除首結點外，每個結點有且只有一個前驅；除尾結點外，每個結點有且只有一個后繼。首結點尾結點第26頁，課件共58頁，創作于2023年2月樹形結構結點之間存在層次關系／1:n關系；除根結點無前驅外，每個結點有且只有一個前驅，但任一結點可以有0~n個后繼。

根結點第27頁，課件共58頁，創作于2023年2月※樹和圖統稱“非線性結構”結點之間存在任意關系／n:m關系：可以存在沒有前驅的結點或和沒有后繼的結點，其他的每個結點則可以有多個前驅，也可以有多個后繼。（在圖中，元素也稱作“頂點”）

網狀結構（圖）第28頁，課件共58頁，創作于2023年2月數據的存儲結構是邏輯結構在計算機存儲器中的映象(image)。即邏輯結構在計算機中的表示順序存儲結構鏈接存儲結構第29頁，課件共58頁，創作于2023年2月順序存儲結構通過數據元素在存儲器中的一個固定的相對位置來表示元素之間的前驅或后繼關系。采用順序映象的物理結構稱作順序結構。a0a1a2a3102104106108第30頁，課件共58頁，創作于2023年2月鏈接順序結構通過在元素的存儲單元中附加“指針”的方式來表示前驅或后繼關系。采用鏈式映象的物理結構稱作鏈式結構。a0a1a2a3first第31頁，課件共58頁，創作于2023年2月數據的邏輯結構和物理結構是密切相關的兩個方面。一般地，一種數據的邏輯結構根據需要可用多種物理結構來存儲，而采用不同的物理結構，其數據處理的算法及其效率往往是不同的。算法的設計取決于選定的邏輯結構算法的實現依賴于采用的物理結構第32頁，課件共58頁，創作于2023年2月數據結構的運算數據結構常見的運算創建運算清除運算插入運算刪除運算搜索運算更新運算訪問運算遍歷運算第33頁，課件共58頁，創作于2023年2月Section3數據抽象和抽象數據類型第34頁，課件共58頁，創作于2023年2月數據抽象和抽象數據類型數據類型是一個值的集合和定義在這個集合上的一組操作的總稱數據類型是高級程序設計語言所定義的某類數據的集合和定義在該集合上的一組原操作的總稱。原操作是指可對集合中的數據元素進行的運算，其算法已由語言系統或計算機硬件實現，并用特定的符號（運算符）表示。

數據類型＝集合＋原操作集第35頁，課件共58頁，創作于2023年2月Example整形數據類型（int）值的范圍：-232~232-1（-32768~32767）元素映像：4字節存儲單元算數運算：+,-,×,/關系運算：<,>,<=,>=,!=,==賦值運算：=第36頁，課件共58頁，創作于2023年2月AbstractDataType抽象數據類型（ADT）是數據類型的擴展或是廣義的數據類型，它可定義各種類型的邏輯數據結構，包括線性表、樹、圖等。抽象數據類型是一個數據結構和定義在這個數據結構上的一組操作的總稱。ADT=數據結構＋操作集這里的“操作”非原操作，需要自定義。ADT可用一個三元組表示：ADT=(D,R,P)D—數據對象，R—D上的關系集，P—對D的基本操作集第37頁，課件共58頁，創作于2023年2月

ADT<抽象數據類型名>isDataObject:

<數據對象描述>Relation

:

<關系描述>Operation

:

<操作聲明>End<抽象數據類型名>在面向對象語言中，ADT可用“類”來實現，其中的操作用“方法”（C++中稱為“成員函數”）實現。ADT的定義格式第38頁，課件共58頁，創作于2023年2月復數運算的構造方法ADT1-1Complexe{

數據：由一對實數（x,y）構成

運算：兩個復數分別為a（a1,a2）和b（b1,b2） ComplexCreateComp(floatx,floaty)%構造復數 ComplexAdd(Complexa,Complexb)%求和 ComplexSub(Complexa,Complexb)%求差 ComplexMul(Complexa,Complexb)%求積 ComplexDiv(Complexa,Complexb)%求除數 }第39頁，課件共58頁，創作于2023年2月#include<stdio.h>#include<stdlib.h>typedefstructcomplex{ float

x,y;}complex;ComplexCreateComp(floatx,floaty){ Complexc; c.x=x;c.y=y; returnc;}ComplexAdd(Complexa,Complexb){ Complexc; c.x=a.x+b.x;c.y=a.y+b.y; returnc;}程序1-1Complex的實現第40頁，課件共58頁，創作于2023年2月VoidPrintComplex(Complexa){ printf(“%3.2f+%3.2fi\n”,a.x,a.y);}Voidmain(){ Complexa,b,c; a=CreateComp(1.0f,2.0f); b=CreateComp(3.0f,4.0f); c=Add(a,b); PrintComplex(a); PrintComplex(b); PrintComplex(c);}程序1-2測試復數加法運算第41頁，課件共58頁，創作于2023年2月Section4算法和算法分析第42頁，課件共58頁，創作于2023年2月算法和算法分析算法（Algorithm）是求解特定問題的方法，它是指令的有限序列。算法是對特定問題求解步驟進行描述的一組指令集。這里的“指令”不是指計算機的機器指令，它可以是高級語言的一條或多條語句，也可以是偽碼語句，或用自然語言編寫的操作命令。第43頁，課件共58頁，創作于2023年2月算法的特征輸入輸出確定性能行性有窮性第44頁，課件共58頁，創作于2023年2月算法的描述算法不是程序，而是實現程序的方法（模型），設計算法也稱程序建模。自然語言：容易，但不簡潔和嚴謹、有二義性。流程圖：算法邏輯直觀清晰，但轉換成高級語言程序需要一定的開銷。如程序流程圖、N-S圖、UML活動圖。偽碼語言（算法語言）：介于自然語言和高級程序設計語言之間，保留了高級語言的語法骨架，但對具體語法和語法細節不做非常詳盡的要求，如忽略變量定義和輸入/出格式等。特點是簡潔、易讀、嚴謹、易被轉換成高級語言。流行的如PDL等。高級語言：開銷大，不靈活，不符合軟件工程思想，不是現代軟件設計風格。第45頁，課件共58頁，創作于2023年2月算法和程序的主要區別程序不一定滿足有窮性，可以出現有意義的無窮循環；算法則必須滿足有窮性。程序中的指令必須是機器可執行的；而算法中的指令則無此限制，算法只是程序的模型。設計算法是軟件開發過程中詳細設計階段的工作，由高級程序員完成；編程的實質是算法的編程語言翻譯，是編碼階段的工作，由普通程序員完成。第46頁，課件共58頁，創作于2023年2月軟件開發過程

系統分析員系統設計員高級程序員程序員系統測試員需求分析概要設計詳細設計編碼測試設計ADT是概要設計階段的工作，由系統設計員完成；算法設計是詳細設計階段的工作，由高級程序員完成；用編程語言編程則是編碼階段的工作，由程序員完成。第47頁，課件共58頁，創作于2023年2月本課程的要求

系統設計員——設計ADT

高級程序員——設計算法

程序員——編寫C++程序并上機調試測試員——找程序的毛病

第48頁，課件共58頁，創作于2023年2月算法評價的標準正確性：算法的運行結果應當滿足系統需求。一個算法的正確性必須通過測試才能驗證健壯性：是指一個算法對不合理數據輸入的反映和處理能力。當輸入的數據非法時，算法應當恰當地作出反映或進行相應處理，而不是產生莫名其妙的輸出結果。并且，處理出錯的方法不應是中斷程序的執行，而應是返回一個表示錯誤性質的值，以便在更高的抽象層次上進行處理。可讀性：算法是寫給其他人（程序員、測試人員及維護人員）看的！！效率：包括時間性和空間性，即運行該算法程序所需花費的時間和占用存儲空間的大小。對于同一個問題如果有多個算法可以解決，運行時間短的算法效率高，這是評價算法效率最主要的度量。第49頁，課件共58頁，創作于2023年2月時間復雜度時間復雜度是指程序運行從開始到結束所需的時間一個算法的時間復雜度是該算法中各條原指令的重復執行次數之和，記為T(n)，它是問題規模n的函數，與問題規模成正比。算法的執行時間=Σ[語句(i)的執行次數*語句(i)的執行時間]問題規模是指算法對求解問題所要處理的數據量。例如，求100以內還是10000以內的素數，就說后者規模比前者大。第50頁，課件共58頁，創作于2023年2月例1-5

算法:兩數交換

s=a;

//1次

a=b;

//1次

b=s;

//1次

∴T(n)=３例1-6算法:求累加和

s=0;//1次

for(i=0;i<n;i++)//n+1次

s+=a[i];

//n次

∴T(n)=2n+2第51頁，課件共58頁，創作于2023年2月例1-7

算法:矩陣相加

for(i=0;i<n;i++)

//n+1次

for(j=0;j<n;j++)

//n(n+1)次

c[i][j]=a[i][j]+b[i][j];

//n*n次

∴T(n)=2n2+2n+1第52頁，課件共58頁，創作于2023年2月漸進時間復雜度一個算法的時間復雜度的計算是比較繁瑣的，特別對于較復雜的算法更是如此。實際上，一般也沒有必要精確地計算出算法的時間復雜度，只要大致計算出相應的數量級／階（order）即可。假如，隨著問題規模n的增長，時間復雜度的增長率和某個函數f(n)的增長率相同；換言之，當n→∞時，T(n)與f(n)同階無窮大且f(n)是T(n)的上界，則可記作：T(n)=O(f(n))并稱T(n)為為算法的漸進時間復雜度（通常也簡稱為時間復雜度），其值用大O表示。第53頁，課件共58頁，創作于2023年2月例1-8

算法:矩陣相乘voidmult(inta[],intb[],int&c[]){//以二維數組存儲矩陣元素，c為a和b的乘積 for(i=1;i<=n;++i) \\n+1 for(j=1;j<=n;++j) \\n(n+1) { c[i,j]=0; \\n2 for(k=1;k<=n;++k) \\n2(n+1) c[i,j]+=a[i,k]*b[k,j]; \\n3 }}∴T(n)=2n3+3n2+2n+1∴漸進時間復雜度：O(n3)第54頁，課件共58頁，創作于2023年2月例1-9算法：選擇排序voidselect_sort(Typea[],intn)//將數組a中的數值序列排列成小→大的有序序列{

for(i=0;i<n-1;i++){//n-1

min=i;

/