900第2章 線性表

1、第第2章章 線性表線性表2.1 線性表的概念和基本操作線性表的概念和基本操作2.2 線性表的順序存儲結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)2.3 線性表的鏈式存儲結(jié)構(gòu)線性表的鏈式存儲結(jié)構(gòu)2.4 線性表兩種存儲方式的比較線性表兩種存儲方式的比較 2.5 應(yīng)用舉例分析應(yīng)用舉例分析本章要點本章要點l線性表的兩種存儲方式l順序表和單鏈表的插入、查找、刪除操作及效率分析l雙向鏈表、循環(huán)鏈表l線性表兩種存儲方式的比較本章難點本章難點l單鏈表的存儲方式及各種操作l線性表的兩種存儲方式的比較學(xué)習(xí)目標學(xué)習(xí)目標l掌握線性表的定義和各種操作l掌握線性表的兩種種存儲方式l掌握順序表、單鏈表、循環(huán)鏈表、雙向鏈表2.1 線性表的概念和

2、基本操作線性表的概念和基本操作 l線性表是具有相同數(shù)據(jù)類型的n(n=0)個數(shù)據(jù)元素的有限序列，通常記為：(a1，a2， ai-1，ai，ai+1，an)，其中n為表長，n0時稱為空表。表中相鄰元素之間存在著順序關(guān)系。將ai-1稱為ai的直接前驅(qū)，ai+1稱為ai的直接后繼。l線性表上的基本操作有：（1）init_list(l) 線性表初始化，當(dāng)表l不存在時，構(gòu)造一個空的線性表。 （2）length_list(l) 求線性表的長度，當(dāng)表l存在時，返回線性表中的所含元素的個數(shù)。（3）get_list(l,i) 取表元，當(dāng)表l存在且1ilength_list(l)時，返回線性表l中的第個元素的值或地

3、址。（4）locate_list(l,x) 按值查找，是給定的一個數(shù)據(jù)元素。當(dāng)線性表l存在時，在表l中查找值為的數(shù)據(jù)元素，其結(jié)果返回在l中首次出現(xiàn)的值為的那個元素的序號或地址，稱為查找成功；否則，即在l中未找到值為的數(shù)據(jù)元素時，返回一特殊值表示查找失敗。2.1 線性表的概念和基本操作線性表的概念和基本操作 （5）insert_list(l,i,x) 插入操作，當(dāng)線性表l存在，插入位置正確 (1in+1,為插入前的表長)時，在線性表l的第 i 個位置上插入一個值為 x 的新元素，這樣使原序號為 i , i+1, . , n 的數(shù)據(jù)元素的序號變?yōu)?i+1,i+2, . , n+1，插入后表長 =

4、原表長+1。（6）delete_list(l,i) 刪除操作，當(dāng)線性表l存在，1in時，在線性表l中刪除序號為i的數(shù)據(jù)元素，刪除后使序號為 i+1, i+2, . , n 的元素變?yōu)樾蛱枮?i , i+1, . , n-1，新表長原表長-。2.1 線性表的概念和基本操作線性表的概念和基本操作 2.2 線性表的順序存儲結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)2.2.1 2.2.1 順序表的定義順序表的定義l線性表的順序存儲是指在內(nèi)存中用地址連續(xù)的一塊存儲空間順序存放線性表的各元素，用這種存儲形式存儲的線性表稱其為順序表。 線性表的順序存儲示意圖 l第i個數(shù)據(jù)元素的地址為： loc(ai)=loc(a)+(i-1

5、)*d 1inl從結(jié)構(gòu)性上考慮，通常將data和last封裝成一個結(jié)構(gòu)體作為順序表的類型，具體描述如下表示：2.2.1 順序表的定義 #define maxsize 100 #define datatype int typedef struct datatype datamaxsize ; int last ; seqlist ;2.2.1 順序表的定義l順序表的初始化問題，順序表的初始化即構(gòu)造一個空表，這對表是一個加工型的運算，因此，將l設(shè)為指針參數(shù)，首先動態(tài)分配存儲空間，然后，將表中 last 設(shè)置為0，表示表中沒有數(shù)據(jù)元素。算法如下： seqlist *init_seqlist( ) s

6、eqlist *l; l=(seqlist *)malloc(sizeof(seqlist); l-last=0; return l; 2.2.1 順序表的定義l線性表的插入是指在表的第i個位置上插入一個值為 x 的新元素，插入后使原表長為 n的表(a1，a2，.，ai-1，ai，ai+1，.，an)成為表長為 n+1表(a1，a2，.，ai-1，x，ai，ai+1，.，an)。i 的取值范圍為1in+1。 步驟如下： 將aian 順序向下移動，為新元素讓出位置； 將 x 置入空出的第i個位置； 修改 last 指針(相當(dāng)于修改表長)，使之增加1。 2.2.2 順序表上元素的插入順序表上元素的

7、插入 l算法如下： int insert_seqlist(seqlist *l，int i，datatype x) int j; if (l-last=maxsize) printf(表已滿); return(-1); /*表空間已滿，不能插入*/ if ( i l-last+1 ) /*檢查插入位置的正確性*/ printf(位置錯);return(0); 2.2.2 順序表上元素的插入順序表上元素的插入 for(j=l-last ; j=i ; j- ) l-dataj=l-dataj-1; /* 結(jié)點依次向后移動 */ l-datai-1=x; /*新元素插入*/ l-last+; /*

8、last仍指向最后元素*/ return (1); /*插入成功，返回*/ 2.2.2 順序表上元素的插入順序表上元素的插入l設(shè)在第i個位置上作插入的概率為pi，則平均移動數(shù)據(jù)元素的次數(shù)：l設(shè)：pi=1/ (n+1) ，即為等概率情況，則：l在順序表上做插入操作需移動表中一半的數(shù)據(jù)元素。顯然時間復(fù)雜度為(n) 11)1(eniiininp11112)1(11)1(eniniiinninninp2.2.2 順序表上元素的插入順序表上元素的插入l順序表上元素的刪除 線性表的刪除運算是指將表中第 i 個元素從線性表中去掉，刪除后使原表長為 n 的線性表(a1，a2，. ，ai-1，ai，ai+1，.

9、，an)成為表長為 n-1 的線性表(a1，a2，. ，ai-1， ai+1，. ，an)。i 的取值范圍為：1in 。l順序表上完成這一運算的步驟如下： 將ai+1an 順序向上移動。 修改last指針（相當(dāng)于修改表長），使之減1。 2.2.2 順序表上元素的順序表上元素的刪除刪除l順序表上元素的定位 順序表上元素的定位主要為按值查找，按值查找是指在線性表中查找與給定值x相等的數(shù)據(jù)元素。在順序表中完成該運算最簡單的方法是：從第一個元素 a1 起依次和x比較，直到找到一個與x相等的數(shù)據(jù)元素，則返回它在順序表中的存儲下標或序號（二者差一）；或者查遍整個表都沒有找到與 x 相等的元素，返回0。2.

10、2 線性表的順序存儲線性表的順序存儲定位定位2.3 線性表的鏈式存儲結(jié)構(gòu)線性表的鏈式存儲結(jié)構(gòu)l順序表的存儲特點是用物理上的相鄰實現(xiàn)了邏輯上的相鄰，它要求用連續(xù)的存儲單元順序存儲線性表中各元素，因此，對順序表插入、刪除時需要通過移動數(shù)據(jù)元素來實現(xiàn)，影響了運行效率。l 本節(jié)介紹線性表鏈式存儲結(jié)構(gòu)，它不需要用地址連續(xù)的存儲單元來實現(xiàn)，因為它不要求邏輯上相鄰的兩個數(shù)據(jù)元素物理上也相鄰，它是通過“鏈”建立起數(shù)據(jù)元素之間的邏輯關(guān)系來，因此對線性表的插入、刪除不需要移動數(shù)據(jù)元素。l單鏈表的定義 為建立起數(shù)據(jù)元素之間的線性關(guān)系，對每個數(shù)據(jù)元素ai，除了存放數(shù)據(jù)元素的自身的信息ai之外，還需要和ai一起存放其后

11、繼ai+1所在的存儲單元的地址，這兩部分信息組成一個“結(jié)點”，結(jié)點的結(jié)構(gòu)如圖所示每個元素都如此。存放數(shù)據(jù)元素信息的稱為數(shù)據(jù)域，存放其后繼地址的稱為指針域。n個元素的線性表通過每個結(jié)點的指針域拉成了一個“鏈子”，稱之為鏈表。因為每個結(jié)點中只有一個指向后繼的指針，所以稱其為單鏈表。datanext2.3.1 單鏈表的定義和操作實現(xiàn)單鏈表的定義和操作實現(xiàn)l鏈表是由一個個結(jié)點構(gòu)成的，結(jié)點定義如下： typedef struct node datatype data; struct node *next; linklist；l作為線性表的一種存儲結(jié)構(gòu)，我們關(guān)心的是結(jié)點間的邏輯結(jié)構(gòu)，而對每個結(jié)點的實際地址

12、并不關(guān)心，所以通常的單鏈表用下圖表示。 2.3.1 單鏈表的定義和操作實現(xiàn)單鏈表的定義和操作實現(xiàn)l建立單鏈表 （1）頭插入法建立鏈表 鏈表與順序表不同，它是一種動態(tài)管理的存儲結(jié)構(gòu)，鏈表中的每個結(jié)點占用的存儲空間不是預(yù)先分配，而是運行時系統(tǒng)根據(jù)需求而生成的，因此建立單鏈表從空表開始，每讀入一個數(shù)據(jù)元素則申請一個新結(jié)點，然后將此結(jié)點放在鏈表中已有結(jié)點的前面，作為新鏈表的第一個結(jié)點，因此稱為頭部插入法。如圖所示：2.3.1 單鏈表的定義和操作實現(xiàn)單鏈表的定義和操作實現(xiàn)l算法如下： linklist *creat_linklist1( ) linklist *h=null； /*空表*/ linkli

13、st *s; int x; /*設(shè)數(shù)據(jù)元素的類型為int*/ scanf(%d,&x); while (x!=flag) s=( linklist *)malloc(sizeof(linklist); s-data=x; s-next=h; h=s; scanf (%d,&x); return h; 頭插入建立單鏈表簡單，但讀入的數(shù)據(jù)元素的順序與生成的鏈表中元素的順序是相反的，若希望次序一致，則用尾插入的方法。2.3.1 單鏈表的定義和操作實現(xiàn)單鏈表的定義和操作實現(xiàn)l（2）尾插入建立鏈表 尾插入算法建立鏈表的過程和頭插入法正好相反，它每次都將新結(jié)點放在已有鏈表的最后面，成為新鏈

14、表的尾結(jié)點。因為每次是將新結(jié)點插入到鏈表的尾部，需要先找到舊鏈表的尾結(jié)點，然后才能將新結(jié)點放在其后面，所以為了提高程序效率，需加入一個指針 r 用來始終指向鏈表中的尾結(jié)點，以便能夠?qū)⑿陆Y(jié)點快速插入到鏈表的尾部。2.3.1 單鏈表的定義和操作實現(xiàn)單鏈表的定義和操作實現(xiàn)l算法如下： linklist *creat_linklist2( ) linklist *l=null; linklist *s,*r=null; int x; /*設(shè)數(shù)據(jù)元素的類型為int*/ scanf(%d,&x); while (x!=flag) s=( linklist *)malloc(sizeof(linkl

15、ist); s-data=x; if (l=null) l=s; /*第一個結(jié)點的處理*/ else r-next=s; /*其它結(jié)點的處理*/ r=s; /*r 指向新的尾結(jié)點*/ scanf(%d,&x); if ( r!=null) r-next=null; /*對于非空表，最后結(jié)點的指針域放空指針*/ return l; 2.3.1 單鏈表的定義和操作實現(xiàn)單鏈表的定義和操作實現(xiàn)l頭結(jié)點 在上面的算法中，第一個結(jié)點的處理和其它結(jié)點是不同的，原因是第一個結(jié)點加入時鏈表為空，它沒有直接前驅(qū)結(jié)點，它的地址就是整個鏈表的指針，需要放在鏈表的頭指針變量中；而其它結(jié)點有直接前驅(qū)結(jié)點，其地址放

16、入直接前驅(qū)結(jié)點的指針域。 為了方便操作，有時在鏈表的頭部加入一個“頭結(jié)點”，頭結(jié)點的類型與數(shù)據(jù)結(jié)點一致，標識鏈表的頭指針變量l中存放該結(jié)點的地址，這樣即使是空表，頭指針變量l也不為空了。頭結(jié)點的加入使得“第一個結(jié)點”的問題不再存在，也使得“空表”和“非空表”的處理成為一致。 下圖是帶頭結(jié)點的單鏈表空表和非空表的示意圖。 2.3.1 單鏈表的定義和操作實現(xiàn)單鏈表的定義和操作實現(xiàn)l單鏈表求表長 算法思路：設(shè)一個移動指針和計數(shù)器，初始化后，所指結(jié)點后面若還有結(jié)點，向后移動，計數(shù)器加1。 （1）設(shè)l是帶頭結(jié)點的單鏈表（線性表的長度不包括頭結(jié)點），求表長的算法如下： int length_linklis

17、t1(linklist *l) linklist * p=l; /* p指向頭結(jié)點*/ int j=0; while (p-next) p=p-next; j+； /* p所指的是第 j 個結(jié)點*/ return j; 2.3.1 單鏈表的定義和操作實現(xiàn)單鏈表的定義和操作實現(xiàn) （2）設(shè)l是不帶頭結(jié)點的單鏈表，求表長的算法如下： int length_linklist2(linklist *l) linklist * p=l; int j; if (p=null) return 0; /*空表的情況*/ j=1; /*在非空表的情況下，p所指的是第一個結(jié)點*/; while (p-next )

18、p=p-next; j+; return j; 不帶頭結(jié)點的單鏈表空表情況要單獨處理。兩個算法的時間復(fù)雜度均為o(n)。 2.3.1 單鏈表的定義和操作實現(xiàn)單鏈表的定義和操作實現(xiàn)l單鏈表查找操作 單鏈表的查找分為按序號查找和按值查找 （1）按序號查找 get_linklist(l,i) 算法思路：從鏈表的第一個元素結(jié)點起，判斷當(dāng)前結(jié)點是否是第i個，若是，則返回該結(jié)點的指針，否則繼續(xù)后一個，表結(jié)束為止；沒有第個結(jié)點時返回空。算法如下： linklist * get_linklist(linklist *l, int i); /*在單鏈表l中查找第i個元素結(jié)點，找到返回其指針，否則返回空*/ li

19、nklist * p=l; int j=0; while (p-next !=null & jnext; j+; if (j=i) return p; else return null; 2.3.1 單鏈表的定義和操作實現(xiàn)單鏈表的定義和操作實現(xiàn) （2）按值查找即定位 locate_linklist(l,x) 算法思路：從鏈表的第一個元素結(jié)點起，判斷當(dāng)前結(jié)點其值是否等于x，若是，返回該結(jié)點的指針，否則繼續(xù)后一個，表結(jié)束為止；找不到時返回空。算法如下： linklist * locate_linklist( linklist *l, datatype x) /*在單鏈表l中查找值為x的結(jié)點

20、，找到后返回其指針，否則返回空*/ linklist * p=l-next; while ( p!=null & p-data != x) p=p-next; return p; 在單鏈表中查找元素的兩種操作的時間復(fù)雜度均為o(n)。2.3.1 單鏈表的定義和操作實現(xiàn)單鏈表的定義和操作實現(xiàn)l單鏈表插入操作（1）后插結(jié)點 設(shè)p指向單鏈表中某結(jié)點，s指向待插入的值為x的新結(jié)點，將s插入到p的后面，插入示意圖如圖，操作如下： s-next=p-next; p-next=s;2.3.1 單鏈表的定義和操作實現(xiàn)單鏈表的定義和操作實現(xiàn)（2）前插結(jié)點 設(shè)指向鏈表中某結(jié)點，指向待插入的值為x的新結(jié)點，

21、將s插入到p的前 面，插入示意圖如圖，與后插不同的是：首先要找到p的前驅(qū)q，然后再完 成在q之后插入s，設(shè)單鏈表頭指針為l。 算法思路（此算法描述在鏈表第i個位置前插入元素x）： 找到第i-1個結(jié)點；若存在繼續(xù)，否則結(jié)束。 申請、填裝新結(jié)點； 將新結(jié)點插入，結(jié)束。2.3.1 單鏈表的定義和操作實現(xiàn)單鏈表的定義和操作實現(xiàn)l單鏈表刪除操作單鏈表刪除操作 刪除結(jié)點：設(shè)p指向單鏈表中某結(jié)點，刪除p，操作示意圖如圖所示。通過示意圖可見，要實現(xiàn)對結(jié)點p的刪除，首先要找到p的前驅(qū)結(jié)點q，然后完成指針的操作即可。 算法思路（此算法描述刪除第i個結(jié)點）： 找到第i-1個結(jié)點；若存在繼續(xù)，否則結(jié)束； 若存在第i個

22、結(jié)點則繼續(xù)，否則結(jié)束； 刪除第i個結(jié)點，結(jié)束。2.3.1 單鏈表的定義和操作實現(xiàn)單鏈表的定義和操作實現(xiàn)l循環(huán)鏈表定義和操作實現(xiàn) 對于單鏈表而言，最后一個結(jié)點的指針域是空指針，如果將該鏈表頭指針置入該指針域，則使得鏈表頭尾結(jié)點相連，就構(gòu)成了單循環(huán)鏈表，如圖所示。當(dāng)循環(huán)鏈表為空時，僅有頭節(jié)點，并且頭節(jié)點的指針域指向頭節(jié)點自身。非空表 空表使用尾指針r標識的循環(huán)鏈表 2.3.2 循環(huán)鏈表定義和操作實現(xiàn)循環(huán)鏈表定義和操作實現(xiàn) l對兩個單循環(huán)鏈表h1 、h2的連接操作，是將h2的第一個數(shù)據(jù)結(jié)點接到h1的尾結(jié)點，如用頭指針標識，則需要找到第一個鏈表的尾結(jié)點，其時間復(fù)雜性為o(n)，而鏈表若用尾指針r1、r

23、2來標識，則時間性能為o(1)。操作如下： p= r1 next; /*保存r1 的頭結(jié)點指針*/ r1-next=r2-next-next; /*頭尾連接*/ free(r2-next); /*釋放第二個表的頭結(jié)點*/ r2-next=p; /*組成循環(huán)鏈表*/ 這一過程可見下圖。2.3.2 循環(huán)鏈表定義和操作實現(xiàn)循環(huán)鏈表定義和操作實現(xiàn) l雙向鏈表定義和操作實現(xiàn) 以上討論的單鏈表的結(jié)點中只有一個指向其后繼結(jié)點的指針域next，因此若已知某結(jié)點的指針為p，其后繼結(jié)點的指針則為p-next ，而找其前驅(qū)則只能從該鏈表的頭指針開始，順著各結(jié)點的next域進行，也就是說找后繼的時間性能是o(1)，找

24、前驅(qū)的時間性能是o(n)，如果也希望找前驅(qū)的時間性能達到o(1)，則只能付出空間的代價：每個結(jié)點再加一個指向前驅(qū)的指針域，結(jié)點的結(jié)構(gòu)為如下圖所示，用這種結(jié)點組成的鏈表稱為雙向鏈表。 priordatanext2.3.2 循環(huán)鏈表定義和操作實現(xiàn)循環(huán)鏈表定義和操作實現(xiàn) 2.3.3 雙向鏈表定義和操作實現(xiàn)雙向鏈表定義和操作實現(xiàn)雙向鏈表結(jié)點的定義如下： typedef struct dlnode datatype data; struct dlnode *prior,*next; dlinklist;l和單鏈表類似，雙向鏈表通常也是用頭指針標識，也可以帶頭結(jié)點做成循環(huán)結(jié)構(gòu)，下圖是帶頭結(jié)點的雙向循環(huán)鏈表

25、示意圖。顯然通過某結(jié)點的指針p即可以直接得到它的后繼結(jié)點的指針p-next，也可以直接得到它的前驅(qū)結(jié)點的的指針p-prior。這樣在有些操作中需要找前驅(qū)時，則無需再用循環(huán)。非空表 空表 2.3.3 雙向鏈表定義和操作實現(xiàn)雙向鏈表定義和操作實現(xiàn)l雙向鏈表中結(jié)點的插入雙向鏈表中結(jié)點的插入 設(shè)p指向雙向鏈表中某結(jié)點，s指向待插入的值為x的新結(jié)點，將*s插入到*p的前面，插入如下圖所示。 操作如下： s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s;2.3.3 雙向鏈表定義和操作實現(xiàn)雙向鏈表定義和操作實現(xiàn)l雙向鏈表中結(jié)點的刪除雙向鏈表中結(jié)點的刪除

26、 設(shè)p指向雙向鏈表中某結(jié)點，刪除*p。操作示意圖如下圖所示。 操作如下： p-prior-next=p-next; p-next-prior=p-prior; free(p); 2.3.3 雙向鏈表定義和操作實現(xiàn)雙向鏈表定義和操作實現(xiàn)2.4 線性表兩種存儲方式的比較線性表兩種存儲方式的比較 l順序存儲的優(yōu)點： 方法簡單，各種高級語言中都有數(shù)組，容易實現(xiàn)。 不用為表示結(jié)點間的邏輯關(guān)系而增加額外的存儲開銷。 順序表具有按元素序號隨機訪問的特點。l 順序結(jié)構(gòu)的缺點： 在順序表中做插入刪除操作時，平均移動大約表中一半的元素，因此對n較大的順序表效率低。 需要預(yù)先分配足夠大的存儲空間，估計過大，可能會導(dǎo)

27、致順序表后部大量閑置；預(yù)先分配過小，又會造成溢出。鏈表的優(yōu)缺點恰好與順序表相反。 l在實際中選取存儲結(jié)構(gòu)基于以下幾點考慮：（1）基于存儲的考慮（2）基于運算的考慮 （3）基于環(huán)境的考慮2.4 線性表兩種存儲方式的比較線性表兩種存儲方式的比較 2.5 應(yīng)用舉例分析應(yīng)用舉例分析l例1 一元多項式相加。 數(shù)學(xué)上，n階一元多項式可以用下面的式子表示：a(x) = anxn +an-1xn-1 +a1x1 + a0 x0 (a0), a(x)的階數(shù)為n。一個n階一元多項式中含有n+1項系數(shù)，并惟一確定，分別對應(yīng)xn的系數(shù)到x0的系數(shù)。在計算機中，描述一個一元多項式，可用線性表表示 a=(n, an, a

28、n-1, an-2, ,a1, a0)，其中第一個元素是階數(shù)，后面都是系數(shù)，按階次逐一遞減排列，a的長度是n+2。數(shù)學(xué)上，一元多項式的另一種表示方法是：a(x)=bx+ bx + + bx ,式中每一項都是非零系數(shù)項，bi是非零系數(shù)，ei具有遞減性。這種表示法對稀疏型多項式特別適合。在計算機中，可用線性表表示 a=(m,em,bm,em-1,bm-1,e1,b1)，其中第一個元素是多項式中非零系數(shù)的項數(shù)，后面是每個項對應(yīng)的階次和系數(shù)，每兩項ei,bi對應(yīng)多項式中的某一非零系數(shù)項的指數(shù)和系數(shù)，a的長度是2m+1。l試用第二種表示方法寫出多項式相加的算法l例2 有順序表a和b，其元素均按從小到大的升序排列，編寫一個算法將它們合并成一個順序表c，要求c的元素也是從小到大的升序排列。 算法思路：依次掃描通過a和b的元素，比較當(dāng)前的元素的值，將較小值的元素賦給c，如此直到一個線性表掃描完畢，然后將未完的那