第二章 线性表.ppt

1、第二章 线性表,2.1 顺序表 2.2 线性链表 2.3 串,线性表是由n个类型相同的数据元素组成的有限序列。通常表示成下列形式： LinearList= a 1 , a 2 , . , a i-1 , a i , a i+1 , . , a n 例： 1、英文字母表（A,B,C,.Z) 2、一个星期的七天（星期一，星期二，星期天） 3、一年的12月（一月，二月，12月）,线性表的顺序存储结构是指用一组连续的存储单元按元素间的逻辑关系依次存储线性表中的每个数据元素。通常称这种存储结构的线性表为顺序表。 元素地址计算方法： 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,存储地址,存储内容,顺序存储结构,位序,2,1,i,n,1、顺序表的类定义 由于高级语言程序设计中的数组也有随机存取的特性，因此，通常都用数组来描述数据结构中的顺序存储结构。 public class LinearList1 private int table ； private int n； ,2、顺序表的操作 （1）初始化 使用构造方法创建表对象，为顺序表分配存储空间，设置顺序表为空状态。 public LinearList1（int n） table=new

3、 int n; this.n=0; ,(2)判断空与满的状态 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）设置顺序表的第i个数据元素值 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）个元素之前插入一个新的数据元素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 ) 数据元素a i-1 和 a i 之间的逻辑关

5、系发生了变化。在顺序表中，由于逻辑上相邻的数据元素在物理上也是相邻的，因此除非是在最后一个元素后插入，否则必须将第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(“数组已满,无法插入”); ,public void insert(int i,int k) insert(n+1,k); ,设Pi是在第i个元素之前

6、插入一个元素的概率，则在长度为n的线性表中插入一个元素时，所需移动的元素次数的平均次数为：,（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 ) 数据元素a i-1 和 a i+1之间有了直接的逻辑关系。在顺序表中，由于逻辑上相邻的数据元素在物理上也是相邻的，因此除非是删除最后一个元素，否则必须将第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;,设Qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素时，所需移动的元素次数的平均值为：,分析结论：顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且

8、经常要对其做插入或删除操作时，这一点需要值得考虑。,一、单链表 结点中只含一个指针域的链表叫单链表。 特点： 1、用一组任意的存储单元存储线性表的数据元素 2、利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素 3、每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息 数据域：元素本身信息 指针域：指示直接后继的存储位置,2.2 线性链表,head,a1,a2,an ,.,1、单链表的结点类定义 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 类声明了单链表的结点结构，一个该类的对象是单链表中的一个结点。通过next 实现各元素间的逻辑关系。 2、onelinkNode类中的成员被定义为共有的，将onelinkNode类编译后放在ds_java包中，以供其他类引用。,无参数时构造值为零的结点,2、单链表类定义 package ds_java； import ds_java onelinkNode； public class onelink1 protected onel

10、inkNode head； ,Onelink1类的对象表示一个单链表, head为链表的头指针,指向链表的第一个结点,当head=null时,表示该链表为空,元素个数为0。,3、单链表的操作 （1）初始化-构造一个空链表 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)插入 第一种:插入前为空链表,插入后链表中仅有一个结点。 head=new OnelinkNode(1); 第二种:链表非空,在head前插入一个结点q

13、。 q=new OnelinkNode(2); q.next=head ; head=q; 第三种:链表非空,在p指向的最后一个结点后插入q。 q=new OnelinkNode(3); p.next=q; 第四种:在非空链表中,在p(不是最后一个结点)指向的结点后插入q。 q=new OnelinkNode(4); q.next=p.next; p.next=q;,例2.1 在单链表中插入如一个结点，插入前链表中的结点已根据其元素值有序，插入后仍然保持有序。 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)删除 第一种:删除前链表中只有一个结点。 head=null; 第二种:链表有一个以上结点,删除第一个结点。 head=head.next; 第三种:链表非空,删除p指向结点的直接后继结点。 p.next=p.next.next;,例2.2 从单链表中删除关键字为k的结点 public void delete( int k) OnelinkNode p=head , q=null ; if (p) if ( p.data=

15、k) head=head.next; else while(p ,4、两种存储结构性能比较 本章介绍了线性表的逻辑结构及它的两种存储结构：顺序表和链表。顺序存储有三个优点： (1) 方法简单，各种高级语言中都有数组，容易实现。 (2) 不用为表示结点间的逻辑关系而增加额外的存储开销。 (3) 顺序表具有按元素序号随机访问的特点。 但它也有两个缺点： 在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此对n较大的顺序表效率低。 需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。 链表的优缺点恰好与顺序表相反。,在实际中怎样选取存储结构呢？通

16、常有以下几点考虑： 基于存储的考虑 对线性表的长度或存储规模难以估计时，不宜采用顺序表；链表不用事先估计存储规模，但链表的存储密度较低。 基于运算的考虑 如果经常做的运算是按序号访问数据元素，顺序表优于链表； 在顺序表中做插入、删除操作时平均移动表中一半的元素，在链表中作插入、删除操作，虽然也要找插入位置，但操作主要是比较操作，从这个角度考虑后者优于前者。 基于环境的考虑 顺序表容易实现，任何高级语言中都有数组类型，链表的操作是基于指针的，相对来讲前者简单些，也是用户考虑的一个因素。 总之，两种存储结构各有长短，选择那一种由实际问题中的主要因素决定。通常“较稳定”的线性表选择顺序存储，而频繁做

17、插入删除的即动态性较强的线性表宜选择链式存储。,h,二、单循环链表 单循环链表是表中最后一个结点的指针指向第一个结点。 特点：从表中任一结点出发均可找到表中其他结点，提高查找效率。操作与单链表基本一致,循环条件不同。,非空链表,长度为1的链表,空链表 Head= null,三、双向链表（double linked list）,1、双链表的结点类定义 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;,空双向循环链表：,非空双向循环链表：,删除,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,串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。然而，串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以“单个元素”作为操作对象，如：在线性表中查找某个元素、求取某个元素、在某个位置上插入一个元素和删除一个元素等；而在串的基本操作中，通常以“串的整体”作为操作对象，如：在串中查找某个子串、求取一个子串、在串的某个位置上插入一个子串以及删除一个子串等。,2.3 串,一、串类型的定义,串是字符串的简称。它是一种在数据元素的组成上

20、具有一定约束条件的线性表，即要求组成线性表的所有数据元素都是字符，所以，人们经常又这样定义串：串是一个有穷字符序列。串一般记作： s= “a1a2.an” (n0) 其中，s是串的名称，用双引号（“”）括起来的字符序列是串的值；ai可以是字母、数字或其他字符；串中字符的数目n被称作串的长度。 当n=0时，串中没有任何字符，其串的长度为0，通常被称为空串。 s1= “”,s2= “ ” s1中没有字符，是一个空串；而s2中有两个空格字符，它的长度等于2，它是由空格字符组成的串，一般称此为空格串。 子串、主串：串中任意连续的字符组成的子序列被称为该串的子串。包含子串的串又被称为该子串的主串。 例如

21、，有下列四个串a，b，c，d： a= “Welcome to Beijing” b= “Welcome” c= “Bei” d= “welcome to” b，c，d都是a的子串。 子串的位置：子串在主串中第一次出现的第一个字符的位置。,两个串相等：两个串的长度相等，并且各个对应的字符也都相同。 例如，有下列四个串a，b，c，d： a= “program” b= “Program” c= “pro” d= “program ”,相等,不等,二、串的表示和实现 如果在程序设计语言中，串只是作为输入或输出的常量出现，则只需存储此串的串值，即字符序列即可。但在多数非数值处理的程序中，串也以变量的形式

22、出现。串有3种机内表示方法。 1、串的顺序存储表示,public class String1 private char table ； private int number=0； public String1( ) table= new char80; number=0; ,2、基本操作 （1）创建一个串 public String1( int n) table=new charn; number=0; ,构造有n个单元的空串,public String1( ) this(10); ,构造有10个单元的空串,构造有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; ,复制数组,(2)length1( )方法返回串的长度 public int length1( ) return number; ,(3)串的联接 方法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）定位函数-查找子串方法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; ,剩余的字符个数,3、串的链式存储表示及基本操作实现,由于串结构中每个数据元素为一个字

27、符，所以最直接的链式存储结构是每个结点的数据域存放一个字符。 优点是操作方便；不足之处是存储密度较低。所谓存储密度为： 存储密度= ,若要将多个字符存放在一个结点中，就可以缓解这个问题。,串值所占的存储单元,实际分配的存储单元,s,t,r,i,n,g ,head,(1)串的链式存储结构的结点类定义 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)创建一个串 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; ,练习题,1、线性表的顺序存储结构是一种( )的存储结构。 A随机存取 B顺序存取 C索引存取 DHASH存取 2、在下面的几个叙述中，正确的是( ) 。 A顺序存储方式只能用于存储线性结构。

30、 B顺序存储方式的优点是存储密度大，且插入、删除运算方便、效率高。 C链式结构属于动态结构，顺序存储结构必为静态结构。 D在链表中，逻辑上相邻的两个元素在物理上不一定相邻。,3、L为具有头结点的单链表的头指针，执行下列程序段后与原单链表比较后发现( )。 if( (L-next!=NULL) A原表的头结点成了新表的尾结点 B原表的首元结点成了新表的尾结点 C原表的第二个元素结点成了新表的尾结点 D原表的尾结点成了新表的首元结点,4、在一个单链表中，若P结点不是最后结点，在P之后插入S结点，则执行( )。 Asnext=p；pnext=s； Bsnext=pnext； pnext=s; Csn

31、ext=pnext；p=s； Dpnext=s；snext=p； 5、对长度为n顺序线性表进行插入元素的操作，如果在每一个元素之前插入一个元素概率相同，则插入一个元素移动元素的平均次数为（ ）。 An /2 B（n 1）/2 C（n +1）/2 Dn 6、一维数组与线性表的区别是（ ）。 A前者长度固定，后者长度可变 B后者长度固定，前者长度可变 C两者长度均固定 D两者长度均可变,7、用链表表示线性表的优点是（ ）。 A便于随机存取 B便于插入和删除 C花费的存储空间较顺序存储少 D元素的物理顺序与逻辑顺序相同 8、在一带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head=（