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

1、數(shù)據(jù)結(jié)構(gòu)概念及順序表,西安交通大學(xué)計(jì)教中心ctec.xjtu.edu.cn,2.1 數(shù)據(jù)結(jié)構(gòu)基本概念,1．?dāng)?shù)據(jù)（data）數(shù)據(jù)是指能夠輸入到計(jì)算機(jī)中，并被計(jì)算機(jī)識(shí)別和處理的符號(hào)的集合。 2．?dāng)?shù)據(jù)元素（data element）數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位。數(shù)據(jù)元素是一個(gè)數(shù)據(jù)整體中相對(duì)獨(dú)立的單位。但它還可以分割成若干個(gè)具有不同屬性的項(xiàng)（字段），故不是組成數(shù)據(jù)的最小單位,數(shù)據(jù)結(jié)構(gòu)（data structure）是指相

2、互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素所組成的集合。數(shù)據(jù)結(jié)構(gòu)包含三個(gè)方面的內(nèi)容，即數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存貯結(jié)構(gòu)和對(duì)數(shù)據(jù)所施加的運(yùn)算。這三個(gè)方面的關(guān)系為： 數(shù)據(jù)的邏輯結(jié)構(gòu)獨(dú)立于計(jì)算機(jī)，是數(shù)據(jù)本身所固有的存貯結(jié)構(gòu)是邏輯結(jié)構(gòu)在計(jì)算機(jī)存貯器中的映像，必須依賴于計(jì)算機(jī)。運(yùn)算是指所施加的一組操作總稱。運(yùn)算的定義直接依賴于邏輯結(jié)構(gòu)，但運(yùn)算的實(shí)現(xiàn)必依賴于存貯結(jié)構(gòu)。,數(shù)據(jù)結(jié)構(gòu)基本類型,線性結(jié)構(gòu) —— 通迅錄、成績(jī)單、花名冊(cè)樹形結(jié)構(gòu) —— 電

3、子字典、家譜、目錄圖狀結(jié)構(gòu) —— 交通線路、通信網(wǎng)絡(luò),數(shù)據(jù)結(jié)構(gòu)中常用的存貯結(jié)構(gòu),(1) 順序存貯所有元素存放在一片連續(xù)的存貯單元中，邏輯上相鄰的元素存放到計(jì)算機(jī)內(nèi)存仍然相鄰。(2) 鏈?zhǔn)酱尜A所有元素存放在可以不連續(xù)的存貯單元中，元素之間的關(guān)系通過地址確定，邏輯上相鄰的元素存放到計(jì)算機(jī)內(nèi)存后不一定是相鄰的。(3) 索引存貯（略） (4) 散列存貯（略）,算法（algorithm）,通俗地講，算法就是一種解題的方法。更嚴(yán)

4、格地說，算法是由若干條指令組成的有窮序列，它必須滿足下述條件（也稱為算法的五大特性）：（1）輸入：具有0個(gè)或多個(gè)輸入的外界量（算法開始前的初始量）（2）輸出：至少產(chǎn)生一個(gè)輸出，它們是算法執(zhí)行完后的結(jié)果。（3）有窮性：每條指令的執(zhí)行次數(shù)必須是有限的。（4）確定性：每條指令的含義都必須明確，無二義性。（5）可行性：每條指令的執(zhí)行時(shí)間都是有限的。,1． 時(shí)間復(fù)雜度一個(gè)算法花費(fèi)的時(shí)間與算法中語句的執(zhí)行次數(shù)成正比，哪個(gè)算法中語句執(zhí)

5、行次數(shù)多，它花費(fèi)時(shí)間就多。 數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)元素個(gè)數(shù)n稱為問題的規(guī)模，當(dāng)n不斷變化時(shí)，語句的執(zhí)行次數(shù)也會(huì)變化。一個(gè)算法中的時(shí)間復(fù)雜度一般用語句執(zhí)行次數(shù)的數(shù)量級(jí)來衡量。例如： for(i=1; i<=n; i++) for(j =1; j<=i; j++) d[i][j]=data[i][j]+1;,算法分析,2． 空間復(fù)雜度與時(shí)間復(fù)雜度類似，空

6、間復(fù)雜度是指算法在計(jì)算機(jī)內(nèi)執(zhí)行時(shí)所占用的內(nèi)存開銷規(guī)模。但我們一般所討論的是除正常占用內(nèi)存開銷外的輔助存儲(chǔ)單元規(guī)模。討論方法與時(shí)間復(fù)雜度類似，不再贅述。,2.2 線性數(shù)據(jù)結(jié)構(gòu),線性表是由有限個(gè)同類型的數(shù)據(jù)元素組成的有序序列，一般記作（a1,a2,…,an）。除了a1和an之外，任意元素ai都有一個(gè)直接前趨ai-1和一個(gè)直接后繼ai+1。 a1無前趨，an無后繼。線性表的存儲(chǔ)結(jié)構(gòu)主要有順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)兩種。,順序表,采用順

7、序存儲(chǔ)結(jié)構(gòu)的線性表稱為順序表，它的數(shù)據(jù)元素按照邏輯順序依次存放在一組連續(xù)的存儲(chǔ)單元中。邏輯上相鄰的數(shù)據(jù)元素，其存儲(chǔ)位置也彼此相鄰。假定元素a1的物理地址是Loc(a1)，每個(gè)元素占d個(gè)存儲(chǔ)單元，則第i個(gè)元素的存儲(chǔ)位置為：Loc(ai) = Loc(a1) + (i-1) * d,順序表類型描述,struct SeqList { ElemType *data; // 順序表存儲(chǔ)數(shù)組的地址 int maxsize;

8、 // 順序表最大允許長(zhǎng)度 int length; // 順序表當(dāng)前長(zhǎng)度 }； SeqList list;// 定義一個(gè)線性表list （1）ElemType代表數(shù)組的類型。（2）數(shù)組data需要在初始化函數(shù)中利用new操作動(dòng)態(tài)申請(qǐng)，maxsize為其長(zhǎng)度。數(shù)組的下標(biāo)從0開始。（3）length表示線性表當(dāng)前長(zhǎng)度，初始長(zhǎng)度為0（空表），最大不超過maxsize。,順序表的主要算法,（1）順序表的初始

9、化 順序表的初始化主要是為ElemType類型的數(shù)組申請(qǐng)空間，下面的初始化函數(shù)為順序表申請(qǐng)了長(zhǎng)度為size的空間。void Init( SeqList *L, int size ) {if( size > 0 ) { L->maxsize = size; L->length = 0; L->

10、data = new ElemType[size]; //申請(qǐng)空間}else cout<<"線性表初始化長(zhǎng)度錯(cuò)誤"; },（2）在表中第 i 個(gè)位置插入新元素x 算法實(shí)現(xiàn)的主要步驟是：① 判斷插入位置的合理性以及表是否已滿。② 從最后一個(gè)元素開始依次向前，將每個(gè)元素向后移動(dòng)一個(gè)位置，直到第i個(gè)元素為止。 ③ 向空出的第i個(gè)位置存入新元素x。④ 最后還要將線性表長(zhǎng)度加一

11、。,void Insert( SeqList *L, int i, ElemType x ){ if( iL->length+1 || L->length==L->maxsize ) coutlength-1; j>=i-1; j-- ) L->data[j+1] = L->data[j]; //元素

12、依次后移 L->data[i-1] = x;// 向第 i 個(gè)位置存入新元素 xL->length++; // 表長(zhǎng)度加一 }},（3）在表中刪除第i個(gè)元素 算法實(shí)現(xiàn)的主要步驟是：① 判斷刪除位置的合理性。 ② 從第i+1個(gè)元素開始，依次向后直到最后一個(gè)元素為止，將每個(gè)元素向前移動(dòng)一個(gè)位置。這時(shí)第i個(gè)元素已經(jīng)被覆蓋刪除。③ 最后還要將線性表長(zhǎng)度減一。,void

13、 Delete( SeqList *L, int i ){ if(iL->length ) coutlength-1; j++ ) L->data[j-1] = L->data[j]; L->length--; } },（4）在表中查找某個(gè)元素 下面是根據(jù)數(shù)據(jù)元素本身的值進(jìn)行查詢的算法，x為

14、需要查找的元素，算法返回元素的實(shí)際位置。int Find( SeqList *L, ElemType x ) { for( int i = 0; ilength; i++ ) { //查找成功，返回元素位置 if( L->data[i]==x ) return i+1; } return 0;//查找失

15、敗，返回 0 },順序表應(yīng)用舉例,【例2-1】利用順序表表示多項(xiàng)式，實(shí)現(xiàn)兩個(gè)一元多項(xiàng)式L1(x)和L2(x)相加，將結(jié)果存于多項(xiàng)式L3(x)中。并計(jì)算當(dāng)L1(x)=3.5+4x2+2.5x4，L2(x)=1.5x+2.6x2+1.6x3時(shí)，L3(x)的結(jié)果是什么。 一元多項(xiàng)式P(x)可以表示為((a0, 0), (a1, 1), … , (a n, n))。例如線性表((6, 1), (-5, 4), (8, 10))表示多項(xiàng)

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