作者：解学武

问题说明

顺序表的就地逆置，即利用原表的存储空间将线性表 (a₁,a₂,a₃,…,a_n) 逆置为 (a_n,…,a₃,a₂,a₁)，实现过程中要求只能使用一个元素的辅助空间。

实现思路

根据顺序表的长度不同，分为两种处理方式：

1. 若顺序表为空表，或者长度仅为 1 ，根据常识判断，该顺序表即使进行逆置操作，最终结果还是其自身，所以为了提高效率，对于此类顺序表不做任何处理。
2. 若顺序表的长度超过1 ，则需对顺序表进行就地逆置，实现过程为：设置两个变量 i 和 j ，分别初始化为顺序表的首元素和尾元素所在数组的下标：若 i < j，则将 a[i] 和 a[j] 的值进行交换，交换后执行 i++ 和 j-- 操作，即分别令 i 和 j 指向顺序表的第 2 个元素和倒数第 2 个元素，再进行交换，依次类推，直到  i 的值大于或等于 j 为止。

代码实现

#include <stdio.h>
#define MAXSIZE 100 //定义顺序表的最大长度
typedef int ElemType;//宏定义顺序表的数据类型
//定义顺序表
typedef struct{
    ElemType data[MAXSIZE];
    int length;//记录顺序表的长度
}SqList;
//创建顺序表的函数，其中 L 为外界声明的顺序表，n 为顺序表的长度
void Creat_SqList(SqList *L,int n){
    int i;
    L->length = n;
    i = 0;
    printf("input %d data:",n);
    //往顺序表中输入 n 个数据
    while(i < n){
        scanf("%d",&L->data[i]);
        i++;
    }
}
//顺序表的就地逆置的实现函数，其中形参 L 为需要逆置的顺序表
void Reverse_SqList(SqList *L){
    int i,j,n,t;
    n = L->length;
    //如果顺序表的长度为 0 或 1 ，由于逆置后还是自身，所以不需要进行逆置
    if (n == 0 || n == 1){
        return ;
    }
    //如果顺序表的长度大于2，则需要进行逆置，设置 i和 j 分别指向顺序表中第一个和最后一个数据
    i = 0;
    j = n-1;
    //不断地交换 i 和 j 所指向的数据，直到 i>j 为止
    while(i<j){
        //此时就用到的唯一一个辅助空间，用于数据之间的交换
        t = L->data[i];
        L->data[i] = L->data[j];
        L->data[j] = t;
        i++;
        j--;
    }
}
//顺序表的输出函数
void Print_SqList(SqList *L){
    int i,n;
    n = L->length;
    i = 0;
    printf("output %d data:",n);
    while(i < n){
        printf("%d ",L->data[i]);
        i++;
    }
}
int main(){
    SqList L;//声明一个顺序表
    int n;
    printf("intput n: ");
    scanf("%d",&n);
    //根据 n 的值，对顺序表进行初始化，n值不能超过MAXSIZE的值
    Creat_SqList(&L,n);
    //将顺序表进行就地逆置
    Reverse_SqList(&L);
    //输出逆置后的顺序表
    Print_SqList(&L);
    return 0;
}

运行结果： 代码分析：

• 5-8行：定义顺序表的结构体，获取数组长度，还可以使用 C 语言库中的函数。
• 10-20行：对声明的顺序表进行初始化
• 22-41行：实现顺序表的就地逆置函数
• 43-52行：顺序表的输出函数
• 53-65行：主函数，通过声明顺序表，然后调用顺序表的初始化函数、就地逆置函数以及输出函数，即可完整顺序表的就地逆置的功能。

提示：可根据实现需要，适当更改代码。

声明：当前文章为本站“玩转C语言和数据结构”官方原创，由国家机构和地方版权局所签发的权威证书所保护。