Get Started

• 伪代码
• 流程图
• 数据结构
  队列&栈
  链表

伪代码

用三种语句表达逻辑，也就是说用js关键字+语句大意来构成代码结构，用来整理思路。

流程图

流程图同样也是用来表示代码的一种方式，比伪代码更加详细，如果流程图严格按照规定方式将每一步写出来，基本上就是用语言将代码写出来了。一般只是画一个示意图。

• 顺序执行语句

  
  image.png

• 条件判断语句

  
  image.png

• 循环语句

  
  image.png

数据结构

就是数据与数据之间的关系和结构
如何表示两个数据
• 如果顺序有意义
[x, y]和[y, x]不一样
要提供first和last操作
• 如果顺序无意义
(x, y)和(y, x)一样
如何表示N个数据
同上
如何表示N对N数据
• 比如学号
用【哈希表】表示
hash = {1001 => '小方', 1001 => '小红'}

数据结构=数据形式+操作

不同形式的数据暴露不同的操作
目前使用过的数据结构
• 数组
可分为队列、栈等
• 哈希表
用来存储key-value对

队列（Queue）

先进先出FIFO的数组
• 题目
实现一个餐厅叫号网页，点击【取号】生成一个号码
点击【叫号】显示【请X号就餐】
• 代码思路
先选择对列queue作为数据结构
queue.push为入队，queue.shift为出队
练一下call用法
• 代码
• https://github.com/AkaneTang/queue-demo-1
• 小要点
spanQueue.innerText = queue.toString();
>>当前队列 1,2,3,4,5
用toString将数组转换为字符串，每个值之间用，隔开。
spanQueue.innerText = JSON.stringify(queue);
>>当前队列 [1,2,3,4]
将数组转化为字符串
• 备注
Codesandbox.io 已经升级，登录之后，可以无限免费创建项目。
用途：用来在线创建vscode项目。

栈（Stack）

后进先出LIFO的数组
• 举例
JS函数的调用栈call stack就是一个栈
递归函数的调用栈。
• 代码

function f1(){let a = '1'; return a+f2()}
function f2(){let b = '2'; return b+f3()}
function f3(){let c = '3'; return c}
f1()

链表（Linked List）

• 实际使用

let array = [1, 2, 3]
array.__proto__ === Array.prototype
Array.prototype.__proto__ === Object.prototype

从这个角度看对象，就是链表
• 代码

list = create(value)
node = get(index)
append(node, value)
remove(node)
travel(list, fn)

链表的变形
• 双向链表
每个节点有一个previous指向上一个节点
• 循环链表
最后一个节点的next指向头节点
• 代码
https://github.com/AkaneTang/queue-demo-1

哈希表（key-value pairs）

• 难点场景
假设哈希表hash里有一万对键值对
如何使得读取hash['xxx']速度最快
• 解决办法
不作任何优化，hash['xxx']需要遍历所有key，O(n)
对key排序，使用二分查找，0(log2 n)
对字符串对应的ASCII数字做索引，O(1)
对索引做除法取余数, O(1)
冲突了，就顺延

树（tree）

一个链多个
• 代码

let tree = createTree(value)
let node = createNode(value)
addChild(tree, node)
removeChild(node1, node2)
travel(tree)