JavaScript中数据结构与算法描述

/ 默认分类 / 没有评论 / 96浏览

数据结构与算法描述

算法和数据结构是程序的灵魂,此生不入算法枉为代码人!

数组

数组的标准定义是:一个存储元素的线性集合(collection),JavaScript 中的数组是一种特殊的对象,用来表示偏移量的索引是该对象的属性,索引可能是整数。但是数字索引在内部被转换为字符串类型,因为 JavaScript 对象中的属性名必须是字符串。数组在 JavaScript 中只是一种特殊的对象,严格来说应该称作对象。

二维数组

默认情况下js仅支持一维,但是js中数组的内容是不存在单一性。我们可以通过在数组中嵌套数组的方式作为二维或者多维数组使用。

创建

二维数组类似一种由行和列构成的数据表格,js中创建二维数组时,需要先创建一维数组并将数组中的每个元素变成一维数组,我们就能够得到n行一列的二维数组了。

function print(value) {
    console.log(value);
}

let twoArr = [];
let n = 5;
for (let i = 0; i < n; i++) {
    twoArr[i] = []
}

print(twoArr)

每次创建多维数组时都需要频繁操作,而且上面创建数组的方法生产的数组的元素值均为undefined,这时可以通过拓展自带的Array对象进行添加创建二维数组的方法。

Array.matrix = function(numrows, numcols, initial) {
  var arr = [];
  for (var i = 0; i < numrows; ++i) {
    var columns = [];
    for (var j = 0; j < numcols; ++j) {
      columns[j] = initial;
    }
    arr[i] = columns;
  }
  return arr;
}

列表

列表是一组有序的数据。每个列表中的数据项称为元素。元素的内容没有内容的限制,严格来说受到计算机内存的限制。不包含任何元素的列表称为空列表,包含元素的个数称为列表的 length,内部用一个变量 listSize 保存列表中元素的个数。列表末尾 append 一个元素, 可以在一个给定元素后或列表的起始位置 insert 一个元素,设定使用 remove 方法从列表中删除元素,使用 clear 方法清空列表中所有的元素。

img

创建列表

// 环境函数
function print(value) {
  console.log(value);
}

// 创建列表数据结构
function List() {
  this.listSize = 0; // 列表的初始长度
  this.pos = 0; // 指针的初始位置
  this.dataStore = []; // 初始化一个空数组来保存列表元素
  // 清空数组
  this.clear = function clear() {
    delete this.dataStore;
    this.dataStore = [];
    this.listSize = 0;
    this.pos = 0;
  };
  // 根据元素值查询其所在列表的下标
  this.find = function find(element) {
    for (var i = 0; i < this.dataStore.length; ++i) {
      // 判断值是否相等
      if (this.dataStore[i] == element) {
        return i;
      }
    }
    // 无法匹配则返回-1
    return -1;
  };
  // 输出数组
  this.toString = function toString() {
    return this.dataStore;
  };
  // 某个元素值之后插入一个元素
  this.insert = 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;
  };
  // 列表尾部添加一个新的元素且列表长度加一
  this.append = function append(element) {
    this.dataStore[this.listSize++] = element;
  };
  // 根据元素值进行移除元素
  this.remove = function remove(element) {
    // 查找当前值的下标
    var foundAt = this.find(element);
    if (foundAt > -1) {
      this.dataStore.splice(foundAt, 1);
      --this.listSize;
      return true;
    }
    return false;
  };
  // 指针指向第一个元素
  this.front = function front() {
    this.pos = 0;
  };
  // 指针指向最后一个元素
  this.end = function end() {
    this.pos = this.listSize - 1;
  };
  // 指针往前移一位
  this.prev = function prev() {
    // 判断是否溢出
    if (this.pos > 0) {
      --this.pos;
    }
  };
  // 指针往后移一位
  this.next = function next() {
    // 判断是否溢出
    if (this.pos < this.listSize - 1) {
      ++this.pos;
    }
  };
  // 返回当前列表的元素
  this.length = function length() {
    return this.listSize;
  };
  // 获得当前指针的值
  this.currPos = function currPos() {
    return this.pos;
  };
  // 指针移动到特定位置
  this.moveTo = function moveTo(position) {
    this.pos = position;
  };
  // 获取当前指针的元素
  this.getElement = function getElement() {
    return this.dataStore[this.pos];
  };
  // 获取元素的个数
  this.length = function length() {
    return this.listSize;
  };
  // 判断元素值是否存在于列表中
  this.contains = function contains(element) {
    for (var i = 0; i < this.dataStore.length; ++i) {
      if (this.dataStore[i] == element) {
        return true;
      }
    }
    return false;
  };
}

// 测试数据
var names = new List();
names.append("Clayton");
names.append("Raymond");
names.append("Cynthia");
names.append("Jennifer");
names.append("Bryan");
names.append("Danny");

names.front();
names.next();
print(names.getElement()); // 显示 Raymond

栈是一种特殊的列表,栈内元素只可以通过列表的一端进行访问并称为栈顶。栈是一种先入后出的数据结构。任何不在栈顶的元素都无法被访问,对栈的操作主要是将元素压入栈和弹出栈。

创建

栈的常见操作是peek方法返回栈顶元素进行预览,通过pop将栈顶弹出,push进行元素压栈。实现记录栈顶元素的位置,引入变量top进行记录栈顶的位置,随着压栈增加,出栈减小。定义栈的clear清空和empty变量表示是否栈内是否含有元素。

// 创建列表数据结构
function Stack() {
  this.dataStore = [];
  this.top = 0; // 表示栈顶位置
  // 元素压栈操作
  this.push = function push(element) {
    this.dataStore[this.top++] = element;
  };
  // 元素弹栈操作
  this.pop = function pop() {
    this.top = this.top - 1; // 指针下移找到栈顶元素
    return this.dataStore[this.top];
  };
  // 获得栈顶元素
  this.peek = function peek() {
    return this.dataStore[this.top - 1];
  };
  // 获取栈内元素个数
  this.length = function length() {
    return this.top;
  };
  this.clear = function clear() {
    delete this.dataStore;
    this.dataStore = [];
    this.top = 0;
  };
}

测试

var s = new Stack();
s.push("David");
s.push("Raymond");
s.push("Bryan");
print("站内元素个数: " + s.length()); // 3
print("栈顶元素: " + s.peek()); // Bryan
var popped = s.pop();
print("弹出栈的元素: " + popped); // Bryan
print(s.peek()); // Raymond
s.push("Cynthia");
print(s.peek()); // Cynthia
s.clear();
print("站内元素个数: " + s.length()); // 0
print(s.peek()); // undefined
s.push("Clayton");
print(s.peek()); // Clayton

小练习

十进制转换成为2进制

Tips: 联系数据仅支持2-9的整数

// 环境函数
function print(value) {
  console.log(value);
}

// 创建列表数据结构
function Stack() {
  this.dataStore = [];
  this.top = 0; // 表示栈顶位置
  // 元素压栈操作
  this.push = function push(element) {
    this.dataStore[this.top++] = element;
  };
  // 元素弹栈操作
  this.pop = function pop() {
    this.top = this.top - 1; // 指针下移找到栈顶元素
    return this.dataStore[this.top];
  };
  // 获得栈顶元素
  this.peek = function peek() {
    return this.dataStore[this.top - 1];
  };
  // 获取栈内元素个数
  this.length = function length() {
    return this.top;
  };
  this.clear = function clear() {
    delete this.dataStore;
    this.dataStore = [];
    this.top = 0;
  };
}

function mulBase(num, base) {
  var s = new Stack(); // 声明栈
  // 方法一
  while (1) {
    // 取余放入栈中
    s.push(num % base);
    // 更改被除数
    num = Math.floor(num / base);
    // 判断被除数是否小于0
    if (num <= 0) {
      break;
    }
  }
  // 设置输出字符串
  let converted = "";
  // 处理输出字符串
  while (s.length() > 0) {
    converted = converted + s.pop();
  }
  return converted;

  // 方法二
  // do {
  //   s.push(num % base);
  //   num = Math.floor((num /= base));
  // } while (num > 0);
  // var converted = "";
  // while (s.length() > 0) {
  //   converted += s.pop();
  // }
  // return converted;
}

print(mulBase(6, 2)); // 110

判断回文

回文是一个单词或者数字是对称,从前和往后写都是相同结果,例如:dad、1001、racecar就是回文现象,使用栈可以轻松判断是否回文。

function isHuiWen(str) {
  let s = new Stack();
  // 字符串分为字符数组
  // 遍历压入栈中
  // 获得将数组元素组合成为反转的字符串
  // 反转字符串与原字符串比较看是否相等
  str.split("").map((item) => {
    s.push(item);
  });
  let recoverStr = "";
  while (s.length() > 0) {
    recoverStr = recoverStr + s.pop();
  }
  if (str === recoverStr) {
    return "符合回文要求";
  } else {
    return "不符合";
  }
}

print(isHuiWen("123211")); // 不符合
print(isHuiWen("dad")); // 符合回文要求

队列

队列就是一种列表,不同的是队列只能在队尾插入元素,队首删除元素,队列用于储存顺序排列的数据,拥有着先进先出的特点(FIFO),队列常用于操作系统的进程调度,打印任务池相关场景。

创建

队列的重要操作是读取队头的元素(peek),属于查阅但是不删除的范畴,使用 length 属性判断队列中的个数,队通过使用 clear() 方法清空队列。

// 环境函数
function print(value) {
  console.log(value);
}

function Queue() {
  this.dataStore = [];
  // 队列尾部插入一个元素
  this.enqueue = function enqueue(element) {
    this.dataStore.push(element);
  };
  // 队列头部删除一个元素
  this.dequeue = function dequeue() {
    return this.dataStore.shift();
  };
  // 返回队列首元素
  this.front = function front() {
    return this.dataStore[0];
  };
  // 返回队列尾元素
  this.back = function back() {
    return this.dataStore[this.dataStore.length - 1];
  };
  //
  this.toString = function toString() {
    let retStr = "";
    for (let i = 0; i < this.dataStore.length; ++i) {
      retStr += this.dataStore[i] + "\n";
    }
    return retStr;
  };
  this.empty = function empty() {
    if (this.dataStore.length == 0) {
      return true;
    } else {
      return false;
    }
  };
  // 返回队列的个数
  this.count = function conut() {
    return this.dataStore.length;
  };
}

// 测试
var q = new Queue();
q.enqueue("Meredith");
q.enqueue("Cynthia");
q.enqueue("Jennifer");
print(q.toString());
q.dequeue();
print(q.toString());
print("Front of queue: " + q.front());
print("Back of queue: " + q.back());

// Meredith
// Cynthia
// Jennifer

// Cynthia
// Jennifer

// Front of queue: Cynthia
// Back of queue: Jennifer

小练习

基数排序

建立一个数组,按顺序放入10个队列,依次根据个位数和十位数的值放入对应数组的索引位置中的队列并输出。

// 环境函数
function print(value) {
  console.log(value);
}

function Queue() {
  this.dataStore = [];
  // 队列尾部插入一个元素
  this.enqueue = function enqueue(element) {
    this.dataStore.push(element);
  };
  // 队列头部删除一个元素
  this.dequeue = function dequeue() {
    return this.dataStore.shift();
  };
  // 返回队列首元素
  this.front = function front() {
    return this.dataStore[0];
  };
  // 返回队列尾元素
  this.back = function back() {
    return this.dataStore[this.dataStore.length - 1];
  };
  //
  this.toString = function toString() {
    let retStr = "";
    for (let i = 0; i < this.dataStore.length; ++i) {
      retStr += this.dataStore[i] + "\n";
    }
    return retStr;
  };
  this.empty = function empty() {
    if (this.dataStore.length == 0) {
      return true;
    } else {
      return false;
    }
  };
  // 返回队列的个数
  this.count = function conut() {
    return this.dataStore.length;
  };
}

// 建立一个数组
let arr = [];
// 放入队列
for (let i = 0; i < 10; i++) {
  arr[i] = new Queue();
}
// 生成10个随机数
let nums = [];
for (let i = 0; i < 10; i++) {
  nums[i] = Math.floor(Math.random() * 100);
}
dispArray(nums);

handleGewei();
dispArray(nums);
handleShiwei();
dispArray(nums);

function handleGewei() {
  // 根据个位数进行排序
  for (let i = 0; i < nums.length; i++) {
    arr[nums[i] % 10].enqueue(nums[i]);
  }
  let count = 0;
  for (let i = 0; i < arr.length; i++) {
    while (!arr[i].empty()) {
      // 从队列中输出元素
      nums[count++] = arr[i].dequeue();
    }
  }
}
function handleShiwei() {
  // 根据十位数进行排序
  for (let i = 0; i < nums.length; i++) {
    arr[Math.floor(nums[i] / 10)].enqueue(nums[i]);
  }
  let count = 0;
  for (let i = 0; i < arr.length; i++) {
    while (!arr[i].empty()) {
      // 从队列中输出元素
      nums[count++] = arr[i].dequeue();
    }
  }
}
// 展示方法
function dispArray(arr) {
  let str = "";
  for (let i = 0; i < arr.length; ++i) {
    str = str + " " + arr[i];
  }
  console.log(str);
}

链表

字典

散列

集合

二叉树

红黑树