Love嵌入式 发表于 2008-3-11 22:11

高手帮忙啊！！

[size=5]一个顺序表La（假设La={1，1，2，3，3，4，6，7，}）中的元素非递减有序，试写一算法，将X插入到顺序表中适当的位置，以保持该表有序性。非常感谢啊！！[/size]

Ethip 发表于 2008-3-12 08:58

回复 1# 的帖子

没有学过数据结构吗？

Ethip 发表于 2008-3-12 09:01

回复 1# 的帖子

找来看看先，那书一开头就是将你的那个问题哦！

mrtao 发表于 2008-3-12 09:29

大部分数据结构的书的开始部分都有的

wfx_best 发表于 2008-3-12 15:59

回答楼主:
假设要插入的数是 x , 顺序表 a
我想到一个方法,下面我把算法描述一下:
可以用折半摸索的方法,寻找一个合适 x 的地方,容易理解这个地方就是与 x 相等的或 <x< 这样的位置(这个位置就是我们要将 x 插入的地方,打比方: 如果是返回的是 3,我们要将 x 插入的位置就是4 ).
    这里就有两个要处理的地方,如果是与 x 相等的我们直接返回它的下标值,但这种概率一般很小,这是第一种情况;  第二种情况,经常搜索会一直进行到剩下最一个元素,我们只要把 x 与这个元素比较,如果 x 小插在此元素前面, x 大则插在后面.
    此算法关键在用折半搜索方法, 将 x 插入到与它相等的地方是不会错的,否则要将 x 插入到 <x<
的地方,这时我们要搜索到最后一个元素,这样才能保证插入的正确性.如果你已经明白了,那么细节的地方你自己去做咯.

wfx_best 发表于 2008-3-12 16:03

补充一下:
我上面说的那个算法,最坏的情况和一般情况出现的概率都差不多,时间复杂度如下
  log2(n) 向上取整,再加上其它消耗
折半感觉还是不错的.

mqh21364 发表于 2008-3-12 21:37

能不能用类似冒泡，选择的数组排序算法呢？？

wfx_best 发表于 2008-3-12 22:09

冒泡是用于排序的,这里是已经排好序,要做的是插入工作.
当然要是从头到尾对每个元素都比较一遍也行,但这样效率要低很多(它的时间复杂度是 n)

sunkaidong 发表于 2008-3-12 23:01

呵呵。。同意楼上观点。。。。折半要效率效率高。。。。

iyth61525 发表于 2008-3-16 15:51

程序如下：
ListInsert(&La,int i,ElemType m)  //在顺序表中插入新的元素m
{  if(i<1!!i>L.length+1)
       return  errror;
   if(L.length>=L.listsize)
      La.elem=(ElemType * )realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
   if(!La.elem) exit(OVERLOW);
   L.listsize=L.listsize+LISTINCREMENT;
   for(j=elem+n-1;j>=elem+i-1;j--)
      *(j+1)=*j;
   *j=x;
   return OK;
}

页: [1]

编程论坛