1數據結構計算機科學與技術學院孫廷凱

2課程意義1001001111姓名學號年齡張三06010120李四06010219………………ABCDEFG“好”的程序算法+數據結構=程序3內容安排第1章緒論2課時第2章線性表8課時第3章棧和隊列4

課時第4章串

2

課時第5章數組與廣義表4課時第6章樹與二叉樹8課時第7章圖8課時第9章查找8課時第10章內部排序4課時上機實驗（線性表4，二叉樹或圖4） 8課時4考核方法平時成績10%考勤作業上機實驗10%（程序+實驗報告）線性表鏈式應用二叉樹有關運算圖有關運算期末考試成績80%（閉卷筆試）5課程信息教材：嚴蔚敏,吳偉民編著.數據結構.清華大學出版社（C語言版）,1997年4月第一版.先修課程：C++程序設計6第一章緒論1.1什么是數據結構1.2基本概念和術語1.3抽象數據類型的表示與實現1.4算法和算法分析71.1什么是數據結構計算機解決問題具體問題—〉數學模型—〉設計算法—〉測試調整很多非數值計算問題無法用數學方程描述例1.1圖書館書目檢索系統——線性（書p.1-2）例1.2計算機和人對弈問題——樹型（書p.1-2）8例1.3多叉路口交通燈管理系統ABCDEABACADBABCBDDADBDCEAEBECEDABACADBADCEDEABCBDDADBEBEC13條通路，考察任意兩條通路是否互相碰撞，在78種情況下有20種情況會碰撞（用連線表示）設置交通燈的問題等價于對圖的頂點著色問題：要求對圖上的每一個頂點染一種顏色，并且要求有線相連的兩個頂點不能具有相同顏色，而總的顏色種類應盡可能地少。9數據結構課程數據結構是一門研究非數值計算的程序設計問題中計算機的操作對象以及它們之間的關系和操作等等的學科。數學代數系統文件系統數據組織信息查詢軟件存儲裝置硬件編碼理論算子關系數據類型數據表示數據運算數據結構數據存取機器組織101.2基本概念與術語數據(Data):是對信息的一種符號表示。在計算機科學中是指所有能輸入到計算機中并被計算機程序處理的符號的總稱。數據元素(DataElement):是數據的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。一個數據元素可由若干個數據項(DataItem)組成。數據項是數據的不可分割的最小單位。數據對象(DataObject):是性質相同的數據元素的集合。是數據的一個子集。數據結構(DataStructure):是相互之間存在一種或多種特定關系的數據元素的集合。11數據的邏輯結構數據元素之間的相互關系稱為邏輯結構。通常分為四類基本結構：集合：結構中的數據元素除了同屬于一種類型外，別無其它關系線性結構：結構中的數據元素之間存在一對一的關系樹型結構：結構中的數據元素之間存在一對多的關系圖狀結構或網狀結構：結構中的數據元素之間存在多對多的關系12數據結構的形式定義數據結構的形式定義為：數據結構是一個二元組

Data_Structure=(D，S)例1.4

在計算機科學中，復數可取如下定義：復數是一種數據結構：Complex=（C，R）

D是數據元素的有限集S是D上關系的有限集C是含兩個實數的集合{c1，c2}R={<c1,c2>}，這里有序偶<c1,c2>表示c1是復數的實部，c2是復數的虛部13數據的存儲結構數據結構在計算機中的表示稱為數據的存儲結構或數據的物理結構。例：復數z=3.0-2.3i的兩種表示見下圖。3.0-2.303000302：：：-2.33.00415041506130611：：：順序映象順序存儲結構非順序映象鏈式存儲結構指針(Pointer)14數據類型數據類型就是在程序設計語言中，變量所具有的數據種類。換句話說，數據類型是一個值的集合和定義在這個值集上的一組操作的總稱。例如：在FORTRAN語言中，變量的數據類型有整型、實型、和復數型例如：在C++語言中，數據類型：基本類型和構造類型整型、浮點型、字符型數組、結構、聯合、指針、枚舉型、自定義15數據結構的分類數據結構邏輯結構存儲結構非線性結構線性結構線性表棧和隊列串數組廣義表樹、二叉樹圖文件順序存儲結構（順序映象）鏈式存儲結構（非順序映象）161.3抽象數據類型的表示與實現抽象數據類型(AbstractDataType簡稱ADT)是指一個數學模型以及定義在該模型上的一組操作。抽象數據類型可用以下三元組表示

ADT=（D，S，P）D是數據對象S是D上關系的有限集P是對D的基本操作集。17抽象數據類型三元組例：ADTTriplet{

數據對象：D={e1,e2,e3|e1,e2,e3∈ElemSet}

數據關系：R1={<e1,e2>,<e2,e3>}

基本操作：

InitTriplet(&T,v1,v2,v3);DestroyTriplet(&T);Get(T,i,&e);Put(&T,i,e);IsAscending(T);IsDescending(T);Max(T,&e);Min(T,&e);}ADTTriplet線性結構18類C語言可以采用介于偽碼和C語言之間的類C語言作為抽象數據類型的描述工具。這使得數據結構和算法的描述和討論簡明清晰，不拘泥于C語言的細節，又能夠容易轉換成C或者C++程序。類C語言精選了C語言的一個核心子集，同時作了若干擴充修改，增強了語言的描述功能。關于類C語言見教材p10-p13191.4算法和算法分析算法：是對特定問題求解步驟的一種描述，是指令的有限序列，其中每一條指令表示一個或多個操作。算法具有以下五個特性：有窮性一個算法必須總是在執行有窮步之后結束，且每一步都在有窮時間內完成。確定性算法中每一條指令必須有確切的含義。不存在二義性。可行性一個算法是可行的。即算法描述的操作都是可以通過已經實現的基本運算執行有限次來實現的。輸入一個算法有零個或多個輸入，這些輸入取自于某個特定的對象集合。輸出一個算法有一個或多個輸出，這些輸出是同輸入有著某些特定關系的量。20算法設計的要求正確性算法應滿足具體問題的需求。“正確”有四個層次：

(a)不含語法錯誤；(b)對幾組輸入正確；

(c)對精心設計的測試輸入正確；(d)對一切合法輸入正確可讀性算法應該好讀。以有利于閱讀者對程序的理解。健狀性算法應具有容錯處理。當輸入非法數據時，算法應對其作出反應，而不是產生莫名其妙的輸出結果。效率與存儲量需求效率指的是算法執行的時間；存儲量需求指算法執行過程中所需要的最大存儲空間。一般，這兩者與問題的規模有關。21算法效率的度量算法執行時間需通過依據該算法編制的程序在計算機上運行時所消耗的時間來度量。通常有兩種方法：事后統計的方法收集此算法的執行時間和實際占用空間的統計資料事前分析估算的方法求出該算法的一個時間界限函數 例：for(i=1;i<=n;++i) for(j=1;j<=n;++j){ c[i][j]=0; for(k=1;k<=n;++k) c[i][j]+=a[i][k]*b[k][j]; }一個算法是由控制結構（順序、分支和循環三種）和原操作（指固有數據類型的操作）構成的，則算法時間取決于兩者的綜合效果。為了便于比較同一問題的不同算法，通常的做法是，從算法中選取一種對于所研究的問題來說是基本操作的原操作，以該基本操作重復執行的次數作為算法的時間量度。撇開與計算機硬件、軟件有關的因素，可以認為一個特定算法“運行工作量”的大小只依賴于問題的規模（通常用整數量n表示）。22漸近時間復雜度一般情況下，算法中基本操作重復執行的次數是問題規模n的某個函數，算法的時間量度記作

T(n)=O(f(n))

稱作算法的漸近時間復雜度(AsymptoticTimeComplexity)。定義：如果g(n)是正整數n的一個函數，若存在兩個正常數c和n0，對于所有的n≧n0，有|g(n)|≦c|f(n)|，則記作g(n)=O(f(n))。23頻度頻度是指語句重復執行的次數。例1{++x;s=0;}

將x自增看成是基本操作，則語句頻度為１，即時間復雜度為Ｏ(1)。 如果將s=0也看成是基本操作，則語句頻度為1，其時間復雜度仍為Ｏ(1)，即常量階。例2for(i=1;i<=n;++i){++x;s+=x;}

語句頻度為：n其時間復雜度為：O(n)，即時間復雜度為線性階。24時間復雜度舉例例3for(i=1;i<=n;++i)

for(j=1;j<=n;++j){++x;s+=x;}

語句頻度為：n2,其時間復雜度為：O(n2)，即時間復雜度為平方階。例4for(i=0;i<=n-1;++i)for(j=0;j<=i;++j) a[i][j]=0;

時間復雜度為：O(n2)i=0:賦值１次i=2:賦值3次i=n-1:賦值n次……………..+1+2+3+…+n=(1+n)n/2=n2/2+n/225時間復雜度的不同量級最常用的六種多項式時間及其關系為：O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)最常用的三種指數時間及其關系為：O(2n)<O(n!)<O(nn)當n取得很大時，指數時間算法和多項式時間算法在所需時間上非常懸殊（