跳至主要內容

顺序表

Caryam...大约 7 分钟

顺序表

定义

顺序表是用连续的物理内存进行存储的线性表，用数组实现。

静态顺序表

实现定长数组

静态顺序表中用于存储数据的数组应该是定长的，由于JavaScript中常规的数组长度是可变的，要实现定长数组要用Object.seal密封数组，使其不能添加新元素。例如：

this._els = Object.seal(new Array(5).fill(null)); // 创建并密封含5个null元素的数组

提示

Object.seal可以密封一个对象，使其不能添加新的属性和方法。但并不冻结原来可写的属性和方法，仍然保留其可变性。

注意

  1. 使用fill填充初始值是必须的，否则数组会被密封成空数组，无法更改。
  2. els仍然可以越界赋值，例如els[10] = 1，这并不会报错。
    但是并不产生效果，els[10]仍为undefined。

插入

插入一个元素的核心步骤是先将从元素需要插入的位序开始往后的元素都先向后移动一位，再将该位序元素设置为插入元素。
下面代码后移的操作从顺序表最后一个元素开始一直到插入位置。

// 从尾部逐步后移元素，直到插入位置
for (let i = this._length; i >= pos; i--) {
  this._els[i] = this._els[i - 1];
}

// 插入元素
this._els[pos - 1] = el;

动图演示：

insert

查找

查找操作很简单，遍历数组，依次判断当前值与查找值是否相等，如果相等，就返回位序。
如果遍历完都没有找到符合的值，就返回0。

/**
* 查找元素在顺序表中的位序
* 如果找不到返回0
* @param {any} el 元素
* @returns
*/
locateElem(el) {
 for (let i = 0, len = this._length; i < len; i++) {
   if (this._els[i] === el) {
     return i + 1;
   }
 }

 return 0;
}

补充

还有一种效率更高的查找方式，就是设置哨兵，可以减少i < len这一条判断语句。
这要求创建顺序表时就空出第一个位置不使用，用于设置哨兵。（注意：本篇其他代码都没有用这种方式）

/**
* 查找元素在顺序表中的位序
* 如果找不到返回0
* @param {any} el 元素
* @returns
*/
locateElem(el) {
  // 设置哨兵为查找元素
  this.els[0] = el;
  // 从后往前遍历
  var i = this._length;

  while(this.els[i]!=el) {
    i--;
  }

  return i;
}

置空

定长数组一般不会导致内存泄漏，所以仅实现逻辑上的置空即可，也即将线性表设置为0，不用逐一重置数组元素。

如果要实现同时释放数组元素内存，推荐使用常规数组来存储数据，这也并不影响顺序表的定长属性，因为使用MaxSize进行逻辑限定了。在这种情况下，置空操作就直接将属性指向一个新的数组就好了，也不需要逐一pop元素。

this._els = [];
this._length = 0;

代码

详情
/**
 * 顺序表
 */
class SeqList {
  /**
   * 构造函数，创建顺序表并初始化
   * @param {number} maxSize 顺序表最大长度
   * @param {number} initialValue 初始化值
   */
  constructor(maxSize, initialValue = null) {
    this._MAXSIZE = maxSize; // 最大存储容量
    this._els = Object.seal(new Array(maxSize).fill(initialValue)); // 定长数组存储顺序表
    this._length = 0; // 顺序表的表长
  }

  /**
   * 获取顺序表表长
   */
  get length() {
    return this._length;
  }

  /**
   * 判断位序是否在顺序表的数据存储范围内
   * @param {number} pos 位序
   */
  _isOutRange(pos) {
    return pos < 1 || pos > this._length;
  }

  /**
   * 判断位序是否在顺序表的可用存储范围外
   * @param {number} pos 位序
   */
  _isOutValidRange(pos) {
    return pos < 1 || pos > this._MAXSIZE;
  }

  /**
   * 删除位序为pos的元素，位序从1开始。
   * @param {number} pos 位序
   * @return {any} 删除的元素
   */
  remove(pos) {
    if (this._isOutRange(pos)) {
      throw "位序越界";
    }

    // 获取待删除元素
    const toDelete = this._els[pos - 1];

    // 从删除位置逐一前移顺序表中元素
    for (let i = pos, len = this._length; i < len; i++) {
      this._els[i - 1] = this._els[i];
    }

    this._length--;

    return toDelete;
  }

  /**
   * 根据位序插入元素
   * @param {number} pos 位序
   * @param {any} el 待插入元素
   */
  insert(pos, el) {
    if (this._isOutValidRange(pos)) {
      throw "位序越界";
    } else if (this._length === this._MAXSIZE) {
      throw "顺序表已满，不能再插入元素";
    }

    // 从尾部逐步后移元素，直到插入位置
    for (let i = this._length; i >= pos; i--) {
      this._els[i] = this._els[i - 1];
    }

    // 插入元素
    this._els[pos - 1] = el;

    this._length++;
  }

  /**
   * 根据位序更新元素
   * @param {number} pos 位序
   * @param {any} el
   */
  update(pos, el) {
    if (this._isOutRange(pos)) {
      throw "位序越界";
    }
    this._els[pos - 1] = el;
  }

  /**
   * 查找元素在顺序表中的位序
   * 如果找不到返回0
   * @param {any} el 元素
   * @returns
   */
  locateElem(el) {
    for (let i = 0, len = this._length; i < len; i++) {
      if (this._els[i] === el) {
        return i + 1;
      }
    }

    return 0;
  }

  /**
   * 返回位序对应元素
   * @param {number} pos
   * @returns
   */
  getElem(pos) {
    if (this._isOutRange(pos)) {
      throw "位序越界";
    }

    return this._els[pos - 1];
  }

  /**
   * 顺序表判空
   * @returns
   */
  isEmpty() {
    return this._length === 0;
  }

  /**
   * 清空顺序表
   * 这里不重置数组，仅仅维护逻辑上的置空。如果需要同时释放掉内存，就应该使用动态的顺序表（或者静态顺序表，但使用动态数组）。
   */
  empty() {
    this._length = 0;
  }

  /**
   * 打印顺序表数据
   */
  print() {
    this.traverse((el, pos) => {
      console.log(`位序: ${pos} --- 元素：${el}`);
    });
  }

  /**
   * 遍历顺序表，依次传入数据元素及对应位序给回调函数处理
   * @param {function} cb 回调函数
   */
  traverse(cb) {
    for (let i = 0, len = this._length; i < len; i++) {
      cb(this._els[i], i + 1);
    }
  }

  /**
   * 反向遍历顺序表，依次传入数据元素及对应位序给回调函数处理
   * @param {function} cb 回调函数
   */
  reverseTraversal(cb) {
    for (let i = this._length - 1; i >= 0; i--) {
      cb(this._els[i], i + 1);
    }
  }

  /**
   * 通过ArrayLike的变量直接创建顺序表
   * @param {ArrayLike} arraylike
   * @param {number} maxSize 指定顺序表最大长度，默认是arraylike的长度
   * @returns 顺序表实例
   */
  static from(arraylike, maxSize) {
    maxSize = maxSize || arraylike.length;

    if (maxSize < arraylike.length) {
      throw "给定顺序表最大长度小于给定数据实际长度";
    }

    const seqList = new SeqList(maxSize);

    for (let i = 0, len = arraylike.length; i < len; i++) {
      seqList.insert(i + 1, arraylike[i]);
    }

    return seqList;
  }
}

动态顺序表

动态顺序表的数据存储空间是“无限”的，可以动态开辟存储空间的。而JavaScript中，常规数组天然存在这种特性，所以只要将静态顺序表中MaxSize的限制去掉，并使用常规数组存储数据即可。

代码

详情
/**
 * 顺序表
 */
class SeqList {
  /**
   * 构造函数，创建顺序表并初始化
   */
  constructor() {
    this._MAXSIZE = maxSize; // 最大存储容量
    this._els = []; // 数组存储顺序表
    this._length = 0; // 顺序表的表长
  }

  /**
   * 获取顺序表表长
   */
  get length() {
    return this._length;
  }

  /**
   * 判断位序是否在顺序表的数据存储范围内
   * @param {number} pos 位序
   */
  _isOutRange(pos) {
    return pos < 1 || pos > this._length;
  }

  /**
   * 判断位序是否在顺序表的可用存储范围外
   * @param {number} pos 位序
   */
  _isOutValidRange(pos) {
    return pos < 1;
  }

  /**
   * 删除位序为pos的元素，位序从1开始。
   * @param {number} pos 位序
   * @return {any} 删除的元素
   */
  remove(pos) {
    if (this._isOutRange(pos)) {
      throw "位序越界";
    }

    // 获取待删除元素
    const toDelete = this._els[pos - 1];

    // 从删除位置逐一前移顺序表中元素
    for (let i = pos, len = this._length; i < len; i++) {
      this._els[i - 1] = this._els[i];
    }

    this._length--;

    return toDelete;
  }

  /**
   * 根据位序插入元素
   * @param {number} pos 位序
   * @param {any} el 待插入元素
   */
  insert(pos, el) {
    if (this._isOutValidRange(pos)) {
      throw "位序越界";
    }

    // 从尾部逐步后移元素，直到插入位置
    for (let i = this._length; i >= pos; i--) {
      this._els[i] = this._els[i - 1];
    }

    // 插入元素
    this._els[pos - 1] = el;

    this._length++;
  }

  /**
   * 根据位序更新元素
   * @param {number} pos 位序
   * @param {any} el
   */
  update(pos, el) {
    if (this._isOutRange(pos)) {
      throw "位序越界";
    }
    this._els[pos - 1] = el;
  }

  /**
   * 查找元素在顺序表中的位序
   * 如果找不到返回0
   * @param {any} el 元素
   * @returns
   */
  locateElem(el) {
    for (let i = 0, len = this._length; i < len; i++) {
      if (this._els[i] === el) {
        return i + 1;
      }
    }

    return 0;
  }

  /**
   * 返回位序对应元素
   * @param {number} pos
   * @returns
   */
  getElem(pos) {
    if (this._isOutRange(pos)) {
      throw "位序越界";
    }

    return this._els[pos - 1];
  }

  /**
   * 顺序表判空
   * @returns
   */
  isEmpty() {
    return this._length === 0;
  }

  /**
   * 清空顺序表
   */
  empty() {
    this._els = [];
    this._length = 0;
  }

  /**
   * 打印顺序表数据
   */
  print() {
    this.traverse((el, pos) => {
      console.log(`位序: ${pos} --- 元素：${el}`);
    });
  }

  /**
   * 遍历顺序表，依次传入数据元素及对应位序给回调函数处理
   * @param {function} cb 回调函数
   */
  traverse(cb) {
    for (let i = 0, len = this._length; i < len; i++) {
      cb(this._els[i], i + 1);
    }
  }

  /**
   * 反向遍历顺序表，依次传入数据元素及对应位序给回调函数处理
   * @param {function} cb 回调函数
   */
  reverseTraversal(cb) {
    for (let i = this._length - 1; i >= 0; i--) {
      cb(this._els[i], i + 1);
    }
  }

  /**
   * 通过ArrayLike的变量直接创建顺序表
   * @param {ArrayLike} arraylike
   * @returns 顺序表实例
   */
  static from(arraylike) {
    const seqList = new SeqList();

    for (let i = 0, len = arraylike.length; i < len; i++) {
      seqList.insert(arraylike[i]);
    }

    return seqList;
  }
}
上次编辑于:
贡献者: cary-mao
0  /  200  字
评论
  • 按正序
  • 按倒序
  • 按热度
Powered by Waline v2.15.7
Copyright © 2024 Caryam