數(shù)據(jù)結(jié)構(gòu)
順序表典型例題
1.?有兩個順序表LA和LB，其元素均為非遞減有序排列，編寫算法，將它們合并為一個新的順序表LC，要求LC也是非遞減有序排列。
2.?假設(shè)一個線性表采用順序表表示，設(shè)計一個算法，刪除其中所有值等于x 的元素，要求算法的時間復(fù)雜度O(n),空間復(fù)雜度O(1)。
3.?
?
?
4.
?
?
5.有一個順序表L，設(shè)計一個盡可能高效的算法，將所有的奇數(shù)移動到偶數(shù)前面。
代碼：
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]);
}
}
