數據結構課件01

第一章緒論精英專升本1.1數據結構討論的范疇1.2基本概念1.4算法和算法分析1.3抽象數據類型1.1

數據結構討論的范疇NiklausWirth：

Algorithm

+DataStructures=Programs程序設計:算法:數據結構:為計算機處理問題編制一組指令集

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

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

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

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

a1a3a2

a5a4a6a1a2a3a4a5a6

數據結構：帶結構的數據元素的集合再例，在一維數組{a1,a2,a3,a4,a5,a6}的數據元素之間存在如下的次序關系:{<ai,ai+1>|i=1,2,3,4,5}

或者說，數據結構是相互之間存在著某種關系的數據元素的集合。可見，不同的“關系”構成不同的“結構”數據結構：有關系的數據元素的集合數據結構的形式定義為:數據結構是一個二元組Data_Structures=(D,S)其中:D是數據元素的有限集，

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

——

邏輯結構在存儲器中的映象“數據元素”的映象？“關系”的映象？數據元素的映象方法：用二進制位(bit)的位串表示數據元素(321)10=(501)8=(101000001)2關系的映象方法：（表示

x,y

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

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

1345元素1

1400

1346元素4∧

…….

……..

…….

1400元素2

1536

…….

……..

…….

1536元素3

1346鏈式存儲結構元素2元素1元素3∧元素41400153613461345hh

數據的邏輯結構

數據的存儲結構數據的運算：插入、刪除、修改、查找、排序

線性結構

非線性結構

順序存儲

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

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

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

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

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

結構體類型名

{ 類型名1變量名1；//數據子域 類型名2變量名2；

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

struct

結構體類型名結構體變量名；例如：

struct

ElemType /*定義結構體*/{intnum;charname[10];};struct

ElemTypex； /*聲明結構體變量x*/

另外有一種方法是使用typedef

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

typedef

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

ElemType就是一個新的類型名，并且是結構體類型名。聲明變量x的語句是：

ElemTypex;(1)通過“結構體變量名.數據子域”可以訪問數據子域。例typedef

struct /*定義結構體Student*/{longnum; /*學號*/

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

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

(AbstractDataType

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

ADT=（D，S，P）數據對象D上的關系集D上的操作集ADT抽象數據類型名{

數據對象：<數據對象的定義>

數據關系：<數據關系的定義>

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

數據對象：

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

數據關系：

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

|e2

是復數的虛數部分}

ADTComplex{基本操作：

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

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

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

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

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

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

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

O(f(n))稱T(n)為算法的(漸近)時間復雜度。10n2+4n+2=O(n2)它表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)的增長率相同。漸進符號（O）的定義：當且僅當存在一個正的常數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í)行的次數作為算法運行時間的衡量準則。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í)行的次數：n*n;T(n)=O(n2)即：矩陣加法的運算量和問題的規(guī)模n的平方是同一個量級變量計數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：順序查找，在數組a[i]中查找第一個值等于e的元素，返回其所在下標。

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

最好情況：1次

最壞情況：n

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

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

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

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