1、第二章 線性表,2.1 順序表 2.2 線性鏈表 2.3 串,線性表是由n個類型相同的數(shù)據(jù)元素組成的有限序列。通常表示成下列形式： LinearList= a 1 , a 2 , . , a i-1 , a i , a i+1 , . , a n 例： 1、英文字母表（A,B,C,.Z) 2、一個星期的七天（星期一，星期二，星期天） 3、一年的12月（一月，二月，12月）,線性表的順序存儲結(jié)構(gòu)是指用一組連續(xù)的存儲單元按元素間的邏輯關(guān)系依次存儲線性表中的每個數(shù)據(jù)元素。通常稱這種存儲結(jié)構(gòu)的線性表為順序表。 元素地址計(jì)算方法： LOC(ai+1)=LOC(ai)+L LOC(ai)=LOC(a1)+

2、(i-1)*L,2.1 順序表,元素n,.,元素i,.,元素2,元素1,Lo,Lo+L,Lo+(i-1)*L,Lo+（n-1)*L,存儲地址,存儲內(nèi)容,順序存儲結(jié)構(gòu),位序,2,1,i,n,1、順序表的類定義 由于高級語言程序設(shè)計(jì)中的數(shù)組也有隨機(jī)存取的特性，因此，通常都用數(shù)組來描述數(shù)據(jù)結(jié)構(gòu)中的順序存儲結(jié)構(gòu)。 public class LinearList1 private int table ； private int n； ,2、順序表的操作 （1）初始化 使用構(gòu)造方法創(chuàng)建表對象，為順序表分配存儲空間，設(shè)置順序表為空狀態(tài)。 public LinearList1（int n） table=new

3、 int n; this.n=0; ,(2)判斷空與滿的狀態(tài) public boolean isEmpty( ) return n=0; public boolean isFull( ) return n=table.length; ,(3)返回順序表長度 public int length( ) return n; ,(4)讀表中的第i個元素 public int get ( int i) if(i0 ,（5）設(shè)置順序表的第i個數(shù)據(jù)元素值 public void set ( int i, int k) if (i0 ,(6)查找 public boolean contains (int k)

4、 int j=indexof(k); if(j!=-1) return true; else return false; ,public int indexof (int k) int j=0; while(j=0 ,(7)插入 線性表的插入是指在第i（1i n+1）個元素之前插入一個新的數(shù)據(jù)元素x，使長度為n的線性表 ( a 1 , a 2 , . , a i-1 , a i , a i+1 , . , a n ) 變成長度為n+1的線性表 ( a 1 , a 2 , . , a i-1 , x , a i , a i+1 , . , a n ) 數(shù)據(jù)元素a i-1 和 a i 之間的邏輯關(guān)

5、系發(fā)生了變化。在順序表中，由于邏輯上相鄰的數(shù)據(jù)元素在物理上也是相鄰的，因此除非是在最后一個元素后插入，否則必須將第i至第n共（n-i+1)個元素后移一個單元。,public void insert(int i,int k) int j; if(!isFull( ) if(in) i=n+1; for(j=n-1;j=i-1;j- -) tablej+1=tablej; tablei-1=k;n+; else system.out.println(“數(shù)組已滿,無法插入”); ,public void insert(int i,int k) insert(n+1,k); ,設(shè)Pi是在第i個元素之前

6、插入一個元素的概率，則在長度為n的線性表中插入一個元素時，所需移動的元素次數(shù)的平均次數(shù)為：,（8）刪除 線性表的刪除是指將第i（1i n）個元素刪除，使長度為n的線性表 ( a 1 , a 2 , . , a i-1 , a i , a i+1 , . , a n ) 變成長度為n-1的線性表 ( a 1 , a 2 , . , a i-1 , a i+1 , . , a n ) 數(shù)據(jù)元素a i-1 和 a i+1之間有了直接的邏輯關(guān)系。在順序表中，由于邏輯上相鄰的數(shù)據(jù)元素在物理上也是相鄰的，因此除非是刪除最后一個元素，否則必須將第i +1至第n共（n-i)個元素前移一個單元。,public

7、void remove( int k) int i=indexof (k); if (i！=-1) for (int j=i+1 ; jn ; j+) tablej-1=tablej; tablen-1=0; n-; else system.out.println(“不存在被刪除元素”); ,for (int j=i ; jn-1 ; j+) tablej=tablej+1;,設(shè)Qi是刪除第i個元素的概率，則在長度為n的線性表中刪除一個元素時，所需移動的元素次數(shù)的平均值為：,分析結(jié)論：順序存儲結(jié)構(gòu)表示的線性表，在做插入或刪除操作時，平均需要移動大約一半的數(shù)據(jù)元素。當(dāng)線性表的數(shù)據(jù)元素量較大，并且

8、經(jīng)常要對其做插入或刪除操作時，這一點(diǎn)需要值得考慮。,一、單鏈表 結(jié)點(diǎn)中只含一個指針域的鏈表叫單鏈表。 特點(diǎn)： 1、用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素 2、利用指針實(shí)現(xiàn)了用不相鄰的存儲單元存放邏輯上相鄰的元素 3、每個數(shù)據(jù)元素ai，除存儲本身信息外，還需存儲其直接后繼的信息 數(shù)據(jù)域：元素本身信息 指針域：指示直接后繼的存儲位置,2.2 線性鏈表,head,a1,a2,an ,.,1、單鏈表的結(jié)點(diǎn)類定義 package ds_java； public class onelinkNode public int data； public onelinkNode next； public onel

9、inkNode（int k） data=k；next=null； public onelinkNode（ ） this（0）； ,說明： 1、onelinkNode 類聲明了單鏈表的結(jié)點(diǎn)結(jié)構(gòu)，一個該類的對象是單鏈表中的一個結(jié)點(diǎn)。通過next 實(shí)現(xiàn)各元素間的邏輯關(guān)系。 2、onelinkNode類中的成員被定義為共有的，將onelinkNode類編譯后放在ds_java包中，以供其他類引用。,無參數(shù)時構(gòu)造值為零的結(jié)點(diǎn),2、單鏈表類定義 package ds_java； import ds_java onelinkNode； public class onelink1 protected onel

10、inkNode head； ,Onelink1類的對象表示一個單鏈表, head為鏈表的頭指針,指向鏈表的第一個結(jié)點(diǎn),當(dāng)head=null時,表示該鏈表為空,元素個數(shù)為0。,3、單鏈表的操作 （1）初始化-構(gòu)造一個空鏈表 public Onelink1（） head=null； public Onelink1（onelinkNode h1） head=h1； ,（2）判斷鏈表是否為空 public boolean isEmpty（） return head=null； ,（3）建立單鏈表-采用從表頭到表尾順序建立 public Onelink1( int n ) OnelinkNode rea

11、r，q; if（n0) int k=(int)(math.random( )*100); head=new OnelinkNode(k); rear=head; for(int i=1;in;i+) k=(int)(math.random( )*100); q=new OnelinkNode(k); rear.next=q; rear=q; ,(4)返回鏈表長度 public int length( ) int n=0; OnelinkNode p=head; while(p!=null) n+;p=p.next; return n; ,(5)輸出鏈表中的元素 public void outp

12、ut(OnelinkNode p) system.out.print(this.getClass( ).getName( )+”: “); while(p!=null) system.out.print(p.data); p=p.next; if(p!=null) system.out.print(“-”); system.out.println(); ,public void output( ) this.output(head); ,(6)插入 第一種:插入前為空鏈表,插入后鏈表中僅有一個結(jié)點(diǎn)。 head=new OnelinkNode(1); 第二種:鏈表非空,在head前插入一個結(jié)點(diǎn)q

13、。 q=new OnelinkNode(2); q.next=head ; head=q; 第三種:鏈表非空,在p指向的最后一個結(jié)點(diǎn)后插入q。 q=new OnelinkNode(3); p.next=q; 第四種:在非空鏈表中,在p(不是最后一個結(jié)點(diǎn))指向的結(jié)點(diǎn)后插入q。 q=new OnelinkNode(4); q.next=p.next; p.next=q;,例2.1 在單鏈表中插入如一個結(jié)點(diǎn)，插入前鏈表中的結(jié)點(diǎn)已根據(jù)其元素值有序，插入后仍然保持有序。 public void insert( int k) OnelinkNode p=null,q=null,t; t=new Oneli

14、nkNode(k); if(head=null) head=t; else if(kq.data) p=q;q=q.next; t.next=q;p.next=t; ,(7)刪除 第一種:刪除前鏈表中只有一個結(jié)點(diǎn)。 head=null; 第二種:鏈表有一個以上結(jié)點(diǎn),刪除第一個結(jié)點(diǎn)。 head=head.next; 第三種:鏈表非空,刪除p指向結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)。 p.next=p.next.next;,例2.2 從單鏈表中刪除關(guān)鍵字為k的結(jié)點(diǎn) public void delete( int k) OnelinkNode p=head , q=null ; if (p) if ( p.data=

15、k) head=head.next; else while(p ,4、兩種存儲結(jié)構(gòu)性能比較 本章介紹了線性表的邏輯結(jié)構(gòu)及它的兩種存儲結(jié)構(gòu)：順序表和鏈表。順序存儲有三個優(yōu)點(diǎn)： (1) 方法簡單，各種高級語言中都有數(shù)組，容易實(shí)現(xiàn)。 (2) 不用為表示結(jié)點(diǎn)間的邏輯關(guān)系而增加額外的存儲開銷。 (3) 順序表具有按元素序號隨機(jī)訪問的特點(diǎn)。 但它也有兩個缺點(diǎn)： 在順序表中做插入刪除操作時，平均移動大約表中一半的元素，因此對n較大的順序表效率低。 需要預(yù)先分配足夠大的存儲空間，估計(jì)過大，可能會導(dǎo)致順序表后部大量閑置；預(yù)先分配過小，又會造成溢出。 鏈表的優(yōu)缺點(diǎn)恰好與順序表相反。,在實(shí)際中怎樣選取存儲結(jié)構(gòu)呢？通

16、常有以下幾點(diǎn)考慮： 基于存儲的考慮 對線性表的長度或存儲規(guī)模難以估計(jì)時，不宜采用順序表；鏈表不用事先估計(jì)存儲規(guī)模，但鏈表的存儲密度較低。 基于運(yùn)算的考慮 如果經(jīng)常做的運(yùn)算是按序號訪問數(shù)據(jù)元素，順序表優(yōu)于鏈表； 在順序表中做插入、刪除操作時平均移動表中一半的元素，在鏈表中作插入、刪除操作，雖然也要找插入位置，但操作主要是比較操作，從這個角度考慮后者優(yōu)于前者。 基于環(huán)境的考慮 順序表容易實(shí)現(xiàn)，任何高級語言中都有數(shù)組類型，鏈表的操作是基于指針的，相對來講前者簡單些，也是用戶考慮的一個因素。 總之，兩種存儲結(jié)構(gòu)各有長短，選擇那一種由實(shí)際問題中的主要因素決定。通?！拜^穩(wěn)定”的線性表選擇順序存儲，而頻繁做

17、插入刪除的即動態(tài)性較強(qiáng)的線性表宜選擇鏈?zhǔn)酱鎯Α?h,二、單循環(huán)鏈表 單循環(huán)鏈表是表中最后一個結(jié)點(diǎn)的指針指向第一個結(jié)點(diǎn)。 特點(diǎn)：從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其他結(jié)點(diǎn)，提高查找效率。操作與單鏈表基本一致,循環(huán)條件不同。,非空鏈表,長度為1的鏈表,空鏈表 Head= null,三、雙向鏈表（double linked list）,1、雙鏈表的結(jié)點(diǎn)類定義 package ds_java； public class TwolinkNode public int data； public TwolinkNode prior ,next； public TwolinkNode（int k） data=k；

18、 prior=next=null； public TwolinkNode（ ） this（0）； ,2、雙鏈表類定義 package ds_java； import ds_java TwolinkNode； public class Twolink1 protected TwolinkNode head； public Twolink1( ) head=null； ,L,L,A,B,p.prior.next= p= ir;,空雙向循環(huán)鏈表：,非空雙向循環(huán)鏈表：,刪除,p.prior.next=p.next;,p.next.prior=p.prior;,s=new Twoli

19、nkNode(x); s.prior=p.prior; p.prior.next=s; s.next=p; p.prior=s;,插入,b,a,串的邏輯結(jié)構(gòu)和線性表極為相似，區(qū)別僅在于串的數(shù)據(jù)對象約束為字符集。然而，串的基本操作和線性表有很大差別。在線性表的基本操作中，大多以“單個元素”作為操作對象，如：在線性表中查找某個元素、求取某個元素、在某個位置上插入一個元素和刪除一個元素等；而在串的基本操作中，通常以“串的整體”作為操作對象，如：在串中查找某個子串、求取一個子串、在串的某個位置上插入一個子串以及刪除一個子串等。,2.3 串,一、串類型的定義,串是字符串的簡稱。它是一種在數(shù)據(jù)元素的組成上

20、具有一定約束條件的線性表，即要求組成線性表的所有數(shù)據(jù)元素都是字符，所以，人們經(jīng)常又這樣定義串：串是一個有窮字符序列。串一般記作： s= “a1a2.an” (n0) 其中，s是串的名稱，用雙引號（“”）括起來的字符序列是串的值；ai可以是字母、數(shù)字或其他字符；串中字符的數(shù)目n被稱作串的長度。 當(dāng)n=0時，串中沒有任何字符，其串的長度為0，通常被稱為空串。 s1= “”,s2= “ ” s1中沒有字符，是一個空串；而s2中有兩個空格字符，它的長度等于2，它是由空格字符組成的串，一般稱此為空格串。 子串、主串：串中任意連續(xù)的字符組成的子序列被稱為該串的子串。包含子串的串又被稱為該子串的主串。 例如

21、，有下列四個串a(chǎn)，b，c，d： a= “Welcome to Beijing” b= “Welcome” c= “Bei” d= “welcome to” b，c，d都是a的子串。 子串的位置：子串在主串中第一次出現(xiàn)的第一個字符的位置。,兩個串相等：兩個串的長度相等，并且各個對應(yīng)的字符也都相同。 例如，有下列四個串a(chǎn)，b，c，d： a= “program” b= “Program” c= “pro” d= “program ”,相等,不等,二、串的表示和實(shí)現(xiàn) 如果在程序設(shè)計(jì)語言中，串只是作為輸入或輸出的常量出現(xiàn)，則只需存儲此串的串值，即字符序列即可。但在多數(shù)非數(shù)值處理的程序中，串也以變量的形式

22、出現(xiàn)。串有3種機(jī)內(nèi)表示方法。 1、串的順序存儲表示,public class String1 private char table ； private int number=0； public String1( ) table= new char80; number=0; ,2、基本操作 （1）創(chuàng)建一個串 public String1( int n) table=new charn; number=0; ,構(gòu)造有n個單元的空串,public String1( ) this(10); ,構(gòu)造有10個單元的空串,構(gòu)造有1個字符的串,public String1(char c ) this( );

23、table0=c; number=1; ,public String1(char c ) this(c.length); System.arraycopy(c,0,table,0,c.length); number=c.length; ,復(fù)制數(shù)組,(2)length1( )方法返回串的長度 public int length1( ) return number; ,(3)串的聯(lián)接 方法concat public void concat(char c) this.tablenumber=c; number+; ,public void concat(String1 s2) for( int i=

24、0 ;is2.length1( );i+) this.concat(s2.tablei); ,( 4 )求子串substring方法 public String1 subString( int i , int n) /i=1,( 4 )求子串substring方法 public String1 subString( int i , int n) /i=1 ,（5）定位函數(shù)-查找子串方法indexof( ) public int indexof(String1 sub) int i=0 , j ; boolean yes=false; while(i+sub.length1( )=sub.len

25、gth1( ) yes=true; else i+; if ( yes )return i+1; else return 0; ,(6)插入 public String1 insert( int i , String1 s2) String1 sub1,sub2; sub1=this.subString(1,i-1); sub2=this.subString(i,this.length1( )-i+1); String1 news1=new String1( ); news1.cocat(sub1); news1.cocat(s2); news1.cocat(sub2); return new

26、s1; ,(7)刪除 public String1 delete( int i , int n) String1 sub1,sub2,sub3; sub1=this.subString(1,i-1); sub2=this.subString(i,n); sub3=this.subString(i+n,this.length1( )-i-n+1); String1 news1=new String1( ); news1.cocat(sub1); news1.cocat(sub3); return news1; ,剩余的字符個數(shù),3、串的鏈?zhǔn)酱鎯Ρ硎炯盎静僮鲗?shí)現(xiàn),由于串結(jié)構(gòu)中每個數(shù)據(jù)元素為一個字

27、符，所以最直接的鏈?zhǔn)酱鎯Y(jié)構(gòu)是每個結(jié)點(diǎn)的數(shù)據(jù)域存放一個字符。 優(yōu)點(diǎn)是操作方便；不足之處是存儲密度較低。所謂存儲密度為： 存儲密度= ,若要將多個字符存放在一個結(jié)點(diǎn)中，就可以緩解這個問題。,串值所占的存儲單元,實(shí)際分配的存儲單元,s,t,r,i,n,g ,head,(1)串的鏈?zhǔn)酱鎯Y(jié)構(gòu)的結(jié)點(diǎn)類定義 package ds_java； public class StringNode public char data； public StringNode next； public StringNode （char k） data=c；next=null； public StringNode （ ）

28、this（?）； ,(2)串的類定義 import ds_java StringNode ； public class String2 private StringNode head,rear； private int number=0; ,(3)創(chuàng)建一個串 public String2( ) head=rear=null; number=0; (4)返回串的長度 public int length2( ) return number; ,(5)concat( ) public void concat( char c) StringNode p,q; if(this.head=null) th

29、is.rear=this.head=new StringNode(c); else q=new StringNode(c); this.rear.next=q; this.rear=q; number+; ,public void concat( String2 s2) StringNode q=s2.head; whlie(q!=null) this.concat(q.data); q=q.next; ,練習(xí)題,1、線性表的順序存儲結(jié)構(gòu)是一種( )的存儲結(jié)構(gòu)。 A隨機(jī)存取 B順序存取 C索引存取 DHASH存取 2、在下面的幾個敘述中，正確的是( ) 。 A順序存儲方式只能用于存儲線性結(jié)構(gòu)。

30、 B順序存儲方式的優(yōu)點(diǎn)是存儲密度大，且插入、刪除運(yùn)算方便、效率高。 C鏈?zhǔn)浇Y(jié)構(gòu)屬于動態(tài)結(jié)構(gòu)，順序存儲結(jié)構(gòu)必為靜態(tài)結(jié)構(gòu)。 D在鏈表中，邏輯上相鄰的兩個元素在物理上不一定相鄰。,3、L為具有頭結(jié)點(diǎn)的單鏈表的頭指針，執(zhí)行下列程序段后與原單鏈表比較后發(fā)現(xiàn)( )。 if( (L-next!=NULL) A原表的頭結(jié)點(diǎn)成了新表的尾結(jié)點(diǎn) B原表的首元結(jié)點(diǎn)成了新表的尾結(jié)點(diǎn) C原表的第二個元素結(jié)點(diǎn)成了新表的尾結(jié)點(diǎn) D原表的尾結(jié)點(diǎn)成了新表的首元結(jié)點(diǎn),4、在一個單鏈表中，若P結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在P之后插入S結(jié)點(diǎn)，則執(zhí)行( )。 Asnext=p；pnext=s； Bsnext=pnext； pnext=s; Csn

31、ext=pnext；p=s； Dpnext=s；snext=p； 5、對長度為n順序線性表進(jìn)行插入元素的操作，如果在每一個元素之前插入一個元素概率相同，則插入一個元素移動元素的平均次數(shù)為（ ）。 An /2 B（n 1）/2 C（n +1）/2 Dn 6、一維數(shù)組與線性表的區(qū)別是（ ）。 A前者長度固定，后者長度可變 B后者長度固定，前者長度可變 C兩者長度均固定 D兩者長度均可變,7、用鏈表表示線性表的優(yōu)點(diǎn)是（ ）。 A便于隨機(jī)存取 B便于插入和刪除 C花費(fèi)的存儲空間較順序存儲少 D元素的物理順序與邏輯順序相同 8、在一帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，p指向尾結(jié)點(diǎn)的直接前驅(qū)，則指向頭結(jié)點(diǎn)的指針head可用p表示為head=（