数据结构特点分析

// 声明一个 3x3 的二维数组并初始化
const matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
];

console.log(matrix);
// 输出:
// [
//   [1, 2, 3],
//   [4, 5, 6],
//   [7, 8, 9]
// ]

double balance[10] = {1,2,2,2,2,2,2,2,2} // 一维

int a[3][4] = { // 二维
	{0,1,2,3},
    {0,1,2,3},
    {0,1,2,3}
}

struct Node {
   int data;
   Node *next;
};

class LinkedList {
   private: Node *head, *tail;
   public: LinkedList() {
       head = NULL;
       tail = NULL;
   }
   void addNode(int n) {
       Node *tmp = new Node;
       tmp->data = n;
       tmp->next= NULL;
       if(head == NULL) {
           head = tmp;
           tail = tmp;
       }
       else {
           tail->next = tmp;
           tail = tail->next;
       }
   }
};

#define SIZE 10

class Stack {
   private: int *arr;
   private: int size = SIZE;
   private: int capacity;
   private: int top;
   public: Stack() {
       size = SIZE;
       arr = new int(size);
       top = -1;
   }
   public:void push(int);
   public: int pop();
};

void Stack::push(int value) {
   if(top == capacity - 1) {
       exit(EXIT_FAILURE);
   }
   arr[++top] = value;
}

int Stack::pop() {
   if(top == -1) {
       exit(EXIT_FAILURE);
   }
   return arr[top--];
}

// 模版1： 栈实现
function bfs() {  
  let level = -1
  // 第一步：初始化Q  
  let Q = [start]
  // 第二步：遍历Q  
  while(Q.length !== 0) {  
    level++
    // 第三步：处理逻辑
    const start = Q.shift()
    for (;;) {
      if(findTheTarget) { return } 
      // 第四步：更新Q  
      Q.push(newItem)  
    }  
  }  
}

  
// 模版2
function bfs() {  
  let level = -1
  // 第一步：初始化Q  
  let Q = [start]
  // 第二步：遍历Q  
  while(Q.length !== 0) {  
    level++
    // 第三步：处理逻辑
    let next = []
    for (let i of Q) {
      if(i.left) next.push(i.left)
      if(i.right) next.push(i.right)
      // 第四步：更新Q  
      Q = next  
    }  
  }  
}

// 模版1: 数组存储的遍历
function travalUtl(narr, index, col, map) {  
  if (!narr[index]) return;  
  travalUtl(narr, 2 * index, col - 1, map);  
  // do something  
  travalUtl(narr, 2 * index + 1, col + 1, map);  
}


// 模版2: 只有索引，没有存储。
function travalUtil(i, j, finishi, finishj, res) {  
  if (i > finishi || j > finishj) return;  
  if (i === finishi && j === finishj) {  
    res.count++;  
    return;  
  }  
  travalUtil(i, j + 1, finishi, finishj, res);  
  travalUtil(i + 1, j, finishi, finishj, res);  
}

void preOrder(Node *node) {
   if(!node) return;
   print node
   preOrder(node->left)
   preOrder(node->right)
}

void inOrder(Node *node) {
  if(!node) return;
  inOrder(node->left)
  print node
  inOrder(node->right)
}

void postOrder(Node *node) {
  if(!node) return
  postOrder(node->left)
  postOrder(node->right)
  print node
}

function update(row, column, rooms, step, next) {
  if (
    row < 0 ||
    row >= rooms.length ||
    column < 0 ||
    column >= rooms[row].length ||
    rooms[row][column] !== 2147483647
  )
    return;
  rooms[row][column] = step;
  next.push([row, column]);
}

function bfs(rooms) {
  // 第一步：初始化
  let Q = [];
  for (let i = 0; i < rooms.length; i++) {
    const element = rooms[i];
    for (let j = 0; j < element.length; j++) {
      Q.push([i, j]);
    }
  }

  // 第二步：遍历
  let step = 0;
  while (Q.length !== 0) {
    // 第三步：处理逻辑
    let next = [];
    for (let [row, column] of Q) {
      update(row, column - 1, rooms, step, next);
      update(row, column + 1, rooms, step, next);
      update(row - 1, column, rooms, step, next);
      update(row + 1, column, rooms, step, next);
    }
    step++;
    // 第四步： 更新Q
    Q = next;
  }
  return rooms;
}

export default bfs;

function travalUtl(narr, curIndex, col, map) {
  if (!narr[curIndex]) return;

  var letfIndex = 2 * curIndex;
  travalUtl(narr, letfIndex, col - 1, map);

  if (narr[curIndex]) {
    if (map[col]) {
      map[col].push(narr[curIndex]);
      map[col].sort((a, b) => a - b);
      console.log(map[col]);
    } else {
      map[col] = [narr[curIndex]];
    }
  }

  var rightIndex = 2 * curIndex + 1;
  travalUtl(narr, rightIndex, col + 1, map);
}

function travelUtil(arr, index, v) {
  if (!arr[index] || !v.result) return;

  if (arr[2 * index] && arr[index] < arr[2 * index]) {
    v.result = false;
    return;
  }
  if (arr[2 * index + 1] !== null && arr[index] > arr[2 * index + 1]) {
    v.result = false;
    return;
  }

  travelUtil(arr, 2 * index, v);
  travelUtil(arr, 2 * index + 1, v);
}

function travalUtil(i, j, finishi, finishj, res) {
  if (i > finishi || j > finishj) return;
  if (i === finishi && j === finishj) {
    res.count++;
    return;
  }
  travalUtil(i, j + 1, finishi, finishj, res);
  travalUtil(i + 1, j, finishi, finishj, res);
}

// Left Left Case imbalance
if (balance > 1 && key < node->left->key)
	return rightRotate(node);

// Right Right Case imbalance
if (balance < -1 && key > node->right->key)
	return leftRotate(node);

// Left Right Case imbalance
if (balance > 1 && key > node->left->key)
{
	node->left = leftRotate(node->left);
	return rightRotate(node);
}

// Right Left Case imbalance
if (balance < -1 && key < node->right->key)
{
	node->right = rightRotate(node->right);
	return leftRotate(node);
}

class Node {
  constructor() {
    this.data = -1; // 数据
    this.forwards = new Array(this.MAX_LEVEL);// 黑色小圆点
    this.maxLevel = 0;
  }
}

export class SkipList {
  constructor() {
    this.SKIPLIST_P = 0.5;
    this.MAX_LEVEL = 16;
    this.levelCount = 1;
    this.head = new Node();
  }

  find(value) {
    let p = this.head;
    for (let i = this.levelCount - 1; i >= 0; --i) {
      while (p.forwards[i] !== null && p.forwards[i].data < value) {
        p = p.forwards[i];
      }
    }

    if (p.forwards[0] !== null && p.forwards[0].data === value) {
      return p.forwards[0];
    } else {
      return null;
    }
  }

  insert(value) {
    const level = value === 5 ? 2: 1;
    const newNode = new Node();
    newNode.data = value;
    newNode.maxLevel = level;
    const update = new Array(level).fill(this.head);

    let p = this.head;
    for (let i = level - 1; i >= 0; --i) {
      while (p.forwards[i] && p.forwards[i].data < value) {
        p = p.forwards[i];
      }
      update[i] = p;
    }

    for (let i = 0; i < level; ++i) {
      newNode.forwards[i] = update[i].forwards[i];
      update[i].forwards[i] = newNode;
    }

    if (this.levelCount < level) this.levelCount = level;
  }

  delete(value) {
    const update = new Array(this.levelCount);
    let p = this.head;
    for (let i = this.levelCount - 1; i >= 0; --i) {
      while (p.forwards[i] !== null && p.forwards[i].data < value) {
        p = p.forwards[i];
      }
      update[i] = p;
    }

    if (p.forwards[0] !== null && p.forwards[0].data === value) {
      for (let i = this.levelCount - 1; i >= 0; --i) {
        if (
          update[i].forwards[i] !== null &&
          update[i].forwards[i].data === value
        ) {
          update[i].forwards[i] = update[i].forwards[i].forwards[i];
        }
      }
    }

    while (
      this.levelCount > 1 &&
      this.head.forwards[this.levelCount] === null
    ) {
      this.levelCount--;
    }
  }

  randomLevel() {
    let level = 1;

    while (Math.random() < this.SKIPLIST_P && level < this.MAX_LEVEL) {
      level += 1;
    }
    return level;
  }

  printAll() {
    let p = this.head;
    while (p.forwards && p.forwards[0] !== null) {
      console.log(p.forwards[0]);
      p = p.forwards[0];
    }
    console.log();
  }
}

class Node {
  constructor() {
    this.data = -1;
    this.forwards = new Array(this.MAX_LEVEL);
    this.maxLevel = 0;
  }

  toString() {
    return `{ data: ${this.data}, levels: ${this.maxLevel} }`;
  }
}

class SkipListNode {
  constructor(value, level) {
    this.value = value;
    this.next = new Array(level).fill(null);
  }
}

class SkipList {
  constructor() {
    this.head = new SkipListNode(null, 32);
    this.maxLevel = 0;
  }

  randomLevel() {
    let level = 1;
    while (Math.random() < 0.5 && level < this.head.next.length) {
      level++;
    }
    return level;
  }

  insert(value) {
    const newNodeLevel = this.randomLevel();
    const newNode = new SkipListNode(value, newNodeLevel);

    let currentNode = this.head;
    const update = new Array(newNodeLevel).fill(null);

    for (let i = this.maxLevel - 1; i >= 0; i--) {
      while (currentNode.next[i] && currentNode.next[i].value < value) {
        currentNode = currentNode.next[i];
      }
      update[i] = currentNode;
    }

    for (let i = 0; i < newNodeLevel; i++) {
      newNode.next[i] = update[i].next[i];
      update[i].next[i] = newNode;
    }

    if (newNodeLevel > this.maxLevel) {
      this.maxLevel = newNodeLevel;
    }
  }

  search(value) {
    let currentNode = this.head;
    for (let i = this.maxLevel - 1; i >= 0; i--) {
      while (currentNode.next[i] && currentNode.next[i].value < value) {
        currentNode = currentNode.next[i];
      }
    }
    currentNode = currentNode.next[0];

    if (currentNode && currentNode.value === value) {
      return currentNode;
    }
    return null;
  }
}

function createAdjacencyList(relationships) {
  const adjacencyList = {};

  for (const node in relationships) {
    if (relationships.hasOwnProperty(node)) {
      const skipList = new SkipList();
      const neighbors = relationships[node];

      for (const neighbor of neighbors) {
        skipList.insert(neighbor);
      }

      adjacencyList[node] = skipList;
    }
  }

  return adjacencyList;
}
//
// const relationships = {
//   1: [2],
//   2: [1, 3, 4],
//   3: [2, 5],
//   4: [1, 2, 5],
//   5: [2, 3, 4],
// };
//
// const adjacencyList = createAdjacencyList(relationships);
// console.log(adjacencyList);

class Node {
    constructor() {
        this.data = -1; // 数据
        this.forwards = new Array(this.MAX_LEVEL); // 黑色小圆点（指针数组）
        this.maxLevel = 0; // 当前节点的最大层级
    }
}

class Graph {
    constructor(v) {
        this.v = v;
        this.adj = new Array(v); // 邻接表（数组）
        for (let i = 0; i < v; ++i) {
           this.adj[i] = new LinkedList(); // 链表或者跳表
        }
    }
}

class Graph {
    constructor(v) {
        this.v = v;
        this.adj = new Array(v); // 邻接矩阵（二维数组）
        for (let i = 0; i < v; ++i) {
            this.adj[i] = [];
        }
    }
}

const graph = {
	A: ['B', 'C'],
	B: ['D'],
	c: []
}

function bfs(graph) {
	const queue = [];
	const visited = new Set();
	const prev = [];

	queue.push(Object.keys(graph)[0])

	while(queue.length > 0) {
		const current = queue.shift();
		visited.push(current)
		prev.push(current)
		for(const edge of current) {
			if(!visited.has(edge)) {
				queue.push(edge)
				prev.push(edge)
			}
		}
	}
	return prev
}

// @params { number } v   顶点个数
// @params { array }  arr 邻接矩阵
//  0 1 2 3 4 
//0 1 0 1 0
//1 1 1
//2 
//3

// 邻接矩阵
function topo(v, arr) {
    let inDegree = new Array(v).fill(0)
	for(let i = 0; i<v; i++) { // v 是5
		if(let j = 0; j < arr[i].length; j++) {
		    if(arr[i][j] === 1) {
				inDegree[j]++
			}
		}
	}

	let queue = []
	for(let i = 0; i < v; i++) {
		if(inDegge[i] === 0) {
			queue.push(i)
		}
	}

	let result = [];
	while(queue.length > 0) {
		const i = queue.shift()
		result.push(i)
		for(let j = 0; j < arr[i].length; j++) {
			if(arr[i][j] === 1) {
				inDegree[j]--
				if(inDegree[j] === 0) {
					queue.push(j)
				}
			}
		}
	}

	if(result.length !== v) {
		// 存在环
	}

}

// 临接表
const graph = {
	A: ['B', 'C'],
	B: ['D'],
	c: []
}
·
function topo(graph) {
    const nodes = Object.keys(graph);
    const inDegree = new Map();// 用对象也OK 相当于是逆邻接表

	for(const node of nodes) {
		const edges = graph[node];
		// for(const edge of edges)
		for(let j = 0; j < edges.length; j++) {
			const w = edges[j]
			inDegree.set(w, (inDegree.get(w) || 0 ) + 1)
		}
	}

	const queue = []
	for(const [key, value] of inDegree) {
		if(value===0) {
			queue.push(key)
		}
	}

	let result = []
	while(queue.length > 0) {
		const w = queue.shift()
		result.push(w)
		for(let j = 0; j < graph[w].length; j++) {
			const w = graph[w][j]
			inDegree.set(w, inDegree.get(w) - 1)
			if(inDegree.get(w) === 0) {
				queue.push(w)
			}
		}
	}

	if(result.length !== nodes.length) {
		// 存在环
	}
}

function topoSortByDFS() {
  // 先构建逆邻接表，边s->t表示，s依赖于t，t先于s
  const inverseAdj = new Array(v).fill().map(() => []);
  for (let i = 0; i < v; ++i) {
    for (let j = 0; j < adj[i].length; ++j) {
      const w = adj[i][j]; // i->w
      inverseAdj[w].push(i); // w->i
    }
  }
  const visited = new Array(v).fill(false);
  for (let i = 0; i < v; ++i) {
    if (!visited[i]) {
      visited[i] = true;
      dfs(i, inverseAdj, visited);
    }
  }
}

function dfs(vertex, inverseAdj, visited) {
  for (let i = 0; i < inverseAdj[vertex].length; ++i) {
    const w = inverseAdj[vertex][i];
    if (visited[w]) continue;
    visited[w] = true;
    dfs(w, inverseAdj, visited);
  }
  // 先把vertex这个顶点可达的所有顶点都打印出来之后，再打印它自己
  console.log("->" + vertex);
}

const visited = new Set()
for(let node of graph) {
	if(!visited.has(node)) {
		dfs(node)
	}
}

function dfs(node) {
    visited.add(node)
    const neighbors = graph[node] || []
    for(const neighbor of neighbors) {
    	if(!visited.has(neighbor)) {
    		dfs(neighbor)
    	}
    }
    stack.unshift(node) // u->v 先将u推入栈中。保证最后输出的是v, u
}
return stack;

// // 邻接表
// class Node {
//     constructor(vertex) {
//         this.vertex = vertex;
//         this.next = null;
//     }
// }
// export function addEdge(adj, source, destination) {
//     let newNode = new Node(destination);
//     newNode.next = adj[source];
//     adj[source] = newNode;
// }

class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

// class LinkedList {
//     constructor() {
//         this.head = null;
//     }
//
//     add(value) {
//         const newNode = new Node(value);
//         if (!this.head) {
//             this.head = newNode;
//         } else {
//             let current = this.head;
//             while (current.next) {
//                 current = current.next;
//             }
//             current.next = newNode;
//         }
//     }
// }

// class Graph {
//     constructor(v) {
//         this.v = v;
//         this.adj = new Array(v);
//         for (let i = 0; i < v; ++i) {
//             this.adj[i] = new LinkedList();
//         }
//     }
//
//     addEdge(s, t) {
//         this.adj[s].add(t);
//         this.adj[t].add(s);
//     }
// }

class Graph {
    constructor(v) {
        this.v = v;
        this.adj = new Array(v);
        for (let i = 0; i < v; ++i) {
            this.adj[i] = [];
        }
    }

    /**
     *
     * @param s s是顶点
     * @param t
     */
    addEdge(s, t) {
        this.adj[s].push(t);
        this.adj[t].push(s);
    }
}

// // 邻接矩阵
// let adj = [
//     [1, 2],    // Adjacency list for vertex 0
//     [0, 2, 3], // Adjacency list for vertex 1
//     [0, 1, 4], // Adjacency list for vertex 2
//     [1],       // Adjacency list for vertex 3
//     [2]        // Adjacency list for vertex 4
// ];

import { addEdge } from "./adj-list";

/**
 * 广度优先
 * @param s
 * @param t
 */
function bfs(adj, s, t) {
  if (s === t) return;
  const visited = new Array(v).fill(false);
  visited[s] = true;
  const queue = [];
  queue.push(s);
  const prev = new Array(v).fill(-1);
  while (queue.length !== 0) {
    const w = queue.shift();
    for (let i = 0; i < adj[w].length; i++) {
      const q = adj[w][i]; // adj[w].get(i) 但是链表取i不方便，所以可以改为跳表
      if (!visited[q]) {
        prev[q] = w;
        if (q === t) {
          print(prev, s, t);
          return;
        }
        visited[q] = true;
        queue.push(q);
      }
    }
  }
}

function print(prev, s, t) {
  if (prev[t] !== -1 && t !== s) {
    print(prev, s, prev[t]);
  }
  console.log(t + " ");
}

// 深度優先搜索
let found = false; // 全局变量或类成员变量

function dfs(adj, s, t) {
  found = false;
  const visited = new Array(v).fill(false);
  const prev = new Array(v).fill(-1);
  for (let i = 0; i < v; ++i) {
    prev[i] = -1;
  }
  recurDfs(s, t, visited, prev);
  print(prev, s, t);
}

function recurDfs(adj, w, t, visited, prev) {
  if (found === true) return;
  visited[w] = true;
  if (w === t) {
    found = true;
    return;
  }
  for (let i = 0; i < adj[w].length; ++i) {
    const q = adj[w][i];
    if (!visited[q]) {
      prev[q] = w;
      recurDfs(q, t, visited, prev);
    }
  }
}
// Helper function to print the path
function print(prev, s, t) {
  // Implement your own logic to print the path
  // based on the 'prev' array and the given 's' and 't'
}


export function graph_bfs_function() {
  // Example usage
  let v = 5; // Number of vertices

  let adj = new Array(v).fill(null);

// Add edges to the adjacency list using linked list
  addEdge(adj, 0, 1);
  addEdge(adj,0, 2);
  addEdge(adj,1, 2);
  addEdge(adj,1, 3);
  addEdge(adj,2, 4);

  let source = 0; // Source vertex
  let target = 4; // Target vertex

  bfs(adj, source, target, v);
  return true;
}

export function test_bfs_function() {
// Example usage
  let v = 5; // Number of vertices

  let adj = new Array(v).fill(null);

// Add edges to the adjacency list using linked list
  addEdge(adj, 0, 1);
  addEdge(adj,0, 2);
  addEdge(adj,1, 2);
  addEdge(adj,1, 3);
  addEdge(adj,2, 4);

  let source = 0; // Source vertex
  let target = 4; // Target vertex

  dfs(adj, source, target);
}

class Graph {
    constructor(v) {
        this.v = v; // 顶点数
        this.adj = new Array(v); // 邻接表（数组）
        for (let i = 0; i < v; ++i) {
            this.adj[i] = new LinkedList(); // 链表或跳表
        }
    }
}

class Graph {
    constructor(v) {
        this.v = v; // 顶点数
        this.adj = new Array(v); // 邻接矩阵（二维数组）
        for (let i = 0; i < v; ++i) {
            this.adj[i] = [];
        }
    }
}

class TreeNode {
    constructor(value) {
        this.value = value;
        this.left = null; // 左子节点
        this.right = null; // 右子节点
    }
}

const createTrieNode = (data) => {
  return {
    data,
    children: Array(26)
      .fill(null),
    isEndingChar: false,
  };
};

const createTrie = () => {
  const root = createTrieNode("/");
  const insert = (words: string) => {
    let p = root;
    Array.from(words).forEach((c: string) => {
      let index: number = c.charCodeAt(0) - "a".charCodeAt(0);
      // 创建新节点
      if (p.children[index] === null) {
        p.children[index] = createTrieNode(c);
      }
      // 指向新节点
      p = p.children[index];
    });
    // 标记为单词结束节点
    p.isEndingChar = true;
  };
  const find = (pattern: string) => {
    let p = root;
    Array.from(pattern).forEach((c: string) => {
      let index = c.charCodeAt(0) - "a".charCodeAt(0);
      if (p.children[index] === null) {
        return false; // not found
      }
      p = p.children[index]; // found
    });
    if (p.isEndingChar === false) return false; // 不能完全匹配
    return true; //找到单词。完全匹配
  };

  return {
    insert,
    find,
  };
};

export function trie_TestFunction() {
  const trie = createTrie();
  const { insert, find } = trie;
  insert("apple");
  insert("app");
  insert("application");
  insert("banana");
  insert("bat");
  insert("cat");
  // 某一个串是否在trie树中
  const result = find("app");
  console.log(result);
  return result
}