数据基础教程29

第2章线性表2.1线性表的定义2.3线性表的链式存储结构2.2线性表的顺序存储结构2.4顺序表和链表的比较CONTENTS提纲2.5线性表的应用1/582.1线性表的定义2.1.1什么是线性表线性表是具有相同特性的数据元素的一个有限序列。所有数据元素类型相同。线性表是有限个数据元素构成的。线性表中数据元素与位置相关，即每个数据元素有唯一的序号。2/58线性表的逻辑结构表示（a0，a1，…，ai，ai+1，…，an-1）用图形表示的逻辑结构：a0a1aiai+1an-1……线性表中每个元素ai的唯一位置通过序号或者索引i表示，为了算法设计方便，将逻辑序号和存储序号统一，均假设从0开始，这样含n个元素的线性表的元素序号i满足0≤i≤n-1。说明3/582.1.2线性表的抽象数据类型描述ADTList{

数据对象：

D={ai|0≤i≤n-1，n≥0，ai为E类型}//E是用户指定的类型

数据关系：

r={<ai，ai+1>|ai，ai+1∈D，i=0，…，n-2}

基本运算（11个）： voidCreateList(E[]a)：由a数组建立线性表的相应存储结构。 voidAdd(Ee)：将元素e添加到线性表末尾。 intsize()：求线性表的长度。 voidSetsize(intnlen)：设置线性表的长度为nlen。 EGetElem(inti)：求线性表中序号为i的元素。 voidSetElem(inti，Ee)：设置线性表中序号i的元素为e。 intGetNo(Ee)：求线性表中第一个值为e的元素的序号。

voidswap(inti，intj)：交换线性表中序号i和序号j的元素。 voidInsert(inti，Ee)：在线性表中插入数据元素e作为第i个元素。 voidDelete(inti)：在线性表中删除第i个数据元素。 StringtoString()：将线性表转换为字符串。}4/582.2线性表的顺序存储结构2.2.1线性表的顺序存储结构—顺序表长度为n的线性表存放在顺序表中a0a1…ai-1ai…an-1…data数组数组下标01…i-1i…n-1capacity-15/58data数组存放线性表元素data数组的容量（存放最多的元素个数）为capacity。线性表中实际数据元素个数sizepublicclassSqListClass<E>{ //顺序表泛型类finalintinitcapacity=10; //顺序表的初始容量(常量)publicE[]data; //存放顺序表中元素publicintsize; //存放顺序表的长度privateintcapacity; //存放顺序表的容量publicSqListClass(){ //构造方法，实现data和length的初始化data=(E[])newObject[initcapacity];//强制转换为E类型数组capacity=initcapacity;size=0;}

//线性表的基本运算算法}6/582.2.2线性表基本运算算法在顺序表中的实现

在动态分配顺序表的空间时，初始容量设置为initcapacity，当添加或者插入元素可能需要扩大容量，在删除元素时可能需要减少容量。privatevoidupdatecapacity(intnewcapacity){//改变顺序表的容量为newcapacityE[]newdata=(E[])newObject[newcapacity];for(inti=0;i<size;i++) //复制原来的元素newdata[i]=data[i];capacity=newcapacity; //设置新容量data=newdata; //仍由data标识数组}7/581.整体建立顺序表publicvoidCreateList(E[]a){ //由a整体建立顺序表 size=0; for(inti=0;i<a.length;i++){ if(size==capacity) //出现上溢出时

updatecapacity(2*size); //扩大容量 data[size]=a[i]; size++; //添加的元素个数增加1 }}

由含若干个元素的数组a的全部元素整体创建顺序表，即依次将a中的元素添加到data数组的末尾，当出现上溢出时按实际元素个数size的两倍扩大容量。8/582.顺序表基本运算算法（1）将元素e添加到线性表末尾Add(e)publicvoidAdd(Ee){ //在线性表的末尾添加一个元素eif(size==capacity) //顺序表空间满时倍增容量updatecapacity(2*size);data[size]=e;size++; //长度增1}时间复杂度是多少？9/58publicintsize(){ //求线性表长度returnsize;}（2）求线性表的长度size()10/58publicvoidSetsize(intnlen){ //设置线性表的长度if(nlen<0||nlen>size)thrownewIllegalArgumentException("设置长度:n不在有效范围内");size=nlen;}（3）设置线性表的长度Setsize(nlen)

用于缩小线性表的长度，当参数nlen正确时（0≤nlen≤size-1）置长度size为nlen，否则抛出相应的异常。11/58publicEGetElem(inti){ //返回线性表中序号为i的元素if(i<0||i>size-1)thrownewIllegalArgumentException("查找:位置i不在有效范围内");return(E)data[i];}（4）求线性表中序号为i的元素GetElem(i)12/58publicvoidSetElem(inti,Ee){ //设置序号i的元素为eif(i<0||i>size-1)thrownewIllegalArgumentException("设置:位置i不在有效范围内");data[i]=e;}（5）设置线性表中序号为i的元素SetElem(i，e)13/58publicintGetNo(Ee){ //查找第一个为e的元素的序号inti=0;while(i<size&&!data[i].equals(e))i++; //查找元素eif(i>=size) //未找到时返回-1return-1;elsereturni; //找到后返回其序号}（6）求线性表中第一个值为e的元素的逻辑序号GetNo(e)14/58publicvoidswap(inti,intj){ //交换data[i]和data[j]Etmp=data[i];data[i]=data[j];data[j]=tmp;}（7）交换线性表中序号i和序号j的元素swap(i,j)15/58publicvoidInsert(inti,Ee){ //在线性表中序号i位置插入元素eif(i<0||i>size) //参数错误抛出异常thrownewIllegalArgumentException("插入:位置i不在有效范围内");if(size==capacity) //满时倍增容量updatecapacity(2*size);for(intj=size;j>i;j--) //data[i]及后面元素后移一个位置data[j]=data[j-1];data[i]=e; //插入元素esize++; //顺序表长度增1}（8）在线性表中插入e作为第i个元素Insert(i，e)a0a1…aiai+1…an-1…从an-1元素开始移动起16/58调用updatecapacity多少次？17/58publicvoidInsert(inti,Ee){ //在线性表中序号i位置插入元素eif(i<0||i>size) //参数错误抛出异常thrownewIllegalArgumentException("插入:位置i不在有效范围内");if(size==capacity) //满时倍增容量updatecapacity(2*size);for(intj=size;j>i;j--) //data[i]及后面元素后移一个位置data[j]=data[j-1];data[i]=e; //插入元素esize++; //顺序表长度增1}

主要时间花在元素移动上。有效插入位置i的取值是0～n，共有n+1个位置可以插入元素：当i=0时，移动次数为n，达到最大值。当i=n时，移动次数为0，达到最小值。其他情况，需要移动data[i..n-1]的元素，移动次数为(n-1)-i+1=n-i。a0a1…aiai+1…an-1…所需移动元素的平均次数为：插入算法的平均时间复杂度为O(n)。18/58扩容运算updatecapacity()在size+1次插入中仅仅调用一次，其平摊时间为O(1)，上述算法时间分析中可以忽略它。说明19/58publicvoidDelete(inti){ //在线性表中删除序号i位置的元素if(i<0||i>size-1)//参数错误抛出异常thrownewIllegalArgumentException("删除:位置i不在有效范围内");for(intj=i;j<size-1;j++)//将data[i]之后的元素前移一个位置data[j]=data[j+1];size--; //顺序表长度减1

if(capacity>initcapacity&&size==capacity/4)updatecapacity(capacity/2);//满足要求容量减半}（9）在线性表中删除第i个数据元素Delete(i)a0a1…aiai+1…an-1…从ai+1元素开始移动起20/58调用updatecapacity多少次？21/58publicvoidDelete(inti){ //在线性表中删除序号i位置的元素if(i<0||i>size-1)//参数错误抛出异常thrownewIllegalArgumentException("删除:位置i不在有效范围内");for(intj=i;j<size-1;j++)//将data[i]之后的元素前移一个位置data[j]=data[j+1];size--; //顺序表长度减1

if(capacity>initcapacity&&size==capacity/4)updatecapacity(capacity/2);//满足要求容量减半}a0a1…aiai+1…an-1…

主要时间花在元素移动上。有效删除位置i的取值是0～n-1，共有n个位置可以删除元素：当i=0时，移动次数为n-1，达到最大值。当i=n-1时，移动次数为0，达到最小值。其他情况，需要移动data[i+1..n-1]的元素，移动次数为 (n-1)-(i+1)+1=n-i-1。所需移动元素的平均次数为：删除算法的平均时间复杂度为O(n)。22/58publicStringtoString(){ //将线性表转换为字符串Stringans="";for(inti=0;i<size;i++)ans+=data[i].toString()+"";returnans;}（10）将线性表转换为字符串toString()23/58@SuppressWarnings("unchecked")publicclasstmp{publicstaticvoidmain(String[]args){Integer[]a={1,2,3,4,5};SqListClass<Integer>L=newSqListClass<Integer>();L.CreateList(a);System.out.println("L:"+L);} }24/58线性表元素基本运算应用程序25/58clsjavac-encodingutf8%1.javajava%1（2）exe.bat批处理文件：（1）@SuppressWarnings("unchecked")实验程序说明26/582.2.3顺序表的应用算法设计示例1.基于顺序表基本操作的算法设计

【例2.1】对于含有n个整数元素的顺序表L，设计一个算法将其中所有元素逆置。

例如L=(1，2，3，4，5)，逆置后L=(5，4，3，2，1)。并给出算法的时间复杂度和空间复杂度。27/58a0…an-1交换ai…aj…ijpublicstaticvoidReverse(SqListClass<Integer>L){inti=0,j=L.size()-1;while(i<j){L.swap(i,j);i++;j--;}}将L所有元素逆置28/58

【例2.2】假设有一个整数顺序表L，所有元素值均不相同。设计一个算法将最大值元素与最小值元素交换。例如L=(1，2，3，4，5)，交换后L=(5，2，3，5，1)。publicstaticvoidSwapmaxmin(SqListClass<Integer>L){intmaxi,mini;

maxi=mini=0;for(inti=1;i<L.size();i++){if(L.GetElem(i)>L.GetElem(maxi))

maxi=i;elseif(L.GetElem(i)<L.GetElem(mini))mini=i;

}L.swap(maxi,mini);}29/58publicstaticbooleanDeletek1(SqListClass<Character>L,inti,intk){if(i<0||k<1||i+k<1||i+k>L.size())returnfalse; //i和k参数不合法时返回falsefor(intj=i;j<=i+k-1;j++)L.Delete(i);returntrue; //成功删除返回true}

【例2.3】假设有一个字符顺序表L，设计一个算法用于删除从序号i开始的k个元素，若成功删除返回true，否则返回false。

例如L=（'a'，'b'，'c'，'d'，'e'），删除i=1开始的k=2个元素后L=（'a'，'d'，'e'）。

解法1：在参数正确时，让j从i到i+k-1循环，每次循环调用Delete()基本运算删除i序号的元素。30/58publicstaticbooleanDeletek2(SqListClass<Character>L,inti,intk){if(i<0||k<1||i+k<1||i+k>L.size())returnfalse; //i和k参数不合法时返回falsefor(intj=i+k;j<L.size();j++) //将元素前移k个位置L.SetElem(j-k,L.GetElem(j));L.Setsize(L.size()-k); //长度减kreturntrue; //成功删除返回true}解法2：在参数正确时，直接将ai+k～an-1的所有元素依次前移k个位置。a0…aiai+1…an-1…均前移k个位置ai+k-1ai+k…删除k个元素两个算法的比较？31/582.基于整体建立顺序表的算法设计给定的顺序表L结果顺序表L1按要求插入如果两者可以共享，直接在L中操作产生结果顺序表32/58

【例2.4】对于含有n个整数元素的顺序表L，设计一个算法用于删除其中所有值为x的元素。

例如L=(1，2，1，5，1)，若x=1，删除后L=(2，5)。并给出算法的时间复杂度和空间复杂度。33/58publicstaticvoidDeletex1(SqListClass<Integer>L,Integerx){inti,k=0;for(i=0;i<L.size();i++){if(L.GetElem(i)!=x) //将不为x的元素插入到data中{L.SetElem(k,L.GetElem(i));k++;}}L.Setsize(k); //重置长度}

解法1：对于整数顺序表L，删除其中所有x元素后得到的结果顺序表可以与原L共享，所以求解问题转化为新建结果顺序表。34/58publicstaticvoidDeletex2(SqListClass<Integer>L,Integerx){inti,k=0;for(i=0;i<L.size();i++){if(L.GetElem(i)!=x) //将不为x的元素前移k个位置L.SetElem(i-k,L.GetElem(i));else //累计删除的元素个数kk++;}L.Setsize(L.size()-k); //重置长度}

解法2：对于整数顺序表L，从头开始扫描L，用k累计当前为止值为x的元素个数（初始值为0），处理当前序号为i的元素ai：

（1）若ai是不为x的元素，此时前面有k个为x的元素，将ai前移k个位置，继续处理下一个元素。

（2）若是为x的元素，置k++，继续处理下一个元素。

最后将L的长度减少k。35/58解法3：由解法2延伸出区间划分法

初始时，“不为x的区间”为空

i=-1，j从0开始遍历，“为x的区间”是a[i+1..j-1]若a[j]=x，跳过，j++。若a[j]≠x，操作是，先执行i++，将a[j]与a[i]进行交换，再执行j++继续遍历其余元素。a0…aiai+1…an-1aj≠x时交换aj…不为x元素区间j为x元素区间36/58publicstaticvoidDeletex3(SqListClass<Integer>L,Integerx){inti=-1,j=0;Integertmp;while(j<L.size()){ //j扫描所有元素if(L.GetElem(j)!=x){ //找到不为x的元素a[j]i++; //扩大不为x的区间if(i!=j)L.swap(i,j); //将a[i]与a[j]交换}j++; //继续扫描}L.Setsize(i+1); //重置长度}

xxxxaj

…

an-1不为x的区间a0…

ai为x的区间37/58

【例2.5】对于含有n个整数元素的顺序表L。设计一个尽可能高效的算法删除所有相邻重复的元素，即多个相邻重复的元素仅仅保留一个。例如L=(1，2，2，2，1)，删除后L=(1，2，1)。并给出算法的时间复杂度和空间复杂度。publicstaticvoidDelsame(SqListClass<Integer>L){inti,k=1;for(i=1;i<L.size();i++){if(L.GetElem(i)!=L.GetElem(k-1)){//将不是相邻重复的元素插入L.SetElem(k,L.GetElem(i));k++;}}L.Setsize(k); //重置长度}解：采用例2.4中解法1的整体创建顺序表的算法思路自己试一试：采用例2.4中解法2和解法3呢？38/58设计一个算法，从一给定的顺序表L中删除元素值在x到y（x≤y）之间的所有元素，要求算法的时间复杂度为O(n)，空间复杂度为O(1)。设计一个算法从有序顺序表中删除重复的元素，并使剩余元素间的相对次序保持不变。…扩展各种顺序表的高效算法设计39/583.有序顺序表的算法设计

【例2.6】有两个按元素值递增有序的整数顺序表A和B，设计一个算法将顺序表A和B的全部元素合并到一个递增有序顺序表C中。并给出算法的时间复杂度和空间复杂度。A=(1,3,5,8)B=(2,3,8,10,11)合并C=(1,2,3,3,5,8,8,10,11)40/58iA：a0a1…ai…an-1jB：b0b1…bj…bm-1C：c0c1…ck…cn+m-1k两者比较将较小者添加到C中二路归并：41/58publicstaticSqListClass<Integer>Merge2(SqListClass<Integer>A, SqListClass<Integer>B){SqListClass<Integer>C=newSqListClass<Integer>();inti=0,j=0; //i用于遍历A,j用于遍历Bwhile(i<A.size()&&j<B.size()){//两个表均没有遍历完if(A.GetElem(i)<B.GetElem(j)){C.Add(A.GetElem(i)); //将较小的A中元素添加到C中i++;}else{C.Add(B.GetElem(j)); //将较小的B中元素添加到C中j++;}}42/58while(i<A.size()){ //若A没有遍历完毕C.Add(A.GetElem(i));i++;}while(j<B.size()){ //若B没有遍历完毕C.Add(B.GetElem(j));j++;}returnC;}算法中尽管有多个while循环语句，但恰好对顺序表A、B中每个元素均访问一次，所以时间复杂度为O(n+m)。算法中需要在临时顺序表C中添加n+m个元素，所以算法的空间复杂度也是O(n+m)。43/58

二路归并中，若两个有序表的长度分别为n、m，算法主要时间花费在元素比较上。那么比较次数是多少呢？?最好的情况：整个归并中仅仅是较长表的第一个元素与较短表每个元素比较一次，此时元素比较次数为MIN(n，m)（为最少元素比较次数），如A=(1，2，3)，B=(4，5，6，7，8)，只需比较3次。最坏的情况：这n+m个元素均两两比较一次，比较次数为n+m-1（为最多元素比较次数），如A=(1，3，5，7)，B=(2，4，6)，需要比较6次。44/582009年全国计算机学科考研题

【例2.7】一个长度为L（L≥1）的升序序列S，处在第

L/2

个位置的数称为S的中位数。

例如：若序列S1=(11，13，15，17，19)，则S1的中位数是15。

两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2=(2，4，6，8，20)，则S1和S2的中位数是11。

现有两个等长的升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。要求：（1）给出算法的基本设计思想。（2）根据设计思想，采用C、C++或Java语言描述算法，关键之处给出注释。（3）说明你所设计算法的时间复杂度和空间复杂度。45/58S1=(11，13，15，17，19)S2=(2，4，6，8，20)二路归并S=(2，4，6，8，

11，13，15，17，19，20)中位数实际上，不需要求出S的全部元素，用k记录当前归并的元素个数，当k=n时，归并的那个元素就是中位数。

思路46/58intM_Search(intA[],intB[],intn){inti，j，k;i=j=k=0;while(i<n&&j<n){k++; //累计归并元素的次数

if(A[i]<B[j]){

if(k==n)returnA[i];i++;

}

else{ //A[i]>=B[j]

if(k==n)

returnB[j];j++;}

}}算法的时间复杂度为O(n)，空间复杂度为O(1)。47/582.2.4ArrayList顺序表容器

在实际应用中可以采用ArrayList类对象作为顺序表，使用其提供的各种方法完成更复杂的问题求解。1.ArrayList类的基本应用ArrayList类的构造方法

（1）ArrayList()：构造一个初始容量为10的空列表。

（2）ArrayList(int

initialCapacity)：构造一个具有指定初始容量的空列表。

（3）ArrayList(Collection<?extendsE>

c)：构造一个包含指定集合的元素的列表。48/58ArrayList类的主要方法

（1）booleanisEmpty()：如果列表不包含元素，则返回true。

（2）intsize()：

返回此列表中的元素数。

（3）add(E

e)：向列表的尾部添加指定的元素。

（4）voidadd(int

index,E

element)：在列表的指定位置插入指定元素。

（5）booleancontains(Object

o)：如果列表包含指定的元素，则返回true。

（6）Eget(int

index)：返回列表中指定位置的元素。

（7）Eset(int

index,E

element)：用指定元素替换列表中指定位置的元素。

（8）intindexOf(Object

o)：返回此列表中第一次出现的指定元素的索引。如果此列表不包含该元素，则返回-1。

（9）intlastIndexOf(Object

o)：返回此列表中最后出现的指定元素的索引。如果列表不包含此元素，则返回-1。

（10）voidclear()：从列表中移除所有元素。

（11）Eremove(int

index)：移除列表中指定位置的元素。

（12）booleanremove(Object

o)：从此列表中移除第一次出现的指定元素（如果存在）。49/582.ArrayList类元素排序

若ArrayList对象中的元素属于Java基本数据类型，如：

ArrayList<Integer>myarrlist=newArrayList<Integer>();

//元素类型为整型则排序方法如下：（1）按元素递增排序Collections.sort(myarrlist);（2）按元素递减排序Collections.sort(myarrlist,Collections.reverseOrder());50/58

若ArrayList对象中的元素属于类类型，则需要指定按什么成员变量排序、按什么次序排序等，主要方式如下：

（1）设置Comparable排序接口

若一个类实现了Comparable接口，就意味着“该类支持排序”。为此重写compareTo方法以定制排序方式。compareTo方法的用法：compareTo(比较对象)若当前对象的值<比较对象的值，返回一个负整数。若当前对象的值=比较对象的值，则返回0。若当前对象的值>比较对象的值，则返回一个正整数。然后调用Collections.sort(ArrayList对象)进行排序。51/58

（2）设置Comparator比较器接口

若需要定控某个类对象的排序次序，而该类本身不支持排序（即没有实现Comparable接口），可以建立一个“比较器”来进行排序。这个“比较器”只需要实现Comparator接口即可。其格式如下：

其中，compare(o1，o2)方法的用法是根据第一个参数小于、等于或大于第二个参数分别返回负整数、零或正整数。Collections.sort(ArrayList对象,newComparator<元素类>{@Overridepublicintcompare(元素类o1,元素类o2){returno1.比较属性().compareTo(o2.比较属性());}});52/58

（3）调用ArrayList类的sort()方法Java8中增加了使用Comparator的comparing进行排序，按照ArrayList类对象中元素类的排序属性进行递增排序的格式如下：

ArrayList类对象.sort(Cparing(元素类::排序属性));

按照ArrayList类对象中元素类的排序属性进行递减排序的格式如下：

ArrayList类对象.sort(Cparing(元素类::排序属性).reversed());53/58

如果是按多个成员变量值排序，还可以增加thenComparing等。

例如ArrayList类对象myarrlist中元素为User类对象，User类有3个成员变量F1、F2和F3，对应的属性分别为getF1()、getF2()和get