问题描述

描述1：已知在一维数组$A[m+n]$中依次存放着两个线性表$(a_1,a_2,a_3,...,a_m)$和$(b_1,b_2,b_3,...,b_n)$,试编写一个函数，将数组中两个顺序表互换，即将$(b_1,b_2,b_3,...,b_n)$放在$(a_1,a_2,a_3,...,a_m)$的前面

描述2： 已知在一维数组$A[m+n]$中依次存放着两个线性表$(a_1,a_2,a_3,...,a_m)$和$(b_1,b_2,b_3,...,b_n)$,试编写一个函数将A中保存的序列循环左移m位

算法思想">算法思想

上面的两种问法最后的结果都是一样的，即将数组$(a_1,a_2,a_3,...,a_m,b_1,b_2,b_3,...,b_n)$变为$(b_1,b_2,b_3,...,b_n,a_1,a_2,a_3,...,a_m)$
为了达到上述目的，我们可以将数组$A[m+n]$中的全部元素$(a_1,a_2,a_3,...,a_m,b_1,b_2,b_3,...,b_n)$原地逆置为$(b_n,b_{n-1},b_{n-2},...,b_1,a_m,a_{m-1},a_{m-2},...,a_1)$，再对前n个元素和后m个元素分别使用逆置算法，就可以得到$(b_1,b_2,b_3,...,b_n,a_1,a_2,a_3,...,a_m)$，从而实现顺序表的位置互换

算法描述">算法描述

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<stdio.h>
#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;i<SL.length;i++){
        SL.data[i]=i+1;
    }

    int m=3, n=SL.length-m;

    Print(&SL);
    Reverse(&SL, 0, SL.length-1, SL.length-1);
    Reverse(&SL, 0, m-1, m);
    Reverse(&SL, m, SL.length-1, n);
    Print(&SL);

    return 0;
}

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;
    }

}

void Print(SqList *L){
    for(int i=0;i<L->length;i++){
        printf("%4d",L->data[i]);
    }
    printf("\n");
}