DS線性表PPT學習教案

1、會計學1DS線性表線性表22線性表存儲結構2.2.1 順序存儲方法： 存儲方法：在內(nèi)存開辟一塊連續(xù)的存儲空間用來依次存放表中的每個元素。元素位置確定：設有線性表A=（a0、a1、an-1），由于A中的元素具有相同類型，且占s字節(jié)，那么元素ai的地址為 ai=&a0+i*s。對線性表的順序存儲常采用數(shù)組來實現(xiàn)。這是因為數(shù)組具有如下特性： 第1頁/共45頁第2頁/共45頁線性表的創(chuàng)建：1 用數(shù)組表示線性表：如： #define MAXSIZE 100 int listMAXSIZE; int n; 第3頁/共45頁如：#define MAXSIZE 100struct char 學號； char

2、姓名； int 數(shù)據(jù)結構； int 操作系統(tǒng)； int 離散數(shù)學； int 英語listMAXSIZE； int n;第4頁/共45頁2 線性表的創(chuàng)建程序： 設list為已定義的存放線性表的數(shù)組，n為線性表的長度。 Void creat_sq_list(int n,list) int i; for (i=0;in;i+) scanf(“%d”,&listi); 第5頁/共45頁2.2.2鏈接存儲方法存儲方法：1 結點：線性表的每個元素除了需要存儲自身的信息外，還需要存儲一至兩個指示其直接后繼元素或直接前驅(qū)元素的地址（鏈接指針），這兩部分信息就組成了一個數(shù)據(jù)通信元素的存儲結構，常稱為結點。 2

3、鏈表：線性表的各個元素之間的關系用鏈接指針把它們連接起來，從而構成鏈表。第6頁/共45頁第7頁/共45頁第8頁/共45頁3 單向鏈表和雙向鏈表： 單向鏈表：每一個結點只設一個指針域指向其直接后繼結點； 雙向鏈表：每一個結點應有兩個指針域，一個指向直接前驅(qū)、另一個指向直接后繼結點。 第9頁/共45頁二、單鏈表中元素位置的確定 鏈表中任意元素的存儲地址只能通過表頭指針順著鏈接指針遍歷鏈表結點而得到。三、線性鏈表的創(chuàng)建1 結點的表示及產(chǎn)生 在C中可以用一個包含數(shù)據(jù)域和指針域的結構體來表示線性鏈表的結點。typedef struct nodechar data; struct node *link1;

4、 struct node *link2; NODE;鏈表結點通過(NODE*)malloc(sizeof(NODE)函數(shù)獲得。第10頁/共45頁線性鏈表的創(chuàng)建程序建立n個結點的單鏈表函數(shù)，返回鏈表的頭指針。NODE *creat_link_list(int n) int i; NODE *head,*p,*q; /*p指向正鏈表最后結點,q指向新申請結點*/ if (n=0)return(NULL); /*結點數(shù)為0返回空表*/ head=(NODE*)malloc(sizeof(NODE); /*申請建立第一個結點*/ p=head; for (i=1;idata); /*輸入結點元素的值*

5、/ q= (NODE*)malloc(sizeof(NODE); /*申請建立下一個結點*/ p-link=q; p=q; scanf(“%c”,&(p-data); /*輸入最后一個結點的值*/ p-link=NULL; /*最后結點指針置空*/ getchar(); /*暫停*/ return(head); /*返回建成鏈表的頭指針*/第11頁/共45頁四、單鏈表的幾種變化形式1 循環(huán)鏈表：鏈表中最后一個結點的指針域指向第一個結點(原單鏈表末結點置NULL處改為置頭指針即可)2 帶表頭結點的鏈表3帶表頭結點的循環(huán)鏈表HeadHeadHeadHeadHead第12頁/共45頁五、雙向鏈表的幾

6、種變化形式1 雙向循環(huán)鏈表：鏈表中最后一個結點的指針域指向第一個結點2 帶表頭結點的雙向鏈表3帶表頭結點的雙向循環(huán)鏈表HeadHead第13頁/共45頁2.3.3 其他存儲方法一、索引存儲 把線性表A中的結點劃分成子線性表A0A m-1，劃分方法是將A中的具有某種性質(zhì)的元素歸并到同一個子表中，常使用索引函數(shù)來計算出每個元素的索引值i,將相同索引i值的元素歸并到同一個Ai中。 再使用順序或鏈接存儲方法來存儲索引表X和子線性表A0A m-1。一般情況下索引表用順序存儲，而子線性表用鏈接存儲方法。實例見P18第14頁/共45頁abcdapplecarbearduckbusbirdcatdog例: 線

7、性表A=(apple,cat,bus,dog,duck,bear,bird,car)使用索引函數(shù)： index(key)=(key的第1個字母ASCII碼)-(a的ASCII碼)。則把A劃分為A0=(apple), A1=(bus,bird,bear), A2=(cat,car), A3=(dog,duck)x0X1x2x3第15頁/共45頁二、分塊存儲 把線性表A劃分成若干塊，每一塊中的元素順序是任意的，但塊與塊的之間必須按關鍵字大小排列， 再建立一個索引表，索引表中的一項對應于表中一塊，索引項由大小域(塊中的元素個數(shù))、鍵域(塊中最大值)和鏈域(結點指針)。實例見P19.第16頁/共45頁

8、053015243548393850607065第一塊第二塊第三塊058534354870鏈鏈 域域大小大小 域域鍵鍵 域域分塊有序表分塊有序表第17頁/共45頁三、壓縮存儲 若線性表A=(a0、a1、an-1)中有很多具有相同值的元素V,由A構造A=(0,a0)、(1,a1 ) 、(n-1,an-1 ),將A中的所有(j,v)元素刪除，得到線性表達式A。再將A中的元素以順序或鏈接方式存儲。例：A=(12,0,0,11,0,18,0,0,17,0,16,0,0,0,15)經(jīng)壓縮處理后A=(0,12), (3,11), (5,18), (8,17), (10,16), (14,15)再對A進行順

9、序或鏈接存儲。第18頁/共45頁四、散列存儲(HASH函數(shù))基本思想：把線性表中的每個元素的值K通過一個函數(shù)H(k)轉(zhuǎn)換成該元素在一塊連續(xù)存儲空間(數(shù)組)的單元地址(下標)來存放。實現(xiàn)關鍵字到地址映射的函數(shù)h(k)稱為散列函數(shù)或哈希(Hash)函數(shù)，h(k)的值稱散列地址或哈希地址，用于線性表進行散列存儲的地址空間(數(shù)組)稱為散列表或哈希表。沖突問題：有ki=kj,但有H(ki)=H(kj),出現(xiàn)地址沖突。散列函數(shù)構造：原則：減少沖突、計算簡單； 常用方法：直接定址、除留余數(shù)法等。沖突處理：開放定址法、鏈接法。實例見P23第19頁/共45頁2.3 線性表的基本運算2.3.1 線性表的運算概述

10、1 創(chuàng)建一個空線性表； 2 求線性表的長度； 3 查找表中的第i個元素 4 根據(jù)已知關鍵字求在線性表的位置； 5 在線性表中第i個元素位置插入一個新元素； 6 修改線性表中元素的值； 7 刪除線性表中第i個元素； 8 對線性表中的元素按關鍵字排序； 9 復制一個線性表； 10 合并線性表； 11 拆分線性表； 12 打印線性表（輸出線性表）。第20頁/共45頁2.3.2 線性表的插入一、插入運算 有長度為n的線性表(a0、a1、an-1 ),現(xiàn)將元素值為x的元素插入線性表中，使之變?yōu)?a0、a1、 ai-1 、x、 ai 、 an-1 )，其長度變?yōu)閚+1。二、順序存儲的線性表的插入算法：1

11、將ai、ai+1、 an-1 依次后移一個位置，留 出位置i;2 將新元素x存入位置i;3 線性表長度加1。 軟件實現(xiàn)見C程序。第21頁/共45頁int sq_ins(list,n,i,x) int list; int *n; int i,x; int j; if(i*n) return(1); if(*n=MAXSIZE) return(2): for(j=*n;ji,j-) listj=listj-1; listi=x; (*n)+; return(0); 第22頁/共45頁1、算法、算法 創(chuàng)建新結點 newnode=(NODE)malloc(sizeof(NODE); newnode-d

12、ata=x; 確定插入位置：從頭結點順序搜索i-1次即到達i-1個結點p; 修改指針：newnode-link=p-link; p-link=newnode;HeadHead第23頁/共45頁 newnodelink = head ; head = newnode；第24頁/共45頁 第25頁/共45頁第26頁/共45頁2.3.2 線性表的刪除一、刪除運算 將長度為n的線性表刪除第I個元素，使其長度變?yōu)閚-1的線性表。二、順序存儲的線性表刪除 算法：從順序存儲的線性表中刪除ai的步驟是：領獎將ai+1, ai+2, an-1依次前移一位，線性表長度減1。 實現(xiàn)程序：見sq_del(list,n

13、,i)。int sq_del(list,n,i)int list, *n, i;int j; if(i*n) return(1); /*第1種情況，i不在可刪除位置上*/ for(j=i+1;jlink; p-link=q-link;第28頁/共45頁2 實現(xiàn)程序：通過函數(shù)link_del()實現(xiàn)上述鏈表的刪除算法。 int link_del(head,i) /*head為鏈表頭指針，I為被刪元素位置*/NODE *head;int i;int j;NODE *p,*q;if(q=NULL)return(1); /*不能刪除情況1*/if(i=0) /*刪除頭結點*/ q=*head; *he

14、ad=q-link; free(q); /*修改指針*/ return(0);j=0; p=*head;while (+ jlink;if (I0|jlink; p-link=q-link;free(q); /*修改指針,釋放空間*/return(0);第29頁/共45頁第30頁/共45頁 newnodelink = plink; if ( plink =NULL ) last = newnode; plink = newnode;第31頁/共45頁 q = plink; plink = qlink; delete q; if ( plink = NULL ) last = p;第32頁/共4

15、5頁第33頁/共45頁第34頁/共45頁第35頁/共45頁第36頁/共45頁2.4 線性表的應用舉例:一、一元多項式的線性表示 一般的n次多項式A(x)按降冪排列，記為：A(x)=anxn+ an-1xn-1+.+ a1x1 +a0，當an0j時稱A(x)為n階多項式。 在數(shù)據(jù)結構中,一個n階多項式可用一個線性表A表示：A=（ an， an-1 ， an-2，.， a1， a0 ） 由于多項式中系數(shù)不為零的很少，例如： A(x)=8x3000+ 3為了節(jié)約存儲空間，應用中只需將多項式中不為零的系數(shù)與對應的冪次數(shù)用兩個數(shù)據(jù)項進行描述，并表示成線性表，則有： A=（( am， em)， ( am-

16、1， em-1)，.，( a1， e1)，( a0， e0)）二、多項式的加法： 一元多項加法運算原則：兩個多項式中所有指數(shù)相同的項對應系數(shù)相加，若和不為零，則構成“和多項式”中的一項，而所有指數(shù)不相同的那些項，均應復制到“和多項式中”。第37頁/共45頁多項式加法的算法描述多項式加法的算法描述：設設A A、B B分別表示兩個線性表，分別表示兩個線性表，A A和和B B相加的結果構成線性表相加的結果構成線性表C,C,其操作步驟如下：其操作步驟如下：線性表線性表C C置空；置空；各取線性表各取線性表A A和和B B的第一個元素分別作為各自線性表當前處理的元素的第一個元素分別作為各自線性表當前處理

17、的元素比較當前處理的兩個元素的指數(shù)值，若指數(shù)相等且它們相加后的系數(shù)和不為零，則把系數(shù)和與指數(shù)值構成一個數(shù)據(jù)元素加到線性表比較當前處理的兩個元素的指數(shù)值，若指數(shù)相等且它們相加后的系數(shù)和不為零，則把系數(shù)和與指數(shù)值構成一個數(shù)據(jù)元素加到線性表C C中，各取中，各取A A和和B B的下一個元素進行處理，若指數(shù)不等，則把指數(shù)大的數(shù)據(jù)元素追加到的下一個元素進行處理，若指數(shù)不等，則把指數(shù)大的數(shù)據(jù)元素追加到C C中，再取該元素所在表的下一元素，另一表的當前處理元素不變；中，再取該元素所在表的下一元素，另一表的當前處理元素不變；重復步驟重復步驟2.4.2 2.4.2 多項式加法的順序存儲實現(xiàn)方法多項式加法的順序存

18、儲實現(xiàn)方法一、數(shù)據(jù)元素的定義：一、數(shù)據(jù)元素的定義：# define MAXN 100typedef struct term float coef; int exp; TERM;TERM polyMAXN;A(x) =4x80 + 7x60 +9x5+5B(x) =2x80 - 7x60 +3x12 第38頁/共45頁A(x) =4x80 + 7x60 +9x5+5B(x) =2x80 - 7x60 +3x12 兩多項式系數(shù)與指數(shù)在結構數(shù)組兩多項式系數(shù)與指數(shù)在結構數(shù)組poly中的存儲表示為中的存儲表示為47952-73.806050806012. 0 1 2 3 4 5 6 7 8 MAXN-1coefex