发布于 2017-02-22 10:04:27 | 166 次阅读 | 评论: 0 | 来源: 网友投递
这里有新鲜出炉的Javascript教程，程序狗速度看过来！
JavaScript客户端脚本语言
Javascript 是一种由Netscape的LiveScript发展而来的原型化继承的基于对象的动态类型的区分大小写的客户端脚本语言，主要目的是为了解决服务器端语言，比如Perl，遗留的速度问题，为客户提供更流畅的浏览效果。
链表简介
链表是一种常见的数据结构，也属于线性表，但不会按线性的顺序来储存数据。而是在每一个节点中，储存了下一个节点的指针。可以看图理解。(有C语言基础的可能比较好理解)。
使用链表结构可以克服数组需要预先知道数据大小的缺点(C语言的数组需要预先定义长度)，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。
接下来就是介绍两种常见的链表: 单向链表，双向链表在JavaScript中的实现。
单向链表
链表中最简单的形式就是单向链表，链表中的节点都包含两个部分，第一部分储存着自身信息，第二部分则储存有指向下一节点的指针。最后一个节点则指向NULL:
JavaScipt中单向链表的实现
首先，创建一个构造函数。
/**
* 单向链表构造函数
*/
function LinkedList() {
/**
* 单向链表中节点的构造函数
* @param {Any} element 要传入链表的节点
*/
var Node = function(element) {
this.element = element;
//下个节点的地址
this.next = null;
}
//单向链表的长度
var length = 0;
//单向链表的头结点，初始化为NULL
var head = null;
}
不难看出，单向链表构造函数比栈与队列要复杂许多。
单向链表需要有如下的方法:
append方法:
说明: 向单向链表尾部添加元素。
实现:
/**
* 向单向链表尾部添加元素
* @param {Any} element 要加入链表的节点
*/
this.append = function(element) {
var node = new Node(element);
var current;
if (head == null) {
head = node;
} else {
// 当前项等于链表头部元素.
// while循环到最后一个，从而将该节点加入链表尾部。
current = head;
// 当next为null时，判定为false。退出循环。
while (current.next) {
current = current.next;
}
current.next = node;
}
length++;
};
insert方法:
说明: 向单向链表中某个位置插入元素。
实现:
/**
* 向单向链表中插入某个元素
* @param {Number} position 要插入的位置
* @param {Any} element 要插入的元素
* @return {Boolean} 插入成功返回true，失败返回false
*/
this.insert = function(position, element) {
if (position >= 0 && position <= length) {
var node = new Node(element);
var current = head;
var previous;
var index = 0;
if (position == 0) {
node.next = current;
head = node;
} else {
while (index++ < position) {
previous = current;
current = current.next;
}
previous.next = node;
node.next = current;
}
length++;
return true;
} else {
return false;
}
};
indexOf方法:
说明：寻找某个元素在单向链表中的位置。
实现:
/**
* 寻找某个元素在单向链表中的位置
* @param {Any} element 要寻找的元素
* @return {Number} 返回值>=0则代表找到相应位置
*/
this.indexOf = function(element) {
var current = head;
var index = -1;
while (current) {
if (element === current.element) {
return index;
}
index++;
current = current.next;
}
return -1;
};
remove方法:
说明: 移除给定的元素。
实现:
/**
* 移除给定的元素
* @param {Any} element 要移除的元素
* @return {Number} 返回值>=0表示移除成功
*/
this.remove = function(element) {
var index = this.indexOf(element);
return this.removeAt(index);
};
removeAt方法:
说明:移除单向链表中某个位置的元素。
实现:
/**
* 移除单向链表中某一个元素
* @param {Number} position 要移除元素的位置
* @return {Any} 移除成功返回被移除的元素，不成功则返回NULL
*/
this.removeAt = function(position) {
if (position > -1 && position < length) {
var current = head;
var previous;
var index = 0;
if (position == 0) {
// 因为之前head指向第一个元素，现在把head修改为指向第二个元素。
// 核心概念在于链表前后全靠指针链接，而非数组一般。
// 所以只需要改变head的元素。
head = current.next;
} else {
while (index++ < position) {
// previous指要操作元素位置之前的那个元素，current表示之后的那个元素。
previous = current;
current = current.next;
}
previous.next = current.next;
}
length--;
return current.element;
} else {
return null;
}
};
getHead方法:
说明:获取单向链表的头部。
实现:
/**
* 获取单向链表的头部
* @return {Any} 单向链表的头部
*/
this.getHead = function() {
return head;
}
isAmpty、toString、size方法
实现:
/**
* 判断单向链表是否为空
* @return {Boolean} 为空则返回true，不为空则返回false
*/
this.isAmpty = function() {
return length === 0
};
/**
* 将链表所有内容以字符串输出
* @return {String} 要输出的字符串
*/
this.toString = function() {
var current = head;
var string = '';
while (current) {
string += current.element;
current = current.next;
}
return string;
};
/**
* 返回单向链表长度
* @return {Number} 单向链表的长度
*/
this.size = function() {
return length;
};
双向链表
双向链表与单向链表很是相像。在单向链表中，只有指向下一个节点的链接。但在双向链表中，还有指向上一个节点的链接，是双向的。
JavaScipt中双向链表的实现
首先，依然是构造函数:
/**
* 双向链表的构造函数
*/
function DoublyLinkedList() {
/**
* 双向链表中节点的构造函数
* @param {Any} element 要传入链表的元素
*/
var Node = function(element) {
this.element = element;
this.prev = null;
this.next = null;
}
//双向链表的长度
var length = 0;
//双向链表的头结点，初始化为NULL
var head = null;
//双向链表的尾结点，初始化为NULL
var tail = null;
}
双向链表需要有如下的方法:
append方法:
说明: 添加元素到双向链表尾部
实现:
/**
* 向链表尾部添加元素
* @param {Any} element 要加入链表的节点
* @return {Any} 加入链表的节点
*/
this.append = function(element) {
var node = new Node(element);
if (head === null) {
head = node;
tail = node;
} else {
var previous;
var current = head;
while (current.next) {
current = current.next;
}
current.next = node;
node.prev = current;
tail = node;
}
length++;
return node;
};
insert方法:
说明: 向双向链表中某个位置插入元素。
实现:
/**
* 向链表中插入某个元素
* @param {Number} position 要插入的位置
* @return {Boolean} 插入成功返回true，失败返回false
*/
this.insert = function(position, element) {
if (position >= 0 && position <= length) {
var node = new Node(element);
var index = 0;
var previous;
var current = head;
if (position === 0) {
if (head === null) {
head = node;
tail = node;
} else {
current.prev = node;
node.next = current;
head = node;
}
} else if (position === length) {
current = tail;
current.next = node;
node.prev = current;
tail = node;
} else {
while (index++ < position) {
previous = current;
current = current.next;
}
previous.next = node;
node.prev = previous;
current.prev = node;
node.next = current;
}
length++;
return true;
} else {
return false;
}
};
removeAt方法:
说明:移除双向链表中某个位置的元素。
实现:
/**
* 移除链表中某一个元素
* @param {Number} position 要移除元素的位置
* @return {Any} 移除成功返回被移除的元素，不成功则返回false
*/
this.removeAt = function(position) {
if (position > -1 && position < length) {
var current = head;
var index = 0;
var previous;
if (position === 0) {
head = current.next;
if (length === 1) {
tail = null;
head.prev = null;
}
} else if (position === length - 1) {
current = tail;
tail = current.prev;
tail.next = null;
} else {
while (index++ < position) {
previous = current.prev;
current = current.next;
}
previous.next = current.next;
current.next.prev = previous;
}
length--;
return current.element;
} else {
return false;
}
};
showHead、showLength、showTail方法
实现:
/**
* 获取链表的头部
* @return {Any} 链表的头部
*/
this.showHead = function() {
return head;
};
/**
* 获取链表长度
* @return {Number} 链表长度
*/
this.showLength = function() {
return length;
};
/**
* 获取链表尾部
* @return {Any} 链表尾部
*/
this.showTail = function() {
return tail;
};
感想
链表这一节，基本全部都是先按需求写代码，写完后再和书上对比。发现简直被瞬间秒成渣。自己写的很多暗坑，逻辑也很混乱。看来还是太年轻了。