1.01 主要数据结构的实现

当然, 我可以为您提供一些使用 TypeScript 实现主要数据结构和算法的案例。这些案例涵盖了链表、二叉树、图以及一些常见的排序算法。

1. 链表 (Linked List)

class ListNode<T> {
    value: T;
    next: ListNode<T> | null;
 
    constructor(value: T) {
        this.value = value;
        this.next = null;
    }
}
 
class LinkedList<T> {
    head: ListNode<T> | null;
 
    constructor() {
        this.head = null;
    }
 
    append(value: T): void {
        const newNode = new ListNode(value);
        if (!this.head) {
            this.head = newNode;
            return;
        }
        let current = this.head;
        while (current.next) {
            current = current.next;
        }
        current.next = newNode;
    }
 
    print(): void {
        let current = this.head;
        while (current) {
            console.log(current.value);
            current = current.next;
        }
    }
}
 
// 使用示例
const list = new LinkedList<number>();
list.append(1);
list.append(2);
list.append(3);
list.print();

2. 二叉树 (Binary Tree)

class TreeNode<T> {
    value: T;
    left: TreeNode<T> | null;
    right: TreeNode<T> | null;
 
    constructor(value: T) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}
 
class BinaryTree<T> {
    root: TreeNode<T> | null;
 
    constructor() {
        this.root = null;
    }
 
    insert(value: T): void {
        const newNode = new TreeNode(value);
        if (!this.root) {
            this.root = newNode;
            return;
        }
        this.insertNode(this.root, newNode);
    }
 
    private insertNode(node: TreeNode<T>, newNode: TreeNode<T>): void {
        if (newNode.value < node.value) {
            if (node.left === null) {
                node.left = newNode;
            } else {
                this.insertNode(node.left, newNode);
            }
        } else {
            if (node.right === null) {
                node.right = newNode;
            } else {
                this.insertNode(node.right, newNode);
            }
        }
    }
 
    inOrderTraversal(node: TreeNode<T> | null): void {
        if (node !== null) {
            this.inOrderTraversal(node.left);
            console.log(node.value);
            this.inOrderTraversal(node.right);
        }
    }
}
 
// 使用示例
const tree = new BinaryTree<number>();
tree.insert(5);
tree.insert(3);
tree.insert(7);
tree.insert(1);
tree.insert(9);
tree.inOrderTraversal(tree.root);

3. 图 (Graph)

class Graph<T> {
    private adjacencyList: Map<T, T[]>;
 
    constructor() {
        this.adjacencyList = new Map();
    }
 
    addVertex(vertex: T): void {
        if (!this.adjacencyList.has(vertex)) {
            this.adjacencyList.set(vertex, []);
        }
    }
 
    addEdge(vertex1: T, vertex2: T): void {
        this.adjacencyList.get(vertex1)?.push(vertex2);
        this.adjacencyList.get(vertex2)?.push(vertex1);
    }
 
    removeEdge(vertex1: T, vertex2: T): void {
        this.adjacencyList.set(vertex1, this.adjacencyList.get(vertex1)?.filter(v => v !== vertex2) || []);
        this.adjacencyList.set(vertex2, this.adjacencyList.get(vertex2)?.filter(v => v !== vertex1) || []);
    }
 
    removeVertex(vertex: T): void {
        while (this.adjacencyList.get(vertex)?.length) {
            const adjacentVertex = this.adjacencyList.get(vertex)?.pop();
            if (adjacentVertex) {
                this.removeEdge(vertex, adjacentVertex);
            }
        }
        this.adjacencyList.delete(vertex);
    }
 
    depthFirstSearch(start: T): T[] {
        const result: T[] = [];
        const visited = new Set<T>();
        const dfs = (vertex: T) => {
            visited.add(vertex);
            result.push(vertex);
            this.adjacencyList.get(vertex)?.forEach(neighbor => {
                if (!visited.has(neighbor)) {
                    dfs(neighbor);
                }
            });
        };
        dfs(start);
        return result;
    }
}
 
// 使用示例
const graph = new Graph<string>();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addEdge("A", "B");
graph.addEdge("B", "C");
console.log(graph.depthFirstSearch("A"));

4. 排序算法

以下是几种常见排序算法的 TypeScript 实现：

A) 快速排序 (Quick Sort)

function quickSort<T>(arr: T[]): T[] {
    if (arr.length <= 1) {
        return arr;
    }
 
    const pivot = arr[Math.floor(arr.length / 2)];
    const left = arr.filter(x => x < pivot);
    const middle = arr.filter(x => x === pivot);
    const right = arr.filter(x => x > pivot);
 
    return [...quickSort(left), ...middle, ...quickSort(right)];
}
 
// 使用示例
console.log(quickSort([3, 6, 8, 10, 1, 2, 1]));

B) 归并排序 (Merge Sort)

function mergeSort<T>(arr: T[]): T[] {
    if (arr.length <= 1) {
        return arr;
    }
 
    const mid = Math.floor(arr.length / 2);
    const left = arr.slice(0, mid);
    const right = arr.slice(mid);
 
    return merge(mergeSort(left), mergeSort(right));
}
 
function merge<T>(left: T[], right: T[]): T[] {
    let result: T[] = [];
    let leftIndex = 0;
    let rightIndex = 0;
 
    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] < right[rightIndex]) {
            result.push(left[leftIndex]);
            leftIndex++;
        } else {
            result.push(right[rightIndex]);
            rightIndex++;
        }
    }
 
    return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}
 
// 使用示例
console.log(mergeSort([3, 6, 8, 10, 1, 2, 1]));

C) 冒泡排序 (Bubble Sort)

function bubbleSort<T>(arr: T[]): T[] {
    const len = arr.length;
    for (let i = 0; i < len; i++) {
        for (let j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
            }
        }
    }
    return arr;
}
 
// 使用示例
console.log(bubbleSort([3, 6, 8, 10, 1, 2, 1]));

这些案例展示了如何使用 TypeScript 实现一些基本的数据结构和算法。它们可以作为学习和理解这些概念的起点, 并可以根据具体需求进行进一步的优化和扩展。在实际应用中, 可能需要考虑更多的边界情况和错误处理。