线性表

线性表是零个或多个数据元素的有限序列。

存储结构

线性表也可以有两种存储结构：

• 顺序存储结构：用一段地址连续的存储单元一次存储线性表的数据元素。（一维数组）

  顺序存储结构称为顺序表。

• 链式存储结构：除了存储元素外，还要存储指向前后位置的信息(指针)，每一个元素+指针的组合叫结点。

  链式存储结构称为链表，链表又可以分为单链表、静态链表、循环链表、双向链表。

存储结构	操作	时间复杂度	应用场景
顺序存储结构	查找	O(1)	元素个数变化不大，更多是存取数据的应用
	插入与删除	O(n)
链式存储结构	查找	O(n)	需要频繁的插入和删除，比较少存取的应用（知道地址的前提下）
	插入与删除	O(1)

列表类的实现

抽象数据类型定义

• ADT 表（List）
  • Data
    • 数据对象集合为{a1, a2, a3, ..., an},每个元素类型均为DataType。其中，除第一个元素 a1 外，每一个元素有且只有一个直接前驱元素，除了最后一个元素 an 外，每一个元素由且只有一个直接后继元素。数据元素之间的关系是一对一的关系。（Js中可以使用数组存储）
  • Operation
    • pos（属性）：列表的当前位置
    • length（属性）： 返回列表中元素的个数
    • clear（方法）： 清空列表中的所有元素
    • toString（方法）： 返回列表的字符串形式
    • getElement（方法）： 返回当前位置的元素
    • insert（方法）： 在现有元素后插入新元素
    • append（方法）： 在列表的末尾添加新元素
    • remove（方法）： 从列表中删除元素
    • front（方法）： 将列表的当前位置设移动到第一个元素
    • end（方法）： 将列表的当前位置移动到最后一个元素
    • prev（方法）： 将当前位置后移一位
    • next（方法）： 将当前位置前移一位
    • currPos（方法）： 返回列表的当前位置
    • moveTo（方法）： 将当前位置移动到指定位置
• endADT

function List() { 
    this.listSize = 0; 
    this.pos = 0; 
    this.dataStore = []; // 初始化一个空数组来保存列表元素 
    this.clear = clear; 
    this.find = find; 
    this.toString = toString; 
    this.insert = insert; 
    this.append = append; 
    this.remove = remove; 
    this.front = front;
    this.end = end; 
    this.prev = prev; 
    this.next = next; 
    this.length = length; 
    this.currPos = currPos; 
    this.moveTo = moveTo; 
    this.getElement = getElement; 
    this.length = length; 
    this.contains = contains;
}
function append(element) { 
    this.dataStore[this.listSize++] = element;
}
function find(element) { 
    for (var i = 0; i < this.dataStore.length; ++i) { 
        if (this.dataStore[i] == element) { 
            return i; 
        } 
    }
    return -1; 
}
function remove(element) { 
    var foundAt = this.find(element); 
    if (foundAt > -1) { 
        this.dataStore.splice(foundAt,1);
        --this.listSize; 
        return true; 
    }
    return false; 
}
function length() { 
    return this.listSize; 
}
function toString() { 
    return this.dataStore; 
}
function insert(element, after) { 
    var insertPos = this.find(after); 
    if (insertPos > -1) { 
        this.dataStore.splice(insertPos+1, 0, element); 
        ++this.listSize; 
        return true; 
    }
    return false; 
}
function clear() { 
    delete this.dataStore; 
    this.dataStore = []; 
    this.listSize = this.pos = 0; 
}
function contains(element) {
    for (var i = 0; i < this.dataStore.length; ++i) { 
        if (this.dataStore[i] == element) { 
            return true; 
        } 
    }
    return false; 
}
function front() { 
    this.pos = 0; 
}
function end() {
    this.pos = this.listSize-1; 
}
function prev() { 
    if (this.pos > 0) { 
        --this.pos;
    } 
}
function next() { 
    if (this.pos < this.listSize-1) { 
        ++this.pos; 
    } 
}
function currPos() { 
    return this.pos; 
}
function moveTo(position) { 
    this.pos = position; 
}
function getElement() { 
    return this.dataStore[this.pos]; 
}

线性表的应用

• 列表类查找系统