第1章第1节练习题9 查找指定值

问题描述

线性表 (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\n");
        Print(&SL);
    }else{
printf("Find success!\n");
printf("It is posed %dth, It will swap with next number!\n", 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("\n");
}