第一章緒論基本概念和術(shù)語

數(shù)據(jù):

所有能被輸入到計(jì)算機(jī)中，且能被計(jì)算機(jī)處理的符號(hào)的集合數(shù)據(jù)項(xiàng)：數(shù)據(jù)結(jié)構(gòu)中討論的最小單位,數(shù)據(jù)元素是數(shù)據(jù)項(xiàng)的集合，數(shù)據(jù)是數(shù)據(jù)元素的集合數(shù)據(jù)元素:

是數(shù)據(jù)(一個(gè)集合)中的一個(gè)“個(gè)體”，是數(shù)據(jù)結(jié)構(gòu)中討論的基本單位001高等數(shù)學(xué)華羅庚S01……002線性代數(shù)鑾汝書L01……003高等數(shù)學(xué)鄭杭生

S01……004離散數(shù)學(xué)耿素云S02………………………………序號(hào)書名作者書名……數(shù)據(jù)元素?cái)?shù)據(jù)項(xiàng)001002003004……數(shù)據(jù)元素?cái)?shù)據(jù)結(jié)構(gòu)

：數(shù)據(jù)以及數(shù)據(jù)之間的關(guān)系基本概念和術(shù)語

集合線性結(jié)構(gòu)樹形結(jié)構(gòu)圖狀結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)：帶結(jié)構(gòu)的數(shù)據(jù)元素的集合，這里的結(jié)構(gòu)是指數(shù)據(jù)元素之間存在的一種約束關(guān)系例1.一個(gè)含12位數(shù)的十進(jìn)制數(shù)可以用三個(gè)4位的十進(jìn)制數(shù)表示3214,6587,9345─

a1(3214),a2(6587),a3(9345)在a1、a2和a3之間存在“次序”關(guān)系

<a1,a2>，<a2,a3>3214，6587，9345≠6587，3214，9345

a1

a2

a3

a2

a1

a3例2.由6個(gè)數(shù)組成一個(gè)2行3列的二維數(shù)組{a1,a2,a3,a4,a5,a6}行的次序關(guān)系:row={<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>}列的次序關(guān)系:col={<a1,a4>,<a2,a5>,<a3,a6>}a1a2a3a4a5a6例3，一維數(shù)組{a1,a2,a3,a4,a5,a6}中存在次序關(guān)系:ai可見：不同的關(guān)系構(gòu)成不同的結(jié)構(gòu)，而數(shù)據(jù)結(jié)構(gòu)就是帶結(jié)構(gòu)的數(shù)據(jù)元素的集合{<ai,ai+1>|i=1,2,3,4,5}

數(shù)據(jù)結(jié)構(gòu)的形式定義為:

數(shù)據(jù)結(jié)構(gòu)是一個(gè)二元組Data_Structures=(D,S)

其中:D是數(shù)據(jù)元素的有限集，

S是D上關(guān)系的有限集。抽象數(shù)據(jù)類型

(AbstractDataType簡(jiǎn)稱ADT)

ADT是指一個(gè)數(shù)學(xué)模型以及定義在此數(shù)學(xué)模型上的一組操作,可用三元組表示,其中，D是數(shù)據(jù)對(duì)象，S是D上的關(guān)系集，P是對(duì)D的基本操作集ADT

抽象數(shù)據(jù)類型名{

數(shù)據(jù)對(duì)象D：〈數(shù)據(jù)對(duì)象的定義〉

數(shù)據(jù)關(guān)系S：〈數(shù)據(jù)關(guān)系的定義〉

基本操作P：〈基本操作的定義〉}ADT

抽象數(shù)據(jù)類型名（D，S，P)例.抽象數(shù)據(jù)類型復(fù)數(shù)的定義：(兩個(gè)實(shí)數(shù)的有序偶對(duì)3+7i2+5i5+8iADTComplex{

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

數(shù)據(jù)關(guān)系：R1={<e1,e2>|e1是實(shí)數(shù)部分,e2是虛數(shù)部分}

基本操作：

InitComplex(&Z,v1,v2)

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

GetReal(Z,&realPart)

操作結(jié)果：用realPart返回復(fù)數(shù)Z的實(shí)部值。

GetImag(Z,&ImagPart)

操作結(jié)果：用ImagPart返回復(fù)數(shù)Z的虛部值。

Add(z1,z2,&sum)

操作結(jié)果：用sum返回兩個(gè)復(fù)數(shù)z1,z2的和值。}ADTComplex時(shí)間復(fù)雜度

看執(zhí)行的代碼和N之間的關(guān)系,把N看作無窮大假如，隨著問題規(guī)模n的增長，算法執(zhí)行時(shí)間的增長率和f(n)的增長率相同，則可記作：T(n)=o(f(n))稱T(n)為算法的(漸近)時(shí)間復(fù)雜度如何估算算法的時(shí)間復(fù)雜度？即如何求f(n)從算法中選取一種對(duì)于所研究的問題來說是基本操作的原操作，以該基本操作在算法中重復(fù)執(zhí)行的次數(shù)作為算法運(yùn)行時(shí)間的衡量準(zhǔn)則

for(i=0;i<n;++i)a=0;for(j=0;j<n;++j)printf(“hello!”);T(n)=O(n)例一

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];}基本操作:乘法操作時(shí)間復(fù)雜度:O(n3)例二voidselect_sort(inta[],intn){//將a中整數(shù)序列重新排列成自小至大有序的整數(shù)序列

for(i=0;i<n-1;++i){j=i;for(k=i-1;k<n;++k)if(a[k]<a[j])j=k;if(j!=i)a[j]←→a[i]}//select_sort}基本操作:比較(數(shù)據(jù)元素)操作時(shí)間復(fù)雜度:O(n2)

例三

voidbubble_sort(inta[],intn){

//將a中整數(shù)序列重新排列成自小至大有序的整數(shù)序列

for(i=n-1,change=TRUE;i>1&&change;--i){change=FALSE;for(j=0;j<i;++j)if(a[j]>a