數(shù)據(jù)結(jié)構(gòu)主講人：張靜常州信息職業(yè)技術(shù)學(xué)院2.2線性表的順序存儲(chǔ)結(jié)構(gòu)順序表Part01順序表

使用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的各個(gè)數(shù)據(jù)元素，該結(jié)構(gòu)稱作線性表的順序存儲(chǔ)結(jié)構(gòu)，簡稱為順序表（SequentialList）。順序表的定義順序表中數(shù)據(jù)元素存儲(chǔ)地址的計(jì)算順序表Part02順序表的基本操作1．順序表類聲明、構(gòu)造方法、存取操作實(shí)現(xiàn)順序表的基本操作聲明構(gòu)造方法publicSeqList(int

length){//構(gòu)造容量為length的空表

this.data=newT[length];//創(chuàng)建長度為length的數(shù)組，元素均為null

this.n=0;//空表長度為0}publicSeqList(T[]values){//由values數(shù)組構(gòu)造順序表this(values.length);//創(chuàng)建容量為values.length的空表for(int

i=0;i<values.length;i++){//復(fù)制數(shù)組元素

this.data[i]=values[i];//對(duì)象引用賦值}this.n=values.length;//順序表長度為數(shù)組values的長度} publicSeqList(){//創(chuàng)建默認(rèn)容量為10的空表

this(10);//構(gòu)造方法重載，調(diào)用本類已聲明的指定參數(shù)列表的構(gòu)造方法}1．順序表類聲明、構(gòu)造方法、存取操作實(shí)現(xiàn)順序表的基本操作獲取值設(shè)置值

2．求表長、清空、判斷表空順序表的基本操作求表長清空判斷表空3．遍歷順序表順序表的基本操作時(shí)間復(fù)雜度：O(n)public

voidprintList(){//遍歷順序表所有元素for(int

i=0;i<this.n;i++){System.out.println(this.data[i]);} }4．順序表的查找順序表的基本操作（1）查找算法//在順序表查找首次出現(xiàn)的與key相等元素，返回元素位置//若不存在返回-1public

intindexOf(Tkey){for(int

i=0;i<this.n;i++){if(key.equals(this.data[i])){

return

i;}}return-1;}（2）判斷是否包含某元素算法//判斷順序表中是否包含key元素public

booleancontains(Tkey){for(int

i=0;i<this.n;i++){if(key.equals(this.data[i])){

return

true;}}return

false;}時(shí)間復(fù)雜度：O(n)5．順序表的插入順序表的基本操作在ai位置插入40125439…a0a1a2…aiai+1…an-2an-15774…892840若插入位置不合理，拋出下標(biāo)越界異常：下標(biāo)范圍為0~n-1，允許直接在表尾后添加元素，因此合理的插入位置為0~n；如果順序表的長度大于等于數(shù)組長度，則動(dòng)態(tài)擴(kuò)容；從最后一個(gè)元素開始向前遍歷到下標(biāo)i處，依次將它們后移1位；將要插入的元素填入下標(biāo)i處；表長加1。5．順序表的插入順序表的基本操作public

intinsert(int

i,Tt){//在順序表的位置i處插入元素t,返回t序號(hào)if(t==null)throw

newNullPointerException("t==null");//拋出空對(duì)象異常if(i>=0&&i<=this.n){Tsrc[]=this.data;//保存原數(shù)組if(this.n==data.length){//若數(shù)組滿，則擴(kuò)充順序表的數(shù)組容量

this.data=newT[src.length*2];//重新申請(qǐng)一個(gè)容量為原來2倍的數(shù)組

for(int

j=0;j<i;j++){

this.data[j]=src[j];//復(fù)制當(dāng)前數(shù)組前i個(gè)元素} }

for(int

j=this.n-1;j>=i;j--){//從最后一個(gè)位置開始到位置i處，每一個(gè)元素向后移動(dòng)1位

this.data[j+1]=src[j];}

this.data[i]=t;//把要插入的元素t存放在位置i處

this.n++;

return

i;//返回下標(biāo)}else{

throw

newIndexOutOfBoundsException(i+"下標(biāo)越界");//拋出下標(biāo)越界異常} }

時(shí)間復(fù)雜度：O(n)6．順序表的刪除順序表的基本操作刪除ai位置上的元素74125439…a0a1a2…aiai+1…an-2an-15774…8928若是空表，拋出異常；若刪除位置不合理，拋出下標(biāo)越界異常；從刪除元素位置開始遍歷到最后一個(gè)元素位置，依次將它們向前移動(dòng)1位；表長減1。6．順序表的刪除順序表的基本操作

時(shí)間復(fù)雜度：O(n)publicTremove(int

i){if(this.n==0){try{

throw

newException("空表無法刪除！");}catch(Exceptione){

e.printStackTrace();}}

if(i>=0&&i<this.n){Told=this.data[i];//old中存放被刪除元素

for(int

j=i;j<this.n-1;j++){

this.data[j]=this.data[j+1];//從位置i+1開始每個(gè)元素依次前移一位}

this.data[this.n-1]=null;//設(shè)置最后一個(gè)位置元素為空

this.n--;

return

old;}else{

throw

newIndexOutOfBoundsException(i+"下標(biāo)越界");

//拋出下標(biāo)越界異常} }順序表結(jié)構(gòu)簡單，便于隨機(jī)訪問表中的任一元素，但在順序表中進(jìn)行插入、刪除操作時(shí)，平均移動(dòng)次數(shù)大約為n/2（n為表中元素個(gè)數(shù)），當(dāng)n較大時(shí)，順序表的插入、刪除操作執(zhí)行效率低。同時(shí)，通常用數(shù)組實(shí)現(xiàn)的