共计 7653 个字符,预计需要花费 20 分钟才能阅读完成。
字典
字典是一种以键 - 值对模式存储数据的数据结构,JavaScript 的 Object 类就是以字典的模式设计的。上面用代码实现字典类以及相干操作方法
Dictionary 类
datastore 为数据集
class Dictionary{datastore=[]
constructor(){}
}
add() 增加键值对
add(key, value) {this.datastore[key]=value
}
get() 失去键的值
get(key) {return this.datastore[key]
}
remove() 移除元素
remove(key) {delete this.datastore[key]
}
showAll() 打印全副信息
showAll() {for(let key in this.datastore){console.log(`key=>${this.datastore[key]}`)
}
}
clear() 清空操作
clear() {for(let key in this.datastore){delete this.datastore[key]
}
}
残缺代码
class Dictionary {datastore = []
constructor() {}
add(key, value) {this.datastore[key] = value
}
find(key) {return this.datastore[key]
}
remove(key) {delete this.datastore[key]
}
showAll() {for (let key in this.datastore) {console.log(`key=>${this.datastore[key]}`)
}
}
count() {
let num = 0
for (let key in this.datastore) {num++}
return num
}
clear() {for (let key in this.datastore) {delete this.datastore[key]
}
}
}
散列
散列是一种罕用的数据存储技术,散列后的数据能够疾速地插入或取用。散列应用的数据结构叫做散列表。
整个散列过程其实就是两步。
- 在存储时,通过散列函数计算记录的散列地址,并按此散列地址存储该记录。
- 当查找记录时,咱们通过同样的散列函数计算记录的散列地址,按此散列地址拜访该记录。
实现 HashTable 类
class HashTable{table=new Array(137)
constructor(){}
}
hash() 散列函数应用霍纳算法计算键值
hash(string){
const H = 37;
var total = 0;
for (var i = 0; i < string.length; ++i) {total += H * total + string.charCodeAt(i);
}
total = total % this.table.length;
if (total < 0) {total += this.table.length-1;}
return parseInt(total);
}
put() 用来将数据存入散列表
put(key,data){let pos = this.hash(key)
this.table[pos]=data
}
showDistro() 示散列表中的数据
showDistro(){for(let index=0,length=this.table.length;index<length;index++){if(this.table[index]){console.log(`index:${this.table[index]}`)
}
}
}
get() 获取对应的键值
get(key) {return this.table[hash(key)]
}
残缺代码
class HashTable {table = new Array(137)
constructor() {}
hash(string) {
const H = 37;
var total = 0;
for (var i = 0; i < string.length; ++i) {total += H * total + string.charCodeAt(i);
}
total = total % this.table.length;
if (total < 0) {total += this.table.length - 1;}
return parseInt(total);
}
showDistro() {for (let index = 0, length = this.table.length; index < length; index++) {if (this.table[index]) {console.log(`index:${this.table[index]}`)
}
}
}
put(key, data) {let pos = this.hash(key)
this.table[pos] = data
}
get(key) {return this.table[hash(key)]
}
}
碰撞解决
当散列函数对于多个输出产生同样的输入时,就产生了碰撞。解决两碰撞解决办法次要有两种:链地址法和凋谢定址法。
1. 链地址法
链地址法是指实现散列表的底层数组中,每个数组元素又是一个新的数据结构,比方另一个数组,这样就能存储多个键了。应用这种技术,即便两个键散列后的值雷同,仍然被保留在同样的地位,只不过它们在第二个数组中的地位不一样罢了
结构散列表
class HashTableChains{table=new Array(137).fill([])
constructor(){}
}
要从新定义 put() 和 get() 办法。put() 办法将键值散列,散列后的值对应数组中的一个地位,先尝试将数据放到该地位上的数组中的第一个单元格,如果该单元格里曾经有数据了,put() 办法会搜寻下一个地位,直到找到能搁置数据的单元格,并把数据存储进去
put(key,data){let pos = this.hash(key)
let index=0
if(this.table[pos][index]==undefined){this.table[pos][index]=data
}else{while(this.table[pos][index]!=undefined){index++}
this.table[pos][index]=key
this.table[pos][index+1]=data
}
}
get(key){let hash = this.hash(key)
let index=0
if(this.table[hash][index]==key){return this.table[hash][index+1]
}else{while(this.table[hash][index]!=key&&this.table[hash][index]!=undefined){index+=2}
if(this.table[hash][index]!=undefined){return this.table[hash][index+1]
}
}
return undefined
}
残缺代码
class HashTableChains{table=new Array(137).fill([])
constructor(){}
hash(string){
const H = 37;
var total = 0;
for (var i = 0; i < string.length; ++i) {total += H * total + string.charCodeAt(i);
}
total = total % this.table.length;
if (total < 0) {total += this.table.length-1;}
return parseInt(total);
}
showDistro(){for(let index=0,length=this.table.length;index<length;index++){if(this.table[index][0] != undefined){console.log(`index:${this.table[index]}`)
}
}
}
put(key,data){let pos = this.hash(key)
let index=0
if(this.table[pos][index]==undefined){this.table[pos][index]=data
}else{while(this.table[pos][index]!=undefined){index++}
this.table[pos][index]=key
this.table[pos][index+1]=data
}
}
get(key){let hash = this.hash(key)
let index=0
if(this.table[hash][index]==key){return this.table[hash][index+1]
}else{while(this.table[hash][index]!=key&&this.table[hash][index]!=undefined){index+=2}
if(this.table[hash][index]!=undefined){return this.table[hash][index+1]
}
}
return undefined
}
}
2. 凋谢定址法
凋谢定址法隶属于一种更一般化的散列技术:凋谢寻址散列。当产生碰撞时,凋谢定址法查散列表中的下一个地位是否为空。如果为空,就将数据存入该地位;如果不为空,则持续查看下一个地位,直到找到一个空的地位为止。
线性探测法工作,须要重写 put() 和 get() 办法。
结构散列表
新增加一个属性 values 用来存散列表每个键对应的值
class HashTableLinear{table=new Array(137)
values=new Array(137)
constructor(){}
}
重写 put() 和 get() 办法
put(key,data){let pos = this.hash(key)
if(this.table[pos]==undefined){this.table[pos]=key
this.values[pos]=data
}else{while(this.table[pos]!=undefined){pos++}
this.table[pos]=key
this.values[pos]=data
}
}
get(key){let pos = this.hash(key)
if(this.table[pos]==key){return this.values[pos]=data
}else{while(this.table[pos]!=key&&this.table[pos]!=undefined){pos++}
if(this.table[pos]!=undefined){return this.values[pos]=data
}
}
return undefined
}
残缺代码
class HashTableLinear{table=new Array(137)
values=new Array(137)
constructor(){}
hash(string){
const H = 37;
var total = 0;
for (var i = 0; i < string.length; ++i) {total += H * total + string.charCodeAt(i);
}
total = total % this.table.length;
if (total < 0) {total += this.table.length-1;}
return parseInt(total);
}
showDistro(){for(let index=0,length=this.table.length;index<length;index++){if(this.table[index]){console.log(`index:${this.table[index]}=>${this.values[index]}`)
}
}
}
put(key,data){let pos = this.hash(key)
if(this.table[pos]==undefined){this.table[pos]=key
this.values[pos]=data
}else{while(this.table[pos]!=undefined){pos++}
this.table[pos]=key
this.values[pos]=data
}
}
get(key){let pos = this.hash(key)
if(this.table[pos]==key){return this.values[pos]=data
}else{while(this.table[pos]!=key&&this.table[pos]!=undefined){pos++}
if(this.table[pos]!=undefined){return this.values[pos]=data
}
}
return undefined
}
}
汇合
汇合是一种蕴含不同元素的数据结构。汇合中的元素称为成员。汇合的两个最重要个性是:首先,汇合中的成员是无序的;其次,汇合中不容许雷同成员存在。当你想要创立一个数据结构,用来保留一些举世无双的元素时,汇合就变得十分有用。
Set 类的实现
class SetList{dataStore=[]
constructor(){}
}
add() 增加元素
add(ele) {if (this.dataStore.indexOf(ele) == -1) {this.dataStore.push(ele)
return true
} else {return false}
}
remove() 移除元素
remove(ele) {let position = this.dataStore.indexOf(ele)
if (position != -1) {this.dataStore.splice(position, 1)
return true
} else {return false}
}
size() 返回数据量
size() {return this.dataStore.length}
show() 展现数据集
show(){return this.dataStore}
contains(),该办法查看一个成员是否属于该汇合
contains(ele) {return this.dataStore.indexOf(ele) != -1
}
union() 办法执行并集操作
union(set) {let unionSet = new SetList()
this.dataStore.forEach(item => {unionSet.add(item)
})
set.dataStore.forEach(item => {unionSet.add(item)
})
return unionSet
}
intersect() 办法求两个汇合的交加
intersect() {let intersectSet = new SetList()
this.dataStore.forEach(item => {if (set.contains(item)) {intersectSet.add(item)
}
})
return intersectSet
}
subset() 判断是否是指标汇合的子集
subset(set) {if (set.size() < this.size()) {return false}
this.dataStore.forEach(item => {if (!set.contains(item)) {return false;}
})
return true
}
difference(),该办法返回一个新汇合,该汇合蕴含的是那些属于第一个汇合但不属于第二个汇合的成员。
difference(set) {let differencetSet = new SetList()
this.dataStore.forEach(item => {if (!set.contains(item)) {differencetSet.add(item)
}
})
return differencetSet
}
实现代码
class SetList {dataStore = []
constructor() {}
add(ele) {if (this.dataStore.indexOf(ele) == -1) {this.dataStore.push(ele)
return true
} else {return false}
}
remove(ele) {let position = this.dataStore.indexOf(ele)
if (position != -1) {this.dataStore.splice(position, 1)
return true
} else {return false}
}
size() {return this.dataStore.length}
contains(ele) {return this.dataStore.indexOf(ele) != -1
}
union(set) {let unionSet = new SetList()
this.dataStore.forEach(item => {unionSet.add(item)
})
set.dataStore.forEach(item => {unionSet.add(item)
})
return unionSet
}
intersect() {let intersectSet = new SetList()
this.dataStore.forEach(item => {if (set.contains(item)) {intersectSet.add(item)
}
})
return intersectSet
}
subset(set) {if (set.size() < this.size()) {return false}
this.dataStore.forEach(item => {if (!set.contains(item)) {return false;}
})
return true
}
difference(set) {let differencetSet = new SetList()
this.dataStore.forEach(item => {if (!set.contains(item)) {differencetSet.add(item)
}
})
return differencetSet
}
show() {return this.dataStore}
}