Advanced-Frontend
第 6 题：请分别用深度优先思想和广度优先思想实现一个拷贝函数？
话不多说直接放代码
发现了比较多的错误，但由于最近工作有点忙，一直没来得及纠正
更改(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上有文章说过了，我就不做多的叙述 这两个方法我认为主要区别在于对于深层次以及环状数据，用深度优先遍历递归去做容易爆栈，广度优先遍历我对环状数据进行了处理，已经存在过的对象会存在数组中，下次直接赋值即可，无需继续遍历 如果出现问题欢迎讨论指出
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
我只深拷贝了 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));
})
var o = {m: 2} var obj = { a: {b:o}, e: o } 广度优先测试失败
公司gayhub怎么老是炸，感谢提醒，已更新，在处理环状数据时我将visitedCopyQueue错用成visitedQueue了，导致上一次使用的数据是存在visitedQueue里的引用导致深复制失败
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;
}
这应该是深度优先拷贝吧
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;
}
/**
* @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)
}
@atheist1 您好。我刚刚查看您的广度优先遍历 BFSdeepClone 函数。while递归中没有判断array的环状数据。
您可以将下面这段代码 添加到函数执行之前，来复现该问题
let a = [1,2,3,4] let b = a a.push(b) obj.a = a;
谢谢指点，我会尝试下的，感谢------------------ 原始邮件 ------------------ 发件人: "qinchenguang"[email protected] 发送时间: 2019年7月22日(星期一) 晚上10:18 收件人: "Advanced-Frontend/Daily-Interview-Question"[email protected]; 抄送: "ZJINH"[email protected];"Comment"[email protected]; 主题: 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.
@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数组 第二次引用会和源数据保持一致
深度优先算法深拷贝有很多就不写了 广度优先算法深拷贝，实现了下，暂时没发现问题
// 广度优先法
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;
}
深度优先算法深拷贝有很多就不写了 广度优先算法深拷贝，实现了下，暂时没发现问题
// 广度优先法 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; }
这好像还是深度遍历
深度优先算法深拷贝有很多就不写了 广度优先算法深拷贝，实现了下，暂时没发现问题
// 广度优先法 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，看看路径
深度优先搜索的拷贝函数，没有考虑一些复杂的对象。
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);
}
visitedArr.push(obj)
@atheist1
这边不应该是放入的原始值吧，应该是放入深拷贝之后的值_obj
circleObjCopy.foo.bar.baz.aChild === circleObjCopy.foo //false
测试用例最后一个，拷贝后的结果的循环引用不正确。
