数据结构
顺序表典型例题
1. 有两个顺序表LA和LB，其元素均为非递减有序排列，编写算法，将它们合并为一个新的顺序表LC，要求LC也是非递减有序排列。
2. 假设一个线性表采用顺序表表示，设计一个算法，删除其中所有值等于x 的元素，要求算法的时间复杂度O(n),空间复杂度O(1)。
3.
4.
5.有一个顺序表L，设计一个尽可能高效的算法，将所有的奇数移动到偶数前面。
代码：
1.
void mergeList(SqList *LA,SqList *LB,SqList *LC)
{
int i,j,k,l;
i=0;j=0;k=0;
while(i<=LA->last&&j<=LB->last)
{
if(LA->elem[i]<=LB->elem[i])
{
LC->elem[i]=LA->elem[i];
i++;
k++;
}
else
{
LC->elem[i]=LB->elem[i];
j++;
k++;
}
}
while(i<=LA->last)
{
LC->elem[i]=LA->elem[i];
i++;
k++;
}
while(i<=LB->last)
{
LC->elem[i]=LB->elem[i];
j++;
k++;
}
LC->last=LA->last+LB->last+1;
}
2.
void delnodel(SqList *&L,ElemType x)
{
int k=0,i;
for(i=0;i<L->length;i++)
{
if(L->data!=x)
{
L->data[k]=L->data[i];
k++;
}
}
L->length=k;
}
void delnode2(SqList *&L,ElemType x)
{
int k=0,i=0;
while(i<L->length)
{
if(L->data[i]==x)
k++;
else
L->data[i-k]=L->data[i];
i++;
}
L->length-=k;
}
3.
void del_x2y(SqList *L,ElemType x,ElemType y)
{
int j=0;
for( int i=0;i<=L->last;i++)
{
if(L->elem[i]<x||L->elem[i]>y)
{
L->elem[j++] = L->elem[i];
}
}
L->last=--j;
}
4.
void del_dupnum(SqList *L)
{
int i=0;j;
for(j=1;j<=L->last;j++)
{
if(L->elem[i]!=L->elem[j])
{
L->elem[++i]=L->elem[j];
}
}
L->last=i;
}
5.
void move(SqList *&L)
{
int i=0,j=L->length-1;
while(i<j)
{
while(i<j&&;L->data[j]%2==0)
j--;
while(i<j&&;L->data[ji%2==1)
i++;
if(i<j)
swap(L->data[i],L->data[j]);
}
}
