阅读:0       作者:严长生

顺序表的就地逆置(带源码+解析)

问题说明

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

实现思路

根据顺序表的长度不同,分为两种处理方式:
  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;
}
运行结果:
intput n: 4
input 4 data:3 2 1 4
output 4 data:4 1 2 3
代码分析:
  • 5-8行:定义顺序表的结构体,获取数组长度,还可以使用 C 语言库中的函数。
  • 10-20行:对声明的顺序表进行初始化
  • 22-41行:实现顺序表的就地逆置函数
  • 43-52行:顺序表的输出函数
  • 53-65行:主函数,通过声明顺序表,然后调用顺序表的初始化函数、就地逆置函数以及输出函数,即可完整顺序表的就地逆置的功能。

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