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

admin2017-11-14  30

问题 线性表(a1,a2,a3,…,an)中元素递增有序且按顺序存储于计算机内。要求设计算法完成以下内容:
    (1)用最少的时间在表中查找数值为x的元素。
    (2)若找到将其与后继元素位置相交换。
    (3)若找不到将其插入表中并使表中元素仍递增有序。

选项

答案(1)顺序存储的线性表递增有序,可以顺序查找,也可折半查找。题目要求“用最少的时间在表中查找数值为x的元素”,这里应使用折半查找方法。 void searchExchangeInsert(ElemType a[];ElemType x) //a是具有n个元素的递增有序线性表,顺序存储。本算法在表中查找数值为X的 //元素,如查到则与其后继交换位置;如查不到,则插入表中,且使表仍递增有序 { low=0: high=11—1: //low和high指向线性表下界和上界的下标 while(10w<=high) { mid:(10w+high)/2: //找中间位置 if(a[mid]==X)break; //找到X,退出while循环 else if(a[mid]high) //查找失败,插入数据元素x { for(i=n—1:i>high;i一一) a[i+1]=a[i]; //后移元素 a[i+1]=X; //插入X } ∥结束插入 } ∥结束本算法 (2)算法讨论 首先是线性表的描述。算法中使用一维数组a表示线性表,未使用包含数据元素的一维数组和指示线性表长度的结构体。若使用结构体,对元素的引用应使用a.elem[i]。另外,元素类型就假定是ElemType,未指明具体类型。其次,C中一维数组下标从0开始,若说有n个元素的一维数组,其最后一个元素的下标应是n一1。最后,本算法可以写成三个函数,即查找函数、交换后继函数与插入函数,写成三个函数显得逻辑清晰、易读。

解析
转载请注明原文地址:https://kaotiyun.com/show/Y3Ri777K
0

最新回复(0)