數(shù)據(jù)結構概念及順序表

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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