第1章第1节练习题9 查找指定值
最后更新于：2022-04-01 19:50:26
## 问题描述
> 线性表(a1,a2,a3,...,an)中元素递增有序，且按顺序存储于计算机内。要求设计一算法完成用最少时间在表中查找数据值为x的元素；若找到，将其与后继元素位置交换；若找不到将其插入到表中，使表中的元素仍递增有序
## 算法思想
> 本题递增有序，为了在最少的事件内完成指定数据x的查找，那么我们可以采用折半查找的思想查找x，如果找到，那么与后继元素交换一次，如果找不到则顺序插入便可。
## 算法描述
~~~
int FindDI(SqList *L, ElemType x)
{
int low=0, high=L->length-1;
int mid;
//折半查找
while(lowdata[mid]==x){
break;
}else if(L->data[mid]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
#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;ilength-1;
int mid;
while(lowdata[mid]==x){
break;
}else if(L->data[mid]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;ilength;i++){
printf("%4d",L->data[i]);
}
printf("\n");
}
~~~
';