阿里前端2018秋招笔试题：判断JSON对象是否有环

前几天做了阿里前端秋招笔试题，感觉受打击很深，找工作很难呀。不过考试完还是要复盘一下。记得有一道题目是判断JSON对象是否有环。因为当使用JSON.stringify()方法格式化一个JSON对象时，如果该对象有环路，就会抛出异常：Uncaught TypeError: Converting circular structure to JSON。例如一下代码：

var obj={
  f:{
    name:'fff',
    age:20,
    call:null
  }
}
obj.f.call=obj.f;
//Uncaught TypeError: Converting circular structure to JSON(…)
JSON.stringify(obj)

当时考试的时候想了好长时间也写不出代码，虽然有思路，但总感觉代码很难写。所以这几天趁着有富裕时间，总算完成了代码的编写：

function isCycle(obj){
  var arr=['obj'],l=1,k=0,flag=false,str='';
  while(l>k){
    var obj_tmp=eval(arr[k]);
    var all=Object.keys(obj_tmp);
    str=arr[k]+'.';
    if(all.length>0){
      for(var i=0,length=all.length;i<length;i++){
        if((typeof obj_tmp[all[i]]) !='object'||Object.prototype.toString.call(obj_tmp)=='[object String]')continue;
        for(var j=0;j<l;j++){
          if(obj_tmp[all[i]]==eval(arr[j])){
            flag=true;
            break;
          }
        }
        if(flag)break;
        arr.push(str+all[i]);
        l++;
      }
    }
    if(flag)break;
    k++;
  }
  if(flag)return true;
  else return false;
}

最终测试如下：

var obj={
  f:{
    name:'fff',
    age:20,
    call:null
  }
};
obj.f.call='fff';

console.log(isCycle(obj));//output:false;

obj.f.call=obj.f;

console.log(isCycle(obj));//output:true;

obj.f.call=new Date();

console.log(isCycle(obj));//output:false;

obj.f.call=new String('ddd');

console.log(isCycle(obj));//output:false;
obj.f.call=[obj.f];

console.log(isCycle(obj));//output:true;

总体思想就是BFS，宽度优先搜索遍历得到对象的所有属性，维护一个数组存储遍历得到的所有值为对象的属性，在遍历一个新属性的时候首先检测其是否与属性数组中的某一项相等，若相等，则证明它是一个环，则要返回true；否则的话就将该属性放进属性数组中，继续遍历。因为属性都存在了数组里，其实遍历属性就是遍历整个属性数组，循环结束条件就是遍历完整个数组的属性。关于该方式有几点要注意：

• 上述思想中一个关键点是数组只保存属性值为对象的属性，因为属性值为基本类型的值不可能构成回环，只有值为对象的属性间的相互引用才能构成回环。而一些特殊的对象如基本包装类型、日期类型也不符合要求，可以通过Object.keys(attr).length>0过滤除去，不过对于String对象还需要进行进一步的过滤，因为显然它不会构成引用，而上面的方式也不会将其过滤除去。所以需要用Object.prototype.toString.call(obj_tmp)=='[object String]'将其过滤。

• 另外一个要注意的是如何判断两个属性是否相等，此时需要将属性数组里面的每个属性的值还原出来。我暂时没想到特别好的方式，用了一种效率低的方法。因为存属性用的是点号，例如obj、obj.f、obj.f.call，所以还原用到了eval()方法，所以代码效率可能有点低，不过运行正常，也算圆了我的一大遗憾了！！！

如果您有什么好的方法，可以讨论。如有错误，请不吝指正。