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

问题描述

从顺序表中删除具有最小值的元素(假设唯一)并由函数返回被删除的值。空出的位置由最后一个元素填补，若顺序表为空，则显示出错信息并退出运行。

问题分析

无

代码实现

bool DeleteMin(SeqList &L,ElementType &min){
    if(L.lenght == 0){
        printf("顺序表为空");
        return false;
    }
    int flag = 0;
    for(int i = 0;i < L.lenght;i++){
        if(L.data[i] < L.data[flag]){
            flag = i;
        }
    }
    min = L.data[flag];
    if(flag != L.lenght - 1){
        L.data[flag] = L.data[L.lenght - 1];
    }
    L.lenght -= 1;
    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 DeleteMin(SeqList &L,ElementType &min){
    if(L.lenght == 0){
        printf("顺序表为空");
        return false;
    }
    int flag = 0;
    for(int i = 0;i < L.lenght;i++){
        if(L.data[i] < L.data[flag]){
            flag = i;
        }
    }
    min = L.data[flag];
    if(flag != L.lenght - 1){
        L.data[flag] = L.data[L.lenght - 1];
    }
    L.lenght -= 1;
    return true;
}

int main()
{
    SeqList L;
    InitSeqList(L);
    for(int i = 0;i < 10;i++){
        InsertELem(L,i + 1, arr[i]);
    }
    int min;
    if(DeleteMin(L,min)){
        printf("删除元素：%d\n", min);
        for(int i = 0;i < L.lenght;i++){
            printf("%d ", L.data[i]);
        }
    }else{
        printf("删除失败\n");
    }
    return 0;
}