线性表

• 线性表
  • 顺序存储：顺序表
  • 链式存储
    • 单链表
    • 双链表
    • 循环链表
    • 静态链表

链式存储中，单链表、双链表、循环链表是基于指针实现，静态链表是借助数组实现

线性表的定义

线性表是具有相同数据类型的n（n>=0）个数据元素的有限序列，其中n为表长，当n=0时线性表是空表。若用L命名线性表，则其一般表示为 L = (a1,a2,...,a_i,a_i+1,a_n)

线性表的逻辑特性

其中，a1是唯一“第一个”数据元素，又称表头元素；a_n是唯一的“最后一个”数据元素，又称表尾元素。 除第一个元素，每个元素有且仅有一个直接前驱。除最后一个元素，每个元素有且仅有一个直接后继。

线性表特点

• 元素个数有限
• 具有逻辑上的顺序性，表中元素有其先后次序
• 元素都是数据元素且为单个元素
• 元素数据类型相同，每个元素占有相同大小的存储空间

注：线性表是一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指存储结构，两者是不同层面的概念。

线性表的顺序表示

随机存储、插入和删除需要移动大量元素。

随机存取：直接存取，可以直接通过下标访问数据元素，访问时间与存储位置无关，例如数组。 顺序存取：访问第N个元素，必须先访问前N-1个元素，与存储位置有关，比如链表。

顺序表

线性表的顺序存储又称顺序表。是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。 i是元素a_i在线性表中的位序。

注意：线性表中的元素的位序从1开始，而数组中元素的下标是从零开始。

特点：

• 逻辑顺序与其物理顺序相同
• 随机访问：通过首地址和元素序号可以在时间O(1)内找到指定元素
• 存储密度高，每个结点只存储数据元素 缺点：
• 逻辑上相邻的元素在物理上也相邻，所以插入和删除操作需要移动大量元素

定义顺序表

c++实现

#define MaxSize 50 // 顺序表最大长度
typedef struct {
    ElemType data[MaxSize]; // ElemType 类型数组表示顺序表
    int length; // 顺序表当前长度
} SqList; // 顺序表类型定义

js实现

const MaxSize = 50;
function SqList() {
    this.data = [];
    this.length = 0;
}

顺序表的基本操作

插入操作

c++实现

bool ListInsert (SqList &L, int i, ElemType e) {
    // 判断 i 的范围是否有效
    if (i < 1 || i > L.length + 1)
        return false;
    // 判断存储空间
    if (L.length >= MaxSize) 
        return false;
    // 将第 i 个元素及之后的元素后移
    // 这里要注意区别位序和数组下标，由于是用数组实现线性表 所以第 i 个元素对应的是数组中的 i-1 项
    for (int j = L.length; j >= i; j--)
        L.data[j] = L.data[j-1];
    // 数组第 i-1 项插入 e 表示线性表中位序i初插入元素
    L.data[i-1] = e;
    // 线性表长度 +1
    L.length++;
    return true;
}

js实现

SqList.prototype.ListInsert = function(i, e) {
    if (i < 1 || i > this.length + 1) return false
    if (this.length > MaxSize) return false
    for(let j = this.data.length; j >= i; j--)
        this.data[j] = this.data[j-1]
    this.data[i-1] = e
    this.length++
    return true
}

删除操作

c++实现

bool ListDelete(SqlList &L, int i, ElemType e) {
    if (i < 1 || i > L.length + 1)
        return false;
    if (i > MaxSize)
        return false;
    for (int j = i; j < L.lenght - 1; j++)
        L.data[j-1] = L.data[j];
    L.length--;
}

js实现

SqList.prototype.ListDelete = function(i, e) {
    if (i < 1 || i > this.length + 1) return false
    e = this.data[i-1]
    for(let j = i; j < this.length; j++)
        this.data[j-1] = this.data[j]
    this.data.length--
    this.length--
    return e
}

按值查找(顺序查找)

c++实现

int LocateElem(SqList L, ElemType e) {
    int i;
    for(i = 0; i < L.length; i++)
        if(L.data[i] == e)
            return i + 1;
    return 0;
}

js实现

SqList.prototype.LocateElem(e) {
    for(let i = 0; i < this.length; i++)
        if(this.data[i] === e) return i + 1
    return 0
}

线性表的链式表示

不需要使用地址连续的存储单元，插入和删除不需要移动元素，只需要移动指针，但是会失去随机存取的优点。

单链表的定义

线性表的链式存储又称单链表，通过一组任意的存储单元来存储线性表中的数据元素。每个结点包括数据域，存放数据元素；next为指针域，存放其后继结点的地址。