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"));