归并 两个长度分别为m和n的有序表,最坏情况下需要比较m+n-1次? |
您所在的位置:网站首页 › 有序表合并最好情况 › 归并 两个长度分别为m和n的有序表,最坏情况下需要比较m+n-1次? |
*摘自百度知道 合并有序表的方法通常使用双指针法。 最差的情况是所有元素都比较过。每比较一次就往表C里放一个元素,也就是说排完m+n-1个元素比较了m+n-1次。 最后一个元素直接放到表C的表尾就可以了。所以总共是m+n-1次。 例:两个有序表分别为: A:1,3,5 B:2,4,6 合并的结果要产生新表C,且表C也是从小到大排序的。 解: 设上链指针p,下链q,每次比较后较小节点依次作为“合并后链表的节点”,同时较小链指针后移。某链指空后不再比较。 具体过程为: 第一步:1和2比,1小作为新节点,p移至3。第二步,3和2比,2小作为新节点,q移至4。第三步,3和4比,3小,p移至5。第四步,5和4比,4小,q移至6。第五步,5和6比,p指空。结束。 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |