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)
网友评论