Java顺序表实现杨辉三角

杨辉三角，又称帕斯卡三角，是二项式系数在三角形中的一种几何排列。每一行的两端都是1，中间的数字等于上一行相邻两数之和。本文将使用Java中的顺序表（即ArrayList）来逐步实现杨辉三角的生成，帮助初学者理解数据结构和算法练习。

1. 什么是顺序表？

在Java中，顺序表通常指ArrayList，它是一种基于动态数组的数据结构，可以动态地添加和删除元素。使用顺序表可以很方便地存储杨辉三角的每一行，因为每一行的长度不同，而ArrayList可以自动扩容。

2. 实现思路

要实现杨辉三角，我们可以使用一个嵌套的List>来存储整个三角。外层列表的每个元素代表一行，内层列表代表该行的具体数值。具体步骤如下：

• 初始化一个空的List>，命名为triangle。
• 循环从0到numRows-1，依次生成每一行。
• 对于第i行（0-indexed），创建一个新的List，名为row。
• 每一行的第一个元素和最后一个元素都是1，因此我们可以在开头和结尾添加1。
• 对于中间的元素（如果存在），则根据上一行的对应位置计算：row.add(prevRow.get(j-1) + prevRow.get(j))。
• 将当前行添加到triangle中。

这个过程就是经典的杨辉三角实现算法，也是面试中常见的算法练习题。

3. 代码实现

下面给出完整的Java代码，使用顺序表实现杨辉三角。代码中包含详细的注释，方便理解。

import java.util.ArrayList;import java.util.List;public class YangHuiTriangle {    public static List> generate(int numRows) {        List> triangle = new ArrayList<>();        if (numRows == 0) return triangle;                // 第一行总是 [1]        triangle.add(new ArrayList<>());        triangle.get(0).add(1);                for (int i = 1; i < numRows; i++) {            List prevRow = triangle.get(i - 1);            List newRow = new ArrayList<>();                        // 第一个元素总是1            newRow.add(1);                        // 中间元素：上一行的相邻两数之和            for (int j = 1; j < prevRow.size(); j++) {                newRow.add(prevRow.get(j - 1) + prevRow.get(j));            }                        // 最后一个元素总是1            newRow.add(1);                        triangle.add(newRow);        }        return triangle;    }        public static void main(String[] args) {        int numRows = 5;        List> result = generate(numRows);        // 打印杨辉三角        for (List row : result) {            for (int num : row) {                System.out.print(num + " ");            }            System.out.println();        }    }}

运行上述代码，输出结果如下：

1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 

通过这个例子，我们可以看到使用Java顺序表实现杨辉三角非常直观。这种数据结构教程中的经典案例，有助于加深对动态数组和嵌套集合的理解。

4. 总结

本文详细介绍了如何用Java的ArrayList顺序表来实现杨辉三角，从概念到代码一步步讲解，适合Java初学者学习数据结构和算法练习。希望大家能动手实践，并尝试优化或扩展，比如打印成等腰三角形形状。如果你有任何疑问，欢迎在评论区交流！