数据结构—线性表的顺序存储及运算—顺序表应用举例

例2.1 将顺序表(a1,a2,… ,an) 重新排列为以a1 为界的两部分:a1 前面的值均比a1 小,a1 后面的值都比a1 大(这里假设数据元素的类型具有可比性, 不妨设为整型),操作前后如图2.5所示。这一操作称为划分。a1 也称为基准。

划分的方法有多种,下面介绍的划分算法其思路简单,性能较差。基本思路:

从第二个元素开始到最后一个元素,逐一向后扫描:
(1)当前数据元素aI 比a1 大时,表明它已经在a1 的后面,不必改变它与a1 之间的位置,继续比较下一个。
(2)当前结点若比a1 小,说明它应该在a1 的前面,此时将它上面的元素都依次向下移动一个位置,然后将它置入最上方。


算法如下:
void part(SeqList *L)
{ int i,j;
datatype x,y;
x=L->data[0]; /* 将基准置入x 中*/
for(i=1;i<=L->last;i++)
if(L->data[i]<x) /*当前元素小于基准*/
{ y = L->data[i];
for(j=i-1;j>=0;j–) /*移动*/
L->data[j+1]=L->data[j];
L->data[0]=y;
}
}
算法2.5

本算法中,有两重循环,外循环执行n-1次,内循环中移动元素的次数与当前数据的大小有关,当第i个元素小于a1 时,要移动它上面的i-1个元素,再加上当前结点的保存及置入,所以移动i-1+2次,在最坏情况下,a1 后面的结点都小于a1 ,故总的移动次数为:

即最坏情况下移动数据时间性能为O(n2)。

这个算法简单但效率低,在第9章的快速排序中时我们将介绍另一种划分算法,它的性能为O(n)。

例2.2 有顺序表A和B,其元素均按从小到大的升序排列,编写一个算法将它们合并成一个顺序表C,要求C的元素也是从小到大的升序排列。

算法思路:依次扫描通过A和B的元素,比较当前的元素的值,将较小值的元素赋给C,如此直到一个线性表扫描完毕,然后将未完的那个顺序表中余下部分赋给C即可。C的容量要能够容纳A、B两个线性表相加的长度。

算法如下:
void merge(SeqList A, SeqList B, SeqList *C)
{ int i,j,k;
i=0;j=0;k=0;
while ( i<=A.last && j<=B.last )
if (A.date[i] C->data[k++]=A.data[i++];
else C->data[k++]=B.data[j++];
while (i<=A.last )
C->data[k++]= A.data[i++];
while (j<=B.last )
C->data[k++]=B.data[j++];
C->last=k-1;
}
算法2.6

算法的时间性能是O(m+n),其中m是A的表长,n是B的表长。

例2.3 比较两个线性表的大小。两个线性表的比较依据下列方法:设A、B是两个线性表,均用向量表示,表长分别为m和n。A′和B′分别为A 和B 中除去最大共同前缀后的子表。

例如A=(x,y,y,z,x,z), B=(x,y,y,z,y,x,x,z),两表最大共同前缀为(x,y,y,z) 。则A′=(x,z), B′=(y,x,x,z),若A′=B′= 空表,则A=B;若A′=空表且B′≠空表,或两者均不空且A′首元素小于B′首元素,则A<B;否则,A>B。

算法思路:首先找出A、B的最大共同前缀;然后求出A′和B′,之后在按比较规则进行比较,A>B 函数返回1;A=B返回0;A<B返回-1。算法如下:
int compare( A,B,m,n)
int A[],B[];
int m,n;
{ int i=0,j,AS[],BS[],ms=0,ns=0; /*AS,BS作为A′,B′*/
while (A[i]==B[i]) i++; /*找最大共同前缀*/
for (j=i;j<m;j++)
{ AS[j-i]=A[j];ms++; } /*求A′,ms为A′的长度*/
for (j=i;j<n;j++)
{ BS[j-i]=B[j];ns++; } /*求B′,ms为B′的长度*/
if (ms==ns&&ms==0) return 0;
else if (ms==0&&ns>0 || ms>0 && ns>0 && AS[0] else return 1;
}
算法2.7

算法的时间性能是O( m+n )。

如果引用本站的原创文章,请注明原文链接:,本站保留追究责任的权利!

发表评论