Javascript实现常用数据结构与算法（一）

js不像java、c++有一部分现成的抽象数据类型（ADT），如集合、链表等，需要自己去实现这些功能的类。
当然我们可以使用ES6中的class的方式写类，本文还是用的函数实现类。

1. 数组

创建数组

通过 [ ] 操作符声明一个数组变量：
var numbers = [];
numbers.length 属性可以返回数组的长度。

数组的核心方法

注意：
　　map()返回的数组里面包含了传入map方法的函数的运行结果（返回值）。会生成新数组。
　　filter() 返回的新数由使函数返回true的元素组成。会生成新数组。
　　forEach()接受一个函数作为参数， 对数组中的每个元素使用该函数。
　　concat() 和 splice() 方法允许通过已有数组创建新数组。 concat 方法可以合并多个数组
创建一个新数组， splice() 方法截取一个数组的子集创建一个新数组。

2. 列表

实现列表类以及相关的操作方法。

//列表的实现
function List() {
	this.listSize = 0;
	this.pos = 0;
	this.dataStore = []; // 初始化一个空数组来保存列表元素
	this.clear = clear;
	this.find = find;
	this.toString = toString;
	this.insert = insert;
	this.append = append;
	this.remove = remove;
	this.front = front;
	this.end = end;
	this.prev = prev;
	this.next = next;
	this.length = length;
	this.currPos = currPos;
	this.moveTo = moveTo;
	this.getElement = getElement;
	this.length = length;
	this.contains = contains;
}
function append(element) {  //添加元素
	this.dataStore[this.listSize++] = element;
}
function find(element) {  //查找元素
	for (var i = 0; i < this.dataStore.length; ++i) {
		if (this.dataStore[i] == element) {
			return i;
		}
	} 
	return -1;
}
function remove(element) {  //移除元素
	var foundAt = this.find(element);
	if (foundAt > -1) {
		this.dataStore.splice(foundAt,1);
		--this.listSize;
		return true;
	} 
	return false;
}
function length() {  //列表的长度（有多少个元素）
	return this.listSize;
}
function toString() {  //显示列表中的元素
	return this.dataStore;
}
function insert(element, after) {  //向列表中插入一个元素，after参数是要在表中插入的位置
	var insertPos = this.find(after);
	if (insertPos > -1) {
		this.dataStore.splice(insertPos+1, 0, element);
		++this.listSize;
		return true;
	} 
	return false;
}
function clear() {  //清除列表所有元素
	delete this.dataStore;
	this.dataStore = [];
	this.listSize = this.pos = 0;
}
function contains(element) {  //判断给定值是否在列表中
	for (var i = 0; i < this.dataStore.length; ++i) {
		if (this.dataStore[i] == element) {
			return true;
		}
	} 
	return false;
}

function front() {  //将列表的当前位置移动到第一个元素
	this.pos = 0;
} 
function end() {  //将列表的当前位置移动到最后一个元素
	this.pos = this.listSize-1;
} 
function prev() {  //将当前位置后移一位
	if (this.pos > 0) {
		--this.pos;
	}
} 
function next() {  //将当前位置前移一位
	if (this.pos < this.listSize-1) {
		++this.pos;
	}
} 
function currPos() {  //返回列表的当前位置
	return this.pos;
} 
function moveTo(position) {  //将当前位置移动到指定位置
	this.pos = position;
} 
function getElement() {  //返回当前位置的元素
	return this.dataStore[this.pos];
}

3. 栈

可以使用栈，进行数制间的转换、判断回文字符串等。

function Stack() {
	this.dataStore = [];  //用数组存储栈的元素
	this.top = 0;   //记录栈顶的位置
	this.push = push;
	this.pop = pop;
	this.peek = peek;
	this.clear = clear;
	this.length = length;
}
function push(element) { //元素入栈
	this.dataStore[this.top++] = element;
}
function pop() {  //元素出栈（栈顶元素永久删除）
	return this.dataStore[--this.top];
}
function peek() {  //元素出栈（只返回栈顶元素，不删除）
	return this.dataStore[this.top-1];
}
function clear() {  //清除栈内所有元素
	this.top = 0;
}
function length() {  //记录栈内元素的个数
	return this.top;
}

10进制数转换进制（2-9）

//把数字转换成其他进制（2~9进制），num是要操作数，base是进制数
function mulBase(num, base) {
	var s = new Stack();
	do {
		s.push(num % base);
		num = Math.floor(num /= base);
	} while (num > 0);
	var converted = "";
	while (s.length() > 0) {
		converted += s.pop();
	} 
	return converted;
} 

判断回文字符串：

function isPalindrome(word) {
	var s = new Stack();
	for (var i = 0; i < word.length; ++i) {
		s.push(word[i]);
	}
	var rword = "";
	while (s.length() > 0) {
		rword += s.pop();
	}
	if (word == rword) {
		return true;
	}else {
		return false;
	}
} 

计算阶乘：

//计算阶乘(递归的方法)
function fact(n) {
	var s = new Stack();
	while (n > 1) {
		s.push(n--);
	}
	var product = 1;
	while (s.length() > 0) {
		product *= s.pop();
	}
	return product;
} 
print(fact(5)); // 显示 120

4. 队列

//用数组实现队列
function Queue() {
	this.dataStore = [];
	this.enqueue = enqueue;
	this.dequeue = dequeue;
	this.front = front;
	this.back = back;
	this.toString = toString;
	this.empty = empty;
	this.count = count;
} 
//向队尾添加一个元素
function enqueue(element) {
	this.dataStore.push(element);
} 
//删除队首的一个元素
function dequeue() {
	return this.dataStore.shift();
} 
//读取到队首的元素
function front() {
	return this.dataStore[0];
} 
//读取到队尾的元素
function back() {
	return this.dataStore[this.dataStore.length-1];
} 
//显示队列内的所有元素
function toString() {
	var retStr = "";
	for (var i = 0; i < this.dataStore.length; ++i) {
		retStr += this.dataStore[i] + "\n";
	} 
	return retStr;
} 
//判断队列是否为空
function empty() {
	if (this.dataStore.length == 0) {
		return true;
	} 
	else {
		return false;
	}
}
//队列的长度
function count() {
	return this.dataStore.length;
}

使用队列进行基数排序：

//使用队列进行基数排序
function distribute(nums, queues, n, digit) { //将数字分配到相应的1-9的队列中
	for (var i = 0; i < n; ++i) {
		if (digit == 1) {    //个位的队列
			queues[nums[i]%10].enqueue(nums[i]);
		} else {     //十位的队列
			queues[Math.floor(nums[i] / 10)].enqueue(nums[i]);
		}
	}
} 
function collect(queues, nums) {   //收集队列中的数字放在原数组中
	var i = 0;
	for (var digit = 0; digit < 10; ++digit) {
		while (!queues[digit].empty()) {
			nums[i++] = queues[digit].dequeue();
		}
	}
} 
function dispArray(arr) {
	for (var i = 0; i < arr.length; ++i) {
		putstr(arr[i] + " ");
	}
} 
// 主程序
var queues = [];
for (var i = 0; i < 10; ++i) {
	queues[i] = new Queue();
} 
var nums = [];
for (var i = 0; i < 10; ++i) {   //随机产生10个数字（0-99）
	nums[i] = Math.floor(Math.floor(Math.random() * 101));
} 
print("排序前: ");
dispArray(nums);
distribute(nums, queues, 10, 1);
collect(queues, nums);
distribute(nums, queues, 10, 10);
collect(queues, nums);
print("\n\n排序后: ");
dispArray(nums);