数据结构 | 每日一练（53）

数据结构

合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下

——老子

1

每日一练

1．线性表(a 1 ,a 2 ,a 3 ,…,a n )中元素递增有序且按顺序存储于计算机内。要求设计一算法完成：

（1） 用最少时间在表中查找数值为 x 的元素。

（2） 若找到将其与后继元素位置相交换。

（3） 若找不到将其插入表中并使表中元素仍递增有序。

正确答案

ps：||代表注释

1.[题目分析] 顺序存储的线性表递增有序，可以顺序查找，也可折半查找。题目要求“用最少的时间在表中查找数值为x的元素”，这里应使用折半查找方法。

void SearchExchangeInsert（ElemType a[]；ElemType x）

∥a是具有n个元素的递增有序线性表，顺序存储。本算法在表中查找数值为x的元素，如查到则与其后继交换位置；如查不到，则插入表中，且使表仍递增有序。

{ low=0；high=n-1； ∥low和high指向线性表下界和上界的下标

while（low<=high）

{mid=（low+high）/2； ∥找中间位置

if（a[mid]==x） break； ∥找到x，退出 while循环。

else if （a[mid] <x） low=mid+1；∥到中点mid的右半去查。

else high=mid-1； ∥到中点mid的左部去查。

}

if（a[mid]==x && mid!=n）∥ 若最后一个元素与x相等，则不存在与其后继交换的操作。

{t=a[mid]；a[mid]=a[mid+1]；a[mid+1]=t；} ∥ 数值x与其后继元素位置交换。

if（low>high） ∥查找失败，插入数据元素x

{ for（i=n-1；i>high；i--） a[i+1]=a[i]；∥后移元素。

a[i+1]=x；∥插入x。

} ∥结束插入

}∥结束本算法。

[算法讨论] 首先是线性表的描述。算法中使用一维数组a表示线性表，未使用包含数据元素的一维数组和指示线性表长度的结构体。若使用结构体，对元素的引用应使用a.elem[i]。另外元素类型就假定是ElemType，未指明具体类型。其次，C中一维数组下标从0开始，若说有n个元素的一维数组，其最后一个元素的下标应是n-1。第三，本算法可以写成三个函数，查找函数，交换后继函数与插入函数。写成三个函数显得逻辑清晰，易读。

如果您觉得本篇文章对您有作用，请转发给更多的人，点一下好看就是对小编的最大支持！

-end-