关于本章邻接表的JS实现和一些相关的疑问
来源:2-6 邻接表的实现
qq_crusader_1
2022-05-11
还是根据老师的视频和JAVA的实现改写的JS,代码如下:
首先,因为JS中没有自带的LinkedList,所以自己实现了一个:
function LinkedList() {
var Node = function(element) {
this.element = element;
this.next = null;
}
var length = 0;
var head = null;
this.add = function(element) {
var node = new Node(element),current;
if (head==null) {
head = node;
} else {
current = head;
while(current.next) {
current = current.next;
}
current.next = node;
}
length++;
}
this.set = function(index, element) {
var a = this.get(index);
a = element;
}
this.get = function(index) {
var num = 0, current;
if (index < 0) throw new RangeError("Index out of range");
current = head;
while(num++ < index) {
current = current.next;
}
var a = current.element;
return a;
}
this.contains = function(element) {
var current = head;
while(current) {
if (current.element == element) return true;
current = current.next;
}
return false;
}
this.length = function() {
return length;
}
this.elements = function() {
var current = head;
var tmpArr = [];
while(current) {
console.log('elements',current)
tmpArr.push(current.element);
current = current.next;
}
return tmpArr;
}
}
module.exports = LinkedList;然后是AdjList实现:
const LinkedList = require('../util/LinkedList');
const fs = require('fs');
const path = require('path');
var _privateMap = new WeakMap();
var _keys = {'V': new String(), 'E': new String(), 'ADJ': new String()}
function AdjList(filename) {
var V, E, adj = new LinkedList(), index = 0;
var file = fs.readFileSync(filename, 'utf8');
var vertices = file.split(/\s\n?/g)
V = +vertices[index++];
_privateMap.set(_keys.V, { writable: true, value: 0 })
_privateMap.set(_keys.E, { writable: true, value: 0 })
_privateMap.set(_keys.ADJ, { writable: true, value: 0 })
adj = [];
for (let i = 0; i < V; i++) {
1) adj[i] = new LinkedList();
}
E = vertices[index++];
this.$privateSet(_privateMap, _keys.V, V);
this.$privateSet(_privateMap, _keys.E, E);
for (var i = 0; i < E; i++) {
let a = +vertices[index++];
this.validateVertex(a);
let b = +vertices[index++];
this.validateVertex(b);
2) adj[a].add(b);
3) adj[b].add(a);
}
this.$privateSet(_privateMap, _keys.ADJ, adj);
console.log('adj', adj)
return this;
}
AdjList.prototype = {
V: function(){
return this.$privateGet(_privateMap, _keys['V'])
},
E: function() {
return this.$privateGet(_privateMap, _keys['E'])
},
elements: function() {
var adj = this.$privateGet(_privateMap, _keys.ADJ);
var V = this.$privateGet(_privateMap, _keys.V);
var str = ``;
for (var i = 0; i < V; i++) {
str += `第${i}个点的邻边是:`
4) for(var j of adj[i].elements()) {
5) str += `${j}、`
6) }
}
str.substring(0, str.length - 2) + '\n'
return str;
},
hasEdge: function(v, w) {
this.validateVertex(v);
this.validateVertex(w);
var adj = this.$privateGet(_privateMap, _keys.ADJ);
7) return adj[v].contains(w);
},
validateVertex(v) {
var V = this.$privateGet(_privateMap, _keys['V']);
if (v < 0 || v >= V) throw new RangeError("vertex " + v + " is invalid");
},
degree: function(v) {
var adj = this.$privateGet(_privateMap, _keys.ADJ);
8) return adj[v].length();
},
adj: function(v) {
this.validateVertex(v);
var adj = this.$privateGet(_privateMap, _keys.ADJ);
9) return adj[v].elements();
},
$privateSet: function($map, $key, $value) {
var descriptor = $map.get($key);
console.log('$privateSet', $value)
descriptor.value = $value;
},
$privateGet: function($map, $key) {
return $map.get($key).value;
}
}
var adjList = new AdjList(`${__dirname}/g.txt`)
console.log(`图有${adjList.V()}个顶点,有${adjList.E()}条边, 顶点1有${adjList.degree(0)}条邻边,它的邻边是${adjList.adj(0)},
顶点0和顶点5${adjList.hasEdge(0, 5) ? '存在' : '不存在'}邻边,${adjList.elements()}`)但是发现我这个LinkedList实现其中的contains时间复杂度不是最优的,并且下标访问元素的时间复杂度也不低,所以暂时舍弃使用这个LinkedList,转而改为js中的Set这样更简单直接,所以针对上述代码改动如下:
1)处改为:
adj[i]=new Set()
2)处改为
adj[a].add(b); adj[b].add(a);
4)-6)处改为:
for (var j of adj[i]) {
str += `${j}、`
}7)改为
return adj[v].has(w);
8)改为
return adj[v].size;
9)改为
return [...adj[v]];
目前还不清楚如何实现LinkedList.contains使它的时间复杂度为O(1),还有也无法自己实现LinkedList通过使用下标访问元素的时间复杂度为O(1)?看Set的这些API跟JAVA中的LinkedList很像,也不清楚Set是否是链表的一种实现?
写回答
1回答
-
LinkedList 无法做到 O(1),LinkedList 就是 O(n) 的。
如果想要高效实现 contains 和 erase 操作,需要使用 Set。通常语言标准库中的 Set,使用的是红黑树或者哈希表,期时间复杂度可以达到 O(logn) 或者 O(1)。课程在下一小节也将使用 Set 来实现邻接表。
继续加油!:)
022022-06-23
相似问题