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];
    }
};

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

javascript数据结构列表算法详解

回复

我来回复
  • 暂无回复内容