數(shù)據(jù)結(jié)構(gòu)課件01

第一章緒論精英專升本1.1數(shù)據(jù)結(jié)構(gòu)討論的范疇1.2基本概念1.4算法和算法分析1.3抽象數(shù)據(jù)類型1.1

數(shù)據(jù)結(jié)構(gòu)討論的范疇NiklausWirth：

Algorithm

+DataStructures=Programs程序設(shè)計:算法:數(shù)據(jù)結(jié)構(gòu):為計算機處理問題編制一組指令集

處理問題的策略問題的數(shù)學模型在現(xiàn)實社會中存在著許多非數(shù)值計算問題，其數(shù)學模型難以用數(shù)學方程描述。例人機對奕問題樹……..……..…...…...…...…...概括地說：

數(shù)據(jù)結(jié)構(gòu)是一門討論“描述現(xiàn)實世界實體的數(shù)學模型(非數(shù)值計算)及其上的操作在計算機中如何表示和實現(xiàn)”的學科。（P3）1.2

基本概念和術(shù)語一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)二、數(shù)據(jù)類型三、抽象數(shù)據(jù)類型一、數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)所有能被輸入到計算機中，且能被計算機處理的符號的集合。數(shù)據(jù):是計算機操作的對象的總稱。是計算機處理的信息的某種特定的符號表示形式。是數(shù)據(jù)（集合）中的一個“個體”數(shù)據(jù)元素:是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位。有時，一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成。數(shù)據(jù)對象是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集

數(shù)據(jù)項：是數(shù)據(jù)結(jié)構(gòu)中討論的最小單位例如：描述一個運動員的數(shù)據(jù)元素可以是姓名俱樂部名稱出生日期參加日期職務(wù)業(yè)績?nèi)咧g的關(guān)系：數(shù)據(jù)對象>數(shù)據(jù)元素>數(shù)據(jù)項數(shù)據(jù)元素可以是數(shù)據(jù)項的集合例，在2行3列的二維數(shù)組{a1,a2,a3,a4,a5,a6}中六個元素之間存在兩個關(guān)系:行的次序關(guān)系:列的次序關(guān)系:row={<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>}col={<a1,a4>,<a2,a5>,<a3,a6>}

a1a3a2

a5a4a6a1a2a3a4a5a6

數(shù)據(jù)結(jié)構(gòu)：帶結(jié)構(gòu)的數(shù)據(jù)元素的集合再例，在一維數(shù)組{a1,a2,a3,a4,a5,a6}的數(shù)據(jù)元素之間存在如下的次序關(guān)系:{<ai,ai+1>|i=1,2,3,4,5}

或者說，數(shù)據(jù)結(jié)構(gòu)是相互之間存在著某種關(guān)系的數(shù)據(jù)元素的集合?？梢?，不同的“關(guān)系”構(gòu)成不同的“結(jié)構(gòu)”數(shù)據(jù)結(jié)構(gòu)：有關(guān)系的數(shù)據(jù)元素的集合數(shù)據(jù)結(jié)構(gòu)的形式定義為:數(shù)據(jù)結(jié)構(gòu)是一個二元組Data_Structures=(D,S)其中:D是數(shù)據(jù)元素的有限集，

S是D上關(guān)系的有限集。1.數(shù)據(jù)結(jié)構(gòu)被形式定義為（D，S），其中D是（）的有限集合，S是D上的（）有限集合。A、算法B、數(shù)據(jù)元素C、數(shù)據(jù)操作D、邏輯關(guān)系E、操作F、映象G、存儲H、關(guān)系BH歷年真題：數(shù)據(jù)結(jié)構(gòu)包括以下幾個方面：數(shù)據(jù)元素之間的邏輯關(guān)系，即邏輯結(jié)構(gòu)數(shù)據(jù)元素及其關(guān)系在計算機存儲器中的存儲方式，即數(shù)據(jù)的存儲結(jié)構(gòu)施加在該數(shù)據(jù)上的操作，即數(shù)據(jù)的運算數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)密切相關(guān) 算法設(shè)計 邏輯結(jié)構(gòu) 算法實現(xiàn) 存儲結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)—只抽象反映數(shù)據(jù)元素的邏輯關(guān)系劃分方法一（1）線性結(jié)構(gòu)有且僅有一個開始和一個終端結(jié)點，并且所有結(jié)點都最多只有一個直接前趨和一個后繼。例如：線性表、棧、隊列、串（2）非線性結(jié)構(gòu)一個結(jié)點可能有多個直接前趨和直接后繼。例如：樹、圖線性結(jié)構(gòu)——一個對一個，如線性表、棧、隊列樹形結(jié)構(gòu)——一個對多個，如樹集合——數(shù)據(jù)元素間除“同屬于一個集合”外，無其它關(guān)系圖形結(jié)構(gòu)——多個對多個，如圖劃分方法二數(shù)據(jù)的存儲結(jié)構(gòu)(物理結(jié)構(gòu))

——

邏輯結(jié)構(gòu)在存儲器中的映象“數(shù)據(jù)元素”的映象？“關(guān)系”的映象？數(shù)據(jù)元素的映象方法：用二進制位(bit)的位串表示數(shù)據(jù)元素(321)10=(501)8=(101000001)2關(guān)系的映象方法：（表示

x,y

的方法）順序映象(順序存儲方法)以相對的存儲位置表示后繼關(guān)系鏈式映象(鏈式存儲方法)

不要求在邏輯上相鄰的結(jié)點在物理位置上也相鄰，結(jié)點間的邏輯關(guān)系由附加的指針字段表示?！舅饕鎯Α俊旧⒘写鎯Α吭豱……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲地址存儲內(nèi)容Loc(元素i)=L0+（i-1)*m順序存儲結(jié)構(gòu)存儲地址存儲內(nèi)容指針

1345元素1

1400

1346元素4∧

…….

……..

…….

1400元素2

1536

…….

……..

…….

1536元素3

1346鏈式存儲結(jié)構(gòu)元素2元素1元素3∧元素41400153613461345hh

數(shù)據(jù)的邏輯結(jié)構(gòu)

數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的運算：插入、刪除、修改、查找、排序

線性結(jié)構(gòu)

非線性結(jié)構(gòu)

順序存儲

鏈式存儲線性表棧、隊列串、數(shù)組樹形結(jié)構(gòu)圖形結(jié)構(gòu)邏輯結(jié)構(gòu)唯一存儲結(jié)構(gòu)不唯一運算的實現(xiàn)依賴于存儲結(jié)構(gòu)小結(jié)：數(shù)據(jù)結(jié)構(gòu)的三個方面1.下列與數(shù)據(jù)元素有關(guān)的敘述中，哪一個是不正確的（）。A．數(shù)據(jù)元素是數(shù)據(jù)的基本單位，即數(shù)據(jù)集合中的個體B．數(shù)據(jù)元素是有獨立含義的數(shù)據(jù)最小單位C．數(shù)據(jù)元素又稱結(jié)點D．數(shù)據(jù)元素又稱作記錄2.下列關(guān)于數(shù)據(jù)的邏輯結(jié)構(gòu)的敘述中，哪一個是正確的（）。A．數(shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)據(jù)間關(guān)系的描述B．數(shù)據(jù)的邏輯結(jié)構(gòu)反映了數(shù)據(jù)在計算機中的存儲方式C．數(shù)據(jù)的邏輯結(jié)構(gòu)分為順序結(jié)構(gòu)和鏈式結(jié)構(gòu)D．數(shù)據(jù)的邏輯結(jié)構(gòu)分為靜態(tài)結(jié)構(gòu)和動態(tài)結(jié)構(gòu)BA3.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（）。A、動態(tài)和靜態(tài)結(jié)構(gòu)B、緊湊接和非緊湊結(jié)構(gòu)C、線性與非線性結(jié)構(gòu)D、內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)C數(shù)據(jù)的運算：插入、刪除、修改、查找、排序數(shù)據(jù)類型

是一個值的集合和定義在此集合上的一組操作的總稱。

不同類型的變量，其所能取的值的范圍不同，所能進行的操作不同。二、數(shù)據(jù)類型例如，C

語言中提供的基本數(shù)據(jù)類型有:整型int浮點型float字符型char邏輯型bool

（C++語言）雙精度型double實型（C++語言）二、數(shù)據(jù)類型數(shù)據(jù)結(jié)構(gòu)課程所研究的問題均運用到“結(jié)構(gòu)體”。在C語言中定義結(jié)構(gòu)體的一般格式是：struct

結(jié)構(gòu)體類型名

{ 類型名1變量名1；//數(shù)據(jù)子域 類型名2變量名2；

…… 類型名n變量名n；}；補充：結(jié)構(gòu)體的定義在使用時必須聲明一個具體的結(jié)構(gòu)體類型的變量，聲明創(chuàng)建一個結(jié)構(gòu)體變量的方法是：

struct

結(jié)構(gòu)體類型名結(jié)構(gòu)體變量名；例如：

struct

ElemType /*定義結(jié)構(gòu)體*/{intnum;charname[10];};struct

ElemTypex； /*聲明結(jié)構(gòu)體變量x*/

另外有一種方法是使用typedef

語句定義結(jié)構(gòu)體，在聲明結(jié)構(gòu)體變量時可以不寫struct，使得書寫更加簡便。例如：

typedef

struct{intnum;charname[10];}ElemType；

ElemType就是一個新的類型名，并且是結(jié)構(gòu)體類型名。聲明變量x的語句是：

ElemTypex;(1)通過“結(jié)構(gòu)體變量名.數(shù)據(jù)子域”可以訪問數(shù)據(jù)子域。例typedef

struct /*定義結(jié)構(gòu)體Student*/{longnum; /*學號*/

intx; /*成績*/charname[10]; /*姓名*/}Student;

補充：結(jié)構(gòu)體的使用Students1;s1.num=1001;/*為s1的數(shù)據(jù)子域提供數(shù)據(jù)*/s1.x=83;補充：結(jié)構(gòu)體的使用(2)通過“結(jié)構(gòu)體指針->數(shù)據(jù)子域”訪問數(shù)據(jù)域。在實際問題中還會使用到指向結(jié)構(gòu)體的指針，通過以下語句段可以說明結(jié)構(gòu)體指針的一般用法。Student*p; /*聲明指針變量p*/p=(Student*)malloc(sizeof(Student));/*分配存儲單元，首地址賦給p指針*/p->num=101;p->x=83;strcpy(p->name,"李明");numxnamep10183李明三、抽象數(shù)據(jù)類型

(AbstractDataType

簡稱ADT)是指一個數(shù)學模型以及定義在此數(shù)學模型上的一組操作。抽象數(shù)據(jù)類型可以用以下的三元組來表示：

ADT=（D，S，P）數(shù)據(jù)對象D上的關(guān)系集D上的操作集ADT抽象數(shù)據(jù)類型名{

數(shù)據(jù)對象：<數(shù)據(jù)對象的定義>

數(shù)據(jù)關(guān)系：<數(shù)據(jù)關(guān)系的定義>

基本操作：<基本操作的定義>}ADT抽象數(shù)據(jù)類型名ADT常用定義格式例如，抽象數(shù)據(jù)類型復數(shù)的定義：

數(shù)據(jù)對象：

D＝{e1,e2｜e1,e2∈RealSet}

數(shù)據(jù)關(guān)系：

R1＝{<e1,e2>|e1是復數(shù)的實數(shù)部分

|e2

是復數(shù)的虛數(shù)部分}

ADTComplex{基本操作：

AssignComplex(&Z,v1,v2)操作結(jié)果：構(gòu)造復數(shù)Z,其實部和虛部分別被賦以參數(shù)v1和v2的值。

DestroyComplex(&Z)操作結(jié)果：復數(shù)Z被銷毀。

GetReal(Z,&realPart)初始條件：復數(shù)已存在。操作結(jié)果：用realPart返回復數(shù)Z的實部值。

GetImag(Z,&ImagPart)初始條件：復數(shù)已存在。操作結(jié)果：用ImagPart返回復數(shù)Z的虛部值。

Add(z1,z2,&sum)初始條件：z1,z2是復數(shù)。操作結(jié)果：用sum返回兩個復數(shù)z1,z2的和值。}ADTComplex1.4算法和算法分析一、算法//二、算法設(shè)計的原則//三、算法效率的衡量方法和準則四、算法的存儲空間需求算法（algorithm）—解決某一特定問題的具體步驟的描述，是指令的有限序列。算法特性——有窮性一個算法必須在執(zhí)行有限步驟之后結(jié)束確定性算法的每一步必須是確切定義的，不能產(chǎn)生二義性可行性算法是能行的輸入一個算法有零個或多個輸入輸出一個算法有一個或多個輸出算法的描述—采用類C語言算法的評價—衡量算法優(yōu)劣的標準正確性(correctness)可讀性(readability)健壯性(robustness)效率與低存儲量三、算法效率的衡量方法和準則一個特定算法的“運行工作量”的大小，只依賴于問題的規(guī)模（通常用整數(shù)量n表示），或者說，它是問題規(guī)模的函數(shù)。

假如，隨著問題規(guī)模n的增長，算法執(zhí)行時間的增長率和f(n)

的增長率相同，則可記作：T(n)=

O(f(n))稱T(n)為算法的(漸近)時間復雜度。10n2+4n+2=O(n2)它表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)的增長率相同。漸進符號（O）的定義：當且僅當存在一個正的常數(shù)C和n0

，使得對所有的

nn0

，有

T(n)

Cf(n)，則

T(n)=O(f(n))3n+2=O(n)/*3n+24nforn2*/3n+3=O(n)/*3n+34nforn3*/100n+6=O(n)

/*100n+6101nforn10*/10n2+4n+2=O(n2)/*10n2+4n+211n2forn5*/6*2n+n2=O(2n)

/*6*2n+n27*2nforn4*/如何估算算法的時間復雜度？

從算法中選取一種對于所研究的問題來說是基本操作

的原操作，以該基本操作在算法中重復執(zhí)行的次數(shù)作為算法運行時間的衡量準則。n*n階矩陣加法：for(i=0;i<n;i++) for(j=0;j<n;j++)

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

語句的頻度（FrequencyCount):重復執(zhí)行的次數(shù)：n*n;T(n)=O(n2)即：矩陣加法的運算量和問題的規(guī)模n的平方是同一個量級變量計數(shù)x=0;y=0;for(intk=0;k<n;k++)x++;for(inti=0;i<n;i++)for(intj=0;j<n;j++)y++;T1(n)=O(1)T2(n)=O(n)T3(n)=O(n2)T(n)=T1(n)+T2(n)+T3(n)=O(max(1,n,n2))=O(n2)例2：for(i=1;i<=n;i++) for(j=1;j<=i;j++)for(k=1;k<=j;k++)

x=x+1;語句頻度

=例3：分析以下程序段的時間復雜度i=1;①while(i<=n) i=i*2;②即f(n)≤log2n，取最大值f(n)=log2n所以該程序段的時間復雜度T(n)=O(log2n)例4：順序查找，在數(shù)組a[i]中查找第一個值等于e的元素，返回其所在下標。

for(i=0;i<n;i++)if(a[i]==e)returni;return0;有的情況下，算法中基本操作重復執(zhí)行的次數(shù)還隨問題的輸入數(shù)據(jù)集不同而不同

最好情況：1次

最壞情況：n

平均時間復雜度為：O(n)復雜度高復雜度低時間復雜度T(n)按數(shù)量級遞增順序為：1、指數(shù)時間的關(guān)系為：O(2n)<O(n!)<O(nn)

3、幾個比較重要的時間復雜度排序：

2、四、算法的存儲空間需求算法的空間復雜度定義為:

表示隨著問題規(guī)模n的增大，算法運行所需存儲量的增長率與g(n)的增長率相同。S(n)=O(g(n))算法的存儲量包括:1．輸入數(shù)據(jù)所占空間2．程序本