数据结构与算法@列表

概述

当不需要再一个很长的序列中查找元素，或者对其进行排序时，列表显得尤为有用。反之，如果数据结构非常复杂，列表的作用就没那么大了。本篇主要讲如何在 JavaScript 中实现一个列表类。思维导图如下，具体细节见参考书籍，实现及常见使用场景见详述部分。

详述

实现列表类

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

// 测试
let names = new List();
names.append("jovy");
names.append("sun");
names.append("tom");
names.append("lucy");
console.log(names);
// List {
//   listSize: 4,
//   pos: 0,
//   dataStore: [ 'jovy', 'sun', 'tom', 'lucy' ] }
names.next();
names.next();
console.log(names.getElement());
// tom
names.prev();
console.log(names.getElement());
// sun

使用迭代器访问列表

console.log("1使用迭代器访问列表+++++++++++++++++");
for (names.front(); names.hasNext(); names.next()) {
  console.log(names.getElement());
}
// jovy
// sun
// tom
// lucy
console.log("2使用迭代器访问列表+++++++++++++++++");
for (names.end(); names.hasPrev(); names.prev()) {
  console.log(names.getElement());
}
// lucy
// tom
// sun
// jovy

一个基于列表的应用

模拟影碟租赁自助查询系统：查询可租借清单，查询用户租赁清单，用户租赁。

// 定义客户类
class Customer {
  constructor(name, movie) {
    this.name = name;
    this.movie = movie;
  }
}
// 显示清单
function displayList(list) {
  for (list.front(); list.hasNext(); list.next()) {
    if (list.getElement() instanceof Customer) {
      console.log(
        list.getElement()["name"] + ", " + list.getElement()["movie"]
      );
    } else {
      console.log(list.getElement());
    }
  }
}

// 检出电影
function checkOut(name, movie, movieList, customerList) {
  if (movieList.contains(movie)) {
    let c = new Customer(name, movie);
    customerList.append(c);
    movieList.remove(movie);
  } else {
    console.log(movie + " is not available.");
  }
}

// 测试+++++++++++++++++++++++++++++++
// 模拟读取数据
let moviesStr =
  "肖申克的救赎，教父，教父2，低俗小说，黄金三镖客，十二怒汉，辛德勒名单，黑暗骑士，指环王：王者归来，搏击俱乐部，星球大战5：帝国反击战，飞越疯人院，指环王：护戒使者，盗梦空间，好家伙，星球大战，七武士，黑客帝国，阿甘正传，上帝之城";
let movies = moviesStr.split("，");

// 使用列表管理电影数据
let movieList = new List();
movies.forEach(element => {
  movieList.append(element);
});
// 使用列表管理客户数据
let customerList = new List();

console.log("Available movies: \n");
displayList(movieList);
checkOut("Jovysun", "教父", movieList, customerList);
console.log("\nCustomer Rentals: \n");
displayList(customerList);
console.log("\nMovies Now Available\n");
displayList(movieList);

练习

更多练习及实现答案请参考下一篇数据结构——列表(练习题及实现)

参考

《数据结构与算法 JavaScript 描述》