javascript数据结构5-链表（包括循环链表 双向链表）

发表于 | 更新于 | 分类于

1.一般链表

图解链表：
这里写图片描述
链表
这里写图片描述
这里写图片描述

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
<!doctype html>
<html>
  <head>
    <meta charset="utf-8" >
  </head>
  <body>
    <script>
    function Node(ele) {
        this.ele=ele;
        this.next=null;
      }
      
    function LList(){
    	   this.head=new Node("head");
     	   this.find=find;
      	   this.insert=insert;
           this.findPrevious=findPrevious;
           this.remove=remove;
           this.display=display;
       // this.Node=Node;
      }
      
      function find(item){
        	var currNode=this.head;
     		 // document.write(currNode);
      		 // console.log(currNode);
            while(currNode.ele!=item)
      		  {currNode=currNode.next;}
      		  return currNode;
      }
      function insert(newElement,item)
      {
      var newNode=new Node(newElement);
      var current=this.find(item);
       newNode.next=current.next;
       current.next=newNode;
      }
      function display(){
      var currNode=this.head;
        while(!(currNode.next==null))
        {document.write(currNode.next.ele+" ");
         currNode=currNode.next;
        }
      }
      
      function findPrevious(item){
        var currNode=this.head;
        while(!(currNode.next==null)&&(currNode.next.ele != item)){
            currNode=currNode.next;
        }
           return currNode;
      }
      function remove(item){
         var prevNode=this.findPrevious(item);
       // document.write(prevNode.ele);
        if(!(prevNode.next==null)){
           prevNode.next=prevNode.next.next;
        }
      }
     var cities=new LList();
      document.write("=========插入数据==========<br/>");
      cities.insert("Con","head");
      cities.insert("Rus","Con");
      cities.insert("Alm","Rus");
      cities.insert("Tom","Alm");
      cities.display();
      document.write("<br/>=========删除数据==========<br/>");
      cities.remove("Rus");
      cities.display();
      
    </script>
  </body>
</html>

对比：find() findPrevious()
while语句多了条件!(currNode.next==null)
这个能保证remove()调用时候，删除链表中没有的节点，会返回最后一个节点，这样remove()执行没有任何结果，而链表能够正常的显示。find()中不能使用，原理一样，想一想为什么？

2.双向链表

这里写图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
	<title>无标题</title>
</head>
<body>
	<script type="text/javascript">
	function Node(element) {
			this.element = element;
			this.next = null;
			this.previous = null;
	}
	function LList() {
		this.head = new Node("head");
		this.find = find;
		this.insert = insert;
		this.display = display;
		this.remove = remove;
		this.findLast = findLast;
		this.dispReverse = dispReverse;
	}
	function dispReverse() {
		var currNode = this.head;
		currNode = this.findLast();
		while (!(currNode.previous == null)) {
			document.write(currNode.element+" ");
			currNode = currNode.previous;
		}
	}
	function findLast() {
		var currNode = this.head;
		while (!(currNode.next == null)) {
			currNode = currNode.next;
		}
		return currNode;
	}
	function remove(item) {
		var currNode = this.find(item);
		if (!(currNode.next == null)) {
			currNode.previous.next = currNode.next;
			currNode.next.previous = currNode.previous;
			currNode.next = null;
			currNode.previous = null;
		}
	}
	//findPrevious 没用了，注释掉
	/*function findPrevious(item) {
	var currNode = this.head;
	while (!(currNode.next == null) &&
	(currNode.next.element != item)) {
	currNode = currNode.next;
	}
	return currNode;
	}*/
	function display() {
		var currNode = this.head;
		while (!(currNode.next == null)) {
		document.write(currNode.next.element+" ");
		currNode = currNode.next;
		}
	}
	function find(item) {
		var currNode = this.head;
		while (currNode.element != item) {
		currNode = currNode.next;
		}
		return currNode;
	}
	function insert(newElement, item) {
		var newNode = new Node(newElement);
		var current = this.find(item);
		newNode.next = current.next;  //1
		newNode.previous = current;   //2
		current.next = newNode;       //3
	}
	var cities = new LList();
	cities.insert("Conway", "head");
	cities.insert("Russellville", "Conway");
	cities.insert("Carlisle", "Russellville");
	cities.insert("Alma", "Carlisle");
	//cities.insert("C", "Russellville"); //按照原程序写的话，出现很大问题
	cities.display();
	document.write("<br/>");
	cities.remove("Carlisle");
	cities.display();
	document.write("<br/>");
	cities.dispReverse();
</script>
</body>
</html>

这是可以完全运行，但是加上黄色的一句话（从中间随便插入一句）就会出现问题

1
2
3
Conway Russellville C Carlisle Alma 
Conway Russellville Alma   //C不显示了
Alma Russellville Conway

这里写图片描述
看链表结构：
1,2,3条线都有，但是从中间插入的时候，会发现缺少4是不行的，于是insert()函数加上这句：

1
2
3
if(newNode.next!=null){
	newNode.next.previous=newNode;
}

就行了。同样书中的删除节点图解，也是知识考虑了在尾部删除

这里写图片描述

存储一个对象的时候：点对象

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>Document</title>
</head>
<body>
<script>
  
function Node(element){
  this.element=element;
  this.next=null;
}
  
  function Point(x,y){
   this.x=x;
    this.y=y;
  }
  function LList(){
    this.head=new Node('head');
    //this.head.next=this.head;
    this.find=find;
    this.insert=insert;
    this.display=display;
    this.remove=remove;
    this.findPrevious=findPrevious;
  }
  
  function display(){
    var curr=this.head;
    while(!(curr.next==null)){
       document.write(curr.next.element.x+'/'+curr.next.element.y);
      curr=curr.next;
    }
    return curr;
  }
  
    function find(item){
      var currNode=this.head;
      while(!(currNode.element==item)){currNode=currNode.next;
  }
  return currNode;
}
  
  function insert(newElement, item) {
   var newNode = new Node(newElement);
   var current = this.find(item);
   newNode.next = current.next;
   current.next = newNode;
}
  
  function  findPrevious(item){
    var currNode=this.head;
    while(!(currNode.next==null)&&(currNode.next.element!=item)){
      currNode=currNode.next;
    }
    return currNode;
  }
  
   function remove(item){
     var prevNode=this.findPrevious(item);
     if((prevNode.next!=null)){
       prevNode.next=prevNode.next.next;
     }
   }
   var p1=new Point(1,2);
   var p2=new Point(3,4);
   
   //document.write(p2.x);
  // console.log(p1);
   var points=new LList();
    points.insert(p1,'head');
    points.insert(p2,p1);
    points.display();
</script>
</body>
</html>

3.循环链表

这里写图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
<html>
<head>
	<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
	<title>循环链表</title>
</head>
<body>
	<script type="text/javascript">
	function Node(element) {
			this.element = element;
			this.next = null;
	}
	function LList() {
		this.head = new Node("head");
		this.head.next=this.head;
		this.find = find;
		this.insert = insert;
		this.display = display;
		this.remove = remove;
	}
	function remove(item) {
		var currNode = this.find(item);
		if (!(currNode.next == null)) {
			currNode.previous.next = currNode.next;
			currNode.next.previous = currNode.previous;
			currNode.next = null;
			currNode.previous = null;
		}
	}
	
	function display() {
		var currNode = this.head;
		while (!(currNode.next.element=="head")&&!(currNode.next == null)) {
			document.write(currNode.next.element+" ");
			currNode = currNode.next;
		}
	}
	function find(item) {
		var currNode = this.head;
		while (!(currNode.next.element=="head")&&(currNode.element != item)) {
			currNode = currNode.next;
		}
		return currNode;
	}
	function insert(newElement, item) {
		var newNode = new Node(newElement);
		var currNode = this.find(item);
		if(!(currNode.next.element=="head")){
			newNode.next=currNode.next;  //从中间插入
			currNode.next=newNode;
		}else{ //从尾部插入
			newNode.next=this.head;  //从中间插入
			currNode.next=newNode;
		}
	}
	var cities = new LList();
	cities.insert("Conway", "head");
	cities.insert("Russellville", "Conway");
	cities.insert("Carlisle", "Russellville");
	cities.insert("Alma", "Carlisle");
	cities.insert("C", "Russellville"); 
	//cities.insert("D", "Rus"); 
	cities.display();
	
</script>
</body>
</html>

javascript数据结构4-队列2-基数排序

发表于 | 更新于 | 分类于

第一次按个位上的数字进行排序，第二次按十位上的数字进行排序

排序：91, 46, 85, 15, 92, 35, 31, 22
经过基数排序第一次扫描之后，数字被分配到如下盒子中：

1
2
3
4
5
6
7
8
9
10
Bin 0:
Bin 1: 91, 31
Bin 2: 92, 22
Bin 3:
Bin 4:
Bin 5: 85, 15, 35
Bin 6: 46
Bin 7:
Bin 8:
Bin 9:

根据盒子的顺序，对数字进行第一次排序的结果如下：
91, 31, 92, 22, 85, 15, 35, 46
然后根据十位上的数值再将上次排序的结果分配到不同的盒子中：

1
2
3
4
5
6
7
8
9
10
Bin 0:
Bin 1: 15
Bin 2: 22
Bin 3: 31, 35
Bin 4: 46
Bin 5:
Bin 6:
Bin 7:
Bin 8: 85
Bin 9: 91, 92

Javascript实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
<!doctype html>
<html>
<head>
<meta charset=utf-8 /> 
	<title>Queue Sample</title>
</head>
<body>
      
   <script type="text/javascript">
   	    /*定义队列*/
   	    function Queue(){
   	    	this.dataStore=[];
   	    	this.enqueue=enqueue;
   	    	this.dequeue=dequeue;
          this.front=front;
          this.back=back;
          this.toStr=toStr;
          this.isEmpty=isEmpty;
   	    }
     
     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 toStr(){
      	var retStr="";
        for(var i=0;i<this.dataStore.length;i++){
        	retStr+=this.dataStore[i]+"\n";
        }
        //console.log(retStr);
         return retStr;
     }
     //判断是否为空
     function isEmpty(){
      	  if(this.dataStore.length==0){
          		return true;
          	}else{
           		return false;   
           	}
     }
  //========================================================================
     function distribute(nums, queues, n, digit) {
        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].isEmpty()) {  
            nums[i++] = queues[digit].dequeue();
            }
          }
     }
     function dispArray(arr){
       for (var i = 0; i < arr.length; i++) {
         document.write(arr[i]+" ");
         // document.write('<br/>');
       };
     }
    var  N=200;//N是要排序的个数 基数排序测试时间：: 4.000ms
    var queues=[];
    for (var i = 0; i < 10; i++) {
      queues[i]=new Queue(); //分别存储Bin0--bin9
     };
    var nums=[];
    for (var i = 0; i < N; i++) {
       nums[i]=Math.floor(Math.random()*101);
       // document.write(nums[i]);
       // document.write('<br/>');
    }
    
    /*********************/
    /*测试一下时间*/
    console.time("基数排序测试时间：");//改变N的值进行测试
    document.write("原数据：");
    dispArray(nums);
    distribute(nums,queues,N,1);
    collect(queues,nums);   //nums分散了，收集起来
    document.write("<br/>个位排序后：");
    dispArray(nums);
    distribute(nums,queues,N,10);
    collect(queues,nums); 
    document.write("<br/>基数排序后：");  
    dispArray(nums);
    console.timeEnd("基数排序测试时间：");
    
   </script>
    
</body>
</html>

javascript数据结构4-队列

发表于 | 更新于 | 分类于

队列是一种先进先出（FIFO，first-in-first-out）的数据结构

javascript代码实现队列：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
<!doctype html>
<html>
<head>
<meta charset=utf-8 /> 
	<title>Queue Sample</title>
</head>
<body>
      
   <script type="text/javascript">
   	    /*定义队列*/
   	    function Queue(){
   	    	this.dataStore=[];
   	    	this.enqueue=enqueue;
   	    	this.dequeue=dequeue;
          this.front=front;
          this.back=back;
          this.toStr=toStr;
          this.isEmpty=isEmpty;
   	    }
     
     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 toStr(){
      	var retStr="";
        for(var i=0;i<this.dataStore.length;i++){
        	retStr+=this.dataStore[i]+"\n";
        }
        //console.log(retStr);
         return retStr;
     }
     //判断是否为空
     function isEmpty(){
      	  if(this.dataStore.length==0){
          		return true;
          	}else{
           		return false;   
           	}
     }
     var que=new Queue();
     que.enqueue("Tom");
     que.enqueue("Sam");
     que.enqueue("Pom");
     console.log(que.dataStore.length);
     document.write(que.toStr());
     que.dequeue();
     document.write(que.toStr());
    console.log(que.toStr);

	</script>
  </body>
</html>

举个案例：
常用队列模拟排队的人。下面我们使用队列来模拟跳方块舞的人。
当男男女女来到舞池，他们按照自己的性别排成两队。当舞池中有地方空出来时，选两个队列中的第一个人组成舞伴。他们身后的人各自向前移动一位，变成新的队首。当一对舞伴迈入舞池时，主持人会大声喊出他们的名字。当一对舞伴走出舞池，且两排队伍中有任意一队没人时，主持人也会把这个情况告诉大家。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
<!doctype html>
<html>
<head>
<meta charset=utf-8 /> 
	<title>Queue Sample</title>
</head>
<body>
      
   <script type="text/javascript">
   	    /*定义队列*/
   	    function Queue(){
   	    	this.dataStore=[];
   	    	this.enqueue=enqueue;
   	    	this.dequeue=dequeue;
          this.front=front;
          this.back=back;
          this.toStr=toStr;
          this.isEmpty=isEmpty;
   	    }
     
     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 toStr(){
      	var retStr="";
        for(var i=0;i<this.dataStore.length;i++){
        	retStr+=this.dataStore[i]+"\n";
        }
        //console.log(retStr);
         return retStr;
     }
     //判断是否为空
     function isEmpty(){
      	  if(this.dataStore.length==0){
          		return true;
          	}else{
           		return false;   
           	}
     }
    
      //舞蹈员性别  姓名
    var  allStr="F Shun F Tim M Huipin M Lanlan F Ping F Li F Lou M Funr F Sun M Pop";  
     
      function Dancer(name,sex){
      	this.name=name;
        this.sex=sex;
      }
     
     //男女分队
     function getDancers(males,females){
          var numbers=allStr.split(" ");
         //document.write(numbers);
          //console.log(numbers);
          for(var i=0;i<numbers.length-1;++i){
             //var dances=numbers[i].trim();
             var sex=numbers[i];
             i++;
             var name=numbers[i]; 
            //console.log(name);
            //console.log(sex);
            if(sex == "F"){  //??????
            	 famaleDances.enqueue(new Dancer(name,sex));
                 console.log(famaleDances);
            }else{
            	 maleDances.enqueue(new Dancer(name,sex));//整体对象存在队列中
            }
         }
     } 
       //队首男女就是要出队的
       function dance(males,famales){
       		document.write("The dance parter are: ");
            document.write("<br />");
            while(!males.isEmpty() && !famales.isEmpty()){
                fperson=famales.dequeue();
               // console.log(fperson);
                document.write("The Famale dance  is:"+fperson.name);               
                person=males.dequeue();
                document.write(" and The Male dance  is:"+person.name);
              	document.write("<br />");
            }
       } 
      var maleDances=new Queue();
      var famaleDances=new Queue();
         // document.write("1");
      getDancers(maleDances,famaleDances);
      dance(maleDances,famaleDances);
     
       if(!famaleDances.isEmpty()){
          document.write(famaleDances.front().name+"is waiting");
       }
       
       if(!maleDances.isEmpty()){
          document.write(maleDances.front().name+"is waiting");
       }
   </script>
</body>
</html>

javascript数据结构3-栈

发表于 | 更新于 | 分类于

后进先出（LIFO,last-in-first-out）的数据结构
类比：堆叠盘子，只能从上面拿走盘子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> 
	<title>栈</title>
</head>
<body>
   <script type="text/javascript">
		function Stack() {
		   this.dataStore = [];
		   this.pos = 0;
		   this.push=push;
		   this.pop=pop;
		   this.peek=peek;
		   this.clear = clear;
		   this.length=length;
		}
        
        function push(element){
        	this.dataStore[this.pos++]=element;
        }
        function peek(){
        	return this.dataStore[this.top-1];
        }
        function pop(){
        	return this.dataStore[--this.top];
        }
        function clear(){
        	this.top=0;
        }
        function length(){
        	return this.top;
        }
       /************************************************************************/
       	var s=new Stack();
       	s.push("Tom");
       	s.push("Som");
       	s.push("Dom");
       	s.push("Fom");
       	// document.write(s.dataStore);
       	console.log(s);
   </script>
</body>
</html>

例子：
十进制转化为二进制，使用栈实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*数制间的相互转换*/
        function mulBase(num,base){
        	var s=new Stack();
        	do{
        		s.push(num% base);
        		num=Math.floor(num /=base);
        	}while(num > 0);
        	var cov="";
          console.log(s.length());
        	while(s.length() >0){
        		cov += s.pop();
        		
        	}
        	return cov;
        }
       var num=32;
       var newNum=mulBase(32,2);  //十进制转换为二进制
       console.log(newNum);
       document.write(newNum);

javascript数据结构2-列表

发表于 | 更新于 | 分类于

1. 类型定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
listSize（属性）         列表的元素个数
pos（ 属性）             列表的当前位置
length（ 属性） 	 	  返回列表中元素的个数
clear（ 方法）  		  清空列表中的所有元素
toString（ 方法）  	  返回列表的字符串形式
getElement（ 方法） 	  返回当前位置的元素
insert（ 方法）  		  在现有元素后插入新元素
append（ 方法） 		  在列表的末尾添加新元素
remove（ 方法） 		  从列表中删除元素
front（ 方法）  		  将列表的当前位置设移动到第一个元素
end（ 方法）  			  将列表的当前位置移动到最后一个元素
prev（方法）  			  将当前位置后移一位
next（ 方法）  	      将当前位置前移一位
currPos（ 方法）  		  返回列表的当前位置
moveTo（方法） 	      将当前位置移动到指定位置

2.实现列表类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> 
	<title>实现列表类</title>
</head>
<body>

<script type="text/javascript">
	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;
}

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 toString() {
    return this.dataStore;
}

 function front(){
  	// return this.dataStore[0];
  	//或者
  	 this.pos=0;
  }
function getElement(){
	return this.dataStore[this.pos];
}
var names = new List();
names.append("Cynthia");
names.append("Raymond");
names.append("Barbara");
console.log(names.toString());
names.remove("Raymond");
console.log(names.toString());
// console.log(names.front());
names.front();
console.log(names.getElement());
</script>
</body>
</html>

3.实际例子

从txt文件中读取数据（注意：这种方法只是适合在IE浏览器）
文档内容：

1.sam
2.tim
3.jom
4.dim
5.pop
6.hello
7.ming

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> 
	<title>无标题</title>
</head>
<body>
  <script type="text/javascript">
  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;
  }
  
  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 toString(){
  	return this.dataStore;
  }

  function front(){
  	// return this.dataStore[0];
  	 this.pos=0;
  }
    function end(){
  	// return this.dataStore[0];
  	 this.pos=this.listSize-1;
  }
  function currPos(){
  	return this.pos;
  }
  function next(){
  	if(this.pos<this.listSize-1){
  		++this.pos();
  	}
  }
	function getElement(){
		return this.dataStore[this.pos];
	}
  function createArr(){
  	// var arr=read(file).split("/n");
  	//读取文件
  	var s=[],arr=[];
  	  var fso, f1, ts;
      var ForReading = 1;
      var src="E:\\jsDS\\test.txt";
      fso = new ActiveXObject("Scripting.FileSystemObject");
      ts = fso.OpenTextFile(src,1,true); 
      // document.all.mailbdy.value=ts.ReadAll();
      while (!ts.AtEndOfStream) 
		{ 
			str=ts.Readline(); 
      	    // s=str.split("\n");
      	    s.push(str);
		}  
		/*console.log("==================");
		console.log(s);
		console.log("==================");*/
  	for (var i = 0; i < s.length; i++) {
  		 arr[i]=s[i].trim();
  	};
  	return arr;
  }

  function displayList(list){
  	// for (list.front();list.currPos()<list.length();list.next()) {
  		var lists=[];
  		list.front();
  		while(list.currPos() < list.length){
  			lists.push(list.getElement());
  			list.next();
  		}
         return lists;
  	
  }

	  var movies=createArr();
	  var mlist=new List();
	  for (var i = 0; i < movies.length; i++) {
	   console.log(movies[i]);
	  	mlist.append(movies[i]);
	  };
	  console.log(mlist);
	   //console.log(displayList(mlist));
  </script>
</body>
</html>

javascript数据结构1-数组

发表于 | 更新于 | 分类于

书籍：

数据结构与算法javascript描述

数组比较简单，这里只是简单介绍：

1.使用数组

1.1 创建数组

1
2
3
4
//第一种形式
var numbers = new Array(3);
//第二种形式
var numbers = [7,4,1776];

大多数JavaScript 专家推荐使用[]操作符，和使用Array 的构造函数相比，这种方式被认为效率更高（new创建的对象，会一直存在于内存中）

1.2 读写数组

1
2
3
4
5
var numbers = [1,2,3,5,8,13,21];
var sum = 0;
for (var i = 0; i < numbers.length; ++i) {
sum += numbers[i];
}

1.3 字符串生成数组

1
2
3
4
5
6
//下面的这一小段程序演示了split() 方法的工作原理：
var sentence = "the quick brown fox jumped over the lazy dog";
var words = sentence.split(" ");
for (var i = 0; i < words.length; ++i) {
	console.log("word " + i + ": " + words[i]);
}

1.4 对数组的整体性操作

1
2
3
4
5
6
7
var nums = [];
for (var i = 0; i < 100; ++i) {
nums[i] = i+1;
}
var samenums = nums;
nums[0] = 400;
console.log(samenums[0]); // 显示400

这种行为被称为浅复制，新数组依然指向原来的数组。一个更好的方案是使用深复制，将
原数组中的每一个元素都复制一份到新数组中。可以写一个深复制函数来做这件事：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function copy(arr1, arr2) {
for (var i = 0; i < arr1.length; ++i) {
arr2[i] = arr1[i];
}
}
//这样，下述代码片段的输出就和我们希望的一样了：
var nums = [];
for (var i = 0; i < 100; ++i) {
nums[i] = i+1;
}
var samenums = [];
copy(nums, samenums);
nums[0] = 400;
console.log(samenums[0]); // 显示 1

2. 存取函数

2.1 查找元素

1
2
3
4
5
6
7
8
9
10
var names = ["David", "Cynthia", "Raymond", "Clayton", "Jennifer"];
putstr("Enter a name to search for: ");
var name = readline();
var position = names.indexOf(name);
if (position >= 0) {
	console.log("Found " + name + " at position " + position);
}
else {
	console.log(name + " not found in array.");
}

2.2 两个函数使用

concat 连接
splice 截取
join() 和toString() 将数组转化为字符串

1
2
3
4
5
6
7
8
9
var cisDept = ["Mike", "Clayton", "Terrill", "Danny", "Jennifer"];
var dmpDept = ["Raymond", "Cynthia", "Bryan"];
var itDiv = cis.concat(dmp);
console.log(itDiv);
itDiv = dmp.concat(cisDept);
console.log(itDiv);
//输出为：
Mike,Clayton,Terrill,Danny,Jennifer,Raymond,Cynthia,Bryan
Raymond,Cynthia,Bryan,Mike,Clayton,Terrill,Danny,Jennifer

3. 可变函数

简单函数：

1
2
3
4
push()          末尾增加元素
unshift()       在开头添加元素
pop()           在末尾删除元素
shift()         在开头删除元素

从数组中间删除元素：

1
2
3
4
var nums = [1,2,3,7,8,9];
var newElements = [4,5,6];
nums.splice(3,0,newElements);
console.log(nums); // 1,2,3,4,5,6,7,8,9

排序函数：

1
2
3
var nums = [1,2,3,4,5];
nums.reverse();
console.log(nums); // 5,4,3,2,1
1
2
3
var names = ["David","Mike","Cynthia","Clayton","Bryan","Raymond"];
names.sort();
console.log(names); // Bryan,Clayton,Cynthia,David,Mike,Raymond

自定义：

1
2
3
4
5
6
7
function compare(num1, num2) {
return num1 - num2;
}
var nums = [3,1,2,100,4,200];
nums.sort(compare);
console.log(nums); // 1,2,3,4,100,200
//sort() 函数使用了compare() 函数对数组按照数字大小进行排序，而不是按照字典顺序。

4.迭代器

1
2
3
4
5
6
7
   函数      说明                           是否生成新数组
foreach()    全部遍历                           否    
every()      全部返回true，才返回true            否    
some()       只要一个返回true，就返回true         否    
reduce()     不断调用累加值                      否    
map()        符合条件的，类比foreach()           是    
filter()     返回结果为true的函数                是

5.二维数组和多维数组

1
2
3
4
5
6
7
8
9
10
Array.matrix = function(numrows, numcols, initial) {
var arr = [];
for (var i = 0; i < numrows; ++i) {
	var columns = [];
	for (var j = 0; j < numcols; ++j) {
	columns[j] = initial;
	}
arr[i] = columns;
}
return

6.两种特殊的数组

数组的函数同样适用

对象数组

1
2
3
4
function Point(x,y) {
	this.x = x;
	this.y = y;
}

对象中的数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function weekTemps() {
this.dataStore = [];
this.add = add;
this.average = average;
}
function add(temp) {
this.dataStore.push(temp);
}
function average() {
var total = 0;
for (var i = 0; i < this.dataStore.length; ++i) {
total += this.dataStore[i];
}
return total / this.dataStore.length;
}
	var thisWeek = new weekTemps();
	thisWeek.add(52);
	thisWeek.add(55);
	thisWeek.add(61);
	thisWeek.add(65);
	thisWeek.add(55);
	thisWeek.add(50);
	thisWeek.add(52);
	thisWeek.add(49);
console.log(thisWeek.average()); // 显示54.875

javascript数据结构9-排序

发表于 | 更新于 | 分类于

排序算法

  1. 基本排序
    • 冒泡排序
    • 选择排序
    • 插入排序
  2. 高级排序
    • 希尔排序
    • 归并排序
    • 快速排序
    • 基数排序 （见【Javascript】四、JS数据结构-队列2-基数排序）

注释：完整例子在最后，可以copy运行。
测试数据平台： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
//数组平台
   function CArray(numElements) {
       this.dataStore = [];
       this.pos = 0;
       this.numElements = numElements;
       this.insert = insert;
       this.toString = toString;
       this.clear = clear;
       this.setData = setData;
       this.swap = swap;
       for (var i = 0; i < numElements; ++i) {
           this.dataStore[i] = i;
       }

       //排序算法
       this.bubbleSort = bubbleSort; //冒泡排序
       this.selectionSort = selectionSort; //选择排序
       this.insertionSort = insertionSort; //插入排序
       this.shellSort = shellSort; //希尔排序
       this.gaps = [5, 3, 1];
   }

   function setData() {
       for (var i = 0; i < this.numElements; ++i) {
           this.dataStore[i] = Math.floor(Math.random() * (this.numElements + 1));
       }
   }

   function clear() {
       for (var i = 0; i < this.dataStore.length; ++i) {
           this.dataStore[i] = 0;
       }
   }

   function insert(element) {
       this.dataStore[this.pos++] = element;
   }

   function toString() {
       var retstr = "";
       for (var i = 0; i < this.dataStore.length; ++i) {
           retstr += this.dataStore[i] + " ";
           if (i > 0 & i % 10 == 0) {
               retstr += "<br/>";
           }
       }
       return retstr;
   }

   function swap(arr, index1, index2) {
       var temp = arr[index1];
       arr[index1] = arr[index2];
       arr[index2] = temp;
   }

1-冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//基本排序算法
    //1-冒泡排序  时间复杂度 n2
    function bubbleSort() {
        var numElements = this.dataStore.length;
        var temp;
        for (var i = numElements; i >= 2; --i) {
            for (var j = 0; j <= i - 1; ++j) {
                if (this.dataStore[j] > this.dataStore[j + 1]) {
                    swap(this.dataStore, j, j + 1);
                }
            }
            document.write(this.toString());
            document.write('<br/>');
        }
    }

    function bubbleSortTest(numElements) {
        // var numElements = 10;
        var myNums = new CArray(numElements);
        myNums.setData();
        document.write(myNums.toString());
        document.write('<br/>冒泡排序过程：【最大的先冒出来排在最后一位】<br/>');
        var start = new Date().getTime();
        myNums.bubbleSort();
        var stop = new Date().getTime();
        var time = stop - start;
        document.write("所需要的时间是：" + time);
        //document.write(myNums.toString());
    }

2-选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//2-选择排序
    function selectionSort() {
        var min, temp;
        for (var i = 0; i <= this.dataStore.length - 2; ++i) {
            min = i;
            for (var j = i + 1; j <= this.dataStore.length - 1; ++j) {
                if (this.dataStore[j] < this.dataStore[min]) {
                    min = j;
                }
            }
            swap(this.dataStore, i, min);
            document.write(this.toString());
            document.write('<br/>');
        }
    }

    function selectionSortTest(numElements) {
        //var numElements = 10;
        var myNums = new CArray(numElements);
        myNums.setData();
        document.write(myNums.toString());
        document.write('<br/>选择排序过程：【最小的选择出来放在第一位】<br/>');
        var start = new Date().getTime();
        myNums.selectionSort();
        var stop = new Date().getTime();
        var time = stop - start;
        document.write("所需要的时间是：" + time);
        //document.write(myNums.toString());
    }

3-插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//3-插入排序
   function insertionSort() {
       var temp, j;
       for (var i = 1; i <= this.dataStore.length - 1; ++i) {
           temp = this.dataStore[i];
           j = i; //j=1
           while (j > 0 && (this.dataStore[j - 1] > temp)) {
               this.dataStore[j] = this.dataStore[j - 1];
               --j;
           }
           this.dataStore[j] = temp;
           document.write(this.toString());
           document.write('<br/>');
       }

   }

   function insertionSortTest(numElements) {
       //var numElements = 10;
       var myNums = new CArray(numElements);
       myNums.setData();
       document.write(myNums.toString());
       document.write('<br/>插入排序过程：【从首位开始一个一个插入比较】<br/>');
       var start = new Date().getTime();
       myNums.insertionSort();
       var stop = new Date().getTime();
       var time = stop - start;
       document.write("所需要的时间是：" + time);
   }

4-希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
//高级排序算法
    //4-shell排序
    function shellSort() {
        //gaps的长度，分为三大步
        for (var g = 0; g < this.gaps.length; ++g) { //3层 
            for (var i = this.gaps[g]; i < this.dataStore.length; ++i) {
                var temp = this.dataStore[i];
                for (var j = i; j >= this.gaps[g] && this.dataStore[j - this.gaps[g]] > temp; j -= this.gaps[g]) { //第一次循环:j=5 如果第1个数【序号0】 > 第6个数【temp序号5】
                    this.dataStore[j] = this.dataStore[j - this.gaps[g]]; //第一次循环j=5  那么第6个数【序号5】 = 第1个数【序号0】
                    //小的排在前面
                }
                this.dataStore[j] = temp;

            }
            document.write(this.toString());
            document.write('<br/>');
        }

    }

    function shellSortTest(numElements) {
        var myNums = new CArray(numElements);
        myNums.setData();
        document.write(myNums.toString());
        document.write('<br/>希尔排序过程：<br/>');
        var start = new Date().getTime();
        myNums.shellSort();
        var stop = new Date().getTime();
        var time = stop - start;
        document.write('排序结果是:<br/>');
        document.write(myNums.toString());
        document.write('<br/>');
        document.write("所需要的时间是：" + time);
    }

5-快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//5-快速排序
   function qSort(arr) {
       if (arr.length == 0) {
           return [];
       }
       var left = [];
       var right = [];
       var pivot = arr[0];
       for (var i = 1; i < arr.length; i++) {
           if (arr[i] < pivot) {
               left.push(arr[i]);
           } else {
               right.push(arr[i]);
           }
       }
       return qSort(left).concat(pivot, qSort(right));
   }

   function qSortTest(numElements) {
       var a = [];
       for (var i = 0; i < numElements; i++) {
           a[i] = Math.floor((Math.random() * numElements) + 1);
       }
       document.write(a);
       document.write('<br/>');
       var start= new Date().getTime();
       document.write(qSort(a));
       document.write("<br/>需要时间是：");
       var stop= new Date().getTime();
       var time=stop-start;
       document.write(time);
   }

完整例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
<!DOCTYPE html>
<html>
<meta charset="utf-8">

<head>
    <title>排序算法总结</title>
</head>

<body>
    <input type="button" value="冒泡排序过程查看" onclick="bubbleSortTest(10)">
    <input type="button" value="选择排序过程查看" onclick="selectionSortTest(10)">
    <input type="button" value="插入排序过程查看" onclick="insertionSortTest(10)">
    <input type="button" value="希尔排序过程查看" onclick="shellSortTest(10)">
    <input type="button" value="快速排序过程查看" onclick="qSortTest(10)">
    <br/>
    <p>查看执行函数，建议先删除排序函数中的document.write过程打印,即是:</p>
    <input type="button" value="冒泡排序执行时间" onclick="bubbleSortTest(10000)">
    <input type="button" value="选择排序执行时间" onclick="selectionSortTest(10000)">
    <input type="button" value="插入排序执行时间" onclick="insertionSortTest(10000)">
    <input type="button" value="希尔排序执行时间" onclick="shellSortTest(10000)">
    <input type="button" value="快速排序执行时间" onclick="qSortTest(10000)">
    <script type="text/javascript">
    //===========================================
    //数组平台
    function CArray(numElements) {
        this.dataStore = [];
        this.pos = 0;
        this.numElements = numElements;
        this.insert = insert;
        this.toString = toString;
        this.clear = clear;
        this.setData = setData;
        this.swap = swap;
        for (var i = 0; i < numElements; ++i) {
            this.dataStore[i] = i;
        }

        //排序算法
        this.bubbleSort = bubbleSort; //冒泡排序
        this.selectionSort = selectionSort; //选择排序
        this.insertionSort = insertionSort; //插入排序
        this.shellSort = shellSort; //希尔排序
        this.gaps = [5, 3, 1];
    }

    function setData() {
        for (var i = 0; i < this.numElements; ++i) {
            this.dataStore[i] = Math.floor(Math.random() * (this.numElements + 1));
        }
    }

    function clear() {
        for (var i = 0; i < this.dataStore.length; ++i) {
            this.dataStore[i] = 0;
        }
    }

    function insert(element) {
        this.dataStore[this.pos++] = element;
    }

    function toString() {
        var retstr = "";
        for (var i = 0; i < this.dataStore.length; ++i) {
            retstr += this.dataStore[i] + " ";
            if (i > 0 & i % 10 == 0) {
                retstr += "<br/>";
            }
        }
        return retstr;
    }

    function swap(arr, index1, index2) {
        var temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
    //使用测试平台类

    //=================================================================
    //基本排序算法
    //1-冒泡排序  时间复杂度 n2
    function bubbleSort() {
        var numElements = this.dataStore.length;
        var temp;
        for (var i = numElements; i >= 2; --i) {
            for (var j = 0; j <= i - 1; ++j) {
                if (this.dataStore[j] > this.dataStore[j + 1]) {
                    swap(this.dataStore, j, j + 1);
                }
            }
            document.write(this.toString());
            document.write('<br/>');
        }
    }

    function bubbleSortTest(numElements) {
        // var numElements = 10;
        var myNums = new CArray(numElements);
        myNums.setData();
        document.write(myNums.toString());
        document.write('<br/>冒泡排序过程：【最大的先冒出来排在最后一位】<br/>');
        var start = new Date().getTime();
        myNums.bubbleSort();
        var stop = new Date().getTime();
        var time = stop - start;
        document.write("所需要的时间是：" + time);
        //document.write(myNums.toString());
    }
    //2-选择排序
    function selectionSort() {
        var min, temp;
        for (var i = 0; i <= this.dataStore.length - 2; ++i) {
            min = i;
            for (var j = i + 1; j <= this.dataStore.length - 1; ++j) {
                if (this.dataStore[j] < this.dataStore[min]) {
                    min = j;
                }
            }
            swap(this.dataStore, i, min);
            document.write(this.toString());
            document.write('<br/>');
        }
    }

    function selectionSortTest(numElements) {
        //var numElements = 10;
        var myNums = new CArray(numElements);
        myNums.setData();
        document.write(myNums.toString());
        document.write('<br/>选择排序过程：【最小的选择出来放在第一位】<br/>');
        var start = new Date().getTime();
        myNums.selectionSort();
        var stop = new Date().getTime();
        var time = stop - start;
        document.write("所需要的时间是：" + time);
        //document.write(myNums.toString());
    }

    //3-插入排序
    function insertionSort() {
        var temp, j;
        for (var i = 1; i <= this.dataStore.length - 1; ++i) {
            temp = this.dataStore[i];
            j = i; //j=1
            while (j > 0 && (this.dataStore[j - 1] > temp)) {
                this.dataStore[j] = this.dataStore[j - 1];
                --j;
            }
            this.dataStore[j] = temp;
            document.write(this.toString());
            document.write('<br/>');
        }

    }

    function insertionSortTest(numElements) {
        //var numElements = 10;
        var myNums = new CArray(numElements);
        myNums.setData();
        document.write(myNums.toString());
        document.write('<br/>插入排序过程：【从首位开始一个一个插入比较】<br/>');
        var start = new Date().getTime();
        myNums.insertionSort();
        var stop = new Date().getTime();
        var time = stop - start;
        document.write("所需要的时间是：" + time);
    }
    //高级排序算法
    //4-shell排序
    function shellSort() {
        //gaps的长度，分为三大步
        for (var g = 0; g < this.gaps.length; ++g) { //3层 
            for (var i = this.gaps[g]; i < this.dataStore.length; ++i) {
                var temp = this.dataStore[i];
                for (var j = i; j >= this.gaps[g] && this.dataStore[j - this.gaps[g]] > temp; j -= this.gaps[g]) { //第一次循环:j=5 如果第1个数【序号0】 > 第6个数【temp序号5】
                    this.dataStore[j] = this.dataStore[j - this.gaps[g]]; //第一次循环j=5  那么第6个数【序号5】 = 第1个数【序号0】
                    //小的排在前面
                }
                this.dataStore[j] = temp;

            }
            document.write(this.toString());
            document.write('<br/>');
        }

    }

    function shellSortTest(numElements) {
        var myNums = new CArray(numElements);
        myNums.setData();
        document.write(myNums.toString());
        document.write('<br/>希尔排序过程：<br/>');
        var start = new Date().getTime();
        myNums.shellSort();
        var stop = new Date().getTime();
        var time = stop - start;
        document.write('排序结果是:<br/>');
        document.write(myNums.toString());
        document.write('<br/>');
        document.write("所需要的时间是：" + time);
    }

    //5-快速排序
    function qSort(arr) {
        if (arr.length == 0) {
            return [];
        }
        var left = [];
        var right = [];
        var pivot = arr[0];
        for (var i = 1; i < arr.length; i++) {
            if (arr[i] < pivot) {
                left.push(arr[i]);
            } else {
                right.push(arr[i]);
            }
        }
        return qSort(left).concat(pivot, qSort(right));
    }

    function qSortTest(numElements) {
        var a = [];
        for (var i = 0; i < numElements; i++) {
            a[i] = Math.floor((Math.random() * numElements) + 1);
        }
        document.write(a);
        document.write('<br/>');
        var start= new Date().getTime();
        document.write(qSort(a));
        document.write("<br/>需要时间是：");
        var stop= new Date().getTime();
        var time=stop-start;
        document.write(time);
    }
    </script>
</body>

</html>

javascript数据结构5-链表2 存放点数据（x,y）

发表于 | 更新于 | 分类于 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>Document</title>
</head>
<body>
<script>
  
function Node(element){
  this.element=element;
  this.next=null;
}
  
  function Point(x,y){
   this.x=x;
    this.y=y;
  }

  function LList(){
    this.head=new Node('head');
    //this.head.next=this.head;
    this.find=find;
    this.insert=insert;
    this.display=display;
    this.remove=remove;
    this.findPrevious=findPrevious;
  }
  
  function display(){
    var curr=this.head;
    while(!(curr.next==null)){
       document.write(curr.next.element.x+'/'+curr.next.element.y);
      curr=curr.next;
    }
    return curr;
  }
  
    function find(item){
      var currNode=this.head;
      while(!(currNode.element==item)){currNode=currNode.next;
  }
  return currNode;
}
  
  function insert(newElement, item) {
   var newNode = new Node(newElement);
   var current = this.find(item);
   newNode.next = current.next;
   current.next = newNode;
}
  
  function  findPrevious(item){
    var currNode=this.head;
    while(!(currNode.next==null)&&(currNode.next.element!=item)){
      currNode=currNode.next;
    }
    return currNode;
  }
  
   function remove(item){
     var prevNode=this.findPrevious(item);
     if((prevNode.next!=null)){
       prevNode.next=prevNode.next.next;
     }
   }
   var p1=new Point(1,2);
   var p2=new Point(3,4);
   
   //document.write(p2.x);
  // console.log(p1);
   var points=new LList();
    points.insert(p1,'head');
    points.insert(p2,p1);
    points.display();
</script>
</body>
</html>

一步一步DIY jQuery库3-引入sizzle引擎

发表于 | 更新于 | 分类于

【注】所有代码挂在我的github上

在前两篇的基础上，正式引入sizzle引擎，这里不详细介绍sizzle引擎。

我们在前两篇的jQuery.fn.init的方法是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var init = function(jQuery){
    jQuery.fn.init = function (selector, context) {
        if (!selector) {
            return this;
        } else {
            var elem = document.querySelector(selector);
            if (elem) {
                this[0] = elem;
                this.length = 1;
            }
            return this;
        }
    };
 
    jQuery.fn.init.prototype = jQuery.fn;
};

这里得到的结果是个数组，而不是我们需要的类数组结构的DOM集合HTMLCollection

1.引入Sizzle引擎

下载Sizzle，将sizzle.js文件复制在src/sizzle中，并且改造Sizzle成模块化的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//1-头部注释
//(function( window ) { 

//2-最后尾部注释
/*if ( typeof define === "function" && define.amd ) {
    define(function() { return Sizzle; });
// Sizzle requires that there be a global window in Common-JS like environments
} else if ( typeof module !== "undefined" && module.exports ) {
    module.exports = Sizzle;
} else {
    window.Sizzle = Sizzle;
}
// EXPOSE

})( window );*///修改点2

//3-增加
export default Sizzle;

同时增加一个初始化文件src/sizzle/init.js

1
2
3
4
5
6
7
import Sizzle from './sizzle.js';

var selectorInit  = function(jQuery){
    jQuery.find = Sizzle;  // Sizzle 赋予静态接口 jQuery.find
}

export default selectorInit;

我们可以在jquery源码中找到全部将sizzle赋值的语句，这些我们暂时先不管

1
2
3
4
5
6
7
jQuery.find = Sizzle;
jQuery.expr = Sizzle.selectors;
jQuery.expr[":"] = jQuery.expr.pseudos;
jQuery.unique = Sizzle.uniqueSort;
jQuery.text = Sizzle.getText;
jQuery.isXMLDoc = Sizzle.isXML;
jQuery.contains = Sizzle.contains;

修改jquery.js

1
2
3
4
5
6
7
8
9
10
import jQuery from './core';
import global from './global';
import init from './init';
import sizzleInit from './sizzle/init';  //新增
 
global(jQuery);
init(jQuery);
sizzleInit(jQuery);  //新增
 
export default jQuery;

测试：

1
2
3
<div><span>1</span></div>
<div><span>2</span></div>
<div>3</div>

1
2
var div = $('div');
console.log(div);

最后的结果仍然是个DOM集合数组

2.$.merger方法

1
2
jQuery.fn = jQuery.prototype = {
    length: 0,  // 修改点1，jQuery实例.length 默认为0,这句一定要有，否则length会NAN
1
2
3
4
5
6
7
8
9
10
11
12
13
jQuery.extend({
    merge: function(first, second) {//新增
        var len = +second.length,
            j = 0,
            i = first.length;
        for (; j < len; j++) {
            first[i++] = second[j];
        }
        first.length = i;

        return first;
    }
});

测试

1
2
3
4
5
6
7
8
9
var divs = $.find('div'); //纯数组
var $div1 = $.merge(['hi'], divs); //右边的数组合并到左边的数组，形成一个新数组
var $div2 = $.merge({
    0: 'hi',
    length: 1
}, divs); //右边的数组合并到左边的对象，形成一个新的类数组对象

console.log($div1);
console.log($div2);

我们发现，只需要将$.merger的第一个参数first设置为this（jQuery的示例对象，length已经默认设置为0），第二个参数second设置为搜索到的DOM集合就可以得到DOM集合类数组对象。
修改src/init.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var init = function(jQuery){
    jQuery.fn.init = function (selector, context) {
        if (!selector) {
            return this;
        } else {
            var elemList = jQuery.find(selector);
            if (elemList.length) {
                jQuery.merge( this, elemList );  //this是jQuery实例，默认实例属性 .length 为0
            }
            return this;
        }
    };
 
    jQuery.fn.init.prototype = jQuery.fn;
};
export default init;

3.扩展 $.fn.find

我们虽然能使用$.find方法，但是它并不支持链式，所以我们需要扩展之。

1
2
3
4
5
6
7
8
9
10
11
12
13
jQuery.fn.extend({
    find: function(selector) {
        var i, ret,
            len = this.length,
            self = this;
        ret = [];

        for (i = 0; i < len; i++) {
            jQuery.find(selector, self[i], ret); // //直接利用 Sizzle 接口，把结果注入到 ret 数组中去
        }
        return jQuery.merger(this,ret);
    }
}

4.记录栈-pushStack方法

参考浏览器的历史记录栈，将检索到的jQuery实例放入到栈中，方便存取数据，其中jquery中有一个方法$.end放回上次检索的jQuery对象，使用记录栈能够很方便的实现。

1
2
3
4
5
6
7
8
9
10
11
12
jQuery.fn = jQuery.prototype = {
    /**新增：
     * [pushStack 入栈操作]
     * @param  {[Array]} elems 
     * @return {[*]}  
     */
    pushStack: function(elems) {
        var ret = jQuery.merge(this.constructor(), elems); //this.constructor() 返回了一个 length 为0的jQuery对象
        ret.prevObject = this;
        return ret;
    }
};

重新修改第3部分的代码

1
2
3
4
5
6
7
8
9
10
11
12
jQuery.fn.extend({
    find: function(selector) {
        var i, ret,
            len = this.length,
            self = this;
        ret =[];
        for (i = 0; i < len; i++) {
            jQuery.find(selector, self[i], ret); // //直接利用 Sizzle 接口，把结果注入到 ret 数组中去
        }
        return  this.pushStack(ret);
    },
});

从性能上考虑，改为这样，建设merge里面的遍历

1
2
3
4
5
6
7
8
9
10
11
12
jQuery.fn.extend({
    find: function(selector) {
        var i, ret,
            len = this.length,
            self = this;
        ret = this.pushStack([]);
        for (i = 0; i < len; i++) {
            jQuery.find(selector, self[i], ret); 
        }
        return ret;
    }
});

5.$.fn.end、$.fn.eq 和 $.fn.get

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
jQuery.fn.extend({
    end: function() {
        return this.prevObject || this.constructor();//this.prevObject记录栈中存在
    },
    eq: function(i) {
        var len = this.length;
        var j = +i + (i < 0 ? len : 0);
        return this.pushStack(j >= 0 && j < len ? [this[j]] : []);
    },
    get: function(num) {
        return num != null ?
            // 支持倒序搜索，num可以是负数
            (num < 0 ? this[num + this.length] : this[num]) :
            // 克隆一个新数组，避免指向相同
            [].slice.call(this); 
    },
    first: function() {
        return this.eq(0);
    },
    last: function() {
        return this.eq(-1);
    }
});

6.todolist

我们花了三篇博客写到这里，其实还是有很多没有完全实现，后面的部分也是参照jquery的源码，DIY一个自己的jquery，还有一些没有实现的点

  • $.fn.init第二个参数context上下文还没实现

  • $.fn.find返回结果中可能带着重复的DOM
    例如： 

    1
    2
    3
    4
    5
    <div><div><span>hi</span></div></div>
    <script>
        var  $span = $('div').find('span');
        console.log($span);  //返回两个span
    </script>

下面的部分留作再写几篇博客

参考阅读：

一步一步DIY jQuery库2-使用es6模块化

发表于 | 更新于 | 分类于

本博文使用了rollup打包，这里同时提供了简明的搭建环境的说明，通过第一部分1.环境搭建就可以在本地配置搭建环境。有关rollup的详细安装使用说明可以查看我的另外一篇博客：《rollup + es6最佳实践》

我们首先把《一步一步DIY一个自己jQuery库1》的代码使用es6模块化的方式打包好

【注】所有代码挂在我的github上

1.搭建环境

1.1 目录结构

1
2
3
4
5
6
7
8
9
10
11
- src
  + .babelrc
  + core.js
  + global.js
  + init.js
  + jquery.js
  + util.js
bundle.js
package.json
rollup.config.dev.js
test.html
  • src是源代码文件夹，其中jquery.js是入口文件
  • bundle是编译后的文件
  • package.json是包管理文件
  • rollup.config.dev.js是rollup的配置文件
  • test.html是测试文件,引入<script src="bundle.js"></script>即可测试

1.2 npm安装

1
npm i rollup rollup-plugin-babel babel-preset-es2015-rollup --save-dev

1.3 使用配置编译

新建文件，文件名为rollup.config.dev.js

1
2
3
4
5
6
7
8
9
import babel from 'rollup-plugin-babel';

export default {
  entry: 'src/jquery.js',
  format: 'umd',
  moduleName: 'jQuery',
  plugins: [babel() ],
  dest: 'bundle.js',
};

src中.babelrc

1
2
3
4
5
{
  presets: [
    ["es2015", { "modules": false }]
  ]
}

注意{ "modules": false }一定要有，否则一直报错
执行命令：rollup -c rollup.config.dev.js,就能得到编译后的文件bundle.js。这里使用的是【umd】的形式，这是jquery的发布版本的格式，当然还有其他的一些格式，amd / es6 / cjs / iife

2.打包

jquery.js

1
2
3
4
5
6
7
8
9
// 出口
import jQuery from './core';
import global from './global';
import init from './init';
 
global(jQuery);
init(jQuery);
 
export default jQuery;

core.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
var version = "0.0.1",
    jQuery = function(selector, context) {
        return new jQuery.fn.init(selector, context);
    };

jQuery.fn = jQuery.prototype = {
    jquery: version,
    constructor: jQuery,
    setBackground: function() {
        this[0].style.background = 'yellow';
        return this;
    },
    setColor: function() {
        this[0].style.color = 'blue';
        return this;
    }
};

jQuery.extend = jQuery.fn.extend = function() {
    var isObject = function(obj) {
        return Object.prototype.toString.call(obj) === "[object Object]";
    };
    var isArray = function(obj) {
        return Object.prototype.toString.call(obj) === "[object Array]";
    };
    var name, clone, copy, copyIsArray ,options, i = 1,
        length = arguments.length,
        target = arguments[0] || {},
        deep = false; //默认为浅复制

    if (typeof target === "boolean") {
        deep = target;
        target = arguments[i] || {};
        i++;
    }
    if (typeof target !== "object" && typeof target !== "function") {
        target = {};
    }

    //target后面没有其他参数了(要拷贝的对象)，直接扩展jQuery自身，target并入jQuery
    if (i === length) {
        target = this;
        i--;
    }
    for (; i < length; i++) {
        if ((options = arguments[i]) != null) {
            for (name in options) {
                src = target[name]; //jQuery是否已经有该属性
                copy = options[name];
                if (target === copy) {
                    continue;
                }
                //深拷贝，且确保被拷属性为对象/数组
                if (deep && copy && isObject(copy) || (copyIsArray = isArray(copy))) {
                    //被拷贝属性为数组
                    if (copyIsArray) {
                        copyIsArray = false;
                        //被合并属性
                        clone = src && isArray(src) ? src : [];
                    } else { //被拷贝属性为对象
                        clone = src && isObject(src) ? src : {};
                    }
                    //右侧递归，直到内部属性值是非对象
                    target[name] = jQuery.extend(deep, clone, copy);
                } else if (copy !== undefined) { //非对象/数组，或者浅复制的情况
                    target[name] = copy; //递归结束
                }
            }
        }
    }
    //返回修改后的target
    return target;
};
export default jQuery;

init.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var init = function(jQuery){
    jQuery.fn.init = function (selector, context, root) {
        if (!selector) {
            return this;
        } else {
            var elem = document.querySelector(selector);
            if (elem) {
                this[0] = elem;
                this.length = 1;
            }
            return this;
        }
    };
 
    jQuery.fn.init.prototype = jQuery.fn;
};
export default init;

global.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var global = function(jQuery){
    //走模块化形式的直接绕过
    if(typeof exports === 'object'&&typeof module !== 'undefined') return;
    var _jQuery = window.jQuery,
        _$ = window.$; 
    jQuery.noConflict = function( deep ) {
        //确保window.$没有再次被改写
        if ( window.$ === jQuery ) {
            window.$ = _$;
        }
        //确保window.jQuery没有再次被改写
        if ( deep&&window.jQuery === jQuery ) {
            window.jQuery = _jQuery;
        }
        return jQuery;  //返回 jQuery 接口引用
    };
 
    window.jQuery = window.$ = jQuery;
};
 
export default global;

打包后bundle.js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
(function (global, factory) {
    typeof exports === 'object' && typeof module !== 'undefined' ? module.exports = factory() :
    typeof define === 'function' && define.amd ? define(factory) :
    (global.jQuery = factory());
}(this, (function () { 'use strict';

var _typeof = typeof Symbol === "function" && typeof Symbol.iterator === "symbol" ? function (obj) { return typeof obj; } : function (obj) { return obj && typeof Symbol === "function" && obj.constructor === Symbol ? "symbol" : typeof obj; };

var version = "0.0.1";
var jQuery$1 = function jQuery$1(selector, context) {

    return new jQuery$1.fn.init(selector, context);
};

jQuery$1.fn = jQuery$1.prototype = {
    jquery: version,
    constructor: jQuery$1,
    setBackground: function setBackground() {
        this[0].style.background = 'yellow';
        return this;
    },
    setColor: function setColor() {
        this[0].style.color = 'blue';
        return this;
    }
};

jQuery$1.extend = jQuery$1.fn.extend = function () {
    var isObject = function isObject(obj) {
        return Object.prototype.toString.call(obj) === "[object Object]";
    };
    var isArray = function isArray(obj) {
        return Object.prototype.toString.call(obj) === "[object Array]";
    };
    var name, clone, copy, copyIsArray, options,
        i = 1,
        length = arguments.length,
        target = arguments[0] || {},
        deep = false; //默认为浅复制

    if (typeof target === "boolean") {
        deep = target;
        target = arguments[i] || {};
        i++;
    }
    if ((typeof target === 'undefined' ? 'undefined' : _typeof(target)) !== "object" && typeof target !== "function") {
        target = {};
    }

    //target后面没有其他参数了(要拷贝的对象)，直接扩展jQuery自身，target并入jQuery
    if (i === length) {
        target = this;
        i--;
    }
    for (; i < length; i++) {
        if ((options = arguments[i]) != null) {
            var name, clone, copy;
            for (name in options) {
                src = target[name]; //jQuery是否已经有该属性
                copy = options[name];
                if (target === copy) {
                    continue;
                }
                //深拷贝，且确保被拷属性为对象/数组
                if (deep && copy && isObject(copy) || (copyIsArray = isArray(copy))) {
                    //被拷贝属性为数组
                    if (copyIsArray) {
                        copyIsArray = false;
                        //被合并属性
                        clone = src && isArray(src) ? src : [];
                    } else {
                        //被拷贝属性为对象
                        clone = src && isObject(src) ? src : {};
                    }
                    //右侧递归，直到内部属性值是非对象
                    target[name] = jQuery$1.extend(deep, clone, copy);
                } else if (copy !== undefined) {
                    //非对象/数组，或者浅复制的情况
                    target[name] = copy; //递归结束
                }
            }
        }
    }

    //返回修改后的target

    return target;
};

var _typeof$1 = typeof Symbol === "function" && typeof Symbol.iterator === "symbol" ? function (obj) { return typeof obj; } : function (obj) { return obj && typeof Symbol === "function" && obj.constructor === Symbol ? "symbol" : typeof obj; };

var global = function global(jQuery) {
    //走模块化形式的直接绕过
    if ((typeof exports === 'undefined' ? 'undefined' : _typeof$1(exports)) === 'object' && typeof module !== 'undefined') return;

    var _jQuery = window.jQuery,
        _$ = window.$;

    jQuery.noConflict = function (deep) {
        //确保window.$没有再次被改写
        if (window.$ === jQuery) {
            window.$ = _$;
        }

        //确保window.jQuery没有再次被改写
        if (deep && window.jQuery === jQuery) {
            window.jQuery = _jQuery;
        }

        return jQuery; //返回 jQuery 接口引用
    };

    window.jQuery = window.$ = jQuery;
};

var init = function init(jQuery) {
    jQuery.fn.init = function (selector, context, root) {
        if (!selector) {
            return this;
        } else {
            var elem = document.querySelector(selector);
            if (elem) {
                this[0] = elem;
                this.length = 1;
            }
            return this;
        }
    };

    jQuery.fn.init.prototype = jQuery.fn;
};

// 出口
global(jQuery$1);
init(jQuery$1);

return jQuery$1;

})));

3.增加基础工具模块&完善extend方法

我们在《一步一步DIY一个自己jQuery库1》中说过extend方法的不完善的地方

  • 使用isObject,isArray并不严谨。在某些浏览器中，像 document 在 Object.toSting 调用时也会返回和 Object 相同结果；

新增一个util.js

1
2
3
4
5
6
export var class2type = {}; //在core.js中会被赋予各类型属性值
export const toString = class2type.toString; //等同于 Object.prototype.toString
export const getProto = Object.getPrototypeOf;
export const hasOwn = class2type.hasOwnProperty;
export const fnToString = hasOwn.toString; //等同于 Object.toString/Function.toString
export const ObjectFunctionString = fnToString.call(Object); //顶层Object构造函数字符串"function Object() { [native code] }"，用于判断 plainObj

在core.js中修改/新增代码

  • 导入
1
import { class2type, toString, getProto, hasOwn, fnToString, ObjectFunctionString } from './util.js';
  • 修改
1
2
3
typeof target !== "function"   //修改为!jQuery.isFunction(target)
isArray                        //均修改为jQuery.isArray
isObject                       //均修改为jQuery.isObject
  • 新增
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//新增修改点1，class2type注入各JS类型键值对，配合 jQuery.type 使用，后面会用上
"Boolean Number String Function Array Date RegExp Object Error Symbol".split(" ").forEach(function(name) {
    class2type["[object " + name + "]"] = name.toLowerCase();
});
//新增修改点2
jQuery.extend({
    isArray: Array.isArray || function( obj ) {
        return jQuery.type(obj) === "array";
    },
    isFunction: function( obj ) {
        return jQuery.type(obj) === "function";
    },
    isPainObject: function(obj) {
        var proto, Ctor;

        if (!obj || toString.call(obj) !== "[object Object]") {
            return false;
        }

        proto = getProto(obj);
        // 通过 Object.create( null ) 形式创建的 {} 是没有prototype的
        if (!proto) {
            return true;
        }

        //简单对象的构造函数等于最顶层Object构造
        Ctor = hasOwn.call(proto, "constructor") && proto.constructor;
        return typeof Ctor === "function" && fnToString.call(Ctor) === ObjectFunctionString;
    },

    type: function(obj) {
        if (obj == null) { //不能用 === 
            return obj + ""; //undefined or null
        }

        return typeof obj === "object" || typeof obj === "function" ?
            //兼容安卓2.3- 函数表达式类型不正确情况
            class2type[toString.call(obj)] || "object" :
            typeof obj;
    }
});

修改后的文件我已经挂在了我的github中，对应文件夹是v2.

参考阅读：