數(shù)據(jù)結(jié)構(gòu)概念及順序表

數(shù)據(jù)結(jié)構(gòu)概念及順序表第一頁，共二十二頁，2022年，8月28日2.1數(shù)據(jù)結(jié)構(gòu)基本概念1．?dāng)?shù)據(jù)（data）

數(shù)據(jù)是指能夠輸入到計算機中，并被計算機識別和處理的符號的集合。

2．?dāng)?shù)據(jù)元素（dataelement）

數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位。數(shù)據(jù)元素是一個數(shù)據(jù)整體中相對獨立的單位。但它還可以分割成若干個具有不同屬性的項（字段），故不是組成數(shù)據(jù)的最小單位第二頁，共二十二頁，2022年，8月28日數(shù)據(jù)結(jié)構(gòu)（datastructure）

是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素所組成的集合。數(shù)據(jù)結(jié)構(gòu)包含三個方面的內(nèi)容，即數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存貯結(jié)構(gòu)和對數(shù)據(jù)所施加的運算。

這三個方面的關(guān)系為：

數(shù)據(jù)的邏輯結(jié)構(gòu)獨立于計算機，是數(shù)據(jù)本身所固有的存貯結(jié)構(gòu)是邏輯結(jié)構(gòu)在計算機存貯器中的映像，必須依賴于計算機。運算是指所施加的一組操作總稱。運算的定義直接依賴于邏輯結(jié)構(gòu)，但運算的實現(xiàn)必依賴于存貯結(jié)構(gòu)。第三頁，共二十二頁，2022年，8月28日數(shù)據(jù)結(jié)構(gòu)基本類型

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

通迅錄、成績單、花名冊樹形結(jié)構(gòu)——

電子字典、家譜、目錄圖狀結(jié)構(gòu)——

交通線路、通信網(wǎng)絡(luò)第四頁，共二十二頁，2022年，8月28日數(shù)據(jù)結(jié)構(gòu)中常用的存貯結(jié)構(gòu)(1)順序存貯

所有元素存放在一片連續(xù)的存貯單元中，邏輯上相鄰的元素存放到計算機內(nèi)存仍然相鄰。(2)鏈?zhǔn)酱尜A

所有元素存放在可以不連續(xù)的存貯單元中，元素之間的關(guān)系通過地址確定，邏輯上相鄰的元素存放到計算機內(nèi)存后不一定是相鄰的。(3)索引存貯（略） (4)散列存貯（略）第五頁，共二十二頁，2022年，8月28日算法（algorithm）

通俗地講，算法就是一種解題的方法。更嚴(yán)格地說，算法是由若干條指令組成的有窮序列，它必須滿足下述條件（也稱為算法的五大特性）：（1）輸入：具有0個或多個輸入的外界量（算法開始前的初始量）（2）輸出：至少產(chǎn)生一個輸出，它們是算法執(zhí)行完后的結(jié)果。（3）有窮性：每條指令的執(zhí)行次數(shù)必須是有限的。（4）確定性：每條指令的含義都必須明確，無二義性。（5）可行性：每條指令的執(zhí)行時間都是有限的。第六頁，共二十二頁，2022年，8月28日1．時間復(fù)雜度

一個算法花費的時間與算法中語句的執(zhí)行次數(shù)成正比，哪個算法中語句執(zhí)行次數(shù)多，它花費時間就多。

數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素個數(shù)n稱為問題的規(guī)模，當(dāng)n不斷變化時，語句的執(zhí)行次數(shù)也會變化。一個算法中的時間復(fù)雜度一般用語句執(zhí)行次數(shù)的數(shù)量級來衡量。 例如：for(i=1;i<=n;i++)

for(j=1;j<=i;j++)

d[i][j]=data[i][j]+1;算法分析O(n2)第七頁，共二十二頁，2022年，8月28日2．空間復(fù)雜度

與時間復(fù)雜度類似，空間復(fù)雜度是指算法在計算機內(nèi)執(zhí)行時所占用的內(nèi)存開銷規(guī)模。但我們一般所討論的是除正常占用內(nèi)存開銷外的輔助存儲單元規(guī)模。討論方法與時間復(fù)雜度類似，不再贅述。第八頁，共二十二頁，2022年，8月28日2.2

線性數(shù)據(jù)結(jié)構(gòu)

線性表是由有限個同類型的數(shù)據(jù)元素組成的有序序列，一般記作（a1,a2,…,an）。除了a1和an之外，任意元素ai都有一個直接前趨ai-1和一個直接后繼ai+1。a1無前趨，an無后繼。

線性表的存儲結(jié)構(gòu)主要有順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)兩種。

第九頁，共二十二頁，2022年，8月28日順序表

采用順序存儲結(jié)構(gòu)的線性表稱為順序表，它的數(shù)據(jù)元素按照邏輯順序依次存放在一組連續(xù)的存儲單元中。邏輯上相鄰的數(shù)據(jù)元素，其存儲位置也彼此相鄰。

假定元素a1的物理地址是Loc(a1)，每個元素占d個存儲單元，則第i個元素的存儲位置為：Loc(ai)=Loc(a1)+(i-1)*d

length=nmaxsize01i-2i-1in-1a2…ai-1aiai+1a1…an第十頁，共二十二頁，2022年，8月28日順序表類描述constintMAXSIZE=100; //順序表最大允許長度classSeqList{public: ElemTypedata[MAXSIZE]; //存儲數(shù)據(jù)的數(shù)組

intlength; //順序表當(dāng)前長度

SeqList(){length=0;}//構(gòu)造函數(shù)

voidClearList(){length=0;}//將順序表置為空表

//判斷順序表是否為空表

boolIsListEmpty(){returnlength==0;} (下頁continue….)第十一頁，共二十二頁，2022年，8月28日

(接上頁)//判斷順序表是否為滿

boolIsListFull(){returnlength==MAXSIZE;} //在表中刪除第i個元素

voidListDelete(inti);//在表中第i個位置插入新元素xvoidListInsert(inti,ElemTypex);intFind(ElemTypex); //在表中查找元素};（1）ElemType代表數(shù)組的某種類型。（2）length表示線性表當(dāng)前長度，初始長度為0（空表），最大不超過maxsize。第十二頁，共二十二頁，2022年，8月28日順序表的主要算法

（1）在表中第i個位置插入新元素x

算法實現(xiàn)的主要步驟是： ①判斷插入位置的合理性以及表是否已滿。

②從最后一個元素開始依次向前，將每個元素向后移動一個位置，直到第i個元素為止。

③向空出的第i個位置存入新元素x。 ④最后還要將線性表長度加一。第十三頁，共二十二頁，2022年，8月28日第十四頁，共二十二頁，2022年，8月28日voidSeqList::ListInsert(inti,ElemTypex){if(i<1||i>length+1||length==MAXSIZE) cout<<"插入位置錯誤或表滿"; else{ for(intj=length-1;j>=i-1;j--){ data[j+1]=data[j]; //元素依次向后移動

} data[i-1]=x; //向第i個位置存入新元素

length++; //表長度加1}}第十五頁，共二十二頁，2022年，8月28日（2）在表中刪除第i個元素

算法實現(xiàn)的主要步驟是： ①判斷刪除位置的合理性。

②從第i+1個元素開始，依次向后直到最后一個元素為止，將每個元素向前移動一個位置。這時第i個元素已經(jīng)被覆蓋刪除。 ③最后還要將線性表長度減一。第十六頁，共二十二頁，2022年，8月28日第十七頁，共二十二頁，2022年，8月28日voidSeqList::Delete(inti){if(i<1||i>L->length) cout<<"表中沒有第"<<i<<"個元素";else{ for(intj=i;j<=length-1;j++) data[j-1]=data[j];//元素依次向前移動

length--; } }第十八頁，共二十二頁，2022年，8月28日（3）在表中查找某個元素

下面是根據(jù)數(shù)據(jù)元素本身的值進行查詢的算法，x為需要查找的元素，算法返回元素的實際位置。

intSeqList::Find(ElemTypex) { for(inti=0;i<length;i++) {//查找成功，返回元素位置

if(data[i]==x)returni+1; } return0; //查找失敗，返回0 }第十九頁，共二十二頁，2022年，8月28日順序表應(yīng)用舉例

【例2-1】利用順序表表示多項式，實現(xiàn)兩個一元多項式L1(x)和L2(x)相加，將結(jié)果存于多項式L3(x)中。并計算當(dāng)L1(x)=3.5+4x2+2.5x4，L2(x)=1.5x+2.6x2+1.6x3時，L3(x)的結(jié)果是什么。

一元多項式P(x)可以表示為((a0,0),(a1,1),…,(an,n))。例如線性表((6,1),(-5,4),(8,10))表示多項式:

P(x)=6x-5x4+8x10。第二十頁，共二十二頁，2022年，8月28日

用順序表L1和L2存放需要相加的兩個多項式L1(x)和L2(x)，用順序表L3來存放結(jié)果。多項式相加算法可按照下列步驟實現(xiàn)：①設(shè)定兩個位置變量i和j指向順序表L1和L2的第一個元素，設(shè)定位置變量k表示L3的插入位置，插入位置從1開始。本例中i、j和k初值均為1。②比較i和j兩個位置數(shù)據(jù)元素的指數(shù)項，如果L1中第i項指數(shù)較小，則將此項數(shù)據(jù)元素復(fù)制到L3的位置k