发表于   |   分类于   |  

1 系统设计

简介

能够在线展示及编写html、js、css、php代码,拥有实时预览、代码高亮、自动完成、在线发布等多项特性,提供新建项目、文件上传、删除、下载及管理功能。
网址：https://ccgis.cn/jsEditor/modules/logreg/login/login.html

功能设计

系统分为以下三个功能模块，分别是项目管理模块、代码编辑及运行模块、工具栏，如下图所示。

2 关键技术

2.1 目录树的生成

根据用户的登录信息得到属于该用户的项目名称及项目文件所在路径，然后根据geoserver提供的fileserver接口，使用getdir方法得到每一个项目所拥有的文件路径。
若当前用户没有项目，就为其创建一个默认的项目，包含基本的文件结构：index.html文件、css文件夹、js文件夹、imgs文件夹和libs文件夹。
如果项目的数量特别大，需要多次的循环，为了防止长时间运行脚本，造成运行阻塞，用户无法与页面进行交互，需要对其使用数组分块技术，基本的思路是：使用定时器处理数组的一小部分，接着再设置另一个定时器，调用arguments.callee处理小一小块。

1
2
3
4
5
6
7
8
9
10
11
setTimeout(function(){
    var start = +new Date();
    do{
        var item = array.shift();
        process(item);
    }while(array.length > 0 && (+new Date() - start < 50));

    if(array.length > 0){
        setTimeout(arguments.callee,100);
    }
},100);

将文件路径转换为节点的格式，每个节点包含id、pId、name、isParent等信息。

1
var zNode = { id:zNodeId, pId:parentId, name:dirArr[i],isParent :isParent, open:openFlag, owner:dirArr[0] };

最后将得到的节点信息绑定到所在的ztree元素的id上，并为其设定相应的点击事件、双击事件及右键点击事件。

1
$.fn.zTree.init($("#"+id), setting, zNodes);

2.2 编辑窗口与目录树关联

点击目录树到编辑窗口打开文件，使用了自定义事件绑定方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

addCustomEvt: function (evtName,callback){ //用于注册事件处理程序
    if(!this.events[evtName]){
        this.events[evtName] = [callback];
    }else{
        this.events[evtName].push(callback);
    }
},
trigger: function (evtName,argsArr){        //用于触发事件
    var callbackArr = this.events[evtName];
    var args = arguments.length >1 ? arguments[1]:[];
    if(callbackArr instanceof Array){
        for(var i=0,len=callbackArr.length;i<len;i++){
            var fun = callbackArr[i];
            fun.apply(null,args);
        }                
    }
},

这种观察者的设计模式，由观察者及主体构成。观察者能够订阅事件即注册回调事件，在主文件中注册打开文件的事件处理程序，openFile函数执行的就是在编辑窗口请求并打开指定的文件：

1
cataMod.addCustomEvt('open',openFile);

主体触发事件，在目录树的点击事件中，触发打开文件的事件。

catalog.trigger('open',args);

打开指定文件使用的是geoserver服务器提供的fileserver接口，使用getfile方法得到当前路径的文件内容。请求文件时在请求的URL中加上时间戳参数，保证每次请求的文件都是从服务器上获取的最新文件，而不是从浏览器的缓存中读取的。最后在标签栏里添加文件名标签，并用CodeMirror提供的setValue()方法填充代码窗口。

2.3 项目管理

2.3.1 新建项目

为项目添加默认目录结构，创建默认html文件，并包含基础的html结构，保存为字符串，使用encodeURIComponent()方法将字符串进行编码，作为URI的con参数，新建文件使用geoserver服务器fileserver接口的putstring方法。
创建默认的文件夹，使用fileserver接口mkdir方法新建css文件夹、js文件夹、imgs文件夹和libs文件夹。
最后利用WebsqlScript接口为用户在数据库中添加一条记录。

2.3.2 新建文件

新建文件后需要在目录树中增加一个新的节点，使用zTree.addNodes(pNode,zNode)添加节点，zTree.expandNode(zNode)将节点展开，并用zTree.selectNode(thisZNode)将该节点设为选中状态。
在编辑窗口添加一个新的文件标签，并将不同类型文件的默认内容更新到<textarea>
标签中。若新建的文件类型为js或css，则在对应的网页文档的<head>标签中插入<script>标签或<link>标签。

2.3.3 删除文件

使用fileserver接口delete方法删除文件；利用ztree的removeNode()方法移除节点；然后判断当前文件是否在代码编辑窗口中打开，若打开则判断编辑窗口中可见的文件是否为要删除的文件，否的话直接删除文件的标签页和在对象中存储的信息，是的话则先判断当前标签页是否有下一个nodeType为1的同级节点元素并作为下一个要打开的文件，否则判断当前标签页是否有上一个nodeType为1的同级节点元素并作为下一个要打开的文件。

2.3.4 下载文件

首先将要下载的文件或文件夹通过fileserver接口dozip方法另存为一个zip格式的压缩文件；创建一个不可见的<iframe>标签，将<iframe>标签的src指向另存文件的路径；最后将标签加到文档中document.body.appendChild(elemIF)。

2.4 压缩文件上传

为更好地满足用户的需要，我们利用 HTML5 提供的 File API 实现上传文件的功能。Javascript 通过 File API 提供的 File、FileList、Blob 接口便可以读取本地文件。在 html5 中， File 对象支持选择多个文件， 用户选择了某些文件之后，便会触发 file 类型的 input 元素的 onchange 事件句柄。File 对象中包含了文件 的所有可访问信息，而不仅仅是文件名。

File API 还提供了一个异步读取文件的接口——FileReader，利用该接口我们可以异步地将文件内容 加载到内存中，赋予某个 js 变量。FileReader 包含了一套完整的事件模型，用于捕获读取文件时的状态 如 onabort (中断)、onerror (出错)、onloadstart (开始)、onprogress (正在读取)、onload (成功读取)等。 基于 FileReader，我们编写了用于多文件上传的 js 类库 gUpload.js，实现本地文件的读取、变量的处理、文件上传至服务器。

上传文件后在目录树中添加新的节点 ；若在根目录下上传则在数据库中添加一条记录；若上传的文件为压缩文件，geoserver会自动将文件解压到同级目录下，因此还需则将同级目录下的同名文件转换为节点添加到目录树中。

2.5 运行结果实时显示

代码编辑窗口使用了<textarea>标签，在使用CodeMirror.fromTextArea()方法初始化编辑器对象时传入该标签元素，并设置相应的参数。运行结果的显示使用的是<iframe>标签。
在代码编辑窗口编写完代码后，利用CodeMirror提供的getValue方法得到当前文件的内容，并保存到服务器中。再使用getMode方法判断当前文件类型，若非网页文档则找到当前文件对应的html文件的路径。最后将iframe的src属性指向html文件所在路径并加上随机数作为参数，就可以实现运行结果实时显示在页面中的效果。

3 存在的不足

3.1 编辑同一个文件存在冲突

当进行协同开发时，多个用户可能同时编辑同一个文件，这时候就极有可能出现冲突，若某个用户修改了文档中的某一部分并对其进行保存，而这时候另一个用户修改了文档中的另一部分并保存，这时候前一个用户修改的内容就会被后一个用户所覆盖。因此之后要考虑在后台将提交的字符串与后台文件合并的功能。

3.2 没有错误提示

目前查看错误只能通过打开浏览器的控制台的方式，这样不便于开发，接下来可以考虑将错误提示直接显示在系统中，更加方便用户进行开发。

附：

1）工具介绍

  • 新建项目：输入项目名后，自动新建一个默认目录结构的项目。
  • 新建js：选择所在项目，输入文件名，即新建js文件。
  • 新建css：选择所在项目，输入文件名，即新建css文件。
  • 第三方库：点击选择需要引入的库，即自动在当前打开的html文件的head标签中插入第三方库的路径，再次点击可取消引入。
  • 保存：修改文件后，标签的图标会变为红点，点击保存后，文件保存到服务器，图标变为红色关闭按钮。
  • 运行：点击“运行”按钮后，可在右边看到运行后的结果。
  • 发布：点击“发布”按钮后，浏览器再打开一个标签页显示运行结果。
  • 帮助：点击“帮助”按钮后，查询帮助文档。
  • 类库文档：跳转到ccgis类库的说明文档。
  • 注销：在界面右上角显示用户名和注销按钮，点击注销按钮后，页面跳转到登录界面。

2）快捷键说明

  • Ctrl+Q：自动补全
  • Ctrl+F：查找全部匹配的结果
  • Alt+F：逐个跳到匹配的结果，
  • enter：跳到下一个匹配结果，
  • shift+enter：找到上一个匹配的结果
  • Ctrl+H：替换
  • Ctrl+L：选中一行，可以删除
  • Ctrl+/: 注释掉选中的区域
  • Ctrl+D: 同时选中多个匹配结果
  • Shift-Ctrl-[：折叠
  • Shift-Ctrl-]：展开折叠区域

发表于   |   分类于   |  

javascript的setter getter方法一共有五种实现方式

  • 1.通过对象初始化器定义
  • 2.使用 Object.create 方法
  • 3.使用 Object.defineProperty 方法
  • 4.使用 Object.defineProperties 方法
  • 5.使用 Object.prototype.defineGetter 以及 Object.prototype.defineSetter 方法

1.通过对象初始化器定义

1
2
3
4
5
6
7
8
9
var o = {
    a : 8,
    get b(){return this.a +1;},//通过 get,set的 b,c方法间接性修改 a 属性
    set c(x){this.a = x/2}
};
console.log(o.a);//8
console.log(o.b);//9
o.c = 50;
console.log(o.a);//25

我们试着将get set的方法改写成同名,结果如下：

1
2
3
4
5
6
7
8
9
10
var o = {
    a : 8,
    get b(){return this.a +1;},
    set b(x){this.a = x/2}
};
console.log(o.a);//8
console.log(o.b);//9
o.b = 50;
console.log(o.a);//25
console.log(o.b);//26

es6中的新语法：

1
2
3
4
5
6
7
8
9
10
11
var b = "bb";
var c = "cc";
var o = {
    _a : 8,
    get [b](){return this._a +1;},
    set [c](x){this._a = x/2},
};
console.log(o._a);//8
console.log(o[b]);//9
o["cc"] = 50;//等同于o.c = 50;
console.log(o._a);//25

2.使用 Object.create 方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var o = { a: 10 };
o = Object.create(Object.prototype, {
    bar: {
        get: function() {
            return o.a;//或者this.a结果一样
        },
        set: function(val) {
            this.a = val;
        }
    }
});
console.log(o.bar); //undefined
o.bar = 12; 
console.log(o.bar); //12

3.使用 Object.defineProperty 方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var o = { a: 10 } //声明一个对象,包含一个 a 属性,值为1
Object.defineProperty(o, "b", {
    get: function() {
        return this.a;
    },
    set: function(val) {
        this.a = val;
    },
    configurable: true
});

console.log(o.b);//10
o.b = 2;
console.log(o.b);//2

4.使用 Object.defineProperties 方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var obj = { a: 1, b: "sss" };
Object.defineProperties(obj, {
    "A": {
        get: function() {
            return this.a + 1;
        },
        set: function(val) { this.a = val; }
    },
    "B": {
        get: function() {
            return this.b + 2;
        },
        set: function(val) { this.b = val }
    }
});

console.log(obj.A);//2
console.log(obj.B);//sss2
obj.A = 3;
obj.B = "hello";
console.log(obj.A);//4
console.log(obj.B);//hello2

5.使用Object.prototype.__defineGetter__ 以及 Object.prototype.__defineSetter__ 方法

这两种方法是非标准，最好不要在开发中使用

1
2
3
4
5
6
7
8
9
10
var o = { _a: 1 };
o.__defineGetter__("a", function() {
    return this._a;
});
o.__defineSetter__("a", function(val) {
    this._a = val;
})
console.log(o.a);//1
o.a = 2;
console.log(o.a);//2

发表于   |   分类于   |  

昨天看了一本书《你不知道的javascript(上)》关于这方面的内容，体会颇深，其中书中讲到的把javascript当作是面向委托的语言比面向对象的解释更加贴切，下面我就简单结合自己的理解，书写阐述一下，也可以作为一种笔记记录。

1. 提取精华——几个重要的方法

1.1 原型链关联

  • Bar.prototype = Foo.prototype;
  • Bar.prototype = new Foo();
  • Bar.prototype = Object.create(Foo.prototype);
    第一种方式，没有创建Bar.prototype的新对象Bar.prototype直接引用了Foo.prototype，修改Bar.prototype会影响Foo.prototype
    第二种方式，创建了一个关联Bar.prototype的新对象，new其实是调用Foo的“构造函数”，有些东西会影响到Bar()的后代。
    第三种方式，Object.create() 方法创建一个拥有指定原型和若干个指定属性的对象。
    语法：Object.create(proto, [ propertiesObject ])
    参数:proto 一个对象，作为新创建对象的原型。
    propertiesObject 可选。该参数对象是一组属性与值，该对象的属性名称将是新创建的对象的属性名称，值是属性描述符（这些属性描述符的结构与Object.defineProperties()的第二个参数一样）

    MDN

ES5之前Object.create Polyfill代码：

1
2
3
4
5
6
7
if(!Object.create){
	Object.create = function(o){
		function F(){};
		F.prototype = 0;
		return new F();  //new的作用参见上述 第二种方式
	}
}

ES5:Object.setPrototypeOf(Bar.prototype,Foo.prototype)更加标准可靠

1.2 ES6 class

内部也是通过原型链实现的，只是一种语法糖。

2.针尖麦芒——面向对象(OO) VS 面向委托(对象关联 OLOO)

  • OO：类的继承是复制行为，简单说关系是父子关系
    OLOO： 只是对象的关联(基于原型/原型链)，简单说关系是兄弟关系，互相关联。

  • 代码

OO风格： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
   
   function Foo(who){
	this.name = who;
}
Foo.prototype.identity = function(){
	return "I am "+this.name;
};

function Bar(who){
	Foo.call(this,who);
}
Bar.prototype = Object.create(Foo.prototype);

Bar.prototype.speak = function(){
	alert("hello,"+this.identity()+" .");
};

var b1 = new Bar('b1');
var b2 = new Bar('b2');
b1.speak();
b2.speak();

OLOO风格：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
	
Foo = {
    init: function(who) {
        this.name = who;
    },
    identity: function() {
        return "I am " + this.name;
    }
};

Bar = Object.create(Foo);
Bar.speak = function() {
    alert("hello," + this.identity() + " .");
};

var b1 = Object.create(Bar);
b1.init('b1');
var b2 = Object.create(Bar);
b2.init('b2');
b1.speak();
b2.speak();

3.问题探究

内省：我们想看Foo和Bar之间的关系
OO:对比的是Bar.prototype与Foo的关系，并不是Bar和Foo的关系

1
2
3
console.log(Bar.prototype instanceof Foo);  //true
console.log(Object.getPrototypeOf(Bar.prototype) === Foo.prototype);//true
console.log(Foo.prototype.isPrototypeOf(Bar.prototype));//true

OLOO:是Bar和Foo的关系

1
2
console.log(Object.getPrototypeOf(Bar) === Foo);
console.log(Foo.isPrototypeOf(Bar));

发表于   |   分类于   |  

排序算法

  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>

发表于   |   分类于   |  

二叉树 ：

这里写图片描述

闲话少说，直接上代码：

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
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>BST</title>
</head>
<body>
<script>
  //结点
    function Node(data,left,right){
        this.data=data;
        this.left=left;
        this.right=right;
        this.floor=floor;  //层数
        this.show=show;
    }
    function floor(){
      return this.floor;
    }
    function show(){
        return this.data;
    }
  
    function BST(){
        this.root=null;
        this.insert=insert; //插入数据
        this.inOrder=inOrder; //中序排列，详细见后面解释
        this.preOrder=preOrder; //先序排序
        this.postOrder=postOrder; //后续排序
        this.getMax=getMax; //得到最大值
      	this.getMin=getMin; //得到最小值
      	this.find=find; //查找
      	this.remove=remove; //删除节点
    }
    
    function insert(data){
       var n=new Node(data,null,null);
        if(this.root==null){
            this.root=n;
            this.root.floor=1;
        }else{
            var current=this.root;
            var parent;
                var c=1;    
            while(true){
                parent=current;  
                if(data<current.data){
                        current=current.left;
                        c++;  //计算层数的计数器加1
                    if(current==null){
                        parent.left=n;
                        parent.left.floor=c;
                        break;
                    }
                }else{
                    current=current.right;
                        c++;   //加1
                    if(current==null){
                        parent.right=n;
                        //rHeight++;
                        // console.log("**"+rHeight+"**");
                        parent.right.floor=c;
                        break;
                    }
                }
            }
        }
    }
  //中序遍历
  function inOrder(node){
      if(!(node==null)){
          inOrder(node.left);
          document.write(node.show()+" ");
          document.write("层数"+node.floor+"<br/>");
          inOrder(node.right);
      }
       //console.count("inOrder被执行的次数");
  }
  //先序遍历
   function preOrder(node){
      if(!(node==null)){
          document.write(node.show()+" ");
          preOrder(node.left);
          preOrder(node.right);
      }
  }
  
  //后序遍历
   function postOrder(node){
      if(!(node==null)){
          postOrder(node.left);        
          postOrder(node.right);
            document.write(node.show()+" ");
      }
  }
  
  //查找最大值
  function getMax(){
     	var current=this.root;
    	while(!(current.right==null)){
          	current=current.right;
        }
    	return current.data;
  }
  //查找最小值
   function getMin(){
     	var current=this.root;
    	while(!(current.left==null)){
          	current=current.left;
        }
    	return current.data;
  }
  //带参数---查找最小值
  function getSmallest(node){
  		while(!(node.left==null)){
  			node=node.left;
  		}
  	 return node;
  }
  //查找
  function find(data){
    	var current=this.root;
    	while(current!=null){
          	if(current.data==data){
              document.write("<br/>找到【"+data+"】节点<br/>");
              return current;
            }else if(data<current.data){
               current=current.left;
            }else{
               current=current.right;
            }
         
        }
     document.write("<br/>没有找到【"+data+"】 节点<br/>");
//     	return current;
  }
  
  //删除节点-详细解释见后后面
     function remove(data) {
			root = removeNode(this.root, data);
       		//其实root=没有用处，只是保留了函数执行的地址
	}
	function removeNode(node, data) {
          if (node == null) {
				return null;
			}
		if (data == node.data) {
			// 没有子节点的节点
			if (node.left == null && node.right == null) {
					return null;
			}
			// 没有左子节点的节点
			if (node.left == null) {
					return node.right;
			}
			// 没有右子节点的节点
			if (node.right == null) {
					return node.left;
			}
			// 有两个子节点的节点
			var tempNode = getSmallest(node.right);
			node.data = tempNode.data;
			node.right = 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);
              // console.log(node);
				return node;
			}
}
  
  //测试
      var nums=new BST();
      nums.insert(56);
      nums.insert(22);  
      nums.insert(81);
      nums.insert(10);
      nums.insert(30);
      nums.insert(77);
      nums.insert(92);
      nums.insert(100);
      document.write("*****************中序遍历***************</br>");
      inOrder(nums.root);
      document.write("</br>***************先序遍历***************</br>");
      preOrder(nums.root);
      document.write("</br>***************后序遍历***************</br>");
      postOrder(nums.root);
      //nums.show();
      //console.log(nums);  
      document.write("</br>***************最大值/最小值************</br>");
      document.write(nums.getMax()+"/"+nums.getMin());
      document.write("</br>***************查找************</br>");
  	  nums.find(100);
      document.write("</br>***************删除节点81后************</br>");
      nums.remove(81);
      console.log(nums);
      preOrder(nums.root);
</script>
</body>
</html>

结果：
这里写图片描述

遍历

中序遍历：
这里写图片描述
理解双层递归

1
2
3
4
5
6
7
8
9
10
function inOrder(node) {
    if (!(node == null)) {
        inOrder(node.left);                             //@1
        document.document(node.show() + " ");           //@2
        inOrder(node.right);                            //@3
    }
}


inOrder(nums.root);    //开始执行

从根节点开始：
这里写图片描述

这里写图片描述
这里写图片描述

删除节点：

1
2
3
function remove(data) {
		root = removeNode(this.root, data);  
	}

简单接受待删除的数据，具体执行是removeNode函数；

1
2
function removeNode(node, data) {
	}

待删除的节点是：
1.叶子结点，只需要将从父节点只想它的链接指向null；

1
2
3
if (node.left == null && node.right == null) {
		return null;   
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
if (node.left == null && node.right == null) {
				return null;   //递归，找到节点置为空即可
			}
			   //其他情况
			}
			else if (data < node.data) {
				node.left = removeNode(node.left, data);  //#1            
				return node; //#2
			}
			else {
				node.right = removeNode(node.right, data);//#3
				return node; //#4
			}

通过if else逻辑找到node节点

//#1  node.left=null(后面的函数递归后返回的值)
//#3  node.right=null(后面的函数递归后返回的值)

2.只包含一个子节点，原本指向它的节点指向它的子节点。
3.左右子树都有的时候。两种做法：找到左子树的最大值或者右子树的最小值。这里我们用第二种。

  • 查找右子树的最小值，创建一个临时的节点tempNode。
  • 将临时节点的值赋值给待删除节点
  • 删除临时节点

注意：

//#2 //#4必须有，如果没有，则删除节点下面的所有子树都将被删除。
真个过程举个形象的说明，遍历的时候把节点之间的链条解开进行查询，return node；递归查询到最后一级后，由下向上对链条进行缝合。

发表于   |   分类于   |  

图（graph）
图由边的集合及顶点的集合组成
有向图：
有向图
无向图：
这里写图片描述
代码： 

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
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>Graph</title>
</head>
<body>
<script>
	function Graph(v){
      	this.vertices=v;
      	this.edges=0;
      	this.adj=[];
     	for(var i=0;i<this.vertices;++i){
        	this.adj[i]=[];
          // this.adj[i].push("");
      }
      	this.addEdge=addEdge;
      	this.showGraph=showGraph;
      
      //深度优先搜索
      this.dfs=dfs;
      this.marked=[];
      for(var i=0;i<this.vertices;++i){
        	this.marked[i]=false;
      }

      // 广度搜索
      this.bfs=bfs;
      	
    }
  
	//   增加顶点
  	function addEdge(v,w){
      	this.adj[v].push(w);
      	this.adj[w].push(v);
		    this.edges++;      
    }
  	
  	//遍历
  	function showGraph(){
      	for(var i=0;i<this.vertices;++i){
          	document.write('<br/>');
          	document.write(i+"-->");
          	for(var j=0;j<this.vertices;++j){
              	if(this.adj[i][j]!=undefined){
                  	document.write(this.adj[i][j]+' ');
                }
            }
        }
    }
  
  	//深度优先搜索
  	function dfs(v){
  		//var w;
  		this.marked[v]=true;
    	if(this.adj[v]!=undefined){
        	document.write("<br/>访问的节点:"+v);
      }
      // for(var w in this.adj[v]){
      //console.log(this.adj[0].length);    
          var w=this.adj[v].shift();
          while(w!=undefined){
              if(!this.marked[w]){
              	this.dfs(w);
              }
              w=this.adj[v].shift();
          }
     
          //console.log(w);
          //console.log(this.adj[v]);
    }

    // 广度搜索
    function bfs(s){
        var queue=[];
        this.marked[s]=true;
        queue.push(s);//添加到队尾
        var w;  //存放邻接表
        while(queue.length>0){

           var v=queue.shift();//从队首删除
           if(v!=undefined){
              document.write("<br/>访问的节点:"+v);
           }

             w=this.adj[v].shift();
             while(w!=undefined){
                if(!this.marked[w]){
                    this.marked[w]=true;
                    queue.push(w);
                }
                 w=this.adj[v].shift();
             }
        }
    }
  	//测试
  	var  graph=new Graph(5);
  	graph.addEdge(0,1);  
  	graph.addEdge(0,2);  
  	graph.addEdge(1,3);  
  	graph.addEdge(2,4);  
    //console.log(graph);
  	//console.log(graph.adj);
  	graph.showGraph();
    document.write("<br/>");
    document.write("======深度度优先搜索=====");
    graph.dfs(0);
    document.write("<br/>");
    document.write("======广度优先搜索=====");
    var  graph1=new Graph(5);
    graph1.addEdge(0,1);  
    graph1.addEdge(0,2);  
    graph1.addEdge(1,3);  
    graph1.addEdge(2,4);  
    graph1.bfs(0);
</script>
</body>
</html>

运行结果：

0–>1 2
1–>0 3
2–>0 4
3–>1
4–>2
======深度度优先搜索=====
访问的节点:0
访问的节点:1
访问的节点:3
访问的节点:2
访问的节点:4
======广度优先搜索=====
访问的节点:0
访问的节点:1
访问的节点:2
访问的节点:3
访问的节点:4

深度搜索的含义：
深度搜索
广度搜索的含义：
广度搜索

发表于   |   分类于   |  

6.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
74
75
76
77
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>字典sample</title>
</head>
<body>
<script>
	function Dictionary(){
	   this.add = add;
	   this.datastore = new Array();
	   this.find = find;
	   this.remove = remove;
	   this.showAll = showAll;
	   this.count = count;
	   this.clear = clear;
	}

	function add(key, value) {
	   this.datastore[key] = value;
	}

	function find(key) {
	   return this.datastore[key];
	}

	function remove(key) {
	   delete this.datastore[key];
	}

	function showAll() {
	if(this.datastore!=null){
	   var datakeys=Array.prototype.slice.call(Object.keys(this.datastore));
	   for (var key in datakeys) {
	      document.write(datakeys[key] + " -> " + this.datastore[datakeys[key]]+" ");
	      // console.log(Object.keys(this.datastore));
	      console.log(key);
	   }
	 }else{
	 	document.write("字典为空");
	 }
	}

	function count() {
	   var n = 0;
	   for  (var key in Object.keys(this.datastore)) {
	      ++n;
	   }
	   return n;
	}

	function clear() {
	   // for  (var key in Object.keys(this.datastore)) {
	   //    delete this.datastore[key];
	   // } 
	   delete this.datastore;
	}

	//测试
	var dic=new Dictionary();
	dic.add("123","R");
	dic.add("456","Python");
	dic.add("789","JavaScipt");
	document.write("</br>**************字典数目**************</br>");
	var n=dic.count();
	document.write(n);
	document.write("</br>**************全部显示**************</br>");
	dic.showAll();
	document.write("</br>**************删除123--->R*************</br>");
	dic.remove("123");
	dic.showAll();
	document.write("</br>**************清除**************</br>");
	dic.clear();
	dic.showAll();
</script>
</body>
</html>

6.2 散列（HashTable）

它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度
使用：MD5 和 SHA-1 可以说是目前应用最广泛的Hash算法
java中已经实现
这里写图片描述

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
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>HashTable散列表</title>
</head>
<body>
<script>
	function HashTable() {
	   this.table = new Array(137); //为了避免碰撞，首先要确保散列表中用来存储数据的数组其大小是个质数。这一点很关
键，这和计算散列值时使用的取余运算有关。
	   this.simpleHash = simpleHash;   //简单的散列表
	   this.betterHash = betterHash;   //更好的HashTable，避免碰撞
	   this.showDistro = showDistro;
	   this.put = put;
	   //this.get = get;
	}
	function put(data) {
	   var pos = this.simpleHash(data);
	   this.table[pos] = data;
	}
	   
	function simpleHash(data) {
	   var total = 0;
	   for (var i = 0; i < data.length; ++i) {
	      total += data.charCodeAt(i);
	   }
	   document.write("Hash value: " + data + " -> " + total+"<br/>");
	   return total % this.table.length;
	}
	function showDistro() {
	   var n = 0;
	   for (var i = 0; i < this.table.length; ++i) {
	      if (this.table[i] != undefined) {
	         document.write(i + ": " + this.table[i]+"<br/>");
	      }
	   }
	}
	function betterHash(string) {
	   const H = 31;  //较小的质数  书上37不行 
	   var total = 0;
	   for (var i = 0; i < string.length; ++i) {
	      total += H * total + string.charCodeAt(i);
	   }
	   total = total % this.table.length;
	   if (total < 0) {
	      total += this.table.length-1;
	   }
	   return parseInt(total);
	}
	var someNames = ["David", "Jennifer", "Donnie", "Raymond",
                 "Cynthia", "Mike", "Clayton", "Danny", "Jonathan"];
	var hTable = new HashTable();
	
	for (var i = 0; i < someNames.length; ++i) {
  		 hTable.put(someNames[i]);
	}
	hTable.showDistro();
</script>
</body>
</html>

这里写图片描述
这就是碰撞，为避免碰撞，使用betterHash
修改：

1
2
3
4
5
function put(data) {
	   // var pos = this.simpleHash(data);
	   var pos = this.betterHash(data);
	   this.table[pos] = data;
	}

发表于   |   分类于   |  

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>

发表于   |   分类于   |   
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>

发表于   |   分类于   |  

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

排序：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>