关于代码中的bug

来源:9-2 排序链表-代码实操

橙序猿哥哥

2019-06-19

详细的看了几遍老师的视频,然后又试了试老师的源码,发现两个个小bug

  • 第一个
    对于输入数组是 [ 5 , 4 , 1 , 3 , 2] 结果为 [ 1, 3, 4, 5, 2 ],
    原因出在寻找基准元素节点函数应该少了最后一步
let partion = (begin, end) => {
  let val = begin.val
  let p = begin
  let q = begin.next
  while (q !== end) {
    if (q.val < val) {
      p = p.next
      swap(p, q)
    }
    q = q.next
  }
  /***此处q点和end指向同一节点,但是并未对end处的节点值进行判断***/
  swap(p, begin)
  return p
}

其中的while循环处存在一个小bug
当q指向end时,此处q点和end指向同一节点,但是并未对end节点处的val大小进行判断
应该改为

let partion = (begin, end) => {
  let val = begin.val
  let p = begin
  let q = begin.next
  while (q !== end) {
    if (q.val < val) {
      p = p.next
      swap(p, q)
    }
    q = q.next
  }
  /***增加步骤*********************************/
  if( q.val < val ){
			swap( p.next , q)
			p = p.next
  }
 /***********************************/	
  // 让基准元素跑到中间去
  swap(p, begin)
  return p
}
  • 第二个
    对于更改完第一个bug后,再次测试发现报错
    **
    let val = begin.val
    ^
    TypeError: Cannot read property ‘val’ of undefined
    **
    原因是在某次循环中,存在p指针指到了end,当进行下一轮递归时,p.next指向undefined,出现这种情况也就是说明,本次分类完成时,大于标志位的右侧组只剩一个元素,导致下一轮递归时,p.next指向发生错误
    更改方法很简单,就是在排序时判断一下,begin是否存在,如果begin不存在代表出现上述情况,则本次递归 无需再进行直接跳出即可,return “”
let partion = (begin, end) => {
	/*******************增加代码***************************/
	if( !begin ){
		return ""
	}
	/****************************************************/
  let val = begin.val
  let p = begin
  let q = begin.next
  while (q !== end) {
    if (q.val < val) {
      p = p.next
      swap(p, q)
    }
    q = q.next
  }
	  if( q.val < val ){
			swap( p.next , q)
			p = p.next
  }
  // 让基准元素跑到中间去
  swap(p, begin)
  return p
}
写回答

2回答

快乐动起来呀

2019-06-19

同学我跑了源码,没发现问题啊:


//img.mukewang.com/szimg/5d0a5a600001da3807580528.jpg

0
2
自驱动
if( q.val <= val ){ swap( p.next , q) p = p.next } 需要小于等于,如果最小值有2个一样,就不会置换了 [1,2,4,3,1]
2021-03-30
共2条回复

橙序猿哥哥

提问者

2019-06-19

哦哦,我明天再去试一试 可能是我出我问题了

0
0

JavaScript版 数据结构与算法

填补前端同学的算法短板,掌握面试中最常见的算法与数据结构

2467 学习 · 395 问题

查看课程