问题描述

线性表(a1,a2,a3,...,an)中元素递增有序，且按顺序存储于计算机内。要求设计一算法完成用最少时间在表中查找数据值为x的元素；若找到，将其与后继元素位置交换；若找不到将其插入到表中，使表中的元素仍递增有序

算法思想

本题递增有序，为了在最少的事件内完成指定数据x的查找，那么我们可以采用折半查找的思想查找x，如果找到，那么与后继元素交换一次，如果找不到则顺序插入便可。

算法描述

int FindDI(SqList *L, ElemType x)
{
    int low=0, high=L->length-1;
    int mid;
    //折半查找
    while(low<high){
        mid=(low+high)/2;
        if(L->data[mid]==x){
            break;
        }else if(L->data[mid]<x){
            low=mid+1;
        }else{
            high=mid-1;
        }
    }
    //已找到，与后继元素位置交换
    if(L->data[mid]==x&&L->data[mid]!=L->length-1){
        ElemType temp;
        temp=L->data[mid];
        L->data[mid]=L->data[mid+1];
        L->data[mid+1]=temp;
        return mid+1;
    }
    //未找到，插入该元素，并且使表中的元素仍递增有序
    if(low>high){
        int i;
        for(i=L->length;i>mid;i--){
            L->data[i]=L->data[i-1];
        }
        L->data[i]=x;
        L->length=L->length+1;
        return -1;
    }
    return 0;
}

具体代码见附件

附件

#include<stdio.h>
#define MaxSize 100
typedef int ElemType;

typedef struct{
    ElemType data[MaxSize];
    int length;
}SqList;

int FindDI(SqList*, ElemType);
void Print(SqList*);

int main(int argc,char *argv[])
{
    SqList SL;
    ElemType e=4;
    SL.length=10;
    for(int i=0;i<SL.length;i++){
        SL.data[i]=2*i+1;
    }
    Print(&SL);
    int flag=FindDI(&SL,e);

    if(flag==-1){
        printf("Find fail!,It will be instered the true position
");
        Print(&SL);
    }else{
        printf("Find success!
");
        printf("It is posed %dth, It will swap with next number!
", flag);
        Print(&SL);
    } 
    return 0;
}

int FindDI(SqList *L, ElemType x)
{
    int low=0, high=L->length-1;
    int mid;
    while(low<high){
        mid=(low+high)/2;
        if(L->data[mid]==x){
            break;
        }else if(L->data[mid]<x){
            low=mid+1;
        }else{
            high=mid-1;
        }
    }

    if(L->data[mid]==x&&L->data[mid]!=L->length-1){
        ElemType temp;
        temp=L->data[mid];
        L->data[mid]=L->data[mid+1];
        L->data[mid+1]=temp;
        return mid+1;
    }

    if(low>high){
        int i;
        for(i=L->length;i>mid;i--){
            L->data[i]=L->data[i-1];
        }
        L->data[i]=x;
        L->length=L->length+1;
        return -1;
    }
    return 0;
}

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