[数据结构] 王道数据结构2023 P18_02

问题描述

设计一个高效算法，将顺序表L的所有元素逆置，要求算法的空间复杂度为O(1)

问题分析

无

代码实现

bool ReverseList(SeqList &L){
    if(L.lenght == 0){
        printf("内容为空\n");
        return false;
    }
    ElementType temp;
    for(int i = 0,j = L.lenght - 1;i < j;i++,j--){
        temp = L.data[i];
        L.data[i] = L.data[j];
        L.data[j] = temp;
    }
    return true;
}

算法分析

无

时间复杂度 O(n)

空间复杂度 O(1)

完整代码

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#define ElementType int
#define InitSize 100

int arr[] = {1,2,3,4,5,6,7,8,9,0};

typedef struct {
    ElementType *data;
    int MaxLen,lenght;
}SeqList;

void InitSeqList(SeqList &L){
    L.data = (ElementType *)malloc(sizeof(ElementType) * InitSize);
    L.MaxLen = InitSize;
    L.lenght = 0;
}

bool InsertELem(SeqList &L,int i,ElementType data){
    if(i < 1 || i > L.lenght + 1){
        printf("位置不合法\n");
        return false;
    }
    if(L.lenght + 1 > L.MaxLen){
        printf("线性表已满\n");
        return false;
    }
    for(int j = L.lenght;j >= i;j--){
        L.data[j] = L.data[j - 1];
    }
    L.data[i - 1] = data;
    L.lenght += 1;
    return true;
}

bool ReverseList(SeqList &L){
    if(L.lenght == 0){
        printf("内容为空\n");
        return false;
    }
    ElementType temp;
    for(int i = 0,j = L.lenght - 1;i < j;i++,j--){
        temp = L.data[i];
        L.data[i] = L.data[j];
        L.data[j] = temp;
    }
    return true;
}

void ShowList(SeqList L){
    for(int i = 0;i < L.lenght;i++){
        printf("%d ", L.data[i]);
    }
    printf("\n");
}

int main()
{
    SeqList L;
    InitSeqList(L);
    for(int i = 0;i < 10;i++){
        InsertELem(L,i + 1, arr[i]);
    }
    if(!ReverseList(L)){
        printf("线性表反转失败\n");
    }else{
        printf("线性表反转成功:");
        ShowList(L);
    }
    return 0;
}