Javascript数据结构与算法之列表详解

Javascript数据结构与算法之列表详解

简介

本文旨在讲解Javascript中数据结构和算法的列表。

列表定义和实现

列表是一组有序的数据，每个列表中的数据项称为元素。在Javascript中，列表可以用数组来实现。数组的好处是它能够存储任意类型的数据，而且可以根据需要动态地调整数组的大小。下面是一个创建列表的基本模板：

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;//返回存储在当前位置的元素
}

这个模板包含以下函数：

• append()：向列表末尾添加新元素。
• find()：在列表中查找给定元素。
• remove()：从列表中删除元素。
• length()：列表中的元素个数。
• toString()：显示列表中的元素。
• insert()：在一个元素后面插入一个新元素。
• clear()：清空列表中所有元素。
• contains()：判断给定的值是否在列表中。
• front()：将列表的当前位置移动到第一个元素。
• end()：将列表的当前位置移动到最后一个元素。
• prev()：将当前位置向前移动一位。
• next()：将当前位置向后移动一位。
• currPos()：返回列表的当前位置。
• moveTo()：将当前位置移动到指定位置。
• getElement()：返回列表的当前元素。

列表示例

下面是一个使用列表来存储数字的示例。在这个示例中，我们从文件中读取一组数字，将这些数字存储在列表中，然后按照从小到大的顺序显示这些数字。

var fs = require('fs');
var readline = require('readline');
var List = require('./List.js');

var rl = readline.createInterface({
  input: fs.createReadStream('numbers.txt'),
  output: process.stdout
});

var numbers = new List();

rl.on('line', function(line) {
  numbers.append(parseInt(line));
});

rl.on('close', function() {
  console.log('before sort:');
  console.log(numbers.toString());

  var len = numbers.length();
  for(var i=0; i<len-1; i++) {
    for(var j=i+1; j<len; j++) {
        if(numbers.dataStore[i] > numbers.dataStore[j]) {
          var tmp = numbers.dataStore[i];
          numbers.dataStore[i] = numbers.dataStore[j];
          numbers.dataStore[j] = tmp;
        }
    }
  }

  console.log('after sort:');
  console.log(numbers.toString());
});

上述示例中，我们使用了一个 readline 对象从文件中读取数字，并将数字存储在列表中。然后，我们使用一个简单的冒泡排序算法对这些数字进行排序，并显示排序后的结果。

下面是使用列表实现一个简单的 TODO 应用的示例：

var readline = require('readline');
var List = require('./List.js');

var todoList = new List();
var rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

var currentCommand = '';

rl.setPrompt('请输入命令(add, remove, show, exit)：', 30);
rl.prompt();

rl.on('line', function(line) {
  currentCommand = line;
  if(line === 'exit') {
    rl.close();
  }
  rl.setPrompt('请输入要添加的任务：', 20);
  rl.prompt();
});

rl.on('line', function(line) {
  if(currentCommand === 'add') {
    todoList.append(line.trim());
  } else if(currentCommand === 'remove') {
    todoList.remove(line.trim());
  } else if(currentCommand === 'show') {
    console.log(todoList.toString());
  }
  rl.setPrompt('请输入命令(add, remove, show, exit)：', 30);
  rl.prompt();
});

上述示例中，我们使用了一个 readline 对象从命令行中读取用户输入，并根据不同的命令进行相应的操作。每个任务都被存储在一个列表中，用户可以添加新任务，删除已有任务，并显示所有任务。