1.数据结构的定义
数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率.
2.几种数据结构
2.1queue(队列)
思想:先进先去,就是像我们在餐厅取号
示例:生成一个叫号的网页,点击[取号]生成一个号码
点击[叫号]显示请xxx号就餐
<!DOCTYPE html>
<html>
<head>
<title>Parcel Sandbox</title>
<meta charset="UTF-8" />
</head>
<body>
<div id="screen"></div>
<div class="actions">
<button id="createNumber">取号</button>
<button id="callNumber">叫号</button>
</div>
<div>最新号码 <span id="newNumber"></span></div>
<div>当前队列 <span id="queue"></span></div>
<script src="src/index.js"></script>
</body>
</html>
#screen{border: 1px solid black;
width: 200px;
height: 200px;
display: flex;
justify-content: center;
align-items: center;
font-size: 20px;
}
import "./styles.css";
const btnCreateNumber = document.querySelector("#createNumber");
const btnCallNumber = document.querySelector("#callNumber");
const spanNewNumber = document.querySelector("#newNumber");
const spanQueue = document.querySelector("#queue");
const divScreen = document.querySelector("#screen");
const queue = [];
let number = 0;
btnCreateNumber.onclick = () => {
number += 1;
queue.push.call(queue, number); // 等价于 queue.push(number)
spanNewNumber.innerText = number;
spanQueue.innerText = JSON.stringify(queue);
};
btnCallNumber.onclick = () => {
const n = queue.shift.call(queue); // 等价于 queue.shift()
// if n === undefined 没处理
divScreen.innerText = `请 ${n} 号就餐`;
spanQueue.innerText = JSON.stringify(queue);
};
image.png
2.2stack(栈)
思想:先进后出
示例:代码的弹栈过程
image.png
2.3Linked List(链表)
思想:一个链接一个
2.3.1Linked List的形式
image.png
2.3.2对链表的操作
//创建新的节点
const createList = value => {
return createNode(value);
};
//增加节点
const appendList = (list, value) => {
const node = createNode(value);
let x = list;
while (x.next) {
x = x.next;
}
// x.next === null //x 是最后一个节点
x.next = node;
return node;
};
//删除节点
const removeFromList = (list, node) => {
//链表
let x = list;
let p = node; // 课堂里将 p 初始化为 null，这里改为 node
while (x !== node && x !== null) { // 对 null 进行处理，如果 node 不在 list 中，x 就可能为 null
p = x;
x = x.next;
}
if(x === null){ // 若 x 为 null，则不需要删除，直接 return， false 表示无法删除不在list里的节点
return false
}else if(x === p){ // 这说明要删除的节点是第一个节点
p = x.next
return p // 如果删除的是第一个节点，那么就要把新 list 的头节点 p 返回给外面，即 newList = removeFromList(list, list)
}else{
p.next = x.next;
return list // 如果删除的不是第一个节点，返回原来的 list 即可
}
};
//创建新的节点的函数
const createNode = value => {
return {
data: value,
next: null
};
};
//遍历节点
const travelList = (list, fn) => {
let x = list;
while (x !== null) {
fn(x);
x = x.next;
}
};
const list = createList(10);
const node2 = appendList(list, 20);
const node3 = appendList(list, 30);
const node4 = appendList(list, 40);
travelList(list, node => {
console.log(node.data);
});
2.4哈希表
思想:就是键和值的组合
难点:如何快速找出需要找到的键值对的组合
2.5tree(树结构)
思想:像公司和中国与省份之间的关系一样的关系,一个链多个
image.png
2.5.1对树的操作
/创建树
const createTree=value=>{
return{
data:value,
children:null,
parent:null,
};
};
//增加新的节点
const addChild=(node,value)=>{
const newNode={
data:value,
children:null,
parent:node,
};
node.children=node.children||[];
node.children.push(newNode);
return newNode;
}
//遍历所有节点,先根遍历
const travel=(tree,fn)=>{
fn(tree);
if(!tree.children){
return;
}
for(let i=0;i<tree.children.length;i++){
travel(tree.children[i],fn);
}
};
//删除节点
const removeNode=(tree,node)=>{
const siblings=node.parent.children;
let index=0;
for(let i=1;i<siblings.length;i++){
if(siblings[i]===node){
index=i;
}
}
siblings.splice(index,1);
};
const tree=createTree(10);
const node2=addChild(tree,20);
const node3=addChild(tree,30);
const node4=addChild(tree,40);
//给node2在增加节点
addChild(node2,200);
addChild(node2,201);
console.log(tree);
//打印出节点数据
const fn=node=>{
console.log(node.data);
}
travel(tree,fn)
//删除节点
removeNode(tree,node4)
本文为本人的原创文章，著作权归本人和饥人谷所有，转载务必注明来源.
网友评论