線性結構特點在數(shù)據(jù)元素的非空有限集中

1、第2章 線性表線性結構特點：在數(shù)據(jù)元素的非空有限集中 存在唯一的一個被稱作“第一個”的數(shù)據(jù)元素 存在唯一的一個被稱作“最后一個”的數(shù)據(jù)元素 除第一個外，集合中的每個數(shù)據(jù)元素均只有一個前驅 除最后一個外，集合中的每個數(shù)據(jù)元素均只有一個后繼2.1 線性表的類型定義1.線性表(Linear List) ：由n(n)個數(shù)據(jù)元素(結點)a1，a2， an組成的有限序列。其中數(shù)據(jù)元素的個數(shù)n定義為表的長度。當n=0時稱為空表，常常將非空的線性表(n0)記作： (a1，a2，an) 這里的數(shù)據(jù)元素ai(1in)只是一個抽象的符號，其具體含義在不同的情況下可以不同。 例1、26個英文字母組成的字母表 （A，B

2、，C、Z） 例2、某校從1978年到1983年各種型號的計算機擁有量的變化情況。 （6，17，28，50，92，188）例3、學生健康情況登記表如下：姓 名學 號性 別年齡 健康情況王小林790631 男 18 健康陳 紅790632 女 20 一般劉建平790633 男 21 健康張立立790634 男 17 神經(jīng)衰弱 . . .例4、一副撲克的點數(shù) （2，3，4，J，Q，K，A） 2.綜合以上例子可看出線性表的邏輯特征線性表的邏輯特征是： 1).在非空的線性表，有且僅有一個開始結點a1，它沒有直接前趨，而僅有一個直接后繼a2； 2).有且僅有一個終端結點an，它沒有直接后繼，而僅有一個直接

3、前趨an-1； 3).其余的內部結點ai(2in-1)都有且僅有一個直接前趨ai-1和一個直接后繼ai+1。 4). 線性表是一種典型的線性結構。 5).數(shù)據(jù)的運算是定義在邏輯結構上的，而運算的具體實現(xiàn)則是在存儲結構上進行的。3.抽象數(shù)據(jù)類型的定義為：P19算法2.1 例2-1 利用兩個線性表LA和LB分別表示兩個集合A和B，現(xiàn)要求一個新的集合A=AB。 void union(List &La，List Lb) /將所有在線性表Lb中但不在La中的數(shù)據(jù)元素插入到La中 La-len=listlength(La)； Lb-len=listlength(Lb)；/求線性表的長度 for(I

4、=1;I=lb-len;I+) getelem(lb，I，e)；/取Lb中第I個數(shù)據(jù)元素賦給e if(!locateelem(la，e，equal)listinsert(la，+la-en，e) /33333333333333333333333333333333333333337 算法2.2例2-2 巳知線性表LA和線性表LB中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要求將LA和LB歸并為一個新的線性表LC，且LC中的元素仍按值非遞減有序排列。 此問題的算法如下： void mergelist(list la，list lb，list &lc) initlist(lc); I=j=1;k=0;

5、 la-len=listlength(la); lb-len=listlength(lb); while(I=la-len)&(j=lb-len) getelem(la，I，ai);getelem(lb，j，bj); if(ai=bj)listinsert(lc，+k，ai);+I; elselistinsert(lc，+k，bj);+j; while(I=la-len) getelem(la，I+，ai);listinsert(lc，+k，ai); while(jdata表示p指向結點的數(shù)據(jù)域(*p).linkp-link表示p指向結點的指針域生成一個JD型新結點：p=(JD *)m

6、alloc(sizeof(JD);系統(tǒng)回收p結點：free(p)線性鏈表v定義：結點中只含一個指針域的鏈表叫，也叫單鏈表頭結點：在單鏈表第一個結點前附設一個結點叫頭結點指針域為空表示線性表為空ha1a2頭結點an .h空表v單鏈表的基本運算l查找：查找單鏈表中是否存在結點X，若有則返回指向X結點的指針；否則返回NULLu算法描述While循環(huán)中語句頻度為若找到結點X，為結點X在表中的序號否則，為n nOnTpabxsu算法評價l插入：在線性表兩個數(shù)據(jù)元素a和b間插入x，已知p指向as-link=p-link;p-link=s; 1OnTu算法描述u算法評價u算法描述pabc 1OnTu算法評價

7、l刪除：單鏈表中刪除b，設p指向ap-link=p-link-link; nOnTl動態(tài)建立單鏈表算法：設線性表n個元素已存放在數(shù)組a中，建立一個單鏈表，h為頭指針u算法描述u算法評價h頭結點an 0h頭結點an-10an a2.h頭結點an-10an ha1a2頭結點an .0Ch2_3.ch頭結點0v單鏈表特點l它是一種動態(tài)結構，整個存儲空間為多個鏈表共用l不需預先分配空間l指針占用額外存儲空間l不能隨機存取，查找速度慢循環(huán)鏈表(circular linked list)v循環(huán)鏈表是表中最后一個結點的指針指向頭結點，使鏈表構成環(huán)狀v特點：從表中任一結點出發(fā)均可找到表中其他結點，提高查找效率

8、v操作與單鏈表基本一致,循環(huán)條件不同l單鏈表p或p-link=NULLl循環(huán)鏈表p或p-link=Hhh空表雙向鏈表（double linked list）單鏈表具有單向性的缺點v結點定義typedef struct node datatype element; struct node *prior,*next;JD;priorelementnextL空雙向循環(huán)鏈表：非空雙向循環(huán)鏈表： LABbcapp-prior-next= p= p-next-proir;bcaPvoid del_dulist(JD *p)p-prior-next=p-next; p-next-prior=p-prior;

9、 free(p);v刪除l算法描述l算法評價：T(n)=O(1)p-prior-next=p-next;p-next-prior=p-prior;void ins_dulist(JD* p,int x)JD *s; s=(JD*)malloc(sizeof(JD); s-element=x; s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s;l算法描述l算法評價：T(n)=O(1)xSbaPv插入2.4 線性表的應用舉例 一元多項式的表示及相加一元多項式的表示：nnnxPxPxPPxP2210)(),(210nPPPPP可用線性表P表示2

10、00001000231)(xxxS但對S(x)這樣的多項式浪費空間一般emmnxPxPxPxPee2121)(其中為非零系數(shù)）（iPemee210用數(shù)據(jù)域含兩個數(shù)據(jù)項的線性表表示emPePePm，2121其存儲結構可以用順序存儲結構，也可以用單鏈表單鏈表的結點定義typedef struct node int coef,exp; struct node *next;JD;coefexpnext17787172522117)()()(9228)(5937)(xxxxBxAxCxxxxBxxxxA-1A7 0 3 1 9 8 5 17 -1B8 1 22 7 -9 8 -1C7 0 11 1 22

11、 7 5 17 一元多項式相加設p,q分別指向A,B中某一結點，p,q初值是第一結點比較p-exp與q-expp-exp exp: p結點是和多項式中的一項 p后移,q不動p-exp q-exp: q結點是和多項式中的一項 將q插在p之前,q后移,p不動p-exp = q-exp: 系數(shù)相加0：從A表中刪去p, 釋放p,q，p,q后移0：修改p系數(shù)域, 釋放q，p,q后移直到p或q為NULL 若q=NULL，結束 若p=NULL，將B中剩余部分連到A上即可運算規(guī)則 2.2 線性表的順序存儲結構2.2.1 線性表 把線性表的結點按邏輯順序依次存放在一組地址連續(xù)的存儲單元里。用這種方法存儲的線性表

12、簡稱順序表。 假設線性表的每個元素需占用l個存儲單元，并以所占的第一個單元的存儲地址作為數(shù)據(jù)元素的存儲位置。則線性表中第I+1個數(shù)據(jù)元素的存儲位置LOC( a i+1)和第i個數(shù)據(jù)元素的存儲位置LOC(a I )之間滿足下列關系： LOC(a i+1)=LOC(a i)+l 線性表的第i個數(shù)據(jù)元素ai的存儲位置為： LOC(ai)=LOC(a1)+(I-1)*l 由于C語言中的一維數(shù)組也是采用順序存儲表示，故可以用數(shù)組類型來描述順序表。又因為除了用數(shù)組來存儲線性表的元素之外，順序表還應該用一個變量來表示線性表的長度屬性，所以我們用結構類型來定義順序表類型。 # define ListSize

13、100 typedef int DataType; typedef struc DataType dataListSize; int length; Sqlist;2.2.2 順序表上實現(xiàn)的基本操作 在順序表存儲結構中，很容易實現(xiàn)線性表的一些操作，如線性表的構造、第i個元素的訪問。 注意：C語言中的數(shù)組下標從“0”開始，因此，若L是Sqlist類型的順序表，則表中第i個元素是l.dataI-1。 以下主要討論線性表的插入和刪除兩種運算。 1、插入 線性表的插入運算是指在表的第I(1in+1個位置上，插入一個新結點x，使長度為n的線性表 (a1，a i-1，ai，an) 變成長度為n+1的線性表

14、 (a1，a i-1，x，ai，an) 算法2.3Void InsertList(Sqlist*L，DataType x，int I) int j; if(Il.length+1) printf(“Position error”); return ERROR if(l.length=ListSize) printf(“overflow”); exit(overflow); for(j=l.length-1;j=I-1;j-) l.dataj+1=l.dataj; l.dataI-1=x; l.length+; 現(xiàn)在分析算法的復雜度。 這里的問題規(guī)模是表的長度，設它的值為。該算法的時間主要化費在

15、循環(huán)的結點后移語句上，該語句的執(zhí)行次數(shù)（即移動結點的次數(shù)）是。由此可看出，所需移動結點的次數(shù)不僅依賴于表的長度，而且還與插入位置有關。當時，由于循環(huán)變量的終值大于初值，結點后移語句將不進行；這是最好情況，其時間復雜度O（1）；當=1時，結點后移語句將循環(huán)執(zhí)行n次，需移動表中所有結點，這是最壞情況，其時間復雜度為O（n）。 由于插入可能在表中任何位置上進行，因此需分析算法的平均復雜度 在長度為n的線性表中第i個位置上插入一個結點，令Eis(n)表示移動結點的期望值（即移動的平均次數(shù)），則在第i個位置上插入一個結點的移動次數(shù)為n-I+1。故 Eis(n)= pi(n-I+1) 不失一般性，假設在表

16、中任何位置(1in+1)上插入結點的機會是均等的，則 p1=p2=p3=p n+1=1/(n+1) 因此，在等概率插入的情況下， Eis(n)= (n-I+1)/(n+1)=n/2 也就是說，在順序表上做插入運算，平均要移動表上一半結點。當表長 n較大時，算法的效率相當?shù)?。雖然Eis(n)中n的的系數(shù)較小，但就數(shù)量級而言，它仍然是線性階的。因此算法的平均時間復雜度為O(n)。 2、刪除 線性表的刪除運算是指將表的第i(1in)結點刪除，使長度為n的線性表： (a1，a i-1，ai，a i+1，an) 變成長度為n-1的線性表 (a1，a i-1，a i+1，an) Void deleteLi

17、st(Sqlist*L，int I) int j; if(Il.length) printf(“Position error”); return ERROR for(j=i;jdata=ch; pnext=head; head=p; ch=getchar( ); return (head); listlink createlist(int n) int data; linklist head; listnode *p head=null; for(i=n;i0;-i) p=(listnode*)malloc(sizeof(listnode); scanf(%d，&pdata); pne

18、xt=head; head=p; return(head); 2、尾插法建表 頭插法建立鏈表雖然算法簡單，但生成的鏈表中結點的次序和輸入的順序相反。若希望二者次序一致，可采用尾插法建表。該方法是將新結點插入到當前鏈表的表尾上，為此必須增加一個尾指針r，使其始終指向當前鏈表的尾結點。例： linklist creater( ) char ch; linklist head; listnode *p，*r; /(， *head;) head=NULL;r=NULL; while(ch=getchar( )!= n) p=(listnode *)malloc(sizeof(listnode); pd

19、ata=ch; if(head=NULL) head=p; else rnext=p; r=p; if (r!=NULL) rnext=NULL; return(head); 說明：第一個生成的結點是開始結點，將開始結點插入到空表中，是在當前鏈表的第一個位置上插入，該位置上的插入操作和鏈表中其它位置上的插入操作處理是不一樣的，原因是開始結點的位置是存放在頭指針（指針變量）中， 而其余結點的位置是在其前趨結點的指針域中。算法中的第一個if語句就是用來對第一個位置上的插入操作做特殊處理。算法中的第二個if語句的作用是為了分別處理空表和非空表兩種不同的情況，若讀入的第一個字符就是結束標志符，則鏈表h

20、ead是空表，尾指針r亦為空，結點*r不存在；否則鏈表head非空，最后一個尾結點*r是終端結點，應將其指針域置空。 如果我們在鏈表的開始結點之前附加一個結點，并稱它為頭結點，那么會帶來以下兩個優(yōu)點： a、由于開始結點的位置被存放在頭結點的指針域中，所以在鏈表的第一個位置上的操作就 和在表的其它位置上的操作一致，無需進行特殊處理；b、無論鏈表是否為空，其頭指針是指向頭結點 在的非空指針（空表中頭結點的指針域為空），因此空表和非空表的處理也就統(tǒng)一了。 其算法如下：linklist createlistr1( ) char ch; linklist head=(linklist)malloc(si

21、zeof(listnode); listnode *p，*r r=head; while(ch=getchar( )!= n p=(listnode*)malloc(sizeof(listnode); pdata=ch; pnext=p; r=p; rnext=NULL; return(head); 上述算法里動態(tài)申請新結點空間時未加錯誤處理，可作下列處理： p=(listnode*)malloc(sizeof(listnode) if(p=NULL) error(No space for node can be obtained); return ERROR; 以上算法的時間復雜度均為O(n

22、)。二、查找運算 1、按序號查找 在鏈表中，即使知道被訪問結點的序號i，也不能象順序表中那樣直接按序號i訪問結點，而只能從鏈表的頭指針出發(fā)，順鏈域next逐個結點往下搜索，直到搜索到第i個結點為止。因此，鏈表不是隨機存取結構。 設單鏈表的長度為n，要查找表中第i個結點，僅當1in時，i的值是合法的。但有時需要找頭結點的位置，故我們將頭結點看做是第0 個結點，其算法如下：Listnode * getnode(linklist head ， int i) int j; listnode * p; p=head;j=0; while(pnext & jnext; j+; if (i=j) r

23、eturn p; else return NULL; 2、按值查找 按值查找是在鏈表中，查找是否有結點值等于給定值key的結點，若有的話，則返回首次找到的其值為key的結點的存儲位置；否則返回NULL。查找過程從開始結點出發(fā)，順著鏈表逐個將結點的值和給定值key作比較。其算法如下：Listnode * locatenode(linklist head，int key) listnode * p=headnext; while( p & pdata!=key) p=pnext; return p; 該算法的執(zhí)行時間亦與輸入實例中的的取值key有關，其平均時間復雜度的分析類似于按序號查找，

24、也為O(n)。三、插入運算 插入運算是將值為x的新結點插入到表的第i個結點的位置上，即插入到ai-1與ai之間。因此，我們必須首先找到ai-1的存儲位置p，然后生成一個數(shù)據(jù)域為x的新結點*p，并令結點*p的指針域指向新結點，新結點的指針域指向結點ai。從而實現(xiàn)三個結點ai-1，x和ai之間的邏輯關系的變化，插入過程如：具體算法如下： void insertnode(linklist head，datetype x，int i) listnode * p，*q; p=getnode(head，i-1); if(p=NULL) error(position error); q=(listnode

25、*)malloc(sizeof(listnode); qdata=x; qnext=pnext; pnext=q; 設鏈表的長度為n，合法的插入位置是1in+1。注意當i=1時，getnode找到的是頭結點，當 i=n+1時，getnode找到的是結點an。因此，用i-1做實參調用getnode時可完成插入位置的合法性檢查。算法的時間主要耗費在查找操作getnode上，故時間復雜度亦為O(n)。四、刪除運算 刪除運算是將表的第i個結點刪去。因為在單鏈表中結點ai的存儲地址是在其直接前趨結點a a i-1的指針域next中，所以我們必須首先找到 a i-1的存儲位置p。然后令pnext指向ai的

26、直接后繼結點，即把ai從鏈上摘下。最后釋放結點ai的空間，將其歸還給“存儲池”。此過程為：具體算法如下： void deletelist(linklist head， int i) listnode * p， *r; p=getnode(head，i-1); if(p= =NULL | pnext= =NULL) return ERROR; r=pnext; pnext=rnext; free( r ) ; 設單鏈表的長度為n，則刪去第i個結點僅當1in時是合法的。注意，當i=n+1時，雖然被刪結點不存在，但其前趨結點卻存在，它是終端結點。因此被刪結點的直接前趨*p存在并不意味著被刪結點就一定

27、存在，僅當*p存在（即p!=NULL）且*p不是終端結點 （即pnext!=NULL）時，才能確定被刪結點存在。 顯然此算法的時間復雜度也是O(n)。 從上面的討論可以看出，鏈表上實現(xiàn)插入和刪除運算，無須移動結點，僅需修改指針。2.3.2 循環(huán)鏈表 循環(huán)鏈表時一種頭尾相接的鏈表。其特點是無須增加存儲量，僅對表的鏈接方式稍作改變，即可使得表處理更加方便靈活。單循環(huán)鏈表：在單鏈表中，將終端結點的指針域NULL改為指向表頭結點的或開始結點，就得到了單鏈形式的循環(huán)鏈表，并簡單稱為單循環(huán)鏈表。 為了使空表和非空表的處理一致，循環(huán)鏈表中也可設置一個頭結點。這樣，空循環(huán)鏈表僅有一個自成循環(huán)的頭結點表示。如下

28、圖所示： a1 an .head 非空表 空表 在用頭指針表示的單鏈表中，找開始結點a1的時間是O(1)，然而要找到終端結點an，則需從頭指針開始遍歷整個鏈表，其時間是O(n) 在很多實際問題中，表的操作常常是在表的首尾位置上進行，此時頭指針表示的單循環(huán)鏈表就顯得不夠方便.如果改用尾指針rear來表示單循環(huán)鏈表，則查找開始結點a1和終端結點an都很方便，它們的存儲位置分別是(rearnext) next和rear，顯然，查找時間都是O(1)。因此，實際中多采用尾指針表示單循環(huán)鏈表。 由于循環(huán)鏈表中沒有NULL指針，故涉及遍歷操作時，其終止條件就不再像非循環(huán)鏈表那樣判斷p或pnext是否為空，而是判斷它們是否等于某一指定指針，如頭指什或尾指針等。例、在鏈表上實現(xiàn)將兩個線性表(a1，a2，a3，an)和(b1，b2，b3，bn)鏈接成一個線性表的運算。 linklist connect(linklist heada，linklist headb) linklist p=headanext; headanext=(headbnext)next free(headbnext); headbnext=p; return(headb); 2.3.3雙鏈表 雙向鏈表(Double linked list):在單鏈表的每個結點里再增加一個指向其直接前趨的指針域prior。這樣就形成的鏈