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

1、第2章數(shù)據(jù)結構及應用概念及順序表,西安交通大學計教中心ctec.xjtu.edu.cn,[第2/42頁],思考問題,數(shù)據(jù)結構要研究什么問題？什么是線性數(shù)據(jù)結構和線性表？如何描述線性表？線性表在計算機中如何存放？有幾種存儲形式？它們的特點是什么？如何處理線性數(shù)據(jù)結構中的數(shù)據(jù)？……,[第3/42頁],數(shù)據(jù)結構問題的由來,計算機求解問題的過程步驟：,,,求解結果,用戶需求,[第4/42頁],數(shù)據(jù)結構,數(shù)據(jù)結構是計算機的專業(yè)

2、技術基礎課。它研究的主要問題有： ?分析數(shù)據(jù)（計算機加工的對象）的特征 ?選擇適當邏輯存儲結構和物理存儲結構 ?在存儲結構的基礎上實現(xiàn)對數(shù)據(jù)的操作,[第5/42頁],2.1 數(shù)據(jù)結構基本概念,1．數(shù)據(jù)（data）數(shù)據(jù)是指能夠輸入到計算機中，并被計算機識別和處理的符號的集合。 2．數(shù)據(jù)元素（data element）數(shù)據(jù)元素是組成數(shù)據(jù)的基本單位。數(shù)據(jù)元素是一個數(shù)據(jù)整體中相對獨立的單位。但它還可以分割成若干個具有不同屬

3、性的項（字段），故不是組成數(shù)據(jù)的最小單位,[第6/42頁],數(shù)據(jù)結構（data structure）是指相互之間存在一種或多種特定關系的數(shù)據(jù)元素所組成的集合。數(shù)據(jù)結構包含三個方面的內容，即數(shù)據(jù)的邏輯結構，數(shù)據(jù)的存貯結構和對數(shù)據(jù)所施加的運算。,[第7/42頁],數(shù)據(jù)的邏輯結構,它是描述數(shù)據(jù)間的順序（邏輯）關系，只是抽象地反映數(shù)據(jù)元素的結構，而不管它們在計算機中如何存放。一般用下列二元組來描述： DS=（D，

4、R） 其中： D：是數(shù)據(jù)元素的有限集合； R：是數(shù)據(jù)元素之間關系的集合。,與數(shù)據(jù)在計算機中的存放的物理位置無關,[第8/42頁],舉例,課題組由1名教師、1~3名研究生、1~6名本科生組成；成員關系是：教師指導研究生、研究生指導1~2名本科生。 定義DS如下： Group=（D，R） 其中：,D={T，G1，…,Gn,S11,…Snm} 1 ? n ? 3 , 1 ? m ? 2

5、,R={R1,R2}R1={|1 ? i ? n , 1 ? n ? 3}R2={|1?i?n ,1? j ? m , 1 ? n ? 3 , 1 ? m ? 2 },[第9/42頁],數(shù)據(jù)的存儲結構,又稱物理結構是指數(shù)據(jù)結構在計算機中的表示(又稱映象),即數(shù)據(jù)在計算機中的存放。,數(shù)據(jù)庫中的數(shù)據(jù)存放在計算機中的物理位置,[第10/42頁],邏輯結構和存儲結構的關系,數(shù)據(jù)的邏輯結構是從邏輯關系（某種順序）上觀察數(shù)據(jù)，它是獨立于計算機

6、的；可以在理論上、形式上進行研究、推理、運算等各種操作。數(shù)據(jù)的存儲結構是邏輯結構在計算機中的實現(xiàn)，是依賴于計算機的；離開了機器，則無法進行任何操作。任何一個算法的設計取決于選定的邏輯結構；而算法的最終實現(xiàn)依賴于采用的存儲結構。,[第11/42頁],數(shù)據(jù)存儲結構分類,順序存儲結構鏈式存儲結構索引存儲結構散列存儲結構,[第12/42頁],順序存儲結構,把數(shù)據(jù)元素按某種順序存放在一塊連續(xù)的存儲單元中的存儲形式。數(shù)據(jù)結點結構:,

7、d1 d2 …… dn,,,,,,數(shù)據(jù)域,特點: 連續(xù)存放;邏輯上相鄰,物理上也相鄰。 結構簡單，易實現(xiàn)。 插入、刪除操作不便（需大量移動元素）。,[第13/42頁],鏈式存儲結構,以鏈表形式將數(shù)據(jù)元素存放于任意存儲單元中，可連續(xù)存放，也可以不連續(xù)存放，以指針實現(xiàn)鏈表間的聯(lián)系。數(shù)據(jù)結點結構:,d1,,,,,,,,...,d2,,,dn ^,,,數(shù)據(jù)域

8、 指針域,特點:非連續(xù)存放,借助指針來表示元素間的關系;插入、刪除操作簡單，只要修改指針即可；結構較復雜，需要額外存儲空間。,[第14/42頁],索引存儲結構,數(shù)據(jù)按索引形式存放。存儲時分為：數(shù)據(jù)項和索引號；通過索引表記錄邏輯號（記錄號）和物理號（存儲序號）之間的對應關系。 數(shù)據(jù)結點結構:,,,,,,,,,12 21 35 2 45 5 10,4 3

9、 2 7 1 6 5,特點：非連續(xù)存放；檢索速度快；增、刪操作簡單。,序 號： 1 2 3 4 5 6 7,數(shù)據(jù)項：索引號：,[第15/42頁],散列存儲結構,在數(shù)據(jù)元素與存儲位置之間建立一種存儲關系F，根據(jù)這種關系F，已知元素E，就可以得到它的存儲地址，即D=F（E）。哈希查找中的哈希表就是這樣一種存儲結構。 特點：數(shù)據(jù)元素間無

10、內在聯(lián)系；存儲形式不定。,[第16/42頁],數(shù)據(jù)運算,數(shù)據(jù)運算是指對存放在物理結構上的數(shù)據(jù),按定義的邏輯結構進行的各種操作。 常見操作有：輸入、檢索、插入、刪除、修改、排序等。,[第17/42頁],數(shù)據(jù)結構分類,,[第18/42頁],數(shù)據(jù)結構基本類型,線性結構 —— 通迅錄、成績單、花名冊樹形結構 —— 電子字典、家譜、目錄圖狀結構 —— 交通線路、通信網絡,[第19/42頁],算法（algorithm）,通俗地講，算法就

11、是一種解題的方法。更嚴格地說，算法是由若干條指令組成的有窮序列，它必須滿足下述條件（也稱為算法的五大特性）：⑴輸入：具有0個或多個輸入的外界量（算法開始前的初始量）⑵輸出：至少有一個輸出，是算法執(zhí)行完后的結果。⑶有窮性：每條指令的執(zhí)行次數(shù)必須是有限的。⑷確定性：每條指令的含義都必須明確，無二義性。⑸可行性：每條指令的執(zhí)行時間都是有限的。,[第20/42頁],1．時間復雜度 一個算法花費的時間與算法中語句的執(zhí)行次數(shù)成正比

12、，哪個算法中語句執(zhí)行次數(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;,算法分析,[第21/42頁],算法的評價

13、,算法評價的標準：時間復雜度 指在計算機上運行該算法所花費的時間。用“O（數(shù)量級）”來表示，稱為“階”。常見的時間復雜度有： O（1） O（logn） O（ n ） O（ n2 ） 常數(shù)階 對數(shù)階 線性階 平方階空間復雜度 指算法在計算機上運行所占用的存儲空間。度量同時間復雜度。,,[第22/42頁],時間復雜度舉例,（a） X：=X+1 ；,（b） FOR I：=1 TO

14、n DO X：= X+1；,（c） FOR I：= 1 TO n DO FOR J：= 1 TO n DO X：= X+1；,O（ 1 ）,O（ n ）,O（ n2 ）,[第23/42頁],2、空間復雜度與時間復雜度類似，空間復雜度是指算法在計算機內執(zhí)行時所占用的內存開銷規(guī)模。但我們一般所討論的是除正常占用內存開銷外的輔助存儲單元規(guī)模。討論

15、方法與時間復雜度類似，不再贅述。,[第24/42頁],2.2 線性數(shù)據(jù)結構,線性表是由有限個同類型的數(shù)據(jù)元素組成的有序序列，一般記作（a1,a2,…,an）。除了a1和an之外，任意元素ai都有一個直接前趨ai-1和一個直接后繼ai+1。 a1無前趨，an無后繼。 例如，一星期七天的英文縮寫表示： （Sun，Mon，The，wed，Thu，F(xiàn)ri，Sat） 是一個線性表，其中的元素是字符串，表的長度為7。,[第25/42頁

16、],線性表的邏輯結構,定義： 線性表是n（n?0）個元素a1,a2,…,an 的有限序列；表中每個數(shù)據(jù)元素，除了第1個和最后1個外，有且僅有一個前趨元素和后繼元素。形式定義： 含有n個數(shù)據(jù)元素的線性表是一種數(shù)據(jù)結構，表示為： Linear_list=( D , R ) 其中: D={ai | ai?D0,i=1,2,3,…,n,n ?0} R={N}, N={|ai-1,ai ?D0 ,i=1,…,n}

17、D是數(shù)據(jù)元素的有限集合，R是D上邏輯關系的有限集合。關系N是一個有序偶對的集合。,[第26/42頁],順序表,采用順序存儲結構的線性表稱為順序表，它的數(shù)據(jù)元素按照邏輯順序依次存放在一組連續(xù)的存儲單元中。邏輯上相鄰的數(shù)據(jù)元素，其存儲位置也彼此相鄰。假定元素a1的物理地址是Loc(a1)，每個元素占d個存儲單元，則第i個元素的存儲位置為：Loc(ai) = Loc(a1) + (i-1) * d,[第27/42頁],線性表元素存儲示

18、意圖,,,,,,,,a1,a2,….,ai,….,元素序號 內存狀態(tài) 存儲地址,1,2,….,i,….,LOC(a1),LOC(a1)+1,….,LOC(a1)+(i-1),….,[第28/42頁],順序表類型描述,struct SeqList { ElemType *data; // 順序表存儲數(shù)組的地址 int maxsize; // 順序表最大允許長度 int length;

19、// 順序表當前長度 }； SeqList list;// 定義一個線性表list （1）ElemType代表數(shù)組的類型。（2）數(shù)組data需要在初始化函數(shù)中利用new操作動態(tài)申請，maxsize為其長度。數(shù)組的下標從0開始。（3）length表示線性表當前長度，初始長度為0（空表），最大不超過maxsize。,[第29/42頁],線性表的基本操作,Setnull（L） 置空表Length（L）

20、 求表長度；求表中元素個數(shù)Get（L，i） 取表中第i個元素（1?i ?n）Prior（L，i） 取i的前趨元素Next（L，i） 取i的后繼元素Locate（L，x） 返回指定元素在表中的位置Insert（L，i，x） 插入元素Delete（L，x） 刪除元素Empty（L） 判別表是否為空,[第30/42頁],順序表的主要算法,（1）順序表的初始化 順序表的

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

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

23、第32/42頁],[第33/42頁],插入算法示意舉例,設有數(shù)列{4,5,8,10,21,30,43,59}，長度為8，在“21”和“30”之間插入元素“25”。算法描述：從數(shù)列右邊開始，即從第8個元素開始；為在第5個元素“21”后插入“25”，則要把其后的3個元素右移，移動元素個數(shù)是3（8-5）； for( int j=L->length-1; j>=i-1; j-- ) // length 是元素個數(shù)(8)

24、 L->data[j+1]=L->data[j]; // j是插入位置(5) 將空出的第6個位置，存放“25”。 L->data[i-1] = x; // 將x存放在第i-1 位置表長度加“1” L->length++; // 加“1

25、”后，結果為“9”最后，得到的結果數(shù)列是{4,5,8,10,21,25,30,43,59},[第34/42頁],void Insert( SeqList *L, int i, ElemType x ){ if( iL->length+1 || L->length==L->maxsize ) coutlength-1; j>=i-1; j-- )

26、 L->data[j+1] = L->data[j]; //元素依次右移 L->data[i-1] = x; // 向第 i 個位置存入新元素 xL->length++; // 表長度加一 }},順序表插入算法,[第35/42頁],（3）在表中刪除第i個元素 算法實現(xiàn)的主要步驟是：① 判斷刪除位置的合理性。

27、② 從第i+1個元素開始，依次向后直到最后一個元素為止，將每個元素向前移動一個位置。這時第i個元素已經被覆蓋刪除。③ 最后還要將線性表長度減一。,[第36/42頁],[第37/42頁],刪除算法示意舉例,設有數(shù)列{4,5,8,10,21,25,30,43,59}，長度為9，將第6位的元素“25”刪除。算法描述：從第7個元素開始(i+1)；將第7個元素“30”存入第6位，將“25”覆蓋，即元素左移，移動元素個數(shù)是3（9-6）；

28、 for ( int j=i; jlength-1; j++ ) // length是元素個數(shù)(9) L->data[j-1] = L->data[j]; // i是刪除位置(6)長度減“1” L->length--；

29、 // 操作后，length 等于8最后，得到的結果數(shù)列是{4,5,8,10,21,30,43,59},[第38/42頁],void Delete( SeqList *L, int i ){ if(iL->length ) coutlength-1; j++ ) L->data[j-1] = L->data[j];

30、 //數(shù)據(jù)元素左移 L->length--; } },順序表刪除算法,[第39/42頁],（4）在表中查找某個元素 下面是根據(jù)數(shù)據(jù)元素本身的值進行查詢的算法，x為需要查找的元素，算法返回元素的實際位置。查找算法:int Find( SeqList *L, ElemType x ) { for( int i = 0; ile

31、ngth; i++ ) { //查找成功, 返回元素位置 if( L->data[i]==x ) return i+1; } return 0; //查找失敗, 返回 0 },[第40/42頁],順序表應用舉例,【例2-1】利用順序表表示多項式，實現(xiàn)兩個一元多項式L1(x)和

32、L2(x)相加，將結果存于多項式L3(x)中。若: L1(x) = 3.5 + 4x2 + 2.5x4 L2(x) = 1.5x + 2.6x2 + 1.6x3 則，L3(x)的結果是: L3(x)= 3.5 + 1.5x + 6.6x2 + 1.6x3 + 2.5x4 一元多項式P(x)可表示為((a0, 0), (a1, 1), … , (an, n))。 例如線性表((6, 1),

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

34、k中，i++和k++；如果L2中第j項指數(shù)小，則同樣是將此項復制到L3中，j++和k++；如果兩項指數(shù)項相等，則合并同類項后再將結果復制到L3中，并同時i++、j++和k++。③當L1或L2中的數(shù)據(jù)元素處理完畢，則將另一個順序表的剩余部分復制到L3中。,算法描述,[第42/42頁],參照程序[例2-1],P2-1.cpp,線性表操作的綜合例子,[第43/42頁],順序存儲結構的特點,數(shù)據(jù)連續(xù)存放、隨機存取邏輯上相鄰，物理上也相鄰存

35、儲結構簡單、易實現(xiàn)插入、刪除操作不便存儲密度大，空間利用率高結論： 順序存儲結構適合于表中元素變動較少的情況。,[第44/42頁],結束語,歡迎參加到中心網站《軟件開發(fā)技術基礎》課程的學習討論中來。中心網址： http://ctec.xjtu.edu.cn課件下載地址: http://202.117.35.160/moodle15我的E-mail地址: LZQ@ctec.xjtu.e