数据结构与算法JavaScript描述练习------第9章集合

1. 修改 Set 类，使里面的元素按顺序存储。写一段测试代码来测试你的修改。

function Set() { 
	this.dataStore = []; 
	this.add = add; 
	this.remove = remove; 
	this.size = size;
	this.contains = contains;
	this.union = union; 
	this.intersect = intersect; 
	this.subset = subset; 
	this.difference = difference; 
	this.show = show; 
}

function add(data) { 
	var index = 0;
	if (this.dataStore.indexOf(data) < 0) { 
		while (index < this.dataStore.length && this.dataStore[index] < data) {
			index++;
		} 
		this.dataStore.splice(index, 0, data);
		return true;
	} else { 
		return false; 
	} 
}

function remove(data) { 
	var pos = this.dataStore.indexOf(data); 
	if (pos > -1) { 
		this.dataStore.splice(pos,1); 
		return true; 
	} else { 
		return false; 
	} 
}

function show() { 
	return this.dataStore; 
}

function contains(data) { 
	if (this.dataStore.indexOf(data) > -1) { 
		return true; 
	} else { 
		return false; 
	} 
}

function union(set) { 
	var tempSet = new Set(); 
	for (var i = 0; i < this.dataStore.length; ++i) { 
		tempSet.add(this.dataStore[i]); 
	} 
	for (var i = 0; i < set.dataStore.length; ++i) { 
		if (!tempSet.contains(set.dataStore[i])) { 
			tempSet.dataStore.push(set.dataStore[i]); 
		} 
	} 
	return tempSet; 
}

function intersect(set) { 
	var tempSet = new Set(); 
	for (var i = 0; i < this.dataStore.length; ++i) { 
		if (set.contains(this.dataStore[i])) { 
			tempSet.add(this.dataStore[i]); 
		} 
	} 
	return tempSet; 
}

function size() { 
	return this.dataStore.length; 
}

function subset(set) { 
	if (this.size() > set.size()) {
		return false; 
	} else { 
		for (var i = 0; i < this.dataStore.length; ++i) {
			if (!set.contains(this.dataStore[i])) { 
				return false; 
			} 
		} 
	} 
	return true; 
}
		
function difference(set) { 
	var tempSet = new Set(); 
	for (var i = 0; i < this.dataStore.length; ++i) { 
		if (!set.contains(this.dataStore[i])) { 
			tempSet.add(this.dataStore[i]); 
		} 
	} 
	return tempSet; 
}	
		
		
		
		

var cis = new Set(); 
cis.add("Clayton"); 
cis.add("Jennifer"); 
cis.add("Danny"); 
cis.add("Bryan"); 
cis.add("Clayton"); 
cis.add("Jennifer"); 
console.log(cis);

2. 修改 Set 类，将存储方式从数组替换为链表。写一段测试代码来测试你的修改。

function Node(data) {
	this.data = data;
	this.next = null;
}

function Set() { 
	this.head = new Node("head"); 
	this.add = add; 
	this.remove = remove; 
	this.size = size;
	this.contains = contains;
	this.union = union; 
	this.intersect = intersect; 
	this.subset = subset; 
	this.difference = difference; 
	this.show = show; 
}

function add(data) { 
	var current = this.head;
	var newNode = new Node(data);
	while (current.next !== null && current.next.data < data) {
		current = current.next;
	} 
	if (current.next === null) {
		current.next = newNode;
	}
	if (current.next.data === data)
		return false;
	else {
		newNode.next = current.next;
		current.next = newNode;
		return true;
	}
}

function remove(data) { 
	var current = this.head;
	while (current.next !== null && current.next.data !== data) {
		current = current.next;
	}
	if (current.next !== null) {
		current.next = current.next.next;
		return true;
	}
	return false;
}

function show() { 
	var elements = [];
	var current = this.head;
	while (current !== null) {
		elements.push(current.data);
		current = current.next;
	}
	return elements;
}

function contains(data) { 
	var current = this.head;
	while (current !== null) {
		if (current.data === data) {
			return true;
		}
	}
	return false;
}

function union(set) { 
	var tempSet = new Set(); 
	var current = this.head;
	while (current !== null) {
		tempSet.add(current.data);
		current = current.next;
	}
	current = set.head;
	while (current !== null) {
		tempSet.add(current.data);
		current = current.next
	}
	return tempSet; 
}

function intersect(set) { 
	var tempSet = new Set(); 
	var current = this.head;
	while (current !== null) { 
		if (set.contains(current.data)) { 
			tempSet.add(current.data); 
		} 
		current = current.next;
	} 
	return tempSet; 
}

function size() { 
	var count = 0;
	var current = this.head;
	while (current !== null) {
		count++;
		current = current.next;
	}
	return count;
}

function subset(set) { 
	if (this.size() > set.size()) {
		return false;
	}
	var current = this.head;
	while (current !== null) {
		if (!set.contains(current.data)) {
			return false;
		}
		current = current.next;
	}
	return true;
}
		
function difference(set) { 
	var tempSet = new Set();
	var current = this.head;
	while (current !== null) {
		if (!set.contains(current.data)) {
			tempSet.add(current.data);
		}
		current = current.next;
	}
	return tempSet;
}			

var cis = new Set(); 
cis.add("Clayton"); 
cis.add("Jennifer"); 
cis.add("Danny"); 
cis.add("Bryan"); 
cis.add("Clayton"); 
cis.add("Jennifer"); 
console.log(cis);

3. 为 Set 类增加一个 higher(element) 方法，该方法返回比传入元素大的元素中最小的那 个。写一段测试代码来测试这个方法。

function Set() { 
	this.dataStore = []; 
	this.add = add; 
	this.remove = remove; 
	this.size = size;
	this.contains = contains;
	this.union = union; 
	this.intersect = intersect; 
	this.subset = subset; 
	this.difference = difference; 
	this.show = show; 
	this.higher = higher;
}

function add(data) { 
	var index = 0;
	if (this.dataStore.indexOf(data) < 0) { 
		while (index < this.dataStore.length && this.dataStore[index] < data) {
			index++;
		} 
		this.dataStore.splice(index, 0, data);
		return true;
	} else { 
		return false; 
	} 
}

function remove(data) { 
	var pos = this.dataStore.indexOf(data); 
	if (pos > -1) { 
		this.dataStore.splice(pos,1); 
		return true; 
	} else { 
		return false; 
	} 
}

function show() { 
	return this.dataStore; 
}

function contains(data) { 
	if (this.dataStore.indexOf(data) > -1) { 
		return true; 
	} else { 
		return false; 
	} 
}

function union(set) { 
	var tempSet = new Set(); 
	for (var i = 0; i < this.dataStore.length; ++i) { 
		tempSet.add(this.dataStore[i]); 
	} 
	for (var i = 0; i < set.dataStore.length; ++i) { 
		if (!tempSet.contains(set.dataStore[i])) { 
			tempSet.dataStore.push(set.dataStore[i]); 
		} 
	} 
	return tempSet; 
}

function intersect(set) { 
	var tempSet = new Set(); 
	for (var i = 0; i < this.dataStore.length; ++i) { 
		if (set.contains(this.dataStore[i])) { 
			tempSet.add(this.dataStore[i]); 
		} 
	} 
	return tempSet; 
}

function size() { 
	return this.dataStore.length; 
}

function subset(set) { 
	if (this.size() > set.size()) {
		return false; 
	} else { 
		for (var i = 0; i < this.dataStore.length; ++i) {
			if (!set.contains(this.dataStore[i])) { 
				return false; 
			} 
		} 
	} 
	return true; 
}
		
function difference(set) { 
	var tempSet = new Set(); 
	for (var i = 0; i < this.dataStore.length; ++i) { 
		if (!set.contains(this.dataStore[i])) { 
			tempSet.add(this.dataStore[i]); 
		} 
	} 
	return tempSet; 
}	
		
function higher(element) { 
    var index = this.dataStore.findIndex(item => item > element);
    if (index !== -1) {
        return this.dataStore[index];
    } else {
        return null;
    }
}		

var cis = new Set(); 
cis.add("Clayton"); 
cis.add("Jennifer"); 
cis.add("Danny"); 
cis.add("Bryan"); 
cis.add("Clayton"); 
cis.add("Jennifer"); 
console.log("集合内容:", cis.show());
console.log("比 'Clayton' 大的最小元素:", cis.higher("Clayton"));
console.log("比 'Danny' 大的最小元素:", cis.higher("Danny"));
console.log("比 'Jennifer' 大的最小元素:", cis.higher("Jennifer"));
console.log("比 'Bryan' 大的最小元素:", cis.higher("Bryan"));
console.log("比 'Zoe' 大的最小元素:", cis.higher("Zoe"));

4. 为 Set 类增加一个 lower(element) 方法，该方法返回比传入元素小的元素中最大的那 个。写一段测试代码来测试这个方法。

function Set() { 
	this.dataStore = []; 
	this.add = add; 
	this.remove = remove; 
	this.size = size;
	this.contains = contains;
	this.union = union; 
	this.intersect = intersect; 
	this.subset = subset; 
	this.difference = difference; 
	this.show = show; 
	this.lower = lower;
}

function add(data) { 
	var index = 0;
	if (this.dataStore.indexOf(data) < 0) { 
		while (index < this.dataStore.length && this.dataStore[index] < data) {
			index++;
		} 
		this.dataStore.splice(index, 0, data);
		return true;
	} else { 
		return false; 
	} 
}

function remove(data) { 
	var pos = this.dataStore.indexOf(data); 
	if (pos > -1) { 
		this.dataStore.splice(pos,1); 
		return true; 
	} else { 
		return false; 
	} 
}

function show() { 
	return this.dataStore; 
}

function contains(data) { 
	if (this.dataStore.indexOf(data) > -1) { 
		return true; 
	} else { 
		return false; 
	} 
}

function union(set) { 
	var tempSet = new Set(); 
	for (var i = 0; i < this.dataStore.length; ++i) { 
		tempSet.add(this.dataStore[i]); 
	} 
	for (var i = 0; i < set.dataStore.length; ++i) { 
		if (!tempSet.contains(set.dataStore[i])) { 
			tempSet.dataStore.push(set.dataStore[i]); 
		} 
	} 
	return tempSet; 
}

function intersect(set) { 
	var tempSet = new Set(); 
	for (var i = 0; i < this.dataStore.length; ++i) { 
		if (set.contains(this.dataStore[i])) { 
			tempSet.add(this.dataStore[i]); 
		} 
	} 
	return tempSet; 
}

function size() { 
	return this.dataStore.length; 
}

function subset(set) { 
	if (this.size() > set.size()) {
		return false; 
	} else { 
		for (var i = 0; i < this.dataStore.length; ++i) {
			if (!set.contains(this.dataStore[i])) { 
				return false; 
			} 
		} 
	} 
	return true; 
}
		
function difference(set) { 
	var tempSet = new Set(); 
	for (var i = 0; i < this.dataStore.length; ++i) { 
		if (!set.contains(this.dataStore[i])) { 
			tempSet.add(this.dataStore[i]); 
		} 
	} 
	return tempSet; 
}			
		
function lower(element) {
	var index = this.dataStore.findIndex(item => item >= element) - 1;
    if (index >= 0) {
        return this.dataStore[index];
    } else {
        return null;
    }
}		

var cis = new Set(); 
cis.add("Clayton"); 
cis.add("Jennifer"); 
cis.add("Danny"); 
cis.add("Bryan"); 
cis.add("Clayton"); 
cis.add("Jennifer"); 
console.log("集合内容:", cis.show());
console.log("比 'Clayton' 小的最大元素:", cis.lower("Clayton"));
console.log("比 'Danny' 小的最大元素:", cis.lower("Danny"));
console.log("比 'Jennifer' 小的最大元素:", cis.lower("Jennifer"));
console.log("比 'Bryan' 小的最大元素:", cis.lower("Bryan"));
console.log("比 'Alex' 小的最大元素:", cis.lower("Alex"));