数据结构
列表
列表是一组有序的数据，每个列表中的数据项称为元素。
在JS中：
- 列表中的元素可以是任意的数据类型
- 列表中可以保存多少元素没有事先限定
- 列表中包含元素的个数称为列表的length
//定义列表
function list(){
this.listSize;//列表的元素个数
this.dataStore=[];//保存列表元素
this.pos;//列表当前位置、
this.append=append;//插入元素
this.find=find;//查找元素的位置
this.remove=remove;//删除元素
this.length=length;//获取长度
this.toString=toString;//显示列表中的元素
this.insert=insert;//插入元素
this.clear=clear;//清空列表
this.contains=contains;//判断值是否在列表中
this.font=font;//将当前位置移动到第一个元素
this.end=end;//将当前位置移动到最后一个元素
this.prev=prev;//将当前位置前移一位
this.next=next;//将当前位置后移一位
this.currPos=currPos;//输出列表的当前位置
this.moveTo=MoveTo;//将当前位置移动到指定的位置
this.hasNext=hasNext;//判断后一位
this.hasPrev=hasPrev;//判断前一位
this.getElement=getElement;//返回当前位置的元素
}
//给列表添加元素
function append(element){
this.dataStore[this.listSize++]=element;
}
//在列表中查找某个元素
//找到返回在列表中的位置，否则返回-1
function find(element){
for(let i=-;i<this.dataStore.length;i++){
if (this.dataStore[i]==element){
return i;
}
}
return -1;
}
//从列表中删除元素
function remove(element){
let 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){
let 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.length=0;//创建一个新数组
this.listSize=this.pos=0;
}
//判断给定值是否存在
function contains(element){
for(let i=0;i<this.dataStore.length;i++){
if(this.dataStore[i]==element){
return true;
}
}
return false;
}
//将列表的当前位置移动到第一个元素
function font(){
this.pos=0;
}
//移动到最后一个元素
function end(){
this.pos=this.listSize-1;
}
//上一个元素
function prev(){
-- this.pos;
}
//下一个元素
function next(){
if(this.pos<this.listSize){
++ this.pos;
}
}
//返回当前位置
function currPos(){
return this.pos;
}
//移动到指定位置
function moveTo(positon){
this.pos=postion;
}
//当前元素
function getElement(){
return this.dataStore[this.pos];
}
//判断下一个
function hasNext(){
return this.pos<this.listSize;
}
//判断上一个
function hasPrev(){
return this.pos>=0;
} 列表可以用来作为简单的查询系统基础实现，带有字典类型的，比如书籍管理、影碟管理等等。如果对数据存储的顺序不重要，也不必对数据进行查找，那么列表就是一种再好不过的存储结构。
栈
栈是一种特殊的列表，栈内的元素只能通过列表的一端访问，这一端称为顶栈，是一种后入先出的数据结构。
由于栈具有后入先出的特点，所以任何不在栈顶的元素都无法访问，为了得到栈底的元素，就必须拿掉上面的元素。
//定义栈
function Stack(){
this.dataStore=[];
this.top=0;
this.push=push;
this.pop=pop;
this.peek=peek;
this.length=length;
}
//添加新元素
function push(element){
this.dataStore[this.top++]=element;
}
//弹出栈顶元素
function pop(){
return this.dataStore[--this.top];
}
//返回数组第top-1个元素位置的元素（栈顶元素）
function peek(){
return this.dataStore[this.top-1];
}
//获取栈的大小
function length(){
return this.top;
}
//清空栈
function clear(){
this.top=0;
} 数制间的互相转换
假设要把数字n转换为以b为基数的数组，实现的思路：
- 最高位为n%b,将此位压入栈
- 使用n/b代替n
- 重复前两步，直到n等于0且没有余数
- 持续将栈内元素弹出，直到栈为空，依次把元素排列，得到转换后的字符串
//任意数转换为2-9进制
function mulBase(num,base){
let s=new Stack();
while(num>0){
s.push(num%base);
num=Math.floor(num/=base);
}
let converted="";
while(s.length()>0){
converted +=s.pop();
}
return converted;
} 回文
回文是说：一个单词、短语或者数字，从前往后写和从后往前写都是一样的。
用栈可以轻松判断一个字符串是否是回文。将拿到的字符串从左到右压入栈，当字符串的每个字符都入栈之后，栈内就保存了一个反转后的字符串，最后的字符在栈顶，第一个字符在栈底。
通过持续弹出栈中的每个字符就可以得到一个新字符串，该字符串与原来的字符串相反，只需要比较这两个字符串就好了，如果相等说明是回文
function isPalindrome(word){
let s=new Stack();
for(let i=0;i<word.length;i++){
s.push(word[i]);
}
let rword='';
while(s.length()>0){
r.word += s.pop();
}
if(word==rword){
return true;
}else{
return false;
}
} 递归
用栈来模拟递归过程，比如说连乘：
function factorial(n){
if(n===0) return 1;
else return n*factorial(n-1);
}
//用栈来模拟过程
function fact(){
let s=new Stack();
while(n>1){
s.push(n--);
}
let product=1;
while(s.length()>0){
product *= s.pop();
}
return product;
} 队列
队列也是一种列表，它只能在队尾插入元素，在队首删除元素，队列用于存储按顺序排列的数据，先入先出。
function Queue(){
this.dataStore=[];
this.enqueue=enqueue;
this.dequeue=dequeue;
this.front=front;
this.back=back;
this.toString=toString;
this.empty=empty;
}
//队尾添加一个数据
function enqueue(){
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(){
let retStr="";
for(let 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;
}
} 方块舞舞伴
使用队列来模拟跳方块舞的人，当男男女女来到舞池，他们按照自己的性别排成两队，当舞池中有空的地方空出来的时候，选两队中的第一个组成舞伴，他们身后的人各自往前移动一位，变成新的队首。
把男男女女的信息保存在一个文件中：dancer.txt ,里面保存了舞者的性别、姓名。
//舞者信息被保存在Dancer对象中
function Dancer(name,sex){
this.name=name;
this.sex=sex;
}
//读取全部舞者信息
function getDancer(males,females){
let names=read("dancer.txt").split("\n");
names=names.map(item=>item.tirm());//数据处理
for(let i=0;i<names.length;i++){
let dancer=names[i].split(" ");
let sex=dancer[0];
let name=dancer[1];
if(sex=='F'){
females.equeue(new Dancer(name,sex));
}else{
males.queue(new Dancer(name,sex));
}
}
}
//配对舞伴
function dance(males,females){
print("这对舞伴是：");
while(!males.empty()&&!females.empty()){
let person=females.dequeue();
print("女方是"+person.name);
person=males.dequeue();
print("男方式"+person.name);
}
}
基数排序
对于0-99的数字，基数排序将数据集扫描两次，第一次按个位上的数字进行排序，第二次按十位上的数字进行排序。每个数字根据对应位上的数值被分在不同的盒子里。
首先需要9个队列，每个对应一个数字，将所有的队列保存在一个数组里，使用取余和除法决定个位和十位。剩余部分将数组加入响应的队列，根据个位数值对齐重新排序，然后再根据十位上的数值进行排序。
//按位 分配到响应的队列中
function distribute(nums,queues,n,digit){//digit表示个位和十位上的值
for(let i=0;i<n;i++){
if(digit==1){//个位
queue[nums[i]%10].enqueue(nums[i]);
}else{//十位
queue[Math.floor(nums[i]/10)].enqueue(nums[i]);
}
}
}
//排序
function colllect(queues,nums){
let i=0;
let(let digit=0;digit<10;i++){
while(!queues.empty()){
nums[i++]=queues[digit].dequeue();
}
}
}
//展示
function display(arr){
for(let i=0;i<arr.length;i++){
putstr(arr[i]+" ");
}
}
//主程序
var queues=[];
for(let i=0;i<10;i++){
queues[i]=new Queue();//建9个队列
}
let nums=[];//待排序的数组
distribute(nums,queues,10,1);
collect(queues,nums);
distribute(nums,queues,10,10);
collect(queues,nums);
display(nums); 优先队列
在优先队列中删除元素时，需要考虑优先权的限制，优先级高的先于优先级低的，同样优先级的按照先来先服务。
//优先队列
function PQueue(name,code){
this.name=name;
this.code=code;//优先级
}
//修改dequeue方法，让它删除队列中最高优先级的元素，规定编码越小优先级越高。
function dequeue(){
let entry=0;
for(let i=0;i<this.dataStore.length;i++){
if(this.dataStore[i].code<this.dataStore[entry].code){
entry=i;
}
}
return this.dataStore.splice(entry,1);
}
//修改显示方法
function toString(){
let retStr="";
for(let i=0;i<this.dataStore.length;i++){
retStr+=this.dataStore[i].name+ " Code:" + this.dataStore[i].code + "\n";
}
return retStr;
} 链表
数组的缺点
- 在一些编程语言中，数组的长度是固定的，所以当数组已经被数据填满时，如果需要加入新的元素就会非常困难，在数组中添加和删除，都需要把其他元素向前或者向后。
- 在js中不存在这个问题，因为用splice()方法不需要再访问数组中的其他元素了。JS中的数组主要问题是，他们被实现成了对象，和其他语言相比，效率很低。
链表
链表是一组节点组成的集合，每个节点都使用一个对象的引用指向它的后继，指向另一个节点的引用叫做链。
单链表
//定义节点
function node(element){
this.element=element;
this.next=null;
}
//定义链表
function LList(){
this.head=new Node("head");
this.find=find;
this.insert=insert;
this.remove=remove;
this.display=display;
this.findPrevious=findPrevious;
}
//展示
function display(){
let curNode=this.head;
while(curNode.next !=null){
console.log(curNode.next.element);
curNode=currnode.next;
}
}
//查找
function find(item){
let curNode=this.head;
while(curNode.element!=null){
curNode=curNode.next;
}
return curNode;
}
//插入
function insert(newELement,item){
let newNode=new Node(newELement);
let current=this.find(item);
newNode.next=current.next;
current.next=newNode;
}
//找到当前节点的前一个节点
function findPrevious(item){
let curNode=this.head;
while((curNode.next!=null)&&(curNode.next.element!=item)){
curNode=curNode.next;
}
return curNode;
}
//删除元素
function remove(item){
let preNode=this.findPervious(item);
if(preNode!=null){
preNode.next=preNode.next.next;
}
} 双向链表
//节点，添加上一个节点
function Node(element){
this.element=element;
this.next=null;
this.previous=null;
}
//插入，需要设置前驱节点
function insert(element,item){
let newNode=new Node(newElement);
let current=this.find(item);
newNode.next=current.next;
newNode.previous=current;
current.next=newNode;
}
//删除，不需要查找前驱节点，直接获取即可
function remove(item){
let curNode=this.find(item);
if(curNode.next!=null){
curNode.previous.next=curNode.next;
curNode.next.previous=curNode.previous;
curNode.next=null;
curNode.previous=null;
}
}
//查找最后一个节点
function findLast(){
let curNode=this.head;
while(curNode.next!=null){
curNode=curNode.next;
}
return curNode;
}
//返序显示双向链表中的元素
function displayReverse(){
let curNode=this.head;
curNode=this.findLast();
while(curNode.previous !=null){
console.log(curNode.element);
curNode=curNode.previous;
}
} 循环链表
特点：链表的尾节点会指向头节点。
如果希望可以从后往前遍历链表，但是又不想付出额外的代价来创建一个双向链表，那么可以使用循环链表，从循环列表的尾节点向后移动，就等于从后向前遍历链表。
function LList(){
this.head=new Node("head");
this.head.next=this.head;
//和单链表没什么区别
}
//display方法需修改
function display(){
let curNode=this.head;
while((curNode.next!=null)&&(curNode.next.element!="head")){
print(curNode.next.element);
curNode=curNode.next;
}
} 二叉树和二叉查找树
树是一种非线性数据结构，以分层的方式存储数据。树被用于存储具有层级关系的数据或者有序列表，比如文件系统的文件等。
二叉树是一种特殊的树，它的子节点不超过2个，通过将子节点的个数限定为2，可以写出高效的程序在树中插入 、删除和查找。
选择二叉树的理由：在二叉树上查找很快（链表上不行），在二叉树上添加或者删除元素很快（数组不行）。
//定义节点
function Node(data,left,right){
this.data=data;
this.left=left;
this.right=right;
this.show=fucntion(){return this.data;};
}
//二叉查找树 BST
function BST(){
this.root=null;
this.insert=insert；
this.inOrder=inOrder;
}
function insert(data){
let n=new Node(data,null,null)
//设根节点
if(this.root==null){
this.root=n;
}else{
//待插入元素小于当前节点，设为原节点的左节点，左节点为空则插入，否则继续；大于则为右节点。
let current=this.root;
let parent;
while(true){
parent=current;
if(data<current.data){
current=current.left;
if(current==null){
parent.left=n;
break;
}
}else{
current=current.right;
if(current==null){
parent.right=n;
break;
}
}
}
}
}
//前序遍历 上左右
function preOrder(node){
if(node !=null){
console.log(node.show());
preOrder(node.left);
preOrder(node.right);
}
}
//中序遍历 左上右
function inOrder(node){
if(node !=null){
inOrder(node.left);
console.log(node.show());
inOrder(node.right);
}
}
//后序遍历 左右上
function postOrder(node){
if(node !=null){
postOrder(node.left);
postOrder(node.right);
console.log(node.show());
}
}
//查找最小值 ---最左边的节点
function getMin(){
let current=this.root;
while(current.left!=null){
current=current.left;
}
return current.data;
}
//查找最大值 ---最右边的节点
function getMax(){
let current=this.root;
while(current.right!=null){
current=current.right;
}
return current.data;
}
//查找给定值
function find(data){
let current=this.root;
while(current !=null){
if(current.data==data){
return current;
}else if(current.data<data){
current=current.right;
}else{
current=current.left;
}
}
return null;
}
//从查找树上删除节点
//如果待删除的节点包含两个子节点：查找右子树上的最小值
function remove(data){
root=removeNode(this.root,data);
}
function removeNode(node,data){
if(node==null) return null;
if(data==node.data){
//没有子节点 父节点指向它的指向null
if(node.left==null&&node.right==null){
return null;
}
//没有左子节点 指向右子节点
if(node.left==null){
return node.right;
}
//没有右子节点 指向左子节点
if(node.right==null){
return node.left;
}
//节点有两个子节点,找到右子树的最小值
let tempNode=getSmallest(node.right);
node.data=removeNode(node.right,tempNode.data);
return node;
}
else if(data<node.data){
node.left=removeNode(node.left,data);
return node;
}else{
node.right=removeNode(node.right,data);
return node;
}
} 计数
BST可以用于记录一组数据集中数据出现的次数。比如使用BST记录考试成绩的分布。
function Node(data,left,right){
this.data=data;
this.count=1;//成绩出现频次
this.left=left;
this.right=right;
this.show=show;
}
//成绩次数增加，需要更新节点的count
function update(data){
let grade=this.find(data);
grade.count++;
return grade;
}
//其他方法不需要修改 图和图的算法
图由边的集合及顶点的集合组成。边由顶点对(V1,V2)定义，V1和V2分别是图中的两个顶点。顶点也有权重（也叫成本）。如果一个图的顶点对是有序的，则可以称之为有向图，在对有向图。在对有向图中的顶点排序之后，便可以在两个顶点之间绘制一个箭头。有向图表明了顶点的流向。如果图是无序的，则成为无向图。
图中一系列顶点构成路径，路径由所有的顶点都由边连接，路径长度用路径图中第一个顶点到最后一个顶点之间边的数量表示。由指向自身的顶点组成的路径称为环，环的长度为0。
圈是至少有一条边的图，且路径的第一个顶点和最后一个顶点相同。无论是有向图还是无向图，只要是没有重复边或重复顶点的圈，就是一个简单圈。除了第一个和最后一个顶点之外，路径的其他顶点有重复的称为平凡圈。
如果两个顶点之间有路径，那么这两个顶点是强连通的。如果有向图的所有顶点都是强连通的，那么这个图也是强连通的。
构建图
//保存顶点和边
function Vertex(label,wasVisited){
this.label=label;//标识顶点
this.wasVistied=wasVisited;//顶点是否被访问过
}
//把所有顶点保存到数组里，在图类里，可以通过它们在数组中的位置引用
//表示图的边的方法称为邻接表或者邻接表数组。将边存储为由顶点的相邻顶点列表构成的数组，并以此顶点作为索引。这样的好处是，当在程序中引用一个顶点时，可以高效地访问与这个顶点相连的所有顶点的列表。
//另一种方法是邻接矩阵，它是一个二维数组，其中的元素表示两个顶点之间是否有一条边
function Graph(v){
this.vertices=v;//顶点
this.edges=0;//边
this.adj=[];//与顶点数相同的数组记录顶点的相邻元素情况
for(let i=0;i<this.vertices;i++){
this.adj[i]=[];
this.adj[j].push("");
}
this.addEdge=addEdge;
this.showGraph=showGraph;
}
//添加边的关系
function addEdge(v,w){
this.adj[v].push(w);
this.adj[w].push(v);
this.adges++;
}
//打印所有顶点及其相邻顶点列表来显示图
function showGraph(){
for(let i=0;i<this.vertices;i++){
putstr(i+"->");
for(let j=0;j<this.vertices;j++){
if(this.adj[i][j] != undefined){
putstr(this.adj[i][j]+' ');
}
}
print();
}
} 搜索图
深度优先搜索
从一条路径的起始顶点开始追溯，直到到达最后一个顶点，然后回溯，继续追溯下一条路径，直到到达最后一个顶点，如此往复，直到没有路径为止。这不是在搜索特定的路径，而是通过搜索来查看在图中有哪些路径可以选择。
深度优先搜索算法：访问一个没有访问的顶点，把它标记为已访问，再递归地去访问在初始顶点的邻接中其他没有访问过的顶点。
function dfs(v){
this.marked[v]=true;
for each(var w in this.adj[v]){
if(!this.marked[w]){
this.dfs(w);
}
}
} 广度优先搜索
从第一个顶点开始，尝试访问尽可能靠近它的顶点，本质上，这种搜索在图上是逐层移动的，首先检查最靠近第一个顶点的层，再逐渐向下移动到离起始顶点最远的层。
首先，需要一个数组来保存从一个顶点到下一个顶点的所有边，将数组命名为edgeTo,因为从始至终都是广度优先搜索函数，所以每次都会遇到一个没有标记的顶点，除了对它进行标记之外，还会从邻接列表中我们正在搜索的那个顶点添加一条边到这个顶点。
//需要给Graph类添加一个参数 this.edgeTo=[]
function bfs(s){
let queue=[];
this.marked[s]=true;
queue.push(s);//添加到队尾
while(queue.length>0){
let v=queue.shift();//从队首移除
if(v==undefined){
print("Visited vertex:"+v);
}
for each(var w in this.adj[v]){
if(!this.marked[w]){
this.edgeTo[w]=v;
this.marked[w]=true;
queue.push(w);
}
}
}
}
//创建一个栈，存储与指定顶点有共同边的所有顶点
function pathTo(v){
let source=0;
if(!this.hasPathTo(v)){return undefined;}
var path=[];
for(let i=v;i!=source;i=this.edgeTo[i]){
path.push(i);
}
path.push(source);
return path;
}
function hasPathTo(v){
return this.marked[v];
} 
京公网安备 11010502036488号