| 根据运行的环境，操作系统可以分为桌面操作系统，手机操作系统，服务器操作系统，嵌入式操作系统等。 
以下是每个数据结构的详细介绍. 对于每种数据结构，它将主要从JS的角度列出经常遇到的经典问题和实现方法，但是只要思路清楚，使用哪种语言，对于本文来说就不那么重要了
对于数组，它是Wuli中程序员最熟悉的数据结构. 我仍然记得当我还是学生时比较数组和链接列表.
最受关注的是两点: 查询和插入删除. 当需要高频率插入和删除时，选择链表；当您需要高频查询时，选择数组.
数组插入和删除: 要插入和删除项目，首先需要找到满足特定条件的位置，然后在插入和删除项目时，需要移动所有其他项目，以便可以清空或填充插入和删除位置，这样您就可以动员除了所有项目之外，这些操作的执行频率很高，而且性能远不及直接修改下一个列表. 链表查询: 如果要查询特定位置的节点，则需要从头节点开始依次遍历；并且数组具有下标，则可以直接访问下标的项. 在数组中找到第k个最小元素
使用快速排序的想法，left []（<）right []，从小到大排序，如果m="">
实现:
var kArr = function(arr,k){
if(arr.length < k){console.log("没有这么多数呀！");return}
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];
var left = [];
var right = [];
for (var i = 0; i < arr.length; i++){
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
if(left.length<k){
return right[k-left.length];
}
else{
return left[k];
}
}
var arr = [1,3,2,5,11,43,22,77,45,12];
console.log(kArr(arr,6));
复制代码
找到第一个没有重复的数组元素
实现: （1）用两层循环直接扫描数组（2），用map计算每个元素val的出现次数，然后返回val为1的第一项.
谈到上面的第二种方法，作者冻结了一些. 在加入秋季技巧之前，面试女士问了一个简单的算法问题，并问我进行了哪些优化. 当时我以为这很复杂，我完全没有去做. 受试者认为c语言单链表冒泡排序，哭泣和流鼻涕，仍然需要回答问题以找到感觉-.-
//查找第一个没有重复的元素
var oneArr = function(arr){
if(arr.length === 1){return arr[0]};
var obj = {};
arr.forEach(element => {
if(!obj[element]) obj[element] = 1;
else obj[element]++;
});
for(var key in obj){
if(obj[key] === 1) {
return key;
}
}
}
var arr = [1,3,2,5,11,3,22,77,45,1,77,0,0];
console.log(oneArr(arr));
复制代码
合并两个排序的数组
实现:
由于JS的实现非常简单，只需在concat之后直接排序，如果不使用这些方法，则可以使用两个指针指向两个数组，让两个元素进行比较，将其中的小元素放入新数组中，并将较小元素的数组指针增加1，并继续进行比较，直到遍历一个数组为止. 最后，将另一个数组的其余元素放入新数组.
重新排列数组中的正数和负数
实现:
使用快速排序的思想，将整数和负数分别放在right []和left []中，然后分别对它们进行排序，最后进行合并
堆栈的主要核心: 先进；堆栈是一种特殊的线性表，只能性表的一端进行操作，允许堆栈的顶部进行操作，而不允许堆栈的底部进行操作.
递归函数的实现利用堆栈数据结构. 调用递归函数时，局部变量，形式参数值和被调用函数的返回地址都存储在递归工作堆栈中. 该函数将在运行时按照后进先出的顺序执行，以完成递归操作.
根据编译原理，我们使用堆栈的结构特征来计算后缀表达式.
示例: 中缀表达式a + b * c +（d * e + f）* g，转换为后缀表达式后为a b c * + d e * f + g * +
特定的转换过程:
1）如果遇到操作数，请直接输出
2）如果遇到运算符，则将其放在堆栈上，并将左括号也放在堆栈上
3）如果遇到右括号，将弹出堆栈元素，并且将输出弹出的运算符，直到遇到左括号为止. 左括号只会弹出而不会输出
4）其他运算符，例如+，*，（从堆栈中弹出元素，直到遇到优先级较低的元素或空堆栈. 弹出这些元素后，只能将遇到的运算符按入栈，这很重要请注意，它只会在遇到时弹出（在其他情况下不会弹出）
5）如果读取了输入的结尾，则将按顺序弹出堆栈中的所有元素
实现: 首先通过js-class实现堆栈结构，然后使用辅助堆栈帮助实现堆栈堆栈排序
class Vect{
constructor(){
this.stack = [];
}
//入栈
in(num){
if (typeof num != "number") return false;
this.stack.push(num);
}
//出栈
out(){
if(this.stack.length>0){
let last = this.stack.pop();
return last;
}
}
//输出
print(){
if(this.stack.length === 0){
console.log("栈空了");
}
else{
console.log(...this.stack);
}
}
}
//利用辅助栈对存储栈排序
var sort = function(stack){
var help = new Vect();
while(stack.stack.length){
var pop = stack.out();
if(help.stack.length&&help.stack[help.stack.length-1]<pop) {//里面的判断顺序不能颠倒，否则出现 java.util.EmptyStackException
stack.in(help.out());//当满足help不为空，且help的元素小于pop(这样排出的顺序顶到底是从小到大的)
} //将help里的元素返回到stack中
help.in(pop);//无论什么情况，只要stack不为空，都将pop压入help
}
while(help.stack.length) {//当help不为空的时候，help里面的元素顶到底是从小到大的，
stack.in(help.out());//所以将help弹到stack中是顶到底是从大到小的
}
stack.print();
}
var stack = new Vect();
stack.in(2);
stack.in(1);
stack.in(5);
sort(stack);
复制代码
详细的排序过程:
进入堆栈[2,1,5]，创建空堆栈helpstack pop pop = 5，因为此时帮助为空，直接在帮助堆栈中，然后pop pop = 1，因为1 <5，直接进入帮助堆栈（确保帮助堆栈是从上到下的: 大-小），然后在堆栈上弹出pop="2，因为1"><2，将pop =="" 1在帮助中直接放入堆栈，然后将2放入堆栈继续堆栈，堆栈会弹出pop="">c语言单链表冒泡排序，因为2> 1，直接在帮助堆栈中，最后将所有帮助弹出到堆栈中，即有序生成堆栈.
帮助堆栈
堆栈堆栈
为简单起见，我们直接判断（）是否匹配，如果需要其他符号，我们可以添加判断
实现思路:
在实现过程中，默认值为“（“”“）”，如果第一件事遇到“）”，它将直接跳出，显示“还有更多右括号”.
扫描str遇到“（”，堆栈遇到“）”，判断堆栈，如果为空，则有更多右括号，返回false；如果不为空，则判断顶部堆栈的顶部，如果不为左括号，则不匹配，返回false；否则，返回false. 如果是左括号，则退出堆栈，继续下一次扫描，确定堆栈是否为空，如果不为空，则表示左括号不匹配，左括号更多，返回false；否则，返回false. 否则匹配成功，返回true
var match = function(str){
var strStack = new Vect();
var strArr = str.split('');
var p = 0;
while(p<strArr.length){
if(strArr[p]==="("){
strStack.in(strArr[p]);
}
if(strArr[p]===")"){
if(strStack.stack.length===0){
console.log("右括号多了");
return false;
}
else if(strStack.stack[strStack.stack.length-1]!=="("){
console.log("不匹配");
return false;;
}
else{
strStack.out();
}
}
p++;
}
if(strStack.stack.length){
console.log("左括号多于右括号");
return false;
}
else{
console.log("左右括号匹配正确");
return true;
}
}
match("((a+b)*v)/2)");
复制代码
队列与堆栈相反. 核心是先进先出. 实现方法类似于堆栈. 区别在于入队和出队的顺序.
链表是由节点和下一个连接的链. 在本文中，我们将简要介绍单链表结构的实现以及相关问题的实现
JS实现单个链表的结构，并实现链表的添加，删除，搜索和反向
class Node{
constructor(element){
this.element = element;
this.next = null;
}
}
class LinkedList{
constructor(){
this.length = 0;
this.head = null;
}
append(element){
let node = new Node(element);
let current;
if(this.head == null) this.head = node;
else{
current = this.head;
while(current.next){
current = current.next;
}
current.next = node;
}
this.length++;
}
removeAt(position){
if(position >-1 && position < this.length){
let current = this.head;
let index = 0;
let previous;
if(position == 0){
this.head = current.next;
}else{
while(index++ < position){
previous = current;
current= current.next;
}
previous.next = current.next;
}
this.length--;
return current.element;
}
else{
return null;
}
}
insert(position,element){ //插入
if(position >-1 && position <= this.length){
let node = new Node(element);
let current = this.head;
let index = 0;
let previous;
if(position==0){
node.next = current;
this.head = node;
}else{
while(index++<position){
previous = current;
current = current.next;
}
previous.next = node;
node.next = current;
}
this.length++;
return true;
}else{
return false;
}
}
toString(){ //转成字符串
let current = this.head;
let str = '';
while(current){
str += ','+current.element;
current = current.next;
}
return str;
}
indexOf(element){ //索引
let current = this.head;
let index = 0;
while(current){
if(current.element == element){
return index;
}
index++;
current = current.next;
}
return -1;
}
reverse(){ //反转
if(this.head === null || this.head.next===null) return;
let current = this.head;
let pnext = current.next;
current.next = null;
while(pnext){
let pp = pnext.next;
pnext.next = current;
current = pnext;
pnext = pp;
}
this.head = current;
}
}
let link = new LinkedList();
link.append("111");
link.append("222");
link.append("333");
link.reverse();
console.log(link);
console.log(link.indexOf("111"));
复制代码
相反的结果:
检查链表中是否有循环返回链表的倒数第二个元素以删除链表中的重复元素
说明: 图由一组有限的顶点和一组顶点之间的边组成，通常表示为: G（V，E），其中G表示图，而V在图G中. 是图G中的一组边. 图中的数据元素称为顶点，而该顶点集是无限非空的. 在图中，任何两个顶点之间可能存在关系. 顶点之间的逻辑关系由边表示，并且边集可能为空.
确定图是否为树: 确保图已连接，并且图没有环
（1）是否有环: 两个数组，一个二维数组作为图的邻接矩阵，一个一维数组，用于标记是否已遍历一个节点（2）是否已连接: 检查上面的一维数组是否具有遍历
统计图中的边数，n个节点: 完全有向图n（n-1），完全无向图n（n-1）/ 2
N二叉树，平衡树，二叉树，二叉搜索树，平衡二叉树，红色和黑色树，B树
摘要:
具有n个节点的二叉树，分支树为n-1. 如果二叉树的高度为h，则至少有h个节点，并且最多2 ^ h -1个节点（完整的二叉树）. 具有n个节点的二叉树，高度最大n，最小高度log2（n + 1）向上舍入一个具有n个节点的完整二叉树，高度height log2（n + 1）向上舍入一个Huffman树: 权重最小的二叉树
非叶??节点的最大数量为两个子节点；左子节点小于右子节点；左右边之差不超过1；没有相同的重复节点
红黑树也是平衡的二叉树
排序算法，这是四个主要细节，描述了作者的个人理解，并且将来会继续覆盖其他内容
算法算法
如何定义稳定和不稳定的排序算法？
（1）稳定: 排序前b之前a，a = b，排序后b之前a静止（冒泡，插入，合并，基数）（2）不稳定: 排序前a之前b之前，a = b，排序后，a可能在b（select，fast，hill，heap）之后
以下按从小到大的顺序分析了各种实现:
从数组中的第一个数字开始，然后依次遍历数组中的每个数字. 通过相邻的比较交换，每轮循环都会找到最大数量的剩余未排序数字，并在数组“最后一个”中“冒泡”.
//冒泡
for(i=0;i<len-1;i++){
for(j=0;j<len-1-i;j++){//每一轮最后一个元素都是最值，所以可以不用再比
if(arr[j]>arr[j+1]){
var temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
复制代码
从所有记录中选择最小的数据元素，以便与第一个位置的记录进行交换；然后在剩余记录中找到最小的交换，并将记录放在第二个位置，循环直到只有最后一个保留Data元素.
//选择
for(i=0;i<len-1;i++){
var minIndex = i;
for(j=i+1;j<len;j++){
if(arr[j]<arr[minIndex]){
minIndex = j;
}
}
var temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
复制代码
从要排序的n条记录中的第二条记录开始，然后依次与前一条记录进行比较以找到插入位置. 每个外循环结束后，将当前编号插入适当的位置.
//插入
for(i=1;i<len;i++){
if(arr[i]<arr[i-1]){
var temp = arr[i];
var j = i-1;
while(j>=0 && temp<arr[j]){
arr[j+1] = arr[j];
j--;
}
arr[j+1] = temp;
}
}
复制代码
插入排序的优化: 当我们找到要插入的位置时，我们可以使用二进制搜索来找到位置
// 优化（二分查找）
for(var i = 1;i<len;i++){
var key = arr[i];
var j = i-1;
var right = i-1;
var left = 0;
while(left<=right){
var mid = parseInt((left+right)/2);
if(key<arr[mid]){
right = mid-1;
}
else{
left = mid+1;
}
}
// 这里最终找到的是left
for(var j=i+1;j>=left;j--){
arr[j+1] = arr[j];
}
arr[left] = key;
}
复制代码
从序列中选择一个元素作为引用，并左右创建两个数组，将小于引用的元素放在左侧，将大于引用的元素放在右侧，然后递归，最后连接两个数组get是排序后的数组.
var quickSort2 = function(arr) {
if (arr.length <= 1) { return arr; }
var pivotIndex = Math.floor(arr.length / 2);
var pivot = arr.splice(pivotIndex, 1)[0];
var left = [];
var right = [];
for (var i = 0; i < arr.length; i++){
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return quickSort2(left).concat([pivot], quickSort2(right));
};
复制代码
里面有些内容还没有补充，持续整理更新。。。有错误请指教，共同进步
复制代码
转载于:
本文来自本站，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-259602-1.html
| 
