怎样利用JS自定义哈希表和顺序列表

程序员文章站 2022-03-20 09:59:49
...
/**哈希表*/
var HashMap = function(){
	this.table={};
 	this.count=0;//长度

 	/**添加对象
	* @param key 键
	* @param obj 对象
	*/
	this.put=function(key,obj){
	    var v=this.table[key];
	    if(typeof(v)=="undefined")this.count+=1;
	    this.table[key]=obj;
	};
	/**获得对象
	* @param key 键
	* @return obj 对象
	*/
	this.get=function(key){
	    return this.table[key];
	};
	
	this.contains=function(key){
		return (key in this.table);
	};
	/**删除对象
	* @param key 键
	* @return obj 对象
	*/
	this.remove=function(key){
	    var obj=this.table[key];
	    if(obj != undefined){
		    delete this.table[key];
		    this.count -= 1;
	    }
	    return obj;
	};
	/**清空所有对象*/
	this.clear=function(){
	    this.table={};
 	    this.count=0;
	};
	/**当前大小*/
	this.size=function(){
		return this.count;
	};
	/**是否为空*/
	this.isEmpty=function(){
		return this.count <= 0;
	};
	/**获得所有值*/
	this.values=function(){
		var values = new Array();
		for(var prop in this.table){
		 	values.push(this.table[prop]);
		}
		return values;
	};
	/**获得所有键*/
	this.keys=function(){
		var keys = new Array();
		for(var prop in this.table){
		 	keys.push(prop);
		}
		return keys;
	};
};

/**顺序链表*/
var ArrayList = function(){
	this.count=0;//长度
 	this.initialCapacity = 10;
	this.list=new Array(this.initialCapacity);

	/**添加对象
	* @param obj 对象
	*/
	this.add=function(obj){
        this.list[this.count]=obj;
        this.count+=1;
	};
	/**按索引设置对象
	* @param obj 对象
	*/
	this.set=function(index,obj){
		if(this.list.length<index){
			this.list[index]=obj;
			return true;
		}else return false;
	};
	/**获得对象
	* @param index 索引位
	* @return obj 对象
	*/
	this.get=function(index){
	    return this.list[index];
	};
	/**删除对象
	* @param index 索引位
	* @return obj 对象
	*/
	this.remove=function(index){
	    var obj=null;
	    if(index>=0&&index<this.count){
	  	    obj = this.list[index];
            for (var i = index; i < this.count - 1; i++) {
                this.list[i] = this.list[i + 1];
            }
            this.list[this.count-1] = null;
            this.count-=1; 
	    }
	    return obj;
	};
	/**删除一组对象
	* @param index  索引位
	* @param length 长度
	*/
	this.removeGroup=function(index,length){
	    if(index>=0){
		    var start=index;var end=index+length;
	  	    var counts=0;var lists=[];
            for (var i = 0; i < this.count; i++) {
        	    if(i>=start&&i<end)continue;
        	    lists[lists.length] = this.list[i];
        	    counts++;
            }
            this.list=lists;
            this.count=counts; 
	    }
	};
	/**清空所有对象*/
	this.clear=function(){
	    this.count=0;   
	    this.list=[];
	};
	/**获得链表大小
	* @return 返回大小
	*/
	this.size=function(){
	    return this.count;
	};
	this.getList=function(){
		return this.list;
	};
	this.setList=function(list){
		this.list=list;
		this.count=list.length;
	};
	/**折半查找
	* @param value 对比的数据
	* @return fun  对比方法
	* @return 返回位置，-1为没找到
	*/
	this.bisearch=function(value,fun){
	   var pos=-1;
       var start = 0;
       var end = this.count-1;
       var current = parseInt(this.count/2);
       for(var i=0;i<current;i++){
       	 if(!fun(value,this.list[start])){
       		start =start+1;
       	 }else{
       	 	pos=start;break;
       	 }
       	 if(!fun(value,this.list[current])){
       		current =current+1;if(current>end)break;
       	 }else{
       	 	pos=current;break;
       	 }
       }
       return pos;
	};
	/**顺序查找
	* @param value 对比的数据
	* @return fun  对比方法
	* @return 返回位置，-1为没找到
	*/
	this.search=function(value,fun){
	   var pos=-1;
       for(var i=0;i<this.count;i++){
       	 if(fun(value,this.list[i])){
       	 	pos=i;break;
       	 }
       }
       return pos;
	};
};
相信看了本文案例你已经掌握了方法，更多精彩请关注其它相关文章！