第1章第1节练习题8 顺序表循环移位
最后更新于：2022-04-01 19:50:24
## 问题描述
> **描述1：**已知在一维数组A[m+n]中依次存放着两个线性表(a1,a2,a3,...,am)和(b1,b2,b3,...,bn),试编写一个函数，将数组中两个顺序表互换，即将(b1,b2,b3,...,bn)放在(a1,a2,a3,...,am)的前面
> **描述2：** 已知在一维数组A[m+n]中依次存放着两个线性表(a1,a2,a3,...,am)和(b1,b2,b3,...,bn),试编写一个函数将A中保存的序列循环左移m位
## 算法思想
上面的两种问法最后的结果都是一样的，即将数组(a1,a2,a3,...,am,b1,b2,b3,...,bn)变为(b1,b2,b3,...,bn,a1,a2,a3,...,am)
为了达到上述目的，我们可以将数组A[m+n]中的全部元素(a1,a2,a3,...,am,b1,b2,b3,...,bn)原地逆置为(bn,bn−1,bn−2,...,b1,am,am−1,am−2,...,a1)，再对前n个元素和后m个元素分别使用逆置算法，就可以得到(b1,b2,b3,...,bn,a1,a2,a3,...,am)，从而实现顺序表的位置互换
## 算法描述
~~~
void Reverse(SqList *L, int left, int right, int length)
{
ElemType temp;
int mid;
mid=(left+right)/2;
for(int i=0;i<=mid-left;i++){
temp=L->data[left+i];
L->data[left+i]=L->data[right-i];
L->data[right-i]=temp;
}
}
~~~
具体代码见附件
## 附件
~~~
#include
#define MaxSize 100
typedef int ElemType;
typedef struct{
ElemType data[MaxSize];
int length;
}SqList;
void Reverse(SqList*, int, int, int);
void Print(SqList*);
int main(int argc,char* argv[])
{
SqList SL;
SL.length=10;
for(int i=0;idata[left+i];
L->data[left+i]=L->data[right-i];
L->data[right-i]=temp;
}
}
void Print(SqList *L){
for(int i=0;ilength;i++){
printf("%4d",L->data[i]);
}
printf("\n");
}
~~~
';