數(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è)計(jì):算法:數(shù)據(jù)結(jié)構(gòu):為計(jì)算機(jī)處理問(wèn)題編制一組指令集

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

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

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

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

或者說(shuō)，數(shù)據(jù)結(jié)構(gòu)是相互之間存在著某種關(guān)系的數(shù)據(jù)元素的集合?？梢姡煌摹瓣P(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)是一個(gè)二元組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、存儲(chǔ)H、關(guān)系BH歷年真題：數(shù)據(jù)結(jié)構(gòu)包括以下幾個(gè)方面：數(shù)據(jù)元素之間的邏輯關(guān)系，即邏輯結(jié)構(gòu)數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器中的存儲(chǔ)方式，即數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)施加在該數(shù)據(jù)上的操作，即數(shù)據(jù)的運(yùn)算數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)密切相關(guān) 算法設(shè)計(jì) 邏輯結(jié)構(gòu) 算法實(shí)現(xiàn) 存儲(chǔ)結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)—只抽象反映數(shù)據(jù)元素的邏輯關(guān)系劃分方法一（1）線性結(jié)構(gòu)有且僅有一個(gè)開始和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)都最多只有一個(gè)直接前趨和一個(gè)后繼。例如：線性表、棧、隊(duì)列、串（2）非線性結(jié)構(gòu)一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前趨和直接后繼。例如：樹、圖線性結(jié)構(gòu)——一個(gè)對(duì)一個(gè)，如線性表、棧、隊(duì)列樹形結(jié)構(gòu)——一個(gè)對(duì)多個(gè)，如樹集合——數(shù)據(jù)元素間除“同屬于一個(gè)集合”外，無(wú)其它關(guān)系圖形結(jié)構(gòu)——多個(gè)對(duì)多個(gè)，如圖劃分方法二數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)(物理結(jié)構(gòu))

——

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

x,y

的方法）順序映象(順序存儲(chǔ)方法)以相對(duì)的存儲(chǔ)位置表示后繼關(guān)系鏈?zhǔn)接诚?鏈?zhǔn)酱鎯?chǔ)方法)

不要求在邏輯上相鄰的結(jié)點(diǎn)在物理位置上也相鄰，結(jié)點(diǎn)間的邏輯關(guān)系由附加的指針字段表示。【索引存儲(chǔ)】【散列存儲(chǔ)】元素n……..元素i……..元素2元素1LoLo+mLo+(i-1)*mLo+（n-1)*m存儲(chǔ)地址存儲(chǔ)內(nèi)容Loc(元素i)=L0+（i-1)*m順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)地址存儲(chǔ)內(nèi)容指針

1345元素1

1400

1346元素4∧

…….

……..

…….

1400元素2

1536

…….

……..

…….

1536元素3

1346鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)元素2元素1元素3∧元素41400153613461345hh

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

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

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

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

順序存儲(chǔ)

鏈?zhǔn)酱鎯?chǔ)線性表?xiàng)?、?duì)列串、數(shù)組樹形結(jié)構(gòu)圖形結(jié)構(gòu)邏輯結(jié)構(gòu)唯一存儲(chǔ)結(jié)構(gòu)不唯一運(yùn)算的實(shí)現(xiàn)依賴于存儲(chǔ)結(jié)構(gòu)小結(jié)：數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面1.下列與數(shù)據(jù)元素有關(guān)的敘述中，哪一個(gè)是不正確的（）。A．?dāng)?shù)據(jù)元素是數(shù)據(jù)的基本單位，即數(shù)據(jù)集合中的個(gè)體B．?dāng)?shù)據(jù)元素是有獨(dú)立含義的數(shù)據(jù)最小單位C．?dāng)?shù)據(jù)元素又稱結(jié)點(diǎn)D．?dāng)?shù)據(jù)元素又稱作記錄2.下列關(guān)于數(shù)據(jù)的邏輯結(jié)構(gòu)的敘述中，哪一個(gè)是正確的（）。A．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)是數(shù)據(jù)間關(guān)系的描述B．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)反映了數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)方式C．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)分為順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)D．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)分為靜態(tài)結(jié)構(gòu)和動(dòng)態(tài)結(jié)構(gòu)BA3.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（）。A、動(dòng)態(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ù)的運(yùn)算：插入、刪除、修改、查找、排序數(shù)據(jù)類型

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

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

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

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

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

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

…… 類型名n變量名n；}；補(bǔ)充：結(jié)構(gòu)體的定義在使用時(shí)必須聲明一個(gè)具體的結(jié)構(gòu)體類型的變量，聲明創(chuàng)建一個(gè)結(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

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

typedef

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

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

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

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

intx; /*成績(jī)*/charname[10]; /*姓名*/}Student;

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

(AbstractDataType

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

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

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

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

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

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

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

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

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

|e2

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

ADTComplex{基本操作：

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

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

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

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

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

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

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

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

，使得對(duì)所有的

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*/如何估算算法的時(shí)間復(fù)雜度？

從算法中選取一種對(duì)于所研究的問(wèn)題來(lái)說(shuō)是基本操作

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

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

語(yǔ)句的頻度（FrequencyCount):重復(fù)執(zhí)行的次數(shù)：n*n;T(n)=O(n2)即：矩陣加法的運(yùn)算量和問(wèn)題的規(guī)模n的平方是同一個(gè)量級(jí)變量計(jì)數(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;語(yǔ)句頻度

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

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

最好情況：1次

最壞情況：n

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

3、幾個(gè)比較重要的時(shí)間復(fù)雜度排序：

2、四、算法的存儲(chǔ)空間需求算法的空間復(fù)雜度定義為:

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