數(shù)據(jù)結(jié)構(gòu)-chap13.5學(xué)分

1數(shù)據(jù)結(jié)構(gòu)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院孫廷凱

2課程意義1001001111姓名學(xué)號(hào)年齡張三06010120李四06010219………………ABCDEFG“好”的程序算法+數(shù)據(jù)結(jié)構(gòu)=程序3內(nèi)容安排第1章緒論2課時(shí)第2章線性表8課時(shí)第3章棧和隊(duì)列4

課時(shí)第4章串

2

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

Data_Structure=(D，S)例1.4

在計(jì)算機(jī)科學(xué)中，復(fù)數(shù)可取如下定義：復(fù)數(shù)是一種數(shù)據(jù)結(jié)構(gòu)：Complex=（C，R）

D是數(shù)據(jù)元素的有限集S是D上關(guān)系的有限集C是含兩個(gè)實(shí)數(shù)的集合{c1，c2}R={<c1,c2>}，這里有序偶<c1,c2>表示c1是復(fù)數(shù)的實(shí)部，c2是復(fù)數(shù)的虛部13數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)或數(shù)據(jù)的物理結(jié)構(gòu)。例：復(fù)數(shù)z=3.0-2.3i的兩種表示見下圖。3.0-2.303000302：：：-2.33.00415041506130611：：：順序映象順序存儲(chǔ)結(jié)構(gòu)非順序映象鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)指針(Pointer)14數(shù)據(jù)類型數(shù)據(jù)類型就是在程序設(shè)計(jì)語(yǔ)言中，變量所具有的數(shù)據(jù)種類。換句話說(shuō)，數(shù)據(jù)類型是一個(gè)值的集合和定義在這個(gè)值集上的一組操作的總稱。例如：在FORTRAN語(yǔ)言中，變量的數(shù)據(jù)類型有整型、實(shí)型、和復(fù)數(shù)型例如：在C++語(yǔ)言中，數(shù)據(jù)類型：基本類型和構(gòu)造類型整型、浮點(diǎn)型、字符型數(shù)組、結(jié)構(gòu)、聯(lián)合、指針、枚舉型、自定義15數(shù)據(jù)結(jié)構(gòu)的分類數(shù)據(jù)結(jié)構(gòu)邏輯結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)非線性結(jié)構(gòu)線性結(jié)構(gòu)線性表?xiàng)：完?duì)列串?dāng)?shù)組廣義表樹、二叉樹圖文件順序存儲(chǔ)結(jié)構(gòu)（順序映象）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（非順序映象）161.3抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)抽象數(shù)據(jù)類型(AbstractDataType簡(jiǎn)稱ADT)是指一個(gè)數(shù)學(xué)模型以及定義在該模型上的一組操作。抽象數(shù)據(jù)類型可用以下三元組表示

ADT=（D，S，P）D是數(shù)據(jù)對(duì)象S是D上關(guān)系的有限集P是對(duì)D的基本操作集。17抽象數(shù)據(jù)類型三元組例：ADTTriplet{

數(shù)據(jù)對(duì)象：D={e1,e2,e3|e1,e2,e3∈ElemSet}

數(shù)據(jù)關(guān)系：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線性結(jié)構(gòu)18類C語(yǔ)言可以采用介于偽碼和C語(yǔ)言之間的類C語(yǔ)言作為抽象數(shù)據(jù)類型的描述工具。這使得數(shù)據(jù)結(jié)構(gòu)和算法的描述和討論簡(jiǎn)明清晰，不拘泥于C語(yǔ)言的細(xì)節(jié)，又能夠容易轉(zhuǎn)換成C或者C++程序。類C語(yǔ)言精選了C語(yǔ)言的一個(gè)核心子集，同時(shí)作了若干擴(kuò)充修改，增強(qiáng)了語(yǔ)言的描述功能。關(guān)于類C語(yǔ)言見教材p10-p13191.4算法和算法分析算法：是對(duì)特定問(wèn)題求解步驟的一種描述，是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。算法具有以下五個(gè)特性：有窮性一個(gè)算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時(shí)間內(nèi)完成。確定性算法中每一條指令必須有確切的含義。不存在二義性?？尚行砸粋€(gè)算法是可行的。即算法描述的操作都是可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)的。輸入一個(gè)算法有零個(gè)或多個(gè)輸入，這些輸入取自于某個(gè)特定的對(duì)象集合。輸出一個(gè)算法有一個(gè)或多個(gè)輸出，這些輸出是同輸入有著某些特定關(guān)系的量。20算法設(shè)計(jì)的要求正確性算法應(yīng)滿足具體問(wèn)題的需求?！罢_”有四個(gè)層次：

(a)不含語(yǔ)法錯(cuò)誤；(b)對(duì)幾組輸入正確；

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

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

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

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

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

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

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

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