数据结构
日常生活中使用列表如：待办事项、购物清单、榜单排名等。计算机程序也在使用列表，尤其是列表中保存的元素不是太多时。当不需要在一个很长的序列中查找元素，或对其进行排序时，列表显得尤为有用。反之，如果数据结构非常复杂，列表的作用就没有那么大了。
列表是一种最自然的数据组织方式，如果数据存储的顺序不重要，也不必对数据进行查找，那么列表就是一种再好不过的数据结构。
抽象数据类型定义
- 列表是一组有序的数据，每个列表中的数据项称为元素。
- 不包含任意元素的列表称为空列表
- 列表中包含元素的个数称为列表的length
- 列表拥有描述元素位置的属性，列表有前有后。
- 列表的抽象数据类型并未指明列表的存储结构
列表
线性表
列表的抽象数据类型定义
-
position列表的当前位置 -
length/size列表元素的个数 -
clear()清空列表中所有元素 -
toString()获取列表的字符串形式 -
element()获取当前位置的元素 -
insert()向现有元素后插入新元素 -
append()在列表末尾追加新元素 -
remove()从列表中移除元素 -
front()将列表当前位置移动到第一个元素 -
end()将列表当前位置移动到最后一个元素 -
prev()将列表当前位置后移一位 -
next()将列表当前位置前移一位 -
position()获取列表的当前位置 -
move()将当前位置移动到指定位置
/*列表*/
function List()
{
this.data = [];
this.length = 0;
this.position = 0;
//判断给定值是否在列表中
var contains = function(element){
for(var i=0; i<this.length; ++i){
if(this.data[i] === element){
return true;
}
}
return false;
};
//从列表中查找元素，成功返回索引，失败返回-1.
var find = function(element){
for(var i=0; i<this.length; ++i){
if(this.data[i] === element){
return i;
}
}
return -1;
};
//为列表末尾追加元素
var append = function(element){
this.data[this.length++] = element;
};
//向列表元素之后插入
var insert = function(element,after){
var index = this.find(after);
if(index > -1){
this.data.splice(index,1,element);
++this.length;
return true;
}
return false;
};
//从列表中删除元素
var remove = function(element){
var index = this.find(element);
if(index > -1){
this.data.splice(index,1);
--this.length;
return true;
}
return false;
};
//获取列表长度，即列表中元素的个数。
var size = function(){
return this.length;
};
//显示列表中的元素
var toString = function(){
return this.data;
};
//清空列表中所有元素
var clear = function(){
this.length = 0;
this.position = 0;
delete this.data;//删除数组
this.data = [];
};
//当前项目
var curele = function(){
return this.data[this.position];
};
var curpos = function(){
return this.position;
};
//在列表自由移动
var front = function(){
this.position = 0;
};
var end = function(){
this.position = this.length-1;
};
var prev = function(){
if(this.position > 0){
--this.position;
}
};
var next = function(){
if(this.position < this.length-1){
++this.position;
}
};
var moveto = function(position){
this.position = position;
};
this.append = append;
this.size = size;
this.toString = toString;
this.find = find;
this.remove = remove;
this.clear = clear;
this.contains = contains;
//当前项目
this.curele = curele;
this.curpos = curpos;
//迭代器行为
this.front = front;
this.end = end;
this.prev = prev;
this.next = next;
this.moveto = moveto;
}
