JavaScript 数据结构与算法实现详解

顺序表（数组）基本操作

1. 顺序表打印

class SeqList {
    constructor(maxSize = 100) {
        this.data = new Array(maxSize);
        this.length = 0;
        this.MAX_SIZE = maxSize;
    }

    // 打印顺序表
    printList() {
        if (this.length === 0) {
            console.log("顺序表为空");
            return;
        }
        
        let result = "";
        for (let i = 0; i < this.length; i++) {
            result += this.data[i] + " ";
        }
        console.log("顺序表内容: " + result.trim());
    }
}

// 使用示例
const seqList = new SeqList();
seqList.data = [1, 3, 5, 7, 9];
seqList.length = 5;
seqList.printList(); // 输出: 顺序表内容: 1 3 5 7 9

2. 顺序表查找

class SeqList {
    // ... 其他代码同上
    
    // 顺序查找元素x的位置（从1开始计数）
    locateElement(x) {
        for (let i = 0; i < this.length; i++) {
            if (this.data[i] === x) {
                return i + 1; // 返回位置（从1开始）
            }
        }
        return 0; // 未找到返回0
    }
    
    // 改进版：使用哨兵简化边界判断
    locateElementWithSentinel(x) {
        // 保存原最后一个元素
        const originalLast = this.length < this.MAX_SIZE ? 
            this.data[this.length] : null;
        
        // 设置哨兵
        if (this.length < this.MAX_SIZE) {
            this.data[this.length] = x;
        }
        
        let i = 0;
        while (this.data[i] !== x) {
            i++;
        }
        
        // 恢复原最后一个元素
        if (originalLast !== null) {
            this.data[this.length] = originalLast;
        }
        
        return i < this.length ? i + 1 : 0;
    }
}

// 测试查找功能
console.log("位置:", seqList.locateElement(5)); // 输出: 3
console.log("位置:", seqList.locateElement(10)); // 输出: 0

3. 顺序表插入

class SeqList {
    // ... 其他代码同上
    
    // 在位置i插入元素x（i从1开始）
    insertElement(x, i) {
        // 检查插入位置合法性
        if (i < 1 || i > this.length + 1) {
            throw new Error("插入位置非法");
        }
        
        // 检查表是否已满
        if (this.length >= this.MAX_SIZE) {
            throw new Error("表空间溢出");
        }
        
        // 从后向前移动元素
        for (let j = this.length - 1; j >= i - 1; j--) {
            this.data[j + 1] = this.data[j];
        }
        
        // 插入新元素
        this.data[i - 1] = x;
        this.length++;
        
        return true;
    }
}

// 测试插入功能
seqList.insertElement(4, 3); // 在位置3插入4
seqList.printList(); // 输出: 1 3 4 5 7 9

4. 顺序表删除

class SeqList {
    // ... 其他代码同上
    
    // 删除位置i的元素（i从1开始）
    deleteElement(i) {
        // 检查删除位置合法性
        if (i < 1 || i > this.length) {
            throw new Error("删除位置非法");
        }
        
        const deletedElement = this.data[i - 1];
        
        // 从前向后移动元素覆盖要删除的元素
        for (let j = i; j < this.length; j++) {
            this.data[j - 1] = this.data[j];
        }
        
        this.length--;
        return deletedElement;
    }
}

// 测试删除功能
const deleted = seqList.deleteElement(4); // 删除位置4的元素（5）
console.log("删除的元素:", deleted); // 输出: 5
seqList.printList(); // 输出: 1 3 4 7 9

5. 顺序表逆置

class SeqList {
    // ... 其他代码同上
    
    // 就地逆置顺序表（空间复杂度O(1)）
    reverse() {
        for (let i = 0; i < Math.floor(this.length / 2); i++) {
            // 交换对称位置的元素
            const temp = this.data[i];
            this.data[i] = this.data[this.length - 1 - i];
            this.data[this.length - 1 - i] = temp;
        }
    }
    
    // 递归方式逆置
    reverseRecursive(start = 0, end = this.length - 1) {
        if (start >= end) return;
        
        // 交换首尾元素
        const temp = this.data[start];
        this.data[start] = this.data[end];
        this.data[end] = temp;
        
        // 递归处理中间部分
        this.reverseRecursive(start + 1, end - 1);
    }
}

// 测试逆置功能
seqList.reverse();
seqList.printList(); // 输出: 9 7 4 3 1

6. 有序顺序表插入

class SeqList {
    // ... 其他代码同上
    
    // 方法1：从后向前找到插入位置
    insertOrderedFromEnd(x) {
        if (this.length >= this.MAX_SIZE) {
            throw new Error("表空间溢出");
        }
        
        let i = this.length - 1;
        // 寻找插入位置并移动元素
        while (i >= 0 && this.data[i] > x) {
            this.data[i + 1] = this.data[i];
            i--;
        }
        
        this.data[i + 1] = x;
        this.length++;
    }
    
    // 方法2：从前向后找到插入位置
    insertOrderedFromStart(x) {
        if (this.length >= this.MAX_SIZE) {
            throw new Error("表空间溢出");
        }
        
        if (this.length === 0 || x >= this.data[this.length - 1]) {
            // 直接插入末尾
            this.data[this.length] = x;
        } else {
            // 寻找第一个大于x的位置
            let i = 0;
            while (i < this.length && x >= this.data[i]) {
                i++;
            }
            
            // 移动元素
            for (let j = this.length - 1; j >= i; j--) {
                this.data[j + 1] = this.data[j];
            }
            
            this.data[i] = x;
        }
        
        this.length++;
    }
}

// 测试有序插入
const orderedList = new SeqList();
orderedList.data = [1, 3, 5, 7, 9];
orderedList.length = 5;

orderedList.insertOrderedFromEnd(6);
orderedList.printList(); // 输出: 1 3 5 6 7 9

orderedList.insertOrderedFromStart(4);
orderedList.printList(); // 输出: 1 3 4 5 6 7 9

单链表基本操作

1. 链表节点定义

class ListNode {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    constructor() {
        this.head = null;
    }
}

2. 单链表的建立

class LinkedList {
    // ... 其他代码同上
    
    // 头插法建立单链表（无头结点）
    createFromHead(arr) {
        this.head = null;
        
        for (let i = arr.length - 1; i >= 0; i--) {
            const newNode = new ListNode(arr[i]);
            newNode.next = this.head;
            this.head = newNode;
        }
        
        return this.head;
    }
    
    // 尾插法建立单链表（无头结点）
    createFromTail(arr) {
        if (arr.length === 0) {
            this.head = null;
            return null;
        }
        
        this.head = new ListNode(arr[0]);
        let current = this.head;
        
        for (let i = 1; i < arr.length; i++) {
            const newNode = new ListNode(arr[i]);
            current.next = newNode;
            current = newNode;
        }
        
        return this.head;
    }
    
    // 尾插法建立单链表（带头结点）
    createWithHeadNode(arr) {
        const headNode = new ListNode(null); // 头结点，数据域为null
        let current = headNode;
        
        for (let i = 0; i < arr.length; i++) {
            const newNode = new ListNode(arr[i]);
            current.next = newNode;
            current = newNode;
        }
        
        this.head = headNode;
        return headNode;
    }
}

// 测试链表建立
const list = new LinkedList();
list.createFromHead([1, 2, 3, 4, 5]);

3. 单链表的基本操作

class LinkedList {
    // ... 其他代码同上
    
    // 打印链表（不带头结点）
    printList() {
        let current = this.head;
        let result = "";
        
        while (current !== null) {
            result += current.data + " -> ";
            current = current.next;
        }
        
        result += "NULL";
        console.log(result);
    }
    
    // 打印链表（带头结点）
    printListWithHead() {
        let current = this.head.next; // 跳过头结点
        let result = "HEAD -> ";
        
        while (current !== null) {
            result += current.data + " -> ";
            current = current.next;
        }
        
        result += "NULL";
        console.log(result);
    }
    
    // 查找第i个节点
    getNode(i) {
        if (i < 1) return null;
        
        let current = this.head;
        let count = 0;
        
        while (current !== null && count < i) {
            current = current.next;
            count++;
        }
        
        return current;
    }
    
    // 查找值为key的节点
    locateNode(key) {
        let current = this.head;
        
        while (current !== null) {
            if (current.data === key) {
                return current;
            }
            current = current.next;
        }
        
        return null;
    }
    
    // 获取链表长度
    getLength() {
        let count = 0;
        let current = this.head;
        
        while (current !== null) {
            count++;
            current = current.next;
        }
        
        return count;
    }
    
    // 获取带头结点链表的长度
    getLengthWithHead() {
        let count = 0;
        let current = this.head.next; // 跳过头结点
        
        while (current !== null) {
            count++;
            current = current.next;
        }
        
        return count;
    }
}

4. 单链表的插入和删除

class LinkedList {
    // ... 其他代码同上
    
    // 在位置i插入新节点
    insertAt(i, x) {
        if (i < 1) return false;
        
        // 处理在头部插入的情况
        if (i === 1) {
            const newNode = new ListNode(x);
            newNode.next = this.head;
            this.head = newNode;
            return true;
        }
        
        // 找到第i-1个节点
        const prevNode = this.getNode(i - 1);
        if (prevNode === null) {
            return false; // 插入位置非法
        }
        
        const newNode = new ListNode(x);
        newNode.next = prevNode.next;
        prevNode.next = newNode;
        
        return true;
    }
    
    // 删除位置i的节点
    deleteAt(i) {
        if (i < 1 || this.head === null) return null;
        
        // 处理删除头节点的情况
        if (i === 1) {
            const deletedNode = this.head;
            this.head = this.head.next;
            return deletedNode;
        }
        
        // 找到第i-1个节点
        const prevNode = this.getNode(i - 1);
        if (prevNode === null || prevNode.next === null) {
            return null; // 删除位置非法
        }
        
        const deletedNode = prevNode.next;
        prevNode.next = deletedNode.next;
        
        return deletedNode;
    }
}

5. 单链表逆置

class LinkedList {
    // ... 其他代码同上
    
    // 迭代法逆置链表
    reverseIterative() {
        let prev = null;
        let current = this.head;
        let next = null;
        
        while (current !== null) {
            next = current.next; // 保存下一个节点
            current.next = prev; // 反转指针
            prev = current;      // 移动prev
            current = next;      // 移动current
        }
        
        this.head = prev; // 更新头指针
    }
    
    // 递归法逆置链表
    reverseRecursive(node = this.head) {
        if (node === null || node.next === null) {
            this.head = node; // 更新头指针指向新的头节点
            return node;
        }
        
        const newHead = this.reverseRecursive(node.next);
        node.next.next = node;
        node.next = null;
        
        return newHead;
    }
    
    // 三指针法逆置（更易理解版本）
    reverseThreePointers() {
        if (this.head === null || this.head.next === null) {
            return; // 空表或只有一个节点不需要逆置
        }
        
        let p = this.head;
        let q = this.head.next;
        let r = null;
        
        while (q !== null) {
            r = q.next; // 保存下一个节点
            q.next = p; // 反转指针
            p = q;      // 移动p
            q = r;      // 移动q
        }
        
        this.head.next = null; // 原头节点变为尾节点
        this.head = p;         // 更新头指针
    }
}

// 测试逆置功能
const list = new LinkedList();
list.createFromTail([1, 2, 3, 4, 5]);
console.log("原链表:");
list.printList(); // 1 -> 2 -> 3 -> 4 -> 5 -> NULL

list.reverseIterative();
console.log("逆置后:");
list.printList(); // 5 -> 4 -> 3 -> 2 -> 1 -> NULL

6. 有序单链表的插入

class LinkedList {
    // ... 其他代码同上
    
    // 有序插入（递减有序表）
    insertOrderedDescending(x) {
        const newNode = new ListNode(x);
        
        // 空表或新节点值大于等于头节点
        if (this.head === null || x >= this.head.data) {
            newNode.next = this.head;
            this.head = newNode;
            return;
        }
        
        // 寻找插入位置
        let current = this.head;
        while (current.next !== null && x < current.next.data) {
            current = current.next;
        }
        
        newNode.next = current.next;
        current.next = newNode;
    }
    
    // 另一种方法：先插入到头节点，然后通过交换调整到正确位置
    insertOrderedWithSwap(x) {
        const newNode = new ListNode(x);
        newNode.next = this.head;
        this.head = newNode;
        
        let current = this.head;
        
        // 通过交换将新节点移动到正确位置
        while (current.next !== null && current.data > current.next.data) {
            // 交换数据域
            [current.data, current.next.data] = [current.next.data, current.data];
            current = current.next;
        }
    }
}

7. 单链表的合并

class LinkedList {
    // ... 其他代码同上
    
    // 合并两个有序链表（递增有序）
    static mergeSortedLists(listA, listB) {
        // 创建新链表的头结点
        const dummyHead = new ListNode(null);
        let current = dummyHead;
        
        let p = listA.head;
        let q = listB.head;
        
        // 合并两个有序链表
        while (p !== null && q !== null) {
            if (p.data <= q.data) {
                current.next = new ListNode(p.data);
                p = p.next;
            } else {
                current.next = new ListNode(q.data);
                q = q.next;
            }
            current = current.next;
        }
        
        // 将剩余部分接到新链表
        while (p !== null) {
            current.next = new ListNode(p.data);
            p = p.next;
            current = current.next;
        }
        
        while (q !== null) {
            current.next = new ListNode(q.data);
            q = q.next;
            current = current.next;
        }
        
        const mergedList = new LinkedList();
        mergedList.head = dummyHead.next;
        return mergedList;
    }
}

// 测试合并功能
const listA = new LinkedList();
listA.createFromTail([1, 3, 5, 7]);

const listB = new LinkedList();
listB.createFromTail([2, 4, 6, 8]);

const mergedList = LinkedList.mergeSortedLists(listA, listB);
console.log("合并后的有序链表:");
mergedList.printList(); // 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> NULL

算法性能分析

时间复杂度分析

操作	顺序表	单链表
访问第i个元素	O(1)	O(n)
在头部插入/删除	O(n)	O(1)
在尾部插入/删除	O(1)	O(n)
在中间插入/删除	O(n)	O(n)
查找	O(n)	O(n)
逆置	O(n)	O(n)

空间复杂度分析

• 顺序表：需要预分配固定大小的空间，可能造成空间浪费
• 单链表：动态分配空间，不需要预分配，但每个节点需要额外的指针空间

实际应用场景

1. 顺序表适用场景：

   • 需要频繁随机访问元素
   • 元素数量相对固定
   • 内存空间充足

2. 单链表适用场景：

   • 需要频繁在头部插入/删除元素
   • 元素数量变化较大
   • 内存使用需要更灵活

这些基础数据结构和算法是计算机科学的基石，熟练掌握它们对于解决复杂问题和优化程序性能至关重要。