C语言实现动态开辟存储杨辉三角
目录
- 问题引入
- 解决方法
- 思路分析
- C代码实现
- C++实现
问题引入
杨辉三角相必大家并不陌生,第1行有1列、第二行有2列…第n行有n列,且每行行首和行尾的值都为1,其余的值为上一行两数相加
我们在C语言阶段,第一次碰到的杨辉三角应该都是用常规的二维数组存储,可以观察到,用绿色填充的空间都是没有被利用的。
存储1行 浪费0个
存储2行 浪费1个
存储3行 浪费3个
存储4行 浪费6个
.
.
.
存储n行 浪费n*(n+1)/2-n个
解决方法
这样极大浪费空间资源,今天我们就来试试动态开辟存储杨辉三角,可以灵活的开辟空间,充分的利用空间。
思路分析
首先用指针pp维护动态开辟的int*类型的指针,再通过int*类型的指针去维护动态开辟的int型数据存储杨辉三角
C代码实现
#include <stdio.h> #include <stdlib.h> void PrintFree(int** pp, int numrows) { //打印 for (int i = 0; i < numrows; i++) { for (int k = 0; k < numrows - i; k++) { printf(" "); } for (int j = 0; j <= i; j++) { printf("%4d", pp[i][j]); //可以根据打印的行数适当调整右对齐 printf(" "); } printf("\n"); } } //清理malloc出来的空间 for (int i = 0; i < numrows; i++) { free(pp[i]); pp[i] = NULL; } } int main() { //杨辉三角的行数 int numrows; scanf("%d", &numrows); //开辟numrows个int*类型的指针用来维护int型的数据 int** pp = (int**)malloc(sizeof(int*) * numrows); for (int i = 0; i < numrows; i++) { //int型数据个数随着行数的增加而增加 pp[i] = (int*)malloc(sizeof(int) * (i + 1)); } for (int i = 0; i < numrows; i++) { for (int j = 0; j <= i; j++) { //每行的行首和行尾都是1 if (j == 0 || i == j) { pp[i][j] = 1; // 等价于 *(*(pp+i)+j) } //其余的就是上一行的两个数据相加 else { pp[i][j] = pp[i - 1][j - 1] + pp[i - 1][j]; } } } PrintFree(pp, numrows); return 0; }
大家可以根据需要打印的行数大小在上面的打印函数适当调整
C++实现
用C++就非常方便了,STL中的vector就可以很方便的解决
#include <iostream> #include <vector> using namespace std; //打印函数 void Print(vector<vector<int>> vv, int numrows) { for (int i = 0; i < numrows; i++) { for (int j = 0; j <= i; j++) { cout << vv[i][j] << " "; } cout << endl; } } int main() { int numrows; cin >> numrows; vector<vector<int>> vv; for (int i = 0; i < numrows; i++) { //每次开i+1个vector<int> vv.resize(i + 1); //每次开i+1个int vv[i].resize(i + 1); } for (int i = 0; i < numrows; i++) { for (int j = 0; j <= i; j++) { if (j == 0 || i == j) { vv[i][j] = 1; } else { vv[i][j] = vv[i - 1][j - 1] + vv[i - 1][j]; } } } Print(vv, numrows); return 0; }
以上就是通过动态开辟的杨辉三角了
到此这篇关于C语言实现动态开辟存储杨辉三角的文章就介绍到这了,更多相关C语言杨辉三角内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!
赞 (0)