第 6 题：请分别用深度优先和广度优先实现一个拷贝函数？

Question

第 6 题：请分别用深度优先和广度优先实现一个拷贝函数？

atheist1 opened this issue 7 years ago · 51 comments

话不多说直接放代码
发现了比较多的错误，但由于最近工作有点忙，一直没来得及纠正

更改(0226)

// 工具函数
let _toString = Object.prototype.toString
let map = {
  array: 'Array',
  object: 'Object',
  function: 'Function',
  string: 'String',
  null: 'Null',
  undefined: 'Undefined',
  boolean: 'Boolean',
  number: 'Number'
}
let getType = (item) => {
  return _toString.call(item).slice(8, -1)
}
let isTypeOf = (item, type) => {
  return map[type] && map[type] === getType(item)
}

深复制深度优先遍历

let DFSdeepClone = (obj, visitedArr = []) => {
  let _obj = {}
  if (isTypeOf(obj, 'array') || isTypeOf(obj, 'object')) {
    let index = visitedArr.indexOf(obj)
    _obj = isTypeOf(obj, 'array') ? [] : {}
    if (~index) { // 判断环状数据
      _obj = visitedArr[index]
    } else {
      visitedArr.push(obj)
      for (let item in obj) {
        _obj[item] = DFSdeepClone(obj[item], visitedArr)
      }
    }
  } else if (isTypeOf(obj, 'function')) {
    _obj = eval('(' + obj.toString() + ')');
  } else {
    _obj = obj
  }
  return _obj
}

广度优先遍历

let BFSdeepClone = (obj) => {
    let origin = [obj],
      copyObj = {},
      copy = [copyObj]
      // 去除环状数据
    let visitedQueue = [],
      visitedCopyQueue = []
    while (origin.length > 0) {
      let items = origin.shift(),
        _obj = copy.shift()
      visitedQueue.push(items)
      if (isTypeOf(items, 'object') || isTypeOf(items, 'array')) {
        for (let item in items) {
          let val = items[item]
          if (isTypeOf(val, 'object')) {
            let index = visitedQueue.indexOf(val)
            if (!~index) {
              _obj[item] = {}
                //下次while循环使用给空对象提供数据
              origin.push(val)
                // 推入引用对象
              copy.push(_obj[item])
            } else {
              _obj[item] = visitedCopyQueue[index]
              visitedQueue.push(_obj)
            }
          } else if (isTypeOf(val, 'array')) {
            // 数组类型在这里创建了一个空数组
            _obj[item] = []
            origin.push(val)
            copy.push(_obj[item])
          } else if (isTypeOf(val, 'function')) {
            _obj[item] = eval('(' + val.toString() + ')');
          } else {
            _obj[item] = val
          }
        }
        // 将已经处理过的对象数据推入数组 给环状数据使用
        visitedCopyQueue.push(_obj)
      } else if (isTypeOf(items, 'function')) {
        copyObj = eval('(' + items.toString() + ')');
      } else {
        copyObj = obj
      }
    }
  return copyObj
}

测试

/**测试数据 */
// 输入 字符串String
// 预期输出String
let str = 'String'
var strCopy = DFSdeepClone(str)
var strCopy1 = BFSdeepClone(str)
console.log(strCopy, strCopy1) // String String 测试通过
// 输入 数字 -1980
// 预期输出数字 -1980
let num = -1980
var numCopy = DFSdeepClone(num)
var numCopy1 = BFSdeepClone(num)
console.log(numCopy, numCopy1) // -1980 -1980 测试通过
// 输入bool类型
// 预期输出bool类型
let bool = false
var boolCopy = DFSdeepClone(bool)
var boolCopy1 = BFSdeepClone(bool)
console.log(boolCopy, boolCopy1) //false false 测试通过
// 输入 null
// 预期输出 null
let nul = null
var nulCopy = DFSdeepClone(nul)
var nulCopy1 = BFSdeepClone(nul)
console.log(nulCopy, nulCopy1) //null null 测试通过

// 输入undefined
// 预期输出undefined
let und = undefined
var undCopy = DFSdeepClone(und)
var undCopy1 = BFSdeepClone(und)
console.log(undCopy, undCopy1) //undefined undefined 测试通过
  //输入引用类型obj
let obj = {
  a: 1,
  b: () => console.log(1),
  c: {
    d: 3,
    e: 4
  },
  f: [1, 2],
  und: undefined,
  nul: null
}
var objCopy = DFSdeepClone(obj)
var objCopy1 = BFSdeepClone(obj)
console.log(objCopy === objCopy1) // 对象类型判断 false 测试通过
console.log(obj.c === objCopy.c) // 对象类型判断 false 测试通过
console.log(obj.c === objCopy1.c) // 对象类型判断 false 测试通过
console.log(obj.b === objCopy1.b) // 函数类型判断 false 测试通过
console.log(obj.b === objCopy.b) // 函数类型判断 false 测试通过
console.log(obj.f === objCopy.f) // 数组类型判断 false 测试通过
console.log(obj.f === objCopy1.f) // 数组类型判断 false 测试通过
console.log(obj.nul, obj.und) // 输出null，undefined 测试通过

// 输入环状数据
// 预期不爆栈且深度复制
let circleObj = {
  foo: {
    name: function() {
      console.log(1)
    },
    bar: {
      name: 'bar',
      baz: {
        name: 'baz',
        aChild: null //待会让它指向obj.foo
      }
    }
  }
}
circleObj.foo.bar.baz.aChild = circleObj.foo
var circleObjCopy = DFSdeepClone(circleObj)
var circleObjCopy1 = BFSdeepClone(circleObj)
console.log(circleObjCopy, circleObjCopy1) // 测试通过?

ps

关于深浅拷贝的问题博主已经在他的git上有文章说过了，我就不做多的叙述
这两个方法我认为主要区别在于对于深层次以及环状数据，用深度优先遍历递归去做容易爆栈，广度优先遍历我对环状数据进行了处理，已经存在过的对象会存在数组中，下次直接赋值即可，无需继续遍历
如果出现问题欢迎讨论指出

Answer 1 · 2019-02-18T07:11:20.000Z

@atheist1 老哥你代码最好添加代码高亮一下，这样阅读感很差。

Answer 2 · 2019-02-19T03:01:01.000Z

笔误：
map = {
number: 'Number'
}

Answer 3 · 2019-02-21T07:03:29.000Z

DFSdeepClone 方法有问题吧字符串 clone 出来不久变数组了
浏览器console 实验一下就错了

Answer 4 · 2019-02-22T04:32:05.000Z

数值赋值本身就是复制，clone的时候需要复制的是array, object和function，这个代码里并没有针对function成员的复制。

Answer 5 · 2019-02-25T04:07:16.000Z

DFS没有对环状结构进行处理~

Answer 6 · 2019-02-26T02:39:44.000Z

顺便说明下，这里我对es6的symbol数据以及构造函数的拷贝都没做处理，想要了解的可以看大佬的
这篇文章【进阶4-4期】Lodash是如何实现深拷贝的

Answer 7 · 2019-02-26T15:19:08.000Z

DFSdeepClone = (obj, visitedArr = []) ,这里visitedArr如果传参的话，子层的属性不能和同层的属性做比较。只有同层的环能检测出来。
let b = {haha: 'haha'} let a = { a: {b: b}, c: {b: b} } const rs = DFSdeepClone(a) console.log(rs.a.b === rs.c.b) // false console.log(a.a.b === a.c.b) // true

Answer 8 · 2019-03-02T06:59:42.000Z

我只深拷贝了 Object, Array，其他的非基本类型都是浅拷贝（如果处理Set什么的就太复杂了，题目用意应该是考察遍历树和重复引用吧）

DFS用常规的递归问题不大，需要注意下重复引用的问题，不用递归的话就用栈

BFS就用队列，整体代码倒是差不多

// 如果是对象/数组，返回一个空的对象/数组，
// 都不是的话直接返回原对象
// 判断返回的对象和原有对象是否相同就可以知道是否需要继续深拷贝
// 处理其他的数据类型的话就在这里加判断
function getEmpty(o){
	if(Object.prototype.toString.call(o) === '[object Object]'){
		return {};
	}
	if(Object.prototype.toString.call(o) === '[object Array]'){
		return [];
	}
	return o;
}

function deepCopyBFS(origin){
	let queue = [];
	let map = new Map(); // 记录出现过的对象，用于处理环

	let target = getEmpty(origin);
	if(target !== origin){
		queue.push([origin, target]);
		map.set(origin, target);
	}

	while(queue.length){
		let [ori, tar] = queue.shift();
		for(let key in ori){
			// 处理环状
			if(map.get(ori[key])){
				tar[key] = map.get(ori[key]);
				continue;
			}

			tar[key] = getEmpty(ori[key]);
			if(tar[key] !== ori[key]){
				queue.push([ori[key], tar[key]]);
				map.set(ori[key], tar[key]);
			}
		}
	}

	return target;
}

function deepCopyDFS(origin){
	let stack = [];
	let map = new Map(); // 记录出现过的对象，用于处理环

	let target = getEmpty(origin);
	if(target !== origin){
		stack.push([origin, target]);
		map.set(origin, target);
	}

	while(stack.length){
		let [ori, tar] = stack.pop();
		for(let key in ori){
			// 处理环状
			if(map.get(ori[key])){
				tar[key] = map.get(ori[key]);
				continue;
			}

			tar[key] = getEmpty(ori[key]);
			if(tar[key] !== ori[key]){
				stack.push([ori[key], tar[key]]);
				map.set(ori[key], tar[key]);
			}
		}
	}

	return target;
}

// test
[deepCopyBFS, deepCopyDFS].forEach(deepCopy=>{
	console.log(deepCopy({a:1}));
	console.log(deepCopy([1,2,{a:[3,4]}]))
	console.log(deepCopy(function(){return 1;}))
	console.log(deepCopy({
		x:function(){
			return "x";
		},
		val:3,
		arr: [
			1,
			{test:1}
		]
	}))

	let circle = {};
	circle.child = circle;
	console.log(deepCopy(circle));
})

Answer 9 · 2019-03-06T02:40:38.000Z

var o = {m: 2}
var obj = {
a: {b:o},
e: o
}
广度优先测试失败

Answer 10 · 2019-03-06T06:13:49.000Z

var o = {m: 2}
var obj = {
a: {b:o},
e: o
}
广度优先测试失败

公司gayhub怎么老是炸，感谢提醒，已更新，在处理环状数据时我将visitedCopyQueue错用成visitedQueue了，导致上一次使用的数据是存在visitedQueue里的引用导致深复制失败

Answer 11 · 2019-03-29T08:42:17.000Z

笔试时会不会纸上手写深度拷贝

Answer 12 · 2019-04-07T14:39:37.000Z

代码有点难读

Answer 13 · 2019-04-11T06:13:53.000Z

    function deepClone(obj){
        var temp = {};
        for(var key in obj){
            if(obj.hasOwnProperty(key)){
                temp[key] = typeof obj[key] === "object" ? deepClone(obj[key]) : obj[key];
            }
        }
        return temp;
    }

Answer 14 · 2019-07-09T18:57:24.000Z

这应该是深度优先拷贝吧

let cloneObject = function(source) {
    let target = {};
    for (key in source) {
        if (source.hasOwnProperty(key)) {
            let itemType = Object.prototype.toString.call(source[key]).slice(8, -1);
            switch (itemType) {
                case "Object":
                    target[key] = cloneObject(source[key]);
                    break;
                case "Array":
                    let temp = [];
                    for (let i = 0; i < source[key].length; i++) {
                        temp.push(source[key][i]);
                    }
                    target[key] = temp;
                    break;
                default:
                    target[key] = source[key];

            }
        }
    }
    return target;
}

Answer 15 · 2019-07-11T09:33:19.000Z

/**
 * @Author nzq
 * @Date 2019/5/28
 * @Description:
 * @Param:
 * @Return:
 */

const type = Object.prototype.toString;

function getType(obj) {
  const map = {
    '[object Boolean]'         : 'boolean',
    '[object Number]'          : 'number',
    '[object String]'          : 'string',
    '[object Null]'            : 'null',
    '[object Undefined]'       : 'undefined',
    '[object Symbol]'          : 'symbol',
    '[object Object]'          : 'object',
    '[object Array]'           : 'array',
    '[object Function]'        : 'function',
    '[object Date]'            : 'date',
    '[object RegExp]'          : 'regExp',
    '[object HTMLDivElement]'  : 'dom',
  };

  return map[type.call(obj)];
}

/**
 * @Author nzq
 * @Date 2019/5/28
 * @Description: 递归
 *        注意 visitedQueue.push(target); createQueue.push(res); 的时机
 * @Param:
 * @Return:
 */
function deepClone(obj) {
  // visitedQueue 和 createQueue 的值一定要相互对应
  let visitedQueue = [],
    createQueue = [],
    visitedIdx = 0;

  return (function _clone (target) {
    let res = null,
    type = getType(target);

    visitedIdx = visitedQueue.indexOf(target);

    // 访问过
    if ( visitedIdx !== -1) {
      res = createQueue[visitedIdx]; // 获取对应的 createQueue 中的值
    }
    // 没访问过
    else {
      switch(type) {
        case 'object': {
          res = {};
          visitedQueue.push(target);
          createQueue.push(res);

          // 遍历
          for (let key in target) {
           res[key] = _clone(target[key]);
          }
          break;
        }
        case 'array': {
          res = [];
          visitedQueue.push(target);
          createQueue.push(res);

          // 遍历
          for (let idx in target) {
            res[idx] = _clone(target[key]);
          }
          break;
        }
        case 'dom': {
          res = target.cloneNode(true);
          break;
        }
        default : {
          res = target;
        }
      }
    }
    return res;
  })(obj)
}

Answer 16 · 2019-07-14T12:33:29.000Z

请问能不能解释一下环状结构数据呢？

Answer 17 · 2019-07-16T17:29:31.000Z

请问能不能解释一下环状结构数据呢？

解决深拷贝中的环问题

Answer 18 · 2019-07-22T14:17:06.000Z

@atheist1
您好。我刚刚查看您的广度优先遍历 BFSdeepClone 函数。while递归中没有判断array的环状数据。

您可以将下面这段代码添加到函数执行之前，来复现该问题

let a = [1,2,3,4]
let b = a
a.push(b)
obj.a = a;

Answer 19 · 2019-07-22T14:21:01.000Z

谢谢指点，我会尝试下的，感谢------------------ 原始邮件 ------------------ 发件人: "qinchenguang"<notifications@github.com> 发送时间: 2019年7月22日(星期一) 晚上10:18 收件人: "Advanced-Frontend/Daily-Interview-Question"<Daily-Interview-Question@noreply.github.com>; 抄送: "ZJINH"<2665229856@QQ.COM>;"Comment"<comment@noreply.github.com>; 主题: Re: [Advanced-Frontend/Daily-Interview-Question] 第 6 题：请分别用深度优先**和广度优先**实现一个拷贝函数？ (#10) @atheist1 您好。我刚刚查看您的广度优先遍历 BFSdeepClone 函数。while递归中没有判断array的环装数据。您可以将下面这段代码添加到函数执行之前，来复现该问题 let a = [1,2,3,4] let b = a a.push(b) obj.a = a; — You are receiving this because you commented. Reply to this email directly, view it on GitHub, or mute the thread.

Answer 20 · 2019-07-22T14:36:29.000Z

@atheist1
因为刚刚发现的问题。我又一次尝试了下。深度优先遍历 DFSdeepClone 函数中 visitedArr 数组存放的都是原数组的引用类型。这会导致环状数据出现问题。

如下代码
let a = [1,2,3,4]
let b = a
a.push(b)
obj.a = a;
var objCopy = DFSdeepClone(obj)
obj.a[2] = 2;
objCopy 克隆对象中的a数组第二次引用会和源数据保持一致

Answer 21 · 2019-07-23T09:09:45.000Z

深度优先算法深拷贝有很多就不写了
广度优先算法深拷贝，实现了下，暂时没发现问题

// 广度优先法
function deepClone(obj, tempNodes=[]) {
    if (obj === null) return null;
    if (typeof obj !== "object") return obj;
    if (obj.constructor === Date) return new Date(obj);
    
    const newObj = new obj.constructor(); 
    
    for (let key in obj) {
      if (obj.hasOwnProperty(key)) { 
        const value = obj[key];
        
        if (typeof value === "object") {
          newObj[key] = null;
          tempNodes.push([newObj, key, value]);
        } else {
          newObj[key] = value;
        }
      }
    }
    
    while (tempNodes.length > 0) {
      let currentNodes = tempNodes.shift();

      currentNodes[0][currentNodes[1]] = deepClone(currentNodes[2], tempNodes);
    }
    
    return newObj;
  }

Answer 22 · 2019-08-01T07:26:47.000Z

深度优先算法深拷贝有很多就不写了
广度优先算法深拷贝，实现了下，暂时没发现问题

// 广度优先法
function deepClone(obj, tempNodes=[]) {
    if (obj === null) return null;
    if (typeof obj !== "object") return obj;
    if (obj.constructor === Date) return new Date(obj);
    
    const newObj = new obj.constructor(); 
    
    for (let key in obj) {
      if (obj.hasOwnProperty(key)) { 
        const value = obj[key];
        
        if (typeof value === "object") {
          newObj[key] = null;
          tempNodes.push([newObj, key, value]);
        } else {
          newObj[key] = value;
        }
      }
    }
    
    while (tempNodes.length > 0) {
      let currentNodes = tempNodes.shift();

      currentNodes[0][currentNodes[1]] = deepClone(currentNodes[2], tempNodes);
    }
    
    return newObj;
  }

这好像还是深度遍历

Answer 23 · 2019-08-02T11:39:35.000Z

深度优先算法深拷贝有很多就不写了
广度优先算法深拷贝，实现了下，暂时没发现问题

// 广度优先法
function deepClone(obj, tempNodes=[]) {
    if (obj === null) return null;
    if (typeof obj !== "object") return obj;
    if (obj.constructor === Date) return new Date(obj);
    
    const newObj = new obj.constructor(); 
    
    for (let key in obj) {
      if (obj.hasOwnProperty(key)) { 
        const value = obj[key];
        
        if (typeof value === "object") {
          newObj[key] = null;
          tempNodes.push([newObj, key, value]);
        } else {
          newObj[key] = value;
        }
      }
    }
    
    while (tempNodes.length > 0) {
      let currentNodes = tempNodes.shift();

      currentNodes[0][currentNodes[1]] = deepClone(currentNodes[2], tempNodes);
    }
    
    return newObj;
  }

这好像还是深度遍历

const test = {a: {b: {v: 1}}, c: {f: 2}, h: new Date()};
你可以再for循环内部打印key，看看路径

Answer 24 · 2019-08-12T09:25:48.000Z

if (~index) 中的~是啥意思

Answer 25 · 2019-08-14T03:47:13.000Z

深度优先搜索的拷贝函数，没有考虑一些复杂的对象。

function deepTraversal(target) {
    // 使用WeakSet防止循环引用
    let weakSet = new WeakSet();

    function realDeepTraversal(target) {
      if (target !== null && target !== undefined) {
        if (typeof target === 'object' && !weakSet.has(target)) {
          weakSet.add(target);

          if (Array.isArray(target)) {
            return target.map(realDeepTraversal);
          } else {
            return Object.keys(target).reduce((result, key) => ({
              ...result,
              [key]: realDeepTraversal(target[key])
            }), {});
          }
        } else {
          return target;
        }
      }
    }

    return realDeepTraversal(target);
  }

Answer 26 · 2019-08-14T13:24:22.000Z

@atheist1 广度优先拷贝存在一个问题：

最外层是数组时，会变成对象

Answer 27 · 2019-08-29T07:51:45.000Z

容我抖个机灵，深度优先json.parse(json.stringify(obj))

Answer 28 · 2019-08-29T08:25:33.000Z

容我抖个机灵，深度优先json.parse(json.stringify(obj))

我自己用的这个

Answer 29 · 2019-09-09T03:17:50.000Z

      visitedArr.push(obj)

@atheist1

这边不应该是放入的原始值吧，应该是放入深拷贝之后的值_obj

circleObjCopy.foo.bar.baz.aChild === circleObjCopy.foo //false

测试用例最后一个，拷贝后的结果的循环引用不正确。

Answer 30 · 2019-10-08T13:27:07.000Z

@atheist1
DFSdeepClone中通过if（～index）判断引用类型是否clone过不妥，直接判断index > -1不更好吗

Answer 31 · 2019-10-09T10:19:54.000Z

谁能解释一下“环状数据”是什么意思？我理解为循环引用

Answer 32 · 2019-10-09T10:22:03.000Z

容我抖个机灵，深度优先json.parse(json.stringify(obj))

这种不能满足所有场景，碰到函数，正则表达式，Symbol...就歇菜了

Answer 33 · 2019-12-30T08:30:27.000Z

// 判断正则、日期函数等
if(value instanceof RegExp){return new RegExp(value)}
if(value instanceof Date){return new Date(value)}

Answer 34 · 2020-01-31T07:41:25.000Z

看不懂大佬的广度优先遍历

Answer 35 · 2020-02-10T11:05:25.000Z

if (~index) 中的~是啥意思

位运算按位非
对任一数值 x 进行按位非操作的结果为 -(x + 1)。例如，~5 结果为 -6。
用在上面的意思就是

if (~-1) // 位运算值为 0，隐式转换后为：false
if (~0) // 位运算值为 -1，隐式转换后为：true
if (~1) // 位运算值为 -2，隐式转换后为：true

Answer 36 · 2020-02-17T08:08:59.000Z

@WozHuang 你的方法好像没有考虑函数，函数拷贝过来的还是原函数的指针，应该同博主一样再做一层判断，eval赋值过来吧？

Answer 37 · 2020-02-17T09:33:30.000Z

@panzhengtao 是的，环状数据指的就是子属性又去引用了父属性，导致了循环引用。

Answer 38 · 2020-02-20T09:50:48.000Z

/**
 * 对象深拷贝（深度优先遍历）
 * 着重点
 * 1. 注意拷贝源可能是对象或者是数组
 * 2. 可能会出现循环引用的问题，用哈希表或数组来检测并正常退出，否则会调用栈溢出
 * 3. 注意对象的key可能是symbol，用for in或者Object.keys遍历不出来，可以用Object.getOwnPropertySymbols获取
 * @param originObj
 * @return 拷贝后的结果
 */

function deepCopy(originObj) {
  return helper(originObj, new WeakSet())
}

/**
 *
 * @param originObj
 * @param appearSet 主要是用来检测循环引用的WeakSet
 * @return {*}
 */
function helper(originObj, appearSet) {
  // 深度优先
  if (typeof originObj !== 'object') {
    // 传入非对象，直接复制返回（基本类型复制值，引用类型复制引用）
    return originObj
  }

  if (appearSet.has(originObj)) {
    // 检测到循环引用，终止
    return null
  }

   // 添加
  appearSet.add(originObj)

  let obj

  if (Array.isArray(originObj)) {
    // 数组
    obj = []

    for (let i = 0; i < originObj.length; i++) {
      obj[i] = helper(originObj[i], appearSet)
    }
  } else {
    // 对象
    obj = {}

    // 考虑上symbol
    const keyList = [...Object.getOwnPropertySymbols(originObj), ...Object.keys(originObj)]
    for (let key of keyList) {
      // 深度优先
      obj[key] = helper(originObj[key], appearSet)
    }
  }
  // 删除
  appearSet.delete(originObj)
  // 返回
  return obj
}

Answer 39 · 2020-03-03T02:25:09.000Z

@atheist1 你的深度优先算法中，处理循环引用的流程感觉不太对，因为复制出来的结果与原对象的引用是同一个，即:
// 现在返回true，深拷贝按理应该是false，
circleObjCopy.foo.bar.baz.aChild === circleObj.foo
也许按 @WozHuang 的做法才正确，因为期望值应该是:
// 应该返回true
circleObjCopy.foo.bar.baz.aChild === circleObjCopy.foo

Answer 40 · 2020-03-13T10:16:15.000Z

广度优先遍历深拷贝，只考虑了Date这特殊对象, 其余特殊对象判断方法一样（已自测一部分数据，可能有些未覆盖到，望指出~）

function bfsDeepClone(obj) {
    if (obj === null) return null;
    if (typeof obj !== 'object') return null;
    if (obj.constructor === Date) return new Date(obj);
    const newObj = new obj.constructor();
    // 使用队列进行广度遍历
    const queue = [[newObj, obj]];
    while (queue.length > 0) {
        // target: 需要拷贝的目标对象，next: 被拷贝源对象
        const [target, source] = queue.shift();
        // 遍历源对象的每个属性
        for (let key in source) {
            if (source.hasOwnProperty(key)) {
                // 不是对象, 直接拷贝 Notes: 需要注意Symbol
                if (typeof source[key] !== 'object') {
                    target[key] = source[key];
                } else if (source[key].constructor === Date) {
                    // 如果是Date对象直接拷贝一个新的Date
                    target[key] = new Date(source[key]);
                } else {
                    // 如果属性是对象, 将其加入队列中继续拷贝
                    target[key] = new source[key].constructor();
                    queue.push([target[key], source[key]]);
                } 
            }
        }
    }
    return newObj
}

Answer 41 · 2020-04-05T15:39:45.000Z

话不多说直接放代码
发现了比较多的错误，但由于最近工作有点忙，一直没来得及纠正

更改(0226)

// 工具函数
let _toString = Object.prototype.toString
let map = {
  array: 'Array',
  object: 'Object',
  function: 'Function',
  string: 'String',
  null: 'Null',
  undefined: 'Undefined',
  boolean: 'Boolean',
  number: 'Number'
}
let getType = (item) => {
  return _toString.call(item).slice(8, -1)
}
let isTypeOf = (item, type) => {
  return map[type] && map[type] === getType(item)
}

深复制深度优先遍历

let DFSdeepClone = (obj, visitedArr = []) => {
  let _obj = {}
  if (isTypeOf(obj, 'array') || isTypeOf(obj, 'object')) {
    let index = visitedArr.indexOf(obj)
    _obj = isTypeOf(obj, 'array') ? [] : {}
    if (~index) { // 判断环状数据
      _obj = visitedArr[index]
    } else {
      visitedArr.push(obj)
      for (let item in obj) {
        _obj[item] = DFSdeepClone(obj[item], visitedArr)
      }
    }
  } else if (isTypeOf(obj, 'function')) {
    _obj = eval('(' + obj.toString() + ')');
  } else {
    _obj = obj
  }
  return _obj
}

广度优先遍历

let BFSdeepClone = (obj) => {
    let origin = [obj],
      copyObj = {},
      copy = [copyObj]
      // 去除环状数据
    let visitedQueue = [],
      visitedCopyQueue = []
    while (origin.length > 0) {
      let items = origin.shift(),
        _obj = copy.shift()
      visitedQueue.push(items)
      if (isTypeOf(items, 'object') || isTypeOf(items, 'array')) {
        for (let item in items) {
          let val = items[item]
          if (isTypeOf(val, 'object')) {
            let index = visitedQueue.indexOf(val)
            if (!~index) {
              _obj[item] = {}
                //下次while循环使用给空对象提供数据
              origin.push(val)
                // 推入引用对象
              copy.push(_obj[item])
            } else {
              _obj[item] = visitedCopyQueue[index]
              visitedQueue.push(_obj)
            }
          } else if (isTypeOf(val, 'array')) {
            // 数组类型在这里创建了一个空数组
            _obj[item] = []
            origin.push(val)
            copy.push(_obj[item])
          } else if (isTypeOf(val, 'function')) {
            _obj[item] = eval('(' + val.toString() + ')');
          } else {
            _obj[item] = val
          }
        }
        // 将已经处理过的对象数据推入数组 给环状数据使用
        visitedCopyQueue.push(_obj)
      } else if (isTypeOf(items, 'function')) {
        copyObj = eval('(' + items.toString() + ')');
      } else {
        copyObj = obj
      }
    }
  return copyObj
}

测试

/**测试数据 */
// 输入 字符串String
// 预期输出String
let str = 'String'
var strCopy = DFSdeepClone(str)
var strCopy1 = BFSdeepClone(str)
console.log(strCopy, strCopy1) // String String 测试通过
// 输入 数字 -1980
// 预期输出数字 -1980
let num = -1980
var numCopy = DFSdeepClone(num)
var numCopy1 = BFSdeepClone(num)
console.log(numCopy, numCopy1) // -1980 -1980 测试通过
// 输入bool类型
// 预期输出bool类型
let bool = false
var boolCopy = DFSdeepClone(bool)
var boolCopy1 = BFSdeepClone(bool)
console.log(boolCopy, boolCopy1) //false false 测试通过
// 输入 null
// 预期输出 null
let nul = null
var nulCopy = DFSdeepClone(nul)
var nulCopy1 = BFSdeepClone(nul)
console.log(nulCopy, nulCopy1) //null null 测试通过

// 输入undefined
// 预期输出undefined
let und = undefined
var undCopy = DFSdeepClone(und)
var undCopy1 = BFSdeepClone(und)
console.log(undCopy, undCopy1) //undefined undefined 测试通过
  //输入引用类型obj
let obj = {
  a: 1,
  b: () => console.log(1),
  c: {
    d: 3,
    e: 4
  },
  f: [1, 2],
  und: undefined,
  nul: null
}
var objCopy = DFSdeepClone(obj)
var objCopy1 = BFSdeepClone(obj)
console.log(objCopy === objCopy1) // 对象类型判断 false 测试通过
console.log(obj.c === objCopy.c) // 对象类型判断 false 测试通过
console.log(obj.c === objCopy1.c) // 对象类型判断 false 测试通过
console.log(obj.b === objCopy1.b) // 函数类型判断 false 测试通过
console.log(obj.b === objCopy.b) // 函数类型判断 false 测试通过
console.log(obj.f === objCopy.f) // 数组类型判断 false 测试通过
console.log(obj.f === objCopy1.f) // 数组类型判断 false 测试通过
console.log(obj.nul, obj.und) // 输出null，undefined 测试通过

// 输入环状数据
// 预期不爆栈且深度复制
let circleObj = {
  foo: {
    name: function() {
      console.log(1)
    },
    bar: {
      name: 'bar',
      baz: {
        name: 'baz',
        aChild: null //待会让它指向obj.foo
      }
    }
  }
}
circleObj.foo.bar.baz.aChild = circleObj.foo
var circleObjCopy = DFSdeepClone(circleObj)
var circleObjCopy1 = BFSdeepClone(circleObj)
console.log(circleObjCopy, circleObjCopy1) // 测试通过?

ps

关于深浅拷贝的问题博主已经在他的git上有文章说过了，我就不做多的叙述
这两个方法我认为主要区别在于对于深层次以及环状数据，用深度优先遍历递归去做容易爆栈，广度优先遍历我对环状数据进行了处理，已经存在过的对象会存在数组中，下次直接赋值即可，无需继续遍历
如果出现问题欢迎讨论指出

嗯～原谅我是杠精，以Symbol为键的对象拷贝时会忽略该键的拷贝。

Answer 42 · 2020-07-11T09:39:59.000Z

"use strict"
// 深度优先
function deepClone(source, hash = new WeakMap()) {
    if (typeof source != "object" || source == null) return source; // 非对象或空对象返回自身
    if (hash.has(source)) {
        return hash.get(source); // 若表中存在这个键，则返回该键对应的值，解决克隆时循环引用的问题
    }
    let target = Array.isArray(source) ? [] : {}; // 识别是对象还是数组
    hash.set(source, target);
    Reflect.ownKeys(source).forEach((key) => { // 这里用Reflect.ownKeys而不用for...in迭代是因为Reflect.ownKeys可以访问Symbol属性
        /** 
         * 1. 如果使用for...in会把原型链上的其他属性也迭代出来，那么就要多层判断Object.prototype.hasOwnProperty.call(source, key)，
         * 防止得到属于原型链而不属于source自身的属性，这里使用Reflect.ownKeys，因此可以省去判断
         * 2. 不直接用source.hasOwnProperty(key)是因为如果source=Object.create(null),
         那么source就没有继承Object的原型，使得source的hasOwnProperty方法为undefinde
         */
        if (typeof source[key] == "object" && source[key] != null) {
            target[key] = deepClone(source[key], hash);
        } else {
            target[key] = source[key];
        }
    });
    return target;
}

// 广度优先
function deepClone2(source) {
    if (typeof source != "object" || source == null) return source; // 非对象或空对象返回自身
    let target = Array.isArray(source) ? [] : {}; // 识别是对象还是数组
    let hash = new WeakMap();
    // 栈
    let loopList = [{
        target: target,
        source: source
    }];
    hash.set(source, target); // 注意这句不要漏，下面还有一个hash.set
    while (loopList.length) {
        // 广度优先
        let data = loopList.pop();
        let node = data.source;
        let target = data.target;
        Reflect.ownKeys(node).some((key) => { // 这里用Reflect.ownKeys而不用for...in迭代是因为Reflect.ownKeys可以访问Symbol属性
            if (typeof node[key] == "object" && node[key] != null) {
                if (hash.has(node[key])) {
                    target[key] = hash.get(node[key]);
                } else {
                    target[key] = Array.isArray(node[key]) ? [] : {}; // 识别是对象还是数组
                    loopList.push({ target: target[key], source: node[key] });
                    hash.set(node[key], target[key]);
                }
            } else {
                target[key] = node[key];
            }
        });
    }
    return target;
}


// 测试用例
var a = {
    name: "muyiy",
    book: {
        title: "You Don't Know JS",
        price: "45"
    },
    a1: undefined,
    a2: null,
    a3: 123,
    Symbols: Symbol("test")
}

a.circleRef = a;

let test2 = deepClone2(a);
// let test2 = deepClone(a);
console.log(a, test2);

Answer 43 · 2020-07-15T10:34:03.000Z

Answer 44 · 2020-07-16T05:59:34.000Z

高赞默写

function getCopy (obj) {
	if (Object.prototype.toString.call(obj) == '[Object Object]') {
		return {};
	}
	if (Object.prototype.toString.call(obj) == '[Object Array]') {
		return [];
	}
	return obj;
}
function dfs(obj) {
	let stack = [];
	let ret = getCopy(obj);
	if (ret !== obj) {
		stack.push([obj, ret]);
	}
	while (stack.length) {
		let [origin, target] = stack.pop();
		for (let key in origin) {
			if (origin.hasOwnProperty(key)) {
				let tmpOrigin = origin[key];
				let tmpTarget = getCopy(tmpOrigin);
				target[key] = tmpTarget;
				if (tmpOrigin !== tmpTarget) {
					stack.push([tmpOrigin, tmpTarget])
				}
			}
		}
	}
	return ret;
}

function bfs(obj) {
	let array = [];
	let ret = getCopy(obj);
	if (ret !== obj) {
		array.push([obj, ret]);
	}
	while(array.length) {
		let [origin, target] = array.shift();
		for (let key in tmpOrigin) {
			if (tmpOrigin.hasOwnProperty(key)) {
				let tmpOrigin = target[key];
				let tmpTarget = getCopy(tmpOrigin);
				target[key] = tmpTarget;
				if (tmpOrigin !== tmpTarget) {
					array.push([tmpOrigin, tmpTarget]);
				}
			}
		}
	}
	return ret;
} 
// 递归版 dfs  能循环的就能递归... 有人爱问这个
function dfs(obj) {
	let ret = getCopy(obj);
	if (ret !== obj) {
		for (let key in obj) {
			if (obj.hasOwnProperty(key)) {
				let tmpOrigin = obj[key];
				let tmpTarget = getCopy(tmpOrigin);

				if (tmpTarget !== tmpOrigin) {
					ret[key] = dfs(tmpOrigin);
				} else {
					ret[key] = tmpTarget;
				}

			}
		}
	}
	return ret;
}

Answer 45 · 2021-01-13T14:57:56.000Z

引用类型只考虑Array，Object

function DFSCopy(old) {
  if (typeof old !== 'object') return old;
  const isArray = Array.isArray(old);
  const newObj = isArray ? [] : {};
  if (isArray) {
    for (let i = 0; i < old.length; i++) {
      newObj[i] = deepCopy(old[i]);
    }
  } else {
    for (let i in old) {
      newObj[i] = deepCopy(old[i]);
    }
  }
  console.log(newObj);
  return newObj;
}

function BFScopy(a) {
  const queue = [];
  const b = new a.constructor();
  queue.push([a, b]);
  while (queue.length) {
    const [oldObj, newObj] = queue.shift();
    for (let i in oldObj) {
      if (typeof oldObj[i] === 'object') {
        newObj[i] = new oldObj[i].constructor();
        queue.push([oldObj[i], newObj[i]]);
      } else {
        newObj[i] = oldObj[i];
      }
    }
  }
  return b;
}

Answer 46 · 2021-02-22T15:24:36.000Z

function dfsCopy(src, copy={}) {
	Object.keys(src).forEach((key) => {
		// 需要复制其他类型请额外加判断
		copy[key] = typeof src[key] === 'object' && src !== src[key] && src[key] !== null ? dfsCopy(src[key]) : copy[key] = src[key]
	})
	return copy
}

function bfsCopy(src, copy={}, collect=[]) {
	Object.keys(src).forEach((key) => {
		// 需要复制其他类型请额外加判断
		if (typeof src[key] === 'object' && src !== src[key] && src[key] !== null) {
			collect.push({ src: src[key], copy: {} })
			copy[key] = collect[collect.length - 1].copy
		} else {
			copy[key] = src[key]
		}
	})
	if (collect.length !== 0) {
		let { src, copy } = collect.shift()
		bfsCopy(src, copy, collect)
	}
	return copy
}

Answer 47 · 2021-02-26T10:09:37.000Z

话不多说直接放代码
发现了比较多的错误，但由于最近工作有点忙，一直没来得及纠正

更改(0226)

// 工具函数
let _toString = Object.prototype.toString
let map = {
  array: 'Array',
  object: 'Object',
  function: 'Function',
  string: 'String',
  null: 'Null',
  undefined: 'Undefined',
  boolean: 'Boolean',
  number: 'Number'
}
let getType = (item) => {
  return _toString.call(item).slice(8, -1)
}
let isTypeOf = (item, type) => {
  return map[type] && map[type] === getType(item)
}

深复制深度优先遍历

let DFSdeepClone = (obj, visitedArr = []) => {
  let _obj = {}
  if (isTypeOf(obj, 'array') || isTypeOf(obj, 'object')) {
    let index = visitedArr.indexOf(obj)
    _obj = isTypeOf(obj, 'array') ? [] : {}
    if (~index) { // 判断环状数据
      _obj = visitedArr[index]
    } else {
      visitedArr.push(obj)
      for (let item in obj) {
        _obj[item] = DFSdeepClone(obj[item], visitedArr)
      }
    }
  } else if (isTypeOf(obj, 'function')) {
    _obj = eval('(' + obj.toString() + ')');
  } else {
    _obj = obj
  }
  return _obj
}

广度优先遍历

let BFSdeepClone = (obj) => {
    let origin = [obj],
      copyObj = {},
      copy = [copyObj]
      // 去除环状数据
    let visitedQueue = [],
      visitedCopyQueue = []
    while (origin.length > 0) {
      let items = origin.shift(),
        _obj = copy.shift()
      visitedQueue.push(items)
      if (isTypeOf(items, 'object') || isTypeOf(items, 'array')) {
        for (let item in items) {
          let val = items[item]
          if (isTypeOf(val, 'object')) {
            let index = visitedQueue.indexOf(val)
            if (!~index) {
              _obj[item] = {}
                //下次while循环使用给空对象提供数据
              origin.push(val)
                // 推入引用对象
              copy.push(_obj[item])
            } else {
              _obj[item] = visitedCopyQueue[index]
              visitedQueue.push(_obj)
            }
          } else if (isTypeOf(val, 'array')) {
            // 数组类型在这里创建了一个空数组
            _obj[item] = []
            origin.push(val)
            copy.push(_obj[item])
          } else if (isTypeOf(val, 'function')) {
            _obj[item] = eval('(' + val.toString() + ')');
          } else {
            _obj[item] = val
          }
        }
        // 将已经处理过的对象数据推入数组 给环状数据使用
        visitedCopyQueue.push(_obj)
      } else if (isTypeOf(items, 'function')) {
        copyObj = eval('(' + items.toString() + ')');
      } else {
        copyObj = obj
      }
    }
  return copyObj
}

测试

/**测试数据 */
// 输入 字符串String
// 预期输出String
let str = 'String'
var strCopy = DFSdeepClone(str)
var strCopy1 = BFSdeepClone(str)
console.log(strCopy, strCopy1) // String String 测试通过
// 输入 数字 -1980
// 预期输出数字 -1980
let num = -1980
var numCopy = DFSdeepClone(num)
var numCopy1 = BFSdeepClone(num)
console.log(numCopy, numCopy1) // -1980 -1980 测试通过
// 输入bool类型
// 预期输出bool类型
let bool = false
var boolCopy = DFSdeepClone(bool)
var boolCopy1 = BFSdeepClone(bool)
console.log(boolCopy, boolCopy1) //false false 测试通过
// 输入 null
// 预期输出 null
let nul = null
var nulCopy = DFSdeepClone(nul)
var nulCopy1 = BFSdeepClone(nul)
console.log(nulCopy, nulCopy1) //null null 测试通过

// 输入undefined
// 预期输出undefined
let und = undefined
var undCopy = DFSdeepClone(und)
var undCopy1 = BFSdeepClone(und)
console.log(undCopy, undCopy1) //undefined undefined 测试通过
  //输入引用类型obj
let obj = {
  a: 1,
  b: () => console.log(1),
  c: {
    d: 3,
    e: 4
  },
  f: [1, 2],
  und: undefined,
  nul: null
}
var objCopy = DFSdeepClone(obj)
var objCopy1 = BFSdeepClone(obj)
console.log(objCopy === objCopy1) // 对象类型判断 false 测试通过
console.log(obj.c === objCopy.c) // 对象类型判断 false 测试通过
console.log(obj.c === objCopy1.c) // 对象类型判断 false 测试通过
console.log(obj.b === objCopy1.b) // 函数类型判断 false 测试通过
console.log(obj.b === objCopy.b) // 函数类型判断 false 测试通过
console.log(obj.f === objCopy.f) // 数组类型判断 false 测试通过
console.log(obj.f === objCopy1.f) // 数组类型判断 false 测试通过
console.log(obj.nul, obj.und) // 输出null，undefined 测试通过

// 输入环状数据
// 预期不爆栈且深度复制
let circleObj = {
  foo: {
    name: function() {
      console.log(1)
    },
    bar: {
      name: 'bar',
      baz: {
        name: 'baz',
        aChild: null //待会让它指向obj.foo
      }
    }
  }
}
circleObj.foo.bar.baz.aChild = circleObj.foo
var circleObjCopy = DFSdeepClone(circleObj)
var circleObjCopy1 = BFSdeepClone(circleObj)
console.log(circleObjCopy, circleObjCopy1) // 测试通过?

ps

关于深浅拷贝的问题博主已经在他的git上有文章说过了，我就不做多的叙述
这两个方法我认为主要区别在于对于深层次以及环状数据，用深度优先遍历递归去做容易爆栈，广度优先遍历我对环状数据进行了处理，已经存在过的对象会存在数组中，下次直接赋值即可，无需继续遍历
如果出现问题欢迎讨论指出

补一个测试用例
··· js
var obj = {};
obj.target = obj;

你这写的函数根本通过不了，taget直接为undefined了

Answer 48 · 2021-03-08T07:15:20.000Z

我只深拷贝了 Object, Array，其他的非基本类型都是浅拷贝（如果处理Set什么的就太复杂了，题目用意应该是考察遍历树和重复引用吧）

DFS用常规的递归问题不大，需要注意下重复引用的问题，不用递归的话就用栈

BFS就用队列，整体代码倒是差不多

// 如果是对象/数组，返回一个空的对象/数组，
// 都不是的话直接返回原对象
// 判断返回的对象和原有对象是否相同就可以知道是否需要继续深拷贝
// 处理其他的数据类型的话就在这里加判断
function getEmpty(o){
	if(Object.prototype.toString.call(o) === '[object Object]'){
		return {};
	}
	if(Object.prototype.toString.call(o) === '[object Array]'){
		return [];
	}
	return o;
}

function deepCopyBFS(origin){
	let queue = [];
	let map = new Map(); // 记录出现过的对象，用于处理环

	let target = getEmpty(origin);
	if(target !== origin){
		queue.push([origin, target]);
		map.set(origin, target);
	}

	while(queue.length){
		let [ori, tar] = queue.shift();
		for(let key in ori){
			// 处理环状
			if(map.get(ori[key])){
				tar[key] = map.get(ori[key]);
				continue;
			}

			tar[key] = getEmpty(ori[key]);
			if(tar[key] !== ori[key]){
				queue.push([ori[key], tar[key]]);
				map.set(ori[key], tar[key]);
			}
		}
	}

	return target;
}

function deepCopyDFS(origin){
	let stack = [];
	let map = new Map(); // 记录出现过的对象，用于处理环

	let target = getEmpty(origin);
	if(target !== origin){
		stack.push([origin, target]);
		map.set(origin, target);
	}

	while(stack.length){
		let [ori, tar] = stack.pop();
		for(let key in ori){
			// 处理环状
			if(map.get(ori[key])){
				tar[key] = map.get(ori[key]);
				continue;
			}

			tar[key] = getEmpty(ori[key]);
			if(tar[key] !== ori[key]){
				stack.push([ori[key], tar[key]]);
				map.set(ori[key], tar[key]);
			}
		}
	}

	return target;
}

// test
[deepCopyBFS, deepCopyDFS].forEach(deepCopy=>{
	console.log(deepCopy({a:1}));
	console.log(deepCopy([1,2,{a:[3,4]}]))
	console.log(deepCopy(function(){return 1;}))
	console.log(deepCopy({
		x:function(){
			return "x";
		},
		val:3,
		arr: [
			1,
			{test:1}
		]
	}))

	let circle = {};
	circle.child = circle;
	console.log(deepCopy(circle));
})

太强了，这个对环状结构的处理才是正确的

Answer 49 · 2021-06-08T07:26:49.000Z

//深度clone
const DFSdeepClone = (data) => {
	if (data === null) return null;
	let obj = {};
	if (Array.isArray(data)) {
		obj = [];
	}
	for (const key in data) {
		if (Object.hasOwnProperty.call(data, key)) {
			const element = data[key];
			const type = typeof element;
			if (type === 'number' || type === 'boolean' || type === 'string' || type === 'undefined' || type === 'symbol' || type == 'bigint') {
				obj[key] = element;
			} else if (type === 'function') {
				obj[key] = eval(`(${element.toString()})`);
			} else {
				obj[key] = DFSdeepClone(element)
			}
		}
	}
	return obj;
}
//广度clone
const BFSDeepClone = (data) => {
	const result = Array.isArray(data) ? [] : {};
	const stack = [[data, result]];
	while (stack.length) {
		const [originData, targetData] = stack.pop();
		for (const key in originData) {
			if (Object.hasOwnProperty.call(originData, key)) {
				const element = originData[key];
				const type = typeof element;
				if (type === 'number' || type === 'boolean' || type === 'string' || type === 'undefined' || type === 'symbol' || type == 'bigint') {
					targetData[key] = element;
				} else if (type === 'function') {
					targetData[key] = eval(`(${element.toString()})`)
				} else {
					let tmpTarget = Array.isArray(element) ? [] : {};
					targetData[key] = tmpTarget;
					stack.push([element, tmpTarget])
				}
			}
		}
	}
	return result
}

Answer 50 · 2021-09-25T12:10:24.000Z

对象深拷贝大家可能最先想到的就是DFS递归属性，递归实现相对简单代码就不贴了，这里放下BFS实现，拷贝主要需要注意下循环引用和重复引用问题，这个可以引入一个缓存数组解决。

`/**

BFS深拷贝对象和数组
@template T
@param {T} obj 旧对象
@return {T} 新对象
*/
function deepClone(obj) {
// 边界处理
if (obj.proto !== Object.prototype && obj.proto !== Array.prototype) {
return obj;
}
// 结果对象
let res = {};
// 队列内放对应层级的属性的对象或数组
const queue = [[res, obj]];
// 记录已经创建的引用和对应的旧对象引用，处理循环引用和重复引用
const hasCloneAttr = [
{
pre: obj, // 旧对象引用
now: res, // 新对象引用
},
];
while (queue.length > 0) {
const length = queue.length;
for (let i = 0; i < length; i++) {
const v = queue.shift();
const keys = Object.keys(v[1]);
for (const key of keys) {
// 对数组和对象进行深拷贝
if (
v[1][key].proto === Object.prototype ||
v[1][key].proto === Array.prototype
) {
let flag = false;
for (let item of hasCloneAttr) {
// 旧对象存在相同引用，则不需要再创建新的引用，直接使用之前创建引用就行
if (item.pre === v[1][key]) {
v[0][key] = item.now;
flag = true;
break;
}
}
if (!flag) {
v[0][key] = v[1][key].proto === Object.prototype ? {} : [];
hasCloneAttr.push({
pre: v[1][key],
now: v[0][key],
});
// 引用类型放入队列，下次依次取出处理
queue.push([v[0][key], v[1][key]]);
}
}
// 基本类型，直接赋值
else {
v[0][key] = v[1][key];
}
}
}
}
return res;
}`

Answer 51 · 2022-01-27T08:12:44.000Z

话不多说直接放代码发现了比较多的错误，但由于最近工作有点忙，一直没来得及纠正

更改(0226)

// 工具函数
let _toString = Object.prototype.toString
let map = {
  array: 'Array',
  object: 'Object',
  function: 'Function',
  string: 'String',
  null: 'Null',
  undefined: 'Undefined',
  boolean: 'Boolean',
  number: 'Number'
}
let getType = (item) => {
  return _toString.call(item).slice(8, -1)
}
let isTypeOf = (item, type) => {
  return map[type] && map[type] === getType(item)
}

深复制深度优先遍历

let DFSdeepClone = (obj, visitedArr = []) => {
  let _obj = {}
  if (isTypeOf(obj, 'array') || isTypeOf(obj, 'object')) {
    let index = visitedArr.indexOf(obj)
    _obj = isTypeOf(obj, 'array') ? [] : {}
    if (~index) { // 判断环状数据
      _obj = visitedArr[index]
    } else {
      visitedArr.push(obj)
      for (let item in obj) {
        _obj[item] = DFSdeepClone(obj[item], visitedArr)
      }
    }
  } else if (isTypeOf(obj, 'function')) {
    _obj = eval('(' + obj.toString() + ')');
  } else {
    _obj = obj
  }
  return _obj
}

广度优先遍历

let BFSdeepClone = (obj) => {
    let origin = [obj],
      copyObj = {},
      copy = [copyObj]
      // 去除环状数据
    let visitedQueue = [],
      visitedCopyQueue = []
    while (origin.length > 0) {
      let items = origin.shift(),
        _obj = copy.shift()
      visitedQueue.push(items)
      if (isTypeOf(items, 'object') || isTypeOf(items, 'array')) {
        for (let item in items) {
          let val = items[item]
          if (isTypeOf(val, 'object')) {
            let index = visitedQueue.indexOf(val)
            if (!~index) {
              _obj[item] = {}
                //下次while循环使用给空对象提供数据
              origin.push(val)
                // 推入引用对象
              copy.push(_obj[item])
            } else {
              _obj[item] = visitedCopyQueue[index]
              visitedQueue.push(_obj)
            }
          } else if (isTypeOf(val, 'array')) {
            // 数组类型在这里创建了一个空数组
            _obj[item] = []
            origin.push(val)
            copy.push(_obj[item])
          } else if (isTypeOf(val, 'function')) {
            _obj[item] = eval('(' + val.toString() + ')');
          } else {
            _obj[item] = val
          }
        }
        // 将已经处理过的对象数据推入数组 给环状数据使用
        visitedCopyQueue.push(_obj)
      } else if (isTypeOf(items, 'function')) {
        copyObj = eval('(' + items.toString() + ')');
      } else {
        copyObj = obj
      }
    }
  return copyObj
}

测试

/**测试数据 */
// 输入 字符串String
// 预期输出String
let str = 'String'
var strCopy = DFSdeepClone(str)
var strCopy1 = BFSdeepClone(str)
console.log(strCopy, strCopy1) // String String 测试通过
// 输入 数字 -1980
// 预期输出数字 -1980
let num = -1980
var numCopy = DFSdeepClone(num)
var numCopy1 = BFSdeepClone(num)
console.log(numCopy, numCopy1) // -1980 -1980 测试通过
// 输入bool类型
// 预期输出bool类型
let bool = false
var boolCopy = DFSdeepClone(bool)
var boolCopy1 = BFSdeepClone(bool)
console.log(boolCopy, boolCopy1) //false false 测试通过
// 输入 null
// 预期输出 null
let nul = null
var nulCopy = DFSdeepClone(nul)
var nulCopy1 = BFSdeepClone(nul)
console.log(nulCopy, nulCopy1) //null null 测试通过

// 输入undefined
// 预期输出undefined
let und = undefined
var undCopy = DFSdeepClone(und)
var undCopy1 = BFSdeepClone(und)
console.log(undCopy, undCopy1) //undefined undefined 测试通过
  //输入引用类型obj
let obj = {
  a: 1,
  b: () => console.log(1),
  c: {
    d: 3,
    e: 4
  },
  f: [1, 2],
  und: undefined,
  nul: null
}
var objCopy = DFSdeepClone(obj)
var objCopy1 = BFSdeepClone(obj)
console.log(objCopy === objCopy1) // 对象类型判断 false 测试通过
console.log(obj.c === objCopy.c) // 对象类型判断 false 测试通过
console.log(obj.c === objCopy1.c) // 对象类型判断 false 测试通过
console.log(obj.b === objCopy1.b) // 函数类型判断 false 测试通过
console.log(obj.b === objCopy.b) // 函数类型判断 false 测试通过
console.log(obj.f === objCopy.f) // 数组类型判断 false 测试通过
console.log(obj.f === objCopy1.f) // 数组类型判断 false 测试通过
console.log(obj.nul, obj.und) // 输出null，undefined 测试通过

// 输入环状数据
// 预期不爆栈且深度复制
let circleObj = {
  foo: {
    name: function() {
      console.log(1)
    },
    bar: {
      name: 'bar',
      baz: {
        name: 'baz',
        aChild: null //待会让它指向obj.foo
      }
    }
  }
}
circleObj.foo.bar.baz.aChild = circleObj.foo
var circleObjCopy = DFSdeepClone(circleObj)
var circleObjCopy1 = BFSdeepClone(circleObj)
console.log(circleObjCopy, circleObjCopy1) // 测试通过?

ps

关于深浅拷贝的问题博主已经在他的git上有文章说过了，我就不做多的叙述这两个方法我认为主要区别在于对于深层次以及环状数据，用深度优先遍历递归去做容易爆栈，广度优先遍历我对环状数据进行了处理，已经存在过的对象会存在数组中，下次直接赋值即可，无需继续遍历如果出现问题欢迎讨论指出

circleObj.foo.bar=1;
执行后发现 circleObjCopy 也被改了

更改(0226)

深复制 深度优先遍历

广度优先遍历

测试

ps

更改(0226)

深复制 深度优先遍历

广度优先遍历

测试

ps

更改(0226)

深复制 深度优先遍历

广度优先遍历

测试

ps

更改(0226)

深复制 深度优先遍历

广度优先遍历

测试

ps

深复制深度优先遍历

深复制深度优先遍历

深复制深度优先遍历

深复制深度优先遍历