Javascript数据结构与算法之列表详解

前言：在日常生活中，人们经常要使用列表，比如我们有时候要去购物时，为了购物时东西要买全，我们可以在去之前，列下要买的东西，这就要用的列表了，或者我们小时候上学那段时间，每次考完试后，学校都会列出这次考试成绩前十名的同学的排名及成绩单，等等这些都是列表的列子。我们计算机内也在使用列表，那么列表适合使用在什么地方呢？不适合使用在什么地方呢？
适合使用在：当列表的元素不是很多的情况下，可以使用列表，因为对列表中的元素查找或者排序时，效率还算非常高，反之：如果列表元素非常多的情况下，就不适合使用列表了。
一：列表的抽象数据类型定义
为了设计列表的抽象数据类型，我们需要给出列表的定义，包括列表应该拥有哪些属性，应该在列表上执行哪些操作等。
列表是一组有序的数据。每个列表中的数据项称为元素。在javascript中，列表中的元素可以是任意数据类型。列表中可以保存多少元素并没有事先约定。但是实际使用时元素数量受到程序内存的限制。
现在我们想设计一个列表，那么我们可以想想实现一个列表，他们应该包含哪些属性和方法，当然我下面的设计都是根据 "javascript数据结构与算法" 书上的demo来设计的，为止我们可以学习下，如果以后我们编写程序时，该如何来设计我们自己的抽象类来作为一个参考，我们现在学习书上的demo最主要的是学习他们中的设计思想及编写代码的方式。他们有如下属性；
 1. listSize（属性）：使用一个listSize变量来保存列表中元素的个数。  2. pos(属性)：  列表的当前位置，元素的索引。  3. dataStore(属性)： 初始化一个空数组来保存元素的个数。如果我们想取得具体的列表中的元素 可以使用上面的pos属性；如 dataStore[pos];
所有的方法；如下列表解释，不一一介绍了。

二：如何实现列表类
根据上面定义的列表抽象数据类型，我们可以实现如下一个List类，如下通过构造函数+原型模式。

代码如下:


function List() {
    // 列表的元素个数
    this.listSize = 0;

    // 列表的当前位置 是第几个     this.pos = 0;
    // 初始化一个空数组来保存列表元素     this.dataStore = [];
}
List.prototype = {         // 给列表末尾添加元素     append: function(element) {         var self = this;         self.dataStore[this.listSize++] = element;     },
    // 从列表中删除元素     remove: function(element) {         var self = this;         var curIndex = self.find(element);         if(curIndex > -1) {             self.dataStore.splice(curIndex,1);             --self.listSize;             return true;         }         return false;     },
    // 查找列表中的元素 返回索引     find: function(element) {         var self = this;         for(var i = 0,dataLen = self.dataStore.length; i < dataLen; i++) {             if(self.dataStore[i] == element) {                 return i;             }         }         return -1;     },         // 返回列表中元素的个数     length: function() {         return this.listSize;     },
    // 显示列表中的元素     toString: function(){         return this.dataStore;     },
    /*      * 在指定元素后面插入一个元素      * @param element 当前的元素      * @param elementAfter 把当前的元素插入到此元素后面      */     insert: function(element,elementAfter){         var self = this;         var insertPos = self.find(elementAfter);         if(insertPos > -1) {             self.dataStore.splice(insertPos+1,0,element);             ++self.listSize;             return true;         }         return false;     },         // 清空列表中的所有元素     clear: function() {         delete this.dataStore;         this.dataStore = [];         this.listSize = this.pos = 0;     },     // 判断给定的元素是否在列表中     contains: function(element) {         var self = this;         for(var i = 0,ilen = self.dataStore.length; i < ilen; i++) {             if(self.dataStore[i] == element) {                 return true;             }         }         return false;     },     // 将列表中的当前元素移动到第一个位置     front: function(){         this.pos = 0;     },     // 将列表中当前的元素移动到最后一个位置     end: function(){         this.pos = this.listSize - 1;     },     // 将当前位置 后移一位     prev: function(){         if(this.pos > 0) {             --this.pos;         }     },     // 将当前位置 前移一位     next: function(){         if(this.pos < this.listSize - 1) {             ++this.pos;         }     },     // 返回列表的当前位置     curPos: function(){         return this.pos;     },     // 将当前位置移动到指定位置     moveTo: function(n) {         this.pos = n;     },     // 返回当前位置的元素     getElement:function(){         return this.dataStore[this.pos];     } };


如上：实现一个列表类，包含上面的如上那么多方法，当然我们也可以扩展一些其他的方法，来丰富实现列表类，最主要可以学习如上编码方式。


有用  |  无用 取消

猜你喜欢